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