Branch data     Line data    Source code

       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                 :            : 
      13                 :          0 : bool list_lru_add(struct list_lru *lru, struct list_head *item)
      14                 :            : {
      15                 :     472428 :         int nid = page_to_nid(virt_to_page(item));
      16                 :     472428 :         struct list_lru_node *nlru = &lru->node[nid];
      17                 :            : 
      18                 :            :         spin_lock(&nlru->lock);
      19 [ -  + ][ #  # ]:     472429 :         WARN_ON_ONCE(nlru->nr_items < 0);
                 [ #  # ]
      20         [ +  + ]:     472429 :         if (list_empty(item)) {
      21                 :     386170 :                 list_add_tail(item, &nlru->list);
      22         [ +  + ]:     386170 :                 if (nlru->nr_items++ == 0)
      23                 :            :                         node_set(nid, lru->active_nodes);
      24                 :            :                 spin_unlock(&nlru->lock);
      25                 :     386170 :                 return true;
      26                 :            :         }
      27                 :            :         spin_unlock(&nlru->lock);
      28                 :      86259 :         return false;
      29                 :            : }
      30                 :            : EXPORT_SYMBOL_GPL(list_lru_add);
      31                 :            : 
      32                 :          0 : bool list_lru_del(struct list_lru *lru, struct list_head *item)
      33                 :            : {
      34                 :     311239 :         int nid = page_to_nid(virt_to_page(item));
      35                 :     311239 :         struct list_lru_node *nlru = &lru->node[nid];
      36                 :            : 
      37                 :            :         spin_lock(&nlru->lock);
      38         [ +  - ]:     311239 :         if (!list_empty(item)) {
      39                 :            :                 list_del_init(item);
      40         [ -  + ]:     311239 :                 if (--nlru->nr_items == 0)
      41                 :            :                         node_clear(nid, lru->active_nodes);
      42 [ -  + ][ #  # ]:     311239 :                 WARN_ON_ONCE(nlru->nr_items < 0);
                 [ #  # ]
      43                 :            :                 spin_unlock(&nlru->lock);
      44                 :     311239 :                 return true;
      45                 :            :         }
      46                 :            :         spin_unlock(&nlru->lock);
      47                 :          0 :         return false;
      48                 :            : }
      49                 :            : EXPORT_SYMBOL_GPL(list_lru_del);
      50                 :            : 
      51                 :            : unsigned long
      52                 :          0 : list_lru_count_node(struct list_lru *lru, int nid)
      53                 :            : {
      54                 :            :         unsigned long count = 0;
      55                 :   32063333 :         struct list_lru_node *nlru = &lru->node[nid];
      56                 :            : 
      57                 :            :         spin_lock(&nlru->lock);
      58 [ -  + ][ #  # ]:   32355730 :         WARN_ON_ONCE(nlru->nr_items < 0);
                 [ #  # ]
      59                 :   32355730 :         count += nlru->nr_items;
      60                 :            :         spin_unlock(&nlru->lock);
      61                 :            : 
      62                 :   32389999 :         return count;
      63                 :            : }
      64                 :            : EXPORT_SYMBOL_GPL(list_lru_count_node);
      65                 :            : 
      66                 :            : unsigned long
      67                 :          0 : list_lru_walk_node(struct list_lru *lru, int nid, list_lru_walk_cb isolate,
      68                 :            :                    void *cb_arg, unsigned long *nr_to_walk)
      69                 :            : {
      70                 :            : 
      71                 :        134 :         struct list_lru_node    *nlru = &lru->node[nid];
      72                 :            :         struct list_head *item, *n;
      73                 :            :         unsigned long isolated = 0;
      74                 :            : 
      75                 :            :         spin_lock(&nlru->lock);
      76                 :            : restart:
      77         [ +  + ]:     104315 :         list_for_each_safe(item, n, &nlru->list) {
      78                 :            :                 enum lru_status ret;
      79                 :            : 
      80                 :            :                 /*
      81                 :            :                  * decrement nr_to_walk first so that we don't livelock if we
      82                 :            :                  * get stuck on large numbesr of LRU_RETRY items
      83                 :            :                  */
      84         [ +  + ]:     104302 :                 if (!*nr_to_walk)
      85                 :            :                         break;
      86                 :     104182 :                 --*nr_to_walk;
      87                 :            : 
      88                 :     104182 :                 ret = isolate(item, &nlru->lock, cb_arg);
      89   [ +  +  +  - ]:     104206 :                 switch (ret) {
      90                 :            :                 case LRU_REMOVED:
      91         [ +  + ]:      71434 :                         if (--nlru->nr_items == 0)
      92                 :            :                                 node_clear(nid, lru->active_nodes);
      93 [ -  + ][ #  # ]:      71427 :                         WARN_ON_ONCE(nlru->nr_items < 0);
                 [ #  # ]
      94                 :      71427 :                         isolated++;
      95                 :      71427 :                         break;
      96                 :            :                 case LRU_ROTATE:
      97                 :            :                         list_move_tail(item, &nlru->list);
      98                 :            :                         break;
      99                 :            :                 case LRU_SKIP:
     100                 :            :                         break;
     101                 :            :                 case LRU_RETRY:
     102                 :            :                         /*
     103                 :            :                          * The lru lock has been dropped, our list traversal is
     104                 :            :                          * now invalid and so we have to restart from scratch.
     105                 :            :                          */
     106                 :            :                         goto restart;
     107                 :            :                 default:
     108                 :          0 :                         BUG();
     109                 :            :                 }
     110                 :            :         }
     111                 :            : 
     112                 :            :         spin_unlock(&nlru->lock);
     113                 :        134 :         return isolated;
     114                 :            : }
     115                 :            : EXPORT_SYMBOL_GPL(list_lru_walk_node);
     116                 :            : 
     117                 :          0 : int list_lru_init(struct list_lru *lru)
     118                 :            : {
     119                 :            :         int i;
     120                 :            :         size_t size = sizeof(*lru->node) * nr_node_ids;
     121                 :            : 
     122                 :          6 :         lru->node = kzalloc(size, GFP_KERNEL);
     123         [ +  - ]:          6 :         if (!lru->node)
     124                 :            :                 return -ENOMEM;
     125                 :            : 
     126                 :            :         nodes_clear(lru->active_nodes);
     127         [ +  - ]:         12 :         for (i = 0; i < nr_node_ids; i++) {
     128                 :          6 :                 spin_lock_init(&lru->node[i].lock);
     129                 :          6 :                 INIT_LIST_HEAD(&lru->node[i].list);
     130                 :          6 :                 lru->node[i].nr_items = 0;
     131                 :            :         }
     132                 :            :         return 0;
     133                 :            : }
     134                 :            : EXPORT_SYMBOL_GPL(list_lru_init);
     135                 :            : 
     136                 :          0 : void list_lru_destroy(struct list_lru *lru)
     137                 :            : {
     138                 :          6 :         kfree(lru->node);
     139                 :          6 : }
     140                 :            : EXPORT_SYMBOL_GPL(list_lru_destroy);