Re: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries

[Peter Zijlstra <peterz@infradead.org>]

On Mon, Jan 13, 2020 at 11:24:37AM -0500, Waiman Long wrote:
> On 1/13/20 10:58 AM, Peter Zijlstra wrote:

> > That's _two_ allocators :/ And it can trivially fail, even if there's
> > plenty space available.
> >
> > Consider nr_chain_hlocks is exhaused, and @size is empty, but size+1
> > still has blocks.
> >
> > I'm guessing you didn't make it a single allocator because you didn't
> > want to implement block splitting? why?
> >
> In my testing, most of the lock chains tend to be rather short (within
> the 2-8 range). I don't see a lot of free blocks left in the system
> after the test. So I don't see a need to implement block splitting for now.
> 
> If you think this is a feature that needs to be implemented for the
> patch to be complete, I can certainly add patch to do that. My initial
> thought is just to split long blocks in the unsized list for allocation
> request that is no longer than 8 to make thing easier.

From an engineering POV I'd much prefer a single complete allocator over
two half ones. We can leave block merger out of the initial allocator I
suppose and worry about that if/when fragmentation really shows to be a
problem.

I'm thinking worst-fit might work well for our use-case. Best-fit would
result in a heap of tiny fragments and we don't have really large
allocations, which is the Achilles-heel of worst-fit.

Also, since you put in a minimal allocation size of 2, but did not
mandate size is a multiple of 2, there is a weird corner case of size-1
fragments. The simplest case is to leak those, but put in a counter so
we can see if they're a problem -- there is a fairly trivial way to
recover them without going full merge.

Also, there's a bunch of syzcaller reports of running out of
ENTRIES/CHAIN_HLOCKS, perhaps try some of those workloads to better
stress the allocator?