diff options
Diffstat (limited to 'example')
| -rw-r--r-- | example/ndpiReader.c | 691 | ||||
| -rw-r--r-- | example/ndpi_util.c | 157 | ||||
| -rw-r--r-- | example/ndpi_util.h | 14 | ||||
| -rw-r--r-- | example/uthash.h | 1096 |
4 files changed, 1847 insertions, 111 deletions
diff --git a/example/ndpiReader.c b/example/ndpiReader.c index dda137df9..ac3d75e77 100644 --- a/example/ndpiReader.c +++ b/example/ndpiReader.c @@ -24,11 +24,11 @@ #endif #include <stdio.h> #include <stdlib.h> +#include <getopt.h> #ifdef WIN32 #include <winsock2.h> /* winsock.h is included automatically */ #include <process.h> #include <io.h> -#include <getopt.h> #define getopt getopt____ #else #include <unistd.h> @@ -44,6 +44,7 @@ #include <assert.h> #include "../config.h" #include "ndpi_api.h" +#include "uthash.h" #ifdef HAVE_JSON_C #include <json.h> @@ -68,10 +69,12 @@ static u_int8_t live_capture = 0; static u_int8_t undetected_flows_deleted = 0; /** User preferences **/ static u_int8_t enable_protocol_guess = 1, verbose = 0, nDPI_traceLevel = 0, json_flag = 0; +static u_int32_t pcap_analysis_duration = (u_int32_t)-1; static u_int16_t decode_tunnels = 0; static u_int16_t num_loops = 1; static u_int8_t shutdown_app = 0, quiet_mode = 0; static u_int8_t num_threads = 1; +static struct timeval begin, end; #ifdef linux static int core_affinity[MAX_NUM_READER_THREADS]; #endif @@ -81,6 +84,40 @@ static time_t capture_for = 0; static time_t capture_until = 0; static u_int32_t num_flows; +struct info_pair{ + u_int32_t addr; + int count; +}; + +typedef struct node_a{ + u_int32_t addr; + int count; + struct node_a *left, *right; +}addr_node; + +struct port_stats { + u_int32_t port; /* we'll use this field as the key */ + u_int32_t num_pkts, num_bytes; + u_int32_t num_addr; /*to hold number of distinct IP addresses */ + u_int32_t cumulative_addr; /*to hold cumulative some of IP addresses */ + addr_node *addr_tree; /* to hold distinct IP addresses */ + struct info_pair top_ip_addrs[MAX_NUM_IP_ADDRESS]; + UT_hash_handle hh; /* makes this structure hashable */ +}; + +struct port_stats *srcStats = NULL, *dstStats = NULL; + +struct ndpi_packet_trailer { + u_int32_t magic; /* 0x19682017 */ + u_int16_t master_protocol /* e.g. HTTP */, app_protocol /* e.g. FaceBook */; + char name[16]; +}; + +static pcap_dumper_t *extcap_dumper = NULL; +static char extcap_buf[16384]; +static char *extcap_capture_fifo = NULL; +static u_int16_t extcap_packet_filter = (u_int16_t)-1; + // struct associated to a workflow for a thread struct reader_thread { struct ndpi_workflow * workflow; @@ -104,9 +141,19 @@ typedef struct ndpi_id { u_int32_t current_ndpi_memory = 0, max_ndpi_memory = 0; +void test_lib(); /* Forward */ + +/* ********************************** */ + +#ifdef DEBUG_TRACE +FILE *trace = NULL; +#endif + /********************** FUNCTIONS ********************* */ + + /** * @brief Set main components necessary to the detection */ @@ -119,13 +166,14 @@ static void setupDetection(u_int16_t thread_id, pcap_t * pcap_handle); static void help(u_int long_help) { printf("Welcome to nDPI %s\n\n", ndpi_revision()); - printf("ndpiReader -i <file|device> [-f <filter>][-s <duration>]\n" + printf("ndpiReader -i <file|device> [-f <filter>][-s <duration>][-m <duration>]\n" " [-p <protos>][-l <loops> [-q][-d][-h][-t][-v <level>]\n" " [-n <threads>] [-w <file>] [-j <file>]\n\n" "Usage:\n" " -i <file.pcap|device> | Specify a pcap file/playlist to read packets from or a device for live capture (comma-separated list)\n" " -f <BPF filter> | Specify a BPF filter for filtering selected traffic\n" " -s <duration> | Maximum capture duration in seconds (live traffic capture only)\n" + " -m <duration> | Split analysis duration in <duration> max seconds\n" " -p <file>.protos | Specify a protocol file (eg. protos.txt)\n" " -l <num loops> | Number of detection loops (test only)\n" " -n <num threads> | Number of threads. Default: number of interfaces in -i. Ignored with pcap files.\n" @@ -140,7 +188,21 @@ static void help(u_int long_help) { " -w <path> | Write test output on the specified file. This is useful for\n" " | testing purposes in order to compare results across runs\n" " -h | This help\n" - " -v <1|2> | Verbose 'unknown protocol' packet print. 1=verbose, 2=very verbose\n"); + " -v <1|2|3> | Verbose 'unknown protocol' packet print. 1=verbose, 2=very verbose, 3=port stats\n"); + + #ifndef WIN32 + printf("\nExcap (wireshark) options:\n" + " --extcap-interfaces\n" + " --extcap-version\n" + " --extcap-dlts\n" + " --extcap-interface <name>\n" + " --extcap-config\n" + " --capture\n" + " --extcap-capture-filter\n" + " --fifo <path to file or pipe>\n" + " --debug\n" + ); + #endif if(long_help) { printf("\n\nSupported protocols:\n"); @@ -152,28 +214,175 @@ static void help(u_int long_help) { } +static struct option longopts[] = { + /* mandatory extcap options */ + { "extcap-interfaces", no_argument, NULL, '0'}, + { "extcap-version", optional_argument, NULL, '1'}, + { "extcap-dlts", no_argument, NULL, '2'}, + { "extcap-interface", required_argument, NULL, '3'}, + { "extcap-config", no_argument, NULL, '4'}, + { "capture", no_argument, NULL, '5'}, + { "extcap-capture-filter", required_argument, NULL, '6'}, + { "fifo", required_argument, NULL, '7'}, + { "debug", optional_argument, NULL, '8'}, + { "ndpi-proto-filter", required_argument, NULL, '9'}, + + /* ndpiReader options */ + { "enable-protocol-guess", no_argument, NULL, 'd'}, + { "interface", required_argument, NULL, 'i'}, + { "filter", required_argument, NULL, 'f'}, + { "cpu-bind", required_argument, NULL, 'g'}, + { "loops", required_argument, NULL, 'l'}, + { "num-threads", required_argument, NULL, 'n'}, + + { "protos", required_argument, NULL, 'p'}, + { "capture-duration", required_argument, NULL, 's'}, + { "decode-tunnels", no_argument, NULL, 't'}, + { "revision", no_argument, NULL, 'r'}, + { "verbose", no_argument, NULL, 'v'}, + { "version", no_argument, NULL, 'V'}, + { "help", no_argument, NULL, 'h'}, + { "json", required_argument, NULL, 'j'}, + { "result-path", required_argument, NULL, 'w'}, + { "quiet", no_argument, NULL, 'q'}, + + {0, 0, 0, 0} +}; + +/* ********************************** */ + +void extcap_interfaces() { + printf("extcap {version=%s}\n", ndpi_revision()); + printf("interface {value=ndpi}{display=nDPI interface}\n"); + exit(0); +} + +/* ********************************** */ + +void extcap_dlts() { + u_int dlts_number = DLT_EN10MB; + printf("dlt {number=%u}{name=%s}{display=%s}\n", dlts_number, "ndpi", "nDPI Interface"); + exit(0); +} + +/* ********************************** */ + +struct ndpi_proto_sorter { + int id; + char name[16]; +}; + +int cmpProto(const void *_a, const void *_b) { + struct ndpi_proto_sorter *a = (struct ndpi_proto_sorter*)_a; + struct ndpi_proto_sorter *b = (struct ndpi_proto_sorter*)_b; + + return(strcmp(a->name, b->name)); +} + +void extcap_config() { + int i, argidx = 0; + struct ndpi_detection_module_struct *ndpi_mod; + struct ndpi_proto_sorter *protos; + + /* -i <interface> */ + printf("arg {number=%u}{call=-i}{display=Capture Interface or Pcap File Path}{type=string}" + "{tooltip=The interface name}\n", argidx++); + +#if 0 + printf("arg {number=%u}{call=-i}{display=Pcap File to Analize}{type=fileselect}" + "{tooltip=The pcap file to analyze (if the interface is unspecified)}\n", argidx++); +#endif + + setupDetection(0, NULL); + ndpi_mod = ndpi_thread_info[0].workflow->ndpi_struct; + + protos = (struct ndpi_proto_sorter*)malloc(sizeof(struct ndpi_proto_sorter)*ndpi_mod->ndpi_num_supported_protocols); + if(!protos) exit(0); + + for(i=0; i<(int)ndpi_mod->ndpi_num_supported_protocols; i++) { + protos[i].id = i; + snprintf(protos[i].name, sizeof(protos[i].name), "%s", ndpi_mod->proto_defaults[i].protoName); + } + + qsort(protos, ndpi_mod->ndpi_num_supported_protocols, sizeof(struct ndpi_proto_sorter), cmpProto); + + printf("arg {number=%u}{call=-9}{display=nDPI Protocol Filter}{type=selector}" + "{tooltip=nDPI Protocol to be filtered}\n", argidx); + + printf("value {arg=%d}{value=%d}{display=%s}\n", argidx, -1, "All Protocols (no nDPI filtering)"); + + for(i=0; i<(int)ndpi_mod->ndpi_num_supported_protocols; i++) + printf("value {arg=%d}{value=%d}{display=%s (%u)}\n", argidx, protos[i].id, + protos[i].name, protos[i].id); + + free(protos); + + exit(0); +} + +/* ********************************** */ + +void extcap_capture() { +#ifdef DEBUG_TRACE + if(trace) fprintf(trace, " #### %s #### \n", __FUNCTION__); +#endif + + if((extcap_dumper = pcap_dump_open(pcap_open_dead(DLT_EN10MB, 16384 /* MTU */), + extcap_capture_fifo)) == NULL) { + fprintf(stderr, "Unable to open the pcap dumper on %s", extcap_capture_fifo); + +#ifdef DEBUG_TRACE + if(trace) fprintf(trace, "Unable to open the pcap dumper on %s\n", + extcap_capture_fifo); +#endif + return; + } + +#ifdef DEBUG_TRACE + if(trace) fprintf(trace, "Starting packet capture [%p]\n", extcap_dumper); +#endif +} + +/* ********************************** */ + /** * @brief Option parser */ static void parseOptions(int argc, char **argv) { - + int option_idx = 0, do_capture = 0; char *__pcap_file = NULL, *bind_mask = NULL; int thread_id, opt; #ifdef linux u_int num_cores = sysconf(_SC_NPROCESSORS_ONLN); #endif - while ((opt = getopt(argc, argv, "df:g:i:hp:l:s:tv:V:n:j:rp:w:q")) != EOF) { +#ifdef DEBUG_TRACE + trace = fopen("/tmp/ndpiReader.log", "a"); + + if(trace) fprintf(trace, " #### %s #### \n", __FUNCTION__); +#endif + + while ((opt = getopt_long(argc, argv, "df:g:i:hp:l:s:tv:V:n:j:rp:w:q0123:456:7:89:m:", longopts, &option_idx)) != EOF) { +#ifdef DEBUG_TRACE + if(trace) fprintf(trace, " #### -%c [%s] #### \n", opt, optarg ? optarg : ""); +#endif + switch (opt) { case 'd': enable_protocol_guess = 0; break; case 'i': + case '3': _pcap_file[0] = optarg; break; + case 'm': + pcap_analysis_duration = atol(optarg); + break; + case 'f': + case '6': _bpf_filter = optarg; break; @@ -240,12 +449,47 @@ static void parseOptions(int argc, char **argv) { quiet_mode = 1; break; + /* Extcap */ + case '0': + extcap_interfaces(); + break; + + case '1': + printf("extcap {version=%s}\n", ndpi_revision()); + break; + + case '2': + extcap_dlts(); + break; + + case '4': + extcap_config(); + break; + + case '5': + do_capture = 1; + break; + + case '7': + extcap_capture_fifo = strdup(optarg); + break; + + case '8': + nDPI_traceLevel = 9; + break; + + case '9': + extcap_packet_filter = atoi(optarg); + break; + default: help(0); break; } } + if(do_capture) extcap_capture(); + // check parameters if(_pcap_file[0] == NULL || strcmp(_pcap_file[0], "") == 0) { help(0); @@ -277,6 +521,10 @@ static void parseOptions(int argc, char **argv) { } } #endif + +#ifdef DEBUG_TRACE + if(trace) fclose(trace); +#endif } @@ -355,22 +603,31 @@ static void printFlow(u_int16_t thread_id, struct ndpi_flow_info *flow) { #endif FILE *out = results_file ? results_file : stdout; + if((verbose != 1) && (verbose != 2)) + return; + if(!json_flag) { fprintf(out, "\t%u", ++num_flows); - fprintf(out, "\t%s %s%s%s:%u <-> %s%s%s:%u ", - ipProto2Name(flow->protocol), - (flow->ip_version == 6) ? "[" : "", - flow->lower_name, - (flow->ip_version == 6) ? "]" : "", - ntohs(flow->lower_port), - (flow->ip_version == 6) ? "[" : "", - flow->upper_name, - (flow->ip_version == 6) ? "]" : "", - ntohs(flow->upper_port)); + fprintf(out, "\t%s ", ipProto2Name(flow->protocol)); + + if(flow->src_to_dst_direction == 1) + fprintf(out, "%s%s%s:%u <-> %s%s%s:%u ", + (flow->ip_version == 6) ? "[" : "", + flow->lower_name, (flow->ip_version == 6) ? "]" : "", ntohs(flow->lower_port), + (flow->ip_version == 6) ? "[" : "", + flow->upper_name, (flow->ip_version == 6) ? "]" : "", ntohs(flow->upper_port) + ); + else + fprintf(out, "%s%s%s:%u <-> %s%s%s:%u ", + (flow->ip_version == 6) ? "[" : "", + flow->upper_name, (flow->ip_version == 6) ? "]" : "", ntohs(flow->upper_port), + (flow->ip_version == 6) ? "[" : "", + flow->lower_name, (flow->ip_version == 6) ? "]" : "", ntohs(flow->lower_port) + ); if(flow->vlan_id > 0) fprintf(out, "[VLAN: %u]", flow->vlan_id); - + if(flow->detected_protocol.master_protocol) { char buf[64]; @@ -388,7 +645,7 @@ static void printFlow(u_int16_t thread_id, struct ndpi_flow_info *flow) { if(flow->host_server_name[0] != '\0') fprintf(out, "[Host: %s]", flow->host_server_name); if(flow->info[0] != '\0') fprintf(out, "[%s]", flow->info); - + if(flow->ssh_ssl.client_info[0] != '\0') fprintf(out, "[client: %s]", flow->ssh_ssl.client_info); if(flow->ssh_ssl.server_info[0] != '\0') fprintf(out, "[server: %s]", flow->ssh_ssl.server_info); if(flow->bittorent_hash[0] != '\0') fprintf(out, "[BT Hash: %s]", flow->bittorent_hash); @@ -502,7 +759,6 @@ static u_int16_t node_guess_undetected_protocol(u_int16_t thread_id, struct ndpi * @brief Proto Guess Walker */ static void node_proto_guess_walker(const void *node, ndpi_VISIT which, int depth, void *user_data) { - struct ndpi_flow_info *flow = *(struct ndpi_flow_info **) node; u_int16_t thread_id = *((u_int16_t *) user_data); @@ -524,6 +780,175 @@ static void node_proto_guess_walker(const void *node, ndpi_VISIT which, int dept } } +/* *********************************************** */ + +int updateIpTree(const u_int32_t key, addr_node **vrootp) { + addr_node *q; + addr_node **rootp = vrootp; + + if(rootp == (addr_node **)0) + return 0; + + while (*rootp != (addr_node *)0) { /* Knuth's T1: */ + if(key == ((*rootp)->addr)) { /* T2: */ + return ++((*rootp)->count); + } + + rootp = (key < ((*rootp)->addr)) ? + &(*rootp)->left : /* T3: follow left branch */ + &(*rootp)->right; /* T4: follow right branch */ + } + + q = (addr_node *) malloc(sizeof(addr_node)); /* T5: key not found */ + if(q != (addr_node *)0) { /* make new node */ + *rootp = q; /* link new node to old */ + q->addr = key; /* initialize new node */ + q->count = UPDATED_TREE; + q->left = q->right = (addr_node *)0; + return q->count; + } + + return(0); +} + +/* *********************************************** */ + +void freeIpTree(addr_node *root) { + while (root != NULL) { + addr_node *left = root->left; + + if(left == NULL) { + addr_node *right = root->right; + root->right = NULL; + root = right; + } else { + /* Rotate the left child up.*/ + root->left = left->right; + left->right = root; + root = left; + } + } +} + +/* *********************************************** */ + +void updateTopIpAddress(u_int32_t addr, int count, struct info_pair top[], int size){ + int update = 0; + int i; + int min_i = 0; + int min = count; + + if(count == 0) return; + + struct info_pair pair; + pair.addr = addr, pair.count = count; + + /* if the same ip with a bigger + count just update it */ + for(i=0; i<size; i++) { + if(top[i].addr == addr) { + top[i].count = count; + return; + } + } + + /* if array is not full yet + add it to the first empty place */ + for(i=0; i<size; i++) { + if(top[i].addr != addr && top[i].count == 0) { + top[i] = pair; + return; + } + } + + /* if bigger than the smallest one, replace it */ + for(i=0; i<size; i++) { + if(top[i].count < count && top[i].count < min){ + min = top[i].count; + min_i = i; + update = 1; + } + } + + if(update) + top[min_i] = pair; +} + +/* *********************************************** */ +static void updatePortStats(struct port_stats **stats, u_int32_t port, u_int32_t addr, u_int32_t num_pkts, u_int32_t num_bytes) { + struct port_stats *s; + char ipname[48]; + int count; + + HASH_FIND_INT(*stats, &port, s); + if(s == NULL) { + s = (struct port_stats*)malloc(sizeof(struct port_stats)); + if(!s) return; + + s->port = port, s->num_pkts = 0, s->num_bytes = 0; + s->num_addr = 1, s->cumulative_addr = 1; + + memset(s->top_ip_addrs, 0, MAX_NUM_IP_ADDRESS*sizeof(struct info_pair)); + updateTopIpAddress(addr, 1, s->top_ip_addrs, MAX_NUM_IP_ADDRESS); + + s->addr_tree = (addr_node *) malloc(sizeof(addr_node)); + if(!s->addr_tree) return; + + s->addr_tree->addr = addr; + s->addr_tree->count = 1; + s->addr_tree->left = NULL; + s->addr_tree->right = NULL; + + HASH_ADD_INT(*stats, port, s); + } + + count = updateIpTree(addr, &(*s).addr_tree); + if(count == UPDATED_TREE) s->num_addr++; + + if(count) { + s->cumulative_addr++; + updateTopIpAddress(addr, count, s->top_ip_addrs, MAX_NUM_IP_ADDRESS); + } + + s->num_pkts += num_pkts, s->num_bytes += num_bytes; +} + +/* *********************************************** */ + +static void deletePortsStats(struct port_stats *stats) { + struct port_stats *current_port, *tmp; + + HASH_ITER(hh, stats, current_port, tmp) { + HASH_DEL(stats, current_port); + freeIpTree(current_port->addr_tree); + free(current_port->addr_tree); + free(current_port); + } +} + +/* *********************************************** */ + +/** + * @brief Ports stats + */ +static void port_stats_walker(const void *node, ndpi_VISIT which, int depth, void *user_data) { + struct ndpi_flow_info *flow = *(struct ndpi_flow_info **) node; + u_int16_t sport, dport; + u_int32_t saddr, daddr; + + if(flow->src_to_dst_direction == 1) { + sport = ntohs(flow->lower_port), dport = ntohs(flow->upper_port); + saddr = flow->lower_ip, daddr = flow->upper_ip; + } + else { + sport = ntohs(flow->upper_port), dport = ntohs(flow->lower_port); + saddr = flow->upper_ip, daddr = flow->lower_ip; + } + updatePortStats(&srcStats, sport, saddr, flow->packets, flow->bytes); + updatePortStats(&dstStats, dport, daddr, flow->packets, flow->bytes); +} + +/* *********************************************** */ /** * @brief Idle Scan Walker @@ -659,7 +1084,6 @@ static void setupDetection(u_int16_t thread_id, pcap_t * pcap_handle) { * @brief End of detection and free flow */ static void terminateDetection(u_int16_t thread_id) { - ndpi_workflow_free(ndpi_thread_info[thread_id].workflow); } @@ -728,12 +1152,12 @@ static void json_init() { } #endif +/* *********************************************** */ /** * @brief Bytes stats format */ char* formatBytes(u_int32_t howMuch, char *buf, u_int buf_len) { - char unit = 'B'; if(howMuch < 1024) { @@ -755,12 +1179,60 @@ char* formatBytes(u_int32_t howMuch, char *buf, u_int buf_len) { return(buf); } +/* *********************************************** */ + +static int port_stats_sort(void *_a, void *_b) { + struct port_stats *a = (struct port_stats*)_a; + struct port_stats *b = (struct port_stats*)_b; + + return(b->num_pkts - a->num_pkts); +} + +/* *********************************************** */ + +static int info_pair_cmp (const void *_a, const void *_b) +{ + struct info_pair *a = (struct info_pair *)_a; + struct info_pair *b = (struct info_pair *)_b; + return b->count - a->count; +} + +/* *********************************************** */ + +void printPortStats(struct port_stats *stats) { + struct port_stats *s, *tmp; + char ip_name[48]; + int i = 0, j = 0, first = 1; + + HASH_ITER(hh, stats, s, tmp) { + i++; + printf("\t%2d\tPort %5u\t[%u IP address(es)/%u pkts/%u bytes]\n\t\tTop IP Stats:\n", + i, s->port, s->num_addr, s->num_pkts, s->num_bytes); + + qsort(&s->top_ip_addrs[0], MAX_NUM_IP_ADDRESS, sizeof(struct info_pair), info_pair_cmp); + + for(j=0; j<MAX_NUM_IP_ADDRESS; j++) { + if(s->top_ip_addrs[j].count != 0) { + inet_ntop(AF_INET, &s->top_ip_addrs[j].addr, ip_name, sizeof(ip_name)); + printf("\t\t%-16s ~ %.2f%%\n", + ip_name, ((s->top_ip_addrs[j].count) * 100.0) / s->cumulative_addr); + first = 0; + } + } + + printf("\n"); + first = 1; + + if(i >= 10) break; + } +} + +/* *********************************************** */ /** * @brief Print result */ static void printResults(u_int64_t tot_usec) { - u_int32_t i; u_int64_t total_flow_bytes = 0; u_int32_t avg_pkt_size = 0; @@ -780,8 +1252,15 @@ static void printResults(u_int64_t tot_usec) { && (ndpi_thread_info[thread_id].workflow->stats.raw_packet_count == 0)) continue; - for(i=0; i<NUM_ROOTS; i++) + for(i=0; i<NUM_ROOTS; i++) { ndpi_twalk(ndpi_thread_info[thread_id].workflow->ndpi_flows_root[i], node_proto_guess_walker, &thread_id); + if(verbose == 3) ndpi_twalk(ndpi_thread_info[thread_id].workflow->ndpi_flows_root[i], port_stats_walker, &thread_id); + } + + if(verbose == 3) { + HASH_SORT(srcStats, port_stats_sort); + HASH_SORT(dstStats, port_stats_sort); + } /* Stats aggregation */ cumulative_stats.guessed_flow_protocols += ndpi_thread_info[thread_id].workflow->stats.guessed_flow_protocols; @@ -809,6 +1288,8 @@ static void printResults(u_int64_t tot_usec) { cumulative_stats.max_packet_len += ndpi_thread_info[thread_id].workflow->stats.max_packet_len; } + if(cumulative_stats.total_wire_bytes == 0) return; + if(!quiet_mode) { printf("\nnDPI Memory statistics:\n"); printf("\tnDPI Memory (once): %-13s\n", formatBytes(sizeof(struct ndpi_detection_module_struct), buf, sizeof(buf))); @@ -847,15 +1328,20 @@ static void printResults(u_int64_t tot_usec) { printf("\tPacket Len > 1500: %-13lu\n", (unsigned long)cumulative_stats.packet_len[5]); if(tot_usec > 0) { - char buf[32], buf1[32]; + char buf[32], buf1[32], when[64]; float t = (float)(cumulative_stats.ip_packet_count*1000000)/(float)tot_usec; float b = (float)(cumulative_stats.total_wire_bytes * 8 *1000000)/(float)tot_usec; float traffic_duration; - if (live_capture) traffic_duration = tot_usec; + if(live_capture) traffic_duration = tot_usec; else traffic_duration = (pcap_end.tv_sec*1000000 + pcap_end.tv_usec) - (pcap_start.tv_sec*1000000 + pcap_start.tv_usec); printf("\tnDPI throughput: %s pps / %s/sec\n", formatPackets(t, buf), formatTraffic(b, 1, buf1)); t = (float)(cumulative_stats.ip_packet_count*1000000)/(float)traffic_duration; b = (float)(cumulative_stats.total_wire_bytes * 8 *1000000)/(float)traffic_duration; + + strftime(when, sizeof(when), "%d/%b/%Y %H:%M:%S", localtime(&pcap_start.tv_sec)); + printf("\tAnalysis begin: %s\n", when); + strftime(when, sizeof(when), "%d/%b/%Y %H:%M:%S", localtime(&pcap_end.tv_sec)); + printf("\tAnalysis end: %s\n", when); printf("\tTraffic throughput: %s pps / %s/sec\n", formatPackets(t, buf), formatTraffic(b, 1, buf1)); printf("\tTraffic duration: %.3f sec\n", traffic_duration/1000000); } @@ -957,7 +1443,7 @@ static void printResults(u_int64_t tot_usec) { // printf("\n\nTotal Flow Traffic: %llu (diff: %llu)\n", total_flow_bytes, cumulative_stats.total_ip_bytes-total_flow_bytes); - if(verbose) { + if((verbose == 1) || (verbose == 2)) { FILE *out = results_file ? results_file : stdout; if(!json_flag) fprintf(out, "\n"); @@ -1003,6 +1489,17 @@ static void printResults(u_int64_t tot_usec) { fclose(json_fp); #endif } + + if(verbose == 3) { + printf("\n\nSource Ports Stats:\n"); + printPortStats(srcStats); + + printf("\nDestination Ports Stats:\n"); + printPortStats(dstStats); + + deletePortsStats(srcStats), deletePortsStats(dstStats); + srcStats = NULL, dstStats = NULL; + } } @@ -1010,14 +1507,11 @@ static void printResults(u_int64_t tot_usec) { * @brief Force a pcap_dispatch() or pcap_loop() call to return */ static void breakPcapLoop(u_int16_t thread_id) { - if(ndpi_thread_info[thread_id].workflow->pcap_handle != NULL) { pcap_breakloop(ndpi_thread_info[thread_id].workflow->pcap_handle); } } - - /** * @brief Sigproc is executed for each packet in the pcap file */ @@ -1135,16 +1629,17 @@ static pcap_t * openPcapFileOrDevice(u_int16_t thread_id, const u_char * pcap_fi /** * @brief Check pcap packet */ -static void pcap_packet_callback_checked(u_char *args, - const struct pcap_pkthdr *header, - const u_char *packet) { - +static void pcap_process_packet(u_char *args, + const struct pcap_pkthdr *header, + const u_char *packet) { + struct ndpi_proto p; u_int16_t thread_id = *((u_int16_t*)args); /* allocate an exact size buffer to check overflows */ uint8_t *packet_checked = malloc(header->caplen); + memcpy(packet_checked, packet, header->caplen); - ndpi_workflow_process_packet(ndpi_thread_info[thread_id].workflow, header, packet_checked); + p = ndpi_workflow_process_packet(ndpi_thread_info[thread_id].workflow, header, packet_checked); if((capture_until != 0) && (header->ts.tv_sec >= capture_until)) { if(ndpi_thread_info[thread_id].workflow->pcap_handle != NULL) @@ -1153,8 +1648,8 @@ static void pcap_packet_callback_checked(u_char *args, } /* Check if capture is live or not */ - if (!live_capture) { - if (!pcap_start.tv_sec) pcap_start.tv_sec = header->ts.tv_sec, pcap_start.tv_usec = header->ts.tv_usec; + if(!live_capture) { + if(!pcap_start.tv_sec) pcap_start.tv_sec = header->ts.tv_sec, pcap_start.tv_usec = header->ts.tv_usec; pcap_end.tv_sec = header->ts.tv_sec, pcap_end.tv_usec = header->ts.tv_usec; } @@ -1182,11 +1677,73 @@ static void pcap_packet_callback_checked(u_char *args, } } +#ifdef DEBUG_TRACE + if(trace) fprintf(trace, "Found %u bytes packet %u.%u\n", header->caplen, p.app_protocol, p.master_protocol); +#endif + + if(extcap_dumper + && ((extcap_packet_filter == (u_int16_t)-1) + || (p.app_protocol == extcap_packet_filter) + || (p.master_protocol == extcap_packet_filter) + ) + ) { + struct pcap_pkthdr h; + uint32_t *crc, delta = sizeof(struct ndpi_packet_trailer) + 4 /* ethernet trailer */; + struct ndpi_packet_trailer *trailer; + + memcpy(&h, header, sizeof(h)); + + if(h.caplen > (sizeof(extcap_buf)-sizeof(struct ndpi_packet_trailer) - 4)) { + printf("INTERNAL ERROR: caplen=%u\n", h.caplen); + h.caplen = sizeof(extcap_buf)-sizeof(struct ndpi_packet_trailer) - 4; + } + + trailer = (struct ndpi_packet_trailer*)&extcap_buf[h.caplen]; + memcpy(extcap_buf, packet, h.caplen); + memset(trailer, 0, sizeof(struct ndpi_packet_trailer)); + trailer->magic = htonl(0x19680924); + trailer->master_protocol = htons(p.master_protocol), trailer->app_protocol = htons(p.app_protocol); + ndpi_protocol2name(ndpi_thread_info[thread_id].workflow->ndpi_struct, p, trailer->name, sizeof(trailer->name)); + crc = (uint32_t*)&extcap_buf[h.caplen+sizeof(struct ndpi_packet_trailer)]; + *crc = 0; + ethernet_crc32((const void*)extcap_buf, h.caplen+sizeof(struct ndpi_packet_trailer), crc); + h.caplen += delta, h.len += delta; + +#ifdef DEBUG_TRACE + if(trace) fprintf(trace, "Dumping %u bytes packet\n", h.caplen); +#endif + + pcap_dump((u_char*)extcap_dumper, &h, (const u_char *)extcap_buf); + pcap_dump_flush(extcap_dumper); + } + /* check for buffer changes */ if(memcmp(packet, packet_checked, header->caplen) != 0) - printf("INTERNAL ERROR: ingress packet was modified by nDPI: this should not happen [thread_id=%u, packetId=%lu]\n", - thread_id, (unsigned long)ndpi_thread_info[thread_id].workflow->stats.raw_packet_count); + printf("INTERNAL ERROR: ingress packet was modified by nDPI: this should not happen [thread_id=%u, packetId=%lu, caplen=%u]\n", + thread_id, (unsigned long)ndpi_thread_info[thread_id].workflow->stats.raw_packet_count, header->caplen); free(packet_checked); + + if((pcap_end.tv_sec-pcap_start.tv_sec) > pcap_analysis_duration) { + int i; + u_int64_t tot_usec; + + gettimeofday(&end, NULL); + tot_usec = end.tv_sec*1000000 + end.tv_usec - (begin.tv_sec*1000000 + begin.tv_usec); + + printResults(tot_usec); + + for(i=0; i<ndpi_thread_info[thread_id].workflow->prefs.num_roots; i++) { + ndpi_tdestroy(ndpi_thread_info[thread_id].workflow->ndpi_flows_root[i], ndpi_flow_info_freer); + ndpi_thread_info[thread_id].workflow->ndpi_flows_root[i] = NULL; + + memset(&ndpi_thread_info[thread_id].workflow->stats, 0, sizeof(struct ndpi_stats)); + } + + printf("\n-------------------------------------------\n\n"); + + memcpy(&begin, &end, sizeof(begin)); + memcpy(&pcap_start, &pcap_end, sizeof(pcap_start)); + } } @@ -1194,12 +1751,10 @@ static void pcap_packet_callback_checked(u_char *args, * @brief Call pcap_loop() to process packets from a live capture or savefile */ static void runPcapLoop(u_int16_t thread_id) { - if((!shutdown_app) && (ndpi_thread_info[thread_id].workflow->pcap_handle != NULL)) - pcap_loop(ndpi_thread_info[thread_id].workflow->pcap_handle, -1, &pcap_packet_callback_checked, (u_char*)&thread_id); + pcap_loop(ndpi_thread_info[thread_id].workflow->pcap_handle, -1, &pcap_process_packet, (u_char*)&thread_id); } - /** * @brief Process a running thread */ @@ -1224,7 +1779,7 @@ void * processing_thread(void *_thread_id) { if((!json_flag) && (!quiet_mode)) printf("Running thread %ld...\n", thread_id); pcap_loop: - runPcapLoop(thread_id); + runPcapLoop(thread_id); if(playlist_fp[thread_id] != NULL) { /* playlist: read next file */ char filename[256]; @@ -1244,8 +1799,7 @@ void * processing_thread(void *_thread_id) { * @brief Begin, process, end detection process */ void test_lib() { - - struct timeval begin, end; + struct timeval end; u_int64_t tot_usec; long thread_id; @@ -1253,20 +1807,48 @@ void test_lib() { json_init(); #endif +#ifdef DEBUG_TRACE + if(trace) fprintf(trace, "Num threads: %d\n", num_threads); +#endif + for(thread_id = 0; thread_id < num_threads; thread_id++) { - pcap_t * cap = openPcapFileOrDevice(thread_id, (const u_char*)_pcap_file[thread_id]); + pcap_t *cap; + +#ifdef DEBUG_TRACE + if(trace) fprintf(trace, "Opening %s\n", (const u_char*)_pcap_file[thread_id]); +#endif + + cap = openPcapFileOrDevice(thread_id, (const u_char*)_pcap_file[thread_id]); setupDetection(thread_id, cap); } gettimeofday(&begin, NULL); - /* Running processing threads */ - for(thread_id = 0; thread_id < num_threads; thread_id++) - pthread_create(&ndpi_thread_info[thread_id].pthread, NULL, processing_thread, (void *) thread_id); + int status; + void * thd_res; + /* Running processing threads */ + for(thread_id = 0; thread_id < num_threads; thread_id++) { + status = pthread_create(&ndpi_thread_info[thread_id].pthread, NULL, processing_thread, (void *) thread_id); + /* check pthreade_create return value */ + if(status != 0) { + fprintf(stderr, "error on create %ld thread\n", thread_id); + exit(-1); + } + } /* Waiting for completion */ - for(thread_id = 0; thread_id < num_threads; thread_id++) - pthread_join(ndpi_thread_info[thread_id].pthread, NULL); + for(thread_id = 0; thread_id < num_threads; thread_id++) { + status = pthread_join(ndpi_thread_info[thread_id].pthread, &thd_res); + /* check pthreade_join return value */ + if(status != 0) { + fprintf(stderr, "error on join %ld thread\n", thread_id); + exit(-1); + } + if(thd_res != NULL) { + fprintf(stderr, "error on returned value of %ld joined thread\n", thread_id); + exit(-1); + } + } gettimeofday(&end, NULL); tot_usec = end.tv_sec*1000000 + end.tv_usec - (begin.tv_sec*1000000 + begin.tv_usec); @@ -1275,9 +1857,9 @@ void test_lib() { printResults(tot_usec); for(thread_id = 0; thread_id < num_threads; thread_id++) { - if(ndpi_thread_info[thread_id].workflow->pcap_handle != NULL) { + if(ndpi_thread_info[thread_id].workflow->pcap_handle != NULL) pcap_close(ndpi_thread_info[thread_id].workflow->pcap_handle); - } + terminateDetection(thread_id); } } @@ -1304,8 +1886,6 @@ int main(int argc, char **argv) { automataUnitTest(); memset(ndpi_thread_info, 0, sizeof(ndpi_thread_info)); - memset(&pcap_start, 0, sizeof(pcap_start)); - memset(&pcap_end, 0, sizeof(pcap_end)); parseOptions(argc, argv); @@ -1325,8 +1905,9 @@ int main(int argc, char **argv) { for(i=0; i<num_loops; i++) test_lib(); - if(results_path) free(results_path); - if(results_file) fclose(results_file); + if(results_path) free(results_path); + if(results_file) fclose(results_file); + if(extcap_dumper) pcap_dump_close(extcap_dumper); return 0; } diff --git a/example/ndpi_util.c b/example/ndpi_util.c index 3ab6d8da4..1ba77eb80 100644 --- a/example/ndpi_util.c +++ b/example/ndpi_util.c @@ -48,6 +48,7 @@ #define MPLS_MULTI 0x8848 #define PPPoE 0x8864 #define SNAP 0xaa +#define BSTP 0x42 /* Bridge Spanning Tree Protocol */ /* mask for FCF */ #define WIFI_DATA 0x2 /* 0000 0010 */ @@ -62,6 +63,10 @@ #define GTP_U_V1_PORT 2152 #define TZSP_PORT 37008 +#ifndef DLT_LINUX_SLL +#define DLT_LINUX_SLL 113 +#endif + #include "ndpi_main.h" #include "ndpi_util.h" @@ -124,7 +129,7 @@ struct ndpi_workflow * ndpi_workflow_init(const struct ndpi_workflow_prefs * pre /* ***************************************************** */ -static void ndpi_flow_info_freer(void *node) { +void ndpi_flow_info_freer(void *node) { struct ndpi_flow_info *flow = (struct ndpi_flow_info*)node; ndpi_free_flow_info_half(flow); @@ -215,7 +220,7 @@ static struct ndpi_flow_info *get_ndpi_flow_info(struct ndpi_workflow * workflow return NULL; if((iph->ihl * 4) > ipsize || ipsize < ntohs(iph->tot_len) - || (iph->frag_off & htons(0x1FFF)) != 0) + /* || (iph->frag_off & htons(0x1FFF)) != 0 */) return NULL; l4_offset = iph->ihl * 4; @@ -255,9 +260,8 @@ static struct ndpi_flow_info *get_ndpi_flow_info(struct ndpi_workflow * workflow if(iph->protocol == IPPROTO_TCP && l4_packet_len >= 20) { u_int tcp_len; - workflow->stats.tcp_count++; - // tcp + workflow->stats.tcp_count++; *tcph = (struct ndpi_tcphdr *)l4; *sport = ntohs((*tcph)->source), *dport = ntohs((*tcph)->dest); @@ -284,8 +288,8 @@ static struct ndpi_flow_info *get_ndpi_flow_info(struct ndpi_workflow * workflow *payload_len = ndpi_max(0, l4_packet_len-4*(*tcph)->doff); } else if(iph->protocol == IPPROTO_UDP && l4_packet_len >= 8) { // udp - workflow->stats.udp_count++; + workflow->stats.udp_count++; *udph = (struct ndpi_udphdr *)l4; *sport = ntohs((*udph)->source), *dport = ntohs((*udph)->dest); *payload = &l4[sizeof(struct ndpi_udphdr)]; @@ -328,7 +332,9 @@ static struct ndpi_flow_info *get_ndpi_flow_info(struct ndpi_workflow * workflow if(ret == NULL) { if(workflow->stats.ndpi_flow_count == workflow->prefs.max_ndpi_flows) { - NDPI_LOG(0, workflow->ndpi_struct, NDPI_LOG_ERROR, "maximum flow count (%u) has been exceeded\n", workflow->prefs.max_ndpi_flows); + NDPI_LOG(0, workflow->ndpi_struct, NDPI_LOG_ERROR, + "maximum flow count (%u) has been exceeded\n", + workflow->prefs.max_ndpi_flows); exit(-1); } else { struct ndpi_flow_info *newflow = (struct ndpi_flow_info*)malloc(sizeof(struct ndpi_flow_info)); @@ -343,6 +349,7 @@ static struct ndpi_flow_info *get_ndpi_flow_info(struct ndpi_workflow * workflow newflow->lower_ip = lower_ip, newflow->upper_ip = upper_ip; newflow->lower_port = lower_port, newflow->upper_port = upper_port; newflow->ip_version = version; + newflow->src_to_dst_direction = *src_to_dst_direction; if(version == IPVERSION) { inet_ntop(AF_INET, &lower_ip, newflow->lower_name, sizeof(newflow->lower_name)); @@ -435,19 +442,19 @@ static struct ndpi_flow_info *get_ndpi_flow_info6(struct ndpi_workflow * workflo void process_ndpi_collected_info(struct ndpi_workflow * workflow, struct ndpi_flow_info *flow) { if(!flow->ndpi_flow) return; - - snprintf(flow->host_server_name, sizeof(flow->host_server_name), "%s", + + snprintf(flow->host_server_name, sizeof(flow->host_server_name), "%s", flow->ndpi_flow->host_server_name); /* BITTORRENT */ if(flow->detected_protocol.app_protocol == NDPI_PROTOCOL_BITTORRENT) { int i, j, n = 0; - + for(i=0, j = 0; j < sizeof(flow->bittorent_hash)-1; i++) { sprintf(&flow->bittorent_hash[j], "%02x", flow->ndpi_flow->bittorent_hash[i]); j += 2, n += flow->ndpi_flow->bittorent_hash[i]; } - + if(n == 0) flow->bittorent_hash[0] = '\0'; } /* MDNS */ @@ -498,13 +505,13 @@ void process_ndpi_collected_info(struct ndpi_workflow * workflow, struct ndpi_fl @Note: ipsize = header->len - ip_offset ; rawsize = header->len */ -static unsigned int packet_processing(struct ndpi_workflow * workflow, - const u_int64_t time, - u_int16_t vlan_id, - const struct ndpi_iphdr *iph, - struct ndpi_ipv6hdr *iph6, - u_int16_t ip_offset, - u_int16_t ipsize, u_int16_t rawsize) { +static struct ndpi_proto packet_processing(struct ndpi_workflow * workflow, + const u_int64_t time, + u_int16_t vlan_id, + const struct ndpi_iphdr *iph, + struct ndpi_ipv6hdr *iph6, + u_int16_t ip_offset, + u_int16_t ipsize, u_int16_t rawsize) { struct ndpi_id_struct *src, *dst; struct ndpi_flow_info *flow = NULL; struct ndpi_flow_struct *ndpi_flow = NULL; @@ -513,7 +520,8 @@ static unsigned int packet_processing(struct ndpi_workflow * workflow, struct ndpi_udphdr *udph = NULL; u_int16_t sport, dport, payload_len; u_int8_t *payload; - u_int8_t src_to_dst_direction= 1; + u_int8_t src_to_dst_direction = 1; + struct ndpi_proto nproto = { NDPI_PROTOCOL_UNKNOWN, NDPI_PROTOCOL_UNKNOWN }; if(iph) flow = get_ndpi_flow_info(workflow, IPVERSION, vlan_id, iph, NULL, @@ -535,12 +543,13 @@ static unsigned int packet_processing(struct ndpi_workflow * workflow, ndpi_flow = flow->ndpi_flow; flow->packets++, flow->bytes += rawsize; flow->last_seen = time; - } else { - return(0); + } else { // flow is NULL + workflow->stats.total_discarded_bytes++; + return(nproto); } /* Protocol already detected */ - if(flow->detection_completed) return(0); + if(flow->detection_completed) return(flow->detected_protocol); flow->detected_protocol = ndpi_detection_process_packet(workflow->ndpi_struct, ndpi_flow, iph ? (uint8_t *)iph : (uint8_t *)iph6, @@ -550,32 +559,29 @@ static unsigned int packet_processing(struct ndpi_workflow * workflow, || ((proto == IPPROTO_UDP) && (flow->packets > 8)) || ((proto == IPPROTO_TCP) && (flow->packets > 10))) { /* New protocol detected or give up */ - flow->detection_completed = 1; - } - if(flow->detection_completed) { if(flow->detected_protocol.app_protocol == NDPI_PROTOCOL_UNKNOWN) - flow->detected_protocol = ndpi_detection_giveup(workflow->ndpi_struct, - flow->ndpi_flow); - } + flow->detected_protocol = ndpi_detection_giveup(workflow->ndpi_struct, + flow->ndpi_flow); + process_ndpi_collected_info(workflow, flow); + } - process_ndpi_collected_info(workflow, flow); - return 0; + return(flow->detected_protocol); } /* ****************************************************** */ -void ndpi_workflow_process_packet (struct ndpi_workflow * workflow, - const struct pcap_pkthdr *header, - const u_char *packet) { +struct ndpi_proto ndpi_workflow_process_packet (struct ndpi_workflow * workflow, + const struct pcap_pkthdr *header, + const u_char *packet) { /* * Declare pointers to packet headers */ /* --- Ethernet header --- */ const struct ndpi_ethhdr *ethernet; /* --- LLC header --- */ - const struct ndpi_llc_header *llc; + const struct ndpi_llc_header_snap *llc; /* --- Cisco HDLC header --- */ const struct ndpi_chdlc *chdlc; @@ -593,6 +599,8 @@ void ndpi_workflow_process_packet (struct ndpi_workflow * workflow, /** --- IPv6 header --- **/ struct ndpi_ipv6hdr *iph6; + struct ndpi_proto nproto = { NDPI_PROTOCOL_UNKNOWN, NDPI_PROTOCOL_UNKNOWN }; + /* lengths and offsets */ u_int16_t eth_offset = 0; u_int16_t radio_len; @@ -629,7 +637,7 @@ void ndpi_workflow_process_packet (struct ndpi_workflow * workflow, datalink_check: switch(datalink_type) { - case DLT_NULL : + case DLT_NULL: if(ntohl(*((u_int32_t*)&packet[eth_offset])) == 2) type = ETH_P_IP; else @@ -653,7 +661,7 @@ void ndpi_workflow_process_packet (struct ndpi_workflow * workflow, break; /* IEEE 802.3 Ethernet - 1 */ - case DLT_EN10MB : + case DLT_EN10MB: ethernet = (struct ndpi_ethhdr *) &packet[eth_offset]; ip_offset = sizeof(struct ndpi_ethhdr) + eth_offset; check = ntohs(ethernet->h_proto); @@ -664,32 +672,34 @@ void ndpi_workflow_process_packet (struct ndpi_workflow * workflow, type = check; if(pyld_eth_len != 0) { + llc = (struct ndpi_llc_header_snap *)(&packet[ip_offset]); /* check for LLC layer with SNAP extension */ - if(packet[ip_offset] == SNAP) { - llc = (struct ndpi_llc_header *)(&packet[ip_offset]); + if(llc->dsap == SNAP || llc->ssap == SNAP) { type = llc->snap.proto_ID; ip_offset += + 8; } + /* No SNAP extension - Spanning Tree pkt must be discarted */ + else if(llc->dsap == BSTP || llc->ssap == BSTP) { + goto v4_warning; + } } break; /* Linux Cooked Capture - 113 */ -#ifdef __linux__ - case DLT_LINUX_SLL : + case DLT_LINUX_SLL: type = (packet[eth_offset+14] << 8) + packet[eth_offset+15]; ip_offset = 16 + eth_offset; break; -#endif /* Radiotap link-layer - 127 */ - case DLT_IEEE802_11_RADIO : + case DLT_IEEE802_11_RADIO: radiotap = (struct ndpi_radiotap_header *) &packet[eth_offset]; radio_len = radiotap->len; /* Check Bad FCS presence */ if((radiotap->flags & BAD_FCS) == BAD_FCS) { workflow->stats.total_discarded_bytes += header->len; - return; + return(nproto); } /* Calculate 802.11 header length (variable) */ @@ -705,12 +715,12 @@ void ndpi_workflow_process_packet (struct ndpi_workflow * workflow, break; /* Check ether_type from LLC */ - llc = (struct ndpi_llc_header*)(packet + eth_offset + wifi_len + radio_len); + llc = (struct ndpi_llc_header_snap*)(packet + eth_offset + wifi_len + radio_len); if(llc->dsap == SNAP) type = ntohs(llc->snap.proto_ID); /* Set IP header offset */ - ip_offset = wifi_len + radio_len + sizeof(struct ndpi_llc_header) + eth_offset; + ip_offset = wifi_len + radio_len + sizeof(struct ndpi_llc_header_snap) + eth_offset; break; case DLT_RAW: @@ -719,7 +729,7 @@ void ndpi_workflow_process_packet (struct ndpi_workflow * workflow, default: /* printf("Unknown datalink %d\n", datalink_type); */ - return; + return(nproto); } /* check ether type */ @@ -800,7 +810,7 @@ void ndpi_workflow_process_packet (struct ndpi_workflow * workflow, } workflow->stats.total_discarded_bytes += header->len; - return; + return(nproto); } } else if(iph->version == 6) { iph6 = (struct ndpi_ipv6hdr *)&packet[ip_offset]; @@ -825,7 +835,7 @@ void ndpi_workflow_process_packet (struct ndpi_workflow * workflow, ipv4_warning_used = 1; } workflow->stats.total_discarded_bytes += header->len; - return; + return(nproto); } if(workflow->prefs.decode_tunnels && (proto == IPPROTO_UDP)) { @@ -884,7 +894,7 @@ void ndpi_workflow_process_packet (struct ndpi_workflow * workflow, offset += tag_len; if(offset >= header->caplen) - return; /* Invalid packet */ + return(nproto); /* Invalid packet */ else { eth_offset = offset; goto datalink_check; @@ -895,6 +905,53 @@ void ndpi_workflow_process_packet (struct ndpi_workflow * workflow, } /* process the packet */ - packet_processing(workflow, time, vlan_id, iph, iph6, - ip_offset, header->len - ip_offset, header->len); + return(packet_processing(workflow, time, vlan_id, iph, iph6, + ip_offset, header->len - ip_offset, header->len)); +} + +/* ********************************************************** */ +/* http://home.thep.lu.se/~bjorn/crc/crc32_fast.c */ +/* ********************************************************** */ + +static uint32_t crc32_for_byte(uint32_t r) { + int j; + + for(j = 0; j < 8; ++j) + r = (r & 1? 0: (uint32_t)0xEDB88320L) ^ r >> 1; + return r ^ (uint32_t)0xFF000000L; +} + +/* Any unsigned integer type with at least 32 bits may be used as + * accumulator type for fast crc32-calulation, but unsigned long is + * probably the optimal choice for most systems. */ +typedef unsigned long accum_t; + +static void init_tables(uint32_t* table, uint32_t* wtable) { + size_t i, k, w, j; + + for(i = 0; i < 0x100; ++i) + table[i] = crc32_for_byte(i); + for(k = 0; k < sizeof(accum_t); ++k) + for(i = 0; i < 0x100; ++i) { + for(j = w = 0; j < sizeof(accum_t); ++j) + w = table[(uint8_t)(j == k? w ^ i: w)] ^ w >> 8; + wtable[(k << 8) + i] = w ^ (k? wtable[0]: 0); + } +} + +void ethernet_crc32(const void* data, size_t n_bytes, uint32_t* crc) { + static uint32_t table[0x100], wtable[0x100*sizeof(accum_t)]; + size_t n_accum = n_bytes/sizeof(accum_t); + size_t i, k, j; + + if(!*table) + init_tables(table, wtable); + for(i = 0; i < n_accum; ++i) { + accum_t a = *crc ^ ((accum_t*)data)[i]; + for(j = *crc = 0; j < sizeof(accum_t); ++j) + *crc ^= wtable[(j << 8) + (uint8_t)(a >> 8*j)]; + } + + for(i = n_accum*sizeof(accum_t); i < n_bytes; ++i) + *crc = table[(uint8_t)*crc ^ ((uint8_t*)data)[i]] ^ *crc >> 8; } diff --git a/example/ndpi_util.h b/example/ndpi_util.h index 1c092cbfa..ca9f20274 100644 --- a/example/ndpi_util.h +++ b/example/ndpi_util.h @@ -38,7 +38,8 @@ #define NUM_ROOTS 512 #define MAX_NDPI_FLOWS 200000000 #define TICK_RESOLUTION 1000 - +#define MAX_NUM_IP_ADDRESS 5 /* len of ip address array */ +#define UPDATED_TREE 1 // flow tracking typedef struct ndpi_flow_info { @@ -46,7 +47,7 @@ typedef struct ndpi_flow_info { u_int32_t upper_ip; u_int16_t lower_port; u_int16_t upper_port; - u_int8_t detection_completed, protocol; + u_int8_t detection_completed, protocol, src_to_dst_direction; u_int16_t vlan_id; struct ndpi_flow_struct *ndpi_flow; char lower_name[48], upper_name[48]; @@ -138,9 +139,9 @@ void ndpi_free_flow_info_half(struct ndpi_flow_info *flow); /* Process a packet and update the workflow */ -void ndpi_workflow_process_packet (struct ndpi_workflow * workflow, - const struct pcap_pkthdr *header, - const u_char *packet); +struct ndpi_proto ndpi_workflow_process_packet(struct ndpi_workflow * workflow, + const struct pcap_pkthdr *header, + const u_char *packet); /* flow callbacks for complete detected flow @@ -160,5 +161,6 @@ static inline void ndpi_workflow_set_flow_giveup_callback(struct ndpi_workflow * /* compare two nodes in workflow */ int ndpi_workflow_node_cmp(const void *a, const void *b); void process_ndpi_collected_info(struct ndpi_workflow * workflow, struct ndpi_flow_info *flow); - +void ethernet_crc32(const void* data, size_t n_bytes, uint32_t* crc); +void ndpi_flow_info_freer(void *node); #endif diff --git a/example/uthash.h b/example/uthash.h new file mode 100644 index 000000000..f78a73b86 --- /dev/null +++ b/example/uthash.h @@ -0,0 +1,1096 @@ +/* +Copyright (c) 2003-2017, Troy D. Hanson http://troydhanson.github.com/uthash/ +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef UTHASH_H +#define UTHASH_H + +#define UTHASH_VERSION 2.0.2 + +#include <string.h> /* memcmp,strlen */ +#include <stddef.h> /* ptrdiff_t */ +#include <stdlib.h> /* exit() */ + +/* These macros use decltype or the earlier __typeof GNU extension. + As decltype is only available in newer compilers (VS2010 or gcc 4.3+ + when compiling c++ source) this code uses whatever method is needed + or, for VS2008 where neither is available, uses casting workarounds. */ +#if !defined(DECLTYPE) && !defined(NO_DECLTYPE) +#if defined(_MSC_VER) /* MS compiler */ +#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ +#define DECLTYPE(x) (decltype(x)) +#else /* VS2008 or older (or VS2010 in C mode) */ +#define NO_DECLTYPE +#endif +#elif defined(__BORLANDC__) || defined(__ICCARM__) || defined(__LCC__) || defined(__WATCOMC__) +#define NO_DECLTYPE +#else /* GNU, Sun and other compilers */ +#define DECLTYPE(x) (__typeof(x)) +#endif +#endif + +#ifdef NO_DECLTYPE +#define DECLTYPE(x) +#define DECLTYPE_ASSIGN(dst,src) \ +do { \ + char **_da_dst = (char**)(&(dst)); \ + *_da_dst = (char*)(src); \ +} while (0) +#else +#define DECLTYPE_ASSIGN(dst,src) \ +do { \ + (dst) = DECLTYPE(dst)(src); \ +} while (0) +#endif + +/* a number of the hash function use uint32_t which isn't defined on Pre VS2010 */ +#if defined(_WIN32) +#if defined(_MSC_VER) && _MSC_VER >= 1600 +#include <stdint.h> +#elif defined(__WATCOMC__) || defined(__MINGW32__) || defined(__CYGWIN__) +#include <stdint.h> +#else +typedef unsigned int uint32_t; +typedef unsigned char uint8_t; +#endif +#elif defined(__GNUC__) && !defined(__VXWORKS__) +#include <stdint.h> +#else +typedef unsigned int uint32_t; +typedef unsigned char uint8_t; +#endif + +#ifndef uthash_fatal +#define uthash_fatal(msg) exit(-1) /* fatal error (out of memory,etc) */ +#endif +#ifndef uthash_malloc +#define uthash_malloc(sz) malloc(sz) /* malloc fcn */ +#endif +#ifndef uthash_free +#define uthash_free(ptr,sz) free(ptr) /* free fcn */ +#endif +#ifndef uthash_strlen +#define uthash_strlen(s) strlen(s) +#endif +#ifndef uthash_memcmp +#define uthash_memcmp(a,b,n) memcmp(a,b,n) +#endif + +#ifndef uthash_noexpand_fyi +#define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */ +#endif +#ifndef uthash_expand_fyi +#define uthash_expand_fyi(tbl) /* can be defined to log expands */ +#endif + +/* initial number of buckets */ +#define HASH_INITIAL_NUM_BUCKETS 32U /* initial number of buckets */ +#define HASH_INITIAL_NUM_BUCKETS_LOG2 5U /* lg2 of initial number of buckets */ +#define HASH_BKT_CAPACITY_THRESH 10U /* expand when bucket count reaches */ + +/* calculate the element whose hash handle address is hhp */ +#define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho))) +/* calculate the hash handle from element address elp */ +#define HH_FROM_ELMT(tbl,elp) ((UT_hash_handle *)(((char*)(elp)) + ((tbl)->hho))) + +#define HASH_VALUE(keyptr,keylen,hashv) \ +do { \ + HASH_FCN(keyptr, keylen, hashv); \ +} while (0) + +#define HASH_FIND_BYHASHVALUE(hh,head,keyptr,keylen,hashval,out) \ +do { \ + (out) = NULL; \ + if (head) { \ + unsigned _hf_bkt; \ + HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _hf_bkt); \ + if (HASH_BLOOM_TEST((head)->hh.tbl, hashval) != 0) { \ + HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], keyptr, keylen, hashval, out); \ + } \ + } \ +} while (0) + +#define HASH_FIND(hh,head,keyptr,keylen,out) \ +do { \ + unsigned _hf_hashv; \ + HASH_VALUE(keyptr, keylen, _hf_hashv); \ + HASH_FIND_BYHASHVALUE(hh, head, keyptr, keylen, _hf_hashv, out); \ +} while (0) + +#ifdef HASH_BLOOM +#define HASH_BLOOM_BITLEN (1UL << HASH_BLOOM) +#define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8UL) + (((HASH_BLOOM_BITLEN%8UL)!=0UL) ? 1UL : 0UL) +#define HASH_BLOOM_MAKE(tbl) \ +do { \ + (tbl)->bloom_nbits = HASH_BLOOM; \ + (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN); \ + if (!((tbl)->bloom_bv)) { uthash_fatal( "out of memory"); } \ + memset((tbl)->bloom_bv, 0, HASH_BLOOM_BYTELEN); \ + (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE; \ +} while (0) + +#define HASH_BLOOM_FREE(tbl) \ +do { \ + uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \ +} while (0) + +#define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8U] |= (1U << ((idx)%8U))) +#define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8U] & (1U << ((idx)%8U))) + +#define HASH_BLOOM_ADD(tbl,hashv) \ + HASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1U))) + +#define HASH_BLOOM_TEST(tbl,hashv) \ + HASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1U))) + +#else +#define HASH_BLOOM_MAKE(tbl) +#define HASH_BLOOM_FREE(tbl) +#define HASH_BLOOM_ADD(tbl,hashv) +#define HASH_BLOOM_TEST(tbl,hashv) (1) +#define HASH_BLOOM_BYTELEN 0U +#endif + +#define HASH_MAKE_TABLE(hh,head) \ +do { \ + (head)->hh.tbl = (UT_hash_table*)uthash_malloc( \ + sizeof(UT_hash_table)); \ + if (!((head)->hh.tbl)) { uthash_fatal( "out of memory"); } \ + memset((head)->hh.tbl, 0, sizeof(UT_hash_table)); \ + (head)->hh.tbl->tail = &((head)->hh); \ + (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \ + (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \ + (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \ + (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \ + HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ + if (! (head)->hh.tbl->buckets) { uthash_fatal( "out of memory"); } \ + memset((head)->hh.tbl->buckets, 0, \ + HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ + HASH_BLOOM_MAKE((head)->hh.tbl); \ + (head)->hh.tbl->signature = HASH_SIGNATURE; \ +} while (0) + +#define HASH_REPLACE_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,replaced,cmpfcn) \ +do { \ + (replaced) = NULL; \ + HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \ + if (replaced) { \ + HASH_DELETE(hh, head, replaced); \ + } \ + HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn); \ +} while (0) + +#define HASH_REPLACE_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add,replaced) \ +do { \ + (replaced) = NULL; \ + HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \ + if (replaced) { \ + HASH_DELETE(hh, head, replaced); \ + } \ + HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add); \ +} while (0) + +#define HASH_REPLACE(hh,head,fieldname,keylen_in,add,replaced) \ +do { \ + unsigned _hr_hashv; \ + HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv); \ + HASH_REPLACE_BYHASHVALUE(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced); \ +} while (0) + +#define HASH_REPLACE_INORDER(hh,head,fieldname,keylen_in,add,replaced,cmpfcn) \ +do { \ + unsigned _hr_hashv; \ + HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv); \ + HASH_REPLACE_BYHASHVALUE_INORDER(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced, cmpfcn); \ +} while (0) + +#define HASH_APPEND_LIST(hh, head, add) \ +do { \ + (add)->hh.next = NULL; \ + (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \ + (head)->hh.tbl->tail->next = (add); \ + (head)->hh.tbl->tail = &((add)->hh); \ +} while (0) + +#define HASH_AKBI_INNER_LOOP(hh,head,add,cmpfcn) \ +do { \ + do { \ + if (cmpfcn(DECLTYPE(head)(_hs_iter), add) > 0) \ + break; \ + } while ((_hs_iter = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->next)); \ +} while (0) + +#ifdef NO_DECLTYPE +#undef HASH_AKBI_INNER_LOOP +#define HASH_AKBI_INNER_LOOP(hh,head,add,cmpfcn) \ +do { \ + char *_hs_saved_head = (char*)(head); \ + do { \ + DECLTYPE_ASSIGN(head, _hs_iter); \ + if (cmpfcn(head, add) > 0) { \ + DECLTYPE_ASSIGN(head, _hs_saved_head); \ + break; \ + } \ + DECLTYPE_ASSIGN(head, _hs_saved_head); \ + } while ((_hs_iter = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->next)); \ +} while (0) +#endif + +#define HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh,head,keyptr,keylen_in,hashval,add,cmpfcn) \ +do { \ + unsigned _ha_bkt; \ + (add)->hh.hashv = (hashval); \ + (add)->hh.key = (char*) (keyptr); \ + (add)->hh.keylen = (unsigned) (keylen_in); \ + if (!(head)) { \ + (add)->hh.next = NULL; \ + (add)->hh.prev = NULL; \ + (head) = (add); \ + HASH_MAKE_TABLE(hh, head); \ + } else { \ + void *_hs_iter = (head); \ + (add)->hh.tbl = (head)->hh.tbl; \ + HASH_AKBI_INNER_LOOP(hh, head, add, cmpfcn); \ + if (_hs_iter) { \ + (add)->hh.next = _hs_iter; \ + if (((add)->hh.prev = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->prev)) { \ + HH_FROM_ELMT((head)->hh.tbl, (add)->hh.prev)->next = (add); \ + } else { \ + (head) = (add); \ + } \ + HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->prev = (add); \ + } else { \ + HASH_APPEND_LIST(hh, head, add); \ + } \ + } \ + (head)->hh.tbl->num_items++; \ + HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt); \ + HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], &(add)->hh); \ + HASH_BLOOM_ADD((head)->hh.tbl, hashval); \ + HASH_EMIT_KEY(hh, head, keyptr, keylen_in); \ + HASH_FSCK(hh, head); \ +} while (0) + +#define HASH_ADD_KEYPTR_INORDER(hh,head,keyptr,keylen_in,add,cmpfcn) \ +do { \ + unsigned _hs_hashv; \ + HASH_VALUE(keyptr, keylen_in, _hs_hashv); \ + HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, keyptr, keylen_in, _hs_hashv, add, cmpfcn); \ +} while (0) + +#define HASH_ADD_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,cmpfcn) \ + HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn) + +#define HASH_ADD_INORDER(hh,head,fieldname,keylen_in,add,cmpfcn) \ + HASH_ADD_KEYPTR_INORDER(hh, head, &((add)->fieldname), keylen_in, add, cmpfcn) + +#define HASH_ADD_KEYPTR_BYHASHVALUE(hh,head,keyptr,keylen_in,hashval,add) \ +do { \ + unsigned _ha_bkt; \ + (add)->hh.hashv = (hashval); \ + (add)->hh.key = (char*) (keyptr); \ + (add)->hh.keylen = (unsigned) (keylen_in); \ + if (!(head)) { \ + (add)->hh.next = NULL; \ + (add)->hh.prev = NULL; \ + (head) = (add); \ + HASH_MAKE_TABLE(hh, head); \ + } else { \ + (add)->hh.tbl = (head)->hh.tbl; \ + HASH_APPEND_LIST(hh, head, add); \ + } \ + (head)->hh.tbl->num_items++; \ + HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt); \ + HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], &(add)->hh); \ + HASH_BLOOM_ADD((head)->hh.tbl, hashval); \ + HASH_EMIT_KEY(hh, head, keyptr, keylen_in); \ + HASH_FSCK(hh, head); \ +} while (0) + +#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \ +do { \ + unsigned _ha_hashv; \ + HASH_VALUE(keyptr, keylen_in, _ha_hashv); \ + HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, keyptr, keylen_in, _ha_hashv, add); \ +} while (0) + +#define HASH_ADD_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add) \ + HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add) + +#define HASH_ADD(hh,head,fieldname,keylen_in,add) \ + HASH_ADD_KEYPTR(hh, head, &((add)->fieldname), keylen_in, add) + +#define HASH_TO_BKT(hashv,num_bkts,bkt) \ +do { \ + bkt = ((hashv) & ((num_bkts) - 1U)); \ +} while (0) + +/* delete "delptr" from the hash table. + * "the usual" patch-up process for the app-order doubly-linked-list. + * The use of _hd_hh_del below deserves special explanation. + * These used to be expressed using (delptr) but that led to a bug + * if someone used the same symbol for the head and deletee, like + * HASH_DELETE(hh,users,users); + * We want that to work, but by changing the head (users) below + * we were forfeiting our ability to further refer to the deletee (users) + * in the patch-up process. Solution: use scratch space to + * copy the deletee pointer, then the latter references are via that + * scratch pointer rather than through the repointed (users) symbol. + */ +#define HASH_DELETE(hh,head,delptr) \ +do { \ + struct UT_hash_handle *_hd_hh_del; \ + if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \ + uthash_free((head)->hh.tbl->buckets, \ + (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ + HASH_BLOOM_FREE((head)->hh.tbl); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + head = NULL; \ + } else { \ + unsigned _hd_bkt; \ + _hd_hh_del = &((delptr)->hh); \ + if ((delptr) == ELMT_FROM_HH((head)->hh.tbl,(head)->hh.tbl->tail)) { \ + (head)->hh.tbl->tail = \ + (UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \ + (head)->hh.tbl->hho); \ + } \ + if ((delptr)->hh.prev != NULL) { \ + ((UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \ + (head)->hh.tbl->hho))->next = (delptr)->hh.next; \ + } else { \ + DECLTYPE_ASSIGN(head,(delptr)->hh.next); \ + } \ + if (_hd_hh_del->next != NULL) { \ + ((UT_hash_handle*)((ptrdiff_t)_hd_hh_del->next + \ + (head)->hh.tbl->hho))->prev = \ + _hd_hh_del->prev; \ + } \ + HASH_TO_BKT( _hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \ + HASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \ + (head)->hh.tbl->num_items--; \ + } \ + HASH_FSCK(hh,head); \ +} while (0) + + +/* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */ +#define HASH_FIND_STR(head,findstr,out) \ + HASH_FIND(hh,head,findstr,(unsigned)uthash_strlen(findstr),out) +#define HASH_ADD_STR(head,strfield,add) \ + HASH_ADD(hh,head,strfield[0],(unsigned)uthash_strlen(add->strfield),add) +#define HASH_REPLACE_STR(head,strfield,add,replaced) \ + HASH_REPLACE(hh,head,strfield[0],(unsigned)uthash_strlen(add->strfield),add,replaced) +#define HASH_FIND_INT(head,findint,out) \ + HASH_FIND(hh,head,findint,sizeof(int),out) +#define HASH_ADD_INT(head,intfield,add) \ + HASH_ADD(hh,head,intfield,sizeof(int),add) +#define HASH_REPLACE_INT(head,intfield,add,replaced) \ + HASH_REPLACE(hh,head,intfield,sizeof(int),add,replaced) +#define HASH_FIND_PTR(head,findptr,out) \ + HASH_FIND(hh,head,findptr,sizeof(void *),out) +#define HASH_ADD_PTR(head,ptrfield,add) \ + HASH_ADD(hh,head,ptrfield,sizeof(void *),add) +#define HASH_REPLACE_PTR(head,ptrfield,add,replaced) \ + HASH_REPLACE(hh,head,ptrfield,sizeof(void *),add,replaced) +#define HASH_DEL(head,delptr) \ + HASH_DELETE(hh,head,delptr) + +/* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined. + * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined. + */ +#ifdef HASH_DEBUG +#define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0) +#define HASH_FSCK(hh,head) \ +do { \ + struct UT_hash_handle *_thh; \ + if (head) { \ + unsigned _bkt_i; \ + unsigned _count; \ + char *_prev; \ + _count = 0; \ + for( _bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; _bkt_i++) { \ + unsigned _bkt_count = 0; \ + _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \ + _prev = NULL; \ + while (_thh) { \ + if (_prev != (char*)(_thh->hh_prev)) { \ + HASH_OOPS("invalid hh_prev %p, actual %p\n", \ + _thh->hh_prev, _prev ); \ + } \ + _bkt_count++; \ + _prev = (char*)(_thh); \ + _thh = _thh->hh_next; \ + } \ + _count += _bkt_count; \ + if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \ + HASH_OOPS("invalid bucket count %u, actual %u\n", \ + (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \ + } \ + } \ + if (_count != (head)->hh.tbl->num_items) { \ + HASH_OOPS("invalid hh item count %u, actual %u\n", \ + (head)->hh.tbl->num_items, _count ); \ + } \ + /* traverse hh in app order; check next/prev integrity, count */ \ + _count = 0; \ + _prev = NULL; \ + _thh = &(head)->hh; \ + while (_thh) { \ + _count++; \ + if (_prev !=(char*)(_thh->prev)) { \ + HASH_OOPS("invalid prev %p, actual %p\n", \ + _thh->prev, _prev ); \ + } \ + _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \ + _thh = ( _thh->next ? (UT_hash_handle*)((char*)(_thh->next) + \ + (head)->hh.tbl->hho) : NULL ); \ + } \ + if (_count != (head)->hh.tbl->num_items) { \ + HASH_OOPS("invalid app item count %u, actual %u\n", \ + (head)->hh.tbl->num_items, _count ); \ + } \ + } \ +} while (0) +#else +#define HASH_FSCK(hh,head) +#endif + +/* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to + * the descriptor to which this macro is defined for tuning the hash function. + * The app can #include <unistd.h> to get the prototype for write(2). */ +#ifdef HASH_EMIT_KEYS +#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \ +do { \ + unsigned _klen = fieldlen; \ + write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \ + write(HASH_EMIT_KEYS, keyptr, (unsigned long)fieldlen); \ +} while (0) +#else +#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) +#endif + +/* default to Jenkin's hash unless overridden e.g. DHASH_FUNCTION=HASH_SAX */ +#ifdef HASH_FUNCTION +#define HASH_FCN HASH_FUNCTION +#else +#define HASH_FCN HASH_JEN +#endif + +/* The Bernstein hash function, used in Perl prior to v5.6. Note (x<<5+x)=x*33. */ +#define HASH_BER(key,keylen,hashv) \ +do { \ + unsigned _hb_keylen=(unsigned)keylen; \ + const unsigned char *_hb_key=(const unsigned char*)(key); \ + (hashv) = 0; \ + while (_hb_keylen-- != 0U) { \ + (hashv) = (((hashv) << 5) + (hashv)) + *_hb_key++; \ + } \ +} while (0) + + +/* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at + * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */ +#define HASH_SAX(key,keylen,hashv) \ +do { \ + unsigned _sx_i; \ + const unsigned char *_hs_key=(const unsigned char*)(key); \ + hashv = 0; \ + for(_sx_i=0; _sx_i < keylen; _sx_i++) { \ + hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \ + } \ +} while (0) +/* FNV-1a variation */ +#define HASH_FNV(key,keylen,hashv) \ +do { \ + unsigned _fn_i; \ + const unsigned char *_hf_key=(const unsigned char*)(key); \ + hashv = 2166136261U; \ + for(_fn_i=0; _fn_i < keylen; _fn_i++) { \ + hashv = hashv ^ _hf_key[_fn_i]; \ + hashv = hashv * 16777619U; \ + } \ +} while (0) + +#define HASH_OAT(key,keylen,hashv) \ +do { \ + unsigned _ho_i; \ + const unsigned char *_ho_key=(const unsigned char*)(key); \ + hashv = 0; \ + for(_ho_i=0; _ho_i < keylen; _ho_i++) { \ + hashv += _ho_key[_ho_i]; \ + hashv += (hashv << 10); \ + hashv ^= (hashv >> 6); \ + } \ + hashv += (hashv << 3); \ + hashv ^= (hashv >> 11); \ + hashv += (hashv << 15); \ +} while (0) + +#define HASH_JEN_MIX(a,b,c) \ +do { \ + a -= b; a -= c; a ^= ( c >> 13 ); \ + b -= c; b -= a; b ^= ( a << 8 ); \ + c -= a; c -= b; c ^= ( b >> 13 ); \ + a -= b; a -= c; a ^= ( c >> 12 ); \ + b -= c; b -= a; b ^= ( a << 16 ); \ + c -= a; c -= b; c ^= ( b >> 5 ); \ + a -= b; a -= c; a ^= ( c >> 3 ); \ + b -= c; b -= a; b ^= ( a << 10 ); \ + c -= a; c -= b; c ^= ( b >> 15 ); \ +} while (0) + +#define HASH_JEN(key,keylen,hashv) \ +do { \ + unsigned _hj_i,_hj_j,_hj_k; \ + unsigned const char *_hj_key=(unsigned const char*)(key); \ + hashv = 0xfeedbeefu; \ + _hj_i = _hj_j = 0x9e3779b9u; \ + _hj_k = (unsigned)(keylen); \ + while (_hj_k >= 12U) { \ + _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \ + + ( (unsigned)_hj_key[2] << 16 ) \ + + ( (unsigned)_hj_key[3] << 24 ) ); \ + _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \ + + ( (unsigned)_hj_key[6] << 16 ) \ + + ( (unsigned)_hj_key[7] << 24 ) ); \ + hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \ + + ( (unsigned)_hj_key[10] << 16 ) \ + + ( (unsigned)_hj_key[11] << 24 ) ); \ + \ + HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ + \ + _hj_key += 12; \ + _hj_k -= 12U; \ + } \ + hashv += (unsigned)(keylen); \ + switch ( _hj_k ) { \ + case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); /* FALLTHROUGH */ \ + case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); /* FALLTHROUGH */ \ + case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); /* FALLTHROUGH */ \ + case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); /* FALLTHROUGH */ \ + case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); /* FALLTHROUGH */ \ + case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); /* FALLTHROUGH */ \ + case 5: _hj_j += _hj_key[4]; /* FALLTHROUGH */ \ + case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); /* FALLTHROUGH */ \ + case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); /* FALLTHROUGH */ \ + case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); /* FALLTHROUGH */ \ + case 1: _hj_i += _hj_key[0]; \ + } \ + HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ +} while (0) + +/* The Paul Hsieh hash function */ +#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 +#define HASH_SFH(key,keylen,hashv) \ +do { \ + unsigned const char *_sfh_key=(unsigned const char*)(key); \ + uint32_t _sfh_tmp, _sfh_len = (uint32_t)keylen; \ + \ + unsigned _sfh_rem = _sfh_len & 3U; \ + _sfh_len >>= 2; \ + hashv = 0xcafebabeu; \ + \ + /* Main loop */ \ + for (;_sfh_len > 0U; _sfh_len--) { \ + hashv += get16bits (_sfh_key); \ + _sfh_tmp = ((uint32_t)(get16bits (_sfh_key+2)) << 11) ^ hashv; \ + hashv = (hashv << 16) ^ _sfh_tmp; \ + _sfh_key += 2U*sizeof (uint16_t); \ + hashv += hashv >> 11; \ + } \ + \ + /* Handle end cases */ \ + switch (_sfh_rem) { \ + case 3: hashv += get16bits (_sfh_key); \ + hashv ^= hashv << 16; \ + hashv ^= (uint32_t)(_sfh_key[sizeof (uint16_t)]) << 18; \ + hashv += hashv >> 11; \ + break; \ + case 2: hashv += get16bits (_sfh_key); \ + hashv ^= hashv << 11; \ + hashv += hashv >> 17; \ + break; \ + case 1: hashv += *_sfh_key; \ + hashv ^= hashv << 10; \ + hashv += hashv >> 1; \ + } \ + \ + /* Force "avalanching" of final 127 bits */ \ + hashv ^= hashv << 3; \ + hashv += hashv >> 5; \ + hashv ^= hashv << 4; \ + hashv += hashv >> 17; \ + hashv ^= hashv << 25; \ + hashv += hashv >> 6; \ +} while (0) + +#ifdef HASH_USING_NO_STRICT_ALIASING +/* The MurmurHash exploits some CPU's (x86,x86_64) tolerance for unaligned reads. + * For other types of CPU's (e.g. Sparc) an unaligned read causes a bus error. + * MurmurHash uses the faster approach only on CPU's where we know it's safe. + * + * Note the preprocessor built-in defines can be emitted using: + * + * gcc -m64 -dM -E - < /dev/null (on gcc) + * cc -## a.c (where a.c is a simple test file) (Sun Studio) + */ +#if (defined(__i386__) || defined(__x86_64__) || defined(_M_IX86)) +#define MUR_GETBLOCK(p,i) p[i] +#else /* non intel */ +#define MUR_PLUS0_ALIGNED(p) (((unsigned long)p & 3UL) == 0UL) +#define MUR_PLUS1_ALIGNED(p) (((unsigned long)p & 3UL) == 1UL) +#define MUR_PLUS2_ALIGNED(p) (((unsigned long)p & 3UL) == 2UL) +#define MUR_PLUS3_ALIGNED(p) (((unsigned long)p & 3UL) == 3UL) +#define WP(p) ((uint32_t*)((unsigned long)(p) & ~3UL)) +#if (defined(__BIG_ENDIAN__) || defined(SPARC) || defined(__ppc__) || defined(__ppc64__)) +#define MUR_THREE_ONE(p) ((((*WP(p))&0x00ffffff) << 8) | (((*(WP(p)+1))&0xff000000) >> 24)) +#define MUR_TWO_TWO(p) ((((*WP(p))&0x0000ffff) <<16) | (((*(WP(p)+1))&0xffff0000) >> 16)) +#define MUR_ONE_THREE(p) ((((*WP(p))&0x000000ff) <<24) | (((*(WP(p)+1))&0xffffff00) >> 8)) +#else /* assume little endian non-intel */ +#define MUR_THREE_ONE(p) ((((*WP(p))&0xffffff00) >> 8) | (((*(WP(p)+1))&0x000000ff) << 24)) +#define MUR_TWO_TWO(p) ((((*WP(p))&0xffff0000) >>16) | (((*(WP(p)+1))&0x0000ffff) << 16)) +#define MUR_ONE_THREE(p) ((((*WP(p))&0xff000000) >>24) | (((*(WP(p)+1))&0x00ffffff) << 8)) +#endif +#define MUR_GETBLOCK(p,i) (MUR_PLUS0_ALIGNED(p) ? ((p)[i]) : \ + (MUR_PLUS1_ALIGNED(p) ? MUR_THREE_ONE(p) : \ + (MUR_PLUS2_ALIGNED(p) ? MUR_TWO_TWO(p) : \ + MUR_ONE_THREE(p)))) +#endif +#define MUR_ROTL32(x,r) (((x) << (r)) | ((x) >> (32 - (r)))) +#define MUR_FMIX(_h) \ +do { \ + _h ^= _h >> 16; \ + _h *= 0x85ebca6bu; \ + _h ^= _h >> 13; \ + _h *= 0xc2b2ae35u; \ + _h ^= _h >> 16; \ +} while (0) + +#define HASH_MUR(key,keylen,hashv) \ +do { \ + const uint8_t *_mur_data = (const uint8_t*)(key); \ + const int _mur_nblocks = (int)(keylen) / 4; \ + uint32_t _mur_h1 = 0xf88D5353u; \ + uint32_t _mur_c1 = 0xcc9e2d51u; \ + uint32_t _mur_c2 = 0x1b873593u; \ + uint32_t _mur_k1 = 0; \ + const uint8_t *_mur_tail; \ + const uint32_t *_mur_blocks = (const uint32_t*)(_mur_data+(_mur_nblocks*4)); \ + int _mur_i; \ + for(_mur_i = -_mur_nblocks; _mur_i!=0; _mur_i++) { \ + _mur_k1 = MUR_GETBLOCK(_mur_blocks,_mur_i); \ + _mur_k1 *= _mur_c1; \ + _mur_k1 = MUR_ROTL32(_mur_k1,15); \ + _mur_k1 *= _mur_c2; \ + \ + _mur_h1 ^= _mur_k1; \ + _mur_h1 = MUR_ROTL32(_mur_h1,13); \ + _mur_h1 = (_mur_h1*5U) + 0xe6546b64u; \ + } \ + _mur_tail = (const uint8_t*)(_mur_data + (_mur_nblocks*4)); \ + _mur_k1=0; \ + switch((keylen) & 3U) { \ + case 3: _mur_k1 ^= (uint32_t)_mur_tail[2] << 16; /* FALLTHROUGH */ \ + case 2: _mur_k1 ^= (uint32_t)_mur_tail[1] << 8; /* FALLTHROUGH */ \ + case 1: _mur_k1 ^= (uint32_t)_mur_tail[0]; \ + _mur_k1 *= _mur_c1; \ + _mur_k1 = MUR_ROTL32(_mur_k1,15); \ + _mur_k1 *= _mur_c2; \ + _mur_h1 ^= _mur_k1; \ + } \ + _mur_h1 ^= (uint32_t)(keylen); \ + MUR_FMIX(_mur_h1); \ + hashv = _mur_h1; \ +} while (0) +#endif /* HASH_USING_NO_STRICT_ALIASING */ + +/* iterate over items in a known bucket to find desired item */ +#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,hashval,out) \ +do { \ + if ((head).hh_head != NULL) { \ + DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (head).hh_head)); \ + } else { \ + (out) = NULL; \ + } \ + while ((out) != NULL) { \ + if ((out)->hh.hashv == (hashval) && (out)->hh.keylen == (keylen_in)) { \ + if (uthash_memcmp((out)->hh.key, keyptr, keylen_in) == 0) { \ + break; \ + } \ + } \ + if ((out)->hh.hh_next != NULL) { \ + DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (out)->hh.hh_next)); \ + } else { \ + (out) = NULL; \ + } \ + } \ +} while (0) + +/* add an item to a bucket */ +#define HASH_ADD_TO_BKT(head,addhh) \ +do { \ + head.count++; \ + (addhh)->hh_next = head.hh_head; \ + (addhh)->hh_prev = NULL; \ + if (head.hh_head != NULL) { (head).hh_head->hh_prev = (addhh); } \ + (head).hh_head=addhh; \ + if ((head.count >= ((head.expand_mult+1U) * HASH_BKT_CAPACITY_THRESH)) \ + && ((addhh)->tbl->noexpand != 1U)) { \ + HASH_EXPAND_BUCKETS((addhh)->tbl); \ + } \ +} while (0) + +/* remove an item from a given bucket */ +#define HASH_DEL_IN_BKT(hh,head,hh_del) \ + (head).count--; \ + if ((head).hh_head == hh_del) { \ + (head).hh_head = hh_del->hh_next; \ + } \ + if (hh_del->hh_prev) { \ + hh_del->hh_prev->hh_next = hh_del->hh_next; \ + } \ + if (hh_del->hh_next) { \ + hh_del->hh_next->hh_prev = hh_del->hh_prev; \ + } + +/* Bucket expansion has the effect of doubling the number of buckets + * and redistributing the items into the new buckets. Ideally the + * items will distribute more or less evenly into the new buckets + * (the extent to which this is true is a measure of the quality of + * the hash function as it applies to the key domain). + * + * With the items distributed into more buckets, the chain length + * (item count) in each bucket is reduced. Thus by expanding buckets + * the hash keeps a bound on the chain length. This bounded chain + * length is the essence of how a hash provides constant time lookup. + * + * The calculation of tbl->ideal_chain_maxlen below deserves some + * explanation. First, keep in mind that we're calculating the ideal + * maximum chain length based on the *new* (doubled) bucket count. + * In fractions this is just n/b (n=number of items,b=new num buckets). + * Since the ideal chain length is an integer, we want to calculate + * ceil(n/b). We don't depend on floating point arithmetic in this + * hash, so to calculate ceil(n/b) with integers we could write + * + * ceil(n/b) = (n/b) + ((n%b)?1:0) + * + * and in fact a previous version of this hash did just that. + * But now we have improved things a bit by recognizing that b is + * always a power of two. We keep its base 2 log handy (call it lb), + * so now we can write this with a bit shift and logical AND: + * + * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0) + * + */ +#define HASH_EXPAND_BUCKETS(tbl) \ +do { \ + unsigned _he_bkt; \ + unsigned _he_bkt_i; \ + struct UT_hash_handle *_he_thh, *_he_hh_nxt; \ + UT_hash_bucket *_he_new_buckets, *_he_newbkt; \ + _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \ + 2UL * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ + if (!_he_new_buckets) { uthash_fatal( "out of memory"); } \ + memset(_he_new_buckets, 0, \ + 2UL * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ + tbl->ideal_chain_maxlen = \ + (tbl->num_items >> (tbl->log2_num_buckets+1U)) + \ + (((tbl->num_items & ((tbl->num_buckets*2U)-1U)) != 0U) ? 1U : 0U); \ + tbl->nonideal_items = 0; \ + for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++) \ + { \ + _he_thh = tbl->buckets[ _he_bkt_i ].hh_head; \ + while (_he_thh != NULL) { \ + _he_hh_nxt = _he_thh->hh_next; \ + HASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2U, _he_bkt); \ + _he_newbkt = &(_he_new_buckets[ _he_bkt ]); \ + if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) { \ + tbl->nonideal_items++; \ + _he_newbkt->expand_mult = _he_newbkt->count / \ + tbl->ideal_chain_maxlen; \ + } \ + _he_thh->hh_prev = NULL; \ + _he_thh->hh_next = _he_newbkt->hh_head; \ + if (_he_newbkt->hh_head != NULL) { _he_newbkt->hh_head->hh_prev = \ + _he_thh; } \ + _he_newbkt->hh_head = _he_thh; \ + _he_thh = _he_hh_nxt; \ + } \ + } \ + uthash_free( tbl->buckets, tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ + tbl->num_buckets *= 2U; \ + tbl->log2_num_buckets++; \ + tbl->buckets = _he_new_buckets; \ + tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ? \ + (tbl->ineff_expands+1U) : 0U; \ + if (tbl->ineff_expands > 1U) { \ + tbl->noexpand=1; \ + uthash_noexpand_fyi(tbl); \ + } \ + uthash_expand_fyi(tbl); \ +} while (0) + + +/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */ +/* Note that HASH_SORT assumes the hash handle name to be hh. + * HASH_SRT was added to allow the hash handle name to be passed in. */ +#define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn) +#define HASH_SRT(hh,head,cmpfcn) \ +do { \ + unsigned _hs_i; \ + unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \ + struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \ + if (head != NULL) { \ + _hs_insize = 1; \ + _hs_looping = 1; \ + _hs_list = &((head)->hh); \ + while (_hs_looping != 0U) { \ + _hs_p = _hs_list; \ + _hs_list = NULL; \ + _hs_tail = NULL; \ + _hs_nmerges = 0; \ + while (_hs_p != NULL) { \ + _hs_nmerges++; \ + _hs_q = _hs_p; \ + _hs_psize = 0; \ + for ( _hs_i = 0; _hs_i < _hs_insize; _hs_i++ ) { \ + _hs_psize++; \ + _hs_q = (UT_hash_handle*)((_hs_q->next != NULL) ? \ + ((void*)((char*)(_hs_q->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + if (! (_hs_q) ) { break; } \ + } \ + _hs_qsize = _hs_insize; \ + while ((_hs_psize > 0U) || ((_hs_qsize > 0U) && (_hs_q != NULL))) {\ + if (_hs_psize == 0U) { \ + _hs_e = _hs_q; \ + _hs_q = (UT_hash_handle*)((_hs_q->next != NULL) ? \ + ((void*)((char*)(_hs_q->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + _hs_qsize--; \ + } else if ( (_hs_qsize == 0U) || (_hs_q == NULL) ) { \ + _hs_e = _hs_p; \ + if (_hs_p != NULL){ \ + _hs_p = (UT_hash_handle*)((_hs_p->next != NULL) ? \ + ((void*)((char*)(_hs_p->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + } \ + _hs_psize--; \ + } else if (( \ + cmpfcn(DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_p)), \ + DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_q))) \ + ) <= 0) { \ + _hs_e = _hs_p; \ + if (_hs_p != NULL){ \ + _hs_p = (UT_hash_handle*)((_hs_p->next != NULL) ? \ + ((void*)((char*)(_hs_p->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + } \ + _hs_psize--; \ + } else { \ + _hs_e = _hs_q; \ + _hs_q = (UT_hash_handle*)((_hs_q->next != NULL) ? \ + ((void*)((char*)(_hs_q->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + _hs_qsize--; \ + } \ + if ( _hs_tail != NULL ) { \ + _hs_tail->next = ((_hs_e != NULL) ? \ + ELMT_FROM_HH((head)->hh.tbl,_hs_e) : NULL); \ + } else { \ + _hs_list = _hs_e; \ + } \ + if (_hs_e != NULL) { \ + _hs_e->prev = ((_hs_tail != NULL) ? \ + ELMT_FROM_HH((head)->hh.tbl,_hs_tail) : NULL); \ + } \ + _hs_tail = _hs_e; \ + } \ + _hs_p = _hs_q; \ + } \ + if (_hs_tail != NULL){ \ + _hs_tail->next = NULL; \ + } \ + if ( _hs_nmerges <= 1U ) { \ + _hs_looping=0; \ + (head)->hh.tbl->tail = _hs_tail; \ + DECLTYPE_ASSIGN(head,ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \ + } \ + _hs_insize *= 2U; \ + } \ + HASH_FSCK(hh,head); \ + } \ +} while (0) + +/* This function selects items from one hash into another hash. + * The end result is that the selected items have dual presence + * in both hashes. There is no copy of the items made; rather + * they are added into the new hash through a secondary hash + * hash handle that must be present in the structure. */ +#define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \ +do { \ + unsigned _src_bkt, _dst_bkt; \ + void *_last_elt=NULL, *_elt; \ + UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \ + ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \ + if (src != NULL) { \ + for(_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \ + for(_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \ + _src_hh != NULL; \ + _src_hh = _src_hh->hh_next) { \ + _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \ + if (cond(_elt)) { \ + _dst_hh = (UT_hash_handle*)(((char*)_elt) + _dst_hho); \ + _dst_hh->key = _src_hh->key; \ + _dst_hh->keylen = _src_hh->keylen; \ + _dst_hh->hashv = _src_hh->hashv; \ + _dst_hh->prev = _last_elt; \ + _dst_hh->next = NULL; \ + if (_last_elt_hh != NULL) { _last_elt_hh->next = _elt; } \ + if (dst == NULL) { \ + DECLTYPE_ASSIGN(dst,_elt); \ + HASH_MAKE_TABLE(hh_dst,dst); \ + } else { \ + _dst_hh->tbl = (dst)->hh_dst.tbl; \ + } \ + HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \ + HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt],_dst_hh); \ + (dst)->hh_dst.tbl->num_items++; \ + _last_elt = _elt; \ + _last_elt_hh = _dst_hh; \ + } \ + } \ + } \ + } \ + HASH_FSCK(hh_dst,dst); \ +} while (0) + +#define HASH_CLEAR(hh,head) \ +do { \ + if (head != NULL) { \ + uthash_free((head)->hh.tbl->buckets, \ + (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \ + HASH_BLOOM_FREE((head)->hh.tbl); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + (head)=NULL; \ + } \ +} while (0) + +#define HASH_OVERHEAD(hh,head) \ + ((head != NULL) ? ( \ + (size_t)(((head)->hh.tbl->num_items * sizeof(UT_hash_handle)) + \ + ((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket)) + \ + sizeof(UT_hash_table) + \ + (HASH_BLOOM_BYTELEN))) : 0U) + +#ifdef NO_DECLTYPE +#define HASH_ITER(hh,head,el,tmp) \ +for(((el)=(head)), ((*(char**)(&(tmp)))=(char*)((head!=NULL)?(head)->hh.next:NULL)); \ + (el) != NULL; ((el)=(tmp)), ((*(char**)(&(tmp)))=(char*)((tmp!=NULL)?(tmp)->hh.next:NULL))) +#else +#define HASH_ITER(hh,head,el,tmp) \ +for(((el)=(head)), ((tmp)=DECLTYPE(el)((head!=NULL)?(head)->hh.next:NULL)); \ + (el) != NULL; ((el)=(tmp)), ((tmp)=DECLTYPE(el)((tmp!=NULL)?(tmp)->hh.next:NULL))) +#endif + +/* obtain a count of items in the hash */ +#define HASH_COUNT(head) HASH_CNT(hh,head) +#define HASH_CNT(hh,head) ((head != NULL)?((head)->hh.tbl->num_items):0U) + +typedef struct UT_hash_bucket { + struct UT_hash_handle *hh_head; + unsigned count; + + /* expand_mult is normally set to 0. In this situation, the max chain length + * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If + * the bucket's chain exceeds this length, bucket expansion is triggered). + * However, setting expand_mult to a non-zero value delays bucket expansion + * (that would be triggered by additions to this particular bucket) + * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH. + * (The multiplier is simply expand_mult+1). The whole idea of this + * multiplier is to reduce bucket expansions, since they are expensive, in + * situations where we know that a particular bucket tends to be overused. + * It is better to let its chain length grow to a longer yet-still-bounded + * value, than to do an O(n) bucket expansion too often. + */ + unsigned expand_mult; + +} UT_hash_bucket; + +/* random signature used only to find hash tables in external analysis */ +#define HASH_SIGNATURE 0xa0111fe1u +#define HASH_BLOOM_SIGNATURE 0xb12220f2u + +typedef struct UT_hash_table { + UT_hash_bucket *buckets; + unsigned num_buckets, log2_num_buckets; + unsigned num_items; + struct UT_hash_handle *tail; /* tail hh in app order, for fast append */ + ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */ + + /* in an ideal situation (all buckets used equally), no bucket would have + * more than ceil(#items/#buckets) items. that's the ideal chain length. */ + unsigned ideal_chain_maxlen; + + /* nonideal_items is the number of items in the hash whose chain position + * exceeds the ideal chain maxlen. these items pay the penalty for an uneven + * hash distribution; reaching them in a chain traversal takes >ideal steps */ + unsigned nonideal_items; + + /* ineffective expands occur when a bucket doubling was performed, but + * afterward, more than half the items in the hash had nonideal chain + * positions. If this happens on two consecutive expansions we inhibit any + * further expansion, as it's not helping; this happens when the hash + * function isn't a good fit for the key domain. When expansion is inhibited + * the hash will still work, albeit no longer in constant time. */ + unsigned ineff_expands, noexpand; + + uint32_t signature; /* used only to find hash tables in external analysis */ +#ifdef HASH_BLOOM + uint32_t bloom_sig; /* used only to test bloom exists in external analysis */ + uint8_t *bloom_bv; + uint8_t bloom_nbits; +#endif + +} UT_hash_table; + +typedef struct UT_hash_handle { + struct UT_hash_table *tbl; + void *prev; /* prev element in app order */ + void *next; /* next element in app order */ + struct UT_hash_handle *hh_prev; /* previous hh in bucket order */ + struct UT_hash_handle *hh_next; /* next hh in bucket order */ + void *key; /* ptr to enclosing struct's key */ + unsigned keylen; /* enclosing struct's key len */ + unsigned hashv; /* result of hash-fcn(key) */ +} UT_hash_handle; + +#endif /* UTHASH_H */ |