[LinuxBIOS] [RFC][PATCH] v3: lar header after member support

[Carl-Daniel Hailfinger]

We had that patch in a larger package about 7 weeks ago, but most parts
of the package have been merged since then, reducing the clutter in the
patch to zero. For your reference:
Message-ID: 
Date: Fri, 12 Oct 2007 00:38:07 +0200

AFAIK not all architectures start executing code at the top of ROM, some
start at the bottom (low address). In that case, we can't start the
archive with a LAR header, but we can end it with one or postfix the
first archive member with a LAR header. To achieve that, the patch
redefines offset as signed instead of unsigned and allows the lar header
after the boot block to point to the boot block at the beginning. That
way, even bottom boot architectures can use the existing header format
unless the first LAR member is bigger than 2 GB.
This patch also introduces a 2 GB limit for file names in LARchives and
a 2 GB limit for unused space between header and data. There is no new
restriction for member lengths or archive length.

Current LAR archives look like this:

Hn=header n
-=padding
Dn=data n
H0D0D0D0H1D1----H2D2D2
where the last bytes of D2 are executed after poweron.

The patch (together with signed offset) makes archives like the below
one possible:
D0D0D0H0H1D1----H2D2D2 (header after boot block points to boot block)

The new archive format possibility allows placing a boot block at the
beginning without sacrificing the goal of one common archive format.
However, there are two potential problems:
- Endless loops if we aren't careful when walking the LAR. I think I got
all corner cases right.
- "Nobody will need more than 640kB", in our case it would be 2GB boot
blocks.

Signed-off-by: Carl-Daniel Hailfinger

Index: LinuxBIOSv3-larheaderaftermember/include/lar.h
===================================================================
--- LinuxBIOSv3-larheaderaftermember/include/lar.h	(Revision 539)
+++ LinuxBIOSv3-larheaderaftermember/include/lar.h	(Arbeitskopie)
@@ -61,7 +61,15 @@
    u32 reallen;
    u32 checksum;
    u32 compchecksum;
-	u32 offset;
+	/* The offset is signed to allow header after data for the first member
+	 * of the LAR. This is needed if code execution starts at bottom of
+	 * flash instead of at top of flash (x86). Please note that a
+	 * header-after-data LAR member can't be larger than 2^31 bytes.
+	 * Right now, we are about five orders of magnitude away from such a
+	 * beast.
+	 * Filenames are limited to 2^31-1-sizeof(lar_header)-1 bytes.
+	 * "Nobody will ever need more than 640k" */
+	s32 offset;
    /* Compression:
     * 0 = no compression
     * 1 = lzma
Index: LinuxBIOSv3-larheaderaftermember/lib/lar.c
===================================================================
--- LinuxBIOSv3-larheaderaftermember/lib/lar.c	(Revision 539)
+++ LinuxBIOSv3-larheaderaftermember/lib/lar.c	(Arbeitskopie)
@@ -116,7 +116,9 @@

if (strcmp(fullname, filename) == 0) {
    		printk(BIOS_SPEW, "LAR: CHECK %s @ %p\n", fullname, header);
-			result->start = walk + ntohl(header->offset);
+			/* In the header-before-member case offset is at least
+			 * sizeof(header) + strlen(filename) + 1 */
+			result->start = walk + (s32)ntohl(header->offset);
    		result->len = ntohl(header->len);
    		result->reallen = ntohl(header->reallen);
    		result->compression = ntohl(header->compression);
@@ -137,9 +139,30 @@
    	 * In the case of consecutive archive members with header-
    	 * before-member structure, the next iteration of the loop will
    	 * start exactly at the beginning of the next header.
-		 */
+		 * In the case of header-after-member (e.g. for bottom boot
+		 * architectures) the calculation below will effectively cause
+		 * walk < header. To elaborate a bit more, in this case
+		 * (header->offset + header->len - 1) will evaluate to a value
+		 * between -1 (header directly after file), -16 (file, 15 bytes
+		 * pad, header), and even smaller values if there is 16 bytes
+		 * or more of padding between member and header. The outer
+		 * expression will usually evaluate to 0xfffffff0, cause the
+		 * expected overflow with unsigned arithmetic and result in a
+		 * decrease of walk. That condition can be checked. */
+#warning FIXME: This loop will explode if this code is ever compiled in 64bit mode
+#warning because of the hardcoded 0xfffffff0.
    	walk += (ntohl(header->offset) + ntohl(header->len) - 1)
    		 & 0xfffffff0;
+		/* If we have header-after-member, walk < header is true.
+		 * Go forward instead by starting at header, adding header size
+		 * and strlen(fullname). The result of this calculation is the
+		 * position of the terminating \0 of fullname. Round that
+		 * address down to the next 16 byte boundary. */
+		if (walk < (char *)header) {
+			walk = (char *)header;
+			walk += (sizeof(struct lar_header) + strlen(fullname))
+				& 0xfffffff0;
+		}
    }
    printk(BIOS_SPEW, "LAR: File not found!\n");
    return 1;
Index: LinuxBIOSv3-larheaderaftermember/util/lar/lar.h
===================================================================
--- LinuxBIOSv3-larheaderaftermember/util/lar/lar.h	(Revision 539)
+++ LinuxBIOSv3-larheaderaftermember/util/lar/lar.h	(Arbeitskopie)
@@ -60,6 +60,7 @@
 typedef uint64_t u64;
 typedef uint32_t u32;
 typedef uint8_t  u8;
+typedef int32_t  s32;

/* NOTE -- This and the user-mode lar.h may NOT be in sync. Be careful. */
 struct lar_header {
@@ -68,9 +69,15 @@
    u32 reallen;
    u32 checksum;
    u32 compchecksum;
-	/* Filenames are limited to 2^31-1-sizeof(lar_header)-1 bytes.
+	/* The offset is signed to allow header after data for the first member
+	 * of the LAR. This is needed if code execution starts at bottom of
+	 * flash instead of at top of flash (x86). Please note that a
+	 * header-after-data LAR member can't be larger than 2^31 bytes.
+	 * Right now, we are about five orders of magnitude away from such a
+	 * beast.
+	 * Filenames are limited to 2^31-1-sizeof(lar_header)-1 bytes.
     * "Nobody will ever need more than 640k" */
-	u32 offset;
+	s32 offset;
    /* Compression:
     * 0 = no compression
     * 1 = lzma

[RFC][PATCH] v3: lar header after member support

[Carl-Daniel Hailfinger]

We need this for MIPS.

The patch already has an old

Acked-by: Peter Stuge

see Message-ID:  for reference.

Regards,
Carl-Daniel

On 05.12.2007 03:26, Carl-Daniel Hailfinger wrote:
> We had that patch in a larger package about 7 weeks ago, but most parts
> of the package have been merged since then, reducing the clutter in the
> patch to zero. For your reference:
> Message-ID: 
> Date: Fri, 12 Oct 2007 00:38:07 +0200
>
> AFAIK not all architectures start executing code at the top of ROM, some
> start at the bottom (low address). In that case, we can't start the
> archive with a LAR header, but we can end it with one or postfix the
> first archive member with a LAR header. To achieve that, the patch
> redefines offset as signed instead of unsigned and allows the lar header
> after the boot block to point to the boot block at the beginning. That
> way, even bottom boot architectures can use the existing header format
> unless the first LAR member is bigger than 2 GB.
> This patch also introduces a 2 GB limit for file names in LARchives and
> a 2 GB limit for unused space between header and data. There is no new
> restriction for member lengths or archive length.
>
> Current LAR archives look like this:
>
> Hn=header n
> -=padding
> Dn=data n
> H0D0D0D0H1D1----H2D2D2
> where the last bytes of D2 are executed after poweron.
>
> The patch (together with signed offset) makes archives like the below
> one possible:
> D0D0D0H0H1D1----H2D2D2 (header after boot block points to boot block)
>
> The new archive format possibility allows placing a boot block at the
> beginning without sacrificing the goal of one common archive format.
> However, there are two potential problems:
> Endless loops if we aren't careful when walking the LAR. I think I got
>
> all corner cases right.
> "Nobody will need more than 640kB", in our case it would be 2GB boot
>
> blocks.
>
> Signed-off-by: Carl-Daniel Hailfinger
> Index: LinuxBIOSv3-larheaderaftermember/include/lar.h
>
> --- LinuxBIOSv3-larheaderaftermember/include/lar.h	(Revision 539)
> +++ LinuxBIOSv3-larheaderaftermember/include/lar.h	(Arbeitskopie)
> @@ -61,7 +61,15 @@
>    u32 reallen;
>    u32 checksum;
>    u32 compchecksum;
> u32 offset;
> /* The offset is signed to allow header after data for the first member
> * of the LAR. This is needed if code execution starts at bottom of
> * flash instead of at top of flash (x86). Please note that a
> * header-after-data LAR member can't be larger than 2^31 bytes.
> * Right now, we are about five orders of magnitude away from such a
> * beast.
> * Filenames are limited to 2^31-1-sizeof(lar_header)-1 bytes.
> * "Nobody will ever need more than 640k" */
> s32 offset;
> /* Compression:
> 0 = no compression
> 1 = lzma
> Index: LinuxBIOSv3-larheaderaftermember/lib/lar.c
>
> --- LinuxBIOSv3-larheaderaftermember/lib/lar.c	(Revision 539)
> +++ LinuxBIOSv3-larheaderaftermember/lib/lar.c	(Arbeitskopie)
> @@ -116,7 +116,9 @@
> if (strcmp(fullname, filename) == 0) {
> 	printk(BIOS_SPEW, "LAR: CHECK %s @ %p\n", fullname, header);
> 	result->start = walk + ntohl(header->offset);
> 	/* In the header-before-member case offset is at least
> 	 * sizeof(header) + strlen(filename) + 1 */
> 	result->start = walk + (s32)ntohl(header->offset);
> result->len = ntohl(header->len);
> result->reallen = ntohl(header->reallen);
> result->compression = ntohl(header->compression);
>
> @@ -137,9 +139,30 @@
>    	 * In the case of consecutive archive members with header-
>    	 * before-member structure, the next iteration of the loop will
>    	 * start exactly at the beginning of the next header.
>  */
>  * In the case of header-after-member (e.g. for bottom boot
>  * architectures) the calculation below will effectively cause
>  * walk < header. To elaborate a bit more, in this case
>  * (header->offset + header->len - 1) will evaluate to a value
>  * between -1 (header directly after file), -16 (file, 15 bytes
>  * pad, header), and even smaller values if there is 16 bytes
>  * or more of padding between member and header. The outer
>  * expression will usually evaluate to 0xfffffff0, cause the
>  * expected overflow with unsigned arithmetic and result in a
>  * decrease of walk. That condition can be checked. */
>
> +#warning FIXME: This loop will explode if this code is ever compiled in 64bit mode
> +#warning because of the hardcoded 0xfffffff0.
>    	walk += (ntohl(header->offset) + ntohl(header->len) - 1)
>    		 & 0xfffffff0;
> /* If we have header-after-member, walk < header is true.
>  * Go forward instead by starting at header, adding header size
>  * and strlen(fullname). The result of this calculation is the
>  * position of the terminating \0 of fullname. Round that
>  * address down to the next 16 byte boundary. */
> if (walk < (char *)header) {
> 	walk = (char *)header;
> 	walk += (sizeof(struct lar_header) + strlen(fullname))
> 		& 0xfffffff0;
> }
> }
> printk(BIOS_SPEW, "LAR: File not found!\n");
> return 1;
> Index: LinuxBIOSv3-larheaderaftermember/util/lar/lar.h
>
> --- LinuxBIOSv3-larheaderaftermember/util/lar/lar.h	(Revision 539)
> +++ LinuxBIOSv3-larheaderaftermember/util/lar/lar.h	(Arbeitskopie)
> @@ -60,6 +60,7 @@
>  typedef uint64_t u64;
>  typedef uint32_t u32;
>  typedef uint8_t  u8;
> +typedef int32_t  s32;
>
> /* NOTE -- This and the user-mode lar.h may NOT be in sync. Be careful. */
>  struct lar_header {
> @@ -68,9 +69,15 @@
>    u32 reallen;
>    u32 checksum;
>    u32 compchecksum;
> /* Filenames are limited to 2^31-1-sizeof(lar_header)-1 bytes.
> /* The offset is signed to allow header after data for the first member
> * of the LAR. This is needed if code execution starts at bottom of
> * flash instead of at top of flash (x86). Please note that a
> * header-after-data LAR member can't be larger than 2^31 bytes.
> * Right now, we are about five orders of magnitude away from such a
> * beast.
> * Filenames are limited to 2^31-1-sizeof(lar_header)-1 bytes.
> "Nobody will ever need more than 640k" */
> u32 offset;
> s32 offset;
> /* Compression:
> 0 = no compression
> 1 = lzma

[RFC][PATCH] v3: lar header after member support

[Stefan Reinauer]

Please dont do this. There's no reason to not just add a jump
instruction in front of an archive on architectures like mips and PPC

Also, NACK as long as the code adds #warnings instead of fixing issues.

Carl-Daniel Hailfinger wrote:
> We need this for MIPS.
>
> The patch already has an old
>
> Acked-by: Peter Stuge
>
> see Message-ID:  for reference.
>
> Regards,
> Carl-Daniel
>
> On 05.12.2007 03:26, Carl-Daniel Hailfinger wrote:
> > We had that patch in a larger package about 7 weeks ago, but most parts
> > of the package have been merged since then, reducing the clutter in the
> > patch to zero. For your reference:
> > Message-ID: 
> > Date: Fri, 12 Oct 2007 00:38:07 +0200
> >
> > AFAIK not all architectures start executing code at the top of ROM, some
> > start at the bottom (low address). In that case, we can't start the
> > archive with a LAR header, but we can end it with one or postfix the
> > first archive member with a LAR header. To achieve that, the patch
> > redefines offset as signed instead of unsigned and allows the lar header
> > after the boot block to point to the boot block at the beginning. That
> > way, even bottom boot architectures can use the existing header format
> > unless the first LAR member is bigger than 2 GB.
> > This patch also introduces a 2 GB limit for file names in LARchives and
> > a 2 GB limit for unused space between header and data. There is no new
> > restriction for member lengths or archive length.
> >
> > Current LAR archives look like this:
> >
> > Hn=header n
> > -=padding
> > Dn=data n
> > H0D0D0D0H1D1----H2D2D2
> > where the last bytes of D2 are executed after poweron.
> >
> > The patch (together with signed offset) makes archives like the below
> > one possible:
> > D0D0D0H0H1D1----H2D2D2 (header after boot block points to boot block)
> >
> > The new archive format possibility allows placing a boot block at the
> > beginning without sacrificing the goal of one common archive format.
> > However, there are two potential problems:
> > Endless loops if we aren't careful when walking the LAR. I think I got
> >
> > all corner cases right.
> > "Nobody will need more than 640kB", in our case it would be 2GB boot
> >
> > blocks.
> >
> > Signed-off-by: Carl-Daniel Hailfinger
> > Index: LinuxBIOSv3-larheaderaftermember/include/lar.h
> >
> > --- LinuxBIOSv3-larheaderaftermember/include/lar.h	(Revision 539)
> > +++ LinuxBIOSv3-larheaderaftermember/include/lar.h	(Arbeitskopie)
> > @@ -61,7 +61,15 @@
> >    u32 reallen;
> >    u32 checksum;
> >    u32 compchecksum;
> > u32 offset;
> > /* The offset is signed to allow header after data for the first member
> > * of the LAR. This is needed if code execution starts at bottom of
> > * flash instead of at top of flash (x86). Please note that a
> > * header-after-data LAR member can't be larger than 2^31 bytes.
> > * Right now, we are about five orders of magnitude away from such a
> > * beast.
> > * Filenames are limited to 2^31-1-sizeof(lar_header)-1 bytes.
> > * "Nobody will ever need more than 640k" */
> > s32 offset;
> > /* Compression:
> > 0 = no compression
> > 1 = lzma
> > Index: LinuxBIOSv3-larheaderaftermember/lib/lar.c
> >
> > --- LinuxBIOSv3-larheaderaftermember/lib/lar.c	(Revision 539)
> > +++ LinuxBIOSv3-larheaderaftermember/lib/lar.c	(Arbeitskopie)
> > @@ -116,7 +116,9 @@
> > if (strcmp(fullname, filename) == 0) {
> > 	printk(BIOS_SPEW, "LAR: CHECK %s @ %p\n", fullname, header);
> > 	result->start = walk + ntohl(header->offset);
> > 	/* In the header-before-member case offset is at least
> > 	 * sizeof(header) + strlen(filename) + 1 */
> > 	result->start = walk + (s32)ntohl(header->offset);
> > result->len = ntohl(header->len);
> > result->reallen = ntohl(header->reallen);
> > result->compression = ntohl(header->compression);
> >
> > @@ -137,9 +139,30 @@
> >    	 * In the case of consecutive archive members with header-
> >    	 * before-member structure, the next iteration of the loop will
> >    	 * start exactly at the beginning of the next header.
> >  */
> >  * In the case of header-after-member (e.g. for bottom boot
> >  * architectures) the calculation below will effectively cause
> >  * walk < header. To elaborate a bit more, in this case
> >  * (header->offset + header->len - 1) will evaluate to a value
> >  * between -1 (header directly after file), -16 (file, 15 bytes
> >  * pad, header), and even smaller values if there is 16 bytes
> >  * or more of padding between member and header. The outer
> >  * expression will usually evaluate to 0xfffffff0, cause the
> >  * expected overflow with unsigned arithmetic and result in a
> >  * decrease of walk. That condition can be checked. */
> >
> > +#warning FIXME: This loop will explode if this code is ever compiled in 64bit mode
> > +#warning because of the hardcoded 0xfffffff0.
> >    	walk += (ntohl(header->offset) + ntohl(header->len) - 1)
> >    		 & 0xfffffff0;
> > /* If we have header-after-member, walk < header is true.
> >  * Go forward instead by starting at header, adding header size
> >  * and strlen(fullname). The result of this calculation is the
> >  * position of the terminating \0 of fullname. Round that
> >  * address down to the next 16 byte boundary. */
> > if (walk < (char *)header) {
> > 	walk = (char *)header;
> > 	walk += (sizeof(struct lar_header) + strlen(fullname))
> > 		& 0xfffffff0;
> > }
> > }
> > printk(BIOS_SPEW, "LAR: File not found!\n");
> > return 1;
> > Index: LinuxBIOSv3-larheaderaftermember/util/lar/lar.h
> >
> > --- LinuxBIOSv3-larheaderaftermember/util/lar/lar.h	(Revision 539)
> > +++ LinuxBIOSv3-larheaderaftermember/util/lar/lar.h	(Arbeitskopie)
> > @@ -60,6 +60,7 @@
> >  typedef uint64_t u64;
> >  typedef uint32_t u32;
> >  typedef uint8_t  u8;
> > +typedef int32_t  s32;
> >
> > /* NOTE -- This and the user-mode lar.h may NOT be in sync. Be careful. */
> >  struct lar_header {
> > @@ -68,9 +69,15 @@
> >    u32 reallen;
> >    u32 checksum;
> >    u32 compchecksum;
> > /* Filenames are limited to 2^31-1-sizeof(lar_header)-1 bytes.
> > /* The offset is signed to allow header after data for the first member
> > * of the LAR. This is needed if code execution starts at bottom of
> > * flash instead of at top of flash (x86). Please note that a
> > * header-after-data LAR member can't be larger than 2^31 bytes.
> > * Right now, we are about five orders of magnitude away from such a
> > * beast.
> > * Filenames are limited to 2^31-1-sizeof(lar_header)-1 bytes.
> > "Nobody will ever need more than 640k" */
> > u32 offset;
> > s32 offset;
> > /* Compression:
> > 0 = no compression
> > 1 = lzma

[RFC][PATCH] v3: lar header after member support

[Carl-Daniel Hailfinger]

On 28.03.2008 10:33, Stefan Reinauer wrote:
> Please dont do this. There's no reason to not just add a jump
> instruction in front of an archive on architectures like mips and PPC

Ugh. How do we handle extraction of archive contents, then? The jump
instruction is not part of any archive member and will simply be
discarded. That would violate our otherwise clean LAR design.
> Also, NACK as long as the code adds #warnings instead of fixing issues.

See below.
> Carl-Daniel Hailfinger wrote:
> > We need this for MIPS.
> >
> > On 05.12.2007 03:26, Carl-Daniel Hailfinger wrote:
> > > Index: LinuxBIOSv3-larheaderaftermember/lib/lar.c
> > >
> > > --- LinuxBIOSv3-larheaderaftermember/lib/lar.c	(Revision 539)
> > > +++ LinuxBIOSv3-larheaderaftermember/lib/lar.c	(Arbeitskopie)
> > > @@ -137,9 +139,30 @@
> > >    	 * In the case of consecutive archive members with header-
> > >    	 * before-member structure, the next iteration of the loop will
> > >    	 * start exactly at the beginning of the next header.
> > >  */
> > >  * In the case of header-after-member (e.g. for bottom boot
> > >  * architectures) the calculation below will effectively cause
> > >  * walk < header. To elaborate a bit more, in this case
> > >  * (header->offset + header->len - 1) will evaluate to a value
> > >  * between -1 (header directly after file), -16 (file, 15 bytes
> > >  * pad, header), and even smaller values if there is 16 bytes
> > >  * or more of padding between member and header. The outer
> > >  * expression will usually evaluate to 0xfffffff0, cause the
> > >  * expected overflow with unsigned arithmetic and result in a
> > >  * decrease of walk. That condition can be checked. */
> > >
> > > +#warning FIXME: This loop will explode if this code is ever compiled in 64bit mode
> > > +#warning because of the hardcoded 0xfffffff0.

We assume sizeof(void *) == sizeof(long) in a number of places. That
assumption is untrue on Win64. Is there any other ABI where that
assumption is incorrect as well?
> > > walk += (ntohl(header->offset) + ntohl(header->len) - 1)
> > > 	 & 0xfffffff0;

I'm considering to replace the 0xfffffff0 with (unsigned long)-16 to
make this more explicit.

Then again, unless we have archive members >=2^31 bytes, the above is
not a bug, just poorly documented code. I'll remove the warning from the
patch.
> > > /* If we have header-after-member, walk < header is true.
> > >  * Go forward instead by starting at header, adding header size
> > >  * and strlen(fullname). The result of this calculation is the
> > >  * position of the terminating \0 of fullname. Round that
> > >  * address down to the next 16 byte boundary. */
> > > if (walk < (char *)header) {
> > > 	walk = (char *)header;
> > > 	walk += (sizeof(struct lar_header) + strlen(fullname))
> > > 		& 0xfffffff0;
> > > }
> > > }
> > > printk(BIOS_SPEW, "LAR: File not found!\n");
> > > return 1;

Regards,
Carl-Daniel