^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0-only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) #include <linux/spinlock.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) #include <linux/list.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) #include <linux/list_bl.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) #include <linux/module.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) #include <linux/sched.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) #include <linux/workqueue.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #include <linux/mbcache.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * Mbcache is a simple key-value store. Keys need not be unique, however
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) * key-value pairs are expected to be unique (we use this fact in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) * mb_cache_entry_delete()).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * Ext2 and ext4 use this cache for deduplication of extended attribute blocks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) * Ext4 also uses it for deduplication of xattr values stored in inodes.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) * They use hash of data as a key and provide a value that may represent a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) * block or inode number. That's why keys need not be unique (hash of different
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) * data may be the same). However user provided value always uniquely
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) * identifies a cache entry.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) * We provide functions for creation and removal of entries, search by key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) * and a special "delete entry with given key-value pair" operation. Fixed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) * size hash table is used for fast key lookups.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) struct mb_cache {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) /* Hash table of entries */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) struct hlist_bl_head *c_hash;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) /* log2 of hash table size */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) int c_bucket_bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) /* Maximum entries in cache to avoid degrading hash too much */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) unsigned long c_max_entries;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) /* Protects c_list, c_entry_count */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) spinlock_t c_list_lock;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) struct list_head c_list;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) /* Number of entries in cache */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) unsigned long c_entry_count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) struct shrinker c_shrink;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) /* Work for shrinking when the cache has too many entries */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) struct work_struct c_shrink_work;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) static struct kmem_cache *mb_entry_cache;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) static unsigned long mb_cache_shrink(struct mb_cache *cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) unsigned long nr_to_scan);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) static inline struct hlist_bl_head *mb_cache_entry_head(struct mb_cache *cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) u32 key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) return &cache->c_hash[hash_32(key, cache->c_bucket_bits)];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) * Number of entries to reclaim synchronously when there are too many entries
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) * in cache
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) #define SYNC_SHRINK_BATCH 64
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) * mb_cache_entry_create - create entry in cache
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) * @cache - cache where the entry should be created
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) * @mask - gfp mask with which the entry should be allocated
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) * @key - key of the entry
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) * @value - value of the entry
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) * @reusable - is the entry reusable by others?
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) * Creates entry in @cache with key @key and value @value. The function returns
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) * -EBUSY if entry with the same key and value already exists in cache.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) * Otherwise 0 is returned.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) int mb_cache_entry_create(struct mb_cache *cache, gfp_t mask, u32 key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) u64 value, bool reusable)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) struct mb_cache_entry *entry, *dup;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) struct hlist_bl_node *dup_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) struct hlist_bl_head *head;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) /* Schedule background reclaim if there are too many entries */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) if (cache->c_entry_count >= cache->c_max_entries)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) schedule_work(&cache->c_shrink_work);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) /* Do some sync reclaim if background reclaim cannot keep up */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) if (cache->c_entry_count >= 2*cache->c_max_entries)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) mb_cache_shrink(cache, SYNC_SHRINK_BATCH);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) entry = kmem_cache_alloc(mb_entry_cache, mask);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) if (!entry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) INIT_LIST_HEAD(&entry->e_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) /* One ref for hash, one ref returned */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) atomic_set(&entry->e_refcnt, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) entry->e_key = key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) entry->e_value = value;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) entry->e_reusable = reusable;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) entry->e_referenced = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) head = mb_cache_entry_head(cache, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) hlist_bl_lock(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) hlist_bl_for_each_entry(dup, dup_node, head, e_hash_list) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) if (dup->e_key == key && dup->e_value == value) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) hlist_bl_unlock(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) kmem_cache_free(mb_entry_cache, entry);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) return -EBUSY;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) hlist_bl_add_head(&entry->e_hash_list, head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) hlist_bl_unlock(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) spin_lock(&cache->c_list_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) list_add_tail(&entry->e_list, &cache->c_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) /* Grab ref for LRU list */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) atomic_inc(&entry->e_refcnt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) cache->c_entry_count++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) spin_unlock(&cache->c_list_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) EXPORT_SYMBOL(mb_cache_entry_create);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) void __mb_cache_entry_free(struct mb_cache_entry *entry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) kmem_cache_free(mb_entry_cache, entry);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) EXPORT_SYMBOL(__mb_cache_entry_free);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) static struct mb_cache_entry *__entry_find(struct mb_cache *cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) struct mb_cache_entry *entry,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) u32 key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) struct mb_cache_entry *old_entry = entry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) struct hlist_bl_node *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) struct hlist_bl_head *head;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) head = mb_cache_entry_head(cache, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) hlist_bl_lock(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) if (entry && !hlist_bl_unhashed(&entry->e_hash_list))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) node = entry->e_hash_list.next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) node = hlist_bl_first(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) while (node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) entry = hlist_bl_entry(node, struct mb_cache_entry,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) e_hash_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) if (entry->e_key == key && entry->e_reusable) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) atomic_inc(&entry->e_refcnt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) node = node->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) entry = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) hlist_bl_unlock(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) if (old_entry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) mb_cache_entry_put(cache, old_entry);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) return entry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) * mb_cache_entry_find_first - find the first reusable entry with the given key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) * @cache: cache where we should search
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) * @key: key to look for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) * Search in @cache for a reusable entry with key @key. Grabs reference to the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) * first reusable entry found and returns the entry.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) struct mb_cache_entry *mb_cache_entry_find_first(struct mb_cache *cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) u32 key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) return __entry_find(cache, NULL, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) EXPORT_SYMBOL(mb_cache_entry_find_first);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) * mb_cache_entry_find_next - find next reusable entry with the same key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) * @cache: cache where we should search
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) * @entry: entry to start search from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) * Finds next reusable entry in the hash chain which has the same key as @entry.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) * If @entry is unhashed (which can happen when deletion of entry races with the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) * search), finds the first reusable entry in the hash chain. The function drops
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) * reference to @entry and returns with a reference to the found entry.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) struct mb_cache_entry *mb_cache_entry_find_next(struct mb_cache *cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) struct mb_cache_entry *entry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) return __entry_find(cache, entry, entry->e_key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) EXPORT_SYMBOL(mb_cache_entry_find_next);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) * mb_cache_entry_get - get a cache entry by value (and key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) * @cache - cache we work with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) * @key - key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) * @value - value
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) struct mb_cache_entry *mb_cache_entry_get(struct mb_cache *cache, u32 key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) u64 value)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) struct hlist_bl_node *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) struct hlist_bl_head *head;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) struct mb_cache_entry *entry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) head = mb_cache_entry_head(cache, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) hlist_bl_lock(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) hlist_bl_for_each_entry(entry, node, head, e_hash_list) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) if (entry->e_key == key && entry->e_value == value) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) atomic_inc(&entry->e_refcnt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) entry = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) hlist_bl_unlock(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) return entry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) EXPORT_SYMBOL(mb_cache_entry_get);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) /* mb_cache_entry_delete - remove a cache entry
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) * @cache - cache we work with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) * @key - key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) * @value - value
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) * Remove entry from cache @cache with key @key and value @value.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) void mb_cache_entry_delete(struct mb_cache *cache, u32 key, u64 value)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) struct hlist_bl_node *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) struct hlist_bl_head *head;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) struct mb_cache_entry *entry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) head = mb_cache_entry_head(cache, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) hlist_bl_lock(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) hlist_bl_for_each_entry(entry, node, head, e_hash_list) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) if (entry->e_key == key && entry->e_value == value) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) /* We keep hash list reference to keep entry alive */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) hlist_bl_del_init(&entry->e_hash_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) hlist_bl_unlock(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) spin_lock(&cache->c_list_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) if (!list_empty(&entry->e_list)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) list_del_init(&entry->e_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) if (!WARN_ONCE(cache->c_entry_count == 0,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) "mbcache: attempt to decrement c_entry_count past zero"))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) cache->c_entry_count--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) atomic_dec(&entry->e_refcnt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) spin_unlock(&cache->c_list_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) mb_cache_entry_put(cache, entry);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) hlist_bl_unlock(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) EXPORT_SYMBOL(mb_cache_entry_delete);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) /* mb_cache_entry_touch - cache entry got used
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) * @cache - cache the entry belongs to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) * @entry - entry that got used
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) * Marks entry as used to give hit higher chances of surviving in cache.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) void mb_cache_entry_touch(struct mb_cache *cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) struct mb_cache_entry *entry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) entry->e_referenced = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) EXPORT_SYMBOL(mb_cache_entry_touch);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) static unsigned long mb_cache_count(struct shrinker *shrink,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) struct shrink_control *sc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) struct mb_cache *cache = container_of(shrink, struct mb_cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) c_shrink);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) return cache->c_entry_count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) /* Shrink number of entries in cache */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) static unsigned long mb_cache_shrink(struct mb_cache *cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) unsigned long nr_to_scan)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) struct mb_cache_entry *entry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) struct hlist_bl_head *head;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) unsigned long shrunk = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) spin_lock(&cache->c_list_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) while (nr_to_scan-- && !list_empty(&cache->c_list)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) entry = list_first_entry(&cache->c_list,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) struct mb_cache_entry, e_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) if (entry->e_referenced) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) entry->e_referenced = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) list_move_tail(&entry->e_list, &cache->c_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) list_del_init(&entry->e_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) cache->c_entry_count--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) * We keep LRU list reference so that entry doesn't go away
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) * from under us.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) spin_unlock(&cache->c_list_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) head = mb_cache_entry_head(cache, entry->e_key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) hlist_bl_lock(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) if (!hlist_bl_unhashed(&entry->e_hash_list)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) hlist_bl_del_init(&entry->e_hash_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) atomic_dec(&entry->e_refcnt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) hlist_bl_unlock(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) if (mb_cache_entry_put(cache, entry))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) shrunk++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) cond_resched();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) spin_lock(&cache->c_list_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) spin_unlock(&cache->c_list_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) return shrunk;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) static unsigned long mb_cache_scan(struct shrinker *shrink,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) struct shrink_control *sc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) struct mb_cache *cache = container_of(shrink, struct mb_cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) c_shrink);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) return mb_cache_shrink(cache, sc->nr_to_scan);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) /* We shrink 1/X of the cache when we have too many entries in it */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) #define SHRINK_DIVISOR 16
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) static void mb_cache_shrink_worker(struct work_struct *work)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) struct mb_cache *cache = container_of(work, struct mb_cache,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) c_shrink_work);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) mb_cache_shrink(cache, cache->c_max_entries / SHRINK_DIVISOR);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) * mb_cache_create - create cache
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) * @bucket_bits: log2 of the hash table size
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) * Create cache for keys with 2^bucket_bits hash entries.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) struct mb_cache *mb_cache_create(int bucket_bits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) struct mb_cache *cache;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) unsigned long bucket_count = 1UL << bucket_bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) unsigned long i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) cache = kzalloc(sizeof(struct mb_cache), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) if (!cache)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) goto err_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) cache->c_bucket_bits = bucket_bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) cache->c_max_entries = bucket_count << 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) INIT_LIST_HEAD(&cache->c_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) spin_lock_init(&cache->c_list_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) cache->c_hash = kmalloc_array(bucket_count,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) sizeof(struct hlist_bl_head),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) if (!cache->c_hash) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) kfree(cache);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) goto err_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) for (i = 0; i < bucket_count; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) INIT_HLIST_BL_HEAD(&cache->c_hash[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) cache->c_shrink.count_objects = mb_cache_count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) cache->c_shrink.scan_objects = mb_cache_scan;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) cache->c_shrink.seeks = DEFAULT_SEEKS;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) if (register_shrinker(&cache->c_shrink)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) kfree(cache->c_hash);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) kfree(cache);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) goto err_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) INIT_WORK(&cache->c_shrink_work, mb_cache_shrink_worker);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) return cache;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) err_out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383) EXPORT_SYMBOL(mb_cache_create);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) * mb_cache_destroy - destroy cache
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) * @cache: the cache to destroy
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) * Free all entries in cache and cache itself. Caller must make sure nobody
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) * (except shrinker) can reach @cache when calling this.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392) void mb_cache_destroy(struct mb_cache *cache)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) struct mb_cache_entry *entry, *next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) unregister_shrinker(&cache->c_shrink);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) * We don't bother with any locking. Cache must not be used at this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) * point.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) list_for_each_entry_safe(entry, next, &cache->c_list, e_list) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) if (!hlist_bl_unhashed(&entry->e_hash_list)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) hlist_bl_del_init(&entry->e_hash_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) atomic_dec(&entry->e_refcnt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) WARN_ON(1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) list_del(&entry->e_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) WARN_ON(atomic_read(&entry->e_refcnt) != 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) mb_cache_entry_put(cache, entry);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) kfree(cache->c_hash);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) kfree(cache);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) EXPORT_SYMBOL(mb_cache_destroy);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) static int __init mbcache_init(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) mb_entry_cache = kmem_cache_create("mbcache",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) sizeof(struct mb_cache_entry), 0,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) SLAB_RECLAIM_ACCOUNT|SLAB_MEM_SPREAD, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) if (!mb_entry_cache)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) static void __exit mbcache_exit(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) kmem_cache_destroy(mb_entry_cache);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) module_init(mbcache_init)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) module_exit(mbcache_exit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) MODULE_AUTHOR("Jan Kara <jack@suse.cz>");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) MODULE_DESCRIPTION("Meta block cache (for extended attributes)");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) MODULE_LICENSE("GPL");
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags