include/linux/list_lru.h

   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 #ifndef _LRU_LIST_H
   8 #define _LRU_LIST_H
   9
  10 #include <linux/list.h>
  11 #include <linux/nodemask.h>
  12
  13 /* list_lru_walk_cb has to always return one of those */
  14 enum lru_status {
  15         LRU_REMOVED,            /* item removed from list */
  16         LRU_ROTATE,             /* item referenced, give another pass */
  17         LRU_SKIP,               /* item cannot be locked, skip */
  18         LRU_RETRY,              /* item not freeable. May drop the lock
  19                                    internally, but has to return locked. */
  20 };
  21
  22 struct list_lru_node {
  23         spinlock_t              lock;
  24         struct list_head        list;
  25         /* kept as signed so we can catch imbalance bugs */
  26         long                    nr_items;
  27 } ____cacheline_aligned_in_smp;
  28
  29 struct list_lru {
  30         /*
  31          * Because we use a fixed-size array, this struct can be very big if
  32          * MAX_NUMNODES is big. If this becomes a problem this is fixable by
  33          * turning this into a pointer and dynamically allocating this to
  34          * nr_node_ids. This quantity is firwmare-provided, and still would
  35          * provide room for all nodes at the cost of a pointer lookup and an
  36          * extra allocation. Because that allocation will most likely come from
  37          * a different slab cache than the main structure holding this
  38          * structure, we may very well fail.
  39          */
  40         struct list_lru_node    node[MAX_NUMNODES];
  41         nodemask_t              active_nodes;
  42 };
  43
  44 int list_lru_init(struct list_lru *lru);
  45
  46 /**
  47  * list_lru_add: add an element to the lru list's tail
  48  * @list_lru: the lru pointer
  49  * @item: the item to be added.
  50  *
  51  * If the element is already part of a list, this function returns doing
  52  * nothing. Therefore the caller does not need to keep state about whether or
  53  * not the element already belongs in the list and is allowed to lazy update
  54  * it. Note however that this is valid for *a* list, not *this* list. If
  55  * the caller organize itself in a way that elements can be in more than
  56  * one type of list, it is up to the caller to fully remove the item from
  57  * the previous list (with list_lru_del() for instance) before moving it
  58  * to @list_lru
  59  *
  60  * Return value: true if the list was updated, false otherwise
  61  */
  62 bool list_lru_add(struct list_lru *lru, struct list_head *item);
  63
  64 /**
  65  * list_lru_del: delete an element to the lru list
  66  * @list_lru: the lru pointer
  67  * @item: the item to be deleted.
  68  *
  69  * This function works analogously as list_lru_add in terms of list
  70  * manipulation. The comments about an element already pertaining to
  71  * a list are also valid for list_lru_del.
  72  *
  73  * Return value: true if the list was updated, false otherwise
  74  */
  75 bool list_lru_del(struct list_lru *lru, struct list_head *item);
  76
  77 /**
  78  * list_lru_count_node: return the number of objects currently held by @lru
  79  * @lru: the lru pointer.
  80  * @nid: the node id to count from.
  81  *
  82  * Always return a non-negative number, 0 for empty lists. There is no
  83  * guarantee that the list is not updated while the count is being computed.
  84  * Callers that want such a guarantee need to provide an outer lock.
  85  */
  86 unsigned long list_lru_count_node(struct list_lru *lru, int nid);
  87 static inline unsigned long list_lru_count(struct list_lru *lru)
  88 {
  89         long count = 0;
  90         int nid;
  91
  92         for_each_node_mask(nid, lru->active_nodes)
  93                 count += list_lru_count_node(lru, nid);
  94
  95         return count;
  96 }
  97
  98 typedef enum lru_status
  99 (*list_lru_walk_cb)(struct list_head *item, spinlock_t *lock, void *cb_arg);
 100 /**
 101  * list_lru_walk_node: walk a list_lru, isolating and disposing freeable items.
 102  * @lru: the lru pointer.
 103  * @nid: the node id to scan from.
 104  * @isolate: callback function that is resposible for deciding what to do with
 105  *  the item currently being scanned
 106  * @cb_arg: opaque type that will be passed to @isolate
 107  * @nr_to_walk: how many items to scan.
 108  *
 109  * This function will scan all elements in a particular list_lru, calling the
 110  * @isolate callback for each of those items, along with the current list
 111  * spinlock and a caller-provided opaque. The @isolate callback can choose to
 112  * drop the lock internally, but *must* return with the lock held. The callback
 113  * will return an enum lru_status telling the list_lru infrastructure what to
 114  * do with the object being scanned.
 115  *
 116  * Please note that nr_to_walk does not mean how many objects will be freed,
 117  * just how many objects will be scanned.
 118  *
 119  * Return value: the number of objects effectively removed from the LRU.
 120  */
 121 unsigned long list_lru_walk_node(struct list_lru *lru, int nid,
 122                                  list_lru_walk_cb isolate, void *cb_arg,
 123                                  unsigned long *nr_to_walk);
 124
 125 static inline unsigned long
 126 list_lru_walk(struct list_lru *lru, list_lru_walk_cb isolate,
 127               void *cb_arg, unsigned long nr_to_walk)
 128 {
 129         long isolated = 0;
 130         int nid;
 131
 132         for_each_node_mask(nid, lru->active_nodes) {
 133                 isolated += list_lru_walk_node(lru, nid, isolate,
 134                                                cb_arg, &nr_to_walk);
 135                 if (nr_to_walk <= 0)
 136                         break;
 137         }
 138         return isolated;
 139 }
 140
 141 typedef void (*list_lru_dispose_cb)(struct list_head *dispose_list);
 142 /**
 143  * list_lru_dispose_all: forceably flush all elements in an @lru
 144  * @lru: the lru pointer
 145  * @dispose: callback function to be called for each lru list.
 146  *
 147  * This function will forceably isolate all elements into the dispose list, and
 148  * call the @dispose callback to flush the list. Please note that the callback
 149  * should expect items in any state, clean or dirty, and be able to flush all of
 150  * them.
 151  *
 152  * Return value: how many objects were freed. It should be equal to all objects
 153  * in the list_lru.
 154  */
 155 unsigned long
 156 list_lru_dispose_all(struct list_lru *lru, list_lru_dispose_cb dispose);
 157 #endif /* _LRU_LIST_H */