FD.io VPP  v21.06-3-gbb25fbf28
Vector Packet Processing
fib_node_list.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2016 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 /**
16  * @brief a hetrogeneous w.r.t. FIB node type, of FIB nodes.
17  * Since we cannot use C pointers, due to memeory reallocs, the next/prev
18  * are described as key:{type,index}.
19  */
20 
21 #include <vnet/fib/fib_node_list.h>
22 
23 /**
24  * @brief An element in the list
25  */
26 typedef struct fib_node_list_elt_t_
27 {
28  /**
29  * The index of the list this element is in
30  */
32 
33  /**
34  * The owner of this element
35  */
37 
38  /**
39  * The next element in the list
40  */
42 
43  /**
44  * The previous element in the list
45  */
48 
49 /**
50  * @brief A list of FIB nodes
51  */
52 typedef struct fib_node_list_head_t_
53 {
54  /**
55  * The head element
56  */
58 
59  /**
60  * Number of elements in the list
61  */
64 
65 /**
66  * Pools of list elements and heads
67  */
70 
71 static index_t
73 {
74  return (elt - fib_node_list_elt_pool);
75 }
76 
77 static fib_node_list_elt_t *
79 {
81 }
82 
83 static index_t
85 {
86  return (head - fib_node_list_head_pool);
87 }
88 static fib_node_list_head_t *
90 {
92 }
93 
94 static fib_node_list_elt_t *
96  int id,
99 {
101 
103 
104  elt->fnle_list = fib_node_list_head_get_index(head);
105  elt->fnle_owner.fnp_type = type;
106  elt->fnle_owner.fnp_index = index;
107 
108  elt->fnle_next = FIB_NODE_INDEX_INVALID;
109  elt->fnle_prev = FIB_NODE_INDEX_INVALID;
110 
111  return (elt);
112 }
113 
114 static void
116 {
117  head->fnlh_n_elts = 0;
119 }
120 
121 /**
122  * @brief Create a new node list.
123  */
126 {
127  fib_node_list_head_t *head;
128 
130 
132 
133  return (fib_node_list_head_get_index(head));
134 }
135 
136 void
138 {
139  fib_node_list_head_t *head;
140 
141  if (FIB_NODE_INDEX_INVALID == *list)
142  return;
143 
144  head = fib_node_list_head_get(*list);
145  ASSERT(0 == head->fnlh_n_elts);
146 
148  *list = FIB_NODE_INDEX_INVALID;
149 }
150 
151 
152 /**
153  * @brief Insert an element at the from of the list.
154  */
155 u32
157  int owner_id,
160 {
162  fib_node_list_head_t *head;
163 
164  head = fib_node_list_head_get(list);
165  elt = fib_node_list_elt_create(head, owner_id, type, index);
166 
167  elt->fnle_prev = FIB_NODE_INDEX_INVALID;
168  elt->fnle_next = head->fnlh_head;
169 
170  if (FIB_NODE_INDEX_INVALID != head->fnlh_head)
171  {
173  next->fnle_prev = fib_node_list_elt_get_index(elt);
174  }
176 
177  head->fnlh_n_elts++;
178 
180 }
181 
182 u32
184  int owner_id,
187 {
188  ASSERT(0);
189  return (FIB_NODE_INDEX_INVALID);
190 }
191 
192 static void
195 {
196  fib_node_list_elt_t *next, *prev;
197 
198  if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
199  {
200  next = fib_node_list_elt_get(elt->fnle_next);
201  next->fnle_prev = elt->fnle_prev;
202  }
203 
204  if (FIB_NODE_INDEX_INVALID != elt->fnle_prev)
205  {
206  prev = fib_node_list_elt_get(elt->fnle_prev);
207  prev->fnle_next = elt->fnle_next;
208  }
209  else
210  {
212  head->fnlh_head = elt->fnle_next;
213  }
214 }
215 
216 static void
218  fib_node_list_elt_t *prev,
220 {
222 
223  elt->fnle_next = prev->fnle_next;
224  if (FIB_NODE_INDEX_INVALID != prev->fnle_next)
225  {
227  next->fnle_prev = fib_node_list_elt_get_index(elt);
228  }
230  elt->fnle_prev = fib_node_list_elt_get_index(prev);
231 }
232 
233 void
235  u32 sibling)
236 {
237  fib_node_list_head_t *head;
239 
240  head = fib_node_list_head_get(list);
241  elt = fib_node_list_elt_get(sibling);
242 
243  fib_node_list_extract(head, elt);
244 
245  head->fnlh_n_elts--;
247 }
248 
249 void
251 {
253 
254  elt = fib_node_list_elt_get(sibling);
255 
256  fib_node_list_remove(elt->fnle_list, sibling);
257 }
258 
259 /**
260  * @brief Advance the sibling one step (toward the tail) in the list.
261  * return 0 if at the end of the list, 1 otherwise.
262  */
263 int
265 {
267  fib_node_list_head_t *head;
268 
269  elt = fib_node_list_elt_get(sibling);
270  head = fib_node_list_head_get(elt->fnle_list);
271 
272  if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
273  {
274  /*
275  * not at the end of the list
276  */
277  next = fib_node_list_elt_get(elt->fnle_next);
278 
279  fib_node_list_extract(head, elt);
281 
282  return (1);
283  }
284  else
285  {
286  return (0);
287  }
288 }
289 
290 int
292  fib_node_ptr_t *ptr)
293 {
295 
296  elt = fib_node_list_elt_get(sibling);
297 
298  if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
299  {
300  next = fib_node_list_elt_get(elt->fnle_next);
301 
302  *ptr = next->fnle_owner;
303  return (1);
304  }
305  else
306  {
308  return (0);
309  }
310 }
311 
312 u32
314 {
315  fib_node_list_head_t *head;
316 
317  if (FIB_NODE_INDEX_INVALID == list)
318  {
319  return (0);
320  }
321 
322  head = fib_node_list_head_get(list);
323 
324  return (head->fnlh_n_elts);
325 }
326 
327 int
329  fib_node_ptr_t *ptr)
330 {
331  fib_node_list_head_t *head;
333 
334 
335  if (0 == fib_node_list_get_size(list))
336  {
338  return (0);
339  }
340 
341  head = fib_node_list_head_get(list);
343 
344  *ptr = elt->fnle_owner;
345 
346  return (1);
347 }
348 
349 /**
350  * @brief Walk the list of node. This must be safe w.r.t. the removal
351  * of nodes during the walk.
352  */
353 void
356  void *args)
357 {
359  fib_node_list_head_t *head;
360  u32 sibling;
361 
362  if (FIB_NODE_INDEX_INVALID == list)
363  {
364  return;
365  }
366 
367  head = fib_node_list_head_get(list);
368  sibling = head->fnlh_head;
369 
370  while (FIB_NODE_INDEX_INVALID != sibling)
371  {
372  elt = fib_node_list_elt_get(sibling);
373  sibling = elt->fnle_next;
374 
375  if (WALK_STOP == fn(&elt->fnle_owner, args))
376  break;
377  }
378 }
379 
380 void
382 {
383  fib_show_memory_usage("Node-list elements",
386  sizeof(fib_node_list_elt_t));
387  fib_show_memory_usage("Node-list heads",
390  sizeof(fib_node_list_head_t));
391 }
fib_node_list_elt_t_::fnle_prev
u32 fnle_prev
The previous element in the list.
Definition: fib_node_list.c:46
fib_node_list_elt_pool
static fib_node_list_elt_t * fib_node_list_elt_pool
Pools of list elements and heads.
Definition: fib_node_list.c:68
pool_elt_at_index
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:553
fib_node_list_t
u32 fib_node_list_t
A list of FIB nodes.
Definition: fib_node.h:209
next
u16 * next
Definition: nat44_ei_out2in.c:718
FIB_NODE_INDEX_INVALID
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:30
fib_node_list_elt_create
static fib_node_list_elt_t * fib_node_list_elt_create(fib_node_list_head_t *head, int id, fib_node_type_t type, fib_node_index_t index)
Definition: fib_node_list.c:95
fib_node_list_head_t
struct fib_node_list_head_t_ fib_node_list_head_t
A list of FIB nodes.
fib_node_list_head_pool
static fib_node_list_head_t * fib_node_list_head_pool
Definition: fib_node_list.c:69
fib_node_list_insert_after
static void fib_node_list_insert_after(fib_node_list_head_t *head, fib_node_list_elt_t *prev, fib_node_list_elt_t *elt)
Definition: fib_node_list.c:217
pool_put
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:305
fib_node_list_memory_show
void fib_node_list_memory_show(void)
Definition: fib_node_list.c:381
fib_node_list_push_back
u32 fib_node_list_push_back(fib_node_list_t list, int owner_id, fib_node_type_t type, fib_node_index_t index)
Definition: fib_node_list.c:183
fib_node_type_t
enum fib_node_type_t_ fib_node_type_t
The types of nodes in a FIB graph.
fib_node_list_elt_get
static fib_node_list_elt_t * fib_node_list_elt_get(index_t fi)
Definition: fib_node_list.c:78
fib_node_list_head_t_::fnlh_n_elts
u32 fnlh_n_elts
Number of elements in the list.
Definition: fib_node_list.c:62
fib_node_list_head_get
static fib_node_list_head_t * fib_node_list_head_get(fib_node_list_t fi)
Definition: fib_node_list.c:89
fib_node_list_get_front
int fib_node_list_get_front(fib_node_list_t list, fib_node_ptr_t *ptr)
Definition: fib_node_list.c:328
fib_node_list_head_t_
A list of FIB nodes.
Definition: fib_node_list.c:52
index_t
u32 index_t
A Data-Path Object is an object that represents actions that are applied to packets are they are swit...
Definition: dpo.h:43
fib_node_list_head_get_index
static index_t fib_node_list_head_get_index(fib_node_list_head_t *head)
Definition: fib_node_list.c:84
fib_node_index_t
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:29
fib_node_list_head_t_::fnlh_head
u32 fnlh_head
The head element.
Definition: fib_node_list.c:57
fib_show_memory_usage
void fib_show_memory_usage(const char *name, u32 in_use_elts, u32 allocd_elts, size_t size_elt)
Show the memory usage for a type.
Definition: fib_node.c:220
fib_node_list_walk_cb_t
walk_rc_t(* fib_node_list_walk_cb_t)(fib_node_ptr_t *owner, void *args)
Callback function invoked during a list walk.
Definition: fib_node_list.h:55
fib_node_list_elt_t_::fnle_owner
fib_node_ptr_t fnle_owner
The owner of this element.
Definition: fib_node_list.c:36
pool_get
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:255
fib_node_list_elt_get_index
static index_t fib_node_list_elt_get_index(fib_node_list_elt_t *elt)
Definition: fib_node_list.c:72
fib_node_list_elt_t
struct fib_node_list_elt_t_ fib_node_list_elt_t
a hetrogeneous w.r.t.
fib_node_list_advance
int fib_node_list_advance(u32 sibling)
Advance the sibling one step (toward the tail) in the list.
Definition: fib_node_list.c:264
fib_node_ptr_t_
A representation of one pointer to another node.
Definition: fib_node.h:195
fib_node_ptr_t_::fnp_index
fib_node_index_t fnp_index
node's index
Definition: fib_node.h:203
pool_len
#define pool_len(p)
Number of elements in pool vector.
Definition: pool.h:139
index
u32 index
Definition: flow_types.api:221
fib_node_list_elt_t_
a hetrogeneous w.r.t.
Definition: fib_node_list.c:26
ASSERT
#define ASSERT(truth)
Definition: error_bootstrap.h:69
u32
unsigned int u32
Definition: types.h:88
fib_node_list_elt_remove
void fib_node_list_elt_remove(u32 sibling)
Definition: fib_node_list.c:250
fib_node_list_remove
void fib_node_list_remove(fib_node_list_t list, u32 sibling)
Definition: fib_node_list.c:234
fib_node_list_get_size
u32 fib_node_list_get_size(fib_node_list_t list)
Definition: fib_node_list.c:313
fib_node_list_walk
void fib_node_list_walk(fib_node_list_t list, fib_node_list_walk_cb_t fn, void *args)
Walk the list of node.
Definition: fib_node_list.c:354
pool_elts
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:127
elt
app_rx_mq_elt_t * elt
Definition: application.c:488
fib_node_list_push_front
u32 fib_node_list_push_front(fib_node_list_t list, int owner_id, fib_node_type_t type, fib_node_index_t index)
Insert an element at the from of the list.
Definition: fib_node_list.c:156
fib_node_list_create
fib_node_list_t fib_node_list_create(void)
Create a new node list.
Definition: fib_node_list.c:125
fib_node_list_elt_t_::fnle_list
fib_node_list_t fnle_list
The index of the list this element is in.
Definition: fib_node_list.c:31
fib_node_list_extract
static void fib_node_list_extract(fib_node_list_head_t *head, fib_node_list_elt_t *elt)
Definition: fib_node_list.c:193
fib_node_list_destroy
void fib_node_list_destroy(fib_node_list_t *list)
Definition: fib_node_list.c:137
fib_node_list.h
fib_node_list_elt_t_::fnle_next
u32 fnle_next
The next element in the list.
Definition: fib_node_list.c:41
fib_node_list_head_init
static void fib_node_list_head_init(fib_node_list_head_t *head)
Definition: fib_node_list.c:115
fib_node_list_elt_get_next
int fib_node_list_elt_get_next(u32 sibling, fib_node_ptr_t *ptr)
Definition: fib_node_list.c:291
WALK_STOP
@ WALK_STOP
Definition: interface_funcs.h:173
type
vl_api_fib_path_type_t type
Definition: fib_types.api:123