UniRec  3.0.0
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 
58 uint8_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 
114 void 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 
130 int 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 
153 int 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 
178 void 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 
290 void ip_dec(const ip_addr_t *ip, ip_addr_t *ip_dec)
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 
317 void ip_inc(const ip_addr_t *ip, ip_addr_t *ip_inc)
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 
343 int 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 
585 int 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 
632 ipps_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 
927 int 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 
1003 int 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_t * init_context(ipps_network_t **networks, uint32_t network_count, uint32_t *context_counter, uint32_t **net_mask_array)
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)
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 cmp_net_v6(const void *v1, const void *v2)
int ipps_search(ip_addr_t *ip, ipps_context_t *prefix_context, void ***data)
int destroy_list(ipps_interval_node_t *interval_list)
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()
ipps_interval_node_t * new_interval(const ip_addr_t *low_ip, const ip_addr_t *high_ip)
void mask_ipv6(ip_addr_t *ip, uint32_t mask, ip_addr_t *masked_ipv6, uint32_t **net_mask_array)
ipps_context_t * ipps_init(ipps_network_list_t *network_list)
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