FD.io VPP  v17.04-9-g99c0734
Vector Packet Processing
slist.c
Go to the documentation of this file.
1 /*
2  Copyright (c) 2012 Cisco and/or its affiliates.
3 
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at:
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15 */
16 
17 #include <vppinfra/slist.h>
18 
19 /*
20  * skip-list implementation
21  *
22  * Good news / bad news. As balanced binary tree schemes go,
23  * this one seems pretty fast and is reasonably simple. There's a very
24  * limited amount that can be done to mitigate sdram read latency.
25  *
26  * Each active clib_slist_elt_t is on from 1 to N lists. Each active element
27  * is always on the "level-0" list. Since most elements are *only* on
28  * level 0, we keep the level 0 (and level 1) in the element. For those
29  * elements on more than two lists, we switch to a vector. Hence, the
30  * "n" union in slib_slist_elt_t.
31  *
32  * The low-order bit of elt->n.next0[0] is 1 for inlined next indices,
33  * 0 for vector indices (since the allocator always aligns to at least
34  * a 4-byte boundary). We can only represent 2e9 items, but since the
35  * practical performance limit is O(1e7), it doesn't matter.
36  *
37  * We create a "head" element which (by construction) is always
38  * lexically lighter than any other element. This makes a large number
39  * of irritating special cases go away.
40  *
41  * User code is in charge of comparing a supplied key with
42  * the key component of a user pool element. The user tells this code
43  * to add or delete (opaque key, 32-bit integer) pairs to the skip-list.
44  *
45  * The algorithm adds new elements to one or more lists.
46  * For levels greater than zero, the probability of a new element landing on
47  * a list is branching_factor**N. Branching_factor = 0.2 seems to work
48  * OK, yielding about 50 compares per search at O(1e7) items.
49  */
50 
52 clib_slist_init (clib_slist_t * sp, f64 branching_factor,
54  format_function_t format_user_element)
55 {
56  clib_slist_elt_t *head;
57  memset (sp, 0, sizeof (sp[0]));
58  sp->branching_factor = branching_factor;
59  sp->format_user_element = format_user_element;
60  sp->compare = compare;
61  sp->seed = 0xdeaddabe;
62  pool_get (sp->elts, head);
63  vec_add1 (head->n.nexts, (u32) ~ 0);
64  head->user_pool_index = (u32) ~ 0;
65  vec_validate (sp->path, 1);
66  vec_validate (sp->occupancy, 0);
67 
68  return 0;
69 }
70 
71 /*
72  * slist_search_internal
73  */
74 static inline clib_slist_search_result_t
75 slist_search_internal (clib_slist_t * sp, void *key, int need_full_path)
76 {
77  int level, comp_result;
78  clib_slist_elt_t *search_elt, *head_elt;
79 
80  sp->ncompares = 0;
81  /*
82  * index 0 is the magic listhead element which is
83  * lexically lighter than / to the left of every element
84  */
85  search_elt = head_elt = pool_elt_at_index (sp->elts, 0);
86 
87  /*
88  * Initial negotiating position, only the head_elt is
89  * lighter than the supplied key
90  */
91  memset (sp->path, 0, vec_len (head_elt->n.nexts) * sizeof (u32));
92 
93  /* Walk the fastest lane first */
94  level = vec_len (head_elt->n.nexts) - 1;
95  _vec_len (sp->path) = level + 1;
96 
97  while (1)
98  {
99  u32 next_index_this_level;
100  clib_slist_elt_t *prefetch_elt;
101 
102  /*
103  * Prefetching the next element at this level makes a measurable
104  * difference, but doesn't fix the dependent read stall problem
105  */
106  prefetch_elt = sp->elts +
107  clib_slist_get_next_at_level (search_elt, level);
108 
109  CLIB_PREFETCH (prefetch_elt, CLIB_CACHE_LINE_BYTES, READ);
110 
111  /* Compare the key with the current element */
112  comp_result = (search_elt == head_elt) ? 1 :
113  sp->compare (key, search_elt->user_pool_index);
114 
115  sp->ncompares++;
116  /* key "lighter" than this element */
117  if (comp_result < 0)
118  {
119  /*
120  * Back up to previous item on this list
121  * and search the next finer-grained list
122  * starting there.
123  */
124  search_elt = pool_elt_at_index (sp->elts, sp->path[level]);
125  next_list:
126  if (level > 0)
127  {
128  level--;
129  continue;
130  }
131  else
132  {
133  return CLIB_SLIST_NO_MATCH;
134  }
135  }
136  /* Match */
137  if (comp_result == 0)
138  {
139  /*
140  * If we're trying to delete an element, we need to
141  * track down all of the elements which point at it.
142  * Otherwise, don't bother with it
143  */
144  if (need_full_path && level > 0)
145  {
146  search_elt = pool_elt_at_index (sp->elts, sp->path[level]);
147  level--;
148  continue;
149  }
150  level = vec_len (head_elt->n.nexts);
151  sp->path[level] = search_elt - sp->elts;
152  _vec_len (sp->path) = level + 1;
153  return CLIB_SLIST_MATCH;
154  }
155  /*
156  * comp_result positive, key is to the right of
157  * this element
158  */
159  sp->path[level] = search_elt - sp->elts;
160 
161  /* Out of list at this level? */
162  next_index_this_level =
163  clib_slist_get_next_at_level (search_elt, level);
164  if (next_index_this_level == (u32) ~ 0)
165  goto next_list;
166 
167  /* No, try the next element */
168  search_elt = pool_elt_at_index (sp->elts, next_index_this_level);
169  }
170  return 0; /* notreached */
171 }
172 
173 u32
174 clib_slist_search (clib_slist_t * sp, void *key, u32 * ncompares)
175 {
177 
178  rv = slist_search_internal (sp, key, 0 /* dont need full path */ );
179  if (rv == CLIB_SLIST_MATCH)
180  {
181  clib_slist_elt_t *elt;
182  elt = pool_elt_at_index (sp->elts, sp->path[vec_len (sp->path) - 1]);
183  if (ncompares)
184  *ncompares = sp->ncompares;
185  return elt->user_pool_index;
186  }
187  return (u32) ~ 0;
188 }
189 
190 void
191 clib_slist_add (clib_slist_t * sp, void *key, u32 user_pool_index)
192 {
193  clib_slist_elt_t *new_elt;
194  clib_slist_search_result_t search_result;
195  int level;
196 
197  search_result = slist_search_internal (sp, key,
198  0 /* don't need full path */ );
199 
200  /* Special case: key exists, just replace user_pool_index */
201  if (PREDICT_FALSE (search_result == CLIB_SLIST_MATCH))
202  {
203  clib_slist_elt_t *elt;
204  elt = pool_elt_at_index (sp->elts, sp->path[0]);
205  elt->user_pool_index = user_pool_index;
206  return;
207  }
208 
209  pool_get (sp->elts, new_elt);
210  new_elt->n.nexts = 0;
211  new_elt->user_pool_index = user_pool_index;
212 
213  /* sp->path lists elements to the left of key, by level */
214  for (level = 0; level < vec_len (sp->path); level++)
215  {
216  clib_slist_elt_t *prev_elt_this_level;
217  u32 prev_elt_next_index_this_level;
218 
219  /* Add to list at the current level */
220  prev_elt_this_level = pool_elt_at_index (sp->elts, sp->path[level]);
221  prev_elt_next_index_this_level = clib_slist_get_next_at_level
222  (prev_elt_this_level, level);
223 
224  clib_slist_set_next_at_level (new_elt, prev_elt_next_index_this_level,
225  level);
226 
227  clib_slist_set_next_at_level (prev_elt_this_level, new_elt - sp->elts,
228  level);
229  sp->occupancy[level]++;
230 
231  /* Randomly add to the next-higher level */
232  if (random_f64 (&sp->seed) > sp->branching_factor)
233  break;
234  }
235  {
236  /* Time to add a new ply? */
237  clib_slist_elt_t *head_elt = pool_elt_at_index (sp->elts, 0);
238  int top_level = vec_len (head_elt->n.nexts) - 1;
239  if (((f64) sp->occupancy[top_level]) * sp->branching_factor > 1.0)
240  {
241  vec_add1 (sp->occupancy, 0);
242  vec_add1 (head_elt->n.nexts, (u32) ~ 0);
243  /* full match case returns n+1 items */
244  vec_validate (sp->path, vec_len (head_elt->n.nexts));
245  }
246  }
247 }
248 
250 clib_slist_del (clib_slist_t * sp, void *key)
251 {
252  clib_slist_search_result_t search_result;
253  clib_slist_elt_t *del_elt;
254  int level;
255 
256  search_result = slist_search_internal (sp, key, 1 /* need full path */ );
257 
258  if (PREDICT_FALSE (search_result == CLIB_SLIST_NO_MATCH))
259  return search_result;
260 
261  del_elt = pool_elt_at_index (sp->elts, sp->path[vec_len (sp->path) - 1]);
262  ASSERT (vec_len (sp->path) > 1);
263 
264  for (level = 0; level < vec_len (sp->path) - 1; level++)
265  {
266  clib_slist_elt_t *path_elt;
267  u32 path_elt_next_index;
268 
269  path_elt = pool_elt_at_index (sp->elts, sp->path[level]);
270  path_elt_next_index = clib_slist_get_next_at_level (path_elt, level);
271 
272  /* Splice the item out of the list if it's adjacent to the victim */
273  if (path_elt_next_index == del_elt - sp->elts)
274  {
275  sp->occupancy[level]--;
276  path_elt_next_index = clib_slist_get_next_at_level (del_elt, level);
277  clib_slist_set_next_at_level (path_elt, path_elt_next_index, level);
278  }
279  }
280 
281  /* If this element is on more than two lists it has a vector of nexts */
282  if (!(del_elt->n.next0[0] & 1))
283  vec_free (del_elt->n.nexts);
284  pool_put (sp->elts, del_elt);
285  return CLIB_SLIST_MATCH;
286 }
287 
288 u8 *
289 format_slist (u8 * s, va_list * args)
290 {
291  clib_slist_t *sl = va_arg (*args, clib_slist_t *);
292  int verbose = va_arg (*args, int);
293  int i;
294  clib_slist_elt_t *head_elt, *elt;
295 
296  s = format (s, "slist 0x%x, %u items, branching_factor %.2f\n", sl,
297  sl->occupancy ? sl->occupancy[0] : 0, sl->branching_factor);
298 
299  if (pool_elts (sl->elts) == 0)
300  return s;
301 
302  head_elt = pool_elt_at_index (sl->elts, 0);
303 
304  for (i = 0; i < vec_len (head_elt->n.nexts); i++)
305  {
306  s = format (s, "level %d: %d elts\n", i,
307  sl->occupancy ? sl->occupancy[i] : 0);
308 
309  if (verbose && head_elt->n.nexts[i] != (u32) ~ 0)
310  {
311  elt = pool_elt_at_index (sl->elts, head_elt->n.nexts[i]);
312  while (elt)
313  {
314  u32 next_index;
315  s = format (s, "%U(%d) ", sl->format_user_element,
316  elt->user_pool_index, elt - sl->elts);
317  next_index = clib_slist_get_next_at_level (elt, i);
318  ASSERT (next_index != 0x7fffffff);
319  if (next_index == (u32) ~ 0)
320  break;
321  else
322  elt = pool_elt_at_index (sl->elts, next_index);
323  }
324  }
325  s = format (s, "\n");
326  }
327  return s;
328 }
329 
330 /*
331  * fd.io coding-style-patch-verification: ON
332  *
333  * Local Variables:
334  * eval: (c-set-style "gnu")
335  * End:
336  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:436
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
word( clib_slist_key_compare_function_t)(void *key, u32 elt_pool_index)
Definition: slist.h:29
f64 branching_factor
Definition: slist.h:121
clib_error_t * clib_slist_init(clib_slist_t *sp, f64 branching_factor, clib_slist_key_compare_function_t compare, format_function_t format_user_element)
Definition: slist.c:52
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:522
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:418
u8 *( format_function_t)(u8 *s, va_list *args)
Definition: format.h:48
clib_slist_key_compare_function_t * compare
Definition: slist.h:115
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:200
u32 * occupancy
Definition: slist.h:112
clib_slist_elt_t * elts
Definition: slist.h:103
clib_slist_search_result_t
Definition: slist.h:31
u32 next0[2]
Definition: slist.h:42
static u32 clib_slist_get_next_at_level(clib_slist_elt_t *elt, int level)
Definition: slist.h:52
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:397
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:241
#define PREDICT_FALSE(x)
Definition: clib.h:97
static clib_slist_search_result_t slist_search_internal(clib_slist_t *sp, void *key, int need_full_path)
Definition: slist.c:75
format_function_t * format_user_element
Definition: slist.h:118
#define CLIB_PREFETCH(addr, size, type)
Definition: cache.h:82
u8 * format_slist(u8 *s, va_list *args)
Definition: slist.c:289
u32 * nexts
Definition: slist.h:43
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:340
void clib_slist_add(clib_slist_t *sp, void *key, u32 user_pool_index)
Definition: slist.c:191
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
static void clib_slist_set_next_at_level(clib_slist_elt_t *elt, u32 index, int level)
Definition: slist.h:71
u32 * path
Definition: slist.h:106
u32 clib_slist_search(clib_slist_t *sp, void *key, u32 *ncompares)
Definition: slist.c:174
static f64 random_f64(u32 *seed)
Generate f64 random number in the interval [0,1].
Definition: random.h:145
u32 user_pool_index
Definition: slist.h:47
clib_slist_search_result_t clib_slist_del(clib_slist_t *sp, void *key)
Definition: slist.c:250
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
double f64
Definition: types.h:142
unsigned char u8
Definition: types.h:56
u32 ncompares
Definition: slist.h:109
u32 seed
Definition: slist.h:124
union clib_slist_elt_t::@21 n
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:67
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:109