The branch main has been updated by pouria:

URL: 
https://cgit.FreeBSD.org/src/commit/?id=63343822430453f4add20bcbfa134c99132361df

commit 63343822430453f4add20bcbfa134c99132361df
Author:     Pouria Mousavizadeh Tehrani <[email protected]>
AuthorDate: 2026-09-18 10:09:43 +0000
Commit:     Pouria Mousavizadeh Tehrani <[email protected]>
CommitDate: 2026-09-18 10:43:05 +0000

    route/fib_algo: Fix nexthop index collision across families
    
    fib_algo indexes its idx->nhop array by the nexthop index with
    assumption of its uniqueness. Which is true except for IPv4 over
    IPv6 nexthops.
    Give each index space its own segment within the same array and
    offset the index by the segment base. Segments are created on demand
    and sized independently, so the rib's own family keeps base 0 and
    tables without cross-family nexthops index exactly as before.
    
    Reviewed by:    melifaro
    Discussed with: markj
    MFC after:      2 weeks
    Differential Revision:  https://reviews.freebsd.org/D59552
---
 sys/net/route/fib_algo.c  | 150 +++++++++++++++++++++++++++++++++++++++-------
 sys/net/route/nhgrp_ctl.c |  19 ++++++
 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 */

Reply via email to