Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset 6eaed07 in mainline


Ignore:
Timestamp:
2012-08-04T21:14:24Z (9 years ago)
Author:
Adam Hraska <adam.hraska+hos@…>
Branches:
lfn, master
Children:
f1c7755
Parents:
26d8df3
Message:

cht: Switched to using a sentinel node instead of checking for NULLs. Added hash memoization (stored in cht_link_t.rcu_link.func function pointer).

Location:
kernel
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • kernel/generic/include/adt/cht.h

    r26d8df3 r6eaed07  
    4646/** Concurrent hash table node link. */
    4747typedef struct cht_link {
    48         /* Must be placed first. */
    49         rcu_item_t rcu_link;
     48        /* Must be placed first.
     49         *
     50         * The function pointer (rcu_link.func) is used to store the item's
     51         * memoized hash.
     52         */
     53        union {
     54                rcu_item_t rcu_link;
     55                size_t hash;
     56        };
    5057        /** Link to the next item in the bucket including any marks. */
    5158        cht_ptr_t link;
     
    7178        cht_ops_t *op;
    7279       
    73         size_t min_order;
    7480        cht_buckets_t *b;
    7581        cht_buckets_t *new_b;
     82        size_t invalid_hash;
    7683
     84        size_t min_order;
    7785        size_t max_load;
    7886        work_t resize_work;
  • kernel/generic/src/adt/cht.c

    r26d8df3 r6eaed07  
    8282        cht_link_t *last;
    8383} wnd_t;
     84
     85
     86/* Sentinel node used by all buckets. Stores the greatest possible hash value.*/
     87static const cht_link_t sentinel = {
     88        .link = 0,
     89        .hash = -1
     90};
    8491
    8592
     
    140147static void next_wnd(wnd_t *wnd);
    141148static bool same_node_pred(void *node, const cht_link_t *item2);
    142 static size_t key_hash(cht_t *h, void *key);
     149static size_t calc_key_hash(cht_t *h, void *key);
    143150static size_t node_hash(cht_t *h, const cht_link_t *item);
     151static size_t calc_node_hash(cht_t *h, const cht_link_t *item);
     152static void memoize_node_hash(cht_t *h, cht_link_t *item);
    144153static size_t calc_split_hash(size_t split_idx, size_t order);
    145154static size_t calc_bucket_idx(size_t hash, size_t order);
     
    159168        ASSERT(h);
    160169        ASSERT(op && op->hash && op->key_hash && op->equal && op->key_equal);
     170        /* Memoized hashes are stored in the rcu_link.func function pointer. */
     171        ASSERT(sizeof(size_t) == sizeof(rcu_func_t));
     172        ASSERT(sentinel.hash == (uintptr_t)sentinel.rcu_link.func);
    161173
    162174        /* All operations are compulsory. */
     
    178190        atomic_set(&h->item_cnt, 0);
    179191        atomic_set(&h->resize_reqs, 0);
     192        /*
     193         * Cached item hashes are stored in item->rcu_link.func. Once the item
     194         * is deleted rcu_link.func will contain the value of invalid_hash.
     195         */
     196        h->invalid_hash = (uintptr_t)h->op->remove_callback;
     197       
    180198        /* Ensure the initialization takes place before we start using the table. */
    181199        write_barrier();
     
    196214        b->order = order;
    197215       
    198         marked_ptr_t head_link
    199                 = set_invalid ? make_link(0, N_INVALID) : make_link(0, N_NORMAL);
     216        marked_ptr_t head_link = set_invalid
     217                ? make_link(&sentinel, N_INVALID)
     218                : make_link(&sentinel, N_NORMAL);
    200219       
    201220        for (size_t i = 0; i < bucket_cnt; ++i) {
     
    253272        ASSERT(rcu_read_locked());
    254273       
    255         size_t hash = key_hash(h, key);
     274        size_t hash = calc_key_hash(h, key);
    256275       
    257276        cht_buckets_t *b = rcu_access(h->b);
     
    282301        ASSERT(item);
    283302       
    284         return find_duplicate(h, item, node_hash(h, item), get_next(item->link));
     303        return find_duplicate(h, item, calc_node_hash(h, item), get_next(item->link));
    285304}
    286305
     
    288307        size_t search_hash)
    289308{
    290         cht_link_t *cur = get_next(head);
    291        
    292         while (cur) {
    293                 /*
    294                  * It is safe to access nodes even outside of this bucket (eg when
    295                  * splitting the bucket). The resizer makes sure that any node we
    296                  * may find by following the next pointers is allocated.
    297                  */
     309        /*
     310         * It is safe to access nodes even outside of this bucket (eg when
     311         * splitting the bucket). The resizer makes sure that any node we
     312         * may find by following the next pointers is allocated.
     313         */
     314
     315        cht_link_t *cur = 0;
     316        marked_ptr_t prev = head;
     317
     318try_again:
     319        /* Filter out items with different hashes. */
     320        do {
     321                cur = get_next(prev);
     322                ASSERT(cur);
     323                prev = cur->link;
     324        } while (node_hash(h, cur) < search_hash);
     325       
     326        /*
     327         * Only search for an item with an equal key if cur is not the sentinel
     328         * node or a node with a different hash.
     329         */
     330        while (node_hash(h, cur) == search_hash) {
    298331                if (h->op->key_equal(key, cur)) {
    299332                        if (!(N_DELETED & get_mark(cur->link)))
     
    302335               
    303336                cur = get_next(cur->link);
     337                ASSERT(cur);
     338        }
     339       
     340        /*
     341         * In the unlikely case that we have encountered a node whose cached
     342         * hash has been overwritten due to a pending rcu_call for it, skip
     343         * the node and try again.
     344         */
     345        if (node_hash(h, cur) == h->invalid_hash) {
     346                prev = cur->link;
     347                goto try_again;
    304348        }
    305349       
     
    413457                 * joining link (or the item is not in the table).
    414458                 */
    415                 if (move_src_idx != old_idx && get_next(old_head)) {
     459                if (move_src_idx != old_idx && get_next(old_head) != &sentinel) {
    416460                        /*
    417461                         * Note that old_head (the bucket to be merged into new_head)
     
    459503
    460504        cht_buckets_t *b = rcu_access(h->b);
     505        memoize_node_hash(h, item);
    461506        size_t hash = node_hash(h, item);
    462507        size_t idx = calc_bucket_idx(hash, b->order);
     
    552597        const wnd_t *wnd)
    553598{
    554         ASSERT(0 == wnd->cur || hash <= node_hash(h, wnd->cur));
    555        
    556         if (0 == wnd->cur || hash < node_hash(h, wnd->cur))
     599        ASSERT(wnd->cur);
     600        ASSERT(wnd->cur == &sentinel || hash <= node_hash(h, wnd->cur)
     601                || node_hash(h, wnd->cur) == h->invalid_hash);
     602       
     603        /* hash < node_hash(h, wnd->cur) */
     604        if (hash != node_hash(h, wnd->cur) && h->invalid_hash != node_hash(h, wnd->cur))
    557605                return false;
    558606
     
    569617        cht_link_t *start)
    570618{
    571         ASSERT(0 == start || hash <= node_hash(h, start));
     619        ASSERT(hash <= node_hash(h, start) || h->invalid_hash == node_hash(h, start));
    572620
    573621        cht_link_t *cur = start;
    574622       
    575         while (cur && node_hash(h, cur) == hash) {
     623try_again:     
     624        ASSERT(cur);
     625
     626        while (node_hash(h, cur) == hash) {
     627                ASSERT(cur != &sentinel);
     628               
    576629                bool deleted = (N_DELETED & get_mark(cur->link));
    577630               
     
    581634               
    582635                cur = get_next(cur->link);
     636                ASSERT(cur);
    583637        }
     638
     639        if (h->invalid_hash == node_hash(h, cur)) {
     640                cur = get_next(cur->link);
     641                goto try_again;
     642        }
    584643       
    585644        return 0;       
     
    590649        ASSERT(h);
    591650       
    592         size_t hash = key_hash(h, key);
     651        size_t hash = calc_key_hash(h, key);
    593652        size_t removed = 0;
    594653       
     
    609668         * we search for it again from the beginning of the correct bucket.
    610669         */
    611         size_t hash = node_hash(h, item);
     670        size_t hash = calc_node_hash(h, item);
    612671        return remove_pred(h, hash, same_node_pred, item);
    613672}
     
    666725                        break;
    667726               
    668                 bool found = wnd.cur && pred(pred_arg, wnd.cur);
     727                bool found = (wnd.cur != &sentinel && pred(pred_arg, wnd.cur));
    669728               
    670729                if (!found) {
     
    684743        bool *deleted_but_gc, bool *resizing)
    685744{
    686         ASSERT(wnd->cur);
     745        ASSERT(wnd->cur && wnd->cur != &sentinel);
    687746       
    688747        *deleted_but_gc = false;
     
    713772        bool *resizing)
    714773{
    715         ASSERT(cur);
     774        ASSERT(cur && cur != &sentinel);
    716775       
    717776        /*
     
    749808        bool *resizing)
    750809{
     810        ASSERT(wnd->cur != &sentinel);
    751811        ASSERT(wnd->cur && (N_DELETED & get_mark(wnd->cur->link)));
    752812       
     
    793853        equal_pred_t pred, void *pred_arg, wnd_t *wnd, bool *resizing)
    794854{
    795         if (!wnd->cur)
     855        ASSERT(wnd->cur);
     856       
     857        if (wnd->cur == &sentinel)
    796858                return true;
    797859       
     
    802864         */
    803865       
    804         size_t cur_hash = node_hash(h, wnd->cur);
     866        size_t cur_hash;
     867
     868try_again:     
     869        cur_hash = node_hash(h, wnd->cur);
    805870               
    806871        while (cur_hash <= hash) {
     872                ASSERT(wnd->cur && wnd->cur != &sentinel);
     873               
    807874                /* GC any deleted nodes on the way. */
    808875                if (N_DELETED & get_mark(wnd->cur->link)) {
     
    819886                }
    820887               
    821                 /* The searched for node is not in the current bucket. */
    822                 if (!wnd->cur)
    823                         return true;
    824                
    825888                cur_hash = node_hash(h, wnd->cur);
     889        }
     890       
     891        if (cur_hash == h->invalid_hash) {
     892                next_wnd(wnd);
     893                ASSERT(wnd->cur);
     894                goto try_again;
    826895        }
    827896       
     
    834903        wnd_t *wnd, bool *resizing)
    835904{
    836         while (wnd->cur && node_hash(h, wnd->cur) < hash) {
     905try_again:
     906        ASSERT(wnd->cur);
     907
     908        while (node_hash(h, wnd->cur) < hash) {
    837909                /* GC any deleted nodes along the way to our desired node. */
    838910                if (N_DELETED & get_mark(wnd->cur->link)) {
     
    844916                        next_wnd(wnd);
    845917                }
    846         }
    847        
     918               
     919                ASSERT(wnd->cur);
     920        }
     921       
     922        if (node_hash(h, wnd->cur) == h->invalid_hash) {
     923                next_wnd(wnd);
     924                goto try_again;
     925        }
     926
    848927        /* wnd->cur may be 0 or even marked N_DELETED. */
    849928        return true;
     
    894973         */
    895974        ASSERT(h->b->order > h->new_b->order);
     975        ASSERT(wnd->cur);
    896976       
    897977        /* Either we did not need the joining link or we have already followed it.*/
    898         if (wnd->cur)
     978        if (wnd->cur != &sentinel)
    899979                return true;
    900980       
    901981        /* We have reached the end of a bucket. */
    902982       
    903         if (wnd->last) {
     983        if (wnd->last != &sentinel) {
    904984                size_t last_seen_hash = node_hash(h, wnd->last);
     985               
     986                if (last_seen_hash == h->invalid_hash) {
     987                        last_seen_hash = calc_node_hash(h, wnd->last);
     988                }
     989               
    905990                size_t last_old_idx = calc_bucket_idx(last_seen_hash, h->b->order);
    906991                size_t move_src_idx = grow_idx(shrink_idx(last_old_idx));
    907992               
    908993                /*
    909                  * Last was in the joining bucket - if the searched for node is there
    910                  * we will find it.
     994                 * Last node seen was in the joining bucket - if the searched
     995                 * for node is there we will find it.
    911996                 */
    912997                if (move_src_idx != last_old_idx)
     
    9941079                        }
    9951080                       
    996                         /* The resizer sets pold_head to 0 when all cpus see the bucket join.*/
    997                         *join_finishing = (0 != get_next(*pold_head));
     1081                        /*
     1082                         * The resizer sets pold_head to &sentinel when all cpus are
     1083                         * guaranteed to see the bucket join.
     1084                         */
     1085                        *join_finishing = (&sentinel != get_next(*pold_head));
    9981086                }
    9991087               
     
    10721160        marked_ptr_t ret;
    10731161       
    1074         ret = cas_link(pdest_head, 0, N_INVALID, next, N_NORMAL);
    1075         ASSERT(ret == make_link(0, N_INVALID) || (N_NORMAL == get_mark(ret)));
     1162        ret = cas_link(pdest_head, &sentinel, N_INVALID, next, N_NORMAL);
     1163        ASSERT(ret == make_link(&sentinel, N_INVALID) || (N_NORMAL == get_mark(ret)));
    10761164        cas_order_barrier();
    10771165       
     
    11401228       
    11411229        /* There are nodes in the dest bucket, ie the second part of the split. */
    1142         if (wnd.cur) {
     1230        if (wnd.cur != &sentinel) {
    11431231                /*
    11441232                 * Mark the first node of the dest bucket as a join node so
     
    11551243       
    11561244        /* Link the dest head to the second part of the split. */
    1157         marked_ptr_t ret = cas_link(pdest_head, 0, N_INVALID, wnd.cur, N_NORMAL);
    1158         ASSERT(ret == make_link(0, N_INVALID) || (N_NORMAL == get_mark(ret)));
     1245        marked_ptr_t ret =
     1246                cas_link(pdest_head, &sentinel, N_INVALID, wnd.cur, N_NORMAL);
     1247        ASSERT(ret == make_link(&sentinel, N_INVALID) || (N_NORMAL == get_mark(ret)));
    11591248        cas_order_barrier();
    11601249       
     
    13021391        cht_link_t *join_node = get_next(*psrc_head);
    13031392
    1304         if (join_node) {
     1393        if (join_node != &sentinel) {
    13051394                mark_join_node(join_node);
    13061395                cas_order_barrier();
     
    13351424                ASSERT(!resizing);
    13361425               
    1337                 if (wnd.cur) {
     1426                if (wnd.cur != &sentinel) {
    13381427                        /* Must be from the new appended bucket. */
    1339                         ASSERT(split_hash <= node_hash(h, wnd.cur));
     1428                        ASSERT(split_hash <= node_hash(h, wnd.cur)
     1429                                || h->invalid_hash == node_hash(h, wnd.cur));
    13401430                        return;
    13411431                }
    13421432               
    13431433                /* Reached the tail of pdest_head - link it to the join node. */
    1344                 marked_ptr_t ret = cas_link(wnd.ppred, 0, N_NORMAL, join_node, N_NORMAL);
    1345                
    1346                 done = (ret == make_link(0, N_NORMAL));
     1434                marked_ptr_t ret =
     1435                        cas_link(wnd.ppred, &sentinel, N_NORMAL, join_node, N_NORMAL);
     1436               
     1437                done = (ret == make_link(&sentinel, N_NORMAL));
    13471438        } while (!done);
    13481439}
     
    13501441static void free_later(cht_t *h, cht_link_t *item)
    13511442{
     1443        ASSERT(item != &sentinel);
     1444       
    13521445        /*
    13531446         * remove_callback only works as rcu_func_t because rcu_link is the first
     
    15771670                        ASSERT(N_INVALID == get_mark(h->b->head[old_idx]));
    15781671                       
    1579                         if (0 != get_next(h->b->head[old_idx]))
    1580                                 h->b->head[old_idx] = make_link(0, N_INVALID);
     1672                        if (&sentinel != get_next(h->b->head[old_idx]))
     1673                                h->b->head[old_idx] = make_link(&sentinel, N_INVALID);
    15811674                }
    15821675        }
     
    16131706        cht_link_t *cur = get_next(*new_head);
    16141707               
    1615         while (cur) {
     1708        while (cur != &sentinel) {
    16161709                /* Clear the join node's JN mark - even if it is marked as deleted. */
    16171710                if (N_JOIN & get_mark(cur->link)) {
     
    16291722        marked_ptr_t *new_head)
    16301723{
     1724        ASSERT(join_node != &sentinel);
    16311725        ASSERT(join_node && (N_JOIN & get_mark(join_node->link)));
    16321726       
     
    17001794                if (N_DELETED & get_mark(*cur_link)) {
    17011795                        ASSERT(cur_link != new_head);
    1702                         ASSERT(wnd.ppred && wnd.cur);
     1796                        ASSERT(wnd.ppred && wnd.cur && wnd.cur != &sentinel);
    17031797                        ASSERT(cur_link == &wnd.cur->link);
    17041798
     
    17161810                        if (is_jf_node) {
    17171811                                cht_link_t *next = get_next(*cur_link);
    1718                                 marked_ptr_t ret
    1719                                         = cas_link(cur_link, next, N_JOIN_FOLLOWS, 0, N_NORMAL);
     1812                                marked_ptr_t ret =
     1813                                        cas_link(cur_link, next, N_JOIN_FOLLOWS, &sentinel, N_NORMAL);
    17201814                               
    1721                                 ASSERT(!next || ((N_JOIN | N_JOIN_FOLLOWS) & get_mark(ret)));
     1815                                ASSERT(next == &sentinel
     1816                                        || ((N_JOIN | N_JOIN_FOLLOWS) & get_mark(ret)));
    17221817
    17231818                                /* Successfully cleared the JF mark of a non-deleted node. */
     
    17391834
    17401835                /* We must encounter a JF node before we reach the end of the bucket. */
    1741                 ASSERT(wnd.cur);
     1836                ASSERT(wnd.cur && wnd.cur != &sentinel);
    17421837                cur_link = &wnd.cur->link;
    17431838        }
     
    17741869}
    17751870
    1776 
    1777 static inline size_t key_hash(cht_t *h, void *key)
    1778 {
    1779         return hash_mix(h->op->key_hash(key));
     1871static inline size_t calc_key_hash(cht_t *h, void *key)
     1872{
     1873        /* Mimick calc_node_hash. */
     1874        return hash_mix(h->op->key_hash(key)) & ~1U;
    17801875}
    17811876
    17821877static inline size_t node_hash(cht_t *h, const cht_link_t *item)
    17831878{
    1784         return hash_mix(h->op->hash(item));
    1785 }
    1786 
     1879        ASSERT(item->hash == h->invalid_hash
     1880                || item->hash == sentinel.hash
     1881                || item->hash == calc_node_hash(h, item));
     1882       
     1883        return item->hash;
     1884}
     1885
     1886static inline size_t calc_node_hash(cht_t *h, const cht_link_t *item)
     1887{
     1888        ASSERT(item != &sentinel);
     1889        /*
     1890         * Clear the lowest order bit in order for sentinel's node hash
     1891         * to be the greatest possible.
     1892         */
     1893        return hash_mix(h->op->hash(item)) & ~1U;
     1894}
     1895
     1896static inline void memoize_node_hash(cht_t *h, cht_link_t *item)
     1897{
     1898        item->hash = calc_node_hash(h, item);
     1899}
    17871900
    17881901static inline marked_ptr_t make_link(const cht_link_t *next, mark_t mark)
     
    18361949        marked_ptr_t new)
    18371950{
     1951        ASSERT(link != &sentinel.link);
    18381952        /*
    18391953         * cas(x) on the same location x on one cpu must be ordered, but do not
  • kernel/test/cht/cht1.c

    r26d8df3 r6eaed07  
    124124        set_val(v[4], 2, key[4]);
    125125        set_val(v[5], 3, key[5]);
    126                
    127        
     126                       
    128127        if (!cht_insert_unique(h, &v[0]->link))
    129128                return "Duplicates in empty";
     
    156155                return "Found nonexisting duplicate 5";
    157156       
    158        
    159157        item = cht_find(h, (void*)v[3]->unique_id);
    160158        if (!item || item != &v[3]->link)
     
    164162        if (item)
    165163                return "Found nonexisting duplicate 3, same hash as others.";
    166        
    167164       
    168165        item = cht_find(h, (void*)v[0]->unique_id);
     
    220217                return "Removed incorrect key";
    221218       
    222         for (size_t k = 0; k < sizeof(v)/sizeof(v[0]); ++k) {
     219        for (size_t k = 0; k < sizeof(v) / sizeof(v[0]); ++k) {
    223220                cht_remove_key(h, (void*)key[k]);
    224221        }
    225222       
    226         for (size_t k = 0; k < sizeof(v)/sizeof(v[0]); ++k) {
     223        for (size_t k = 0; k < sizeof(v) / sizeof(v[0]); ++k) {
    227224                if (cht_find(h, (void*)key[k]))
    228225                        return "Found a key in a cleared table";
     
    395392                                }
    396393                                work->elem[elem_idx].inserted = false;
    397                         } else if (work->elem[elem_idx].deleted){
     394                        } else if (work->elem[elem_idx].deleted) {
    398395                                work->elem[elem_idx].deleted = false;
    399396                               
     
    555552        if (err)
    556553                return err;
     554        printf("Basic sanity test: ok.\n");
    557555       
    558556        if (!do_stress())
Note: See TracChangeset for help on using the changeset viewer.