[PATCH]: grub: Fix ofdisk disk cache corruption.

[PATCH]: grub: Fix ofdisk disk cache corruption.

[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.

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  <davem@davemloft.net>

	* 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(-)

diff --git a/disk/ieee1275/ofdisk.c b/disk/ieee1275/ofdisk.c
index fec56be..a56433d 100644
--- a/disk/ieee1275/ofdisk.c
+++ b/disk/ieee1275/ofdisk.c
@@ -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;
 }
 
-- 
1.6.2.2

Re: [PATCH]: grub: Fix ofdisk disk cache corruption.

[Pavel Roskin]

On Sat, 2009-04-11 at 01:08 -0700, David Miller wrote:
> 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.  

> +#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.

> +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.

> +  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.

-- 
Regards,
Pavel Roskin

Re: [PATCH]: grub: Fix ofdisk disk cache corruption.

[David Miller]

From: Pavel Roskin <proski@gnu.org>
Date: Sun, 12 Apr 2009 02:29:15 -0400

> On Sat, 2009-04-11 at 01:08 -0700, David Miller wrote:
>> 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.  
> 
>> +#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?

> 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.

> 
>> +  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.

Re: [PATCH]: grub: Fix ofdisk disk cache corruption.

[phcoder]

David Miller wrote:
> From: Pavel Roskin <proski@gnu.org>
> Date: Sun, 12 Apr 2009 02:29:15 -0400
> 
>> On Sat, 2009-04-11 at 01:08 -0700, David Miller wrote:
>>> 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.  
>>
>>> +#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.
> 
This is so called "survivorship bias". If this hash generated a 
collision for you you would already have changed it
> 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
>> 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
> 
>>> +  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
> Grub-devel@gnu.org
> http://lists.gnu.org/mailman/listinfo/grub-devel


-- 

Regards
Vladimir 'phcoder' Serbinenko

Re: [PATCH]: grub: Fix ofdisk disk cache corruption.

[David Miller]

From: phcoder <phcoder@gmail.com>
Date: Sun, 12 Apr 2009 12:44:10 +0200

> David Miller wrote:
>> From: Pavel Roskin <proski@gnu.org>
>> Date: Sun, 12 Apr 2009 02:29:15 -0400
>> 
>>> On Sat, 2009-04-11 at 01:08 -0700, David Miller wrote:
>> 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.

>>> 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.

Re: [PATCH]: grub: Fix ofdisk disk cache corruption.

[phcoder]

David Miller wrote:
> From: phcoder <phcoder@gmail.com>
> Date: Sun, 12 Apr 2009 12:44:10 +0200
> 
>> David Miller wrote:
>>> From: Pavel Roskin <proski@gnu.org>
>>> Date: Sun, 12 Apr 2009 02:29:15 -0400
>>>
>>>> On Sat, 2009-04-11 at 01:08 -0700, David Miller wrote:
>>> 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.
> 
>>>> 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

-- 

Regards
Vladimir 'phcoder' Serbinenko

Re: [PATCH]: grub: Fix ofdisk disk cache corruption.

[David Miller]

From: phcoder <phcoder@gmail.com>
Date: Mon, 13 Apr 2009 03:09:20 +0200

> David Miller wrote:
>> 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.

Re: [PATCH]: grub: Fix ofdisk disk cache corruption.

[Pavel Roskin]

On Sun, 2009-04-12 at 01:01 -0700, David Miller wrote:

> > 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.

-- 
Regards,
Pavel Roskin

Re: [PATCH]: grub: Fix ofdisk disk cache corruption.

[David Miller]

From: Pavel Roskin <proski@gnu.org>
Date: Sun, 12 Apr 2009 17:01:07 -0400

> 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.