File Management Tool - Part 2

I have worked with my program a bit more and there are some interesting aspects of this kind of backup.

At the end of the backup all duplicate files point to the same inode, so the SHA1 version can be deleted.

eg. 

inode   name
1299    workingdir/folder1/file1.txt
1299    workingdir/folder5/file1.txt
1299    workingdir/folderx/file1_renamed.txt
1299    backupdir/54817fa363dc294bc03e4a70f51f5411f4a0e9a9

All these files now point at the same inode and so the backup directory can be erased and no file has executive control over this inode. All three files would have to be deleted to finally get rid of inode 1299. Generally it seems that programs save files with new inodes (Text Edit ...), so editing any of the versions breaks the links. It seems that UNIXy programs respect the inode better, vim saves with the same inode and so editing any version edits every version.

Removing the "backup" directory also helps Spotlight resolve the names and filetypes. Deleting that folder and running `mdimport ./workingdir` complained mightily but more or less re-indexed the folder. Here is a quick slice of the errors it produced, I'm not going to try to make sense of them, but think they're interesting; maybe Spotlight encounters these kinds of problems always and just keeps silent about them.

$mdimport ./workingdir
...
font `F88' not found in document.
font `F82' not found in document.
font `F88' not found in document.
font `F82' not found in document.
font `F88' not found in document.
font `F82' not found in document.
font `F88' not found in document.
encountered unexpected symbol `c'.
encountered unexpected symbol `c'.
encountered unexpected symbol `c'.
encountered unexpected symbol `c'.
encountered unexpected symbol `c'.
encountered unexpected symbol `c'.
encountered unexpected symbol `c'.
choked on input: `144.255.258'.
choked on input: `630.3.9'.
choked on input: `681.906458.747'.
choked on input: `680.335458.626'.
choked on input: `682.932458.507'.
choked on input: `530.3354382.624'.
font `Fw' not found in document.
font `Fw8' not found in document.
encountered unexpected symbol `w6.8'.
encountered unexpected symbol `w0.5'.
font `Fw8' not found in document.
encountered unexpected symbol `w0.5'.
encountered unexpected symbol `w6.8'.
choked on input: `397.67.'.
choked on input: `370.5g'.
choked on input: `370.5g'.
choked on input: `D42.32 m
314.94 742.32 l
S
306.06 751.2 m
306.06 7...'.
choked on input: `67.l'.
choked on input: `67.l4'
failed to find start of cross-reference table.
missing or invalid cross-reference trailer.

To reiterate, this is a funny trick that my program is doing. It builds a list of SHA1 named files from the source directory and then you just delete the index it just made and you're left with all the duplicates hard linked. I think that's pretty cool.

Metadata

One stated aim of this backup tool was to preserve metadata. So far this tool preserves the time stamps and metadata of whatever file it indexes first and the filename of every file it indexes. I'm not sure how to implement any more than this in a transparent way. As far as I can tell from the documentation, you can't have a single inode with multiple access and modification times. And building an external database of that kind of information would not get used.

File Management Tool

I ended up sketching out the details of how my file managing tool will work, it's kind of like a virtual librarian that removes redundant files without deleting the file hierarchy. My method is a bit of a mashup of how other tools work, so I'll give credit where credit is due.

This is how it works so far:

• All files in a tree have their SHA1 hash-value computed (Git)
• A hard link is created in the backup folder with the SHA1 name (Time Machine) ...
• unless: the file exists already, then it is hard-linked to the existing SHA1 (...)

There is no copying or moving of files, simply linking and unlinking, so 99.9999% of the time is spent computing the hash values of the files. Here's the python version of this:

import os
import hashlib

backupfolder = os.path.abspath('./backup')
srcfolder = os.path.abspath('./working')
srcfile = ''
backupfile = ''

for root, dirs, files in os.walk(srcfolder):
    for name in files:
        if name == '.DS_Store':
            continue
        srcfile = os.path.join(root, name)
        sha1 = hashlib.sha1(open(srcfile, 'r').read()).hexdigest()
        backupfile = os.path.join(backupfolder, sha1)
        if os.path.exists(backupfile):
            os.unlink(srcfile)
            os.link(backupfile, srcfile)
        else:
            os.link(srcfile, backupfile)
        # print backupfile

This folder contains about 5 GB of info and I thought that the SHA1 calculations might take a couple weeks, but as it turns out, it only takes a couple minutes. What you end up with is a backup folder that contains every unique file within this tree named by it's sha1 tag, and the source folder looks exactly as when you started, but every file is a hard link.

So, what are the benefits?

Filenames are not important

Because the SHA1 only calculates the contents of a file, filenames are not important. This is important in two ways, if a file has been renamed in one tree, yet remains physically the same, you only have one copy and the unique names are preserved. And more importantly, if you have two files in separate trees that are named the same, (ie. 'Picture 1.png'), you keep the naming, yet have different files.

If you have some trees of highly redundant data, this is the archive method for you. My test case was a folder of 15 direct copies of backup CD's that I have made over the years and I have saved about 600M across 5GB. And the original file hierarchies look exactly the same as they did before running the backup.

What is wrong with it?

As it stands, it messes with Spotlight and Finder's heads a little bit. Finder isn't computing correct size values for the two folders. du prints the same usage whether I include both folders or one at a time, which is pretty clever: total:5.1GB, working:5.1GB, backup:5.1GB. Finder on the other hand prints Total: 5.1GB, working: 5.1GB, backup: 4.22GB.

Spotlight

Some very wierd stuff happens with Spotlight.

A Spotlight search in the working directory will show mostly files from the backup directory, which isn't convenient. The files in the backup dir have no file extension so they're essentially unopenable by Finder. Here's what i found using the command-line mdfind:

mdfind -onlyin ./working "current"
/Users/.../backup/5f5b587eb07ee61f15ab0a032ca564a17ff461e9
/Users/.../backup/0f3f769000f164b2e30bb7b3f09482e8cc244135
and so on ...

mdfind -onlyin ./backup "current"
nothing found

For some reason, when searching the working directory it finds the information, yet always resolves the name of the file to a directory it's not supposed to be searching. And if you search the backup directory, it doesn't even bother reading the files, because it assumes from the name that they are unreadable by it.

I'm starting to wish that Steve Jobs hadn't caved and given in to the file extension system.

Time Machine

Okay, it's useful but how is it similar to Time Machine? Time Machine creates a full copy of the tree when it first backs up the system. From then on it creates the full hierarchy of directories but all the files that haven't changed are hard links to the original backup. Each unique file is a new inode created in time, whereas in my system each unique file is a new inode created in space. All duplicates in time are flattened by Time Machine and all duplicates in space are flattened by my system.

Note: To copy folders from the command line and preserve as much as possible for metadata use `cp -Rp`.

File Backup And Synchronization

In my previous post I had mentioned that I was looking for a backup/file synchronization tool.

I don't think Git is it and neither is dropbox. Both these are useful in that they are format transparent, which most database software is not. But what they are lacking is a way to deal with a large variety of file and folder hierarchies and seamlessly compress without losing transparency and semantic meaning.

So here is my list of requirements from a backup tool:

1. Preserves any time-stamp information, even conflicting
2. Distributed (decentralized)
3. Minimizes redundant data
4. Preserves hierarchies for semantic meaning
5. Hides hierarchy clutter
6. Preserves every bit of metadata, even if it's not explicit
7. Accessible and platform neutral
8. Makes data integrity paramount

It may seem like I have requirements that conflict with each other, but I will try to explain what I mean. I have loaded four of my backup CD's onto my laptop. I know there are duplicate files and I know there are time-stamps that disagree with one another.

I want to be able to view these files in a number of ways:

• In their original on-disk hierarchy.
• By file type, date, tags or physical description.

And I want to be able to synchronize all or part of these folders between machines, in addition to making zip/tar archive of them to a backup machine.

Any suggestions, or shall I start coding?

Git And The Future Of The Internet.

I've recently taken a detour into philosophizing about where technology is going. What does the future look like and what does it mean for humanity, life and the current business models as we know them?

It all started with a bit of research into Linus Torvalds latest project, Git. I've been thinking about trying some kind of content management system for personal use. I've looked at a lot of personal database type stuff (Bento, FileMaker, MySQL, ...) and they just seem like format specific black holes to drop your content into. I'm still not sure Git is right for what I'm thinking, but I watched Linus' Google tech talk followed by Kevin Kelly's TED talk and had a vision of a web that is so much more than what it is right now.

They're both pretty long, but I've had a bit of time on my hands lately... http://www.youtube.com/watch?v=4XpnKHJAok8 http://www.ted.com/talks/kevin_kelly_on_the_next_5_000_days_of_the_web.html Linus brings up two important points in his talk: one is the notion of working in a "network of trust" and the other is the sacredness of one's own data. Both of these are extremely important and often lacking components in the emerging technologies of our day. The network of trust is the only way to do collaborative work on open source development right now.

I think this is hitting a critical mass and will soon be the only way to do any kind of work. Monolithic organizations cannot keep up with the changing landscape of information growth. Git is a very interesting project because it takes this model and implements it in a very practical way. It employs a lot of very technical algorithms to allow software projects to grow very organically in a social environment. A lot of the metaphors that surround software development are hard, physical metaphors like construction, building and engineering, but the emerging metaphors are about growth, evolution and adaptation to environment. 

The benefits of collaborative networked projects are obvious but the sacredness of one's data is a bit more of a veiled concept. Linus outlines the use of the SHA1 algorithms as a means to ensure that the entire history of a project, or set of data, can be verified to be accurate and traceable throughout it's lifespan. This has obvious benefits when dealing with buggy network connections or failing hard drives, but it's more interesting to me in it's wider application.

Where's My Information?

As a person that has used a computer for a number of years I'm already seeing the breakdown of continuity in my archived information. As data gets moved around, archived to CDROM, uploaded to Google Docs, downloaded to PDF's and transferred to different operating systems, it all ends up in a soup of data without context or history. I have no idea if the timestamps are accurate, or what the context and related content might be. As soon as you add cloud computing to the mix, the problems amplify greatly.

This very blog post is being submitted to the vast expanse of content controlled and managed by the cloud. I have no simple way of traversing the internet and picking up all the odds and ends that I have put there.

This is the real direction of Git I think, and I want to figure out how to use it for more than just source code management because I think it could change the way the internet works. What if this blog was simply a mirror of the "Blog" folder on my hard drive, which was mirrored on every machine I use and was also shareable to other collaborators who mirrored their own unique versions? And what if my photo page on flickr and Facebook were simply mirrors of a folder called "Published Photos" on my hard drive which were mirrors of... and so on.

Vapor Trails

The fundamental problem of cloud computing is the owners right to content and tracking. This is generally possible with today's technology, but never practical. I have 65 documents in Google Docs at the moment and I could download all of them in one go into plain text files, but all the metadata would be garbage, and I couldn't easily merge them with the existing contents of my hard drive. Sure, I could spend a bit of time diff-ing them with my files and organizing them into logical places, but imagine if I was talking about the entire contents of my home directory. du | wc -l command shows 5,627 files in my home directory and I don't even have my music collection on this computer! Yes, the data is basically safe in the cloud, but what if I want to take it with me or move it elsewhere? What if I want to host this blog from my own server, how would I transfer it? The current cloud model only takes uploading and viewing seriously and neglects personal ownership rights. Google docs has special code written for exporting, blogger doesn't, facebook and flickr don't, youtube doesn't.

They are all greedy information gathering tools. They are only concerned with gathering your information and storing it on their sites. There are "sync" tools for most platforms, but their only intent is to gather your content with more ease and transparency.

Git looks promising in that it allows you to publish your information, yet still control the source of it.

Assembly Language For Mac

I'm away from my Linux box and want to do some assembly programming. Mac installs GCC with the developer tools, but there are enough differences that I haven't bothered to work through them until now. Here's a decent tutorial, although it focuses on PPC assembly and I'm using an Intel Mac. The thing that frightened me about the Mac assembler was the default output of gcc -S. There is some strange optimizations and flags in the resulting assembly code. The key, as the tutorial points out, is in the compiler options. Here's what I used on the ubiquitous "Hello World" program:

gcc -S -fno-PIC -O2 -Wall -o hello.s hello.c

And here's the assembly code it spit out:

    .cstring
LC0:
   .ascii "Hello World!%d\12\0"
   .text
   .align 4,0x90

.globl _main
_main:
   pushl   %ebp
   movl    %esp, %ebp
   subl    $24, %esp
   movl    $12, 4(%esp)
   movl    $LC0, (%esp)
   call    _printf
   xorl    %eax, %eax
   leave
   ret
   .subsections_via_symbols

This is more familiar territory, the only differences being the .cstring directive instead of .section .text, the leading underscore on printf, and the .subsections_via_symbols directive. The general naming of sections is outlined on the Mac Assembler Reference, and the .subsections_via_symbols explanation is interesting. I'm already used to using many labels in my code; does this mean that the named sections would be ripped out because they are not "called" by any other code? I tested this out in the previous example, just adding a second call to _printf in a labelled section and the code worked just fine. It seems that labels don't count, they have to be declared sections like .globl, .section or whatever. That seems fair, I haven't yet made a habit of calling sections that are supposed to flow naturally into other sections. Maybe there is some instance where this might be a useful optimization? I will be looking into Position Independent Code(PIC) a bit more, it seems that it's similar in theory to how the latest Linux kernel runs code at randomized memory locations to prevent hardcoded attacks, but I don't know if that's the extent of it.

RPN Calculator - v0.02

My calculator code was quite easily polished up. Here's the revised code which stacks operands properly and supports the main arithmetic operators +,-,*,/. If you flush the stack completely, you get a "nan" warning, which seems reasonable. Here's the code: (gas, x86)

.section .data
expr_length:    .int 128
ADD:            .ascii "+"
SUB:            .ascii "-"
MUL:           .ascii "*"
DIV:            .ascii "/"
null:           .ascii "\0"
disp_float:     .ascii "%f\n\n\0"
.section .bss
    .lcomm expr, 128
.section .text
.globl main

main:
    finit
    1:
    leal    null, %esi          #Clear the expr buffer
    leal    expr, %edi
    movl    expr_length, %ecx
    cld
    lodsb
    rep     stosb
    addl    $4, %esp
    pushl   stdin               # Read an expression
    pushl   $64
    pushl   $expr
    call    fgets
    addl    $12, %esp

    movb    ADD, %ah            # Test For Operators
    movb    expr, %bh
    cmp     %ah, %bh
    je      addFloat
    movb    SUB, %ah
    cmp     %ah, %bh
    je      subFloat
    movb    MUL, %ah
    cmp     %ah, %bh
    je      mulFloat
    movb    DIV, %ah
    cmp     %ah, %bh
    je      divFloat

    pushl   $expr               # Must be a number
    call    atof
    addl    $4, %esp
    jmp 1b

    addFloat:
        faddp
        fstl   (%esp)
        jmp     disp_answer

    subFloat:
        fsubrp
        fstl   (%esp)
        jmp     disp_answer

    mulFloat:
        fmulp
        fstl    (%esp)
        jmp     disp_answer

    divFloat:
        fdivrp
        fstl   (%esp)

    disp_answer:
        pushl   $disp_float
        call    printf
        addl    $8, %esp
        jmp     1b


    notfound:
    movl $1, %eax
    movl $0, %ebx
    int $0x80