>From 8d6dd4288064e9b880eccb1a6b1b7a6b03f2ba96 Mon Sep 17 00:00:00 2001
From: "Richard W.M. Jones" <address@hidden>
Date: Sat, 19 Jan 2019 10:30:28 +0000
Subject: [PATCH] partitioning: Support MBR logical partitions.

XXX NEEDS TESTS
---
 .../nbdkit-partitioning-plugin.pod            |  25 +---
 plugins/partitioning/virtual-disk.h           |  15 +-
 plugins/partitioning/partition-gpt.c          |   2 +-
 plugins/partitioning/partition-mbr.c          | 134 +++++++++++++++---
 plugins/partitioning/partitioning.c           |  31 ++--
 plugins/partitioning/virtual-disk.c           |  42 +++++-
 6 files changed, 184 insertions(+), 65 deletions(-)

diff --git a/plugins/partitioning/nbdkit-partitioning-plugin.pod b/plugins/partitioning/nbdkit-partitioning-plugin.pod
index 57a1133..edb0776 100644
--- a/plugins/partitioning/nbdkit-partitioning-plugin.pod
+++ b/plugins/partitioning/nbdkit-partitioning-plugin.pod
@@ -27,23 +27,12 @@ access use the I<-r> flag.
 
 =head2 Partition table type
 
-You can choose either an MBR partition table, which is limited to 4
-partitions, or a GPT partition table.  In theory GPT supports an
-unlimited number of partitions.
-
-The rule for selecting the partition table type is:
+Using the C<partition-type> parameter you can choose either an MBR or
+a GPT partition table.  If this parameter is I<not> present then:
 
 =over 4
 
-=item C<partition-type=mbr> parameter on the command line
-
-⇒ MBR is selected
-
-=item C<partition-type=gpt> parameter on the command line
-
-⇒ GPT is selected
-
-=item else, number of files E<gt> 4
+=item number of files E<gt> 4
 
 ⇒ GPT
 
@@ -131,7 +120,9 @@ C<./> (absolute paths do not need modification).
 =item B<partition-type=mbr>
 
 Add an MBR (DOS-style) partition table.  The MBR format is maximally
-compatible with all clients, but only supports up to 4 partitions.
+compatible with all clients.  If there are E<gt> 4 partitions then an
+extended partition is created
+(L<https://en.wikipedia.org/wiki/Extended_boot_record>).
 
 =item B<partition-type=gpt>
 
@@ -163,10 +154,6 @@ a Linux filesystem.
 
 =head1 LIMITS
 
-This plugin only supports B<primary> MBR partitions, hence the limit
-of 4 partitions with MBR.  This might be increased in future if we
-implement support for logical/extended MBR partitions.
-
 Although this plugin can create GPT partition tables containing more
 than 128 GPT partitions (in fact, unlimited numbers of partitions),
 some clients will not be able to handle this.
diff --git a/plugins/partitioning/virtual-disk.h b/plugins/partitioning/virtual-disk.h
index 3860f46..f59df70 100644
--- a/plugins/partitioning/virtual-disk.h
+++ b/plugins/partitioning/virtual-disk.h
@@ -34,6 +34,7 @@
 #ifndef NBDKIT_VIRTUAL_DISK_H
 #define NBDKIT_VIRTUAL_DISK_H
 
+#include <stdbool.h>
 #include <sys/types.h>
 #include <sys/stat.h>
 
@@ -103,7 +104,7 @@ extern struct file *files;
 extern size_t nr_files;
 
 extern struct regions regions;
-extern unsigned char *primary, *secondary;
+extern unsigned char *primary, *secondary, **ebr;
 
 /* Main entry point called after files array has been populated. */
 extern int create_virtual_disk_layout (void);
@@ -114,16 +115,16 @@ extern int create_virtual_disk_layout (void);
 extern int parse_guid (const char *str, char *out)
   __attribute__((__nonnull__ (1, 2)));
 
-/* Internal functions for creating MBR and GPT layouts.  These are
- * published here because the GPT code calls into the MBR code, but
- * are not meant to be called from the main plugin.
+/* Internal function for creating a single MBR PTE.  The GPT code
+ * calls this for creating the protective MBR.
  */
-extern void create_mbr_partition_table (unsigned char *out)
-  __attribute__((__nonnull__ (1)));
 extern void create_mbr_partition_table_entry (const struct region *,
-                                              int bootable, int partition_id,
+                                              bool bootable, int partition_id,
                                               unsigned char *)
   __attribute__((__nonnull__ (1, 4)));
+
+/* Create MBR or GPT layout. */
+extern void create_mbr_layout (void);
 extern void create_gpt_layout (void);
 
 #endif /* NBDKIT_VIRTUAL_DISK_H */
diff --git a/plugins/partitioning/partition-gpt.c b/plugins/partitioning/partition-gpt.c
index 5fb7602..be52e72 100644
--- a/plugins/partitioning/partition-gpt.c
+++ b/plugins/partitioning/partition-gpt.c
@@ -210,7 +210,7 @@ create_gpt_protective_mbr (unsigned char *out)
   region.end = end;
   region.len = region.end - region.start + 1;
 
-  create_mbr_partition_table_entry (&region, 0, 0xee, &out[0x1be]);
+  create_mbr_partition_table_entry (&region, false, 0xee, &out[0x1be]);
 
   /* Boot signature. */
   out[0x1fe] = 0x55;
diff --git a/plugins/partitioning/partition-mbr.c b/plugins/partitioning/partition-mbr.c
index d3a0d78..6f76432 100644
--- a/plugins/partitioning/partition-mbr.c
+++ b/plugins/partitioning/partition-mbr.c
@@ -49,27 +49,125 @@
 #include "regions.h"
 #include "virtual-disk.h"
 
-/* Create the partition table. */
+static const struct region *find_file_region (size_t i, size_t *j);
+static const struct region *find_ebr_region (size_t i, size_t *j);
+
+/* Create the MBR and optionally EBRs. */
 void
-create_mbr_partition_table (unsigned char *out)
+create_mbr_layout (void)
 {
-  size_t i, j;
-
-  for (j = 0; j < nr_regions (&regions); ++j) {
-    const struct region *region = get_region (&regions, j);
-
-    if (region->type == region_file) {
-      i = region->u.i;
-      assert (i < 4);
-      create_mbr_partition_table_entry (region, i == 0,
-                                        files[i].mbr_id,
-                                        &out[0x1be + 16*i]);
-    }
-  }
+  size_t i, j = 0;
 
   /* Boot signature. */
-  out[0x1fe] = 0x55;
-  out[0x1ff] = 0xaa;
+  primary[0x1fe] = 0x55;
+  primary[0x1ff] = 0xaa;
+
+  if (nr_files <= 4) {
+    /* Basic MBR with no extended partition. */
+    for (i = 0; i < nr_files; ++i) {
+      const struct region *region = find_file_region (i, &j);
+
+      create_mbr_partition_table_entry (region, i == 0, files[i].mbr_id,
+                                        &primary[0x1be + 16*i]);
+    }
+  }
+  else {
+    struct region region;
+    const struct region *rptr, *eptr0, *eptr;
+
+    /* The first three primary partitions correspond to the first
+     * three files.
+     */
+    for (i = 0; i < 3; ++i) {
+      rptr = find_file_region (i, &j);
+      create_mbr_partition_table_entry (rptr, i == 0, files[i].mbr_id,
+                                        &primary[0x1be + 16*i]);
+    }
+
+    /* The fourth partition is an extended PTE and does not correspond
+     * to any file.  This partition starts with the first EBR, so find
+     * it.  The partition extends to the end of the disk.
+     */
+    eptr0 = find_ebr_region (3, &j);
+    region.start = eptr0->start;
+    region.end = virtual_size (&regions) - 1; /* to end of disk */
+    region.len = region.end - region.start + 1;
+    create_mbr_partition_table_entry (&region, false, 0xf, &primary[0x1ee]);
+
+    /* The remaining files are mapped to logical partitions living in
+     * the fourth extended partition.
+     */
+    for (i = 3; i < nr_files; ++i) {
+      if (i == 3)
+        eptr = eptr0;
+      else
+        eptr = find_ebr_region (i, &j);
+      rptr = find_file_region (i, &j);
+
+      /* Signature. */
+      ebr[i-3][0x1fe] = 0x55;
+      ebr[i-3][0x1ff] = 0xaa;
+
+      /* First entry in EBR contains:
+       * offset from EBR sector to the first sector of the logical partition
+       * total count of sectors in the logical partition
+       */
+      region.start = rptr->start - eptr->start;
+      region.len = rptr->len;
+      create_mbr_partition_table_entry (&region, false, files[i].mbr_id,
+                                        &ebr[i-3][0x1be]);
+
+      if (i < nr_files-1) {
+        size_t j2 = j;
+        const struct region *enext = find_ebr_region (i+1, &j2);
+        const struct region *rnext = find_file_region (i+1, &j2);
+
+        /* Second entry in the EBR contains:
+         * address of next EBR relative to extended partition
+         * total count of sectors in the next logical partition including
+         * next EBR
+         */
+        region.start = enext->start - eptr0->start;
+        region.len = rnext->end - enext->start + 1;
+        create_mbr_partition_table_entry (&region, false, files[i+1].mbr_id,
+                                          &ebr[i-3][0x1ce]);
+      }
+    }
+  }
+}
+
+/* Find the region corresponding to file[i].
+ * j is a scratch register ensuring we only do a linear scan.
+ */
+static const struct region *
+find_file_region (size_t i, size_t *j)
+{
+  const struct region *region;
+
+  for (; *j < nr_regions (&regions); ++(*j)) {
+    region = get_region (&regions, *j);
+    if (region->type == region_file && region->u.i == i)
+      return region;
+  }
+  abort ();
+}
+
+/* Find the region corresponding to EBR of file[i] (i >= 3).
+ * j is a scratch register ensuring we only do a linear scan.
+ */
+static const struct region *
+find_ebr_region (size_t i, size_t *j)
+{
+  const struct region *region;
+
+  assert (i >= 3);
+
+  for (; *j < nr_regions (&regions); ++(*j)) {
+    region = get_region (&regions, *j);
+    if (region->type == region_data && region->u.data == ebr[i-3])
+      return region;
+  }
+  abort ();
 }
 
 static void
@@ -84,7 +182,7 @@ chs_too_large (unsigned char *out)
 
 void
 create_mbr_partition_table_entry (const struct region *region,
-                                  int bootable, int partition_id,
+                                  bool bootable, int partition_id,
                                   unsigned char *out)
 {
   uint64_t start_sector, nr_sectors;
diff --git a/plugins/partitioning/partitioning.c b/plugins/partitioning/partitioning.c
index 205c059..689cb24 100644
--- a/plugins/partitioning/partitioning.c
+++ b/plugins/partitioning/partitioning.c
@@ -35,6 +35,7 @@
 
 #include <stdio.h>
 #include <stdlib.h>
+#include <stdbool.h>
 #include <stdint.h>
 #include <inttypes.h>
 #include <string.h>
@@ -81,8 +82,11 @@ size_t nr_files = 0;
 /* Virtual disk layout. */
 struct regions regions;
 
-/* Primary and secondary partition tables (secondary is only used for GPT). */
-unsigned char *primary = NULL, *secondary = NULL;
+/* Primary and secondary partition tables and extended boot records.
+ * Secondary PT is only used for GPT.  EBR array of sectors is only
+ * used for MBR with > 4 partitions and has length equal to nr_files-3.
+ */
+unsigned char *primary = NULL, *secondary = NULL, **ebr = NULL;
 
 /* Used to generate random unique partition GUIDs for GPT. */
 static struct random_state random_state;
@@ -105,12 +109,17 @@ partitioning_unload (void)
   free (files);
 
   /* We don't need to free regions.regions[].u.data because it points
-   * to either primary or secondary which we free here.
+   * to primary, secondary or ebr which we free here.
    */
   free_regions (&regions);
 
   free (primary);
   free (secondary);
+  if (ebr) {
+    for (i = 0; i < nr_files-3; ++i)
+      free (ebr[i]);
+    free (ebr);
+  }
 }
 
 static int
@@ -225,7 +234,7 @@ partitioning_config_complete (void)
 {
   size_t i;
   uint64_t total_size;
-  int needs_gpt;
+  bool needs_gpt;
 
   /* Not enough / too many files? */
   if (nr_files == 0) {
@@ -236,17 +245,11 @@ partitioning_config_complete (void)
   total_size = 0;
   for (i = 0; i < nr_files; ++i)
     total_size += files[i].statbuf.st_size;
-
-  if (nr_files > 4)
-    needs_gpt = 1;
-  else if (total_size > MAX_MBR_DISK_SIZE)
-    needs_gpt = 1;
-  else
-    needs_gpt = 0;
+  needs_gpt = total_size > MAX_MBR_DISK_SIZE;
 
   /* Choose default parttype if not set. */
   if (parttype == PARTTYPE_UNSET) {
-    if (needs_gpt) {
+    if (needs_gpt || nr_files > 4) {
       parttype = PARTTYPE_GPT;
       nbdkit_debug ("picking partition type GPT");
     }
@@ -256,8 +259,8 @@ partitioning_config_complete (void)
     }
   }
   else if (parttype == PARTTYPE_MBR && needs_gpt) {
-    nbdkit_error ("MBR partition table type supports a maximum of 4 partitions "
-                  "and a maximum virtual disk size of about 2 TB, "
+    nbdkit_error ("MBR partition table type supports "
+                  "a maximum virtual disk size of about 2 TB, "
                   "but you requested %zu partition(s) "
                   "and a total size of %" PRIu64 " bytes (> %" PRIu64 ").  "
                   "Try using: partition-type=gpt",
diff --git a/plugins/partitioning/virtual-disk.c b/plugins/partitioning/virtual-disk.c
index e2d72bc..4fe186e 100644
--- a/plugins/partitioning/virtual-disk.c
+++ b/plugins/partitioning/virtual-disk.c
@@ -69,6 +69,25 @@ create_virtual_disk_layout (void)
       nbdkit_error ("malloc: %m");
       return -1;
     }
+
+    if (nr_files > 4) {
+      /* The first 3 primary partitions will be real partitions, the
+       * 4th will be an extended partition, and so we need to store
+       * EBRs for nr_files-3 logical partitions.
+       */
+      ebr = malloc (sizeof (unsigned char *) * (nr_files-3));
+      if (ebr == NULL) {
+        nbdkit_error ("malloc: %m");
+        return -1;
+      }
+      for (i = 0; i < nr_files-3; ++i) {
+        ebr[i] = calloc (1, SECTOR_SIZE);
+        if (ebr[i] == NULL) {
+          nbdkit_error ("malloc: %m");
+          return -1;
+        }
+      }
+    }
   }
   else /* PARTTYPE_GPT */ {
     /* Protective MBR + PT header + PTA = 2 + GPT_PTA_LBAs */
@@ -117,6 +136,20 @@ create_virtual_disk_layout (void)
      */
     assert (IS_ALIGNED (offset, SECTOR_SIZE));
 
+    /* Logical partitions are preceeded by an EBR. */
+    if (parttype == PARTTYPE_MBR && nr_files > 4 && i >= 3) {
+      region.start = offset;
+      region.len = SECTOR_SIZE;
+      region.end = region.start + region.len - 1;
+      region.type = region_data;
+      region.u.data = ebr[i-3];
+      region.description = "EBR";
+      if (append_region (&regions, region) == -1)
+        return -1;
+
+      offset = virtual_size (&regions);
+    }
+
     /* Make sure each partition is aligned for best performance. */
     if (!IS_ALIGNED (offset, files[i].alignment)) {
       region.start = offset;
@@ -207,13 +240,10 @@ create_partition_table (void)
   if (parttype == PARTTYPE_GPT)
     assert (secondary != NULL);
 
-  if (parttype == PARTTYPE_MBR) {
-    assert (nr_files <= 4);
-    create_mbr_partition_table (primary);
-  }
-  else /* parttype == PARTTYPE_GPT */ {
+  if (parttype == PARTTYPE_MBR)
+    create_mbr_layout ();
+  else /* parttype == PARTTYPE_GPT */
     create_gpt_layout ();
-  }
 
   return 0;
 }
-- 
2.20.1