lkml.org 
[lkml]   [2018]   [Mar]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[RFC v2 77/83] GC: Fast garbage collection.
    Date
    From: Andiry Xu <jix024@cs.ucsd.edu>

    NOVA cleans and compacts the log when the log is full.
    The log is a linked list of 4KB pmem pages, and NOVA performs
    fast garbage collection by deleting dead log pages (all the entries are invalid)
    from the linked list.

    Example:
    I = Invalid, V = Valid

    VIIV -> IIII -> VVII

    ||
    || fast gc
    \/

    VIIV -> VVII

    Signed-off-by: Andiry Xu <jix024@cs.ucsd.edu>
    ---
    fs/nova/Makefile | 2 +-
    fs/nova/gc.c | 186 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
    fs/nova/log.c | 3 +
    fs/nova/nova.h | 7 +++
    4 files changed, 197 insertions(+), 1 deletion(-)
    create mode 100644 fs/nova/gc.c

    diff --git a/fs/nova/Makefile b/fs/nova/Makefile
    index 87e56c6..7a5fb6d 100644
    --- a/fs/nova/Makefile
    +++ b/fs/nova/Makefile
    @@ -4,5 +4,5 @@

    obj-$(CONFIG_NOVA_FS) += nova.o

    -nova-y := balloc.o bbuild.o dax.o dir.o file.o inode.o ioctl.o journal.o\
    +nova-y := balloc.o bbuild.o dax.o dir.o file.o gc.o inode.o ioctl.o journal.o\
    log.o namei.o rebuild.o stats.o super.o symlink.o
    diff --git a/fs/nova/gc.c b/fs/nova/gc.c
    new file mode 100644
    index 0000000..1634c04
    --- /dev/null
    +++ b/fs/nova/gc.c
    @@ -0,0 +1,186 @@
    +/*
    + * BRIEF DESCRIPTION
    + *
    + * Garbage collection methods
    + *
    + * Copyright 2015-2016 Regents of the University of California,
    + * UCSD Non-Volatile Systems Lab, Andiry Xu <jix024@cs.ucsd.edu>
    + * Copyright 2012-2013 Intel Corporation
    + * Copyright 2009-2011 Marco Stornelli <marco.stornelli@gmail.com>
    + * Copyright 2003 Sony Corporation
    + * Copyright 2003 Matsushita Electric Industrial Co., Ltd.
    + * 2003-2004 (c) MontaVista Software, Inc. , Steve Longerbeam
    + * This file is licensed under the terms of the GNU General Public
    + * License version 2. This program is licensed "as is" without any
    + * warranty of any kind, whether express or implied.
    + */
    +
    +#include "nova.h"
    +#include "inode.h"
    +
    +
    +static bool curr_page_invalid(struct super_block *sb,
    + struct nova_inode *pi, struct nova_inode_info_header *sih,
    + u64 page_head)
    +{
    + struct nova_inode_log_page *curr_page;
    + struct nova_inode_page_tail page_tail;
    + unsigned int num_entries;
    + unsigned int invalid_entries;
    + bool ret;
    + timing_t check_time;
    + int rc;
    +
    + NOVA_START_TIMING(check_invalid_t, check_time);
    +
    + curr_page = (struct nova_inode_log_page *)
    + nova_get_block(sb, page_head);
    + rc = memcpy_mcsafe(&page_tail, &curr_page->page_tail,
    + sizeof(struct nova_inode_page_tail));
    + if (rc) {
    + nova_err(sb, "check page failed\n");
    + return false;
    + }
    +
    + num_entries = le32_to_cpu(page_tail.num_entries);
    + invalid_entries = le32_to_cpu(page_tail.invalid_entries);
    +
    + ret = (invalid_entries == num_entries);
    + if (!ret) {
    + sih->num_entries += num_entries;
    + sih->valid_entries += num_entries - invalid_entries;
    + }
    +
    + NOVA_END_TIMING(check_invalid_t, check_time);
    + return ret;
    +}
    +
    +static void free_curr_page(struct super_block *sb,
    + struct nova_inode_info_header *sih,
    + struct nova_inode_log_page *curr_page,
    + struct nova_inode_log_page *last_page, u64 curr_head)
    +{
    + u8 btype = sih->i_blk_type;
    +
    + nova_set_next_page_address(sb, last_page,
    + curr_page->page_tail.next_page, 1);
    + nova_free_log_blocks(sb, sih,
    + nova_get_blocknr(sb, curr_head, btype), 1);
    +}
    +
    +
    +/*
    + * Scan pages in the log and remove those with no valid log entries.
    + */
    +int nova_inode_log_fast_gc(struct super_block *sb,
    + struct nova_inode *pi, struct nova_inode_info_header *sih,
    + u64 curr_tail, u64 new_block,
    + int num_pages, int force_thorough)
    +{
    + u64 curr, next, possible_head = 0;
    + int found_head = 0;
    + struct nova_inode_log_page *last_page = NULL;
    + struct nova_inode_log_page *curr_page = NULL;
    + int first_need_free = 0;
    + int num_logs;
    + u8 btype = sih->i_blk_type;
    + unsigned long blocks;
    + unsigned long checked_pages = 0;
    + int freed_pages = 0;
    + timing_t gc_time;
    +
    + NOVA_START_TIMING(fast_gc_t, gc_time);
    + curr = sih->log_head;
    + sih->valid_entries = 0;
    + sih->num_entries = 0;
    +
    + num_logs = 1;
    +
    + nova_dbgv("%s: log head 0x%llx, tail 0x%llx\n",
    + __func__, curr, curr_tail);
    + while (1) {
    + if (curr >> PAGE_SHIFT == sih->log_tail >> PAGE_SHIFT) {
    + /* Don't recycle tail page */
    + if (found_head == 0) {
    + possible_head = cpu_to_le64(curr);
    + }
    + break;
    + }
    +
    + curr_page = (struct nova_inode_log_page *)
    + nova_get_block(sb, curr);
    + next = next_log_page(sb, curr);
    + if (next < 0)
    + break;
    +
    + nova_dbg_verbose("curr 0x%llx, next 0x%llx\n", curr, next);
    + if (curr_page_invalid(sb, pi, sih, curr)) {
    + nova_dbg_verbose("curr page %p invalid\n", curr_page);
    + if (curr == sih->log_head) {
    + /* Free first page later */
    + first_need_free = 1;
    + last_page = curr_page;
    + } else {
    + nova_dbg_verbose("Free log block 0x%llx\n",
    + curr >> PAGE_SHIFT);
    + free_curr_page(sb, sih, curr_page, last_page,
    + curr);
    + }
    + NOVA_STATS_ADD(fast_gc_pages, 1);
    + freed_pages++;
    + } else {
    + if (found_head == 0) {
    + possible_head = cpu_to_le64(curr);
    + found_head = 1;
    + }
    + last_page = curr_page;
    + }
    +
    + curr = next;
    + checked_pages++;
    + if (curr == 0)
    + break;
    + }
    +
    + NOVA_STATS_ADD(fast_checked_pages, checked_pages);
    + nova_dbgv("checked pages %lu, freed %d\n", checked_pages, freed_pages);
    + checked_pages -= freed_pages;
    +
    + // TODO: I think this belongs in nova_extend_inode_log.
    + if (num_pages > 0) {
    + curr = BLOCK_OFF(curr_tail);
    + curr_page = (struct nova_inode_log_page *)
    + nova_get_block(sb, curr);
    +
    + nova_set_next_page_address(sb, curr_page, new_block, 1);
    + }
    +
    + curr = sih->log_head;
    +
    + pi->log_head = possible_head;
    + nova_persist_inode(pi);
    + sih->log_head = possible_head;
    + nova_dbgv("%s: %d new head 0x%llx\n", __func__,
    + found_head, possible_head);
    + sih->log_pages += (num_pages - freed_pages) * num_logs;
    + /* Don't update log tail pointer here */
    + nova_flush_buffer(&pi->log_head, CACHELINE_SIZE, 1);
    +
    + if (first_need_free) {
    + nova_dbg_verbose("Free log head block 0x%llx\n",
    + curr >> PAGE_SHIFT);
    + nova_free_log_blocks(sb, sih,
    + nova_get_blocknr(sb, curr, btype), 1);
    + }
    +
    + NOVA_END_TIMING(fast_gc_t, gc_time);
    +
    + if (sih->num_entries == 0)
    + return 0;
    +
    + blocks = (sih->valid_entries * checked_pages) / sih->num_entries;
    + if ((sih->valid_entries * checked_pages) % sih->num_entries)
    + blocks++;
    +
    + return 0;
    +}
    diff --git a/fs/nova/log.c b/fs/nova/log.c
    index 451be27..66bf98e 100644
    --- a/fs/nova/log.c
    +++ b/fs/nova/log.c
    @@ -964,6 +964,9 @@ static u64 nova_extend_inode_log(struct super_block *sb, struct nova_inode *pi,
    }

    /* Perform GC */
    + nova_inode_log_fast_gc(sb, pi, sih, curr_p,
    + new_block, allocated, 0);
    +
    return new_block;
    }

    diff --git a/fs/nova/nova.h b/fs/nova/nova.h
    index ab9153e..32b7b2f 100644
    --- a/fs/nova/nova.h
    +++ b/fs/nova/nova.h
    @@ -515,6 +515,13 @@ int nova_remove_dentry(struct dentry *dentry, int dec_link,
    extern const struct file_operations nova_dax_file_operations;
    extern const struct inode_operations nova_file_inode_operations;

    +
    +/* gc.c */
    +int nova_inode_log_fast_gc(struct super_block *sb,
    + struct nova_inode *pi, struct nova_inode_info_header *sih,
    + u64 curr_tail, u64 new_block, int num_pages,
    + int force_thorough);
    +
    /* ioctl.c */
    extern long nova_ioctl(struct file *filp, unsigned int cmd, unsigned long arg);
    #ifdef CONFIG_COMPAT
    --
    2.7.4
    \
     
     \ /
      Last update: 2018-03-10 19:22    [W:4.158 / U:0.052 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site