fs/btrfs/lru_cache.c

   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 void btrfs_lru_cache_init(struct btrfs_lru_cache *cache, unsigned int max_size)
  16 {
  17         INIT_LIST_HEAD(&cache->lru_list);
  18         mt_init(&cache->entries);
  19         cache->size = 0;
  20         cache->max_size = max_size;
  21 }
  22
  23 static struct btrfs_lru_cache_entry *match_entry(struct list_head *head, u64 key,
  24                                                  u64 gen)
  25 {
  26         struct btrfs_lru_cache_entry *entry;
  27
  28         list_for_each_entry(entry, head, list) {
  29                 if (entry->key == key && entry->gen == gen)
  30                         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 struct btrfs_lru_cache_entry *btrfs_lru_cache_lookup(struct btrfs_lru_cache *cache,
  46                                                      u64 key, u64 gen)
  47 {
  48         struct list_head *head;
  49         struct btrfs_lru_cache_entry *entry;
  50
  51         head = mtree_load(&cache->entries, key);
  52         if (!head)
  53                 return NULL;
  54
  55         entry = match_entry(head, key, gen);
  56         if (entry)
  57                 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 void btrfs_lru_cache_remove(struct btrfs_lru_cache *cache,
  71                             struct btrfs_lru_cache_entry *entry)
  72 {
  73         struct list_head *prev = entry->list.prev;
  74
  75         ASSERT(cache->size > 0);
  76         ASSERT(!mtree_empty(&cache->entries));
  77
  78         list_del(&entry->list);
  79         list_del(&entry->lru_list);
  80
  81         if (list_empty(prev)) {
  82                 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                 head = mtree_erase(&cache->entries, entry->key);
  90                 ASSERT(head == prev);
  91                 kfree(head);
  92         }
  93
  94         kfree(entry);
  95         cache->size--;
  96 }
  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 int btrfs_lru_cache_store(struct btrfs_lru_cache *cache,
 107                           struct btrfs_lru_cache_entry *new_entry,
 108                           gfp_t gfp)
 109 {
 110         const u64 key = new_entry->key;
 111         struct list_head *head;
 112         int ret;
 113
 114         head = kmalloc(sizeof(*head), gfp);
 115         if (!head)
 116                 return -ENOMEM;
 117
 118         ret = mtree_insert(&cache->entries, key, head, gfp);
 119         if (ret == 0) {
 120                 INIT_LIST_HEAD(head);
 121                 list_add_tail(&new_entry->list, head);
 122         } else if (ret == -EEXIST) {
 123                 kfree(head);
 124                 head = mtree_load(&cache->entries, key);
 125                 ASSERT(head != NULL);
 126                 if (match_entry(head, key, new_entry->gen) != NULL)
 127                         return -EEXIST;
 128                 list_add_tail(&new_entry->list, head);
 129         } else if (ret < 0) {
 130                 kfree(head);
 131                 return ret;
 132         }
 133
 134         if (cache->max_size > 0 && cache->size == cache->max_size) {
 135                 struct btrfs_lru_cache_entry *lru_entry;
 136
 137                 lru_entry = list_first_entry(&cache->lru_list,
 138                                              struct btrfs_lru_cache_entry,
 139                                              lru_list);
 140                 btrfs_lru_cache_remove(cache, lru_entry);
 141         }
 142
 143         list_add_tail(&new_entry->lru_list, &cache->lru_list);
 144         cache->size++;
 145
 146         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 void btrfs_lru_cache_clear(struct btrfs_lru_cache *cache)
 157 {
 158         struct btrfs_lru_cache_entry *entry;
 159         struct btrfs_lru_cache_entry *tmp;
 160
 161         list_for_each_entry_safe(entry, tmp, &cache->lru_list, lru_list)
 162                 btrfs_lru_cache_remove(cache, entry);
 163
 164         ASSERT(cache->size == 0);
 165         ASSERT(mtree_empty(&cache->entries));
 166 }