Index: kernel/generic/src/adt/avl.c =================================================================== --- kernel/generic/src/adt/avl.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/adt/avl.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -76,5 +76,5 @@ else if (p->key < key) p = p->rgt; - else + else return p; } @@ -102,5 +102,5 @@ * Iteratively descend to the leftmost leaf in the tree. */ - while (p->lft != NULL) + while (p->lft != NULL) p = p->lft; @@ -156,8 +156,8 @@ * @param t AVL tree. * @param newnode New node to be inserted. - */ + */ void avltree_insert(avltree_t *t, avltree_node_t *newnode) -{ - avltree_node_t *par; +{ + avltree_node_t *par; avltree_node_t *gpa; avltree_node_t *top; @@ -170,5 +170,5 @@ /* * Creating absolute key. - */ + */ key = newnode->key + t->base; @@ -223,5 +223,5 @@ if (top->par == NULL) { dpc = &t->root; - } else { + } else { if (top->par->lft == top) dpc = &top->par->lft; @@ -255,5 +255,5 @@ */ REBALANCE_INSERT_LL(); - } else { + } else { /* * LR rotation. @@ -263,5 +263,5 @@ REBALANCE_INSERT_LR(); } - } else if (top->balance == 2) { + } else if (top->balance == 2) { par = top->rgt; if (par->balance == 1) { @@ -278,5 +278,5 @@ REBALANCE_INSERT_RL(); } - } else { + } else { /* * Balance is not broken, insertion is finised. @@ -303,5 +303,5 @@ * @param ro Read only operation; do not modify any tree pointers. This is * useful for tracking direction via the dir pointer. - * + * * @return Zero if w became the new root of the tree, otherwise return * non-zero. @@ -313,7 +313,7 @@ if (u->par == NULL) { if (!ro) - t->root = w; + t->root = w; return 0; - } else { + } else { if (u->par->lft == v) { if (!ro) @@ -362,5 +362,5 @@ * Because multiple identical keys are allowed, the parent pointers are * essential during deletion. - * + * * @param t AVL tree structure. * @param node Address of the node which will be deleted. @@ -379,5 +379,5 @@ if (node->rgt) { /* - * Replace the node with its only right son. + * Replace the node with its only right son. * * Balance of the right son will be repaired in the @@ -388,5 +388,5 @@ gpa = cur; dir = RIGHT; - cur->balance = node->balance; + cur->balance = node->balance; } else { if (node->par == NULL) { @@ -421,5 +421,5 @@ * Cutting off of the found node has two cases that * depend on its left son. - */ + */ if (cur->lft) { /* @@ -429,5 +429,5 @@ gpa->par = cur->par; dir = LEFT; - gpa->balance = cur->balance; + gpa->balance = cur->balance; } else { dir = RIGHT; @@ -436,6 +436,6 @@ cur->par->rgt = cur->lft; cur->lft = node->lft; - cur->lft->par = cur; - } else { + cur->lft->par = cur; + } else { /* * The left son of the node hasn't got a right son. The @@ -443,8 +443,8 @@ */ dir = LEFT; - gpa = cur; + gpa = cur; } if (node->rgt) - node->rgt->par = cur; + node->rgt->par = cur; cur->rgt = node->rgt; cur->balance = node->balance; @@ -473,5 +473,5 @@ */ break; - } else if (gpa->balance == 2) { + } else if (gpa->balance == 2) { /* * Bad balance, heights of left and right @@ -538,5 +538,5 @@ (void) repair(t, par, gpa, par, NULL, false); - break; + break; } else { par->balance = 0; @@ -559,5 +559,5 @@ gpa = gpa->par; } - } else { + } else { /* * Deletion was made in the right subtree. @@ -605,5 +605,5 @@ break; gpa = cur->par; - } else { + } else { /* * LL rotation. @@ -681,5 +681,5 @@ node = node->lft; - avltree_delete(t, node); + avltree_delete(t, node); return true; Index: kernel/generic/src/adt/btree.c =================================================================== --- kernel/generic/src/adt/btree.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/adt/btree.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -124,5 +124,5 @@ if (root->keys) { - for (i = 0; i < root->keys + 1; i++) { + for (i = 0; i < root->keys + 1; i++) { if (root->subtree[i]) btree_destroy_subtree(root->subtree[i]); Index: kernel/generic/src/adt/cht.c =================================================================== --- kernel/generic/src/adt/cht.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/adt/cht.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -35,5 +35,5 @@ * @file * @brief Scalable resizable concurrent lock-free hash table. - * + * * CHT is a concurrent hash table that is scalable resizable and lock-free. * resizable = the number of buckets of the table increases or decreases @@ -48,10 +48,10 @@ * fraction of updates (insert/remove) increases. Other data structures * significantly outperform CHT if the fraction of updates exceeds ~40%. - * + * * CHT tolerates hardware exceptions and may be accessed from exception * handlers as long as the underlying RCU implementation is exception safe. - * + * * @par Caveats - * + * * 0) Never assume an item is still in the table. * The table may be accessed concurrently; therefore, other threads may @@ -59,20 +59,20 @@ * in the table if cht_find() just returned it to you. Similarly, an * item may have already been inserted by the time cht_find() returns NULL. - * + * * 1) Always use RCU read locks when searching the table. * Holding an RCU lock guarantees that an item found in the table remains * valid (eg is not freed) even if the item was removed from the table * in the meantime by another thread. - * + * * 2) Never update values in place. * Do not update items in the table in place, ie directly. The changes * will not propagate to other readers (on other cpus) immediately or even * correctly. Some readers may then encounter items that have only some - * of their fields changed or are completely inconsistent. - * - * Instead consider inserting an updated/changed copy of the item and + * of their fields changed or are completely inconsistent. + * + * Instead consider inserting an updated/changed copy of the item and * removing the original item. Or contact the maintainer to provide * you with a function that atomically replaces an item with a copy. - * + * * 3) Use cht_insert_unique() instead of checking for duplicates with cht_find() * The following code is prone to race conditions: @@ -84,41 +84,41 @@ * @endcode * See cht_insert_unique() on how to correctly fix this. - * + * * * @par Semantics - * + * * Lazy readers = cht_find_lazy(), cht_find_next_lazy() * Readers = lazy readers, cht_find(), cht_find_next() - * Updates = cht_insert(), cht_insert_unique(), cht_remove_key(), + * Updates = cht_insert(), cht_insert_unique(), cht_remove_key(), * cht_remove_item() - * - * Readers (but not lazy readers) are guaranteed to see the effects - * of @e completed updates. In other words, if cht_find() is invoked - * after a cht_insert() @e returned eg on another cpu, cht_find() is - * guaranteed to see the inserted item. - * + * + * Readers (but not lazy readers) are guaranteed to see the effects + * of @e completed updates. In other words, if cht_find() is invoked + * after a cht_insert() @e returned eg on another cpu, cht_find() is + * guaranteed to see the inserted item. + * * Similarly, updates see the effects of @e completed updates. For example, - * issuing cht_remove() after a cht_insert() for that key returned (even + * issuing cht_remove() after a cht_insert() for that key returned (even * on another cpu) is guaranteed to remove the inserted item. - * + * * Reading or updating the table concurrently with other updates * always returns consistent data and never corrupts the table. * However the effects of concurrent updates may or may not be * visible to all other concurrent readers or updaters. Eg, not - * all readers may see that an item has already been inserted - * if cht_insert() has not yet returned. - * + * all readers may see that an item has already been inserted + * if cht_insert() has not yet returned. + * * Lazy readers are guaranteed to eventually see updates but it * may take some time (possibly milliseconds) after the update * completes for the change to propagate to lazy readers on all * cpus. - * + * * @par Implementation - * + * * Collisions in CHT are resolved with chaining. The number of buckets - * is always a power of 2. Each bucket is represented with a single linked - * lock-free list [1]. Items in buckets are sorted by their mixed hashes - * in ascending order. All buckets are terminated with a single global - * sentinel node whose mixed hash value is the greatest possible. + * is always a power of 2. Each bucket is represented with a single linked + * lock-free list [1]. Items in buckets are sorted by their mixed hashes + * in ascending order. All buckets are terminated with a single global + * sentinel node whose mixed hash value is the greatest possible. * * CHT with 2^k buckets uses the k most significant bits of a hash value @@ -127,32 +127,32 @@ * hash function does not produce uniform hashes, hash values are * mixed first so that the top bits of a mixed hash change even if hash - * values differ only in the least significant bits. The mixed hash - * values are cached in cht_link.hash (which is overwritten once the + * values differ only in the least significant bits. The mixed hash + * values are cached in cht_link.hash (which is overwritten once the * item is scheduled for removal via rcu_call). - * + * * A new item is inserted before all other existing items in the bucket * with the same hash value as the newly inserted item (a la the original - * lock-free list [2]). Placing new items at the start of a same-hash - * sequence of items (eg duplicates) allows us to easily check for duplicates - * in cht_insert_unique(). The function can first check that there are - * no duplicates of the newly inserted item amongst the items with the - * same hash as the new item. If there were no duplicates the new item - * is linked before the same-hash items. Inserting a duplicate while - * the function is checking for duplicates is detected as a change of - * the link to the first checked same-hash item (and the search for + * lock-free list [2]). Placing new items at the start of a same-hash + * sequence of items (eg duplicates) allows us to easily check for duplicates + * in cht_insert_unique(). The function can first check that there are + * no duplicates of the newly inserted item amongst the items with the + * same hash as the new item. If there were no duplicates the new item + * is linked before the same-hash items. Inserting a duplicate while + * the function is checking for duplicates is detected as a change of + * the link to the first checked same-hash item (and the search for * duplicates can be restarted). - * + * * @par Table resize algorithm - * + * * Table resize is based on [3] and [5]. First, a new bucket head array * is allocated and initialized. Second, old bucket heads are moved - * to the new bucket head array with the protocol mentioned in [5]. + * to the new bucket head array with the protocol mentioned in [5]. * At this point updaters start using the new bucket heads. Third, * buckets are split (or joined) so that the table can make use of * the extra bucket head slots in the new array (or stop wasting space * with the unnecessary extra slots in the old array). Splitting - * or joining buckets employs a custom protocol. Last, the new array + * or joining buckets employs a custom protocol. Last, the new array * replaces the original bucket array. - * + * * A single background work item (of the system work queue) guides * resizing of the table. If an updater detects that the bucket it @@ -160,51 +160,51 @@ * or it needs to be split/joined), it helps out and completes the * head move or the bucket split/join. - * - * The table always grows or shrinks by a factor of 2. Because items - * are assigned a bucket based on the top k bits of their mixed hash - * values, when growing the table each bucket is split into two buckets - * and all items of the two new buckets come from the single bucket in the + * + * The table always grows or shrinks by a factor of 2. Because items + * are assigned a bucket based on the top k bits of their mixed hash + * values, when growing the table each bucket is split into two buckets + * and all items of the two new buckets come from the single bucket in the * original table. Ie items from separate buckets in the original table - * never intermix in the new buckets. Moreover - * since the buckets are sorted by their mixed hash values the items - * at the beginning of the old bucket will end up in the first new + * never intermix in the new buckets. Moreover + * since the buckets are sorted by their mixed hash values the items + * at the beginning of the old bucket will end up in the first new * bucket while all the remaining items of the old bucket will end up - * in the second new bucket. Therefore, there is a single point where - * to split the linked list of the old bucket into two correctly sorted + * in the second new bucket. Therefore, there is a single point where + * to split the linked list of the old bucket into two correctly sorted * linked lists of the new buckets: * .- bucket split - * | - * <-- first --> v <-- second --> + * | + * <-- first --> v <-- second --> * [old] --> [00b] -> [01b] -> [10b] -> [11b] -> sentinel - * ^ ^ - * [new0] -- -+ | + * ^ ^ + * [new0] -- -+ | * [new1] -- -- -- -- -- -- -- -+ - * + * * Resize in greater detail: - * - * a) First, a resizer (a single background system work queue item - * in charge of resizing the table) allocates and initializes a new - * bucket head array. New bucket heads are pointed to the sentinel - * and marked Invalid (in the lower order bits of the pointer to the + * + * a) First, a resizer (a single background system work queue item + * in charge of resizing the table) allocates and initializes a new + * bucket head array. New bucket heads are pointed to the sentinel + * and marked Invalid (in the lower order bits of the pointer to the * next item, ie the sentinel in this case): - * + * * [old, N] --> [00b] -> [01b] -> [10b] -> [11b] -> sentinel * ^ ^ * [new0, Inv] -------------------------------------+ | * [new1, Inv] ---------------------------------------+ - * - * - * b) Second, the resizer starts moving old bucket heads with the following - * lock-free protocol (from [5]) where cas(variable, expected_val, new_val) + * + * + * b) Second, the resizer starts moving old bucket heads with the following + * lock-free protocol (from [5]) where cas(variable, expected_val, new_val) * is short for compare-and-swap: - * + * * old head new0 head transition to next state * -------- --------- ------------------------ * addr, N sentinel, Inv cas(old, (addr, N), (addr, Const)) - * .. mark the old head as immutable, so that - * updaters do not relink it to other nodes + * .. mark the old head as immutable, so that + * updaters do not relink it to other nodes * until the head move is done. * addr, Const sentinel, Inv cas(new0, (sentinel, Inv), (addr, N)) - * .. move the address to the new head and mark + * .. move the address to the new head and mark * the new head normal so updaters can start * using it. @@ -213,20 +213,20 @@ * the head move is done. * addr, Inv addr, N - * + * * Notice that concurrent updaters may step in at any point and correctly * complete the head move without disrupting the resizer. At worst, the - * resizer or other concurrent updaters will attempt a number of CAS() that + * resizer or other concurrent updaters will attempt a number of CAS() that * will correctly fail. - * + * * [old, Inv] -> [00b] -> [01b] -> [10b] -> [11b] -> sentinel * ^ ^ * [new0, N] ----+ | * [new1, Inv] --------------------------------------+ - * - * - * c) Third, buckets are split if the table is growing; or joined if - * shrinking (by the resizer or updaters depending on whoever accesses + * + * + * c) Third, buckets are split if the table is growing; or joined if + * shrinking (by the resizer or updaters depending on whoever accesses * the bucket first). See split_bucket() and join_buckets() for details. - * + * * 1) Mark the last item of new0 with JOIN_FOLLOWS: * [old, Inv] -> [00b] -> [01b, JF] -> [10b] -> [11b] -> sentinel @@ -234,5 +234,5 @@ * [new0, N] ----+ | * [new1, Inv] ------------------------------------------+ - * + * * 2) Mark the first item of new1 with JOIN_NODE: * [old, Inv] -> [00b] -> [01b, JF] -> [10b, JN] -> [11b] -> sentinel @@ -240,5 +240,5 @@ * [new0, N] ----+ | * [new1, Inv] ----------------------------------------------+ - * + * * 3) Point new1 to the join-node and mark new1 NORMAL. * [old, Inv] -> [00b] -> [01b, JF] -> [10b, JN] -> [11b] -> sentinel @@ -246,12 +246,12 @@ * [new0, N] ----+ | * [new1, N] --------------------------+ - * - * - * d) Fourth, the resizer cleans up extra marks added during bucket + * + * + * d) Fourth, the resizer cleans up extra marks added during bucket * splits/joins but only when it is sure all updaters are accessing * the table via the new bucket heads only (ie it is certain there - * are no delayed updaters unaware of the resize and accessing the + * are no delayed updaters unaware of the resize and accessing the * table via the old bucket head). - * + * * [old, Inv] ---+ * v @@ -259,16 +259,16 @@ * v * [new1, N] --> [10b, N] -> [11b] -> sentinel - * - * + * + * * e) Last, the resizer publishes the new bucket head array for everyone * to see and use. This signals the end of the resize and the old bucket - * array is freed. - * - * + * array is freed. + * + * * To understand details of how the table is resized, read [1, 3, 5] * and comments in join_buckets(), split_bucket(). - * - * - * [1] High performance dynamic lock-free hash tables and list-based sets, + * + * + * [1] High performance dynamic lock-free hash tables and list-based sets, * Michael, 2002 * http://www.research.ibm.com/people/m/michael/spaa-2002.pdf @@ -311,11 +311,11 @@ #define CHT_MIN_BUCKET_CNT (1 << CHT_MIN_ORDER) /* Does not have to be a power of 2. */ -#define CHT_MAX_LOAD 2 +#define CHT_MAX_LOAD 2 typedef cht_ptr_t marked_ptr_t; typedef bool (*equal_pred_t)(void *arg, const cht_link_t *item); -/** The following mark items and bucket heads. - * +/** The following mark items and bucket heads. + * * They are stored in the two low order bits of the next item pointers. * Some marks may be combined. Some marks share the same binary value and @@ -327,22 +327,22 @@ N_NORMAL = 0, /** Logically deleted item that might have already been unlinked. - * - * May be combined with N_JOIN and N_JOIN_FOLLOWS. Applicable only - * to items; never to bucket heads. - * - * Once marked deleted an item remains marked deleted. + * + * May be combined with N_JOIN and N_JOIN_FOLLOWS. Applicable only + * to items; never to bucket heads. + * + * Once marked deleted an item remains marked deleted. */ N_DELETED = 1, - /** Immutable bucket head. - * - * The bucket is being moved or joined with another and its (old) head + /** Immutable bucket head. + * + * The bucket is being moved or joined with another and its (old) head * must not be modified. - * + * * May be combined with N_INVALID. Applicable only to old bucket heads, * ie cht_t.b and not cht_t.new_b. */ N_CONST = 1, - /** Invalid bucket head. The bucket head must not be modified. - * + /** Invalid bucket head. The bucket head must not be modified. + * * Old bucket heads (ie cht_t.b) are marked invalid if they have * already been moved to cht_t.new_b or if the bucket had already @@ -354,12 +354,12 @@ N_INVALID = 3, /** The item is a join node, ie joining two buckets - * + * * A join node is either the first node of the second part of * a bucket to be split; or it is the first node of the bucket * to be merged into/appended to/joined with another bucket. - * - * May be combined with N_DELETED. Applicable only to items, never + * + * May be combined with N_DELETED. Applicable only to items, never * to bucket heads. - * + * * Join nodes are referred to from two different buckets and may, * therefore, not be safely/atomically unlinked from both buckets. @@ -369,12 +369,12 @@ */ N_JOIN = 2, - /** The next node is a join node and will soon be marked so. - * + /** The next node is a join node and will soon be marked so. + * * A join-follows node is the last node of the first part of bucket * that is to be split, ie it is the last node that will remain * in the same bucket after splitting it. - * + * * May be combined with N_DELETED. Applicable to items as well - * as to bucket heads of the bucket to be split (but only in cht_t.new_b). + * as to bucket heads of the bucket to be split (but only in cht_t.new_b). */ N_JOIN_FOLLOWS = 2, @@ -413,31 +413,31 @@ static size_t size_to_order(size_t bucket_cnt, size_t min_order); -static cht_buckets_t *alloc_buckets(size_t order, bool set_invalid, +static cht_buckets_t *alloc_buckets(size_t order, bool set_invalid, bool can_block); static inline cht_link_t *find_lazy(cht_t *h, void *key); -static cht_link_t *search_bucket(cht_t *h, marked_ptr_t head, void *key, +static cht_link_t *search_bucket(cht_t *h, marked_ptr_t head, void *key, size_t search_hash); -static cht_link_t *find_resizing(cht_t *h, void *key, size_t hash, +static cht_link_t *find_resizing(cht_t *h, void *key, size_t hash, marked_ptr_t old_head, size_t old_idx); static bool insert_impl(cht_t *h, cht_link_t *item, cht_link_t **dup_item); static bool insert_at(cht_link_t *item, const wnd_t *wnd, walk_mode_t walk_mode, bool *resizing); -static bool has_duplicate(cht_t *h, const cht_link_t *item, size_t hash, +static bool has_duplicate(cht_t *h, const cht_link_t *item, size_t hash, cht_link_t *cur, cht_link_t **dup_item); -static cht_link_t *find_duplicate(cht_t *h, const cht_link_t *item, size_t hash, +static cht_link_t *find_duplicate(cht_t *h, const cht_link_t *item, size_t hash, cht_link_t *start); static bool remove_pred(cht_t *h, size_t hash, equal_pred_t pred, void *pred_arg); -static bool delete_at(cht_t *h, wnd_t *wnd, walk_mode_t walk_mode, +static bool delete_at(cht_t *h, wnd_t *wnd, walk_mode_t walk_mode, bool *deleted_but_gc, bool *resizing); static bool mark_deleted(cht_link_t *cur, walk_mode_t walk_mode, bool *resizing); static bool unlink_from_pred(wnd_t *wnd, walk_mode_t walk_mode, bool *resizing); -static bool find_wnd_and_gc_pred(cht_t *h, size_t hash, walk_mode_t walk_mode, +static bool find_wnd_and_gc_pred(cht_t *h, size_t hash, walk_mode_t walk_mode, equal_pred_t pred, void *pred_arg, wnd_t *wnd, bool *resizing); -static bool find_wnd_and_gc(cht_t *h, size_t hash, walk_mode_t walk_mode, +static bool find_wnd_and_gc(cht_t *h, size_t hash, walk_mode_t walk_mode, wnd_t *wnd, bool *resizing); static bool gc_deleted_node(cht_t *h, walk_mode_t walk_mode, wnd_t *wnd, bool *resizing); static bool join_completed(cht_t *h, const wnd_t *wnd); -static void upd_resizing_head(cht_t *h, size_t hash, marked_ptr_t **phead, +static void upd_resizing_head(cht_t *h, size_t hash, marked_ptr_t **phead, bool *join_finishing, walk_mode_t *walk_mode); static void item_removed(cht_t *h); @@ -448,12 +448,12 @@ static void mark_const(marked_ptr_t *psrc_head); static void complete_head_move(marked_ptr_t *psrc_head, marked_ptr_t *pdest_head); -static void split_bucket(cht_t *h, marked_ptr_t *psrc_head, +static void split_bucket(cht_t *h, marked_ptr_t *psrc_head, marked_ptr_t *pdest_head, size_t split_hash); -static void mark_join_follows(cht_t *h, marked_ptr_t *psrc_head, +static void mark_join_follows(cht_t *h, marked_ptr_t *psrc_head, size_t split_hash, wnd_t *wnd); static void mark_join_node(cht_link_t *join_node); -static void join_buckets(cht_t *h, marked_ptr_t *psrc_head, +static void join_buckets(cht_t *h, marked_ptr_t *psrc_head, marked_ptr_t *pdest_head, size_t split_hash); -static void link_to_join_node(cht_t *h, marked_ptr_t *pdest_head, +static void link_to_join_node(cht_t *h, marked_ptr_t *pdest_head, cht_link_t *join_node, size_t split_hash); static void resize_table(work_t *arg); @@ -461,5 +461,5 @@ static void shrink_table(cht_t *h); static void cleanup_join_node(cht_t *h, marked_ptr_t *new_head); -static void clear_join_and_gc(cht_t *h, cht_link_t *join_node, +static void clear_join_and_gc(cht_t *h, cht_link_t *join_node, marked_ptr_t *new_head); static void cleanup_join_follows(cht_t *h, marked_ptr_t *new_head); @@ -478,7 +478,7 @@ static size_t grow_idx(size_t idx); static size_t shrink_idx(size_t idx); -static marked_ptr_t cas_link(marked_ptr_t *link, const cht_link_t *cur_next, +static marked_ptr_t cas_link(marked_ptr_t *link, const cht_link_t *cur_next, mark_t cur_mark, const cht_link_t *new_next, mark_t new_mark); -static marked_ptr_t _cas_link(marked_ptr_t *link, marked_ptr_t cur, +static marked_ptr_t _cas_link(marked_ptr_t *link, marked_ptr_t cur, marked_ptr_t new); static void cas_order_barrier(void); @@ -490,5 +490,5 @@ /** Creates a concurrent hash table. - * + * * @param h Valid pointer to a cht_t instance. * @param op Item specific operations. All operations are compulsory. @@ -497,9 +497,9 @@ bool cht_create_simple(cht_t *h, cht_ops_t *op) { - return cht_create(h, 0, 0, 0, false, op); + return cht_create(h, 0, 0, 0, false, op); } /** Creates a concurrent hash table. - * + * * @param h Valid pointer to a cht_t instance. * @param init_size The initial number of buckets the table should contain. @@ -513,11 +513,11 @@ * before the table grows. * @param can_block If true creating the table blocks until enough memory - * is available (possibly indefinitely). Otherwise, + * is available (possibly indefinitely). Otherwise, * table creation does not block and returns immediately - * even if not enough memory is available. + * even if not enough memory is available. * @param op Item specific operations. All operations are compulsory. * @return True if successfully created the table. False otherwise. */ -bool cht_create(cht_t *h, size_t init_size, size_t min_size, size_t max_load, +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) { @@ -551,5 +551,5 @@ } - /* + /* * Cached item hashes are stored in item->rcu_link.func. Once the item * is deleted rcu_link.func will contain the value of invalid_hash. @@ -564,13 +564,13 @@ /** Allocates and initializes 2^order buckets. - * + * * All bucket heads are initialized to point to the sentinel node. - * + * * @param order The number of buckets to allocate is 2^order. * @param set_invalid Bucket heads are marked invalid if true; otherwise * they are marked N_NORMAL. * @param can_block If true memory allocation blocks until enough memory - * is available (possibly indefinitely). Otherwise, - * memory allocation does not block. + * is available (possibly indefinitely). Otherwise, + * memory allocation does not block. * @return Newly allocated and initialized buckets or NULL if not enough memory. */ @@ -578,5 +578,5 @@ { size_t bucket_cnt = (1 << order); - size_t bytes = + size_t bytes = sizeof(cht_buckets_t) + (bucket_cnt - 1) * sizeof(marked_ptr_t); cht_buckets_t *b = malloc(bytes, can_block ? 0 : FRAME_ATOMIC); @@ -587,6 +587,6 @@ b->order = order; - marked_ptr_t head_link = set_invalid - ? make_link(&sentinel, N_INVALID) + marked_ptr_t head_link = set_invalid + ? make_link(&sentinel, N_INVALID) : make_link(&sentinel, N_NORMAL); @@ -615,5 +615,5 @@ /** Destroys a CHT successfully created via cht_create(). - * + * * Waits for all outstanding concurrent operations to complete and * frees internal allocated resources. The table is however not cleared @@ -644,16 +644,16 @@ /** Returns the first item equal to the search key or NULL if not found. - * - * The call must be enclosed in a rcu_read_lock() unlock() pair. The + * + * The call must be enclosed in a rcu_read_lock() unlock() pair. The * returned item is guaranteed to be allocated until rcu_read_unlock() * although the item may be concurrently removed from the table by another * cpu. - * + * * Further items matching the key may be retrieved via cht_find_next(). - * + * * cht_find() sees the effects of any completed cht_remove(), cht_insert(). * If a concurrent remove or insert had not yet completed cht_find() may * or may not see the effects of it (eg it may find an item being removed). - * + * * @param h CHT to operate on. * @param key Search key as defined by cht_ops_t.key_equal() and .key_hash(). @@ -668,11 +668,11 @@ /** Returns the first item equal to the search key or NULL if not found. - * - * Unlike cht_find(), cht_find_lazy() may not see the effects of + * + * Unlike cht_find(), cht_find_lazy() may not see the effects of * cht_remove() or cht_insert() even though they have already completed. * It may take a couple of milliseconds for those changes to propagate - * and become visible to cht_find_lazy(). On the other hand, cht_find_lazy() + * and become visible to cht_find_lazy(). On the other hand, cht_find_lazy() * operates a bit faster than cht_find(). - * + * * See cht_find() for more details. */ @@ -693,6 +693,6 @@ cht_buckets_t *b = rcu_access(h->b); size_t idx = calc_bucket_idx(hash, b->order); - /* - * No need for access_once. b->head[idx] will point to an allocated node + /* + * No need for access_once. b->head[idx] will point to an allocated node * even if marked invalid until we exit rcu read section. */ @@ -706,11 +706,11 @@ } -/** Returns the next item matching \a item. - * - * Must be enclosed in a rcu_read_lock()/unlock() pair. Effects of +/** Returns the next item matching \a item. + * + * Must be enclosed in a rcu_read_lock()/unlock() pair. Effects of * completed cht_remove(), cht_insert() are guaranteed to be visible * to cht_find_next(). - * - * See cht_find() for more details. + * + * See cht_find() for more details. */ cht_link_t *cht_find_next(cht_t *h, const cht_link_t *item) @@ -721,11 +721,11 @@ } -/** Returns the next item matching \a item. - * - * Must be enclosed in a rcu_read_lock()/unlock() pair. Effects of +/** Returns the next item matching \a item. + * + * Must be enclosed in a rcu_read_lock()/unlock() pair. Effects of * completed cht_remove(), cht_insert() may or may not be visible * to cht_find_next_lazy(). - * - * See cht_find_lazy() for more details. + * + * See cht_find_lazy() for more details. */ cht_link_t *cht_find_next_lazy(cht_t *h, const cht_link_t *item) @@ -739,10 +739,10 @@ /** Searches the bucket at head for key using search_hash. */ -static inline cht_link_t *search_bucket(cht_t *h, marked_ptr_t head, void *key, +static inline cht_link_t *search_bucket(cht_t *h, marked_ptr_t head, void *key, size_t search_hash) { - /* + /* * It is safe to access nodes even outside of this bucket (eg when - * splitting the bucket). The resizer makes sure that any node we + * splitting the bucket). The resizer makes sure that any node we * may find by following the next pointers is allocated. */ @@ -759,7 +759,7 @@ } while (node_hash(h, cur) < search_hash); - /* + /* * Only search for an item with an equal key if cur is not the sentinel - * node or a node with a different hash. + * node or a node with a different hash. */ while (node_hash(h, cur) == search_hash) { @@ -771,7 +771,7 @@ cur = get_next(cur->link); assert(cur); - } - - /* + } + + /* * In the unlikely case that we have encountered a node whose cached * hash has been overwritten due to a pending rcu_call for it, skip @@ -787,8 +787,8 @@ /** Searches for the key while the table is undergoing a resize. */ -static cht_link_t *find_resizing(cht_t *h, void *key, size_t hash, +static cht_link_t *find_resizing(cht_t *h, void *key, size_t hash, marked_ptr_t old_head, size_t old_idx) { - assert(N_INVALID == get_mark(old_head)); + assert(N_INVALID == get_mark(old_head)); assert(h->new_b); @@ -799,5 +799,5 @@ /* Growing. */ if (h->b->order < h->new_b->order) { - /* + /* * Old bucket head is invalid, so it must have been already * moved. Make the new head visible if still not visible, ie @@ -805,11 +805,11 @@ */ if (N_INVALID == get_mark(new_head)) { - /* + /* * We should be searching a newly added bucket but the old - * moved bucket has not yet been split (its marked invalid) - * or we have not yet seen the split. + * moved bucket has not yet been split (its marked invalid) + * or we have not yet seen the split. */ if (grow_idx(old_idx) != new_idx) { - /* + /* * Search the moved bucket. It is guaranteed to contain * items of the newly added bucket that were present @@ -821,5 +821,5 @@ /* new_head is now the moved bucket, either valid or invalid. */ - /* + /* * The old bucket was definitely moved to new_head but the * change of new_head had not yet propagated to this cpu. @@ -829,9 +829,9 @@ * We could issue a read_barrier() and make the now valid * moved bucket head new_head visible, but instead fall back - * on using the old bucket. Although the old bucket head is - * invalid, it points to a node that is allocated and in the + * on using the old bucket. Although the old bucket head is + * invalid, it points to a node that is allocated and in the * right bucket. Before the node can be freed, it must be * unlinked from the head (or another item after that item - * modified the new_head) and a grace period must elapse. + * modified the new_head) and a grace period must elapse. * As a result had the node been already freed the grace * period preceeding the free() would make the unlink and @@ -855,17 +855,17 @@ /* - * h->b->head[move_src_idx] had already been moved to new_head + * h->b->head[move_src_idx] had already been moved to new_head * but the change to new_head had not yet propagated to us. */ if (N_INVALID == get_mark(new_head)) { /* - * new_head is definitely valid and we could make it visible - * to this cpu with a read_barrier(). Instead, use the bucket - * in the old table that was moved even though it is now marked + * new_head is definitely valid and we could make it visible + * to this cpu with a read_barrier(). Instead, use the bucket + * in the old table that was moved even though it is now marked * as invalid. The node it points to must be allocated because * a grace period would have to elapse before it could be freed; - * and the grace period would make the now valid new_head - * visible to all cpus. - * + * and the grace period would make the now valid new_head + * visible to all cpus. + * * Note that move_src_idx may not be the same as old_idx. * If move_src_idx != old_idx then old_idx is the bucket @@ -873,8 +873,8 @@ * appended to the moved bucket, ie it is added at the tail * of new_head. In that case an invalid old_head notes that - * it had already been merged into (the moved) new_head. + * it had already been merged into (the moved) new_head. * We will try to search that bucket first because it - * may contain some newly added nodes after the bucket - * join. Moreover, the bucket joining link may already be + * may contain some newly added nodes after the bucket + * join. Moreover, the bucket joining link may already be * visible even if new_head is not. Therefore, if we're * lucky we'll find the item via moved_old_head. In any @@ -895,6 +895,6 @@ if (move_src_idx != old_idx && get_next(old_head) != &sentinel) { /* - * Note that old_head (the bucket to be merged into new_head) - * points to an allocated join node (if non-null) even if marked + * Note that old_head (the bucket to be merged into new_head) + * points to an allocated join node (if non-null) even if marked * invalid. Before the resizer lets join nodes to be unlinked * (and freed) it sets old_head to NULL and waits for a grace period. @@ -909,10 +909,10 @@ return NULL; } else { - /* + /* * Resize is almost done. The resizer is waiting to make * sure all cpus see that the new table replaced the old one. */ assert(h->b->order == h->new_b->order); - /* + /* * The resizer must ensure all new bucket heads are visible before * replacing the old table. @@ -929,10 +929,10 @@ } -/** Inserts a unique item. Returns false if an equal item was already present. - * +/** Inserts a unique item. Returns false if an equal item was already present. + * * Use this function to atomically check if an equal/duplicate item had - * not yet been inserted into the table and to insert this item into the + * not yet been inserted into the table and to insert this item into the * table. - * + * * The following is @e NOT thread-safe, so do not use: * @code @@ -944,5 +944,5 @@ * } * @endcode - * + * * Replace such code with: * @code @@ -951,5 +951,5 @@ * // Whoops, someone beat us to it - an equal item 'dup_item' * // had already been inserted. - * free(item); + * free(item); * } else { * // Successfully inserted the item and we are guaranteed that @@ -957,5 +957,5 @@ * } * @endcode - * + * */ bool cht_insert_unique(cht_t *h, cht_link_t *item, cht_link_t **dup_item) @@ -1007,5 +1007,5 @@ } - inserted = insert_at(item, &wnd, walk_mode, &resizing); + inserted = insert_at(item, &wnd, walk_mode, &resizing); } while (!inserted); @@ -1016,11 +1016,11 @@ } -/** Inserts item between wnd.ppred and wnd.cur. - * +/** Inserts item between wnd.ppred and wnd.cur. + * * @param item Item to link to wnd.ppred and wnd.cur. * @param wnd The item will be inserted before wnd.cur. Wnd.ppred * must be N_NORMAL. - * @param walk_mode - * @param resizing Set to true only if the table is undergoing resize + * @param walk_mode + * @param resizing Set to true only if the table is undergoing resize * and it was not expected (ie walk_mode == WM_NORMAL). * @return True if the item was successfully linked to wnd.ppred. False @@ -1028,5 +1028,5 @@ * of wnd.cur has changed. */ -inline static bool insert_at(cht_link_t *item, const wnd_t *wnd, +inline static bool insert_at(cht_link_t *item, const wnd_t *wnd, walk_mode_t walk_mode, bool *resizing) { @@ -1076,5 +1076,5 @@ /** Returns true if the chain starting at cur has an item equal to \a item. - * + * * @param h CHT to operate on. * @param item Item whose duplicates the function looks for. @@ -1084,5 +1084,5 @@ * @return True if a non-deleted item equal to \a item exists in the table. */ -static inline bool has_duplicate(cht_t *h, const cht_link_t *item, size_t hash, +static inline bool has_duplicate(cht_t *h, const cht_link_t *item, size_t hash, cht_link_t *cur, cht_link_t **dup_item) { @@ -1095,7 +1095,7 @@ return false; - /* - * Load the most recent node marks. Otherwise we might pronounce a - * logically deleted node for a duplicate of the item just because + /* + * Load the most recent node marks. Otherwise we might pronounce a + * logically deleted node for a duplicate of the item just because * the deleted node's DEL mark had not yet propagated to this cpu. */ @@ -1107,5 +1107,5 @@ /** Returns an item that is equal to \a item starting in a chain at \a start. */ -static cht_link_t *find_duplicate(cht_t *h, const cht_link_t *item, size_t hash, +static cht_link_t *find_duplicate(cht_t *h, const cht_link_t *item, size_t hash, cht_link_t *start) { @@ -1114,5 +1114,5 @@ cht_link_t *cur = start; -try_again: +try_again: assert(cur); @@ -1128,5 +1128,5 @@ cur = get_next(cur->link); assert(cur); - } + } /* Skip logically deleted nodes with rcu_call() in progress. */ @@ -1147,5 +1147,5 @@ size_t removed = 0; - while (remove_pred(h, hash, h->op->key_equal, key)) + while (remove_pred(h, hash, h->op->key_equal, key)) ++removed; @@ -1153,11 +1153,11 @@ } -/** Removes a specific item from the table. - * - * The called must hold rcu read lock. - * +/** Removes a specific item from the table. + * + * The called must hold rcu read lock. + * * @param item Item presumably present in the table and to be removed. * @return True if the item was removed successfully; or false if it had - * already been deleted. + * already been deleted. */ bool cht_remove_item(cht_t *h, cht_link_t *item) @@ -1168,7 +1168,7 @@ assert(rcu_read_locked()); - /* + /* * Even though we know the node we want to delete we must unlink it - * from the correct bucket and from a clean/normal predecessor. Therefore, + * from the correct bucket and from a clean/normal predecessor. Therefore, * we search for it again from the beginning of the correct bucket. */ @@ -1213,12 +1213,12 @@ } - /* + /* * The item lookup is affected by a bucket join but effects of * the bucket join have not been seen while searching for the item. */ if (join_finishing && !join_completed(h, &wnd)) { - /* - * Bucket was appended at the end of another but the next - * ptr linking them together was not visible on this cpu. + /* + * Bucket was appended at the end of another but the next + * ptr linking them together was not visible on this cpu. * join_completed() makes this appended bucket visible. */ @@ -1237,5 +1237,5 @@ } - deleted = delete_at(h, &wnd, walk_mode, &deleted_but_gc, &resizing); + deleted = delete_at(h, &wnd, walk_mode, &deleted_but_gc, &resizing); } while (!deleted || deleted_but_gc); @@ -1245,13 +1245,13 @@ /** Unlinks wnd.cur from wnd.ppred and schedules a deferred free for the item. - * + * * Ignores nodes marked N_JOIN if walk mode is WM_LEAVE_JOIN. - * + * * @param h CHT to operate on. * @param wnd Points to the item to delete and its N_NORMAL predecessor. * @param walk_mode Bucket chaing walk mode. - * @param deleted_but_gc Set to true if the item had been logically deleted, + * @param deleted_but_gc Set to true if the item had been logically deleted, * but a garbage collecting walk of the bucket is in order for - * it to be fully unlinked. + * it to be fully unlinked. * @param resizing Set to true if the table is undergoing an unexpected * resize (ie walk_mode == WM_NORMAL). @@ -1259,5 +1259,5 @@ * delete operation must be retried. */ -static inline bool delete_at(cht_t *h, wnd_t *wnd, walk_mode_t walk_mode, +static inline bool delete_at(cht_t *h, wnd_t *wnd, walk_mode_t walk_mode, bool *deleted_but_gc, bool *resizing) { @@ -1289,12 +1289,12 @@ /** Marks cur logically deleted. Returns false to request a retry. */ -static inline bool mark_deleted(cht_link_t *cur, walk_mode_t walk_mode, +static inline bool mark_deleted(cht_link_t *cur, walk_mode_t walk_mode, bool *resizing) { assert(cur && cur != &sentinel); - /* + /* * Btw, we could loop here if the cas fails but let's not complicate - * things and let's retry from the head of the bucket. + * things and let's retry from the head of the bucket. */ @@ -1315,10 +1315,10 @@ mark_t cur_mark = get_mark(cur->link) & N_JOIN_FOLLOWS; - marked_ptr_t ret = + marked_ptr_t ret = cas_link(&cur->link, next, cur_mark, next, cur_mark | N_DELETED); if (ret != make_link(next, cur_mark)) return false; - } + } return true; @@ -1326,5 +1326,5 @@ /** Unlinks wnd.cur from wnd.ppred. Returns false if it should be retried. */ -static inline bool unlink_from_pred(wnd_t *wnd, walk_mode_t walk_mode, +static inline bool unlink_from_pred(wnd_t *wnd, walk_mode_t walk_mode, bool *resizing) { @@ -1355,5 +1355,5 @@ marked_ptr_t pred_link = make_link(wnd->cur, N_NORMAL); /* Link to cur's successor keeping/copying cur's JF mark. */ - marked_ptr_t next_link = make_link(next, cur_mark); + marked_ptr_t next_link = make_link(next, cur_mark); marked_ptr_t ret = _cas_link(wnd->ppred, pred_link, next_link); @@ -1361,5 +1361,5 @@ if (pred_link != ret) { /* If we're not resizing the table there are no JF/JN nodes. */ - *resizing = (walk_mode == WM_NORMAL) + *resizing = (walk_mode == WM_NORMAL) && (N_JOIN_FOLLOWS & get_mark(ret)); return false; @@ -1371,9 +1371,9 @@ /** Finds the first non-deleted item equal to \a pred_arg according to \a pred. - * + * * The function returns the candidate item in \a wnd. Logically deleted * nodes are garbage collected so the predecessor will most likely not - * be marked as deleted. - * + * be marked as deleted. + * * Unlike find_wnd_and_gc(), this function never returns a node that * is known to have already been marked N_DELETED. @@ -1382,5 +1382,5 @@ * collected, ie free in the background via rcu_call (except for join-nodes * if walk_mode == WM_LEAVE_JOIN). - * + * * @param h CHT to operate on. * @param hash Hash the search for. @@ -1392,8 +1392,8 @@ * @param resizing Set to true if the table is resizing but it was not * expected (ie walk_mode == WM_NORMAL). - * @return False if the operation has to be retried. True otherwise + * @return False if the operation has to be retried. True otherwise * (even if an equal item had not been found). */ -static bool find_wnd_and_gc_pred(cht_t *h, size_t hash, walk_mode_t walk_mode, +static bool find_wnd_and_gc_pred(cht_t *h, size_t hash, walk_mode_t walk_mode, equal_pred_t pred, void *pred_arg, wnd_t *wnd, bool *resizing) { @@ -1403,6 +1403,6 @@ return true; - /* - * A read barrier is not needed here to bring up the most recent + /* + * A read barrier is not needed here to bring up the most recent * node marks (esp the N_DELETED). At worst we'll try to delete * an already deleted node; fail in delete_at(); and retry. @@ -1411,5 +1411,5 @@ size_t cur_hash; -try_again: +try_again: cur_hash = node_hash(h, wnd->cur); @@ -1445,25 +1445,25 @@ /** Find the first item (deleted or not) with a hash greater or equal to \a hash. - * - * The function returns the first item with a hash that is greater or + * + * The function returns the first item with a hash that is greater or * equal to \a hash in \a wnd. Moreover it garbage collects logically * deleted node that have not yet been unlinked and freed. Therefore, * the returned node's predecessor will most likely be N_NORMAL. - * + * * Unlike find_wnd_and_gc_pred(), this function may return a node * that is known to had been marked N_DELETED. - * + * * @param h CHT to operate on. * @param hash Hash of the item to find. * @param walk_mode Bucket chain walk mode. - * @param[in,out] wnd wnd.cur denotes the first node of the chain. If the - * the operation is successful, \a wnd points to the desired + * @param[in,out] wnd wnd.cur denotes the first node of the chain. If the + * the operation is successful, \a wnd points to the desired * item. * @param resizing Set to true if a table resize was detected but walk_mode * suggested the table was not undergoing a resize. - * @return False indicates the operation must be retried. True otherwise + * @return False indicates the operation must be retried. True otherwise * (even if an item with exactly the same has was not found). */ -static bool find_wnd_and_gc(cht_t *h, size_t hash, walk_mode_t walk_mode, +static bool find_wnd_and_gc(cht_t *h, size_t hash, walk_mode_t walk_mode, wnd_t *wnd, bool *resizing) { @@ -1505,5 +1505,5 @@ } else { /* Ordinary deleted node or a deleted JOIN_FOLLOWS. */ - assert(walk_mode != WM_LEAVE_JOIN + assert(walk_mode != WM_LEAVE_JOIN || !((N_JOIN | N_JOIN_FOLLOWS) & get_mark(wnd->cur->link))); @@ -1525,8 +1525,8 @@ /** Returns true if a bucket join had already completed. - * - * May only be called if upd_resizing_head() indicates a bucket join + * + * May only be called if upd_resizing_head() indicates a bucket join * may be in progress. - * + * * If it returns false, the search must be retried in order to guarantee * all item that should have been encountered have been seen. @@ -1534,15 +1534,15 @@ static bool join_completed(cht_t *h, const wnd_t *wnd) { - /* - * The table is shrinking and the searched for item is in a bucket - * appended to another. Check that the link joining these two buckets + /* + * The table is shrinking and the searched for item is in a bucket + * appended to another. Check that the link joining these two buckets * is visible and if not, make it visible to this cpu. */ - /* - * Resizer ensures h->b->order stays the same for the duration of this + /* + * Resizer ensures h->b->order stays the same for the duration of this * func. We got here because there was an alternative head to search. * The resizer waits for all preexisting readers to finish after - * it + * it */ assert(h->b->order > h->new_b->order); @@ -1565,13 +1565,13 @@ size_t move_src_idx = grow_idx(shrink_idx(last_old_idx)); - /* - * Last node seen was in the joining bucket - if the searched - * for node is there we will find it. + /* + * Last node seen was in the joining bucket - if the searched + * for node is there we will find it. */ - if (move_src_idx != last_old_idx) + if (move_src_idx != last_old_idx) return true; } - /* + /* * Reached the end of the bucket but no nodes from the joining bucket * were seen. There should have at least been a JOIN node so we have @@ -1584,9 +1584,9 @@ /** When resizing returns the bucket head to start the search with in \a phead. - * + * * If a resize had been detected (eg cht_t.b.head[idx] is marked immutable). * upd_resizing_head() moves the bucket for \a hash from the old head * to the new head. Moreover, it splits or joins buckets as necessary. - * + * * @param h CHT to operate on. * @param hash Hash of an item whose chain we would like to traverse. @@ -1595,7 +1595,7 @@ * in progress and the bucket may have to traversed again * as indicated by join_completed(). - * @param[out] walk_mode Specifies how to interpret node marks. - */ -static void upd_resizing_head(cht_t *h, size_t hash, marked_ptr_t **phead, + * @param[out] walk_mode Specifies how to interpret node marks. + */ +static void upd_resizing_head(cht_t *h, size_t hash, marked_ptr_t **phead, bool *join_finishing, walk_mode_t *walk_mode) { @@ -1621,6 +1621,6 @@ if (move_dest_idx == new_idx) { assert(pmoved_head == pnew_head); - /* - * move_head() makes the new head of the moved bucket visible. + /* + * move_head() makes the new head of the moved bucket visible. * The new head may be marked with a JOIN_FOLLOWS */ @@ -1629,6 +1629,6 @@ } else { assert(pmoved_head != pnew_head); - /* - * The hash belongs to the bucket that is the result of splitting + /* + * The hash belongs to the bucket that is the result of splitting * the old/moved bucket, ie the bucket that contains the second * half of the split/old/moved bucket. @@ -1639,6 +1639,6 @@ size_t split_hash = calc_split_hash(new_idx, h->new_b->order); split_bucket(h, pmoved_head, pnew_head, split_hash); - /* - * split_bucket() makes the new head visible. No + /* + * split_bucket() makes the new head visible. No * JOIN_FOLLOWS in this part of split bucket. */ @@ -1653,6 +1653,6 @@ size_t move_src_idx = grow_idx(new_idx); - /* - * Complete moving the bucket from the old to the new table. + /* + * Complete moving the bucket from the old to the new table. * Makes a valid pnew_head visible if already moved. */ @@ -1667,5 +1667,5 @@ } - /* + /* * The resizer sets pold_head to &sentinel when all cpus are * guaranteed to see the bucket join. @@ -1681,6 +1681,6 @@ *walk_mode = WM_LEAVE_JOIN; } else { - /* - * Final stage of resize. The resizer is waiting for all + /* + * Final stage of resize. The resizer is waiting for all * readers to notice that the old table had been replaced. */ @@ -1700,13 +1700,13 @@ #endif -/** Moves an immutable head \a psrc_head of cht_t.b to \a pdest_head of cht_t.new_b. - * +/** Moves an immutable head \a psrc_head of cht_t.b to \a pdest_head of cht_t.new_b. + * * The function guarantees the move will be visible on this cpu once * it completes. In particular, *pdest_head will not be N_INVALID. - * + * * Unlike complete_head_move(), help_head_move() checks if the head had already * been moved and tries to avoid moving the bucket heads if possible. */ -static inline void help_head_move(marked_ptr_t *psrc_head, +static inline void help_head_move(marked_ptr_t *psrc_head, marked_ptr_t *pdest_head) { @@ -1729,6 +1729,6 @@ /** Initiates the move of the old head \a psrc_head. - * - * The move may be completed with help_head_move(). + * + * The move may be completed with help_head_move(). */ static void start_head_move(marked_ptr_t *psrc_head) @@ -1766,6 +1766,6 @@ cas_order_barrier(); - DBG(ret = ) - cas_link(psrc_head, next, N_CONST, next, N_INVALID); + DBG(ret = ) + cas_link(psrc_head, next, N_CONST, next, N_INVALID); assert(ret == make_link(next, N_CONST) || (N_INVALID == get_mark(ret))); cas_order_barrier(); @@ -1773,17 +1773,17 @@ /** Splits the bucket at psrc_head and links to the remainder from pdest_head. - * + * * Items with hashes greater or equal to \a split_hash are moved to bucket - * with head at \a pdest_head. - * + * with head at \a pdest_head. + * * @param h CHT to operate on. * @param psrc_head Head of the bucket to split (in cht_t.new_b). * @param pdest_head Head of the bucket that points to the second part * of the split bucket in psrc_head. (in cht_t.new_b) - * @param split_hash Hash of the first possible item in the remainder of + * @param split_hash Hash of the first possible item in the remainder of * psrc_head, ie the smallest hash pdest_head is allowed * to point to.. */ -static void split_bucket(cht_t *h, marked_ptr_t *psrc_head, +static void split_bucket(cht_t *h, marked_ptr_t *psrc_head, marked_ptr_t *pdest_head, size_t split_hash) { @@ -1794,9 +1794,9 @@ /* * L == Last node of the first part of the split bucket. That part - * remains in the original/src bucket. + * remains in the original/src bucket. * F == First node of the second part of the split bucket. That part * will be referenced from the dest bucket head. * - * We want to first mark a clean L as JF so that updaters unaware of + * We want to first mark a clean L as JF so that updaters unaware of * the split (or table resize): * - do not insert a new node between L and F @@ -1804,31 +1804,31 @@ * - do not unlink F * - * Then we can safely mark F as JN even if it has been marked deleted. - * Once F is marked as JN updaters aware of table resize will not + * Then we can safely mark F as JN even if it has been marked deleted. + * Once F is marked as JN updaters aware of table resize will not * attempt to unlink it (JN will have two predecessors - we cannot - * safely unlink from both at the same time). Updaters unaware of - * ongoing resize can reach F only via L and that node is already + * safely unlink from both at the same time). Updaters unaware of + * ongoing resize can reach F only via L and that node is already * marked JF, so they won't unlink F. - * + * * Last, link the new/dest head to F. - * - * - * 0) ,-- split_hash, first hash of the dest bucket - * v + * + * + * 0) ,-- split_hash, first hash of the dest bucket + * v * [src_head | N] -> .. -> [L] -> [F] * [dest_head | Inv] - * + * * 1) ,-- split_hash - * v + * v * [src_head | N] -> .. -> [JF] -> [F] * [dest_head | Inv] - * + * * 2) ,-- split_hash - * v + * v * [src_head | N] -> .. -> [JF] -> [JN] * [dest_head | Inv] - * + * * 3) ,-- split_hash - * v + * v * [src_head | N] -> .. -> [JF] -> [JN] * ^ @@ -1845,12 +1845,12 @@ /* There are nodes in the dest bucket, ie the second part of the split. */ if (wnd.cur != &sentinel) { - /* - * Mark the first node of the dest bucket as a join node so - * updaters do not attempt to unlink it if it is deleted. + /* + * Mark the first node of the dest bucket as a join node so + * updaters do not attempt to unlink it if it is deleted. */ mark_join_node(wnd.cur); cas_order_barrier(); } else { - /* + /* * Second part of the split bucket is empty. There are no nodes * to mark as JOIN nodes and there never will be. @@ -1868,14 +1868,14 @@ /** Finds and marks the last node of psrc_head w/ hash less than split_hash. - * - * Finds a node in psrc_head with the greatest hash that is strictly less - * than split_hash and marks it with N_JOIN_FOLLOWS. - * - * Returns a window pointing to that node. - * - * Any logically deleted nodes along the way are - * garbage collected; therefore, the predecessor node (if any) will most + * + * Finds a node in psrc_head with the greatest hash that is strictly less + * than split_hash and marks it with N_JOIN_FOLLOWS. + * + * Returns a window pointing to that node. + * + * Any logically deleted nodes along the way are + * garbage collected; therefore, the predecessor node (if any) will most * likely not be marked N_DELETED. - * + * * @param h CHT to operate on. * @param psrc_head Bucket head. @@ -1884,5 +1884,5 @@ * @param[out] wnd Points to the node marked with N_JOIN_FOLLOWS. */ -static void mark_join_follows(cht_t *h, marked_ptr_t *psrc_head, +static void mark_join_follows(cht_t *h, marked_ptr_t *psrc_head, size_t split_hash, wnd_t *wnd) { @@ -1896,8 +1896,8 @@ wnd->cur = get_next(*psrc_head); - /* + /* * Find the split window, ie the last node of the first part of * the split bucket and the its successor - the first node of - * the second part of the split bucket. Retry if GC failed. + * the second part of the split bucket. Retry if GC failed. */ if (!find_wnd_and_gc(h, split_hash, WM_MOVE_JOIN_FOLLOWS, wnd, &resizing)) @@ -1906,6 +1906,6 @@ /* Must not report that the table is resizing if WM_MOVE_JOIN_FOLLOWS.*/ assert(!resizing); - /* - * Mark the last node of the first half of the split bucket + /* + * Mark the last node of the first half of the split bucket * that a join node follows. It must be clean/normal. */ @@ -1913,7 +1913,7 @@ = cas_link(wnd->ppred, wnd->cur, N_NORMAL, wnd->cur, N_JOIN_FOLLOWS); - /* - * Successfully marked as a JF node or already marked that way (even - * if also marked deleted - unlinking the node will move the JF mark). + /* + * Successfully marked as a JF node or already marked that way (even + * if also marked deleted - unlinking the node will move the JF mark). */ done = (ret == make_link(wnd->cur, N_NORMAL)) @@ -1932,9 +1932,9 @@ mark_t mark = get_mark(join_node->link); - /* - * May already be marked as deleted, but it won't be unlinked + /* + * May already be marked as deleted, but it won't be unlinked * because its predecessor is marked with JOIN_FOLLOWS or CONST. */ - marked_ptr_t ret + marked_ptr_t ret = cas_link(&join_node->link, next, mark, next, mark | N_JOIN); @@ -1946,5 +1946,5 @@ /** Appends the bucket at psrc_head to the bucket at pdest_head. - * + * * @param h CHT to operate on. * @param psrc_head Bucket to merge with pdest_head. @@ -1952,5 +1952,5 @@ * @param split_hash The smallest hash psrc_head may contain. */ -static void join_buckets(cht_t *h, marked_ptr_t *psrc_head, +static void join_buckets(cht_t *h, marked_ptr_t *psrc_head, marked_ptr_t *pdest_head, size_t split_hash) { @@ -1959,18 +1959,18 @@ return; /* - * F == First node of psrc_head, ie the bucket we want to append + * F == First node of psrc_head, ie the bucket we want to append * to (ie join with) the bucket starting at pdest_head. * L == Last node of pdest_head, ie the bucket that psrc_head will - * be appended to. - * - * (1) We first mark psrc_head immutable to signal that a join is - * in progress and so that updaters unaware of the join (or table + * be appended to. + * + * (1) We first mark psrc_head immutable to signal that a join is + * in progress and so that updaters unaware of the join (or table * resize): * - do not insert new nodes between the head psrc_head and F * - do not unlink F (it may already be marked deleted) - * + * * (2) Next, F is marked as a join node. Updaters aware of table resize - * will not attempt to unlink it. We cannot safely/atomically unlink - * the join node because it will be pointed to from two different + * will not attempt to unlink it. We cannot safely/atomically unlink + * the join node because it will be pointed to from two different * buckets. Updaters unaware of resize will fail to unlink the join * node due to the head being marked immutable. @@ -1978,48 +1978,48 @@ * (3) Then the tail of the bucket at pdest_head is linked to the join * node. From now on, nodes in both buckets can be found via pdest_head. - * + * * (4) Last, mark immutable psrc_head as invalid. It signals updaters * that the join is complete and they can insert new nodes (originally - * destined for psrc_head) into pdest_head. - * + * destined for psrc_head) into pdest_head. + * * Note that pdest_head keeps pointing at the join node. This allows * lookups and updaters to determine if they should see a link between * the tail L and F when searching for nodes originally in psrc_head - * via pdest_head. If they reach the tail of pdest_head without + * via pdest_head. If they reach the tail of pdest_head without * encountering any nodes of psrc_head, either there were no nodes * in psrc_head to begin with or the link between L and F did not * yet propagate to their cpus. If psrc_head was empty, it remains - * NULL. Otherwise psrc_head points to a join node (it will not be + * NULL. Otherwise psrc_head points to a join node (it will not be * unlinked until table resize completes) and updaters/lookups * should issue a read_barrier() to make the link [L]->[JN] visible. - * - * 0) ,-- split_hash, first hash of the src bucket - * v + * + * 0) ,-- split_hash, first hash of the src bucket + * v * [dest_head | N]-> .. -> [L] - * [src_head | N]--> [F] -> .. + * [src_head | N]--> [F] -> .. * ^ * ` split_hash, first hash of the src bucket - * + * * 1) ,-- split_hash - * v + * v * [dest_head | N]-> .. -> [L] - * [src_head | C]--> [F] -> .. - * + * [src_head | C]--> [F] -> .. + * * 2) ,-- split_hash - * v + * v * [dest_head | N]-> .. -> [L] - * [src_head | C]--> [JN] -> .. - * + * [src_head | C]--> [JN] -> .. + * * 3) ,-- split_hash - * v + * v * [dest_head | N]-> .. -> [L] --+ * v - * [src_head | C]-------------> [JN] -> .. - * + * [src_head | C]-------------> [JN] -> .. + * * 4) ,-- split_hash - * v + * v * [dest_head | N]-> .. -> [L] --+ * v - * [src_head | Inv]-----------> [JN] -> .. + * [src_head | Inv]-----------> [JN] -> .. */ @@ -2038,5 +2038,5 @@ link_to_join_node(h, pdest_head, join_node, split_hash); cas_order_barrier(); - } + } DBG(marked_ptr_t ret = ) @@ -2049,5 +2049,5 @@ /** Links the tail of pdest_head to join_node. - * + * * @param h CHT to operate on. * @param pdest_head Head of the bucket whose tail is to be linked to join_node. @@ -2057,5 +2057,5 @@ * (originally) in pdest_head. */ -static void link_to_join_node(cht_t *h, marked_ptr_t *pdest_head, +static void link_to_join_node(cht_t *h, marked_ptr_t *pdest_head, cht_link_t *join_node, size_t split_hash) { @@ -2077,5 +2077,5 @@ if (wnd.cur != &sentinel) { /* Must be from the new appended bucket. */ - assert(split_hash <= node_hash(h, wnd.cur) + assert(split_hash <= node_hash(h, wnd.cur) || h->invalid_hash == node_hash(h, wnd.cur)); return; @@ -2083,5 +2083,5 @@ /* Reached the tail of pdest_head - link it to the join node. */ - marked_ptr_t ret = + marked_ptr_t ret = cas_link(wnd.ppred, &sentinel, N_NORMAL, join_node, N_NORMAL); @@ -2090,6 +2090,6 @@ } -/** Instructs RCU to free the item once all preexisting references are dropped. - * +/** Instructs RCU to free the item once all preexisting references are dropped. + * * The item is freed via op->remove_callback(). */ @@ -2098,5 +2098,5 @@ assert(item != &sentinel); - /* + /* * remove_callback only works as rcu_func_t because rcu_link is the first * field in cht_link_t. @@ -2108,6 +2108,6 @@ /** Notes that an item had been unlinked from the table and shrinks it if needed. - * - * If the number of items in the table drops below 1/4 of the maximum + * + * If the number of items in the table drops below 1/4 of the maximum * allowed load the table is shrunk in the background. */ @@ -2129,6 +2129,6 @@ } -/** Notes an item had been inserted and grows the table if needed. - * +/** Notes an item had been inserted and grows the table if needed. + * * The table is resized in the background. */ @@ -2192,5 +2192,5 @@ /* Failed to alloc a new table - try next time the resizer is run. */ - if (!h->new_b) + if (!h->new_b) return; @@ -2199,6 +2199,6 @@ size_t old_bucket_cnt = (1 << h->b->order); - /* - * Give updaters a chance to help out with the resize. Do the minimum + /* + * Give updaters a chance to help out with the resize. Do the minimum * work needed to announce a resize is in progress, ie start moving heads. */ @@ -2227,8 +2227,8 @@ } - /* + /* * Wait for all updaters to notice the new heads. Once everyone sees * the invalid old bucket heads they will know a resize is in progress - * and updaters will modify the correct new buckets. + * and updaters will modify the correct new buckets. */ rcu_synchronize(); @@ -2241,7 +2241,7 @@ } - /* + /* * Wait for everyone to notice that buckets were split, ie link connecting - * the join follows and join node has been cut. + * the join follows and join node has been cut. */ rcu_synchronize(); @@ -2278,5 +2278,5 @@ /* Failed to alloc a new table - try next time the resizer is run. */ - if (!h->new_b) + if (!h->new_b) return; @@ -2286,6 +2286,6 @@ size_t old_bucket_cnt = (1 << h->b->order); - /* - * Give updaters a chance to help out with the resize. Do the minimum + /* + * Give updaters a chance to help out with the resize. Do the minimum * work needed to announce a resize is in progress, ie start moving heads. */ @@ -2318,13 +2318,13 @@ /* This bucket should join the moved bucket. */ size_t split_hash = calc_split_hash(old_idx, h->b->order); - join_buckets(h, &h->b->head[old_idx], &h->new_b->head[new_idx], + join_buckets(h, &h->b->head[old_idx], &h->new_b->head[new_idx], split_hash); } } - /* + /* * Wait for all updaters to notice the new heads. Once everyone sees * the invalid old bucket heads they will know a resize is in progress - * and updaters will modify the correct new buckets. + * and updaters will modify the correct new buckets. */ rcu_synchronize(); @@ -2389,5 +2389,5 @@ /** Clears the join_node's N_JOIN mark frees it if marked N_DELETED as well. */ -static void clear_join_and_gc(cht_t *h, cht_link_t *join_node, +static void clear_join_and_gc(cht_t *h, cht_link_t *join_node, marked_ptr_t *new_head) { @@ -2404,5 +2404,5 @@ mark_t cleared_mark = get_mark(jn_link) & N_DELETED; - marked_ptr_t ret = + marked_ptr_t ret = _cas_link(&join_node->link, jn_link, make_link(next, cleared_mark)); @@ -2429,5 +2429,5 @@ }; - done = find_wnd_and_gc_pred(h, jn_hash, WM_NORMAL, same_node_pred, + done = find_wnd_and_gc_pred(h, jn_hash, WM_NORMAL, same_node_pred, join_node, &wnd, &resizing); @@ -2452,9 +2452,9 @@ * Find the non-deleted node with a JF mark and clear the JF mark. * The JF node may be deleted and/or the mark moved to its neighbors - * at any time. Therefore, we GC deleted nodes until we find the JF - * node in order to remove stale/deleted JF nodes left behind eg by - * delayed threads that did not yet get a chance to unlink the deleted - * JF node and move its mark. - * + * at any time. Therefore, we GC deleted nodes until we find the JF + * node in order to remove stale/deleted JF nodes left behind eg by + * delayed threads that did not yet get a chance to unlink the deleted + * JF node and move its mark. + * * Note that the head may be marked JF (but never DELETED). */ @@ -2481,8 +2481,8 @@ if (is_jf_node) { cht_link_t *next = get_next(*cur_link); - marked_ptr_t ret = + marked_ptr_t ret = cas_link(cur_link, next, N_JOIN_FOLLOWS, &sentinel, N_NORMAL); - assert(next == &sentinel + assert(next == &sentinel || ((N_JOIN | N_JOIN_FOLLOWS) & get_mark(ret))); @@ -2491,6 +2491,6 @@ break; } else { - /* - * The JF node had been deleted or a new node inserted + /* + * The JF node had been deleted or a new node inserted * right after it. Retry from the head. */ @@ -2500,5 +2500,5 @@ } else { wnd.ppred = cur_link; - wnd.cur = get_next(*cur_link); + wnd.cur = get_next(*cur_link); } } @@ -2512,6 +2512,6 @@ } -/** Returns the first possible hash following a bucket split point. - * +/** Returns the first possible hash following a bucket split point. + * * In other words the returned hash is the smallest possible hash * the remainder of the split bucket may contain. @@ -2558,5 +2558,5 @@ static inline size_t node_hash(cht_t *h, const cht_link_t *item) { - assert(item->hash == h->invalid_hash + assert(item->hash == h->invalid_hash || item->hash == sentinel.hash || item->hash == calc_node_hash(h, item)); @@ -2569,5 +2569,5 @@ { assert(item != &sentinel); - /* + /* * Clear the lowest order bit in order for sentinel's node hash * to be the greatest possible. @@ -2624,13 +2624,13 @@ /** Compare-and-swaps a next item link. */ -static inline marked_ptr_t cas_link(marked_ptr_t *link, const cht_link_t *cur_next, +static inline marked_ptr_t cas_link(marked_ptr_t *link, const cht_link_t *cur_next, mark_t cur_mark, const cht_link_t *new_next, mark_t new_mark) { - return _cas_link(link, make_link(cur_next, cur_mark), + return _cas_link(link, make_link(cur_next, cur_mark), make_link(new_next, new_mark)); } /** Compare-and-swaps a next item link. */ -static inline marked_ptr_t _cas_link(marked_ptr_t *link, marked_ptr_t cur, +static inline marked_ptr_t _cas_link(marked_ptr_t *link, marked_ptr_t cur, marked_ptr_t new) { @@ -2640,11 +2640,11 @@ * have to be ordered wrt to other cas(y) to a different location y * on the same cpu. - * - * cas(x) must act as a write barrier on x, ie if cas(x) succeeds - * and is observed by another cpu, then all cpus must be able to + * + * cas(x) must act as a write barrier on x, ie if cas(x) succeeds + * and is observed by another cpu, then all cpus must be able to * make the effects of cas(x) visible just by issuing a load barrier. * For example: * cpu1 cpu2 cpu3 - * cas(x, 0 -> 1), succeeds + * cas(x, 0 -> 1), succeeds * cas(x, 0 -> 1), fails * MB, to order load of x in cas and store to y @@ -2652,19 +2652,19 @@ * sees y == 7 * loadMB must be enough to make cas(x) on cpu3 visible to cpu1, ie x == 1. - * + * * If cas() did not work this way: * a) our head move protocol would not be correct. * b) freeing an item linked to a moved head after another item was * inserted in front of it, would require more than one grace period. - * + * * Ad (a): In the following example, cpu1 starts moving old_head * to new_head, cpu2 completes the move and cpu3 notices cpu2 * completed the move before cpu1 gets a chance to notice cpu2 - * had already completed the move. Our requirements for cas() - * assume cpu3 will see a valid and mutable value in new_head - * after issuing a load memory barrier once it has determined - * the old_head's value had been successfully moved to new_head + * had already completed the move. Our requirements for cas() + * assume cpu3 will see a valid and mutable value in new_head + * after issuing a load memory barrier once it has determined + * the old_head's value had been successfully moved to new_head * (because it sees old_head marked invalid). - * + * * cpu1 cpu2 cpu3 * cas(old_head, , ), succeeds @@ -2672,24 +2672,24 @@ * // Move from old_head to new_head started, now the interesting stuff: * cas(new_head, <0, Inv>, ), succeeds - * + * * cas(new_head, <0, Inv>, ), but fails * cas-order-barrier * cas(old_head, , ), succeeds - * + * * Sees old_head marked Inv (by cpu2) * load-MB * assert(new_head == ) - * + * * cas-order-barrier - * + * * Even though cpu1 did not yet issue a cas-order-barrier, cpu1's store * to new_head (successful cas()) must be made visible to cpu3 with * a load memory barrier if cpu1's store to new_head is visible * on another cpu (cpu2) and that cpu's (cpu2's) store to old_head - * is already visible to cpu3. * + * is already visible to cpu3. * */ void *expected = (void*)cur; - /* + /* * Use the acquire-release model, although we could probably * get away even with the relaxed memory model due to our use Index: kernel/generic/src/adt/hash_table.c =================================================================== --- kernel/generic/src/adt/hash_table.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/adt/hash_table.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -2,5 +2,5 @@ * Copyright (c) 2008 Jakub Jermar * Copyright (c) 2012 Adam Hraska - * + * * All rights reserved. * @@ -37,11 +37,11 @@ /* * This is an implementation of a generic resizable chained hash table. - * - * The table grows to 2*n+1 buckets each time, starting at n == 89, + * + * The table grows to 2*n+1 buckets each time, starting at n == 89, * per Thomas Wang's recommendation: * http://www.concentric.net/~Ttwang/tech/hashsize.htm - * + * * This policy produces prime table sizes for the first five resizes - * and generally produces table sizes which are either prime or + * and generally produces table sizes which are either prime or * have fairly large (prime/odd) divisors. Having a prime table size * mitigates the use of suboptimal hash functions and distributes @@ -79,5 +79,5 @@ * @param h Hash table structure. Will be initialized by this call. * @param init_size Initial desired number of hash table buckets. Pass zero - * if you want the default initial size. + * if you want the default initial size. * @param max_load The table is resized when the average load per bucket * exceeds this number. Pass zero if you want the default. @@ -86,5 +86,5 @@ * upon removal. equal() is optional if and only if * hash_table_insert_unique() will never be invoked. - * All other operations are mandatory. + * All other operations are mandatory. * * @return True on success @@ -210,6 +210,6 @@ * @param h Hash table. * @param item Item to be inserted into the hash table. - * - * @return False if such an item had already been inserted. + * + * @return False if such an item had already been inserted. * @return True if the inserted item was the only item with such a lookup key. */ @@ -225,6 +225,6 @@ /* Check for duplicates. */ list_foreach(h->bucket[idx], link, ht_link_t, cur_link) { - /* - * We could filter out items using their hashes first, but + /* + * We could filter out items using their hashes first, but * calling equal() might very well be just as fast. */ @@ -255,7 +255,7 @@ list_foreach(h->bucket[idx], link, ht_link_t, cur_link) { - /* - * Is this is the item we are looking for? We could have first - * checked if the hashes match but op->key_equal() may very well be + /* + * Is this is the item we are looking for? We could have first + * checked if the hashes match but op->key_equal() may very well be * just as fast as op->hash(). */ @@ -278,7 +278,7 @@ assert(cur); ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); - /* - * Is this is the item we are looking for? We could have first - * checked if the hashes match but op->equal() may very well be + /* + * Is this is the item we are looking for? We could have first + * checked if the hashes match but op->equal() may very well be * just as fast as op->hash(). */ @@ -298,5 +298,5 @@ * @param key Array of keys that will be compared against items of * the hash table. - * + * * @return Returns the number of removed items. */ @@ -342,12 +342,12 @@ * * @param h Hash table. - * @param f Function to be applied. Return false if no more items + * @param f Function to be applied. Return false if no more items * should be visited. The functor may only delete the supplied - * item. It must not delete the successor of the item passed + * item. It must not delete the successor of the item passed * in the first argument. * @param arg Argument to be passed to the function. */ void hash_table_apply(hash_table_t *h, bool (*f)(ht_link_t *, void *), void *arg) -{ +{ assert(f); assert(h && h->bucket); @@ -361,6 +361,6 @@ list_foreach_safe(h->bucket[idx], cur, next) { ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); - /* - * The next pointer had already been saved. f() may safely + /* + * The next pointer had already been saved. f() may safely * delete cur (but not next!). */ @@ -409,6 +409,6 @@ { if (h->item_cnt <= h->full_item_cnt / 4 && HT_MIN_BUCKETS < h->bucket_cnt) { - /* - * Keep the bucket_cnt odd (possibly also prime). + /* + * Keep the bucket_cnt odd (possibly also prime). * Shrink from 2n + 1 to n. Integer division discards the +1. */ @@ -430,5 +430,5 @@ /** Allocates and rehashes items to a new table. Frees the old table. */ -static void resize(hash_table_t *h, size_t new_bucket_cnt) +static void resize(hash_table_t *h, size_t new_bucket_cnt) { assert(h && h->bucket); Index: kernel/generic/src/adt/list.c =================================================================== --- kernel/generic/src/adt/list.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/adt/list.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -78,5 +78,5 @@ void list_splice(list_t *list, link_t *pos) { - if (list_empty(list)) + if (list_empty(list)) return; Index: kernel/generic/src/console/cmd.c =================================================================== --- kernel/generic/src/console/cmd.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/console/cmd.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -277,5 +277,5 @@ .len = sizeof(set_buf) }, - { + { .type = ARG_TYPE_INT } @@ -334,5 +334,5 @@ .len = sizeof(call0_buf) }, - { + { .type = ARG_TYPE_VAR, .buffer = carg1_buf, @@ -357,10 +357,10 @@ .len = sizeof(call0_buf) }, - { + { .type = ARG_TYPE_VAR, .buffer = carg1_buf, .len = sizeof(carg1_buf) }, - { + { .type = ARG_TYPE_VAR, .buffer = carg2_buf, @@ -385,15 +385,15 @@ .len = sizeof(call0_buf) }, - { + { .type = ARG_TYPE_VAR, .buffer = carg1_buf, .len = sizeof(carg1_buf) }, - { + { .type = ARG_TYPE_VAR, .buffer = carg2_buf, .len = sizeof(carg2_buf) }, - { + { .type = ARG_TYPE_VAR, .buffer = carg3_buf, @@ -952,5 +952,5 @@ } - spinlock_unlock(&cmd_lock); + spinlock_unlock(&cmd_lock); return 1; @@ -1087,5 +1087,5 @@ arch_construct_function(&fptr, (void *) symaddr, (void *) cmd_call2); - printf("Calling f(%#" PRIxn ", %#" PRIxn "): %p: %s\n", + printf("Calling f(%#" PRIxn ", %#" PRIxn "): %p: %s\n", arg1, arg2, (void *) symaddr, symbol); printf("Result: %#" PRIxn "\n", fnc(arg1, arg2)); Index: kernel/generic/src/cpu/cpu_mask.c =================================================================== --- kernel/generic/src/cpu/cpu_mask.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/cpu/cpu_mask.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -56,5 +56,5 @@ assert(cpu_cnt <= config.cpu_count); - for (size_t active_word = 0; + for (size_t active_word = 0; (active_word + 1) * word_bit_cnt <= cpu_cnt; ++active_word) { @@ -70,6 +70,6 @@ } -/** Sets bits corresponding to the active cpus, ie the first - * config.cpu_active cpus. +/** Sets bits corresponding to the active cpus, ie the first + * config.cpu_active cpus. */ void cpu_mask_active(cpu_mask_t *cpus) Index: kernel/generic/src/ipc/ipc.c =================================================================== --- kernel/generic/src/ipc/ipc.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/ipc/ipc.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -69,5 +69,5 @@ static slab_cache_t *answerbox_cache; -slab_cache_t *phone_cache = NULL; +slab_cache_t *phone_cache = NULL; /** Initialize a call structure. @@ -725,5 +725,5 @@ */ spinlock_unlock(&TASK->active_calls_lock); - return; + return; } Index: kernel/generic/src/ipc/ops/dataread.c =================================================================== --- kernel/generic/src/ipc/ops/dataread.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/ipc/ops/dataread.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -1,4 +1,4 @@ /* - * Copyright (c) 2012 Jakub Jermar + * Copyright (c) 2012 Jakub Jermar * All rights reserved. * Index: kernel/generic/src/ipc/ops/datawrite.c =================================================================== --- kernel/generic/src/ipc/ops/datawrite.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/ipc/ops/datawrite.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -1,4 +1,4 @@ /* - * Copyright (c) 2012 Jakub Jermar + * Copyright (c) 2012 Jakub Jermar * All rights reserved. * Index: kernel/generic/src/ipc/ops/debug.c =================================================================== --- kernel/generic/src/ipc/ops/debug.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/ipc/ops/debug.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -1,4 +1,4 @@ /* - * Copyright (c) 2008 Jiri Svoboda + * Copyright (c) 2008 Jiri Svoboda * All rights reserved. * Index: kernel/generic/src/ipc/ops/pagein.c =================================================================== --- kernel/generic/src/ipc/ops/pagein.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/ipc/ops/pagein.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -1,4 +1,4 @@ /* - * Copyright (c) 2016 Jakub Jermar + * Copyright (c) 2016 Jakub Jermar * All rights reserved. * Index: kernel/generic/src/ipc/ops/sharein.c =================================================================== --- kernel/generic/src/ipc/ops/sharein.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/ipc/ops/sharein.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -1,4 +1,4 @@ /* - * Copyright (c) 2012 Jakub Jermar + * Copyright (c) 2012 Jakub Jermar * All rights reserved. * Index: kernel/generic/src/ipc/ops/shareout.c =================================================================== --- kernel/generic/src/ipc/ops/shareout.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/ipc/ops/shareout.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -1,4 +1,4 @@ /* - * Copyright (c) 2012 Jakub Jermar + * Copyright (c) 2012 Jakub Jermar * All rights reserved. * Index: kernel/generic/src/ipc/ops/stchngath.c =================================================================== --- kernel/generic/src/ipc/ops/stchngath.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/ipc/ops/stchngath.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -1,4 +1,4 @@ /* - * Copyright (c) 2012 Jakub Jermar + * Copyright (c) 2012 Jakub Jermar * All rights reserved. * Index: kernel/generic/src/ipc/sysipc.c =================================================================== --- kernel/generic/src/ipc/sysipc.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/ipc/sysipc.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -186,5 +186,5 @@ * concurrently executing forget operation is forced to * release its active_calls_lock and lose the race to - * forget this soon to be answered call. + * forget this soon to be answered call. */ spinlock_lock(&answer->sender->active_calls_lock); @@ -695,5 +695,5 @@ saved = false; - errno_t rc = copy_from_uspace(&call->data.args, &data->args, + errno_t rc = copy_from_uspace(&call->data.args, &data->args, sizeof(call->data.args)); if (rc != EOK) { Index: kernel/generic/src/ipc/sysipc_ops.c =================================================================== --- kernel/generic/src/ipc/sysipc_ops.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/ipc/sysipc_ops.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -1,4 +1,4 @@ /* - * Copyright (c) 2012 Jakub Jermar + * Copyright (c) 2012 Jakub Jermar * All rights reserved. * Index: kernel/generic/src/lib/str.c =================================================================== --- kernel/generic/src/lib/str.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/lib/str.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -491,5 +491,5 @@ if (c1 == 0 || c2 == 0) - break; + break; } @@ -545,5 +545,5 @@ break; - ++len; + ++len; } Index: kernel/generic/src/log/log.c =================================================================== --- kernel/generic/src/log/log.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/log/log.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -92,5 +92,5 @@ */ void log_init(void) -{ +{ event_set_unmask_callback(EVENT_KLOG, log_update); atomic_set(&log_inited, true); @@ -112,5 +112,5 @@ /** Append data to the currently open log entry. - * + * * This function requires that the log_lock is acquired by the caller. */ @@ -143,5 +143,5 @@ /** Begin writing an entry to the log. - * + * * This acquires the log and output buffer locks, so only calls to log_* functions should * be used until calling log_end. @@ -167,5 +167,5 @@ /** Finish writing an entry to the log. - * + * * This releases the log and output buffer locks. */ @@ -233,5 +233,5 @@ /** Append a message to the currently being written entry. - * + * * Requires that an entry has been started using log_begin() */ @@ -253,5 +253,5 @@ /** Append a message to the currently being written entry. - * + * * Requires that an entry has been started using log_begin() */ @@ -269,5 +269,5 @@ /** Log a message to the kernel log. - * + * * This atomically appends a log entry. * The resulting message should not contain a trailing newline, as the log @@ -339,5 +339,5 @@ if (entry_len > PAGE_SIZE) { - /* + /* * Since we limit data transfer * to uspace to a maximum of PAGE_SIZE Index: kernel/generic/src/mm/as.c =================================================================== --- kernel/generic/src/mm/as.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/mm/as.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -344,5 +344,5 @@ * page. */ - int const gp = (guarded || + int const gp = (guarded || (area->flags & AS_AREA_GUARD)) ? 1 : 0; Index: kernel/generic/src/mm/backend_elf.c =================================================================== --- kernel/generic/src/mm/backend_elf.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/mm/backend_elf.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -349,5 +349,5 @@ frame = PTE_GET_FRAME(&pte); - } + } } else if (upage >= start_anon) { /* @@ -385,5 +385,5 @@ PAGE_SIZE - pad_lo - pad_hi); if (entry->p_flags & PF_X) { - smc_coherence_block((void *) (kpage + pad_lo), + smc_coherence_block((void *) (kpage + pad_lo), PAGE_SIZE - pad_lo - pad_hi); } Index: kernel/generic/src/mm/backend_phys.c =================================================================== --- kernel/generic/src/mm/backend_phys.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/mm/backend_phys.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -61,5 +61,5 @@ typedef struct { uintptr_t base; - size_t frames; + size_t frames; } phys_shared_data_t; Index: kernel/generic/src/mm/frame.c =================================================================== --- kernel/generic/src/mm/frame.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/mm/frame.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -288,5 +288,5 @@ NO_TRACE static size_t find_free_zone_lowprio(size_t count, zone_flags_t flags, pfn_t constraint, size_t hint) -{ +{ for (size_t pos = 0; pos < zones.count; pos++) { size_t i = (pos + hint) % zones.count; Index: kernel/generic/src/mm/km.c =================================================================== --- kernel/generic/src/mm/km.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/mm/km.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -53,5 +53,5 @@ static ra_arena_t *km_ni_arena; -#define DEFERRED_PAGES_MAX (PAGE_SIZE / sizeof(uintptr_t)) +#define DEFERRED_PAGES_MAX (PAGE_SIZE / sizeof(uintptr_t)) /** Number of freed pages in the deferred buffer. */ @@ -188,7 +188,7 @@ { uintptr_t page; - size_t offs; - - offs = paddr - ALIGN_DOWN(paddr, FRAME_SIZE); + size_t offs; + + offs = paddr - ALIGN_DOWN(paddr, FRAME_SIZE); page = km_map_aligned(ALIGN_DOWN(paddr, FRAME_SIZE), ALIGN_UP(size + offs, FRAME_SIZE), flags); @@ -205,7 +205,7 @@ void km_unmap(uintptr_t vaddr, size_t size) { - size_t offs; - - offs = vaddr - ALIGN_DOWN(vaddr, PAGE_SIZE); + size_t offs; + + offs = vaddr - ALIGN_DOWN(vaddr, PAGE_SIZE); km_unmap_aligned(ALIGN_DOWN(vaddr, PAGE_SIZE), ALIGN_UP(size + offs, PAGE_SIZE)); @@ -258,5 +258,5 @@ page = km_map(frame, PAGE_SIZE, PAGE_READ | PAGE_WRITE | PAGE_CACHEABLE); - if (!page) { + if (!page) { frame_free(frame, 1); goto lowmem; Index: kernel/generic/src/mm/page.c =================================================================== --- kernel/generic/src/mm/page.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/mm/page.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -178,5 +178,5 @@ /** Make the mapping shared by all page tables (not address spaces). - * + * * @param base Starting virtual address of the range that is made global. * @param size Size of the address range that is made global. Index: kernel/generic/src/mm/slab.c =================================================================== --- kernel/generic/src/mm/slab.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/mm/slab.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -39,5 +39,5 @@ * * with the following exceptions: - * @li empty slabs are deallocated immediately + * @li empty slabs are deallocated immediately * (in Linux they are kept in linked list, in Solaris ???) * @li empty magazines are deallocated when not needed @@ -52,11 +52,11 @@ * good SMP scaling. * - * When a new object is being allocated, it is first checked, if it is + * When a new object is being allocated, it is first checked, if it is * available in a CPU-bound magazine. If it is not found there, it is * allocated from a CPU-shared slab - if a partially full one is found, - * it is used, otherwise a new one is allocated. + * it is used, otherwise a new one is allocated. * * When an object is being deallocated, it is put to a CPU-bound magazine. - * If there is no such magazine, a new one is allocated (if this fails, + * If there is no such magazine, a new one is allocated (if this fails, * the object is deallocated into slab). If the magazine is full, it is * put into cpu-shared list of magazines and a new one is allocated. @@ -79,5 +79,5 @@ * the frame allocator fails to allocate a frame, it calls slab_reclaim(). * It tries 'light reclaim' first, then brutal reclaim. The light reclaim - * releases slabs from cpu-shared magazine-list, until at least 1 slab + * releases slabs from cpu-shared magazine-list, until at least 1 slab * is deallocated in each cache (this algorithm should probably change). * The brutal reclaim removes all cached objects, even from CPU-bound @@ -90,5 +90,5 @@ * to add cpu-cached magazine cache (which would allocate it's magazines * from non-cpu-cached mag. cache). This would provide a nice per-cpu - * buffer. The other possibility is to use the per-cache + * buffer. The other possibility is to use the per-cache * 'empty-magazine-list', which decreases competing for 1 per-system * magazine cache. @@ -660,5 +660,5 @@ } -/** Create slab cache +/** Create slab cache * */ Index: kernel/generic/src/proc/program.c =================================================================== --- kernel/generic/src/proc/program.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/proc/program.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -244,5 +244,5 @@ return rc; - // FIXME: control the permissions + // FIXME: control the permissions perm_set(prg.task, perm_get(TASK)); program_ready(&prg); Index: kernel/generic/src/proc/thread.c =================================================================== --- kernel/generic/src/proc/thread.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/proc/thread.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -546,14 +546,14 @@ /** Interrupts an existing thread so that it may exit as soon as possible. - * - * Threads that are blocked waiting for a synchronization primitive + * + * Threads that are blocked waiting for a synchronization primitive * are woken up with a return code of EINTR if the * blocking call was interruptable. See waitq_sleep_timeout(). - * + * * The caller must guarantee the thread object is valid during the entire * function, eg by holding the threads_lock lock. - * + * * Interrupted threads automatically exit when returning back to user space. - * + * * @param thread A valid thread object. The caller must guarantee it * will remain valid until thread_interrupt() exits. @@ -575,5 +575,5 @@ /** Returns true if the thread was interrupted. - * + * * @param thread A valid thread object. User must guarantee it will * be alive during the entire call. @@ -693,5 +693,5 @@ * @param usec Number of microseconds to sleep. * - */ + */ void thread_usleep(uint32_t usec) { Index: kernel/generic/src/smp/smp.c =================================================================== --- kernel/generic/src/smp/smp.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/smp/smp.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -27,5 +27,5 @@ */ -/** @addtogroup generic +/** @addtogroup generic * @{ */ Index: kernel/generic/src/smp/smp_call.c =================================================================== --- kernel/generic/src/smp/smp_call.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/smp/smp_call.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -61,20 +61,20 @@ /** Invokes a function on a specific cpu and waits for it to complete. - * - * Calls @a func on the CPU denoted by its logical id @cpu_id . - * The function will execute with interrupts disabled. It should - * be a quick and simple function and must never block. - * + * + * Calls @a func on the CPU denoted by its logical id @cpu_id . + * The function will execute with interrupts disabled. It should + * be a quick and simple function and must never block. + * * If @a cpu_id is the local CPU, the function will be invoked * directly. - * + * * All memory accesses of prior to smp_call() will be visible * to @a func on cpu @a cpu_id. Similarly, any changes @a func * makes on cpu @a cpu_id will be visible on this cpu once * smp_call() returns. - * + * * Invoking @a func on the destination cpu acts as a memory barrier * on that cpu. - * + * * @param cpu_id Destination CPU's logical id (eg CPU->id) * @param func Function to call. @@ -89,30 +89,30 @@ /** Invokes a function on a specific cpu asynchronously. - * - * Calls @a func on the CPU denoted by its logical id @cpu_id . - * The function will execute with interrupts disabled. It should - * be a quick and simple function and must never block. - * - * Pass @a call_info to smp_call_wait() in order to wait for + * + * Calls @a func on the CPU denoted by its logical id @cpu_id . + * The function will execute with interrupts disabled. It should + * be a quick and simple function and must never block. + * + * Pass @a call_info to smp_call_wait() in order to wait for * @a func to complete. - * + * * @a call_info must be valid until/after @a func returns. Use * smp_call_wait() to wait until it is safe to free @a call_info. - * + * * If @a cpu_id is the local CPU, the function will be invoked * directly. If the destination cpu id @a cpu_id is invalid * or denotes an inactive cpu, the call is discarded immediately. - * + * * All memory accesses of the caller prior to smp_call_async() - * will be made visible to @a func on the other cpu. Similarly, + * will be made visible to @a func on the other cpu. Similarly, * any changes @a func makes on cpu @a cpu_id will be visible * to this cpu when smp_call_wait() returns. - * + * * Invoking @a func on the destination cpu acts as a memory barrier * on that cpu. - * + * * Interrupts must be enabled. Otherwise you run the risk * of a deadlock. - * + * * @param cpu_id Destination CPU's logical id (eg CPU->id). * @param func Function to call. @@ -121,12 +121,12 @@ * be valid until the function completes. */ -void smp_call_async(unsigned int cpu_id, smp_call_func_t func, void *arg, +void smp_call_async(unsigned int cpu_id, smp_call_func_t func, void *arg, smp_call_t *call_info) { - /* - * Interrupts must not be disabled or you run the risk of a deadlock + /* + * Interrupts must not be disabled or you run the risk of a deadlock * if both the destination and source cpus try to send an IPI to each - * other with interrupts disabled. Because the interrupts are disabled - * the IPIs cannot be delivered and both cpus will forever busy wait + * other with interrupts disabled. Because the interrupts are disabled + * the IPIs cannot be delivered and both cpus will forever busy wait * for an acknowledgment of the IPI from the other cpu. */ @@ -155,8 +155,8 @@ * If a platform supports SMP it must implement arch_smp_call_ipi(). * It should issue an IPI on cpu_id and invoke smp_call_ipi_recv() - * on cpu_id in turn. - * + * on cpu_id in turn. + * * Do not implement as just an empty dummy function. Instead - * consider providing a full implementation or at least a version + * consider providing a full implementation or at least a version * that panics if invoked. Note that smp_call_async() never * calls arch_smp_call_ipi() on uniprocessors even if CONFIG_SMP. @@ -177,7 +177,7 @@ /** Waits for a function invoked on another CPU asynchronously to complete. - * + * * Does not sleep but rather spins. - * + * * Example usage: * @code @@ -185,5 +185,5 @@ * puts((char*)p); * } - * + * * smp_call_t call_info; * smp_call_async(cpus[2].id, hello, "hi!\n", &call_info); @@ -191,5 +191,5 @@ * smp_call_wait(&call_info); * @endcode - * + * * @param call_info Initialized by smp_call_async(). */ @@ -202,5 +202,5 @@ /** Architecture independent smp call IPI handler. - * + * * Interrupts must be disabled. Tolerates spurious calls. */ @@ -213,5 +213,5 @@ list_initialize(&calls_list); - /* + /* * Acts as a load memory barrier. Any changes made by the cpu that * added the smp_call to calls_list will be made visible to this cpu. @@ -222,5 +222,5 @@ /* Walk the list manually, so that we can safely remove list items. */ - for (link_t *cur = calls_list.head.next, *next = cur->next; + for (link_t *cur = calls_list.head.next, *next = cur->next; !list_empty(&calls_list); cur = next, next = cur->next) { @@ -254,6 +254,6 @@ static void call_done(smp_call_t *call_info) { - /* - * Separate memory accesses of the called function from the + /* + * Separate memory accesses of the called function from the * announcement of its completion. */ @@ -265,7 +265,7 @@ { do { - /* + /* * Ensure memory accesses following call_wait() are ordered - * after completion of the called function on another cpu. + * after completion of the called function on another cpu. * Also, speed up loading of call_info->pending. */ Index: kernel/generic/src/synch/condvar.c =================================================================== --- kernel/generic/src/synch/condvar.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/synch/condvar.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -107,5 +107,5 @@ /** Wait for the condition to become true with a locked spinlock. - * + * * The function is not aware of irq_spinlock. Therefore do not even * try passing irq_spinlock_t to it. Use _condvar_wait_timeout_irq_spinlock() @@ -124,5 +124,5 @@ * @return See comment for waitq_sleep_timeout(). */ -errno_t _condvar_wait_timeout_spinlock_impl(condvar_t *cv, spinlock_t *lock, +errno_t _condvar_wait_timeout_spinlock_impl(condvar_t *cv, spinlock_t *lock, uint32_t usec, int flags) { @@ -148,5 +148,5 @@ /** Wait for the condition to become true with a locked irq spinlock. - * + * * @param cv Condition variable. * @param lock Locked irq spinlock. @@ -161,5 +161,5 @@ * @return See comment for waitq_sleep_timeout(). */ -errno_t _condvar_wait_timeout_irq_spinlock(condvar_t *cv, irq_spinlock_t *irq_lock, +errno_t _condvar_wait_timeout_irq_spinlock(condvar_t *cv, irq_spinlock_t *irq_lock, uint32_t usec, int flags) { @@ -171,12 +171,12 @@ irq_lock->guard = false; - /* - * waitq_prepare() restores interrupts to the current state, - * ie disabled. Therefore, interrupts will remain disabled while - * it spins waiting for a pending timeout handler to complete. + /* + * waitq_prepare() restores interrupts to the current state, + * ie disabled. Therefore, interrupts will remain disabled while + * it spins waiting for a pending timeout handler to complete. * Although it spins with interrupts disabled there can only * be a pending timeout if we failed to cancel an imminent - * timeout (on another cpu) during a wakeup. As a result the - * timeout handler is guaranteed to run (it is most likely already + * timeout (on another cpu) during a wakeup. As a result the + * timeout handler is guaranteed to run (it is most likely already * running) and there is no danger of a deadlock. */ Index: kernel/generic/src/synch/futex.c =================================================================== --- kernel/generic/src/synch/futex.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/synch/futex.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -35,12 +35,12 @@ * @file * @brief Kernel backend for futexes. - * - * Kernel futex objects are stored in a global hash table futex_ht + * + * Kernel futex objects are stored in a global hash table futex_ht * where the physical address of the futex variable (futex_t.paddr) - * is used as the lookup key. As a result multiple address spaces - * may share the same futex variable. - * + * is used as the lookup key. As a result multiple address spaces + * may share the same futex variable. + * * A kernel futex object is created the first time a task accesses - * the futex (having a futex variable at a physical address not + * the futex (having a futex variable at a physical address not * encountered before). Futex object's lifetime is governed by * a reference count that represents the number of all the different @@ -48,15 +48,15 @@ * physical address of the futex variable. A futex object is freed * when the last task having accessed the futex exits. - * + * * Each task keeps track of the futex objects it accessed in a list - * of pointers (futex_ptr_t, task->futex_list) to the different futex + * of pointers (futex_ptr_t, task->futex_list) to the different futex * objects. - * + * * To speed up translation of futex variables' virtual addresses * to their physical addresses, futex pointers accessed by the * task are furthermore stored in a concurrent hash table (CHT, * task->futexes->ht). A single lookup without locks or accesses - * to the page table translates a futex variable's virtual address - * into its futex kernel object. + * to the page table translates a futex variable's virtual address + * into its futex kernel object. */ @@ -119,5 +119,5 @@ /** Mutex protecting the global futex hash table. - * + * * Acquire task specific TASK->futex_list_lock before this mutex. */ @@ -125,5 +125,5 @@ /** Global kernel futex hash table. Lock futex_ht_lock before accessing. - * + * * Physical address of the futex variable is the lookup key. */ @@ -170,5 +170,5 @@ if (interrupts_disabled()) { /* Invoke the blocking cht_destroy in the background. */ - workq_global_enqueue_noblock(&task->futexes->destroy_work, + workq_global_enqueue_noblock(&task->futexes->destroy_work, destroy_task_cache); } else { @@ -181,8 +181,8 @@ static void destroy_task_cache(work_t *work) { - struct futex_cache *cache = + struct futex_cache *cache = member_to_inst(work, struct futex_cache, destroy_work); - /* + /* * Destroy the cache before manually freeing items of the cache in case * table resize is in progress. @@ -216,5 +216,5 @@ * task have already terminated, so they have also definitely * exited their CHT futex cache protecting rcu reader sections. - * Moreover release_ref() only frees the futex if this is the + * Moreover release_ref() only frees the futex if this is the * last task referencing the futex. Therefore, only threads * of this task may have referenced the futex if it is to be freed. @@ -273,5 +273,5 @@ futex_t *futex = find_cached_futex(uaddr); - if (futex) + if (futex) return futex; @@ -319,5 +319,5 @@ if (futex_ptr_link) { - futex_ptr_t *futex_ptr + futex_ptr_t *futex_ptr = member_to_inst(futex_ptr_link, futex_ptr_t, cht_link); @@ -333,6 +333,6 @@ -/** - * Returns a kernel futex for the physical address @a phys_addr and caches +/** + * Returns a kernel futex for the physical address @a phys_addr and caches * it in this task under the virtual address @a uaddr (if not already cached). */ @@ -341,6 +341,6 @@ futex_t *futex = malloc(sizeof(futex_t), 0); - /* - * Find the futex object in the global futex table (or insert it + /* + * Find the futex object in the global futex table (or insert it * if it is not present). */ @@ -360,6 +360,6 @@ spinlock_unlock(&futex_ht_lock); - /* - * Cache the link to the futex object for this task. + /* + * Cache the link to the futex object for this task. */ futex_ptr_t *fut_ptr = malloc(sizeof(futex_ptr_t), 0); @@ -382,5 +382,5 @@ futex_ptr_t *dup = member_to_inst(dup_link, futex_ptr_t, cht_link); - futex = dup->futex; + futex = dup->futex; } @@ -402,5 +402,5 @@ futex_t *futex = get_futex(uaddr); - if (!futex) + if (!futex) return (sys_errno_t) ENOENT; @@ -473,5 +473,5 @@ /* - * Operations of a task's CHT that caches mappings of futex user space + * Operations of a task's CHT that caches mappings of futex user space * virtual addresses to kernel futex objects. */ Index: kernel/generic/src/synch/rcu.c =================================================================== --- kernel/generic/src/synch/rcu.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/synch/rcu.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -35,7 +35,7 @@ * @file * @brief Preemptible read-copy update. Usable from interrupt handlers. - * + * * @par Podzimek-preempt-RCU (RCU_PREEMPT_PODZIMEK) - * + * * Podzimek-preempt-RCU is a preemptible variant of Podzimek's non-preemptible * RCU algorithm [1, 2]. Grace period (GP) detection is centralized into a @@ -43,24 +43,24 @@ * that it passed a quiescent state (QS), ie a state when the cpu is * outside of an rcu reader section (CS). Cpus check for QSs during context - * switches and when entering and exiting rcu reader sections. Once all - * cpus announce a QS and if there were no threads preempted in a CS, the + * switches and when entering and exiting rcu reader sections. Once all + * cpus announce a QS and if there were no threads preempted in a CS, the * GP ends. - * - * The detector increments the global GP counter, _rcu_cur_gp, in order - * to start a new GP. Readers notice the new GP by comparing the changed + * + * The detector increments the global GP counter, _rcu_cur_gp, in order + * to start a new GP. Readers notice the new GP by comparing the changed * _rcu_cur_gp to a locally stored value last_seen_gp which denotes the * the last GP number for which the cpu noted an explicit QS (and issued * a memory barrier). Readers check for the change in the outer-most - * (ie not nested) rcu_read_lock()/unlock() as these functions represent - * a QS. The reader first executes a memory barrier (MB) in order to contain - * memory references within a CS (and to make changes made by writers - * visible in the CS following rcu_read_lock()). Next, the reader notes + * (ie not nested) rcu_read_lock()/unlock() as these functions represent + * a QS. The reader first executes a memory barrier (MB) in order to contain + * memory references within a CS (and to make changes made by writers + * visible in the CS following rcu_read_lock()). Next, the reader notes * that it reached a QS by updating the cpu local last_seen_gp to the * global GP counter, _rcu_cur_gp. Cache coherency eventually makes * the updated last_seen_gp visible to the detector cpu, much like it * delivered the changed _rcu_cur_gp to all cpus. - * - * The detector waits a while after starting a GP and then reads each - * cpu's last_seen_gp to see if it reached a QS. If a cpu did not record + * + * The detector waits a while after starting a GP and then reads each + * cpu's last_seen_gp to see if it reached a QS. If a cpu did not record * a QS (might be a long running thread without an RCU reader CS; or cache * coherency has yet to make the most current last_seen_gp visible to @@ -68,28 +68,28 @@ * via an IPI. If the IPI handler finds the cpu still in a CS, it instructs * the cpu to notify the detector that it had exited the CS via a semaphore - * (CPU->rcu.is_delaying_gp). + * (CPU->rcu.is_delaying_gp). * The detector then waits on the semaphore for any cpus to exit their - * CSs. Lastly, it waits for the last reader preempted in a CS to + * CSs. Lastly, it waits for the last reader preempted in a CS to * exit its CS if there were any and signals the end of the GP to * separate reclaimer threads wired to each cpu. Reclaimers then * execute the callbacks queued on each of the cpus. - * - * + * + * * @par A-RCU algorithm (RCU_PREEMPT_A) - * + * * A-RCU is based on the user space rcu algorithm in [3] utilizing signals - * (urcu) and Podzimek's rcu [1]. Like in Podzimek's rcu, callbacks are - * executed by cpu-bound reclaimer threads. There is however no dedicated - * detector thread and the reclaimers take on the responsibilities of the - * detector when they need to start a new GP. A new GP is again announced + * (urcu) and Podzimek's rcu [1]. Like in Podzimek's rcu, callbacks are + * executed by cpu-bound reclaimer threads. There is however no dedicated + * detector thread and the reclaimers take on the responsibilities of the + * detector when they need to start a new GP. A new GP is again announced * and acknowledged with _rcu_cur_gp and the cpu local last_seen_gp. Unlike - * Podzimek's rcu, cpus check explicitly for QS only during context switches. + * Podzimek's rcu, cpus check explicitly for QS only during context switches. * Like in urcu, rcu_read_lock()/unlock() only maintain the nesting count * and never issue any memory barriers. This makes rcu_read_lock()/unlock() * simple and fast. - * + * * If a new callback is queued for a reclaimer and no GP is in progress, - * the reclaimer takes on the role of a detector. The detector increments - * _rcu_cur_gp in order to start a new GP. It waits a while to give cpus + * the reclaimer takes on the role of a detector. The detector increments + * _rcu_cur_gp in order to start a new GP. It waits a while to give cpus * a chance to switch a context (a natural QS). Then, it examines each * non-idle cpu that has yet to pass a QS via an IPI. The IPI handler @@ -98,28 +98,28 @@ * finds the cpu in a CS it does nothing and let the detector poll/interrupt * the cpu again after a short sleep. - * + * * @par Caveats - * + * * last_seen_gp and _rcu_cur_gp are always 64bit variables and they * are read non-atomically on 32bit machines. Reading a clobbered * value of last_seen_gp or _rcu_cur_gp or writing a clobbered value * of _rcu_cur_gp to last_seen_gp will at worst force the detector - * to unnecessarily interrupt a cpu. Interrupting a cpu makes the + * to unnecessarily interrupt a cpu. Interrupting a cpu makes the * correct value of _rcu_cur_gp visible to the cpu and correctly * resets last_seen_gp in both algorithms. - * - * - * + * + * + * * [1] Read-copy-update for opensolaris, * 2010, Podzimek * https://andrej.podzimek.org/thesis.pdf - * + * * [2] (podzimek-rcu) implementation file "rcu.patch" * http://d3s.mff.cuni.cz/projects/operating_systems/rcu/rcu.patch - * + * * [3] User-level implementations of read-copy update, * 2012, appendix * http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf - * + * */ @@ -139,11 +139,11 @@ #include -/* - * Number of milliseconds to give to preexisting readers to finish +/* + * Number of milliseconds to give to preexisting readers to finish * when non-expedited grace period detection is in progress. */ #define DETECT_SLEEP_MS 10 -/* - * Max number of pending callbacks in the local cpu's queue before +/* + * Max number of pending callbacks in the local cpu's queue before * aggressively expediting the current grace period */ @@ -159,6 +159,6 @@ #define UINT32_MAX_HALF 2147483648U -/** - * The current grace period number. Increases monotonically. +/** + * The current grace period number. Increases monotonically. * Lock rcu.gp_lock or rcu.preempt_lock to get a current value. */ @@ -171,5 +171,5 @@ /** Reclaimers use to notify the detector to accelerate GP detection. */ condvar_t expedite_now; - /** + /** * Protects: req_gp_end_cnt, req_expedited_cnt, completed_gp, _rcu_cur_gp; * or: completed_gp, _rcu_cur_gp @@ -177,6 +177,6 @@ SPINLOCK_DECLARE(gp_lock); /** - * The number of the most recently completed grace period. At most - * one behind _rcu_cur_gp. If equal to _rcu_cur_gp, a grace period + * The number of the most recently completed grace period. At most + * one behind _rcu_cur_gp. If equal to _rcu_cur_gp, a grace period * detection is not in progress and the detector is idle. */ @@ -189,7 +189,7 @@ /** Reader that have been preempted and might delay the next grace period.*/ list_t next_preempted; - /** - * The detector is waiting for the last preempted reader - * in cur_preempted to announce that it exited its reader + /** + * The detector is waiting for the last preempted reader + * in cur_preempted to announce that it exited its reader * section by up()ing remaining_readers. */ @@ -198,6 +198,6 @@ #ifdef RCU_PREEMPT_A - /** - * The detector waits on this semaphore for any preempted readers + /** + * The detector waits on this semaphore for any preempted readers * delaying the grace period once all cpus pass a quiescent state. */ @@ -212,15 +212,15 @@ /** Number of consecutive grace periods to detect quickly and aggressively.*/ size_t req_expedited_cnt; - /** + /** * Number of cpus with readers that are delaying the current GP. * They will up() remaining_readers. */ atomic_t delaying_cpu_cnt; - /** + /** * The detector waits on this semaphore for any readers delaying the GP. - * - * Each of the cpus with readers that are delaying the current GP - * must up() this sema once they reach a quiescent state. If there - * are any readers in cur_preempted (ie preempted preexisting) and + * + * Each of the cpus with readers that are delaying the current GP + * must up() this sema once they reach a quiescent state. If there + * are any readers in cur_preempted (ie preempted preexisting) and * they are already delaying GP detection, the last to unlock its * reader section must up() this sema once. @@ -252,5 +252,5 @@ static void start_reclaimers(void); static void synch_complete(rcu_item_t *rcu_item); -static inline void rcu_call_impl(bool expedite, rcu_item_t *rcu_item, +static inline void rcu_call_impl(bool expedite, rcu_item_t *rcu_item, rcu_func_t func); static void add_barrier_cb(void *arg); @@ -396,6 +396,6 @@ -/** Cleans up global RCU resources and stops dispatching callbacks. - * +/** Cleans up global RCU resources and stops dispatching callbacks. + * * Call when shutting down the kernel. Outstanding callbacks will * not be processed. Instead they will linger forever. @@ -444,8 +444,8 @@ snprintf(name, THREAD_NAME_BUFLEN - 1, "rcu-rec/%u", cpu_id); - cpus[cpu_id].rcu.reclaimer_thr = + cpus[cpu_id].rcu.reclaimer_thr = thread_create(reclaimer, NULL, TASK, THREAD_FLAG_NONE, name); - if (!cpus[cpu_id].rcu.reclaimer_thr) + if (!cpus[cpu_id].rcu.reclaimer_thr) panic("Failed to create RCU reclaimer thread on cpu%u.", cpu_id); @@ -460,8 +460,8 @@ static void start_detector(void) { - rcu.detector_thr = + rcu.detector_thr = thread_create(detector, NULL, TASK, THREAD_FLAG_NONE, "rcu-det"); - if (!rcu.detector_thr) + if (!rcu.detector_thr) panic("Failed to create RCU detector thread."); @@ -479,9 +479,9 @@ } -/** Unlocks the local reader section using the given nesting count. - * - * Preemption or interrupts must be disabled. - * - * @param pnesting_cnt Either &CPU->rcu.tmp_nesting_cnt or +/** Unlocks the local reader section using the given nesting count. + * + * Preemption or interrupts must be disabled. + * + * @param pnesting_cnt Either &CPU->rcu.tmp_nesting_cnt or * THREAD->rcu.nesting_cnt. */ @@ -493,9 +493,9 @@ _rcu_record_qs(); - /* - * The thread was preempted while in a critical section or - * the detector is eagerly waiting for this cpu's reader - * to finish. - * + /* + * The thread was preempted while in a critical section or + * the detector is eagerly waiting for this cpu's reader + * to finish. + * * Note that THREAD may be NULL in scheduler() and not just during boot. */ @@ -518,5 +518,5 @@ */ - /* + /* * If the detector is eagerly waiting for this cpu's reader to unlock, * notify it that the reader did so. @@ -566,5 +566,5 @@ assert(!rcu_read_locked()); - synch_item_t completion; + synch_item_t completion; waitq_initialize(&completion.wq); @@ -584,5 +584,5 @@ void rcu_barrier(void) { - /* + /* * Serialize rcu_barrier() calls so we don't overwrite cpu.barrier_item * currently in use by rcu_barrier(). @@ -590,5 +590,5 @@ mutex_lock(&rcu.barrier_mtx); - /* + /* * Ensure we queue a barrier callback on all cpus before the already * enqueued barrier callbacks start signaling completion. @@ -610,7 +610,7 @@ } -/** Issues a rcu_barrier() callback on the local cpu. - * - * Executed with interrupts disabled. +/** Issues a rcu_barrier() callback on the local cpu. + * + * Executed with interrupts disabled. */ static void add_barrier_cb(void *arg) @@ -631,8 +631,8 @@ } -/** Adds a callback to invoke after all preexisting readers finish. - * +/** Adds a callback to invoke after all preexisting readers finish. + * * May be called from within interrupt handlers or RCU reader sections. - * + * * @param rcu_item Used by RCU to track the call. Must remain * until the user callback function is entered. @@ -655,5 +655,5 @@ /** rcu_call() inline-able implementation. See rcu_call() for comments. */ -static inline void rcu_call_impl(bool expedite, rcu_item_t *rcu_item, +static inline void rcu_call_impl(bool expedite, rcu_item_t *rcu_item, rcu_func_t func) { @@ -667,5 +667,5 @@ rcu_cpu_data_t *r = &CPU->rcu; - rcu_item_t **prev_tail + rcu_item_t **prev_tail = local_atomic_exchange(&r->parriving_cbs_tail, &rcu_item->next); *prev_tail = rcu_item; @@ -704,6 +704,6 @@ { assert(THREAD && THREAD->wired); - /* - * Accessing with interrupts enabled may at worst lead to + /* + * Accessing with interrupts enabled may at worst lead to * a false negative if we race with a local interrupt handler. */ @@ -740,5 +740,5 @@ static bool wait_for_pending_cbs(void) { - if (!all_cbs_empty()) + if (!all_cbs_empty()) return true; @@ -772,14 +772,14 @@ if (exec_cnt < CRITICAL_THRESHOLD) { exec_cbs(&CPU->rcu.cur_cbs); - exec_cbs(&CPU->rcu.next_cbs); + exec_cbs(&CPU->rcu.next_cbs); } else { - /* - * Getting overwhelmed with too many callbacks to run. - * Disable preemption in order to prolong our time slice + /* + * Getting overwhelmed with too many callbacks to run. + * Disable preemption in order to prolong our time slice * and catch up with updaters posting new callbacks. */ preemption_disable(); exec_cbs(&CPU->rcu.cur_cbs); - exec_cbs(&CPU->rcu.next_cbs); + exec_cbs(&CPU->rcu.next_cbs); preemption_enable(); } @@ -792,7 +792,7 @@ exec_cbs(&CPU->rcu.cur_cbs); } else { - /* - * Getting overwhelmed with too many callbacks to run. - * Disable preemption in order to prolong our time slice + /* + * Getting overwhelmed with too many callbacks to run. + * Disable preemption in order to prolong our time slice * and catch up with updaters posting new callbacks. */ @@ -828,5 +828,5 @@ CPU->rcu.stat_max_cbs = max(arriving_cnt, CPU->rcu.stat_max_cbs); if (0 < arriving_cnt) { - CPU->rcu.stat_avg_cbs = + CPU->rcu.stat_avg_cbs = (99 * CPU->rcu.stat_avg_cbs + 1 * arriving_cnt) / 100; } @@ -834,5 +834,5 @@ /** Prepares another batch of callbacks to dispatch at the nest grace period. - * + * * @return True if the next batch of callbacks must be expedited quickly. */ @@ -849,10 +849,10 @@ CPU->rcu.arriving_cbs_cnt = 0; - /* + /* * Too many callbacks queued. Better speed up the detection * or risk exhausting all system memory. */ bool expedite = (EXPEDITE_THRESHOLD < CPU->rcu.next_cbs_cnt) - || CPU->rcu.expedite_arriving; + || CPU->rcu.expedite_arriving; CPU->rcu.expedite_arriving = false; @@ -860,5 +860,5 @@ CPU->rcu.next_cbs = CPU->rcu.arriving_cbs; - /* + /* * At least one callback arrived. The tail therefore does not point * to the head of arriving_cbs and we can safely reset it to NULL. @@ -873,6 +873,6 @@ ACCESS_ONCE(CPU->rcu.parriving_cbs_tail) = &CPU->rcu.arriving_cbs; } else { - /* - * arriving_cbs was null and parriving_cbs_tail pointed to it + /* + * arriving_cbs was null and parriving_cbs_tail pointed to it * so leave it that way. Note that interrupt handlers may have * added a callback in the meantime so it is not safe to reset @@ -884,6 +884,6 @@ upd_stat_cb_cnts(CPU->rcu.next_cbs_cnt); - /* - * Make changes prior to queuing next_cbs visible to readers. + /* + * Make changes prior to queuing next_cbs visible to readers. * See comment in wait_for_readers(). */ @@ -898,8 +898,8 @@ CPU->rcu.next_cbs_gp = _rcu_cur_gp + 1; - /* + /* * There are no callbacks to invoke before next_cbs. Instruct * wait_for_cur_cbs_gp() to notify us of the nearest GP end. - * That could be sooner than next_cbs_gp (if the current GP + * That could be sooner than next_cbs_gp (if the current GP * had not yet completed), so we'll create a shorter batch * of callbacks next time around. @@ -907,5 +907,5 @@ if (cur_cbs_empty()) { CPU->rcu.cur_cbs_gp = rcu.completed_gp + 1; - } + } spinlock_unlock(&rcu.gp_lock); @@ -916,5 +916,5 @@ assert(CPU->rcu.cur_cbs_gp <= CPU->rcu.next_cbs_gp); - return expedite; + return expedite; } @@ -922,9 +922,9 @@ #ifdef RCU_PREEMPT_A -/** Waits for the grace period associated with callbacks cub_cbs to elapse. - * - * @param expedite Instructs the detector to aggressively speed up grace +/** Waits for the grace period associated with callbacks cub_cbs to elapse. + * + * @param expedite Instructs the detector to aggressively speed up grace * period detection without any delay. - * @param completed_gp Returns the most recent completed grace period + * @param completed_gp Returns the most recent completed grace period * number. * @return false if the thread was interrupted and should stop. @@ -951,16 +951,16 @@ condvar_broadcast(&rcu.gp_ended); } else { - /* GP detection is in progress.*/ + /* GP detection is in progress.*/ - if (expedite) + if (expedite) condvar_signal(&rcu.expedite_now); /* Wait for the GP to complete. */ - errno_t ret = _condvar_wait_timeout_spinlock(&rcu.gp_ended, &rcu.gp_lock, + errno_t ret = _condvar_wait_timeout_spinlock(&rcu.gp_ended, &rcu.gp_lock, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_INTERRUPTIBLE); if (ret == EINTR) { spinlock_unlock(&rcu.gp_lock); - return false; + return false; } } @@ -984,5 +984,5 @@ while (!cpu_mask_is_none(reader_cpus)) { /* Give cpus a chance to context switch (a QS) and batch callbacks. */ - if(!gp_sleep(&expedite)) + if(!gp_sleep(&expedite)) return false; @@ -996,5 +996,5 @@ } - /* + /* * All cpus have passed through a QS and see the most recent _rcu_cur_gp. * As a result newly preempted readers will associate with next_preempted @@ -1038,5 +1038,5 @@ if (locked && !passed_qs) { - /* + /* * This cpu has not yet passed a quiescent state during this grace * period and it is currently in a reader section. We'll have to @@ -1057,11 +1057,11 @@ assert(interrupts_disabled()); - /* - * In order not to worry about NMI seeing rcu_nesting change work + /* + * In order not to worry about NMI seeing rcu_nesting change work * with a local copy. */ size_t nesting_cnt = local_atomic_exchange(&THE->rcu_nesting, 0); - /* + /* * Ensures NMIs see .rcu_nesting without the WAS_PREEMPTED mark and * do not accidentally call rm_preempted_reader() from unlock(). @@ -1079,20 +1079,20 @@ if (CPU->rcu.last_seen_gp != _rcu_cur_gp) { - /* - * Contain any memory accesses of old readers before announcing a QS. + /* + * Contain any memory accesses of old readers before announcing a QS. * Also make changes from the previous GP visible to this cpu. - * Moreover it separates writing to last_seen_gp from + * Moreover it separates writing to last_seen_gp from * note_preempted_reader(). */ memory_barrier(); - /* + /* * The preempted reader has been noted globally. There are therefore * no readers running on this cpu so this is a quiescent state. - * - * Reading the multiword _rcu_cur_gp non-atomically is benign. + * + * Reading the multiword _rcu_cur_gp non-atomically is benign. * At worst, the read value will be different from the actual value. * As a result, both the detector and this cpu will believe * this cpu has not yet passed a QS although it really did. - * + * * Reloading _rcu_cur_gp is benign, because it cannot change * until this cpu acknowledges it passed a QS by writing to @@ -1103,5 +1103,5 @@ } - /* + /* * Forcefully associate the reclaimer with the highest priority * even if preempted due to its time slice running out. @@ -1109,5 +1109,5 @@ if (THREAD == CPU->rcu.reclaimer_thr) { THREAD->priority = -1; - } + } upd_max_cbs_in_slice(CPU->rcu.arriving_cbs_cnt); @@ -1123,6 +1123,6 @@ } -/** Called from scheduler() when exiting the current thread. - * +/** Called from scheduler() when exiting the current thread. + * * Preemption or interrupts are disabled and the scheduler() already * switched away from the current thread, calling rcu_after_thread_ran(). @@ -1132,8 +1132,8 @@ assert(THE->rcu_nesting == 0); - /* - * The thread forgot to exit its reader critical section. + /* + * The thread forgot to exit its reader critical section. * It is a bug, but rather than letting the entire system lock up - * forcefully leave the reader section. The thread is not holding + * forcefully leave the reader section. The thread is not holding * any references anyway since it is exiting so it is safe. */ @@ -1162,5 +1162,5 @@ size_t prev = local_atomic_exchange(&THE->rcu_nesting, 0); if (prev == RCU_WAS_PREEMPTED) { - /* + /* * NMI handlers are never preempted but may call rm_preempted_reader() * if a NMI occurred in _rcu_preempted_unlock() of a preempted thread. @@ -1168,5 +1168,5 @@ * in _rcu_preempted_unlock() is: an IPI/sample_local_cpu() and * the initial part of rcu_after_thread_ran(). - * + * * rm_preempted_reader() will not deadlock because none of the locks * it uses are locked in this case. Neither _rcu_preempted_unlock() @@ -1180,9 +1180,9 @@ #elif defined(RCU_PREEMPT_PODZIMEK) -/** Waits for the grace period associated with callbacks cub_cbs to elapse. - * - * @param expedite Instructs the detector to aggressively speed up grace +/** Waits for the grace period associated with callbacks cub_cbs to elapse. + * + * @param expedite Instructs the detector to aggressively speed up grace * period detection without any delay. - * @param completed_gp Returns the most recent completed grace period + * @param completed_gp Returns the most recent completed grace period * number. * @return false if the thread was interrupted and should stop. @@ -1190,22 +1190,22 @@ static bool wait_for_cur_cbs_gp_end(bool expedite, rcu_gp_t *completed_gp) { - /* + /* * Use a possibly outdated version of completed_gp to bypass checking * with the lock. - * - * Note that loading and storing rcu.completed_gp is not atomic - * (it is 64bit wide). Reading a clobbered value that is less than - * rcu.completed_gp is harmless - we'll recheck with a lock. The - * only way to read a clobbered value that is greater than the actual - * value is if the detector increases the higher-order word first and - * then decreases the lower-order word (or we see stores in that order), - * eg when incrementing from 2^32 - 1 to 2^32. The loaded value - * suddenly jumps by 2^32. It would take hours for such an increase - * to occur so it is safe to discard the value. We allow increases + * + * Note that loading and storing rcu.completed_gp is not atomic + * (it is 64bit wide). Reading a clobbered value that is less than + * rcu.completed_gp is harmless - we'll recheck with a lock. The + * only way to read a clobbered value that is greater than the actual + * value is if the detector increases the higher-order word first and + * then decreases the lower-order word (or we see stores in that order), + * eg when incrementing from 2^32 - 1 to 2^32. The loaded value + * suddenly jumps by 2^32. It would take hours for such an increase + * to occur so it is safe to discard the value. We allow increases * of up to half the maximum to generously accommodate for loading an * outdated lower word. */ rcu_gp_t compl_gp = ACCESS_ONCE(rcu.completed_gp); - if (CPU->rcu.cur_cbs_gp <= compl_gp + if (CPU->rcu.cur_cbs_gp <= compl_gp && compl_gp <= CPU->rcu.cur_cbs_gp + UINT32_MAX_HALF) { *completed_gp = compl_gp; @@ -1224,6 +1224,6 @@ assert(_rcu_cur_gp <= CPU->rcu.cur_cbs_gp); - /* - * Notify the detector of how many GP ends we intend to wait for, so + /* + * Notify the detector of how many GP ends we intend to wait for, so * it can avoid going to sleep unnecessarily. Optimistically assume * new callbacks will arrive while we're waiting; hence +1. @@ -1232,14 +1232,14 @@ req_detection(remaining_gp_ends + (arriving_cbs_empty() ? 0 : 1)); - /* - * Ask the detector to speed up GP detection if there are too many + /* + * Ask the detector to speed up GP detection if there are too many * pending callbacks and other reclaimers have not already done so. */ if (expedite) { - if(0 == rcu.req_expedited_cnt) + if(0 == rcu.req_expedited_cnt) condvar_signal(&rcu.expedite_now); - /* - * Expedite only cub_cbs. If there really is a surge of callbacks + /* + * Expedite only cub_cbs. If there really is a surge of callbacks * the arriving batch will expedite the GP for the huge number * of callbacks currently in next_cbs @@ -1252,5 +1252,5 @@ *completed_gp = rcu.completed_gp; - spinlock_unlock(&rcu.gp_lock); + spinlock_unlock(&rcu.gp_lock); if (!interrupted) @@ -1269,5 +1269,5 @@ /* Wait until wait_on_gp ends. */ while (rcu.completed_gp < wait_on_gp && !interrupted) { - int ret = _condvar_wait_timeout_spinlock(&rcu.gp_ended, &rcu.gp_lock, + int ret = _condvar_wait_timeout_spinlock(&rcu.gp_ended, &rcu.gp_lock, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_INTERRUPTIBLE); interrupted = (ret == EINTR); @@ -1298,5 +1298,5 @@ while (wait_for_detect_req()) { - /* + /* * Announce new GP started. Readers start lazily acknowledging that * they passed a QS. @@ -1306,5 +1306,5 @@ spinlock_unlock(&rcu.gp_lock); - if (!wait_for_readers()) + if (!wait_for_readers()) goto unlocked_out; @@ -1329,5 +1329,5 @@ while (0 == rcu.req_gp_end_cnt && !interrupted) { - int ret = _condvar_wait_timeout_spinlock(&rcu.req_gp_changed, + int ret = _condvar_wait_timeout_spinlock(&rcu.req_gp_changed, &rcu.gp_lock, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_INTERRUPTIBLE); @@ -1357,6 +1357,6 @@ cpu_mask_active(reading_cpus); - /* - * Give readers time to pass through a QS. Also, batch arriving + /* + * Give readers time to pass through a QS. Also, batch arriving * callbacks in order to amortize detection overhead. */ @@ -1417,7 +1417,7 @@ } -/** Invoked on a cpu delaying grace period detection. - * - * Induces a quiescent state for the cpu or it instructs remaining +/** Invoked on a cpu delaying grace period detection. + * + * Induces a quiescent state for the cpu or it instructs remaining * readers to notify the detector once they finish. */ @@ -1432,7 +1432,7 @@ if (0 < CPU->rcu.nesting_cnt) { assert(!CPU->idle); - /* - * Note to notify the detector from rcu_read_unlock(). - * + /* + * Note to notify the detector from rcu_read_unlock(). + * * ACCESS_ONCE ensures the compiler writes to is_delaying_gp * only after it determines that we are in a reader CS. @@ -1443,13 +1443,13 @@ atomic_inc(&rcu.delaying_cpu_cnt); } else { - /* - * The cpu did not enter any rcu reader sections since + /* + * The cpu did not enter any rcu reader sections since * the start of the current GP. Record a quiescent state. - * + * * Or, we interrupted rcu_read_unlock_impl() right before - * it recorded a QS. Record a QS for it. The memory barrier - * contains the reader section's mem accesses before + * it recorded a QS. Record a QS for it. The memory barrier + * contains the reader section's mem accesses before * updating last_seen_gp. - * + * * Or, we interrupted rcu_read_lock() right after it recorded * a QS for the previous GP but before it got a chance to @@ -1461,11 +1461,11 @@ } } else { - /* - * This cpu already acknowledged that it had passed through - * a quiescent state since the start of cur_gp. + /* + * This cpu already acknowledged that it had passed through + * a quiescent state since the start of cur_gp. */ } - /* + /* * smp_call() makes sure any changes propagate back to the caller. * In particular, it makes the most current last_seen_gp visible @@ -1495,12 +1495,12 @@ assert(interrupts_disabled()); - /* + /* * Prevent NMI handlers from interfering. The detector will be notified - * in this function if CPU->rcu.is_delaying_gp. The current thread is + * in this function if CPU->rcu.is_delaying_gp. The current thread is * no longer running so there is nothing else to signal to the detector. */ CPU->rcu.signal_unlock = false; - /* - * Separates clearing of .signal_unlock from accesses to + /* + * Separates clearing of .signal_unlock from accesses to * THREAD->rcu.was_preempted and CPU->rcu.nesting_cnt. */ @@ -1516,5 +1516,5 @@ } - /* + /* * The preempted reader has been noted globally. There are therefore * no readers running on this cpu so this is a quiescent state. @@ -1522,16 +1522,16 @@ _rcu_record_qs(); - /* - * Interrupt handlers might use RCU while idle in scheduler(). - * The preempted reader has been noted globally, so the handlers + /* + * Interrupt handlers might use RCU while idle in scheduler(). + * The preempted reader has been noted globally, so the handlers * may now start announcing quiescent states. */ CPU->rcu.nesting_cnt = 0; - /* - * This cpu is holding up the current GP. Let the detector know - * it has just passed a quiescent state. - * - * The detector waits separately for preempted readers, so we have + /* + * This cpu is holding up the current GP. Let the detector know + * it has just passed a quiescent state. + * + * The detector waits separately for preempted readers, so we have * to notify the detector even if we have just preempted a reader. */ @@ -1541,16 +1541,16 @@ } - /* + /* * Forcefully associate the detector with the highest priority * even if preempted due to its time slice running out. - * + * * todo: Replace with strict scheduler priority classes. */ if (THREAD == rcu.detector_thr) { THREAD->priority = -1; - } + } else if (THREAD == CPU->rcu.reclaimer_thr) { THREAD->priority = -1; - } + } upd_max_cbs_in_slice(CPU->rcu.arriving_cbs_cnt); @@ -1566,5 +1566,5 @@ CPU->rcu.nesting_cnt = THREAD->rcu.nesting_cnt; - /* + /* * Ensures NMI see the proper nesting count before .signal_unlock. * Otherwise the NMI may incorrectly signal that a preempted reader @@ -1573,10 +1573,10 @@ compiler_barrier(); - /* - * In the unlikely event that a NMI occurs between the loading of the - * variables and setting signal_unlock, the NMI handler may invoke + /* + * In the unlikely event that a NMI occurs between the loading of the + * variables and setting signal_unlock, the NMI handler may invoke * rcu_read_unlock() and clear signal_unlock. In that case we will * incorrectly overwrite signal_unlock from false to true. This event - * is benign and the next rcu_read_unlock() will at worst + * is benign and the next rcu_read_unlock() will at worst * needlessly invoke _rcu_signal_unlock(). */ @@ -1584,6 +1584,6 @@ } -/** Called from scheduler() when exiting the current thread. - * +/** Called from scheduler() when exiting the current thread. + * * Preemption or interrupts are disabled and the scheduler() already * switched away from the current thread, calling rcu_after_thread_ran(). @@ -1595,8 +1595,8 @@ assert(PREEMPTION_DISABLED || interrupts_disabled()); - /* - * The thread forgot to exit its reader critical section. + /* + * The thread forgot to exit its reader critical section. * It is a bug, but rather than letting the entire system lock up - * forcefully leave the reader section. The thread is not holding + * forcefully leave the reader section. The thread is not holding * any references anyway since it is exiting so it is safe. */ @@ -1623,11 +1623,11 @@ ++_rcu_cur_gp; - /* + /* * Readers preempted before the start of this GP (next_preempted) - * are preexisting readers now that a GP started and will hold up + * are preexisting readers now that a GP started and will hold up * the current GP until they exit their reader sections. - * - * Preempted readers from the previous GP have finished so - * cur_preempted is empty, but see comment in _rcu_record_qs(). + * + * Preempted readers from the previous GP have finished so + * cur_preempted is empty, but see comment in _rcu_record_qs(). */ list_concat(&rcu.cur_preempted, &rcu.next_preempted); @@ -1642,8 +1642,8 @@ { /* - * Ensure the announcement of the start of a new GP (ie up-to-date - * cur_gp) propagates to cpus that are just coming out of idle + * Ensure the announcement of the start of a new GP (ie up-to-date + * cur_gp) propagates to cpus that are just coming out of idle * mode before we sample their idle state flag. - * + * * Cpus guarantee that after they set CPU->idle = true they will not * execute any RCU reader sections without first setting idle to @@ -1660,33 +1660,33 @@ * on the previously idle cpu -- again thanks to issuing a memory * barrier after returning from idle mode. - * + * * idle -> non-idle cpu | detector | reclaimer * ------------------------------------------------------ * rcu reader 1 | | rcu_call() * MB X | | - * idle = true | | rcu_call() - * (no rcu readers allowed ) | | MB A in advance_cbs() + * idle = true | | rcu_call() + * (no rcu readers allowed ) | | MB A in advance_cbs() * MB Y | (...) | (...) - * (no rcu readers allowed) | | MB B in advance_cbs() + * (no rcu readers allowed) | | MB B in advance_cbs() * idle = false | ++cur_gp | * (no rcu readers allowed) | MB C | * MB Z | signal gp_end | * rcu reader 2 | | exec_cur_cbs() - * - * + * + * * MB Y orders visibility of changes to idle for detector's sake. - * - * MB Z pairs up with MB C. The cpu making a transition from idle + * + * MB Z pairs up with MB C. The cpu making a transition from idle * will see the most current value of cur_gp and will not attempt * to notify the detector even if preempted during this GP. - * + * * MB Z pairs up with MB A from the previous batch. Updaters' changes - * are visible to reader 2 even when the detector thinks the cpu is idle + * are visible to reader 2 even when the detector thinks the cpu is idle * but it is not anymore. - * + * * MB X pairs up with MB B. Late mem accesses of reader 1 are contained - * and visible before idling and before any callbacks are executed + * and visible before idling and before any callbacks are executed * by reclaimers. - * + * * In summary, the detector does not know of or wait for reader 2, but * it does not have to since it is a new reader that will not access @@ -1696,13 +1696,13 @@ cpu_mask_for_each(*cpu_mask, cpu_id) { - /* - * The cpu already checked for and passed through a quiescent + /* + * The cpu already checked for and passed through a quiescent * state since the beginning of this GP. - * - * _rcu_cur_gp is modified by local detector thread only. - * Therefore, it is up-to-date even without a lock. - * + * + * _rcu_cur_gp is modified by local detector thread only. + * Therefore, it is up-to-date even without a lock. + * * cpu.last_seen_gp may not be up-to-date. At worst, we will - * unnecessarily sample its last_seen_gp with a smp_call. + * unnecessarily sample its last_seen_gp with a smp_call. */ bool cpu_acked_gp = (cpus[cpu_id].rcu.last_seen_gp == _rcu_cur_gp); @@ -1750,5 +1750,5 @@ list_append(&THREAD->rcu.preempt_link, &rcu.cur_preempted); } else { - /* + /* * The reader started after the GP started and this cpu * already noted a quiescent state. We might block the next GP. @@ -1774,7 +1774,7 @@ bool last_removed = now_empty && !prev_empty; - /* - * Preempted readers are blocking the detector and - * this was the last reader blocking the current GP. + /* + * Preempted readers are blocking the detector and + * this was the last reader blocking the current GP. */ if (last_removed && rcu.preempt_blocking_det) { @@ -1801,5 +1801,5 @@ return semaphore_down_interruptable(&rcu.remaining_readers); - } + } return true; @@ -1821,7 +1821,7 @@ void rcu_print_stat(void) { - /* - * Don't take locks. Worst case is we get out-dated values. - * CPU local values are updated without any locks, so there + /* + * Don't take locks. Worst case is we get out-dated values. + * CPU local values are updated without any locks, so there * are no locks to lock in order to get up-to-date values. */ @@ -1834,9 +1834,9 @@ printf("Config: expedite_threshold=%d, critical_threshold=%d," - " detect_sleep=%dms, %s\n", + " detect_sleep=%dms, %s\n", EXPEDITE_THRESHOLD, CRITICAL_THRESHOLD, DETECT_SLEEP_MS, algo); printf("Completed GPs: %" PRIu64 "\n", rcu.completed_gp); printf("Expedited GPs: %zu\n", rcu.stat_expedited_cnt); - printf("Delayed GPs: %zu (cpus w/ still running readers after gp sleep)\n", + printf("Delayed GPs: %zu (cpus w/ still running readers after gp sleep)\n", rcu.stat_delayed_cnt); printf("Preempt blocked GPs: %zu (waited for preempted readers; " Index: kernel/generic/src/synch/smp_memory_barrier.c =================================================================== --- kernel/generic/src/synch/smp_memory_barrier.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/synch/smp_memory_barrier.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -48,5 +48,5 @@ /** Issues a memory barrier on each cpu that is running a thread of the current * task. - * + * * @return Irrelevant. */ Index: kernel/generic/src/synch/spinlock.c =================================================================== --- kernel/generic/src/synch/spinlock.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/synch/spinlock.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -67,5 +67,5 @@ * * Lock spinlock. - * This version has limitted ability to report + * This version has limitted ability to report * possible occurence of deadlock. * Index: kernel/generic/src/synch/waitq.c =================================================================== --- kernel/generic/src/synch/waitq.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/synch/waitq.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -341,6 +341,6 @@ * Wait for a waitq_wakeup() or waitq_unsleep() to complete * before returning from waitq_sleep() to the caller. Otherwise - * the caller might expect that the wait queue is no longer used - * and deallocate it (although the wakeup on a another cpu has + * the caller might expect that the wait queue is no longer used + * and deallocate it (although the wakeup on a another cpu has * not yet completed and is using the wait queue). * @@ -474,11 +474,11 @@ /** If there is a wakeup in progress actively waits for it to complete. - * + * * The function returns once the concurrently running waitq_wakeup() - * exits. It returns immediately if there are no concurrent wakeups + * exits. It returns immediately if there are no concurrent wakeups * at the time. - * + * * Interrupts must be disabled. - * + * * Example usage: * @code @@ -488,5 +488,5 @@ * waitq_wakeup(wq); * } - * void wait_for_completion(void) + * void wait_for_completion(void) * { * waitq wg; @@ -496,14 +496,14 @@ * // Wait for callback() to complete its work. * waitq_sleep(&wq); - * // callback() completed its work, but it may still be accessing - * // wq in waitq_wakeup(). Therefore it is not yet safe to return - * // from waitq_sleep() or it would clobber up our stack (where wq + * // callback() completed its work, but it may still be accessing + * // wq in waitq_wakeup(). Therefore it is not yet safe to return + * // from waitq_sleep() or it would clobber up our stack (where wq * // is stored). waitq_sleep() ensures the wait queue is no longer * // in use by invoking waitq_complete_wakeup() internally. - * + * * // waitq_sleep() returned, it is safe to free wq. * } * @endcode - * + * * @param wq Pointer to a wait queue. */ Index: kernel/generic/src/synch/workqueue.c =================================================================== --- kernel/generic/src/synch/workqueue.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/synch/workqueue.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -54,6 +54,6 @@ struct work_queue { - /* - * Protects everything except activate_worker. + /* + * Protects everything except activate_worker. * Must be acquired after any thread->locks. */ @@ -93,5 +93,5 @@ /* Magic cookie for integrity checks. Immutable. Accessed without lock. */ uint32_t cookie; -#endif +#endif }; @@ -132,5 +132,5 @@ static void interrupt_workers(struct work_queue *workq); static void wait_for_workers(struct work_queue *workq); -static int _workq_enqueue(struct work_queue *workq, work_t *work_item, +static int _workq_enqueue(struct work_queue *workq, work_t *work_item, work_func_t func, bool can_block); static void init_work_item(work_t *work_item, work_func_t func); @@ -150,6 +150,6 @@ void workq_global_worker_init(void) { - /* - * No need for additional synchronization. Stores to word-sized + /* + * No need for additional synchronization. Stores to word-sized * variables are atomic and the change will eventually propagate. * Moreover add_worker() includes the necessary memory barriers @@ -221,5 +221,5 @@ #ifdef CONFIG_DEBUG workq->cookie = 0; -#endif +#endif free(workq); @@ -231,5 +231,5 @@ #ifdef CONFIG_DEBUG workq->cookie = WORKQ_MAGIC; -#endif +#endif irq_spinlock_initialize(&workq->lock, name); @@ -252,6 +252,6 @@ } -/** Initializes a work queue. Returns true if successful. - * +/** Initializes a work queue. Returns true if successful. + * * Before destroying a work queue it must be stopped via * workq_stop(). @@ -268,5 +268,5 @@ assert(!workq_corrupted(workq)); - thread_t *thread = thread_create(worker_thread, workq, TASK, + thread_t *thread = thread_create(worker_thread, workq, TASK, THREAD_FLAG_NONE, workq->name); @@ -297,5 +297,5 @@ cpu_id = CPU->id; - thread->workq = workq; + thread->workq = workq; thread->cpu = &cpus[cpu_id]; thread->workq_blocked = false; @@ -305,5 +305,5 @@ list_append(&thread->workq_link, &workq->workers); } else { - /* + /* * Work queue is shutting down - we must not add the worker * and we cannot destroy it without ready-ing it. Mark it @@ -330,7 +330,7 @@ } -/** Shuts down the work queue. Waits for all pending work items to complete. - * - * workq_stop() may only be run once. +/** Shuts down the work queue. Waits for all pending work items to complete. + * + * workq_stop() may only be run once. */ void workq_stop(struct work_queue *workq) @@ -391,6 +391,6 @@ } -/** Queues a function into the global wait queue without blocking. - * +/** Queues a function into the global wait queue without blocking. + * * See workq_enqueue_noblock() for more details. */ @@ -400,6 +400,6 @@ } -/** Queues a function into the global wait queue; may block. - * +/** Queues a function into the global wait queue; may block. + * * See workq_enqueue() for more details. */ @@ -409,13 +409,13 @@ } -/** Adds a function to be invoked in a separate thread without blocking. - * - * workq_enqueue_noblock() is guaranteed not to block. It is safe +/** Adds a function to be invoked in a separate thread without blocking. + * + * workq_enqueue_noblock() is guaranteed not to block. It is safe * to invoke from interrupt handlers. - * + * * Consider using workq_enqueue() instead if at all possible. Otherwise, - * your work item may have to wait for previously enqueued sleeping + * your work item may have to wait for previously enqueued sleeping * work items to complete if you are unlucky. - * + * * @param workq Work queue where to queue the work item. * @param work_item Work item bookkeeping structure. Must be valid @@ -423,9 +423,9 @@ * @param func User supplied function to invoke in a worker thread. - * @return false if work queue is shutting down; function is not - * queued for further processing. + * @return false if work queue is shutting down; function is not + * queued for further processing. * @return true Otherwise. func() will be invoked in a separate thread. */ -bool workq_enqueue_noblock(struct work_queue *workq, work_t *work_item, +bool workq_enqueue_noblock(struct work_queue *workq, work_t *work_item, work_func_t func) { @@ -433,9 +433,9 @@ } -/** Adds a function to be invoked in a separate thread; may block. - * - * While the workq_enqueue() is unlikely to block, it may do so if too +/** Adds a function to be invoked in a separate thread; may block. + * + * While the workq_enqueue() is unlikely to block, it may do so if too * many previous work items blocked sleeping. - * + * * @param workq Work queue where to queue the work item. * @param work_item Work item bookkeeping structure. Must be valid @@ -443,6 +443,6 @@ * @param func User supplied function to invoke in a worker thread. - * @return false if work queue is shutting down; function is not - * queued for further processing. + * @return false if work queue is shutting down; function is not + * queued for further processing. * @return true Otherwise. func() will be invoked in a separate thread. */ @@ -453,7 +453,7 @@ /** Adds a work item that will be processed by a separate worker thread. - * - * func() will be invoked in another kernel thread and may block. - * + * + * func() will be invoked in another kernel thread and may block. + * * Prefer to call _workq_enqueue() with can_block set. Otherwise * your work item may have to wait for sleeping work items to complete. @@ -461,5 +461,5 @@ * be create without can_block set because creating a thread might * block due to low memory conditions. - * + * * @param workq Work queue where to queue the work item. * @param work_item Work item bookkeeping structure. Must be valid @@ -468,9 +468,9 @@ * @param can_block May adding this work item block? - * @return false if work queue is shutting down; function is not - * queued for further processing. + * @return false if work queue is shutting down; function is not + * queued for further processing. * @return true Otherwise. */ -static int _workq_enqueue(struct work_queue *workq, work_t *work_item, +static int _workq_enqueue(struct work_queue *workq, work_t *work_item, work_func_t func, bool can_block) { @@ -493,6 +493,6 @@ signal_op = signal_worker_logic(workq, can_block); } else { - /* - * During boot there are no workers to signal. Just queue + /* + * During boot there are no workers to signal. Just queue * the work and let future workers take care of it. */ @@ -514,5 +514,5 @@ #ifdef CONFIG_DEBUG work_item->cookie = WORK_ITEM_MAGIC; -#endif +#endif link_initialize(&work_item->queue_link); @@ -537,8 +537,8 @@ assert(workq->activate_pending <= workq->idle_worker_cnt); - /* - * Workers actively running the work func() this very moment and - * are neither blocked nor idle. Exclude ->activate_pending workers - * since they will run their work func() once they get a time slice + /* + * Workers actively running the work func() this very moment and + * are neither blocked nor idle. Exclude ->activate_pending workers + * since they will run their work func() once they get a time slice * and are not running it right now. */ @@ -546,7 +546,7 @@ } -/** - * Returns the number of workers that are running or are about to run work - * func() and that are not blocked. +/** + * Returns the number of workers that are running or are about to run work + * func() and that are not blocked. */ static size_t active_workers(struct work_queue *workq) @@ -554,6 +554,6 @@ assert(irq_spinlock_locked(&workq->lock)); - /* - * Workers actively running the work func() and are neither blocked nor + /* + * Workers actively running the work func() and are neither blocked nor * idle. ->activate_pending workers will run their work func() once they * get a time slice after waking from a condvar wait, so count them @@ -586,9 +586,9 @@ /** Determines how to signal workers if at all. - * + * * @param workq Work queue where a new work item was queued. - * @param can_block True if we may block while signaling a worker or creating + * @param can_block True if we may block while signaling a worker or creating * a new worker. - * + * * @return Function that will notify workers or NULL if no action is needed. */ @@ -601,7 +601,7 @@ signal_op_t signal_op = NULL; - /* - * Workers actively running the work func() and neither blocked nor idle. - * Including ->activate_pending workers that will run their work func() + /* + * Workers actively running the work func() and neither blocked nor idle. + * Including ->activate_pending workers that will run their work func() * once they get a time slice. */ @@ -613,12 +613,12 @@ if (max_load < workq->item_cnt) { - size_t remaining_idle = + size_t remaining_idle = workq->idle_worker_cnt - workq->activate_pending; /* Idle workers still exist - activate one. */ if (remaining_idle > 0) { - /* + /* * Directly changing idle_worker_cnt here would not allow - * workers to recognize spurious wake-ups. Change + * workers to recognize spurious wake-ups. Change * activate_pending instead. */ @@ -633,5 +633,5 @@ if (need_worker && can_block) { signal_op = add_worker_op; - /* + /* * It may take some time to actually create the worker. * We don't want to swamp the thread pool with superfluous @@ -642,5 +642,5 @@ } - /* + /* * We cannot create a new worker but we need one desperately * because all workers are blocked in their work functions. @@ -661,6 +661,6 @@ } } else { - /* - * There are enough active/running workers to process the queue. + /* + * There are enough active/running workers to process the queue. * No need to signal/activate any new workers. */ @@ -674,7 +674,7 @@ static void worker_thread(void *arg) { - /* - * The thread has been created after the work queue was ordered to stop. - * Do not access the work queue and return immediately. + /* + * The thread has been created after the work queue was ordered to stop. + * Do not access the work queue and return immediately. */ if (thread_interrupted(THREAD)) { @@ -760,5 +760,5 @@ return (min_worker_cnt <= workq->idle_worker_cnt); } else { - /* + /* * There is work but we are swamped with too many active workers * that were woken up from sleep at around the same time. We @@ -854,5 +854,5 @@ bool stopping = workq->stopping; bool worker_surplus = worker_unnecessary(workq); - const char *load_str = worker_surplus ? "decreasing" : + const char *load_str = worker_surplus ? "decreasing" : (0 < workq->activate_pending) ? "increasing" : "stable"; @@ -869,5 +869,5 @@ "Stopping: %d\n" "Load: %s\n", - max_worker_cnt, min_worker_cnt, + max_worker_cnt, min_worker_cnt, max_concurrent_workers, max_items_per_worker, total, @@ -895,5 +895,5 @@ while (list_empty(&info->work_queues) && !stop) { - errno_t ret = _condvar_wait_timeout_irq_spinlock(&info->req_cv, + errno_t ret = _condvar_wait_timeout_irq_spinlock(&info->req_cv, &info->lock, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_INTERRUPTIBLE); @@ -902,5 +902,5 @@ if (!stop) { - *pworkq = list_get_instance(list_first(&info->work_queues), + *pworkq = list_get_instance(list_first(&info->work_queues), struct work_queue, nb_link); @@ -932,5 +932,5 @@ list_initialize(&nonblock_adder.work_queues); - nonblock_adder.thread = thread_create(thr_nonblock_add_worker, + nonblock_adder.thread = thread_create(thr_nonblock_add_worker, &nonblock_adder, TASK, THREAD_FLAG_NONE, "kworkq-nb"); @@ -938,5 +938,5 @@ thread_ready(nonblock_adder.thread); } else { - /* + /* * We won't be able to add workers without blocking if all workers * sleep, but at least boot the system. @@ -947,11 +947,11 @@ #ifdef CONFIG_DEBUG -/** Returns true if the workq is definitely corrupted; false if not sure. - * +/** Returns true if the workq is definitely corrupted; false if not sure. + * * Can be used outside of any locks. */ static bool workq_corrupted(struct work_queue *workq) { - /* + /* * Needed to make the most current cookie value set by workq_preinit() * visible even if we access the workq right after it is created but @@ -963,6 +963,6 @@ } -/** Returns true if the work_item is definitely corrupted; false if not sure. - * +/** Returns true if the work_item is definitely corrupted; false if not sure. + * * Must be used with the work queue protecting spinlock locked. */ Index: kernel/generic/src/time/clock.c =================================================================== --- kernel/generic/src/time/clock.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/time/clock.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -75,5 +75,5 @@ * * The applications (and sometimes kernel) need to access accurate - * information about realtime data. We allocate 1 page with these + * information about realtime data. We allocate 1 page with these * data and update it periodically. * Index: kernel/generic/src/time/delay.c =================================================================== --- kernel/generic/src/time/delay.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/time/delay.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -51,5 +51,5 @@ void delay(uint32_t usec) { - /* + /* * The delay loop is calibrated for each and every CPU in the system. * If running in a thread context, it is therefore necessary to disable Index: kernel/generic/src/udebug/udebug_ipc.c =================================================================== --- kernel/generic/src/udebug/udebug_ipc.c (revision 4ed41b3e13c688b74f72670e2c04efe22ad7a9a8) +++ kernel/generic/src/udebug/udebug_ipc.c (revision 3061bc129a855122d429fbba1e623a521aaa164c) @@ -194,5 +194,5 @@ IPC_SET_RETVAL(call->data, 0); /* ARG1=dest, ARG2=size as in IPC_M_DATA_READ so that - same code in process_answer() can be used + same code in process_answer() can be used (no way to distinguish method in answer) */ IPC_SET_ARG1(call->data, uspace_addr); @@ -239,5 +239,5 @@ IPC_SET_RETVAL(call->data, 0); /* ARG1=dest, ARG2=size as in IPC_M_DATA_READ so that - same code in process_answer() can be used + same code in process_answer() can be used (no way to distinguish method in answer) */ IPC_SET_ARG1(call->data, uspace_addr); @@ -286,5 +286,5 @@ IPC_SET_RETVAL(call->data, 0); /* ARG1=dest, ARG2=size as in IPC_M_DATA_READ so that - same code in process_answer() can be used + same code in process_answer() can be used (no way to distinguish method in answer) */ IPC_SET_ARG1(call->data, uspace_addr); @@ -327,5 +327,5 @@ IPC_SET_RETVAL(call->data, 0); /* ARG1=dest, ARG2=size as in IPC_M_DATA_READ so that - same code in process_answer() can be used + same code in process_answer() can be used (no way to distinguish method in answer) */ IPC_SET_ARG1(call->data, uspace_addr); @@ -368,5 +368,5 @@ IPC_SET_RETVAL(call->data, 0); /* ARG1=dest, ARG2=size as in IPC_M_DATA_READ so that - same code in process_answer() can be used + same code in process_answer() can be used (no way to distinguish method in answer) */ IPC_SET_ARG1(call->data, uspace_addr); @@ -407,5 +407,5 @@ IPC_SET_RETVAL(call->data, 0); /* ARG1=dest, ARG2=size as in IPC_M_DATA_READ so that - same code in process_answer() can be used + same code in process_answer() can be used (no way to distinguish method in answer) */ IPC_SET_ARG1(call->data, uspace_dst); @@ -438,5 +438,5 @@ IPC_SET_RETVAL(call->data, EINVAL); ipc_answer(&TASK->kb.box, call); - return; + return; } }