xref: /unit/src/nxt_nncq.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_NNCQ_H_INCLUDED_
7*1554Smax.romanov@nginx.com #define _NXT_NNCQ_H_INCLUDED_
8*1554Smax.romanov@nginx.com 
9*1554Smax.romanov@nginx.com 
10*1554Smax.romanov@nginx.com /* Numeric Naive Circular Queue */
11*1554Smax.romanov@nginx.com 
12*1554Smax.romanov@nginx.com #define NXT_NNCQ_SIZE  16384
13*1554Smax.romanov@nginx.com 
14*1554Smax.romanov@nginx.com typedef uint32_t nxt_nncq_atomic_t;
15*1554Smax.romanov@nginx.com typedef uint16_t nxt_nncq_cycle_t;
16*1554Smax.romanov@nginx.com 
17*1554Smax.romanov@nginx.com typedef struct {
18*1554Smax.romanov@nginx.com     nxt_nncq_atomic_t  head;
19*1554Smax.romanov@nginx.com     nxt_nncq_atomic_t  entries[NXT_NNCQ_SIZE];
20*1554Smax.romanov@nginx.com     nxt_nncq_atomic_t  tail;
21*1554Smax.romanov@nginx.com } nxt_nncq_t;
22*1554Smax.romanov@nginx.com 
23*1554Smax.romanov@nginx.com 
24*1554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_head(nxt_nncq_t const volatile * q)25*1554Smax.romanov@nginx.com nxt_nncq_head(nxt_nncq_t const volatile *q)
26*1554Smax.romanov@nginx.com {
27*1554Smax.romanov@nginx.com     return q->head;
28*1554Smax.romanov@nginx.com }
29*1554Smax.romanov@nginx.com 
30*1554Smax.romanov@nginx.com 
31*1554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_tail(nxt_nncq_t const volatile * q)32*1554Smax.romanov@nginx.com nxt_nncq_tail(nxt_nncq_t const volatile *q)
33*1554Smax.romanov@nginx.com {
34*1554Smax.romanov@nginx.com     return q->tail;
35*1554Smax.romanov@nginx.com }
36*1554Smax.romanov@nginx.com 
37*1554Smax.romanov@nginx.com 
38*1554Smax.romanov@nginx.com static inline void
nxt_nncq_tail_cmp_inc(nxt_nncq_t volatile * q,nxt_nncq_atomic_t t)39*1554Smax.romanov@nginx.com nxt_nncq_tail_cmp_inc(nxt_nncq_t volatile *q, nxt_nncq_atomic_t t)
40*1554Smax.romanov@nginx.com {
41*1554Smax.romanov@nginx.com     nxt_atomic_cmp_set(&q->tail, t, t + 1);
42*1554Smax.romanov@nginx.com }
43*1554Smax.romanov@nginx.com 
44*1554Smax.romanov@nginx.com 
45*1554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_index(nxt_nncq_t const volatile * q,nxt_nncq_atomic_t i)46*1554Smax.romanov@nginx.com nxt_nncq_index(nxt_nncq_t const volatile *q, nxt_nncq_atomic_t i)
47*1554Smax.romanov@nginx.com {
48*1554Smax.romanov@nginx.com     return i % NXT_NNCQ_SIZE;
49*1554Smax.romanov@nginx.com }
50*1554Smax.romanov@nginx.com 
51*1554Smax.romanov@nginx.com 
52*1554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_map(nxt_nncq_t const volatile * q,nxt_nncq_atomic_t i)53*1554Smax.romanov@nginx.com nxt_nncq_map(nxt_nncq_t const volatile *q, nxt_nncq_atomic_t i)
54*1554Smax.romanov@nginx.com {
55*1554Smax.romanov@nginx.com     return i % NXT_NNCQ_SIZE;
56*1554Smax.romanov@nginx.com }
57*1554Smax.romanov@nginx.com 
58*1554Smax.romanov@nginx.com 
59*1554Smax.romanov@nginx.com static inline nxt_nncq_cycle_t
nxt_nncq_cycle(nxt_nncq_t const volatile * q,nxt_nncq_atomic_t i)60*1554Smax.romanov@nginx.com nxt_nncq_cycle(nxt_nncq_t const volatile *q, nxt_nncq_atomic_t i)
61*1554Smax.romanov@nginx.com {
62*1554Smax.romanov@nginx.com     return i / NXT_NNCQ_SIZE;
63*1554Smax.romanov@nginx.com }
64*1554Smax.romanov@nginx.com 
65*1554Smax.romanov@nginx.com 
66*1554Smax.romanov@nginx.com static inline nxt_nncq_cycle_t
nxt_nncq_next_cycle(nxt_nncq_t const volatile * q,nxt_nncq_cycle_t i)67*1554Smax.romanov@nginx.com nxt_nncq_next_cycle(nxt_nncq_t const volatile *q, nxt_nncq_cycle_t i)
68*1554Smax.romanov@nginx.com {
69*1554Smax.romanov@nginx.com     return i + 1;
70*1554Smax.romanov@nginx.com }
71*1554Smax.romanov@nginx.com 
72*1554Smax.romanov@nginx.com 
73*1554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_new_entry(nxt_nncq_t const volatile * q,nxt_nncq_cycle_t cycle,nxt_nncq_atomic_t i)74*1554Smax.romanov@nginx.com nxt_nncq_new_entry(nxt_nncq_t const volatile *q, nxt_nncq_cycle_t cycle,
75*1554Smax.romanov@nginx.com     nxt_nncq_atomic_t i)
76*1554Smax.romanov@nginx.com {
77*1554Smax.romanov@nginx.com     return cycle * NXT_NNCQ_SIZE + (i % NXT_NNCQ_SIZE);
78*1554Smax.romanov@nginx.com }
79*1554Smax.romanov@nginx.com 
80*1554Smax.romanov@nginx.com 
81*1554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_empty(nxt_nncq_t const volatile * q)82*1554Smax.romanov@nginx.com nxt_nncq_empty(nxt_nncq_t const volatile *q)
83*1554Smax.romanov@nginx.com {
84*1554Smax.romanov@nginx.com     return NXT_NNCQ_SIZE;
85*1554Smax.romanov@nginx.com }
86*1554Smax.romanov@nginx.com 
87*1554Smax.romanov@nginx.com 
88*1554Smax.romanov@nginx.com static void
nxt_nncq_init(nxt_nncq_t volatile * q)89*1554Smax.romanov@nginx.com nxt_nncq_init(nxt_nncq_t volatile *q)
90*1554Smax.romanov@nginx.com {
91*1554Smax.romanov@nginx.com     q->head = NXT_NNCQ_SIZE;
92*1554Smax.romanov@nginx.com     nxt_memzero((void *) q->entries, NXT_NNCQ_SIZE * sizeof(nxt_nncq_atomic_t));
93*1554Smax.romanov@nginx.com     q->tail = NXT_NNCQ_SIZE;
94*1554Smax.romanov@nginx.com }
95*1554Smax.romanov@nginx.com 
96*1554Smax.romanov@nginx.com 
97*1554Smax.romanov@nginx.com static void
nxt_nncq_enqueue(nxt_nncq_t volatile * q,nxt_nncq_atomic_t val)98*1554Smax.romanov@nginx.com nxt_nncq_enqueue(nxt_nncq_t volatile *q, nxt_nncq_atomic_t val)
99*1554Smax.romanov@nginx.com {
100*1554Smax.romanov@nginx.com     nxt_nncq_cycle_t   e_cycle, t_cycle;
101*1554Smax.romanov@nginx.com     nxt_nncq_atomic_t  n, t, e, j;
102*1554Smax.romanov@nginx.com 
103*1554Smax.romanov@nginx.com     for ( ;; ) {
104*1554Smax.romanov@nginx.com         t = nxt_nncq_tail(q);
105*1554Smax.romanov@nginx.com         j = nxt_nncq_map(q, t);
106*1554Smax.romanov@nginx.com         e = q->entries[j];
107*1554Smax.romanov@nginx.com 
108*1554Smax.romanov@nginx.com         e_cycle = nxt_nncq_cycle(q, e);
109*1554Smax.romanov@nginx.com         t_cycle = nxt_nncq_cycle(q, t);
110*1554Smax.romanov@nginx.com 
111*1554Smax.romanov@nginx.com         if (e_cycle == t_cycle) {
112*1554Smax.romanov@nginx.com             nxt_nncq_tail_cmp_inc(q, t);
113*1554Smax.romanov@nginx.com             continue;
114*1554Smax.romanov@nginx.com         }
115*1554Smax.romanov@nginx.com 
116*1554Smax.romanov@nginx.com         if (nxt_nncq_next_cycle(q, e_cycle) != t_cycle) {
117*1554Smax.romanov@nginx.com             continue;
118*1554Smax.romanov@nginx.com         }
119*1554Smax.romanov@nginx.com 
120*1554Smax.romanov@nginx.com         n = nxt_nncq_new_entry(q, t_cycle, val);
121*1554Smax.romanov@nginx.com 
122*1554Smax.romanov@nginx.com         if (nxt_atomic_cmp_set(&q->entries[j], e, n)) {
123*1554Smax.romanov@nginx.com             break;
124*1554Smax.romanov@nginx.com         }
125*1554Smax.romanov@nginx.com     }
126*1554Smax.romanov@nginx.com 
127*1554Smax.romanov@nginx.com     nxt_nncq_tail_cmp_inc(q, t);
128*1554Smax.romanov@nginx.com }
129*1554Smax.romanov@nginx.com 
130*1554Smax.romanov@nginx.com 
131*1554Smax.romanov@nginx.com static nxt_nncq_atomic_t
nxt_nncq_dequeue(nxt_nncq_t volatile * q)132*1554Smax.romanov@nginx.com nxt_nncq_dequeue(nxt_nncq_t volatile *q)
133*1554Smax.romanov@nginx.com {
134*1554Smax.romanov@nginx.com     nxt_nncq_cycle_t   e_cycle, h_cycle;
135*1554Smax.romanov@nginx.com     nxt_nncq_atomic_t  h, j, e;
136*1554Smax.romanov@nginx.com 
137*1554Smax.romanov@nginx.com     for ( ;; ) {
138*1554Smax.romanov@nginx.com         h = nxt_nncq_head(q);
139*1554Smax.romanov@nginx.com         j = nxt_nncq_map(q, h);
140*1554Smax.romanov@nginx.com         e = q->entries[j];
141*1554Smax.romanov@nginx.com 
142*1554Smax.romanov@nginx.com         e_cycle = nxt_nncq_cycle(q, e);
143*1554Smax.romanov@nginx.com         h_cycle = nxt_nncq_cycle(q, h);
144*1554Smax.romanov@nginx.com 
145*1554Smax.romanov@nginx.com         if (e_cycle != h_cycle) {
146*1554Smax.romanov@nginx.com             if (nxt_nncq_next_cycle(q, e_cycle) == h_cycle) {
147*1554Smax.romanov@nginx.com                 return nxt_nncq_empty(q);
148*1554Smax.romanov@nginx.com             }
149*1554Smax.romanov@nginx.com 
150*1554Smax.romanov@nginx.com             continue;
151*1554Smax.romanov@nginx.com         }
152*1554Smax.romanov@nginx.com 
153*1554Smax.romanov@nginx.com         if (nxt_atomic_cmp_set(&q->head, h, h + 1)) {
154*1554Smax.romanov@nginx.com             break;
155*1554Smax.romanov@nginx.com         }
156*1554Smax.romanov@nginx.com     }
157*1554Smax.romanov@nginx.com 
158*1554Smax.romanov@nginx.com     return nxt_nncq_index(q, e);
159*1554Smax.romanov@nginx.com }
160*1554Smax.romanov@nginx.com 
161*1554Smax.romanov@nginx.com 
162*1554Smax.romanov@nginx.com #endif /* _NXT_NNCQ_H_INCLUDED_ */
163