Prebinding for DragonFly/FreeBSD-4

Simon 'corecode' Schubert corecode at fs.ei.tum.de
Sat Sep 13 13:06:40 PDT 2003


Lately Matthew Dillon told:

>     My one issue is with the hash function... 32 bits isn't enough, I
>     would prefer a 64 bit hash (as a minimum).  This is from my
>     experience with Diablo where even good 32 bit hash functions
>     produced collisions on news message-id's (and even 64 bit hash
>     functions in some cases).

Actually I don't think this is much of a problem because each ELF object
is also identified by its path component.

Also, if I understood the paper right, the collision bound can easily be
approximated by the number of hashed blocks.

Let's take libc.so. As RTLD is hashing on DT_REL[A], we get about 13KB
data. This is about 3.3e3 blocks (each 32 bit).
With a collision bound at n*2e-28 we get a collision propability at
3.3e3*2e-28 = 6.6e-25 which is 1:1500000000000000000000000.

But, of course, the hash function can be changed, or (what the authors
suppose) used twice with different hash keys.

cheers
  simon
 
-- 
/"\   http://corecode.ath.cx/#donate
\ /
 \     ASCII Ribbon Campaign
/ \  Against HTML Mail and News
Attachment:
pgp00012.pgp
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pgp00012.pgp
Type: application/octet-stream
Size: 189 bytes
Desc: "Description: PGP signature"
URL: <http://lists.dragonflybsd.org/pipermail/kernel/attachments/20030913/4e8ca752/attachment-0015.obj>


More information about the Kernel mailing list