Date: Thu, 28 Aug 2003 07:13:33 +0100
From: Jamie Lokier <jamie@shareable.org>
To: Timo Sirainen <tss@iki.fi>
Cc: root@chaos.analogic.com, Martin Konold <martin.konold@erfrakon.de>,
       linux-kernel@vger.kernel.org
Subject: Re: Lockless file reading
Message-ID: <20030828061333.GA5822@mail.jlokier.co.uk>
References: <20030828015027.GA4715@mail.jlokier.co.uk> <3217CEE6-D906-11D7-A165-000393CC2E90@iki.fi>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <3217CEE6-D906-11D7-A165-000393CC2E90@iki.fi>
User-Agent: Mutt/1.4.1i
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1002
Lines: 25

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.

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.

> How about checksum[n] = data[n-1] ^ data[n]? That looks like it would 
> work.

Consider when the data {1,0,1,0} is replaced by {2,0,2,0}.

-- Jamie

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