diff options
Diffstat (limited to 'fs/f2fs/cache.c')
| -rw-r--r-- | fs/f2fs/cache.c | 720 |
1 files changed, 720 insertions, 0 deletions
diff --git a/fs/f2fs/cache.c b/fs/f2fs/cache.c new file mode 100644 index 000000000000..38fc5eb17f92 --- /dev/null +++ b/fs/f2fs/cache.c @@ -0,0 +1,720 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Copyright (c) 2026 Google LLC + * Author: Chao Yu <chaseyu@google.com> + */ +#include <linux/fs.h> +#include <linux/f2fs_fs.h> +#include <linux/radix-tree.h> +#include <linux/slab.h> +#include <linux/list.h> +#include <linux/pagemap.h> +#include <linux/kthread.h> +#include <linux/freezer.h> +#include <linux/delay.h> +#include "f2fs.h" +#include "cache.h" +#include "node.h" +#include <trace/events/f2fs.h> +#include "segment.h" + +void f2fs_cache_wait_writeback_cond(struct f2fs_cached_block *entry, + enum page_type type) +{ + /* in case the entry was truncated or on-going shrink */ + if (!entry->cache) + return; + + if (!f2fs_cache_test_writeback(entry)) + return; + + /* submit cached bio */ + f2fs_submit_merged_write_cache(entry->cache->sbi, entry, 0, type); + + wait_on_bit_io(&entry->state, F2FS_BLOCK_WRITEBACK, + TASK_UNINTERRUPTIBLE); +} + +void f2fs_cache_wait_writeback(struct f2fs_cached_block *entry) +{ + /* in case the entry was truncated or on-going shrink */ + if (!entry->cache) + return; + + f2fs_cache_wait_writeback_cond(entry, + IS_META_CACHE(entry->cache) ? META : NODE); +} + +void f2fs_cache_update_tag(struct f2fs_cached_block *entry, + unsigned int clear_from, unsigned int set_to) +{ + struct f2fs_cached_block_list *cache = entry->cache; + unsigned long flags; + + spin_lock_irqsave(&cache->tree_lock, flags); + if (clear_from != F2FS_CACHE_TAG_NONE) + radix_tree_tag_clear(&cache->root, entry->index, clear_from); + if (set_to != F2FS_CACHE_TAG_NONE) + radix_tree_tag_set(&cache->root, entry->index, set_to); + spin_unlock_irqrestore(&cache->tree_lock, flags); +} + +bool f2fs_mark_cache_dirty(struct f2fs_cached_block *entry) +{ + struct f2fs_cached_block_list *cache = entry->cache; + + f2fs_cache_set_uptodate(entry); + +#ifdef CONFIG_F2FS_CHECK_FS + if (f2fs_is_node_cache(entry) && IS_INODE(cache->sbi, entry)) + f2fs_inode_chksum_set(cache->sbi, entry); +#endif + + if (!f2fs_cache_test_and_set_dirty(entry)) { + enum count_type type = IS_META_CACHE(cache) ? + F2FS_DIRTY_META : F2FS_DIRTY_NODES; + + trace_f2fs_cache_set_dirty(entry, + IS_META_CACHE(cache) ? META : NODE); + f2fs_cache_update_tag(entry, F2FS_CACHE_TAG_NONE, + F2FS_CACHE_TAG_DIRTY); + inc_cache_count(cache->sbi, type); + return true; + } + + return false; +} + +void f2fs_drop_cache_dirty(struct f2fs_cached_block *entry) +{ + + struct f2fs_cached_block_list *cache = entry->cache; + enum count_type type = IS_META_CACHE(cache) ? + F2FS_DIRTY_META : F2FS_DIRTY_NODES; + + f2fs_cache_clear_uptodate(entry); + + if (!f2fs_cache_test_and_clear_dirty(entry)) + return; + + f2fs_cache_update_tag(entry, F2FS_CACHE_TAG_DIRTY, + F2FS_CACHE_TAG_NONE); + dec_cache_count(cache->sbi, type); +} + +void f2fs_start_cache_writeback(struct f2fs_cached_block *entry) +{ + f2fs_cache_set_writeback(entry); + f2fs_cache_update_tag(entry, F2FS_CACHE_TAG_DIRTY, + F2FS_CACHE_TAG_WRITEBACK); +} + +void f2fs_end_cache_writeback(struct f2fs_cached_block *entry) +{ + /* + * should call f2fs_cache_update_tag() before clearing writeback bit, + * in case f2fs_truncate_cache() set entry->cache to NULL. + */ + f2fs_cache_update_tag(entry, F2FS_CACHE_TAG_WRITEBACK, + F2FS_CACHE_TAG_NONE); + clear_and_wake_up_bit(F2FS_BLOCK_WRITEBACK, &entry->state); +} + +static int f2fs_cache_refcount(struct f2fs_cached_block *entry) +{ + return atomic_read(&entry->refcount); +} + +static void f2fs_do_free_cache(struct f2fs_cached_block *entry) +{ + kfree(entry->data); + kfree(entry); +} + +static void f2fs_free_cache(struct f2fs_cached_block *entry) +{ + WARN_ON_ONCE(!list_empty(&entry->list)); + WARN_ON_ONCE(f2fs_cache_refcount(entry)); + f2fs_do_free_cache(entry); +} + +void f2fs_cache_get(struct f2fs_cached_block *entry) +{ + atomic_inc(&entry->refcount); +} + +static bool f2fs_cache_put(struct f2fs_cached_block *entry) +{ + WARN_ON_ONCE(!f2fs_cache_refcount(entry)); + if (atomic_dec_and_test(&entry->refcount)) { + f2fs_free_cache(entry); + return true; + } + return false; +} + +static struct f2fs_cached_block *f2fs_create_cache( + struct f2fs_cached_block_list *cache, + unsigned long index, bool nofail) +{ + struct f2fs_sb_info *sbi = cache->sbi; + struct f2fs_cached_block *entry; + unsigned int flags = GFP_NOFS; + + if (index == ULONG_MAX) + return ERR_PTR(-ERANGE); + + if (nofail) { + flags |= __GFP_NOFAIL; + entry = kzalloc_obj(*entry, flags); + entry->data = kmalloc(sbi->blocksize, flags); + } else { + entry = f2fs_kzalloc(sbi, sizeof(*entry), flags); + if (!entry) + return ERR_PTR(-ENOMEM); + + entry->data = f2fs_kmalloc(sbi, sbi->blocksize, flags); + if (!entry->data) { + kfree(entry); + return ERR_PTR(-ENOMEM); + } + } + entry->index = index; + + atomic_set(&entry->refcount, 0); + if (!IS_COMPRESS_CACHE(cache)) + entry->next_entry = NULL; + else + entry->ino = 0; + INIT_LIST_HEAD(&entry->list); + + entry->cache = cache; + + return entry; +} + +static struct f2fs_cached_block *f2fs_insert_cache( + struct f2fs_cached_block_list *cache, + unsigned long index, + struct f2fs_cached_block *new) +{ + struct f2fs_cached_block *e; + int ret; + unsigned long flags; + + ret = radix_tree_preload(GFP_NOFS | __GFP_NOFAIL); + f2fs_bug_on(cache->sbi, ret); + + spin_lock(&cache->list_lock); + spin_lock_irqsave(&cache->tree_lock, flags); + e = radix_tree_lookup(&cache->root, index); + if (!e) { + e = new; + f2fs_bug_on(cache->sbi, f2fs_cache_refcount(e)); + + ret = radix_tree_insert(&cache->root, index, e); + f2fs_bug_on(cache->sbi, ret); + + /* radix tree referenced cache entry */ + f2fs_cache_get(e); + f2fs_bug_on(cache->sbi, !list_empty(&e->list)); + list_add_tail(&e->list, &cache->lru_list); + cache->num_entries++; + } + f2fs_cache_get(e); + spin_unlock_irqrestore(&cache->tree_lock, flags); + spin_unlock(&cache->list_lock); + radix_tree_preload_end(); + + if (new != e) { + f2fs_bug_on(cache->sbi, f2fs_cache_refcount(new)); + f2fs_do_free_cache(new); + } + + return e; +} + +struct f2fs_cached_block *f2fs_find_cache( + struct f2fs_cached_block_list *cache, + unsigned long index, + enum f2fs_cache_request_flag rflag) +{ + struct f2fs_cached_block *entry; + unsigned long flags; + bool access = rflag & F2FS_CACHE_ACCESS; + + spin_lock_irqsave(&cache->tree_lock, flags); + entry = radix_tree_lookup(&cache->root, index); + if (entry) { + f2fs_bug_on(cache->sbi, !f2fs_cache_refcount(entry)); + f2fs_cache_get(entry); + if (access && !f2fs_cache_test_referenced(entry)) + f2fs_cache_set_referenced(entry); + } else { + entry = ERR_PTR(-ENOENT); + } + spin_unlock_irqrestore(&cache->tree_lock, flags); + + return entry; +} + +struct f2fs_cached_block *f2fs_grab_cache( + struct f2fs_cached_block_list *cache, + unsigned long index, int flags) + +{ + struct f2fs_cached_block *entry, *new; + bool create = flags & F2FS_CACHE_CREATE; + bool nofail = flags & F2FS_CACHE_NOFAIL; + bool lock = flags & F2FS_CACHE_LOCK; + +repeat: + entry = f2fs_find_cache(cache, index, F2FS_CACHE_ACCESS); + if (!IS_ERR(entry)) + goto found; + + if (!create) + return ERR_PTR(-ENOENT); + + new = f2fs_create_cache(cache, index, nofail); + if (IS_ERR(new)) + return new; + + entry = f2fs_insert_cache(cache, index, new); +found: + if (lock) { + f2fs_lock_cache(entry); + /* has been truncated */ + if (entry->cache != cache) { + f2fs_put_cache(entry, true); + goto repeat; + } + } + return entry; +} + +bool f2fs_trylock_cache(struct f2fs_cached_block *entry) +{ + return !test_and_set_bit(F2FS_BLOCK_LOCKED, &entry->state); +} + +void f2fs_lock_cache(struct f2fs_cached_block *entry) +{ + wait_on_bit_lock(&entry->state, F2FS_BLOCK_LOCKED, + TASK_UNINTERRUPTIBLE); +} + +void f2fs_unlock_cache(struct f2fs_cached_block *entry) +{ + clear_and_wake_up_bit(F2FS_BLOCK_LOCKED, &entry->state); +} + +bool f2fs_put_cache(struct f2fs_cached_block *entry, bool unlock) +{ + if (IS_ERR_OR_NULL(entry)) + return false; + if (unlock) + f2fs_unlock_cache(entry); + return f2fs_cache_put(entry); +} + +unsigned int f2fs_cache_gang_lookup(struct f2fs_cached_block_list *cache, + struct f2fs_cached_block **entries, + pgoff_t *index, unsigned long end) +{ + unsigned long flags; + unsigned int max_nr = min((unsigned long)F2FS_ONSTACK_CACHES, end - *index); + int nr, i; + + if (*index >= end || *index == ULONG_MAX) + return 0; + + spin_lock_irqsave(&cache->tree_lock, flags); + nr = radix_tree_gang_lookup(&cache->root, (void **)entries, + *index, max_nr); + if (!nr) + goto out_unlock; + + for (i = 0; i < nr; i++) { + struct f2fs_cached_block *entry = entries[i]; + + if (entry->index >= end) { + nr = i; + break; + } + f2fs_cache_get(entry); + } + if (nr) + *index = entries[nr - 1]->index + 1; +out_unlock: + spin_unlock_irqrestore(&cache->tree_lock, flags); + return nr; +} + +unsigned int f2fs_cache_gang_lookup_tag(struct f2fs_cached_block_list *cache, + struct f2fs_cached_block **entries, + pgoff_t *index, unsigned int max_nr, + int tag) +{ + unsigned long flags; + int nr, i; + + if (*index == ULONG_MAX) + return 0; + + spin_lock_irqsave(&cache->tree_lock, flags); + nr = radix_tree_gang_lookup_tag(&cache->root, (void **)entries, + *index, max_nr, tag); + if (!nr) + goto out; + + for (i = 0; i < nr; i++) + f2fs_cache_get(entries[i]); + *index = entries[nr - 1]->index + 1; +out: + spin_unlock_irqrestore(&cache->tree_lock, flags); + return nr; +} + +void f2fs_cache_gang_release(struct f2fs_cached_block **entries, + unsigned int nr_entries) +{ + int i; + + for (i = 0; i < nr_entries; i++) + f2fs_put_cache(entries[i], false); +} + +void f2fs_cache_wait_on_all_writeback(struct f2fs_cached_block_list *cache) +{ + unsigned long index = 0; + struct f2fs_cached_block *entries[F2FS_ONSTACK_CACHES]; + int nr, i; + +next: + nr = f2fs_cache_gang_lookup_tag(cache, entries, &index, + F2FS_ONSTACK_CACHES, F2FS_CACHE_TAG_WRITEBACK); + if (!nr) + return; + + for (i = 0; i < nr; i++) + f2fs_cache_wait_writeback(entries[i]); + f2fs_cache_gang_release(entries, nr); + + cond_resched(); + goto next; +} + +static void f2fs_do_truncate_cache(struct f2fs_cached_block *entry, + bool drop_dirty) +{ + struct f2fs_cached_block_list *cache = entry->cache; + unsigned long flags; + + if (drop_dirty) + goto drop_it; + + if (f2fs_cache_test_dirty(entry) || + f2fs_cache_test_writeback(entry)) + return; + +drop_it: + f2fs_cache_wait_writeback(entry); + f2fs_drop_cache_dirty(entry); + + spin_lock(&cache->list_lock); + spin_lock_irqsave(&cache->tree_lock, flags); + + f2fs_bug_on(cache->sbi, !entry->cache); + if (!radix_tree_delete(&cache->root, entry->index)) + f2fs_bug_on(cache->sbi, !entry->cache); + + entry->cache = NULL; + cache->num_entries--; + + atomic_dec(&entry->refcount); + f2fs_bug_on(cache->sbi, !f2fs_cache_refcount(entry)); + + f2fs_bug_on(cache->sbi, list_empty(&entry->list)); + list_del_init(&entry->list); + + spin_unlock_irqrestore(&cache->tree_lock, flags); + spin_unlock(&cache->list_lock); +} + +void f2fs_truncate_locked_cache(struct f2fs_cached_block *entry, + bool drop_dirty) +{ + if (!entry->cache) + return; + f2fs_do_truncate_cache(entry, drop_dirty); +} + +void f2fs_truncate_cache(struct f2fs_cached_block *entry, bool drop_dirty) +{ + f2fs_lock_cache(entry); + f2fs_truncate_locked_cache(entry, drop_dirty); + f2fs_unlock_cache(entry); +} + +static void f2fs_drop_cache(struct f2fs_cached_block_list *cache, + block_t blkaddr, bool drop_dirty) +{ + struct f2fs_cached_block *entry; + + entry = f2fs_find_cache(cache, blkaddr, 0); + if (IS_ERR(entry)) + return; + + f2fs_truncate_cache(entry, drop_dirty); + f2fs_put_cache(entry, false); +} + +void f2fs_drop_cache_range(struct f2fs_cached_block_list *cache, + unsigned long start, unsigned long len, bool drop_dirty) +{ + unsigned long index = start; + unsigned long end = (ULONG_MAX - start < len) ? + ULONG_MAX : (start + len); + struct f2fs_cached_block *entries[F2FS_ONSTACK_CACHES]; + int nr, i; + + if (len == 1) + return f2fs_drop_cache(cache, index, drop_dirty); + +next: + nr = f2fs_cache_gang_lookup(cache, entries, &index, end); + if (!nr) + return; + + for (i = 0; i < nr; i++) + f2fs_truncate_cache(entries[i], drop_dirty); + f2fs_cache_gang_release(entries, nr); + + if (index < end) { + cond_resched(); + goto next; + } +} + +int f2fs_init_cache(struct f2fs_sb_info *sbi, + struct f2fs_cached_block_list *cache, + enum f2fs_cache_type type) +{ + cache->sbi = sbi; + cache->type = type; + INIT_RADIX_TREE(&cache->root, GFP_ATOMIC); + spin_lock_init(&cache->tree_lock); + spin_lock_init(&cache->list_lock); + INIT_LIST_HEAD(&cache->lru_list); + cache->num_entries = 0; + + return 0; +} + +void f2fs_destroy_cache(struct f2fs_cached_block_list *cache) +{ + struct list_head *head = &cache->lru_list; + struct f2fs_cached_block *entry; + unsigned long flags; + + f2fs_cache_wait_on_all_writeback(cache); +next: + spin_lock(&cache->list_lock); + if (list_empty(head)) { + spin_unlock(&cache->list_lock); + return; + } + entry = list_first_entry(head, struct f2fs_cached_block, list); + + spin_lock_irqsave(&cache->tree_lock, flags); + radix_tree_delete(&cache->root, entry->index); + cache->num_entries--; + list_del_init(&entry->list); + spin_unlock_irqrestore(&cache->tree_lock, flags); + + spin_unlock(&cache->list_lock); + + /* wait on read cache IO */ + f2fs_lock_cache(entry); + /* wait on write cache IO */ + f2fs_cache_wait_writeback(entry); + f2fs_bug_on(cache->sbi, f2fs_cache_test_dirty(entry)); + f2fs_bug_on(cache->sbi, f2fs_cache_test_writeback(entry)); + f2fs_bug_on(cache->sbi, !list_empty(&entry->list)); + f2fs_bug_on(cache->sbi, f2fs_cache_refcount(entry) != 1); + f2fs_put_cache(entry, true); + goto next; +} + +static unsigned long f2fs_do_shrink_cache(struct f2fs_cached_block_list *cache, + unsigned long nr_to_scan) +{ + struct f2fs_cached_block *entry, *next; + LIST_HEAD(dispose_list); + LIST_HEAD(keep_list); + unsigned long freed = 0; + unsigned long scanned = 0; + + /* Phase 1: Isolate candidate entries from LRU list into dispose_list */ + spin_lock(&cache->list_lock); + list_for_each_entry_safe(entry, next, &cache->lru_list, list) { + if (scanned >= cache->num_entries) + break; + if (scanned++ >= nr_to_scan) + break; + + /* If accessed, give it a second chance to rotate to tail */ + if (f2fs_cache_test_and_clear_referenced(entry)) { + list_move_tail(&entry->list, &cache->lru_list); + continue; + } + + if (f2fs_cache_test_dirty(entry) || + f2fs_cache_test_writeback(entry) || + f2fs_cache_test_locked(entry)) + continue; + + if (f2fs_cache_refcount(entry) != 1) + continue; + + list_move_tail(&entry->list, &dispose_list); + } + spin_unlock(&cache->list_lock); + + /* Phase 2: Process isolated candidates one by one */ + while (1) { + spin_lock(&cache->list_lock); + entry = list_first_entry_or_null(&dispose_list, + struct f2fs_cached_block, list); + if (!entry) { + spin_unlock(&cache->list_lock); + break; + } + f2fs_cache_get(entry); + list_move_tail(&entry->list, &keep_list); + spin_unlock(&cache->list_lock); + + if (!f2fs_trylock_cache(entry)) { + f2fs_put_cache(entry, false); + continue; + } + + /* the entry has been truncated */ + if (!entry->cache) { + f2fs_put_cache(entry, true); + continue; + } + /* + * at least there are shrinker, radix tree and another user + * has referenced the entry. + */ + if (f2fs_cache_refcount(entry) >= 3) { + f2fs_put_cache(entry, true); + continue; + } + + f2fs_do_truncate_cache(entry, false); + + if (f2fs_put_cache(entry, true)) + freed++; + } + + /* Phase 3: Splice un-reclaimed entries back onto cache->lru_list */ + if (!list_empty(&keep_list)) { + spin_lock(&cache->list_lock); + list_splice_tail(&keep_list, &cache->lru_list); + spin_unlock(&cache->list_lock); + } + + return freed; +} + +unsigned long f2fs_shrink_cache(struct f2fs_sb_info *sbi, + unsigned long nr_to_scan) +{ + unsigned long freed; + + freed = f2fs_do_shrink_cache(META_CACHE(sbi), nr_to_scan); + if (freed >= nr_to_scan) + return freed; + + freed += f2fs_do_shrink_cache(NODE_CACHE(sbi), nr_to_scan - freed); + if (freed >= nr_to_scan) + return freed; + + freed += f2fs_do_shrink_cache(COMPRESS_CACHE(sbi), nr_to_scan - freed); + return freed; +} + +static int f2fs_cache_writeback_kthread(void *data) +{ + struct f2fs_sb_info *sbi = data; + struct f2fs_cache_kthread *cache_thread = &sbi->cache_thread; + wait_queue_head_t *wq = &cache_thread->cache_wb_wq; + + set_freezable(); + + while (!kthread_should_stop()) { + unsigned int interval = cache_thread->cache_wb_interval; + + wait_event_freezable_timeout(*wq, + kthread_should_stop(), + msecs_to_jiffies(interval)); + + if (kthread_should_stop()) + break; + + if (f2fs_readonly(sbi->sb)) + continue; + + if (f2fs_cp_error(sbi)) + continue; + + if (unlikely(freezing(current))) + continue; + + if (!sb_start_write_trylock(sbi->sb)) + continue; + + f2fs_write_meta_caches(sbi); + f2fs_write_node_caches(sbi); + + sb_end_write(sbi->sb); + } + return 0; +} + +int f2fs_start_cache_wb_thread(struct f2fs_sb_info *sbi) +{ + struct f2fs_cache_kthread *cache_thread = &sbi->cache_thread; + struct task_struct *task; + dev_t dev = sbi->sb->s_dev; + char name[36]; + + if (cache_thread->cache_wb_task) + return 0; + + init_waitqueue_head(&cache_thread->cache_wb_wq); + cache_thread->cache_wb_interval = DEF_DIRTY_CACHE_TIMEOUT; + snprintf(name, sizeof(name), "f2fs_writeback-%u:%u", + MAJOR(dev), MINOR(dev)); + + task = kthread_run(f2fs_cache_writeback_kthread, sbi, "%s", name); + if (IS_ERR(task)) + return PTR_ERR(task); + + cache_thread->cache_wb_task = task; + return 0; +} + +void f2fs_stop_cache_wb_thread(struct f2fs_sb_info *sbi) +{ + struct f2fs_cache_kthread *cache_thread = &sbi->cache_thread; + + if (!cache_thread->cache_wb_task) + return; + + kthread_stop(cache_thread->cache_wb_task); + cache_thread->cache_wb_task = NULL; +} |