1a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner/* 2a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner * Copyright (c) 2013 Red Hat, Inc. and Parallels Inc. All rights reserved. 3a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner * Authors: David Chinner and Glauber Costa 4a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner * 5a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner * Generic LRU infrastructure 6a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner */ 7a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner#include <linux/kernel.h> 8a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner#include <linux/module.h> 93b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner#include <linux/mm.h> 10a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner#include <linux/list_lru.h> 115ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa#include <linux/slab.h> 12a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 13a38e40824844a5ec85f3ea95632be953477d2afaDave Chinnerbool list_lru_add(struct list_lru *lru, struct list_head *item) 14a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner{ 153b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner int nid = page_to_nid(virt_to_page(item)); 163b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner struct list_lru_node *nlru = &lru->node[nid]; 173b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 183b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_lock(&nlru->lock); 193b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner WARN_ON_ONCE(nlru->nr_items < 0); 20a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner if (list_empty(item)) { 213b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner list_add_tail(item, &nlru->list); 223b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner if (nlru->nr_items++ == 0) 233b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner node_set(nid, lru->active_nodes); 243b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_unlock(&nlru->lock); 25a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return true; 26a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 273b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_unlock(&nlru->lock); 28a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return false; 29a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner} 30a38e40824844a5ec85f3ea95632be953477d2afaDave ChinnerEXPORT_SYMBOL_GPL(list_lru_add); 31a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 32a38e40824844a5ec85f3ea95632be953477d2afaDave Chinnerbool list_lru_del(struct list_lru *lru, struct list_head *item) 33a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner{ 343b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner int nid = page_to_nid(virt_to_page(item)); 353b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner struct list_lru_node *nlru = &lru->node[nid]; 363b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 373b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_lock(&nlru->lock); 38a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner if (!list_empty(item)) { 39a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner list_del_init(item); 403b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner if (--nlru->nr_items == 0) 413b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner node_clear(nid, lru->active_nodes); 423b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner WARN_ON_ONCE(nlru->nr_items < 0); 433b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_unlock(&nlru->lock); 44a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return true; 45a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 463b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_unlock(&nlru->lock); 47a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return false; 48a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner} 49a38e40824844a5ec85f3ea95632be953477d2afaDave ChinnerEXPORT_SYMBOL_GPL(list_lru_del); 50a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 516a4f496fd2fc74fa036732ae52c184952d6e3e37Glauber Costaunsigned long 526a4f496fd2fc74fa036732ae52c184952d6e3e37Glauber Costalist_lru_count_node(struct list_lru *lru, int nid) 53a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner{ 543b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner unsigned long count = 0; 556a4f496fd2fc74fa036732ae52c184952d6e3e37Glauber Costa struct list_lru_node *nlru = &lru->node[nid]; 563b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 576a4f496fd2fc74fa036732ae52c184952d6e3e37Glauber Costa spin_lock(&nlru->lock); 586a4f496fd2fc74fa036732ae52c184952d6e3e37Glauber Costa WARN_ON_ONCE(nlru->nr_items < 0); 596a4f496fd2fc74fa036732ae52c184952d6e3e37Glauber Costa count += nlru->nr_items; 606a4f496fd2fc74fa036732ae52c184952d6e3e37Glauber Costa spin_unlock(&nlru->lock); 613b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 623b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner return count; 633b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner} 646a4f496fd2fc74fa036732ae52c184952d6e3e37Glauber CostaEXPORT_SYMBOL_GPL(list_lru_count_node); 653b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 666a4f496fd2fc74fa036732ae52c184952d6e3e37Glauber Costaunsigned long 673b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinnerlist_lru_walk_node(struct list_lru *lru, int nid, list_lru_walk_cb isolate, 683b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner void *cb_arg, unsigned long *nr_to_walk) 693b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner{ 703b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 713b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner struct list_lru_node *nlru = &lru->node[nid]; 72a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner struct list_head *item, *n; 733b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner unsigned long isolated = 0; 74a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 753b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_lock(&nlru->lock); 76a38e40824844a5ec85f3ea95632be953477d2afaDave Chinnerrestart: 773b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner list_for_each_safe(item, n, &nlru->list) { 78a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner enum lru_status ret; 795cedf721a7cdb54e9222133516c916210d836470Dave Chinner 805cedf721a7cdb54e9222133516c916210d836470Dave Chinner /* 815cedf721a7cdb54e9222133516c916210d836470Dave Chinner * decrement nr_to_walk first so that we don't livelock if we 825cedf721a7cdb54e9222133516c916210d836470Dave Chinner * get stuck on large numbesr of LRU_RETRY items 835cedf721a7cdb54e9222133516c916210d836470Dave Chinner */ 84c56b097af26cb11c1f49a4311ba538c825666fedRussell King if (!*nr_to_walk) 855cedf721a7cdb54e9222133516c916210d836470Dave Chinner break; 86c56b097af26cb11c1f49a4311ba538c825666fedRussell King --*nr_to_walk; 875cedf721a7cdb54e9222133516c916210d836470Dave Chinner 883b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner ret = isolate(item, &nlru->lock, cb_arg); 89a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner switch (ret) { 90449dd6984d0e47643c04c807f609dd56d48d5bccJohannes Weiner case LRU_REMOVED_RETRY: 91449dd6984d0e47643c04c807f609dd56d48d5bccJohannes Weiner assert_spin_locked(&nlru->lock); 92a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_REMOVED: 933b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner if (--nlru->nr_items == 0) 943b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner node_clear(nid, lru->active_nodes); 953b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner WARN_ON_ONCE(nlru->nr_items < 0); 963b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner isolated++; 97449dd6984d0e47643c04c807f609dd56d48d5bccJohannes Weiner /* 98449dd6984d0e47643c04c807f609dd56d48d5bccJohannes Weiner * If the lru lock has been dropped, our list 99449dd6984d0e47643c04c807f609dd56d48d5bccJohannes Weiner * traversal is now invalid and so we have to 100449dd6984d0e47643c04c807f609dd56d48d5bccJohannes Weiner * restart from scratch. 101449dd6984d0e47643c04c807f609dd56d48d5bccJohannes Weiner */ 102449dd6984d0e47643c04c807f609dd56d48d5bccJohannes Weiner if (ret == LRU_REMOVED_RETRY) 103449dd6984d0e47643c04c807f609dd56d48d5bccJohannes Weiner goto restart; 104a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner break; 105a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_ROTATE: 1063b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner list_move_tail(item, &nlru->list); 107a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner break; 108a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_SKIP: 109a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner break; 110a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_RETRY: 1115cedf721a7cdb54e9222133516c916210d836470Dave Chinner /* 1125cedf721a7cdb54e9222133516c916210d836470Dave Chinner * The lru lock has been dropped, our list traversal is 1135cedf721a7cdb54e9222133516c916210d836470Dave Chinner * now invalid and so we have to restart from scratch. 1145cedf721a7cdb54e9222133516c916210d836470Dave Chinner */ 115449dd6984d0e47643c04c807f609dd56d48d5bccJohannes Weiner assert_spin_locked(&nlru->lock); 116a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner goto restart; 117a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner default: 118a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner BUG(); 119a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 120a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 1213b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 1223b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_unlock(&nlru->lock); 1233b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner return isolated; 1243b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner} 1253b1d58a4c96799eb4c92039e1b851b86f853548aDave ChinnerEXPORT_SYMBOL_GPL(list_lru_walk_node); 1263b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 127449dd6984d0e47643c04c807f609dd56d48d5bccJohannes Weinerint list_lru_init_key(struct list_lru *lru, struct lock_class_key *key) 128a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner{ 1293b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner int i; 1305ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa size_t size = sizeof(*lru->node) * nr_node_ids; 1315ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa 1325ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa lru->node = kzalloc(size, GFP_KERNEL); 1335ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa if (!lru->node) 1345ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa return -ENOMEM; 135a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 1363b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner nodes_clear(lru->active_nodes); 1375ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa for (i = 0; i < nr_node_ids; i++) { 1383b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_lock_init(&lru->node[i].lock); 139449dd6984d0e47643c04c807f609dd56d48d5bccJohannes Weiner if (key) 140449dd6984d0e47643c04c807f609dd56d48d5bccJohannes Weiner lockdep_set_class(&lru->node[i].lock, key); 1413b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner INIT_LIST_HEAD(&lru->node[i].list); 1423b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner lru->node[i].nr_items = 0; 1433b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner } 144a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return 0; 145a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner} 146449dd6984d0e47643c04c807f609dd56d48d5bccJohannes WeinerEXPORT_SYMBOL_GPL(list_lru_init_key); 1475ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa 1485ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costavoid list_lru_destroy(struct list_lru *lru) 1495ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa{ 1505ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa kfree(lru->node); 1515ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa} 1525ca302c8e502ca53b7d75f12127ec0289904003aGlauber CostaEXPORT_SYMBOL_GPL(list_lru_destroy); 153