⬢ DragonFlyBSD Kernel Audit
DF-3011 / fix.diff
← back to finding ↓ download raw 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
--- a/sys/vfs/hammer/hammer_btree.c
+++ b/sys/vfs/hammer/hammer_btree.c
@@ -83,8 +83,23 @@
 static int btree_search(hammer_cursor_t cursor, int flags);
 static int btree_split_internal(hammer_cursor_t cursor);
 static int btree_split_leaf(hammer_cursor_t cursor);
-static int btree_remove(hammer_cursor_t cursor, int *ndelete);
+static int btree_remove(hammer_cursor_t cursor, int *ndelete, int depth);
 static __inline int btree_node_is_full(hammer_node_ondisk_t node);
+
+/*
+ * DF-3011: btree_remove() recurses once per single-element internal-node
+ * level and nothing bounds B-tree depth (the pushdown in btree_search()
+ * and the hammer_btree_get_parent() walk are iterative and unbounded).
+ * A crafted image containing a chain of internal nodes with count==1
+ * (all counts/types/CRCs VALID) drives this recursion arbitrarily deep
+ * on the caller's 16KB kernel stack, overflowing it.  Cap the recursion;
+ * past the cap we return EDEADLK, which every caller already handles
+ * identically to the deadlock-defer case.  Nothing has been modified at
+ * the level that bails, so the tree stays consistent and the pruner
+ * cleans up the empty leaf later.  32 is far above any depth a real
+ * 63-way-radix tree reaches and far below the exhaustion threshold.
+ */
+#define BTREE_REMOVE_DEPTH_MAX	32
 static int hammer_btree_mirror_propagate(hammer_cursor_t cursor,
 			hammer_tid_t mirror_tid);
 static void hammer_make_separator(hammer_base_elm_t key1,
@@ -930,7 +945,7 @@
 	 */
 	KKASSERT(cursor->index <= ondisk->count);
 	if (ondisk->count == 0) {
-		error = btree_remove(cursor, ndelete);
+		error = btree_remove(cursor, ndelete, 0);
 		if (error == EDEADLK)
 			error = 0;
 	} else {
@@ -1935,7 +1950,7 @@
  * for further iteration but not for an immediate insertion or deletion.
  */
 static int
-btree_remove(hammer_cursor_t cursor, int *ndelete)
+btree_remove(hammer_cursor_t cursor, int *ndelete, int depth)
 {
 	hammer_node_ondisk_t ondisk;
 	hammer_btree_elm_t elm;
@@ -1978,6 +1993,13 @@
 	 */
 	if (parent->ondisk->count == 1) {
 		/*
+		 * DF-3011: bail out with EDEADLK (the defer semantics
+		 * below) before recursing any deeper; crafted images can
+		 * make the single-element chain arbitrarily long.
+		 */
+		if (depth >= BTREE_REMOVE_DEPTH_MAX)
+			return (EDEADLK);
+		/*
 		 * This special cursor_up_locked() call leaves the original
 		 * node exclusively locked and referenced, leaves the
 		 * original parent locked (as the new node), and locks the
@@ -2004,7 +2026,7 @@
 
 		if (error == 0) {
 			hammer_cursor_deleted_element(cursor->node, 0);
-			error = btree_remove(cursor, ndelete);
+			error = btree_remove(cursor, ndelete, depth + 1);
 			if (error == 0) {
 				KKASSERT(node != cursor->node);
 				hammer_cursor_removed_node(