Lines Matching +full:1 +full:br +full:- +full:10
1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause
9 * 1. Redistributions of source code must retain the above copyright
60 * 0.0.0.0/0 -> nh1
61 * 10.0.0.0/24 -> nh2
62 * 10.0.0.1/32 -> nh3
66 * 0.0.0.0 -> nh1
67 * 10.0.0.0 -> nh2
68 * 10.0.0.1 -> nh3
69 * 10.0.0.2 -> nh2
70 * 10.0.1.0 -> nh1
86 struct bsearch4_record br[0]; member
99 const struct bsearch4_record *br; in bsearch4_lookup() local
103 int end = bd->num_items; in bsearch4_lookup()
106 while (start + 1 < end) { in bsearch4_lookup()
108 br = &bd->br[i]; in bsearch4_lookup()
109 if (addr4 < br->addr4) { in bsearch4_lookup()
113 } else if (addr4 > br->addr4) { in bsearch4_lookup()
119 return (br->nh); in bsearch4_lookup()
122 /* start + 1 == end */ in bsearch4_lookup()
123 return (bd->br[start].nh); in bsearch4_lookup()
128 * Assume ideal for < 10 (typical single-interface setup has 5)
137 if (rinfo->num_prefixes < 10) in bsearch4_get_pref()
139 else if (rinfo->num_prefixes < 30) in bsearch4_get_pref()
140 return (255 - rinfo->num_prefixes * 8); in bsearch4_get_pref()
142 return (1); in bsearch4_get_pref()
155 count = rinfo.num_prefixes * 11 / 10 + 64; in bsearch4_init()
163 /* Align datapath-usable structure to cache line boundary */ in bsearch4_init()
165 bd->mem = mem; in bsearch4_init()
166 bd->alloc_items = count; in bsearch4_init()
167 bd->fd = fd; in bsearch4_init()
175 bd->rr = mallocarray(count, sizeof(struct bsearch4_record), M_TEMP, M_NOWAIT | M_ZERO); in bsearch4_init()
176 if (bd->rr == NULL) in bsearch4_init()
187 if (bd->rr != NULL) in bsearch4_destroy()
188 free(bd->rr, M_TEMP); in bsearch4_destroy()
189 free(bd->mem, M_RTABLE); in bsearch4_destroy()
204 if (bd->num_items >= bd->alloc_items) in bsearch4_add_route_cb()
207 rr = &bd->rr[bd->num_items++]; in bsearch4_add_route_cb()
209 rr->addr4 = ntohl(addr4.s_addr); in bsearch4_add_route_cb()
210 rr->mask4 = ntohl(mask4.s_addr); in bsearch4_add_route_cb()
211 rr->nh = rt_get_raw_nhop(rt); in bsearch4_add_route_cb()
218 * 10.0.0.0/24 < 10.0.0.0/25 <- less specific wins
219 * 10.0.0.0/25 < 10.0.0.1/32 <- bigger base wins
228 if (rec1->addr4 < rec2->addr4) in rr_cmp()
229 return (-1); in rr_cmp()
230 else if (rec1->addr4 > rec2->addr4) in rr_cmp()
231 return (1); in rr_cmp()
237 if (rec1->mask4 < rec2->mask4) in rr_cmp()
238 return (-1); in rr_cmp()
239 else if (rec1->mask4 > rec2->mask4) in rr_cmp()
240 return (1); in rr_cmp()
254 if (ba->num_items < ba->alloc_items) { in add_array_entry()
255 ba->arr[ba->num_items++] = *br_new; in add_array_entry()
265 return (&ba->arr[ba->num_items - 1]); in get_last_entry()
271 * stack: 10.0.1.0/24,nh=3 array: 10.0.1.0/25,nh=4 -> ++10.0.1.128/24,nh=3
284 stack->num_items--; in pop_stack_entry()
287 last_array_addr = (br_prev->addr4 | ~br_prev->mask4); in pop_stack_entry()
289 last_stack_addr = (pstack->addr4 | ~pstack->mask4); in pop_stack_entry()
299 .addr4 = last_array_addr + 1, in pop_stack_entry()
300 .mask4 = pstack->mask4, in pop_stack_entry()
301 .nh = pstack->nh, in pop_stack_entry()
322 while (stack->num_items > 0) { in bsearch4_process_record()
327 * Rely on the ordering - larger prefixes comes up first in bsearch4_process_record()
330 if (pst->addr4 == (rib_entry->addr4 & pst->mask4)) in bsearch4_process_record()
337 if (dst_array->num_items > 0) { in bsearch4_process_record()
350 uint32_t last_declared_addr = br_tmp->addr4 | ~br_tmp->mask4; in bsearch4_process_record()
351 if (last_declared_addr < rib_entry->addr4 - 1) { in bsearch4_process_record()
355 .addr4 = last_declared_addr + 1, in bsearch4_process_record()
356 .mask4 = pst->mask4, in bsearch4_process_record()
357 .nh = pst->nh, in bsearch4_process_record()
369 if (br_tmp->addr4 == rib_entry->addr4) { in bsearch4_process_record()
390 * 32 prefixes for a single address, pre-allocate stack of size 32. in bsearch4_build_array()
399 for (int i = 0; i < src_array->num_items; i++) { in bsearch4_build_array()
400 struct bsearch4_record *rib_entry = &src_array->arr[i]; in bsearch4_build_array()
426 .alloc_items = bd->alloc_items, in bsearch4_build()
427 .num_items = bd->num_items, in bsearch4_build()
428 .arr = bd->rr, in bsearch4_build()
450 .alloc_items = bd->alloc_items, in bsearch4_build()
451 .arr = bd->br, in bsearch4_build()
455 bd->num_items = dst_array.num_items; in bsearch4_build()
457 free(bd->rr, M_TEMP); in bsearch4_build()
458 bd->rr = NULL; in bsearch4_build()
471 dp->f = bsearch4_lookup; in bsearch4_end_dump()
472 dp->arg = bd; in bsearch4_end_dump()
535 ent = (struct radix4_addr_entry *)(rn_match(&addr4, &rnh->rh)); in lradix4_lookup()
537 return (ent->nhop); in lradix4_lookup()
543 * Assume close-to-ideal of < 10 routes (though worse than bsearch), then
550 if (rinfo->num_prefixes < 10) in lradix4_get_pref()
552 else if (rinfo->num_prefixes < 1000) in lradix4_get_pref()
553 return (254 - rinfo->num_prefixes / 4); in lradix4_get_pref()
555 return (1); in lradix4_get_pref()
567 if (lr == NULL || !rn_inithead((void **)&lr->rnh, OFF_LEN_INET)) in lradix4_init()
571 count = rinfo.num_prefixes * 11 / 10; in lradix4_init()
573 lr->mem = malloc(sz, M_RTABLE, M_NOWAIT | M_ZERO); in lradix4_init()
574 if (lr->mem == NULL) in lradix4_init()
577 lr->rt_base = (char *)roundup2((uintptr_t)lr->mem, CACHE_LINE_SIZE); in lradix4_init()
578 lr->alloc_items = count; in lradix4_init()
579 lr->fd = fd; in lradix4_init()
591 if (lr->rnh != NULL) in lradix4_destroy()
592 rn_detachhead((void **)&lr->rnh); in lradix4_destroy()
593 if (lr->mem != NULL) in lradix4_destroy()
594 free(lr->mem, M_RTABLE); in lradix4_destroy()
609 if (lr->num_items >= lr->alloc_items) in lradix4_add_route_cb()
612 ae = (struct radix4_addr_entry *)(lr->rt_base + lr->num_items * LRADIX4_ITEM_SZ); in lradix4_add_route_cb()
613 lr->num_items++; in lradix4_add_route_cb()
615 ae->nhop = rt_get_raw_nhop(rt); in lradix4_add_route_cb()
618 ae->addr.sin_len = KEY_LEN_INET; in lradix4_add_route_cb()
619 ae->addr.sin_addr = addr4; in lradix4_add_route_cb()
629 rn = lr->rnh->rnh_addaddr((struct sockaddr *)&ae->addr, rt_mask, in lradix4_add_route_cb()
630 &lr->rnh->rh, ae->rn); in lradix4_add_route_cb()
642 dp->f = lradix4_lookup; in lradix4_end_dump()
643 dp->arg = lr->rnh; in lradix4_end_dump()
694 rn = rn_match((void *)&sin4, &rh->head); in radix4_lookup()
695 if (rn != NULL && ((rn->rn_flags & RNF_ROOT) == 0)) in radix4_lookup()
696 nh = (RNTORT(rn))->rt_nhop; in radix4_lookup()
717 r4->fd = fd; in radix4_init()
718 r4->rh = fib_get_rh(fd); in radix4_init()
744 dp->f = radix4_lookup; in radix4_end_dump()
745 dp->arg = r4->rh; in radix4_end_dump()