mm/list_lru.c

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