lkml.org 
[lkml]   [2006]   [Apr]   [4]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
Subject[RFC2] non-power of 2 allocator for noMMU Linux
Based on the feedback we got last week, Phil did look into alloc_exact, and 
had the following thoughts:

>
> It looks simple but the trouble is that all the freed pages are freed
> one at a time.
>
> So you get a po2 block of memory and return the excess to the single
> page list ( hot pages )
>
> When you free the allocation you return the original block ( less the
> already freed pages ) to the hot page list as single pages.
>
> I guess the system will then see too many hot pages and combine them
> but I have not researched this.
>
> I see a possible increased risk of fragmentation with this system.
> The idea of taking a large block of memory and then splitting the
> whole thing up into a large number of single pages troubles me.
>
> I have dropped the hot page list in sidekick. single pages are kept as
> is in the latest version.
>
> The manual merge ( which could be simply automated if needed ) will
> perform the page combination.

The non-power of 2 patch he has been working on (which is stable enough to
boot a system) is at:

http://blackfin.uclinux.org/tracker/index.php?func=detail&aid=1175

It is not Blackfin specific. We just have a number of these systems set
up for testing.

This was the notice he sent to the uClinuc-dev mailing list a few days ago:
>I have been working for a few weeks on a non power of 2 allocator for the
>2.6 kernel.
>The work was triggered by the arrival of the slob allocator, I got the
>basis of an idea from that system.
>
>The objective was to provide a system that could be used in smaller memory
>footprints and not incur the power of 2 overhead for all allocations in a
>non MMU environment
>
>The operation is quite simple. All available memory is turned into a super
>slob and, if you ask for an allocation of order size 4 or more then you
>will get the exact number of pages you need to satisfy your memory size
>request.
>
>AS you free memory the block of pages is added back into the pool and also
>added to a "free memory" list.
>
>Future allocations will scan the list first for a suitable block and
>neither find one of an exact size or a larger one.
>
>If needed, the larger block is broken up into two smaller blocks to suit a
>given request.
>
>The difference between this and the older 2.4 NP2 allocator is the fact
>that the free page bit map (and associated bit map search) is no longer
>needed. This allocator should be almost as fast as the power of 2 allocator.
>The nature of its operation tends to limit fragmentation but more testing
>is needed.
>
>Note that the slob system in the 2.16 kernel is not optimized, There is a
>speed up patch for the slob allocator that also should be applied.
>I will upgrade the slob code in a later patch.

Any feedback appreciated.

-robin

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2006-04-04 20:01    [W:0.031 / U:0.112 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site