benchmark/ms-queue/my_queue.h

   1 #ifndef _MY_QUEUE_H
   2 #define _MY_QUEUE_H
   3
   4 #include <stdatomic.h>
   5
   6 #define MAX_NODES                       0xf
   7
   8 typedef unsigned long long pointer;
   9 typedef atomic_ullong pointer_t;
  10
  11 #define MAKE_POINTER(ptr, count)        ((((pointer)count) << 32) | ptr)
  12 #define PTR_MASK 0xffffffffLL
  13 #define COUNT_MASK (0xffffffffLL << 32)
  14
  15 static inline void set_count(pointer *p, unsigned int val) { *p = (*p & ~COUNT_MASK) | ((pointer)val << 32); }
  16 static inline void set_ptr(pointer *p, unsigned int val) { *p = (*p & ~PTR_MASK) | val; }
  17 static inline unsigned int get_count(pointer p) { return (p & COUNT_MASK) >> 32; }
  18 static inline unsigned int get_ptr(pointer p) { return p & PTR_MASK; }
  19
  20 typedef struct node {
  21         unsigned int value;
  22         pointer_t next;
  23 } node_t;
  24
  25 typedef struct {
  26         pointer_t head;
  27         pointer_t tail;
  28         node_t nodes[MAX_NODES + 1];
  29 } queue_t;
  30
  31 void init_queue(queue_t *q, int num_threads);
  32
  33 /**
  34         @Begin
  35         @Global_define:
  36                 @DeclareStruct:
  37                 typedef struct tag_elem {
  38                         call_id_t id;
  39                         unsigned int data;
  40                 } tag_elem_t;
  41
  42                 @DeclareVar:
  43                 spec_list *__queue;
  44                 id_tag_t *tag;
  45                 @InitVar:
  46                         __queue = new_spec_list();
  47                         tag = new_id_tag(); // Beginning of available id
  48                 @DefineFunc:
  49                         tag_elem_t* new_tag_elem(call_id_t id, unsigned int data) {
  50                                 tag_elem_t *e = (tag_elem_t*) MODEL_MALLOC(sizeof(tag_elem_t));
  51                                 e->id = id;
  52                                 e->data = data;
  53                                 return e;
  54                         }
  55                 @DefineFunc:
  56                         void free_tag_elem(tag_elem_t *e) {
  57                                 free(e);
  58                         }
  59                 @DefineFunc:
  60                         call_id_t get_id(void *wrapper) {
  61                                 return ((tag_elem_t*) wrapper)->id;
  62                         }
  63                 @DefineFunc:
  64                         unsigned int get_data(void *wrapper) {
  65                                 return ((tag_elem_t*) wrapper)->data;
  66                         }
  67         @Happens_before:
  68                 # Only check the happens-before relationship according to the id of the
  69                 # commit_point_set. For commit_point_set that has same ID, A -> B means
  70                 # B happens after the previous A.
  71                 Enqueue -> Dequeue
  72         @End
  73 */
  74
  75
  76
  77 /**
  78         @Begin
  79         @Interface: Enqueue
  80         @Commit_point_set: Enqueue_Success_Point
  81         @ID: get_and_inc(tag);
  82         @Action:
  83                 # __ID__ is an internal macro that refers to the id of the current
  84                 # interface call
  85                 tag_elem_t *elem = new_tag_elem(__ID__, val);
  86                 push_back(__queue, elem);
  87         @End
  88 */
  89 void enqueue(queue_t *q, unsigned int val);
  90
  91 /**
  92         @Begin
  93         @Interface: Dequeue
  94         @Commit_point_set: Dequeue_Success_Point | Dequeue_Empty_Point
  95         @ID: get_id(back(__queue))
  96         @Action:
  97                 unsigned int _Old_Val = get_data(front(__queue));
  98                 pop_front(__queue);
  99         @Post_check:
 100                 _Old_Val == __RET__
 101         @End
 102 */
 103 unsigned int dequeue(queue_t *q);
 104 int get_thread_num();
 105
 106 #endif