summaryrefslogtreecommitdiffstats
path: root/tests/exp
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-13 12:18:05 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-13 12:18:05 +0000
commitb46aad6df449445a9fc4aa7b32bd40005438e3f7 (patch)
tree751aa858ca01f35de800164516b298887382919d /tests/exp
parentInitial commit. (diff)
downloadhaproxy-b46aad6df449445a9fc4aa7b32bd40005438e3f7.tar.xz
haproxy-b46aad6df449445a9fc4aa7b32bd40005438e3f7.zip
Adding upstream version 2.9.5.upstream/2.9.5
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r--tests/exp/blocksig.c16
-rw-r--r--tests/exp/filltab25.c399
-rw-r--r--tests/exp/hash_results.txt218
-rw-r--r--tests/exp/hashing-results.txt314
-rw-r--r--tests/exp/io_limits.txt116
-rw-r--r--tests/exp/ip-hash.c202
-rw-r--r--tests/exp/test_hashes.c559
-rw-r--r--tests/exp/testinet.c28
-rw-r--r--tests/exp/uri_hash.c377
9 files changed, 2229 insertions, 0 deletions
diff --git a/tests/exp/blocksig.c b/tests/exp/blocksig.c
new file mode 100644
index 0000000..13b55e7
--- /dev/null
+++ b/tests/exp/blocksig.c
@@ -0,0 +1,16 @@
+#include <stdio.h>
+#include <signal.h>
+#include <unistd.h>
+
+int main(int argc, char **argv)
+{
+ sigset_t new_sig, old_sig;
+
+ sigfillset(&new_sig);
+ sigprocmask(SIG_SETMASK, &new_sig, &old_sig);
+ printf("old_sig: %16Lx\n", *(unsigned long long*)&old_sig);
+ printf("new_sig: %16Lx\n", *(unsigned long long*)&new_sig);
+
+ argc--; argv++;
+ return argc ? execvp(*argv, argv) : 0;
+}
diff --git a/tests/exp/filltab25.c b/tests/exp/filltab25.c
new file mode 100644
index 0000000..1197143
--- /dev/null
+++ b/tests/exp/filltab25.c
@@ -0,0 +1,399 @@
+/*
+ * experimental weighted round robin scheduler - (c) 2007 willy tarreau.
+ *
+ * This filling algorithm is excellent at spreading the servers, as it also
+ * takes care of keeping the most uniform distance between occurrences of each
+ * server, by maximizing this distance. It reduces the number of variables
+ * and expensive operations.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <import/eb32tree.h>
+
+struct srv {
+ struct eb32_node node;
+ struct eb_root *tree; // we want to know where the server is
+ int num;
+ int w; /* weight */
+ int next, last;
+ int rem;
+} *srv;
+
+/* those trees represent a sliding window of 3 time frames */
+struct eb_root tree_0 = EB_ROOT;
+struct eb_root tree_1 = EB_ROOT;
+struct eb_root tree_2 = EB_ROOT;
+
+struct eb_root *init_tree; /* receives positions 0..sw-1 */
+struct eb_root *next_tree; /* receives positions >= 2sw */
+
+int nsrv; /* # of servers */
+int nsw, sw; /* sum of weights */
+int p; /* current position, between sw..2sw-1 */
+
+/* queue a server in the weights tree */
+void queue_by_weight(struct eb_root *root, struct srv *s) {
+ s->node.key = 255 - s->w;
+ eb32_insert(root, &s->node);
+ s->tree = root;
+}
+
+/* queue a server in the weight tree <root>, except if its weight is 0 */
+void queue_by_weight_0(struct eb_root *root, struct srv *s) {
+ if (s->w) {
+ s->node.key = 255 - s->w;
+ eb32_insert(root, &s->node);
+ s->tree = root;
+ } else {
+ s->tree = NULL;
+ }
+}
+
+static inline void dequeue_srv(struct srv *s) {
+ eb32_delete(&s->node);
+}
+
+/* queues a server into the correct tree depending on ->next */
+void put_srv(struct srv *s) {
+ if (s->w <= 0 ||
+ s->next >= 2*sw || /* delay everything which does not fit into the window */
+ s->next >= sw+nsw) { /* and everything which does not fit into the theoretical new window */
+ /* put into next tree */
+ s->next -= sw; // readjust next in case we could finally take this back to current.
+ queue_by_weight_0(next_tree, s);
+ } else {
+ // The overflow problem is caused by the scale we want to apply to user weight
+ // to turn it into effective weight. Since this is only used to provide a smooth
+ // slowstart on very low weights (1), it is a pure waste. Thus, we just have to
+ // apply a small scaling factor and warn the user that slowstart is not very smooth
+ // on low weights.
+ // The max key is about ((scale*maxw)*(scale*maxw)*nbsrv)/ratio (where the ratio is
+ // the arbitrary divide we perform in the examples above). Assuming that ratio==scale,
+ // this translates to maxkey=scale*maxw^2*nbsrv, so
+ // max_nbsrv=2^32/255^2/scale ~= 66051/scale
+ // Using a scale of 16 is enough to support 4000 servers without overflow, providing
+ // 6% steps during slowstart.
+
+ s->node.key = 256 * s->next + (16*255 + s->rem - s->w) / 16;
+
+ /* check for overflows */
+ if ((int)s->node.key < 0)
+ printf(" OV: srv=%p w=%d rem=%d next=%d key=%d", s, s->w, s->rem, s->next, s->node.key);
+ eb32_insert(&tree_0, &s->node);
+ s->tree = &tree_0;
+ }
+}
+
+/* prepares a server when extracting it from the init tree */
+static inline void get_srv_init(struct srv *s) {
+ s->next = s->rem = 0;
+}
+
+/* prepares a server when extracting it from the next tree */
+static inline void get_srv_next(struct srv *s) {
+ s->next += sw;
+}
+
+/* prepares a server when extracting it from the next tree */
+static inline void get_srv_down(struct srv *s) {
+ s->next = p;
+}
+
+/* prepares a server when extracting it from its tree */
+void get_srv(struct srv *s) {
+ if (s->tree == init_tree) {
+ get_srv_init(s);
+ }
+ else if (s->tree == next_tree) {
+ get_srv_next(s);
+ }
+ else if (s->tree == NULL) {
+ get_srv_down(s);
+ }
+}
+
+
+/* return next server from the current tree, or a server from the init tree
+ * if appropriate. If both trees are empty, return NULL.
+ */
+struct srv *get_next_server() {
+ struct eb32_node *node;
+ struct srv *s;
+
+ node = eb32_first(&tree_0);
+ s = eb32_entry(node, struct srv, node);
+
+ if (!node || s->next > p) {
+ /* either we have no server left, or we have a hole */
+ struct eb32_node *node2;
+ node2 = eb32_first(init_tree);
+ if (node2) {
+ node = node2;
+ s = eb32_entry(node, struct srv, node);
+ get_srv_init(s);
+ if (s->w == 0)
+ node = NULL;
+ s->node.key = 0; // do not display random values
+ }
+ }
+ if (node)
+ return s;
+ else
+ return NULL;
+}
+
+void update_position(struct srv *s) {
+ //if (s->tree == init_tree) {
+ if (!s->next) {
+ // first time ever for this server
+ s->last = p;
+ s->next = p + nsw / s->w;
+ s->rem += nsw % s->w;
+
+ if (s->rem >= s->w) {
+ s->rem -= s->w;
+ s->next++;
+ }
+ } else {
+ s->last = s->next; // or p ?
+ //s->next += sw / s->w;
+ //s->rem += sw % s->w;
+ s->next += nsw / s->w;
+ s->rem += nsw % s->w;
+
+ if (s->rem >= s->w) {
+ s->rem -= s->w;
+ s->next++;
+ }
+ }
+}
+
+
+/* switches trees init_tree and next_tree. init_tree should be empty when
+ * this happens, and next_tree filled with servers sorted by weights.
+ */
+void switch_trees() {
+ struct eb_root *swap;
+ swap = init_tree;
+ init_tree = next_tree;
+ next_tree = swap;
+ sw = nsw;
+ p = sw;
+}
+
+main(int argc, char **argv) {
+ int conns;
+ int i;
+
+ struct srv *s;
+
+ argc--; argv++;
+ nsrv = argc;
+
+ if (!nsrv)
+ exit(1);
+
+ srv = calloc(nsrv, sizeof(struct srv));
+
+ sw = 0;
+ for (i = 0; i < nsrv; i++) {
+ s = &srv[i];
+ s->num = i;
+ s->w = atol(argv[i]);
+ sw += s->w;
+ }
+
+ nsw = sw;
+
+ init_tree = &tree_1;
+ next_tree = &tree_2;
+
+ /* and insert all the servers in the PREV tree */
+ /* note that it is required to insert them according to
+ * the reverse order of their weights.
+ */
+ printf("---------------:");
+ for (i = 0; i < nsrv; i++) {
+ s = &srv[i];
+ queue_by_weight_0(init_tree, s);
+ printf("%2d", s->w);
+ }
+ printf("\n");
+
+ p = sw; // time base of current tree
+ conns = 0;
+ while (1) {
+ struct eb32_node *node;
+
+ printf("%08d|%06d: ", conns, p);
+
+ /* if we have en empty tree, let's first try to collect weights
+ * which might have changed.
+ */
+ if (!sw) {
+ if (nsw) {
+ sw = nsw;
+ p = sw;
+ /* do not switch trees, otherwise new servers (from init)
+ * would end up in next.
+ */
+ //switch_trees();
+ //printf("bla\n");
+ }
+ else
+ goto next_iteration;
+ }
+
+ s = get_next_server();
+ if (!s) {
+ printf("----------- switch (empty) -- sw=%d -> %d ---------\n", sw, nsw);
+ switch_trees();
+ s = get_next_server();
+ printf("%08d|%06d: ", conns, p);
+
+ if (!s)
+ goto next_iteration;
+ }
+ else if (s->next >= 2*sw) {
+ printf("ARGGGGG! s[%d].next=%d, max=%d\n", s->num, s->next, 2*sw-1);
+ }
+
+ /* now we have THE server we want to put at this position */
+ for (i = 0; i < s->num; i++) {
+ if (srv[i].w > 0)
+ printf(". ");
+ else
+ printf("_ ");
+ }
+ printf("# ");
+ for (i = s->num + 1; i < nsrv; i++) {
+ if (srv[i].w > 0)
+ printf(". ");
+ else
+ printf("_ ");
+ }
+ printf(" : ");
+
+ printf("s=%02d v=%04d w=%03d n=%03d r=%03d ",
+ s->num, s->node.key, s->w, s->next, s->rem);
+
+ update_position(s);
+ printf(" | next=%03d, rem=%03d ", s->next, s->rem);
+
+ if (s->next >= sw * 2) {
+ dequeue_srv(s);
+ //queue_by_weight(next_tree, s);
+ put_srv(s);
+ printf(" => next (w=%d, n=%d) ", s->w, s->next);
+ }
+ else {
+ printf(" => curr ");
+
+ //s->node.key = s->next;
+ /* we want to ensure that in case of conflicts, servers with
+ * the highest weights will get served first. Also, we still
+ * have the remainder to see where the entry expected to be
+ * inserted.
+ */
+ //s->node.key = 256 * s->next + 255 - s->w;
+ //s->node.key = sw * s->next + sw / s->w;
+ //s->node.key = sw * s->next + s->rem; /// seems best (check with filltab15) !
+
+ //s->node.key = (2 * sw * s->next) + s->rem + sw / s->w;
+
+ /* FIXME: must be optimized */
+ dequeue_srv(s);
+ put_srv(s);
+ //eb32i_insert(&tree_0, &s->node);
+ //s->tree = &tree_0;
+ }
+
+ next_iteration:
+ p++;
+ conns++;
+ if (/*conns == 30*/ /**/random()%100 == 0/**/) {
+ int w = /*20*//**/random()%4096/**/;
+ int num = /*1*//**/random()%nsrv/**/;
+ struct srv *s = &srv[num];
+
+ nsw = nsw - s->w + w;
+ //sw=nsw;
+
+ if (s->tree == init_tree) {
+ printf(" -- chgwght1(%d): %d->%d, n=%d --", s->num, s->w, w, s->next);
+ printf("(init)");
+ s->w = w;
+ dequeue_srv(s);
+ queue_by_weight_0(s->tree, s);
+ }
+ else if (s->tree == NULL) {
+ printf(" -- chgwght2(%d): %d->%d, n=%d --", s->num, s->w, w, s->next);
+ printf("(down)");
+ s->w = w;
+ dequeue_srv(s);
+ //queue_by_weight_0(init_tree, s);
+ get_srv(s);
+ s->next = p + (nsw + sw - p) / s->w;
+ put_srv(s);
+ }
+ else {
+ int oldnext;
+
+ /* the server is either active or in the next queue */
+ get_srv(s);
+ printf(" -- chgwght3(%d): %d->%d, n=%d, sw=%d, nsw=%d --", s->num, s->w, w, s->next, sw, nsw);
+
+ oldnext = s->next;
+ s->w = w;
+
+ /* we must measure how far we are from the end of the current window
+ * and try to fit their as many entries as should theoretically be.
+ */
+
+ //s->w = s->w * (2*sw - p) / sw;
+ if (s->w > 0) {
+ int step = (nsw /*+ sw - p*/) / s->w;
+ s->next = s->last + step;
+ s->rem = 0;
+ if (s->next > oldnext) {
+ s->next = oldnext;
+ printf(" aaaaaaa ");
+ }
+
+ if (s->next < p + 2) {
+ s->next = p + step;
+ printf(" bbbbbb ");
+ }
+ } else {
+ printf(" push -- ");
+ /* push it into the next tree */
+ s->w = 0;
+ s->next = p + sw;
+ }
+
+
+ dequeue_srv(s);
+ printf(" n=%d", s->next);
+ put_srv(s);
+ }
+ }
+
+ printf("\n");
+
+ if (0 && conns % 50000 == 0) {
+ printf("-------- %-5d : changing all weights ----\n", conns);
+
+ for (i = 0; i < nsrv; i++) {
+ int w = i + 1;
+ s = &srv[i];
+ nsw = nsw - s->w + w;
+ s->w = w;
+ dequeue_srv(s);
+ queue_by_weight_0(next_tree, s); // or init_tree ?
+ }
+ }
+
+ }
+}
+
diff --git a/tests/exp/hash_results.txt b/tests/exp/hash_results.txt
new file mode 100644
index 0000000..0f14ec9
--- /dev/null
+++ b/tests/exp/hash_results.txt
@@ -0,0 +1,218 @@
+Test: ./test_hashes | sort -k 3 -r
+
+Note: haproxy_server_hash should be avoided as it's just a 32 bit XOR.
+
+Athlon @ 1533 MHz, gcc-3.4 -march=i686 :
+ haproxy_server_hash : 18477000 run/sec
+ SuperFastHash : 6983511 run/sec
+ hash_djbx33 : 4164334 run/sec
+ bernstein : 3371838 run/sec
+ kr_hash : 3257684 run/sec
+ sax_hash : 3027567 run/sec
+ fnv_hash : 2818374 run/sec
+ haproxy_uri_hash : 2108346 run/sec
+ oat_hash : 2106181 run/sec
+ hashword : 1936973 run/sec
+ hashpjw : 1803475 run/sec
+ fnv_32a_str : 1499198 run/sec
+
+Pentium-M @1700 MHz, gcc-3.4 -march=i686 :
+ haproxy_server_hash : 15471737 run/sec
+ SuperFastHash : 8155706 run/sec
+ hash_djbx33 : 4520191 run/sec
+ bernstein : 3956142 run/sec
+ kr_hash : 3725125 run/sec
+ fnv_hash : 3155413 run/sec
+ sax_hash : 2688323 run/sec
+ oat_hash : 2452789 run/sec
+ haproxy_uri_hash : 2010853 run/sec
+ hashword : 1831441 run/sec
+ hashpjw : 1737000 run/sec
+ fnv_32a_str : 1643737 run/sec
+
+Athlon @ 1533 MHz, gcc-4.1 -march=i686 :
+ haproxy_server_hash : 13592089 run/sec
+ SuperFastHash2 : 8687957 run/sec
+ SuperFastHash : 7361242 run/sec
+ hash_djbx33 : 5741546 run/sec
+ bernstein : 3368909 run/sec
+ sax_hash : 3339880 run/sec
+ kr_hash : 3277230 run/sec
+ fnv_hash : 2832402 run/sec
+ hashword : 2500317 run/sec
+ haproxy_uri_hash : 2433241 run/sec
+ oat_hash : 2403118 run/sec
+ hashpjw : 1881229 run/sec
+ fnv_32a_str : 1815709 run/sec
+
+Pentium-M @1700 MHz, gcc-4.1 -march=i686 :
+ haproxy_server_hash : 14128788 run/sec
+ SuperFastHash2 : 8157119 run/sec
+ SuperFastHash : 7481027 run/sec
+ hash_djbx33 : 5660711 run/sec
+ bernstein : 3961493 run/sec
+ fnv_hash : 3590727 run/sec
+ kr_hash : 3389393 run/sec
+ sax_hash : 2667227 run/sec
+ oat_hash : 2348211 run/sec
+ hashword : 2278856 run/sec
+ haproxy_uri_hash : 2098022 run/sec
+ hashpjw : 1846583 run/sec
+ fnv_32a_str : 1661219 run/sec
+
+Pentium-M @600 MHz, gcc-4.1 -march=i686 :
+ haproxy_server_hash : 5318468 run/sec
+ SuperFastHash2 : 3126165 run/sec
+ SuperFastHash : 2729981 run/sec
+ hash_djbx33 : 2042181 run/sec
+ bernstein : 1422927 run/sec
+ fnv_hash : 1287736 run/sec
+ kr_hash : 1217924 run/sec
+ sax_hash : 949694 run/sec
+ oat_hash : 837279 run/sec
+ hashword : 812868 run/sec
+ haproxy_uri_hash : 747611 run/sec
+ hashpjw : 659890 run/sec
+ fnv_32a_str : 590895 run/sec
+
+athlon @ 1.5 GHz, gcc-2.95 -march=i686 :
+ haproxy_server_hash : 13592864 run/sec
+ SuperFastHash : 6931251 run/sec
+ bernstein : 4105179 run/sec
+ hash_djbx33 : 3920059 run/sec
+ kr_hash : 2985794 run/sec
+ fnv_hash : 2815457 run/sec
+ sax_hash : 2791358 run/sec
+ haproxy_uri_hash : 2786663 run/sec
+ oat_hash : 2237859 run/sec
+ hashword : 1985740 run/sec
+ hashpjw : 1757733 run/sec
+ fnv_32a_str : 1697299 run/sec
+
+Pentium-M @ 600 MHz, gcc-2.95 -march=i686 :
+ SuperFastHash : 2934387 run/sec
+ haproxy_server_hash : 2864668 run/sec
+ hash_djbx33 : 1498043 run/sec
+ bernstein : 1414993 run/sec
+ kr_hash : 1297907 run/sec
+ fnv_hash : 1260343 run/sec
+ sax_hash : 924764 run/sec
+ oat_hash : 854545 run/sec
+ haproxy_uri_hash : 790040 run/sec
+ hashword : 693501 run/sec
+ hashpjw : 647346 run/sec
+ fnv_32a_str : 579691 run/sec
+
+Pentium-M @ 1700 MHz, gcc-2.95 -march=i686 :
+ SuperFastHash : 8006127 run/sec
+ haproxy_server_hash : 7834162 run/sec
+ hash_djbx33 : 4186025 run/sec
+ bernstein : 3941492 run/sec
+ kr_hash : 3630713 run/sec
+ fnv_hash : 3507488 run/sec
+ sax_hash : 2528128 run/sec
+ oat_hash : 2395188 run/sec
+ haproxy_uri_hash : 2158924 run/sec
+ hashword : 1910992 run/sec
+ hashpjw : 1819894 run/sec
+ fnv_32a_str : 1629844 run/sec
+
+UltraSparc @ 400 MHz, gcc-3.4.3 :
+ haproxy_server_hash : 5573220 run/sec
+ SuperFastHash : 1372714 run/sec
+ bernstein : 1361733 run/sec
+ hash_djbx33 : 1090373 run/sec
+ sax_hash : 872499 run/sec
+ oat_hash : 730354 run/sec
+ kr_hash : 645431 run/sec
+ haproxy_uri_hash : 541157 run/sec
+ fnv_32a_str : 442608 run/sec
+ hashpjw : 434858 run/sec
+ fnv_hash : 401945 run/sec
+ hashword : 340594 run/sec
+
+UltraSparc @ 400 MHz, gcc-3.4.3 -mcpu=v9 :
+ haproxy_server_hash : 5671183 run/sec
+ bernstein : 1437122 run/sec
+ hash_djbx33 : 1376294 run/sec
+ SuperFastHash : 1306634 run/sec
+ sax_hash : 873650 run/sec
+ kr_hash : 801439 run/sec
+ oat_hash : 729920 run/sec
+ haproxy_uri_hash : 545341 run/sec
+ hashpjw : 472190 run/sec
+ fnv_32a_str : 443668 run/sec
+ hashword : 357295 run/sec
+ fnv_hash : 208823 run/sec
+
+
+Alpha EV6 @ 466 MHz, gcc-3.3 :
+ haproxy_server_hash : 2495928 run/sec
+ SuperFastHash : 2037208 run/sec
+ hash_djbx33 : 1625092 run/sec
+ kr_hash : 1532206 run/sec
+ bernstein : 1256746 run/sec
+ haproxy_uri_hash : 999106 run/sec
+ oat_hash : 841943 run/sec
+ sax_hash : 737447 run/sec
+ hashpjw : 676170 run/sec
+ fnv_hash : 644054 run/sec
+ fnv_32a_str : 638526 run/sec
+ hashword : 421777 run/sec
+
+VIA EPIA @ 533 MHz, gcc-2.95 -march=i586 :
+ haproxy_server_hash : 1391374 run/sec
+ SuperFastHash : 912397 run/sec
+ hash_djbx33 : 589868 run/sec
+ kr_hash : 453706 run/sec
+ bernstein : 437318 run/sec
+ sax_hash : 334456 run/sec
+ hashpjw : 316670 run/sec
+ hashword : 315476 run/sec
+ haproxy_uri_hash : 311112 run/sec
+ oat_hash : 259127 run/sec
+ fnv_32a_str : 229485 run/sec
+ fnv_hash : 151620 run/sec
+
+VIA EPIA @ 533 MHz, gcc-3.4 -march=i586 :
+ haproxy_server_hash : 1660407 run/sec
+ SuperFastHash : 791981 run/sec
+ hash_djbx33 : 680498 run/sec
+ kr_hash : 384076 run/sec
+ bernstein : 377247 run/sec
+ sax_hash : 355183 run/sec
+ hashpjw : 298879 run/sec
+ haproxy_uri_hash : 296748 run/sec
+ oat_hash : 283932 run/sec
+ hashword : 269429 run/sec
+ fnv_32a_str : 204776 run/sec
+ fnv_hash : 155301 run/sec
+
+Pentium @ 133 MHz, gcc-3.4 -march=i586 :
+ haproxy_server_hash : 930788 run/sec
+ SuperFastHash : 344988 run/sec
+ hash_djbx33 : 278996 run/sec
+ bernstein : 211545 run/sec
+ sax_hash : 185225 run/sec
+ kr_hash : 156603 run/sec
+ oat_hash : 135163 run/sec
+ hashword : 128518 run/sec
+ fnv_hash : 107024 run/sec
+ haproxy_uri_hash : 105523 run/sec
+ fnv_32a_str : 99913 run/sec
+ hashpjw : 97860 run/sec
+
+VAX VLC4000 @30 MHz, gcc-2.95 :
+ haproxy_server_hash : 13208 run/sec
+ hash_djbx33 : 12963 run/sec
+ fnv_hash : 12150 run/sec
+ SuperFastHash : 12037 run/sec
+ bernstein : 11765 run/sec
+ kr_hash : 11111 run/sec
+ sax_hash : 7273 run/sec
+ hashword : 7143 run/sec
+ oat_hash : 6931 run/sec
+ hashpjw : 6667 run/sec
+ haproxy_uri_hash : 5714 run/sec
+ fnv_32a_str : 4800 run/sec
+
diff --git a/tests/exp/hashing-results.txt b/tests/exp/hashing-results.txt
new file mode 100644
index 0000000..d2dbf59
--- /dev/null
+++ b/tests/exp/hashing-results.txt
@@ -0,0 +1,314 @@
+These are the result of tests conducted to determine efficacy of hashing
+algorithms and avalache application in haproxy. All results below were
+generated using version 1.5. See the document on hashing under internal docs
+for a detailed description on the tests the methodology and interpretation
+of the results.
+
+The following was the set up used
+
+(a) hash-type consistent/map-bases
+(b) avalanche on/off
+(c) balanche host(hdr)
+(d) 3 criteria for inputs
+ - ~ 10K requests, including duplicates
+ - ~ 46K requests, unique requests from 1 MM requests were obtained
+ - ~ 250K requests, including duplicates
+(e) 17 servers in backend, all servers were assigned the same weight
+
+The results can be interpreted across 3 dimensions corresponding to input
+criteria (a)/(b) and (d) above
+
+== 10 K requests ==
+
+=== Consistent with avalanche ===
+
+Servers SDBM DJB2 WT6
+-----------------------------
+1 576 637 592
+2 552 608 600
+3 539 559 551
+4 578 586 493
+5 534 555 549
+6 614 607 576
+7 519 556 554
+8 591 565 607
+9 529 604 575
+10 642 550 678
+11 537 591 506
+12 568 571 567
+13 589 606 572
+14 648 568 711
+15 645 557 603
+16 583 627 591
+17 699 596 618
+-----------------------------
+Std Dev 48.95 26.29 51.75
+
+=== Consistent without avalanche ===
+
+Servers SDBM DJB2 WT6
+-----------------------------
+1 612 627 579
+2 631 607 563
+3 585 605 604
+4 594 502 518
+5 583 526 602
+6 589 594 555
+7 591 602 511
+8 518 540 623
+9 550 519 523
+10 600 637 647
+11 568 536 550
+12 552 605 645
+13 547 556 564
+14 615 674 635
+15 642 624 618
+16 575 585 609
+17 591 604 597
+-----------------------------
+Std Dev 30.71 45.97 42.52
+
+=== Map based without avalanche ===
+
+Servers SDBM DJB2 WT6
+-----------------------------
+1 602 560 598
+2 576 583 583
+3 579 624 593
+4 608 587 551
+5 579 549 588
+6 582 560 590
+7 553 616 562
+8 568 600 551
+9 594 607 620
+10 574 611 635
+11 578 607 603
+12 563 581 547
+13 604 531 572
+14 621 606 618
+15 600 561 602
+16 555 570 585
+17 607 590 545
+-----------------------------
+Std Dev 19.24 25.56 26.29
+
+=== Map based with avalanche ===
+
+Servers SDBM DJB2 WT6
+-----------------------------
+Servers SDBM DJB2 WT6
+1 548 641 597
+2 612 563 655
+3 596 536 595
+4 609 574 537
+5 586 610 570
+6 600 568 562
+7 589 573 578
+8 584 549 573
+9 561 636 603
+10 607 553 603
+11 554 602 616
+12 560 577 568
+13 597 534 570
+14 597 647 570
+15 563 581 647
+16 575 647 565
+17 605 552 534
+-----------------------------
+Std Dev 20.23 37.47 32.16
+
+== Uniques in 1 MM ==
+
+=== Consistent with avalanche ===
+
+Servers SDBM DJB2 WT6
+-----------------------------
+1 2891 2963 2947
+2 2802 2849 2771
+3 2824 2854 2904
+4 2704 2740 2763
+5 2664 2699 2646
+6 2902 2876 2935
+7 2829 2745 2730
+8 2648 2768 2800
+9 2710 2741 2689
+10 3070 3111 3106
+11 2733 2638 2589
+12 2828 2866 2885
+13 2876 2961 2870
+14 3090 2997 3044
+15 2871 2879 2827
+16 2881 2727 2921
+17 2936 2845 2832
+-----------------------------
+Std Dev 121.66 118.59 131.61
+
+=== Consistent without avalanche ===
+
+Servers SDBM DJB2 WT6
+-----------------------------
+1 2879 2930 2863
+2 2835 2856 2853
+3 2875 2741 2899
+4 2720 2718 2761
+5 2703 2754 2689
+6 2848 2901 2925
+7 2829 2756 2838
+8 2761 2779 2805
+9 2719 2671 2746
+10 3015 3176 3079
+11 2620 2661 2656
+12 2879 2773 2713
+13 2829 2844 2925
+14 3064 2951 3041
+15 2898 2928 2877
+16 2880 2867 2791
+17 2905 2953 2798
+-----------------------------
+Std Dev 107.65 125.2 111.34
+
+=== Map based without avalanche ===
+
+Servers SDBM DJB2 WT6
+-----------------------------
+1 2863 2837 2923
+2 2966 2829 2847
+3 2865 2803 2808
+4 2682 2816 2787
+5 2847 2782 2815
+6 2910 2862 2862
+7 2821 2784 2793
+8 2837 2834 2796
+9 2857 2891 2859
+10 2829 2906 2873
+11 2742 2851 2841
+12 2790 2837 2870
+13 2765 2902 2794
+14 2870 2732 2900
+15 2898 2891 2759
+16 2877 2860 2863
+17 2840 2842 2869
+-----------------------------
+Std Dev 64.65 45.16 43.38
+
+=== Map based with avalanche ===
+
+Servers SDBM DJB2 WT6
+-----------------------------
+1 2816 2859 2895
+2 2841 2739 2789
+3 2846 2903 2888
+4 2817 2878 2812
+5 2750 2794 2852
+6 2816 2917 2847
+7 2792 2782 2786
+8 2800 2814 2868
+9 2854 2883 2842
+10 2770 2854 2855
+11 2851 2854 2837
+12 2910 2846 2776
+13 2904 2792 2882
+14 2984 2767 2854
+15 2766 2863 2823
+16 2902 2797 2907
+17 2840 2917 2746
+-----------------------------
+Std Dev 58.39 52.16 43.72
+
+== 250K requests ==
+
+=== Consistent with avalanche ===
+
+Servers SDBM DJB2 WT6
+-----------------------------
+1 14182 12996 20924
+2 14881 18376 8901
+3 13537 17935 13639
+4 11031 12582 19758
+5 15429 10084 12112
+6 18712 12574 14052
+7 14271 11257 14538
+8 12048 18582 16653
+9 10570 10283 13949
+10 11683 13081 23530
+11 9288 14828 10818
+12 10775 13607 19844
+13 10036 19138 15413
+14 31903 15222 11824
+15 21276 11963 10405
+16 17233 23116 11316
+17 11437 12668 10616
+-----------------------------
+Std Dev 5355.95 3512.39 4096.65
+
+=== Consistent without avalanche ===
+
+Servers SDBM DJB2 WT6
+-----------------------------
+1 12411 17833 11831
+2 14213 11165 14833
+3 11431 10241 11671
+4 14080 13913 20224
+5 10886 12101 14272
+6 15168 12470 14641
+7 18802 12211 10164
+8 18678 11852 12421
+9 17468 10865 17655
+10 19801 28493 13221
+11 10885 20201 13507
+12 20419 11660 14078
+13 12591 18616 13906
+14 12798 18200 24152
+15 13338 10532 14111
+16 11715 10478 14759
+17 13608 17461 12846
+-----------------------------
+Std Dev 3113.33 4749.97 3256.04
+
+=== Map based without avalanche ===
+
+Servers SDBM DJB2 WT6
+-----------------------------
+1 14660 12483 11472
+2 11118 11552 12146
+3 15407 19952 11032
+4 15444 12218 14572
+5 22091 11434 13738
+6 18273 17587 21337
+7 10527 16784 15118
+8 13013 12010 17195
+9 15754 9886 14611
+10 13758 11613 14844
+11 19564 16453 17403
+12 9692 17246 14469
+13 13905 11885 20024
+14 19401 15350 10611
+15 11889 25485 11172
+16 13846 13928 12109
+17 9950 12426 16439
+-----------------------------
+Std Dev 3481.45 3847.74 3031.93
+
+=== Map based with avalanche ===
+
+Servers SDBM DJB2 WT6
+-----------------------------
+1 15546 11454 12871
+2 15388 11464 17587
+3 11767 15527 14785
+4 15843 13214 11420
+5 11129 12192 15083
+6 15647 17875 11051
+7 18723 13629 23006
+8 10938 11295 11223
+9 12653 17202 23347
+10 10108 12867 14178
+11 12116 11190 20523
+12 14982 12341 11881
+13 13221 13929 11828
+14 17642 19621 15320
+15 12410 26171 11721
+16 25075 14764 13544
+17 15104 13557 8924
+-----------------------------
+Std Dev 3521.83 3742.21 4101.2
diff --git a/tests/exp/io_limits.txt b/tests/exp/io_limits.txt
new file mode 100644
index 0000000..03399bc
--- /dev/null
+++ b/tests/exp/io_limits.txt
@@ -0,0 +1,116 @@
+---------- epoll without limits --------
+% time seconds usecs/call calls errors syscall
+------ ----------- ----------- --------- --------- ----------------
+ 47.19 2.671077 56 48093 22397 recv
+ 47.15 2.668840 106 25060 4858 send
+ 2.19 0.124020 10 12150 epoll_ctl
+ 1.96 0.110904 286 388 epoll_wait
+ 0.56 0.031565 47 670 close
+ 0.19 0.010481 28 380 350 connect
+ 0.15 0.008650 25 350 socket
+ 0.14 0.008204 26 320 shutdown
+ 0.14 0.007655 22 355 35 accept
+ 0.12 0.006871 10 670 setsockopt
+ 0.11 0.006194 9 670 fcntl64
+ 0.07 0.004148 12 355 brk
+ 0.04 0.002055 5 389 gettimeofday
+------ ----------- ----------- --------- --------- ----------------
+100.00 5.660664 89850 27640 total
+
+
+---------- sepoll without limit --------
+% time seconds usecs/call calls errors syscall
+------ ----------- ----------- --------- --------- ----------------
+ 49.43 2.770682 97 28486 3861 send
+ 46.48 2.605336 53 49317 23434 recv
+ 2.00 0.111916 206 542 epoll_wait
+ 0.65 0.036325 12 3030 epoll_ctl
+ 0.45 0.025282 38 670 close
+ 0.24 0.013247 34 388 358 connect
+ 0.17 0.009544 27 350 socket
+ 0.16 0.008734 27 320 shutdown
+ 0.11 0.006432 18 357 37 accept
+ 0.10 0.005699 9 670 setsockopt
+ 0.08 0.004724 7 670 fcntl64
+ 0.08 0.004568 6 767 gettimeofday
+ 0.06 0.003127 9 356 brk
+------ ----------- ----------- --------- --------- ----------------
+100.00 5.605616 85923 27690 total
+
+
+---------- sepoll with send limit only --------
+% time seconds usecs/call calls errors syscall
+------ ----------- ----------- --------- --------- ----------------
+ 49.21 2.779349 109 25417 418 send
+ 46.94 2.651058 54 49150 23368 recv
+ 1.77 0.099863 264 378 epoll_wait
+ 0.57 0.032141 14 2351 epoll_ctl
+ 0.46 0.025822 39 670 close
+ 0.25 0.014300 37 387 357 connect
+ 0.19 0.010530 30 350 socket
+ 0.15 0.008656 27 320 shutdown
+ 0.14 0.008008 23 354 34 accept
+ 0.11 0.006051 9 670 setsockopt
+ 0.10 0.005461 8 670 fcntl64
+ 0.07 0.003842 6 604 gettimeofday
+ 0.06 0.003120 9 358 brk
+------ ----------- ----------- --------- --------- ----------------
+100.00 5.648201 81679 24177 total
+
+
+---------- sepoll with send + recv limits --------
+Process 3173 attached - interrupt to quit
+Process 3173 detached
+% time seconds usecs/call calls errors syscall
+------ ----------- ----------- --------- --------- ----------------
+ 49.09 2.802918 105 26771 596 send
+ 47.72 2.724651 89 30761 728 recv
+ 1.12 0.063952 55 1169 epoll_wait
+ 0.47 0.026810 40 676 close
+ 0.44 0.025358 11 2329 epoll_ctl
+ 0.21 0.012255 30 403 367 connect
+ 0.20 0.011135 35 320 shutdown
+ 0.18 0.010313 29 356 socket
+ 0.15 0.008614 6 1351 gettimeofday
+ 0.13 0.007678 21 360 40 accept
+ 0.13 0.007218 11 676 setsockopt
+ 0.10 0.005559 8 676 fcntl64
+ 0.05 0.002882 9 327 brk
+------ ----------- ----------- --------- --------- ----------------
+100.00 5.709343 66175 1731 total
+
+---------- epoll with send+recv limits -----------
+Process 3271 attached - interrupt to quit
+Process 3271 detached
+% time seconds usecs/call calls errors syscall
+------ ----------- ----------- --------- --------- ----------------
+ 46.96 2.742476 124 22193 send
+ 46.55 2.718027 98 27730 recv
+ 2.58 0.150701 11 13331 epoll_ctl
+ 2.30 0.134350 135 998 epoll_wait
+ 0.52 0.030520 45 673 close
+ 0.23 0.013422 42 320 shutdown
+ 0.19 0.011282 29 386 353 connect
+ 0.19 0.011063 31 353 socket
+ 0.12 0.007039 20 359 39 accept
+ 0.11 0.006629 10 673 fcntl64
+ 0.10 0.005920 9 673 setsockopt
+ 0.09 0.005157 5 999 gettimeofday
+ 0.05 0.002885 9 335 brk
+------ ----------- ----------- --------- --------- ----------------
+100.00 5.839471 69023 392 total
+
+
+Conclusion
+----------
+epoll = 89850 syscalls
+sepoll = 85923 syscalls
+epoll+limits = 69023 syscalls
+sepoll+limits = 66175 syscalls
+
+=> limits reduce the number of syscalls by 23%
+=> sepoll reduces the number of syscalls by 4%
+=> sepoll reduces the number of epoll_ctl by 83%
+=> limits reduce the number of epoll_ctl by 24%
+=> limits increase the number of epoll_wait by 115%
+
diff --git a/tests/exp/ip-hash.c b/tests/exp/ip-hash.c
new file mode 100644
index 0000000..8bb2d48
--- /dev/null
+++ b/tests/exp/ip-hash.c
@@ -0,0 +1,202 @@
+/*
+ * Integer hashing tests. These functions work with 32-bit integers, so are
+ * perfectly suited for IPv4 addresses. A few tests show that they may also
+ * be chained for larger keys (eg: IPv6), this way :
+ * f(x[0-3]) = f(f(f(f(x[0])^x[1])^x[2])^x[3])
+ *
+ * See also bob jenkin's site for more info on hashing, and check perfect
+ * hashing for constants (eg: header names).
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <arpa/inet.h>
+#include <math.h>
+
+#define NSERV 8
+#define MAXLINE 1000
+
+
+int counts_id[NSERV][NSERV];
+uint32_t hash_id( uint32_t a)
+{
+ return a;
+}
+
+/* Full-avalanche integer hashing function from Thomas Wang, suitable for use
+ * with a modulo. See below, worth a read !
+ * http://www.concentric.net/~Ttwang/tech/inthash.htm
+ *
+ * See also tests performed by Bob Jenkins (says it's faster than his) :
+ * http://burtleburtle.net/bob/hash/integer.html
+ *
+ * This function is small and fast. It does not seem as smooth as bj6 though.
+ * About 0x40 bytes, 6 shifts.
+ */
+int counts_tw1[NSERV][NSERV];
+uint32_t hash_tw1(uint32_t a)
+{
+ a += ~(a<<15);
+ a ^= (a>>10);
+ a += (a<<3);
+ a ^= (a>>6);
+ a += ~(a<<11);
+ a ^= (a>>16);
+ return a;
+}
+
+/* Thomas Wang's mix function. The multiply is optimized away by the compiler
+ * on most platforms.
+ * It is about equivalent to the one above.
+ */
+int counts_tw2[NSERV][NSERV];
+uint32_t hash_tw2(uint32_t a)
+{
+ a = ~a + (a << 15);
+ a = a ^ (a >> 12);
+ a = a + (a << 2);
+ a = a ^ (a >> 4);
+ a = a * 2057;
+ a = a ^ (a >> 16);
+ return a;
+}
+
+/* Thomas Wang's multiplicative hash function. About 0x30 bytes, and it is
+ * extremely fast on recent processors with a fast multiply. However, it
+ * must not be used on low bits only, as multiples of 0x00100010 only return
+ * even values !
+ */
+int counts_tw3[NSERV][NSERV];
+uint32_t hash_tw3(uint32_t a)
+{
+ a = (a ^ 61) ^ (a >> 16);
+ a = a + (a << 3);
+ a = a ^ (a >> 4);
+ a = a * 0x27d4eb2d;
+ a = a ^ (a >> 15);
+ return a;
+}
+
+
+/* Full-avalanche integer hashing function from Bob Jenkins, suitable for use
+ * with a modulo. It has a very smooth distribution.
+ * http://burtleburtle.net/bob/hash/integer.html
+ * About 0x50 bytes, 6 shifts.
+ */
+int counts_bj6[NSERV][NSERV];
+int counts_bj6x[NSERV][NSERV];
+uint32_t hash_bj6(uint32_t a)
+{
+ a = (a+0x7ed55d16) + (a<<12);
+ a = (a^0xc761c23c) ^ (a>>19);
+ a = (a+0x165667b1) + (a<<5);
+ a = (a+0xd3a2646c) ^ (a<<9);
+ a = (a+0xfd7046c5) + (a<<3);
+ a = (a^0xb55a4f09) ^ (a>>16);
+ return a;
+}
+
+/* Similar function with one more shift and no magic number. It is slightly
+ * slower but provides the overall smoothest distribution.
+ * About 0x40 bytes, 7 shifts.
+ */
+int counts_bj7[NSERV][NSERV];
+int counts_bj7x[NSERV][NSERV];
+uint32_t hash_bj7(uint32_t a)
+{
+ a -= (a<<6);
+ a ^= (a>>17);
+ a -= (a<<9);
+ a ^= (a<<4);
+ a -= (a<<3);
+ a ^= (a<<10);
+ a ^= (a>>15);
+ return a;
+}
+
+
+void count_hash_results(unsigned long hash, int counts[NSERV][NSERV]) {
+ int srv, nsrv;
+
+ for (nsrv = 0; nsrv < NSERV; nsrv++) {
+ srv = hash % (nsrv + 1);
+ counts[nsrv][srv]++;
+ }
+}
+
+void dump_hash_results(char *name, int counts[NSERV][NSERV]) {
+ int srv, nsrv;
+ double err, total_err, max_err;
+
+ printf("%s:\n", name);
+ for (nsrv = 0; nsrv < NSERV; nsrv++) {
+ total_err = 0.0;
+ max_err = 0.0;
+ printf("%02d srv: ", nsrv+1);
+ for (srv = 0; srv <= nsrv; srv++) {
+ err = 100.0*(counts[nsrv][srv] - (double)counts[0][0]/(nsrv+1)) / (double)counts[0][0];
+ //printf("%6d ", counts[nsrv][srv]);
+ printf("% 3.1f%%%c ", err,
+ counts[nsrv][srv]?' ':'*'); /* display '*' when a server is never selected */
+ err = fabs(err);
+ total_err += err;
+ if (err > max_err)
+ max_err = err;
+ }
+ total_err /= (double)(nsrv+1);
+ for (srv = nsrv+1; srv < NSERV; srv++)
+ printf(" ");
+ printf(" avg_err=%3.1f, max_err=%3.1f\n", total_err, max_err);
+ }
+ printf("\n");
+}
+
+int main() {
+ int nr;
+ unsigned int address = 0;
+ unsigned int mask = ~0;
+
+ memset(counts_id, 0, sizeof(counts_id));
+ memset(counts_tw1, 0, sizeof(counts_tw1));
+ memset(counts_tw2, 0, sizeof(counts_tw2));
+ memset(counts_tw3, 0, sizeof(counts_tw3));
+ memset(counts_bj6, 0, sizeof(counts_bj6));
+ memset(counts_bj7, 0, sizeof(counts_bj7));
+
+ address = 0x10000000;
+ mask = 0xffffff00; // user mask to apply to addresses
+ for (nr = 0; nr < 0x10; nr++) {
+ //address += ~nr; // semi-random addresses.
+ //address += 1;
+ address += 0x00000100;
+ //address += 0x11111111;
+ //address += 7;
+ //address += 8;
+ //address += 256;
+ //address += 65536;
+ //address += 131072;
+ //address += 0x00100010; // this increment kills tw3 !
+ count_hash_results(hash_id (address & mask), counts_id); // 0.69s / 100M
+ count_hash_results(hash_tw1(address & mask), counts_tw1); // 1.04s / 100M
+ count_hash_results(hash_tw2(address & mask), counts_tw2); // 1.13s / 100M
+ count_hash_results(hash_tw3(address & mask), counts_tw3); // 1.01s / 100M
+ count_hash_results(hash_bj6(address & mask), counts_bj6); // 1.07s / 100M
+ count_hash_results(hash_bj7(address & mask), counts_bj7); // 1.20s / 100M
+ /* adding the original address after the hash reduces the error
+ * rate in in presence of very small data sets (eg: 16 source
+ * addresses for 8 servers). In this case, bj7 is very good.
+ */
+ count_hash_results(hash_bj6(address & mask)+(address&mask), counts_bj6x); // 1.07s / 100M
+ count_hash_results(hash_bj7(address & mask)+(address&mask), counts_bj7x); // 1.20s / 100M
+ }
+
+ dump_hash_results("hash_id", counts_id);
+ dump_hash_results("hash_tw1", counts_tw1);
+ dump_hash_results("hash_tw2", counts_tw2);
+ dump_hash_results("hash_tw3", counts_tw3);
+ dump_hash_results("hash_bj6", counts_bj6);
+ dump_hash_results("hash_bj6x", counts_bj6x);
+ dump_hash_results("hash_bj7", counts_bj7);
+ dump_hash_results("hash_bj7x", counts_bj7x);
+ return 0;
+}
diff --git a/tests/exp/test_hashes.c b/tests/exp/test_hashes.c
new file mode 100644
index 0000000..39cb965
--- /dev/null
+++ b/tests/exp/test_hashes.c
@@ -0,0 +1,559 @@
+/*
+ This file only show how many operations a hash is able to handle.
+ It don't show the distribution nor collisions.
+
+ gcc -Wall -O3 -o test_hashes test_hashes.c
+ ./test_hashes |sort -k 3 -r
+ */
+#include <sys/time.h>
+#include <time.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+#include <stdio.h>
+//#include <stdint.h>
+
+
+static struct timeval timeval_current(void)
+{
+ struct timeval tv;
+ gettimeofday(&tv, NULL);
+ return tv;
+}
+
+static double timeval_elapsed(struct timeval *tv)
+{
+ struct timeval tv2 = timeval_current();
+ return (tv2.tv_sec - tv->tv_sec) +
+ (tv2.tv_usec - tv->tv_usec)*1.0e-6;
+}
+
+#define HAPROXY_BACKENDS 4
+
+unsigned long haproxy_uri_hash(char *uri, int uri_len){
+
+ unsigned long hash = 0;
+ int c;
+
+ while (uri_len--) {
+ c = *uri++;
+ if (c == '?')
+ break;
+ hash = c + (hash << 6) + (hash << 16) - hash;
+ }
+
+ return hash%HAPROXY_BACKENDS; /* I assume 4 active backends */
+} /* end haproxy_hash() */
+
+/*
+ * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
+ */
+unsigned sax_hash ( void *key, int len )
+{
+ unsigned char *p = key;
+ unsigned h = 0;
+ int i;
+
+ for ( i = 0; i < len; i++ )
+ h ^= ( h << 5 ) + ( h >> 2 ) + p[i];
+
+ return h;
+}
+
+#include <arpa/inet.h>
+/* len 4 for ipv4 and 16 for ipv6 */
+unsigned int haproxy_server_hash(const char *addr, int len){
+ unsigned int h, l;
+ l = h = 0;
+
+ while ((l + sizeof (int)) <= len) {
+ h ^= ntohl(*(unsigned int *)(&addr[l]));
+ l += sizeof (int);
+ }
+ return h %= HAPROXY_BACKENDS;
+}/* end haproxy_server_hash() */
+
+
+int hashpjw(const void *key) {
+
+ const char *ptr;
+ unsigned int val;
+ /*********************************************************************
+ * *
+ * Hash the key by performing a number of bit operations on it. *
+ * *
+ *********************************************************************/
+
+ val = 0;
+ ptr = key;
+
+ while (*ptr != '\0') {
+
+ int tmp;
+
+ val = (val << 4) + (*ptr);
+
+ if((tmp = (val & 0xf0000000))) {
+ val = val ^ (tmp >> 24);
+ val = val ^ tmp;
+ }
+ ptr++;
+ }/* end while */
+
+ return val;
+}/* end hashpjw */
+
+static unsigned long
+hash_djbx33(
+ register unsigned char *key,
+ register size_t len)
+{
+ register unsigned long hash = 5381;
+
+ /* the hash unrolled eight times */
+ for (; len >= 8; len -= 8) {
+ hash = ((hash << 5) + hash) + *key++;
+ hash = ((hash << 5) + hash) + *key++;
+ hash = ((hash << 5) + hash) + *key++;
+ hash = ((hash << 5) + hash) + *key++;
+ hash = ((hash << 5) + hash) + *key++;
+ hash = ((hash << 5) + hash) + *key++;
+ hash = ((hash << 5) + hash) + *key++;
+ hash = ((hash << 5) + hash) + *key++;
+ }
+ switch (len) {
+ case 7: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
+ case 6: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
+ case 5: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
+ case 4: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
+ case 3: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
+ case 2: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
+ case 1: hash = ((hash << 5) + hash) + *key++; break;
+ default: /* case 0: */ break;
+ }
+ return hash;
+}
+
+typedef unsigned long int ub4; /* unsigned 4-byte quantities */
+typedef unsigned char ub1; /* unsigned 1-byte quantities */
+
+ub4 bernstein(ub1 *key, ub4 len, ub4 level){
+ ub4 hash = level;
+ ub4 i;
+ for (i=0; i<len; ++i) hash = 33*hash + key[i];
+ return hash;
+}
+
+/*
+ * http://www.azillionmonkeys.com/qed/hash.html
+ */
+#undef get16bits
+#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
+ || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
+#define get16bits(d) (*((const uint16_t *) (d)))
+#endif
+
+#if !defined (get16bits)
+#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
+ +(uint32_t)(((const uint8_t *)(d))[0]) )
+#endif
+
+uint32_t SuperFastHash (const char * data, int len) {
+uint32_t hash = len, tmp;
+int rem;
+
+ if (len <= 0 || data == NULL) return 0;
+
+ rem = len & 3;
+ len >>= 2;
+
+ /* Main loop */
+ for (;len > 0; len--) {
+ hash += get16bits (data);
+ tmp = (get16bits (data+2) << 11) ^ hash;
+ hash = (hash << 16) ^ tmp;
+ data += 2*sizeof (uint16_t);
+ hash += hash >> 11;
+ }
+
+ /* Handle end cases */
+ switch (rem) {
+ case 3: hash += get16bits (data);
+ hash ^= hash << 16;
+ hash ^= data[sizeof (uint16_t)] << 18;
+ hash += hash >> 11;
+ break;
+ case 2: hash += get16bits (data);
+ hash ^= hash << 11;
+ hash += hash >> 17;
+ break;
+ case 1: hash += *data;
+ hash ^= hash << 10;
+ hash += hash >> 1;
+ }
+
+ /* Force "avalanching" of final 127 bits */
+ hash ^= hash << 3;
+ hash += hash >> 5;
+ hash ^= hash << 4;
+ hash += hash >> 17;
+ hash ^= hash << 25;
+ hash += hash >> 6;
+
+ return hash;
+}
+
+/*
+ * This variant is about 15% faster.
+ */
+uint32_t SuperFastHash2 (const char * data, int len) {
+uint32_t hash = len, tmp;
+int rem;
+
+ if (len <= 0 || data == NULL) return 0;
+
+ rem = len & 3;
+ len >>= 2;
+
+ /* Main loop */
+ for (;len > 0; len--) {
+ register uint32_t next;
+ next = get16bits(data+2);
+ hash += get16bits(data);
+ tmp = (next << 11) ^ hash;
+ hash = (hash << 16) ^ tmp;
+ data += 2*sizeof (uint16_t);
+ hash += hash >> 11;
+ }
+
+ /* Handle end cases */
+ switch (rem) {
+ case 3: hash += get16bits (data);
+ hash ^= hash << 16;
+ hash ^= data[sizeof (uint16_t)] << 18;
+ hash += hash >> 11;
+ break;
+ case 2: hash += get16bits (data);
+ hash ^= hash << 11;
+ hash += hash >> 17;
+ break;
+ case 1: hash += *data;
+ hash ^= hash << 10;
+ hash += hash >> 1;
+ }
+
+ /* Force "avalanching" of final 127 bits */
+ hash ^= hash << 3;
+ hash += hash >> 5;
+ hash ^= hash << 4;
+ hash += hash >> 17;
+ hash ^= hash << 25;
+ hash += hash >> 6;
+
+ return hash;
+}
+
+/*
+ * 32 bit FNV-0 hash type
+ */
+typedef unsigned long Fnv32_t;
+
+/*
+ * fnv_32a_str - perform a 32 bit Fowler/Noll/Vo FNV-1a hash on a string
+ *
+ * input:
+ * str - string to hash
+ * hval - previous hash value or 0 if first call
+ *
+ * returns:
+ * 32 bit hash as a static hash type
+ *
+ * NOTE: To use the recommended 32 bit FNV-1a hash, use FNV1_32A_INIT as the
+ * hval arg on the first call to either fnv_32a_buf() or fnv_32a_str().
+ */
+Fnv32_t
+fnv_32a_str(char *str, Fnv32_t hval)
+{
+ unsigned char *s = (unsigned char *)str; /* unsigned string */
+
+ /*
+ * FNV-1a hash each octet in the buffer
+ */
+ while (*s) {
+
+ /* xor the bottom with the current octet */
+ hval ^= (Fnv32_t)*s++;
+
+/* #define NO_FNV_GCC_OPTIMIZATION */
+ /* multiply by the 32 bit FNV magic prime mod 2^32 */
+#if defined(NO_FNV_GCC_OPTIMIZATION)
+ /*
+ * 32 bit magic FNV-1a prime
+ */
+#define FNV_32_PRIME ((Fnv32_t)0x01000193)
+ hval *= FNV_32_PRIME;
+#else
+ hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);
+#endif
+ }
+
+ /* return our new hash value */
+ return hval;
+}
+
+/*
+ * from lookup3.c, by Bob Jenkins, May 2006, Public Domain.
+ */
+
+#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
+
+/*
+-------------------------------------------------------------------------------
+mix -- mix 3 32-bit values reversibly.
+
+This is reversible, so any information in (a,b,c) before mix() is
+still in (a,b,c) after mix().
+
+If four pairs of (a,b,c) inputs are run through mix(), or through
+mix() in reverse, there are at least 32 bits of the output that
+are sometimes the same for one pair and different for another pair.
+This was tested for:
+* pairs that differed by one bit, by two bits, in any combination
+ of top bits of (a,b,c), or in any combination of bottom bits of
+ (a,b,c).
+* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
+ the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
+ is commonly produced by subtraction) look like a single 1-bit
+ difference.
+* the base values were pseudorandom, all zero but one bit set, or
+ all zero plus a counter that starts at zero.
+
+Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
+satisfy this are
+ 4 6 8 16 19 4
+ 9 15 3 18 27 15
+ 14 9 3 7 17 3
+Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
+for "differ" defined as + with a one-bit base and a two-bit delta. I
+used http://burtleburtle.net/bob/hash/avalanche.html to choose
+the operations, constants, and arrangements of the variables.
+
+This does not achieve avalanche. There are input bits of (a,b,c)
+that fail to affect some output bits of (a,b,c), especially of a. The
+most thoroughly mixed value is c, but it doesn't really even achieve
+avalanche in c.
+
+This allows some parallelism. Read-after-writes are good at doubling
+the number of bits affected, so the goal of mixing pulls in the opposite
+direction as the goal of parallelism. I did what I could. Rotates
+seem to cost as much as shifts on every machine I could lay my hands
+on, and rotates are much kinder to the top and bottom bits, so I used
+rotates.
+-------------------------------------------------------------------------------
+*/
+#define mix(a,b,c) \
+{ \
+ a -= c; a ^= rot(c, 4); c += b; \
+ b -= a; b ^= rot(a, 6); a += c; \
+ c -= b; c ^= rot(b, 8); b += a; \
+ a -= c; a ^= rot(c,16); c += b; \
+ b -= a; b ^= rot(a,19); a += c; \
+ c -= b; c ^= rot(b, 4); b += a; \
+}
+
+/*
+-------------------------------------------------------------------------------
+final -- final mixing of 3 32-bit values (a,b,c) into c
+
+Pairs of (a,b,c) values differing in only a few bits will usually
+produce values of c that look totally different. This was tested for
+* pairs that differed by one bit, by two bits, in any combination
+ of top bits of (a,b,c), or in any combination of bottom bits of
+ (a,b,c).
+* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
+ the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
+ is commonly produced by subtraction) look like a single 1-bit
+ difference.
+* the base values were pseudorandom, all zero but one bit set, or
+ all zero plus a counter that starts at zero.
+
+These constants passed:
+ 14 11 25 16 4 14 24
+ 12 14 25 16 4 14 24
+and these came close:
+ 4 8 15 26 3 22 24
+ 10 8 15 26 3 22 24
+ 11 8 15 26 3 22 24
+-------------------------------------------------------------------------------
+*/
+#define final(a,b,c) \
+{ \
+ c ^= b; c -= rot(b,14); \
+ a ^= c; a -= rot(c,11); \
+ b ^= a; b -= rot(a,25); \
+ c ^= b; c -= rot(b,16); \
+ a ^= c; a -= rot(c,4); \
+ b ^= a; b -= rot(a,14); \
+ c ^= b; c -= rot(b,24); \
+}
+
+/*
+--------------------------------------------------------------------
+ This works on all machines. To be useful, it requires
+ -- that the key be an array of uint32_t's, and
+ -- that the length be the number of uint32_t's in the key
+
+ The function hashword() is identical to hashlittle() on little-endian
+ machines, and identical to hashbig() on big-endian machines,
+ except that the length has to be measured in uint32_ts rather than in
+ bytes. hashlittle() is more complicated than hashword() only because
+ hashlittle() has to dance around fitting the key bytes into registers.
+--------------------------------------------------------------------
+*/
+uint32_t hashword(
+const uint32_t *k, /* the key, an array of uint32_t values */
+size_t length, /* the length of the key, in uint32_ts */
+uint32_t initval) /* the previous hash, or an arbitrary value */
+{
+ uint32_t a,b,c;
+
+ /* Set up the internal state */
+ a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
+
+ /*------------------------------------------------- handle most of the key */
+ while (length > 3)
+ {
+ a += k[0];
+ b += k[1];
+ c += k[2];
+ mix(a,b,c);
+ length -= 3;
+ k += 3;
+ }
+
+ /*------------------------------------------- handle the last 3 uint32_t's */
+ switch(length) /* all the case statements fall through */
+ {
+ case 3 : c+=k[2];
+ case 2 : b+=k[1];
+ case 1 : a+=k[0];
+ final(a,b,c);
+ case 0: /* case 0: nothing left to add */
+ break;
+ }
+ /*------------------------------------------------------ report the result */
+ return c;
+}
+
+/* from K&R book site 139 */
+#define HASHSIZE 101
+
+unsigned kr_hash(char *s){
+ unsigned hashval;
+
+ for(hashval = 0; *s != '\0';s++)
+ hashval = *s + 31 * hashval;
+
+ return hashval % HASHSIZE;
+
+} /* end kr_hash() */
+
+unsigned fnv_hash ( void *key, int len )
+{
+ unsigned char *p = key;
+ unsigned h = 2166136261;
+ int i;
+
+ for ( i = 0; i < len; i++ )
+ h = ( h * 16777619 ) ^ p[i];
+
+ return h;
+}
+
+unsigned oat_hash ( void *key, int len )
+{
+ unsigned char *p = key;
+ unsigned h = 0;
+ int i;
+
+ for ( i = 0; i < len; i++ ) {
+ h += p[i];
+ h += ( h << 10 );
+ h ^= ( h >> 6 );
+ }
+
+ h += ( h << 3 );
+ h ^= ( h >> 11 );
+ h += ( h << 15 );
+
+ return h;
+}
+
+unsigned wt_hash ( void *key, int len )
+{
+ unsigned char *p = key;
+ unsigned h = 0x783c965aUL;
+ unsigned step = 16;
+
+ for (; len > 0; len--) {
+ h ^= *p * 9;
+ p++;
+ h = (h << step) | (h >> (32-step));
+ step ^= h;
+ step &= 0x1F;
+ }
+
+ return h;
+}
+
+
+#define run_test(fct, args) { \
+ unsigned long loop, count; \
+ volatile unsigned long result; \
+ double delta; \
+ struct timeval tv; \
+ fprintf(stderr, "Starting %s\n", #fct); \
+ tv = timeval_current(); \
+ count = 0; \
+ do { \
+ delta = timeval_elapsed(&tv); \
+ for (loop = 0; loop < 1000; loop++) { \
+ result = fct args; \
+ count++; \
+ } \
+ } while (delta < 1.0); \
+ fprintf(stdout, "%-20s : %10.0f run/sec\n", #fct, count/delta); \
+ fflush(stdout); \
+}
+
+int main(){
+
+ char **start;
+ int len;
+
+ char *urls[] = {
+ "http://www.microsoft.com/shared/core/1/webservice/navigation.asmx/DisplayDownlevelNavHtml",
+ NULL
+ };
+
+ start = urls;
+ len = strlen(*urls);
+
+ run_test(wt_hash, (*urls, len));
+ run_test(SuperFastHash2, (*urls, len));
+ run_test(SuperFastHash, (*urls, len));
+ run_test(haproxy_uri_hash, (*urls, len));
+ run_test(haproxy_server_hash, (*urls, len));
+ run_test(hashpjw, (*urls));
+ run_test(hash_djbx33, ((unsigned char *)*urls, len));
+ run_test(bernstein, ((unsigned char *)*urls, len, 4));
+ run_test(fnv_32a_str, (*urls, 0));
+ run_test(hashword, ((const uint32_t *)*urls,strlen(*urls),0));
+ run_test(kr_hash, (*urls));
+ run_test(sax_hash, (*urls, len));
+ run_test(fnv_hash, (*urls, len));
+ run_test(oat_hash, (*urls, len));
+
+ return 0;
+
+}/* end main() */
diff --git a/tests/exp/testinet.c b/tests/exp/testinet.c
new file mode 100644
index 0000000..0eb87e9
--- /dev/null
+++ b/tests/exp/testinet.c
@@ -0,0 +1,28 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <string.h>
+#include <ctype.h>
+#include <sys/time.h>
+#include <sys/types.h>
+#include <sys/socket.h>
+#include <netinet/tcp.h>
+#include <netinet/in.h>
+#include <arpa/inet.h>
+#include <netdb.h>
+#include <fcntl.h>
+#include <errno.h>
+#include <signal.h>
+#include <stdarg.h>
+#include <sys/resource.h>
+#include <time.h>
+#include <regex.h>
+#include <syslog.h>
+
+
+int main() {
+ printf("sizeof sockaddr=%d\n", sizeof(struct sockaddr));
+ printf("sizeof sockaddr_in=%d\n", sizeof(struct sockaddr_in));
+ printf("sizeof sockaddr_in6=%d\n", sizeof(struct sockaddr_in6));
+ return 0;
+}
diff --git a/tests/exp/uri_hash.c b/tests/exp/uri_hash.c
new file mode 100644
index 0000000..0b5d755
--- /dev/null
+++ b/tests/exp/uri_hash.c
@@ -0,0 +1,377 @@
+#include <stdio.h>
+#include <string.h>
+#include <arpa/inet.h>
+
+#define NSERV 10
+#define MAXLINE 1000
+
+char line[MAXLINE];
+
+int counts_gd1[NSERV][NSERV];
+static unsigned long hash_gd1(char *uri)
+{
+ unsigned long hash = 0;
+ int c;
+
+ while ((c = *uri++))
+ hash = c + (hash << 6) + (hash << 16) - hash;
+
+ return hash;
+}
+
+int counts_gd2[NSERV][NSERV];
+static unsigned long hash_gd2(char *uri)
+{
+ unsigned long hash = 0;
+ int c;
+
+ while ((c = *uri++)) {
+ if (c == '?' || c == '\n')
+ break;
+ hash = c + (hash << 6) + (hash << 16) - hash;
+ }
+
+ return hash;
+}
+
+
+int counts_gd3[NSERV][NSERV];
+static unsigned long hash_gd3(char *uri)
+{
+ unsigned long hash = 0;
+ int c;
+
+ while ((c = *uri++)) {
+ if (c == '?' || c == '\n')
+ break;
+ hash = c - (hash << 3) + (hash << 15) - hash;
+ }
+
+ return hash;
+}
+
+
+int counts_gd4[NSERV][NSERV];
+static unsigned long hash_gd4(char *uri)
+{
+ unsigned long hash = 0;
+ int c;
+
+ while ((c = *uri++)) {
+ if (c == '?' || c == '\n')
+ break;
+ hash = hash + (hash << 6) - (hash << 15) - c;
+ }
+
+ return hash;
+}
+
+
+int counts_gd5[NSERV][NSERV];
+static unsigned long hash_gd5(char *uri)
+{
+ unsigned long hash = 0;
+ int c;
+
+ while ((c = *uri++)) {
+ if (c == '?' || c == '\n')
+ break;
+ hash = hash + (hash << 2) - (hash << 19) - c;
+ }
+
+ return hash;
+}
+
+
+int counts_gd6[NSERV][NSERV];
+static unsigned long hash_gd6(char *uri)
+{
+ unsigned long hash = 0;
+ int c;
+
+ while ((c = *uri++)) {
+ if (c == '?' || c == '\n')
+ break;
+ hash = hash + (hash << 2) - (hash << 22) - c;
+ }
+
+ return hash;
+}
+
+
+int counts_wt1[NSERV][NSERV];
+static unsigned long hash_wt1(int hsize, char *string) {
+ int bits;
+ unsigned long data, val;
+
+ bits = val = data = 0;
+ while (*string) {
+ if (*string == '?' || *string == '\n')
+ break;
+ data |= ((unsigned long)(unsigned char)*string) << bits;
+ bits += 8;
+ while (bits >= hsize) {
+ val ^= data - (val >> hsize);
+ bits -= hsize;
+ data >>= hsize;
+ }
+ string++;
+ }
+ val ^= data;
+ while (val > ((1 << hsize) - 1)) {
+ val = (val & ((1 << hsize) - 1)) ^ (val >> hsize);
+ }
+ return val;
+}
+
+/*
+ * efficient hash : no duplicate on the first 65536 values of 2 bytes.
+ * less than 0.1% duplicates for the first 1.6 M values of 3 bytes.
+ */
+int counts_wt2[NSERV][NSERV];
+typedef unsigned int u_int32_t;
+
+static inline u_int32_t shl32(u_int32_t i, int count) {
+ if (count == 32)
+ return 0;
+ return i << count;
+}
+
+static inline u_int32_t shr32(u_int32_t i, int count) {
+ if (count == 32)
+ return 0;
+ return i >> count;
+}
+
+static unsigned int rev32(unsigned int c) {
+ c = ((c & 0x0000FFFF) << 16)| ((c & 0xFFFF0000) >> 16);
+ c = ((c & 0x00FF00FF) << 8) | ((c & 0xFF00FF00) >> 8);
+ c = ((c & 0x0F0F0F0F) << 4) | ((c & 0xF0F0F0F0) >> 4);
+ c = ((c & 0x33333333) << 2) | ((c & 0xCCCCCCCC) >> 2);
+ c = ((c & 0x55555555) << 1) | ((c & 0xAAAAAAAA) >> 1);
+ return c;
+}
+
+int hash_wt2(const char *src, int len) {
+ unsigned int i = 0x3C964BA5; /* as many ones as zeroes */
+ unsigned int j;
+ unsigned int ih, il;
+ int bit;
+
+ while (len--) {
+ j = (unsigned char)*src++;
+ if (j == '?' || j == '\n')
+ break;
+ bit = rev32(j - i);
+ bit = bit - (bit >> 3) + (bit >> 16) - j;
+
+ bit &= 0x1f;
+ ih = shr32(i, bit);
+ il = i & (shl32(1, bit) - 1);
+ i = shl32(il, 32-bit) - ih - ~j;
+ }
+ return i;
+}
+
+
+//typedef unsigned int uint32_t;
+//typedef unsigned short uint8_t;
+//typedef unsigned char uint16_t;
+
+/*
+ * http://www.azillionmonkeys.com/qed/hash.html
+ */
+#undef get16bits
+#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
+ || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
+#define get16bits(d) (*((const uint16_t *) (d)))
+#endif
+
+#if !defined (get16bits)
+#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
+ +(uint32_t)(((const uint8_t *)(d))[0]) )
+#endif
+
+/*
+ * This function has a hole of 11 unused bits in bytes 2 and 3 of each block of
+ * 32 bits.
+ */
+int counts_SuperFastHash[NSERV][NSERV];
+
+uint32_t SuperFastHash (const char * data, int len) {
+uint32_t hash = len, tmp;
+int rem;
+
+ if (len <= 0 || data == NULL) return 0;
+
+ rem = len & 3;
+ len >>= 2;
+
+ /* Main loop */
+ for (;len > 0; len--) {
+ hash += get16bits (data);
+ tmp = (get16bits (data+2) << 11) ^ hash;
+ hash = (hash << 16) ^ tmp;
+ data += 2*sizeof (uint16_t);
+ hash += hash >> 11;
+ }
+
+ /* Handle end cases */
+ switch (rem) {
+ case 3: hash += get16bits (data);
+ hash ^= hash << 16;
+ hash ^= data[sizeof (uint16_t)] << 18;
+ hash += hash >> 11;
+ break;
+ case 2: hash += get16bits (data);
+ hash ^= hash << 11;
+ hash += hash >> 17;
+ break;
+ case 1: hash += *data;
+ hash ^= hash << 10;
+ hash += hash >> 1;
+ }
+
+ /* Force "avalanching" of final 127 bits */
+ hash ^= hash << 3;
+ hash += hash >> 5;
+ hash ^= hash << 4;
+ hash += hash >> 17;
+ hash ^= hash << 25;
+ hash += hash >> 6;
+
+ return hash;
+}
+
+/*
+ * This variant uses all bits from the input block, and is about 15% faster.
+ */
+int counts_SuperFastHash2[NSERV][NSERV];
+uint32_t SuperFastHash2 (const char * data, int len) {
+uint32_t hash = len, tmp;
+int rem;
+
+ if (len <= 0 || data == NULL) return 0;
+
+ rem = len & 3;
+ len >>= 2;
+
+ /* Main loop */
+ for (;len > 0; len--) {
+ register uint32_t next;
+ next = get16bits(data+2);
+ hash += get16bits(data);
+ tmp = ((next << 11) | (next >> 21)) ^ hash;
+ hash = (hash << 16) ^ tmp;
+ data += 2*sizeof (uint16_t);
+ hash += hash >> 11;
+ }
+
+ /* Handle end cases */
+ switch (rem) {
+ case 3: hash += get16bits (data);
+ hash ^= hash << 16;
+ hash ^= data[sizeof (uint16_t)] << 18;
+ hash += hash >> 11;
+ break;
+ case 2: hash += get16bits (data);
+ hash ^= hash << 11;
+ hash += hash >> 17;
+ break;
+ case 1: hash += *data;
+ hash ^= hash << 10;
+ hash += hash >> 1;
+ }
+
+ /* Force "avalanching" of final 127 bits */
+ hash ^= hash << 3;
+ hash += hash >> 5;
+ hash ^= hash << 4;
+ hash += hash >> 17;
+ hash ^= hash << 25;
+ hash += hash >> 6;
+
+ return hash;
+}
+
+/* len 4 for ipv4 and 16 for ipv6 */
+int counts_srv[NSERV][NSERV];
+unsigned int haproxy_server_hash(const char *addr, int len){
+ unsigned int h, l;
+ l = h = 0;
+
+ while ((l + sizeof (int)) <= len) {
+ h ^= ntohl(*(unsigned int *)(&addr[l]));
+ l += sizeof (int);
+ }
+ return h;
+}/* end haproxy_server_hash() */
+
+
+
+void count_hash_results(unsigned long hash, int counts[NSERV][NSERV]) {
+ int srv, nsrv;
+
+ for (nsrv = 0; nsrv < NSERV; nsrv++) {
+ srv = hash % (nsrv + 1);
+ counts[nsrv][srv]++;
+ }
+}
+
+void dump_hash_results(char *name, int counts[NSERV][NSERV]) {
+ int srv, nsrv;
+
+ printf("%s:\n", name);
+ for (nsrv = 0; nsrv < NSERV; nsrv++) {
+ printf("%02d srv: ", nsrv+1);
+ for (srv = 0; srv <= nsrv; srv++) {
+ //printf("%6d ", counts[nsrv][srv]);
+ //printf("%3.1f ", (100.0*counts[nsrv][srv]) / (double)counts[0][0]);
+ printf("%3.1f ", 100.0*(counts[nsrv][srv] - (double)counts[0][0]/(nsrv+1)) / (double)counts[0][0]);
+ }
+ printf("\n");
+ }
+ printf("\n");
+}
+
+int main() {
+ memset(counts_gd1, 0, sizeof(counts_gd1));
+ memset(counts_gd2, 0, sizeof(counts_gd2));
+ memset(counts_gd3, 0, sizeof(counts_gd3));
+ memset(counts_gd4, 0, sizeof(counts_gd4));
+ memset(counts_gd5, 0, sizeof(counts_gd5));
+ memset(counts_gd6, 0, sizeof(counts_gd6));
+ memset(counts_wt1, 0, sizeof(counts_wt1));
+ memset(counts_wt2, 0, sizeof(counts_wt2));
+ memset(counts_srv, 0, sizeof(counts_srv));
+ memset(counts_SuperFastHash, 0, sizeof(counts_SuperFastHash));
+ memset(counts_SuperFastHash2, 0, sizeof(counts_SuperFastHash2));
+
+ while (fgets(line, MAXLINE, stdin) != NULL) {
+ count_hash_results(hash_gd1(line), counts_gd1);
+ count_hash_results(hash_gd2(line), counts_gd2);
+ count_hash_results(hash_gd3(line), counts_gd3);
+ count_hash_results(hash_gd4(line), counts_gd4);
+ count_hash_results(hash_gd5(line), counts_gd5);
+ count_hash_results(hash_gd6(line), counts_gd6);
+ count_hash_results(hash_wt1(31, line), counts_wt1);
+ count_hash_results(hash_wt2(line, strlen(line)), counts_wt2);
+ count_hash_results(haproxy_server_hash(line, strlen(line)), counts_srv);
+ count_hash_results(SuperFastHash(line, strlen(line)), counts_SuperFastHash);
+ count_hash_results(SuperFastHash2(line, strlen(line)), counts_SuperFastHash2);
+ }
+
+ dump_hash_results("hash_gd1", counts_gd1);
+ dump_hash_results("hash_gd2", counts_gd2);
+ dump_hash_results("hash_gd3", counts_gd3);
+ dump_hash_results("hash_gd4", counts_gd4);
+ dump_hash_results("hash_gd5", counts_gd5);
+ dump_hash_results("hash_gd6", counts_gd6);
+ dump_hash_results("hash_wt1", counts_wt1);
+ dump_hash_results("hash_wt2", counts_wt2);
+ dump_hash_results("haproxy_server_hash", counts_srv);
+ dump_hash_results("SuperFastHash", counts_SuperFastHash);
+ dump_hash_results("SuperFastHash2", counts_SuperFastHash2);
+
+ return 0;
+}