| blob | 145ab695d7c5b451445caf34d77e017b8aaf008b |
1 mbcache2: reimplement mbcache
3 From: Jan Kara <jack@suse.cz>
5 Original mbcache was designed to have more features than what ext?
6 filesystems ended up using. It supported entry being in more hashes, it
7 had a home-grown rwlocking of each entry, and one cache could cache
8 entries from multiple filesystems. This genericity also resulted in more
9 complex locking, larger cache entries, and generally more code
10 complexity.
12 This is reimplementation of the mbcache functionality to exactly fit the
13 purpose ext? filesystems use it for. Cache entries are now considerably
14 smaller (7 instead of 13 longs), the code is considerably smaller as
15 well (432 vs 913 lines of code), and IMO also simpler. The new code is
16 also much more lightweight.
18 I have measured the speed using artificial xattr-bench benchmark, which
19 spawns P processes, each process sets xattr for F different files, and
20 the value of xattr is randomly chosen from a pool of V values. Averages
21 of runtimes for 5 runs for various combinations of parameters are below.
22 The first value in each cell is old mbache, the second value is the new
23 mbcache.
25 V=10
26 F\P 1 2 4 8 16 32 64
27 10 0.158,0.157 0.208,0.196 0.500,0.277 0.798,0.400 3.258,0.584 13.807,1.047 61.339,2.803
28 100 0.172,0.167 0.279,0.222 0.520,0.275 0.825,0.341 2.981,0.505 12.022,1.202 44.641,2.943
29 1000 0.185,0.174 0.297,0.239 0.445,0.283 0.767,0.340 2.329,0.480 6.342,1.198 16.440,3.888
31 V=100
32 F\P 1 2 4 8 16 32 64
33 10 0.162,0.153 0.200,0.186 0.362,0.257 0.671,0.496 1.433,0.943 3.801,1.345 7.938,2.501
34 100 0.153,0.160 0.221,0.199 0.404,0.264 0.945,0.379 1.556,0.485 3.761,1.156 7.901,2.484
35 1000 0.215,0.191 0.303,0.246 0.471,0.288 0.960,0.347 1.647,0.479 3.916,1.176 8.058,3.160
37 V=1000
38 F\P 1 2 4 8 16 32 64
39 10 0.151,0.129 0.210,0.163 0.326,0.245 0.685,0.521 1.284,0.859 3.087,2.251 6.451,4.801
40 100 0.154,0.153 0.211,0.191 0.276,0.282 0.687,0.506 1.202,0.877 3.259,1.954 8.738,2.887
41 1000 0.145,0.179 0.202,0.222 0.449,0.319 0.899,0.333 1.577,0.524 4.221,1.240 9.782,3.579
43 V=10000
44 F\P 1 2 4 8 16 32 64
45 10 0.161,0.154 0.198,0.190 0.296,0.256 0.662,0.480 1.192,0.818 2.989,2.200 6.362,4.746
46 100 0.176,0.174 0.236,0.203 0.326,0.255 0.696,0.511 1.183,0.855 4.205,3.444 19.510,17.760
47 1000 0.199,0.183 0.240,0.227 1.159,1.014 2.286,2.154 6.023,6.039 10.933,--- 36.620,---
49 V=100000
50 F\P 1 2 4 8 16 32 64
51 10 0.171,0.162 0.204,0.198 0.285,0.230 0.692,0.500 1.225,0.881 2.990,2.243 6.379,4.771
52 100 0.151,0.171 0.220,0.210 0.295,0.255 0.720,0.518 1.226,0.844 3.423,2.831 19.234,17.544
53 1000 0.192,0.189 0.249,0.225 1.162,1.043 2.257,2.093 5.853,4.997 10.399,--- 32.198,---
55 We see that the new code is faster in pretty much all the cases and
56 starting from 4 processes there are significant gains with the new code
57 resulting in upto 20-times shorter runtimes. Also for large numbers of
58 cached entries all values for the old code could not be measured as the
59 kernel started hitting softlockups and died before the test completed.
61 Signed-off-by: Jan Kara <jack@suse.cz>
62 Signed-off-by: Theodore Ts'o <tytso@mit.edu>
63 ---
64 fs/Makefile | 2 +-
65 fs/mbcache2.c | 388 +++++++++++++++++++++++++++++++++++++++++++++++
66 include/linux/mbcache2.h | 54 +++++++
67 3 files changed, 443 insertions(+), 1 deletion(-)
68 create mode 100644 fs/mbcache2.c
69 create mode 100644 include/linux/mbcache2.h
71 diff --git a/fs/Makefile b/fs/Makefile
72 index 79f522575cba..15b3d6c4e46a 100644
73 --- a/fs/Makefile
74 +++ b/fs/Makefile
75 @@ -41,7 +41,7 @@ obj-$(CONFIG_COMPAT_BINFMT_ELF) += compat_binfmt_elf.o
76 obj-$(CONFIG_BINFMT_ELF_FDPIC) += binfmt_elf_fdpic.o
77 obj-$(CONFIG_BINFMT_FLAT) += binfmt_flat.o
79 -obj-$(CONFIG_FS_MBCACHE) += mbcache.o
80 +obj-$(CONFIG_FS_MBCACHE) += mbcache.o mbcache2.o
81 obj-$(CONFIG_FS_POSIX_ACL) += posix_acl.o
82 obj-$(CONFIG_NFS_COMMON) += nfs_common/
83 obj-$(CONFIG_COREDUMP) += coredump.o
84 diff --git a/fs/mbcache2.c b/fs/mbcache2.c
85 new file mode 100644
86 index 000000000000..4ccf0752c6d1
87 --- /dev/null
88 +++ b/fs/mbcache2.c
89 @@ -0,0 +1,388 @@
90 +#include <linux/spinlock.h>
91 +#include <linux/slab.h>
92 +#include <linux/list.h>
93 +#include <linux/list_bl.h>
94 +#include <linux/module.h>
95 +#include <linux/sched.h>
96 +#include <linux/mbcache2.h>
97 +
98 +/*
99 + * Mbcache is a simple key-value store. Keys need not be unique, however
100 + * key-value pairs are expected to be unique (we use this in
101 + * mb2_cache_entry_delete_block()).
102 + *
103 + * We provide functions for creation and removal of entries, search by key,
104 + * and a special "delete entry with given key-value pair" operation. Fixed
105 + * size hash table is used for fast key lookups.
106 + */
107 +
108 +struct mb2_cache {
109 + /* Hash table of entries */
110 + struct hlist_bl_head *c_hash;
111 + /* log2 of hash table size */
112 + int c_bucket_bits;
113 + /* Protects c_lru_list, c_entry_count */
114 + spinlock_t c_lru_list_lock;
115 + struct list_head c_lru_list;
116 + /* Number of entries in cache */
117 + unsigned long c_entry_count;
118 + struct shrinker c_shrink;
119 +};
120 +
121 +static struct kmem_cache *mb2_entry_cache;
122 +
123 +/*
124 + * mb2_cache_entry_create - create entry in cache
125 + * @cache - cache where the entry should be created
126 + * @mask - gfp mask with which the entry should be allocated
127 + * @key - key of the entry
128 + * @block - block that contains data
129 + *
130 + * Creates entry in @cache with key @key and records that data is stored in
131 + * block @block. The function returns -EBUSY if entry with the same key
132 + * and for the same block already exists in cache. Otherwise reference to
133 + * the created entry is returned.
134 + */
135 +struct mb2_cache_entry *mb2_cache_entry_create(struct mb2_cache *cache,
136 + gfp_t mask,
137 + unsigned int key,
138 + sector_t block)
139 +{
140 + struct mb2_cache_entry *entry, *dup;
141 + struct hlist_bl_node *dup_node;
142 + struct hlist_bl_head *head;
143 +
144 + entry = kmem_cache_alloc(mb2_entry_cache, mask);
145 + if (!entry)
146 + return ERR_PTR(-ENOMEM);
147 +
148 + INIT_LIST_HEAD(&entry->e_lru_list);
149 + /* One ref for hash, one ref returned */
150 + atomic_set(&entry->e_refcnt, 2);
151 + entry->e_key = key;
152 + entry->e_block = block;
153 + head = &cache->c_hash[hash_32(key, cache->c_bucket_bits)];
154 + entry->e_hash_list_head = head;
155 + hlist_bl_lock(head);
156 + hlist_bl_for_each_entry(dup, dup_node, head, e_hash_list) {
157 + if (dup->e_key == key && dup->e_block == block) {
158 + hlist_bl_unlock(head);
159 + kmem_cache_free(mb2_entry_cache, entry);
160 + return ERR_PTR(-EBUSY);
161 + }
162 + }
163 + hlist_bl_add_head(&entry->e_hash_list, head);
164 + hlist_bl_unlock(head);
165 +
166 + spin_lock(&cache->c_lru_list_lock);
167 + list_add_tail(&entry->e_lru_list, &cache->c_lru_list);
168 + /* Grab ref for LRU list */
169 + atomic_inc(&entry->e_refcnt);
170 + cache->c_entry_count++;
171 + spin_unlock(&cache->c_lru_list_lock);
172 +
173 + return entry;
174 +}
175 +EXPORT_SYMBOL(mb2_cache_entry_create);
176 +
177 +void __mb2_cache_entry_free(struct mb2_cache_entry *entry)
178 +{
179 + kmem_cache_free(mb2_entry_cache, entry);
180 +}
181 +EXPORT_SYMBOL(__mb2_cache_entry_free);
182 +
183 +/*
184 + * mb2_cache_entry_delete - delete entry from cache
185 + * @cache - cache where the entry is
186 + * @entry - entry to delete
187 + *
188 + * Delete entry from cache. The entry is unhashed and deleted from the lru list
189 + * so it cannot be found. We also drop the reference to @entry caller gave us.
190 + * However entry need not be freed if there's someone else still holding a
191 + * reference to it. Freeing happens when the last reference is dropped.
192 + */
193 +void mb2_cache_entry_delete(struct mb2_cache *cache,
194 + struct mb2_cache_entry *entry)
195 +{
196 + struct hlist_bl_head *head = entry->e_hash_list_head;
197 +
198 + hlist_bl_lock(head);
199 + if (!hlist_bl_unhashed(&entry->e_hash_list)) {
200 + hlist_bl_del_init(&entry->e_hash_list);
201 + atomic_dec(&entry->e_refcnt);
202 + }
203 + hlist_bl_unlock(head);
204 + spin_lock(&cache->c_lru_list_lock);
205 + if (!list_empty(&entry->e_lru_list)) {
206 + list_del_init(&entry->e_lru_list);
207 + cache->c_entry_count--;
208 + atomic_dec(&entry->e_refcnt);
209 + }
210 + spin_unlock(&cache->c_lru_list_lock);
211 + mb2_cache_entry_put(cache, entry);
212 +}
213 +EXPORT_SYMBOL(mb2_cache_entry_delete);
214 +
215 +static struct mb2_cache_entry *__entry_find(struct mb2_cache *cache,
216 + struct mb2_cache_entry *entry,
217 + unsigned int key)
218 +{
219 + struct mb2_cache_entry *old_entry = entry;
220 + struct hlist_bl_node *node;
221 + struct hlist_bl_head *head;
222 +
223 + if (entry)
224 + head = entry->e_hash_list_head;
225 + else
226 + head = &cache->c_hash[hash_32(key, cache->c_bucket_bits)];
227 + hlist_bl_lock(head);
228 + if (entry && !hlist_bl_unhashed(&entry->e_hash_list))
229 + node = entry->e_hash_list.next;
230 + else
231 + node = hlist_bl_first(head);
232 + while (node) {
233 + entry = hlist_bl_entry(node, struct mb2_cache_entry,
234 + e_hash_list);
235 + if (entry->e_key == key) {
236 + atomic_inc(&entry->e_refcnt);
237 + goto out;
238 + }
239 + node = node->next;
240 + }
241 + entry = NULL;
242 +out:
243 + hlist_bl_unlock(head);
244 + if (old_entry)
245 + mb2_cache_entry_put(cache, old_entry);
246 +
247 + return entry;
248 +}
249 +
250 +/*
251 + * mb2_cache_entry_find_first - find the first entry in cache with given key
252 + * @cache: cache where we should search
253 + * @key: key to look for
254 + *
255 + * Search in @cache for entry with key @key. Grabs reference to the first
256 + * entry found and returns the entry.
257 + */
258 +struct mb2_cache_entry *mb2_cache_entry_find_first(struct mb2_cache *cache,
259 + unsigned int key)
260 +{
261 + return __entry_find(cache, NULL, key);
262 +}
263 +EXPORT_SYMBOL(mb2_cache_entry_find_first);
264 +
265 +/*
266 + * mb2_cache_entry_find_next - find next entry in cache with the same
267 + * @cache: cache where we should search
268 + * @entry: entry to start search from
269 + *
270 + * Finds next entry in the hash chain which has the same key as @entry.
271 + * If @entry is unhashed (which can happen when deletion of entry races
272 + * with the search), finds the first entry in the hash chain. The function
273 + * drops reference to @entry and returns with a reference to the found entry.
274 + */
275 +struct mb2_cache_entry *mb2_cache_entry_find_next(struct mb2_cache *cache,
276 + struct mb2_cache_entry *entry)
277 +{
278 + return __entry_find(cache, entry, entry->e_key);
279 +}
280 +EXPORT_SYMBOL(mb2_cache_entry_find_next);
281 +
282 +/* mb2_cache_entry_delete_block - remove information about block from cache
283 + * @cache - cache we work with
284 + * @key - key of the entry to remove
285 + * @block - block containing data for @key
286 + *
287 + * Remove entry from cache @cache with key @key with data stored in @block.
288 + */
289 +void mb2_cache_entry_delete_block(struct mb2_cache *cache, unsigned int key,
290 + sector_t block)
291 +{
292 + struct hlist_bl_node *node;
293 + struct hlist_bl_head *head;
294 + struct mb2_cache_entry *entry;
295 +
296 + head = &cache->c_hash[hash_32(key, cache->c_bucket_bits)];
297 + hlist_bl_lock(head);
298 + hlist_bl_for_each_entry(entry, node, head, e_hash_list) {
299 + if (entry->e_key == key && entry->e_block == block) {
300 + /* We keep hash list reference to keep entry alive */
301 + hlist_bl_del_init(&entry->e_hash_list);
302 + hlist_bl_unlock(head);
303 + spin_lock(&cache->c_lru_list_lock);
304 + if (!list_empty(&entry->e_lru_list)) {
305 + list_del_init(&entry->e_lru_list);
306 + cache->c_entry_count--;
307 + atomic_dec(&entry->e_refcnt);
308 + }
309 + spin_unlock(&cache->c_lru_list_lock);
310 + mb2_cache_entry_put(cache, entry);
311 + return;
312 + }
313 + }
314 + hlist_bl_unlock(head);
315 +}
316 +EXPORT_SYMBOL(mb2_cache_entry_delete_block);
317 +
318 +/* mb2_cache_entry_touch - cache entry got used
319 + * @cache - cache the entry belongs to
320 + * @entry - entry that got used
321 + *
322 + * Move entry in lru list to reflect the fact that it was used.
323 + */
324 +void mb2_cache_entry_touch(struct mb2_cache *cache,
325 + struct mb2_cache_entry *entry)
326 +{
327 + spin_lock(&cache->c_lru_list_lock);
328 + if (!list_empty(&entry->e_lru_list))
329 + list_move_tail(&cache->c_lru_list, &entry->e_lru_list);
330 + spin_unlock(&cache->c_lru_list_lock);
331 +}
332 +EXPORT_SYMBOL(mb2_cache_entry_touch);
333 +
334 +static unsigned long mb2_cache_count(struct shrinker *shrink,
335 + struct shrink_control *sc)
336 +{
337 + struct mb2_cache *cache = container_of(shrink, struct mb2_cache,
338 + c_shrink);
339 +
340 + return cache->c_entry_count;
341 +}
342 +
343 +/* Shrink number of entries in cache */
344 +static unsigned long mb2_cache_scan(struct shrinker *shrink,
345 + struct shrink_control *sc)
346 +{
347 + int nr_to_scan = sc->nr_to_scan;
348 + struct mb2_cache *cache = container_of(shrink, struct mb2_cache,
349 + c_shrink);
350 + struct mb2_cache_entry *entry;
351 + struct hlist_bl_head *head;
352 + unsigned int shrunk = 0;
353 +
354 + spin_lock(&cache->c_lru_list_lock);
355 + while (nr_to_scan-- && !list_empty(&cache->c_lru_list)) {
356 + entry = list_first_entry(&cache->c_lru_list,
357 + struct mb2_cache_entry, e_lru_list);
358 + list_del_init(&entry->e_lru_list);
359 + cache->c_entry_count--;
360 + /*
361 + * We keep LRU list reference so that entry doesn't go away
362 + * from under us.
363 + */
364 + spin_unlock(&cache->c_lru_list_lock);
365 + head = entry->e_hash_list_head;
366 + hlist_bl_lock(head);
367 + if (!hlist_bl_unhashed(&entry->e_hash_list)) {
368 + hlist_bl_del_init(&entry->e_hash_list);
369 + atomic_dec(&entry->e_refcnt);
370 + }
371 + hlist_bl_unlock(head);
372 + if (mb2_cache_entry_put(cache, entry))
373 + shrunk++;
374 + cond_resched();
375 + spin_lock(&cache->c_lru_list_lock);
376 + }
377 + spin_unlock(&cache->c_lru_list_lock);
378 +
379 + return shrunk;
380 +}
381 +
382 +/*
383 + * mb2_cache_create - create cache
384 + * @bucket_bits: log2 of the hash table size
385 + *
386 + * Create cache for keys with 2^bucket_bits hash entries.
387 + */
388 +struct mb2_cache *mb2_cache_create(int bucket_bits)
389 +{
390 + struct mb2_cache *cache;
391 + int bucket_count = 1 << bucket_bits;
392 + int i;
393 +
394 + if (!try_module_get(THIS_MODULE))
395 + return NULL;
396 +
397 + cache = kzalloc(sizeof(struct mb2_cache), GFP_KERNEL);
398 + if (!cache)
399 + goto err_out;
400 + cache->c_bucket_bits = bucket_bits;
401 + INIT_LIST_HEAD(&cache->c_lru_list);
402 + spin_lock_init(&cache->c_lru_list_lock);
403 + cache->c_hash = kmalloc(bucket_count * sizeof(struct hlist_bl_head),
404 + GFP_KERNEL);
405 + if (!cache->c_hash) {
406 + kfree(cache);
407 + goto err_out;
408 + }
409 + for (i = 0; i < bucket_count; i++)
410 + INIT_HLIST_BL_HEAD(&cache->c_hash[i]);
411 +
412 + cache->c_shrink.count_objects = mb2_cache_count;
413 + cache->c_shrink.scan_objects = mb2_cache_scan;
414 + cache->c_shrink.seeks = DEFAULT_SEEKS;
415 + register_shrinker(&cache->c_shrink);
416 +
417 + return cache;
418 +
419 +err_out:
420 + module_put(THIS_MODULE);
421 + return NULL;
422 +}
423 +EXPORT_SYMBOL(mb2_cache_create);
424 +
425 +/*
426 + * mb2_cache_destroy - destroy cache
427 + * @cache: the cache to destroy
428 + *
429 + * Free all entries in cache and cache itself. Caller must make sure nobody
430 + * (except shrinker) can reach @cache when calling this.
431 + */
432 +void mb2_cache_destroy(struct mb2_cache *cache)
433 +{
434 + struct mb2_cache_entry *entry, *next;
435 +
436 + unregister_shrinker(&cache->c_shrink);
437 +
438 + /*
439 + * We don't bother with any locking. Cache must not be used at this
440 + * point.
441 + */
442 + list_for_each_entry_safe(entry, next, &cache->c_lru_list, e_lru_list) {
443 + if (!hlist_bl_unhashed(&entry->e_hash_list)) {
444 + hlist_bl_del_init(&entry->e_hash_list);
445 + atomic_dec(&entry->e_refcnt);
446 + } else
447 + WARN_ON(1);
448 + list_del(&entry->e_lru_list);
449 + WARN_ON(atomic_read(&entry->e_refcnt) != 1);
450 + mb2_cache_entry_put(cache, entry);
451 + }
452 + kfree(cache->c_hash);
453 + kfree(cache);
454 + module_put(THIS_MODULE);
455 +}
456 +EXPORT_SYMBOL(mb2_cache_destroy);
457 +
458 +static int __init mb2cache_init(void)
459 +{
460 + mb2_entry_cache = kmem_cache_create("mbcache",
461 + sizeof(struct mb2_cache_entry), 0,
462 + SLAB_RECLAIM_ACCOUNT|SLAB_MEM_SPREAD, NULL);
463 + BUG_ON(!mb2_entry_cache);
464 + return 0;
465 +}
466 +
467 +static void __exit mb2cache_exit(void)
468 +{
469 + kmem_cache_destroy(mb2_entry_cache);
470 +}
471 +
472 +module_init(mb2cache_init)
473 +module_exit(mb2cache_exit)
474 +
475 +MODULE_AUTHOR("Jan Kara <jack@suse.cz>");
476 +MODULE_DESCRIPTION("Meta block cache (for extended attributes)");
477 +MODULE_LICENSE("GPL");
478 diff --git a/include/linux/mbcache2.h b/include/linux/mbcache2.h
479 new file mode 100644
480 index 000000000000..2a58c51c3a0a
481 --- /dev/null
482 +++ b/include/linux/mbcache2.h
483 @@ -0,0 +1,54 @@
484 +#ifndef _LINUX_MB2CACHE_H
485 +#define _LINUX_MB2CACHE_H
486 +
487 +#include <linux/hash.h>
488 +#include <linux/list_bl.h>
489 +#include <linux/list.h>
490 +#include <linux/atomic.h>
491 +#include <linux/fs.h>
492 +
493 +struct mb2_cache;
494 +
495 +struct mb2_cache_entry {
496 + /* LRU list - protected by cache->c_lru_list_lock */
497 + struct list_head e_lru_list;
498 + /* Hash table list - protected by bitlock in e_hash_list_head */
499 + struct hlist_bl_node e_hash_list;
500 + atomic_t e_refcnt;
501 + /* Key in hash - stable during lifetime of the entry */
502 + unsigned int e_key;
503 + /* Block number of hashed block - stable during lifetime of the entry */
504 + sector_t e_block;
505 + /* Head of hash list (for list bit lock) - stable */
506 + struct hlist_bl_head *e_hash_list_head;
507 +};
508 +
509 +struct mb2_cache *mb2_cache_create(int bucket_bits);
510 +void mb2_cache_destroy(struct mb2_cache *cache);
511 +
512 +struct mb2_cache_entry *mb2_cache_entry_create(struct mb2_cache *cache,
513 + gfp_t mask,
514 + unsigned int key,
515 + sector_t block);
516 +void mb2_cache_entry_delete(struct mb2_cache *cache,
517 + struct mb2_cache_entry *entry);
518 +void __mb2_cache_entry_free(struct mb2_cache_entry *entry);
519 +static inline int mb2_cache_entry_put(struct mb2_cache *cache,
520 + struct mb2_cache_entry *entry)
521 +{
522 + if (!atomic_dec_and_test(&entry->e_refcnt))
523 + return 0;
524 + __mb2_cache_entry_free(entry);
525 + return 1;
526 +}
527 +
528 +void mb2_cache_entry_delete_block(struct mb2_cache *cache, unsigned int key,
529 + sector_t block);
530 +struct mb2_cache_entry *mb2_cache_entry_find_first(struct mb2_cache *cache,
531 + unsigned int key);
532 +struct mb2_cache_entry *mb2_cache_entry_find_next(struct mb2_cache *cache,
533 + struct mb2_cache_entry *entry);
534 +void mb2_cache_entry_touch(struct mb2_cache *cache,
535 + struct mb2_cache_entry *entry);
536 +
537 +#endif /* _LINUX_MB2CACHE_H */
538 --
539 2.1.4