[ovs-dev] [cmap v2 1/2] cmap: New module for cuckoo hash table.

Ben Pfaff blp at nicira.com
Tue May 20 16:48:55 UTC 2014

On Tue, May 20, 2014 at 09:12:23AM -0700, Ben Pfaff wrote:
> On Fri, May 16, 2014 at 04:38:02PM -0700, Jarno Rajahalme wrote:
> > > +    if (b->nodes[slot] == node) {
> > > +        cmap_set_bucket(b, slot, cmap_node_next_protected(node), hash);
> > 
> > ?hash? is not changing here, so could just set the nodes:
> > 
> >         b->nodes[slot] = cmap_node_next_protected(node);
> > 
> > Btw, what is the rationale that the nodes pointers are not RCU
> > pointers? If they were, it would feel possible to combine this special
> > case with the loop below.
> Good points.  I'll work on that for a v3.

After thinking a little further, I am not sure that it would become
possible to combine them, because I think that the cases are a little

        * If we are removing the last node with a hash, which is usually
          the case if node == b->nodes[slot], then we want to make sure
          that from the viewpoint of any reader that this is atomic
          (that is, the change to ->hashes[] and ->nodes[]), by
          incrementing the counter around the change.  I am not
          absolutely certain that this is required, but the cost is
          minimal so, lacking confidence, I prefer to do it.

        * Otherwise, we are shortening a linked list, but not
          eliminating its slot, which does not affect readers in the
          same way, so an ordinary RCU store should suffice.

What I'm increasingly uncertain about is whether cmap_find() is correct.
The intention is that the atomic reads of the counters before and after
checking the nodes and the hashes should ensure that the cache lines
occupied by the buckets are stable.  I think that's going to be true in
practice, with current compiler technology.  But I am not sure that the
atomic_reads on the counters actually means that the node and hash reads
can't be moved outside the counter reads.  If not, though, making the
node reads atomic (via RCU) and even the hash reads atomic (by making
them atomic_uint32s) wouldn't help.  I think that the only thing that
would help would be adding explicit acquire and release barriers.  That
might actually, in conjunction with good comments, be clearer than what
we have now.

What do you think?

More information about the dev mailing list