[syslinux:elflink] xfs: Rework xfs_dir2_get_right_blk()
syslinux-bot for Chen Baozi
baozich at gmail.com
Tue Nov 27 12:57:25 PST 2012
Commit-ID: f9ad46af812f493ccd1c41a3540005b0f5f21ed6
Gitweb: http://www.syslinux.org/commit/f9ad46af812f493ccd1c41a3540005b0f5f21ed6
Author: Chen Baozi <baozich at gmail.com>
AuthorDate: Wed, 15 Aug 2012 17:32:42 +0800
Committer: Paulo Alcantara <pcacjr at zytor.com>
CommitDate: Sun, 2 Sep 2012 19:18:36 -0300
xfs: Rework xfs_dir2_get_right_blk()
In B+tree directory, besides the node/leaf blocks, all the
extents which store xfs_bmbt_rec_t entries are also organized
in B+tree. We need to rework xfs_dir2_get_right_blk() to
make it workable in all cases.
Signed-off-by: Chen Baozi <baozich at gmail.com>
Signed-off-by: Paulo Alcantara <pcacjr at zytor.com>
---
core/fs/xfs/xfs.h | 128 +++++++++++++++++++++++++++++++++++++++++++++
core/fs/xfs/xfs_dir2.c | 129 +++++++++++++++++++++++++++++++++++++---------
core/fs/xfs/xfs_dir2.h | 3 +-
core/fs/xfs/xfs_readdir.c | 6 +--
4 files changed, 237 insertions(+), 29 deletions(-)
diff --git a/core/fs/xfs/xfs.h b/core/fs/xfs/xfs.h
index 21abf58..64d01fd 100644
--- a/core/fs/xfs/xfs.h
+++ b/core/fs/xfs/xfs.h
@@ -254,6 +254,8 @@ typedef struct xfs_bmbt_rec {
uint64_t l1;
} __attribute__((__packed__)) xfs_bmbt_rec_t;
+typedef xfs_bmbt_rec_t xfs_bmdr_rec_t;
+
/*
* Possible extent states.
*/
@@ -293,6 +295,12 @@ typedef struct xfs_timestamp {
int32_t t_nsec;
} __attribute__((__packed__)) xfs_timestamp_t;
+/*
+ * Fork identifiers.
+ */
+#define XFS_DATA_FORK 0
+#define xFS_ATTR_FORK 1
+
typedef enum xfs_dinode_fmt {
XFS_DINODE_FMT_DEV,
XFS_DINODE_FMT_LOCAL,
@@ -334,6 +342,34 @@ typedef struct xfs_dinode {
uint8_t di_literal_area[1];
} __attribute__((packed)) xfs_dinode_t;
+/*
+ * Inode size for given fs.
+ */
+#define XFS_LITINO(fs) \
+ ((int)((XFS_INFO(fs)->inodesize) - sizeof(struct xfs_dinode) - 1))
+
+#define XFS_BROOT_SIZE_ADJ \
+ (XFS_BTREE_LBLOCK_LEN - sizeof(xfs_bmdr_block_t))
+
+/*
+ * Inode data & attribute fork sizes, per inode.
+ */
+#define XFS_DFORK_Q(dip) ((dip)->di_forkoff != 0)
+#define XFS_DFORK_BOFF(dip) ((int)((dip)->di_forkoff << 3))
+
+#define XFS_DFORK_DSIZE(dip, fs) \
+ (XFS_DFORK_Q(dip) ? \
+ XFS_DFORK_BOFF(dip) : \
+ XFS_LITINO(fs))
+#define XFS_DFORK_ASIZE(dip, fs) \
+ (XFS_DFORK_Q(dip) ? \
+ XFS_LITINO(fs) - XFS_DFORK_BOFF(dip) : \
+ 0)
+#define XFS_DFORK_SIZE(dip, fs, w) \
+ ((w) == XFS_DATA_FORK ? \
+ XFS_DFORK_DSIZE(dip, fs) : \
+ XFS_DFORK_ASIZE(dip, fs))
+
struct xfs_inode {
xfs_agblock_t i_agblock;
block_t i_ino_blk;
@@ -606,4 +642,96 @@ static inline void fill_xfs_inode_pvt(struct fs_info *fs, struct inode *inode,
XFS_INFO(fs)->inode_shift;
}
+/*
+ * Generic btree header.
+ *
+ * This is a combination of the actual format used on disk for short and long
+ * format btrees. The first three fields are shared by both format, but
+ * the pointers are different and should be used with care.
+ *
+ * To get the size of the actual short or long form headers please use
+ * the size macros belows. Never use sizeof(xfs_btree_block);
+ */
+typedef struct xfs_btree_block {
+ uint32_t bb_magic; /* magic number for block type */
+ uint16_t bb_level; /* 0 is a leaf */
+ uint16_t bb_numrecs; /* current # of data records */
+ union {
+ struct {
+ uint32_t bb_leftsib;
+ uint32_t bb_rightsib;
+ } s; /* short form pointers */
+ struct {
+ uint64_t bb_leftsib;
+ uint64_t bb_rightsib;
+ } l; /* long form pointers */
+ } bb_u; /* rest */
+} xfs_btree_block_t;
+
+#define XFS_BTREE_SBLOCK_LEN 16 /* size of a short form block */
+#define XFS_BTREE_LBLOCK_LEN 24 /* size of a long form block */
+
+/*
+ * Bmap root header, on-disk form only.
+ */
+typedef struct xfs_bmdr_block {
+ uint16_t bb_level; /* 0 is a leaf */
+ uint16_t bb_numrecs; /* current # of data records */
+} xfs_bmdr_block_t;
+
+/*
+ * Key structure for non-leaf levels of the tree.
+ */
+typedef struct xfs_bmbt_key {
+ uint64_t br_startoff; /* starting file offset */
+} xfs_bmbt_key_t, xfs_bmdr_key_t;
+
+/* btree pointer type */
+typedef uint64_t xfs_bmbt_ptr_t, xfs_bmdr_ptr_t;
+
+/*
+ * Btree block header size depends on a superblock flag.
+ *
+ * (not quite yet, but soon)
+ */
+#define XFS_BMBT_BLOCK_LEN(fs) XFS_BTREE_LBLOCK_LEN
+
+#define XFS_BMBT_REC_ADDR(fs, block, index) \
+ ((xfs_bmbt_rec_t *) \
+ ((char *)(block) + \
+ XFS_BMBT_BLOCK_LEN(fs) + \
+ ((index) - 1) * sizeof(xfs_bmbt_rec_t)))
+
+#define XFS_BMBT_KEY_ADDR(fs, block, index) \
+ ((xfs_bmbt_key_t *) \
+ ((char *)(block) + \
+ XFS_BMBT_BLOCK_LEN(fs) + \
+ ((index) - 1) * sizeof(xfs_bmbt_key_t)))
+
+#define XFS_BMBT_PTR_ADDR(fs, block, index, maxrecs) \
+ ((xfs_bmbt_ptr_t *) \
+ ((char *)(block) + \
+ XFS_BMBT_BLOCK_LEN(fs) + \
+ (maxrecs) * sizeof(xfs_bmbt_key_t) + \
+ ((index) - 1) * sizeof(xfs_bmbt_ptr_t)))
+
+#define XFS_BMDR_REC_ADDR(block, index) \
+ ((xfs_bmdr_rec_t *) \
+ ((char *)(block) + \
+ sizeof(struct xfs_bmdr_block) + \
+ ((index) - 1) * sizeof(xfs_bmdr_rec_t)))
+
+#define XFS_BMDR_KEY_ADDR(block, index) \
+ ((xfs_bmdr_key_t *) \
+ ((char *)(block) + \
+ sizeof(struct xfs_bmdr_block) + \
+ ((index) - 1) * sizeof(xfs_bmdr_key_t)))
+
+#define XFS_BMDR_PTR_ADDR(block, index, maxrecs) \
+ ((xfs_bmdr_ptr_t *) \
+ ((char *)(block) + \
+ sizeof(struct xfs_bmdr_block) + \
+ (maxrecs) * sizeof(xfs_bmdr_key_t) + \
+ ((index) - 1) * sizeof(xfs_bmdr_ptr_t)))
+
#endif /* XFS_H_ */
diff --git a/core/fs/xfs/xfs_dir2.c b/core/fs/xfs/xfs_dir2.c
index db1a1b1..7d1e8ee 100644
--- a/core/fs/xfs/xfs_dir2.c
+++ b/core/fs/xfs/xfs_dir2.c
@@ -432,20 +432,108 @@ failed:
return ip;
}
+/*
+ * Calculate number of records in a bmap btree inode root.
+ */
+static inline int
+xfs_bmdr_maxrecs(int blocklen, int leaf)
+{
+ blocklen -= sizeof(xfs_bmdr_block_t);
+
+ if (leaf)
+ return blocklen / sizeof(xfs_bmdr_rec_t);
+ return blocklen / (sizeof(xfs_bmdr_key_t) + sizeof(xfs_bmdr_ptr_t));
+}
+
+static xfs_fsblock_t
+select_child(xfs_dfiloff_t off,
+ xfs_bmbt_key_t *kp,
+ xfs_bmbt_ptr_t *pp,
+ int nrecs)
+{
+ int i;
+
+ for (i = 0; i < nrecs; i++) {
+ if (be64_to_cpu(kp[i].br_startoff) == off)
+ return be64_to_cpu(pp[i]);
+ if (be64_to_cpu(kp[i].br_startoff) > off) {
+ if (i == 0)
+ return be64_to_cpu(pp[i]);
+ else
+ return be64_to_cpu(pp[i-1]);
+ }
+ }
+
+ return be64_to_cpu(pp[nrecs - 1]);
+}
+
block_t xfs_dir2_get_right_blk(struct fs_info *fs, xfs_dinode_t *core,
- uint32_t from, uint32_t to, block_t fsblkno,
- int *error)
+ block_t fsblkno, int *error)
{
uint32_t idx;
xfs_bmbt_irec_t irec;
+ block_t bno;
+ block_t nextbno;
+ xfs_bmdr_block_t *rblock;
+ int fsize;
+ int nextents;
+ xfs_bmbt_ptr_t *pp;
+ xfs_bmbt_key_t *kp;
+ xfs_btree_block_t *blk;
+ xfs_bmbt_rec_t *xp;
*error = 0;
- for (idx = from; idx < to; idx++) {
- bmbt_irec_get(&irec,
- ((xfs_bmbt_rec_t *)&core->di_literal_area[0]) + idx);
- if (fsblkno >= irec.br_startoff &&
- fsblkno < irec.br_startoff + irec.br_blockcount)
- break;
+ if (core->di_format == XFS_DINODE_FMT_EXTENTS) {
+ xfs_debug("XFS_DINODE_FMT_EXTENTS");
+ for (idx = 0; idx < be32_to_cpu(core->di_nextents); idx++) {
+ bmbt_irec_get(&irec,
+ ((xfs_bmbt_rec_t *)&core->di_literal_area[0]) + idx);
+ if (fsblkno >= irec.br_startoff &&
+ fsblkno < irec.br_startoff + irec.br_blockcount)
+ break;
+ }
+ } else if (core->di_format == XFS_DINODE_FMT_BTREE) {
+ xfs_debug("XFS_DINODE_FMT_BTREE");
+ bno = NULLFSBLOCK;
+ rblock = (xfs_bmdr_block_t *)&core->di_literal_area[0];
+ fsize = XFS_DFORK_SIZE(core, fs, XFS_DATA_FORK);
+ pp = XFS_BMDR_PTR_ADDR(rblock, 1, xfs_bmdr_maxrecs(fsize, 0));
+ kp = XFS_BMDR_KEY_ADDR(rblock, 1);
+ bno = fsblock_to_bytes(fs,
+ select_child(fsblkno, kp, pp,
+ be16_to_cpu(rblock->bb_numrecs))) >> BLOCK_SHIFT(fs);
+
+ /* Find the leaf */
+ for (;;) {
+ blk = (xfs_btree_block_t *)get_cache(fs->fs_dev, bno);
+ if (be16_to_cpu(blk->bb_level) == 0)
+ break;
+ pp = XFS_BMBT_PTR_ADDR(fs, blk, 1,
+ xfs_bmdr_maxrecs(XFS_INFO(fs)->blocksize, 0));
+ kp = XFS_BMBT_KEY_ADDR(fs, blk, 1);
+ bno = fsblock_to_bytes(fs,
+ select_child(fsblkno, kp, pp,
+ be16_to_cpu(blk->bb_numrecs))) >> BLOCK_SHIFT(fs);
+ }
+
+ /* Find the records among leaves */
+ for (;;) {
+ nextbno = be64_to_cpu(blk->bb_u.l.bb_rightsib);
+ nextents = be16_to_cpu(blk->bb_numrecs);
+ xp = (xfs_bmbt_rec_t *)XFS_BMBT_REC_ADDR(fs, blk, 1);
+ for (idx = 0; idx < nextents; idx++) {
+ bmbt_irec_get(&irec, xp + idx);
+ if (fsblkno >= irec.br_startoff &&
+ fsblkno < irec.br_startoff + irec.br_blockcount) {
+ nextbno = NULLFSBLOCK;
+ break;
+ }
+ }
+ if (nextbno == NULLFSBLOCK)
+ break;
+ bno = fsblock_to_bytes(fs, nextbno) >> BLOCK_SHIFT(fs);
+ blk = (xfs_btree_block_t *)get_cache(fs->fs_dev, bno);
+ }
}
if (fsblkno < irec.br_startoff ||
@@ -460,8 +548,6 @@ block_t xfs_dir2_get_right_blk(struct fs_info *fs, xfs_dinode_t *core,
struct inode *xfs_dir2_node_find_entry(const char *dname, struct inode *parent,
xfs_dinode_t *core)
{
- xfs_bmbt_irec_t irec;
- uint32_t node_off = 0;
block_t fsblkno;
xfs_da_intnode_t *node = NULL;
uint32_t hashwant;
@@ -487,16 +573,16 @@ struct inode *xfs_dir2_node_find_entry(const char *dname, struct inode *parent,
xfs_dinode_t *ncore;
uint8_t *buf = NULL;
- do {
- bmbt_irec_get(&irec, ((xfs_bmbt_rec_t *)&core->di_literal_area[0]) +
- (++node_off));
- } while (irec.br_startoff <
- xfs_dir2_byte_to_db(parent->fs, XFS_DIR2_LEAF_OFFSET));
-
hashwant = xfs_dir2_da_hashname((uint8_t *)dname, strlen(dname));
- fsblkno = fsblock_to_bytes(parent->fs, irec.br_startblock) >>
- BLOCK_SHIFT(parent->fs);
+ fsblkno = xfs_dir2_get_right_blk(parent->fs, core,
+ xfs_dir2_byte_to_db(parent->fs, XFS_DIR2_LEAF_OFFSET),
+ &error);
+ if (error) {
+ xfs_error("Cannot find right rec!");
+ return NULL;
+ }
+
node = (xfs_da_intnode_t *)xfs_dir2_get_dirblks(parent->fs, fsblkno, 1);
if (be16_to_cpu(node->hdr.info.magic) != XFS_DA_NODE_MAGIC) {
xfs_error("Node's magic number does not match!");
@@ -542,9 +628,7 @@ struct inode *xfs_dir2_node_find_entry(const char *dname, struct inode *parent,
else
fsblkno = be32_to_cpu(node->btree[probe].before);
- fsblkno = xfs_dir2_get_right_blk(parent->fs, core, node_off + 1,
- be32_to_cpu(core->di_nextents) - 1,
- fsblkno, &error);
+ fsblkno = xfs_dir2_get_right_blk(parent->fs, core, fsblkno, &error);
if (error) {
xfs_error("Cannot find right rec!");
goto out;
@@ -597,8 +681,7 @@ struct inode *xfs_dir2_node_find_entry(const char *dname, struct inode *parent,
if (buf)
free(buf);
- fsblkno = xfs_dir2_get_right_blk(parent->fs, core, 0, node_off,
- newdb, &error);
+ fsblkno = xfs_dir2_get_right_blk(parent->fs, core, newdb, &error);
if (error) {
xfs_error("Cannot find data block!");
goto out;
diff --git a/core/fs/xfs/xfs_dir2.h b/core/fs/xfs/xfs_dir2.h
index c939833..e1b9622 100644
--- a/core/fs/xfs/xfs_dir2.h
+++ b/core/fs/xfs/xfs_dir2.h
@@ -28,8 +28,7 @@ void *xfs_dir2_get_dirblks(struct fs_info *fs, block_t startblock,
xfs_filblks_t c);
uint32_t xfs_dir2_da_hashname(const uint8_t *name, int namelen);
block_t xfs_dir2_get_right_blk(struct fs_info *fs, xfs_dinode_t *core,
- uint32_t from, uint32_t to, block_t fsblkno,
- int *error);
+ block_t fsblkno, int *error);
struct inode *xfs_dir2_local_find_entry(const char *dname, struct inode *parent,
xfs_dinode_t *core);
diff --git a/core/fs/xfs/xfs_readdir.c b/core/fs/xfs/xfs_readdir.c
index e68ce63..a3be247 100644
--- a/core/fs/xfs/xfs_readdir.c
+++ b/core/fs/xfs/xfs_readdir.c
@@ -315,9 +315,7 @@ try_next_btree:
goto out;
fsblkno = be32_to_cpu(node->btree[XFS_PVT(inode)->i_btree_offset].before);
- fsblkno = xfs_dir2_get_right_blk(fs, core, node_off + 1,
- be32_to_cpu(core->di_nextents) - 1,
- fsblkno, &error);
+ fsblkno = xfs_dir2_get_right_blk(fs, core, fsblkno, &error);
if (error) {
xfs_error("Cannot find leaf rec!");
goto out;
@@ -355,7 +353,7 @@ try_next_btree:
db = xfs_dir2_dataptr_to_db(fs, be32_to_cpu(lep->address));
- fsblkno = xfs_dir2_get_right_blk(fs, core, 0, node_off, db, &error);
+ fsblkno = xfs_dir2_get_right_blk(fs, core, db, &error);
if (error) {
xfs_error("Cannot find data block!");
goto out1;
More information about the Syslinux-commits
mailing list