lkml.org 
[lkml]   [2018]   [Dec]   [3]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [PATCH 22/27] locking/lockdep: Reuse list entries that are no longer in use
From
Date
On Sat, 2018-12-01 at 21:24 +0100, Peter Zijlstra wrote:
> On Thu, Nov 29, 2018 at 08:48:50AM -0800, Bart Van Assche wrote:
> > On Thu, 2018-11-29 at 13:01 +0100, Peter Zijlstra wrote:
> > > On Thu, Nov 29, 2018 at 11:49:02AM +0100, Peter Zijlstra wrote:
> > > > On Wed, Nov 28, 2018 at 03:43:20PM -0800, Bart Van Assche wrote:
> > > > > /*
> > > > > * Remove all dependencies this lock is
> > > > > * involved in:
> > > > > */
> > > > > + list_for_each_entry_safe(entry, tmp, &all_list_entries, alloc_entry) {
> > > > > if (entry->class != class && entry->links_to != class)
> > > > > continue;
> > > > > links_to = entry->links_to;
> > > > > WARN_ON_ONCE(entry->class == links_to);
> > > > > list_del_rcu(&entry->lock_order_entry);
> > > > > + list_move(&entry->alloc_entry, &free_list_entries);
> > > > > entry->class = NULL;
> > > > > entry->links_to = NULL;
> > > > > check_free_class(zapped_classes, class);
> > > >
> > > > Hurm.. I'm confused here.
> > > >
> > > > The reason you cannot re-use lock_order_entry for the free list is
> > > > because list_del_rcu(), right? But if so, then what ensures the
> > > > list_entry is not re-used before it's grace-period?
> > >
> > > Also; if you have to grow lock_list by 16 bytes just to be able to free
> > > it, a bitmap allocator is much cheaper, space wise.
> > >
> > > Some people seem to really care about the static image size, and
> > > lockdep's .data section does matter to them.
> >
> > How about addressing this by moving removed list entries to a "zapped_entries"
> > list and only moving list entries from the zapped_entries list to the
> > free_list_entries list after an RCU grace period? I'm not sure that it is
> > possible to implement that approach without introducing a new list_head in
> > struct lock_list.
>
> 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.

Thanks,

Bart.

\
 
 \ /
  Last update: 2018-12-03 17:41    [W:0.127 / U:0.040 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site