Messages in this thread | | | Date | Fri, 13 Dec 2019 19:43:32 +0100 | From | Peter Zijlstra <> | Subject | Re: [PATCH 4/5] locking/lockdep: Reuse free chain_hlocks entries |
| |
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]); > }
| |