Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

fuse-devel

 [fuse-devel] Again about inodes and the way to administer them. From: Stef Bon - 2010-05-12 20:29:05 ```Hello, earlier I write about lowlevel fs and relayfs, as an example. What I've said there, that I do not understand the use of a hash table, was true then, but now I do. I still do not see why a hash function is used, but a hash table for inodes and entries is very usefull. When writing a lowlevel fs, you have to find a way your fs will administer (right spelling?) the inodes. The highlevel does that for you, at the lowlevel your fs has to do that. Now, It became clear to me that there are various ways to set up the way inodes stored: one big linked list, or one seperate index, or with the help of a hashtable (and a little bit of linked list). You'll need to have some system here, your fs has to determine the right inode 'record' in memory knowing the inode number. Now, with one linked list : inodea -> inodeb -> inodec ->..... your fs has to walk through all the inode one by one, which is not very efficient. If you have a lot of inodes, well obvious very inefficient.(O(n)) Second an index, like we know from databases. How to maintain it, I do not know, but you'll need to have an array which has the same size as the number of inodes. With a good search function this is of order O(logn). But it's necessary to The third is used in relayfs, which is a combination of a sort of index (a hash table) and a linked list. A hash function is used to create a value like: hashfunction(inode) % tabelsize. (A) This is not an unique operation. The modulo operation is responseable for that. The value tablesize+1 has the same result as 1 (which is 1). Now with relayfs al the inodes with the same result are kept in one linked list. A hashtable (with as parameter the result of A) points to the first record. Maybe this is the record looked for, then ready. If not, this record points to another record with the same value A. And so on. I still do not understand the reason the (complicated) hash function is used, especially, the most important operation is the modulo. This make the whole function not unique. Maybe some of you use another way. Well, maybe some of you know all this. But maybe not. Stef ```
 Re: [fuse-devel] Again about inodes and the way to administer them. From: Stef Bon - 2010-05-13 09:25:30 ```Oh whole rereading my message I've mentioned relayfs while meaning deltafs of course. Sorry for the confusion. Stef Bon ```