list_lru.c revision a38e40824844a5ec85f3ea95632be953477d2afa 
1/*
2 * Copyright (c) 2013 Red Hat, Inc. and Parallels Inc. All rights reserved.
3 * Authors: David Chinner and Glauber Costa
4 *
5 * Generic LRU infrastructure
6 */
7#include <linux/kernel.h>
8#include <linux/module.h>
9#include <linux/list_lru.h>
10
11bool list_lru_add(struct list_lru *lru, struct list_head *item)
12{
13	spin_lock(&lru->lock);
14	if (list_empty(item)) {
15		list_add_tail(item, &lru->list);
16		lru->nr_items++;
17		spin_unlock(&lru->lock);
18		return true;
19	}
20	spin_unlock(&lru->lock);
21	return false;
22}
23EXPORT_SYMBOL_GPL(list_lru_add);
24
25bool list_lru_del(struct list_lru *lru, struct list_head *item)
26{
27	spin_lock(&lru->lock);
28	if (!list_empty(item)) {
29		list_del_init(item);
30		lru->nr_items--;
31		spin_unlock(&lru->lock);
32		return true;
33	}
34	spin_unlock(&lru->lock);
35	return false;
36}
37EXPORT_SYMBOL_GPL(list_lru_del);
38
39unsigned long list_lru_walk(struct list_lru *lru, list_lru_walk_cb isolate,
40			    void *cb_arg, unsigned long nr_to_walk)
41{
42	struct list_head *item, *n;
43	unsigned long removed = 0;
44	/*
45	 * If we don't keep state of at which pass we are, we can loop at
46	 * LRU_RETRY, since we have no guarantees that the caller will be able
47	 * to do something other than retry on the next pass. We handle this by
48	 * allowing at most one retry per object. This should not be altered
49	 * by any condition other than LRU_RETRY.
50	 */
51	bool first_pass = true;
52
53	spin_lock(&lru->lock);
54restart:
55	list_for_each_safe(item, n, &lru->list) {
56		enum lru_status ret;
57		ret = isolate(item, &lru->lock, cb_arg);
58		switch (ret) {
59		case LRU_REMOVED:
60			lru->nr_items--;
61			removed++;
62			break;
63		case LRU_ROTATE:
64			list_move_tail(item, &lru->list);
65			break;
66		case LRU_SKIP:
67			break;
68		case LRU_RETRY:
69			if (!first_pass) {
70				first_pass = true;
71				break;
72			}
73			first_pass = false;
74			goto restart;
75		default:
76			BUG();
77		}
78
79		if (nr_to_walk-- == 0)
80			break;
81
82	}
83	spin_unlock(&lru->lock);
84	return removed;
85}
86EXPORT_SYMBOL_GPL(list_lru_walk);
87
88unsigned long list_lru_dispose_all(struct list_lru *lru,
89				   list_lru_dispose_cb dispose)
90{
91	unsigned long disposed = 0;
92	LIST_HEAD(dispose_list);
93
94	spin_lock(&lru->lock);
95	while (!list_empty(&lru->list)) {
96		list_splice_init(&lru->list, &dispose_list);
97		disposed += lru->nr_items;
98		lru->nr_items = 0;
99		spin_unlock(&lru->lock);
100
101		dispose(&dispose_list);
102
103		spin_lock(&lru->lock);
104	}
105	spin_unlock(&lru->lock);
106	return disposed;
107}
108
109int list_lru_init(struct list_lru *lru)
110{
111	spin_lock_init(&lru->lock);
112	INIT_LIST_HEAD(&lru->list);
113	lru->nr_items = 0;
114
115	return 0;
116}
117EXPORT_SYMBOL_GPL(list_lru_init);
118