UniRec 3.3.2
Loading...
Searching...
No Matches
ip_prefix_search.c
Go to the documentation of this file.
1
10/*
11 * Copyright (C) 2013,2014 CESNET
12 *
13 * LICENSE TERMS
14 *
15 * Redistribution and use in source and binary forms, with or without
16 * modification, are permitted provided that the following conditions
17 * are met:
18 * 1. Redistributions of source code must retain the above copyright
19 * notice, this list of conditions and the following disclaimer.
20 * 2. Redistributions in binary form must reproduce the above copyright
21 * notice, this list of conditions and the following disclaimer in
22 * the documentation and/or other materials provided with the
23 * distribution.
24 * 3. Neither the name of the Company nor the names of its contributors
25 * may be used to endorse or promote products derived from this
26 * software without specific prior written permission.
27 *
28 * ALTERNATIVELY, provided that this notice is retained in full, this
29 * product may be distributed under the terms of the GNU General Public
30 * License (GPL) version 2 or later, in which case the provisions
31 * of the GPL apply INSTEAD OF those given above.
32 *
33 * This software is provided ``as is'', and any express or implied
34 * warranties, including, but not limited to, the implied warranties of
35 * merchantability and fitness for a particular purpose are disclaimed.
36 * In no event shall the company or contributors be liable for any
37 * direct, indirect, incidental, special, exemplary, or consequential
38 * damages (including, but not limited to, procurement of substitute
39 * goods or services; loss of use, data, or profits; or business
40 * interruption) however caused and on any theory of liability, whether
41 * in contract, strict liability, or tort (including negligence or
42 * otherwise) arising in any way out of the use of this software, even
43 * if advised of the possibility of such damage.
44 *
45 */
46
47#include <stdio.h>
48#include <stdint.h>
49#include <stdlib.h>
51#include "ipps_internal.h"
52
58uint8_t bit_endian_swap(uint8_t in)
59{
60 in = (in & 0xF0) >> 4 | (in & 0x0F) << 4;
61 in = (in & 0xCC) >> 2 | (in & 0x33) << 2;
62 in = (in & 0xAA) >> 1 | (in & 0x55) << 1;
63 return in;
64}
65
73{
74 int i, j;
75 uint32_t **net_mask_array = malloc(129 * sizeof(uint32_t *));
76 if (net_mask_array == NULL) {
77 return NULL;
78 }
79
80 net_mask_array[0] = calloc(4, sizeof(uint32_t));
81 for (i = 1; i < 129; i++) {
82 net_mask_array[i] = malloc(4 * sizeof(uint32_t));
83 if (net_mask_array[i] == NULL) {
84 for (int k = 0; k < i; k++) {
85 free(net_mask_array[i]);
86 }
87 free(net_mask_array);
88 return NULL;
89 }
90 // Fill every word of IPv6 address
91 net_mask_array[i][0] = 0xFFFFFFFF >> (i == 0 || i >= 32 ? 0 : 32 - i);
92 net_mask_array[i][1] = i <= 32 ? 0 : 0xFFFFFFFF >> (i >= 64 ? 0 : 64 - i);
93 net_mask_array[i][2] = i <= 64 ? 0 : 0xFFFFFFFF >> (i >= 96 ? 0 : 96 - i);
94 net_mask_array[i][3] = i <= 96 ? 0 : 0xFFFFFFFF >> (128 - i);
95
96 // Swap bits in every byte for compatibility with ip_addr_t stucture
97 for (j = 0; j < 4; ++j) {
98 net_mask_array[i][j] = (bit_endian_swap((net_mask_array[i][j] & 0x000000FF) >> 0) << 0) |
99 (bit_endian_swap((net_mask_array[i][j] & 0x0000FF00) >> 8) << 8) |
100 (bit_endian_swap((net_mask_array[i][j] & 0x00FF0000) >> 16) << 16) |
101 (bit_endian_swap((net_mask_array[i][j] & 0xFF000000) >> 24) << 24);
102 }
103 }
104
105 return net_mask_array;
106}
107
115void destroy_ip_v6_net_mask_array(uint32_t **net_mask_array)
116{
117 int index;
118 for (index = 0; index < 129; index++) {
119 free(net_mask_array[index]);
120 }
121 free(net_mask_array);
122}
123
131int cmp_net_v4(const void *v1, const void *v2)
132{
133 const ipps_network_t *n1 = *(ipps_network_t **)v1;
134 const ipps_network_t *n2 = *(ipps_network_t **)v2;
135
136 int ip_cmp_result;
137
138 ip_cmp_result = memcmp(&n1->addr.ui32[2], &n2->addr.ui32[2], 4);
139 /* if they are equal - lower mask (greater network) first */
140 if (ip_cmp_result == 0) {
141 return memcmp(&n1->mask, &n2->mask, 4);
142 } else {
143 return ip_cmp_result;
144 }
145}
146
154int cmp_net_v6(const void *v1, const void *v2)
155{
156 const ipps_network_t *n1 = *(ipps_network_t **)v1;
157 const ipps_network_t *n2 = *(ipps_network_t **)v2;
158
159 int ip_cmp_result;
160
161 ip_cmp_result = memcmp(&n1->addr.ui8, &n2->addr.ui8, 16);
162 /* if they are equal - lower mask (greater network) first */
163 if (ip_cmp_result == 0) {
164 return memcmp(&n1->mask, &n2->mask, 4);
165 } else {
166 return ip_cmp_result;
167 }
168}
169
179void mask_ipv6(ip_addr_t *ip, uint32_t mask, ip_addr_t *masked_ipv6, uint32_t **net_mask_array)
180{
181 int i;
182 for (i = 0; i < 4; i++) {
183 masked_ipv6->ui32[i] = ip->ui32[i] & net_mask_array[mask][i];
184 }
185}
186
197 uint32_t **net_mask_array)
198{
199 inter->data_cnt = 0;
200 inter->data_array = NULL;
201
202 /* Fill network address */
203 memcpy(&inter->low_ip, &net->addr, 16);
204
205 /* Fill broadcast address */
206 if (!ip_is6(&net->addr)) {
207 // IPv4
208 inter->high_ip.ui64[0] = 0;
209 inter->high_ip.ui32[2] = net->addr.ui32[2] | ( ~ net_mask_array[net->mask][0]);
210 inter->high_ip.ui32[3] = 0xffffffff;
211 } else {
212 // IPv6
213 int i;
214 for (i = 0; i < 4; i++) {
215 inter->high_ip.ui32[i] = net->addr.ui32[i] | ( ~ net_mask_array[net->mask][i]);
216 }
217 }
218}
219
227 ipps_interval_node_t *new_interval(const ip_addr_t *low_ip, const ip_addr_t *high_ip)
228{
229
230 ipps_interval_node_t * new_node = malloc(sizeof(ipps_interval_node_t));
231 if (new_node == NULL) {
232 fprintf(stderr, "ERROR allocating memory for network interval node\n");
233 return NULL;
234 }
235
236 new_node->interval = malloc(sizeof(ipps_interval_t));
237 if (new_node->interval == NULL) {
238 fprintf(stderr, "ERROR allocating memory for network interval\n");
239 free(new_node);
240 return NULL;
241 }
242 new_node->next = NULL;
243
244 /* Initialize struct members */
245 memcpy(&new_node->interval->low_ip, low_ip, 16);
246 memcpy(&new_node->interval->high_ip, high_ip, 16);
247 new_node->interval->data_cnt = 0;
248 new_node->interval->array_len = DATASLOTS;
249 new_node->interval->data_array = malloc(DATASLOTS * sizeof(void *));
250 if (new_node->interval->data_array == NULL) {
251 fprintf(stderr, "ERROR allocating memory for data pointers\n");
252 free(new_node->interval);
253 free(new_node);
254 return NULL;
255 }
256
257 return new_node;
258}
259
270 const ip_addr_t *low_ip, const ip_addr_t *high_ip)
271{
272 ipps_interval_node_t *new_interval_node = new_interval(low_ip, high_ip);
273 if (new_interval_node == NULL) {
274 return NULL;
275 }
276
277 /* Post Insert */
278 new_interval_node->next = position->next;
279 position->next = new_interval_node;
280
281 return new_interval_node;
282}
283
292{
293 if (ip_is6(ip)) {
294 memcpy(ip_dec, ip, 16);
295
296 uint32_t tmp = 0xffffffff;
297 int i;
298 for (i = 3; i >=0; i--) {
299 ip_dec->ui32[i] = htonl(ntohl(ip->ui32[i]) - 1);
300 if (ip_dec->ui32[i] != tmp) {
301 break;
302 }
303 }
304 } else {
305 ip_dec->ui64[0] = 0;
306 ip_dec->ui32[2] = htonl(ntohl(ip->ui32[2]) - 1);
307 ip_dec->ui32[3] = 0xffffffff;
308 }
309}
310
319{
320 if (ip_is6(ip)) {
321 memcpy(ip_inc, ip, 16);
322
323 uint32_t tmp = 0xffffffff;
324 int i;
325 for (i = 3; i >= 0; i--) {
326 ip_inc->ui32[i] = htonl(ntohl(ip->ui32[i]) + 1);
327 if (ip->ui32[i] < tmp) {
328 break;
329 }
330 }
331 } else {
332 ip_inc->ui64[0] = 0;
333 ip_inc->ui32[2] = htonl(ntohl(ip->ui32[2]) + 1);
334 ip_inc->ui32[3] = 0xffffffff;
335 }
336}
337
344int ipps_destroy(ipps_context_t *prefix_context)
345{
346 int i;
347 void **data_collector; // Array with freed memory pointers
348 uint32_t data_collector_cnt = 0; // Number of pointers in 'data_collector'
349
350 if (prefix_context == NULL) {
351 fprintf(stderr, "ERROR NULL pointer passed to ipps_destroy\n");
352 return 1;
353 }
354
355 data_collector = malloc(COLLECTORSLOTS * sizeof(void *));
356 if (data_collector == NULL) {
357 fprintf(stderr, "ERROR allocating memory for freed data collector\n");
358 return 1;
359 }
360
361 // Dealloc all IPv4 data and intervals
362 for (i = 0; i < prefix_context->v4_count; ++i) {
363 if (free_data(&prefix_context->v4_prefix_intervals[i], &data_collector, &data_collector_cnt)) {
364 return 1;
365 }
366 }
367
368 // Dealloc all IPv6 data and intervals
369 data_collector_cnt = 0;
370 for (i = 0; i < prefix_context->v6_count; ++i) {
371 if (free_data(&prefix_context->v6_prefix_intervals[i], &data_collector, &data_collector_cnt)) {
372 return 1;
373 }
374 }
375
376 free(data_collector);
377 free(prefix_context->v4_prefix_intervals);
378 free(prefix_context->v6_prefix_intervals);
379 free(prefix_context);
380 return 0;
381}
382
388{
389 ipps_context_t *prefix_context = malloc(sizeof(ipps_context_t));
390 if (prefix_context == NULL) {
391 fprintf(stderr, "ERROR allocating memory for network mask array\n");
392 return NULL;
393 }
394
395 prefix_context->v4_count = 0;
396 prefix_context->v6_count = 0;
397 prefix_context->v4_prefix_intervals = NULL;
398 prefix_context->v6_prefix_intervals = NULL;
399
400 return prefix_context;
401}
402
412{
413 int index;
414 ip_addr_t *masked_ip;
415
416 if (network_list == NULL) {
417 fprintf(stderr, "ERROR Network list is not initialized");
418 return NULL;
419 }
420
421 if (network_list->net_count <= 0) {
422 fprintf(stderr, "ERROR Network lists are empty, nothing to do");
423 return NULL;
424 }
425
426 // Create new interval_search_context
427 ipps_context_t *prefix_context = new_context();
428 if (prefix_context == NULL) {
429 return NULL;
430 }
431
432 // Create and fill net mask array - for masking IP
433 uint32_t **net_mask_array = create_ip_v6_net_mask_array();
434 if (net_mask_array == NULL) {
435 fprintf(stderr, "ERROR allocating memory for network mask array\n");
436 ipps_destroy(prefix_context);
437 return NULL;
438 }
439
440 ipps_network_t *current_net; // Currently precessed network
441 void *tmp;
442
443 ipps_network_t **networks_v6 = NULL; // Pointers to ipv6 networks
444 ipps_network_t **networks_v4 = NULL; // Pointers to ipv4 networks
445
446
447 uint32_t i_v6 = 0; // Number of ipv6 networks
448 uint32_t i_v4 = 0; // Number of ipv4 networks
449
450 size_t i_v6_alloc = NETWORKSLOTS; // Number of available network pointers
451 size_t i_v4_alloc = NETWORKSLOTS; // Number of available network pointers
452
453 // Allocate memory for network array
454 if ((networks_v4 = malloc(i_v4_alloc * sizeof(ipps_network_t *))) == NULL ||
455 (networks_v6 = malloc(i_v6_alloc * sizeof(ipps_network_t *))) == NULL) {
456 free(networks_v4);
457 free(networks_v6);
458 ipps_destroy(prefix_context);
459 destroy_ip_v6_net_mask_array(net_mask_array);
460 fprintf(stderr, "ERROR allocating sorted network structures\n");
461 return NULL;
462 }
463
464 // For each network in array - mask ip address and split to ipv4 or ipv6 network
465 for (index = 0; index < network_list->net_count; ++index)
466 {
467 current_net = &network_list->networks[index];
468 if (ip_is6(&current_net->addr)) {
469 masked_ip = &current_net->addr;
470 mask_ipv6(&current_net->addr, current_net->mask, masked_ip, net_mask_array);
471
472 i_v6++;
473 if (i_v6_alloc < i_v6) {
474 i_v6_alloc *= 2;
475 tmp = realloc(networks_v6, i_v6_alloc * sizeof(ipps_network_t *));
476 if (tmp == NULL) {
477 fprintf(stderr, "ERROR allocating memory for ipv6 network collector\n");
478 ipps_destroy(prefix_context);
479 destroy_ip_v6_net_mask_array(net_mask_array);
480 free(networks_v4);
481 free(networks_v6);
482 return NULL;
483 }
484 networks_v6 = tmp;
485
486 }
487 networks_v6[i_v6-1] = current_net;
488 } else {
489 masked_ip = &current_net->addr;
490 masked_ip->ui32[2] = masked_ip->ui32[2] & net_mask_array[current_net->mask][0];
491
492 i_v4++;
493 if (i_v4_alloc < i_v4) {
494 i_v4_alloc *= 2;
495 tmp = realloc(networks_v4, i_v4_alloc * sizeof(ipps_network_t *));
496 if (tmp == NULL) {
497 fprintf(stderr, "ERROR allocating memory for ipv6 network collector\n");
498 ipps_destroy(prefix_context);
499 destroy_ip_v6_net_mask_array(net_mask_array);
500 free(networks_v4);
501 free(networks_v6);
502 return NULL;
503 }
504 networks_v4 = tmp;
505 }
506 networks_v4[i_v4 - 1] = current_net;
507 }
508 }
509
510 if (i_v4 > 0 && networks_v4[0] != NULL) {
511 qsort(networks_v4, i_v4, sizeof(ipps_network_t *), cmp_net_v4);
512
513 // Fill intervals for IPv4 to interval_search_context array, if fail, dealloc and rtrn NULL
514 prefix_context->v4_prefix_intervals = init_context(networks_v4, i_v4,
515 &prefix_context->v4_count, net_mask_array);
516 if (prefix_context->v4_prefix_intervals == NULL) {
517 destroy_ip_v6_net_mask_array(net_mask_array);
518 ipps_destroy(prefix_context);
519 free(networks_v4);
520 free(networks_v6);
521 return NULL;
522 }
523 /************************/
524 }
525 free(networks_v4);
526
527 if (i_v6 > 0 && networks_v6[0] != NULL) {
528 qsort(networks_v6, i_v6, sizeof(ipps_network_t *), cmp_net_v6);
529
530 // Fill intervals for IPv6 to interval_search_context array, if fail, dealloc and return NULL
531 prefix_context->v6_prefix_intervals = init_context(networks_v6, i_v6,
532 &prefix_context->v6_count, net_mask_array);
533 if (prefix_context->v6_prefix_intervals == NULL) {
534 destroy_ip_v6_net_mask_array(net_mask_array);
535 ipps_destroy(prefix_context);
536 free(networks_v6);
537 return NULL;
538 }
539
540 /************************/
541 }
542 free(networks_v6);
543
544 destroy_ip_v6_net_mask_array(net_mask_array);
545 return prefix_context;
546}
547
557{
558
559 if (dest->data_cnt + src->data_cnt > dest->array_len) {
560 // no free pointer slots for src data in dest data_array
561 void **tmp;
562 dest->array_len += src->array_len;
563 tmp = realloc (dest->data_array, dest->array_len * sizeof(void *));
564 if (tmp == NULL) {
565 fprintf(stderr, "ERROR allocating memory for network mask array\n");
566 return 1;
567 }
568 dest->data_array = tmp;
569 }
570
571 memcpy(dest->data_array + dest->data_cnt, src->data_array, src->data_cnt * sizeof(void *));
572 dest->data_cnt += src->data_cnt;
573 return 0;
574}
575
586int add_data(ipps_interval_t *interval, void *data, size_t data_len)
587{
588 // Alloc new data and copy
589 void *new_data = malloc(data_len);
590 if (new_data == NULL) {
591 fprintf(stderr, "ERROR allocating memory for network mask array\n");
592 return 1;
593 }
594
595 memcpy(new_data, data, data_len);
596
597 // Insert new data to interval's data array - first do some space ...
598 interval->data_cnt++;
599 if (interval->data_cnt > interval->array_len) {
600 void **tmp;
601 interval->array_len *= 2;
602 tmp = realloc (interval->data_array, interval->array_len * sizeof(void *));
603 if (tmp == NULL) {
604 fprintf(stderr, "ERROR allocating memory for network mask array\n");
605 free(new_data);
606 return 1;
607 }
608 interval->data_array = tmp;
609 }
610
611 // ... then push new data to array
612 interval->data_array[interval->data_cnt - 1] = new_data;
613
614 return 0;
615}
616
633ipps_interval_t *init_context( ipps_network_t **networks, uint32_t network_count,
634 uint32_t *context_counter, uint32_t **net_mask_array)
635{
636 uint32_t interval_counter = 0;
637
638 ipps_interval_t current_interval;
639 ipps_interval_node_t *interval_list = NULL;
640
641 int index = 0;
642
643 // push first interval from network tree to interval_search_context interval list
644 // compute ip interval - low and high ip addresses
645 fill_interval_by_network(networks[0], &current_interval, net_mask_array);
646 // insert root interval node to list
647 interval_list = new_interval(&current_interval.low_ip, &current_interval.high_ip);
648 if (interval_list == NULL) {
649 return NULL;
650 }
651
652 if (add_data(interval_list->interval, networks[0]->data, networks[0]->data_len)) {
653 // add data to root node
654 destroy_list(interval_list);
655 return NULL;
656 }
657 interval_counter++; // number of intervals
658
659 ipps_interval_node_t *conductor = NULL; // list iterator
660 ipps_interval_node_t *end_of_list = interval_list; // last element in the list
661
662 int ip_cmp_result; // result of ip comparison
663 ip_addr_t tmp_ip ; // temporary ip addr union for compute first or last IP address of interval
664
665 conductor = interval_list;
666
667 // traverse rest of networks tree
668 for (index = 1; index < network_count; ++index) {
669 // fill temporary interval variable by current interval
670 fill_interval_by_network(networks[index], &current_interval, net_mask_array);
671
672 while (conductor != NULL) {
673 // compare low IP of actual processed interval with high IP all intervals in list
674 ip_cmp_result = ip_cmp( &conductor->interval->high_ip, &current_interval.low_ip);
675
676 if (ip_cmp_result >= 0) {
677 ip_cmp_result = ip_cmp( &conductor->interval->low_ip, &current_interval.low_ip);
678 if (ip_cmp_result > 0) {
679 // LowI > LowT
680 ip_cmp_result = ip_cmp( &conductor->interval->high_ip, &current_interval.high_ip);
681 if (ip_cmp_result > 0) {
682 // Con <---------->
683 // Cur <---------->
684
685 fprintf(stderr, "ERROR Inserting to list");
686 destroy_list(interval_list);
687 return NULL;
688 } else if (ip_cmp_result < 0) {
689 // Con <-------->
690 // Cur <------------>
691
692 fprintf(stderr, "ERROR Inserting to list");
693 destroy_list(interval_list);
694 return NULL;
695 } else {
696 // Con <-------->
697 // Cur <---------->
698
699 fprintf(stderr, "ERROR Inserting to list");
700 destroy_list(interval_list);
701 return NULL;
702 }
703 } else if (ip_cmp_result < 0) {
704 // LowI < LowT
705 ip_cmp_result = ip_cmp( &conductor->interval->high_ip, &current_interval.high_ip);
706 if (ip_cmp_result > 0) {
707 // Con <---------->
708 // Cur <----->
709
710 /***********************/
711 /* | | ↓ | |
712 * <----------->
713 * <----->
714 */
715
716 // Insert new interval to interval tree, conductor post insert
717 if (insert_new_interval(conductor, &current_interval.low_ip,
718 &current_interval.high_ip) == NULL) {
719 destroy_list(interval_list);
720 return NULL;
721 }
722 interval_counter++;
723
724 // Fill data array in new interval node
725 // Copy original data and add new one from current network
726 if (copy_all_data(conductor->next->interval, conductor->interval)) {
727 destroy_list(interval_list);
728 return NULL;
729 }
730 if (add_data(conductor->next->interval, networks[index]->data, networks[index]->data_len)) {
731 destroy_list(interval_list);
732 return NULL;
733 }
734 /***********************/
735
736 /***********************/
737 /*
738 * | | |↓ |
739 * Con <----------->
740 * Cur <----->
741 */
742
743 // Insert new interval to interval list
744 ip_inc(&current_interval.high_ip, &tmp_ip);
745 if (insert_new_interval(conductor->next, &tmp_ip, &conductor->interval->high_ip) == NULL) {
746 destroy_list(interval_list);
747 return NULL;
748 }
749 interval_counter++;
750
751 if (copy_all_data(conductor->next->next->interval, conductor->interval)) {
752 destroy_list(interval_list);
753 return NULL;
754 }
755
756 /***********************/
757
758 /***********************/
759 /* |↓| | |
760 * Con <----------->
761 * Cur <----->
762 */
763
764 // Modify original interval
765 ip_dec(&current_interval.low_ip, &tmp_ip);
766 memcpy(&conductor->interval->high_ip, &tmp_ip, 16);
767 /***********************/
768
769 // Modify end of interval list, 2 follower inserted
770 if (end_of_list == conductor) {
771 end_of_list = conductor->next->next;
772 }
773 break;
774 }
775 else if (ip_cmp_result < 0) {
776 // Con <---------->
777 // Cur <----------->
778
779 fprintf(stderr, "ERROR Inserting to list");
780 destroy_list(interval_list);
781 return NULL;
782 } else {
783 // Con <---------->
784 // Cur <-------->
785
786 if (insert_new_interval(conductor, &current_interval.low_ip,
787 &conductor->interval->high_ip) == NULL) {
788 destroy_list(interval_list);
789 return NULL;
790 }
791 interval_counter++;
792
793 if (copy_all_data(conductor->next->interval, conductor->interval)) {
794 destroy_list(interval_list);
795 return NULL;
796 }
797 if (add_data(conductor->next->interval, networks[index]->data,
798 networks[index]->data_len)) {
799 destroy_list(interval_list);
800 return NULL;
801 }
802
803 if (end_of_list == conductor) {
804 end_of_list = conductor->next;
805 }
806
807 ip_dec(&current_interval.low_ip, &tmp_ip);
808 memcpy(&conductor->interval->high_ip, &tmp_ip, 16);
809 }
810 } else {
811 ip_cmp_result = ip_cmp( &conductor->interval->high_ip, &current_interval.high_ip);
812 if (ip_cmp_result > 0) {
813 // Con <---------->
814 // Cur <-------->
815
816 ip_inc(&current_interval.high_ip, &tmp_ip);
817
818 insert_new_interval(conductor, &tmp_ip, &conductor->interval->high_ip);
819 interval_counter++;
820
821 copy_all_data(conductor->next->interval, conductor->interval);
822
823 if (end_of_list == conductor) {
824 end_of_list = conductor->next;
825 }
826 memcpy(&conductor->interval->high_ip, &current_interval.high_ip, 16);
827 if (add_data(conductor->interval, networks[index]->data, networks[index]->data_len)) {
828 destroy_list(interval_list);
829 return NULL;
830 }
831
832 break;
833 } else if (ip_cmp_result < 0) {
834 // Con <-------->
835 // Cur <---------->
836
837 fprintf(stderr, "ERROR Inserting to list");
838 destroy_list(interval_list);
839 return NULL;
840 } else {
841 // Con <-------->
842 // Cur <-------->
843
844 if (add_data(conductor->interval, networks[index]->data,
845 networks[index]->data_len)) {
846 destroy_list(interval_list);
847 return NULL;
848 }
849 }
850 }
851
852 break;
853 } else if (ip_cmp_result < 0) {
854 // Low ip address of current is higher then high ip of interval list member,
855 // take next interval in list
856 conductor = conductor->next;
857 } else {
858 // Useless branch, memcmp error
859 fprintf(stderr, "ERROR Inserting to list");
860 destroy_list(interval_list);
861 return NULL;
862 }
863 }
864
865 if (conductor == NULL) {
866 // New interval at the end of list
867 if (insert_new_interval(end_of_list, &current_interval.low_ip, &current_interval.high_ip) == NULL) {
868 destroy_list(interval_list);
869 return NULL;
870 }
871
872 // Add new data to new end of list
873 end_of_list = end_of_list->next;
874
875 if (add_data(end_of_list->interval, networks[index]->data, networks[index]->data_len)) {
876 destroy_list(interval_list);
877 return NULL;
878 }
879 interval_counter++;
880
881 conductor = end_of_list;
882 }
883 }
884
885 // Alloc new interval array
886 ipps_interval_t *prefix_context = (ipps_interval_t *)malloc(interval_counter * sizeof(ipps_interval_t));
887 if (prefix_context == NULL) {
888 fprintf(stderr, "ERROR allocating memory for prefix interval_search_context\n");
889 destroy_list(interval_list);
890 return NULL;
891 }
892
893 // Fill interval array
894 // Hard copy intervals from list to array, duplicate data array pointer, free all list node
895 conductor = interval_list;
896 ipps_interval_t *array_iterator = prefix_context;
897 size_t size_of_pref_interval = sizeof(ipps_interval_t);
898 *context_counter = interval_counter;
899
900 // Iterate whole interval list
901 while (conductor != NULL) {
902 // Copy from list to array
903 memcpy(array_iterator, conductor->interval, size_of_pref_interval);
904 array_iterator++; // next interval in array
905
906 // Destroy list node, Don't destroy data!
907 interval_list = conductor->next;
908 free(conductor->interval);
909 free(conductor);
910 conductor = interval_list;
911 }
912
913 return prefix_context;
914}
915
928int ipps_search(ip_addr_t *ip, ipps_context_t *prefix_context, void ***data)
929{
930 int first, last, middle; // Array indexes
931
932 ipps_interval_t *interval_array; // Pointer to IPv4 or IPv6 interval array
933 uint8_t *middle_interval; // Pointer to first byte of current middle interval
934
935 int ip_high_cmp_result; // Result of comparing high IP of 2 intervals
936 int ip_low_cmp_result; // Result of comparing low IP of 2 intervals
937
938 void *ip_addr_start; // Ptr to first useful byte in ip_addr_t union, etc offset ui32[2] in IPv4
939
940 size_t ip_addr_len = sizeof(ip_addr_t);
941 size_t addr_cmp_len; // Number of compare bytes, 4 for IPv4, 16 for IPv6 (IP addr size)
942
943 size_t low_ip_offset; // Offset of 'low_ip' in 'ipps_interval_t' structure
944 size_t high_ip_offset; // Offset of 'high' in 'ipps_interval_t' structure
945
946 if (ip_is6(ip)) {
947 if (prefix_context->v6_count == 0) {
948 return 0;
949 }
950 first = 0;
951 last = prefix_context->v6_count - 1;
952 middle = (first + last)>>1;
953
954 interval_array = prefix_context->v6_prefix_intervals;
955
956 low_ip_offset = 0; // interval->low_ip is first member of struct
957 high_ip_offset = ip_addr_len; // interval->high_ip is second member of struct
958 addr_cmp_len = 16; // Compare length, 16 bytes for IPv6
959 ip_addr_start = (uint8_t *)ip;
960
961 } else {
962 if (prefix_context->v4_count == 0) {
963 return 0;
964 }
965 first = 0;
966 last = prefix_context->v4_count - 1;
967 middle = (first + last)>>1;
968
969 interval_array = prefix_context->v4_prefix_intervals;
970
971 low_ip_offset = 8; // low_ip.ui32[2]
972 high_ip_offset = ip_addr_len + 8; // high.ui32[2]
973 addr_cmp_len = 4; // Compare length, 4 bytes for IPv4
974
975 ip_addr_start = ((uint8_t *)ip) + 8; // ip.ui32[2]
976 }
977
978 while (first <= last ) {
979 middle_interval = (uint8_t *)(interval_array + middle);
980
981 ip_low_cmp_result = memcmp(middle_interval + low_ip_offset, ip_addr_start, addr_cmp_len);
982 ip_high_cmp_result = memcmp(middle_interval + high_ip_offset, ip_addr_start, addr_cmp_len);
983
984 if (ip_low_cmp_result <= 0 && ip_high_cmp_result >= 0) {
985 *data = ((ipps_interval_t *)middle_interval)->data_array;
986 return ((ipps_interval_t *)middle_interval)->data_cnt;
987 } else if (ip_high_cmp_result > 0) {
988 last = middle - 1;
989 } else {
990 first = middle + 1;
991 }
992 middle = (first + last) >> 1;
993 }
994 return 0;
995}
996
1004int free_data(ipps_interval_t *interval, void ***data_collector, uint32_t *data_coll_cnt )
1005{
1006 int j,k;
1007 void **tmp;
1008
1009 for (j = 0; j < interval->data_cnt; ++j) {
1010 for (k = 0; k < *data_coll_cnt; ++k) {
1011 if (interval->data_array[j] == (*data_collector)[k]) {
1012 interval->data_array[j] = NULL; // pointer has been freed
1013 break;
1014 }
1015 }
1016
1017 if (k == *data_coll_cnt) {
1018 // Data not match in data_collector, add data pointer to collector and free memory
1019 if (*data_coll_cnt >= COLLECTORSLOTS && *data_coll_cnt % COLLECTORSLOTS == 0) {
1020 tmp = realloc(*data_collector, ((*data_coll_cnt) + COLLECTORSLOTS) * sizeof(void *));
1021 if (tmp == NULL) {
1022 fprintf(stderr, "ERROR allocating memory for network mask array\n");
1023 return 1;
1024 }
1025 *data_collector = tmp;
1026 }
1027
1028 (*data_collector)[*data_coll_cnt] = interval->data_array[j]; // Add pointer to collector
1029 (*data_coll_cnt)++;
1030
1031 free(interval->data_array[j]); // free data
1032 }
1033 }
1034 free(interval->data_array); // free pointers to data
1035 return 0;
1036}
1037
1046{
1047 void **data_collector; // pointers to freed memory
1048 uint32_t data_collector_cnt = 0;
1049 ipps_interval_node_t *tmp_interval;
1050
1051 data_collector = malloc(COLLECTORSLOTS * sizeof(void *));
1052 if (data_collector == NULL) {
1053 fprintf(stderr, "ERROR allocating memory for freed data collector\n");
1054 return 1;
1055 }
1056
1057 while (interval_list != NULL) {
1058 tmp_interval = interval_list;
1059 interval_list = interval_list->next;
1060
1061 if (free_data(tmp_interval->interval, &data_collector, &data_collector_cnt)) {
1062 return 1;
1063 }
1064 free(tmp_interval->interval);
1065 free(tmp_interval);
1066 }
1067 free(data_collector);
1068
1069 return 0;
1070}
uint8_t ui8[16]
Definition ipaddr.h:109
uint32_t ui32[4]
Definition ipaddr.h:117
uint64_t ui64[2]
Definition ipaddr.h:121
INLINE_IMPL int ip_cmp(const ip_addr_t *addr1, const ip_addr_t *addr2)
Definition ipaddr.h:266
INLINE_IMPL int ip_is6(const ip_addr_t *addr)
Definition ipaddr.h:143
int ipps_destroy(ipps_context_t *prefix_context)
ipps_context_t * new_context()
ipps_interval_node_t * new_interval(const ip_addr_t *low_ip, const ip_addr_t *high_ip)
ipps_context_t * ipps_init(ipps_network_list_t *network_list)
void ip_inc(const ip_addr_t *ip, ip_addr_t *ip_inc)
void destroy_ip_v6_net_mask_array(uint32_t **net_mask_array)
uint8_t bit_endian_swap(uint8_t in)
int free_data(ipps_interval_t *interval, void ***data_collector, uint32_t *data_coll_cnt)
int cmp_net_v6(const void *v1, const void *v2)
int ipps_search(ip_addr_t *ip, ipps_context_t *prefix_context, void ***data)
ipps_interval_node_t * insert_new_interval(ipps_interval_node_t *position, const ip_addr_t *low_ip, const ip_addr_t *high_ip)
int destroy_list(ipps_interval_node_t *interval_list)
ipps_interval_t * init_context(ipps_network_t **networks, uint32_t network_count, uint32_t *context_counter, uint32_t **net_mask_array)
int add_data(ipps_interval_t *interval, void *data, size_t data_len)
void ip_dec(const ip_addr_t *ip, ip_addr_t *ip_dec)
int copy_all_data(ipps_interval_t *dest, ipps_interval_t *src)
void fill_interval_by_network(const ipps_network_t *net, ipps_interval_t *inter, uint32_t **net_mask_array)
int cmp_net_v4(const void *v1, const void *v2)
uint32_t ** create_ip_v6_net_mask_array()
void mask_ipv6(ip_addr_t *ip, uint32_t mask, ip_addr_t *masked_ipv6, uint32_t **net_mask_array)
Init context and prefix search.
ip_addr_t high_ip
High IP of interval.
ipps_interval_t * v4_prefix_intervals
Pointer to IPv4 intervals array.
ipps_interval_t * v6_prefix_intervals
Pointer to IPv6 intervals array.
uint32_t v6_count
Number of intervals in IPv6 array.
uint32_t data_cnt
Number of currently used data pointers in 'data_array'.
#define COLLECTORSLOTS
void * data
Pointer to same data.
#define DATASLOTS
size_t data_len
Number of bytes in 'data'.
uint32_t v4_count
Number of intervals in IPv4 array.
uint32_t net_count
Number of networks in 'networks' array.
#define NETWORKSLOTS
ipps_network_t * networks
Pointer to networks array.
ip_addr_t low_ip
Low IP of interval.
size_t array_len
Allocated size of 'data_array' => total available slots.
uint32_t mask
Network mask, CIDR notation, use for indexing.
void ** data_array
Array of pointers to data.
ip_addr_t addr
Network IP address.
Init context and prefix search - Internal functions and structures.
ipps_interval_t * interval
Pointer to interval structure.
struct ipps_interval_node * next
Next node in list, NULL if last node in list.