Line data    Source code

       1             : /* SPDX-License-Identifier: GPL-2.0 */
       2             : #ifndef _LINUX_LIST_NULLS_H
       3             : #define _LINUX_LIST_NULLS_H
       4             : 
       5             : #include <linux/poison.h>
       6             : #include <linux/const.h>
       7             : 
       8             : /*
       9             :  * Special version of lists, where end of list is not a NULL pointer,
      10             :  * but a 'nulls' marker, which can have many different values.
      11             :  * (up to 2^31 different values guaranteed on all platforms)
      12             :  *
      13             :  * In the standard hlist, termination of a list is the NULL pointer.
      14             :  * In this special 'nulls' variant, we use the fact that objects stored in
      15             :  * a list are aligned on a word (4 or 8 bytes alignment).
      16             :  * We therefore use the last significant bit of 'ptr' :
      17             :  * Set to 1 : This is a 'nulls' end-of-list marker (ptr >> 1)
      18             :  * Set to 0 : This is a pointer to some object (ptr)
      19             :  */
      20             : 
      21             : struct hlist_nulls_head {
      22             :         struct hlist_nulls_node *first;
      23             : };
      24             : 
      25             : struct hlist_nulls_node {
      26             :         struct hlist_nulls_node *next, **pprev;
      27             : };
      28             : #define NULLS_MARKER(value) (1UL | (((long)value) << 1))
      29             : #define INIT_HLIST_NULLS_HEAD(ptr, nulls) \
      30             :         ((ptr)->first = (struct hlist_nulls_node *) NULLS_MARKER(nulls))
      31             : 
      32             : #define hlist_nulls_entry(ptr, type, member) container_of(ptr,type,member)
      33             : 
      34             : #define hlist_nulls_entry_safe(ptr, type, member) \
      35             :         ({ typeof(ptr) ____ptr = (ptr); \
      36             :            !is_a_nulls(____ptr) ? hlist_nulls_entry(____ptr, type, member) : NULL; \
      37             :         })
      38             : /**
      39             :  * ptr_is_a_nulls - Test if a ptr is a nulls
      40             :  * @ptr: ptr to be tested
      41             :  *
      42             :  */
      43         461 : static inline int is_a_nulls(const struct hlist_nulls_node *ptr)
      44             : {
      45         453 :         return ((unsigned long)ptr & 1);
      46             : }
      47             : 
      48             : /**
      49             :  * get_nulls_value - Get the 'nulls' value of the end of chain
      50             :  * @ptr: end of chain
      51             :  *
      52             :  * Should be called only if is_a_nulls(ptr);
      53             :  */
      54           8 : static inline unsigned long get_nulls_value(const struct hlist_nulls_node *ptr)
      55             : {
      56           8 :         return ((unsigned long)ptr) >> 1;
      57             : }
      58             : 
      59             : /**
      60             :  * hlist_nulls_unhashed - Has node been removed and reinitialized?
      61             :  * @h: Node to be checked
      62             :  *
      63             :  * Not that not all removal functions will leave a node in unhashed state.
      64             :  * For example, hlist_del_init_rcu() leaves the node in unhashed state,
      65             :  * but hlist_nulls_del() does not.
      66             :  */
      67           8 : static inline int hlist_nulls_unhashed(const struct hlist_nulls_node *h)
      68             : {
      69           8 :         return !h->pprev;
      70             : }
      71             : 
      72             : /**
      73             :  * hlist_nulls_unhashed_lockless - Has node been removed and reinitialized?
      74             :  * @h: Node to be checked
      75             :  *
      76             :  * Not that not all removal functions will leave a node in unhashed state.
      77             :  * For example, hlist_del_init_rcu() leaves the node in unhashed state,
      78             :  * but hlist_nulls_del() does not.  Unlike hlist_nulls_unhashed(), this
      79             :  * function may be used locklessly.
      80             :  */
      81             : static inline int hlist_nulls_unhashed_lockless(const struct hlist_nulls_node *h)
      82             : {
      83             :         return !READ_ONCE(h->pprev);
      84             : }
      85             : 
      86           0 : static inline int hlist_nulls_empty(const struct hlist_nulls_head *h)
      87             : {
      88           0 :         return is_a_nulls(READ_ONCE(h->first));
      89             : }
      90             : 
      91           0 : static inline void hlist_nulls_add_head(struct hlist_nulls_node *n,
      92             :                                         struct hlist_nulls_head *h)
      93             : {
      94           0 :         struct hlist_nulls_node *first = h->first;
      95             : 
      96           0 :         n->next = first;
      97           0 :         WRITE_ONCE(n->pprev, &h->first);
      98           0 :         h->first = n;
      99           0 :         if (!is_a_nulls(first))
     100           0 :                 WRITE_ONCE(first->pprev, &n->next);
     101             : }
     102             : 
     103           8 : static inline void __hlist_nulls_del(struct hlist_nulls_node *n)
     104             : {
     105           8 :         struct hlist_nulls_node *next = n->next;
     106           8 :         struct hlist_nulls_node **pprev = n->pprev;
     107             : 
     108           8 :         WRITE_ONCE(*pprev, next);
     109           8 :         if (!is_a_nulls(next))
     110           8 :                 WRITE_ONCE(next->pprev, pprev);
     111             : }
     112             : 
     113           0 : static inline void hlist_nulls_del(struct hlist_nulls_node *n)
     114             : {
     115           0 :         __hlist_nulls_del(n);
     116           0 :         WRITE_ONCE(n->pprev, LIST_POISON2);
     117             : }
     118             : 
     119             : /**
     120             :  * hlist_nulls_for_each_entry   - iterate over list of given type
     121             :  * @tpos:       the type * to use as a loop cursor.
     122             :  * @pos:        the &struct hlist_node to use as a loop cursor.
     123             :  * @head:       the head for your list.
     124             :  * @member:     the name of the hlist_node within the struct.
     125             :  *
     126             :  */
     127             : #define hlist_nulls_for_each_entry(tpos, pos, head, member)                    \
     128             :         for (pos = (head)->first;                                           \
     129             :              (!is_a_nulls(pos)) &&                                             \
     130             :                 ({ tpos = hlist_nulls_entry(pos, typeof(*tpos), member); 1;}); \
     131             :              pos = pos->next)
     132             : 
     133             : /**
     134             :  * hlist_nulls_for_each_entry_from - iterate over a hlist continuing from current point
     135             :  * @tpos:       the type * to use as a loop cursor.
     136             :  * @pos:        the &struct hlist_node to use as a loop cursor.
     137             :  * @member:     the name of the hlist_node within the struct.
     138             :  *
     139             :  */
     140             : #define hlist_nulls_for_each_entry_from(tpos, pos, member)      \
     141             :         for (; (!is_a_nulls(pos)) &&                            \
     142             :                 ({ tpos = hlist_nulls_entry(pos, typeof(*tpos), member); 1;}); \
     143             :              pos = pos->next)
     144             : 
     145             : #endif