*** empty log message ***
authorMatthew Mondor <mmondor@pulsar-zone.net>
Wed, 18 Jun 2003 01:15:20 +0000 (01:15 +0000)
committerMatthew Mondor <mmondor@pulsar-zone.net>
Wed, 18 Jun 2003 01:15:20 +0000 (01:15 +0000)
28 files changed:
mmsoftware/TODO
mmsoftware/install.sh
mmsoftware/mmftpd/ChangeLog
mmsoftware/mmftpd/install.sh
mmsoftware/mmftpd/src/mmftpd.c
mmsoftware/mmftpd/src/mmftpd.h
mmsoftware/mmlib/Makefile
mmsoftware/mmlib/makepart.sh
mmsoftware/mmlib/mmbstring.c
mmsoftware/mmlib/mmhash.3 [new file with mode: 0644]
mmsoftware/mmlib/mmhash.c [new file with mode: 0644]
mmsoftware/mmlib/mmhash.h [new file with mode: 0644]
mmsoftware/mmlib/mmlist.3
mmsoftware/mmlib/mmpool.3
mmsoftware/mmlib/mmserver.c
mmsoftware/mmlib/mmserver.h
mmsoftware/mmlib/mmstat.h
mmsoftware/mmlib/mmstring.c
mmsoftware/mmlib/mmstring.h
mmsoftware/mmmail/ChangeLog
mmsoftware/mmmail/install.sh
mmsoftware/mmmail/src/mmsmtpd/mmsmtpd.c
mmsoftware/mmmail/src/mmsmtpd/mmsmtpd.h
mmsoftware/mmstatd/ChangeLog
mmsoftware/mmstatd/install.sh
mmsoftware/mmstatd/src/mmstat.c
mmsoftware/mmstatd/src/mmstatd.c
mmsoftware/mmstatd/src/mmstatd.h

index 32a51f0..32a1be1 100644 (file)
@@ -1,10 +1,11 @@
-$Id: TODO,v 1.10 2003/06/04 06:00:16 mmondor Exp $
+$Id: TODO,v 1.11 2003/06/18 01:15:19 mmondor Exp $
 
 
 
 MMFTPD
 ======
 
+- Add support for mmsmtpd-like fail mmstat logs with per-ip info
 - Support admin-specified port ranges for passive connections which makes
   it much easier to setup mmftpd behind ipf
 
@@ -97,43 +98,6 @@ MMSTATD
   -v for verbose +d<dateformat> +c<columnsformat> etc...
   Or, defaults to the current format and:
   -h human etc...
-
-- BETTER KEY LOOKUP ALGORITHM
-  Since I started to more heavily use mmstatd and store alot of keys in it,
-  I noticed that the linear 64-bit hash lookup method which was originally
-  ideal for small registries started to consist of the main bottleneck of
-  the application. I use mmstatd to store keys based on automatic on-the-fly
-  apache log parsing for instance, and log statistics about file transfers
-  and bytes transfered for many virtualhosts.
-  It would be nice if the key lookup method of mmstatd was more efficient when
-  used with a very large registry. Various methods would be possible to
-  improve it's performance:
-  - Separate '.' separated elements and store them in a tree hierarchy.
-    Although this could help to narrow down the search, it still would be
-    nice to use a hashing system to lookup through the nodes of the same
-    sublevel.
-  - If a range-determined hash algorithm was used, with the possibility of
-    more collisions however, it would be possible to map an index to locate
-    the key node quickly. However, because of collisions, buckets would need
-    to be used.
-  - It would be possible to maintain a btree for the characters of each
-    node of a key, so that we could easily determine pre-existance of a
-    key, etc. So we would have a tree of dot separated nodes, and a tree
-    of node name for each. However, lookup, insert, removal and rename
-    operations could be tricky and actually be slow if not properly
-    implemented. Also, the memory requirements to store the keys in
-    memory could become larger.
-  - Using a general purpose storage library like db3/4 would be very easy.
-    However, as it only deals with key/data pairs, it would most likely not
-    be ideal with very large registries. I beleive that a method especially
-    designed with the current system in mind could be more efficient. Moreover,
-    as mmstatd already handles a recovery log, db library's would not be
-    necessary. Also, because all atomic transactions are performed sequencially
-    by the same process, no special synchronization is required (another of
-    nice db features).
-  - Using mysql would be suboptimal, and would require a huge dependancy which
-    alot of software are happy to avoid.
-
 - It is possible that in the future mmstat key nodes be separated by '/'
   instead of '.' which is a character which we may want to store in a node
   name (i.e. a filename).
index 7f98805..bbf73cd 100755 (executable)
@@ -1,5 +1,5 @@
 #!/bin/sh
-# $Id: install.sh,v 1.6 2003/03/28 21:09:28 mmondor Exp $
+# $Id: install.sh,v 1.7 2003/06/18 01:15:20 mmondor Exp $
 
 if [ "$1" = "help" ]; then
        echo
@@ -116,6 +116,7 @@ instman mmlist.3 3
 instman mmpool.3 3
 instman mmpath.3 3
 instman mmstat.3 3
+instman mmhash.3 3
 cd ../
 
 cd mmpasswd/
@@ -184,7 +185,7 @@ echo "mmftpd users: mmftpd(8), mmftpd.conf(5), mmftpdpasswd(5)"
 echo "mmmail users: mmmail(8), mmsmtpd(8), mmsmtpd.conf(5), mmpop3d(8),"
 echo "              mmpop3d.conf(5)"
 echo "source auditors: mmstat(3), mmfd(3), mmlist(3), mmpool(3), mmfifo(3),"
-echo "                 mmlifo(3), mmpath(3)"
+echo "                 mmlifo(3), mmpath(3), mmhash(3)"
 echo
 echo "Thank you for using mmsoftware."
 echo
index 0e09155..064cf34 100644 (file)
@@ -1,21 +1,26 @@
-$Id: ChangeLog,v 1.14 2003/06/04 06:00:16 mmondor Exp $
+$Id: ChangeLog,v 1.15 2003/06/18 01:15:20 mmondor Exp $
 
 
 
 Release: mmftpd 0.0.16 devl
-Date   : April 25, 2003
+Date   : June 16, 2003
 By     : Matthew Mondor
 
-* Fix requireing a minor configuration file change
-  - The GROUPS directive now expects groups to be comma-separated instead of
-    space-separated. The quotes then of course also become optional if multiple
-    groups are specified. This was made because that mmreadcfg(3) library is
-    also used by other of my projects for which comma-separated groups were
-    required.
+* Important
+  - Important changes to mmstat(3) and mmstatd(8) were made which require a
+    database synchronization procedure to be performed before upgrading.
+    See mmstatd/ChangeLog for details.
+  - The GROUPS directive in mmftpd.conf(5) and mmstatd.conf(5) now expect
+    groups to be comma-separated instead of space-separated. The quotes then
+    of course also become optional if multiple groups are specified. This was
+    made because mmreadcfg(3) library is also used by other of my projects for
+    which comma-separated groups were also required.
 * Miscelaneous new features
   - When user has no rights to modify or upload (i.e. usually anonymous user)
     all files now appear as read-only and non-executable, and directories
     as read-only, when using LIST.
+  - mmftpd now reports the number of bytes transfered in both directions for
+    each user via the mmstat facility.
 * Bug fixes
   - Fixed ALIGN_CEIL alignment macros which used to always add bytes even
     if the value was already aligned properly. A few bytes were often wasted
@@ -39,6 +44,15 @@ By     : Matthew Mondor
   - Where appropriate and possible, const keyword was added to the function
     parameters and global data types.
   - Some more source cleanups
+  - mmstatd will now perform much better when used with a large number of
+    keys, and will now retain the real time of the operation if it had to
+    be killed before it can incorporate the recovery logs and sync.
+  - Now uses mmhash(3) for user lookup which should make mmftpd faster when
+    many simultaneous users are logged in at the same time (this is used to
+    verify user login limits and link a new user to the shared tree quota
+    structure).
+  - mmhash(3) is now used by mmserver(3) as well, which should enhance
+    connection validity and DNS hostname cache performance.
 
 
 
index 59954e0..b6c0543 100755 (executable)
@@ -1,5 +1,5 @@
 #!/bin/sh
-# $Id: install.sh,v 1.5 2003/05/01 02:06:22 mmondor Exp $
+# $Id: install.sh,v 1.6 2003/06/18 01:15:20 mmondor Exp $
 
 if [ "$1" = "help" ]; then
        echo
@@ -102,6 +102,7 @@ instman mmlist.3 3
 instman mmpool.3 3
 instman mmpath.3 3
 instman mmstat.3 3
+instman mmhash.3 3
 cd ../
 
 cd mmpasswd/
@@ -146,7 +147,7 @@ echo
 echo "mmstat(8), mmstatd(8), mmstatd.conf(5) mmpasswd(8)"
 echo "mmftpd(8), mmftpd.conf(5), mmftpdpasswd(5)"
 echo "source auditors: mmstat(3), mmfd(3), mmlist(3), mmpool(3), mmfifo(3),"
-echo "                 mmpath(3)"
+echo "                 mmpath(3), mmhash(3)"
 echo
 echo "Thank you for using mmsoftware."
 echo
index 50435eb..8402169 100644 (file)
@@ -1,4 +1,4 @@
-/* $Id: mmftpd.c,v 1.19 2003/06/04 06:00:16 mmondor Exp $ */
+/* $Id: mmftpd.c,v 1.20 2003/06/18 01:15:20 mmondor Exp $ */
 
 /*
  * Copyright (C) 2002-2003, Matthew Mondor
@@ -66,6 +66,7 @@
 #include <mmfd.h>
 #include <mmlist.h>
 #include <mmpool.h>
+#include <mmhash.h>
 #include <mmserver.h>
 #include <mmpath.h>
 #include <mmlog.h>
@@ -80,7 +81,7 @@
 
 MMCOPYRIGHT("@(#) Copyright (c) 2002-2003\n\
 \tMatthew Mondor. All rights reserved.\n");
-MMRCSID("$Id: mmftpd.c,v 1.19 2003/06/04 06:00:16 mmondor Exp $");
+MMRCSID("$Id: mmftpd.c,v 1.20 2003/06/18 01:15:20 mmondor Exp $");
 
 
 
@@ -110,14 +111,14 @@ static pth_attr_t tthreadattr;
 /* List of logged in users and optionally current home directory size */
 static pth_mutex_t lusers_lock;
 static pool_t plusers;
-static list_t lusers;
+static hashtable_t lusers;
 
 /* This is used so that clientenv structures be allocated/freed fast */
 static pth_mutex_t clenvs_lock;
 static pool_t pclenvs;
 static pool_t pfifos;
 
-/* Pool used to optimize creatiing/destroying mmfd mutexes */
+/* Pool used to optimize creating/destroying mmfd mutexes */
 static pth_mutex_t mutexes_lock;
 static pool_t pmutexes;
 
@@ -516,7 +517,6 @@ auth_pass(clientenv *clenv)
     int nextstate = STATE_CURRENT;
     fdbuf *fdb = clenv->fdb;
     char *pw;
-    u_int64_t uhash;
 
     if (!clenv->user && !clenv->tuser) {
 
@@ -599,6 +599,7 @@ auth_pass(clientenv *clenv)
      */
     if (nextstate == STATE_MAIN) {
        lusernode *lun;
+       size_t len;
 
        if (*CONF.MOTD_FILE) {
            reply(fdb, 230, TRUE, NULL);
@@ -611,13 +612,20 @@ auth_pass(clientenv *clenv)
        pth_mutex_acquire(&lusers_lock, FALSE, NULL);
 
        /* Verify if user in list */
-       for (lun = (lusernode *)&lusers.top, uhash = mm_strhash64(clenv->user);
-               lun; lun = (lusernode *)lun->node.node.next)
-           if (uhash == lun->hash) break;
-       if (lun) {
-           /* Yes, make sure we observe limits if any */
-           if (!clenv->maxlogins || lun->logins < clenv->maxlogins) {
-               lun->logins++;
+       len = mm_strlen(clenv->user);
+       if ((lun = (lusernode *)hashtable_find(&lusers, clenv->user, len + 1))
+               != NULL) {
+           bool lok = TRUE;
+           /* Yes, make sure that we observe limits, if any */
+           if (clenv->maxlogins != 0) {
+               pth_mutex_acquire(&lun->lock, FALSE, NULL);
+               if (lun->logins < clenv->maxlogins)
+                   lun->logins++;
+               else
+                   lok = FALSE;
+               pth_mutex_release(&lun->lock);
+           }
+           if (lok) {
                clenv->unode = lun;
                if (clenv->anonymous)
                    reply(fdb, 230, FALSE, "Restricted anonymous login ok");
@@ -629,13 +637,10 @@ auth_pass(clientenv *clenv)
                nextstate = STATE_CURRENT;
            }
        } else {
-           if (!clenv->maxlogins || 1 <= clenv->maxlogins) {
+           if (clenv->maxlogins == 0 || 1 <= clenv->maxlogins) {
                /* Add new user entry, and optionally record current tree size
                 */
                if ((lun = (lusernode *)pool_alloc(&plusers, FALSE))) {
-                   lun->hash = uhash;
-                   pth_mutex_init(&lun->lock);
-                   lun->logins = 1;
                    if (clenv->maxhomesize) {
                        if ((lun->homesize = treesize(clenv, clenv->home,
                                        clenv->minfilesize)) == -1) {
@@ -652,9 +657,13 @@ auth_pass(clientenv *clenv)
                            "* auth_pass() - pool_alloc(plusers)");
                    nextstate = STATE_ERROR;
                }
-               if (lun) {
+               if (lun != NULL) {
+                   pth_mutex_init(&lun->lock);
+                   lun->logins = 1;
+                   mm_memcpy(lun->user, clenv->user, len + 1);
                    clenv->unode = lun;
-                   LIST_APPEND(&lusers, (node_t *)lun);
+                   hashtable_link(&lusers, (hashnode_t *)lun, lun->user,
+                           len + 1);
                    if (clenv->anonymous)
                        reply(fdb, 230, FALSE,
                                "Restricted anonymous login ok");
@@ -2170,7 +2179,16 @@ main_stat(clientenv *clenv)
                        clenv->c_hostname, clenv->c_ipaddr);
        else
            fdbprintf(fdb, "    Connected to %s\r\n", clenv->c_ipaddr);
-       fdbprintf(fdb, "    Logged in as %s\r\n", clenv->user);
+
+       {
+           long logins;
+
+           pth_mutex_acquire(&clenv->unode->lock, FALSE, NULL);
+           logins = clenv->unode->logins;
+           pth_mutex_release(&clenv->unode->lock);
+           fdbprintf(fdb, "    Logged in as %s (%ld concurrent logins)\r\n",
+                   clenv->user, logins);
+       }
 
        fdbwrite(fdb, "    TYPE: ", 10);
        /* An index would not be worth it for three possibilities */
@@ -2466,7 +2484,8 @@ main(int argc, char **argv)
     /* User-shared state nodes */
     pool_init(&plusers, malloc, free, sizeof(lusernode),
            (32768 * CONF.ALLOC_BUFFERS) / sizeof(lusernode), 0, 0);
-    LIST_INIT(&lusers);
+    hashtable_init(&lusers, HT_DEFAULT_CAPACITY, HT_DEFAULT_FACTOR, malloc,
+           free, mm_memcmp, hashtable_hash);
     /* Mutexes pool for mmfd */
     pool_init(&pmutexes, malloc, free, sizeof(struct mutexnode),
            (16384 * CONF.ALLOC_BUFFERS) / sizeof(struct mutexnode), 0, 0);
@@ -2476,7 +2495,8 @@ main(int argc, char **argv)
                (CONF.REMEMBER_CWDS * sizeof(u_int64_t)),
                CONF.ALLOC_BUFFERS * 64, 0, 0);
 
-    if (POOL_VALID(&pclenvs) && POOL_VALID(&plusers) && POOL_VALID(&pmutexes)
+    if (POOL_VALID(&pclenvs) && POOL_VALID(&plusers) &&
+           HASHTABLE_VALID(&lusers) && POOL_VALID(&pmutexes)
            && (!*CONF.DISPLAY_FILE || POOL_VALID(&pfifos))) {
        fdbcinit(&gfdf, &fdbc, CONF.GBANDWIDTH_IN * 1024,
                CONF.GBANDWIDTH_OUT * 1024);
@@ -2496,6 +2516,7 @@ main(int argc, char **argv)
     if (POOL_VALID(&pfifos)) pool_destroy(&pfifos);
     if (POOL_VALID(&pmutexes)) pool_destroy(&pmutexes);
     if (POOL_VALID(&plusers)) pool_destroy(&plusers);
+    if (HASHTABLE_VALID(&lusers)) hashtable_destroy(&lusers, FALSE);
     if (POOL_VALID(&pclenvs)) pool_destroy(&pclenvs);
 
     exit(ret);
@@ -2811,10 +2832,15 @@ free_clientenv(clientenv *clenv)
     if (clenv->group) mmstrfree(clenv->group);
     if (clenv->rnfr) mmstrfree(clenv->rnfr);
     if (clenv->unode) {
+       bool zero = FALSE;
+
        pth_mutex_acquire(&lusers_lock, FALSE, NULL);
-       clenv->unode->logins--;
-       if (clenv->unode->logins < 1) {
-           LIST_UNLINK(&lusers, (node_t *)clenv->unode);
+       pth_mutex_acquire(&clenv->unode->lock, FALSE, NULL);
+       if ((--clenv->unode->logins) < 1)
+           zero = TRUE;
+       pth_mutex_release(&clenv->unode->lock);
+       if (zero) {
+           hashtable_unlink(&lusers, (hashnode_t *)clenv->unode, TRUE);
            /* May be required by some POSIX thread implementations */
            /* pth_mutex_destroy(&clenv->unode->lock); */
            pool_free((pnode_t *)clenv->unode);
@@ -2823,7 +2849,7 @@ free_clientenv(clientenv *clenv)
     }
 
     pth_mutex_acquire(&clenvs_lock, FALSE, NULL);
-    if (fnode) pool_free((pnode_t *)fnode);
+    if (fnode != NULL) pool_free((pnode_t *)fnode);
     pool_free((pnode_t *)clenv);
     pth_mutex_release(&clenvs_lock);
 
@@ -3195,9 +3221,14 @@ thread");
            control_out = FDBBYTESW(fdb);
 
            mmstat_transact(&clenv->vstat, TRUE);
-           if (clenv->login)
+           if (clenv->login) {
                mmstat(&clenv->vstat, STAT_UPDATE, -1, "mmftpd.who.%s",
                        clenv->user);
+               mmstat(&clenv->pstat, STAT_UPDATE, data_in + control_in,
+                       "mmftpd.%s.in", clenv->user);
+               mmstat(&clenv->pstat, STAT_UPDATE, data_out + control_out,
+                       "mmftpd.%s.out", clenv->user);
+           }
            mmstat(&clenv->vstat, STAT_UPDATE, -1,
                    "mmftpd.current.connections");
            mmstat_transact(&clenv->vstat, FALSE);
@@ -3207,6 +3238,12 @@ thread");
                    "mmftpd.total.downloads");
            mmstat(&clenv->pstat, STAT_UPDATE, ul_files,
                    "mmftpd.total.uploads");
+           if (clenv->login) {
+               mmstat(&clenv->pstat, STAT_UPDATE, dl_files,
+                       "mmftpd.%s.downloads", clenv->user);
+               mmstat(&clenv->pstat, STAT_UPDATE, ul_files,
+                       "mmftpd.%s.uploads", clenv->user);
+           }
            mmstat(&clenv->pstat, STAT_UPDATE, data_in,
                    "mmftpd.total.data-in");
            mmstat(&clenv->pstat, STAT_UPDATE, data_out,
index f333f97..fa4985b 100644 (file)
@@ -1,4 +1,4 @@
-/* $Id: mmftpd.h,v 1.11 2003/05/28 06:39:44 mmondor Exp $ */
+/* $Id: mmftpd.h,v 1.12 2003/06/18 01:15:20 mmondor Exp $ */
 
 /*
  * Copyright (C) 2000-2003, Matthew Mondor
@@ -50,6 +50,7 @@
 #include <mmserver.h>
 #include <mmlist.h>
 #include <mmpool.h>
+#include <mmhash.h>
 #include <mmfifo.h>
 #include <mmstat.h>
 #include <mmserver.h>
@@ -215,11 +216,11 @@ typedef struct clientenv {
  * to share a common current home directory size value.
  */
 typedef struct lusernode {
-    pnode_t node;
-    u_int64_t hash;              /* User name hash */
-    pth_mutex_t lock;            /* For treesize_edit() */
-    long logins;                 /* Simultanious current logins for user */
-    off_t homesize;              /* Current home directory size for user */
+    hashnode_t node;
+    char user[32];             /* User name (key) */
+    pth_mutex_t lock;          /* For treesize_edit() */
+    long logins;               /* Simultanious current logins for user */
+    off_t homesize;            /* Current home directory size for user */
 } lusernode;
 
 /* Used for mmfd thread support delegation/abstraction */
index abe6ca3..a4f4887 100644 (file)
@@ -1,4 +1,4 @@
-# $Id: Makefile,v 1.4 2003/03/28 21:09:29 mmondor Exp $
+# $Id: Makefile,v 1.5 2003/06/18 01:15:20 mmondor Exp $
 
 CC = gcc
 MAKE = make
@@ -14,7 +14,7 @@ PTH != $(ECHO) `pth-config --cflags`
 MYSQL != $(ECHO) `mysql_config --cflags`
 INCDIR = -I/usr/include -I/usr/local/include -I. $(PTH) $(MYSQL)
 
-OBJS = mmpool.o mmfd.o mmrc4.o mmserver.o mmpath.o mmlog.o mmstr.o mmsql.o mmreadcfg.o mmstring.o mmloadarray.o mmstat.o mmbstring.o
+OBJS = mmpool.o mmfd.o mmrc4.o mmserver.o mmpath.o mmlog.o mmstr.o mmsql.o mmreadcfg.o mmstring.o mmloadarray.o mmstat.o mmbstring.o mmhash.o
 
 CCOBJ = $(CC) $(CFLAGS) -c $(INCDIR)
 
@@ -70,3 +70,6 @@ mmstat.o:
 
 mmbstring.o:
        $(CCOBJ) mmbstring.c
+
+mmhash.o:
+       $(CCOBJ) mmhash.c
index a771f57..7461f8d 100755 (executable)
@@ -1,10 +1,10 @@
 #!/bin/sh
-# $Id: makepart.sh,v 1.4 2003/03/28 21:09:29 mmondor Exp $
+# $Id: makepart.sh,v 1.5 2003/06/18 01:15:20 mmondor Exp $
 
 . ./makedefs.sh
 
 OBJS="mmpool.o mmfd.o mmrc4.o mmserver.o mmpath.o mmlog.o mmstr.o \
-mmsql.o mmreadcfg.o mmstring.o mmloadarray.o mmstat.o mmbstring.o"
+mmsql.o mmreadcfg.o mmstring.o mmloadarray.o mmstat.o mmbstring.o mmhash.o"
 
 if [ "$1" = "clean" ]; then
        show $RM $OBJS libmmondor.a
index 7175aba..f5d38a4 100644 (file)
@@ -1,4 +1,4 @@
-/* $Id: mmbstring.c,v 1.1 2003/01/08 20:57:46 mmondor Exp $ */
+/* $Id: mmbstring.c,v 1.2 2003/06/18 01:15:20 mmondor Exp $ */
 
 /*
  * Copyright (C) 2001-2003, Matthew Mondor
@@ -51,7 +51,7 @@
 
 MMCOPYRIGHT("@(#) Copyright (c) 2002-2003\n\
 \tMatthew Mondor. All rights reserved.\n");
-MMRCSID("$Id: mmbstring.c,v 1.1 2003/01/08 20:57:46 mmondor Exp $");
+MMRCSID("$Id: mmbstring.c,v 1.2 2003/06/18 01:15:20 mmondor Exp $");
 
 
 
@@ -91,7 +91,7 @@ size_t bstrcat2(bstring *bstr, bstring *obstr)
 bool bstrcmp2(bstring *bstr, bstring *obstr)
 {
     if (bstr->len == obstr->len) {
-       return (mm_memcmp(bstr->string, obstr->string, bstr->len));
+       return (mm_memcmp(bstr->string, obstr->string, bstr->len) == 0);
     }
 
     return (FALSE);
diff --git a/mmsoftware/mmlib/mmhash.3 b/mmsoftware/mmlib/mmhash.3
new file mode 100644 (file)
index 0000000..57b4fa7
--- /dev/null
@@ -0,0 +1,476 @@
+.\" $Id: mmhash.3,v 1.1 2003/06/18 01:15:20 mmondor Exp $
+.\"
+.\" Copyright (C) 2001-2003, Matthew Mondor
+.\" All rights reserved.
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\"    notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\"    notice, this list of conditions and the following disclaimer in the
+.\"    documentation and/or other materials provided with the distribution.
+.\" 3. All advertising materials mentioning features or use of this software
+.\"    must display the following acknowledgement:
+.\"      This product includes software written by Matthew Mondor.
+.\" 4. The name of Matthew Mondor may not be used to endorse or promote
+.\"    products derived from this software without specific prior written
+.\"    permission.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY MATTHEW MONDOR ``AS IS'' AND ANY EXPRESS OR
+.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+.\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+.\" IN NO EVENT SHALL MATTHEW MONDOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+.\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+.\" BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+.\" USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+.\"
+.Dd June 17, 2003
+.Dt MMHASH 3
+.Os mmsoftware
+.Sh NAME
+.Nm mmhash
+.Nd General purpose hash table support
+.Sh SYNOPSIS
+.Fd #include <sys/types.h>
+.Fd #include <mmtypes.h>
+.Fd #include <mmhash.h>
+.Ft bool
+.Fn hashtable_init "hashtable_t *table" "unsigned int initialcapacity" \
+"float loadfactor" "void *(*malloc)(size_t)" "void (*free)(void *)" \
+"int (*keycmp)(const void *, const void *, size_t)" \
+"int (*keyhash)(const void *, size_t)"
+.Ft void
+.Fn hashtable_destroy "hashtable_t *table" "bool freeall"
+.Ft hashnode_t *
+.Fn hashtable_find "hashtable_t *table" "const void *key" "size_t keysize"
+.Ft bool
+.Fn hashtable_link "hashtable_t *table" "hashnode_t *node" "const void *key" \
+"size_t keysize"
+.Ft void
+.Fn hashtable_unlink "hashtable_t *table" "hashnode_t *node" "bool rehash"
+.Ft void
+.Fn hashtable_empty "hashtable_t *table" "bool freeall"
+.Ft void
+.Fn hashtable_iterate "hashtable_t *table" \
+"bool (*func)(hashnode_t *, void *)" "void *udata"
+.Ft u_int32_t
+.Fn hashtable_hash "const void *data" "size_t size"
+.Ft unsigned int
+.Fn HASHTABLE_NODES "hashtable_t *table"
+.Ft bool
+.Fn HASHTABLE_VALID "hashtable_t *table"
+.Sh DESCRIPTION
+The
+.Nm
+library provides a useful set of functions to perform fast hash tables
+operations. A hash table is used to hold key/data pair records, and does not
+allow storage of duplicate key elements. The unique key can be used to very
+efficiently retreive the corresponding data record after it had been archived.
+Iteration through all the records is also allowed, but may be slightly slower
+than simply running through a linked list. Note that the storage method is
+not sequencial, which means that the natural order in which key/data pairs
+are stored internally is not sorted, and automatically changes over time.
+.Pp
+Internally, a 32-bit hash function is used to obtain an integer for the key
+element. Because it is possible for that function to generate duplicates under
+certain circumstances with very similar key data, buckets are maintained, which
+can hold hash duplicates, without allowing for duplicate user key data,
+however. This means that when used properly, it is guaranteed that this library
+does not loose entries due to duplicate 32-bit hash collisions.
+.Pp
+The records tend to be as distributed as possible within the number of buckets,
+that is, the table capacity. The buckets consist of an array which is accessed
+efficiently providing indexing. The number of buckets will automatically
+increase as necessary, by two, when the specified bucket fill factor is met.
+However, the system maintains statistics on the average usage of buckets in
+time, which allows it to also automatically decrease the number of buckets,
+making sure to not decrease it for nothing if it knows that the buckets may
+still be necessary soon, for efficiency. The same method that
+.Xr mmpool 3
+uses is employed for this.
+.Pp
+Note that this system is compatible with
+.Xr mmpool 3
+and
+.Xr mmlist 3
+libraries in that it is safe to allocate
+.Nm hashtable_t
+and
+.Nm hashnode_t
+objects using the
+.Xr mmpool 3
+library, and that those nodes can then safely be linked into lists using the
+.Xr mmlist 3
+library. Note however that when an
+.Nm hashnode_t
+is linked within a hash table, it should no longer be linked directly into
+custom
+.Nm list_t
+lists until it be unlinked from the hash table. However, the user can always
+provide a
+.Nm node_t
+as part of the custom node for user linking while the element is still linked
+into the
+.Nm hashtable_t .
+.Pp
+This library does not provide any kind of special synchronization for multiple
+processes or threads to safely access the hash tables or their records. The
+caller is responsible for providing this functionality where needed. The
+hash table is expected to be in memory, as such this library is not intended
+to work on large disk-based databases, but will work with large tables as soon
+as they can fit into memory. The Berkeley DB3/4 library may be what you want
+to use if you need automatic disk storage where memory is only used for
+synchronization, cacheing and performance.
+.Ss HEADER FILE AND DATA STRUCTURES
+.Pp
+To use
+.Nm
+the user should create a custom record structure, prefixing it with an
+.Nm hashnode_t
+object, and holding the necessary record elements such as the key and data,
+although these latter are application-specific. It then can initialize an
+.Nm hashtable_t
+object and use it. Those primitive objects are defined in
+.Pa <mmhash.h> .
+Example:
+.Bd -literal -offset indent
+struct myrecord {
+    hashnode_t node;
+    /* Custom fields follow */
+    char key[128];
+    int data;
+};
+.Ed
+.Pp
+.Ss FUNCTIONS
+.Bl -tag -width indent -offset indent
+.It Xo bool
+.Fo hashtable_init Fa
+.Fa "hashtable_t *table"
+.Fa "unsigned int initialcapacity"
+.Fa "float loadfactor"
+.Fa "void *(*malloc)(size_t)"
+.Fa "void (*free)(void *)"
+.Fa "int (*keycmp)(const void *, const void *, size_t)"
+.Fa "int (*keyhash)(const void *, size_t)"
+.Fc
+.Xc
+is necessary to use first to initialize an
+.Dv hashtable_t
+object before it can be used to store records.
+.Pp
+.Fa table
+consists of the table object to initialize.
+.Pp
+.Fa initialcapacity
+specifies the number of initial buckets that this table should start with.
+.Dv HT_DEFAULT_CAPACITY
+may be used, but if it is known that the table will immediately be filled with
+alot of records, specifying a larger value may be useful to increase insertion
+speed.
+.Pp
+.Fa loadfactor
+specifies the load factor (based on 1, not 100), meaning how many buckets must
+be in use before the table capacity is doubled.
+.Dv HT_DEFAULT_FACTOR
+is generally used, which equals 0.75 but it may be useful to specify an other
+value at times.
+.Pp
+.Fa malloc
+specifies the
+.Xr malloc 3
+style allocation function to use to allocate the buckets index array, and
+.Fa free
+simiarily specifies the
+.Xr free 3
+like corresponding counterpart. Specifying custom functions may be useful to
+use a table in shared memory, for instance.
+.Pp
+.Fa keycmp
+specifies a custom application-specific function which should be employed
+internally to perform key comparision. If it is known that the key data in the
+record node structure is always 32-bit aligned, for instance, specifying a
+custom function for key comparision can improove performance over using the
+standard
+.Xr memcmp 3
+function. It is important for the custom function to semantically behave
+the same as
+.Xr memcmp 3 ,
+and it is allowed to provide a case-insensitive variant. Of course, the size
+argument may or may not be useful for a custom function where the size is
+known and can be assumed.
+.Pp
+.Fa keyhash
+similarily specifies the function which should be used to generate 32-bit
+hashes on arbitrary data. Generally,
+.Fn hashtable_hash
+is used, which is general-purpose and case-insensitive, but using a custom function may be useful to improve performance assuming bit alignment, or using a
+case-insensitive algorithm to derive the hash value.
+.It void Fn hashtable_destroy "hashtable_t *table"
+Allows to destroy a previously initialized
+.Dv hashtable_t
+object.
+.Pp
+.Fa table
+specifies the table to affect and
+.Fa freeall
+allows to optionally automatically call the
+.Xr mmpool 3
+.Fn pool_free
+function on all elements if set to
+.Dv TRUE ,
+or to leave them alone if
+.Dv FALSE .
+.Pp
+Note that if all entries are known to have originated from the same
+.Dv pool_t
+and that the entire pool could be destroyed, it is faster to specify
+.Dv FALSE
+and to use
+.Fn pool_destroy ,
+since when setting
+.Fa autofree
+to
+.Dv TRUE
+the nodes will be individually freed, when
+.Fn pool_destroy
+will just free all the pages.
+.It hashnode_t * Fn hashtable_find "hashtable_t *table" "const void *key" \
+"size_t keysize"
+allows to perform a fast lookup into specified
+.Fa table ,
+for a record which unique key matches the specified
+.Fa key
+and
+.Fa keysize .
+Note that the returned pointer will correspond to the user-supplied one which
+was supplied at
+.Fn hashtable_link ,
+that is, to the actual
+.Dv hashnode_t
+prefixed record in memory, not to a copy.
+.It bool Fn hashtable_link "hashtable_t *table" "hashnode_t *node" \
+"const void *key" "size_t keysize"
+attempts to link the specified
+.Fa node
+record object into the
+.Fa table
+.Dv hashtable_t
+object.
+.Pp
+The record will not be copied but will rather be linked. This means
+that the user is responsible for holding the memory for the supplied
+.Fa node
+for as long as it is required. The
+.Xr mmpool 3
+library is generally used to allocate records before linking them using this
+function.
+.Pp
+The
+.Fa key
+and
+.Fa keysize
+arguments specify the location and size of the actual unique key in the
+supplied record. Those will internally be required by the library when calling
+the
+.Fa keycmp
+and
+.Fa keyhash
+functions provided at
+.Fn hashtable_init ,
+because the library has no other means to know where the key data is stored
+within the custom application-specific
+.Dv hashnode_t
+based structure used to hold the records.
+.Pp
+Note that this function will refuse
+to insert a record if the key is identical to an already existing one, which
+would cause a duplicate. Although occasional duplicates are allowed from the
+supplied
+.Fa keyhash
+function to
+.Fn hashtable_init ,
+duplicate record keys are not allowed.
+.It void Fn hashtable_unlink "hashtable_t *table" "hashnode_t *node" \
+"bool rehash"
+permits to unlink the specified
+.Fa node
+record from the
+.Fa table
+hash table, which obviously must previously have been inserted into it. The
+.Fa node
+is usually obtained from a previous
+.Fn hashtable_lookup
+function call.
+.Pp
+Note that although the record is unlinked from the table, it is
+not freed from memory. The caller is responsible for maintaining the memory
+associated with the record nodes (usually using the
+.Xr mmpool 3
+library).
+.Pp
+If
+.Fa rehash
+is
+.Dv TRUE ,
+the
+.Dv hashtable_t
+capacity (number of buckets) will automatically be reduced if statistics
+evaluate that it has been too wide for too long. It should generally be
+.Dv TRUE ,
+but it is important to specify
+.Dv FALSE
+if
+.Fn hashtable_unlink
+is called from within an iterator function called by
+.Fn hashtable_iterate ,
+in which case statistics are still maintained so that the first non-iterative
+unlink could still rehash the table if
+.Dv TRUE
+was specified.
+.It void Fn hashtable_empty "hashtable_t *table" "bool freeall"
+unlinks all records from the supplied
+.Fa table .
+.Pp
+The hashtable capacity is automatically restored to the initial one specified
+at
+.Fn hashtable_init .
+If
+.Fa freeall
+is
+.Dv TRUE ,
+all nodes linked in the table are also automatically freed using
+the
+.Xr mmpool 3
+library
+.Fn pool_free
+function.
+.Pp
+Note that similarily to with
+.Fn hashtable_destroy ,
+it is faster to specify
+.Dv FALSE
+for
+.Fa freeall
+and to call
+.Xr mmpool 3
+.Fn pool_destroy
+if it is known that all nodes originated from the same
+.Dv pool_t .
+.It void Fn hashtable_iterate "hashtable_t *table" \
+"bool (*func)(hashnode_t *, void *)" "void *udata"
+permits to run through the existing records of the specified
+.Fa table .
+.Pp
+The specified
+.Fa func
+function will be called for each record, sequencially, supplied with the
+pointer to a record and the
+.Fa udata
+custom user data function (which can be NULL).
+.Pp
+Note that the order in which the records will flow is unsorted and
+undetermined. As long as the supplied function returns
+.Dv TRUE ,
+it will be fed new records until they all have been processed. If it returns
+.Dv FALSE ,
+.Fn hashtable_iterate
+immediately stops iteration and returns.
+.Pp
+Note that it is safe to call
+.Fn hashtable_unlink
+from within an iterator function, but that
+.Dv FALSE
+should be specified to it's
+.Fa rehash
+argument, otherwise the behavior is undefined.
+.It u_int32_t Fn hashtable_hash "const void *data" "size_t size"
+is provided as a generic case-insensitive and bit alignment independant
+hashing function to be specified at
+.Fn hashtable_init .
+.Pp
+It is known to work well in most circumstances, but it is still recommended
+to use a custom function where appropriate when optimizations or functionality
+enhancements can be achieved for a particular key data set type. For instance,
+a function taking advantage of known 32-bit alignment will be faster. Also,
+a system which wants to work with case-insensitive alphanumeric keys
+may want to use a different function than
+.Fn hashtable_hash .
+.It unsigned int Fn HASHTABLE_NODES "hashtable_t *table"
+This macro is useful to return the total number of current nodes linked into
+the specified
+.Fa table
+.Dv hashtable_t .
+.It bool Fn HASHTABLE_VALID "hashtable_t *table"
+This macro returns
+.Dv TRUE
+if the supplied
+.Fa table
+is valid, that is, was properly initialized with success, and was not yet
+destroyed, or
+.Dv FALSE
+otherwise.
+.El
+.Sh RETURN VALUES
+.Bl -tag -width indent -offset indent
+.It Xo
+.Fn hashtable_destroy ,
+.Fn hashtable_unlink ,
+.Fn hashtable_destroy ,
+.Fn hashtable_unlink ,
+.Fn hashtable_empty ,
+.Fn hashtable_iterate
+.Xc
+return nothing.
+.It Fn hashtable_init
+returns
+.Dv TRUE
+on success, or
+.Dv FALSE
+on error (out of memory).
+.It Fn hashtable_find
+returns the pointer to the matching
+.Dv hashnode_t
+if found, or
+.Dv NULL
+if no entry matched the supplied key.
+.It Fn hashtable_link
+returns
+.Dv TRUE
+if the record could be inserted, or
+.Dv FALSE
+if it refused to insert it because it would consist of a duplicate key entry.
+.It Fn hashtable_hash
+returns a 32-bit hash code/value corresponding to the specified memory area.
+.It Fn HASHTABLE_NODES
+returns the total number of currently existing records into the specified
+table.
+.It Fn HASHTABLE_VALID
+returns
+.Dv TRUE
+or
+.Dv FALSE .
+.El
+.Sh SEE ALSO
+.Xr malloc 3 ,
+.Xr free 3 ,
+.Xr mmlist 3 ,
+.Xr mmpool 3 ,
+.Xr memcmp 3 .
+.Sh STANDARDS
+None
+.Sh HISTORY
+.Xr mmhash 3
+was originally developped for the Xisop portable microkernel project
+from Matthew Mondor. It later on was adapted to be used by
+.Xr mmstatd 8 .
+.Sh AUTHORS
+The mmhash library was written by Matthew Mondor and is
+Copyright (c) 2001-2003, Matthew Mondor, All rights reserved.
+.Sh BUGS
+Please report any bug to mmondor@gobot.ca
diff --git a/mmsoftware/mmlib/mmhash.c b/mmsoftware/mmlib/mmhash.c
new file mode 100644 (file)
index 0000000..882149e
--- /dev/null
@@ -0,0 +1,345 @@
+/* $Id: mmhash.c,v 1.1 2003/06/18 01:15:20 mmondor Exp $ */
+
+/*
+ * Copyright (C) 2001-2003, Matthew Mondor
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *      This product includes software written by Matthew Mondor.
+ * 4. The name of Matthew Mondor may not be used to endorse or promote
+ *    products derived from this software without specific prior written
+ *    permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY MATTHEW MONDOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL MATTHEW MONDOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+ * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+
+
+#include <sys/types.h>
+#include <syslog.h>
+
+#include <mmhash.h>
+
+
+/* This system is safe to use 32-bit hashes internally, despite the possibility
+ * for collisions. We maintain an array or buckets, within which the entries
+ * are distributed. A 32-bit hash collision entry will end up on the same
+ * bucket. We however also make sure to not allow to store exact duplicate
+ * keys. The number if buckets will increase and decrease whenever the system
+ * detects that it becomes necessary for efficiency. The larger the number of
+ * buckets, the less nodes are likely to coexist in each bucket. The bucket
+ * index to use is evaluated using a modulo to convert the 32-bit hash to
+ * fit into the current number of buckets in the table. Of course, when
+ * the number of buckets is to be updated (which ideally happens rarely),
+ * the entries are rehashed to be properly indexed within the new capacity.
+ *
+ * The number of buckets is automatically doubled when the table fills up
+ * to the specified factor (usually 0.75/1), and of course the table rehashed.
+ * The hash table capacity can therefore also be reduced over time when it is
+ * known that memory wastage occurs for some while (statistics are maintained
+ * for this, similarily to how the mmpool library works). This means that if
+ * the number of entries is constantly growing high and falling back low,
+ * the table capacity should not change for better performance.
+ *
+ * Commonly used values for the initial hash table bucket capacity and fill
+ * factor are 11, 0.75, respectively, to which are set HT_DEFAULT_CAPACITY
+ * and HT_DEFAULT_FACTOR.
+ *
+ * Searching for a key by pattern, which requires iterating through the
+ * nodes, rather than through it's absolute key can actually be a little
+ * slower than running through a simple linked list of absolute hash values,
+ * since all buckets must be scanned. However, we ensure to stop running
+ * through buckets when the total number of mappings have been scanned already.
+ * Lookups using the absolute key of the node will be much faster in the case
+ * where the hash table grows considerably, however.
+ *
+ * XXX
+ * - Fix growing problem; It should normally only grow the capacity when
+ *   it knows that most buckets are in use (and are probably holding more than
+ *   a certain number of nodes each. Either we choose a maximum number of nodes
+ *   per leaf to support, or we find a good balancing system.
+ * - Implement capacity shrinking using statistics
+ * - Write a man page
+ */
+
+
+
+#define HASH_INDEX(h, s)       (((h) & 0x7FFFFFFF) % (s))
+
+
+
+static void hashtable_rehash(hashtable_t *, unsigned int);
+
+
+
+bool hashtable_init(hashtable_t *t, unsigned int initialcapacity,
+       float loadfactor, void *(*allocfunc)(size_t), void (*freefunc)(void *),
+       int (*keycomp)(const void *, const void *, size_t),
+       u_int32_t (*keyhash)(const void *, size_t))
+{
+    if (!HASHTABLE_VALID(t)) {
+       if ((t->array = allocfunc(sizeof(list_t) * initialcapacity)) != NULL) {
+           unsigned int i;
+
+           t->magic = MAGIC_HASHTABLE;
+           t->malloc = allocfunc;
+           t->free = freefunc;
+           t->keycomp = keycomp;
+           t->keyhash = keyhash;
+           t->nodes = 0;
+           t->initial = t->capacity = initialcapacity;
+           t->loadfactor = loadfactor;
+           t->threshold = (unsigned int)(((float)initialcapacity) *
+                   loadfactor);
+           t->avgtotal = t->avgcnt = initialcapacity;
+           for (i = 0; i < initialcapacity; i++)
+               LIST_INIT(&(t->array[i]));
+
+           return TRUE;
+       } else
+           syslog(LOG_NOTICE, "hashtable_init() - Out of memory");
+    } else
+       syslog(LOG_NOTICE, "hashtable_init() - Table already initialized");
+
+    return FALSE;
+}
+
+
+void hashtable_destroy(hashtable_t *t, bool freeall)
+{
+    if (HASHTABLE_VALID(t)) {
+       if (t->array != NULL) {
+           if (freeall) {
+               register unsigned int i, done;
+               register list_t *l;
+               register hashnode_t *k;
+
+               for (i = done = 0; done < t->nodes && i < t->capacity; i++) {
+                   l = &(t->array[i]);
+                   if (l->nodes > 0) {
+                       for (k = (hashnode_t *)l->top; k != NULL;
+                               k = (hashnode_t *)k->node.node.next) {
+                           pool_free((pnode_t *)k);
+                           done++;
+                       }
+                   }
+               }
+           }
+           t->free(t->array);
+       }
+       t->magic = 0;
+    } else
+       syslog(LOG_NOTICE, "hashtable_destroy() - Invalid hashtable pointer");
+}
+
+
+hashnode_t *hashtable_find(hashtable_t *t, const void *key, size_t keysize)
+{
+    register u_int32_t hash;
+    register unsigned int i;
+    register list_t *l;
+    register hashnode_t *k = NULL;
+
+    hash = t->keyhash(key, keysize);
+    i = HASH_INDEX(hash, t->capacity);
+    l = &(t->array[i]);
+    if (l->nodes > 0) {
+       for (k = (hashnode_t *)l->top; k != NULL;
+               k = (hashnode_t *)k->node.node.next)
+           if (k->hash == hash && k->keysize == keysize &&
+                   t->keycomp(k->key, key, keysize) == 0)
+               break;
+    }
+
+    return k;
+}
+
+
+bool hashtable_link(hashtable_t *t, hashnode_t *k, const void *key,
+       size_t keysize)
+{
+    register u_int32_t hash;
+    register unsigned int i;
+    register list_t *l;
+    bool ok = TRUE;
+
+    hash = t->keyhash(key, keysize);
+    i = HASH_INDEX(hash, t->capacity);
+    l = &(t->array[i]);
+    /* We do not allow exact duplicates, so verify first. Duplicate hashes are
+     * fine, however, as long as the key data is not identical.
+     */
+    if (l->nodes > 0) {
+       register hashnode_t *tk;
+
+       for (tk = (hashnode_t *)l->top; tk != NULL;
+               tk = (hashnode_t *)tk->node.node.next) {
+           if (tk == k || (tk->hash == hash && tk->keysize == keysize &&
+                       t->keycomp(tk->key, key, keysize) == 0)) {
+               syslog(LOG_NOTICE, "hashtable_link() - Duplicate key attempt");
+               ok = FALSE;
+               break;
+           }
+       }
+    }
+    if (ok) {
+       k->hash = hash;
+       k->list = l;
+       k->key = key;
+       k->keysize = keysize;
+       LIST_INSERT(l, (node_t *)k);
+       /* Grow capacity if necessary */
+       if (++t->nodes > t->threshold)
+           hashtable_rehash(t, t->capacity * 2);
+    }
+
+    return ok;
+}
+
+
+void hashtable_unlink(hashtable_t *t, hashnode_t *k, bool rehash)
+{
+    unsigned int exceeding;
+
+    LIST_UNLINK(k->list, (node_t *)k);
+    k->list = NULL;
+    t->nodes--;
+
+    /* Verify if the capacity should be reduced, using statistics */
+    t->avgtotal += t->capacity;
+    t->avgcnt++;
+    if (t->avgcnt > t->capacity / (t->initial * 3)) {
+       t->avgcnt = 1;
+       t->avgtotal = t->capacity;
+    }
+    /* Rehash with a smaller capacity if necessary */
+    if (rehash) {
+       if ((exceeding = t->capacity - (t->avgtotal / t->avgcnt)) > 0)
+           hashtable_rehash(t, t->capacity - exceeding);
+    }
+}
+
+
+/* Note that as the user generally has a pool_t dedicated to the hashnode_t
+ * elements for a particular table, it may be more efficient to not use
+ * the <freeall> option and to pool_free() which does not need to iterate
+ * through nodes. This function has to however, because it obviously cannot
+ * assume that the caller wishes to free all nodes of the origin pool_t, or
+ * that all entries origin from the same pool_t.
+ */
+void hashtable_empty(hashtable_t *t, bool freeall)
+{
+    register unsigned int i;
+    register list_t *l;
+    register hashnode_t *k, *kt;
+
+    for (i = 0; i < t->capacity; i++) {
+       if (freeall) {
+           l = &(t->array[i]);
+           if (l->nodes > 0) {
+               for (k = (hashnode_t *)l->top; k != NULL; k = kt) {
+                   kt = (hashnode_t *)k->node.node.next;
+                   pool_free((pnode_t *)k);
+               }
+           }
+       } else
+           LIST_INIT(&(t->array[i]));
+    }
+    hashtable_rehash(t, t->initial);
+}
+
+
+void hashtable_iterate(hashtable_t *t,
+       bool (*func)(hashnode_t *, void *), void *udata)
+{
+    register unsigned int i;
+    register list_t *l;
+    register hashnode_t *k, *kt;
+
+    for (i = 0; i < t->capacity; i++) {
+       l = &(t->array[i]);
+       if (l->nodes > 0) {
+           /* Note that we use a temporary variable to hold the next key,
+            * in case the user function alters the key node (i.e. unlinks it)
+            */
+           for (k = (hashnode_t *)l->top; k != NULL; k = kt) {
+               kt = (hashnode_t *)k->node.node.next;
+               if (!func(k, udata))
+                   return;
+           }
+       }
+    }
+}
+
+
+/* Rehashes the whole hashtable so that the capacity may be changed to the
+ * specified one. The memory area is also automatically changed. Ideally,
+ * this only occurs rarely. If it fails because of a lack of memory, the
+ * hash table will simply not be affected, but lookups will become slower.
+ */
+static void hashtable_rehash(hashtable_t *t, unsigned int newcapacity)
+{
+    list_t *newarray;
+
+    if ((newarray = t->malloc(sizeof(list_t) * newcapacity)) != NULL) {
+       register unsigned int i, done;
+
+       for (i = 0; i < newcapacity; i++)
+           LIST_INIT(&newarray[i]);
+
+       for (i = done = 0; done < t->nodes && i < t->capacity; i++) {
+           register hashnode_t *k, *kt;
+           register list_t *l, *newl;
+
+           l = &(t->array[i]);
+           if (l->nodes > 0) {
+               for (k = (hashnode_t *)l->top; k != NULL; k = kt) {
+                   kt = (hashnode_t *)k->node.node.next;
+                   newl = &newarray[HASH_INDEX(k->hash, newcapacity)];
+                   LIST_SWAP(newl, l, (node_t *)k, TRUE);
+                   k->list = newl;
+                   done++;
+               }
+           }
+       }
+
+       t->capacity = newcapacity;
+       t->threshold = (unsigned int)(((float)newcapacity) * t->loadfactor);
+       t->free(t->array);
+       t->array = newarray;
+    }
+}
+
+
+u_int32_t hashtable_hash(const void *mem, size_t size)
+{
+    register u_int32_t hash;
+    register const char *curmem, *tomem;
+
+    hash = 0;
+    curmem = tomem = mem;
+    tomem += size;
+
+    for (; curmem < tomem; curmem++)
+       hash = *curmem + (31 * hash);
+
+    return hash;
+}
diff --git a/mmsoftware/mmlib/mmhash.h b/mmsoftware/mmlib/mmhash.h
new file mode 100644 (file)
index 0000000..52bbcde
--- /dev/null
@@ -0,0 +1,104 @@
+/* $Id: mmhash.h,v 1.1 2003/06/18 01:15:20 mmondor Exp $ */
+
+/*
+ * Copyright (C) 2001-2003, Matthew Mondor
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *      This product includes software written by Matthew Mondor.
+ * 4. The name of Matthew Mondor may not be used to endorse or promote
+ *    products derived from this software without specific prior written
+ *    permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY MATTHEW MONDOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL MATTHEW MONDOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+ * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+
+
+#ifndef MMHASH_H
+#define MMHASH_H
+
+
+
+#include <sys/types.h>
+
+#include <mmtypes.h>
+#include <mmlist.h>
+#include <mmpool.h>
+
+
+
+typedef struct hashnode hashnode_t;
+typedef struct hashtable hashtable_t;
+
+
+
+struct hashnode {
+    pnode_t node;
+    list_t *list;
+    u_int32_t hash;
+    const void *key;
+    size_t keysize;
+    /* Custom user data will follow, uncluding the key element to which the
+     * previous key pointer is expected to point.
+     */
+};
+
+struct hashtable {
+    pnode_t node;      /* In case we want a pool_t of hashtable_t */
+    u_int32_t magic;
+    unsigned int initial, capacity, threshold, nodes;
+    float loadfactor;
+    list_t *array;
+    void *(*malloc)(size_t);
+    void (*free)(void *);
+    int (*keycomp)(const void *, const void *, size_t);
+    u_int32_t (*keyhash)(const void *, size_t);
+    unsigned int avgtotal, avgcnt;
+};
+
+
+
+#define MAGIC_HASHTABLE                0x4854424c      /* HTBL */
+#define HT_DEFAULT_CAPACITY    128
+#define HT_DEFAULT_FACTOR      0.75f
+
+#define HASHTABLE_NODES(t)     ((t)->nodes)
+#define HASHTABLE_VALID(t)     ((t) != NULL && (t)->magic == MAGIC_HASHTABLE)
+
+
+
+bool hashtable_init(hashtable_t *, unsigned int, float,
+       void *(*)(size_t), void (*)(void *),
+       int (*)(const void *, const void *, size_t),
+       u_int32_t (*)(const void *, size_t));
+void hashtable_destroy(hashtable_t *, bool);
+hashnode_t *hashtable_find(hashtable_t *, const void *, size_t);
+bool hashtable_link(hashtable_t *, hashnode_t *, const void *, size_t);
+void hashtable_unlink(hashtable_t *, hashnode_t *, bool);
+void hashtable_empty(hashtable_t *, bool);
+void hashtable_iterate(hashtable_t *, bool (*)(hashnode_t *, void *),
+       void *);
+u_int32_t hashtable_hash(const void *, size_t);
+
+
+
+#endif
index 3036fe2..dccb1bf 100644 (file)
@@ -1,4 +1,4 @@
-.\" $Id: mmlist.3,v 1.5 2003/03/28 21:09:29 mmondor Exp $
+.\" $Id: mmlist.3,v 1.6 2003/06/18 01:15:20 mmondor Exp $
 .\"
 .\" Copyright (C) 2002-2003, Matthew Mondor
 .\" All rights reserved.
@@ -127,7 +127,8 @@ from
 .Sh RETURN VALUES
 These macros do not return anything.
 .Sh SEE ALSO
-.Xr mmpool 3 .
+.Xr mmpool 3 ,
+.Xr mmhash 3 .
 .Sh STANDARDS
 None
 .Sh HISTORY
index 14146eb..dfd94de 100644 (file)
@@ -1,4 +1,4 @@
-.\" $Id: mmpool.3,v 1.1 2003/03/28 21:09:29 mmondor Exp $
+.\" $Id: mmpool.3,v 1.2 2003/06/18 01:15:20 mmondor Exp $
 .\"
 .\" Copyright (C) 2001-2003, Matthew Mondor
 .\" All rights reserved.
@@ -243,7 +243,8 @@ macros return TRUE or FALSE.
 .Sh SEE ALSO
 .Xr malloc 3 ,
 .Xr free 3 ,
-.Xr mmlist 3 .
+.Xr mmlist 3 ,
+.Xr mmhash 3 .
 .Sh STANDARDS
 None
 .Sh HISTORY
index da12e84..5c9ece5 100644 (file)
@@ -1,4 +1,4 @@
-/* $Id: mmserver.c,v 1.6 2003/05/28 06:39:44 mmondor Exp $ */
+/* $Id: mmserver.c,v 1.7 2003/06/18 01:15:20 mmondor Exp $ */
 
 /*
  * Copyright (C) 2000-2003, Matthew Mondor
@@ -65,6 +65,8 @@
 #include <mmstring.h>
 #include <mmfd.h>
 #include <mmlist.h>
+#include <mmpool.h>
+#include <mmhash.h>
 #include <mmserver.h>
 #include <mmreadcfg.h>
 
@@ -73,7 +75,7 @@
 
 MMCOPYRIGHT("@(#) Copyright (c) 2002-2003\n\
 \tMatthew Mondor. All rights reserved.\n");
-MMRCSID("$Id: mmserver.c,v 1.6 2003/05/28 06:39:44 mmondor Exp $");
+MMRCSID("$Id: mmserver.c,v 1.7 2003/06/18 01:15:20 mmondor Exp $");
 
 
 
@@ -94,6 +96,11 @@ static bool spawn_async_procs(uid_t, gid_t *, int);
 static void async_proc_main(int);
 static void async_resolvehostname(struct async_msg *);
 
+static u_int32_t clnode_keyhash(const void *, size_t);
+static int clnode_keycmp(const void *, const void *, size_t);
+static void *clnode_expire_thread(void *);
+static bool clnode_expire_thread_iterator(hashnode_t *, void *);
+
 
 
 
@@ -101,9 +108,9 @@ static void async_resolvehostname(struct async_msg *);
 
 static int (*handleclientfunc)(unsigned long, int, clientlistnode *,
        struct iface *, struct async_clenv *);
-static pth_mutex_t cpool_lock, ppool_lock;
+static pth_mutex_t ctable_lock, ppool_lock;
 static pool_t cpool, ppool;
-static list_t clist;
+static hashtable_t ctable;
 static struct async_env *async = NULL;
 
 /* Useful so that daemons can log standard disconnection status easily */
@@ -143,14 +150,14 @@ tcp_server(char *message, char *server_names, char *listen_ips, uid_t uid,
     struct sockaddr_in server, *sinaddr;
     socklen_t addrl;
     clientlistnode *clnode;
-    int msgsock, ret, cnt, msglen, nifaces, nifaces2, i, reason;
+    int msgsock, ret, msglen, nifaces, nifaces2, i, reason;
     bool ok;
     struct pollfd *fds;
     struct ifacendx *fdsi;
     struct iface *ifaces, *tif;
     unsigned long id;
-    pth_t thread;
-    pth_attr_t threadattr;
+    pth_t thread, clnode_thread;
+    pth_attr_t threadattr, clnode_threadattr;
 
     sinaddr = (struct sockaddr_in *)&addr;
     handleclientfunc = handleclient1;
@@ -164,8 +171,9 @@ tcp_server(char *message, char *server_names, char *listen_ips, uid_t uid,
     /* Pth related */
     threadattr = pth_attr_new();
     pth_attr_set(threadattr, PTH_ATTR_JOINABLE, FALSE);
-    pth_mutex_init(&cpool_lock);
-    LIST_INIT(&clist);
+    clnode_threadattr = pth_attr_new();
+    pth_attr_set(clnode_threadattr, PTH_ATTR_JOINABLE, TRUE);
+    pth_mutex_init(&ctable_lock);
     pth_mutex_init(&ppool_lock);
 
     /* Used by resolve_hostname() */
@@ -184,7 +192,11 @@ tcp_server(char *message, char *server_names, char *listen_ips, uid_t uid,
     if (!pool_init(&cpool, malloc, free, sizeof(clientlistnode),
                65536 / sizeof(clientlistnode), 0, 0) ||
            !pool_init(&ppool, malloc, free, sizeof(phandleinfo),
-               16384 / sizeof(phandleinfo), 0, 0)) {
+               16384 / sizeof(phandleinfo), 0, 0) ||
+           !hashtable_init(&ctable, 16, HT_DEFAULT_FACTOR,
+               malloc, free, clnode_keycmp, clnode_keyhash) ||
+           ((clnode_thread = pth_spawn(clnode_threadattr,
+                               clnode_expire_thread, &rateper)) == NULL)) {
        syslog(LOG_NOTICE, "* mmserver() - Out of memory");
        closelog();
        mmstrexit();
@@ -271,6 +283,11 @@ tcp_server(char *message, char *server_names, char *listen_ips, uid_t uid,
     if (ret) {
        free(ifaces);
        mmstrexit();
+       if (clnode_thread != NULL) {
+           pth_abort(clnode_thread);
+           pth_join(clnode_thread, NULL);
+       }
+       if (HASHTABLE_VALID(&ctable)) hashtable_destroy(&ctable, FALSE);
        if (POOL_VALID(&ppool)) pool_destroy(&ppool);
        if (POOL_VALID(&cpool)) pool_destroy(&cpool);
        exit(ret);
@@ -289,81 +306,53 @@ tcp_server(char *message, char *server_names, char *listen_ips, uid_t uid,
                    addrl = sizeof(struct sockaddr);
                    if ((msgsock = pth_accept(fds[i].fd, &addr, &addrl))
                            != -1) {
-                       register clientlistnode *nclnode;
-                       time_t tim;
-
-                       pth_mutex_acquire(&cpool_lock, FALSE, NULL);
-
-                       /* Try to locate the IP address of the new connection
-                        * in our clientlist. Doing so, we also garbage
-                        * collect / free ones which no longer need to be
-                        * cached, since this list also holds the connection
-                        * rate statistics for each address.
+                       /* Make sure that we respect connection and rate
+                        * limits.
                         */
-                       cnt = 0;
-                       tim = time(NULL);
-                       clnode = (clientlistnode *)clist.top;
-                       while (clnode) {
-                           nclnode = (clientlistnode *)clnode->node.node.next;
-                           /* Has the period expired? If so, reset it */
-                           if (clnode->period < tim) {
-                               clnode->period = tim + rateper;
-                               clnode->rate = 0;
-                           }
-                           if (((struct sockaddr_in *)&clnode->client)->
-                                   sin_addr.s_addr ==
-                                   sinaddr->sin_addr.s_addr)
-                               /* Reuse this node */
-                               break;
-                           if (clnode->connections == 0 &&
-                                   clnode->rate == 0) {
-                               /* Free from cache */
-                               if (clnode->hostname)
-                                   mmstrfree(clnode->hostname);
-                               LIST_UNLINK(&clist, (node_t *)clnode);
-                               pool_free((pnode_t *)clnode);
-                           }
-                           cnt++;
-                           if (cnt > 32) {
-                               cnt = 0;
-                               pth_yield(NULL);
-                           }
-                           clnode = nclnode;
-                       }
-
                        ok = FALSE;
                        reason = MMS_NORMAL;
-                       if (clnode) {
-                           /* Found, Make sure we don't exceed maxperip
-                            * and connection rate
-                            */
-                           if (clnode->connections < maxperip) {
-                               if (ratemax) {
-                                   if (clnode->rate < ratemax) {
-                                       clnode->rate++;
-                                       ok = TRUE;
-                                   } else reason = MMS_RATE_EXCEEDED;
-                               } else ok = TRUE;
-                           } else reason = MMS_CONPERADDRESS_EXCEEDED;
-                       } else {
-                           /* Make sure we don't exceed maxips */
-                           if (clist.nodes < maxips) {
-                               /* Allocate a new ip-address shared node */
+                       pth_mutex_acquire(&ctable_lock, FALSE, NULL);
+                       if ((clnode = (clientlistnode *)hashtable_find(&ctable,
+                                       &sinaddr->sin_addr.s_addr,
+                                       sizeof(u_int32_t))) == NULL) {
+                           /* Create new node */
+                           if (HASHTABLE_NODES(&ctable) < maxips) {
                                if ((clnode = (clientlistnode *)pool_alloc(
                                                &cpool, FALSE)) != NULL) {
                                    clnode->hostname = NULL;
                                    clnode->connections = clnode->rate = 0;
-                                   clnode->period = tim + rateper;
+                                   clnode->period = time(NULL) + rateper;
                                    clnode->timeout = (timeout * 1000);
                                    clnode->client = addr;
                                    clnode->resolve = resolve;
-                                   LIST_APPEND(&clist, (node_t *)clnode);
-                                   ok = TRUE;
+                                   hashtable_link(&ctable,
+                                           (hashnode_t *)clnode,
+                                           &((struct sockaddr_in *)&clnode->
+                                            client)->sin_addr.s_addr,
+                                           sizeof(u_int32_t));
                                } else
                                    syslog(LOG_NOTICE,
                                            "* mmserver() - Out of memory");
-                           } else reason = MMS_ADDRESSES_EXCEEDED;
+                           } else
+                               reason = MMS_ADDRESSES_EXCEEDED;
+                       }
+                       if (clnode != NULL) {
+                           /* Either we found an existing node or we created
+                            * it successfully
+                            */
+                           if (clnode->connections < maxperip) {
+                               if (ratemax != 0) {
+                                   if (clnode->rate < ratemax) {
+                                       clnode->rate++;
+                                       ok = TRUE;
+                                   } else
+                                       reason = MMS_RATE_EXCEEDED;
+                               } else
+                                   ok = TRUE;
+                           } else
+                               reason = MMS_CONPERADDRESS_EXCEEDED;
                        }
+                       pth_mutex_release(&ctable_lock);
 
                        if (ok) {
                            phandleinfo *phi;
@@ -414,7 +403,7 @@ thread to serve client");
                                        ipaddr, MMS_RSTRING(reason));
                        }
 
-                       pth_mutex_release(&cpool_lock);
+                       pth_mutex_release(&ctable_lock);
 
                    } else
                        syslog(LOG_NOTICE,
@@ -426,11 +415,14 @@ thread to serve client");
 
     free(ifaces);
     mmstrexit();
+    pth_abort(clnode_thread);
+    pth_join(clnode_thread, NULL);
+    hashtable_destroy(&ctable, FALSE);
     pool_destroy(&ppool);
     pool_destroy(&cpool);
     /* Unrequired for Pth (non-existing even)
      * pth_mutex_destroy(&apool_lock);
-     * pth_mutex_destroy(&cpool_lock);
+     * pth_mutex_destroy(&ctable_lock);
      * pth_mutex_destroy(&ppool_lock);
      */
 
@@ -635,11 +627,11 @@ phandleclient(void *args)
            }
            if (tmp) {
                /* Lock the mutex for a very short moment */
-               pth_mutex_acquire(&cpool_lock, FALSE, NULL);
+               pth_mutex_acquire(&ctable_lock, FALSE, NULL);
                /* Verify again for NULL to avoid a potential memory leak */
                if(clnode->hostname == NULL) clnode->hostname = tmp;
                else tmp = mmstrfree(tmp);
-               pth_mutex_release(&cpool_lock);
+               pth_mutex_release(&ctable_lock);
            }
        }
 
@@ -658,12 +650,12 @@ phandleclient(void *args)
        close(socket);
     }
 
-    /* Decrease our connection/refcount counter, and let mmserver()
-     * garbage-collect or recycle our clnode as required.
+    /* Decrease our connection/refcount counter, and let our ctable thread
+     * decide if/when to uncache our node.
      */
-    pth_mutex_acquire(&cpool_lock, FALSE, NULL);
+    pth_mutex_acquire(&ctable_lock, FALSE, NULL);
     if (clnode->connections > 0) clnode->connections--;
-    pth_mutex_release(&cpool_lock);
+    pth_mutex_release(&ctable_lock);
 
     /* kthxbye :) */
     pth_exit(&ret);
@@ -1230,3 +1222,92 @@ resolve_hostname(struct async_clenv *aclenv, struct sockaddr *saddr)
 
     return (tmp);
 }
+
+
+/* These are related to the clnode ipaddress hash table. */
+
+
+/* A quick hashtable_hash() replacement which already deals with unique
+ * 32-bit values
+ */
+/* ARGSUSED */
+static u_int32_t
+clnode_keyhash(const void *data, size_t len)
+{
+    return *((u_int32_t *)data);
+}
+
+
+/* A quick memcmp() replacement which only needs to compare two 32-bit values
+ */
+/* ARGSUSED */
+static int
+clnode_keycmp(const void *src, const void *dst, size_t len)
+{
+    return *((u_int32_t *)src) - *((u_int32_t *)dst);
+}
+
+
+/* This is the actual ctable hash control and expiration thread */
+/* ARGSUSED */
+static void *
+clnode_expire_thread(void *args)
+{
+    long period = *((long *)args);
+    struct clnode_expire_thread_iterator_udata data;
+
+    /* Set initial timeout to maximum allowed */
+    data.soonest = time(NULL) + period;
+    data.cnt = 0;
+    data.period = period;
+    for (;;) {
+       /* Sleep until it is known that at least one node expired */
+       pth_sleep(data.soonest - time(NULL));
+       /* Tell our iterator function the current time and the maximum
+        * allowed time to wait to
+        */
+       data.current = time(NULL);
+       data.soonest = data.current + period;
+       /* Lock ctable, reset expired nodes, garbage collect, and set
+        * data.soonest to the time of the soonest next expireing node.
+        */
+       pth_mutex_acquire(&ctable_lock, FALSE, NULL);
+       hashtable_iterate(&ctable, clnode_expire_thread_iterator, &data);
+       pth_mutex_release(&ctable_lock);
+    }
+
+    /* NOTREACHED */
+    pth_exit(NULL);
+    return NULL;
+}
+
+
+static bool
+clnode_expire_thread_iterator(hashnode_t *hnod, void *udata)
+{
+    clientlistnode *clnode = (clientlistnode *)hnod;
+    struct clnode_expire_thread_iterator_udata *data = udata;
+
+    if (clnode->period < data->current) {
+       /* This entry expired, reset it */
+       clnode->period = data->current + data->period;
+       clnode->rate = 0;
+    } else {
+       /* We must find and record the soonest expireing node */
+       if (data->soonest > clnode->period)
+           data->soonest = clnode->period;
+    }
+    if (clnode->connections == 0 && clnode->rate == 0) {
+       /* Safe to expunge this node from the cache */
+       hashtable_unlink(&ctable, (hashnode_t *)clnode, FALSE);
+       pool_free((pnode_t *)clnode);
+    }
+
+    /* If the cache is big, prevent from interfering with other threads */
+    if ((data->cnt++) == 64) {
+       data->cnt = 0;
+       pth_yield(NULL);
+    }
+
+    return TRUE;
+}
index 2ce09d8..7ed5317 100644 (file)
@@ -1,4 +1,4 @@
-/* $Id: mmserver.h,v 1.4 2003/05/28 06:39:44 mmondor Exp $ */
+/* $Id: mmserver.h,v 1.5 2003/06/18 01:15:20 mmondor Exp $ */
 
 /*
  * Copyright (C) 2000-2003, Matthew Mondor
@@ -45,6 +45,8 @@
 
 #include <mmtypes.h>
 #include <mmpool.h>
+#include <mmlist.h>
+#include <mmhash.h>
 
 
 
@@ -82,15 +84,22 @@ enum mms {
  * no connections are left and occurred for connection rate period.
  */
 typedef struct clientlistnode {
-    pnode_t node;
+    hashnode_t node;
     char *hostname;
     long connections, rate;
     time_t period;
     int timeout;
+    /* Key is ((struct sockaddr_in *)&clnode->client)->sin_addr.s_addr */
     struct sockaddr client;
     bool resolve;
 } clientlistnode;
 
+struct clnode_expire_thread_iterator_udata {
+    time_t current, soonest;
+    int cnt;
+    long period;
+};
+
 /* This is passed to the client threads, which they return to the pool when
  * done with (internally, the user thread function does not need to free it).
  */
@@ -102,7 +111,7 @@ typedef struct phandleinfo {
     int socket;
 } phandleinfo;
 
-/* XXX most security options and limits should be on a per-iface basis,
+/* XXX most security options and limits should be on a per-interface basis,
  * This would however require mmreadcfg library enhancements.
  */
 struct iface {
index 1373522..2a0ffc1 100644 (file)
@@ -1,4 +1,4 @@
-/* $Id: mmstat.h,v 1.4 2003/04/27 19:48:04 mmondor Exp $ */
+/* $Id: mmstat.h,v 1.5 2003/06/18 01:15:20 mmondor Exp $ */
 
 /*
  * Copyright (C) 2002-2003, Matthew Mondor
 
 
 
-#ifndef mmstat_t_H
-#define mmstat_t_H
+#ifndef MMSTAT_H
+#define MMSTAT_H
 
 
 
 
-/* HEADERS */
-
 #include <sys/types.h>
 
 #include <mmtypes.h>
 #include <mmlist.h>
 #include <mmpool.h>
+#include <mmhash.h>
 
 
 
 
-/* DEFINITIONS */
-
 #define MAX_TRANSACT   16
 #define KEY_SIZE       128
 
@@ -63,8 +60,6 @@ typedef struct mmstat_report  mmstatres_t;
 
 
 
-/* STRUCTURES */
-
 enum stat_type {
     STAT_TRANSACT = 1,
     STAT_NEWFILE = 2,
@@ -81,29 +76,10 @@ struct mmstat_entry {
     bool persistant;
 };
 
-/* We keep the hash table of the key and rest of data into separate lists so
- * that frequently referenced hash table does not get swapped out of physical
- * memory for speed considerations. The referenced data, only required when
- * a matching hash is found, is potentially larger, and could be partly swapped
- * out by the kernel. It would be possible to mlock() wanted pages but I
- * beleive that it is better to leave physical memory to other processes
- * requireing it, letting the kernel do it's job. The only reason we keep the
- * data nodes in a list as well is to use the mmlist library buffering to
- * speed up allocation/deallocation.
- */
-struct data_node {
-    pnode_t node;
-    mmstatent_t entry;
-};
-struct key_node {
-    pnode_t node;
-    u_int64_t hash;
-    struct data_node *data;
-};
-
 struct log_entry {
     enum stat_type type;
     uid_t uid;
+    time_t time;
     bool persistant, autoflush;
     char key[KEY_SIZE];
     union {
@@ -137,8 +113,8 @@ struct mmstat_report {
 
 struct mmstat_config {
     char USER[32], GROUPS[256], LOG_FACILITY[32], PID_FILE[256],
-        LOCK_FILE[256], LOG_SOCKET[256], STAT_SOCKET[256], ENV_DIR[128],
-        LOG_GROUP[32], STAT_GROUP[32];
+       LOCK_FILE[256], LOG_SOCKET[256], STAT_SOCKET[256], ENV_DIR[128],
+       LOG_GROUP[32], STAT_GROUP[32];
     long SYNC_INTERVAL, SYNC_BYTES, MAX_LOGSIZE, STATS_RATE, STATS_TIME;
     gid_t log_group, stat_group;
     off_t max_logsize;
@@ -147,8 +123,6 @@ struct mmstat_config {
 
 
 
-/* PROTOTYPES */
-
 bool mmstat_initialize(void);
 bool mmstat_init(mmstat_t *, bool, bool);
 bool mmstat(mmstat_t *, enum stat_type, int64_t, const char *, ...);
index 8ffd41b..6f131a0 100644 (file)
@@ -1,4 +1,4 @@
-/* $Id: mmstring.c,v 1.7 2003/03/19 04:20:17 mmondor Exp $ */
+/* $Id: mmstring.c,v 1.8 2003/06/18 01:15:20 mmondor Exp $ */
 
 /*
  * Copyright (C) 1989-2003, Matthew Mondor
@@ -58,7 +58,7 @@
 
 MMCOPYRIGHT("@(#) Copyright (c) 2002-2003\n\
 \tMatthew Mondor. All rights reserved.\n");
-MMRCSID("$Id: mmstring.c,v 1.7 2003/03/19 04:20:17 mmondor Exp $");
+MMRCSID("$Id: mmstring.c,v 1.8 2003/06/18 01:15:20 mmondor Exp $");
 
 static const unsigned char toupper_table[] = {
     0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 
@@ -688,7 +688,7 @@ mm_memhash64(void *mem, size_t size)
  */
 
 
-bool
+int
 mm_memcmp(const void *dest, const void *src, size_t len)
 {
     register const char *ptr, *toptr, *dptr;
@@ -697,6 +697,8 @@ mm_memcmp(const void *dest, const void *src, size_t len)
     toptr += len;
     dptr = dest;
 
+#define RET(a, b)      return (int)(*(--(a)) - *(--(b)))
+
 #if defined(ARCH_INT8)
 
 #if !defined(ARCH_LOWCACHE)
@@ -704,11 +706,11 @@ mm_memcmp(const void *dest, const void *src, size_t len)
        if (*ptr++ != *dptr++ || *ptr++ != *dptr++ || *ptr++ != *dptr++ ||
            *ptr++ != *dptr++ || *ptr++ != *dptr++ || *ptr++ != *dptr++ ||
            *ptr++ != *dptr++ || *ptr++ != *dptr++)
-           return (FALSE);
+           RET(ptr, dptr);
 #endif                         /* !defined(ARCH_LOWCACHE) */
     while (ptr < toptr)
        if (*ptr++ != *dptr++)
-           return (FALSE);
+           RET(ptr, dptr);
 
 #else                          /* defined(ARCH_INT8) */
 
@@ -719,11 +721,11 @@ mm_memcmp(const void *dest, const void *src, size_t len)
                || *ptr++ != *dptr++ || *ptr++ != *dptr++
                || *ptr++ != *dptr++ || *ptr++ != *dptr++
                || *ptr++ != *dptr++)
-               return (FALSE);
+               RET(ptr, dptr);
 #endif                         /* !defined(ARCH_LOWCACHE) */
        while (ptr < toptr)
            if (*ptr++ != *dptr++)
-               return (FALSE);
+               RET(ptr, dptr);
     } else {
        register const int *lptr, *ltoptr, *ldptr, *ldtoptr;
        register const char *dtoptr;
@@ -739,29 +741,31 @@ mm_memcmp(const void *dest, const void *src, size_t len)
 
        while (ptr < (const char *)lptr)
            if (*ptr++ != *dptr++)
-               return (FALSE);
+               RET(ptr, dptr);
 #if !defined(ARCH_LOWCACHE)
        while (lptr < ltoptr - (sizeof(int) * 8)) {
            if (*ptr++ != *dptr++ || *ptr++ != *dptr++ || *ptr++ != *dptr++
                || *ptr++ != *dptr++ || *ptr++ != *dptr++
                || *ptr++ != *dptr++ || *ptr++ != *dptr++
                || *ptr++ != *dptr++)
-               return (FALSE);
+               RET(ptr, dptr);
        }
 #endif                         /* !defined(ARCH_LOWCACHE) */
        while (lptr < ltoptr)
            if (*lptr++ != *ldptr++)
-               return (FALSE);
+               RET(lptr, ldptr);
        ptr = (const char *)lptr;
        dptr = (const char *)ldptr;
        while (ptr < toptr)
            if (*ptr++ != *dptr++)
-               return (FALSE);
+               RET(ptr, dptr);
     }
 
 #endif                         /* !defined(ARCH_INT8) */
 
-    return (TRUE);
+#undef RET
+
+    return (0);
 }
 
 
index 53d8523..60fdcd5 100644 (file)
@@ -1,4 +1,4 @@
-/* $Id: mmstring.h,v 1.6 2003/02/13 00:12:31 mmondor Exp $ */
+/* $Id: mmstring.h,v 1.7 2003/06/18 01:15:20 mmondor Exp $ */
 
 /*
  * Copyright (C) 2000-2003, Matthew Mondor
@@ -87,7 +87,7 @@ u_int64_t mm_strhash64(char *);
 u_int64_t mm_memhash64(void *, size_t);
 
 
-bool mm_memcmp(const void *, const void *, size_t);
+int mm_memcmp(const void *, const void *, size_t);
 void mm_memcpy(void *, const void *, size_t);
 void mm_memmov(void *, const void *, size_t);
 void mm_memset(void *, char, size_t);
index 31d17a7..aa120a1 100644 (file)
@@ -1,17 +1,21 @@
-$Id: ChangeLog,v 1.16 2003/06/04 06:00:16 mmondor Exp $
+$Id: ChangeLog,v 1.17 2003/06/18 01:15:20 mmondor Exp $
 
 
 
 Release: mmmail 0.0.22 devl
-Date   : April 25, 2003
+Date   : June 16, 2003
 By     : Matthew Mondor
 
-* Fix requireing a minor configuration file change
-  - The GROUPS directive now expects groups to be comma-separated instead of
-    space-separated. The quotes then of course also become optional if multiple
-    groups are specified. This was made because that mmreadcfg(3) library is
-    also used by other of my projects for which comma-separated groups were
-    required.
+* Important
+  - Important changes to mmstat(3) and mmstatd(8) were made which require a
+    database synchronization procedure to be performed before upgrading.
+    See mmstatd/ChangeLog for details.
+  - The GROUPS directive in mmsmtpd.conf(5), mmpop3d.conf(5) and
+    mmstatd.conf(5) now expect groups to be comma-separated instead of
+    space-separated. The quotes then of course also become optional if
+    multiple groups are specified. This was made because mmreadcfg(3) library
+    is also used by other of my projects for which comma-separated groups
+    were also required.
 * Various
   - Fixed ALIGN_CEIL alignment macros which used to always add bytes even
     if the value was already aligned properly. As a result a few bytes of
@@ -20,6 +24,18 @@ By     : Matthew Mondor
     mmftpd was migrated to use the new ones.
   - When an alias points to an invalid address, an error is now logged about
     it for the administrator to notice and delete the alias.
+  - mmstatd will now perform much better when used with a large number of
+    keys, and will now retain the real time of the operation if it had to
+    be killed before it can incorporate the recovery logs and sync.
+  - mmsmtpd now uses mmhash(3) for it's FLOOD_PROTECTION cache which enhances
+    performance when many hosts are in the cache, and yields cleaner code.
+    As the number of RCPTs allowed per post is generally small, it still uses
+    linked lists for those with the old 64-bit hash for faster comparition,
+    but sequencial searching is still performed when checking against
+    duplicates. This will change if I ever obtain a request about someone who
+    needs to use enough RCPTs in a post to use a hash table for performance.
+  - mmhash(3) is now used by mmserver(3) as well, which should enhance 
+    connection validity and DNS hostname cache performance.
 * Bug fixes
   - The SQL SELECT statement in mmpop3d's auth_pass() function was erroneous
     and often caused POP3 authentication problems. Fixed.
index 1f917f7..137249c 100755 (executable)
@@ -1,5 +1,5 @@
 #!/bin/sh
-# $Id: install.sh,v 1.4 2003/03/28 21:09:29 mmondor Exp $
+# $Id: install.sh,v 1.5 2003/06/18 01:15:20 mmondor Exp $
 
 if [ "$1" = "help" ]; then
        echo
@@ -99,6 +99,7 @@ instman mmfd.3 3
 instman mmlist.3 3
 instman mmpool.3 3
 instman mmstat.3 3
+instman mmhash.3 3
 cd ../
 
 cd mmpasswd/
@@ -149,7 +150,7 @@ echo "*** Please read the following man pages ***"
 echo
 echo "mmstat(8), mmstatd(8), mmstatd.conf(5) mmpasswd(8)"
 echo "mmmail(8), mmsmtpd(8), mmsmtpd.conf(5), mmpop3d(8) mmpop3d.conf(5)"
-echo "source auditors: mmstat(3), mmfd(3), mmlist(3), mmpool(3)"
+echo "source auditors: mmstat(3), mmfd(3), mmlist(3), mmpool(3), mmhash(3)"
 echo
 echo "Thank you for using mmsoftware."
 echo
index c279a9c..7eb4d39 100644 (file)
@@ -1,4 +1,4 @@
-/* $Id: mmsmtpd.c,v 1.17 2003/06/04 06:00:16 mmondor Exp $ */
+/* $Id: mmsmtpd.c,v 1.18 2003/06/18 01:15:20 mmondor Exp $ */
 
 /*
  * Copyright (C) 2001-2003, Matthew Mondor
@@ -74,7 +74,7 @@
 
 MMCOPYRIGHT("@(#) Copyright (c) 2002-2003\n\
 \tMatthew Mondor. All rights reserved.\n");
-MMRCSID("$Id: mmsmtpd.c,v 1.17 2003/06/04 06:00:16 mmondor Exp $");
+MMRCSID("$Id: mmsmtpd.c,v 1.18 2003/06/18 01:15:20 mmondor Exp $");
 
 
 
@@ -125,10 +125,10 @@ static int LOGLEVEL;
 static pool_t cpool;
 static pth_mutex_t cpool_lock;
 
-/* Used for flood protection cache */
+/* Used for the flood protection cache */
 static pool_t mpool;
-static list_t mlist;
-static pth_mutex_t mlist_lock;
+static hashtable_t mtable;
+static pth_mutex_t mtable_lock;
 
 /* Used for rcpt allocation buffering */
 static pool_t rpool;
@@ -294,6 +294,8 @@ main(int argc, char **argv)
        _pth_thread_yield
     };
     mmstat_t vstat;
+    pth_t mtable_thread = NULL;
+    pth_attr_t threadattr;
 
     /* Set defaults */
     *CONF.CHROOT_DIR = 0;
@@ -421,7 +423,7 @@ main(int argc, char **argv)
     pth_init();
     async_init_pth();
     pth_mutex_init(&cpool_lock);
-    pth_mutex_init(&mlist_lock);
+    pth_mutex_init(&mtable_lock);
     pth_mutex_init(&rpool_lock);
     pth_mutex_init(&mutexes_lock);
 
@@ -438,13 +440,18 @@ main(int argc, char **argv)
     /* Rate nodes */
     if (CONF.FLOOD_PROTECTION) {
        pool_init(&mpool, malloc, free, sizeof(mnode), CONF.FLOOD_CACHE, 1, 1);
-       LIST_INIT(&mlist);
+       hashtable_init(&mtable, CONF.FLOOD_CACHE, 1, malloc, free, mm_memcmp,
+               hashtable_hash);
+       threadattr = pth_attr_new();
+       pth_attr_set(threadattr, PTH_ATTR_JOINABLE, TRUE);
+       mtable_thread = pth_spawn(threadattr, mnode_expire_thread, NULL);
     }
     /* mmstr nodes */
     strlist = mmstrinit(malloc, free, 65536 * CONF.ALLOC_BUFFERS);
 
     if (POOL_VALID(&cpool) && POOL_VALID(&rpool) && POOL_VALID(&pmutexes) &&
-           strlist && (!CONF.FLOOD_PROTECTION || POOL_VALID(&mpool))) {
+           strlist && (!CONF.FLOOD_PROTECTION || (POOL_VALID(&mpool) &&
+                   HASHTABLE_VALID(&mtable) && mtable_thread != NULL))) {
        fdbcinit(&gfdf, &fdbc, CONF.GBANDWIDTH_IN * 1024,
                CONF.GBANDWIDTH_OUT * 1024);
        mmsql_init(&mmsqlfuncs);
@@ -465,6 +472,11 @@ main(int argc, char **argv)
     }
 
     if (strlist) mmstrexit();
+    if (mtable_thread != NULL) {
+       pth_abort(mtable_thread);
+       pth_join(mtable_thread, NULL);
+    }
+    if (HASHTABLE_VALID(&mtable)) hashtable_destroy(&mtable, FALSE);
     if (POOL_VALID(&pmutexes)) pool_destroy(&pmutexes);
     if (POOL_VALID(&mpool)) pool_destroy(&mpool);
     if (POOL_VALID(&rpool)) pool_destroy(&rpool);
@@ -757,57 +769,25 @@ all_rcpt(clientenv *clenv)
        }
     }
 
-    /* If CONF.FLOOD_PROTECTION is on, make sure that we respect the rate
-     * of CONF.FLOOD_MESSAGES within CONF.FLOOD_EXPIRES for this client
+    /* If CONF.FLOOD_PROTECTION is TRUE, make sure that we respect the rate
+     * of CONF.FLOOD_MESSAGES within CONF.FLOOD_EXPIRES for this client.
      */
     if (valid && CONF.FLOOD_PROTECTION) {
-       register mnode *mnod, *next;
-       register int cnt;
-       register u_int64_t hash;
-       register time_t t;
+       register mnode *mnod;
+       register size_t len;
+       register char *entry;
 
-       cnt = 0;
-       if (clenv->c_hostname) hash = mm_strhash64(clenv->c_hostname);
-       else hash = mm_strhash64(clenv->c_ipaddr);
-       t = time(NULL);
+       if (clenv->c_hostname != NULL)
+           entry = clenv->c_hostname;
+       else
+           entry = clenv->c_ipaddr;
+       len = mm_strlen(entry);
 
-       pth_mutex_acquire(&mlist_lock, FALSE, NULL);
+       pth_mutex_acquire(&mtable_lock, FALSE, NULL);
        /* First acquire our mnode, or create it if required */
-       mnod = (mnode *)mlist.top;
-       while (mnod) {
-           next = (mnode *)mnod->node.node.next;
-           if (mnod->expires < t) {
-               /* This entry has expired, expunge it */
-               LIST_UNLINK(&mlist, (node_t *)mnod);
-               pool_free((pnode_t *)mnod);
-           } else if (mnod->hash == hash) break;
-           /* Of course as we still are holding the mutex another
-            * thread in the same state would wait still...
-            */
-           cnt++;
-           if (cnt > 64) {
-               cnt = 0;
-               pth_yield(NULL);
-           }
-           mnod = next;
-       }
-
-       if (!mnod) {
-           /* Create a new mnode since none matched */
-           if ((mnod = (mnode *)pool_alloc(&mpool, FALSE)) != NULL) {
-               mnod->hash = hash;
-               mnod->expires = t + (CONF.FLOOD_EXPIRES * 60);
-               mnod->posts = 1;
-               LIST_APPEND(&mlist, (node_t *)mnod);
-           } else {
-               valid = FALSE;
-               reason = RCPT_FLOOD;
-               mmsyslog(0, LOGLEVEL, "* FLOOD_CACHE not large enough");
-           }
-       } else {
-           /* We found a cached entry for this client,
-            * check limits and update.
-            */
+       if ((mnod = (mnode *)hashtable_find(&mtable, entry, len + 1))
+               != NULL) {
+           /* Found, check and update limits */
            mnod->posts++;
            if (mnod->posts > CONF.FLOOD_MESSAGES) {
                valid = FALSE;
@@ -817,8 +797,20 @@ all_rcpt(clientenv *clenv)
 within last %ld minute(s))", clenv->id, mnod->posts,
                        CONF.FLOOD_EXPIRES);
            }
+       } else {
+           /* Create a new entry */
+           if ((mnod = (mnode *)pool_alloc(&mpool, FALSE)) != NULL) {
+               mm_memcpy(mnod->host, entry, len + 1);
+               mnod->expires = time(NULL) + (CONF.FLOOD_EXPIRES * 60);
+               mnod->posts = 1;
+               hashtable_link(&mtable, (hashnode_t *)mnod, entry, len + 1);
+           } else {
+               valid = FALSE;
+               reason = RCPT_FLOOD;
+               mmsyslog(0, LOGLEVEL, "* FLOOD_CACHE not large enough");
+           }
        }
-       pth_mutex_release(&mlist_lock);
+       pth_mutex_release(&mtable_lock);
 
        if (!valid && CONF.STATFAIL_FLOOD)
            mmstat(&clenv->pstat, STAT_UPDATE, 1,
@@ -1809,3 +1801,65 @@ a_res_query(clientenv *clenv, const char *dname, int class, int type,
 
     return (res);
 }
+
+
+/* Here consists of our mnode expiration thread. It asynchroneously and
+ * occasionally iterating through all the nodes to reset and/or expunge the
+ * expired ones. Doing this here prevents interfering with the normally more
+ * frequent lookups which can be done with hashtable_find() in another thread.
+ * We wouln't want those to need to iterate through all the nodes everytime.
+ */
+/* ARGSUSED */
+static void *
+mnode_expire_thread(void *args)
+{
+    struct mnode_expire_thread_iterator_udata data;
+
+    /* Set the initial timeout to the maximum allowed */
+    data.soonest = time(NULL) + CONF.FLOOD_EXPIRES;
+    data.cnt = 0;
+    for (;;) {
+       /* Sleep until it is known that at least one node expired */
+       pth_sleep(data.soonest - time(NULL));
+       /* Tell our iterator function the current time and the maximum
+        * allowed time to wait to
+        */
+       data.current = time(NULL);
+       data.soonest = data.current + CONF.FLOOD_EXPIRES;
+       /* Lock mtable, expunge expired nodes and set data.soonest to the
+        * time of the soonest next expireing node
+        */
+       pth_mutex_acquire(&mtable_lock, FALSE, NULL);
+       hashtable_iterate(&mtable, mnode_expire_thread_iterator, &data);
+       pth_mutex_release(&mtable_lock);
+    }
+
+    /* NOTREACHED */
+    pth_exit(NULL);
+    return NULL;
+}
+
+
+static bool
+mnode_expire_thread_iterator(hashnode_t *hnod, void *udata)
+{
+    mnode *mnod = (mnode *)hnod;
+    struct mnode_expire_thread_iterator_udata *data = udata;
+
+    if (mnod->expires < data->current) {
+       /* This entry expired, expunge it */
+       hashtable_unlink(&mtable, (hashnode_t *)mnod, FALSE);
+       pool_free((pnode_t *)mnod);
+    } else {
+       /* We must find and record the soonest expireing node */
+       if (data->soonest > mnod->expires)
+           data->soonest = mnod->expires;
+    }
+    /* If the cache is big, prevent from interfering with other threads */
+    if ((data->cnt++) == 64) {
+       data->cnt = 0;
+       pth_yield(NULL);
+    }
+
+    return TRUE;
+}
index ce06228..0715eb8 100644 (file)
@@ -1,4 +1,4 @@
-/* $Id: mmsmtpd.h,v 1.12 2003/05/28 06:39:45 mmondor Exp $ */
+/* $Id: mmsmtpd.h,v 1.13 2003/06/18 01:15:20 mmondor Exp $ */
 
 /*
  * Copyright (C) 2000-2003, Matthew Mondor
@@ -50,6 +50,7 @@
 #include <mmtypes.h>
 #include <mmlist.h>
 #include <mmpool.h>
+#include <mmhash.h>
 #include <mmserver.h>
 #include <mmfd.h>
 #include <mmstat.h>
@@ -157,17 +158,22 @@ typedef struct rcptnode {
     u_int64_t hash;
 } rcptnode;
 
-/* This structure is used to keep a cache of recent boxes for which mail was
+/* This structure is used to keep a cache of recent hosts from which mail was
  * received, along with information on it to determine if the rate of messages
  * is too high.
  */
 typedef struct mnode {
-    pnode_t node;
-    u_int64_t hash;            /* 64-bit hash of host address or name */
+    hashnode_t node;
+    char host[128];            /* Hostname */
     time_t expires;            /* Time entry will expire */
     long posts;                        /* How many posts since entry creation */
 } mnode;
 
+struct mnode_expire_thread_iterator_udata {
+    time_t current, soonest;
+    int cnt;
+};
+
 /* Used for mmfd thread support delegation/abstraction */
 struct mutexnode {
     pnode_t node;
@@ -263,6 +269,9 @@ static void _pth_thread_yield(void);
 static void async_resquery(struct async_msg *);
 static int a_res_query(clientenv *, const char *, int, int, u_char *, int);
 
+static void *mnode_expire_thread(void *);
+static bool mnode_expire_thread_iterator(hashnode_t *, void *);
+
 
 
 
index 5a39085..bd177f3 100644 (file)
@@ -1,20 +1,50 @@
-$Id: ChangeLog,v 1.3 2003/06/04 06:00:16 mmondor Exp $
+$Id: ChangeLog,v 1.4 2003/06/18 01:15:20 mmondor Exp $
 
 
 
 Release: mmstatd 0.0.7 devl
-Date   : April 25, 2003
+Date   : June 16, 2003
 By     : Matthew Mondor
 
-* Fix requireing a minor configuration file change
+* Important
+  - The recovery log format has changed. This means that when upgrading,
+    you should first make sure that your actual database is in sync.
+    There are two ways to do this a) kill mmstatd using SIGTERM and
+    restart it again, or b) perform any rotation operation, which forces a
+    full sync. You can then kill mmstatd and upgrade it. Failure to follow
+    these instructions may result in mmstatd crashing, and yielding undefined
+    behavior. Moreover, both mmstat clients (the shell standard mmstat client,
+    as well as any other application using the mmstat(3) interface, and the
+    mmstatd server need to be recompiled when upgrading.
+  - MMSTAT, MMSTATENT and MMSTATRES data types were changed to mmstat_t,
+    mmstatent_t and mmstatres_t for consistency with other mmsoftware style.
+    This will require minor modifications to software using the mmstat(3) API.
   - The GROUPS directive now expects groups to be comma-separated instead of
     space-separated. The quotes then of course also become optional if multiple
     groups are specified. This was made because that mmreadcfg(3) library is
     also used by other of my projects for which comma-separated groups were
     required.
-* Minor interface change
-  - MMSTAT, MMSTATENT and MMSTATRES data types were changed to mmstat_t,
-    mmstatent_t and mmstatres_t for consistency with other mmsoftware style.
+* Performance enhancement
+  - The system used to hold the keys into a sequencial linked list using a
+    64-bit hash coupled with the key strings to make the list lookup faster.
+    Although this worked fine and was ideal for very small sets, it would
+    become a bottleneck for the librarian process when in heavy use with
+    a very large number of entries. It now uses a 32-bit string hash function,
+    but also a bucket-based hashing algorithm to store the entries which
+    provides fast indexing, considerably speeding up lookups. Moreover, the
+    32-bit string hashing function collisions will not cause storage
+    collisions and is faster than the 64-bit one used to be on 32-bit systems.
+    The mmhash(3) library is used for this, which was imported from my
+    Xisop project.
+* Bug fixes
+  - The default shell mmstat client would always force autoflush on updates
+    even if the 'a' flag was not specified.
+  - Because full disk database synchronization happen rarely, when mmstatd
+    is stopped and restarted, if alot of recent modifications were made which
+    are in the recover logs, their modification timestamps would only be
+    considered when recovering from those logs at mmstatd startup. The time
+    of each operation is now stored within the logs as well, so that at
+    recovery they be applied the real modification time.
 
 
 
index 372b386..29a72ed 100755 (executable)
@@ -1,5 +1,5 @@
 #!/bin/sh
-# $Id: install.sh,v 1.3 2003/03/28 21:09:29 mmondor Exp $
+# $Id: install.sh,v 1.4 2003/06/18 01:15:20 mmondor Exp $
 
 if [ "$1" = "help" ]; then
        echo
@@ -85,6 +85,7 @@ cd ../mmlib/
 instman mmlist.3 3
 instman mmpool.3 3
 instman mmstat.3 3
+instman mmhash.3 3
 cd ../
 
 cd mmstatd/src/
@@ -107,7 +108,7 @@ echo
 echo "*** Please read the following man pages ***"
 echo
 echo "mmstat(8), mmstatd(8), mmstatd.conf(5)"
-echo "source auditors: mmstat(3), mmlist(3), mmpool(3)"
+echo "source auditors: mmstat(3), mmlist(3), mmpool(3), mmhash(3)"
 echo
 echo "Thank you for using mmsoftware."
 echo
index 26c6611..7c4568b 100644 (file)
@@ -1,4 +1,4 @@
-/* $Id: mmstat.c,v 1.9 2003/06/04 06:00:17 mmondor Exp $ */
+/* $Id: mmstat.c,v 1.10 2003/06/18 01:15:20 mmondor Exp $ */
 
 /*
  * Copyright (C) 2002-2003, Matthew Mondor
@@ -52,7 +52,7 @@
 
 MMCOPYRIGHT("@(#) Copyright (c) 2002-2003\n\
 \tMatthew Mondor. All rights reserved.\n");
-MMRCSID("$Id: mmstat.c,v 1.9 2003/06/04 06:00:17 mmondor Exp $");
+MMRCSID("$Id: mmstat.c,v 1.10 2003/06/18 01:15:20 mmondor Exp $");
 
 
 
@@ -285,6 +285,9 @@ int stat_reset(int argc, char **argv)
        if (mm_strchr(argv[2], 'p')) persistant = TRUE;
        if (mm_strchr(argv[2], 'v')) persistant = FALSE;
        if (mm_strchr(argv[2], 'a')) autoflush = TRUE;
+       /* XXX */
+       printf("persistant=%s, autoflush=%s\n", persistant ? "TRUE" : "FALSE",
+               autoflush ? "TRUE" : "FALSE");
        if (mmstat_init(&mms, persistant, autoflush)) {
            mmstat_transact(&mms, TRUE);
            for (i = 3; i < argc; i++) {
@@ -323,7 +326,7 @@ stat_update(int argc, char **argv)
        if (mm_strchr(argv[2], 'p')) persistant = TRUE;
        if (mm_strchr(argv[2], 'v')) persistant = FALSE;
        if (mm_strchr(argv[2], 'a')) autoflush = TRUE;
-       if (mmstat_init(&mms, persistant, TRUE)) {
+       if (mmstat_init(&mms, persistant, autoflush)) {
            mmstat_transact(&mms, TRUE);
            for (i = 3; i < argc; i++) {
                arg = argv[i];
index d8fa2af..488700e 100644 (file)
@@ -1,4 +1,4 @@
-/* $Id: mmstatd.c,v 1.10 2003/06/04 06:00:17 mmondor Exp $ */
+/* $Id: mmstatd.c,v 1.11 2003/06/18 01:15:20 mmondor Exp $ */
 
 /*
  * Copyright (C) 2002-2003, Matthew Mondor
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
-/* TODO
+/* TODO:
  * - Finish client packet uid credential checking, credentials have to be
  *   passed through the unix domain socket
- * - Have endian-independant logfile and database formats
+ * - Have endian-independant logfile and database formats (Note: linux has no
+ *   standard 64-bit conversion function it seems, although NetBSD does)
  */
 
 
@@ -67,8 +68,8 @@
 #include <grp.h>
 
 #include <mmtypes.h>
-#include <mmlist.h>
 #include <mmpool.h>
+#include <mmhash.h>
 #include <mmstring.h>
 #include <mmstat.h>
 #include <mmstatd.h>
 
 MMCOPYRIGHT("@(#) Copyright (c) 2002-2003\n\
 \tMatthew Mondor. All rights reserved.\n");
-MMRCSID("$Id: mmstatd.c,v 1.10 2003/06/04 06:00:17 mmondor Exp $");
-
-
-
-
-/* PROTOTYPES */
-
-static pid_t process_spawn(int (*)(void *), void *, bool);
-static void sighandler(int);
-static bool lock_check(const char *);
-static int unix_init(const char *, gid_t, mode_t, int, bool, bool);
-static bool log_match(const char *, const char *);
-static bool logentries_write(int, struct log_entry *, int, int *, long *,
-               off_t *);
-static bool logentry_read(int, struct log_entry *, int *, long *, off_t *);
-static int logentries_read(int, struct log_entry *, int, int *, long *,
-       off_t *);
-static bool logentry_process(struct log_entry *, bool);
-static bool logentries_process(struct log_entry *, int, bool);
-/* static void logentry_debug(char, struct log_entry *); */
-static void db_load(long *, off_t *);
-static bool db_load_v0_0_1(FILE *, long *, long *);
-static bool db_load_v0_0_2(FILE *, long *, off_t *);
-static bool db_load_v0_0_3(FILE *, long *, off_t *);
-static void db_sync(long, off_t, bool);
-static void db_free(void);
-static void db_recover(void);
-static void stats_write(int, char *);
-static void stats_rotate(char *, char *);
-
-int main(int, char **);
-
-static int librarian_init(void *);
-static void librarian_main(int, int, int, long *, off_t *);
-static int logger_init(void *);
-static void logger_main(int, int, int, long *, off_t *);
+MMRCSID("$Id: mmstatd.c,v 1.11 2003/06/18 01:15:20 mmondor Exp $");
 
 
 
@@ -123,10 +89,10 @@ static void logger_main(int, int, int, long *, off_t *);
 
 static struct mmstat_config CONF;
 static pid_t librarian_pid = -1, logger_pid = -1;
-static pool_t key_pool, data_pool;
-static list_t key_list, data_list;
+static pool_t key_pool;
+static hashtable_t key_table;
 static int pipefds[2], syncbytes = 0;
-static bool run = TRUE, pipesend = TRUE, kdirection = TRUE, ddirection = TRUE;
+static bool pipesend = TRUE;
 
 
 
@@ -183,21 +149,17 @@ process_spawn(int (*function)(void *), void *params, bool leader)
 static void
 sighandler(int sig)
 {
-    pid_t pid = getpid();
-
     switch (sig) {
     case SIGTERM:
        syslog(LOG_NOTICE, "Received SIGTERM, cleaning up");
-       run = FALSE;
-       if (librarian_pid != -1 && librarian_pid != pid)
-           kill(librarian_pid, SIGTERM);
-       if (logger_pid != -1 && logger_pid != pid)
-           kill(logger_pid, SIGTERM);
+       signal(SIGTERM, SIG_IGN);
+       kill(0, SIGTERM);
+       exit(0);
        break;
     case SIGSEGV:
        syslog(LOG_NOTICE, "Received SIGSEGV! Cleaning up");
        kill(0, SIGTERM);
-       run = FALSE;
+       exit(0);
        break;
     case SIGPIPE:
        pipesend = FALSE;
@@ -311,7 +273,6 @@ logentries_write(int pfd, struct log_entry *entries, int len, int *fd,
     char filename[256], dat[MAX_TRANSACT];
 
     ok = TRUE;
-
     l = len * sizeof(struct log_entry);
 
     /* First perform logfile rotation if required */
@@ -345,6 +306,14 @@ logentries_write(int pfd, struct log_entry *entries, int len, int *fd,
 
     /* Write our new log entry */
     if (ok) {
+       time_t tim;
+       int i;
+
+       /* Mark entry time */
+       tim = time(NULL);
+       for (i = 0; i < len; i++)
+           entries[i].time = tim;
+       /* Write to logfile */
        if (write(*fd, entries, l) == l) {
            *logpos += l;
            /* A trick to keep resonable physical disk sync rate */
@@ -392,7 +361,7 @@ logentry_read(int pfd, struct log_entry *entry, int *fd, long *lognum,
                    sizeof(struct log_entry))
                ok = TRUE;
        } else {
-           while (run) {
+           for (;;) {
                if ((poll(fds, 1, 5000)) > 0) {
                    if (fds[0].revents & POLLIN) {
                        if ((read(pfd, &c, 1)) == 1) {
@@ -515,146 +484,106 @@ logentries_read(int pfd, struct log_entry *entries, int max, int *fd,
 static bool
 logentry_process(struct log_entry *entry, bool tmp)
 {
-    bool ok;
-    u_int64_t hash;
     enum stat_type type;
 
     /* logentry_debug(':', entry); */
 
-    ok = TRUE;
     type = entry->type;
 
     if (tmp || entry->persistant) {
+       register size_t len;
        register char *ptr;
 
        /* Verify if we should perform wildcard matching and perform an atomic
         * operation on all matching keys
         */
-       for (ptr = entry->key; *ptr; ptr++)
-           if (*ptr == '?' || *ptr == '*') break;
-
-       if (!(*ptr)) {
-           register struct key_node *knod;
-
-           /* Operating on a single key.
-            * Locate corresponding key in db, if any
-            */
-           hash = mm_strhash64(entry->key);
-           if (kdirection) {
-               for (knod = (struct key_node *)key_list.top; knod;
-                       knod = (struct key_node *)knod->node.node.next)
-                   if (knod->hash == hash) break;
-           } else {
-               for (knod = (struct key_node *)key_list.bottom; knod;
-                       knod = (struct key_node *)knod->node.node.prev)
-                   if (knod->hash == hash) break;
-           }
-           kdirection = !kdirection;
-           if (knod) {
-               /* Make sure that uid matches entry creator's. Of course uid 0
-                * has total access.
+       for (ptr = entry->key; *ptr != '\0'; ptr++)
+           if (*ptr == '?' || *ptr == '*')
+               break;
+       len = mm_strlen(entry->key);
+
+       if (*ptr == '\0') {     /* Operation on single key */
+           struct key_node *knod;
+
+           /* Locate corresponding key in table */
+           if ((knod = (struct key_node *)hashtable_find(&key_table,
+                           entry->key, len + 1)) != NULL) {
+               /* Key exists, make sure that UID matches entry creator's or
+                * that operator was UID 0
                 */
-               if (knod->data->entry.uid != entry->uid &&
-                       entry->uid != 0) {
-                   syslog(LOG_NOTICE, "Unauthorized uid!");
-                   ok = FALSE;
-               }
-               if (ok) {
-                   if (type == STAT_DELETE) {
-                       /* Delete entry */
-                       LIST_UNLINK(&data_list, (node_t *)knod->data);
-                       pool_free((pnode_t *)knod->data);
-                       LIST_UNLINK(&key_list, (node_t *)knod);
-                       pool_free((pnode_t *)knod);
-                       return (TRUE);
-                   }
+               if (knod->entry.uid != entry->uid && entry->uid != 0) {
+                   syslog(LOG_NOTICE, "Unauthorized UID!");
+                   return FALSE;
                }
+               if (type == STAT_UPDATE)
+                   knod->entry.value += entry->un.update.modifier;
+               else if(type == STAT_RESET)
+                   knod->entry.value = entry->un.reset.value;
+               if (type == STAT_DELETE || (knod->entry.value == 0 &&
+                           entry->autoflush)) {
+                   /* Delete entry */
+                   hashtable_unlink(&key_table, (hashnode_t *)knod, TRUE);
+                   pool_free((pnode_t *)knod);
+               } else
+                   knod->entry.modified = entry->time;
            } else {
                /* Key does not exist */
-               if (type == STAT_DELETE) return (TRUE);
+               if (type == STAT_DELETE)
+                   return TRUE;
                if (type == STAT_UPDATE || type == STAT_RESET) {
                    if (!(entry->autoflush && (type == STAT_UPDATE ?
                                    entry->un.update.modifier :
                                    entry->un.reset.value) == 0)) {
-                       register struct data_node *dnod;
-
                        /* Create new entry */
-                       if ((dnod = (struct data_node *)pool_alloc(&data_pool,
-                                       FALSE))) {
-                           if ((knod = (struct key_node *)pool_alloc(
-                                           &key_pool, FALSE))) {
-                               mm_strncpy(dnod->entry.key, entry->key,
-                                       KEY_SIZE - 1);
-                               dnod->entry.value = type == STAT_UPDATE ?
-                                   entry->un.update.modifier :
-                                   entry->un.reset.value;
-                               dnod->entry.uid = entry->uid;
-                               dnod->entry.created = dnod->entry.modified =
-                                   time(NULL);
-                               dnod->entry.persistant = entry->persistant;
-                               LIST_APPEND(&data_list, (node_t *)dnod);
-                               knod->hash = hash;
-                               knod->data = dnod;
-                               LIST_APPEND(&key_list, (node_t *)knod);
-                           } else
-                               dnod = (struct data_node *)pool_free(
-                                       (pnode_t *)dnod);
-                       }
-                       if (!dnod || !knod)
-                           return (FALSE);
+                       if ((knod = (struct key_node *)pool_alloc(&key_pool,
+                                       FALSE)) != NULL) {
+                           mm_memcpy(knod->entry.key, entry->key, len + 1);
+                           knod->entry.value = (type == STAT_UPDATE ?
+                               entry->un.update.modifier :
+                               entry->un.reset.value);
+                           knod->entry.uid = entry->uid;
+                           knod->entry.created = knod->entry.modified =
+                               entry->time;
+                           knod->entry.persistant = entry->persistant;
+                           knod->processed = FALSE;
+                           hashtable_link(&key_table, (hashnode_t *)knod,
+                                   knod->entry.key, len + 1);
+                       } else
+                           return FALSE;
                    }
-                   return (ok);
                }
            }
 
-           if (ok) {
-               if (type == STAT_UPDATE)
-                   knod->data->entry.value += entry->un.update.modifier;
-               else if(type == STAT_RESET)
-                   knod->data->entry.value = entry->un.reset.value;
-               if (knod->data->entry.value == 0 && entry->autoflush) {
-                   /* autoflush entry which reached zero, delete it */
-                   LIST_UNLINK(&data_list, (node_t *)knod->data);
-                   pool_free((pnode_t *)knod->data);
-                   LIST_UNLINK(&key_list, (node_t *)knod);
-                   pool_free((pnode_t *)knod);
-               } else
-                   knod->data->entry.modified = time(NULL);
-           }
+       } else          /* Operation on all keys matching pattern */
+           hashtable_iterate(&key_table, logentry_process_iterator, entry);
 
-       } else {
-           register struct key_node *knod, *tknod;
-           register struct data_node *dnod;
-
-           /* Perform operation on all matching keys which belong to us
-            * in an atomic manner.
-            */
-           knod = (struct key_node *)key_list.top;
-           while (knod) {
-               tknod = (struct key_node *)knod->node.node.next;
-               dnod = knod->data;
-               if (dnod->entry.uid == entry->uid &&
-                       log_match(dnod->entry.key, entry->key)) {
-                   if (entry->type == STAT_RESET)
-                       dnod->entry.value = entry->un.reset.value;
-                   else if (type == STAT_UPDATE)
-                       dnod->entry.value += entry->un.update.modifier;
-                   if ((dnod->entry.value == 0 && entry->autoflush) ||
-                           type == STAT_DELETE) {
-                       LIST_UNLINK(&data_list, (node_t *)dnod);
-                       pool_free((pnode_t *)dnod);
-                       LIST_UNLINK(&key_list, (node_t *)knod);
-                       pool_free((pnode_t *)knod);
-                   }
-               }
-               knod = tknod;
-           }
+    }
+
+    return TRUE;
+}
 
-       }
 
+static bool
+logentry_process_iterator(hashnode_t *hnod, void *udata)
+{
+    struct key_node *knod = (struct key_node *)hnod;
+    struct log_entry *entry = udata;
+
+    if ((knod->entry.uid == entry->uid || entry->uid == 0) &&
+           log_match(knod->entry.key, entry->key)) {
+       if (entry->type == STAT_RESET)
+           knod->entry.value = entry->un.reset.value;
+       else if (entry->type == STAT_UPDATE)
+           knod->entry.value += entry->un.update.modifier;
+       if (entry->type == STAT_DELETE || (knod->entry.value == 0 &&
+                   entry->autoflush)) {
+           hashtable_unlink(&key_table, (hashnode_t *)knod, FALSE);
+           pool_free((pnode_t *)knod);
+       } else
+           knod->entry.modified = entry->time;
     }
 
-    return (ok);
+    return TRUE;
 }
 
 
@@ -718,7 +647,6 @@ logentry_debug(char c, struct log_entry *entry)
  * log an error via syslog but will either provide an empty or incomplete
  * db in memory.
  */
-/* XXX Make file format portable among various endian architectures */
 static void
 db_load(long *lognum, off_t *logpos)
 {
@@ -732,11 +660,10 @@ db_load(long *lognum, off_t *logpos)
     *logpos = 0;
 
     snprintf(filename, 255, "%s/mmstatd.db", CONF.ENV_DIR);
-    if (pool_init(&data_pool, malloc, free, sizeof(struct data_node),
-               16384 / sizeof(struct data_node), 0, 0)) {
-       if (pool_init(&key_pool, malloc, free, sizeof(struct key_node),
-                   16384 / sizeof(struct key_node), 0, 0)) {
-           LIST_INIT(&key_list);
+    if (pool_init(&key_pool, malloc, free, sizeof(struct key_node),
+               32768 / sizeof(struct key_node), 0, 0)) {
+       if (hashtable_init(&key_table, HT_DEFAULT_CAPACITY, HT_DEFAULT_FACTOR,
+                   malloc, free, mm_memcmp, hashtable_hash)) {
            if ((fh = fopen(filename, "rb"))) {
                /* We now remember how to load old mmstatd database files,
                 * since at times the format changes accross versions.
@@ -746,38 +673,44 @@ db_load(long *lognum, off_t *logpos)
                if (fread(&ver, sizeof(u_int32_t), 1, fh) == 1) {
                    version = 0xFFFFFFFF - ver;
                    switch (version) {
-                       case 2:
-                           /* mmstatd 0.0.2, db v2 */
-                           ok = db_load_v0_0_2(fh, lognum, logpos);
-                           break;
-                       case 3:
-                           /* mmstatd 0.0.3 db v3 */
-                           ok = db_load_v0_0_3(fh, lognum, logpos);
-                           break;
-                       default:
-                           {
-                               /* First version */
-                               long o_lognum, o_logpos;
-
-                               /* Seek back to start since there was no
-                                * version info back then
-                                */
-                               fseek(fh, 0, SEEK_SET);
-                               ok = db_load_v0_0_1(fh, &o_lognum, &o_logpos);
-                               *lognum = o_lognum;
-                               *logpos = (off_t)o_logpos;
-                           }
-                           break;
+                   case 2:
+                       /* mmstatd 0.0.2, db v2 */
+                       ok = db_load_v0_0_2(fh, lognum, logpos);
+                       break;
+                   case 3:
+                       /* mmstatd 0.0.3 db v3 */
+                       ok = db_load_v0_0_3(fh, lognum, logpos);
+                       break;
+                   case 4:
+                       /* mmstatd 0.0.7 db v4 */
+                       ok = db_load_v0_0_4(fh, lognum, logpos);
+                       break;
+                   default:
+                       {
+                           /* First version */
+                           long o_lognum, o_logpos;
+
+                           /* Seek back to start since there was no
+                            * version info back then
+                            */
+                           fseek(fh, 0, SEEK_SET);
+                           ok = db_load_v0_0_1(fh, &o_lognum, &o_logpos);
+                           *lognum = o_lognum;
+                           *logpos = (off_t)o_logpos;
+                       }
+                       break;
                    }
                } else ok = FALSE;
                fclose(fh);
+               if (!ok)
+                   syslog(LOG_NOTICE,
+                           "db_load() - Error loading database (corrupt)");
            } else
                syslog(LOG_NOTICE, "db_load() - New database");
-       }
-    }
-    if (!ok) {
-       syslog(LOG_NOTICE, "db_load() - Error loading database (corrupt)");
-    }
+       } else
+           syslog(LOG_NOTICE, "db_load() - Out of memory");
+    } else
+       syslog(LOG_NOTICE, "db_load() - Out of memory");
 }
 
 
@@ -785,7 +718,6 @@ static bool
 db_load_v0_0_1(FILE *fh, long *lognum, long *logpos)
 {
     struct key_node *knod = NULL;
-    struct data_node *dnod = NULL;
     u_int64_t hash;
     unsigned char len;
     bool ok = TRUE;
@@ -795,33 +727,32 @@ db_load_v0_0_1(FILE *fh, long *lognum, long *logpos)
        ok = FALSE;
     while (ok) {
        if (fread(&hash, sizeof(u_int64_t), 1, fh) == 1) {
-           if ((dnod = (struct data_node *)pool_alloc(&data_pool, FALSE))) {
-               dnod->entry.persistant = TRUE;
-               if ((knod = (struct key_node *)pool_alloc(&key_pool, FALSE))) {
-                   knod->hash = hash;
-                   knod->data = dnod;
-                   if (fread(&dnod->entry.value, sizeof(int64_t), 1, fh) != 1
-                           || fread(&dnod->entry.created, sizeof(time_t), 1,
-                               fh) != 1
-                           || fread(&dnod->entry.modified, sizeof(time_t), 1,
-                               fh) != 1
-                           || fread(&dnod->entry.uid, sizeof(uid_t), 1,
-                               fh) != 1
-                           || fread(&len, sizeof(unsigned char), 1, fh) != 1
-                           || fread(&dnod->entry.key, len + 1, 1, fh) != 1)
-                       ok = FALSE;
-                   else {
-                       LIST_APPEND(&data_list, (node_t *)dnod);
-                       LIST_APPEND(&key_list, (node_t *)knod);
-                   }
-               } else
+           if ((knod = (struct key_node *)pool_alloc(&key_pool, FALSE))) {
+               knod->entry.persistant = TRUE;
+               knod->processed = FALSE;
+               if (fread(&knod->entry.value, sizeof(int64_t), 1, fh) != 1
+                       || fread(&knod->entry.created, sizeof(time_t), 1,
+                           fh) != 1
+                       || fread(&knod->entry.modified, sizeof(time_t), 1,
+                           fh) != 1
+                       || fread(&knod->entry.uid, sizeof(uid_t), 1,
+                           fh) != 1
+                       || fread(&len, sizeof(unsigned char), 1, fh) != 1
+                       || fread(&knod->entry.key, len + 1, 1, fh) != 1)
                    ok = FALSE;
+               else {
+                   if (!hashtable_link(&key_table, (hashnode_t *)knod,
+                               knod->entry.key, len + 1)) {
+                       syslog(LOG_NOTICE,
+                               "db_load_v0_0_1() - Duplicate key '%s'",
+                               knod->entry.key);
+                       knod = (struct key_node *)pool_free((pnode_t *)knod);
+                   }
+               }
            } else
                ok = FALSE;
-           if (!ok) {
-               if (dnod) pool_free((pnode_t *)dnod);
+           if (!ok)
                if (knod) pool_free((pnode_t *)knod);
-           }
        } else
            break;
     }
@@ -834,7 +765,6 @@ static bool
 db_load_v0_0_2(FILE *fh, long *lognum, off_t *logpos)
 {
     struct key_node *knod = NULL;
-    struct data_node *dnod = NULL;
     u_int64_t hash;
     unsigned char len;
     bool ok = TRUE;
@@ -844,33 +774,32 @@ db_load_v0_0_2(FILE *fh, long *lognum, off_t *logpos)
        ok = FALSE;
     while (ok) {
        if (fread(&hash, sizeof(u_int64_t), 1, fh) == 1) {
-           if ((dnod = (struct data_node *)pool_alloc(&data_pool, FALSE))) {
-               dnod->entry.persistant = TRUE;
-               if ((knod = (struct key_node *)pool_alloc(&key_pool, FALSE))) {
-                   knod->hash = hash;
-                   knod->data = dnod;
-                   if (fread(&dnod->entry.value, sizeof(int64_t), 1, fh) != 1
-                           || fread(&dnod->entry.created, sizeof(time_t), 1,
-                               fh) != 1
-                           || fread(&dnod->entry.modified, sizeof(time_t), 1,
-                               fh) != 1
-                           || fread(&dnod->entry.uid, sizeof(uid_t), 1,
-                               fh) != 1
-                           || fread(&len, sizeof(unsigned char), 1, fh) != 1
-                           || fread(&dnod->entry.key, len + 1, 1, fh) != 1)
-                       ok = FALSE;
-                   else {
-                       LIST_APPEND(&data_list, (node_t *)dnod);
-                       LIST_APPEND(&key_list, (node_t *)knod);
-                   }
-               } else
+           if ((knod = (struct key_node *)pool_alloc(&key_pool, FALSE))) {
+               knod->entry.persistant = TRUE;
+               knod->processed = FALSE;
+               if (fread(&knod->entry.value, sizeof(int64_t), 1, fh) != 1
+                       || fread(&knod->entry.created, sizeof(time_t), 1,
+                           fh) != 1
+                       || fread(&knod->entry.modified, sizeof(time_t), 1,
+                           fh) != 1
+                       || fread(&knod->entry.uid, sizeof(uid_t), 1,
+                           fh) != 1
+                       || fread(&len, sizeof(unsigned char), 1, fh) != 1
+                       || fread(&knod->entry.key, len + 1, 1, fh) != 1)
                    ok = FALSE;
+               else {
+                   if (!hashtable_link(&key_table, (hashnode_t *)knod,
+                               knod->entry.key, len + 1)) {
+                       syslog(LOG_NOTICE,
+                               "db_load_v0_0_2() - Duplicate key '%s'",
+                               knod->entry.key);
+                       knod = (struct key_node *)pool_free((pnode_t *)knod);
+                   }
+               }
            } else
                ok = FALSE;
-           if (!ok) {
-               if (dnod) pool_free((pnode_t *)dnod);
+           if (!ok)
                if (knod) pool_free((pnode_t *)knod);
-           }
        } else
            break;
     }
@@ -883,7 +812,6 @@ static bool
 db_load_v0_0_3(FILE *fh, long *lognum, off_t *logpos)
 {
     struct key_node *knod = NULL;
-    struct data_node *dnod = NULL;
     u_int64_t hash;
     size_t len;
     bool ok = TRUE;
@@ -893,33 +821,78 @@ db_load_v0_0_3(FILE *fh, long *lognum, off_t *logpos)
        ok = FALSE;
     while (ok) {
        if (fread(&hash, sizeof(u_int64_t), 1, fh) == 1) {
-           if ((dnod = (struct data_node *)pool_alloc(&data_pool, FALSE))) {
-               dnod->entry.persistant = TRUE;
-               if ((knod = (struct key_node *)pool_alloc(&key_pool, FALSE))) {
-                   knod->hash = hash;
-                   knod->data = dnod;
-                   if (fread(&dnod->entry.value, sizeof(int64_t), 1, fh) != 1
-                           || fread(&dnod->entry.created, sizeof(time_t), 1,
-                               fh) != 1
-                           || fread(&dnod->entry.modified, sizeof(time_t), 1,
-                               fh) != 1
-                           || fread(&dnod->entry.uid, sizeof(uid_t), 1,
-                               fh) != 1
-                           || fread(&len, sizeof(size_t), 1, fh) != 1
-                           || fread(&dnod->entry.key, len + 1, 1, fh) != 1)
-                       ok = FALSE;
-                   else {
-                       LIST_APPEND(&data_list, (node_t *)dnod);
-                       LIST_APPEND(&key_list, (node_t *)knod);
+           if ((knod = (struct key_node *)pool_alloc(&key_pool, FALSE))) {
+               knod->entry.persistant = TRUE;
+               knod->processed = FALSE;
+               if (fread(&knod->entry.value, sizeof(int64_t), 1, fh) != 1
+                       || fread(&knod->entry.created, sizeof(time_t), 1,
+                           fh) != 1
+                       || fread(&knod->entry.modified, sizeof(time_t), 1,
+                           fh) != 1
+                       || fread(&knod->entry.uid, sizeof(uid_t), 1,
+                           fh) != 1
+                       || fread(&len, sizeof(size_t), 1, fh) != 1
+                       || fread(&knod->entry.key, len + 1, 1, fh) != 1)
+                   ok = FALSE;
+               else {
+                   if (!hashtable_link(&key_table, (hashnode_t *)knod,
+                               knod->entry.key, len + 1)) {
+                       syslog(LOG_NOTICE,
+                               "db_load_v0_0_3() - Duplicate key '%s'",
+                               knod->entry.key);
+                       knod = (struct key_node *)pool_free((pnode_t *)knod);
                    }
-               } else
+               }
+           } else
+               ok = FALSE;
+           if (!ok)
+               if (knod) pool_free((pnode_t *)knod);
+       } else
+           break;
+    }
+
+    return (ok);
+}
+
+
+static bool
+db_load_v0_0_4(FILE *fh, long *lognum, off_t *logpos)
+{
+    struct key_node *knod = NULL;
+    int64_t val;
+    size_t len;
+    bool ok = TRUE;
+
+    if (fread(lognum, sizeof(long), 1, fh) != 1 ||
+           fread(logpos, sizeof(off_t), 1, fh) != 1)
+       ok = FALSE;
+    while (ok) {
+       if (fread(&val, sizeof(int64_t), 1, fh) == 1) {
+           if ((knod = (struct key_node *)pool_alloc(&key_pool, FALSE))) {
+               knod->entry.persistant = TRUE;
+               knod->entry.value = val;
+               knod->processed = FALSE;
+               if (fread(&knod->entry.created, sizeof(time_t), 1, fh) != 1
+                       || fread(&knod->entry.modified, sizeof(time_t), 1,
+                           fh) != 1
+                       || fread(&knod->entry.uid, sizeof(uid_t), 1,
+                           fh) != 1
+                       || fread(&len, sizeof(size_t), 1, fh) != 1
+                       || fread(&knod->entry.key, len + 1, 1, fh) != 1)
                    ok = FALSE;
+               else {
+                   if (!hashtable_link(&key_table, (hashnode_t *)knod,
+                               knod->entry.key, len + 1)) {
+                       syslog(LOG_NOTICE,
+                               "db_load_v0_0_4() - Duplicate key '%s'",
+                               knod->entry.key);
+                       knod = (struct key_node *)pool_free((pnode_t *)knod);
+                   }
+               }
            } else
                ok = FALSE;
-           if (!ok) {
-               if (dnod) pool_free((pnode_t *)dnod);
+           if (!ok)
                if (knod) pool_free((pnode_t *)knod);
-           }
        } else
            break;
     }
@@ -940,10 +913,9 @@ db_sync(long lognum, off_t logpos, bool all)
     char old_db[256], new_db[256];
     FILE *fh;
     DIR *dir;
-    struct key_node *knod;
-    size_t len;
-    u_int32_t version = 0xFFFFFFFF - 3;
+    u_int32_t version = 0xFFFFFFFF - 4;
     bool ok;
+    struct db_sync_iterator_udata data;
 
     /* We use a technique which permits to retrieve the previous state of
      * the db in case we could not save properly, using rename().
@@ -961,29 +933,10 @@ db_sync(long lognum, off_t logpos, bool all)
                fwrite(&lognum, sizeof(long), 1, fh) == 1 &&
                fwrite(&logpos, sizeof(off_t), 1, fh) == 1) {
            /* DB contents */
-           for (knod = (struct key_node *)key_list.top; knod && ok;
-                   knod = (struct key_node *)knod->node.node.next) {
-               len = mm_strlen(knod->data->entry.key);
-               if (knod->data->entry.persistant) {
-                   if (fwrite(&knod->hash, sizeof(u_int64_t), 1, fh)
-                           != 1 ||
-                           fwrite(&knod->data->entry.value,
-                               sizeof(int64_t), 1, fh) != 1 ||
-                           fwrite(&knod->data->entry.created, sizeof(time_t),
-                               1, fh) != 1 ||
-                           fwrite(&knod->data->entry.modified, sizeof(time_t),
-                               1, fh) != 1 ||
-                           fwrite(&knod->data->entry.uid, sizeof(uid_t), 1,
-                               fh) != 1 ||
-                           fwrite(&len, sizeof(size_t), 1, fh) != 1 ||
-                           fwrite(knod->data->entry.key, len + 1, 1, fh)
-                           != 1) {
-                       ok = FALSE;
-                       break;
-                   }
-               }
-           }
-           kdirection = TRUE;
+           data.fh = fh;
+           data.ok = TRUE;
+           hashtable_iterate(&key_table, db_sync_iterator, &data);
+           ok = data.ok;
        } else
            ok = FALSE;
        fflush(fh);
@@ -994,8 +947,10 @@ db_sync(long lognum, off_t logpos, bool all)
     if (ok)
        if (rename(new_db, old_db) == -1) ok = FALSE;
 
-    if (!ok) unlink(new_db);
-    else {
+    if (!ok) {
+       unlink(new_db);
+       syslog(LOG_NOTICE, "db_sync() - Error writing database!");
+    } else {
        /* Scan for recovery logs and unlink obsolete ones */
        if ((dir = opendir(CONF.ENV_DIR))) {
            char *name, filename[256];
@@ -1018,13 +973,39 @@ db_sync(long lognum, off_t logpos, bool all)
 }
 
 
+static bool
+db_sync_iterator(hashnode_t *hnod, void *udata)
+{
+    struct key_node *knod = (struct key_node *)hnod;
+    struct db_sync_iterator_udata *data = udata;
+    FILE *fh = data->fh;
+
+    if (knod->entry.persistant) {
+       size_t len;
+
+       len = mm_strlen(knod->entry.key);
+       if (fwrite(&knod->entry.value, sizeof(int64_t), 1, fh) != 1 ||
+               fwrite(&knod->entry.created, sizeof(time_t), 1, fh) != 1 ||
+               fwrite(&knod->entry.modified, sizeof(time_t), 1, fh) != 1 ||
+               fwrite(&knod->entry.uid, sizeof(uid_t), 1, fh) != 1 ||
+               fwrite(&len, sizeof(size_t), 1, fh) != 1 ||
+               fwrite(knod->entry.key, len + 1, 1, fh) != 1) {
+           data->ok = FALSE;
+           return FALSE;
+       }
+    }
+
+    return TRUE;
+}
+
+
 static void
 db_free(void)
 {
-    if (POOL_VALID(&data_pool)) pool_destroy(&data_pool);
-    LIST_INIT(&data_list);
-    if (POOL_VALID(&key_pool)) pool_destroy(&key_pool);
-    LIST_INIT(&key_list);
+    if (HASHTABLE_VALID(&key_table))
+       hashtable_destroy(&key_table, FALSE);
+    if (POOL_VALID(&key_pool))
+       pool_destroy(&key_pool);
 }
 
 
@@ -1065,8 +1046,7 @@ db_recover(void)
                break;
            }
        close(fd);
-    } else
-       syslog(LOG_NOTICE, "db_recover() - open(%s)", filename);
+    }
 
     /* Sync back db to disk and delete obsolete recovery logs */
     lognum = 0;
@@ -1078,12 +1058,9 @@ db_recover(void)
 
 /* key char array should be KEY_SIZE bytes in size */
 static void
-stats_write(int fd, char *key)
+stats_write(int fd, const char *key)
 {
-    u_int64_t hash;
-    struct data_node *dnod;
     struct key_node *knod;
-    char *ptr;
 
     /* Sanity check */
     if (key[KEY_SIZE - 1] == '\0') {
@@ -1092,38 +1069,26 @@ stats_write(int fd, char *key)
         */
        if (*key == '\0') {
            /* Full statistics report request */
-           for (dnod = (struct data_node *)data_list.top; dnod && pipesend;
-                   dnod = (struct data_node *)dnod->node.node.next)
-               write(fd, &dnod->entry, sizeof(mmstatent_t));
-           ddirection = 0;
+           hashtable_iterate(&key_table, stats_write_iterator_full, &fd);
        } else {
+           const char *ptr;
+
            for (ptr = key; *ptr; ptr++)
                if (*ptr == '*' || *ptr == '?') break;
            if (*ptr) {
+               struct stats_write_iterator_pattern_udata data;
+
                /* Key pattern matching report request */
-               for (dnod = (struct data_node *)data_list.top;
-                       dnod && pipesend;
-                       dnod = (struct data_node *)dnod->node.node.next) {
-                   if (log_match(dnod->entry.key, key))
-                       write(fd, &dnod->entry, sizeof(mmstatent_t));
-               }
-               ddirection = 0;
+               data.fd = fd;
+               data.pattern = key;
+               hashtable_iterate(&key_table, stats_write_iterator_pattern,
+                       &data);
            } else {
                /* Absolute key report request */
-               hash = mm_strhash64(key);
-               if (kdirection) {
-                   for (knod = (struct key_node *)key_list.top; knod;
-                           knod = (struct key_node *)knod->node.node.next)
-                       if (knod->hash == hash) break;
-               } else {
-                   for (knod = (struct key_node *)key_list.bottom; knod;
-                           knod = (struct key_node *)knod->node.node.prev)
-                       if (knod->hash == hash) break;
-               }
-               kdirection = !kdirection;
-               if (knod && pipesend) {
-                   dnod = knod->data;
-                   write(fd, &dnod->entry, sizeof(mmstatent_t));
+               if ((knod = (struct key_node *)hashtable_find(&key_table, key,
+                               mm_strlen(key) + 1)) != NULL) {
+                   if (pipesend)
+                       write(fd, &knod->entry, sizeof(mmstatent_t));
                }
            }
        }
@@ -1131,25 +1096,101 @@ stats_write(int fd, char *key)
 }
 
 
+static bool
+stats_write_iterator_full(hashnode_t *hnod, void *udata)
+{
+    struct key_node *knod = (struct key_node *)hnod;
+    int fd = *(int *)udata;
+
+    if (pipesend)
+       write(fd, &knod->entry, sizeof(mmstatent_t));
+
+    return pipesend;
+}
+
+
+static bool
+stats_write_iterator_pattern(hashnode_t *hnod, void *udata)
+{
+    struct key_node *knod = (struct key_node *)hnod;
+    struct stats_write_iterator_pattern_udata *data = udata;
+
+    if (pipesend) {
+       if (log_match(knod->entry.key, data->pattern))
+           write(data->fd, &knod->entry, sizeof(mmstatent_t));
+    }
+
+    return pipesend;
+}
+
+
 static void
-stats_rotate(char *pattern, char *prefix)
+stats_rotate(const char *pattern, const char *prefix)
 {
-    struct key_node *knod;
-    char key[KEY_SIZE + 1];
+    char okey[KEY_SIZE + 1], nkey[KEY_SIZE + 1];
 
     /* Sanity check */
     if (pattern[KEY_SIZE - 1] == '\0' && prefix[KEY_SIZE - 1] == '\0') {
-       for (knod = (struct key_node *)key_list.top; knod;
-               knod = (struct key_node *)knod->node.node.next) {
-           if (knod->data->entry.persistant &&
-                   log_match(knod->data->entry.key, pattern)) {
-               snprintf(key, KEY_SIZE - 1, "%s%s", prefix,
-                       knod->data->entry.key);
-               mm_strncpy(knod->data->entry.key, key, KEY_SIZE - 1);
-               knod->hash = mm_strhash64(knod->data->entry.key);
-           }
+       struct stats_rotate_iterator_process_udata data;
+
+       /* Because modifying a key requires to unlink and relink it to the
+        * table, and that the ordering of the iteration is undefined, we
+        * have to make sure not to attempt to process the same entry more
+        * than once, which could still be matching with the pattern.
+        * We therefore use a boolean flag (processed) to prevent this.
+        * Our iterator functions use it.
+        */
+       data.pattern = pattern;
+       data.prefix = prefix;
+       data.okey = okey;
+       data.nkey = nkey;
+       hashtable_iterate(&key_table, stats_rotate_iterator_process, &data);
+       hashtable_iterate(&key_table, stats_rotate_iterator_clear, NULL);
+    }
+}
+
+
+static bool
+stats_rotate_iterator_process(hashnode_t *hnod, void *udata)
+{
+    struct key_node *knod = (struct key_node *)hnod;
+    struct stats_rotate_iterator_process_udata *data = udata;
+
+    /* We make sure to not process already processed keys, and to restore the
+     * old key if the renaming process causes a duplicate.
+     */
+    if (knod->processed == FALSE && knod->entry.persistant &&
+           log_match(knod->entry.key, data->pattern)) {
+       knod->processed = TRUE;
+       mm_memcpy(data->okey, knod->entry.key, KEY_SIZE);
+       hashtable_unlink(&key_table, (hashnode_t *)knod, FALSE);
+       snprintf(data->nkey, KEY_SIZE - 1, "%s%s", data->prefix,
+               knod->entry.key);
+       mm_memcpy(knod->entry.key, data->nkey, KEY_SIZE);
+       if (!hashtable_link(&key_table, (hashnode_t *)knod, knod->entry.key,
+                   mm_strlen(data->nkey) + 1)) {
+           /* Would cause a duplicate, restore entry */
+           syslog(LOG_NOTICE, "stats_rotate() - Rename of key '%s' to '%s' \
+would cause a duplicate", data->okey, data->nkey);
+           mm_memcpy(knod->entry.key, data->okey, KEY_SIZE);
+           hashtable_link(&key_table, (hashnode_t *)knod, knod->entry.key,
+                   mm_strlen(data->okey));
        }
     }
+
+    return TRUE;
+}
+
+
+/* ARGSUSED */
+static bool
+stats_rotate_iterator_clear(hashnode_t *hnod, void *udata)
+{
+    struct key_node *knod = (struct key_node *)hnod;
+
+    knod->processed = FALSE;
+
+    return TRUE;
 }
 
 
@@ -1282,8 +1323,6 @@ main(int argc, char **argv)
 
     /* Initialization */
     librarian_pid = logger_pid = -1;
-    LIST_INIT(&key_list);
-    LIST_INIT(&data_list);
     pipefds[0] = pipefds[1] = -1;
 
     printf("\r\n+++ %s (%s)\r\n\r\n", DAEMON_NAME, DAEMON_VERSION);
@@ -1409,7 +1448,7 @@ librarian_main(int pfd, int ufd, int lfd, long *lognum, off_t *logpos)
 
     ttim = time(NULL);
     secs = cnt = 0;
-    while (run) {
+    for (;;) {
        otim = time(NULL);
        if (poll(fds, 2, 60000) > 0) {
            /* Process more log entries if any */
@@ -1557,7 +1596,7 @@ logger_main(int pfd, int ufd, int lfd, long *lognum, off_t *logpos)
            sizeof(struct log_entry));
     aentries->un.transact.begin = TRUE;
 
-    while (run) {
+    for (;;) {
        if (poll(fds, 1, -1) > 0) {
            if (fds[0].revents & POLLIN) {
                /* New packet to log, may consist of a single operation or
index 3b68937..f46621a 100644 (file)
@@ -1,4 +1,4 @@
-/* $Id: mmstatd.h,v 1.4 2003/03/28 21:09:29 mmondor Exp $ */
+/* $Id: mmstatd.h,v 1.5 2003/06/18 01:15:20 mmondor Exp $ */
 
 /*
  * Copyright (C) 2002-2003, Matthew Mondor
 
 
 
+#include <sys/types.h>
+
+#include <mmtypes.h>
+#include <mmpool.h>
+#include <mmhash.h>
+#include <mmstat.h>
+
+
+
+
 #define DAEMON_NAME    "mmstatd"
 #define DAEMON_VERSION "0.0.7/mmondor"
 
 
 
 
+struct key_node {
+    hashnode_t node;
+    mmstatent_t entry;
+    bool processed;
+};
+
+struct db_sync_iterator_udata {
+    FILE *fh;
+    bool ok;
+};
+
+struct stats_write_iterator_pattern_udata {
+    int fd;
+    const char *pattern;
+};
+
+struct stats_rotate_iterator_process_udata {
+    const char *pattern;
+    const char *prefix;
+    char *okey, *nkey;
+};
+
+
+
+
+static pid_t process_spawn(int (*)(void *), void *, bool);
+static void sighandler(int);
+static bool lock_check(const char *);
+static int unix_init(const char *, gid_t, mode_t, int, bool, bool);
+static bool log_match(const char *, const char *);
+static bool logentries_write(int, struct log_entry *, int, int *, long *,
+               off_t *);
+static bool logentry_read(int, struct log_entry *, int *, long *, off_t *);
+static int logentries_read(int, struct log_entry *, int, int *, long *,
+       off_t *);
+static bool logentry_process(struct log_entry *, bool);
+static bool logentry_process_iterator(hashnode_t *, void *);
+static bool logentries_process(struct log_entry *, int, bool);
+/* static void logentry_debug(char, struct log_entry *); */
+static void db_load(long *, off_t *);
+static bool db_load_v0_0_1(FILE *, long *, long *);
+static bool db_load_v0_0_2(FILE *, long *, off_t *);
+static bool db_load_v0_0_3(FILE *, long *, off_t *);
+static bool db_load_v0_0_4(FILE *, long *, off_t *);
+static void db_sync(long, off_t, bool);
+static bool db_sync_iterator(hashnode_t *, void *);
+static void db_free(void);
+static void db_recover(void);
+static void stats_write(int, const char *);
+static bool stats_write_iterator_full(hashnode_t *, void *);
+static bool stats_write_iterator_pattern(hashnode_t *, void *);
+static void stats_rotate(const char *, const char *);
+static bool stats_rotate_iterator_process(hashnode_t *, void *);
+static bool stats_rotate_iterator_clear(hashnode_t *, void *);
+
+int main(int, char **);
+
+static int librarian_init(void *);
+static void librarian_main(int, int, int, long *, off_t *);
+static int logger_init(void *);
+static void logger_main(int, int, int, long *, off_t *);
+
+
+
+
+
+
 #endif