[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>

#if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
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 && !CONFIG_SLOB */

#if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
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 __always_inline struct mem_cgroup *mem_cgroup_from_kmem(void *ptr)
{
	struct page *page;

	if (!memcg_kmem_enabled())
		return NULL;
	page = virt_to_head_page(ptr);
	return page->mem_cgroup;
}

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 && !CONFIG_SLOB */

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++;
		nlru->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--;
		nlru->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)
{
	struct list_lru_node *nlru;

	nlru = &lru->node[nid];
	return nlru->nr_items;
}
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++;
			nlru->nr_items--;
			/*
			 * 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;
}

#if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
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 && !CONFIG_SLOB */

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