sys/compat/linuxkpi/common/include/linux/list.h

   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 _LINUXKPI_LINUX_LIST_H_
  32 #define _LINUXKPI_LINUX_LIST_H_
  33
  34 #ifndef _STANDALONE
  35 /*
  36  * Since LIST_HEAD conflicts with the Linux definition we must include any
  37  * FreeBSD header which requires it here so it is resolved with the correct
  38  * definition prior to the undef.
  39  */
  40 #include <linux/types.h>
  41
  42 #include <sys/param.h>
  43 #include <sys/kernel.h>
  44 #include <sys/queue.h>
  45 #include <sys/cpuset.h>
  46 #include <sys/jail.h>
  47 #include <sys/lock.h>
  48 #include <sys/mutex.h>
  49 #include <sys/proc.h>
  50 #include <sys/vnode.h>
  51 #include <sys/conf.h>
  52 #include <sys/socket.h>
  53 #include <sys/mbuf.h>
  54
  55 #include <net/bpf.h>
  56 #include <net/ethernet.h>
  57 #include <net/if.h>
  58 #include <net/if_var.h>
  59 #include <net/if_types.h>
  60 #include <net/if_media.h>
  61 #include <net/vnet.h>
  62
  63 #include <netinet/in.h>
  64 #include <netinet/in_pcb.h>
  65 #include <netinet/in_var.h>
  66 #include <netinet/tcp_lro.h>
  67
  68 #include <netinet6/in6_var.h>
  69 #include <netinet6/nd6.h>
  70
  71 #include <net80211/ieee80211.h>
  72 #include <net80211/ieee80211_var.h>
  73 #include <net80211/ieee80211_node.h>
  74
  75 #include <vm/vm.h>
  76 #include <vm/vm_object.h>
  77 #include <vm/pmap.h>
  78 #endif
  79
  80 #ifndef prefetch
  81 #define prefetch(x)
  82 #endif
  83
  84 #define LINUX_LIST_HEAD_INIT(name) { &(name), &(name) }
  85
  86 #define LINUX_LIST_HEAD(name) \
  87         struct list_head name = LINUX_LIST_HEAD_INIT(name)
  88
  89 #ifndef LIST_HEAD_DEF
  90 #define LIST_HEAD_DEF
  91 struct list_head {
  92         struct list_head *next;
  93         struct list_head *prev;
  94 };
  95 #endif
  96
  97 static inline void
  98 INIT_LIST_HEAD(struct list_head *list)
  99 {
 100
 101         list->next = list->prev = list;
 102 }
 103
 104 static inline int
 105 list_empty(const struct list_head *head)
 106 {
 107
 108         return (head->next == head);
 109 }
 110
 111 static inline int
 112 list_empty_careful(const struct list_head *head)
 113 {
 114         struct list_head *next = head->next;
 115
 116         return ((next == head) && (next == head->prev));
 117 }
 118
 119 static inline void
 120 __list_del(struct list_head *prev, struct list_head *next)
 121 {
 122         next->prev = prev;
 123         WRITE_ONCE(prev->next, next);
 124 }
 125
 126 static inline void
 127 __list_del_entry(struct list_head *entry)
 128 {
 129
 130         __list_del(entry->prev, entry->next);
 131 }
 132
 133 static inline void
 134 list_del(struct list_head *entry)
 135 {
 136
 137         __list_del(entry->prev, entry->next);
 138 }
 139
 140 static inline void
 141 list_replace(struct list_head *old, struct list_head *new)
 142 {
 143         new->next = old->next;
 144         new->next->prev = new;
 145         new->prev = old->prev;
 146         new->prev->next = new;
 147 }
 148
 149 static inline void
 150 list_replace_init(struct list_head *old, struct list_head *new)
 151 {
 152         list_replace(old, new);
 153         INIT_LIST_HEAD(old);
 154 }
 155
 156 static inline void
 157 linux_list_add(struct list_head *new, struct list_head *prev,
 158     struct list_head *next)
 159 {
 160
 161         next->prev = new;
 162         new->next = next;
 163         new->prev = prev;
 164         prev->next = new;
 165 }
 166
 167 static inline void
 168 list_del_init(struct list_head *entry)
 169 {
 170
 171         list_del(entry);
 172         INIT_LIST_HEAD(entry);
 173 }
 174
 175 #define list_entry(ptr, type, field)    container_of(ptr, type, field)
 176
 177 #define list_first_entry(ptr, type, member) \
 178         list_entry((ptr)->next, type, member)
 179
 180 #define list_last_entry(ptr, type, member)      \
 181         list_entry((ptr)->prev, type, member)
 182
 183 #define list_first_entry_or_null(ptr, type, member) \
 184         (!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
 185
 186 #define list_next_entry(ptr, member)                                    \
 187         list_entry(((ptr)->member.next), typeof(*(ptr)), member)
 188
 189 #define list_safe_reset_next(ptr, n, member) \
 190         (n) = list_next_entry(ptr, member)
 191
 192 #define list_prev_entry(ptr, member)                                    \
 193         list_entry(((ptr)->member.prev), typeof(*(ptr)), member)
 194
 195 #define list_for_each(p, head)                                          \
 196         for (p = (head)->next; p != (head); p = (p)->next)
 197
 198 #define list_for_each_safe(p, n, head)                                  \
 199         for (p = (head)->next, n = (p)->next; p != (head); p = n, n = (p)->next)
 200
 201 #define list_for_each_entry(p, h, field)                                \
 202         for (p = list_entry((h)->next, typeof(*p), field); &(p)->field != (h); \
 203             p = list_entry((p)->field.next, typeof(*p), field))
 204
 205 #define list_for_each_entry_safe(p, n, h, field)                        \
 206         for (p = list_entry((h)->next, typeof(*p), field),              \
 207             n = list_entry((p)->field.next, typeof(*p), field); &(p)->field != (h);\
 208             p = n, n = list_entry(n->field.next, typeof(*n), field))
 209
 210 #define list_for_each_entry_from(p, h, field) \
 211         for ( ; &(p)->field != (h); \
 212             p = list_entry((p)->field.next, typeof(*p), field))
 213
 214 #define list_for_each_entry_continue(p, h, field)                       \
 215         for (p = list_next_entry((p), field); &(p)->field != (h);       \
 216             p = list_next_entry((p), field))
 217
 218 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
 219         for (n = list_entry((pos)->member.next, typeof(*pos), member);          \
 220              &(pos)->member != (head);                                          \
 221              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 222
 223 #define list_for_each_entry_reverse(p, h, field)                        \
 224         for (p = list_entry((h)->prev, typeof(*p), field); &(p)->field != (h); \
 225             p = list_entry((p)->field.prev, typeof(*p), field))
 226
 227 #define list_for_each_entry_safe_reverse(p, n, h, field)                \
 228         for (p = list_entry((h)->prev, typeof(*p), field),              \
 229             n = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
 230             p = n, n = list_entry(n->field.prev, typeof(*n), field))
 231
 232 #define list_for_each_entry_continue_reverse(p, h, field) \
 233         for (p = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
 234             p = list_entry((p)->field.prev, typeof(*p), field))
 235
 236 #define list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = (p)->prev)
 237
 238 #define list_for_each_entry_from_reverse(p, h, field)   \
 239         for (; &p->field != (h);                        \
 240              p = list_prev_entry(p, field))
 241
 242 static inline void
 243 list_add(struct list_head *new, struct list_head *head)
 244 {
 245
 246         linux_list_add(new, head, head->next);
 247 }
 248
 249 static inline void
 250 list_add_tail(struct list_head *new, struct list_head *head)
 251 {
 252
 253         linux_list_add(new, head->prev, head);
 254 }
 255
 256 static inline void
 257 list_move(struct list_head *list, struct list_head *head)
 258 {
 259
 260         list_del(list);
 261         list_add(list, head);
 262 }
 263
 264 static inline void
 265 list_move_tail(struct list_head *entry, struct list_head *head)
 266 {
 267
 268         list_del(entry);
 269         list_add_tail(entry, head);
 270 }
 271
 272 static inline void
 273 list_bulk_move_tail(struct list_head *head, struct list_head *first,
 274     struct list_head *last)
 275 {
 276         first->prev->next = last->next;
 277         last->next->prev = first->prev;
 278         head->prev->next = first;
 279         first->prev = head->prev;
 280         last->next = head;
 281         head->prev = last;
 282 }
 283
 284 static inline void
 285 linux_list_splice(const struct list_head *list, struct list_head *prev,
 286     struct list_head *next)
 287 {
 288         struct list_head *first;
 289         struct list_head *last;
 290
 291         if (list_empty(list))
 292                 return;
 293         first = list->next;
 294         last = list->prev;
 295         first->prev = prev;
 296         prev->next = first;
 297         last->next = next;
 298         next->prev = last;
 299 }
 300
 301 static inline void
 302 list_splice(const struct list_head *list, struct list_head *head)
 303 {
 304
 305         linux_list_splice(list, head, head->next);
 306 }
 307
 308 static inline void
 309 list_splice_tail(struct list_head *list, struct list_head *head)
 310 {
 311
 312         linux_list_splice(list, head->prev, head);
 313 }
 314
 315 static inline void
 316 list_splice_init(struct list_head *list, struct list_head *head)
 317 {
 318
 319         linux_list_splice(list, head, head->next);
 320         INIT_LIST_HEAD(list);
 321 }
 322
 323 static inline void
 324 list_splice_tail_init(struct list_head *list, struct list_head *head)
 325 {
 326
 327         linux_list_splice(list, head->prev, head);
 328         INIT_LIST_HEAD(list);
 329 }
 330
 331 #undef LIST_HEAD
 332 #define LIST_HEAD(name) struct list_head name = { &(name), &(name) }
 333
 334 struct hlist_head {
 335         struct hlist_node *first;
 336 };
 337
 338 struct hlist_node {
 339         struct hlist_node *next, **pprev;
 340 };
 341 #define HLIST_HEAD_INIT { }
 342 #define HLIST_HEAD(name) struct hlist_head name = HLIST_HEAD_INIT
 343 #define INIT_HLIST_HEAD(head) (head)->first = NULL
 344 #define INIT_HLIST_NODE(node)                                           \
 345 do {                                                                    \
 346         (node)->next = NULL;                                            \
 347         (node)->pprev = NULL;                                           \
 348 } while (0)
 349
 350 static inline int
 351 hlist_unhashed(const struct hlist_node *h)
 352 {
 353
 354         return !h->pprev;
 355 }
 356
 357 static inline int
 358 hlist_empty(const struct hlist_head *h)
 359 {
 360
 361         return !READ_ONCE(h->first);
 362 }
 363
 364 static inline void
 365 hlist_del(struct hlist_node *n)
 366 {
 367
 368         WRITE_ONCE(*(n->pprev), n->next);
 369         if (n->next != NULL)
 370                 n->next->pprev = n->pprev;
 371 }
 372
 373 static inline void
 374 hlist_del_init(struct hlist_node *n)
 375 {
 376
 377         if (hlist_unhashed(n))
 378                 return;
 379         hlist_del(n);
 380         INIT_HLIST_NODE(n);
 381 }
 382
 383 static inline void
 384 hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 385 {
 386
 387         n->next = h->first;
 388         if (h->first != NULL)
 389                 h->first->pprev = &n->next;
 390         WRITE_ONCE(h->first, n);
 391         n->pprev = &h->first;
 392 }
 393
 394 static inline void
 395 hlist_add_before(struct hlist_node *n, struct hlist_node *next)
 396 {
 397
 398         n->pprev = next->pprev;
 399         n->next = next;
 400         next->pprev = &n->next;
 401         WRITE_ONCE(*(n->pprev), n);
 402 }
 403
 404 static inline void
 405 hlist_add_behind(struct hlist_node *n, struct hlist_node *prev)
 406 {
 407
 408         n->next = prev->next;
 409         WRITE_ONCE(prev->next, n);
 410         n->pprev = &prev->next;
 411
 412         if (n->next != NULL)
 413                 n->next->pprev = &n->next;
 414 }
 415
 416 static inline void
 417 hlist_move_list(struct hlist_head *old, struct hlist_head *new)
 418 {
 419
 420         new->first = old->first;
 421         if (new->first)
 422                 new->first->pprev = &new->first;
 423         old->first = NULL;
 424 }
 425
 426 static inline int list_is_singular(const struct list_head *head)
 427 {
 428         return !list_empty(head) && (head->next == head->prev);
 429 }
 430
 431 static inline void __list_cut_position(struct list_head *list,
 432                 struct list_head *head, struct list_head *entry)
 433 {
 434         struct list_head *new_first = entry->next;
 435         list->next = head->next;
 436         list->next->prev = list;
 437         list->prev = entry;
 438         entry->next = list;
 439         head->next = new_first;
 440         new_first->prev = head;
 441 }
 442
 443 static inline void list_cut_position(struct list_head *list,
 444                 struct list_head *head, struct list_head *entry)
 445 {
 446         if (list_empty(head))
 447                 return;
 448         if (list_is_singular(head) &&
 449                 (head->next != entry && head != entry))
 450                 return;
 451         if (entry == head)
 452                 INIT_LIST_HEAD(list);
 453         else
 454                 __list_cut_position(list, head, entry);
 455 }
 456
 457 static inline int list_is_first(const struct list_head *list,
 458                                 const struct list_head *head)
 459 {
 460
 461         return (list->prev == head);
 462 }
 463
 464 static inline int list_is_last(const struct list_head *list,
 465                                 const struct list_head *head)
 466 {
 467         return list->next == head;
 468 }
 469
 470 #define hlist_entry(ptr, type, field)   container_of(ptr, type, field)
 471
 472 #define hlist_for_each(p, head)                                         \
 473         for (p = (head)->first; p; p = (p)->next)
 474
 475 #define hlist_for_each_safe(p, n, head)                                 \
 476         for (p = (head)->first; p && ({ n = (p)->next; 1; }); p = n)
 477
 478 #define hlist_entry_safe(ptr, type, member) \
 479         ((ptr) ? hlist_entry(ptr, type, member) : NULL)
 480
 481 #define hlist_for_each_entry(pos, head, member)                         \
 482         for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
 483              pos;                                                       \
 484              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 485
 486 #define hlist_for_each_entry_continue(pos, member)                      \
 487         for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member); \
 488              (pos);                                                     \
 489              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 490
 491 #define hlist_for_each_entry_from(pos, member)                          \
 492         for (; (pos);                                                           \
 493              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 494
 495 #define hlist_for_each_entry_safe(pos, n, head, member)                 \
 496         for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \
 497              (pos) && ({ n = (pos)->member.next; 1; });                 \
 498              pos = hlist_entry_safe(n, typeof(*(pos)), member))
 499
 500 extern void list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv,
 501     struct list_head *a, struct list_head *b));
 502
 503 #endif /* _LINUXKPI_LINUX_LIST_H_ */