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]

Date:   Tue, 14 Jan 2020 14:16:58 -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 v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries

On 1/14/20 4:46 AM, Peter Zijlstra wrote:
> 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.
I am going to add a patch to split chain block as a last resort in case
we run out of the main buffer.
>
> 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.

There is no size-1 fragment. Are you referring to the those blocks with
a size of 2, but with only one entry used? There are some wasted space
there. I can add a counter to track that.

Cheers,
Longman

>
> 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?
>