[PATCH 1/2] erofs-utils: rearrange on-disk metadata
Gao Xiang
hsiangkao at linux.alibaba.com
Fri Mar 17 19:50:44 AEDT 2023
- Use BFS instead of DFS;
- Regular data is separated from metadata and dir data.
Signed-off-by: Gao Xiang <hsiangkao at linux.alibaba.com>
---
include/erofs/inode.h | 3 +-
include/erofs/internal.h | 2 +
lib/cache.c | 5 +-
lib/inode.c | 234 ++++++++++++++++++++++-----------------
mkfs/main.c | 2 +-
5 files changed, 141 insertions(+), 105 deletions(-)
diff --git a/include/erofs/inode.h b/include/erofs/inode.h
index bf20cd3..058a235 100644
--- a/include/erofs/inode.h
+++ b/include/erofs/inode.h
@@ -20,8 +20,7 @@ unsigned char erofs_ftype_to_dtype(unsigned int filetype);
void erofs_inode_manager_init(void);
unsigned int erofs_iput(struct erofs_inode *inode);
erofs_nid_t erofs_lookupnid(struct erofs_inode *inode);
-struct erofs_inode *erofs_mkfs_build_tree_from_path(struct erofs_inode *parent,
- const char *path);
+struct erofs_inode *erofs_mkfs_build_tree_from_path(const char *path);
struct erofs_inode *erofs_mkfs_build_special_from_fd(int fd, const char *name);
#ifdef __cplusplus
diff --git a/include/erofs/internal.h b/include/erofs/internal.h
index a727312..1f1e730 100644
--- a/include/erofs/internal.h
+++ b/include/erofs/internal.h
@@ -147,6 +147,8 @@ struct erofs_inode {
unsigned int flags;
/* (mkfs.erofs) device ID containing source file */
u32 dev;
+ /* (mkfs.erofs) queued sub-directories blocking dump */
+ u32 subdirs_queued;
};
unsigned int i_count;
struct erofs_inode *i_parent;
diff --git a/lib/cache.c b/lib/cache.c
index 3ada3eb..9eb0394 100644
--- a/lib/cache.c
+++ b/lib/cache.c
@@ -288,7 +288,10 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
bb->blkaddr = NULL_ADDR;
bb->buffers.off = 0;
init_list_head(&bb->buffers.list);
- list_add_tail(&bb->list, &blkh.list);
+ if (type == DATA)
+ list_add(&bb->list, &last_mapped_block->list);
+ else
+ list_add_tail(&bb->list, &blkh.list);
init_list_head(&bb->mapped_list);
bh = malloc(sizeof(struct erofs_buffer_head));
diff --git a/lib/inode.c b/lib/inode.c
index 39874a0..0f49f6e 100644
--- a/lib/inode.c
+++ b/lib/inode.c
@@ -183,7 +183,6 @@ int erofs_prepare_dir_file(struct erofs_inode *dir, unsigned int nr_subdirs)
{
struct erofs_dentry *d, *n, **sorted_d;
unsigned int d_size, i_nlink, i;
- int ret;
/* dot is pointed to the current dir inode */
d = erofs_d_alloc(dir, ".");
@@ -241,11 +240,6 @@ int erofs_prepare_dir_file(struct erofs_inode *dir, unsigned int nr_subdirs)
/* no compression for all dirs */
dir->datalayout = EROFS_INODE_FLAT_INLINE;
- /* allocate dir main data */
- ret = __allocate_inode_bh_data(dir, erofs_blknr(d_size));
- if (ret)
- return ret;
-
/* it will be used in erofs_prepare_inode_buffer */
dir->idata_size = d_size % erofs_blksiz();
return 0;
@@ -284,6 +278,33 @@ static int write_dirblock(unsigned int q, struct erofs_dentry *head,
return blk_write(buf, blkaddr, 1);
}
+erofs_nid_t erofs_lookupnid(struct erofs_inode *inode)
+{
+ struct erofs_buffer_head *const bh = inode->bh;
+ erofs_off_t off, meta_offset;
+
+ if (!bh || inode->nid)
+ return inode->nid;
+
+ erofs_mapbh(bh->block);
+ off = erofs_btell(bh, false);
+
+ meta_offset = erofs_pos(sbi.meta_blkaddr);
+ DBG_BUGON(off < meta_offset);
+ inode->nid = (off - meta_offset) >> EROFS_ISLOTBITS;
+ erofs_dbg("Assign nid %llu to file %s (mode %05o)",
+ inode->nid, inode->i_srcpath, inode->i_mode);
+ return inode->nid;
+}
+
+static void erofs_d_invalidate(struct erofs_dentry *d)
+{
+ struct erofs_inode *const inode = d->inode;
+
+ d->nid = erofs_lookupnid(inode);
+ erofs_iput(inode);
+}
+
static int erofs_write_dir_file(struct erofs_inode *dir)
{
struct erofs_dentry *head = list_first_entry(&dir->i_subdirs,
@@ -295,10 +316,16 @@ static int erofs_write_dir_file(struct erofs_inode *dir)
q = used = blkno = 0;
+ /* allocate dir main data */
+ ret = __allocate_inode_bh_data(dir, erofs_blknr(dir->i_size));
+ if (ret)
+ return ret;
+
list_for_each_entry(d, &dir->i_subdirs, d_child) {
const unsigned int len = strlen(d->name) +
sizeof(struct erofs_dirent);
+ erofs_d_invalidate(d);
if (used + len > erofs_blksiz()) {
ret = write_dirblock(q, head, d,
dir->u.i_blkaddr + blkno);
@@ -589,23 +616,11 @@ static int erofs_prepare_tail_block(struct erofs_inode *inode)
return 0;
bh = inode->bh_data;
- if (!bh) {
- bh = erofs_balloc(DATA, erofs_blksiz(), 0, 0);
- if (IS_ERR(bh))
- return PTR_ERR(bh);
- bh->op = &erofs_skip_write_bhops;
-
- /* get blkaddr of bh */
- ret = erofs_mapbh(bh->block);
- DBG_BUGON(ret < 0);
- inode->u.i_blkaddr = bh->block->blkaddr;
-
- inode->bh_data = bh;
- return 0;
+ if (bh) {
+ /* expend a block as the tail block (should be successful) */
+ ret = erofs_bh_balloon(bh, erofs_blksiz());
+ DBG_BUGON(ret != erofs_blksiz());
}
- /* expend a block as the tail block (should be successful) */
- ret = erofs_bh_balloon(bh, erofs_blksiz());
- DBG_BUGON(ret != erofs_blksiz());
return 0;
}
@@ -728,7 +743,20 @@ static int erofs_write_tail_end(struct erofs_inode *inode)
int ret;
erofs_off_t pos, zero_pos;
- erofs_mapbh(bh->block);
+ if (!bh) {
+ bh = erofs_balloc(DATA, erofs_blksiz(), 0, 0);
+ if (IS_ERR(bh))
+ return PTR_ERR(bh);
+ bh->op = &erofs_skip_write_bhops;
+
+ /* get blkaddr of bh */
+ ret = erofs_mapbh(bh->block);
+ inode->u.i_blkaddr = bh->block->blkaddr;
+ inode->bh_data = bh;
+ } else {
+ ret = erofs_mapbh(bh->block);
+ }
+ DBG_BUGON(ret < 0);
pos = erofs_btell(bh, true) - erofs_blksiz();
/* 0'ed data should be padded at head for 0padding conversion */
@@ -911,8 +939,10 @@ static int erofs_fill_inode(struct erofs_inode *inode, struct stat *st,
if (!inode->i_srcpath)
return -ENOMEM;
- inode->dev = st->st_dev;
- inode->i_ino[1] = st->st_ino;
+ if (!S_ISDIR(inode->i_mode)) {
+ inode->dev = st->st_dev;
+ inode->i_ino[1] = st->st_ino;
+ }
if (erofs_should_use_inode_extended(inode)) {
if (cfg.c_force_inodeversion == FORCE_INODE_COMPACT) {
@@ -1003,31 +1033,7 @@ static void erofs_fixup_meta_blkaddr(struct erofs_inode *rootdir)
rootdir->nid = (off - meta_offset) >> EROFS_ISLOTBITS;
}
-erofs_nid_t erofs_lookupnid(struct erofs_inode *inode)
-{
- struct erofs_buffer_head *const bh = inode->bh;
- erofs_off_t off, meta_offset;
-
- if (!bh)
- return inode->nid;
-
- erofs_mapbh(bh->block);
- off = erofs_btell(bh, false);
-
- meta_offset = erofs_pos(sbi.meta_blkaddr);
- DBG_BUGON(off < meta_offset);
- return inode->nid = (off - meta_offset) >> EROFS_ISLOTBITS;
-}
-
-static void erofs_d_invalidate(struct erofs_dentry *d)
-{
- struct erofs_inode *const inode = d->inode;
-
- d->nid = erofs_lookupnid(inode);
- erofs_iput(inode);
-}
-
-static struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
+static int erofs_mkfs_build_tree(struct erofs_inode *dir, struct list_head *dirs)
{
int ret;
DIR *_dir;
@@ -1037,40 +1043,37 @@ static struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
ret = erofs_prepare_xattr_ibody(dir);
if (ret < 0)
- return ERR_PTR(ret);
+ return ret;
if (!S_ISDIR(dir->i_mode)) {
if (S_ISLNK(dir->i_mode)) {
char *const symlink = malloc(dir->i_size);
if (!symlink)
- return ERR_PTR(-ENOMEM);
+ return -ENOMEM;
ret = readlink(dir->i_srcpath, symlink, dir->i_size);
if (ret < 0) {
free(symlink);
- return ERR_PTR(-errno);
+ return -errno;
}
-
ret = erofs_write_file_from_buffer(dir, symlink);
free(symlink);
- if (ret)
- return ERR_PTR(ret);
} else {
ret = erofs_write_file(dir);
- if (ret)
- return ERR_PTR(ret);
}
+ if (ret)
+ return ret;
erofs_prepare_inode_buffer(dir);
erofs_write_tail_end(dir);
- return dir;
+ return 0;
}
_dir = opendir(dir->i_srcpath);
if (!_dir) {
erofs_err("failed to opendir at %s: %s",
dir->i_srcpath, erofs_strerror(errno));
- return ERR_PTR(-errno);
+ return -errno;
}
nr_subdirs = 0;
@@ -1111,23 +1114,23 @@ static struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
ret = erofs_prepare_dir_file(dir, nr_subdirs);
if (ret)
- goto err;
+ return ret;
ret = erofs_prepare_inode_buffer(dir);
if (ret)
- goto err;
+ return ret;
+ dir->bh->op = &erofs_skip_write_bhops;
if (IS_ROOT(dir))
erofs_fixup_meta_blkaddr(dir);
list_for_each_entry(d, &dir->i_subdirs, d_child) {
- char buf[PATH_MAX], *trimmed;
+ char buf[PATH_MAX];
unsigned char ftype;
+ struct erofs_inode *inode;
- if (is_dot_dotdot(d->name)) {
- erofs_d_invalidate(d);
+ if (is_dot_dotdot(d->name))
continue;
- }
ret = snprintf(buf, PATH_MAX, "%s/%s",
dir->i_srcpath, d->name);
@@ -1136,59 +1139,88 @@ static struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
goto fail;
}
- trimmed = erofs_trim_for_progressinfo(erofs_fspath(buf),
- sizeof("Processing ...") - 1);
- erofs_update_progressinfo("Processing %s ...", trimmed);
- free(trimmed);
- d->inode = erofs_mkfs_build_tree_from_path(dir, buf);
- if (IS_ERR(d->inode)) {
- ret = PTR_ERR(d->inode);
+ inode = erofs_iget_from_path(buf, true);
+
+ if (IS_ERR(inode)) {
+ ret = PTR_ERR(inode);
fail:
d->inode = NULL;
d->type = EROFS_FT_UNKNOWN;
- goto err;
+ return ret;
}
- ftype = erofs_mode_to_ftype(d->inode->i_mode);
+ /* a hardlink to the existed inode */
+ if (inode->i_parent) {
+ ++inode->i_nlink;
+ } else {
+ inode->i_parent = dir;
+ erofs_igrab(inode);
+ list_add_tail(&inode->i_subdirs, dirs);
+ ++dir->subdirs_queued;
+ }
+ ftype = erofs_mode_to_ftype(inode->i_mode);
DBG_BUGON(ftype == EROFS_FT_DIR && d->type != ftype);
+ d->inode = inode;
d->type = ftype;
-
- erofs_d_invalidate(d);
- erofs_info("add file %s/%s (nid %llu, type %u)",
- dir->i_srcpath, d->name, (unsigned long long)d->nid,
- d->type);
+ erofs_info("file %s/%s dumped (type %u)",
+ dir->i_srcpath, d->name, d->type);
}
- erofs_write_dir_file(dir);
- erofs_write_tail_end(dir);
- return dir;
+ return 0;
err_closedir:
closedir(_dir);
-err:
- return ERR_PTR(ret);
+ return ret;
}
-struct erofs_inode *erofs_mkfs_build_tree_from_path(struct erofs_inode *parent,
- const char *path)
+static void erofs_mkfs_dump_directory(struct erofs_inode *dir)
{
- struct erofs_inode *const inode = erofs_iget_from_path(path, true);
+ erofs_write_dir_file(dir);
+ erofs_write_tail_end(dir);
+ dir->bh->op = &erofs_write_inode_bhops;
+}
- if (IS_ERR(inode))
- return inode;
+struct erofs_inode *erofs_mkfs_build_tree_from_path(const char *path)
+{
+ LIST_HEAD(dirs);
+ struct erofs_inode *inode, *root, *parent;
- /* a hardlink to the existed inode */
- if (inode->i_parent) {
- ++inode->i_nlink;
- return inode;
- }
+ root = erofs_igrab(erofs_iget_from_path(path, true));
+ if (IS_ERR(root))
+ return root;
- /* a completely new inode is found */
- if (parent)
- inode->i_parent = parent;
- else
- inode->i_parent = inode; /* rootdir mark */
+ root->i_parent = root; /* rootdir mark */
+ root->subdirs_queued = 1;
+ list_add(&root->i_subdirs, &dirs);
- return erofs_mkfs_build_tree(inode);
+ do {
+ int err;
+ char *trimmed;
+
+ inode = list_first_entry(&dirs, struct erofs_inode, i_subdirs);
+ list_del(&inode->i_subdirs);
+ init_list_head(&inode->i_subdirs);
+
+ trimmed = erofs_trim_for_progressinfo(
+ erofs_fspath(inode->i_srcpath),
+ sizeof("Processing ...") - 1);
+ erofs_update_progressinfo("Processing %s ...", trimmed);
+ free(trimmed);
+
+ err = erofs_mkfs_build_tree(inode, &dirs);
+ if (err) {
+ root = ERR_PTR(err);
+ break;
+ }
+ parent = inode->i_parent;
+
+ DBG_BUGON(!parent->subdirs_queued);
+ if (S_ISDIR(inode->i_mode) && !inode->subdirs_queued)
+ erofs_mkfs_dump_directory(inode);
+ if (!--parent->subdirs_queued)
+ erofs_mkfs_dump_directory(parent);
+ erofs_iput(inode);
+ } while (!list_empty(&dirs));
+ return root;
}
struct erofs_inode *erofs_mkfs_build_special_from_fd(int fd, const char *name)
diff --git a/mkfs/main.c b/mkfs/main.c
index f4d2330..a05d4f9 100644
--- a/mkfs/main.c
+++ b/mkfs/main.c
@@ -856,7 +856,7 @@ int main(int argc, char **argv)
goto exit;
}
- root_inode = erofs_mkfs_build_tree_from_path(NULL, cfg.c_src_path);
+ root_inode = erofs_mkfs_build_tree_from_path(cfg.c_src_path);
if (IS_ERR(root_inode)) {
err = PTR_ERR(root_inode);
goto exit;
--
2.24.4
More information about the Linux-erofs
mailing list