[v3,2/6] btrfs-progs: utils: Introduce basic set operations for range
diff mbox

Message ID 20161219065642.25078-3-quwenruo@cn.fujitsu.com
State New
Headers show

Commit Message

Qu Wenruo Dec. 19, 2016, 6:56 a.m. UTC
Introduce basic set operations: is_subset() and is_intersection().

This is quite useful to check if a range [start, start + len) subset or
intersection of another range.
So we don't need to use open code to do it, which I sometimes do it
wrong.

Also use these new facilities in btrfs-convert, to check if a range is a
subset or intersects with btrfs convert reserved ranges.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 convert/main.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++
 disk-io.h      |  9 +++++++--
 utils.h        | 19 +++++++++++++++++++
 3 files changed, 77 insertions(+), 2 deletions(-)

Comments

David Sterba Jan. 23, 2017, 5:28 p.m. UTC | #1
On Mon, Dec 19, 2016 at 02:56:38PM +0800, Qu Wenruo wrote:
> Introduce basic set operations: is_subset() and is_intersection().
> 
> This is quite useful to check if a range [start, start + len) subset or
> intersection of another range.
> So we don't need to use open code to do it, which I sometimes do it
> wrong.
> 
> Also use these new facilities in btrfs-convert, to check if a range is a
> subset or intersects with btrfs convert reserved ranges.

I see the range helpers used only inside convert so I don't think we
need to export them into utils. Then you could introduce a helper
structure with start and len members and use that instead of 2 arrays

> --- a/disk-io.h
> +++ b/disk-io.h
> @@ -97,11 +97,16 @@ enum btrfs_read_sb_flags {
>  	SBREAD_PARTIAL		= (1 << 1),
>  };
>  
> +/*
> + * Use macro to define mirror super block position
> + * So we can use it in static array initializtion
> + */
> +#define BTRFS_SB_MIRROR_OFFSET(mirror)	((u64)(16 * 1024) << \
> +					 (BTRFS_SUPER_MIRROR_SHIFT * (mirror)))

This is unrelated change and should go separately.

>  static inline u64 btrfs_sb_offset(int mirror)
>  {
> -	u64 start = 16 * 1024;
>  	if (mirror)
> -		return start << (BTRFS_SUPER_MIRROR_SHIFT * mirror);
> +		return BTRFS_SB_MIRROR_OFFSET(mirror);
>  	return BTRFS_SUPER_INFO_OFFSET;
>  }
>  
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
David Sterba Jan. 23, 2017, 5:40 p.m. UTC | #2
On Mon, Dec 19, 2016 at 02:56:38PM +0800, Qu Wenruo wrote:
> +static u64 reserved_range_starts[3] = { 0, BTRFS_SB_MIRROR_OFFSET(1),
> +					BTRFS_SB_MIRROR_OFFSET(2) };
> +static u64 reserved_range_lens[3] = { 1024 * 1024, 64 * 1024, 64 * 1024 };

Also anywhere in the relevant code, the 3 should be better a named
constant and not either 3 or the ARRAY_SIZE, or 2 in some backward going
for loop I've seen.
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Qu Wenruo Jan. 24, 2017, 12:40 a.m. UTC | #3
At 01/24/2017 01:28 AM, David Sterba wrote:
> On Mon, Dec 19, 2016 at 02:56:38PM +0800, Qu Wenruo wrote:
>> Introduce basic set operations: is_subset() and is_intersection().
>>
>> This is quite useful to check if a range [start, start + len) subset or
>> intersection of another range.
>> So we don't need to use open code to do it, which I sometimes do it
>> wrong.
>>
>> Also use these new facilities in btrfs-convert, to check if a range is a
>> subset or intersects with btrfs convert reserved ranges.
>
> I see the range helpers used only inside convert so I don't think we
> need to export them into utils. Then you could introduce a helper
> structure with start and len members and use that instead of 2 arrays

Right, I could move it convert.

>
>> --- a/disk-io.h
>> +++ b/disk-io.h
>> @@ -97,11 +97,16 @@ enum btrfs_read_sb_flags {
>>  	SBREAD_PARTIAL		= (1 << 1),
>>  };
>>
>> +/*
>> + * Use macro to define mirror super block position
>> + * So we can use it in static array initializtion
>> + */
>> +#define BTRFS_SB_MIRROR_OFFSET(mirror)	((u64)(16 * 1024) << \
>> +					 (BTRFS_SUPER_MIRROR_SHIFT * (mirror)))
>
> This is unrelated change and should go separately.

OK, I can send out a patch first.

Thanks for reviewing,
Qu

>
>>  static inline u64 btrfs_sb_offset(int mirror)
>>  {
>> -	u64 start = 16 * 1024;
>>  	if (mirror)
>> -		return start << (BTRFS_SUPER_MIRROR_SHIFT * mirror);
>> +		return BTRFS_SB_MIRROR_OFFSET(mirror);
>>  	return BTRFS_SUPER_INFO_OFFSET;
>>  }
>>
>
>


--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Patch
diff mbox

diff --git a/convert/main.c b/convert/main.c
index 15f14af..db6d371 100644
--- a/convert/main.c
+++ b/convert/main.c
@@ -61,6 +61,15 @@ 
 
 #define CONV_IMAGE_SUBVOL_OBJECTID BTRFS_FIRST_FREE_OBJECTID
 
+/*
+ * Btrfs reserved ranges.
+ * In these ranges, btrfs record superblocks, so old fs data in these
+ * range can be relocated to other physical location
+ */
+static u64 reserved_range_starts[3] = { 0, BTRFS_SB_MIRROR_OFFSET(1),
+					BTRFS_SB_MIRROR_OFFSET(2) };
+static u64 reserved_range_lens[3] = { 1024 * 1024, 64 * 1024, 64 * 1024 };
+
 struct task_ctx {
 	uint32_t max_copy_inodes;
 	uint32_t cur_copy_inodes;
@@ -2672,6 +2681,48 @@  fail:
 	return -1;
 }
 
+/*
+ * Check if [start, start + len) is a subset of btrfs reserved ranges
+ */
+static int is_range_subset_of_reserved_ranges(u64 start, u64 len)
+{
+	int i;
+	int ret = 0;
+
+	for (i = 0; i < ARRAY_SIZE(reserved_range_starts); i++) {
+		if (is_range_subset(start, len, reserved_range_starts[i],
+				    reserved_range_lens[i])) {
+			ret = 1;
+			break;
+		}
+	}
+	return ret;
+}
+
+/*
+ * Check if [start, start + len) intersects with btrfs reserved ranges
+ * if intersects, record the first range it intersects with to @ret_index
+ */
+static int is_range_intersection_of_reserved_ranges(u64 start, u64 len,
+						    int *ret_index)
+{
+	int nr = -1;
+	int i;
+
+	for (i = 0; i < ARRAY_SIZE(reserved_range_starts); i++) {
+		if (is_range_intersect(start, len, reserved_range_starts[i],
+				       reserved_range_lens[i])) {
+			nr = i;
+			break;
+		}
+	}
+	if (nr == -1)
+		return 0;
+	if (ret_index)
+		*ret_index = nr;
+	return 1;
+}
+
 static int do_rollback(const char *devname)
 {
 	int fd = -1;
diff --git a/disk-io.h b/disk-io.h
index 1c8387e..af6fcfd 100644
--- a/disk-io.h
+++ b/disk-io.h
@@ -97,11 +97,16 @@  enum btrfs_read_sb_flags {
 	SBREAD_PARTIAL		= (1 << 1),
 };
 
+/*
+ * Use macro to define mirror super block position
+ * So we can use it in static array initializtion
+ */
+#define BTRFS_SB_MIRROR_OFFSET(mirror)	((u64)(16 * 1024) << \
+					 (BTRFS_SUPER_MIRROR_SHIFT * (mirror)))
 static inline u64 btrfs_sb_offset(int mirror)
 {
-	u64 start = 16 * 1024;
 	if (mirror)
-		return start << (BTRFS_SUPER_MIRROR_SHIFT * mirror);
+		return BTRFS_SB_MIRROR_OFFSET(mirror);
 	return BTRFS_SUPER_INFO_OFFSET;
 }
 
diff --git a/utils.h b/utils.h
index 366ca29..39ca970 100644
--- a/utils.h
+++ b/utils.h
@@ -457,4 +457,23 @@  unsigned int rand_range(unsigned int upper);
 /* Also allow setting the seed manually */
 void init_rand_seed(u64 seed);
 
+/*
+ * Basic set operations
+ * Mainly used for ranges subset/intersect
+ */
+/* Check if [start1, start1 + len1) is subset of [start2, start2 + len2) */
+static inline int is_range_subset(u64 start1, u64 len1, u64 start2, u64 len2)
+{
+	if (start1 >= start2 && start1 + len1 <= start2 + len2)
+		return 1;
+	return 0;
+}
+
+/* Check if [start1, start1 + len1) intersects with [start2, start2 + len2) */
+static inline int is_range_intersect(u64 start1, u64 len1, u64 start2, u64 len2)
+{
+	if (start1 >= start2 + len2 || start1 + len1 <= start2)
+		return 0;
+	return 1;
+}
 #endif