1 /*
2 for tracking IP/port ranges
3 */
4 #include "massip-rangesv6.h"
5 #include "massip-rangesv4.h"
6 #include "util-malloc.h"
7 #include "logger.h"
8 #include "massip.h"
9 #include "massip-parse.h"
10
11 #include <assert.h>
12 #include <ctype.h>
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <string.h>
16 #include <stdint.h>
17
18 #define BUCKET_COUNT 16
19
20 #define REGRESS(i,x) if (!(x)) return (fprintf(stderr, "[-] %u: regression failed %s:%d\n", (unsigned)i, __FILE__, __LINE__)|1)
21 #ifndef false
22 #define false 0
23 #endif
24 #ifndef true
25 #define true 1
26 #endif
27
28 #define EQUAL(x,y) ipv6address_is_equal(x,y)
29
30 static inline ipv6address
_int128_add(ipv6address x,ipv6address y)31 _int128_add(ipv6address x, ipv6address y)
32 {
33 ipv6address result;
34 result.lo = x.lo + y.lo;
35 result.hi = x.hi + y.hi + (result.lo < x.lo);
36 return result;
37 }
38
39 static inline ipv6address
_int128_subtract(ipv6address x,ipv6address y)40 _int128_subtract(ipv6address x, ipv6address y)
41 {
42 ipv6address result;
43 result.lo = x.lo - y.lo;
44 result.hi = x.hi - y.hi - (result.lo > x.lo);
45 return result;
46 }
47
48 static ipv6address
_int128_add64(const ipv6address lhs,uint64_t rhs)49 _int128_add64(const ipv6address lhs, uint64_t rhs)
50 {
51 ipv6address result = lhs;
52 result.lo += rhs;
53 if (result.lo < lhs.lo)
54 result.hi++;
55 return result;
56 }
57
58 static inline massint128_t
_int128_mult64(massint128_t lhs,uint64_t rhs)59 _int128_mult64(massint128_t lhs, uint64_t rhs)
60 {
61 massint128_t result = {0,0};
62 uint64_t x;
63 uint64_t b;
64 uint64_t a;
65
66 /* low-order 32 */
67 a = (rhs>>0) & 0xFFFFFFFFULL;
68 b = (lhs.lo>>0) & 0xFFFFFFFFULL;
69 x = (a * b);
70 result.lo += x;
71
72 b = (lhs.lo>>32ULL) & 0xFFFFFFFFULL;
73 x = (a * b);
74 result.lo += x<<32ULL;
75 result.hi += x>>32ULL;
76
77 b = lhs.hi;
78 x = (a * b);
79 result.hi += x;
80
81 /* next 32 */
82 a = (rhs>>32ULL) & 0xFFFFFFFFULL;
83 b = (lhs.lo>>0ULL) & 0xFFFFFFFFULL;
84 x = (a * b);
85 result.lo += x<<32ULL;
86 result.hi += (x>>32ULL) + (result.lo < (x<<32ULL));
87
88 b = (lhs.lo>>32ULL) & 0xFFFFFFFFULL;
89 x = (a * b);
90 result.hi += x;
91
92 b = lhs.hi;
93 x = (a * b);
94 result.hi += x<<32ULL;
95
96 return result;
97 }
98
99 static int
LESS(const ipv6address lhs,const ipv6address rhs)100 LESS(const ipv6address lhs, const ipv6address rhs)
101 {
102 if (lhs.hi < rhs.hi)
103 return 1;
104 else if (lhs.hi == rhs.hi && lhs.lo < rhs.lo)
105 return 1;
106 else
107 return 0;
108 }
109 #define GREATEREQ(x,y) (!LESS(x,y))
110
111 static int
LESSEQ(const ipv6address lhs,const ipv6address rhs)112 LESSEQ(const ipv6address lhs, const ipv6address rhs)
113 {
114 if (lhs.hi < rhs.hi)
115 return 1;
116 if (lhs.hi > rhs.hi)
117 return 0;
118
119 if (lhs.lo <= rhs.lo)
120 return 1;
121 else
122 return 0;
123 }
124
range6_is_bad_address(const struct Range6 * range)125 int range6_is_bad_address(const struct Range6 *range)
126 {
127 return LESS(range->end, range->begin);
128 }
129
130 static int
_int128_is_equals(const ipv6address lhs,const ipv6address rhs)131 _int128_is_equals(const ipv6address lhs, const ipv6address rhs)
132 {
133 return lhs.hi == rhs.hi && lhs.lo == rhs.lo;
134 }
135
136 static ipv6address
MINUS_ONE(const ipv6address ip)137 MINUS_ONE(const ipv6address ip)
138 {
139 ipv6address result;
140
141 if (ip.lo == 0) {
142 result.hi = ip.hi - 1;
143 result.lo = ~0ULL;
144 } else {
145 result.hi = ip.hi;
146 result.lo = ip.lo - 1;
147 }
148
149 return result;
150 }
151
PLUS_ONE(const ipv6address ip)152 static ipv6address PLUS_ONE(const ipv6address ip)
153 {
154 ipv6address result;
155
156 if (ip.lo == ~0) {
157 result.hi = ip.hi + 1;
158 result.lo = 0;
159 } else {
160 result.hi = ip.hi;
161 result.lo = ip.lo + 1;
162 }
163
164 return result;
165 }
166
167 /***************************************************************************
168 ***************************************************************************/
169 massint128_t
massip_range(struct MassIP * massip)170 massip_range(struct MassIP *massip)
171 {
172 massint128_t result;
173
174
175 result = range6list_count(&massip->ipv6);
176 result = _int128_add64(result, rangelist_count(&massip->ipv4));
177 result = _int128_mult64(result, rangelist_count(&massip->ports));
178
179 return result;
180 }
181
182 /***************************************************************************
183 ***************************************************************************/
184 int
range6list_is_contains(const struct Range6List * targets,const ipv6address ip)185 range6list_is_contains(const struct Range6List *targets, const ipv6address ip)
186 {
187 unsigned i;
188
189 for (i=0; i<targets->count; i++) {
190 struct Range6 *range = &targets->list[i];
191
192 if (LESSEQ(range->begin, ip) && LESSEQ(ip, range->end))
193 return 1;
194 }
195 return 0;
196 }
197
198 /***************************************************************************
199 * ???
200 ***************************************************************************/
201 static void
todo_remove_at(struct Range6List * targets,unsigned index)202 todo_remove_at(struct Range6List *targets, unsigned index)
203 {
204 memmove(&targets->list[index],
205 &targets->list[index+1],
206 (targets->count - index) * sizeof(targets->list[index])
207 );
208 targets->count--;
209 }
210
211
212 /***************************************************************************
213 * Test if two ranges overlap.
214 * This is easiest done by testing that they don't overlap, and inverting
215 * the result.
216 * Note that adjacent addresses overlap.
217 ***************************************************************************/
218 static int
range6_is_overlap(const struct Range6 lhs,const struct Range6 rhs)219 range6_is_overlap(const struct Range6 lhs, const struct Range6 rhs)
220 {
221 static const ipv6address FFFF = {~0ULL, ~0ULL};
222
223 if (LESS(lhs.begin, rhs.begin)) {
224 if (EQUAL(lhs.end, FFFF) || GREATEREQ(PLUS_ONE(lhs.end), rhs.begin))
225 return 1;
226 }
227 if (GREATEREQ(lhs.begin, rhs.begin)) {
228 if (LESSEQ(lhs.end, rhs.end))
229 return 1;
230 }
231
232 if (LESS(rhs.begin, lhs.begin)) {
233 if (EQUAL(rhs.end, FFFF) || GREATEREQ(PLUS_ONE(rhs.end), lhs.begin))
234 return 1;
235 }
236 if (GREATEREQ(rhs.begin, lhs.begin)) {
237 if (LESSEQ(rhs.end, lhs.end))
238 return 1;
239 }
240
241 return 0;
242 #if 0
243 static const ipv6address zero = {0, 0};
244 ipv6address lhs_endm = MINUS_ONE(lhs.end);
245 ipv6address rhs_endm = MINUS_ONE(rhs.end);
246
247 /* llll rrrr */
248 if (LESS(zero, lhs.end) && LESS(lhs_endm, rhs.begin))
249 return 0;
250
251 /* rrrr llll */
252 if (LESS(zero, rhs.end) && LESS(rhs_endm, lhs.begin))
253 return 0;
254
255 return 1;
256 #endif
257 }
258
259
260 /***************************************************************************
261 * Combine two ranges, such as when they overlap.
262 ***************************************************************************/
263 static void
range6_combine(struct Range6 * lhs,const struct Range6 rhs)264 range6_combine(struct Range6 *lhs, const struct Range6 rhs)
265 {
266 if (LESSEQ(rhs.begin, lhs->begin))
267 lhs->begin = rhs.begin;
268 if (LESSEQ(lhs->end, rhs.end))
269 lhs->end = rhs.end;
270 }
271
272
273 /***************************************************************************
274 * Callback for qsort() for comparing two ranges
275 ***************************************************************************/
276 static int
range6_compare(const void * lhs,const void * rhs)277 range6_compare(const void *lhs, const void *rhs)
278 {
279 struct Range6 *left = (struct Range6 *)lhs;
280 struct Range6 *right = (struct Range6 *)rhs;
281
282 if (ipv6address_is_equal(left->begin, right->begin))
283 return 0;
284 else if (LESS(left->begin, right->begin))
285 return -1;
286 else
287 return 1;
288 }
289
290
291 /***************************************************************************
292 ***************************************************************************/
293 void
range6list_sort(struct Range6List * targets)294 range6list_sort(struct Range6List *targets)
295 {
296 size_t i;
297 struct Range6List newlist = {0};
298 size_t original_count = targets->count;
299
300 /* Empty lists are, of course, sorted. We need to set this
301 * to avoid an error later on in the code which asserts that
302 * the lists are sorted */
303 if (targets->count == 0) {
304 targets->is_sorted = 1;
305 return;
306 }
307
308 /* If it's already sorted, then skip this */
309 if (targets->is_sorted) {
310 return;
311 }
312
313
314 /* First, sort the list */
315 LOG(3, "[+] range6:sort: sorting...\n");
316 qsort( targets->list, /* the array to sort */
317 targets->count, /* number of elements to sort */
318 sizeof(targets->list[0]), /* size of element */
319 range6_compare);
320
321
322 /* Second, combine all overlapping ranges. We do this by simply creating
323 * a new list from a sorted list, so we don't have to remove things in the
324 * middle when collapsing overlapping entries together, which is painfully
325 * slow. */
326 LOG(3, "[+] range:sort: combining...\n");
327 for (i=0; i<targets->count; i++) {
328 range6list_add_range(&newlist, targets->list[i].begin, targets->list[i].end);
329 }
330
331 LOG(3, "[+] range:sort: combined from %u elements to %u elements\n", original_count, newlist.count);
332 free(targets->list);
333 targets->list = newlist.list;
334 targets->count = newlist.count;
335 newlist.list = 0;
336
337 LOG(2, "[+] range:sort: done...\n");
338
339 targets->is_sorted = 1;
340 }
341
342
343
344 void
range6list_add_range(struct Range6List * targets,ipv6address begin,ipv6address end)345 range6list_add_range(struct Range6List *targets, ipv6address begin, ipv6address end)
346 {
347 struct Range6 range;
348
349 range.begin = begin;
350 range.end = end;
351
352 /* auto-expand the list if necessary */
353 if (targets->count + 1 >= targets->max) {
354 targets->max = targets->max * 2 + 1;
355 targets->list = REALLOCARRAY(targets->list, targets->max, sizeof(targets->list[0]));
356 }
357
358 /* If empty list, then add this one */
359 if (targets->count == 0) {
360 targets->list[0] = range;
361 targets->count++;
362 targets->is_sorted = 1;
363 return;
364 }
365
366 /* If new range overlaps the last range in the list, then combine it
367 * rather than appending it. This is an optimization for the fact that
368 * we often read in sequential addresses */
369 if (range6_is_overlap(targets->list[targets->count - 1], range)) {
370 range6_combine(&targets->list[targets->count - 1], range);
371 targets->is_sorted = 0;
372 return;
373 }
374
375 /* append to the end of our list */
376 targets->list[targets->count] = range;
377 targets->count++;
378 targets->is_sorted = 0;
379 }
380
381 /***************************************************************************
382 ***************************************************************************/
383 void
range6list_remove_all(struct Range6List * targets)384 range6list_remove_all(struct Range6List *targets)
385 {
386 if (targets->list)
387 free(targets->list);
388 if (targets->picker)
389 free(targets->picker);
390 memset(targets, 0, sizeof(*targets));
391 }
392
393 /***************************************************************************
394 ***************************************************************************/
395 void
range6list_merge(struct Range6List * list1,const struct Range6List * list2)396 range6list_merge(struct Range6List *list1, const struct Range6List *list2)
397 {
398 unsigned i;
399
400 for (i=0; i<list2->count; i++) {
401 range6list_add_range(list1, list2->list[i].begin, list2->list[i].end);
402 }
403 }
404
405 /***************************************************************************
406 ***************************************************************************/
407 void
range6list_remove_range(struct Range6List * targets,const ipv6address begin,const ipv6address end)408 range6list_remove_range(struct Range6List *targets, const ipv6address begin, const ipv6address end)
409 {
410 unsigned i;
411 struct Range6 x;
412
413 x.begin = begin;
414 x.end = end;
415
416 /* See if the range overlaps any exist range already in the
417 * list */
418 for (i = 0; i < targets->count; i++) {
419 if (!range6_is_overlap(targets->list[i], x))
420 continue;
421
422 /* If the removal-range wholly covers the range, delete
423 * it completely */
424 if (LESSEQ(begin, targets->list[i].begin) && LESSEQ(targets->list[i].end, end)) {
425 todo_remove_at(targets, i);
426 i--;
427 continue;
428 }
429
430 /* If the removal-range bisects the target-rage, truncate
431 * the lower end and add a new high-end */
432 if (LESSEQ(targets->list[i].begin, begin) && LESSEQ(end, targets->list[i].end)) {
433 struct Range6 newrange;
434
435 newrange.begin = PLUS_ONE(end);
436 newrange.end = targets->list[i].end;
437
438
439 targets->list[i].end = MINUS_ONE(begin);
440
441 range6list_add_range(targets, newrange.begin, newrange.end);
442 i--;
443 continue;
444 }
445
446 /* If overlap on the lower side */
447 if (LESSEQ(targets->list[i].begin, end) && LESSEQ(end, targets->list[i].end)) {
448 targets->list[i].begin = PLUS_ONE(end);
449 }
450
451 /* If overlap on the upper side */
452 if (LESSEQ(targets->list[i].begin, begin) && LESSEQ(begin, targets->list[i].end)) {
453 targets->list[i].end = MINUS_ONE(begin);
454 }
455 }
456 }
457
458 void
range6list_remove_range2(struct Range6List * targets,struct Range6 range)459 range6list_remove_range2(struct Range6List *targets, struct Range6 range)
460 {
461 range6list_remove_range(targets, range.begin, range.end);
462 }
463
464 /***************************************************************************
465 ***************************************************************************/
466 ipv6address
range6list_exclude(struct Range6List * targets,const struct Range6List * excludes)467 range6list_exclude( struct Range6List *targets,
468 const struct Range6List *excludes)
469 {
470 ipv6address count = {0,0};
471 unsigned i;
472
473 for (i=0; i<excludes->count; i++) {
474 struct Range6 range = excludes->list[i];
475 ipv6address x;
476
477 x = _int128_subtract(range.end, range.begin);
478 x = _int128_add64(x, 1);
479
480 count = _int128_add(count, x);
481 range6list_remove_range(targets, range.begin, range.end);
482 }
483
484 return count;
485 }
486
487
488 /***************************************************************************
489 ***************************************************************************/
490 massint128_t
range6list_count(const struct Range6List * targets)491 range6list_count(const struct Range6List *targets)
492 {
493 unsigned i;
494 ipv6address result = {0,0};
495
496 for (i=0; i<targets->count; i++) {
497 ipv6address x;
498
499 x = _int128_subtract(targets->list[i].end, targets->list[i].begin);
500 if (x.hi == ~0ULL && x.lo == ~0ULL)
501 return x; /* overflow */
502 x = _int128_add64(x, 1);
503 result = _int128_add(result, x);
504 }
505
506 return result;
507 }
508
509
510 /***************************************************************************
511 ***************************************************************************/
512 ipv6address
range6list_pick(const struct Range6List * targets,uint64_t index)513 range6list_pick(const struct Range6List *targets, uint64_t index)
514 {
515 size_t maxmax = targets->count;
516 size_t min = 0;
517 size_t max = targets->count;
518 size_t mid;
519 const size_t *picker = targets->picker;
520
521 if (picker == NULL) {
522 fprintf(stderr, "[-] ipv6 picker is null\n");
523 exit(1);
524 }
525
526
527 for (;;) {
528 mid = min + (max-min)/2;
529 if (index < picker[mid]) {
530 max = mid;
531 continue;
532 } if (index >= picker[mid]) {
533 if (mid + 1 == maxmax)
534 break;
535 else if (index < picker[mid+1])
536 break;
537 else
538 min = mid+1;
539 }
540 }
541
542 return _int128_add64(targets->list[mid].begin, (index - picker[mid]));
543 }
544
545
546 /***************************************************************************
547 * The normal "pick" function is a linear search, which is slow when there
548 * are a lot of ranges. Therefore, the "pick2" creates sort of binary
549 * search that'll be a lot faster. We choose "binary search" because
550 * it's the most cache-efficient, having the least overhead to fit within
551 * the cache.
552 ***************************************************************************/
553 void
range6list_optimize(struct Range6List * targets)554 range6list_optimize(struct Range6List *targets)
555 {
556 size_t *picker;
557 size_t i;
558 ipv6address total = {0,0};
559
560 if (targets->count == 0)
561 return;
562
563 /* This technique only works when the targets are in
564 * ascending order */
565 if (!targets->is_sorted)
566 range6list_sort(targets);
567
568 if (targets->picker)
569 free(targets->picker);
570
571 picker = REALLOCARRAY(NULL, targets->count, sizeof(*picker));
572
573 for (i=0; i<targets->count; i++) {
574 ipv6address x;
575 picker[i] = total.lo;
576 x = _int128_subtract(targets->list[i].end, targets->list[i].begin);
577 x = _int128_add64(x, 1);
578 total = _int128_add(total, x);
579 }
580
581 targets->picker = picker;
582 }
583
584
585
586 /***************************************************************************
587 * Provide my own rand() simply to avoid static-analysis warning me that
588 * 'rand()' is unrandom, when in fact we want the non-random properties of
589 * rand() for regression testing.
590 ***************************************************************************/
591 static unsigned
r_rand(unsigned * seed)592 r_rand(unsigned *seed)
593 {
594 static const unsigned a = 214013;
595 static const unsigned c = 2531011;
596
597 *seed = (*seed) * a + c;
598 return (*seed)>>16 & 0x7fff;
599 }
600
601 /***************************************************************************
602 ***************************************************************************/
603 static int
regress_pick2()604 regress_pick2()
605 {
606 unsigned i;
607 unsigned seed = 0;
608
609 /*
610 */
611 for (i=0; i<65536; i++)
612 {
613 ipv6address a;
614 ipv6address b;
615 ipv6address c;
616 ipv6address d;
617
618 a.hi = r_rand(&seed);
619 a.lo = (unsigned long long)r_rand(&seed)<<49ULL;
620 b.hi = r_rand(&seed);
621 b.lo = 0x8765432100000000ULL;
622
623 c = _int128_add(a, b);
624 d = _int128_subtract(c, b);
625
626 if (!_int128_is_equals(a, d)) {
627 fprintf(stderr, "[-] %s:%d: test failed (%u)\n", __FILE__, __LINE__, (unsigned)i);
628 return 1;
629 }
630 }
631
632 /*
633 * Run 100 randomized regression tests
634 */
635 for (i=3; i<100; i++) {
636 unsigned j;
637 unsigned num_targets;
638 ipv6address begin = {0};
639 ipv6address end = {0};
640 struct Range6List targets[1];
641 struct Range6List duplicate[1];
642 uint64_t range;
643 ipv6address x;
644
645 seed = i;
646
647 /* Create a new target list */
648 memset(targets, 0, sizeof(targets[0]));
649
650 /* fill the target list with random ranges */
651 num_targets = r_rand(&seed)%5 + 1;
652 for (j=0; j<num_targets; j++) {
653 begin.lo += r_rand(&seed)%10;
654 end.lo = begin.lo + r_rand(&seed)%10;
655
656 range6list_add_range(targets, begin, end);
657 }
658
659 /* Optimize for faster 'picking' addresses from an index */
660 range6list_optimize(targets);
661
662
663 /* Duplicate the targetlist using the picker */
664 memset(duplicate, 0, sizeof(duplicate[0]));
665 x = range6list_count(targets);
666 if (x.hi) {
667 fprintf(stderr, "[-] range6: range too big\n");
668 return 1;
669 }
670 range = x.lo;
671 for (j=0; j<range; j++) {
672 ipv6address addr;
673
674 addr = range6list_pick(targets, j);
675 range6list_add_range(duplicate, addr, addr);
676 }
677
678 /* at this point, the two range lists shouild be identical */
679 REGRESS(i, targets->count == duplicate->count);
680 REGRESS(i, memcmp(targets->list, duplicate->list, targets->count*sizeof(targets->list[0])) == 0);
681
682 range6list_remove_all(targets);
683 range6list_remove_all(duplicate);
684 }
685
686 return 0;
687 }
688
689
690
691
692
693 /***************************************************************************
694 * Called during "make regress" to run a regression test over this module.
695 ***************************************************************************/
696 int
ranges6_selftest(void)697 ranges6_selftest(void)
698 {
699 struct Range6 r;
700 struct Range6List targets[1];
701 int err;
702
703 REGRESS(0, regress_pick2() == 0);
704
705 memset(targets, 0, sizeof(targets[0]));
706 #define ERROR() fprintf(stderr, "selftest: failed %s:%u\n", __FILE__, __LINE__);
707
708 err = massip_parse_range("2001:0db8:85a3:0000:0000:8a2e:0370:7334", 0, 0, 0, &r);
709 if (err != Ipv6_Address)
710 ERROR();
711
712 /* test for the /0 CIDR block, since we'll be using that a lot to scan the entire
713 * Internet */
714 if (r.begin.hi != 0x20010db885a30000ULL)
715 return 1;
716 if (r.begin.lo != 0x00008a2e03707334ULL)
717 return 1;
718
719 return 0;
720 }
721
722