Are you actually still talking about a small fixed-sized array here (which
sounds cumbersome) or a linked list (which is slightly more challenging
to binary search efficiently). The problem does immediately suggest a tree
approach though. In fact there might be several places in the VFS where we
build and sort lists (elevator algorithm?) that might be more efficiently
done with trees.
Well it looks like what we're talking about how is adding the capability
to have a new doubly linked list (using linux/list.h) in buffer_head
structures. Since it will be easy to tell whether that buffer is linked
into a inode-specific linked list, it will be very fast to see whether
the buffer is linked in or not.
Something I'm thinking about doing is if the filesystem tries to add a
block to an inode-dirty list, and that block is already on some other
inode's dirty list, then the VFS layer will add that block to a
per-filesystem "shared dirty list", which can get fsync()'ed by the
filesystem if it turns out to be a filesystem (like FFS or FAT) which
regularly shares data blocks or metadata blocks between multiple inodes.
(Yes, I know ext2 has a similar issue with the inode table, but the way
we flush inodes back to disk is handled separately from the data and
indirect blocks.)
- Ted
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/