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