FD.io VPP  v19.01.3-6-g70449b9b9
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 {
80  return (pool_elt_at_index(fib_node_list_elt_pool, fi));
81 }
82 
83 static index_t
85 {
86  return (head - fib_node_list_head_pool);
87 }
88 static fib_node_list_head_t *
90 {
91  return (pool_elt_at_index(fib_node_list_head_pool, fi));
92 }
93 
94 static fib_node_list_elt_t *
96  int id,
97  fib_node_type_t type,
98  fib_node_index_t index)
99 {
100  fib_node_list_elt_t *elt;
101 
102  pool_get(fib_node_list_elt_pool, elt);
103 
105  elt->fnle_owner.fnp_type = type;
106  elt->fnle_owner.fnp_index = index;
107 
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 
129  pool_get(fib_node_list_head_pool, head);
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 
147  pool_put(fib_node_list_head_pool, head);
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,
158  fib_node_type_t type,
159  fib_node_index_t index)
160 {
161  fib_node_list_elt_t *elt, *next;
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 
168  elt->fnle_next = head->fnlh_head;
169 
170  if (FIB_NODE_INDEX_INVALID != head->fnlh_head)
171  {
172  next = fib_node_list_elt_get(head->fnlh_head);
174  }
176 
177  head->fnlh_n_elts++;
178 
179  return (fib_node_list_elt_get_index(elt));
180 }
181 
182 u32
184  int owner_id,
185  fib_node_type_t type,
186  fib_node_index_t index)
187 {
188  ASSERT(0);
189  return (FIB_NODE_INDEX_INVALID);
190 }
191 
192 static void
194  fib_node_list_elt_t *elt)
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,
219  fib_node_list_elt_t *elt)
220 {
221  fib_node_list_elt_t *next;
222 
223  elt->fnle_next = prev->fnle_next;
224  if (FIB_NODE_INDEX_INVALID != prev->fnle_next)
225  {
226  next = fib_node_list_elt_get(prev->fnle_next);
228  }
231 }
232 
233 void
235  u32 sibling)
236 {
237  fib_node_list_head_t *head;
238  fib_node_list_elt_t *elt;
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--;
246  pool_put(fib_node_list_elt_pool, elt);
247 }
248 
249 void
251 {
252  fib_node_list_elt_t *elt;
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 {
266  fib_node_list_elt_t *elt, *next;
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);
280  fib_node_list_insert_after(head, next, elt);
281 
282  return (1);
283  }
284  else
285  {
286  return (0);
287  }
288 }
289 
290 int
292  fib_node_ptr_t *ptr)
293 {
294  fib_node_list_elt_t *elt, *next;
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;
332  fib_node_list_elt_t *elt;
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);
342  elt = fib_node_list_elt_get(head->fnlh_head);
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 {
358  fib_node_list_elt_t *elt;
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  fn(&elt->fnle_owner, args);
376  }
377 }
378 
379 void
381 {
382  fib_show_memory_usage("Node-list elements",
383  pool_elts(fib_node_list_elt_pool),
384  pool_len(fib_node_list_elt_pool),
385  sizeof(fib_node_list_elt_t));
386  fib_show_memory_usage("Node-list heads",
387  pool_elts(fib_node_list_head_pool),
388  pool_len(fib_node_list_head_pool),
389  sizeof(fib_node_list_head_t));
390 }
void fib_node_list_elt_remove(u32 sibling)
static fib_node_list_head_t * fib_node_list_head_get(fib_node_list_t fi)
Definition: fib_node_list.c:89
static index_t fib_node_list_head_get_index(fib_node_list_head_t *head)
Definition: fib_node_list.c:84
static index_t fib_node_list_elt_get_index(fib_node_list_elt_t *elt)
Definition: fib_node_list.c:72
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:41
void fib_node_list_memory_show(void)
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:236
void fib_node_list_walk(fib_node_list_t list, fib_node_list_walk_cb_t fn, void *args)
Walk the list of node.
#define pool_len(p)
Number of elements in pool vector.
Definition: pool.h:140
fib_node_index_t fnp_index
node&#39;s index
Definition: fib_node.h:193
void fib_node_list_remove(fib_node_list_t list, u32 sibling)
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
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
unsigned int u32
Definition: types.h:88
A representation of one pointer to another node.
Definition: fib_node.h:185
fib_node_ptr_t fnle_owner
The owner of this element.
Definition: fib_node_list.c:36
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:511
fib_node_type_t fnp_type
node type
Definition: fib_node.h:189
struct fib_node_list_head_t_ fib_node_list_head_t
A list of FIB nodes.
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:286
u32 fib_node_list_push_back(fib_node_list_t list, int owner_id, fib_node_type_t type, fib_node_index_t index)
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.
int(* 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
int fib_node_list_advance(u32 sibling)
Advance the sibling one step (toward the tail) in the list.
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)
static fib_node_list_elt_t * fib_node_list_elt_get(index_t fi)
Definition: fib_node_list.c:78
A list of FIB nodes.
Definition: fib_node_list.c:52
u32 fnle_next
The next element in the list.
Definition: fib_node_list.c:41
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:30
static fib_node_list_head_t * fib_node_list_head_pool
Definition: fib_node_list.c:69
u32 fnlh_head
The head element.
Definition: fib_node_list.c:57
u32 fib_node_list_get_size(fib_node_list_t list)
#define ASSERT(truth)
fib_node_list_t fib_node_list_create(void)
Create a new node list.
void fib_node_list_destroy(fib_node_list_t *list)
static fib_node_list_elt_t * fib_node_list_elt_pool
Pools of list elements and heads.
Definition: fib_node_list.c:68
int fib_node_list_get_front(fib_node_list_t list, fib_node_ptr_t *ptr)
static void fib_node_list_head_init(fib_node_list_head_t *head)
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:31
struct fib_node_list_elt_t_ fib_node_list_elt_t
a hetrogeneous w.r.t.
fib_node_list_t fnle_list
The index of the list this element is in.
Definition: fib_node_list.c:31
u32 fnlh_n_elts
Number of elements in the list.
Definition: fib_node_list.c:62
enum fib_node_type_t_ fib_node_type_t
The types of nodes in a FIB graph.
u32 fib_node_list_t
A list of FIB nodes.
Definition: fib_node.h:199
static void fib_node_list_extract(fib_node_list_head_t *head, fib_node_list_elt_t *elt)
int fib_node_list_elt_get_next(u32 sibling, fib_node_ptr_t *ptr)
u32 fnle_prev
The previous element in the list.
Definition: fib_node_list.c:46
a hetrogeneous w.r.t.
Definition: fib_node_list.c:26
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:128