From patchwork Sat Mar 10 18:18:58 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andiry Xu X-Patchwork-Id: 10273993 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id EEDF8601A0 for ; Sat, 10 Mar 2018 18:22:04 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id DCD5F29106 for ; Sat, 10 Mar 2018 18:22:04 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id D1AE629735; Sat, 10 Mar 2018 18:22:04 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-1.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_NONE,T_DKIM_INVALID autolearn=no version=3.3.1 Received: from ml01.01.org (ml01.01.org [198.145.21.10]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 65A0929106 for ; Sat, 10 Mar 2018 18:22:04 +0000 (UTC) Received: from [127.0.0.1] (localhost [IPv6:::1]) by ml01.01.org (Postfix) with ESMTP id B34212264D228; Sat, 10 Mar 2018 10:15:32 -0800 (PST) X-Original-To: linux-nvdimm@lists.01.org Delivered-To: linux-nvdimm@lists.01.org Received-SPF: Pass (sender SPF authorized) identity=mailfrom; client-ip=2607:f8b0:400e:c05::243; helo=mail-pg0-x243.google.com; envelope-from=jix024@eng.ucsd.edu; receiver=linux-nvdimm@lists.01.org Received: from mail-pg0-x243.google.com (mail-pg0-x243.google.com [IPv6:2607:f8b0:400e:c05::243]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ml01.01.org (Postfix) with ESMTPS id 107D22264D228 for ; Sat, 10 Mar 2018 10:15:31 -0800 (PST) Received: by mail-pg0-x243.google.com with SMTP id m19so4838076pgn.1 for ; Sat, 10 Mar 2018 10:21:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=eng.ucsd.edu; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=lv/OoL4mFuRuLNzcn7BlVnCpaBx4ZddnUH2AItpJTZk=; b=fT5nsxPtfjatVns4Q1DpTIOcQN+GXyX3hdtehVCKkOMmbn1jIJXIRG0eEiDLmaY5WW 8RMlsx6/8JA7ALEpaH/xewERhiwyGOKDX622lpZmNNVXZI6Ay2huaZOzohOaIvO0bvVL gIEfcli0p79zC0kG+HI6i3NC6LAIfWTO+R+GQ= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=lv/OoL4mFuRuLNzcn7BlVnCpaBx4ZddnUH2AItpJTZk=; b=H5jTYzjXABK8MFBsrvdJj3YH3cePDNXeXaGTTJkTMtFs+GGEtTPDykQ1J64hAXCXjd RtNECSYAoMkertcq+1fmq3yJ6gW8pqOqp2J/Zal/u/DhVINu27fkK2qgWtAHMJ6RSJ8A sbsxWMBCZDQKkeCuH/U+j/e7wwFVPHCIKMZIMl/AAyipThvxSxtek8MR9Ld3KgTL9VQY Sx96N1H/AjQ3GmYe4d3BsdALTg0G+K4c0m7SjuQ6FWAmO/6QzbROV+MyDPyrLfS2XpkJ YByYLtIpXmvbeRQJuYFSMcQdtVJt/PeDHQrGMCyt/RQBf+ykVA//HqWueTBynA8rhBAN sZ9Q== X-Gm-Message-State: AElRT7GiZuPU5ufu3SnyWnk3hzCOoq3ZIJ7D10cCptXs33mEhq9ZvDem 4hMUIa0d3hLwXkHWr+wqCVHZXg== X-Google-Smtp-Source: AG47ELvrjf7y9MX6Z2iOsENK8KWJjBDClmYArCXQ/8UIwjTFaC8Ll8ARmmqijhn8tBkmeKsHVMFMvw== X-Received: by 10.167.131.135 with SMTP id u7mr2684807pfm.50.1520706109450; Sat, 10 Mar 2018 10:21:49 -0800 (PST) Received: from brienza-desktop.8.8.4.4 (andxu.ucsd.edu. [132.239.17.134]) by smtp.gmail.com with ESMTPSA id h80sm9210167pfj.181.2018.03.10.10.21.48 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sat, 10 Mar 2018 10:21:48 -0800 (PST) From: Andiry Xu To: linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org, linux-nvdimm@lists.01.org Subject: [RFC v2 77/83] GC: Fast garbage collection. Date: Sat, 10 Mar 2018 10:18:58 -0800 Message-Id: <1520705944-6723-78-git-send-email-jix024@eng.ucsd.edu> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1520705944-6723-1-git-send-email-jix024@eng.ucsd.edu> References: <1520705944-6723-1-git-send-email-jix024@eng.ucsd.edu> X-BeenThere: linux-nvdimm@lists.01.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "Linux-nvdimm developer list." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: coughlan@redhat.com, miklos@szeredi.hu, Andiry Xu , david@fromorbit.com, jack@suse.com, swanson@cs.ucsd.edu, swhiteho@redhat.com, andiry.xu@gmail.com MIME-Version: 1.0 Errors-To: linux-nvdimm-bounces@lists.01.org Sender: "Linux-nvdimm" X-Virus-Scanned: ClamAV using ClamSMTP From: Andiry Xu 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 --- 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 + * Copyright 2012-2013 Intel Corporation + * Copyright 2009-2011 Marco Stornelli + * 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