On 18.11.2019 17:24, Ola Liljedahl wrote:
> 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?
Giving a second look at cmap implementation it seems that cmap_set_bucket()
could only initialize a new slot or move the entire list from one slot to
another duplicating it. List operations are done manually without blocking
the slot. It's OK, because list itself is RCU protected. However, I'm still
not sure that all the cases will be correctly handled. Need to look closer.
>
>>
>> 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.
>>
>>
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
