[ovs-dev] [PATCH v1 2/2] cmap: non-blocking cmap lookup

[Ilya Maximets]

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.

Best regards, Ilya Maximets.