Re: [PATCH v6 00/16] locking/lockdep: Add support for dynamic keys

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

On 1/18/19 1:48 AM, Peter Zijlstra wrote:
> On Mon, Jan 14, 2019 at 08:52:33AM -0800, Bart Van Assche wrote:
>> On Mon, 2019-01-14 at 13:52 +0100, Peter Zijlstra wrote:
>>> On Fri, Jan 11, 2019 at 09:01:41AM -0800, Bart Van Assche wrote:
>>>> The list_del_rcu() call must only happen once.
>>>
>>> Yes; obviously. But if we need to check all @pf's, that means the entry
>>> is still reachable after a single reset_lock()/free_key_range(), which
>>> is a bug.
>>>
>>>> I ran into complaints reporting that
>>>> the list_del_rcu() call triggered list corruption. This change made these complaints
>>>> disappear.
>>>
>>> I'm saying this solution buggy, because that means the entry is still
>>> reachable after we do call_rcu() (which is a straight up UAF).
>>>
>>> Also put it differently, what guarantees checking those two @pf's is
>>> sufficient. Suppose your earlier @pf already did the RCU callback and
>>> freed stuff while the second is in progress. Then you're poking into
>>> dead space.
>>
>> zap_class() only examines elements of the list_entries[] array for which the
>> corresponding bit in list_entries_in_use has been set. The RCU callback clears
>> the bits in the list_entries_in_use that correspond to elements that have been
>> freed. The graph lock serializes zap_class() calls and the code inside the
>> RCU callback. So it's not clear to me why you are claiming that zap_class()
>> would trigger a use-after-free?
> 
> The scenario is like:
> 
> 
> CPU0					CPU1					CPU2
> 
> lockdep_reset_lock_reg()
>    pf = get_pending_free_lock() // pf[0]
>    __lockdep_reset_lock(pf)
>      zap_class()
>    schedule_free_zapped_classes(pf)
>      call_rcu()
> 
> 
>    // here is wbere the objects 'freed' in zap_class()
>    // can still be used through references obtained
>    // __before__ we did call_rcu().
> 
> 
> 					lockdep_reset_lock_reg()
> 					  pf = get_pending_free_lock() // pf[1]
> 					  __lockdep_reset_lock(pf)
> 					    zap_class()
> 					      list_entry_being_freed()
> 						// checks: pf[0]
> 
> 						// this is a problem, it
> 						// should _NEVER_ match
> 						// anything from pf[0]
> 
> 						// those entries should
> 						// be unreachable,
> 						// otherwise:
> 
> 
> 										rcu_read_lock()
> 										entry = rcu_dereference()
> 
> <rcu-callback>
>    free_zapped_classes()
> 
> 										entry->class // UAF, just freed by rcu-callback
> 
> 										rcu_read_unlock()
> 
> 
> 
> 
> Now, arguably, I'm having a really hard time actually finding the RCU user of
> lock_list::entry, the comment in add_lock_to_list() seems to mention
> look_up_lock_class(), but the only RCU usage there is the
> lock_class::hash_entry, not lock_list::entry.
> 
> If lock_class is not indeed RCU used, that would simplify things. Please
> double check.
> 
> But in any case, the normal RCU pattern is:
> 
> lock()
> add-to-data-structure()
> unlock()
> 
> 				rcu_read_lock()
> 				obj = obtain-from-data-structure();
> 
> lock()
> remove-from-data-structure()
>    call_rcu()
> unlock();
> 
> 				use(obj);
> 				rcu_read_unlock();
> 
> 
> <rcu-callback>
>    actually-free-obj()
> 
> 
> 
> Fundamentally RCU delays the callback to the point where the last observer
> that started before call_rcu() has finished and no later (in practise it often
> is much later, but no guarantees there). So being able to reach an object
> after you did call_rcu() on it is a fundamental fail.

Hi Peter,

I agree with what you wrote. The only code I know of that accesses list
entries using RCU is the __bfs() function. In that function I found the
following loop:

	list_for_each_entry_rcu(entry, head, entry) { [ ... ] }

Since zap_class() calls list_del_rcu(&entry->entry), since a grace period
occurs between the call_rcu() invocation and the RCU callback function,
since at least an RCU reader lock must be held around RCU loops and since
sleeping is not allowed while holding an RCU read lock I think there is
no risk that __bfs() will examine a list entry after it has been freed.

Bart.