<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br><div><div>On May 20, 2014, at 1:03 PM, Ben Pfaff <<a href="mailto:blp@nicira.com">blp@nicira.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div style="font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">On Tue, May 20, 2014 at 12:40:20PM -0700, Jarno Rajahalme wrote:<br><blockquote type="cite"><br>On May 20, 2014, at 10:08 AM, Ben Pfaff <<a href="mailto:blp@nicira.com">blp@nicira.com</a>> wrote:<br><br><blockquote type="cite">On Tue, May 20, 2014 at 09:12:23AM -0700, Ben Pfaff wrote:<br><blockquote type="cite">On Fri, May 16, 2014 at 04:38:02PM -0700, Jarno Rajahalme wrote:<br><blockquote type="cite"><blockquote type="cite">+static bool<br>+cmap_insert_dup(struct cmap_node *new_node, uint32_t hash,<br>+ struct cmap_bucket *b)<br>+{<br>+ int i;<br>+<br>+ for (i = 0; i < CMAP_K; i++) {<br>+ struct cmap_node *node = b->nodes[i];<br>+ if (b->hashes[i] == hash && node) {<br>+ for (;;) {<br>+ struct cmap_node *next = cmap_node_next_protected(node);<br>+ if (!next) {<br>+ ovsrcu_set(&node->next, new_node);<br>+ return true;<br>+ }<br>+ node = next;<br>+ }<br></blockquote><br>It would be faster to add the dup to the beginning of the list instead:<br><br> for (i = 0; i < CMAP_K; i++) {<br> if (b->hashes[i] == hash) {<br> ovsrcu_set(&new_node->next, b->nodes[i]);<br> b->nodes[i] = new_node;<br> return true;<br> }<br> }<br><br>Syncing via the counter should be unnecessary, as the hash value was<br>already set.<br></blockquote><br>That's a good point about the counter. That's the reason that I<br>switched to this method in v2.<br></blockquote><br>OK, here's an incremental I'm folding in. What do you think?<br><br>diff --git a/lib/cmap.c b/lib/cmap.c<br>index a1367bc..30a6e2d 100644<br>--- a/lib/cmap.c<br>+++ b/lib/cmap.c<br>@@ -392,7 +392,7 @@ cmap_set_bucket(struct cmap_bucket *b, int i,<br><br>/* Searches 'b' for a node with the given 'hash'. If it finds one, adds<br>* 'new_node' to the node's linked list and returns true. If it does not find<br>- * one, returns false. */<br>+ * one, returns false. */<br>static bool<br>cmap_insert_dup(struct cmap_node *new_node, uint32_t hash,<br> struct cmap_bucket *b)<br>@@ -402,14 +402,30 @@ cmap_insert_dup(struct cmap_node *new_node, uint32_t hash,<br> for (i = 0; i < CMAP_K; i++) {<br> struct cmap_node *node = b->nodes[i];<br> if (b->hashes[i] == hash && node) {<br>+ struct cmap_node *p;<br>+<br>+ /* The common case is that 'new_node' is a singleton, with a null<br>+ * 'next' pointer, but rehashing can add a longer chain. Find the<br>+ * end of the chain starting at 'new_node', then splice 'node' to<br>+ * the end of that chain. */<br></blockquote><br>I think this could be done regardless of the value of the<br>?node?. ?node? could be NULL, if a preceding remove just NULLed the<br>node pointer but left the hash intact. I.e. it seems to me that when<br>a node is removed, there is no reason to remove the hash value from<br>the bucket, meaning that syncing via the counter would not be<br>necessary when removing nodes from cmap.<br></blockquote><br>I believe that the incremental that I posted does what you are describing.<br>It does not call cmap_set_bucket() or set ->hashes[].</div></blockquote></div><br><div>There is still this before the added code lines:</div><div><br></div><div>@@ -402,14 +402,30 @@ cmap_insert_dup(struct cmap_node *new_node, uint32_t hash,<br> for (i = 0; i < CMAP_K; i++) {<br> struct cmap_node *node = b->nodes[i];<br> if (b->hashes[i] == hash && node) {</div><div><br></div><div>i.e., ‘node’ is checked to be non-NULL.</div><div><br></div><div> Jarno</div><div><br></div></body></html>