1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 3 * 4 * Copyright (c) 2020 Alexander V. Chernikov 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 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 */ 27 28 #include <sys/cdefs.h> 29 __FBSDID("$FreeBSD$"); 30 #include "opt_inet6.h" 31 32 #include <sys/param.h> 33 #include <sys/eventhandler.h> 34 #include <sys/kernel.h> 35 #include <sys/lock.h> 36 #include <sys/rmlock.h> 37 #include <sys/malloc.h> 38 #include <sys/mbuf.h> 39 #include <sys/module.h> 40 #include <sys/kernel.h> 41 #include <sys/priv.h> 42 #include <sys/proc.h> 43 #include <sys/socket.h> 44 #include <sys/socketvar.h> 45 #include <sys/sysctl.h> 46 #include <net/vnet.h> 47 48 #include <net/if.h> 49 #include <net/if_var.h> 50 51 #include <netinet/in.h> 52 #include <netinet/in_var.h> 53 #include <netinet/ip.h> 54 #include <netinet/ip_var.h> 55 #include <netinet/ip6.h> 56 #include <netinet6/ip6_var.h> 57 #include <netinet6/in6_fib.h> 58 59 #include <net/route.h> 60 #include <net/route/nhop.h> 61 #include <net/route/route_ctl.h> 62 #include <net/route/route_var.h> 63 #include <net/route/fib_algo.h> 64 65 /* 66 * Lockless radix lookup algo. 67 * 68 * Compiles immutable radix from the current routing table. 69 * Used with small amount of routes (<1000). 70 * As datastructure is immutable, it gets rebuild on each rtable change. 71 * 72 */ 73 74 #define KEY_LEN_INET6 (offsetof(struct sa_in6, sin6_addr) + sizeof(struct in6_addr)) 75 #define OFF_LEN_INET6 (8 * offsetof(struct sa_in6, sin6_addr)) 76 struct sa_in6 { 77 uint8_t sin6_len; 78 uint8_t sin6_family; 79 uint8_t pad[6]; 80 struct in6_addr sin6_addr; 81 }; 82 struct radix6_addr_entry { 83 struct radix_node rn[2]; 84 struct sa_in6 addr; 85 struct nhop_object *nhop; 86 }; 87 #define LRADIX6_ITEM_SZ roundup2(sizeof(struct radix6_addr_entry), CACHE_LINE_SIZE) 88 89 struct lradix6_data { 90 struct radix_node_head *rnh; 91 struct fib_data *fd; 92 void *mem; // raw radix_mem pointer to free 93 void *radix_mem; 94 uint32_t alloc_items; 95 uint32_t num_items; 96 }; 97 98 static struct nhop_object * 99 lradix6_lookup(void *algo_data, const struct flm_lookup_key key, uint32_t scopeid) 100 { 101 struct radix_node_head *rnh = (struct radix_node_head *)algo_data; 102 struct radix6_addr_entry *ent; 103 struct sa_in6 addr6 = { 104 .sin6_len = KEY_LEN_INET6, 105 .sin6_addr = *key.addr6, 106 }; 107 if (IN6_IS_SCOPE_LINKLOCAL(key.addr6)) 108 addr6.sin6_addr.s6_addr16[1] = htons(scopeid & 0xffff); 109 ent = (struct radix6_addr_entry *)(rn_match(&addr6, &rnh->rh)); 110 if (ent != NULL) 111 return (ent->nhop); 112 return (NULL); 113 } 114 115 static uint8_t 116 lradix6_get_pref(const struct rib_rtable_info *rinfo) 117 { 118 119 if (rinfo->num_prefixes < 10) 120 return (255); 121 else if (rinfo->num_prefixes < 10000) 122 return (255 - rinfo->num_prefixes / 40); 123 else 124 return (1); 125 } 126 127 static enum flm_op_result 128 lradix6_init(uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data) 129 { 130 struct lradix6_data *lr; 131 struct rib_rtable_info rinfo; 132 uint32_t count; 133 void *mem; 134 135 lr = malloc(sizeof(struct lradix6_data), M_RTABLE, M_NOWAIT | M_ZERO); 136 if (lr == NULL || !rn_inithead((void **)&lr->rnh, OFF_LEN_INET6)) 137 return (FLM_REBUILD); 138 fib_get_rtable_info(fib_get_rh(fd), &rinfo); 139 140 count = rinfo.num_prefixes * 11 / 10; 141 // count+1 adds at least 1 cache line 142 mem = malloc((count + 1) * LRADIX6_ITEM_SZ, M_RTABLE, M_NOWAIT | M_ZERO); 143 if (mem == NULL) 144 return (FLM_REBUILD); 145 lr->mem = mem; 146 lr->radix_mem = (void *)roundup2((uintptr_t)mem, CACHE_LINE_SIZE); 147 lr->alloc_items = count; 148 lr->fd = fd; 149 150 *_data = lr; 151 152 return (FLM_SUCCESS); 153 } 154 155 static void 156 lradix6_destroy(void *_data) 157 { 158 struct lradix6_data *lr = (struct lradix6_data *)_data; 159 160 if (lr->rnh != NULL) 161 rn_detachhead((void **)&lr->rnh); 162 if (lr->mem != NULL) 163 free(lr->mem, M_RTABLE); 164 free(lr, M_RTABLE); 165 } 166 167 static enum flm_op_result 168 lradix6_add_route_cb(struct rtentry *rt, void *_data) 169 { 170 struct lradix6_data *lr = (struct lradix6_data *)_data; 171 struct radix6_addr_entry *ae; 172 struct sockaddr_in6 *rt_dst, *rt_mask; 173 struct sa_in6 mask; 174 struct radix_node *rn; 175 struct nhop_object *nh; 176 177 nh = rt_get_raw_nhop(rt); 178 179 if (lr->num_items >= lr->alloc_items) 180 return (FLM_REBUILD); 181 182 ae = (struct radix6_addr_entry *)((char *)lr->radix_mem + lr->num_items * LRADIX6_ITEM_SZ); 183 lr->num_items++; 184 185 ae->nhop = nh; 186 187 rt_dst = (struct sockaddr_in6 *)rt_key(rt); 188 rt_mask = (struct sockaddr_in6 *)rt_mask(rt); 189 190 ae->addr.sin6_len = KEY_LEN_INET6; 191 ae->addr.sin6_addr = rt_dst->sin6_addr; 192 193 if (rt_mask != NULL) { 194 bzero(&mask, sizeof(mask)); 195 mask.sin6_len = KEY_LEN_INET6; 196 mask.sin6_addr = rt_mask->sin6_addr; 197 rt_mask = (struct sockaddr_in6 *)&mask; 198 } 199 200 rn = lr->rnh->rnh_addaddr((struct sockaddr *)&ae->addr, 201 (struct sockaddr *)rt_mask, &lr->rnh->rh, ae->rn); 202 if (rn == NULL) 203 return (FLM_REBUILD); 204 205 return (FLM_SUCCESS); 206 } 207 208 static enum flm_op_result 209 lradix6_end_dump(void *_data, struct fib_dp *dp) 210 { 211 struct lradix6_data *lr = (struct lradix6_data *)_data; 212 213 dp->f = lradix6_lookup; 214 dp->arg = lr->rnh; 215 216 return (FLM_SUCCESS); 217 } 218 219 static enum flm_op_result 220 lradix6_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc, 221 void *_data) 222 { 223 224 return (FLM_REBUILD); 225 } 226 227 struct fib_lookup_module flm_radix6_lockless = { 228 .flm_name = "radix6_lockless", 229 .flm_family = AF_INET6, 230 .flm_init_cb = lradix6_init, 231 .flm_destroy_cb = lradix6_destroy, 232 .flm_dump_rib_item_cb = lradix6_add_route_cb, 233 .flm_dump_end_cb = lradix6_end_dump, 234 .flm_change_rib_item_cb = lradix6_change_cb, 235 .flm_get_pref = lradix6_get_pref, 236 }; 237 238 /* 239 * Fallback lookup algorithm. 240 * This is a simple wrapper around system radix. 241 */ 242 243 struct radix6_data { 244 struct fib_data *fd; 245 struct rib_head *rh; 246 }; 247 248 static struct nhop_object * 249 radix6_lookup(void *algo_data, const struct flm_lookup_key key, uint32_t scopeid) 250 { 251 RIB_RLOCK_TRACKER; 252 struct rib_head *rh = (struct rib_head *)algo_data; 253 struct radix_node *rn; 254 struct nhop_object *nh; 255 256 /* Prepare lookup key */ 257 struct sockaddr_in6 sin6 = { 258 .sin6_family = AF_INET6, 259 .sin6_len = sizeof(struct sockaddr_in6), 260 .sin6_addr = *key.addr6, 261 }; 262 if (IN6_IS_SCOPE_LINKLOCAL(key.addr6)) 263 sin6.sin6_addr.s6_addr16[1] = htons(scopeid & 0xffff); 264 265 nh = NULL; 266 RIB_RLOCK(rh); 267 rn = rn_match((void *)&sin6, &rh->head); 268 if (rn != NULL && ((rn->rn_flags & RNF_ROOT) == 0)) 269 nh = (RNTORT(rn))->rt_nhop; 270 RIB_RUNLOCK(rh); 271 272 return (nh); 273 } 274 275 struct nhop_object * 276 fib6_radix_lookup_nh(uint32_t fibnum, const struct in6_addr *dst6, uint32_t scopeid) 277 { 278 struct rib_head *rh = rh = rt_tables_get_rnh(fibnum, AF_INET6); 279 const struct flm_lookup_key key = { .addr6 = dst6 }; 280 281 if (rh == NULL) 282 return (NULL); 283 284 return (radix6_lookup(rh, key, scopeid)); 285 } 286 287 static uint8_t 288 radix6_get_pref(const struct rib_rtable_info *rinfo) 289 { 290 291 return (50); 292 } 293 294 static enum flm_op_result 295 radix6_init(uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data) 296 { 297 struct radix6_data *r6; 298 299 r6 = malloc(sizeof(struct radix6_data), M_RTABLE, M_NOWAIT | M_ZERO); 300 if (r6 == NULL) 301 return (FLM_REBUILD); 302 r6->fd = fd; 303 r6->rh = fib_get_rh(fd); 304 305 *_data = r6; 306 307 return (FLM_SUCCESS); 308 } 309 310 static void 311 radix6_destroy(void *_data) 312 { 313 314 free(_data, M_RTABLE); 315 } 316 317 static enum flm_op_result 318 radix6_add_route_cb(struct rtentry *rt, void *_data) 319 { 320 321 return (FLM_SUCCESS); 322 } 323 324 static enum flm_op_result 325 radix6_end_dump(void *_data, struct fib_dp *dp) 326 { 327 struct radix6_data *r6 = (struct radix6_data *)_data; 328 329 dp->f = radix6_lookup; 330 dp->arg = r6->rh; 331 332 return (FLM_SUCCESS); 333 } 334 335 static enum flm_op_result 336 radix6_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc, 337 void *_data) 338 { 339 340 return (FLM_SUCCESS); 341 } 342 343 struct fib_lookup_module flm_radix6 = { 344 .flm_name = "radix6", 345 .flm_family = AF_INET6, 346 .flm_init_cb = radix6_init, 347 .flm_destroy_cb = radix6_destroy, 348 .flm_dump_rib_item_cb = radix6_add_route_cb, 349 .flm_dump_end_cb = radix6_end_dump, 350 .flm_change_rib_item_cb = radix6_change_cb, 351 .flm_get_pref = radix6_get_pref, 352 }; 353 354 static void 355 fib6_algo_init(void) 356 { 357 358 fib_module_register(&flm_radix6_lockless); 359 fib_module_register(&flm_radix6); 360 } 361 SYSINIT(fib6_algo_init, SI_SUB_PROTO_DOMAIN, SI_ORDER_THIRD, fib6_algo_init, NULL); 362