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 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 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 * 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 115 DestroyHashtable(struct hashtable *ht) 116 { 117 free(ht); 118 } 119 /*----------------------------------------------------------------------------*/ 120 int 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* 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* 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