: grub: Fix ofdisk disk cache corruption.
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
@@ -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
Quoted 5 lines · David Miller
The ieee1275 ofdisk driver doesn't use a unique value for
disk->idso 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
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->idso 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.
Quoted 28 lines · David Miller
From: Pavel Roskin <[email protected]>
Date: Sun, 12 Apr 2009 02:29:15 -0400Quoted 10 lines · David Miller
Quoted 5 lines
The ieee1275 ofdisk driver doesn't use a unique value for
disk->idso 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
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 -0400Quoted 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.
Quoted 28 lines · David Miller
From: phcoder <[email protected]>
Date: Sun, 12 Apr 2009 12:44:10 +0200Quoted 10 lines
Quoted 8 lines · David Miller
From: Pavel Roskin <[email protected]>
Date: Sun, 12 Apr 2009 02:29:15 -0400Quoted 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
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.
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
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.