linux-kernel - Re: [PATCH v2 4/6] locking/lockdep: Reuse freed 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: <20200114094656.GA2844@hirez.programming.kicks-ass.net>
Date:   Tue, 14 Jan 2020 10:46:56 +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 v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries

On Mon, Jan 13, 2020 at 11:24:37AM -0500, Waiman Long wrote:
> On 1/13/20 10:58 AM, Peter Zijlstra wrote:

> > That's _two_ allocators :/ And it can trivially fail, even if there's
> > plenty space available.
> >
> > Consider nr_chain_hlocks is exhaused, and @size is empty, but size+1
> > still has blocks.
> >
> > I'm guessing you didn't make it a single allocator because you didn't
> > want to implement block splitting? why?
> >
> In my testing, most of the lock chains tend to be rather short (within
> the 2-8 range). I don't see a lot of free blocks left in the system
> after the test. So I don't see a need to implement block splitting for now.
> 
> If you think this is a feature that needs to be implemented for the
> patch to be complete, I can certainly add patch to do that. My initial
> thought is just to split long blocks in the unsized list for allocation
> request that is no longer than 8 to make thing easier.

>From an engineering POV I'd much prefer a single complete allocator over
two half ones. We can leave block merger out of the initial allocator I
suppose and worry about that if/when fragmentation really shows to be a
problem.

I'm thinking worst-fit might work well for our use-case. Best-fit would
result in a heap of tiny fragments and we don't have really large
allocations, which is the Achilles-heel of worst-fit.

Also, since you put in a minimal allocation size of 2, but did not
mandate size is a multiple of 2, there is a weird corner case of size-1
fragments. The simplest case is to leak those, but put in a counter so
we can see if they're a problem -- there is a fairly trivial way to
recover them without going full merge.

Also, there's a bunch of syzcaller reports of running out of
ENTRIES/CHAIN_HLOCKS, perhaps try some of those workloads to better
stress the allocator?