c++ - Concurrent Doubly Linked List - Multiple Producer/Consumer FIFO Queue - Deadlock -

i playing around doubly-linked list mpmc fifo-queue (mainly demonstration purposes). aim trying pin down mistake while , not make progress.

i run deadlock, shortly after producer-threads have produced values. pinned down problem following:

lock acquisition:

<thread id> | <message> | <mutex address>  4460175360 : trylock head:   0x7fb380c039d0 4460175360 : locked head:     0x7fb380c039d0 4460175360 : released head: 0x7fb380c039d0  4460175360 : trylock head:    0x7fb380c039d0 4460175360 : locked head:      0x7fb380c039d0 4460175360 : released head:  0x7fb380c039d0  4460175360 : trylock head:    0x7fb380c039d0 4460175360 : locked head:      0x7fb380c039d0 4460175360 : released head:  0x7fb380c039d0  4460175360 : trylock head:    0x7fb380c039d0 4459638784 : trylock tail:       0x7fb380c039d0 4460711936 : trylock tail:       0x7fb380c039d0 4460175360 : locked head:      0x7fb380c039d0 4460175360 : released head:  0x7fb380c039d0  4460175360 : trylock head: 0x7fb380c039d0   <---- try-lock-head never gets confirmed! 4459638784 : locked tail:  0x7fb380c039d0  4459638784 : release mutex: 0x7fb380c039d0 <---- producer thread released 0x7fb380c039d0 producer-thread 4459638784 produced: 0  ---- 1 element in queue ----  4460711936 : locked tail:  0x7fb381800020 <---- address of lock has changed fine (because element has been added) 4460711936 : release mutex @ addr: 0x7fb381800020 producer-thread 4460711936 produced: 0  ---- 2 elements in queue ----  4460711936 : trylock tail: 0x7fb381a00020 4459638784 : trylock tail: 0x7fb381a00020 4460711936 : locked tail:   0x7fb381a00020 4460711936 : release mutex @ addr: 0x7fb381a00020 producer-thread 4460711936 produced: 1  ---- 3 elements in queue ----  4459638784 : locked tail: 0x7fb380d00060  <---- again address has changed -- fine 4459638784 : release mutex @ addr: 0x7fb380d00060 producer-thread 4459638784 produced: 1  ---- 4 elements in queue ---- producers done ---- ---- consumer thread blocks - still trying lock 0x7fb380c039d0 ----  ---- nobody else holds 0x7fb380c039d0 ---- no self-deadlock? 

gdb tells me both producer threads have terminated, , thread waiting mutx @ addr 0x7fb380c039d0 thread 2 (the consumer thread):

    (gdb) info threads * 2                         0x00007fff8edc5dfd in pthread_mutex_lock ()   1 "com.apple.main-thread" 0x00007fff8e715386 in __semwait_signal () (gdb) bt #0  0x00007fff8e715122 in __psynch_mutexwait () #1  0x00007fff8edc5dfd in pthread_mutex_lock () #2  0x00000001000011a8 in concurrentdoublylinkedlist<int>::consumenode (this=0x1001000e0) @ concurrentdlist.h:142 #3  0x0000000100000bd4 in consumevalues (ctx=0x7fff5fbffa78) @ concurrentdlist.cpp:29 #4  0x00007fff8edc07a2 in _pthread_start () #5  0x00007fff8edad1e1 in thread_start () (gdb) f 2 #2  0x00000001000011a8 in concurrentdoublylinkedlist<int>::consumenode (this=0x1001000e0) @ concurrentdlist.h:142 142             pthread_mutex_lock(&head_->mutex); (gdb) info reg rax            0x200012d    33554733 rbx            0x100281000  4297592832 rcx            0x100280da8  4297592232 rdx            0x100    256 rsi            0x403    1027 rdi            0x1001039f0  4296030704 rbp            0x100280ed0  0x100280ed0 rsp            0x100280e00  0x100280e00 r8             0x2060   8288 r9             0x100280720  4297590560 r10            0xf9d79  1023353 r11            0x206    518 r12            0x1303   4867 r13            0x0  0 r14            0x7fff5fbffa78   140734799805048 r15            0x100000bb0  4294970288 rip            0x1000011a8  0x1000011a8 <concurrentdoublylinkedlist<int>::consumenode()+110> eflags         0x206    518 cs             0x7  7 ss             0x0  0 ds             0x0  0 es             0x0  0 fs             0x0  0 gs             0x0  0 (gdb) p *(pthread_mutex_t*) 0x1001039f0 $34 = {   __sig = 1297437784,    __opaque = "\000\000\000\000` \000\000\000\000\000\000\000\000\000\000\003\004\000\000\000\002\000\000{?\017\000\000\000\000\000\b:\020\000\001\000\000\000\f:\020\000\001\000\000\000\000\000\000\000\000\000\000" } 

unfortunately cannot insect pthread_mutex_t because opaque type. (although have opaque types turned on within gdb?). otherwise see owner of mutex is.

the code of list given below - excessively commented, explain thoughts on implementation. note far not or high-performance implementation - illustration purposes.

cpp-code:

#include <stdlib.h> #include <iostream>  #include <pthread.h>  template <class t> class node {     private:        t value_;         node<t> *next_;        node<t> *prev_;      public:          pthread_mutex_t mutex;          node(t value, node<t>* next, node<t>* prev)         {             value_ = value;              next_ = next;             prev_ = prev;              pthread_mutex_init(&mutex, null);         }          ~node()         {             pthread_mutex_destroy(&mutex);         }          void setnext(node<t>* next)         {             next_ = next;         }                  void setprevious(node<t>* prev)         {             prev_ = prev;         }          node<t>* getnext()         {             return next_;         }           node<t>* getprevious()         {             return prev_;         }           virtual bool issentinel()         {             return false;         }  };  template <class t> class sentinelnode : public node<t> {     public:       sentinelnode(t val, node<t>* next, node<t>* prev)           : node<t>(val, next, prev)       {       }        virtual bool issentinel()       {           return true;       } };  template <class t> class concurrentdoublylinkedlist {     private:         node<t> *head_;         node<t> *tail_;      public:          concurrentdoublylinkedlist()         {             head_ = tail_ = new sentinelnode<t>(null, null, null);         }          void producenode(node<t>* n)         {               pthread_mutex_lock(&tail_->mutex);              node<t>* old = tail_;              if(head_->issentinel())             {                 head_ = tail_ = n;                 pthread_mutex_unlock(&old->mutex);                  delete old;                 old = null;             }             else             {                 n->setnext(tail_);                 tail_->setprevious(n);                 tail_ = n;                  pthread_mutex_unlock(&old->mutex);             }         }          node<t>* consumenode()         {             pthread_mutex_lock(&head_->mutex);              if(head_->issentinel())             {                  /* head can sentinel if there                   * no element within list                   */                    /* means list                    * implicitly locked */                    /* return null , let thread decide */                    pthread_mutex_unlock(&head_->mutex);                    return null;             }             else             {                 /* head not sentinel, implies on of following:                  *     - list has 1 element, means:                  *         => head_ == tail_ && !head_->issentinel()                  *                       *     or                  *                       *     - list has @ least 2 elements, means:                  *         => head_ != tail_ && !head_->issentinel()                  *                  *     - absence of sentinel guarantees list                  *       not empty                  */                   if(head_ == tail_)                  {                       /* single element within list                         * list still locked,                         * implicit because head_ == tail_                        */                         /* replace element                         * sentinel, because                         * list empty afterwards                         */                          node<t>* p = head_;                         head_ = tail_ = new sentinelnode<t>(null, null, null);                          pthread_mutex_unlock(&p->mutex);                          return p;                  }                  else                  {                       /* @ least 2 elements in list                        * means current head                        * must have valid predecessor                         */                         /* producer , consumer                         * hold lock on 2 adjacent                         * nodes. thus, consumer                         * must acquire head->prev                         */                          node<t>* p = head_;                         node<t>* n = head_->getprevious();                          pthread_mutex_lock(&n->mutex);                          /* head_->prev can not owned                           * producer.                           */                          head_ = n;                         head_->setnext(null);                          pthread_mutex_unlock(&p->mutex);                         pthread_mutex_unlock(&n->mutex);                          return p;                  }              }         } }; 

i appreciate thoughts , ideas on stuff. looking @ while , totally on wrong path. appreciated..

thanks, sebastian

the consume , produce both lock head , tail nodes assuming nodes still head , tail afterwards. is, threads may have locked nodes no longer head or tail nodes. if stored "old" pointer before locking, @ least know node locked, locked node may have been consumed, , of logic may no longer hold.

i think easier lock head , tail pointers, rather actual nodes, assuming need produce , consume methods. of course, simplest solution lock entire data structure.