On Sun, Jul 26, 2009 at 12:35 AM, Vladimir 'phcoder'
Serbinenko<phco...@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
diff --git a/ChangeLog b/ChangeLog
index 752bde8..eac8b8a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,7 @@
+2009-07-25 Vladimir Serbinenko <phco...@gmail.com>
+
+ * partmap/pc.c (pc_partition_map_iterate): Detect and break loops.
+
2009-07-25 Felix Zielcke <fziel...@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");
_______________________________________________
Grub-devel mailing list
Grub-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/grub-devel
