1/*
2 * Copyright 2010-2015 Samy Al Bahra.
3 * Copyright 2011 David Joseph.
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 *    notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in the
13 *    documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 * SUCH DAMAGE.
26 */
27
28#ifndef CK_HP_FIFO_H
29#define CK_HP_FIFO_H
30
31#include <ck_cc.h>
32#include <ck_hp.h>
33#include <ck_pr.h>
34#include <ck_stddef.h>
35
36#define CK_HP_FIFO_SLOTS_COUNT (2)
37#define CK_HP_FIFO_SLOTS_SIZE  (sizeof(void *) * CK_HP_FIFO_SLOTS_COUNT)
38
39/*
40 * Though it is possible to embed the data structure, measurements need
41 * to be made for the cost of this. If we were to embed the hazard pointer
42 * state into the data structure, this means every deferred reclamation
43 * will also include a cache invalidation when linking into the hazard pointer
44 * pending queue. This may lead to terrible cache line bouncing.
45 */
46struct ck_hp_fifo_entry {
47	void *value;
48	ck_hp_hazard_t hazard;
49	struct ck_hp_fifo_entry *next;
50};
51typedef struct ck_hp_fifo_entry ck_hp_fifo_entry_t;
52
53struct ck_hp_fifo {
54	struct ck_hp_fifo_entry *head;
55	struct ck_hp_fifo_entry *tail;
56};
57typedef struct ck_hp_fifo ck_hp_fifo_t;
58
59CK_CC_INLINE static void
60ck_hp_fifo_init(struct ck_hp_fifo *fifo, struct ck_hp_fifo_entry *stub)
61{
62
63	fifo->head = fifo->tail = stub;
64	stub->next = NULL;
65	return;
66}
67
68CK_CC_INLINE static void
69ck_hp_fifo_deinit(struct ck_hp_fifo *fifo, struct ck_hp_fifo_entry **stub)
70{
71
72	*stub = fifo->head;
73	fifo->head = fifo->tail = NULL;
74	return;
75}
76
77CK_CC_INLINE static void
78ck_hp_fifo_enqueue_mpmc(ck_hp_record_t *record,
79			struct ck_hp_fifo *fifo,
80			struct ck_hp_fifo_entry *entry,
81			void *value)
82{
83	struct ck_hp_fifo_entry *tail, *next;
84
85	entry->value = value;
86	entry->next = NULL;
87	ck_pr_fence_store_atomic();
88
89	for (;;) {
90		tail = ck_pr_load_ptr(&fifo->tail);
91		ck_hp_set_fence(record, 0, tail);
92		if (tail != ck_pr_load_ptr(&fifo->tail))
93			continue;
94
95		next = ck_pr_load_ptr(&tail->next);
96		if (next != NULL) {
97			ck_pr_cas_ptr(&fifo->tail, tail, next);
98			continue;
99		} else if (ck_pr_cas_ptr(&fifo->tail->next, next, entry) == true)
100			break;
101	}
102
103	ck_pr_fence_atomic();
104	ck_pr_cas_ptr(&fifo->tail, tail, entry);
105	return;
106}
107
108CK_CC_INLINE static bool
109ck_hp_fifo_tryenqueue_mpmc(ck_hp_record_t *record,
110			   struct ck_hp_fifo *fifo,
111			   struct ck_hp_fifo_entry *entry,
112			   void *value)
113{
114	struct ck_hp_fifo_entry *tail, *next;
115
116	entry->value = value;
117	entry->next = NULL;
118	ck_pr_fence_store_atomic();
119
120	tail = ck_pr_load_ptr(&fifo->tail);
121	ck_hp_set_fence(record, 0, tail);
122	if (tail != ck_pr_load_ptr(&fifo->tail))
123		return false;
124
125	next = ck_pr_load_ptr(&tail->next);
126	if (next != NULL) {
127		ck_pr_cas_ptr(&fifo->tail, tail, next);
128		return false;
129	} else if (ck_pr_cas_ptr(&fifo->tail->next, next, entry) == false)
130		return false;
131
132	ck_pr_fence_atomic();
133	ck_pr_cas_ptr(&fifo->tail, tail, entry);
134	return true;
135}
136
137CK_CC_INLINE static struct ck_hp_fifo_entry *
138ck_hp_fifo_dequeue_mpmc(ck_hp_record_t *record,
139			struct ck_hp_fifo *fifo,
140			void *value)
141{
142	struct ck_hp_fifo_entry *head, *tail, *next;
143
144	for (;;) {
145		head = ck_pr_load_ptr(&fifo->head);
146		ck_pr_fence_load();
147		tail = ck_pr_load_ptr(&fifo->tail);
148		ck_hp_set_fence(record, 0, head);
149		if (head != ck_pr_load_ptr(&fifo->head))
150			continue;
151
152		next = ck_pr_load_ptr(&head->next);
153		ck_hp_set_fence(record, 1, next);
154		if (head != ck_pr_load_ptr(&fifo->head))
155			continue;
156
157		if (head == tail) {
158			if (next == NULL)
159				return NULL;
160
161			ck_pr_cas_ptr(&fifo->tail, tail, next);
162			continue;
163		} else if (ck_pr_cas_ptr(&fifo->head, head, next) == true)
164			break;
165	}
166
167	ck_pr_store_ptr_unsafe(value, next->value);
168	return head;
169}
170
171CK_CC_INLINE static struct ck_hp_fifo_entry *
172ck_hp_fifo_trydequeue_mpmc(ck_hp_record_t *record,
173			   struct ck_hp_fifo *fifo,
174			   void *value)
175{
176	struct ck_hp_fifo_entry *head, *tail, *next;
177
178	head = ck_pr_load_ptr(&fifo->head);
179	ck_pr_fence_load();
180	tail = ck_pr_load_ptr(&fifo->tail);
181	ck_hp_set_fence(record, 0, head);
182	if (head != ck_pr_load_ptr(&fifo->head))
183		return NULL;
184
185	next = ck_pr_load_ptr(&head->next);
186	ck_hp_set_fence(record, 1, next);
187	if (head != ck_pr_load_ptr(&fifo->head))
188		return NULL;
189
190	if (head == tail) {
191		if (next == NULL)
192			return NULL;
193
194		ck_pr_cas_ptr(&fifo->tail, tail, next);
195		return NULL;
196	} else if (ck_pr_cas_ptr(&fifo->head, head, next) == false)
197		return NULL;
198
199	ck_pr_store_ptr_unsafe(value, next->value);
200	return head;
201}
202
203#define CK_HP_FIFO_ISEMPTY(f) ((f)->head->next == NULL)
204#define CK_HP_FIFO_FIRST(f)   ((f)->head->next)
205#define CK_HP_FIFO_NEXT(m)    ((m)->next)
206#define CK_HP_FIFO_FOREACH(fifo, entry)                       	\
207        for ((entry) = CK_HP_FIFO_FIRST(fifo);                	\
208             (entry) != NULL;                                   \
209             (entry) = CK_HP_FIFO_NEXT(entry))
210#define CK_HP_FIFO_FOREACH_SAFE(fifo, entry, T)			\
211        for ((entry) = CK_HP_FIFO_FIRST(fifo);			\
212             (entry) != NULL && ((T) = (entry)->next, 1);	\
213             (entry) = (T))
214
215#endif /* CK_HP_FIFO_H */
216