Quelle  lru_cache.c   Sprache: C

// 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(sizeof(*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));
}