list_lru.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649
  1. // SPDX-License-Identifier: GPL-2.0-only
  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. #include <linux/kernel.h>
  9. #include <linux/module.h>
  10. #include <linux/mm.h>
  11. #include <linux/list_lru.h>
  12. #include <linux/slab.h>
  13. #include <linux/mutex.h>
  14. #include <linux/memcontrol.h>
  15. #include "slab.h"
  16. #ifdef CONFIG_MEMCG_KMEM
  17. static LIST_HEAD(list_lrus);
  18. static DEFINE_MUTEX(list_lrus_mutex);
  19. static void list_lru_register(struct list_lru *lru)
  20. {
  21. mutex_lock(&list_lrus_mutex);
  22. list_add(&lru->list, &list_lrus);
  23. mutex_unlock(&list_lrus_mutex);
  24. }
  25. static void list_lru_unregister(struct list_lru *lru)
  26. {
  27. mutex_lock(&list_lrus_mutex);
  28. list_del(&lru->list);
  29. mutex_unlock(&list_lrus_mutex);
  30. }
  31. static int lru_shrinker_id(struct list_lru *lru)
  32. {
  33. return lru->shrinker_id;
  34. }
  35. static inline bool list_lru_memcg_aware(struct list_lru *lru)
  36. {
  37. return lru->memcg_aware;
  38. }
  39. static inline struct list_lru_one *
  40. list_lru_from_memcg_idx(struct list_lru_node *nlru, int idx)
  41. {
  42. struct list_lru_memcg *memcg_lrus;
  43. /*
  44. * Either lock or RCU protects the array of per cgroup lists
  45. * from relocation (see memcg_update_list_lru_node).
  46. */
  47. memcg_lrus = rcu_dereference_check(nlru->memcg_lrus,
  48. lockdep_is_held(&nlru->lock));
  49. if (memcg_lrus && idx >= 0)
  50. return memcg_lrus->lru[idx];
  51. return &nlru->lru;
  52. }
  53. static inline struct list_lru_one *
  54. list_lru_from_kmem(struct list_lru_node *nlru, void *ptr,
  55. struct mem_cgroup **memcg_ptr)
  56. {
  57. struct list_lru_one *l = &nlru->lru;
  58. struct mem_cgroup *memcg = NULL;
  59. if (!nlru->memcg_lrus)
  60. goto out;
  61. memcg = mem_cgroup_from_obj(ptr);
  62. if (!memcg)
  63. goto out;
  64. l = list_lru_from_memcg_idx(nlru, memcg_cache_id(memcg));
  65. out:
  66. if (memcg_ptr)
  67. *memcg_ptr = memcg;
  68. return l;
  69. }
  70. #else
  71. static void list_lru_register(struct list_lru *lru)
  72. {
  73. }
  74. static void list_lru_unregister(struct list_lru *lru)
  75. {
  76. }
  77. static int lru_shrinker_id(struct list_lru *lru)
  78. {
  79. return -1;
  80. }
  81. static inline bool list_lru_memcg_aware(struct list_lru *lru)
  82. {
  83. return false;
  84. }
  85. static inline struct list_lru_one *
  86. list_lru_from_memcg_idx(struct list_lru_node *nlru, int idx)
  87. {
  88. return &nlru->lru;
  89. }
  90. static inline struct list_lru_one *
  91. list_lru_from_kmem(struct list_lru_node *nlru, void *ptr,
  92. struct mem_cgroup **memcg_ptr)
  93. {
  94. if (memcg_ptr)
  95. *memcg_ptr = NULL;
  96. return &nlru->lru;
  97. }
  98. #endif /* CONFIG_MEMCG_KMEM */
  99. bool list_lru_add(struct list_lru *lru, struct list_head *item)
  100. {
  101. int nid = page_to_nid(virt_to_page(item));
  102. struct list_lru_node *nlru = &lru->node[nid];
  103. struct mem_cgroup *memcg;
  104. struct list_lru_one *l;
  105. spin_lock(&nlru->lock);
  106. if (list_empty(item)) {
  107. l = list_lru_from_kmem(nlru, item, &memcg);
  108. list_add_tail(item, &l->list);
  109. /* Set shrinker bit if the first element was added */
  110. if (!l->nr_items++)
  111. memcg_set_shrinker_bit(memcg, nid,
  112. lru_shrinker_id(lru));
  113. nlru->nr_items++;
  114. spin_unlock(&nlru->lock);
  115. return true;
  116. }
  117. spin_unlock(&nlru->lock);
  118. return false;
  119. }
  120. EXPORT_SYMBOL_GPL(list_lru_add);
  121. bool list_lru_del(struct list_lru *lru, struct list_head *item)
  122. {
  123. int nid = page_to_nid(virt_to_page(item));
  124. struct list_lru_node *nlru = &lru->node[nid];
  125. struct list_lru_one *l;
  126. spin_lock(&nlru->lock);
  127. if (!list_empty(item)) {
  128. l = list_lru_from_kmem(nlru, item, NULL);
  129. list_del_init(item);
  130. l->nr_items--;
  131. nlru->nr_items--;
  132. spin_unlock(&nlru->lock);
  133. return true;
  134. }
  135. spin_unlock(&nlru->lock);
  136. return false;
  137. }
  138. EXPORT_SYMBOL_GPL(list_lru_del);
  139. void list_lru_isolate(struct list_lru_one *list, struct list_head *item)
  140. {
  141. list_del_init(item);
  142. list->nr_items--;
  143. }
  144. EXPORT_SYMBOL_GPL(list_lru_isolate);
  145. void list_lru_isolate_move(struct list_lru_one *list, struct list_head *item,
  146. struct list_head *head)
  147. {
  148. list_move(item, head);
  149. list->nr_items--;
  150. }
  151. EXPORT_SYMBOL_GPL(list_lru_isolate_move);
  152. unsigned long list_lru_count_one(struct list_lru *lru,
  153. int nid, struct mem_cgroup *memcg)
  154. {
  155. struct list_lru_node *nlru = &lru->node[nid];
  156. struct list_lru_one *l;
  157. unsigned long count;
  158. rcu_read_lock();
  159. l = list_lru_from_memcg_idx(nlru, memcg_cache_id(memcg));
  160. count = READ_ONCE(l->nr_items);
  161. rcu_read_unlock();
  162. return count;
  163. }
  164. EXPORT_SYMBOL_GPL(list_lru_count_one);
  165. unsigned long list_lru_count_node(struct list_lru *lru, int nid)
  166. {
  167. struct list_lru_node *nlru;
  168. nlru = &lru->node[nid];
  169. return nlru->nr_items;
  170. }
  171. EXPORT_SYMBOL_GPL(list_lru_count_node);
  172. static unsigned long
  173. __list_lru_walk_one(struct list_lru_node *nlru, int memcg_idx,
  174. list_lru_walk_cb isolate, void *cb_arg,
  175. unsigned long *nr_to_walk)
  176. {
  177. struct list_lru_one *l;
  178. struct list_head *item, *n;
  179. unsigned long isolated = 0;
  180. l = list_lru_from_memcg_idx(nlru, memcg_idx);
  181. restart:
  182. list_for_each_safe(item, n, &l->list) {
  183. enum lru_status ret;
  184. /*
  185. * decrement nr_to_walk first so that we don't livelock if we
  186. * get stuck on large numbers of LRU_RETRY items
  187. */
  188. if (!*nr_to_walk)
  189. break;
  190. --*nr_to_walk;
  191. ret = isolate(item, l, &nlru->lock, cb_arg);
  192. switch (ret) {
  193. case LRU_REMOVED_RETRY:
  194. assert_spin_locked(&nlru->lock);
  195. fallthrough;
  196. case LRU_REMOVED:
  197. isolated++;
  198. nlru->nr_items--;
  199. /*
  200. * If the lru lock has been dropped, our list
  201. * traversal is now invalid and so we have to
  202. * restart from scratch.
  203. */
  204. if (ret == LRU_REMOVED_RETRY)
  205. goto restart;
  206. break;
  207. case LRU_ROTATE:
  208. list_move_tail(item, &l->list);
  209. break;
  210. case LRU_SKIP:
  211. break;
  212. case LRU_RETRY:
  213. /*
  214. * The lru lock has been dropped, our list traversal is
  215. * now invalid and so we have to restart from scratch.
  216. */
  217. assert_spin_locked(&nlru->lock);
  218. goto restart;
  219. default:
  220. BUG();
  221. }
  222. }
  223. return isolated;
  224. }
  225. unsigned long
  226. list_lru_walk_one(struct list_lru *lru, int nid, struct mem_cgroup *memcg,
  227. list_lru_walk_cb isolate, void *cb_arg,
  228. unsigned long *nr_to_walk)
  229. {
  230. struct list_lru_node *nlru = &lru->node[nid];
  231. unsigned long ret;
  232. spin_lock(&nlru->lock);
  233. ret = __list_lru_walk_one(nlru, memcg_cache_id(memcg), isolate, cb_arg,
  234. nr_to_walk);
  235. spin_unlock(&nlru->lock);
  236. return ret;
  237. }
  238. EXPORT_SYMBOL_GPL(list_lru_walk_one);
  239. unsigned long
  240. list_lru_walk_one_irq(struct list_lru *lru, int nid, struct mem_cgroup *memcg,
  241. list_lru_walk_cb isolate, void *cb_arg,
  242. unsigned long *nr_to_walk)
  243. {
  244. struct list_lru_node *nlru = &lru->node[nid];
  245. unsigned long ret;
  246. spin_lock_irq(&nlru->lock);
  247. ret = __list_lru_walk_one(nlru, memcg_cache_id(memcg), isolate, cb_arg,
  248. nr_to_walk);
  249. spin_unlock_irq(&nlru->lock);
  250. return ret;
  251. }
  252. unsigned long list_lru_walk_node(struct list_lru *lru, int nid,
  253. list_lru_walk_cb isolate, void *cb_arg,
  254. unsigned long *nr_to_walk)
  255. {
  256. long isolated = 0;
  257. int memcg_idx;
  258. isolated += list_lru_walk_one(lru, nid, NULL, isolate, cb_arg,
  259. nr_to_walk);
  260. if (*nr_to_walk > 0 && list_lru_memcg_aware(lru)) {
  261. for_each_memcg_cache_index(memcg_idx) {
  262. struct list_lru_node *nlru = &lru->node[nid];
  263. spin_lock(&nlru->lock);
  264. isolated += __list_lru_walk_one(nlru, memcg_idx,
  265. isolate, cb_arg,
  266. nr_to_walk);
  267. spin_unlock(&nlru->lock);
  268. if (*nr_to_walk <= 0)
  269. break;
  270. }
  271. }
  272. return isolated;
  273. }
  274. EXPORT_SYMBOL_GPL(list_lru_walk_node);
  275. static void init_one_lru(struct list_lru_one *l)
  276. {
  277. INIT_LIST_HEAD(&l->list);
  278. l->nr_items = 0;
  279. }
  280. #ifdef CONFIG_MEMCG_KMEM
  281. static void __memcg_destroy_list_lru_node(struct list_lru_memcg *memcg_lrus,
  282. int begin, int end)
  283. {
  284. int i;
  285. for (i = begin; i < end; i++)
  286. kfree(memcg_lrus->lru[i]);
  287. }
  288. static int __memcg_init_list_lru_node(struct list_lru_memcg *memcg_lrus,
  289. int begin, int end)
  290. {
  291. int i;
  292. for (i = begin; i < end; i++) {
  293. struct list_lru_one *l;
  294. l = kmalloc(sizeof(struct list_lru_one), GFP_KERNEL);
  295. if (!l)
  296. goto fail;
  297. init_one_lru(l);
  298. memcg_lrus->lru[i] = l;
  299. }
  300. return 0;
  301. fail:
  302. __memcg_destroy_list_lru_node(memcg_lrus, begin, i);
  303. return -ENOMEM;
  304. }
  305. static int memcg_init_list_lru_node(struct list_lru_node *nlru)
  306. {
  307. struct list_lru_memcg *memcg_lrus;
  308. int size = memcg_nr_cache_ids;
  309. memcg_lrus = kvmalloc(sizeof(*memcg_lrus) +
  310. size * sizeof(void *), GFP_KERNEL);
  311. if (!memcg_lrus)
  312. return -ENOMEM;
  313. if (__memcg_init_list_lru_node(memcg_lrus, 0, size)) {
  314. kvfree(memcg_lrus);
  315. return -ENOMEM;
  316. }
  317. RCU_INIT_POINTER(nlru->memcg_lrus, memcg_lrus);
  318. return 0;
  319. }
  320. static void memcg_destroy_list_lru_node(struct list_lru_node *nlru)
  321. {
  322. struct list_lru_memcg *memcg_lrus;
  323. /*
  324. * This is called when shrinker has already been unregistered,
  325. * and nobody can use it. So, there is no need to use kvfree_rcu_local().
  326. */
  327. memcg_lrus = rcu_dereference_protected(nlru->memcg_lrus, true);
  328. __memcg_destroy_list_lru_node(memcg_lrus, 0, memcg_nr_cache_ids);
  329. kvfree(memcg_lrus);
  330. }
  331. static void kvfree_rcu_local(struct rcu_head *head)
  332. {
  333. struct list_lru_memcg *mlru;
  334. mlru = container_of(head, struct list_lru_memcg, rcu);
  335. kvfree(mlru);
  336. }
  337. static int memcg_update_list_lru_node(struct list_lru_node *nlru,
  338. int old_size, int new_size)
  339. {
  340. struct list_lru_memcg *old, *new;
  341. BUG_ON(old_size > new_size);
  342. old = rcu_dereference_protected(nlru->memcg_lrus,
  343. lockdep_is_held(&list_lrus_mutex));
  344. new = kvmalloc(sizeof(*new) + new_size * sizeof(void *), GFP_KERNEL);
  345. if (!new)
  346. return -ENOMEM;
  347. if (__memcg_init_list_lru_node(new, old_size, new_size)) {
  348. kvfree(new);
  349. return -ENOMEM;
  350. }
  351. memcpy(&new->lru, &old->lru, old_size * sizeof(void *));
  352. /*
  353. * The locking below allows readers that hold nlru->lock avoid taking
  354. * rcu_read_lock (see list_lru_from_memcg_idx).
  355. *
  356. * Since list_lru_{add,del} may be called under an IRQ-safe lock,
  357. * we have to use IRQ-safe primitives here to avoid deadlock.
  358. */
  359. spin_lock_irq(&nlru->lock);
  360. rcu_assign_pointer(nlru->memcg_lrus, new);
  361. spin_unlock_irq(&nlru->lock);
  362. call_rcu(&old->rcu, kvfree_rcu_local);
  363. return 0;
  364. }
  365. static void memcg_cancel_update_list_lru_node(struct list_lru_node *nlru,
  366. int old_size, int new_size)
  367. {
  368. struct list_lru_memcg *memcg_lrus;
  369. memcg_lrus = rcu_dereference_protected(nlru->memcg_lrus,
  370. lockdep_is_held(&list_lrus_mutex));
  371. /* do not bother shrinking the array back to the old size, because we
  372. * cannot handle allocation failures here */
  373. __memcg_destroy_list_lru_node(memcg_lrus, old_size, new_size);
  374. }
  375. static int memcg_init_list_lru(struct list_lru *lru, bool memcg_aware)
  376. {
  377. int i;
  378. lru->memcg_aware = memcg_aware;
  379. if (!memcg_aware)
  380. return 0;
  381. for_each_node(i) {
  382. if (memcg_init_list_lru_node(&lru->node[i]))
  383. goto fail;
  384. }
  385. return 0;
  386. fail:
  387. for (i = i - 1; i >= 0; i--) {
  388. if (!lru->node[i].memcg_lrus)
  389. continue;
  390. memcg_destroy_list_lru_node(&lru->node[i]);
  391. }
  392. return -ENOMEM;
  393. }
  394. static void memcg_destroy_list_lru(struct list_lru *lru)
  395. {
  396. int i;
  397. if (!list_lru_memcg_aware(lru))
  398. return;
  399. for_each_node(i)
  400. memcg_destroy_list_lru_node(&lru->node[i]);
  401. }
  402. static int memcg_update_list_lru(struct list_lru *lru,
  403. int old_size, int new_size)
  404. {
  405. int i;
  406. if (!list_lru_memcg_aware(lru))
  407. return 0;
  408. for_each_node(i) {
  409. if (memcg_update_list_lru_node(&lru->node[i],
  410. old_size, new_size))
  411. goto fail;
  412. }
  413. return 0;
  414. fail:
  415. for (i = i - 1; i >= 0; i--) {
  416. if (!lru->node[i].memcg_lrus)
  417. continue;
  418. memcg_cancel_update_list_lru_node(&lru->node[i],
  419. old_size, new_size);
  420. }
  421. return -ENOMEM;
  422. }
  423. static void memcg_cancel_update_list_lru(struct list_lru *lru,
  424. int old_size, int new_size)
  425. {
  426. int i;
  427. if (!list_lru_memcg_aware(lru))
  428. return;
  429. for_each_node(i)
  430. memcg_cancel_update_list_lru_node(&lru->node[i],
  431. old_size, new_size);
  432. }
  433. int memcg_update_all_list_lrus(int new_size)
  434. {
  435. int ret = 0;
  436. struct list_lru *lru;
  437. int old_size = memcg_nr_cache_ids;
  438. mutex_lock(&list_lrus_mutex);
  439. list_for_each_entry(lru, &list_lrus, list) {
  440. ret = memcg_update_list_lru(lru, old_size, new_size);
  441. if (ret)
  442. goto fail;
  443. }
  444. out:
  445. mutex_unlock(&list_lrus_mutex);
  446. return ret;
  447. fail:
  448. list_for_each_entry_continue_reverse(lru, &list_lrus, list)
  449. memcg_cancel_update_list_lru(lru, old_size, new_size);
  450. goto out;
  451. }
  452. static void memcg_drain_list_lru_node(struct list_lru *lru, int nid,
  453. int src_idx, struct mem_cgroup *dst_memcg)
  454. {
  455. struct list_lru_node *nlru = &lru->node[nid];
  456. int dst_idx = dst_memcg->kmemcg_id;
  457. struct list_lru_one *src, *dst;
  458. /*
  459. * Since list_lru_{add,del} may be called under an IRQ-safe lock,
  460. * we have to use IRQ-safe primitives here to avoid deadlock.
  461. */
  462. spin_lock_irq(&nlru->lock);
  463. src = list_lru_from_memcg_idx(nlru, src_idx);
  464. dst = list_lru_from_memcg_idx(nlru, dst_idx);
  465. list_splice_init(&src->list, &dst->list);
  466. if (src->nr_items) {
  467. dst->nr_items += src->nr_items;
  468. memcg_set_shrinker_bit(dst_memcg, nid, lru_shrinker_id(lru));
  469. src->nr_items = 0;
  470. }
  471. spin_unlock_irq(&nlru->lock);
  472. }
  473. static void memcg_drain_list_lru(struct list_lru *lru,
  474. int src_idx, struct mem_cgroup *dst_memcg)
  475. {
  476. int i;
  477. if (!list_lru_memcg_aware(lru))
  478. return;
  479. for_each_node(i)
  480. memcg_drain_list_lru_node(lru, i, src_idx, dst_memcg);
  481. }
  482. void memcg_drain_all_list_lrus(int src_idx, struct mem_cgroup *dst_memcg)
  483. {
  484. struct list_lru *lru;
  485. mutex_lock(&list_lrus_mutex);
  486. list_for_each_entry(lru, &list_lrus, list)
  487. memcg_drain_list_lru(lru, src_idx, dst_memcg);
  488. mutex_unlock(&list_lrus_mutex);
  489. }
  490. #else
  491. static int memcg_init_list_lru(struct list_lru *lru, bool memcg_aware)
  492. {
  493. return 0;
  494. }
  495. static void memcg_destroy_list_lru(struct list_lru *lru)
  496. {
  497. }
  498. #endif /* CONFIG_MEMCG_KMEM */
  499. int __list_lru_init(struct list_lru *lru, bool memcg_aware,
  500. struct lock_class_key *key, struct shrinker *shrinker)
  501. {
  502. int i;
  503. int err = -ENOMEM;
  504. #ifdef CONFIG_MEMCG_KMEM
  505. if (shrinker)
  506. lru->shrinker_id = shrinker->id;
  507. else
  508. lru->shrinker_id = -1;
  509. #endif
  510. memcg_get_cache_ids();
  511. lru->node = kcalloc(nr_node_ids, sizeof(*lru->node), GFP_KERNEL);
  512. if (!lru->node)
  513. goto out;
  514. for_each_node(i) {
  515. spin_lock_init(&lru->node[i].lock);
  516. if (key)
  517. lockdep_set_class(&lru->node[i].lock, key);
  518. init_one_lru(&lru->node[i].lru);
  519. }
  520. err = memcg_init_list_lru(lru, memcg_aware);
  521. if (err) {
  522. kfree(lru->node);
  523. /* Do this so a list_lru_destroy() doesn't crash: */
  524. lru->node = NULL;
  525. goto out;
  526. }
  527. list_lru_register(lru);
  528. out:
  529. memcg_put_cache_ids();
  530. return err;
  531. }
  532. EXPORT_SYMBOL_GPL(__list_lru_init);
  533. void list_lru_destroy(struct list_lru *lru)
  534. {
  535. /* Already destroyed or not yet initialized? */
  536. if (!lru->node)
  537. return;
  538. memcg_get_cache_ids();
  539. list_lru_unregister(lru);
  540. memcg_destroy_list_lru(lru);
  541. kfree(lru->node);
  542. lru->node = NULL;
  543. #ifdef CONFIG_MEMCG_KMEM
  544. lru->shrinker_id = -1;
  545. #endif
  546. memcg_put_cache_ids();
  547. }
  548. EXPORT_SYMBOL_GPL(list_lru_destroy);