Skip to contentSkip to conversation

: grub: Fix ofdisk disk cache corruption.

PATCH In review David Miller 3 participants 9 messages Apr 11, 2009 – Apr 13, 2009

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 : grub: Fix ofdisk disk cache corruption.

The ieee1275 ofdisk driver doesn't use a unique value for disk->id so it's really easy to get disk corruption. I was able to see such corruption by simply booting grub from one disk and booting a Linux kernel from another, both of which were on the same disk controller.

The solution implemented here is to create a hash table of OF device paths openned, and use the address of the hash table entry as disk->id

2009-04-11 David S. Miller <[email protected]>

* disk/ieee1275/ofdisk.c (struct ofdisk_hash_ent): New struct. (OFDISK_HASH_SZ): Define.
(ofdisk_hash): New hash table.
(ofdisk_hash_fn, ofdisk_hash_find, ofdisk_hash_add): New functions. (grub_ofdisk_open): Use ofdisk_hash_ent address as disk->id instead of device phandle which is not unique.

---
 disk/ieee1275/ofdisk.c |   70 +++++++++++++++++++++++++++++++++++++++++------
 1 files changed, 61 insertions(+), 9 deletions(-)
disk/ieee1275/ofdisk.c +61 -9
index fec56be..a56433d 100644
@@ -23,6 +23,53 @@
 #include <grub/ieee1275/ieee1275.h>
 #include <grub/ieee1275/ofdisk.h>
 
+struct ofdisk_hash_ent
+{
+  char *devpath;
+  struct ofdisk_hash_ent *next;
+};
+
+#define OFDISK_HASH_SZ	8
+static struct ofdisk_hash_ent *ofdisk_hash[OFDISK_HASH_SZ];
+
+static int
+ofdisk_hash_fn (const char *devpath)
+{
+  int hash = 0;
+  while (*devpath)
+    hash ^= *devpath++;
+  return (hash & (OFDISK_HASH_SZ - 1));
+}
+
+static struct ofdisk_hash_ent *
+ofdisk_hash_find (const char *devpath)
+{
+  struct ofdisk_hash_ent *p = ofdisk_hash[ofdisk_hash_fn(devpath)];
+
+  while (p)
+    {
+      if (!grub_strcmp (p->devpath, devpath))
+	break;
+      p = p->next;
+    }
+  return p;
+}
+
+static struct ofdisk_hash_ent *
+ofdisk_hash_add (char *devpath)
+{
+  struct ofdisk_hash_ent **head = &ofdisk_hash[ofdisk_hash_fn(devpath)];
+  struct ofdisk_hash_ent *p = grub_malloc(sizeof (*p));
+
+  if (p)
+    {
+      p->devpath = devpath;
+      p->next = *head;
+      *head = p;
+    }
+  return p;
+}
+
 static int
 grub_ofdisk_iterate (int (*hook) (const char *name))
 {
@@ -76,6 +123,7 @@ grub_ofdisk_open (const char *name, grub_disk_t disk)
 {
   grub_ieee1275_phandle_t dev;
   grub_ieee1275_ihandle_t dev_ihandle = 0;
+  struct ofdisk_hash_ent *op;
   char *devpath;
   /* XXX: This should be large enough for any possible case.  */
   char prop[64];
@@ -89,18 +137,26 @@ grub_ofdisk_open (const char *name, grub_disk_t disk)
   if (! grub_ieee1275_test_flag (GRUB_IEEE1275_FLAG_NO_PARTITION_0))
     grub_strcat (devpath, ":0");
 
-  grub_dprintf ("disk", "Opening `%s'.\n", devpath);
+  op = ofdisk_hash_find (devpath);
+  if (!op)
+    op = ofdisk_hash_add (devpath);
 
-  grub_ieee1275_open (devpath, &dev_ihandle);
+  grub_free (devpath);
+  if (!op)
+    return grub_errno;
+
+  grub_dprintf ("disk", "Opening `%s'.\n", op->devpath);
+
+  grub_ieee1275_open (op->devpath, &dev_ihandle);
   if (! dev_ihandle)
     {
       grub_error (GRUB_ERR_UNKNOWN_DEVICE, "Can't open device");
       goto fail;
     }
 
-  grub_dprintf ("disk", "Opened `%s' as handle %p.\n", devpath, (void *) dev_ihandle);
+  grub_dprintf ("disk", "Opened `%s' as handle %p.\n", op->devpath, (void *) dev_ihandle);
 
-  if (grub_ieee1275_finddevice (devpath, &dev))
+  if (grub_ieee1275_finddevice (op->devpath, &dev))
     {
       grub_error (GRUB_ERR_UNKNOWN_DEVICE, "Can't read device properties");
       goto fail;
@@ -124,20 +180,16 @@ grub_ofdisk_open (const char *name, grub_disk_t disk)
      is possible to use seek for this.  */
   disk->total_sectors = 0xFFFFFFFFUL;
 
-  /* XXX: Is it ok to use this?  Perhaps it is better to use the path
-     or some property.  */
-  disk->id = dev;
+  disk->id = (unsigned long) op;
 
   /* XXX: Read this, somehow.  */
   disk->has_partitions = 1;
   disk->data = (void *) dev_ihandle;
-  grub_free (devpath);
   return 0;
 
  fail:
   if (dev_ihandle)
     grub_ieee1275_close (dev_ihandle);
-  grub_free (devpath);
   return grub_errno;
 }
 
Signature · 1 line
1.6.2.2
#1 lore raw
Quoted 5 lines · David Miller

The ieee1275 ofdisk driver doesn't use a unique value for disk->id so it's really easy to get disk corruption. I was able to see such corruption by simply booting grub from one disk and booting a Linux kernel from another, both of which were on the same disk controller.

I hope you mean disk cache corruption, as in the subject, not disk corruption. GRUB only writes to disks to save environment variables, and it's done very carefully.

disk/ieee1275/ofdisk.c line 42

Quoted 11 lines
disk/ieee1275/ofdisk.c +11 -0
+#define OFDISK_HASH_SZ	8
+static struct ofdisk_hash_ent *ofdisk_hash[OFDISK_HASH_SZ];
+
+static int
+ofdisk_hash_fn (const char *devpath)
+{
+  int hash = 0;
+  while (*devpath)
+    hash ^= *devpath++;
+  return (hash & (OFDISK_HASH_SZ - 1));
+}

That's a 3 bit hash. The risk of collisions is very high. I would understand if you had 8 entries for the hash values, but the hash values themselves should be reasonably unique.

disk/ieee1275/ofdisk.c line 66

Quoted 9 lines
disk/ieee1275/ofdisk.c +9 -0
+static struct ofdisk_hash_ent *
+ofdisk_hash_add (char *devpath)
+{
+  struct ofdisk_hash_ent **head = &ofdisk_hash[ofdisk_hash_fn(devpath)];
+  struct ofdisk_hash_ent *p = grub_malloc(sizeof (*p));
+
+  if (p)
+    {
+      p->devpath = devpath;

If you can save the device names, then there is no point in using hashes. You can use (long)devpath.

disk/ieee1275/ofdisk.c grub_ofdisk_open (const char *name, grub_disk_t disk) · line 144

Quoted 5 lines
disk/ieee1275/ofdisk.c +3 -1
+  if (!op)
+    op = ofdisk_hash_add (devpath);
 
-  grub_ieee1275_open (devpath, &dev_ihandle);
+  grub_free (devpath);

But if you free the device names, then they are bad IDs. The probability of the same memory being reused for another name is high.

Perhaps I misunderstand something.

Signature · 2 lines
Regards,
Pavel Roskin
#2 lore raw

From: Pavel Roskin <[email protected]>
Date: Sun, 12 Apr 2009 02:29:15 -0400

Quoted 11 lines · David Miller
Quoted 5 lines

The ieee1275 ofdisk driver doesn't use a unique value for disk->id so it's really easy to get disk corruption. I was able to see such corruption by simply booting grub from one disk and booting a Linux kernel from another, both of which were on the same disk controller.

I hope you mean disk cache corruption, as in the subject, not disk corruption. GRUB only writes to disks to save environment variables, and it's done very carefully.

Quoted 15 lines

disk/ieee1275/ofdisk.c line 42

Quoted 11 lines
disk/ieee1275/ofdisk.c +11 -0
+#define OFDISK_HASH_SZ	8
+static struct ofdisk_hash_ent *ofdisk_hash[OFDISK_HASH_SZ];
+
+static int
+ofdisk_hash_fn (const char *devpath)
+{
+  int hash = 0;
+  while (*devpath)
+    hash ^= *devpath++;
+  return (hash & (OFDISK_HASH_SZ - 1));
+}

That's a 3 bit hash. The risk of collisions is very high. I would understand if you had 8 entries for the hash values, but the hash values themselves should be reasonably unique.

In my testing there weren't many collisions.

I think fixing disk cache corruption is more important than arguing over the distribution properties of the hash function I have choosen.

Right?

Quoted 2 lines

If you can save the device names, then there is no point in using hashes. You can use (long)devpath.

Sure we need the hash, to find path entries we've saved beforehand.

Quoted 11 lines

disk/ieee1275/ofdisk.c grub_ofdisk_open (const char *name, grub_disk_t disk) · line 144

Quoted 6 lines
disk/ieee1275/ofdisk.c +3 -1
+  if (!op)
+    op = ofdisk_hash_add (devpath);
 
-  grub_ieee1275_open (devpath, &dev_ihandle);
+  grub_free (devpath);

But if you free the device names, then they are bad IDs. The probability of the same memory being reused for another name is high.

Perhaps I misunderstand something.

The path we use is dup'd into the hash entries we create, and the hash entry path string is the one we use.

Therefore "devpath" is only needed across the ofdisk_hash_add() call.

#3 lore raw
Quoted 28 lines · David Miller

From: Pavel Roskin <[email protected]>
Date: Sun, 12 Apr 2009 02:29:15 -0400

Quoted 10 lines · David Miller
Quoted 5 lines

The ieee1275 ofdisk driver doesn't use a unique value for disk->id so it's really easy to get disk corruption. I was able to see such corruption by simply booting grub from one disk and booting a Linux kernel from another, both of which were on the same disk controller.

I hope you mean disk cache corruption, as in the subject, not disk corruption. GRUB only writes to disks to save environment variables, and it's done very carefully.

Quoted 14 lines

disk/ieee1275/ofdisk.c line 42

Quoted 11 lines
disk/ieee1275/ofdisk.c +11 -0
+#define OFDISK_HASH_SZ	8
+static struct ofdisk_hash_ent *ofdisk_hash[OFDISK_HASH_SZ];
+
+static int
+ofdisk_hash_fn (const char *devpath)
+{
+  int hash = 0;
+  while (*devpath)
+    hash ^= *devpath++;
+  return (hash & (OFDISK_HASH_SZ - 1));
+}

That's a 3 bit hash. The risk of collisions is very high. I would understand if you had 8 entries for the hash values, but the hash values themselves should be reasonably unique.

Quoted 2 lines

In my testing there weren't many collisions.

This is so called "survivorship bias". If this hash generated a collision for you you would already have changed it

Quoted 4 lines

I think fixing disk cache corruption is more important than arguing over the distribution properties of the hash function I have choosen.

Yes, but weak hash has exactly the same problem, just on other systems

Quoted 4 lines
Quoted 2 lines

If you can save the device names, then there is no point in using hashes. You can use (long)devpath.

Sure we need the hash, to find path entries we've saved beforehand.

You can maintain a table of devpathes in cache and use the index in this table as id. This way is the safest

Quoted 22 lines
Quoted 10 lines

disk/ieee1275/ofdisk.c grub_ofdisk_open (const char *name, grub_disk_t disk) · line 144

Quoted 6 lines
disk/ieee1275/ofdisk.c +3 -1
+  if (!op)
+    op = ofdisk_hash_add (devpath);
 
-  grub_ieee1275_open (devpath, &dev_ihandle);
+  grub_free (devpath);

But if you free the device names, then they are bad IDs. The probability of the same memory being reused for another name is high.

Perhaps I misunderstand something.

The path we use is dup'd into the hash entries we create, and the hash entry path string is the one we use.

Therefore "devpath" is only needed across the ofdisk_hash_add() call.

_______________________________________________
Grub-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/grub-devel

Signature · 2 lines
Regards
Vladimir 'phcoder' Serbinenko
#4 lore raw

From: phcoder <[email protected]>
Date: Sun, 12 Apr 2009 12:44:10 +0200

Quoted 10 lines
Quoted 8 lines · David Miller

From: Pavel Roskin <[email protected]>
Date: Sun, 12 Apr 2009 02:29:15 -0400

Quoted 1 line · David Miller

I think fixing disk cache corruption is more important than arguing over the distribution properties of the hash function I have choosen.

Yes, but weak hash has exactly the same problem, just on other systems

Nobody has even shown that the hash is actually weak or not effective in any particular case, theoretical or otherwise.

That's why it frustrates me that we're discussing this at all.

"That hash might not be good, only 3 bits of entropy" meanwhile we have a disk cache corrupt bug still unfixed.

Can't we bicker about these kinds of issues after the bug is fixed? And also, after some proof is given that the hash matters at all.

Priorities are definitely wrong here.

Quoted 5 lines
Quoted 3 lines
Quoted 2 lines

If you can save the device names, then there is no point in using hashes. You can use (long)devpath.

Sure we need the hash, to find path entries we've saved beforehand.

You can maintain a table of devpathes in cache and use the index in this table as id. This way is the safest

Ummm, that's essentially what my code does, except that the "index" is the address of the cached path entry itself.

#5 lore raw
Quoted 28 lines · David Miller

From: phcoder <[email protected]>
Date: Sun, 12 Apr 2009 12:44:10 +0200

Quoted 10 lines
Quoted 8 lines · David Miller

From: Pavel Roskin <[email protected]>
Date: Sun, 12 Apr 2009 02:29:15 -0400

Quoted 1 line · David Miller

I think fixing disk cache corruption is more important than arguing over the distribution properties of the hash function I have choosen.

Yes, but weak hash has exactly the same problem, just on other systems

Nobody has even shown that the hash is actually weak or not effective in any particular case, theoretical or otherwise.

That's why it frustrates me that we're discussing this at all.

"That hash might not be good, only 3 bits of entropy" meanwhile we have a disk cache corrupt bug still unfixed.

Can't we bicker about these kinds of issues after the bug is fixed? And also, after some proof is given that the hash matters at all.

Priorities are definitely wrong here.

Quoted 8 lines
Quoted 5 lines
Quoted 3 lines
Quoted 2 lines

If you can save the device names, then there is no point in using hashes. You can use (long)devpath.

Sure we need the hash, to find path entries we've saved beforehand.

You can maintain a table of devpathes in cache and use the index in this table as id. This way is the safest

Ummm, that's essentially what my code does, except that the "index" is the address of the cached path entry itself.

Sorry I totally misread your code. Now it's fine

Signature · 2 lines
Regards
Vladimir 'phcoder' Serbinenko
#6 lore raw

From: phcoder <[email protected]>
Date: Mon, 13 Apr 2009 03:09:20 +0200

Quoted 4 lines
Quoted 2 lines · David Miller

Ummm, that's essentially what my code does, except that the "index" is the address of the cached path entry itself.

Sorry I totally misread your code. Now it's fine

Thanks for your review, I've thus committed this bug fix.

#7 lore raw
In reply to David Miller
Quoted 11 lines · David Miller
Quoted 3 lines

That's a 3 bit hash. The risk of collisions is very high. I would understand if you had 8 entries for the hash values, but the hash values themselves should be reasonably unique.

In my testing there weren't many collisions.

I think fixing disk cache corruption is more important than arguing over the distribution properties of the hash function I have choosen.

Right?

It's not just about distribution properties. My impression is that your code misuses hashes as indices in a table. Let's make the hash 32-bit. That would make it harder to misuse.

Signature · 2 lines
Regards,
Pavel Roskin
#8 lore raw

From: Pavel Roskin <[email protected]>
Date: Sun, 12 Apr 2009 17:01:07 -0400

Quoted 3 lines

It's not just about distribution properties. My impression is that your code misuses hashes as indices in a table. Let's make the hash 32-bit. That would make it harder to misuse.

They aren't indices in the traditional sense, they are simply unique ID's just like the filesystem UUIDs grub also supports.

Their only purpose it to indicate uniqueness, nothing more.

Since we have to allocate in-memory objects to remember the previously used paths anyways, it is just the most convenient thing to do to use the address of the object.

Other disk drivers do this too, I'm not inventing anything nor doing anything strange here.