Hi Ilya, New node insertion does not always set bucket slot. It should be only two cases would trigger slot updating. 1. node is inserted into an empty slot. 2. rearrange cmap bucket in case of no candidate bucket for new node. see "cmap_insert_bfs"
1st case is an empty slot, there is no other node in the list. 2nd case, the slot movement has two step: a. copy an slot(hash,node list) into another candidate slot. b. replace the old position with another slot. So there is at least one complete slot copy in the cmap. If one slot is updating and skipped by bitmap, it will be found in anther candidate bucket. Best Regards, Wei Yanqin > -----Original Message----- > From: Ilya Maximets <[email protected]> > Sent: Tuesday, November 19, 2019 12:06 AM > To: Ola Liljedahl <[email protected]>; [email protected]; Yanqin Wei > (Arm Technology China) <[email protected]>; [email protected] > Cc: Gavin Hu (Arm Technology China) <[email protected]>; nd > <[email protected]>; [email protected] > Subject: Re: [ovs-dev] [PATCH v1 2/2] cmap: non-blocking cmap lookup > > 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 > bucket->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
