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

[Bart Van Assche <bvanassche@acm.org>]

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.