Received: by 10.223.185.111 with SMTP id b44csp1654579wrg; Sat, 10 Mar 2018 10:42:54 -0800 (PST) X-Google-Smtp-Source: AG47ELvgrK9ixx8RFA0z8nPVx8HVloujR2USOSjeVYdArYi8SxpKl8FSArjOyx0rV1k6FBECoUgW X-Received: by 2002:a17:902:8484:: with SMTP id c4-v6mr2742660plo.271.1520707374694; Sat, 10 Mar 2018 10:42:54 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1520707374; cv=none; d=google.com; s=arc-20160816; b=OOLuTjgddSZ4pPfwbHiM7mxvMnx8Fna9dHT7oXx8CY6sq7oWN/t/wYVxe536+Er+x4 SEPnptbumylCBA2nJhEPRd12//nG7s6W4Ha1VgJvi1GKW2zs3vs5plGN7bJpPNXNmcMr /poasyz9DP3nSpxNJFosZ+6hqIJR9XM9H97KgFJpN2xcIzUYNSeno281NucITXLbXVlr 4zBYHvu4ZVd5r4EcoUvbPIN3tQdgemX1W4gfYlxAHPz7riqmEiTbxhDA9ETOgWk0UVmk c8FcIJez5lXCiEkKnyfkKzapg/mGcuCNYDHRlhCEbKgywibyPH7yHsMZ0XGBANHJugpC 343Q== 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=gCOc/n9fK4CUfp0RS2P03HBOKNEuZ+C8j+HlKjcgT/4=; b=SJ+xHCj/GQwDWv2n67gwnxYlVweGvaAHZ7lSWb1Y/tgnCgD05Wbx3np6WWvwj09NXt HGocvx2T3E7ywQZ31vDLUxYohI5GGvEFvR7ab2DFFcZapwQB2bFeboo1vMdTcHuXLa3o /cxvbpIGiqxvmHjC2j17u7ifXasm0+Vs0njQ4k57cA3+E9ctjBCaTt39t29sd5W9r+HF ty9XZHwgP1+EXRgNtEd5w8b6o+IlmnH2dR82w1HzFIbzcrIq8zYMBa+OwXOMoNYtA31G hR4rmmLHc/4eR1fZSd4uCJomEuKyY7TGhNobKR6jfXT8pz+O4jHiDJaV5euOWTNmUwrI Ey9w== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@eng.ucsd.edu header.s=google header.b=NtiLXxxa; 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 a13si2576309pgt.572.2018.03.10.10.42.40; Sat, 10 Mar 2018 10:42:54 -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=NtiLXxxa; 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 S932365AbeCJSlt (ORCPT + 99 others); Sat, 10 Mar 2018 13:41:49 -0500 Received: from mail-pg0-f66.google.com ([74.125.83.66]:35332 "EHLO mail-pg0-f66.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932324AbeCJSUg (ORCPT ); Sat, 10 Mar 2018 13:20:36 -0500 Received: by mail-pg0-f66.google.com with SMTP id l131so4839800pga.2 for ; Sat, 10 Mar 2018 10:20:35 -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=gCOc/n9fK4CUfp0RS2P03HBOKNEuZ+C8j+HlKjcgT/4=; b=NtiLXxxa76t94qDFy6AnGro2WM36sU/hB1Jc4tbLAKePJI11cLg2keB8rFgcIqn77r TO0sBc5g/B7TwANVPDoNuAJuJkq6IDnQZNarKdH2J8MqF/DiXBG8LPKV7dNgF+ejQttt xF/Reb2R9czgP2yl/1CH4l4JbyIH//yYp+N3s= 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=gCOc/n9fK4CUfp0RS2P03HBOKNEuZ+C8j+HlKjcgT/4=; b=ZfSgJK0NmMOHS6xe9u/fiuPxXUtW71t3EfjL/dTD3ZcI/AiUL/VnfE3aM5XkjEkdXz UqrVuYnzUaPEvQaQ9zGcG4px+SLpLYNBzhj2YGFjgkJt+Hna4qkW0el1RfEOyGDx+wlr V/Q373x2Y4OwDarb/+o5WxZvYB84b2B6SPmOdNY638PkRCoOsjLMtXxCbPKtKKuyI/mi TcrU3las9Yxz0sxdk5SllJKxIm7XcuoI5mXyH7u7MI+MWnlFYplxqJuIX31Ftc70P7Lc PtOzYldr8IBTfi2w9S3Y22Iwa6HzG/MWqpVBu9Sx6ytp0STONNKasRg/Lq/DSEaB4EIy /H5Q== X-Gm-Message-State: AElRT7G0hM2NCvcH6euDq/f8fDZpSxM6hFnJ2VEpWYJgrwoq8T5ne56O 12FNkvEYw4eov2PRVKoOOqjCKA== X-Received: by 10.99.60.72 with SMTP id i8mr2163592pgn.399.1520706035499; Sat, 10 Mar 2018 10:20:35 -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.20.34 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sat, 10 Mar 2018 10:20:34 -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 16/83] Initialize block map and free lists in nova_init(). Date: Sat, 10 Mar 2018 10:17:57 -0800 Message-Id: <1520705944-6723-17-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 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; + + 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) +{ + 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); -- 2.7.4