mbcache2-use-referenced-bit-instead-of-LRU

   1 mbcache2: use referenced bit instead of LRU
   2
   3 From: Jan Kara <jack@suse.cz>
   4
   5 Currently we maintain perfect LRU list by moving entry to the tail of
   6 the list when it gets used. However these operations on cache-global
   7 list are relatively expensive.
   8
   9 In this patch we switch to lazy updates of LRU list. Whenever entry gets
  10 used, we set a referenced bit in it. When reclaiming entries, we give
  11 referenced entries another round in the LRU.
  12
  13 In my testing this logic gives about 30% boost to workloads with mostly
  14 unique xattr blocks (e.g. xattr-bench with 10 files and 10000 unique
  15 xattr values).
  16
  17 Signed-off-by: Jan Kara <jack@suse.cz>
  18 Signed-off-by: Theodore Ts'o <tytso@mit.edu>
  19 ---
  20  fs/mbcache2.c            | 41 +++++++++++++++++++++++++++++++++--------
  21  include/linux/mbcache2.h |  7 +++++--
  22  2 files changed, 38 insertions(+), 10 deletions(-)
  23
  24 diff --git a/fs/mbcache2.c b/fs/mbcache2.c
  25 index fe9f6f6a2953..60310a690f8d 100644
  26 --- a/fs/mbcache2.c
  27 +++ b/fs/mbcache2.c
  28 @@ -39,6 +39,29 @@ static struct kmem_cache *mb2_entry_cache;
  29  static unsigned long mb2_cache_shrink(struct mb2_cache *cache,
  30                                       unsigned int nr_to_scan);
  31
  32 +static inline bool mb2_cache_entry_referenced(struct mb2_cache_entry *entry)
  33 +{
  34 +       return entry->_e_hash_list_head & 1;
  35 +}
  36 +
  37 +static inline void mb2_cache_entry_set_referenced(struct mb2_cache_entry *entry)
  38 +{
  39 +       entry->_e_hash_list_head |= 1;
  40 +}
  41 +
  42 +static inline void mb2_cache_entry_clear_referenced(
  43 +                                       struct mb2_cache_entry *entry)
  44 +{
  45 +       entry->_e_hash_list_head &= ~1;
  46 +}
  47 +
  48 +static inline struct hlist_bl_head *mb2_cache_entry_head(
  49 +                                       struct mb2_cache_entry *entry)
  50 +{
  51 +       return (struct hlist_bl_head *)
  52 +                       (entry->_e_hash_list_head & ~1);
  53 +}
  54 +
  55  /*
  56   * Number of entries to reclaim synchronously when there are too many entries
  57   * in cache
  58 @@ -83,7 +106,7 @@ struct mb2_cache_entry *mb2_cache_entry_create(struct mb2_cache *cache,
  59         entry->e_key = key;
  60         entry->e_block = block;
  61         head = &cache->c_hash[hash_32(key, cache->c_bucket_bits)];
  62 -       entry->e_hash_list_head = head;
  63 +       entry->_e_hash_list_head = (unsigned long)head;
  64         hlist_bl_lock(head);
  65         hlist_bl_for_each_entry(dup, dup_node, head, e_hash_list) {
  66                 if (dup->e_key == key && dup->e_block == block) {
  67 @@ -125,7 +148,7 @@ EXPORT_SYMBOL(__mb2_cache_entry_free);
  68  void mb2_cache_entry_delete(struct mb2_cache *cache,
  69                             struct mb2_cache_entry *entry)
  70  {
  71 -       struct hlist_bl_head *head = entry->e_hash_list_head;
  72 +       struct hlist_bl_head *head = mb2_cache_entry_head(entry);
  73
  74         hlist_bl_lock(head);
  75         if (!hlist_bl_unhashed(&entry->e_hash_list)) {
  76 @@ -153,7 +176,7 @@ static struct mb2_cache_entry *__entry_find(struct mb2_cache *cache,
  77         struct hlist_bl_head *head;
  78
  79         if (entry)
  80 -               head = entry->e_hash_list_head;
  81 +               head = mb2_cache_entry_head(entry);
  82         else
  83                 head = &cache->c_hash[hash_32(key, cache->c_bucket_bits)];
  84         hlist_bl_lock(head);
  85 @@ -256,10 +279,7 @@ EXPORT_SYMBOL(mb2_cache_entry_delete_block);
  86  void mb2_cache_entry_touch(struct mb2_cache *cache,
  87                            struct mb2_cache_entry *entry)
  88  {
  89 -       spin_lock(&cache->c_lru_list_lock);
  90 -       if (!list_empty(&entry->e_lru_list))
  91 -               list_move_tail(&cache->c_lru_list, &entry->e_lru_list);
  92 -       spin_unlock(&cache->c_lru_list_lock);
  93 +       mb2_cache_entry_set_referenced(entry);
  94  }
  95  EXPORT_SYMBOL(mb2_cache_entry_touch);
  96
  97 @@ -284,6 +304,11 @@ static unsigned long mb2_cache_shrink(struct mb2_cache *cache,
  98         while (nr_to_scan-- && !list_empty(&cache->c_lru_list)) {
  99                 entry = list_first_entry(&cache->c_lru_list,
 100                                          struct mb2_cache_entry, e_lru_list);
 101 +               if (mb2_cache_entry_referenced(entry)) {
 102 +                       mb2_cache_entry_clear_referenced(entry);
 103 +                       list_move_tail(&cache->c_lru_list, &entry->e_lru_list);
 104 +                       continue;
 105 +               }
 106                 list_del_init(&entry->e_lru_list);
 107                 cache->c_entry_count--;
 108                 /*
 109 @@ -291,7 +316,7 @@ static unsigned long mb2_cache_shrink(struct mb2_cache *cache,
 110                  * from under us.
 111                  */
 112                 spin_unlock(&cache->c_lru_list_lock);
 113 -               head = entry->e_hash_list_head;
 114 +               head = mb2_cache_entry_head(entry);
 115                 hlist_bl_lock(head);
 116                 if (!hlist_bl_unhashed(&entry->e_hash_list)) {
 117                         hlist_bl_del_init(&entry->e_hash_list);
 118 diff --git a/include/linux/mbcache2.h b/include/linux/mbcache2.h
 119 index 2a58c51c3a0a..ca5b509c14a8 100644
 120 --- a/include/linux/mbcache2.h
 121 +++ b/include/linux/mbcache2.h
 122 @@ -19,8 +19,11 @@ struct mb2_cache_entry {
 123         unsigned int            e_key;
 124         /* Block number of hashed block - stable during lifetime of the entry */
 125         sector_t                e_block;
 126 -       /* Head of hash list (for list bit lock) - stable */
 127 -       struct hlist_bl_head    *e_hash_list_head;
 128 +       /*
 129 +        * Head of hash list (for list bit lock) - stable. Combined with
 130 +        * referenced bit of entry
 131 +        */
 132 +       unsigned long           _e_hash_list_head;
 133  };
 134
 135  struct mb2_cache *mb2_cache_create(int bucket_bits);
 136 --
 137 2.1.4
 138
 139