From: Jan Kara Subject: [PATCH 6/7] mbcache2: Use referenced bit instead of LRU Date: Wed, 16 Dec 2015 18:00:23 +0100 Message-ID: <1450285224-1525-7-git-send-email-jack@suse.cz> References: <1450285224-1525-1-git-send-email-jack@suse.cz> Cc: =?UTF-8?q?Andreas=20Gr=C3=BCnbacher?= , Andreas Dilger , Laurent GUERBY , linux-ext4@vger.kernel.org, Jan Kara To: Ted Tso Return-path: Received: from mx2.suse.de ([195.135.220.15]:60173 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S966039AbbLPRAk (ORCPT ); Wed, 16 Dec 2015 12:00:40 -0500 In-Reply-To: <1450285224-1525-1-git-send-email-jack@suse.cz> Sender: linux-ext4-owner@vger.kernel.org List-ID: Currently we maintain perfect LRU list by moving entry to the tail of the list when it gets used. However these operations on cache-global list are relatively expensive. In this patch we switch to lazy updates of LRU list. Whenever entry gets used, we set a referenced bit in it. When reclaiming entries, we give referenced entries another round in the LRU. Since the list is not a real LRU anymore, rename it to just 'list'. In my testing this logic gives about 30% boost to workloads with mostly unique xattr blocks (e.g. xattr-bench with 10 files and 10000 unique xattr values). Signed-off-by: Jan Kara --- fs/mbcache2.c | 87 +++++++++++++++++++++++++++++++----------------- include/linux/mbcache2.h | 11 +++--- 2 files changed, 63 insertions(+), 35 deletions(-) diff --git a/fs/mbcache2.c b/fs/mbcache2.c index 8b3ef891573c..133ecb2c42ce 100644 --- a/fs/mbcache2.c +++ b/fs/mbcache2.c @@ -30,9 +30,9 @@ struct mb2_cache { int c_bucket_bits; /* Maximum entries in cache to avoid degrading hash too much */ int c_max_entries; - /* Protects c_lru_list, c_entry_count */ - spinlock_t c_lru_list_lock; - struct list_head c_lru_list; + /* Protects c_list, c_entry_count */ + spinlock_t c_list_lock; + struct list_head c_list; /* Number of entries in cache */ unsigned long c_entry_count; struct shrinker c_shrink; @@ -45,6 +45,29 @@ static struct kmem_cache *mb2_entry_cache; static unsigned long mb2_cache_shrink(struct mb2_cache *cache, unsigned int nr_to_scan); +static inline bool mb2_cache_entry_referenced(struct mb2_cache_entry *entry) +{ + return entry->_e_hash_list_head & 1; +} + +static inline void mb2_cache_entry_set_referenced(struct mb2_cache_entry *entry) +{ + entry->_e_hash_list_head |= 1; +} + +static inline void mb2_cache_entry_clear_referenced( + struct mb2_cache_entry *entry) +{ + entry->_e_hash_list_head &= ~1; +} + +static inline struct hlist_bl_head *mb2_cache_entry_head( + struct mb2_cache_entry *entry) +{ + return (struct hlist_bl_head *) + (entry->_e_hash_list_head & ~1); +} + /* * Number of entries to reclaim synchronously when there are too many entries * in cache @@ -83,13 +106,13 @@ struct mb2_cache_entry *mb2_cache_entry_create(struct mb2_cache *cache, if (!entry) return ERR_PTR(-ENOMEM); - INIT_LIST_HEAD(&entry->e_lru_list); + INIT_LIST_HEAD(&entry->e_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; + entry->_e_hash_list_head = (unsigned long)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) { @@ -101,12 +124,12 @@ struct mb2_cache_entry *mb2_cache_entry_create(struct mb2_cache *cache, 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); + spin_lock(&cache->c_list_lock); + list_add_tail(&entry->e_list, &cache->c_list); /* Grab ref for LRU list */ atomic_inc(&entry->e_refcnt); cache->c_entry_count++; - spin_unlock(&cache->c_lru_list_lock); + spin_unlock(&cache->c_list_lock); return entry; } @@ -127,7 +150,7 @@ static struct mb2_cache_entry *__entry_find(struct mb2_cache *cache, struct hlist_bl_head *head; if (entry) - head = entry->e_hash_list_head; + head = mb2_cache_entry_head(entry); else head = &cache->c_hash[hash_32(key, cache->c_bucket_bits)]; hlist_bl_lock(head); @@ -206,13 +229,13 @@ void mb2_cache_entry_delete_block(struct mb2_cache *cache, unsigned int key, /* 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); + spin_lock(&cache->c_list_lock); + if (!list_empty(&entry->e_list)) { + list_del_init(&entry->e_list); cache->c_entry_count--; atomic_dec(&entry->e_refcnt); } - spin_unlock(&cache->c_lru_list_lock); + spin_unlock(&cache->c_list_lock); mb2_cache_entry_put(cache, entry); return; } @@ -225,15 +248,12 @@ EXPORT_SYMBOL(mb2_cache_entry_delete_block); * @cache - cache the entry belongs to * @entry - entry that got used * - * Move entry in lru list to reflect the fact that it was used. + * Marks entry as used to give hit higher chances of surviving in cache. */ 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); + mb2_cache_entry_set_referenced(entry); } EXPORT_SYMBOL(mb2_cache_entry_touch); @@ -254,18 +274,23 @@ static unsigned long mb2_cache_shrink(struct mb2_cache *cache, 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); + spin_lock(&cache->c_list_lock); + while (nr_to_scan-- && !list_empty(&cache->c_list)) { + entry = list_first_entry(&cache->c_list, + struct mb2_cache_entry, e_list); + if (mb2_cache_entry_referenced(entry)) { + mb2_cache_entry_clear_referenced(entry); + list_move_tail(&cache->c_list, &entry->e_list); + continue; + } + list_del_init(&entry->e_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; + spin_unlock(&cache->c_list_lock); + head = mb2_cache_entry_head(entry); hlist_bl_lock(head); if (!hlist_bl_unhashed(&entry->e_hash_list)) { hlist_bl_del_init(&entry->e_hash_list); @@ -275,9 +300,9 @@ static unsigned long mb2_cache_shrink(struct mb2_cache *cache, if (mb2_cache_entry_put(cache, entry)) shrunk++; cond_resched(); - spin_lock(&cache->c_lru_list_lock); + spin_lock(&cache->c_list_lock); } - spin_unlock(&cache->c_lru_list_lock); + spin_unlock(&cache->c_list_lock); return shrunk; } @@ -321,8 +346,8 @@ struct mb2_cache *mb2_cache_create(int bucket_bits) goto err_out; cache->c_bucket_bits = bucket_bits; cache->c_max_entries = bucket_count << 4; - INIT_LIST_HEAD(&cache->c_lru_list); - spin_lock_init(&cache->c_lru_list_lock); + INIT_LIST_HEAD(&cache->c_list); + spin_lock_init(&cache->c_list_lock); cache->c_hash = kmalloc(bucket_count * sizeof(struct hlist_bl_head), GFP_KERNEL); if (!cache->c_hash) { @@ -364,13 +389,13 @@ void mb2_cache_destroy(struct mb2_cache *cache) * 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) { + list_for_each_entry_safe(entry, next, &cache->c_list, e_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); + list_del(&entry->e_list); WARN_ON(atomic_read(&entry->e_refcnt) != 1); mb2_cache_entry_put(cache, entry); } diff --git a/include/linux/mbcache2.h b/include/linux/mbcache2.h index 26ec4ecd2a18..e84983be8311 100644 --- a/include/linux/mbcache2.h +++ b/include/linux/mbcache2.h @@ -10,8 +10,8 @@ struct mb2_cache; struct mb2_cache_entry { - /* LRU list - protected by cache->c_lru_list_lock */ - struct list_head e_lru_list; + /* List of entries in cache - protected by cache->c_list_lock */ + struct list_head e_list; /* Hash table list - protected by bitlock in e_hash_list_head */ struct hlist_bl_node e_hash_list; atomic_t e_refcnt; @@ -19,8 +19,11 @@ struct mb2_cache_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; + /* + * Head of hash list (for list bit lock) - stable. Combined with + * referenced bit of entry + */ + unsigned long _e_hash_list_head; }; struct mb2_cache *mb2_cache_create(int bucket_bits); -- 2.1.4