Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
Date:   Mon, 27 Sep 2021 16:14:06 -0400
From:   Kent Overstreet <kent.overstreet@gmail.com>
To:     Vlastimil Babka <vbabka@suse.cz>
Cc:     Matthew Wilcox <willy@infradead.org>,
        linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org,
        linux-mm@kvack.org, Johannes Weiner <hannes@cmpxchg.org>,
        Linus Torvalds <torvalds@linux-foundation.org>,
        Andrew Morton <akpm@linux-foundation.org>,
        "Darrick J. Wong" <djwong@kernel.org>,
        Christoph Hellwig <hch@infradead.org>,
        David Howells <dhowells@redhat.com>
Subject: Re: Struct page proposal
Message-ID: <YVImDtfdgo+RXBe+@moria.home.lan>
References: <YUvWm6G16+ib+Wnb@moria.home.lan>
 <bc22b4d0-ba63-4559-88d9-a510da233cad@suse.cz>
 <YVIH5j5xkPafvNds@casper.infradead.org>
 <YVII7eM7P42riwoI@moria.home.lan>
 <751358b2-aec2-43a3-cbbe-1f8c4469b6d3@suse.cz>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <751358b2-aec2-43a3-cbbe-1f8c4469b6d3@suse.cz>
Precedence: bulk

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.