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(list: &cache->lru_list); |
18 | mt_init(mt: &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(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 | */ |
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: &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 | */ |
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(size: sizeof(*head), flags: 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 | */ |
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 | |