]>
git.proxmox.com Git - mirror_ubuntu-jammy-kernel.git/blob - mm/list_lru.c
1 // SPDX-License-Identifier: GPL-2.0-only
3 * Copyright (c) 2013 Red Hat, Inc. and Parallels Inc. All rights reserved.
4 * Authors: David Chinner and Glauber Costa
6 * Generic LRU infrastructure
8 #include <linux/kernel.h>
9 #include <linux/module.h>
11 #include <linux/list_lru.h>
12 #include <linux/slab.h>
13 #include <linux/mutex.h>
14 #include <linux/memcontrol.h>
17 #ifdef CONFIG_MEMCG_KMEM
18 static LIST_HEAD(list_lrus
);
19 static DEFINE_MUTEX(list_lrus_mutex
);
21 static void list_lru_register(struct list_lru
*lru
)
23 mutex_lock(&list_lrus_mutex
);
24 list_add(&lru
->list
, &list_lrus
);
25 mutex_unlock(&list_lrus_mutex
);
28 static void list_lru_unregister(struct list_lru
*lru
)
30 mutex_lock(&list_lrus_mutex
);
32 mutex_unlock(&list_lrus_mutex
);
35 static int lru_shrinker_id(struct list_lru
*lru
)
37 return lru
->shrinker_id
;
40 static inline bool list_lru_memcg_aware(struct list_lru
*lru
)
42 return lru
->memcg_aware
;
45 static inline struct list_lru_one
*
46 list_lru_from_memcg_idx(struct list_lru_node
*nlru
, int idx
)
48 struct list_lru_memcg
*memcg_lrus
;
50 * Either lock or RCU protects the array of per cgroup lists
51 * from relocation (see memcg_update_list_lru_node).
53 memcg_lrus
= rcu_dereference_check(nlru
->memcg_lrus
,
54 lockdep_is_held(&nlru
->lock
));
55 if (memcg_lrus
&& idx
>= 0)
56 return memcg_lrus
->lru
[idx
];
60 static inline struct list_lru_one
*
61 list_lru_from_kmem(struct list_lru_node
*nlru
, void *ptr
,
62 struct mem_cgroup
**memcg_ptr
)
64 struct list_lru_one
*l
= &nlru
->lru
;
65 struct mem_cgroup
*memcg
= NULL
;
67 if (!nlru
->memcg_lrus
)
70 memcg
= mem_cgroup_from_obj(ptr
);
74 l
= list_lru_from_memcg_idx(nlru
, memcg_cache_id(memcg
));
81 static void list_lru_register(struct list_lru
*lru
)
85 static void list_lru_unregister(struct list_lru
*lru
)
89 static int lru_shrinker_id(struct list_lru
*lru
)
94 static inline bool list_lru_memcg_aware(struct list_lru
*lru
)
99 static inline struct list_lru_one
*
100 list_lru_from_memcg_idx(struct list_lru_node
*nlru
, int idx
)
105 static inline struct list_lru_one
*
106 list_lru_from_kmem(struct list_lru_node
*nlru
, void *ptr
,
107 struct mem_cgroup
**memcg_ptr
)
113 #endif /* CONFIG_MEMCG_KMEM */
115 bool list_lru_add(struct list_lru
*lru
, struct list_head
*item
)
117 int nid
= page_to_nid(virt_to_page(item
));
118 struct list_lru_node
*nlru
= &lru
->node
[nid
];
119 struct mem_cgroup
*memcg
;
120 struct list_lru_one
*l
;
122 spin_lock(&nlru
->lock
);
123 if (list_empty(item
)) {
124 l
= list_lru_from_kmem(nlru
, item
, &memcg
);
125 list_add_tail(item
, &l
->list
);
126 /* Set shrinker bit if the first element was added */
128 set_shrinker_bit(memcg
, nid
,
129 lru_shrinker_id(lru
));
131 spin_unlock(&nlru
->lock
);
134 spin_unlock(&nlru
->lock
);
137 EXPORT_SYMBOL_GPL(list_lru_add
);
139 bool list_lru_del(struct list_lru
*lru
, struct list_head
*item
)
141 int nid
= page_to_nid(virt_to_page(item
));
142 struct list_lru_node
*nlru
= &lru
->node
[nid
];
143 struct list_lru_one
*l
;
145 spin_lock(&nlru
->lock
);
146 if (!list_empty(item
)) {
147 l
= list_lru_from_kmem(nlru
, item
, NULL
);
151 spin_unlock(&nlru
->lock
);
154 spin_unlock(&nlru
->lock
);
157 EXPORT_SYMBOL_GPL(list_lru_del
);
159 void list_lru_isolate(struct list_lru_one
*list
, struct list_head
*item
)
164 EXPORT_SYMBOL_GPL(list_lru_isolate
);
166 void list_lru_isolate_move(struct list_lru_one
*list
, struct list_head
*item
,
167 struct list_head
*head
)
169 list_move(item
, head
);
172 EXPORT_SYMBOL_GPL(list_lru_isolate_move
);
174 unsigned long list_lru_count_one(struct list_lru
*lru
,
175 int nid
, struct mem_cgroup
*memcg
)
177 struct list_lru_node
*nlru
= &lru
->node
[nid
];
178 struct list_lru_one
*l
;
182 l
= list_lru_from_memcg_idx(nlru
, memcg_cache_id(memcg
));
183 count
= READ_ONCE(l
->nr_items
);
188 EXPORT_SYMBOL_GPL(list_lru_count_one
);
190 unsigned long list_lru_count_node(struct list_lru
*lru
, int nid
)
192 struct list_lru_node
*nlru
;
194 nlru
= &lru
->node
[nid
];
195 return nlru
->nr_items
;
197 EXPORT_SYMBOL_GPL(list_lru_count_node
);
200 __list_lru_walk_one(struct list_lru_node
*nlru
, int memcg_idx
,
201 list_lru_walk_cb isolate
, void *cb_arg
,
202 unsigned long *nr_to_walk
)
205 struct list_lru_one
*l
;
206 struct list_head
*item
, *n
;
207 unsigned long isolated
= 0;
209 l
= list_lru_from_memcg_idx(nlru
, memcg_idx
);
211 list_for_each_safe(item
, n
, &l
->list
) {
215 * decrement nr_to_walk first so that we don't livelock if we
216 * get stuck on large numbers of LRU_RETRY items
222 ret
= isolate(item
, l
, &nlru
->lock
, cb_arg
);
224 case LRU_REMOVED_RETRY
:
225 assert_spin_locked(&nlru
->lock
);
231 * If the lru lock has been dropped, our list
232 * traversal is now invalid and so we have to
233 * restart from scratch.
235 if (ret
== LRU_REMOVED_RETRY
)
239 list_move_tail(item
, &l
->list
);
245 * The lru lock has been dropped, our list traversal is
246 * now invalid and so we have to restart from scratch.
248 assert_spin_locked(&nlru
->lock
);
258 list_lru_walk_one(struct list_lru
*lru
, int nid
, struct mem_cgroup
*memcg
,
259 list_lru_walk_cb isolate
, void *cb_arg
,
260 unsigned long *nr_to_walk
)
262 struct list_lru_node
*nlru
= &lru
->node
[nid
];
265 spin_lock(&nlru
->lock
);
266 ret
= __list_lru_walk_one(nlru
, memcg_cache_id(memcg
), isolate
, cb_arg
,
268 spin_unlock(&nlru
->lock
);
271 EXPORT_SYMBOL_GPL(list_lru_walk_one
);
274 list_lru_walk_one_irq(struct list_lru
*lru
, int nid
, struct mem_cgroup
*memcg
,
275 list_lru_walk_cb isolate
, void *cb_arg
,
276 unsigned long *nr_to_walk
)
278 struct list_lru_node
*nlru
= &lru
->node
[nid
];
281 spin_lock_irq(&nlru
->lock
);
282 ret
= __list_lru_walk_one(nlru
, memcg_cache_id(memcg
), isolate
, cb_arg
,
284 spin_unlock_irq(&nlru
->lock
);
288 unsigned long list_lru_walk_node(struct list_lru
*lru
, int nid
,
289 list_lru_walk_cb isolate
, void *cb_arg
,
290 unsigned long *nr_to_walk
)
295 isolated
+= list_lru_walk_one(lru
, nid
, NULL
, isolate
, cb_arg
,
297 if (*nr_to_walk
> 0 && list_lru_memcg_aware(lru
)) {
298 for_each_memcg_cache_index(memcg_idx
) {
299 struct list_lru_node
*nlru
= &lru
->node
[nid
];
301 spin_lock(&nlru
->lock
);
302 isolated
+= __list_lru_walk_one(nlru
, memcg_idx
,
305 spin_unlock(&nlru
->lock
);
307 if (*nr_to_walk
<= 0)
313 EXPORT_SYMBOL_GPL(list_lru_walk_node
);
315 static void init_one_lru(struct list_lru_one
*l
)
317 INIT_LIST_HEAD(&l
->list
);
321 #ifdef CONFIG_MEMCG_KMEM
322 static void __memcg_destroy_list_lru_node(struct list_lru_memcg
*memcg_lrus
,
327 for (i
= begin
; i
< end
; i
++)
328 kfree(memcg_lrus
->lru
[i
]);
331 static int __memcg_init_list_lru_node(struct list_lru_memcg
*memcg_lrus
,
336 for (i
= begin
; i
< end
; i
++) {
337 struct list_lru_one
*l
;
339 l
= kmalloc(sizeof(struct list_lru_one
), GFP_KERNEL
);
344 memcg_lrus
->lru
[i
] = l
;
348 __memcg_destroy_list_lru_node(memcg_lrus
, begin
, i
);
352 static int memcg_init_list_lru_node(struct list_lru_node
*nlru
)
354 struct list_lru_memcg
*memcg_lrus
;
355 int size
= memcg_nr_cache_ids
;
357 memcg_lrus
= kvmalloc(sizeof(*memcg_lrus
) +
358 size
* sizeof(void *), GFP_KERNEL
);
362 if (__memcg_init_list_lru_node(memcg_lrus
, 0, size
)) {
366 RCU_INIT_POINTER(nlru
->memcg_lrus
, memcg_lrus
);
371 static void memcg_destroy_list_lru_node(struct list_lru_node
*nlru
)
373 struct list_lru_memcg
*memcg_lrus
;
375 * This is called when shrinker has already been unregistered,
376 * and nobody can use it. So, there is no need to use kvfree_rcu().
378 memcg_lrus
= rcu_dereference_protected(nlru
->memcg_lrus
, true);
379 __memcg_destroy_list_lru_node(memcg_lrus
, 0, memcg_nr_cache_ids
);
383 static int memcg_update_list_lru_node(struct list_lru_node
*nlru
,
384 int old_size
, int new_size
)
386 struct list_lru_memcg
*old
, *new;
388 BUG_ON(old_size
> new_size
);
390 old
= rcu_dereference_protected(nlru
->memcg_lrus
,
391 lockdep_is_held(&list_lrus_mutex
));
392 new = kvmalloc(sizeof(*new) + new_size
* sizeof(void *), GFP_KERNEL
);
396 if (__memcg_init_list_lru_node(new, old_size
, new_size
)) {
401 memcpy(&new->lru
, &old
->lru
, old_size
* sizeof(void *));
404 * The locking below allows readers that hold nlru->lock avoid taking
405 * rcu_read_lock (see list_lru_from_memcg_idx).
407 * Since list_lru_{add,del} may be called under an IRQ-safe lock,
408 * we have to use IRQ-safe primitives here to avoid deadlock.
410 spin_lock_irq(&nlru
->lock
);
411 rcu_assign_pointer(nlru
->memcg_lrus
, new);
412 spin_unlock_irq(&nlru
->lock
);
414 kvfree_rcu(old
, rcu
);
418 static void memcg_cancel_update_list_lru_node(struct list_lru_node
*nlru
,
419 int old_size
, int new_size
)
421 struct list_lru_memcg
*memcg_lrus
;
423 memcg_lrus
= rcu_dereference_protected(nlru
->memcg_lrus
,
424 lockdep_is_held(&list_lrus_mutex
));
425 /* do not bother shrinking the array back to the old size, because we
426 * cannot handle allocation failures here */
427 __memcg_destroy_list_lru_node(memcg_lrus
, old_size
, new_size
);
430 static int memcg_init_list_lru(struct list_lru
*lru
, bool memcg_aware
)
434 lru
->memcg_aware
= memcg_aware
;
440 if (memcg_init_list_lru_node(&lru
->node
[i
]))
445 for (i
= i
- 1; i
>= 0; i
--) {
446 if (!lru
->node
[i
].memcg_lrus
)
448 memcg_destroy_list_lru_node(&lru
->node
[i
]);
453 static void memcg_destroy_list_lru(struct list_lru
*lru
)
457 if (!list_lru_memcg_aware(lru
))
461 memcg_destroy_list_lru_node(&lru
->node
[i
]);
464 static int memcg_update_list_lru(struct list_lru
*lru
,
465 int old_size
, int new_size
)
469 if (!list_lru_memcg_aware(lru
))
473 if (memcg_update_list_lru_node(&lru
->node
[i
],
479 for (i
= i
- 1; i
>= 0; i
--) {
480 if (!lru
->node
[i
].memcg_lrus
)
483 memcg_cancel_update_list_lru_node(&lru
->node
[i
],
489 static void memcg_cancel_update_list_lru(struct list_lru
*lru
,
490 int old_size
, int new_size
)
494 if (!list_lru_memcg_aware(lru
))
498 memcg_cancel_update_list_lru_node(&lru
->node
[i
],
502 int memcg_update_all_list_lrus(int new_size
)
505 struct list_lru
*lru
;
506 int old_size
= memcg_nr_cache_ids
;
508 mutex_lock(&list_lrus_mutex
);
509 list_for_each_entry(lru
, &list_lrus
, list
) {
510 ret
= memcg_update_list_lru(lru
, old_size
, new_size
);
515 mutex_unlock(&list_lrus_mutex
);
518 list_for_each_entry_continue_reverse(lru
, &list_lrus
, list
)
519 memcg_cancel_update_list_lru(lru
, old_size
, new_size
);
523 static void memcg_drain_list_lru_node(struct list_lru
*lru
, int nid
,
524 int src_idx
, struct mem_cgroup
*dst_memcg
)
526 struct list_lru_node
*nlru
= &lru
->node
[nid
];
527 int dst_idx
= dst_memcg
->kmemcg_id
;
528 struct list_lru_one
*src
, *dst
;
531 * Since list_lru_{add,del} may be called under an IRQ-safe lock,
532 * we have to use IRQ-safe primitives here to avoid deadlock.
534 spin_lock_irq(&nlru
->lock
);
536 src
= list_lru_from_memcg_idx(nlru
, src_idx
);
537 dst
= list_lru_from_memcg_idx(nlru
, dst_idx
);
539 list_splice_init(&src
->list
, &dst
->list
);
542 dst
->nr_items
+= src
->nr_items
;
543 set_shrinker_bit(dst_memcg
, nid
, lru_shrinker_id(lru
));
547 spin_unlock_irq(&nlru
->lock
);
550 static void memcg_drain_list_lru(struct list_lru
*lru
,
551 int src_idx
, struct mem_cgroup
*dst_memcg
)
555 if (!list_lru_memcg_aware(lru
))
559 memcg_drain_list_lru_node(lru
, i
, src_idx
, dst_memcg
);
562 void memcg_drain_all_list_lrus(int src_idx
, struct mem_cgroup
*dst_memcg
)
564 struct list_lru
*lru
;
566 mutex_lock(&list_lrus_mutex
);
567 list_for_each_entry(lru
, &list_lrus
, list
)
568 memcg_drain_list_lru(lru
, src_idx
, dst_memcg
);
569 mutex_unlock(&list_lrus_mutex
);
572 static int memcg_init_list_lru(struct list_lru
*lru
, bool memcg_aware
)
577 static void memcg_destroy_list_lru(struct list_lru
*lru
)
580 #endif /* CONFIG_MEMCG_KMEM */
582 int __list_lru_init(struct list_lru
*lru
, bool memcg_aware
,
583 struct lock_class_key
*key
, struct shrinker
*shrinker
)
588 #ifdef CONFIG_MEMCG_KMEM
590 lru
->shrinker_id
= shrinker
->id
;
592 lru
->shrinker_id
= -1;
594 memcg_get_cache_ids();
596 lru
->node
= kcalloc(nr_node_ids
, sizeof(*lru
->node
), GFP_KERNEL
);
601 spin_lock_init(&lru
->node
[i
].lock
);
603 lockdep_set_class(&lru
->node
[i
].lock
, key
);
604 init_one_lru(&lru
->node
[i
].lru
);
607 err
= memcg_init_list_lru(lru
, memcg_aware
);
610 /* Do this so a list_lru_destroy() doesn't crash: */
615 list_lru_register(lru
);
617 memcg_put_cache_ids();
620 EXPORT_SYMBOL_GPL(__list_lru_init
);
622 void list_lru_destroy(struct list_lru
*lru
)
624 /* Already destroyed or not yet initialized? */
628 memcg_get_cache_ids();
630 list_lru_unregister(lru
);
632 memcg_destroy_list_lru(lru
);
636 #ifdef CONFIG_MEMCG_KMEM
637 lru
->shrinker_id
= -1;
639 memcg_put_cache_ids();
641 EXPORT_SYMBOL_GPL(list_lru_destroy
);