167 lines · c
1// SPDX-License-Identifier: GPL-2.02 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 responsibility to13 * trim the cache in that case.14 */15void 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 23static 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 */45struct 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 */70void 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, it86 * 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 */106int 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 */156void 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}167