// SPDX-License-Identifier: GPL-2.0 #include <linux/mm.h>#include "lru_cache.h"#include "messages.h" /* * Initialize a cache object. * * @cache:      The cache. * @max_size:   Maximum size (number of entries) for the cache. *              Use 0 for unlimited size, it's the user's responsibility to *              trim the cache in that case. */void btrfs_lru_cache_init(struct btrfs_lru_cache *cache, unsigned int max_size){	INIT_LIST_HEAD(&cache->lru_list);	mt_init(&cache->entries);	cache->size = 0;	cache->max_size = max_size;} static struct btrfs_lru_cache_entry *match_entry(struct list_head *head, u64 key,						 u64 gen){	struct btrfs_lru_cache_entry *entry; 	list_for_each_entry(entry, head, list) {		if (entry->key == key && entry->gen == gen)			return entry;	} 	return NULL;} /* * Lookup for an entry in the cache. * * @cache:      The cache. * @key:        The key of the entry we are looking for. * @gen:        Generation associated to the key. * * Returns the entry associated with the key or NULL if none found. */struct btrfs_lru_cache_entry *btrfs_lru_cache_lookup(struct btrfs_lru_cache *cache,						     u64 key, u64 gen){	struct list_head *head;	struct btrfs_lru_cache_entry *entry; 	head = mtree_load(&cache->entries, key);	if (!head)		return NULL; 	entry = match_entry(head, key, gen);	if (entry)		list_move_tail(&entry->lru_list, &cache->lru_list); 	return entry;} /* * Remove an entry from the cache. * * @cache:     The cache to remove from. * @entry:     The entry to remove from the cache. * * Note: this also frees the memory used by the entry. */void btrfs_lru_cache_remove(struct btrfs_lru_cache *cache,			    struct btrfs_lru_cache_entry *entry){	struct list_head *prev = entry->list.prev; 	ASSERT(cache->size > 0);	ASSERT(!mtree_empty(&cache->entries)); 	list_del(&entry->list);	list_del(&entry->lru_list); 	if (list_empty(prev)) {		struct list_head *head; 		/*		 * If previous element in the list entry->list is now empty, it		 * means it's a head entry not pointing to any cached entries,		 * so remove it from the maple tree and free it.		 */		head = mtree_erase(&cache->entries, entry->key);		ASSERT(head == prev);		kfree(head);	} 	kfree(entry);	cache->size--;} /* * Store an entry in the cache. * * @cache:      The cache. * @entry:      The entry to store. * * Returns 0 on success and < 0 on error. */int btrfs_lru_cache_store(struct btrfs_lru_cache *cache,			  struct btrfs_lru_cache_entry *new_entry,			  gfp_t gfp){	const u64 key = new_entry->key;	struct list_head *head;	int ret; 	head = kmalloc_obj(*head, gfp);	if (!head)		return -ENOMEM; 	ret = mtree_insert(&cache->entries, key, head, gfp);	if (ret == 0) {		INIT_LIST_HEAD(head);		list_add_tail(&new_entry->list, head);	} else if (ret == -EEXIST) {		kfree(head);		head = mtree_load(&cache->entries, key);		ASSERT(head != NULL);		if (match_entry(head, key, new_entry->gen) != NULL)			return -EEXIST;		list_add_tail(&new_entry->list, head);	} else if (ret < 0) {		kfree(head);		return ret;	} 	if (cache->max_size > 0 && cache->size == cache->max_size) {		struct btrfs_lru_cache_entry *lru_entry; 		lru_entry = list_first_entry(&cache->lru_list,					     struct btrfs_lru_cache_entry,					     lru_list);		btrfs_lru_cache_remove(cache, lru_entry);	} 	list_add_tail(&new_entry->lru_list, &cache->lru_list);	cache->size++; 	return 0;} /* * Empty a cache. * * @cache:     The cache to empty. * * Removes all entries from the cache. */void btrfs_lru_cache_clear(struct btrfs_lru_cache *cache){	struct btrfs_lru_cache_entry *entry;	struct btrfs_lru_cache_entry *tmp; 	list_for_each_entry_safe(entry, tmp, &cache->lru_list, lru_list)		btrfs_lru_cache_remove(cache, entry); 	ASSERT(cache->size == 0);	ASSERT(mtree_empty(&cache->entries));}