On Tue, May 20, 2014 at 12:40:20PM -0700, Jarno Rajahalme wrote:
>
> On May 20, 2014, at 10:08 AM, Ben Pfaff <b...@nicira.com> wrote:
>
> > 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:
> >>>> +static bool
> >>>> +cmap_insert_dup(struct cmap_node *new_node, uint32_t hash,
> >>>> + struct cmap_bucket *b)
> >>>> +{
> >>>> + int i;
> >>>> +
> >>>> + for (i = 0; i < CMAP_K; i++) {
> >>>> + struct cmap_node *node = b->nodes[i];
> >>>> + if (b->hashes[i] == hash && node) {
> >>>> + for (;;) {
> >>>> + struct cmap_node *next = cmap_node_next_protected(node);
> >>>> + if (!next) {
> >>>> + ovsrcu_set(&node->next, new_node);
> >>>> + return true;
> >>>> + }
> >>>> + node = next;
> >>>> + }
> >>>
> >>> It would be faster to add the dup to the beginning of the list instead:
> >>>
> >>> for (i = 0; i < CMAP_K; i++) {
> >>> if (b->hashes[i] == hash) {
> >>> ovsrcu_set(&new_node->next, b->nodes[i]);
> >>> b->nodes[i] = new_node;
> >>> return true;
> >>> }
> >>> }
> >>>
> >>> Syncing via the counter should be unnecessary, as the hash value was
> >>> already set.
> >>
> >> That's a good point about the counter. That's the reason that I
> >> switched to this method in v2.
> >
> > OK, here's an incremental I'm folding in. What do you think?
> >
> > diff --git a/lib/cmap.c b/lib/cmap.c
> > index a1367bc..30a6e2d 100644
> > --- a/lib/cmap.c
> > +++ b/lib/cmap.c
> > @@ -392,7 +392,7 @@ cmap_set_bucket(struct cmap_bucket *b, int i,
> >
> > /* Searches 'b' for a node with the given 'hash'. If it finds one, adds
> > * 'new_node' to the node's linked list and returns true. If it does not
> > find
> > - * one, returns false. */
> > + * one, returns false. */
> > static bool
> > cmap_insert_dup(struct cmap_node *new_node, uint32_t hash,
> > struct cmap_bucket *b)
> > @@ -402,14 +402,30 @@ cmap_insert_dup(struct cmap_node *new_node, uint32_t
> > hash,
> > for (i = 0; i < CMAP_K; i++) {
> > struct cmap_node *node = b->nodes[i];
> > if (b->hashes[i] == hash && node) {
> > + struct cmap_node *p;
> > +
> > + /* The common case is that 'new_node' is a singleton, with a
> > null
> > + * 'next' pointer, but rehashing can add a longer chain. Find
> > the
> > + * end of the chain starting at 'new_node', then splice 'node'
> > to
> > + * the end of that chain. */
>
> I think this could be done regardless of the value of the
> ?node?. ?node? could be NULL, if a preceding remove just NULLed the
> node pointer but left the hash intact. I.e. it seems to me that when
> a node is removed, there is no reason to remove the hash value from
> the bucket, meaning that syncing via the counter would not be
> necessary when removing nodes from cmap.
I believe that the incremental that I posted does what you are describing.
It does not call cmap_set_bucket() or set ->hashes[].
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
