mbcache.c 12 KB

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