merged a bugfix for the idtree code from the Linux kernel. This
authorAndrew Tridgell <tridge@samba.org>
Tue, 30 Sep 2008 14:14:31 +0000 (07:14 -0700)
committerAndrew Tridgell <tridge@samba.org>
Tue, 30 Sep 2008 14:14:31 +0000 (07:14 -0700)
matches commit 7aae6dd80e265aa9402ed507caaff4a5dba55069 in the kernel.

Many thanks to Jim Houston for pointing out this fix to us

source4/lib/util/idtree.c

index 1e2cc2976a330a6f371c748e8913e7d7408a7668..392f4e81f82bd420d7737bfd83b756b35650a538 100644 (file)
@@ -105,12 +105,13 @@ static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
        int n, m, sh;
        struct idr_layer *p, *new;
        struct idr_layer *pa[MAX_LEVEL];
        int n, m, sh;
        struct idr_layer *p, *new;
        struct idr_layer *pa[MAX_LEVEL];
-       int l, id;
+       int l, id, oid;
        uint32_t bm;
 
        memset(pa, 0, sizeof(pa));
 
        id = *starting_id;
        uint32_t bm;
 
        memset(pa, 0, sizeof(pa));
 
        id = *starting_id;
+restart:
        p = idp->top;
        l = idp->layers;
        pa[l--] = NULL;
        p = idp->top;
        l = idp->layers;
        pa[l--] = NULL;
@@ -124,12 +125,23 @@ static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
                if (m == IDR_SIZE) {
                        /* no space available go back to previous layer. */
                        l++;
                if (m == IDR_SIZE) {
                        /* no space available go back to previous layer. */
                        l++;
+                       oid = id;
                        id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
                        id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
+
+                       /* if already at the top layer, we need to grow */
                        if (!(p = pa[l])) {
                                *starting_id = id;
                                return -2;
                        }
                        if (!(p = pa[l])) {
                                *starting_id = id;
                                return -2;
                        }
+
+                       /* If we need to go up one layer, continue the
+                        * loop; otherwise, restart from the top.
+                        */
+                       sh = IDR_BITS * (l + 1);
+                       if (oid >> sh == id >> sh)
                        continue;
                        continue;
+                       else
+                               goto restart;
                }
                if (m != n) {
                        sh = IDR_BITS*l;
                }
                if (m != n) {
                        sh = IDR_BITS*l;