William Lee Irwin III wrote: > > 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. Minor nit: When you free a page you invert the bit that corresponds to the page and its buddy; you also invert the same bit when allocating. That is, each pair of pages is represented by a bit, each pair-of- pairs is represented by a bit, etc. If a bit is 1, it means "This block is fragmented", and if it's 0 it means "This block is unfragmented - either both halves are in use or both halves are free." expand() &c rely on the fact that they know which operation (alloc or free) they're performing in order to coalesce buddy blocks based on the fragmentation bitmap. If you free a page and the page+buddy bit becomes 0, you know the 2-page block is free, and can potentially be coalesced with its 2-page buddy (if the buddy is also free, which you find out simply by flipping the 4-page-block fragmentation bit and checking if it's 0); if the bit becomes 1 on a free, you know not to coalesce the block. Cheers, -- "I should like to close this book by sticking out any part of my neck which is not yet exposed, and making a few predictions about how the problem of quantum gravity will in the end be solved." --- Physicist Lee Smolin, "Three Roads to Quantum Gravity" -- 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/
