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