11554Smax.romanov@nginx.com
21554Smax.romanov@nginx.com /*
31554Smax.romanov@nginx.com * Copyright (C) NGINX, Inc.
41554Smax.romanov@nginx.com */
51554Smax.romanov@nginx.com
61554Smax.romanov@nginx.com #ifndef _NXT_NNCQ_H_INCLUDED_
71554Smax.romanov@nginx.com #define _NXT_NNCQ_H_INCLUDED_
81554Smax.romanov@nginx.com
91554Smax.romanov@nginx.com
101554Smax.romanov@nginx.com /* Numeric Naive Circular Queue */
111554Smax.romanov@nginx.com
121554Smax.romanov@nginx.com #define NXT_NNCQ_SIZE 16384
131554Smax.romanov@nginx.com
141554Smax.romanov@nginx.com typedef uint32_t nxt_nncq_atomic_t;
151554Smax.romanov@nginx.com typedef uint16_t nxt_nncq_cycle_t;
161554Smax.romanov@nginx.com
171554Smax.romanov@nginx.com typedef struct {
181554Smax.romanov@nginx.com nxt_nncq_atomic_t head;
191554Smax.romanov@nginx.com nxt_nncq_atomic_t entries[NXT_NNCQ_SIZE];
201554Smax.romanov@nginx.com nxt_nncq_atomic_t tail;
211554Smax.romanov@nginx.com } nxt_nncq_t;
221554Smax.romanov@nginx.com
231554Smax.romanov@nginx.com
241554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_head(nxt_nncq_t const volatile * q)251554Smax.romanov@nginx.com nxt_nncq_head(nxt_nncq_t const volatile *q)
261554Smax.romanov@nginx.com {
271554Smax.romanov@nginx.com return q->head;
281554Smax.romanov@nginx.com }
291554Smax.romanov@nginx.com
301554Smax.romanov@nginx.com
311554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_tail(nxt_nncq_t const volatile * q)321554Smax.romanov@nginx.com nxt_nncq_tail(nxt_nncq_t const volatile *q)
331554Smax.romanov@nginx.com {
341554Smax.romanov@nginx.com return q->tail;
351554Smax.romanov@nginx.com }
361554Smax.romanov@nginx.com
371554Smax.romanov@nginx.com
381554Smax.romanov@nginx.com static inline void
nxt_nncq_tail_cmp_inc(nxt_nncq_t volatile * q,nxt_nncq_atomic_t t)391554Smax.romanov@nginx.com nxt_nncq_tail_cmp_inc(nxt_nncq_t volatile *q, nxt_nncq_atomic_t t)
401554Smax.romanov@nginx.com {
411554Smax.romanov@nginx.com nxt_atomic_cmp_set(&q->tail, t, t + 1);
421554Smax.romanov@nginx.com }
431554Smax.romanov@nginx.com
441554Smax.romanov@nginx.com
451554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_index(nxt_nncq_t const volatile * q,nxt_nncq_atomic_t i)461554Smax.romanov@nginx.com nxt_nncq_index(nxt_nncq_t const volatile *q, nxt_nncq_atomic_t i)
471554Smax.romanov@nginx.com {
481554Smax.romanov@nginx.com return i % NXT_NNCQ_SIZE;
491554Smax.romanov@nginx.com }
501554Smax.romanov@nginx.com
511554Smax.romanov@nginx.com
521554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_map(nxt_nncq_t const volatile * q,nxt_nncq_atomic_t i)531554Smax.romanov@nginx.com nxt_nncq_map(nxt_nncq_t const volatile *q, nxt_nncq_atomic_t i)
541554Smax.romanov@nginx.com {
551554Smax.romanov@nginx.com return i % NXT_NNCQ_SIZE;
561554Smax.romanov@nginx.com }
571554Smax.romanov@nginx.com
581554Smax.romanov@nginx.com
591554Smax.romanov@nginx.com static inline nxt_nncq_cycle_t
nxt_nncq_cycle(nxt_nncq_t const volatile * q,nxt_nncq_atomic_t i)601554Smax.romanov@nginx.com nxt_nncq_cycle(nxt_nncq_t const volatile *q, nxt_nncq_atomic_t i)
611554Smax.romanov@nginx.com {
621554Smax.romanov@nginx.com return i / NXT_NNCQ_SIZE;
631554Smax.romanov@nginx.com }
641554Smax.romanov@nginx.com
651554Smax.romanov@nginx.com
661554Smax.romanov@nginx.com static inline nxt_nncq_cycle_t
nxt_nncq_next_cycle(nxt_nncq_t const volatile * q,nxt_nncq_cycle_t i)671554Smax.romanov@nginx.com nxt_nncq_next_cycle(nxt_nncq_t const volatile *q, nxt_nncq_cycle_t i)
681554Smax.romanov@nginx.com {
691554Smax.romanov@nginx.com return i + 1;
701554Smax.romanov@nginx.com }
711554Smax.romanov@nginx.com
721554Smax.romanov@nginx.com
731554Smax.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)741554Smax.romanov@nginx.com nxt_nncq_new_entry(nxt_nncq_t const volatile *q, nxt_nncq_cycle_t cycle,
751554Smax.romanov@nginx.com nxt_nncq_atomic_t i)
761554Smax.romanov@nginx.com {
771554Smax.romanov@nginx.com return cycle * NXT_NNCQ_SIZE + (i % NXT_NNCQ_SIZE);
781554Smax.romanov@nginx.com }
791554Smax.romanov@nginx.com
801554Smax.romanov@nginx.com
811554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_empty(nxt_nncq_t const volatile * q)821554Smax.romanov@nginx.com nxt_nncq_empty(nxt_nncq_t const volatile *q)
831554Smax.romanov@nginx.com {
841554Smax.romanov@nginx.com return NXT_NNCQ_SIZE;
851554Smax.romanov@nginx.com }
861554Smax.romanov@nginx.com
871554Smax.romanov@nginx.com
88*2155Salx.manpages@gmail.com static inline void
nxt_nncq_init(nxt_nncq_t volatile * q)891554Smax.romanov@nginx.com nxt_nncq_init(nxt_nncq_t volatile *q)
901554Smax.romanov@nginx.com {
911554Smax.romanov@nginx.com q->head = NXT_NNCQ_SIZE;
921554Smax.romanov@nginx.com nxt_memzero((void *) q->entries, NXT_NNCQ_SIZE * sizeof(nxt_nncq_atomic_t));
931554Smax.romanov@nginx.com q->tail = NXT_NNCQ_SIZE;
941554Smax.romanov@nginx.com }
951554Smax.romanov@nginx.com
961554Smax.romanov@nginx.com
97*2155Salx.manpages@gmail.com static inline void
nxt_nncq_enqueue(nxt_nncq_t volatile * q,nxt_nncq_atomic_t val)981554Smax.romanov@nginx.com nxt_nncq_enqueue(nxt_nncq_t volatile *q, nxt_nncq_atomic_t val)
991554Smax.romanov@nginx.com {
1001554Smax.romanov@nginx.com nxt_nncq_cycle_t e_cycle, t_cycle;
1011554Smax.romanov@nginx.com nxt_nncq_atomic_t n, t, e, j;
1021554Smax.romanov@nginx.com
1031554Smax.romanov@nginx.com for ( ;; ) {
1041554Smax.romanov@nginx.com t = nxt_nncq_tail(q);
1051554Smax.romanov@nginx.com j = nxt_nncq_map(q, t);
1061554Smax.romanov@nginx.com e = q->entries[j];
1071554Smax.romanov@nginx.com
1081554Smax.romanov@nginx.com e_cycle = nxt_nncq_cycle(q, e);
1091554Smax.romanov@nginx.com t_cycle = nxt_nncq_cycle(q, t);
1101554Smax.romanov@nginx.com
1111554Smax.romanov@nginx.com if (e_cycle == t_cycle) {
1121554Smax.romanov@nginx.com nxt_nncq_tail_cmp_inc(q, t);
1131554Smax.romanov@nginx.com continue;
1141554Smax.romanov@nginx.com }
1151554Smax.romanov@nginx.com
1161554Smax.romanov@nginx.com if (nxt_nncq_next_cycle(q, e_cycle) != t_cycle) {
1171554Smax.romanov@nginx.com continue;
1181554Smax.romanov@nginx.com }
1191554Smax.romanov@nginx.com
1201554Smax.romanov@nginx.com n = nxt_nncq_new_entry(q, t_cycle, val);
1211554Smax.romanov@nginx.com
1221554Smax.romanov@nginx.com if (nxt_atomic_cmp_set(&q->entries[j], e, n)) {
1231554Smax.romanov@nginx.com break;
1241554Smax.romanov@nginx.com }
1251554Smax.romanov@nginx.com }
1261554Smax.romanov@nginx.com
1271554Smax.romanov@nginx.com nxt_nncq_tail_cmp_inc(q, t);
1281554Smax.romanov@nginx.com }
1291554Smax.romanov@nginx.com
1301554Smax.romanov@nginx.com
131*2155Salx.manpages@gmail.com static inline nxt_nncq_atomic_t
nxt_nncq_dequeue(nxt_nncq_t volatile * q)1321554Smax.romanov@nginx.com nxt_nncq_dequeue(nxt_nncq_t volatile *q)
1331554Smax.romanov@nginx.com {
1341554Smax.romanov@nginx.com nxt_nncq_cycle_t e_cycle, h_cycle;
1351554Smax.romanov@nginx.com nxt_nncq_atomic_t h, j, e;
1361554Smax.romanov@nginx.com
1371554Smax.romanov@nginx.com for ( ;; ) {
1381554Smax.romanov@nginx.com h = nxt_nncq_head(q);
1391554Smax.romanov@nginx.com j = nxt_nncq_map(q, h);
1401554Smax.romanov@nginx.com e = q->entries[j];
1411554Smax.romanov@nginx.com
1421554Smax.romanov@nginx.com e_cycle = nxt_nncq_cycle(q, e);
1431554Smax.romanov@nginx.com h_cycle = nxt_nncq_cycle(q, h);
1441554Smax.romanov@nginx.com
1451554Smax.romanov@nginx.com if (e_cycle != h_cycle) {
1461554Smax.romanov@nginx.com if (nxt_nncq_next_cycle(q, e_cycle) == h_cycle) {
1471554Smax.romanov@nginx.com return nxt_nncq_empty(q);
1481554Smax.romanov@nginx.com }
1491554Smax.romanov@nginx.com
1501554Smax.romanov@nginx.com continue;
1511554Smax.romanov@nginx.com }
1521554Smax.romanov@nginx.com
1531554Smax.romanov@nginx.com if (nxt_atomic_cmp_set(&q->head, h, h + 1)) {
1541554Smax.romanov@nginx.com break;
1551554Smax.romanov@nginx.com }
1561554Smax.romanov@nginx.com }
1571554Smax.romanov@nginx.com
1581554Smax.romanov@nginx.com return nxt_nncq_index(q, e);
1591554Smax.romanov@nginx.com }
1601554Smax.romanov@nginx.com
1611554Smax.romanov@nginx.com
1621554Smax.romanov@nginx.com #endif /* _NXT_NNCQ_H_INCLUDED_ */
163