fuzz_set_alloc_callbacks: 31| 1.05k|{ 32| 1.05k| ndpi_set_memory_alloction_functions(malloc_wrapper, 33| 1.05k| free_wrapper, 34| 1.05k| calloc_wrapper, 35| 1.05k| realloc_wrapper, 36| | /* Aligned allocations are used only by croaring, 37| | but no during fuzzing. So no point to set 38| | these two wrappers here */ 39| 1.05k| NULL, NULL, 40| 1.05k| malloc_wrapper, 41| 1.05k| free_wrapper); 42| 1.05k|} fuzz_set_alloc_seed: 44| 1.05k|{ 45| 1.05k| mem_alloc_state = seed; 46| 1.05k|} fuzz_set_alloc_callbacks_and_seed: 48| 1.05k|{ 49| 1.05k| fuzz_set_alloc_callbacks(); 50| 1.05k| fuzz_set_alloc_seed(seed); 51| 1.05k|} fuzz_common_code.c:malloc_wrapper: 17| 1.05k|static void *malloc_wrapper(size_t size) { 18| 1.05k| return (fastrand () % 16) ? malloc (size) : NULL; ------------------ | Branch (18:10): [True: 1.03k, False: 18] ------------------ 19| 1.05k|} fuzz_common_code.c:fastrand: 11| 75.0k|{ 12| 75.0k| if(!mem_alloc_state) return 1; /* No failures */ ------------------ | Branch (12:6): [True: 0, False: 75.0k] ------------------ 13| 75.0k| mem_alloc_state = (214013 * mem_alloc_state + 2531011); 14| 75.0k| return (mem_alloc_state >> 16) & 0x7FFF; 15| 75.0k|} fuzz_common_code.c:free_wrapper: 20| 70.2k|static void free_wrapper(void *freeable) { 21| 70.2k| free(freeable); 22| 70.2k|} fuzz_common_code.c:calloc_wrapper: 23| 73.9k|static void *calloc_wrapper(size_t nmemb, size_t size) { 24| 73.9k| return (fastrand () % 16) ? calloc (nmemb, size) : NULL; ------------------ | Branch (24:10): [True: 69.1k, False: 4.77k] ------------------ 25| 73.9k|} LLVMFuzzerTestOneInput: 10| 1.05k|extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { 11| 1.05k| FuzzedDataProvider fuzzed_data(data, size); 12| 1.05k| u_int16_t i, num_iteration; 13| 1.05k| ndpi_ptree_t *t; 14| 1.05k| ndpi_ip_addr_t addr, addr2, addr_added; 15| 1.05k| u_int8_t bits; 16| 1.05k| int rc, is_added = 0; 17| 1.05k| u_int64_t user_data; 18| 1.05k| char buf_ip[256]; 19| | 20| | /* To allow memory allocation failures */ 21| 1.05k| fuzz_set_alloc_callbacks_and_seed(size); 22| | 23| 1.05k| t = ndpi_ptree_create(); 24| | 25| | /* Random insert */ 26| 1.05k| num_iteration = fuzzed_data.ConsumeIntegral(); 27| 135k| for (i = 0; i < num_iteration; i++) { ------------------ | Branch (27:15): [True: 134k, False: 1.05k] ------------------ 28| 134k| if (fuzzed_data.ConsumeBool()) { ------------------ | Branch (28:9): [True: 12.6k, False: 121k] ------------------ 29| 12.6k| if(fuzzed_data.remaining_bytes() > 16) { ------------------ | Branch (29:10): [True: 12.1k, False: 498] ------------------ 30| 12.1k| memcpy(&addr.ipv6, fuzzed_data.ConsumeBytes(16).data(), 16); 31| 12.1k| bits = fuzzed_data.ConsumeIntegralInRange(0, 128); 32| 12.1k| } else { 33| 498| continue; 34| 498| } 35| 121k| } else { 36| 121k| memset(&addr, '\0', sizeof(addr)); 37| 121k| addr.ipv4 = fuzzed_data.ConsumeIntegral(); 38| 121k| bits = fuzzed_data.ConsumeIntegralInRange(0, 32); 39| 133k| }; 40| | 41| | /* Not really ptree stuff, but this seem the right place to fuzz these `ndpi_ip_addr_t` functions */ 42| 133k| ndpi_parse_ip_string(ndpi_get_ip_string(&addr, buf_ip, sizeof(buf_ip)), &addr2); 43| | 44| 133k| rc = ndpi_ptree_insert(t, &addr, bits, 0); 45| | /* Keep one random node really added */ 46| 133k| if (rc == 0 && is_added == 0 && fuzzed_data.ConsumeBool()) { ------------------ | Branch (46:9): [True: 18.5k, False: 115k] | Branch (46:20): [True: 1.41k, False: 17.1k] | Branch (46:37): [True: 595, False: 816] ------------------ 47| 595| is_added = 1; 48| 595| addr_added = addr; 49| 595| } 50| 133k| } 51| | 52| | /* Some higher level functions */ 53| 1.05k| ndpi_load_ptree_file(t, "ipv4_addresses.txt", NDPI_PROTOCOL_TLS); 54| 1.05k| ndpi_load_ptree_file(t, "invalid_filename", NDPI_PROTOCOL_TLS); 55| 1.05k| ndpi_load_ptree_file(t, "ipv6_addresses.txt", NDPI_PROTOCOL_TLS); 56| | 57| | /* Random search */ 58| 1.05k| num_iteration = fuzzed_data.ConsumeIntegral(); 59| 34.3k| for (i = 0; i < num_iteration; i++) { ------------------ | Branch (59:15): [True: 33.3k, False: 1.05k] ------------------ 60| 33.3k| if (fuzzed_data.ConsumeBool()) { ------------------ | Branch (60:9): [True: 8.51k, False: 24.7k] ------------------ 61| 8.51k| if(fuzzed_data.remaining_bytes() > 16) { ------------------ | Branch (61:10): [True: 8.25k, False: 257] ------------------ 62| 8.25k| memcpy(&addr.ipv6, fuzzed_data.ConsumeBytes(16).data(), 16); 63| 8.25k| } else { 64| 257| continue; 65| 257| } 66| 24.7k| } else { 67| 24.7k| memset(&addr, '\0', sizeof(addr)); 68| 24.7k| addr.ipv4 = fuzzed_data.ConsumeIntegral(); 69| 33.0k| }; 70| | 71| 33.0k| ndpi_ptree_match_addr(t, &addr, &user_data); 72| 33.0k| } 73| | /* Search of an added node */ 74| 1.05k| if (is_added) ------------------ | Branch (74:7): [True: 595, False: 459] ------------------ 75| 595| ndpi_ptree_match_addr(t, &addr_added, &user_data); 76| | 77| 1.05k| ndpi_ptree_destroy(t); 78| | 79| 1.05k| return 0; 80| 1.05k|} ndpi_fill_prefix_v4: 3182| 144k|int ndpi_fill_prefix_v4(ndpi_prefix_t *p, const struct in_addr *a, int b, int mb) { 3183| 144k| memset(p, 0, sizeof(ndpi_prefix_t)); 3184| | 3185| 144k| if(b < 0 || b > mb) ------------------ | Branch (3185:6): [True: 0, False: 144k] | Branch (3185:15): [True: 0, False: 144k] ------------------ 3186| 0| return(-1); 3187| | 3188| 144k| p->add.sin.s_addr = a->s_addr, p->family = AF_INET, p->bitlen = b, p->ref_count = 0; 3189| | 3190| 144k| return(0); 3191| 144k|} ndpi_fill_prefix_v6: 3195| 20.4k|int ndpi_fill_prefix_v6(ndpi_prefix_t *prefix, const struct in6_addr *addr, int bits, int maxbits) { 3196| 20.4k| memset(prefix, 0, sizeof(ndpi_prefix_t)); 3197| | 3198| 20.4k| if(bits < 0 || bits > maxbits) ------------------ | Branch (3198:6): [True: 0, False: 20.4k] | Branch (3198:18): [True: 0, False: 20.4k] ------------------ 3199| 0| return -1; 3200| | 3201| 20.4k| memcpy(&prefix->add.sin6, addr, (maxbits + 7) / 8); 3202| 20.4k| prefix->family = AF_INET6, prefix->bitlen = bits, prefix->ref_count = 0; 3203| | 3204| 20.4k| return 0; 3205| 20.4k|} ndpi_load_ptree_file: 3489| 3.16k| u_int16_t protocol_id) { 3490| 3.16k| char buffer[1024], *line, *addr, *cidr, *saveptr; 3491| 3.16k| FILE *fd; 3492| 3.16k| int len; 3493| 3.16k| u_int num_loaded = 0; 3494| | 3495| 3.16k| if( !path || !ptree) ------------------ | Branch (3495:7): [True: 0, False: 3.16k] | Branch (3495:16): [True: 183, False: 2.97k] ------------------ 3496| 183| return(-1); 3497| | 3498| 2.97k| fd = fopen(path, "r"); 3499| | 3500| 2.97k| if(fd == NULL) { ------------------ | Branch (3500:6): [True: 993, False: 1.98k] ------------------ 3501| | /* NDPI_LOG_ERR(NULL, "Unable to open file %s [%s]\n", path, strerror(errno)); */ 3502| 993| return(-1); 3503| 993| } 3504| | 3505| 13.9k| while(1) { ------------------ | Branch (3505:9): [True: 13.9k, Folded] ------------------ 3506| 13.9k| line = fgets(buffer, sizeof(buffer), fd); 3507| | 3508| 13.9k| if(line == NULL) ------------------ | Branch (3508:8): [True: 1.98k, False: 11.9k] ------------------ 3509| 1.98k| break; 3510| | 3511| 11.9k| len = strlen(line); 3512| | 3513| 11.9k| if((len <= 1) || (line[0] == '#')) ------------------ | Branch (3513:8): [True: 2.97k, False: 8.93k] | Branch (3513:22): [True: 1.98k, False: 6.95k] ------------------ 3514| 4.96k| continue; 3515| | 3516| 6.95k| line[len - 1] = '\0'; 3517| 6.95k| addr = strtok_r(line, "/", &saveptr); 3518| | 3519| 6.95k| if(addr) { ------------------ | Branch (3519:8): [True: 6.95k, False: 0] ------------------ 3520| 6.95k| ndpi_patricia_node_t *node; 3521| 6.95k| bool is_ipv4 = strchr(addr, ':') ? false : true; ------------------ | Branch (3521:22): [True: 2.97k, False: 3.97k] ------------------ 3522| | 3523| 6.95k| cidr = strtok_r(NULL, "\n", &saveptr); 3524| | 3525| 6.95k| if(is_ipv4) { ------------------ | Branch (3525:10): [True: 3.97k, False: 2.97k] ------------------ 3526| 3.97k| struct in_addr addr4; 3527| | 3528| 3.97k| addr4.s_addr = inet_addr(addr); 3529| | 3530| | /* printf("+ %s/%d\n", addr, cidr ? atoi(cidr) : 32); */ 3531| 3.97k| node = add_to_ptree(ptree->v4, AF_INET, &addr4, cidr ? atoi(cidr) : 32 /* bits */); ------------------ | Branch (3531:50): [True: 1.98k, False: 1.98k] ------------------ 3532| 3.97k| } else { 3533| 2.97k| struct in6_addr addr6; 3534| | 3535| 2.97k| if(inet_pton(AF_INET6, addr, &addr6) == 1) ------------------ | Branch (3535:5): [True: 2.97k, False: 0] ------------------ 3536| 2.97k| node = add_to_ptree(ptree->v6, AF_INET6, &addr6, cidr ? atoi(cidr) : 128); ------------------ | Branch (3536:53): [True: 993, False: 1.98k] ------------------ 3537| 0| else 3538| 0| node = NULL; 3539| 2.97k| } 3540| | 3541| 6.95k| if(node != NULL) { ------------------ | Branch (3541:10): [True: 5.55k, False: 1.39k] ------------------ 3542| 5.55k| u_int i, found = 0; 3543| | 3544| 5.55k| for(i=0; ivalue.u.uv16[i].user_value == 0) { ------------------ | Branch (3545:7): [True: 5.55k, False: 0] ------------------ 3546| 5.55k| node->value.u.uv16[i].user_value = protocol_id, 3547| 5.55k| node->value.u.uv16[i].additional_user_value = 0 /* port */; 3548| 5.55k| found = 1; 3549| 5.55k| break; 3550| 5.55k| } 3551| 5.55k| } 3552| | 3553| 5.55k| if(found) ------------------ | Branch (3553:5): [True: 5.55k, False: 0] ------------------ 3554| 5.55k| num_loaded++; 3555| 5.55k| } 3556| 6.95k| } 3557| 6.95k| } 3558| | 3559| 1.98k| fclose(fd); 3560| 1.98k| return(num_loaded); 3561| 2.97k|} ndpi_is_ipv6: 11486| 301k|u_int8_t ndpi_is_ipv6(const ndpi_ip_addr_t *ip) { 11487| 301k| return(ip->ipv6.u6_addr.u6_addr32[1] != 0 || ip->ipv6.u6_addr.u6_addr32[2] != 0 || ------------------ | Branch (11487:10): [True: 26.5k, False: 274k] | Branch (11487:48): [True: 2.34k, False: 272k] ------------------ 11488| 272k| ip->ipv6.u6_addr.u6_addr32[3] != 0); ------------------ | Branch (11488:3): [True: 1.45k, False: 270k] ------------------ 11489| 301k|} ndpi_get_ip_string: 11493| 133k|char *ndpi_get_ip_string(const ndpi_ip_addr_t *ip, char *buf, u_int buf_len) { 11494| 133k| const u_int8_t *a = (const u_int8_t *) &ip->ipv4; 11495| | 11496| 133k| if(ndpi_is_ipv6(ip)) { ------------------ | Branch (11496:6): [True: 11.2k, False: 122k] ------------------ 11497| 11.2k| struct in6_addr addr = *(struct in6_addr *)&ip->ipv6.u6_addr; 11498| | 11499| 11.2k| if(inet_ntop(AF_INET6, &addr, buf, buf_len) == NULL) ------------------ | Branch (11499:8): [True: 0, False: 11.2k] ------------------ 11500| 0| buf[0] = '\0'; 11501| | 11502| 11.2k| return(buf); 11503| 11.2k| } 11504| | 11505| 122k| ndpi_snprintf(buf, buf_len, "%u.%u.%u.%u", a[0], a[1], a[2], a[3]); 11506| | 11507| 122k| return(buf); 11508| 133k|} ndpi_parse_ip_string: 11513| 133k|int ndpi_parse_ip_string(const char *ip_str, ndpi_ip_addr_t *parsed_ip) { 11514| 133k| int rv = -1; 11515| 133k| memset(parsed_ip, 0, sizeof(*parsed_ip)); 11516| | 11517| 133k| if(strchr(ip_str, '.')) { ------------------ | Branch (11517:6): [True: 122k, False: 10.8k] ------------------ 11518| 122k| if(inet_pton(AF_INET, ip_str, &parsed_ip->ipv4) > 0) ------------------ | Branch (11518:8): [True: 122k, False: 350] ------------------ 11519| 122k| rv = 4; 11520| 122k| } else { 11521| 10.8k| if(inet_pton(AF_INET6, ip_str, &parsed_ip->ipv6) > 0) ------------------ | Branch (11521:8): [True: 10.8k, False: 0] ------------------ 11522| 10.8k| rv = 6; 11523| 10.8k| } 11524| | 11525| 133k| return(rv); 11526| 133k|} ndpi_ptree_create: 12599| 1.05k|ndpi_ptree_t *ndpi_ptree_create(void) { 12600| 1.05k| ndpi_ptree_t *tree = (ndpi_ptree_t *) ndpi_malloc(sizeof(ndpi_ptree_t)); 12601| | 12602| 1.05k| if(tree) { ------------------ | Branch (12602:6): [True: 1.03k, False: 18] ------------------ 12603| 1.03k| tree->v4 = ndpi_patricia_new(32); 12604| 1.03k| tree->v6 = ndpi_patricia_new(128); 12605| | 12606| 1.03k| if((!tree->v4) || (!tree->v6)) { ------------------ | Branch (12606:8): [True: 31, False: 1.00k] | Branch (12606:23): [True: 12, False: 993] ------------------ 12607| 43| ndpi_ptree_destroy(tree); 12608| 43| return(NULL); 12609| 43| } 12610| 1.03k| } 12611| | 12612| 1.01k| return(tree); 12613| 1.05k|} ndpi_ptree_destroy: 12617| 1.09k|void ndpi_ptree_destroy(ndpi_ptree_t *tree) { 12618| 1.09k| if(tree) { ------------------ | Branch (12618:6): [True: 1.03k, False: 61] ------------------ 12619| 1.03k| if(tree->v4) ------------------ | Branch (12619:8): [True: 1.00k, False: 31] ------------------ 12620| 1.00k| ndpi_patricia_destroy(tree->v4, free_ptree_data); 12621| | 12622| 1.03k| if(tree->v6) ------------------ | Branch (12622:8): [True: 1.02k, False: 13] ------------------ 12623| 1.02k| ndpi_patricia_destroy(tree->v6, free_ptree_data); 12624| | 12625| 1.03k| ndpi_free(tree); 12626| 1.03k| } 12627| 1.09k|} ndpi_ptree_insert: 12632| 133k| u_int8_t bits, u_int64_t user_data) { 12633| 133k| u_int8_t is_v6 = ndpi_is_ipv6(addr); 12634| 133k| ndpi_patricia_tree_t *ptree; 12635| 133k| ndpi_prefix_t prefix; 12636| 133k| ndpi_patricia_node_t *node; 12637| | 12638| 133k| if(!tree) ------------------ | Branch (12638:6): [True: 3.88k, False: 129k] ------------------ 12639| 3.88k| return(-4); 12640| | 12641| 129k| ptree = is_v6 ? tree->v6 : tree->v4; ------------------ | Branch (12641:11): [True: 10.5k, False: 119k] ------------------ 12642| | 12643| 129k| if(bits > ptree->maxbits) ------------------ | Branch (12643:6): [True: 694, False: 129k] ------------------ 12644| 694| return(-1); 12645| | 12646| 129k| if(is_v6) ------------------ | Branch (12646:6): [True: 10.5k, False: 118k] ------------------ 12647| 10.5k| ndpi_fill_prefix_v6(&prefix, (const struct in6_addr *) &addr->ipv6, bits, ptree->maxbits); 12648| 118k| else 12649| 118k| ndpi_fill_prefix_v4(&prefix, (const struct in_addr *) &addr->ipv4, bits, ptree->maxbits); 12650| | 12651| | /* Verify that the node does not already exist */ 12652| 129k| node = ndpi_patricia_search_best(ptree, &prefix); 12653| | 12654| 129k| if(node && (node->prefix->bitlen == bits)) ------------------ | Branch (12654:6): [True: 119k, False: 10.0k] | Branch (12654:14): [True: 107k, False: 11.8k] ------------------ 12655| 107k| return(-2); 12656| | 12657| 21.9k| node = ndpi_patricia_lookup(ptree, &prefix); 12658| | 12659| 21.9k| if(node != NULL) { ------------------ | Branch (12659:6): [True: 18.5k, False: 3.34k] ------------------ 12660| 18.5k| node->value.u.uv64 = user_data; 12661| | 12662| 18.5k| return(0); 12663| 18.5k| } 12664| | 12665| 3.34k| return(-3); 12666| 21.9k|} ndpi_ptree_match_addr: 12671| 33.6k| const ndpi_ip_addr_t *addr, u_int64_t *user_data) { 12672| 33.6k| u_int8_t is_v6 = ndpi_is_ipv6(addr); 12673| 33.6k| ndpi_patricia_tree_t *ptree; 12674| 33.6k| ndpi_prefix_t prefix; 12675| 33.6k| ndpi_patricia_node_t *node; 12676| 33.6k| int bits; 12677| | 12678| 33.6k| if(!tree) ------------------ | Branch (12678:6): [True: 4.46k, False: 29.1k] ------------------ 12679| 4.46k| return(-2); 12680| | 12681| 29.1k| ptree = is_v6 ? tree->v6 : tree->v4; ------------------ | Branch (12681:11): [True: 6.88k, False: 22.2k] ------------------ 12682| 29.1k| bits = ptree->maxbits; 12683| | 12684| 29.1k| if(is_v6) ------------------ | Branch (12684:6): [True: 6.88k, False: 22.2k] ------------------ 12685| 6.88k| ndpi_fill_prefix_v6(&prefix, (const struct in6_addr *) &addr->ipv6, 12686| 6.88k| bits, ptree->maxbits); 12687| 22.2k| else 12688| 22.2k| ndpi_fill_prefix_v4(&prefix, (const struct in_addr *) &addr->ipv4, 12689| 22.2k| bits, ptree->maxbits); 12690| | 12691| 29.1k| node = ndpi_patricia_search_best(ptree, &prefix); 12692| | 12693| 29.1k| if(node) { ------------------ | Branch (12693:6): [True: 9.73k, False: 19.4k] ------------------ 12694| 9.73k| *user_data = node->value.u.uv64; 12695| | 12696| 9.73k| return(0); 12697| 9.73k| } 12698| | 12699| 19.4k| return(-1); 12700| 29.1k|} ndpi_main.c:add_to_ptree: 3465| 6.95k|static ndpi_patricia_node_t* add_to_ptree(ndpi_patricia_tree_t *tree, int family, void *addr, int bits) { 3466| 6.95k| ndpi_prefix_t prefix; 3467| 6.95k| ndpi_patricia_node_t *node; 3468| | 3469| 6.95k| if(family == AF_INET) ------------------ | Branch (3469:6): [True: 3.97k, False: 2.97k] ------------------ 3470| 3.97k| ndpi_fill_prefix_v4(&prefix, (struct in_addr *) addr, bits, tree->maxbits); 3471| 2.97k| else 3472| 2.97k| ndpi_fill_prefix_v6(&prefix, (struct in6_addr *) addr, bits, tree->maxbits); 3473| | 3474| 6.95k| node = ndpi_patricia_lookup(tree, &prefix); 3475| | /* if(node) memset(&node->value, 0, sizeof(node->value)); */ 3476| | 3477| 6.95k| return(node); 3478| 6.95k|} ndpi_set_memory_alloction_functions: 52| 1.05k| void (*__ndpi_flow_free)(void *ptr)) { 53| | 54| | /* We can't log here */ 55| | 56| 1.05k| if(__ndpi_malloc && __ndpi_free && ------------------ | Branch (56:6): [True: 1.05k, False: 0] | Branch (56:23): [True: 1.05k, False: 0] ------------------ 57| 1.05k| __ndpi_calloc && __ndpi_realloc) { ------------------ | Branch (57:6): [True: 1.05k, False: 0] | Branch (57:23): [True: 1.05k, False: 0] ------------------ 58| 1.05k| _ndpi_malloc = __ndpi_malloc; 59| 1.05k| _ndpi_free = __ndpi_free; 60| 1.05k| _ndpi_calloc = __ndpi_calloc; 61| 1.05k| _ndpi_realloc = __ndpi_realloc; 62| 1.05k| } 63| 1.05k| if(__ndpi_aligned_malloc && __ndpi_aligned_free) { ------------------ | Branch (63:6): [True: 0, False: 1.05k] | Branch (63:31): [True: 0, False: 0] ------------------ 64| 0| _ndpi_aligned_malloc = __ndpi_aligned_malloc; 65| 0| _ndpi_aligned_free = __ndpi_aligned_free; 66| 0| } 67| 1.05k| if(__ndpi_flow_malloc && __ndpi_flow_free) { ------------------ | Branch (67:6): [True: 1.05k, False: 0] | Branch (67:28): [True: 1.05k, False: 0] ------------------ 68| 1.05k| _ndpi_flow_malloc = __ndpi_flow_malloc; 69| 1.05k| _ndpi_flow_free = __ndpi_flow_free; 70| 1.05k| } 71| 1.05k|} ndpi_malloc: 81| 1.05k|void *ndpi_malloc(size_t size) { 82| 1.05k| __sync_fetch_and_add(&ndpi_tot_allocated_memory, size); 83| 1.05k| return(_ndpi_malloc ? _ndpi_malloc(size) : malloc(size)); ------------------ | Branch (83:10): [True: 1.05k, False: 0] ------------------ 84| 1.05k|} ndpi_calloc: 88| 73.9k|void *ndpi_calloc(size_t nmemb, size_t size) { 89| 73.9k| __sync_fetch_and_add(&ndpi_tot_allocated_memory, nmemb * size); 90| 73.9k| return(_ndpi_calloc ? _ndpi_calloc(nmemb, size) : calloc(nmemb, size)); ------------------ | Branch (90:10): [True: 73.9k, False: 0] ------------------ 91| 73.9k|} ndpi_free: 95| 70.2k|void ndpi_free(void *ptr) { 96| 70.2k| _ndpi_free ? _ndpi_free(ptr) : free(ptr); ------------------ | Branch (96:3): [True: 70.2k, False: 0] ------------------ 97| 70.2k|} ndpi_vsnprintf: 3979| 122k|{ 3980| |#ifdef WIN32 3981| | if((str == NULL) || (size == 0) || (format == NULL)) { 3982| | return -1; 3983| | } 3984| | 3985| | int ret = vsnprintf_s(str, size, _TRUNCATE, format, va_args); 3986| | 3987| | if(ret < 0) { 3988| | return size; 3989| | } else { 3990| | return ret; 3991| | } 3992| |#else 3993| 122k| return vsnprintf(str, size, format, va_args); 3994| 122k|#endif 3995| 122k|} ndpi_snprintf: 4012| 122k|int ndpi_snprintf(char * str, size_t size, char const * format, ...) { 4013| 122k| va_list va_args; 4014| | 4015| 122k| va_start(va_args, format); 4016| 122k| int rc = ndpi_vsnprintf(str, size, format, va_args); 4017| 122k| va_end(va_args); 4018| | 4019| | /* 4020| | ndpi_snprintf wraps standard snprintf, which returns the number of characters that would 4021| | have been written (not the number actually written) when the output is truncated. 4022| | So if rc >= size, only size - 1 characters were actually written, but tls_s_len is 4023| | advanced by rc. This has two consequences: 4024| | */ 4025| | 4026| 122k| if(rc >= (int)size) ------------------ | Branch (4026:6): [True: 0, False: 122k] ------------------ 4027| 0| rc = size - 1; 4028| | 4029| 122k| return(rc); 4030| 122k|} ndpi_patricia_new: 310| 2.07k|{ 311| 2.07k| ndpi_patricia_tree_t *patricia = (ndpi_patricia_tree_t*)ndpi_calloc(1, sizeof *patricia); 312| 2.07k| if(!patricia) ------------------ | Branch (312:6): [True: 44, False: 2.02k] ------------------ 313| 44| return (NULL); 314| | 315| 2.02k| patricia->maxbits = maxbits; 316| 2.02k| patricia->head = NULL; 317| 2.02k| patricia->num_active_node = 0; 318| 2.02k| assert((u_int16_t)maxbits <= PATRICIA_MAXBITS); /* XXX */ ------------------ | Branch (318:3): [True: 0, False: 2.02k] | Branch (318:3): [True: 2.02k, False: 0] ------------------ 319| 2.02k| num_active_patricia++; 320| 2.02k| return (patricia); 321| 2.02k|} ndpi_Clear_Patricia: 330| 2.02k|{ 331| 2.02k| if(!patricia) ------------------ | Branch (331:6): [True: 0, False: 2.02k] ------------------ 332| 0| return; 333| | 334| 2.02k| if(patricia->head) { ------------------ | Branch (334:6): [True: 1.98k, False: 43] ------------------ 335| | 336| 1.98k| ndpi_patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; 337| 1.98k| ndpi_patricia_node_t **Xsp = Xstack; 338| 1.98k| ndpi_patricia_node_t *Xrn = patricia->head; 339| | 340| 41.1k| while (Xrn) { ------------------ | Branch (340:12): [True: 39.1k, False: 1.98k] ------------------ 341| 39.1k| ndpi_patricia_node_t *l = Xrn->l; 342| 39.1k| ndpi_patricia_node_t *r = Xrn->r; 343| | 344| 39.1k| if(Xrn->prefix) { ------------------ | Branch (344:10): [True: 24.1k, False: 14.9k] ------------------ 345| 24.1k| ndpi_Deref_Prefix (Xrn->prefix); 346| 24.1k| if(Xrn->data && func) ------------------ | Branch (346:5): [True: 0, False: 24.1k] | Branch (346:18): [True: 0, False: 0] ------------------ 347| 0| func (Xrn->data); 348| 24.1k| } 349| 14.9k| else { 350| 14.9k| assert (Xrn->data == NULL); ------------------ | Branch (350:2): [True: 0, False: 14.9k] | Branch (350:2): [True: 14.9k, False: 0] ------------------ 351| 14.9k| } 352| 39.1k| ndpi_DeleteEntry (Xrn); 353| 39.1k| patricia->num_active_node--; 354| | 355| 39.1k| if(l) { ------------------ | Branch (355:10): [True: 18.7k, False: 20.3k] ------------------ 356| 18.7k| if(r) { ------------------ | Branch (356:5): [True: 16.2k, False: 2.56k] ------------------ 357| 16.2k| *Xsp++ = r; 358| 16.2k| } 359| 18.7k| Xrn = l; 360| 20.3k| } else if(r) { ------------------ | Branch (360:17): [True: 2.13k, False: 18.2k] ------------------ 361| 2.13k| Xrn = r; 362| 18.2k| } else if(Xsp != Xstack) { ------------------ | Branch (362:17): [True: 16.2k, False: 1.98k] ------------------ 363| 16.2k| Xrn = *(--Xsp); 364| 16.2k| } else { 365| 1.98k| Xrn = NULL; 366| 1.98k| } 367| 39.1k| } 368| 1.98k| } 369| 2.02k| assert (patricia->num_active_node == 0); ------------------ | Branch (369:3): [True: 0, False: 2.02k] | Branch (369:3): [True: 2.02k, False: 0] ------------------ 370| | /* ndpi_DeleteEntry (patricia); */ 371| 2.02k|} ndpi_patricia_destroy: 375| 2.02k|{ 376| 2.02k| ndpi_Clear_Patricia (patricia, func); 377| 2.02k| ndpi_DeleteEntry (patricia); 378| 2.02k| num_active_patricia--; 379| 2.02k|} ndpi_patricia_search_best2: 551| 158k|{ 552| 158k| ndpi_patricia_node_t *node; 553| 158k| ndpi_patricia_node_t *stack[PATRICIA_MAXBITS + 1]; 554| 158k| u_char *addr; 555| 158k| u_int16_t bitlen; 556| 158k| int cnt = 0; 557| | 558| 158k| if(patricia == NULL) ------------------ | Branch (558:6): [True: 0, False: 158k] ------------------ 559| 0| return (NULL); 560| | 561| 158k| assert (prefix); ------------------ | Branch (561:3): [True: 0, False: 158k] | Branch (561:3): [True: 158k, False: 0] ------------------ 562| 158k| assert (prefix->bitlen <= patricia->maxbits); ------------------ | Branch (562:3): [True: 0, False: 158k] | Branch (562:3): [True: 158k, False: 0] ------------------ 563| | 564| 158k| patricia->stats.n_search++; 565| | 566| 158k| if(patricia->head == NULL) ------------------ | Branch (566:6): [True: 1.47k, False: 156k] ------------------ 567| 1.47k| return (NULL); 568| | 569| 156k| node = patricia->head; 570| 156k| addr = ndpi_prefix_touchar (prefix); ------------------ | | 50| 156k|#define ndpi_prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin) ------------------ 571| 156k| bitlen = prefix->bitlen; 572| | 573| 373k| while (node->bit < bitlen) { ------------------ | Branch (573:10): [True: 240k, False: 133k] ------------------ 574| 240k| if(node->prefix) { ------------------ | Branch (574:8): [True: 95.1k, False: 145k] ------------------ 575| |#ifdef PATRICIA_DEBUG 576| | fprintf (stderr, "patricia_search_best: push %s/%d\n", 577| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 578| |#endif /* PATRICIA_DEBUG */ 579| 95.1k| stack[cnt++] = node; 580| 95.1k| } 581| | 582| 240k| if(BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) { ------------------ | | 54| 240k|#define BIT_TEST(f, b) ((f) & (b)) | | ------------------ | | | Branch (54:25): [True: 102k, False: 138k] | | ------------------ ------------------ 583| |#ifdef PATRICIA_DEBUG 584| | if(node->prefix) 585| | fprintf (stderr, "patricia_search_best: take right %s/%d\n", 586| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 587| | else 588| | fprintf (stderr, "patricia_search_best: take right at %u\n", 589| | node->bit); 590| |#endif /* PATRICIA_DEBUG */ 591| 102k| node = node->r; 592| 138k| } else { 593| |#ifdef PATRICIA_DEBUG 594| | if(node->prefix) 595| | fprintf (stderr, "patricia_search_best: take left %s/%d\n", 596| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 597| | else 598| | fprintf (stderr, "patricia_search_best: take left at %u\n", 599| | node->bit); 600| |#endif /* PATRICIA_DEBUG */ 601| 138k| node = node->l; 602| 138k| } 603| | 604| 240k| if(node == NULL) ------------------ | Branch (604:8): [True: 23.5k, False: 217k] ------------------ 605| 23.5k| break; 606| 240k| } 607| | 608| 156k| if(inclusive && node && node->prefix) { ------------------ | Branch (608:6): [True: 156k, False: 0] | Branch (608:19): [True: 133k, False: 23.5k] | Branch (608:27): [True: 131k, False: 1.64k] ------------------ 609| |#ifdef PATRICIA_DEBUG 610| | fprintf (stderr, "patricia_search_best: found node %s/%d [searching %s/%d]\n", 611| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen, 612| | ndpi_prefix_toa (prefix), prefix->bitlen); 613| |#endif 614| 131k| stack[cnt++] = node; 615| 131k| } 616| | 617| |#ifdef PATRICIA_DEBUG 618| | if(node == NULL) 619| | fprintf (stderr, "patricia_search_best: stop at null\n"); 620| | else if(node->prefix) 621| | fprintf (stderr, "patricia_search_best: stop at %s/%d\n", 622| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 623| | else 624| | fprintf (stderr, "patricia_search_best: stop at %u\n", node->bit); 625| |#endif /* PATRICIA_DEBUG */ 626| | 627| 156k| if(cnt <= 0) ------------------ | Branch (627:6): [True: 845, False: 155k] ------------------ 628| 845| return (NULL); 629| | 630| 206k| while (--cnt >= 0) { ------------------ | Branch (630:10): [True: 179k, False: 27.2k] ------------------ 631| 179k| node = stack[cnt]; 632| |#ifdef PATRICIA_DEBUG 633| | fprintf (stderr, "patricia_search_best: pop %s/%d\n", 634| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 635| |#endif /* PATRICIA_DEBUG */ 636| 179k| if(ndpi_comp_with_mask (ndpi_prefix_tochar (node->prefix), ------------------ | Branch (636:8): [True: 131k, False: 48.2k] ------------------ 637| 179k| ndpi_prefix_tochar (prefix), 638| 179k| node->prefix->bitlen) && node->prefix->bitlen <= bitlen) { ------------------ | Branch (638:33): [True: 128k, False: 2.60k] ------------------ 639| |#ifdef PATRICIA_DEBUG 640| | fprintf (stderr, "patricia_search_best: found %s/%d\n", 641| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 642| |#endif /* PATRICIA_DEBUG */ 643| 128k| patricia->stats.n_found++; 644| 128k| return (node); 645| 128k| } 646| 179k| } 647| 27.2k| return (NULL); 648| 155k|} ndpi_patricia_search_best: 653| 158k|{ 654| 158k| return (ndpi_patricia_search_best2 (patricia, prefix, 1)); 655| 158k|} ndpi_patricia_lookup: 660| 28.8k|{ 661| 28.8k| ndpi_patricia_node_t *node, *new_node, *parent, *glue; 662| 28.8k| u_char *addr, *test_addr; 663| 28.8k| u_int16_t bitlen, check_bit, differ_bit; 664| 28.8k| int i, j; 665| | 666| 28.8k| if(!patricia) ------------------ | Branch (666:6): [True: 0, False: 28.8k] ------------------ 667| 0| return (NULL); 668| | 669| |#ifdef PATRICIA_DEBUG 670| | fprintf (stderr, "patricia_lookup() %s/%d (head)\n", 671| | ndpi_prefix_toa (prefix), prefix->bitlen); 672| |#endif /* PATRICIA_DEBUG */ 673| | 674| 28.8k| assert (prefix); ------------------ | Branch (674:3): [True: 0, False: 28.8k] | Branch (674:3): [True: 28.8k, False: 0] ------------------ 675| 28.8k| assert (prefix->bitlen <= patricia->maxbits); ------------------ | Branch (675:3): [True: 0, False: 28.8k] | Branch (675:3): [True: 28.8k, False: 0] ------------------ 676| | 677| 28.8k| if(patricia->head == NULL) { ------------------ | Branch (677:6): [True: 2.41k, False: 26.4k] ------------------ 678| 2.41k| node = (ndpi_patricia_node_t*)ndpi_calloc(1, sizeof *node); 679| 2.41k| if(!node) ------------------ | Branch (679:8): [True: 133, False: 2.27k] ------------------ 680| 133| return NULL; 681| 2.27k| node->bit = prefix->bitlen; 682| 2.27k| node->prefix = ndpi_Ref_Prefix (prefix); 683| 2.27k| if(!node->prefix) { ------------------ | Branch (683:8): [True: 293, False: 1.98k] ------------------ 684| 293| ndpi_free(node); 685| 293| return NULL; 686| 293| } 687| 1.98k| node->parent = NULL; 688| 1.98k| node->l = node->r = NULL; 689| 1.98k| node->data = NULL; 690| 1.98k| patricia->head = node; 691| |#ifdef PATRICIA_DEBUG 692| | fprintf (stderr, "patricia_lookup: new_node #0 %s/%d (head)\n", 693| | ndpi_prefix_toa (prefix), prefix->bitlen); 694| |#endif /* PATRICIA_DEBUG */ 695| 1.98k| patricia->num_active_node++; 696| 1.98k| return (node); 697| 2.27k| } 698| | 699| 26.4k| addr = ndpi_prefix_touchar (prefix); ------------------ | | 50| 26.4k|#define ndpi_prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin) ------------------ 700| 26.4k| bitlen = prefix->bitlen; 701| 26.4k| node = patricia->head; 702| | 703| 139k| while (node->bit < bitlen || node->prefix == NULL) { ------------------ | Branch (703:10): [True: 118k, False: 21.3k] | Branch (703:32): [True: 4.01k, False: 17.3k] ------------------ 704| 122k| if(node->bit < patricia->maxbits && ------------------ | Branch (704:8): [True: 122k, False: 0] ------------------ 705| 122k| BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) { ------------------ | | 54| 122k|#define BIT_TEST(f, b) ((f) & (b)) | | ------------------ | | | Branch (54:25): [True: 60.0k, False: 62.4k] | | ------------------ ------------------ 706| 60.0k| if(node->r == NULL) ------------------ | Branch (706:10): [True: 3.83k, False: 56.2k] ------------------ 707| 3.83k| break; 708| |#ifdef PATRICIA_DEBUG 709| | if(node->prefix) 710| | fprintf (stderr, "patricia_lookup: take right %s/%d\n", 711| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 712| | else 713| | fprintf (stderr, "patricia_lookup: take right at %u\n", node->bit); 714| |#endif /* PATRICIA_DEBUG */ 715| 56.2k| node = node->r; 716| 56.2k| } 717| 62.4k| else { 718| 62.4k| if(node->l == NULL) ------------------ | Branch (718:10): [True: 5.29k, False: 57.1k] ------------------ 719| 5.29k| break; 720| |#ifdef PATRICIA_DEBUG 721| | if(node->prefix) 722| | fprintf (stderr, "patricia_lookup: take left %s/%d\n", 723| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 724| | else 725| | fprintf (stderr, "patricia_lookup: take left at %u\n", node->bit); 726| |#endif /* PATRICIA_DEBUG */ 727| 57.1k| node = node->l; 728| 57.1k| } 729| | 730| 122k| assert (node); ------------------ | Branch (730:5): [True: 0, False: 113k] | Branch (730:5): [True: 113k, False: 0] ------------------ 731| 113k| } 732| | 733| 26.4k| assert (node->prefix); ------------------ | Branch (733:3): [True: 0, False: 26.4k] | Branch (733:3): [True: 26.4k, False: 0] ------------------ 734| |#ifdef PATRICIA_DEBUG 735| | fprintf (stderr, "patricia_lookup: stop at %s/%d\n", 736| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 737| |#endif /* PATRICIA_DEBUG */ 738| | 739| 26.4k| test_addr = ndpi_prefix_touchar (node->prefix); ------------------ | | 50| 26.4k|#define ndpi_prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin) ------------------ 740| | /* find the first bit different */ 741| 26.4k| check_bit = (node->bit < bitlen)? node->bit: bitlen; ------------------ | Branch (741:15): [True: 9.13k, False: 17.3k] ------------------ 742| 26.4k| differ_bit = 0; 743| 70.0k| for (i = 0; (u_int)i*8 < check_bit; i++) { ------------------ | Branch (743:15): [True: 64.0k, False: 5.91k] ------------------ 744| 64.0k| int r; 745| | 746| 64.0k| if((r = (addr[i] ^ test_addr[i])) == 0) { ------------------ | Branch (746:8): [True: 43.5k, False: 20.5k] ------------------ 747| 43.5k| differ_bit = (i + 1) * 8; 748| 43.5k| continue; 749| 43.5k| } 750| | /* I know the better way, but for now */ 751| 95.9k| for (j = 0; j < 8; j++) { ------------------ | Branch (751:17): [True: 95.9k, False: 0] ------------------ 752| 95.9k| if(BIT_TEST (r, (0x80 >> j))) ------------------ | | 54| 95.9k|#define BIT_TEST(f, b) ((f) & (b)) | | ------------------ | | | Branch (54:25): [True: 20.5k, False: 75.4k] | | ------------------ ------------------ 753| 20.5k| break; 754| 95.9k| } 755| | /* must be found */ 756| 20.5k| assert (j < 8); ------------------ | Branch (756:5): [True: 0, False: 20.5k] | Branch (756:5): [True: 20.5k, False: 0] ------------------ 757| 20.5k| differ_bit = i * 8 + j; 758| 20.5k| break; 759| 20.5k| } 760| | 761| 26.4k| if(differ_bit > check_bit) ------------------ | Branch (761:6): [True: 4.29k, False: 22.1k] ------------------ 762| 4.29k| differ_bit = check_bit; 763| |#ifdef PATRICIA_DEBUG 764| | fprintf (stderr, "patricia_lookup: differ_bit %d\n", differ_bit); 765| |#endif /* PATRICIA_DEBUG */ 766| | 767| 26.4k| parent = node->parent; 768| 39.8k| while (parent && parent->bit >= differ_bit) { ------------------ | Branch (768:10): [True: 35.6k, False: 4.26k] | Branch (768:20): [True: 13.4k, False: 22.2k] ------------------ 769| 13.4k| node = parent; 770| 13.4k| parent = node->parent; 771| |#ifdef PATRICIA_DEBUG 772| | if(node->prefix) 773| | fprintf (stderr, "patricia_lookup: up to %s/%d\n", 774| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 775| | else 776| | fprintf (stderr, "patricia_lookup: up to %u\n", node->bit); 777| |#endif /* PATRICIA_DEBUG */ 778| 13.4k| } 779| | 780| 26.4k| if(differ_bit == bitlen && node->bit == bitlen) { ------------------ | Branch (780:6): [True: 4.49k, False: 21.9k] | Branch (780:30): [True: 846, False: 3.64k] ------------------ 781| 846| if(node->prefix) { ------------------ | Branch (781:8): [True: 0, False: 846] ------------------ 782| |#ifdef PATRICIA_DEBUG 783| | fprintf (stderr, "patricia_lookup: found %s/%d\n", 784| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 785| |#endif /* PATRICIA_DEBUG */ 786| 0| return (node); 787| 0| } 788| 846| node->prefix = ndpi_Ref_Prefix (prefix); 789| 846| if(!node->prefix) { ------------------ | Branch (789:8): [True: 93, False: 753] ------------------ 790| 93| return NULL; 791| 93| } 792| |#ifdef PATRICIA_DEBUG 793| | fprintf (stderr, "patricia_lookup: new node #1 %s/%d (glue mod)\n", 794| | ndpi_prefix_toa (prefix), prefix->bitlen); 795| |#endif /* PATRICIA_DEBUG */ 796| 846| assert (node->data == NULL); ------------------ | Branch (796:5): [True: 0, False: 753] | Branch (796:5): [True: 753, False: 0] ------------------ 797| 753| return (node); 798| 753| } 799| | 800| 25.6k| new_node = (ndpi_patricia_node_t*)ndpi_calloc(1, sizeof *new_node); 801| 25.6k| if(!new_node) return NULL; ------------------ | Branch (801:6): [True: 1.64k, False: 23.9k] ------------------ 802| 23.9k| new_node->bit = prefix->bitlen; 803| 23.9k| new_node->prefix = ndpi_Ref_Prefix (prefix); 804| 23.9k| if(!new_node->prefix) { ------------------ | Branch (804:6): [True: 1.54k, False: 22.4k] ------------------ 805| 1.54k| ndpi_free(new_node); 806| 1.54k| return NULL; 807| 1.54k| } 808| 22.4k| new_node->parent = NULL; 809| 22.4k| new_node->l = new_node->r = NULL; 810| 22.4k| new_node->data = NULL; 811| 22.4k| patricia->num_active_node++; 812| | 813| 22.4k| if(node->bit == differ_bit) { ------------------ | Branch (813:6): [True: 2.40k, False: 20.0k] ------------------ 814| 2.40k| new_node->parent = node; 815| 2.40k| if(node->bit < patricia->maxbits && ------------------ | Branch (815:8): [True: 2.40k, False: 0] ------------------ 816| 2.40k| BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) { ------------------ | | 54| 2.40k|#define BIT_TEST(f, b) ((f) & (b)) | | ------------------ | | | Branch (54:25): [True: 1.17k, False: 1.23k] | | ------------------ ------------------ 817| 1.17k| assert (node->r == NULL); ------------------ | Branch (817:7): [True: 0, False: 1.17k] | Branch (817:7): [True: 1.17k, False: 0] ------------------ 818| 1.17k| node->r = new_node; 819| 1.17k| } 820| 1.23k| else { 821| 1.23k| assert (node->l == NULL); ------------------ | Branch (821:7): [True: 0, False: 1.23k] | Branch (821:7): [True: 1.23k, False: 0] ------------------ 822| 1.23k| node->l = new_node; 823| 1.23k| } 824| |#ifdef PATRICIA_DEBUG 825| | fprintf (stderr, "patricia_lookup: new_node #2 %s/%d (child)\n", 826| | ndpi_prefix_toa (prefix), prefix->bitlen); 827| |#endif /* PATRICIA_DEBUG */ 828| 2.40k| return (new_node); 829| 2.40k| } 830| | 831| 20.0k| if(bitlen == differ_bit) { ------------------ | Branch (831:6): [True: 3.27k, False: 16.7k] ------------------ 832| 3.27k| if(bitlen < patricia->maxbits && ------------------ | Branch (832:8): [True: 3.27k, False: 0] ------------------ 833| 3.27k| BIT_TEST (test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) { ------------------ | | 54| 3.27k|#define BIT_TEST(f, b) ((f) & (b)) | | ------------------ | | | Branch (54:25): [True: 1.45k, False: 1.82k] | | ------------------ ------------------ 834| 1.45k| new_node->r = node; 835| 1.45k| } 836| 1.82k| else { 837| 1.82k| new_node->l = node; 838| 1.82k| } 839| 3.27k| new_node->parent = node->parent; 840| 3.27k| if(node->parent == NULL) { ------------------ | Branch (840:8): [True: 499, False: 2.77k] ------------------ 841| 499| assert (patricia->head == node); ------------------ | Branch (841:7): [True: 0, False: 499] | Branch (841:7): [True: 499, False: 0] ------------------ 842| 499| patricia->head = new_node; 843| 499| } 844| 2.77k| else if(node->parent->r == node) { ------------------ | Branch (844:13): [True: 1.50k, False: 1.26k] ------------------ 845| 1.50k| node->parent->r = new_node; 846| 1.50k| } 847| 1.26k| else { 848| 1.26k| node->parent->l = new_node; 849| 1.26k| } 850| 3.27k| node->parent = new_node; 851| |#ifdef PATRICIA_DEBUG 852| | fprintf (stderr, "patricia_lookup: new_node #3 %s/%d (parent)\n", 853| | ndpi_prefix_toa (prefix), prefix->bitlen); 854| |#endif /* PATRICIA_DEBUG */ 855| 3.27k| } 856| 16.7k| else { 857| 16.7k| glue = (ndpi_patricia_node_t*)ndpi_calloc(1, sizeof *glue); 858| | 859| 16.7k| if(!glue) { ------------------ | Branch (859:8): [True: 1.02k, False: 15.7k] ------------------ 860| 1.02k| ndpi_Deref_Prefix(new_node->prefix); 861| 1.02k| ndpi_DeleteEntry (new_node); 862| 1.02k| patricia->num_active_node--; 863| 1.02k| return(NULL); 864| 1.02k| } 865| 15.7k| glue->bit = differ_bit; 866| 15.7k| glue->prefix = NULL; 867| 15.7k| glue->parent = node->parent; 868| 15.7k| glue->data = NULL; 869| 15.7k| patricia->num_active_node++; 870| 15.7k| if(differ_bit < patricia->maxbits && ------------------ | Branch (870:8): [True: 15.7k, False: 0] ------------------ 871| 15.7k| BIT_TEST (addr[differ_bit >> 3], 0x80 >> (differ_bit & 0x07))) { ------------------ | | 54| 15.7k|#define BIT_TEST(f, b) ((f) & (b)) | | ------------------ | | | Branch (54:25): [True: 7.31k, False: 8.42k] | | ------------------ ------------------ 872| 7.31k| glue->r = new_node; 873| 7.31k| glue->l = node; 874| 7.31k| } 875| 8.42k| else { 876| 8.42k| glue->r = node; 877| 8.42k| glue->l = new_node; 878| 8.42k| } 879| 15.7k| new_node->parent = glue; 880| | 881| 15.7k| if(node->parent == NULL) { ------------------ | Branch (881:8): [True: 2.09k, False: 13.6k] ------------------ 882| 2.09k| assert (patricia->head == node); ------------------ | Branch (882:7): [True: 0, False: 2.09k] | Branch (882:7): [True: 2.09k, False: 0] ------------------ 883| 2.09k| patricia->head = glue; 884| 2.09k| } 885| 13.6k| else if(node->parent->r == node) { ------------------ | Branch (885:13): [True: 6.83k, False: 6.81k] ------------------ 886| 6.83k| node->parent->r = glue; 887| 6.83k| } 888| 6.81k| else { 889| 6.81k| node->parent->l = glue; 890| 6.81k| } 891| 15.7k| node->parent = glue; 892| |#ifdef PATRICIA_DEBUG 893| | fprintf (stderr, "patricia_lookup: new_node #4 %s/%d (glue+node)\n", 894| | ndpi_prefix_toa (prefix), prefix->bitlen); 895| |#endif /* PATRICIA_DEBUG */ 896| 15.7k| } 897| 19.0k| return (new_node); 898| 20.0k|} ndpi_patricia.c:ndpi_Deref_Prefix: 288| 25.1k|{ 289| 25.1k| if(prefix == NULL) ------------------ | Branch (289:6): [True: 0, False: 25.1k] ------------------ 290| 0| return; 291| | /* for secure programming, raise an assert. no static prefix can call this */ 292| 25.1k| assert (prefix->ref_count > 0); ------------------ | Branch (292:3): [True: 0, False: 25.1k] | Branch (292:3): [True: 25.1k, False: 0] ------------------ 293| | 294| 25.1k| prefix->ref_count--; 295| 25.1k| assert (prefix->ref_count >= 0); ------------------ | Branch (295:3): [True: 0, False: 25.1k] | Branch (295:3): [True: 25.1k, False: 0] ------------------ 296| 25.1k| if(prefix->ref_count <= 0) { ------------------ | Branch (296:6): [True: 25.1k, False: 0] ------------------ 297| 25.1k| ndpi_DeleteEntry (prefix); 298| 25.1k| return; 299| 25.1k| } 300| 25.1k|} ndpi_patricia.c:ndpi_DeleteEntry: 57| 67.3k|static void ndpi_DeleteEntry(void *a) { 58| 67.3k| ndpi_free(a); 59| 67.3k|} ndpi_patricia.c:ndpi_comp_with_mask: 80| 179k|static int ndpi_comp_with_mask (void *addr, void *dest, u_int mask) { 81| 179k| uint32_t *pa = addr; 82| 179k| uint32_t *pd = dest; 83| 179k| uint32_t m; 84| 193k| for(;mask >= 32; mask -= 32, pa++,pd++) ------------------ | Branch (84:8): [True: 34.9k, False: 158k] ------------------ 85| 34.9k| if(*pa != *pd) return 0; ------------------ | Branch (85:8): [True: 20.9k, False: 13.9k] ------------------ 86| 158k| if(!mask) return 1; ------------------ | Branch (86:6): [True: 111k, False: 46.9k] ------------------ 87| 46.9k| m = htonl((~0u) << (32-mask)); 88| 46.9k| return (*pa & m) == (*pd &m); 89| 158k|} ndpi_patricia.c:ndpi_prefix_tochar: 67| 359k|{ 68| 359k| unsigned short family; 69| | 70| 359k| if(prefix == NULL) ------------------ | Branch (70:6): [True: 0, False: 359k] ------------------ 71| 0| return (NULL); 72| | 73| 359k| family = prefix->family; 74| | 75| 359k| if(family == AF_INET) return ((u_char *) & prefix->add.sin); ------------------ | Branch (75:6): [True: 311k, False: 48.2k] ------------------ 76| 48.2k| else if(family == AF_INET6) return ((u_char *) & prefix->add.sin6); ------------------ | Branch (76:11): [True: 48.2k, False: 0] ------------------ 77| 0| else /* if(family == AF_MAC) */ return ((u_char *) & prefix->add.mac); 78| 359k|} ndpi_patricia.c:ndpi_Ref_Prefix: 274| 27.1k|{ 275| 27.1k| if(prefix == NULL) ------------------ | Branch (275:6): [True: 0, False: 27.1k] ------------------ 276| 0| return (NULL); 277| 27.1k| if(prefix->ref_count == 0) { ------------------ | Branch (277:6): [True: 27.1k, False: 0] ------------------ 278| | /* make a copy in case of a static prefix */ 279| 27.1k| return (ndpi_New_Prefix2 (prefix->family, &prefix->add, prefix->bitlen, NULL)); 280| 27.1k| } 281| 0| prefix->ref_count++; 282| | /* fprintf(stderr, "[A %s, %d]\n", ndpi_prefix_toa (prefix), prefix->ref_count); */ 283| 0| return (prefix); 284| 27.1k|} ndpi_patricia.c:ndpi_New_Prefix2: 210| 27.1k|{ 211| 27.1k| int dynamic_allocated = 0; 212| 27.1k| int default_bitlen = sizeof(struct in_addr) * 8; 213| | 214| 27.1k| if(family == AF_INET6) { ------------------ | Branch (214:6): [True: 11.1k, False: 15.9k] ------------------ 215| 11.1k| default_bitlen = sizeof(struct in6_addr) * 8; 216| 11.1k| if(prefix == NULL) { ------------------ | Branch (216:8): [True: 11.1k, False: 0] ------------------ 217| 11.1k| prefix = (ndpi_prefix_t*)ndpi_calloc(1, sizeof (ndpi_prefix_t)); 218| 11.1k| if(!prefix) ------------------ | Branch (218:10): [True: 971, False: 10.2k] ------------------ 219| 971| return (NULL); 220| 10.2k| dynamic_allocated++; 221| 10.2k| } 222| 10.2k| memcpy (&prefix->add.sin6, dest, sizeof(struct in6_addr)); 223| 10.2k| } 224| 15.9k| else 225| 15.9k| if(family == AF_INET) { ------------------ | Branch (225:8): [True: 15.9k, False: 0] ------------------ 226| 15.9k| if(prefix == NULL) { ------------------ | Branch (226:10): [True: 15.9k, False: 0] ------------------ 227| 15.9k|#ifndef NT 228| 15.9k| prefix = (ndpi_prefix_t*)ndpi_calloc(1, sizeof (prefix4_t)); 229| |#else 230| | //for some reason, compiler is getting 231| | //prefix4_t size incorrect on NT 232| | prefix = ndpi_calloc(1, sizeof (ndpi_prefix_t)); 233| |#endif /* NT */ 234| 15.9k| if(!prefix) ------------------ | Branch (234:5): [True: 957, False: 14.9k] ------------------ 235| 957| return (NULL); 236| | 237| 14.9k| dynamic_allocated++; 238| 14.9k| } 239| 14.9k| memcpy (&prefix->add.sin, dest, sizeof(struct in_addr)); 240| 14.9k| } 241| 0| else if(family == AF_MAC) { ------------------ | | 2067| 0|#define AF_MAC 99 ------------------ | Branch (241:13): [True: 0, False: 0] ------------------ 242| 0| default_bitlen = 48; 243| 0| if(prefix == NULL) { ------------------ | Branch (243:10): [True: 0, False: 0] ------------------ 244| 0| prefix = (ndpi_prefix_t*)ndpi_calloc(1, sizeof (ndpi_prefix_t)); 245| 0| if(!prefix) ------------------ | Branch (245:12): [True: 0, False: 0] ------------------ 246| 0| return (NULL); 247| 0| dynamic_allocated++; 248| 0| } 249| 0| memcpy (prefix->add.mac, dest, 6); 250| 0| } 251| 0| else { 252| 0| return (NULL); 253| 0| } 254| | 255| 25.1k| prefix->bitlen = (u_int16_t)((bitlen >= 0) ? bitlen : default_bitlen); ------------------ | Branch (255:32): [True: 25.1k, False: 0] ------------------ 256| 25.1k| prefix->family = (u_int16_t)family; 257| 25.1k| prefix->ref_count = 0; 258| 25.1k| if(dynamic_allocated) { ------------------ | Branch (258:6): [True: 25.1k, False: 0] ------------------ 259| 25.1k| prefix->ref_count++; 260| 25.1k| } 261| | /* fprintf(stderr, "[C %s, %d]\n", ndpi_prefix_toa (prefix), prefix->ref_count); */ 262| 25.1k| return (prefix); 263| 27.1k|}