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 _LINUX_LIST_H_
  32 #define _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/if.h>
  57 #include <net/if_var.h>
  58 #include <net/if_types.h>
  59 #include <net/if_media.h>
  60 #include <net/vnet.h>
  61
  62 #include <netinet/in.h>
  63 #include <netinet/in_pcb.h>
  64 #include <netinet/in_var.h>
  65 #include <netinet/tcp_lro.h>
  66
  67 #include <netinet6/in6_var.h>
  68 #include <netinet6/nd6.h>
  69
  70 #include <vm/vm.h>
  71 #include <vm/vm_object.h>
  72 #include <vm/pmap.h>
  73 #endif
  74
  75 #ifndef prefetch
  76 #define prefetch(x)
  77 #endif
  78
  79 #define LINUX_LIST_HEAD_INIT(name) { &(name), &(name) }
  80
  81 #define LINUX_LIST_HEAD(name) \
  82         struct list_head name = LINUX_LIST_HEAD_INIT(name)
  83
  84 #ifndef LIST_HEAD_DEF
  85 #define LIST_HEAD_DEF
  86 struct list_head {
  87         struct list_head *next;
  88         struct list_head *prev;
  89 };
  90 #endif
  91
  92 static inline void
  93 INIT_LIST_HEAD(struct list_head *list)
  94 {
  95
  96         list->next = list->prev = list;
  97 }
  98
  99 static inline int
 100 list_empty(const struct list_head *head)
 101 {
 102
 103         return (head->next == head);
 104 }
 105
 106 static inline int
 107 list_empty_careful(const struct list_head *head)
 108 {
 109         struct list_head *next = head->next;
 110
 111         return ((next == head) && (next == head->prev));
 112 }
 113
 114 static inline void
 115 __list_del(struct list_head *prev, struct list_head *next)
 116 {
 117         next->prev = prev;
 118         WRITE_ONCE(prev->next, next);
 119 }
 120
 121 static inline void
 122 __list_del_entry(struct list_head *entry)
 123 {
 124
 125         __list_del(entry->prev, entry->next);
 126 }
 127
 128 static inline void
 129 list_del(struct list_head *entry)
 130 {
 131
 132         __list_del(entry->prev, entry->next);
 133 }
 134
 135 static inline void
 136 list_replace(struct list_head *old, struct list_head *new)
 137 {
 138         new->next = old->next;
 139         new->next->prev = new;
 140         new->prev = old->prev;
 141         new->prev->next = new;
 142 }
 143
 144 static inline void
 145 list_replace_init(struct list_head *old, struct list_head *new)
 146 {
 147         list_replace(old, new);
 148         INIT_LIST_HEAD(old);
 149 }
 150
 151 static inline void
 152 linux_list_add(struct list_head *new, struct list_head *prev,
 153     struct list_head *next)
 154 {
 155
 156         next->prev = new;
 157         new->next = next;
 158         new->prev = prev;
 159         prev->next = new;
 160 }
 161
 162 static inline void
 163 list_del_init(struct list_head *entry)
 164 {
 165
 166         list_del(entry);
 167         INIT_LIST_HEAD(entry);
 168 }
 169
 170 #define list_entry(ptr, type, field)    container_of(ptr, type, field)
 171
 172 #define list_first_entry(ptr, type, member) \
 173         list_entry((ptr)->next, type, member)
 174
 175 #define list_last_entry(ptr, type, member)      \
 176         list_entry((ptr)->prev, type, member)
 177
 178 #define list_first_entry_or_null(ptr, type, member) \
 179         (!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
 180
 181 #define list_next_entry(ptr, member)                                    \
 182         list_entry(((ptr)->member.next), typeof(*(ptr)), member)
 183
 184 #define list_safe_reset_next(ptr, n, member) \
 185         (n) = list_next_entry(ptr, member)
 186
 187 #define list_prev_entry(ptr, member)                                    \
 188         list_entry(((ptr)->member.prev), typeof(*(ptr)), member)
 189
 190 #define list_for_each(p, head)                                          \
 191         for (p = (head)->next; p != (head); p = (p)->next)
 192
 193 #define list_for_each_safe(p, n, head)                                  \
 194         for (p = (head)->next, n = (p)->next; p != (head); p = n, n = (p)->next)
 195
 196 #define list_for_each_entry(p, h, field)                                \
 197         for (p = list_entry((h)->next, typeof(*p), field); &(p)->field != (h); \
 198             p = list_entry((p)->field.next, typeof(*p), field))
 199
 200 #define list_for_each_entry_safe(p, n, h, field)                        \
 201         for (p = list_entry((h)->next, typeof(*p), field),              \
 202             n = list_entry((p)->field.next, typeof(*p), field); &(p)->field != (h);\
 203             p = n, n = list_entry(n->field.next, typeof(*n), field))
 204
 205 #define list_for_each_entry_from(p, h, field) \
 206         for ( ; &(p)->field != (h); \
 207             p = list_entry((p)->field.next, typeof(*p), field))
 208
 209 #define list_for_each_entry_continue(p, h, field)                       \
 210         for (p = list_next_entry((p), field); &(p)->field != (h);       \
 211             p = list_next_entry((p), field))
 212
 213 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
 214         for (n = list_entry((pos)->member.next, typeof(*pos), member);          \
 215              &(pos)->member != (head);                                          \
 216              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 217
 218 #define list_for_each_entry_reverse(p, h, field)                        \
 219         for (p = list_entry((h)->prev, typeof(*p), field); &(p)->field != (h); \
 220             p = list_entry((p)->field.prev, typeof(*p), field))
 221
 222 #define list_for_each_entry_safe_reverse(p, n, h, field)                \
 223         for (p = list_entry((h)->prev, typeof(*p), field),              \
 224             n = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
 225             p = n, n = list_entry(n->field.prev, typeof(*n), field))
 226
 227 #define list_for_each_entry_continue_reverse(p, h, field) \
 228         for (p = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
 229             p = list_entry((p)->field.prev, typeof(*p), field))
 230
 231 #define list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = (p)->prev)
 232
 233 #define list_for_each_entry_from_reverse(p, h, field)   \
 234         for (; &p->field != (h);                        \
 235              p = list_prev_entry(p, field))
 236
 237 static inline void
 238 list_add(struct list_head *new, struct list_head *head)
 239 {
 240
 241         linux_list_add(new, head, head->next);
 242 }
 243
 244 static inline void
 245 list_add_tail(struct list_head *new, struct list_head *head)
 246 {
 247
 248         linux_list_add(new, head->prev, head);
 249 }
 250
 251 static inline void
 252 list_move(struct list_head *list, struct list_head *head)
 253 {
 254
 255         list_del(list);
 256         list_add(list, head);
 257 }
 258
 259 static inline void
 260 list_move_tail(struct list_head *entry, struct list_head *head)
 261 {
 262
 263         list_del(entry);
 264         list_add_tail(entry, head);
 265 }
 266
 267 static inline void
 268 list_bulk_move_tail(struct list_head *head, struct list_head *first,
 269     struct list_head *last)
 270 {
 271         first->prev->next = last->next;
 272         last->next->prev = first->prev;
 273         head->prev->next = first;
 274         first->prev = head->prev;
 275         last->next = head;
 276         head->prev = last;
 277 }
 278
 279 static inline void
 280 linux_list_splice(const struct list_head *list, struct list_head *prev,
 281     struct list_head *next)
 282 {
 283         struct list_head *first;
 284         struct list_head *last;
 285
 286         if (list_empty(list))
 287                 return;
 288         first = list->next;
 289         last = list->prev;
 290         first->prev = prev;
 291         prev->next = first;
 292         last->next = next;
 293         next->prev = last;
 294 }
 295
 296 static inline void
 297 list_splice(const struct list_head *list, struct list_head *head)
 298 {
 299
 300         linux_list_splice(list, head, head->next);
 301 }
 302
 303 static inline void
 304 list_splice_tail(struct list_head *list, struct list_head *head)
 305 {
 306
 307         linux_list_splice(list, head->prev, head);
 308 }
 309
 310 static inline void
 311 list_splice_init(struct list_head *list, struct list_head *head)
 312 {
 313
 314         linux_list_splice(list, head, head->next);
 315         INIT_LIST_HEAD(list);
 316 }
 317
 318 static inline void
 319 list_splice_tail_init(struct list_head *list, struct list_head *head)
 320 {
 321
 322         linux_list_splice(list, head->prev, head);
 323         INIT_LIST_HEAD(list);
 324 }
 325
 326 #undef LIST_HEAD
 327 #define LIST_HEAD(name) struct list_head name = { &(name), &(name) }
 328
 329 struct hlist_head {
 330         struct hlist_node *first;
 331 };
 332
 333 struct hlist_node {
 334         struct hlist_node *next, **pprev;
 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_first(const struct list_head *list,
 453                                 const struct list_head *head)
 454 {
 455
 456         return (list->prev == head);
 457 }
 458
 459 static inline int list_is_last(const struct list_head *list,
 460                                 const struct list_head *head)
 461 {
 462         return list->next == head;
 463 }
 464
 465 #define hlist_entry(ptr, type, field)   container_of(ptr, type, field)
 466
 467 #define hlist_for_each(p, head)                                         \
 468         for (p = (head)->first; p; p = (p)->next)
 469
 470 #define hlist_for_each_safe(p, n, head)                                 \
 471         for (p = (head)->first; p && ({ n = (p)->next; 1; }); p = n)
 472
 473 #define hlist_entry_safe(ptr, type, member) \
 474         ((ptr) ? hlist_entry(ptr, type, member) : NULL)
 475
 476 #define hlist_for_each_entry(pos, head, member)                         \
 477         for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
 478              pos;                                                       \
 479              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 480
 481 #define hlist_for_each_entry_continue(pos, member)                      \
 482         for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member); \
 483              (pos);                                                     \
 484              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 485
 486 #define hlist_for_each_entry_from(pos, member)                          \
 487         for (; (pos);                                                           \
 488              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
 489
 490 #define hlist_for_each_entry_safe(pos, n, head, member)                 \
 491         for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \
 492              (pos) && ({ n = (pos)->member.next; 1; });                 \
 493              pos = hlist_entry_safe(n, typeof(*(pos)), member))
 494
 495 extern void list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv,
 496     struct list_head *a, struct list_head *b));
 497
 498 #endif /* _LINUX_LIST_H_ */