list_lru.c revision a38e40824844a5ec85f3ea95632be953477d2afa
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> 9a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner#include <linux/list_lru.h> 10a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 11a38e40824844a5ec85f3ea95632be953477d2afaDave Chinnerbool list_lru_add(struct list_lru *lru, struct list_head *item) 12a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner{ 13a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner spin_lock(&lru->lock); 14a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner if (list_empty(item)) { 15a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner list_add_tail(item, &lru->list); 16a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner lru->nr_items++; 17a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner spin_unlock(&lru->lock); 18a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return true; 19a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 20a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner spin_unlock(&lru->lock); 21a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return false; 22a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner} 23a38e40824844a5ec85f3ea95632be953477d2afaDave ChinnerEXPORT_SYMBOL_GPL(list_lru_add); 24a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 25a38e40824844a5ec85f3ea95632be953477d2afaDave Chinnerbool list_lru_del(struct list_lru *lru, struct list_head *item) 26a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner{ 27a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner spin_lock(&lru->lock); 28a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner if (!list_empty(item)) { 29a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner list_del_init(item); 30a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner lru->nr_items--; 31a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner spin_unlock(&lru->lock); 32a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return true; 33a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 34a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner spin_unlock(&lru->lock); 35a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return false; 36a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner} 37a38e40824844a5ec85f3ea95632be953477d2afaDave ChinnerEXPORT_SYMBOL_GPL(list_lru_del); 38a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 39a38e40824844a5ec85f3ea95632be953477d2afaDave Chinnerunsigned long list_lru_walk(struct list_lru *lru, list_lru_walk_cb isolate, 40a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner void *cb_arg, unsigned long nr_to_walk) 41a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner{ 42a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner struct list_head *item, *n; 43a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner unsigned long removed = 0; 44a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner /* 45a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner * If we don't keep state of at which pass we are, we can loop at 46a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner * LRU_RETRY, since we have no guarantees that the caller will be able 47a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner * to do something other than retry on the next pass. We handle this by 48a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner * allowing at most one retry per object. This should not be altered 49a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner * by any condition other than LRU_RETRY. 50a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner */ 51a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner bool first_pass = true; 52a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 53a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner spin_lock(&lru->lock); 54a38e40824844a5ec85f3ea95632be953477d2afaDave Chinnerrestart: 55a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner list_for_each_safe(item, n, &lru->list) { 56a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner enum lru_status ret; 57a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner ret = isolate(item, &lru->lock, cb_arg); 58a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner switch (ret) { 59a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_REMOVED: 60a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner lru->nr_items--; 61a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner removed++; 62a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner break; 63a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_ROTATE: 64a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner list_move_tail(item, &lru->list); 65a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner break; 66a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_SKIP: 67a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner break; 68a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner case LRU_RETRY: 69a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner if (!first_pass) { 70a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner first_pass = true; 71a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner break; 72a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 73a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner first_pass = false; 74a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner goto restart; 75a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner default: 76a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner BUG(); 77a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 78a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 79a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner if (nr_to_walk-- == 0) 80a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner break; 81a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 82a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 83a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner spin_unlock(&lru->lock); 84a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return removed; 85a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner} 86a38e40824844a5ec85f3ea95632be953477d2afaDave ChinnerEXPORT_SYMBOL_GPL(list_lru_walk); 87a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 88a38e40824844a5ec85f3ea95632be953477d2afaDave Chinnerunsigned long list_lru_dispose_all(struct list_lru *lru, 89a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner list_lru_dispose_cb dispose) 90a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner{ 91a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner unsigned long disposed = 0; 92a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner LIST_HEAD(dispose_list); 93a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 94a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner spin_lock(&lru->lock); 95a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner while (!list_empty(&lru->list)) { 96a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner list_splice_init(&lru->list, &dispose_list); 97a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner disposed += lru->nr_items; 98a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner lru->nr_items = 0; 99a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner spin_unlock(&lru->lock); 100a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 101a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner dispose(&dispose_list); 102a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 103a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner spin_lock(&lru->lock); 104a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner } 105a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner spin_unlock(&lru->lock); 106a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return disposed; 107a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner} 108a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 109a38e40824844a5ec85f3ea95632be953477d2afaDave Chinnerint list_lru_init(struct list_lru *lru) 110a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner{ 111a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner spin_lock_init(&lru->lock); 112a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner INIT_LIST_HEAD(&lru->list); 113a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner lru->nr_items = 0; 114a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner 115a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner return 0; 116a38e40824844a5ec85f3ea95632be953477d2afaDave Chinner} 117a38e40824844a5ec85f3ea95632be953477d2afaDave ChinnerEXPORT_SYMBOL_GPL(list_lru_init); 118