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 #include "internal.h"
  17
  18 #ifdef CONFIG_MEMCG
  19 static LIST_HEAD(memcg_list_lrus);
  20 static DEFINE_MUTEX(list_lrus_mutex);
  21
  22 static inline bool list_lru_memcg_aware(struct list_lru *lru)
  23 {
  24         return lru->memcg_aware;
  25 }
  26
  27 static void list_lru_register(struct list_lru *lru)
  28 {
  29         if (!list_lru_memcg_aware(lru))
  30                 return;
  31
  32         mutex_lock(&list_lrus_mutex);
  33         list_add(&lru->list, &memcg_list_lrus);
  34         mutex_unlock(&list_lrus_mutex);
  35 }
  36
  37 static void list_lru_unregister(struct list_lru *lru)
  38 {
  39         if (!list_lru_memcg_aware(lru))
  40                 return;
  41
  42         mutex_lock(&list_lrus_mutex);
  43         list_del(&lru->list);
  44         mutex_unlock(&list_lrus_mutex);
  45 }
  46
  47 static int lru_shrinker_id(struct list_lru *lru)
  48 {
  49         return lru->shrinker_id;
  50 }
  51
  52 static inline struct list_lru_one *
  53 list_lru_from_memcg_idx(struct list_lru *lru, int nid, int idx)
  54 {
  55         if (list_lru_memcg_aware(lru) && idx >= 0) {
  56                 struct list_lru_memcg *mlru = xa_load(&lru->xa, idx);
  57
  58                 return mlru ? &mlru->node[nid] : NULL;
  59         }
  60         return &lru->node[nid].lru;
  61 }
  62
  63 static inline struct list_lru_one *
  64 lock_list_lru_of_memcg(struct list_lru *lru, int nid, struct mem_cgroup *memcg,
  65                        bool irq, bool skip_empty)
  66 {
  67         struct list_lru_one *l;
  68         long nr_items;
  69
  70         rcu_read_lock();
  71 again:
  72         l = list_lru_from_memcg_idx(lru, nid, memcg_kmem_id(memcg));
  73         if (likely(l)) {
  74                 if (irq)
  75                         spin_lock_irq(&l->lock);
  76                 else
  77                         spin_lock(&l->lock);
  78                 nr_items = READ_ONCE(l->nr_items);
  79                 if (likely(nr_items != LONG_MIN)) {
  80                         WARN_ON(nr_items < 0);
  81                         rcu_read_unlock();
  82                         return l;
  83                 }
  84                 if (irq)
  85                         spin_unlock_irq(&l->lock);
  86                 else
  87                         spin_unlock(&l->lock);
  88         }
  89         /*
  90          * Caller may simply bail out if raced with reparenting or
  91          * may iterate through the list_lru and expect empty slots.
  92          */
  93         if (skip_empty) {
  94                 rcu_read_unlock();
  95                 return NULL;
  96         }
  97         VM_WARN_ON(!css_is_dying(&memcg->css));
  98         memcg = parent_mem_cgroup(memcg);
  99         goto again;
 100 }
 101
 102 static inline void unlock_list_lru(struct list_lru_one *l, bool irq_off)
 103 {
 104         if (irq_off)
 105                 spin_unlock_irq(&l->lock);
 106         else
 107                 spin_unlock(&l->lock);
 108 }
 109 #else
 110 static void list_lru_register(struct list_lru *lru)
 111 {
 112 }
 113
 114 static void list_lru_unregister(struct list_lru *lru)
 115 {
 116 }
 117
 118 static int lru_shrinker_id(struct list_lru *lru)
 119 {
 120         return -1;
 121 }
 122
 123 static inline bool list_lru_memcg_aware(struct list_lru *lru)
 124 {
 125         return false;
 126 }
 127
 128 static inline struct list_lru_one *
 129 list_lru_from_memcg_idx(struct list_lru *lru, int nid, int idx)
 130 {
 131         return &lru->node[nid].lru;
 132 }
 133
 134 static inline struct list_lru_one *
 135 lock_list_lru_of_memcg(struct list_lru *lru, int nid, struct mem_cgroup *memcg,
 136                        bool irq, bool skip_empty)
 137 {
 138         struct list_lru_one *l = &lru->node[nid].lru;
 139
 140         if (irq)
 141                 spin_lock_irq(&l->lock);
 142         else
 143                 spin_lock(&l->lock);
 144
 145         return l;
 146 }
 147
 148 static inline void unlock_list_lru(struct list_lru_one *l, bool irq_off)
 149 {
 150         if (irq_off)
 151                 spin_unlock_irq(&l->lock);
 152         else
 153                 spin_unlock(&l->lock);
 154 }
 155 #endif /* CONFIG_MEMCG */
 156
 157 /* The caller must ensure the memcg lifetime. */
 158 bool list_lru_add(struct list_lru *lru, struct list_head *item, int nid,
 159                   struct mem_cgroup *memcg)
 160 {
 161         struct list_lru_node *nlru = &lru->node[nid];
 162         struct list_lru_one *l;
 163
 164         l = lock_list_lru_of_memcg(lru, nid, memcg, false, false);
 165         if (!l)
 166                 return false;
 167         if (list_empty(item)) {
 168                 list_add_tail(item, &l->list);
 169                 /* Set shrinker bit if the first element was added */
 170                 if (!l->nr_items++)
 171                         set_shrinker_bit(memcg, nid, lru_shrinker_id(lru));
 172                 unlock_list_lru(l, false);
 173                 atomic_long_inc(&nlru->nr_items);
 174                 return true;
 175         }
 176         unlock_list_lru(l, false);
 177         return false;
 178 }
 179
 180 bool list_lru_add_obj(struct list_lru *lru, struct list_head *item)
 181 {
 182         bool ret;
 183         int nid = page_to_nid(virt_to_page(item));
 184
 185         if (list_lru_memcg_aware(lru)) {
 186                 rcu_read_lock();
 187                 ret = list_lru_add(lru, item, nid, mem_cgroup_from_slab_obj(item));
 188                 rcu_read_unlock();
 189         } else {
 190                 ret = list_lru_add(lru, item, nid, NULL);
 191         }
 192
 193         return ret;
 194 }
 195 EXPORT_SYMBOL_GPL(list_lru_add_obj);
 196
 197 /* The caller must ensure the memcg lifetime. */
 198 bool list_lru_del(struct list_lru *lru, struct list_head *item, int nid,
 199                   struct mem_cgroup *memcg)
 200 {
 201         struct list_lru_node *nlru = &lru->node[nid];
 202         struct list_lru_one *l;
 203         l = lock_list_lru_of_memcg(lru, nid, memcg, false, false);
 204         if (!l)
 205                 return false;
 206         if (!list_empty(item)) {
 207                 list_del_init(item);
 208                 l->nr_items--;
 209                 unlock_list_lru(l, false);
 210                 atomic_long_dec(&nlru->nr_items);
 211                 return true;
 212         }
 213         unlock_list_lru(l, false);
 214         return false;
 215 }
 216
 217 bool list_lru_del_obj(struct list_lru *lru, struct list_head *item)
 218 {
 219         bool ret;
 220         int nid = page_to_nid(virt_to_page(item));
 221
 222         if (list_lru_memcg_aware(lru)) {
 223                 rcu_read_lock();
 224                 ret = list_lru_del(lru, item, nid, mem_cgroup_from_slab_obj(item));
 225                 rcu_read_unlock();
 226         } else {
 227                 ret = list_lru_del(lru, item, nid, NULL);
 228         }
 229
 230         return ret;
 231 }
 232 EXPORT_SYMBOL_GPL(list_lru_del_obj);
 233
 234 void list_lru_isolate(struct list_lru_one *list, struct list_head *item)
 235 {
 236         list_del_init(item);
 237         list->nr_items--;
 238 }
 239 EXPORT_SYMBOL_GPL(list_lru_isolate);
 240
 241 void list_lru_isolate_move(struct list_lru_one *list, struct list_head *item,
 242                            struct list_head *head)
 243 {
 244         list_move(item, head);
 245         list->nr_items--;
 246 }
 247 EXPORT_SYMBOL_GPL(list_lru_isolate_move);
 248
 249 unsigned long list_lru_count_one(struct list_lru *lru,
 250                                  int nid, struct mem_cgroup *memcg)
 251 {
 252         struct list_lru_one *l;
 253         long count;
 254
 255         rcu_read_lock();
 256         l = list_lru_from_memcg_idx(lru, nid, memcg_kmem_id(memcg));
 257         count = l ? READ_ONCE(l->nr_items) : 0;
 258         rcu_read_unlock();
 259
 260         if (unlikely(count < 0))
 261                 count = 0;
 262
 263         return count;
 264 }
 265 EXPORT_SYMBOL_GPL(list_lru_count_one);
 266
 267 unsigned long list_lru_count_node(struct list_lru *lru, int nid)
 268 {
 269         struct list_lru_node *nlru;
 270
 271         nlru = &lru->node[nid];
 272         return atomic_long_read(&nlru->nr_items);
 273 }
 274 EXPORT_SYMBOL_GPL(list_lru_count_node);
 275
 276 static unsigned long
 277 __list_lru_walk_one(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, bool irq_off)
 280 {
 281         struct list_lru_node *nlru = &lru->node[nid];
 282         struct list_lru_one *l = NULL;
 283         struct list_head *item, *n;
 284         unsigned long isolated = 0;
 285
 286 restart:
 287         l = lock_list_lru_of_memcg(lru, nid, memcg, irq_off, true);
 288         if (!l)
 289                 return isolated;
 290         list_for_each_safe(item, n, &l->list) {
 291                 enum lru_status ret;
 292
 293                 /*
 294                  * decrement nr_to_walk first so that we don't livelock if we
 295                  * get stuck on large numbers of LRU_RETRY items
 296                  */
 297                 if (!*nr_to_walk)
 298                         break;
 299                 --*nr_to_walk;
 300
 301                 ret = isolate(item, l, cb_arg);
 302                 switch (ret) {
 303                 /*
 304                  * LRU_RETRY, LRU_REMOVED_RETRY and LRU_STOP will drop the lru
 305                  * lock. List traversal will have to restart from scratch.
 306                  */
 307                 case LRU_RETRY:
 308                         goto restart;
 309                 case LRU_REMOVED_RETRY:
 310                         fallthrough;
 311                 case LRU_REMOVED:
 312                         isolated++;
 313                         atomic_long_dec(&nlru->nr_items);
 314                         if (ret == LRU_REMOVED_RETRY)
 315                                 goto restart;
 316                         break;
 317                 case LRU_ROTATE:
 318                         list_move_tail(item, &l->list);
 319                         break;
 320                 case LRU_SKIP:
 321                         break;
 322                 case LRU_STOP:
 323                         goto out;
 324                 default:
 325                         BUG();
 326                 }
 327         }
 328         unlock_list_lru(l, irq_off);
 329 out:
 330         return isolated;
 331 }
 332
 333 unsigned long
 334 list_lru_walk_one(struct list_lru *lru, int nid, struct mem_cgroup *memcg,
 335                   list_lru_walk_cb isolate, void *cb_arg,
 336                   unsigned long *nr_to_walk)
 337 {
 338         return __list_lru_walk_one(lru, nid, memcg, isolate,
 339                                    cb_arg, nr_to_walk, false);
 340 }
 341 EXPORT_SYMBOL_GPL(list_lru_walk_one);
 342
 343 unsigned long
 344 list_lru_walk_one_irq(struct list_lru *lru, int nid, struct mem_cgroup *memcg,
 345                       list_lru_walk_cb isolate, void *cb_arg,
 346                       unsigned long *nr_to_walk)
 347 {
 348         return __list_lru_walk_one(lru, nid, memcg, isolate,
 349                                    cb_arg, nr_to_walk, true);
 350 }
 351
 352 unsigned long list_lru_walk_node(struct list_lru *lru, int nid,
 353                                  list_lru_walk_cb isolate, void *cb_arg,
 354                                  unsigned long *nr_to_walk)
 355 {
 356         long isolated = 0;
 357
 358         isolated += list_lru_walk_one(lru, nid, NULL, isolate, cb_arg,
 359                                       nr_to_walk);
 360
 361 #ifdef CONFIG_MEMCG
 362         if (*nr_to_walk > 0 && list_lru_memcg_aware(lru)) {
 363                 struct list_lru_memcg *mlru;
 364                 struct mem_cgroup *memcg;
 365                 unsigned long index;
 366
 367                 xa_for_each(&lru->xa, index, mlru) {
 368                         rcu_read_lock();
 369                         memcg = mem_cgroup_from_id(index);
 370                         if (!mem_cgroup_tryget(memcg)) {
 371                                 rcu_read_unlock();
 372                                 continue;
 373                         }
 374                         rcu_read_unlock();
 375                         isolated += __list_lru_walk_one(lru, nid, memcg,
 376                                                         isolate, cb_arg,
 377                                                         nr_to_walk, false);
 378                         mem_cgroup_put(memcg);
 379
 380                         if (*nr_to_walk <= 0)
 381                                 break;
 382                 }
 383         }
 384 #endif
 385
 386         return isolated;
 387 }
 388 EXPORT_SYMBOL_GPL(list_lru_walk_node);
 389
 390 static void init_one_lru(struct list_lru *lru, struct list_lru_one *l)
 391 {
 392         INIT_LIST_HEAD(&l->list);
 393         spin_lock_init(&l->lock);
 394         l->nr_items = 0;
 395 #ifdef CONFIG_LOCKDEP
 396         if (lru->key)
 397                 lockdep_set_class(&l->lock, lru->key);
 398 #endif
 399 }
 400
 401 #ifdef CONFIG_MEMCG
 402 static struct list_lru_memcg *memcg_init_list_lru_one(struct list_lru *lru, gfp_t gfp)
 403 {
 404         int nid;
 405         struct list_lru_memcg *mlru;
 406
 407         mlru = kmalloc(struct_size(mlru, node, nr_node_ids), gfp);
 408         if (!mlru)
 409                 return NULL;
 410
 411         for_each_node(nid)
 412                 init_one_lru(lru, &mlru->node[nid]);
 413
 414         return mlru;
 415 }
 416
 417 static inline void memcg_init_list_lru(struct list_lru *lru, bool memcg_aware)
 418 {
 419         if (memcg_aware)
 420                 xa_init_flags(&lru->xa, XA_FLAGS_LOCK_IRQ);
 421         lru->memcg_aware = memcg_aware;
 422 }
 423
 424 static void memcg_destroy_list_lru(struct list_lru *lru)
 425 {
 426         XA_STATE(xas, &lru->xa, 0);
 427         struct list_lru_memcg *mlru;
 428
 429         if (!list_lru_memcg_aware(lru))
 430                 return;
 431
 432         xas_lock_irq(&xas);
 433         xas_for_each(&xas, mlru, ULONG_MAX) {
 434                 kfree(mlru);
 435                 xas_store(&xas, NULL);
 436         }
 437         xas_unlock_irq(&xas);
 438 }
 439
 440 static void memcg_reparent_list_lru_one(struct list_lru *lru, int nid,
 441                                         struct list_lru_one *src,
 442                                         struct mem_cgroup *dst_memcg)
 443 {
 444         int dst_idx = dst_memcg->kmemcg_id;
 445         struct list_lru_one *dst;
 446
 447         spin_lock_irq(&src->lock);
 448         dst = list_lru_from_memcg_idx(lru, nid, dst_idx);
 449         spin_lock_nested(&dst->lock, SINGLE_DEPTH_NESTING);
 450
 451         list_splice_init(&src->list, &dst->list);
 452         if (src->nr_items) {
 453                 dst->nr_items += src->nr_items;
 454                 set_shrinker_bit(dst_memcg, nid, lru_shrinker_id(lru));
 455         }
 456         /* Mark the list_lru_one dead */
 457         src->nr_items = LONG_MIN;
 458
 459         spin_unlock(&dst->lock);
 460         spin_unlock_irq(&src->lock);
 461 }
 462
 463 void memcg_reparent_list_lrus(struct mem_cgroup *memcg, struct mem_cgroup *parent)
 464 {
 465         struct list_lru *lru;
 466         int i;
 467
 468         mutex_lock(&list_lrus_mutex);
 469         list_for_each_entry(lru, &memcg_list_lrus, list) {
 470                 struct list_lru_memcg *mlru;
 471                 XA_STATE(xas, &lru->xa, memcg->kmemcg_id);
 472
 473                 /*
 474                  * Lock the Xarray to ensure no on going list_lru_memcg
 475                  * allocation and further allocation will see css_is_dying().
 476                  */
 477                 xas_lock_irq(&xas);
 478                 mlru = xas_store(&xas, NULL);
 479                 xas_unlock_irq(&xas);
 480                 if (!mlru)
 481                         continue;
 482
 483                 /*
 484                  * With Xarray value set to NULL, holding the lru lock below
 485                  * prevents list_lru_{add,del,isolate} from touching the lru,
 486                  * safe to reparent.
 487                  */
 488                 for_each_node(i)
 489                         memcg_reparent_list_lru_one(lru, i, &mlru->node[i], parent);
 490
 491                 /*
 492                  * Here all list_lrus corresponding to the cgroup are guaranteed
 493                  * to remain empty, we can safely free this lru, any further
 494                  * memcg_list_lru_alloc() call will simply bail out.
 495                  */
 496                 kvfree_rcu(mlru, rcu);
 497         }
 498         mutex_unlock(&list_lrus_mutex);
 499 }
 500
 501 static inline bool memcg_list_lru_allocated(struct mem_cgroup *memcg,
 502                                             struct list_lru *lru)
 503 {
 504         int idx = memcg->kmemcg_id;
 505
 506         return idx < 0 || xa_load(&lru->xa, idx);
 507 }
 508
 509 int memcg_list_lru_alloc(struct mem_cgroup *memcg, struct list_lru *lru,
 510                          gfp_t gfp)
 511 {
 512         unsigned long flags;
 513         struct list_lru_memcg *mlru;
 514         struct mem_cgroup *pos, *parent;
 515         XA_STATE(xas, &lru->xa, 0);
 516
 517         if (!list_lru_memcg_aware(lru) || memcg_list_lru_allocated(memcg, lru))
 518                 return 0;
 519
 520         gfp &= GFP_RECLAIM_MASK;
 521         /*
 522          * Because the list_lru can be reparented to the parent cgroup's
 523          * list_lru, we should make sure that this cgroup and all its
 524          * ancestors have allocated list_lru_memcg.
 525          */
 526         do {
 527                 /*
 528                  * Keep finding the farest parent that wasn't populated
 529                  * until found memcg itself.
 530                  */
 531                 pos = memcg;
 532                 parent = parent_mem_cgroup(pos);
 533                 while (!memcg_list_lru_allocated(parent, lru)) {
 534                         pos = parent;
 535                         parent = parent_mem_cgroup(pos);
 536                 }
 537
 538                 mlru = memcg_init_list_lru_one(lru, gfp);
 539                 if (!mlru)
 540                         return -ENOMEM;
 541                 xas_set(&xas, pos->kmemcg_id);
 542                 do {
 543                         xas_lock_irqsave(&xas, flags);
 544                         if (!xas_load(&xas) && !css_is_dying(&pos->css)) {
 545                                 xas_store(&xas, mlru);
 546                                 if (!xas_error(&xas))
 547                                         mlru = NULL;
 548                         }
 549                         xas_unlock_irqrestore(&xas, flags);
 550                 } while (xas_nomem(&xas, gfp));
 551                 if (mlru)
 552                         kfree(mlru);
 553         } while (pos != memcg && !css_is_dying(&pos->css));
 554
 555         return xas_error(&xas);
 556 }
 557 #else
 558 static inline void memcg_init_list_lru(struct list_lru *lru, bool memcg_aware)
 559 {
 560 }
 561
 562 static void memcg_destroy_list_lru(struct list_lru *lru)
 563 {
 564 }
 565 #endif /* CONFIG_MEMCG */
 566
 567 int __list_lru_init(struct list_lru *lru, bool memcg_aware, struct shrinker *shrinker)
 568 {
 569         int i;
 570
 571 #ifdef CONFIG_MEMCG
 572         if (shrinker)
 573                 lru->shrinker_id = shrinker->id;
 574         else
 575                 lru->shrinker_id = -1;
 576
 577         if (mem_cgroup_kmem_disabled())
 578                 memcg_aware = false;
 579 #endif
 580
 581         lru->node = kcalloc(nr_node_ids, sizeof(*lru->node), GFP_KERNEL);
 582         if (!lru->node)
 583                 return -ENOMEM;
 584
 585         for_each_node(i)
 586                 init_one_lru(lru, &lru->node[i].lru);
 587
 588         memcg_init_list_lru(lru, memcg_aware);
 589         list_lru_register(lru);
 590
 591         return 0;
 592 }
 593 EXPORT_SYMBOL_GPL(__list_lru_init);
 594
 595 void list_lru_destroy(struct list_lru *lru)
 596 {
 597         /* Already destroyed or not yet initialized? */
 598         if (!lru->node)
 599                 return;
 600
 601         list_lru_unregister(lru);
 602
 603         memcg_destroy_list_lru(lru);
 604         kfree(lru->node);
 605         lru->node = NULL;
 606
 607 #ifdef CONFIG_MEMCG
 608         lru->shrinker_id = -1;
 609 #endif
 610 }
 611 EXPORT_SYMBOL_GPL(list_lru_destroy);