mm/list_lru.c

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