Received: by 10.223.185.111 with SMTP id b44csp1641537wrg; Sat, 10 Mar 2018 10:23:28 -0800 (PST) X-Google-Smtp-Source: AG47ELt3WQOo47FkllBwqDJk/LyVVEolhb/RgWf4k08ntJ3oBkQSWXa2EBYoUepNGPKRH9htZhCa X-Received: by 10.99.151.26 with SMTP id n26mr2236758pge.370.1520706207972; Sat, 10 Mar 2018 10:23:27 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1520706207; cv=none; d=google.com; s=arc-20160816; b=vaO8Umgk5W+xcw4LqmWmmBQyB8DXNrSpJSuLPVc7yp8xWjf4o/DtjkZNsZvo3aE1uF QBqTaoZwZaQkmSbozaaElYiyFTidpgtEIGJI/15Ocw00JQSHAqq9Tjg6hMxjShyid9vy 360uV1JsLBXNHVDAK/3m6OuTREAdgMbJvIzBGJco/QND6qznXsDrHVt0slMkiaSfPhxj AW2WgztdTbb+XFGuk+8dqzNAuNH6aydkIdfAM3g6a8p3IByEWs92GfnMbr4OkDdrgSFM h/So09JATk9/pM08mvk/X7qTUOR0Noyltg/h6XWUAEv54jzkOuLZzvyAzxIxH4Jd828y dRTw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:dkim-signature:arc-authentication-results; bh=lv/OoL4mFuRuLNzcn7BlVnCpaBx4ZddnUH2AItpJTZk=; b=YawK8dwCMQDTdSd7zBbsnUyJE9/KUwRO+ymQmUZM/tHCOmscr8xahD8tnI2uJ8FiVI 7u/iDAbBwozCAleUlfgT05AsUtgxMs7Qzyo/BILPvm4I3fiOaZjmegnH51vXl+cddKe2 DEhKH11QUfjb+7Hn4g48VmAH1yGazC8Su46crcTnxAdHP87NcoExBD4Wu24/mF4ZkuES 9YFlWt4JcC/5oBH4AtGlv9xnxYT0WGhSbKqMm+QG4Uv2KgAg1xLM87Pmk/dJurBbX5Vr axVvfKFWPwUnfpBiqccbk+d99Nts/+IoD+7+ajeoyHyUEi5q8I7JKOs1wjZRhrSJvyh3 Q+aQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@eng.ucsd.edu header.s=google header.b=fT5nsxPt; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id i2si704016pgc.818.2018.03.10.10.23.13; Sat, 10 Mar 2018 10:23:27 -0800 (PST) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; dkim=pass header.i=@eng.ucsd.edu header.s=google header.b=fT5nsxPt; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932993AbeCJSWA (ORCPT + 99 others); Sat, 10 Mar 2018 13:22:00 -0500 Received: from mail-pg0-f68.google.com ([74.125.83.68]:35398 "EHLO mail-pg0-f68.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932071AbeCJSVu (ORCPT ); Sat, 10 Mar 2018 13:21:50 -0500 Received: by mail-pg0-f68.google.com with SMTP id l131so4840555pga.2 for ; Sat, 10 Mar 2018 10:21:50 -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=Vmv7XvsumgjsOL9Ze6kJNlo6HWA6txhGsfLCjiU2AARrPqQgPCDlYk4pR7G3A2d+At CeGKT1KBNbhqPOw/24JNapAyPMsjrKeOFMvKPgw0CAKKp8MHqbVn4kFCZ38uDkWmr0zN +nX1ta8qYz+NEKOu2qIXVLFcguZU4CnamJUvQwUfxt8MB9k8WvBOKmqVFDpU5srMZaw2 F1PjgGa2+7J6lPLfqHjxhxXjb1ipds0o29tImeSuBmFN3niNmejDiH74tEUNNm8eN74y fuLXG/iI0zfSkJn/vDkOSI2fA+0pL/75E05e5kOptHnyLzKZwHcvPZj61xlftOgGiQwi 9vfA== X-Gm-Message-State: AElRT7F+5jqTWBRs7D2js+SZUGJSYBUouvMZUDr22kBygzttPQ2e6QnJ n68wmGfzCVOnLk0UFL+9q105FA== 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 Cc: dan.j.williams@intel.com, andy.rudoff@intel.com, coughlan@redhat.com, swanson@cs.ucsd.edu, david@fromorbit.com, jack@suse.com, swhiteho@redhat.com, miklos@szeredi.hu, andiry.xu@gmail.com, Andiry Xu 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> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 -- 2.7.4