[PATCH V2] Add support for BTRFS raid5/6 to GRUB

[PATCH V2] Add support for BTRFS raid5/6 to GRUB

[Goffredo Baroncelli]

Hi All,

the aim of this patches set is to provide support for a BTRFS raid5/6
 filesystem in GRUB.

The first patch, implements the basic support for raid5/6. I.e this works when
 all the disks
are present.

The next 4 patches, are preparatory ones.

The last two implements the support for raid5/6 recovery. It allow to read
from the filesystem even when 1 or 2 (for raid 6) disk(s) are missing.

The last one is the more controversial. The code for the raid6 recovery is
copied from the GRUB file reaid6_recovery.c . I preferred this approach,
because the original code assumes that the read is GRUB_DISK_SECTOR_SIZE
bytes based (512 bytes). Instead the GRUB BTRFS implementation need to
read the disk with a granularity of the byte.
I tried to update the code (and the function which the code calls), but
the change was quite invasive. So for now I preferred to duplicating the
code, to get some feedback.

I tested the code in grub-emu, and it works (for me) both with all the disks,
 and with some disks missing. I checked the sh1sums calculated from grub and
from linux and these matched.

Comments are welcome.

BR
G.Baroncelli


--
gpg @keyserver.linux.it: Goffredo Baroncelli <kreijackATinwind.it>
Key fingerprint BBF5 1610 0B64 DAC6 5F7D  17B2 0EDA 9B37 8B82 E0B5

[PATCH 1/7] Add support for reading a filesystem with a raid5 or raid6 profile.

[Goffredo Baroncelli]

Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
---
 grub-core/fs/btrfs.c | 32 ++++++++++++++++++++++++++++++++
 1 file changed, 32 insertions(+)

diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
index be195448d..b0032ea46 100644
--- a/grub-core/fs/btrfs.c
+++ b/grub-core/fs/btrfs.c
@@ -119,6 +119,8 @@ struct grub_btrfs_chunk_item
 #define GRUB_BTRFS_CHUNK_TYPE_RAID1         0x10
 #define GRUB_BTRFS_CHUNK_TYPE_DUPLICATED    0x20
 #define GRUB_BTRFS_CHUNK_TYPE_RAID10        0x40
+#define GRUB_BTRFS_CHUNK_TYPE_RAID5         0x80
+#define GRUB_BTRFS_CHUNK_TYPE_RAID6        0x100
   grub_uint8_t dummy2[0xc];
   grub_uint16_t nstripes;
   grub_uint16_t nsubstripes;
@@ -764,6 +766,36 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
 	      stripe_offset = low + chunk_stripe_length
 		* high;
 	      csize = chunk_stripe_length - low;
+	      break;
+	    }
+	  case GRUB_BTRFS_CHUNK_TYPE_RAID5:
+	  case GRUB_BTRFS_CHUNK_TYPE_RAID6:
+	    {
+	      grub_uint64_t nparities;
+	      grub_uint64_t stripe_nr, high;
+	      grub_uint64_t low;
+
+	      redundancy = 1;	/* no redundancy for now */
+
+	      if (grub_le_to_cpu64 (chunk->type) & GRUB_BTRFS_CHUNK_TYPE_RAID5)
+		{
+		  grub_dprintf ("btrfs", "RAID5\n");
+		  nparities = 1;
+		}
+	      else
+		{
+		  grub_dprintf ("btrfs", "RAID6\n");
+		  nparities = 2;
+		}
+
+	      stripe_nr = grub_divmod64 (off, chunk_stripe_length, &low);
+
+	      high = grub_divmod64 (stripe_nr, nstripes - nparities, &stripen);
+	      grub_divmod64 (high + stripen, nstripes, &stripen);
+
+	      stripe_offset = low + chunk_stripe_length * high;
+	      csize = chunk_stripe_length - low;
+
 	      break;
 	    }
 	  default:
-- 
2.17.0

[PATCH 2/7] Add helper to check the btrfs header.

[Goffredo Baroncelli]

This helper was used in few places to help the debugging. As conservative
approach, in case of error it is only logged.

Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
---
 grub-core/fs/btrfs.c | 22 +++++++++++++++++++++-
 1 file changed, 21 insertions(+), 1 deletion(-)

diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
index b0032ea46..01a1fc7a1 100644
--- a/grub-core/fs/btrfs.c
+++ b/grub-core/fs/btrfs.c
@@ -77,7 +77,8 @@ struct btrfs_header
 {
   grub_btrfs_checksum_t checksum;
   grub_btrfs_uuid_t uuid;
-  grub_uint8_t dummy[0x30];
+  grub_uint64_t bytenr;
+  grub_uint8_t dummy[0x28];
   grub_uint32_t nitems;
   grub_uint8_t level;
 } GRUB_PACKED;
@@ -286,6 +287,23 @@ free_iterator (struct grub_btrfs_leaf_descriptor *desc)
   grub_free (desc->data);
 }
 
+static grub_err_t
+check_btrfs_header (struct grub_btrfs_data *data, struct btrfs_header *header,
+                    grub_disk_addr_t addr)
+{
+  if (grub_le_to_cpu64 (header->bytenr) != addr)
+    {
+      grub_dprintf ("btrfs", "btrfs_header.bytenr is not addr\n");
+      return grub_error (GRUB_ERR_BAD_FS, "header bytenr is not addr");
+    }
+  if (grub_memcmp (data->sblock.uuid, header->uuid, sizeof(grub_btrfs_uuid_t)))
+    {
+      grub_dprintf ("btrfs", "btrfs_header.uuid doesn't match\n");
+      return grub_error (GRUB_ERR_BAD_FS, "header uuid doesn't match");
+    }
+  return GRUB_ERR_NONE;
+}
+
 static grub_err_t
 save_ref (struct grub_btrfs_leaf_descriptor *desc,
 	  grub_disk_addr_t addr, unsigned i, unsigned m, int l)
@@ -341,6 +359,7 @@ next (struct grub_btrfs_data *data,
 
       err = grub_btrfs_read_logical (data, grub_le_to_cpu64 (node.addr),
 				     &head, sizeof (head), 0);
+      check_btrfs_header (data, &head, grub_le_to_cpu64 (node.addr));
       if (err)
 	return -err;
 
@@ -402,6 +421,7 @@ lower_bound (struct grub_btrfs_data *data,
       /* FIXME: preread few nodes into buffer. */
       err = grub_btrfs_read_logical (data, addr, &head, sizeof (head),
 				     recursion_depth + 1);
+      check_btrfs_header (data, &head, addr);
       if (err)
 	return err;
       addr += sizeof (head);
-- 
2.17.0

[PATCH 3/7] Move from the find_device the error logging logic to the callee.

[Goffredo Baroncelli]

Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
---
 grub-core/fs/btrfs.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
index 01a1fc7a1..745bb854e 100644
--- a/grub-core/fs/btrfs.c
+++ b/grub-core/fs/btrfs.c
@@ -602,9 +602,6 @@ find_device (struct grub_btrfs_data *data, grub_uint64_t id, int do_rescan)
     grub_device_iterate (find_device_iter, &ctx);
   if (!ctx.dev_found)
     {
-      grub_error (GRUB_ERR_BAD_FS,
-		  N_("couldn't find a necessary member device "
-		     "of multi-device filesystem"));
       return NULL;
     }
   data->n_devices_attached++;
@@ -862,6 +859,9 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
 		dev = find_device (data, stripe->device_id, j);
 		if (!dev)
 		  {
+		    grub_dprintf ("btrfs",
+				  "couldn't find a necessary member device "
+				  "of multi-device filesystem\n");
 		    err = grub_errno;
 		    grub_errno = GRUB_ERR_NONE;
 		    continue;
-- 
2.17.0

[PATCH 4/7] Avoiding scanning for an already not found device.

[Goffredo Baroncelli]

If a device is missing, create the entry in data->devices_attached[] array.
This avoid un-necessary devices rescan.

Signed-off-by: Goffredo Baroncelli <kreikack@inwind.it>
---
 grub-core/fs/btrfs.c | 19 +++++++++----------
 1 file changed, 9 insertions(+), 10 deletions(-)

diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
index 745bb854e..d6c3adbe4 100644
--- a/grub-core/fs/btrfs.c
+++ b/grub-core/fs/btrfs.c
@@ -586,7 +586,7 @@ find_device_iter (const char *name, void *data)
 }
 
 static grub_device_t
-find_device (struct grub_btrfs_data *data, grub_uint64_t id, int do_rescan)
+find_device (struct grub_btrfs_data *data, grub_uint64_t id)
 {
   struct find_device_ctx ctx = {
     .data = data,
@@ -598,12 +598,9 @@ find_device (struct grub_btrfs_data *data, grub_uint64_t id, int do_rescan)
   for (i = 0; i < data->n_devices_attached; i++)
     if (id == data->devices_attached[i].id)
       return data->devices_attached[i].dev;
-  if (do_rescan)
-    grub_device_iterate (find_device_iter, &ctx);
-  if (!ctx.dev_found)
-    {
-      return NULL;
-    }
+
+  grub_device_iterate (find_device_iter, &ctx);
+
   data->n_devices_attached++;
   if (data->n_devices_attached > data->n_devices_allocated)
     {
@@ -615,7 +612,8 @@ find_device (struct grub_btrfs_data *data, grub_uint64_t id, int do_rescan)
 			* sizeof (data->devices_attached[0]));
       if (!data->devices_attached)
 	{
-	  grub_device_close (ctx.dev_found);
+	  if (ctx.dev_found)
+	    grub_device_close (ctx.dev_found);
 	  data->devices_attached = tmp;
 	  return NULL;
 	}
@@ -856,7 +854,7 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
 			      " for laddr 0x%" PRIxGRUB_UINT64_T "\n", paddr,
 			      addr);
 
-		dev = find_device (data, stripe->device_id, j);
+		dev = find_device (data, stripe->device_id);
 		if (!dev)
 		  {
 		    grub_dprintf ("btrfs",
@@ -933,7 +931,8 @@ grub_btrfs_unmount (struct grub_btrfs_data *data)
   unsigned i;
   /* The device 0 is closed one layer upper.  */
   for (i = 1; i < data->n_devices_attached; i++)
-    grub_device_close (data->devices_attached[i].dev);
+    if (data->devices_attached[i].dev)
+        grub_device_close (data->devices_attached[i].dev);
   grub_free (data->devices_attached);
   grub_free (data->extent);
   grub_free (data);
-- 
2.17.0

[PATCH 5/7] Refactor the code of read from disk

[Goffredo Baroncelli]

This is a preparatory patch, to help the adding of the raid5/6 recovery code

Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
---
 grub-core/fs/btrfs.c | 111 ++++++++++++++++++++++++-------------------
 1 file changed, 62 insertions(+), 49 deletions(-)

diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
index d6c3adbe4..697322125 100644
--- a/grub-core/fs/btrfs.c
+++ b/grub-core/fs/btrfs.c
@@ -623,6 +623,47 @@ find_device (struct grub_btrfs_data *data, grub_uint64_t id)
   return ctx.dev_found;
 }
 
+static grub_err_t
+btrfs_read_from_chunk (struct grub_btrfs_data *data,
+		       struct grub_btrfs_chunk_item *chunk,
+		       grub_uint64_t stripen, grub_uint64_t stripe_offset,
+		       int redundancy, grub_uint64_t csize,
+		       void *buf)
+{
+
+    struct grub_btrfs_chunk_stripe *stripe;
+    grub_disk_addr_t paddr;
+    grub_device_t dev;
+    grub_err_t err;
+
+    stripe = (struct grub_btrfs_chunk_stripe *) (chunk + 1);
+    /* Right now the redundancy handling is easy.
+       With RAID5-like it will be more difficult.  */
+    stripe += stripen + redundancy;
+
+    paddr = grub_le_to_cpu64 (stripe->offset) + stripe_offset;
+
+    grub_dprintf ("btrfs", "stripe %" PRIxGRUB_UINT64_T
+		  " maps to 0x%" PRIxGRUB_UINT64_T "\n",
+		  stripen, stripe->offset);
+    grub_dprintf ("btrfs", "reading paddr 0x%" PRIxGRUB_UINT64_T "\n", paddr);
+
+    dev = find_device (data, stripe->device_id);
+    if (!dev)
+      {
+	grub_dprintf ("btrfs",
+		      "couldn't find a necessary member device "
+		      "of multi-device filesystem\n");
+	grub_errno = GRUB_ERR_NONE;
+	return GRUB_ERR_READ_ERROR;
+      }
+
+    err = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS,
+			  paddr & (GRUB_DISK_SECTOR_SIZE - 1),
+			  csize, buf);
+    return err;
+}
+
 static grub_err_t
 grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
 			 void *buf, grub_size_t size, int recursion_depth)
@@ -636,7 +677,6 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
       grub_err_t err = 0;
       struct grub_btrfs_key key_out;
       int challoc = 0;
-      grub_device_t dev;
       struct grub_btrfs_key key_in;
       grub_size_t chsize;
       grub_disk_addr_t chaddr;
@@ -825,55 +865,28 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
 	if (csize > (grub_uint64_t) size)
 	  csize = size;
 
-	for (j = 0; j < 2; j++)
+	err = GRUB_ERR_NONE + 1;
+
+	for (j = 0; j < 2 && err != GRUB_ERR_NONE; j++)
 	  {
-	    for (i = 0; i < redundancy; i++)
-	      {
-		struct grub_btrfs_chunk_stripe *stripe;
-		grub_disk_addr_t paddr;
-
-		stripe = (struct grub_btrfs_chunk_stripe *) (chunk + 1);
-		/* Right now the redundancy handling is easy.
-		   With RAID5-like it will be more difficult.  */
-		stripe += stripen + i;
-
-		paddr = grub_le_to_cpu64 (stripe->offset) + stripe_offset;
-
-		grub_dprintf ("btrfs", "chunk 0x%" PRIxGRUB_UINT64_T
-			      "+0x%" PRIxGRUB_UINT64_T
-			      " (%d stripes (%d substripes) of %"
-			      PRIxGRUB_UINT64_T ") stripe %" PRIxGRUB_UINT64_T
-			      " maps to 0x%" PRIxGRUB_UINT64_T "\n",
-			      grub_le_to_cpu64 (key->offset),
-			      grub_le_to_cpu64 (chunk->size),
-			      grub_le_to_cpu16 (chunk->nstripes),
-			      grub_le_to_cpu16 (chunk->nsubstripes),
-			      grub_le_to_cpu64 (chunk->stripe_length),
-			      stripen, stripe->offset);
-		grub_dprintf ("btrfs", "reading paddr 0x%" PRIxGRUB_UINT64_T
-			      " for laddr 0x%" PRIxGRUB_UINT64_T "\n", paddr,
-			      addr);
-
-		dev = find_device (data, stripe->device_id);
-		if (!dev)
-		  {
-		    grub_dprintf ("btrfs",
-				  "couldn't find a necessary member device "
-				  "of multi-device filesystem\n");
-		    err = grub_errno;
-		    grub_errno = GRUB_ERR_NONE;
-		    continue;
-		  }
-
-		err = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS,
-				      paddr & (GRUB_DISK_SECTOR_SIZE - 1),
-				      csize, buf);
-		if (!err)
-		  break;
-		grub_errno = GRUB_ERR_NONE;
-	      }
-	    if (i != redundancy)
-	      break;
+	    grub_dprintf ("btrfs", "chunk 0x%" PRIxGRUB_UINT64_T
+			  "+0x%" PRIxGRUB_UINT64_T
+			  " (%d stripes (%d substripes) of %"
+			  PRIxGRUB_UINT64_T ") \n",
+			  grub_le_to_cpu64 (key->offset),
+			  grub_le_to_cpu64 (chunk->size),
+			  grub_le_to_cpu16 (chunk->nstripes),
+			  grub_le_to_cpu16 (chunk->nsubstripes),
+			  grub_le_to_cpu64 (chunk->stripe_length));
+	    grub_dprintf ("btrfs", "reading laddr 0x%" PRIxGRUB_UINT64_T "\n",
+			  addr);
+
+	    err = GRUB_ERR_NONE + 1;
+	    for (i = 0; i < redundancy && err != GRUB_ERR_NONE; i++)
+		 err = btrfs_read_from_chunk (data, chunk, stripen,
+					      stripe_offset,
+					      i,     /* redundancy */
+					      csize, buf);
 	  }
 	if (err)
 	  return grub_errno = err;
-- 
2.17.0

[PATCH 6/7] Add support for recovery for a raid5 btrfs profiles.

[Goffredo Baroncelli]

Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
---
 grub-core/fs/btrfs.c | 206 +++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 199 insertions(+), 7 deletions(-)

diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
index 697322125..5c76a68f3 100644
--- a/grub-core/fs/btrfs.c
+++ b/grub-core/fs/btrfs.c
@@ -29,6 +29,7 @@
 #include <minilzo.h>
 #include <grub/i18n.h>
 #include <grub/btrfs.h>
+#include <grub/crypto.h>
 
 GRUB_MOD_LICENSE ("GPLv3+");
 
@@ -661,9 +662,180 @@ btrfs_read_from_chunk (struct grub_btrfs_data *data,
     err = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS,
 			  paddr & (GRUB_DISK_SECTOR_SIZE - 1),
 			  csize, buf);
+    grub_dprintf ("btrfs", "reading paddr 0x%" PRIxGRUB_UINT64_T "\n", paddr);
     return err;
 }
 
+struct raid56_buffer {
+  void *buf;
+  int  ok;
+};
+
+static void
+rebuild_raid5 (struct raid56_buffer *buffers, grub_uint64_t nstripes,
+               grub_uint64_t csize)
+{
+  grub_uint64_t target, i;
+
+  target = 0;
+  while (buffers[target].ok && target < nstripes)
+    ++target;
+
+  if (target == nstripes)
+    {
+      grub_dprintf ("btrfs", "called rebuild_raid5(), but all disks are OK\n");
+      return;
+    }
+
+  grub_dprintf ("btrfs", "rebuilding raid5 stripe #%" PRIuGRUB_UINT64_T "\n",
+	        target);
+  for (i = 0; i < nstripes ; i++)
+    if (i != target)
+      grub_crypto_xor (buffers[target].buf, buffers[target].buf, buffers[i].buf,
+                       csize);
+}
+
+static void
+rebuild_raid6 (struct raid56_buffer *buffers, grub_uint64_t nstripes,
+               grub_uint64_t csize, grub_uint64_t parities_pos, void *dest,
+               grub_uint64_t stripen)
+
+{
+  (void)buffers;
+  (void)nstripes;
+  (void)csize;
+  (void)parities_pos;
+  (void)dest;
+  (void)stripen;
+  grub_dprintf ("btrfs", "called rebuild_raid6(), NOT IMPLEMENTED\n");
+}
+
+static grub_err_t
+raid56_read_retry (struct grub_btrfs_data *data,
+		   struct grub_btrfs_chunk_item *chunk,
+		   grub_uint64_t stripe_offset, grub_uint64_t stripen,
+		   grub_uint64_t csize, void *buf, grub_uint64_t parities_pos)
+{
+
+  struct raid56_buffer *buffers = NULL;
+  grub_uint64_t nstripes = grub_le_to_cpu16 (chunk->nstripes);
+  grub_uint64_t chunk_type = grub_le_to_cpu64 (chunk->type);
+  grub_err_t ret = GRUB_ERR_NONE;
+  grub_uint64_t i, failed_devices;
+
+  buffers = grub_zalloc (sizeof(struct raid56_buffer)* nstripes);
+  if (!buffers)
+    {
+      ret = GRUB_ERR_OUT_OF_MEMORY;
+      goto cleanup;
+    }
+
+  for (i = 0 ; i < nstripes ; i++)
+    {
+      buffers[i].buf = grub_zalloc(csize);
+      if (!buffers[i].buf)
+	{
+	  ret = GRUB_ERR_OUT_OF_MEMORY;
+	  goto cleanup;
+	}
+    }
+
+  for (i = 0 ; i < nstripes ; i++)
+    {
+      struct grub_btrfs_chunk_stripe *stripe;
+      grub_disk_addr_t paddr;
+      grub_device_t dev;
+      grub_err_t err2;
+
+      stripe = (struct grub_btrfs_chunk_stripe *) (chunk + 1);
+      stripe += i;
+
+      paddr = grub_le_to_cpu64 (stripe->offset) + stripe_offset;
+      grub_dprintf ("btrfs", "reading paddr %" PRIxGRUB_UINT64_T
+                    " from stripe ID %" PRIxGRUB_UINT64_T "\n", paddr,
+                    stripe->device_id);
+
+      /* FIXME: rescan the devices */
+      dev = find_device (data, stripe->device_id);
+      if (!dev)
+	{
+	  buffers[i].ok = 0;
+	  grub_dprintf ("btrfs", "stripe %" PRIuGRUB_UINT64_T " FAILED (dev ID %"
+			PRIxGRUB_UINT64_T ")\n", i, stripe->device_id);
+	  continue;
+        }
+
+      err2 = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS,
+			     paddr & (GRUB_DISK_SECTOR_SIZE - 1),
+			     csize, buffers[i].buf);
+      if (err2 == GRUB_ERR_NONE)
+	{
+	  buffers[i].ok = 1;
+	  grub_dprintf ("btrfs", "stripe %" PRIuGRUB_UINT64_T " Ok (dev ID %"
+			PRIxGRUB_UINT64_T ")\n", i, stripe->device_id);
+	}
+      else
+	{
+	  buffers[i].ok = 0;
+	  grub_dprintf ("btrfs", "stripe %" PRIuGRUB_UINT64_T
+			" FAILED (dev ID %" PRIxGRUB_UINT64_T ")\n", i,
+			stripe->device_id);
+	}
+    }
+
+  failed_devices = 0;
+  for (i = 0 ; i < nstripes ; i++)
+    if (!buffers[i].ok)
+      ++failed_devices;
+  if (failed_devices > 1 && (chunk_type & GRUB_BTRFS_CHUNK_TYPE_RAID5))
+    {
+      grub_dprintf ("btrfs",
+		    "not enough disks for raid5: total %" PRIuGRUB_UINT64_T
+		    ", missing %" PRIuGRUB_UINT64_T "\n",
+		    nstripes, failed_devices);
+      ret = GRUB_ERR_READ_ERROR;
+      goto cleanup;
+    }
+  else if (failed_devices > 2 && (chunk_type & GRUB_BTRFS_CHUNK_TYPE_RAID6))
+    {
+      grub_dprintf ("btrfs",
+		    "not enough disks for raid6: total %" PRIuGRUB_UINT64_T
+		    ", missing %" PRIuGRUB_UINT64_T "\n",
+		    nstripes, failed_devices);
+      ret = GRUB_ERR_READ_ERROR;
+      goto cleanup;
+    }
+  else
+    {
+      grub_dprintf ("btrfs",
+                    "enough disks for raid5/6 rebuilding: total %"
+		    PRIuGRUB_UINT64_T ", missing %" PRIuGRUB_UINT64_T "\n",
+                    nstripes, failed_devices);
+    }
+
+  /* if these are enough, try to rebuild the data */
+  if (chunk_type & GRUB_BTRFS_CHUNK_TYPE_RAID5)
+    {
+      rebuild_raid5 (buffers, nstripes, csize);
+      grub_memcpy (buf, buffers[stripen].buf, csize);
+    }
+  else
+    {
+      rebuild_raid6 (buffers, nstripes, csize, parities_pos, buf, stripen);
+    }
+
+cleanup:
+  if (buffers)
+    {
+      for (i = 0 ; i < nstripes ; i++)
+	if (buffers[i].buf)
+	  grub_free(buffers[i].buf);
+      grub_free(buffers);
+    }
+
+  return ret;
+}
+
 static grub_err_t
 grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
 			 void *buf, grub_size_t size, int recursion_depth)
@@ -741,6 +913,11 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
 	grub_uint16_t nstripes;
 	unsigned redundancy = 1;
 	unsigned i, j;
+        int is_raid56;
+	grub_uint64_t parities_pos = 0;
+
+        is_raid56 = !!(grub_le_to_cpu64 (chunk->type) &
+		    (GRUB_BTRFS_CHUNK_TYPE_RAID5|GRUB_BTRFS_CHUNK_TYPE_RAID6));
 
 	if (grub_le_to_cpu64 (chunk->size) <= off)
 	  {
@@ -844,9 +1021,10 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
 		}
 
 	      stripe_nr = grub_divmod64 (off, chunk_stripe_length, &low);
-
 	      high = grub_divmod64 (stripe_nr, nstripes - nparities, &stripen);
 	      grub_divmod64 (high + stripen, nstripes, &stripen);
+	      grub_divmod64 (high + nstripes - nparities, nstripes,
+			     &parities_pos);
 
 	      stripe_offset = low + chunk_stripe_length * high;
 	      csize = chunk_stripe_length - low;
@@ -881,12 +1059,26 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
 	    grub_dprintf ("btrfs", "reading laddr 0x%" PRIxGRUB_UINT64_T "\n",
 			  addr);
 
-	    err = GRUB_ERR_NONE + 1;
-	    for (i = 0; i < redundancy && err != GRUB_ERR_NONE; i++)
-		 err = btrfs_read_from_chunk (data, chunk, stripen,
-					      stripe_offset,
-					      i,     /* redundancy */
-					      csize, buf);
+	    if (!is_raid56)
+	      {
+		err = GRUB_ERR_NONE+1;
+		for (i = 0; i < redundancy && err != GRUB_ERR_NONE; i++)
+		    err = btrfs_read_from_chunk (data, chunk, stripen,
+						 stripe_offset,
+						 i,     /* use mirror #nr */
+						 csize, buf);
+	      }
+	    else
+	      {
+		err = btrfs_read_from_chunk (data, chunk, stripen,
+					     stripe_offset,
+					     0,     /* no mirror */
+					     csize, buf);
+		if (err != GRUB_ERR_NONE)
+		  err = raid56_read_retry (data, chunk, stripe_offset,
+					   stripen, csize, buf, parities_pos);
+	      }
+
 	  }
 	if (err)
 	  return grub_errno = err;
-- 
2.17.0

[PATCH 7/7] Add raid6 recovery.

[Goffredo Baroncelli]

The code origins from "raid6_recovery.c". The code was changed because the
original one assumed that both the disk address and size are multiple of
GRUB_DISK_SECTOR_SIZE. This is not true for grub btrfs driver.

The code was made more generalized using a function pointer for reading
the data from the memory or disk.

Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
---
 grub-core/fs/btrfs.c | 211 +++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 204 insertions(+), 7 deletions(-)

diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
index 5c76a68f3..195313a31 100644
--- a/grub-core/fs/btrfs.c
+++ b/grub-core/fs/btrfs.c
@@ -30,6 +30,7 @@
 #include <grub/i18n.h>
 #include <grub/btrfs.h>
 #include <grub/crypto.h>
+#include <grub/diskfilter.h>
 
 GRUB_MOD_LICENSE ("GPLv3+");
 
@@ -695,19 +696,215 @@ rebuild_raid5 (struct raid56_buffer *buffers, grub_uint64_t nstripes,
                        csize);
 }
 
+
+/* copied from raid6_recover */
+/* x**y.  */
+static grub_uint8_t powx[255 * 2];
+/* Such an s that x**s = y */
+static unsigned powx_inv[256];
+static const grub_uint8_t poly = 0x1d;
+
+static void
+grub_raid_block_mulx (unsigned mul, char *buf, grub_size_t size)
+{
+  grub_size_t i;
+  grub_uint8_t *p;
+
+  p = (grub_uint8_t *) buf;
+  for (i = 0; i < size; i++, p++)
+    if (*p)
+      *p = powx[mul + powx_inv[*p]];
+}
+
+static void
+grub_raid6_init_table (void)
+{
+  unsigned i;
+
+  grub_uint8_t cur = 1;
+  for (i = 0; i < 255; i++)
+    {
+      powx[i] = cur;
+      powx[i + 255] = cur;
+      powx_inv[cur] = i;
+      if (cur & 0x80)
+	cur = (cur << 1) ^ poly;
+      else
+	cur <<= 1;
+    }
+}
+
+static unsigned
+mod_255 (unsigned x)
+{
+  while (x > 0xff)
+    x = (x >> 8) + (x & 0xff);
+  if (x == 0xff)
+    return 0;
+  return x;
+}
+
+typedef grub_err_t (* raid_recover_read_t)(void *data, int disk_nr,
+					   grub_uint64_t addr, void *dest,
+					   grub_size_t size);
+#if 0
+/*
+ * code example to be used in raid6_recover.
+ */
+static grub_err_t
+raid_recover_read_diskfilter_array (void *data, int disk_nr,
+				    grub_uint64_t sector,
+				    void *buf, grub_size_t size)
+{
+    struct grub_diskfilter_segment *array = data;
+    return grub_diskfilter_read_node (&array->nodes[disk_nr],
+				      (grub_disk_addr_t)sector,
+				      size >> GRUB_DISK_SECTOR_BITS, buf);
+}
+#endif
+
+static grub_err_t
+raid_recover_read_raid56_buffer (void *data, int disk_nr, grub_uint64_t addr,
+                                 void *dest, grub_size_t size)
+{
+    struct raid56_buffer *buffers = data;
+
+    (void)addr;
+    grub_memcpy(dest, buffers[disk_nr].buf, size);
+
+    grub_errno = buffers[disk_nr].ok ? GRUB_ERR_NONE : GRUB_ERR_READ_ERROR;
+    return grub_errno;
+}
+
+static grub_err_t
+grub_raid6_recover (void *data, grub_uint64_t nstripes, int disknr, int p,
+                    char *buf, grub_uint64_t sector, grub_size_t size,
+		    raid_recover_read_t read_func, int layout)
+{
+  int i, q, pos;
+  int bad1 = -1, bad2 = -1;
+  char *pbuf = 0, *qbuf = 0;
+  static int table_initializated = 0;
+
+  if (!table_initializated)
+    {
+      grub_raid6_init_table();
+      table_initializated = 1;
+    }
+
+  pbuf = grub_zalloc (size);
+  if (!pbuf)
+    goto quit;
+
+  qbuf = grub_zalloc (size);
+  if (!qbuf)
+    goto quit;
+
+  q = p + 1;
+  if (q == (int) nstripes)
+    q = 0;
+
+  pos = q + 1;
+  if (pos == (int) nstripes)
+    pos = 0;
+
+  for (i = 0; i < (int) nstripes - 2; i++)
+    {
+      int c;
+      if (layout & GRUB_RAID_LAYOUT_MUL_FROM_POS)
+	c = pos;
+      else
+	c = i;
+      if (pos == disknr)
+        bad1 = c;
+      else
+        {
+	  if (!read_func(data, pos, sector, buf, size))
+            {
+              grub_crypto_xor (pbuf, pbuf, buf, size);
+              grub_raid_block_mulx (c, buf, size);
+              grub_crypto_xor (qbuf, qbuf, buf, size);
+            }
+          else
+            {
+              /* Too many bad devices */
+              if (bad2 >= 0)
+                goto quit;
+
+              bad2 = c;
+              grub_errno = GRUB_ERR_NONE;
+            }
+        }
+
+      pos++;
+      if (pos == (int) nstripes)
+        pos = 0;
+    }
+
+  /* Invalid disknr or p */
+  if (bad1 < 0)
+    goto quit;
+
+  if (bad2 < 0)
+    {
+      /* One bad device */
+      if (!read_func(data, p, sector, buf, size))
+        {
+          grub_crypto_xor (buf, buf, pbuf, size);
+          goto quit;
+        }
+
+      grub_errno = GRUB_ERR_NONE;
+      if (read_func(data, q, sector, buf, size))
+        goto quit;
+
+      grub_crypto_xor (buf, buf, qbuf, size);
+      grub_raid_block_mulx (255 - bad1, buf,
+                           size);
+    }
+  else
+    {
+      /* Two bad devices */
+      unsigned c;
+
+      if (read_func(data, p, sector, buf, size))
+        goto quit;
+
+      grub_crypto_xor (pbuf, pbuf, buf, size);
+
+      if (read_func(data, q, sector, buf, size))
+        goto quit;
+
+      grub_crypto_xor (qbuf, qbuf, buf, size);
+
+      c = mod_255((255 ^ bad1)
+		  + (255 ^ powx_inv[(powx[bad2 + (bad1 ^ 255)] ^ 1)]));
+      grub_raid_block_mulx (c, qbuf, size);
+
+      c = mod_255((unsigned) bad2 + c);
+      grub_raid_block_mulx (c, pbuf, size);
+
+      grub_crypto_xor (pbuf, pbuf, qbuf, size);
+      grub_memcpy (buf, pbuf, size);
+    }
+
+quit:
+  grub_free (pbuf);
+  grub_free (qbuf);
+
+  return grub_errno;
+}
+
+/* end copy */
 static void
 rebuild_raid6 (struct raid56_buffer *buffers, grub_uint64_t nstripes,
                grub_uint64_t csize, grub_uint64_t parities_pos, void *dest,
                grub_uint64_t stripen)
 
 {
-  (void)buffers;
-  (void)nstripes;
-  (void)csize;
-  (void)parities_pos;
-  (void)dest;
-  (void)stripen;
-  grub_dprintf ("btrfs", "called rebuild_raid6(), NOT IMPLEMENTED\n");
+  grub_raid6_recover (buffers, nstripes, stripen, parities_pos,
+		      dest, 0, csize,
+		      raid_recover_read_raid56_buffer, 0);
 }
 
 static grub_err_t
-- 
2.17.0

Re: [PATCH 1/7] Add support for reading a filesystem with a raid5 or raid6 profile.

[Daniel Kiper]

On Tue, Apr 24, 2018 at 09:13:10PM +0200, Goffredo Baroncelli wrote:
> Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
> ---
>  grub-core/fs/btrfs.c | 32 ++++++++++++++++++++++++++++++++
>  1 file changed, 32 insertions(+)
>
> diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
> index be195448d..b0032ea46 100644
> --- a/grub-core/fs/btrfs.c
> +++ b/grub-core/fs/btrfs.c
> @@ -119,6 +119,8 @@ struct grub_btrfs_chunk_item
>  #define GRUB_BTRFS_CHUNK_TYPE_RAID1         0x10
>  #define GRUB_BTRFS_CHUNK_TYPE_DUPLICATED    0x20
>  #define GRUB_BTRFS_CHUNK_TYPE_RAID10        0x40
> +#define GRUB_BTRFS_CHUNK_TYPE_RAID5         0x80
> +#define GRUB_BTRFS_CHUNK_TYPE_RAID6        0x100

#define GRUB_BTRFS_CHUNK_TYPE_RAID5         0x80
#define GRUB_BTRFS_CHUNK_TYPE_RAID6         0x100
 Please start in one column...     ---->    ^^^^^

>    grub_uint8_t dummy2[0xc];
>    grub_uint16_t nstripes;
>    grub_uint16_t nsubstripes;
> @@ -764,6 +766,36 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>  	      stripe_offset = low + chunk_stripe_length
>  		* high;
>  	      csize = chunk_stripe_length - low;
> +	      break;
> +	    }
> +	  case GRUB_BTRFS_CHUNK_TYPE_RAID5:
> +	  case GRUB_BTRFS_CHUNK_TYPE_RAID6:
> +	    {
> +	      grub_uint64_t nparities;
> +	      grub_uint64_t stripe_nr, high;
> +	      grub_uint64_t low;

Could you define all in one line?

> +	      redundancy = 1;	/* no redundancy for now */
> +
> +	      if (grub_le_to_cpu64 (chunk->type) & GRUB_BTRFS_CHUNK_TYPE_RAID5)
> +		{
> +		  grub_dprintf ("btrfs", "RAID5\n");
> +		  nparities = 1;
> +		}
> +	      else
> +		{
> +		  grub_dprintf ("btrfs", "RAID6\n");
> +		  nparities = 2;
> +		}
> +
> +	      stripe_nr = grub_divmod64 (off, chunk_stripe_length, &low);

This is clear for me...

> +	      high = grub_divmod64 (stripe_nr, nstripes - nparities, &stripen);
> +	      grub_divmod64 (high + stripen, nstripes, &stripen);

... but not these two. Could you enlighten me?

> +	      stripe_offset = low + chunk_stripe_length * high;

???

> +	      csize = chunk_stripe_length - low;

Chunk size to read?

Daniel

Re: [PATCH 2/7] Add helper to check the btrfs header.

[Daniel Kiper]

On Tue, Apr 24, 2018 at 09:13:11PM +0200, Goffredo Baroncelli wrote:
> This helper was used in few places to help the debugging. As conservative
> approach, in case of error it is only logged.

Could you explain in the commit message why we are so conservative here?

> Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
> ---
>  grub-core/fs/btrfs.c | 22 +++++++++++++++++++++-
>  1 file changed, 21 insertions(+), 1 deletion(-)
>
> diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
> index b0032ea46..01a1fc7a1 100644
> --- a/grub-core/fs/btrfs.c
> +++ b/grub-core/fs/btrfs.c
> @@ -77,7 +77,8 @@ struct btrfs_header
>  {
>    grub_btrfs_checksum_t checksum;
>    grub_btrfs_uuid_t uuid;
> -  grub_uint8_t dummy[0x30];
> +  grub_uint64_t bytenr;
> +  grub_uint8_t dummy[0x28];
>    grub_uint32_t nitems;
>    grub_uint8_t level;
>  } GRUB_PACKED;
> @@ -286,6 +287,23 @@ free_iterator (struct grub_btrfs_leaf_descriptor *desc)
>    grub_free (desc->data);
>  }
>
> +static grub_err_t
> +check_btrfs_header (struct grub_btrfs_data *data, struct btrfs_header *header,
> +                    grub_disk_addr_t addr)
> +{
> +  if (grub_le_to_cpu64 (header->bytenr) != addr)
> +    {
> +      grub_dprintf ("btrfs", "btrfs_header.bytenr is not addr\n");
> +      return grub_error (GRUB_ERR_BAD_FS, "header bytenr is not addr");

s/is not addr/is not equal node addr/?

> +    }
> +  if (grub_memcmp (data->sblock.uuid, header->uuid, sizeof(grub_btrfs_uuid_t)))
> +    {
> +      grub_dprintf ("btrfs", "btrfs_header.uuid doesn't match\n");
> +      return grub_error (GRUB_ERR_BAD_FS, "header uuid doesn't match");

s/doesn't match/doesn't match sblock uuid/?

Daniel

Re: [PATCH 3/7] Move from the find_device the error logging logic to the callee.

[Daniel Kiper]

On Tue, Apr 24, 2018 at 09:13:12PM +0200, Goffredo Baroncelli wrote:
> Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
> ---
>  grub-core/fs/btrfs.c | 6 +++---
>  1 file changed, 3 insertions(+), 3 deletions(-)
>
> diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
> index 01a1fc7a1..745bb854e 100644
> --- a/grub-core/fs/btrfs.c
> +++ b/grub-core/fs/btrfs.c
> @@ -602,9 +602,6 @@ find_device (struct grub_btrfs_data *data, grub_uint64_t id, int do_rescan)
>      grub_device_iterate (find_device_iter, &ctx);
>    if (!ctx.dev_found)
>      {
> -      grub_error (GRUB_ERR_BAD_FS,
> -		  N_("couldn't find a necessary member device "
> -		     "of multi-device filesystem"));
>        return NULL;
>      }
>    data->n_devices_attached++;
> @@ -862,6 +859,9 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>  		dev = find_device (data, stripe->device_id, j);
>  		if (!dev)
>  		  {
> +		    grub_dprintf ("btrfs",
> +				  "couldn't find a necessary member device "
> +				  "of multi-device filesystem\n");

May I ask you to explain in the commit message why are you doing that?

Daniel

Re: [PATCH 4/7] Avoiding scanning for an already not found device.

[Daniel Kiper]

On Tue, Apr 24, 2018 at 09:13:13PM +0200, Goffredo Baroncelli wrote:
> If a device is missing, create the entry in data->devices_attached[] array.

What kind of entry? Invalid one? Please clarify this.

> This avoid un-necessary devices rescan.
>
> Signed-off-by: Goffredo Baroncelli <kreikack@inwind.it>

Otherwise LGTM.

Daniel

Re: [PATCH 5/7] Refactor the code of read from disk

[Daniel Kiper]

On Tue, Apr 24, 2018 at 09:13:14PM +0200, Goffredo Baroncelli wrote:
> This is a preparatory patch, to help the adding of the raid5/6 recovery code

OK, but please tell us why this patch is needed?

> Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
> ---
>  grub-core/fs/btrfs.c | 111 ++++++++++++++++++++++++-------------------
>  1 file changed, 62 insertions(+), 49 deletions(-)
>
> diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
> index d6c3adbe4..697322125 100644
> --- a/grub-core/fs/btrfs.c
> +++ b/grub-core/fs/btrfs.c
> @@ -623,6 +623,47 @@ find_device (struct grub_btrfs_data *data, grub_uint64_t id)
>    return ctx.dev_found;
>  }
>
> +static grub_err_t
> +btrfs_read_from_chunk (struct grub_btrfs_data *data,
> +		       struct grub_btrfs_chunk_item *chunk,
> +		       grub_uint64_t stripen, grub_uint64_t stripe_offset,
> +		       int redundancy, grub_uint64_t csize,
> +		       void *buf)
> +{
> +
> +    struct grub_btrfs_chunk_stripe *stripe;
> +    grub_disk_addr_t paddr;
> +    grub_device_t dev;
> +    grub_err_t err;
> +
> +    stripe = (struct grub_btrfs_chunk_stripe *) (chunk + 1);
> +    /* Right now the redundancy handling is easy.
> +       With RAID5-like it will be more difficult.  */
> +    stripe += stripen + redundancy;
> +
> +    paddr = grub_le_to_cpu64 (stripe->offset) + stripe_offset;
> +
> +    grub_dprintf ("btrfs", "stripe %" PRIxGRUB_UINT64_T
> +		  " maps to 0x%" PRIxGRUB_UINT64_T "\n",
> +		  stripen, stripe->offset);
> +    grub_dprintf ("btrfs", "reading paddr 0x%" PRIxGRUB_UINT64_T "\n", paddr);
> +
> +    dev = find_device (data, stripe->device_id);
> +    if (!dev)
> +      {
> +	grub_dprintf ("btrfs",
> +		      "couldn't find a necessary member device "
> +		      "of multi-device filesystem\n");
> +	grub_errno = GRUB_ERR_NONE;
> +	return GRUB_ERR_READ_ERROR;
> +      }
> +
> +    err = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS,
> +			  paddr & (GRUB_DISK_SECTOR_SIZE - 1),
> +			  csize, buf);
> +    return err;
> +}
> +
>  static grub_err_t
>  grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>  			 void *buf, grub_size_t size, int recursion_depth)
> @@ -636,7 +677,6 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>        grub_err_t err = 0;
>        struct grub_btrfs_key key_out;
>        int challoc = 0;
> -      grub_device_t dev;
>        struct grub_btrfs_key key_in;
>        grub_size_t chsize;
>        grub_disk_addr_t chaddr;
> @@ -825,55 +865,28 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>  	if (csize > (grub_uint64_t) size)
>  	  csize = size;
>
> -	for (j = 0; j < 2; j++)
> +	err = GRUB_ERR_NONE + 1;
> +
> +	for (j = 0; j < 2 && err != GRUB_ERR_NONE; j++)
>  	  {
> -	    for (i = 0; i < redundancy; i++)
> -	      {
> -		struct grub_btrfs_chunk_stripe *stripe;
> -		grub_disk_addr_t paddr;
> -
> -		stripe = (struct grub_btrfs_chunk_stripe *) (chunk + 1);
> -		/* Right now the redundancy handling is easy.
> -		   With RAID5-like it will be more difficult.  */
> -		stripe += stripen + i;
> -
> -		paddr = grub_le_to_cpu64 (stripe->offset) + stripe_offset;
> -
> -		grub_dprintf ("btrfs", "chunk 0x%" PRIxGRUB_UINT64_T
> -			      "+0x%" PRIxGRUB_UINT64_T
> -			      " (%d stripes (%d substripes) of %"
> -			      PRIxGRUB_UINT64_T ") stripe %" PRIxGRUB_UINT64_T
> -			      " maps to 0x%" PRIxGRUB_UINT64_T "\n",
> -			      grub_le_to_cpu64 (key->offset),
> -			      grub_le_to_cpu64 (chunk->size),
> -			      grub_le_to_cpu16 (chunk->nstripes),
> -			      grub_le_to_cpu16 (chunk->nsubstripes),
> -			      grub_le_to_cpu64 (chunk->stripe_length),
> -			      stripen, stripe->offset);
> -		grub_dprintf ("btrfs", "reading paddr 0x%" PRIxGRUB_UINT64_T
> -			      " for laddr 0x%" PRIxGRUB_UINT64_T "\n", paddr,
> -			      addr);
> -
> -		dev = find_device (data, stripe->device_id);
> -		if (!dev)
> -		  {
> -		    grub_dprintf ("btrfs",
> -				  "couldn't find a necessary member device "
> -				  "of multi-device filesystem\n");
> -		    err = grub_errno;
> -		    grub_errno = GRUB_ERR_NONE;
> -		    continue;
> -		  }
> -
> -		err = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS,
> -				      paddr & (GRUB_DISK_SECTOR_SIZE - 1),
> -				      csize, buf);
> -		if (!err)
> -		  break;
> -		grub_errno = GRUB_ERR_NONE;
> -	      }
> -	    if (i != redundancy)
> -	      break;
> +	    grub_dprintf ("btrfs", "chunk 0x%" PRIxGRUB_UINT64_T
> +			  "+0x%" PRIxGRUB_UINT64_T
> +			  " (%d stripes (%d substripes) of %"
> +			  PRIxGRUB_UINT64_T ") \n",
> +			  grub_le_to_cpu64 (key->offset),
> +			  grub_le_to_cpu64 (chunk->size),
> +			  grub_le_to_cpu16 (chunk->nstripes),
> +			  grub_le_to_cpu16 (chunk->nsubstripes),
> +			  grub_le_to_cpu64 (chunk->stripe_length));
> +	    grub_dprintf ("btrfs", "reading laddr 0x%" PRIxGRUB_UINT64_T "\n",
> +			  addr);
> +
> +	    err = GRUB_ERR_NONE + 1;
> +	    for (i = 0; i < redundancy && err != GRUB_ERR_NONE; i++)
> +		 err = btrfs_read_from_chunk (data, chunk, stripen,
> +					      stripe_offset,
> +					      i,     /* redundancy */
> +					      csize, buf);

It seems to me that this patch does more than it is told in commit message.
At least it plays some games with debug messages? Could you split this
patch into logical parts or if it is not possible could you say in the
commit message why are you doing this and that?

Daniel

Re: [PATCH 6/7] Add support for recovery for a raid5 btrfs profiles.

[Daniel Kiper]

On Tue, Apr 24, 2018 at 09:13:15PM +0200, Goffredo Baroncelli wrote:
> Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
> ---
>  grub-core/fs/btrfs.c | 206 +++++++++++++++++++++++++++++++++++++++++--
>  1 file changed, 199 insertions(+), 7 deletions(-)
>
> diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
> index 697322125..5c76a68f3 100644
> --- a/grub-core/fs/btrfs.c
> +++ b/grub-core/fs/btrfs.c
> @@ -29,6 +29,7 @@
>  #include <minilzo.h>
>  #include <grub/i18n.h>
>  #include <grub/btrfs.h>
> +#include <grub/crypto.h>
>
>  GRUB_MOD_LICENSE ("GPLv3+");
>
> @@ -661,9 +662,180 @@ btrfs_read_from_chunk (struct grub_btrfs_data *data,
>      err = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS,
>  			  paddr & (GRUB_DISK_SECTOR_SIZE - 1),
>  			  csize, buf);
> +    grub_dprintf ("btrfs", "reading paddr 0x%" PRIxGRUB_UINT64_T "\n", paddr);
>      return err;
>  }
>
> +struct raid56_buffer {
> +  void *buf;
> +  int  ok;

What ok is?

> +};
> +
> +static void
> +rebuild_raid5 (struct raid56_buffer *buffers, grub_uint64_t nstripes,
> +               grub_uint64_t csize)
> +{
> +  grub_uint64_t target, i;

grub_uint64_t target = 0, i;

> +  target = 0;

...then you can drop this.

> +  while (buffers[target].ok && target < nstripes)
> +    ++target;
> +
> +  if (target == nstripes)
> +    {
> +      grub_dprintf ("btrfs", "called rebuild_raid5(), but all disks are OK\n");
> +      return;
> +    }
> +
> +  grub_dprintf ("btrfs", "rebuilding raid5 stripe #%" PRIuGRUB_UINT64_T "\n",
> +	        target);
> +  for (i = 0; i < nstripes ; i++)
> +    if (i != target)
> +      grub_crypto_xor (buffers[target].buf, buffers[target].buf, buffers[i].buf,
> +                       csize);
> +}
> +
> +static void
> +rebuild_raid6 (struct raid56_buffer *buffers, grub_uint64_t nstripes,
> +               grub_uint64_t csize, grub_uint64_t parities_pos, void *dest,
> +               grub_uint64_t stripen)
> +
> +{
> +  (void)buffers;
> +  (void)nstripes;
> +  (void)csize;
> +  (void)parities_pos;
> +  (void)dest;
> +  (void)stripen;
> +  grub_dprintf ("btrfs", "called rebuild_raid6(), NOT IMPLEMENTED\n");

Could you add this function in next patch and print the relevant message
below directly instead from rebuild_raid6()?

> +}
> +
> +static grub_err_t
> +raid56_read_retry (struct grub_btrfs_data *data,
> +		   struct grub_btrfs_chunk_item *chunk,
> +		   grub_uint64_t stripe_offset, grub_uint64_t stripen,
> +		   grub_uint64_t csize, void *buf, grub_uint64_t parities_pos)
> +{
> +
> +  struct raid56_buffer *buffers = NULL;
> +  grub_uint64_t nstripes = grub_le_to_cpu16 (chunk->nstripes);
> +  grub_uint64_t chunk_type = grub_le_to_cpu64 (chunk->type);
> +  grub_err_t ret = GRUB_ERR_NONE;
> +  grub_uint64_t i, failed_devices;
> +
> +  buffers = grub_zalloc (sizeof(struct raid56_buffer)* nstripes);

... sizeof (*buffers) * nstripes ...

> +  if (!buffers)
> +    {
> +      ret = GRUB_ERR_OUT_OF_MEMORY;
> +      goto cleanup;
> +    }
> +
> +  for (i = 0 ; i < nstripes ; i++)

for (i = 0; i < nstripes; i++)

> +    {
> +      buffers[i].buf = grub_zalloc(csize);

... grub_zalloc (csize);

> +      if (!buffers[i].buf)
> +	{
> +	  ret = GRUB_ERR_OUT_OF_MEMORY;
> +	  goto cleanup;
> +	}
> +    }
> +
> +  for (i = 0 ; i < nstripes ; i++)

Ditto.

> +    {
> +      struct grub_btrfs_chunk_stripe *stripe;
> +      grub_disk_addr_t paddr;
> +      grub_device_t dev;
> +      grub_err_t err2;
> +
> +      stripe = (struct grub_btrfs_chunk_stripe *) (chunk + 1);
> +      stripe += i;
> +
> +      paddr = grub_le_to_cpu64 (stripe->offset) + stripe_offset;
> +      grub_dprintf ("btrfs", "reading paddr %" PRIxGRUB_UINT64_T
> +                    " from stripe ID %" PRIxGRUB_UINT64_T "\n", paddr,
> +                    stripe->device_id);
> +
> +      /* FIXME: rescan the devices */
> +      dev = find_device (data, stripe->device_id);
> +      if (!dev)
> +	{
> +	  buffers[i].ok = 0;
> +	  grub_dprintf ("btrfs", "stripe %" PRIuGRUB_UINT64_T " FAILED (dev ID %"
> +			PRIxGRUB_UINT64_T ")\n", i, stripe->device_id);
> +	  continue;
> +        }

Something is wrong with aligment.

> +      err2 = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS,
> +			     paddr & (GRUB_DISK_SECTOR_SIZE - 1),
> +			     csize, buffers[i].buf);
> +      if (err2 == GRUB_ERR_NONE)
> +	{
> +	  buffers[i].ok = 1;
> +	  grub_dprintf ("btrfs", "stripe %" PRIuGRUB_UINT64_T " Ok (dev ID %"
> +			PRIxGRUB_UINT64_T ")\n", i, stripe->device_id);
> +	}
> +      else
> +	{
> +	  buffers[i].ok = 0;
> +	  grub_dprintf ("btrfs", "stripe %" PRIuGRUB_UINT64_T
> +			" FAILED (dev ID %" PRIxGRUB_UINT64_T ")\n", i,
> +			stripe->device_id);
> +	}
> +    }
> +
> +  failed_devices = 0;
> +  for (i = 0 ; i < nstripes ; i++)

Ditto.

> +    if (!buffers[i].ok)
> +      ++failed_devices;
> +  if (failed_devices > 1 && (chunk_type & GRUB_BTRFS_CHUNK_TYPE_RAID5))
> +    {
> +      grub_dprintf ("btrfs",
> +		    "not enough disks for raid5: total %" PRIuGRUB_UINT64_T
> +		    ", missing %" PRIuGRUB_UINT64_T "\n",
> +		    nstripes, failed_devices);
> +      ret = GRUB_ERR_READ_ERROR;
> +      goto cleanup;
> +    }
> +  else if (failed_devices > 2 && (chunk_type & GRUB_BTRFS_CHUNK_TYPE_RAID6))
> +    {
> +      grub_dprintf ("btrfs",
> +		    "not enough disks for raid6: total %" PRIuGRUB_UINT64_T
> +		    ", missing %" PRIuGRUB_UINT64_T "\n",
> +		    nstripes, failed_devices);
> +      ret = GRUB_ERR_READ_ERROR;
> +      goto cleanup;
> +    }

This piece of code should be introduced in next patch.

> +  else
> +    {
> +      grub_dprintf ("btrfs",
> +                    "enough disks for raid5/6 rebuilding: total %"
> +		    PRIuGRUB_UINT64_T ", missing %" PRIuGRUB_UINT64_T "\n",
> +                    nstripes, failed_devices);
> +    }
> +
> +  /* if these are enough, try to rebuild the data */
> +  if (chunk_type & GRUB_BTRFS_CHUNK_TYPE_RAID5)
> +    {
> +      rebuild_raid5 (buffers, nstripes, csize);
> +      grub_memcpy (buf, buffers[stripen].buf, csize);
> +    }
> +  else
> +    {
> +      rebuild_raid6 (buffers, nstripes, csize, parities_pos, buf, stripen);

Please print not implemented messaged here instead of rebuild_raid6() call.

> +    }
> +
> +cleanup:

Please add one space before the label.

> +  if (buffers)
> +    {
> +      for (i = 0 ; i < nstripes ; i++)

Ditto.

> +	if (buffers[i].buf)
> +	  grub_free(buffers[i].buf);
> +      grub_free(buffers);
> +    }
> +
> +  return ret;
> +}
> +
>  static grub_err_t
>  grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>  			 void *buf, grub_size_t size, int recursion_depth)
> @@ -741,6 +913,11 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>  	grub_uint16_t nstripes;
>  	unsigned redundancy = 1;
>  	unsigned i, j;
> +        int is_raid56;

Incorrect aligment.

> +	grub_uint64_t parities_pos = 0;
> +
> +        is_raid56 = !!(grub_le_to_cpu64 (chunk->type) &
> +		    (GRUB_BTRFS_CHUNK_TYPE_RAID5|GRUB_BTRFS_CHUNK_TYPE_RAID6));

Do we need GRUB_BTRFS_CHUNK_TYPE_RAID6 here? Or maybe this
should be introduced by next patch?

>  	if (grub_le_to_cpu64 (chunk->size) <= off)
>  	  {
> @@ -844,9 +1021,10 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>  		}
>
>  	      stripe_nr = grub_divmod64 (off, chunk_stripe_length, &low);
> -
>  	      high = grub_divmod64 (stripe_nr, nstripes - nparities, &stripen);
>  	      grub_divmod64 (high + stripen, nstripes, &stripen);
> +	      grub_divmod64 (high + nstripes - nparities, nstripes,
> +			     &parities_pos);
>
>  	      stripe_offset = low + chunk_stripe_length * high;
>  	      csize = chunk_stripe_length - low;
> @@ -881,12 +1059,26 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>  	    grub_dprintf ("btrfs", "reading laddr 0x%" PRIxGRUB_UINT64_T "\n",
>  			  addr);
>
> -	    err = GRUB_ERR_NONE + 1;
> -	    for (i = 0; i < redundancy && err != GRUB_ERR_NONE; i++)
> -		 err = btrfs_read_from_chunk (data, chunk, stripen,
> -					      stripe_offset,
> -					      i,     /* redundancy */
> -					      csize, buf);
> +	    if (!is_raid56)
> +	      {
> +		err = GRUB_ERR_NONE+1;

What?

Daniel

Re: [PATCH 7/7] Add raid6 recovery.

[Daniel Kiper]

On Tue, Apr 24, 2018 at 09:13:16PM +0200, Goffredo Baroncelli wrote:
> The code origins from "raid6_recovery.c". The code was changed because the
> original one assumed that both the disk address and size are multiple of
> GRUB_DISK_SECTOR_SIZE. This is not true for grub btrfs driver.
>
> The code was made more generalized using a function pointer for reading
> the data from the memory or disk.
>
> Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
> ---
>  grub-core/fs/btrfs.c | 211 +++++++++++++++++++++++++++++++++++++++++--
>  1 file changed, 204 insertions(+), 7 deletions(-)
>
> diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
> index 5c76a68f3..195313a31 100644
> --- a/grub-core/fs/btrfs.c
> +++ b/grub-core/fs/btrfs.c
> @@ -30,6 +30,7 @@
>  #include <grub/i18n.h>
>  #include <grub/btrfs.h>
>  #include <grub/crypto.h>
> +#include <grub/diskfilter.h>
>
>  GRUB_MOD_LICENSE ("GPLv3+");
>
> @@ -695,19 +696,215 @@ rebuild_raid5 (struct raid56_buffer *buffers, grub_uint64_t nstripes,
>                         csize);
>  }
>
> +
> +/* copied from raid6_recover */
> +/* x**y.  */
> +static grub_uint8_t powx[255 * 2];
> +/* Such an s that x**s = y */
> +static unsigned powx_inv[256];
> +static const grub_uint8_t poly = 0x1d;

Could you define this as a constant?

> +static void
> +grub_raid_block_mulx (unsigned mul, char *buf, grub_size_t size)
> +{
> +  grub_size_t i;
> +  grub_uint8_t *p;
> +
> +  p = (grub_uint8_t *) buf;
> +  for (i = 0; i < size; i++, p++)
> +    if (*p)
> +      *p = powx[mul + powx_inv[*p]];
> +}
> +
> +static void
> +grub_raid6_init_table (void)
> +{
> +  unsigned i;
> +
> +  grub_uint8_t cur = 1;
> +  for (i = 0; i < 255; i++)
> +    {
> +      powx[i] = cur;
> +      powx[i + 255] = cur;
> +      powx_inv[cur] = i;
> +      if (cur & 0x80)
> +	cur = (cur << 1) ^ poly;
> +      else
> +	cur <<= 1;
> +    }
> +}

Could not we do this as a static? It is initialized only once.

> +static unsigned
> +mod_255 (unsigned x)
> +{
> +  while (x > 0xff)
> +    x = (x >> 8) + (x & 0xff);
> +  if (x == 0xff)
> +    return 0;
> +  return x;
> +}
> +
> +typedef grub_err_t (* raid_recover_read_t)(void *data, int disk_nr,
> +					   grub_uint64_t addr, void *dest,
> +					   grub_size_t size);
> +#if 0
> +/*
> + * code example to be used in raid6_recover.
> + */
> +static grub_err_t
> +raid_recover_read_diskfilter_array (void *data, int disk_nr,
> +				    grub_uint64_t sector,
> +				    void *buf, grub_size_t size)
> +{
> +    struct grub_diskfilter_segment *array = data;
> +    return grub_diskfilter_read_node (&array->nodes[disk_nr],
> +				      (grub_disk_addr_t)sector,
> +				      size >> GRUB_DISK_SECTOR_BITS, buf);
> +}
> +#endif

Please drop this.

> +
> +static grub_err_t
> +raid_recover_read_raid56_buffer (void *data, int disk_nr, grub_uint64_t addr,
> +                                 void *dest, grub_size_t size)
> +{
> +    struct raid56_buffer *buffers = data;
> +
> +    (void)addr;

"grub_uint64_t addr __attribute__ ((unused))" in prototype definition?

> +    grub_memcpy(dest, buffers[disk_nr].buf, size);
> +
> +    grub_errno = buffers[disk_nr].ok ? GRUB_ERR_NONE : GRUB_ERR_READ_ERROR;
> +    return grub_errno;
> +}
> +
> +static grub_err_t
> +grub_raid6_recover (void *data, grub_uint64_t nstripes, int disknr, int p,
> +                    char *buf, grub_uint64_t sector, grub_size_t size,
> +		    raid_recover_read_t read_func, int layout)
> +{
> +  int i, q, pos;
> +  int bad1 = -1, bad2 = -1;
> +  char *pbuf = 0, *qbuf = 0;
> +  static int table_initializated = 0;
> +
> +  if (!table_initializated)
> +    {
> +      grub_raid6_init_table();
> +      table_initializated = 1;
> +    }
> +
> +  pbuf = grub_zalloc (size);
> +  if (!pbuf)
> +    goto quit;
> +
> +  qbuf = grub_zalloc (size);
> +  if (!qbuf)
> +    goto quit;
> +
> +  q = p + 1;
> +  if (q == (int) nstripes)
> +    q = 0;
> +
> +  pos = q + 1;
> +  if (pos == (int) nstripes)
> +    pos = 0;
> +
> +  for (i = 0; i < (int) nstripes - 2; i++)
> +    {
> +      int c;
> +      if (layout & GRUB_RAID_LAYOUT_MUL_FROM_POS)
> +	c = pos;
> +      else
> +	c = i;
> +      if (pos == disknr)
> +        bad1 = c;
> +      else
> +        {
> +	  if (!read_func(data, pos, sector, buf, size))
> +            {
> +              grub_crypto_xor (pbuf, pbuf, buf, size);
> +              grub_raid_block_mulx (c, buf, size);
> +              grub_crypto_xor (qbuf, qbuf, buf, size);
> +            }
> +          else
> +            {
> +              /* Too many bad devices */
> +              if (bad2 >= 0)
> +                goto quit;
> +
> +              bad2 = c;
> +              grub_errno = GRUB_ERR_NONE;
> +            }
> +        }
> +
> +      pos++;
> +      if (pos == (int) nstripes)
> +        pos = 0;
> +    }
> +
> +  /* Invalid disknr or p */
> +  if (bad1 < 0)
> +    goto quit;
> +
> +  if (bad2 < 0)
> +    {
> +      /* One bad device */
> +      if (!read_func(data, p, sector, buf, size))
> +        {
> +          grub_crypto_xor (buf, buf, pbuf, size);
> +          goto quit;
> +        }
> +
> +      grub_errno = GRUB_ERR_NONE;
> +      if (read_func(data, q, sector, buf, size))
> +        goto quit;
> +
> +      grub_crypto_xor (buf, buf, qbuf, size);
> +      grub_raid_block_mulx (255 - bad1, buf,
> +                           size);
> +    }
> +  else
> +    {
> +      /* Two bad devices */
> +      unsigned c;
> +
> +      if (read_func(data, p, sector, buf, size))
> +        goto quit;
> +
> +      grub_crypto_xor (pbuf, pbuf, buf, size);
> +
> +      if (read_func(data, q, sector, buf, size))
> +        goto quit;
> +
> +      grub_crypto_xor (qbuf, qbuf, buf, size);
> +
> +      c = mod_255((255 ^ bad1)
> +		  + (255 ^ powx_inv[(powx[bad2 + (bad1 ^ 255)] ^ 1)]));
> +      grub_raid_block_mulx (c, qbuf, size);
> +
> +      c = mod_255((unsigned) bad2 + c);
> +      grub_raid_block_mulx (c, pbuf, size);
> +
> +      grub_crypto_xor (pbuf, pbuf, qbuf, size);
> +      grub_memcpy (buf, pbuf, size);
> +    }
> +
> +quit:

One space before the label please?

> +  grub_free (pbuf);
> +  grub_free (qbuf);
> +
> +  return grub_errno;
> +}
> +
> +/* end copy */
>  static void
>  rebuild_raid6 (struct raid56_buffer *buffers, grub_uint64_t nstripes,
>                 grub_uint64_t csize, grub_uint64_t parities_pos, void *dest,
>                 grub_uint64_t stripen)
>
>  {
> -  (void)buffers;
> -  (void)nstripes;
> -  (void)csize;
> -  (void)parities_pos;
> -  (void)dest;
> -  (void)stripen;
> -  grub_dprintf ("btrfs", "called rebuild_raid6(), NOT IMPLEMENTED\n");
> +  grub_raid6_recover (buffers, nstripes, stripen, parities_pos,
> +		      dest, 0, csize,
> +		      raid_recover_read_raid56_buffer, 0);

grub_raid6_recover() should be called directly from right place.

Daniel

Re: [PATCH V2] Add support for BTRFS raid5/6 to GRUB

[Daniel Kiper]

On Tue, Apr 24, 2018 at 09:13:09PM +0200, Goffredo Baroncelli wrote:
>
> Hi All,
>
> the aim of this patches set is to provide support for a BTRFS raid5/6
>  filesystem in GRUB.
>
> The first patch, implements the basic support for raid5/6. I.e this works when
>  all the disks
> are present.
>
> The next 4 patches, are preparatory ones.
>
> The last two implements the support for raid5/6 recovery. It allow to read
> from the filesystem even when 1 or 2 (for raid 6) disk(s) are missing.
>
> The last one is the more controversial. The code for the raid6 recovery is
> copied from the GRUB file reaid6_recovery.c . I preferred this approach,
> because the original code assumes that the read is GRUB_DISK_SECTOR_SIZE
> bytes based (512 bytes). Instead the GRUB BTRFS implementation need to
> read the disk with a granularity of the byte.
> I tried to update the code (and the function which the code calls), but
> the change was quite invasive. So for now I preferred to duplicating the
> code, to get some feedback.
>
> I tested the code in grub-emu, and it works (for me) both with all the disks,
>  and with some disks missing. I checked the sh1sums calculated from grub and
> from linux and these matched.
>
> Comments are welcome.

Mostly nitpicks. However, if we can reuse reaid6_recovery.c somehow that
will be great. Even if this require some more patches.

Daniel

Re: [PATCH V2] Add support for BTRFS raid5/6 to GRUB

[Goffredo Baroncelli]

On 05/09/2018 07:00 PM, Daniel Kiper wrote:
> On Tue, Apr 24, 2018 at 09:13:09PM +0200, Goffredo Baroncelli wrote:
>>
>> Hi All,
>>
>> the aim of this patches set is to provide support for a BTRFS raid5/6
>>  filesystem in GRUB.
>>
>> The first patch, implements the basic support for raid5/6. I.e this works when
>>  all the disks
>> are present.
>>
>> The next 4 patches, are preparatory ones.
>>
>> The last two implements the support for raid5/6 recovery. It allow to read
>> from the filesystem even when 1 or 2 (for raid 6) disk(s) are missing.
>>
>> The last one is the more controversial. The code for the raid6 recovery is
>> copied from the GRUB file reaid6_recovery.c . I preferred this approach,
>> because the original code assumes that the read is GRUB_DISK_SECTOR_SIZE
>> bytes based (512 bytes). Instead the GRUB BTRFS implementation need to
>> read the disk with a granularity of the byte.
>> I tried to update the code (and the function which the code calls), but
>> the change was quite invasive. So for now I preferred to duplicating the
>> code, to get some feedback.
>>
>> I tested the code in grub-emu, and it works (for me) both with all the disks,
>>  and with some disks missing. I checked the sh1sums calculated from grub and
>> from linux and these matched.
>>
>> Comments are welcome.
> 
> Mostly nitpicks. However, if we can reuse reaid6_recovery.c somehow that
> will be great. Even if this require some more patches.

I liked the idea too. I am not sure to be able to tests all the cases. Do you know if it exists a list of tests about raid6_recovery and dm ?

Anyway, I update the patch. Tomorrow I will test these and then I issue the patch set.

BR

> 
> Daniel
> 
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> https://lists.gnu.org/mailman/listinfo/grub-devel
> 


-- 
gpg @keyserver.linux.it: Goffredo Baroncelli <kreijackATinwind.it>
Key fingerprint BBF5 1610 0B64 DAC6 5F7D  17B2 0EDA 9B37 8B82 E0B5

Re: [PATCH 6/7] Add support for recovery for a raid5 btrfs profiles.

[Goffredo Baroncelli]

On 05/09/2018 06:46 PM, Daniel Kiper wrote:
> On Tue, Apr 24, 2018 at 09:13:15PM +0200, Goffredo Baroncelli wrote:
>> Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
>> ---
>>  grub-core/fs/btrfs.c | 206 +++++++++++++++++++++++++++++++++++++++++--
>>  1 file changed, 199 insertions(+), 7 deletions(-)
>>
>> diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
>> index 697322125..5c76a68f3 100644
>> --- a/grub-core/fs/btrfs.c
>> +++ b/grub-core/fs/btrfs.c
>> @@ -29,6 +29,7 @@
>>  #include <minilzo.h>
>>  #include <grub/i18n.h>
>>  #include <grub/btrfs.h>
>> +#include <grub/crypto.h>
>>
>>  GRUB_MOD_LICENSE ("GPLv3+");
>>
>> @@ -661,9 +662,180 @@ btrfs_read_from_chunk (struct grub_btrfs_data *data,
>>      err = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS,
>>  			  paddr & (GRUB_DISK_SECTOR_SIZE - 1),
>>  			  csize, buf);
>> +    grub_dprintf ("btrfs", "reading paddr 0x%" PRIxGRUB_UINT64_T "\n", paddr);
>>      return err;
>>  }
>>
>> +struct raid56_buffer {
>> +  void *buf;
>> +  int  ok;
> 
> What ok is?
in the next series I renamed it as "data_is_valid"
> 
>> +};
>> +
>> +static void
>> +rebuild_raid5 (struct raid56_buffer *buffers, grub_uint64_t nstripes,
>> +               grub_uint64_t csize)
>> +{
>> +  grub_uint64_t target, i;
> 
> grub_uint64_t target = 0, i;
> 
>> +  target = 0;
> 
> ...then you can drop this.
ok
> 
>> +  while (buffers[target].ok && target < nstripes)
>> +    ++target;
>> +
>> +  if (target == nstripes)
>> +    {
>> +      grub_dprintf ("btrfs", "called rebuild_raid5(), but all disks are OK\n");
>> +      return;
>> +    }
>> +
>> +  grub_dprintf ("btrfs", "rebuilding raid5 stripe #%" PRIuGRUB_UINT64_T "\n",
>> +	        target);
>> +  for (i = 0; i < nstripes ; i++)
>> +    if (i != target)
>> +      grub_crypto_xor (buffers[target].buf, buffers[target].buf, buffers[i].buf,
>> +                       csize);
>> +}
>> +
>> +static void
>> +rebuild_raid6 (struct raid56_buffer *buffers, grub_uint64_t nstripes,
>> +               grub_uint64_t csize, grub_uint64_t parities_pos, void *dest,
>> +               grub_uint64_t stripen)
>> +
>> +{
>> +  (void)buffers;
>> +  (void)nstripes;
>> +  (void)csize;
>> +  (void)parities_pos;
>> +  (void)dest;
>> +  (void)stripen;
>> +  grub_dprintf ("btrfs", "called rebuild_raid6(), NOT IMPLEMENTED\n");
> 
> Could you add this function in next patch and print the relevant message
> below directly instead from rebuild_raid6()?
Ok
> 
>> +}
>> +
>> +static grub_err_t
>> +raid56_read_retry (struct grub_btrfs_data *data,
>> +		   struct grub_btrfs_chunk_item *chunk,
>> +		   grub_uint64_t stripe_offset, grub_uint64_t stripen,
>> +		   grub_uint64_t csize, void *buf, grub_uint64_t parities_pos)
>> +{
>> +
>> +  struct raid56_buffer *buffers = NULL;
>> +  grub_uint64_t nstripes = grub_le_to_cpu16 (chunk->nstripes);
>> +  grub_uint64_t chunk_type = grub_le_to_cpu64 (chunk->type);
>> +  grub_err_t ret = GRUB_ERR_NONE;
>> +  grub_uint64_t i, failed_devices;
>> +
>> +  buffers = grub_zalloc (sizeof(struct raid56_buffer)* nstripes);
> 
> ... sizeof (*buffers) * nstripes ...
ok
> 
>> +  if (!buffers)
>> +    {
>> +      ret = GRUB_ERR_OUT_OF_MEMORY;
>> +      goto cleanup;
>> +    }
>> +
>> +  for (i = 0 ; i < nstripes ; i++)
> 
> for (i = 0; i < nstripes; i++)
ok
> 
>> +    {
>> +      buffers[i].buf = grub_zalloc(csize);
> 
> ... grub_zalloc (csize);
ok
> 
>> +      if (!buffers[i].buf)
>> +	{
>> +	  ret = GRUB_ERR_OUT_OF_MEMORY;
>> +	  goto cleanup;
>> +	}
>> +    }
>> +
>> +  for (i = 0 ; i < nstripes ; i++)
> 
> Ditto.
ok
>> +    {
>> +      struct grub_btrfs_chunk_stripe *stripe;
>> +      grub_disk_addr_t paddr;
>> +      grub_device_t dev;
>> +      grub_err_t err2;
>> +
>> +      stripe = (struct grub_btrfs_chunk_stripe *) (chunk + 1);
>> +      stripe += i;
>> +
>> +      paddr = grub_le_to_cpu64 (stripe->offset) + stripe_offset;
>> +      grub_dprintf ("btrfs", "reading paddr %" PRIxGRUB_UINT64_T
>> +                    " from stripe ID %" PRIxGRUB_UINT64_T "\n", paddr,
>> +                    stripe->device_id);
>> +
>> +      /* FIXME: rescan the devices */
>> +      dev = find_device (data, stripe->device_id);
>> +      if (!dev)
>> +	{
>> +	  buffers[i].ok = 0;
>> +	  grub_dprintf ("btrfs", "stripe %" PRIuGRUB_UINT64_T " FAILED (dev ID %"
>> +			PRIxGRUB_UINT64_T ")\n", i, stripe->device_id);
>> +	  continue;
>> +        }
> 
> Something is wrong with aligment.
ok
> 
>> +      err2 = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS,
>> +			     paddr & (GRUB_DISK_SECTOR_SIZE - 1),
>> +			     csize, buffers[i].buf);
>> +      if (err2 == GRUB_ERR_NONE)
>> +	{
>> +	  buffers[i].ok = 1;
>> +	  grub_dprintf ("btrfs", "stripe %" PRIuGRUB_UINT64_T " Ok (dev ID %"
>> +			PRIxGRUB_UINT64_T ")\n", i, stripe->device_id);
>> +	}
>> +      else
>> +	{
>> +	  buffers[i].ok = 0;
>> +	  grub_dprintf ("btrfs", "stripe %" PRIuGRUB_UINT64_T
>> +			" FAILED (dev ID %" PRIxGRUB_UINT64_T ")\n", i,
>> +			stripe->device_id);
>> +	}
>> +    }
>> +
>> +  failed_devices = 0;
>> +  for (i = 0 ; i < nstripes ; i++)
> 
> Ditto.
Ok
> 
>> +    if (!buffers[i].ok)
>> +      ++failed_devices;
>> +  if (failed_devices > 1 && (chunk_type & GRUB_BTRFS_CHUNK_TYPE_RAID5))
>> +    {
>> +      grub_dprintf ("btrfs",
>> +		    "not enough disks for raid5: total %" PRIuGRUB_UINT64_T
>> +		    ", missing %" PRIuGRUB_UINT64_T "\n",
>> +		    nstripes, failed_devices);
>> +      ret = GRUB_ERR_READ_ERROR;
>> +      goto cleanup;
>> +    }
>> +  else if (failed_devices > 2 && (chunk_type & GRUB_BTRFS_CHUNK_TYPE_RAID6))
>> +    {
>> +      grub_dprintf ("btrfs",
>> +		    "not enough disks for raid6: total %" PRIuGRUB_UINT64_T
>> +		    ", missing %" PRIuGRUB_UINT64_T "\n",
>> +		    nstripes, failed_devices);
>> +      ret = GRUB_ERR_READ_ERROR;
>> +      goto cleanup;
>> +    }
> 
> This piece of code should be introduced in next patch.
ok
> 
>> +  else
>> +    {
>> +      grub_dprintf ("btrfs",
>> +                    "enough disks for raid5/6 rebuilding: total %"
>> +		    PRIuGRUB_UINT64_T ", missing %" PRIuGRUB_UINT64_T "\n",
>> +                    nstripes, failed_devices);
>> +    }
>> +
>> +  /* if these are enough, try to rebuild the data */
>> +  if (chunk_type & GRUB_BTRFS_CHUNK_TYPE_RAID5)
>> +    {
>> +      rebuild_raid5 (buffers, nstripes, csize);
>> +      grub_memcpy (buf, buffers[stripen].buf, csize);
>> +    }
>> +  else
>> +    {
>> +      rebuild_raid6 (buffers, nstripes, csize, parities_pos, buf, stripen);
> 
> Please print not implemented messaged here instead of rebuild_raid6() call.
ok
> 
>> +    }
>> +
>> +cleanup:
> 
> Please add one space before the label.
ok
> 
>> +  if (buffers)
>> +    {
>> +      for (i = 0 ; i < nstripes ; i++)
> 
> Ditto.
ok
> 
>> +	if (buffers[i].buf)
>> +	  grub_free(buffers[i].buf);
>> +      grub_free(buffers);
>> +    }
>> +
>> +  return ret;
>> +}
>> +
>>  static grub_err_t
>>  grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>>  			 void *buf, grub_size_t size, int recursion_depth)
>> @@ -741,6 +913,11 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>>  	grub_uint16_t nstripes;
>>  	unsigned redundancy = 1;
>>  	unsigned i, j;
>> +        int is_raid56;
ok
> 
> Incorrect aligment.
> 
>> +	grub_uint64_t parities_pos = 0;
>> +
>> +        is_raid56 = !!(grub_le_to_cpu64 (chunk->type) &
>> +		    (GRUB_BTRFS_CHUNK_TYPE_RAID5|GRUB_BTRFS_CHUNK_TYPE_RAID6));
> 
> Do we need GRUB_BTRFS_CHUNK_TYPE_RAID6 here? Or maybe this
> should be introduced by next patch?
ok
> 
>>  	if (grub_le_to_cpu64 (chunk->size) <= off)
>>  	  {
>> @@ -844,9 +1021,10 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>>  		}
>>
>>  	      stripe_nr = grub_divmod64 (off, chunk_stripe_length, &low);
>> -
>>  	      high = grub_divmod64 (stripe_nr, nstripes - nparities, &stripen);
>>  	      grub_divmod64 (high + stripen, nstripes, &stripen);
>> +	      grub_divmod64 (high + nstripes - nparities, nstripes,
>> +			     &parities_pos);
>>
>>  	      stripe_offset = low + chunk_stripe_length * high;
>>  	      csize = chunk_stripe_length - low;
>> @@ -881,12 +1059,26 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>>  	    grub_dprintf ("btrfs", "reading laddr 0x%" PRIxGRUB_UINT64_T "\n",
>>  			  addr);
>>
>> -	    err = GRUB_ERR_NONE + 1;
>> -	    for (i = 0; i < redundancy && err != GRUB_ERR_NONE; i++)
>> -		 err = btrfs_read_from_chunk (data, chunk, stripen,
>> -					      stripe_offset,
>> -					      i,     /* redundancy */
>> -					      csize, buf);
>> +	    if (!is_raid56)
>> +	      {
>> +		err = GRUB_ERR_NONE+1;
> 
> What?
Ok, I correct it
> 
> Daniel
> 


-- 
gpg @keyserver.linux.it: Goffredo Baroncelli <kreijackATinwind.it>
Key fingerprint BBF5 1610 0B64 DAC6 5F7D  17B2 0EDA 9B37 8B82 E0B5

Re: [PATCH 5/7] Refactor the code of read from disk

[Goffredo Baroncelli]

On 05/09/2018 04:26 PM, Daniel Kiper wrote:
> On Tue, Apr 24, 2018 at 09:13:14PM +0200, Goffredo Baroncelli wrote:
>> This is a preparatory patch, to help the adding of the raid5/6 recovery code
> 
> OK, but please tell us why this patch is needed?

I will put this commit message:

  Refactor the code that read from disk

  This is a preparatory patch, to help the adding of the raid5/6 recovery code.
  In case of availability of all disks, this code is good for all the RAID
  profiles. However in case of failure, the error handling is quite different.
  Refactoring this code increases the general readability.

> 
>> Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
>> ---
>>  grub-core/fs/btrfs.c | 111 ++++++++++++++++++++++++-------------------
>>  1 file changed, 62 insertions(+), 49 deletions(-)
>>
>> diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
>> index d6c3adbe4..697322125 100644
>> --- a/grub-core/fs/btrfs.c
>> +++ b/grub-core/fs/btrfs.c
>> @@ -623,6 +623,47 @@ find_device (struct grub_btrfs_data *data, grub_uint64_t id)
>>    return ctx.dev_found;
>>  }
>>
>> +static grub_err_t
>> +btrfs_read_from_chunk (struct grub_btrfs_data *data,
>> +		       struct grub_btrfs_chunk_item *chunk,
>> +		       grub_uint64_t stripen, grub_uint64_t stripe_offset,
>> +		       int redundancy, grub_uint64_t csize,
>> +		       void *buf)
>> +{
>> +
>> +    struct grub_btrfs_chunk_stripe *stripe;
>> +    grub_disk_addr_t paddr;
>> +    grub_device_t dev;
>> +    grub_err_t err;
>> +
>> +    stripe = (struct grub_btrfs_chunk_stripe *) (chunk + 1);
>> +    /* Right now the redundancy handling is easy.
>> +       With RAID5-like it will be more difficult.  */
>> +    stripe += stripen + redundancy;
>> +
>> +    paddr = grub_le_to_cpu64 (stripe->offset) + stripe_offset;
>> +
>> +    grub_dprintf ("btrfs", "stripe %" PRIxGRUB_UINT64_T
>> +		  " maps to 0x%" PRIxGRUB_UINT64_T "\n",
>> +		  stripen, stripe->offset);
>> +    grub_dprintf ("btrfs", "reading paddr 0x%" PRIxGRUB_UINT64_T "\n", paddr);
>> +
>> +    dev = find_device (data, stripe->device_id);
>> +    if (!dev)
>> +      {
>> +	grub_dprintf ("btrfs",
>> +		      "couldn't find a necessary member device "
>> +		      "of multi-device filesystem\n");
>> +	grub_errno = GRUB_ERR_NONE;
>> +	return GRUB_ERR_READ_ERROR;
>> +      }
>> +
>> +    err = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS,
>> +			  paddr & (GRUB_DISK_SECTOR_SIZE - 1),
>> +			  csize, buf);
>> +    return err;
>> +}
>> +
>>  static grub_err_t
>>  grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>>  			 void *buf, grub_size_t size, int recursion_depth)
>> @@ -636,7 +677,6 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>>        grub_err_t err = 0;
>>        struct grub_btrfs_key key_out;
>>        int challoc = 0;
>> -      grub_device_t dev;
>>        struct grub_btrfs_key key_in;
>>        grub_size_t chsize;
>>        grub_disk_addr_t chaddr;
>> @@ -825,55 +865,28 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>>  	if (csize > (grub_uint64_t) size)
>>  	  csize = size;
>>
>> -	for (j = 0; j < 2; j++)
>> +	err = GRUB_ERR_NONE + 1;
>> +
>> +	for (j = 0; j < 2 && err != GRUB_ERR_NONE; j++)
>>  	  {
>> -	    for (i = 0; i < redundancy; i++)
>> -	      {
>> -		struct grub_btrfs_chunk_stripe *stripe;
>> -		grub_disk_addr_t paddr;
>> -
>> -		stripe = (struct grub_btrfs_chunk_stripe *) (chunk + 1);
>> -		/* Right now the redundancy handling is easy.
>> -		   With RAID5-like it will be more difficult.  */
>> -		stripe += stripen + i;
>> -
>> -		paddr = grub_le_to_cpu64 (stripe->offset) + stripe_offset;
>> -
>> -		grub_dprintf ("btrfs", "chunk 0x%" PRIxGRUB_UINT64_T
>> -			      "+0x%" PRIxGRUB_UINT64_T
>> -			      " (%d stripes (%d substripes) of %"
>> -			      PRIxGRUB_UINT64_T ") stripe %" PRIxGRUB_UINT64_T
>> -			      " maps to 0x%" PRIxGRUB_UINT64_T "\n",
>> -			      grub_le_to_cpu64 (key->offset),
>> -			      grub_le_to_cpu64 (chunk->size),
>> -			      grub_le_to_cpu16 (chunk->nstripes),
>> -			      grub_le_to_cpu16 (chunk->nsubstripes),
>> -			      grub_le_to_cpu64 (chunk->stripe_length),
>> -			      stripen, stripe->offset);
>> -		grub_dprintf ("btrfs", "reading paddr 0x%" PRIxGRUB_UINT64_T
>> -			      " for laddr 0x%" PRIxGRUB_UINT64_T "\n", paddr,
>> -			      addr);
>> -
>> -		dev = find_device (data, stripe->device_id);
>> -		if (!dev)
>> -		  {
>> -		    grub_dprintf ("btrfs",
>> -				  "couldn't find a necessary member device "
>> -				  "of multi-device filesystem\n");
>> -		    err = grub_errno;
>> -		    grub_errno = GRUB_ERR_NONE;
>> -		    continue;
>> -		  }
>> -
>> -		err = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS,
>> -				      paddr & (GRUB_DISK_SECTOR_SIZE - 1),
>> -				      csize, buf);
>> -		if (!err)
>> -		  break;
>> -		grub_errno = GRUB_ERR_NONE;
>> -	      }
>> -	    if (i != redundancy)
>> -	      break;
>> +	    grub_dprintf ("btrfs", "chunk 0x%" PRIxGRUB_UINT64_T
>> +			  "+0x%" PRIxGRUB_UINT64_T
>> +			  " (%d stripes (%d substripes) of %"
>> +			  PRIxGRUB_UINT64_T ") \n",
>> +			  grub_le_to_cpu64 (key->offset),
>> +			  grub_le_to_cpu64 (chunk->size),
>> +			  grub_le_to_cpu16 (chunk->nstripes),
>> +			  grub_le_to_cpu16 (chunk->nsubstripes),
>> +			  grub_le_to_cpu64 (chunk->stripe_length));
>> +	    grub_dprintf ("btrfs", "reading laddr 0x%" PRIxGRUB_UINT64_T "\n",
>> +			  addr);
>> +
>> +	    err = GRUB_ERR_NONE + 1;
>> +	    for (i = 0; i < redundancy && err != GRUB_ERR_NONE; i++)
>> +		 err = btrfs_read_from_chunk (data, chunk, stripen,
>> +					      stripe_offset,
>> +					      i,     /* redundancy */
>> +					      csize, buf);
> 
> It seems to me that this patch does more than it is told in commit message.
> At least it plays some games with debug messages? Could you split this
> patch into logical parts or if it is not possible could you say in the
> commit message why are you doing this and that?

I had some trouble in understanding the original code, because the mixing of
the "retry" logic and the "reading logic". So I refactored the "reading logic",
which helped also to implement the retry logic for the RAID5/6.

The log is the same, however the caller and the called doesn't have the
same information (the caller has access to the "key" variable, and the
called has access to the "stripe" variable). So I split the log depending
by the information available.

> 
> Daniel
> 


-- 
gpg @keyserver.linux.it: Goffredo Baroncelli <kreijackATinwind.it>
Key fingerprint BBF5 1610 0B64 DAC6 5F7D  17B2 0EDA 9B37 8B82 E0B5

Re: [PATCH 2/7] Add helper to check the btrfs header.

[Goffredo Baroncelli]

On 05/09/2018 03:52 PM, Daniel Kiper wrote:
> On Tue, Apr 24, 2018 at 09:13:11PM +0200, Goffredo Baroncelli wrote:
>> This helper was used in few places to help the debugging. As conservative
>> approach, in case of error it is only logged.
> 
> Could you explain in the commit message why we are so conservative here?
> 
>> Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
>> ---
>>  grub-core/fs/btrfs.c | 22 +++++++++++++++++++++-
>>  1 file changed, 21 insertions(+), 1 deletion(-)
>>
>> diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
>> index b0032ea46..01a1fc7a1 100644
>> --- a/grub-core/fs/btrfs.c
>> +++ b/grub-core/fs/btrfs.c
>> @@ -77,7 +77,8 @@ struct btrfs_header
>>  {
>>    grub_btrfs_checksum_t checksum;
>>    grub_btrfs_uuid_t uuid;
>> -  grub_uint8_t dummy[0x30];
>> +  grub_uint64_t bytenr;
>> +  grub_uint8_t dummy[0x28];
>>    grub_uint32_t nitems;
>>    grub_uint8_t level;
>>  } GRUB_PACKED;
>> @@ -286,6 +287,23 @@ free_iterator (struct grub_btrfs_leaf_descriptor *desc)
>>    grub_free (desc->data);
>>  }
>>
>> +static grub_err_t
>> +check_btrfs_header (struct grub_btrfs_data *data, struct btrfs_header *header,
>> +                    grub_disk_addr_t addr)
>> +{
>> +  if (grub_le_to_cpu64 (header->bytenr) != addr)
>> +    {
>> +      grub_dprintf ("btrfs", "btrfs_header.bytenr is not addr\n");
>> +      return grub_error (GRUB_ERR_BAD_FS, "header bytenr is not addr");
> 
> s/is not addr/is not equal node addr/?
> 
>> +    }
>> +  if (grub_memcmp (data->sblock.uuid, header->uuid, sizeof(grub_btrfs_uuid_t)))
>> +    {
>> +      grub_dprintf ("btrfs", "btrfs_header.uuid doesn't match\n");
>> +      return grub_error (GRUB_ERR_BAD_FS, "header uuid doesn't match");
> 
> s/doesn't match/doesn't match sblock uuid/?
> 
Updated

> Daniel
> 


-- 
gpg @keyserver.linux.it: Goffredo Baroncelli <kreijackATinwind.it>
Key fingerprint BBF5 1610 0B64 DAC6 5F7D  17B2 0EDA 9B37 8B82 E0B5

Re: [PATCH 4/7] Avoiding scanning for an already not found device.

[Goffredo Baroncelli]

On 05/09/2018 04:07 PM, Daniel Kiper wrote:
> On Tue, Apr 24, 2018 at 09:13:13PM +0200, Goffredo Baroncelli wrote:
>> If a device is missing, create the entry in data->devices_attached[] array.
> 
> What kind of entry? Invalid one? Please clarify this.
> 
>> This avoid un-necessary devices rescan.
>>
>> Signed-off-by: Goffredo Baroncelli <kreikack@inwind.it>
> 
> Otherwise LGTM.
> 
> Daniel
> 

Avoiding a rescan for a device which was already not founded.

If a device is not found, record this failure storing NULL in
data->devices_attached[]. This avoid un-necessary devices rescan, 
speeding the reading in case of a degraded array.

-- 
gpg @keyserver.linux.it: Goffredo Baroncelli <kreijackATinwind.it>
Key fingerprint BBF5 1610 0B64 DAC6 5F7D  17B2 0EDA 9B37 8B82 E0B5

Re: [PATCH 3/7] Move from the find_device the error logging logic to the callee.

[Goffredo Baroncelli]

On 05/09/2018 04:00 PM, Daniel Kiper wrote:
> On Tue, Apr 24, 2018 at 09:13:12PM +0200, Goffredo Baroncelli wrote:
>> Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
>> ---
>>  grub-core/fs/btrfs.c | 6 +++---
>>  1 file changed, 3 insertions(+), 3 deletions(-)
>>
>> diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
>> index 01a1fc7a1..745bb854e 100644
>> --- a/grub-core/fs/btrfs.c
>> +++ b/grub-core/fs/btrfs.c
>> @@ -602,9 +602,6 @@ find_device (struct grub_btrfs_data *data, grub_uint64_t id, int do_rescan)
>>      grub_device_iterate (find_device_iter, &ctx);
>>    if (!ctx.dev_found)
>>      {
>> -      grub_error (GRUB_ERR_BAD_FS,
>> -		  N_("couldn't find a necessary member device "
>> -		     "of multi-device filesystem"));
>>        return NULL;
>>      }
>>    data->n_devices_attached++;
>> @@ -862,6 +859,9 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>>  		dev = find_device (data, stripe->device_id, j);
>>  		if (!dev)
>>  		  {
>> +		    grub_dprintf ("btrfs",
>> +				  "couldn't find a necessary member device "
>> +				  "of multi-device filesystem\n");
> 
> May I ask you to explain in the commit message why are you doing that?
> 

I update the commit message to better explain the reason

   This is a preparatory patch. The callee knows better if this
   error is fatal, or it exists another available disk.

In the next patch find_device() will be called from more places

> Daniel
> 
-- 
gpg @keyserver.linux.it: Goffredo Baroncelli <kreijackATinwind.it>
Key fingerprint BBF5 1610 0B64 DAC6 5F7D  17B2 0EDA 9B37 8B82 E0B5

Re: [PATCH 1/7] Add support for reading a filesystem with a raid5 or raid6 profile.

[Goffredo Baroncelli]

On 05/09/2018 03:46 PM, Daniel Kiper wrote:
> On Tue, Apr 24, 2018 at 09:13:10PM +0200, Goffredo Baroncelli wrote:
>> Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
>> ---
>>  grub-core/fs/btrfs.c | 32 ++++++++++++++++++++++++++++++++
>>  1 file changed, 32 insertions(+)
>>
>> diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
>> index be195448d..b0032ea46 100644
>> --- a/grub-core/fs/btrfs.c
>> +++ b/grub-core/fs/btrfs.c
>> @@ -119,6 +119,8 @@ struct grub_btrfs_chunk_item
>>  #define GRUB_BTRFS_CHUNK_TYPE_RAID1         0x10
>>  #define GRUB_BTRFS_CHUNK_TYPE_DUPLICATED    0x20
>>  #define GRUB_BTRFS_CHUNK_TYPE_RAID10        0x40
>> +#define GRUB_BTRFS_CHUNK_TYPE_RAID5         0x80
>> +#define GRUB_BTRFS_CHUNK_TYPE_RAID6        0x100
> 
> #define GRUB_BTRFS_CHUNK_TYPE_RAID5         0x80
> #define GRUB_BTRFS_CHUNK_TYPE_RAID6         0x100
>  Please start in one column...     ---->    ^^^^^
OK
> 
>>    grub_uint8_t dummy2[0xc];
>>    grub_uint16_t nstripes;
>>    grub_uint16_t nsubstripes;
>> @@ -764,6 +766,36 @@ grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
>>  	      stripe_offset = low + chunk_stripe_length
>>  		* high;
>>  	      csize = chunk_stripe_length - low;
>> +	      break;
>> +	    }
>> +	  case GRUB_BTRFS_CHUNK_TYPE_RAID5:
>> +	  case GRUB_BTRFS_CHUNK_TYPE_RAID6:
>> +	    {
>> +	      grub_uint64_t nparities;
>> +	      grub_uint64_t stripe_nr, high;
>> +	      grub_uint64_t low;
> 
> Could you define all in one line?
Ok
> 
>> +	      redundancy = 1;	/* no redundancy for now */
>> +
>> +	      if (grub_le_to_cpu64 (chunk->type) & GRUB_BTRFS_CHUNK_TYPE_RAID5)
>> +		{
>> +		  grub_dprintf ("btrfs", "RAID5\n");
>> +		  nparities = 1;
>> +		}
>> +	      else
>> +		{
>> +		  grub_dprintf ("btrfs", "RAID6\n");
>> +		  nparities = 2;
>> +		}
>> +
>> +	      stripe_nr = grub_divmod64 (off, chunk_stripe_length, &low);
> 
> This is clear for me...
I want to put this comment before the line above
	      /*
	       * A raid 6 layout consists in several stripes spread
	       * on the disks, following a layout like the one below
	       *
	       *   Disk1  Disk2  Disk3  Ddisk4
	       *
	       *    A1     B1     P1     Q1
	       *    Q2     A2     B2     P2  
	       *    P3     Q3     A3     B3
	       *  [...]
	       *
	       *  Note that the placement of the parities depends by the row
	       *  In the code below:
	       *  stripe_nr -> is the stripe number not considering the parities
	       *               (A1=0, B1=1, A2 = 2, B2 = 3, ...)
	       *  high -> is the row number (0 for A1...Q1, 1 for Q2..P2, ...)
	       *  stripen -> is the column number (or number of disk)
	       *  off -> logical address to read (from teh beginning of the 
	       *         chunk space)
	       *  chunk_stripe_length -> size of a stripe (typically 64k)
	       *  nstripes -> number of disks
	       * 
	       */

> 
>> +	      high = grub_divmod64 (stripe_nr, nstripes - nparities, &stripen);
then I want to put here

	      /*
	       * until now stripen is evaluated without the parities (0 for A1,
	       * A2, A3... 1 for B1, B2...); now consider also the parities (0
	       * for A1, 1 for A2, 2 for A3....); the math is done "modulo"
	       * number of disk
	       */


>> +	      grub_divmod64 (high + stripen, nstripes, &stripen);
> 
> ... but not these two. Could you enlighten me?

It is more clear ? To understand this I spent a lot of time dumping the raw data on the disks; this because in wikipedia there is another stripe layout (A1, B1, B2 always on the first column; however btrfs does this different)
>> +	      stripe_offset = low + chunk_stripe_length * high;
> 
> ???
This is like the other RAID profile: high is the "row number" of the stripe matrix; so stripe_offset is the start of the data from the begin of the chunk (on the disk)
> 
>> +	      csize = chunk_stripe_length - low;
> 
> Chunk size to read?
This is like the other code. We can read until the end of the stripe. Then the disks will change.
> 
> Daniel
> 


-- 
gpg @keyserver.linux.it: Goffredo Baroncelli <kreijackATinwind.it>
Key fingerprint BBF5 1610 0B64 DAC6 5F7D  17B2 0EDA 9B37 8B82 E0B5

Re: [PATCH 7/7] Add raid6 recovery.

[Goffredo Baroncelli]

On 05/09/2018 06:58 PM, Daniel Kiper wrote:
> On Tue, Apr 24, 2018 at 09:13:16PM +0200, Goffredo Baroncelli wrote:
>> The code origins from "raid6_recovery.c". The code was changed because the
>> original one assumed that both the disk address and size are multiple of
>> GRUB_DISK_SECTOR_SIZE. This is not true for grub btrfs driver.
>>
>> The code was made more generalized using a function pointer for reading
>> the data from the memory or disk.
>>
>> Signed-off-by: Goffredo Baroncelli <kreijack@inwind.it>
>> ---
>>  grub-core/fs/btrfs.c | 211 +++++++++++++++++++++++++++++++++++++++++--
>>  1 file changed, 204 insertions(+), 7 deletions(-)
>>
>> diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
>> index 5c76a68f3..195313a31 100644
>> --- a/grub-core/fs/btrfs.c
>> +++ b/grub-core/fs/btrfs.c
>> @@ -30,6 +30,7 @@
>>  #include <grub/i18n.h>
>>  #include <grub/btrfs.h>
>>  #include <grub/crypto.h>
>> +#include <grub/diskfilter.h>
>>
>>  GRUB_MOD_LICENSE ("GPLv3+");
>>
>> @@ -695,19 +696,215 @@ rebuild_raid5 (struct raid56_buffer *buffers, grub_uint64_t nstripes,
>>                         csize);
>>  }
>>
>> +
>> +/* copied from raid6_recover */
>> +/* x**y.  */
>> +static grub_uint8_t powx[255 * 2];
>> +/* Such an s that x**s = y */
>> +static unsigned powx_inv[256];
>> +static const grub_uint8_t poly = 0x1d;
> 
> Could you define this as a constant?
In the original code from raid6_recover.c is the same. I prefer to not diverge too much.
> 
>> +static void
>> +grub_raid_block_mulx (unsigned mul, char *buf, grub_size_t size)
>> +{
>> +  grub_size_t i;
>> +  grub_uint8_t *p;
>> +
>> +  p = (grub_uint8_t *) buf;
>> +  for (i = 0; i < size; i++, p++)
>> +    if (*p)
>> +      *p = powx[mul + powx_inv[*p]];
>> +}
>> +
>> +static void
>> +grub_raid6_init_table (void)
>> +{
>> +  unsigned i;
>> +
>> +  grub_uint8_t cur = 1;
>> +  for (i = 0; i < 255; i++)
>> +    {
>> +      powx[i] = cur;
>> +      powx[i + 255] = cur;
>> +      powx_inv[cur] = i;
>> +      if (cur & 0x80)
>> +	cur = (cur << 1) ^ poly;
>> +      else
>> +	cur <<= 1;
>> +    }
>> +}
> 
> Could not we do this as a static? It is initialized only once.
Ditto

> 
>> +static unsigned
>> +mod_255 (unsigned x)
>> +{
>> +  while (x > 0xff)
>> +    x = (x >> 8) + (x & 0xff);
>> +  if (x == 0xff)
>> +    return 0;
>> +  return x;
>> +}
>> +
>> +typedef grub_err_t (* raid_recover_read_t)(void *data, int disk_nr,
>> +					   grub_uint64_t addr, void *dest,
>> +					   grub_size_t size);
>> +#if 0
>> +/*
>> + * code example to be used in raid6_recover.
>> + */
>> +static grub_err_t
>> +raid_recover_read_diskfilter_array (void *data, int disk_nr,
>> +				    grub_uint64_t sector,
>> +				    void *buf, grub_size_t size)
>> +{
>> +    struct grub_diskfilter_segment *array = data;
>> +    return grub_diskfilter_read_node (&array->nodes[disk_nr],
>> +				      (grub_disk_addr_t)sector,
>> +				      size >> GRUB_DISK_SECTOR_BITS, buf);
>> +}
>> +#endif
> 
> Please drop this.
See below

> 
>> +
>> +static grub_err_t
>> +raid_recover_read_raid56_buffer (void *data, int disk_nr, grub_uint64_t addr,
>> +                                 void *dest, grub_size_t size)
>> +{
>> +    struct raid56_buffer *buffers = data;
>> +
>> +    (void)addr;
> 
> "grub_uint64_t addr __attribute__ ((unused))" in prototype definition?
It is ugly ! :-)
> 
>> +    grub_memcpy(dest, buffers[disk_nr].buf, size);
>> +
>> +    grub_errno = buffers[disk_nr].ok ? GRUB_ERR_NONE : GRUB_ERR_READ_ERROR;
>> +    return grub_errno;
>> +}
>> +
>> +static grub_err_t
>> +grub_raid6_recover (void *data, grub_uint64_t nstripes, int disknr, int p,
>> +                    char *buf, grub_uint64_t sector, grub_size_t size,
>> +		    raid_recover_read_t read_func, int layout)
>> +{
>> +  int i, q, pos;
>> +  int bad1 = -1, bad2 = -1;
>> +  char *pbuf = 0, *qbuf = 0;
>> +  static int table_initializated = 0;
>> +
>> +  if (!table_initializated)
>> +    {
>> +      grub_raid6_init_table();
>> +      table_initializated = 1;
>> +    }
>> +
>> +  pbuf = grub_zalloc (size);
>> +  if (!pbuf)
>> +    goto quit;
>> +
>> +  qbuf = grub_zalloc (size);
>> +  if (!qbuf)
>> +    goto quit;
>> +
>> +  q = p + 1;
>> +  if (q == (int) nstripes)
>> +    q = 0;
>> +
>> +  pos = q + 1;
>> +  if (pos == (int) nstripes)
>> +    pos = 0;
>> +
>> +  for (i = 0; i < (int) nstripes - 2; i++)
>> +    {
>> +      int c;
>> +      if (layout & GRUB_RAID_LAYOUT_MUL_FROM_POS)
>> +	c = pos;
>> +      else
>> +	c = i;
>> +      if (pos == disknr)
>> +        bad1 = c;
>> +      else
>> +        {
>> +	  if (!read_func(data, pos, sector, buf, size))
>> +            {
>> +              grub_crypto_xor (pbuf, pbuf, buf, size);
>> +              grub_raid_block_mulx (c, buf, size);
>> +              grub_crypto_xor (qbuf, qbuf, buf, size);
>> +            }
>> +          else
>> +            {
>> +              /* Too many bad devices */
>> +              if (bad2 >= 0)
>> +                goto quit;
>> +
>> +              bad2 = c;
>> +              grub_errno = GRUB_ERR_NONE;
>> +            }
>> +        }
>> +
>> +      pos++;
>> +      if (pos == (int) nstripes)
>> +        pos = 0;
>> +    }
>> +
>> +  /* Invalid disknr or p */
>> +  if (bad1 < 0)
>> +    goto quit;
>> +
>> +  if (bad2 < 0)
>> +    {
>> +      /* One bad device */
>> +      if (!read_func(data, p, sector, buf, size))
>> +        {
>> +          grub_crypto_xor (buf, buf, pbuf, size);
>> +          goto quit;
>> +        }
>> +
>> +      grub_errno = GRUB_ERR_NONE;
>> +      if (read_func(data, q, sector, buf, size))
>> +        goto quit;
>> +
>> +      grub_crypto_xor (buf, buf, qbuf, size);
>> +      grub_raid_block_mulx (255 - bad1, buf,
>> +                           size);
>> +    }
>> +  else
>> +    {
>> +      /* Two bad devices */
>> +      unsigned c;
>> +
>> +      if (read_func(data, p, sector, buf, size))
>> +        goto quit;
>> +
>> +      grub_crypto_xor (pbuf, pbuf, buf, size);
>> +
>> +      if (read_func(data, q, sector, buf, size))
>> +        goto quit;
>> +
>> +      grub_crypto_xor (qbuf, qbuf, buf, size);
>> +
>> +      c = mod_255((255 ^ bad1)
>> +		  + (255 ^ powx_inv[(powx[bad2 + (bad1 ^ 255)] ^ 1)]));
>> +      grub_raid_block_mulx (c, qbuf, size);
>> +
>> +      c = mod_255((unsigned) bad2 + c);
>> +      grub_raid_block_mulx (c, pbuf, size);
>> +
>> +      grub_crypto_xor (pbuf, pbuf, qbuf, size);
>> +      grub_memcpy (buf, pbuf, size);
>> +    }
>> +
>> +quit:
> 
> One space before the label please?
ok
> 
>> +  grub_free (pbuf);
>> +  grub_free (qbuf);
>> +
>> +  return grub_errno;
>> +}
>> +
>> +/* end copy */
>>  static void
>>  rebuild_raid6 (struct raid56_buffer *buffers, grub_uint64_t nstripes,
>>                 grub_uint64_t csize, grub_uint64_t parities_pos, void *dest,
>>                 grub_uint64_t stripen)
>>
>>  {
>> -  (void)buffers;
>> -  (void)nstripes;
>> -  (void)csize;
>> -  (void)parities_pos;
>> -  (void)dest;
>> -  (void)stripen;
>> -  grub_dprintf ("btrfs", "called rebuild_raid6(), NOT IMPLEMENTED\n");
>> +  grub_raid6_recover (buffers, nstripes, stripen, parities_pos,
>> +		      dest, 0, csize,
>> +		      raid_recover_read_raid56_buffer, 0);
> 
> grub_raid6_recover() should be called directly from right place.

replacing raid_recover_read_raid56_buffer() with raid_recover_read_diskfilter_array(), could allow to use grub_raid6_recover() even in the grub-core/disk/raid6_recover.c. This is the reason of "double call".


> 
> Daniel
> 


-- 
gpg @keyserver.linux.it: Goffredo Baroncelli <kreijackATinwind.it>
Key fingerprint BBF5 1610 0B64 DAC6 5F7D  17B2 0EDA 9B37 8B82 E0B5

Re: [PATCH V2] Add support for BTRFS raid5/6 to GRUB

[Daniel Kiper]

On Wed, May 09, 2018 at 09:36:55PM +0200, Goffredo Baroncelli wrote:
> On 05/09/2018 07:00 PM, Daniel Kiper wrote:
> > On Tue, Apr 24, 2018 at 09:13:09PM +0200, Goffredo Baroncelli wrote:
> >>
> >> Hi All,
> >>
> >> the aim of this patches set is to provide support for a BTRFS raid5/6
> >>  filesystem in GRUB.
> >>
> >> The first patch, implements the basic support for raid5/6. I.e this works when
> >>  all the disks
> >> are present.
> >>
> >> The next 4 patches, are preparatory ones.
> >>
> >> The last two implements the support for raid5/6 recovery. It allow to read
> >> from the filesystem even when 1 or 2 (for raid 6) disk(s) are missing.
> >>
> >> The last one is the more controversial. The code for the raid6 recovery is
> >> copied from the GRUB file reaid6_recovery.c . I preferred this approach,
> >> because the original code assumes that the read is GRUB_DISK_SECTOR_SIZE
> >> bytes based (512 bytes). Instead the GRUB BTRFS implementation need to
> >> read the disk with a granularity of the byte.
> >> I tried to update the code (and the function which the code calls), but
> >> the change was quite invasive. So for now I preferred to duplicating the
> >> code, to get some feedback.
> >>
> >> I tested the code in grub-emu, and it works (for me) both with all the disks,
> >>  and with some disks missing. I checked the sh1sums calculated from grub and
> >> from linux and these matched.
> >>
> >> Comments are welcome.
> >
> > Mostly nitpicks. However, if we can reuse reaid6_recovery.c somehow that
> > will be great. Even if this require some more patches.
>
> I liked the idea too. I am not sure to be able to tests all the cases.
> Do you know if it exists a list of tests about raid6_recovery and dm ?

Sadly I know nothing about that.

> Anyway, I update the patch. Tomorrow I will test these and then I issue the patch set.

I agree mostly with your replies. Please respin the patches
and I will take a look at v2.

Thank you for doing the work.

Daniel