Line data    Source code

       1             : // SPDX-License-Identifier: GPL-2.0
       2             : 
       3             : #include <linux/mm.h>
       4             : #include "lru_cache.h"
       5             : #include "messages.h"
       6             : 
       7             : /*
       8             :  * Initialize a cache object.
       9             :  *
      10             :  * @cache:      The cache.
      11             :  * @max_size:   Maximum size (number of entries) for the cache.
      12             :  *              Use 0 for unlimited size, it's the user's responsability to
      13             :  *              trim the cache in that case.
      14             :  */
      15           0 : void btrfs_lru_cache_init(struct btrfs_lru_cache *cache, unsigned int max_size)
      16             : {
      17           0 :         INIT_LIST_HEAD(&cache->lru_list);
      18           0 :         mt_init(&cache->entries);
      19           0 :         cache->size = 0;
      20           0 :         cache->max_size = max_size;
      21           0 : }
      22             : 
      23           0 : static struct btrfs_lru_cache_entry *match_entry(struct list_head *head, u64 key,
      24             :                                                  u64 gen)
      25             : {
      26           0 :         struct btrfs_lru_cache_entry *entry;
      27             : 
      28           0 :         list_for_each_entry(entry, head, list) {
      29           0 :                 if (entry->key == key && entry->gen == gen)
      30           0 :                         return entry;
      31             :         }
      32             : 
      33             :         return NULL;
      34             : }
      35             : 
      36             : /*
      37             :  * Lookup for an entry in the cache.
      38             :  *
      39             :  * @cache:      The cache.
      40             :  * @key:        The key of the entry we are looking for.
      41             :  * @gen:        Generation associated to the key.
      42             :  *
      43             :  * Returns the entry associated with the key or NULL if none found.
      44             :  */
      45           0 : struct btrfs_lru_cache_entry *btrfs_lru_cache_lookup(struct btrfs_lru_cache *cache,
      46             :                                                      u64 key, u64 gen)
      47             : {
      48           0 :         struct list_head *head;
      49           0 :         struct btrfs_lru_cache_entry *entry;
      50             : 
      51           0 :         head = mtree_load(&cache->entries, key);
      52           0 :         if (!head)
      53             :                 return NULL;
      54             : 
      55           0 :         entry = match_entry(head, key, gen);
      56           0 :         if (entry)
      57           0 :                 list_move_tail(&entry->lru_list, &cache->lru_list);
      58             : 
      59             :         return entry;
      60             : }
      61             : 
      62             : /*
      63             :  * Remove an entry from the cache.
      64             :  *
      65             :  * @cache:     The cache to remove from.
      66             :  * @entry:     The entry to remove from the cache.
      67             :  *
      68             :  * Note: this also frees the memory used by the entry.
      69             :  */
      70           0 : void btrfs_lru_cache_remove(struct btrfs_lru_cache *cache,
      71             :                             struct btrfs_lru_cache_entry *entry)
      72             : {
      73           0 :         struct list_head *prev = entry->list.prev;
      74             : 
      75           0 :         ASSERT(cache->size > 0);
      76           0 :         ASSERT(!mtree_empty(&cache->entries));
      77             : 
      78           0 :         list_del(&entry->list);
      79           0 :         list_del(&entry->lru_list);
      80             : 
      81           0 :         if (list_empty(prev)) {
      82           0 :                 struct list_head *head;
      83             : 
      84             :                 /*
      85             :                  * If previous element in the list entry->list is now empty, it
      86             :                  * means it's a head entry not pointing to any cached entries,
      87             :                  * so remove it from the maple tree and free it.
      88             :                  */
      89           0 :                 head = mtree_erase(&cache->entries, entry->key);
      90           0 :                 ASSERT(head == prev);
      91           0 :                 kfree(head);
      92             :         }
      93             : 
      94           0 :         kfree(entry);
      95           0 :         cache->size--;
      96           0 : }
      97             : 
      98             : /*
      99             :  * Store an entry in the cache.
     100             :  *
     101             :  * @cache:      The cache.
     102             :  * @entry:      The entry to store.
     103             :  *
     104             :  * Returns 0 on success and < 0 on error.
     105             :  */
     106           0 : int btrfs_lru_cache_store(struct btrfs_lru_cache *cache,
     107             :                           struct btrfs_lru_cache_entry *new_entry,
     108             :                           gfp_t gfp)
     109             : {
     110           0 :         const u64 key = new_entry->key;
     111           0 :         struct list_head *head;
     112           0 :         int ret;
     113             : 
     114           0 :         head = kmalloc(sizeof(*head), gfp);
     115           0 :         if (!head)
     116             :                 return -ENOMEM;
     117             : 
     118           0 :         ret = mtree_insert(&cache->entries, key, head, gfp);
     119           0 :         if (ret == 0) {
     120           0 :                 INIT_LIST_HEAD(head);
     121           0 :                 list_add_tail(&new_entry->list, head);
     122           0 :         } else if (ret == -EEXIST) {
     123           0 :                 kfree(head);
     124           0 :                 head = mtree_load(&cache->entries, key);
     125           0 :                 ASSERT(head != NULL);
     126           0 :                 if (match_entry(head, key, new_entry->gen) != NULL)
     127             :                         return -EEXIST;
     128           0 :                 list_add_tail(&new_entry->list, head);
     129           0 :         } else if (ret < 0) {
     130           0 :                 kfree(head);
     131           0 :                 return ret;
     132             :         }
     133             : 
     134           0 :         if (cache->max_size > 0 && cache->size == cache->max_size) {
     135           0 :                 struct btrfs_lru_cache_entry *lru_entry;
     136             : 
     137           0 :                 lru_entry = list_first_entry(&cache->lru_list,
     138             :                                              struct btrfs_lru_cache_entry,
     139             :                                              lru_list);
     140           0 :                 btrfs_lru_cache_remove(cache, lru_entry);
     141             :         }
     142             : 
     143           0 :         list_add_tail(&new_entry->lru_list, &cache->lru_list);
     144           0 :         cache->size++;
     145             : 
     146           0 :         return 0;
     147             : }
     148             : 
     149             : /*
     150             :  * Empty a cache.
     151             :  *
     152             :  * @cache:     The cache to empty.
     153             :  *
     154             :  * Removes all entries from the cache.
     155             :  */
     156           0 : void btrfs_lru_cache_clear(struct btrfs_lru_cache *cache)
     157             : {
     158           0 :         struct btrfs_lru_cache_entry *entry;
     159           0 :         struct btrfs_lru_cache_entry *tmp;
     160             : 
     161           0 :         list_for_each_entry_safe(entry, tmp, &cache->lru_list, lru_list)
     162           0 :                 btrfs_lru_cache_remove(cache, entry);
     163             : 
     164           0 :         ASSERT(cache->size == 0);
     165           0 :         ASSERT(mtree_empty(&cache->entries));
     166           0 : }