xref: /freebsd/sys/compat/linuxkpi/common/include/linux/list.h (revision 2f513db72b034fd5ef7f080b11be5c711c15186a)
1 /*-
2  * Copyright (c) 2010 Isilon Systems, Inc.
3  * Copyright (c) 2010 iX Systems, Inc.
4  * Copyright (c) 2010 Panasas, Inc.
5  * Copyright (c) 2013-2016 Mellanox Technologies, Ltd.
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice unmodified, this list of conditions, and the following
13  *    disclaimer.
14  * 2. Redistributions in binary form must reproduce the above copyright
15  *    notice, this list of conditions and the following disclaimer in the
16  *    documentation and/or other materials provided with the distribution.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  *
29  * $FreeBSD$
30  */
31 #ifndef _LINUX_LIST_H_
32 #define _LINUX_LIST_H_
33 
34 /*
35  * Since LIST_HEAD conflicts with the linux definition we must include any
36  * FreeBSD header which requires it here so it is resolved with the correct
37  * definition prior to the undef.
38  */
39 #include <linux/types.h>
40 
41 #include <sys/param.h>
42 #include <sys/kernel.h>
43 #include <sys/queue.h>
44 #include <sys/cpuset.h>
45 #include <sys/jail.h>
46 #include <sys/lock.h>
47 #include <sys/mutex.h>
48 #include <sys/proc.h>
49 #include <sys/vnode.h>
50 #include <sys/conf.h>
51 #include <sys/socket.h>
52 #include <sys/mbuf.h>
53 
54 #include <net/bpf.h>
55 #include <net/if.h>
56 #include <net/if_var.h>
57 #include <net/if_types.h>
58 #include <net/if_media.h>
59 #include <net/vnet.h>
60 
61 #include <netinet/in.h>
62 #include <netinet/in_pcb.h>
63 #include <netinet/in_var.h>
64 #include <netinet/tcp_lro.h>
65 
66 #include <netinet6/in6_var.h>
67 #include <netinet6/nd6.h>
68 
69 #include <vm/vm.h>
70 #include <vm/vm_object.h>
71 #include <vm/pmap.h>
72 
73 #ifndef prefetch
74 #define	prefetch(x)
75 #endif
76 
77 #define LINUX_LIST_HEAD_INIT(name) { &(name), &(name) }
78 
79 #define LINUX_LIST_HEAD(name) \
80 	struct list_head name = LINUX_LIST_HEAD_INIT(name)
81 
82 #ifndef LIST_HEAD_DEF
83 #define	LIST_HEAD_DEF
84 struct list_head {
85 	struct list_head *next;
86 	struct list_head *prev;
87 };
88 #endif
89 
90 static inline void
91 INIT_LIST_HEAD(struct list_head *list)
92 {
93 
94 	list->next = list->prev = list;
95 }
96 
97 static inline int
98 list_empty(const struct list_head *head)
99 {
100 
101 	return (head->next == head);
102 }
103 
104 static inline int
105 list_empty_careful(const struct list_head *head)
106 {
107 	struct list_head *next = head->next;
108 
109 	return ((next == head) && (next == head->prev));
110 }
111 
112 static inline void
113 __list_del(struct list_head *prev, struct list_head *next)
114 {
115 	next->prev = prev;
116 	WRITE_ONCE(prev->next, next);
117 }
118 
119 static inline void
120 __list_del_entry(struct list_head *entry)
121 {
122 
123 	__list_del(entry->prev, entry->next);
124 }
125 
126 static inline void
127 list_del(struct list_head *entry)
128 {
129 
130 	__list_del(entry->prev, entry->next);
131 }
132 
133 static inline void
134 list_replace(struct list_head *old, struct list_head *new)
135 {
136 	new->next = old->next;
137 	new->next->prev = new;
138 	new->prev = old->prev;
139 	new->prev->next = new;
140 }
141 
142 static inline void
143 list_replace_init(struct list_head *old, struct list_head *new)
144 {
145 	list_replace(old, new);
146 	INIT_LIST_HEAD(old);
147 }
148 
149 static inline void
150 linux_list_add(struct list_head *new, struct list_head *prev,
151     struct list_head *next)
152 {
153 
154 	next->prev = new;
155 	new->next = next;
156 	new->prev = prev;
157 	prev->next = new;
158 }
159 
160 static inline void
161 list_del_init(struct list_head *entry)
162 {
163 
164 	list_del(entry);
165 	INIT_LIST_HEAD(entry);
166 }
167 
168 #define	list_entry(ptr, type, field)	container_of(ptr, type, field)
169 
170 #define	list_first_entry(ptr, type, member) \
171 	list_entry((ptr)->next, type, member)
172 
173 #define	list_last_entry(ptr, type, member)	\
174 	list_entry((ptr)->prev, type, member)
175 
176 #define	list_first_entry_or_null(ptr, type, member) \
177 	(!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
178 
179 #define	list_next_entry(ptr, member)					\
180 	list_entry(((ptr)->member.next), typeof(*(ptr)), member)
181 
182 #define	list_safe_reset_next(ptr, n, member) \
183 	(n) = list_next_entry(ptr, member)
184 
185 #define	list_prev_entry(ptr, member)					\
186 	list_entry(((ptr)->member.prev), typeof(*(ptr)), member)
187 
188 #define	list_for_each(p, head)						\
189 	for (p = (head)->next; p != (head); p = (p)->next)
190 
191 #define	list_for_each_safe(p, n, head)					\
192 	for (p = (head)->next, n = (p)->next; p != (head); p = n, n = (p)->next)
193 
194 #define list_for_each_entry(p, h, field)				\
195 	for (p = list_entry((h)->next, typeof(*p), field); &(p)->field != (h); \
196 	    p = list_entry((p)->field.next, typeof(*p), field))
197 
198 #define list_for_each_entry_safe(p, n, h, field)			\
199 	for (p = list_entry((h)->next, typeof(*p), field),		\
200 	    n = list_entry((p)->field.next, typeof(*p), field); &(p)->field != (h);\
201 	    p = n, n = list_entry(n->field.next, typeof(*n), field))
202 
203 #define	list_for_each_entry_from(p, h, field) \
204 	for ( ; &(p)->field != (h); \
205 	    p = list_entry((p)->field.next, typeof(*p), field))
206 
207 #define	list_for_each_entry_continue(p, h, field)			\
208 	for (p = list_next_entry((p), field); &(p)->field != (h);	\
209 	    p = list_next_entry((p), field))
210 
211 #define	list_for_each_entry_safe_from(pos, n, head, member)			\
212 	for (n = list_entry((pos)->member.next, typeof(*pos), member);		\
213 	     &(pos)->member != (head);						\
214 	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
215 
216 #define	list_for_each_entry_reverse(p, h, field)			\
217 	for (p = list_entry((h)->prev, typeof(*p), field); &(p)->field != (h); \
218 	    p = list_entry((p)->field.prev, typeof(*p), field))
219 
220 #define	list_for_each_entry_safe_reverse(p, n, h, field)		\
221 	for (p = list_entry((h)->prev, typeof(*p), field),		\
222 	    n = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
223 	    p = n, n = list_entry(n->field.prev, typeof(*n), field))
224 
225 #define	list_for_each_entry_continue_reverse(p, h, field) \
226 	for (p = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
227 	    p = list_entry((p)->field.prev, typeof(*p), field))
228 
229 #define	list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = (p)->prev)
230 
231 #define	list_for_each_entry_from_reverse(p, h, field)	\
232 	for (; &p->field != (h);			\
233 	     p = list_prev_entry(p, field))
234 
235 static inline void
236 list_add(struct list_head *new, struct list_head *head)
237 {
238 
239 	linux_list_add(new, head, head->next);
240 }
241 
242 static inline void
243 list_add_tail(struct list_head *new, struct list_head *head)
244 {
245 
246 	linux_list_add(new, head->prev, head);
247 }
248 
249 static inline void
250 list_move(struct list_head *list, struct list_head *head)
251 {
252 
253 	list_del(list);
254 	list_add(list, head);
255 }
256 
257 static inline void
258 list_move_tail(struct list_head *entry, struct list_head *head)
259 {
260 
261 	list_del(entry);
262 	list_add_tail(entry, head);
263 }
264 
265 static inline void
266 list_bulk_move_tail(struct list_head *head, struct list_head *first,
267     struct list_head *last)
268 {
269 	first->prev->next = last->next;
270 	last->next->prev = first->prev;
271 	head->prev->next = first;
272 	first->prev = head->prev;
273 	last->next = head;
274 	head->prev = last;
275 }
276 
277 static inline void
278 linux_list_splice(const struct list_head *list, struct list_head *prev,
279     struct list_head *next)
280 {
281 	struct list_head *first;
282 	struct list_head *last;
283 
284 	if (list_empty(list))
285 		return;
286 	first = list->next;
287 	last = list->prev;
288 	first->prev = prev;
289 	prev->next = first;
290 	last->next = next;
291 	next->prev = last;
292 }
293 
294 static inline void
295 list_splice(const struct list_head *list, struct list_head *head)
296 {
297 
298 	linux_list_splice(list, head, head->next);
299 }
300 
301 static inline void
302 list_splice_tail(struct list_head *list, struct list_head *head)
303 {
304 
305 	linux_list_splice(list, head->prev, head);
306 }
307 
308 static inline void
309 list_splice_init(struct list_head *list, struct list_head *head)
310 {
311 
312 	linux_list_splice(list, head, head->next);
313 	INIT_LIST_HEAD(list);
314 }
315 
316 static inline void
317 list_splice_tail_init(struct list_head *list, struct list_head *head)
318 {
319 
320 	linux_list_splice(list, head->prev, head);
321 	INIT_LIST_HEAD(list);
322 }
323 
324 #undef LIST_HEAD
325 #define LIST_HEAD(name)	struct list_head name = { &(name), &(name) }
326 
327 
328 struct hlist_head {
329 	struct hlist_node *first;
330 };
331 
332 struct hlist_node {
333 	struct hlist_node *next, **pprev;
334 };
335 
336 #define	HLIST_HEAD_INIT { }
337 #define	HLIST_HEAD(name) struct hlist_head name = HLIST_HEAD_INIT
338 #define	INIT_HLIST_HEAD(head) (head)->first = NULL
339 #define	INIT_HLIST_NODE(node)						\
340 do {									\
341 	(node)->next = NULL;						\
342 	(node)->pprev = NULL;						\
343 } while (0)
344 
345 static inline int
346 hlist_unhashed(const struct hlist_node *h)
347 {
348 
349 	return !h->pprev;
350 }
351 
352 static inline int
353 hlist_empty(const struct hlist_head *h)
354 {
355 
356 	return !READ_ONCE(h->first);
357 }
358 
359 static inline void
360 hlist_del(struct hlist_node *n)
361 {
362 
363 	WRITE_ONCE(*(n->pprev), n->next);
364 	if (n->next != NULL)
365 		n->next->pprev = n->pprev;
366 }
367 
368 static inline void
369 hlist_del_init(struct hlist_node *n)
370 {
371 
372 	if (hlist_unhashed(n))
373 		return;
374 	hlist_del(n);
375 	INIT_HLIST_NODE(n);
376 }
377 
378 static inline void
379 hlist_add_head(struct hlist_node *n, struct hlist_head *h)
380 {
381 
382 	n->next = h->first;
383 	if (h->first != NULL)
384 		h->first->pprev = &n->next;
385 	WRITE_ONCE(h->first, n);
386 	n->pprev = &h->first;
387 }
388 
389 static inline void
390 hlist_add_before(struct hlist_node *n, struct hlist_node *next)
391 {
392 
393 	n->pprev = next->pprev;
394 	n->next = next;
395 	next->pprev = &n->next;
396 	WRITE_ONCE(*(n->pprev), n);
397 }
398 
399 static inline void
400 hlist_add_behind(struct hlist_node *n, struct hlist_node *prev)
401 {
402 
403 	n->next = prev->next;
404 	WRITE_ONCE(prev->next, n);
405 	n->pprev = &prev->next;
406 
407 	if (n->next != NULL)
408 		n->next->pprev = &n->next;
409 }
410 
411 static inline void
412 hlist_move_list(struct hlist_head *old, struct hlist_head *new)
413 {
414 
415 	new->first = old->first;
416 	if (new->first)
417 		new->first->pprev = &new->first;
418 	old->first = NULL;
419 }
420 
421 static inline int list_is_singular(const struct list_head *head)
422 {
423 	return !list_empty(head) && (head->next == head->prev);
424 }
425 
426 static inline void __list_cut_position(struct list_head *list,
427 		struct list_head *head, struct list_head *entry)
428 {
429 	struct list_head *new_first = entry->next;
430 	list->next = head->next;
431 	list->next->prev = list;
432 	list->prev = entry;
433 	entry->next = list;
434 	head->next = new_first;
435 	new_first->prev = head;
436 }
437 
438 static inline void list_cut_position(struct list_head *list,
439 		struct list_head *head, struct list_head *entry)
440 {
441 	if (list_empty(head))
442 		return;
443 	if (list_is_singular(head) &&
444 		(head->next != entry && head != entry))
445 		return;
446 	if (entry == head)
447 		INIT_LIST_HEAD(list);
448 	else
449 		__list_cut_position(list, head, entry);
450 }
451 
452 static inline int list_is_last(const struct list_head *list,
453 				const struct list_head *head)
454 {
455 	return list->next == head;
456 }
457 
458 #define	hlist_entry(ptr, type, field)	container_of(ptr, type, field)
459 
460 #define	hlist_for_each(p, head)						\
461 	for (p = (head)->first; p; p = (p)->next)
462 
463 #define	hlist_for_each_safe(p, n, head)					\
464 	for (p = (head)->first; p && ({ n = (p)->next; 1; }); p = n)
465 
466 #define	hlist_entry_safe(ptr, type, member) \
467 	((ptr) ? hlist_entry(ptr, type, member) : NULL)
468 
469 #define	hlist_for_each_entry(pos, head, member)				\
470 	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
471 	     pos;							\
472 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
473 
474 #define	hlist_for_each_entry_continue(pos, member)			\
475 	for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member); \
476 	     (pos);							\
477 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
478 
479 #define	hlist_for_each_entry_from(pos, member)				\
480 	for (; (pos);								\
481 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
482 
483 #define	hlist_for_each_entry_safe(pos, n, head, member)			\
484 	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \
485 	     (pos) && ({ n = (pos)->member.next; 1; });			\
486 	     pos = hlist_entry_safe(n, typeof(*(pos)), member))
487 
488 extern void list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv,
489     struct list_head *a, struct list_head *b));
490 
491 #endif /* _LINUX_LIST_H_ */
492