aboutsummaryrefslogtreecommitdiffstats
path: root/src/vnet/fib
diff options
context:
space:
mode:
Diffstat (limited to 'src/vnet/fib')
-rw-r--r--src/vnet/fib/fib_entry.c67
-rw-r--r--src/vnet/fib/fib_entry.h44
-rw-r--r--src/vnet/fib/fib_entry_src.c197
-rw-r--r--src/vnet/fib/fib_entry_src.h70
-rw-r--r--src/vnet/fib/fib_entry_src_mpls.c7
5 files changed, 264 insertions, 121 deletions
diff --git a/src/vnet/fib/fib_entry.c b/src/vnet/fib/fib_entry.c
index 35716cacc29..a9ca0f20f6d 100644
--- a/src/vnet/fib/fib_entry.c
+++ b/src/vnet/fib/fib_entry.c
@@ -213,29 +213,33 @@ fib_entry_last_lock_gone (fib_node_t *node)
FIB_ENTRY_DBG(fib_entry, "last-lock");
fib_node_deinit(&fib_entry->fe_node);
- // FIXME -RR Backwalk
ASSERT(0 == vec_len(fib_entry->fe_delegates));
vec_free(fib_entry->fe_delegates);
- vec_free(fib_entry->fe_srcs);
+ if (fib_entry_has_multiple_srcs(fib_entry))
+ {
+ vec_free(fib_entry->fe_u_src.fe_srcs);
+ }
pool_put(fib_entry_pool, fib_entry);
}
-static fib_entry_src_t*
+static const fib_entry_src_t*
fib_entry_get_best_src_i (const fib_entry_t *fib_entry)
{
- fib_entry_src_t *bsrc;
+ const fib_entry_src_t *bsrc;
/*
* the enum of sources is deliberately arranged in priority order
*/
- if (0 == vec_len(fib_entry->fe_srcs))
+ if (fib_entry_has_multiple_srcs(fib_entry))
{
- bsrc = NULL;
+ ASSERT(vec_len(fib_entry->fe_u_src.fe_srcs));
+
+ bsrc = vec_elt_at_index(fib_entry->fe_u_src.fe_srcs, 0);
}
else
{
- bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
+ bsrc = &fib_entry->fe_u_src.fe_src;
}
return (bsrc);
@@ -248,7 +252,7 @@ fib_entry_src_get_source (const fib_entry_src_t *esrc)
{
return (esrc->fes_src);
}
- return (FIB_SOURCE_MAX);
+ return (FIB_SOURCE_INVALID);
}
static fib_entry_flag_t
@@ -262,6 +266,18 @@ fib_entry_src_get_flags (const fib_entry_src_t *esrc)
}
fib_entry_flag_t
+fib_entry_get_flags_i (const fib_entry_t *fib_entry)
+{
+ const fib_entry_src_t *esrc;
+
+ esrc = fib_entry_get_best_src_i(fib_entry);
+
+ ASSERT(esrc);
+
+ return (esrc->fes_entry_flags);
+}
+
+fib_entry_flag_t
fib_entry_get_flags (fib_node_index_t fib_entry_index)
{
return (fib_entry_get_flags_i(fib_entry_get(fib_entry_index)));
@@ -330,11 +346,18 @@ fib_entry_show_memory (void)
pool_foreach(entry, fib_entry_pool,
({
- n_srcs += vec_len(entry->fe_srcs);
- vec_foreach(esrc, entry->fe_srcs)
- {
- n_exts += fib_path_ext_list_length(&esrc->fes_path_exts);
- }
+ if (fib_entry_has_multiple_srcs(entry))
+ {
+ n_srcs += vec_len(entry->fe_u_src.fe_srcs);
+ vec_foreach(esrc, entry->fe_u_src.fe_srcs)
+ {
+ n_exts += fib_path_ext_list_length(&esrc->fes_path_exts);
+ }
+ }
+ else
+ {
+ n_exts += fib_path_ext_list_length(&entry->fe_u_src.fe_src.fes_path_exts);
+ }
}));
fib_show_memory_usage("Entry Source",
@@ -795,10 +818,10 @@ fib_entry_special_add (fib_node_index_t fib_entry_index,
fib_entry_flag_t flags,
const dpo_id_t *dpo)
{
+ const fib_entry_src_t *bsrc;
fib_source_t best_source;
fib_entry_flag_t bflags;
fib_entry_t *fib_entry;
- fib_entry_src_t *bsrc;
fib_entry = fib_entry_get(fib_entry_index);
@@ -816,10 +839,10 @@ fib_entry_special_update (fib_node_index_t fib_entry_index,
fib_entry_flag_t flags,
const dpo_id_t *dpo)
{
+ const fib_entry_src_t *bsrc;
fib_source_t best_source;
fib_entry_flag_t bflags;
fib_entry_t *fib_entry;
- fib_entry_src_t *bsrc;
fib_entry = fib_entry_get(fib_entry_index);
@@ -838,10 +861,10 @@ fib_entry_path_add (fib_node_index_t fib_entry_index,
fib_entry_flag_t flags,
const fib_route_path_t *rpath)
{
+ const fib_entry_src_t *bsrc;
fib_source_t best_source;
fib_entry_flag_t bflags;
fib_entry_t *fib_entry;
- fib_entry_src_t *bsrc;
ASSERT(1 == vec_len(rpath));
@@ -900,11 +923,11 @@ fib_entry_path_remove (fib_node_index_t fib_entry_index,
fib_source_t source,
const fib_route_path_t *rpath)
{
+ const fib_entry_src_t *bsrc;
fib_entry_src_flag_t sflag;
fib_source_t best_source;
fib_entry_flag_t bflags;
fib_entry_t *fib_entry;
- fib_entry_src_t *bsrc;
ASSERT(1 == vec_len(rpath));
@@ -951,7 +974,7 @@ fib_entry_path_remove (fib_node_index_t fib_entry_index,
bsrc = fib_entry_get_best_src_i(fib_entry);
best_source = fib_entry_src_get_source(bsrc);
- if (FIB_SOURCE_MAX == best_source) {
+ if (FIB_SOURCE_INVALID == best_source) {
/*
* no more sources left. this entry is toast.
*/
@@ -996,11 +1019,11 @@ fib_entry_src_flag_t
fib_entry_special_remove (fib_node_index_t fib_entry_index,
fib_source_t source)
{
+ const fib_entry_src_t *bsrc;
fib_entry_src_flag_t sflag;
fib_source_t best_source;
fib_entry_flag_t bflags;
fib_entry_t *fib_entry;
- fib_entry_src_t *bsrc;
fib_entry = fib_entry_get(fib_entry_index);
ASSERT(NULL != fib_entry);
@@ -1041,7 +1064,7 @@ fib_entry_special_remove (fib_node_index_t fib_entry_index,
bsrc = fib_entry_get_best_src_i(fib_entry);
best_source = fib_entry_src_get_source(bsrc);
- if (FIB_SOURCE_MAX == best_source) {
+ if (FIB_SOURCE_INVALID == best_source) {
/*
* no more sources left. this entry is toast.
*/
@@ -1098,10 +1121,10 @@ fib_entry_update (fib_node_index_t fib_entry_index,
fib_entry_flag_t flags,
const fib_route_path_t *paths)
{
+ const fib_entry_src_t *bsrc;
fib_source_t best_source;
fib_entry_flag_t bflags;
fib_entry_t *fib_entry;
- fib_entry_src_t *bsrc;
fib_entry = fib_entry_get(fib_entry_index);
ASSERT(NULL != fib_entry);
@@ -1361,8 +1384,8 @@ fib_entry_get_resolving_interface (fib_node_index_t entry_index)
fib_source_t
fib_entry_get_best_source (fib_node_index_t entry_index)
{
+ const fib_entry_src_t *bsrc;
fib_entry_t *fib_entry;
- fib_entry_src_t *bsrc;
fib_entry = fib_entry_get(entry_index);
diff --git a/src/vnet/fib/fib_entry.h b/src/vnet/fib/fib_entry.h
index cd2a685b765..cd954e3a15c 100644
--- a/src/vnet/fib/fib_entry.h
+++ b/src/vnet/fib/fib_entry.h
@@ -29,6 +29,10 @@
*/
typedef enum fib_source_t_ {
/**
+ * An invalid source of value 0
+ */
+ FIB_SOURCE_INVALID,
+ /**
* Marker. Add new values after this one.
*/
FIB_SOURCE_FIRST,
@@ -142,6 +146,7 @@ STATIC_ASSERT (sizeof(fib_source_t) == 1,
#define FIB_SOURCE_MAX (FIB_SOURCE_LAST+1)
#define FIB_SOURCES { \
+ [FIB_SOURCE_INVALID] = "invalid", \
[FIB_SOURCE_SPECIAL] = "special", \
[FIB_SOURCE_INTERFACE] = "interface", \
[FIB_SOURCE_PROXY] = "proxy", \
@@ -377,6 +382,29 @@ typedef struct fib_entry_src_t_ {
} fib_entry_src_t;
/**
+ * FIB entry flags.
+ * these are stored in the pad space within the fib_node_t
+ */
+typedef enum fib_entry_node_attribute_t_
+{
+ /**
+ * FIB entry has multiple sources, so the fe_srcs union
+ * uses the vector
+ */
+ FIB_ENTRY_NODE_ATTR_MULTIPLE_SRCS,
+} fib_entry_node_attribute_t;
+
+#define FIB_ENTRY_NODE_FLAG_NAMES { \
+ [FIB_ENTRY_NODE_ATTR_MULTIPLE_SRCS] = "multiple-srcs", \
+}
+
+typedef enum fib_entry_node_flags_t_
+{
+ FIB_ENTRY_NODE_FLAG_MULTIPLE_SRCS = (1 << FIB_ENTRY_NODE_ATTR_MULTIPLE_SRCS),
+} fib_entry_node_flags_t;
+
+
+/**
* An entry in a FIB table.
*
* This entry represents a route added to the FIB that is stored
@@ -409,12 +437,20 @@ typedef struct fib_entry_t_ {
* type to derive the EOS bit value.
*/
dpo_id_t fe_lb;
+
/**
- * Vector of source infos.
- * Most entries will only have 1 source. So we optimise for memory usage,
- * which is preferable since we have many entries.
+ * Source info.
+ * in the majority of cases a FIB entry will have only one source.
+ * so to save the extra memory allocation of the source's vector, we
+ * store space for one source inline. When two sources are present,
+ * we burn extra memory.
+ * The union is switched based on the FIB_ENTRY_NODE_FLAG_MULTIPLE_SRCS
*/
- fib_entry_src_t *fe_srcs;
+ union {
+ fib_entry_src_t *fe_srcs;
+ fib_entry_src_t fe_src;
+ } fe_u_src;
+
/**
* the path-list for which this entry is a child. This is also the path-list
* that is contributing forwarding for this entry.
diff --git a/src/vnet/fib/fib_entry_src.c b/src/vnet/fib/fib_entry_src.c
index 214dafe9b8d..acb8579e85e 100644
--- a/src/vnet/fib/fib_entry_src.c
+++ b/src/vnet/fib/fib_entry_src.c
@@ -61,13 +61,62 @@ fib_entry_src_action_init (fib_entry_t *fib_entry,
fib_entry_src_vft[source].fesv_init(&esrc);
}
- vec_add1(fib_entry->fe_srcs, esrc);
- vec_sort_with_function(fib_entry->fe_srcs,
- fib_entry_src_cmp_for_sort);
+ if (fib_entry_has_multiple_srcs(fib_entry))
+ {
+ vec_add1(fib_entry->fe_u_src.fe_srcs, esrc);
+
+ vec_sort_with_function(fib_entry->fe_u_src.fe_srcs,
+ fib_entry_src_cmp_for_sort);
+ }
+ else
+ {
+ /*
+ * is this the very first source
+ */
+ if (FIB_SOURCE_INVALID == fib_entry->fe_u_src.fe_src.fes_src)
+ {
+ clib_memcpy(&fib_entry->fe_u_src.fe_src, &esrc, sizeof(esrc));
+ }
+ else
+ {
+ /*
+ * transitioning to multiple sources.
+ * allocate the vecotr of sources.
+ */
+ fib_entry_src_t *srcs = NULL;
+
+ vec_validate(srcs, 1);
+
+ /*
+ * sorted insert
+ */
+ if (fib_entry->fe_u_src.fe_src.fes_src < esrc.fes_src)
+ {
+ srcs[0] = fib_entry->fe_u_src.fe_src;
+ srcs[1] = esrc;
+ }
+ else
+ {
+ srcs[0] = esrc;
+ srcs[1] = fib_entry->fe_u_src.fe_src;
+ }
+ memset(&fib_entry->fe_u_src.fe_src, 0,
+ sizeof(fib_entry->fe_u_src.fe_src));
+ fib_entry->fe_u_src.fe_srcs = srcs;
+
+ fib_entry->fe_node.fn_pad |= FIB_ENTRY_NODE_FLAG_MULTIPLE_SRCS;
+ }
+ }
+}
+
+u32
+fib_entry_has_multiple_srcs(const fib_entry_t * fib_entry)
+{
+ return (fib_entry->fe_node.fn_pad & FIB_ENTRY_NODE_FLAG_MULTIPLE_SRCS);
}
static fib_entry_src_t *
-fib_entry_src_find (const fib_entry_t *fib_entry,
+fib_entry_src_find (fib_entry_t *fib_entry,
fib_source_t source,
u32 *index)
@@ -76,20 +125,80 @@ fib_entry_src_find (const fib_entry_t *fib_entry,
int ii;
ii = 0;
- vec_foreach(esrc, fib_entry->fe_srcs)
+ if (fib_entry_has_multiple_srcs(fib_entry))
{
- if (esrc->fes_src == source)
- {
- if (NULL != index)
- {
- *index = ii;
- }
- return (esrc);
- }
- else
- {
- ii++;
- }
+ vec_foreach(esrc, fib_entry->fe_u_src.fe_srcs)
+ {
+ if (esrc->fes_src == source)
+ {
+ if (NULL != index)
+ {
+ *index = ii;
+ }
+ return (esrc);
+ }
+ else
+ {
+ ii++;
+ }
+ }
+ }
+ else
+ {
+ esrc = &fib_entry->fe_u_src.fe_src;
+ if (esrc->fes_src == source)
+ {
+ if (NULL != index)
+ {
+ *index = -1;
+ }
+ return (esrc);
+ }
+ }
+
+ return (NULL);
+}
+
+static fib_entry_src_t *
+fib_entry_src_delete (fib_entry_t *fib_entry,
+ u32 index)
+
+{
+ if (-1 == index)
+ {
+ ASSERT(!fib_entry_has_multiple_srcs(fib_entry));
+ memset(&fib_entry->fe_u_src.fe_src, 0,
+ sizeof(fib_entry->fe_u_src.fe_src));
+ }
+ else
+ {
+ vec_del1(fib_entry->fe_u_src.fe_srcs, index);
+
+ ASSERT(vec_len(fib_entry->fe_u_src.fe_srcs));
+ if (1 == vec_len(fib_entry->fe_u_src.fe_srcs))
+ {
+ /*
+ * Is there much point in transitioning back?
+ * We've paid the cost of the malloc for the vector,
+ * why not keep it.
+ * Favour memory use. If the expectation that multiple sources
+ * is rare is correct, then we should expect this entry is
+ * unlikely to need the vector again
+ */
+ fib_entry_src_t *srcs;
+
+ srcs = fib_entry->fe_u_src.fe_srcs;
+ fib_entry->fe_node.fn_pad &= ~FIB_ENTRY_NODE_FLAG_MULTIPLE_SRCS;
+ clib_memcpy(&fib_entry->fe_u_src.fe_src,
+ &srcs[0],
+ sizeof(fib_entry->fe_u_src.fe_src));
+ vec_free(srcs);
+ }
+ else
+ {
+ vec_sort_with_function(fib_entry->fe_u_src.fe_srcs,
+ fib_entry_src_cmp_for_sort);
+ }
}
return (NULL);
@@ -108,8 +217,7 @@ fib_entry_is_sourced (fib_node_index_t fib_entry_index,
static fib_entry_src_t *
fib_entry_src_find_or_create (fib_entry_t *fib_entry,
- fib_source_t source,
- u32 *index)
+ fib_source_t source)
{
fib_entry_src_t *esrc;
@@ -141,7 +249,7 @@ fib_entry_src_action_deinit (fib_entry_t *fib_entry,
}
fib_path_ext_list_flush(&esrc->fes_path_exts);
- vec_del1(fib_entry->fe_srcs, index);
+ fib_entry_src_delete(fib_entry, index);
}
fib_entry_src_cover_res_t
@@ -744,23 +852,6 @@ fib_entry_src_action_deactivate (fib_entry_t *fib_entry,
fib_entry->fe_sibling = FIB_NODE_INDEX_INVALID;
}
-static void
-fib_entry_src_action_fwd_update (const fib_entry_t *fib_entry,
- fib_source_t source)
-{
- fib_entry_src_t *esrc;
-
- vec_foreach(esrc, fib_entry->fe_srcs)
- {
- if (NULL != fib_entry_src_vft[esrc->fes_src].fesv_fwd_update)
- {
- fib_entry_src_vft[esrc->fes_src].fesv_fwd_update(esrc,
- fib_entry,
- source);
- }
- }
-}
-
void
fib_entry_src_action_reactivate (fib_entry_t *fib_entry,
fib_source_t source)
@@ -813,11 +904,10 @@ fib_entry_src_action_reactivate (fib_entry_t *fib_entry,
fib_path_list_unlock(path_list_index);
}
fib_entry_src_action_install(fib_entry, source);
- fib_entry_src_action_fwd_update(fib_entry, source);
}
void
-fib_entry_src_action_installed (const fib_entry_t *fib_entry,
+fib_entry_src_action_installed (fib_entry_t *fib_entry,
fib_source_t source)
{
fib_entry_src_t *esrc;
@@ -829,8 +919,6 @@ fib_entry_src_action_installed (const fib_entry_t *fib_entry,
fib_entry_src_vft[source].fesv_installed(esrc,
fib_entry);
}
-
- fib_entry_src_action_fwd_update(fib_entry, source);
}
/*
@@ -850,7 +938,7 @@ fib_entry_src_action_add (fib_entry_t *fib_entry,
fib_node_index_t fib_entry_index;
fib_entry_src_t *esrc;
- esrc = fib_entry_src_find_or_create(fib_entry, source, NULL);
+ esrc = fib_entry_src_find_or_create(fib_entry, source);
esrc->fes_ref_count++;
@@ -909,7 +997,7 @@ fib_entry_src_action_update (fib_entry_t *fib_entry,
fib_node_index_t fib_entry_index, old_path_list_index;
fib_entry_src_t *esrc;
- esrc = fib_entry_src_find_or_create(fib_entry, source, NULL);
+ esrc = fib_entry_src_find_or_create(fib_entry, source);
if (NULL == esrc)
return (fib_entry_src_action_add(fib_entry, source, flags, dpo));
@@ -1369,29 +1457,6 @@ fib_entry_get_flags_for_source (fib_node_index_t entry_index,
return (FIB_ENTRY_FLAG_NONE);
}
-fib_entry_flag_t
-fib_entry_get_flags_i (const fib_entry_t *fib_entry)
-{
- fib_entry_flag_t flags;
-
- /*
- * the vector of sources is deliberately arranged in priority order
- */
- if (0 == vec_len(fib_entry->fe_srcs))
- {
- flags = FIB_ENTRY_FLAG_NONE;
- }
- else
- {
- fib_entry_src_t *esrc;
-
- esrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
- flags = esrc->fes_entry_flags;
- }
-
- return (flags);
-}
-
void
fib_entry_set_source_data (fib_node_index_t fib_entry_index,
fib_source_t source,
diff --git a/src/vnet/fib/fib_entry_src.h b/src/vnet/fib/fib_entry_src.h
index 35c43936a1f..a19fae10a1c 100644
--- a/src/vnet/fib/fib_entry_src.h
+++ b/src/vnet/fib/fib_entry_src.h
@@ -105,15 +105,6 @@ typedef fib_entry_src_cover_res_t (*fib_entry_src_cover_update_t)(
const fib_entry_t *fib_entry);
/**
- * Forwarding updated. Notification that the forwarding information for the
- * entry has been updated. This notification is sent to all sources, not just
- * the active best.
- */
-typedef void (*fib_entry_src_fwd_update_t)(fib_entry_src_t *src,
- const fib_entry_t *fib_entry,
- fib_source_t best_source);
-
-/**
* Installed. Notification that the source is now installed as
* the entry's forwarding source.
*/
@@ -182,22 +173,56 @@ typedef struct fib_entry_src_vft_t_ {
fib_entry_src_cover_update_t fesv_cover_update;
fib_entry_src_format_t fesv_format;
fib_entry_src_installed_t fesv_installed;
- fib_entry_src_fwd_update_t fesv_fwd_update;
fib_entry_src_get_data_t fesv_get_data;
fib_entry_src_set_data_t fesv_set_data;
} fib_entry_src_vft_t;
-#define FOR_EACH_SRC_ADDED(_entry, _src, _source, action) \
-{ \
- vec_foreach(_src, _entry->fe_srcs) \
- { \
- if (_src->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED) { \
- _source = _src->fes_src; \
- do { \
- action; \
- } while(0); \
- } \
- } \
+#define FOR_EACH_SRC_ADDED(_entry, _src, _source, action) \
+{ \
+ if (fib_entry_has_multiple_srcs(_entry)) \
+ { \
+ vec_foreach(_src, _entry->fe_u_src.fe_srcs) \
+ { \
+ if (_src->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED) { \
+ _source = _src->fes_src; \
+ do { \
+ action; \
+ } while(0); \
+ } \
+ } \
+ } \
+ else \
+ { \
+ _src = &_entry->fe_u_src.fe_src; \
+ if (_src->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED) { \
+ _source = _src->fes_src; \
+ do { \
+ action; \
+ } while(0); \
+ } \
+ } \
+}
+
+#define FOR_EACH_SRC(_entry, _src, _source, action) \
+{ \
+ if (fib_entry_has_multiple_srcs(_entry)) \
+ { \
+ vec_foreach(_src, _entry->fe_u_src.fe_srcs) \
+ { \
+ _source = _src->fes_src; \
+ do { \
+ action; \
+ } while(0); \
+ } \
+ } \
+ else \
+ { \
+ _src = &_entry->fe_u_src.fe_src; \
+ _source = _src->fes_src; \
+ do { \
+ action; \
+ } while(0); \
+ } \
}
extern u8* fib_entry_src_format(fib_entry_t *entry,
@@ -260,7 +285,7 @@ extern fib_entry_src_flag_t fib_entry_src_action_path_remove(fib_entry_t *fib_en
fib_source_t source,
const fib_route_path_t *path);
-extern void fib_entry_src_action_installed(const fib_entry_t *fib_entry,
+extern void fib_entry_src_action_installed(fib_entry_t *fib_entry,
fib_source_t source);
extern fib_forward_chain_type_t fib_entry_get_default_chain_type(
@@ -279,6 +304,7 @@ extern void fib_entry_src_mk_lb (fib_entry_t *fib_entry,
extern fib_protocol_t fib_entry_get_proto(const fib_entry_t * fib_entry);
extern dpo_proto_t fib_entry_get_dpo_proto(const fib_entry_t * fib_entry);
+extern u32 fib_entry_has_multiple_srcs(const fib_entry_t * fib_entry);
/*
* Per-source registration. declared here so we save a separate .h file for each
diff --git a/src/vnet/fib/fib_entry_src_mpls.c b/src/vnet/fib/fib_entry_src_mpls.c
index f80d42afbb0..f95ca657705 100644
--- a/src/vnet/fib/fib_entry_src_mpls.c
+++ b/src/vnet/fib/fib_entry_src_mpls.c
@@ -181,13 +181,6 @@ const static fib_entry_src_vft_t mpls_src_vft = {
.fesv_format = fib_entry_src_mpls_format,
.fesv_set_data = fib_entry_src_mpls_set_data,
.fesv_get_data = fib_entry_src_mpls_get_data,
- /*
- * .fesv_fwd_update = fib_entry_src_mpls_fwd_update,
- * When the forwarding for the IP entry is updated, any MPLS chains
- * it has created are also updated. Since the MPLS entry will have already
- * installed that chain/load-balance there is no need to update the netry
- * FIXME: later: propagate any walk to the children of the MPLS entry. for SR
- */
};
void