| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <20200204134446.GQ14946@hirez.programming.kicks-ass.net>
Date: Tue, 4 Feb 2020 14:44:46 +0100
From: Peter Zijlstra <peterz@...radead.org>
To: Waiman Long <longman@...hat.com>
Cc: Ingo Molnar <mingo@...hat.com>, Will Deacon <will.deacon@....com>,
linux-kernel@...r.kernel.org, Bart Van Assche <bvanassche@....org>
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;
}
Powered by blists - more mailing lists