On Mon, 2019-11-18 at 17:06 +0100, Ilya Maximets wrote:
> On 18.11.2019 16:55, Ola Liljedahl wrote:
>
> On Mon, 2019-11-18 at 16:45 +0100, Ilya Maximets wrote:
>
> On 18.11.2019 3:45, Yanqin Wei wrote:
>
> Currently cmap_bucket is protected by a counter. Cmap reader will be
> blocked until the counter becomes even, writer increments it by 1 to be
> odd, and after slot update, increments by 1 again to become even. If the
> writer is pending or scheduled out during the writer course, the reader
> will be blocked.
>
> This patch introduces a bitmap as guard variable for (hash,node) pair.
> Writer need set slot valid bit to 0 before each change. And after change,
> writer sets valid bit to 1 and increments counter. Thus, reader can ensure
> slot consistency by only scanning valid slot and then checking counter+bitmap
> does not change while examining the bucket.
>
> The only time a reader has to retry the read operation for single bucket
> is when
> 1)a writer clears a bit in the valid bitmap between a reader's first and
> second read of the counter+bitmap.
> 2)a writer increments the counter between a reader's first and second
> read of counter+bitmap.
> I.e. the read operation needs to be retried when some other thread has
> made progress (with a write).
> There is no spinning/waiting for other threads to complete. This makes
> the design non-blocking (for readers).
>
> And it has almost no additional overhead because counter and bitmap
> share one 32 bits variable. No additional load/store for reader and
> writer.
>
>
> IIUC, after this change if writer will start inserting the node, reader
> will not find any node with the same hash in cmap because it will check
> only "valid" slots. This breaks the cmap API and could lead to crash.
> Why wouldn't readers find other valid slots with the same hash value?
> It is only the slot that is being updated that is cleared in the valid bitmap
> duing the update. Other valid slots (irrespective of actual hash values) are
> unchanged.
>
> Am I missing something? Do the users of cmap have some other expectations that
> are not obvious from looking at the cmap code?
>
> bucket->nodes[i] is not a single node, but the list of nodes with the same
> hash
> equal to bucket->hashes[i].
Thanks. I missed this.
ovsrcu_set(&b->nodes[i].next, node); /* Also atomic. */
To maintain the correctness of the list, node->next must already have been
written with the old value of b->nodes[i].next? Which means part of the
implementation is actually outside of cmap_set_bucket(). That makes it difficult
to change the design, need to modify all callers of cmap_set_bucket() if we want
to do e.g. an atomic enqueue to the list.
cmap_set_bucket() also writes bucket->hashes[i] so this could actually change
the hash value for existing entries in the nodes[i] list?
>
> You may look at the implementation of
> CMAP_NODE_FOR_EACH/CMAP_FOR_EACH_WITH_HASH
> and read comments to 'struct cmap_node' and cmap.{c,h} in general.
>
> While adding the new node to the list you're restricting access to
> the whole list making it impossible to find any node there.
I understand that now.
>
> Best regards, Ilya Maximets.
>
>
--
Ola Liljedahl, System Architect, Arm
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
