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