On Mon, Sep 27, 2021 at 09:07:21PM +0200, Vlastimil Babka wrote: > On 9/27/2021 8:09 PM, Kent Overstreet wrote: > > On Mon, Sep 27, 2021 at 07:05:26PM +0100, Matthew Wilcox wrote: > >> On Mon, Sep 27, 2021 at 07:48:15PM +0200, Vlastimil Babka wrote: > >>> Won't be easy to cram all that into two unsigned long's, or even a single > >>> one. We should avoid storing anything in the free page itself. Allocating > >>> some external structures to track free pages is going to have funny > >>> bootstrap problems. Probably a major redesign would be needed... > >> > >> Wait, why do we want to avoid using the memory that we're allocating? > > > > The issue is where to stick the state for free pages. If that doesn't fit in two > > ulongs, then we'd need a separate allocation, which means slab needs to be up > > and running before free pages are initialized. > > So that's what I meant by the funny bootstrap problems - slab allocates pages > from the buddy allocator. And well, not just bootstrap, imagine free memory > becomes low, we need to reclaim pages, and in order to turn full pages to free > buddy pages we need to allocate these slab structures, and the slab is full too > and needs to allocate more backing pages... > > By "major redesign" I meant e.g. something along - bitmaps of free pages per > each order? (instead of the free lists) Hm but I guess no, the worst case times > searching for free pages would just suck... We can have arrays of pointers to free pages - then within struct page we'd keep the index of that page in the freelist array. To take a page off the middle of the freelist we'd just swap it with the one at the end. And instead of using a literal array, we'd want to use a simple radix tree.
