[Pvfs2-developers] duplicate entries in directory listing

[Sam Lang]

On Oct 9, 2006, at 3:23 PM, Phil Carns wrote:

> Phil Carns wrote:
>>> I started thinking about some more possible ideas, but I realized  
>>> after looking closer at the code that I don't actually see why  
>>> duplicates would occur in the first place with the algorithm that  
>>> is being used :)  I apologize if this has been discussed a few  
>>> times already, but could we walk through it one more time?
>>>
>>> I know that the request protocol uses a token (integer based) to  
>>> keep track of position.  However, the pcache converts this into a  
>>> particular key based on where the last iteration left off.  This  
>>> key contains the handle as well as the alphanumeric name of the  
>>> entry.
>>>
>>> Trove then does a c_get on that key with the DB_SET flag, which  
>>> should put the cursor at the proper position.  If the entry has  
>>> been deleted (which is not happening in my case- I am only  
>>> creating files), then it retries the c_get with the DB_SET_RANGE  
>>> flag which should set the cursor at the next position.  "next" in  
>>> this case is defined by the comparison function,  
>>> PINT_trove_dbpf_keyval_compare().
>>>
>>> The keyval_comare() function sorts the keys based on handle  
>>> value, then key length, then stncmp of the key name.
>>>
>>> This means that essentially we are indexing off of the name of  
>>> the entry rather than a position in the database.
>>>
>>> So how could inserting a new entry between readdir requests cause  
>>> a duplicate?  The old entry that is stored in the pcache should  
>>> still be valid.  If the newly inserted entry comes after it  
>>> (according to the keyval_comare() sort order), then we should see  
>>> it as we continue iterating.  If the new entry comes before it,  
>>> then it should not show up (we don't back up in the directory  
>>> listing).  It doesn't seem like there should be any combination  
>>> that causes it to show up twice.
>>>
>>> Is c_get() not traversing the db in the order defined by the  
>>> keyval_comare() function?
>>>
>>> The only other danger that I see is that if the pcache_lookup()  
>>> fails, the code falls back to stepping linearly through the db to  
>>> the token position which I could imagine might have ordering  
>>> implications. However, I am only talking to the server from a  
>>> single client, so I don't see why it would ever miss the pcache  
>>> lookup.
>>>
>>> I just want to confirm that there is actually an algorithm  
>>> problem here rather than just a bug in the code somewhere.
>> Oh, or is the problem in how the end of the directory is  
>> detected?  Does the client do something like issuing a readdir  
>> until it gets a response with zero entries?  I haven't looked at  
>> how this works yet, but I imagine that could throw a wrench into  
>> things if the directory gets additional entries between when the  
>> server first indicates that it has reached the end and when the  
>> client gives up on asking for more.
>
> I just tried repeating the test a few times, replacing the "ls" in  
> my test script with either "pvfs2-ls" or "pvfs2-ls -al".  I cannot  
> trigger the problem when using pvfs2-ls.
>
> If I switch back to "ls" or "/bin/ls" the problem shows up reliably.
>
> Is there anything fundamentally different between how pvfs2-ls  
> works and how the vfs readdir path works, or is pvfs2-ls somehow  
> getting luckier with the timing?

The kernel module sets the position itself before calling readdir  
each time.  It also tries to update the position if it can't handle  
all 32 entries (out of memory) in the readdir response.  This is why  
we didn't initially think we could use the component name as the  
position.  Murali has looked at making sure the position is getting  
set to the correct value, but maybe there are still some bugs there.   
I'll have to look.

-sam

>
> -Phil
>