calculation overflow in grub_mm_init_region

calculation overflow in grub_mm_init_region

[Leif Lindholm]

When allocating memory for the heap on ARMv7 UEFI, the init code
pretty much just allocates a chunk from the top of available RAM.

This means that when grub_mm_init_region is called for a region
extending to the top of the 32-bit address space, addr + size == 0.
However, this is not taken into account by arithmetic in this
function, causing Grub to fail on one of my platforms[1] before
"Welcome to GRUB".

Having some trouble getting my head around the grub_mm_init_region
code right now (where is grub_mm_base initialised?), so don't have
a patch.

/
    Leif

[1] Versatile Express V2P-CA15_A7, also known as TC2, has 2GB of RAM
    starting at 0x80000000.  

Re: calculation overflow in grub_mm_init_region (patch)

[Leif Lindholm]

On Thu, Aug 29, 2013 at 07:26:03PM +0200, Leif Lindholm wrote:
> When allocating memory for the heap on ARMv7 UEFI, the init code
> pretty much just allocates a chunk from the top of available RAM.
> 
> This means that when grub_mm_init_region is called for a region
> extending to the top of the 32-bit address space, addr + size == 0.
> However, this is not taken into account by arithmetic in this
> function, causing Grub to fail on one of my platforms[1] before
> "Welcome to GRUB".
> 
> Having some trouble getting my head around the grub_mm_init_region
> code right now (where is grub_mm_base initialised?), so don't have
> a patch.

So, sat down to dissect the code a bit, and turns out that apart from
a debug message (which is #ifdef 0 by default), grub_mm_init_region()
is actually innocent.

The error lies in get_header_from_pointer() (also kern/mm.c), and its
comparisons regarding whether a pointer lies within the current
region or not.

My suggested fix is as follows (with a little bit of refactoring to
help my brain).

/
    Leif

=== modified file 'grub-core/kern/mm.c'
--- grub-core/kern/mm.c 2013-04-20 15:39:49 +0000
+++ grub-core/kern/mm.c 2013-09-10 11:13:36 +0000
@@ -86,13 +86,20 @@
 static void
 get_header_from_pointer (void *ptr, grub_mm_header_t *p, grub_mm_region_t *r)
 {
+  grub_addr_t block_start = (grub_addr_t) ptr;
+
   if ((grub_addr_t) ptr & (GRUB_MM_ALIGN - 1))
     grub_fatal ("unaligned pointer %p", ptr);
 
   for (*r = grub_mm_base; *r; *r = (*r)->next)
-    if ((grub_addr_t) ptr > (grub_addr_t) ((*r) + 1)
-       && (grub_addr_t) ptr <= (grub_addr_t) ((*r) + 1) + (*r)->size)
-      break;
+    {
+      grub_addr_t region_start = (grub_addr_t) ((*r) + 1);
+      grub_addr_t region_end = (grub_addr_t) ((*r) + 1) + (*r)->size;
+
+      if (block_start > region_start)
+       if ((block_start <= region_end) || (region_end == 0))
+         break;
+    }
 
   if (! *r)
     grub_fatal ("out of range pointer %p", ptr);

Re: calculation overflow in grub_mm_init_region (patch)

[Seth Goldberg]

Quoting Leif Lindholm, who wrote the following on Tue, 10 Sep 2013:

> On Thu, Aug 29, 2013 at 07:26:03PM +0200, Leif Lindholm wrote:
>> When allocating memory for the heap on ARMv7 UEFI, the init code
>> pretty much just allocates a chunk from the top of available RAM.
>>
>> This means that when grub_mm_init_region is called for a region
>> extending to the top of the 32-bit address space, addr + size == 0.
>> However, this is not taken into account by arithmetic in this
>> function, causing Grub to fail on one of my platforms[1] before
>> "Welcome to GRUB".
>>
>> Having some trouble getting my head around the grub_mm_init_region
>> code right now (where is grub_mm_base initialised?), so don't have
>> a patch.
>
> So, sat down to dissect the code a bit, and turns out that apart from
> a debug message (which is #ifdef 0 by default), grub_mm_init_region()
> is actually innocent.
>
> The error lies in get_header_from_pointer() (also kern/mm.c), and its
> comparisons regarding whether a pointer lies within the current
> region or not.
>
> My suggested fix is as follows (with a little bit of refactoring to
> help my brain).
>
> /
>    Leif
>
> === modified file 'grub-core/kern/mm.c'
> --- grub-core/kern/mm.c 2013-04-20 15:39:49 +0000
> +++ grub-core/kern/mm.c 2013-09-10 11:13:36 +0000
> @@ -86,13 +86,20 @@
> static void
> get_header_from_pointer (void *ptr, grub_mm_header_t *p, grub_mm_region_t *r)
> {
> +  grub_addr_t block_start = (grub_addr_t) ptr;
> +
>   if ((grub_addr_t) ptr & (GRUB_MM_ALIGN - 1))
>     grub_fatal ("unaligned pointer %p", ptr);
>
>   for (*r = grub_mm_base; *r; *r = (*r)->next)
> -    if ((grub_addr_t) ptr > (grub_addr_t) ((*r) + 1)
> -       && (grub_addr_t) ptr <= (grub_addr_t) ((*r) + 1) + (*r)->size)
> -      break;
> +    {
> +      grub_addr_t region_start = (grub_addr_t) ((*r) + 1);
> +      grub_addr_t region_end = (grub_addr_t) ((*r) + 1) + (*r)->size;
> +
> +      if (block_start > region_start)
> +       if ((block_start <= region_end) || (region_end == 0))


   Why would region_end be zero?  That sounds like an invalid value.

  --S

Re: calculation overflow in grub_mm_init_region (patch)

[Leif Lindholm]

On 10 September 2013 22:46, Seth Goldberg <seth.goldberg@oracle.com> wrote:
>   Why would region_end be zero?  That sounds like an invalid value.

Because when a heap region sits at the top of RAM, region base +
region size == 0.

/
    Leif

Re: calculation overflow in grub_mm_init_region (patch)

[Leif Lindholm]

On 10 September 2013 23:36, Leif Lindholm <leif.lindholm@linaro.org> wrote:
> On 10 September 2013 22:46, Seth Goldberg <seth.goldberg@oracle.com> wrote:
>>   Why would region_end be zero?  That sounds like an invalid value.
>
> Because when a heap region sits at the top of RAM, region base +
> region size == 0.

(On that specific platform. In general, when it sits at the top of
addressable memory.)

/
    Leif

Re: calculation overflow in grub_mm_init_region (patch)

[Seth Goldberg]

On Sep 10, 2013, at 3:36 PM, Leif Lindholm <leif.lindholm@linaro.org> wrote:

> On 10 September 2013 22:46, Seth Goldberg <seth.goldberg@oracle.com> wrote:
>>  Why would region_end be zero?  That sounds like an invalid value.
> 
> Because when a heap region sits at the top of RAM, region base +
> region size == 0.

  So, an overflow.  Ugh.  Reserving the last 4k would be fine, too, yes.

  --S


> 
> /
>    Leif
> 
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> https://lists.gnu.org/mailman/listinfo/grub-devel

Re: calculation overflow in grub_mm_init_region (patch)

[Vladimir 'φ-coder/phcoder' Serbinenko]

[-- Attachment #1: Type: text/plain, Size: 839 bytes --]


>    for (*r = grub_mm_base; *r; *r = (*r)->next)
> -    if ((grub_addr_t) ptr > (grub_addr_t) ((*r) + 1)
> -       && (grub_addr_t) ptr <= (grub_addr_t) ((*r) + 1) + (*r)->size)
> -      break;
> +    {
> +      grub_addr_t region_start = (grub_addr_t) ((*r) + 1);
> +      grub_addr_t region_end = (grub_addr_t) ((*r) + 1) + (*r)->size;
> +
> +      if (block_start > region_start)
> +       if ((block_start <= region_end) || (region_end == 0))
> +         break;
> +    }
This fix looks correct but as indicated by us not having discovered this
bug earlier, this is a very unusual case and it's difficult to ensure
that similar bug doesn't pop up in another place or that we don't suffer
a regression. I'd prefer to exclude top 4K of adressable memory from
heap as safety measure. Are you ok with this approach?



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 291 bytes --]

Re: calculation overflow in grub_mm_init_region (patch)

[Leif Lindholm]

On 11 September 2013 02:00, Vladimir 'φ-coder/phcoder' Serbinenko
<phcoder@gmail.com> wrote:
> This fix looks correct but as indicated by us not having discovered this
> bug earlier, this is a very unusual case and it's difficult to ensure
> that similar bug doesn't pop up in another place or that we don't suffer
> a regression. I'd prefer to exclude top 4K of adressable memory from
> heap as safety measure. Are you ok with this approach?

I am happy with that.

/
    Leif