1 // SPDX-License-Identifier: GPL-2.0-only
2 #include <linux/spinlock.h>
3 #include <linux/slab.h>
4 #include <linux/list.h>
5 #include <linux/list_bl.h>
6 #include <linux/module.h>
7 #include <linux/sched.h>
8 #include <linux/workqueue.h>
9 #include <linux/mbcache.h>
12 * Mbcache is a simple key-value store. Keys need not be unique, however
13 * key-value pairs are expected to be unique (we use this fact in
14 * mb_cache_entry_delete_or_get()).
16 * Ext2 and ext4 use this cache for deduplication of extended attribute blocks.
17 * Ext4 also uses it for deduplication of xattr values stored in inodes.
18 * They use hash of data as a key and provide a value that may represent a
19 * block or inode number. That's why keys need not be unique (hash of different
20 * data may be the same). However user provided value always uniquely
21 * identifies a cache entry.
23 * We provide functions for creation and removal of entries, search by key,
24 * and a special "delete entry with given key-value pair" operation. Fixed
25 * size hash table is used for fast key lookups.
29 /* Hash table of entries */
30 struct hlist_bl_head
*c_hash
;
31 /* log2 of hash table size */
33 /* Maximum entries in cache to avoid degrading hash too much */
34 unsigned long c_max_entries
;
35 /* Protects c_list, c_entry_count */
36 spinlock_t c_list_lock
;
37 struct list_head c_list
;
38 /* Number of entries in cache */
39 unsigned long c_entry_count
;
40 struct shrinker c_shrink
;
41 /* Work for shrinking when the cache has too many entries */
42 struct work_struct c_shrink_work
;
45 static struct kmem_cache
*mb_entry_cache
;
47 static unsigned long mb_cache_shrink(struct mb_cache
*cache
,
48 unsigned long nr_to_scan
);
50 static inline struct hlist_bl_head
*mb_cache_entry_head(struct mb_cache
*cache
,
53 return &cache
->c_hash
[hash_32(key
, cache
->c_bucket_bits
)];
57 * Number of entries to reclaim synchronously when there are too many entries
60 #define SYNC_SHRINK_BATCH 64
63 * mb_cache_entry_create - create entry in cache
64 * @cache - cache where the entry should be created
65 * @mask - gfp mask with which the entry should be allocated
66 * @key - key of the entry
67 * @value - value of the entry
68 * @reusable - is the entry reusable by others?
70 * Creates entry in @cache with key @key and value @value. The function returns
71 * -EBUSY if entry with the same key and value already exists in cache.
72 * Otherwise 0 is returned.
74 int mb_cache_entry_create(struct mb_cache
*cache
, gfp_t mask
, u32 key
,
75 u64 value
, bool reusable
)
77 struct mb_cache_entry
*entry
, *dup
;
78 struct hlist_bl_node
*dup_node
;
79 struct hlist_bl_head
*head
;
81 /* Schedule background reclaim if there are too many entries */
82 if (cache
->c_entry_count
>= cache
->c_max_entries
)
83 schedule_work(&cache
->c_shrink_work
);
84 /* Do some sync reclaim if background reclaim cannot keep up */
85 if (cache
->c_entry_count
>= 2*cache
->c_max_entries
)
86 mb_cache_shrink(cache
, SYNC_SHRINK_BATCH
);
88 entry
= kmem_cache_alloc(mb_entry_cache
, mask
);
92 INIT_LIST_HEAD(&entry
->e_list
);
93 /* Initial hash reference */
94 atomic_set(&entry
->e_refcnt
, 1);
96 entry
->e_value
= value
;
97 entry
->e_reusable
= reusable
;
98 entry
->e_referenced
= 0;
99 head
= mb_cache_entry_head(cache
, key
);
101 hlist_bl_for_each_entry(dup
, dup_node
, head
, e_hash_list
) {
102 if (dup
->e_key
== key
&& dup
->e_value
== value
) {
103 hlist_bl_unlock(head
);
104 kmem_cache_free(mb_entry_cache
, entry
);
108 hlist_bl_add_head(&entry
->e_hash_list
, head
);
110 * Add entry to LRU list before it can be found by
111 * mb_cache_entry_delete() to avoid races
113 spin_lock(&cache
->c_list_lock
);
114 list_add_tail(&entry
->e_list
, &cache
->c_list
);
115 cache
->c_entry_count
++;
116 spin_unlock(&cache
->c_list_lock
);
117 hlist_bl_unlock(head
);
121 EXPORT_SYMBOL(mb_cache_entry_create
);
123 void __mb_cache_entry_free(struct mb_cache
*cache
, struct mb_cache_entry
*entry
)
125 struct hlist_bl_head
*head
;
127 head
= mb_cache_entry_head(cache
, entry
->e_key
);
129 hlist_bl_del(&entry
->e_hash_list
);
130 hlist_bl_unlock(head
);
131 kmem_cache_free(mb_entry_cache
, entry
);
133 EXPORT_SYMBOL(__mb_cache_entry_free
);
136 * mb_cache_entry_wait_unused - wait to be the last user of the entry
138 * @entry - entry to work on
140 * Wait to be the last user of the entry.
142 void mb_cache_entry_wait_unused(struct mb_cache_entry
*entry
)
144 wait_var_event(&entry
->e_refcnt
, atomic_read(&entry
->e_refcnt
) <= 2);
146 EXPORT_SYMBOL(mb_cache_entry_wait_unused
);
148 static struct mb_cache_entry
*__entry_find(struct mb_cache
*cache
,
149 struct mb_cache_entry
*entry
,
152 struct mb_cache_entry
*old_entry
= entry
;
153 struct hlist_bl_node
*node
;
154 struct hlist_bl_head
*head
;
156 head
= mb_cache_entry_head(cache
, key
);
158 if (entry
&& !hlist_bl_unhashed(&entry
->e_hash_list
))
159 node
= entry
->e_hash_list
.next
;
161 node
= hlist_bl_first(head
);
163 entry
= hlist_bl_entry(node
, struct mb_cache_entry
,
165 if (entry
->e_key
== key
&& entry
->e_reusable
&&
166 atomic_inc_not_zero(&entry
->e_refcnt
))
172 hlist_bl_unlock(head
);
174 mb_cache_entry_put(cache
, old_entry
);
180 * mb_cache_entry_find_first - find the first reusable entry with the given key
181 * @cache: cache where we should search
182 * @key: key to look for
184 * Search in @cache for a reusable entry with key @key. Grabs reference to the
185 * first reusable entry found and returns the entry.
187 struct mb_cache_entry
*mb_cache_entry_find_first(struct mb_cache
*cache
,
190 return __entry_find(cache
, NULL
, key
);
192 EXPORT_SYMBOL(mb_cache_entry_find_first
);
195 * mb_cache_entry_find_next - find next reusable entry with the same key
196 * @cache: cache where we should search
197 * @entry: entry to start search from
199 * Finds next reusable entry in the hash chain which has the same key as @entry.
200 * If @entry is unhashed (which can happen when deletion of entry races with the
201 * search), finds the first reusable entry in the hash chain. The function drops
202 * reference to @entry and returns with a reference to the found entry.
204 struct mb_cache_entry
*mb_cache_entry_find_next(struct mb_cache
*cache
,
205 struct mb_cache_entry
*entry
)
207 return __entry_find(cache
, entry
, entry
->e_key
);
209 EXPORT_SYMBOL(mb_cache_entry_find_next
);
212 * mb_cache_entry_get - get a cache entry by value (and key)
213 * @cache - cache we work with
217 struct mb_cache_entry
*mb_cache_entry_get(struct mb_cache
*cache
, u32 key
,
220 struct hlist_bl_node
*node
;
221 struct hlist_bl_head
*head
;
222 struct mb_cache_entry
*entry
;
224 head
= mb_cache_entry_head(cache
, key
);
226 hlist_bl_for_each_entry(entry
, node
, head
, e_hash_list
) {
227 if (entry
->e_key
== key
&& entry
->e_value
== value
&&
228 atomic_inc_not_zero(&entry
->e_refcnt
))
233 hlist_bl_unlock(head
);
236 EXPORT_SYMBOL(mb_cache_entry_get
);
238 /* mb_cache_entry_delete_or_get - remove a cache entry if it has no users
239 * @cache - cache we work with
243 * Remove entry from cache @cache with key @key and value @value. The removal
244 * happens only if the entry is unused. The function returns NULL in case the
245 * entry was successfully removed or there's no entry in cache. Otherwise the
246 * function grabs reference of the entry that we failed to delete because it
247 * still has users and return it.
249 struct mb_cache_entry
*mb_cache_entry_delete_or_get(struct mb_cache
*cache
,
252 struct mb_cache_entry
*entry
;
254 entry
= mb_cache_entry_get(cache
, key
, value
);
259 * Drop the ref we got from mb_cache_entry_get() and the initial hash
260 * ref if we are the last user
262 if (atomic_cmpxchg(&entry
->e_refcnt
, 2, 0) != 2)
265 spin_lock(&cache
->c_list_lock
);
266 if (!list_empty(&entry
->e_list
))
267 list_del_init(&entry
->e_list
);
268 cache
->c_entry_count
--;
269 spin_unlock(&cache
->c_list_lock
);
270 __mb_cache_entry_free(cache
, entry
);
273 EXPORT_SYMBOL(mb_cache_entry_delete_or_get
);
275 /* mb_cache_entry_touch - cache entry got used
276 * @cache - cache the entry belongs to
277 * @entry - entry that got used
279 * Marks entry as used to give hit higher chances of surviving in cache.
281 void mb_cache_entry_touch(struct mb_cache
*cache
,
282 struct mb_cache_entry
*entry
)
284 entry
->e_referenced
= 1;
286 EXPORT_SYMBOL(mb_cache_entry_touch
);
288 static unsigned long mb_cache_count(struct shrinker
*shrink
,
289 struct shrink_control
*sc
)
291 struct mb_cache
*cache
= container_of(shrink
, struct mb_cache
,
294 return cache
->c_entry_count
;
297 /* Shrink number of entries in cache */
298 static unsigned long mb_cache_shrink(struct mb_cache
*cache
,
299 unsigned long nr_to_scan
)
301 struct mb_cache_entry
*entry
;
302 unsigned long shrunk
= 0;
304 spin_lock(&cache
->c_list_lock
);
305 while (nr_to_scan
-- && !list_empty(&cache
->c_list
)) {
306 entry
= list_first_entry(&cache
->c_list
,
307 struct mb_cache_entry
, e_list
);
308 /* Drop initial hash reference if there is no user */
309 if (entry
->e_referenced
||
310 atomic_cmpxchg(&entry
->e_refcnt
, 1, 0) != 1) {
311 entry
->e_referenced
= 0;
312 list_move_tail(&entry
->e_list
, &cache
->c_list
);
315 list_del_init(&entry
->e_list
);
316 cache
->c_entry_count
--;
317 spin_unlock(&cache
->c_list_lock
);
318 __mb_cache_entry_free(cache
, entry
);
321 spin_lock(&cache
->c_list_lock
);
323 spin_unlock(&cache
->c_list_lock
);
328 static unsigned long mb_cache_scan(struct shrinker
*shrink
,
329 struct shrink_control
*sc
)
331 struct mb_cache
*cache
= container_of(shrink
, struct mb_cache
,
333 return mb_cache_shrink(cache
, sc
->nr_to_scan
);
336 /* We shrink 1/X of the cache when we have too many entries in it */
337 #define SHRINK_DIVISOR 16
339 static void mb_cache_shrink_worker(struct work_struct
*work
)
341 struct mb_cache
*cache
= container_of(work
, struct mb_cache
,
343 mb_cache_shrink(cache
, cache
->c_max_entries
/ SHRINK_DIVISOR
);
347 * mb_cache_create - create cache
348 * @bucket_bits: log2 of the hash table size
350 * Create cache for keys with 2^bucket_bits hash entries.
352 struct mb_cache
*mb_cache_create(int bucket_bits
)
354 struct mb_cache
*cache
;
355 unsigned long bucket_count
= 1UL << bucket_bits
;
358 cache
= kzalloc(sizeof(struct mb_cache
), GFP_KERNEL
);
361 cache
->c_bucket_bits
= bucket_bits
;
362 cache
->c_max_entries
= bucket_count
<< 4;
363 INIT_LIST_HEAD(&cache
->c_list
);
364 spin_lock_init(&cache
->c_list_lock
);
365 cache
->c_hash
= kmalloc_array(bucket_count
,
366 sizeof(struct hlist_bl_head
),
368 if (!cache
->c_hash
) {
372 for (i
= 0; i
< bucket_count
; i
++)
373 INIT_HLIST_BL_HEAD(&cache
->c_hash
[i
]);
375 cache
->c_shrink
.count_objects
= mb_cache_count
;
376 cache
->c_shrink
.scan_objects
= mb_cache_scan
;
377 cache
->c_shrink
.seeks
= DEFAULT_SEEKS
;
378 if (register_shrinker(&cache
->c_shrink
, "mbcache-shrinker")) {
379 kfree(cache
->c_hash
);
384 INIT_WORK(&cache
->c_shrink_work
, mb_cache_shrink_worker
);
391 EXPORT_SYMBOL(mb_cache_create
);
394 * mb_cache_destroy - destroy cache
395 * @cache: the cache to destroy
397 * Free all entries in cache and cache itself. Caller must make sure nobody
398 * (except shrinker) can reach @cache when calling this.
400 void mb_cache_destroy(struct mb_cache
*cache
)
402 struct mb_cache_entry
*entry
, *next
;
404 unregister_shrinker(&cache
->c_shrink
);
407 * We don't bother with any locking. Cache must not be used at this
410 list_for_each_entry_safe(entry
, next
, &cache
->c_list
, e_list
) {
411 list_del(&entry
->e_list
);
412 WARN_ON(atomic_read(&entry
->e_refcnt
) != 1);
413 mb_cache_entry_put(cache
, entry
);
415 kfree(cache
->c_hash
);
418 EXPORT_SYMBOL(mb_cache_destroy
);
420 static int __init
mbcache_init(void)
422 mb_entry_cache
= kmem_cache_create("mbcache",
423 sizeof(struct mb_cache_entry
), 0,
424 SLAB_RECLAIM_ACCOUNT
|SLAB_MEM_SPREAD
, NULL
);
430 static void __exit
mbcache_exit(void)
432 kmem_cache_destroy(mb_entry_cache
);
435 module_init(mbcache_init
)
436 module_exit(mbcache_exit
)
438 MODULE_AUTHOR("Jan Kara <jack@suse.cz>");
439 MODULE_DESCRIPTION("Meta block cache (for extended attributes)");
440 MODULE_LICENSE("GPL");