[PATCH] more intelligent cbfs walker

[Patrick Georgi]

Hi,

attached patch makes the CBFS file lookup skip file data instead of brute-
forcing its way through it, looking for magic numbers.
For one, it should speed up file access, esp. with many entries, but it also 
helps against false positives (eg. seabios, which contains the magic number 
for its own CBFS support, which _might_ just be aligned properly)

Signed-off-by: Patrick Georgi

[Myles Watson]

On Sat, Apr 25, 2009 at 2:44 AM, Patrick Georgi  wrote:
> Hi,
>
> attached patch makes the CBFS file lookup skip file data instead of brute-
> forcing its way through it, looking for magic numbers.
> For one, it should speed up file access, esp. with many entries, but it also
> helps against false positives (eg. seabios, which contains the magic number
> for its own CBFS support, which _might_ just be aligned properly)
>
> Signed-off-by: Patrick Georgi

I'd prefer that it used the ALIGN macro, but it's a pretty trivial
macro.  It just makes it more clear.

Either way:
Acked-by: Myles Watson

Thanks,
Myles

[Patrick Georgi]

Am 25.04.2009 14:14, schrieb Myles Watson:
> I'd prefer that it used the ALIGN macro, but it's a pretty trivial
> macro.  It just makes it more clear.

Beware, this patch might create an infinite loop.
Attached patch avoids the infinite loop, ends lookup on invalid magic 
(we can do this now), and uses ALIGN.
Other than the original patch this one is only compile tested, so please 
test.

Signed-off-by: Patrick Georgi

[Myles Watson]

On Sat, Apr 25, 2009 at 6:42 AM, Patrick Georgi  wrote:
> Am 25.04.2009 14:14, schrieb Myles Watson:
> > I'd prefer that it used the ALIGN macro, but it's a pretty trivial
> > macro.  It just makes it more clear.
>
> Beware, this patch might create an infinite loop.
> Attached patch avoids the infinite loop, ends lookup on invalid magic (we
> can do this now), and uses ALIGN.
> Other than the original patch this one is only compile tested, so please
> test.

I won't be able to until Monday, but I have a couple of comments/questions.
> Signed-off-by: Patrick Georgi

+	int align= ntohl(header->align);
+
    while(1) {
    	struct cbfs_file *file = (struct cbfs_file *) offset;
-		if (cbfs_check_magic(file)) printk_info("Check %s\n", CBFS_NAME(file));
-		if (cbfs_check_magic(file) &&
-		    !strcmp(CBFS_NAME(file), name))
+		if (!cbfs_check_magic(file)) return NULL;
+		printk_info("Check %s\n", CBFS_NAME(file));
+		if (!strcmp(CBFS_NAME(file), name))
    		return file;

-		offset += ntohl(header->align);
+		int flen = ntohl(file->len);
+		int foffset = ntohl(file->offset);
+		printk_spew("CBFS: follow chain: %p + %x + %x + align -> ", offset,
foffset, flen);

+		unsigned long oldoffset = offset;
+		offset = ALIGN(offset + foffset + flen, align);
+		printk_spew("%p\n", offset);
+		if (offset == oldoffset) return NULL;
Why do we have this check?  Is there a time when offset ==
ALIGN(offset + foffset + flen, align)?
+
    	if (offset < 0xFFFFFFFF - ntohl(header->romsize))
    		return NULL;
I know this line isn't part of your change, but shouldn't we check
that we're within the file system, not just within the flash?
    }

Thanks,
Myles

[Patrick Georgi]

Am 25.04.2009 14:53, schrieb Myles Watson:
> unsigned long oldoffset = offset;
> offset = ALIGN(offset + foffset + flen, align);
> printk_spew("%p\n", offset);
> if (offset == oldoffset) return NULL;
>
> Why do we have this check?  Is there a time when offset ==
> ALIGN(offset + foffset + flen, align)?

offset == ALIGN(offset + 0 + 0, align) // offset is already aligned

If, for some twisted reason, right after the last file, there's a CBFS 
file magic, and otherwise zeroes (and offset is already aligned, which 
it should be), you end up in an endless loop. This test ends it.
> if (offset<  0xFFFFFFFF - ntohl(header->romsize))
>   	return NULL;
>
> I know this line isn't part of your change, but shouldn't we check
> that we're within the file system, not just within the flash?

Good idea. Another issue, another patch.

Patrick

[Myles Watson]

> -----Original Message-----
> From: Patrick Georgi [mailto:[e-mail]]
> Sent: Saturday, April 25, 2009 6:57 AM
> To: Myles Watson
> Cc: [e-mail]
> Subject: Re: [coreboot] [PATCH] more intelligent cbfs walker
>
> Am 25.04.2009 14:53, schrieb Myles Watson:
> > unsigned long oldoffset = offset;
> > offset = ALIGN(offset + foffset + flen, align);
> > printk_spew("%p\n", offset);
> > if (offset == oldoffset) return NULL;
> >
> > Why do we have this check?  Is there a time when offset ==
> > ALIGN(offset + foffset + flen, align)?
>
> offset == ALIGN(offset + 0 + 0, align) // offset is already aligned
>
> If, for some twisted reason, right after the last file, there's a CBFS
> file magic, and otherwise zeroes (and offset is already aligned, which
> it should be), you end up in an endless loop. This test ends it.

OK.  I think that would be more clear if we tested foffset.  How about 
if (foffset == 0) /* Invalid CBFS entry that would cause an infinite loop */
    return NULL;

Or we could just test foffset when we test the magic number.
> > if (offset<  0xFFFFFFFF - ntohl(header->romsize))
> >   	return NULL;
> >
> > I know this line isn't part of your change, but shouldn't we check
> > that we're within the file system, not just within the flash?
>
> Good idea. Another issue, another patch.

Sure.

Thanks,
Myles

[Patrick Georgi]

Am 25.04.2009 15:06, schrieb Myles Watson:
> OK. I think that would be more clear if we tested foffset. How about
> if (foffset == 0) /* Invalid CBFS entry that would cause an infinite loop */
>    return NULL;
>
> Or we could just test foffset when we test the magic number.

The problem is that we can't trust _anything_ in that array: there's no 
final entry in the chain, so the data after that is garbage.
You still have an endless loop for (foffset == 4) && (flen == -4)
We could do
if (foffset + flen == 0) return NULL;
but I wonder why we shouldn't just do the full test then, with some 
comment to the same effect as yours above.

Patrick

[Myles Watson]

> -----Original Message-----
> From: Patrick Georgi [mailto:[e-mail]]
> Sent: Saturday, April 25, 2009 7:16 AM
> To: Myles Watson
> Cc: [e-mail]
> Subject: Re: [coreboot] [PATCH] more intelligent cbfs walker
>
> Am 25.04.2009 15:06, schrieb Myles Watson:
> > OK. I think that would be more clear if we tested foffset. How about
> > if (foffset == 0) /* Invalid CBFS entry that would cause an infinite
>
> loop */
> > return NULL;
> >
> > Or we could just test foffset when we test the magic number.
>
> The problem is that we can't trust _anything_ in that array: there's no
> final entry in the chain, so the data after that is garbage.
> You still have an endless loop for (foffset == 4) && (flen == -4)
> We could do
> if (foffset + flen == 0) return NULL;
> but I wonder why we shouldn't just do the full test then, with some
> comment to the same effect as yours above.

I can see your point, but CBFS design assumes that CBFS magic is sufficient.
We know how large the file system is, and any entry inside it was created by
a CBFS tool.  If we really want to be paranoid, you need to check that
offset > oldoffset so that you don't get a negative foffset.

Myles

[Patrick Georgi]

Am 25.04.2009 15:22, schrieb Myles Watson:
> I can see your point, but CBFS design assumes that CBFS magic is sufficient.

So if seabios was in the image, then deleted, and a smaller payload is 
added, and the first surviving bytes of the old seabios image are part 
of its cbfs walker (which includes the magic)?
> We know how large the file system is, and any entry inside it was created by
> a CBFS tool.  If we really want to be paranoid, you need to check that
> offset>  oldoffset so that you don't get a negative foffset.

True.

Patrick

[Myles Watson]

> -----Original Message-----
> From: Patrick Georgi [mailto:[e-mail]]
> Sent: Saturday, April 25, 2009 8:24 AM
> To: Myles Watson
> Cc: [e-mail]
> Subject: Re: [coreboot] [PATCH] more intelligent cbfs walker
>
> Am 25.04.2009 15:22, schrieb Myles Watson:
> > I can see your point, but CBFS design assumes that CBFS magic is
>
> sufficient.
> >
>
> So if seabios was in the image, then deleted, and a smaller payload is
> added, and the first surviving bytes of the old seabios image are part
> of its cbfs walker (which includes the magic)?

Have you seen this happen?  If so delete is broken.  Delete zeroes freed
space.

Thanks for fixing this,

Myles

[Patrick Georgi]

Am 25.04.2009 17:10, schrieb Myles Watson:
> Have you seen this happen? If so delete is broken. Delete zeroes freed
> space.

Can we be sure to have only one implementation that writes cbfs?

I've seen quite some weird stuff happen (for example, the first version 
of the patch should _always_ end up in an infinite loop, but it didn't 
at first), and given that this part of the code can make the difference 
between "works" and "hangs with black screen", I'll rather be paranoid 
about these issues.

[Myles Watson]

> -----Original Message-----
> From: Patrick Georgi [mailto:[e-mail]]
> Sent: Saturday, April 25, 2009 9:20 AM
> To: Myles Watson
> Cc: [e-mail]
> Subject: Re: [coreboot] [PATCH] more intelligent cbfs walker
>
> Am 25.04.2009 17:10, schrieb Myles Watson:
> > Have you seen this happen? If so delete is broken. Delete zeroes freed
> > space.
>
> Can we be sure to have only one implementation that writes cbfs?

I hope so, but you're right it's not guaranteed right now.
> I've seen quite some weird stuff happen (for example, the first version
> of the patch should _always_ end up in an infinite loop, but it didn't
> at first), and given that this part of the code can make the difference
> between "works" and "hangs with black screen", I'll rather be paranoid
> about these issues.

Well when you put it that way :)  My only concern is that if we get too
paranoid it gets harder to maintain and test all of the code paths.  Thanks
for your patch.  It was definitely an improvement.

Myles

[Stefan Reinauer]

On 25.04.2009 14:42 Uhr, Patrick Georgi wrote:
> Am 25.04.2009 14:14, schrieb Myles Watson:
> > I'd prefer that it used the ALIGN macro, but it's a pretty trivial
> > macro.  It just makes it more clear.
>
> Beware, this patch might create an infinite loop.
> Attached patch avoids the infinite loop, ends lookup on invalid magic
> (we can do this now), and uses ALIGN.
> Other than the original patch this one is only compile tested, so
> please test.
>
> Signed-off-by: Patrick Georgi

Acked-by: Stefan Reinauer