got rid of the Files[] array completely (previously I'd just made it

private to files.c)

It now is a doubly linked list with a bitmap for allocated file
numbers. Similarly for the fd_ptr code. I also changed the default
maximum number of open files to 4096. The static cost is 1 bit per
file.

It all seems to work, and it passes the "does Sue scream" test, but if
you see weird behaviour then please investigate. With the volume of
new code that has gone in there are bound to be one or two bugs
lurking.

note that you must do a "make clean" before building this as many data
structures have changed in size.
(This used to be commit 79755ce97004b787d7e83a8d18fc4c7c003b7231)

8 files changed, 234 insertions, 154 deletions

diff --git a/source3/Makefile.in b/source3/Makefile.in
index 51cf4feec1..677159b440 100644
--- a/source3/Makefile.in
+++ b/source3/Makefile.in
@@ -88,7 +88,8 @@ LIB_OBJ = lib/charcnv.o lib/charset.o lib/debug.o lib/fault.o \
           lib/getsmbpass.o lib/interface.o lib/kanji.o lib/md4.o \
           lib/membuffer.o lib/netmask.o lib/pidfile.o lib/replace.o \
           lib/signal.o lib/slprintf.o lib/system.o lib/time.o lib/ufc.o \
-          lib/util.o lib/genrand.o lib/username.o lib/access.o lib/smbrun.o
+          lib/util.o lib/genrand.o lib/username.o lib/access.o lib/smbrun.o \
+	  lib/bitmap.o
 
 UBIQX_OBJ = ubiqx/ubi_BinTree.o ubiqx/ubi_Cache.o ubiqx/ubi_SplayTree.o \
             ubiqx/ubi_dLinkList.o ubiqx/ubi_sLinkList.o
diff --git a/source3/include/proto.h b/source3/include/proto.h
index 6f2a593f92..e52ffdcd7a 100644
--- a/source3/include/proto.h
+++ b/source3/include/proto.h
@@ -49,6 +49,15 @@ BOOL allow_access(char *deny_list,char *allow_list,
 		  char *cname,char *caddr);
 BOOL check_access(int sock, char *allow_list, char *deny_list);
 
+/*The following definitions come from  lib/bitmap.c  */
+
+struct bitmap *bitmap_allocate(int n);
+void bitmap_free(struct bitmap *bm);
+BOOL bitmap_set(struct bitmap *bm, unsigned i);
+BOOL bitmap_clear(struct bitmap *bm, unsigned i);
+BOOL bitmap_query(struct bitmap *bm, unsigned i);
+int bitmap_find(struct bitmap *bm, unsigned ofs);
+
 /*The following definitions come from  lib/charcnv.c  */
 
 char *unix2dos_format(char *str,BOOL overwrite);
diff --git a/source3/include/smb.h b/source3/include/smb.h
index 3b562b9d13..e99eb30023 100644
--- a/source3/include/smb.h
+++ b/source3/include/smb.h
@@ -599,7 +599,6 @@ typedef struct files_struct
 	BOOL granted_oplock;
 	BOOL sent_oplock_break;
 	BOOL is_directory;
-	BOOL reserved;
 	char *fsp_name;
 } files_struct;
 
diff --git a/source3/lib/bitmap.c b/source3/lib/bitmap.c
index f67ea994e5..ab84a2a84e 100644
--- a/source3/lib/bitmap.c
+++ b/source3/lib/bitmap.c
@@ -43,7 +43,7 @@ struct bitmap *bitmap_allocate(int n)
 		return NULL;
 	}
 
-	memset(bm->b, 0, sizeof(bm->b[0])*bm->n);
+	memset(bm->b, 0, sizeof(bm->b[0])*(n+31)/32);
 
 	return bm;
 }
@@ -70,6 +70,16 @@ BOOL bitmap_set(struct bitmap *bm, unsigned i)
 }
 
 /****************************************************************************
+clear a bit in a bitmap
+****************************************************************************/
+BOOL bitmap_clear(struct bitmap *bm, unsigned i)
+{
+	if (i >= bm->n) return False;
+	bm->b[i/32] &= ~(1<<(i%32));
+	return True;
+}
+
+/****************************************************************************
 query a bit in a bitmap
 ****************************************************************************/
 BOOL bitmap_query(struct bitmap *bm, unsigned i)
diff --git a/source3/smbd/files.c b/source3/smbd/files.c
index 04aff67a15..66fbaebeb0 100644
--- a/source3/smbd/files.c
+++ b/source3/smbd/files.c
@@ -23,20 +23,23 @@
 
 extern int DEBUGLEVEL;
 
-#define MAX_OPEN_FILES 100
+/* the only restriction is that this must be less than PIPE_HANDLE_OFFSET */
+#define MAX_FNUMS 4096
 
-#define MAX_FNUMS (MAX_OPEN_FILES+MAX_OPEN_DIRECTORIES)
 #define VALID_FNUM(fnum)   (((fnum) >= 0) && ((fnum) < MAX_FNUMS))
 
-static files_struct Files[MAX_FNUMS];
+static struct bitmap *file_bmap;
+static struct bitmap *fd_bmap;
+
+static files_struct *Files;
 
 /*
  * Indirection for file fd's. Needed as POSIX locking
  * is based on file/process, not fd/process.
  */
-static file_fd_struct FileFd[MAX_OPEN_FILES];
-static int max_file_fd_used = 0;
+static file_fd_struct *FileFd;
 
+static int files_used, fd_ptr_used;
 
 /****************************************************************************
   find first available file slot
@@ -45,6 +48,7 @@ files_struct *file_new(void )
 {
 	int i;
 	static int first_file;
+	files_struct *fsp;
 
 	/* we want to give out file handles differently on each new
 	   connection because of a common bug in MS clients where they try to
@@ -56,59 +60,55 @@ files_struct *file_new(void )
 		if (first_file == 0) first_file = 1;
 	}
 
-	if (first_file >= MAX_FNUMS)
+	if (first_file >= MAX_FNUMS) {
 		first_file = 1;
+	}
 
-	for (i=first_file;i<MAX_FNUMS;i++)
-		if (!Files[i].open && !Files[i].reserved) {
-			memset(&Files[i], 0, sizeof(Files[i]));
-			first_file = i+1;
-			Files[i].reserved = True;
-			Files[i].fnum = i;
-			return &Files[i];
+	i = bitmap_find(file_bmap, first_file);
+	if (i == -1) {
+		/* 
+		 * Before we give up, go through the open files 
+		 * and see if there are any files opened with a
+		 * batch oplock. If so break the oplock and then
+		 * re-use that entry (if it becomes closed).
+		 * This may help as NT/95 clients tend to keep
+		 * files batch oplocked for quite a long time
+		 * after they have finished with them.
+		 */
+		for (fsp=Files;fsp;fsp=fsp->next) {
+			if (attempt_close_oplocked_file(fsp)) {
+				return file_new();
+			}
 		}
 
-	/* returning a file handle of 0 is a bad idea - so we start at 1 */
-	for (i=1;i<first_file;i++)
-		if (!Files[i].open && !Files[i].reserved) {
-			memset(&Files[i], 0, sizeof(Files[i]));
-			first_file = i+1;
-			Files[i].reserved = True;
-			Files[i].fnum = i;
-			return &Files[i];
-		}
+		DEBUG(0,("ERROR! Out of file structures\n"));
+		return NULL;
+	}
 
-        /* 
-         * Before we give up, go through the open files 
-         * and see if there are any files opened with a
-         * batch oplock. If so break the oplock and then
-         * re-use that entry (if it becomes closed).
-         * This may help as NT/95 clients tend to keep
-         * files batch oplocked for quite a long time
-         * after they have finished with them.
-         */
-        for (i=first_file;i<MAX_FNUMS;i++) {
-          if(attempt_close_oplocked_file( &Files[i])) {
-            memset(&Files[i], 0, sizeof(Files[i]));
-            first_file = i+1;
-            Files[i].reserved = True;
-	    Files[i].fnum = i;
-	    return &Files[i];
-          }
-        }
-
-        for (i=1;i<MAX_FNUMS;i++) {
-          if(attempt_close_oplocked_file( &Files[i])) {
-            memset(&Files[i], 0, sizeof(Files[i]));
-            first_file = i+1;
-            Files[i].reserved = True;
-	    Files[i].fnum = i;
-	    return &Files[i];
-          }
-        }
-
-	DEBUG(1,("ERROR! Out of file structures - perhaps increase MAX_OPEN_FILES?\n"));
-	return NULL;
+	fsp = (files_struct *)malloc(sizeof(*fsp));
+	if (!fsp) return NULL;
+
+	memset(fsp, 0, sizeof(*fsp));
+	first_file = i+1;
+	fsp->fnum = i;
+	string_init(&fsp->fsp_name,"");
+
+	bitmap_set(file_bmap, i);
+	files_used++;
+	
+	/* hook into the front of the list */
+	if (!Files) {
+		Files = fsp;
+	} else {
+		Files->prev = fsp;
+		fsp->next = Files;
+		Files = fsp;
+	}
+
+	DEBUG(5,("allocated file structure %d (%d used)\n",
+		 i, files_used));
+	
+	return fsp;
 }
 
 
@@ -119,60 +119,74 @@ and inode - increments the ref_count of the returned file_fd_struct *.
 ****************************************************************************/
 file_fd_struct *fd_get_already_open(struct stat *sbuf)
 {
-  int i;
-  file_fd_struct *fd_ptr;
-
-  if(sbuf == 0)
-    return 0;
-
-  for(i = 0; i <= max_file_fd_used; i++) {
-    fd_ptr = &FileFd[i];
-    if((fd_ptr->ref_count > 0) &&
-       (((uint32)sbuf->st_dev) == fd_ptr->dev) &&
-       (((uint32)sbuf->st_ino) == fd_ptr->inode)) {
-      fd_ptr->ref_count++;
-      DEBUG(3,
-       ("Re-used file_fd_struct %d, dev = %x, inode = %x, ref_count = %d\n",
-        i, fd_ptr->dev, fd_ptr->inode, fd_ptr->ref_count));
-      return fd_ptr;
-    }
-  }
-  return 0;
+	file_fd_struct *fd_ptr;
+
+	if(!sbuf) return NULL;
+
+	for (fd_ptr=FileFd;fd_ptr;fd_ptr=fd_ptr->next) {
+		if ((fd_ptr->ref_count > 0) &&
+		    (((uint32)sbuf->st_dev) == fd_ptr->dev) &&
+		    (((uint32)sbuf->st_ino) == fd_ptr->inode)) {
+			fd_ptr->ref_count++;
+			DEBUG(3,("Re-used file_fd_struct dev = %x, inode = %x, ref_count = %d\n",
+				 fd_ptr->dev, fd_ptr->inode, 
+				 fd_ptr->ref_count));
+			return fd_ptr;
+		}
+	}
+
+	return NULL;
 }
 
+
+
 /****************************************************************************
 fd support routines - attempt to find a empty slot in the FileFd array.
 Increments the ref_count of the returned entry.
 ****************************************************************************/
 file_fd_struct *fd_get_new(void)
 {
-  extern struct current_user current_user;
-  int i;
-  file_fd_struct *fd_ptr;
-
-  for(i = 0; i < MAX_OPEN_FILES; i++) {
-    fd_ptr = &FileFd[i];
-    if(fd_ptr->ref_count == 0) {
-      fd_ptr->dev = (uint32)-1;
-      fd_ptr->inode = (uint32)-1;
-      fd_ptr->fd = -1;
-      fd_ptr->fd_readonly = -1;
-      fd_ptr->fd_writeonly = -1;
-      fd_ptr->real_open_flags = -1;
-      fd_ptr->uid_cache_count = 0;
-      fd_add_to_uid_cache(fd_ptr, (uid_t)current_user.uid);
-      fd_ptr->ref_count++;
-      /* Increment max used counter if neccessary, cuts down
-         on search time when re-using */
-      if(i > max_file_fd_used)
-        max_file_fd_used = i;
-      DEBUG(3,("Allocated new file_fd_struct %d, dev = %x, inode = %x\n",
-               i, fd_ptr->dev, fd_ptr->inode));
-      return fd_ptr;
-    }
-  }
-  DEBUG(1,("ERROR! Out of file_fd structures - perhaps increase MAX_OPEN_FILES?\n"));
-  return 0;
+	extern struct current_user current_user;
+	int i;
+	file_fd_struct *fd_ptr;
+
+	i = bitmap_find(fd_bmap, 1);
+	if (i == -1) {
+		DEBUG(0,("ERROR! Out of file_fd structures\n"));
+		return NULL;
+	}
+
+	fd_ptr = (file_fd_struct *)malloc(sizeof(*fd_ptr));
+	if (!fd_ptr) return NULL;
+	
+	memset(fd_ptr, 0, sizeof(*fd_ptr));
+	
+	fd_ptr->fdnum = i;
+	fd_ptr->dev = (uint32)-1;
+	fd_ptr->inode = (uint32)-1;
+	fd_ptr->fd = -1;
+	fd_ptr->fd_readonly = -1;
+	fd_ptr->fd_writeonly = -1;
+	fd_ptr->real_open_flags = -1;
+	fd_add_to_uid_cache(fd_ptr, (uid_t)current_user.uid);
+	fd_ptr->ref_count++;
+
+	bitmap_set(fd_bmap, i);
+	fd_ptr_used++;
+
+	/* hook into the front of the list */
+	if (!FileFd) {
+		FileFd = fd_ptr;
+	} else {
+		FileFd->prev = fd_ptr;
+		fd_ptr->next = FileFd;
+		FileFd = fd_ptr;
+	}
+
+	DEBUG(5,("allocated fd_ptr structure %d (%d used)\n",
+		 i, fd_ptr_used));
+
+	return fd_ptr;
 }
 
 
@@ -181,14 +195,16 @@ close all open files for a connection
 ****************************************************************************/
 void file_close_conn(connection_struct *conn)
 {
-  int i;
-  for (i=0;i<MAX_FNUMS;i++)
-    if (Files[i].conn == conn && Files[i].open) {
-      if(Files[i].is_directory)
-        close_directory(&Files[i]); 
-      else                  
-        close_file(&Files[i],False); 
-    }
+	files_struct *fsp;
+	
+	for (fsp=Files;fsp;fsp=fsp->next) {
+		if (fsp->conn == conn && fsp->open) {
+			if (fsp->is_directory)
+				close_directory(fsp); 
+			else                  
+				close_file(fsp,False); 
+		}
+	}
 }
 
 /****************************************************************************
@@ -196,10 +212,14 @@ initialise file structures
 ****************************************************************************/
 void file_init(void)
 {
-	int i;
+	file_bmap = bitmap_allocate(MAX_FNUMS);
+	fd_bmap = bitmap_allocate(MAX_FNUMS);
+
+	if (!file_bmap || !fd_bmap) {
+		exit_server("out of memory in file_init");
+	}
 
-#ifdef HAVE_GETRLIMIT
-#ifdef RLIMIT_NOFILE
+#if (defined(HAVE_GETRLIMIT) && defined(RLIMIT_NOFILE))
 	{
 		struct rlimit rlp;
 		getrlimit(RLIMIT_NOFILE, &rlp);
@@ -215,34 +235,23 @@ void file_init(void)
 			 (int)rlp.rlim_cur));
 	}
 #endif
-#endif
-
-  
-
-	for (i=0;i<MAX_FNUMS;i++) {
-		Files[i].open = False;
-		string_init(&Files[i].fsp_name,"");
-	}
-
-	for (i=0;i<MAX_OPEN_FILES;i++) {
-		file_fd_struct *fd_ptr = &FileFd[i];
-		fd_ptr->ref_count = 0;
-		fd_ptr->dev = (int32)-1;
-		fd_ptr->inode = (int32)-1;
-		fd_ptr->fd = -1;
-		fd_ptr->fd_readonly = -1;
-		fd_ptr->fd_writeonly = -1;
-		fd_ptr->real_open_flags = -1;
-	}
 }
 
+
 /****************************************************************************
 find a fsp given a fnum
 ****************************************************************************/
 files_struct *file_fsp(int fnum)
 {
+	files_struct *fsp;
+
 	if (!VALID_FNUM(fnum)) return NULL;
-	return &Files[fnum];
+	
+	for (fsp=Files;fsp;fsp=fsp->next) {
+		if (fsp->fnum == fnum) return fsp;
+	}
+
+	return NULL;
 }
 
 
@@ -251,9 +260,9 @@ close files open by a specified vuid
 ****************************************************************************/
 void file_close_user(int vuid)
 {
-	int i;
-	for (i=0;i<MAX_FNUMS;i++) {
-		files_struct *fsp = &Files[i];
+	files_struct *fsp;
+
+	for (fsp=Files;fsp;fsp=fsp->next) {
 		if ((fsp->vuid == vuid) && fsp->open) {
 			if(!fsp->is_directory)
 				close_file(fsp,False);
@@ -269,9 +278,9 @@ find a fsp given a device, inode and timevalue
 ****************************************************************************/
 files_struct *file_find_dit(int dev, int inode, struct timeval *tval)
 {
-	int i;
-	for (i=0;i<MAX_FNUMS;i++) {
-		files_struct *fsp = &Files[i];
+	files_struct *fsp;
+
+	for (fsp=Files;fsp;fsp=fsp->next) {
 		if (fsp->open && 
 		    fsp->fd_ptr->dev == dev && 
 		    fsp->fd_ptr->inode == inode &&
@@ -279,22 +288,21 @@ files_struct *file_find_dit(int dev, int inode, struct timeval *tval)
 		    fsp->open_time.tv_usec == tval->tv_usec) {
 			return fsp;
 		}
-	} 
+	}
+
 	return NULL;
 }
 
+
 /****************************************************************************
 find a fsp that is open for printing
 ****************************************************************************/
 files_struct *file_find_print(void)
 {
-	int i;
+	files_struct *fsp;
 
-	for (i=0;i<MAX_FNUMS;i++) {
-		files_struct *fsp = &Files[i];
-		if (fsp->open && fsp->print_file) {
-			return fsp;
-		}
+	for (fsp=Files;fsp;fsp=fsp->next) {
+		if (fsp->open && fsp->print_file) return fsp;
 	} 
 	return NULL;
 }
@@ -305,9 +313,9 @@ sync open files on a connection
 ****************************************************************************/
 void file_sync_all(connection_struct *conn)
 {
-	int i;
-	for (i=0;i<MAX_FNUMS;i++) {
-		files_struct *fsp = &Files[i];
+	files_struct *fsp;
+
+	for (fsp=Files;fsp;fsp=fsp->next) {
 		if (fsp->open && conn == fsp->conn) {
 			sync_file(conn,fsp);
 		}
@@ -315,7 +323,60 @@ void file_sync_all(connection_struct *conn)
 }
 
 
+/****************************************************************************
+free up a fd_ptr
+****************************************************************************/
+static void fd_ptr_free(file_fd_struct *fd_ptr)
+{
+	if (fd_ptr == FileFd) {
+		FileFd = fd_ptr->next;
+		if (FileFd) FileFd->prev = NULL;
+	} else {
+		fd_ptr->prev->next = fd_ptr->next;
+		if (fd_ptr->next) fd_ptr->next->prev = fd_ptr->prev;
+	}
+
+	bitmap_clear(fd_bmap, fd_ptr->fdnum);
+	fd_ptr_used--;
+
+	DEBUG(5,("freed fd_ptr structure %d (%d used)\n",
+		 fd_ptr->fdnum, fd_ptr_used));
+
+	/* paranoia */
+	memset(fd_ptr, 0, sizeof(*fd_ptr));
+
+	free(fd_ptr);
+}
+
+
+/****************************************************************************
+free up a fsp
+****************************************************************************/
 void file_free(files_struct *fsp)
 {
+	if (fsp == Files) {
+		Files = fsp->next;
+		if (Files) Files->prev = NULL;
+	} else {
+		fsp->prev->next = fsp->next;
+		if (fsp->next) fsp->next->prev = fsp->prev;
+	}
+
+	string_free(&fsp->fsp_name);
+
+	if (fsp->fd_ptr && fsp->fd_ptr->ref_count == 0) {
+		fd_ptr_free(fsp->fd_ptr);
+	}
+
+	bitmap_clear(file_bmap, fsp->fnum);
+	files_used--;
+
+	DEBUG(5,("freed files structure %d (%d used)\n",
+		 fsp->fnum, files_used));
+
+	/* this is paranoia, just in case someone tries to reuse the 
+	   information */
 	memset(fsp, 0, sizeof(*fsp));
+
+	free(fsp);
 }
diff --git a/source3/smbd/nttrans.c b/source3/smbd/nttrans.c
index 0e76bf30b2..4778e3a66b 100644
--- a/source3/smbd/nttrans.c
+++ b/source3/smbd/nttrans.c
@@ -754,7 +754,7 @@ static int call_nt_transact_create(connection_struct *conn,
         unix_ERR_class = ERRDOS;
         unix_ERR_code = ERRbadpath;
       }
-      fsp->reserved = False;
+      file_free(fsp);
 
       restore_case_semantics(file_attributes);
 
diff --git a/source3/smbd/reply.c b/source3/smbd/reply.c
index 340602d3a5..e62c0bd576 100644
--- a/source3/smbd/reply.c
+++ b/source3/smbd/reply.c
@@ -3279,7 +3279,7 @@ static BOOL copy_file(char *src,char *dest1,connection_struct *conn, int ofun,
 		   1,0,0,&Access,&action);
 
   if (!fsp1->open) {
-	  fsp1->reserved = False;
+	  file_free(fsp1);
 	  return(False);
   }
 
@@ -3296,7 +3296,7 @@ static BOOL copy_file(char *src,char *dest1,connection_struct *conn, int ofun,
 
   if (!fsp2->open) {
     close_file(fsp1,False);
-    fsp2->reserved = False;
+    file_free(fsp2);
     return(False);
   }
 
diff --git a/source3/smbd/server.c b/source3/smbd/server.c
index e9aa2d0278..1ae402b902 100644
--- a/source3/smbd/server.c
+++ b/source3/smbd/server.c
@@ -885,8 +885,9 @@ static int fd_attempt_close(file_fd_struct *fd_ptr)
       fd_ptr->dev = (uint32)-1;
       fd_ptr->inode = (uint32)-1;
       fd_ptr->uid_cache_count = 0;
-    } else
+    } else {
       fd_remove_from_uid_cache(fd_ptr, (uid_t)current_user.uid);
+    }
   } 
  return fd_ptr->ref_count;
 }
@@ -1308,7 +1309,6 @@ static void close_filestruct(files_struct *fsp)
 {   
 	connection_struct *conn = fsp->conn;
     
-	fsp->reserved = False;
 	fsp->open = False;
 	fsp->is_directory = False;