diff options
Diffstat (limited to 'vpp/vppinfra/vppinfra/slist.c')
| -rw-r--r-- | vpp/vppinfra/vppinfra/slist.c | 336 |
1 files changed, 336 insertions, 0 deletions
diff --git a/vpp/vppinfra/vppinfra/slist.c b/vpp/vppinfra/vppinfra/slist.c new file mode 100644 index 00000000..892517bb --- /dev/null +++ b/vpp/vppinfra/vppinfra/slist.c @@ -0,0 +1,336 @@ +/* + Copyright (c) 2012 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 <vppinfra/slist.h> + +/* + * skip-list implementation + * + * Good news / bad news. As balanced binary tree schemes go, + * this one seems pretty fast and is reasonably simple. There's a very + * limited amount that can be done to mitigate sdram read latency. + * + * Each active clib_slist_elt_t is on from 1 to N lists. Each active element + * is always on the "level-0" list. Since most elements are *only* on + * level 0, we keep the level 0 (and level 1) in the element. For those + * elements on more than two lists, we switch to a vector. Hence, the + * "n" union in slib_slist_elt_t. + * + * The low-order bit of elt->n.next0[0] is 1 for inlined next indices, + * 0 for vector indices (since the allocator always aligns to at least + * a 4-byte boundary). We can only represent 2e9 items, but since the + * practical performance limit is O(1e7), it doesn't matter. + * + * We create a "head" element which (by construction) is always + * lexically lighter than any other element. This makes a large number + * of irritating special cases go away. + * + * User code is in charge of comparing a supplied key with + * the key component of a user pool element. The user tells this code + * to add or delete (opaque key, 32-bit integer) pairs to the skip-list. + * + * The algorithm adds new elements to one or more lists. + * For levels greater than zero, the probability of a new element landing on + * a list is branching_factor**N. Branching_factor = 0.2 seems to work + * OK, yielding about 50 compares per search at O(1e7) items. + */ + +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) +{ + clib_slist_elt_t *head; + memset (sp, 0, sizeof (sp[0])); + sp->branching_factor = branching_factor; + sp->format_user_element = format_user_element; + sp->compare = compare; + sp->seed = 0xdeaddabe; + pool_get (sp->elts, head); + vec_add1 (head->n.nexts, (u32) ~ 0); + head->user_pool_index = (u32) ~ 0; + vec_validate (sp->path, 1); + vec_validate (sp->occupancy, 0); + + return 0; +} + +/* + * slist_search_internal + */ +static inline clib_slist_search_result_t +slist_search_internal (clib_slist_t * sp, void *key, int need_full_path) +{ + int level, comp_result; + clib_slist_elt_t *search_elt, *head_elt; + + sp->ncompares = 0; + /* + * index 0 is the magic listhead element which is + * lexically lighter than / to the left of every element + */ + search_elt = head_elt = pool_elt_at_index (sp->elts, 0); + + /* + * Initial negotiating position, only the head_elt is + * lighter than the supplied key + */ + memset (sp->path, 0, vec_len (head_elt->n.nexts) * sizeof (u32)); + + /* Walk the fastest lane first */ + level = vec_len (head_elt->n.nexts) - 1; + _vec_len (sp->path) = level + 1; + + while (1) + { + u32 next_index_this_level; + clib_slist_elt_t *prefetch_elt; + + /* + * Prefetching the next element at this level makes a measurable + * difference, but doesn't fix the dependent read stall problem + */ + prefetch_elt = sp->elts + + clib_slist_get_next_at_level (search_elt, level); + + CLIB_PREFETCH (prefetch_elt, CLIB_CACHE_LINE_BYTES, READ); + + /* Compare the key with the current element */ + comp_result = (search_elt == head_elt) ? 1 : + sp->compare (key, search_elt->user_pool_index); + + sp->ncompares++; + /* key "lighter" than this element */ + if (comp_result < 0) + { + /* + * Back up to previous item on this list + * and search the next finer-grained list + * starting there. + */ + search_elt = pool_elt_at_index (sp->elts, sp->path[level]); + next_list: + if (level > 0) + { + level--; + continue; + } + else + { + return CLIB_SLIST_NO_MATCH; + } + } + /* Match */ + if (comp_result == 0) + { + /* + * If we're trying to delete an element, we need to + * track down all of the elements which point at it. + * Otherwise, don't bother with it + */ + if (need_full_path && level > 0) + { + search_elt = pool_elt_at_index (sp->elts, sp->path[level]); + level--; + continue; + } + level = vec_len (head_elt->n.nexts); + sp->path[level] = search_elt - sp->elts; + _vec_len (sp->path) = level + 1; + return CLIB_SLIST_MATCH; + } + /* + * comp_result positive, key is to the right of + * this element + */ + sp->path[level] = search_elt - sp->elts; + + /* Out of list at this level? */ + next_index_this_level = + clib_slist_get_next_at_level (search_elt, level); + if (next_index_this_level == (u32) ~ 0) + goto next_list; + + /* No, try the next element */ + search_elt = pool_elt_at_index (sp->elts, next_index_this_level); + } + return 0; /* notreached */ +} + +u32 +clib_slist_search (clib_slist_t * sp, void *key, u32 * ncompares) +{ + clib_slist_search_result_t rv; + + rv = slist_search_internal (sp, key, 0 /* dont need full path */ ); + if (rv == CLIB_SLIST_MATCH) + { + clib_slist_elt_t *elt; + elt = pool_elt_at_index (sp->elts, sp->path[vec_len (sp->path) - 1]); + if (ncompares) + *ncompares = sp->ncompares; + return elt->user_pool_index; + } + return (u32) ~ 0; +} + +void +clib_slist_add (clib_slist_t * sp, void *key, u32 user_pool_index) +{ + clib_slist_elt_t *new_elt; + clib_slist_search_result_t search_result; + int level; + + search_result = slist_search_internal (sp, key, + 0 /* don't need full path */ ); + + /* Special case: key exists, just replace user_pool_index */ + if (PREDICT_FALSE (search_result == CLIB_SLIST_MATCH)) + { + clib_slist_elt_t *elt; + elt = pool_elt_at_index (sp->elts, sp->path[0]); + elt->user_pool_index = user_pool_index; + return; + } + + pool_get (sp->elts, new_elt); + new_elt->n.nexts = 0; + new_elt->user_pool_index = user_pool_index; + + /* sp->path lists elements to the left of key, by level */ + for (level = 0; level < vec_len (sp->path); level++) + { + clib_slist_elt_t *prev_elt_this_level; + u32 prev_elt_next_index_this_level; + + /* Add to list at the current level */ + prev_elt_this_level = pool_elt_at_index (sp->elts, sp->path[level]); + prev_elt_next_index_this_level = clib_slist_get_next_at_level + (prev_elt_this_level, level); + + clib_slist_set_next_at_level (new_elt, prev_elt_next_index_this_level, + level); + + clib_slist_set_next_at_level (prev_elt_this_level, new_elt - sp->elts, + level); + sp->occupancy[level]++; + + /* Randomly add to the next-higher level */ + if (random_f64 (&sp->seed) > sp->branching_factor) + break; + } + { + /* Time to add a new ply? */ + clib_slist_elt_t *head_elt = pool_elt_at_index (sp->elts, 0); + int top_level = vec_len (head_elt->n.nexts) - 1; + if (((f64) sp->occupancy[top_level]) * sp->branching_factor > 1.0) + { + vec_add1 (sp->occupancy, 0); + vec_add1 (head_elt->n.nexts, (u32) ~ 0); + /* full match case returns n+1 items */ + vec_validate (sp->path, vec_len (head_elt->n.nexts)); + } + } +} + +clib_slist_search_result_t +clib_slist_del (clib_slist_t * sp, void *key) +{ + clib_slist_search_result_t search_result; + clib_slist_elt_t *del_elt; + int level; + + search_result = slist_search_internal (sp, key, 1 /* need full path */ ); + + if (PREDICT_FALSE (search_result == CLIB_SLIST_NO_MATCH)) + return search_result; + + del_elt = pool_elt_at_index (sp->elts, sp->path[vec_len (sp->path) - 1]); + ASSERT (vec_len (sp->path) > 1); + + for (level = 0; level < vec_len (sp->path) - 1; level++) + { + clib_slist_elt_t *path_elt; + u32 path_elt_next_index; + + path_elt = pool_elt_at_index (sp->elts, sp->path[level]); + path_elt_next_index = clib_slist_get_next_at_level (path_elt, level); + + /* Splice the item out of the list if it's adjacent to the victim */ + if (path_elt_next_index == del_elt - sp->elts) + { + sp->occupancy[level]--; + path_elt_next_index = clib_slist_get_next_at_level (del_elt, level); + clib_slist_set_next_at_level (path_elt, path_elt_next_index, level); + } + } + + /* If this element is on more than two lists it has a vector of nexts */ + if (!(del_elt->n.next0[0] & 1)) + vec_free (del_elt->n.nexts); + pool_put (sp->elts, del_elt); + return CLIB_SLIST_MATCH; +} + +u8 * +format_slist (u8 * s, va_list * args) +{ + clib_slist_t *sl = va_arg (*args, clib_slist_t *); + int verbose = va_arg (*args, int); + int i; + clib_slist_elt_t *head_elt, *elt; + + s = format (s, "slist 0x%x, %u items, branching_factor %.2f\n", sl, + sl->occupancy ? sl->occupancy[0] : 0, sl->branching_factor); + + if (pool_elts (sl->elts) == 0) + return s; + + head_elt = pool_elt_at_index (sl->elts, 0); + + for (i = 0; i < vec_len (head_elt->n.nexts); i++) + { + s = format (s, "level %d: %d elts\n", i, + sl->occupancy ? sl->occupancy[i] : 0); + + if (verbose && head_elt->n.nexts[i] != (u32) ~ 0) + { + elt = pool_elt_at_index (sl->elts, head_elt->n.nexts[i]); + while (elt) + { + u32 next_index; + s = format (s, "%U(%d) ", sl->format_user_element, + elt->user_pool_index, elt - sl->elts); + next_index = clib_slist_get_next_at_level (elt, i); + ASSERT (next_index != 0x7fffffff); + if (next_index == (u32) ~ 0) + break; + else + elt = pool_elt_at_index (sl->elts, next_index); + } + } + s = format (s, "\n"); + } + return s; +} + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ |