list_lru.c revision 5ca302c8e502ca53b7d75f12127ec0289904003a
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 */ 845cedf721a7cdb54e9222133516c916210d836470Dave Chinner if (--(*nr_to_walk) == 0) 855cedf721a7cdb54e9222133516c916210d836470Dave Chinner break; 865cedf721a7cdb54e9222133516c916210d836470Dave Chinner 873b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner ret = isolate(item, &nlru->lock, cb_arg); 88a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner switch (ret) { 89a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_REMOVED: 903b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner if (--nlru->nr_items == 0) 913b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner node_clear(nid, lru->active_nodes); 923b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner WARN_ON_ONCE(nlru->nr_items < 0); 933b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner isolated++; 94a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner break; 95a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_ROTATE: 963b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner list_move_tail(item, &nlru->list); 97a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner break; 98a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_SKIP: 99a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner break; 100a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_RETRY: 1015cedf721a7cdb54e9222133516c916210d836470Dave Chinner /* 1025cedf721a7cdb54e9222133516c916210d836470Dave Chinner * The lru lock has been dropped, our list traversal is 1035cedf721a7cdb54e9222133516c916210d836470Dave Chinner * now invalid and so we have to restart from scratch. 1045cedf721a7cdb54e9222133516c916210d836470Dave Chinner */ 105a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner goto restart; 106a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner default: 107a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner BUG(); 108a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 109a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 1103b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 1113b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_unlock(&nlru->lock); 1123b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner return isolated; 1133b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner} 1143b1d58a4c96799eb4c92039e1b851b86f853548aDave ChinnerEXPORT_SYMBOL_GPL(list_lru_walk_node); 1153b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 116a38e40824844a5ec85f3ea95632be953477d2afaDave Chinnerint list_lru_init(struct list_lru *lru) 117a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner{ 1183b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner int i; 1195ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa size_t size = sizeof(*lru->node) * nr_node_ids; 1205ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa 1215ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa lru->node = kzalloc(size, GFP_KERNEL); 1225ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa if (!lru->node) 1235ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa return -ENOMEM; 124a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 1253b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner nodes_clear(lru->active_nodes); 1265ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa for (i = 0; i < nr_node_ids; i++) { 1273b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_lock_init(&lru->node[i].lock); 1283b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner INIT_LIST_HEAD(&lru->node[i].list); 1293b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner lru->node[i].nr_items = 0; 1303b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner } 131a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return 0; 132a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner} 133a38e40824844a5ec85f3ea95632be953477d2afaDave ChinnerEXPORT_SYMBOL_GPL(list_lru_init); 1345ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa 1355ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costavoid list_lru_destroy(struct list_lru *lru) 1365ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa{ 1375ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa kfree(lru->node); 1385ca302c8e502ca53b7d75f12127ec0289904003aGlauber Costa} 1395ca302c8e502ca53b7d75f12127ec0289904003aGlauber CostaEXPORT_SYMBOL_GPL(list_lru_destroy); 140