19a19fea4Smochel@digitalimplant.org /* 29a19fea4Smochel@digitalimplant.org * klist.c - Routines for manipulating klists. 39a19fea4Smochel@digitalimplant.org * 49a19fea4Smochel@digitalimplant.org * 59a19fea4Smochel@digitalimplant.org * This klist interface provides a couple of structures that wrap around 69a19fea4Smochel@digitalimplant.org * struct list_head to provide explicit list "head" (struct klist) and 79a19fea4Smochel@digitalimplant.org * list "node" (struct klist_node) objects. For struct klist, a spinlock 89a19fea4Smochel@digitalimplant.org * is included that protects access to the actual list itself. struct 99a19fea4Smochel@digitalimplant.org * klist_node provides a pointer to the klist that owns it and a kref 109a19fea4Smochel@digitalimplant.org * reference count that indicates the number of current users of that node 119a19fea4Smochel@digitalimplant.org * in the list. 129a19fea4Smochel@digitalimplant.org * 139a19fea4Smochel@digitalimplant.org * The entire point is to provide an interface for iterating over a list 149a19fea4Smochel@digitalimplant.org * that is safe and allows for modification of the list during the 159a19fea4Smochel@digitalimplant.org * iteration (e.g. insertion and removal), including modification of the 169a19fea4Smochel@digitalimplant.org * current node on the list. 179a19fea4Smochel@digitalimplant.org * 189a19fea4Smochel@digitalimplant.org * It works using a 3rd object type - struct klist_iter - that is declared 199a19fea4Smochel@digitalimplant.org * and initialized before an iteration. klist_next() is used to acquire the 209a19fea4Smochel@digitalimplant.org * next element in the list. It returns NULL if there are no more items. 219a19fea4Smochel@digitalimplant.org * Internally, that routine takes the klist's lock, decrements the reference 229a19fea4Smochel@digitalimplant.org * count of the previous klist_node and increments the count of the next 239a19fea4Smochel@digitalimplant.org * klist_node. It then drops the lock and returns. 249a19fea4Smochel@digitalimplant.org * 259a19fea4Smochel@digitalimplant.org * There are primitives for adding and removing nodes to/from a klist. 269a19fea4Smochel@digitalimplant.org * When deleting, klist_del() will simply decrement the reference count. 279a19fea4Smochel@digitalimplant.org * Only when the count goes to 0 is the node removed from the list. 289a19fea4Smochel@digitalimplant.org * klist_remove() will try to delete the node from the list and block 299a19fea4Smochel@digitalimplant.org * until it is actually removed. This is useful for objects (like devices) 309a19fea4Smochel@digitalimplant.org * that have been removed from the system and must be freed (but must wait 319a19fea4Smochel@digitalimplant.org * until all accessors have finished). 329a19fea4Smochel@digitalimplant.org * 339a19fea4Smochel@digitalimplant.org * Copyright (C) 2005 Patrick Mochel 349a19fea4Smochel@digitalimplant.org * 359a19fea4Smochel@digitalimplant.org * This file is released under the GPL v2. 369a19fea4Smochel@digitalimplant.org */ 379a19fea4Smochel@digitalimplant.org 389a19fea4Smochel@digitalimplant.org #include <linux/klist.h> 399a19fea4Smochel@digitalimplant.org #include <linux/module.h> 409a19fea4Smochel@digitalimplant.org 419a19fea4Smochel@digitalimplant.org 429a19fea4Smochel@digitalimplant.org /** 439a19fea4Smochel@digitalimplant.org * klist_init - Initialize a klist structure. 449a19fea4Smochel@digitalimplant.org * @k: The klist we're initializing. 45*34bb61f9SJames Bottomley * @get: The get function for the embedding object (NULL if none) 46*34bb61f9SJames Bottomley * @put: The put function for the embedding object (NULL if none) 47*34bb61f9SJames Bottomley * 48*34bb61f9SJames Bottomley * Initialises the klist structure. If the klist_node structures are 49*34bb61f9SJames Bottomley * going to be embedded in refcounted objects (necessary for safe 50*34bb61f9SJames Bottomley * deletion) then the get/put arguments are used to initialise 51*34bb61f9SJames Bottomley * functions that take and release references on the embedding 52*34bb61f9SJames Bottomley * objects. 539a19fea4Smochel@digitalimplant.org */ 549a19fea4Smochel@digitalimplant.org 55*34bb61f9SJames Bottomley void klist_init(struct klist * k, void (*get)(struct klist_node *), 56*34bb61f9SJames Bottomley void (*put)(struct klist_node *)) 579a19fea4Smochel@digitalimplant.org { 589a19fea4Smochel@digitalimplant.org INIT_LIST_HEAD(&k->k_list); 599a19fea4Smochel@digitalimplant.org spin_lock_init(&k->k_lock); 60*34bb61f9SJames Bottomley k->get = get; 61*34bb61f9SJames Bottomley k->put = put; 629a19fea4Smochel@digitalimplant.org } 639a19fea4Smochel@digitalimplant.org 649a19fea4Smochel@digitalimplant.org EXPORT_SYMBOL_GPL(klist_init); 659a19fea4Smochel@digitalimplant.org 669a19fea4Smochel@digitalimplant.org 679a19fea4Smochel@digitalimplant.org static void add_head(struct klist * k, struct klist_node * n) 689a19fea4Smochel@digitalimplant.org { 699a19fea4Smochel@digitalimplant.org spin_lock(&k->k_lock); 709a19fea4Smochel@digitalimplant.org list_add(&n->n_node, &k->k_list); 719a19fea4Smochel@digitalimplant.org spin_unlock(&k->k_lock); 729a19fea4Smochel@digitalimplant.org } 739a19fea4Smochel@digitalimplant.org 749a19fea4Smochel@digitalimplant.org static void add_tail(struct klist * k, struct klist_node * n) 759a19fea4Smochel@digitalimplant.org { 769a19fea4Smochel@digitalimplant.org spin_lock(&k->k_lock); 779a19fea4Smochel@digitalimplant.org list_add_tail(&n->n_node, &k->k_list); 789a19fea4Smochel@digitalimplant.org spin_unlock(&k->k_lock); 799a19fea4Smochel@digitalimplant.org } 809a19fea4Smochel@digitalimplant.org 819a19fea4Smochel@digitalimplant.org 829a19fea4Smochel@digitalimplant.org static void klist_node_init(struct klist * k, struct klist_node * n) 839a19fea4Smochel@digitalimplant.org { 849a19fea4Smochel@digitalimplant.org INIT_LIST_HEAD(&n->n_node); 859a19fea4Smochel@digitalimplant.org init_completion(&n->n_removed); 869a19fea4Smochel@digitalimplant.org kref_init(&n->n_ref); 879a19fea4Smochel@digitalimplant.org n->n_klist = k; 88*34bb61f9SJames Bottomley if (k->get) 89*34bb61f9SJames Bottomley k->get(n); 909a19fea4Smochel@digitalimplant.org } 919a19fea4Smochel@digitalimplant.org 929a19fea4Smochel@digitalimplant.org 939a19fea4Smochel@digitalimplant.org /** 949a19fea4Smochel@digitalimplant.org * klist_add_head - Initialize a klist_node and add it to front. 959a19fea4Smochel@digitalimplant.org * @n: node we're adding. 96d856f1e3SJames Bottomley * @k: klist it's going on. 979a19fea4Smochel@digitalimplant.org */ 989a19fea4Smochel@digitalimplant.org 99d856f1e3SJames Bottomley void klist_add_head(struct klist_node * n, struct klist * k) 1009a19fea4Smochel@digitalimplant.org { 1019a19fea4Smochel@digitalimplant.org klist_node_init(k, n); 1029a19fea4Smochel@digitalimplant.org add_head(k, n); 1039a19fea4Smochel@digitalimplant.org } 1049a19fea4Smochel@digitalimplant.org 1059a19fea4Smochel@digitalimplant.org EXPORT_SYMBOL_GPL(klist_add_head); 1069a19fea4Smochel@digitalimplant.org 1079a19fea4Smochel@digitalimplant.org 1089a19fea4Smochel@digitalimplant.org /** 1099a19fea4Smochel@digitalimplant.org * klist_add_tail - Initialize a klist_node and add it to back. 1109a19fea4Smochel@digitalimplant.org * @n: node we're adding. 111d856f1e3SJames Bottomley * @k: klist it's going on. 1129a19fea4Smochel@digitalimplant.org */ 1139a19fea4Smochel@digitalimplant.org 114d856f1e3SJames Bottomley void klist_add_tail(struct klist_node * n, struct klist * k) 1159a19fea4Smochel@digitalimplant.org { 1169a19fea4Smochel@digitalimplant.org klist_node_init(k, n); 1179a19fea4Smochel@digitalimplant.org add_tail(k, n); 1189a19fea4Smochel@digitalimplant.org } 1199a19fea4Smochel@digitalimplant.org 1209a19fea4Smochel@digitalimplant.org EXPORT_SYMBOL_GPL(klist_add_tail); 1219a19fea4Smochel@digitalimplant.org 1229a19fea4Smochel@digitalimplant.org 1239a19fea4Smochel@digitalimplant.org static void klist_release(struct kref * kref) 1249a19fea4Smochel@digitalimplant.org { 1259a19fea4Smochel@digitalimplant.org struct klist_node * n = container_of(kref, struct klist_node, n_ref); 126*34bb61f9SJames Bottomley void (*put)(struct klist_node *) = n->n_klist->put; 1279a19fea4Smochel@digitalimplant.org list_del(&n->n_node); 1289a19fea4Smochel@digitalimplant.org complete(&n->n_removed); 1298b0c250bSmochel@digitalimplant.org n->n_klist = NULL; 130*34bb61f9SJames Bottomley if (put) 131*34bb61f9SJames Bottomley put(n); 1329a19fea4Smochel@digitalimplant.org } 1339a19fea4Smochel@digitalimplant.org 1349a19fea4Smochel@digitalimplant.org static int klist_dec_and_del(struct klist_node * n) 1359a19fea4Smochel@digitalimplant.org { 1369a19fea4Smochel@digitalimplant.org return kref_put(&n->n_ref, klist_release); 1379a19fea4Smochel@digitalimplant.org } 1389a19fea4Smochel@digitalimplant.org 1399a19fea4Smochel@digitalimplant.org 1409a19fea4Smochel@digitalimplant.org /** 1419a19fea4Smochel@digitalimplant.org * klist_del - Decrement the reference count of node and try to remove. 1429a19fea4Smochel@digitalimplant.org * @n: node we're deleting. 1439a19fea4Smochel@digitalimplant.org */ 1449a19fea4Smochel@digitalimplant.org 1459a19fea4Smochel@digitalimplant.org void klist_del(struct klist_node * n) 1469a19fea4Smochel@digitalimplant.org { 1479a19fea4Smochel@digitalimplant.org struct klist * k = n->n_klist; 1489a19fea4Smochel@digitalimplant.org 1499a19fea4Smochel@digitalimplant.org spin_lock(&k->k_lock); 1509a19fea4Smochel@digitalimplant.org klist_dec_and_del(n); 1519a19fea4Smochel@digitalimplant.org spin_unlock(&k->k_lock); 1529a19fea4Smochel@digitalimplant.org } 1539a19fea4Smochel@digitalimplant.org 1549a19fea4Smochel@digitalimplant.org EXPORT_SYMBOL_GPL(klist_del); 1559a19fea4Smochel@digitalimplant.org 1569a19fea4Smochel@digitalimplant.org 1579a19fea4Smochel@digitalimplant.org /** 1589a19fea4Smochel@digitalimplant.org * klist_remove - Decrement the refcount of node and wait for it to go away. 1599a19fea4Smochel@digitalimplant.org * @n: node we're removing. 1609a19fea4Smochel@digitalimplant.org */ 1619a19fea4Smochel@digitalimplant.org 1629a19fea4Smochel@digitalimplant.org void klist_remove(struct klist_node * n) 1639a19fea4Smochel@digitalimplant.org { 1640293a509Smochel@digitalimplant.org struct klist * k = n->n_klist; 1650293a509Smochel@digitalimplant.org spin_lock(&k->k_lock); 1669a19fea4Smochel@digitalimplant.org klist_dec_and_del(n); 1670293a509Smochel@digitalimplant.org spin_unlock(&k->k_lock); 1689a19fea4Smochel@digitalimplant.org wait_for_completion(&n->n_removed); 1699a19fea4Smochel@digitalimplant.org } 1709a19fea4Smochel@digitalimplant.org 1719a19fea4Smochel@digitalimplant.org EXPORT_SYMBOL_GPL(klist_remove); 1729a19fea4Smochel@digitalimplant.org 1739a19fea4Smochel@digitalimplant.org 1749a19fea4Smochel@digitalimplant.org /** 1758b0c250bSmochel@digitalimplant.org * klist_node_attached - Say whether a node is bound to a list or not. 1768b0c250bSmochel@digitalimplant.org * @n: Node that we're testing. 1778b0c250bSmochel@digitalimplant.org */ 1788b0c250bSmochel@digitalimplant.org 1798b0c250bSmochel@digitalimplant.org int klist_node_attached(struct klist_node * n) 1808b0c250bSmochel@digitalimplant.org { 1818b0c250bSmochel@digitalimplant.org return (n->n_klist != NULL); 1828b0c250bSmochel@digitalimplant.org } 1838b0c250bSmochel@digitalimplant.org 1848b0c250bSmochel@digitalimplant.org EXPORT_SYMBOL_GPL(klist_node_attached); 1858b0c250bSmochel@digitalimplant.org 1868b0c250bSmochel@digitalimplant.org 1878b0c250bSmochel@digitalimplant.org /** 1889a19fea4Smochel@digitalimplant.org * klist_iter_init_node - Initialize a klist_iter structure. 1899a19fea4Smochel@digitalimplant.org * @k: klist we're iterating. 1909a19fea4Smochel@digitalimplant.org * @i: klist_iter we're filling. 1919a19fea4Smochel@digitalimplant.org * @n: node to start with. 1929a19fea4Smochel@digitalimplant.org * 1939a19fea4Smochel@digitalimplant.org * Similar to klist_iter_init(), but starts the action off with @n, 1949a19fea4Smochel@digitalimplant.org * instead of with the list head. 1959a19fea4Smochel@digitalimplant.org */ 1969a19fea4Smochel@digitalimplant.org 1979a19fea4Smochel@digitalimplant.org void klist_iter_init_node(struct klist * k, struct klist_iter * i, struct klist_node * n) 1989a19fea4Smochel@digitalimplant.org { 1999a19fea4Smochel@digitalimplant.org i->i_klist = k; 2009a19fea4Smochel@digitalimplant.org i->i_head = &k->k_list; 2019a19fea4Smochel@digitalimplant.org i->i_cur = n; 2029a19fea4Smochel@digitalimplant.org } 2039a19fea4Smochel@digitalimplant.org 2049a19fea4Smochel@digitalimplant.org EXPORT_SYMBOL_GPL(klist_iter_init_node); 2059a19fea4Smochel@digitalimplant.org 2069a19fea4Smochel@digitalimplant.org 2079a19fea4Smochel@digitalimplant.org /** 2089a19fea4Smochel@digitalimplant.org * klist_iter_init - Iniitalize a klist_iter structure. 2099a19fea4Smochel@digitalimplant.org * @k: klist we're iterating. 2109a19fea4Smochel@digitalimplant.org * @i: klist_iter structure we're filling. 2119a19fea4Smochel@digitalimplant.org * 2129a19fea4Smochel@digitalimplant.org * Similar to klist_iter_init_node(), but start with the list head. 2139a19fea4Smochel@digitalimplant.org */ 2149a19fea4Smochel@digitalimplant.org 2159a19fea4Smochel@digitalimplant.org void klist_iter_init(struct klist * k, struct klist_iter * i) 2169a19fea4Smochel@digitalimplant.org { 2179a19fea4Smochel@digitalimplant.org klist_iter_init_node(k, i, NULL); 2189a19fea4Smochel@digitalimplant.org } 2199a19fea4Smochel@digitalimplant.org 2209a19fea4Smochel@digitalimplant.org EXPORT_SYMBOL_GPL(klist_iter_init); 2219a19fea4Smochel@digitalimplant.org 2229a19fea4Smochel@digitalimplant.org 2239a19fea4Smochel@digitalimplant.org /** 2249a19fea4Smochel@digitalimplant.org * klist_iter_exit - Finish a list iteration. 2259a19fea4Smochel@digitalimplant.org * @i: Iterator structure. 2269a19fea4Smochel@digitalimplant.org * 2279a19fea4Smochel@digitalimplant.org * Must be called when done iterating over list, as it decrements the 2289a19fea4Smochel@digitalimplant.org * refcount of the current node. Necessary in case iteration exited before 2299a19fea4Smochel@digitalimplant.org * the end of the list was reached, and always good form. 2309a19fea4Smochel@digitalimplant.org */ 2319a19fea4Smochel@digitalimplant.org 2329a19fea4Smochel@digitalimplant.org void klist_iter_exit(struct klist_iter * i) 2339a19fea4Smochel@digitalimplant.org { 2349a19fea4Smochel@digitalimplant.org if (i->i_cur) { 2359a19fea4Smochel@digitalimplant.org klist_del(i->i_cur); 2369a19fea4Smochel@digitalimplant.org i->i_cur = NULL; 2379a19fea4Smochel@digitalimplant.org } 2389a19fea4Smochel@digitalimplant.org } 2399a19fea4Smochel@digitalimplant.org 2409a19fea4Smochel@digitalimplant.org EXPORT_SYMBOL_GPL(klist_iter_exit); 2419a19fea4Smochel@digitalimplant.org 2429a19fea4Smochel@digitalimplant.org 2439a19fea4Smochel@digitalimplant.org static struct klist_node * to_klist_node(struct list_head * n) 2449a19fea4Smochel@digitalimplant.org { 2459a19fea4Smochel@digitalimplant.org return container_of(n, struct klist_node, n_node); 2469a19fea4Smochel@digitalimplant.org } 2479a19fea4Smochel@digitalimplant.org 2489a19fea4Smochel@digitalimplant.org 2499a19fea4Smochel@digitalimplant.org /** 2509a19fea4Smochel@digitalimplant.org * klist_next - Ante up next node in list. 2519a19fea4Smochel@digitalimplant.org * @i: Iterator structure. 2529a19fea4Smochel@digitalimplant.org * 2539a19fea4Smochel@digitalimplant.org * First grab list lock. Decrement the reference count of the previous 2549a19fea4Smochel@digitalimplant.org * node, if there was one. Grab the next node, increment its reference 2559a19fea4Smochel@digitalimplant.org * count, drop the lock, and return that next node. 2569a19fea4Smochel@digitalimplant.org */ 2579a19fea4Smochel@digitalimplant.org 2589a19fea4Smochel@digitalimplant.org struct klist_node * klist_next(struct klist_iter * i) 2599a19fea4Smochel@digitalimplant.org { 2609a19fea4Smochel@digitalimplant.org struct list_head * next; 2619a19fea4Smochel@digitalimplant.org struct klist_node * knode = NULL; 2629a19fea4Smochel@digitalimplant.org 2639a19fea4Smochel@digitalimplant.org spin_lock(&i->i_klist->k_lock); 2649a19fea4Smochel@digitalimplant.org if (i->i_cur) { 2659a19fea4Smochel@digitalimplant.org next = i->i_cur->n_node.next; 2669a19fea4Smochel@digitalimplant.org klist_dec_and_del(i->i_cur); 2679a19fea4Smochel@digitalimplant.org } else 2689a19fea4Smochel@digitalimplant.org next = i->i_head->next; 2699a19fea4Smochel@digitalimplant.org 2709a19fea4Smochel@digitalimplant.org if (next != i->i_head) { 2719a19fea4Smochel@digitalimplant.org knode = to_klist_node(next); 2729a19fea4Smochel@digitalimplant.org kref_get(&knode->n_ref); 2739a19fea4Smochel@digitalimplant.org } 2749a19fea4Smochel@digitalimplant.org i->i_cur = knode; 2759a19fea4Smochel@digitalimplant.org spin_unlock(&i->i_klist->k_lock); 2769a19fea4Smochel@digitalimplant.org return knode; 2779a19fea4Smochel@digitalimplant.org } 2789a19fea4Smochel@digitalimplant.org 2799a19fea4Smochel@digitalimplant.org EXPORT_SYMBOL_GPL(klist_next); 2808b0c250bSmochel@digitalimplant.org 2818b0c250bSmochel@digitalimplant.org 282