Line data    Source code

       1             : // SPDX-License-Identifier: GPL-2.0
       2             : 
       3             : #include <linux/mm.h>
       4             : #include "lru_cache.h"
       5             : #include "messages.h"
       6             : 
       7             : /*
       8             :  * Initialize a cache object.
       9             :  *
      10             :  * @cache:      The cache.
      11             :  * @max_size:   Maximum size (number of entries) for the cache.
      12             :  *              Use 0 for unlimited size, it's the user's responsability to
      13             :  *              trim the cache in that case.
      14             :  */
      15         850 : void btrfs_lru_cache_init(struct btrfs_lru_cache *cache, unsigned int max_size)
      16             : {
      17         850 :         INIT_LIST_HEAD(&cache->lru_list);
      18         850 :         mt_init(&cache->entries);
      19         847 :         cache->size = 0;
      20         847 :         cache->max_size = max_size;
      21         847 : }
      22             : 
      23     5882572 : static struct btrfs_lru_cache_entry *match_entry(struct list_head *head, u64 key,
      24             :                                                  u64 gen)
      25             : {
      26     5882572 :         struct btrfs_lru_cache_entry *entry;
      27             : 
      28     5882605 :         list_for_each_entry(entry, head, list) {
      29     5882680 :                 if (entry->key == key && entry->gen == gen)
      30     5882647 :                         return entry;
      31             :         }
      32             : 
      33             :         return NULL;
      34             : }
      35             : 
      36             : /*
      37             :  * Lookup for an entry in the cache.
      38             :  *
      39             :  * @cache:      The cache.
      40             :  * @key:        The key of the entry we are looking for.
      41             :  * @gen:        Generation associated to the key.
      42             :  *
      43             :  * Returns the entry associated with the key or NULL if none found.
      44             :  */
      45     7756846 : struct btrfs_lru_cache_entry *btrfs_lru_cache_lookup(struct btrfs_lru_cache *cache,
      46             :                                                      u64 key, u64 gen)
      47             : {
      48     7756846 :         struct list_head *head;
      49     7756846 :         struct btrfs_lru_cache_entry *entry;
      50             : 
      51     7756846 :         head = mtree_load(&cache->entries, key);
      52     7757384 :         if (!head)
      53             :                 return NULL;
      54             : 
      55     5881989 :         entry = match_entry(head, key, gen);
      56     5882722 :         if (entry)
      57     5882715 :                 list_move_tail(&entry->lru_list, &cache->lru_list);
      58             : 
      59             :         return entry;
      60             : }
      61             : 
      62             : /*
      63             :  * Remove an entry from the cache.
      64             :  *
      65             :  * @cache:     The cache to remove from.
      66             :  * @entry:     The entry to remove from the cache.
      67             :  *
      68             :  * Note: this also frees the memory used by the entry.
      69             :  */
      70     1752291 : void btrfs_lru_cache_remove(struct btrfs_lru_cache *cache,
      71             :                             struct btrfs_lru_cache_entry *entry)
      72             : {
      73     1752291 :         struct list_head *prev = entry->list.prev;
      74             : 
      75     1752291 :         ASSERT(cache->size > 0);
      76     1752291 :         ASSERT(!mtree_empty(&cache->entries));
      77             : 
      78     1752291 :         list_del(&entry->list);
      79     1752307 :         list_del(&entry->lru_list);
      80             : 
      81     1752341 :         if (list_empty(prev)) {
      82     1752330 :                 struct list_head *head;
      83             : 
      84             :                 /*
      85             :                  * If previous element in the list entry->list is now empty, it
      86             :                  * means it's a head entry not pointing to any cached entries,
      87             :                  * so remove it from the maple tree and free it.
      88             :                  */
      89     1752330 :                 head = mtree_erase(&cache->entries, entry->key);
      90     1752314 :                 ASSERT(head == prev);
      91     1752314 :                 kfree(head);
      92             :         }
      93             : 
      94     1752356 :         kfree(entry);
      95     1752332 :         cache->size--;
      96     1752332 : }
      97             : 
      98             : /*
      99             :  * Store an entry in the cache.
     100             :  *
     101             :  * @cache:      The cache.
     102             :  * @entry:      The entry to store.
     103             :  *
     104             :  * Returns 0 on success and < 0 on error.
     105             :  */
     106     1752370 : int btrfs_lru_cache_store(struct btrfs_lru_cache *cache,
     107             :                           struct btrfs_lru_cache_entry *new_entry,
     108             :                           gfp_t gfp)
     109             : {
     110     1752370 :         const u64 key = new_entry->key;
     111     1752370 :         struct list_head *head;
     112     1752370 :         int ret;
     113             : 
     114     1752370 :         head = kmalloc(sizeof(*head), gfp);
     115     1752372 :         if (!head)
     116             :                 return -ENOMEM;
     117             : 
     118     1752372 :         ret = mtree_insert(&cache->entries, key, head, gfp);
     119     1752329 :         if (ret == 0) {
     120     1752319 :                 INIT_LIST_HEAD(head);
     121     1752319 :                 list_add_tail(&new_entry->list, head);
     122          10 :         } else if (ret == -EEXIST) {
     123          10 :                 kfree(head);
     124          10 :                 head = mtree_load(&cache->entries, key);
     125          10 :                 ASSERT(head != NULL);
     126          10 :                 if (match_entry(head, key, new_entry->gen) != NULL)
     127             :                         return -EEXIST;
     128          10 :                 list_add_tail(&new_entry->list, head);
     129           0 :         } else if (ret < 0) {
     130           0 :                 kfree(head);
     131           0 :                 return ret;
     132             :         }
     133             : 
     134     1752335 :         if (cache->max_size > 0 && cache->size == cache->max_size) {
     135     1246362 :                 struct btrfs_lru_cache_entry *lru_entry;
     136             : 
     137     1246362 :                 lru_entry = list_first_entry(&cache->lru_list,
     138             :                                              struct btrfs_lru_cache_entry,
     139             :                                              lru_list);
     140     1246362 :                 btrfs_lru_cache_remove(cache, lru_entry);
     141             :         }
     142             : 
     143     1752377 :         list_add_tail(&new_entry->lru_list, &cache->lru_list);
     144     1752365 :         cache->size++;
     145             : 
     146     1752365 :         return 0;
     147             : }
     148             : 
     149             : /*
     150             :  * Empty a cache.
     151             :  *
     152             :  * @cache:     The cache to empty.
     153             :  *
     154             :  * Removes all entries from the cache.
     155             :  */
     156        2386 : void btrfs_lru_cache_clear(struct btrfs_lru_cache *cache)
     157             : {
     158        2386 :         struct btrfs_lru_cache_entry *entry;
     159        2386 :         struct btrfs_lru_cache_entry *tmp;
     160             : 
     161      101048 :         list_for_each_entry_safe(entry, tmp, &cache->lru_list, lru_list)
     162       98662 :                 btrfs_lru_cache_remove(cache, entry);
     163             : 
     164        2386 :         ASSERT(cache->size == 0);
     165        2386 :         ASSERT(mtree_empty(&cache->entries));
     166        2386 : }