lkml.org 
[lkml]   [2019]   [Dec]   [13]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [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]);
> }

\
 
 \ /
  Last update: 2019-12-13 19:44    [W:0.068 / U:0.140 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site