Re: [PATCH 4/5] locking/lockdep: Reuse free chain_hlocks entries

[Peter Zijlstra <peterz@infradead.org>]

modified version that assumes MAX_BLOCKS <= 15bit, if it is more, you
need the 2 entry version of it, but I suppose you get the idea.

On Fri, Dec 13, 2019 at 11:25:25AM +0100, Peter Zijlstra wrote:

> An implementation would be something along these lines (completely
> untested, fresh from the keyboard):
> 
> struct chain_block {
> 	int size;
> 	int base;
> 	struct chain_block *next;
> };
> 
> struct chain_block chain_blocks[MAX_BLOCKS];
> struct chain_block *free_blocks;

- struct chain_block init_block = {
- 	.size = MAX_LOCKDEP_CHAIN_HLOCKS,
- 	.base = 0,
- 	.next = NULL,
- };

- struct chain_block *free_list[MAX_BUCKETS] = {
- 	&init_block, /* 0 */
- };

+ struct chain_block *free_list;

> void free_block(struct chain_block *b)
> {
> 	b->next = free_blocks;
> 	free_blocks = b;
> }
> 
> struct chain_block *alloc_block(void)
> {
> 	struct chain_block *block = free_blocks;
> 	free_blocks = block->next;
> 	return block;
> }
> 
> struct chain_block *pop_block(struct chain_block **bp)
> {
> 	struct chain_block *b = *bp;
> 	if (!b)
> 		return NULL;
> 	*bp = b->next;
> }
> 
> void push_block(struct chain_block **bp, struct chain_block *b)
> {
	u16 idx = (b - chain_blocks) | BIT(15);

+	chain_hlock[b->base] = idx;
+	chain_block[b->base + b->size - 1] = idx;

> 	b->next = *bp;
> 	*bp = b;
> }
> 
> /* could contemplate ilog2() buckets */
> int size2bucket(int size)
> {
> 	return size >= MAX_BUCKET ? 0 : size;
> }
> 
> /* bucket[0] is mixed size */
> struct chain_block *pop_block_0(struct chain_block **bp, int size)
> {
> 	struct chain_block **p = bp, *b = *bp;
> 	if (!b)
> 		return NULL;
> 
> 	p = bp;
> 	while (b && b->size < size) {
> 		p = &b->next;
> 		b = b->next;
> 	}
> 	if (!b)
> 		return NULL;
> 
> 	*p = b->next;
> 	return b;
> }
> 
> u16 *alloc_chain(int size)
> {
> 	int i, bucket = size2bucket(size);
> 	struct chain_block *b;
> 	u16 *chain;
> 
> 	if (!bucket) {
> 		b = pop_block_0(&free_list[0], size);
> 		if (b)
> 			goto got_block;
> 	} else {
> 		b = pop_block(&free_list[bucket]);
> 		if (b)
> 			goto got_block;
> 
> 		/* pop a large block, hope the fragment is still useful */
> 		b = pop_block_0(&free_list[0], size);
> 		if (b)
> 			goto got_block;
> 
> 		for (i = MAX_BUCKETS-1; i > bucket; i--)
> 			b = pop_block(&free_list[bucket]);
> 			if (b)
> 				goto got_block;
> 		}
> 	}
> 	return NULL;
> 
> got_block:
> 
> 	chain = chain_hlocks + b->base;
> 	b->base += size;
> 	b->size -= size;
> 
> 	if (b->size) {
> 		/* return the fragment */
> 		bucket = size2bucket(b->size);
> 		push_block(&free_list[bucket], b);
> 	} else {
> 		free_block(b);
> 	}
> 
> 	return chain;
> }
> 
> void free_chain(int size, u16 *chain)
> {
- 	struct chain_block *b = alloc_block();
- 	int bucket = size2bucket(size);

+	struct chain_block *b = NULL, *p = NULL, *n = NULL;
+	int base = chain - chain_hlocks;
+	u16 p_idx, n_idx;
+	int bucket;

	p_idx = chain_hlocks[base - 1];
	n_idx = chain_hlocks[base + size];

	if (p_idx & BIT(15)) {
		p = chain_blocks[p_idx & ~BIT(15)];
		bucket = size2bucket(p->size);

		// find and remove @p from @bucket

		p->size += size; // merge with prev
		b = p;
	}

	if (n_idx & BIT(15)) {
		n = chain_blocks[n_idx & ~BIT(15)];
		bucket = size2bucket(n->size);

		// find and remove @n from @bucket

		if (p) {
			p->size += n->size;
			free_block(n);
			n = NULL;
		} else {
			n->base -= size;
			b = n;
		}
	}
		
	if (!b) {
		b = alloc_bucket();
		if (!b) {
			// leak stuff
			return;
		}

		b->size = size;
		b->base = base;
	}
	
- 	if (!b) {
- 		// leak stuff;
- 		return;
- 	}
- 
- 	b->size = size;
- 	b->base = chain - chain_hlocks;

	bucket = size2bucket(b->size);

> 	push_bucket(&free_list[bucket], b);
> }
> 
> void init_blocks(void)
> {
> 	int i;

	chain_blocks[0].size = MAX_LOCKDEP_CHAIN_HLOCKS;
	chain_blocks[0].base = 0;
	chain_blocks[0].next = NULL;

	free_list[0] = &chain_blocks[0];

> 	for (i = 1; i < MAX_BLOCKS; i++)
> 		free_block(chain_blocks[i]);
> }