| 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: <d639c80c-d60f-d5ac-8559-7942798dc92e@redhat.com>
Date: Fri, 13 Dec 2019 10:02:26 -0500
From: Waiman Long <longman@...hat.com>
To: Peter Zijlstra <peterz@...radead.org>
Cc: Ingo Molnar <mingo@...hat.com>, Will Deacon <will.deacon@....com>,
linux-kernel@...r.kernel.org, Bart Van Assche <bvanassche@....org>
Subject: Re: [PATCH 4/5] locking/lockdep: Reuse free chain_hlocks entries
On 12/13/19 5:25 AM, Peter Zijlstra wrote:
> On Thu, Dec 12, 2019 at 05:35:24PM -0500, Waiman Long wrote:
>
>> diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
>> index 4c23ab7d27c2..999cd714e0d1 100644
>> --- a/kernel/locking/lockdep_internals.h
>> +++ b/kernel/locking/lockdep_internals.h
>> @@ -107,8 +107,15 @@ static const unsigned long LOCKF_USED_IN_IRQ_READ =
>> #endif
>>
>> #define MAX_LOCKDEP_CHAINS (1UL << MAX_LOCKDEP_CHAINS_BITS)
>> -
>> #define MAX_LOCKDEP_CHAIN_HLOCKS (MAX_LOCKDEP_CHAINS*5)
>> +#define MAX_CHAIN_HLOCKS_BLOCKS 1024
>> +#define CHAIN_HLOCKS_HASH 8
>> +
>> +struct chain_hlocks_block {
>> + unsigned int depth: 8,
>> + base :24;
>> + struct chain_hlocks_block *next;
>> +};
>>
>> extern struct list_head all_lock_classes;
>> extern struct lock_chain lock_chains[];
> This doesn't need to be in the header, there are no users outside of the
> stuff you wrote below.
>
That is true.
>> +#ifdef CONFIG_PROVE_LOCKING
>> +static struct chain_hlocks_block chain_hlocks_blocks[MAX_CHAIN_HLOCKS_BLOCKS];
>> +static struct chain_hlocks_block *chain_hlocks_block_hash[CHAIN_HLOCKS_HASH];
>> +static struct chain_hlocks_block *free_chain_hlocks_blocks;
>> +
>> +/*
>> + * Graph lock must be held before calling the chain_hlocks_block functions.
>> + * Chain hlocks of depth 1-(CHAIN_HLOCKS_HASH-1) is mapped directly to
>> + * chain_hlocks_block_hash[1-(CHAIN_HLOCKS_HASH-1)]. All other sizes
>> + * are mapped to chain_hlocks_block_hash[0].
>> + */
>> +static inline struct chain_hlocks_block *alloc_chain_hlocks_block(void)
>> +{
>> + struct chain_hlocks_block *block = free_chain_hlocks_blocks;
>> +
>> + WARN_ONCE(!debug_locks_silent && !block,
>> + "Running out of chain_hlocks_block\n");
>> + free_chain_hlocks_blocks = block ? block->next : NULL;
>> + return block;
>> +}
>> +
>> +static inline void free_chain_hlocks_block(struct chain_hlocks_block *block)
>> +{
>> + block->next = free_chain_hlocks_blocks;
>> + free_chain_hlocks_blocks = block;
>> +}
>> +
>> +static inline void push_chain_hlocks_block(struct chain_hlocks_block *block)
>> +{
>> + int hash, depth = block->depth;
>> +
>> + hash = (depth >= CHAIN_HLOCKS_HASH) ? 0 : depth;
>> + block->next = chain_hlocks_block_hash[hash];
>> + chain_hlocks_block_hash[hash] = block;
>> + nr_free_chain_hlocks += depth;
>> +}
> I would argue this is not a hash, these are buckets. You're doing
> regular size buckets.
I think I used the wrong terminology here. Bucket is a better description.
>
>> +static inline struct chain_hlocks_block *pop_chain_hlocks_block(int depth)
>> +{
>> + struct chain_hlocks_block *curr, **pprev;
>> +
>> + if (!nr_free_chain_hlocks)
>> + return NULL;
>> +
>> + if (depth < CHAIN_HLOCKS_HASH) {
>> + curr = chain_hlocks_block_hash[depth];
>> + if (curr) {
>> + chain_hlocks_block_hash[depth] = curr->next;
>> + nr_free_chain_hlocks -= depth;
>> + }
>> + return curr;
>> + }
>> +
>> + /*
>> + * For depth >= CHAIN_HLOCKS_HASH, it is not really a pop operation.
>> + * Instead, the first entry with the right size is returned.
>> + */
>> + curr = chain_hlocks_block_hash[0];
>> + pprev = chain_hlocks_block_hash;
>> +
>> + while (curr) {
>> + if (curr->depth == depth)
>> + break;
>> + pprev = &(curr->next);
>> + curr = curr->next;
>> + }
>> +
>> + if (curr) {
>> + *pprev = curr->next;
>> + nr_free_chain_hlocks -= depth;
>> + }
>> + return curr;
>> +}
>> +#else
>> +static inline void free_chain_hlocks_block(struct chain_hlocks_block *block) { }
>> +static inline struct chain_hlocks_block *pop_chain_hlocks_block(int depth)
>> +{
>> + return NULL;
>> +}
>> +#endif /* CONFIG_PROVE_LOCKING */
> You've made a bit of a mess of things though. Why is that push/pop crud
> exposed? Why didn't you build a self contained allocator?
>
> All you really want is:
>
> u16 *alloc_chain(int size);
> void free_chain(int size, u16 *chain);
>
>
> 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 */
> };
>
>
> 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)
> {
> 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);
>
> if (!b) {
> // leak stuff;
> return;
> }
>
> b->size = size;
> b->base = chain - chain_hlocks;
>
> push_bucket(&free_list[bucket], b);
> }
>
> void init_blocks(void)
> {
> int i;
>
> for (i = 0; i < MAX_BLOCKS; i++)
> free_block(chain_blocks[i]);
> }
>
Thanks for the suggestion. I will incorporate your idea in the next
version of the patch.
Cheers,
Longman
Powered by blists - more mailing lists