From: Rusty Russell <rusty@rustcorp.com.au>
Date: Mon, 6 Dec 2010 03:00:59 +0000 (+1030)
Subject: idtree: import fix from SAMBA source
X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=6994f3d0b1fefa78443253b6b9bf4db15f29b3f3

idtree: import fix from SAMBA source

(Imported from b53f8c187de8)

Author: Rusty Russell <rusty@rustorp.com.au>
Date:   Thu Jun 10 13:27:51 2010 -0700

Since idtree assigns sequentially, it rarely reaches high numbers.
But such numbers can be forced with idr_get_new_above(), and that
reveals two bugs:

1) Crash in sub_remove() caused by pa array being too short.
2) Shift by more than 32 in _idr_find(), which is undefined, causing
   the "outside the current tree" optimization to misfire and return NULL.
---

diff --git a/ccan/idtree/idtree.c b/ccan/idtree/idtree.c
index bf83c318..bc7ba5fc 100644
--- a/ccan/idtree/idtree.c
+++ b/ccan/idtree/idtree.c
@@ -236,7 +236,7 @@ build_up:
 static int sub_remove(struct idtree *idp, int shift, int id)
 {
 	struct idtree_layer *p = idp->top;
-	struct idtree_layer **pa[MAX_LEVEL];
+	struct idtree_layer **pa[1+MAX_LEVEL];
 	struct idtree_layer ***paa = &pa[0];
 	int n;
 
@@ -276,7 +276,8 @@ void *idtree_lookup(const struct idtree *idp, int id)
 	 * This tests to see if bits outside the current tree are
 	 * present.  If so, tain't one of ours!
 	 */
-	if ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDTREE_BITS))
+	if (n + IDTREE_BITS < 31 &&
+	    (id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDTREE_BITS))
 	     return NULL;
 
 	/* Mask off upper bits we don't use for the search. */