Re: kern/54979 (radixtree might misbehave if ENOMEM)

[Andrew Doran <ad%netbsd.org@localhost>]

The following reply was made to PR kern/54979; it has been noted by GNATS.

From: Andrew Doran <ad%netbsd.org@localhost>
To: gnats-bugs%netbsd.org@localhost
Cc: 
Subject: Re: kern/54979 (radixtree might misbehave if ENOMEM)
Date: Sun, 15 Mar 2020 19:56:01 +0000

 I see one possible failure path:
 
 Imagine radix_tree_grow() manages to insert >0 nodes to increase the height
 of the tree, but fails to allocate at least one node to complete the path,
 and returns ENOMEM.
 
 There is an assumption that the operation will be retried and a subsequent
 radix_tree_insert_node() will finish it off.
 
 That implies there will be a matching radix_tree_remove_node() later too, to
 remove the leaf node and collapse the height of the tree back down to zero.
 
 If the insertion was speculative that might not happen, so the the tree can
 be left in limbo.
 
 Now, radix_tree_grow() can't back out what it's done without sabotaging
 radix_tree_await_memory(), and a call to uvm_wait() in libkern would suck,
 so maybe another solution would be to back out the change and cache the
 already allocated nodes with struct radix_tree (with a catchall to free
 them in radix_tree_fini_tree()).  It's not very elegant though.
 
 Andrew