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 #define	prefetch(x)
74 
75 #define LINUX_LIST_HEAD_INIT(name) { &(name), &(name) }
76 
77 #define LINUX_LIST_HEAD(name) \
78 	struct list_head name = LINUX_LIST_HEAD_INIT(name)
79 
80 #ifndef LIST_HEAD_DEF
81 #define	LIST_HEAD_DEF
82 struct list_head {
83 	struct list_head *next;
84 	struct list_head *prev;
85 };
86 #endif
87 
88 static inline void
89 INIT_LIST_HEAD(struct list_head *list)
90 {
91 
92 	list->next = list->prev = list;
93 }
94 
95 static inline int
96 list_empty(const struct list_head *head)
97 {
98 
99 	return (head->next == head);
100 }
101 
102 static inline int
103 list_empty_careful(const struct list_head *head)
104 {
105 	struct list_head *next = head->next;
106 
107 	return ((next == head) && (next == head->prev));
108 }
109 
110 static inline void
111 __list_del(struct list_head *prev, struct list_head *next)
112 {
113 	next->prev = prev;
114 	WRITE_ONCE(prev->next, next);
115 }
116 
117 static inline void
118 list_del(struct list_head *entry)
119 {
120 
121 	__list_del(entry->prev, entry->next);
122 }
123 
124 static inline void
125 list_replace(struct list_head *old, struct list_head *new)
126 {
127 	new->next = old->next;
128 	new->next->prev = new;
129 	new->prev = old->prev;
130 	new->prev->next = new;
131 }
132 
133 static inline void
134 list_replace_init(struct list_head *old, struct list_head *new)
135 {
136 	list_replace(old, new);
137 	INIT_LIST_HEAD(old);
138 }
139 
140 static inline void
141 linux_list_add(struct list_head *new, struct list_head *prev,
142     struct list_head *next)
143 {
144 
145 	next->prev = new;
146 	new->next = next;
147 	new->prev = prev;
148 	prev->next = new;
149 }
150 
151 static inline void
152 list_del_init(struct list_head *entry)
153 {
154 
155 	list_del(entry);
156 	INIT_LIST_HEAD(entry);
157 }
158 
159 #define	list_entry(ptr, type, field)	container_of(ptr, type, field)
160 
161 #define list_first_entry(ptr, type, member) \
162         list_entry((ptr)->next, type, member)
163 
164 #define	list_last_entry(ptr, type, member)	\
165 	list_entry((ptr)->prev, type, member)
166 
167 #define	list_first_entry_or_null(ptr, type, member) \
168 	(!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
169 
170 #define	list_next_entry(ptr, member)					\
171 	list_entry(((ptr)->member.next), typeof(*(ptr)), member)
172 
173 #define	list_prev_entry(ptr, member)					\
174 	list_entry(((ptr)->member.prev), typeof(*(ptr)), member)
175 
176 #define	list_for_each(p, head)						\
177 	for (p = (head)->next; p != (head); p = (p)->next)
178 
179 #define	list_for_each_safe(p, n, head)					\
180 	for (p = (head)->next, n = (p)->next; p != (head); p = n, n = (p)->next)
181 
182 #define list_for_each_entry(p, h, field)				\
183 	for (p = list_entry((h)->next, typeof(*p), field); &(p)->field != (h); \
184 	    p = list_entry((p)->field.next, typeof(*p), field))
185 
186 #define list_for_each_entry_safe(p, n, h, field)			\
187 	for (p = list_entry((h)->next, typeof(*p), field), 		\
188 	    n = list_entry((p)->field.next, typeof(*p), field); &(p)->field != (h);\
189 	    p = n, n = list_entry(n->field.next, typeof(*n), field))
190 
191 #define	list_for_each_entry_from(p, h, field) \
192 	for ( ; &(p)->field != (h); \
193 	    p = list_entry((p)->field.next, typeof(*p), field))
194 
195 #define	list_for_each_entry_continue(p, h, field)			\
196 	for (p = list_next_entry((p), field); &(p)->field != (h);	\
197 	    p = list_next_entry((p), field))
198 
199 #define	list_for_each_entry_safe_from(pos, n, head, member) 			\
200 	for (n = list_entry((pos)->member.next, typeof(*pos), member);		\
201 	     &(pos)->member != (head);						\
202 	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
203 
204 #define	list_for_each_entry_reverse(p, h, field)			\
205 	for (p = list_entry((h)->prev, typeof(*p), field); &(p)->field != (h); \
206 	    p = list_entry((p)->field.prev, typeof(*p), field))
207 
208 #define	list_for_each_entry_safe_reverse(p, n, h, field)		\
209 	for (p = list_entry((h)->prev, typeof(*p), field), 		\
210 	    n = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
211 	    p = n, n = list_entry(n->field.prev, typeof(*n), field))
212 
213 #define	list_for_each_entry_continue_reverse(p, h, field) \
214 	for (p = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
215 	    p = list_entry((p)->field.prev, typeof(*p), field))
216 
217 #define	list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = (p)->prev)
218 
219 static inline void
220 list_add(struct list_head *new, struct list_head *head)
221 {
222 
223 	linux_list_add(new, head, head->next);
224 }
225 
226 static inline void
227 list_add_tail(struct list_head *new, struct list_head *head)
228 {
229 
230 	linux_list_add(new, head->prev, head);
231 }
232 
233 static inline void
234 list_move(struct list_head *list, struct list_head *head)
235 {
236 
237 	list_del(list);
238 	list_add(list, head);
239 }
240 
241 static inline void
242 list_move_tail(struct list_head *entry, struct list_head *head)
243 {
244 
245 	list_del(entry);
246 	list_add_tail(entry, head);
247 }
248 
249 static inline void
250 linux_list_splice(const struct list_head *list, struct list_head *prev,
251     struct list_head *next)
252 {
253 	struct list_head *first;
254 	struct list_head *last;
255 
256 	if (list_empty(list))
257 		return;
258 	first = list->next;
259 	last = list->prev;
260 	first->prev = prev;
261 	prev->next = first;
262 	last->next = next;
263 	next->prev = last;
264 }
265 
266 static inline void
267 list_splice(const struct list_head *list, struct list_head *head)
268 {
269 
270 	linux_list_splice(list, head, head->next);
271 }
272 
273 static inline void
274 list_splice_tail(struct list_head *list, struct list_head *head)
275 {
276 
277 	linux_list_splice(list, head->prev, head);
278 }
279 
280 static inline void
281 list_splice_init(struct list_head *list, struct list_head *head)
282 {
283 
284 	linux_list_splice(list, head, head->next);
285 	INIT_LIST_HEAD(list);
286 }
287 
288 static inline void
289 list_splice_tail_init(struct list_head *list, struct list_head *head)
290 {
291 
292 	linux_list_splice(list, head->prev, head);
293 	INIT_LIST_HEAD(list);
294 }
295 
296 #undef LIST_HEAD
297 #define LIST_HEAD(name)	struct list_head name = { &(name), &(name) }
298 
299 
300 struct hlist_head {
301 	struct hlist_node *first;
302 };
303 
304 struct hlist_node {
305 	struct hlist_node *next, **pprev;
306 };
307 
308 #define	HLIST_HEAD_INIT { }
309 #define	HLIST_HEAD(name) struct hlist_head name = HLIST_HEAD_INIT
310 #define	INIT_HLIST_HEAD(head) (head)->first = NULL
311 #define	INIT_HLIST_NODE(node)						\
312 do {									\
313 	(node)->next = NULL;						\
314 	(node)->pprev = NULL;						\
315 } while (0)
316 
317 static inline int
318 hlist_unhashed(const struct hlist_node *h)
319 {
320 
321 	return !h->pprev;
322 }
323 
324 static inline int
325 hlist_empty(const struct hlist_head *h)
326 {
327 
328 	return !h->first;
329 }
330 
331 static inline void
332 hlist_del(struct hlist_node *n)
333 {
334 
335         if (n->next)
336                 n->next->pprev = n->pprev;
337         *n->pprev = n->next;
338 }
339 
340 static inline void
341 hlist_del_init(struct hlist_node *n)
342 {
343 
344 	if (hlist_unhashed(n))
345 		return;
346 	hlist_del(n);
347 	INIT_HLIST_NODE(n);
348 }
349 
350 static inline void
351 hlist_add_head(struct hlist_node *n, struct hlist_head *h)
352 {
353 
354 	n->next = h->first;
355 	if (h->first)
356 		h->first->pprev = &n->next;
357 	h->first = n;
358 	n->pprev = &h->first;
359 }
360 
361 static inline void
362 hlist_add_before(struct hlist_node *n, struct hlist_node *next)
363 {
364 
365 	n->pprev = next->pprev;
366 	n->next = next;
367 	next->pprev = &n->next;
368 	*(n->pprev) = n;
369 }
370 
371 static inline void
372 hlist_add_after(struct hlist_node *n, struct hlist_node *next)
373 {
374 
375 	next->next = n->next;
376 	n->next = next;
377 	next->pprev = &n->next;
378 	if (next->next)
379 		next->next->pprev = &next->next;
380 }
381 
382 static inline void
383 hlist_move_list(struct hlist_head *old, struct hlist_head *new)
384 {
385 
386 	new->first = old->first;
387 	if (new->first)
388 		new->first->pprev = &new->first;
389 	old->first = NULL;
390 }
391 
392 /**
393  * list_is_singular - tests whether a list has just one entry.
394  * @head: the list to test.
395  */
396 static inline int list_is_singular(const struct list_head *head)
397 {
398 	return !list_empty(head) && (head->next == head->prev);
399 }
400 
401 static inline void __list_cut_position(struct list_head *list,
402 		struct list_head *head, struct list_head *entry)
403 {
404 	struct list_head *new_first = entry->next;
405 	list->next = head->next;
406 	list->next->prev = list;
407 	list->prev = entry;
408 	entry->next = list;
409 	head->next = new_first;
410 	new_first->prev = head;
411 }
412 
413 /**
414  * list_cut_position - cut a list into two
415  * @list: a new list to add all removed entries
416  * @head: a list with entries
417  * @entry: an entry within head, could be the head itself
418  *	and if so we won't cut the list
419  *
420  * This helper moves the initial part of @head, up to and
421  * including @entry, from @head to @list. You should
422  * pass on @entry an element you know is on @head. @list
423  * should be an empty list or a list you do not care about
424  * losing its data.
425  *
426  */
427 static inline void list_cut_position(struct list_head *list,
428 		struct list_head *head, struct list_head *entry)
429 {
430 	if (list_empty(head))
431 		return;
432 	if (list_is_singular(head) &&
433 		(head->next != entry && head != entry))
434 		return;
435 	if (entry == head)
436 		INIT_LIST_HEAD(list);
437 	else
438 		__list_cut_position(list, head, entry);
439 }
440 
441 /**
442  *  list_is_last - tests whether @list is the last entry in list @head
443  *   @list: the entry to test
444  *    @head: the head of the list
445  */
446 static inline int list_is_last(const struct list_head *list,
447                                 const struct list_head *head)
448 {
449         return list->next == head;
450 }
451 
452 #define	hlist_entry(ptr, type, field)	container_of(ptr, type, field)
453 
454 #define	hlist_for_each(p, head)						\
455 	for (p = (head)->first; p; p = (p)->next)
456 
457 #define	hlist_for_each_safe(p, n, head)					\
458 	for (p = (head)->first; p && ({ n = (p)->next; 1; }); p = n)
459 
460 #define	hlist_entry_safe(ptr, type, member) \
461 	((ptr) ? hlist_entry(ptr, type, member) : NULL)
462 
463 #define	hlist_for_each_entry(pos, head, member)				\
464 	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
465 	     pos;							\
466 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
467 
468 #define	hlist_for_each_entry_continue(pos, member)			\
469 	for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member); \
470 	     (pos);							\
471 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
472 
473 #define	hlist_for_each_entry_from(pos, member)				\
474 	for (; (pos);								\
475 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
476 
477 #define	hlist_for_each_entry_safe(pos, n, head, member)			\
478 	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \
479 	     (pos) && ({ n = (pos)->member.next; 1; });			\
480 	     pos = hlist_entry_safe(n, typeof(*(pos)), member))
481 
482 extern void list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv,
483     struct list_head *a, struct list_head *b));
484 
485 #endif /* _LINUX_LIST_H_ */
486