UniRec  3.3.2
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  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 
115 void 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 
131 int 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 
154 int 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 
179 void 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 
291 void ip_dec(const ip_addr_t *ip, ip_addr_t *ip_dec)
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 
318 void ip_inc(const ip_addr_t *ip, ip_addr_t *ip_inc)
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 
344 int 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 
586 int 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 
633 ipps_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 
928 int 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 
1004 int 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_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