Changeset 6eaed07 in mainline
- Timestamp:
- 2012-08-04T21:14:24Z (12 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- f1c7755
- Parents:
- 26d8df3
- Location:
- kernel
- Files:
-
- 3 edited
-
generic/include/adt/cht.h (modified) (2 diffs)
-
generic/src/adt/cht.c (modified) (41 diffs)
-
test/cht/cht1.c (modified) (6 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/include/adt/cht.h
r26d8df3 r6eaed07 46 46 /** Concurrent hash table node link. */ 47 47 typedef 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 }; 50 57 /** Link to the next item in the bucket including any marks. */ 51 58 cht_ptr_t link; … … 71 78 cht_ops_t *op; 72 79 73 size_t min_order;74 80 cht_buckets_t *b; 75 81 cht_buckets_t *new_b; 82 size_t invalid_hash; 76 83 84 size_t min_order; 77 85 size_t max_load; 78 86 work_t resize_work; -
kernel/generic/src/adt/cht.c
r26d8df3 r6eaed07 82 82 cht_link_t *last; 83 83 } wnd_t; 84 85 86 /* Sentinel node used by all buckets. Stores the greatest possible hash value.*/ 87 static const cht_link_t sentinel = { 88 .link = 0, 89 .hash = -1 90 }; 84 91 85 92 … … 140 147 static void next_wnd(wnd_t *wnd); 141 148 static bool same_node_pred(void *node, const cht_link_t *item2); 142 static size_t key_hash(cht_t *h, void *key);149 static size_t calc_key_hash(cht_t *h, void *key); 143 150 static size_t node_hash(cht_t *h, const cht_link_t *item); 151 static size_t calc_node_hash(cht_t *h, const cht_link_t *item); 152 static void memoize_node_hash(cht_t *h, cht_link_t *item); 144 153 static size_t calc_split_hash(size_t split_idx, size_t order); 145 154 static size_t calc_bucket_idx(size_t hash, size_t order); … … 159 168 ASSERT(h); 160 169 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); 161 173 162 174 /* All operations are compulsory. */ … … 178 190 atomic_set(&h->item_cnt, 0); 179 191 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 180 198 /* Ensure the initialization takes place before we start using the table. */ 181 199 write_barrier(); … … 196 214 b->order = order; 197 215 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); 200 219 201 220 for (size_t i = 0; i < bucket_cnt; ++i) { … … 253 272 ASSERT(rcu_read_locked()); 254 273 255 size_t hash = key_hash(h, key);274 size_t hash = calc_key_hash(h, key); 256 275 257 276 cht_buckets_t *b = rcu_access(h->b); … … 282 301 ASSERT(item); 283 302 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)); 285 304 } 286 305 … … 288 307 size_t search_hash) 289 308 { 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 318 try_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) { 298 331 if (h->op->key_equal(key, cur)) { 299 332 if (!(N_DELETED & get_mark(cur->link))) … … 302 335 303 336 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; 304 348 } 305 349 … … 413 457 * joining link (or the item is not in the table). 414 458 */ 415 if (move_src_idx != old_idx && get_next(old_head) ) {459 if (move_src_idx != old_idx && get_next(old_head) != &sentinel) { 416 460 /* 417 461 * Note that old_head (the bucket to be merged into new_head) … … 459 503 460 504 cht_buckets_t *b = rcu_access(h->b); 505 memoize_node_hash(h, item); 461 506 size_t hash = node_hash(h, item); 462 507 size_t idx = calc_bucket_idx(hash, b->order); … … 552 597 const wnd_t *wnd) 553 598 { 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)) 557 605 return false; 558 606 … … 569 617 cht_link_t *start) 570 618 { 571 ASSERT( 0 == start || hash <= node_hash(h, start));619 ASSERT(hash <= node_hash(h, start) || h->invalid_hash == node_hash(h, start)); 572 620 573 621 cht_link_t *cur = start; 574 622 575 while (cur && node_hash(h, cur) == hash) { 623 try_again: 624 ASSERT(cur); 625 626 while (node_hash(h, cur) == hash) { 627 ASSERT(cur != &sentinel); 628 576 629 bool deleted = (N_DELETED & get_mark(cur->link)); 577 630 … … 581 634 582 635 cur = get_next(cur->link); 636 ASSERT(cur); 583 637 } 638 639 if (h->invalid_hash == node_hash(h, cur)) { 640 cur = get_next(cur->link); 641 goto try_again; 642 } 584 643 585 644 return 0; … … 590 649 ASSERT(h); 591 650 592 size_t hash = key_hash(h, key);651 size_t hash = calc_key_hash(h, key); 593 652 size_t removed = 0; 594 653 … … 609 668 * we search for it again from the beginning of the correct bucket. 610 669 */ 611 size_t hash = node_hash(h, item);670 size_t hash = calc_node_hash(h, item); 612 671 return remove_pred(h, hash, same_node_pred, item); 613 672 } … … 666 725 break; 667 726 668 bool found = wnd.cur && pred(pred_arg, wnd.cur);727 bool found = (wnd.cur != &sentinel && pred(pred_arg, wnd.cur)); 669 728 670 729 if (!found) { … … 684 743 bool *deleted_but_gc, bool *resizing) 685 744 { 686 ASSERT(wnd->cur );745 ASSERT(wnd->cur && wnd->cur != &sentinel); 687 746 688 747 *deleted_but_gc = false; … … 713 772 bool *resizing) 714 773 { 715 ASSERT(cur );774 ASSERT(cur && cur != &sentinel); 716 775 717 776 /* … … 749 808 bool *resizing) 750 809 { 810 ASSERT(wnd->cur != &sentinel); 751 811 ASSERT(wnd->cur && (N_DELETED & get_mark(wnd->cur->link))); 752 812 … … 793 853 equal_pred_t pred, void *pred_arg, wnd_t *wnd, bool *resizing) 794 854 { 795 if (!wnd->cur) 855 ASSERT(wnd->cur); 856 857 if (wnd->cur == &sentinel) 796 858 return true; 797 859 … … 802 864 */ 803 865 804 size_t cur_hash = node_hash(h, wnd->cur); 866 size_t cur_hash; 867 868 try_again: 869 cur_hash = node_hash(h, wnd->cur); 805 870 806 871 while (cur_hash <= hash) { 872 ASSERT(wnd->cur && wnd->cur != &sentinel); 873 807 874 /* GC any deleted nodes on the way. */ 808 875 if (N_DELETED & get_mark(wnd->cur->link)) { … … 819 886 } 820 887 821 /* The searched for node is not in the current bucket. */822 if (!wnd->cur)823 return true;824 825 888 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; 826 895 } 827 896 … … 834 903 wnd_t *wnd, bool *resizing) 835 904 { 836 while (wnd->cur && node_hash(h, wnd->cur) < hash) { 905 try_again: 906 ASSERT(wnd->cur); 907 908 while (node_hash(h, wnd->cur) < hash) { 837 909 /* GC any deleted nodes along the way to our desired node. */ 838 910 if (N_DELETED & get_mark(wnd->cur->link)) { … … 844 916 next_wnd(wnd); 845 917 } 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 848 927 /* wnd->cur may be 0 or even marked N_DELETED. */ 849 928 return true; … … 894 973 */ 895 974 ASSERT(h->b->order > h->new_b->order); 975 ASSERT(wnd->cur); 896 976 897 977 /* Either we did not need the joining link or we have already followed it.*/ 898 if (wnd->cur )978 if (wnd->cur != &sentinel) 899 979 return true; 900 980 901 981 /* We have reached the end of a bucket. */ 902 982 903 if (wnd->last ) {983 if (wnd->last != &sentinel) { 904 984 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 905 990 size_t last_old_idx = calc_bucket_idx(last_seen_hash, h->b->order); 906 991 size_t move_src_idx = grow_idx(shrink_idx(last_old_idx)); 907 992 908 993 /* 909 * Last was in the joining bucket - if the searched for node is there910 * 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. 911 996 */ 912 997 if (move_src_idx != last_old_idx) … … 994 1079 } 995 1080 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)); 998 1086 } 999 1087 … … 1072 1160 marked_ptr_t ret; 1073 1161 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))); 1076 1164 cas_order_barrier(); 1077 1165 … … 1140 1228 1141 1229 /* There are nodes in the dest bucket, ie the second part of the split. */ 1142 if (wnd.cur ) {1230 if (wnd.cur != &sentinel) { 1143 1231 /* 1144 1232 * Mark the first node of the dest bucket as a join node so … … 1155 1243 1156 1244 /* 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))); 1159 1248 cas_order_barrier(); 1160 1249 … … 1302 1391 cht_link_t *join_node = get_next(*psrc_head); 1303 1392 1304 if (join_node ) {1393 if (join_node != &sentinel) { 1305 1394 mark_join_node(join_node); 1306 1395 cas_order_barrier(); … … 1335 1424 ASSERT(!resizing); 1336 1425 1337 if (wnd.cur ) {1426 if (wnd.cur != &sentinel) { 1338 1427 /* 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)); 1340 1430 return; 1341 1431 } 1342 1432 1343 1433 /* 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)); 1347 1438 } while (!done); 1348 1439 } … … 1350 1441 static void free_later(cht_t *h, cht_link_t *item) 1351 1442 { 1443 ASSERT(item != &sentinel); 1444 1352 1445 /* 1353 1446 * remove_callback only works as rcu_func_t because rcu_link is the first … … 1577 1670 ASSERT(N_INVALID == get_mark(h->b->head[old_idx])); 1578 1671 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); 1581 1674 } 1582 1675 } … … 1613 1706 cht_link_t *cur = get_next(*new_head); 1614 1707 1615 while (cur ) {1708 while (cur != &sentinel) { 1616 1709 /* Clear the join node's JN mark - even if it is marked as deleted. */ 1617 1710 if (N_JOIN & get_mark(cur->link)) { … … 1629 1722 marked_ptr_t *new_head) 1630 1723 { 1724 ASSERT(join_node != &sentinel); 1631 1725 ASSERT(join_node && (N_JOIN & get_mark(join_node->link))); 1632 1726 … … 1700 1794 if (N_DELETED & get_mark(*cur_link)) { 1701 1795 ASSERT(cur_link != new_head); 1702 ASSERT(wnd.ppred && wnd.cur );1796 ASSERT(wnd.ppred && wnd.cur && wnd.cur != &sentinel); 1703 1797 ASSERT(cur_link == &wnd.cur->link); 1704 1798 … … 1716 1810 if (is_jf_node) { 1717 1811 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); 1720 1814 1721 ASSERT(!next || ((N_JOIN | N_JOIN_FOLLOWS) & get_mark(ret))); 1815 ASSERT(next == &sentinel 1816 || ((N_JOIN | N_JOIN_FOLLOWS) & get_mark(ret))); 1722 1817 1723 1818 /* Successfully cleared the JF mark of a non-deleted node. */ … … 1739 1834 1740 1835 /* 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); 1742 1837 cur_link = &wnd.cur->link; 1743 1838 } … … 1774 1869 } 1775 1870 1776 1777 static inline size_t key_hash(cht_t *h, void *key) 1778 { 1779 return hash_mix(h->op->key_hash(key)) ;1871 static 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; 1780 1875 } 1781 1876 1782 1877 static inline size_t node_hash(cht_t *h, const cht_link_t *item) 1783 1878 { 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 1886 static 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 1896 static inline void memoize_node_hash(cht_t *h, cht_link_t *item) 1897 { 1898 item->hash = calc_node_hash(h, item); 1899 } 1787 1900 1788 1901 static inline marked_ptr_t make_link(const cht_link_t *next, mark_t mark) … … 1836 1949 marked_ptr_t new) 1837 1950 { 1951 ASSERT(link != &sentinel.link); 1838 1952 /* 1839 1953 * cas(x) on the same location x on one cpu must be ordered, but do not -
kernel/test/cht/cht1.c
r26d8df3 r6eaed07 124 124 set_val(v[4], 2, key[4]); 125 125 set_val(v[5], 3, key[5]); 126 127 126 128 127 if (!cht_insert_unique(h, &v[0]->link)) 129 128 return "Duplicates in empty"; … … 156 155 return "Found nonexisting duplicate 5"; 157 156 158 159 157 item = cht_find(h, (void*)v[3]->unique_id); 160 158 if (!item || item != &v[3]->link) … … 164 162 if (item) 165 163 return "Found nonexisting duplicate 3, same hash as others."; 166 167 164 168 165 item = cht_find(h, (void*)v[0]->unique_id); … … 220 217 return "Removed incorrect key"; 221 218 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) { 223 220 cht_remove_key(h, (void*)key[k]); 224 221 } 225 222 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) { 227 224 if (cht_find(h, (void*)key[k])) 228 225 return "Found a key in a cleared table"; … … 395 392 } 396 393 work->elem[elem_idx].inserted = false; 397 } else if (work->elem[elem_idx].deleted) {394 } else if (work->elem[elem_idx].deleted) { 398 395 work->elem[elem_idx].deleted = false; 399 396 … … 555 552 if (err) 556 553 return err; 554 printf("Basic sanity test: ok.\n"); 557 555 558 556 if (!do_stress())
Note:
See TracChangeset
for help on using the changeset viewer.
