diff options
Diffstat (limited to 'vppinfra/vppinfra/mhash.h')
-rw-r--r-- | vppinfra/vppinfra/mhash.h | 159 |
1 files changed, 159 insertions, 0 deletions
diff --git a/vppinfra/vppinfra/mhash.h b/vppinfra/vppinfra/mhash.h new file mode 100644 index 00000000000..2938a8472d2 --- /dev/null +++ b/vppinfra/vppinfra/mhash.h @@ -0,0 +1,159 @@ +/* + * Copyright (c) 2015 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. + */ +#ifndef included_clib_mhash_h +#define included_clib_mhash_h + +/* + Copyright (c) 2010 Eliot Dresselhaus + + Permission is hereby granted, free of charge, to any person obtaining + a copy of this software and associated documentation files (the + "Software"), to deal in the Software without restriction, including + without limitation the rights to use, copy, modify, merge, publish, + distribute, sublicense, and/or sell copies of the Software, and to + permit persons to whom the Software is furnished to do so, subject to + the following conditions: + + The above copyright notice and this permission notice shall be + included in all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +*/ + +#include <vppinfra/format.h> +#include <vppinfra/hash.h> +#include <vppinfra/heap.h> + +/* Hash table plus vector of keys. */ +typedef struct { + /* Vector or heap used to store keys. Hash table stores keys as byte + offsets into this vector. */ + u8 * key_vector_or_heap; + + /* Byte offsets of free keys in vector (used to store free keys when + n_key_bytes > 1). */ + u32 * key_vector_free_indices; + + u8 ** key_tmps; + + /* Possibly fixed size of key. + 0 means keys are vectors of u8's. + 1 means keys are null terminated c strings. */ +#define MHASH_VEC_STRING_KEY 0 +#define MHASH_C_STRING_KEY 1 + u32 n_key_bytes; + + /* Seed value for Jenkins hash. */ + u32 hash_seed; + + /* Hash table mapping key -> value. */ + uword * hash; + + /* Format function for keys. */ + format_function_t * format_key; +} mhash_t; + +void mhash_init (mhash_t * h, uword n_value_bytes, uword n_key_bytes); + +always_inline void +mhash_init_c_string (mhash_t * h, uword n_value_bytes) +{ mhash_init (h, n_value_bytes, MHASH_C_STRING_KEY); } + +always_inline void +mhash_init_vec_string (mhash_t * h, uword n_value_bytes) +{ mhash_init (h, n_value_bytes, MHASH_VEC_STRING_KEY); } + +always_inline void * +mhash_key_to_mem (mhash_t * h, uword key) +{ + if (key == ~0) + { + u8 * key_tmp; + + int my_cpu = os_get_cpu_number(); + vec_validate(h->key_tmps, my_cpu); + key_tmp = h->key_tmps[my_cpu]; + return key_tmp; + } + return vec_elt_at_index (h->key_vector_or_heap, key); +} + +hash_pair_t * mhash_get_pair (mhash_t * h, void * key); +uword mhash_set_mem (mhash_t * h, void * key, uword * new_value, uword * old_value); +uword mhash_unset (mhash_t * h, void * key, uword * old_value); + +always_inline uword * +mhash_get (mhash_t * h, void * key) +{ + hash_pair_t * p = mhash_get_pair (h, key); + return p ? &p->value[0] : 0; +} + +always_inline uword +mhash_set (mhash_t * h, void * key, uword new_value, uword * old_value) +{ return mhash_set_mem (h, key, &new_value, old_value); } + +always_inline uword +mhash_unset_key (mhash_t * h, uword key, uword * old_value) +{ + void * k = mhash_key_to_mem (h, key); + return mhash_unset (h, k, old_value); +} + +always_inline uword +mhash_value_bytes (mhash_t * m) +{ + hash_t * h = hash_header (m->hash); + return hash_value_bytes (h); +} + +always_inline uword +mhash_elts (mhash_t * m) +{ return hash_elts (m->hash); } + +always_inline uword +mhash_key_vector_is_heap (mhash_t * h) +{ return h->n_key_bytes <= 1; } + +always_inline void +mhash_free (mhash_t * h) +{ + if (mhash_key_vector_is_heap (h)) + heap_free (h->key_vector_or_heap); + else + vec_free (h->key_vector_or_heap); + vec_free (h->key_vector_free_indices); + hash_free (h->hash); +} + +#define mhash_foreach(k,v,mh,body) \ +do { \ + hash_pair_t * _mhash_foreach_p; \ + hash_foreach_pair (_mhash_foreach_p, (mh)->hash, ({ \ + (k) = mhash_key_to_mem ((mh), _mhash_foreach_p->key); \ + (v) = &_mhash_foreach_p->value[0]; \ + body; \ + })); \ +} while (0) + +format_function_t format_mhash_key; /*
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[i]);
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;
}
|