xref: /unit/src/nxt_nvbcq.h (revision 1554:8f22edff911d)
1*1554Smax.romanov@nginx.com 
2*1554Smax.romanov@nginx.com /*
3*1554Smax.romanov@nginx.com  * Copyright (C) NGINX, Inc.
4*1554Smax.romanov@nginx.com  */
5*1554Smax.romanov@nginx.com 
6*1554Smax.romanov@nginx.com #ifndef _NXT_NVBCQ_H_INCLUDED_
7*1554Smax.romanov@nginx.com #define _NXT_NVBCQ_H_INCLUDED_
8*1554Smax.romanov@nginx.com 
9*1554Smax.romanov@nginx.com 
10*1554Smax.romanov@nginx.com /* Numeric VBart Circular Queue */
11*1554Smax.romanov@nginx.com 
12*1554Smax.romanov@nginx.com #define NXT_NVBCQ_SIZE  16384
13*1554Smax.romanov@nginx.com 
14*1554Smax.romanov@nginx.com typedef uint32_t nxt_nvbcq_atomic_t;
15*1554Smax.romanov@nginx.com 
16*1554Smax.romanov@nginx.com struct nxt_nvbcq_s {
17*1554Smax.romanov@nginx.com     nxt_nvbcq_atomic_t  head;
18*1554Smax.romanov@nginx.com     nxt_nvbcq_atomic_t  entries[NXT_NVBCQ_SIZE];
19*1554Smax.romanov@nginx.com     nxt_nvbcq_atomic_t  tail;
20*1554Smax.romanov@nginx.com };
21*1554Smax.romanov@nginx.com 
22*1554Smax.romanov@nginx.com typedef struct nxt_nvbcq_s nxt_nvbcq_t;
23*1554Smax.romanov@nginx.com 
24*1554Smax.romanov@nginx.com 
25*1554Smax.romanov@nginx.com static inline nxt_nvbcq_atomic_t
nxt_nvbcq_head(nxt_nvbcq_t const volatile * q)26*1554Smax.romanov@nginx.com nxt_nvbcq_head(nxt_nvbcq_t const volatile *q)
27*1554Smax.romanov@nginx.com {
28*1554Smax.romanov@nginx.com     return q->head;
29*1554Smax.romanov@nginx.com }
30*1554Smax.romanov@nginx.com 
31*1554Smax.romanov@nginx.com 
32*1554Smax.romanov@nginx.com static inline nxt_nvbcq_atomic_t
nxt_nvbcq_tail(nxt_nvbcq_t const volatile * q)33*1554Smax.romanov@nginx.com nxt_nvbcq_tail(nxt_nvbcq_t const volatile *q)
34*1554Smax.romanov@nginx.com {
35*1554Smax.romanov@nginx.com     return q->tail;
36*1554Smax.romanov@nginx.com }
37*1554Smax.romanov@nginx.com 
38*1554Smax.romanov@nginx.com 
39*1554Smax.romanov@nginx.com static inline void
nxt_nvbcq_tail_cmp_inc(nxt_nvbcq_t volatile * q,nxt_nvbcq_atomic_t t)40*1554Smax.romanov@nginx.com nxt_nvbcq_tail_cmp_inc(nxt_nvbcq_t volatile *q, nxt_nvbcq_atomic_t t)
41*1554Smax.romanov@nginx.com {
42*1554Smax.romanov@nginx.com     nxt_atomic_cmp_set(&q->tail, t, t + 1);
43*1554Smax.romanov@nginx.com }
44*1554Smax.romanov@nginx.com 
45*1554Smax.romanov@nginx.com 
46*1554Smax.romanov@nginx.com static inline nxt_nvbcq_atomic_t
nxt_nvbcq_index(nxt_nvbcq_t const volatile * q,nxt_nvbcq_atomic_t i)47*1554Smax.romanov@nginx.com nxt_nvbcq_index(nxt_nvbcq_t const volatile *q, nxt_nvbcq_atomic_t i)
48*1554Smax.romanov@nginx.com {
49*1554Smax.romanov@nginx.com     return i % NXT_NVBCQ_SIZE;
50*1554Smax.romanov@nginx.com }
51*1554Smax.romanov@nginx.com 
52*1554Smax.romanov@nginx.com 
53*1554Smax.romanov@nginx.com static inline nxt_nvbcq_atomic_t
nxt_nvbcq_map(nxt_nvbcq_t const volatile * q,nxt_nvbcq_atomic_t i)54*1554Smax.romanov@nginx.com nxt_nvbcq_map(nxt_nvbcq_t const volatile *q, nxt_nvbcq_atomic_t i)
55*1554Smax.romanov@nginx.com {
56*1554Smax.romanov@nginx.com     return i % NXT_NVBCQ_SIZE;
57*1554Smax.romanov@nginx.com }
58*1554Smax.romanov@nginx.com 
59*1554Smax.romanov@nginx.com 
60*1554Smax.romanov@nginx.com static inline nxt_nvbcq_atomic_t
nxt_nvbcq_empty(nxt_nvbcq_t const volatile * q)61*1554Smax.romanov@nginx.com nxt_nvbcq_empty(nxt_nvbcq_t const volatile *q)
62*1554Smax.romanov@nginx.com {
63*1554Smax.romanov@nginx.com     return NXT_NVBCQ_SIZE;
64*1554Smax.romanov@nginx.com }
65*1554Smax.romanov@nginx.com 
66*1554Smax.romanov@nginx.com 
67*1554Smax.romanov@nginx.com static void
nxt_nvbcq_init(nxt_nvbcq_t volatile * q)68*1554Smax.romanov@nginx.com nxt_nvbcq_init(nxt_nvbcq_t volatile *q)
69*1554Smax.romanov@nginx.com {
70*1554Smax.romanov@nginx.com     nxt_nvbcq_atomic_t  i;
71*1554Smax.romanov@nginx.com 
72*1554Smax.romanov@nginx.com     q->head = 0;
73*1554Smax.romanov@nginx.com 
74*1554Smax.romanov@nginx.com     for (i = 0; i < NXT_NVBCQ_SIZE; i++) {
75*1554Smax.romanov@nginx.com         q->entries[i] = NXT_NVBCQ_SIZE;
76*1554Smax.romanov@nginx.com     }
77*1554Smax.romanov@nginx.com 
78*1554Smax.romanov@nginx.com     q->tail = NXT_NVBCQ_SIZE;
79*1554Smax.romanov@nginx.com }
80*1554Smax.romanov@nginx.com 
81*1554Smax.romanov@nginx.com 
82*1554Smax.romanov@nginx.com static void
nxt_nvbcq_enqueue(nxt_nvbcq_t volatile * q,nxt_nvbcq_atomic_t val)83*1554Smax.romanov@nginx.com nxt_nvbcq_enqueue(nxt_nvbcq_t volatile *q, nxt_nvbcq_atomic_t val)
84*1554Smax.romanov@nginx.com {
85*1554Smax.romanov@nginx.com     nxt_nvbcq_atomic_t  t, h, i;
86*1554Smax.romanov@nginx.com 
87*1554Smax.romanov@nginx.com     t = nxt_nvbcq_tail(q);
88*1554Smax.romanov@nginx.com     h = t - NXT_NVBCQ_SIZE;
89*1554Smax.romanov@nginx.com 
90*1554Smax.romanov@nginx.com     for ( ;; ) {
91*1554Smax.romanov@nginx.com         i = nxt_nvbcq_map(q, t);
92*1554Smax.romanov@nginx.com 
93*1554Smax.romanov@nginx.com         if (q->entries[i] == NXT_NVBCQ_SIZE
94*1554Smax.romanov@nginx.com             && nxt_atomic_cmp_set(&q->entries[i], NXT_NVBCQ_SIZE, val))
95*1554Smax.romanov@nginx.com         {
96*1554Smax.romanov@nginx.com             nxt_nvbcq_tail_cmp_inc(q, t);
97*1554Smax.romanov@nginx.com             return;
98*1554Smax.romanov@nginx.com         }
99*1554Smax.romanov@nginx.com 
100*1554Smax.romanov@nginx.com         if ((t - h) == NXT_NVBCQ_SIZE) {
101*1554Smax.romanov@nginx.com             h = nxt_nvbcq_head(q);
102*1554Smax.romanov@nginx.com 
103*1554Smax.romanov@nginx.com             if ((t - h) == NXT_NVBCQ_SIZE) {
104*1554Smax.romanov@nginx.com                 return;
105*1554Smax.romanov@nginx.com             }
106*1554Smax.romanov@nginx.com         }
107*1554Smax.romanov@nginx.com 
108*1554Smax.romanov@nginx.com         t++;
109*1554Smax.romanov@nginx.com     }
110*1554Smax.romanov@nginx.com }
111*1554Smax.romanov@nginx.com 
112*1554Smax.romanov@nginx.com 
113*1554Smax.romanov@nginx.com static nxt_nvbcq_atomic_t
nxt_nvbcq_dequeue(nxt_nvbcq_t volatile * q)114*1554Smax.romanov@nginx.com nxt_nvbcq_dequeue(nxt_nvbcq_t volatile *q)
115*1554Smax.romanov@nginx.com {
116*1554Smax.romanov@nginx.com     nxt_nvbcq_atomic_t  h, t, i, e;
117*1554Smax.romanov@nginx.com 
118*1554Smax.romanov@nginx.com     h = nxt_nvbcq_head(q);
119*1554Smax.romanov@nginx.com     t = h + NXT_NVBCQ_SIZE;
120*1554Smax.romanov@nginx.com 
121*1554Smax.romanov@nginx.com     for ( ;; ) {
122*1554Smax.romanov@nginx.com         i = nxt_nvbcq_map(q, h);
123*1554Smax.romanov@nginx.com         e = q->entries[i];
124*1554Smax.romanov@nginx.com 
125*1554Smax.romanov@nginx.com         if (e < NXT_NVBCQ_SIZE
126*1554Smax.romanov@nginx.com             && nxt_atomic_cmp_set(&q->entries[i], e, NXT_NVBCQ_SIZE))
127*1554Smax.romanov@nginx.com         {
128*1554Smax.romanov@nginx.com             nxt_atomic_cmp_set(&q->head, h, h + 1);
129*1554Smax.romanov@nginx.com 
130*1554Smax.romanov@nginx.com             return e;
131*1554Smax.romanov@nginx.com         }
132*1554Smax.romanov@nginx.com 
133*1554Smax.romanov@nginx.com         if ((t - h) == NXT_NVBCQ_SIZE) {
134*1554Smax.romanov@nginx.com             t = nxt_nvbcq_tail(q);
135*1554Smax.romanov@nginx.com 
136*1554Smax.romanov@nginx.com             if ((t - h) == NXT_NVBCQ_SIZE) {
137*1554Smax.romanov@nginx.com                 return NXT_NVBCQ_SIZE;
138*1554Smax.romanov@nginx.com             }
139*1554Smax.romanov@nginx.com         }
140*1554Smax.romanov@nginx.com 
141*1554Smax.romanov@nginx.com         h++;
142*1554Smax.romanov@nginx.com     }
143*1554Smax.romanov@nginx.com }
144*1554Smax.romanov@nginx.com 
145*1554Smax.romanov@nginx.com 
146*1554Smax.romanov@nginx.com #endif /* _NXT_NVBCQ_H_INCLUDED_ */
147