Back to home page

LXR

 
 

    


0001 /*
0002  * klist.c - Routines for manipulating klists.
0003  *
0004  * Copyright (C) 2005 Patrick Mochel
0005  *
0006  * This file is released under the GPL v2.
0007  *
0008  * This klist interface provides a couple of structures that wrap around
0009  * struct list_head to provide explicit list "head" (struct klist) and list
0010  * "node" (struct klist_node) objects. For struct klist, a spinlock is
0011  * included that protects access to the actual list itself. struct
0012  * klist_node provides a pointer to the klist that owns it and a kref
0013  * reference count that indicates the number of current users of that node
0014  * in the list.
0015  *
0016  * The entire point is to provide an interface for iterating over a list
0017  * that is safe and allows for modification of the list during the
0018  * iteration (e.g. insertion and removal), including modification of the
0019  * current node on the list.
0020  *
0021  * It works using a 3rd object type - struct klist_iter - that is declared
0022  * and initialized before an iteration. klist_next() is used to acquire the
0023  * next element in the list. It returns NULL if there are no more items.
0024  * Internally, that routine takes the klist's lock, decrements the
0025  * reference count of the previous klist_node and increments the count of
0026  * the next klist_node. It then drops the lock and returns.
0027  *
0028  * There are primitives for adding and removing nodes to/from a klist.
0029  * When deleting, klist_del() will simply decrement the reference count.
0030  * Only when the count goes to 0 is the node removed from the list.
0031  * klist_remove() will try to delete the node from the list and block until
0032  * it is actually removed. This is useful for objects (like devices) that
0033  * have been removed from the system and must be freed (but must wait until
0034  * all accessors have finished).
0035  */
0036 
0037 #include <linux/klist.h>
0038 #include <linux/export.h>
0039 #include <linux/sched.h>
0040 
0041 /*
0042  * Use the lowest bit of n_klist to mark deleted nodes and exclude
0043  * dead ones from iteration.
0044  */
0045 #define KNODE_DEAD      1LU
0046 #define KNODE_KLIST_MASK    ~KNODE_DEAD
0047 
0048 static struct klist *knode_klist(struct klist_node *knode)
0049 {
0050     return (struct klist *)
0051         ((unsigned long)knode->n_klist & KNODE_KLIST_MASK);
0052 }
0053 
0054 static bool knode_dead(struct klist_node *knode)
0055 {
0056     return (unsigned long)knode->n_klist & KNODE_DEAD;
0057 }
0058 
0059 static void knode_set_klist(struct klist_node *knode, struct klist *klist)
0060 {
0061     knode->n_klist = klist;
0062     /* no knode deserves to start its life dead */
0063     WARN_ON(knode_dead(knode));
0064 }
0065 
0066 static void knode_kill(struct klist_node *knode)
0067 {
0068     /* and no knode should die twice ever either, see we're very humane */
0069     WARN_ON(knode_dead(knode));
0070     *(unsigned long *)&knode->n_klist |= KNODE_DEAD;
0071 }
0072 
0073 /**
0074  * klist_init - Initialize a klist structure.
0075  * @k: The klist we're initializing.
0076  * @get: The get function for the embedding object (NULL if none)
0077  * @put: The put function for the embedding object (NULL if none)
0078  *
0079  * Initialises the klist structure.  If the klist_node structures are
0080  * going to be embedded in refcounted objects (necessary for safe
0081  * deletion) then the get/put arguments are used to initialise
0082  * functions that take and release references on the embedding
0083  * objects.
0084  */
0085 void klist_init(struct klist *k, void (*get)(struct klist_node *),
0086         void (*put)(struct klist_node *))
0087 {
0088     INIT_LIST_HEAD(&k->k_list);
0089     spin_lock_init(&k->k_lock);
0090     k->get = get;
0091     k->put = put;
0092 }
0093 EXPORT_SYMBOL_GPL(klist_init);
0094 
0095 static void add_head(struct klist *k, struct klist_node *n)
0096 {
0097     spin_lock(&k->k_lock);
0098     list_add(&n->n_node, &k->k_list);
0099     spin_unlock(&k->k_lock);
0100 }
0101 
0102 static void add_tail(struct klist *k, struct klist_node *n)
0103 {
0104     spin_lock(&k->k_lock);
0105     list_add_tail(&n->n_node, &k->k_list);
0106     spin_unlock(&k->k_lock);
0107 }
0108 
0109 static void klist_node_init(struct klist *k, struct klist_node *n)
0110 {
0111     INIT_LIST_HEAD(&n->n_node);
0112     kref_init(&n->n_ref);
0113     knode_set_klist(n, k);
0114     if (k->get)
0115         k->get(n);
0116 }
0117 
0118 /**
0119  * klist_add_head - Initialize a klist_node and add it to front.
0120  * @n: node we're adding.
0121  * @k: klist it's going on.
0122  */
0123 void klist_add_head(struct klist_node *n, struct klist *k)
0124 {
0125     klist_node_init(k, n);
0126     add_head(k, n);
0127 }
0128 EXPORT_SYMBOL_GPL(klist_add_head);
0129 
0130 /**
0131  * klist_add_tail - Initialize a klist_node and add it to back.
0132  * @n: node we're adding.
0133  * @k: klist it's going on.
0134  */
0135 void klist_add_tail(struct klist_node *n, struct klist *k)
0136 {
0137     klist_node_init(k, n);
0138     add_tail(k, n);
0139 }
0140 EXPORT_SYMBOL_GPL(klist_add_tail);
0141 
0142 /**
0143  * klist_add_behind - Init a klist_node and add it after an existing node
0144  * @n: node we're adding.
0145  * @pos: node to put @n after
0146  */
0147 void klist_add_behind(struct klist_node *n, struct klist_node *pos)
0148 {
0149     struct klist *k = knode_klist(pos);
0150 
0151     klist_node_init(k, n);
0152     spin_lock(&k->k_lock);
0153     list_add(&n->n_node, &pos->n_node);
0154     spin_unlock(&k->k_lock);
0155 }
0156 EXPORT_SYMBOL_GPL(klist_add_behind);
0157 
0158 /**
0159  * klist_add_before - Init a klist_node and add it before an existing node
0160  * @n: node we're adding.
0161  * @pos: node to put @n after
0162  */
0163 void klist_add_before(struct klist_node *n, struct klist_node *pos)
0164 {
0165     struct klist *k = knode_klist(pos);
0166 
0167     klist_node_init(k, n);
0168     spin_lock(&k->k_lock);
0169     list_add_tail(&n->n_node, &pos->n_node);
0170     spin_unlock(&k->k_lock);
0171 }
0172 EXPORT_SYMBOL_GPL(klist_add_before);
0173 
0174 struct klist_waiter {
0175     struct list_head list;
0176     struct klist_node *node;
0177     struct task_struct *process;
0178     int woken;
0179 };
0180 
0181 static DEFINE_SPINLOCK(klist_remove_lock);
0182 static LIST_HEAD(klist_remove_waiters);
0183 
0184 static void klist_release(struct kref *kref)
0185 {
0186     struct klist_waiter *waiter, *tmp;
0187     struct klist_node *n = container_of(kref, struct klist_node, n_ref);
0188 
0189     WARN_ON(!knode_dead(n));
0190     list_del(&n->n_node);
0191     spin_lock(&klist_remove_lock);
0192     list_for_each_entry_safe(waiter, tmp, &klist_remove_waiters, list) {
0193         if (waiter->node != n)
0194             continue;
0195 
0196         list_del(&waiter->list);
0197         waiter->woken = 1;
0198         mb();
0199         wake_up_process(waiter->process);
0200     }
0201     spin_unlock(&klist_remove_lock);
0202     knode_set_klist(n, NULL);
0203 }
0204 
0205 static int klist_dec_and_del(struct klist_node *n)
0206 {
0207     return kref_put(&n->n_ref, klist_release);
0208 }
0209 
0210 static void klist_put(struct klist_node *n, bool kill)
0211 {
0212     struct klist *k = knode_klist(n);
0213     void (*put)(struct klist_node *) = k->put;
0214 
0215     spin_lock(&k->k_lock);
0216     if (kill)
0217         knode_kill(n);
0218     if (!klist_dec_and_del(n))
0219         put = NULL;
0220     spin_unlock(&k->k_lock);
0221     if (put)
0222         put(n);
0223 }
0224 
0225 /**
0226  * klist_del - Decrement the reference count of node and try to remove.
0227  * @n: node we're deleting.
0228  */
0229 void klist_del(struct klist_node *n)
0230 {
0231     klist_put(n, true);
0232 }
0233 EXPORT_SYMBOL_GPL(klist_del);
0234 
0235 /**
0236  * klist_remove - Decrement the refcount of node and wait for it to go away.
0237  * @n: node we're removing.
0238  */
0239 void klist_remove(struct klist_node *n)
0240 {
0241     struct klist_waiter waiter;
0242 
0243     waiter.node = n;
0244     waiter.process = current;
0245     waiter.woken = 0;
0246     spin_lock(&klist_remove_lock);
0247     list_add(&waiter.list, &klist_remove_waiters);
0248     spin_unlock(&klist_remove_lock);
0249 
0250     klist_del(n);
0251 
0252     for (;;) {
0253         set_current_state(TASK_UNINTERRUPTIBLE);
0254         if (waiter.woken)
0255             break;
0256         schedule();
0257     }
0258     __set_current_state(TASK_RUNNING);
0259 }
0260 EXPORT_SYMBOL_GPL(klist_remove);
0261 
0262 /**
0263  * klist_node_attached - Say whether a node is bound to a list or not.
0264  * @n: Node that we're testing.
0265  */
0266 int klist_node_attached(struct klist_node *n)
0267 {
0268     return (n->n_klist != NULL);
0269 }
0270 EXPORT_SYMBOL_GPL(klist_node_attached);
0271 
0272 /**
0273  * klist_iter_init_node - Initialize a klist_iter structure.
0274  * @k: klist we're iterating.
0275  * @i: klist_iter we're filling.
0276  * @n: node to start with.
0277  *
0278  * Similar to klist_iter_init(), but starts the action off with @n,
0279  * instead of with the list head.
0280  */
0281 void klist_iter_init_node(struct klist *k, struct klist_iter *i,
0282               struct klist_node *n)
0283 {
0284     i->i_klist = k;
0285     i->i_cur = NULL;
0286     if (n && kref_get_unless_zero(&n->n_ref))
0287         i->i_cur = n;
0288 }
0289 EXPORT_SYMBOL_GPL(klist_iter_init_node);
0290 
0291 /**
0292  * klist_iter_init - Iniitalize a klist_iter structure.
0293  * @k: klist we're iterating.
0294  * @i: klist_iter structure we're filling.
0295  *
0296  * Similar to klist_iter_init_node(), but start with the list head.
0297  */
0298 void klist_iter_init(struct klist *k, struct klist_iter *i)
0299 {
0300     klist_iter_init_node(k, i, NULL);
0301 }
0302 EXPORT_SYMBOL_GPL(klist_iter_init);
0303 
0304 /**
0305  * klist_iter_exit - Finish a list iteration.
0306  * @i: Iterator structure.
0307  *
0308  * Must be called when done iterating over list, as it decrements the
0309  * refcount of the current node. Necessary in case iteration exited before
0310  * the end of the list was reached, and always good form.
0311  */
0312 void klist_iter_exit(struct klist_iter *i)
0313 {
0314     if (i->i_cur) {
0315         klist_put(i->i_cur, false);
0316         i->i_cur = NULL;
0317     }
0318 }
0319 EXPORT_SYMBOL_GPL(klist_iter_exit);
0320 
0321 static struct klist_node *to_klist_node(struct list_head *n)
0322 {
0323     return container_of(n, struct klist_node, n_node);
0324 }
0325 
0326 /**
0327  * klist_prev - Ante up prev node in list.
0328  * @i: Iterator structure.
0329  *
0330  * First grab list lock. Decrement the reference count of the previous
0331  * node, if there was one. Grab the prev node, increment its reference
0332  * count, drop the lock, and return that prev node.
0333  */
0334 struct klist_node *klist_prev(struct klist_iter *i)
0335 {
0336     void (*put)(struct klist_node *) = i->i_klist->put;
0337     struct klist_node *last = i->i_cur;
0338     struct klist_node *prev;
0339 
0340     spin_lock(&i->i_klist->k_lock);
0341 
0342     if (last) {
0343         prev = to_klist_node(last->n_node.prev);
0344         if (!klist_dec_and_del(last))
0345             put = NULL;
0346     } else
0347         prev = to_klist_node(i->i_klist->k_list.prev);
0348 
0349     i->i_cur = NULL;
0350     while (prev != to_klist_node(&i->i_klist->k_list)) {
0351         if (likely(!knode_dead(prev))) {
0352             kref_get(&prev->n_ref);
0353             i->i_cur = prev;
0354             break;
0355         }
0356         prev = to_klist_node(prev->n_node.prev);
0357     }
0358 
0359     spin_unlock(&i->i_klist->k_lock);
0360 
0361     if (put && last)
0362         put(last);
0363     return i->i_cur;
0364 }
0365 EXPORT_SYMBOL_GPL(klist_prev);
0366 
0367 /**
0368  * klist_next - Ante up next node in list.
0369  * @i: Iterator structure.
0370  *
0371  * First grab list lock. Decrement the reference count of the previous
0372  * node, if there was one. Grab the next node, increment its reference
0373  * count, drop the lock, and return that next node.
0374  */
0375 struct klist_node *klist_next(struct klist_iter *i)
0376 {
0377     void (*put)(struct klist_node *) = i->i_klist->put;
0378     struct klist_node *last = i->i_cur;
0379     struct klist_node *next;
0380 
0381     spin_lock(&i->i_klist->k_lock);
0382 
0383     if (last) {
0384         next = to_klist_node(last->n_node.next);
0385         if (!klist_dec_and_del(last))
0386             put = NULL;
0387     } else
0388         next = to_klist_node(i->i_klist->k_list.next);
0389 
0390     i->i_cur = NULL;
0391     while (next != to_klist_node(&i->i_klist->k_list)) {
0392         if (likely(!knode_dead(next))) {
0393             kref_get(&next->n_ref);
0394             i->i_cur = next;
0395             break;
0396         }
0397         next = to_klist_node(next->n_node.next);
0398     }
0399 
0400     spin_unlock(&i->i_klist->k_lock);
0401 
0402     if (put && last)
0403         put(last);
0404     return i->i_cur;
0405 }
0406 EXPORT_SYMBOL_GPL(klist_next);