From b2b8282b8cc1774ac9cbef9a31ac23705ca45ac2 Mon Sep 17 00:00:00 2001 From: Andrew Tridgell Date: Tue, 19 Oct 2004 07:08:35 +0000 Subject: r3057: - moved the idtree.c code into lib/ - converted the tid handling to use a idtree instead of bitmaps (This used to be commit 4220914179d10132057216650b65ed7f7679717e) --- source4/lib/idtree.c | 360 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 360 insertions(+) create mode 100644 source4/lib/idtree.c (limited to 'source4/lib/idtree.c') diff --git a/source4/lib/idtree.c b/source4/lib/idtree.c new file mode 100644 index 0000000000..80f7df97a0 --- /dev/null +++ b/source4/lib/idtree.c @@ -0,0 +1,360 @@ +/* + Unix SMB/CIFS implementation. + + very efficient functions to manage mapping a id (such as a fnum) to + a pointer. This is used for fnum and search id allocation. + + Copyright (C) Andrew Tridgell 2004 + + This code is derived from lib/idr.c in the 2.6 Linux kernel, which was + written by Jim Houston jim.houston@ccur.com, and is + Copyright (C) 2002 by Concurrent Computer Corporation + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. +*/ + +/* + see the section marked "public interface" below for documentation +*/ + +#include "includes.h" + +#define IDR_BITS 5 +#define IDR_FULL 0xfffffffful +#define TOP_LEVEL_FULL (IDR_FULL >> 30) +#define IDR_SIZE (1 << IDR_BITS) +#define IDR_MASK ((1 << IDR_BITS)-1) +#define MAX_ID_SHIFT (sizeof(int)*8 - 1) +#define MAX_ID_BIT (1U << MAX_ID_SHIFT) +#define MAX_ID_MASK (MAX_ID_BIT - 1) +#define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS +#define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL + +#define set_bit(bit, v) (v) |= (1<<(bit)) +#define clear_bit(bit, v) (v) &= ~(1<<(bit)) + +struct idr_layer { + uint32_t bitmap; + struct idr_layer *ary[IDR_SIZE]; + int count; +}; + +struct idr { + struct idr_layer *top; + struct idr_layer *id_free; + int layers; + int id_free_cnt; +}; + +static struct idr_layer *alloc_layer(struct idr *idp) +{ + struct idr_layer *p; + + if (!(p = idp->id_free)) + return NULL; + idp->id_free = p->ary[0]; + idp->id_free_cnt--; + p->ary[0] = NULL; + return p; +} + +static int find_next_bit(uint32_t bm, int maxid, int n) +{ + while (nary[0] = idp->id_free; + idp->id_free = p; + idp->id_free_cnt++; +} + +static int idr_pre_get(struct idr *idp) +{ + while (idp->id_free_cnt < IDR_FREE_MAX) { + struct idr_layer *new = talloc_zero_p(idp, struct idr_layer); + if(new == NULL) + return (0); + free_layer(idp, new); + } + return 1; +} + +static int sub_alloc(struct idr *idp, void *ptr, int *starting_id) +{ + int n, m, sh; + struct idr_layer *p, *new; + struct idr_layer *pa[MAX_LEVEL]; + int l, id; + uint32_t bm; + + id = *starting_id; + p = idp->top; + l = idp->layers; + pa[l--] = NULL; + while (1) { + /* + * We run around this while until we reach the leaf node... + */ + n = (id >> (IDR_BITS*l)) & IDR_MASK; + bm = ~p->bitmap; + m = find_next_bit(bm, IDR_SIZE, n); + if (m == IDR_SIZE) { + /* no space available go back to previous layer. */ + l++; + id = (id | ((1 << (IDR_BITS*l))-1)) + 1; + if (!(p = pa[l])) { + *starting_id = id; + return -2; + } + continue; + } + if (m != n) { + sh = IDR_BITS*l; + id = ((id >> sh) ^ n ^ m) << sh; + } + if ((id >= MAX_ID_BIT) || (id < 0)) + return -1; + if (l == 0) + break; + /* + * Create the layer below if it is missing. + */ + if (!p->ary[m]) { + if (!(new = alloc_layer(idp))) + return -1; + p->ary[m] = new; + p->count++; + } + pa[l--] = p; + p = p->ary[m]; + } + /* + * We have reached the leaf node, plant the + * users pointer and return the raw id. + */ + p->ary[m] = (struct idr_layer *)ptr; + set_bit(m, p->bitmap); + p->count++; + /* + * If this layer is full mark the bit in the layer above + * to show that this part of the radix tree is full. + * This may complete the layer above and require walking + * up the radix tree. + */ + n = id; + while (p->bitmap == IDR_FULL) { + if (!(p = pa[++l])) + break; + n = n >> IDR_BITS; + set_bit((n & IDR_MASK), p->bitmap); + } + return(id); +} + +static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id) +{ + struct idr_layer *p, *new; + int layers, v, id; + + idr_pre_get(idp); + + id = starting_id; +build_up: + p = idp->top; + layers = idp->layers; + if (!p) { + if (!(p = alloc_layer(idp))) + return -1; + layers = 1; + } + /* + * Add a new layer to the top of the tree if the requested + * id is larger than the currently allocated space. + */ + while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) { + layers++; + if (!p->count) + continue; + if (!(new = alloc_layer(idp))) { + /* + * The allocation failed. If we built part of + * the structure tear it down. + */ + for (new = p; p && p != idp->top; new = p) { + p = p->ary[0]; + new->ary[0] = NULL; + new->bitmap = new->count = 0; + free_layer(idp, new); + } + return -1; + } + new->ary[0] = p; + new->count = 1; + if (p->bitmap == IDR_FULL) + set_bit(0, new->bitmap); + p = new; + } + idp->top = p; + idp->layers = layers; + v = sub_alloc(idp, ptr, &id); + if (v == -2) + goto build_up; + return(v); +} + +static void sub_remove(struct idr *idp, int shift, int id) +{ + struct idr_layer *p = idp->top; + struct idr_layer **pa[MAX_LEVEL]; + struct idr_layer ***paa = &pa[0]; + + *paa = NULL; + *++paa = &idp->top; + + while ((shift > 0) && p) { + int n = (id >> shift) & IDR_MASK; + clear_bit(n, p->bitmap); + *++paa = &p->ary[n]; + p = p->ary[n]; + shift -= IDR_BITS; + } + if (p != NULL) { + int n = id & IDR_MASK; + clear_bit(n, p->bitmap); + p->ary[n] = NULL; + while(*paa && ! --((**paa)->count)){ + free_layer(idp, **paa); + **paa-- = NULL; + } + if ( ! *paa ) + idp->layers = 0; + } +} + +static void *_idr_find(struct idr *idp, int id) +{ + int n; + struct idr_layer *p; + + n = idp->layers * IDR_BITS; + p = idp->top; + /* + * 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)) + return NULL; + + /* Mask off upper bits we don't use for the search. */ + id &= MAX_ID_MASK; + + while (n > 0 && p) { + n -= IDR_BITS; + p = p->ary[(id >> n) & IDR_MASK]; + } + return((void *)p); +} + +static void _idr_remove(struct idr *idp, int id) +{ + struct idr_layer *p; + + if (_idr_find(idp, id) == NULL) { + DEBUG(0,("WARNING: attempt to remove non-existant id %d in idtree\n", + id)); + return; + } + + /* Mask off upper bits we don't use for the search. */ + id &= MAX_ID_MASK; + + sub_remove(idp, (idp->layers - 1) * IDR_BITS, id); + if ( idp->top && idp->top->count == 1 && + (idp->layers > 1) && + idp->top->ary[0]) { + /* We can drop a layer */ + p = idp->top->ary[0]; + idp->top->bitmap = idp->top->count = 0; + free_layer(idp, idp->top); + idp->top = p; + --idp->layers; + } + while (idp->id_free_cnt >= IDR_FREE_MAX) { + p = alloc_layer(idp); + talloc_free(p); + return; + } +} + +/************************************************************************ + this is the public interface +**************************************************************************/ + +/* + initialise a idr tree. The context return value must be passed to + all subsequent idr calls. To destroy the idr tree use talloc_free() + on this context + */ +void *idr_init(TALLOC_CTX *mem_ctx) +{ + return talloc_zero_p(mem_ctx, struct idr); +} + +/* + allocate the next available id, and assign 'ptr' into its slot. + you can retrieve later this pointer using idr_find() +*/ +int idr_get_new(void *idp, void *ptr, int limit) +{ + int ret = idr_get_new_above_int((struct idr *)idp, ptr, 0); + if (ret >= limit) { + idr_remove(idp, ret); + return -1; + } + return ret; +} + +/* + allocate a new id, giving the first available value greater than or + equal to the given starting id +*/ +int idr_get_new_above(void *idp, void *ptr, int starting_id, int limit) +{ + int ret = idr_get_new_above_int((struct idr *)idp, ptr, starting_id); + if (ret >= limit) { + idr_remove(idp, ret); + return -1; + } + return ret; +} + +/* + find a pointer value previously set with idr_get_new given an id +*/ +void *idr_find(void *idp, int id) +{ + return _idr_find((struct idr *)idp, id); +} + +/* + remove an id from the idr tree +*/ +void idr_remove(void *idp, int id) +{ + return _idr_remove((struct idr *)idp, id); +} -- cgit