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  */
btrfs_lru_cache_init(struct btrfs_lru_cache * cache,unsigned int max_size)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 
match_entry(struct list_head * head,u64 key,u64 gen)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  */
btrfs_lru_cache_lookup(struct btrfs_lru_cache * cache,u64 key,u64 gen)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  */
btrfs_lru_cache_remove(struct btrfs_lru_cache * cache,struct btrfs_lru_cache_entry * entry)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  */
btrfs_lru_cache_store(struct btrfs_lru_cache * cache,struct btrfs_lru_cache_entry * new_entry,gfp_t gfp)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  */
btrfs_lru_cache_clear(struct btrfs_lru_cache * cache)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