Branch data     Line data    Source code

       1                 :            : // SPDX-License-Identifier: GPL-2.0-only
       2                 :            : /*
       3                 :            :  * klist.c - Routines for manipulating klists.
       4                 :            :  *
       5                 :            :  * Copyright (C) 2005 Patrick Mochel
       6                 :            :  *
       7                 :            :  * This klist interface provides a couple of structures that wrap around
       8                 :            :  * struct list_head to provide explicit list "head" (struct klist) and list
       9                 :            :  * "node" (struct klist_node) objects. For struct klist, a spinlock is
      10                 :            :  * included that protects access to the actual list itself. struct
      11                 :            :  * klist_node provides a pointer to the klist that owns it and a kref
      12                 :            :  * reference count that indicates the number of current users of that node
      13                 :            :  * in the list.
      14                 :            :  *
      15                 :            :  * The entire point is to provide an interface for iterating over a list
      16                 :            :  * that is safe and allows for modification of the list during the
      17                 :            :  * iteration (e.g. insertion and removal), including modification of the
      18                 :            :  * current node on the list.
      19                 :            :  *
      20                 :            :  * It works using a 3rd object type - struct klist_iter - that is declared
      21                 :            :  * and initialized before an iteration. klist_next() is used to acquire the
      22                 :            :  * next element in the list. It returns NULL if there are no more items.
      23                 :            :  * Internally, that routine takes the klist's lock, decrements the
      24                 :            :  * reference count of the previous klist_node and increments the count of
      25                 :            :  * the next klist_node. It then drops the lock and returns.
      26                 :            :  *
      27                 :            :  * There are primitives for adding and removing nodes to/from a klist.
      28                 :            :  * When deleting, klist_del() will simply decrement the reference count.
      29                 :            :  * Only when the count goes to 0 is the node removed from the list.
      30                 :            :  * klist_remove() will try to delete the node from the list and block until
      31                 :            :  * it is actually removed. This is useful for objects (like devices) that
      32                 :            :  * have been removed from the system and must be freed (but must wait until
      33                 :            :  * all accessors have finished).
      34                 :            :  */
      35                 :            : 
      36                 :            : #include <linux/klist.h>
      37                 :            : #include <linux/export.h>
      38                 :            : #include <linux/sched.h>
      39                 :            : 
      40                 :            : /*
      41                 :            :  * Use the lowest bit of n_klist to mark deleted nodes and exclude
      42                 :            :  * dead ones from iteration.
      43                 :            :  */
      44                 :            : #define KNODE_DEAD              1LU
      45                 :            : #define KNODE_KLIST_MASK        ~KNODE_DEAD
      46                 :            : 
      47                 :            : static struct klist *knode_klist(struct klist_node *knode)
      48                 :            : {
      49                 :          3 :         return (struct klist *)
      50                 :          3 :                 ((unsigned long)knode->n_klist & KNODE_KLIST_MASK);
      51                 :            : }
      52                 :            : 
      53                 :            : static bool knode_dead(struct klist_node *knode)
      54                 :            : {
      55                 :          3 :         return (unsigned long)knode->n_klist & KNODE_DEAD;
      56                 :            : }
      57                 :            : 
      58                 :          3 : static void knode_set_klist(struct klist_node *knode, struct klist *klist)
      59                 :            : {
      60                 :          3 :         knode->n_klist = klist;
      61                 :            :         /* no knode deserves to start its life dead */
      62                 :          3 :         WARN_ON(knode_dead(knode));
      63                 :          3 : }
      64                 :            : 
      65                 :          3 : static void knode_kill(struct klist_node *knode)
      66                 :            : {
      67                 :            :         /* and no knode should die twice ever either, see we're very humane */
      68                 :          3 :         WARN_ON(knode_dead(knode));
      69                 :          3 :         *(unsigned long *)&knode->n_klist |= KNODE_DEAD;
      70                 :          3 : }
      71                 :            : 
      72                 :            : /**
      73                 :            :  * klist_init - Initialize a klist structure.
      74                 :            :  * @k: The klist we're initializing.
      75                 :            :  * @get: The get function for the embedding object (NULL if none)
      76                 :            :  * @put: The put function for the embedding object (NULL if none)
      77                 :            :  *
      78                 :            :  * Initialises the klist structure.  If the klist_node structures are
      79                 :            :  * going to be embedded in refcounted objects (necessary for safe
      80                 :            :  * deletion) then the get/put arguments are used to initialise
      81                 :            :  * functions that take and release references on the embedding
      82                 :            :  * objects.
      83                 :            :  */
      84                 :          3 : void klist_init(struct klist *k, void (*get)(struct klist_node *),
      85                 :            :                 void (*put)(struct klist_node *))
      86                 :            : {
      87                 :          3 :         INIT_LIST_HEAD(&k->k_list);
      88                 :          3 :         spin_lock_init(&k->k_lock);
      89                 :          3 :         k->get = get;
      90                 :          3 :         k->put = put;
      91                 :          3 : }
      92                 :            : EXPORT_SYMBOL_GPL(klist_init);
      93                 :            : 
      94                 :          0 : static void add_head(struct klist *k, struct klist_node *n)
      95                 :            : {
      96                 :            :         spin_lock(&k->k_lock);
      97                 :          0 :         list_add(&n->n_node, &k->k_list);
      98                 :            :         spin_unlock(&k->k_lock);
      99                 :          0 : }
     100                 :            : 
     101                 :          3 : static void add_tail(struct klist *k, struct klist_node *n)
     102                 :            : {
     103                 :            :         spin_lock(&k->k_lock);
     104                 :          3 :         list_add_tail(&n->n_node, &k->k_list);
     105                 :            :         spin_unlock(&k->k_lock);
     106                 :          3 : }
     107                 :            : 
     108                 :          3 : static void klist_node_init(struct klist *k, struct klist_node *n)
     109                 :            : {
     110                 :          3 :         INIT_LIST_HEAD(&n->n_node);
     111                 :            :         kref_init(&n->n_ref);
     112                 :          3 :         knode_set_klist(n, k);
     113                 :          3 :         if (k->get)
     114                 :          3 :                 k->get(n);
     115                 :          3 : }
     116                 :            : 
     117                 :            : /**
     118                 :            :  * klist_add_head - Initialize a klist_node and add it to front.
     119                 :            :  * @n: node we're adding.
     120                 :            :  * @k: klist it's going on.
     121                 :            :  */
     122                 :          0 : void klist_add_head(struct klist_node *n, struct klist *k)
     123                 :            : {
     124                 :          0 :         klist_node_init(k, n);
     125                 :          0 :         add_head(k, n);
     126                 :          0 : }
     127                 :            : EXPORT_SYMBOL_GPL(klist_add_head);
     128                 :            : 
     129                 :            : /**
     130                 :            :  * klist_add_tail - Initialize a klist_node and add it to back.
     131                 :            :  * @n: node we're adding.
     132                 :            :  * @k: klist it's going on.
     133                 :            :  */
     134                 :          3 : void klist_add_tail(struct klist_node *n, struct klist *k)
     135                 :            : {
     136                 :          3 :         klist_node_init(k, n);
     137                 :          3 :         add_tail(k, n);
     138                 :          3 : }
     139                 :            : EXPORT_SYMBOL_GPL(klist_add_tail);
     140                 :            : 
     141                 :            : /**
     142                 :            :  * klist_add_behind - Init a klist_node and add it after an existing node
     143                 :            :  * @n: node we're adding.
     144                 :            :  * @pos: node to put @n after
     145                 :            :  */
     146                 :          0 : void klist_add_behind(struct klist_node *n, struct klist_node *pos)
     147                 :            : {
     148                 :            :         struct klist *k = knode_klist(pos);
     149                 :            : 
     150                 :          0 :         klist_node_init(k, n);
     151                 :            :         spin_lock(&k->k_lock);
     152                 :          0 :         list_add(&n->n_node, &pos->n_node);
     153                 :            :         spin_unlock(&k->k_lock);
     154                 :          0 : }
     155                 :            : EXPORT_SYMBOL_GPL(klist_add_behind);
     156                 :            : 
     157                 :            : /**
     158                 :            :  * klist_add_before - Init a klist_node and add it before an existing node
     159                 :            :  * @n: node we're adding.
     160                 :            :  * @pos: node to put @n after
     161                 :            :  */
     162                 :          0 : void klist_add_before(struct klist_node *n, struct klist_node *pos)
     163                 :            : {
     164                 :            :         struct klist *k = knode_klist(pos);
     165                 :            : 
     166                 :          0 :         klist_node_init(k, n);
     167                 :            :         spin_lock(&k->k_lock);
     168                 :          0 :         list_add_tail(&n->n_node, &pos->n_node);
     169                 :            :         spin_unlock(&k->k_lock);
     170                 :          0 : }
     171                 :            : EXPORT_SYMBOL_GPL(klist_add_before);
     172                 :            : 
     173                 :            : struct klist_waiter {
     174                 :            :         struct list_head list;
     175                 :            :         struct klist_node *node;
     176                 :            :         struct task_struct *process;
     177                 :            :         int woken;
     178                 :            : };
     179                 :            : 
     180                 :            : static DEFINE_SPINLOCK(klist_remove_lock);
     181                 :            : static LIST_HEAD(klist_remove_waiters);
     182                 :            : 
     183                 :          3 : static void klist_release(struct kref *kref)
     184                 :            : {
     185                 :            :         struct klist_waiter *waiter, *tmp;
     186                 :          3 :         struct klist_node *n = container_of(kref, struct klist_node, n_ref);
     187                 :            : 
     188                 :          3 :         WARN_ON(!knode_dead(n));
     189                 :            :         list_del(&n->n_node);
     190                 :            :         spin_lock(&klist_remove_lock);
     191                 :          3 :         list_for_each_entry_safe(waiter, tmp, &klist_remove_waiters, list) {
     192                 :          0 :                 if (waiter->node != n)
     193                 :          0 :                         continue;
     194                 :            : 
     195                 :            :                 list_del(&waiter->list);
     196                 :          0 :                 waiter->woken = 1;
     197                 :          0 :                 mb();
     198                 :          0 :                 wake_up_process(waiter->process);
     199                 :            :         }
     200                 :            :         spin_unlock(&klist_remove_lock);
     201                 :          3 :         knode_set_klist(n, NULL);
     202                 :          3 : }
     203                 :            : 
     204                 :          3 : static int klist_dec_and_del(struct klist_node *n)
     205                 :            : {
     206                 :          3 :         return kref_put(&n->n_ref, klist_release);
     207                 :            : }
     208                 :            : 
     209                 :          3 : static void klist_put(struct klist_node *n, bool kill)
     210                 :            : {
     211                 :            :         struct klist *k = knode_klist(n);
     212                 :          3 :         void (*put)(struct klist_node *) = k->put;
     213                 :            : 
     214                 :            :         spin_lock(&k->k_lock);
     215                 :          3 :         if (kill)
     216                 :          3 :                 knode_kill(n);
     217                 :          3 :         if (!klist_dec_and_del(n))
     218                 :            :                 put = NULL;
     219                 :            :         spin_unlock(&k->k_lock);
     220                 :          3 :         if (put)
     221                 :          3 :                 put(n);
     222                 :          3 : }
     223                 :            : 
     224                 :            : /**
     225                 :            :  * klist_del - Decrement the reference count of node and try to remove.
     226                 :            :  * @n: node we're deleting.
     227                 :            :  */
     228                 :          3 : void klist_del(struct klist_node *n)
     229                 :            : {
     230                 :          3 :         klist_put(n, true);
     231                 :          3 : }
     232                 :            : EXPORT_SYMBOL_GPL(klist_del);
     233                 :            : 
     234                 :            : /**
     235                 :            :  * klist_remove - Decrement the refcount of node and wait for it to go away.
     236                 :            :  * @n: node we're removing.
     237                 :            :  */
     238                 :          0 : void klist_remove(struct klist_node *n)
     239                 :            : {
     240                 :            :         struct klist_waiter waiter;
     241                 :            : 
     242                 :          0 :         waiter.node = n;
     243                 :          0 :         waiter.process = current;
     244                 :          0 :         waiter.woken = 0;
     245                 :            :         spin_lock(&klist_remove_lock);
     246                 :            :         list_add(&waiter.list, &klist_remove_waiters);
     247                 :            :         spin_unlock(&klist_remove_lock);
     248                 :            : 
     249                 :            :         klist_del(n);
     250                 :            : 
     251                 :            :         for (;;) {
     252                 :          0 :                 set_current_state(TASK_UNINTERRUPTIBLE);
     253                 :          0 :                 if (waiter.woken)
     254                 :            :                         break;
     255                 :          0 :                 schedule();
     256                 :          0 :         }
     257                 :          0 :         __set_current_state(TASK_RUNNING);
     258                 :          0 : }
     259                 :            : EXPORT_SYMBOL_GPL(klist_remove);
     260                 :            : 
     261                 :            : /**
     262                 :            :  * klist_node_attached - Say whether a node is bound to a list or not.
     263                 :            :  * @n: Node that we're testing.
     264                 :            :  */
     265                 :          3 : int klist_node_attached(struct klist_node *n)
     266                 :            : {
     267                 :          3 :         return (n->n_klist != NULL);
     268                 :            : }
     269                 :            : EXPORT_SYMBOL_GPL(klist_node_attached);
     270                 :            : 
     271                 :            : /**
     272                 :            :  * klist_iter_init_node - Initialize a klist_iter structure.
     273                 :            :  * @k: klist we're iterating.
     274                 :            :  * @i: klist_iter we're filling.
     275                 :            :  * @n: node to start with.
     276                 :            :  *
     277                 :            :  * Similar to klist_iter_init(), but starts the action off with @n,
     278                 :            :  * instead of with the list head.
     279                 :            :  */
     280                 :          3 : void klist_iter_init_node(struct klist *k, struct klist_iter *i,
     281                 :            :                           struct klist_node *n)
     282                 :            : {
     283                 :          3 :         i->i_klist = k;
     284                 :          3 :         i->i_cur = NULL;
     285                 :          3 :         if (n && kref_get_unless_zero(&n->n_ref))
     286                 :          0 :                 i->i_cur = n;
     287                 :          3 : }
     288                 :            : EXPORT_SYMBOL_GPL(klist_iter_init_node);
     289                 :            : 
     290                 :            : /**
     291                 :            :  * klist_iter_init - Iniitalize a klist_iter structure.
     292                 :            :  * @k: klist we're iterating.
     293                 :            :  * @i: klist_iter structure we're filling.
     294                 :            :  *
     295                 :            :  * Similar to klist_iter_init_node(), but start with the list head.
     296                 :            :  */
     297                 :          3 : void klist_iter_init(struct klist *k, struct klist_iter *i)
     298                 :            : {
     299                 :            :         klist_iter_init_node(k, i, NULL);
     300                 :          3 : }
     301                 :            : EXPORT_SYMBOL_GPL(klist_iter_init);
     302                 :            : 
     303                 :            : /**
     304                 :            :  * klist_iter_exit - Finish a list iteration.
     305                 :            :  * @i: Iterator structure.
     306                 :            :  *
     307                 :            :  * Must be called when done iterating over list, as it decrements the
     308                 :            :  * refcount of the current node. Necessary in case iteration exited before
     309                 :            :  * the end of the list was reached, and always good form.
     310                 :            :  */
     311                 :          3 : void klist_iter_exit(struct klist_iter *i)
     312                 :            : {
     313                 :          3 :         if (i->i_cur) {
     314                 :          3 :                 klist_put(i->i_cur, false);
     315                 :          3 :                 i->i_cur = NULL;
     316                 :            :         }
     317                 :          3 : }
     318                 :            : EXPORT_SYMBOL_GPL(klist_iter_exit);
     319                 :            : 
     320                 :            : static struct klist_node *to_klist_node(struct list_head *n)
     321                 :            : {
     322                 :          3 :         return container_of(n, struct klist_node, n_node);
     323                 :            : }
     324                 :            : 
     325                 :            : /**
     326                 :            :  * klist_prev - Ante up prev node in list.
     327                 :            :  * @i: Iterator structure.
     328                 :            :  *
     329                 :            :  * First grab list lock. Decrement the reference count of the previous
     330                 :            :  * node, if there was one. Grab the prev node, increment its reference
     331                 :            :  * count, drop the lock, and return that prev node.
     332                 :            :  */
     333                 :          0 : struct klist_node *klist_prev(struct klist_iter *i)
     334                 :            : {
     335                 :          0 :         void (*put)(struct klist_node *) = i->i_klist->put;
     336                 :          0 :         struct klist_node *last = i->i_cur;
     337                 :            :         struct klist_node *prev;
     338                 :            :         unsigned long flags;
     339                 :            : 
     340                 :          0 :         spin_lock_irqsave(&i->i_klist->k_lock, flags);
     341                 :            : 
     342                 :          0 :         if (last) {
     343                 :          0 :                 prev = to_klist_node(last->n_node.prev);
     344                 :          0 :                 if (!klist_dec_and_del(last))
     345                 :            :                         put = NULL;
     346                 :            :         } else
     347                 :          0 :                 prev = to_klist_node(i->i_klist->k_list.prev);
     348                 :            : 
     349                 :          0 :         i->i_cur = NULL;
     350                 :          0 :         while (prev != to_klist_node(&i->i_klist->k_list)) {
     351                 :          0 :                 if (likely(!knode_dead(prev))) {
     352                 :            :                         kref_get(&prev->n_ref);
     353                 :          0 :                         i->i_cur = prev;
     354                 :          0 :                         break;
     355                 :            :                 }
     356                 :          0 :                 prev = to_klist_node(prev->n_node.prev);
     357                 :            :         }
     358                 :            : 
     359                 :          0 :         spin_unlock_irqrestore(&i->i_klist->k_lock, flags);
     360                 :            : 
     361                 :          0 :         if (put && last)
     362                 :          0 :                 put(last);
     363                 :          0 :         return i->i_cur;
     364                 :            : }
     365                 :            : EXPORT_SYMBOL_GPL(klist_prev);
     366                 :            : 
     367                 :            : /**
     368                 :            :  * klist_next - Ante up next node in list.
     369                 :            :  * @i: Iterator structure.
     370                 :            :  *
     371                 :            :  * First grab list lock. Decrement the reference count of the previous
     372                 :            :  * node, if there was one. Grab the next node, increment its reference
     373                 :            :  * count, drop the lock, and return that next node.
     374                 :            :  */
     375                 :          3 : struct klist_node *klist_next(struct klist_iter *i)
     376                 :            : {
     377                 :          3 :         void (*put)(struct klist_node *) = i->i_klist->put;
     378                 :          3 :         struct klist_node *last = i->i_cur;
     379                 :            :         struct klist_node *next;
     380                 :            :         unsigned long flags;
     381                 :            : 
     382                 :          3 :         spin_lock_irqsave(&i->i_klist->k_lock, flags);
     383                 :            : 
     384                 :          3 :         if (last) {
     385                 :          3 :                 next = to_klist_node(last->n_node.next);
     386                 :          3 :                 if (!klist_dec_and_del(last))
     387                 :            :                         put = NULL;
     388                 :            :         } else
     389                 :          3 :                 next = to_klist_node(i->i_klist->k_list.next);
     390                 :            : 
     391                 :          3 :         i->i_cur = NULL;
     392                 :          3 :         while (next != to_klist_node(&i->i_klist->k_list)) {
     393                 :          3 :                 if (likely(!knode_dead(next))) {
     394                 :            :                         kref_get(&next->n_ref);
     395                 :          3 :                         i->i_cur = next;
     396                 :          3 :                         break;
     397                 :            :                 }
     398                 :          0 :                 next = to_klist_node(next->n_node.next);
     399                 :            :         }
     400                 :            : 
     401                 :          3 :         spin_unlock_irqrestore(&i->i_klist->k_lock, flags);
     402                 :            : 
     403                 :          3 :         if (put && last)
     404                 :          0 :                 put(last);
     405                 :          3 :         return i->i_cur;
     406                 :            : }
     407                 :            : EXPORT_SYMBOL_GPL(klist_next);