LXR linux/mm/list

   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#include <linux/slab.h>
  12
  13bool list_lru_add(struct list_lru *lru, struct list_head *item)
  14{
  15        int nid = page_to_nid(virt_to_page(item));
  16        struct list_lru_node *nlru = &lru->node[nid];
  17
  18        spin_lock(&nlru->lock);
  19        WARN_ON_ONCE(nlru->nr_items < 0);
  20        if (list_empty(item)) {
  21                list_add_tail(item, &nlru->list);
  22                if (nlru->nr_items++ == 0)
  23                        node_set(nid, lru->active_nodes);
  24                spin_unlock(&nlru->lock);
  25                return true;
  26        }
  27        spin_unlock(&nlru->lock);
  28        return false;
  29}
  30EXPORT_SYMBOL_GPL(list_lru_add);
  31
  32bool list_lru_del(struct list_lru *lru, struct list_head *item)
  33{
  34        int nid = page_to_nid(virt_to_page(item));
  35        struct list_lru_node *nlru = &lru->node[nid];
  36
  37        spin_lock(&nlru->lock);
  38        if (!list_empty(item)) {
  39                list_del_init(item);
  40                if (--nlru->nr_items == 0)
  41                        node_clear(nid, lru->active_nodes);
  42                WARN_ON_ONCE(nlru->nr_items < 0);
  43                spin_unlock(&nlru->lock);
  44                return true;
  45        }
  46        spin_unlock(&nlru->lock);
  47        return false;
  48}
  49EXPORT_SYMBOL_GPL(list_lru_del);
  50
  51unsigned long
  52list_lru_count_node(struct list_lru *lru, int nid)
  53{
  54        unsigned long count = 0;
  55        struct list_lru_node *nlru = &lru->node[nid];
  56
  57        spin_lock(&nlru->lock);
  58        WARN_ON_ONCE(nlru->nr_items < 0);
  59        count += nlru->nr_items;
  60        spin_unlock(&nlru->lock);
  61
  62        return count;
  63}
  64EXPORT_SYMBOL_GPL(list_lru_count_node);
  65
  66unsigned long
  67list_lru_walk_node(struct list_lru *lru, int nid, list_lru_walk_cb isolate,
  68                   void *cb_arg, unsigned long *nr_to_walk)
  69{
  70
  71        struct list_lru_node    *nlru = &lru->node[nid];
  72        struct list_head *item, *n;
  73        unsigned long isolated = 0;
  74
  75        spin_lock(&nlru->lock);
  76restart:
  77        list_for_each_safe(item, n, &nlru->list) {
  78                enum lru_status ret;
  79
  80                /*
  81                 * decrement nr_to_walk first so that we don't livelock if we
  82                 * get stuck on large numbesr of LRU_RETRY items
  83                 */
  84                if (!*nr_to_walk)
  85                        break;
  86                --*nr_to_walk;
  87
  88                ret = isolate(item, &nlru->lock, cb_arg);
  89                switch (ret) {
  90                case LRU_REMOVED:
  91                        if (--nlru->nr_items == 0)
  92                                node_clear(nid, lru->active_nodes);
  93                        WARN_ON_ONCE(nlru->nr_items < 0);
  94                        isolated++;
  95                        break;
  96                case LRU_ROTATE:
  97                        list_move_tail(item, &nlru->list);
  98                        break;
  99                case LRU_SKIP:
 100                        break;
 101                case LRU_RETRY:
 102                        /*
 103                         * The lru lock has been dropped, our list traversal is
 104                         * now invalid and so we have to restart from scratch.
 105                         */
 106                        goto restart;
 107                default:
 108                        BUG();
 109                }
 110        }
 111
 112        spin_unlock(&nlru->lock);
 113        return isolated;
 114}
 115EXPORT_SYMBOL_GPL(list_lru_walk_node);
 116
 117int list_lru_init(struct list_lru *lru)
 118{
 119        int i;
 120        size_t size = sizeof(*lru->node) * nr_node_ids;
 121
 122        lru->node = kzalloc(size, GFP_KERNEL);
 123        if (!lru->node)
 124                return -ENOMEM;
 125
 126        nodes_clear(lru->active_nodes);
 127        for (i = 0; i < nr_node_ids; i++) {
 128                spin_lock_init(&lru->node[i].lock);
 129                INIT_LIST_HEAD(&lru->node[i].list);
 130                lru->node[i].nr_items = 0;
 131        }
 132        return 0;
 133}
 134EXPORT_SYMBOL_GPL(list_lru_init);
 135
 136void list_lru_destroy(struct list_lru *lru)
 137{
 138        kfree(lru->node);
 139}
 140EXPORT_SYMBOL_GPL(list_lru_destroy);
 141