1 #if HAVE_CONFIG_H
2 #include "config.h"
3 #endif
4
5 #include <ctype.h>
6 #include <errno.h>
7 #include <stdio.h>
8 #include <stdlib.h>
9 #include <string.h>
10 #include <strings.h>
11
12 #include "sx_prefix.h"
13 #include "sx_report.h"
14
15 int debug_aggregation=0;
16 extern int debug_expander;
17
18 struct sx_prefix*
sx_prefix_alloc(struct sx_prefix * p)19 sx_prefix_alloc(struct sx_prefix* p)
20 {
21 struct sx_prefix* sp=malloc(sizeof(struct sx_prefix));
22 if(!sp) return NULL;
23 if(p) {
24 *sp=*p;
25 } else {
26 memset(sp,0,sizeof(struct sx_prefix));
27 };
28 return sp;
29 };
30 void
sx_prefix_destroy(struct sx_prefix * p)31 sx_prefix_destroy(struct sx_prefix* p)
32 {
33 if(p) free(p);
34 };
35
36 void
sx_prefix_adjust_masklen(struct sx_prefix * p)37 sx_prefix_adjust_masklen(struct sx_prefix* p)
38 {
39 int nbytes=(p->family==AF_INET?4:16);
40 int i;
41 if(p->masklen==nbytes*8) return ; /* mask is all ones */
42 for(i=nbytes-1;i>p->masklen/8;i--) {
43 p->addr.addrs[i]=0;
44 };
45 for(i=1;i<=8-p->masklen%8;i++) {
46 p->addr.addrs[p->masklen/8]&=(0xff<<i);
47 };
48 };
49
50 void
sx_prefix_mask(struct sx_prefix * p,struct sx_prefix * q)51 sx_prefix_mask(struct sx_prefix* p, struct sx_prefix* q)
52 {
53 int i;
54 memset(q->addr.addrs, 0, sizeof(q->addr.addrs));
55 q->family=p->family;
56 q->masklen=p->masklen;
57 for(i=0;i<p->masklen/8;i++)
58 q->addr.addrs[i]=0xff;
59 for(i=1;i<=p->masklen%8;i++)
60 q->addr.addrs[p->masklen/8]|=(1<<(8-i));
61 };
62
63 void
sx_prefix_imask(struct sx_prefix * p,struct sx_prefix * q)64 sx_prefix_imask(struct sx_prefix* p, struct sx_prefix* q)
65 {
66 int i;
67 memset(q->addr.addrs, 0xff, sizeof(q->addr.addrs));
68 q->family=p->family;
69 q->masklen=p->masklen;
70 for(i=0;i<p->masklen/8;i++)
71 q->addr.addrs[i]=0;
72 for(i=1;i<=p->masklen%8;i++)
73 q->addr.addrs[p->masklen/8]&=~(1<<(8-i));
74 };
75
76
77 int
sx_prefix_parse(struct sx_prefix * p,int af,char * text)78 sx_prefix_parse(struct sx_prefix* p, int af, char* text)
79 {
80 char* c=NULL;
81 int masklen, ret;
82 char mtext[INET6_ADDRSTRLEN+5];
83 strlcpy(mtext, text, sizeof(mtext));
84
85 c=strchr(mtext,'/');
86 if(c) {
87 char* eod;
88 *c=0;
89 masklen=strtol(c+1,&eod,10);
90 if(eod && eod[0] && !isspace(eod[0])) {
91 *c='/';
92 sx_report(SX_ERROR,"Invalid masklen in prefix %s\n", text);
93 goto fixups;
94 };
95 } else {
96 masklen=-1;
97 };
98
99 if(!af) {
100 if(strchr(mtext,':')) af=AF_INET6;
101 else
102 af=AF_INET;
103 };
104
105 ret = inet_pton(af, mtext, &p->addr);
106 if(ret != 1) {
107 int aparts[4];
108 /* contrary to documentation (man inet_ntop on FreeBSD),
109 addresses with leading zeros are not parsed correctly. Try to
110 workaround this issue manually */
111 if (af==AF_INET && sscanf(mtext, "%i.%i.%i.%i", aparts,
112 aparts+1, aparts+2, aparts+3) == 4 && aparts[0]>=0 &&
113 aparts[0]<256 && aparts[1]>=0 && aparts[1]<256 &&
114 aparts[2]>=0 && aparts[2]<256 && aparts[3]>=0 &&
115 aparts[3]<256) {
116 p->addr.addr.s_addr = htonl((aparts[0]<<24) +
117 (aparts[1]<<16) + (aparts[2]<<8) + aparts[3]);
118 } else {
119 if(c) *c='/';
120 sx_report(SX_ERROR,"Unable to parse prefix '%s', af=%i (%s), "
121 "ret=%i\n", mtext, af, af==AF_INET ? "inet" : "inet6", ret);
122 goto fixups;
123 };
124 };
125
126 if(af==AF_INET) {
127 if(masklen==-1) p->masklen=32;
128 else {
129 if(masklen<0 || masklen>32) {
130 p->masklen=32;
131 } else {
132 p->masklen=masklen;
133 };
134 };
135 } else if(af==AF_INET6) {
136 if(masklen==-1) p->masklen=128;
137 else {
138 if(masklen<0 || masklen>128) {
139 p->masklen=128;
140 } else {
141 p->masklen=masklen;
142 };
143 };
144 } else {
145 sx_report(SX_ERROR,"Invalid address family %i\n", af);
146 goto fixups;
147 };
148
149 p->family=af;
150 sx_prefix_adjust_masklen(p);
151 if(c) *c='/';
152
153 return 1;
154 fixups:
155 return 0;
156 };
157
158 int
sx_prefix_isbitset(struct sx_prefix * p,int n)159 sx_prefix_isbitset(struct sx_prefix* p, int n)
160 {
161 unsigned char s;
162 /* bits outside the prefix considered unset */
163 if(p->family==AF_INET && (n<0 || n>32)) return 0;
164 else if(p->family==AF_INET6 && (n<0 || n>128)) return 0;
165 s=p->addr.addrs[(n-1)/8];
166 return (s&(0x80>>((n-1)%8)))?1:0;
167 };
168
169 void
sx_prefix_setbit(struct sx_prefix * p,int n)170 sx_prefix_setbit(struct sx_prefix* p, int n)
171 {
172 unsigned char* s;
173 if (p->family == AF_INET && (n<0 || n>32)) return;
174 else if (p->family == AF_INET6 && (n<0 || n>128)) return;
175 s=p->addr.addrs+(n-1)/8;
176 (*s)|=0x80>>((n-1)%8);
177 };
178
179
180 int
sx_radix_tree_insert_specifics(struct sx_radix_tree * t,struct sx_prefix p,unsigned min,unsigned max)181 sx_radix_tree_insert_specifics(struct sx_radix_tree* t, struct sx_prefix p,
182 unsigned min, unsigned max)
183 {
184 if (p.masklen >= min)
185 sx_radix_tree_insert(t, &p);
186 if (p.masklen+1 > max)
187 return 1;
188 p.masklen+=1;
189 sx_radix_tree_insert_specifics(t, p, min, max);
190 sx_prefix_setbit(&p, p.masklen);
191 sx_radix_tree_insert_specifics(t, p, min, max);
192 return 1;
193 };
194
195 int
sx_prefix_range_parse(struct sx_radix_tree * tree,int af,int maxlen,char * text)196 sx_prefix_range_parse(struct sx_radix_tree* tree, int af, int maxlen,
197 char* text)
198 {
199 char* d=strchr(text, '^');
200 struct sx_prefix p;
201 unsigned long min, max;
202
203 if (!d || !d[1]) return 0;
204 *d = 0;
205
206 if (!sx_prefix_parse(&p, 0, text)) {
207 sx_report(SX_ERROR, "Unable to parse prefix %s^%s\n", text, d+1);
208 return 0;
209 };
210 *d = '^';
211 if (af && p.family != af) {
212 SX_DEBUG(debug_expander, "Ignoring prefix %s, wrong af %i\n", text,
213 p.family);
214 return 0;
215 };
216 if (maxlen && p.masklen > maxlen) {
217 SX_DEBUG(debug_expander, "Ignoring prefix %s, masklen %i > max "
218 "masklen %u\n", text, p.masklen, maxlen);
219 return 0;
220 };
221 if (d[1] == '-') {
222 min=p.masklen+1;
223 max=maxlen;
224 } else if (d[1] == '+') {
225 min=p.masklen;
226 max=maxlen;
227 } else if (isdigit(d[1])) {
228 char* dm = NULL;
229 min = strtoul(d+1, &dm, 10);
230 if (dm && *dm == '-' && isdigit(dm[1])) {
231 max = strtoul(dm+1, NULL, 10);
232 } else if (dm && *dm) {
233 sx_report(SX_ERROR, "Unable to parse prefix-range %s\n", text);
234 return 0;
235 };
236 } else {
237 sx_report(SX_ERROR, "Invalid prefix-range %s\n", text);
238 return 0;
239 };
240 if (min < p.masklen) {
241 sx_report(SX_ERROR, "Invalid prefix-range %s: min %lu < masklen %u\n",
242 text, min, p.masklen);
243 return 0;
244 };
245 if (af == AF_INET && max > 32) {
246 sx_report(SX_ERROR, "Invalid prefix-range %s: max %lu > 32\n",
247 text, max);
248 return 0;
249 } else if (af == AF_INET6 && max > 128) {
250 sx_report(SX_ERROR, "Invalid ipv6 prefix-range %s: max %lu > 128\n",
251 text, max);
252 return 0;
253 };
254 if (max > maxlen)
255 max = maxlen;
256 SX_DEBUG(debug_expander, "parsed prefix-range %s as %lu-%lu (maxlen: %u)\n",
257 text, min, max, maxlen);
258 sx_radix_tree_insert_specifics(tree, p, min, max);
259 return 1;
260 };
261
262 struct sx_prefix*
sx_prefix_new(int af,char * text)263 sx_prefix_new(int af, char* text)
264 {
265 struct sx_prefix* p=NULL;
266
267 if(!text) return NULL;
268
269 p=sx_prefix_alloc(NULL);
270
271 if(!p) return NULL;
272 if(!sx_prefix_parse(p,af,text)) {
273 sx_prefix_destroy(p);
274 return NULL;
275 };
276 return p;
277 };
278
279 int
sx_prefix_fprint(FILE * f,struct sx_prefix * p)280 sx_prefix_fprint(FILE* f, struct sx_prefix* p)
281 {
282 char buffer[128];
283 if(!p) {
284 fprintf(f?f:stdout,"(null)");
285 return 0;
286 };
287 inet_ntop(p->family,&p->addr,buffer,sizeof(buffer));
288 return fprintf(f?f:stdout,"%s/%i",buffer,p->masklen);
289 };
290
291 int
sx_prefix_snprintf_sep(struct sx_prefix * p,char * rbuffer,int srb,char * sep)292 sx_prefix_snprintf_sep(struct sx_prefix* p, char* rbuffer, int srb, char* sep)
293 {
294 char buffer[128];
295 if(!sep) sep="/";
296 if(!p) {
297 snprintf(rbuffer,srb,"(null)");
298 return 0;
299 };
300 inet_ntop(p->family,&p->addr,buffer,sizeof(buffer));
301 return snprintf(rbuffer,srb,"%s%s%i",buffer,sep,p->masklen);
302 };
303
304 int
sx_prefix_snprintf(struct sx_prefix * p,char * rbuffer,int srb)305 sx_prefix_snprintf(struct sx_prefix* p, char* rbuffer, int srb)
306 {
307 return sx_prefix_snprintf_sep(p, rbuffer, srb, "/");
308 };
309
310 int
sx_prefix_snprintf_fmt(struct sx_prefix * p,char * buffer,int size,const char * name,const char * format)311 sx_prefix_snprintf_fmt(struct sx_prefix* p, char* buffer, int size,
312 const char* name, const char* format)
313 {
314 unsigned off=0;
315 const char* c=format;
316 struct sx_prefix q;
317 while(*c) {
318 if(*c=='%') {
319 switch(*(c+1)) {
320 case 'r':
321 case 'n':
322 inet_ntop(p->family,&p->addr,buffer+off,size-off);
323 off=strlen(buffer);
324 break;
325 case 'l':
326 off+=snprintf(buffer+off,size-off,"%i",p->masklen);
327 break;
328 case '%':
329 buffer[off++]='%';
330 break;
331 case 'N':
332 off+=snprintf(buffer+off,size-off,"%s",name);
333 break;
334 case 'm':
335 sx_prefix_mask(p, &q);
336 inet_ntop(p->family,&q.addr,buffer+off,size-off);
337 off=strlen(buffer);
338 break;
339 case 'i':
340 sx_prefix_imask(p, &q);
341 inet_ntop(p->family,&q.addr,buffer+off,size-off);
342 off=strlen(buffer);
343 break;
344 default :
345 sx_report(SX_ERROR, "Unknown format char '%c'\n", *(c+1));
346 return 0;
347 };
348 c+=2;
349 } else if (*c=='\\') {
350 switch(*(c+1)) {
351 case 'n':
352 buffer[off++]='\n'; break;
353 case 't':
354 buffer[off++]='\t'; break;
355 case '\\':
356 buffer[off++]='\\'; break;
357 default:
358 buffer[off++]=*(c+1);
359 break;
360 };
361 c+=2;
362 } else {
363 buffer[off++]=*c;
364 c++;
365 };
366 };
367 return strlen(buffer);
368 };
369
370 int
sx_prefix_jsnprintf(struct sx_prefix * p,char * rbuffer,int srb)371 sx_prefix_jsnprintf(struct sx_prefix* p, char* rbuffer, int srb)
372 {
373 char buffer[128];
374 if(!p) {
375 snprintf(rbuffer,srb,"(null)");
376 return 0;
377 };
378 inet_ntop(p->family,&p->addr,buffer,sizeof(buffer));
379 return snprintf(rbuffer,srb,"%s\\/%i",buffer,p->masklen);
380 };
381
382 struct sx_radix_tree*
sx_radix_tree_new(int af)383 sx_radix_tree_new(int af)
384 {
385 struct sx_radix_tree* rt=malloc(sizeof(struct sx_radix_tree));
386 if(!rt) {
387 return NULL;
388 };
389 memset(rt,0,sizeof(struct sx_radix_tree));
390 rt->family=af;
391 return rt;
392 };
393
394 int
sx_radix_tree_empty(struct sx_radix_tree * t)395 sx_radix_tree_empty(struct sx_radix_tree* t)
396 {
397 return t->head == NULL;
398 };
399
400 struct sx_radix_node*
sx_radix_node_new(struct sx_prefix * prefix)401 sx_radix_node_new(struct sx_prefix* prefix)
402 {
403 struct sx_radix_node* rn=malloc(sizeof(struct sx_radix_node));
404 if(!rn) return NULL;
405 memset(rn,0,sizeof(struct sx_radix_node));
406 if(prefix) {
407 rn->prefix=*prefix; /* structure copy */
408 };
409 return rn;
410 };
411
412 int
sx_prefix_eqbits(struct sx_prefix * a,struct sx_prefix * b)413 sx_prefix_eqbits(struct sx_prefix* a, struct sx_prefix* b)
414 {
415 int i;
416 int nbytes=(a->family==AF_INET?4:16);
417 for(i=0;i<nbytes;i++) {
418 if(a->addr.addrs[i]==b->addr.addrs[i]) continue;
419 else {
420 int j;
421 for(j=0;j<8 && i*8+j<=a->masklen && i*8+j<=b->masklen;j++) {
422 if((a->addr.addrs[i]&(0x80>>j))!=(b->addr.addrs[i]&(0x80>>j)))
423 return i*8+j;
424 };
425 };
426 };
427 if(a->masklen<b->masklen) return a->masklen;
428 return b->masklen;
429 };
430
431 struct sx_prefix*
sx_prefix_overlay(struct sx_prefix * p,int n)432 sx_prefix_overlay(struct sx_prefix* p, int n)
433 {
434 struct sx_prefix* sp=sx_prefix_alloc(p);
435 sp->masklen=n;
436 sx_prefix_adjust_masklen(sp);
437 return sp;
438 };
439
440 void
sx_radix_tree_unlink(struct sx_radix_tree * tree,struct sx_radix_node * node)441 sx_radix_tree_unlink(struct sx_radix_tree* tree, struct sx_radix_node* node)
442 {
443 next:
444 if(node->r && node->l) {
445 node->isGlue=1;
446 } else if(node->r) {
447 if(node->parent) {
448 if(node->parent->r==node) {
449 node->parent->r=node->r;
450 node->r->parent=node->parent;
451 } else if(node->parent->l==node) {
452 node->parent->l=node->r;
453 node->r->parent=node->parent;
454 } else {
455 sx_report(SX_ERROR,"Unlinking node which is not descendant "
456 "of its parent\n");
457 };
458 } else if(tree->head==node) {
459 /* only one case, really */
460 tree->head=node->r;
461 node->r->parent=NULL;
462 } else {
463 sx_report(SX_ERROR,"Unlinking node with no parent and not root\n");
464 };
465 return;
466 } else if(node->l) {
467 if(node->parent) {
468 if(node->parent->r==node) {
469 node->parent->r=node->l;
470 node->l->parent=node->parent;
471 } else if(node->parent->l==node) {
472 node->parent->l=node->l;
473 node->l->parent=node->parent;
474 } else {
475 sx_report(SX_ERROR,"Unlinking node which is not descendant "
476 "of its parent\n");
477 };
478 } else if(tree->head==node) {
479 tree->head=node->l;
480 node->l->parent=NULL;
481 } else {
482 sx_report(SX_ERROR,"Unlinking node with no parent and not root\n");
483 };
484 return;
485 } else {
486 /* the only case - node does not have descendants */
487 if(node->parent) {
488 if(node->parent->l==node) node->parent->l=NULL;
489 else if(node->parent->r==node) node->parent->r=NULL;
490 else {
491 sx_report(SX_ERROR,"Unlinking node which is not descendant "
492 "of its parent\n");
493 };
494 if(node->parent->isGlue) {
495 node=node->parent;
496 goto next;
497 };
498 } else if(tree->head==node) {
499 tree->head=NULL;
500 } else {
501 sx_report(SX_ERROR,"Unlinking node with no parent and not root\n");
502 };
503 return;
504 };
505 };
506
507
508 struct sx_radix_node*
sx_radix_tree_lookup(struct sx_radix_tree * tree,struct sx_prefix * prefix)509 sx_radix_tree_lookup(struct sx_radix_tree* tree, struct sx_prefix* prefix)
510 {
511 int eb;
512 struct sx_radix_node* candidate=NULL, *chead;
513
514 if(!tree || !prefix) return NULL;
515 if(tree->family!=prefix->family) return NULL;
516 if(!tree->head) return NULL;
517
518 chead=tree->head;
519
520 next:
521 eb=sx_prefix_eqbits(&chead->prefix,prefix);
522 if(eb==chead->prefix.masklen && eb==prefix->masklen) {
523 /* they are equal */
524 if(chead->isGlue) return candidate;
525 return chead;
526 } else if(eb<chead->prefix.masklen) {
527 return candidate;
528 } else if(eb<prefix->masklen) {
529 /* it equals chead->masklen */
530 if(sx_prefix_isbitset(prefix,eb+1)) {
531 if(chead->r) {
532 if(!chead->isGlue) {
533 candidate=chead;
534 };
535 chead=chead->r;
536 goto next;
537 } else {
538 if(chead->isGlue) return candidate;
539 return chead;
540 };
541 } else {
542 if(chead->l) {
543 if(!chead->isGlue) {
544 candidate=chead;
545 };
546 chead=chead->l;
547 goto next;
548 } else {
549 if(chead->isGlue) return candidate;
550 return chead;
551 };
552 };
553 } else {
554 char pbuffer[128], cbuffer[128];
555 sx_prefix_snprintf(prefix,pbuffer,sizeof(pbuffer));
556 sx_prefix_snprintf(&chead->prefix,cbuffer,sizeof(cbuffer));
557 printf("Unreachible point... eb=%i, prefix=%s, chead=%s\n", eb,
558 pbuffer, cbuffer);
559 abort();
560 };
561 };
562
563
564 struct sx_radix_node*
sx_radix_tree_insert(struct sx_radix_tree * tree,struct sx_prefix * prefix)565 sx_radix_tree_insert(struct sx_radix_tree* tree, struct sx_prefix* prefix)
566 {
567 int eb;
568 struct sx_radix_node** candidate=NULL, *chead;
569
570 if(!tree || !prefix) return NULL;
571 if(tree->family!=prefix->family) {
572 return NULL;
573 };
574 if(!tree->head) {
575 tree->head=sx_radix_node_new(prefix);
576 return tree->head;
577 };
578 candidate=&tree->head;
579 chead=tree->head;
580
581 next:
582 eb=sx_prefix_eqbits(prefix,&chead->prefix);
583 if(eb<prefix->masklen && eb<chead->prefix.masklen) {
584 struct sx_prefix neoRoot=*prefix;
585 struct sx_radix_node* rn, *ret=sx_radix_node_new(prefix);
586 neoRoot.masklen=eb;
587 sx_prefix_adjust_masklen(&neoRoot);
588 rn=sx_radix_node_new(&neoRoot);
589 if(!rn) {
590 sx_report(SX_ERROR,"Unable to create node: %s\n", strerror(errno));
591 return NULL;
592 };
593 if(sx_prefix_isbitset(prefix,eb+1)) {
594 rn->l=chead;
595 rn->r=ret;
596 } else {
597 rn->l=ret;
598 rn->r=chead;
599 };
600 rn->parent=chead->parent;
601 chead->parent=rn;
602 ret->parent=rn;
603 rn->isGlue=1;
604 *candidate=rn;
605 return ret;
606 } else if(eb==prefix->masklen && eb<chead->prefix.masklen) {
607 struct sx_radix_node* ret=sx_radix_node_new(prefix);
608 if(sx_prefix_isbitset(&chead->prefix,eb+1)) {
609 ret->r=chead;
610 } else {
611 ret->l=chead;
612 };
613 ret->parent=chead->parent;
614 chead->parent=ret;
615 *candidate=ret;
616 return ret;
617 } else if(eb==chead->prefix.masklen && eb<prefix->masklen) {
618 if(sx_prefix_isbitset(prefix,eb+1)) {
619 if(chead->r) {
620 candidate=&chead->r;
621 chead=chead->r;
622 goto next;
623 } else {
624 chead->r=sx_radix_node_new(prefix);
625 chead->r->parent=chead;
626 return chead->r;
627 };
628 } else {
629 if(chead->l) {
630 candidate=&chead->l;
631 chead=chead->l;
632 goto next;
633 } else {
634 chead->l=sx_radix_node_new(prefix);
635 chead->l->parent=chead;
636 return chead->l;
637 };
638 };
639 } else if(eb==chead->prefix.masklen && eb==prefix->masklen) {
640 /* equal routes... */
641 if(chead->isGlue) {
642 chead->isGlue=0;
643 };
644 return chead;
645 } else {
646 char pbuffer[128], cbuffer[128];
647 sx_prefix_snprintf(prefix,pbuffer,sizeof(pbuffer));
648 sx_prefix_snprintf(&chead->prefix,cbuffer,sizeof(cbuffer));
649 printf("Unreachible point... eb=%i, prefix=%s, chead=%s\n", eb,
650 pbuffer, cbuffer);
651 abort();
652 };
653 };
654
655 void
sx_radix_node_fprintf(struct sx_radix_node * node,void * udata)656 sx_radix_node_fprintf(struct sx_radix_node* node, void* udata)
657 {
658 FILE* out=(udata?udata:stdout);
659 char buffer[128];
660 if(!node) {
661 fprintf(out,"(null)\n");
662 } else {
663 sx_prefix_snprintf(&node->prefix,buffer,sizeof(buffer));
664 fprintf(out,"%s %s\n", buffer, node->isGlue?"(glue)":"");
665 };
666 };
667
668 int
sx_radix_node_foreach(struct sx_radix_node * node,void (* func)(struct sx_radix_node *,void *),void * udata)669 sx_radix_node_foreach(struct sx_radix_node* node,
670 void (*func)(struct sx_radix_node*, void*), void* udata)
671 {
672 func(node,udata);
673 if(node->l) sx_radix_node_foreach(node->l,func,udata);
674 if(node->r) sx_radix_node_foreach(node->r,func,udata);
675 return 0;
676 };
677
678 int
sx_radix_tree_foreach(struct sx_radix_tree * tree,void (* func)(struct sx_radix_node *,void *),void * udata)679 sx_radix_tree_foreach(struct sx_radix_tree* tree,
680 void (*func)(struct sx_radix_node*, void*), void* udata)
681 {
682 if(!func || !tree || !tree->head) return 0;
683 sx_radix_node_foreach(tree->head,func,udata);
684 return 0;
685 };
686
687 int
sx_radix_node_aggregate(struct sx_radix_node * node)688 sx_radix_node_aggregate(struct sx_radix_node* node)
689 {
690 if(node->l)
691 sx_radix_node_aggregate(node->l);
692 if(node->r)
693 sx_radix_node_aggregate(node->r);
694
695 if(debug_aggregation) {
696 printf("Aggregating on node: ");
697 sx_prefix_fprint(stdout,&node->prefix);
698 printf(" %s%s%u,%u\n", node->isGlue?"Glue ":"",
699 node->isAggregate?"Aggregate ":"",node->aggregateLow,
700 node->aggregateHi);
701 if(node->r) {
702 printf("R-Tree: ");
703 sx_prefix_fprint(stdout,&node->r->prefix);
704 printf(" %s%s%u,%u\n", (node->r->isGlue)?"Glue ":"",
705 (node->r->isAggregate)?"Aggregate ":"",
706 node->r->aggregateLow,node->r->aggregateHi);
707 if(node->r->son) {
708 printf("R-Son: ");
709 sx_prefix_fprint(stdout,&node->r->son->prefix);
710 printf(" %s%s%u,%u\n",node->r->son->isGlue?"Glue ":"",
711 node->r->son->isAggregate?"Aggregate ":"",
712 node->r->son->aggregateLow,node->r->son->aggregateHi);
713 };
714 };
715 if(node->l) {
716 printf("L-Tree: ");
717 sx_prefix_fprint(stdout,&node->l->prefix);
718 printf(" %s%s%u,%u\n",node->l->isGlue?"Glue ":"",
719 node->l->isAggregate?"Aggregate ":"",
720 node->l->aggregateLow,node->l->aggregateHi);
721 if(node->l->son) {
722 printf("L-Son: ");
723 sx_prefix_fprint(stdout,&node->l->son->prefix);
724 printf(" %s%s%u,%u\n",node->l->son->isGlue?"Glue ":"",
725 node->l->son->isAggregate?"Aggregate ":"",
726 node->l->son->aggregateLow,node->l->son->aggregateHi);
727 };
728 };
729 };
730
731 if(node->r && node->l) {
732 if(!node->r->isAggregate && !node->l->isAggregate &&
733 !node->r->isGlue && !node->l->isGlue &&
734 node->r->prefix.masklen==node->l->prefix.masklen) {
735 if(node->r->prefix.masklen==node->prefix.masklen+1) {
736 node->isAggregate=1;
737 node->r->isGlue=1;
738 node->l->isGlue=1;
739 node->aggregateHi=node->r->prefix.masklen;
740 if(node->isGlue) {
741 node->isGlue=0;
742 node->aggregateLow=node->r->prefix.masklen;
743 } else {
744 node->aggregateLow=node->prefix.masklen;
745 };
746 };
747 if(node->r->son && node->l->son &&
748 node->r->son->isAggregate && node->l->son->isAggregate &&
749 node->r->son->aggregateHi==node->l->son->aggregateHi &&
750 node->r->son->aggregateLow==node->l->son->aggregateLow &&
751 node->r->prefix.masklen==node->prefix.masklen+1 &&
752 node->l->prefix.masklen==node->prefix.masklen+1)
753 {
754 node->son=sx_radix_node_new(&node->prefix);
755 node->son->isGlue=0;
756 node->son->isAggregate=1;
757 node->son->aggregateHi=node->r->son->aggregateHi;
758 node->son->aggregateLow=node->r->son->aggregateLow;
759 node->r->son->isGlue=1;
760 node->l->son->isGlue=1;
761 };
762 } else if(node->r->isAggregate && node->l->isAggregate &&
763 node->r->aggregateHi==node->l->aggregateHi &&
764 node->r->aggregateLow==node->l->aggregateLow) {
765 if(node->r->prefix.masklen==node->prefix.masklen+1 &&
766 node->l->prefix.masklen==node->prefix.masklen+1) {
767 if(node->isGlue) {
768 node->r->isGlue=1;
769 node->l->isGlue=1;
770 node->isAggregate=1;
771 node->isGlue=0;
772 node->aggregateHi=node->r->aggregateHi;
773 node->aggregateLow=node->r->aggregateLow;
774 } else if(node->r->prefix.masklen==node->r->aggregateLow) {
775 node->r->isGlue=1;
776 node->l->isGlue=1;
777 node->isAggregate=1;
778 node->aggregateHi=node->r->aggregateHi;
779 node->aggregateLow=node->prefix.masklen;
780 } else {
781 node->son=sx_radix_node_new(&node->prefix);
782 node->son->isGlue=0;
783 node->son->isAggregate=1;
784 node->son->aggregateHi=node->r->aggregateHi;
785 node->son->aggregateLow=node->r->aggregateLow;
786 node->r->isGlue=1;
787 node->l->isGlue=1;
788 if(node->r->son && node->l->son &&
789 node->r->son->aggregateHi==node->l->son->aggregateHi &&
790 node->r->son->aggregateLow==node->l->son->aggregateLow)
791 {
792 node->son->son=sx_radix_node_new(&node->prefix);
793 node->son->son->isGlue=0;
794 node->son->son->isAggregate=1;
795 node->son->son->aggregateHi=node->r->son->aggregateHi;
796 node->son->son->aggregateLow=node->r->son->aggregateLow;
797 node->r->son->isGlue=1;
798 node->l->son->isGlue=1;
799 };
800 };
801 };
802 } else if(node->l->son &&
803 node->r->isAggregate && node->l->son->isAggregate &&
804 node->r->aggregateHi==node->l->son->aggregateHi &&
805 node->r->aggregateLow==node->l->son->aggregateLow) {
806 if(node->r->prefix.masklen==node->prefix.masklen+1 &&
807 node->l->prefix.masklen==node->prefix.masklen+1) {
808 if(node->isGlue) {
809 node->r->isGlue=1;
810 node->l->son->isGlue=1;
811 node->isAggregate=1;
812 node->isGlue=0;
813 node->aggregateHi=node->r->aggregateHi;
814 node->aggregateLow=node->r->aggregateLow;
815 } else {
816 node->son=sx_radix_node_new(&node->prefix);
817 node->son->isGlue=0;
818 node->son->isAggregate=1;
819 node->son->aggregateHi=node->r->aggregateHi;
820 node->son->aggregateLow=node->r->aggregateLow;
821 node->r->isGlue=1;
822 node->l->son->isGlue=1;
823 };
824 };
825 } else if(node->r->son &&
826 node->l->isAggregate && node->r->son->isAggregate &&
827 node->l->aggregateHi==node->r->son->aggregateHi &&
828 node->l->aggregateLow==node->r->son->aggregateLow) {
829 if(node->l->prefix.masklen==node->prefix.masklen+1 &&
830 node->r->prefix.masklen==node->prefix.masklen+1) {
831 if(node->isGlue) {
832 node->l->isGlue=1;
833 node->r->son->isGlue=1;
834 node->isAggregate=1;
835 node->isGlue=0;
836 node->aggregateHi=node->l->aggregateHi;
837 node->aggregateLow=node->l->aggregateLow;
838 } else {
839 node->son=sx_radix_node_new(&node->prefix);
840 node->son->isGlue=0;
841 node->son->isAggregate=1;
842 node->son->aggregateHi=node->l->aggregateHi;
843 node->son->aggregateLow=node->l->aggregateLow;
844 node->l->isGlue=1;
845 node->r->son->isGlue=1;
846 };
847 };
848 };
849 };
850 return 0;
851 };
852
853 int
sx_radix_tree_aggregate(struct sx_radix_tree * tree)854 sx_radix_tree_aggregate(struct sx_radix_tree* tree)
855 {
856 if(tree && tree->head) return sx_radix_node_aggregate(tree->head);
857 return 0;
858 };
859
860 static void
setGlueUpTo(struct sx_radix_node * node,void * udata)861 setGlueUpTo(struct sx_radix_node* node, void* udata)
862 {
863 unsigned refine=*(unsigned*)udata;
864 if(node && node->prefix.masklen <= refine) {
865 node->isGlue=1;
866 };
867 };
868
869 static void
sx_radix_node_hyperaggregate(struct sx_radix_node * node,unsigned max)870 sx_radix_node_hyperaggregate(struct sx_radix_node* node, unsigned max)
871 {
872 if(!node->isGlue) {
873 node->isAggregate=0;
874 if(node->l)
875 sx_radix_node_foreach(node->l, setGlueUpTo, &max);
876 if(node->r)
877 sx_radix_node_foreach(node->r, setGlueUpTo, &max);
878 } else {
879 if(node->l)
880 sx_radix_node_hyperaggregate(node->l, max);
881 if(node->r)
882 sx_radix_node_hyperaggregate(node->r, max);
883 };
884 };
885
886 int
sx_radix_tree_hyperaggregate(struct sx_radix_tree * tree)887 sx_radix_tree_hyperaggregate(struct sx_radix_tree* tree)
888 {
889 if(tree && tree->head) {
890 unsigned max = tree->family == AF_INET ? 32 : 128;
891 sx_radix_node_hyperaggregate(tree->head, max);
892 };
893 return 0;
894 };
895
896 int
sx_radix_node_refine(struct sx_radix_node * node,unsigned refine)897 sx_radix_node_refine(struct sx_radix_node* node, unsigned refine)
898 {
899 if(!node->isGlue && node->prefix.masklen<refine) {
900 node->isAggregate=1;
901 node->aggregateLow=node->prefix.masklen;
902 node->aggregateHi=refine;
903 if(node->l) {
904 sx_radix_node_foreach(node->l, setGlueUpTo, &refine);
905 sx_radix_node_refine(node->l, refine);
906 };
907 if(node->r) {
908 sx_radix_node_foreach(node->r, setGlueUpTo, &refine);
909 sx_radix_node_refine(node->r, refine);
910 };
911 } else if(!node->isGlue && node->prefix.masklen==refine) {
912 /* not setting aggregate in this case */
913 if(node->l) sx_radix_node_refine(node->l, refine);
914 if(node->r) sx_radix_node_refine(node->r, refine);
915 } else if(node->isGlue) {
916 if(node->r) sx_radix_node_refine(node->r, refine);
917 if(node->l) sx_radix_node_refine(node->l, refine);
918 } else {
919 /* node->prefix.masklen > refine */
920 /* do nothing, should pass specifics 'as is'. Also, do not
921 process any embedded routes, their masklen is bigger, too...
922 node->isGlue=1;
923 if(node->l) sx_radix_node_foreach(node->l, setGlue, NULL);
924 if(node->r) sx_radix_node_foreach(node->r, setGlue, NULL);
925 */
926 };
927 return 0;
928 };
929
930 int
sx_radix_tree_refine(struct sx_radix_tree * tree,unsigned refine)931 sx_radix_tree_refine(struct sx_radix_tree* tree, unsigned refine)
932 {
933 if(tree && tree->head) return sx_radix_node_refine(tree->head, refine);
934 return 0;
935 };
936
937 static void
setGlueFrom(struct sx_radix_node * node,void * udata)938 setGlueFrom(struct sx_radix_node* node, void* udata)
939 {
940 unsigned refine=*(unsigned*)udata;
941 if(node && node->prefix.masklen <= refine) {
942 node->isGlue=1;
943 };
944 };
945
946 static int
sx_radix_node_refineLow(struct sx_radix_node * node,unsigned refineLow)947 sx_radix_node_refineLow(struct sx_radix_node* node, unsigned refineLow)
948 {
949 if(!node->isGlue && node->prefix.masklen<=refineLow) {
950 if(!node->isAggregate) {
951 node->isAggregate=1;
952 node->aggregateLow=refineLow;
953 if(node->prefix.family == AF_INET) {
954 node->aggregateHi=32;
955 } else {
956 node->aggregateHi=128;
957 }
958 } else {
959 node->aggregateLow=refineLow;
960 };
961 if(node->l) {
962 sx_radix_node_foreach(node->l, setGlueFrom, &refineLow);
963 sx_radix_node_refineLow(node->l, refineLow);
964 };
965 if(node->r) {
966 sx_radix_node_foreach(node->r, setGlueFrom, &refineLow);
967 sx_radix_node_refineLow(node->r, refineLow);
968 };
969 } else if(!node->isGlue && node->prefix.masklen==refineLow) {
970 /* not setting aggregate in this case */
971 if(node->l) sx_radix_node_refineLow(node->l, refineLow);
972 if(node->r) sx_radix_node_refineLow(node->r, refineLow);
973 } else if(node->isGlue) {
974 if(node->r) sx_radix_node_refineLow(node->r, refineLow);
975 if(node->l) sx_radix_node_refineLow(node->l, refineLow);
976 } else {
977 /* node->prefix.masklen > refine */
978 /* do nothing, should pass specifics 'as is'. Also, do not
979 process any embedded routes, their masklen is bigger, too...
980 node->isGlue=1;
981 if(node->l) sx_radix_node_foreach(node->l, setGlue, NULL);
982 if(node->r) sx_radix_node_foreach(node->r, setGlue, NULL);
983 */
984 };
985 return 0;
986 };
987
988
989 int
sx_radix_tree_refineLow(struct sx_radix_tree * tree,unsigned refineLow)990 sx_radix_tree_refineLow(struct sx_radix_tree* tree, unsigned refineLow)
991 {
992 if(tree && tree->head)
993 return sx_radix_node_refineLow(tree->head, refineLow);
994 return 0;
995 };
996
997
998 #if SX_PTREE_TEST
999 int
main()1000 main() {
1001 struct sx_prefix* p;
1002 int n;
1003 struct sx_radix_tree* tree;
1004 struct sx_radix_node* node;
1005
1006 p=sx_prefix_new(0,"10.11.12.13/24");
1007 sx_prefix_fprint(stdout,p);
1008 printf("\n");
1009 p=sx_prefix_new(0,"10.11.12.13/33");
1010 sx_prefix_fprint(stdout,p);
1011 printf("\n");
1012 p=sx_prefix_new(0,"10.11.12.13/-133");
1013 sx_prefix_fprint(stdout,p);
1014 printf("\n");
1015
1016 p=sx_prefix_new(AF_INET,"10.11.12.14/24");
1017 sx_prefix_fprint(stdout,p);
1018 printf("\n");
1019 p=sx_prefix_new(AF_INET,"10.11.12.14/33");
1020 sx_prefix_fprint(stdout,p);
1021 printf("\n");
1022 p=sx_prefix_new(AF_INET,"10.11.12.14/-133");
1023 sx_prefix_fprint(stdout,p);
1024 printf("\n");
1025
1026 p=sx_prefix_new(AF_INET6,"10.11.12.15/24");
1027 sx_prefix_fprint(stdout,p);
1028 printf("\n");
1029 p=sx_prefix_new(AF_INET6,"10.11.12.15/33");
1030 sx_prefix_fprint(stdout,p);
1031 printf("\n");
1032 p=sx_prefix_new(AF_INET6,"10.11.12.15/-133");
1033 sx_prefix_fprint(stdout,p);
1034 printf("\n");
1035
1036 p=sx_prefix_new(0,"2001:1b00::/24");
1037 sx_prefix_fprint(stdout,p);
1038 printf("\n");
1039 p=sx_prefix_new(0,"2001:1b00::/33");
1040 sx_prefix_fprint(stdout,p);
1041 printf("\n");
1042 p=sx_prefix_new(0,"2001:1b00::/-133");
1043 sx_prefix_fprint(stdout,p);
1044 printf("\n");
1045
1046 p=sx_prefix_new(AF_INET6,"2001:1b01::/24");
1047 sx_prefix_fprint(stdout,p);
1048 printf("\n");
1049 p=sx_prefix_new(AF_INET6,"2001:1b01::/33");
1050 sx_prefix_fprint(stdout,p);
1051 printf("\n");
1052 p=sx_prefix_new(AF_INET6,"2001:1b01::/-133");
1053 sx_prefix_fprint(stdout,p);
1054 printf("\n");
1055
1056 #define SX_TEST_EBITS(a,b,susp) n=sx_prefix_eqbits(sx_prefix_new(0,a)),\
1057 sx_prefix_new(0,b))); \
1058 if(n!=susp) printf("FAILED: %s eqbits %s=%i, not %i\n", a, b, n, susp);\
1059 else printf("OK, %s eqbits %s=%i, as suspected\n", a, b, n);
1060 SX_TEST_EBITS("192.168.0.0/24","192.168.1.0/24",23);
1061 SX_TEST_EBITS("192.168.0.0/32","192.168.0.1/32",31);
1062 #if SX_LIBPTREE_IPV6
1063 SX_TEST_EBITS("2001:1b00::/32","2001:1b01::/32",31);
1064 #endif
1065
1066 p=sx_prefix_new(0,"10.11.12.255/32");
1067 sx_prefix_fprint(stdout,p);
1068 printf("\n31'th bit is %i\n",sx_prefix_isbitset(p,31));
1069 printf("32'th bit is %i\n",sx_prefix_isbitset(p,32));
1070 printf("33'th bit is %i\n",sx_prefix_isbitset(p,33));
1071 p=sx_prefix_new(0,"10.11.12.255/31");
1072 sx_prefix_fprint(stdout,p);
1073 printf("\n31'th bit is %i\n",sx_prefix_isbitset(p,31));
1074 printf("32'th bit is %i\n",sx_prefix_isbitset(p,32));
1075 printf("33'th bit is %i\n",sx_prefix_isbitset(p,33));
1076 p=sx_prefix_new(0,"10.11.12.255/30");
1077 sx_prefix_fprint(stdout,p);
1078 printf("\n31'th bit is %i\n",sx_prefix_isbitset(p,31));
1079 p=sx_prefix_new(0,"10.11.12.255/29");
1080 sx_prefix_fprint(stdout,p);
1081 printf("\n");
1082 p=sx_prefix_new(0,"10.11.12.255/28");
1083 sx_prefix_fprint(stdout,p);
1084 printf("\n");
1085 p=sx_prefix_new(0,"10.11.12.255/27");
1086 sx_prefix_fprint(stdout,p);
1087 printf("\n");
1088 p=sx_prefix_new(0,"10.11.12.255/26");
1089 sx_prefix_fprint(stdout,p);
1090 printf("\n");
1091 p=sx_prefix_new(0,"10.11.12.255/25");
1092 sx_prefix_fprint(stdout,p);
1093 printf("\n25'th bit is %i\n",sx_prefix_isbitset(p,25));
1094 p=sx_prefix_new(0,"10.11.12.255/24");
1095 sx_prefix_fprint(stdout,p);
1096 printf("\n25'th bit is %i\n",sx_prefix_isbitset(p,25));
1097
1098 tree=sx_radix_tree_new(AF_INET);
1099 sx_radix_tree_insert(tree,sx_prefix_new(0,"81.9.100.10/32"));
1100 sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.83/32"));
1101
1102 sx_radix_tree_foreach(tree,sx_radix_node_fprintf,NULL);
1103
1104 tree=sx_radix_tree_new(AF_INET);
1105 sx_radix_tree_insert(tree,sx_prefix_new(0,"81.9.100.10/32"));
1106 sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.83/32"));
1107 sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.84/32"));
1108 sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.85/32"));
1109 sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.86/32"));
1110 sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.87/32"));
1111 sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.90/32"));
1112 sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.90/32"));
1113 sx_radix_tree_insert(tree,sx_prefix_new(0,"127.0.0.1/32"));
1114 sx_radix_tree_insert(tree,sx_prefix_new(0,"127.0.0.1/24"));
1115 sx_radix_tree_insert(tree,sx_prefix_new(0,"127.0.0.0/24"));
1116 sx_radix_tree_insert(tree,sx_prefix_new(0,"128.0.0.0/1"));
1117
1118 sx_radix_tree_foreach(tree,sx_radix_node_fprintf,NULL);
1119
1120 printf("lookup 1.1.1.1: ");
1121 node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"1.1.1.1"));
1122 sx_radix_node_fprintf(node,NULL);
1123
1124 printf("lookup 217.170.80.90: ");
1125 node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"217.170.80.90"));
1126 sx_radix_node_fprintf(node,NULL);
1127
1128 sx_radix_tree_unlink(tree,node);
1129 printf("lookup 217.170.80.90 after delete: ");
1130 node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"217.170.80.90"));
1131 sx_radix_node_fprintf(node,NULL);
1132
1133 sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.90/32"));
1134 printf("lookup 217.170.80.90 after reinsert: ");
1135 node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"217.170.80.90"));
1136 sx_radix_node_fprintf(node,NULL);
1137
1138 printf("lookup 217.170.80.81: ");
1139 node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"217.170.80.81"));
1140 sx_radix_node_fprintf(node,NULL);
1141
1142 printf("lookup 127.0.0.1/24: ");
1143 node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"127.0.0.1/24"));
1144 sx_radix_node_fprintf(node,NULL);
1145
1146 printf("lookup 127.0.0.1/26: ");
1147 node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"127.0.0.1/26"));
1148 sx_radix_node_fprintf(node,NULL);
1149
1150 printf("lookup 127.0.0.1/23: ");
1151 node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"127.0.0.1/23"));
1152 sx_radix_node_fprintf(node,NULL);
1153
1154 tree=sx_radix_tree_new(AF_INET6);
1155 sx_radix_tree_insert(tree,sx_prefix_new(0,"2100:1b00::/32"));
1156 sx_radix_tree_insert(tree,sx_prefix_new(0,"2100:1b01::/32"));
1157 sx_radix_tree_insert(tree,sx_prefix_new(0,"2100:1b00::/33"));
1158 sx_radix_tree_insert(tree,sx_prefix_new(0,"2100:1b00::1/128"));
1159 sx_radix_tree_foreach(tree,sx_radix_node_fprintf,NULL);
1160
1161 return 0;
1162 };
1163
1164 #endif
1165