Syslinux - Dec 2015 - [PATCH v2] btrfs: Fix logical to physical block address mapping

The current btrfs support did not handled multiple stripes stored in
chunk items, hence skipping the physical addresses that were needed to
do the mapping.

Besides, the chunk tree may contain DEV_ITEM keys which store
information on all of the underlying block devices, so we must skip them
instead of finishing lookup.

The bug was reproduced with btrfs-progs v4.2.2.

Cc: Gene Cumm <gene.cumm at gmail.com>
Cc: H. Peter Anvin <hpa at zytor.com>
Signed-off-by: Paulo Alcantara <pcacjr at zytor.com>
---
 core/fs/btrfs/btrfs.c | 50 ++++++++++++++++++++++++++++++++++----------------
 core/fs/btrfs/btrfs.h |  2 ++
 2 files changed, 36 insertions(+), 16 deletions(-)

diff --git a/core/fs/btrfs/btrfs.c b/core/fs/btrfs/btrfs.c
index 53e1105..a06607e 100644
--- a/core/fs/btrfs/btrfs.c
+++ b/core/fs/btrfs/btrfs.c
@@ -81,7 +81,8 @@ static int btrfs_comp_chunk_map(struct btrfs_chunk_map_item
*m1,
 }
 
 /* insert a new chunk mapping item */
-static void insert_map(struct fs_info *fs, struct btrfs_chunk_map_item *item)
+static void insert_chunk_item(struct fs_info *fs,
+			      struct btrfs_chunk_map_item *item)
 {
 	struct btrfs_info * const bfs = fs->fs_info;
 	struct btrfs_chunk_map *chunk_map = &bfs->chunk_map;
@@ -113,6 +114,22 @@ static void insert_map(struct fs_info *fs, struct
btrfs_chunk_map_item *item)
 	chunk_map->cur_length++;
 }
 
+static inline void insert_map(struct fs_info *fs, struct btrfs_disk_key *key,
+			      struct btrfs_chunk *chunk)
+{
+	struct btrfs_stripe *stripe = &chunk->stripe;
+	struct btrfs_stripe *stripe_end = &chunk->stripe +
chunk->num_stripes;
+	struct btrfs_chunk_map_item item;
+
+	item.logical = key->offset;
+	item.length = chunk->length;
+	for ( ; stripe < stripe_end; stripe++) {
+		item.devid = stripe->devid;
+		item.physical = stripe->offset;
+		insert_chunk_item(fs, &item);
+	}
+}
+
 /*
  * from sys_chunk_array or chunk_tree, we can convert a logical address to
  * a physical address we can not support multi device case yet
@@ -330,7 +347,6 @@ static int next_slot(struct fs_info *fs, struct
btrfs_disk_key *key,
 static void btrfs_read_sys_chunk_array(struct fs_info *fs)
 {
 	struct btrfs_info * const bfs = fs->fs_info;
-	struct btrfs_chunk_map_item item;
 	struct btrfs_disk_key *key;
 	struct btrfs_chunk *chunk;
 	int cur;
@@ -342,12 +358,7 @@ static void btrfs_read_sys_chunk_array(struct fs_info *fs)
 		cur += sizeof(*key);
 		chunk = (struct btrfs_chunk *)(bfs->sb.sys_chunk_array + cur);
 		cur += btrfs_chunk_item_size(chunk->num_stripes);
-		/* insert to mapping table, ignore multi stripes */
-		item.logical = key->offset;
-		item.length = chunk->length;
-		item.devid = chunk->stripe.devid;
-		item.physical = chunk->stripe.offset;/*ignore other stripes */
-		insert_map(fs, &item);
+		insert_map(fs, key, chunk);
 	}
 }
 
@@ -356,8 +367,8 @@ static void btrfs_read_chunk_tree(struct fs_info *fs)
 {
 	struct btrfs_info * const bfs = fs->fs_info;
 	struct btrfs_disk_key search_key;
+	struct btrfs_disk_key ignore_key;
 	struct btrfs_chunk *chunk;
-	struct btrfs_chunk_map_item item;
 	struct btrfs_path path;
 
 	if (!(bfs->sb.flags & BTRFS_SUPER_FLAG_METADUMP)) {
@@ -370,17 +381,24 @@ static void btrfs_read_chunk_tree(struct fs_info *fs)
 		clear_path(&path);
 		search_tree(fs, bfs->sb.chunk_root, &search_key, &path);
 		do {
+			ignore_key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
+			ignore_key.type = BTRFS_DEV_ITEM_KEY;
 			do {
+				/* skip information about underlying block
+				 * devices.
+				 */
+				if (!btrfs_comp_keys_type(&ignore_key,
+							  &path.item.key))
+					goto skip_dev_item;
 				if (btrfs_comp_keys_type(&search_key,
-							&path.item.key))
+							 &path.item.key))
 					break;
+
 				chunk = (struct btrfs_chunk *)(path.data);
-				/* insert to mapping table, ignore stripes */
-				item.logical = path.item.key.offset;
-				item.length = chunk->length;
-				item.devid = chunk->stripe.devid;
-				item.physical = chunk->stripe.offset;
-				insert_map(fs, &item);
+				insert_map(fs, &path.item.key, chunk);
+
+			skip_dev_item:
+				;
 			} while (!next_slot(fs, &search_key, &path));
 			if (btrfs_comp_keys_type(&search_key, &path.item.key))
 				break;
diff --git a/core/fs/btrfs/btrfs.h b/core/fs/btrfs/btrfs.h
index 8f519a9..32e7c70 100644
--- a/core/fs/btrfs/btrfs.h
+++ b/core/fs/btrfs/btrfs.h
@@ -56,6 +56,8 @@ typedef u64 __le64;
 #define BTRFS_MAX_LEVEL 8
 #define BTRFS_MAX_CHUNK_ENTRIES 256
 
+#define BTRFS_DEV_ITEMS_OBJECTID 1ULL
+
 #define BTRFS_FT_REG_FILE	1
 #define BTRFS_FT_DIR		2
 #define BTRFS_FT_SYMLINK	7
-- 
2.4.3

The current btrfs support did not handled multiple stripes stored in
chunk items, hence skipping the physical addresses that were needed to
do the mapping.

Besides, the chunk tree may contain DEV_ITEM keys which store
information on all of the underlying block devices, so we must skip them
instead of finishing lookup.

The bug was reproduced with btrfs-progs v4.2.2.

Cc: Gene Cumm <gene.cumm at gmail.com>
Cc: H. Peter Anvin <hpa at zytor.com>
Signed-off-by: Paulo Alcantara <pcacjr at zytor.com>
---
v1 -> v2:
 * Do not set ignore_key multiple times. Set it before parsing chunk
   tree.
---
 core/fs/btrfs/btrfs.c | 52 +++++++++++++++++++++++++++++++++++----------------
 core/fs/btrfs/btrfs.h |  2 ++
 2 files changed, 38 insertions(+), 16 deletions(-)

diff --git a/core/fs/btrfs/btrfs.c b/core/fs/btrfs/btrfs.c
index 53e1105..ca611db 100644
--- a/core/fs/btrfs/btrfs.c
+++ b/core/fs/btrfs/btrfs.c
@@ -81,7 +81,8 @@ static int btrfs_comp_chunk_map(struct btrfs_chunk_map_item
*m1,
 }
 
 /* insert a new chunk mapping item */
-static void insert_map(struct fs_info *fs, struct btrfs_chunk_map_item *item)
+static void insert_chunk_item(struct fs_info *fs,
+			      struct btrfs_chunk_map_item *item)
 {
 	struct btrfs_info * const bfs = fs->fs_info;
 	struct btrfs_chunk_map *chunk_map = &bfs->chunk_map;
@@ -113,6 +114,22 @@ static void insert_map(struct fs_info *fs, struct
btrfs_chunk_map_item *item)
 	chunk_map->cur_length++;
 }
 
+static inline void insert_map(struct fs_info *fs, struct btrfs_disk_key *key,
+			      struct btrfs_chunk *chunk)
+{
+	struct btrfs_stripe *stripe = &chunk->stripe;
+	struct btrfs_stripe *stripe_end = &chunk->stripe +
chunk->num_stripes;
+	struct btrfs_chunk_map_item item;
+
+	item.logical = key->offset;
+	item.length = chunk->length;
+	for ( ; stripe < stripe_end; stripe++) {
+		item.devid = stripe->devid;
+		item.physical = stripe->offset;
+		insert_chunk_item(fs, &item);
+	}
+}
+
 /*
  * from sys_chunk_array or chunk_tree, we can convert a logical address to
  * a physical address we can not support multi device case yet
@@ -330,7 +347,6 @@ static int next_slot(struct fs_info *fs, struct
btrfs_disk_key *key,
 static void btrfs_read_sys_chunk_array(struct fs_info *fs)
 {
 	struct btrfs_info * const bfs = fs->fs_info;
-	struct btrfs_chunk_map_item item;
 	struct btrfs_disk_key *key;
 	struct btrfs_chunk *chunk;
 	int cur;
@@ -342,12 +358,7 @@ static void btrfs_read_sys_chunk_array(struct fs_info *fs)
 		cur += sizeof(*key);
 		chunk = (struct btrfs_chunk *)(bfs->sb.sys_chunk_array + cur);
 		cur += btrfs_chunk_item_size(chunk->num_stripes);
-		/* insert to mapping table, ignore multi stripes */
-		item.logical = key->offset;
-		item.length = chunk->length;
-		item.devid = chunk->stripe.devid;
-		item.physical = chunk->stripe.offset;/*ignore other stripes */
-		insert_map(fs, &item);
+		insert_map(fs, key, chunk);
 	}
 }
 
@@ -355,14 +366,18 @@ static void btrfs_read_sys_chunk_array(struct fs_info *fs)
 static void btrfs_read_chunk_tree(struct fs_info *fs)
 {
 	struct btrfs_info * const bfs = fs->fs_info;
+	struct btrfs_disk_key ignore_key;
 	struct btrfs_disk_key search_key;
 	struct btrfs_chunk *chunk;
-	struct btrfs_chunk_map_item item;
 	struct btrfs_path path;
 
 	if (!(bfs->sb.flags & BTRFS_SUPER_FLAG_METADUMP)) {
 		if (bfs->sb.num_devices > 1)
 			printf("warning: only support single device btrfs\n");
+
+		ignore_key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
+		ignore_key.type = BTRFS_DEV_ITEM_KEY;
+
 		/* read chunk from chunk_tree */
 		search_key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
 		search_key.type = BTRFS_CHUNK_ITEM_KEY;
@@ -371,16 +386,21 @@ static void btrfs_read_chunk_tree(struct fs_info *fs)
 		search_tree(fs, bfs->sb.chunk_root, &search_key, &path);
 		do {
 			do {
+				/* skip information about underlying block
+				 * devices.
+				 */
+				if (!btrfs_comp_keys_type(&ignore_key,
+							  &path.item.key))
+					goto skip_dev_item;
 				if (btrfs_comp_keys_type(&search_key,
-							&path.item.key))
+							 &path.item.key))
 					break;
+
 				chunk = (struct btrfs_chunk *)(path.data);
-				/* insert to mapping table, ignore stripes */
-				item.logical = path.item.key.offset;
-				item.length = chunk->length;
-				item.devid = chunk->stripe.devid;
-				item.physical = chunk->stripe.offset;
-				insert_map(fs, &item);
+				insert_map(fs, &path.item.key, chunk);
+
+			skip_dev_item:
+				;
 			} while (!next_slot(fs, &search_key, &path));
 			if (btrfs_comp_keys_type(&search_key, &path.item.key))
 				break;
diff --git a/core/fs/btrfs/btrfs.h b/core/fs/btrfs/btrfs.h
index 8f519a9..32e7c70 100644
--- a/core/fs/btrfs/btrfs.h
+++ b/core/fs/btrfs/btrfs.h
@@ -56,6 +56,8 @@ typedef u64 __le64;
 #define BTRFS_MAX_LEVEL 8
 #define BTRFS_MAX_CHUNK_ENTRIES 256
 
+#define BTRFS_DEV_ITEMS_OBJECTID 1ULL
+
 #define BTRFS_FT_REG_FILE	1
 #define BTRFS_FT_DIR		2
 #define BTRFS_FT_SYMLINK	7
-- 
2.4.3

On Thu, Dec 24, 2015 at 8:58 AM, Paulo Alcantara <pcacjr at gmail.com>
wrote:
> The current btrfs support did not handled multiple stripes stored in
> chunk items, hence skipping the physical addresses that were needed to
> do the mapping.
>
> Besides, the chunk tree may contain DEV_ITEM keys which store
> information on all of the underlying block devices, so we must skip them
> instead of finishing lookup.
>
> The bug was reproduced with btrfs-progs v4.2.2.
>
> Cc: Gene Cumm <gene.cumm at gmail.com>
> Cc: H. Peter Anvin <hpa at zytor.com>
> Signed-off-by: Paulo Alcantara <pcacjr at zytor.com>
> ---
> v1 -> v2:
>  * Do not set ignore_key multiple times. Set it before parsing chunk
>    tree.
> ---
>  core/fs/btrfs/btrfs.c | 52
+++++++++++++++++++++++++++++++++++----------------
>  core/fs/btrfs/btrfs.h |  2 ++
>  2 files changed, 38 insertions(+), 16 deletions(-)
>
> diff --git a/core/fs/btrfs/btrfs.c b/core/fs/btrfs/btrfs.c
> index 53e1105..ca611db 100644
> --- a/core/fs/btrfs/btrfs.c
> +++ b/core/fs/btrfs/btrfs.c
> @@ -371,16 +386,21 @@ static void btrfs_read_chunk_tree(struct fs_info *fs)
>                 search_tree(fs, bfs->sb.chunk_root, &search_key,
&path);
>                 do {
>                         do {
> +                               /* skip information about underlying block
> +                                * devices.
> +                                */
> +                               if (!btrfs_comp_keys_type(&ignore_key,
> +                                                        
&path.item.key))
> +                                       goto skip_dev_item;
Why not just a continue rather than a goto to an empty label?
>                                 if (btrfs_comp_keys_type(&search_key,
> -                                                      
&path.item.key))
> +                                                       
&path.item.key))
>                                         break;
> +
>                                 chunk = (struct btrfs_chunk *)(path.data);
> -                               /* insert to mapping table, ignore stripes
*/
> -                               item.logical = path.item.key.offset;
> -                               item.length = chunk->length;
> -                               item.devid = chunk->stripe.devid;
> -                               item.physical = chunk->stripe.offset;
> -                               insert_map(fs, &item);
> +                               insert_map(fs, &path.item.key, chunk);
> +
> +                       skip_dev_item:
> +                               ;
>                         } while (!next_slot(fs, &search_key,
&path));
>                         if (btrfs_comp_keys_type(&search_key,
&path.item.key))
>                                 break;
-- 
-Gene

The current btrfs support did not handled multiple stripes stored in
chunk items, hence skipping the physical addresses that were needed to
do the mapping.

Besides, the chunk tree may contain DEV_ITEM keys which store
information on all of the underlying block devices, so we must skip them
instead of finishing lookup.

The bug was reproduced with btrfs-progs v4.2.2.

Cc: Gene Cumm <gene.cumm at gmail.com>
Cc: H. Peter Anvin <hpa at zytor.com>
Signed-off-by: Paulo Alcantara <pcacjr at zytor.com>
---
v1 -> v2:
 * Do not set ignore_key multiple times. Set it before parsing chunk
   tree.
v2 -> v3:
 * Replace an unnecessary goto with a continue statement.
---
 core/fs/btrfs/btrfs.c | 49 +++++++++++++++++++++++++++++++++----------------
 core/fs/btrfs/btrfs.h |  2 ++
 2 files changed, 35 insertions(+), 16 deletions(-)

diff --git a/core/fs/btrfs/btrfs.c b/core/fs/btrfs/btrfs.c
index 53e1105..58e1fe6 100644
--- a/core/fs/btrfs/btrfs.c
+++ b/core/fs/btrfs/btrfs.c
@@ -81,7 +81,8 @@ static int btrfs_comp_chunk_map(struct btrfs_chunk_map_item
*m1,
 }
 
 /* insert a new chunk mapping item */
-static void insert_map(struct fs_info *fs, struct btrfs_chunk_map_item *item)
+static void insert_chunk_item(struct fs_info *fs,
+			      struct btrfs_chunk_map_item *item)
 {
 	struct btrfs_info * const bfs = fs->fs_info;
 	struct btrfs_chunk_map *chunk_map = &bfs->chunk_map;
@@ -113,6 +114,22 @@ static void insert_map(struct fs_info *fs, struct
btrfs_chunk_map_item *item)
 	chunk_map->cur_length++;
 }
 
+static inline void insert_map(struct fs_info *fs, struct btrfs_disk_key *key,
+			      struct btrfs_chunk *chunk)
+{
+	struct btrfs_stripe *stripe = &chunk->stripe;
+	struct btrfs_stripe *stripe_end = stripe + chunk->num_stripes;
+	struct btrfs_chunk_map_item item;
+
+	item.logical = key->offset;
+	item.length = chunk->length;
+	for ( ; stripe < stripe_end; stripe++) {
+		item.devid = stripe->devid;
+		item.physical = stripe->offset;
+		insert_chunk_item(fs, &item);
+	}
+}
+
 /*
  * from sys_chunk_array or chunk_tree, we can convert a logical address to
  * a physical address we can not support multi device case yet
@@ -330,7 +347,6 @@ static int next_slot(struct fs_info *fs, struct
btrfs_disk_key *key,
 static void btrfs_read_sys_chunk_array(struct fs_info *fs)
 {
 	struct btrfs_info * const bfs = fs->fs_info;
-	struct btrfs_chunk_map_item item;
 	struct btrfs_disk_key *key;
 	struct btrfs_chunk *chunk;
 	int cur;
@@ -342,12 +358,7 @@ static void btrfs_read_sys_chunk_array(struct fs_info *fs)
 		cur += sizeof(*key);
 		chunk = (struct btrfs_chunk *)(bfs->sb.sys_chunk_array + cur);
 		cur += btrfs_chunk_item_size(chunk->num_stripes);
-		/* insert to mapping table, ignore multi stripes */
-		item.logical = key->offset;
-		item.length = chunk->length;
-		item.devid = chunk->stripe.devid;
-		item.physical = chunk->stripe.offset;/*ignore other stripes */
-		insert_map(fs, &item);
+		insert_map(fs, key, chunk);
 	}
 }
 
@@ -355,14 +366,18 @@ static void btrfs_read_sys_chunk_array(struct fs_info *fs)
 static void btrfs_read_chunk_tree(struct fs_info *fs)
 {
 	struct btrfs_info * const bfs = fs->fs_info;
+	struct btrfs_disk_key ignore_key;
 	struct btrfs_disk_key search_key;
 	struct btrfs_chunk *chunk;
-	struct btrfs_chunk_map_item item;
 	struct btrfs_path path;
 
 	if (!(bfs->sb.flags & BTRFS_SUPER_FLAG_METADUMP)) {
 		if (bfs->sb.num_devices > 1)
 			printf("warning: only support single device btrfs\n");
+
+		ignore_key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
+		ignore_key.type = BTRFS_DEV_ITEM_KEY;
+
 		/* read chunk from chunk_tree */
 		search_key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
 		search_key.type = BTRFS_CHUNK_ITEM_KEY;
@@ -371,16 +386,18 @@ static void btrfs_read_chunk_tree(struct fs_info *fs)
 		search_tree(fs, bfs->sb.chunk_root, &search_key, &path);
 		do {
 			do {
+				/* skip information about underlying block
+				 * devices.
+				 */
+				if (!btrfs_comp_keys_type(&ignore_key,
+							  &path.item.key))
+					continue;
 				if (btrfs_comp_keys_type(&search_key,
-							&path.item.key))
+							 &path.item.key))
 					break;
+
 				chunk = (struct btrfs_chunk *)(path.data);
-				/* insert to mapping table, ignore stripes */
-				item.logical = path.item.key.offset;
-				item.length = chunk->length;
-				item.devid = chunk->stripe.devid;
-				item.physical = chunk->stripe.offset;
-				insert_map(fs, &item);
+				insert_map(fs, &path.item.key, chunk);
 			} while (!next_slot(fs, &search_key, &path));
 			if (btrfs_comp_keys_type(&search_key, &path.item.key))
 				break;
diff --git a/core/fs/btrfs/btrfs.h b/core/fs/btrfs/btrfs.h
index 8f519a9..32e7c70 100644
--- a/core/fs/btrfs/btrfs.h
+++ b/core/fs/btrfs/btrfs.h
@@ -56,6 +56,8 @@ typedef u64 __le64;
 #define BTRFS_MAX_LEVEL 8
 #define BTRFS_MAX_CHUNK_ENTRIES 256
 
+#define BTRFS_DEV_ITEMS_OBJECTID 1ULL
+
 #define BTRFS_FT_REG_FILE	1
 #define BTRFS_FT_DIR		2
 #define BTRFS_FT_SYMLINK	7
-- 
2.4.3

On Sun, Dec 27, 2015 at 9:00 AM, Paulo Alcantara <pcacjr at gmail.com>
wrote:
> The current btrfs support did not handled multiple stripes stored in
> chunk items, hence skipping the physical addresses that were needed to
> do the mapping.
>
> Besides, the chunk tree may contain DEV_ITEM keys which store
> information on all of the underlying block devices, so we must skip them
> instead of finishing lookup.
>
> The bug was reproduced with btrfs-progs v4.2.2.
>
> Cc: Gene Cumm <gene.cumm at gmail.com>
> Cc: H. Peter Anvin <hpa at zytor.com>
> Signed-off-by: Paulo Alcantara <pcacjr at zytor.com>
> ---
> v1 -> v2:
>  * Do not set ignore_key multiple times. Set it before parsing chunk
>    tree.
> v2 -> v3:
>  * Replace an unnecessary goto with a continue statement.
Merged and pushed.  Thanks Paulo.

-- 
-Gene