klist.c 10.3 KB
Newer Older
1
/*
2
 * klist.c - Routines for manipulating klists.
3
 *
4
 * Copyright (C) 2005 Patrick Mochel
5
 *
6
 * This file is released under the GPL v2.
7
 *
8 9 10 11 12 13 14
 * This klist interface provides a couple of structures that wrap around
 * struct list_head to provide explicit list "head" (struct klist) and list
 * "node" (struct klist_node) objects. For struct klist, a spinlock is
 * included that protects access to the actual list itself. struct
 * klist_node provides a pointer to the klist that owns it and a kref
 * reference count that indicates the number of current users of that node
 * in the list.
15
 *
16 17 18 19
 * The entire point is to provide an interface for iterating over a list
 * that is safe and allows for modification of the list during the
 * iteration (e.g. insertion and removal), including modification of the
 * current node on the list.
20
 *
21 22 23 24 25 26
 * It works using a 3rd object type - struct klist_iter - that is declared
 * and initialized before an iteration. klist_next() is used to acquire the
 * next element in the list. It returns NULL if there are no more items.
 * Internally, that routine takes the klist's lock, decrements the
 * reference count of the previous klist_node and increments the count of
 * the next klist_node. It then drops the lock and returns.
27
 *
28 29 30 31 32 33 34
 * There are primitives for adding and removing nodes to/from a klist.
 * When deleting, klist_del() will simply decrement the reference count.
 * Only when the count goes to 0 is the node removed from the list.
 * klist_remove() will try to delete the node from the list and block until
 * it is actually removed. This is useful for objects (like devices) that
 * have been removed from the system and must be freed (but must wait until
 * all accessors have finished).
35 36 37
 */

#include <linux/klist.h>
38
#include <linux/export.h>
39
#include <linux/sched.h>
40

41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
/*
 * Use the lowest bit of n_klist to mark deleted nodes and exclude
 * dead ones from iteration.
 */
#define KNODE_DEAD		1LU
#define KNODE_KLIST_MASK	~KNODE_DEAD

static struct klist *knode_klist(struct klist_node *knode)
{
	return (struct klist *)
		((unsigned long)knode->n_klist & KNODE_KLIST_MASK);
}

static bool knode_dead(struct klist_node *knode)
{
	return (unsigned long)knode->n_klist & KNODE_DEAD;
}

static void knode_set_klist(struct klist_node *knode, struct klist *klist)
{
	knode->n_klist = klist;
	/* no knode deserves to start its life dead */
	WARN_ON(knode_dead(knode));
}

static void knode_kill(struct klist_node *knode)
{
	/* and no knode should die twice ever either, see we're very humane */
	WARN_ON(knode_dead(knode));
	*(unsigned long *)&knode->n_klist |= KNODE_DEAD;
}
72 73

/**
74 75 76 77
 * klist_init - Initialize a klist structure.
 * @k: The klist we're initializing.
 * @get: The get function for the embedding object (NULL if none)
 * @put: The put function for the embedding object (NULL if none)
78 79 80 81 82 83
 *
 * Initialises the klist structure.  If the klist_node structures are
 * going to be embedded in refcounted objects (necessary for safe
 * deletion) then the get/put arguments are used to initialise
 * functions that take and release references on the embedding
 * objects.
84
 */
85
void klist_init(struct klist *k, void (*get)(struct klist_node *),
86
		void (*put)(struct klist_node *))
87 88 89
{
	INIT_LIST_HEAD(&k->k_list);
	spin_lock_init(&k->k_lock);
90 91
	k->get = get;
	k->put = put;
92 93 94
}
EXPORT_SYMBOL_GPL(klist_init);

95
static void add_head(struct klist *k, struct klist_node *n)
96 97 98 99 100 101
{
	spin_lock(&k->k_lock);
	list_add(&n->n_node, &k->k_list);
	spin_unlock(&k->k_lock);
}

102
static void add_tail(struct klist *k, struct klist_node *n)
103 104 105 106 107 108
{
	spin_lock(&k->k_lock);
	list_add_tail(&n->n_node, &k->k_list);
	spin_unlock(&k->k_lock);
}

109
static void klist_node_init(struct klist *k, struct klist_node *n)
110 111 112
{
	INIT_LIST_HEAD(&n->n_node);
	kref_init(&n->n_ref);
113
	knode_set_klist(n, k);
114 115
	if (k->get)
		k->get(n);
116 117 118
}

/**
119 120 121
 * klist_add_head - Initialize a klist_node and add it to front.
 * @n: node we're adding.
 * @k: klist it's going on.
122
 */
123
void klist_add_head(struct klist_node *n, struct klist *k)
124 125 126 127 128 129 130
{
	klist_node_init(k, n);
	add_head(k, n);
}
EXPORT_SYMBOL_GPL(klist_add_head);

/**
131 132 133
 * klist_add_tail - Initialize a klist_node and add it to back.
 * @n: node we're adding.
 * @k: klist it's going on.
134
 */
135
void klist_add_tail(struct klist_node *n, struct klist *k)
136 137 138 139 140 141
{
	klist_node_init(k, n);
	add_tail(k, n);
}
EXPORT_SYMBOL_GPL(klist_add_tail);

142
/**
143
 * klist_add_behind - Init a klist_node and add it after an existing node
144 145 146
 * @n: node we're adding.
 * @pos: node to put @n after
 */
147
void klist_add_behind(struct klist_node *n, struct klist_node *pos)
148
{
149
	struct klist *k = knode_klist(pos);
150 151 152 153 154 155

	klist_node_init(k, n);
	spin_lock(&k->k_lock);
	list_add(&n->n_node, &pos->n_node);
	spin_unlock(&k->k_lock);
}
156
EXPORT_SYMBOL_GPL(klist_add_behind);
157 158 159 160 161 162 163 164

/**
 * klist_add_before - Init a klist_node and add it before an existing node
 * @n: node we're adding.
 * @pos: node to put @n after
 */
void klist_add_before(struct klist_node *n, struct klist_node *pos)
{
165
	struct klist *k = knode_klist(pos);
166 167 168 169 170 171 172 173

	klist_node_init(k, n);
	spin_lock(&k->k_lock);
	list_add_tail(&n->n_node, &pos->n_node);
	spin_unlock(&k->k_lock);
}
EXPORT_SYMBOL_GPL(klist_add_before);

174 175 176 177 178 179 180 181 182 183
struct klist_waiter {
	struct list_head list;
	struct klist_node *node;
	struct task_struct *process;
	int woken;
};

static DEFINE_SPINLOCK(klist_remove_lock);
static LIST_HEAD(klist_remove_waiters);

184
static void klist_release(struct kref *kref)
185
{
186
	struct klist_waiter *waiter, *tmp;
187
	struct klist_node *n = container_of(kref, struct klist_node, n_ref);
188

189
	WARN_ON(!knode_dead(n));
190
	list_del(&n->n_node);
191 192 193 194 195
	spin_lock(&klist_remove_lock);
	list_for_each_entry_safe(waiter, tmp, &klist_remove_waiters, list) {
		if (waiter->node != n)
			continue;

196
		list_del(&waiter->list);
197 198 199 200 201
		waiter->woken = 1;
		mb();
		wake_up_process(waiter->process);
	}
	spin_unlock(&klist_remove_lock);
202
	knode_set_klist(n, NULL);
203 204
}

205
static int klist_dec_and_del(struct klist_node *n)
206 207 208 209
{
	return kref_put(&n->n_ref, klist_release);
}

210
static void klist_put(struct klist_node *n, bool kill)
211
{
212
	struct klist *k = knode_klist(n);
213
	void (*put)(struct klist_node *) = k->put;
214 215

	spin_lock(&k->k_lock);
216 217
	if (kill)
		knode_kill(n);
218 219
	if (!klist_dec_and_del(n))
		put = NULL;
220
	spin_unlock(&k->k_lock);
221 222
	if (put)
		put(n);
223
}
224 225 226 227 228 229 230 231 232

/**
 * klist_del - Decrement the reference count of node and try to remove.
 * @n: node we're deleting.
 */
void klist_del(struct klist_node *n)
{
	klist_put(n, true);
}
233 234 235
EXPORT_SYMBOL_GPL(klist_del);

/**
236 237
 * klist_remove - Decrement the refcount of node and wait for it to go away.
 * @n: node we're removing.
238
 */
239
void klist_remove(struct klist_node *n)
240
{
241 242 243 244 245 246 247 248 249
	struct klist_waiter waiter;

	waiter.node = n;
	waiter.process = current;
	waiter.woken = 0;
	spin_lock(&klist_remove_lock);
	list_add(&waiter.list, &klist_remove_waiters);
	spin_unlock(&klist_remove_lock);

250
	klist_del(n);
251 252 253 254 255 256 257 258

	for (;;) {
		set_current_state(TASK_UNINTERRUPTIBLE);
		if (waiter.woken)
			break;
		schedule();
	}
	__set_current_state(TASK_RUNNING);
259 260 261
}
EXPORT_SYMBOL_GPL(klist_remove);

262
/**
263 264
 * klist_node_attached - Say whether a node is bound to a list or not.
 * @n: Node that we're testing.
265
 */
266
int klist_node_attached(struct klist_node *n)
267 268 269 270 271
{
	return (n->n_klist != NULL);
}
EXPORT_SYMBOL_GPL(klist_node_attached);

272
/**
273 274 275 276
 * klist_iter_init_node - Initialize a klist_iter structure.
 * @k: klist we're iterating.
 * @i: klist_iter we're filling.
 * @n: node to start with.
277
 *
278 279
 * Similar to klist_iter_init(), but starts the action off with @n,
 * instead of with the list head.
280
 */
281 282
void klist_iter_init_node(struct klist *k, struct klist_iter *i,
			  struct klist_node *n)
283 284
{
	i->i_klist = k;
285 286 287
	i->i_cur = NULL;
	if (n && kref_get_unless_zero(&n->n_ref))
		i->i_cur = n;
288 289 290 291
}
EXPORT_SYMBOL_GPL(klist_iter_init_node);

/**
292 293 294
 * klist_iter_init - Iniitalize a klist_iter structure.
 * @k: klist we're iterating.
 * @i: klist_iter structure we're filling.
295
 *
296
 * Similar to klist_iter_init_node(), but start with the list head.
297
 */
298
void klist_iter_init(struct klist *k, struct klist_iter *i)
299 300 301 302 303 304
{
	klist_iter_init_node(k, i, NULL);
}
EXPORT_SYMBOL_GPL(klist_iter_init);

/**
305 306
 * klist_iter_exit - Finish a list iteration.
 * @i: Iterator structure.
307
 *
308 309 310
 * Must be called when done iterating over list, as it decrements the
 * refcount of the current node. Necessary in case iteration exited before
 * the end of the list was reached, and always good form.
311
 */
312
void klist_iter_exit(struct klist_iter *i)
313 314
{
	if (i->i_cur) {
315
		klist_put(i->i_cur, false);
316 317 318 319 320
		i->i_cur = NULL;
	}
}
EXPORT_SYMBOL_GPL(klist_iter_exit);

321
static struct klist_node *to_klist_node(struct list_head *n)
322 323 324 325
{
	return container_of(n, struct klist_node, n_node);
}

326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366
/**
 * klist_prev - Ante up prev node in list.
 * @i: Iterator structure.
 *
 * First grab list lock. Decrement the reference count of the previous
 * node, if there was one. Grab the prev node, increment its reference
 * count, drop the lock, and return that prev node.
 */
struct klist_node *klist_prev(struct klist_iter *i)
{
	void (*put)(struct klist_node *) = i->i_klist->put;
	struct klist_node *last = i->i_cur;
	struct klist_node *prev;

	spin_lock(&i->i_klist->k_lock);

	if (last) {
		prev = to_klist_node(last->n_node.prev);
		if (!klist_dec_and_del(last))
			put = NULL;
	} else
		prev = to_klist_node(i->i_klist->k_list.prev);

	i->i_cur = NULL;
	while (prev != to_klist_node(&i->i_klist->k_list)) {
		if (likely(!knode_dead(prev))) {
			kref_get(&prev->n_ref);
			i->i_cur = prev;
			break;
		}
		prev = to_klist_node(prev->n_node.prev);
	}

	spin_unlock(&i->i_klist->k_lock);

	if (put && last)
		put(last);
	return i->i_cur;
}
EXPORT_SYMBOL_GPL(klist_prev);

367
/**
368 369
 * klist_next - Ante up next node in list.
 * @i: Iterator structure.
370
 *
371 372 373
 * First grab list lock. Decrement the reference count of the previous
 * node, if there was one. Grab the next node, increment its reference
 * count, drop the lock, and return that next node.
374
 */
375
struct klist_node *klist_next(struct klist_iter *i)
376
{
377
	void (*put)(struct klist_node *) = i->i_klist->put;
378 379
	struct klist_node *last = i->i_cur;
	struct klist_node *next;
380 381

	spin_lock(&i->i_klist->k_lock);
382 383 384 385

	if (last) {
		next = to_klist_node(last->n_node.next);
		if (!klist_dec_and_del(last))
386
			put = NULL;
387
	} else
388
		next = to_klist_node(i->i_klist->k_list.next);
389

390 391 392 393 394 395 396 397
	i->i_cur = NULL;
	while (next != to_klist_node(&i->i_klist->k_list)) {
		if (likely(!knode_dead(next))) {
			kref_get(&next->n_ref);
			i->i_cur = next;
			break;
		}
		next = to_klist_node(next->n_node.next);
398
	}
399

400
	spin_unlock(&i->i_klist->k_lock);
401 402 403 404

	if (put && last)
		put(last);
	return i->i_cur;
405 406
}
EXPORT_SYMBOL_GPL(klist_next);