sys/netinet6/in6_fib_algo.c

   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);