linux-kernel - Re: [PATCH v5 7/7] locking/lockdep: Add a fast path for chain

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20200204131813.GQ14914@hirez.programming.kicks-ass.net>
Date:   Tue, 4 Feb 2020 14:18:13 +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 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.