summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/vector_avx512.h
blob: c54d8cd249947d568be507d2920a20ea8ceaa8e4 (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

/*
 * Copyright (c) 2015 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.
 */

#ifndef included_vector_avx512_h
#define included_vector_avx512_h

#include <vppinfra/clib.h>
#include <x86intrin.h>

/* *INDENT-OFF* */
#define foreach_avx512_vec512i \
  _(i,8,64,epi8) _(i,16,32,epi16) _(i,32,16,epi32)  _(i,64,8,epi64)
#define foreach_avx512_vec512u \
  _(u,8,64,epi8) _(u,16,32,epi16) _(u,32,16,epi32)  _(u,64,8,epi64)
#define foreach_avx512_vec512f \
  _(f,32,8,ps) _(f,64,4,pd)

/* splat, load_unaligned, store_unaligned, is_all_zero, is_equal,
   is_all_equal, is_zero_mask */
#define _(t, s, c, i) \
static_always_inline t##s##x##c						\
t##s##x##c##_splat (t##s x)						\
{ return (t##s##x##c) _mm512_set1_##i (x); }				\
\
static_always_inline t##s##x##c						\
t##s##x##c##_load_unaligned (void *p)					\
{ return (t##s##x##c) _mm512_loadu_si512 (p); }				\
\
static_always_inline void						\
t##s##x##c##_store_unaligned (t##s##x##c v, void *p)			\
{ _mm512_storeu_si512 ((__m512i *) p, (__m512i) v); }			\
\
static_always_inline int						\
t##s##x##c##_is_all_zero (t##s##x##c v)					\
{ return (_mm512_test_epi64_mask ((__m512i) v, (__m512i) v) == 0); }	\
\
static_always_inline int						\
t##s##x##c##_is_equal (t##s##x##c a, t##s##x##c b)			\
{ return t##s##x##c##_is_all_zero (a ^ b); }				\
\
static_always_inline int						\
t##s##x##c##_is_all_equal (t##s##x##c v, t##s x)			\
{ return t##s##x##c##_is_equal (v, t##s##x##c##_splat (x)); }		\
\
static_always_inline u##c						\
t##s##x##c##_is_zero_mask (t##s##x##c v)				\
{ return _mm512_test_##i##_mask ((__m512i) v, (__m512i) v); }		\
\
static_always_inline t##s##x##c                                         \
t##s##x##c##_interleave_lo (t##s##x##c a, t##s##x##c b)                 \
{ return (t##s##x##c) _mm512_unpacklo_##i ((__m512i) a, (__m512i) b); } \
\
static_always_inline t##s##x##c                                         \
t##s##x##c##_interleave_hi (t##s##x##c a, t##s##x##c b)                 \
{ return (t##s##x##c) _mm512_unpackhi_##i ((__m512i) a, (__m512i) b); } \


foreach_avx512_vec512i foreach_avx512_vec512u
#undef _
/* *INDENT-ON* */

static_always_inline u32
u16x32_msb_mask (u16x32 v)
{
  return (u32) _mm512_movepi16_mask ((__m512i) v);
}

static_always_inline u32x16
u32x16_byte_swap (u32x16 v)
{
  u8x64 swap = {
    3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12,
    3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12,
    3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12,
    3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12
  };
  return (u32x16) _mm512_shuffle_epi8 ((__m512i) v, (__m512i) swap);
}

static_always_inline u16x32
u16x32_byte_swap (u16x32 v)
{
  u8x64 swap = {
    1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14,
    1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14,
    1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14,
    1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14
  };
  return (u16x32) _mm512_shuffle_epi8 ((__m512i) v, (__m512i) swap);
}

static_always_inline u32x8
u32x16_extract_lo (u32x16 v)
{
  return (u32x8) _mm512_extracti64x4_epi64 ((__m512i) v, 0);
}

static_always_inline u32x8
u32x16_extract_hi (u32x16 v)
{
  return (u32x8) _mm512_extracti64x4_epi64 ((__m512i) v, 1);
}

static_always_inline u32
u32x16_min_scalar (u32x16 v)
{
  return u32x8_min_scalar (u32x8_min (u32x16_extract_lo (v),
				      u32x16_extract_hi (v)));
}

static_always_inline u32x16
u32x16_insert_lo (u32x16 r, u32x8 v)
{
  return (u32x16) _mm512_inserti64x4 ((__m512i) r, (__m256i) v, 0);
}

static_always_inline u32x16
u32x16_insert_hi (u32x16 r, u32x8 v)
{
  return (u32x16) _mm512_inserti64x4 ((__m512i) r, (__m256i) v, 1);
}

static_always_inline u64x8
u64x8_permute (u64x8 a, u64x8 b, u64x8 mask)
{
  return (u64x8) _mm512_permutex2var_epi64 ((__m512i) a, (__m512i) mask,
					    (__m512i) b);
}


#define u32x16_ternary_logic(a, b, c, d) \
  (u32x16) _mm512_ternarylogic_epi32 ((__m512i) a, (__m512i) b, (__m512i) c, d)

static_always_inline void
u32x16_transpose (u32x16 m[16])
{
  __m512i r[16], a, b, c, d, x, y;

  /* *INDENT-OFF* */
  __m512i pm1 = (__m512i) (u64x8) { 0, 1, 8, 9, 4, 5, 12, 13};
  __m512i pm2 = (__m512i) (u64x8) { 2, 3, 10, 11, 6, 7, 14, 15};
  __m512i pm3 = (__m512i) (u64x8) { 0, 1, 2, 3, 8, 9, 10, 11};
  __m512i pm4 = (__m512i) (u64x8) { 4, 5, 6, 7, 12, 13, 14, 15};
  /* *INDENT-ON* */

  r[0] = _mm512_unpacklo_epi32 ((__m512i) m[0], (__m512i) m[1]);
  r[1] = _mm512_unpacklo_epi32 ((__m512i) m[2], (__m512i) m[3]);
  r[2] = _mm512_unpacklo_epi32 ((__m512i) m[4], (__m512i) m[5]);
  r[3] = _mm512_unpacklo_epi32 ((__m512i) m[6], (__m512i) m[7]);
  r[4] = _mm512_unpacklo_epi32 ((__m512i) m[8], (__m512i) m[9]);
  r[5] = _mm512_unpacklo_epi32 ((__m512i) m[10], (__m512i) m[11]);
  r[6] = _mm512_unpacklo_epi32 ((__m512i) m[12], (__m512i) m[13]);
  r[7] = _mm512_unpacklo_epi32 ((__m512i) m[14], (__m512i) m[15]);

  r[8] = _mm512_unpackhi_epi32 ((__m512i) m[0], (__m512i) m[1]);
  r[9] = _mm512_unpackhi_epi32 ((__m512i) m[2], (__m512i) m[3]);
  r[10] = _mm512_unpackhi_epi32 ((__m512i) m[4], (__m512i) m[5]);
  r[11] = _mm512_unpackhi_epi32 ((__m512i) m[6], (__m512i) m[7]);
  r[12] = _mm512_unpackhi_epi32 ((__m512i) m[8], (__m512i) m[9]);
  r[13] = _mm512_unpackhi_epi32 ((__m512i) m[10], (__m512i) m[11]);
  r[14] = _mm512_unpackhi_epi32 ((__m512i) m[12], (__m512i) m[13]);
  r[15] = _mm512_unpackhi_epi32 ((__m512i) m[14], (__m512i) m[15]);

  a = _mm512_unpacklo_epi64 (r[0], r[1]);
  b = _mm512_unpacklo_epi64 (r[2], r[3]);
  c = _mm512_unpacklo_epi64 (r[4], r[5]);
  d = _mm512_unpacklo_epi64 (r[6], r[7]);
  x = _mm512_permutex2var_epi64 (a, pm1, b);
  y = _mm512_permutex2var_epi64 (c, pm1, d);
  m[0] = (u32x16) _mm512_permutex2var_epi64 (x, pm3, y);
  m[8] = (u32x16) _mm512_permutex2var_epi64 (x, pm4, y);
  x = _mm512_permutex2var_epi64 (a, pm2, b);
  y = _mm512_permutex2var_epi64 (c, pm2, d);
  m[4] = (u32x16) _mm512_permutex2var_epi64 (x, pm3, y);
  m[12] = (u32x16) _mm512_permutex2var_epi64 (x, pm4, y);

  a = _mm512_unpacklo_epi64 (r[8], r[9]);
  b = _mm512_unpacklo_epi64 (r[10], r[11]);
  c = _mm512_unpacklo_epi64 (r[12], r[13]);
  d = _mm512_unpacklo_epi64 (r[14], r[15]);
  x = _mm512_permutex2var_epi64 (a, pm1, b);
  y = _mm512_permutex2var_epi64 (c, pm1, d);
  m[2] = (u32x16) _mm512_permutex2var_epi64 (x, pm3, y);
  m[10] = (u32x16) _mm512_permutex2var_epi64 (x, pm4, y);
  x = _mm512_permutex2var_epi64 (a, pm2, b);
  y = _mm512_permutex2var_epi64 (c, pm2, d);
  m[6] = (u32x16) _mm512_permutex2var_epi64 (x, pm3, y);
  m[14] = (u32x16) _mm512_permutex2var_epi64 (x, pm4, y);

  a = _mm512_unpackhi_epi64 (r[0], r[1]);
  b = _mm512_unpackhi_epi64 (r[2], r[3]);
  c = _mm512_unpackhi_epi64 (r[4], r[5]);
  d = _mm512_unpackhi_epi64 (r[6], r[7]);
  x = _mm512_permutex2var_epi64 (a, pm1, b);
  y = _mm512_permutex2var_epi64 (c, pm1, d);
  m[1] = (u32x16) _mm512_permutex2var_epi64 (x, pm3, y);
  m[9] = (u32x16) _mm512_permutex2var_epi64 (x, pm4, y);
  x = _mm512_permutex2var_epi64 (a, pm2, b);
  y = _mm512_permutex2var_epi64 (c, pm2, d);
  m[5] = (u32x16) _mm512_permutex2var_epi64 (x, pm3, y);
  m[13] = (u32x16) _mm512_permutex2var_epi64 (x, pm4, y);

  a = _mm512_unpackhi_epi64 (r[8], r[9]);
  b = _mm512_unpackhi_epi64 (r[10], r[11]);
  c = _mm512_unpackhi_epi64 (r[12], r[13]);
  d = _mm512_unpackhi_epi64 (r[14], r[15]);
  x = _mm512_permutex2var_epi64 (a, pm1, b);
  y = _mm512_permutex2var_epi64 (c, pm1, d);
  m[3] = (u32x16) _mm512_permutex2var_epi64 (x, pm3, y);
  m[11] = (u32x16) _mm512_permutex2var_epi64 (x, pm4, y);
  x = _mm512_permutex2var_epi64 (a, pm2, b);
  y = _mm512_permutex2var_epi64 (c, pm2, d);
  m[7] = (u32x16) _mm512_permutex2var_epi64 (x, pm3, y);
  m[15] = (u32x16) _mm512_permutex2var_epi64 (x, pm4, y);
}



static_always_inline void
u64x8_transpose (u64x8 m[8])
{
  __m512i r[8], x, y;

  /* *INDENT-OFF* */
  __m512i pm1 = (__m512i) (u64x8) { 0, 1, 8, 9, 4, 5, 12, 13};
  __m512i pm2 = (__m512i) (u64x8) { 2, 3, 10, 11, 6, 7, 14, 15};
  __m512i pm3 = (__m512i) (u64x8) { 0, 1, 2, 3, 8, 9, 10, 11};
  __m512i pm4 = (__m512i) (u64x8) { 4, 5, 6, 7, 12, 13, 14, 15};
  /* *INDENT-ON* */

  r[0] = _mm512_unpacklo_epi64 ((__m512i) m[0], (__m512i) m[1]);
  r[1] = _mm512_unpacklo_epi64 ((__m512i) m[2], (__m512i) m[3]);
  r[2] = _mm512_unpacklo_epi64 ((__m512i) m[4], (__m512i) m[5]);
  r[3] = _mm512_unpacklo_epi64 ((__m512i) m[6], (__m512i) m[7]);
  r[4] = _mm512_unpackhi_epi64 ((__m512i) m[0], (__m512i) m[1]);
  r[5] = _mm512_unpackhi_epi64 ((__m512i) m[2], (__m512i) m[3]);
  r[6] = _mm512_unpackhi_epi64 ((__m512i) m[4], (__m512i) m[5]);
  r[7] = _mm512_unpackhi_epi64 ((__m512i) m[6], (__m512i) m[7]);

  x = _mm512_permutex2var_epi64 (r[0], pm1, r[1]);
  y = _mm512_permutex2var_epi64 (r[2], pm1, r[3]);
  m[0] = (u64x8) _mm512_permutex2var_epi64 (x, pm3, y);
  m[4] = (u64x8) _mm512_permutex2var_epi64 (x, pm4, y);
  x = _mm512_permutex2var_epi64 (r[0], pm2, r[1]);
  y = _mm512_permutex2var_epi64 (r[2], pm2, r[3]);
  m[2] = (u64x8) _mm512_permutex2var_epi64 (x, pm3, y);
  m[6] = (u64x8) _mm512_permutex2var_epi64 (x, pm4, y);

  x = _mm512_permutex2var_epi64 (r[4], pm1, r[5]);
  y = _mm512_permutex2var_epi64 (r[6], pm1, r[7]);
  m[1] = (u64x8) _mm512_permutex2var_epi64 (x, pm3, y);
  m[5] = (u64x8) _mm512_permutex2var_epi64 (x, pm4, y);
  x = _mm512_permutex2var_epi64 (r[4], pm2, r[5]);
  y = _mm512_permutex2var_epi64 (r[6], pm2, r[7]);
  m[3] = (u64x8) _mm512_permutex2var_epi64 (x, pm3, y);
  m[7] = (u64x8) _mm512_permutex2var_epi64 (x, pm4, y);
}

#endif /* included_vector_avx512_h */
/*
 * fd.io coding-style-patch-verification: ON
 *
 * Local Variables:
 * eval: (c-set-style "gnu")
 * End:
 */
background-color: #fff0f0 } /* Literal.String.Affix */ .highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */ .highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */ .highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */ .highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */ .highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */ .highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */ .highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */ .highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */ .highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */ .highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */ .highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */ .highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */ .highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */ .highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */ .highlight .vc { color: #336699 } /* Name.Variable.Class */ .highlight .vg { color: #dd7700 } /* Name.Variable.Global */ .highlight .vi { color: #3333bb } /* Name.Variable.Instance */ .highlight .vm { color: #336699 } /* Name.Variable.Magic */ .highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */ } 
/*
 * 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/vnet.h>
#include <vnet/ip/format.h>
#include <vnet/ip/ip.h>
#include <vnet/dpo/drop_dpo.h>
#include <vnet/dpo/receive_dpo.h>
#include <vnet/dpo/load_balance_map.h>
#include <vnet/dpo/lookup_dpo.h>

#include <vnet/adj/adj.h>
#include <vnet/adj/adj_mcast.h>

#include <vnet/fib/fib_path.h>
#include <vnet/fib/fib_node.h>
#include <vnet/fib/fib_table.h>
#include <vnet/fib/fib_entry.h>
#include <vnet/fib/fib_path_list.h>
#include <vnet/fib/fib_internal.h>
#include <vnet/fib/fib_urpf_list.h>

/**
 * Enurmeration of path types
 */
typedef enum fib_path_type_t_ {
    /**
     * Marker. Add new types after this one.
     */
    FIB_PATH_TYPE_FIRST = 0,
    /**
     * Attached-nexthop. An interface and a nexthop are known.
     */
    FIB_PATH_TYPE_ATTACHED_NEXT_HOP = FIB_PATH_TYPE_FIRST,
    /**
     * attached. Only the interface is known.
     */
    FIB_PATH_TYPE_ATTACHED,
    /**
     * recursive. Only the next-hop is known.
     */
    FIB_PATH_TYPE_RECURSIVE,
    /**
     * special. nothing is known. so we drop.
     */
    FIB_PATH_TYPE_SPECIAL,
    /**
     * exclusive. user provided adj.
     */
    FIB_PATH_TYPE_EXCLUSIVE,
    /**
     * deag. Link to a lookup adj in the next table
     */
    FIB_PATH_TYPE_DEAG,
    /**
     * receive. it's for-us.
     */
    FIB_PATH_TYPE_RECEIVE,
    /**
     * Marker. Add new types before this one, then update it.
     */
    FIB_PATH_TYPE_LAST = FIB_PATH_TYPE_RECEIVE,
} __attribute__ ((packed)) fib_path_type_t;

/**
 * The maximum number of path_types
 */
#define FIB_PATH_TYPE_MAX (FIB_PATH_TYPE_LAST + 1)

#define FIB_PATH_TYPES {					\
    [FIB_PATH_TYPE_ATTACHED_NEXT_HOP] = "attached-nexthop",	\
    [FIB_PATH_TYPE_ATTACHED]          = "attached",		\
    [FIB_PATH_TYPE_RECURSIVE]         = "recursive",	        \
    [FIB_PATH_TYPE_SPECIAL]           = "special",	        \
    [FIB_PATH_TYPE_EXCLUSIVE]         = "exclusive",	        \
    [FIB_PATH_TYPE_DEAG]              = "deag",	                \
    [FIB_PATH_TYPE_RECEIVE]           = "receive",	        \
}

#define FOR_EACH_FIB_PATH_TYPE(_item) \
    for (_item = FIB_PATH_TYPE_FIRST; _item <= FIB_PATH_TYPE_LAST; _item++)

/**
 * Enurmeration of path operational (i.e. derived) attributes
 */
typedef enum fib_path_oper_attribute_t_ {
    /**
     * Marker. Add new types after this one.
     */
    FIB_PATH_OPER_ATTRIBUTE_FIRST = 0,
    /**
     * The path forms part of a recursive loop.
     */
    FIB_PATH_OPER_ATTRIBUTE_RECURSIVE_LOOP = FIB_PATH_OPER_ATTRIBUTE_FIRST,
    /**
     * The path is resolved
     */
    FIB_PATH_OPER_ATTRIBUTE_RESOLVED,
    /**
     * The path has become a permanent drop.
     */
    FIB_PATH_OPER_ATTRIBUTE_DROP,
    /**
     * Marker. Add new types before this one, then update it.
     */
    FIB_PATH_OPER_ATTRIBUTE_LAST = FIB_PATH_OPER_ATTRIBUTE_DROP,
} __attribute__ ((packed)) fib_path_oper_attribute_t;

/**
 * The maximum number of path operational attributes
 */
#define FIB_PATH_OPER_ATTRIBUTE_MAX (FIB_PATH_OPER_ATTRIBUTE_LAST + 1)

#define FIB_PATH_OPER_ATTRIBUTES {					\
    [FIB_PATH_OPER_ATTRIBUTE_RECURSIVE_LOOP] = "recursive-loop",	\
    [FIB_PATH_OPER_ATTRIBUTE_RESOLVED]       = "resolved",	        \
    [FIB_PATH_OPER_ATTRIBUTE_DROP]           = "drop",		        \
}

#define FOR_EACH_FIB_PATH_OPER_ATTRIBUTE(_item) \
    for (_item = FIB_PATH_OPER_ATTRIBUTE_FIRST; \
	 _item <= FIB_PATH_OPER_ATTRIBUTE_LAST; \
	 _item++)

/**
 * Path flags from the attributes
 */
typedef enum fib_path_oper_flags_t_ {
    FIB_PATH_OPER_FLAG_NONE = 0,
    FIB_PATH_OPER_FLAG_RECURSIVE_LOOP = (1 << FIB_PATH_OPER_ATTRIBUTE_RECURSIVE_LOOP),
    FIB_PATH_OPER_FLAG_DROP = (1 << FIB_PATH_OPER_ATTRIBUTE_DROP),
    FIB_PATH_OPER_FLAG_RESOLVED = (1 << FIB_PATH_OPER_ATTRIBUTE_RESOLVED),
} __attribute__ ((packed)) fib_path_oper_flags_t;

/**
 * A FIB path
 */
typedef struct fib_path_t_ {
    /**
     * A path is a node in the FIB graph.
     */
    fib_node_t fp_node;

    /**
     * The index of the path-list to which this path belongs
     */
    u32 fp_pl_index;

    /**
     * This marks the start of the memory area used to hash
     * the path
     */
    STRUCT_MARK(path_hash_start);

    /**
     * Configuration Flags
     */
    fib_path_cfg_flags_t fp_cfg_flags;

    /**
     * The type of the path. This is the selector for the union
     */
    fib_path_type_t fp_type;

    /**
     * The protocol of the next-hop, i.e. the address family of the
     * next-hop's address. We can't derive this from the address itself
     * since the address can be all zeros
     */
    fib_protocol_t fp_nh_proto;

    /**
     * UCMP [unnormalised] weigt
     */
    u32 fp_weight;

    /**
     * per-type union of the data required to resolve the path
     */
    union {
	struct {
	    /**
	     * The next-hop
	     */
	    ip46_address_t fp_nh;
	    /**
	     * The interface
	     */
	    u32 fp_interface;
	} attached_next_hop;
	struct {
	    /**
	     * The interface
	     */
	    u32 fp_interface;
	} attached;
	struct {
	    union
	    {
		/**
		 * The next-hop
		 */
		ip46_address_t fp_ip;
		/**
		 * The local label to resolve through.
		 */
		mpls_label_t fp_local_label;
	    } fp_nh;
	    /**
	     * The FIB table index in which to find the next-hop.
	     * This needs to be fixed. We should lookup the adjacencies in
	     * a separate table of adjacencies, rather than from the FIB.
	     * Two reasons I can think of:
	     *   - consider:
	     *       int ip addr Gig0 10.0.0.1/24
	     *       ip route 10.0.0.2/32 via Gig1 192.168.1.2
	     *       ip route 1.1.1.1/32 via Gig0 10.0.0.2
	     *     this is perfectly valid.
	     *     Packets addressed to 10.0.0.2 should be sent via Gig1.
	     *     Packets address to 1.1.1.1 should be sent via Gig0.
	     *    when we perform the adj resolution from the FIB for the path
	     *    "via Gig0 10.0.0.2" the lookup will result in the route via Gig1
	     *    and so we will pick up the adj via Gig1 - which was not what the
	     *    operator wanted.
	     *  - we can only return link-type IPv4 and so not the link-type MPLS.
	     *    more on this in a later commit.
	     *
	     * The table ID should only belong to a recursive path and indicate
	     * which FIB should be used to resolve the next-hop.
	     */
	    fib_node_index_t fp_tbl_id;
	} recursive;
	struct {
	    /**
	     * The FIB index in which to perfom the next lookup
	     */
	    fib_node_index_t fp_tbl_id;
	} deag;
	struct {
	} special;
	struct {
	    /**
	     * The user provided 'exclusive' DPO
	     */
	    dpo_id_t fp_ex_dpo;
	} exclusive;
	struct {
	    /**
	     * The interface on which the local address is configured
	     */
	    u32 fp_interface;
	    /**
	     * The next-hop
	     */
	    ip46_address_t fp_addr;
	} receive;
    };
    STRUCT_MARK(path_hash_end);

    /**
     * Memebers in this last section represent information that is
     * dervied during resolution. It should not be copied to new paths
     * nor compared.
     */

    /**
     * Operational Flags
     */
    fib_path_oper_flags_t fp_oper_flags;

    /**
     * the resolving via fib. not part of the union, since it it not part
     * of the path's hash.
     */
    fib_node_index_t fp_via_fib;

    /**
     * The Data-path objects through which this path resolves for IP.
     */
    dpo_id_t fp_dpo;

    /**
     * the index of this path in the parent's child list.
     */
    u32 fp_sibling;
} fib_path_t;

/*
 * Array of strings/names for the path types and attributes
 */
static const char *fib_path_type_names[] = FIB_PATH_TYPES;
static const char *fib_path_oper_attribute_names[] = FIB_PATH_OPER_ATTRIBUTES;
static const char *fib_path_cfg_attribute_names[]  = FIB_PATH_CFG_ATTRIBUTES;

/*
 * The memory pool from which we allocate all the paths
 */
static fib_path_t *fib_path_pool;

/*
 * Debug macro
 */
#ifdef FIB_DEBUG
#define FIB_PATH_DBG(_p, _fmt, _args...)			\
{       		          				\
    u8 *_tmp = NULL;						\
    _tmp = fib_path_format(fib_path_get_index(_p), _tmp);	\
    clib_warning("path:[%d:%s]:" _fmt,				\
		 fib_path_get_index(_p), _tmp,			\
		 ##_args);					\
    vec_free(_tmp);						\
}
#else
#define FIB_PATH_DBG(_p, _fmt, _args...)
#endif

static fib_path_t *
fib_path_get (fib_node_index_t index)
{
    return (pool_elt_at_index(fib_path_pool, index));
}

static fib_node_index_t 
fib_path_get_index (fib_path_t *path)
{
    return (path - fib_path_pool);
}

static fib_node_t *
fib_path_get_node (fib_node_index_t index)
{
    return ((fib_node_t*)fib_path_get(index));
}

static fib_path_t*
fib_path_from_fib_node (fib_node_t *node)
{
#if CLIB_DEBUG > 0
    ASSERT(FIB_NODE_TYPE_PATH == node->fn_type);
#endif
    return ((fib_path_t*)node);
}

u8 *
format_fib_path (u8 * s, va_list * args)
{
    fib_path_t *path = va_arg (*args, fib_path_t *);
    vnet_main_t * vnm = vnet_get_main();
    fib_path_oper_attribute_t oattr;
    fib_path_cfg_attribute_t cattr;

    s = format (s, "      index:%d ", fib_path_get_index(path));
    s = format (s, "pl-index:%d ", path->fp_pl_index);
    s = format (s, "%U ", format_fib_protocol, path->fp_nh_proto);
    s = format (s, "weight=%d ", path->fp_weight);
    s = format (s, "%s: ", fib_path_type_names[path->fp_type]);
    if (FIB_PATH_OPER_FLAG_NONE != path->fp_oper_flags) {
	s = format(s, " oper-flags:");
	FOR_EACH_FIB_PATH_OPER_ATTRIBUTE(oattr) {
	    if ((1<<oattr) & path->fp_oper_flags) {
		s = format (s, "%s,", fib_path_oper_attribute_names[oattr]);
	    }
	}
    }
    if (FIB_PATH_CFG_FLAG_NONE != path->fp_cfg_flags) {
	s = format(s, " cfg-flags:");
	FOR_EACH_FIB_PATH_CFG_ATTRIBUTE(cattr) {
	    if ((1<<cattr) & path->fp_cfg_flags) {
		s = format (s, "%s,", fib_path_cfg_attribute_names[cattr]);
	    }
	}
    }
    s = format(s, "\n       ");

    switch (path->fp_type)
    {
    case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
	s = format (s, "%U", format_ip46_address,
		    &path->attached_next_hop.fp_nh,
		    IP46_TYPE_ANY);
	if (path->fp_oper_flags & FIB_PATH_OPER_FLAG_DROP)
	{
	    s = format (s, " if_index:%d", path->attached_next_hop.fp_interface);
	}
	else
	{
	    s = format (s, " %U",
			format_vnet_sw_interface_name,
			vnm,
			vnet_get_sw_interface(
			    vnm,
			    path->attached_next_hop.fp_interface));
	    if (vnet_sw_interface_is_p2p(vnet_get_main(),
					 path->attached_next_hop.fp_interface))
	    {
		s = format (s, " (p2p)");
	    }
	}
	if (!dpo_id_is_valid(&path->fp_dpo))
	{
	    s = format(s, "\n          unresolved");
	}
	else
	{
	    s = format(s, "\n          %U",
		       format_dpo_id,
		       &path->fp_dpo, 13);
	}
	break;
    case FIB_PATH_TYPE_ATTACHED:
	if (path->fp_oper_flags & FIB_PATH_OPER_FLAG_DROP)
	{
	    s = format (s, " if_index:%d", path->attached_next_hop.fp_interface);
	}
	else
	{
	    s = format (s, " %U",
			format_vnet_sw_interface_name,
			vnm,
			vnet_get_sw_interface(
			    vnm,
			    path->attached.fp_interface));
	}
	break;
    case FIB_PATH_TYPE_RECURSIVE:
	if (FIB_PROTOCOL_MPLS == path->fp_nh_proto)
	{
	    s = format (s, "via %U",
			format_mpls_unicast_label,
			path->recursive.fp_nh.fp_local_label);
	}
	else
	{
	    s = format (s, "via %U",
			format_ip46_address,
			&path->recursive.fp_nh.fp_ip,
			IP46_TYPE_ANY);
	}
	s = format (s, " in fib:%d",
		    path->recursive.fp_tbl_id,
		    path->fp_via_fib); 
	s = format (s, " via-fib:%d", path->fp_via_fib); 
	s = format (s, " via-dpo:[%U:%d]",
		    format_dpo_type, path->fp_dpo.dpoi_type, 
		    path->fp_dpo.dpoi_index);

	break;
    case FIB_PATH_TYPE_RECEIVE:
    case FIB_PATH_TYPE_SPECIAL:
    case FIB_PATH_TYPE_DEAG:
    case FIB_PATH_TYPE_EXCLUSIVE:
	if (dpo_id_is_valid(&path->fp_dpo))
	{
	    s = format(s, "%U", format_dpo_id,
		       &path->fp_dpo, 2);
	}
	break;
    }
    return (s);
}

u8 *
fib_path_format (fib_node_index_t pi, u8 *s)
{
    fib_path_t *path;

    path = fib_path_get(pi);
    ASSERT(NULL != path);

    return (format (s, "%U", format_fib_path, path));
}

u8 *
fib_path_adj_format (fib_node_index_t pi,
		     u32 indent,
		     u8 *s)
{
    fib_path_t *path;

    path = fib_path_get(pi);
    ASSERT(NULL != path);

    if (!dpo_id_is_valid(&path->fp_dpo))
    {
	s = format(s, " unresolved");
    }
    else
    {
	s = format(s, "%U", format_dpo_id,
		   &path->fp_dpo, 2);
    }

    return (s);
}

/*
 * fib_path_last_lock_gone
 *
 * We don't share paths, we share path lists, so the [un]lock functions
 * are no-ops
 */
static void
fib_path_last_lock_gone (fib_node_t *node)
{
    ASSERT(0);
}

static const adj_index_t
fib_path_attached_next_hop_get_adj (fib_path_t *path,
				    vnet_link_t link)
{
    if (vnet_sw_interface_is_p2p(vnet_get_main(),
				 path->attached_next_hop.fp_interface))
    {
	/*
	 * if the interface is p2p then the adj for the specific
	 * neighbour on that link will never exist. on p2p links
	 * the subnet address (the attached route) links to the
	 * auto-adj (see below), we want that adj here too.
	 */
	return (adj_nbr_add_or_lock(path->fp_nh_proto,
				    link,
				    &zero_addr,
				    path->attached_next_hop.fp_interface));
    }
    else
    {
	return (adj_nbr_add_or_lock(path->fp_nh_proto,
				    link,
				    &path->attached_next_hop.fp_nh,
				    path->attached_next_hop.fp_interface));
    }
}

static void
fib_path_attached_next_hop_set (fib_path_t *path)
{
    /*
     * resolve directly via the adjacnecy discribed by the
     * interface and next-hop
     */
    if (!vnet_sw_interface_is_admin_up(vnet_get_main(),
				      path->attached_next_hop.fp_interface))
    {
	path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
    }

    dpo_set(&path->fp_dpo,
	    DPO_ADJACENCY,
	    fib_proto_to_dpo(path->fp_nh_proto),
	    fib_path_attached_next_hop_get_adj(
		 path,
		 fib_proto_to_link(path->fp_nh_proto)));

    /*
     * become a child of the adjacency so we receive updates
     * when its rewrite changes
     */
    path->fp_sibling = adj_child_add(path->fp_dpo.dpoi_index,
				     FIB_NODE_TYPE_PATH,
				     fib_path_get_index(path));
}

/*
 * create of update the paths recursive adj
 */
static void
fib_path_recursive_adj_update (fib_path_t *path,
			       fib_forward_chain_type_t fct,
			       dpo_id_t *dpo)
{
    dpo_id_t via_dpo = DPO_INVALID;

    /*
     * get the DPO to resolve through from the via-entry
     */
    fib_entry_contribute_forwarding(path->fp_via_fib,
				    fct,
				    &via_dpo);


    /*
     * hope for the best - clear if restrictions apply.
     */
    path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;

    /*
     * Validate any recursion constraints and over-ride the via
     * adj if not met
     */
    if (path->fp_oper_flags & FIB_PATH_OPER_FLAG_RECURSIVE_LOOP)
    {
	path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
	dpo_copy(&via_dpo, drop_dpo_get(fib_proto_to_dpo(path->fp_nh_proto)));
    }
    else if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RESOLVE_HOST)
    {
	/*
	 * the via FIB must be a host route.
	 * note the via FIB just added will always be a host route
	 * since it is an RR source added host route. So what we need to
	 * check is whether the route has other sources. If it does then
	 * some other source has added it as a host route. If it doesn't
	 * then it was added only here and inherits forwarding from a cover.
	 * the cover is not a host route.
	 * The RR source is the lowest priority source, so we check if it
	 * is the best. if it is there are no other sources.
	 */
	if (fib_entry_get_best_source(path->fp_via_fib) >= FIB_SOURCE_RR)
	{
	    path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
            dpo_copy(&via_dpo, drop_dpo_get(fib_proto_to_dpo(path->fp_nh_proto)));

            /*
             * PIC edge trigger. let the load-balance maps know
             */
            load_balance_map_path_state_change(fib_path_get_index(path));
	}
    }
    else if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RESOLVE_ATTACHED)
    {
	/*
	 * RR source entries inherit the flags from the cover, so
	 * we can check the via directly
	 */
	if (!(FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags(path->fp_via_fib)))
	{
	    path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
            dpo_copy(&via_dpo, drop_dpo_get(fib_proto_to_dpo(path->fp_nh_proto)));

            /*
             * PIC edge trigger. let the load-balance maps know
             */
            load_balance_map_path_state_change(fib_path_get_index(path));
	}
    }

    /*
     * update the path's contributed DPO
     */
    dpo_copy(dpo, &via_dpo);

    FIB_PATH_DBG(path, "recursive update: %U",
		 fib_get_lookup_main(path->fp_nh_proto),
		 &path->fp_dpo, 2);

    dpo_reset(&via_dpo);
}

/*
 * fib_path_is_permanent_drop
 *
 * Return !0 if the path is configured to permanently drop,
 * despite other attributes.
 */
static int
fib_path_is_permanent_drop (fib_path_t *path)
{
    return ((path->fp_cfg_flags & FIB_PATH_CFG_FLAG_DROP) ||
	    (path->fp_oper_flags & FIB_PATH_OPER_FLAG_DROP));
}

/*
 * fib_path_unresolve
 *
 * Remove our dependency on the resolution target
 */
static void
fib_path_unresolve (fib_path_t *path)
{
    /*
     * the forced drop path does not need unresolving
     */
    if (fib_path_is_permanent_drop(path))
    {
	return;
    }

    switch (path->fp_type)
    {
    case FIB_PATH_TYPE_RECURSIVE:
	if (FIB_NODE_INDEX_INVALID != path->fp_via_fib)
	{
	    fib_prefix_t pfx;

	    fib_entry_get_prefix(path->fp_via_fib, &pfx);
	    fib_entry_child_remove(path->fp_via_fib,
				   path->fp_sibling);
	    fib_table_entry_special_remove(path->recursive.fp_tbl_id,
					   &pfx,
					   FIB_SOURCE_RR);
	    path->fp_via_fib = FIB_NODE_INDEX_INVALID;
	}
	break;
    case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
    case FIB_PATH_TYPE_ATTACHED:
	adj_child_remove(path->fp_dpo.dpoi_index,
			 path->fp_sibling);
        adj_unlock(path->fp_dpo.dpoi_index);
        break;
    case FIB_PATH_TYPE_EXCLUSIVE:
	dpo_reset(&path->exclusive.fp_ex_dpo);
        break;
    case FIB_PATH_TYPE_SPECIAL:
    case FIB_PATH_TYPE_RECEIVE:
    case FIB_PATH_TYPE_DEAG:
        /*
         * these hold only the path's DPO, which is reset below.
         */
	break;
    }

    /*
     * release the adj we were holding and pick up the
     * drop just in case.
     */
    dpo_reset(&path->fp_dpo);
    path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;

    return;
}

static fib_forward_chain_type_t
fib_path_proto_to_chain_type (fib_protocol_t proto)
{
    switch (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:
	return (FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS);
    }
    return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
}

/*
 * fib_path_back_walk_notify
 *
 * A back walk has reach this path.
 */
static fib_node_back_walk_rc_t
fib_path_back_walk_notify (fib_node_t *node,
			   fib_node_back_walk_ctx_t *ctx)
{
    fib_path_t *path;

    path = fib_path_from_fib_node(node);

    switch (path->fp_type)
    {
    case FIB_PATH_TYPE_RECURSIVE:
	if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason)
	{
	    /*
	     * modify the recursive adjacency to use the new forwarding
	     * of the via-fib.
	     * this update is visible to packets in flight in the DP.
	     */
	    fib_path_recursive_adj_update(
		path,
		fib_path_proto_to_chain_type(path->fp_nh_proto),
		&path->fp_dpo);
	}
	if ((FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason) ||
            (FIB_NODE_BW_REASON_FLAG_ADJ_DOWN   & ctx->fnbw_reason))
	{
	    /*
	     * ADJ updates (complete<->incomplete) do not need to propagate to
	     * recursive entries.
	     * The only reason its needed as far back as here, is that the adj
	     * and the incomplete adj are a different DPO type, so the LBs need
	     * to re-stack.
	     * If this walk was quashed in the fib_entry, then any non-fib_path
	     * children (like tunnels that collapse out the LB when they stack)
	     * would not see the update.
	     */
	    return (FIB_NODE_BACK_WALK_CONTINUE);
	}
	break;
    case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
	/*
FIXME comment
	 * ADJ_UPDATE backwalk pass silently through here and up to
	 * the path-list when the multipath adj collapse occurs.
	 * The reason we do this is that the assumtption is that VPP
	 * runs in an environment where the Control-Plane is remote
	 * and hence reacts slowly to link up down. In order to remove
	 * this down link from the ECMP set quickly, we back-walk.
	 * VPP also has dedicated CPUs, so we are not stealing resources
	 * from the CP to do so.
	 */
	if (FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason)
	{
            if (path->fp_oper_flags & FIB_PATH_OPER_FLAG_RESOLVED)
            {
                /*
                 * alreday resolved. no need to walk back again
                 */
                return (FIB_NODE_BACK_WALK_CONTINUE);
            }
	    path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;
	}
	if (FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason)
	{
            if (!(path->fp_oper_flags & FIB_PATH_OPER_FLAG_RESOLVED))
            {
                /*
                 * alreday unresolved. no need to walk back again
                 */
                return (FIB_NODE_BACK_WALK_CONTINUE);
            }
	    path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
	}
	if (FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
	{
	    /*
	     * The interface this path resolves through has been deleted.
	     * This will leave the path in a permanent drop state. The route
	     * needs to be removed and readded (and hence the path-list deleted)
	     * before it can forward again.
	     */
	    fib_path_unresolve(path);
	    path->fp_oper_flags |= FIB_PATH_OPER_FLAG_DROP;
	}
        if (FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason)
	{
            /*
             * restack the DPO to pick up the correct DPO sub-type
             */
            uword if_is_up;
            adj_index_t ai;

            if_is_up = vnet_sw_interface_is_admin_up(
                           vnet_get_main(),
                           path->attached_next_hop.fp_interface);

            if (if_is_up)
            {
                path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;
            }

            ai = fib_path_attached_next_hop_get_adj(
                     path,
                     fib_proto_to_link(path->fp_nh_proto));

            dpo_set(&path->fp_dpo, DPO_ADJACENCY,
                    fib_proto_to_dpo(path->fp_nh_proto),
                    ai);
            adj_unlock(ai);

            if (!if_is_up)
            {
                /*
                 * If the interface is not up there is no reason to walk
                 * back to children. if we did they would only evalute
                 * that this path is unresolved and hence it would
                 * not contribute the adjacency - so it would be wasted
                 * CPU time.
                 */
                return (FIB_NODE_BACK_WALK_CONTINUE);
            }
        }
        if (FIB_NODE_BW_REASON_FLAG_ADJ_DOWN & ctx->fnbw_reason)
	{
            if (!(path->fp_oper_flags & FIB_PATH_OPER_FLAG_RESOLVED))
            {
                /*
                 * alreday unresolved. no need to walk back again
                 */
                return (FIB_NODE_BACK_WALK_CONTINUE);
            }
            /*
             * the adj has gone down. the path is no longer resolved.
             */
	    path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
        }
	break;
    case FIB_PATH_TYPE_ATTACHED:
	/*
	 * FIXME; this could schedule a lower priority walk, since attached
	 * routes are not usually in ECMP configurations so the backwalk to
	 * the FIB entry does not need to be high priority
	 */
	if (FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason)
	{
	    path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;
	}
	if (FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason)
	{
	    path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
	}
	if (FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
	{
	    fib_path_unresolve(path);
	    path->fp_oper_flags |= FIB_PATH_OPER_FLAG_DROP;
	}
	break;
    case FIB_PATH_TYPE_DEAG:
	/*
	 * FIXME When VRF delete is allowed this will need a poke.
	 */
    case FIB_PATH_TYPE_SPECIAL:
    case FIB_PATH_TYPE_RECEIVE:
    case FIB_PATH_TYPE_EXCLUSIVE:
	/*
	 * these path types have no parents. so to be
	 * walked from one is unexpected.
	 */
	ASSERT(0);
	break;
    }

    /*
     * propagate the backwalk further to the path-list
     */
    fib_path_list_back_walk(path->fp_pl_index, ctx);

    return (FIB_NODE_BACK_WALK_CONTINUE);
}

static void
fib_path_memory_show (void)
{
    fib_show_memory_usage("Path",
			  pool_elts(fib_path_pool),
			  pool_len(fib_path_pool),
			  sizeof(fib_path_t));
}

/*
 * The FIB path's graph node virtual function table
 */
static const fib_node_vft_t fib_path_vft = {
    .fnv_get = fib_path_get_node,
    .fnv_last_lock = fib_path_last_lock_gone,
    .fnv_back_walk = fib_path_back_walk_notify,
    .fnv_mem_show = fib_path_memory_show,
};

static fib_path_cfg_flags_t
fib_path_route_flags_to_cfg_flags (const fib_route_path_t *rpath)
{
    fib_path_cfg_flags_t cfg_flags = FIB_PATH_CFG_FLAG_NONE;

    if (rpath->frp_flags & FIB_ROUTE_PATH_RESOLVE_VIA_HOST)
	cfg_flags |= FIB_PATH_CFG_FLAG_RESOLVE_HOST;
    if (rpath->frp_flags & FIB_ROUTE_PATH_RESOLVE_VIA_ATTACHED)
	cfg_flags |= FIB_PATH_CFG_FLAG_RESOLVE_ATTACHED;
    if (rpath->frp_flags & FIB_ROUTE_PATH_LOCAL)
	cfg_flags |= FIB_PATH_CFG_FLAG_LOCAL;

    return (cfg_flags);
}

/*
 * fib_path_create
 *
 * Create and initialise a new path object.
 * return the index of the path.
 */
fib_node_index_t
fib_path_create (fib_node_index_t pl_index,
		 fib_protocol_t nh_proto,
		 fib_path_cfg_flags_t flags,
		 const fib_route_path_t *rpath)
{
    fib_path_t *path;

    pool_get(fib_path_pool, path);
    memset(path, 0, sizeof(*path));

    fib_node_init(&path->fp_node,
		  FIB_NODE_TYPE_PATH);

    dpo_reset(&path->fp_dpo);
    path->fp_pl_index = pl_index;
    path->fp_nh_proto = nh_proto;
    path->fp_via_fib = FIB_NODE_INDEX_INVALID;
    path->fp_weight = rpath->frp_weight;
    if (0 == path->fp_weight)
    {
        /*
         * a weight of 0 is a meaningless value. We could either reject it, and thus force
         * clients to always use 1, or we can accept it and fixup approrpiately.
         */
        path->fp_weight = 1;
    }
    path->fp_cfg_flags = flags;
    path->fp_cfg_flags |= fib_path_route_flags_to_cfg_flags(rpath);

    /*
     * deduce the path's tpye from the parementers and save what is needed.
     */
    if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_LOCAL)
    {
        path->fp_type = FIB_PATH_TYPE_RECEIVE;
        path->receive.fp_interface = rpath->frp_sw_if_index;
        path->receive.fp_addr = rpath->frp_addr;
    }
    else if (~0 != rpath->frp_sw_if_index)
    {
        if (ip46_address_is_zero(&rpath->frp_addr))
        {
            path->fp_type = FIB_PATH_TYPE_ATTACHED;
            path->attached.fp_interface = rpath->frp_sw_if_index;
        }
        else
        {
            path->fp_type = FIB_PATH_TYPE_ATTACHED_NEXT_HOP;
            path->attached_next_hop.fp_interface = rpath->frp_sw_if_index;
            path->attached_next_hop.fp_nh = rpath->frp_addr;
        }
    }
    else
    {
	if (ip46_address_is_zero(&rpath->frp_addr))
	{
	    if (~0 == rpath->frp_fib_index)
	    {
		path->fp_type = FIB_PATH_TYPE_SPECIAL;
	    }
	    else
	    {
		path->fp_type = FIB_PATH_TYPE_DEAG;
		path->deag.fp_tbl_id = rpath->frp_fib_index;
	    }		
	}
	else
	{
	    path->fp_type = FIB_PATH_TYPE_RECURSIVE;
	    if (FIB_PROTOCOL_MPLS == path->fp_nh_proto)
	    {
		path->recursive.fp_nh.fp_local_label = rpath->frp_local_label;
	    }
	    else
	    {
		path->recursive.fp_nh.fp_ip = rpath->frp_addr;
	    }
	    path->recursive.fp_tbl_id = rpath->frp_fib_index;
	}
    }

    FIB_PATH_DBG(path, "create");

    return (fib_path_get_index(path));
}

/*
 * fib_path_create_special
 *
 * Create and initialise a new path object.
 * return the index of the path.
 */
fib_node_index_t
fib_path_create_special (fib_node_index_t pl_index,
			 fib_protocol_t nh_proto,
			 fib_path_cfg_flags_t flags,
			 const dpo_id_t *dpo)
{
    fib_path_t *path;

    pool_get(fib_path_pool, path);
    memset(path, 0, sizeof(*path));

    fib_node_init(&path->fp_node,
		  FIB_NODE_TYPE_PATH);
    dpo_reset(&path->fp_dpo);

    path->fp_pl_index = pl_index;
    path->fp_weight = 1;
    path->fp_nh_proto = nh_proto;
    path->fp_via_fib = FIB_NODE_INDEX_INVALID;
    path->fp_cfg_flags = flags;

    if (FIB_PATH_CFG_FLAG_DROP & flags)
    {
	path->fp_type = FIB_PATH_TYPE_SPECIAL;
    }
    else if (FIB_PATH_CFG_FLAG_LOCAL & flags)
    {
	path->fp_type = FIB_PATH_TYPE_RECEIVE;
	path->attached.fp_interface = FIB_NODE_INDEX_INVALID;
    }
    else
    {
	path->fp_type = FIB_PATH_TYPE_EXCLUSIVE;
	ASSERT(NULL != dpo);
	dpo_copy(&path->exclusive.fp_ex_dpo, dpo);
    }

    return (fib_path_get_index(path));
}

/*
 * fib_path_copy
 *
 * Copy a path. return index of new path.
 */
fib_node_index_t
fib_path_copy (fib_node_index_t path_index,
	       fib_node_index_t path_list_index)
{
    fib_path_t *path, *orig_path;

    pool_get(fib_path_pool, path);

    orig_path = fib_path_get(path_index);
    ASSERT(NULL != orig_path);

    memcpy(path, orig_path, sizeof(*path));

    FIB_PATH_DBG(path, "create-copy:%d", path_index);

    /*
     * reset the dynamic section
     */
    fib_node_init(&path->fp_node, FIB_NODE_TYPE_PATH);
    path->fp_oper_flags     = FIB_PATH_OPER_FLAG_NONE;
    path->fp_pl_index  = path_list_index;
    path->fp_via_fib   = FIB_NODE_INDEX_INVALID;
    memset(&path->fp_dpo, 0, sizeof(path->fp_dpo));
    dpo_reset(&path->fp_dpo);

    return (fib_path_get_index(path));
}

/*
 * fib_path_destroy
 *
 * destroy a path that is no longer required
 */
void
fib_path_destroy (fib_node_index_t path_index)
{
    fib_path_t *path;

    path = fib_path_get(path_index);

    ASSERT(NULL != path);
    FIB_PATH_DBG(path, "destroy");

    fib_path_unresolve(path);

    fib_node_deinit(&path->fp_node);
    pool_put(fib_path_pool, path);
}

/*
 * fib_path_destroy
 *
 * destroy a path that is no longer required
 */
uword
fib_path_hash (fib_node_index_t path_index)
{
    fib_path_t *path;

    path = fib_path_get(path_index);

    return (hash_memory(STRUCT_MARK_PTR(path, path_hash_start),
			(STRUCT_OFFSET_OF(fib_path_t, path_hash_end) -
			 STRUCT_OFFSET_OF(fib_path_t, path_hash_start)),
			0));
}

/*
 * fib_path_cmp_i
 *
 * Compare two paths for equivalence.
 */
static int
fib_path_cmp_i (const fib_path_t *path1,
		const fib_path_t *path2)
{
    int res;

    res = 1;

    /*
     * paths of different types and protocol are not equal.
     * different weights only are the same path.
     */
    if (path1->fp_type != path2->fp_type)
    {
	res = (path1->fp_type - path2->fp_type);
    }
    else if (path1->fp_nh_proto != path2->fp_nh_proto)
    {
	res = (path1->fp_nh_proto - path2->fp_nh_proto);
    }
    else
    {
	/*
	 * both paths are of the same type.
	 * consider each type and its attributes in turn.
	 */
	switch (path1->fp_type)
	{
	case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
	    res = ip46_address_cmp(&path1->attached_next_hop.fp_nh,
				   &path2->attached_next_hop.fp_nh);
	    if (0 == res) {
		res = vnet_sw_interface_compare(
			  vnet_get_main(),
			  path1->attached_next_hop.fp_interface,
			  path2->attached_next_hop.fp_interface);
	    }
	    break;
	case FIB_PATH_TYPE_ATTACHED:
	    res = vnet_sw_interface_compare(
		      vnet_get_main(),
		      path1->attached.fp_interface,
		      path2->attached.fp_interface);
	    break;
	case FIB_PATH_TYPE_RECURSIVE:
	    res = ip46_address_cmp(&path1->recursive.fp_nh,
				   &path2->recursive.fp_nh);
 
	    if (0 == res)
	    {
		res = (path1->recursive.fp_tbl_id - path2->recursive.fp_tbl_id);
	    }
	    break;
	case FIB_PATH_TYPE_DEAG:
	    res = (path1->deag.fp_tbl_id - path2->deag.fp_tbl_id);
	    break;
	case FIB_PATH_TYPE_SPECIAL:
	case FIB_PATH_TYPE_RECEIVE:
	case FIB_PATH_TYPE_EXCLUSIVE:
	    res = 0;
	    break;
	}
    }
    return (res);
}

/*
 * fib_path_cmp_for_sort
 *
 * Compare two paths for equivalence. Used during path sorting.
 * As usual 0 means equal.
 */
int
fib_path_cmp_for_sort (void * v1,
		       void * v2)
{
    fib_node_index_t *pi1 = v1, *pi2 = v2;
    fib_path_t *path1, *path2;

    path1 = fib_path_get(*pi1);
    path2 = fib_path_get(*pi2);

    return (fib_path_cmp_i(path1, path2));
}

/*
 * fib_path_cmp
 *
 * Compare two paths for equivalence.
 */
int
fib_path_cmp (fib_node_index_t pi1,
	      fib_node_index_t pi2)
{
    fib_path_t *path1, *path2;

    path1 = fib_path_get(pi1);
    path2 = fib_path_get(pi2);

    return (fib_path_cmp_i(path1, path2));
}

int
fib_path_cmp_w_route_path (fib_node_index_t path_index,
			   const fib_route_path_t *rpath)
{
    fib_path_t *path;
    int res;

    path = fib_path_get(path_index);

    res = 1;

    if (path->fp_weight != rpath->frp_weight)
    {
	res = (path->fp_weight - rpath->frp_weight);
    }
    else
    {
	/*
	 * both paths are of the same type.
	 * consider each type and its attributes in turn.
	 */
	switch (path->fp_type)
	{
	case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
	    res = ip46_address_cmp(&path->attached_next_hop.fp_nh,
				   &rpath->frp_addr);
	    if (0 == res)
	    {
		res = vnet_sw_interface_compare(
			  vnet_get_main(),
			  path->attached_next_hop.fp_interface,
			  rpath->frp_sw_if_index);
	    }
	    break;
	case FIB_PATH_TYPE_ATTACHED:
	    res = vnet_sw_interface_compare(
		      vnet_get_main(),
		      path->attached.fp_interface,
		      rpath->frp_sw_if_index);
	    break;
	case FIB_PATH_TYPE_RECURSIVE:
            if (FIB_PROTOCOL_MPLS == path->fp_nh_proto)
            {
                res = path->recursive.fp_nh.fp_local_label - rpath->frp_local_label;
            }
            else
            {
                res = ip46_address_cmp(&path->recursive.fp_nh.fp_ip,
                                       &rpath->frp_addr);
            }

            if (0 == res)
            {
                res = (path->recursive.fp_tbl_id - rpath->frp_fib_index);
            }
	    break;
	case FIB_PATH_TYPE_DEAG:
	    res = (path->deag.fp_tbl_id - rpath->frp_fib_index);
	    break;
	case FIB_PATH_TYPE_SPECIAL:
	case FIB_PATH_TYPE_RECEIVE:
	case FIB_PATH_TYPE_EXCLUSIVE:
	    res = 0;
	    break;
	}
    }
    return (res);
}

/*
 * fib_path_recursive_loop_detect
 *
 * A forward walk of the FIB object graph to detect for a cycle/loop. This
 * walk is initiated when an entry is linking to a new path list or from an old.
 * The entry vector passed contains all the FIB entrys that are children of this
 * path (it is all the entries encountered on the walk so far). If this vector
 * contains the entry this path resolve via, then a loop is about to form.
 * The loop must be allowed to form, since we need the dependencies in place
 * so that we can track when the loop breaks.
 * However, we MUST not produce a loop in the forwarding graph (else packets
 * would loop around the switch path until the loop breaks), so we mark recursive
 * paths as looped so that they do not contribute forwarding information.
 * By marking the path as looped, an etry such as;
 *    X/Y
 *     via a.a.a.a (looped)
 *     via b.b.b.b (not looped)
 * can still forward using the info provided by b.b.b.b only
 */
int
fib_path_recursive_loop_detect (fib_node_index_t path_index,
				fib_node_index_t **entry_indicies)
{
    fib_path_t *path;

    path = fib_path_get(path_index);

    /*
     * the forced drop path is never looped, cos it is never resolved.
     */
    if (fib_path_is_permanent_drop(path))
    {
	return (0);
    }

    switch (path->fp_type)
    {
    case FIB_PATH_TYPE_RECURSIVE:
    {
	fib_node_index_t *entry_index, *entries;
	int looped = 0;
	entries = *entry_indicies;

	vec_foreach(entry_index, entries) {
	    if (*entry_index == path->fp_via_fib)
	    {
		/*
		 * the entry that is about to link to this path-list (or
		 * one of this path-list's children) is the same entry that
		 * this recursive path resolves through. this is a cycle.
		 * abort the walk.
		 */
		looped = 1;
		break;
	    }
	}

	if (looped)
	{
	    FIB_PATH_DBG(path, "recursive loop formed");
	    path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RECURSIVE_LOOP;

	    dpo_copy(&path->fp_dpo,
                    drop_dpo_get(fib_proto_to_dpo(path->fp_nh_proto)));
	}
	else
	{
	    /*
	     * no loop here yet. keep forward walking the graph.
	     */	    
	    if (fib_entry_recursive_loop_detect(path->fp_via_fib, entry_indicies))
	    {
		FIB_PATH_DBG(path, "recursive loop formed");
		path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RECURSIVE_LOOP;
	    }
	    else
	    {
		FIB_PATH_DBG(path, "recursive loop cleared");
		path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RECURSIVE_LOOP;
	    }
	}
	break;
    }
    case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
    case FIB_PATH_TYPE_ATTACHED:
    case FIB_PATH_TYPE_SPECIAL:
    case FIB_PATH_TYPE_DEAG:
    case FIB_PATH_TYPE_RECEIVE:
    case FIB_PATH_TYPE_EXCLUSIVE:
	/*
	 * these path types cannot be part of a loop, since they are the leaves
	 * of the graph.
	 */
	break;
    }

    return (fib_path_is_looped(path_index));
}

int
fib_path_resolve (fib_node_index_t path_index)
{
    fib_path_t *path;

    path = fib_path_get(path_index);

    /*
     * hope for the best.
     */
    path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;

    /*
     * the forced drop path resolves via the drop adj
     */
    if (fib_path_is_permanent_drop(path))
    {
	dpo_copy(&path->fp_dpo,
                 drop_dpo_get(fib_proto_to_dpo(path->fp_nh_proto)));
	path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
	return (fib_path_is_resolved(path_index));
    }

    switch (path->fp_type)
    {
    case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
	fib_path_attached_next_hop_set(path);
	break;
    case FIB_PATH_TYPE_ATTACHED:
	/*
	 * path->attached.fp_interface
	 */
	if (!vnet_sw_interface_is_admin_up(vnet_get_main(),
					   path->attached.fp_interface))
	{
	    path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
	}
	if (vnet_sw_interface_is_p2p(vnet_get_main(),
				     path->attached.fp_interface))
	{
	    /*
	     * point-2-point interfaces do not require a glean, since
	     * there is nothing to ARP. Install a rewrite/nbr adj instead
	     */
	    dpo_set(&path->fp_dpo,
		    DPO_ADJACENCY,
		    fib_proto_to_dpo(path->fp_nh_proto),
		    adj_nbr_add_or_lock(
			path->fp_nh_proto,
			fib_proto_to_link(path->fp_nh_proto),
			&zero_addr,
			path->attached.fp_interface));
	}
	else
	{
	    dpo_set(&path->fp_dpo,
		    DPO_ADJACENCY_GLEAN,
		    fib_proto_to_dpo(path->fp_nh_proto),
		    adj_glean_add_or_lock(path->fp_nh_proto,
					  path->attached.fp_interface,
					  NULL));
	}
	/*
	 * become a child of the adjacency so we receive updates
	 * when the interface state changes
	 */
	path->fp_sibling = adj_child_add(path->fp_dpo.dpoi_index,
					 FIB_NODE_TYPE_PATH,
					 fib_path_get_index(path));

	break;
    case FIB_PATH_TYPE_RECURSIVE:
    {
	/*
	 * Create a RR source entry in the table for the address
	 * that this path recurses through.
	 * This resolve action is recursive, hence we may create
	 * more paths in the process. more creates mean maybe realloc
	 * of this path.
	 */
	fib_node_index_t fei;
	fib_prefix_t pfx;

	ASSERT(FIB_NODE_INDEX_INVALID == path->fp_via_fib);

	if (FIB_PROTOCOL_MPLS == path->fp_nh_proto)
	{
	    fib_prefix_from_mpls_label(path->recursive.fp_nh.fp_local_label, &pfx);
	}
	else
	{
	    fib_prefix_from_ip46_addr(&path->recursive.fp_nh.fp_ip, &pfx);
	}

	fei = fib_table_entry_special_add(path->recursive.fp_tbl_id,
					  &pfx,
					  FIB_SOURCE_RR,
					  FIB_ENTRY_FLAG_NONE,
					  ADJ_INDEX_INVALID);

	path = fib_path_get(path_index);
	path->fp_via_fib = fei;

	/*
	 * become a dependent child of the entry so the path is 
	 * informed when the forwarding for the entry changes.
	 */
	path->fp_sibling = fib_entry_child_add(path->fp_via_fib,
					       FIB_NODE_TYPE_PATH,
					       fib_path_get_index(path));

	/*
	 * create and configure the IP DPO
	 */
	fib_path_recursive_adj_update(
	    path,
	    fib_path_proto_to_chain_type(path->fp_nh_proto),
	    &path->fp_dpo);

	break;
    }
    case FIB_PATH_TYPE_SPECIAL:
	/*
	 * Resolve via the drop
	 */
	dpo_copy(&path->fp_dpo,
                 drop_dpo_get(fib_proto_to_dpo(path->fp_nh_proto)));
	break;
    case FIB_PATH_TYPE_DEAG:
	/*
	 * Resolve via a lookup DPO.
         * FIXME. control plane should add routes with a table ID
	 */
	lookup_dpo_add_or_lock_w_fib_index(path->deag.fp_tbl_id,
                                          fib_proto_to_dpo(path->fp_nh_proto),
                                          LOOKUP_INPUT_DST_ADDR,
                                          LOOKUP_TABLE_FROM_CONFIG,
                                          &path->fp_dpo);
	break;
    case FIB_PATH_TYPE_RECEIVE:
	/*
	 * Resolve via a receive DPO.
	 */
	receive_dpo_add_or_lock(fib_proto_to_dpo(path->fp_nh_proto),
                                path->receive.fp_interface,
                                &path->receive.fp_addr,
                                &path->fp_dpo);
	break;
    case FIB_PATH_TYPE_EXCLUSIVE:
	/*
	 * Resolve via the user provided DPO
	 */
	dpo_copy(&path->fp_dpo, &path->exclusive.fp_ex_dpo);
	break;
    }

    return (fib_path_is_resolved(path_index));
}

u32
fib_path_get_resolving_interface (fib_node_index_t path_index)
{
    fib_path_t *path;

    path = fib_path_get(path_index);

    switch (path->fp_type)
    {
    case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
	return (path->attached_next_hop.fp_interface);
    case FIB_PATH_TYPE_ATTACHED:
	return (path->attached.fp_interface);
    case FIB_PATH_TYPE_RECEIVE:
	return (path->receive.fp_interface);
    case FIB_PATH_TYPE_RECURSIVE:
	return (fib_entry_get_resolving_interface(path->fp_via_fib));    
    case FIB_PATH_TYPE_SPECIAL:
    case FIB_PATH_TYPE_DEAG:
    case FIB_PATH_TYPE_EXCLUSIVE:
	break;
    }
    return (~0);
}

adj_index_t
fib_path_get_adj (fib_node_index_t path_index)
{
    fib_path_t *path;

    path = fib_path_get(path_index);

    ASSERT(dpo_is_adj(&path->fp_dpo));
    if (dpo_is_adj(&path->fp_dpo))
    {
	return (path->fp_dpo.dpoi_index);
    }
    return (ADJ_INDEX_INVALID);
}

int
fib_path_get_weight (fib_node_index_t path_index)
{
    fib_path_t *path;

    path = fib_path_get(path_index);

    ASSERT(path);

    return (path->fp_weight);
}

/**
 * @brief Contribute the path's adjacency to the list passed.
 * By calling this function over all paths, recursively, a child
 * can construct its full set of forwarding adjacencies, and hence its
 * uRPF list.
 */
void
fib_path_contribute_urpf (fib_node_index_t path_index,
			  index_t urpf)
{
    fib_path_t *path;

    if (!fib_path_is_resolved(path_index))
	return;

    path = fib_path_get(path_index);

    switch (path->fp_type)
    {
    case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
	fib_urpf_list_append(urpf, path->attached_next_hop.fp_interface);
	break;

    case FIB_PATH_TYPE_ATTACHED:
	fib_urpf_list_append(urpf, path->attached.fp_interface);
	break;

    case FIB_PATH_TYPE_RECURSIVE:
	fib_entry_contribute_urpf(path->fp_via_fib, urpf);
	break;

    case FIB_PATH_TYPE_EXCLUSIVE:
    case FIB_PATH_TYPE_SPECIAL:
	/*
	 * these path types may link to an adj, if that's what
	 * the clinet gave
	 */
	if (dpo_is_adj(&path->fp_dpo))
	{
	    ip_adjacency_t *adj;

	    adj = adj_get(path->fp_dpo.dpoi_index);

	    fib_urpf_list_append(urpf, adj->rewrite_header.sw_if_index);
	}
	break;

    case FIB_PATH_TYPE_DEAG:
    case FIB_PATH_TYPE_RECEIVE:
	/*
	 * these path types don't link to an adj
	 */
	break;
    }
}

void
fib_path_contribute_forwarding (fib_node_index_t path_index,
				fib_forward_chain_type_t fct,
				dpo_id_t *dpo)
{
    fib_path_t *path;

    path = fib_path_get(path_index);

    ASSERT(path);
    ASSERT(FIB_FORW_CHAIN_TYPE_MPLS_EOS != fct);

    FIB_PATH_DBG(path, "contribute");

    /*
     * The DPO stored in the path was created when the path was resolved.
     * This then represents the path's 'native' protocol; IP.
     * For all others will need to go find something else.
     */
    if (fib_path_proto_to_chain_type(path->fp_nh_proto) == fct)
    {
	dpo_copy(dpo, &path->fp_dpo);
    }
    else
    {
	switch (path->fp_type)
	{
	case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
	    switch (fct)
	    {
	    case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
	    case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
	    case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
	    case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
	    case FIB_FORW_CHAIN_TYPE_ETHERNET:
	    {
		adj_index_t ai;

		/*
		 * get a appropriate link type adj.
		 */
		ai = fib_path_attached_next_hop_get_adj(
		         path,
			 fib_forw_chain_type_to_link_type(fct));
		dpo_set(dpo, DPO_ADJACENCY,
			fib_forw_chain_type_to_dpo_proto(fct), ai);
		adj_unlock(ai);

		break;
	    }
	    case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
	    case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
	    break;
            }
            break;
	case FIB_PATH_TYPE_RECURSIVE:
	    switch (fct)
	    {
	    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:
		fib_path_recursive_adj_update(path, fct, dpo);
		break;
	    case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
	    case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
	    case FIB_FORW_CHAIN_TYPE_ETHERNET:
		ASSERT(0);
		break;
	    }
	    break;
	case FIB_PATH_TYPE_DEAG:
            switch (fct)
	    {
	    case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
                lookup_dpo_add_or_lock_w_table_id(MPLS_FIB_DEFAULT_TABLE_ID,
                                                  DPO_PROTO_MPLS,
                                                  LOOKUP_INPUT_DST_ADDR,
                                                  LOOKUP_TABLE_FROM_CONFIG,
                                                  dpo);
                break;
	    case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
	    case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
	    case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
		dpo_copy(dpo, &path->fp_dpo);
		break;
	    case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
	    case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
	    case FIB_FORW_CHAIN_TYPE_ETHERNET:
		ASSERT(0);
		break;
            }
            break;
	case FIB_PATH_TYPE_EXCLUSIVE:
	    dpo_copy(dpo, &path->exclusive.fp_ex_dpo);
	    break;
        case FIB_PATH_TYPE_ATTACHED:
	    switch (fct)
	    {
	    case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
	    case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
	    case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
	    case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
	    case FIB_FORW_CHAIN_TYPE_ETHERNET:
                break;
	    case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
	    case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
                {
                    adj_index_t ai;

                    /*
                     * Create the adj needed for sending IP multicast traffic
                     */
                    ai = adj_mcast_add_or_lock(path->fp_nh_proto,
                                               fib_forw_chain_type_to_link_type(fct),
                                               path->attached.fp_interface);
                    dpo_set(dpo, DPO_ADJACENCY_MCAST,
                            fib_forw_chain_type_to_dpo_proto(fct),
                            ai);
                    adj_unlock(ai);
                }
                break;
            }
            break;
        case FIB_PATH_TYPE_RECEIVE:
        case FIB_PATH_TYPE_SPECIAL:
            dpo_copy(dpo, &path->fp_dpo);
            break;
	}
    }
}

load_balance_path_t *
fib_path_append_nh_for_multipath_hash (fib_node_index_t path_index,
				       fib_forward_chain_type_t fct,
				       load_balance_path_t *hash_key)
{
    load_balance_path_t *mnh;
    fib_path_t *path;

    path = fib_path_get(path_index);

    ASSERT(path);

    if (fib_path_is_resolved(path_index))
    {
	vec_add2(hash_key, mnh, 1);

	mnh->path_weight = path->fp_weight;
	mnh->path_index = path_index;
	fib_path_contribute_forwarding(path_index, fct, &mnh->path_dpo);
    }

    return (hash_key);
}

int
fib_path_is_recursive (fib_node_index_t path_index)
{
    fib_path_t *path;

    path = fib_path_get(path_index);

    return (FIB_PATH_TYPE_RECURSIVE == path->fp_type);
}

int
fib_path_is_exclusive (fib_node_index_t path_index)
{
    fib_path_t *path;

    path = fib_path_get(path_index);

    return (FIB_PATH_TYPE_EXCLUSIVE == path->fp_type);
}

int
fib_path_is_deag (fib_node_index_t path_index)
{
    fib_path_t *path;

    path = fib_path_get(path_index);

    return (FIB_PATH_TYPE_DEAG == path->fp_type);
}

int
fib_path_is_resolved (fib_node_index_t path_index)
{
    fib_path_t *path;

    path = fib_path_get(path_index);

    return (dpo_id_is_valid(&path->fp_dpo) &&
	    (path->fp_oper_flags & FIB_PATH_OPER_FLAG_RESOLVED) &&
	    !fib_path_is_looped(path_index) &&
	    !fib_path_is_permanent_drop(path));
}

int
fib_path_is_looped (fib_node_index_t path_index)
{
    fib_path_t *path;

    path = fib_path_get(path_index);

    return (path->fp_oper_flags & FIB_PATH_OPER_FLAG_RECURSIVE_LOOP);
}

int
fib_path_encode (fib_node_index_t path_list_index,
		 fib_node_index_t path_index,
                 void *ctx)
{
    fib_route_path_encode_t **api_rpaths = ctx;
    fib_route_path_encode_t *api_rpath;
    fib_path_t *path;

    path = fib_path_get(path_index);
    if (!path)
      return (0);
    vec_add2(*api_rpaths, api_rpath, 1);
    api_rpath->rpath.frp_weight = path->fp_weight;
    api_rpath->rpath.frp_proto = path->fp_nh_proto;
    api_rpath->rpath.frp_sw_if_index = ~0;
    api_rpath->dpo = path->exclusive.fp_ex_dpo;
    switch (path->fp_type)
      {
      case FIB_PATH_TYPE_RECEIVE:
        api_rpath->rpath.frp_addr = path->receive.fp_addr;
        api_rpath->rpath.frp_sw_if_index = path->receive.fp_interface;
        break;
      case FIB_PATH_TYPE_ATTACHED:
        api_rpath->rpath.frp_sw_if_index = path->attached.fp_interface;
        break;
      case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
        api_rpath->rpath.frp_sw_if_index = path->attached_next_hop.fp_interface;
        api_rpath->rpath.frp_addr = path->attached_next_hop.fp_nh;
        break;
      case FIB_PATH_TYPE_SPECIAL:
        break;
      case FIB_PATH_TYPE_DEAG:
        break;
      case FIB_PATH_TYPE_RECURSIVE:
        api_rpath->rpath.frp_addr = path->recursive.fp_nh.fp_ip;
        break;
      default:
        break;
      }
    return (1);
}

fib_protocol_t
fib_path_get_proto (fib_node_index_t path_index)
{
    fib_path_t *path;

    path = fib_path_get(path_index);

    return (path->fp_nh_proto);
}

void
fib_path_module_init (void)
{
    fib_node_register_type (FIB_NODE_TYPE_PATH, &fib_path_vft);
}

static clib_error_t *
show_fib_path_command (vlib_main_t * vm,
			unformat_input_t * input,
			vlib_cli_command_t * cmd)
{
    fib_node_index_t pi;
    fib_path_t *path;

    if (unformat (input, "%d", &pi))
    {
	/*
	 * show one in detail
	 */
	if (!pool_is_free_index(fib_path_pool, pi))
	{
	    path = fib_path_get(pi);
	    u8 *s = fib_path_format(pi, NULL);
	    s = format(s, "children:");
	    s = fib_node_children_format(path->fp_node.fn_children, s);
	    vlib_cli_output (vm, "%s", s);
	    vec_free(s);
	}
	else
	{
	    vlib_cli_output (vm, "path %d invalid", pi);
	}
    }
    else
    {
	vlib_cli_output (vm, "FIB Paths");
	pool_foreach(path, fib_path_pool,
	({
	    vlib_cli_output (vm, "%U", format_fib_path, path);
	}));
    }

    return (NULL);
}

VLIB_CLI_COMMAND (show_fib_path, static) = {
  .path = "show fib paths",
  .function = show_fib_path_command,
  .short_help = "show fib paths",
};