summaryrefslogtreecommitdiffstats
path: root/src/plugins/l2e/l2e_node.c
blob: 71c9b4bc6afc6f7cbedef80a75130f2f137fa2a9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
/*
 * l2e_node.c : l2 emulation node
 *
 * Copyright (c) 2019 Cisco and/or its affiliates.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#include <plugins/l2e/l2e.h>
#include <vnet/l2/l2_input.h>
#include <vnet/l2/feat_bitmap.h>

#define foreach_l2_emulation                    \
  _(IP4, "Extract IPv4")                        \
  _(IP6, "Extract IPv6")

typedef enum
{
#define _(sym,str) L2_EMULATION_ERROR_##sym,
  foreach_l2_emulation
#undef _
    L2_EMULATION_N_ERROR,
} l2_emulation_error_t;

static char *l2_emulation_error_strings[] = {
#define _(sym,string) string,
  foreach_l2_emulation
#undef _
};

typedef enum
{
#define _(sym,str) L2_EMULATION_NEXT_##sym,
  foreach_l2_emulation
#undef _
    L2_EMULATION_N_NEXT,
} l2_emulation_next_t;

/* packet trace format function */
static u8 *
format_l2_emulation_trace (u8 * s, va_list * args)
{
  CLIB_UNUSED (vlib_main_t * vm) = va_arg (*args, vlib_main_t *);
  CLIB_UNUSED (vlib_node_t * node) = va_arg (*args, vlib_node_t *);
  l2_emulation_trace_t *t = va_arg (*args, l2_emulation_trace_t *);

  s = format (s, "l2-emulation: %s", (t->extracted ? "yes" : "no"));

  return s;
}

VLIB_NODE_FN (l2_emulation_node) (vlib_main_t * vm,
				  vlib_node_runtime_t * node,
				  vlib_frame_t * frame)
{
  l2_emulation_main_t *em = &l2_emulation_main;
  u32 n_left_from, *from, *to_next;
  l2_emulation_next_t next_index;
  u32 ip4_hits = 0;
  u32 ip6_hits = 0;

  next_index = 0;
  n_left_from = frame->n_vectors;
  from = vlib_frame_vector_args (frame);

  while (n_left_from > 0)
    {
      u32 n_left_to_next;

      vlib_get_next_frame (vm, node, next_index, to_next, n_left_to_next);
      while (n_left_from >= 4 && n_left_to_next >= 2)
	{
	  vlib_buffer_t *b0, *b1;
	  u32 sw_if_index0, sw_if_index1;
	  u16 ether_type0, ether_type1;
	  u32 next0 = ~0, next1 = ~0;
	  u8 l2_len0, l2_len1;
	  u32 bi0, bi1;
	  u8 *h0, *h1;

	  bi0 = to_next[0] = from[0];
	  bi1 = to_next[1] = from[1];

	  from += 2;
	  n_left_from -= 2;
	  to_next += 2;
	  n_left_to_next -= 2;

	  b0 = vlib_get_buffer (vm, bi0);
	  b1 = vlib_get_buffer (vm, bi1);
	  l2_len0 = vnet_buffer (b0)->l2.l2_len;
	  l2_len1 = vnet_buffer (b1)->l2.l2_len;

	  h0 = vlib_buffer_get_current (b0);
	  h1 = vlib_buffer_get_current (b1);

	  ether_type0 = clib_net_to_host_u16 (*(u16 *) (h0 + l2_len0 - 2));
	  ether_type1 = clib_net_to_host_u16 (*(u16 *) (h1 + l2_len1 - 2));
	  sw_if_index0 = vnet_buffer (b0)->sw_if_index[VLIB_RX];
	  sw_if_index1 = vnet_buffer (b1)->sw_if_index[VLIB_RX];

	  /*
	   * only extract unicast
	   */
	  if (PREDICT_TRUE (!(h0[0] & 0x1)))
	    {
	      switch (ether_type0)
		{
		case ETHERNET_TYPE_IP4:
		  ASSERT (em->l2_emulations[sw_if_index0].enabled);
		  ++ip4_hits;
		  next0 = L2_EMULATION_NEXT_IP4;
		  vlib_buffer_advance (b0, l2_len0);
		  break;
		case ETHERNET_TYPE_IP6:
		  ASSERT (em->l2_emulations[sw_if_index0].enabled);
		  ++ip6_hits;
		  next0 = L2_EMULATION_NEXT_IP6;
		  vlib_buffer_advance (b0, l2_len0);
		default:
		  break;
		}
	    }
	  if (PREDICT_TRUE (!(h1[0] & 0x1)))
	    {
	      switch (ether_type1)
		{
		case ETHERNET_TYPE_IP4:
		  ASSERT (em->l2_emulations[sw_if_index1].enabled);
		  ++ip4_hits;
		  next1 = L2_EMULATION_NEXT_IP4;
		  vlib_buffer_advance (b1, l2_len1);
		  break;
		case ETHERNET_TYPE_IP6:
		  ASSERT (em->l2_emulations[sw_if_index1].enabled);
		  ++ip6_hits;
		  next1 = L2_EMULATION_NEXT_IP6;
		  vlib_buffer_advance (b1, l2_len1);
		default:
		  break;
		}
	    }
	  if (PREDICT_FALSE ((node->flags & VLIB_NODE_FLAG_TRACE)
			     && (b0->flags & VLIB_BUFFER_IS_TRACED)))
	    {
	      l2_emulation_trace_t *t =
		vlib_add_trace (vm, node, b0, sizeof (*t));
	      t->extracted = (next0 != ~0);
	    }
	  if (PREDICT_FALSE ((node->flags & VLIB_NODE_FLAG_TRACE)
			     && (b1->flags & VLIB_BUFFER_IS_TRACED)))
	    {
	      l2_emulation_trace_t *t =
		vlib_add_trace (vm, node, b1, sizeof (*t));
	      t->extracted = (next1 != ~0);
	    }

	  /* Determine the next node and remove ourself from bitmap */
	  if (PREDICT_TRUE (next0 == ~0))
	    next0 = vnet_l2_feature_next (b0, em->l2_input_feat_next,
					  L2INPUT_FEAT_L2_EMULATION);

	  /* Determine the next node and remove ourself from bitmap */
	  if (PREDICT_TRUE (next1 == ~0))
	    next1 = vnet_l2_feature_next (b1, em->l2_input_feat_next,
					  L2INPUT_FEAT_L2_EMULATION);

	  vlib_validate_buffer_enqueue_x2 (vm, node, next_index,
					   to_next, n_left_to_next,
					   bi0, bi1, next0, next1);
	}
      while (n_left_from > 0 && n_left_to_next > 0)
	{
	  vlib_buffer_t *b0;
	  u32 sw_if_index0;
	  u16 ether_type0;
	  u32 next0 = ~0;
	  u8 l2_len0;
	  u32 bi0;
	  u8 *h0;

	  bi0 = from[0];
	  to_next[0] = bi0;
	  from += 1;
	  to_next += 1;
	  n_left_from -= 1;
	  n_left_to_next -= 1;

	  b0 = vlib_get_buffer (vm, bi0);
	  l2_len0 = vnet_buffer (b0)->l2.l2_len;

	  h0 = vlib_buffer_get_current (b0);
	  ether_type0 = clib_net_to_host_u16 (*(u16 *) (h0 + l2_len0 - 2));
	  sw_if_index0 = vnet_buffer (b0)->sw_if_index[VLIB_RX];

	  /*
	   * only extract unicast
	   */
	  if (PREDICT_TRUE (!(h0[0] & 0x1)))
	    {
	      switch (ether_type0)
		{
		case ETHERNET_TYPE_IP4:
		  ASSERT (em->l2_emulations[sw_if_index0].enabled);
		  ++ip4_hits;
		  next0 = L2_EMULATION_NEXT_IP4;
		  vlib_buffer_advance (b0, l2_len0);
		  break;
		case ETHERNET_TYPE_IP6:
		  ASSERT (em->l2_emulations[sw_if_index0].enabled);
		  ++ip6_hits;
		  next0 = L2_EMULATION_NEXT_IP6;
		  vlib_buffer_advance (b0, l2_len0);
		default:
		  break;
		}
	    }

	  if (PREDICT_FALSE ((node->flags & VLIB_NODE_FLAG_TRACE)
			     && (b0->flags & VLIB_BUFFER_IS_TRACED)))
	    {
	      l2_emulation_trace_t *t =
		vlib_add_trace (vm, node, b0, sizeof (*t));
	      t->extracted = (next0 != ~0);
	    }

	  /* Determine the next node and remove ourself from bitmap */
	  if (PREDICT_TRUE (next0 == ~0))
	    next0 = vnet_l2_feature_next (b0, em->l2_input_feat_next,
					  L2INPUT_FEAT_L2_EMULATION);

	  /* verify speculative enqueue, maybe switch current next frame */
	  vlib_validate_buffer_enqueue_x1 (vm, node, next_index,
					   to_next, n_left_to_next,
					   bi0, next0);
	}

      vlib_put_next_frame (vm, node, next_index, n_left_to_next);
    }

  vlib_node_increment_counter (vm, node->node_index,
			       L2_EMULATION_ERROR_IP4, ip4_hits);
  vlib_node_increment_counter (vm, node->node_index,
			       L2_EMULATION_ERROR_IP6, ip6_hits);

  return frame->n_vectors;
}

/* *INDENT-OFF* */
VLIB_REGISTER_NODE (l2_emulation_node) = {
  .name = "l2-emulation",
  .vector_size = sizeof (u32),
  .format_trace = format_l2_emulation_trace,
  .type = VLIB_NODE_TYPE_INTERNAL,

  .n_errors = ARRAY_LEN(l2_emulation_error_strings),
  .error_strings = l2_emulation_error_strings,

  .n_next_nodes = L2_EMULATION_N_NEXT,

  /* edit / add dispositions here */
  .next_nodes = {
    [L2_EMULATION_NEXT_IP4] = "ip4-input",
    [L2_EMULATION_NEXT_IP6] = "ip6-input",
  },
};
/* *INDENT-ON* */

/*
 * fd.io coding-style-patch-verification: ON
 *
 * Local Variables:
 * eval: (c-set-style "gnu")
 * End:
 */
ef='#n1535'>1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674
/*
 * Copyright (c) 2016 Cisco and/or its affiliates.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <vlib/vlib.h>
#include <vnet/ip/format.h>
#include <vnet/ip/lookup.h>
#include <vnet/adj/adj.h>
#include <vnet/dpo/load_balance.h>
#include <vnet/dpo/drop_dpo.h>

#include <vnet/fib/fib_entry.h>
#include <vnet/fib/fib_walk.h>
#include <vnet/fib/fib_entry_src.h>
#include <vnet/fib/fib_entry_cover.h>
#include <vnet/fib/fib_table.h>
#include <vnet/fib/fib_internal.h>
#include <vnet/fib/fib_attached_export.h>
#include <vnet/fib/fib_path_ext.h>

/*
 * Array of strings/names for the FIB sources
 */
static const char *fib_source_names[] = FIB_SOURCES;
static const char *fib_attribute_names[] = FIB_ENTRY_ATTRIBUTES;
static const char *fib_src_attribute_names[] = FIB_ENTRY_SRC_ATTRIBUTES;

/*
 * Pool for all fib_entries
 */
static fib_entry_t *fib_entry_pool;

fib_entry_t *
fib_entry_get (fib_node_index_t index)
{
    return (pool_elt_at_index(fib_entry_pool, index));
}

static fib_node_t *
fib_entry_get_node (fib_node_index_t index)
{
    return ((fib_node_t*)fib_entry_get(index));
}

fib_node_index_t
fib_entry_get_index (const fib_entry_t * fib_entry)
{
    return (fib_entry - fib_entry_pool);
}

fib_protocol_t
fib_entry_get_proto (const fib_entry_t * fib_entry)
{
    return (fib_entry->fe_prefix.fp_proto);
}

dpo_proto_t
fib_entry_get_dpo_proto (const fib_entry_t * fib_entry)
{
    return (fib_proto_to_dpo(fib_entry->fe_prefix.fp_proto));
}

fib_forward_chain_type_t
fib_entry_get_default_chain_type (const fib_entry_t *fib_entry)
{
    switch (fib_entry->fe_prefix.fp_proto)
    {
    case FIB_PROTOCOL_IP4:
	return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
    case FIB_PROTOCOL_IP6:
	return (FIB_FORW_CHAIN_TYPE_UNICAST_IP6);
    case FIB_PROTOCOL_MPLS:
	if (MPLS_EOS == fib_entry->fe_prefix.fp_eos)
	    return (FIB_FORW_CHAIN_TYPE_MPLS_EOS);
	else
	    return (FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS);
    }

    return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
}

u8 *
format_fib_source (u8 * s, va_list * args)
{
    fib_source_t source = va_arg (*args, int);

    s = format (s, "src:%s", fib_source_names[source]);

    return (s);
}

u8 *
format_fib_entry (u8 * s, va_list * args)
{
    fib_entry_src_attribute_t sattr;
    fib_forward_chain_type_t fct;
    fib_entry_attribute_t attr;
    fib_entry_t *fib_entry;
    fib_entry_src_t *src;
    fib_node_index_t fei;
    fib_source_t source;
    int level;

    fei = va_arg (*args, fib_node_index_t);
    level = va_arg (*args, int);
    fib_entry = fib_entry_get(fei);

    s = format (s, "%U", format_fib_prefix, &fib_entry->fe_prefix);

    if (level >= FIB_ENTRY_FORMAT_DETAIL)
    {
	s = format (s, " fib:%d", fib_entry->fe_fib_index);
	s = format (s, " index:%d", fib_entry_get_index(fib_entry));
	s = format (s, " locks:%d", fib_entry->fe_node.fn_locks);

	FOR_EACH_SRC_ADDED(fib_entry, src, source,
        ({
	    s = format (s, "\n  %U", format_fib_source, source);
	    s = format (s, " refs:%d", src->fes_ref_count);
	    if (FIB_ENTRY_FLAG_NONE != src->fes_entry_flags) {
		s = format(s, " entry-flags:");
		FOR_EACH_FIB_ATTRIBUTE(attr) {
		    if ((1<<attr) & src->fes_entry_flags) {
			s = format (s, "%s,", fib_attribute_names[attr]);
		    }
		}
	    }
	    if (FIB_ENTRY_SRC_FLAG_NONE != src->fes_flags) {
		s = format(s, " src-flags:");
		FOR_EACH_FIB_SRC_ATTRIBUTE(sattr) {
		    if ((1<<sattr) & src->fes_flags) {
			s = format (s, "%s,", fib_src_attribute_names[sattr]);
		    }
		}
	    }
            s = fib_entry_src_format(fib_entry, source, s);
	    s = format (s, "\n");
	    if (FIB_NODE_INDEX_INVALID != src->fes_pl)
	    {
		s = fib_path_list_format(src->fes_pl, s);
	    }
            s = format(s, "%U", format_fib_path_ext_list, &src->fes_path_exts);
	}));
    
	s = format (s, "\n forwarding: ");
    }
    else
    {
	s = format (s, "\n");
    }

    fct = fib_entry_get_default_chain_type(fib_entry);

    if (!dpo_id_is_valid(&fib_entry->fe_lb))
    {
	s = format (s, "  UNRESOLVED\n");
	return (s);
    }
    else
    {
        s = format(s, "  %U-chain\n  %U",
                   format_fib_forw_chain_type, fct,
                   format_dpo_id,
                   &fib_entry->fe_lb,
                   2);
        s = format(s, "\n");

        if (level >= FIB_ENTRY_FORMAT_DETAIL2)
        {
            fib_entry_delegate_type_t fdt;
            fib_entry_delegate_t *fed;

            s = format (s, " Delegates:\n");
            FOR_EACH_DELEGATE(fib_entry, fdt, fed,
            {
                s = format(s, "  %U\n", format_fib_entry_deletegate, fed);
            });
        }
    }

    if (level >= FIB_ENTRY_FORMAT_DETAIL2)
    {
        s = format(s, " Children:");
        s = fib_node_children_format(fib_entry->fe_node.fn_children, s);
    }

    return (s);
}

static fib_entry_t*
fib_entry_from_fib_node (fib_node_t *node)
{
    ASSERT(FIB_NODE_TYPE_ENTRY == node->fn_type);
    return ((fib_entry_t*)node);
}

static void
fib_entry_last_lock_gone (fib_node_t *node)
{
    fib_entry_delegate_type_t fdt;
    fib_entry_delegate_t *fed;
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_from_fib_node(node);

    ASSERT(!dpo_id_is_valid(&fib_entry->fe_lb));

    FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
    {
	dpo_reset(&fed->fd_dpo);
        fib_entry_delegate_remove(fib_entry, fdt);
    });

    FIB_ENTRY_DBG(fib_entry, "last-lock");

    fib_node_deinit(&fib_entry->fe_node);

    ASSERT(0 == vec_len(fib_entry->fe_delegates));
    vec_free(fib_entry->fe_delegates);
    vec_free(fib_entry->fe_srcs);
    pool_put(fib_entry_pool, fib_entry);
}

static fib_entry_src_t*
fib_entry_get_best_src_i (const fib_entry_t *fib_entry)
{
    fib_entry_src_t *bsrc;

    /*
     * the enum of sources is deliberately arranged in priority order
     */
    if (0 == vec_len(fib_entry->fe_srcs))
    {
	bsrc = NULL;
    }
    else
    {
	bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
    }

    return (bsrc);
}

static fib_source_t
fib_entry_src_get_source (const fib_entry_src_t *esrc)
{
    if (NULL != esrc)
    {
	return (esrc->fes_src);
    }
    return (FIB_SOURCE_MAX);
}

static fib_entry_flag_t
fib_entry_src_get_flags (const fib_entry_src_t *esrc)
{
    if (NULL != esrc)
    {
	return (esrc->fes_entry_flags);
    }
    return (FIB_ENTRY_FLAG_NONE);
}

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

/*
 * fib_entry_back_walk_notify
 *
 * A back walk has reach this entry.
 */
static fib_node_back_walk_rc_t
fib_entry_back_walk_notify (fib_node_t *node,
			    fib_node_back_walk_ctx_t *ctx)
{
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_from_fib_node(node);

    if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason        ||
        FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason      ||
        FIB_NODE_BW_REASON_FLAG_ADJ_DOWN & ctx->fnbw_reason        ||
	FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason    ||
	FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason  ||
	FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
    {
	fib_entry_src_action_reactivate(fib_entry,
                                        fib_entry_get_best_source(
                                            fib_entry_get_index(fib_entry)));
    }

    /*
     * all other walk types can be reclassifed to a re-evaluate to
     * all recursive dependents.
     * By reclassifying we ensure that should any of these walk types meet
     * they can be merged.
     */
    ctx->fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE;

    /*
     * ... and nothing is forced sync from now on.
     */
    ctx->fnbw_flags &= ~FIB_NODE_BW_FLAG_FORCE_SYNC;

    /*
     * propagate the backwalk further if we haven't already reached the
     * maximum depth.
     */
    fib_walk_sync(FIB_NODE_TYPE_ENTRY,
		  fib_entry_get_index(fib_entry),
		  ctx);

    return (FIB_NODE_BACK_WALK_CONTINUE);
}

static void
fib_entry_show_memory (void)
{
    u32 n_srcs = 0, n_exts = 0;
    fib_entry_src_t *esrc;
    fib_entry_t *entry;

    fib_show_memory_usage("Entry",
			  pool_elts(fib_entry_pool),
			  pool_len(fib_entry_pool),
			  sizeof(fib_entry_t));

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

    fib_show_memory_usage("Entry Source",
			  n_srcs, n_srcs, sizeof(fib_entry_src_t));
    fib_show_memory_usage("Entry Path-Extensions",
			  n_exts, n_exts,
			  sizeof(fib_path_ext_t));
}

/*
 * The FIB path-list's graph node virtual function table
 */
static const fib_node_vft_t fib_entry_vft = {
    .fnv_get = fib_entry_get_node,
    .fnv_last_lock = fib_entry_last_lock_gone,
    .fnv_back_walk = fib_entry_back_walk_notify,
    .fnv_mem_show = fib_entry_show_memory,
};

/**
 * @brief Contribute the set of Adjacencies that this entry forwards with
 * to build the uRPF list of its children
 */
void
fib_entry_contribute_urpf (fib_node_index_t entry_index,
			   index_t urpf)
{
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_get(entry_index);

    return (fib_path_list_contribute_urpf(fib_entry->fe_parent, urpf));
}

/*
 * If the client is request a chain for multicast forwarding then swap
 * the chain type to one that can provide such transport.
 */
static fib_forward_chain_type_t
fib_entry_chain_type_mcast_to_ucast (fib_forward_chain_type_t fct)
{
    switch (fct)
    {
    case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
    case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
        /*
         * we can only transport IP multicast packets if there is an
         * LSP.
         */
        fct = FIB_FORW_CHAIN_TYPE_MPLS_EOS;
        break;
    case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
    case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
    case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
    case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
    case FIB_FORW_CHAIN_TYPE_ETHERNET:
    case FIB_FORW_CHAIN_TYPE_NSH:
    case FIB_FORW_CHAIN_TYPE_BIER:
        break;
    }

    return (fct);
}

/*
 * fib_entry_contribute_forwarding
 *
 * Get an lock the forwarding information (DPO) contributed by the FIB entry.
 */
void
fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
				 fib_forward_chain_type_t fct,
				 dpo_id_t *dpo)
{
    fib_entry_delegate_t *fed;
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_get(fib_entry_index);

    /*
     * mfib children ask for mcast chains. fix these to the appropriate ucast types.
     */
    fct = fib_entry_chain_type_mcast_to_ucast(fct);

    if (fct == fib_entry_get_default_chain_type(fib_entry))
    {
        dpo_copy(dpo, &fib_entry->fe_lb);
    }
    else
    {
        fed = fib_entry_delegate_get(fib_entry,
                                     fib_entry_chain_type_to_delegate_type(fct));

        if (NULL == fed)
        {
            fed = fib_entry_delegate_find_or_add(
                      fib_entry,
                      fib_entry_chain_type_to_delegate_type(fct));
            /*
             * on-demand create eos/non-eos.
             * There is no on-demand delete because:
             *   - memory versus complexity & reliability:
             *      leaving unrequired [n]eos LB arounds wastes memory, cleaning
             *      then up on the right trigger is more code. i favour the latter.
             */
            fib_entry_src_mk_lb(fib_entry,
                                fib_entry_get_best_src_i(fib_entry),
                                fct,
                                &fed->fd_dpo);
        }

        dpo_copy(dpo, &fed->fd_dpo);
    }
    /*
     * use the drop DPO is nothing else is present
     */
    if (!dpo_id_is_valid(dpo))
    {
        dpo_copy(dpo, drop_dpo_get(fib_forw_chain_type_to_dpo_proto(fct)));
    }

    /*
     * don't allow the special index indicating replicate.vs.load-balance
     * to escape to the clients
     */
    dpo->dpoi_index &= ~MPLS_IS_REPLICATE;
}

const dpo_id_t *
fib_entry_contribute_ip_forwarding (fib_node_index_t fib_entry_index)
{
    fib_forward_chain_type_t fct;
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_get(fib_entry_index);
    fct = fib_entry_get_default_chain_type(fib_entry);

    ASSERT((fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP4 ||
            fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP6));

    if (dpo_id_is_valid(&fib_entry->fe_lb))
    {
        return (&fib_entry->fe_lb);
    }

    return (drop_dpo_get(fib_forw_chain_type_to_dpo_proto(fct)));
}

adj_index_t
fib_entry_get_adj (fib_node_index_t fib_entry_index)
{
    const dpo_id_t *dpo;

    dpo = fib_entry_contribute_ip_forwarding(fib_entry_index);

    if (dpo_id_is_valid(dpo))
    {
        dpo = load_balance_get_bucket(dpo->dpoi_index, 0);

        if (dpo_is_adj(dpo))
        {
            return (dpo->dpoi_index);
        }
    }
    return (ADJ_INDEX_INVALID);
}

fib_node_index_t
fib_entry_get_path_list (fib_node_index_t fib_entry_index)
{
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_get(fib_entry_index);

    return (fib_entry->fe_parent);
}

u32
fib_entry_child_add (fib_node_index_t fib_entry_index,
		     fib_node_type_t child_type,
		     fib_node_index_t child_index)
{
    return (fib_node_child_add(FIB_NODE_TYPE_ENTRY,
                               fib_entry_index,
                               child_type,
                               child_index));
};

void
fib_entry_child_remove (fib_node_index_t fib_entry_index,
			u32 sibling_index)
{
    fib_node_child_remove(FIB_NODE_TYPE_ENTRY,
                          fib_entry_index,
                          sibling_index);

    if (0 == fib_node_get_n_children(FIB_NODE_TYPE_ENTRY,
                                     fib_entry_index))
    {
        /*
         * if there are no children left then there is no reason to keep
         * the non-default forwarding chains. those chains are built only
         * because the children want them.
         */
        fib_entry_delegate_type_t fdt;
        fib_entry_delegate_t *fed;
        fib_entry_t *fib_entry;

        fib_entry = fib_entry_get(fib_entry_index);

        FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
        {
            dpo_reset(&fed->fd_dpo);
            fib_entry_delegate_remove(fib_entry, fdt);
        });
    }
}

static fib_entry_t *
fib_entry_alloc (u32 fib_index,
		 const fib_prefix_t *prefix,
		 fib_node_index_t *fib_entry_index)
{
    fib_entry_t *fib_entry;
    fib_prefix_t *fep;

    pool_get(fib_entry_pool, fib_entry);
    memset(fib_entry, 0, sizeof(*fib_entry));

    fib_node_init(&fib_entry->fe_node,
		  FIB_NODE_TYPE_ENTRY);

    fib_entry->fe_fib_index = fib_index;

    /*
     * the one time we need to update the const prefix is when
     * the entry is first created
     */
    fep = (fib_prefix_t*)&(fib_entry->fe_prefix);
    *fep = *prefix;

    if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
    {
	fep->fp_len = 21;
	if (MPLS_NON_EOS == fep->fp_eos)
	{
	    fep->fp_payload_proto = DPO_PROTO_MPLS;
	}
    	ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
    }

    dpo_reset(&fib_entry->fe_lb);

    *fib_entry_index = fib_entry_get_index(fib_entry);

    FIB_ENTRY_DBG(fib_entry, "alloc");

    return (fib_entry);
}

static fib_entry_t*
fib_entry_post_flag_update_actions (fib_entry_t *fib_entry,
				    fib_entry_flag_t old_flags)
{
    fib_node_index_t fei;

    /*
     * save the index so we can recover from pool reallocs
     */
    fei = fib_entry_get_index(fib_entry);

    /*
     * handle changes to attached export for import entries
     */
    int is_import  = (FIB_ENTRY_FLAG_IMPORT & fib_entry_get_flags_i(fib_entry));
    int was_import = (FIB_ENTRY_FLAG_IMPORT & old_flags);

    if (!was_import && is_import)
    {
	/*
	 * transition from not exported to exported
	 */

	/*
	 * there is an assumption here that the entry resolves via only
	 * one interface and that it is the cross VRF interface.
	 */
	u32 sw_if_index = fib_path_list_get_resolving_interface(fib_entry->fe_parent);

	fib_attached_export_import(fib_entry,
				   fib_table_get_index_for_sw_if_index(
				       fib_entry_get_proto(fib_entry),
                                       sw_if_index));
    }
    else if (was_import && !is_import)
    {
	/*
	 * transition from exported to not exported
	 */
	fib_attached_export_purge(fib_entry);
    }
    /*
     * else
     *   no change. nothing to do.
     */

    /*
     * reload the entry address post possible pool realloc
     */
    fib_entry = fib_entry_get(fei);

    /*
     * handle changes to attached export for export entries
     */
    int is_attached  = (FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags_i(fib_entry));
    int was_attached = (FIB_ENTRY_FLAG_ATTACHED & old_flags);

    if (!was_attached && is_attached)
    {
	/*
	 * transition to attached. time to export
	 */
	// FIXME
    }
    // else FIXME

    return (fib_entry);
}

static void
fib_entry_post_install_actions (fib_entry_t *fib_entry,
				fib_source_t source,
				fib_entry_flag_t old_flags)
{
    fib_entry = fib_entry_post_flag_update_actions(fib_entry,
                                                   old_flags);
    fib_entry_src_action_installed(fib_entry, source);
}

fib_node_index_t
fib_entry_create (u32 fib_index,
		  const fib_prefix_t *prefix,
		  fib_source_t source,
		  fib_entry_flag_t flags,
		  const fib_route_path_t *paths)
{
    fib_node_index_t fib_entry_index;
    fib_entry_t *fib_entry;

    ASSERT(0 < vec_len(paths));

    fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);

    /*
     * since this is a new entry create, we don't need to check for winning
     * sources - there is only one.
     */
    fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
                                         drop_dpo_get(
                                             fib_proto_to_dpo(
                                                 fib_entry_get_proto(fib_entry))));
    fib_entry_src_action_path_swap(fib_entry,
				   source,
				   flags,
				   paths);
    /*
     * handle possible realloc's by refetching the pointer
     */
    fib_entry = fib_entry_get(fib_entry_index);
    fib_entry_src_action_activate(fib_entry, source);

    fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);

    return (fib_entry_index);
}

fib_node_index_t
fib_entry_create_special (u32 fib_index,
			  const fib_prefix_t *prefix,
			  fib_source_t source,
			  fib_entry_flag_t flags,
			  const dpo_id_t *dpo)
{
    fib_node_index_t fib_entry_index;
    fib_entry_t *fib_entry;

    /*
     * create and initiliase the new enty
     */
    fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);

    /*
     * create the path-list
     */
    fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
    fib_entry_src_action_activate(fib_entry, source);

    fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);

    return (fib_entry_index);
}

static void
fib_entry_post_update_actions (fib_entry_t *fib_entry,
			       fib_source_t source,
			       fib_entry_flag_t old_flags)
{
    /*
     * backwalk to children to inform then of the change to forwarding.
     */
    fib_node_back_walk_ctx_t bw_ctx = {
	.fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
    };

    fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);

    /*
     * then inform any covered prefixes
     */
    fib_entry_cover_update_notify(fib_entry);

    fib_entry_post_install_actions(fib_entry, source, old_flags);
}

void
fib_entry_recalculate_forwarding (fib_node_index_t fib_entry_index)
{
    fib_source_t best_source;
    fib_entry_t *fib_entry;
    fib_entry_src_t *bsrc;

    fib_entry = fib_entry_get(fib_entry_index);

    bsrc = fib_entry_get_best_src_i(fib_entry);
    best_source = fib_entry_src_get_source(bsrc);

    fib_entry_src_action_reactivate(fib_entry, best_source);
}

static void
fib_entry_source_change_w_flags (fib_entry_t *fib_entry,
                                 fib_source_t old_source,
                                 fib_entry_flag_t old_flags,
                                 fib_source_t new_source)
{
    if (new_source < old_source)
    {
	/*
	 * we have a new winning source.
	 */
	fib_entry_src_action_deactivate(fib_entry, old_source);
	fib_entry_src_action_activate(fib_entry, new_source);
    }
    else if (new_source > old_source)
    {
        /*
         * the new source loses. Re-activate the winning sources
         * in case it is an interposer and hence relied on the losing
         * source's path-list.
         */
        fib_entry_src_action_reactivate(fib_entry, old_source);
        return;
    }
    else
    {
	/*
	 * the new source is one this entry already has.
	 * But the path-list was updated, which will contribute new forwarding,
	 * so install it.
	 */
        fib_entry_src_action_reactivate(fib_entry, new_source);
    }

    fib_entry_post_update_actions(fib_entry, new_source, old_flags);
}

void
fib_entry_source_change (fib_entry_t *fib_entry,
                         fib_source_t old_source,
			 fib_source_t new_source)
{
    fib_entry_flag_t old_flags;

    old_flags = fib_entry_get_flags_for_source(
        fib_entry_get_index(fib_entry), old_source);

    return (fib_entry_source_change_w_flags(fib_entry, old_source,
                                            old_flags, new_source));
}

void
fib_entry_special_add (fib_node_index_t fib_entry_index,
		       fib_source_t source,
		       fib_entry_flag_t flags,
		       const dpo_id_t *dpo)
{
    fib_source_t best_source;
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_get(fib_entry_index);
    best_source = fib_entry_get_best_source(fib_entry_index);

    fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
    fib_entry_source_change(fib_entry, best_source, source);
}

void
fib_entry_special_update (fib_node_index_t fib_entry_index,
			  fib_source_t source,
			  fib_entry_flag_t flags,
			  const dpo_id_t *dpo)
{
    fib_source_t best_source;
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_get(fib_entry_index);
    best_source = fib_entry_get_best_source(fib_entry_index);

    fib_entry = fib_entry_src_action_update(fib_entry, source, flags, dpo);
    fib_entry_source_change(fib_entry, best_source, source);
}


void
fib_entry_path_add (fib_node_index_t fib_entry_index,
		    fib_source_t source,
		    fib_entry_flag_t flags,
		    const fib_route_path_t *rpath)
{
    fib_source_t best_source;
    fib_entry_t *fib_entry;
    fib_entry_src_t *bsrc;

    ASSERT(1 == vec_len(rpath));

    fib_entry = fib_entry_get(fib_entry_index);
    ASSERT(NULL != fib_entry);

    bsrc = fib_entry_get_best_src_i(fib_entry);
    best_source = fib_entry_src_get_source(bsrc);
    
    fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpath);

    fib_entry_source_change(fib_entry, best_source, source);
}

static fib_entry_src_flag_t
fib_entry_src_burn_only_inherited (fib_entry_t *fib_entry)
{
    fib_entry_src_t *src;
    fib_source_t source;
    int has_only_inherited_sources = 1;

    FOR_EACH_SRC_ADDED(fib_entry, src, source,
    ({
        if (!(src->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
        {
            has_only_inherited_sources = 0;
            break;
        }
    }));
    if (has_only_inherited_sources)
    {
        FOR_EACH_SRC_ADDED(fib_entry, src, source,
        ({
            fib_entry_src_action_remove(fib_entry, source);
        }));
        return (FIB_ENTRY_SRC_FLAG_NONE);
    }
    else
    {
        return (FIB_ENTRY_SRC_FLAG_ADDED);
    }
}

static fib_entry_src_flag_t
fib_entry_source_removed (fib_entry_t *fib_entry,
                          fib_entry_flag_t old_flags)
{
    const fib_entry_src_t *bsrc;
    fib_source_t best_source;

    /*
     * if all that is left are inherited sources, then burn them
     */
    fib_entry_src_burn_only_inherited(fib_entry);

    bsrc = fib_entry_get_best_src_i(fib_entry);
    best_source = fib_entry_src_get_source(bsrc);

    if (FIB_SOURCE_MAX == best_source)
    {
        /*
         * no more sources left. this entry is toast.
         */
        fib_entry = fib_entry_post_flag_update_actions(fib_entry, old_flags);
        fib_entry_src_action_uninstall(fib_entry);

        return (FIB_ENTRY_SRC_FLAG_NONE);
    }
    else
    {
        fib_entry_src_action_activate(fib_entry, best_source);
    }

    fib_entry_post_update_actions(fib_entry, best_source, old_flags);

    /*
     * still have sources
     */
    return (FIB_ENTRY_SRC_FLAG_ADDED);
}

/*
 * fib_entry_path_remove
 *
 * remove a path from the entry.
 * return the fib_entry's index if it is still present, INVALID otherwise.
 */
fib_entry_src_flag_t
fib_entry_path_remove (fib_node_index_t fib_entry_index,
		       fib_source_t source,
		       const fib_route_path_t *rpath)
{
    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));

    fib_entry = fib_entry_get(fib_entry_index);
    ASSERT(NULL != fib_entry);

    bsrc = fib_entry_get_best_src_i(fib_entry);
    best_source = fib_entry_src_get_source(bsrc);
    bflags = fib_entry_src_get_flags(bsrc);

    sflag = fib_entry_src_action_path_remove(fib_entry, source, rpath);

    /*
     * if the path list for the source passed is invalid,
     * then we need to create a new one. else we are updating
     * an existing.
     */
    if (source < best_source)
    {
	/*
	 * Que! removing a path from a source that is better than the
	 * one this entry is using.
	 */
	ASSERT(0);
    }
    else if (source > best_source )
    {
	/*
	 * the source is not the best. no need to update forwarding
	 */
	if (FIB_ENTRY_SRC_FLAG_ADDED & sflag)
        {
            /*
             * the source being removed still has paths
             */
            return (FIB_ENTRY_SRC_FLAG_ADDED);
        }
        else
        {
            /*
             * that was the last path from this source, check if those
             * that remain are non-inherited
             */
            return (fib_entry_src_burn_only_inherited(fib_entry));
       }
    }
    else
    {
	/*
	 * removing a path from the path-list we were using.
	 */
	if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
	{
	    /*
	     * the last path from the source was removed.
	     * fallback to lower source
	     */
            return (fib_entry_source_removed(fib_entry, bflags));
	}
	else
	{
	    /*
	     * re-install the new forwarding information
	     */
	    fib_entry_src_action_reactivate(fib_entry, source);
	}
    }

    fib_entry_post_update_actions(fib_entry, source, bflags);

    /*
     * still have sources
     */
    return (FIB_ENTRY_SRC_FLAG_ADDED);
}

/*
 * fib_entry_special_remove
 *
 * remove a special source from the entry.
 * return the fib_entry's index if it is still present, INVALID otherwise.
 */
fib_entry_src_flag_t
fib_entry_special_remove (fib_node_index_t fib_entry_index,
			  fib_source_t source)
{
    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);

    bsrc = fib_entry_get_best_src_i(fib_entry);
    best_source = fib_entry_src_get_source(bsrc);
    bflags = fib_entry_src_get_flags(bsrc);

    sflag = fib_entry_src_action_remove_or_update_inherit(fib_entry, source);

    /*
     * if the path list for the source passed is invalid,
     * then we need to create a new one. else we are updating
     * an existing.
     */
    if (source < best_source )
    {
	/*
	 * Que! removing a path from a source that is better than the
	 * one this entry is using. This can only mean it is a source
         * this prefix does not have.
	 */
        return (FIB_ENTRY_SRC_FLAG_ADDED);
    }
    else if (source > best_source ) {
	/*
	 * the source is not the best. no need to update forwarding
	 */
	if (FIB_ENTRY_SRC_FLAG_ADDED & sflag)
        {
            /*
             * the source being removed still has paths
             */
            return (FIB_ENTRY_SRC_FLAG_ADDED);
        }
        else
        {
            /*
             * that was the last path from this source, check if those
             * that remain are non-inherited
             */
            if (FIB_ENTRY_SRC_FLAG_NONE == fib_entry_src_burn_only_inherited(fib_entry))
            {
                /*
                 * no more sources left. this entry is toast.
                 */
                fib_entry = fib_entry_post_flag_update_actions(fib_entry, bflags);
                fib_entry_src_action_uninstall(fib_entry);
                return (FIB_ENTRY_SRC_FLAG_NONE);
            }

            /*
             * reactivate the best source so the interposer gets restacked
             */
            fib_entry_src_action_reactivate(fib_entry, best_source);

            return (FIB_ENTRY_SRC_FLAG_ADDED);
        }
    }
    else
    {
	if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
	{
	    /*
	     * the source was removed. use the next best.
	     */
            return (fib_entry_source_removed(fib_entry, bflags));
	}
	else
	{
	    /*
	     * re-install the new forwarding information
	     */
	    fib_entry_src_action_reactivate(fib_entry, source);
	}
    }

    fib_entry_post_update_actions(fib_entry, source, bflags);

    /*
     * still have sources
     */
    return (FIB_ENTRY_SRC_FLAG_ADDED);
}

/**
 * fib_entry_inherit
 *
 * If the source on the cover is inherting then push this source
 * down to the covered.
 */
void
fib_entry_inherit (fib_node_index_t cover,
                   fib_node_index_t covered)
{
    fib_entry_src_inherit(fib_entry_get(cover),
                          fib_entry_get(covered));
}

/**
 * fib_entry_delete
 *
 * The source is withdrawing all the paths it provided
 */
fib_entry_src_flag_t
fib_entry_delete (fib_node_index_t fib_entry_index,
		  fib_source_t source)
{
    return (fib_entry_special_remove(fib_entry_index, source));
}

/**
 * fib_entry_update
 *
 * The source has provided a new set of paths that will replace the old.
 */
void
fib_entry_update (fib_node_index_t fib_entry_index,
		  fib_source_t source,
		  fib_entry_flag_t flags,
		  const fib_route_path_t *paths)
{
    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);

    bsrc = fib_entry_get_best_src_i(fib_entry);
    best_source = fib_entry_src_get_source(bsrc);
    bflags = fib_entry_get_flags_i(fib_entry);

    fib_entry = fib_entry_src_action_path_swap(fib_entry,
                                               source,
                                               flags,
                                               paths);

    fib_entry_source_change_w_flags(fib_entry, best_source, bflags, source);
}


/*
 * fib_entry_cover_changed
 *
 * this entry is tracking its cover and that cover has changed.
 */
void
fib_entry_cover_changed (fib_node_index_t fib_entry_index)
{
    fib_entry_src_cover_res_t res = {
	.install = !0,
	.bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
    };
    CLIB_UNUSED(fib_source_t source);
    fib_source_t best_source;
    fib_entry_flag_t bflags;
    fib_entry_t *fib_entry;
    fib_entry_src_t *esrc;
    u32 index;

    bflags = FIB_ENTRY_FLAG_NONE;
    best_source = FIB_SOURCE_FIRST;
    fib_entry = fib_entry_get(fib_entry_index);

    fib_attached_export_cover_change(fib_entry);

    /*
     * propagate the notificuation to each of the added sources
     */
    index = 0;
    FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
    ({
	if (0 == index)
	{
	    /*
	     * only the best source gets to set the back walk flags
	     */
	    res = fib_entry_src_action_cover_change(fib_entry, esrc);
            bflags = fib_entry_src_get_flags(esrc);
            best_source = fib_entry_src_get_source(esrc);
	}
	else
	{
	    fib_entry_src_action_cover_change(fib_entry, esrc);
	}
	index++;
    }));

    if (res.install)
    {
	fib_entry_src_action_reactivate(fib_entry,
					fib_entry_src_get_source(
					    fib_entry_get_best_src_i(fib_entry)));
        fib_entry_post_install_actions(fib_entry, best_source, bflags);
    }
    else
    {
	fib_entry_src_action_uninstall(fib_entry);
    }

    if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
    {
	/*
	 * time for walkies fido.
	 */
	fib_node_back_walk_ctx_t bw_ctx = {
	    .fnbw_reason = res.bw_reason,
        };

	fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
    }
}

/*
 * fib_entry_cover_updated
 *
 * this entry is tracking its cover and that cover has been updated
 * (i.e. its forwarding information has changed).
 */
void
fib_entry_cover_updated (fib_node_index_t fib_entry_index)
{
    fib_entry_src_cover_res_t res = {
	.install = !0,
	.bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
    };
    CLIB_UNUSED(fib_source_t source);
    fib_source_t best_source;
    fib_entry_flag_t bflags;
    fib_entry_t *fib_entry;
    fib_entry_src_t *esrc;
    u32 index;

    bflags = FIB_ENTRY_FLAG_NONE;
    best_source = FIB_SOURCE_FIRST;
    fib_entry = fib_entry_get(fib_entry_index);

    fib_attached_export_cover_update(fib_entry);

    /*
     * propagate the notificuation to each of the added sources
     */
    index = 0;
    FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
    ({
	if (0 == index)
	{
	    /*
	     * only the best source gets to set the back walk flags
	     */
	    res = fib_entry_src_action_cover_update(fib_entry, esrc);
            bflags = fib_entry_src_get_flags(esrc);
            best_source = fib_entry_src_get_source(esrc);
	}
	else
	{
	    fib_entry_src_action_cover_update(fib_entry, esrc);
	}
	index++;
    }));

    if (res.install)
    {
	fib_entry_src_action_reactivate(fib_entry,
					fib_entry_src_get_source(
					    fib_entry_get_best_src_i(fib_entry)));
        fib_entry_post_install_actions(fib_entry, best_source, bflags);
    }
    else
    {
	fib_entry_src_action_uninstall(fib_entry);
    }

    if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
    {
	/*
	 * time for walkies fido.
	 */
	fib_node_back_walk_ctx_t bw_ctx = {
	    .fnbw_reason = res.bw_reason,
        };

	fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
    }
}

int
fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
				 fib_node_index_t **entry_indicies)
{
    fib_entry_t *fib_entry;
    int was_looped, is_looped;

    fib_entry = fib_entry_get(entry_index);

    if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
    {
	fib_node_index_t *entries = *entry_indicies;

	vec_add1(entries, entry_index);
	was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
	is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
							&entries);

	*entry_indicies = entries;

	if (!!was_looped != !!is_looped)
	{
	    /*
	     * re-evaluate all the entry's forwarding
	     * NOTE: this is an inplace modify
	     */
            fib_entry_delegate_type_t fdt;
            fib_entry_delegate_t *fed;

            FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
            {
                fib_entry_src_mk_lb(fib_entry,
                                    fib_entry_get_best_src_i(fib_entry),
                                    fib_entry_delegate_type_to_chain_type(fdt),
                                    &fed->fd_dpo);
	    });
	}
    }
    else
    {
	/*
	 * the entry is currently not linked to a path-list. this happens
	 * when it is this entry that is re-linking path-lists and has thus
	 * broken the loop
	 */
	is_looped = 0;
    }

    return (is_looped);
}

u32
fib_entry_get_resolving_interface (fib_node_index_t entry_index)
{
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_get(entry_index);

    return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
}

fib_source_t
fib_entry_get_best_source (fib_node_index_t entry_index)
{
    fib_entry_t *fib_entry;
    fib_entry_src_t *bsrc;

    fib_entry = fib_entry_get(entry_index);

    bsrc = fib_entry_get_best_src_i(fib_entry);
    return (fib_entry_src_get_source(bsrc));
}

/**
 * Return !0 is the entry is reoslved, i.e. will return a valid forwarding
 * chain
 */
int
fib_entry_is_resolved (fib_node_index_t fib_entry_index)
{
    fib_entry_delegate_t *fed;
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_get(fib_entry_index);

    fed = fib_entry_delegate_get(fib_entry, FIB_ENTRY_DELEGATE_BFD);

    if (NULL == fed)
    {
        /*
         * no BFD tracking - consider it resolved.
         */
        return (!0);
    }
    else
    {
        /*
         * defer to the state of the BFD tracking
         */
        return (FIB_BFD_STATE_UP == fed->fd_bfd_state);
    }
}

void
fib_entry_set_flow_hash_config (fib_node_index_t fib_entry_index,
                                flow_hash_config_t hash_config)
{
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_get(fib_entry_index);

    /*
     * pass the hash-config on to the load-balance object where it is cached.
     * we can ignore LBs in the delegate chains, since they will not be of the
     * correct protocol type (i.e. they are not IP)
     * There's no way, nor need, to change the hash config for MPLS.
     */
    if (dpo_id_is_valid(&fib_entry->fe_lb))
    {
        load_balance_t *lb;

        ASSERT(DPO_LOAD_BALANCE == fib_entry->fe_lb.dpoi_type);

        lb = load_balance_get(fib_entry->fe_lb.dpoi_index);

        /*
         * atomic update for packets in flight
         */
        lb->lb_hash_config = hash_config;
    }
}

static int
fib_ip4_address_compare (const ip4_address_t * a1,
                         const ip4_address_t * a2)
{
    /*
     * IP addresses are unsiged ints. the return value here needs to be signed
     * a simple subtraction won't cut it.
     * If the addresses are the same, the sort order is undefiend, so phoey.
     */
    return ((clib_net_to_host_u32(a1->data_u32) >
	     clib_net_to_host_u32(a2->data_u32) ) ?
	    1 : -1);
}

static int
fib_ip6_address_compare (const ip6_address_t * a1,
                         const ip6_address_t * a2)
{
  int i;
  for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
  {
      int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
		 clib_net_to_host_u16 (a2->as_u16[i]));
      if (cmp != 0)
	  return cmp;
  }
  return 0;
}

static int
fib_entry_cmp (fib_node_index_t fib_entry_index1,
	       fib_node_index_t fib_entry_index2)
{
    fib_entry_t *fib_entry1, *fib_entry2;
    int cmp = 0;

    fib_entry1 = fib_entry_get(fib_entry_index1);
    fib_entry2 = fib_entry_get(fib_entry_index2);

    switch (fib_entry1->fe_prefix.fp_proto)
    {
    case FIB_PROTOCOL_IP4:
        cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
                                      &fib_entry2->fe_prefix.fp_addr.ip4);
        break;
    case FIB_PROTOCOL_IP6:
        cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
                                      &fib_entry2->fe_prefix.fp_addr.ip6);
        break;
    case FIB_PROTOCOL_MPLS:
	cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);

	if (0 == cmp)
	{
	    cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
	}
        break;
    }

    if (0 == cmp) {
	cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
    }
    return (cmp);   
}

int
fib_entry_cmp_for_sort (void *i1, void *i2)
{
    fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;

    return (fib_entry_cmp(*fib_entry_index1,
			  *fib_entry_index2));
}

void
fib_entry_lock (fib_node_index_t fib_entry_index)
{
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_get(fib_entry_index);

    fib_node_lock(&fib_entry->fe_node);
}

void
fib_entry_unlock (fib_node_index_t fib_entry_index)
{
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_get(fib_entry_index);

    fib_node_unlock(&fib_entry->fe_node);
}

void
fib_entry_module_init (void)
{
    fib_node_register_type (FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
}

void
fib_entry_encode (fib_node_index_t fib_entry_index,
		  fib_route_path_encode_t **api_rpaths)
{
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_get(fib_entry_index);
    if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
    {
        fib_path_list_walk(fib_entry->fe_parent, fib_path_encode, api_rpaths);
    }
}

void
fib_entry_get_prefix (fib_node_index_t fib_entry_index,
		      fib_prefix_t *pfx)
{
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_get(fib_entry_index);
    *pfx = fib_entry->fe_prefix;
}

u32
fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
{
    fib_entry_t *fib_entry;

    fib_entry = fib_entry_get(fib_entry_index);

    return (fib_entry->fe_fib_index);
}

u32
fib_entry_pool_size (void)
{
    return (pool_elts(fib_entry_pool));
}

static clib_error_t *
show_fib_entry_command (vlib_main_t * vm,
			unformat_input_t * input,
			vlib_cli_command_t * cmd)
{
    fib_node_index_t fei;

    if (unformat (input, "%d", &fei))
    {
	/*
	 * show one in detail
	 */
	if (!pool_is_free_index(fib_entry_pool, fei))
	{
	    vlib_cli_output (vm, "%d@%U",
			     fei,
			     format_fib_entry, fei,
			     FIB_ENTRY_FORMAT_DETAIL2);
	}
	else
	{
	    vlib_cli_output (vm, "entry %d invalid", fei);
	}
    }
    else
    {
	/*
	 * show all
	 */
	vlib_cli_output (vm, "FIB Entries:");
	pool_foreach_index(fei, fib_entry_pool,
        ({
	    vlib_cli_output (vm, "%d@%U",
			     fei,
			     format_fib_entry, fei,
			     FIB_ENTRY_FORMAT_BRIEF);
	}));
    }

    return (NULL);
}

VLIB_CLI_COMMAND (show_fib_entry, static) = {
  .path = "show fib entry",
  .function = show_fib_entry_command,
  .short_help = "show fib entry",
};