Date: Wed, 10 May 2000 22:56:41 -0400 (EDT)
From: Erez Zadok <[EMAIL PROTECTED]>
It depends what you mean by "reasonable way" and "good way". I've done it
in my prototype implementation of unionfs which uses fan-out stackable f/s:
(1) you read directory 1, and store the names you see in a hash table.
(2) as you read each entry from subsequent directories, you check if it's in
the hash table. If it is, skip it; if it's not, add it to the getdents
output buf, and add the entry to the hash-table.
This was a simple design and easy to implement. Yes it added overhead to
readdir(2) but not as much as you'd think. It was certainly not "horribly
slow", nor did it chew up lots of ram. I tried it on several directories
with several dozen entries each (i.e., typical directory sizes), not on
directories with thousands or more entries.
You do need to make sure you've coded things defensively so that the
kernel doesn't consume all available memory and then do something silly
like crash/thrash the system as a result of someone (possibly
maliciously, possibly innocently mounting a squid cache as unionfs
without knowing what might happen) mounting your unionfs on a directiry
with tens of thousands of entries. At the very least readdir should
fail gracefully, and not kill the system in a case like that.
A scheme you might consider, which is related to using a hash table, is
one which I first saw used on a spelling checker on a Z-80 CP/M
machine. What it did was to build a huge bit-array, and for each word
that was entered into the dictionary, seven different hashes were
calculated on that word, and a bit was set in the bit-array using each
of the seven different hashes as an index into the array. When you
wanted to check to see if a word was in the dictionary, you simply
calculated the seven hashes, and then checked to make sure all of the
positions in the bit-array identified by the seven hash values were
set.
The advantage of such a scheme is that amount of memory used is
constant, regardless of how many entries are in the dictionary. As the
number of entries in the dictionary go up, the chances of false
positives go up, but if the dictionary is decently sized, and the hash
functions are decent ones, it can work fairly well. This can still
take a lot of memory, but it scales better for really large
directories. (And it's a really cool algorithm :-)
If you're determined to do the duplicate elimination in the kernel, you
might want to think about using some kind of scheme like that to keep
the memory usage under control. Keep in mind that whatever data
structures we use, we need to create one for each opendir() that gets
called. So a malicious or badly written program could accidentally or
deliberate suddenly cause the kernel to consume a huge amount of
unswappable kernel data memory.
- Ted
