| 1 |
|
| 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 |
|
| 19 | enum lru_status {
|
| 20 | LRU_REMOVED,
|
| 21 | LRU_REMOVED_RETRY, |
| 22 | dropped and reacquired
|
| 23 | LRU_ROTATE,
|
| 24 | LRU_SKIP,
|
| 25 | LRU_RETRY, |
| 26 | internally, but has to return locked.
|
| 27 | LRU_STOP, |
| 28 | internally, but has to return locked.
|
| 29 | };
|
| 30 |
|
| 31 | struct list_lru_one {
|
| 32 | struct list_head list;
|
| 33 |
|
| 34 | long nr_items;
|
| 35 |
|
| 36 | spinlock_t lock;
|
| 37 | };
|
| 38 |
|
| 39 | struct list_lru_memcg {
|
| 40 | struct rcu_head rcu;
|
| 41 |
|
| 42 | struct list_lru_one node[];
|
| 43 | };
|
| 44 |
|
| 45 | struct list_lru_node {
|
| 46 |
|
| 47 | struct list_lru_one lru;
|
| 48 | atomic_long_t nr_items;
|
| 49 | } ____cacheline_aligned_in_smp;
|
| 50 |
|
| 51 | struct list_lru {
|
| 52 | struct list_lru_node *node;
|
| 53 | #ifdef CONFIG_MEMCG
|
| 54 | struct list_head list;
|
| 55 | int shrinker_id;
|
| 56 | bool memcg_aware;
|
| 57 | struct xarray xa;
|
| 58 | #endif
|
| 59 | #ifdef CONFIG_LOCKDEP
|
| 60 | struct lock_class_key *key;
|
| 61 | #endif
|
| 62 | };
|
| 63 |
|
| 64 | void list_lru_destroy(struct list_lru *lru);
|
| 65 | int __list_lru_init(struct list_lru *lru, bool memcg_aware,
|
| 66 | struct shrinker *shrinker);
|
| 67 |
|
| 68 | #define list_lru_init(lru) \
|
| 69 | __list_lru_init((lru), false, NULL)
|
| 70 | #define list_lru_init_memcg(lru, shrinker) \
|
| 71 | __list_lru_init((lru), true, shrinker)
|
| 72 |
|
| 73 | static inline int list_lru_init_memcg_key(struct list_lru *lru, struct shrinker *shrinker,
|
| 74 | struct lock_class_key *key)
|
| 75 | {
|
| 76 | #ifdef CONFIG_LOCKDEP
|
| 77 | lru->key = key;
|
| 78 | #endif
|
| 79 | return list_lru_init_memcg(lru, shrinker);
|
| 80 | }
|
| 81 |
|
| 82 | int memcg_list_lru_alloc(struct mem_cgroup *memcg, struct list_lru *lru,
|
| 83 | gfp_t gfp);
|
| 84 |
|
| 85 | #ifdef CONFIG_MEMCG
|
| 86 | |
| 87 | * folio_memcg_list_lru_alloc - allocate list_lru heads for shrinkable folio
|
| 88 | * @folio: the newly allocated & charged folio
|
| 89 | * @lru: the list_lru this might be queued on
|
| 90 | * @gfp: gfp mask
|
| 91 | *
|
| 92 | * Allocate list_lru heads (per-memcg, per-node) needed to queue this
|
| 93 | * particular folio down the line.
|
| 94 | *
|
| 95 | * This does memcg_list_lru_alloc(), but on the memcg that @folio is
|
| 96 | * associated with. Handles folio_memcg() access rules in the fast
|
| 97 | * path (list_lru heads allocated) and the allocation slowpath.
|
| 98 | *
|
| 99 | * Returns 0 on success, a negative error value otherwise.
|
| 100 |
|
| 101 | int folio_memcg_list_lru_alloc(struct folio *folio, struct list_lru *lru,
|
| 102 | gfp_t gfp);
|
| 103 | #else
|
| 104 | static inline int folio_memcg_list_lru_alloc(struct folio *folio,
|
| 105 | struct list_lru *lru, gfp_t gfp)
|
| 106 | {
|
| 107 | return 0;
|
| 108 | }
|
| 109 | #endif
|
| 110 |
|
| 111 | void memcg_reparent_list_lrus(struct mem_cgroup *memcg, struct mem_cgroup *parent);
|
| 112 |
|
| 113 | |
| 114 | * list_lru_lock: lock the sublist for the given node and memcg
|
| 115 | * @lru: the lru pointer
|
| 116 | * @nid: the node id of the sublist to lock.
|
| 117 | * @memcg: pointer to the cgroup of the sublist to lock. On return,
|
| 118 | * updated to the cgroup whose sublist was actually locked,
|
| 119 | * which may be an ancestor if the original memcg was dying.
|
| 120 | *
|
| 121 | * Returns the locked list_lru_one sublist. The caller must call
|
| 122 | * list_lru_unlock() when done.
|
| 123 | *
|
| 124 | * You must ensure that the memcg is not freed during this call (e.g., with
|
| 125 | * rcu or by taking a css refcnt).
|
| 126 | *
|
| 127 | * Return: the locked list_lru_one, or NULL on failure
|
| 128 |
|
| 129 | struct list_lru_one *list_lru_lock(struct list_lru *lru, int nid,
|
| 130 | struct mem_cgroup **memcg);
|
| 131 |
|
| 132 | |
| 133 | * list_lru_unlock: unlock a sublist locked by list_lru_lock()
|
| 134 | * @l: the list_lru_one to unlock
|
| 135 |
|
| 136 | void list_lru_unlock(struct list_lru_one *l);
|
| 137 |
|
| 138 | struct list_lru_one *list_lru_lock_irq(struct list_lru *lru, int nid,
|
| 139 | struct mem_cgroup **memcg);
|
| 140 | void list_lru_unlock_irq(struct list_lru_one *l);
|
| 141 |
|
| 142 | struct list_lru_one *list_lru_lock_irqsave(struct list_lru *lru, int nid,
|
| 143 | struct mem_cgroup **memcg, unsigned long *irq_flags);
|
| 144 | void list_lru_unlock_irqrestore(struct list_lru_one *l,
|
| 145 | unsigned long *irq_flags);
|
| 146 |
|
| 147 |
|
| 148 | bool __list_lru_add(struct list_lru *lru, struct list_lru_one *l,
|
| 149 | struct list_head *item, int nid, struct mem_cgroup *memcg);
|
| 150 | bool __list_lru_del(struct list_lru *lru, struct list_lru_one *l,
|
| 151 | struct list_head *item, int nid);
|
| 152 |
|
| 153 | |
| 154 | * list_lru_add: add an element to the lru list's tail
|
| 155 | * @lru: the lru pointer
|
| 156 | * @item: the item to be added.
|
| 157 | * @nid: the node id of the sublist to add the item to.
|
| 158 | * @memcg: the cgroup of the sublist to add the item to.
|
| 159 | *
|
| 160 | * If the element is already part of a list, this function returns doing
|
| 161 | * nothing. This means that it is not necessary to keep state about whether or
|
| 162 | * not the element already belongs in the list. That said, this logic only
|
| 163 | * works if the item is in *this* list. If the item might be in some other
|
| 164 | * list, then you cannot rely on this check and you must remove it from the
|
| 165 | * other list before trying to insert it.
|
| 166 | *
|
| 167 | * The lru list consists of many sublists internally; the @nid and @memcg
|
| 168 | * parameters are used to determine which sublist to insert the item into.
|
| 169 | * It's important to use the right value of @nid and @memcg when deleting the
|
| 170 | * item, since it might otherwise get deleted from the wrong sublist.
|
| 171 | *
|
| 172 | * This also applies when attempting to insert the item multiple times - if
|
| 173 | * the item is currently in one sublist and you call list_lru_add() again, you
|
| 174 | * must pass the right @nid and @memcg parameters so that the same sublist is
|
| 175 | * used.
|
| 176 | *
|
| 177 | * You must ensure that the memcg is not freed during this call (e.g., with
|
| 178 | * rcu or by taking a css refcnt).
|
| 179 | *
|
| 180 | * Return: true if the list was updated, false otherwise
|
| 181 |
|
| 182 | bool list_lru_add(struct list_lru *lru, struct list_head *item, int nid,
|
| 183 | struct mem_cgroup *memcg);
|
| 184 |
|
| 185 | bool list_lru_add_irq(struct list_lru *lru, struct list_head *item, int nid,
|
| 186 | struct mem_cgroup *memcg);
|
| 187 |
|
| 188 | |
| 189 | * list_lru_add_obj: add an element to the lru list's tail
|
| 190 | * @lru: the lru pointer
|
| 191 | * @item: the item to be added.
|
| 192 | *
|
| 193 | * This function is similar to list_lru_add(), but the NUMA node and the
|
| 194 | * memcg of the sublist is determined by @item list_head. This assumption is
|
| 195 | * valid for slab objects LRU such as dentries, inodes, etc.
|
| 196 | *
|
| 197 | * Return: true if the list was updated, false otherwise
|
| 198 |
|
| 199 | bool list_lru_add_obj(struct list_lru *lru, struct list_head *item);
|
| 200 |
|
| 201 | |
| 202 | * list_lru_del: delete an element from the lru list
|
| 203 | * @lru: the lru pointer
|
| 204 | * @item: the item to be deleted.
|
| 205 | * @nid: the node id of the sublist to delete the item from.
|
| 206 | * @memcg: the cgroup of the sublist to delete the item from.
|
| 207 | *
|
| 208 | * This function works analogously as list_lru_add() in terms of list
|
| 209 | * manipulation.
|
| 210 | *
|
| 211 | * The comments in list_lru_add() about an element already being in a list are
|
| 212 | * also valid for list_lru_del(), that is, you can delete an item that has
|
| 213 | * already been removed or never been added. However, if the item is in a
|
| 214 | * list, it must be in *this* list, and you must pass the right value of @nid
|
| 215 | * and @memcg so that the right sublist is used.
|
| 216 | *
|
| 217 | * You must ensure that the memcg is not freed during this call (e.g., with
|
| 218 | * rcu or by taking a css refcnt). When a memcg is deleted, list_lru entries
|
| 219 | * are automatically moved to the parent memcg. This is done in a race-free
|
| 220 | * way, so during deletion of an memcg both the old and new memcg will resolve
|
| 221 | * to the same sublist internally.
|
| 222 | *
|
| 223 | * Return: true if the list was updated, false otherwise
|
| 224 |
|
| 225 | bool list_lru_del(struct list_lru *lru, struct list_head *item, int nid,
|
| 226 | struct mem_cgroup *memcg);
|
| 227 |
|
| 228 | |
| 229 | * list_lru_del_obj: delete an element from the lru list
|
| 230 | * @lru: the lru pointer
|
| 231 | * @item: the item to be deleted.
|
| 232 | *
|
| 233 | * This function is similar to list_lru_del(), but the NUMA node and the
|
| 234 | * memcg of the sublist is determined by @item list_head. This assumption is
|
| 235 | * valid for slab objects LRU such as dentries, inodes, etc.
|
| 236 | *
|
| 237 | * Return: true if the list was updated, false otherwise.
|
| 238 |
|
| 239 | bool list_lru_del_obj(struct list_lru *lru, struct list_head *item);
|
| 240 |
|
| 241 | |
| 242 | * list_lru_count_one: return the number of objects currently held by @lru
|
| 243 | * @lru: the lru pointer.
|
| 244 | * @nid: the node id to count from.
|
| 245 | * @memcg: the cgroup to count from.
|
| 246 | *
|
| 247 | * There is no guarantee that the list is not updated while the count is being
|
| 248 | * computed. Callers that want such a guarantee need to provide an outer lock.
|
| 249 | *
|
| 250 | * Return: 0 for empty lists, otherwise the number of objects
|
| 251 | * currently held by @lru.
|
| 252 |
|
| 253 | unsigned long list_lru_count_one(struct list_lru *lru,
|
| 254 | int nid, struct mem_cgroup *memcg);
|
| 255 | unsigned long list_lru_count_node(struct list_lru *lru, int nid);
|
| 256 |
|
| 257 | static inline unsigned long list_lru_shrink_count(struct list_lru *lru,
|
| 258 | struct shrink_control *sc)
|
| 259 | {
|
| 260 | return list_lru_count_one(lru, sc->nid, sc->memcg);
|
| 261 | }
|
| 262 |
|
| 263 | static inline unsigned long list_lru_count(struct list_lru *lru)
|
| 264 | {
|
| 265 | long count = 0;
|
| 266 | int nid;
|
| 267 |
|
| 268 | for_each_node_state(nid, N_NORMAL_MEMORY)
|
| 269 | count += list_lru_count_node(lru, nid);
|
| 270 |
|
| 271 | return count;
|
| 272 | }
|
| 273 |
|
| 274 | void list_lru_isolate(struct list_lru_one *list, struct list_head *item);
|
| 275 | void list_lru_isolate_move(struct list_lru_one *list, struct list_head *item,
|
| 276 | struct list_head *head);
|
| 277 |
|
| 278 | typedef enum lru_status (*list_lru_walk_cb)(struct list_head *item,
|
| 279 | struct list_lru_one *list, void *cb_arg);
|
| 280 |
|
| 281 | |
| 282 | * list_lru_walk_one: walk a @lru, isolating and disposing freeable items.
|
| 283 | * @lru: the lru pointer.
|
| 284 | * @nid: the node id to scan from.
|
| 285 | * @memcg: the cgroup to scan from.
|
| 286 | * @isolate: callback function that is responsible for deciding what to do with
|
| 287 | * the item currently being scanned
|
| 288 | * @cb_arg: opaque type that will be passed to @isolate
|
| 289 | * @nr_to_walk: how many items to scan.
|
| 290 | *
|
| 291 | * This function will scan all elements in a particular @lru, calling the
|
| 292 | * @isolate callback for each of those items, along with the current list
|
| 293 | * spinlock and a caller-provided opaque. The @isolate callback can choose to
|
| 294 | * drop the lock internally, but *must* return with the lock held. The callback
|
| 295 | * will return an enum lru_status telling the @lru infrastructure what to
|
| 296 | * do with the object being scanned.
|
| 297 | *
|
| 298 | * Please note that @nr_to_walk does not mean how many objects will be freed,
|
| 299 | * just how many objects will be scanned.
|
| 300 | *
|
| 301 | * Return: the number of objects effectively removed from the LRU.
|
| 302 |
|
| 303 | unsigned long list_lru_walk_one(struct list_lru *lru,
|
| 304 | int nid, struct mem_cgroup *memcg,
|
| 305 | list_lru_walk_cb isolate, void *cb_arg,
|
| 306 | unsigned long *nr_to_walk);
|
| 307 | |
| 308 | * list_lru_walk_one_irq: walk a @lru, isolating and disposing freeable items.
|
| 309 | * @lru: the lru pointer.
|
| 310 | * @nid: the node id to scan from.
|
| 311 | * @memcg: the cgroup to scan from.
|
| 312 | * @isolate: callback function that is responsible for deciding what to do with
|
| 313 | * the item currently being scanned
|
| 314 | * @cb_arg: opaque type that will be passed to @isolate
|
| 315 | * @nr_to_walk: how many items to scan.
|
| 316 | *
|
| 317 | * Same as list_lru_walk_one() except that the spinlock is acquired with
|
| 318 | * spin_lock_irq().
|
| 319 |
|
| 320 | unsigned long list_lru_walk_one_irq(struct list_lru *lru,
|
| 321 | int nid, struct mem_cgroup *memcg,
|
| 322 | list_lru_walk_cb isolate, void *cb_arg,
|
| 323 | unsigned long *nr_to_walk);
|
| 324 | unsigned long list_lru_walk_node(struct list_lru *lru, int nid,
|
| 325 | list_lru_walk_cb isolate, void *cb_arg,
|
| 326 | unsigned long *nr_to_walk);
|
| 327 |
|
| 328 | static inline unsigned long
|
| 329 | list_lru_shrink_walk(struct list_lru *lru, struct shrink_control *sc,
|
| 330 | list_lru_walk_cb isolate, void *cb_arg)
|
| 331 | {
|
| 332 | return list_lru_walk_one(lru, sc->nid, sc->memcg, isolate, cb_arg,
|
| 333 | &sc->nr_to_scan);
|
| 334 | }
|
| 335 |
|
| 336 | static inline unsigned long
|
| 337 | list_lru_shrink_walk_irq(struct list_lru *lru, struct shrink_control *sc,
|
| 338 | list_lru_walk_cb isolate, void *cb_arg)
|
| 339 | {
|
| 340 | return list_lru_walk_one_irq(lru, sc->nid, sc->memcg, isolate, cb_arg,
|
| 341 | &sc->nr_to_scan);
|
| 342 | }
|
| 343 |
|
| 344 | static inline unsigned long
|
| 345 | list_lru_walk(struct list_lru *lru, list_lru_walk_cb isolate,
|
| 346 | void *cb_arg, unsigned long nr_to_walk)
|
| 347 | {
|
| 348 | long isolated = 0;
|
| 349 | int nid;
|
| 350 |
|
| 351 | for_each_node_state(nid, N_NORMAL_MEMORY) {
|
| 352 | isolated += list_lru_walk_node(lru, nid, isolate,
|
| 353 | cb_arg, &nr_to_walk);
|
| 354 | if (nr_to_walk <= 0)
|
| 355 | break;
|
| 356 | }
|
| 357 | return isolated;
|
| 358 | }
|
| 359 | #endif
|