Messages in this thread Patch in this message |  | | Date | Tue, 4 Feb 2020 14:44:46 +0100 | From | Peter Zijlstra <> | Subject | Re: [PATCH v5 7/7] locking/lockdep: Add a fast path for chain_hlocks allocation |
| |
On Tue, Feb 04, 2020 at 02:18:13PM +0100, Peter Zijlstra wrote: > 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.
Completely untested something like so
---
--- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -2717,7 +2717,7 @@ static inline void init_chain_block(int static inline void add_chain_block(int offset, int size) { int bucket = size_to_bucket(size); - int next = chain_block_buckets[bucket]; + int prev, curr, next = chain_block_buckets[bucket]; if (unlikely(size < 2)) { /* @@ -2731,26 +2731,38 @@ static inline void add_chain_block(int o return; } - init_chain_block(offset, next, bucket, size); - chain_block_buckets[bucket] = offset; - nr_free_chain_hlocks += size; - - if (bucket == 0) + if (!bucket) { nr_large_chain_blocks++; + /* + * Variable sized, sort large to small. + */ + for_each_chain_block(0, prev, curr, next) { + if (size > chain_block_size(curr)) + break; + } + init_chain_block(offset, curr, 0, size); + if (prev < 0) + chain_block_buckets[prev + MAX_CHAIN_BUCKETS] = offset; + else + init_chain_block(prev, offset, MAX_CHAIN_BUCKETS, 0); + } else { + /* + * Fixed size, add to head. + */ + init_chain_block(offset, next, bucket, size); + chain_block_buckets[bucket] = offset; + } + nr_free_chain_hlocks += size; } + /* * When offset < 0, the bucket number is encoded in it. */ -static inline void del_chain_block(int offset, int size, int next) +static inline void del_chain_block(int bucket, int size, int next) { - int bucket = size_to_bucket(size); - nr_free_chain_hlocks -= size; - if (offset < 0) - chain_block_buckets[offset + MAX_CHAIN_BUCKETS] = next; - else - init_chain_block(offset, next, bucket, size); + chain_block_buckets[bucket] = next; if (bucket == 0) nr_large_chain_blocks--; @@ -2774,9 +2786,7 @@ static void init_chain_block_buckets(voi */ static int alloc_chain_hlocks(int req) { - int max_prev, max_curr, max_next, max_size = INT_MIN; - int prev, curr, next, size; - int bucket; + int bucket, curr, size; /* * We rely on the MSB to act as an escape bit to denote freelist @@ -2798,40 +2808,24 @@ static int alloc_chain_hlocks(int req) if (bucket != 0) { curr = chain_block_buckets[bucket]; - if (curr < 0) - goto search; - - del_chain_block(bucket - MAX_CHAIN_BUCKETS, req, - chain_block_next(curr)); - return curr; + if (curr >= 0) { + del_chain_block(bucket, req, chain_block_next(curr)); + return curr; + } } -search: /* - * linear search of the variable sized freelist; look for an exact - * match or the largest block. + * The variable sized freelist is sorted by size; the first entry is + * the largest. Use it if it fits. */ - for_each_chain_block(0, prev, curr, next) { + curr = chain_block_buckets[0]; + if (curr >= 0) { size = chain_block_size(curr); - next = chain_block_next(curr); - - if (size == req) { - del_chain_block(prev, req, next); + if (likely(size > req)) { + del_chain_block(0, size, chain_block_next(curr)); + add_chain_block(curr + req, size - req); return curr; } - - if (size > max_size) { - max_prev = prev; - max_curr = curr; - max_next = next; - max_size = size; - } - } - - if (likely(max_size > req)) { - del_chain_block(max_prev, max_size, max_next); - add_chain_block(max_curr + req, max_size - req); - return max_curr; } /* @@ -2843,8 +2837,7 @@ static int alloc_chain_hlocks(int req) if (curr < 0) continue; - del_chain_block(bucket - MAX_CHAIN_BUCKETS, size, - chain_block_next(curr)); + del_chain_block(bucket, size, chain_block_next(curr)); add_chain_block(curr + req, size - req); return curr; }
|  |