[PATCH] efi: fix boundary checking in efi_high_alloc()

[PATCH] efi: fix boundary checking in efi_high_alloc()

[Yinghai Lu]

While adding support loading kernel and initrd above 4G to grub2 in legacy
mode, I was referring to efi_high_alloc().
That will allocate buffer for kernel and then initrd, and initrd will
use kernel buffer start as limit.

During testing found two buffers will be overlapped when initrd size is
very big like 400M.

It turns out efi_high_alloc() boundary checking is not right.
end - size will be the new start, and should not compare new
start with max, we need to make sure end is smaller than max.

Signed-off-by: Yinghai Lu <yinghai-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org>

---
 drivers/firmware/efi/libstub/efi-stub-helper.c |    8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

Index: linux-2.6/drivers/firmware/efi/libstub/efi-stub-helper.c
===================================================================
--- linux-2.6.orig/drivers/firmware/efi/libstub/efi-stub-helper.c
+++ linux-2.6/drivers/firmware/efi/libstub/efi-stub-helper.c
@@ -183,12 +183,12 @@ again:
 		start = desc->phys_addr;
 		end = start + desc->num_pages * (1UL << EFI_PAGE_SHIFT);
 
-		if ((start + size) > end || (start + size) > max)
-			continue;
-
-		if (end - size > max)
+		if (end > max)
 			end = max;
 
+		if ((start + size) > end)
+			continue;
+
 		if (round_down(end - size, align) < start)
 			continue;
 

[PATCH] efi: fix boundary checking in efi_high_alloc()

[Yinghai Lu]

While adding support loading kernel and initrd above 4G to grub2 in legacy
mode, I was referring to efi_high_alloc().
That will allocate buffer for kernel and then initrd, and initrd will
use kernel buffer start as limit.

During testing found two buffers will be overlapped when initrd size is
very big like 400M.

It turns out efi_high_alloc() boundary checking is not right.
end - size will be the new start, and should not compare new
start with max, we need to make sure end is smaller than max.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>

---
 drivers/firmware/efi/libstub/efi-stub-helper.c |    8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

Index: linux-2.6/drivers/firmware/efi/libstub/efi-stub-helper.c
===================================================================
--- linux-2.6.orig/drivers/firmware/efi/libstub/efi-stub-helper.c
+++ linux-2.6/drivers/firmware/efi/libstub/efi-stub-helper.c
@@ -183,12 +183,12 @@ again:
 		start = desc->phys_addr;
 		end = start + desc->num_pages * (1UL << EFI_PAGE_SHIFT);
 
-		if ((start + size) > end || (start + size) > max)
-			continue;
-
-		if (end - size > max)
+		if (end > max)
 			end = max;
 
+		if ((start + size) > end)
+			continue;
+
 		if (round_down(end - size, align) < start)
 			continue;
 

Re: [PATCH] efi: fix boundary checking in efi_high_alloc()

[Matt Fleming]

On Thu, 19 Feb, at 08:18:03PM, Yinghai Lu wrote:
> While adding support loading kernel and initrd above 4G to grub2 in legacy
> mode, I was referring to efi_high_alloc().
> That will allocate buffer for kernel and then initrd, and initrd will
> use kernel buffer start as limit.
> 
> During testing found two buffers will be overlapped when initrd size is
> very big like 400M.
> 
> It turns out efi_high_alloc() boundary checking is not right.
> end - size will be the new start, and should not compare new
> start with max, we need to make sure end is smaller than max.
> 
> Signed-off-by: Yinghai Lu <yinghai-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org>
> 
> ---
>  drivers/firmware/efi/libstub/efi-stub-helper.c |    8 ++++----
>  1 file changed, 4 insertions(+), 4 deletions(-)

The patch looks fine but this changelog could do with some finessing
because I spent 30 minutes trying to understand what the bug was, and
more specifically, what values to feed into the allocation algorithm to
trigger it.

Basically, with the current efi_high_alloc() code it's possible to
allocate memory above 'max', because efi_high_alloc() doesn't check that
the tail of the allocation is below 'max'.

If you have an EFI memory map with a single entry that looks like so,

 [0xc0000000-0xc0004000]

And want to allocate 0x3000 bytes below 0xc0003000 the current code will
allocate [0xc0001000-0xc0004000], not [0xc0000000-0xc0003000] like you
would expect.

I've queued up the below patch. If the Linaro/ARM gang could test it out
I'd really appreciate it.

---

>From 1e7295b5d4c5226a160a9167e61b581e388f7f9a Mon Sep 17 00:00:00 2001
From: Yinghai Lu <yinghai-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org>
Date: Thu, 19 Feb 2015 20:18:03 -0800
Subject: [PATCH] efi/libstub: Fix boundary checking in efi_high_alloc()

While adding support loading kernel and initrd above 4G to grub2 in legacy
mode, I was referring to efi_high_alloc().
That will allocate buffer for kernel and then initrd, and initrd will
use kernel buffer start as limit.

During testing found two buffers will be overlapped when initrd size is
very big like 400M.

It turns out efi_high_alloc() boundary checking is not right.
end - size will be the new start, and should not compare new
start with max, we need to make sure end is smaller than max.

[ Basically, with the current efi_high_alloc() code it's possible to
  allocate memory above 'max', because efi_high_alloc() doesn't check
  that the tail of the allocation is below 'max'.

  If you have an EFI memory map with a single entry that looks like so,

   [0xc0000000-0xc0004000]

  And want to allocate 0x3000 bytes below 0xc0003000 the current code
  will allocate [0xc0001000-0xc0004000], not [0xc0000000-0xc0003000]
  like you would expect. - Matt ]

Signed-off-by: Yinghai Lu <yinghai-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org>
Cc: <stable-u79uwXL29TY76Z2rM5mHXA@public.gmane.org>
Signed-off-by: Matt Fleming <matt.fleming-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org>
---
 drivers/firmware/efi/libstub/efi-stub-helper.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/drivers/firmware/efi/libstub/efi-stub-helper.c b/drivers/firmware/efi/libstub/efi-stub-helper.c
index 9bd9fbb5bea8..c927bccd92bd 100644
--- a/drivers/firmware/efi/libstub/efi-stub-helper.c
+++ b/drivers/firmware/efi/libstub/efi-stub-helper.c
@@ -170,12 +170,12 @@ again:
 		start = desc->phys_addr;
 		end = start + desc->num_pages * (1UL << EFI_PAGE_SHIFT);
 
-		if ((start + size) > end || (start + size) > max)
-			continue;
-
-		if (end - size > max)
+		if (end > max)
 			end = max;
 
+		if ((start + size) > end)
+			continue;
+
 		if (round_down(end - size, align) < start)
 			continue;
 
-- 
1.9.3

-- 
Matt Fleming, Intel Open Source Technology Center

Re: [PATCH] efi: fix boundary checking in efi_high_alloc()

[Matt Fleming]

On Thu, 19 Feb, at 08:18:03PM, Yinghai Lu wrote:
> While adding support loading kernel and initrd above 4G to grub2 in legacy
> mode, I was referring to efi_high_alloc().
> That will allocate buffer for kernel and then initrd, and initrd will
> use kernel buffer start as limit.
> 
> During testing found two buffers will be overlapped when initrd size is
> very big like 400M.
> 
> It turns out efi_high_alloc() boundary checking is not right.
> end - size will be the new start, and should not compare new
> start with max, we need to make sure end is smaller than max.
> 
> Signed-off-by: Yinghai Lu <yinghai@kernel.org>
> 
> ---
>  drivers/firmware/efi/libstub/efi-stub-helper.c |    8 ++++----
>  1 file changed, 4 insertions(+), 4 deletions(-)

The patch looks fine but this changelog could do with some finessing
because I spent 30 minutes trying to understand what the bug was, and
more specifically, what values to feed into the allocation algorithm to
trigger it.

Basically, with the current efi_high_alloc() code it's possible to
allocate memory above 'max', because efi_high_alloc() doesn't check that
the tail of the allocation is below 'max'.

If you have an EFI memory map with a single entry that looks like so,

 [0xc0000000-0xc0004000]

And want to allocate 0x3000 bytes below 0xc0003000 the current code will
allocate [0xc0001000-0xc0004000], not [0xc0000000-0xc0003000] like you
would expect.

I've queued up the below patch. If the Linaro/ARM gang could test it out
I'd really appreciate it.

---

>From 1e7295b5d4c5226a160a9167e61b581e388f7f9a Mon Sep 17 00:00:00 2001
From: Yinghai Lu <yinghai@kernel.org>
Date: Thu, 19 Feb 2015 20:18:03 -0800
Subject: [PATCH] efi/libstub: Fix boundary checking in efi_high_alloc()

While adding support loading kernel and initrd above 4G to grub2 in legacy
mode, I was referring to efi_high_alloc().
That will allocate buffer for kernel and then initrd, and initrd will
use kernel buffer start as limit.

During testing found two buffers will be overlapped when initrd size is
very big like 400M.

It turns out efi_high_alloc() boundary checking is not right.
end - size will be the new start, and should not compare new
start with max, we need to make sure end is smaller than max.

[ Basically, with the current efi_high_alloc() code it's possible to
  allocate memory above 'max', because efi_high_alloc() doesn't check
  that the tail of the allocation is below 'max'.

  If you have an EFI memory map with a single entry that looks like so,

   [0xc0000000-0xc0004000]

  And want to allocate 0x3000 bytes below 0xc0003000 the current code
  will allocate [0xc0001000-0xc0004000], not [0xc0000000-0xc0003000]
  like you would expect. - Matt ]

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
Cc: <stable@vger.kernel.org>
Signed-off-by: Matt Fleming <matt.fleming@intel.com>
---
 drivers/firmware/efi/libstub/efi-stub-helper.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/drivers/firmware/efi/libstub/efi-stub-helper.c b/drivers/firmware/efi/libstub/efi-stub-helper.c
index 9bd9fbb5bea8..c927bccd92bd 100644
--- a/drivers/firmware/efi/libstub/efi-stub-helper.c
+++ b/drivers/firmware/efi/libstub/efi-stub-helper.c
@@ -170,12 +170,12 @@ again:
 		start = desc->phys_addr;
 		end = start + desc->num_pages * (1UL << EFI_PAGE_SHIFT);
 
-		if ((start + size) > end || (start + size) > max)
-			continue;
-
-		if (end - size > max)
+		if (end > max)
 			end = max;
 
+		if ((start + size) > end)
+			continue;
+
 		if (round_down(end - size, align) < start)
 			continue;
 
-- 
1.9.3

-- 
Matt Fleming, Intel Open Source Technology Center

Re: [PATCH] efi: fix boundary checking in efi_high_alloc()

[Mark Rutland]

Hi Matt,

> From 1e7295b5d4c5226a160a9167e61b581e388f7f9a Mon Sep 17 00:00:00 2001
> From: Yinghai Lu <yinghai-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org>
> Date: Thu, 19 Feb 2015 20:18:03 -0800
> Subject: [PATCH] efi/libstub: Fix boundary checking in efi_high_alloc()
> 
> While adding support loading kernel and initrd above 4G to grub2 in legacy
> mode, I was referring to efi_high_alloc().
> That will allocate buffer for kernel and then initrd, and initrd will
> use kernel buffer start as limit.
> 
> During testing found two buffers will be overlapped when initrd size is
> very big like 400M.
> 
> It turns out efi_high_alloc() boundary checking is not right.
> end - size will be the new start, and should not compare new
> start with max, we need to make sure end is smaller than max.
> 
> [ Basically, with the current efi_high_alloc() code it's possible to
>   allocate memory above 'max', because efi_high_alloc() doesn't check
>   that the tail of the allocation is below 'max'.
> 
>   If you have an EFI memory map with a single entry that looks like so,
> 
>    [0xc0000000-0xc0004000]
> 
>   And want to allocate 0x3000 bytes below 0xc0003000 the current code
>   will allocate [0xc0001000-0xc0004000], not [0xc0000000-0xc0003000]
>   like you would expect. - Matt ]
> 
> Signed-off-by: Yinghai Lu <yinghai-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org>
> Cc: <stable-u79uwXL29TY76Z2rM5mHXA@public.gmane.org>

I've convinced myself that the new logic is sound, and with this patch
applied atop of v4.0-rc1 I don't see regressions on the platforms I have
access to. So:

Reviewed-by: Mark Rutland <mark.rutland-5wv7dgnIgG8@public.gmane.org>
Tested-by: Mark Rutland <mark.rutland-5wv7dgnIgG8@public.gmane.org>

Ard, Leif:

On a related note, I think that the logic for deciding where to place
the kernel and DTB isn't quite right. The kernel needs to be in the same
naturally-aligned 512M region as the DTB in order to be able to map it,
but the kernel could get relocated above the max address we'll consider
for the DTB if there isn't sufficient space for the kernel between
dram_base and dram_base + 512M.

We should try to use the fixmap to map the DTB so it can be located
anywhere in physical memory. That will make things easier for the stub
and other loaders.

Thanks,
Mark.

> Signed-off-by: Matt Fleming <matt.fleming-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org>
> ---
>  drivers/firmware/efi/libstub/efi-stub-helper.c | 8 ++++----
>  1 file changed, 4 insertions(+), 4 deletions(-)
> 
> diff --git a/drivers/firmware/efi/libstub/efi-stub-helper.c b/drivers/firmware/efi/libstub/efi-stub-helper.c
> index 9bd9fbb5bea8..c927bccd92bd 100644
> --- a/drivers/firmware/efi/libstub/efi-stub-helper.c
> +++ b/drivers/firmware/efi/libstub/efi-stub-helper.c
> @@ -170,12 +170,12 @@ again:
>  		start = desc->phys_addr;
>  		end = start + desc->num_pages * (1UL << EFI_PAGE_SHIFT);
>  
> -		if ((start + size) > end || (start + size) > max)
> -			continue;
> -
> -		if (end - size > max)
> +		if (end > max)
>  			end = max;
>  
> +		if ((start + size) > end)
> +			continue;
> +
>  		if (round_down(end - size, align) < start)
>  			continue;
>  
> -- 
> 1.9.3
> 
> -- 
> Matt Fleming, Intel Open Source Technology Center
> --
> To unsubscribe from this list: send the line "unsubscribe linux-efi" in
> the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: [PATCH] efi: fix boundary checking in efi_high_alloc()

[Mark Rutland]

Hi Matt,

> From 1e7295b5d4c5226a160a9167e61b581e388f7f9a Mon Sep 17 00:00:00 2001
> From: Yinghai Lu <yinghai@kernel.org>
> Date: Thu, 19 Feb 2015 20:18:03 -0800
> Subject: [PATCH] efi/libstub: Fix boundary checking in efi_high_alloc()
> 
> While adding support loading kernel and initrd above 4G to grub2 in legacy
> mode, I was referring to efi_high_alloc().
> That will allocate buffer for kernel and then initrd, and initrd will
> use kernel buffer start as limit.
> 
> During testing found two buffers will be overlapped when initrd size is
> very big like 400M.
> 
> It turns out efi_high_alloc() boundary checking is not right.
> end - size will be the new start, and should not compare new
> start with max, we need to make sure end is smaller than max.
> 
> [ Basically, with the current efi_high_alloc() code it's possible to
>   allocate memory above 'max', because efi_high_alloc() doesn't check
>   that the tail of the allocation is below 'max'.
> 
>   If you have an EFI memory map with a single entry that looks like so,
> 
>    [0xc0000000-0xc0004000]
> 
>   And want to allocate 0x3000 bytes below 0xc0003000 the current code
>   will allocate [0xc0001000-0xc0004000], not [0xc0000000-0xc0003000]
>   like you would expect. - Matt ]
> 
> Signed-off-by: Yinghai Lu <yinghai@kernel.org>
> Cc: <stable@vger.kernel.org>

I've convinced myself that the new logic is sound, and with this patch
applied atop of v4.0-rc1 I don't see regressions on the platforms I have
access to. So:

Reviewed-by: Mark Rutland <mark.rutland@arm.com>
Tested-by: Mark Rutland <mark.rutland@arm.com>

Ard, Leif:

On a related note, I think that the logic for deciding where to place
the kernel and DTB isn't quite right. The kernel needs to be in the same
naturally-aligned 512M region as the DTB in order to be able to map it,
but the kernel could get relocated above the max address we'll consider
for the DTB if there isn't sufficient space for the kernel between
dram_base and dram_base + 512M.

We should try to use the fixmap to map the DTB so it can be located
anywhere in physical memory. That will make things easier for the stub
and other loaders.

Thanks,
Mark.

> Signed-off-by: Matt Fleming <matt.fleming@intel.com>
> ---
>  drivers/firmware/efi/libstub/efi-stub-helper.c | 8 ++++----
>  1 file changed, 4 insertions(+), 4 deletions(-)
> 
> diff --git a/drivers/firmware/efi/libstub/efi-stub-helper.c b/drivers/firmware/efi/libstub/efi-stub-helper.c
> index 9bd9fbb5bea8..c927bccd92bd 100644
> --- a/drivers/firmware/efi/libstub/efi-stub-helper.c
> +++ b/drivers/firmware/efi/libstub/efi-stub-helper.c
> @@ -170,12 +170,12 @@ again:
>  		start = desc->phys_addr;
>  		end = start + desc->num_pages * (1UL << EFI_PAGE_SHIFT);
>  
> -		if ((start + size) > end || (start + size) > max)
> -			continue;
> -
> -		if (end - size > max)
> +		if (end > max)
>  			end = max;
>  
> +		if ((start + size) > end)
> +			continue;
> +
>  		if (round_down(end - size, align) < start)
>  			continue;
>  
> -- 
> 1.9.3
> 
> -- 
> Matt Fleming, Intel Open Source Technology Center
> --
> To unsubscribe from this list: send the line "unsubscribe linux-efi" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: [PATCH] efi: fix boundary checking in efi_high_alloc()

[Ard Biesheuvel]

On 23 February 2015 at 14:15, Mark Rutland <mark.rutland@arm.com> wrote:
> Hi Matt,
>
>> From 1e7295b5d4c5226a160a9167e61b581e388f7f9a Mon Sep 17 00:00:00 2001
>> From: Yinghai Lu <yinghai@kernel.org>
>> Date: Thu, 19 Feb 2015 20:18:03 -0800
>> Subject: [PATCH] efi/libstub: Fix boundary checking in efi_high_alloc()
>>
>> While adding support loading kernel and initrd above 4G to grub2 in legacy
>> mode, I was referring to efi_high_alloc().
>> That will allocate buffer for kernel and then initrd, and initrd will
>> use kernel buffer start as limit.
>>
>> During testing found two buffers will be overlapped when initrd size is
>> very big like 400M.
>>
>> It turns out efi_high_alloc() boundary checking is not right.
>> end - size will be the new start, and should not compare new
>> start with max, we need to make sure end is smaller than max.
>>
>> [ Basically, with the current efi_high_alloc() code it's possible to
>>   allocate memory above 'max', because efi_high_alloc() doesn't check
>>   that the tail of the allocation is below 'max'.
>>
>>   If you have an EFI memory map with a single entry that looks like so,
>>
>>    [0xc0000000-0xc0004000]
>>
>>   And want to allocate 0x3000 bytes below 0xc0003000 the current code
>>   will allocate [0xc0001000-0xc0004000], not [0xc0000000-0xc0003000]
>>   like you would expect. - Matt ]
>>
>> Signed-off-by: Yinghai Lu <yinghai@kernel.org>
>> Cc: <stable@vger.kernel.org>
>
> I've convinced myself that the new logic is sound, and with this patch
> applied atop of v4.0-rc1 I don't see regressions on the platforms I have
> access to. So:
>
> Reviewed-by: Mark Rutland <mark.rutland@arm.com>
> Tested-by: Mark Rutland <mark.rutland@arm.com>
>

Reviewed-by: Ard Biesheuvel <ard.biesheuvel@linaro.org>

> Ard, Leif:
>
> On a related note, I think that the logic for deciding where to place
> the kernel and DTB isn't quite right. The kernel needs to be in the same
> naturally-aligned 512M region as the DTB in order to be able to map it,
> but the kernel could get relocated above the max address we'll consider
> for the DTB if there isn't sufficient space for the kernel between
> dram_base and dram_base + 512M.
>

It also assumes that dram_base itself is 512M aligned, which may not
necessarily be the case, so yes, that logic seems broken.

> We should try to use the fixmap to map the DTB so it can be located
> anywhere in physical memory. That will make things easier for the stub
> and other loaders.
>

Yes, that would be useful, but I think it shouldn't be /that/ hard to
fix the stub

-- 
Ard.

>> ---
>>  drivers/firmware/efi/libstub/efi-stub-helper.c | 8 ++++----
>>  1 file changed, 4 insertions(+), 4 deletions(-)
>>
>> diff --git a/drivers/firmware/efi/libstub/efi-stub-helper.c b/drivers/firmware/efi/libstub/efi-stub-helper.c
>> index 9bd9fbb5bea8..c927bccd92bd 100644
>> --- a/drivers/firmware/efi/libstub/efi-stub-helper.c
>> +++ b/drivers/firmware/efi/libstub/efi-stub-helper.c
>> @@ -170,12 +170,12 @@ again:
>>               start = desc->phys_addr;
>>               end = start + desc->num_pages * (1UL << EFI_PAGE_SHIFT);
>>
>> -             if ((start + size) > end || (start + size) > max)
>> -                     continue;
>> -
>> -             if (end - size > max)
>> +             if (end > max)
>>                       end = max;
>>
>> +             if ((start + size) > end)
>> +                     continue;
>> +
>>               if (round_down(end - size, align) < start)
>>                       continue;
>>
>> --
>> 1.9.3
>>
>> --
>> Matt Fleming, Intel Open Source Technology Center
>> --
>> To unsubscribe from this list: send the line "unsubscribe linux-efi" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>