On Thu, Mar 22, 2018 at 08:17:19AM -0700, Matthew Wilcox wrote: > 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. Thanks for the pointer, will take a look later. Currently I'm focusing on finding real workloads that have zone lock contention issue.
