[PATCH] Rewrite and fix grub_bufio_read()

[PATCH] Rewrite and fix grub_bufio_read()

[Stefan Fritsch]

We had problems downloading large (10-100 MB) gziped files via http
with grub. After some debugging, I think I have found the reason in
grub_bufio_read, which leads to wrong data being passed on. This patch
fixes the issues for me.  I did my tests with a somewhat older
snapshot, but the bufio.c file is the same.

Cheers,
Stefan

The grub_bufio_read() had some issues:

* in the calculation of next_buf, it assumed that bufio->block_size is a
  power of 2, which is not always the case (see code in grub_bufio_open()).

* it assumed that the len passed to grub_bufio_read() is not larger
  than bufio->block_size. I have no idea if this is always true, but it
  seems rather fragile to depend on that.

* depending on the seek patterns, it can do much unbuffered reading

This patch rewrites the function, making it more readable and fixing
these issues. It also loops until the requested amount of bytes has
been read.
---
 grub-core/io/bufio.c | 104 ++++++++++++++++++++-------------------------------
 1 file changed, 40 insertions(+), 64 deletions(-)

diff --git a/grub-core/io/bufio.c b/grub-core/io/bufio.c
index 2243827..2ee96e4 100644
--- a/grub-core/io/bufio.c
+++ b/grub-core/io/bufio.c
@@ -103,81 +103,57 @@ static grub_ssize_t
 grub_bufio_read (grub_file_t file, char *buf, grub_size_t len)
 {
   grub_size_t res = 0;
-  grub_off_t next_buf;
   grub_bufio_t bufio = file->data;
   grub_ssize_t really_read;
 
-  if (file->size == GRUB_FILE_SIZE_UNKNOWN)
-    file->size = bufio->file->size;
-
-  /* First part: use whatever we already have in the buffer.  */
-  if ((file->offset >= bufio->buffer_at) &&
-      (file->offset < bufio->buffer_at + bufio->buffer_len))
+  while (len > 0)
     {
-      grub_size_t n;
-      grub_uint64_t pos;
-
-      pos = file->offset - bufio->buffer_at;
-      n = bufio->buffer_len - pos;
-      if (n > len)
-        n = len;
-
-      grub_memcpy (buf, &bufio->buffer[pos], n);
-      len -= n;
-      res += n;
-
-      buf += n;
-    }
-  if (len == 0)
-    return res;
 
-  /* Need to read some more.  */
-  next_buf = (file->offset + res + len - 1) & ~((grub_off_t) bufio->block_size - 1);
-  /* Now read between file->offset + res and bufio->buffer_at.  */
-  if (file->offset + res < next_buf)
-    {
-      grub_size_t read_now;
-      read_now = next_buf - (file->offset + res);
-      grub_file_seek (bufio->file, file->offset + res);
-      really_read = grub_file_read (bufio->file, buf, read_now);
-      if (really_read < 0)
-	return -1;
       if (file->size == GRUB_FILE_SIZE_UNKNOWN)
 	file->size = bufio->file->size;
-      len -= really_read;
-      buf += really_read;
-      res += really_read;
 
-      /* Partial read. File ended unexpectedly. Save the last chunk in buffer.
-       */
-      if (really_read != (grub_ssize_t) read_now)
+      /* First part: use whatever we already have in the buffer.  */
+      if ((file->offset + res >= bufio->buffer_at) &&
+	  (file->offset + res < bufio->buffer_at + bufio->buffer_len))
 	{
-	  bufio->buffer_len = really_read;
-	  if (bufio->buffer_len > bufio->block_size)
-	    bufio->buffer_len = bufio->block_size;
-	  bufio->buffer_at = file->offset + res - bufio->buffer_len;
-	  grub_memcpy (&bufio->buffer[0], buf - bufio->buffer_len,
-		       bufio->buffer_len);
-	  return res;
+	  grub_size_t n;
+	  grub_uint64_t pos;
+
+	  pos = file->offset + res - bufio->buffer_at;
+	  n = bufio->buffer_len - pos;
+	  if (n > len)
+	    n = len;
+
+	  grub_memcpy (buf, &bufio->buffer[pos], n);
+	  len -= n;
+	  res += n;
+
+	  buf += n;
 	}
-    }
+      if (len == 0)
+	return res;
+
+      /* Need to read some more.  */
+
+      if ((file->offset + res < bufio->buffer_at) ||
+	  (file->offset + res >= bufio->buffer_at + bufio->block_size))
+        {
+	  /* There is no space left in the buffer, move start of buffer */
+	  bufio->buffer_at = file->offset + res;
+	  bufio->buffer_len = 0;
+        }
+
+      grub_file_seek (bufio->file, bufio->buffer_at + bufio->buffer_len);
 
-  /* Read into buffer.  */
-  grub_file_seek (bufio->file, next_buf);
-  really_read = grub_file_read (bufio->file, bufio->buffer,
-				bufio->block_size);
-  if (really_read < 0)
-    return -1;
-  bufio->buffer_at = next_buf;
-  bufio->buffer_len = really_read;
-
-  if (file->size == GRUB_FILE_SIZE_UNKNOWN)
-    file->size = bufio->file->size;
-
-  if (len > bufio->buffer_len)
-    len = bufio->buffer_len;
-  grub_memcpy (buf, &bufio->buffer[file->offset + res - next_buf], len);
-  res += len;
+      really_read = grub_file_read (bufio->file, &bufio->buffer[bufio->buffer_len],
+				    bufio->block_size - bufio->buffer_len);
+
+      if (really_read < 0)
+	return -1;
+      if (really_read == 0)
+	return res;
+      bufio->buffer_len += really_read;
+    }
 
   return res;
 }
-- 
2.1.4

Re: [PATCH] Rewrite and fix grub_bufio_read()

[Andrei Borzenkov]

28.04.2016 14:11, Stefan Fritsch пишет:
> We had problems downloading large (10-100 MB) gziped files via http
> with grub. After some debugging, I think I have found the reason in
> grub_bufio_read, which leads to wrong data being passed on. This patch
> fixes the issues for me.  I did my tests with a somewhat older
> snapshot, but the bufio.c file is the same.
> 

Please send minimal patch that fixes bug in bufio so we can actually see
where the bug is and apply bug fix for 2.02. It is impossible to deduce
from your complete rewrite and this patch is too intrusive for 2.02
irrespectively of considerations below.

> Cheers,
> Stefan
> 
> The grub_bufio_read() had some issues:
> 
> * in the calculation of next_buf, it assumed that bufio->block_size is a
>   power of 2, which is not always the case (see code in grub_bufio_open()).
> 

All current callers set it to power of 2, although you are right that it
should verify it.

> * it assumed that the len passed to grub_bufio_read() is not larger
>   than bufio->block_size. I have no idea if this is always true, but it
>   seems rather fragile to depend on that.
> 

Where do you got this impression from? It reads arbitrary size, there is
no assumption about len. Otherwise netboot had not worked at all. The
logic is - rest of previous buffer, direct read until farthest buffer
boundary, partial buffer read at the end. Low level file is responsible
for the second step, so there is no loop needed.

> * depending on the seek patterns, it can do much unbuffered reading
> 

Yes, if you read large chunk as in reading kernel or initrd it simply
does direct read into provided buffer, thus avoiding extra memory copy.

> This patch rewrites the function, making it more readable and fixing
> these issues. It also loops until the requested amount of bytes has
> been read.

Well, your patch now adds extra copying of every block thus making it
less efficient for large reads which are the primary objective. So I am
afraid we cannot use this patch; but it would be great if you could
provide analysis of problem you observed in current code, showing where
and why it happens, so we could fix it.

> ---
>  grub-core/io/bufio.c | 104 ++++++++++++++++++++-------------------------------
>  1 file changed, 40 insertions(+), 64 deletions(-)
> 
> diff --git a/grub-core/io/bufio.c b/grub-core/io/bufio.c
> index 2243827..2ee96e4 100644
> --- a/grub-core/io/bufio.c
> +++ b/grub-core/io/bufio.c
> @@ -103,81 +103,57 @@ static grub_ssize_t
>  grub_bufio_read (grub_file_t file, char *buf, grub_size_t len)
>  {
>    grub_size_t res = 0;
> -  grub_off_t next_buf;
>    grub_bufio_t bufio = file->data;
>    grub_ssize_t really_read;
>  
> -  if (file->size == GRUB_FILE_SIZE_UNKNOWN)
> -    file->size = bufio->file->size;
> -
> -  /* First part: use whatever we already have in the buffer.  */
> -  if ((file->offset >= bufio->buffer_at) &&
> -      (file->offset < bufio->buffer_at + bufio->buffer_len))
> +  while (len > 0)
>      {
> -      grub_size_t n;
> -      grub_uint64_t pos;
> -
> -      pos = file->offset - bufio->buffer_at;
> -      n = bufio->buffer_len - pos;
> -      if (n > len)
> -        n = len;
> -
> -      grub_memcpy (buf, &bufio->buffer[pos], n);
> -      len -= n;
> -      res += n;
> -
> -      buf += n;
> -    }
> -  if (len == 0)
> -    return res;
>  
> -  /* Need to read some more.  */
> -  next_buf = (file->offset + res + len - 1) & ~((grub_off_t) bufio->block_size - 1);
> -  /* Now read between file->offset + res and bufio->buffer_at.  */
> -  if (file->offset + res < next_buf)
> -    {
> -      grub_size_t read_now;
> -      read_now = next_buf - (file->offset + res);
> -      grub_file_seek (bufio->file, file->offset + res);
> -      really_read = grub_file_read (bufio->file, buf, read_now);
> -      if (really_read < 0)
> -	return -1;
>        if (file->size == GRUB_FILE_SIZE_UNKNOWN)
>  	file->size = bufio->file->size;
> -      len -= really_read;
> -      buf += really_read;
> -      res += really_read;
>  
> -      /* Partial read. File ended unexpectedly. Save the last chunk in buffer.
> -       */
> -      if (really_read != (grub_ssize_t) read_now)
> +      /* First part: use whatever we already have in the buffer.  */
> +      if ((file->offset + res >= bufio->buffer_at) &&
> +	  (file->offset + res < bufio->buffer_at + bufio->buffer_len))
>  	{
> -	  bufio->buffer_len = really_read;
> -	  if (bufio->buffer_len > bufio->block_size)
> -	    bufio->buffer_len = bufio->block_size;
> -	  bufio->buffer_at = file->offset + res - bufio->buffer_len;
> -	  grub_memcpy (&bufio->buffer[0], buf - bufio->buffer_len,
> -		       bufio->buffer_len);
> -	  return res;
> +	  grub_size_t n;
> +	  grub_uint64_t pos;
> +
> +	  pos = file->offset + res - bufio->buffer_at;
> +	  n = bufio->buffer_len - pos;
> +	  if (n > len)
> +	    n = len;
> +
> +	  grub_memcpy (buf, &bufio->buffer[pos], n);
> +	  len -= n;
> +	  res += n;
> +
> +	  buf += n;
>  	}
> -    }
> +      if (len == 0)
> +	return res;
> +
> +      /* Need to read some more.  */
> +
> +      if ((file->offset + res < bufio->buffer_at) ||
> +	  (file->offset + res >= bufio->buffer_at + bufio->block_size))
> +        {
> +	  /* There is no space left in the buffer, move start of buffer */
> +	  bufio->buffer_at = file->offset + res;
> +	  bufio->buffer_len = 0;
> +        }
> +
> +      grub_file_seek (bufio->file, bufio->buffer_at + bufio->buffer_len);
>  
> -  /* Read into buffer.  */
> -  grub_file_seek (bufio->file, next_buf);
> -  really_read = grub_file_read (bufio->file, bufio->buffer,
> -				bufio->block_size);
> -  if (really_read < 0)
> -    return -1;
> -  bufio->buffer_at = next_buf;
> -  bufio->buffer_len = really_read;
> -
> -  if (file->size == GRUB_FILE_SIZE_UNKNOWN)
> -    file->size = bufio->file->size;
> -
> -  if (len > bufio->buffer_len)
> -    len = bufio->buffer_len;
> -  grub_memcpy (buf, &bufio->buffer[file->offset + res - next_buf], len);
> -  res += len;
> +      really_read = grub_file_read (bufio->file, &bufio->buffer[bufio->buffer_len],
> +				    bufio->block_size - bufio->buffer_len);
> +
> +      if (really_read < 0)
> +	return -1;
> +      if (really_read == 0)
> +	return res;
> +      bufio->buffer_len += really_read;
> +    }
>  
>    return res;
>  }
> 

Re: [PATCH] Rewrite and fix grub_bufio_read()

[Stefan Fritsch]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2271 bytes --]

On Thu, 28 Apr 2016, Andrei Borzenkov wrote:

> 28.04.2016 14:11, Stefan Fritsch пишет:
> > We had problems downloading large (10-100 MB) gziped files via http
> > with grub. After some debugging, I think I have found the reason in
> > grub_bufio_read, which leads to wrong data being passed on. This patch
> > fixes the issues for me.  I did my tests with a somewhat older
> > snapshot, but the bufio.c file is the same.
> > 
> 
> Please send minimal patch that fixes bug in bufio so we can actually see
> where the bug is and apply bug fix for 2.02. It is impossible to deduce
> from your complete rewrite and this patch is too intrusive for 2.02
> irrespectively of considerations below.
> 
> > Cheers,
> > Stefan
> > 
> > The grub_bufio_read() had some issues:
> > 
> > * in the calculation of next_buf, it assumed that bufio->block_size is a
> >   power of 2, which is not always the case (see code in grub_bufio_open()).
> > 
> 
> All current callers set it to power of 2, although you are right that it
> should verify it.

No:

  if ((size < 0) || ((unsigned) size > io->size))
    size = ((io->size > GRUB_BUFIO_MAX_SIZE) ? GRUB_BUFIO_MAX_SIZE :
            io->size);

...

  bufio->block_size = size;

io->size is the file size. So at least for files < 32K (which is the size 
that bufio is called with by the net layer), block_size is not a power of 
2 but the size of the file. Then next_buf typically gets a value from 0 
to 8.

Though that should not cause wrong data and does not explain the problems 
we have seen with large files.

> 
> > * it assumed that the len passed to grub_bufio_read() is not larger
> >   than bufio->block_size. I have no idea if this is always true, but it
> >   seems rather fragile to depend on that.
> > 
> 
> Where do you got this impression from? It reads arbitrary size, there is
> no assumption about len. Otherwise netboot had not worked at all. The
> logic is - rest of previous buffer, direct read until farthest buffer
> boundary, partial buffer read at the end. Low level file is responsible
> for the second step, so there is no loop needed.

You are right, I was misreading the second part of the code with the 
direct read. Now I wonder why the patch helped with our problem. I will do 
some more debugging.

gzio/http problem (was: [PATCH] Rewrite and fix grub_bufio_read())

[Stefan Fritsch]

On Thursday 28 April 2016 21:52:27, Stefan Fritsch wrote:
> You are right, I was misreading the second part of the code with
> the  direct read. Now I wonder why the patch helped with our
> problem. I will do some more debugging.

The real problem seems to be that http sometimes (depending on network 
timing?) returns short reads but gzio does not check how many bytes 
have actually been read. The looping in my patch for grub_bufio_read() 
fixed this by never returning a short read.

I guess two things should be fixed: gzio should check the return value 
of grub_file_read(), and (assuming that other code depends on there 
not being short reads, too) http should be fixed. Or maybe 
grub_file_read() should get a loop that ensures that there are no 
short reads?

Re: gzio/http problem (was: [PATCH] Rewrite and fix grub_bufio_read())

[Vladimir 'phcoder' Serbinenko]

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

HTTP code should never return short reads. The whole subsystem relies on
never having short reads from any fs or network driver

Le ven. 29 avr. 2016 09:30, Stefan Fritsch <sf@sfritsch.de> a écrit :

> On Thursday 28 April 2016 21:52:27, Stefan Fritsch wrote:
> > You are right, I was misreading the second part of the code with
> > the  direct read. Now I wonder why the patch helped with our
> > problem. I will do some more debugging.
>
> The real problem seems to be that http sometimes (depending on network
> timing?) returns short reads but gzio does not check how many bytes
> have actually been read. The looping in my patch for grub_bufio_read()
> fixed this by never returning a short read.
>
> I guess two things should be fixed: gzio should check the return value
> of grub_file_read(), and (assuming that other code depends on there
> not being short reads, too) http should be fixed. Or maybe
> grub_file_read() should get a loop that ensures that there are no
> short reads?
>
>
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> https://lists.gnu.org/mailman/listinfo/grub-devel
>

[-- Attachment #2: Type: text/html, Size: 1610 bytes --]

Re: gzio/http problem

[Andrei Borzenkov]

29.04.2016 00:54, Vladimir 'phcoder' Serbinenko пишет:
> HTTP code should never return short reads. The whole subsystem relies on
> never having short reads from any fs or network driver
> 

HTTP code never returns short reads itself. But it sets EOF on socket in
case something bad happens, and in this case we return currently
received data to caller in net core.

      if (!net->eof)
        {
          try++;
          grub_net_poll_cards (GRUB_NET_INTERVAL +
                               (try * GRUB_NET_INTERVAL_ADDITION),
&net->stall);
        }
      else
        return total;

Disallowing short reads means also we should also disallow files with
unknown size. I think that's unrealistic.

> Le ven. 29 avr. 2016 09:30, Stefan Fritsch <sf@sfritsch.de> a écrit :
> 
>> On Thursday 28 April 2016 21:52:27, Stefan Fritsch wrote:
>>> You are right, I was misreading the second part of the code with
>>> the  direct read. Now I wonder why the patch helped with our
>>> problem. I will do some more debugging.
>>
>> The real problem seems to be that http sometimes (depending on network
>> timing?) returns short reads but gzio does not check how many bytes
>> have actually been read. The looping in my patch for grub_bufio_read()
>> fixed this by never returning a short read.
>>
>> I guess two things should be fixed: gzio should check the return value
>> of grub_file_read(), and (assuming that other code depends on there
>> not being short reads, too) http should be fixed. Or maybe
>> grub_file_read() should get a loop that ensures that there are no
>> short reads?
>>
>>
>> _______________________________________________
>> Grub-devel mailing list
>> Grub-devel@gnu.org
>> https://lists.gnu.org/mailman/listinfo/grub-devel
>>
> 
> 
> 
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> https://lists.gnu.org/mailman/listinfo/grub-devel
> 

Re: gzio/http problem

[Stefan Fritsch]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1391 bytes --]

On Fri, 29 Apr 2016, Andrei Borzenkov wrote:

> 29.04.2016 00:54, Vladimir 'phcoder' Serbinenko пишет:
> > HTTP code should never return short reads. The whole subsystem relies on
> > never having short reads from any fs or network driver
> > 
> 
> HTTP code never returns short reads itself. But it sets EOF on socket in
> case something bad happens, and in this case we return currently
> received data to caller in net core.
> 
>       if (!net->eof)
>         {
>           try++;
>           grub_net_poll_cards (GRUB_NET_INTERVAL +
>                                (try * GRUB_NET_INTERVAL_ADDITION),
> &net->stall);
>         }
>       else
>         return total;
> 
> Disallowing short reads means also we should also disallow files with
> unknown size. I think that's unrealistic.

I think I have found the problem:

http_seek() creates a new connection but does not reset the eof flag. 
grub_net_fs_read_real() then does a short read because of the set eof 
flag.


This patch seems to fix the issue:

@@ -453,6 +461,7 @@ http_seek (struct grub_file *file, grub_off_t off)
     }
 
   file->device->net->stall = 0;
+  file->device->net->eof = 0;
   file->device->net->offset = off;
 
   data = grub_zalloc (sizeof (*data));


Though one could also argue that grub_net_seek_real() should reset the eof 
flag before calling file->device->net->protocol->seek().


Cheers,
Stefan

Re: gzio/http problem

[Andrei Borzenkov]

30.04.2016 00:00, Stefan Fritsch пишет:
> On Fri, 29 Apr 2016, Andrei Borzenkov wrote:
> 
>> 29.04.2016 00:54, Vladimir 'phcoder' Serbinenko пишет:
>>> HTTP code should never return short reads. The whole subsystem relies on
>>> never having short reads from any fs or network driver
>>>
>>
>> HTTP code never returns short reads itself. But it sets EOF on socket in
>> case something bad happens, and in this case we return currently
>> received data to caller in net core.
>>
>>       if (!net->eof)
>>         {
>>           try++;
>>           grub_net_poll_cards (GRUB_NET_INTERVAL +
>>                                (try * GRUB_NET_INTERVAL_ADDITION),
>> &net->stall);
>>         }
>>       else
>>         return total;
>>
>> Disallowing short reads means also we should also disallow files with
>> unknown size. I think that's unrealistic.
> 
> I think I have found the problem:
> 
> http_seek() creates a new connection but does not reset the eof flag. 
> grub_net_fs_read_real() then does a short read because of the set eof 
> flag.
> 
> 
> This patch seems to fix the issue:
> 
> @@ -453,6 +461,7 @@ http_seek (struct grub_file *file, grub_off_t off)
>      }
>  
>    file->device->net->stall = 0;
> +  file->device->net->eof = 0;
>    file->device->net->offset = off;
>  
>    data = grub_zalloc (sizeof (*data));
> 

Good catch! Committed.

> 
> Though one could also argue that grub_net_seek_real() should reset the eof 
> flag before calling file->device->net->protocol->seek().
> 

It does it if it re-establishes connection itself (BTW it needs to reset
->stall in this case as well, I also added patch for it). But it does
not know how low level protocol implements it, so it would be wrong here.

We probably need to consolidate cleanup code to make sure it is done in
one place.

Re: [PATCH] Rewrite and fix grub_bufio_read()

[Andrei Borzenkov]

28.04.2016 22:52, Stefan Fritsch пишет:
> On Thu, 28 Apr 2016, Andrei Borzenkov wrote:
> 
>> 28.04.2016 14:11, Stefan Fritsch пишет:
>>> We had problems downloading large (10-100 MB) gziped files via http
>>> with grub. After some debugging, I think I have found the reason in
>>> grub_bufio_read, which leads to wrong data being passed on. This patch
>>> fixes the issues for me.  I did my tests with a somewhat older
>>> snapshot, but the bufio.c file is the same.
>>>
>>
>> Please send minimal patch that fixes bug in bufio so we can actually see
>> where the bug is and apply bug fix for 2.02. It is impossible to deduce
>> from your complete rewrite and this patch is too intrusive for 2.02
>> irrespectively of considerations below.
>>
>>> Cheers,
>>> Stefan
>>>
>>> The grub_bufio_read() had some issues:
>>>
>>> * in the calculation of next_buf, it assumed that bufio->block_size is a
>>>   power of 2, which is not always the case (see code in grub_bufio_open()).
>>>
>>
>> All current callers set it to power of 2, although you are right that it
>> should verify it.
> 
> No:
> 
>   if ((size < 0) || ((unsigned) size > io->size))
>     size = ((io->size > GRUB_BUFIO_MAX_SIZE) ? GRUB_BUFIO_MAX_SIZE :
>             io->size);
> 
> ...
> 
>   bufio->block_size = size;
> 
> io->size is the file size. So at least for files < 32K (which is the size 
> that bufio is called with by the net layer), block_size is not a power of 
> 2 but the size of the file. Then next_buf typically gets a value from 0 
> to 8.
> 


Ah, OK. Not sure why we need this check in the first place. Buffer size
is unrelated to file size, so this looks more like micro-optimization of
buffer size.

Although this means that we always have the whole file in buffer anyway
and so never hit power of 2 issue.