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

[Peter Zijlstra <peterz@infradead.org>]

On Thu, Feb 06, 2020 at 10:24:08AM -0500, Waiman Long wrote:
> +static int alloc_chain_hlocks(int req)
> +{
> +	int bucket, curr, size;
> +
> +	/*
> +	 * We rely on the MSB to act as an escape bit to denote freelist
> +	 * pointers. Make sure this bit isn't set in 'normal' class_idx usage.
> +	 */
> +	BUILD_BUG_ON((MAX_LOCKDEP_KEYS-1) & CHAIN_BLK_FLAG);
> +
> +	init_data_structures_once();
> +
> +	if (nr_free_chain_hlocks < req)
> +		return -1;
> +
> +	/*
> +	 * We require a minimum of 2 (u16) entries to encode a freelist
> +	 * 'pointer'.
> +	 */
> +	req = max(req, 2);
> +	bucket = size_to_bucket(req);
> +	curr = chain_block_buckets[bucket];
> +
> +	if (bucket && (curr >= 0)) {
> +		del_chain_block(bucket, req, chain_block_next(curr));
> +		return curr;
> +	} else if (bucket) {
> +		/* Try bucket 0 */
> +		curr = chain_block_buckets[0];
> +	}

	if (bucket) {
		if (curr >= 0) {
			del_chain_block(bucket, req, chain_block_next(curr));
			return curr;
		}
		/* Try bucket 0 */
		curr = chain_block_bucket[0];
	}

reads much easier IMO.

> +	/*
> +	 * The variable sized freelist is sorted by size; the first entry is
> +	 * the largest. Use it if it fits.
> +	 */
> +	if (curr >= 0) {
> +		size = chain_block_size(curr);
> +		if (likely(size >= req)) {
> +			del_chain_block(0, size, chain_block_next(curr));
> +			add_chain_block(curr + req, size - req);
> +			return curr;
> +		}
> +	}
> +
> +	/*
> +	 * Last resort, split a block in a larger sized bucket.
> +	 */
> +	for (size = MAX_CHAIN_BUCKETS; size > req; size--) {
> +		bucket = size_to_bucket(size);
> +		curr = chain_block_buckets[bucket];
> +		if (curr < 0)
> +			continue;
> +
> +		del_chain_block(bucket, size, chain_block_next(curr));
> +		add_chain_block(curr + req, size - req);
> +		return curr;
> +	}
> +
> +	return -1;
> +}