Commit | Line | Data |
---|---|---|
90b90d4a FM |
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. | |
3e49363b FM |
12 | * Use 0 for unlimited size, it's the user's responsability to |
13 | * trim the cache in that case. | |
90b90d4a FM |
14 | */ |
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 | ||
0da0c560 FM |
23 | static struct btrfs_lru_cache_entry *match_entry(struct list_head *head, u64 key, |
24 | u64 gen) | |
6273ee62 FM |
25 | { |
26 | struct btrfs_lru_cache_entry *entry; | |
27 | ||
28 | list_for_each_entry(entry, head, list) { | |
0da0c560 | 29 | if (entry->key == key && entry->gen == gen) |
6273ee62 FM |
30 | return entry; |
31 | } | |
32 | ||
33 | return NULL; | |
34 | } | |
35 | ||
90b90d4a FM |
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. | |
0da0c560 | 41 | * @gen: Generation associated to the key. |
90b90d4a FM |
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, | |
0da0c560 | 46 | u64 key, u64 gen) |
90b90d4a | 47 | { |
6273ee62 | 48 | struct list_head *head; |
90b90d4a FM |
49 | struct btrfs_lru_cache_entry *entry; |
50 | ||
6273ee62 FM |
51 | head = mtree_load(&cache->entries, key); |
52 | if (!head) | |
53 | return NULL; | |
54 | ||
0da0c560 | 55 | entry = match_entry(head, key, gen); |
90b90d4a FM |
56 | if (entry) |
57 | list_move_tail(&entry->lru_list, &cache->lru_list); | |
58 | ||
59 | return entry; | |
60 | } | |
61 | ||
d588adae FM |
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) | |
6273ee62 FM |
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 | ||
90b90d4a FM |
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 | { | |
6273ee62 FM |
110 | const u64 key = new_entry->key; |
111 | struct list_head *head; | |
90b90d4a FM |
112 | int ret; |
113 | ||
6273ee62 FM |
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); | |
0da0c560 | 126 | if (match_entry(head, key, new_entry->gen) != NULL) |
6273ee62 FM |
127 | return -EEXIST; |
128 | list_add_tail(&new_entry->list, head); | |
129 | } else if (ret < 0) { | |
130 | kfree(head); | |
131 | return ret; | |
132 | } | |
133 | ||
3e49363b | 134 | if (cache->max_size > 0 && cache->size == cache->max_size) { |
90b90d4a | 135 | struct btrfs_lru_cache_entry *lru_entry; |
90b90d4a FM |
136 | |
137 | lru_entry = list_first_entry(&cache->lru_list, | |
138 | struct btrfs_lru_cache_entry, | |
139 | lru_list); | |
d588adae | 140 | btrfs_lru_cache_remove(cache, lru_entry); |
90b90d4a FM |
141 | } |
142 | ||
90b90d4a FM |
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 | */ | |
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) | |
d588adae | 162 | btrfs_lru_cache_remove(cache, entry); |
90b90d4a | 163 | |
6273ee62 FM |
164 | ASSERT(cache->size == 0); |
165 | ASSERT(mtree_empty(&cache->entries)); | |
90b90d4a | 166 | } |