From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-ej1-f54.google.com (mail-ej1-f54.google.com [209.85.218.54]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 4FDA13F54DB for ; Thu, 7 May 2026 13:22:06 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.54 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778160128; cv=none; b=D8hIaMUGleDzc0uBie3rbtPUdgNiiG6DubbaS2qgcs5Lktcnna72GVVINa76GkiErbrcBM35/VdCL23CKzNQY51x0XHc8qCOQGdKqSsq32ynCzeDsSViyNhMZCanDDA4qt7Vr2AmRd/2HZCzF3Za/bFd+T8nJ/95zlqL+OaCRms= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778160128; c=relaxed/simple; bh=vzhyj8MNM18LG2FqXKE6lcrN/Ie6V3NNrJ/hsR+nZWk=; h=From:To:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=bvXpYAhWuE879FpJwH26oksFGoHdnPa8VgiPRdEEmbfhwh8aGBRn52BXw5vtMghelhRaI9/f0Uw4PlPPH3vtIw7I3/351pABkZjSG172OhcBvE3Qb4aUqAz08d88KOYUhXW0SX2z8VxNJ5Zc/oanCSFIGmGTSxszRzKv2cyl/Yc= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=permerror header.from=versity.com; spf=pass smtp.mailfrom=versity.com; dkim=pass (2048-bit key) header.d=versity.com header.i=@versity.com header.b=i0dTMwL4; arc=none smtp.client-ip=209.85.218.54 Authentication-Results: smtp.subspace.kernel.org; dmarc=permerror header.from=versity.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=versity.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=versity.com header.i=@versity.com header.b="i0dTMwL4" Received: by mail-ej1-f54.google.com with SMTP id a640c23a62f3a-b9382e59c0eso131523766b.0 for ; Thu, 07 May 2026 06:22:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=versity.com; s=google; t=1778160125; x=1778764925; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:from:to:cc:subject:date:message-id :reply-to; bh=abVUzQ5vnUvFJlYIICJpw9y6+d30Sd8IAOnv9RAO5xc=; b=i0dTMwL4PAsalrdzwITItM7T82dtxL5GLrl7nM/MdQUNu2Ww0yDNdAK+btMJuFCwUp DTZ5BTsAdzOHOaE6g9eI++r9Wx/1C1jfWl/L8L1sZBsWXUfEArXavNDi+GnoATHABV5O pLCJazHA7VLEI82Cp/ElZTcudejTgJBpcDm1CeyY8phCatgnJn+55HhWbSfBzxRzy+g1 wGvhNuI++xSx9yBkwBvRWUmS1fjspRTXv2uzAvYZX7vmJfdnoFdGRYJUFaSczNEEgqSL dx0efOcS0GcWX3afLZwqqFHyY14BqXXy0/SsWCvzfBB2WU7Btetdsa76m4iO4IgRpFL0 KkLA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1778160125; x=1778764925; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:x-gm-gg:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=abVUzQ5vnUvFJlYIICJpw9y6+d30Sd8IAOnv9RAO5xc=; b=llVQXAlC4+09jFhVK2/wDce31GodXmEpMPa0zQ07ey0kszv0Xev9f3dsvSgRVOVjAG bo8g2wxzK5FYoCAZpOeZG1p1sp6lynyYrwSgvNiH3OW4VWV0xYA8dlP10ZaqZbypJpqE 1juS5GxT5+GR7GiP83Sbqd+Dy/hRwH8/KbVT/jxC19F4tqJP6/Pjb1vx6V+Sn89n9uw/ gBEZUHQewvimr/9UGIRDiHwqQZpSgLV3vVWimft33Y6HDNGWBqzfI6J8iZU8u+Xx0aG9 ZkXrqCbrGdWFA2J+2lNQH5dbJkP8jTp2dHYSHoX2tfe5e+JgGB/jdAhSREmdLxxx1aTv GHQw== X-Gm-Message-State: AOJu0YzqEYZWQK2V+FfR3+C9Uf7NxFOL/G2/2AJiUygLvWUTb+3DKvov Emyr2f2zfUHJIGQ1r2i0donXvZjJg8YSzn7F44gxDsR7X/u/tfcdAE60lyZLn7WX16rxj5BvH46 pRnpXiAU= X-Gm-Gg: AeBDietBrOwcENh+1amGKfkFlKVH3iiW2I/eu2OrZ2K3Gb1kWcDhNcRtNMYx7BmwNLc cNCi9vj7BJD+MD7zYK4QganuI0Gdd78xiy5/bKwPMVLaaFuRDGsdM6RTh82gXy5C0UzzvEdIoVc NIFBElvTUxuvReE5iK/n1BH/nxw7tm1M/2FTCjqoCCX+NU/O25xppOQgGHNLWftmDoGe5d548fg IMS5IPwWad+BzxiiEuaRq/iQWyNvyF4syBVcJ5qmMNKshy0KtGIsO6oLaqrr/NWE6pM1CZ8j6n8 5koc00/8OUkuozNrE579iN5aIyYQqPU7Urv0OMM59/XLlz6HwY89rw2fv8E8FBYA6enmS1Lb+WD Ge+2yTDP7/cKxQqfrm4ImkhbewdHJRpm4HBZ5mSX8LLQObkA/JjSnO2B218njLGeTPF4H3z2WgW O6saRFBbWkj41ykfuKUYzgHtfTTpSdaWRrkBnraHiSXb7K1jsbb5V2n9iGBz2i/2l8ycqQeBq7k xjMh5l3eTUCkacPKqpeBFUK4yC3pG+KotnUbg== X-Received: by 2002:a17:907:6b07:b0:bc5:d77e:c099 with SMTP id a640c23a62f3a-bc5d77ed941mr478849366b.33.1778160124362; Thu, 07 May 2026 06:22:04 -0700 (PDT) Received: from localhost.localdomain (46-117-212-87.ftth.glasoperator.nl. [87.212.117.46]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-bc83364c5e3sm80638666b.35.2026.05.07.06.22.03 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 May 2026 06:22:03 -0700 (PDT) From: Valerie Aurora To: rpdfs-devel@lists.linux.dev Subject: [PATCH 3/6] rpdfs: add basic file data initialization Date: Thu, 7 May 2026 15:21:50 +0200 Message-ID: <20260507132153.1161324-4-val@versity.com> X-Mailer: git-send-email 2.49.0 In-Reply-To: <20260507132153.1161324-1-val@versity.com> References: <20260507132153.1161324-1-val@versity.com> Precedence: bulk X-Mailing-List: rpdfs-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Initialize the file data root, plus a few simple routines to calculate mapping block levels. Rename the field in the inode from "data" to "data_root" to avoid confusion with the "data" member of struct rpdfs_block_handle. Signed-off-by: Valerie Aurora --- fs/rpdfs/Makefile | 1 + fs/rpdfs/data.c | 93 +++++++++++++++++++++++++++++++++++++++++ fs/rpdfs/data.h | 11 +++++ fs/rpdfs/format-block.h | 32 +++++++------- fs/rpdfs/inode.c | 8 ++++ fs/rpdfs/inode.h | 1 + 6 files changed, 129 insertions(+), 17 deletions(-) create mode 100644 fs/rpdfs/data.c create mode 100644 fs/rpdfs/data.h diff --git a/fs/rpdfs/Makefile b/fs/rpdfs/Makefile index d995103ea5a8..f8301d86682b 100644 --- a/fs/rpdfs/Makefile +++ b/fs/rpdfs/Makefile @@ -12,6 +12,7 @@ rpdfs-y := balloc.o \ block.o \ btree.o \ btree_txn.o \ + data.o \ dir.o \ file.o \ ht.o \ diff --git a/fs/rpdfs/data.c b/fs/rpdfs/data.c new file mode 100644 index 000000000000..65b753886a04 --- /dev/null +++ b/fs/rpdfs/data.c @@ -0,0 +1,93 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +#include +#include +#include +#include +#include + +#include "balloc.h" +#include "inode.h" +#include "format-block.h" +#include "pr.h" +#include "super.h" +#include "data.h" + +/* + * File data is stored in simple tree of mapping blocks with data all + * at the same level of the tree. The topmost block in the tree and its + * level are stored in the inode. The tree is sparse and branches are + * grown as necessary to index newly written data blocks. While + * manipulating the tree, we use levels to identify the blocks at + * various levels of the tree, with the highest levels closer to the + * root. + * + * The data root field in the inode contains both the persistent + * reference (block number, etc.) to the root block of the tree, plus + * the height of the tree (the level of the block it points to, plus 1). + * The root block reference is not part of a mapping block. + * + * The level of a block is: + * + * 0 = data block + * 1 = references to data blocks + * 2 = references to single mapping blocks (pointing to data blocks) + * 3 = references to double mapping blocks + * 4 = references to triple mapping blocks + * + * Thus a data root reference with height 1 points to a block of level 0 + * = a single block of data at logical file offset 0. + */ + +/* + * Return the logical block number containing offset within a file. + */ +static u64 lblk_from_offset(u64 offset) +{ + return offset >> RPDFS_BLOCK_SHIFT; +} + +/* + * Calculate the index of the block reference for this logical block + * within a mapping block at this level. + */ +static u32 calc_ref_ind(u64 lblk, u8 level) +{ + u8 ind; + + BUG_ON(level == 0); + + BUILD_BUG_ON_NOT_POWER_OF_2(RPDFS_DATA_REFS_PER_BLK); + + ind = (lblk >> (level - 1) * RPDFS_DATA_REFS_PER_BLK_SHIFT) & RPDFS_DATA_REFS_PER_BLK_MASK; + + rpdfs_prd("lblk %llu level %u ind %u refs_per_blk %llu", lblk, level, ind, RPDFS_DATA_REFS_PER_BLK); + + return ind; +} + +/* + * Calculate the height of the tree needed to index the logical block + * lblk in this file. This is stored in the inode's data tree root. + */ +static u8 height_from_lblk(u64 lblk) +{ + u8 height; + + if (lblk == 0) + return 1; + + height = ((fls(lblk) - 1)/RPDFS_DATA_REFS_PER_BLK_SHIFT) + 2; + + rpdfs_prd("lblk %llu fls(lblk) - 1 %u refs_per_blk_shift %u + 2 = height %u", + lblk, fls(lblk) - 1, RPDFS_DATA_REFS_PER_BLK_SHIFT, height); + + return height; +} + +void rpdfs_data_root_init(struct rpdfs_data_root *data) +{ + data->height = 0; + data->ref.bnr = 0; + data->ref.alloc_counter = 0; +} diff --git a/fs/rpdfs/data.h b/fs/rpdfs/data.h new file mode 100644 index 000000000000..bb6b0c7dea86 --- /dev/null +++ b/fs/rpdfs/data.h @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef RPDFS_DATA_H +#define RPDFS_DATA_H + +#include "format-block.h" + +void rpdfs_data_root_init(struct rpdfs_data_root *data); + +extern const struct address_space_operations rpdfs_aops; + +#endif diff --git a/fs/rpdfs/format-block.h b/fs/rpdfs/format-block.h index 395e6d2d17e7..c2879e677084 100644 --- a/fs/rpdfs/format-block.h +++ b/fs/rpdfs/format-block.h @@ -4,9 +4,10 @@ #include #include +#include #define RPDFS_BLOCK_SHIFT 12 -#define RPDFS_BLOCK_SIZE (1 << RPDFS_BLOCK_SHIFT) +#define RPDFS_BLOCK_SIZE (1ULL << RPDFS_BLOCK_SHIFT) #define RPDFS_BLOCK_MASK (RPDFS_BLOCK_SIZE - 1ULL) struct rpdfs_block_ref { @@ -113,9 +114,11 @@ struct rpdfs_ino_gen { }; /* - * Data blocks are pointed to by a simple tree of indirect blocks rooted - * in a single field in the inode. The height is one greater than the - * level of the referenced block. It's 0 for an empty tree. + * Data blocks are pointed to by a simple tree of mapping blocks rooted + * in a single field in the inode. The height of the tree is the number + * of blocks in the mapping chain, including the data block itself. It's + * 0 for a file with no data, 1 for a file with 1 data block at logical + * block 0, 2 for for a file with 2 data blocks at 0 and 1, etc. */ struct rpdfs_data_root { struct rpdfs_block_ref ref; @@ -124,21 +127,16 @@ struct rpdfs_data_root { }; /* - * Indirect blocks are a simple array of block refs. We rely on the - * number of references per indirect block being a power of 2, so check - * that at compile time. + * Mapping blocks are a simple array of block refs. Because blocks per + * ref is based on the size of a struct, we can't do the smart thing and + * define the shift first and then the value, we have to go backwards + * and define the shift from the value instead. */ -#define RPDFS_DATA_REFS_PER_BLK (RPDFS_BLOCK_SIZE / sizeof(struct rpdfs_block_ref)) - -/* - * Because blocks per ref is based on the size of a struct, we can't do - * the smart thing and define the shift first and then the value, we - * have to go backwards and define the shift from the value instead. - */ - +#define RPDFS_DATA_REFS_PER_BLK (RPDFS_BLOCK_SIZE / sizeof(struct rpdfs_block_ref)) #define RPDFS_DATA_REFS_PER_BLK_SHIFT const_ilog2(RPDFS_DATA_REFS_PER_BLK) +#define RPDFS_DATA_REFS_PER_BLK_MASK (RPDFS_DATA_REFS_PER_BLK - 1ULL) -struct rpdfs_indirect_block { +struct rpdfs_map_block { struct rpdfs_block_ref refs[RPDFS_DATA_REFS_PER_BLK]; }; @@ -168,7 +166,7 @@ struct rpdfs_inode { __le64 crtime_nsec; struct rpdfs_btree_root dirents; struct rpdfs_btree_root xattrs; - struct rpdfs_data_root data; + struct rpdfs_data_root data_root; }; #define RPDFS_ROOT_INO 1 diff --git a/fs/rpdfs/inode.c b/fs/rpdfs/inode.c index a2baa862f6a4..fd0913e0e4b6 100644 --- a/fs/rpdfs/inode.c +++ b/fs/rpdfs/inode.c @@ -9,6 +9,7 @@ #include "btree.h" #include "compare.h" +#include "data.h" #include "dir.h" #include "file.h" #include "inode.h" @@ -80,6 +81,8 @@ static void copy_rinode_to_vfs_inode(struct inode *inode, struct rpdfs_inode *ri ri->xattrs = rinode->xattrs; ri->xattr_creates = rinode->xattr_creates; + + ri->data_root = rinode->data_root; } static __le64 cpu_ts64_to_le64_ns(struct timespec64 ts) @@ -122,6 +125,8 @@ static void print_inode_change(struct inode *inode, struct rpdfs_inode *rinode) print_diff64("dirents", le64_to_cpu(ri->dirents.ref.bnr), le64_to_cpu(rinode->dirents.ref.bnr)); print_diff64("xattrs", le64_to_cpu(ri->xattrs.ref.bnr), le64_to_cpu(rinode->xattrs.ref.bnr)); print_diff64("xattr_creates", le64_to_cpu(ri->xattr_creates), le64_to_cpu(rinode->xattr_creates)); + print_diff64("data_root.height", ri->data_root.height, rinode->data_root.height); + print_diff64("data_root.ref.bnr", le64_to_cpu(ri->data_root.ref.bnr), le64_to_cpu(rinode->data_root.ref.bnr)); } static void copy_vfs_inode_to_rinode(struct rpdfs_inode *rinode, struct inode *inode) @@ -144,6 +149,8 @@ static void copy_vfs_inode_to_rinode(struct rpdfs_inode *rinode, struct inode *i rinode->xattrs = ri->xattrs; rinode->xattr_creates = ri->xattr_creates; + + rinode->data_root = ri->data_root; } /* @@ -336,6 +343,7 @@ struct inode *rpdfs_new_inode(struct super_block *sb, struct rpdfs_ino_gen *ig) rpdfs_btree_root_init(&ri->dirents); rpdfs_btree_root_init(&ri->xattrs); + rpdfs_data_root_init(&ri->data_root); ts = inode_set_ctime_current(inode); inode_set_mtime_to_ts(inode, ts); diff --git a/fs/rpdfs/inode.h b/fs/rpdfs/inode.h index 3b0be2d83e61..3892fdcc8b1b 100644 --- a/fs/rpdfs/inode.h +++ b/fs/rpdfs/inode.h @@ -25,6 +25,7 @@ struct rpdfs_inode_info { struct rpdfs_ino_gen ig; struct rpdfs_btree_root dirents; struct rpdfs_btree_root xattrs; + struct rpdfs_data_root data_root; struct inode vfs_inode; }; -- 2.49.0