Lock-free data structures. Inside. Memory management schemes

Published on November 19, 2013

Lock-free data structures. Inside. Memory management schemes


    As I mentioned in my previous notes, the main difficulties in implementing lock-free data structures are the ABA problem and memory deletion. I share these two problems, although they are related: the fact is that there are algorithms that solve only one of them.
    In this article, I will give an overview of the methods known to me as safe memory reclamation for lock-free containers. I will demonstrate the application of this or that method on Michael-Scott's classic lock-free queue [MS98].



    Tagged pointers


    The tagged pointers scheme was proposed by IBM to solve the ABA problem. Perhaps this is the first known algorithm for solving this problem.
    According to this scheme, each pointer is an indivisible pair of the actual address of the memory cell and its tag - a 32-bit integer.
    template <typename T>
    struct tagged_ptr {
        T * ptr ;
        unsigned int tag ;
        tagged_ptr(): ptr(nullptr), tag(0) {}
        tagged_ptr( T * p ): ptr(p), tag(0) {}
        tagged_ptr( T * p, unsigned int n ): ptr(p), tag(n) {}
        T * operator->() const { return ptr; }
    };
    

    The tag acts as a version number and increments with every CAS operation on the labeled pointer and is never reset, that is, strictly increasing. When removing an item from the container, instead of physically deleting the item, the item should be placed in some free-list free list. At the same time, it is quite acceptable if the remote element located in the free-list is accessed: we have a lock-free structure, so while one thread removes the X element, the other thread can have a local copy of the labeled pointer to X and refer to the fields of the element . Therefore, a free-list must be separate for each type T, moreover, calling a data type T destructor when placing an element in a free-list is inadmissible in many cases (due to concurrent access, another thread may read data from this element during the destructor operation).
    The tagged pointer scheme has the following disadvantages:
    • The scheme is implemented on platforms on which there is a CAS atomic primitive over a double word (dwCAS). For 32-bit modern platforms, this requirement is fulfilled, since dwCAS works with 64-bit words, and all modern architectures have a full set of 64-bit instructions. But for 64-bit operation mode, a 128-bit (or at least 96-bit) dwCAS is required, which is not implemented on all architectures.
      Yes, you wrote nonsense, my friend!
      Особо искушенные в lock-free могут возразить, что для реализации tagged pointers не обязательно иметь широкий 128-битный (или 96-битный) CAS. Можно обойтись 64-битным, если учесть, что современные процессоры используют только 48 бит для адресации, старшие 16 бит адреса свободны и могут быть использованы для хранения счетчика-тега. Что ж, действительно, могут. Так сделано в boost.lockfree.
      В таком подходе есть два «но»:
      • Кто гарантирует, что в будущем эти старшие 16 бит адреса не будут задействованы? Как только наступит очередной прорыв в области чипов памяти и её объем возрастет скачком на порядок, — вендоры сразу выпустят новые процессоры с полностью 64-разрядной адресацией
      • Достаточно ли 16 бит для хранения тега? На этот счет проводились исследования, и результат этих исследований таков: 16 бит недостаточно, вполне возможно переполнение, что потенциально может привести к возникновению ABA-проблемы. А вот 32 бита – достаточно.
        Действительно, 16 бит – это значения тега 0 – 65535. В современных операционных системах квант времени, отводящийся потоку, порядка 300 – 500 тысяч ассемблерных инструкций (взято из внутренней переписки разработчиков linux), и с увеличением производительности процессоров этот квант может только расти. Получается, за один квант вполне можно выполнить 65 тысяч даже таких тяжелых операций, как CAS (ну, если невозможно сегодня, то будет возможно уже завтра). Таким образом, при 16-битовом теге мы вполне рискуем получить ABA-проблему.


    • The free-list implementation is a lock-free stack or a lock-free queue, which makes a negative contribution to performance: at least one more CAS call when an item is removed from the free-list and added to it. On the other hand, the presence of a free-list can increase productivity, since if the free-list is not empty, then you do not need to use the system, usually rather slow and synchronized memory allocation functions.
    • Having a separate free-list for each data type can be a luxury for some applications, as it can lead to inefficient use of memory. For example, if the lock-free queue on average contains 10 elements, but in the peak its size can reach 1 million, then the size of the free-list after reaching the peak will be stable about 1 million. Often this behavior is unacceptable.

    Thus, the tagged pointer scheme is an example of an algorithm that solves only the ABA problem and does not solve the problem of freeing memory.

    The libcds library does not currently use tagged pointers to implement lock-free containers. Despite its relative simplicity, this scheme can lead to uncontrolled growth in memory consumption due to the presence of a free-list for each container object. In libcds, I focused on lock-free algorithms with predictable memory consumption, without using dwCAS.
    A good example of using tagged pointers is a library boost.lockfree.

    Tagged pointers example


    Fans of sheets (if any) - pseudocode MSQueue[MS98] with tagged pointer. Yes, lock-free algorithms are very verbose!
    For simplicity, I omitted the application std:atomic.
    template <typename T> struct node {
        tagged_ptr next;
        T data;
    } ;
    template <typename T> class MSQueue {
       tagged_ptr<T> volatile m_Head;
       tagged_ptr<T> volatile m_Tail;
       FreeList m_FreeList;
    public:
       MSQueue()
       {
         // Распределяем dummy node
         // Head & Tail указывают на dummy node
         m_Head.ptr = m_Tail.ptr = new node();
       }
    };
    void enqueue( T const& value ) 
    {
    E1: node * pNode = m_FreeList.newNode();
    E2: pNode–>data = value;
    E3: pNode–>next.ptr = nullptr;
    E4: for (;;) {
    E5:   tagged_ptr<T> tail = m_Tail;
    E6:   tagged_ptr<T> next = tail.ptr–>next;
    E7:   if tail == m_Tail {
             // Tail указывает на последний элемент?
    E8:      if next.ptr == nullptr {
                // Пробуем добавить элемент в конец списка
    E9:         if CAS(&tail.ptr–>next, next, tagged_ptr<T>(node, next.tag+1)) {
                  // Успех, выходим из цикла
    E10:          break;
                }
    E11:     } else {
                // Tail не указывает на последний элемент
                // Пробуем переместить tail на последний элемент
    E12:        CAS(&m_Tail, tail, tagged_ptr<T>(next.ptr, tail.tag+1));
             }
          }
        } // end loop
        // Пробуем переместить tail на вставленный элемент
    E13: CAS(&m_Tail, tail, tagged_ptr<T>(pNode, tail.tag+1));
     }
    bool dequeue( T& dest ) {
    D1:  for (;;) {
    D2:    tagged_ptr<T> head = m_Head;
    D3:    tagged_ptr<T> tail = m_Tail;
    D4:    tagged_ptr<T> next = head–>next;
           // Head, tail и next консистентны?
    D5:    if ( head == m_Head ) {
              // Queue пуста или tail не последний?
    D6:       if ( head.ptr == tail.ptr ) {
                // Очередь пуста?
    D7:         if (next.ptr == nullptr ) {
                   // Очередь пуста
    D8: 	         return false;
                }
                // Tail не на последнем элементе
                // Пробуем продвинуть tail
    D9:         CAS(&m_Tail, tail, tagged_ptr<T>(next.ptr, tail.tag+1>)); 
    D10:      } else { // Tailна месте
                // Читаем значение перед CAS, так как иначе 
                // другой dequeue может освободить next
    D11:        dest = next.ptr–>data;
                // Пробуем продвинуть head
    D12:        if (CAS(&m_Head, head, tagged_ptr<T>(next.ptr, head.tag+1))
    D13:           break // Успех, выходим из цикла
              }
           }
         } // end of loop
         // Освобождаем старый dummy node 
    D14: m_FreeList.add(head.ptr);
    D15: return true; // результат – в dest
      }
    


    Let's take a close look at the algorithms of the enqueue and dequeue operations. Using their example, you can see several standard tricks when building lock-free structures.

    It is noteworthy that both methods contain loops - the entire substantial part of the operations is repeated until it is successful (or successful execution is impossible, for example, dequeuefrom an empty queue). Such “swotting” with the help of a loop is a typical lock-free programming technique.

    The first element in the queue (to which it points m_Head) is a dummy element (dummy node). The presence of a dummy element ensures that pointers to the beginning and end of the queue are never equal NULL. A sign of an empty queue is a condition m_Head == m_Tail && m_Tail->next == NULL(lines D6-D8). The last condition (m_Tail->next == NULL) is essential, because we do not change the process of adding to the queue m_Tail- the line E9 only changes m_Tail->next. Thus, at first glance, the method enqueueviolates the structure of the queue. Actually, the tail m_Tailchanges in another method and / or another thread: the operation enqueuebefore adding an element checks (line E8) that it m_Tailpoints to the last element (that is m_Tail->next == NULL), and if it does not, it tries to move the pointer to the end (line E12 ); likewise, an operation dequeuebefore performing its “immediate duties” changes m_Tailif it does not indicate the end of the queue (line D9). This shows us a common approach in lock-free programming - thread mutual assistance ( helping): the algorithm of one operation is “smeared” over all operations of the container and one operation relies heavily on the fact that its work will be completed by the next call to (possibly another) operation in a (possibly) different thread.

    Another fundamental observation: operations store in local variables the values ​​of pointers that they need to operate (lines E5-E6, D2-D4). Then (lines E7, D5), the values ​​just read are compared with the originals - a typical lock-free trick, unnecessary for non-competitive programming: during the time elapsed since the reading, the original values ​​may change. So that the compiler does not optimize access to the shared data of the queue (and a too “smart” compiler is able to completely delete the E7 or D5 comparison lines), m_Headand m_Tailmust be declared in C ++ 11 asatomic(in pseudo code - volatile). In addition, we recall that the CAS primitive verifies the value of the target address with the given one, and if they are equal, changes the data at the target address to a new value. Therefore, for a CAS primitive, you should always specify a local copy of the current value; the challenge CAS(&val, val, newVal)will be successful almost always, which is a mistake for us.

    Now let's see whendequeue data is copied in the method (line D11): before the item is excluded from the queue (line D12). Given that the exception of the element (promotionm_Headin line D12) may fail, data copying (D11) may be repeated. From the point of view of C ++, this means that the data stored in the queue should not be too complicated, otherwise the overhead of the assignment operator in line D11 will be too large. Accordingly, under high load conditions, the probability of failure of the CAS primitive increases. An attempt to “optimize” the algorithm by moving the D11 line out of the loop will result in an error: the element nextmay be deleted by another thread. Since the implementation of the queue in question is based on the tagged pointer scheme, in which elements are never deleted, this “optimization” will lead to the fact that we can return incorrect data (not the ones that were in the queue at the time of successful execution of the D12 line).
    Feature of M & S-queue
    Вообще, алгоритм MSQueue интересен тем, что m_Head всегда указывает на dummy node, а первым элементом непустой очереди является следующий за m_Head элемент. При dequeue из непустой очереди читается значение первого элемента, то есть m_Head.next, dummy-элемент удаляется, а новым dummy-элементом (и новой головой) становится следующий элемент, то есть тот самый, значение которого мы возвращаем. Получается, что физически удалить элемент можно только после следующей операции dequeue.
    Эта особенность может доставить много хлопот, если вы захотите использовать интрузивный вариант очереди cds::intrusive::MSQueue.



    Epoch-based reclamation


    Fraser [Fra03] proposed an epoch- based scheme . Delayed deletion is applied at a safe moment in time, when there is full confidence that none of the threads has links to the deleted element. This guarantee is provided by epochs : there is a global era nGlobalEpoch, and each stream works in its own local era nThreadEpoch. Upon entering the code protected by the epoch-based scheme, the local epoch of the flow is incremented if it does not exceed the global epoch. Once all streams have reached the global era, nGlobalEpochincremented.

    Schema Pseudo Code:
    
    // Глобальная эпоха
    static atomic<unsigned int> m_nGlobalEpoch := 1 ;
    const EPOCH_COUNT = 3 ;
    // TLS data
    struct ThreadEpoch {
        // Локальная эпоха потока
        unsigned int	m_nThreadEpoch ;
        // Список отложенных для удаления элементов
        List<void *>	m_arrRetired[ EPOCH_COUNT ] ;
        ThreadEpoch(): m_nThreadEpoch(1) {}
        void enter() {
           if ( m_nThreadEpoch <= m_nGlobalEpoch )
              m_nThreadEpoch = m_nGlobalEpoch + 1 ;
        }
        void exit() {
           if ( все потоки находятся в эпохе, следующей за m_nGlobalEpoch ) {
              ++m_nGlobalEpoch ;
              освобождаем (delete) элементы 
              m_arrRetired[ (m_nGlobalEpoch – 1) % EPOCH_COUNT ]
              всех потоков ;
           }
        }
    } ;
    

    The released elements of the lock-free container are placed in the local list of the items waiting to be deleted for the stream m_arrRetired[m_nThreadEpoch % EPOCH_COUNT]. As soon as all flows have passed through the global era m_nGlobalEpoch, all lists of all flows of the era m_nGlobalEpoch – 1can be released, and the global era itself can be incremented.
    UPD 2016
    UPD 2016: спасибо perfhunter за указание ошибки в этом псевдокоде:

    Поправьте, пожалуйста небольшую ошибку в статье «Lock-free структуры данных. Внутри. Схемы управления памятью» — в разделе «Epoch-based reclamation» в функции exit() нужно заменить m_arrRetired[ (m_nGlobalEpoch – 2) % EPOCH_COUNT ] на m_arrRetired[ (m_nGlobalEpoch – 1) % EPOCH_COUNT ]. В этот момент локальная эпоха для потоков может быть либо m_nGlobalEpoch (для тех потоков, которые уже выполнили enter(), или m_nGlobalEpoch + 1 (для потоков, вновь входящих в критическую секцию), а поколение m_nGlobalEpoch – 1 как раз можно спокойно освобождать.



    Each operation of the lock-free container is enclosed in calls ThreadEpoch::enter()and ThreadEpoch::exit(), which is very similar to the critical section:
    lock_free_op( … ) {
        get_current_thread()->ThreadEpoch.enter() ;
        . . .
        // lock-free операция контейнера. 
        // Мы находимся внутри “критической секции” epoch-based схемы,
        // так что можем быть уверены, что никто не удалит данные, с которыми
        // мы работаем.
        . . .
        get_current_thread()->ThreadEpoch.exit() ;
    }
    

    The scheme is quite simple and protects local links (that is, links within container operations) to lock-free container elements. The scheme cannot provide global links protection (from outside the container’s operations), that is, the concept of iterators over the elements of a lock-free container cannot be implemented using an epoch based scheme. The disadvantage of this scheme is that allprogram flows should go to the next era, that is, turn to some kind of lock-free container; if at least one thread does not move into the next era, the removal of pending pointers will not occur. If the priority of the streams is not the same, low-priority streams can lead to uncontrolled growth in the list of deferred ones for deleting elements of high-priority streams. Thus, an epoch-based scheme can lead (and in the event of a crash of one of the threads, it will certainly lead) to unlimited memory consumption.

    The libcds library does not have an implementation of an epoch-based scheme. Reason: I was not able to build a sufficiently effective algorithm for determining whether all flows reached the global era. Perhaps one of the readers will recommend a solution? ..


    Hazard pointer



    The scheme was proposed by Michael [Mic02a, Mic03] and is intended to protect local links to lock-free data structure elements. Perhaps it is the most famous and elaborated scheme of deferred removal. It is based only on atomic reading and writing and does not use “heavy” synchronization primitives like CAS at all.
    The cornerstone of the scheme is the obligation to declare a pointer to an element of a lock-free container as hazard (hazardous) inside the lock-free operation of a data structure, that is, before working with a pointer to an element, we must put it in an array of HPhazard pointers of the current stream. The array HPis private to the stream: only the owner stream writes to it, all streams can read (in the procedureScan) If you carefully analyze the operations of various lock-free containers, you will notice that the size of the array HP(the number of hazard pointers of one thread) does not exceed 3 - 4, so that the overhead for maintaining the circuit is small.
    Giant data structures
    Справедливости ради следует отметить, что существуют «гигантские» структуры данных, требующие свыше 64 hazard pointer’ов. В качестве примера можно привести skip-list (cds::container::SkipListMap) – вероятностную структуру данных, по сути, список списков, с переменной высотой каждого элемента. Такие контейнеры не очень подходят для схемы Hazard Pointer, хотя в libcds есть реализация skip-list для этой схемы.


    Hazard Pointers Pseudo Code [Mic02]:
    // Константы
    // P : число потоков
    // K : число hazard pointer в одном потоке
    // N : общее число hazard pointers = K*P
    // R : batch size, R-N=Ω(N), например, R=2*N
    // Per-thread переменные:
    // Массив Hazard Pouinter потока
    // Пишет в него только поток-владелец
    // читают все потоки
    void * HP[K]
    // текущий размер dlist (значения 0..R)
    unsigned dcount = 0; 
    // массив готовых к удалению данных
    void* dlist[R]; 
    // Удаление данных
    // Помещает данные в массив dlist
    void RetireNode( void * node ) { 
      dlist[dcount++] = node;
      // Если массив заполнен – вызываем основную функцию Scan
      if (dcount == R)
         Scan();
    }
    // Основная функция
    // Удаляет все элементы массива dlist, которые не объявлены 
    // как Hazard Pointer
    void Scan() { 
       unsigned i;
       unsigned p=0;
       unsigned new_dcount = 0; // 0 .. N
       void * hptr, plist[N], new_dlist[N];
       // Stage 1 – проходим по всем HP всех потоков
       // Собираем общий массив plist защищенных указателей
       for (unsigned t=0; t < P; ++t) {
          void ** pHPThread = get_thread_data(t)->HP ;
          for (i = 0; i < K; ++i) {
             hptr = pHPThread[i];
             if ( hptr != nullptr )
                plist[p++] = hptr;
          }
       }
       // Stage 2 – сортировка hazard pointer'ов
       // Сортировка нужна для последующего бинарного поиска
       sort(plist);
       // Stage 3 – удаление элементов, не объявленных как hazard
       for ( i = 0; i < R; ++i ) {
          // Если dlist[i] отсутствует в списке plist всех Hazard Pointer’ов
          // то dlist[i] может быть удален
          if ( binary_search(dlist[i], plist))
             new_dlist[new_dcount++] = dlist[i];
          else
             free(dlist[i]);
       }
       // Stage 4 – формирование нового массива отложенных элементов.
       for (i = 0; i < new_dcount; ++i ) 
          dlist[i] = new_dlist[i]; 
       dcount = new_dcount;
    }
    


    When a lock-free container RetireNode(pNode)element is deleted, the pNodestream jplaces pNodein the local (for the stream j) list of dlistdeferred (requiring removal) elements. As soon as the size of the list dlistreaches R ( R is comparable to N = P*K, but more than N ; for example, R = 2N), a procedure is called Scan()that deals with the removal of pending items. The condition R > P*Kis essential: only when this condition is met is it guaranteed that it Scan()can remove anything from the array of pending data. If this condition is violated, it Scan()may not delete anything from the array, and we will get an algorithm error - the array is completely full, but its size cannot be reduced.

    Scan() consists of four stages.
    • First, an array of plistcurrent hazard pointers is prepared , which includes all non- nullhazard pointers of all flows. Only the first stage reads the shared data - arrays of HPstreams - the remaining stages work only with local data.
    • Stage 2 sorts the array plistto optimize the subsequent search; here you can also remove plistduplicate elements.
    • Stage 3 - deletion itself: all elements of the array of the dlistcurrent stream are viewed . If an element dlist[i]is in plist(that is, some thread works with this pointer, declaring it as a hazard pointer), you cannot delete it and it remains in dlist(is transferred to new_dlist). Otherwise, the item dlist[i]may be deleted - not a single thread works with it.
    • Stage 4 copies undeleted items from new_dlistin dlist. Since R > N, the procedure Scan()will necessarily reduce the size of the array dlist, that is, some elements will be deleted.


    Declaring a pointer as a Hazard Pointer is typically done as follows:
    std::atomic<T *> atomicPtr ;
    …
    T * localPtr ;
    do {
        localPtr = atomicPtr.load(std::memory_order_relaxed);
        HP[i] = localPtr ;
    } while ( localPtr != atomicPtr.load(std::memory_order_acquire));
    

    We read the atomic pointer atomicPtrinto a local variable localPtr(which we will work with later) and into a free slot in the HP[i]array of HPhazard pointers of the current stream. After this, it should be checked that during the time we read atomicPtr, its value was not changed by another thread, for which we again read atomicPtrand compare it with the previously read value localPtr. This happens until we put in the array the HPtrue (at the time of declaration as hazard) value atomicPtr. As long as the pointer is in the Hazard Pointer array (that is, declared hazard), it cannot be physically deleted by any thread, so accessing the pointer will not lead to reading garbage or writing to an empty memory area.

    The Hazard Pointer scheme (HP scheme) is analyzed in detail from the point of view of atomic operations C ++ 11 and memory ordering in [Tor08].
    MSQueue by Hazard Pointer
    Lock-free очередь Майкла-Скотта [MS98] в исполнении Hazard Pointer. Здесь я привожу “чистый” псевдокод, без специфики libcds:
    template <typename T>
    class MSQueue {
        struct node {
            std::atomic<node *>  next ;
            T data;
            node(): next(nullptr) {}
            node( T const& v): next(nullptr), data(v) {}
        };
        std::atomic<node *> m_Head;
        std::atomic<node *> m_Tail;
    public:
        MSQueue()
        {
            node * p = new node;
            m_Head.store( p, std::memory_order_release );
            m_Tail.store( p, std::memory_order_release );
        }
        void enqueue( T const& data )
        {
           node * pNew = new node( data );
           while (true) { 
    	    node * t = m_Tail.load(std::memory_order_relaxed);
              // объявление указателя как hazard. HP – thread-private массив
     	    HP[0] = t;		
              // обязательно проверяем, что m_Tail не изменился!
    	    if (t != m_Tail.load(std::memory_order_acquire) continue;					
              node * next = t->next.load(std::memory_order_acquire);
    	    if (t != m_Tail) continue;
    	    if (next != nullptr) { 
                  // m_Tail указывает  на последний элемент
                  // продвигаем m_Tail
     	        m_Tail.compare_exchange_weak(
                    t, next, std::memory_order_release); 
    	        continue;
              } 
              node * tmp = nullptr;
              if ( t->next.compare_exchange_strong(
                   tmp, pNew, std::memory_order_release))
                  break;
           }
           m_Tail.compare_exchange_strong( t, pNew, std::memory_order_acq_rel );
           HP[0] = nullptr; // обнуляем hazard pointer
        }
        bool dequeue(T& dest) 
        { 
           while true { 
    	    node * h = m_Head.load(std::memory_order_relaxed);
              // Устанавливаем Hazard Pointer
    	    HP[0] = h;
              // Проверяем, что m_Head не изменился
     	    if (h != m_Head.load(std::memory_order_acquire)) continue;
    	    node * t = m_Tail.load(std::memory_order_relaxed);
    	    node * next = h->next.load(std::memory_order_acquire);
              // head->next также отмечаем как Hazard Pointer
    	    HP[1] = next;
              // Если m_Head изменился – начинаем все заново
    	    if (h != m_Head.load(std::memory_order_relaxed))
                continue;
              if (next == nullptr) { 
                 // Очередь пуста
    	       HP[0] = nullptr; 
    	       return false;
     	    } 
              if (h == t) { 
                // Помогаем методу enqueue – продвигаем m_Tail
    	      m_Tail.compare_exchange_strong( t, next,
                       std::memory_order_release); 
                continue;
    	    } 
              dest = next->data;
    	    if ( m_Head.compare_exchange_strong(h, next,
                           std::memory_order_release))
                 break;
           }
           // Обнуляем Hazard Pointers
           HP[0] = nullptr; 
           HP[1] = nullptr;
           // Помещаем старую голову очереди в массив
           // готовых к удалению данных.
           RetireNode(h); 
        }
    };
    



    Is the Hazard Pointer circuit universal? That is, is it applicable to all data structures? As described here, no. The reason is simple: the number of hazard pointer'ov bounded by a constant the K . For most data structures, this condition — a limited number of hazard pointers — is fulfilled, and, as noted, the number of hazard pointers is usually quite small. But there are algorithms for which it is impossible a priori to estimate the number of simultaneously required hazard pointers. An example is Harris's sorted list [Har01]. In the algorithm for deleting an element of this list, a chain of indefinite length can be deleted, which makes the HP scheme inapplicable.
    Strictly speaking, HP circuitry cangeneralize to the case of an unlimited number of hazard pointers. The author of this scheme himself gives quite detailed instructions on how to do this. But I decided in libcds to restrict myself to the classical algorithm, so as not to complicate and, as a result, not to burden the implementation of the HP-scheme. Moreover, there is another, less well-known scheme - Pass the Buck - which is quite similar to the Hazard Pointer, but where the principle of an unlimited number of hazard pointers was originally laid down. I will talk about it later.

    Hazard Pointer implementation in libcds




    This figure shows the internal structure of the hazard pointer algorithm in libcds. The core of the algorithm - Hazard Pointer Manager - is a singleton, a dynamic library libcds.dll / .so. Each stream object has a - structure Thread Manager HP , - which is actually an array of HP hazard pointer'ov size K and remote array (pending) pointers Retired size R . All HP Manager Thread structures are linked to a list. The maximum number of streams is P . By default in libcds:
    • Hazard pointer array size K = 8
    • Number of threads P = 100
    • The size of the array of pending (ready to be deleted) data R = 2 * K * P = 1600.


    In libcds, the HP schema is implemented in three levels:
    • The core is a data type-independent low-level implementation of a schema (namespace cds::gc::hzp). Since the kernel is not typed (it does not depend on the type of Tdata to be deleted), it can be moved to a dynamic library. Information about the data type is lost here, so we can’t call the data destructor (for the sake of accuracy, it should be noted that “deletion” is not always a physical deletion. For intrusive containers, for example, this is a call to a functor-disposer, in fact, an event is raised “ data can be safely deleted. ”What is behind this, what event handler, we don’t know).
    • Implementation level - a typed implementation of the scheme, located in the namespace cds::gc::hzp. This level is a set of template shell shell structures designed to preserve data typing (something similar to type erasure). This level should not be used in programs.
    • The interface level (API) is the class cds::gc::HP. This is what should be used (and is used) in lock-free containers of libcds, in fact, this is the value (one of, since there are other schemes) of the GCcontainer template parameter . From a code point of view, a class cds::gc::HPis a thin wrapper around the implementation level with its many small classes.

    Recover Lost Data Type
    Если мы в ядре «потеряли» тип данных, то как же происходит вызов деструктора, точнее, восстановление типа? Очень просто: в ядре каждая запись массива готовых к удалению (отложенных, retired) данных имеет вид:
    struct retired_ptr {
       typedef void (* fnDisposer )( void * );
       void *  ptr ; // Отложенный указатель
       fnDisposer pDisposer; // Функция-диспозер
       retired_ptr( void * p, fnDisposer d): ptr(p), pDisposer(d) {}
    };
    

    То есть хранится удаляемый (retired) указатель и функция его удаления. Метод Scan() HP-схемы вызывает pDisposer(ptr) для «удаления» элемента.
    Функция pDisposer знает тип своего аргумента. За прозрачное формирование данной функции отвечает уровень реализации. Например, физическое удаление может быть произведено так:
    template <typename T>
    struct make_disposer {
        static void dispose( void * p ) { delete reinterpret_cast<T *>(p); }
    };
    template <typename T>
    void retire_ptr( T * p )
    {
        // Помещаем p в массив arrRetired готовых к удалению данных
        // Заметим, что arrRetired – приватные данные потока
        arrRetired.push( retired_ptr( p, make_disposer<T>::dispose ));
        // Если массив заполнен – вызываем scan
        if ( arrRetired.full() )
           scan();
    }
    

    Это немного упрощенный подход, но суть, я думаю, ясна.


    If you want to use containers based on the HP schema from the libcds library, then simply declare main()a type in the object cds::gc::HPand connect it to each thread that uses containers based on the HP schema, as I described in the previous article . Another thing is if you want to write your own container class based on cds::gc::HP. In this case, you need to know the HP schema API.

    Cds :: gc :: HP class API
    Все методы класса cds::gc::HP – статические, что подчеркивает, что класс является оберткой над синглтоном.
    • Конструктор
      HP(size_t nHazardPtrCount = 0, 
         size_t nMaxThreadCount = 0, 
         size_t nMaxRetiredPtrCount = 0,          
         cds::gc::hzp::scan_type nScanType = cds::gc::hzp::inplace);
      

      nHazardPtrCount – максимальное число hazard pointer’ов (константа K схемы)
      nMaxThreadCount – максимальное число потоков (константа P схемы)
      nMaxRetiredPtrCount – размерность массива retired-указателей (константа R = 2KP схемы)
      nScanType – небольшая оптимизация: значение cds::gc::hzp::classic указывает, что следует точно следовать псевдокоду алгоритма Scan; значение cds::gc::hzp::inplace позволяет избавиться в Scan() от масива new_dlist и использовать вместо него dlist (он ведь может только уменьшаться).

      Следует помнить, что объект cds::gc::HP может быть только один. Конструктор на самом деле вызывает статические функции инициализации ядра, так что попытка объявить два объекта класса cds::gc::HP не приведет к созданию двух схем Hazard Pointer, а лишь к повторной инициализации, что безопасно, но бесполезно.
    • Помещение указателя в массив retired (отложенное удаление) текущего потока
      template <class Disposer, typename T>
      static void retire( T * p ) ;
      template <typename T>
      static void retire( T * p, void (* pFunc)(T *) )
      

      Аргумент Disposer (или pFunc) задают функтор удаления (диспозер). Вызов в первом случае довольно вычурный:
      struct Foo { … };
      struct fooDisposer {
         void operator()( Foo * p ) const { delete p; }
      };
      // Вызов диспозера myDisposer для указателя на Foo
      Foo * p = new Foo ;
      cds::gc::HP::retire<fooDisposer>( p );
      

    • static void force_dispose();
      

      Принудительный вызов алгоритма Scan() схемы Hazard Pointer. Не знаю, зачем это может понадобиться в реальной жизни, но в тестах libcds это бывает необходимо.

    Помимо этого, в классе cds::gc::HP объявлены три важных подкласса:
    • thread_gc – представляет собой обертку вокруг кода инициализации приватных для потока данных (thread data), относящихся к схеме Hazard Pointer. Этот класс предоставляет только конструктор, осуществляющий подключение HP-схемы к потоку, и деструктор, отключающий поток от схемы
    • Guard – собственно hazard pointer
    • template <size_t Count> GuardArray – массив hazard pointer’ов. При применении HP-схемы очень часто требуется объявить несколько hazard-указателей сразу. Более эффективно сделать это сразу одним массивом, а не несколькими объектами типа Guard

    Классы Guard и GuardArray<N> представляют собой надстройку над внутренним массивом Hazard Pointer, приватным для потока. Они работают как аллокаторы из этого внутреннего массива.

    Класс Guard суть hazard-слот и имеет следующее API:
    • template <typename T>
      T protect( CDS_ATOMIC::atomic<T> const& toGuard );
      template <typename T, class Func>
      T protect( CDS_ATOMIC::atomic<T> const& toGuard, Func f );
      

      Объявление атомарного указателя (тип T – обычно указатель) как hazard. Внутри этих методов скрыт цикл, который я описывал ранее: читается значение атомарного указателя toGuard, присваивается hazard pointer’у и затем проверяется, что прочитанный указатель не изменился.
      Второй синтаксис (с функтором Func) необходим, если нам требуется объявить как hazard не сам указатель на T *, а некий производный от него указатель. Это специфика интрузивных контейнеров, в которых контейнер управляет указателями на узел (node), а указатель на реальные данные может от него отличаться (например, node может являться полем реальных данных). Функтор Func имеет такую сигнатуру:
      struct functor {
         value_type * operator()( T * p ) ;
      };
      

      Оба метода возвращают указатель, который они объявили как hazard.
    • template <typename T> 
      T * assign( T * p );
      template <typename T, int Bitmask>
      T * assign( cds::details::marked_ptr<T, Bitmask> p );
      

      Эти методы объявляют указатель p как hazard. Здесь, в отличие от protect, нет никакого цикла, — p просто помещается в hazard-слот.
      Второй синтаксис предназначен для маркированных указателей cds::details::marked_ptr. В marked-указателях используются младшие 2-3 бита (которые всегда 0 на выравненных данных) в качестве хранилища битовых флагов, — очень распространенный прием в lock-free программировании. Данный метод помещает в hazard-слот указатель с обнуленными битами флагов (по маске Bitmask).
      Методы возвращают указатель, который они объявили как hazard.
    • template <typename T>
      T * get() const;
      

      Читаем значение текущего hazard-слота. Иногда это бывает нужно.
    • void copy( Guard const& src );
      

      Копирует значение hazard-слота из src в this. В результате два hazard-слота содержат одно и то же значение.
    • void clear();
      

      Обнуление значения hazard-слота. То е самое делает деструктор класса Guard.

    Класс GuardArray обладает аналогичным API, только указывается ещё индекс в массиве:
    template <typename T>
    T protect(size_t nIndex, CDS_ATOMIC::atomic<T> const& toGuard );
    template <typename T, class Func>
    T protect(size_t nIndex, CDS_ATOMIC::atomic<T> const& toGuard, Func f )
    template <typename T>
    T * assign( size_t nIndex, T * p );
    template <typename T, int Bitmask>
    T * assign( size_t nIndex, cds::details::marked_ptr<T, Bitmask> p );
    void copy( size_t nDestIndex, size_t nSrcIndex );
    void copy( size_t nIndex, Guard const& src );
    template <typename T>
    T * get( size_t nIndex) const;
    void clear( size_t nIndex);
    


    Внимательный читатель заметит незнакомое CDS_ATOMIC – что это?
    Это макрос, объявляющий подходящее пространство имен для std::atomic. Если компилятор поддерживает (и реализует) C++11 atomic, то CDS_ATOMIC есть std. Если не поддерживает – это cds::cxx11_atomics, пространство имен, в котором располагаются собственные libcds-велосипеды для atomic. В будущей версии libcds можно будет использовать boost.atomic, тогда CDS_ATOMIC будет равно boost.


    Hazard Pointer with Reference Counter



    The disadvantage of the Hazard Pointer scheme is that it is designed to protect only local links to lock-free container nodes. She cannot protect global links, for example, for implementing the concept of iterators: for this, in principle, an unlimited size of an array of hazard pointers would be required.
    Clarification
    На самом деле, с помощью HP-схемы можно реализовать итераторы. Для этого сам объект-итератор должен содержать в себе HP-слот, защищающий указатель итератора. В результате получится весьма специфический итератор, привязанный к потоку (вспомним, что hazard-слоты являются приватными данными для потока). Учитывая этот факт, а также конечность множества hazard-указателей, можно сделать вывод, что в общем случае итераторы с помощью HP-схемы не реализовать.

    На картинке — классическая древнегреческая статуя «Самсон, поражающий дубиной Бага, покровителя говнокода». Древнегреческие программисты считали, что подсчет ссылок — универсальный инструмент, избавляющий от всех ошибок. Сейчас мы знаем, что древние ошибались.

    The most famous method of recognizing whether an object is used or not is the reference counting (RefCount) method. In the work of Valois, one of the pioneers of the lock-free approach, the reference counting scheme was used to safely remove container elements. But the RefCount scheme has its drawbacks, the main one of which is the difficulty of implementing cyclic data structures when elements refer to each other. In addition, many researchers note the inefficiency of the RefCount scheme, since its lock-free implementation uses fetch-and-add primitives too often (in fact, before each use of the pointer, the counter of links to it should be increased, and then decremented).
    A research team from the University of Gothenburg published in 2005 [GPST05], in which the Hazard Pointer and RefCount methods are combined: the Hazard Pointers scheme is used to effectively protect local links inside the lock-free data structure operations, and the RefCount scheme is used to protect global links and maintain integrity data structures. For brevity, we call this scheme HRC (Hazard pointer RefCounting).
    The use of Hazard Pointers allowed avoiding the heavy operations of incrementing / decrementing the number of links to an element while protecting local links, which significantly increased the performance of the RefCounting scheme in general. On the other hand, the application of two approaches at once somewhat complicated the algorithm of the combined scheme (due to the abundance of technical details, I do not provide its full pseudo-code, see [GPST05]). If the Hazard Pointers scheme does not require any special support from the elements of the lock-free container themselves , then HRC relies on the presence of two auxiliary methods for the element:
    void CleanUpNode( Node * pNode);
    void TerminateNode( Node * pNode);
    

    The procedure TerminateNoderesets pNodeall pointers to other elements of the container inside the element . The procedure is CleanUpNodeused to ensure that an element pNoderefers only to “live” (not marked for deletion) elements of the data structure, changing (promoting) links if necessary; since each link in the RefCount container is accompanied by an increase in the reference counter of the element to which we are referring, it CleanUpNodealso reduces the reference counts of deleted elements:
    void CleanUpNode(Node * pNode)
    {
        for (all x where pNode->link[x] of node is reference-counted) {
        retry:
            node1 = DeRefLink(&pNode->link[x]);  // устанавливает HP
            if (node1 != NULL and !is_deleted( node1 )) {
                node2 = DeRefLink(node1->link[x]); // устанавливает HP
                // Меняем ссылку, а заодно и декрементируем счетчик ссылок
                // на старый элемент node1
                CompareAndSwapRef(&pNode->link[x],node1,node2);
                ReleaseRef(node2);	// очищает HP
                ReleaseRef(node1);	// очищает HP
                goto retry; // новая ссылка также может быть уже удаленной, поэтому повторяем
            }
            ReleaseRef(node1);	// очищает HP
        }
    }
    

    Due to such a transfer of lock-free container control accents from the core of the circuit to the container element itself (which fits well with the C ++ virtual functions), the HRC core itself becomes independent of the specific lock-free data structure being implemented. We note, however, that the algorithm CleanUpNodemay violate the integrity of the data structure for a short time, as it changes the links inside the element one at a time , which may be unacceptable in some cases. For lock-free containers for which such a violation is unacceptable, you can use MultiCAS software emulation to atomically change all the links in an element.
    As with the Hazard Pointers scheme, the number of pending elements is limited from above. The physical deletion algorithm is very similar to the algorithmScanHazar Pointers schemas (with some changes related to managing link counts and calling CleanUpNode). The main difference is as follows: if in the Hazard Pointers scheme we are guaranteed (by choosing R > N = P * K) that the procedure Scanwill necessarily delete something (that is, there is at least one pending element that is not protected by a hazard pointer), then in the HRC scheme the procedure call Scanmay fail due to reciprocal links of elements to each other (each link is a counter increment). Therefore, in case of failure Scan, an auxiliary procedure is called CleanUpAll: it runs through all arrays of pending pointers of all threads and calls a procedure for each deleted element CleanUpNode, thereby making the call again successful Scan.
    Implementing an HRC Schema in libcds
    UPD (2016 год): в версии libcds 2.0.0 реализация HRC-схемы удалена по причине нестабильности реализации (это скорее мой недостаток, чем алгоритма), а также из-за того, что она не дает никаких преимуществ по производительности по сравнению с чистым Hazard Pointer.

    В libcds HRC-схема реализована по аналогии с HP-схемой. Основной класс – cds::gc::HRC. API этого класса полностью аналогичен API cds::gc::HP. Детали реализации расположены в namespace cds::gc::hrc.
    Главное преимущество HRC-схемы – возможность воплотить концепцию итераторов – не реализована в libcds. В процессе работы над библиотекой я пришел к выводу, что в общем случае итераторы в принципе не применимы к lock-free контейнерам. Итераторы предполагают не только безопасное обращение к объекту, на который указывает итератор, но и безопасный и полный обход всего контейнера. Последнее условие – полный обход – в lock-free контейнерах обеспечить в общем случае невозможно: всегда найдется поток-конкурент, удаляющий элемент, на котором позиционируется итератор. В результате, безопасно обратиться к полям узла можно, так как узел защищен HP-схемой и не может быть физически удален, но получить следующий элемент уже невозможно, — узел может быть уже исключен из lock-free контейнера.
    Таким образом, HRC-схема представлена в libcds как специфический случай реализации HP-схемы. На её примере можно убедиться, насколько введение дополнительных условий (счетчика ссылок) утяжеляет HP-схему: на тестовых примерах HRC-контейнер может быть в 2-3 раза медленней, чем HP-контейнер. Плюс можно увидеть «подвисания», свойственные полноценным сборщикам мусора: при невозможности удалить что-либо в вызове Scan (например, из-за циклических ссылок) запускается тяжелая процедура CleanUpAll, пробегающая по всем retired-узлам.
    Так что HRC-схема используется в libcds как разновидность HP-like схем, позволяющая при проектировании не забывать об общности. В силу специфического внутреннего строения HRC-схемы обобщение HRC-based и HP-based контейнеров иногда представляет собой очень интересную задачу.


    Pass the buck



    Working on the problem of freeing memory in lock-free data structures, Herlihy & al invented the Pass-the-Buck algorithm (PTB, the “blame” idiom) [HLM02, HLM05], which in essence is very similar to M. Michael’s HP scheme, but significantly different in implementation details.
    Just like in the HP-scheme, the PTB-scheme requires declaring the pointer protected (guarded, analogue of hazard pointer in the HP-scheme). The PTB scheme was originally designed for a predetermined number of defenders (i.e. hazard pointers). Upon accumulation of a sufficient number of data ready for deletion (retired), a procedure Liberateis called — an analogue Scanin the HP scheme.Liberatereturns an array of pointers that can be safely removed. Unlike the HP scheme, where the array of retired pointers is private to the stream, in the PTB scheme the array of data ready for deletion is the same for all flows.
    The structure of the guard (hazard pointer) is interesting: it contains not only the protected pointer itself, but also a pointer to retired data, the so-called hand-off (“hands off”). If during the deletion process the procedure Liberatedetects that some retired data from the general array of data ready for deletion is protected by the guard, it places this retired record in the hand-off guard slot. At the next Liberatehand-off call, data can be deleted if the guard to which it is attached has changed, that is, it already contains a pointer to other protected data.

    The authors in [HLM05] give two algorithms for Liberate: wait-free and lock-free. The wait-free algorithm requires dwCAS (CAS over a double word), which makes the algorithm dependent on dwCAS support on the target platform. The lock-free algorithm is interesting in that it can only work when data is changed. If the data (guards and retired pointers) remain unchanged between calls to the lock-free version Liberate, a loop is possible (more precisely, the algorithm will not delete all possible retired data, so it will need to be called again and again ). The situation of the immutability of data occurs at the end of the program, when a purge occurs in the singleton destructor of the PTB circuit, including a call Liberate.

    Fairly tormented in due time with a loop, I decided to change the algorithmLiberatePTB schemes, making it similar to the HP scheme. As a result, the PTB implementation in libcds has become more similar to the HP version with an arbitrary number of hazard pointers and a single array of retired data. This had little effect on performance: a "clean" HP circuit is still slightly faster than PTB, but PTB may be preferable due to the absence of restrictions on the number of guards.

    Libcds implementation
    UPD (2016 год): в версии libcds 2.0.0 эта схема переименована в cds::gc::DHP — динамический HP, — так как де факто от оригинального pass-the-buck там мало что осталось, — получился алгоритм Hazard Pointer без ограничения на число потоков.

    В библиотеке libcds PTB-схему представляет класс cds::gc::PTB, детали реализации находятся в namespace cds::gc::ptb. API класса cds::gc::PTB полностью аналогичен cds::gc:::HP, за исключением аргументов конструктора. Конструктор принимает следующие аргументы:
    PTB( size_t nLiberateThreshold = 1024, size_t nInitialThreadGuardCount = 8 );
    

    • nLiberateThreshold — порог вызова Liberate. Как только общий массив retired-данных достигнет этого размера, вызывается Liberate
    • nInitialThreadGuardCount — начальное число quard'ов при создании потока (точнее, при подсоединении потока к внутренней инфраструктуре libcds). В последующем в случае нехватки guard'ов автоматически создаются новые



    Conclusion


    In this article, I gave an overview of the safe memory reclamation algorithms that I know, with a particular emphasis on Hazard Pointer-type circuits. The HP schema and its variants provide a good way to provide secure memory management in lock-free data structures.

    All of the above relates more to the field of creating lock-free data structures. If you just use the libcds library, then you just need to initialize the selected scheme, do not forget to attach (attach) streams to the scheme and substitute the circuit class as the first argument to the GCcontainer from the libcds library. Link protection, calling Scan()/ Liberate()etc., all this is already wired inside the container implementation.

    There was another interesting algorithm left behind - RCU, which differs from HP-like circuits, but I will talk about it in one of the following articles.

    UPD 2016: thanks to Errandir for spotting typos in the pseudo-code, especially in the Hazard Pointer pseudo-code (the basic constants of the HP method were mixed up).

    Primary sources
    [Fra03] Keir Fraser Practical Lock Freedom, 2004; technical report is based on a dissertation submitted September 2003 by K.Fraser for the degree of Doctor of Philosophy to the University of Cambridge, King's College

    [GPST05] Anders Gidenstam, Marina Papatriantafilou, Hakan Sundell, Philippas Tsigas Practical and Efficient Lock-Free Garbage Collection Based on Reference Counting, Technical Report no. 2005-04 in Computer Science and Engineering at Chalmers University of Technology and Goteborg University, 2005

    [Har01] Timothy Harris A pragmatic implementation of Non-Blocking Linked List, 2001

    [HLM02] M. Herlihy, V. Luchangco, and M. Moir The repeat offender problem: A mechanism for supporting
    dynamic-sized lockfree data structures
    Technical Report TR-2002-112, Sun Microsystems
    Laboratories, 2002.

    [HLM05] M.Herlihy, V.Luchangco, P.Martin, and M.Moir Nonblocing Memory Management Support for Dynamic-Sized Data Structure, ACM Transactions on Computer Systems, Vol. 23, No. 2, May 2005, Pages 146–196.

    [Mic02] Maged Michael Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes, 2002

    [Mic03] Maged Michael Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects, 2003

    [MS98] Maged Michael, Michael Scott Simple, Fast and Practical Non-Bloking and Blocking Concurrent Queue Algorithms, 1998

    [Tor08] Johan Torp The parallelism shift and C++’s memory model, chapter 13, 2008