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 */
 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, 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 */
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}