Branch data     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                 :   10727118 :         h->next = NULL;
      47                 :   10727118 :         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                 :  102041298 :         return !h->pprev;
      55                 :            : }
      56                 :            : 
      57                 :            : static inline struct hlist_bl_node *hlist_bl_first(struct hlist_bl_head *h)
      58                 :            : {
      59                 :   28676377 :         return (struct hlist_bl_node *)
      60                 :   28676377 :                 ((unsigned long)h->first & ~LIST_BL_LOCKMASK);
      61                 :            : }
      62                 :            : 
      63                 :            : static inline void hlist_bl_set_first(struct hlist_bl_head *h,
      64                 :            :                                         struct hlist_bl_node *n)
      65                 :            : {
      66                 :            :         LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
      67                 :            :         LIST_BL_BUG_ON(((unsigned long)h->first & LIST_BL_LOCKMASK) !=
      68                 :            :                                                         LIST_BL_LOCKMASK);
      69                 :        207 :         h->first = (struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK);
      70                 :            : }
      71                 :            : 
      72                 :            : static inline bool hlist_bl_empty(const struct hlist_bl_head *h)
      73                 :            : {
      74                 :          2 :         return !((unsigned long)READ_ONCE(h->first) & ~LIST_BL_LOCKMASK);
      75                 :            : }
      76                 :            : 
      77                 :            : static inline void hlist_bl_add_head(struct hlist_bl_node *n,
      78                 :            :                                         struct hlist_bl_head *h)
      79                 :            : {
      80                 :            :         struct hlist_bl_node *first = hlist_bl_first(h);
      81                 :            : 
      82                 :        207 :         n->next = first;
      83         [ -  + ]:        207 :         if (first)
      84                 :          0 :                 first->pprev = &n->next;
      85                 :        207 :         n->pprev = &h->first;
      86                 :            :         hlist_bl_set_first(h, n);
      87                 :            : }
      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                 :            : static inline void __hlist_bl_del(struct hlist_bl_node *n)
     116                 :            : {
     117                 :   13860546 :         struct hlist_bl_node *next = n->next;
     118                 :   13860546 :         struct hlist_bl_node **pprev = n->pprev;
     119                 :            : 
     120                 :            :         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                 :   13860546 :         WRITE_ONCE(*pprev,
     124                 :            :                    (struct hlist_bl_node *)
     125                 :            :                         ((unsigned long)next |
     126                 :            :                          ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
     127   [ +  +  +  +  :   13860546 :         if (next)
                   #  # ]
     128                 :     461680 :                 next->pprev = pprev;
     129                 :            : }
     130                 :            : 
     131                 :            : static inline void hlist_bl_del(struct hlist_bl_node *n)
     132                 :            : {
     133                 :            :         __hlist_bl_del(n);
     134                 :          0 :         n->next = LIST_POISON1;
     135                 :          0 :         n->pprev = LIST_POISON2;
     136                 :            : }
     137                 :            : 
     138                 :            : static inline void hlist_bl_del_init(struct hlist_bl_node *n)
     139                 :            : {
     140   [ #  #  #  #  :          0 :         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                 :   32633486 :         bit_spin_lock(0, (unsigned long *)b);
     149                 :            : }
     150                 :            : 
     151                 :            : static inline void hlist_bl_unlock(struct hlist_bl_head *b)
     152                 :            : {
     153                 :            :         __bit_spin_unlock(0, (unsigned long *)b);
     154                 :            : }
     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