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].
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.
Best regards, Ilya Maximets.
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
