btrfs: hardening against radix tree conflicts on 32bit systems
cover btrfs: hardening against radix tree conflicts on 32bit systems
Inspired by a recent patch touching btrfs_ioctl_subvol_sync() function, it turns out that we have a very rare (I'd even call it unpractical) but still real (one can even craft one image) problem, that on 32-bit systems, we always truncate the subvolid down to 32bit unsigned long.
This means the following two valid subvolume trees will get the same index:
Subvolume 257 (0x101) and subvolume 4294967553 (0x100000101)
It should really be very rare, as we have other limits like anon_dev, which should hit way before subvolumeid limits.
But one can craft an image with only above two subvolumes, and on 32bit systems only one subvolume can be reached.
Address the situation by:
- Do not insert data reloc tree into fs_roots_radix
As we will reject subvolume ids > ULONG_MAX on 32 bit systems, we don't want to insert data reloc tree into that radix tree in the first place.
- Reject subvolume ids > ULONG_MAX
For 64 bits this will become an no-op.
For 32 bits, most subvolumes should still have their ids <= ULONG_MAX.
For crafted images, subvolumes ids larger than ULONG_MAX will be rejected with a rate-limited error message every time such subvolume is going to be inserted.
This can lead to some transaction abort, e.g. createing a snapshot whose id is too large.
But I don't have better solution than rejecting them.
Qu Wenruo (2):
btrfs: do not insert the data reloc tree into fs_roots_radix
btrfs: reject subvolume ids that do not fit into unsigned long
fs/btrfs/disk-io.c | 64 +++++++++++++++++++++++++++++++++++++++------- fs/btrfs/disk-io.h | 19 ++++++++++++++ fs/btrfs/ioctl.c | 2 +- 3 files changed, 75 insertions(+), 10 deletions(-)
Signature · 1 line
2.56.0
PATCH 1/2 btrfs: do not insert the data reloc tree into fs_roots_radix
The reasons not to do so are:
- There is already a global pointer fs_info->data_reloc_root And data reloc tree itself has TRACK_DIRTY flag set, thus its treated as a COW-only root, not a SHAREABLE root, unlike regular subvolume trees.
- 32-bit conflicts
For 32-bit systems, radix tree index is always truncated to 32 bits.
This means a subvolume with id 0xfffffff7, will conflict with the truncated data reloc tree id (0xfffffffffffffff7 -> 0xfffffff7).
This will prevent btrfs from reading or creating such subvolume. Thankfully this should be very rare, as the subvolume id is reusable, and it's very hard to keep so many subvolumes before hitting other limits (e.g. anon_dev limits).
So change the code to not insert data reloc tree into fs_roots_radix:
- Load the tree with a dedicated helper
The new helper, read_data_reloc_root() will call btrfs_read_tree_root(), with refs check, then call btrfs_init_fs_root().
It skips the fs_roots_radix tree insert completely.
- Grab data_reloc_tree as a global root
--- fs/btrfs/disk-io.c | 51 ++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 42 insertions(+), 9 deletions(-)
fs/btrfs/disk-io.c +42 -9
@@ -1169,6 +1169,8 @@ static struct btrfs_root *btrfs_get_global_root(struct btrfs_fs_info *fs_info,return btrfs_grab_root (fs_info->stripe_root);case BTRFS_REMAP_TREE_OBJECTID :return btrfs_grab_root (fs_info->remap_root); +case BTRFS_DATA_RELOC_TREE_OBJECTID : +return btrfs_grab_root (fs_info->data_reloc_root);default :return NULL ; }
@@ -1304,8 +1306,13 @@ static struct btrfs_root *btrfs_get_root_ref(struct btrfs_fs_info *fs_info,* * This is namely for free-space-tree and quota tree, which can change * at runtime and should only be grabbed from fs_info. +* +* The data reloc tree is also such a tree. It is loaded at mount time +* by read_data_reloc_root() and never inserted into the radix tree, as +* its objectid is truncated to the radix tree index on 32-bit systems +* and can conflict with a real subvolume. */ -if (!btrfs_is_fstree (objectid) && objectid !=BTRFS_DATA_RELOC_TREE_OBJECTID ) +if (!btrfs_is_fstree (objectid))return ERR_PTR (-ENOENT ); again: root =btrfs_lookup_fs_root (fs_info, objectid);
@@ -1409,6 +1416,39 @@ struct btrfs_root *btrfs_get_new_fs_root(struct btrfs_fs_info *fs_info,return btrfs_get_root_ref (fs_info, objectid, anon_dev, true); } +/* Read and initialize the data reloc tree. */ +static struct btrfs_root *read_data_reloc_root (struct btrfs_fs_info *fs_info) +{ +struct btrfs_key key = { + .objectid =BTRFS_DATA_RELOC_TREE_OBJECTID , + .type =BTRFS_ROOT_ITEM_KEY , + .offset = (u64)-1 , + }; +struct btrfs_root *root; +int ret; + + root =btrfs_read_tree_root (fs_info->tree_root, &key); +if (IS_ERR (root)) +return root; + +if (btrfs_root_refs (&root->root_item) ==0 ) { + ret = -ENOENT ; + goto fail; + } + +/* +* This tree can share blocks with some other fs tree during +* relocation and we need a proper setup by btrfs_init_fs_root(). +*/ + ret =btrfs_init_fs_root (root,0 ); +if (ret) + goto fail; +return root; +fail: +btrfs_put_root (root); +return ERR_PTR (ret); +} +/* * Return a root for the given objectid. *
@@ -2275,12 +2315,7 @@ static int btrfs_read_roots(struct btrfs_fs_info *fs_info) PTR_ERR(root)); } }else { -/* -* This tree can share blocks with some other fs tree during -* relocation and we need a proper setup by btrfs_get_fs_root(). -*/ - root =btrfs_get_fs_root (tree_root->fs_info, -BTRFS_DATA_RELOC_TREE_OBJECTID , true); + root =read_data_reloc_root (fs_info);if (IS_ERR (root)) {if (!btrfs_test_opt (fs_info,IGNOREBADROOTS )) { location.objectid =BTRFS_DATA_RELOC_TREE_OBJECTID ;
@@ -3815,8 +3850,6 @@ int __cold open_ctree(struct super_block *sb, struct btrfs_fs_devices *fs_devicebtrfs_put_block_group_cache (fs_info); fail_tree_roots: -if (fs_info->data_reloc_root) -btrfs_drop_and_free_fs_root (fs_info, fs_info->data_reloc_root);free_root_pointers (fs_info, true);invalidate_and_check_btree_folios (fs_info);
Signature · 1 line
2.56.0
Re: [PATCH 1/2] btrfs: do not insert the data reloc tree into fs_roots_radix
Quoted 10 lines · Qu Wenruo
The reasons not to do so are:
- There is already a global pointer
fs_info->data_reloc_rootAnd data reloc tree itself hasTRACK_DIRTYflag set, thus its treated as a COW-only root, not a SHAREABLE root, unlike regular subvolume trees.- 32-bit conflicts
For 32-bit systems, radix tree index is always truncated to 32 bits.
I think it's clearer to say that radix tree keys are unsigned longs, and therefore on 32-bit platforms they are 32 bits wide.
Quoted 39 lines
This means a subvolume with id
0xfffffff7, will conflict with the truncated data reloc tree id (0xfffffffffffffff7->0xfffffff7).This will prevent btrfs from reading or creating such subvolume. Thankfully this should be very rare, as the subvolume id is reusable, and it's very hard to keep so many subvolumes before hitting other limits (e.g.
anon_devlimits).So change the code to not insert data reloc tree into
fs_roots_radix:- Load the tree with a dedicated helper
The new helper,read_data_reloc_root()will callbtrfs_read_tree_root(), with refs check, then callbtrfs_init_fs_root().It skips the
fs_roots_radixtree insert completely.- Grab
data_reloc_treeas a global rootSigned-off-by Qu Wenruo <[email protected]>--- fs/btrfs/disk-io.c | 51 ++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 42 insertions(+), 9 deletions(-)fs/btrfs/disk-io.c +2
-0@@ -1169,6 +1169,8 @@ static struct btrfs_root *btrfs_get_global_root(struct btrfs_fs_info *fs_info,return btrfs_grab_root (fs_info->stripe_root);case BTRFS_REMAP_TREE_OBJECTID :return btrfs_grab_root (fs_info->remap_root); +case BTRFS_DATA_RELOC_TREE_OBJECTID : +return btrfs_grab_root (fs_info->data_reloc_root);default :return NULL ; }
fs/btrfs/disk-io.c static struct btrfs_root *btrfs_get_root_ref(struct btrfs_fs_info *fs_info, · line 1312
Quoted 7 lines
fs/btrfs/disk-io.c +4
-0@@ -1304,8 +1306,13 @@ static struct btrfs_root *btrfs_get_root_ref(struct btrfs_fs_info *fs_info,* * This is namely for free-space-tree and quota tree, which can change * at runtime and should only be grabbed from fs_info. +* +* The data reloc tree is also such a tree. It is loaded at mount time +* by read_data_reloc_root() and never inserted into the radix tree, as +* its objectid is truncated to the radix tree index on 32-bit systems
Same here, something like for example:
... as radix tree keys are of type unsigned long, which is 32 bits wide on 32-bit platforms.
Casting the objectid to unsigned long can therefore result in a conflict with a subvolume.
Anyway:
Thanks.
Quoted 74 lines
fs/btrfs/disk-io.c +36
-10+* and can conflict with a real subvolume. */ -if (!btrfs_is_fstree (objectid) && objectid !=BTRFS_DATA_RELOC_TREE_OBJECTID ) +if (!btrfs_is_fstree (objectid))return ERR_PTR (-ENOENT ); again: root =btrfs_lookup_fs_root (fs_info, objectid);@@ -1409,6 +1416,39 @@ struct btrfs_root *btrfs_get_new_fs_root(struct btrfs_fs_info *fs_info,return btrfs_get_root_ref (fs_info, objectid, anon_dev, true); } +/* Read and initialize the data reloc tree. */ +static struct btrfs_root *read_data_reloc_root (struct btrfs_fs_info *fs_info) +{ +struct btrfs_key key = { + .objectid =BTRFS_DATA_RELOC_TREE_OBJECTID , + .type =BTRFS_ROOT_ITEM_KEY , + .offset = (u64)-1 , + }; +struct btrfs_root *root; +int ret; + + root =btrfs_read_tree_root (fs_info->tree_root, &key); +if (IS_ERR (root)) +return root; + +if (btrfs_root_refs (&root->root_item) ==0 ) { + ret = -ENOENT ; + goto fail; + } + +/* +* This tree can share blocks with some other fs tree during +* relocation and we need a proper setup by btrfs_init_fs_root(). +*/ + ret =btrfs_init_fs_root (root,0 ); +if (ret) + goto fail; +return root; +fail: +btrfs_put_root (root); +return ERR_PTR (ret); +} +/* * Return a root for the given objectid. * @@ -2275,12 +2315,7 @@ static int btrfs_read_roots(struct btrfs_fs_info *fs_info) PTR_ERR(root)); } }else { -/* -* This tree can share blocks with some other fs tree during -* relocation and we need a proper setup by btrfs_get_fs_root(). -*/ - root =btrfs_get_fs_root (tree_root->fs_info, -BTRFS_DATA_RELOC_TREE_OBJECTID , true); + root =read_data_reloc_root (fs_info);if (IS_ERR (root)) {if (!btrfs_test_opt (fs_info,IGNOREBADROOTS )) { location.objectid =BTRFS_DATA_RELOC_TREE_OBJECTID ;@@ -3815,8 +3850,6 @@ int __cold open_ctree(struct super_block *sb, struct btrfs_fs_devices *fs_devicebtrfs_put_block_group_cache (fs_info); fail_tree_roots: -if (fs_info->data_reloc_root) -btrfs_drop_and_free_fs_root (fs_info, fs_info->data_reloc_root);free_root_pointers (fs_info, true);invalidate_and_check_btree_folios (fs_info); --2.56.0
PATCH 2/2 btrfs: reject subvolume ids that do not fit into unsigned long
In reply to Qu Wenruofs_roots_radix is indexed by unsigned long, so on 32-bit systems the subvolume id is silently truncated to 32 bits, e.g:
Subvolume 257 (0x101) and subvolume 4294967553 (0x100000101) will have the same index (0x101) on 32-bit systems.
Although this should be very rare, as btrfs can reuse deleted subvolume ids, and there are other limits like anon_dev preventing us from so many subvolumes.
But it's still better to address such problems, since 32 bit systems are still widely supported by the kernel.
Address such rare problem by:
- Add btrfs_check_subvolid() to btrfs_insert_fs_root()
So that all subvolumes inserted into the fs radix tree are ensured to be no larger than ULONG_MAX.
If there is a high subvolumeid, it will show an error message.
- Do not search the radix tree if subvolid is is too larger It's possible to pass reloc tree into btrfs_lookup_fs_root() through backref walk.
And it can be very common during qgroup operations. So we don't want to flood the dmesg with error messages.
Just silently reject such search silently, and searching tree reloc tree inside btrfs_lookup_fs_root() will return nothing anyway.
--- fs/btrfs/disk-io.c | 13 +++++++++++++ fs/btrfs/disk-io.h | 19 +++++++++++++++++++ fs/btrfs/ioctl.c | 2 +- 3 files changed, 33 insertions(+), 1 deletion(-)
fs/btrfs/disk-io.c +13 -0
@@ -1129,6 +1129,15 @@ static struct btrfs_root *btrfs_lookup_fs_root(struct btrfs_fs_info *fs_info, {struct btrfs_root *root; +#if BITS_PER_LONG ==32 +/* +* Roots with ids above ULONG_MAX are never inserted into the radix +* tree, and a truncated index may hit an unrelated root. +*/ +if (root_id >ULONG_MAX ) +return NULL ; +#endif +spin_lock (&fs_info->fs_roots_radix_lock); root =radix_tree_lookup (&fs_info->fs_roots_radix, (unsigned long )root_id);
@@ -1181,6 +1190,10 @@ int btrfs_insert_fs_root(struct btrfs_fs_info *fs_info, {int ret; + ret =btrfs_check_subvolid (fs_info,btrfs_root_id (root)); +if (ret) +return ret; + ret =radix_tree_preload (GFP_NOFS );if (ret)return ret;
fs/btrfs/disk-io.h +19 -0
@@ -105,6 +105,25 @@ static inline struct btrfs_root *btrfs_grab_root(struct btrfs_root *root)return NULL ; } +/* +* fs_roots_radix is indexed by unsigned long, so on 32-bit systems a subvolume +* id above ULONG_MAX is truncated, and can conflict with other subvolumes. +* Such subvolumes are not supported. +*/ +static inline int btrfs_check_subvolid (const struct btrfs_fs_info *fs_info, +u64 subvolid) +{ +#if BITS_PER_LONG ==32 +if (unlikely (subvolid >ULONG_MAX )) { +btrfs_err_rl (fs_info, +"subvolume id %llu is too large for 32-bit systems, max supported id is %lu" , + subvolid,ULONG_MAX ); +return -EOVERFLOW ; + } +#endif +return 0 ; +} +void btrfs_put_root (struct btrfs_root *root);void btrfs_mark_buffer_dirty (struct btrfs_trans_handle *trans,struct extent_buffer *buf);
fs/btrfs/ioctl.c +1 -1
@@ -5126,7 +5126,7 @@ static int btrfs_ioctl_subvol_sync(struct btrfs_fs_info *fs_info, void __user *a }/* 32bit limitation: fs_roots_radix key is not wide enough. */ -if (sizeof (unsigned long ) !=sizeof (u64) && args.subvolid >U32_MAX ) +if (btrfs_check_subvolid (fs_info, args.subvolid))return -EOVERFLOW ;while (1 ) {
Signature · 1 line
2.56.0
Re: [PATCH 2/2] btrfs: reject subvolume ids that do not fit into unsigned long
Quoted 104 lines · Qu Wenruo
fs_roots_radixis indexed by unsigned long, so on 32-bit systems the subvolume id is silently truncated to 32 bits, e.g:Subvolume 257 (
0x101) and subvolume 4294967553 (0x100000101) will have the same index (0x101) on 32-bit systems.Although this should be very rare, as btrfs can reuse deleted subvolume ids, and there are other limits like
anon_devpreventing us from so many subvolumes.But it's still better to address such problems, since 32 bit systems are still widely supported by the kernel.
Address such rare problem by:
- Add
btrfs_check_subvolid()tobtrfs_insert_fs_root()
So that all subvolumes inserted into the fs radix tree are ensured to be no larger thanULONG_MAX.If there is a high subvolumeid, it will show an error message.
- Do not search the radix tree if subvolid is is too larger It's possible to pass reloc tree into
btrfs_lookup_fs_root()through backref walk.And it can be very common during qgroup operations. So we don't want to flood the dmesg with error messages.
Just silently reject such search silently, and searching tree reloc tree insidebtrfs_lookup_fs_root()will return nothing anyway.Signed-off-by Qu Wenruo <[email protected]>--- fs/btrfs/disk-io.c | 13 +++++++++++++ fs/btrfs/disk-io.h | 19 +++++++++++++++++++ fs/btrfs/ioctl.c | 2 +- 3 files changed, 33 insertions(+), 1 deletion(-)fs/btrfs/disk-io.c +13
-0@@ -1129,6 +1129,15 @@ static struct btrfs_root *btrfs_lookup_fs_root(struct btrfs_fs_info *fs_info, {struct btrfs_root *root; +#if BITS_PER_LONG ==32 +/* +* Roots with ids above ULONG_MAX are never inserted into the radix +* tree, and a truncated index may hit an unrelated root. +*/ +if (root_id >ULONG_MAX ) +return NULL ; +#endif +spin_lock (&fs_info->fs_roots_radix_lock); root =radix_tree_lookup (&fs_info->fs_roots_radix, (unsigned long )root_id);@@ -1181,6 +1190,10 @@ int btrfs_insert_fs_root(struct btrfs_fs_info *fs_info, {int ret; + ret =btrfs_check_subvolid (fs_info,btrfs_root_id (root)); +if (ret) +return ret; + ret =radix_tree_preload (GFP_NOFS );if (ret)return ret;fs/btrfs/disk-io.h +19
-0@@ -105,6 +105,25 @@ static inline struct btrfs_root *btrfs_grab_root(struct btrfs_root *root)return NULL ; } +/* +* fs_roots_radix is indexed by unsigned long, so on 32-bit systems a subvolume +* id above ULONG_MAX is truncated, and can conflict with other subvolumes. +* Such subvolumes are not supported. +*/ +static inline int btrfs_check_subvolid (const struct btrfs_fs_info *fs_info, +u64 subvolid) +{ +#if BITS_PER_LONG ==32 +if (unlikely (subvolid >ULONG_MAX )) { +btrfs_err_rl (fs_info, +"subvolume id %llu is too large for 32-bit systems, max supported id is %lu" , + subvolid,ULONG_MAX ); +return -EOVERFLOW ; + } +#endif +return 0 ; +} +void btrfs_put_root (struct btrfs_root *root);void btrfs_mark_buffer_dirty (struct btrfs_trans_handle *trans,struct extent_buffer *buf);fs/btrfs/ioctl.c +0
-0
fs/btrfs/ioctl.c static int btrfs_ioctl_subvol_sync(struct btrfs_fs_info *fs_info, void __user *a · line 5130
Quoted 6 lines
fs/btrfs/ioctl.c +1
-1@@ -5126,7 +5126,7 @@ static int btrfs_ioctl_subvol_sync(struct btrfs_fs_info *fs_info, void __user *a }/* 32bit limitation: fs_roots_radix key is not wide enough. */ -if (sizeof (unsigned long ) !=sizeof (u64) && args.subvolid >U32_MAX ) +if (btrfs_check_subvolid (fs_info, args.subvolid))return -EOVERFLOW ;
Technically we should return exactly what btrfs_check_subvoldid() returns. Right now the only error it can return happens to be what we have hardcoded here, so there's no problem.
But it would be cleaner to do this:
ret = btrfs_check_subvolid();
if (ret)
return ret;
Anyway:
Thanks.
Quoted 6 lines
fs/btrfs/ioctl.c +0
-1while (1 ) { --2.56.0