Re: [PATCH v4 2/3] mm/free_pcppages_bulk: do not hold lock when picking pages to free

[Matthew Wilcox]

On Tue, Mar 13, 2018 at 11:34:53AM +0800, Aaron Lu wrote:
> I wish there is a data structure that has the flexibility of list while
> at the same time we can locate the Nth element in the list without the
> need to iterate. That's what I'm looking for when developing clustered
> allocation for order 0 pages. In the end, I had to use another place to
> record where the Nth element is. I hope to send out v2 of that RFC
> series soon but I'm still collecting data for it. I would appreciate if
> people could take a look then :-)

Sorry, I missed this.  There is such a data structure -- the IDR, or
possibly a bare radix tree, or we can build a better data structure on
top of the radix tree (I talked about one called the XQueue a while ago).

The IDR will automatically grow to whatever needed size, it stores
pointers, you can find out quickly where the last allocated index is,
you can remove from the middle of the array.  Disadvantage is that it
requires memory allocation to store the array of pointers, *but* it
can always hold at least one entry.  So if you have no memory, you can
always return the one element in your IDR to the free pool and allocate
from that page.