idtree: fix handling of large ids (eg INT_MAX)

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.

Signed-off-by: Rusty Russell <rusty@rustorp.com.au>

diff --git a/lib/util/idtree.c b/lib/util/idtree.c
index 06544e1444b85bb4c5f3c54c47144eb9e19022eb..ef6d21fd2852d79d825a26bb5001b89baae60401 100644 (file)
--- a/lib/util/idtree.c
+++ b/lib/util/idtree.c
@@ -240,7 +240,7 @@ build_up:
 static int sub_remove(struct idr_context *idp, int shift, int id)
 {
        struct idr_layer *p = idp->top;
-       struct idr_layer **pa[MAX_LEVEL];
+       struct idr_layer **pa[1+MAX_LEVEL];
        struct idr_layer ***paa = &pa[0];
        int n;
 
@@ -280,8 +280,10 @@ static void *_idr_find(struct idr_context *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 + IDR_BITS))
+       if (n + IDR_BITS < 31 &&
+           ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS))) {
             return NULL;
+       }
 
        /* Mask off upper bits we don't use for the search. */
        id &= MAX_ID_MASK;