Date: Mon, 4 Jun 2012 13:54:50 +0300 From: Efstratios Karatzas <gpf.kira@gmail.com> To: soc-status@freebsd.org Subject: Kernel Level File Integrity Checker report #2 Message-ID: <CAHywV0jySmwx5rkXcQcZj-T65XshJuBCGvQmh3xB3trpwUvjuQ@mail.gmail.com>
next in thread | raw e-mail | index | archive | help
During week #2: * sbin/pefs now uses an ioctl() to grab cipher-text for each 4k block from kernel, which is then used to generate the checksum. * A major concern of mine was to have a hash table that would allow us the fastest lookups possible since lookup is the only operation performed by the kernel fs driver. I ended up implementing cuckoo hashing for that reason; this way, worst lookup case is 2 cache read misses. With cuckoo hashing, we also end up spending 4 times less memory than with separate chaining for the index that is kept in kernel heap. Cuckoo hashing does have some drawbacks like slow insertion time that may result in an infinite loop. I used a python script to experiment and see how probable it is to fall in an infinite loop. For table sizes of next_prime(n + n * 15%) where n = total elements, there's a 1.5% chance. If that happens, we simply allocate new, larger tables and try again with the same hash functions until we succeed. The chance to fall in an infinite loop twice in a row is 1.5% * 1.5% = 0.225%. Since the hash table is created only once in userland during filesystem generation phase, we don't mind the extra time that is spent at this stage to generate the tables. Proper handling of this infinite loop case is still a todo. -- Efstratios "GPF" Karatzas
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CAHywV0jySmwx5rkXcQcZj-T65XshJuBCGvQmh3xB3trpwUvjuQ>