[PATCH v3 0/2] btrfs: re-define btrfs_raid_types

[PATCH v3 0/2] btrfs: re-define btrfs_raid_types

[Qu Wenruo]

[CHANGELOG]
Changelog:
v2:
- Fix the start value of BTRFS_RAID_RAID0

v3:
- Introduce more static sanity checks
  They are kinda overkilled, but they are only compile time checks, it
  should be fine.

- Keep btrfs_bg_flags_to_raid_index() as regular function

By the nature of BTRFS_BLOCK_GROUP_* profiles, converting the flag into
an index should only need one bits AND, one if () check for SINGLE
profile, one right shift to align the values, one ilog2() call which is
normally converted into ffs() assembly code.

But we're using a lot of if () branches to do the convert.

This patch will re-define btrfs_raid_types by:

- Move it to volumes.h
  btrfs_raid_types are only used internally, no need to be exposed
  through UAPI.

- Re-order btrfs_raid_types
  To make them match their value order.

- Use ilog2() to convert them into index

- Extra static_assert()s to make sure RAID0 is always the least
  significant bit in PROFILE_MASK


Qu Wenruo (2):
  btrfs: move definition of btrfs_raid_types to volumes.h
  btrfs: use ilog2() to replace if () branches for
    btrfs_bg_flags_to_raid_index()

 fs/btrfs/space-info.h           |  2 ++
 fs/btrfs/volumes.c              | 24 ++++++----------------
 fs/btrfs/volumes.h              | 35 +++++++++++++++++++++++++++++++++
 include/uapi/linux/btrfs_tree.h | 13 ------------
 4 files changed, 43 insertions(+), 31 deletions(-)

-- 
2.35.1

[PATCH v3 1/2] btrfs: move definition of btrfs_raid_types to volumes.h

[Qu Wenruo]

It's only internally used as another way to represent btrfs profiles,
it's not exposed through any on-disk format, in fact this
btrfs_raid_types is diverted from the on-disk format values.

Furthermore, since it's internal structure, its definition can change in
the future.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 fs/btrfs/space-info.h           |  2 ++
 fs/btrfs/volumes.h              | 13 +++++++++++++
 include/uapi/linux/btrfs_tree.h | 13 -------------
 3 files changed, 15 insertions(+), 13 deletions(-)

diff --git a/fs/btrfs/space-info.h b/fs/btrfs/space-info.h
index a803e29bd781..c096695598c1 100644
--- a/fs/btrfs/space-info.h
+++ b/fs/btrfs/space-info.h
@@ -3,6 +3,8 @@
 #ifndef BTRFS_SPACE_INFO_H
 #define BTRFS_SPACE_INFO_H
 
+#include "volumes.h"
+
 struct btrfs_space_info {
 	spinlock_t lock;
 
diff --git a/fs/btrfs/volumes.h b/fs/btrfs/volumes.h
index f3e28f11cfb6..dbb15e4eaa50 100644
--- a/fs/btrfs/volumes.h
+++ b/fs/btrfs/volumes.h
@@ -17,6 +17,19 @@ extern struct mutex uuid_mutex;
 
 #define BTRFS_STRIPE_LEN	SZ_64K
 
+enum btrfs_raid_types {
+	BTRFS_RAID_RAID10,
+	BTRFS_RAID_RAID1,
+	BTRFS_RAID_DUP,
+	BTRFS_RAID_RAID0,
+	BTRFS_RAID_SINGLE,
+	BTRFS_RAID_RAID5,
+	BTRFS_RAID_RAID6,
+	BTRFS_RAID_RAID1C3,
+	BTRFS_RAID_RAID1C4,
+	BTRFS_NR_RAID_TYPES
+};
+
 struct btrfs_io_geometry {
 	/* remaining bytes before crossing a stripe */
 	u64 len;
diff --git a/include/uapi/linux/btrfs_tree.h b/include/uapi/linux/btrfs_tree.h
index b069752a8ecf..d4117152d907 100644
--- a/include/uapi/linux/btrfs_tree.h
+++ b/include/uapi/linux/btrfs_tree.h
@@ -880,19 +880,6 @@ struct btrfs_dev_replace_item {
 #define BTRFS_BLOCK_GROUP_RESERVED	(BTRFS_AVAIL_ALLOC_BIT_SINGLE | \
 					 BTRFS_SPACE_INFO_GLOBAL_RSV)
 
-enum btrfs_raid_types {
-	BTRFS_RAID_RAID10,
-	BTRFS_RAID_RAID1,
-	BTRFS_RAID_DUP,
-	BTRFS_RAID_RAID0,
-	BTRFS_RAID_SINGLE,
-	BTRFS_RAID_RAID5,
-	BTRFS_RAID_RAID6,
-	BTRFS_RAID_RAID1C3,
-	BTRFS_RAID_RAID1C4,
-	BTRFS_NR_RAID_TYPES
-};
-
 #define BTRFS_BLOCK_GROUP_TYPE_MASK	(BTRFS_BLOCK_GROUP_DATA |    \
 					 BTRFS_BLOCK_GROUP_SYSTEM |  \
 					 BTRFS_BLOCK_GROUP_METADATA)
-- 
2.35.1

Re: [PATCH v3 1/2] btrfs: move definition of btrfs_raid_types to volumes.h

[Johannes Thumshirn]

Looks good,
Reviewed-by: Johannes Thumshirn <johannes.thumshirn@wdc.com>

[PATCH v3 2/2] btrfs: use ilog2() to replace if () branches for btrfs_bg_flags_to_raid_index()

[Qu Wenruo]

In function btrfs_bg_flags_to_raid_index(), we use quite some if () to
convert the BTRFS_BLOCK_GROUP_* bits to a index number.

But the truth is, there is really no such need for so many branches at
all.
Since all BTRFS_BLOCK_GROUP_* flags are just one single bit set inside
BTRFS_BLOCK_GROUP_PROFILES_MASK, we can easily use ilog2() to calculate
their values.

This calculation has an anchor point, the lowest PROFILE bit, which is
RAID0.

Even it's fixed on-disk format and should never change, here I added
extra compile time checks to make it super safe:

1. Make sure RAID0 is always the lowest bit in PROFILE_MASK
   This is done by finding the first (least significant) bit set of
   RAID0 and PROFILE_MASK & ~RAID0.

2. Make sure RAID0 bit set beyond the highest bit of TYPE_MASK

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 fs/btrfs/volumes.c | 24 ++++++------------------
 fs/btrfs/volumes.h | 40 +++++++++++++++++++++++++++++++---------
 2 files changed, 37 insertions(+), 27 deletions(-)

diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c
index 2368a2ffbee7..4cfe6daa0fee 100644
--- a/fs/btrfs/volumes.c
+++ b/fs/btrfs/volumes.c
@@ -164,24 +164,12 @@ const struct btrfs_raid_attr btrfs_raid_array[BTRFS_NR_RAID_TYPES] = {
  */
 enum btrfs_raid_types __attribute_const__ btrfs_bg_flags_to_raid_index(u64 flags)
 {
-	if (flags & BTRFS_BLOCK_GROUP_RAID10)
-		return BTRFS_RAID_RAID10;
-	else if (flags & BTRFS_BLOCK_GROUP_RAID1)
-		return BTRFS_RAID_RAID1;
-	else if (flags & BTRFS_BLOCK_GROUP_RAID1C3)
-		return BTRFS_RAID_RAID1C3;
-	else if (flags & BTRFS_BLOCK_GROUP_RAID1C4)
-		return BTRFS_RAID_RAID1C4;
-	else if (flags & BTRFS_BLOCK_GROUP_DUP)
-		return BTRFS_RAID_DUP;
-	else if (flags & BTRFS_BLOCK_GROUP_RAID0)
-		return BTRFS_RAID_RAID0;
-	else if (flags & BTRFS_BLOCK_GROUP_RAID5)
-		return BTRFS_RAID_RAID5;
-	else if (flags & BTRFS_BLOCK_GROUP_RAID6)
-		return BTRFS_RAID_RAID6;
-
-	return BTRFS_RAID_SINGLE; /* BTRFS_BLOCK_GROUP_SINGLE */
+	u64 profile = flags & BTRFS_BLOCK_GROUP_PROFILE_MASK;
+
+	if (!profile)
+		return BTRFS_RAID_SINGLE;
+
+	return BTRFS_BG_FLAG_TO_INDEX(profile);
 }
 
 const char *btrfs_bg_type_to_raid_name(u64 flags)
diff --git a/fs/btrfs/volumes.h b/fs/btrfs/volumes.h
index dbb15e4eaa50..627f1ae672c4 100644
--- a/fs/btrfs/volumes.h
+++ b/fs/btrfs/volumes.h
@@ -17,16 +17,38 @@ extern struct mutex uuid_mutex;
 
 #define BTRFS_STRIPE_LEN	SZ_64K
 
+/* Used by sanity check for btrfs_raid_types. */
+#define const_ffs(n) (__builtin_ctzll(n) + 1)
+
+/*
+ * The conversion from BTRFS_BLOCK_GROUP_* bits to btrfs_raid_type requires
+ * RAID0 always to be the lowest profile bit.
+ * Although it's part of on-disk format and should never change, just do extra
+ * compile time sanity check on it.
+ */
+static_assert(const_ffs(BTRFS_BLOCK_GROUP_RAID0) <
+	      const_ffs(BTRFS_BLOCK_GROUP_PROFILE_MASK &
+			~BTRFS_BLOCK_GROUP_RAID0));
+static_assert(const_ilog2(BTRFS_BLOCK_GROUP_RAID0) >
+	      ilog2(BTRFS_BLOCK_GROUP_TYPE_MASK));
+
+/* ilog2() can handle both constants and variables */
+#define BTRFS_BG_FLAG_TO_INDEX(profile)	\
+	ilog2((profile) >> (ilog2(BTRFS_BLOCK_GROUP_RAID0) - 1))
+
 enum btrfs_raid_types {
-	BTRFS_RAID_RAID10,
-	BTRFS_RAID_RAID1,
-	BTRFS_RAID_DUP,
-	BTRFS_RAID_RAID0,
-	BTRFS_RAID_SINGLE,
-	BTRFS_RAID_RAID5,
-	BTRFS_RAID_RAID6,
-	BTRFS_RAID_RAID1C3,
-	BTRFS_RAID_RAID1C4,
+	/* SINGLE is the special one as it doesn't have on-disk bit. */
+	BTRFS_RAID_SINGLE  = 0,
+
+	BTRFS_RAID_RAID0   = BTRFS_BG_FLAG_TO_INDEX(BTRFS_BLOCK_GROUP_RAID0),
+	BTRFS_RAID_RAID1   = BTRFS_BG_FLAG_TO_INDEX(BTRFS_BLOCK_GROUP_RAID1),
+	BTRFS_RAID_DUP	   = BTRFS_BG_FLAG_TO_INDEX(BTRFS_BLOCK_GROUP_DUP),
+	BTRFS_RAID_RAID10  = BTRFS_BG_FLAG_TO_INDEX(BTRFS_BLOCK_GROUP_RAID10),
+	BTRFS_RAID_RAID5   = BTRFS_BG_FLAG_TO_INDEX(BTRFS_BLOCK_GROUP_RAID5),
+	BTRFS_RAID_RAID6   = BTRFS_BG_FLAG_TO_INDEX(BTRFS_BLOCK_GROUP_RAID6),
+	BTRFS_RAID_RAID1C3 = BTRFS_BG_FLAG_TO_INDEX(BTRFS_BLOCK_GROUP_RAID1C3),
+	BTRFS_RAID_RAID1C4 = BTRFS_BG_FLAG_TO_INDEX(BTRFS_BLOCK_GROUP_RAID1C4),
+
 	BTRFS_NR_RAID_TYPES
 };
 
-- 
2.35.1

Re: [PATCH v3 2/2] btrfs: use ilog2() to replace if () branches for btrfs_bg_flags_to_raid_index()

[Johannes Thumshirn]

On 20/04/2022 10:09, Qu Wenruo wrote:
> In function btrfs_bg_flags_to_raid_index(), we use quite some if () to
> convert the BTRFS_BLOCK_GROUP_* bits to a index number.
> 
> But the truth is, there is really no such need for so many branches at
> all.
> Since all BTRFS_BLOCK_GROUP_* flags are just one single bit set inside
> BTRFS_BLOCK_GROUP_PROFILES_MASK, we can easily use ilog2() to calculate
> their values.
> 
> This calculation has an anchor point, the lowest PROFILE bit, which is
> RAID0.
> 
> Even it's fixed on-disk format and should never change, here I added
> extra compile time checks to make it super safe:
> 
> 1. Make sure RAID0 is always the lowest bit in PROFILE_MASK
>    This is done by finding the first (least significant) bit set of
>    RAID0 and PROFILE_MASK & ~RAID0.
> 
> 2. Make sure RAID0 bit set beyond the highest bit of TYPE_MASK

TBH I think this change obscures the code more than it improves it.

Re: [PATCH v3 2/2] btrfs: use ilog2() to replace if () branches for btrfs_bg_flags_to_raid_index()

[Qu Wenruo]

On 2022/4/20 16:25, Johannes Thumshirn wrote:
> On 20/04/2022 10:09, Qu Wenruo wrote:
>> In function btrfs_bg_flags_to_raid_index(), we use quite some if () to
>> convert the BTRFS_BLOCK_GROUP_* bits to a index number.
>>
>> But the truth is, there is really no such need for so many branches at
>> all.
>> Since all BTRFS_BLOCK_GROUP_* flags are just one single bit set inside
>> BTRFS_BLOCK_GROUP_PROFILES_MASK, we can easily use ilog2() to calculate
>> their values.
>>
>> This calculation has an anchor point, the lowest PROFILE bit, which is
>> RAID0.
>>
>> Even it's fixed on-disk format and should never change, here I added
>> extra compile time checks to make it super safe:
>>
>> 1. Make sure RAID0 is always the lowest bit in PROFILE_MASK
>>     This is done by finding the first (least significant) bit set of
>>     RAID0 and PROFILE_MASK & ~RAID0.
>>
>> 2. Make sure RAID0 bit set beyond the highest bit of TYPE_MASK
>
> TBH I think this change obscures the code more than it improves it.
>
Right, that kinda makes sense.

Will update the patchset to remove that line if needed.

Thanks,
Qu

Re: [PATCH v3 2/2] btrfs: use ilog2() to replace if () branches for btrfs_bg_flags_to_raid_index()

[Johannes Thumshirn]

On 20/04/2022 10:38, Qu Wenruo wrote:
> 
> 
> On 2022/4/20 16:25, Johannes Thumshirn wrote:
>> On 20/04/2022 10:09, Qu Wenruo wrote:
>>> In function btrfs_bg_flags_to_raid_index(), we use quite some if () to
>>> convert the BTRFS_BLOCK_GROUP_* bits to a index number.
>>>
>>> But the truth is, there is really no such need for so many branches at
>>> all.
>>> Since all BTRFS_BLOCK_GROUP_* flags are just one single bit set inside
>>> BTRFS_BLOCK_GROUP_PROFILES_MASK, we can easily use ilog2() to calculate
>>> their values.
>>>
>>> This calculation has an anchor point, the lowest PROFILE bit, which is
>>> RAID0.
>>>
>>> Even it's fixed on-disk format and should never change, here I added
>>> extra compile time checks to make it super safe:
>>>
>>> 1. Make sure RAID0 is always the lowest bit in PROFILE_MASK
>>>     This is done by finding the first (least significant) bit set of
>>>     RAID0 and PROFILE_MASK & ~RAID0.
>>>
>>> 2. Make sure RAID0 bit set beyond the highest bit of TYPE_MASK
>>
>> TBH I think this change obscures the code more than it improves it.
>>
> Right, that kinda makes sense.
> 
> Will update the patchset to remove that line if needed.

I think the whole patch makes the code harder to follow. As of now you can
just look it up, now you have to look how the calculation is done etc.

If you want to get rid of the branches (which I still don't see a reason for)
have you considered creating a lookup table?

Re: [PATCH v3 2/2] btrfs: use ilog2() to replace if () branches for btrfs_bg_flags_to_raid_index()

[Qu Wenruo]

On 2022/4/20 16:41, Johannes Thumshirn wrote:
> On 20/04/2022 10:38, Qu Wenruo wrote:
>>
>>
>> On 2022/4/20 16:25, Johannes Thumshirn wrote:
>>> On 20/04/2022 10:09, Qu Wenruo wrote:
>>>> In function btrfs_bg_flags_to_raid_index(), we use quite some if () to
>>>> convert the BTRFS_BLOCK_GROUP_* bits to a index number.
>>>>
>>>> But the truth is, there is really no such need for so many branches at
>>>> all.
>>>> Since all BTRFS_BLOCK_GROUP_* flags are just one single bit set inside
>>>> BTRFS_BLOCK_GROUP_PROFILES_MASK, we can easily use ilog2() to calculate
>>>> their values.
>>>>
>>>> This calculation has an anchor point, the lowest PROFILE bit, which is
>>>> RAID0.
>>>>
>>>> Even it's fixed on-disk format and should never change, here I added
>>>> extra compile time checks to make it super safe:
>>>>
>>>> 1. Make sure RAID0 is always the lowest bit in PROFILE_MASK
>>>>      This is done by finding the first (least significant) bit set of
>>>>      RAID0 and PROFILE_MASK & ~RAID0.
>>>>
>>>> 2. Make sure RAID0 bit set beyond the highest bit of TYPE_MASK
>>>
>>> TBH I think this change obscures the code more than it improves it.
>>>
>> Right, that kinda makes sense.
>>
>> Will update the patchset to remove that line if needed.
> 
> I think the whole patch makes the code harder to follow. As of now you can
> just look it up, now you have to look how the calculation is done etc.

The problem is, why you need to look the index up?

The index is pretty straight forward, just a enum for each profile, one 
should not really bother whatever the value is.

> 
> If you want to get rid of the branches (which I still don't see a reason for)

The new code is just 5 asm commands on x86_64.

> have you considered creating a lookup table?

The index is used for the lookup table of btrfs_raid_type.

Thanks,
Qu

Re: [PATCH v3 2/2] btrfs: use ilog2() to replace if () branches for btrfs_bg_flags_to_raid_index()

[David Sterba]

On Wed, Apr 20, 2022 at 08:41:13AM +0000, Johannes Thumshirn wrote:
> On 20/04/2022 10:38, Qu Wenruo wrote:
> >>> 1. Make sure RAID0 is always the lowest bit in PROFILE_MASK
> >>>     This is done by finding the first (least significant) bit set of
> >>>     RAID0 and PROFILE_MASK & ~RAID0.
> >>>
> >>> 2. Make sure RAID0 bit set beyond the highest bit of TYPE_MASK
> >>
> >> TBH I think this change obscures the code more than it improves it.
> >>
> > Right, that kinda makes sense.
> > 
> > Will update the patchset to remove that line if needed.
> 
> I think the whole patch makes the code harder to follow. As of now you can
> just look it up, now you have to look how the calculation is done etc.

I think the index is the least useful information about the profiles,
it's there just that we have a sequence representing the profile flags
that's usable for arrays, like the space infos. The on-disk definition
is the bit and that's the source, how exactly it's converted to the
index is IMHO just a detail.

> If you want to get rid of the branches (which I still don't see a reason for)
> have you considered creating a lookup table?

It's yet another place that keeps the mapping of the values open coded.

Possibly if we would want to take it farther, a single definition of the
index enums could be like

#define	DEFINE_RAID_INDEX(profile)				\
	BTRFS_RAID_##profile   = BTRFS_BG_FLAG_TO_INDEX(BTRFS_BLOCK_GROUP_##profile)

and then used like

enum raid_types {
	DEFINE_RAID_INDEX(RAID0),
	DEFINE_RAID_INDEX(RAID10),
	...
};

But that's obscuring what exactly does it define and we do use the plain
indexes like BTRFS_RAID_DUP in several places. It's sometimes annoying
that ctags don't locate all the setget helpers because of all the
BTRFS_SETGET_FUNCS macros.

Re: [PATCH v3 2/2] btrfs: use ilog2() to replace if () branches for btrfs_bg_flags_to_raid_index()

[Qu Wenruo]

On 2022/4/20 23:16, David Sterba wrote:
> On Wed, Apr 20, 2022 at 08:41:13AM +0000, Johannes Thumshirn wrote:
>> On 20/04/2022 10:38, Qu Wenruo wrote:
>>>>> 1. Make sure RAID0 is always the lowest bit in PROFILE_MASK
>>>>>      This is done by finding the first (least significant) bit set of
>>>>>      RAID0 and PROFILE_MASK & ~RAID0.
>>>>>
>>>>> 2. Make sure RAID0 bit set beyond the highest bit of TYPE_MASK
>>>>
>>>> TBH I think this change obscures the code more than it improves it.
>>>>
>>> Right, that kinda makes sense.
>>>
>>> Will update the patchset to remove that line if needed.
>>
>> I think the whole patch makes the code harder to follow. As of now you can
>> just look it up, now you have to look how the calculation is done etc.
>
> I think the index is the least useful information about the profiles,
> it's there just that we have a sequence representing the profile flags
> that's usable for arrays, like the space infos. The on-disk definition
> is the bit and that's the source, how exactly it's converted to the
> index is IMHO just a detail.
>
>> If you want to get rid of the branches (which I still don't see a reason for)
>> have you considered creating a lookup table?
>
> It's yet another place that keeps the mapping of the values open coded.
>
> Possibly if we would want to take it farther, a single definition of the
> index enums could be like
>
> #define	DEFINE_RAID_INDEX(profile)				\
> 	BTRFS_RAID_##profile   = BTRFS_BG_FLAG_TO_INDEX(BTRFS_BLOCK_GROUP_##profile)
>
> and then used like
>
> enum raid_types {
> 	DEFINE_RAID_INDEX(RAID0),
> 	DEFINE_RAID_INDEX(RAID10),
> 	...
> };
>
> But that's obscuring what exactly does it define and we do use the plain
> indexes like BTRFS_RAID_DUP in several places. It's sometimes annoying
> that ctags don't locate all the setget helpers because of all the
> BTRFS_SETGET_FUNCS macros.

Ctags are really out-of-date now.
LSP is the future, just try clangd, handling macros is just a piece of cake.

Thanks,
Qu

Re: [PATCH v3 0/2] btrfs: re-define btrfs_raid_types

[David Sterba]

On Wed, Apr 20, 2022 at 04:08:26PM +0800, Qu Wenruo wrote:
> [CHANGELOG]
> Changelog:
> v2:
> - Fix the start value of BTRFS_RAID_RAID0
> 
> v3:
> - Introduce more static sanity checks
>   They are kinda overkilled, but they are only compile time checks, it
>   should be fine.
> 
> - Keep btrfs_bg_flags_to_raid_index() as regular function
> 
> By the nature of BTRFS_BLOCK_GROUP_* profiles, converting the flag into
> an index should only need one bits AND, one if () check for SINGLE
> profile, one right shift to align the values, one ilog2() call which is
> normally converted into ffs() assembly code.
> 
> But we're using a lot of if () branches to do the convert.
> 
> This patch will re-define btrfs_raid_types by:
> 
> - Move it to volumes.h
>   btrfs_raid_types are only used internally, no need to be exposed
>   through UAPI.
> 
> - Re-order btrfs_raid_types
>   To make them match their value order.
> 
> - Use ilog2() to convert them into index
> 
> - Extra static_assert()s to make sure RAID0 is always the least
>   significant bit in PROFILE_MASK
> 
> 
> Qu Wenruo (2):
>   btrfs: move definition of btrfs_raid_types to volumes.h
>   btrfs: use ilog2() to replace if () branches for
>     btrfs_bg_flags_to_raid_index()

I've added the patches to for-next as it looks good as it is now, feel
free to send an update, either an incremental fixup or full resend.