dm-csum: A new device mapper target that checks data integrity
Subsystems (2)
RFC PATCH 1/1 dm-csum: A new device mapper target that checks data integrity
Hi!
I'm writing this device mapper target that stores checksums on writes and verifies them on reads.
It's not widely tested, but you can run mke2fs on it and do basic file operations. The to-do list is still large, and most of it can be found within the code.
To test it, you will need to format the device using the (very rough) attached tool, and then create the dm device with something like:
echo 0 $SIZE csum $REALDEVICE 0 | dmsetup create $NAME
I think it can be useful for people who want to detect data corruption and are either using the block layer directly or a filesystem that doesn't check data integrity (which are most, if not all, of the popular ones today). Maybe it could also be used for testing the bio-integrity extensions, although at the moment it's completely independent and I haven't looked much, but it's on my to-do list.
It does NOT pretend to be useful for consistency checks for security purposes. Use something else if you do not want someone evil tampering with your data.
Comments are obviously welcome. There are also some questions embedded in the code, if anyone cares to answer any of them, I'd really appreciate it.
Thanks a lot,
Alberto
drivers/md/Kconfig +10 -0
@@ -258,6 +258,16 @@ config DM_DELAY If unsure, say N. +config DM_CSUM + tristate "Checksumming target (EXPERIMENTAL)" + depends on BLK_DEV_DM && EXPERIMENTAL + select CRC_CCITT + ---help--- + A target that stores checksums on writes, and verifies + them on reads. + + If unsure, say N. + config DM_UEVENT bool "DM uevents (EXPERIMENTAL)" depends on BLK_DEV_DM && EXPERIMENTAL
drivers/md/Makefile +1 -0
@@ -39,6 +39,7 @@ obj-$(CONFIG_DM_MULTIPATH) += dm-multipath.o dm-round-robin.o obj-$(CONFIG_DM_SNAPSHOT) += dm-snapshot.o obj-$(CONFIG_DM_MIRROR) += dm-mirror.o dm-log.o dm-region-hash.o obj-$(CONFIG_DM_ZERO) += dm-zero.o +obj-$(CONFIG_DM_CSUM) += dm-csum.o quiet_cmd_unroll = UNROLL $@ cmd_unroll = $(PERL) $(srctree)/$(src)/unroll.pl $(UNROLL) \
drivers/md/dm-csum.c new file +1281 -0
1,281 lines not on this page · raw message
/* Formats the given file for use by dm-csum */
/* Needed to use pwrite() */
#define _XOPEN_SOURCE 500
#include <stdio.h> /* printf() */
#include <stdlib.h> /* malloc() */
#include <unistd.h> /* pwrite() and friends */
#include <sys/types.h> /* open() */
#include <sys/stat.h> /* open() */
#include <fcntl.h> /* open() */
#include <stdint.h> /* uint8_t and friends */
#include <string.h> /* memset() */
/* simple definitions so we can copy-paste the structs from the kernel */ #define u8 uint8_t
#define __be16 uint16_t
#define __be32 uint32_t
/*
* Copied from the kernel definition, MUST match
*/
#define RESERVED_INITIAL_SECTORS_D 1
#define RESERVED_INITIAL_SECTORS_M 1
#define SECTORS_PER_IMD 62
struct imd_tuple {
__be16 crc;
__be16 flags;
__be32 tag;
} __attribute__ ((packed));struct imd_sector_header {
u8 last_updated;
u8 unused1;
__be16 crc;
__be32 unused3;
} __attribute__ ((packed));/* Format function to use when imd and data are on the same device */
int format_same(int fd, off_t total_size) {
int r;
off_t off;
unsigned char buf[1024];
struct imd_sector_header *m1, *m2;
memset(buf, 0, sizeof(buf));
m1 = (struct imd_sector_header *) buf;
m2 = (struct imd_sector_header *) (buf + 512);
m1->last_updated = 2;
m2->last_updated = 1;
off = RESERVED_INITIAL_SECTORS_D * 512;
while (off < total_size) {
r = pwrite(fd, buf, 1024, off);
if (r != 1024)
return -1;
off += 1024 + SECTORS_PER_IMD * 512;
}
return 0;
}int format_diff(int data_fd, int imd_fd, off_t total_size)
{
printf("Not implemented yet\n");
return 0;
}void usage()
{
printf("Use: mk-dm-csum same <device>\n");
printf(" or: mk-dm-csum diff <data device> <imd device>\n");
}int main(int argc, char **argv)
{
int fd, imd_fd;
off_t total_size;
int same;
if (argc < 3) {
usage();
return 1;
}
if (strcmp(argv[1], "same") == 0) {
same = 1;
} else if (strcmp(argv[1], "diff") == 0) {
same = 0;
} else {
usage();
return 1;
}
fd = open(argv[2], O_WRONLY);
if (fd < 0) {
perror("Error opening device");
return 1;
}
/* TODO: diff */
total_size = lseek(fd, 0, SEEK_END);
if (total_size == -1) {
perror("Error finding out the size");
return 1;
}
/* round down to a multiple of SECTORS_PER_IMD */
total_size -= total_size % SECTORS_PER_IMD;
if (same) {
if (format_same(fd, total_size) != 0) {
perror("Error formatting");
return 2;
}
} else {
if (format_diff(fd, imd_fd, total_size) != 0) {
perror("Error formatting");
return 2;
}
}
if (fsync(fd) != 0) {
perror("Error syncing data to disk");
return 3;
}
return 0;
}Quoted 27 lines · Alberto Bertogli
Hi!
I'm writing this device mapper target that stores checksums on writes and verifies them on reads.
It's not widely tested, but you can run mke2fs on it and do basic file operations. The to-do list is still large, and most of it can be found within the code.
To test it, you will need to format the device using the (very rough) attached tool, and then create the dm device with something like:
echo 0 $SIZE csum $REALDEVICE 0 | dmsetup create $NAME
I think it can be useful for people who want to detect data corruption and are either using the block layer directly or a filesystem that doesn't check data integrity (which are most, if not all, of the popular ones today). Maybe it could also be used for testing the bio-integrity extensions, although at the moment it's completely independent and I haven't looked much, but it's on my to-do list.
It does NOT pretend to be useful for consistency checks for security purposes. Use something else if you do not want someone evil tampering with your data.
Quoted 5 lines
Comments are obviously welcome. There are also some questions embedded in the code, if anyone cares to answer any of them, I'd really appreciate it.
Thanks a lot,
Alberto
I have not looked at your patch, but does this tie into the integrity logic that was added to mainline a few months ago?
I'm not sure if it should or not, but I am curious how it ties in.
Greg
Signature · 14 lines
Greg Freemyer Head of EDD Tape Extraction and Processing team Litigation Triage Solutions Specialist http://www.linkedin.com/in/gregfreemyer First 99 Days Litigation White Paper - http://www.norcrossgroup.com/forms/whitepapers/99%20Days%20whitepaper.pdf The Norcross Group The Intersection of Evidence & Technology http://www.norcrossgroup.com -- To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 7 lines · Greg Freemyer
Quoted 2 lines · Alberto Bertogli
I'm writing this device mapper target that stores checksums on writes and verifies them on reads.
I have not looked at your patch, but does this tie into the integrity logic that was added to mainline a few months ago?
At the moment it has no relation, but making dm-csum devices register with the bio integrity extensions is on my to-do list, and the on-disk format already reserves 32 bits for every 512-byte sector for tagging purposes.
Thanks,
Alberto
Quoted 26 lines · Alberto Bertogli
Hi!
I'm writing this device mapper target that stores checksums on writes and verifies them on reads.
It's not widely tested, but you can run mke2fs on it and do basic file operations. The to-do list is still large, and most of it can be found within the code.
To test it, you will need to format the device using the (very rough) attached tool, and then create the dm device with something like:
echo 0 $SIZE csum $REALDEVICE 0 | dmsetup create $NAME
I think it can be useful for people who want to detect data corruption and are either using the block layer directly or a filesystem that doesn't check data integrity (which are most, if not all, of the popular ones today). Maybe it could also be used for testing the bio-integrity extensions, although at the moment it's completely independent and I haven't looked much, but it's on my to-do list.
It does NOT pretend to be useful for consistency checks for security purposes. Use something else if you do not want someone evil tampering with your data.
Quoted 5 lines
Comments are obviously welcome. There are also some questions embedded in the code, if anyone cares to answer any of them, I'd really appreciate it.
Thanks a lot,
Alberto
How does that behave on crashes? Will checksums be out of sync with data? Will pending blocks recalculate their checksum?
MfG
Goswin
Quoted 6 lines · Goswin von Brederlow
Quoted 2 lines · Alberto Bertogli
I'm writing this device mapper target that stores checksums on writes and verifies them on reads.
How does that behave on crashes? Will checksums be out of sync with data? Will pending blocks recalculate their checksum?
It should behave well on crashes, the checksums should be in sync (see below), and there is no concept of "pending blocks".
Quoting from the docs (included at the beginning of the patch):
It stores an 8-byte "integrity metadata" ("imd", from now on) structure for each 512-byte data sector. imd structures are clustered in groups of 62 plus a small header, so they fit a sector (referred to as an "imd sector"). Every imd sector has a "brother", another adjacent imd sector, for consistency purposes (explained below). That means we devote two sectors to imd storage for every 62 data sectors.
[...]
To guarantee consistency, two imd sectors (named M1 and M2) are kept for every 62 data sectors, and the following procedure is used to update them when a write to a given sector is required:
- Read both M1 and M2.
- Find out (using information stored in their headers) which one is newer. Let's assume M1 is newer than M2.
- Update the M2 buffer to mark it's newer, and update the new data's CRC.
- Submit the write to M2, and then the write to the data, using a barrier to make sure the metadata is updated _after_ the data.
Accordingly, the read operations are handled as follows:
- Read both the data, M1 and M2.
- Find out which one is newer. Let's assume M1 is newer than M2.
- Calculate the data's CRC, and compare it to the one found in M1. If they match, the reading is successful. If not, compare it to the one found in M2. If they match, the reading is successful; otherwise, fail. If the read involves multiple sectors, it is possible that some of the correct CRCs are in M1 and some in M2.
The barrier will be (it's not done yet) replaced with serialized writes for cases where the underlying block device does not support them, or when the integrity metadata resides on a different block device than the data.
This scheme assumes writes to a single sector are atomic in the presence of normal crashes, which I'm not sure if it's something sane to assume in practise. If it's not, then the scheme can be modified to cope with that.
Thanks a lot,
Alberto
Quoted 12 lines · Alberto Bertogli
Quoted 6 lines · Goswin von Brederlow
Quoted 2 lines · Alberto Bertogli
I'm writing this device mapper target that stores checksums on writes and verifies them on reads.
How does that behave on crashes? Will checksums be out of sync with data? Will pending blocks recalculate their checksum?
To guarantee consistency, two imd sectors (named M1 and M2) are kept for every 62 data sectors, and the following procedure is used to update them when a write to a given sector is required:
Quoted 6 lines
- Read both M1 and M2.
- Find out (using information stored in their headers) which one is newer. Let's assume M1 is newer than M2.
- Update the M2 buffer to mark it's newer, and update the new data's CRC.
- Submit the write to M2, and then the write to the data, using a barrier to make sure the metadata is updated _after_ the data.
Consider that the disk writes the data and then the system crashes. Now you have the old checksum but the new data. The checksum is out of sync.
Don't you mean that M2 is written _before_ the data? That way you have the old checksum in M1 and the new in M2. One of them will match depending on wether the data gets written before a crash or not. That would be more consistent with your read operation below.
Quoted 11 lines
Accordingly, the read operations are handled as follows:
- Read both the data, M1 and M2.
- Find out which one is newer. Let's assume M1 is newer than M2.
- Calculate the data's CRC, and compare it to the one found in M1. If they match, the reading is successful. If not, compare it to the one found in M2. If they match, the reading is successful; otherwise, fail. If the read involves multiple sectors, it is possible that some of the correct CRCs are in M1 and some in M2.
Quoted 8 lines
The barrier will be (it's not done yet) replaced with serialized writes for cases where the underlying block device does not support them, or when the integrity metadata resides on a different block device than the data.
This scheme assumes writes to a single sector are atomic in the presence of normal crashes, which I'm not sure if it's something sane to assume in practise. If it's not, then the scheme can be modified to cope with that.
What happens if you have multiple writes to the same sector? (assuming you ment "before" above)
- user writes to sector
- queue up write for M1 and data1
- M1 writes
- user writes to sector
- queue up writes for M2 and data2
- data1 is thrown away as data2 overwrites it
- M2 writes
- system crashes
Now both M1 and M2 have a different checksum than the old data left on disk.
Can this happen?
MfG
Goswin
Quoted 20 lines · Goswin von Brederlow
Quoted 12 lines · Alberto Bertogli
Quoted 6 lines · Goswin von Brederlow
Quoted 2 lines · Alberto Bertogli
I'm writing this device mapper target that stores checksums on writes and verifies them on reads.
How does that behave on crashes? Will checksums be out of sync with data? Will pending blocks recalculate their checksum?
To guarantee consistency, two imd sectors (named M1 and M2) are kept for every 62 data sectors, and the following procedure is used to update them when a write to a given sector is required:
Quoted 6 lines
- Read both M1 and M2.
- Find out (using information stored in their headers) which one is newer. Let's assume M1 is newer than M2.
- Update the M2 buffer to mark it's newer, and update the new data's CRC.
- Submit the write to M2, and then the write to the data, using a barrier to make sure the metadata is updated _after_ the data.
Quoted 8 lines
Consider that the disk writes the data and then the system crashes. Now you have the old checksum but the new data. The checksum is out of sync.
Don't you mean that M2 is written _before_ the data? That way you have the old checksum in M1 and the new in M2. One of them will match depending on wether the data gets written before a crash or not. That would be more consistent with your read operation below.
Yes, the comment is wrong, thanks for noticing. That is how it's implemented.
Quoted 32 lines
Quoted 11 lines
Accordingly, the read operations are handled as follows:
- Read both the data, M1 and M2.
- Find out which one is newer. Let's assume M1 is newer than M2.
- Calculate the data's CRC, and compare it to the one found in M1. If they match, the reading is successful. If not, compare it to the one found in M2. If they match, the reading is successful; otherwise, fail. If the read involves multiple sectors, it is possible that some of the correct CRCs are in M1 and some in M2.Quoted 8 lines
The barrier will be (it's not done yet) replaced with serialized writes for cases where the underlying block device does not support them, or when the integrity metadata resides on a different block device than the data.
This scheme assumes writes to a single sector are atomic in the presence of normal crashes, which I'm not sure if it's something sane to assume in practise. If it's not, then the scheme can be modified to cope with that.
What happens if you have multiple writes to the same sector? (assuming you ment "before" above)
- user writes to sector
- queue up write for M1 and data1
- M1 writes
- user writes to sector
- queue up writes for M2 and data2
- data1 is thrown away as data2 overwrites it
- M2 writes
- system crashes
Quoted 4 lines
Now both M1 and M2 have a different checksum than the old data left on disk.
Can this happen?
No, parallel writes that affect the same metadata sectors will not be allowed. At the moment there is a rough lock which does not allow simultaneous updates at all, I plan to make that more fine-grained in the future.
Note that bios that affect more than one sector are just fine, since the metadata sector will be properly updated.
Thanks,
Alberto
Now I need to get a new harddisk so I can test this without risking live data. :)
MfG
Goswin
Hi Alberto,
+ * TODO: would it be better to have M1 and M2 apart, to improve the chances of
+ * recovery in case of a failure?
+ *
How do you guarantee consistency in case of any lost writes? Your checksum might hold an updated value while your data block might be lost or written to a wrong destination?
When implementing such integrity solutions, IMO, it is always advisable to handle such error conditions else this might lead to issues. Since, checksums are very tightly coupled with the data and any misleading can be quite dangerous unlike parity which can be recovered.
Calculate the data's CRC, and compare it to the one found in M1. If they
+ * match, the reading is successful. If not, compare it to the one found in
+ * M2. If they match, the reading is successful;
Also, I hope by M1 and M2 you refer to the entry for a particular block in the respective IMD sector. What kind of mechanism do you use to determine which is younger?
Is it the timestamp or some generation count?
I assume information is per_block_entry in the IMD sectors. Which I don't see in your implementation?
*
+ * The imd structure consists of:
+ * - 16 bit CRC (CCITT) (big endian) + * - 16 bit flags (big endian) + * - 32 bit tag
Correct me If I am missing something.
Quoted 10 lines · Goswin von Brederlow
Now I need to get a new harddisk so I can test this without risking live data. :)
MfG
Goswin
--
To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Signature · 9 lines
Regards, Sandeep. “To learn is to change. Education is a process that changes the learner.”
Hi,
I meant sectors and not blocks.
Quoted 10 lines · SandeepKsinha
Hi Alberto,
+ * TODO: would it be better to have M1 and M2 apart, to improve the chances of
+ * recovery in case of a failure?
+ *How do you guarantee consistency in case of any lost writes? Your checksum might hold an updated value while your data block might be lost or written to a wrong destination?
sector in place of block.
Quoted 6 lines
When implementing such integrity solutions, IMO, it is always advisable to handle such error conditions else this might lead to issues. Since, checksums are very tightly coupled with the data and any misleading can be quite dangerous unlike parity which can be recovered.
Quoted 9 lines
Calculate the data's CRC, and compare it to the one found in M1. If they
+ * match, the reading is successful. If not, compare it to the one found in
+ * M2. If they match, the reading is successful;Also, I hope by M1 and M2 you refer to the entry for a particular block in the respective IMD sector. What kind of mechanism do you use to determine which is younger?
Is it the timestamp or some generation count?
for a particular sector and not block.
Quoted 35 lines
I assume information is
per_block_entryin the IMD sectors. Which I don't see in your implementation?
*
+ * The imd structure consists of:
+ * - 16 bit CRC (CCITT) (big endian)
+ * - 16 bit flags (big endian)
+ * - 32 bit tagCorrect me If I am missing something.
Quoted 10 lines · Goswin von Brederlow
Now I need to get a new harddisk so I can test this without risking live data. :)
MfG
Goswin
--
To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html--
Regards,
Sandeep.“To learn is to change. Education is a process that changes the learner.”
Signature · 13 lines
Regards, Sandeep. “To learn is to change. Education is a process that changes the learner.” -- To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 9 lines · SandeepKsinha
Hi Alberto,
+ * TODO: would it be better to have M1 and M2 apart, to improve the chances of
+ * recovery in case of a failure?
+ *How do you guarantee consistency in case of any lost writes? Your checksum might hold an updated value while your data block might be lost or written to a wrong destination?
The module aims to detect corruption, not prevent or recover from it. If the write bio returns an error, it should be properly handled and propagated to the upper layers.
If it returns success but writes the wrong data to the disk, then there will be a mismatch between the checksum and the data at the destination, which will be detected when it is read.
If a write returns success but no write ever takes place on the disk, then dm-csum (as it is now) will not detect it; although I'm not sure if that qualifies as on-disk data corruption or is it a disk controller issue.
Quoted 5 lines
When implementing such integrity solutions, IMO, it is always advisable to handle such error conditions else this might lead to issues. Since, checksums are very tightly coupled with the data and any misleading can be quite dangerous unlike parity which can be recovered.
The code considers the possibility of bios failing, and propagates this information to the upper layers. If you see any part of the code that lacks error handling, please let me know so I can fix it.
Quoted 6 lines
Calculate the data's CRC, and compare it to the one found in M1. If they
+ * match, the reading is successful. If not, compare it to the one found in
+ * M2. If they match, the reading is successful;Also, I hope by M1 and M2 you refer to the entry for a particular block in the respective IMD sector. What kind of mechanism do you use
M1 and M2 refer to whole IMD sectors.
Quoted 5 lines
to determine which is younger?
Is it the timestamp or some generation count?I assume information is
per_block_entryin the IMD sectors. Which I don't see in your implementation?
It's per IMD sector. More specifically, struct imd_sector_header's last_updated contains the generation count for the entire IMD sector, which is used to determine which one is younger for updating purposes.
On reads, both IMD sectors are loaded and CRCs are verified against both.
Thanks a lot,
Alberto
Quoted 3 lines
If it returns success but writes the wrong data to the disk, then there will be a mismatch between the checksum and the data at the destination, which will be detected when it is read.
(or to the wrong place on the disk which for pre SATA is actually possibly more likely as the command transfers are not CRC protected on the cable - just slower, while the data is CRC protected). SATA fixes this.
Quoted 3 lines
If a write returns success but no write ever takes place on the disk, then dm-csum (as it is now) will not detect it; although I'm not sure if that qualifies as on-disk data corruption or is it a disk controller issue.
Does it matter to the poor victim ? At this point you get into putting mirrors on disks A & B with their integrity on the opposite pair so if one forgets to do I/O hopefully both won't.
To be honest if you are really really paranoid you don't do link layer checksumming anyway (which is what this is) you checksum in the apps using the data set. That protects you against lots of error cases in the memory/cache system and on network transmissions. On big clusters crunching enormous amounts of data all those 1 in 10^lots bit error rates become such that it's worth the effort.
Quoted 5 lines
It's per IMD sector. More specifically, struct imd_sector_header's
last_updatedcontains the generation count for the entire IMD sector, which is used to determine which one is younger for updating purposes.On reads, both IMD sectors are loaded and CRCs are verified against both.
Seems reasonably paranoid - drives will do things under you like commit data to disk out in a different order to the commands unless the cache gets flushed between them but the barrier code should do that bit.
Alan
Quoted 65 lines · On Tuesday May 26, [email protected] wrote:
Quoted 20 lines · Goswin von Brederlow
Quoted 12 lines · Alberto Bertogli
Quoted 6 lines · Goswin von Brederlow
Quoted 2 lines · Alberto Bertogli
I'm writing this device mapper target that stores checksums on writes and verifies them on reads.
How does that behave on crashes? Will checksums be out of sync with data? Will pending blocks recalculate their checksum?
To guarantee consistency, two imd sectors (named M1 and M2) are kept for every 62 data sectors, and the following procedure is used to update them when a write to a given sector is required:
Quoted 6 lines
- Read both M1 and M2.
- Find out (using information stored in their headers) which one is newer. Let's assume M1 is newer than M2.
- Update the M2 buffer to mark it's newer, and update the new data's CRC.
- Submit the write to M2, and then the write to the data, using a barrier to make sure the metadata is updated _after_ the data.Quoted 8 lines
Consider that the disk writes the data and then the system crashes. Now you have the old checksum but the new data. The checksum is out of sync.
Don't you mean that M2 is written _before_ the data? That way you have the old checksum in M1 and the new in M2. One of them will match depending on wether the data gets written before a crash or not. That would be more consistent with your read operation below.
Yes, the comment is wrong, thanks for noticing. That is how it's implemented.
Quoted 32 lines
Quoted 11 lines
Accordingly, the read operations are handled as follows:
- Read both the data, M1 and M2.
- Find out which one is newer. Let's assume M1 is newer than M2.
- Calculate the data's CRC, and compare it to the one found in M1. If they match, the reading is successful. If not, compare it to the one found in M2. If they match, the reading is successful; otherwise, fail. If the read involves multiple sectors, it is possible that some of the correct CRCs are in M1 and some in M2.Quoted 8 lines
The barrier will be (it's not done yet) replaced with serialized writes for cases where the underlying block device does not support them, or when the integrity metadata resides on a different block device than the data.
This scheme assumes writes to a single sector are atomic in the presence of normal crashes, which I'm not sure if it's something sane to assume in practise. If it's not, then the scheme can be modified to cope with that.
What happens if you have multiple writes to the same sector? (assuming you ment "before" above)
- user writes to sector
- queue up write for M1 and data1
- M1 writes
- user writes to sector
- queue up writes for M2 and data2
- data1 is thrown away as data2 overwrites it
- M2 writes
- system crashes
Quoted 8 lines
Quoted 4 lines
Now both M1 and M2 have a different checksum than the old data left on disk.
Can this happen?
No, parallel writes that affect the same metadata sectors will not be allowed. At the moment there is a rough lock which does not allow simultaneous updates at all, I plan to make that more fine-grained in the future.
Can I suggest a variation on the above which, I think, can cause a problem.
- user writes data-A' to sector-A (which currently contains data-A)
- queue up write for M1 and data-A'
- M1 is written correctly.
- power fails (before data-A' is written)
reboot
- read sector-A, find data-A which matches checksum on M2, so success.
So everything is working perfectly so far...
- write sector-B (in same 62-sector range as sector-A).
- queue up write for M2 and data-B
- those writes complete
- read sector-A. find data-A, which doesn't match M1 (that has data-A') and doesn't match M2 (which is mostly a copy of M1), so the read fails.
i.e. you get a situation where writing one sector can cause another sector to spontaneously fail.
NeilBrown
Quoted 38 lines · Neil Brown
Quoted 17 lines · On Tuesday May 26, [email protected] wrote:
Quoted 16 lines · Goswin von Brederlow
Quoted 3 lines
This scheme assumes writes to a single sector are atomic in the presence of normal crashes, which I'm not sure if it's something sane to assume in practise. If it's not, then the scheme can be modified to cope with that.
What happens if you have multiple writes to the same sector? (assuming you ment "before" above)
- user writes to sector
- queue up write for M1 and data1
- M1 writes
- user writes to sector
- queue up writes for M2 and data2
- data1 is thrown away as data2 overwrites it
- M2 writes
- system crashesQuoted 8 lines
Quoted 4 lines
Now both M1 and M2 have a different checksum than the old data left on disk.
Can this happen?
No, parallel writes that affect the same metadata sectors will not be allowed. At the moment there is a rough lock which does not allow simultaneous updates at all, I plan to make that more fine-grained in the future.
Can I suggest a variation on the above which, I think, can cause a problem.
- user writes data-A' to sector-A (which currently contains data-A)
- queue up write for M1 and data-A'
- M1 is written correctly.
- power fails (before data-A' is written)
reboot
- read sector-A, find data-A which matches checksum on M2, so success.
Quoted 8 lines
So everything is working perfectly so far...
- write sector-B (in same 62-sector range as sector-A).
- queue up write for M2 and data-B
- those writes complete
- read sector-A. find data-A, which doesn't match M1 (that has data-A') and doesn't match M2 (which is mostly a copy of M1), so the read fails.
The thing is that M2 is not a copy of M1. When updating M2 for data-B, the procedure is not "copy M1, update sector-B's checksum, write" but "read M2, update sector-B's checksum, write". So as long as there are no writes to sector-A, M1 will have the incorrect checksum and M2 will have the correct one, regardless of writes to the other sectors.
However, a troubling scenario based on yours could be:
- M2 has the right checksum but is older, M1 has the wrong checksum but is newer.
- user writes data-A'' to sector'A
- queue up write for M2 (chosen because it is older)
- M2 is written correctly
- power fails before data-A'' is written
At that point, data-A is written at sector-A, but both M1 and M2 have incorrect checksums for it.
I'll try to come up with a better scheme that copes with this kind of scenarios and post an updated patch.
Thanks a lot,
Alberto
Quoted 63 lines · Alberto Bertogli
Quoted 38 lines · Neil Brown
Quoted 17 lines · On Tuesday May 26, [email protected] wrote:
Quoted 16 lines · Goswin von Brederlow
Quoted 3 lines
This scheme assumes writes to a single sector are atomic in the presence of normal crashes, which I'm not sure if it's something sane to assume in practise. If it's not, then the scheme can be modified to cope with that.
What happens if you have multiple writes to the same sector? (assuming you ment "before" above)
- user writes to sector
- queue up write for M1 and data1
- M1 writes
- user writes to sector
- queue up writes for M2 and data2
- data1 is thrown away as data2 overwrites it
- M2 writes
- system crashesQuoted 8 lines
Quoted 4 lines
Now both M1 and M2 have a different checksum than the old data left on disk.
Can this happen?
No, parallel writes that affect the same metadata sectors will not be allowed. At the moment there is a rough lock which does not allow simultaneous updates at all, I plan to make that more fine-grained in the future.
Can I suggest a variation on the above which, I think, can cause a problem.
- user writes data-A' to sector-A (which currently contains data-A)
- queue up write for M1 and data-A'
- M1 is written correctly.
- power fails (before data-A' is written)
reboot
- read sector-A, find data-A which matches checksum on M2, so success.Quoted 8 lines
So everything is working perfectly so far...
- write sector-B (in same 62-sector range as sector-A).
- queue up write for M2 and data-B
- those writes complete
- read sector-A. find data-A, which doesn't match M1 (that has data-A') and doesn't match M2 (which is mostly a copy of M1), so the read fails.The thing is that M2 is not a copy of M1. When updating M2 for data-B, the procedure is not "copy M1, update sector-B's checksum, write" but "read M2, update sector-B's checksum, write". So as long as there are no writes to sector-A, M1 will have the incorrect checksum and M2 will have the correct one, regardless of writes to the other sectors.
However, a troubling scenario based on yours could be:
- M2 has the right checksum but is older, M1 has the wrong checksum but is newer.
- user writes data-A'' to sector'A
- queue up write for M2 (chosen because it is older)
- M2 is written correctly
- power fails before data-A'' is written
Quoted 8 lines
At that point, data-A is written at sector-A, but both M1 and M2 have incorrect checksums for it.
I'll try to come up with a better scheme that copes with this kind of scenarios and post an updated patch.
Thanks a lot,
Alberto
When the newer block has the wrong checksum you first need to correct that. If you find a wrong checksum on read that is easy to do. But you won't detect this on writes.
One solution I can think of is this:
- user writes to sector A
- compare checksum of sector A in M1 and M2
if checksums differ:
- read sector A and calculate checksum
- if M1 has the right checksum update M2
- wait
- write new checksum to M1
- wait
- write data to sector A
- wait
- write new checksum to M2
MfG
Goswin
RFC PATCH v2 1/1 dm-csum: A new device mapper target that checks data integrity
In reply to Alberto BertogliQuoted 2 lines · Alberto Bertogli
I'm writing this device mapper target that stores checksums on writes and verifies them on reads.
Here's a new version of the patch, against current Linus' git tree. The most important change from the first one is the support of the bio-integrity extensions.
As with the previous version, it's been only mildly tested (creation of a filesystem and basic file manipulation, over a loop device).
Thanks a lot,
Alberto
drivers/md/Kconfig +10 -0
@@ -258,6 +258,16 @@ config DM_DELAY If unsure, say N. +config DM_CSUM + tristate "Checksumming target (EXPERIMENTAL)" + depends on BLK_DEV_DM && EXPERIMENTAL + select CRC_CCITT + ---help--- + A target that stores checksums on writes, and verifies + them on reads. + + If unsure, say N. + config DM_UEVENT bool "DM uevents (EXPERIMENTAL)" depends on BLK_DEV_DM && EXPERIMENTAL
drivers/md/Makefile +1 -0
@@ -39,6 +39,7 @@ obj-$(CONFIG_DM_MULTIPATH) += dm-multipath.o dm-round-robin.o obj-$(CONFIG_DM_SNAPSHOT) += dm-snapshot.o obj-$(CONFIG_DM_MIRROR) += dm-mirror.o dm-log.o dm-region-hash.o obj-$(CONFIG_DM_ZERO) += dm-zero.o +obj-$(CONFIG_DM_CSUM) += dm-csum.o quiet_cmd_unroll = UNROLL $@ cmd_unroll = $(PERL) $(srctree)/$(src)/unroll.pl $(UNROLL) \
drivers/md/dm-csum.c new file +1537 -0
1,537 lines not on this page · raw message