fuzz_set_alloc_callbacks: 31| 657|{ 32| 657| ndpi_set_memory_alloction_functions(malloc_wrapper, 33| 657| free_wrapper, 34| 657| calloc_wrapper, 35| 657| 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| 657| NULL, NULL, 40| 657| malloc_wrapper, 41| 657| free_wrapper); 42| 657|} fuzz_set_alloc_seed: 44| 657|{ 45| 657| mem_alloc_state = seed; 46| 657|} fuzz_set_alloc_callbacks_and_seed: 48| 657|{ 49| 657| fuzz_set_alloc_callbacks(); 50| 657| fuzz_set_alloc_seed(seed); 51| 657|} fuzz_common_code.c:fastrand: 11| 119k|{ 12| 119k| if(!mem_alloc_state) return 1; /* No failures */ ------------------ | Branch (12:6): [True: 0, False: 119k] ------------------ 13| 119k| mem_alloc_state = (214013 * mem_alloc_state + 2531011); 14| 119k| return (mem_alloc_state >> 16) & 0x7FFF; 15| 119k|} fuzz_common_code.c:free_wrapper: 20| 111k|static void free_wrapper(void *freeable) { 21| 111k| free(freeable); 22| 111k|} fuzz_common_code.c:calloc_wrapper: 23| 119k|static void *calloc_wrapper(size_t nmemb, size_t size) { 24| 119k| return (fastrand () % 16) ? calloc (nmemb, size) : NULL; ------------------ | Branch (24:10): [True: 111k, False: 8.09k] ------------------ 25| 119k|} LLVMFuzzerTestOneInput: 18| 675|extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { 19| 675| FuzzedDataProvider fuzzed_data(data, size); 20| 675| u_int16_t i, num_iteration, ip_len; 21| 675| ndpi_patricia_tree_t *p, *p_cloned; 22| 675| u_int16_t maxbits; 23| 675| int is_added = 0; 24| 675| ndpi_prefix_t prefix, prefix_added; 25| 675| u_char *ip; 26| 675| ndpi_patricia_node_t *node; 27| 675| int tree_type; /* 0: ipv4, 1: ipv6, 2: mac */ 28| | 29| | /* Just to have some data */ 30| 675| if (fuzzed_data.remaining_bytes() < 1024) ------------------ | Branch (30:7): [True: 18, False: 657] ------------------ 31| 18| return -1; 32| | 33| | /* To allow memory allocation failures */ 34| 657| fuzz_set_alloc_callbacks_and_seed(size); 35| | 36| 657| tree_type = fuzzed_data.ConsumeIntegralInRange(0, 2); 37| 657| if (tree_type == 0) ------------------ | Branch (37:7): [True: 238, False: 419] ------------------ 38| 238| maxbits = 32; 39| 419| else if (tree_type == 1) ------------------ | Branch (39:12): [True: 223, False: 196] ------------------ 40| 223| maxbits = 128; 41| 196| else 42| 196| maxbits = 48; 43| | 44| 657| p = ndpi_patricia_new(maxbits); 45| | 46| 657| ndpi_patricia_get_maxbits(p); 47| 657| ndpi_patricia_process(p, process_ptree_data); 48| 657| ndpi_patricia_walk_tree_inorder(p, process3_ptree_data, NULL); 49| | 50| | /* "Random" add */ 51| 657| num_iteration = fuzzed_data.ConsumeIntegral(); 52| 65.5k| for (i = 0; i < num_iteration; i++) { ------------------ | Branch (52:15): [True: 64.8k, False: 657] ------------------ 53| 64.8k| if (tree_type == 0) { ------------------ | Branch (53:9): [True: 27.7k, False: 37.0k] ------------------ 54| 27.7k| if(fuzzed_data.remaining_bytes() > 4) { ------------------ | Branch (54:10): [True: 26.4k, False: 1.36k] ------------------ 55| 26.4k| std::vectordata = fuzzed_data.ConsumeBytes(4); 56| 26.4k| ip = data.data(); 57| 26.4k| ip_len = fuzzed_data.ConsumeIntegralInRange(0, 33); /* 33 to force error */ 58| 26.4k| ndpi_fill_prefix_v4(&prefix, (struct in_addr *)ip, ip_len, 32); 59| 26.4k| node = ndpi_patricia_lookup(p, &prefix); 60| | /* Keep one random node really added */ 61| 26.4k| if (node && is_added == 0 && fuzzed_data.ConsumeBool()) { ------------------ | Branch (61:6): [True: 21.1k, False: 5.26k] | Branch (61:14): [True: 901, False: 20.2k] | Branch (61:31): [True: 166, False: 735] ------------------ 62| 166| is_added = 1; 63| 166| prefix_added = prefix; 64| | /* Some random operations on this node */ 65| 166| ndpi_patricia_get_node_prefix(node); 66| 166| ndpi_patricia_get_node_bits(node); 67| 166| ndpi_patricia_set_node_data(node, NULL); 68| 166| assert(ndpi_patricia_get_node_data(node) == NULL); ------------------ | Branch (68:11): [True: 166, False: 0] ------------------ 69| 166| ndpi_patricia_set_node_u64(node, 0); 70| 166| assert(ndpi_patricia_get_node_u64(node) == 0); ------------------ | Branch (70:11): [True: 166, False: 0] ------------------ 71| 166| } 72| 26.4k| } 73| 37.0k| } else if (tree_type == 1){ ------------------ | Branch (73:16): [True: 21.3k, False: 15.7k] ------------------ 74| 21.3k| if(fuzzed_data.remaining_bytes() > 16) { ------------------ | Branch (74:10): [True: 14.7k, False: 6.57k] ------------------ 75| 14.7k| std::vectordata = fuzzed_data.ConsumeBytes(16); 76| 14.7k| ip = data.data(); 77| 14.7k| ip_len = fuzzed_data.ConsumeIntegralInRange(0, 129); /* 129 to force error */ 78| 14.7k| ndpi_fill_prefix_v6(&prefix, (const struct in6_addr *)ip, ip_len, 128); 79| 14.7k| node = ndpi_patricia_lookup(p, &prefix); 80| | /* Keep one random node really added */ 81| 14.7k| if (node && is_added == 0 && fuzzed_data.ConsumeBool()) { ------------------ | Branch (81:6): [True: 12.6k, False: 2.14k] | Branch (81:14): [True: 1.13k, False: 11.5k] | Branch (81:31): [True: 154, False: 984] ------------------ 82| 154| is_added = 1; 83| 154| prefix_added = prefix; 84| | /* Some random operations on this node */ 85| 154| ndpi_patricia_get_node_prefix(node); 86| 154| ndpi_patricia_get_node_bits(node); 87| 154| ndpi_patricia_set_node_data(node, NULL); 88| 154| assert(ndpi_patricia_get_node_data(node) == NULL); ------------------ | Branch (88:11): [True: 154, False: 0] ------------------ 89| 154| ndpi_patricia_set_node_u64(node, 0); 90| 154| assert(ndpi_patricia_get_node_u64(node) == 0); ------------------ | Branch (90:11): [True: 154, False: 0] ------------------ 91| 154| } 92| 14.7k| } 93| 21.3k| } else { 94| 15.7k| if(fuzzed_data.remaining_bytes() > 6) { ------------------ | Branch (94:10): [True: 13.6k, False: 2.05k] ------------------ 95| 13.6k| std::vectordata = fuzzed_data.ConsumeBytes(6); 96| 13.6k| ip = data.data(); 97| 13.6k| ip_len = fuzzed_data.ConsumeIntegralInRange(0, 49); /* 49 to force error */ 98| 13.6k| ndpi_fill_prefix_mac(&prefix, ip, ip_len, 48); 99| 13.6k| node = ndpi_patricia_lookup(p, &prefix); 100| | /* Keep one random node really added */ 101| 13.6k| if (node && is_added == 0 && fuzzed_data.ConsumeBool()) { ------------------ | Branch (101:6): [True: 10.6k, False: 3.03k] | Branch (101:14): [True: 1.73k, False: 8.88k] | Branch (101:31): [True: 104, False: 1.62k] ------------------ 102| 104| is_added = 1; 103| 104| prefix_added = prefix; 104| | /* Some random operations on this node */ 105| 104| ndpi_patricia_get_node_prefix(node); 106| 104| ndpi_patricia_get_node_bits(node); 107| 104| ndpi_patricia_set_node_data(node, NULL); 108| 104| assert(ndpi_patricia_get_node_data(node) == NULL); ------------------ | Branch (108:11): [True: 104, False: 0] ------------------ 109| 104| ndpi_patricia_set_node_u64(node, 0); 110| 104| assert(ndpi_patricia_get_node_u64(node) == 0); ------------------ | Branch (110:11): [True: 104, False: 0] ------------------ 111| 104| } 112| 13.6k| } 113| 15.7k| } 114| 64.8k| } 115| | 116| 657| ndpi_patricia_process(p, process_ptree_data); 117| 657| ndpi_patricia_walk_tree_inorder(p, process3_ptree_data, NULL); 118| | 119| | /* "Random" exact search. Remove if found */ 120| 657| num_iteration = fuzzed_data.ConsumeIntegral(); 121| 53.3k| for (i = 0; i < num_iteration; i++) { ------------------ | Branch (121:15): [True: 52.6k, False: 657] ------------------ 122| 52.6k| if (tree_type == 0) { ------------------ | Branch (122:9): [True: 19.8k, False: 32.8k] ------------------ 123| 19.8k| if(fuzzed_data.remaining_bytes() > 4) { ------------------ | Branch (123:10): [True: 14.1k, False: 5.67k] ------------------ 124| 14.1k| std::vectordata = fuzzed_data.ConsumeBytes(4); 125| 14.1k| ip = data.data(); 126| 14.1k| ip_len = fuzzed_data.ConsumeIntegralInRange(0, 32); 127| 14.1k| ndpi_fill_prefix_v4(&prefix, (struct in_addr *)ip, ip_len, 32); 128| 14.1k| node = ndpi_patricia_search_exact(p, &prefix); 129| 14.1k| if (node) ------------------ | Branch (129:6): [True: 890, False: 13.2k] ------------------ 130| 890| ndpi_patricia_remove(p, node); 131| 14.1k| } 132| 32.8k| } else if (tree_type == 1) { ------------------ | Branch (132:16): [True: 17.9k, False: 14.8k] ------------------ 133| 17.9k| if(fuzzed_data.remaining_bytes() > 16) { ------------------ | Branch (133:10): [True: 10.2k, False: 7.71k] ------------------ 134| 10.2k| std::vectordata = fuzzed_data.ConsumeBytes(16); 135| 10.2k| ip = data.data(); 136| 10.2k| ip_len = fuzzed_data.ConsumeIntegralInRange(0, 128); 137| 10.2k| ndpi_fill_prefix_v6(&prefix, (const struct in6_addr *)ip, ip_len, 128); 138| 10.2k| node = ndpi_patricia_search_exact(p, &prefix); 139| 10.2k| if (node) ------------------ | Branch (139:6): [True: 531, False: 9.73k] ------------------ 140| 531| ndpi_patricia_remove(p, node); 141| 10.2k| } 142| 17.9k| } else { 143| 14.8k| if(fuzzed_data.remaining_bytes() > 6) { ------------------ | Branch (143:10): [True: 10.1k, False: 4.74k] ------------------ 144| 10.1k| std::vectordata = fuzzed_data.ConsumeBytes(6); 145| 10.1k| ip = data.data(); 146| 10.1k| ip_len = fuzzed_data.ConsumeIntegralInRange(0, 48); 147| 10.1k| ndpi_fill_prefix_mac(&prefix, ip, ip_len, 48); 148| 10.1k| node = ndpi_patricia_search_exact(p, &prefix); 149| 10.1k| if (node) ------------------ | Branch (149:6): [True: 535, False: 9.60k] ------------------ 150| 535| ndpi_patricia_remove(p, node); 151| 10.1k| } 152| 14.8k| } 153| | 154| 52.6k| } 155| | /* Exact search of an added node */ 156| 657| if (is_added) ------------------ | Branch (156:7): [True: 424, False: 233] ------------------ 157| 424| ndpi_patricia_search_exact(p, &prefix_added); 158| | 159| | /* "Random" best search. Remove if found */ 160| 657| num_iteration = fuzzed_data.ConsumeIntegral(); 161| 59.7k| for (i = 0; i < num_iteration; i++) { ------------------ | Branch (161:15): [True: 59.0k, False: 657] ------------------ 162| 59.0k| if (tree_type == 0) { ------------------ | Branch (162:9): [True: 20.8k, False: 38.1k] ------------------ 163| 20.8k| if(fuzzed_data.remaining_bytes() > 4) { ------------------ | Branch (163:10): [True: 13.1k, False: 7.75k] ------------------ 164| 13.1k| std::vectordata = fuzzed_data.ConsumeBytes(4); 165| 13.1k| ip = data.data(); 166| 13.1k| ip_len = fuzzed_data.ConsumeIntegralInRange(0, 32); 167| 13.1k| ndpi_fill_prefix_v4(&prefix, (struct in_addr *)ip, ip_len, 32); 168| 13.1k| node = ndpi_patricia_search_best(p, &prefix); 169| 13.1k| if (node) ------------------ | Branch (169:6): [True: 1.56k, False: 11.5k] ------------------ 170| 1.56k| ndpi_patricia_remove(p, node); 171| 13.1k| } 172| 38.1k| } else if (tree_type == 1) { ------------------ | Branch (172:16): [True: 19.8k, False: 18.3k] ------------------ 173| 19.8k| if(fuzzed_data.remaining_bytes() > 16) { ------------------ | Branch (173:10): [True: 9.70k, False: 10.1k] ------------------ 174| 9.70k| std::vectordata = fuzzed_data.ConsumeBytes(16); 175| 9.70k| ip = data.data(); 176| 9.70k| ip_len = fuzzed_data.ConsumeIntegralInRange(0, 128); 177| 9.70k| ndpi_fill_prefix_v6(&prefix, (const struct in6_addr *)ip, ip_len, 128); 178| 9.70k| node = ndpi_patricia_search_best(p, &prefix); 179| 9.70k| if (node) ------------------ | Branch (179:6): [True: 1.55k, False: 8.14k] ------------------ 180| 1.55k| ndpi_patricia_remove(p, node); 181| 9.70k| } 182| 19.8k| } else { 183| 18.3k| if(fuzzed_data.remaining_bytes() > 6) { ------------------ | Branch (183:10): [True: 11.6k, False: 6.74k] ------------------ 184| 11.6k| std::vectordata = fuzzed_data.ConsumeBytes(6); 185| 11.6k| ip = data.data(); 186| 11.6k| ip_len = fuzzed_data.ConsumeIntegralInRange(0, 48); 187| 11.6k| ndpi_fill_prefix_mac(&prefix, ip, ip_len, 48); 188| 11.6k| node = ndpi_patricia_search_best(p, &prefix); 189| 11.6k| if (node) ------------------ | Branch (189:6): [True: 819, False: 10.7k] ------------------ 190| 819| ndpi_patricia_remove(p, node); 191| 11.6k| } 192| 18.3k| } 193| 59.0k| } 194| | /* Best search of an added node */ 195| 657| if (is_added) ------------------ | Branch (195:7): [True: 424, False: 233] ------------------ 196| 424| ndpi_patricia_search_best(p, &prefix_added); 197| | 198| 657| p_cloned = ndpi_patricia_clone(p); 199| | 200| 657| ndpi_patricia_process(p_cloned, process_ptree_data); 201| 657| ndpi_patricia_walk_tree_inorder(p_cloned, process3_ptree_data, NULL); 202| | 203| | 204| 657| ndpi_patricia_destroy(p, NULL); 205| 657| ndpi_patricia_destroy(p_cloned, NULL); 206| | 207| 657| return 0; 208| 657|} fuzz_ds_patricia.cpp:_ZL18process_ptree_dataP14_ndpi_prefix_tPv: 9| 47.9k|static void process_ptree_data(ndpi_prefix_t *prefix, void *data) { 10| | /* Nothing to do */ 11| | assert(prefix && data == NULL); ------------------ | Branch (11:3): [True: 47.9k, False: 0] | Branch (11:3): [True: 47.9k, False: 0] | Branch (11:3): [True: 47.9k, False: 0] ------------------ 12| 47.9k|} fuzz_ds_patricia.cpp:_ZL19process3_ptree_dataP21_ndpi_patricia_node_tPvS1_: 13| 47.9k|static void process3_ptree_data(ndpi_patricia_node_t *node, void *data, void *user_data) { 14| | /* Nothing to do */ 15| | assert(node && data == NULL && user_data == NULL); ------------------ | Branch (15:3): [True: 47.9k, False: 0] | Branch (15:3): [True: 47.9k, False: 0] | Branch (15:3): [True: 47.9k, False: 0] | Branch (15:3): [True: 47.9k, False: 0] ------------------ 16| 47.9k|} ndpi_patricia_get_maxbits: 3100| 657|u_int16_t ndpi_patricia_get_maxbits(ndpi_patricia_tree_t *tree) { 3101| 657| if(!tree) ------------------ | Branch (3101:6): [True: 34, False: 623] ------------------ 3102| 34| return 0; 3103| 623| return(tree->maxbits); 3104| 657|} ndpi_fill_prefix_v4: 3182| 53.6k|int ndpi_fill_prefix_v4(ndpi_prefix_t *p, const struct in_addr *a, int b, int mb) { 3183| 53.6k| memset(p, 0, sizeof(ndpi_prefix_t)); 3184| | 3185| 53.6k| if(b < 0 || b > mb) ------------------ | Branch (3185:6): [True: 0, False: 53.6k] | Branch (3185:15): [True: 2.57k, False: 51.1k] ------------------ 3186| 2.57k| return(-1); 3187| | 3188| 51.1k| p->add.sin.s_addr = a->s_addr, p->family = AF_INET, p->bitlen = b, p->ref_count = 0; 3189| | 3190| 51.1k| return(0); 3191| 53.6k|} ndpi_fill_prefix_v6: 3195| 34.7k|int ndpi_fill_prefix_v6(ndpi_prefix_t *prefix, const struct in6_addr *addr, int bits, int maxbits) { 3196| 34.7k| memset(prefix, 0, sizeof(ndpi_prefix_t)); 3197| | 3198| 34.7k| if(bits < 0 || bits > maxbits) ------------------ | Branch (3198:6): [True: 0, False: 34.7k] | Branch (3198:18): [True: 603, False: 34.1k] ------------------ 3199| 603| return -1; 3200| | 3201| 34.1k| memcpy(&prefix->add.sin6, addr, (maxbits + 7) / 8); 3202| 34.1k| prefix->family = AF_INET6, prefix->bitlen = bits, prefix->ref_count = 0; 3203| | 3204| 34.1k| return 0; 3205| 34.7k|} ndpi_fill_prefix_mac: 3209| 35.4k|int ndpi_fill_prefix_mac(ndpi_prefix_t *prefix, u_int8_t *mac, int bits, int maxbits) { 3210| 35.4k| memset(prefix, 0, sizeof(ndpi_prefix_t)); 3211| | 3212| 35.4k| if(bits < 0 || bits > maxbits) ------------------ | Branch (3212:6): [True: 0, False: 35.4k] | Branch (3212:18): [True: 1.19k, False: 34.2k] ------------------ 3213| 1.19k| return -1; 3214| | 3215| 34.2k| memcpy(prefix->add.mac, mac, 6); 3216| 34.2k| prefix->family = AF_MAC, prefix->bitlen = bits, prefix->ref_count = 0; ------------------ | | 2067| 34.2k|#define AF_MAC 99 ------------------ 3217| | 3218| 34.2k| return 0; 3219| 35.4k|} ndpi_patricia_get_node_prefix: 3223| 424|ndpi_prefix_t *ndpi_patricia_get_node_prefix(ndpi_patricia_node_t *node) { 3224| 424| return(node->prefix); 3225| 424|} ndpi_patricia_get_node_bits: 3229| 424|u_int16_t ndpi_patricia_get_node_bits(ndpi_patricia_node_t *node) { 3230| 424| return(node->bit); 3231| 424|} ndpi_patricia_set_node_data: 3235| 424|void ndpi_patricia_set_node_data(ndpi_patricia_node_t *node, void *data) { 3236| 424| node->data = data; 3237| 424|} ndpi_patricia_get_node_data: 3241| 424|void *ndpi_patricia_get_node_data(ndpi_patricia_node_t *node) { 3242| 424| return(node->data); 3243| 424|} ndpi_patricia_set_node_u64: 3247| 424|void ndpi_patricia_set_node_u64(ndpi_patricia_node_t *node, u_int64_t value) { 3248| 424| node->value.u.uv64 = value; 3249| 424|} ndpi_patricia_get_node_u64: 3253| 424|u_int64_t ndpi_patricia_get_node_u64(ndpi_patricia_node_t *node) { 3254| 424| return(node->value.u.uv64); 3255| 424|} ndpi_set_memory_alloction_functions: 52| 657| void (*__ndpi_flow_free)(void *ptr)) { 53| | 54| | /* We can't log here */ 55| | 56| 657| if(__ndpi_malloc && __ndpi_free && ------------------ | Branch (56:6): [True: 657, False: 0] | Branch (56:23): [True: 657, False: 0] ------------------ 57| 657| __ndpi_calloc && __ndpi_realloc) { ------------------ | Branch (57:6): [True: 657, False: 0] | Branch (57:23): [True: 657, False: 0] ------------------ 58| 657| _ndpi_malloc = __ndpi_malloc; 59| 657| _ndpi_free = __ndpi_free; 60| 657| _ndpi_calloc = __ndpi_calloc; 61| 657| _ndpi_realloc = __ndpi_realloc; 62| 657| } 63| 657| if(__ndpi_aligned_malloc && __ndpi_aligned_free) { ------------------ | Branch (63:6): [True: 0, False: 657] | 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| 657| if(__ndpi_flow_malloc && __ndpi_flow_free) { ------------------ | Branch (67:6): [True: 657, False: 0] | Branch (67:28): [True: 657, False: 0] ------------------ 68| 657| _ndpi_flow_malloc = __ndpi_flow_malloc; 69| 657| _ndpi_flow_free = __ndpi_flow_free; 70| 657| } 71| 657|} ndpi_calloc: 88| 119k|void *ndpi_calloc(size_t nmemb, size_t size) { 89| 119k| __sync_fetch_and_add(&ndpi_tot_allocated_memory, nmemb * size); 90| 119k| return(_ndpi_calloc ? _ndpi_calloc(nmemb, size) : calloc(nmemb, size)); ------------------ | Branch (90:10): [True: 119k, False: 0] ------------------ 91| 119k|} ndpi_free: 95| 111k|void ndpi_free(void *ptr) { 96| 111k| _ndpi_free ? _ndpi_free(ptr) : free(ptr); ------------------ | Branch (96:3): [True: 111k, False: 0] ------------------ 97| 111k|} ndpi_patricia_new: 310| 1.28k|{ 311| 1.28k| ndpi_patricia_tree_t *patricia = (ndpi_patricia_tree_t*)ndpi_calloc(1, sizeof *patricia); 312| 1.28k| if(!patricia) ------------------ | Branch (312:6): [True: 72, False: 1.20k] ------------------ 313| 72| return (NULL); 314| | 315| 1.20k| patricia->maxbits = maxbits; 316| 1.20k| patricia->head = NULL; 317| 1.20k| patricia->num_active_node = 0; 318| 1.20k| assert((u_int16_t)maxbits <= PATRICIA_MAXBITS); /* XXX */ ------------------ | Branch (318:3): [True: 0, False: 1.20k] | Branch (318:3): [True: 1.20k, False: 0] ------------------ 319| 1.20k| num_active_patricia++; 320| 1.20k| return (patricia); 321| 1.20k|} ndpi_Clear_Patricia: 330| 1.31k|{ 331| 1.31k| if(!patricia) ------------------ | Branch (331:6): [True: 106, False: 1.20k] ------------------ 332| 106| return; 333| | 334| 1.20k| if(patricia->head) { ------------------ | Branch (334:6): [True: 859, False: 349] ------------------ 335| | 336| 859| ndpi_patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; 337| 859| ndpi_patricia_node_t **Xsp = Xstack; 338| 859| ndpi_patricia_node_t *Xrn = patricia->head; 339| | 340| 67.8k| while (Xrn) { ------------------ | Branch (340:12): [True: 67.0k, False: 859] ------------------ 341| 67.0k| ndpi_patricia_node_t *l = Xrn->l; 342| 67.0k| ndpi_patricia_node_t *r = Xrn->r; 343| | 344| 67.0k| if(Xrn->prefix) { ------------------ | Branch (344:10): [True: 42.0k, False: 24.9k] ------------------ 345| 42.0k| ndpi_Deref_Prefix (Xrn->prefix); 346| 42.0k| if(Xrn->data && func) ------------------ | Branch (346:5): [True: 0, False: 42.0k] | Branch (346:18): [True: 0, False: 0] ------------------ 347| 0| func (Xrn->data); 348| 42.0k| } 349| 24.9k| else { 350| 24.9k| assert (Xrn->data == NULL); ------------------ | Branch (350:2): [True: 0, False: 24.9k] | Branch (350:2): [True: 24.9k, False: 0] ------------------ 351| 24.9k| } 352| 67.0k| ndpi_DeleteEntry (Xrn); 353| 67.0k| patricia->num_active_node--; 354| | 355| 67.0k| if(l) { ------------------ | Branch (355:10): [True: 34.1k, False: 32.8k] ------------------ 356| 34.1k| if(r) { ------------------ | Branch (356:5): [True: 27.7k, False: 6.35k] ------------------ 357| 27.7k| *Xsp++ = r; 358| 27.7k| } 359| 34.1k| Xrn = l; 360| 34.1k| } else if(r) { ------------------ | Branch (360:17): [True: 4.26k, False: 28.6k] ------------------ 361| 4.26k| Xrn = r; 362| 28.6k| } else if(Xsp != Xstack) { ------------------ | Branch (362:17): [True: 27.7k, False: 859] ------------------ 363| 27.7k| Xrn = *(--Xsp); 364| 27.7k| } else { 365| 859| Xrn = NULL; 366| 859| } 367| 67.0k| } 368| 859| } 369| 1.20k| assert (patricia->num_active_node == 0); ------------------ | Branch (369:3): [True: 0, False: 1.20k] | Branch (369:3): [True: 1.20k, False: 0] ------------------ 370| | /* ndpi_DeleteEntry (patricia); */ 371| 1.20k|} ndpi_patricia_destroy: 375| 1.31k|{ 376| 1.31k| ndpi_Clear_Patricia (patricia, func); 377| 1.31k| ndpi_DeleteEntry (patricia); 378| 1.31k| num_active_patricia--; 379| 1.31k|} ndpi_patricia_process: 387| 1.97k|{ 388| 1.97k| ndpi_patricia_node_t *node; 389| | 390| 1.97k| if (!patricia) ------------------ | Branch (390:7): [True: 140, False: 1.83k] ------------------ 391| 140| return; 392| 1.97k| assert (func); ------------------ | Branch (392:3): [True: 0, False: 1.83k] | Branch (392:3): [True: 1.83k, False: 0] ------------------ 393| | 394| 75.6k| PATRICIA_WALK (patricia->head, node) { ------------------ | | 103| 1.83k| do { \ | | 104| 1.83k| ndpi_patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \ | | 105| 1.83k| ndpi_patricia_node_t **Xsp = Xstack; \ | | 106| 1.83k| ndpi_patricia_node_t *Xrn = (Xhead); \ | | 107| 75.6k| while ((Xnode = Xrn)) { \ | | ------------------ | | | Branch (107:12): [True: 73.7k, False: 1.83k] | | ------------------ | | 108| 73.7k| if (Xnode->prefix) | | ------------------ | | | Branch (108:11): [True: 47.9k, False: 25.8k] | | ------------------ ------------------ 395| 47.9k| func (node->prefix, node->data); 396| 73.7k| } PATRICIA_WALK_END; ------------------ | | 127| 73.7k| if (Xrn->l) { \ | | ------------------ | | | Branch (127:7): [True: 37.5k, False: 36.2k] | | ------------------ | | 128| 37.5k| if (Xrn->r) { \ | | ------------------ | | | Branch (128:9): [True: 29.6k, False: 7.84k] | | ------------------ | | 129| 29.6k| *Xsp++ = Xrn->r; \ | | 130| 29.6k| } \ | | 131| 37.5k| Xrn = Xrn->l; \ | | 132| 37.5k| } else if (Xrn->r) { \ | | ------------------ | | | Branch (132:14): [True: 5.73k, False: 30.5k] | | ------------------ | | 133| 5.73k| Xrn = Xrn->r; \ | | 134| 30.5k| } else if (Xsp != Xstack) { \ | | ------------------ | | | Branch (134:14): [True: 29.6k, False: 878] | | ------------------ | | 135| 29.6k| Xrn = *(--Xsp); \ | | 136| 29.6k| } else { \ | | 137| 878| Xrn = (ndpi_patricia_node_t *) 0; \ | | 138| 878| } \ | | 139| 73.7k| } \ | | 140| 1.83k| } while (0) | | ------------------ | | | Branch (140:14): [Folded, False: 1.83k] | | ------------------ ------------------ 397| 1.83k|} ndpi_patricia_clone: 429| 657|{ 430| 657| if(!from) return (NULL); ------------------ | Branch (430:6): [True: 34, False: 623] ------------------ 431| | 432| 623| ndpi_patricia_tree_t *patricia = ndpi_patricia_new(from->maxbits); 433| | 434| 623| if(!patricia) return (NULL); ------------------ | Branch (434:6): [True: 38, False: 585] ------------------ 435| | 436| 585| if(from->head) ------------------ | Branch (436:6): [True: 415, False: 170] ------------------ 437| 415| ndpi_patricia_clone_walk(from->head, patricia); 438| | 439| 585| return (patricia); 440| 623|} ndpi_patricia_walk_inorder: 444| 73.7k|{ 445| 73.7k| size_t n = 0; 446| 73.7k| assert(func); ------------------ | Branch (446:3): [True: 0, False: 73.7k] | Branch (446:3): [True: 73.7k, False: 0] ------------------ 447| | 448| 73.7k| if(node->l) { ------------------ | Branch (448:6): [True: 37.5k, False: 36.2k] ------------------ 449| 37.5k| n += ndpi_patricia_walk_inorder(node->l, func, data); 450| 37.5k| } 451| | 452| 73.7k| if(node->prefix) { ------------------ | Branch (452:6): [True: 47.9k, False: 25.8k] ------------------ 453| 47.9k| func(node, node->data, data); 454| 47.9k| n++; 455| 47.9k| } 456| | 457| 73.7k| if(node->r) { ------------------ | Branch (457:6): [True: 35.4k, False: 38.3k] ------------------ 458| 35.4k| n += ndpi_patricia_walk_inorder(node->r, func, data); 459| 35.4k| } 460| | 461| 73.7k| return n; 462| 73.7k|} ndpi_patricia_walk_tree_inorder: 465| 1.97k|ndpi_patricia_walk_tree_inorder(ndpi_patricia_tree_t *patricia, ndpi_void_fn3_t func, void *data) { 466| 1.97k| if (patricia == NULL || patricia->head == NULL) ------------------ | Branch (466:7): [True: 140, False: 1.83k] | Branch (466:27): [True: 953, False: 878] ------------------ 467| 1.09k| return 0; 468| | 469| 878| return ndpi_patricia_walk_inorder(patricia->head, func, data); 470| 1.97k|} ndpi_patricia_search_exact: 474| 34.9k|{ 475| 34.9k| ndpi_patricia_node_t *node; 476| 34.9k| u_char *addr; 477| 34.9k| u_int16_t bitlen; 478| | 479| 34.9k| if (!patricia) ------------------ | Branch (479:7): [True: 2.65k, False: 32.3k] ------------------ 480| 2.65k| return (NULL); 481| 34.9k| assert (prefix); ------------------ | Branch (481:3): [True: 0, False: 32.3k] | Branch (481:3): [True: 32.3k, False: 0] ------------------ 482| 32.3k| assert (prefix->bitlen <= patricia->maxbits); ------------------ | Branch (482:3): [True: 0, False: 32.3k] | Branch (482:3): [True: 32.3k, False: 0] ------------------ 483| | 484| 32.3k| patricia->stats.n_search++; 485| | 486| 32.3k| if(patricia->head == NULL) ------------------ | Branch (486:6): [True: 9.40k, False: 22.9k] ------------------ 487| 9.40k| return (NULL); 488| | 489| 22.9k| node = patricia->head; 490| 22.9k| addr = ndpi_prefix_touchar (prefix); ------------------ | | 50| 22.9k|#define ndpi_prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin) ------------------ 491| 22.9k| bitlen = prefix->bitlen; 492| | 493| 149k| while (node->bit < bitlen) { ------------------ | Branch (493:10): [True: 134k, False: 15.7k] ------------------ 494| | 495| 134k| if(BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) { ------------------ | | 54| 134k|#define BIT_TEST(f, b) ((f) & (b)) | | ------------------ | | | Branch (54:25): [True: 39.9k, False: 94.1k] | | ------------------ ------------------ 496| |#ifdef PATRICIA_DEBUG 497| | if(node->prefix) 498| | fprintf (stderr, "patricia_search_exact: take right %s/%d\n", 499| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 500| | else 501| | fprintf (stderr, "patricia_search_exact: take right at %u\n", 502| | node->bit); 503| |#endif /* PATRICIA_DEBUG */ 504| 39.9k| node = node->r; 505| 39.9k| } 506| 94.1k| else { 507| |#ifdef PATRICIA_DEBUG 508| | if(node->prefix) 509| | fprintf (stderr, "patricia_search_exact: take left %s/%d\n", 510| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 511| | else 512| | fprintf (stderr, "patricia_search_exact: take left at %u\n", 513| | node->bit); 514| |#endif /* PATRICIA_DEBUG */ 515| 94.1k| node = node->l; 516| 94.1k| } 517| | 518| 134k| if(node == NULL) ------------------ | Branch (518:8): [True: 7.17k, False: 126k] ------------------ 519| 7.17k| return (NULL); 520| 134k| } 521| | 522| |#ifdef PATRICIA_DEBUG 523| | if(node->prefix) 524| | fprintf (stderr, "patricia_search_exact: stop at %s/%d [node->bit: %u][bitlen: %u]\n", 525| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen, node->bit, bitlen); 526| | else 527| | fprintf (stderr, "patricia_search_exact: stop at %u\n", node->bit); 528| |#endif /* PATRICIA_DEBUG */ 529| | 530| 15.7k| if(node->bit > bitlen || node->prefix == NULL) ------------------ | Branch (530:6): [True: 8.66k, False: 7.09k] | Branch (530:28): [True: 2.93k, False: 4.15k] ------------------ 531| 11.5k| return (NULL); 532| | 533| 15.7k| assert (node->bit == bitlen); ------------------ | Branch (533:3): [True: 0, False: 4.15k] | Branch (533:3): [True: 4.15k, False: 0] ------------------ 534| 4.15k| assert (node->bit == node->prefix->bitlen); ------------------ | Branch (534:3): [True: 0, False: 4.15k] | Branch (534:3): [True: 4.15k, False: 0] ------------------ 535| 4.15k| if(ndpi_comp_with_mask (ndpi_prefix_tochar (node->prefix), ndpi_prefix_tochar (prefix), ------------------ | Branch (535:6): [True: 2.32k, False: 1.83k] ------------------ 536| 4.15k| bitlen)) { 537| |#ifdef PATRICIA_DEBUG 538| | fprintf (stderr, "patricia_search_exact: found %s/%d\n", 539| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 540| |#endif /* PATRICIA_DEBUG */ 541| 2.32k| patricia->stats.n_found++; 542| 2.32k| return (node); 543| 2.32k| } 544| 1.83k| return (NULL); 545| 4.15k|} ndpi_patricia_search_best2: 551| 34.8k|{ 552| 34.8k| ndpi_patricia_node_t *node; 553| 34.8k| ndpi_patricia_node_t *stack[PATRICIA_MAXBITS + 1]; 554| 34.8k| u_char *addr; 555| 34.8k| u_int16_t bitlen; 556| 34.8k| int cnt = 0; 557| | 558| 34.8k| if(patricia == NULL) ------------------ | Branch (558:6): [True: 2.06k, False: 32.7k] ------------------ 559| 2.06k| return (NULL); 560| | 561| 34.8k| assert (prefix); ------------------ | Branch (561:3): [True: 0, False: 32.7k] | Branch (561:3): [True: 32.7k, False: 0] ------------------ 562| 32.7k| assert (prefix->bitlen <= patricia->maxbits); ------------------ | Branch (562:3): [True: 0, False: 32.7k] | Branch (562:3): [True: 32.7k, False: 0] ------------------ 563| | 564| 32.7k| patricia->stats.n_search++; 565| | 566| 32.7k| if(patricia->head == NULL) ------------------ | Branch (566:6): [True: 14.6k, False: 18.1k] ------------------ 567| 14.6k| return (NULL); 568| | 569| 18.1k| node = patricia->head; 570| 18.1k| addr = ndpi_prefix_touchar (prefix); ------------------ | | 50| 18.1k|#define ndpi_prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin) ------------------ 571| 18.1k| bitlen = prefix->bitlen; 572| | 573| 116k| while (node->bit < bitlen) { ------------------ | Branch (573:10): [True: 105k, False: 11.4k] ------------------ 574| 105k| if(node->prefix) { ------------------ | Branch (574:8): [True: 39.8k, False: 65.3k] ------------------ 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| 39.8k| stack[cnt++] = node; 580| 39.8k| } 581| | 582| 105k| if(BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) { ------------------ | | 54| 105k|#define BIT_TEST(f, b) ((f) & (b)) | | ------------------ | | | Branch (54:25): [True: 52.5k, False: 52.7k] | | ------------------ ------------------ 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| 52.5k| node = node->r; 592| 52.7k| } 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| 52.7k| node = node->l; 602| 52.7k| } 603| | 604| 105k| if(node == NULL) ------------------ | Branch (604:8): [True: 6.65k, False: 98.5k] ------------------ 605| 6.65k| break; 606| 105k| } 607| | 608| 18.1k| if(inclusive && node && node->prefix) { ------------------ | Branch (608:6): [True: 18.1k, False: 0] | Branch (608:19): [True: 11.4k, False: 6.65k] | Branch (608:27): [True: 7.55k, False: 3.94k] ------------------ 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| 7.55k| stack[cnt++] = node; 615| 7.55k| } 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| 18.1k| if(cnt <= 0) ------------------ | Branch (627:6): [True: 3.76k, False: 14.3k] ------------------ 628| 3.76k| return (NULL); 629| | 630| 27.9k| while (--cnt >= 0) { ------------------ | Branch (630:10): [True: 17.8k, False: 10.1k] ------------------ 631| 17.8k| 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| 17.8k| if(ndpi_comp_with_mask (ndpi_prefix_tochar (node->prefix), ------------------ | Branch (636:8): [True: 6.03k, False: 11.8k] ------------------ 637| 17.8k| ndpi_prefix_tochar (prefix), 638| 17.8k| node->prefix->bitlen) && node->prefix->bitlen <= bitlen) { ------------------ | Branch (638:33): [True: 4.26k, False: 1.76k] ------------------ 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| 4.26k| patricia->stats.n_found++; 644| 4.26k| return (node); 645| 4.26k| } 646| 17.8k| } 647| 10.1k| return (NULL); 648| 14.3k|} ndpi_patricia_search_best: 653| 34.8k|{ 654| 34.8k| return (ndpi_patricia_search_best2 (patricia, prefix, 1)); 655| 34.8k|} ndpi_patricia_lookup: 660| 76.6k|{ 661| 76.6k| ndpi_patricia_node_t *node, *new_node, *parent, *glue; 662| 76.6k| u_char *addr, *test_addr; 663| 76.6k| u_int16_t bitlen, check_bit, differ_bit; 664| 76.6k| int i, j; 665| | 666| 76.6k| if(!patricia) ------------------ | Branch (666:6): [True: 1.60k, False: 75.0k] ------------------ 667| 1.60k| 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| 76.6k| assert (prefix); ------------------ | Branch (674:3): [True: 0, False: 75.0k] | Branch (674:3): [True: 75.0k, False: 0] ------------------ 675| 75.0k| assert (prefix->bitlen <= patricia->maxbits); ------------------ | Branch (675:3): [True: 0, False: 75.0k] | Branch (675:3): [True: 75.0k, False: 0] ------------------ 676| | 677| 75.0k| if(patricia->head == NULL) { ------------------ | Branch (677:6): [True: 3.14k, False: 71.8k] ------------------ 678| 3.14k| node = (ndpi_patricia_node_t*)ndpi_calloc(1, sizeof *node); 679| 3.14k| if(!node) ------------------ | Branch (679:8): [True: 193, False: 2.95k] ------------------ 680| 193| return NULL; 681| 2.95k| node->bit = prefix->bitlen; 682| 2.95k| node->prefix = ndpi_Ref_Prefix (prefix); 683| 2.95k| if(!node->prefix) { ------------------ | Branch (683:8): [True: 2.07k, False: 878] ------------------ 684| 2.07k| ndpi_free(node); 685| 2.07k| return NULL; 686| 2.07k| } 687| 878| node->parent = NULL; 688| 878| node->l = node->r = NULL; 689| 878| node->data = NULL; 690| 878| 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| 878| patricia->num_active_node++; 696| 878| return (node); 697| 2.95k| } 698| | 699| 71.8k| addr = ndpi_prefix_touchar (prefix); ------------------ | | 50| 71.8k|#define ndpi_prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin) ------------------ 700| 71.8k| bitlen = prefix->bitlen; 701| 71.8k| node = patricia->head; 702| | 703| 474k| while (node->bit < bitlen || node->prefix == NULL) { ------------------ | Branch (703:10): [True: 411k, False: 62.2k] | Branch (703:32): [True: 9.27k, False: 52.9k] ------------------ 704| 421k| if(node->bit < patricia->maxbits && ------------------ | Branch (704:8): [True: 421k, False: 0] ------------------ 705| 421k| BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) { ------------------ | | 54| 421k|#define BIT_TEST(f, b) ((f) & (b)) | | ------------------ | | | Branch (54:25): [True: 189k, False: 231k] | | ------------------ ------------------ 706| 189k| if(node->r == NULL) ------------------ | Branch (706:10): [True: 11.0k, False: 178k] ------------------ 707| 11.0k| 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| 178k| node = node->r; 716| 178k| } 717| 231k| else { 718| 231k| if(node->l == NULL) ------------------ | Branch (718:10): [True: 7.81k, False: 223k] ------------------ 719| 7.81k| 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| 223k| node = node->l; 728| 223k| } 729| | 730| 421k| assert (node); ------------------ | Branch (730:5): [True: 0, False: 402k] | Branch (730:5): [True: 402k, False: 0] ------------------ 731| 402k| } 732| | 733| 71.8k| assert (node->prefix); ------------------ | Branch (733:3): [True: 0, False: 71.8k] | Branch (733:3): [True: 71.8k, 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| 71.8k| test_addr = ndpi_prefix_touchar (node->prefix); ------------------ | | 50| 71.8k|#define ndpi_prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin) ------------------ 740| | /* find the first bit different */ 741| 71.8k| check_bit = (node->bit < bitlen)? node->bit: bitlen; ------------------ | Branch (741:15): [True: 18.8k, False: 52.9k] ------------------ 742| 71.8k| differ_bit = 0; 743| 216k| for (i = 0; (u_int)i*8 < check_bit; i++) { ------------------ | Branch (743:15): [True: 183k, False: 32.4k] ------------------ 744| 183k| int r; 745| | 746| 183k| if((r = (addr[i] ^ test_addr[i])) == 0) { ------------------ | Branch (746:8): [True: 144k, False: 39.4k] ------------------ 747| 144k| differ_bit = (i + 1) * 8; 748| 144k| continue; 749| 144k| } 750| | /* I know the better way, but for now */ 751| 186k| for (j = 0; j < 8; j++) { ------------------ | Branch (751:17): [True: 186k, False: 0] ------------------ 752| 186k| if(BIT_TEST (r, (0x80 >> j))) ------------------ | | 54| 186k|#define BIT_TEST(f, b) ((f) & (b)) | | ------------------ | | | Branch (54:25): [True: 39.4k, False: 147k] | | ------------------ ------------------ 753| 39.4k| break; 754| 186k| } 755| | /* must be found */ 756| 39.4k| assert (j < 8); ------------------ | Branch (756:5): [True: 0, False: 39.4k] | Branch (756:5): [True: 39.4k, False: 0] ------------------ 757| 39.4k| differ_bit = i * 8 + j; 758| 39.4k| break; 759| 39.4k| } 760| | 761| 71.8k| if(differ_bit > check_bit) ------------------ | Branch (761:6): [True: 23.5k, False: 48.3k] ------------------ 762| 23.5k| 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| 71.8k| parent = node->parent; 768| 110k| while (parent && parent->bit >= differ_bit) { ------------------ | Branch (768:10): [True: 94.9k, False: 15.0k] | Branch (768:20): [True: 38.1k, False: 56.7k] ------------------ 769| 38.1k| node = parent; 770| 38.1k| 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| 38.1k| } 779| | 780| 71.8k| if(differ_bit == bitlen && node->bit == bitlen) { ------------------ | Branch (780:6): [True: 32.1k, False: 39.7k] | Branch (780:30): [True: 18.2k, False: 13.8k] ------------------ 781| 18.2k| if(node->prefix) { ------------------ | Branch (781:8): [True: 15.9k, False: 2.30k] ------------------ 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| 15.9k| return (node); 787| 15.9k| } 788| 2.30k| node->prefix = ndpi_Ref_Prefix (prefix); 789| 2.30k| if(!node->prefix) { ------------------ | Branch (789:8): [True: 662, False: 1.64k] ------------------ 790| 662| return NULL; 791| 662| } 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| 2.30k| assert (node->data == NULL); ------------------ | Branch (796:5): [True: 0, False: 1.64k] | Branch (796:5): [True: 1.64k, False: 0] ------------------ 797| 1.64k| return (node); 798| 1.64k| } 799| | 800| 53.6k| new_node = (ndpi_patricia_node_t*)ndpi_calloc(1, sizeof *new_node); 801| 53.6k| if(!new_node) return NULL; ------------------ | Branch (801:6): [True: 3.46k, False: 50.1k] ------------------ 802| 50.1k| new_node->bit = prefix->bitlen; 803| 50.1k| new_node->prefix = ndpi_Ref_Prefix (prefix); 804| 50.1k| if(!new_node->prefix) { ------------------ | Branch (804:6): [True: 2.60k, False: 47.5k] ------------------ 805| 2.60k| ndpi_free(new_node); 806| 2.60k| return NULL; 807| 2.60k| } 808| 47.5k| new_node->parent = NULL; 809| 47.5k| new_node->l = new_node->r = NULL; 810| 47.5k| new_node->data = NULL; 811| 47.5k| patricia->num_active_node++; 812| | 813| 47.5k| if(node->bit == differ_bit) { ------------------ | Branch (813:6): [True: 6.14k, False: 41.4k] ------------------ 814| 6.14k| new_node->parent = node; 815| 6.14k| if(node->bit < patricia->maxbits && ------------------ | Branch (815:8): [True: 6.14k, False: 0] ------------------ 816| 6.14k| BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) { ------------------ | | 54| 6.14k|#define BIT_TEST(f, b) ((f) & (b)) | | ------------------ | | | Branch (54:25): [True: 4.70k, False: 1.43k] | | ------------------ ------------------ 817| 4.70k| assert (node->r == NULL); ------------------ | Branch (817:7): [True: 0, False: 4.70k] | Branch (817:7): [True: 4.70k, False: 0] ------------------ 818| 4.70k| node->r = new_node; 819| 4.70k| } 820| 1.43k| else { 821| 1.43k| assert (node->l == NULL); ------------------ | Branch (821:7): [True: 0, False: 1.43k] | Branch (821:7): [True: 1.43k, False: 0] ------------------ 822| 1.43k| node->l = new_node; 823| 1.43k| } 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| 6.14k| return (new_node); 829| 6.14k| } 830| | 831| 41.4k| if(bitlen == differ_bit) { ------------------ | Branch (831:6): [True: 11.8k, False: 29.5k] ------------------ 832| 11.8k| if(bitlen < patricia->maxbits && ------------------ | Branch (832:8): [True: 11.8k, False: 0] ------------------ 833| 11.8k| BIT_TEST (test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) { ------------------ | | 54| 11.8k|#define BIT_TEST(f, b) ((f) & (b)) | | ------------------ | | | Branch (54:25): [True: 3.23k, False: 8.61k] | | ------------------ ------------------ 834| 3.23k| new_node->r = node; 835| 3.23k| } 836| 8.61k| else { 837| 8.61k| new_node->l = node; 838| 8.61k| } 839| 11.8k| new_node->parent = node->parent; 840| 11.8k| if(node->parent == NULL) { ------------------ | Branch (840:8): [True: 2.74k, False: 9.10k] ------------------ 841| 2.74k| assert (patricia->head == node); ------------------ | Branch (841:7): [True: 0, False: 2.74k] | Branch (841:7): [True: 2.74k, False: 0] ------------------ 842| 2.74k| patricia->head = new_node; 843| 2.74k| } 844| 9.10k| else if(node->parent->r == node) { ------------------ | Branch (844:13): [True: 4.99k, False: 4.11k] ------------------ 845| 4.99k| node->parent->r = new_node; 846| 4.99k| } 847| 4.11k| else { 848| 4.11k| node->parent->l = new_node; 849| 4.11k| } 850| 11.8k| 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| 11.8k| } 856| 29.5k| else { 857| 29.5k| glue = (ndpi_patricia_node_t*)ndpi_calloc(1, sizeof *glue); 858| | 859| 29.5k| if(!glue) { ------------------ | Branch (859:8): [True: 2.12k, False: 27.4k] ------------------ 860| 2.12k| ndpi_Deref_Prefix(new_node->prefix); 861| 2.12k| ndpi_DeleteEntry (new_node); 862| 2.12k| patricia->num_active_node--; 863| 2.12k| return(NULL); 864| 2.12k| } 865| 27.4k| glue->bit = differ_bit; 866| 27.4k| glue->prefix = NULL; 867| 27.4k| glue->parent = node->parent; 868| 27.4k| glue->data = NULL; 869| 27.4k| patricia->num_active_node++; 870| 27.4k| if(differ_bit < patricia->maxbits && ------------------ | Branch (870:8): [True: 27.4k, False: 0] ------------------ 871| 27.4k| BIT_TEST (addr[differ_bit >> 3], 0x80 >> (differ_bit & 0x07))) { ------------------ | | 54| 27.4k|#define BIT_TEST(f, b) ((f) & (b)) | | ------------------ | | | Branch (54:25): [True: 20.2k, False: 7.23k] | | ------------------ ------------------ 872| 20.2k| glue->r = new_node; 873| 20.2k| glue->l = node; 874| 20.2k| } 875| 7.23k| else { 876| 7.23k| glue->r = node; 877| 7.23k| glue->l = new_node; 878| 7.23k| } 879| 27.4k| new_node->parent = glue; 880| | 881| 27.4k| if(node->parent == NULL) { ------------------ | Branch (881:8): [True: 2.66k, False: 24.8k] ------------------ 882| 2.66k| assert (patricia->head == node); ------------------ | Branch (882:7): [True: 0, False: 2.66k] | Branch (882:7): [True: 2.66k, False: 0] ------------------ 883| 2.66k| patricia->head = glue; 884| 2.66k| } 885| 24.8k| else if(node->parent->r == node) { ------------------ | Branch (885:13): [True: 16.8k, False: 7.96k] ------------------ 886| 16.8k| node->parent->r = glue; 887| 16.8k| } 888| 7.96k| else { 889| 7.96k| node->parent->l = glue; 890| 7.96k| } 891| 27.4k| 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| 27.4k| } 897| 39.3k| return (new_node); 898| 41.4k|} ndpi_patricia_remove: 903| 5.89k|{ 904| 5.89k| ndpi_patricia_node_t *parent, *child; 905| | 906| 5.89k| if(!patricia) ------------------ | Branch (906:6): [True: 0, False: 5.89k] ------------------ 907| 0| return; 908| 5.89k| assert (node); ------------------ | Branch (908:3): [True: 0, False: 5.89k] | Branch (908:3): [True: 5.89k, False: 0] ------------------ 909| | 910| 5.89k| if(node->r && node->l) { ------------------ | Branch (910:6): [True: 1.86k, False: 4.03k] | Branch (910:17): [True: 965, False: 902] ------------------ 911| |#ifdef PATRICIA_DEBUG 912| | fprintf (stderr, "patricia_remove: #0 %s/%d (r & l)\n", 913| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 914| |#endif /* PATRICIA_DEBUG */ 915| | 916| | /* this might be a placeholder node -- have to check and make sure 917| | * there is a prefix associated with it ! */ 918| 965| if(node->prefix != NULL) ------------------ | Branch (918:8): [True: 965, False: 0] ------------------ 919| 965| ndpi_Deref_Prefix (node->prefix); 920| 965| node->prefix = NULL; 921| | /* Also I needed to clear data pointer -- masaki */ 922| 965| node->data = NULL; 923| 965| return; 924| 965| } 925| | 926| 4.93k| if(node->r == NULL && node->l == NULL) { ------------------ | Branch (926:6): [True: 4.03k, False: 902] | Branch (926:25): [True: 2.68k, False: 1.34k] ------------------ 927| |#ifdef PATRICIA_DEBUG 928| | fprintf (stderr, "patricia_remove: #1 %s/%d (!r & !l)\n", 929| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 930| |#endif /* PATRICIA_DEBUG */ 931| 2.68k| parent = node->parent; 932| 2.68k| ndpi_Deref_Prefix (node->prefix); 933| 2.68k| ndpi_DeleteEntry (node); 934| 2.68k| patricia->num_active_node--; 935| | 936| 2.68k| if(parent == NULL) { ------------------ | Branch (936:8): [True: 19, False: 2.66k] ------------------ 937| 19| assert (patricia->head == node); ------------------ | Branch (937:7): [True: 0, False: 19] | Branch (937:7): [True: 19, False: 0] ------------------ 938| 19| patricia->head = NULL; 939| 19| return; 940| 19| } 941| | 942| 2.66k| if(parent->r == node) { ------------------ | Branch (942:8): [True: 1.41k, False: 1.25k] ------------------ 943| 1.41k| parent->r = NULL; 944| 1.41k| child = parent->l; 945| 1.41k| } 946| 1.25k| else { 947| 1.25k| assert (parent->l == node); ------------------ | Branch (947:7): [True: 0, False: 1.25k] | Branch (947:7): [True: 1.25k, False: 0] ------------------ 948| 1.25k| parent->l = NULL; 949| 1.25k| child = parent->r; 950| 1.25k| } 951| | 952| 2.66k| if(parent->prefix) ------------------ | Branch (952:8): [True: 833, False: 1.83k] ------------------ 953| 833| return; 954| | 955| | /* we need to remove parent too */ 956| | 957| 1.83k| if(parent->parent == NULL) { ------------------ | Branch (957:8): [True: 44, False: 1.79k] ------------------ 958| 44| assert (patricia->head == parent); ------------------ | Branch (958:7): [True: 0, False: 44] | Branch (958:7): [True: 44, False: 0] ------------------ 959| 44| patricia->head = child; 960| 44| } 961| 1.79k| else if(parent->parent->r == parent) { ------------------ | Branch (961:13): [True: 777, False: 1.01k] ------------------ 962| 777| parent->parent->r = child; 963| 777| } 964| 1.01k| else { 965| 1.01k| assert (parent->parent->l == parent); ------------------ | Branch (965:7): [True: 0, False: 1.01k] | Branch (965:7): [True: 1.01k, False: 0] ------------------ 966| 1.01k| parent->parent->l = child; 967| 1.01k| } 968| 1.83k| child->parent = parent->parent; 969| 1.83k| ndpi_DeleteEntry (parent); 970| 1.83k| patricia->num_active_node--; 971| 1.83k| return; 972| 1.83k| } 973| | 974| |#ifdef PATRICIA_DEBUG 975| | fprintf (stderr, "patricia_remove: #2 %s/%d (r ^ l)\n", 976| | ndpi_prefix_toa (node->prefix), node->prefix->bitlen); 977| |#endif /* PATRICIA_DEBUG */ 978| 2.24k| if(node->r) { ------------------ | Branch (978:6): [True: 902, False: 1.34k] ------------------ 979| 902| child = node->r; 980| 902| } 981| 1.34k| else { 982| 1.34k| assert (node->l); ------------------ | Branch (982:5): [True: 0, False: 1.34k] | Branch (982:5): [True: 1.34k, False: 0] ------------------ 983| 1.34k| child = node->l; 984| 1.34k| } 985| 2.24k| parent = node->parent; 986| 2.24k| child->parent = parent; 987| | 988| 2.24k| ndpi_Deref_Prefix (node->prefix); 989| 2.24k| ndpi_DeleteEntry (node); 990| 2.24k| patricia->num_active_node--; 991| | 992| 2.24k| if(parent == NULL) { ------------------ | Branch (992:6): [True: 96, False: 2.14k] ------------------ 993| 96| assert (patricia->head == node); ------------------ | Branch (993:5): [True: 0, False: 96] | Branch (993:5): [True: 96, False: 0] ------------------ 994| 96| patricia->head = child; 995| 96| return; 996| 96| } 997| | 998| 2.14k| if(parent->r == node) { ------------------ | Branch (998:6): [True: 866, False: 1.28k] ------------------ 999| 866| parent->r = child; 1000| 866| } 1001| 1.28k| else { 1002| 1.28k| assert (parent->l == node); ------------------ | Branch (1002:5): [True: 0, False: 1.28k] | Branch (1002:5): [True: 1.28k, False: 0] ------------------ 1003| 1.28k| parent->l = child; 1004| 1.28k| } 1005| 2.14k|} ndpi_patricia.c:ndpi_Deref_Prefix: 288| 50.0k|{ 289| 50.0k| if(prefix == NULL) ------------------ | Branch (289:6): [True: 0, False: 50.0k] ------------------ 290| 0| return; 291| | /* for secure programming, raise an assert. no static prefix can call this */ 292| 50.0k| assert (prefix->ref_count > 0); ------------------ | Branch (292:3): [True: 0, False: 50.0k] | Branch (292:3): [True: 50.0k, False: 0] ------------------ 293| | 294| 50.0k| prefix->ref_count--; 295| 50.0k| assert (prefix->ref_count >= 0); ------------------ | Branch (295:3): [True: 0, False: 50.0k] | Branch (295:3): [True: 50.0k, False: 0] ------------------ 296| 50.0k| if(prefix->ref_count <= 0) { ------------------ | Branch (296:6): [True: 29.7k, False: 20.3k] ------------------ 297| 29.7k| ndpi_DeleteEntry (prefix); 298| 29.7k| return; 299| 29.7k| } 300| 50.0k|} ndpi_patricia.c:ndpi_DeleteEntry: 57| 107k|static void ndpi_DeleteEntry(void *a) { 58| 107k| ndpi_free(a); 59| 107k|} ndpi_patricia.c:ndpi_patricia_clone_walk: 401| 34.7k|{ 402| 34.7k| ndpi_patricia_node_t *cloned_node; 403| 34.7k| size_t n = 0; 404| | 405| 34.7k| if(node->l) { ------------------ | Branch (405:6): [True: 17.7k, False: 17.0k] ------------------ 406| 17.7k| n += ndpi_patricia_clone_walk(node->l, dst); 407| 17.7k| } 408| | 409| 34.7k| if(node->prefix) { ------------------ | Branch (409:6): [True: 21.7k, False: 12.9k] ------------------ 410| 21.7k| cloned_node = ndpi_patricia_lookup(dst, node->prefix); 411| | 412| 21.7k| if(cloned_node) { ------------------ | Branch (412:8): [True: 19.4k, False: 2.28k] ------------------ 413| | /* Note: this is not cloning clone referenced void * data / user_data */ 414| 19.4k| memcpy(&cloned_node->value, &node->value, sizeof(cloned_node->value)); 415| 19.4k| } 416| | 417| 21.7k| n++; 418| 21.7k| } 419| | 420| 34.7k| if(node->r) { ------------------ | Branch (420:6): [True: 16.6k, False: 18.1k] ------------------ 421| 16.6k| n += ndpi_patricia_clone_walk(node->r, dst); 422| 16.6k| } 423| | 424| 34.7k| return n; 425| 34.7k|} ndpi_patricia.c:ndpi_comp_with_mask: 80| 22.0k|static int ndpi_comp_with_mask (void *addr, void *dest, u_int mask) { 81| 22.0k| uint32_t *pa = addr; 82| 22.0k| uint32_t *pd = dest; 83| 22.0k| uint32_t m; 84| 30.9k| for(;mask >= 32; mask -= 32, pa++,pd++) ------------------ | Branch (84:8): [True: 14.5k, False: 16.3k] ------------------ 85| 14.5k| if(*pa != *pd) return 0; ------------------ | Branch (85:8): [True: 5.70k, False: 8.87k] ------------------ 86| 16.3k| if(!mask) return 1; ------------------ | Branch (86:6): [True: 1.22k, False: 15.1k] ------------------ 87| 15.1k| m = htonl((~0u) << (32-mask)); 88| 15.1k| return (*pa & m) == (*pd &m); 89| 16.3k|} ndpi_patricia.c:ndpi_prefix_tochar: 67| 44.0k|{ 68| 44.0k| unsigned short family; 69| | 70| 44.0k| if(prefix == NULL) ------------------ | Branch (70:6): [True: 0, False: 44.0k] ------------------ 71| 0| return (NULL); 72| | 73| 44.0k| family = prefix->family; 74| | 75| 44.0k| if(family == AF_INET) return ((u_char *) & prefix->add.sin); ------------------ | Branch (75:6): [True: 16.8k, False: 27.2k] ------------------ 76| 27.2k| else if(family == AF_INET6) return ((u_char *) & prefix->add.sin6); ------------------ | Branch (76:11): [True: 15.5k, False: 11.7k] ------------------ 77| 11.7k| else /* if(family == AF_MAC) */ return ((u_char *) & prefix->add.mac); 78| 44.0k|} ndpi_patricia.c:ndpi_Ref_Prefix: 274| 55.4k|{ 275| 55.4k| if(prefix == NULL) ------------------ | Branch (275:6): [True: 0, False: 55.4k] ------------------ 276| 0| return (NULL); 277| 55.4k| if(prefix->ref_count == 0) { ------------------ | Branch (277:6): [True: 35.1k, False: 20.3k] ------------------ 278| | /* make a copy in case of a static prefix */ 279| 35.1k| return (ndpi_New_Prefix2 (prefix->family, &prefix->add, prefix->bitlen, NULL)); 280| 35.1k| } 281| 20.3k| prefix->ref_count++; 282| | /* fprintf(stderr, "[A %s, %d]\n", ndpi_prefix_toa (prefix), prefix->ref_count); */ 283| 20.3k| return (prefix); 284| 55.4k|} ndpi_patricia.c:ndpi_New_Prefix2: 210| 35.1k|{ 211| 35.1k| int dynamic_allocated = 0; 212| 35.1k| int default_bitlen = sizeof(struct in_addr) * 8; 213| | 214| 35.1k| if(family == AF_INET6) { ------------------ | Branch (214:6): [True: 9.93k, False: 25.1k] ------------------ 215| 9.93k| default_bitlen = sizeof(struct in6_addr) * 8; 216| 9.93k| if(prefix == NULL) { ------------------ | Branch (216:8): [True: 9.93k, False: 0] ------------------ 217| 9.93k| prefix = (ndpi_prefix_t*)ndpi_calloc(1, sizeof (ndpi_prefix_t)); 218| 9.93k| if(!prefix) ------------------ | Branch (218:10): [True: 659, False: 9.27k] ------------------ 219| 659| return (NULL); 220| 9.27k| dynamic_allocated++; 221| 9.27k| } 222| 9.27k| memcpy (&prefix->add.sin6, dest, sizeof(struct in6_addr)); 223| 9.27k| } 224| 25.1k| else 225| 25.1k| if(family == AF_INET) { ------------------ | Branch (225:8): [True: 15.0k, False: 10.1k] ------------------ 226| 15.0k| if(prefix == NULL) { ------------------ | Branch (226:10): [True: 15.0k, False: 0] ------------------ 227| 15.0k|#ifndef NT 228| 15.0k| 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.0k| if(!prefix) ------------------ | Branch (234:5): [True: 1.04k, False: 13.9k] ------------------ 235| 1.04k| return (NULL); 236| | 237| 13.9k| dynamic_allocated++; 238| 13.9k| } 239| 13.9k| memcpy (&prefix->add.sin, dest, sizeof(struct in_addr)); 240| 13.9k| } 241| 10.1k| else if(family == AF_MAC) { ------------------ | | 2067| 10.1k|#define AF_MAC 99 ------------------ | Branch (241:13): [True: 7.06k, False: 3.09k] ------------------ 242| 7.06k| default_bitlen = 48; 243| 7.06k| if(prefix == NULL) { ------------------ | Branch (243:10): [True: 7.06k, False: 0] ------------------ 244| 7.06k| prefix = (ndpi_prefix_t*)ndpi_calloc(1, sizeof (ndpi_prefix_t)); 245| 7.06k| if(!prefix) ------------------ | Branch (245:12): [True: 534, False: 6.53k] ------------------ 246| 534| return (NULL); 247| 6.53k| dynamic_allocated++; 248| 6.53k| } 249| 6.53k| memcpy (prefix->add.mac, dest, 6); 250| 6.53k| } 251| 3.09k| else { 252| 3.09k| return (NULL); 253| 3.09k| } 254| | 255| 29.7k| prefix->bitlen = (u_int16_t)((bitlen >= 0) ? bitlen : default_bitlen); ------------------ | Branch (255:32): [True: 29.7k, False: 0] ------------------ 256| 29.7k| prefix->family = (u_int16_t)family; 257| 29.7k| prefix->ref_count = 0; 258| 29.7k| if(dynamic_allocated) { ------------------ | Branch (258:6): [True: 29.7k, False: 0] ------------------ 259| 29.7k| prefix->ref_count++; 260| 29.7k| } 261| | /* fprintf(stderr, "[C %s, %d]\n", ndpi_prefix_toa (prefix), prefix->ref_count); */ 262| 29.7k| return (prefix); 263| 35.1k|}