Messages in this thread | | | Subject | Re: Lockless file reading | From | Timo Sirainen <> | Date | Thu, 28 Aug 2003 11:57:18 +0300 |
| |
On Thu, 2003-08-28 at 09:13, Jamie Lokier wrote: > Timo Sirainen wrote: > > I'm sure someone has figured out a way to make a checksum of data that > > can detect if there's even a single bit wrong, if the checksum is > > allowed to take as much space as the data itself. I should read more > > about algorithms.. > > You said that MD5 wasn't strong enough, and you would like a guarantee.
Yes. I don't really like it if my program heavily relies on something that can go wrong in some situations.
> You won't find a guarantee unless you are prepared to use memory > barriers in your code. _Any_ checksum is going to have a chance of > false validation if you are doing out-of-order reads which can observe > parts of the old and new data, and parts of the old and new checksum.
Not really. With {b1, b2, b1 xor b2} it doesn't matter what you read or write first, no matter what the old data was. If they match, the result is always either old or new.
If I want to get a checksum of 4 bytes then, I have to divide them into two parts. Using the b1^b2 I can know if either one of them is valid, but I can't know if they belong together.
Assuming that it's always either the previous one or the new one, I think (once again :) that it's possible to check that by getting mixed checksums: data = ABCD, c1 = A^B, c2 = C^D, c3 = A^C, c4 = B^D.
Except that the old data that read() sees could be even older than the previous value. Maybe here works the growing xor-byte. I haven't thought that far yet.
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |