[deliverable/linux.git] / mm / list_lru.c

/*
 * Copyright (c) 2013 Red Hat, Inc. and Parallels Inc. All rights reserved.
 * Authors: David Chinner and Glauber Costa
 *
 * Generic LRU infrastructure
 */
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/mm.h>
#include <linux/list_lru.h>
#include <linux/slab.h>
#include <linux/mutex.h>
#include <linux/memcontrol.h>

#ifdef CONFIG_MEMCG_KMEM
static LIST_HEAD(list_lrus);
static DEFINE_MUTEX(list_lrus_mutex);

static void list_lru_register(struct list_lru *lru)
{
	mutex_lock(&list_lrus_mutex);
	list_add(&lru->list, &list_lrus);
	mutex_unlock(&list_lrus_mutex);
}

static void list_lru_unregister(struct list_lru *lru)
{
	mutex_lock(&list_lrus_mutex);
	list_del(&lru->list);
	mutex_unlock(&list_lrus_mutex);
}
#else
static void list_lru_register(struct list_lru *lru)
{
}

static void list_lru_unregister(struct list_lru *lru)
{
}
#endif /* CONFIG_MEMCG_KMEM */

#ifdef CONFIG_MEMCG_KMEM
static inline bool list_lru_memcg_aware(struct list_lru *lru)
{
	/*
	 * This needs node 0 to be always present, even
	 * in the systems supporting sparse numa ids.
	 */
	return !!lru->node[0].memcg_lrus;
}

static inline struct list_lru_one *
list_lru_from_memcg_idx(struct list_lru_node *nlru, int idx)
{
	/*
	 * The lock protects the array of per cgroup lists from relocation
	 * (see memcg_update_list_lru_node).
	 */
	lockdep_assert_held(&nlru->lock);
	if (nlru->memcg_lrus && idx >= 0)
		return nlru->memcg_lrus->lru[idx];

	return &nlru->lru;
}

static inline struct list_lru_one *
list_lru_from_kmem(struct list_lru_node *nlru, void *ptr)
{
	struct mem_cgroup *memcg;

	if (!nlru->memcg_lrus)
		return &nlru->lru;

	memcg = mem_cgroup_from_kmem(ptr);
	if (!memcg)
		return &nlru->lru;

	return list_lru_from_memcg_idx(nlru, memcg_cache_id(memcg));
}
#else
static inline bool list_lru_memcg_aware(struct list_lru *lru)
{
	return false;
}

static inline struct list_lru_one *
list_lru_from_memcg_idx(struct list_lru_node *nlru, int idx)
{
	return &nlru->lru;
}

static inline struct list_lru_one *
list_lru_from_kmem(struct list_lru_node *nlru, void *ptr)
{
	return &nlru->lru;
}
#endif /* CONFIG_MEMCG_KMEM */

bool list_lru_add(struct list_lru *lru, struct list_head *item)
{
	int nid = page_to_nid(virt_to_page(item));
	struct list_lru_node *nlru = &lru->node[nid];
	struct list_lru_one *l;

	spin_lock(&nlru->lock);
	if (list_empty(item)) {
		l = list_lru_from_kmem(nlru, item);
		list_add_tail(item, &l->list);
		l->nr_items++;
		spin_unlock(&nlru->lock);
		return true;
	}
	spin_unlock(&nlru->lock);
	return false;
}
EXPORT_SYMBOL_GPL(list_lru_add);

bool list_lru_del(struct list_lru *lru, struct list_head *item)
{
	int nid = page_to_nid(virt_to_page(item));
	struct list_lru_node *nlru = &lru->node[nid];
	struct list_lru_one *l;

	spin_lock(&nlru->lock);
	if (!list_empty(item)) {
		l = list_lru_from_kmem(nlru, item);
		list_del_init(item);
		l->nr_items--;
		spin_unlock(&nlru->lock);
		return true;
	}
	spin_unlock(&nlru->lock);
	return false;
}
EXPORT_SYMBOL_GPL(list_lru_del);

void list_lru_isolate(struct list_lru_one *list, struct list_head *item)
{
	list_del_init(item);
	list->nr_items--;
}
EXPORT_SYMBOL_GPL(list_lru_isolate);

void list_lru_isolate_move(struct list_lru_one *list, struct list_head *item,
			   struct list_head *head)
{
	list_move(item, head);
	list->nr_items--;
}
EXPORT_SYMBOL_GPL(list_lru_isolate_move);

static unsigned long __list_lru_count_one(struct list_lru *lru,
					  int nid, int memcg_idx)
{
	struct list_lru_node *nlru = &lru->node[nid];
	struct list_lru_one *l;
	unsigned long count;

	spin_lock(&nlru->lock);
	l = list_lru_from_memcg_idx(nlru, memcg_idx);
	count = l->nr_items;
	spin_unlock(&nlru->lock);

	return count;
}

unsigned long list_lru_count_one(struct list_lru *lru,
				 int nid, struct mem_cgroup *memcg)
{
	return __list_lru_count_one(lru, nid, memcg_cache_id(memcg));
}
EXPORT_SYMBOL_GPL(list_lru_count_one);

unsigned long list_lru_count_node(struct list_lru *lru, int nid)
{
	long count = 0;
	int memcg_idx;

	count += __list_lru_count_one(lru, nid, -1);
	if (list_lru_memcg_aware(lru)) {
		for_each_memcg_cache_index(memcg_idx)
			count += __list_lru_count_one(lru, nid, memcg_idx);
	}
	return count;
}
EXPORT_SYMBOL_GPL(list_lru_count_node);

static unsigned long
__list_lru_walk_one(struct list_lru *lru, int nid, int memcg_idx,
		    list_lru_walk_cb isolate, void *cb_arg,
		    unsigned long *nr_to_walk)
{

	struct list_lru_node *nlru = &lru->node[nid];
	struct list_lru_one *l;
	struct list_head *item, *n;
	unsigned long isolated = 0;

	spin_lock(&nlru->lock);
	l = list_lru_from_memcg_idx(nlru, memcg_idx);
restart:
	list_for_each_safe(item, n, &l->list) {
		enum lru_status ret;

		/*
		 * decrement nr_to_walk first so that we don't livelock if we
		 * get stuck on large numbesr of LRU_RETRY items
		 */
		if (!*nr_to_walk)
			break;
		--*nr_to_walk;

		ret = isolate(item, l, &nlru->lock, cb_arg);
		switch (ret) {
		case LRU_REMOVED_RETRY:
			assert_spin_locked(&nlru->lock);
		case LRU_REMOVED:
			isolated++;
			/*
			 * If the lru lock has been dropped, our list
			 * traversal is now invalid and so we have to
			 * restart from scratch.
			 */
			if (ret == LRU_REMOVED_RETRY)
				goto restart;
			break;
		case LRU_ROTATE:
			list_move_tail(item, &l->list);
			break;
		case LRU_SKIP:
			break;
		case LRU_RETRY:
			/*
			 * The lru lock has been dropped, our list traversal is
			 * now invalid and so we have to restart from scratch.
			 */
			assert_spin_locked(&nlru->lock);
			goto restart;
		default:
			BUG();
		}
	}

	spin_unlock(&nlru->lock);
	return isolated;
}

unsigned long
list_lru_walk_one(struct list_lru *lru, int nid, struct mem_cgroup *memcg,
		  list_lru_walk_cb isolate, void *cb_arg,
		  unsigned long *nr_to_walk)
{
	return __list_lru_walk_one(lru, nid, memcg_cache_id(memcg),
				   isolate, cb_arg, nr_to_walk);
}
EXPORT_SYMBOL_GPL(list_lru_walk_one);

unsigned long list_lru_walk_node(struct list_lru *lru, int nid,
				 list_lru_walk_cb isolate, void *cb_arg,
				 unsigned long *nr_to_walk)
{
	long isolated = 0;
	int memcg_idx;

	isolated += __list_lru_walk_one(lru, nid, -1, isolate, cb_arg,
					nr_to_walk);
	if (*nr_to_walk > 0 && list_lru_memcg_aware(lru)) {
		for_each_memcg_cache_index(memcg_idx) {
			isolated += __list_lru_walk_one(lru, nid, memcg_idx,
						isolate, cb_arg, nr_to_walk);
			if (*nr_to_walk <= 0)
				break;
		}
	}
	return isolated;
}
EXPORT_SYMBOL_GPL(list_lru_walk_node);

static void init_one_lru(struct list_lru_one *l)
{
	INIT_LIST_HEAD(&l->list);
	l->nr_items = 0;
}

#ifdef CONFIG_MEMCG_KMEM
static void __memcg_destroy_list_lru_node(struct list_lru_memcg *memcg_lrus,
					  int begin, int end)
{
	int i;

	for (i = begin; i < end; i++)
		kfree(memcg_lrus->lru[i]);
}

static int __memcg_init_list_lru_node(struct list_lru_memcg *memcg_lrus,
				      int begin, int end)
{
	int i;

	for (i = begin; i < end; i++) {
		struct list_lru_one *l;

		l = kmalloc(sizeof(struct list_lru_one), GFP_KERNEL);
		if (!l)
			goto fail;

		init_one_lru(l);
		memcg_lrus->lru[i] = l;
	}
	return 0;
fail:
	__memcg_destroy_list_lru_node(memcg_lrus, begin, i - 1);
	return -ENOMEM;
}

static int memcg_init_list_lru_node(struct list_lru_node *nlru)
{
	int size = memcg_nr_cache_ids;

	nlru->memcg_lrus = kmalloc(size * sizeof(void *), GFP_KERNEL);
	if (!nlru->memcg_lrus)
		return -ENOMEM;

	if (__memcg_init_list_lru_node(nlru->memcg_lrus, 0, size)) {
		kfree(nlru->memcg_lrus);
		return -ENOMEM;
	}

	return 0;
}

static void memcg_destroy_list_lru_node(struct list_lru_node *nlru)
{
	__memcg_destroy_list_lru_node(nlru->memcg_lrus, 0, memcg_nr_cache_ids);
	kfree(nlru->memcg_lrus);
}

static int memcg_update_list_lru_node(struct list_lru_node *nlru,
				      int old_size, int new_size)
{
	struct list_lru_memcg *old, *new;

	BUG_ON(old_size > new_size);

	old = nlru->memcg_lrus;
	new = kmalloc(new_size * sizeof(void *), GFP_KERNEL);
	if (!new)
		return -ENOMEM;

	if (__memcg_init_list_lru_node(new, old_size, new_size)) {
		kfree(new);
		return -ENOMEM;
	}

	memcpy(new, old, old_size * sizeof(void *));

	/*
	 * The lock guarantees that we won't race with a reader
	 * (see list_lru_from_memcg_idx).
	 *
	 * Since list_lru_{add,del} may be called under an IRQ-safe lock,
	 * we have to use IRQ-safe primitives here to avoid deadlock.
	 */
	spin_lock_irq(&nlru->lock);
	nlru->memcg_lrus = new;
	spin_unlock_irq(&nlru->lock);

	kfree(old);
	return 0;
}

static void memcg_cancel_update_list_lru_node(struct list_lru_node *nlru,
					      int old_size, int new_size)
{
	/* do not bother shrinking the array back to the old size, because we
	 * cannot handle allocation failures here */
	__memcg_destroy_list_lru_node(nlru->memcg_lrus, old_size, new_size);
}

static int memcg_init_list_lru(struct list_lru *lru, bool memcg_aware)
{
	int i;

	if (!memcg_aware)
		return 0;

	for_each_node(i) {
		if (memcg_init_list_lru_node(&lru->node[i]))
			goto fail;
	}
	return 0;
fail:
	for (i = i - 1; i >= 0; i--) {
		if (!lru->node[i].memcg_lrus)
			continue;
		memcg_destroy_list_lru_node(&lru->node[i]);
	}
	return -ENOMEM;
}

static void memcg_destroy_list_lru(struct list_lru *lru)
{
	int i;

	if (!list_lru_memcg_aware(lru))
		return;

	for_each_node(i)
		memcg_destroy_list_lru_node(&lru->node[i]);
}

static int memcg_update_list_lru(struct list_lru *lru,
				 int old_size, int new_size)
{
	int i;

	if (!list_lru_memcg_aware(lru))
		return 0;

	for_each_node(i) {
		if (memcg_update_list_lru_node(&lru->node[i],
					       old_size, new_size))
			goto fail;
	}
	return 0;
fail:
	for (i = i - 1; i >= 0; i--) {
		if (!lru->node[i].memcg_lrus)
			continue;

		memcg_cancel_update_list_lru_node(&lru->node[i],
						  old_size, new_size);
	}
	return -ENOMEM;
}

static void memcg_cancel_update_list_lru(struct list_lru *lru,
					 int old_size, int new_size)
{
	int i;

	if (!list_lru_memcg_aware(lru))
		return;

	for_each_node(i)
		memcg_cancel_update_list_lru_node(&lru->node[i],
						  old_size, new_size);
}

int memcg_update_all_list_lrus(int new_size)
{
	int ret = 0;
	struct list_lru *lru;
	int old_size = memcg_nr_cache_ids;

	mutex_lock(&list_lrus_mutex);
	list_for_each_entry(lru, &list_lrus, list) {
		ret = memcg_update_list_lru(lru, old_size, new_size);
		if (ret)
			goto fail;
	}
out:
	mutex_unlock(&list_lrus_mutex);
	return ret;
fail:
	list_for_each_entry_continue_reverse(lru, &list_lrus, list)
		memcg_cancel_update_list_lru(lru, old_size, new_size);
	goto out;
}

static void memcg_drain_list_lru_node(struct list_lru_node *nlru,
				      int src_idx, int dst_idx)
{
	struct list_lru_one *src, *dst;

	/*
	 * Since list_lru_{add,del} may be called under an IRQ-safe lock,
	 * we have to use IRQ-safe primitives here to avoid deadlock.
	 */
	spin_lock_irq(&nlru->lock);

	src = list_lru_from_memcg_idx(nlru, src_idx);
	dst = list_lru_from_memcg_idx(nlru, dst_idx);

	list_splice_init(&src->list, &dst->list);
	dst->nr_items += src->nr_items;
	src->nr_items = 0;

	spin_unlock_irq(&nlru->lock);
}

static void memcg_drain_list_lru(struct list_lru *lru,
				 int src_idx, int dst_idx)
{
	int i;

	if (!list_lru_memcg_aware(lru))
		return;

	for_each_node(i)
		memcg_drain_list_lru_node(&lru->node[i], src_idx, dst_idx);
}

void memcg_drain_all_list_lrus(int src_idx, int dst_idx)
{
	struct list_lru *lru;

	mutex_lock(&list_lrus_mutex);
	list_for_each_entry(lru, &list_lrus, list)
		memcg_drain_list_lru(lru, src_idx, dst_idx);
	mutex_unlock(&list_lrus_mutex);
}
#else
static int memcg_init_list_lru(struct list_lru *lru, bool memcg_aware)
{
	return 0;
}

static void memcg_destroy_list_lru(struct list_lru *lru)
{
}
#endif /* CONFIG_MEMCG_KMEM */

int __list_lru_init(struct list_lru *lru, bool memcg_aware,
		    struct lock_class_key *key)
{
	int i;
	size_t size = sizeof(*lru->node) * nr_node_ids;
	int err = -ENOMEM;

	memcg_get_cache_ids();

	lru->node = kzalloc(size, GFP_KERNEL);
	if (!lru->node)
		goto out;

	for_each_node(i) {
		spin_lock_init(&lru->node[i].lock);
		if (key)
			lockdep_set_class(&lru->node[i].lock, key);
		init_one_lru(&lru->node[i].lru);
	}

	err = memcg_init_list_lru(lru, memcg_aware);
	if (err) {
		kfree(lru->node);
		goto out;
	}

	list_lru_register(lru);
out:
	memcg_put_cache_ids();
	return err;
}
EXPORT_SYMBOL_GPL(__list_lru_init);

void list_lru_destroy(struct list_lru *lru)
{
	/* Already destroyed or not yet initialized? */
	if (!lru->node)
		return;

	memcg_get_cache_ids();

	list_lru_unregister(lru);

	memcg_destroy_list_lru(lru);
	kfree(lru->node);
	lru->node = NULL;

	memcg_put_cache_ids();
}
EXPORT_SYMBOL_GPL(list_lru_destroy);
Commit	Line	Data
a38e4082 DC	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>
3b1d58a4	9	#include <linux/mm.h>
a38e4082	10	#include <linux/list_lru.h>
5ca302c8	11	#include <linux/slab.h>
c0a5b560	12	#include <linux/mutex.h>
60d3fd32	13	#include <linux/memcontrol.h>
c0a5b560 VD	14
	15	#ifdef CONFIG_MEMCG_KMEM
	16	static LIST_HEAD(list_lrus);
	17	static DEFINE_MUTEX(list_lrus_mutex);
	18
	19	static void list_lru_register(struct list_lru *lru)
	20	{
	21	mutex_lock(&list_lrus_mutex);
	22	list_add(&lru->list, &list_lrus);
	23	mutex_unlock(&list_lrus_mutex);
	24	}
	25
	26	static void list_lru_unregister(struct list_lru *lru)
	27	{
	28	mutex_lock(&list_lrus_mutex);
	29	list_del(&lru->list);
	30	mutex_unlock(&list_lrus_mutex);
	31	}
	32	#else
	33	static void list_lru_register(struct list_lru *lru)
	34	{
	35	}
	36
	37	static void list_lru_unregister(struct list_lru *lru)
	38	{
	39	}
	40	#endif /* CONFIG_MEMCG_KMEM */
a38e4082	41
60d3fd32 VD	42	#ifdef CONFIG_MEMCG_KMEM
	43	static inline bool list_lru_memcg_aware(struct list_lru *lru)
	44	{
145949a1 R	45	/*
	46	* This needs node 0 to be always present, even
	47	* in the systems supporting sparse numa ids.
	48	*/
60d3fd32 VD	49	return !!lru->node[0].memcg_lrus;
	50	}
	51
	52	static inline struct list_lru_one *
	53	list_lru_from_memcg_idx(struct list_lru_node *nlru, int idx)
	54	{
	55	/*
	56	* The lock protects the array of per cgroup lists from relocation
	57	* (see memcg_update_list_lru_node).
	58	*/
	59	lockdep_assert_held(&nlru->lock);
	60	if (nlru->memcg_lrus && idx >= 0)
	61	return nlru->memcg_lrus->lru[idx];
	62
	63	return &nlru->lru;
	64	}
	65
	66	static inline struct list_lru_one *
	67	list_lru_from_kmem(struct list_lru_node nlru, void ptr)
	68	{
	69	struct mem_cgroup *memcg;
	70
	71	if (!nlru->memcg_lrus)
	72	return &nlru->lru;
	73
	74	memcg = mem_cgroup_from_kmem(ptr);
	75	if (!memcg)
	76	return &nlru->lru;
	77
	78	return list_lru_from_memcg_idx(nlru, memcg_cache_id(memcg));
	79	}
	80	#else
	81	static inline bool list_lru_memcg_aware(struct list_lru *lru)
	82	{
	83	return false;
	84	}
	85
	86	static inline struct list_lru_one *
	87	list_lru_from_memcg_idx(struct list_lru_node *nlru, int idx)
	88	{
	89	return &nlru->lru;
	90	}
	91
	92	static inline struct list_lru_one *
	93	list_lru_from_kmem(struct list_lru_node nlru, void ptr)
	94	{
	95	return &nlru->lru;
	96	}
	97	#endif /* CONFIG_MEMCG_KMEM */
	98
a38e4082 DC	99	bool list_lru_add(struct list_lru lru, struct list_head item)
a38e4082 DC	100	{
3b1d58a4 DC	101	int nid = page_to_nid(virt_to_page(item));
3b1d58a4 DC	102	struct list_lru_node *nlru = &lru->node[nid];
60d3fd32	103	struct list_lru_one *l;
3b1d58a4 DC	104
3b1d58a4 DC	105	spin_lock(&nlru->lock);
a38e4082	106	if (list_empty(item)) {
26f5d760	107	l = list_lru_from_kmem(nlru, item);
60d3fd32 VD	108	list_add_tail(item, &l->list);
60d3fd32 VD	109	l->nr_items++;
3b1d58a4	110	spin_unlock(&nlru->lock);
a38e4082 DC	111	return true;
a38e4082 DC	112	}
3b1d58a4	113	spin_unlock(&nlru->lock);
a38e4082 DC	114	return false;
	115	}
	116	EXPORT_SYMBOL_GPL(list_lru_add);
	117
	118	bool list_lru_del(struct list_lru lru, struct list_head item)
	119	{
3b1d58a4 DC	120	int nid = page_to_nid(virt_to_page(item));
3b1d58a4 DC	121	struct list_lru_node *nlru = &lru->node[nid];
60d3fd32	122	struct list_lru_one *l;
3b1d58a4 DC	123
3b1d58a4 DC	124	spin_lock(&nlru->lock);
a38e4082	125	if (!list_empty(item)) {
26f5d760	126	l = list_lru_from_kmem(nlru, item);
a38e4082	127	list_del_init(item);
60d3fd32	128	l->nr_items--;
3b1d58a4	129	spin_unlock(&nlru->lock);
a38e4082 DC	130	return true;
a38e4082 DC	131	}
3b1d58a4	132	spin_unlock(&nlru->lock);
a38e4082 DC	133	return false;
	134	}
	135	EXPORT_SYMBOL_GPL(list_lru_del);
	136
3f97b163 VD	137	void list_lru_isolate(struct list_lru_one list, struct list_head item)
	138	{
	139	list_del_init(item);
	140	list->nr_items--;
	141	}
	142	EXPORT_SYMBOL_GPL(list_lru_isolate);
	143
	144	void list_lru_isolate_move(struct list_lru_one list, struct list_head item,
	145	struct list_head *head)
	146	{
	147	list_move(item, head);
	148	list->nr_items--;
	149	}
	150	EXPORT_SYMBOL_GPL(list_lru_isolate_move);
	151
60d3fd32 VD	152	static unsigned long __list_lru_count_one(struct list_lru *lru,
60d3fd32 VD	153	int nid, int memcg_idx)
a38e4082	154	{
6a4f496f	155	struct list_lru_node *nlru = &lru->node[nid];
60d3fd32 VD	156	struct list_lru_one *l;
60d3fd32 VD	157	unsigned long count;
3b1d58a4	158
6a4f496f	159	spin_lock(&nlru->lock);
60d3fd32	160	l = list_lru_from_memcg_idx(nlru, memcg_idx);
60d3fd32	161	count = l->nr_items;
6a4f496f	162	spin_unlock(&nlru->lock);
3b1d58a4 DC	163
	164	return count;
	165	}
60d3fd32 VD	166
	167	unsigned long list_lru_count_one(struct list_lru *lru,
	168	int nid, struct mem_cgroup *memcg)
	169	{
	170	return __list_lru_count_one(lru, nid, memcg_cache_id(memcg));
	171	}
	172	EXPORT_SYMBOL_GPL(list_lru_count_one);
	173
	174	unsigned long list_lru_count_node(struct list_lru *lru, int nid)
	175	{
	176	long count = 0;
	177	int memcg_idx;
	178
	179	count += __list_lru_count_one(lru, nid, -1);
	180	if (list_lru_memcg_aware(lru)) {
	181	for_each_memcg_cache_index(memcg_idx)
	182	count += __list_lru_count_one(lru, nid, memcg_idx);
	183	}
	184	return count;
	185	}
6a4f496f	186	EXPORT_SYMBOL_GPL(list_lru_count_node);
3b1d58a4	187
60d3fd32 VD	188	static unsigned long
	189	__list_lru_walk_one(struct list_lru *lru, int nid, int memcg_idx,
	190	list_lru_walk_cb isolate, void *cb_arg,
	191	unsigned long *nr_to_walk)
3b1d58a4 DC	192	{
3b1d58a4 DC	193
60d3fd32 VD	194	struct list_lru_node *nlru = &lru->node[nid];
60d3fd32 VD	195	struct list_lru_one *l;
a38e4082	196	struct list_head item, n;
3b1d58a4	197	unsigned long isolated = 0;
a38e4082	198
3b1d58a4	199	spin_lock(&nlru->lock);
60d3fd32	200	l = list_lru_from_memcg_idx(nlru, memcg_idx);
a38e4082	201	restart:
60d3fd32	202	list_for_each_safe(item, n, &l->list) {
a38e4082	203	enum lru_status ret;
5cedf721 DC	204
	205	/*
	206	* decrement nr_to_walk first so that we don't livelock if we
	207	* get stuck on large numbesr of LRU_RETRY items
	208	*/
c56b097a	209	if (!*nr_to_walk)
5cedf721	210	break;
c56b097a	211	--*nr_to_walk;
5cedf721	212
3f97b163	213	ret = isolate(item, l, &nlru->lock, cb_arg);
a38e4082	214	switch (ret) {
449dd698 JW	215	case LRU_REMOVED_RETRY:
449dd698 JW	216	assert_spin_locked(&nlru->lock);
a38e4082	217	case LRU_REMOVED:
3b1d58a4	218	isolated++;
449dd698 JW	219	/*
	220	* If the lru lock has been dropped, our list
	221	* traversal is now invalid and so we have to
	222	* restart from scratch.
	223	*/
	224	if (ret == LRU_REMOVED_RETRY)
	225	goto restart;
a38e4082 DC	226	break;
a38e4082 DC	227	case LRU_ROTATE:
60d3fd32	228	list_move_tail(item, &l->list);
a38e4082 DC	229	break;
	230	case LRU_SKIP:
	231	break;
	232	case LRU_RETRY:
5cedf721 DC	233	/*
	234	* The lru lock has been dropped, our list traversal is
	235	* now invalid and so we have to restart from scratch.
	236	*/
449dd698	237	assert_spin_locked(&nlru->lock);
a38e4082 DC	238	goto restart;
	239	default:
	240	BUG();
	241	}
a38e4082	242	}
3b1d58a4 DC	243
	244	spin_unlock(&nlru->lock);
	245	return isolated;
	246	}
60d3fd32 VD	247
	248	unsigned long
	249	list_lru_walk_one(struct list_lru lru, int nid, struct mem_cgroup memcg,
	250	list_lru_walk_cb isolate, void *cb_arg,
	251	unsigned long *nr_to_walk)
	252	{
	253	return __list_lru_walk_one(lru, nid, memcg_cache_id(memcg),
	254	isolate, cb_arg, nr_to_walk);
	255	}
	256	EXPORT_SYMBOL_GPL(list_lru_walk_one);
	257
	258	unsigned long list_lru_walk_node(struct list_lru *lru, int nid,
	259	list_lru_walk_cb isolate, void *cb_arg,
	260	unsigned long *nr_to_walk)
	261	{
	262	long isolated = 0;
	263	int memcg_idx;
	264
	265	isolated += __list_lru_walk_one(lru, nid, -1, isolate, cb_arg,
	266	nr_to_walk);
	267	if (*nr_to_walk > 0 && list_lru_memcg_aware(lru)) {
	268	for_each_memcg_cache_index(memcg_idx) {
	269	isolated += __list_lru_walk_one(lru, nid, memcg_idx,
	270	isolate, cb_arg, nr_to_walk);
	271	if (*nr_to_walk <= 0)
	272	break;
	273	}
	274	}
	275	return isolated;
	276	}
3b1d58a4 DC	277	EXPORT_SYMBOL_GPL(list_lru_walk_node);
3b1d58a4 DC	278
60d3fd32 VD	279	static void init_one_lru(struct list_lru_one *l)
	280	{
	281	INIT_LIST_HEAD(&l->list);
	282	l->nr_items = 0;
	283	}
	284
	285	#ifdef CONFIG_MEMCG_KMEM
	286	static void __memcg_destroy_list_lru_node(struct list_lru_memcg *memcg_lrus,
	287	int begin, int end)
	288	{
	289	int i;
	290
	291	for (i = begin; i < end; i++)
	292	kfree(memcg_lrus->lru[i]);
	293	}
	294
	295	static int __memcg_init_list_lru_node(struct list_lru_memcg *memcg_lrus,
	296	int begin, int end)
	297	{
	298	int i;
	299
	300	for (i = begin; i < end; i++) {
	301	struct list_lru_one *l;
	302
	303	l = kmalloc(sizeof(struct list_lru_one), GFP_KERNEL);
	304	if (!l)
	305	goto fail;
	306
	307	init_one_lru(l);
	308	memcg_lrus->lru[i] = l;
	309	}
	310	return 0;
	311	fail:
	312	__memcg_destroy_list_lru_node(memcg_lrus, begin, i - 1);
	313	return -ENOMEM;
	314	}
	315
	316	static int memcg_init_list_lru_node(struct list_lru_node *nlru)
	317	{
	318	int size = memcg_nr_cache_ids;
	319
	320	nlru->memcg_lrus = kmalloc(size * sizeof(void *), GFP_KERNEL);
	321	if (!nlru->memcg_lrus)
	322	return -ENOMEM;
	323
	324	if (__memcg_init_list_lru_node(nlru->memcg_lrus, 0, size)) {
	325	kfree(nlru->memcg_lrus);
	326	return -ENOMEM;
	327	}
	328
	329	return 0;
	330	}
	331
	332	static void memcg_destroy_list_lru_node(struct list_lru_node *nlru)
	333	{
	334	__memcg_destroy_list_lru_node(nlru->memcg_lrus, 0, memcg_nr_cache_ids);
	335	kfree(nlru->memcg_lrus);
	336	}
	337
	338	static int memcg_update_list_lru_node(struct list_lru_node *nlru,
	339	int old_size, int new_size)
	340	{
	341	struct list_lru_memcg old, new;
	342
343	BUG_ON(old_size > new_size);
344
345	old = nlru->memcg_lrus;
346	new = kmalloc(new_size * sizeof(void *), GFP_KERNEL);
347	if (!new)
348	return -ENOMEM;
349
350	if (__memcg_init_list_lru_node(new, old_size, new_size)) {
351	kfree(new);
352	return -ENOMEM;
353	}
354
355	memcpy(new, old, old_size * sizeof(void *));
356
357	/*
358	* The lock guarantees that we won't race with a reader
359	* (see list_lru_from_memcg_idx).
360	*
361	* Since list_lru_{add,del} may be called under an IRQ-safe lock,
362	* we have to use IRQ-safe primitives here to avoid deadlock.
363	*/
364	spin_lock_irq(&nlru->lock);
365	nlru->memcg_lrus = new;
366	spin_unlock_irq(&nlru->lock);
367
368	kfree(old);
369	return 0;
370	}
371
372	static void memcg_cancel_update_list_lru_node(struct list_lru_node *nlru,
373	int old_size, int new_size)
374	{
375	/* do not bother shrinking the array back to the old size, because we
376	* cannot handle allocation failures here */
377	__memcg_destroy_list_lru_node(nlru->memcg_lrus, old_size, new_size);
378	}
379
380	static int memcg_init_list_lru(struct list_lru *lru, bool memcg_aware)
381	{
382	int i;
383
145949a1 R	384	if (!memcg_aware)
	385	return 0;
	386
	387	for_each_node(i) {
	388	if (memcg_init_list_lru_node(&lru->node[i]))
60d3fd32 VD	389	goto fail;
	390	}
	391	return 0;
	392	fail:
145949a1 R	393	for (i = i - 1; i >= 0; i--) {
	394	if (!lru->node[i].memcg_lrus)
	395	continue;
60d3fd32	396	memcg_destroy_list_lru_node(&lru->node[i]);
145949a1	397	}
60d3fd32 VD	398	return -ENOMEM;
	399	}
	400
	401	static void memcg_destroy_list_lru(struct list_lru *lru)
	402	{
	403	int i;
	404
	405	if (!list_lru_memcg_aware(lru))
	406	return;
	407
145949a1	408	for_each_node(i)
60d3fd32 VD	409	memcg_destroy_list_lru_node(&lru->node[i]);
	410	}
	411
	412	static int memcg_update_list_lru(struct list_lru *lru,
	413	int old_size, int new_size)
	414	{
	415	int i;
	416
	417	if (!list_lru_memcg_aware(lru))
	418	return 0;
	419
145949a1	420	for_each_node(i) {
60d3fd32 VD	421	if (memcg_update_list_lru_node(&lru->node[i],
	422	old_size, new_size))
	423	goto fail;
	424	}
	425	return 0;
	426	fail:
145949a1 R	427	for (i = i - 1; i >= 0; i--) {
	428	if (!lru->node[i].memcg_lrus)
	429	continue;
	430
60d3fd32 VD	431	memcg_cancel_update_list_lru_node(&lru->node[i],
60d3fd32 VD	432	old_size, new_size);
145949a1	433	}
60d3fd32 VD	434	return -ENOMEM;
	435	}
	436
	437	static void memcg_cancel_update_list_lru(struct list_lru *lru,
	438	int old_size, int new_size)
	439	{
	440	int i;
	441
	442	if (!list_lru_memcg_aware(lru))
	443	return;
	444
145949a1	445	for_each_node(i)
60d3fd32 VD	446	memcg_cancel_update_list_lru_node(&lru->node[i],
	447	old_size, new_size);
	448	}
	449
	450	int memcg_update_all_list_lrus(int new_size)
	451	{
	452	int ret = 0;
	453	struct list_lru *lru;
	454	int old_size = memcg_nr_cache_ids;
	455
	456	mutex_lock(&list_lrus_mutex);
	457	list_for_each_entry(lru, &list_lrus, list) {
	458	ret = memcg_update_list_lru(lru, old_size, new_size);
	459	if (ret)
	460	goto fail;
	461	}
	462	out:
	463	mutex_unlock(&list_lrus_mutex);
	464	return ret;
	465	fail:
	466	list_for_each_entry_continue_reverse(lru, &list_lrus, list)
	467	memcg_cancel_update_list_lru(lru, old_size, new_size);
	468	goto out;
	469	}
2788cf0c VD	470
	471	static void memcg_drain_list_lru_node(struct list_lru_node *nlru,
	472	int src_idx, int dst_idx)
	473	{
	474	struct list_lru_one src, dst;
	475
	476	/*
	477	* Since list_lru_{add,del} may be called under an IRQ-safe lock,
	478	* we have to use IRQ-safe primitives here to avoid deadlock.
	479	*/
	480	spin_lock_irq(&nlru->lock);
	481
	482	src = list_lru_from_memcg_idx(nlru, src_idx);
	483	dst = list_lru_from_memcg_idx(nlru, dst_idx);
	484
	485	list_splice_init(&src->list, &dst->list);
	486	dst->nr_items += src->nr_items;
	487	src->nr_items = 0;
	488
	489	spin_unlock_irq(&nlru->lock);
	490	}
	491
	492	static void memcg_drain_list_lru(struct list_lru *lru,
	493	int src_idx, int dst_idx)
	494	{
	495	int i;
	496
	497	if (!list_lru_memcg_aware(lru))
	498	return;
	499
145949a1	500	for_each_node(i)
2788cf0c VD	501	memcg_drain_list_lru_node(&lru->node[i], src_idx, dst_idx);
	502	}
	503
	504	void memcg_drain_all_list_lrus(int src_idx, int dst_idx)
	505	{
	506	struct list_lru *lru;
	507
	508	mutex_lock(&list_lrus_mutex);
	509	list_for_each_entry(lru, &list_lrus, list)
	510	memcg_drain_list_lru(lru, src_idx, dst_idx);
	511	mutex_unlock(&list_lrus_mutex);
	512	}
60d3fd32 VD	513	#else
	514	static int memcg_init_list_lru(struct list_lru *lru, bool memcg_aware)
	515	{
	516	return 0;
	517	}
	518
	519	static void memcg_destroy_list_lru(struct list_lru *lru)
	520	{
	521	}
	522	#endif /* CONFIG_MEMCG_KMEM */
	523
	524	int __list_lru_init(struct list_lru *lru, bool memcg_aware,
	525	struct lock_class_key *key)
a38e4082	526	{
3b1d58a4	527	int i;
5ca302c8	528	size_t size = sizeof(lru->node) nr_node_ids;
60d3fd32 VD	529	int err = -ENOMEM;
	530
	531	memcg_get_cache_ids();
5ca302c8 GC	532
	533	lru->node = kzalloc(size, GFP_KERNEL);
	534	if (!lru->node)
60d3fd32	535	goto out;
a38e4082	536
145949a1	537	for_each_node(i) {
3b1d58a4	538	spin_lock_init(&lru->node[i].lock);
449dd698 JW	539	if (key)
449dd698 JW	540	lockdep_set_class(&lru->node[i].lock, key);
60d3fd32 VD	541	init_one_lru(&lru->node[i].lru);
	542	}
	543
	544	err = memcg_init_list_lru(lru, memcg_aware);
	545	if (err) {
	546	kfree(lru->node);
	547	goto out;
3b1d58a4	548	}
60d3fd32	549
c0a5b560	550	list_lru_register(lru);
60d3fd32 VD	551	out:
	552	memcg_put_cache_ids();
	553	return err;
a38e4082	554	}
60d3fd32	555	EXPORT_SYMBOL_GPL(__list_lru_init);
5ca302c8 GC	556
	557	void list_lru_destroy(struct list_lru *lru)
	558	{
c0a5b560 VD	559	/* Already destroyed or not yet initialized? */
	560	if (!lru->node)
	561	return;
60d3fd32 VD	562
	563	memcg_get_cache_ids();
	564
c0a5b560	565	list_lru_unregister(lru);
60d3fd32 VD	566
60d3fd32 VD	567	memcg_destroy_list_lru(lru);
5ca302c8	568	kfree(lru->node);
c0a5b560	569	lru->node = NULL;
60d3fd32 VD	570
60d3fd32 VD	571	memcg_put_cache_ids();
5ca302c8 GC	572	}
5ca302c8 GC	573	EXPORT_SYMBOL_GPL(list_lru_destroy);