From 72ed7049d88e5296ebec362189e62a384385ad34 Mon Sep 17 00:00:00 2001 From: Andrew Tridgell Date: Mon, 17 Aug 1998 06:47:53 +0000 Subject: added some optimisation for the case where the number of open files is very large. files.c now promotes a files_struct to the top of the list if it is used when it is more than 10 elements from the top. also moved common linked list code for the 5 sets of linked lists that I've created over the past few days into dlinklist.h (I've explained to Chris why I didn't use the ubiqx code) (This used to be commit 1eb9ae2996b5a243a147f485e7e353d54f820852) --- source3/include/dlinklist.h | 52 +++++++++++++++++++++++++++++++++++++++ source3/include/includes.h | 2 ++ source3/lib/util_hnd.c | 17 ++----------- source3/rpc_server/srv_lsa_hnd.c | 17 ++----------- source3/rpc_server/srv_pipe_hnd.c | 17 ++----------- source3/smbd/conn.c | 27 ++++++++------------ source3/smbd/files.c | 47 +++++++++++------------------------ 7 files changed, 84 insertions(+), 95 deletions(-) create mode 100644 source3/include/dlinklist.h diff --git a/source3/include/dlinklist.h b/source3/include/dlinklist.h new file mode 100644 index 0000000000..8810eca5b9 --- /dev/null +++ b/source3/include/dlinklist.h @@ -0,0 +1,52 @@ +/* + Unix SMB/Netbios implementation. + Version 1.9. + some simple double linked list macros + Copyright (C) Andrew Tridgell 1998 + + 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. +*/ + +/* To use these macros you must have a structure containing a next and + prev pointer */ + + +/* hook into the front of the list */ +#define DLIST_ADD(list, p) \ + if (!(list)) { \ + (list) = (p); \ + (p)->next = (p)->prev = NULL; \ + } else { \ + (list)->prev = (p); \ + (p)->next = (list); \ + (p)->prev = NULL; \ + (list) = (p); \ + } + + +/* remove an element from a list */ +#define DLIST_REMOVE(list, p) \ + if ((p) == (list)) { \ + (list) = (p)->next; \ + if (list) (list)->prev = NULL; \ + } else { \ + (p)->prev->next = (p)->next; \ + if ((p)->next) (p)->next->prev = (p)->prev; \ + } + +/* promote an element to the top of the list */ +#define DLIST_PROMOTE(list, p) \ + DLIST_REMOVE(list, p) \ + DLIST_ADD(list, p) diff --git a/source3/include/includes.h b/source3/include/includes.h index 4ced157359..3fd5f7be08 100644 --- a/source3/include/includes.h +++ b/source3/include/includes.h @@ -314,6 +314,8 @@ extern int errno; /* Lists, trees, caching, datbase... */ #include "ubi_sLinkList.h" #include "ubi_dLinkList.h" +#include "dlinklist.h" + #ifndef UBI_BINTREE_H #include "ubi_Cache.h" #endif /* UBI_BINTREE_H */ diff --git a/source3/lib/util_hnd.c b/source3/lib/util_hnd.c index 2fc2c73ea3..d65116e646 100644 --- a/source3/lib/util_hnd.c +++ b/source3/lib/util_hnd.c @@ -124,14 +124,7 @@ BOOL open_lsa_policy_hnd(POLICY_HND *hnd) bitmap_set(bmap, i); - /* hook into the front of the list */ - if (!Policy) { - Policy = p; - } else { - Policy->prev = p; - p->next = Policy; - Policy = p; - } + DLIST_ADD(Policy, p); DEBUG(4,("Opened policy hnd[%x] ", i)); dump_data(4, (char *)hnd->data, sizeof(hnd->data)); @@ -303,13 +296,7 @@ BOOL close_lsa_policy_hnd(POLICY_HND *hnd) DEBUG(3,("Closed policy name pnum=%x\n", p->pnum)); - if (p == Policy) { - Policy = p->next; - if (Policy) Policy->prev = NULL; - } else { - p->prev->next = p->next; - if (p->next) p->next->prev = p->prev; - } + DLIST_REMOVE(Policy, p); bitmap_clear(bmap, p->pnum); diff --git a/source3/rpc_server/srv_lsa_hnd.c b/source3/rpc_server/srv_lsa_hnd.c index 2fc2c73ea3..d65116e646 100644 --- a/source3/rpc_server/srv_lsa_hnd.c +++ b/source3/rpc_server/srv_lsa_hnd.c @@ -124,14 +124,7 @@ BOOL open_lsa_policy_hnd(POLICY_HND *hnd) bitmap_set(bmap, i); - /* hook into the front of the list */ - if (!Policy) { - Policy = p; - } else { - Policy->prev = p; - p->next = Policy; - Policy = p; - } + DLIST_ADD(Policy, p); DEBUG(4,("Opened policy hnd[%x] ", i)); dump_data(4, (char *)hnd->data, sizeof(hnd->data)); @@ -303,13 +296,7 @@ BOOL close_lsa_policy_hnd(POLICY_HND *hnd) DEBUG(3,("Closed policy name pnum=%x\n", p->pnum)); - if (p == Policy) { - Policy = p->next; - if (Policy) Policy->prev = NULL; - } else { - p->prev->next = p->next; - if (p->next) p->next->prev = p->prev; - } + DLIST_REMOVE(Policy, p); bitmap_clear(bmap, p->pnum); diff --git a/source3/rpc_server/srv_pipe_hnd.c b/source3/rpc_server/srv_pipe_hnd.c index 368bf013a0..b030ee0e90 100644 --- a/source3/rpc_server/srv_pipe_hnd.c +++ b/source3/rpc_server/srv_pipe_hnd.c @@ -91,14 +91,7 @@ pipes_struct *open_rpc_pipe_p(char *pipe_name, p = (pipes_struct *)malloc(sizeof(*p)); if (!p) return NULL; - /* hook into the front of the list */ - if (!Pipes) { - Pipes = p; - } else { - Pipes->prev = p; - p->next = Pipes; - Pipes = p; - } + DLIST_ADD(Pipes, p); bitmap_set(bmap, i); i += PIPE_HANDLE_OFFSET; @@ -292,13 +285,7 @@ BOOL close_rpc_pipe_hnd(pipes_struct *p, connection_struct *conn) DEBUG(4,("closed pipe name %s pnum=%x (pipes_open=%d)\n", p->name, p->pnum, pipes_open)); - if (p == Pipes) { - Pipes = p->next; - if (Pipes) Pipes->prev = NULL; - } else { - p->prev->next = p->next; - if (p->next) p->next->prev = p->prev; - } + DLIST_REMOVE(Pipes, p); memset(p, 0, sizeof(*p)); diff --git a/source3/smbd/conn.c b/source3/smbd/conn.c index b110e8d082..2afbfb7d7e 100644 --- a/source3/smbd/conn.c +++ b/source3/smbd/conn.c @@ -72,10 +72,16 @@ find a conn given a cnum ****************************************************************************/ connection_struct *conn_find(int cnum) { + int count=0; connection_struct *conn; - for (conn=Connections;conn;conn=conn->next) { - if (conn->cnum == cnum) return conn; + for (conn=Connections;conn;conn=conn->next,count++) { + if (conn->cnum == cnum) { + if (count > 10) { + DLIST_PROMOTE(Connections, conn); + } + return conn; + } } return NULL; @@ -114,14 +120,7 @@ connection_struct *conn_new(void) string_init(&conn->connectpath,""); string_init(&conn->origpath,""); - /* hook into the front of the list */ - if (!Connections) { - Connections = conn; - } else { - Connections->prev = conn; - conn->next = Connections; - Connections = conn; - } + DLIST_ADD(Connections, conn); return conn; } @@ -165,13 +164,7 @@ free a conn structure ****************************************************************************/ void conn_free(connection_struct *conn) { - if (conn == Connections) { - Connections = conn->next; - if (Connections) Connections->prev = NULL; - } else { - conn->prev->next = conn->next; - if (conn->next) conn->next->prev = conn->prev; - } + DLIST_REMOVE(Connections, conn); if (conn->ngroups && conn->groups) { free(conn->groups); diff --git a/source3/smbd/files.c b/source3/smbd/files.c index 7bd5501de5..fa1b8f3bac 100644 --- a/source3/smbd/files.c +++ b/source3/smbd/files.c @@ -100,14 +100,7 @@ files_struct *file_new(void ) fsp->fnum = i + FILE_HANDLE_OFFSET; string_init(&fsp->fsp_name,""); - /* hook into the front of the list */ - if (!Files) { - Files = fsp; - } else { - Files->prev = fsp; - fsp->next = Files; - Files = fsp; - } + DLIST_ADD(Files, fsp); DEBUG(5,("allocated file structure %d (%d used)\n", i, files_used)); @@ -180,14 +173,7 @@ file_fd_struct *fd_get_new(void) 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; - } + DLIST_ADD(FileFd, fd_ptr); DEBUG(5,("allocated fd_ptr structure %d (%d used)\n", i, fd_ptr_used)); @@ -269,14 +255,18 @@ find a fsp given a device, inode and timevalue ****************************************************************************/ files_struct *file_find_dit(int dev, int inode, struct timeval *tval) { + int count=0; files_struct *fsp; - for (fsp=Files;fsp;fsp=fsp->next) { + for (fsp=Files;fsp;fsp=fsp->next,count++) { if (fsp->open && fsp->fd_ptr->dev == dev && fsp->fd_ptr->inode == inode && fsp->open_time.tv_sec == tval->tv_sec && fsp->open_time.tv_usec == tval->tv_usec) { + if (count > 10) { + DLIST_PROMOTE(Files, fsp); + } return fsp; } } @@ -320,13 +310,7 @@ 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; - } + DLIST_REMOVE(FileFd, fd_ptr); bitmap_clear(fd_bmap, fd_ptr->fdnum); fd_ptr_used--; @@ -346,13 +330,7 @@ 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; - } + DLIST_REMOVE(Files, fsp); string_free(&fsp->fsp_name); @@ -381,16 +359,19 @@ get a fsp from a packet given the offset of a 16 bit fnum ****************************************************************************/ files_struct *file_fsp(char *buf, int where) { - int fnum; + int fnum, count=0; files_struct *fsp; if (chain_fsp) return chain_fsp; fnum = SVAL(buf, where); - for (fsp=Files;fsp;fsp=fsp->next) { + for (fsp=Files;fsp;fsp=fsp->next, count++) { if (fsp->fnum == fnum) { chain_fsp = fsp; + if (count > 10) { + DLIST_PROMOTE(Files, fsp); + } return fsp; } } -- cgit