Received: by 10.192.245.15 with SMTP id i15csp1147658imn; Sun, 11 Mar 2018 05:16:41 -0700 (PDT) X-Google-Smtp-Source: AG47ELvIWUFalEaXrLuyzR1SI4aCUd1YIyTzDpT5CrH/mCnOpWcJCFco/aapCU4g3hq0Fnz0vAXD X-Received: by 10.101.97.67 with SMTP id o3mr3924838pgv.251.1520770600944; Sun, 11 Mar 2018 05:16:40 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1520770600; cv=none; d=google.com; s=arc-20160816; b=F6t2q7pYIh1F+N/cuGhOYkhX0Pi9dhUPDtoGDP3pZlhjzYkSzcj77NaXmGgT8/VLLH H4+BBew7OAPPHOrvmaP1RX3Cd+Iq94httODVuYUKLgZpJ31XgptYnvZp1mqUcwHi7e+c t7ivZN/2z8+hSt2vdw3jUbVDcmFltZk6USK0RVxJPvOA/PjvZ0Fh64YuZLsSvYP0bRWX q2jtuzFpcSuvNLJ3IcKzn4a9zMKp/pmrGEr57qvORPkmzNxJ3bOpa0sypBeX3aZ1rSGR KS1MKnzHspoNDIwexueCpf7WEn9WAONhj4zndHCD5nBE4ksUD+e+P8I1BKqZl0TNFX4S iZRA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:content-transfer-encoding :content-language:in-reply-to:mime-version:user-agent:date :message-id:from:references:cc:to:subject:dkim-signature :arc-authentication-results; bh=2U/D6+fXdF9d1KdoOWNYQ52l7zP7NYDjavoI8ub1wrY=; b=ECF++GauUK9OWCS1Pq9JGfhsvQfvPWDXCd2U7moRdRnELlPESV/yqC5xaw6p4PkOVU h6el28BpBo9Knk8ZNP87vDFu3bf5gtAGNlM83Q/cx98UFGRYKo959oX80LwiuibpoVrF cqJJw5+hsEKE57d+BwF3PsHEDLMOPRdNWuOQfUtzwkvOaBBio6suqcQDS1yjNKnFMaqj Fo/1Yf21tn7ut8M3SN/nHoml/zYV10O8snvLJbpaeJD3KzlZJRGCI+7vU+4OHXMG/F7x QQ+Dpqpo7QfdcNZ738yxwH1LLta1DYIV2gLZkwKZviYvCH4G2fipOJsUhwyyy5Bd5Ml6 rRiw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=Atcxobgj; 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; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id 11-v6si4279344plc.376.2018.03.11.05.16.15; Sun, 11 Mar 2018 05:16:40 -0700 (PDT) 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=@gmail.com header.s=20161025 header.b=Atcxobgj; 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; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932171AbeCKMMx (ORCPT + 99 others); Sun, 11 Mar 2018 08:12:53 -0400 Received: from mail-pl0-f67.google.com ([209.85.160.67]:46902 "EHLO mail-pl0-f67.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932125AbeCKMMv (ORCPT ); Sun, 11 Mar 2018 08:12:51 -0400 Received: by mail-pl0-f67.google.com with SMTP id f5-v6so212893plj.13; Sun, 11 Mar 2018 05:12:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:to:cc:references:from:message-id:date:user-agent :mime-version:in-reply-to:content-language:content-transfer-encoding; bh=2U/D6+fXdF9d1KdoOWNYQ52l7zP7NYDjavoI8ub1wrY=; b=Atcxobgjv2+9HlJ5UB3U4BP1R1LNYoBF7hNuQm+bkGkw3W2eBH4m84i8VYzujSGirV 9Q/VQ8RmBYHYyhEaQj00KCo/V8J3U438HK2AO96LAfYBCkAQCn3Pap1c9l1BRBlVb7xB IjIafUmT2hijlO2LNhyMvyLG6aBbZZx8io9JenemuxBhyGZAnbPUNax2WOcxxpy4HNbh 7+TZGMYzjgq0p3BaXTzfYCfUzsD8as2cd/wbzzRy9cL0bMmzZTYoJMbRpiJIinUzQleH 3SP5jDs7IwFW0P1CkBlUTAvhqiLB97Gf0KHjxmD/a2t2v3BfTcB+uybj+fKaYKzR+MBK Sgpg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=2U/D6+fXdF9d1KdoOWNYQ52l7zP7NYDjavoI8ub1wrY=; b=Xs+QN/W4H3eOQPrJ9s+fTKB5J3Xgx1RzwpmNr6JDTD/oXGYYqDHhb/g3gNb9ZgrhtJ Vj5DQbWEF9bdM92Jw8f3WHl5guhu5RHQGsWmBCv8kCnJZYDcTIdS4V8SYRvF196V3Mhe zkZkTgnXfUd/uUJaD2IoCOO0E44sZE5bTeJXLgCXqJR5mUtZ8TVyB4lkYwB4tEQlaCqM qDF0/w3kYx7PBXoPtvx1E+l5AHb57w7+T0K+BAsqsa/nkIOpO7cypZpffvI6ulhtnqOu TlVPBKRcj5ZyTxlTwaWNwCpAgv4Cn1XHZaZQN95oo8CBggkmCpbTNRqU19Df57ts/BX3 P+ew== X-Gm-Message-State: AElRT7FVEDS1OOD2BWOHrqcaC1+2+v2RuuvoQLYZd4yeyf7WyuzJL7yb rKF9j+Zg1rf+luCPN6yDBEo= X-Received: by 2002:a17:902:2f43:: with SMTP id s61-v6mr4490271plb.236.1520770370747; Sun, 11 Mar 2018 05:12:50 -0700 (PDT) Received: from [10.20.1.223] (ivokamhome.ddns.nbis.net. [87.120.136.31]) by smtp.gmail.com with ESMTPSA id a67sm10054144pgc.6.2018.03.11.05.12.45 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 11 Mar 2018 05:12:49 -0700 (PDT) Subject: Re: [RFC v2 16/83] Initialize block map and free lists in nova_init(). To: Andiry Xu , 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 References: <1520705944-6723-1-git-send-email-jix024@eng.ucsd.edu> <1520705944-6723-17-git-send-email-jix024@eng.ucsd.edu> From: Nikolay Borisov Message-ID: <3c1e2c80-ad39-c10f-a4c3-9228ebed776e@gmail.com> Date: Sun, 11 Mar 2018 14:12:42 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.6.0 MIME-Version: 1.0 In-Reply-To: <1520705944-6723-17-git-send-email-jix024@eng.ucsd.edu> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 10.03.2018 20:17, Andiry Xu wrote: > From: Andiry Xu > > NOVA divides the pmem range equally among per-CPU free lists, > and format the red-black trees by inserting the initial free range. > > Signed-off-by: Andiry Xu > --- > fs/nova/balloc.c | 161 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ > fs/nova/balloc.h | 13 ++++- > fs/nova/super.c | 2 + > 3 files changed, 175 insertions(+), 1 deletion(-) > > diff --git a/fs/nova/balloc.c b/fs/nova/balloc.c > index 450c942..cb627db 100644 > --- a/fs/nova/balloc.c > +++ b/fs/nova/balloc.c > @@ -55,4 +55,165 @@ void nova_delete_free_lists(struct super_block *sb) > sbi->free_lists = NULL; > } > > +// Initialize a free list. Each CPU gets an equal share of the block space to > +// manage. > +static void nova_init_free_list(struct super_block *sb, > + struct free_list *free_list, int index) > +{ > + struct nova_sb_info *sbi = NOVA_SB(sb); > + unsigned long per_list_blocks; > + > + per_list_blocks = sbi->num_blocks / sbi->cpus; nit: You've already initialised per_list_blocks in nova_init_blockmap, which calls this function. So just reference it, rather than performing the the divison every time > + > + free_list->block_start = per_list_blocks * index; > + free_list->block_end = free_list->block_start + > + per_list_blocks - 1; > + if (index == 0) > + free_list->block_start += sbi->head_reserved_blocks; > + if (index == sbi->cpus - 1) > + free_list->block_end -= sbi->tail_reserved_blocks; > +} > + > +inline struct nova_range_node *nova_alloc_blocknode(struct super_block *sb) > +{ > + return nova_alloc_range_node(sb); > +} > + > +inline void nova_free_blocknode(struct super_block *sb, > + struct nova_range_node *node) > +{ > + nova_free_range_node(node); > +} > + > +void nova_init_blockmap(struct super_block *sb, int recovery) > +{ > + struct nova_sb_info *sbi = NOVA_SB(sb); > + struct rb_root *tree; > + struct nova_range_node *blknode; > + struct free_list *free_list; > + int i; > + int ret; > + > + /* Divide the block range among per-CPU free lists */ > + sbi->per_list_blocks = sbi->num_blocks / sbi->cpus; > + for (i = 0; i < sbi->cpus; i++) { > + free_list = nova_get_free_list(sb, i); > + tree = &(free_list->block_free_tree); > + nova_init_free_list(sb, free_list, i); > + > + /* For recovery, update these fields later */ > + if (recovery == 0) { > + free_list->num_free_blocks = free_list->block_end - > + free_list->block_start + 1; > + > + blknode = nova_alloc_blocknode(sb); > + if (blknode == NULL) > + return; > + blknode->range_low = free_list->block_start; > + blknode->range_high = free_list->block_end; > + ret = nova_insert_blocktree(sbi, tree, blknode); > + if (ret) { > + nova_err(sb, "%s failed\n", __func__); > + nova_free_blocknode(sb, blknode); > + return; > + } > + free_list->first_node = blknode; > + free_list->last_node = blknode; > + free_list->num_blocknode = 1; > + } > + > + nova_dbgv("%s: free list %d: block start %lu, end %lu, %lu free blocks\n", > + __func__, i, > + free_list->block_start, > + free_list->block_end, > + free_list->num_free_blocks); > + } > +} > + > +static inline int nova_rbtree_compare_rangenode(struct nova_range_node *curr, > + unsigned long range_low) > +{ > + if (range_low < curr->range_low) > + return -1; > + if (range_low > curr->range_high) > + return 1; > > + return 0; > +} > + > +int nova_find_range_node(struct nova_sb_info *sbi, > + struct rb_root *tree, unsigned long range_low, > + struct nova_range_node **ret_node) Instead of having a **ret_node pointer as an argument, just make the function return struct nova_range *node and have callers check for null: struct nova_range_node *node = nova_find_range_node(sbi, tree, range); if (ret) { //do stuff with *node } > +{ > + struct nova_range_node *curr = NULL; > + struct rb_node *temp; > + int compVal; > + int ret = 0; > + > + temp = tree->rb_node; > + > + while (temp) { > + curr = container_of(temp, struct nova_range_node, node); > + compVal = nova_rbtree_compare_rangenode(curr, range_low); > + > + if (compVal == -1) { > + temp = temp->rb_left; > + } else if (compVal == 1) { > + temp = temp->rb_right; > + } else { > + ret = 1; > + break; > + } > + } > + > + *ret_node = curr; > + return ret; > +} > + > + > +int nova_insert_range_node(struct rb_root *tree, > + struct nova_range_node *new_node) > +{ > + struct nova_range_node *curr; > + struct rb_node **temp, *parent; > + int compVal; > + > + temp = &(tree->rb_node); > + parent = NULL; > + > + while (*temp) { > + curr = container_of(*temp, struct nova_range_node, node); > + compVal = nova_rbtree_compare_rangenode(curr, > + new_node->range_low); > + parent = *temp; > + > + if (compVal == -1) { > + temp = &((*temp)->rb_left); > + } else if (compVal == 1) { > + temp = &((*temp)->rb_right); > + } else { > + nova_dbg("%s: entry %lu - %lu already exists: %lu - %lu\n", > + __func__, new_node->range_low, > + new_node->range_high, curr->range_low, > + curr->range_high); > + return -EINVAL; > + } > + } > + > + rb_link_node(&new_node->node, parent, temp); > + rb_insert_color(&new_node->node, tree); > + > + return 0; > +} > + > +inline int nova_insert_blocktree(struct nova_sb_info *sbi, > + struct rb_root *tree, struct nova_range_node *new_node) > +{ > + int ret; > + > + ret = nova_insert_range_node(tree, new_node); > + if (ret) > + nova_dbg("ERROR: %s failed %d\n", __func__, ret); > + > + return ret; > +} > diff --git a/fs/nova/balloc.h b/fs/nova/balloc.h > index e7c7a1d..57a93e4 100644 > --- a/fs/nova/balloc.h > +++ b/fs/nova/balloc.h > @@ -62,5 +62,16 @@ enum alloc_type { > > int nova_alloc_block_free_lists(struct super_block *sb); > void nova_delete_free_lists(struct super_block *sb); > - > +inline struct nova_range_node *nova_alloc_blocknode(struct super_block *sb); > +inline void nova_free_blocknode(struct super_block *sb, > + struct nova_range_node *bnode); > +extern void nova_init_blockmap(struct super_block *sb, int recovery); > +inline int nova_insert_blocktree(struct nova_sb_info *sbi, > + struct rb_root *tree, struct nova_range_node *new_node); > + > +extern int nova_insert_range_node(struct rb_root *tree, > + struct nova_range_node *new_node); > +extern int nova_find_range_node(struct nova_sb_info *sbi, > + struct rb_root *tree, unsigned long range_low, > + struct nova_range_node **ret_node); > #endif > diff --git a/fs/nova/super.c b/fs/nova/super.c > index 43b24a7..9762f26 100644 > --- a/fs/nova/super.c > +++ b/fs/nova/super.c > @@ -376,6 +376,8 @@ static struct nova_inode *nova_init(struct super_block *sb, > pi->nova_ino = NOVA_BLOCKNODE_INO; > nova_flush_buffer(pi, CACHELINE_SIZE, 1); > > + nova_init_blockmap(sb, 0); > + > sbi->nova_sb->s_size = cpu_to_le64(size); > sbi->nova_sb->s_blocksize = cpu_to_le32(blocksize); > sbi->nova_sb->s_magic = cpu_to_le32(NOVA_SUPER_MAGIC); >