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