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(list: &cache->lru_list);
18 mt_init(mt: &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(mt: &cache->entries, index: key);
52 if (!head)
53 return NULL;
54
55 entry = match_entry(head, key, gen);
56 if (entry)
57 list_move_tail(list: &entry->lru_list, head: &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: &entry->list);
79 list_del(entry: &entry->lru_list);
80
81 if (list_empty(head: 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(mt: &cache->entries, index: entry->key);
90 ASSERT(head == prev);
91 kfree(objp: head);
92 }
93
94 kfree(objp: 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(mt: &cache->entries, index: key, entry: head, gfp);
119 if (ret == 0) {
120 INIT_LIST_HEAD(list: head);
121 list_add_tail(new: &new_entry->list, head);
122 } else if (ret == -EEXIST) {
123 kfree(objp: head);
124 head = mtree_load(mt: &cache->entries, index: key);
125 ASSERT(head != NULL);
126 if (match_entry(head, key, gen: new_entry->gen) != NULL)
127 return -EEXIST;
128 list_add_tail(new: &new_entry->list, head);
129 } else if (ret < 0) {
130 kfree(objp: 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, entry: lru_entry);
141 }
142
143 list_add_tail(new: &new_entry->lru_list, head: &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

source code of linux/fs/btrfs/lru_cache.c