linux-kernel - Re: [PATCH 22/27] locking/lockdep: Reuse list entries that are no longer in use

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: <20181204081436.GL11614@hirez.programming.kicks-ass.net>
Date:   Tue, 4 Dec 2018 09:14:36 +0100
From:   Peter Zijlstra <peterz@...radead.org>
To:     Bart Van Assche <bvanassche@....org>
Cc:     mingo@...hat.com, tj@...nel.org, johannes.berg@...el.com,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH 22/27] locking/lockdep: Reuse list entries that are no
 longer in use

On Mon, Dec 03, 2018 at 10:16:59AM -0800, Bart Van Assche wrote:
> On Mon, 2018-12-03 at 18:32 +0100, Peter Zijlstra wrote:
> > On Mon, Dec 03, 2018 at 08:40:48AM -0800, Bart Van Assche wrote:
> > 
> > > > I think we can do this with a free bitmap and an array of 2 pending
> > > > bitmaps and an index. Add newly freed entries to the pending bitmap
> > > > indicated by the current index, when complete flip the index -- such
> > > > that further new bits go to the other pending bitmap -- and call_rcu().
> > > > 
> > > > Then, on the call_rcu() callback, ie. after a GP has happened, OR our
> > > > pending bitmap into the free bitmap, and when the other pending bitmap
> > > > isn't empty, flip the index again and start it all again.
> > > > 
> > > > This ensures there is at least one full GP between setting a bit and it
> > > > landing in the free mask.
> > > 
> > > Hi Peter,
> > > 
> > > How about the following alternative which requires only two bitmaps instead
> > > of three:
> > > - Maintain two bitmaps, one for the free entries and one for the entries
> > >   that are being freed.
> > > - Protect all accesses to both bitmaps with the graph lock.
> > > - zap_class() sets a bit in the "being freed" bitmap for the entries that
> > >   should be freed after a GP.
> > > - Instead of making free_zapped_classes() wait for a grace period by calling
> > >   synchronize_sched(), use call_rcu() and do the freeing work from inside the
> > >   RCU callback.
> > > - From inside the RCU callback, set a bit in the "free" bitmap for all entries
> > >   that have a bit set in the "being freed" bitmap and clears the "being freed"
> > >   bitmap.
> > 
> > What happens when another unreg happens while the rcu_call thing is
> > still pending?
> 
> A new flag will have to keep track of whether or not an RCU callback has
> already been scheduled via rcu_call() but not yet executed to avoid double
> RCU call complaints.

That's not the only problem there. You either then have to synchronously
wait for that flag / rcu_call to complete, or, if you modify the bitmap,
ensure it re-queues itself for another GP before committing, which is
starvation prone.

> In other code a possible alternative would be to
> allocate the RCU head data structure dynamically. However, I don't think
> that alternative is appropriate inside the lockdep code - I don't want to
> introduce a circular dependency between the lockdep code and the memory
> allocator.

Yes, that's a trainwreck waiting to happen ;-)