Btrfs: allocator improvements, inode block groups
Signed-off-by: Chris Mason <chris.mason@oracle.com>
diff --git a/fs/btrfs/btrfs_inode.h b/fs/btrfs/btrfs_inode.h
index 43a4f1dd..6b50076 100644
--- a/fs/btrfs/btrfs_inode.h
+++ b/fs/btrfs/btrfs_inode.h
@@ -3,6 +3,7 @@
struct btrfs_inode {
struct btrfs_root *root;
+ struct btrfs_block_group_cache *block_group;
struct btrfs_key location;
struct inode vfs_inode;
};
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index b4783bf..dbd3f63 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -61,7 +61,7 @@
*cow_ret = buf;
return 0;
}
- cow = btrfs_alloc_free_block(trans, root);
+ cow = btrfs_alloc_free_block(trans, root, buf->b_blocknr);
cow_node = btrfs_buffer_node(cow);
if (buf->b_size != root->blocksize || cow->b_size != root->blocksize)
WARN_ON(1);
@@ -800,7 +800,7 @@
BUG_ON(path->nodes[level]);
BUG_ON(path->nodes[level-1] != root->node);
- t = btrfs_alloc_free_block(trans, root);
+ t = btrfs_alloc_free_block(trans, root, root->node->b_blocknr);
c = btrfs_buffer_node(t);
memset(c, 0, root->blocksize);
btrfs_set_header_nritems(&c->header, 1);
@@ -905,7 +905,7 @@
}
c_nritems = btrfs_header_nritems(&c->header);
- split_buffer = btrfs_alloc_free_block(trans, root);
+ split_buffer = btrfs_alloc_free_block(trans, root, t->b_blocknr);
split = btrfs_buffer_node(split_buffer);
btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header));
btrfs_set_header_level(&split->header, btrfs_header_level(&c->header));
@@ -1277,7 +1277,7 @@
slot = path->slots[0];
nritems = btrfs_header_nritems(&l->header);
mid = (nritems + 1)/ 2;
- right_buffer = btrfs_alloc_free_block(trans, root);
+ right_buffer = btrfs_alloc_free_block(trans, root, l_buf->b_blocknr);
BUG_ON(!right_buffer);
right = btrfs_buffer_leaf(right_buffer);
memset(&right->header, 0, sizeof(right->header));
@@ -1374,7 +1374,7 @@
if (!double_split)
return ret;
- right_buffer = btrfs_alloc_free_block(trans, root);
+ right_buffer = btrfs_alloc_free_block(trans, root, l_buf->b_blocknr);
BUG_ON(!right_buffer);
right = btrfs_buffer_leaf(right_buffer);
memset(&right->header, 0, sizeof(right->header));
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index c432222..e6bf991 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -174,6 +174,7 @@
__le64 generation;
__le64 size;
__le64 nblocks;
+ __le64 block_group;
__le32 nlink;
__le32 uid;
__le32 gid;
@@ -241,6 +242,7 @@
/* tag for the radix tree of block groups in ram */
#define BTRFS_BLOCK_GROUP_DIRTY 0
+#define BTRFS_BLOCK_GROUP_AVAIL 1
#define BTRFS_BLOCK_GROUP_HINTS 8
#define BTRFS_BLOCK_GROUP_SIZE (256 * 1024 * 1024)
struct btrfs_block_group_item {
@@ -410,6 +412,17 @@
i->nblocks = cpu_to_le64(val);
}
+static inline u64 btrfs_inode_block_group(struct btrfs_inode_item *i)
+{
+ return le64_to_cpu(i->block_group);
+}
+
+static inline void btrfs_set_inode_block_group(struct btrfs_inode_item *i,
+ u64 val)
+{
+ i->block_group = cpu_to_le64(val);
+}
+
static inline u32 btrfs_inode_nlink(struct btrfs_inode_item *i)
{
return le32_to_cpu(i->nlink);
@@ -1054,10 +1067,13 @@
btrfs_item_offset((leaf)->items + (slot))))
/* extent-tree.c */
+struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
+ struct btrfs_block_group_cache
+ *hint, int data);
int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
struct btrfs_root *root);
struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
- struct btrfs_root *root);
+ struct btrfs_root *root, u64 hint);
int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
struct btrfs_root *root, u64 owner,
u64 num_blocks, u64 search_start,
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 62051a3..8b8cbe2 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -12,42 +12,57 @@
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
btrfs_root *extent_root);
-static int find_search_start(struct btrfs_root *root, int data)
+struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
+ struct btrfs_block_group_cache
+ *hint, int data)
{
struct btrfs_block_group_cache *cache[8];
+ struct btrfs_block_group_cache *found_group = NULL;
struct btrfs_fs_info *info = root->fs_info;
u64 used;
- u64 last;
+ u64 last = 0;
+ u64 hint_last;
int i;
int ret;
-
- cache[0] = info->block_group_cache;
- if (!cache[0])
- goto find_new;
- used = btrfs_block_group_used(&cache[0]->item);
- if (used < (cache[0]->key.offset * 3 / 2))
- return 0;
-find_new:
- last = 0;
+ int full_search = 0;
+ if (hint) {
+ used = btrfs_block_group_used(&hint->item);
+ if (used < (hint->key.offset * 2) / 3) {
+ return hint;
+ }
+ radix_tree_tag_clear(&info->block_group_radix,
+ hint->key.objectid + hint->key.offset - 1,
+ BTRFS_BLOCK_GROUP_AVAIL);
+ last = hint->key.objectid + hint->key.offset;
+ hint_last = last;
+ } else {
+ hint_last = 0;
+ last = 0;
+ }
while(1) {
ret = radix_tree_gang_lookup_tag(&info->block_group_radix,
(void **)cache,
last, ARRAY_SIZE(cache),
- BTRFS_BLOCK_GROUP_DIRTY);
+ BTRFS_BLOCK_GROUP_AVAIL);
if (!ret)
break;
for (i = 0; i < ret; i++) {
used = btrfs_block_group_used(&cache[i]->item);
- if (used < (cache[i]->key.offset * 3 / 2)) {
+ if (used < (cache[i]->key.offset * 2) / 3) {
info->block_group_cache = cache[i];
- cache[i]->last_alloc = cache[i]->first_free;
- return 0;
+ found_group = cache[i];
+ goto found;
}
+ radix_tree_tag_clear(&info->block_group_radix,
+ cache[i]->key.objectid +
+ cache[i]->key.offset - 1,
+ BTRFS_BLOCK_GROUP_AVAIL);
last = cache[i]->key.objectid +
- cache[i]->key.offset - 1;
+ cache[i]->key.offset;
}
}
- last = 0;
+ last = hint_last;
+again:
while(1) {
ret = radix_tree_gang_lookup(&info->block_group_radix,
(void **)cache,
@@ -56,17 +71,32 @@
break;
for (i = 0; i < ret; i++) {
used = btrfs_block_group_used(&cache[i]->item);
- if (used < (cache[i]->key.offset * 3 / 2)) {
+ if (used < cache[i]->key.offset) {
info->block_group_cache = cache[i];
- cache[i]->last_alloc = cache[i]->first_free;
- return 0;
+ found_group = cache[i];
+ goto found;
}
+ radix_tree_tag_clear(&info->block_group_radix,
+ cache[i]->key.objectid +
+ cache[i]->key.offset - 1,
+ BTRFS_BLOCK_GROUP_AVAIL);
last = cache[i]->key.objectid +
- cache[i]->key.offset - 1;
+ cache[i]->key.offset;
}
}
info->block_group_cache = NULL;
- return 0;
+ if (!full_search) {
+ last = 0;
+ full_search = 1;
+ goto again;
+ }
+found:
+ if (!found_group) {
+ ret = radix_tree_gang_lookup(&info->block_group_radix,
+ (void **)&found_group, 0, 1);
+ BUG_ON(ret != 1);
+ }
+ return found_group;
}
int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
@@ -243,6 +273,7 @@
path, cache[i]);
if (err)
werr = err;
+ cache[i]->last_alloc = cache[i]->first_free;
}
}
btrfs_free_path(path);
@@ -322,10 +353,6 @@
btree_inode->i_blkbits));
}
}
- if (root->fs_info->block_group_cache) {
- root->fs_info->block_group_cache->last_alloc =
- root->fs_info->block_group_cache->first_free;
- }
return 0;
}
@@ -532,22 +559,43 @@
int total_found = 0;
int fill_prealloc = 0;
int level;
+ int update_block_group = 0;
+ struct btrfs_block_group_cache *hint_block_group;
path = btrfs_alloc_path();
ins->flags = 0;
btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
level = btrfs_header_level(btrfs_buffer_header(root->node));
+ /* find search start here */
+ if (0 && search_start && num_blocks) {
+ u64 used;
+ ret = radix_tree_gang_lookup(&info->block_group_radix,
+ (void **)&hint_block_group,
+ search_start, 1);
+ if (ret) {
+ used = btrfs_block_group_used(&hint_block_group->item);
+ if (used > (hint_block_group->key.offset * 9) / 10)
+ search_start = 0;
+ else if (search_start < hint_block_group->last_alloc)
+ search_start = hint_block_group->last_alloc;
+ } else {
+ search_start = 0;
+ }
+ }
if (num_blocks == 0) {
fill_prealloc = 1;
num_blocks = 1;
total_needed = (min(level + 1, BTRFS_MAX_LEVEL) + 2) * 3;
}
- find_search_start(root, 0);
- if (info->block_group_cache &&
- info->block_group_cache->last_alloc > search_start)
- search_start = info->block_group_cache->last_alloc;
-
+ if (1 || !search_start) {
+ trans->block_group = btrfs_find_block_group(root,
+ trans->block_group,
+ 0);
+ if (trans->block_group->last_alloc > search_start)
+ search_start = trans->block_group->last_alloc;
+ update_block_group = 1;
+ }
check_failed:
btrfs_init_path(path);
ins->objectid = search_start;
@@ -662,11 +710,13 @@
}
info->extent_tree_prealloc_nr = total_found;
}
- ret = radix_tree_gang_lookup(&info->block_group_radix,
- (void **)&info->block_group_cache,
- ins->objectid, 1);
- if (ret) {
- info->block_group_cache->last_alloc = ins->objectid;
+ if (update_block_group) {
+ ret = radix_tree_gang_lookup(&info->block_group_radix,
+ (void **)&trans->block_group,
+ ins->objectid, 1);
+ if (ret) {
+ trans->block_group->last_alloc = ins->objectid;
+ }
}
ins->offset = num_blocks;
btrfs_free_path(path);
@@ -747,14 +797,14 @@
* returns the tree buffer or NULL.
*/
struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
- struct btrfs_root *root)
+ struct btrfs_root *root, u64 hint)
{
struct btrfs_key ins;
int ret;
struct buffer_head *buf;
ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
- 1, 0, (unsigned long)-1, &ins);
+ 1, hint, (unsigned long)-1, &ins);
if (ret) {
BUG();
return NULL;
@@ -975,6 +1025,7 @@
struct btrfs_key found_key;
struct btrfs_leaf *leaf;
u64 group_size_blocks = BTRFS_BLOCK_GROUP_SIZE / root->blocksize;
+ u64 used;
root = root->fs_info->extent_root;
key.objectid = 0;
@@ -1005,8 +1056,8 @@
struct btrfs_block_group_item);
memcpy(&cache->item, bi, sizeof(*bi));
memcpy(&cache->key, &found_key, sizeof(found_key));
- cache->last_alloc = 0;
- cache->first_free = 0;
+ cache->last_alloc = cache->key.objectid;
+ cache->first_free = cache->key.objectid;
key.objectid = found_key.objectid + found_key.offset;
btrfs_release_path(root, path);
ret = radix_tree_insert(&root->fs_info->block_group_radix,
@@ -1014,6 +1065,13 @@
found_key.offset - 1,
(void *)cache);
BUG_ON(ret);
+ used = btrfs_block_group_used(bi);
+ if (used < (key.offset * 2) / 3) {
+ radix_tree_tag_set(&root->fs_info->block_group_radix,
+ found_key.objectid +
+ found_key.offset - 1,
+ BTRFS_BLOCK_GROUP_AVAIL);
+ }
if (key.objectid >=
btrfs_super_total_blocks(root->fs_info->disk_super))
break;
diff --git a/fs/btrfs/super.c b/fs/btrfs/super.c
index 1890e86..7ecbe7c 100644
--- a/fs/btrfs/super.c
+++ b/fs/btrfs/super.c
@@ -52,6 +52,8 @@
struct btrfs_inode_item *inode_item;
struct btrfs_root *root = BTRFS_I(inode)->root;
struct btrfs_key location;
+ struct btrfs_block_group_cache *alloc_group;
+ u64 alloc_group_block;
int ret;
path = btrfs_alloc_path();
@@ -82,6 +84,12 @@
inode->i_ctime.tv_nsec = btrfs_timespec_nsec(&inode_item->ctime);
inode->i_blocks = btrfs_inode_nblocks(inode_item);
inode->i_generation = btrfs_inode_generation(inode_item);
+ alloc_group_block = btrfs_inode_block_group(inode_item);
+ ret = radix_tree_gang_lookup(&root->fs_info->block_group_radix,
+ (void **)&alloc_group,
+ alloc_group_block, 1);
+ BUG_ON(!ret);
+ BTRFS_I(inode)->block_group = alloc_group;
btrfs_free_path(path);
inode_item = NULL;
@@ -136,6 +144,8 @@
btrfs_set_timespec_nsec(&item->ctime, inode->i_ctime.tv_nsec);
btrfs_set_inode_nblocks(item, inode->i_blocks);
btrfs_set_inode_generation(item, inode->i_generation);
+ btrfs_set_inode_block_group(item,
+ BTRFS_I(inode)->block_group->key.objectid);
}
@@ -237,6 +247,7 @@
root = BTRFS_I(dir)->root;
mutex_lock(&root->fs_info->fs_mutex);
trans = btrfs_start_transaction(root, 1);
+ btrfs_set_trans_block_group(trans, dir);
ret = btrfs_unlink_trans(trans, root, dir, dentry);
btrfs_end_transaction(trans, root);
mutex_unlock(&root->fs_info->fs_mutex);
@@ -262,6 +273,7 @@
btrfs_init_path(path);
mutex_lock(&root->fs_info->fs_mutex);
trans = btrfs_start_transaction(root, 1);
+ btrfs_set_trans_block_group(trans, dir);
key.objectid = inode->i_ino;
key.offset = (u64)-1;
key.flags = (u32)-1;
@@ -429,6 +441,7 @@
inode->i_size = 0;
mutex_lock(&root->fs_info->fs_mutex);
trans = btrfs_start_transaction(root, 1);
+ btrfs_set_trans_block_group(trans, inode);
if (S_ISREG(inode->i_mode)) {
ret = btrfs_truncate_in_trans(trans, root, inode);
BUG_ON(ret);
@@ -731,6 +744,7 @@
if (wait) {
mutex_lock(&root->fs_info->fs_mutex);
trans = btrfs_start_transaction(root, 1);
+ btrfs_set_trans_block_group(trans, inode);
ret = btrfs_commit_transaction(trans, root);
mutex_unlock(&root->fs_info->fs_mutex);
}
@@ -744,6 +758,7 @@
mutex_lock(&root->fs_info->fs_mutex);
trans = btrfs_start_transaction(root, 1);
+ btrfs_set_trans_block_group(trans, inode);
btrfs_update_inode(trans, root, inode);
btrfs_end_transaction(trans, root);
mutex_unlock(&root->fs_info->fs_mutex);
@@ -751,7 +766,9 @@
static struct inode *btrfs_new_inode(struct btrfs_trans_handle *trans,
struct btrfs_root *root,
- u64 objectid, int mode)
+ u64 objectid,
+ struct btrfs_block_group_cache *group,
+ int mode)
{
struct inode *inode;
struct btrfs_inode_item inode_item;
@@ -763,6 +780,8 @@
return ERR_PTR(-ENOMEM);
BTRFS_I(inode)->root = root;
+ group = btrfs_find_block_group(root, group, 0);
+ BTRFS_I(inode)->block_group = group;
inode->i_uid = current->fsuid;
inode->i_gid = current->fsgid;
@@ -832,6 +851,7 @@
mutex_lock(&root->fs_info->fs_mutex);
trans = btrfs_start_transaction(root, 1);
+ btrfs_set_trans_block_group(trans, dir);
err = btrfs_find_free_objectid(trans, root, dir->i_ino, &objectid);
if (err) {
@@ -839,11 +859,13 @@
goto out_unlock;
}
- inode = btrfs_new_inode(trans, root, objectid, mode);
+ inode = btrfs_new_inode(trans, root, objectid,
+ BTRFS_I(dir)->block_group, mode);
err = PTR_ERR(inode);
if (IS_ERR(inode))
goto out_unlock;
- // FIXME mark the inode dirty
+
+ btrfs_set_trans_block_group(trans, inode);
err = btrfs_add_nondir(trans, dentry, inode);
if (err)
drop_inode = 1;
@@ -853,6 +875,8 @@
inode->i_op = &btrfs_file_inode_operations;
}
dir->i_sb->s_dirt = 1;
+ btrfs_update_inode_block_group(trans, inode);
+ btrfs_update_inode_block_group(trans, dir);
out_unlock:
btrfs_end_transaction(trans, root);
mutex_unlock(&root->fs_info->fs_mutex);
@@ -904,6 +928,7 @@
mutex_lock(&root->fs_info->fs_mutex);
trans = btrfs_start_transaction(root, 1);
+ btrfs_set_trans_block_group(trans, dir);
if (IS_ERR(trans)) {
err = PTR_ERR(trans);
goto out_unlock;
@@ -915,7 +940,8 @@
goto out_unlock;
}
- inode = btrfs_new_inode(trans, root, objectid, S_IFDIR | mode);
+ inode = btrfs_new_inode(trans, root, objectid,
+ BTRFS_I(dir)->block_group, S_IFDIR | mode);
if (IS_ERR(inode)) {
err = PTR_ERR(inode);
goto out_fail;
@@ -923,6 +949,7 @@
drop_on_err = 1;
inode->i_op = &btrfs_dir_inode_operations;
inode->i_fop = &btrfs_dir_file_operations;
+ btrfs_set_trans_block_group(trans, inode);
err = btrfs_make_empty_dir(trans, root, inode->i_ino, dir->i_ino);
if (err)
@@ -938,6 +965,8 @@
d_instantiate(dentry, inode);
drop_on_err = 0;
dir->i_sb->s_dirt = 1;
+ btrfs_update_inode_block_group(trans, inode);
+ btrfs_update_inode_block_group(trans, dir);
out_fail:
btrfs_end_transaction(trans, root);
@@ -1349,6 +1378,7 @@
/* FIXME, add redo link to tree so we don't leak on crash */
mutex_lock(&root->fs_info->fs_mutex);
trans = btrfs_start_transaction(root, 1);
+ btrfs_set_trans_block_group(trans, inode);
ret = btrfs_truncate_in_trans(trans, root, inode);
BUG_ON(ret);
ret = btrfs_end_transaction(trans, root);
@@ -1445,6 +1475,7 @@
mutex_lock(&root->fs_info->fs_mutex);
trans = btrfs_start_transaction(root, 1);
+ btrfs_set_trans_block_group(trans, inode);
bh = page_buffers(pages[i]);
if (buffer_mapped(bh) && bh->b_blocknr == 0) {
@@ -1481,6 +1512,7 @@
kunmap(pages[i]);
}
SetPageChecked(pages[i]);
+ btrfs_update_inode_block_group(trans, inode);
ret = btrfs_end_transaction(trans, root);
BUG_ON(ret);
mutex_unlock(&root->fs_info->fs_mutex);
@@ -1821,6 +1853,7 @@
mutex_unlock(&root->fs_info->fs_mutex);
goto out_unlock;
}
+ btrfs_set_trans_block_group(trans, inode);
/* FIXME blocksize != 4096 */
inode->i_blocks += num_blocks << 3;
if (start_pos < inode->i_size) {
@@ -1845,6 +1878,7 @@
}
BUG_ON(ret);
alloc_extent_start = ins.objectid;
+ btrfs_update_inode_block_group(trans, inode);
ret = btrfs_end_transaction(trans, root);
mutex_unlock(&root->fs_info->fs_mutex);
@@ -2017,6 +2051,7 @@
struct btrfs_leaf *leaf;
struct btrfs_root *new_root;
struct inode *inode;
+ struct inode *dir;
int ret;
u64 objectid;
u64 new_dirid = BTRFS_FIRST_FREE_OBJECTID;
@@ -2025,7 +2060,7 @@
trans = btrfs_start_transaction(root, 1);
BUG_ON(!trans);
- subvol = btrfs_alloc_free_block(trans, root);
+ subvol = btrfs_alloc_free_block(trans, root, 0);
if (subvol == NULL)
return -ENOSPC;
leaf = btrfs_buffer_leaf(subvol);
@@ -2069,10 +2104,9 @@
* insert the directory item
*/
key.offset = (u64)-1;
+ dir = root->fs_info->sb->s_root->d_inode;
ret = btrfs_insert_dir_item(trans, root->fs_info->tree_root,
- name, namelen,
- root->fs_info->sb->s_root->d_inode->i_ino,
- &key, 0);
+ name, namelen, dir->i_ino, &key, 0);
BUG_ON(ret);
ret = btrfs_commit_transaction(trans, root);
@@ -2084,7 +2118,8 @@
trans = btrfs_start_transaction(new_root, 1);
BUG_ON(!trans);
- inode = btrfs_new_inode(trans, new_root, new_dirid, S_IFDIR | 0700);
+ inode = btrfs_new_inode(trans, new_root, new_dirid,
+ BTRFS_I(dir)->block_group, S_IFDIR | 0700);
inode->i_op = &btrfs_dir_inode_operations;
inode->i_fop = &btrfs_dir_file_operations;
diff --git a/fs/btrfs/transaction.c b/fs/btrfs/transaction.c
index f9b8864..bdbf514 100644
--- a/fs/btrfs/transaction.c
+++ b/fs/btrfs/transaction.c
@@ -77,6 +77,7 @@
h->transaction = root->fs_info->running_transaction;
h->blocks_reserved = num_blocks;
h->blocks_used = 0;
+ h->block_group = NULL;
root->fs_info->running_transaction->use_count++;
mutex_unlock(&root->fs_info->trans_mutex);
h->magic = h->magic2 = TRANS_MAGIC;
diff --git a/fs/btrfs/transaction.h b/fs/btrfs/transaction.h
index afe42d1..b537811 100644
--- a/fs/btrfs/transaction.h
+++ b/fs/btrfs/transaction.h
@@ -1,5 +1,6 @@
#ifndef __TRANSACTION__
#define __TRANSACTION__
+#include "btrfs_inode.h"
struct btrfs_transaction {
u64 transid;
@@ -20,10 +21,24 @@
unsigned long blocks_reserved;
unsigned long blocks_used;
struct btrfs_transaction *transaction;
+ struct btrfs_block_group_cache *block_group;
int magic2;
};
+static inline void btrfs_set_trans_block_group(struct btrfs_trans_handle *trans,
+ struct inode *inode)
+{
+ trans->block_group = BTRFS_I(inode)->block_group;
+}
+
+static inline void btrfs_update_inode_block_group(struct
+ btrfs_trans_handle *trans,
+ struct inode *inode)
+{
+ BTRFS_I(inode)->block_group = trans->block_group;
+}
+
int btrfs_end_transaction(struct btrfs_trans_handle *trans,
struct btrfs_root *root);
struct btrfs_trans_handle *btrfs_start_transaction(struct btrfs_root *root,