Hi,
I'm writing FUSE fs's, and need a method for doing lookups for of dentries and inodes. To start with dentries, a FUSE lookup uses the parent inode ino (an uint64_t) and the name.
Now I've expirmented a lttle creating a key like:
- first 8 bytes used by parent inode ino, left padded with zeros. - rest the name of the entry
like
00000001dexample
which is the directory dexample in directory with ino 1. (to make this work custom locking is required)
It works, but is it a good idea to do? Or are there other methods better?
S.Bon
stefbon@gmail.com wrote:
Hi,
I'm writing FUSE fs's, and need a method for doing lookups for of dentries and inodes. To start with dentries, a FUSE lookup uses the parent inode ino (an uint64_t) and the name.
Now I've expirmented a lttle creating a key like:
- first 8 bytes used by parent inode ino, left padded with zeros.
- rest the name of the entry
like
00000001dexample
which is the directory dexample in directory with ino 1. (to make this work custom locking is required)
What locking is required?
It works, but is it a good idea to do? Or are there other methods better?
Keeping LMDB keysize limits in mind, it will work. But you'd probably do better using LMDB's DUPSORT feature. Use the parent inode as the key, use the name as the value.
Howard Chu wrote:
What locking is required?
locking rw per directory. A directory is the group of dentries with the same parent inode. This is a small subset of the whole list. The whole list is for all the dentries of a FUSE mountpoint.
Keeping LMDB keysize limits in mind, it will work. But you'd probably do better using LMDB's DUPSORT
feature. Use the parent inode as the key, use the name as the value.
Well, what you suggest is that the lookup does not use the name: after a search for the first dentry having the desired parent inode, then step by step to get to the dentry with the right name. This is not what I'm looking for: then I can better use an internal hashtable. I'm hoping I can use lmdb to do a lookup using the parent ino and the name. Is it a bad thing to use the name next to the parent ino as well? You mention the LMDB keysize.
S. Bon
stefbon@gmail.com wrote:
Howard Chu wrote:
What locking is required?
locking rw per directory. A directory is the group of dentries with the same parent inode. This is a small subset of the whole list. The whole list is for all the dentries of a FUSE mountpoint.
Keeping LMDB keysize limits in mind, it will work. But you'd probably do better using LMDB's DUPSORT
feature. Use the parent inode as the key, use the name as the value.
Well, what you suggest is that the lookup does not use the name: after a search for the first dentry having the desired parent inode, then step by step to get to the dentry with the right name. This is not what I'm looking for: then I can better use an internal hashtable.
No, not at all. And that would be stupid indeed. The MDB_GET_BOTH flag means both the key and the value will be looked up. Also, using DUPSORT saves space since the inode will only be stored once instead of repeatedly on every entry.
I'm hoping I can use lmdb to do a lookup using the parent ino and the name. Is it a bad thing to use the name next to the parent ino as well? You mention the LMDB keysize.
It's not a terrible thing, it just wastes space.
S. Bon
Hi S.,
On Mon, 2025-07-28 at 15:10 +0000, stefbon@gmail.com wrote:
Hi,
I'm writing FUSE fs's, and need a method for doing lookups for of dentries and inodes. To start with dentries, a FUSE lookup uses the parent inode ino (an uint64_t) and the name.
Now I've expirmented a lttle creating a key like:
- first 8 bytes used by parent inode ino, left padded with zeros.
- rest the name of the entry
like
00000001dexample
which is the directory dexample in directory with ino 1. (to make this work custom locking is required)
It works, but is it a good idea to do? Or are there other methods better?
S.Bon
It's notable that the LMDB DB key size is limited at compilation time (it can be changed), but the default is well above NAME_MAX+8, so you should be good, for a file name, and even attributes.
Looks like this filesystem is squashfs-like in that it's pre-built and nothing would change afterwards, with potentially (file attributes, file data) as value corresponding to this (parent inode, ..., basename) key?
I had posted here before about LMDB for filesystem indexing, which is rather similar, and got some feedback. For a more dynamic structure, I was not considering putting "dynamic" values in a key.
Best regards,
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512
Jérôme Carretero wrote:
Hi S.,
On Mon, 2025-07-28 at 15:10 +0000, stefbon@gmail.com wrote:
Hi,
I'm writing FUSE fs's, and need a method for doing lookups for of dentries and inodes. To start with dentries, a FUSE lookup uses the parent inode ino (an uint64_t) and the name.
Now I've expirmented a lttle creating a key like:
- first 8 bytes used by parent inode ino, left padded with zeros. - rest the name of the entry
like
00000001dexample
which is the directory dexample in directory with ino 1. (to make this work custom locking is required)
It works, but is it a good idea to do? Or are there other methods better?
That's essentially the scheme that OpenLDAP itself uses in back-hdb and back-mdb. back-hdb's design was presented here https://openldap.org/conf/odd-sfo-2003/proceedings.html
S.Bon
It's notable that the LMDB DB key size is limited at compilation time (it can be changed), but the default is well above NAME_MAX+8, so you should be good, for a file name, and even attributes.
Looks like this filesystem is squashfs-like in that it's pre-built and nothing would change afterwards, with potentially (file attributes, file data) as value corresponding to this (parent inode, ..., basename) key?
I had posted here before about LMDB for filesystem indexing, which is rather similar, and got some feedback. For a more dynamic structure, I was not considering putting "dynamic" values in a key.
Best regards,
- -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/
openldap-technical@openldap.org