[MAJOR] remove files distributed under an obscure license
src/chtbl.c, src/hashpjw.c and src/list.c are distributed under
an obscure license. While Aleks and I believe that this license
is OK for haproxy, other people think it is not compatible with
the GPL.
Whether it is or not is not the problem. The fact that it rises
a doubt is sufficient for this problem to be addressed. Arnaud
Cornet rewrote the unclear parts with clean GPLv2 and LGPL code.
The hash algorithm has changed too and the code has been slightly
simplified in the process. A lot of care has been taken in order
to respect the original API as much as possible, including the
LGPL for the exportable parts.
The new code has not been thoroughly tested but it looks OK now.
diff --git a/Makefile b/Makefile
index c5c262e..d607e5c 100644
--- a/Makefile
+++ b/Makefile
@@ -221,7 +221,7 @@
all: haproxy
-OBJS = src/haproxy.o src/list.o src/chtbl.o src/hashpjw.o src/base64.o \
+OBJS = src/haproxy.o src/sessionhash.o src/base64.o \
src/uri_auth.o src/standard.o src/buffers.o src/log.o src/task.o \
src/time.o src/fd.o src/regex.o src/cfgparse.o src/server.o \
src/checks.o src/queue.o src/client.o src/proxy.o \
diff --git a/Makefile.bsd b/Makefile.bsd
index 025bc45..892cdb2 100644
--- a/Makefile.bsd
+++ b/Makefile.bsd
@@ -93,7 +93,7 @@
CFLAGS = -Wall $(COPTS) $(DEBUG)
LDFLAGS = -g
-OBJS = src/haproxy.o src/list.o src/chtbl.o src/hashpjw.o src/base64.o \
+OBJS = src/haproxy.o src/sessionhash.o src/base64.o \
src/uri_auth.o src/standard.o src/buffers.o src/log.o src/task.o \
src/time.o src/fd.o src/regex.o src/cfgparse.o src/server.o \
src/checks.o src/queue.o src/client.o src/proxy.o \
diff --git a/Makefile.osx b/Makefile.osx
index f588478..a920f98 100644
--- a/Makefile.osx
+++ b/Makefile.osx
@@ -90,7 +90,7 @@
CFLAGS = -Wall $(COPTS) $(DEBUG) -isysroot /Developer/SDKs/MacOSX10.4u.sdk -arch ppc -arch i386
LDFLAGS = -g -isysroot /Developer/SDKs/MacOSX10.4u.sdk -arch ppc -arch i386
-OBJS = src/haproxy.o src/list.o src/chtbl.o src/hashpjw.o src/base64.o \
+OBJS = src/haproxy.o src/sessionhash.o src/base64.o \
src/uri_auth.o src/standard.o src/buffers.o src/log.o src/task.o \
src/time.o src/fd.o src/regex.o src/cfgparse.o src/server.o \
src/checks.o src/queue.o src/client.o src/proxy.o \
diff --git a/include/common/appsession.h b/include/common/appsession.h
index 4687298..e77396c 100644
--- a/include/common/appsession.h
+++ b/include/common/appsession.h
@@ -1,15 +1,14 @@
#ifndef _COMMON_APPSESS_H
#define _COMMON_APPSESS_H
-#define TBLSIZ 10
-#define TBLCHKINT 5000 /* The time between two calls of appsession_refresh in ms */
+/*
+ * The time between two calls of appsession_refresh in ms.
+ */
+#define TBLCHKINT 5000
#include <sys/time.h>
-#include <common/chtbl.h>
#include <common/config.h>
-#include <common/hashpjw.h>
-#include <common/list.h>
#include <common/memory.h>
#include <types/task.h>
@@ -19,6 +18,7 @@
char *serverid;
struct timeval expire; /* next expiration time for this application session */
unsigned long int request_count;
+ struct list hash_list;
} appsess;
extern struct pool_head *pool2_appsess;
@@ -36,11 +36,7 @@
int match_str(const void *key1, const void *key2);
/* Callback for destroy */
-void destroy(void *data);
-
-#if defined(DEBUG_HASH)
-static void print_table(const CHTbl *htbl);
-#endif
+void destroy(appsess *data);
void appsession_refresh(struct task *t, struct timeval *next);
int appsession_task_init(void);
diff --git a/include/common/chtbl.h b/include/common/chtbl.h
deleted file mode 100644
index cddb207..0000000
--- a/include/common/chtbl.h
+++ /dev/null
@@ -1,64 +0,0 @@
-/*
- This File is copied from
-
- http://www.oreilly.com/catalog/masteralgoc/index.html
- Mastering Algorithms with C
- By Kyle Loudon
- ISBN: 1-56592-453-3
- Publishd by O'Reilly
-
- */
-
-/*****************************************************************************
-* *
-* ------------------------------- chtbl.h -------------------------------- *
-* *
-*****************************************************************************/
-
-#ifndef _COMMON_CHTBL_H
-#define _COMMON_CHTBL_H
-
-#include <stdlib.h>
-
-#include <common/config.h>
-#include <common/list.h>
-
-/*****************************************************************************
-* *
-* Define a structure for chained hash tables. *
-* *
-*****************************************************************************/
-
-typedef struct CHTbl_ {
-
- int buckets;
-
- int (*h)(const void *key);
- int (*match)(const void *key1, const void *key2);
- void (*destroy)(void *data);
-
- int size;
- List *table;
-} CHTbl;
-
-/*****************************************************************************
- * *
- * --------------------------- Public Interface --------------------------- *
- * *
- *****************************************************************************/
-
-int chtbl_init(CHTbl *htbl, int buckets, int (*h)(const void *key), int
- (*match)(const void *key1, const void *key2), void (*destroy)(void *data));
-
-void chtbl_destroy(CHTbl *htbl);
-
-int chtbl_insert(CHTbl *htbl, const void *data);
-
-int chtbl_remove(CHTbl *htbl, void **data);
-
-int chtbl_lookup(const CHTbl *htbl, void **data);
-
-#define chtbl_size(htbl) ((htbl)->size)
-
-#endif /* _COMMON_CHTBL_H */
-
diff --git a/include/common/hashpjw.h b/include/common/hashpjw.h
deleted file mode 100644
index 8d3998c..0000000
--- a/include/common/hashpjw.h
+++ /dev/null
@@ -1,40 +0,0 @@
-/*
- This File is copied from
-
- http://www.oreilly.com/catalog/masteralgoc/index.html
- Mastering Algorithms with C
- By Kyle Loudon
- ISBN: 1-56592-453-3
- Publishd by O'Reilly
-
- We have added our own struct to these function.
- */
-
-/*****************************************************************************
-* *
-* ------------------------------- hashpjw.h ------------------------------ *
-* *
-*****************************************************************************/
-
-#ifndef _COMMON_HASHPJW_H
-#define _COMMON_HASHPJW_H
-
-#include <common/config.h>
-
-/*****************************************************************************
-* *
-* Define a table size for demonstration purposes only. *
-* *
-*****************************************************************************/
-
-#define PRIME_TBLSIZ 1699
-
-/*****************************************************************************
-* *
-* --------------------------- Public Interface --------------------------- *
-* *
-*****************************************************************************/
-
-int hashpjw(const void *key);
-
-#endif /* _COMMON_HASHPJW_H */
diff --git a/include/common/list.h b/include/common/list.h
deleted file mode 100644
index 91a5084..0000000
--- a/include/common/list.h
+++ /dev/null
@@ -1,85 +0,0 @@
-/*
- This File is copied from
-
- http://www.oreilly.com/catalog/masteralgoc/index.html
- Mastering Algorithms with C
- By Kyle Loudon
- ISBN: 1-56592-453-3
- Publishd by O'Reilly
-
- */
-
-/*****************************************************************************
-* *
-* -------------------------------- list.h -------------------------------- *
-* *
-*****************************************************************************/
-
-#ifndef _COMMON_LIST_H
-#define _COMMON_LIST_H
-
-#include <stdlib.h>
-#include <common/config.h>
-
-/*****************************************************************************
- * *
- * Define a structure for linked list elements. *
- * *
- *****************************************************************************/
-
-typedef struct ListElmt_ {
- void *data;
- struct ListElmt_ *next;
-} ListElmt;
-
-/*****************************************************************************
- * *
- * Define a structure for linked lists. *
- * *
- *****************************************************************************/
-
-typedef struct List_ {
- int size;
- int (*match)(const void *key1, const void *key2);
- void (*destroy)(void *data);
-
- ListElmt *head;
- ListElmt *tail;
-} List;
-
-/*****************************************************************************
- * *
- * --------------------------- Public Interface --------------------------- *
- * *
- *****************************************************************************/
-
-void list_init(List *list, void (*destroy)(void *data));
-
-void list_destroy(List *list);
-
-int list_ins_next(List *list, ListElmt *element, const void *data);
-
-int list_rem_next(List *list, ListElmt *element, void **data);
-
-#define list_size(list) ((list)->size)
-
-#define list_head(list) ((list)->head)
-
-#define list_tail(list) ((list)->tail)
-
-#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)
-
-#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)
-
-#define list_data(element) ((element)->data)
-
-#define list_next(element) ((element)->next)
-
-#endif /* _COMMON_LIST_H */
-
-/*
- * Local variables:
- * c-indent-level: 8
- * c-basic-offset: 8
- * End:
- */
diff --git a/include/common/sessionhash.h b/include/common/sessionhash.h
new file mode 100644
index 0000000..da5fde0
--- /dev/null
+++ b/include/common/sessionhash.h
@@ -0,0 +1,62 @@
+#ifndef SESSION_HASH_H
+#define SESSION_HASH_H
+
+/*
+ * HashTable functions.
+ *
+ * Copyright 2007 Arnaud Cornet
+ *
+ * This file is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License, version 2.1 as published by the Free Software Foundation.
+ *
+ */
+
+#include <common/appsession.h>
+
+#ifndef TABLESHIFT
+#define TABLESHIFT 11
+#endif
+#define TABLESIZE (1UL << TABLESHIFT)
+#define TABLEMASK (TABLESIZE - 1)
+
+/*
+ * quick and dirty AppSession hash table, using sessid as key
+ */
+
+struct appsession_hash
+{
+ struct list *table;
+ void (*destroy)(appsess *);
+};
+
+unsigned int appsession_hash_f(char *);
+int appsession_hash_init(struct appsession_hash *hash,
+ void(*destroy)(appsess*));
+void appsession_hash_insert(struct appsession_hash *hash,
+ struct appsessions *session);
+struct appsessions *appsession_hash_lookup(struct appsession_hash *hash,
+ char *key);
+void appsession_hash_remove(struct appsession_hash *hash,
+ struct appsessions *session);
+
+void appsession_hash_destroy(struct appsession_hash *hash);
+#if defined(DEBUG_HASH)
+void appsession_hash_dump(struct appsession_hash *hash);
+#endif
+
+/*
+ * Iterates <item> through a hashtable of items of type "typeof(*item)"
+ * A pointer to the appsession_hash is passed in <hash>. The hash table
+ * internaly uses <list_head> member of the struct. A temporary variable <back>
+ * of same type as <item> is needed so that <item> may safely be deleted if
+ * needed. <idx> is a variable containing <item>'s current bucket index in the
+ * hash table.
+ * Example: as_hash_for_each_entry_safe(idx, item, tmp, &hash, hash_list)
+ * { ... }
+ */
+#define as_hash_for_each_entry_safe(idx, item, back, hash, member) \
+ for (idx = 0; idx < TABLESIZE; idx++) \
+ list_for_each_entry_safe(item, back, &((hash)->table[idx]), member)
+
+#endif /* SESSION_HASH_H */
diff --git a/include/types/proxy.h b/include/types/proxy.h
index d205c42..e4cf4ce 100644
--- a/include/types/proxy.h
+++ b/include/types/proxy.h
@@ -28,10 +28,10 @@
#include <arpa/inet.h>
#include <common/appsession.h>
-#include <common/chtbl.h>
#include <common/config.h>
#include <common/mini-clist.h>
#include <common/regex.h>
+#include <common/sessionhash.h>
#include <common/tools.h>
#include <types/acl.h>
@@ -101,7 +101,7 @@
char *appsession_name; /* name of the cookie to look for */
int appsession_name_len; /* strlen(appsession_name), computed only once */
int appsession_len; /* length of the appsession cookie value to be used */
- CHTbl htbl_proxy; /* Per Proxy hashtable */
+ struct appsession_hash htbl_proxy; /* Per Proxy hashtable */
char *capture_name; /* beginning of the name of the cookie to capture */
int capture_namelen; /* length of the cookie name to match */
int capture_len; /* length of the string to be captured */
diff --git a/src/appsession.c b/src/appsession.c
index 50554a5..9b6868c 100644
--- a/src/appsession.c
+++ b/src/appsession.c
@@ -15,10 +15,9 @@
#include <string.h>
#include <common/appsession.h>
-#include <common/chtbl.h>
#include <common/config.h>
-#include <common/list.h>
#include <common/memory.h>
+#include <common/sessionhash.h>
#include <common/time.h>
#include <types/buffers.h>
@@ -33,39 +32,6 @@
struct app_pool apools;
int have_appsession;
-#if defined(DEBUG_HASH)
-void print_table(const CHTbl *htbl)
-{
- ListElmt *element;
- int i;
- appsess *asession;
-
- /*********************************************************************
- * *
- * Display the chained hash table. *
- * *
- *********************************************************************/
-
- fprintf(stdout, "Table size is %d\n", chtbl_size(htbl));
-
- for (i = 0; i < TBLSIZ; i++) {
- fprintf(stdout, "Bucket[%03d]\n", i);
-
- for (element = list_head(&htbl->table[i]);
- element != NULL; element = list_next(element)) {
- //fprintf(stdout, "%c", *(char *)list_data(element));
- asession = (appsess *)list_data(element);
- fprintf(stdout, "ELEM :%s:", asession->sessid);
- fprintf(stdout, " Server :%s: \n", asession->serverid);
- //fprintf(stdout, " Server request_count :%li:\n",asession->request_count);
- }
-
- fprintf(stdout, "\n");
- }
- return;
-} /* end print_table */
-#endif
-
int appsession_init(void)
{
static int initialized = 0;
@@ -139,48 +105,30 @@
void appsession_refresh(struct task *t, struct timeval *next)
{
- struct proxy *p = proxy;
- CHTbl *htbl;
- ListElmt *element, *last;
- int i;
- appsess *asession;
- void *data;
+ struct proxy *p = proxy;
+ struct appsession_hash *htbl;
+ appsess *element, *back;
+ int i;
while (p) {
if (p->appsession_name != NULL) {
htbl = &p->htbl_proxy;
- /* if we ever give up the use of TBLSIZ, we need to change this */
- for (i = 0; i < TBLSIZ; i++) {
- last = NULL;
- for (element = list_head(&htbl->table[i]);
- element != NULL; element = list_next(element)) {
- asession = (appsess *)list_data(element);
- if (tv_isle(&asession->expire, &now)) {
- if ((global.mode & MODE_DEBUG) &&
- (!(global.mode & MODE_QUIET) || (global.mode & MODE_VERBOSE))) {
- int len;
- /*
- on Linux NULL pointers are catched by sprintf, on solaris -> segfault
- */
- len = sprintf(trash, "appsession_refresh: cleaning up expired Session '%s' on Server %s\n",
- asession->sessid, asession->serverid?asession->serverid:"(null)");
- write(1, trash, len);
- }
- /* delete the expired element from within the hash table */
- if ((list_rem_next(&htbl->table[i], last, (void **)&data) == 0)
- && (htbl->table[i].destroy != NULL)) {
- htbl->table[i].destroy(data);
- }
- if (last == NULL) {/* patient lost his head, get a new one */
- element = list_head(&htbl->table[i]);
- if (element == NULL) break; /* no heads left, go to next patient */
- }
- else
- element = last;
- }/* end if (tv_isle(&asession->expire, &now)) */
- else
- last = element;
- }/* end for (element = list_head(&htbl->table[i]); element != NULL; element = list_next(element)) */
+ as_hash_for_each_entry_safe(i, element, back, &p->htbl_proxy, hash_list) {
+ if (tv_isle(&element->expire, &now)) {
+ if ((global.mode & MODE_DEBUG) &&
+ (!(global.mode & MODE_QUIET) || (global.mode & MODE_VERBOSE))) {
+ int len;
+ /*
+ on Linux NULL pointers are caught by sprintf, on solaris -> segfault
+ */
+ len = sprintf(trash, "appsession_refresh: cleaning up expired Session '%s' on Server %s\n",
+ element->sessid, element->serverid?element->serverid:"(null)");
+ write(1, trash, len);
+ }
+ /* delete the expired element from within the hash table */
+ LIST_DEL(&element->hash_list);
+ htbl->destroy(element);
+ }/* end if (tv_isle(&asession->expire, &now)) */
}
}
p = p->next;
@@ -202,12 +150,7 @@
return (strcmp(temp1->sessid,temp2->sessid) == 0);
}/* end match_str */
-void destroy(void *data) {
- appsess *temp1;
-
- //printf("destroy called\n");
- temp1 = (appsess *)data;
-
+void destroy(appsess *temp1) {
if (temp1->sessid)
pool_free2(apools.sessid, temp1->sessid);
@@ -222,7 +165,7 @@
struct proxy *p = proxy;
while(p) {
- chtbl_destroy(&(p->htbl_proxy));
+ appsession_hash_destroy(&(p->htbl_proxy));
p = p->next;
}
}/* end appsession_cleanup() */
diff --git a/src/cfgparse.c b/src/cfgparse.c
index 783e189..b3af23f 100644
--- a/src/cfgparse.c
+++ b/src/cfgparse.c
@@ -796,9 +796,8 @@
else
tv_eternity(&curproxy->appsession_timeout);
- rc = chtbl_init(&(curproxy->htbl_proxy), TBLSIZ, hashpjw, match_str, destroy);
- if (rc) {
- Alert("Error Init Appsession Hashtable.\n");
+ if (appsession_hash_init(&(curproxy->htbl_proxy), destroy) == 0) {
+ Alert("parsing [%s:%d] : out of memory.\n", file, linenum);
return -1;
}
} /* Url App Session */
diff --git a/src/chtbl.c b/src/chtbl.c
deleted file mode 100644
index 08eebb8..0000000
--- a/src/chtbl.c
+++ /dev/null
@@ -1,270 +0,0 @@
-/*
- This File is copied from
-
- http://www.oreilly.com/catalog/masteralgoc/index.html
- Mastering Algorithms with C
- By Kyle Loudon
- ISBN: 1-56592-453-3
- Publishd by O'Reilly
-
- */
-
-/*****************************************************************************
- * *
- * ------------------------------- chtbl.c -------------------------------- *
- * *
- *****************************************************************************/
-
-#include <stdlib.h>
-#include <string.h>
-
-#include <common/config.h>
-#include <common/list.h>
-#include <common/chtbl.h>
-
-/*****************************************************************************
- * *
- * ------------------------------ chtbl_init ------------------------------ *
- * *
- *****************************************************************************/
-
-int chtbl_init(CHTbl *htbl, int buckets, int (*h)(const void *key), int
- (*match)(const void *key1, const void *key2), void (*destroy)(void*data)) {
-
- int i;
-
- /*****************************************************************************
- * *
- * Allocate space for the hash table. *
- * *
- *****************************************************************************/
-
- if ((htbl->table = (List *)malloc(buckets * sizeof(List))) == NULL)
- return -1;
-
- /*****************************************************************************
- * *
- * Initialize the buckets. *
- * *
- *****************************************************************************/
-
- htbl->buckets = buckets;
-
- for (i = 0; i < htbl->buckets; i++)
- list_init(&htbl->table[i], destroy);
-
- /*****************************************************************************
- * *
- * Encapsulate the functions. *
- * *
- *****************************************************************************/
-
- htbl->h = h;
- htbl->match = match;
- htbl->destroy = destroy;
-
- /*****************************************************************************
- * *
- * Initialize the number of elements in the table. *
- * *
- *****************************************************************************/
-
- htbl->size = 0;
-
- return 0;
-} /* end chtbl_init () */
-
-/*****************************************************************************
- * *
- * ---------------------------- chtbl_destroy ----------------------------- *
- * *
- *****************************************************************************/
-
-void chtbl_destroy(CHTbl *htbl) {
-
- int i;
-
- /*****************************************************************************
- * *
- * Destroy each bucket. *
- * *
- *****************************************************************************/
-
- for (i = 0; i < htbl->buckets; i++) {
- list_destroy(&htbl->table[i]);
- } /* end for () */
-
- /*****************************************************************************
- * *
- * Free the storage allocated for the hash table. *
- * *
- *****************************************************************************/
-
- free(htbl->table);
-
- /*****************************************************************************
- * *
- * No operations are allowed now, but clear the structure as a precaution. *
- * *
- *****************************************************************************/
-
- memset(htbl, 0, sizeof(CHTbl));
-
- return;
-} /* end chtbl_destroy() */
-
-/*****************************************************************************
- * *
- * ----------------------------- chtbl_insert ----------------------------- *
- * *
- *****************************************************************************/
-
-int chtbl_insert(CHTbl *htbl, const void *data) {
-
- void *temp;
- int bucket,retval;
-
- /*****************************************************************************
- * *
- * Do nothing if the data is already in the table. *
- * *
- *****************************************************************************/
-
- temp = (void *)data;
-
- if (chtbl_lookup(htbl, &temp) == 0)
- return 1;
-
- /*****************************************************************************
- * *
- * Hash the key. *
- * *
- *****************************************************************************/
-
- bucket = htbl->h(data) % htbl->buckets;
-
- /*****************************************************************************
- * *
- * Insert the data into the bucket. *
- * *
- *****************************************************************************/
-
- if ((retval = list_ins_next(&htbl->table[bucket], NULL, data)) == 0)
- htbl->size++;
-
- return retval;
-} /* end chtbl_insert() */
-
-/*****************************************************************************
- * *
- * ----------------------------- chtbl_remove ----------------------------- *
- * *
- *****************************************************************************/
-
-int chtbl_remove(CHTbl *htbl, void **data) {
-
- ListElmt *element, *prev;
- int bucket;
-
- /*********************************************************************
- * *
- * Hash the key. *
- * *
- *********************************************************************/
-
- bucket = htbl->h(*data) % htbl->buckets;
-
- /*********************************************************************
- * *
- * Search for the data in the bucket. *
- * *
- *********************************************************************/
-
- prev = NULL;
-
- for (element = list_head(&htbl->table[bucket]);
- element != NULL; element = list_next(element)) {
- if (htbl->match(*data, list_data(element))) {
-
- /*****************************************************
- * *
- * Remove the data from the bucket. *
- * *
- *****************************************************/
-
- if (list_rem_next(&htbl->table[bucket], prev, data) == 0) {
- htbl->size--;
- return 0;
- } /* end if() */
- else {
- return -1;
- }/* end else */
- }/* end if (htbl->match(*data, list_data(element))) */
-
- prev = element;
- }/* end for() */
-
- /*********************************************************************
- * *
- * Return that the data was not found. *
- * *
- *********************************************************************/
-
- return -1;
-} /* end int chtbl_remove(CHTbl *htbl, void **data) */
-
-/*****************************************************************************
- * *
- * ----------------------------- chtbl_lookup ----------------------------- *
- * *
- *****************************************************************************/
-
-int chtbl_lookup(const CHTbl *htbl, void **data) {
-
- ListElmt *element;
- int bucket;
-
- /*********************************************************************
- * *
- * Hash the key. *
- * *
- *********************************************************************/
-
- bucket = htbl->h(*data) % htbl->buckets;
-
- /*********************************************************************
- * *
- * Search for the data in the bucket. *
- * *
- *********************************************************************/
-
- for (element = list_head(&htbl->table[bucket]);
- element != NULL; element = list_next(element)) {
- if (htbl->match(*data, list_data(element))) {
-
- /*****************************************************
- * *
- * Pass back the data from the table. *
- * *
- *****************************************************/
-
- *data = list_data(element);
- return 0;
- }/* end if() */
- }/* end for() */
-
- /*********************************************************************
- * *
- * Return that the data was not found. *
- * *
- *********************************************************************/
-
- return -1;
-} /* end chtbl_lookup() */
-
-/*
- * Local variables:
- * c-indent-level: 8
- * c-basic-offset: 8
- * End:
- */
diff --git a/src/hashpjw.c b/src/hashpjw.c
deleted file mode 100644
index 17ef3a2..0000000
--- a/src/hashpjw.c
+++ /dev/null
@@ -1,71 +0,0 @@
-/*
- This File is copied from
-
- http://www.oreilly.com/catalog/masteralgoc/index.html
- Mastering Algorithms with C
- By Kyle Loudon
- ISBN: 1-56592-453-3
- Publishd by O'Reilly
-
- We have added our own struct to these function.
- */
-
-/*****************************************************************************
-* *
-* ------------------------------- hashpjw.c ------------------------------ *
-* *
-*****************************************************************************/
-
-#include <common/config.h>
-#include <common/hashpjw.h>
-#include <common/appsession.h>
-
-/*****************************************************************************
-* *
-* -------------------------------- hashpjw ------------------------------- *
-* *
-*****************************************************************************/
-
-int hashpjw(const void *key) {
-
- const char *ptr;
- unsigned int val;
- appsess *appsession_temp;
-
- /*********************************************************************
- * *
- * Hash the key by performing a number of bit operations on it. *
- * *
- *********************************************************************/
-
- val = 0;
- appsession_temp = (appsess *)key;
- ptr = appsession_temp->sessid;
-
- while (*ptr != '\0') {
-
- int tmp;
-
- val = (val << 4) + (*ptr);
-
- if((tmp = (val & 0xf0000000))) {
- val = val ^ (tmp >> 24);
- val = val ^ tmp;
- }
- ptr++;
- }/* end while */
-
- /*********************************************************************
- * *
- * In practice, replace PRIME_TBLSIZ with the actual table size. *
- * *
- *********************************************************************/
- return val % PRIME_TBLSIZ;
-}/* end hashpjw */
-
-/*
- * Local variables:
- * c-indent-level: 8
- * c-basic-offset: 8
- * End:
- */
diff --git a/src/list.c b/src/list.c
deleted file mode 100644
index f23686a..0000000
--- a/src/list.c
+++ /dev/null
@@ -1,236 +0,0 @@
-/*
- This File is copied from
-
- http://www.oreilly.com/catalog/masteralgoc/index.html
- Mastering Algorithms with C
- By Kyle Loudon
- ISBN: 1-56592-453-3
- Publishd by O'Reilly
-
- */
-
-/*****************************************************************************
- * *
- * -------------------------------- list.c -------------------------------- *
- * *
- *****************************************************************************/
-
-#include <stdlib.h>
-#include <string.h>
-
-#include <common/config.h>
-#include <common/list.h>
-
-/*****************************************************************************
-* *
-* ------------------------------- list_init ------------------------------ *
-* *
-*****************************************************************************/
-
-void list_init(List *list, void (*destroy)(void *data)) {
-
- /*********************************************************************
- * *
- * Initialize the list. *
- * *
- *********************************************************************/
-
- list->size = 0;
- list->destroy = destroy;
- list->head = NULL;
- list->tail = NULL;
- return;
-} /* end list_init() */
-
-/*****************************************************************************
- * *
- * ----------------------------- list_destroy ----------------------------- *
- * *
- *****************************************************************************/
-
-void list_destroy(List *list) {
-
- void *data;
- int rc;
-
- /*********************************************************************
- * *
- * Remove each element. *
- * *
- *********************************************************************/
-
- while (list_size(list) > 0) {
-
- rc = list_rem_next(list, NULL, (void **)&data);
-
- if (( rc == 0) && (list->destroy != NULL)) {
-
- /*******************************************************************
- * *
- * Call a user-defined function to free dynamically allocated data.*
- * *
- *******************************************************************/
-
- list->destroy(data);
- }/* end if() */
- }/* end while() */
-
- /**************************************************************************
- * *
- * No operations are allowed now, but clear the structure as a precaution.*
- * *
- **************************************************************************/
-
- memset(list, 0, sizeof(List));
- return;
-} /* void list_destroy(List *list) */
-
-/*****************************************************************************
- * *
- * ----------------------------- list_ins_next ---------------------------- *
- * *
- *****************************************************************************/
-
-int list_ins_next(List *list, ListElmt *element, const void *data) {
-
- ListElmt *new_element;
-
- /*********************************************************************
- * *
- * Allocate storage for the element. *
- * *
- *********************************************************************/
-
- if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
- return -1;
-
- /*********************************************************************
- * *
- * Insert the element into the list. *
- * *
- *********************************************************************/
-
- new_element->data = (void *)data;
-
- if (element == NULL) {
-
- /*************************************************************
- * *
- * Handle insertion at the head of the list. *
- * *
- *************************************************************/
-
- if (list_size(list) == 0)
- list->tail = new_element;
-
- new_element->next = list->head;
- list->head = new_element;
- }/* end if (element == NULL) */
- else {
-
- /*************************************************************
- * *
- * Handle insertion somewhere other than at the head. *
- * *
- *************************************************************/
-
- if (element->next == NULL)
- list->tail = new_element;
-
- new_element->next = element->next;
- element->next = new_element;
- }/* end else */
-
- /*********************************************************************
- * *
- * Adjust the size of the list to account for the inserted element. *
- * *
- *********************************************************************/
-
- list->size++;
- return 0;
-} /* end list_ins_next() */
-
-/*****************************************************************************
- * *
- * ----------------------------- list_rem_next ---------------------------- *
- * *
- *****************************************************************************/
-
-int list_rem_next(List *list, ListElmt *element, void **data) {
-
- ListElmt *old_element;
-
- /*********************************************************************
- * *
- * Do not allow removal from an empty list. *
- * *
- *********************************************************************/
-
- if (list_size(list) == 0)
- return -1;
-
- /*********************************************************************
- * *
- * Remove the element from the list. *
- * *
- *********************************************************************/
-
- if (element == NULL) {
-
- /*************************************************************
- * *
- * Handle removal from the head of the list. *
- * *
- *************************************************************/
-
- *data = list->head->data;
- old_element = list->head;
- list->head = list->head->next;
-
- if (list_size(list) == 1)
- list->tail = NULL;
- }/* end if (element == NULL) */
- else {
-
- /*************************************************************
- * *
- * Handle removal from somewhere other than the head. *
- * *
- *************************************************************/
-
- if (element->next == NULL)
- return -1;
-
- *data = element->next->data;
- old_element = element->next;
- element->next = element->next->next;
-
- if (element->next == NULL)
- list->tail = element;
- }/* end else */
-
- /*********************************************************************
- * *
- * Free the storage allocated by the abstract data type. *
- * *
- *********************************************************************/
-
- free(old_element);
-
- /*********************************************************************
- * *
- * Adjust the size of the list to account for the removed element. *
- * *
- *********************************************************************/
-
- list->size--;
- return 0;
-}
-
-/*
- * Local variables:
- * c-indent-level: 8
- * c-basic-offset: 8
- * End:
- */
diff --git a/src/proto_http.c b/src/proto_http.c
index 7a86d11..6d71dcd 100644
--- a/src/proto_http.c
+++ b/src/proto_http.c
@@ -4515,9 +4515,10 @@
memcpy(asession_temp->sessid, p3, t->be->appsession_len);
asession_temp->sessid[t->be->appsession_len] = 0;
asession_temp->serverid = NULL;
-
+
/* only do insert, if lookup fails */
- if (chtbl_lookup(&(t->be->htbl_proxy), (void *) &asession_temp) != 0) {
+ asession_temp = appsession_hash_lookup(&(t->be->htbl_proxy), asession_temp->sessid);
+ if (asession_temp == NULL) {
if ((asession_temp = pool_alloc2(pool2_appsess)) == NULL) {
/* free previously allocated memory */
pool_free2(apools.sessid, local_asession.sessid);
@@ -4528,12 +4529,11 @@
asession_temp->sessid = local_asession.sessid;
asession_temp->serverid = local_asession.serverid;
- chtbl_insert(&(t->be->htbl_proxy), (void *) asession_temp);
+ appsession_hash_insert(&(t->be->htbl_proxy), asession_temp);
} else {
/* free previously allocated memory */
pool_free2(apools.sessid, local_asession.sessid);
}
-
if (asession_temp->serverid == NULL) {
Alert("Found Application Session without matching server.\n");
} else {
@@ -4989,7 +4989,7 @@
asession_temp->serverid = NULL;
/* only do insert, if lookup fails */
- if (chtbl_lookup(&(t->be->htbl_proxy), (void *) &asession_temp) != 0) {
+ if (appsession_hash_lookup(&(t->be->htbl_proxy), asession_temp->sessid) == NULL) {
if ((asession_temp = pool_alloc2(pool2_appsess)) == NULL) {
Alert("Not enough Memory process_srv():asession:calloc().\n");
send_log(t->be, LOG_ALERT, "Not enough Memory process_srv():asession:calloc().\n");
@@ -4997,13 +4997,12 @@
}
asession_temp->sessid = local_asession.sessid;
asession_temp->serverid = local_asession.serverid;
- chtbl_insert(&(t->be->htbl_proxy), (void *) asession_temp);
- }/* end if (chtbl_lookup()) */
- else {
+ appsession_hash_insert(&(t->be->htbl_proxy), asession_temp);
+ } else {
/* free wasted memory */
pool_free2(apools.sessid, local_asession.sessid);
- } /* end else from if (chtbl_lookup()) */
-
+ }
+
if (asession_temp->serverid == NULL) {
if ((asession_temp->serverid = pool_alloc2(apools.serverid)) == NULL) {
Alert("Not enough Memory process_srv():asession->sessid:malloc().\n");
@@ -5019,7 +5018,7 @@
tv_add(&asession_temp->expire, &now, &t->be->appsession_timeout);
#if defined(DEBUG_HASH)
- print_table(&(t->be->htbl_proxy));
+ appsession_hash_dump(&(t->be->htbl_proxy));
#endif
}/* end if ((t->proxy->appsession_name != NULL) ... */
break; /* we don't want to loop again since there cannot be another cookie on the same line */
@@ -5161,7 +5160,7 @@
asession_temp->serverid = NULL;
/* only do insert, if lookup fails */
- if (chtbl_lookup(&(t->be->htbl_proxy), (void *)&asession_temp)) {
+ if (appsession_hash_lookup(&(t->be->htbl_proxy), asession_temp->sessid) == NULL) {
if ((asession_temp = pool_alloc2(pool2_appsess)) == NULL) {
/* free previously allocated memory */
pool_free2(apools.sessid, local_asession.sessid);
@@ -5171,18 +5170,18 @@
}
asession_temp->sessid = local_asession.sessid;
asession_temp->serverid = local_asession.serverid;
- chtbl_insert(&(t->be->htbl_proxy), (void *) asession_temp);
+ appsession_hash_insert(&(t->be->htbl_proxy), asession_temp);
}
else {
/* free previously allocated memory */
pool_free2(apools.sessid, local_asession.sessid);
}
-
+
tv_add(&asession_temp->expire, &now, &t->be->appsession_timeout);
asession_temp->request_count++;
-
+
#if defined(DEBUG_HASH)
- print_table(&(t->proxy->htbl_proxy));
+ appsession_hash_dump(&(t->be->htbl_proxy));
#endif
if (asession_temp->serverid == NULL) {
Alert("Found Application Session without matching server.\n");
diff --git a/src/sessionhash.c b/src/sessionhash.c
new file mode 100644
index 0000000..dc32820
--- /dev/null
+++ b/src/sessionhash.c
@@ -0,0 +1,124 @@
+/*
+ * HashTable functions.
+ *
+ * Copyright 2007 Arnaud Cornet
+ *
+ * This file is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License, version 2.1 as published by the Free Software Foundation.
+ *
+ */
+
+/*
+ * quick and dirty AppSession hash table, using sessid as key
+ */
+
+#include <common/sessionhash.h>
+#include <string.h>
+#ifdef TEST
+#include <stdio.h>
+#endif
+
+/*
+ * This is a bernstein hash derivate
+ * returns unsigned int between 0 and (TABLESIZE - 1) inclusive
+ */
+unsigned int appsession_hash_f(char *ptr)
+{
+ unsigned int h = 5381;
+
+ while (*ptr) {
+ h = (h << 5) + h + *ptr;
+ ptr++;
+ }
+ return ((h >> 16) ^ h) & TABLEMASK;
+}
+
+int appsession_hash_init(struct appsession_hash *hash,
+ void(*destroy)(appsess*))
+{
+ int i;
+
+ hash->destroy = destroy;
+ hash->table = malloc(TABLESIZE * sizeof(struct list));
+ if (hash->table == NULL)
+ return 0;
+ for (i = 0; i < TABLESIZE; i++)
+ LIST_INIT(&hash->table[i]);
+ return 1;
+}
+
+void appsession_hash_insert(struct appsession_hash *hash, appsess *session)
+{
+ unsigned int idx;
+
+ idx = appsession_hash_f(session->sessid);
+ LIST_ADDQ(&hash->table[idx], &session->hash_list);
+}
+
+appsess *appsession_hash_lookup(struct appsession_hash *hash, char *sessid)
+{
+ unsigned int idx;
+ appsess *item;
+
+ idx = appsession_hash_f(sessid);
+
+ list_for_each_entry(item, &hash->table[idx], hash_list) {
+ if (strcmp(item->sessid, sessid) == 0)
+ return item;
+ }
+ return NULL;
+}
+
+void appsession_hash_remove(struct appsession_hash *hash, appsess *session)
+{
+ unsigned int idx;
+ appsess *item;
+
+ idx = appsession_hash_f(session->sessid);
+
+ /* we don't even need to call _safe because we return at once */
+ list_for_each_entry(item, &hash->table[idx], hash_list) {
+ if (strcmp(item->sessid, session->sessid) == 0) {
+ LIST_DEL(&item->hash_list);
+ hash->destroy(item);
+ return;
+ }
+ }
+}
+
+void appsession_hash_destroy(struct appsession_hash *hash)
+{
+ unsigned int i;
+ appsess *item;
+
+ for (i = 0; i < TABLESIZE; i++) {
+ while (!LIST_ISEMPTY(&hash->table[i])) {
+ item = LIST_ELEM(hash->table[i].n, appsess *,
+ hash_list);
+ hash->destroy(item);
+ LIST_DEL(&item->hash_list);
+ }
+ }
+ free(hash->table);
+ hash->table = NULL;
+ hash->destroy = NULL;
+}
+
+#if defined(DEBUG_HASH)
+void appsession_hash_dump(struct appsession_hash *hash)
+{
+ unsigned int idx;
+ appsess *sess_head, *item;
+
+ printf("Dumping hashtable 0x%x\n", hash);
+ for (idx = 0; idx < TABLESIZE; idx++) {
+ /* we don't even need to call _safe because we return at once */
+ list_for_each_entry(item, &hash->table[idx], hash_list) {
+ printf("\ttable[%d]:\t%s\t-> 0x%x\n", idx, item->sessid,
+ item);
+ }
+ }
+ printf(".\n");
+}
+#endif
diff --git a/tests/sessionhash_test.c b/tests/sessionhash_test.c
new file mode 100644
index 0000000..cb05f8c
--- /dev/null
+++ b/tests/sessionhash_test.c
@@ -0,0 +1,54 @@
+#include <stdio.h>
+#include <common/sessionhash.h>
+
+int main(int argc, char *argv[])
+{
+ appsess *a, *b, *c, *d, *tmp;
+ struct appsession_hash h;
+ int i;
+
+ a = malloc(sizeof(appsess));
+ b = malloc(sizeof(appsess));
+ c = malloc(sizeof(appsess));
+ d = malloc(sizeof(appsess));
+
+ a->sessid = "abcdefg";
+ b->sessid = "2c";
+ c->sessid = "pe";
+ d->sessid = "abbbbbccccb";
+
+ appsession_hash_init(&h, (void (*)())free);
+ appsession_hash_dump(&h);
+ appsession_hash_insert(&h, a);
+ appsession_hash_insert(&h, b);
+ appsession_hash_insert(&h, c);
+ appsession_hash_insert(&h, d);
+
+ appsession_hash_dump(&h);
+
+ printf("a: %p\n", a);
+ printf("b: %p\n", b);
+ printf("c: %p\n", c);
+ printf("d: %p\n", d);
+ printf("-------------\n");
+ printf("a: %p\n", appsession_hash_lookup(&h, "abcdefg"));
+ printf("b: %p\n", appsession_hash_lookup(&h, "2c"));
+ printf("c: %p\n", appsession_hash_lookup(&h, "pe"));
+ printf("d: %p\n", appsession_hash_lookup(&h, "abbbbbccccb"));
+ printf("null: %p\n", appsession_hash_lookup(&h, "non existant"));
+
+
+ appsession_hash_remove(&h, c);
+ appsession_hash_remove(&h, d);
+
+ appsession_hash_dump(&h);
+
+ printf("-- remove c,d\n");
+ printf("a: %p\n", appsession_hash_lookup(&h, "abcdefg"));
+ printf("b: %p\n", appsession_hash_lookup(&h, "2c"));
+ printf("c: %p\n", appsession_hash_lookup(&h, "pe"));
+ printf("d: %p\n", appsession_hash_lookup(&h, "abbbbbccccb"));
+ printf("null: %p\n", appsession_hash_lookup(&h, "non existant"));
+
+ appsession_hash_destroy(&h);
+}