Index: kernel/generic/include/adt/cht.h =================================================================== --- kernel/generic/include/adt/cht.h (revision ec443d53cc8411f6b71e18809a8bf0563e29e90a) +++ kernel/generic/include/adt/cht.h (revision ec443d53cc8411f6b71e18809a8bf0563e29e90a) @@ -0,0 +1,153 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup genericadt + * @{ + */ +/** @file + */ + +#ifndef KERN_CONC_HASH_TABLE_H_ +#define KERN_CONC_HASH_TABLE_H_ + +#include +#include +#include +#include +#include + +typedef uintptr_t cht_ptr_t; + +/** Concurrent hash table node link. */ +typedef struct cht_link { + /* Must be placed first. + * + * The function pointer (rcu_link.func) is used to store the item's + * mixed memoized hash. If in use by RCU (ie waiting for deferred + * destruction) the hash will contain the value of + * cht_t.op->remove_callback. + */ + union { + rcu_item_t rcu_link; + size_t hash; + }; + /** Link to the next item in the bucket including any marks. */ + cht_ptr_t link; +} cht_link_t; + +/** Set of operations for a concurrent hash table. */ +typedef struct cht_ops { + /** Returns the hash of the item. + * + * Applicable also to items that were logically deleted from the table + * but have yet to be physically removed by means of remove_callback(). + */ + size_t (*hash)(const cht_link_t *item); + /** Returns the hash value of the key used to search for entries. */ + size_t (*key_hash)(void *key); + /** Returns true if the two items store equal search keys. */ + bool (*equal)(const cht_link_t *item1, const cht_link_t *item2); + /** Returns true if the item contains an equal search key. */ + bool (*key_equal)(void *key, const cht_link_t *item); + /** Invoked to free a removed item once all references to it are dropped. */ + void (*remove_callback)(cht_link_t *item); +} cht_ops_t; + +/** Groups hash table buckets with their count. + * + * It allows both the number of buckets as well as the bucket array + * to be swapped atomically when resing the table. + */ +typedef struct cht_buckets { + /** The number of buckets is 2^order. */ + size_t order; + /** Array of single linked list bucket heads along with any marks. */ + cht_ptr_t head[1]; +} cht_buckets_t; + +/** Concurrent hash table structure. */ +typedef struct { + /** Item specific operations. */ + cht_ops_t *op; + + /** Buckets currently in use. */ + cht_buckets_t *b; + /** Resized table buckets that will replace b once resize is complete. */ + cht_buckets_t *new_b; + /** Invalid memoized hash value. + * + * If cht_link.hash contains this value the item had been logically + * removed and is waiting to be freed. Such hashes (and the associated + * items) are disregarded and skipped or the actual hash must be + * determined via op->hash(). + */ + size_t invalid_hash; + + /** Minimum number of buckets is 2^min_order. */ + size_t min_order; + /** Maximum number of items per bucket before the table grows. */ + size_t max_load; + /** Table is resized in the background in a work queue. */ + work_t resize_work; + /** If positive the table should grow or shrink. + * + * If not 0 resize work had already been posted to the system work queue. + */ + atomic_t resize_reqs; + + /** Number of items in the table that have not been logically deleted. */ + atomic_t item_cnt; +} cht_t; + +#define cht_get_inst(item, type, member) \ + member_to_inst((item), type, member) + + +#define cht_read_lock() rcu_read_lock() +#define cht_read_unlock() rcu_read_unlock() + +extern bool cht_create_simple(cht_t *h, cht_ops_t *op); +extern bool cht_create(cht_t *h, size_t init_size, size_t min_size, + size_t max_load, bool can_block, cht_ops_t *op); +extern void cht_destroy(cht_t *h); +extern void cht_destroy_unsafe(cht_t *h); + +extern cht_link_t *cht_find(cht_t *h, void *key); +extern cht_link_t *cht_find_lazy(cht_t *h, void *key); +extern cht_link_t *cht_find_next(cht_t *h, const cht_link_t *item); +extern cht_link_t *cht_find_next_lazy(cht_t *h, const cht_link_t *item); + +extern void cht_insert(cht_t *h, cht_link_t *item); +extern bool cht_insert_unique(cht_t *h, cht_link_t *item, cht_link_t **dup_item); +extern size_t cht_remove_key(cht_t *h, void *key); +extern bool cht_remove_item(cht_t *h, cht_link_t *item); + +#endif + +/** @} + */ Index: kernel/generic/include/adt/hash.h =================================================================== --- kernel/generic/include/adt/hash.h (revision ec443d53cc8411f6b71e18809a8bf0563e29e90a) +++ kernel/generic/include/adt/hash.h (revision ec443d53cc8411f6b71e18809a8bf0563e29e90a) @@ -0,0 +1,112 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup genericadt + * @{ + */ +/** @file + */ +#ifndef KERN_HASH_H_ +#define KERN_HASH_H_ + +#include + +/** Produces a uniform hash affecting all output bits from the skewed input. */ +static inline uint32_t hash_mix32(uint32_t hash) +{ + /* + * Thomas Wang's modification of Bob Jenkin's hash mixing function: + * http://www.concentric.net/~Ttwang/tech/inthash.htm + * Public domain. + */ + hash = ~hash + (hash << 15); + hash = hash ^ (hash >> 12); + hash = hash + (hash << 2); + hash = hash ^ (hash >> 4); + hash = hash * 2057; + hash = hash ^ (hash >> 16); + return hash; +} + +/** Produces a uniform hash affecting all output bits from the skewed input. */ +static inline uint64_t hash_mix64(uint64_t hash) +{ + /* + * Thomas Wang's public domain 64-bit hash mixing function: + * http://www.concentric.net/~Ttwang/tech/inthash.htm + */ + hash = (hash ^ 61) ^ (hash >> 16); + hash = hash + (hash << 3); + hash = hash ^ (hash >> 4); + hash = hash * 0x27d4eb2d; + hash = hash ^ (hash >> 15); + /* + * Lower order bits are mixed more thoroughly. Swap them with + * the higher order bits and make the resulting higher order bits + * more usable. + */ + return (hash << 32) | (hash >> 32); +} + +/** Produces a uniform hash affecting all output bits from the skewed input. */ +static inline size_t hash_mix(size_t hash) +{ +#ifdef __32_BITS__ + return hash_mix32(hash); +#elif defined(__64_BITS__) + return hash_mix64(hash); +#else +#error Unknown size_t size - cannot select proper hash mix function. +#endif +} + +/** Use to create a hash from multiple values. + * + * Typical usage: + * @code + * int car_id; + * bool car_convertible; + * // .. + * size_t hash = 0; + * hash = hash_combine(hash, car_id); + * hash = hash_combine(hash, car_convertible); + * // Now use hash as a hash of both car_id and car_convertible. + * @endcode + */ +static inline size_t hash_combine(size_t seed, size_t hash) +{ + /* + * todo: use Bob Jenkin's proper mixing hash pass: + * http://burtleburtle.net/bob/c/lookup3.c + */ + seed ^= hash + 0x9e3779b9 + + ((seed << 5) | (seed >> (sizeof(size_t) * 8 - 5))); + return seed; +} + +#endif Index: kernel/generic/include/adt/list.h =================================================================== --- kernel/generic/include/adt/list.h (revision 7856d096ccea34cfe2f6cdd077ec231776bed992) +++ kernel/generic/include/adt/list.h (revision ec443d53cc8411f6b71e18809a8bf0563e29e90a) @@ -52,4 +52,10 @@ } list_t; + +extern int list_member(const link_t *, const list_t *); +extern void list_splice(list_t *, link_t *); +extern unsigned int list_count(const list_t *); + + /** Declare and initialize statically allocated list. * @@ -80,4 +86,36 @@ _link != &(list).head; _link = _link->prev) +/** Unlike list_foreach(), allows removing items while traversing a list. + * + * @code + * list_t mylist; + * typedef struct item { + * int value; + * link_t item_link; + * } item_t; + * + * //.. + * + * // Print each list element's value and remove the element from the list. + * list_foreach_safe(mylist, cur_link, next_link) { + * item_t *cur_item = list_get_instance(cur_link, item_t, item_link); + * printf("%d\n", cur_item->value); + * list_remove(cur_link); + * } + * @endcode + * + * @param list List to traverse. + * @param iterator Iterator to the current element of the list. + * The item this iterator points may be safely removed + * from the list. + * @param next_iter Iterator to the next element of the list. + */ +#define list_foreach_safe(list, iterator, next_iter) \ + for (link_t *iterator = (list).head.next, \ + *next_iter = iterator->next; \ + iterator != &(list).head; \ + iterator = next_iter, next_iter = iterator->next) + + #define assert_link_not_used(link) \ ASSERT(!link_used(link)) @@ -289,4 +327,19 @@ { headless_list_split_or_concat(part1, part2); +} + +/** Concatenate two lists + * + * Concatenate lists @a list1 and @a list2, producing a single + * list @a list1 containing items from both (in @a list1, @a list2 + * order) and empty list @a list2. + * + * @param list1 First list and concatenated output + * @param list2 Second list and empty output. + * + */ +NO_TRACE static inline void list_concat(list_t *list1, list_t *list2) +{ + list_splice(list2, list1->head.prev); } @@ -340,8 +393,4 @@ } -extern int list_member(const link_t *, const list_t *); -extern void list_concat(list_t *, list_t *); -extern unsigned int list_count(const list_t *); - #endif