Back to home page

LXR

 
 

    


0001 /*
0002  * Copyright (c) 2013 Red Hat, Inc. and Parallels Inc. All rights reserved.
0003  * Authors: David Chinner and Glauber Costa
0004  *
0005  * Generic LRU infrastructure
0006  */
0007 #include <linux/kernel.h>
0008 #include <linux/module.h>
0009 #include <linux/mm.h>
0010 #include <linux/list_lru.h>
0011 #include <linux/slab.h>
0012 #include <linux/mutex.h>
0013 #include <linux/memcontrol.h>
0014 
0015 #if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
0016 static LIST_HEAD(list_lrus);
0017 static DEFINE_MUTEX(list_lrus_mutex);
0018 
0019 static void list_lru_register(struct list_lru *lru)
0020 {
0021     mutex_lock(&list_lrus_mutex);
0022     list_add(&lru->list, &list_lrus);
0023     mutex_unlock(&list_lrus_mutex);
0024 }
0025 
0026 static void list_lru_unregister(struct list_lru *lru)
0027 {
0028     mutex_lock(&list_lrus_mutex);
0029     list_del(&lru->list);
0030     mutex_unlock(&list_lrus_mutex);
0031 }
0032 #else
0033 static void list_lru_register(struct list_lru *lru)
0034 {
0035 }
0036 
0037 static void list_lru_unregister(struct list_lru *lru)
0038 {
0039 }
0040 #endif /* CONFIG_MEMCG && !CONFIG_SLOB */
0041 
0042 #if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
0043 static inline bool list_lru_memcg_aware(struct list_lru *lru)
0044 {
0045     /*
0046      * This needs node 0 to be always present, even
0047      * in the systems supporting sparse numa ids.
0048      */
0049     return !!lru->node[0].memcg_lrus;
0050 }
0051 
0052 static inline struct list_lru_one *
0053 list_lru_from_memcg_idx(struct list_lru_node *nlru, int idx)
0054 {
0055     /*
0056      * The lock protects the array of per cgroup lists from relocation
0057      * (see memcg_update_list_lru_node).
0058      */
0059     lockdep_assert_held(&nlru->lock);
0060     if (nlru->memcg_lrus && idx >= 0)
0061         return nlru->memcg_lrus->lru[idx];
0062 
0063     return &nlru->lru;
0064 }
0065 
0066 static __always_inline struct mem_cgroup *mem_cgroup_from_kmem(void *ptr)
0067 {
0068     struct page *page;
0069 
0070     if (!memcg_kmem_enabled())
0071         return NULL;
0072     page = virt_to_head_page(ptr);
0073     return page->mem_cgroup;
0074 }
0075 
0076 static inline struct list_lru_one *
0077 list_lru_from_kmem(struct list_lru_node *nlru, void *ptr)
0078 {
0079     struct mem_cgroup *memcg;
0080 
0081     if (!nlru->memcg_lrus)
0082         return &nlru->lru;
0083 
0084     memcg = mem_cgroup_from_kmem(ptr);
0085     if (!memcg)
0086         return &nlru->lru;
0087 
0088     return list_lru_from_memcg_idx(nlru, memcg_cache_id(memcg));
0089 }
0090 #else
0091 static inline bool list_lru_memcg_aware(struct list_lru *lru)
0092 {
0093     return false;
0094 }
0095 
0096 static inline struct list_lru_one *
0097 list_lru_from_memcg_idx(struct list_lru_node *nlru, int idx)
0098 {
0099     return &nlru->lru;
0100 }
0101 
0102 static inline struct list_lru_one *
0103 list_lru_from_kmem(struct list_lru_node *nlru, void *ptr)
0104 {
0105     return &nlru->lru;
0106 }
0107 #endif /* CONFIG_MEMCG && !CONFIG_SLOB */
0108 
0109 bool list_lru_add(struct list_lru *lru, struct list_head *item)
0110 {
0111     int nid = page_to_nid(virt_to_page(item));
0112     struct list_lru_node *nlru = &lru->node[nid];
0113     struct list_lru_one *l;
0114 
0115     spin_lock(&nlru->lock);
0116     if (list_empty(item)) {
0117         l = list_lru_from_kmem(nlru, item);
0118         list_add_tail(item, &l->list);
0119         l->nr_items++;
0120         spin_unlock(&nlru->lock);
0121         return true;
0122     }
0123     spin_unlock(&nlru->lock);
0124     return false;
0125 }
0126 EXPORT_SYMBOL_GPL(list_lru_add);
0127 
0128 bool list_lru_del(struct list_lru *lru, struct list_head *item)
0129 {
0130     int nid = page_to_nid(virt_to_page(item));
0131     struct list_lru_node *nlru = &lru->node[nid];
0132     struct list_lru_one *l;
0133 
0134     spin_lock(&nlru->lock);
0135     if (!list_empty(item)) {
0136         l = list_lru_from_kmem(nlru, item);
0137         list_del_init(item);
0138         l->nr_items--;
0139         spin_unlock(&nlru->lock);
0140         return true;
0141     }
0142     spin_unlock(&nlru->lock);
0143     return false;
0144 }
0145 EXPORT_SYMBOL_GPL(list_lru_del);
0146 
0147 void list_lru_isolate(struct list_lru_one *list, struct list_head *item)
0148 {
0149     list_del_init(item);
0150     list->nr_items--;
0151 }
0152 EXPORT_SYMBOL_GPL(list_lru_isolate);
0153 
0154 void list_lru_isolate_move(struct list_lru_one *list, struct list_head *item,
0155                struct list_head *head)
0156 {
0157     list_move(item, head);
0158     list->nr_items--;
0159 }
0160 EXPORT_SYMBOL_GPL(list_lru_isolate_move);
0161 
0162 static unsigned long __list_lru_count_one(struct list_lru *lru,
0163                       int nid, int memcg_idx)
0164 {
0165     struct list_lru_node *nlru = &lru->node[nid];
0166     struct list_lru_one *l;
0167     unsigned long count;
0168 
0169     spin_lock(&nlru->lock);
0170     l = list_lru_from_memcg_idx(nlru, memcg_idx);
0171     count = l->nr_items;
0172     spin_unlock(&nlru->lock);
0173 
0174     return count;
0175 }
0176 
0177 unsigned long list_lru_count_one(struct list_lru *lru,
0178                  int nid, struct mem_cgroup *memcg)
0179 {
0180     return __list_lru_count_one(lru, nid, memcg_cache_id(memcg));
0181 }
0182 EXPORT_SYMBOL_GPL(list_lru_count_one);
0183 
0184 unsigned long list_lru_count_node(struct list_lru *lru, int nid)
0185 {
0186     long count = 0;
0187     int memcg_idx;
0188 
0189     count += __list_lru_count_one(lru, nid, -1);
0190     if (list_lru_memcg_aware(lru)) {
0191         for_each_memcg_cache_index(memcg_idx)
0192             count += __list_lru_count_one(lru, nid, memcg_idx);
0193     }
0194     return count;
0195 }
0196 EXPORT_SYMBOL_GPL(list_lru_count_node);
0197 
0198 static unsigned long
0199 __list_lru_walk_one(struct list_lru *lru, int nid, int memcg_idx,
0200             list_lru_walk_cb isolate, void *cb_arg,
0201             unsigned long *nr_to_walk)
0202 {
0203 
0204     struct list_lru_node *nlru = &lru->node[nid];
0205     struct list_lru_one *l;
0206     struct list_head *item, *n;
0207     unsigned long isolated = 0;
0208 
0209     spin_lock(&nlru->lock);
0210     l = list_lru_from_memcg_idx(nlru, memcg_idx);
0211 restart:
0212     list_for_each_safe(item, n, &l->list) {
0213         enum lru_status ret;
0214 
0215         /*
0216          * decrement nr_to_walk first so that we don't livelock if we
0217          * get stuck on large numbesr of LRU_RETRY items
0218          */
0219         if (!*nr_to_walk)
0220             break;
0221         --*nr_to_walk;
0222 
0223         ret = isolate(item, l, &nlru->lock, cb_arg);
0224         switch (ret) {
0225         case LRU_REMOVED_RETRY:
0226             assert_spin_locked(&nlru->lock);
0227         case LRU_REMOVED:
0228             isolated++;
0229             /*
0230              * If the lru lock has been dropped, our list
0231              * traversal is now invalid and so we have to
0232              * restart from scratch.
0233              */
0234             if (ret == LRU_REMOVED_RETRY)
0235                 goto restart;
0236             break;
0237         case LRU_ROTATE:
0238             list_move_tail(item, &l->list);
0239             break;
0240         case LRU_SKIP:
0241             break;
0242         case LRU_RETRY:
0243             /*
0244              * The lru lock has been dropped, our list traversal is
0245              * now invalid and so we have to restart from scratch.
0246              */
0247             assert_spin_locked(&nlru->lock);
0248             goto restart;
0249         default:
0250             BUG();
0251         }
0252     }
0253 
0254     spin_unlock(&nlru->lock);
0255     return isolated;
0256 }
0257 
0258 unsigned long
0259 list_lru_walk_one(struct list_lru *lru, int nid, struct mem_cgroup *memcg,
0260           list_lru_walk_cb isolate, void *cb_arg,
0261           unsigned long *nr_to_walk)
0262 {
0263     return __list_lru_walk_one(lru, nid, memcg_cache_id(memcg),
0264                    isolate, cb_arg, nr_to_walk);
0265 }
0266 EXPORT_SYMBOL_GPL(list_lru_walk_one);
0267 
0268 unsigned long list_lru_walk_node(struct list_lru *lru, int nid,
0269                  list_lru_walk_cb isolate, void *cb_arg,
0270                  unsigned long *nr_to_walk)
0271 {
0272     long isolated = 0;
0273     int memcg_idx;
0274 
0275     isolated += __list_lru_walk_one(lru, nid, -1, isolate, cb_arg,
0276                     nr_to_walk);
0277     if (*nr_to_walk > 0 && list_lru_memcg_aware(lru)) {
0278         for_each_memcg_cache_index(memcg_idx) {
0279             isolated += __list_lru_walk_one(lru, nid, memcg_idx,
0280                         isolate, cb_arg, nr_to_walk);
0281             if (*nr_to_walk <= 0)
0282                 break;
0283         }
0284     }
0285     return isolated;
0286 }
0287 EXPORT_SYMBOL_GPL(list_lru_walk_node);
0288 
0289 static void init_one_lru(struct list_lru_one *l)
0290 {
0291     INIT_LIST_HEAD(&l->list);
0292     l->nr_items = 0;
0293 }
0294 
0295 #if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
0296 static void __memcg_destroy_list_lru_node(struct list_lru_memcg *memcg_lrus,
0297                       int begin, int end)
0298 {
0299     int i;
0300 
0301     for (i = begin; i < end; i++)
0302         kfree(memcg_lrus->lru[i]);
0303 }
0304 
0305 static int __memcg_init_list_lru_node(struct list_lru_memcg *memcg_lrus,
0306                       int begin, int end)
0307 {
0308     int i;
0309 
0310     for (i = begin; i < end; i++) {
0311         struct list_lru_one *l;
0312 
0313         l = kmalloc(sizeof(struct list_lru_one), GFP_KERNEL);
0314         if (!l)
0315             goto fail;
0316 
0317         init_one_lru(l);
0318         memcg_lrus->lru[i] = l;
0319     }
0320     return 0;
0321 fail:
0322     __memcg_destroy_list_lru_node(memcg_lrus, begin, i - 1);
0323     return -ENOMEM;
0324 }
0325 
0326 static int memcg_init_list_lru_node(struct list_lru_node *nlru)
0327 {
0328     int size = memcg_nr_cache_ids;
0329 
0330     nlru->memcg_lrus = kmalloc(size * sizeof(void *), GFP_KERNEL);
0331     if (!nlru->memcg_lrus)
0332         return -ENOMEM;
0333 
0334     if (__memcg_init_list_lru_node(nlru->memcg_lrus, 0, size)) {
0335         kfree(nlru->memcg_lrus);
0336         return -ENOMEM;
0337     }
0338 
0339     return 0;
0340 }
0341 
0342 static void memcg_destroy_list_lru_node(struct list_lru_node *nlru)
0343 {
0344     __memcg_destroy_list_lru_node(nlru->memcg_lrus, 0, memcg_nr_cache_ids);
0345     kfree(nlru->memcg_lrus);
0346 }
0347 
0348 static int memcg_update_list_lru_node(struct list_lru_node *nlru,
0349                       int old_size, int new_size)
0350 {
0351     struct list_lru_memcg *old, *new;
0352 
0353     BUG_ON(old_size > new_size);
0354 
0355     old = nlru->memcg_lrus;
0356     new = kmalloc(new_size * sizeof(void *), GFP_KERNEL);
0357     if (!new)
0358         return -ENOMEM;
0359 
0360     if (__memcg_init_list_lru_node(new, old_size, new_size)) {
0361         kfree(new);
0362         return -ENOMEM;
0363     }
0364 
0365     memcpy(new, old, old_size * sizeof(void *));
0366 
0367     /*
0368      * The lock guarantees that we won't race with a reader
0369      * (see list_lru_from_memcg_idx).
0370      *
0371      * Since list_lru_{add,del} may be called under an IRQ-safe lock,
0372      * we have to use IRQ-safe primitives here to avoid deadlock.
0373      */
0374     spin_lock_irq(&nlru->lock);
0375     nlru->memcg_lrus = new;
0376     spin_unlock_irq(&nlru->lock);
0377 
0378     kfree(old);
0379     return 0;
0380 }
0381 
0382 static void memcg_cancel_update_list_lru_node(struct list_lru_node *nlru,
0383                           int old_size, int new_size)
0384 {
0385     /* do not bother shrinking the array back to the old size, because we
0386      * cannot handle allocation failures here */
0387     __memcg_destroy_list_lru_node(nlru->memcg_lrus, old_size, new_size);
0388 }
0389 
0390 static int memcg_init_list_lru(struct list_lru *lru, bool memcg_aware)
0391 {
0392     int i;
0393 
0394     if (!memcg_aware)
0395         return 0;
0396 
0397     for_each_node(i) {
0398         if (memcg_init_list_lru_node(&lru->node[i]))
0399             goto fail;
0400     }
0401     return 0;
0402 fail:
0403     for (i = i - 1; i >= 0; i--) {
0404         if (!lru->node[i].memcg_lrus)
0405             continue;
0406         memcg_destroy_list_lru_node(&lru->node[i]);
0407     }
0408     return -ENOMEM;
0409 }
0410 
0411 static void memcg_destroy_list_lru(struct list_lru *lru)
0412 {
0413     int i;
0414 
0415     if (!list_lru_memcg_aware(lru))
0416         return;
0417 
0418     for_each_node(i)
0419         memcg_destroy_list_lru_node(&lru->node[i]);
0420 }
0421 
0422 static int memcg_update_list_lru(struct list_lru *lru,
0423                  int old_size, int new_size)
0424 {
0425     int i;
0426 
0427     if (!list_lru_memcg_aware(lru))
0428         return 0;
0429 
0430     for_each_node(i) {
0431         if (memcg_update_list_lru_node(&lru->node[i],
0432                            old_size, new_size))
0433             goto fail;
0434     }
0435     return 0;
0436 fail:
0437     for (i = i - 1; i >= 0; i--) {
0438         if (!lru->node[i].memcg_lrus)
0439             continue;
0440 
0441         memcg_cancel_update_list_lru_node(&lru->node[i],
0442                           old_size, new_size);
0443     }
0444     return -ENOMEM;
0445 }
0446 
0447 static void memcg_cancel_update_list_lru(struct list_lru *lru,
0448                      int old_size, int new_size)
0449 {
0450     int i;
0451 
0452     if (!list_lru_memcg_aware(lru))
0453         return;
0454 
0455     for_each_node(i)
0456         memcg_cancel_update_list_lru_node(&lru->node[i],
0457                           old_size, new_size);
0458 }
0459 
0460 int memcg_update_all_list_lrus(int new_size)
0461 {
0462     int ret = 0;
0463     struct list_lru *lru;
0464     int old_size = memcg_nr_cache_ids;
0465 
0466     mutex_lock(&list_lrus_mutex);
0467     list_for_each_entry(lru, &list_lrus, list) {
0468         ret = memcg_update_list_lru(lru, old_size, new_size);
0469         if (ret)
0470             goto fail;
0471     }
0472 out:
0473     mutex_unlock(&list_lrus_mutex);
0474     return ret;
0475 fail:
0476     list_for_each_entry_continue_reverse(lru, &list_lrus, list)
0477         memcg_cancel_update_list_lru(lru, old_size, new_size);
0478     goto out;
0479 }
0480 
0481 static void memcg_drain_list_lru_node(struct list_lru_node *nlru,
0482                       int src_idx, int dst_idx)
0483 {
0484     struct list_lru_one *src, *dst;
0485 
0486     /*
0487      * Since list_lru_{add,del} may be called under an IRQ-safe lock,
0488      * we have to use IRQ-safe primitives here to avoid deadlock.
0489      */
0490     spin_lock_irq(&nlru->lock);
0491 
0492     src = list_lru_from_memcg_idx(nlru, src_idx);
0493     dst = list_lru_from_memcg_idx(nlru, dst_idx);
0494 
0495     list_splice_init(&src->list, &dst->list);
0496     dst->nr_items += src->nr_items;
0497     src->nr_items = 0;
0498 
0499     spin_unlock_irq(&nlru->lock);
0500 }
0501 
0502 static void memcg_drain_list_lru(struct list_lru *lru,
0503                  int src_idx, int dst_idx)
0504 {
0505     int i;
0506 
0507     if (!list_lru_memcg_aware(lru))
0508         return;
0509 
0510     for_each_node(i)
0511         memcg_drain_list_lru_node(&lru->node[i], src_idx, dst_idx);
0512 }
0513 
0514 void memcg_drain_all_list_lrus(int src_idx, int dst_idx)
0515 {
0516     struct list_lru *lru;
0517 
0518     mutex_lock(&list_lrus_mutex);
0519     list_for_each_entry(lru, &list_lrus, list)
0520         memcg_drain_list_lru(lru, src_idx, dst_idx);
0521     mutex_unlock(&list_lrus_mutex);
0522 }
0523 #else
0524 static int memcg_init_list_lru(struct list_lru *lru, bool memcg_aware)
0525 {
0526     return 0;
0527 }
0528 
0529 static void memcg_destroy_list_lru(struct list_lru *lru)
0530 {
0531 }
0532 #endif /* CONFIG_MEMCG && !CONFIG_SLOB */
0533 
0534 int __list_lru_init(struct list_lru *lru, bool memcg_aware,
0535             struct lock_class_key *key)
0536 {
0537     int i;
0538     size_t size = sizeof(*lru->node) * nr_node_ids;
0539     int err = -ENOMEM;
0540 
0541     memcg_get_cache_ids();
0542 
0543     lru->node = kzalloc(size, GFP_KERNEL);
0544     if (!lru->node)
0545         goto out;
0546 
0547     for_each_node(i) {
0548         spin_lock_init(&lru->node[i].lock);
0549         if (key)
0550             lockdep_set_class(&lru->node[i].lock, key);
0551         init_one_lru(&lru->node[i].lru);
0552     }
0553 
0554     err = memcg_init_list_lru(lru, memcg_aware);
0555     if (err) {
0556         kfree(lru->node);
0557         /* Do this so a list_lru_destroy() doesn't crash: */
0558         lru->node = NULL;
0559         goto out;
0560     }
0561 
0562     list_lru_register(lru);
0563 out:
0564     memcg_put_cache_ids();
0565     return err;
0566 }
0567 EXPORT_SYMBOL_GPL(__list_lru_init);
0568 
0569 void list_lru_destroy(struct list_lru *lru)
0570 {
0571     /* Already destroyed or not yet initialized? */
0572     if (!lru->node)
0573         return;
0574 
0575     memcg_get_cache_ids();
0576 
0577     list_lru_unregister(lru);
0578 
0579     memcg_destroy_list_lru(lru);
0580     kfree(lru->node);
0581     lru->node = NULL;
0582 
0583     memcg_put_cache_ids();
0584 }
0585 EXPORT_SYMBOL_GPL(list_lru_destroy);