Page History

...

Code Block

bgColor	#FFcccc
lang	c


#include <glib.h>
#include <glib-object.h>

struct Node {
  void *data;
  Node *next;
};

struct Queue {
  Node *head;
  Node *tail;
};

Queue* queue_new(void) {
  Queue *q = g_slice_new( sizeof(Queue));
  q->head = q->tail = g_slice_new0( sizeof(Node));
  return q;
}

void queue_enqueue(Queue *q, gpointer data) {
  Node *node;
  Node *tail;
  Node *next;

  node = g_slice_new(Node);
  node->data = data;
  node->next = NULL;
  while (TRUE) {
    tail = q->tail;
    next = tail->next;
    if (tail != q->tail) {
      continue;
    }
    if (next != NULL) {
      CAS(&q->tail, tail, next);
      continue;
    }
    if (CAS( &tail->next, null, node)) {
      break;
    }
  }
  CAS(&q->tail, tail, node);
}

gpointer queue_dequeue(Queue *q) {
  Node *node;
  Node *tail;
  Node *next;

  while (TRUE) {
    head = q->head;
    tail = q->tail;
    next = head->next;
    if (head != q->head) {
      continue;
    }
    if (next == NULL) {
      return NULL; // Empty
    }
    if (head == tail) {
      CAS(&q->tail, tail, next);
      continue;
    }
    data = next->data;
    if (CAS(&q->head, head, next)) {
      break;
    }
  }
  g_slice_free(Node, head);
  return data;
}

...

Thread	Queue Before	Operation	Queue After
`T1`	head -> A -> B -> C -> tail	Enters `queue_dequeue()` function head = A, tail = C next = B after executing `data = next->data;` This thread gets pre-empted	head -> A -> B -> C -> tail
`T2`	head -> A -> B -> C -> tail	Removes node A	head -> B -> C -> tail
`T2`	head -> B -> C -> tail	Removes node B	head -> C -> tail
`T2`	head -> C -> tail	Enqueues node A back into the queue	head -> A C -> C A -> tail
`T2`	head -> A C -> C A -> tail	Removes node C	head -> A -> tail
`T2`	head -> A -> tail	Enqueues a new node D After enqueue operation thread 2 gets pre-empted	head -> A -> D -> tail
`T1`	head -> A -> D -> tail	Thread 1 starts execution Compares the local head= `q->head` = A (true in this case) Updates `q->head` with node B (but node B is removed)	undefined {}

...

Code Block

bgColor	#ccccff
lang	c


// Hazard Pointers Types and Strucutre
 structure HPRecType {
   HP[K]:*Nodetype; Next:*HPRecType;}
// The header of the HPRec list
 HeadHPRec: *HPRecType;
//Per-thread private variables
 rlist: listType; // initially empty
 rcount: integer; // initially 0


//The Retired Node routine
RetiredNode(node:*NodeType) {
  rlist.push(node);
  rcount++;
  if(rcount >= R)
    Scan(HeadHPRec);
}


// The scan routine
Scan(head:*HPRecType) {
  // Stage1: Scan HP list and insert non null values in plist
  plist.init();
  hprec<-head;
  while (hprec != null) {
    for (i<-0 to K-1) {
      hptr<-hprec^HP[i];
      if (hptr!= null)
        plist.insert(hptr);
    }
    hprec<-hprec^Next;
  }

  // Stage 2: search plist
  tmplist<-rlist.popAll();
  rcount<-0;
  node<-tmplist.pop();
  while (node != null) {
    if (plist.lookup(node)) {
      rlist.push(node);
      rcount++;
    }
    else {
      PrepareForReuse(node);
    }
    node<-tmplist.pop();
  }
  plist.free();
}

...

Code Block

bgColor	#ccccff
lang	c


void queue_enqueue(Queue *q, gpointer data) {
  Node *node;
  Node *tail;
  Node *next;

  node = g_slice_new(Node);
  node->data = data;
  node->next = NULL;
  while (TRUE) {
    tail = q->tail;
    HAZARD_SET(0, tail);              // Mark tail has hazardous
    if (tail != q->tail) {            // Check tail hasn't changed
      continue;
    }
    next = tail->next;
    if (tail != q->tail) {
      continue;
    }
    if (next != NULL) {
      CAS(&q->tail, tail, next);
      continue;
    }
    if (CAS(&tail->next, null, node) {
      break;
    }
  }
  CAS(&q->tail, tail, node);
}


gpointer queue_dequeue(Queue *q) {
  Node *node;
  Node *tail;
  Node *next;

  while (TRUE) {
    head = q->head;
    LF_HAZARD_SET(0, head);    // Mark head as hazardous
    if (head != q->head) {     // Check head hasn't changed
      continue;
    }
    tail = q->tail;
    next = head->next;
    LF_HAZARD_SET(1, next);    // Mark next has hazardous
    if (head != q->head) {
      continue;
    }
    if (next == NULL) {
      return NULL; // Empty
    }
    if (head == tail) {
      CAS(&q->tail, tail, next);
      continue;
    }
    data = next->data;
    if (CAS(&q->head, head, next)) {
      break;
    }
  }
  LF_HAZARD_UNSET(head);        // Retire head, and perform
                                // reclamation if needed.
  return data;
}

...

In this compliant solution, pthreadmtx_mutex_lock() is used to lock the queue.

...

Code Block

bgColor	#ccccff
lang	c


#include <glib-object.h>

struct Node {
  void *data;
  Node *next;
};

struct Queue {
  Node *head;
  Node *tail;
  pthread_mutexmtx_t mutex;
};

Queue* queue_new(void) {
  Queue *q = g_slice_new( sizeof(Queue));
  q->head = q->tail = g_slice_new0( sizeof(Node));
  return q;
}

void queue_enqueue(Queue *q, gpointer data) {
  Node *node;
  Node *tail;
  Node *next;

  // Lock the queue before accesingaccessing the contents
  pthread_mutexmtx_lock(&(q->mutex));

  node = g_slice_new(Node);
  node->data = data;
  node->next = NULL;

  if(q->head == NULL) {
    q->head = node;
    q->tail = node;
  }
  else {
    q->tail->next = node;
    q->tail = node;
  }
  // Unlock the mutex
  pthreadmtx_mutex_unlock(&(queue->mutex));
}

gpointer queue_dequeue(Queue *q) {
  Node *node;
  Node *tail;
  Node *next;

  pthreadmtx_mutex_lock(&(q->mutex));

  head = q->head;
  tail = q->tail;
  next = head->next;
  data = next->data;
  q->head = next;

  g_slice_free(Node, head);
  pthread_mutexmtx_unlock(&(queue->mutex));

  return data;
}

...

Space shortcuts

Page tree

Versions Compared

Old Version 12

New Version 13

Key