Changeset 3bacee1 in mainline for kernel/generic/src/adt/cht.c


Ignore:
Timestamp:
2018-04-12T16:27:17Z (7 years ago)
Author:
Jiri Svoboda <jiri@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
3cf22f9
Parents:
76d0981d
git-author:
Jiri Svoboda <jiri@…> (2018-04-11 19:25:33)
git-committer:
Jiri Svoboda <jiri@…> (2018-04-12 16:27:17)
Message:

Make ccheck-fix again and commit more good files.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • kernel/generic/src/adt/cht.c

    r76d0981d r3bacee1  
    407407static size_t size_to_order(size_t bucket_cnt, size_t min_order);
    408408static cht_buckets_t *alloc_buckets(size_t order, bool set_invalid,
    409         bool can_block);
     409    bool can_block);
    410410static inline cht_link_t *find_lazy(cht_t *h, void *key);
    411411static cht_link_t *search_bucket(cht_t *h, marked_ptr_t head, void *key,
    412         size_t search_hash);
     412    size_t search_hash);
    413413static cht_link_t *find_resizing(cht_t *h, void *key, size_t hash,
    414         marked_ptr_t old_head, size_t old_idx);
     414    marked_ptr_t old_head, size_t old_idx);
    415415static bool insert_impl(cht_t *h, cht_link_t *item, cht_link_t **dup_item);
    416416static bool insert_at(cht_link_t *item, const wnd_t *wnd, walk_mode_t walk_mode,
    417         bool *resizing);
     417    bool *resizing);
    418418static bool has_duplicate(cht_t *h, const cht_link_t *item, size_t hash,
    419         cht_link_t *cur, cht_link_t **dup_item);
     419    cht_link_t *cur, cht_link_t **dup_item);
    420420static cht_link_t *find_duplicate(cht_t *h, const cht_link_t *item, size_t hash,
    421         cht_link_t *start);
     421    cht_link_t *start);
    422422static bool remove_pred(cht_t *h, size_t hash, equal_pred_t pred, void *pred_arg);
    423423static bool delete_at(cht_t *h, wnd_t *wnd, walk_mode_t walk_mode,
    424         bool *deleted_but_gc, bool *resizing);
     424    bool *deleted_but_gc, bool *resizing);
    425425static bool mark_deleted(cht_link_t *cur, walk_mode_t walk_mode, bool *resizing);
    426426static bool unlink_from_pred(wnd_t *wnd, walk_mode_t walk_mode, bool *resizing);
    427427static bool find_wnd_and_gc_pred(cht_t *h, size_t hash, walk_mode_t walk_mode,
    428         equal_pred_t pred, void *pred_arg, wnd_t *wnd, bool *resizing);
     428    equal_pred_t pred, void *pred_arg, wnd_t *wnd, bool *resizing);
    429429static bool find_wnd_and_gc(cht_t *h, size_t hash, walk_mode_t walk_mode,
    430         wnd_t *wnd, bool *resizing);
     430    wnd_t *wnd, bool *resizing);
    431431static bool gc_deleted_node(cht_t *h, walk_mode_t walk_mode, wnd_t *wnd,
    432         bool *resizing);
     432    bool *resizing);
    433433static bool join_completed(cht_t *h, const wnd_t *wnd);
    434434static void upd_resizing_head(cht_t *h, size_t hash, marked_ptr_t **phead,
    435         bool *join_finishing,  walk_mode_t *walk_mode);
     435    bool *join_finishing,  walk_mode_t *walk_mode);
    436436static void item_removed(cht_t *h);
    437437static void item_inserted(cht_t *h);
    … …  
    442442static void complete_head_move(marked_ptr_t *psrc_head, marked_ptr_t *pdest_head);
    443443static void split_bucket(cht_t *h, marked_ptr_t *psrc_head,
    444         marked_ptr_t *pdest_head, size_t split_hash);
     444    marked_ptr_t *pdest_head, size_t split_hash);
    445445static void mark_join_follows(cht_t *h, marked_ptr_t *psrc_head,
    446         size_t split_hash, wnd_t *wnd);
     446    size_t split_hash, wnd_t *wnd);
    447447static void mark_join_node(cht_link_t *join_node);
    448448static void join_buckets(cht_t *h, marked_ptr_t *psrc_head,
    449         marked_ptr_t *pdest_head, size_t split_hash);
     449    marked_ptr_t *pdest_head, size_t split_hash);
    450450static void link_to_join_node(cht_t *h, marked_ptr_t *pdest_head,
    451         cht_link_t *join_node, size_t split_hash);
     451    cht_link_t *join_node, size_t split_hash);
    452452static void resize_table(work_t *arg);
    453453static void grow_table(cht_t *h);
    … …  
    455455static void cleanup_join_node(cht_t *h, marked_ptr_t *new_head);
    456456static void clear_join_and_gc(cht_t *h, cht_link_t *join_node,
    457         marked_ptr_t *new_head);
     457    marked_ptr_t *new_head);
    458458static void cleanup_join_follows(cht_t *h, marked_ptr_t *new_head);
    459459static marked_ptr_t make_link(const cht_link_t *next, mark_t mark);
    460 static cht_link_t * get_next(marked_ptr_t link);
     460static cht_link_t *get_next(marked_ptr_t link);
    461461static mark_t get_mark(marked_ptr_t link);
    462462static void next_wnd(wnd_t *wnd);
    … …  
    472472static size_t shrink_idx(size_t idx);
    473473static marked_ptr_t cas_link(marked_ptr_t *link, const cht_link_t *cur_next,
    474         mark_t cur_mark, const cht_link_t *new_next, mark_t new_mark);
     474    mark_t cur_mark, const cht_link_t *new_next, mark_t new_mark);
    475475static marked_ptr_t _cas_link(marked_ptr_t *link, marked_ptr_t cur,
    476         marked_ptr_t new);
     476    marked_ptr_t new);
    477477static void cas_order_barrier(void);
    478478
    … …  
    513513 */
    514514bool cht_create(cht_t *h, size_t init_size, size_t min_size, size_t max_load,
    515         bool can_block, cht_ops_t *op)
     515    bool can_block, cht_ops_t *op)
    516516{
    517517        assert(h);
    … …  
    572572        size_t bucket_cnt = (1 << order);
    573573        size_t bytes =
    574                 sizeof(cht_buckets_t) + (bucket_cnt - 1) * sizeof(marked_ptr_t);
     574            sizeof(cht_buckets_t) + (bucket_cnt - 1) * sizeof(marked_ptr_t);
    575575        cht_buckets_t *b = malloc(bytes, can_block ? 0 : FRAME_ATOMIC);
    576576
    … …  
    580580        b->order = order;
    581581
    582         marked_ptr_t head_link = set_invalid
    583                 ? make_link(&sentinel, N_INVALID)
    584                 : make_link(&sentinel, N_NORMAL);
     582        marked_ptr_t head_link = set_invalid ?
     583            make_link(&sentinel, N_INVALID) :
     584            make_link(&sentinel, N_NORMAL);
    585585
    586586        for (size_t i = 0; i < bucket_cnt; ++i) {
    … …  
    733733/** Searches the bucket at head for key using search_hash. */
    734734static inline cht_link_t *search_bucket(cht_t *h, marked_ptr_t head, void *key,
    735         size_t search_hash)
     735    size_t search_hash)
    736736{
    737737        /*
    … …  
    781781/** Searches for the key while the table is undergoing a resize. */
    782782static cht_link_t *find_resizing(cht_t *h, void *key, size_t hash,
    783         marked_ptr_t old_head, size_t old_idx)
     783    marked_ptr_t old_head, size_t old_idx)
    784784{
    785785        assert(N_INVALID == get_mark(old_head));
    … …  
    10221022 */
    10231023inline static bool insert_at(cht_link_t *item, const wnd_t *wnd,
    1024         walk_mode_t walk_mode, bool *resizing)
     1024    walk_mode_t walk_mode, bool *resizing)
    10251025{
    10261026        marked_ptr_t ret;
    … …  
    10781078 */
    10791079static inline bool has_duplicate(cht_t *h, const cht_link_t *item, size_t hash,
    1080         cht_link_t *cur, cht_link_t **dup_item)
     1080    cht_link_t *cur, cht_link_t **dup_item)
    10811081{
    10821082        assert(cur);
    1083         assert(cur == &sentinel || hash <= node_hash(h, cur)
    1084                 || node_hash(h, cur) == h->invalid_hash);
     1083        assert(cur == &sentinel || hash <= node_hash(h, cur) ||
     1084            node_hash(h, cur) == h->invalid_hash);
    10851085
    10861086        /* hash < node_hash(h, cur) */
    … …  
    11011101/** Returns an item that is equal to \a item starting in a chain at \a start. */
    11021102static cht_link_t *find_duplicate(cht_t *h, const cht_link_t *item, size_t hash,
    1103         cht_link_t *start)
     1103    cht_link_t *start)
    11041104{
    11051105        assert(hash <= node_hash(h, start) || h->invalid_hash == node_hash(h, start));
    … …  
    12011201
    12021202                if (!find_wnd_and_gc_pred(
    1203                         h, hash, walk_mode, pred, pred_arg, &wnd, &resizing)) {
     1203                    h, hash, walk_mode, pred, pred_arg, &wnd, &resizing)) {
    12041204                        /* Could not GC a node; or detected an unexpected resize. */
    12051205                        continue;
    … …  
    12531253 */
    12541254static inline bool delete_at(cht_t *h, wnd_t *wnd, walk_mode_t walk_mode,
    1255         bool *deleted_but_gc, bool *resizing)
     1255    bool *deleted_but_gc, bool *resizing)
    12561256{
    12571257        assert(wnd->cur && wnd->cur != &sentinel);
    … …  
    12831283/** Marks cur logically deleted. Returns false to request a retry. */
    12841284static inline bool mark_deleted(cht_link_t *cur, walk_mode_t walk_mode,
    1285         bool *resizing)
     1285    bool *resizing)
    12861286{
    12871287        assert(cur && cur != &sentinel);
    … …  
    13091309
    13101310                marked_ptr_t ret =
    1311                         cas_link(&cur->link, next, cur_mark, next, cur_mark | N_DELETED);
     1311                    cas_link(&cur->link, next, cur_mark, next, cur_mark | N_DELETED);
    13121312
    13131313                if (ret != make_link(next, cur_mark))
    … …  
    13201320/** Unlinks wnd.cur from wnd.ppred. Returns false if it should be retried. */
    13211321static inline bool unlink_from_pred(wnd_t *wnd, walk_mode_t walk_mode,
    1322         bool *resizing)
     1322    bool *resizing)
    13231323{
    13241324        assert(wnd->cur != &sentinel);
    … …  
    13541354                if (pred_link != ret) {
    13551355                        /* If we're not resizing the table there are no JF/JN nodes. */
    1356                         *resizing = (walk_mode == WM_NORMAL)
    1357                                 && (N_JOIN_FOLLOWS & get_mark(ret));
     1356                        *resizing = (walk_mode == WM_NORMAL) &&
     1357                            (N_JOIN_FOLLOWS & get_mark(ret));
    13581358                        return false;
    13591359                }
    … …  
    13891389 */
    13901390static bool find_wnd_and_gc_pred(cht_t *h, size_t hash, walk_mode_t walk_mode,
    1391         equal_pred_t pred, void *pred_arg, wnd_t *wnd, bool *resizing)
     1391    equal_pred_t pred, void *pred_arg, wnd_t *wnd, bool *resizing)
    13921392{
    13931393        assert(wnd->cur);
    … …  
    14591459 */
    14601460static bool find_wnd_and_gc(cht_t *h, size_t hash, walk_mode_t walk_mode,
    1461         wnd_t *wnd, bool *resizing)
     1461    wnd_t *wnd, bool *resizing)
    14621462{
    14631463try_again:
    … …  
    14891489/** Garbage collects the N_DELETED node at \a wnd skipping join nodes. */
    14901490static bool gc_deleted_node(cht_t *h, walk_mode_t walk_mode, wnd_t *wnd,
    1491         bool *resizing)
     1491    bool *resizing)
    14921492{
    14931493        assert(N_DELETED & get_mark(wnd->cur->link));
    … …  
    14981498        } else {
    14991499                /* Ordinary deleted node or a deleted JOIN_FOLLOWS. */
    1500                 assert(walk_mode != WM_LEAVE_JOIN
    1501                         || !((N_JOIN | N_JOIN_FOLLOWS) & get_mark(wnd->cur->link)));
     1500                assert(walk_mode != WM_LEAVE_JOIN ||
     1501                    !((N_JOIN | N_JOIN_FOLLOWS) & get_mark(wnd->cur->link)));
    15021502
    15031503                /* Unlink an ordinary deleted node, move JOIN_FOLLOWS mark. */
    … …  
    15911591 */
    15921592static void upd_resizing_head(cht_t *h, size_t hash, marked_ptr_t **phead,
    1593         bool *join_finishing,  walk_mode_t *walk_mode)
     1593    bool *join_finishing,  walk_mode_t *walk_mode)
    15941594{
    15951595        cht_buckets_t *b = rcu_access(h->b);
    … …  
    16411641                        *walk_mode = WM_LEAVE_JOIN;
    16421642                }
    1643         } else if (h->new_b->order < b->order ) {
     1643        } else if (h->new_b->order < b->order) {
    16441644                /* Shrinking the table. */
    16451645
    … …  
    17021702 */
    17031703static inline void help_head_move(marked_ptr_t *psrc_head,
    1704         marked_ptr_t *pdest_head)
     1704    marked_ptr_t *pdest_head)
    17051705{
    17061706        /* Head move has to in progress already when calling this func. */
    … …  
    17431743                /* Mark the normal/clean src link immutable/const. */
    17441744                ret = cas_link(psrc_head, next, N_NORMAL, next, N_CONST);
    1745         } while(ret != src_link && !(N_CONST & get_mark(ret)));
     1745        } while (ret != src_link && !(N_CONST & get_mark(ret)));
    17461746}
    17471747
    … …  
    17831783 */
    17841784static void split_bucket(cht_t *h, marked_ptr_t *psrc_head,
    1785         marked_ptr_t *pdest_head, size_t split_hash)
     1785    marked_ptr_t *pdest_head, size_t split_hash)
    17861786{
    17871787        /* Already split. */
    … …  
    18841884 */
    18851885static void mark_join_follows(cht_t *h, marked_ptr_t *psrc_head,
    1886         size_t split_hash, wnd_t *wnd)
     1886    size_t split_hash, wnd_t *wnd)
    18871887{
    18881888        /* See comment in split_bucket(). */
    … …  
    19091909                 * that a join node follows. It must be clean/normal.
    19101910                 */
    1911                 marked_ptr_t ret
    1912                         = cas_link(wnd->ppred, wnd->cur, N_NORMAL, wnd->cur, N_JOIN_FOLLOWS);
     1911                marked_ptr_t ret =
     1912                    cas_link(wnd->ppred, wnd->cur, N_NORMAL, wnd->cur, N_JOIN_FOLLOWS);
    19131913
    19141914                /*
    … …  
    19161916                 * if also marked deleted - unlinking the node will move the JF mark).
    19171917                 */
    1918                 done = (ret == make_link(wnd->cur, N_NORMAL))
    1919                         || (N_JOIN_FOLLOWS & get_mark(ret));
     1918                done = (ret == make_link(wnd->cur, N_NORMAL)) ||
     1919                    (N_JOIN_FOLLOWS & get_mark(ret));
    19201920        } while (!done);
    19211921}
    … …  
    19351935                 * because its predecessor is marked with JOIN_FOLLOWS or CONST.
    19361936                 */
    1937                 marked_ptr_t ret
    1938                         = cas_link(&join_node->link, next, mark, next, mark | N_JOIN);
     1937                marked_ptr_t ret =
     1938                    cas_link(&join_node->link, next, mark, next, mark | N_JOIN);
    19391939
    19401940                /* Successfully marked or already marked as a join node. */
    1941                 done = (ret == make_link(next, mark))
    1942                         || (N_JOIN & get_mark(ret));
    1943         } while(!done);
     1941                done = (ret == make_link(next, mark)) ||
     1942                    (N_JOIN & get_mark(ret));
     1943        } while (!done);
    19441944}
    19451945
    … …  
    19521952 */
    19531953static void join_buckets(cht_t *h, marked_ptr_t *psrc_head,
    1954         marked_ptr_t *pdest_head, size_t split_hash)
     1954    marked_ptr_t *pdest_head, size_t split_hash)
    19551955{
    19561956        /* Buckets already joined. */
    … …  
    20592059 */
    20602060static void link_to_join_node(cht_t *h, marked_ptr_t *pdest_head,
    2061         cht_link_t *join_node, size_t split_hash)
     2061    cht_link_t *join_node, size_t split_hash)
    20622062{
    20632063        bool done = false;
    … …  
    20782078                if (wnd.cur != &sentinel) {
    20792079                        /* Must be from the new appended bucket. */
    2080                         assert(split_hash <= node_hash(h, wnd.cur)
    2081                                 || h->invalid_hash == node_hash(h, wnd.cur));
     2080                        assert(split_hash <= node_hash(h, wnd.cur) ||
     2081                            h->invalid_hash == node_hash(h, wnd.cur));
    20822082                        return;
    20832083                }
    … …  
    20852085                /* Reached the tail of pdest_head - link it to the join node. */
    20862086                marked_ptr_t ret =
    2087                         cas_link(wnd.ppred, &sentinel, N_NORMAL, join_node, N_NORMAL);
     2087                    cas_link(wnd.ppred, &sentinel, N_NORMAL, join_node, N_NORMAL);
    20882088
    20892089                done = (ret == make_link(&sentinel, N_NORMAL));
    … …  
    23202320                        size_t split_hash = calc_split_hash(old_idx, h->b->order);
    23212321                        join_buckets(h, &h->b->head[old_idx], &h->new_b->head[new_idx],
    2322                                 split_hash);
     2322                            split_hash);
    23232323                }
    23242324        }
    … …  
    23912391/** Clears the join_node's N_JOIN mark frees it if marked N_DELETED as well. */
    23922392static void clear_join_and_gc(cht_t *h, cht_link_t *join_node,
    2393         marked_ptr_t *new_head)
     2393    marked_ptr_t *new_head)
    23942394{
    23952395        assert(join_node != &sentinel);
    … …  
    24062406
    24072407                marked_ptr_t ret =
    2408                         _cas_link(&join_node->link, jn_link, make_link(next, cleared_mark));
     2408                    _cas_link(&join_node->link, jn_link, make_link(next, cleared_mark));
    24092409
    24102410                /* Done if the mark was cleared. Retry if a new node was inserted. */
    … …  
    24312431
    24322432                done = find_wnd_and_gc_pred(h, jn_hash, WM_NORMAL, same_node_pred,
    2433                         join_node, &wnd, &resizing);
     2433                    join_node, &wnd, &resizing);
    24342434
    24352435                assert(!resizing);
    … …  
    24832483                                cht_link_t *next = get_next(*cur_link);
    24842484                                marked_ptr_t ret =
    2485                                         cas_link(cur_link, next, N_JOIN_FOLLOWS, &sentinel, N_NORMAL);
    2486 
    2487                                 assert(next == &sentinel
    2488                                         || ((N_JOIN | N_JOIN_FOLLOWS) & get_mark(ret)));
     2485                                    cas_link(cur_link, next, N_JOIN_FOLLOWS, &sentinel, N_NORMAL);
     2486
     2487                                assert(next == &sentinel ||
     2488                                    ((N_JOIN | N_JOIN_FOLLOWS) & get_mark(ret)));
    24892489
    24902490                                /* Successfully cleared the JF mark of a non-deleted node. */
    … …  
    25592559static inline size_t node_hash(cht_t *h, const cht_link_t *item)
    25602560{
    2561         assert(item->hash == h->invalid_hash
    2562                 || item->hash == sentinel.hash
    2563                 || item->hash == calc_node_hash(h, item));
     2561        assert(item->hash == h->invalid_hash ||
     2562            item->hash == sentinel.hash ||
     2563            item->hash == calc_node_hash(h, item));
    25642564
    25652565        return item->hash;
    … …  
    25952595
    25962596/** Strips any marks from the next item link and returns the next item's address.*/
    2597 static inline cht_link_t * get_next(marked_ptr_t link)
    2598 {
    2599         return (cht_link_t*)(link & ~N_MARK_MASK);
     2597static inline cht_link_t *get_next(marked_ptr_t link)
     2598{
     2599        return (cht_link_t *)(link & ~N_MARK_MASK);
    26002600}
    26012601
    … …  
    26202620static bool same_node_pred(void *node, const cht_link_t *item2)
    26212621{
    2622         const cht_link_t *item1 = (const cht_link_t*) node;
     2622        const cht_link_t *item1 = (const cht_link_t *) node;
    26232623        return item1 == item2;
    26242624}
    … …  
    26262626/** Compare-and-swaps a next item link. */
    26272627static inline marked_ptr_t cas_link(marked_ptr_t *link, const cht_link_t *cur_next,
    2628         mark_t cur_mark, const cht_link_t *new_next, mark_t new_mark)
     2628    mark_t cur_mark, const cht_link_t *new_next, mark_t new_mark)
    26292629{
    26302630        return _cas_link(link, make_link(cur_next, cur_mark),
    2631                 make_link(new_next, new_mark));
     2631            make_link(new_next, new_mark));
    26322632}
    26332633
    26342634/** Compare-and-swaps a next item link. */
    26352635static inline marked_ptr_t _cas_link(marked_ptr_t *link, marked_ptr_t cur,
    2636         marked_ptr_t new)
     2636    marked_ptr_t new)
    26372637{
    26382638        assert(link != &sentinel.link);
    … …  
    26902690         * is already visible to cpu3.   *
    26912691         */
    2692         void *expected = (void*)cur;
     2692        void *expected = (void *)cur;
    26932693
    26942694        /*
    … …  
    26972697         * of explicit memory barriers.
    26982698         */
    2699         __atomic_compare_exchange_n((void**)link, &expected, (void *)new, false,
    2700                 __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE);
     2699        __atomic_compare_exchange_n((void **)link, &expected, (void *)new, false,
     2700            __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE);
    27012701
    27022702        return (marked_ptr_t) expected;
Note: See TracChangeset for help on using the changeset viewer.