Switch to 64-bit sector pointers everywhere

Switch to consistent use of 64-bit sector pointers; this should enable
booting even for individual *partitions* larger than 2 TB.  In order
to not slow down the boot too much, switch the initial load from an
enumeration to an extent map.  This means the table gets larger (since
we have to assume the worst case), but it simplifies the Sector 1 code
(since we can push all the hard stuff into the installer), and will
speed up booting in the general case.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>

5 files changed, 266 insertions, 63 deletions

diff --git a/libinstaller/syslinux.h b/libinstaller/syslinux.h
index 311b9f2e..bf2b716a 100644
--- a/libinstaller/syslinux.h
+++ b/libinstaller/syslinux.h
@@ -46,7 +46,8 @@ void syslinux_make_bootsect(void *);
 const char *syslinux_check_bootsect(const void *bs);
 
 /* This patches the boot sector and ldlinux.sys based on a sector map */
-int syslinux_patch(const uint32_t * sectors, int nsectors,
+typedef uint64_t sector_t;
+int syslinux_patch(const sector_t *sectors, int nsectors,
 		   int stupid, int raid_mode, const char *subdir);
 
 #endif
diff --git a/libinstaller/syslxcom.c b/libinstaller/syslxcom.c
index 825419b4..013b69af 100644
--- a/libinstaller/syslxcom.c
+++ b/libinstaller/syslxcom.c
@@ -33,6 +33,8 @@
 #include <sys/vfs.h>
 #include <linux/fs.h>		/* FIGETBSZ, FIBMAP */
 #include <linux/msdos_fs.h>	/* FAT_IOCTL_SET_ATTRIBUTES */
+#undef SECTOR_SIZE		/* Defined in msdos_fs.h for no good reason */
+#include <linux/fiemap.h>	/* FIEMAP definitions */
 #include "syslxcom.h"
 
 const char *program;
@@ -180,13 +182,86 @@ void set_attributes(int fd)
     }
 }
 
-/*
- * Produce file map
- */
-int sectmap(int fd, uint32_t * sectors, int nsectors)
+/* New FIEMAP based mapping */
+static int sectmap_fie(int fd, sector_t *sectors, int nsectors)
 {
-    unsigned int blksize, blk, nblk;
+    struct fiemap *fm;
+    struct fiemap_extent *fe;
+    unsigned int i, nsec;
+    sector_t sec, *secp, *esec;
+    struct stat st;
+    uint64_t maplen;
+
+    if (fstat(fd, &st))
+	return -1;
+
+    fm = alloca(sizeof(struct fiemap)
+		+ nsectors * sizeof(struct fiemap_extent));
+
+    memset(fm, 0, sizeof *fm);
+
+    maplen = (uint64_t)nsectors << SECTOR_SHIFT;
+    if (maplen > (uint64_t)st.st_size)
+	maplen = st.st_size;
+
+    fm->fm_start        = 0;
+    fm->fm_length       = maplen;
+    fm->fm_flags        = FIEMAP_FLAG_SYNC;
+    fm->fm_extent_count = nsectors;
+
+    if (ioctl(fd, FS_IOC_FIEMAP, &fm))
+	return -1;
+
+    memset(sectors, 0, nsectors * sizeof *sectors);
+    esec = sectors + nsectors;
+
+    fe = fm->fm_extents;
+
+    if (fm->fm_mapped_extents < 1 ||
+	!(fe[fm->fm_mapped_extents-1].fe_flags & FIEMAP_EXTENT_LAST))
+	return -1;
+
+    for (i = 0; i < fm->fm_mapped_extents; i++) {
+	if (fe->fe_flags & FIEMAP_EXTENT_LAST) {
+	    /* If this is the *final* extent, pad the length */
+	    fe->fe_length = (fe->fe_length + SECTOR_SIZE - 1)
+		& (SECTOR_SIZE - 1);
+	}
+
+	if ((fe->fe_logical | fe->fe_physical| fe->fe_length) &
+	    (SECTOR_SIZE - 1))
+	    return -1;
+
+	if (fe->fe_flags & (FIEMAP_EXTENT_UNKNOWN|
+			    FIEMAP_EXTENT_DELALLOC|
+			    FIEMAP_EXTENT_ENCODED|
+			    FIEMAP_EXTENT_DATA_ENCRYPTED|
+			    FIEMAP_EXTENT_UNWRITTEN))
+	    return -1;
+
+	secp = sectors + (fe->fe_logical >> SECTOR_SHIFT);
+	sec  = fe->fe_physical >> SECTOR_SHIFT;
+	nsec = fe->fe_length >> SECTOR_SHIFT;
+
+	while (nsec--) {
+	    if (secp >= esec)
+		break;
+	    *secp++ = sec++;
+	}
+
+	fe++;
+    }
+
+    return 0;
+}
+
+/* Legacy FIBMAP based mapping */
+static int sectmap_fib(int fd, sector_t *sectors, int nsectors)
+{
+    unsigned int blk, nblk;
     unsigned int i;
+    unsigned int blksize;
+    sector_t sec;
 
     /* Get block size */
     if (ioctl(fd, FIGETBSZ, &blksize))
@@ -197,22 +272,28 @@ int sectmap(int fd, uint32_t * sectors, int nsectors)
 
     nblk = 0;
     while (nsectors) {
-
 	blk = nblk++;
-	dprintf("querying block %u\n", blk);
 	if (ioctl(fd, FIBMAP, &blk))
 	    return -1;
 
-	blk *= blksize;
+	sec = (sector_t)blk * blksize;
 	for (i = 0; i < blksize; i++) {
-	    if (!nsectors)
-		return 0;
-
-	    dprintf("Sector: %10u\n", blk);
-	    *sectors++ = blk++;
-	    nsectors--;
+	    *sectors++ = sec++;
+	    if (! --nsectors)
+		break;
 	}
     }
 
     return 0;
 }
+
+/*
+ * Produce file map
+ */
+int sectmap(int fd, sector_t *sectors, int nsectors)
+{
+    if (!sectmap_fie(fd, sectors, nsectors))
+	return 0;
+
+    return sectmap_fib(fd, sectors, nsectors);
+}
diff --git a/libinstaller/syslxcom.h b/libinstaller/syslxcom.h
index ba4f1d00..39ca09d3 100644
--- a/libinstaller/syslxcom.h
+++ b/libinstaller/syslxcom.h
@@ -1,6 +1,8 @@
 #ifndef _H_SYSLXCOM_
 #define _H_SYSLXCOM_
 
+#include "syslinux.h"
+
 /* Global fs_type for handling fat, ext2/3/4 and btrfs */
 enum filesystem {
     NONE,
@@ -15,6 +17,6 @@ ssize_t xpread(int fd, void *buf, size_t count, off_t offset);
 ssize_t xpwrite(int fd, const void *buf, size_t count, off_t offset);
 void clear_attributes(int fd);
 void set_attributes(int fd);
-int sectmap(int fd, uint32_t * sectors, int nsectors);
+int sectmap(int fd, sector_t *sectors, int nsectors);
 
 #endif
diff --git a/libinstaller/syslxint.h b/libinstaller/syslxint.h
index bc818df6..53aa05dc 100644
--- a/libinstaller/syslxint.h
+++ b/libinstaller/syslxint.h
@@ -15,6 +15,12 @@
 
 #include "syslinux.h"
 
+#if defined(__386__) || defined(__i386__) || defined(__x86_64__)
+# define X86_MEM 1		/* Littleendian and unaligned safe */
+#else
+# define X86_MEM 0
+#endif
+
 /*
  * Access functions for littleendian numbers, possibly misaligned.
  */
@@ -25,37 +31,47 @@ static inline uint8_t get_8(const uint8_t * p)
 
 static inline uint16_t get_16(const uint16_t * p)
 {
-#if defined(__i386__) || defined(__x86_64__)
+#if X86_MEM
     /* Littleendian and unaligned-capable */
     return *p;
 #else
     const uint8_t *pp = (const uint8_t *)p;
-    return (uint16_t) pp[0] + ((uint16_t) pp[1] << 8);
+    return pp[0] + ((uint16_t)pp[1] << 8);
 #endif
 }
 
 static inline uint32_t get_32(const uint32_t * p)
 {
-#if defined(__i386__) || defined(__x86_64__)
+#if X86_MEM
     /* Littleendian and unaligned-capable */
     return *p;
 #else
-    const uint8_t *pp = (const uint8_t *)p;
-    return (uint32_t) pp[0] + ((uint32_t) pp[1] << 8) +
-	((uint32_t) pp[2] << 16) + ((uint32_t) pp[3] << 24);
+    const uint16_t *pp = (const uint16_t *)p;
+    return get_16(pp[0]) + (uint32_t)get_16(pp[1]);
+#endif
+}
+
+static inline uint64_t get_64(const uint64_t * p)
+{
+#if X86_MEM
+    /* Littleendian and unaligned-capable */
+    return *p;
+#else
+    const uint32_t *pp = (const uint32_t *)p;
+    return get_32(pp[0]) + (uint64_t)get_32(pp[1]);
 #endif
 }
 
-static inline void set_8(uint8_t * p, uint8_t v)
+static inline void set_8(uint8_t *p, uint8_t v)
 {
     *p = v;
 }
 
-static inline void set_16(uint16_t * p, uint16_t v)
+static inline void set_16(uint16_t *p, uint16_t v)
 {
-#if defined(__i386__) || defined(__x86_64__)
+#if X86_MEM
     /* Littleendian and unaligned-capable */
-    *(uint16_t *) p = v;
+    *p = v;
 #else
     uint8_t *pp = (uint8_t *) p;
     pp[0] = (v & 0xff);
@@ -63,11 +79,11 @@ static inline void set_16(uint16_t * p, uint16_t v)
 #endif
 }
 
-static inline void set_32(uint32_t * p, uint32_t v)
+static inline void set_32(uint32_t *p, uint32_t v)
 {
-#if defined(__i386__) || defined(__x86_64__)
+#if X86_MEM
     /* Littleendian and unaligned-capable */
-    *(uint32_t *) p = v;
+    *p = v;
 #else
     uint8_t *pp = (uint8_t *) p;
     pp[0] = (v & 0xff);
@@ -77,6 +93,18 @@ static inline void set_32(uint32_t * p, uint32_t v)
 #endif
 }
 
+static inline void set_64(uint64_t *p, uint64_t v)
+{
+#if X86_MEM
+    /* Littleendian and unaligned-capable */
+    *p = v;
+#else
+    uint32_t *pp = (uint32_t *) p;
+    set_32(pp[0], v);
+    set_32(pp[1], v >> 32);
+#endif
+}
+
 #define LDLINUX_MAGIC	0x3eb202fe
 
 /* Patch area for disk-based installers */
@@ -88,6 +116,7 @@ struct patch_area {
     uint32_t dwords;
     uint32_t checksum;
     uint16_t maxtransfer;
+    uint16_t advptroffset;
     uint16_t diroffset;
     uint16_t dirlen;
     uint16_t subvoloffset;
@@ -96,7 +125,13 @@ struct patch_area {
     uint16_t secptrcnt;
 };
 
-  /* FAT bootsector format, also used by other disk-based derivatives */
+/* Sector extent */
+struct syslinux_extent {
+    uint64_t lba;
+    uint16_t len;
+} __attribute__((packed));
+
+/* FAT bootsector format, also used by other disk-based derivatives */
 struct boot_sector {
     uint8_t bsJump[3];
     char bsOemName[8];
@@ -121,7 +156,7 @@ struct boot_sector {
 	    uint32_t VolumeID;
 	    char VolumeLabel[11];
 	    char FileSysType[8];
-	    uint8_t Code[444];
+	    uint8_t Code[440];
 	} __attribute__ ((packed)) bs16;
 	struct {
 	    uint32_t FATSz32;
@@ -137,11 +172,11 @@ struct boot_sector {
 	    uint32_t VolumeID;
 	    char VolumeLabel[11];
 	    char FileSysType[8];
-	    uint8_t Code[416];
+	    uint8_t Code[412];
 	} __attribute__ ((packed)) bs32;
     } __attribute__ ((packed));
 
-    uint32_t NextSector;	/* Pointer to the first unused sector */
+    uint64_t NextSector;	/* Pointer to the first unused sector */
     uint16_t bsSignature;
 } __attribute__ ((packed));
 
diff --git a/libinstaller/syslxmod.c b/libinstaller/syslxmod.c
index c600a816..c9eddec1 100644
--- a/libinstaller/syslxmod.c
+++ b/libinstaller/syslxmod.c
@@ -161,7 +161,7 @@ static __noinline uint8_t get_8_sl(const uint8_t * p)
     uint8_t v;
 
     p = set_fs(p);
-    asm volatile ("movb %%fs:%1,%0":"=q" (v):"m"(*p));
+    asm volatile("movb %%fs:%1,%0":"=q" (v):"m"(*p));
     return v;
 }
 #endif
@@ -171,7 +171,7 @@ static __noinline uint16_t get_16_sl(const uint16_t * p)
     uint16_t v;
 
     p = set_fs(p);
-    asm volatile ("movw %%fs:%1,%0":"=r" (v):"m"(*p));
+    asm volatile("movw %%fs:%1,%0":"=r" (v):"m"(*p));
     return v;
 }
 
@@ -180,28 +180,50 @@ static __noinline uint32_t get_32_sl(const uint32_t * p)
     uint32_t v;
 
     p = set_fs(p);
-    asm volatile ("movl %%fs:%1,%0":"=r" (v):"m"(*p));
+    asm volatile("movl %%fs:%1,%0":"=r" (v):"m"(*p));
     return v;
 }
 
 #if 0				/* unused */
+static __noinline uint64_t get_64_sl(const uint64_t * p)
+{
+    uint32_t v0, v1;
+    const uint32_t *pp = (const uint32_t *)p;
+
+    p = set_fs(p);
+    asm volatile("movl %%fs:%1,%0" : "=r" (v0) : "m" (pp[0]));
+    asm volatile("movl %%fs:%1,%0" : "=r" (v1) : "m" (pp[1]));
+    return v0 + ((uint64_t)v1 << 32);
+}
+#endif
+
+#if 0				/* unused */
 static __noinline void set_8_sl(uint8_t * p, uint8_t v)
 {
     p = set_fs(p);
-    asm volatile ("movb %1,%%fs:%0":"=m" (*p):"qi"(v));
+    asm volatile("movb %1,%%fs:%0":"=m" (*p):"qi"(v));
 }
 #endif
 
 static __noinline void set_16_sl(uint16_t * p, uint16_t v)
 {
     p = set_fs(p);
-    asm volatile ("movw %1,%%fs:%0":"=m" (*p):"ri"(v));
+    asm volatile("movw %1,%%fs:%0":"=m" (*p):"ri"(v));
 }
 
 static __noinline void set_32_sl(uint32_t * p, uint32_t v)
 {
     p = set_fs(p);
-    asm volatile ("movl %1,%%fs:%0":"=m" (*p):"ri"(v));
+    asm volatile("movl %1,%%fs:%0":"=m" (*p):"ri"(v));
+}
+
+static __noinline void set_64_sl(uint64_t * p, uint64_t v)
+{
+    uint32_t *pp = (uint32_t *)p;
+
+    p = set_fs(p);
+    asm volatile("movl %1,%%fs:%0" : "=m" (pp[0]) : "ri"((uint32_t)v));
+    asm volatile("movl %1,%%fs:%0" : "=m" (pp[1]) : "ri"((uint32_t)(v >> 32)));
 }
 
 #else
@@ -210,13 +232,63 @@ static __noinline void set_32_sl(uint32_t * p, uint32_t v)
 #define get_8_sl(x)    get_8(x)
 #define get_16_sl(x)   get_16(x)
 #define get_32_sl(x)   get_32(x)
+#define get_64_sl(x)   get_64(x)
 #define set_8_sl(x,y)  set_8(x,y)
 #define set_16_sl(x,y) set_16(x,y)
 #define set_32_sl(x,y) set_32(x,y)
+#define set_64_sl(x,y) set_64(x,y)
 
 #endif
 
 /*
+ * Generate sector extents
+ */
+static void generate_extents(struct syslinux_extent *ex, int nptrs,
+			     const sector_t *sectp, int nsect)
+{
+    struct syslinux_extent thisex;
+    uint32_t addr = 0x7c00 + 2*SECTOR_SIZE;
+    uint32_t base;
+    sector_t sect;
+
+    thisex.len = base = 0;
+
+    memset(ex, 0, nptrs * sizeof *ex);
+
+    while (nsect) {
+	sect = *sectp++;
+
+	if (thisex.len &&
+	    sect == thisex.lba + thisex.len &&
+	    ((addr ^ (base + thisex.len * SECTOR_SIZE)) & 0xffff0000) == 0) {
+	    /* We can add to the current extent */
+	    thisex.len++;
+	    goto next;
+	}
+
+	if (thisex.len) {
+	    set_64_sl(&ex->lba, thisex.lba);
+	    set_16_sl(&ex->len, thisex.len);
+	    ex++;
+	}
+
+	base = addr;
+	thisex.lba = sect;
+	thisex.len = 1;
+
+    next:
+	addr += SECTOR_SIZE;
+	nsect--;
+    }
+
+    if (thisex.len) {
+	set_64_sl(&ex->lba, thisex.lba);
+	set_16_sl(&ex->len, thisex.len);
+	ex++;
+    }
+}
+
+/*
  * This patches the boot sector and the beginning of ldlinux.sys
  * based on an ldlinux.sys sector map passed in.  Typically this is
  * handled by writing ldlinux.sys, mapping it, and then overwrite it
@@ -227,18 +299,23 @@ static __noinline void set_32_sl(uint32_t * p, uint32_t v)
  * Returns the number of modified bytes in ldlinux.sys if successful,
  * otherwise -1.
  */
-int syslinux_patch(const uint32_t * sectors, int nsectors,
+#define NADV 2
+
+int syslinux_patch(const sector_t *sectp, int nsectors,
 		   int stupid, int raid_mode, const char *subdir)
 {
     struct patch_area *patcharea;
+    struct syslinux_extent *ex;
     uint32_t *wp;
-    int nsect = (boot_image_len + 511) >> 9;
+    int nsect = ((boot_image_len + SECTOR_SIZE - 1) >> SECTOR_SHIFT) + 2;
     uint32_t csum;
     int i, dw, nptrs;
     struct boot_sector *sbs = (struct boot_sector *)boot_sector;
     size_t diroffset, dirlen;
+    int secptroffset;
+    uint64_t *advptrs;
 
-    if (nsectors < nsect)
+    if (nsectors <= nsect)
 	return -1;
 
     /* Handle RAID mode, write proper bsSignature */
@@ -248,7 +325,7 @@ int syslinux_patch(const uint32_t * sectors, int nsectors,
     set_16(&sbs->bsSignature, 0xAA55);
 
     /* First sector need pointer in boot sector */
-    set_32(&sbs->NextSector, *sectors++);
+    set_64(&sbs->NextSector, *sectp++);
 
     /* Search for LDLINUX_MAGIC to find the patch area */
     for (wp = (uint32_t *)boot_image; get_32_sl(wp) != LDLINUX_MAGIC;
@@ -257,10 +334,36 @@ int syslinux_patch(const uint32_t * sectors, int nsectors,
 
     /* Set up the totals */
     dw = boot_image_len >> 2;	/* COMPLETE dwords, excluding ADV */
-    set_16_sl(&patcharea->data_sectors, nsect);	/* Not including ADVs */
+    set_16_sl(&patcharea->data_sectors, nsect - 2); /* Not including ADVs */
     set_16_sl(&patcharea->adv_sectors, 2);	/* ADVs need 2 sectors */
     set_32_sl(&patcharea->dwords, dw);
 
+    /* Handle Stupid mode */
+    if (stupid) {
+	/* Access only one sector at a time */
+	set_16(&patcharea->maxtransfer, 1);
+    }
+
+    /* Set the sector extents */
+    secptroffset = get_16_sl(&patcharea->secptroffset);
+    ex = (struct syslinux_extent *) ((char *)boot_image + secptroffset);
+    nptrs = get_16_sl(&patcharea->secptrcnt);
+
+    if (nsect > nptrs) {
+	/* Not necessarily an error in this case, but a general problem */
+	fprintf(stderr, "Insufficient extent space, build error!\n");
+	exit(1);
+    }
+
+    /* -1 for the pointer in the boot sector, -2 for the two ADVs */
+    generate_extents(ex, nptrs, sectp, nsect-1-2);
+
+    /* ADV pointers */
+    advptrs = (uint64_t *)((char *)boot_image +
+			   get_16_sl(&patcharea->advptroffset));
+    set_64_sl(&advptrs[0], sectp[nsect-1-2]);
+    set_64_sl(&advptrs[1], sectp[nsect-1-1]);
+
     /* Poke in the base directory path */
     if (subdir) {
 	diroffset = get_16(&patcharea->diroffset);
@@ -272,25 +375,6 @@ int syslinux_patch(const uint32_t * sectors, int nsectors,
 	memcpy((char *)boot_image + diroffset, subdir, strlen(subdir) + 1);
     }
 
-    /* Handle Stupid mode */
-    if (stupid) {
-	/* Access only one sector at a time */
-	set_16(&patcharea->maxtransfer, 1);
-    }
-
-    /* Set the sector pointers */
-    wp = (uint32_t *) ((char *)boot_image +
-		       get_16_sl(&patcharea->secptroffset));
-    nptrs = get_16_sl(&patcharea->secptrcnt);
-
-    nsect += 2;
-    while (--nsect) { /* the first sector is in bs->NextSector */
-	set_32_sl(wp++, *sectors++);
-	nptrs--;
-    }
-    while (nptrs--)
-	set_32_sl(wp++, 0);
-
     /* Now produce a checksum */
     set_32_sl(&patcharea->checksum, 0);