[PATCH] fix an infinite loop with a corrupted pc partition table

[PATCH] fix an infinite loop with a corrupted pc partition table

[Felix Zielcke]

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

With this [0] partition table grub-probe currently loops forever:

kern/disk.c:389: Reading `hd1'...
partmap/pc.c:142: partition 0: flag 0x0, type 0x5, start 0x0, len
0x11177330
partmap/pc.c:142: partition 1: flag 0x0, type 0x0, start 0x0, len 0x0
partmap/pc.c:142: partition 2: flag 0x0, type 0x0, start 0x0, len 0x0
partmap/pc.c:142: partition 3: flag 0x0, type 0x0, start 0x0, len 0x0
kern/disk.c:389: Reading `hd1'...
partmap/pc.c:142: partition 0: flag 0x0, type 0x5, start 0x0, len
0x11177330
partmap/pc.c:142: partition 1: flag 0x0, type 0x0, start 0x0, len 0x0
partmap/pc.c:142: partition 2: flag 0x0, type 0x0, start 0x0, len 0x0
partmap/pc.c:142: partition 3: flag 0x0, type 0x0, start 0x0, len 0x0
[...]

This patch fixes it, but probable there's a better fix.


[0] http://bugs.debian.org/cgi-bin/bugreport.cgi?msg=5;filename=corrupt-table.dat;att=1;bug=519223

-- 
Felix Zielcke

[-- Attachment #2: corrupted_partmap.diff --]
[-- Type: text/x-patch, Size: 1090 bytes --]

2009-07-24  Felix Zielcke  <fzielcke@z-51.de>

	* partmap/pc.c (pc_partition_map_iterate): Don't loop forever
	in case the partition table is corrupted.

diff --git a/partmap/pc.c b/partmap/pc.c
index 6f68ecf..0271311 100644
--- a/partmap/pc.c
+++ b/partmap/pc.c
@@ -97,6 +97,7 @@ pc_partition_map_iterate (grub_disk_t disk,
   struct grub_pc_partition_mbr mbr;
   struct grub_pc_partition_disk_label label;
   struct grub_disk raw;
+  int loop;
 
   /* Enforce raw disk access.  */
   raw = *disk;
@@ -108,11 +109,13 @@ pc_partition_map_iterate (grub_disk_t disk,
   p.data = &pcdata;
   p.partmap = &grub_pc_partition_map;
 
-  while (1)
+  loop = 0;
+  while (loop < 100)
     {
       int i;
       struct grub_pc_partition_entry *e;
 
+      loop++;
       /* Read the MBR.  */
       if (grub_disk_read (&raw, p.offset, 0, sizeof (mbr), &mbr))
 	goto finish;
@@ -221,6 +224,9 @@ pc_partition_map_iterate (grub_disk_t disk,
 	break;
     }
 
+  if (loop == 100)
+    return grub_error (GRUB_ERR_BAD_PART_TABLE, "Corrupted partition table found.");
+
  finish:
   return grub_errno;
 }

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Felix Zielcke]

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

Am Freitag, den 24.07.2009, 18:58 +0200 schrieb Felix Zielcke:
> 
> 
> With this [0] partition table grub-probe currently loops forever:
> 
> kern/disk.c:389: Reading `hd1'...
> partmap/pc.c:142: partition 0: flag 0x0, type 0x5, start 0x0, len
> 0x11177330
> partmap/pc.c:142: partition 1: flag 0x0, type 0x0, start 0x0, len 0x0
> partmap/pc.c:142: partition 2: flag 0x0, type 0x0, start 0x0, len 0x0
> partmap/pc.c:142: partition 3: flag 0x0, type 0x0, start 0x0, len 0x0
> kern/disk.c:389: Reading `hd1'...
> partmap/pc.c:142: partition 0: flag 0x0, type 0x5, start 0x0, len
> 0x11177330
> partmap/pc.c:142: partition 1: flag 0x0, type 0x0, start 0x0, len 0x0
> partmap/pc.c:142: partition 2: flag 0x0, type 0x0, start 0x0, len 0x0
> partmap/pc.c:142: partition 3: flag 0x0, type 0x0, start 0x0, len 0x0
> [...]
> 
> This patch fixes it, but probable there's a better fix.
> 
> 
> [0]
> http://bugs.debian.org/cgi-bin/bugreport.cgi?msg=5;filename=corrupt-table.dat;att=1;bug=519223 

Here's a new one after comments from Vladimir on IRC
loop count is increased to 100'000 and partitions with a starting sector
of 0 are ignored.

-- 
Felix Zielcke

[-- Attachment #2: corrupted_partmap.diff.2 --]
[-- Type: text/plain, Size: 1858 bytes --]

2009-07-24  Felix Zielcke  <fzielcke@z-51.de>

	* partmap/pc.c (pc_partition_map_iterate): Don't loop forever
	in case the partition table is corrupted.  Also ignore partitions
	with a starting sector of 0.

diff --git a/partmap/pc.c b/partmap/pc.c
index 6f68ecf..ab58b3d 100644
--- a/partmap/pc.c
+++ b/partmap/pc.c
@@ -97,6 +97,7 @@ pc_partition_map_iterate (grub_disk_t disk,
   struct grub_pc_partition_mbr mbr;
   struct grub_pc_partition_disk_label label;
   struct grub_disk raw;
+  int loop;
 
   /* Enforce raw disk access.  */
   raw = *disk;
@@ -108,11 +109,13 @@ pc_partition_map_iterate (grub_disk_t disk,
   p.data = &pcdata;
   p.partmap = &grub_pc_partition_map;
 
-  while (1)
+  loop = 0;
+  while (loop < 100000)
     {
       int i;
       struct grub_pc_partition_entry *e;
 
+      loop++;
       /* Read the MBR.  */
       if (grub_disk_read (&raw, p.offset, 0, sizeof (mbr), &mbr))
 	goto finish;
@@ -143,7 +146,7 @@ pc_partition_map_iterate (grub_disk_t disk,
 	    return grub_error (GRUB_ERR_BAD_PART_TABLE, "dummy mbr");
 
 	  /* If this partition is a normal one, call the hook.  */
-	  if (! grub_pc_partition_is_empty (e->type)
+	  if (e->start != 0 && ! grub_pc_partition_is_empty (e->type)
 	      && ! grub_pc_partition_is_extended (e->type))
 	    {
 	      pcdata.dos_part++;
@@ -206,7 +209,7 @@ pc_partition_map_iterate (grub_disk_t disk,
 	{
 	  e = mbr.entries + i;
 
-	  if (grub_pc_partition_is_extended (e->type))
+	  if (e->start != 0 && grub_pc_partition_is_extended (e->type))
 	    {
 	      p.offset = pcdata.ext_offset + grub_le_to_cpu32 (e->start);
 	      if (! pcdata.ext_offset)
@@ -221,6 +224,8 @@ pc_partition_map_iterate (grub_disk_t disk,
 	break;
     }
 
+  if (loop == 100000)
+    return grub_error (GRUB_ERR_BAD_PART_TABLE, "Corrupted partition table found.");
  finish:
   return grub_errno;
 }

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Pavel Roskin]

On Fri, 2009-07-24 at 18:58 +0200, Felix Zielcke wrote:
> With this [0] partition table grub-probe currently loops forever:
> 
> kern/disk.c:389: Reading `hd1'...
> partmap/pc.c:142: partition 0: flag 0x0, type 0x5, start 0x0, len
> 0x11177330

That's so evil!

> This patch fixes it, but probable there's a better fix.

We could require that all references to extended partitions are only
considered if they lead to a sector after the one currently being
processed.

Actually, no partition table should point to any partition (extended or
not) in an earlier sector, but it's enough to exclude backward links
between extended partitions to break the loop.

ChangeLog:

	* partmap/pc.c (pc_partition_map_iterate): Only allow references
	to subsequent sectors in extended partition entries.
---
 partmap/pc.c |    8 +++++++-
 1 files changed, 7 insertions(+), 1 deletions(-)

diff --git a/partmap/pc.c b/partmap/pc.c
index 6f68ecf..cd119c0 100644
--- a/partmap/pc.c
+++ b/partmap/pc.c
@@ -208,7 +208,13 @@ pc_partition_map_iterate (grub_disk_t disk,
 
 	  if (grub_pc_partition_is_extended (e->type))
 	    {
-	      p.offset = pcdata.ext_offset + grub_le_to_cpu32 (e->start);
+	      grub_disk_addr_t new_offset;
+
+	      /* Only allow references subsequent sectors */
+	      new_offset = pcdata.ext_offset + grub_le_to_cpu32 (e->start);
+	      if (new_offset <= p.offset)
+		continue;
+
 	      if (! pcdata.ext_offset)
 		pcdata.ext_offset = p.offset;
 

-- 
Regards,
Pavel Roskin

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Pavel Roskin]

On Fri, 2009-07-24 at 21:24 +0200, Felix Zielcke wrote:

> Here's a new one after comments from Vladimir on IRC
> loop count is increased to 100'000 and partitions with a starting sector
> of 0 are ignored.

I don't see why it's better.  Do you think the links backwards should be
allowed?

-- 
Regards,
Pavel Roskin

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Vladimir 'phcoder' Serbinenko]

Hello
>> This patch fixes it, but probable there's a better fix.
>
> We could require that all references to extended partitions are only
> considered if they lead to a sector after the one currently being
> processed.
I already thought about this and spoke about it on IRC. Unfortunately
backward pointers do exist. I had it few years ago when I used
diskdrake. It put the logical partition at the end of the chain even
if partition itself was in the middle of the disk. I don't know if it
still has this behaviour but partition schemes have sometimes tendency
to stay a long time. I don't like they idea of user not being able to
boot his mandriva or some partitions not being accessible.
A big problem with pc partitions is that AFAIK there is no normative
standard for it, only descriptive documents
>
> Actually, no partition table should point to any partition (extended or
> not) in an earlier sector, but it's enough to exclude backward links
> between extended partitions to break the loop.
>
> ChangeLog:
>
>        * partmap/pc.c (pc_partition_map_iterate): Only allow references
>        to subsequent sectors in extended partition entries.
> ---
>  partmap/pc.c |    8 +++++++-
>  1 files changed, 7 insertions(+), 1 deletions(-)
>
> diff --git a/partmap/pc.c b/partmap/pc.c
> index 6f68ecf..cd119c0 100644
> --- a/partmap/pc.c
> +++ b/partmap/pc.c
> @@ -208,7 +208,13 @@ pc_partition_map_iterate (grub_disk_t disk,
>
>          if (grub_pc_partition_is_extended (e->type))
>            {
> -             p.offset = pcdata.ext_offset + grub_le_to_cpu32 (e->start);
> +             grub_disk_addr_t new_offset;
> +
> +             /* Only allow references subsequent sectors */
> +             new_offset = pcdata.ext_offset + grub_le_to_cpu32 (e->start);
> +             if (new_offset <= p.offset)
> +               continue;
> +
>              if (! pcdata.ext_offset)
>                pcdata.ext_offset = p.offset;
>
>
> --
> Regards,
> Pavel Roskin
>
>
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> http://lists.gnu.org/mailman/listinfo/grub-devel
>



-- 
Regards
Vladimir 'phcoder' Serbinenko

Personal git repository: http://repo.or.cz/w/grub2/phcoder.git

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Vladimir 'phcoder' Serbinenko]

>> Here's a new one after comments from Vladimir on IRC
>> loop count is increased to 100'000 and partitions with a starting sector
>> of 0 are ignored.
>
> I don't see why it's better.  Do you think the links backwards should be
> allowed?
I think yes since breaking some configuration will be seen as
regression. I know that consensus is to consider backward links a
non-compliance but AFAIK no OS reject it. Situation "my OS sees
partitions and grub doesn't" creates problems for users and is seen as
a bug.
If you have any arguments feel free to post them, as any sane person
I'm ready to change my opinion in face of good arguments
>
> --
> Regards,
> Pavel Roskin
>
>
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> http://lists.gnu.org/mailman/listinfo/grub-devel
>



-- 
Regards
Vladimir 'phcoder' Serbinenko

Personal git repository: http://repo.or.cz/w/grub2/phcoder.git

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Pavel Roskin]

On Fri, 2009-07-24 at 22:35 +0200, Vladimir 'phcoder' Serbinenko wrote:
> Hello
> >> This patch fixes it, but probable there's a better fix.
> >
> > We could require that all references to extended partitions are only
> > considered if they lead to a sector after the one currently being
> > processed.
> I already thought about this and spoke about it on IRC. Unfortunately
> backward pointers do exist. I had it few years ago when I used
> diskdrake. It put the logical partition at the end of the chain even
> if partition itself was in the middle of the disk. I don't know if it
> still has this behaviour but partition schemes have sometimes tendency
> to stay a long time. I don't like they idea of user not being able to
> boot his mandriva or some partitions not being accessible.

This would still work.

This is still allowed:

MBR  ---------------->  Ext
        Logical  <-----/

This is what I want to forbid:

MBR  ---------------->  Ext
             Ext  <----/
                \-------------->  Logical

I don't think any tool would create that insanity.

> A big problem with pc partitions is that AFAIK there is no normative 
> standard for it, only descriptive documents

Yes, it's a typical "industry standard" :-(

-- 
Regards,
Pavel Roskin

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Vladimir 'phcoder' Serbinenko]

On Fri, Jul 24, 2009 at 11:03 PM, Pavel Roskin<proski@gnu.org> wrote:
> On Fri, 2009-07-24 at 22:35 +0200, Vladimir 'phcoder' Serbinenko wrote:

> This is still allowed:
>
> MBR  ---------------->  Ext
>        Logical  <-----/
AFAIK this isn't even possible since e->start is unsigned and
references to logical partitions from ext label are relative to
position of ext while ext->ext reference are relative to the first
position of ext.
>
> This is what I want to forbid:
>
> MBR  ---------------->  Ext
>             Ext  <----/
>                \-------------->  Logical
>
> I don't think any tool would create that insanity.
>
If I remember correctly DiskDrake created something like
MBR----------------> Ext --> Logical

\-------------------------------------------------->Ext -----> Logical
                                                 Ext<------------------------/
                                                   \----->Logical
>> A big problem with pc partitions is that AFAIK there is no normative
>> standard for it, only descriptive documents
>
> Yes, it's a typical "industry standard" :-(
>
> --
> Regards,
> Pavel Roskin
>
>
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> http://lists.gnu.org/mailman/listinfo/grub-devel
>



-- 
Regards
Vladimir 'phcoder' Serbinenko

Personal git repository: http://repo.or.cz/w/grub2/phcoder.git

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Robert Millan]

On Fri, Jul 24, 2009 at 09:24:31PM +0200, Felix Zielcke wrote:
> +  loop = 0;
> +  while (loop < 100000)
> [...]
> +  if (loop == 100000)
> +    return grub_error (GRUB_ERR_BAD_PART_TABLE, "Corrupted partition table found.");

What does this 100000 represent?  It looks like heuristic, but I'm missing
some context (I'm not familiar with extended partition layout).

-- 
Robert Millan

  The DRM opt-in fallacy: "Your data belongs to us. We will decide when (and
  how) you may access your data; but nobody's threatening your freedom: we
  still allow you to remove your data and not access it at all."

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Vladimir 'phcoder' Serbinenko]

On Sat, Jul 25, 2009 at 6:36 PM, Robert Millan<rmh@aybabtu.com> wrote:
> On Fri, Jul 24, 2009 at 09:24:31PM +0200, Felix Zielcke wrote:
>> +  loop = 0;
>> +  while (loop < 100000)
>> [...]
>> +  if (loop == 100000)
>> +    return grub_error (GRUB_ERR_BAD_PART_TABLE, "Corrupted partition table found.");
>
> What does this 100000 represent?  It looks like heuristic, but I'm missing
> some context (I'm not familiar with extended partition layout).
It is a heuristic.It's a number bigger than highest number of "sane"
partitions but an amount of iteration which a computer can handle
easily.
I know that it's an arbitrary limit butusing a correct algorithm (e.g.
record all visited extended partitions offsets) would take place
almost uselessly and other solutions risk to have other problems (as
"invisible" partitions)
>
> --
> Robert Millan
>
>  The DRM opt-in fallacy: "Your data belongs to us. We will decide when (and
>  how) you may access your data; but nobody's threatening your freedom: we
>  still allow you to remove your data and not access it at all."
>
>
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> http://lists.gnu.org/mailman/listinfo/grub-devel
>



-- 
Regards
Vladimir 'phcoder' Serbinenko

Personal git repository: http://repo.or.cz/w/grub2/phcoder.git

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Pavel Roskin]

On Sat, 2009-07-25 at 18:56 +0200, Vladimir 'phcoder' Serbinenko wrote:
> On Sat, Jul 25, 2009 at 6:36 PM, Robert Millan<rmh@aybabtu.com> wrote:
> > On Fri, Jul 24, 2009 at 09:24:31PM +0200, Felix Zielcke wrote:
> >> +  loop = 0;
> >> +  while (loop < 100000)
> >> [...]
> >> +  if (loop == 100000)
> >> +    return grub_error (GRUB_ERR_BAD_PART_TABLE, "Corrupted partition table found.");
> >
> > What does this 100000 represent?  It looks like heuristic, but I'm missing
> > some context (I'm not familiar with extended partition layout).
> It is a heuristic.It's a number bigger than highest number of "sane"
> partitions but an amount of iteration which a computer can handle
> easily.
> I know that it's an arbitrary limit butusing a correct algorithm (e.g.
> record all visited extended partitions offsets) would take place
> almost uselessly and other solutions risk to have other problems (as
> "invisible" partitions)

Let's try to see the complete picture.  By the time we get 100000
partitions we are already in trouble, especially if running ls on a slow
terminal.  Reaching 100000 means we were wrong all along.

Links backwards between extended partition entries are more likely to be
due to data corruption than due to buggy partitoning tools.  OK, if you
want, let's support up to 10 backward links.  That's more than enough.

I would hate to get caught in another discussion about minor issues when
we have a real problem in that code.

GRUB only follows a single chain of extended partitions rather than a
tree of links.  I think the whole point in having the Linux extended
partition type is to allow it to coexist with an MS-DOS extended
partition.  That's a realistic scenario, unlike backward links.

-- 
Regards,
Pavel Roskin

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Vladimir 'phcoder' Serbinenko]

> Links backwards between extended partition entries are more likely to be
> due to data corruption than due to buggy partitoning tools.  OK, if you
> want, let's support up to 10 backward links.  That's more than enough.
I remembered a compact algorithm for detecting loops of such kind I
will implement it and submit a patch and we'll see how really compact
it is

-- 
Regards
Vladimir 'phcoder' Serbinenko

Personal git repository: http://repo.or.cz/w/grub2/phcoder.git

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Vladimir 'phcoder' Serbinenko]

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

On Sun, Jul 26, 2009 at 12:35 AM, Vladimir 'phcoder'
Serbinenko<phcoder@gmail.com> wrote:
>> Links backwards between extended partition entries are more likely to be
>> due to data corruption than due to buggy partitoning tools.  OK, if you
>> want, let's support up to 10 backward links.  That's more than enough.
> I remembered a compact algorithm for detecting loops of such kind I
> will implement it and submit a patch and we'll see how really compact
> it is
Here it is. Strange that I haven't remembered this algorithm before.
Can someone test this patch?
>
> --
> Regards
> Vladimir 'phcoder' Serbinenko
>
> Personal git repository: http://repo.or.cz/w/grub2/phcoder.git
>



-- 
Regards
Vladimir 'phcoder' Serbinenko

Personal git repository: http://repo.or.cz/w/grub2/phcoder.git

[-- Attachment #2: loop.diff --]
[-- Type: text/plain, Size: 1639 bytes --]

diff --git a/ChangeLog b/ChangeLog
index 752bde8..eac8b8a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,7 @@
+2009-07-25  Vladimir Serbinenko  <phcoder@gmail.com>
+
+	* partmap/pc.c (pc_partition_map_iterate): Detect and break loops.
+
 2009-07-25  Felix Zielcke  <fzielcke@z-51.de>
 
 	* kern/file.c (grub_file_open): Revert to previous check with
diff --git a/partmap/pc.c b/partmap/pc.c
index 6f68ecf..e64f118 100644
--- a/partmap/pc.c
+++ b/partmap/pc.c
@@ -97,6 +97,9 @@ pc_partition_map_iterate (grub_disk_t disk,
   struct grub_pc_partition_mbr mbr;
   struct grub_pc_partition_disk_label label;
   struct grub_disk raw;
+  int labeln = 1, lastlabeln = 1;
+  /* Just not zero. It will be overwritten during first iteration. */
+  grub_disk_addr_t lastaddr = 0x1;
 
   /* Enforce raw disk access.  */
   raw = *disk;
@@ -117,6 +120,21 @@ pc_partition_map_iterate (grub_disk_t disk,
       if (grub_disk_read (&raw, p.offset, 0, sizeof (mbr), &mbr))
 	goto finish;
 
+      /* This is our loop-detection algorithm. It works the following way:
+	 It saves last position which was a power of two. Then it compares the
+	 saved value with a current one. This way it's guaranteed that the loop
+	 will be broken by at most third walk.
+       */
+      if (lastaddr == p.offset)
+	return grub_error (GRUB_ERR_BAD_PART_TABLE, "loop detected");
+
+      labeln++;
+      if (labeln == (lastlabeln << 1))
+	{
+	  lastaddr = p.offset;
+	  lastlabeln <<= 1;
+	}
+
       /* Check if it is valid.  */
       if (mbr.signature != grub_cpu_to_le16 (GRUB_PC_PARTITION_SIGNATURE))
 	return grub_error (GRUB_ERR_BAD_PART_TABLE, "no signature");

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Vladimir 'phcoder' Serbinenko]

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

On Sun, Jul 26, 2009 at 12:58 AM, Vladimir 'phcoder'
Serbinenko<phcoder@gmail.com> wrote:
> On Sun, Jul 26, 2009 at 12:35 AM, Vladimir 'phcoder'
> Serbinenko<phcoder@gmail.com> wrote:
>>> Links backwards between extended partition entries are more likely to be
>>> due to data corruption than due to buggy partitoning tools.  OK, if you
>>> want, let's support up to 10 backward links.  That's more than enough.
>> I remembered a compact algorithm for detecting loops of such kind I
>> will implement it and submit a patch and we'll see how really compact
>> it is
> Here it is. Strange that I haven't remembered this algorithm before.
> Can someone test this patch?
Small optimisation
>>
>> --
>> Regards
>> Vladimir 'phcoder' Serbinenko
>>
>> Personal git repository: http://repo.or.cz/w/grub2/phcoder.git
>>
>
>
>
> --
> Regards
> Vladimir 'phcoder' Serbinenko
>
> Personal git repository: http://repo.or.cz/w/grub2/phcoder.git
>



-- 
Regards
Vladimir 'phcoder' Serbinenko

Personal git repository: http://repo.or.cz/w/grub2/phcoder.git

[-- Attachment #2: loop.diff --]
[-- Type: text/plain, Size: 1525 bytes --]

diff --git a/ChangeLog b/ChangeLog
index 752bde8..eac8b8a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,7 @@
+2009-07-25  Vladimir Serbinenko  <phcoder@gmail.com>
+
+	* partmap/pc.c (pc_partition_map_iterate): Detect and break loops.
+
 2009-07-25  Felix Zielcke  <fzielcke@z-51.de>
 
 	* kern/file.c (grub_file_open): Revert to previous check with
diff --git a/partmap/pc.c b/partmap/pc.c
index 6f68ecf..165d3ac 100644
--- a/partmap/pc.c
+++ b/partmap/pc.c
@@ -97,6 +97,8 @@ pc_partition_map_iterate (grub_disk_t disk,
   struct grub_pc_partition_mbr mbr;
   struct grub_pc_partition_disk_label label;
   struct grub_disk raw;
+  int labeln = 0;
+  grub_disk_addr_t lastaddr;
 
   /* Enforce raw disk access.  */
   raw = *disk;
@@ -117,6 +119,18 @@ pc_partition_map_iterate (grub_disk_t disk,
       if (grub_disk_read (&raw, p.offset, 0, sizeof (mbr), &mbr))
 	goto finish;
 
+      /* This is our loop-detection algorithm. It works the following way:
+	 It saves last position which was a power of two. Then it compares the
+	 saved value with a current one. This way it's guaranteed that the loop
+	 will be broken by at most third walk.
+       */
+      if (labeln && lastaddr == p.offset)
+	return grub_error (GRUB_ERR_BAD_PART_TABLE, "loop detected");
+
+      labeln++;
+      if ((labeln & (labeln - 1)) == 0)
+	lastaddr = p.offset;
+
       /* Check if it is valid.  */
       if (mbr.signature != grub_cpu_to_le16 (GRUB_PC_PARTITION_SIGNATURE))
 	return grub_error (GRUB_ERR_BAD_PART_TABLE, "no signature");

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Felix Zielcke]

Am Sonntag, den 26.07.2009, 01:20 +0200 schrieb Vladimir 'phcoder'
Serbinenko:
> On Sun, Jul 26, 2009 at 12:58 AM, Vladimir 'phcoder'
> Serbinenko<phcoder@gmail.com> wrote:
> > On Sun, Jul 26, 2009 at 12:35 AM, Vladimir 'phcoder'
> > Serbinenko<phcoder@gmail.com> wrote:
> >>> Links backwards between extended partition entries are more likely
> to be
> >>> due to data corruption than due to buggy partitoning tools.  OK,
> if you
> >>> want, let's support up to 10 backward links.  That's more than
> enough.
> >> I remembered a compact algorithm for detecting loops of such kind I
> >> will implement it and submit a patch and we'll see how really
> compact
> >> it is
> > Here it is. Strange that I haven't remembered this algorithm before.
> > Can someone test this patch?
> Small optimisation 

This works with the partition table of the initial bug report:

/home/fz/grub/grub2-1.96+20090725/kern/partition.c:106: Detecting pc_partition_map...
/home/fz/grub/grub2-1.96+20090725/kern/disk.c:389: Reading `hd1'...
/home/fz/grub/grub2-1.96+20090725/partmap/pc.c:153: partition 0: flag 0x0, type 0x5, start 0x0, len 0x11177330
/home/fz/grub/grub2-1.96+20090725/partmap/pc.c:153: partition 1: flag 0x0, type 0x0, start 0x0, len 0x0
/home/fz/grub/grub2-1.96+20090725/partmap/pc.c:153: partition 2: flag 0x0, type 0x0, start 0x0, len 0x0
/home/fz/grub/grub2-1.96+20090725/partmap/pc.c:153: partition 3: flag 0x0, type 0x0, start 0x0, len 0x0
/home/fz/grub/grub2-1.96+20090725/kern/disk.c:389: Reading `hd1'...
/home/fz/grub/grub2-1.96+20090725/kern/partition.c:112: pc_partition_map detection failed.
/home/fz/grub/grub2-1.96+20090725/kern/disk.c:333: Closing `hd1'.



-- 
Felix Zielcke
Proud Debian Maintainer

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Robert Millan]

On Sun, Jul 26, 2009 at 12:58:59AM +0200, Vladimir 'phcoder' Serbinenko wrote:
> +      /* This is our loop-detection algorithm. It works the following way:
> +	 It saves last position which was a power of two. Then it compares the
> +	 saved value with a current one. This way it's guaranteed that the loop
> +	 will be broken by at most third walk.
> +       */
> +      if (lastaddr == p.offset)
> +	return grub_error (GRUB_ERR_BAD_PART_TABLE, "loop detected");
> +
> +      labeln++;
> +      if (labeln == (lastlabeln << 1))
> +	{
> +	  lastaddr = p.offset;
> +	  lastlabeln <<= 1;
> +	}

I would prefer something simpler, but if that's not possible, this is better
than hardcoding a number IMO.

Unless Pavel has any objection, I think it's ok.

-- 
Robert Millan

  The DRM opt-in fallacy: "Your data belongs to us. We will decide when (and
  how) you may access your data; but nobody's threatening your freedom: we
  still allow you to remove your data and not access it at all."

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Vladimir 'phcoder' Serbinenko]

On Tue, Jul 28, 2009 at 7:55 PM, Robert Millan<rmh@aybabtu.com> wrote:
> On Sun, Jul 26, 2009 at 12:58:59AM +0200, Vladimir 'phcoder' Serbinenko wrote:
>> +      /* This is our loop-detection algorithm. It works the following way:
>> +      It saves last position which was a power of two. Then it compares the
>> +      saved value with a current one. This way it's guaranteed that the loop
>> +      will be broken by at most third walk.
>> +       */
>> +      if (lastaddr == p.offset)
>> +     return grub_error (GRUB_ERR_BAD_PART_TABLE, "loop detected");
>> +
>> +      labeln++;
>> +      if (labeln == (lastlabeln << 1))
>> +     {
>> +       lastaddr = p.offset;
>> +       lastlabeln <<= 1;
>> +     }
>
> I would prefer something simpler, but if that's not possible, this is better
> than hardcoding a number IMO.
>
> Unless Pavel has any objection, I think it's ok.
Any problems with this one?
>
> --
> Robert Millan
>
>  The DRM opt-in fallacy: "Your data belongs to us. We will decide when (and
>  how) you may access your data; but nobody's threatening your freedom: we
>  still allow you to remove your data and not access it at all."
>
>
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> http://lists.gnu.org/mailman/listinfo/grub-devel
>



-- 
Regards
Vladimir 'phcoder' Serbinenko

Personal git repository: http://repo.or.cz/w/grub2/phcoder.git

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Vladimir 'phcoder' Serbinenko]

Ping?

On Sun, Aug 23, 2009 at 5:40 PM, Vladimir 'phcoder'
Serbinenko<phcoder@gmail.com> wrote:
> On Tue, Jul 28, 2009 at 7:55 PM, Robert Millan<rmh@aybabtu.com> wrote:
>> On Sun, Jul 26, 2009 at 12:58:59AM +0200, Vladimir 'phcoder' Serbinenko wrote:
>>> +      /* This is our loop-detection algorithm. It works the following way:
>>> +      It saves last position which was a power of two. Then it compares the
>>> +      saved value with a current one. This way it's guaranteed that the loop
>>> +      will be broken by at most third walk.
>>> +       */
>>> +      if (lastaddr == p.offset)
>>> +     return grub_error (GRUB_ERR_BAD_PART_TABLE, "loop detected");
>>> +
>>> +      labeln++;
>>> +      if (labeln == (lastlabeln << 1))
>>> +     {
>>> +       lastaddr = p.offset;
>>> +       lastlabeln <<= 1;
>>> +     }
>>
>> I would prefer something simpler, but if that's not possible, this is better
>> than hardcoding a number IMO.
>>
>> Unless Pavel has any objection, I think it's ok.
> Any problems with this one?
>>
>> --
>> Robert Millan
>>
>>  The DRM opt-in fallacy: "Your data belongs to us. We will decide when (and
>>  how) you may access your data; but nobody's threatening your freedom: we
>>  still allow you to remove your data and not access it at all."
>>
>>
>> _______________________________________________
>> Grub-devel mailing list
>> Grub-devel@gnu.org
>> http://lists.gnu.org/mailman/listinfo/grub-devel
>>
>
>
>
> --
> Regards
> Vladimir 'phcoder' Serbinenko
>
> Personal git repository: http://repo.or.cz/w/grub2/phcoder.git
>



-- 
Regards
Vladimir 'phcoder' Serbinenko

Personal git repository: http://repo.or.cz/w/grub2/phcoder.git

Re: [PATCH] fix an infinite loop with a corrupted pc partition table

[Pavel Roskin]

On Sun, 2009-08-23 at 17:40 +0200, Vladimir 'phcoder' Serbinenko wrote:
> > I would prefer something simpler, but if that's not possible, this is better
> > than hardcoding a number IMO.
> >
> > Unless Pavel has any objection, I think it's ok.
> Any problems with this one?

No objections.

-- 
Regards,
Pavel Roskin