list_lru.c revision 5cedf721a7cdb54e9222133516c916210d836470
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> 11a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 12a38e40824844a5ec85f3ea95632be953477d2afaDave Chinnerbool list_lru_add(struct list_lru *lru, struct list_head *item) 13a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner{ 143b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner int nid = page_to_nid(virt_to_page(item)); 153b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner struct list_lru_node *nlru = &lru->node[nid]; 163b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 173b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_lock(&nlru->lock); 183b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner WARN_ON_ONCE(nlru->nr_items < 0); 19a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner if (list_empty(item)) { 203b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner list_add_tail(item, &nlru->list); 213b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner if (nlru->nr_items++ == 0) 223b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner node_set(nid, lru->active_nodes); 233b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_unlock(&nlru->lock); 24a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return true; 25a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 263b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_unlock(&nlru->lock); 27a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return false; 28a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner} 29a38e40824844a5ec85f3ea95632be953477d2afaDave ChinnerEXPORT_SYMBOL_GPL(list_lru_add); 30a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 31a38e40824844a5ec85f3ea95632be953477d2afaDave Chinnerbool list_lru_del(struct list_lru *lru, struct list_head *item) 32a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner{ 333b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner int nid = page_to_nid(virt_to_page(item)); 343b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner struct list_lru_node *nlru = &lru->node[nid]; 353b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 363b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_lock(&nlru->lock); 37a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner if (!list_empty(item)) { 38a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner list_del_init(item); 393b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner if (--nlru->nr_items == 0) 403b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner node_clear(nid, lru->active_nodes); 413b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner WARN_ON_ONCE(nlru->nr_items < 0); 423b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_unlock(&nlru->lock); 43a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return true; 44a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 453b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_unlock(&nlru->lock); 46a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return false; 47a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner} 48a38e40824844a5ec85f3ea95632be953477d2afaDave ChinnerEXPORT_SYMBOL_GPL(list_lru_del); 49a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 503b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinnerunsigned long list_lru_count(struct list_lru *lru) 51a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner{ 523b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner unsigned long count = 0; 533b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner int nid; 543b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 553b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner for_each_node_mask(nid, lru->active_nodes) { 563b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner struct list_lru_node *nlru = &lru->node[nid]; 573b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 583b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_lock(&nlru->lock); 593b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner WARN_ON_ONCE(nlru->nr_items < 0); 603b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner count += nlru->nr_items; 613b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_unlock(&nlru->lock); 623b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner } 633b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 643b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner return count; 653b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner} 663b1d58a4c96799eb4c92039e1b851b86f853548aDave ChinnerEXPORT_SYMBOL_GPL(list_lru_count); 673b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 683b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinnerstatic unsigned long 693b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinnerlist_lru_walk_node(struct list_lru *lru, int nid, list_lru_walk_cb isolate, 703b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner void *cb_arg, unsigned long *nr_to_walk) 713b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner{ 723b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 733b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner struct list_lru_node *nlru = &lru->node[nid]; 74a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner struct list_head *item, *n; 753b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner unsigned long isolated = 0; 76a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 773b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_lock(&nlru->lock); 78a38e40824844a5ec85f3ea95632be953477d2afaDave Chinnerrestart: 793b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner list_for_each_safe(item, n, &nlru->list) { 80a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner enum lru_status ret; 815cedf721a7cdb54e9222133516c916210d836470Dave Chinner 825cedf721a7cdb54e9222133516c916210d836470Dave Chinner /* 835cedf721a7cdb54e9222133516c916210d836470Dave Chinner * decrement nr_to_walk first so that we don't livelock if we 845cedf721a7cdb54e9222133516c916210d836470Dave Chinner * get stuck on large numbesr of LRU_RETRY items 855cedf721a7cdb54e9222133516c916210d836470Dave Chinner */ 865cedf721a7cdb54e9222133516c916210d836470Dave Chinner if (--(*nr_to_walk) == 0) 875cedf721a7cdb54e9222133516c916210d836470Dave Chinner break; 885cedf721a7cdb54e9222133516c916210d836470Dave Chinner 893b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner ret = isolate(item, &nlru->lock, cb_arg); 90a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner switch (ret) { 91a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_REMOVED: 923b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner if (--nlru->nr_items == 0) 933b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner node_clear(nid, lru->active_nodes); 943b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner WARN_ON_ONCE(nlru->nr_items < 0); 953b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner isolated++; 96a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner break; 97a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_ROTATE: 983b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner list_move_tail(item, &nlru->list); 99a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner break; 100a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_SKIP: 101a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner break; 102a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_RETRY: 1035cedf721a7cdb54e9222133516c916210d836470Dave Chinner /* 1045cedf721a7cdb54e9222133516c916210d836470Dave Chinner * The lru lock has been dropped, our list traversal is 1055cedf721a7cdb54e9222133516c916210d836470Dave Chinner * now invalid and so we have to restart from scratch. 1065cedf721a7cdb54e9222133516c916210d836470Dave Chinner */ 107a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner goto restart; 108a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner default: 109a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner BUG(); 110a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 111a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 1123b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 1133b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_unlock(&nlru->lock); 1143b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner return isolated; 1153b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner} 1163b1d58a4c96799eb4c92039e1b851b86f853548aDave ChinnerEXPORT_SYMBOL_GPL(list_lru_walk_node); 1173b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 1183b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinnerunsigned long list_lru_walk(struct list_lru *lru, list_lru_walk_cb isolate, 1193b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner void *cb_arg, unsigned long nr_to_walk) 1203b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner{ 1213b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner unsigned long isolated = 0; 1223b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner int nid; 1233b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 1243b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner for_each_node_mask(nid, lru->active_nodes) { 1253b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner isolated += list_lru_walk_node(lru, nid, isolate, 1263b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner cb_arg, &nr_to_walk); 1273b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner if (nr_to_walk <= 0) 1283b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner break; 1293b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner } 1303b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner return isolated; 131a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner} 132a38e40824844a5ec85f3ea95632be953477d2afaDave ChinnerEXPORT_SYMBOL_GPL(list_lru_walk); 133a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 1343b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinnerstatic unsigned long list_lru_dispose_all_node(struct list_lru *lru, int nid, 1353b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner list_lru_dispose_cb dispose) 136a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner{ 1373b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner struct list_lru_node *nlru = &lru->node[nid]; 138a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner LIST_HEAD(dispose_list); 1393b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner unsigned long disposed = 0; 140a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 1413b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_lock(&nlru->lock); 1423b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner while (!list_empty(&nlru->list)) { 1433b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner list_splice_init(&nlru->list, &dispose_list); 1443b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner disposed += nlru->nr_items; 1453b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner nlru->nr_items = 0; 1463b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner node_clear(nid, lru->active_nodes); 1473b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_unlock(&nlru->lock); 148a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 149a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner dispose(&dispose_list); 150a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 1513b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_lock(&nlru->lock); 152a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 1533b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_unlock(&nlru->lock); 154a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return disposed; 155a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner} 156a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 1573b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinnerunsigned long list_lru_dispose_all(struct list_lru *lru, 1583b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner list_lru_dispose_cb dispose) 1593b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner{ 1603b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner unsigned long disposed; 1613b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner unsigned long total = 0; 1623b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner int nid; 1633b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 1643b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner do { 1653b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner disposed = 0; 1663b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner for_each_node_mask(nid, lru->active_nodes) { 1673b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner disposed += list_lru_dispose_all_node(lru, nid, 1683b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner dispose); 1693b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner } 1703b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner total += disposed; 1713b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner } while (disposed != 0); 1723b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 1733b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner return total; 1743b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner} 1753b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner 176a38e40824844a5ec85f3ea95632be953477d2afaDave Chinnerint list_lru_init(struct list_lru *lru) 177a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner{ 1783b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner int i; 179a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 1803b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner nodes_clear(lru->active_nodes); 1813b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner for (i = 0; i < MAX_NUMNODES; i++) { 1823b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner spin_lock_init(&lru->node[i].lock); 1833b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner INIT_LIST_HEAD(&lru->node[i].list); 1843b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner lru->node[i].nr_items = 0; 1853b1d58a4c96799eb4c92039e1b851b86f853548aDave Chinner } 186a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return 0; 187a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner} 188a38e40824844a5ec85f3ea95632be953477d2afaDave ChinnerEXPORT_SYMBOL_GPL(list_lru_init); 189