mm/list_lru.c

   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>
   9 #include <linux/mm.h>
  10 #include <linux/list_lru.h>
  11
  12 bool list_lru_add(struct list_lru *lru, struct list_head *item)
  13 {
  14         int nid = page_to_nid(virt_to_page(item));
  15         struct list_lru_node *nlru = &lru->node[nid];
  16
  17         spin_lock(&nlru->lock);
  18         WARN_ON_ONCE(nlru->nr_items < 0);
  19         if (list_empty(item)) {
  20                 list_add_tail(item, &nlru->list);
  21                 if (nlru->nr_items++ == 0)
  22                         node_set(nid, lru->active_nodes);
  23                 spin_unlock(&nlru->lock);
  24                 return true;
  25         }
  26         spin_unlock(&nlru->lock);
  27         return false;
  28 }
  29 EXPORT_SYMBOL_GPL(list_lru_add);
  30
  31 bool list_lru_del(struct list_lru *lru, struct list_head *item)
  32 {
  33         int nid = page_to_nid(virt_to_page(item));
  34         struct list_lru_node *nlru = &lru->node[nid];
  35
  36         spin_lock(&nlru->lock);
  37         if (!list_empty(item)) {
  38                 list_del_init(item);
  39                 if (--nlru->nr_items == 0)
  40                         node_clear(nid, lru->active_nodes);
  41                 WARN_ON_ONCE(nlru->nr_items < 0);
  42                 spin_unlock(&nlru->lock);
  43                 return true;
  44         }
  45         spin_unlock(&nlru->lock);
  46         return false;
  47 }
  48 EXPORT_SYMBOL_GPL(list_lru_del);
  49
  50 unsigned long list_lru_count(struct list_lru *lru)
  51 {
  52         unsigned long count = 0;
  53         int nid;
  54
  55         for_each_node_mask(nid, lru->active_nodes) {
  56                 struct list_lru_node *nlru = &lru->node[nid];
  57
  58                 spin_lock(&nlru->lock);
  59                 WARN_ON_ONCE(nlru->nr_items < 0);
  60                 count += nlru->nr_items;
  61                 spin_unlock(&nlru->lock);
  62         }
  63
  64         return count;
  65 }
  66 EXPORT_SYMBOL_GPL(list_lru_count);
  67
  68 static unsigned long
  69 list_lru_walk_node(struct list_lru *lru, int nid, list_lru_walk_cb isolate,
  70                    void *cb_arg, unsigned long *nr_to_walk)
  71 {
  72
  73         struct list_lru_node    *nlru = &lru->node[nid];
  74         struct list_head *item, *n;
  75         unsigned long isolated = 0;
  76
  77         spin_lock(&nlru->lock);
  78 restart:
  79         list_for_each_safe(item, n, &nlru->list) {
  80                 enum lru_status ret;
  81
  82                 /*
  83                  * decrement nr_to_walk first so that we don't livelock if we
  84                  * get stuck on large numbesr of LRU_RETRY items
  85                  */
  86                 if (--(*nr_to_walk) == 0)
  87                         break;
  88
  89                 ret = isolate(item, &nlru->lock, cb_arg);
  90                 switch (ret) {
  91                 case LRU_REMOVED:
  92                         if (--nlru->nr_items == 0)
  93                                 node_clear(nid, lru->active_nodes);
  94                         WARN_ON_ONCE(nlru->nr_items < 0);
  95                         isolated++;
  96                         break;
  97                 case LRU_ROTATE:
  98                         list_move_tail(item, &nlru->list);
  99                         break;
 100                 case LRU_SKIP:
 101                         break;
 102                 case LRU_RETRY:
 103                         /*
 104                          * The lru lock has been dropped, our list traversal is
 105                          * now invalid and so we have to restart from scratch.
 106                          */
 107                         goto restart;
 108                 default:
 109                         BUG();
 110                 }
 111         }
 112
 113         spin_unlock(&nlru->lock);
 114         return isolated;
 115 }
 116 EXPORT_SYMBOL_GPL(list_lru_walk_node);
 117
 118 unsigned long list_lru_walk(struct list_lru *lru, list_lru_walk_cb isolate,
 119                             void *cb_arg, unsigned long nr_to_walk)
 120 {
 121         unsigned long isolated = 0;
 122         int nid;
 123
 124         for_each_node_mask(nid, lru->active_nodes) {
 125                 isolated += list_lru_walk_node(lru, nid, isolate,
 126                                                cb_arg, &nr_to_walk);
 127                 if (nr_to_walk <= 0)
 128                         break;
 129         }
 130         return isolated;
 131 }
 132 EXPORT_SYMBOL_GPL(list_lru_walk);
 133
 134 static unsigned long list_lru_dispose_all_node(struct list_lru *lru, int nid,
 135                                                list_lru_dispose_cb dispose)
 136 {
 137         struct list_lru_node    *nlru = &lru->node[nid];
 138         LIST_HEAD(dispose_list);
 139         unsigned long disposed = 0;
 140
 141         spin_lock(&nlru->lock);
 142         while (!list_empty(&nlru->list)) {
 143                 list_splice_init(&nlru->list, &dispose_list);
 144                 disposed += nlru->nr_items;
 145                 nlru->nr_items = 0;
 146                 node_clear(nid, lru->active_nodes);
 147                 spin_unlock(&nlru->lock);
 148
 149                 dispose(&dispose_list);
 150
 151                 spin_lock(&nlru->lock);
 152         }
 153         spin_unlock(&nlru->lock);
 154         return disposed;
 155 }
 156
 157 unsigned long list_lru_dispose_all(struct list_lru *lru,
 158                                    list_lru_dispose_cb dispose)
 159 {
 160         unsigned long disposed;
 161         unsigned long total = 0;
 162         int nid;
 163
 164         do {
 165                 disposed = 0;
 166                 for_each_node_mask(nid, lru->active_nodes) {
 167                         disposed += list_lru_dispose_all_node(lru, nid,
 168                                                               dispose);
 169                 }
 170                 total += disposed;
 171         } while (disposed != 0);
 172
 173         return total;
 174 }
 175
 176 int list_lru_init(struct list_lru *lru)
 177 {
 178         int i;
 179
 180         nodes_clear(lru->active_nodes);
 181         for (i = 0; i < MAX_NUMNODES; i++) {
 182                 spin_lock_init(&lru->node[i].lock);
 183                 INIT_LIST_HEAD(&lru->node[i].list);
 184                 lru->node[i].nr_items = 0;
 185         }
 186         return 0;
 187 }
 188 EXPORT_SYMBOL_GPL(list_lru_init);