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

[Bart Van Assche]

On Thu, 2018-11-29 at 13:01 +-0100, Peter Zijlstra wrote:
+AD4 On Thu, Nov 29, 2018 at 11:49:02AM +-0100, Peter Zijlstra wrote:
+AD4 +AD4 On Wed, Nov 28, 2018 at 03:43:20PM -0800, Bart Van Assche wrote:
+AD4 +AD4 +AD4  	/+ACo
+AD4 +AD4 +AD4  	 +ACo Remove all dependencies this lock is
+AD4 +AD4 +AD4  	 +ACo involved in:
+AD4 +AD4 +AD4  	 +ACo-/
+AD4 +AD4 +AD4 +-	list+AF8-for+AF8-each+AF8-entry+AF8-safe(entry, tmp, +ACY-all+AF8-list+AF8-entries, alloc+AF8-entry) +AHs
+AD4 +AD4 +AD4  		if (entry-+AD4-class +ACEAPQ class +ACYAJg entry-+AD4-links+AF8-to +ACEAPQ class)
+AD4 +AD4 +AD4  			continue+ADs
+AD4 +AD4 +AD4  		links+AF8-to +AD0 entry-+AD4-links+AF8-to+ADs
+AD4 +AD4 +AD4  		WARN+AF8-ON+AF8-ONCE(entry-+AD4-class +AD0APQ links+AF8-to)+ADs
+AD4 +AD4 +AD4  		list+AF8-del+AF8-rcu(+ACY-entry-+AD4-lock+AF8-order+AF8-entry)+ADs
+AD4 +AD4 +AD4 +-		list+AF8-move(+ACY-entry-+AD4-alloc+AF8-entry, +ACY-free+AF8-list+AF8-entries)+ADs
+AD4 +AD4 +AD4  		entry-+AD4-class +AD0 NULL+ADs
+AD4 +AD4 +AD4  		entry-+AD4-links+AF8-to +AD0 NULL+ADs
+AD4 +AD4 +AD4  		check+AF8-free+AF8-class(zapped+AF8-classes, class)+ADs
+AD4 +AD4 
+AD4 +AD4 Hurm.. I'm confused here.
+AD4 +AD4 
+AD4 +AD4 The reason you cannot re-use lock+AF8-order+AF8-entry for the free list is
+AD4 +AD4 because list+AF8-del+AF8-rcu(), right? But if so, then what ensures the
+AD4 +AD4 list+AF8-entry is not re-used before it's grace-period?
+AD4 
+AD4 Also+ADs if you have to grow lock+AF8-list by 16 bytes just to be able to free
+AD4 it, a bitmap allocator is much cheaper, space wise.
+AD4 
+AD4 Some people seem to really care about the static image size, and
+AD4 lockdep's .data section does matter to them.

How about addressing this by moving removed list entries to a +ACI-zapped+AF8-entries+ACI
list and only moving list entries from the zapped+AF8-entries list to the
free+AF8-list+AF8-entries list after an RCU grace period? I'm not sure that it is
possible to implement that approach without introducing a new list+AF8-head in
struct lock+AF8-list.

Thanks,

Bart.