Line data    Source code

       1             : /* SPDX-License-Identifier: GPL-2.0 */
       2             : #ifndef _LINUX_LIST_BL_H
       3             : #define _LINUX_LIST_BL_H
       4             : 
       5             : #include <linux/list.h>
       6             : #include <linux/bit_spinlock.h>
       7             : 
       8             : /*
       9             :  * Special version of lists, where head of the list has a lock in the lowest
      10             :  * bit. This is useful for scalable hash tables without increasing memory
      11             :  * footprint overhead.
      12             :  *
      13             :  * For modification operations, the 0 bit of hlist_bl_head->first
      14             :  * pointer must be set.
      15             :  *
      16             :  * With some small modifications, this can easily be adapted to store several
      17             :  * arbitrary bits (not just a single lock bit), if the need arises to store
      18             :  * some fast and compact auxiliary data.
      19             :  */
      20             : 
      21             : #if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_SPINLOCK)
      22             : #define LIST_BL_LOCKMASK        1UL
      23             : #else
      24             : #define LIST_BL_LOCKMASK        0UL
      25             : #endif
      26             : 
      27             : #ifdef CONFIG_DEBUG_LIST
      28             : #define LIST_BL_BUG_ON(x) BUG_ON(x)
      29             : #else
      30             : #define LIST_BL_BUG_ON(x)
      31             : #endif
      32             : 
      33             : 
      34             : struct hlist_bl_head {
      35             :         struct hlist_bl_node *first;
      36             : };
      37             : 
      38             : struct hlist_bl_node {
      39             :         struct hlist_bl_node *next, **pprev;
      40             : };
      41             : #define INIT_HLIST_BL_HEAD(ptr) \
      42             :         ((ptr)->first = NULL)
      43             : 
      44             : static inline void INIT_HLIST_BL_NODE(struct hlist_bl_node *h)
      45             : {
      46  1788654150 :         h->next = NULL;
      47  1788654150 :         h->pprev = NULL;
      48             : }
      49             : 
      50             : #define hlist_bl_entry(ptr, type, member) container_of(ptr,type,member)
      51             : 
      52             : static inline bool  hlist_bl_unhashed(const struct hlist_bl_node *h)
      53             : {
      54 80945261339 :         return !h->pprev;
      55             : }
      56             : 
      57             : static inline struct hlist_bl_node *hlist_bl_first(struct hlist_bl_head *h)
      58             : {
      59  3543003987 :         return (struct hlist_bl_node *)
      60  3542834482 :                 ((unsigned long)h->first & ~LIST_BL_LOCKMASK);
      61             : }
      62             : 
      63      169486 : static inline void hlist_bl_set_first(struct hlist_bl_head *h,
      64             :                                         struct hlist_bl_node *n)
      65             : {
      66      169486 :         LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
      67      169486 :         LIST_BL_BUG_ON(((unsigned long)h->first & LIST_BL_LOCKMASK) !=
      68             :                                                         LIST_BL_LOCKMASK);
      69      169486 :         h->first = (struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK);
      70      169486 : }
      71             : 
      72             : static inline bool hlist_bl_empty(const struct hlist_bl_head *h)
      73             : {
      74      124610 :         return !((unsigned long)READ_ONCE(h->first) & ~LIST_BL_LOCKMASK);
      75             : }
      76             : 
      77      169505 : static inline void hlist_bl_add_head(struct hlist_bl_node *n,
      78             :                                         struct hlist_bl_head *h)
      79             : {
      80      169505 :         struct hlist_bl_node *first = hlist_bl_first(h);
      81             : 
      82      169505 :         n->next = first;
      83      169505 :         if (first)
      84      150545 :                 first->pprev = &n->next;
      85      169505 :         n->pprev = &h->first;
      86      169505 :         hlist_bl_set_first(h, n);
      87      169483 : }
      88             : 
      89             : static inline void hlist_bl_add_before(struct hlist_bl_node *n,
      90             :                                        struct hlist_bl_node *next)
      91             : {
      92             :         struct hlist_bl_node **pprev = next->pprev;
      93             : 
      94             :         n->pprev = pprev;
      95             :         n->next = next;
      96             :         next->pprev = &n->next;
      97             : 
      98             :         /* pprev may be `first`, so be careful not to lose the lock bit */
      99             :         WRITE_ONCE(*pprev,
     100             :                    (struct hlist_bl_node *)
     101             :                         ((uintptr_t)n | ((uintptr_t)*pprev & LIST_BL_LOCKMASK)));
     102             : }
     103             : 
     104             : static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
     105             :                                        struct hlist_bl_node *prev)
     106             : {
     107             :         n->next = prev->next;
     108             :         n->pprev = &prev->next;
     109             :         prev->next = n;
     110             : 
     111             :         if (n->next)
     112             :                 n->next->pprev = &n->next;
     113             : }
     114             : 
     115  2426176385 : static inline void __hlist_bl_del(struct hlist_bl_node *n)
     116             : {
     117  2426176385 :         struct hlist_bl_node *next = n->next;
     118  2426176385 :         struct hlist_bl_node **pprev = n->pprev;
     119             : 
     120  2426176385 :         LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
     121             : 
     122             :         /* pprev may be `first`, so be careful not to lose the lock bit */
     123  2426176385 :         WRITE_ONCE(*pprev,
     124             :                    (struct hlist_bl_node *)
     125             :                         ((unsigned long)next |
     126             :                          ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
     127  2426176385 :         if (next)
     128    47051658 :                 next->pprev = pprev;
     129  2426176385 : }
     130             : 
     131             : static inline void hlist_bl_del(struct hlist_bl_node *n)
     132             : {
     133             :         __hlist_bl_del(n);
     134      169565 :         n->next = LIST_POISON1;
     135      169565 :         n->pprev = LIST_POISON2;
     136             : }
     137             : 
     138             : static inline void hlist_bl_del_init(struct hlist_bl_node *n)
     139             : {
     140             :         if (!hlist_bl_unhashed(n)) {
     141             :                 __hlist_bl_del(n);
     142             :                 INIT_HLIST_BL_NODE(n);
     143             :         }
     144             : }
     145             : 
     146             : static inline void hlist_bl_lock(struct hlist_bl_head *b)
     147             : {
     148  4857178392 :         bit_spin_lock(0, (unsigned long *)b);
     149             : }
     150             : 
     151             : static inline void hlist_bl_unlock(struct hlist_bl_head *b)
     152             : {
     153  4857957328 :         __bit_spin_unlock(0, (unsigned long *)b);
     154           0 : }
     155             : 
     156             : static inline bool hlist_bl_is_locked(struct hlist_bl_head *b)
     157             : {
     158             :         return bit_spin_is_locked(0, (unsigned long *)b);
     159             : }
     160             : 
     161             : /**
     162             :  * hlist_bl_for_each_entry      - iterate over list of given type
     163             :  * @tpos:       the type * to use as a loop cursor.
     164             :  * @pos:        the &struct hlist_node to use as a loop cursor.
     165             :  * @head:       the head for your list.
     166             :  * @member:     the name of the hlist_node within the struct.
     167             :  *
     168             :  */
     169             : #define hlist_bl_for_each_entry(tpos, pos, head, member)                \
     170             :         for (pos = hlist_bl_first(head);                                \
     171             :              pos &&                                                     \
     172             :                 ({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \
     173             :              pos = pos->next)
     174             : 
     175             : /**
     176             :  * hlist_bl_for_each_entry_safe - iterate over list of given type safe against removal of list entry
     177             :  * @tpos:       the type * to use as a loop cursor.
     178             :  * @pos:        the &struct hlist_node to use as a loop cursor.
     179             :  * @n:          another &struct hlist_node to use as temporary storage
     180             :  * @head:       the head for your list.
     181             :  * @member:     the name of the hlist_node within the struct.
     182             :  */
     183             : #define hlist_bl_for_each_entry_safe(tpos, pos, n, head, member)         \
     184             :         for (pos = hlist_bl_first(head);                                 \
     185             :              pos && ({ n = pos->next; 1; }) &&                                \
     186             :                 ({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \
     187             :              pos = n)
     188             : 
     189             : #endif