A Blog Less Ordinary

The blog of Dave Ingram

Insight: Where am I now, and where next?

So I’ve been in Deep Coding Mode� for quite a while. What have I got to show for it?

Well, the short answer is that Insight is now a functioning file system… for a given definition of “functioning”.

As of this morning:

So far, so good. Now for the limitations:

But I am working on all of these things. At the moment, the main thing is sorting out the internal inode lists. Once those are done, then it should be quite straightforward to do tag assignment/removal and import directly into tags. Plan of action, therefore:

  1. Implement inode insertion/deletion
  2. Implement inode set functions (intersection, union, difference)
  3. Re-implement query tree builder from path. Currently only deals with building a basic conjunctive query tree and assumes that all components are tags. Should:
    • Take a path
    • Canonicalise it
    • Check path components (left-to-right) to ensure tags exist
    • If last part is an incomplete tag, treat appropriately
    • If last part is a complete tag, then fine
    • If last part does not resolve as a tag, then hash it and see if it translates to a known inode
    • If not, or if any tags in path do not exist, then path is invalid
    • If it is a valid inode, then add QUERY_IS_INODE node to tree
    • Otherwise return query tree
  4. Implement query processing:
    • Given input set of inodes, produce an output set at each node of the query tree.
    • In trivial case with top-level IS_ANY node, output set is the set of limbo inodes, with internal negation flag set to false
    • With an IS node, the output set is the recursive union of the inodes belonging to that tag and its subtags, with internal negation flag set to false
    • With an IS_NOSUB node, the output set is the set of inodes belonging tag, with internal negation flag set to false
    • With an IS_INODE node, the output set contains a single element: the inode.
    • With an IS_NOT node with a subquery, the output set is identical to the subquery resultset, with an internal negation flag inverted
    • With an IS_NOT node with a tag, the output set is the same as for an IS node, with an internal negation flag set to true
    • An AND node output depends on the negation flags of its subqueries:
      • Both false: output is the set intersection of its subqueries, with negation flag clear
      • Both true: output is union of subqueries, with negation flag set
      • Otherwise: output is set difference, with the negation-true set removed from the negation-false set, and the negation flag cleared
    • An OR node output depends on the negation flags of its subqueries:
      • Both false: output is union of subquery results, with negation flag clear
      • Both true: output is intersection of subquery results, with negation flag set
      • Otherwise: output is ???
    • Probably very likely to be an error if the negation flag is found to be set at the top level.
    • Also have to think about how to build a tree from a bracketed expression. But later. Much later.
  5. Output of query processing is an inode set.
  6. Maybe low-overhead query processing just to see if an inode would match the query?
  7. Implement open/read/write as pass-through operations on the inode symlink targets.
  8. Implement symlinking directories as creating synonyms.
  9. Add LOTS of checks.
  10. Note: also have to track inode reference count, so that when it gets to zero the inode is added to the limbo list. Once removed from there, it is removed from the filesystem completely.

These should be quite straightforward to do (I hope), especially as I know more or less exactly what I’m doing. Deadlines are closing in, however, and I have a report and presentation and demo to write yet. Hopefully I can get much of this done by Tuesday, then can spend the day doing bits of my report.

I must say that I do love developing this. It’s just so amazing to be developing a file system and see it work!

One Response to Insight: Where am I now, and where next?

Will Jones says: June 9, 2008 at 13:09

I’ve been enjoying your blog over the last few months with regard to Insight Dave – must say I laughed when reading the first point of “What it doesn’t do” 🙂

Best of luck – can’t wait to see the final product 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *

*

*

 

GitHub Google+ Twitter