From: Jan Kara Subject: [PATCH 6/6] mbcache2: Use referenced bit instead of LRU Date: Wed, 9 Dec 2015 18:57:38 +0100 Message-ID: <1449683858-28936-7-git-send-email-jack@suse.cz> References: <1449683858-28936-1-git-send-email-jack@suse.cz> Cc: linux-ext4@vger.kernel.org, Laurent GUERBY , Andreas Dilger , Jan Kara To: Ted Tso Return-path: Received: from mx2.suse.de ([195.135.220.15]:33140 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753207AbbLIR5s (ORCPT ); Wed, 9 Dec 2015 12:57:48 -0500 In-Reply-To: <1449683858-28936-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. 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 | 41 +++++++++++++++++++++++++++++++++-------- include/linux/mbcache2.h | 7 +++++-- 2 files changed, 38 insertions(+), 10 deletions(-) diff --git a/fs/mbcache2.c b/fs/mbcache2.c index fe9f6f6a2953..60310a690f8d 100644 --- a/fs/mbcache2.c +++ b/fs/mbcache2.c @@ -39,6 +39,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,7 +106,7 @@ struct mb2_cache_entry *mb2_cache_entry_create(struct mb2_cache *cache, 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) { @@ -125,7 +148,7 @@ EXPORT_SYMBOL(__mb2_cache_entry_free); void mb2_cache_entry_delete(struct mb2_cache *cache, struct mb2_cache_entry *entry) { - struct hlist_bl_head *head = entry->e_hash_list_head; + struct hlist_bl_head *head = mb2_cache_entry_head(entry); hlist_bl_lock(head); if (!hlist_bl_unhashed(&entry->e_hash_list)) { @@ -153,7 +176,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); @@ -256,10 +279,7 @@ EXPORT_SYMBOL(mb2_cache_entry_delete_block); 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); @@ -284,6 +304,11 @@ static unsigned long mb2_cache_shrink(struct mb2_cache *cache, 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); + if (mb2_cache_entry_referenced(entry)) { + mb2_cache_entry_clear_referenced(entry); + list_move_tail(&cache->c_lru_list, &entry->e_lru_list); + continue; + } list_del_init(&entry->e_lru_list); cache->c_entry_count--; /* @@ -291,7 +316,7 @@ static unsigned long mb2_cache_shrink(struct mb2_cache *cache, * from under us. */ spin_unlock(&cache->c_lru_list_lock); - head = entry->e_hash_list_head; + 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); diff --git a/include/linux/mbcache2.h b/include/linux/mbcache2.h index 2a58c51c3a0a..ca5b509c14a8 100644 --- a/include/linux/mbcache2.h +++ b/include/linux/mbcache2.h @@ -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