[mirror_ubuntu-bionic-kernel.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)
{
	return lru->memcg_aware;
}

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);
			/* fall through */
		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);
	return -ENOMEM;
}

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

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

	if (__memcg_init_list_lru_node(nlru->memcg_lrus, 0, size)) {
		kvfree(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);
	kvfree(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 = kvmalloc(new_size * sizeof(void *), GFP_KERNEL);
	if (!new)
		return -ENOMEM;

	if (__memcg_init_list_lru_node(new, old_size, new_size)) {
		kvfree(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);

	kvfree(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;

	lru->memcg_aware = memcg_aware;

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