diff options
| -rw-r--r-- | sys/net/route/fib_algo.c | 150 | ||||
| -rw-r--r-- | sys/net/route/nhgrp_ctl.c | 19 | ||||
| -rw-r--r-- | sys/net/route/nhop.h | 1 |
3 files changed, 148 insertions, 22 deletions
diff --git a/sys/net/route/fib_algo.c b/sys/net/route/fib_algo.c index 2ba044a31020..0a949ff8b776 100644 --- a/sys/net/route/fib_algo.c +++ b/sys/net/route/fib_algo.c @@ -145,6 +145,28 @@ struct nhop_ref_table { int32_t refcnt[0]; }; +/* + * Nexthop indexes are allocated per-rib, and ribs are keyed by + * (fibnum, neighbor family). A route with a gateway belonging to another + * family (an IPv4 prefix via an IPv6 nexthop, RFC 5549) therefore gets + * its index from that other family's space, where it can collide with the + * index of a native nexthop. + * + * Keep one flat idx->nhop array, but give every index space a contiguous + * segment within it, so the array offset is nhaf_base + nhop index. + * The rib's own family always owns the first segment, making the offset + * identical to the nexthop index for every table with no cross-family nexthops. + */ +struct nhop_af_table { + uint8_t nhaf_family; /* AF owning this index space */ + bool nhaf_hit; /* true if out of index space */ + uint32_t nhaf_count; /* # of indexes reserved */ + uint32_t nhaf_base; /* offset within fd->nh_idx */ +}; + +/* # of nhop index spaces per instance, currently 4o6 for now */ +#define FD_MAX_NH_AF 2 + enum fib_callout_action { FDA_NONE, /* No callout scheduled */ FDA_REBUILD, /* Asks to rebuild algo instance */ @@ -162,15 +184,20 @@ struct fib_sync_status { /* * Data structure for the fib lookup instance tied to the particular rib. + * + * Key: + * (f) - Protected by the FIB_MOD lock + * (r) - Protected by the RIB lock */ struct fib_data { - uint32_t number_nhops; /* current # of nhops */ - uint8_t hit_nhops; /* true if out of nhop limit */ - uint8_t init_done; /* true if init is competed */ - uint32_t fd_dead:1; /* Scheduled for deletion */ - uint32_t fd_linked:1; /* true if linked */ - uint32_t fd_need_rebuild:1; /* true if rebuild scheduled */ - uint32_t fd_batch:1; /* true if batched notification scheduled */ + uint32_t number_nhops; /* (r) total size of the nhop arrays */ + uint32_t fd_dead:1, /* (f) Scheduled for deletion */ + fd_linked:1; /* (f) true if linked */ + uint32_t init_done:1, /* (r) true if init is competed */ + fd_need_rebuild:1, /* (r) true if rebuild scheduled */ + fd_batch:1, /* (r) true if batched notification scheduled */ + hit_nhops:1; /* (r) true if out of nhop limit */ + uint8_t fd_num_af; /* (r) # of nhop index spaces in use */ uint8_t fd_family; /* family */ uint32_t fd_fibnum; /* fibnum */ uint32_t fd_failed_rebuilds; /* stat: failed rebuilds */ @@ -178,6 +205,7 @@ struct fib_data { struct callout fd_callout; /* rebuild callout */ enum fib_callout_action fd_callout_action; /* Callout action to take */ void *fd_algo_data; /* algorithm data */ + struct nhop_af_table fd_af[FD_MAX_NH_AF]; /* (r) index space descriptors */ struct nhop_object **nh_idx; /* nhop idx->ptr array */ struct nhop_ref_table *nh_ref_table; /* array with # of nhop references */ struct rib_head *fd_rh; /* RIB table we're attached to */ @@ -885,17 +913,37 @@ handle_rtable_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc, static void estimate_nhop_scale(const struct fib_data *old_fd, struct fib_data *fd) { + uint32_t base = 0; if (old_fd == NULL) { + fd->fd_num_af = 1; + fd->fd_af[0].nhaf_family = fd->fd_family; // TODO: read from rtable - fd->number_nhops = 16; - return; + fd->fd_af[0].nhaf_count = 16; + } else { + fd->fd_num_af = old_fd->fd_num_af; + memcpy(fd->fd_af, old_fd->fd_af, sizeof(fd->fd_af)); + + for (int i = 0; i < fd->fd_num_af; i++) { + struct nhop_af_table *nt; + + nt = &fd->fd_af[i]; + nt->nhaf_hit = false; + if (!old_fd->fd_af[i].nhaf_hit) + continue; + if (nt->nhaf_count == 0) + /* half of the main family */ + nt->nhaf_count = 8; + else if (nt->nhaf_count < FIB_MAX_NHOPS) + nt->nhaf_count *= 2; + } } - if (old_fd->hit_nhops && old_fd->number_nhops < FIB_MAX_NHOPS) - fd->number_nhops = 2 * old_fd->number_nhops; - else - fd->number_nhops = old_fd->number_nhops; + for (int i = 0; i < fd->fd_num_af; i++) { + fd->fd_af[i].nhaf_base = base; + base += fd->fd_af[i].nhaf_count; + } + fd->number_nhops = base; } struct walk_cbdata { @@ -940,7 +988,7 @@ sync_algo_end_cb(struct rib_head *rnh, enum rib_walk_hook stage, void *_data) if (w->result == FLM_SUCCESS) { /* Mark init as done to allow routing updates */ - fd->init_done = 1; + fd->init_done = true; } } @@ -1166,8 +1214,6 @@ try_setup_fd_instance(struct fib_lookup_module *flm, struct rib_head *rh, } *pfd = fd; - estimate_nhop_scale(old_fd, fd); - fd->fd_rh = rh; fd->fd_family = rh->rib_family; fd->fd_fibnum = rh->rib_fibnum; @@ -1175,6 +1221,8 @@ try_setup_fd_instance(struct fib_lookup_module *flm, struct rib_head *rh, fd->fd_vnet = curvnet; fd->fd_flm = flm; + estimate_nhop_scale(old_fd, fd); + FIB_MOD_LOCK(); flm->flm_refcount++; fd->fd_gen = ++fib_gen; @@ -1766,11 +1814,51 @@ get_nhop_idx(struct nhop_object *nh) return (nhop_get_idx(nh)); } +static uint8_t +get_nhop_family(struct nhop_object *nh) +{ + + if (NH_IS_NHGRP(nh)) + return (nhgrp_get_neigh_family((struct nhgrp_object *)nh)); + + return (nhop_get_neigh_family(nh)); +} + +/* + * Returns the index space of fd owning family, or NULL. + */ +static struct nhop_af_table * +find_af_table(struct fib_data *fd, uint8_t family) +{ + + for (int i = 0; i < fd->fd_num_af; i++) { + if (fd->fd_af[i].nhaf_family == family) + return (&fd->fd_af[i]); + } + + return (NULL); +} + +/* + * Maps nh to its offset within the flat idx->nhop array of fd. + */ +static uint32_t +get_nhop_off(struct fib_data *fd, struct nhop_object *nh) +{ + struct nhop_af_table *nt = find_af_table(fd, get_nhop_family(nh)); + uint32_t idx = get_nhop_idx(nh); + + KASSERT(nt != NULL, ("no index space for the nhop family")); + KASSERT(idx < nt->nhaf_count, ("invalid nhop index")); + + return (nt->nhaf_base + idx); +} + uint32_t fib_get_nhop_idx(struct fib_data *fd, struct nhop_object *nh) { - return (get_nhop_idx(nh)); + return (get_nhop_off(fd, nh)); } static bool @@ -1783,12 +1871,30 @@ is_idx_free(struct fib_data *fd, uint32_t index) static uint32_t fib_ref_nhop(struct fib_data *fd, struct nhop_object *nh) { - uint32_t idx = get_nhop_idx(nh); + struct nhop_af_table *nt; + uint32_t idx; + uint8_t family; + + RIB_WLOCK_ASSERT(fd->fd_rh); - if (idx >= fd->number_nhops) { + family = get_nhop_family(nh); + nt = find_af_table(fd, family); + if (nt == NULL) { + KASSERT(fd->fd_num_af < FD_MAX_NH_AF, + ("out of nhop index spaces for %s", print_family(family))); + nt = &fd->fd_af[fd->fd_num_af++]; + nt->nhaf_family = family; + nt->nhaf_count = 0; + nt->nhaf_base = 0; + } + + idx = get_nhop_idx(nh); + if (idx >= nt->nhaf_count) { + nt->nhaf_hit = true; fd->hit_nhops = 1; return (0); } + idx += nt->nhaf_base; if (is_idx_free(fd, idx)) { nhop_ref_any(nh); @@ -1844,10 +1950,10 @@ fib_schedule_release_nhop(struct fib_data *fd, struct nhop_object *nh) static void fib_unref_nhop(struct fib_data *fd, struct nhop_object *nh) { - uint32_t idx = get_nhop_idx(nh); + uint32_t idx = get_nhop_off(fd, nh); - KASSERT((idx < fd->number_nhops), ("invalid nhop index")); - KASSERT((nh == fd->nh_idx[idx]), ("index table contains whong nh")); + KASSERT(idx < fd->number_nhops, ("invalid nhop index")); + KASSERT(nh == fd->nh_idx[idx], ("index table contains whong nh")); fd->nh_ref_table->refcnt[idx]--; if (fd->nh_ref_table->refcnt[idx] == 0) { diff --git a/sys/net/route/nhgrp_ctl.c b/sys/net/route/nhgrp_ctl.c index ea1d3b089d9e..4d0694c330ba 100644 --- a/sys/net/route/nhgrp_ctl.c +++ b/sys/net/route/nhgrp_ctl.c @@ -1058,6 +1058,25 @@ nhgrp_get_idx(const struct nhgrp_object *nhg) return (nhg_priv->nhg_idx); } +/* + * Returns the address family of the nexthop index space @nhg was + * allocated from. + * + * XXX: we get group indexes from the nh_control, which is keyed by + * the neighbor family of its members. For now, all members are required + * to share that nh_control. The ideal is to support nexthop groups spanning + * multiple address families. Such a group will no longer belong to a + * single neighbor family. + */ +uint8_t +nhgrp_get_neigh_family(const struct nhgrp_object *nhg) +{ + const struct nhgrp_priv *nhg_priv; + + nhg_priv = NHGRP_PRIV_CONST(nhg); + return (nhg_priv->nh_control->ctl_rh->rib_family); +} + uint8_t nhgrp_get_origin(const struct nhgrp_object *nhg) { diff --git a/sys/net/route/nhop.h b/sys/net/route/nhop.h index 0ae41cbf8292..a4e0881760b2 100644 --- a/sys/net/route/nhop.h +++ b/sys/net/route/nhop.h @@ -223,6 +223,7 @@ struct nhgrp_object *nhgrp_alloc(uint32_t fibnum, int family, struct nhgrp_object *nhgrp_get_nhgrp(struct nhgrp_object *nhg, int *perror); void nhgrp_set_uidx(struct nhgrp_object *nhg, uint32_t uidx); uint32_t nhgrp_get_uidx(const struct nhgrp_object *nhg); +uint8_t nhgrp_get_neigh_family(const struct nhgrp_object *nhg); uint8_t nhgrp_get_origin(const struct nhgrp_object *nhg); void nhgrp_set_origin(struct nhgrp_object *nhg, uint8_t origin); #endif /* _KERNEL */ |