1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
// SPDX-License-Identifier: GPL-2.0
#include <linux/mm.h>
#include "lru_cache.h"
#include "messages.h"
/*
* Initialize a cache object.
*
* @cache: The cache.
* @max_size: Maximum size (number of entries) for the cache.
* Use 0 for unlimited size, it's the user's responsability to
* trim the cache in that case.
*/
void btrfs_lru_cache_init(struct btrfs_lru_cache *cache, unsigned int max_size)
{
INIT_LIST_HEAD(&cache->lru_list);
mt_init(&cache->entries);
cache->size = 0;
cache->max_size = max_size;
}
static struct btrfs_lru_cache_entry *match_entry(struct list_head *head, u64 key,
u64 gen)
{
struct btrfs_lru_cache_entry *entry;
list_for_each_entry(entry, head, list) {
if (entry->key == key && entry->gen == gen)
return entry;
}
return NULL;
}
/*
* Lookup for an entry in the cache.
*
* @cache: The cache.
* @key: The key of the entry we are looking for.
* @gen: Generation associated to the key.
*
* Returns the entry associated with the key or NULL if none found.
*/
struct btrfs_lru_cache_entry *btrfs_lru_cache_lookup(struct btrfs_lru_cache *cache,
u64 key, u64 gen)
{
struct list_head *head;
struct btrfs_lru_cache_entry *entry;
head = mtree_load(&cache->entries, key);
if (!head)
return NULL;
entry = match_entry(head, key, gen);
if (entry)
list_move_tail(&entry->lru_list, &cache->lru_list);
return entry;
}
/*
* Remove an entry from the cache.
*
* @cache: The cache to remove from.
* @entry: The entry to remove from the cache.
*
* Note: this also frees the memory used by the entry.
*/
void btrfs_lru_cache_remove(struct btrfs_lru_cache *cache,
struct btrfs_lru_cache_entry *entry)
{
struct list_head *prev = entry->list.prev;
ASSERT(cache->size > 0);
ASSERT(!mtree_empty(&cache->entries));
list_del(&entry->list);
list_del(&entry->lru_list);
if (list_empty(prev)) {
struct list_head *head;
/*
* If previous element in the list entry->list is now empty, it
* means it's a head entry not pointing to any cached entries,
* so remove it from the maple tree and free it.
*/
head = mtree_erase(&cache->entries, entry->key);
ASSERT(head == prev);
kfree(head);
}
kfree(entry);
cache->size--;
}
/*
* Store an entry in the cache.
*
* @cache: The cache.
* @entry: The entry to store.
*
* Returns 0 on success and < 0 on error.
*/
int btrfs_lru_cache_store(struct btrfs_lru_cache *cache,
struct btrfs_lru_cache_entry *new_entry,
gfp_t gfp)
{
const u64 key = new_entry->key;
struct list_head *head;
int ret;
head = kmalloc(sizeof(*head), gfp);
if (!head)
return -ENOMEM;
ret = mtree_insert(&cache->entries, key, head, gfp);
if (ret == 0) {
INIT_LIST_HEAD(head);
list_add_tail(&new_entry->list, head);
} else if (ret == -EEXIST) {
kfree(head);
head = mtree_load(&cache->entries, key);
ASSERT(head != NULL);
if (match_entry(head, key, new_entry->gen) != NULL)
return -EEXIST;
list_add_tail(&new_entry->list, head);
} else if (ret < 0) {
kfree(head);
return ret;
}
if (cache->max_size > 0 && cache->size == cache->max_size) {
struct btrfs_lru_cache_entry *lru_entry;
lru_entry = list_first_entry(&cache->lru_list,
struct btrfs_lru_cache_entry,
lru_list);
btrfs_lru_cache_remove(cache, lru_entry);
}
list_add_tail(&new_entry->lru_list, &cache->lru_list);
cache->size++;
return 0;
}
/*
* Empty a cache.
*
* @cache: The cache to empty.
*
* Removes all entries from the cache.
*/
void btrfs_lru_cache_clear(struct btrfs_lru_cache *cache)
{
struct btrfs_lru_cache_entry *entry;
struct btrfs_lru_cache_entry *tmp;
list_for_each_entry_safe(entry, tmp, &cache->lru_list, lru_list)
btrfs_lru_cache_remove(cache, entry);
ASSERT(cache->size == 0);
ASSERT(mtree_empty(&cache->entries));
}
|
