1 /* $OpenBSD: radish.c,v 1.8 2023/04/19 12:58:16 jsg Exp $ */
2 /*
3 * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project.
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of the project nor the names of its contributors
15 * may be used to endorse or promote products derived from this software
16 * without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * SUCH DAMAGE.
29 *
30 */
31
32 /*
33 * radish.c
34 *
35 * Version: 0.9
36 * Created: May 27, 1995
37 * Modified: January 28, 1997
38 * Author: Kazu YAMAMOTO
39 * Email: kazu@is.aist-nara.ac.jp
40 */
41
42 #include <sys/types.h>
43 #include <sys/socket.h>
44 #include <string.h>
45 #include <stdlib.h>
46 #include <errno.h>
47
48 #include "radish.h"
49
50 #include <netinet/in.h>
51 #include <strings.h>
52 #include <stdio.h>
53
54 #define FATAL(x) \
55 do { \
56 fputs(x, stderr); \
57 abort(); \
58 } while (0/* CONSTCOND */)
59
60 static u_char rd_bmask [] = {
61 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe,
62 };
63
64 static u_char rd_btest [] = {
65 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01,
66 };
67
68 u_char rd_deleted_km[1024];
69
70 /*
71 * return 1 if success
72 * return 0 if error
73 */
74 int
rd_inithead(void ** headp,int family,int slen,int off,int alen,int (* match)(void *,void *))75 rd_inithead(void **headp, int family, int slen, int off, int alen,
76 int (*match)(void *, void *))
77 {
78 struct radish_head *head;
79 struct radish *new;
80 struct sockaddr *masks;
81 u_char *m;
82 int num = alen * 8 + 1, i, j, q, r;
83 int len = sizeof(*head) + sizeof(*new) + slen * num;
84
85 if (*headp) return (1);
86 R_Malloc(head, struct radish_head *, len);
87 if (head == NULL)
88 return 0;
89 Bzero(head, len);
90 new = (struct radish *)(head + 1);
91 masks = (struct sockaddr *)(new +1);
92 *headp = head;
93
94 /*
95 * prepare all continuous masks
96 */
97 m = (u_char *)masks;
98 for (i = 0; i < num; i++, m += slen) {
99 *m = slen;
100 *(m + 1) = family;
101 q = i >> 3;
102 r = i & 7;
103 for(j = 0; j < q; j++)
104 *(m + off + j) = 0xff;
105 *(m + off + j) = rd_bmask[r];
106 }
107
108 head->rdh_slen = slen;
109 head->rdh_offset = off;
110 head->rdh_alen = alen;
111 head->rdh_masks = masks;
112 head->rdh_match = match;
113 head->rdh_top = new;
114
115 new->rd_route = masks;
116 new->rd_mask = masks;
117 new->rd_btest = rd_btest[0];
118 /* other nembers are 0 */
119
120 return(1);
121 }
122
123 struct sockaddr *
rd_mask(struct sockaddr * m_arg,struct radish_head * head,int * maskp)124 rd_mask(struct sockaddr *m_arg, struct radish_head *head, int *maskp)
125 {
126 u_char *mp, *masks = (u_char *)head->rdh_masks;
127 int off = head->rdh_offset;
128 int slen = head->rdh_slen;
129 int alen = head->rdh_alen;
130 int i = 0, masklen = 0;
131
132 if (m_arg == NULL) {
133 masklen = alen * 8;
134 *maskp = masklen;
135 return((struct sockaddr *)(masks + slen * masklen));
136 }
137 mp = (u_char *)m_arg + off;
138 while ((i < alen) && (mp[i] == 0xff)) {
139 masklen += 8;
140 i++;
141 }
142 if (i < alen)
143 switch (mp[i]) {
144 case 0xfe: masklen += 7; break;
145 case 0xfc: masklen += 6; break;
146 case 0xf8: masklen += 5; break;
147 case 0xf0: masklen += 4; break;
148 case 0xe0: masklen += 3; break;
149 case 0xc0: masklen += 2; break;
150 case 0x80: masklen += 1; break;
151 case 0x00: break;
152 }
153 *maskp = masklen;
154 return((struct sockaddr *)(masks + slen * masklen));
155 }
156
157 int
rd_insert(struct sockaddr * d_arg,struct sockaddr * m_arg,struct radish_head * head,void * rt)158 rd_insert(struct sockaddr *d_arg, struct sockaddr *m_arg,
159 struct radish_head *head, void *rt)
160 {
161 struct radish *cur = head->rdh_top, *parent, *new;
162 int off = head->rdh_offset;
163 int slen = head->rdh_slen;
164 int alen = head->rdh_alen;
165 int i, lim, q, r, masklen;
166 u_char *dp, *np, *rp;
167 struct sockaddr *mask;
168
169 mask = rd_mask(m_arg, head, &masklen);
170 q = masklen >> 3;
171 r = masklen & 7;
172
173 /* Allocate a new radish.
174 * This may be overhead in the case that
175 * masklen == cur->rd_masklen
176 * and
177 * route == dest.
178 */
179 R_Malloc(new, struct radish *, sizeof(*new) + slen);
180 if (new == NULL)
181 return ENOBUFS;
182 Bzero(new, sizeof(*new) + slen);
183 new->rd_route = (struct sockaddr *)(new + 1);
184 new->rd_mask = mask;
185 new->rd_masklen = masklen;
186 new->rd_masklim = q;
187 new->rd_bmask = rd_bmask[r];
188 new->rd_btest = rd_btest[r];
189 new->rd_rtent = rt;
190
191 /* masked copy from dest to route */
192 np = (u_char *)new->rd_route;
193 dp = (u_char *)d_arg;
194 *np = *dp; /* sa_len */
195 np[1] = dp[1]; /* sa_family */
196 dp += off;
197 np += off;
198 i = 0;
199 while (i < q) {
200 np[i] = dp[i];
201 i++;
202 }
203 np[i] = dp[i] & rd_bmask[r]; /* just in case */
204
205 while (cur) {
206 if (masklen == cur->rd_masklen) {
207 rp = (u_char *)cur->rd_route + off;
208 for (i = 0; i < alen; i++)
209 if (np[i] != rp[i]) {
210 /*
211 * masklen == cur->rd_masklen
212 * dest != route
213 */
214 return rd_glue(cur, new, i, head);
215 }
216 /*
217 * masklen == cur->rd_masklen
218 * dest == route
219 */
220 Free(new);
221 if (cur->rd_rtent != NULL)
222 return EEXIST;
223 cur->rd_rtent = rt;
224 return 0;
225 }
226 /*
227 * masklen != cur->rd_masklen
228 */
229 if (masklen > cur->rd_masklen) {
230 /*
231 * See if dest matches with cur node.
232 * (dest & mask) == route
233 */
234 rp = (u_char *)cur->rd_route + off;
235 lim = cur->rd_masklim;
236
237 /* mask is continuous, thus mask is 0xff here. */
238 for (i = 0; i < lim; i++)
239 if(np[i] != rp[i]) {
240 /*
241 * masklen > cur->rd_masklen
242 * (dest & mask) != route
243 */
244 return rd_glue(cur, new, i, head);
245 }
246 if (cur->rd_bmask)
247 if ((np[lim] & cur->rd_bmask) != rp[lim]) {
248 /*
249 * masklen > cur->rd_masklen
250 * (dest & mask) != route
251 */
252 return rd_glue(cur, new, lim, head);
253 }
254 /*
255 * masklen > cur->rd_masklen
256 * (dest & mask) == route
257 */
258 if (cur->rd_btest & np[cur->rd_masklim]) {
259 if (cur->rd_r != NULL) {
260 cur = cur->rd_r;
261 continue;
262 }
263 cur->rd_r = new;
264 new->rd_p = cur;
265 return 0;
266 } else {
267 if (cur->rd_l != NULL) {
268 cur = cur->rd_l;
269 continue;
270 }
271 cur->rd_l = new;
272 new->rd_p = cur;
273 return 0;
274 }
275 }
276 /*
277 * masklen < cur->rd_masklen
278 */
279
280 /* See if route matches with dest, be careful!
281 * dest == (route & dest_mask)
282 */
283 rp = (u_char *)cur->rd_route + off;
284 lim = new->rd_masklim;
285
286 /* mask is continuous, thus mask is 0xff here. */
287 for (i = 0; i < lim; i++)
288 if(np[i] != rp[i]) {
289 /*
290 * masklen < cur->rd_masklen
291 * dest != (route & dest_mask)
292 */
293 return rd_glue(cur, new, i, head);
294 }
295 if (new->rd_bmask)
296 if (np[lim] != (rp[lim] & new->rd_bmask)) {
297 /*
298 * masklen < cur->rd_masklen
299 * dest != (route & dest_mask)
300 */
301 return rd_glue(cur, new, lim, head);
302 }
303 /*
304 * masklen < cur->rd_masklen
305 * dest == (route & dest_mask)
306 */
307
308 /* put the new radish between cur and its parent */
309 parent = cur->rd_p;
310 new->rd_p = parent;
311 if (parent->rd_l == cur)
312 parent->rd_l = new;
313 else if (parent->rd_r == cur)
314 parent->rd_r = new;
315 else
316 FATAL("rd_insert");
317 if (new->rd_btest & rp[new->rd_masklim])
318 new->rd_r = cur;
319 else
320 new->rd_l = cur;
321
322 cur->rd_p = new;
323 return 0;
324 }
325 return 1;
326 }
327
328 /*
329 * Insert a glue radish between the current and its parent.
330 * Let the current radish one child of glue radish.
331 * Let the new radish the other child of glue radish.
332 */
333 int
rd_glue(struct radish * cur,struct radish * new,int misbyte,struct radish_head * head)334 rd_glue(struct radish *cur, struct radish *new, int misbyte,
335 struct radish_head *head)
336 {
337 struct radish *parent = cur->rd_p, *glue;
338 u_char *cp = (u_char *)cur->rd_route;
339 u_char *np = (u_char *)new->rd_route;
340 u_char *gp;
341 int off = head->rdh_offset, slen = head->rdh_slen;
342 int maskb, xor, i;
343
344 /*
345 * Glue radish
346 */
347 R_Malloc(glue, struct radish *, sizeof(*glue) + slen);
348 if (glue == NULL) {
349 Free (new);
350 return ENOBUFS;
351 }
352 Bzero(glue, sizeof(*glue) + slen);
353
354 /* calculate a bit to test */
355 xor = (*(cp + off + misbyte) ^ *(np + off + misbyte)) & 0xff;
356 maskb = 8;
357 while(xor) {
358 xor >>= 1;
359 maskb--;
360 }
361
362 glue->rd_route = (struct sockaddr *)(glue + 1);
363 glue->rd_masklen = 8 * misbyte + maskb;
364 glue->rd_masklim = misbyte;
365 glue->rd_bmask = rd_bmask[maskb];
366 glue->rd_btest = rd_btest[maskb];
367 glue->rd_rtent = NULL;
368 glue->rd_p = parent;
369 glue->rd_mask = (struct sockaddr *)
370 ((u_char *)head->rdh_masks + slen * glue->rd_masklen);
371
372 /* masked copy of route */
373 gp = (u_char *)glue->rd_route;
374 *gp = *cp; /* sa_len */
375 *(gp + 1) = *(cp + 1); /* sa_family */
376 cp += off;
377 gp += off;
378 for(i = 0; i < misbyte; i++)
379 gp[i] = cp[i];
380 gp[misbyte] = cp[misbyte] & glue->rd_bmask;
381
382 if (glue->rd_btest & cp[misbyte]) {
383 glue->rd_r = cur;
384 glue->rd_l = new;
385 } else {
386 glue->rd_r = new;
387 glue->rd_l = cur;
388 }
389
390 /*
391 * Children
392 */
393 new->rd_p = cur->rd_p = glue;
394
395 /*
396 * Parent
397 */
398 if (parent->rd_l == cur)
399 parent->rd_l = glue;
400 else if (parent->rd_r == cur)
401 parent->rd_r = glue;
402 else
403 FATAL("rd_insert");
404 return 0;
405 }
406
407 /*
408 * Find the longest-match radish with the destination.
409 * Return 1 if success, otherwise return 0.
410 */
411
412 int
rd_match(struct sockaddr * d_arg,struct radish_head * head,struct radish ** rdp)413 rd_match(struct sockaddr *d_arg, struct radish_head *head, struct radish **rdp)
414 {
415 return rd_match_next(d_arg, head, rdp, NULL);
416 }
417
418 int
rd_match_next(struct sockaddr * d_arg,struct radish_head * head,struct radish ** rdp,struct radish * cur)419 rd_match_next(struct sockaddr *d_arg, struct radish_head *head,
420 struct radish **rdp, struct radish *cur)
421 {
422 struct radish *target = NULL;
423 int off = head->rdh_offset, i, lim;
424 u_char *dp = (u_char *)d_arg + off, *cp;
425
426 if (cur == NULL) {
427 cur = head->rdh_top;
428 while (cur) {
429 target = cur;
430 if (cur->rd_btest & *(dp + cur->rd_masklim))
431 cur = cur->rd_r;
432 else
433 cur = cur->rd_l;
434 }
435 } else {
436 target = cur->rd_p;
437 if (target == NULL) {
438 *rdp = NULL;
439 return 0;
440 }
441 }
442
443 /* We are now on the leaf radish. Backtrace to find the radish
444 which contains route to match. */
445 do {
446 /* If this radish doesn't have route,
447 we skip it and chase the next parent. */
448 if (target->rd_rtent != NULL) {
449 cp = (u_char *)target->rd_route + off;
450 lim = target->rd_masklim;
451
452 /* Check the edge for slight speed up */
453 if (target->rd_bmask)
454 if ((*(dp + lim) & target->rd_bmask)
455 != *(cp + lim)){
456 nextparent:
457 continue;
458 }
459
460 /* mask is always 0xff */
461 for (i = 0; i < lim; i++)
462 if(dp[i] != cp[i])
463 /* to break the for loop */
464 goto nextparent;
465 /* Matched to this radish! */
466 *rdp = target;
467 return 1;
468 }
469 } while ((target = target->rd_p));
470 *rdp = NULL;
471 return 0;
472 }
473
474 /*
475 * Lookup the same radish according to a pair of destination and mask.
476 * Return a pointer to rtentry if exists. Otherwise, return NULL.
477 */
478
479 void *
rd_lookup(struct sockaddr * d_arg,struct sockaddr * m_arg,struct radish_head * head)480 rd_lookup(struct sockaddr *d_arg, struct sockaddr *m_arg,
481 struct radish_head *head)
482 {
483 struct radish *cur = head->rdh_top;
484 int off = head->rdh_offset, i, lim, olim = 0, masklen;
485 u_char *dp = (u_char *)d_arg + off, *cp;
486
487 rd_mask(m_arg, head, &masklen);
488
489 /* Skipping forward search */
490 while (cur) {
491 /* Skip a radish if it doesn't have a route */
492 if (cur->rd_rtent != NULL) {
493 cp = (u_char *)(cur->rd_route) + off;
494 lim = cur->rd_masklim;
495 /* check the edge to speed up a bit */
496 if (cur->rd_bmask)
497 if ((*(dp + lim) & cur->rd_bmask)
498 != *(cp + lim))
499 return NULL;
500 /* mask is always 0xff */
501 for (i = olim; i < lim; i++)
502 if(dp[i] != cp[i])
503 return NULL;
504 if (masklen == cur->rd_masklen)
505 return cur->rd_rtent;
506 olim = lim;
507 }
508 if (cur->rd_btest & *(dp + cur->rd_masklim))
509 cur = cur->rd_r;
510 else
511 cur = cur->rd_l;
512 }
513 return NULL;
514 }
515
516 /*
517 * Delete the radish for dest and mask.
518 * Return 0 if success.
519 * Return ENOENT if no such radish exists.
520 * Return EFAULT if try to delete intermediate radish which doesn't have route.
521 */
522
523 int
rd_delete(struct sockaddr * d_arg,struct sockaddr * m_arg,struct radish_head * head,void ** item)524 rd_delete(struct sockaddr *d_arg, struct sockaddr *m_arg,
525 struct radish_head *head, void **item)
526 {
527 struct radish *cur = head->rdh_top;
528 int off = head->rdh_offset, i, lim, masklen;
529 u_char *dp = (u_char *)d_arg + off, *cp;
530
531 rd_mask(m_arg, head, &masklen);
532 *item = NULL; /* just in case */
533
534 while (cur) {
535 /* exit loop if dest does not match with the current node
536 * (dest & mask) != route
537 */
538 cp = (u_char *)cur->rd_route + off;
539 /* check the edge to speed up */
540 if (cur->rd_bmask)
541 if ((*(dp + cur->rd_masklim) & cur->rd_bmask)
542 != *(cp + cur->rd_masklim))
543 return ENOENT;
544 /* mask is always 0xff */
545 lim = cur->rd_masklim;
546 for (i = 0; i < lim; i++)
547 if(dp[i] != cp[i])
548 return ENOENT;
549
550 /* See if cur is exactly what we delete */
551
552 /* Check mask to speed up */
553 if (cur->rd_masklen != masklen)
554 goto next;
555
556 cp = (u_char *)cur->rd_route + off;
557 lim = head->rdh_alen;
558 for (i = 0; i < lim; i++)
559 if (dp[i] != cp[i])
560 goto next;
561 /*
562 * Both route and mask are the same.
563 */
564 if (cur->rd_rtent == NULL) {
565 /* Leaf always has route, so this radish
566 * must be intermediate.
567 * Can't delete intermediate radish which
568 * doesn't have route.
569 */
570 return EFAULT;
571 }
572 *item = cur->rd_rtent;
573 {
574 /* used to report the deleted entry back */
575 u_char rl = cur->rd_route->sa_len;
576 u_char ml = cur->rd_mask->sa_len;
577
578 bcopy(cur->rd_route, rd_deleted_km, rl);
579 bcopy(cur->rd_mask, rd_deleted_km + rl, ml);
580 }
581 if (cur->rd_l && cur->rd_r) {
582 /* This radish has two children */
583 cur->rd_rtent = NULL;
584 return 0;
585 }
586 /* Unlink the radish that has 0 or 1 child
587 * and surely has a route.
588 */
589 rd_unlink(cur, head->rdh_top);
590 return 0;
591
592 next:
593 /* search corresponding subtree */
594 if (cur->rd_btest & *(dp + cur->rd_masklim)) {
595 if (cur->rd_r) {
596 cur = cur->rd_r;
597 continue;
598 } else
599 break;
600 } else {
601 if (cur->rd_l) {
602 cur = cur->rd_l;
603 continue;
604 } else
605 break;
606 }
607 }
608 return ENOENT;
609 }
610
611 /*
612 * Free radish and refine radish tree.
613 * rd_unlink is called with radish which have 0 or 1 child and route.
614 * Error causes panic, so return only when success.
615 */
616
617 void
rd_unlink(struct radish * cur,struct radish * top)618 rd_unlink(struct radish *cur, struct radish *top)
619 {
620 struct radish *parent, *child;
621
622 if (cur == top) {
623 cur->rd_rtent = NULL;
624 return;
625 }
626
627 if ((cur->rd_l == 0) && (cur->rd_r == 0)) {
628 /* No child, just delete it. */
629 parent = cur->rd_p;
630 if (parent->rd_l == cur) {
631 parent->rd_l = NULL;
632 Free(cur);
633 } else if (parent->rd_r == cur) {
634 parent->rd_r = NULL;
635 Free(cur);
636 } else
637 FATAL("rd_unlink");
638 if (parent->rd_rtent == NULL && parent != top)
639 /* Parent is not necessary, refine radish. */
640 rd_unlink(parent, top);
641 } else {
642 /*
643 * There is one child, never two.
644 * Make its child its parent's child.
645 */
646 if (cur->rd_l)
647 child = cur->rd_l;
648 else
649 child = cur->rd_r;
650 parent = cur->rd_p;
651 child->rd_p = parent;
652 if (parent->rd_l == cur) {
653 parent->rd_l = child;
654 Free(cur);
655 } else if (parent->rd_r == cur) {
656 parent->rd_r = child;
657 Free(cur);
658 } else
659 FATAL("rd_unlink");
660 }
661 }
662
663 int
rd_walktree(struct radish_head * h,register int (* f)(struct radish *,void *),void * w)664 rd_walktree(struct radish_head *h, register int (*f)(struct radish *, void *),
665 void *w)
666 {
667 int error = 0;
668 struct radish *par = NULL, *cur, *top = h->rdh_top;
669
670 cur = top;
671 for (;;) {
672 while (cur) {
673 if (cur->rd_rtent != NULL)
674 if ((error = (*f)(cur, w)))
675 return error;
676 par = cur;
677 cur = cur->rd_l;
678 }
679 cur = par;
680 while (cur->rd_r == NULL || par == cur->rd_r) {
681 par = cur;
682 cur = cur->rd_p;
683 if (cur == NULL) return 0;
684 }
685 par = cur;
686 cur = cur->rd_r;
687 }
688 }
689
690 /* This function can be mush easier in the context of radish.
691 * For instance, using rd_mask. But we stay the original because
692 * it works.
693 */
694 int
rd_refines(void * m_arg,void * n_arg)695 rd_refines(void *m_arg, void *n_arg)
696 {
697 register caddr_t m = m_arg, n = n_arg;
698 register caddr_t lim, lim2 = lim = n + *(u_char *)n;
699 int longer = (*(u_char *)n++) - (int)(*(u_char *)m++);
700 int masks_are_equal = 1;
701
702 if (longer > 0)
703 lim -= longer;
704 while (n < lim) {
705 if (*n & ~(*m))
706 return 0;
707 if (*n++ != *m++)
708 masks_are_equal = 0;
709
710 }
711 while (n < lim2)
712 if (*n++)
713 return 0;
714 if (masks_are_equal && (longer < 0))
715 for (lim2 = m - longer; m < lim2; )
716 if (*m++)
717 return 1;
718 return (!masks_are_equal);
719 }
720