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 responsibility 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 } 167