r3056: added a id -> pointer data structure (a type of radix tree). This is

an extremely efficient way of mapping from an integer handle (such as
an open file handle) to a pointer (such as the structure containing
the open file information). The code is taken from lib/idr.c in the
2.6 Linux kernel, and is very fast and space efficient. By using
talloc it even has auto cleanup.

This commit converts the handling of open file handles and open
directory search handles to use the idtree routines. In combination
with talloc destructors, this simplifies the structure handling in the
pvfs backend a lot. For example, we no longer need to keep a linked
list of open directory searches at all, and we no longer need to do
linear scans of the list of open files on most operations.

The end result is that the pvfs code is now extremely scalable. You
can have 10s of thousands of open files and open searches and the code
still runs very fast.

I have also added a small optimisation into the file close path, to
avoid looking in the byte range locking database if we know that there
are no locks outstanding.
(This used to be commit 16835a0ef91a16fa01145b773aad8d43da215dbf)

7 files changed, 494 insertions, 130 deletions

diff --git a/source4/ntvfs/common/idtree.c b/source4/ntvfs/common/idtree.c
new file mode 100644
index 00000000000..80f7df97a0f
--- /dev/null
+++ b/source4/ntvfs/common/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 (n<maxid && ((bm & (1<<n)) == 0)) n++;
+	return n;
+}
+
+static void free_layer(struct idr *idp, struct idr_layer *p)
+{
+	p->ary[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);
+}
diff --git a/source4/ntvfs/posix/config.mk b/source4/ntvfs/posix/config.mk
index b6ba073a99e..732e896d2b1 100644
--- a/source4/ntvfs/posix/config.mk
+++ b/source4/ntvfs/posix/config.mk
@@ -22,6 +22,7 @@ ADD_OBJ_FILES = \
 		ntvfs/posix/pvfs_shortname.o \
 		ntvfs/posix/pvfs_lock.o \
 		ntvfs/posix/pvfs_wait.o \
+		ntvfs/common/idtree.o \
 		ntvfs/common/brlock.o
 # End MODULE ntvfs_posix
 ################################################
diff --git a/source4/ntvfs/posix/pvfs_lock.c b/source4/ntvfs/posix/pvfs_lock.c
index e32fcb2e3a4..f52e68eeb16 100644
--- a/source4/ntvfs/posix/pvfs_lock.c
+++ b/source4/ntvfs/posix/pvfs_lock.c
@@ -75,6 +75,7 @@ static void pvfs_lock_async_failed(struct pvfs_state *pvfs,
 			   f->fnum,
 			   locks[i].offset,
 			   locks[i].count);
+		f->lock_count--;
 	}
 	req->async.status = status;
 	req->async.send_fn(req);
@@ -117,6 +118,10 @@ static void pvfs_pending_lock_continue(void *private, BOOL timed_out)
 			  locks[pending->pending_lock].count,
 			  rw, NULL);
 
+	if (NT_STATUS_IS_OK(status)) {
+		f->lock_count++;
+	}
+
 	/* if we have failed and timed out, or succeeded, then we
 	   don't need the pending lock any more */
 	if (NT_STATUS_IS_OK(status) || timed_out) {
@@ -182,6 +187,8 @@ static void pvfs_pending_lock_continue(void *private, BOOL timed_out)
 			pvfs_lock_async_failed(pvfs, req, f, locks, i, status);
 			return;
 		}
+
+		f->lock_count++;
 	}
 
 	/* we've managed to get all the locks. Tell the client */
@@ -191,26 +198,28 @@ static void pvfs_pending_lock_continue(void *private, BOOL timed_out)
 
 
 /*
-  called when we close a file that might have pending locks
+  called when we close a file that might have locks
 */
-void pvfs_lock_close_pending(struct pvfs_state *pvfs, struct pvfs_file *f)
+void pvfs_lock_close(struct pvfs_state *pvfs, struct pvfs_file *f)
 {
 	struct pvfs_pending_lock *p, *next;
-	NTSTATUS status;
 
+	if (f->lock_count || f->pending_list) {
+		DEBUG(5,("pvfs_lock: removing %.0f locks on close\n", 
+			 (double)f->lock_count));
+		brl_close(f->pvfs->brl_context, &f->locking_key, f->fnum);
+		f->lock_count = 0;
+	}
+
+	/* reply to all the pending lock requests, telling them the 
+	   lock failed */
 	for (p=f->pending_list;p;p=next) {
 		next = p->next;
 		DLIST_REMOVE(f->pending_list, p);
-		status = brl_remove_pending(pvfs->brl_context, &f->locking_key, p);
-		if (!NT_STATUS_IS_OK(status)) {
-			DEBUG(0,("pvfs_lock_close_pending: failed to remove pending lock - %s\n", 
-				 nt_errstr(status)));
-		}
 		talloc_free(p->wait_handle);
 		p->req->async.status = NT_STATUS_RANGE_NOT_LOCKED;
 		p->req->async.send_fn(p->req);
 	}
-
 }
 
 
@@ -262,6 +271,7 @@ NTSTATUS pvfs_lock(struct ntvfs_module_context *ntvfs,
 	int i;
 	enum brl_type rw;
 	struct pvfs_pending_lock *pending = NULL;
+	NTSTATUS status;
 
 	f = pvfs_find_fd(pvfs, req, lck->generic.in.fnum);
 	if (!f) {
@@ -270,21 +280,29 @@ NTSTATUS pvfs_lock(struct ntvfs_module_context *ntvfs,
 
 	switch (lck->generic.level) {
 	case RAW_LOCK_LOCK:
-		return brl_lock(pvfs->brl_context,
-				&f->locking_key,
-				req->smbpid,
-				f->fnum,
-				lck->lock.in.offset,
-				lck->lock.in.count,
-				WRITE_LOCK, NULL);
-				
-	case RAW_LOCK_UNLOCK:
-		return brl_unlock(pvfs->brl_context,
+		status = brl_lock(pvfs->brl_context,
 				  &f->locking_key,
 				  req->smbpid,
 				  f->fnum,
 				  lck->lock.in.offset,
-				  lck->lock.in.count);
+				  lck->lock.in.count,
+				  WRITE_LOCK, NULL);
+		if (NT_STATUS_IS_OK(status)) {
+			f->lock_count++;
+		}
+		return status;
+				
+	case RAW_LOCK_UNLOCK:
+		status = brl_unlock(pvfs->brl_context,
+				    &f->locking_key,
+				    req->smbpid,
+				    f->fnum,
+				    lck->lock.in.offset,
+				    lck->lock.in.count);
+		if (NT_STATUS_IS_OK(status)) {
+			f->lock_count--;
+		}
+		return status;
 
 	case RAW_LOCK_GENERIC:
 		return NT_STATUS_INVALID_LEVEL;
@@ -337,7 +355,6 @@ NTSTATUS pvfs_lock(struct ntvfs_module_context *ntvfs,
 	locks = lck->lockx.in.locks;
 
 	for (i=0;i<lck->lockx.in.ulock_cnt;i++) {
-		NTSTATUS status;
 		status = brl_unlock(pvfs->brl_context,
 				    &f->locking_key,
 				    locks[i].pid,
@@ -347,13 +364,12 @@ NTSTATUS pvfs_lock(struct ntvfs_module_context *ntvfs,
 		if (!NT_STATUS_IS_OK(status)) {
 			return status;
 		}
+		f->lock_count--;
 	}
 
 	locks += i;
 
 	for (i=0;i<lck->lockx.in.lock_cnt;i++) {
-		NTSTATUS status;
-
 		if (pending) {
 			pending->pending_lock = i;
 		}
@@ -387,9 +403,11 @@ NTSTATUS pvfs_lock(struct ntvfs_module_context *ntvfs,
 					   f->fnum,
 					   locks[i].offset,
 					   locks[i].count);
+				f->lock_count--;
 			}
 			return status;
 		}
+		f->lock_count++;
 	}
 
 	return NT_STATUS_OK;
diff --git a/source4/ntvfs/posix/pvfs_open.c b/source4/ntvfs/posix/pvfs_open.c
index 429f519bcad..c2555583696 100644
--- a/source4/ntvfs/posix/pvfs_open.c
+++ b/source4/ntvfs/posix/pvfs_open.c
@@ -31,16 +31,19 @@ struct pvfs_file *pvfs_find_fd(struct pvfs_state *pvfs,
 			       struct smbsrv_request *req, uint16_t fnum)
 {
 	struct pvfs_file *f;
-	for (f=pvfs->open_files;f;f=f->next) {
-		if (f->fnum == fnum) {
-			if (req->session != f->session) {
-				DEBUG(2,("pvfs_find_fd: attempt to use wrong session for fnum %d\n", fnum));
-				return NULL;
-			}
-			return f;
-		}
+
+	f = idr_find(pvfs->idtree_fnum, fnum);
+	if (f == NULL) {
+		return NULL;
 	}
-	return NULL;
+
+	if (req->session != f->session) {
+		DEBUG(2,("pvfs_find_fd: attempt to use wrong session for fnum %d\n", 
+			 fnum));
+		return NULL;
+	}
+
+	return f;
 }
 
 /*
@@ -52,14 +55,15 @@ static int pvfs_fd_destructor(void *p)
 {
 	struct pvfs_file *f = p;
 
-	pvfs_lock_close_pending(f->pvfs, f);
-
-	brl_close(f->pvfs->brl_context, &f->locking_key, f->fnum);
+	pvfs_lock_close(f->pvfs, f);
 
 	if (f->fd != -1) {
 		close(f->fd);
 		f->fd = -1;
 	}
+
+	idr_remove(f->pvfs->idtree_fnum, f->fnum);
+
 	return 0;
 }
 
@@ -80,6 +84,7 @@ NTSTATUS pvfs_open(struct ntvfs_module_context *ntvfs,
 		dev_t device;
 		ino_t inode;
 	} lock_context;
+	int fnum;
 
 	if (io->generic.level != RAW_OPEN_GENERIC) {
 		return ntvfs_map_open(req, io, ntvfs);
@@ -147,6 +152,17 @@ NTSTATUS pvfs_open(struct ntvfs_module_context *ntvfs,
 		}
 	}
 
+	f = talloc_p(pvfs, struct pvfs_file);
+	if (f == NULL) {
+		return NT_STATUS_NO_MEMORY;
+	}
+
+	fnum = idr_get_new(pvfs->idtree_fnum, f, 0x10000);
+	if (fnum == -1) {
+		talloc_free(f);
+		return NT_STATUS_TOO_MANY_OPENED_FILES;
+	}
+
 do_open:
 	fd = open(name->full_name, flags, 0644);
 	if (fd == -1) {
@@ -155,25 +171,20 @@ do_open:
 		return pvfs_map_errno(pvfs,errno);
 	}
 
-	f = talloc_p(pvfs, struct pvfs_file);
-	if (f == NULL) {
-		close(fd);
-		return NT_STATUS_NO_MEMORY;
-	}
-
 	/* re-resolve the open fd */
 	status = pvfs_resolve_name_fd(pvfs, fd, name);
 	if (!NT_STATUS_IS_OK(status)) {
 		return status;
 	}
 
-	f->fnum = fd;
+	f->fnum = fnum;
 	f->fd = fd;
 	f->name = talloc_steal(f, name);
 	f->session = req->session;
 	f->smbpid = req->smbpid;
 	f->pvfs = pvfs;
 	f->pending_list = NULL;
+	f->lock_count = 0;
 
 	/* we must zero here to take account of padding */
 	ZERO_STRUCT(lock_context);
@@ -223,22 +234,16 @@ NTSTATUS pvfs_close(struct ntvfs_module_context *ntvfs,
 		return NT_STATUS_INVALID_HANDLE;
 	}
 
-	pvfs_lock_close_pending(pvfs, f);
-
-	status = brl_close(pvfs->brl_context, &f->locking_key, f->fnum);
-	if (!NT_STATUS_IS_OK(status)) {
-		return status;
-	}
-
 	if (close(f->fd) != 0) {
 		status = pvfs_map_errno(pvfs, errno);
 	} else {
 		status = NT_STATUS_OK;
 	}
-
-	talloc_set_destructor(f, NULL);
+	f->fd = -1;
 
 	DLIST_REMOVE(pvfs->open_files, f);
+
+	/* the destructor takes care of the rest */
 	talloc_free(f);
 
 	return status;
@@ -257,7 +262,6 @@ NTSTATUS pvfs_logoff(struct ntvfs_module_context *ntvfs,
 	for (f=pvfs->open_files;f;f=next) {
 		next = f->next;
 		if (f->session == req->session) {
-			talloc_set_destructor(f, NULL);
 			DLIST_REMOVE(pvfs->open_files, f);
 			talloc_free(f);
 		}
@@ -279,7 +283,6 @@ NTSTATUS pvfs_exit(struct ntvfs_module_context *ntvfs,
 	for (f=pvfs->open_files;f;f=next) {
 		next = f->next;
 		if (f->smbpid == req->smbpid) {
-			talloc_set_destructor(f, NULL);
 			DLIST_REMOVE(pvfs->open_files, f);
 			talloc_free(f);
 		}
diff --git a/source4/ntvfs/posix/pvfs_search.c b/source4/ntvfs/posix/pvfs_search.c
index 07f2a0f127d..7b0da321d38 100644
--- a/source4/ntvfs/posix/pvfs_search.c
+++ b/source4/ntvfs/posix/pvfs_search.c
@@ -23,6 +23,17 @@
 #include "include/includes.h"
 #include "vfs_posix.h"
 
+
+/*
+  destroy an open search
+*/
+static int pvfs_search_destructor(void *ptr)
+{
+	struct pvfs_search_state *search = ptr;
+	idr_remove(search->pvfs->idtree_search, search->handle);
+	return 0;
+}
+
 /*
   fill in a single search result for a given info level
 */
@@ -224,32 +235,6 @@ static NTSTATUS pvfs_search_fill(struct pvfs_state *pvfs, TALLOC_CTX *mem_ctx,
 	return NT_STATUS_OK;
 }
 
-/*
-  return the next available search handle
-*/
-static NTSTATUS pvfs_next_search_handle(struct pvfs_state *pvfs, uint16_t *handle, 
-					uint_t max_handles)
-{
-	struct pvfs_search_state *search;
-
-	if (pvfs->search.num_active_searches >= max_handles) {
-		return NT_STATUS_INSUFFICIENT_RESOURCES;
-	}
-
-	(*handle) = (pvfs->search.next_search_handle) & (max_handles-1);
-again:
-	for (search=pvfs->search.open_searches;search;search=search->next) {
-		if (*handle == search->handle) {
-			*handle = ((*handle)+1) & (max_handles-1);
-			goto again;
-		} 
-	}
-	pvfs->search.next_search_handle = ((*handle)+1) & (max_handles-1);
-
-	return NT_STATUS_OK;
-}
-
-
 /* 
    list files in a directory matching a wildcard pattern - old SMBsearch interface
 */
@@ -266,6 +251,7 @@ static NTSTATUS pvfs_search_first_old(struct ntvfs_module_context *ntvfs,
 	const char *pattern;
 	NTSTATUS status;
 	struct pvfs_filename *name;
+	int id;
 
 	search_attrib = io->search_first.in.search_attrib;
 	pattern       = io->search_first.in.pattern;
@@ -301,15 +287,19 @@ static NTSTATUS pvfs_search_first_old(struct ntvfs_module_context *ntvfs,
 
 	/* we need to give a handle back to the client so it
 	   can continue a search */
-	status = pvfs_next_search_handle(pvfs, &search->handle, 0x100);
-	if (!NT_STATUS_IS_OK(status)) {
-		return status;
+	id = idr_get_new(pvfs->idtree_search, search, 0x100);
+	if (id == -1) {
+		return NT_STATUS_INSUFFICIENT_RESOURCES;
 	}
-	
+
+	search->pvfs = pvfs;
+	search->handle = id;
 	search->dir = dir;
 	search->current_index = 0;
 	search->search_attrib = search_attrib;
 
+	talloc_set_destructor(search, pvfs_search_destructor);
+
 	status = pvfs_search_fill(pvfs, req, io->search_first.in.max_count, search, io->generic.level,
 				  &reply_count, search_private, callback);
 	if (!NT_STATUS_IS_OK(status)) {
@@ -323,9 +313,7 @@ static NTSTATUS pvfs_search_first_old(struct ntvfs_module_context *ntvfs,
 		return STATUS_NO_MORE_FILES;
 	}
 
-	pvfs->search.num_active_searches++;
 	talloc_steal(pvfs, search);
-	DLIST_ADD(pvfs->search.open_searches, search);
 
 	return NT_STATUS_OK;
 }
@@ -346,11 +334,8 @@ static NTSTATUS pvfs_search_next_old(struct ntvfs_module_context *ntvfs,
 	handle    = io->search_next.in.id.handle;
 	max_count = io->search_next.in.max_count;
 
-	for (search=pvfs->search.open_searches; search; search = search->next) {
-		if (search->handle == handle) break;
-	}
-	
-	if (!search) {
+	search = idr_find(pvfs->idtree_search, handle);
+	if (search == NULL) {
 		/* we didn't find the search handle */
 		return NT_STATUS_INVALID_HANDLE;
 	}
@@ -369,7 +354,6 @@ static NTSTATUS pvfs_search_next_old(struct ntvfs_module_context *ntvfs,
 
 	/* not matching any entries means end of search */
 	if (reply_count == 0) {
-		DLIST_REMOVE(pvfs->search.open_searches, search);
 		talloc_free(search);
 	}
 
@@ -392,6 +376,7 @@ NTSTATUS pvfs_search_first(struct ntvfs_module_context *ntvfs,
 	const char *pattern;
 	NTSTATUS status;
 	struct pvfs_filename *name;
+	int id;
 
 	if (io->generic.level >= RAW_SEARCH_SEARCH) {
 		return pvfs_search_first_old(ntvfs, req, io, search_private, callback);
@@ -430,17 +415,19 @@ NTSTATUS pvfs_search_first(struct ntvfs_module_context *ntvfs,
 		return status;
 	}
 
-	/* we need to give a handle back to the client so it
-	   can continue a search */
-	status = pvfs_next_search_handle(pvfs, &search->handle, 0x10000);
-	if (!NT_STATUS_IS_OK(status)) {
-		return status;
+	id = idr_get_new(pvfs->idtree_search, search, 0x10000);
+	if (id == -1) {
+		return NT_STATUS_INSUFFICIENT_RESOURCES;
 	}
-	
+
+	search->pvfs = pvfs;
+	search->handle = id;
 	search->dir = dir;
 	search->current_index = 0;
 	search->search_attrib = search_attrib;
 
+	talloc_set_destructor(search, pvfs_search_destructor);
+
 	status = pvfs_search_fill(pvfs, req, max_count, search, io->generic.level,
 				  &reply_count, search_private, callback);
 	if (!NT_STATUS_IS_OK(status)) {
@@ -463,9 +450,7 @@ NTSTATUS pvfs_search_first(struct ntvfs_module_context *ntvfs,
 	     io->t2ffirst.out.end_of_search)) {
 		talloc_free(search);
 	} else {
-		pvfs->search.num_active_searches++;
 		talloc_steal(pvfs, search);
-		DLIST_ADD(pvfs->search.open_searches, search);
 	}
 
 	return NT_STATUS_OK;
@@ -491,11 +476,8 @@ NTSTATUS pvfs_search_next(struct ntvfs_module_context *ntvfs,
 
 	handle = io->t2fnext.in.handle;
 
-	for (search=pvfs->search.open_searches; search; search = search->next) {
-		if (search->handle == handle) break;
-	}
-	
-	if (!search) {
+	search = idr_find(pvfs->idtree_search, handle);
+	if (search == NULL) {
 		/* we didn't find the search handle */
 		return NT_STATUS_INVALID_HANDLE;
 	}
@@ -544,7 +526,6 @@ found:
 	if ((io->t2fnext.in.flags & FLAG_TRANS2_FIND_CLOSE) ||
 	    ((io->t2fnext.in.flags & FLAG_TRANS2_FIND_CLOSE_IF_END) && 
 	     io->t2fnext.out.end_of_search)) {
-		DLIST_REMOVE(pvfs->search.open_searches, search);
 		talloc_free(search);
 	}
 
@@ -565,16 +546,12 @@ NTSTATUS pvfs_search_close(struct ntvfs_module_context *ntvfs,
 		handle = io->findclose.in.handle;
 	}
 
-	for (search=pvfs->search.open_searches; search; search = search->next) {
-		if (search->handle == handle) break;
-	}
-	
-	if (!search) {
+	search = idr_find(pvfs->idtree_search, handle);
+	if (search == NULL) {
 		/* we didn't find the search handle */
 		return NT_STATUS_INVALID_HANDLE;
 	}
 
-	DLIST_REMOVE(pvfs->search.open_searches, search);
 	talloc_free(search);
 
 	return NT_STATUS_OK;
diff --git a/source4/ntvfs/posix/vfs_posix.c b/source4/ntvfs/posix/vfs_posix.c
index e989f8de676..8aa028919c4 100644
--- a/source4/ntvfs/posix/vfs_posix.c
+++ b/source4/ntvfs/posix/vfs_posix.c
@@ -61,11 +61,10 @@ static NTSTATUS pvfs_connect(struct ntvfs_module_context *ntvfs,
 	char *base_directory;
 	NTSTATUS status;
 
-	pvfs = talloc_p(tcon, struct pvfs_state);
+	pvfs = talloc_zero_p(tcon, struct pvfs_state);
 	if (pvfs == NULL) {
 		return NT_STATUS_NO_MEMORY;
 	}
-	ZERO_STRUCTP(pvfs);
 
 	/* for simplicity of path construction, remove any trailing slash now */
 	base_directory = talloc_strdup(pvfs, lp_pathname(tcon->service));
@@ -95,6 +94,18 @@ static NTSTATUS pvfs_connect(struct ntvfs_module_context *ntvfs,
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
+	/* allocate the fnum id -> ptr tree */
+	pvfs->idtree_fnum = idr_init(pvfs);
+	if (pvfs->idtree_fnum == NULL) {
+		return NT_STATUS_NO_MEMORY;
+	}
+
+	/* allocate the search handle -> ptr tree */
+	pvfs->idtree_search = idr_init(pvfs);
+	if (pvfs->idtree_search == NULL) {
+		return NT_STATUS_NO_MEMORY;
+	}
+
 	status = pvfs_mangle_init(pvfs);
 	if (!NT_STATUS_IS_OK(status)) {
 		return status;
diff --git a/source4/ntvfs/posix/vfs_posix.h b/source4/ntvfs/posix/vfs_posix.h
index 6aaa43a2134..ae601c60c7b 100644
--- a/source4/ntvfs/posix/vfs_posix.h
+++ b/source4/ntvfs/posix/vfs_posix.h
@@ -32,27 +32,17 @@ struct pvfs_state {
 	const char *share_name;
 	uint_t flags;
 
-	struct {
-		/* a linked list of open searches */
-		struct pvfs_search_state *open_searches;
-
-		/* search handles are returned to the clients so they
-		   can continue searches */
-		uint16_t next_search_handle;
-
-		/* count of active searches */
-		uint_t num_active_searches;
-
-		/* during trans2 search continuations we need to use
-		   the initial search attributes */
-		uint16_t search_attrib;
-	} search;
-
 	struct pvfs_file *open_files;
 
 	struct pvfs_mangle_context *mangle_ctx;
 
 	void *brl_context;
+
+	/* an id tree mapping open search ID to a pvfs_search_state structure */
+	void *idtree_search;
+
+	/* an id tree mapping open file handle -> struct pvfs_file */
+	void *idtree_fnum;
 };
 
 
@@ -95,7 +85,7 @@ struct pvfs_dir {
 
 /* the state of a search started with pvfs_search_first() */
 struct pvfs_search_state {
-	struct pvfs_search_state *next, *prev;
+	struct pvfs_state *pvfs;
 	uint16_t handle;
 	uint_t current_index;
 	uint16_t search_attrib;
@@ -126,6 +116,10 @@ struct pvfs_file {
 
 	/* a list of pending locks - used for locking cancel operations */
 	struct pvfs_pending_lock *pending_list;
+
+	/* a count of active locks - used to avoid calling brl_close on
+	   file close */
+	uint64_t lock_count;
 };