Harry Gunnarsson wrote: > > I thought that this was the point of the SLAB allocator, i.e. > > avoiding fragmentations with fixed size pre-allocated blocks. > > Well, I'm not entirely certain how the SLAB allocator operates, > since I haven't really looked at its code at all. But I do > know (from testing) that larger blocks can be chosen and sliced > to create smaller blocks. I don't know what its criteria is > for choosing blocks; my *assumption* is that it walks up the > chain (ie. if it needs a 256k block, it'll look in the 256k > free list, and only if there aren't any will it go up to the > 512k free list, and so on until it finds a block it can slice > up and distribute). But I really don't know. Maybe it tries > to do something clever instead.
The algorithm which looks for a 256k free block, then if it doesn't find one, looks for a 512k block to split into two, and so on doubling size until it finds one, is called the Buddy allocator, also called page_alloc.c. When freeing, it does the opposite: when it frees a block and it finds a neighbouring block of the same size, it merges them to make a bigger block, then checks that against it's neighbours, and so on. That algorithm is really quite bad for fragmentation... It's fast though. SLAB only optimises allocation of objects smaller than a page size (4k). It avoids fragmenting large blocks due to tiny objects, but wastes some space in unused parts of pages. Larger allocations use the Buddy allocator (page_alloc.c), or other options which you can configure at kernel compile time. I found page_alloc2.c (on 2.4 kernels) noticably slow and it has some bugs interacting well with the filesystem cache (but they only slow it down, they don't break it), but it's much better at avoiding fragmentation than Buddy. Recently, some changes were made to 2.6 kernels, and some patches not applied, which might make the fragmentation with Buddy less bad on embedded systems: Clustered page reclamation, allocating pages with different lifetimes seperately, and movable pages. The patches were designed for bigger machines, but they should help small ones. -- Jamie _______________________________________________ uClinux-dev mailing list uClinux-dev@uclinux.org http://mailman.uclinux.org/mailman/listinfo/uclinux-dev This message was resent by uclinux-dev@uclinux.org To unsubscribe see: http://mailman.uclinux.org/mailman/options/uclinux-dev
