include/linux/list_lru.h

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2 /*
   3  * Copyright (c) 2013 Red Hat, Inc. and Parallels Inc. All rights reserved.
   4  * Authors: David Chinner and Glauber Costa
   5  *
   6  * Generic LRU infrastructure
   7  */
   8 #ifndef _LRU_LIST_H
   9 #define _LRU_LIST_H
  10
  11 #include <linux/list.h>
  12 #include <linux/nodemask.h>
  13 #include <linux/shrinker.h>
  14 #include <linux/xarray.h>
  15
  16 struct mem_cgroup;
  17
  18 /* list_lru_walk_cb has to always return one of those */
  19 enum lru_status {
  20         LRU_REMOVED,            /* item removed from list */
  21         LRU_REMOVED_RETRY,      /* item removed, but lock has been
  22                                    dropped and reacquired */
  23         LRU_ROTATE,             /* item referenced, give another pass */
  24         LRU_SKIP,               /* item cannot be locked, skip */
  25         LRU_RETRY,              /* item not freeable. May drop the lock
  26                                    internally, but has to return locked. */
  27         LRU_STOP,               /* stop lru list walking. May drop the lock
  28                                    internally, but has to return locked. */
  29 };
  30
  31 struct list_lru_one {
  32         struct list_head        list;
  33         /* may become negative during memcg reparenting */
  34         long                    nr_items;
  35 };
  36
  37 struct list_lru_memcg {
  38         struct rcu_head         rcu;
  39         /* array of per cgroup per node lists, indexed by node id */
  40         struct list_lru_one     node[];
  41 };
  42
  43 struct list_lru_node {
  44         /* protects all lists on the node, including per cgroup */
  45         spinlock_t              lock;
  46         /* global list, used for the root cgroup in cgroup aware lrus */
  47         struct list_lru_one     lru;
  48         long                    nr_items;
  49 } ____cacheline_aligned_in_smp;
  50
  51 struct list_lru {
  52         struct list_lru_node    *node;
  53 #ifdef CONFIG_MEMCG_KMEM
  54         struct list_head        list;
  55         int                     shrinker_id;
  56         bool                    memcg_aware;
  57         struct xarray           xa;
  58 #endif
  59 };
  60
  61 void list_lru_destroy(struct list_lru *lru);
  62 int __list_lru_init(struct list_lru *lru, bool memcg_aware,
  63                     struct lock_class_key *key, struct shrinker *shrinker);
  64
  65 #define list_lru_init(lru)                              \
  66         __list_lru_init((lru), false, NULL, NULL)
  67 #define list_lru_init_memcg(lru, shrinker)              \
  68         __list_lru_init((lru), true, NULL, shrinker)
  69
  70 int memcg_list_lru_alloc(struct mem_cgroup *memcg, struct list_lru *lru,
  71                          gfp_t gfp);
  72 void memcg_reparent_list_lrus(struct mem_cgroup *memcg, struct mem_cgroup *parent);
  73
  74 /**
  75  * list_lru_add: add an element to the lru list's tail
  76  * @lru: the lru pointer
  77  * @item: the item to be added.
  78  * @nid: the node id of the sublist to add the item to.
  79  * @memcg: the cgroup of the sublist to add the item to.
  80  *
  81  * If the element is already part of a list, this function returns doing
  82  * nothing. Therefore the caller does not need to keep state about whether or
  83  * not the element already belongs in the list and is allowed to lazy update
  84  * it. Note however that this is valid for *a* list, not *this* list. If
  85  * the caller organize itself in a way that elements can be in more than
  86  * one type of list, it is up to the caller to fully remove the item from
  87  * the previous list (with list_lru_del() for instance) before moving it
  88  * to @lru.
  89  *
  90  * Return: true if the list was updated, false otherwise
  91  */
  92 bool list_lru_add(struct list_lru *lru, struct list_head *item, int nid,
  93                     struct mem_cgroup *memcg);
  94
  95 /**
  96  * list_lru_add_obj: add an element to the lru list's tail
  97  * @lru: the lru pointer
  98  * @item: the item to be added.
  99  *
 100  * This function is similar to list_lru_add(), but the NUMA node and the
 101  * memcg of the sublist is determined by @item list_head. This assumption is
 102  * valid for slab objects LRU such as dentries, inodes, etc.
 103  *
 104  * Return value: true if the list was updated, false otherwise
 105  */
 106 bool list_lru_add_obj(struct list_lru *lru, struct list_head *item);
 107
 108 /**
 109  * list_lru_del: delete an element from the lru list
 110  * @lru: the lru pointer
 111  * @item: the item to be deleted.
 112  * @nid: the node id of the sublist to delete the item from.
 113  * @memcg: the cgroup of the sublist to delete the item from.
 114  *
 115  * This function works analogously as list_lru_add() in terms of list
 116  * manipulation. The comments about an element already pertaining to
 117  * a list are also valid for list_lru_del().
 118  *
 119  * Return: true if the list was updated, false otherwise
 120  */
 121 bool list_lru_del(struct list_lru *lru, struct list_head *item, int nid,
 122                     struct mem_cgroup *memcg);
 123
 124 /**
 125  * list_lru_del_obj: delete an element from the lru list
 126  * @lru: the lru pointer
 127  * @item: the item to be deleted.
 128  *
 129  * This function is similar to list_lru_del(), but the NUMA node and the
 130  * memcg of the sublist is determined by @item list_head. This assumption is
 131  * valid for slab objects LRU such as dentries, inodes, etc.
 132  *
 133  * Return value: true if the list was updated, false otherwise.
 134  */
 135 bool list_lru_del_obj(struct list_lru *lru, struct list_head *item);
 136
 137 /**
 138  * list_lru_count_one: return the number of objects currently held by @lru
 139  * @lru: the lru pointer.
 140  * @nid: the node id to count from.
 141  * @memcg: the cgroup to count from.
 142  *
 143  * There is no guarantee that the list is not updated while the count is being
 144  * computed. Callers that want such a guarantee need to provide an outer lock.
 145  *
 146  * Return: 0 for empty lists, otherwise the number of objects
 147  * currently held by @lru.
 148  */
 149 unsigned long list_lru_count_one(struct list_lru *lru,
 150                                  int nid, struct mem_cgroup *memcg);
 151 unsigned long list_lru_count_node(struct list_lru *lru, int nid);
 152
 153 static inline unsigned long list_lru_shrink_count(struct list_lru *lru,
 154                                                   struct shrink_control *sc)
 155 {
 156         return list_lru_count_one(lru, sc->nid, sc->memcg);
 157 }
 158
 159 static inline unsigned long list_lru_count(struct list_lru *lru)
 160 {
 161         long count = 0;
 162         int nid;
 163
 164         for_each_node_state(nid, N_NORMAL_MEMORY)
 165                 count += list_lru_count_node(lru, nid);
 166
 167         return count;
 168 }
 169
 170 void list_lru_isolate(struct list_lru_one *list, struct list_head *item);
 171 void list_lru_isolate_move(struct list_lru_one *list, struct list_head *item,
 172                            struct list_head *head);
 173
 174 typedef enum lru_status (*list_lru_walk_cb)(struct list_head *item,
 175                 struct list_lru_one *list, spinlock_t *lock, void *cb_arg);
 176
 177 /**
 178  * list_lru_walk_one: walk a @lru, isolating and disposing freeable items.
 179  * @lru: the lru pointer.
 180  * @nid: the node id to scan from.
 181  * @memcg: the cgroup to scan from.
 182  * @isolate: callback function that is responsible for deciding what to do with
 183  *  the item currently being scanned
 184  * @cb_arg: opaque type that will be passed to @isolate
 185  * @nr_to_walk: how many items to scan.
 186  *
 187  * This function will scan all elements in a particular @lru, calling the
 188  * @isolate callback for each of those items, along with the current list
 189  * spinlock and a caller-provided opaque. The @isolate callback can choose to
 190  * drop the lock internally, but *must* return with the lock held. The callback
 191  * will return an enum lru_status telling the @lru infrastructure what to
 192  * do with the object being scanned.
 193  *
 194  * Please note that @nr_to_walk does not mean how many objects will be freed,
 195  * just how many objects will be scanned.
 196  *
 197  * Return: the number of objects effectively removed from the LRU.
 198  */
 199 unsigned long list_lru_walk_one(struct list_lru *lru,
 200                                 int nid, struct mem_cgroup *memcg,
 201                                 list_lru_walk_cb isolate, void *cb_arg,
 202                                 unsigned long *nr_to_walk);
 203 /**
 204  * list_lru_walk_one_irq: walk a @lru, isolating and disposing freeable items.
 205  * @lru: the lru pointer.
 206  * @nid: the node id to scan from.
 207  * @memcg: the cgroup to scan from.
 208  * @isolate: callback function that is responsible for deciding what to do with
 209  *  the item currently being scanned
 210  * @cb_arg: opaque type that will be passed to @isolate
 211  * @nr_to_walk: how many items to scan.
 212  *
 213  * Same as list_lru_walk_one() except that the spinlock is acquired with
 214  * spin_lock_irq().
 215  */
 216 unsigned long list_lru_walk_one_irq(struct list_lru *lru,
 217                                     int nid, struct mem_cgroup *memcg,
 218                                     list_lru_walk_cb isolate, void *cb_arg,
 219                                     unsigned long *nr_to_walk);
 220 unsigned long list_lru_walk_node(struct list_lru *lru, int nid,
 221                                  list_lru_walk_cb isolate, void *cb_arg,
 222                                  unsigned long *nr_to_walk);
 223
 224 static inline unsigned long
 225 list_lru_shrink_walk(struct list_lru *lru, struct shrink_control *sc,
 226                      list_lru_walk_cb isolate, void *cb_arg)
 227 {
 228         return list_lru_walk_one(lru, sc->nid, sc->memcg, isolate, cb_arg,
 229                                  &sc->nr_to_scan);
 230 }
 231
 232 static inline unsigned long
 233 list_lru_shrink_walk_irq(struct list_lru *lru, struct shrink_control *sc,
 234                          list_lru_walk_cb isolate, void *cb_arg)
 235 {
 236         return list_lru_walk_one_irq(lru, sc->nid, sc->memcg, isolate, cb_arg,
 237                                      &sc->nr_to_scan);
 238 }
 239
 240 static inline unsigned long
 241 list_lru_walk(struct list_lru *lru, list_lru_walk_cb isolate,
 242               void *cb_arg, unsigned long nr_to_walk)
 243 {
 244         long isolated = 0;
 245         int nid;
 246
 247         for_each_node_state(nid, N_NORMAL_MEMORY) {
 248                 isolated += list_lru_walk_node(lru, nid, isolate,
 249                                                cb_arg, &nr_to_walk);
 250                 if (nr_to_walk <= 0)
 251                         break;
 252         }
 253         return isolated;
 254 }
 255 #endif /* _LRU_LIST_H */