Captive-free algorithms: model “do it, write it down (charge it to another)”

Следуя совету хабрапублики, пробую новый вариант перевода термина "lock-free"

В прошлый раз мы видели «беззахватный по духу» алгоритм, где захват был реализован так, что поток, обращающийся к захваченным данным, не ждёт их освобождения, а отправляется «обходным путём» (вычисляет требуемый результат, не пользуясь услугами кэша). В своём следующем посте Реймонд объясняет, как данный алгоритм можно усовершенствовать на случай, когда «обходного пути» нет. Алгоритм, однако, остаётся беззахватным: каждый поток продолжает работать, не дожидаясь освобождения захваченных данных.

In the shared variable, two service bits are now needed: in addition to the capture flag, as in the previous example, the “commission new job” flag; and if the work entrusted is complicated, then in addition to the flag, it will also be necessary to store its parameters somewhere else. For example, in a general variable, you can store a pointer to an (aligned in memory) object with parameters, and in the free least significant bits of the pointer - two named flags.

Before performing an action on an object, first of all, we capture it, atomically setting the corresponding flag. If it turns out that the object has already been captured, we will entrust the execution of our action to the captured stream by setting the second flag.

If the object was able to be captured, then after completing work with it, remove the capture flag and at the same time check whether we were entrusted with a new job. (That is, were there any calls to the object during the time that we kept it captured.) If there is work, then we will do it too; and so on, until once upon unlocking the object there is no delayed work. We are not entitled to leave the object in a state of "not captured, but there is work."

The resulting “do, write, (assign to another)” model is woven from many cycles in case of all kinds of failures. Each atomic operation consists in a cycle; execution of deferred work is carried out in a cycle; and every time a callInterlockedCompareExchangereveals overwriting of used data, you need to roll back all the work done, and perform it from the beginning. The model comes out very confusing. Raymond describes it like this: “In the whole world, perhaps only five will be able to implement it correctly, and I do not belong to these five.” Nevertheless, as an illustration, he gives an example of an object called GroupWait, which supports two operations:

• AddWait: Add a new event handle to the list.
• SignalAll: Set all events in the list, automatically deleting each event at the same time as it is set. In order for the event to be set the next time SignalAll is called, it must be added to the list again.

The object is implemented simply as a list of handles. It is clear that it could have been implemented without a tricky, non-capturing model: for example, using atomic functions over lists implemented since Windows XP. The task was chosen only to accompany the verbal description with an example code. Do not take GroupWait as a model for implementing a thread-safe list.

So, we use the lower two bits of the pointer to store two flags: a capture flag, indicating that a certain thread is performing an operation on the list; and a work flag indicating that the user requested the installation of events while the list was being captured.

// WARNING! IF YOU USE THIS CODE YOU ARE AN IDIOT - READ THE TEXT ABOVE
struct NODE;
NODE * Node (LONG_PTR key) {return reinterpret_cast(key); }
enum {
 Locked = 1,
 Signaled = 2,
};
struct NODE {
 NODE * pnNext;
 HANDLE hEvent;
 LONG_PTR Key () {return reinterpret_cast(this); }
 NODE * Ptr () {return Node (Key () & ~ (Locked | Signaled)); }
};
#define NODE_INVALID Node (-1)
class GroupWait {
public:
 GroupWait (): m_pnRoot (NULL) {}
 ~ GroupWait ();
 BOOL AddWait (HANDLE hEvent);
 void SignalAll ();
private:
 NODE * m_pnRoot;
};

Since we combine a pointer to a list item and a pair of flags in one value, for convenience it’s worth identifying methods that convert the types used to each other: Nodereturns a pointer, Keyis a numerical value, and Ptris a usable pointer (without flags in the low-order bits).

We will depict our values ​​as bit fields of the form p|S|L: p - pointer to the next element of the list; S - flag of work; and L is the capture flag. The set flag S means that you need to process all the elements of the list, starting with the following - imagine it marked not inside the element, but on the outgoing arrow.

For instance:

   m_pnRoot
  + -------- + - + - +
  | * | 0 | 1 |
  + --- | ---- + - + - +
      |
      v
  + -------- + - + - + --------- +
A | * | 1 |? | hEvent1 |
  + --- | ---- + - + - + --------- +
      |
      v
  + -------- + - + - + --------- +
B | * |? |? | hEvent2 |
  + --- | ---- + - + - + --------- +
      |
      v
  + -------- + - + - + --------- +
C | NULL |? |? | hEvent3 |
  + -------- + - + - + --------- +

A GroupWait object containing three handles is shown. The reset flag S at the head of the list means that no one required to set the hEvent1 event. On the contrary, the flag S set in element A means that you need to go around all the elements after A and set the corresponding events - namely, hEvent2 and hEvent3. In particular, the value of the flag S in elements B and C does not matter; these elements will be processed anyway because the S flag in element A requires it. Thus, the value of the S flag in the last element of the list never matters at all.

The L flag is used only at the head of the list; in all other elements it does not matter.

So the preparations are complete; add a new handle to the list.

BOOL GroupWait :: AddWait (HANDLE hEvent)
{
 NODE * pnInsert = new (nothrow) NODE;
 if (pnInsert == NULL) return FALSE;
 pnInsert-> hEvent = hEvent;
 NODE * pn;
 NODE * pnNew;
 do {
  pn = InterlockedReadAcquire (& m_pnRoot, NODE_INVALID);
  pnInsert-> pnNext = pn;
  pnNew = Node (pnInsert-> Key () | (pn-> Key () & Locked));
 } while (InterlockedCompareExchangeRelease (& m_pnRoot, pnNew, pn)! = pn);
 return TRUE;
}

We add a new element to the top of the list, and make sure that the L flag changes from the old element to the new one: otherwise it may turn out that another thread has already captured the list, and we inadvertently “released” it. The S flag in the item being added is cleared: no one has yet demanded to set a new event. We add an element to the head of the list according to the familiar model “do, write, (try again)” - checking that no one has changed the list behind us. Please note that the “ABA problem” does not occur: even if the unchanged value m_pnRootpoints to another object, we still use only the pointer itself, and not the contents of the object.

The simplicity of the AddWait method is unusual for the “do, write, (assign to another)” model: in case of failure, we have nothing to delegate - all the work consists of one write to memory. The rest of the methods will be paid for this simplicity, in which you will have to provide for the processing of elements added to the list while it was captured.

The SignalAll method is so complex that it is better to read it in parts.

void GroupWait :: SignalAll ()
{
 NODE * pnCapture;
 NODE * pnNew;
 do {
  pnCapture = InterlockedReadAcquire (& m_pnRoot, NODE_INVALID);
  if (pnCapture-> Key () & Locked) {
   pnNew = Node (pnCapture-> Key () | Signaled);
  } else {
   pnNew = Node (Locked);
  }
 } while (InterlockedCompareExchangeAcquire (& m_pnRoot,
                              pnNew, pnCapture)! = pnCapture);
 if (pnCapture-> Key () & Locked) return;
 ...

If the list is captured, then the only thing that is required of us is to set the flag S in his head. If the list is free, we will try to capture it and at the same time “steal” all the elements of the list by writing a “stub” instead of the head NULL|0|1. In both cases, the list head is rewritten using the “do, write, (try again)” model - we repeat the attempts until the recording succeeds.

By setting the S flag, we delegated our work to the thread that captured the list. The set flag S in the head of the list means that you need to process all the items following the head of the list - i.e. generally all elements of the list; just what we need. The thread that has captured the list will check the flag when the list is released, and will do the work for us.

If the list was not captured, then by our action we captured it. "Stolen" elements are not visible to other threads, so the simultaneous call of SignalAll from different threads will not lead to multiple events.

 ...
 NODE * pnNext;
 NODE * pn;
 for (pn = pnCapture-> Ptr (); pn; pn = pnNext) {
  SetEvent (pn-> hEvent);
  pnNext = pn-> pnNext-> Ptr ();
  delete pn;
 }
 ...

Bypassing the "stolen" list is implemented in a very straightforward manner, without any concern for thread-safety; just take element by element, set the event, and delete the element. The only feature is a call Ptrto remove flags from the pointer to the next element.

Now the list needs to be unlocked. To start:

 ...
 pnCapture = pnNew;
 ...

At the beginning of the method, we wrote pnNewin m_pnRoot, and if this value was saved in the head of the list, it means that we got off easily: no one accessed the list while we worked with it.

 ...
 for (;;) {
  pnNew = Node (pnCapture-> Key () & ~ Locked);
  if (InterlockedCompareExchangeRelease (& m_pnRoot,
                      pnNew, pnCapture) == pnCapture) {
   return
  }
 ...

First, check if the list has changed: if not, just unblock it and you're done. Otherwise, we begin a new cycle: you need to perform all the pending work that has accumulated while the list was captured.

 ...
  pnCapture = InterlockedReadAcquire (& m_pnRoot, NODE_INVALID);
  NODE * pnNew = Node (pnCapture-> Key () & ~ (Locked | Signaled));
  NODE ** ppn = & pnNew;
  NODE * pn;
  NODE * pnNext;
  BOOL fSignalSeen = FALSE;
  for (pn = pnNew; pn-> Ptr (); pn = pnNext) {
   pnNext = pn-> Ptr () -> pnNext;
   if (fSignalSeen) {
    SetEvent (pn-> Ptr () -> hEvent);
    delete pn-> Ptr ();
   } else if (pn-> Key () & Signaled) {
    fSignalSeen = TRUE;
    (* ppn) = Node (Locked); // steal, leaving captured
    SetEvent (pn-> Ptr () -> hEvent);
    delete pn-> Ptr ();
   } else {
    ppn = & pn-> Ptr () -> pnNext;
   }
  }
 } // try to unlock again
} // end of function

To do the pending work, we go around the list until we find the set bit S. In the first element, in which the bit S is set, we reset the outgoing pointer to “steal” the rest of the list; then, bypassing this remainder, we set each event, and delete the item. As before, we “steal” the list so that the simultaneous call from several threads does not lead to the multiple installation of the event. In the end, when the work is done, we again try to unblock the list - in the expectation that one day there will be no new work, and we can rightfully exit the function.

---

As you can see, the main idea of ​​the “do it, write it down (entrust it to another)” model is quite simple, but from its implementation, taking into account all the subtleties, the head may hurt. It’s best to leave the implementation of such things to system programmers who have enough time, patience and ability to cope with all this. For example, in an interview with Arun Kishan: Inside Windows 7 - Farewell to the Windows Kernel Dispatcher Lock , an architect working on a Windows kernel talks about using this particular model.