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

[Waiman Long]

On 1/15/20 5:44 AM, Peter Zijlstra wrote:
> On Tue, Jan 14, 2020 at 02:16:58PM -0500, Waiman Long wrote:
>> On 1/14/20 4:46 AM, Peter Zijlstra wrote:
>>> 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.
>> I am going to add a patch to split chain block as a last resort in case
>> we run out of the main buffer.
> It will be the common path; you'll start with a single huge fragment.
>
> Remember, 1 allocator is better than 2.

One reason why I keep the array allocation code is because it is simple
and fast. Using a free block in the bucket will be a bit slower. Still
we are just dealing with the first block in the list as long as the size
isn't bigger than MAX_CHAIN_BUCKETS. Now if we need to deal with block
splitting (or even merging), it will be even more slow. Given the fact
that we are holding the graph lock in doing all these. It could have a
visible impact on performance.

That is the primary reason why I intend to allow block splitting only as
the last resort when the chain_hlocks array is running out.

>>> 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.
>> There is no size-1 fragment. Are you referring to the those blocks with
>> a size of 2, but with only one entry used? There are some wasted space
>> there. I can add a counter to track that.
> There will be; imagine you have a size-6 fragment and request a size-5,
> then we'll have to split off one. But one is too short to encode on the
> free lists.
>
> Suppose you tag them with -2, then on free of the size-5, we can check
> if curr+size+1 is -2 and reunite.
>
> First-fit or best-fit would result in lots of that, hence my suggestion
> to use worst-fit if you can't find an exact match.
>
What I am thinking is to allow block splitting only if it has a size
that is at least 2 larger than the desire value. In that way, we will
not produce a fragment that is less than 2 in size. The down side is
that we have fewer viable candidates for splitting.

Cheers,
Longman