xref: /unit/src/nxt_app_nncq.h (revision 1555:1d84b9e4b459)
1*1555Smax.romanov@nginx.com 
2*1555Smax.romanov@nginx.com /*
3*1555Smax.romanov@nginx.com  * Copyright (C) NGINX, Inc.
4*1555Smax.romanov@nginx.com  */
5*1555Smax.romanov@nginx.com 
6*1555Smax.romanov@nginx.com #ifndef _NXT_APP_NNCQ_H_INCLUDED_
7*1555Smax.romanov@nginx.com #define _NXT_APP_NNCQ_H_INCLUDED_
8*1555Smax.romanov@nginx.com 
9*1555Smax.romanov@nginx.com 
10*1555Smax.romanov@nginx.com /* Appilcation Numeric Naive Circular Queue */
11*1555Smax.romanov@nginx.com 
12*1555Smax.romanov@nginx.com #define NXT_APP_NNCQ_SIZE  131072
13*1555Smax.romanov@nginx.com 
14*1555Smax.romanov@nginx.com typedef uint32_t nxt_app_nncq_atomic_t;
15*1555Smax.romanov@nginx.com typedef uint16_t nxt_app_nncq_cycle_t;
16*1555Smax.romanov@nginx.com 
17*1555Smax.romanov@nginx.com typedef struct {
18*1555Smax.romanov@nginx.com     nxt_app_nncq_atomic_t  head;
19*1555Smax.romanov@nginx.com     nxt_app_nncq_atomic_t  entries[NXT_APP_NNCQ_SIZE];
20*1555Smax.romanov@nginx.com     nxt_app_nncq_atomic_t  tail;
21*1555Smax.romanov@nginx.com } nxt_app_nncq_t;
22*1555Smax.romanov@nginx.com 
23*1555Smax.romanov@nginx.com 
24*1555Smax.romanov@nginx.com static inline nxt_app_nncq_atomic_t
nxt_app_nncq_head(nxt_app_nncq_t const volatile * q)25*1555Smax.romanov@nginx.com nxt_app_nncq_head(nxt_app_nncq_t const volatile *q)
26*1555Smax.romanov@nginx.com {
27*1555Smax.romanov@nginx.com     return q->head;
28*1555Smax.romanov@nginx.com }
29*1555Smax.romanov@nginx.com 
30*1555Smax.romanov@nginx.com 
31*1555Smax.romanov@nginx.com static inline nxt_app_nncq_atomic_t
nxt_app_nncq_tail(nxt_app_nncq_t const volatile * q)32*1555Smax.romanov@nginx.com nxt_app_nncq_tail(nxt_app_nncq_t const volatile *q)
33*1555Smax.romanov@nginx.com {
34*1555Smax.romanov@nginx.com     return q->tail;
35*1555Smax.romanov@nginx.com }
36*1555Smax.romanov@nginx.com 
37*1555Smax.romanov@nginx.com 
38*1555Smax.romanov@nginx.com static inline void
nxt_app_nncq_tail_cmp_inc(nxt_app_nncq_t volatile * q,nxt_app_nncq_atomic_t t)39*1555Smax.romanov@nginx.com nxt_app_nncq_tail_cmp_inc(nxt_app_nncq_t volatile *q, nxt_app_nncq_atomic_t t)
40*1555Smax.romanov@nginx.com {
41*1555Smax.romanov@nginx.com     nxt_atomic_cmp_set(&q->tail, t, t + 1);
42*1555Smax.romanov@nginx.com }
43*1555Smax.romanov@nginx.com 
44*1555Smax.romanov@nginx.com 
45*1555Smax.romanov@nginx.com static inline nxt_app_nncq_atomic_t
nxt_app_nncq_index(nxt_app_nncq_t const volatile * q,nxt_app_nncq_atomic_t i)46*1555Smax.romanov@nginx.com nxt_app_nncq_index(nxt_app_nncq_t const volatile *q, nxt_app_nncq_atomic_t i)
47*1555Smax.romanov@nginx.com {
48*1555Smax.romanov@nginx.com     return i % NXT_APP_NNCQ_SIZE;
49*1555Smax.romanov@nginx.com }
50*1555Smax.romanov@nginx.com 
51*1555Smax.romanov@nginx.com 
52*1555Smax.romanov@nginx.com static inline nxt_app_nncq_atomic_t
nxt_app_nncq_map(nxt_app_nncq_t const volatile * q,nxt_app_nncq_atomic_t i)53*1555Smax.romanov@nginx.com nxt_app_nncq_map(nxt_app_nncq_t const volatile *q, nxt_app_nncq_atomic_t i)
54*1555Smax.romanov@nginx.com {
55*1555Smax.romanov@nginx.com     return i % NXT_APP_NNCQ_SIZE;
56*1555Smax.romanov@nginx.com }
57*1555Smax.romanov@nginx.com 
58*1555Smax.romanov@nginx.com 
59*1555Smax.romanov@nginx.com static inline nxt_app_nncq_cycle_t
nxt_app_nncq_cycle(nxt_app_nncq_t const volatile * q,nxt_app_nncq_atomic_t i)60*1555Smax.romanov@nginx.com nxt_app_nncq_cycle(nxt_app_nncq_t const volatile *q, nxt_app_nncq_atomic_t i)
61*1555Smax.romanov@nginx.com {
62*1555Smax.romanov@nginx.com     return i / NXT_APP_NNCQ_SIZE;
63*1555Smax.romanov@nginx.com }
64*1555Smax.romanov@nginx.com 
65*1555Smax.romanov@nginx.com 
66*1555Smax.romanov@nginx.com static inline nxt_app_nncq_cycle_t
nxt_app_nncq_next_cycle(nxt_app_nncq_t const volatile * q,nxt_app_nncq_cycle_t i)67*1555Smax.romanov@nginx.com nxt_app_nncq_next_cycle(nxt_app_nncq_t const volatile *q,
68*1555Smax.romanov@nginx.com     nxt_app_nncq_cycle_t i)
69*1555Smax.romanov@nginx.com {
70*1555Smax.romanov@nginx.com     return i + 1;
71*1555Smax.romanov@nginx.com }
72*1555Smax.romanov@nginx.com 
73*1555Smax.romanov@nginx.com 
74*1555Smax.romanov@nginx.com static inline nxt_app_nncq_atomic_t
nxt_app_nncq_new_entry(nxt_app_nncq_t const volatile * q,nxt_app_nncq_cycle_t cycle,nxt_app_nncq_atomic_t i)75*1555Smax.romanov@nginx.com nxt_app_nncq_new_entry(nxt_app_nncq_t const volatile *q,
76*1555Smax.romanov@nginx.com     nxt_app_nncq_cycle_t cycle,
77*1555Smax.romanov@nginx.com     nxt_app_nncq_atomic_t i)
78*1555Smax.romanov@nginx.com {
79*1555Smax.romanov@nginx.com     return cycle * NXT_APP_NNCQ_SIZE + (i % NXT_APP_NNCQ_SIZE);
80*1555Smax.romanov@nginx.com }
81*1555Smax.romanov@nginx.com 
82*1555Smax.romanov@nginx.com 
83*1555Smax.romanov@nginx.com static inline nxt_app_nncq_atomic_t
nxt_app_nncq_empty(nxt_app_nncq_t const volatile * q)84*1555Smax.romanov@nginx.com nxt_app_nncq_empty(nxt_app_nncq_t const volatile *q)
85*1555Smax.romanov@nginx.com {
86*1555Smax.romanov@nginx.com     return NXT_APP_NNCQ_SIZE;
87*1555Smax.romanov@nginx.com }
88*1555Smax.romanov@nginx.com 
89*1555Smax.romanov@nginx.com 
90*1555Smax.romanov@nginx.com static void
nxt_app_nncq_init(nxt_app_nncq_t volatile * q)91*1555Smax.romanov@nginx.com nxt_app_nncq_init(nxt_app_nncq_t volatile *q)
92*1555Smax.romanov@nginx.com {
93*1555Smax.romanov@nginx.com     q->head = NXT_APP_NNCQ_SIZE;
94*1555Smax.romanov@nginx.com     nxt_memzero((void *) q->entries,
95*1555Smax.romanov@nginx.com                 NXT_APP_NNCQ_SIZE * sizeof(nxt_app_nncq_atomic_t));
96*1555Smax.romanov@nginx.com     q->tail = NXT_APP_NNCQ_SIZE;
97*1555Smax.romanov@nginx.com }
98*1555Smax.romanov@nginx.com 
99*1555Smax.romanov@nginx.com 
100*1555Smax.romanov@nginx.com static void
nxt_app_nncq_enqueue(nxt_app_nncq_t volatile * q,nxt_app_nncq_atomic_t val)101*1555Smax.romanov@nginx.com nxt_app_nncq_enqueue(nxt_app_nncq_t volatile *q, nxt_app_nncq_atomic_t val)
102*1555Smax.romanov@nginx.com {
103*1555Smax.romanov@nginx.com     nxt_app_nncq_cycle_t   e_cycle, t_cycle;
104*1555Smax.romanov@nginx.com     nxt_app_nncq_atomic_t  n, t, e, j;
105*1555Smax.romanov@nginx.com 
106*1555Smax.romanov@nginx.com     for ( ;; ) {
107*1555Smax.romanov@nginx.com         t = nxt_app_nncq_tail(q);
108*1555Smax.romanov@nginx.com         j = nxt_app_nncq_map(q, t);
109*1555Smax.romanov@nginx.com         e = q->entries[j];
110*1555Smax.romanov@nginx.com 
111*1555Smax.romanov@nginx.com         e_cycle = nxt_app_nncq_cycle(q, e);
112*1555Smax.romanov@nginx.com         t_cycle = nxt_app_nncq_cycle(q, t);
113*1555Smax.romanov@nginx.com 
114*1555Smax.romanov@nginx.com         if (e_cycle == t_cycle) {
115*1555Smax.romanov@nginx.com             nxt_app_nncq_tail_cmp_inc(q, t);
116*1555Smax.romanov@nginx.com             continue;
117*1555Smax.romanov@nginx.com         }
118*1555Smax.romanov@nginx.com 
119*1555Smax.romanov@nginx.com         if (nxt_app_nncq_next_cycle(q, e_cycle) != t_cycle) {
120*1555Smax.romanov@nginx.com             continue;
121*1555Smax.romanov@nginx.com         }
122*1555Smax.romanov@nginx.com 
123*1555Smax.romanov@nginx.com         n = nxt_app_nncq_new_entry(q, t_cycle, val);
124*1555Smax.romanov@nginx.com 
125*1555Smax.romanov@nginx.com         if (nxt_atomic_cmp_set(&q->entries[j], e, n)) {
126*1555Smax.romanov@nginx.com             break;
127*1555Smax.romanov@nginx.com         }
128*1555Smax.romanov@nginx.com     }
129*1555Smax.romanov@nginx.com 
130*1555Smax.romanov@nginx.com     nxt_app_nncq_tail_cmp_inc(q, t);
131*1555Smax.romanov@nginx.com }
132*1555Smax.romanov@nginx.com 
133*1555Smax.romanov@nginx.com 
134*1555Smax.romanov@nginx.com static nxt_app_nncq_atomic_t
nxt_app_nncq_dequeue(nxt_app_nncq_t volatile * q)135*1555Smax.romanov@nginx.com nxt_app_nncq_dequeue(nxt_app_nncq_t volatile *q)
136*1555Smax.romanov@nginx.com {
137*1555Smax.romanov@nginx.com     nxt_app_nncq_cycle_t   e_cycle, h_cycle;
138*1555Smax.romanov@nginx.com     nxt_app_nncq_atomic_t  h, j, e;
139*1555Smax.romanov@nginx.com 
140*1555Smax.romanov@nginx.com     for ( ;; ) {
141*1555Smax.romanov@nginx.com         h = nxt_app_nncq_head(q);
142*1555Smax.romanov@nginx.com         j = nxt_app_nncq_map(q, h);
143*1555Smax.romanov@nginx.com         e = q->entries[j];
144*1555Smax.romanov@nginx.com 
145*1555Smax.romanov@nginx.com         e_cycle = nxt_app_nncq_cycle(q, e);
146*1555Smax.romanov@nginx.com         h_cycle = nxt_app_nncq_cycle(q, h);
147*1555Smax.romanov@nginx.com 
148*1555Smax.romanov@nginx.com         if (e_cycle != h_cycle) {
149*1555Smax.romanov@nginx.com             if (nxt_app_nncq_next_cycle(q, e_cycle) == h_cycle) {
150*1555Smax.romanov@nginx.com                 return nxt_app_nncq_empty(q);
151*1555Smax.romanov@nginx.com             }
152*1555Smax.romanov@nginx.com 
153*1555Smax.romanov@nginx.com             continue;
154*1555Smax.romanov@nginx.com         }
155*1555Smax.romanov@nginx.com 
156*1555Smax.romanov@nginx.com         if (nxt_atomic_cmp_set(&q->head, h, h + 1)) {
157*1555Smax.romanov@nginx.com             break;
158*1555Smax.romanov@nginx.com         }
159*1555Smax.romanov@nginx.com     }
160*1555Smax.romanov@nginx.com 
161*1555Smax.romanov@nginx.com     return nxt_app_nncq_index(q, e);
162*1555Smax.romanov@nginx.com }
163*1555Smax.romanov@nginx.com 
164*1555Smax.romanov@nginx.com 
165*1555Smax.romanov@nginx.com #endif /* _NXT_APP_NNCQ_H_INCLUDED_ */
166