vppinfra/vppinfra/slist.c

   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
  51 clib_error_t *
  52 clib_slist_init (clib_slist_t *sp, f64 branching_factor,
  53                  clib_slist_key_compare_function_t compare,
  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 = clib_slist_get_next_at_level (search_elt, level);
 163       if (next_index_this_level == (u32)~0)
 164         goto next_list;
 165
 166       /* No, try the next element */
 167       search_elt = pool_elt_at_index (sp->elts, next_index_this_level);
 168     }
 169   return 0; /* notreached */
 170 }
 171
 172 u32 clib_slist_search (clib_slist_t *sp, void *key, u32 *ncompares)
 173 {
 174   clib_slist_search_result_t rv;
 175
 176   rv = slist_search_internal (sp, key, 0 /* dont need full path */);
 177   if (rv == CLIB_SLIST_MATCH)
 178     {
 179       clib_slist_elt_t *elt;
 180       elt = pool_elt_at_index (sp->elts, sp->path[vec_len(sp->path)-1]);
 181       if (ncompares)
 182         *ncompares = sp->ncompares;
 183       return elt->user_pool_index;
 184     }
 185   return (u32)~0;
 186 }
 187
 188 void clib_slist_add (clib_slist_t *sp, void *key, u32 user_pool_index)
 189 {
 190   clib_slist_elt_t *new_elt;
 191   clib_slist_search_result_t search_result;
 192   int level;
 193
 194   search_result = slist_search_internal (sp, key,
 195                                          0 /* don't need full path */);
 196
 197   /* Special case: key exists, just replace user_pool_index */
 198   if (PREDICT_FALSE(search_result == CLIB_SLIST_MATCH))
 199     {
 200       clib_slist_elt_t *elt;
 201       elt = pool_elt_at_index (sp->elts, sp->path[0]);
 202       elt->user_pool_index = user_pool_index;
 203       return;
 204     }
 205
 206   pool_get (sp->elts, new_elt);
 207   new_elt->n.nexts = 0;
 208   new_elt->user_pool_index = user_pool_index;
 209
 210   /* sp->path lists elements to the left of key, by level */
 211   for (level = 0; level < vec_len(sp->path); level++)
 212     {
 213       clib_slist_elt_t *prev_elt_this_level;
 214       u32 prev_elt_next_index_this_level;
 215
 216       /* Add to list at the current level */
 217       prev_elt_this_level = pool_elt_at_index (sp->elts, sp->path[level]);
 218       prev_elt_next_index_this_level = clib_slist_get_next_at_level
 219         (prev_elt_this_level, level);
 220
 221       clib_slist_set_next_at_level (new_elt, prev_elt_next_index_this_level,
 222                                     level);
 223
 224       clib_slist_set_next_at_level (prev_elt_this_level, new_elt - sp->elts,
 225                                     level);
 226       sp->occupancy[level]++;
 227
 228       /* Randomly add to the next-higher level */
 229       if (random_f64 (&sp->seed) > sp->branching_factor)
 230         break;
 231     }
 232     {
 233     /* Time to add a new ply? */
 234       clib_slist_elt_t *head_elt = pool_elt_at_index (sp->elts, 0);
 235       int top_level = vec_len(head_elt->n.nexts) - 1;
 236       if (((f64)sp->occupancy[top_level]) * sp->branching_factor > 1.0)
 237         {
 238           vec_add1 (sp->occupancy, 0);
 239           vec_add1 (head_elt->n.nexts, (u32)~0);
 240           /* full match case returns n+1 items */
 241           vec_validate (sp->path, vec_len(head_elt->n.nexts));
 242         }
 243     }
 244 }
 245
 246 clib_slist_search_result_t
 247 clib_slist_del (clib_slist_t *sp, void *key)
 248 {
 249   clib_slist_search_result_t search_result;
 250   clib_slist_elt_t *del_elt;
 251   int level;
 252
 253   search_result = slist_search_internal (sp, key, 1 /* need full path */);
 254
 255   if (PREDICT_FALSE(search_result == CLIB_SLIST_NO_MATCH))
 256     return search_result;
 257
 258   del_elt = pool_elt_at_index (sp->elts, sp->path[vec_len(sp->path)-1]);
 259   ASSERT(vec_len(sp->path) > 1);
 260
 261   for (level = 0; level < vec_len (sp->path)-1; level++)
 262     {
 263       clib_slist_elt_t *path_elt;
 264       u32 path_elt_next_index;
 265
 266       path_elt = pool_elt_at_index (sp->elts, sp->path[level]);
 267       path_elt_next_index = clib_slist_get_next_at_level (path_elt, level);
 268
 269       /* Splice the item out of the list if it's adjacent to the victim */
 270       if (path_elt_next_index == del_elt - sp->elts)
 271         {
 272           sp->occupancy[level]--;
 273           path_elt_next_index = clib_slist_get_next_at_level (del_elt, level);
 274           clib_slist_set_next_at_level (path_elt, path_elt_next_index, level);
 275         }
 276     }
 277
 278   /* If this element is on more than two lists it has a vector of nexts */
 279   if (! (del_elt->n.next0[0] & 1))
 280     vec_free (del_elt->n.nexts);
 281   pool_put (sp->elts, del_elt);
 282   return CLIB_SLIST_MATCH;
 283 }
 284
 285 u8 * format_slist (u8 * s, va_list *args)
 286 {
 287   clib_slist_t *sl = va_arg (*args, clib_slist_t *);
 288   int verbose = va_arg (*args, int);
 289   int i;
 290   clib_slist_elt_t *head_elt, *elt;
 291
 292   s = format (s, "slist 0x%x, %u items, branching_factor %.2f\n", sl,
 293               sl->occupancy ? sl->occupancy[0] : 0, sl->branching_factor);
 294
 295   if (pool_elts(sl->elts) == 0)
 296     return s;
 297
 298   head_elt = pool_elt_at_index (sl->elts, 0);
 299
 300   for (i = 0; i < vec_len (head_elt->n.nexts); i++)
 301     {
 302       s = format (s, "level %d: %d elts\n", i, sl->occupancy[i]);
 303
 304       if (verbose && head_elt->n.nexts[i] != (u32)~0)
 305         {
 306           elt = pool_elt_at_index (sl->elts, head_elt->n.nexts[i]);
 307           while (elt)
 308             {
 309               u32 next_index;
 310               s = format (s, "%U(%d) ", sl->format_user_element,
 311                           elt->user_pool_index, elt - sl->elts);
 312               next_index = clib_slist_get_next_at_level (elt, i);
 313               ASSERT(next_index != 0x7fffffff);
 314               if (next_index == (u32)~0)
 315                 break;
 316               else
 317                 elt = pool_elt_at_index (sl->elts, next_index);
 318             }
 319         }
 320       s = format (s, "\n");
 321     }
 322   return s;
 323 }