Message ID | 1449683858-28936-2-git-send-email-jack@suse.cz |
---|---|
State | Superseded, archived |
Headers | show |
Jan, 2015-12-09 18:57 GMT+01:00 Jan Kara <jack@suse.cz>: > diff --git a/fs/mbcache2.c b/fs/mbcache2.c > new file mode 100644 > index 000000000000..4ccf0752c6d1 > --- /dev/null > +++ b/fs/mbcache2.c > @@ -0,0 +1,388 @@ > +#include <linux/spinlock.h> > +#include <linux/slab.h> > +#include <linux/list.h> > +#include <linux/list_bl.h> > +#include <linux/module.h> > +#include <linux/sched.h> > +#include <linux/mbcache2.h> > + > +/* > + * Mbcache is a simple key-value store. > + Keys need not be unique, however > + * key-value pairs are expected to be unique (we use this in > + * mb2_cache_entry_delete_block()). This comment is very confusing. Could you say what the keys and values are and what that kind of cache is used for so that people will have a chance of understanding what's going on? > + * We provide functions for creation and removal of entries, search by key, > + * and a special "delete entry with given key-value pair" operation. Fixed > + * size hash table is used for fast key lookups. > + */ Have you had a look at rhashtables? They would give us lockless lookups and they would automatically grow, at somewhat more complexity. > +struct mb2_cache { > + /* Hash table of entries */ > + struct hlist_bl_head *c_hash; > + /* log2 of hash table size */ > + int c_bucket_bits; > + /* Protects c_lru_list, c_entry_count */ > + spinlock_t c_lru_list_lock; > + struct list_head c_lru_list; > + /* Number of entries in cache */ > + unsigned long c_entry_count; > + struct shrinker c_shrink; > +}; > + > +static struct kmem_cache *mb2_entry_cache; > + > +/* > + * mb2_cache_entry_create - create entry in cache > + * @cache - cache where the entry should be created > + * @mask - gfp mask with which the entry should be allocated > + * @key - key of the entry > + * @block - block that contains data > + * > + * Creates entry in @cache with key @key and records that data is stored in > + * block @block. The function returns -EBUSY if entry with the same key > + * and for the same block already exists in cache. Otherwise reference to > + * the created entry is returned. > + */ > +struct mb2_cache_entry *mb2_cache_entry_create(struct mb2_cache *cache, > + gfp_t mask, > + unsigned int key, > + sector_t block) > +{ > + struct mb2_cache_entry *entry, *dup; > + struct hlist_bl_node *dup_node; > + struct hlist_bl_head *head; > + > + entry = kmem_cache_alloc(mb2_entry_cache, mask); > + if (!entry) > + return ERR_PTR(-ENOMEM); > + > + INIT_LIST_HEAD(&entry->e_lru_list); > + /* One ref for hash, one ref returned */ > + atomic_set(&entry->e_refcnt, 2); > + entry->e_key = key; > + entry->e_block = block; > + head = &cache->c_hash[hash_32(key, cache->c_bucket_bits)]; > + entry->e_hash_list_head = head; > + hlist_bl_lock(head); > + hlist_bl_for_each_entry(dup, dup_node, head, e_hash_list) { > + if (dup->e_key == key && dup->e_block == block) { > + hlist_bl_unlock(head); > + kmem_cache_free(mb2_entry_cache, entry); > + return ERR_PTR(-EBUSY); > + } > + } > + hlist_bl_add_head(&entry->e_hash_list, head); > + hlist_bl_unlock(head); > + > + spin_lock(&cache->c_lru_list_lock); > + list_add_tail(&entry->e_lru_list, &cache->c_lru_list); > + /* Grab ref for LRU list */ > + atomic_inc(&entry->e_refcnt); > + cache->c_entry_count++; > + spin_unlock(&cache->c_lru_list_lock); > + > + return entry; > +} > +EXPORT_SYMBOL(mb2_cache_entry_create); > + > +void __mb2_cache_entry_free(struct mb2_cache_entry *entry) > +{ > + kmem_cache_free(mb2_entry_cache, entry); > +} > +EXPORT_SYMBOL(__mb2_cache_entry_free); > + > +/* > + * mb2_cache_entry_delete - delete entry from cache > + * @cache - cache where the entry is > + * @entry - entry to delete > + * > + * Delete entry from cache. The entry is unhashed and deleted from the lru list > + * so it cannot be found. We also drop the reference to @entry caller gave us. > + * However entry need not be freed if there's someone else still holding a > + * reference to it. Freeing happens when the last reference is dropped. > + */ > +void mb2_cache_entry_delete(struct mb2_cache *cache, > + struct mb2_cache_entry *entry) This function should become static; there are no external users. > +{ > + struct hlist_bl_head *head = entry->e_hash_list_head; > + > + hlist_bl_lock(head); > + if (!hlist_bl_unhashed(&entry->e_hash_list)) { > + hlist_bl_del_init(&entry->e_hash_list); > + atomic_dec(&entry->e_refcnt); > + } > + hlist_bl_unlock(head); > + spin_lock(&cache->c_lru_list_lock); > + if (!list_empty(&entry->e_lru_list)) { > + list_del_init(&entry->e_lru_list); > + cache->c_entry_count--; > + atomic_dec(&entry->e_refcnt); > + } > + spin_unlock(&cache->c_lru_list_lock); > + mb2_cache_entry_put(cache, entry); > +} > +EXPORT_SYMBOL(mb2_cache_entry_delete); > + > +static struct mb2_cache_entry *__entry_find(struct mb2_cache *cache, > + struct mb2_cache_entry *entry, > + unsigned int key) > +{ > + struct mb2_cache_entry *old_entry = entry; > + struct hlist_bl_node *node; > + struct hlist_bl_head *head; > + > + if (entry) > + head = entry->e_hash_list_head; > + else > + head = &cache->c_hash[hash_32(key, cache->c_bucket_bits)]; > + hlist_bl_lock(head); > + if (entry && !hlist_bl_unhashed(&entry->e_hash_list)) > + node = entry->e_hash_list.next; > + else > + node = hlist_bl_first(head); > + while (node) { > + entry = hlist_bl_entry(node, struct mb2_cache_entry, > + e_hash_list); > + if (entry->e_key == key) { > + atomic_inc(&entry->e_refcnt); > + goto out; > + } > + node = node->next; > + } > + entry = NULL; > +out: > + hlist_bl_unlock(head); > + if (old_entry) > + mb2_cache_entry_put(cache, old_entry); > + > + return entry; > +} > + > +/* > + * mb2_cache_entry_find_first - find the first entry in cache with given key > + * @cache: cache where we should search > + * @key: key to look for > + * > + * Search in @cache for entry with key @key. Grabs reference to the first > + * entry found and returns the entry. > + */ > +struct mb2_cache_entry *mb2_cache_entry_find_first(struct mb2_cache *cache, > + unsigned int key) > +{ > + return __entry_find(cache, NULL, key); > +} > +EXPORT_SYMBOL(mb2_cache_entry_find_first); > + > +/* > + * mb2_cache_entry_find_next - find next entry in cache with the same > + * @cache: cache where we should search > + * @entry: entry to start search from > + * > + * Finds next entry in the hash chain which has the same key as @entry. > + * If @entry is unhashed (which can happen when deletion of entry races > + * with the search), finds the first entry in the hash chain. The function > + * drops reference to @entry and returns with a reference to the found entry. > + */ > +struct mb2_cache_entry *mb2_cache_entry_find_next(struct mb2_cache *cache, > + struct mb2_cache_entry *entry) > +{ > + return __entry_find(cache, entry, entry->e_key); > +} > +EXPORT_SYMBOL(mb2_cache_entry_find_next); > + > +/* mb2_cache_entry_delete_block - remove information about block from cache > + * @cache - cache we work with > + * @key - key of the entry to remove > + * @block - block containing data for @key > + * > + * Remove entry from cache @cache with key @key with data stored in @block. > + */ > +void mb2_cache_entry_delete_block(struct mb2_cache *cache, unsigned int key, > + sector_t block) > +{ > + struct hlist_bl_node *node; > + struct hlist_bl_head *head; > + struct mb2_cache_entry *entry; > + > + head = &cache->c_hash[hash_32(key, cache->c_bucket_bits)]; > + hlist_bl_lock(head); > + hlist_bl_for_each_entry(entry, node, head, e_hash_list) { > + if (entry->e_key == key && entry->e_block == block) { > + /* We keep hash list reference to keep entry alive */ > + hlist_bl_del_init(&entry->e_hash_list); > + hlist_bl_unlock(head); > + spin_lock(&cache->c_lru_list_lock); > + if (!list_empty(&entry->e_lru_list)) { > + list_del_init(&entry->e_lru_list); > + cache->c_entry_count--; > + atomic_dec(&entry->e_refcnt); > + } > + spin_unlock(&cache->c_lru_list_lock); > + mb2_cache_entry_put(cache, entry); > + return; > + } > + } > + hlist_bl_unlock(head); > +} > +EXPORT_SYMBOL(mb2_cache_entry_delete_block); > + > +/* mb2_cache_entry_touch - cache entry got used > + * @cache - cache the entry belongs to > + * @entry - entry that got used > + * > + * Move entry in lru list to reflect the fact that it was used. > + */ > +void mb2_cache_entry_touch(struct mb2_cache *cache, > + struct mb2_cache_entry *entry) > +{ > + spin_lock(&cache->c_lru_list_lock); > + if (!list_empty(&entry->e_lru_list)) > + list_move_tail(&cache->c_lru_list, &entry->e_lru_list); > + spin_unlock(&cache->c_lru_list_lock); > +} > +EXPORT_SYMBOL(mb2_cache_entry_touch); > + > +static unsigned long mb2_cache_count(struct shrinker *shrink, > + struct shrink_control *sc) > +{ > + struct mb2_cache *cache = container_of(shrink, struct mb2_cache, > + c_shrink); > + > + return cache->c_entry_count; > +} > + > +/* Shrink number of entries in cache */ > +static unsigned long mb2_cache_scan(struct shrinker *shrink, > + struct shrink_control *sc) > +{ > + int nr_to_scan = sc->nr_to_scan; > + struct mb2_cache *cache = container_of(shrink, struct mb2_cache, > + c_shrink); > + struct mb2_cache_entry *entry; > + struct hlist_bl_head *head; > + unsigned int shrunk = 0; > + > + spin_lock(&cache->c_lru_list_lock); > + while (nr_to_scan-- && !list_empty(&cache->c_lru_list)) { > + entry = list_first_entry(&cache->c_lru_list, > + struct mb2_cache_entry, e_lru_list); > + list_del_init(&entry->e_lru_list); > + cache->c_entry_count--; > + /* > + * We keep LRU list reference so that entry doesn't go away > + * from under us. > + */ > + spin_unlock(&cache->c_lru_list_lock); > + head = entry->e_hash_list_head; > + hlist_bl_lock(head); Instead of taking and dropping c_lru_list_lock in the loop, could we get away with a simple-to-implement hlist_bl_trylock() and cond_resched_lock()? > + if (!hlist_bl_unhashed(&entry->e_hash_list)) { > + hlist_bl_del_init(&entry->e_hash_list); > + atomic_dec(&entry->e_refcnt); > + } > + hlist_bl_unlock(head); > + if (mb2_cache_entry_put(cache, entry)) > + shrunk++; > + cond_resched(); > + spin_lock(&cache->c_lru_list_lock); > + } > + spin_unlock(&cache->c_lru_list_lock); > + > + return shrunk; > +} > + > +/* > + * mb2_cache_create - create cache > + * @bucket_bits: log2 of the hash table size > + * > + * Create cache for keys with 2^bucket_bits hash entries. > + */ > +struct mb2_cache *mb2_cache_create(int bucket_bits) > +{ > + struct mb2_cache *cache; > + int bucket_count = 1 << bucket_bits; > + int i; > + > + if (!try_module_get(THIS_MODULE)) > + return NULL; > + > + cache = kzalloc(sizeof(struct mb2_cache), GFP_KERNEL); > + if (!cache) > + goto err_out; > + cache->c_bucket_bits = bucket_bits; > + INIT_LIST_HEAD(&cache->c_lru_list); > + spin_lock_init(&cache->c_lru_list_lock); > + cache->c_hash = kmalloc(bucket_count * sizeof(struct hlist_bl_head), > + GFP_KERNEL); > + if (!cache->c_hash) { > + kfree(cache); > + goto err_out; > + } > + for (i = 0; i < bucket_count; i++) > + INIT_HLIST_BL_HEAD(&cache->c_hash[i]); > + > + cache->c_shrink.count_objects = mb2_cache_count; > + cache->c_shrink.scan_objects = mb2_cache_scan; > + cache->c_shrink.seeks = DEFAULT_SEEKS; > + register_shrinker(&cache->c_shrink); > + > + return cache; > + > +err_out: > + module_put(THIS_MODULE); > + return NULL; > +} > +EXPORT_SYMBOL(mb2_cache_create); > + > +/* > + * mb2_cache_destroy - destroy cache > + * @cache: the cache to destroy > + * > + * Free all entries in cache and cache itself. Caller must make sure nobody > + * (except shrinker) can reach @cache when calling this. > + */ > +void mb2_cache_destroy(struct mb2_cache *cache) > +{ > + struct mb2_cache_entry *entry, *next; > + > + unregister_shrinker(&cache->c_shrink); > + > + /* > + * We don't bother with any locking. Cache must not be used at this > + * point. > + */ > + list_for_each_entry_safe(entry, next, &cache->c_lru_list, e_lru_list) { > + if (!hlist_bl_unhashed(&entry->e_hash_list)) { > + hlist_bl_del_init(&entry->e_hash_list); > + atomic_dec(&entry->e_refcnt); > + } else > + WARN_ON(1); > + list_del(&entry->e_lru_list); > + WARN_ON(atomic_read(&entry->e_refcnt) != 1); > + mb2_cache_entry_put(cache, entry); > + } > + kfree(cache->c_hash); > + kfree(cache); > + module_put(THIS_MODULE); > +} > +EXPORT_SYMBOL(mb2_cache_destroy); > + > +static int __init mb2cache_init(void) > +{ > + mb2_entry_cache = kmem_cache_create("mbcache", > + sizeof(struct mb2_cache_entry), 0, > + SLAB_RECLAIM_ACCOUNT|SLAB_MEM_SPREAD, NULL); > + BUG_ON(!mb2_entry_cache); > + return 0; > +} > + > +static void __exit mb2cache_exit(void) > +{ > + kmem_cache_destroy(mb2_entry_cache); > +} > + > +module_init(mb2cache_init) > +module_exit(mb2cache_exit) > + > +MODULE_AUTHOR("Jan Kara <jack@suse.cz>"); > +MODULE_DESCRIPTION("Meta block cache (for extended attributes)"); > +MODULE_LICENSE("GPL"); > diff --git a/include/linux/mbcache2.h b/include/linux/mbcache2.h > new file mode 100644 > index 000000000000..2a58c51c3a0a > --- /dev/null > +++ b/include/linux/mbcache2.h > @@ -0,0 +1,54 @@ > +#ifndef _LINUX_MB2CACHE_H > +#define _LINUX_MB2CACHE_H > + > +#include <linux/hash.h> > +#include <linux/list_bl.h> > +#include <linux/list.h> > +#include <linux/atomic.h> > +#include <linux/fs.h> > + > +struct mb2_cache; > + > +struct mb2_cache_entry { > + /* LRU list - protected by cache->c_lru_list_lock */ > + struct list_head e_lru_list; > + /* Hash table list - protected by bitlock in e_hash_list_head */ > + struct hlist_bl_node e_hash_list; > + atomic_t e_refcnt; > + /* Key in hash - stable during lifetime of the entry */ > + unsigned int e_key; > + /* Block number of hashed block - stable during lifetime of the entry */ > + sector_t e_block; > + /* Head of hash list (for list bit lock) - stable */ > + struct hlist_bl_head *e_hash_list_head; > +}; > + > +struct mb2_cache *mb2_cache_create(int bucket_bits); > +void mb2_cache_destroy(struct mb2_cache *cache); > + > +struct mb2_cache_entry *mb2_cache_entry_create(struct mb2_cache *cache, > + gfp_t mask, > + unsigned int key, > + sector_t block); > +void mb2_cache_entry_delete(struct mb2_cache *cache, > + struct mb2_cache_entry *entry); > +void __mb2_cache_entry_free(struct mb2_cache_entry *entry); > +static inline int mb2_cache_entry_put(struct mb2_cache *cache, > + struct mb2_cache_entry *entry) > +{ > + if (!atomic_dec_and_test(&entry->e_refcnt)) > + return 0; > + __mb2_cache_entry_free(entry); > + return 1; > +} > + > +void mb2_cache_entry_delete_block(struct mb2_cache *cache, unsigned int key, > + sector_t block); > +struct mb2_cache_entry *mb2_cache_entry_find_first(struct mb2_cache *cache, > + unsigned int key); > +struct mb2_cache_entry *mb2_cache_entry_find_next(struct mb2_cache *cache, > + struct mb2_cache_entry *entry); > +void mb2_cache_entry_touch(struct mb2_cache *cache, > + struct mb2_cache_entry *entry); > + > +#endif /* _LINUX_MB2CACHE_H */ > -- > 2.1.4 Thanks, Andreas -- To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hello, On Sat 12-12-15 00:58:30, Andreas Grünbacher wrote: > > +/* > > + * Mbcache is a simple key-value store. > > + Keys need not be unique, however > > + * key-value pairs are expected to be unique (we use this in > > + * mb2_cache_entry_delete_block()). > > This comment is very confusing. Could you say what the keys and values > are and what that kind of cache is used for so that people will have a > chance of understanding what's going on? I've added some more explanations to the comment. > > + * We provide functions for creation and removal of entries, search by key, > > + * and a special "delete entry with given key-value pair" operation. Fixed > > + * size hash table is used for fast key lookups. > > + */ > > Have you had a look at rhashtables? They would give us lockless > lookups and they would automatically grow, at somewhat more > complexity. No, I didn't have a look at them. As I said I'm not sure the complexity is worth it. We can have a look into it in future. Lockless lookups could provide interesting speedups for the case with limited number of unique xattr blocks. Case with lots of unique xattr blocks will not benefit at all since that is write-mostly workload... > > +/* > > + * mb2_cache_entry_delete - delete entry from cache > > + * @cache - cache where the entry is > > + * @entry - entry to delete > > + * > > + * Delete entry from cache. The entry is unhashed and deleted from the lru list > > + * so it cannot be found. We also drop the reference to @entry caller gave us. > > + * However entry need not be freed if there's someone else still holding a > > + * reference to it. Freeing happens when the last reference is dropped. > > + */ > > +void mb2_cache_entry_delete(struct mb2_cache *cache, > > + struct mb2_cache_entry *entry) > > This function should become static; there are no external users. It's actually completely unused. But if we end up removing entries for blocks where refcount hit maximum, then it will be used by the fs. Thinking about removal of entries with max refcount, the slight complication is that when refcount decreases again, we won't insert the entry in cache unless someone calls listattr or getattr for inode with that block. So we'll probably need some more complex logic to avoid this. I'll first gather some statistics on the lengths of hash chains and hash chain scanning when there are few unique xattrs to see whether the complexity is worth it. > > +/* Shrink number of entries in cache */ > > +static unsigned long mb2_cache_scan(struct shrinker *shrink, > > + struct shrink_control *sc) > > +{ > > + int nr_to_scan = sc->nr_to_scan; > > + struct mb2_cache *cache = container_of(shrink, struct mb2_cache, > > + c_shrink); > > + struct mb2_cache_entry *entry; > > + struct hlist_bl_head *head; > > + unsigned int shrunk = 0; > > + > > + spin_lock(&cache->c_lru_list_lock); > > + while (nr_to_scan-- && !list_empty(&cache->c_lru_list)) { > > + entry = list_first_entry(&cache->c_lru_list, > > + struct mb2_cache_entry, e_lru_list); > > + list_del_init(&entry->e_lru_list); > > + cache->c_entry_count--; > > + /* > > + * We keep LRU list reference so that entry doesn't go away > > + * from under us. > > + */ > > + spin_unlock(&cache->c_lru_list_lock); > > + head = entry->e_hash_list_head; > > + hlist_bl_lock(head); > > Instead of taking and dropping c_lru_list_lock in the loop, could we > get away with a simple-to-implement hlist_bl_trylock() and > cond_resched_lock()? For now I'd keep things simple. Since we limit number of entries in cache ourselves, shrinker doesn't get used that often and so the lock traffic on lru_list_lock from it is minimal... Honza
On Tue 15-12-15 12:08:09, Jan Kara wrote: > > > +/* > > > + * mb2_cache_entry_delete - delete entry from cache > > > + * @cache - cache where the entry is > > > + * @entry - entry to delete > > > + * > > > + * Delete entry from cache. The entry is unhashed and deleted from the lru list > > > + * so it cannot be found. We also drop the reference to @entry caller gave us. > > > + * However entry need not be freed if there's someone else still holding a > > > + * reference to it. Freeing happens when the last reference is dropped. > > > + */ > > > +void mb2_cache_entry_delete(struct mb2_cache *cache, > > > + struct mb2_cache_entry *entry) > > > > This function should become static; there are no external users. > > It's actually completely unused. But if we end up removing entries for > blocks where refcount hit maximum, then it will be used by the fs. Thinking > about removal of entries with max refcount, the slight complication is that > when refcount decreases again, we won't insert the entry in cache unless > someone calls listattr or getattr for inode with that block. So we'll > probably need some more complex logic to avoid this. > > I'll first gather some statistics on the lengths of hash chains and hash > chain scanning when there are few unique xattrs to see whether the > complexity is worth it. So I did some experiments with observing length of hash chains with lots of same xattr blocks. Indeed hash chains get rather long in such case as you expected - for F files having V different xattr blocks hash chain lenght is around F/V/1024 as expected. I've also implemented logic that removes entry from cache when the refcount of xattr block reaches maximum and adds it back when refcount drops. But this doesn't make hash chains significantly shorter because most of xattr blocks end up close to max refcount but not quite at the maximum (as the benchmark ends up adding & removing references to blocks mostly randomly). That made me realize that any strategy based solely on xattr block refcount isn't going to significantly improve the situation. What we'd have to do is something like making sure that we cache only one xattr block with given contents. However that would make insertions more costly as we'd have to compare full xattr blocks for duplicates instead of just hashes. So overall I don't think optimizing this case is really worth it for now. If we see some real world situation where this matters, we can reconsider the decision. Honza
2015-12-16 16:52 GMT+01:00 Jan Kara <jack@suse.cz>: > On Tue 15-12-15 12:08:09, Jan Kara wrote: >> > > +/* >> > > + * mb2_cache_entry_delete - delete entry from cache >> > > + * @cache - cache where the entry is >> > > + * @entry - entry to delete >> > > + * >> > > + * Delete entry from cache. The entry is unhashed and deleted from the lru list >> > > + * so it cannot be found. We also drop the reference to @entry caller gave us. >> > > + * However entry need not be freed if there's someone else still holding a >> > > + * reference to it. Freeing happens when the last reference is dropped. >> > > + */ >> > > +void mb2_cache_entry_delete(struct mb2_cache *cache, >> > > + struct mb2_cache_entry *entry) >> > >> > This function should become static; there are no external users. >> >> It's actually completely unused. But if we end up removing entries for >> blocks where refcount hit maximum, then it will be used by the fs. Thinking >> about removal of entries with max refcount, the slight complication is that >> when refcount decreases again, we won't insert the entry in cache unless >> someone calls listattr or getattr for inode with that block. So we'll >> probably need some more complex logic to avoid this. >> >> I'll first gather some statistics on the lengths of hash chains and hash >> chain scanning when there are few unique xattrs to see whether the >> complexity is worth it. > > So I did some experiments with observing length of hash chains with lots of > same xattr blocks. Indeed hash chains get rather long in such case as you > expected - for F files having V different xattr blocks hash chain lenght is > around F/V/1024 as expected. > > I've also implemented logic that removes entry from cache when the refcount > of xattr block reaches maximum and adds it back when refcount drops. But > this doesn't make hash chains significantly shorter because most of xattr > blocks end up close to max refcount but not quite at the maximum (as the > benchmark ends up adding & removing references to blocks mostly > randomly). > > That made me realize that any strategy based solely on xattr block refcount > isn't going to significantly improve the situation. That test scenario probably isn't very realistic: xattrs are mostly initialized at or immediately after file create time; they rarely removed. Hash chains should shrink significantly for that scenario. In addition, if the hash table is sized reasonably, long hash chains won't hurt that much because we can stop searching them as soon as we find the first reusable block. This won't help when there are hash conflicts, but those should be unlikely. We are currently using a predictable hash algorithm so attacks on the hash table are possible; it's probably not worth protecting against that though. > What we'd have to do is something like making sure that we cache only > one xattr block with given contents. No, when that one cached block reaches its maximum refcount, we would have to allocate another block because we didn't cache the other identical, reusable blocks; this would hurt significantly. > However that would make insertions more costly as we'd have to > compare full xattr blocks for duplicates instead of just hashes. I don't understand, why would we turn to comparing blocks? Thanks, Andreas -- To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue 22-12-15 13:20:58, Andreas Grünbacher wrote: > 2015-12-16 16:52 GMT+01:00 Jan Kara <jack@suse.cz>: > > On Tue 15-12-15 12:08:09, Jan Kara wrote: > >> > > +/* > >> > > + * mb2_cache_entry_delete - delete entry from cache > >> > > + * @cache - cache where the entry is > >> > > + * @entry - entry to delete > >> > > + * > >> > > + * Delete entry from cache. The entry is unhashed and deleted from the lru list > >> > > + * so it cannot be found. We also drop the reference to @entry caller gave us. > >> > > + * However entry need not be freed if there's someone else still holding a > >> > > + * reference to it. Freeing happens when the last reference is dropped. > >> > > + */ > >> > > +void mb2_cache_entry_delete(struct mb2_cache *cache, > >> > > + struct mb2_cache_entry *entry) > >> > > >> > This function should become static; there are no external users. > >> > >> It's actually completely unused. But if we end up removing entries for > >> blocks where refcount hit maximum, then it will be used by the fs. Thinking > >> about removal of entries with max refcount, the slight complication is that > >> when refcount decreases again, we won't insert the entry in cache unless > >> someone calls listattr or getattr for inode with that block. So we'll > >> probably need some more complex logic to avoid this. > >> > >> I'll first gather some statistics on the lengths of hash chains and hash > >> chain scanning when there are few unique xattrs to see whether the > >> complexity is worth it. > > > > So I did some experiments with observing length of hash chains with lots of > > same xattr blocks. Indeed hash chains get rather long in such case as you > > expected - for F files having V different xattr blocks hash chain lenght is > > around F/V/1024 as expected. > > > > I've also implemented logic that removes entry from cache when the refcount > > of xattr block reaches maximum and adds it back when refcount drops. But > > this doesn't make hash chains significantly shorter because most of xattr > > blocks end up close to max refcount but not quite at the maximum (as the > > benchmark ends up adding & removing references to blocks mostly > > randomly). > > > > That made me realize that any strategy based solely on xattr block refcount > > isn't going to significantly improve the situation. > > That test scenario probably isn't very realistic: xattrs are mostly > initialized at or immediately after file create time; they rarely > removed. Hash chains should shrink significantly for that scenario. Well, the refcount gets dropped when the file itself is deleted. And that isn't that rare. So I agree my benchmark isn't completely realistic in changing the xattr but dropping xattr block refcount due to deleted file will be relatively frequent so I don't thing refcount distribution obtained by my benchmark is completely out. > In addition, if the hash table is sized reasonably, long hash chains > won't hurt that much because we can stop searching them as soon as we > find the first reusable block. This won't help when there are hash > conflicts, but those should be unlikely. Well, this is what happens currently as well... > We are currently using a predictable hash algorithm so attacks on the > hash table are possible; it's probably not worth protecting against > that though. Agreed. > > What we'd have to do is something like making sure that we cache only > > one xattr block with given contents. > > No, when that one cached block reaches its maximum refcount, we would > have to allocate another block because we didn't cache the other > identical, reusable blocks; this would hurt significantly. > > > However that would make insertions more costly as we'd have to > > compare full xattr blocks for duplicates instead of just hashes. > > I don't understand, why would we turn to comparing blocks? If we wanted to avoid duplicit blocks in the hash table, we'd have to first find out whether two blocks are really the same (or whether just 32-bit hash collided). But as I said (and you seem to agree) this isn't the right way to go anyway. Honza
2015-12-22 14:07 GMT+01:00 Jan Kara <jack@suse.cz>: > On Tue 22-12-15 13:20:58, Andreas Grünbacher wrote: >> 2015-12-16 16:52 GMT+01:00 Jan Kara <jack@suse.cz>: >> > On Tue 15-12-15 12:08:09, Jan Kara wrote: >> >> > > +/* >> >> > > + * mb2_cache_entry_delete - delete entry from cache >> >> > > + * @cache - cache where the entry is >> >> > > + * @entry - entry to delete >> >> > > + * >> >> > > + * Delete entry from cache. The entry is unhashed and deleted from the lru list >> >> > > + * so it cannot be found. We also drop the reference to @entry caller gave us. >> >> > > + * However entry need not be freed if there's someone else still holding a >> >> > > + * reference to it. Freeing happens when the last reference is dropped. >> >> > > + */ >> >> > > +void mb2_cache_entry_delete(struct mb2_cache *cache, >> >> > > + struct mb2_cache_entry *entry) >> >> > >> >> > This function should become static; there are no external users. >> >> >> >> It's actually completely unused. But if we end up removing entries for >> >> blocks where refcount hit maximum, then it will be used by the fs. Thinking >> >> about removal of entries with max refcount, the slight complication is that >> >> when refcount decreases again, we won't insert the entry in cache unless >> >> someone calls listattr or getattr for inode with that block. So we'll >> >> probably need some more complex logic to avoid this. >> >> >> >> I'll first gather some statistics on the lengths of hash chains and hash >> >> chain scanning when there are few unique xattrs to see whether the >> >> complexity is worth it. >> > >> > So I did some experiments with observing length of hash chains with lots of >> > same xattr blocks. Indeed hash chains get rather long in such case as you >> > expected - for F files having V different xattr blocks hash chain lenght is >> > around F/V/1024 as expected. >> > >> > I've also implemented logic that removes entry from cache when the refcount >> > of xattr block reaches maximum and adds it back when refcount drops. But >> > this doesn't make hash chains significantly shorter because most of xattr >> > blocks end up close to max refcount but not quite at the maximum (as the >> > benchmark ends up adding & removing references to blocks mostly >> > randomly). >> > >> > That made me realize that any strategy based solely on xattr block refcount >> > isn't going to significantly improve the situation. >> >> That test scenario probably isn't very realistic: xattrs are mostly >> initialized at or immediately after file create time; they rarely >> removed. Hash chains should shrink significantly for that scenario. > > Well, the refcount gets dropped when the file itself is deleted. And that > isn't that rare. So I agree my benchmark isn't completely realistic in > changing the xattr but dropping xattr block refcount due to deleted file > will be relatively frequent so I don't thing refcount distribution obtained > by my benchmark is completely out. Good point. >> In addition, if the hash table is sized reasonably, long hash chains >> won't hurt that much because we can stop searching them as soon as we >> find the first reusable block. This won't help when there are hash >> conflicts, but those should be unlikely. > > Well, this is what happens currently as well... Yes, except that many "unshareable" xattr blocks can remain in the hash table where they can only be skipped over. Since you have already written the code for fixing that and that fix won't make things worse, I would like to see that go in. Andreas -- To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/fs/Makefile b/fs/Makefile index 79f522575cba..15b3d6c4e46a 100644 --- a/fs/Makefile +++ b/fs/Makefile @@ -41,7 +41,7 @@ obj-$(CONFIG_COMPAT_BINFMT_ELF) += compat_binfmt_elf.o obj-$(CONFIG_BINFMT_ELF_FDPIC) += binfmt_elf_fdpic.o obj-$(CONFIG_BINFMT_FLAT) += binfmt_flat.o -obj-$(CONFIG_FS_MBCACHE) += mbcache.o +obj-$(CONFIG_FS_MBCACHE) += mbcache.o mbcache2.o obj-$(CONFIG_FS_POSIX_ACL) += posix_acl.o obj-$(CONFIG_NFS_COMMON) += nfs_common/ obj-$(CONFIG_COREDUMP) += coredump.o diff --git a/fs/mbcache2.c b/fs/mbcache2.c new file mode 100644 index 000000000000..4ccf0752c6d1 --- /dev/null +++ b/fs/mbcache2.c @@ -0,0 +1,388 @@ +#include <linux/spinlock.h> +#include <linux/slab.h> +#include <linux/list.h> +#include <linux/list_bl.h> +#include <linux/module.h> +#include <linux/sched.h> +#include <linux/mbcache2.h> + +/* + * Mbcache is a simple key-value store. Keys need not be unique, however + * key-value pairs are expected to be unique (we use this in + * mb2_cache_entry_delete_block()). + * + * We provide functions for creation and removal of entries, search by key, + * and a special "delete entry with given key-value pair" operation. Fixed + * size hash table is used for fast key lookups. + */ + +struct mb2_cache { + /* Hash table of entries */ + struct hlist_bl_head *c_hash; + /* log2 of hash table size */ + int c_bucket_bits; + /* Protects c_lru_list, c_entry_count */ + spinlock_t c_lru_list_lock; + struct list_head c_lru_list; + /* Number of entries in cache */ + unsigned long c_entry_count; + struct shrinker c_shrink; +}; + +static struct kmem_cache *mb2_entry_cache; + +/* + * mb2_cache_entry_create - create entry in cache + * @cache - cache where the entry should be created + * @mask - gfp mask with which the entry should be allocated + * @key - key of the entry + * @block - block that contains data + * + * Creates entry in @cache with key @key and records that data is stored in + * block @block. The function returns -EBUSY if entry with the same key + * and for the same block already exists in cache. Otherwise reference to + * the created entry is returned. + */ +struct mb2_cache_entry *mb2_cache_entry_create(struct mb2_cache *cache, + gfp_t mask, + unsigned int key, + sector_t block) +{ + struct mb2_cache_entry *entry, *dup; + struct hlist_bl_node *dup_node; + struct hlist_bl_head *head; + + entry = kmem_cache_alloc(mb2_entry_cache, mask); + if (!entry) + return ERR_PTR(-ENOMEM); + + INIT_LIST_HEAD(&entry->e_lru_list); + /* One ref for hash, one ref returned */ + atomic_set(&entry->e_refcnt, 2); + entry->e_key = key; + entry->e_block = block; + head = &cache->c_hash[hash_32(key, cache->c_bucket_bits)]; + entry->e_hash_list_head = head; + hlist_bl_lock(head); + hlist_bl_for_each_entry(dup, dup_node, head, e_hash_list) { + if (dup->e_key == key && dup->e_block == block) { + hlist_bl_unlock(head); + kmem_cache_free(mb2_entry_cache, entry); + return ERR_PTR(-EBUSY); + } + } + hlist_bl_add_head(&entry->e_hash_list, head); + hlist_bl_unlock(head); + + spin_lock(&cache->c_lru_list_lock); + list_add_tail(&entry->e_lru_list, &cache->c_lru_list); + /* Grab ref for LRU list */ + atomic_inc(&entry->e_refcnt); + cache->c_entry_count++; + spin_unlock(&cache->c_lru_list_lock); + + return entry; +} +EXPORT_SYMBOL(mb2_cache_entry_create); + +void __mb2_cache_entry_free(struct mb2_cache_entry *entry) +{ + kmem_cache_free(mb2_entry_cache, entry); +} +EXPORT_SYMBOL(__mb2_cache_entry_free); + +/* + * mb2_cache_entry_delete - delete entry from cache + * @cache - cache where the entry is + * @entry - entry to delete + * + * Delete entry from cache. The entry is unhashed and deleted from the lru list + * so it cannot be found. We also drop the reference to @entry caller gave us. + * However entry need not be freed if there's someone else still holding a + * reference to it. Freeing happens when the last reference is dropped. + */ +void mb2_cache_entry_delete(struct mb2_cache *cache, + struct mb2_cache_entry *entry) +{ + struct hlist_bl_head *head = entry->e_hash_list_head; + + hlist_bl_lock(head); + if (!hlist_bl_unhashed(&entry->e_hash_list)) { + hlist_bl_del_init(&entry->e_hash_list); + atomic_dec(&entry->e_refcnt); + } + hlist_bl_unlock(head); + spin_lock(&cache->c_lru_list_lock); + if (!list_empty(&entry->e_lru_list)) { + list_del_init(&entry->e_lru_list); + cache->c_entry_count--; + atomic_dec(&entry->e_refcnt); + } + spin_unlock(&cache->c_lru_list_lock); + mb2_cache_entry_put(cache, entry); +} +EXPORT_SYMBOL(mb2_cache_entry_delete); + +static struct mb2_cache_entry *__entry_find(struct mb2_cache *cache, + struct mb2_cache_entry *entry, + unsigned int key) +{ + struct mb2_cache_entry *old_entry = entry; + struct hlist_bl_node *node; + struct hlist_bl_head *head; + + if (entry) + head = entry->e_hash_list_head; + else + head = &cache->c_hash[hash_32(key, cache->c_bucket_bits)]; + hlist_bl_lock(head); + if (entry && !hlist_bl_unhashed(&entry->e_hash_list)) + node = entry->e_hash_list.next; + else + node = hlist_bl_first(head); + while (node) { + entry = hlist_bl_entry(node, struct mb2_cache_entry, + e_hash_list); + if (entry->e_key == key) { + atomic_inc(&entry->e_refcnt); + goto out; + } + node = node->next; + } + entry = NULL; +out: + hlist_bl_unlock(head); + if (old_entry) + mb2_cache_entry_put(cache, old_entry); + + return entry; +} + +/* + * mb2_cache_entry_find_first - find the first entry in cache with given key + * @cache: cache where we should search + * @key: key to look for + * + * Search in @cache for entry with key @key. Grabs reference to the first + * entry found and returns the entry. + */ +struct mb2_cache_entry *mb2_cache_entry_find_first(struct mb2_cache *cache, + unsigned int key) +{ + return __entry_find(cache, NULL, key); +} +EXPORT_SYMBOL(mb2_cache_entry_find_first); + +/* + * mb2_cache_entry_find_next - find next entry in cache with the same + * @cache: cache where we should search + * @entry: entry to start search from + * + * Finds next entry in the hash chain which has the same key as @entry. + * If @entry is unhashed (which can happen when deletion of entry races + * with the search), finds the first entry in the hash chain. The function + * drops reference to @entry and returns with a reference to the found entry. + */ +struct mb2_cache_entry *mb2_cache_entry_find_next(struct mb2_cache *cache, + struct mb2_cache_entry *entry) +{ + return __entry_find(cache, entry, entry->e_key); +} +EXPORT_SYMBOL(mb2_cache_entry_find_next); + +/* mb2_cache_entry_delete_block - remove information about block from cache + * @cache - cache we work with + * @key - key of the entry to remove + * @block - block containing data for @key + * + * Remove entry from cache @cache with key @key with data stored in @block. + */ +void mb2_cache_entry_delete_block(struct mb2_cache *cache, unsigned int key, + sector_t block) +{ + struct hlist_bl_node *node; + struct hlist_bl_head *head; + struct mb2_cache_entry *entry; + + head = &cache->c_hash[hash_32(key, cache->c_bucket_bits)]; + hlist_bl_lock(head); + hlist_bl_for_each_entry(entry, node, head, e_hash_list) { + if (entry->e_key == key && entry->e_block == block) { + /* We keep hash list reference to keep entry alive */ + hlist_bl_del_init(&entry->e_hash_list); + hlist_bl_unlock(head); + spin_lock(&cache->c_lru_list_lock); + if (!list_empty(&entry->e_lru_list)) { + list_del_init(&entry->e_lru_list); + cache->c_entry_count--; + atomic_dec(&entry->e_refcnt); + } + spin_unlock(&cache->c_lru_list_lock); + mb2_cache_entry_put(cache, entry); + return; + } + } + hlist_bl_unlock(head); +} +EXPORT_SYMBOL(mb2_cache_entry_delete_block); + +/* mb2_cache_entry_touch - cache entry got used + * @cache - cache the entry belongs to + * @entry - entry that got used + * + * Move entry in lru list to reflect the fact that it was used. + */ +void mb2_cache_entry_touch(struct mb2_cache *cache, + struct mb2_cache_entry *entry) +{ + spin_lock(&cache->c_lru_list_lock); + if (!list_empty(&entry->e_lru_list)) + list_move_tail(&cache->c_lru_list, &entry->e_lru_list); + spin_unlock(&cache->c_lru_list_lock); +} +EXPORT_SYMBOL(mb2_cache_entry_touch); + +static unsigned long mb2_cache_count(struct shrinker *shrink, + struct shrink_control *sc) +{ + struct mb2_cache *cache = container_of(shrink, struct mb2_cache, + c_shrink); + + return cache->c_entry_count; +} + +/* Shrink number of entries in cache */ +static unsigned long mb2_cache_scan(struct shrinker *shrink, + struct shrink_control *sc) +{ + int nr_to_scan = sc->nr_to_scan; + struct mb2_cache *cache = container_of(shrink, struct mb2_cache, + c_shrink); + struct mb2_cache_entry *entry; + struct hlist_bl_head *head; + unsigned int shrunk = 0; + + spin_lock(&cache->c_lru_list_lock); + while (nr_to_scan-- && !list_empty(&cache->c_lru_list)) { + entry = list_first_entry(&cache->c_lru_list, + struct mb2_cache_entry, e_lru_list); + list_del_init(&entry->e_lru_list); + cache->c_entry_count--; + /* + * We keep LRU list reference so that entry doesn't go away + * from under us. + */ + spin_unlock(&cache->c_lru_list_lock); + head = entry->e_hash_list_head; + hlist_bl_lock(head); + if (!hlist_bl_unhashed(&entry->e_hash_list)) { + hlist_bl_del_init(&entry->e_hash_list); + atomic_dec(&entry->e_refcnt); + } + hlist_bl_unlock(head); + if (mb2_cache_entry_put(cache, entry)) + shrunk++; + cond_resched(); + spin_lock(&cache->c_lru_list_lock); + } + spin_unlock(&cache->c_lru_list_lock); + + return shrunk; +} + +/* + * mb2_cache_create - create cache + * @bucket_bits: log2 of the hash table size + * + * Create cache for keys with 2^bucket_bits hash entries. + */ +struct mb2_cache *mb2_cache_create(int bucket_bits) +{ + struct mb2_cache *cache; + int bucket_count = 1 << bucket_bits; + int i; + + if (!try_module_get(THIS_MODULE)) + return NULL; + + cache = kzalloc(sizeof(struct mb2_cache), GFP_KERNEL); + if (!cache) + goto err_out; + cache->c_bucket_bits = bucket_bits; + INIT_LIST_HEAD(&cache->c_lru_list); + spin_lock_init(&cache->c_lru_list_lock); + cache->c_hash = kmalloc(bucket_count * sizeof(struct hlist_bl_head), + GFP_KERNEL); + if (!cache->c_hash) { + kfree(cache); + goto err_out; + } + for (i = 0; i < bucket_count; i++) + INIT_HLIST_BL_HEAD(&cache->c_hash[i]); + + cache->c_shrink.count_objects = mb2_cache_count; + cache->c_shrink.scan_objects = mb2_cache_scan; + cache->c_shrink.seeks = DEFAULT_SEEKS; + register_shrinker(&cache->c_shrink); + + return cache; + +err_out: + module_put(THIS_MODULE); + return NULL; +} +EXPORT_SYMBOL(mb2_cache_create); + +/* + * mb2_cache_destroy - destroy cache + * @cache: the cache to destroy + * + * Free all entries in cache and cache itself. Caller must make sure nobody + * (except shrinker) can reach @cache when calling this. + */ +void mb2_cache_destroy(struct mb2_cache *cache) +{ + struct mb2_cache_entry *entry, *next; + + unregister_shrinker(&cache->c_shrink); + + /* + * We don't bother with any locking. Cache must not be used at this + * point. + */ + list_for_each_entry_safe(entry, next, &cache->c_lru_list, e_lru_list) { + if (!hlist_bl_unhashed(&entry->e_hash_list)) { + hlist_bl_del_init(&entry->e_hash_list); + atomic_dec(&entry->e_refcnt); + } else + WARN_ON(1); + list_del(&entry->e_lru_list); + WARN_ON(atomic_read(&entry->e_refcnt) != 1); + mb2_cache_entry_put(cache, entry); + } + kfree(cache->c_hash); + kfree(cache); + module_put(THIS_MODULE); +} +EXPORT_SYMBOL(mb2_cache_destroy); + +static int __init mb2cache_init(void) +{ + mb2_entry_cache = kmem_cache_create("mbcache", + sizeof(struct mb2_cache_entry), 0, + SLAB_RECLAIM_ACCOUNT|SLAB_MEM_SPREAD, NULL); + BUG_ON(!mb2_entry_cache); + return 0; +} + +static void __exit mb2cache_exit(void) +{ + kmem_cache_destroy(mb2_entry_cache); +} + +module_init(mb2cache_init) +module_exit(mb2cache_exit) + +MODULE_AUTHOR("Jan Kara <jack@suse.cz>"); +MODULE_DESCRIPTION("Meta block cache (for extended attributes)"); +MODULE_LICENSE("GPL"); diff --git a/include/linux/mbcache2.h b/include/linux/mbcache2.h new file mode 100644 index 000000000000..2a58c51c3a0a --- /dev/null +++ b/include/linux/mbcache2.h @@ -0,0 +1,54 @@ +#ifndef _LINUX_MB2CACHE_H +#define _LINUX_MB2CACHE_H + +#include <linux/hash.h> +#include <linux/list_bl.h> +#include <linux/list.h> +#include <linux/atomic.h> +#include <linux/fs.h> + +struct mb2_cache; + +struct mb2_cache_entry { + /* LRU list - protected by cache->c_lru_list_lock */ + struct list_head e_lru_list; + /* Hash table list - protected by bitlock in e_hash_list_head */ + struct hlist_bl_node e_hash_list; + atomic_t e_refcnt; + /* Key in hash - stable during lifetime of the entry */ + unsigned int e_key; + /* Block number of hashed block - stable during lifetime of the entry */ + sector_t e_block; + /* Head of hash list (for list bit lock) - stable */ + struct hlist_bl_head *e_hash_list_head; +}; + +struct mb2_cache *mb2_cache_create(int bucket_bits); +void mb2_cache_destroy(struct mb2_cache *cache); + +struct mb2_cache_entry *mb2_cache_entry_create(struct mb2_cache *cache, + gfp_t mask, + unsigned int key, + sector_t block); +void mb2_cache_entry_delete(struct mb2_cache *cache, + struct mb2_cache_entry *entry); +void __mb2_cache_entry_free(struct mb2_cache_entry *entry); +static inline int mb2_cache_entry_put(struct mb2_cache *cache, + struct mb2_cache_entry *entry) +{ + if (!atomic_dec_and_test(&entry->e_refcnt)) + return 0; + __mb2_cache_entry_free(entry); + return 1; +} + +void mb2_cache_entry_delete_block(struct mb2_cache *cache, unsigned int key, + sector_t block); +struct mb2_cache_entry *mb2_cache_entry_find_first(struct mb2_cache *cache, + unsigned int key); +struct mb2_cache_entry *mb2_cache_entry_find_next(struct mb2_cache *cache, + struct mb2_cache_entry *entry); +void mb2_cache_entry_touch(struct mb2_cache *cache, + struct mb2_cache_entry *entry); + +#endif /* _LINUX_MB2CACHE_H */
Original mbcache was designed to have more features than what ext? filesystems ended up using. It supported entry being in more hashes, it had a home-grown rwlocking of each entry, and one cache could cache entries from multiple filesystems. This genericity also resulted in more complex locking, larger cache entries, and generally more code complexity. This is reimplementation of the mbcache functionality to exactly fit the purpose ext? filesystems use it for. Cache entries are now considerably smaller (7 instead of 13 longs), the code is considerably smaller as well (432 vs 913 lines of code), and IMO also simpler. The new code is also much more lightweight. I have measured the speed using artificial xattr-bench benchmark, which spawns P processes, each process sets xattr for F different files, and the value of xattr is randomly chosen from a pool of V values. Averages of runtimes for 5 runs for various combinations of parameters are below. The first value in each cell is old mbache, the second value is the new mbcache. V=10 F\P 1 2 4 8 16 32 64 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 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 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 V=100 F\P 1 2 4 8 16 32 64 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 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 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 V=1000 F\P 1 2 4 8 16 32 64 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 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 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 V=10000 F\P 1 2 4 8 16 32 64 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 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 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,--- V=100000 F\P 1 2 4 8 16 32 64 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 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 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,--- We see that the new code is faster in pretty much all the cases and starting from 4 processes there are significant gains with the new code resulting in upto 20-times shorter runtimes. Also for large numbers of cached entries all values for the old code could not be measured as the kernel started hitting softlockups and died before the test completed. Signed-off-by: Jan Kara <jack@suse.cz> --- fs/Makefile | 2 +- fs/mbcache2.c | 388 +++++++++++++++++++++++++++++++++++++++++++++++ include/linux/mbcache2.h | 54 +++++++ 3 files changed, 443 insertions(+), 1 deletion(-) create mode 100644 fs/mbcache2.c create mode 100644 include/linux/mbcache2.h