Information Technology Reference
In-Depth Information
typedefstructElementS{
intkey;
intval1;
intval2;
structElementS*next;
}Element;
classRCULL{
private:
RCULockrcuLock;
Element*head;
public:
intsearch(intkey,int*ret1,int*ret2);
voidinsert(Element*item);
voidremove(intkey);
};
Figure6.17: Declaration of data structures and API for a linkled list that uses
RCU for synchronization.
read
1
v0 or v1
overlaps publish v1
read
2
v2
after publish v2, before publish v3
read
3
v3
after publish v3
read
4
v0 or v1
overlaps publish v1
read
5
v1 or v2
overlaps publish v2
read
4
v0, v1, or v2
overlaps publish v1 and v2
read
7
v3
after publish v2
Example: RCU linked list. Suppose we have linked list of records, such as
the one defined in Figure 6.17. Here, the list comprises an RCU lock
rcuLock
and a pointer to the head of the list
head
. Each record has three data fields,
key
,
val1
, and
val2
, and a
next
pointer to the next record on the list.
Figure 6.19 shows how we implement a
search()
method that scans down
the list until an element with a matching key is found. If such an element
is found, the method returns the two value fields by setting the two result
pointers and providing a nonzero return value. Otherwise, the method returns
0 to indicate that no matching record was found. Since this method does not
modify any of the list's state, it acquires and releases the RCU lock in read
mode.
Figure 6.19 shows two methods that update the list. Each of them is
arranged so that a single pointer update is all that is needed to publish the list
update to the readers. In particular, notice that it is important that
insert()
initialize the data structure before updating the
head
pointer to make the new
element visible to readers.
Implementing RCU. In implementing RCU, the central goal is to minimize
the cost of read critical sections|the cost should be low and should be constant
