1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <assert.h>
5 #include <math.h>
6 #include <netinet/in.h>
7 #include <arpa/inet.h>
8 #include <sys/queue.h>
9
10 #include "debug.h"
11 #include "fhash.h"
12
13 //#include "stdint.h" /* Replace with <stdint.h> if appropriate */
14 #undef get16bits
15 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
16 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
17 #define get16bits(d) (*((const uint16_t *) (d)))
18 #endif
19
20 #if !defined (get16bits)
21 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
22 +(uint32_t)(((const uint8_t *)(d))[0]) )
23 #endif
24
25 inline uint32_t
SuperFastHash(const char * data,int len)26 SuperFastHash (const char * data, int len) {
27 register uint32_t hash = len, tmp;
28 int rem;
29
30 if (len <= 0 || data == NULL) return 0;
31
32 rem = len & 3;
33 len >>= 2;
34
35 /* Main loop */
36 for (;len > 0; len--) {
37 hash += get16bits (data);
38 tmp = (get16bits (data+2) << 11) ^ hash;
39 hash = (hash << 16) ^ tmp;
40 data += 2*sizeof (uint16_t);
41 hash += hash >> 11;
42 }
43
44 /* Handle end cases */
45 switch (rem) {
46 case 3: hash += get16bits (data);
47 hash ^= hash << 16;
48 hash ^= ((signed char)data[sizeof (uint16_t)]) << 18;
49 hash += hash >> 11;
50 break;
51 case 2: hash += get16bits (data);
52 hash ^= hash << 11;
53 hash += hash >> 17;
54 break;
55 case 1: hash += (signed char)*data;
56 hash ^= hash << 10;
57 hash += hash >> 1;
58 }
59
60 /* Force "avalanching" of final 127 bits */
61 hash ^= hash << 3;
62 hash += hash >> 5;
63 hash ^= hash << 4;
64 hash += hash >> 17;
65 hash ^= hash << 25;
66 hash += hash >> 6;
67
68 return hash;
69 }
70
71 /*----------------------------------------------------------------------------*/
72 inline unsigned int
HashFlow(const tcp_stream * flow)73 HashFlow(const tcp_stream *flow)
74 {
75 #if 0
76 register unsigned int hash, i;
77 char *key = (char *)&flow->saddr;
78
79 for (hash = i = 0; i < 12; ++i) {
80 hash += key[i];
81 hash += (hash << 10);
82 hash ^= (hash >> 6);
83 }
84 hash += (hash << 3);
85 hash ^= (hash >> 11);
86 hash += (hash << 15);
87
88 return hash & (NUM_BINS - 1);
89 #else
90 return SuperFastHash((const char *)&flow->saddr, 12) & (NUM_BINS - 1);
91 #endif
92 }
93 /*---------------------------------------------------------------------------*/
94 #define EQUAL_FLOW(flow1, flow2) \
95 (flow1->saddr == flow2->saddr && flow1->sport == flow2->sport && \
96 flow1->daddr == flow2->daddr && flow1->dport == flow2->dport)
97 /*---------------------------------------------------------------------------*/
98 struct hashtable *
CreateHashtable(void)99 CreateHashtable(void) // equality
100 {
101 int i;
102 struct hashtable* ht = calloc(1, sizeof(struct hashtable));
103 if (!ht){
104 TRACE_ERROR("calloc: CreateHashtable");
105 return 0;
106 }
107
108 /* init the tables */
109 for (i = 0; i < NUM_BINS; i++)
110 TAILQ_INIT(&ht->ht_table[i]);
111 return ht;
112 }
113 /*----------------------------------------------------------------------------*/
114 void
DestroyHashtable(struct hashtable * ht)115 DestroyHashtable(struct hashtable *ht)
116 {
117 free(ht);
118 }
119 /*----------------------------------------------------------------------------*/
120 int
HTInsert(struct hashtable * ht,tcp_stream * item,unsigned int * hash)121 HTInsert(struct hashtable *ht, tcp_stream *item, unsigned int *hash)
122 {
123 /* create an entry*/
124 int idx;
125
126 assert(ht);
127 assert(ht->ht_count <= 65535); // uint16_t ht_count
128
129 if (hash)
130 idx = (int)*hash;
131 else
132 idx = HashFlow(item);
133
134 assert(idx >=0 && idx < NUM_BINS);
135
136 #if STATIC_TABLE
137 int i;
138 for (i = 0; i < TCP_AR_CNT; i++) {
139 // insert into empty array slot
140 if (!ht->ht_array[idx][i]) {
141 ht->ht_array[idx][i] = item;
142 item->ht_idx = i;
143 ht->ht_count++;
144 return 0;
145 }
146 }
147
148 TRACE_INFO("[WARNING] HTSearch() cnt: %d!!\n", TCP_AR_CNT);
149 #endif
150
151 TAILQ_INSERT_TAIL(&ht->ht_table[idx], item, rcvvar->he_link);
152 item->rcvvar->he_mybucket = &ht->ht_table[idx];
153 item->ht_idx = TCP_AR_CNT;
154 ht->ht_count++;
155
156 return 0;
157 }
158 /*----------------------------------------------------------------------------*/
159 void*
HTRemove(struct hashtable * ht,tcp_stream * item)160 HTRemove(struct hashtable *ht, tcp_stream *item)
161 {
162 hash_bucket_head *head;
163 //int idx = HashFlow(item);
164
165 #if STATIC_TABLE
166 if (item->ht_idx < TCP_AR_CNT) {
167 assert(ht_array[idx][item->ht_idx]);
168 ht->ht_array[idx][item->ht_idx] = NULL;
169 } else {
170 #endif
171 //head = &ht->ht_table[idx];
172 head = item->rcvvar->he_mybucket;
173 assert(head);
174 TAILQ_REMOVE(head, item, rcvvar->he_link);
175 #if STATIC_TABLE
176 }
177 #endif
178
179 ht->ht_count--;
180 return (item);
181 }
182 /*----------------------------------------------------------------------------*/
183 tcp_stream*
HTSearch(struct hashtable * ht,const tcp_stream * item,unsigned int * hash)184 HTSearch(struct hashtable *ht, const tcp_stream *item, unsigned int *hash)
185 {
186 tcp_stream *walk;
187 hash_bucket_head *head;
188 int idx;
189
190 #if STATIC_TABLE
191 int i;
192
193 idx = HashFlow(item);
194
195 for (i = 0; i < TCP_AR_CNT; i++) {
196 if (ht->ht_array[idx][i]) {
197 if (EQUAL_FLOW(ht->ht_array[idx][i], item))
198 return ht->ht_array[idx][i];
199 }
200 }
201 #endif
202
203 idx = HashFlow(item);
204 *hash = idx;
205
206 head = &ht->ht_table[idx];
207
208 TAILQ_FOREACH(walk, head, rcvvar->he_link) {
209 if (EQUAL_FLOW(walk, item))
210 return walk;
211 }
212
213 return NULL;
214 }
215 /*----------------------------------------------------------------------------*/
216