<br><div class="gmail_quote">On Wed, Feb 25, 2009 at 8:20 PM, Chinmay Kamat <span dir="ltr"><<a href="mailto:chinmaykamat@gmail.com">chinmaykamat@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
We had thought of using a smaller hash function. However the following<br>
issue arises ---  hash value of a block being written to disk is<br>
calculated and compared in the tree index. If a match is found, we are<br>
never sure if the blocks are identical or its a hash collision.</blockquote><div><br>Still, you're not sure with 512bits hash...<br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
 So we<br>
need to do a byte by byte comparison of the 2 blocks- current block<br>
being written and the block pointed to by matching tree entry. This<br>
would  mean doing disk read for reading the block pointed to by tree<br>
entry. So each detection of duplicate block will have an overhead of a<br>
block read.<br>
</blockquote><div><br>Yes but if you process block asyncronously and we make sure that the block list processed is seek-friendly this should not cost that much, and maybe block to compare with is in cache...<br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>
On the other hand, in case of a larger hash (SHA1) when 2 hash values match,<br>
the blocks should be duplicates, assuming the chances of collision<br>
with large hashes<br>
are very remote. Probably more remote than hw failure.</blockquote><div><br>Very true. Would it be difficult to add block compare to your current implementation ? If not, let people choosing in the final patch is perhaps a good option ? what do to think ?<br>
<br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br>
The tree contains only the first 64 bits of the SHA1 hash,<br>
so there is some optimization. ( we are working on handling collisions here).<br>
<br>
About the SHA1 implementation, as Daniel mentioned in his mail, we<br>
will be looking at<br>
implementations other than openssl before the kernel port.<br>
<br>
Regards,<br>
<br>
Gaurav Tungatkar<br>
<font color="#888888">Chinmay Kamat<br>
Kushal Dalmia<br>
Amey Magar<br>
</font><div><div></div><div class="Wj3C7c"><br>
_______________________________________________<br>
Tux3 mailing list<br>
<a href="mailto:Tux3@tux3.org">Tux3@tux3.org</a><br>
<a href="http://mailman.tux3.org/cgi-bin/mailman/listinfo/tux3" target="_blank">http://mailman.tux3.org/cgi-bin/mailman/listinfo/tux3</a><br>
</div></div></blockquote></div><br>