On Tue, Jan 15, 2002 at 05:42:29PM -0800, Amit Purohit wrote: > Is there any documentation available on the zoned > buddy allocator, which could cover the core technical > details and explanations regarding the data structures > used. Wilson has a survey paper on allocators in general, which should give a good idea of how it operates in general. Buddy allocators are quite common in general. page_alloc.c uses segregated fit, FIFO ordering and the buddy bitmap technique for coalescing. Despite mainline's "You aren't supposed to understand this", it's not difficult to understand. Segregated fit means that the free blocks of memory of different sizes are kept in different lists. To get one, you need only find a list with a blocksize large enough and get the first block of memory in the list. It has a bitmap for each block size (which are powers of two). These bitmaps are used only to discover when blocks of memory touch so that they can be treated like a larger block of memory. Basically when you free a page, you clear its bit. If that and the page next to it are free, the bit in the next higher bitmap is cleared. A similar process happens in reverse for when you allocate pages. When you split or merge in the bitmap you have to do the same splitting and merging in the lists, but you already know where to look, thanks to the bitmap. velco, riel, any corrections or clarifications to make there? Cheers, Bill -- Kernelnewbies: Help each other learn about the Linux kernel. Archive: http://mail.nl.linux.org/kernelnewbies/ IRC Channel: irc.openprojects.net / #kernelnewbies Web Page: http://www.kernelnewbies.org/
