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          * If we don't keep state of at which pass we are, we can loop at
  78          * LRU_RETRY, since we have no guarantees that the caller will be able
  79          * to do something other than retry on the next pass. We handle this by
  80          * allowing at most one retry per object. This should not be altered
  81          * by any condition other than LRU_RETRY.
  82          */
  83         bool first_pass = true;
  84
  85         spin_lock(&nlru->lock);
  86 restart:
  87         list_for_each_safe(item, n, &nlru->list) {
  88                 enum lru_status ret;
  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                         if (!first_pass) {
 104                                 first_pass = true;
 105                                 break;
 106                         }
 107                         first_pass = false;
 108                         goto restart;
 109                 default:
 110                         BUG();
 111                 }
 112
 113                 if ((*nr_to_walk)-- == 0)
 114                         break;
 115
 116         }
 117
 118         spin_unlock(&nlru->lock);
 119         return isolated;
 120 }
 121 EXPORT_SYMBOL_GPL(list_lru_walk_node);
 122
 123 unsigned long list_lru_walk(struct list_lru *lru, list_lru_walk_cb isolate,
 124                             void *cb_arg, unsigned long nr_to_walk)
 125 {
 126         unsigned long isolated = 0;
 127         int nid;
 128
 129         for_each_node_mask(nid, lru->active_nodes) {
 130                 isolated += list_lru_walk_node(lru, nid, isolate,
 131                                                cb_arg, &nr_to_walk);
 132                 if (nr_to_walk <= 0)
 133                         break;
 134         }
 135         return isolated;
 136 }
 137 EXPORT_SYMBOL_GPL(list_lru_walk);
 138
 139 static unsigned long list_lru_dispose_all_node(struct list_lru *lru, int nid,
 140                                                list_lru_dispose_cb dispose)
 141 {
 142         struct list_lru_node    *nlru = &lru->node[nid];
 143         LIST_HEAD(dispose_list);
 144         unsigned long disposed = 0;
 145
 146         spin_lock(&nlru->lock);
 147         while (!list_empty(&nlru->list)) {
 148                 list_splice_init(&nlru->list, &dispose_list);
 149                 disposed += nlru->nr_items;
 150                 nlru->nr_items = 0;
 151                 node_clear(nid, lru->active_nodes);
 152                 spin_unlock(&nlru->lock);
 153
 154                 dispose(&dispose_list);
 155
 156                 spin_lock(&nlru->lock);
 157         }
 158         spin_unlock(&nlru->lock);
 159         return disposed;
 160 }
 161
 162 unsigned long list_lru_dispose_all(struct list_lru *lru,
 163                                    list_lru_dispose_cb dispose)
 164 {
 165         unsigned long disposed;
 166         unsigned long total = 0;
 167         int nid;
 168
 169         do {
 170                 disposed = 0;
 171                 for_each_node_mask(nid, lru->active_nodes) {
 172                         disposed += list_lru_dispose_all_node(lru, nid,
 173                                                               dispose);
 174                 }
 175                 total += disposed;
 176         } while (disposed != 0);
 177
 178         return total;
 179 }
 180
 181 int list_lru_init(struct list_lru *lru)
 182 {
 183         int i;
 184
 185         nodes_clear(lru->active_nodes);
 186         for (i = 0; i < MAX_NUMNODES; i++) {
 187                 spin_lock_init(&lru->node[i].lock);
 188                 INIT_LIST_HEAD(&lru->node[i].list);
 189                 lru->node[i].nr_items = 0;
 190         }
 191         return 0;
 192 }
 193 EXPORT_SYMBOL_GPL(list_lru_init);