Re: [PATCH] Fix integer overflow in badram_iter

[Arjun]

The surrounding code already uses ULL instead of grub_uint64_t. ULL
already is guaranteed >= 64 bits so I would expect this to work fine
as is. Could you explain why grub_uint64_t cast is recommended?

Amended patch with signoff below.

Signed-off-by: Arjun Barrett <arjunbarrett@gmail.com>
---
 grub-core/mmap/mmap.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/grub-core/mmap/mmap.c b/grub-core/mmap/mmap.c
index c8c8312c5..ce02d8e66 100644
--- a/grub-core/mmap/mmap.c
+++ b/grub-core/mmap/mmap.c
@@ -396,13 +396,14 @@ badram_iter (grub_uint64_t addr, grub_uint64_t size,
   else
     {
       low = 0;
-      high = ~0ULL;
+      high = var < 64 ? (1ULL << var) - 1ULL : ~0ULL;
+
       /* Find starting value. Keep low and high such that
  fill_mask (low) < addr and fill_mask (high) >= addr;
       */
       while (high - low > 1)
  {
-   cur = (low + high) / 2;
+   cur = low / 2 + high / 2 + (low & high & 1ULL);
    if (fill_mask (entry, cur) >= addr)
      high = cur;
    else
-- 
2.45.2

On Tue, Aug 13, 2024 at 7:26 AM Daniel Kiper <dkiper@net-space.pl> wrote:
>
> On Mon, Jul 29, 2024 at 09:07:48PM -0700, Arjun wrote:
> > Fixes support for 64-bit badram entries. Previously, whenever the start 
> > address
> > of an mmap region exceeded the maximum address attainable via an addr,mask 
> > pair,
> > GRUB would erroneously attempt to binary-search up to the integer limit for 
> > an
> > unsigned 64-bit integer in search of the "start" of its iterator over badram
> > locations in the current range.
> >
> > On its own this wouldn't be an issue, as the iterator should be empty 
> > anyway in
> > this case. However, the binary search code directly adds two 64-bit unsigned
> > integers as an intermediate step, causing an integer overflow and a 
> > subsequent
> > infinite loop.
> >
> > This patch fixes this behavior with two changes:
> >   1. We set the initial upper bound of the binary search to the actual 
> > maximum
> >      possible index for the iterator to start at (i.e. (1 << var) - 1), 
> > rather
> >      than the 64-bit unsigned integer limit.
> >   2. We avoid any integer overflows in the binary search by adding the high 
> > and
> >      low operands more carefully.
> >
> > The user-facing effect of this is that 64-bit badram entries no longer cause
> > GRUB to hang indefinitely. This change has been tested and verified working 
> > on
> > x86_64 EFI.
>
> Missing Signed-off-by: ...
>
> > ---
> > grub-core/mmap/mmap.c | 5 +++--
> > 1 file changed, 3 insertions(+), 2 deletions(-)
> >
> > diff --git a/grub-core/mmap/mmap.c b/grub-core/mmap/mmap.c
> > index c8c8312c5..ce02d8e66 100644
> > --- a/grub-core/mmap/mmap.c
> > +++ b/grub-core/mmap/mmap.c
> > @@ -396,13 +396,14 @@ badram_iter (grub_uint64_t addr, grub_uint64_t size,
> >   else
> >     {
> >       low = 0;
> > -      high = ~0ULL;
> > +      high = var < 64 ? (1ULL << var) - 1ULL : ~0ULL;
>
> Instead of ULL you should use grub_uint64_t cast.
>
> >       /* Find starting value. Keep low and high such that
> >         fill_mask (low) < addr and fill_mask (high) >= addr;
> >       */
> >       while (high - low > 1)
> >        {
> > -         cur = (low + high) / 2;
> > +         cur = low / 2 + high / 2 + (low & high & 1ULL);
>
> Ditto...
>
> Daniel