[pcbios] Support arbitrary splits of the e820 memory map

Allow for an arbitrary number of splits of the system memory map via
INT 15,e820.

Features of the new map-mangling algorithm include:

  Supports random access to e820 map entries.

  Requires only sequential access support from the underlying e820
  map, even if our caller uses random access.

  Empty regions will always be stripped.

  Always terminates with %ebx=0, even if the underlying map terminates
  with CF=1.

  Allows for an arbitrary number of hidden regions, with underlying
  regions split into as many subregions as necessary.

Total size increase to achieve this is 193 bytes.

5 files changed, 123 insertions, 360 deletions

diff --git a/src/arch/i386/core/umalloc.c b/src/arch/i386/core/umalloc.c
index bfd62ef1..3990488c 100644
--- a/src/arch/i386/core/umalloc.c
+++ b/src/arch/i386/core/umalloc.c
@@ -194,8 +194,8 @@ userptr_t urealloc ( userptr_t ptr, size_t new_size ) {
 
 	/* Collect any free blocks and update hidden memory region */
 	ecollect_free();
-	hide_region ( EXTMEM, user_to_phys ( bottom, -sizeof ( extmem ) ),
-		      user_to_phys ( top, 0 ) );
+	hide_umalloc ( user_to_phys ( bottom, -sizeof ( extmem ) ),
+		       user_to_phys ( top, 0 ) );
 
 	return ( new_size ? new : UNOWHERE );
 }
diff --git a/src/arch/i386/firmware/pcbios/e820mangler.S b/src/arch/i386/firmware/pcbios/e820mangler.S
index 0ab857b6..3c4cf21b 100644
--- a/src/arch/i386/firmware/pcbios/e820mangler.S
+++ b/src/arch/i386/firmware/pcbios/e820mangler.S
@@ -26,159 +26,82 @@
 #define SMAP 0x534d4150
 
 /****************************************************************************
- * Check for overlap
  *
- * Parameters:
- *  %edx:%eax	Region start
- *  %ecx:%ebx	Region end
- *  %si		Pointer to hidden region descriptor
- * Returns:
- *  CF set	Region overlaps
- *  CF clear	No overlap
- ****************************************************************************
- */ 
-	.section ".text16"
-check_overlap:
-	/* If start >= hidden_end, there is no overlap. */
-	testl	%edx, %edx
-	jnz	no_overlap
-	cmpl	4(%si), %eax
-	jae	no_overlap
-	/* If end <= hidden_start, there is no overlap; equivalently,
-	 * if end > hidden_start, there is overlap.
-	*/
-	testl	%ecx, %ecx
-	jnz	overlap
-	cmpl	0(%si), %ebx
-	ja	overlap
-no_overlap:
-	clc
-	ret
-overlap:
-	stc
-	ret
-	.size check_overlap, . - check_overlap
-
-/****************************************************************************
- * Check for overflow/underflow
+ * Allowed memory windows
  *
- * Parameters:
- *  %edx:%eax	Region start
- *  %ecx:%ebx	Region end
- * Returns:
- *  CF set	start < end
- *  CF clear	start >= end
- ****************************************************************************
- */
-	.section ".text16"
-check_overflow:
-	pushl	%ecx
-	pushl	%ebx
-	subl	%eax, %ebx
-	sbbl	%edx, %ecx
-	popl	%ebx
-	popl	%ecx
-	ret
-	.size check_overflow, . - check_overflow
-	
-/****************************************************************************
- * Truncate towards start of region
+ * There are two ways to view this list.  The first is as a list of
+ * (non-overlapping) allowed memory regions, sorted by increasing
+ * address.  The second is as a list of (non-overlapping) hidden
+ * memory regions, again sorted by increasing address.  The second
+ * view is offset by half an entry from the first: think about this
+ * for a moment and it should make sense.
  *
- * Parameters:
- *  %edx:%eax	Region start
- *  %ecx:%ebx	Region end
- *  %si		Pointer to hidden region descriptor
- * Returns:
- *  %edx:%eax	Modified region start
- *  %ecx:%ebx	Modified region end
- *  CF set	Region was truncated
- *  CF clear	Region was not truncated
- ****************************************************************************
- */
-	.section ".text16"
-truncate_to_start:
-	/* If overlaps, set region end = hidden region start */
-	call	check_overlap
-	jnc	99f
-	movl	0(%si), %ebx
-	xorl	%ecx, %ecx
-	/* If region end < region start, set region end = region start */
-	call	check_overflow
-	jnc	1f
-	movl	%eax, %ebx
-	movl	%edx, %ecx
-1:	stc
-99:	ret
-	.size truncate_to_start, . - truncate_to_start
-
-/****************************************************************************
- * Truncate towards end of region
+ * xxx_memory_window is used to indicate an "allowed region"
+ * structure, hidden_xxx_memory is used to indicate a "hidden region"
+ * structure.  Each structure is 16 bytes in length.
  *
- * Parameters:
- *  %edx:%eax	Region start
- *  %ecx:%ebx	Region end
- *  %si		Pointer to hidden region descriptor
- * Returns:
- *  %edx:%eax	Modified region start
- *  %ecx:%ebx	Modified region end
- *  CF set	Region was truncated
- *  CF clear	Region was not truncated
  ****************************************************************************
  */
-	.section ".text16"
-truncate_to_end:
-	/* If overlaps, set region start = hidden region end */
-	call	check_overlap
-	jnc	99f
-	movl	4(%si), %eax
-	xorl	%edx, %edx
-	/* If region start > region end, set region start = region end */
-	call	check_overflow
-	jnc	1f
-	movl	%ebx, %eax
-	movl	%ecx, %edx
-1:	stc
-99:	ret
-	.size truncate_to_end, . - truncate_to_end
-	
+	.section ".data16"
+	.align 16
+	.globl hidemem_base
+	.globl hidemem_umalloc
+	.globl hidemem_text
+memory_windows:
+base_memory_window:	.long 0x00000000, 0x00000000 /* Start of memory */
+
+hidemem_base:		.long 0x000a0000, 0x00000000 /* Changes at runtime */
+ext_memory_window:	.long 0x000a0000, 0x00000000 /* 640kB mark */
+
+hidemem_umalloc:	.long 0xffffffff, 0xffffffff /* Changes at runtime */
+			.long 0xffffffff, 0xffffffff /* Changes at runtime */
+
+hidemem_text:		.long 0xffffffff, 0xffffffff /* Changes at runtime */
+			.long 0xffffffff, 0xffffffff /* Changes at runtime */
+
+			.long 0xffffffff, 0xffffffff /* End of memory */
+memory_windows_end:
+
 /****************************************************************************
- * Truncate region
+ * Truncate region to memory window
  *
  * Parameters:
- *  %edx:%eax	Region start
- *  %ecx:%ebx	Region length (*not* region end)
- *  %bp		truncate_to_start or truncate_to_end
+ *  %edx:%eax	Start of region
+ *  %ecx:%ebx	Length of region
+ *  %si		Memory window
  * Returns:
- *  %edx:%eax	Modified region start
- *  %ecx:%ebx	Modified region length
- *  CF set	Region was truncated
- *  CF clear	Region was not truncated
+ *  %edx:%eax	Start of windowed region
+ *  %ecx:%ebx	Length of windowed region
  ****************************************************************************
  */
 	.section ".text16"
-truncate:
-	pushw	%si
-	pushfw
-	/* Convert (start,len) to (start,end) */
+window_region:
+	/* Convert (start,len) to (start, end) */
 	addl	%eax, %ebx
 	adcl	%edx, %ecx
-	/* Hide all hidden regions, truncating as directed */
-	movw	$hidden_regions, %si
-1:	call	*%bp
-	jnc	2f
-	popfw	/* If CF was set, set stored CF in flags word on stack */
-	stc
-	pushfw
-2:	addw	$8, %si
-	cmpl	$0, 0(%si)
-	jne	1b
-	/* Convert modified (start,end) back to (start,len) */
+	/* Truncate to window start */
+	cmpl	4(%si), %edx
+	jne	1f
+	cmpl	0(%si), %eax
+1:	jae	2f
+	movl	4(%si), %edx
+	movl	0(%si), %eax
+2:	/* Truncate to window end */
+	cmpl	12(%si), %ecx
+	jne	1f
+	cmpl	8(%si), %ebx
+1:	jbe	2f
+	movl	12(%si), %ecx
+	movl	8(%si), %ebx
+2:	/* Convert (start, end) back to (start, len) */
 	subl	%eax, %ebx
 	sbbl	%edx, %ecx
-	popfw
-	popw	%si
+	/* If length is <0, set length to 0 */
+	jae	1f
+	xorl	%ebx, %ebx
+	xorl	%ecx, %ecx
 	ret
-	.size truncate, . - truncate
+	.size	window_region, . - window_region
 
 /****************************************************************************
  * Patch "memory above 1MB" figure
@@ -187,21 +110,19 @@ truncate:
  *  %ax		Memory above 1MB, in 1kB blocks
  * Returns:
  *  %ax		Modified memory above 1M in 1kB blocks
- *  CF set	Region was truncated
- *  CF clear	Region was not truncated
  ****************************************************************************
  */
 	.section ".text16"
 patch_1m:
 	pushal
 	/* Convert to (start,len) format and call truncate */
-	movw	$truncate_to_start, %bp
 	xorl	%ecx, %ecx
 	movzwl	%ax, %ebx
 	shll	$10, %ebx
 	xorl	%edx, %edx
 	movl	$0x100000, %eax
-	call	truncate
+	movw	$ext_memory_window, %si
+	call	window_region
 	/* Convert back to "memory above 1MB" format and return via %ax */
 	pushfw
 	shrl	$10, %ebx
@@ -219,20 +140,18 @@ patch_1m:
  *  %bx		Memory above 16MB, in 64kB blocks
  * Returns:
  *  %bx		Modified memory above 16M in 64kB blocks
- *  CF set	Region was truncated
- *  CF clear	Region was not truncated
  ****************************************************************************
  */
 	.section ".text16"
 patch_16m:
 	pushal
 	/* Convert to (start,len) format and call truncate */
-	movw	$truncate_to_start, %bp
 	xorl	%ecx, %ecx
 	shll	$16, %ebx
 	xorl	%edx, %edx
 	movl	$0x1000000, %eax
-	call	truncate
+	movw	$ext_memory_window, %si
+	call	window_region
 	/* Convert back to "memory above 16MB" format and return via %bx */
 	pushfw
 	shrl	$16, %ebx
@@ -252,19 +171,17 @@ patch_16m:
  * Returns:
  *  %ax		Modified memory between 1MB and 16MB, in 1kB blocks
  *  %bx		Modified memory above 16MB, in 64kB blocks
- *  CF set	Region was truncated
- *  CF clear	Region was not truncated
  ****************************************************************************
  */
 	.section ".text16"
 patch_1m_16m:
 	call	patch_1m
-	jc	1f
 	call	patch_16m
-	ret
-1:	/* 1m region was truncated; kill the 16m region */
+	/* If 1M region is no longer full-length, kill off the 16M region */
+	cmpw	$( 15 * 1024 ), %ax
+	je	1f
 	xorw	%bx, %bx
-	ret
+1:	ret
 	.size patch_1m_16m, . - patch_1m_16m
 
 /****************************************************************************
@@ -337,7 +254,7 @@ get_underlying_e820:
 	je	2f /* 'SMAP' missing: error */
 1:	/* An error occurred: return values returned by underlying e820 call */
 	stc	/* Force CF set if SMAP was missing */
-	leal	16(%esp), %esp /* avoid changing other flags */
+	addr32 leal 16(%esp), %esp /* avoid changing other flags */
 	ret
 2:	/* No error occurred */
 	movl	%ebx, underlying_e820_ebx
@@ -400,18 +317,6 @@ underlying_e820_cache:
  *
  ****************************************************************************
  */
-
-	.section ".tbl.data16.memory_windows.00"
-	.align 16
-memory_windows:
-
-	// Dummy memory window encompassing entire 64-bit address space
-	.long 0, 0, 0xffffffff, 0xffffffff
-
-	.section ".tbl.data16.memory_windows.99"
-	.align 16
-memory_windows_end:
-	
 	.section ".text16"
 get_windowed_e820:
 
@@ -421,7 +326,6 @@ get_windowed_e820:
 
 	/* Split %ebx into %si:%bx, store original %bx in %bp */
 	pushl	%ebx
-	xorl	%esi, %esi
 	popw	%bp
 	popw	%si
 
@@ -441,30 +345,8 @@ get_windowed_e820:
 	movl	%es:4(%di), %edx
 	movl	%es:8(%di), %ebx
 	movl	%es:12(%di), %ecx
-	/* Convert (start,len) to (start, end) */
-	addl	%eax, %ebx
-	adcl	%edx, %ecx
-	/* Truncate to window start */
-	cmpl	4(%esi), %edx
-	jne	1f
-	cmpl	0(%esi), %eax
-1:	jae	2f
-	movl	4(%esi), %edx
-	movl	0(%esi), %eax
-2:	/* Truncate to window end */
-	cmpl	12(%esi), %ecx
-	jne	1f
-	cmpl	8(%esi), %ebx
-1:	jbe	2f
-	movl	12(%esi), %ecx
-	movl	8(%esi), %ebx
-2:	/* Convert (start, end) back to (start, len) */
-	subl	%eax, %ebx
-	sbbl	%edx, %ecx
-	/* If length is <0, set length to 0 */
-	jae	1f
-	xorl	%ebx, %ebx
-	xorl	%ecx, %ecx
+	/* Truncate region to current window */
+	call	window_region
 1:	/* Store modified values in e820 map entry */
 	movl	%eax, %es:0(%di)
 	movl	%edx, %es:4(%di)
@@ -537,7 +419,7 @@ get_nonempty_e820:
 98:	/* Clear CF */
 	clc
 99:	/* Return values from underlying call */
-	leal	12(%esp), %esp /* avoid changing flags */
+	addr32 leal 12(%esp), %esp /* avoid changing flags */
 	ret
 	.size get_nonempty_e820, . - get_nonempty_e820
 
@@ -572,7 +454,7 @@ get_mangled_e820:
 	popw	%es
 	movw	%sp, %di
 	call	get_nonempty_e820
-	leal	20(%esp), %esp /* avoid changing flags */
+	addr32 leal 20(%esp), %esp /* avoid changing flags */
 	popal
 	jnc	99f /* There are further nonempty regions */
 
@@ -584,136 +466,16 @@ get_mangled_e820:
 	.size get_mangled_e820, . - get_mangled_e820
 
 /****************************************************************************
- * Patch E820 memory map entry
- *
- * Parameters:
- *  %es:di	Pointer to E820 memory map descriptor
- *  %bp		truncate_to_start or truncate_to_end
- * Returns:
- *  %es:di	Pointer to now-modified E820 memory map descriptor
- *  CF set	Region was truncated
- *  CF clear	Region was not truncated
- ****************************************************************************
- */
-	.section ".text16"
-patch_e820:
-	pushal
-	movl	%es:0(%di), %eax
-	movl	%es:4(%di), %edx
-	movl	%es:8(%di), %ebx
-	movl	%es:12(%di), %ecx
-	call	truncate
-	movl	%eax, %es:0(%di)
-	movl	%edx, %es:4(%di)
-	movl	%ebx, %es:8(%di)
-	movl	%ecx, %es:12(%di)
-	popal
-	ret
-	.size patch_e820, . - patch_e820
-
-/****************************************************************************
- * Split E820 memory map entry if necessary
- *
- * Parameters: 
- *   As for INT 15,e820
- * Returns:
- *   As for INT 15,e820
- *
- * Calls the underlying INT 15,e820 and returns a modified memory map.
- * Regions will be split around any hidden regions.
+ * INT 15,e820 handler
  ****************************************************************************
  */
 	.section ".text16"
-split_e820:
-	pushw	%si
-	pushw	%bp
-	/* Caller's %bx => %si, real %ebx to %ebx, call previous handler */
-	pushfw
-	movw	%bx, %si
-	testl	%ebx, %ebx
-	jnz	1f
-	movl	%ebx, %cs:real_ebx
-1:	movl	%cs:real_ebx, %ebx
-
-//	lcall	*%cs:int15_vector
-	/* Hacked in call to get_mangled_e820 in place of underlying INT15 */
-	popfw
+int15_e820:
 	pushw	%ds
 	pushw	%cs:rm_ds
 	popw	%ds
 	call	get_mangled_e820
 	popw	%ds
-
-	pushfw
-	/* Edit result */
-	pushw	%ds
-	pushw	%cs:rm_ds
-	popw	%ds
-	movw	$truncate_to_start, %bp
-	incw	%si
-	jns	2f
-	movw	$truncate_to_end, %bp
-2:	call	patch_e820
-	jnc	3f
-	xorw	$0x8000, %si
-3:	testw	%si, %si
-	js	4f
-	movl	%ebx, %cs:real_ebx
-	testl	%ebx, %ebx
-	jz	5f
-4:	movw	%si, %bx
-5:	popw	%ds
-	/* Restore flags returned by previous handler and return */
-	popfw
-	popw	%bp
-	popw	%si
-	ret
-	.size split_e820, . - split_e820
-
-	.section ".text16.data"
-real_ebx:
-	.long 0
-	.size real_ebx, . - real_ebx
-
-/****************************************************************************
- * INT 15,e820 handler
- ****************************************************************************
- */
-	.section ".text16"
-int15_e820:
-	pushl	%eax
-	pushl	%ecx
-	pushl	%edx	
-	call	split_e820
-	pushfw
-	/* If we've hit an error, exit immediately */
-	jc	99f
-	/* If region is non-empty, return this region */
-	pushl	%eax
-	movl	%es:8(%di), %eax
-	orl	%es:12(%di), %eax
-	popl	%eax
-	jnz	99f
-	/* Region is empty.  If this is not the end of the map,
-	 * skip over this region.
-	 */
-	testl	%ebx, %ebx
-	jz	1f
-	popfw
-	popl	%edx
-	popl	%ecx
-	popl	%eax
-	jmp	int15_e820
-1:	/* Region is empty and this is the end of the map.  Return
-	 * with CF set to avoid placing an empty region at the end of
-	 * the map.
-	 */
-	popfw
-	stc
-	pushfw
-99:	/* Restore flags from original INT 15,e820 call and return */
-	popfw
-	addr32 leal	12(%esp), %esp /* avoid changing flags */
 	lret	$2
 	.size int15_e820, . - int15_e820
 	
diff --git a/src/arch/i386/firmware/pcbios/hidemem.c b/src/arch/i386/firmware/pcbios/hidemem.c
index 11ca3128..fb60fa8b 100644
--- a/src/arch/i386/firmware/pcbios/hidemem.c
+++ b/src/arch/i386/firmware/pcbios/hidemem.c
@@ -15,6 +15,7 @@
  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  */
 
+#include <assert.h>
 #include <realmode.h>
 #include <biosint.h>
 #include <basemem.h>
@@ -25,7 +26,7 @@
 #define ALIGN_HIDDEN 4096   /* 4kB page alignment should be enough */
 
 /**
- * A hidden region of Etherboot
+ * A hidden region of gPXE
  *
  * This represents a region that will be edited out of the system's
  * memory map.
@@ -34,24 +35,23 @@
  * changed.
  */
 struct hidden_region {
-	/* Physical start address */
-	physaddr_t start;
-	/* Physical end address */
-	physaddr_t end;
+	/** Physical start address */
+	uint64_t start;
+	/** Physical end address */
+	uint64_t end;
 };
 
-/**
- * List of hidden regions
- *
- * Must be terminated by a zero entry.
- */
-struct hidden_region __data16_array ( hidden_regions, [] ) = {
-	[TEXT] = { 0, 0 },
-	[BASEMEM] = { ( 640 * 1024 ), ( 640 * 1024 ) },
-	[EXTMEM] = { 0, 0 },
-	{ 0, 0, } /* Terminator */
-};
-#define hidden_regions __use_data16 ( hidden_regions )
+/** Hidden base memory */
+extern struct hidden_region __data16 ( hidemem_base );
+#define hidemem_base __use_data16 ( hidemem_base )
+
+/** Hidden umalloc memory */
+extern struct hidden_region __data16 ( hidemem_umalloc );
+#define hidemem_umalloc __use_data16 ( hidemem_umalloc )
+
+/** Hidden text memory */
+extern struct hidden_region __data16 ( hidemem_text );
+#define hidemem_text __use_data16 ( hidemem_text )
 
 /** Assembly routine in e820mangler.S */
 extern void int15();
@@ -60,14 +60,19 @@ extern void int15();
 extern struct segoff __text16 ( int15_vector );
 #define int15_vector __use_text16 ( int15_vector )
 
+/* The linker defines these symbols for us */
+extern char _text[];
+extern char _end[];
+
 /**
  * Hide region of memory from system memory map
  *
+ * @v region		Hidden memory region
  * @v start		Start of region
  * @v end		End of region
  */
-void hide_region ( unsigned int region_id, physaddr_t start, physaddr_t end ) {
-	struct hidden_region *region = &hidden_regions[region_id];
+static void hide_region ( struct hidden_region *region,
+			  physaddr_t start, physaddr_t end ) {
 
 	/* Some operating systems get a nasty shock if a region of the
 	 * E820 map seems to start on a non-page boundary.  Make life
@@ -76,21 +81,7 @@ void hide_region ( unsigned int region_id, physaddr_t start, physaddr_t end ) {
 	region->start = ( start & ~( ALIGN_HIDDEN - 1 ) );
 	region->end = ( ( end + ALIGN_HIDDEN - 1 ) & ~( ALIGN_HIDDEN - 1 ) );
 
-	DBG ( "Hiding region %d [%lx,%lx)\n",
-	      region_id, region->start, region->end );
-}
-
-/**
- * Hide Etherboot text
- *
- */
-static void hide_text ( void ) {
-
-	/* The linker defines these symbols for us */
-	extern char _text[];
-	extern char _end[];
-
-	hide_region ( TEXT, virt_to_phys ( _text ), virt_to_phys ( _end ) );
+	DBG ( "Hiding region [%llx,%llx)\n", region->start, region->end );
 }
 
 /**
@@ -102,7 +93,25 @@ void hide_basemem ( void ) {
 	 * hide_region(), because we don't want this rounded to the
 	 * nearest page boundary.
 	 */
-	hidden_regions[BASEMEM].start = ( get_fbms() * 1024 );
+	hidemem_base.start = ( get_fbms() * 1024 );
+}
+
+/**
+ * Hide umalloc() region
+ *
+ */
+void hide_umalloc ( physaddr_t start, physaddr_t end ) {
+	assert ( end <= virt_to_phys ( _text ) );
+	hide_region ( &hidemem_umalloc, start, end );
+}
+
+/**
+ * Hide .text and .data
+ *
+ */
+void hide_text ( void ) {
+	hide_region ( &hidemem_text, virt_to_phys ( _text ),
+		      virt_to_phys ( _end ) );
 }
 
 /**
@@ -114,8 +123,9 @@ void hide_basemem ( void ) {
 static void hide_etherboot ( void ) {
 
 	/* Initialise the hidden regions */
-	hide_text();
 	hide_basemem();
+	hide_umalloc ( virt_to_phys ( _text ), virt_to_phys ( _text ) );
+	hide_text();
 
 	/* Hook INT 15 */
 	hook_bios_interrupt ( 0x15, ( unsigned int ) int15,
diff --git a/src/arch/i386/scripts/i386.lds b/src/arch/i386/scripts/i386.lds
index 0422344d..a5a01056 100644
--- a/src/arch/i386/scripts/i386.lds
+++ b/src/arch/i386/scripts/i386.lds
@@ -82,7 +82,6 @@ SECTIONS {
 	__data16 = .;
 	*(.data16)
 	*(.data16.*)
-	*(SORT(.tbl.data16.*))	/* Various tables.  See include/tables.h */
 	_edata16_progbits = .;
     }
     .bss16 : AT ( _data16_load_offset + __bss16 ) {
diff --git a/src/include/gpxe/hidemem.h b/src/include/gpxe/hidemem.h
index 547f8881..010fdb58 100644
--- a/src/include/gpxe/hidemem.h
+++ b/src/include/gpxe/hidemem.h
@@ -8,16 +8,8 @@
  *
  */
 
-/**
- * Unique IDs for hidden regions
- */
-enum hidemem_region_id {
-	TEXT = 0,
-	BASEMEM,
-	EXTMEM,
-};
+#include <stdint.h>
 
-extern void hide_region ( unsigned int region_id, physaddr_t start,
-			  physaddr_t end );
+extern void hide_umalloc ( physaddr_t start, physaddr_t end );
 
 #endif /* _GPXE_HIDEMEM_H */