Re: [PATCH v5 7/7] locking/lockdep: Add a fast path for chain_hlocks allocation

[Peter Zijlstra <peterz@infradead.org>]

On Mon, Feb 03, 2020 at 11:41:47AM -0500, Waiman Long wrote:

> @@ -2809,6 +2813,18 @@ static int alloc_chain_hlocks(int req)
>  			return curr;
>  		}
>  
> +		/*
> +		 * Fast path: splitting out a sub-block at the end of the
> +		 * primordial chain block.
> +		 */
> +		if (likely((size > MAX_LOCK_DEPTH) &&
> +			   (size - req > MAX_CHAIN_BUCKETS))) {
> +			size -= req;
> +			nr_free_chain_hlocks -= req;
> +			init_chain_block_size(curr, size);
> +			return curr + size;
> +		}
> +
>  		if (size > max_size) {
>  			max_prev = prev;
>  			max_curr = curr;

A less horrible hack might be to keep the freelist sorted on size (large
-> small)

That moves the linear-search from alloc_chain_hlocks() into
add_chain_block().  But the thing is that it would amortize to O(1)
because this initial chunk is pretty much 'always' the largest.

Only once we've exhausted the initial block will we hit that search, but
then the hope is that we mostly live off of the buckets, not the
variable freelist.