Index: kernel/generic/src/adt/cht.c
===================================================================
--- kernel/generic/src/adt/cht.c	(revision 5e5cef3b7bf7f9684a41a5a30a8d2022b309efd7)
+++ kernel/generic/src/adt/cht.c	(revision f1c7755075766af5ee998c23d3234987a8f09572)
@@ -82,4 +82,11 @@
 	cht_link_t *last;
 } wnd_t;
+
+
+/* Sentinel node used by all buckets. Stores the greatest possible hash value.*/
+static const cht_link_t sentinel = {
+	.link = 0,
+	.hash = -1
+};
 
 
@@ -140,6 +147,8 @@
 static void next_wnd(wnd_t *wnd);
 static bool same_node_pred(void *node, const cht_link_t *item2);
-static size_t key_hash(cht_t *h, void *key);
+static size_t calc_key_hash(cht_t *h, void *key);
 static size_t node_hash(cht_t *h, const cht_link_t *item);
+static size_t calc_node_hash(cht_t *h, const cht_link_t *item);
+static void memoize_node_hash(cht_t *h, cht_link_t *item);
 static size_t calc_split_hash(size_t split_idx, size_t order);
 static size_t calc_bucket_idx(size_t hash, size_t order);
@@ -159,4 +168,7 @@
 	ASSERT(h);
 	ASSERT(op && op->hash && op->key_hash && op->equal && op->key_equal);
+	/* Memoized hashes are stored in the rcu_link.func function pointer. */
+	ASSERT(sizeof(size_t) == sizeof(rcu_func_t));
+	ASSERT(sentinel.hash == (uintptr_t)sentinel.rcu_link.func);
 
 	/* All operations are compulsory. */
@@ -178,4 +190,10 @@
 	atomic_set(&h->item_cnt, 0);
 	atomic_set(&h->resize_reqs, 0);
+	/* 
+	 * 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.
+	 */
+	h->invalid_hash = (uintptr_t)h->op->remove_callback;
+	
 	/* Ensure the initialization takes place before we start using the table. */
 	write_barrier();
@@ -196,6 +214,7 @@
 	b->order = order;
 	
-	marked_ptr_t head_link 
-		= set_invalid ? make_link(0, N_INVALID) : make_link(0, N_NORMAL);
+	marked_ptr_t head_link = set_invalid 
+		? make_link(&sentinel, N_INVALID) 
+		: make_link(&sentinel, N_NORMAL);
 	
 	for (size_t i = 0; i < bucket_cnt; ++i) {
@@ -253,5 +272,5 @@
 	ASSERT(rcu_read_locked());
 	
-	size_t hash = key_hash(h, key);
+	size_t hash = calc_key_hash(h, key);
 	
 	cht_buckets_t *b = rcu_access(h->b);
@@ -282,5 +301,5 @@
 	ASSERT(item);
 	
-	return find_duplicate(h, item, node_hash(h, item), get_next(item->link));
+	return find_duplicate(h, item, calc_node_hash(h, item), get_next(item->link));
 }
 
@@ -288,12 +307,26 @@
 	size_t search_hash)
 {
-	cht_link_t *cur = get_next(head);
-	
-	while (cur) {
-		/* 
-		 * It is safe to access nodes even outside of this bucket (eg when
-		 * splitting the bucket). The resizer makes sure that any node we 
-		 * may find by following the next pointers is allocated.
-		 */
+	/* 
+	 * It is safe to access nodes even outside of this bucket (eg when
+	 * splitting the bucket). The resizer makes sure that any node we 
+	 * may find by following the next pointers is allocated.
+	 */
+
+	cht_link_t *cur = 0;
+	marked_ptr_t prev = head;
+
+try_again:
+	/* Filter out items with different hashes. */
+	do {
+		cur = get_next(prev);
+		ASSERT(cur);
+		prev = cur->link;
+	} 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. 
+	 */
+	while (node_hash(h, cur) == search_hash) {
 		if (h->op->key_equal(key, cur)) {
 			if (!(N_DELETED & get_mark(cur->link)))
@@ -302,4 +335,15 @@
 		
 		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
+	 * the node and try again.
+	 */
+	if (node_hash(h, cur) == h->invalid_hash) {
+		prev = cur->link;
+		goto try_again;
 	}
 	
@@ -413,5 +457,5 @@
 		 * joining link (or the item is not in the table).
 		 */
-		if (move_src_idx != old_idx && get_next(old_head)) {
+		if (move_src_idx != old_idx && get_next(old_head) != &sentinel) {
 			/*
 			 * Note that old_head (the bucket to be merged into new_head) 
@@ -459,4 +503,5 @@
 
 	cht_buckets_t *b = rcu_access(h->b);
+	memoize_node_hash(h, item);
 	size_t hash = node_hash(h, item);
 	size_t idx = calc_bucket_idx(hash, b->order);
@@ -552,7 +597,10 @@
 	const wnd_t *wnd)
 {
-	ASSERT(0 == wnd->cur || hash <= node_hash(h, wnd->cur));
-	
-	if (0 == wnd->cur || hash < node_hash(h, wnd->cur))
+	ASSERT(wnd->cur);
+	ASSERT(wnd->cur == &sentinel || hash <= node_hash(h, wnd->cur)
+		|| node_hash(h, wnd->cur) == h->invalid_hash);
+	
+	/* hash < node_hash(h, wnd->cur) */
+	if (hash != node_hash(h, wnd->cur) && h->invalid_hash != node_hash(h, wnd->cur))
 		return false;
 
@@ -569,9 +617,14 @@
 	cht_link_t *start)
 {
-	ASSERT(0 == start || hash <= node_hash(h, start));
+	ASSERT(hash <= node_hash(h, start) || h->invalid_hash == node_hash(h, start));
 
 	cht_link_t *cur = start;
 	
-	while (cur && node_hash(h, cur) == hash) {
+try_again:	
+	ASSERT(cur);
+
+	while (node_hash(h, cur) == hash) {
+		ASSERT(cur != &sentinel);
+		
 		bool deleted = (N_DELETED & get_mark(cur->link));
 		
@@ -581,5 +634,11 @@
 		
 		cur = get_next(cur->link);
+		ASSERT(cur);
 	} 
+
+	if (h->invalid_hash == node_hash(h, cur)) {
+		cur = get_next(cur->link);
+		goto try_again;
+	}
 	
 	return 0;	
@@ -590,5 +649,5 @@
 	ASSERT(h);
 	
-	size_t hash = key_hash(h, key);
+	size_t hash = calc_key_hash(h, key);
 	size_t removed = 0;
 	
@@ -609,5 +668,5 @@
 	 * we search for it again from the beginning of the correct bucket.
 	 */
-	size_t hash = node_hash(h, item);
+	size_t hash = calc_node_hash(h, item);
 	return remove_pred(h, hash, same_node_pred, item);
 }
@@ -666,5 +725,5 @@
 			break;
 		
-		bool found = wnd.cur && pred(pred_arg, wnd.cur);
+		bool found = (wnd.cur != &sentinel && pred(pred_arg, wnd.cur));
 		
 		if (!found) {
@@ -684,5 +743,5 @@
 	bool *deleted_but_gc, bool *resizing)
 {
-	ASSERT(wnd->cur);
+	ASSERT(wnd->cur && wnd->cur != &sentinel);
 	
 	*deleted_but_gc = false;
@@ -713,5 +772,5 @@
 	bool *resizing)
 {
-	ASSERT(cur);
+	ASSERT(cur && cur != &sentinel);
 	
 	/* 
@@ -749,4 +808,5 @@
 	bool *resizing)
 {
+	ASSERT(wnd->cur != &sentinel);
 	ASSERT(wnd->cur && (N_DELETED & get_mark(wnd->cur->link)));
 	
@@ -793,5 +853,7 @@
 	equal_pred_t pred, void *pred_arg, wnd_t *wnd, bool *resizing)
 {
-	if (!wnd->cur)
+	ASSERT(wnd->cur);
+	
+	if (wnd->cur == &sentinel)
 		return true;
 	
@@ -802,7 +864,12 @@
 	 */
 	
-	size_t cur_hash = node_hash(h, wnd->cur);
+	size_t cur_hash;
+
+try_again:	
+	cur_hash = node_hash(h, wnd->cur);
 		
 	while (cur_hash <= hash) {
+		ASSERT(wnd->cur && wnd->cur != &sentinel);
+		
 		/* GC any deleted nodes on the way. */
 		if (N_DELETED & get_mark(wnd->cur->link)) {
@@ -819,9 +886,11 @@
 		}
 		
-		/* The searched for node is not in the current bucket. */
-		if (!wnd->cur)
-			return true;
-		
 		cur_hash = node_hash(h, wnd->cur);
+	}
+	
+	if (cur_hash == h->invalid_hash) {
+		next_wnd(wnd);
+		ASSERT(wnd->cur);
+		goto try_again;
 	}
 	
@@ -834,5 +903,8 @@
 	wnd_t *wnd, bool *resizing)
 {
-	while (wnd->cur && node_hash(h, wnd->cur) < hash) {
+try_again:
+	ASSERT(wnd->cur);
+
+	while (node_hash(h, wnd->cur) < hash) {
 		/* GC any deleted nodes along the way to our desired node. */
 		if (N_DELETED & get_mark(wnd->cur->link)) {
@@ -844,6 +916,13 @@
 			next_wnd(wnd);
 		}
-	}
-	
+		
+		ASSERT(wnd->cur);
+	}
+	
+	if (node_hash(h, wnd->cur) == h->invalid_hash) {
+		next_wnd(wnd);
+		goto try_again;
+	}
+
 	/* wnd->cur may be 0 or even marked N_DELETED. */
 	return true;
@@ -894,19 +973,25 @@
 	 */
 	ASSERT(h->b->order > h->new_b->order);
+	ASSERT(wnd->cur);
 	
 	/* Either we did not need the joining link or we have already followed it.*/
-	if (wnd->cur)
+	if (wnd->cur != &sentinel)
 		return true;
 	
 	/* We have reached the end of a bucket. */
 	
-	if (wnd->last) {
+	if (wnd->last != &sentinel) {
 		size_t last_seen_hash = node_hash(h, wnd->last);
+		
+		if (last_seen_hash == h->invalid_hash) {
+			last_seen_hash = calc_node_hash(h, wnd->last);
+		}
+		
 		size_t last_old_idx = calc_bucket_idx(last_seen_hash, h->b->order);
 		size_t move_src_idx = grow_idx(shrink_idx(last_old_idx));
 		
 		/* 
-		 * Last 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) 
@@ -994,6 +1079,9 @@
 			}
 			
-			/* The resizer sets pold_head to 0 when all cpus see the bucket join.*/
-			*join_finishing = (0 != get_next(*pold_head));
+			/* 
+			 * The resizer sets pold_head to &sentinel when all cpus are
+			 * guaranteed to see the bucket join.
+			 */
+			*join_finishing = (&sentinel != get_next(*pold_head));
 		}
 		
@@ -1072,6 +1160,6 @@
 	marked_ptr_t ret;
 	
-	ret = cas_link(pdest_head, 0, N_INVALID, next, N_NORMAL);
-	ASSERT(ret == make_link(0, N_INVALID) || (N_NORMAL == get_mark(ret)));
+	ret = cas_link(pdest_head, &sentinel, N_INVALID, next, N_NORMAL);
+	ASSERT(ret == make_link(&sentinel, N_INVALID) || (N_NORMAL == get_mark(ret)));
 	cas_order_barrier();
 	
@@ -1140,5 +1228,5 @@
 	
 	/* There are nodes in the dest bucket, ie the second part of the split. */
-	if (wnd.cur) {
+	if (wnd.cur != &sentinel) {
 		/* 
 		 * Mark the first node of the dest bucket as a join node so 
@@ -1155,6 +1243,7 @@
 	
 	/* Link the dest head to the second part of the split. */
-	marked_ptr_t ret = cas_link(pdest_head, 0, N_INVALID, wnd.cur, N_NORMAL);
-	ASSERT(ret == make_link(0, N_INVALID) || (N_NORMAL == get_mark(ret)));
+	marked_ptr_t ret = 
+		cas_link(pdest_head, &sentinel, N_INVALID, wnd.cur, N_NORMAL);
+	ASSERT(ret == make_link(&sentinel, N_INVALID) || (N_NORMAL == get_mark(ret)));
 	cas_order_barrier();
 	
@@ -1302,5 +1391,5 @@
 	cht_link_t *join_node = get_next(*psrc_head);
 
-	if (join_node) {
+	if (join_node != &sentinel) {
 		mark_join_node(join_node);
 		cas_order_barrier();
@@ -1335,14 +1424,16 @@
 		ASSERT(!resizing);
 		
-		if (wnd.cur) {
+		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;
 		}
 		
 		/* Reached the tail of pdest_head - link it to the join node. */
-		marked_ptr_t ret = cas_link(wnd.ppred, 0, N_NORMAL, join_node, N_NORMAL);
-		
-		done = (ret == make_link(0, N_NORMAL));
+		marked_ptr_t ret = 
+			cas_link(wnd.ppred, &sentinel, N_NORMAL, join_node, N_NORMAL);
+		
+		done = (ret == make_link(&sentinel, N_NORMAL));
 	} while (!done);
 }
@@ -1350,4 +1441,6 @@
 static void free_later(cht_t *h, cht_link_t *item)
 {
+	ASSERT(item != &sentinel);
+	
 	/* 
 	 * remove_callback only works as rcu_func_t because rcu_link is the first
@@ -1577,6 +1670,6 @@
 			ASSERT(N_INVALID == get_mark(h->b->head[old_idx]));
 			
-			if (0 != get_next(h->b->head[old_idx]))
-				h->b->head[old_idx] = make_link(0, N_INVALID);
+			if (&sentinel != get_next(h->b->head[old_idx]))
+				h->b->head[old_idx] = make_link(&sentinel, N_INVALID);
 		}
 	}
@@ -1613,5 +1706,5 @@
 	cht_link_t *cur = get_next(*new_head);
 		
-	while (cur) {
+	while (cur != &sentinel) {
 		/* Clear the join node's JN mark - even if it is marked as deleted. */
 		if (N_JOIN & get_mark(cur->link)) {
@@ -1629,4 +1722,5 @@
 	marked_ptr_t *new_head)
 {
+	ASSERT(join_node != &sentinel);
 	ASSERT(join_node && (N_JOIN & get_mark(join_node->link)));
 	
@@ -1700,5 +1794,5 @@
 		if (N_DELETED & get_mark(*cur_link)) {
 			ASSERT(cur_link != new_head);
-			ASSERT(wnd.ppred && wnd.cur);
+			ASSERT(wnd.ppred && wnd.cur && wnd.cur != &sentinel);
 			ASSERT(cur_link == &wnd.cur->link);
 
@@ -1716,8 +1810,9 @@
 			if (is_jf_node) {
 				cht_link_t *next = get_next(*cur_link);
-				marked_ptr_t ret 
-					= cas_link(cur_link, next, N_JOIN_FOLLOWS, 0, N_NORMAL);
+				marked_ptr_t ret = 
+					cas_link(cur_link, next, N_JOIN_FOLLOWS, &sentinel, N_NORMAL);
 				
-				ASSERT(!next || ((N_JOIN | N_JOIN_FOLLOWS) & get_mark(ret)));
+				ASSERT(next == &sentinel 
+					|| ((N_JOIN | N_JOIN_FOLLOWS) & get_mark(ret)));
 
 				/* Successfully cleared the JF mark of a non-deleted node. */
@@ -1739,5 +1834,5 @@
 
 		/* We must encounter a JF node before we reach the end of the bucket. */
-		ASSERT(wnd.cur);
+		ASSERT(wnd.cur && wnd.cur != &sentinel);
 		cur_link = &wnd.cur->link;
 	}
@@ -1774,15 +1869,33 @@
 }
 
-
-static inline size_t key_hash(cht_t *h, void *key)
-{
-	return hash_mix(h->op->key_hash(key));
+static inline size_t calc_key_hash(cht_t *h, void *key)
+{
+	/* Mimick calc_node_hash. */
+	return hash_mix(h->op->key_hash(key)) & ~1U;
 }
 
 static inline size_t node_hash(cht_t *h, const cht_link_t *item)
 {
-	return hash_mix(h->op->hash(item));
-}
-
+	ASSERT(item->hash == h->invalid_hash 
+		|| item->hash == sentinel.hash
+		|| item->hash == calc_node_hash(h, item));
+	
+	return item->hash;
+}
+
+static inline size_t calc_node_hash(cht_t *h, const cht_link_t *item)
+{
+	ASSERT(item != &sentinel);
+	/* 
+	 * Clear the lowest order bit in order for sentinel's node hash
+	 * to be the greatest possible.
+	 */
+	return hash_mix(h->op->hash(item)) & ~1U;
+}
+
+static inline void memoize_node_hash(cht_t *h, cht_link_t *item)
+{
+	item->hash = calc_node_hash(h, item);
+}
 
 static inline marked_ptr_t make_link(const cht_link_t *next, mark_t mark)
@@ -1836,4 +1949,5 @@
 	marked_ptr_t new)
 {
+	ASSERT(link != &sentinel.link);
 	/*
 	 * cas(x) on the same location x on one cpu must be ordered, but do not
