Skip to contentSkip to conversation

Starting a grad project that may change kernel VFS. Early research

DISCUSSION Jeff Shanab 4 participants 4 messages Aug 24, 2009 – Aug 25, 2009

lore
Share & tools
lore
#0 lore raw

Title: "Pay it forward patch set"
Goal: Desire to change the dentry and inode functionality so commands like du -s appear to have greatly improved performance.
How: TBD? 2 phase ubdate walking up the tree to root.

Prior to actually starting my Grad Project in Computer science, I am
taking 1 semester to do research for it at the recommendation of my advisory. I need to of course make sure it doesn't already exist. It may be that all the changes end up in a file system and the kernel will be left alone, just one of the things I want help determining.

1) First question, where to put this functionality?
I originally thought to put my functionality in the VFS so that all
mounted file systems could share it, but after reading fs.h, and inode.c, it looks like the VFS is purely an abstract interface and functionality at that level may not be wanted? Also I guess certain file systems may not have needed on disk structures to save the info (ie VFAT,NFS, etc)

2) Second Question. The two part idea.
I was thinking that a good way to handle this is that it starts with
a file change in a directory. The directory entry contains a sum already for itself and all the subdirs and an adjustment is made immediately to that, it should be in the cache. Then we queue up the change to be sent to the parent(s?). These queued up events should be a low priority at a more human time like 1 second. If a large number of changes come to a directory, multiple adjustments hit the queue with the same (directory name, inode #?) and early ones are thrown out. So levels above would see at most a 1 per second low priority update.

So when you issue a 'du -sh' or use anything that uses stat like
filelight, it can get the size of all the subdirs without actually recursing through them, they have been built up over time.

I have a second set of changes I am considering and I think would
fit more completely in a file system, but I bring them up here in case it influences the above.
title: "User Metadata" aka "pet peeve reduction"
I would like to maintain a few classifications of metadata, most
optional and configurable.

1) OriginalFileName: Default on. The original filename is hung
onto. A warning is issued if it is attempted to be saved again in same directory. This is primarily for all those darn auto generated youtube and pdf filenames.

2) UserClasification: User Optional: User defined classifications
can be applied. Most examples I can think of can be usually handled by directories, or file types, but users are surprising. Maybe clasifications like personnel, buisness, job, school, can span directory structures.

3) KeyWords: Auto Gen or user defined: Allow google type searches
of files. Obviously faster to keep in a central location, we leave that up to the application. we need it attached to file so an index can be rebuilt or it moves with the file.

4) Description: User Optional: A user friendly Description can be
applied to any file. File Managers in a GUI can display original filename and this Description on mouse hoover.

5) Extension Specific Metadata: Configurable. An index page into
metadata specific to a file type. For example, security video may be broken into many segments and may have motion events and alarms and analytic information. A index to the frame containing this for the file type may be useful.

Hopefully the cost of these would be relatively small, and most users would only chose a few of them per file, so not all in use for every file, but all available.

Sorry for the length of this. If you have read this far, thankyou!

#1 lore raw
Quoted 11 lines · Jeff Shanab

Title: "Pay it forward patch set"
Goal: Desire to change the dentry and inode functionality so commands like du -s appear to have greatly improved performance.
How: TBD? 2 phase ubdate walking up the tree to root.

  Prior to actually starting my Grad Project in Computer science, I am taking 1 semester to do research for it at the recommendation of my advisory.  I need to of course make sure it doesn't already exist.  It may be that all the changes end up in a file system and the kernel will be left alone, just one of the things I want help determining.

Quoted 7 lines

1) First question, where to put this functionality?
   I originally thought to put my functionality in the VFS so that all mounted file systems could share it, but after reading fs.h, and inode.c, it looks like the VFS is purely an abstract interface and functionality at that level may not be wanted? Also I guess certain file systems may not have needed on disk structures to save the info (ie VFAT,NFS, etc)

VFS has a lot of generic functionality that filesystems can opt into - but see below about your specific proposals...

Quoted 10 lines

2) Second Question. The two part idea.
   I was thinking that a good way to handle this is that it starts with a file change in a directory. The directory entry contains a sum already for itself and all the subdirs and an adjustment is made immediately to that, it should be in the cache. Then we queue up the change to be sent to the parent(s?). These queued up events should be a low priority at a more human time like 1 second. If a large number of changes come to a directory, multiple adjustments hit the queue with the same (directory name, inode #?) and early ones are thrown out. So levels above would see at most a 1 per second low priority update.

As I understand it, you want to tag each directory with the total size of its contents. There are a few problems with this:
1) A metadata change is required for a filesystem to use this. It would be prohibitively expensive to cache all directories in memory to remember their sizes, and we can't just traverse a directory and all of its contents to find its disk space usage just because someone touched it. So the size has to be remembered on disk.
2) Hard links break this scheme rather badly. Consider if /foo/x is hardlinked to /bar/x. Then something modifies /bar/x. The kernel cannot find all other hardlinks to /bar/x, so /foo's disk usage estimate is not updated. Moreover /'s disk space usage would have twice the actual size used by /{foo,bar}/x.

You can't just call it a rough estimate to get around 2), as the error can build up without bounds, until you have directories apparently taking 10x the size of your actual hard disk. That said, for filesystems without hardlinks this is doable, but most Linux filesystems support hardlinks. Heck, even NTFS supports hardlinks. So it's unlikely to be useful in Linux...

Quoted 6 lines

   I have a second set of changes I am considering and I think would fit more completely in a file system, but I bring them up here in case it influences the above.
title: "User Metadata" aka "pet peeve reduction"
   I would like to maintain a few classifications of metadata, most optional and configurable.

[snip details]

This is already supported through user xattrs. It just needs more application support (good luck getting flash to use them for temp files though ;)

#2 lore raw
In reply to Jeff Shanab
Quoted 9 lines · Jeff Shanab

I was thinking that a good way to handle this is that it starts with
a file change in a directory. The directory entry contains a sum already for itself and all the subdirs and an adjustment is made immediately to that, it should be in the cache. Then we queue up the change to be sent to the parent(s?). These queued up events should be a low priority at a more human time like 1 second. If a large number of changes come to a directory, multiple adjustments hit the queue with the same (directory name, inode #?) and early ones are thrown out. So levels above would see at most a 1 per second low priority update.

Is this something that you want to be stored in the file system, or just cached in memory? If it is going to be stored on disk, which seems to be implied by your description, and it is only going to be updated once a second, what happens if there is a system crash? Over time, the values will go out of date. Fsck could fix this, sure, but that means you have to do the equivant of running "du -s" on the root directory of the filesystem after an unclean shutdown.

You could write the size changes in a journal, but that blows up the size of information that would need to be stored in a journal. It also slows down the very common operaton of writing to a file, all for the sake of speeding up the relatively uncommon "du -s" operation. It's not at all clear it's worthwhile tradeoff.

In addition, how will you handle hard links? An inode can have multiple hard links in different directories, and there is no way to find all of the directories which might contain a hard link to a particular inode, short of doing a brute force search. Hence if you have a file living in src/linux/v2.6.29/README, and it is a hard link to ~/hacker/linux/README, and a program appends data to the file ~/hacker/linux/README, this would also change the result of running du -s src/linux/v2.6.29; however, there's no way for your extension to know that.

Quoted 3 lines

title: "User Metadata" aka "pet peeve reduction"
I would like to maintain a few classifications of metadata, most
optional and configurable.

Most Linux filesystems already have extended attributes that can be used to store your proposed metadata. Changing user application programs to store the keywords, etc., is an exercise in application-level programming; the kernel-side support is already there.

- Ted

#3 lore raw
In reply to Jeff Shanab
Quoted 12 lines

2) Second Question. The two part idea.
I was thinking that a good way to handle this is that it starts with
a file change in a directory. The directory entry contains a sum already for itself and all the subdirs and an adjustment is made immediately to that, it should be in the cache. Then we queue up the change to be sent to the parent(s?). These queued up events should be a low priority at a more human time like 1 second. If a large number of changes come to a directory, multiple adjustments hit the queue with the same (directory name, inode #?) and early ones are thrown out. So levels above would see at most a 1 per second low priority update.

Quoted 3 lines

So when you issue a 'du -sh' or use anything that uses stat like
filelight, it can get the size of all the subdirs without actually recursing through them, they have been built up over time.

I'd suggest you look at jack's recursive mtime idea, and then implement your features on top of that, in userland.

Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html