More hpcboot memory/ELF loading errors?

Folks:
	I've been having a lot of trouble getting hpcboot to
correctly
	load/boot much of anything on my iPAQ, and the symptoms
look very
	much like the bug Uwe fixed about 2 years ago... looks like
I'm
	running out of memory in the currently allocated region(s)
and
	some page is either leaked into or overwritten because it's
been
	handed out more than once.

	Unfortunately in my case it appears to generally be the
bootinfo
	page, which means my 2nd-stage loader jumps to some junk
address
	rather than the start of the kernel.

	It *does* seem related to size of the binary being loaded,
but
	not in a bigger-is-worse way... it's the rounding of the
memory
	use to the 64-k regions that seems to bite me.

	As an example, a slightly bigger than 16k test executable I
built
	which just outputs some stuff to the serial port and spins
still
	hit the rounding condition (it allocated 16 4k-pages, not
sure why
	it needed that many) a vast majority of the time. 
Occasionally
	the memory pages returned by the allocator to hpcboot would
be
	different and it would work, but most of the time it would
fail
	because the start address (and everything else) in the
bootinfo
	page would be trashed by the time it got into the assembly
code.
	The same happened with a couple of test kernels I built
and/or
	sucked off the web... the majority of the time I'd die due
to
	the bootinfo page getting smashed.

	The following is my hack^Wworkaround (for illustration
purposes
	mostly -- it's extracted from a bigger set of changes, so
it may
	not apply cleanly or at all):

	I'm going to dig a little bit more, but thought I'd send a
query
	out in case anybody else has fallen into this hole, and to
troll
	for ideas before I go dive in after the issue again.

Thanks,
--rafal

  - - - 8< - - Cut here - - 8< - -     - - - 8< - -
Cut here - - 8< - - 
Index: hpcboot/arch.cpp
============================================================
=======
RCS file:
/cvsroot/src/sys/arch/hpc/stand/hpcboot/arch.cpp,v
retrieving revision 1.14
diff -u -p -u -p -r1.14 arch.cpp
--- hpcboot/arch.cpp	5 Mar 2006 04:05:39 -0000	1.14
+++ hpcboot/arch.cpp	21 Feb 2008 18:10:43 -0000
 -69,8
+69,8  Architecture::allocateMemory(size_t sz)
 {
 	//binary image.
 	sz = _mem->estimateTaggedPageSize(sz);
-	//pvec + BootArgs + 2 nd bootloader + bootloader stack.
-	sz += _mem->getPageSize() * 4;
+	//pvec + BootArgs + guard page + 2 nd bootloader + guard
page + bootloader stack.
+	sz += _mem->getPageSize() * 6;
 	sz = _mem->roundRegion(sz);
 	return _mem->reservePage(sz);
 }
Index: hpcboot/arm/arm_arch.cpp
============================================================
=======
RCS file:
/cvsroot/src/sys/arch/hpc/stand/hpcboot/arm/arm_arch.cpp,v
retrieving revision 1.6
diff -u -p -u -p -r1.6 arm_arch.cpp
--- hpcboot/arm/arm_arch.cpp	19 Feb 2006 13:04:42 -0000	1.6
+++ hpcboot/arm/arm_arch.cpp	21 Feb 2008 18:26:18 -0000
 -94,8
+94,14  BOOL
 ARMArchitecture::setupLoader()
 {
 	vaddr_t v;
+	vaddr_t p;
 	vsize_t sz = BOOT_FUNC_END - BOOT_FUNC_START;
 
+	// get a guard page...
+	_mem->getPage(v , p);
+	DPRINTF((TEXT("bootloader guard vaddr=0x%08x
paddr=0x%08xn"),
+	    (unsigned)v,(unsigned)p));
+
 	// check 2nd bootloader size.
 	if (sz > _mem->getPageSize()) {
 		DPRINTF((TEXT("2nd bootloader size(%dbyte) is larger
than page size(%d).n"),
 -126,9
+132,16  ARMArchitecture::jump(paddr_t info, padd
 	vaddr_t v;
 	paddr_t p;
 
-	// stack for bootloader
+	// guard page before bootloader stack
+	_mem->getPage(v, p);
+	memset(reinterpret_cast <LPVOID>(v), 0x69,
_mem->getPageSize());
+	DPRINTF((TEXT("guard page for bootloader stack =
%08xn"), p));
+
+	// stack for bootloader 
 	_mem->getPage(v, p);
+	memset(reinterpret_cast <LPVOID>(v), 0x42,
_mem->getPageSize());
 	sp = ptokv(p) + _mem->getPageSize();
+	DPRINTF((TEXT("sp for bootloader = %08xn"),
sp));
 
 	// writeback whole D-cache
 	WritebackDCache();
	from a bigger set of changes so it 
	a much bigger set of changes and I can't
  - - - 8< - - Cut here - - 8< - -     - - - 8< - -
Cut here - - 8< - - 

-- 
  Time is an illusion; lunchtime, doubly so.     |//|     
     Rafal Boni
                   -- Ford Prefect               |//|     
rafalpobox.com

Rafal Boni wrote:
> Folks:
> 	I've been having a lot of trouble getting hpcboot to
correctly
> 	load/boot much of anything on my iPAQ, and the
symptoms look very
> 	much like the bug Uwe fixed about 2 years ago... looks
like I'm
> 	running out of memory in the currently allocated
region(s) and
> 	some page is either leaked into or overwritten because
it's been
> 	handed out more than once.

My latest attempt has tossed the guard pages out the window
and made the 
ELF symbol-loading machinery return better (read: more
conservative) 
estimates of amount of memory required to load the symbols.

The issue appears to be that while the symbol header, symbol
table and 
string table are all loaded in 3 separate passes, the
size-estimation 
code returned the size of all 3 items as a single datum,
ignoring the 
fact that each of those 3 components would need at least one
page (and 
maybe more) to store the contents in the 'load chain'.

Diff attached... comments welcome,
--rafal

Just a minute ago, I wrote:
> Rafal Boni wrote:
>> Folks:
>>     I've been having a lot of trouble getting
hpcboot to correctly
>>     load/boot much of anything on my iPAQ, and the
symptoms look very
>>     much like the bug Uwe fixed about 2 years
ago... looks like I'm
>>     running out of memory in the currently
allocated region(s) and
>>     some page is either leaked into or overwritten
because it's been
>>     handed out more than once.
> 
> My latest attempt has tossed the guard pages out the
window and made the 
> ELF symbol-loading machinery return better (read: more
conservative) 
> estimates of amount of memory required to load the
symbols.
> 
> The issue appears to be that while the symbol header,
symbol table and 
> string table are all loaded in 3 separate passes, the
size-estimation 
> code returned the size of all 3 items as a single
datum, ignoring the 
> fact that each of those 3 components would need at
least one page (and 
> maybe more) to store the contents in the 'load chain'.

In case anyone is itching to try it out, an ARM hpcboot
binary with this 
fix (and a bunch of other, unrelated changes), can be had
at:
	ftp://ftp.netbsd.org/pub/NetBSD/misc/rafal/hpcboot.exe

--rafal

On Wed, Mar 05, 2008 at 21:33:19 -0500, Rafal Boni wrote:

> The issue appears to be that while the symbol header,
symbol table and 
> string table are all loaded in 3 separate passes, the
size-estimation 
> code returned the size of all 3 items as a single
datum, ignoring the 
> fact that each of those 3 components would need at
least one page (and 
> maybe more) to store the contents in the 'load chain'.
> 
> Diff attached... comments welcome,
> --rafal

> Index: hpcboot/load_elf.cpp
>
============================================================
=======
> RCS file:
/cvsroot/src/sys/arch/hpc/stand/hpcboot/load_elf.cpp,v
> retrieving revision 1.17
> diff -u -p -u -p -r1.17 load_elf.cpp
> --- hpcboot/load_elf.cpp	5 Mar 2006 04:04:13
-0000	1.17
> +++ hpcboot/load_elf.cpp	6 Mar 2008 02:01:36 -0000
>  -123,10 +123,6  ElfLoader::memorySize()
>  			sz += _mem->roundPage(filesz);
>  			// compensate for partial last tag
>  			extra += _mem->getTaggedPageSize();
> -			if (filesz < ph->p_memsz)
> -				// compensate for zero clear
> -				extra += _mem->getTaggedPageSize();
> -
>  		}
>  	}

Why have you removed this?  Zero-clear chunk occupies an
extra tagged
page in the chain.


>  -135,8 +131,9  ElfLoader::memorySize()
>  	if (symblk_sz) {
>  		sz += symblk_sz;
>  		DPRINTF((TEXT(" = 0x%x]"), symblk_sz));
> -		// XXX: compensate for partial tags after ELF header
and symtab
> -		extra += 2 * _mem->getTaggedPageSize();
> +		// XXX: compensate for partial tags after ELF
header, symtab
> +		// and strtab
> +		extra += 3 * _mem->getTaggedPageSize();
>  	}

Does it work for you with this hunk alone?


>  	sz += extra;
>  -263,13 +260,17 
ElfLoader::symbol_block_size()
>  	    ROUND4(_sym_blk.shsym->sh_size);
>  	_sym_blk.enable = TRUE;
>  
> -	DPRINTF((TEXT("+[ksyms: header 0x%x, symtab
0x%x, strtab 0x%x"),
> +	DPRINTF((TEXT("+[ksyms: header 0x%x, symtab
0x%x, strtab 0x%x = 0x%x]"),
>  	    _sym_blk.header_size,
_sym_blk.shsym->sh_size,
> -	    _sym_blk.shstr->sh_size));
> +	    _sym_blk.shstr->sh_size, _sym_blk.header_size
+ 
> +	    ROUND4(_sym_blk.shsym->sh_size) +
_sym_blk.shstr->sh_size));

The sum is printed in the caller.  If you print it here, you
need to
remove the printf in the caller.


> -	// return total amount of symbol block
> -	return (_sym_blk.header_size +
ROUND4(_sym_blk.shsym->sh_size) +
> -	    _sym_blk.shstr->sh_size);
> +	// Round each of the three components to page_size
since they're
> +	// loaded as 3 different segments.
> +	return (_mem->roundPage(_sym_blk.header_size) +
>
+		_mem->roundPage(ROUND4(_sym_blk.shsym->sh_size)) +
> +		_mem->roundPage(_sym_blk.shstr->sh_size));
> +	    
>  }

Is these roundPage necessary?  I really don't want to
inflict on
myself the pain of reading and understanding this code
again, but IIRC
extra pages added in the caller are supposed to take care of
this.
Moreover, IIRC, doing roundPage doesn't actually help the
"partial
tag" problem.


I'd prefer we really understand were the overflow occurs
before we
commit anything to this code that is already quite hairy.

SY, Uwe
-- 
uwestderr.spb.ru                       |       Zu Grunde
kommen
http://snark.ptc.spbu.
ru/~uwe/          |       Ist zu Grunde gehen

Valeriy E. Ushakov wrote:
> On Wed, Mar 05, 2008 at 21:33:19 -0500, Rafal Boni
wrote:
> 
>> The issue appears to be that while the symbol
header, symbol table and 
>> string table are all loaded in 3 separate passes,
the size-estimation 
>> code returned the size of all 3 items as a single
datum, ignoring the 
>> fact that each of those 3 components would need at
least one page (and 
>> maybe more) to store the contents in the 'load
chain'.
>>
>> Diff attached... comments welcome,
>> --rafal
> 
>> Index: hpcboot/load_elf.cpp
>>
============================================================
=======
>> RCS file:
/cvsroot/src/sys/arch/hpc/stand/hpcboot/load_elf.cpp,v
>> retrieving revision 1.17
>> diff -u -p -u -p -r1.17 load_elf.cpp
>> --- hpcboot/load_elf.cpp	5 Mar 2006 04:04:13
-0000	1.17
>> +++ hpcboot/load_elf.cpp	6 Mar 2008 02:01:36 -0000
>>  -123,10 +123,6  ElfLoader::memorySize()
>>  			sz += _mem->roundPage(filesz);
>>  			// compensate for partial last tag
>>  			extra += _mem->getTaggedPageSize();
>> -			if (filesz < ph->p_memsz)
>> -				// compensate for zero clear
>> -				extra += _mem->getTaggedPageSize();
>> -
>>  		}
>>  	}
> 
> Why have you removed this?  Zero-clear chunk occupies
an extra tagged
> page in the chain.

I thought this was the case too,  but if you follow the code
/ chain, 
you'll note that they steal from the initial 'pvec' page
allocated at 
the beginning (they just kidnap sizeof(PageTag) since
there's no data to 
store).  So I adjusted for reality.

>>  -135,8 +131,9  ElfLoader::memorySize()
>>  	if (symblk_sz) {
>>  		sz += symblk_sz;
>>  		DPRINTF((TEXT(" = 0x%x]"),
symblk_sz));
>> -		// XXX: compensate for partial tags after ELF
header and symtab
>> -		extra += 2 * _mem->getTaggedPageSize();
>> +		// XXX: compensate for partial tags after ELF
header, symtab
>> +		// and strtab
>> +		extra += 3 * _mem->getTaggedPageSize();
>>  	}
> 
> Does it work for you with this hunk alone?

I haven't tried just that one -- though even if it works, it
seems a 
little like a rubber-chickens and voodoo-sticks change ;). 
But I'll 
give it a try and report back in any case..

>>  	sz += extra;
>>  -263,13 +260,17 
ElfLoader::symbol_block_size()
>>  	    ROUND4(_sym_blk.shsym->sh_size);
>>  	_sym_blk.enable = TRUE;
>>  
>> -	DPRINTF((TEXT("+[ksyms: header 0x%x, symtab
0x%x, strtab 0x%x"),
>> +	DPRINTF((TEXT("+[ksyms: header 0x%x, symtab
0x%x, strtab 0x%x = 0x%x]"),
>>  	    _sym_blk.header_size,
_sym_blk.shsym->sh_size,
>> -	    _sym_blk.shstr->sh_size));
>> +	    _sym_blk.shstr->sh_size,
_sym_blk.header_size + 
>> +	    ROUND4(_sym_blk.shsym->sh_size) +
_sym_blk.shstr->sh_size));
> 
> The sum is printed in the caller.  If you print it
here, you need to
> remove the printf in the caller.

Oops, I thought I had done that; will update, thanks.

>> -	// return total amount of symbol block
>> -	return (_sym_blk.header_size +
ROUND4(_sym_blk.shsym->sh_size) +
>> -	    _sym_blk.shstr->sh_size);
>> +	// Round each of the three components to
page_size since they're
>> +	// loaded as 3 different segments.
>> +	return (_mem->roundPage(_sym_blk.header_size)
+
>>
+		_mem->roundPage(ROUND4(_sym_blk.shsym->sh_size)) +
>>
+		_mem->roundPage(_sym_blk.shstr->sh_size));
>> +	    
>>  }
> 
> Is these roundPage necessary?  I really don't want to
inflict on
> myself the pain of reading and understanding this code
again, but IIRC
> extra pages added in the caller are supposed to take
care of this.
> Moreover, IIRC, doing roundPage doesn't actually help
the "partial
> tag" problem.

I think this is the crux of the problem, and yeah, I think
it's 
necessary.  If you look at what
ElfLoader::load_symbol_block() does, it 
loads (a) header, (b) symbol table, and (c) string table as
individual 
segments, which means each will start on a new page in the
tag chain.

So if you have e.g. 1320 + 1290 + 1350 bytes in those 3,
before we'd 
return 1320 + ROUND4(1290) = 1292 + 1350 = 3962, which would
look like 
it would fit in a single page (even in a single tagged
page), but would 
actually require *3* tagged pages since each component would
get it's 
own link (== tagged page) in the tag chain.

AAs for the 'partial tag' issue, I'm also not sure off the
top of my 
head, but given the gyrations Architecture::allocateMemory
goes through 
to convert bytes-needed-in-memory to tagged-pages-needed,
I'd think as 
long as we rounded up all segments to the next unit of
tagged-page-size 
(since after all that's what matters, not actual HW page
size), there 
should be *no* page unaccounted for.  Rounding up to HW page
size is 
maybe a little sloppy, but should give more *conservative*
estimates, 
which from our POV is OK (after all, it's going to get
rounded up to the 
next chunk of 64k anyway when we allocate pages from
WinCE).

> I'd prefer we really understand were the overflow
occurs before we
> commit anything to this code that is already quite
hairy.

I'm all for that, which is why I'm sending this to the list
rather than 
checking in... but I also want to minimize the amount of
damage my 
forehead takes from beating it against this too much, and in
the end I 
want something which works at least semi-reliably -- and
this hasn't 
been the case with the hpcboot built from unmodified
sources.

Thanks,
--rafal

Valeriy E. Ushakov wrote:
>>  -135,8 +131,9  ElfLoader::memorySize()
>>  	if (symblk_sz) {
>>  		sz += symblk_sz;
>>  		DPRINTF((TEXT(" = 0x%x]"),
symblk_sz));
>> -		// XXX: compensate for partial tags after ELF
header and symtab
>> -		extra += 2 * _mem->getTaggedPageSize();
>> +		// XXX: compensate for partial tags after ELF
header, symtab
>> +		// and strtab
>> +		extra += 3 * _mem->getTaggedPageSize();
>>  	}
> 
> Does it work for you with this hunk alone?

Only sometimes; it worked loading a ~ 2.8MB kernel once, but
then it 
died in the same 'entrypoint gets overwritten' way loading
my little 16K 
test executable.  With the whole mess of changes I haven't
had a failure 
yet (both booting real kernels and booting my test
executable).

--rafal

On Thu, Mar 06, 2008 at 08:52:02 -0500, Rafal Boni wrote:

> >>--- hpcboot/load_elf.cpp	5 Mar 2006 04:04:13
-0000	1.17
> >>+++ hpcboot/load_elf.cpp	6 Mar 2008 02:01:36
-0000
> >> -123,10 +123,6  ElfLoader::memorySize()
> >> 			sz += _mem->roundPage(filesz);
> >> 			// compensate for partial last tag
> >> 			extra += _mem->getTaggedPageSize();
> >>-			if (filesz < ph->p_memsz)
> >>-				// compensate for zero clear
> >>-				extra += _mem->getTaggedPageSize();
> >>-
> >> 		}
> >> 	}
> >
> >Why have you removed this?  Zero-clear chunk
occupies an extra tagged
> >page in the chain.
> 
> I thought this was the case too,  but if you follow the
code / chain, 
> you'll note that they steal from the initial 'pvec'
page allocated at 
> the beginning (they just kidnap sizeof(PageTag) since
there's no data to 
> store).  So I adjusted for reality.

Well, my memory is hazy and the way page allocation is
managed is a
bit contorted, but my reading of _load_segment is that we
burn a whole
tagged page for zero-clear.  And that extra you've deleted
was added
there exactly to force an extra tagged page to be allocated
for that
zero-clear.  Cf. boot_func at the end of sh3/sh_arch.h.




> >> -135,8 +131,9  ElfLoader::memorySize()
> >> 	if (symblk_sz) {
> >> 		sz += symblk_sz;
> >> 		DPRINTF((TEXT(" = 0x%x]"),
symblk_sz));
> >>-		// XXX: compensate for partial tags after
ELF header and 
> >>symtab
> >>-		extra += 2 * _mem->getTaggedPageSize();
> >>+		// XXX: compensate for partial tags after
ELF header, symtab
> >>+		// and strtab
> >>+		extra += 3 * _mem->getTaggedPageSize();
> >> 	}
> >
> >Does it work for you with this hunk alone?
> 
> I haven't tried just that one -- though even if it
works, it seems a 
> little like a rubber-chickens and voodoo-sticks change
;).  But I'll 
> give it a try and report back in any case..
[...]
> >>-	// return total amount of symbol block
> >>-	return (_sym_blk.header_size +
ROUND4(_sym_blk.shsym->sh_size) +
> >>-	    _sym_blk.shstr->sh_size);
> >>+	// Round each of the three components to
page_size since they're
> >>+	// loaded as 3 different segments.
> >>+	return
(_mem->roundPage(_sym_blk.header_size) +
>
>>+		_mem->roundPage(ROUND4(_sym_blk.shsym->sh_s
ize)) +
>
>>+		_mem->roundPage(_sym_blk.shstr->sh_size));
> >>+	    
> >> }
> >
> >Is these roundPage necessary?  I really don't want
to inflict on
> >myself the pain of reading and understanding this
code again, but IIRC
> >extra pages added in the caller are supposed to
take care of this.
> >Moreover, IIRC, doing roundPage doesn't actually
help the "partial
> >tag" problem.
> 
> I think this is the crux of the problem, and yeah, I
think it's 
> necessary.  If you look at what
ElfLoader::load_symbol_block() does, it 
> loads (a) header, (b) symbol table, and (c) string
table as individual 
> segments, which means each will start on a new page in
the tag chain.
> 
> So if you have e.g. 1320 + 1290 + 1350 bytes in those
3, before we'd 
> return 1320 + ROUND4(1290) = 1292 + 1350 = 3962, which
would look like 
> it would fit in a single page (even in a single tagged
page), but would 
> actually require *3* tagged pages since each component
would get it's 
> own link (== tagged page) in the tag chain.

But then the caller throws in two extra pages into the
calculation to
accomdate the "gaps" induced by each of the above
being allocated from
a fresh tagged page, so it's:

    1320 + tsz + 1292 + tsz + 1350

and that rounds to 3 pages (see estimateTaggedPageSize) as
expected.
Even if each of the above is just 1 byte, the extra will
still pad it
so that at least three tagged pages are allocated.

The rule of thumb is - the caller adds a page to the
"extra" for every
potential partial tagged page:

	. last partial page of each segment
	. zero-clear page for each segment if necessary
	. elf header
	. symbol table

As string table is last, there's no gap and so no extra is
added for
it.

I wonder if we don't account for some otehr partial tag
elsewhere.


> As for the 'partial tag' issue, I'm also not sure off
the top of my 
> head, but given the gyrations
Architecture::allocateMemory goes through 
> to convert bytes-needed-in-memory to
tagged-pages-needed, I'd think as 
> long as we rounded up all segments to the next unit of
tagged-page-size 
> (since after all that's what matters, not actual HW
page size), there 
> should be *no* page unaccounted for.  Rounding up to HW
page size is 
> maybe a little sloppy, but should give more
*conservative* estimates, 
> which from our POV is OK (after all, it's going to get
rounded up to the 
> next chunk of 64k anyway when we allocate pages from
WinCE).

Well the "extra" provides just that by
conservatively forcing an extra
tagged page to be allocated for every place we might have a
partial
tagged page caused by next segment &co starting from the
new tagged
page.  This should have the same effect as rounding, except
for some
cases where rounding will force two extra pages to be
allocated
(e.g. last page is full except for the last 16 bytes
(sizeof(PageTag))
or less - with rounding you will allocate two extra tagged
pages to
"hold" the extra space instead of one).


> >I'd prefer we really understand were the overflow
occurs before we
> >commit anything to this code that is already quite
hairy.
> 
> I'm all for that, which is why I'm sending this to the
list rather than 
> checking in... but I also want to minimize the amount
of damage my 
> forehead takes from beating it against this too much,
and in the end I 
> want something which works at least semi-reliably --
and this hasn't 
> been the case with the hpcboot built from unmodified
sources.

Why don't you enable the debugging printfs (there an option
to dump
page chains) and find where does the overflow occur?


SY, Uwe
-- 
uwestderr.spb.ru                       |       Zu Grunde
kommen
http://snark.ptc.spbu.
ru/~uwe/          |       Ist zu Grunde gehen

In a state of confusion, I asserted thusly:
> Rafal Boni wrote:
> >Folks:
> >	I've been having a lot of trouble getting hpcboot
to correctly
> >	load/boot much of anything on my iPAQ, and the
symptoms look very
> >	much like the bug Uwe fixed about 2 years ago...
looks like I'm
> >	running out of memory in the currently allocated
region(s) and
> >	some page is either leaked into or overwritten
because it's been
> >	handed out more than once.
> 
> My latest attempt has tossed the guard pages out the
window and made the 
> ELF symbol-loading machinery return better (read: more
conservative) 
> estimates of amount of memory required to load the
symbols.

Actually, this was all highly un-necessary voodoo....

My biggest problem was that I had enabled the serial-port
debug code in the
2nd-stage bootloader, which was causing all the havoc by
making the stack
grow up rather than down when it attempted to preserve the
two registers it
trashed... D'oh!  As you might imagine, that doesn't work so
well when you
set the initial stack pointer to just below the bootinfo
page.

Just pretend you didn't see any of the patches I sent ;)...
I'll report here
again if I find more/other problems.

Sorry for all the noise,
--rafal

-- 
  Time is an illusion; lunchtime, doubly so.     |//|     
     Rafal Boni
                   -- Ford Prefect               |//|     
rafalpobox.com