Re: [Chapter One] THP zones: the use cases of policy zones

[Matthew Wilcox <willy@infradead.org>]

On Mon, Mar 04, 2024 at 03:19:42PM +0000, Matthew Wilcox wrote:
> On Thu, Feb 29, 2024 at 11:34:33AM -0700, Yu Zhao wrote:
> > ZONE_MOVABLE becomes the first policy zone, followed by two new policy
> > zones:
> > 1. ZONE_NOSPLIT, which contains pages that are movable (inherited from
> >    ZONE_MOVABLE) and restricted to a minimum order to be
> >    anti-fragmentation. The latter means that they cannot be split down
> >    below that order, while they are free or in use.
> > 2. ZONE_NOMERGE, which contains pages that are movable and restricted
> >    to an exact order. The latter means that not only is split
> >    prohibited (inherited from ZONE_NOSPLIT) but also merge (see the
> >    reason in Chapter Three), while they are free or in use.
> 
> These two zones end up solving a problem for memdescs.  So I'm in favour!
> I added Option 5 to https://kernelnewbies.org/MatthewWilcox/BuddyAllocator

I realised that we don't even need a doubly-linked-list for ZONE_NOMERGE
(would ZONE_FIXEDSIZE be a better name?)  We only need a oubly linked
list to make removal from the middle of the list an O(1) operation, and
we only remove from the middle of a list when merging.  So we can simply
keep a stack of free "pages" and we have 60 bits to point to the next
memdesc, so we can easily cover all memory that can exist in a 64-bit
machine in ZONE_NOMERGE.  ZONE_NOSPLIT would be limited to the first 1PB
of memory (assuming it has a minimum size of 2MB -- with 29 bits to
refer to each of next & prev, 29 + 21 = 50 bits of address space).