2009-12-06

fsdb_ufs - The UFS File System Debugger

Previously, I mentioned that I had run across fsdb and planned to spend some time playing around with it. I had some time last week, so here's a few simple notes on it.

There are 2 automagic variables in fsdb: ";" and ".". ";" represents the current i-node, and "." is the current location on disk. Between the two of them, you can do things like "go to i-node X and read the first 16 bytes." Then, since "." has been updated, you can readily read the next 16 bytes from the file, and so on until you hit the end of the file or disk.

All commands (except "shell escape") must begin with an i-node specification. ":" is the current i-node, but you can specify another i-node with "#:inode". The third part of the command tells fsdb how to update the value of ":". "inode mode" updates the value to the given inode, as long as it's already allocated. "dir mode" updates : to the given directory entry, ordered by inode (this is not the same order as the directory listing is in). This makes it much easier to modify directory entries than trying to fill over the correct bytes in the directory.

"?" is the "formatted output" command. It is similar in feel to gdb's "print" command, but there are file-system specific formats, such as "inode" and "dir." ("/" is unformatted output).

Some examples:

/dev/lofi/1 > 2:inode?ino
i#: 2              md: d---rwxr-xr-x  uid: 29b7          gid: 12c     
ln: 6              bs: 2              sz : c_flags : 0           200                 

db#0: 170          
        accessed: Mon Nov 30 16:31:46 2009
        modified: Mon Nov 30 16:26:25 2009
        created : Mon Nov 30 16:26:25 2009

inode 2 is special in UFS; it is always the root of the filesystem (inode 3 seems to always be lost+found, as well). The output format looks curiously like the output from stat, except that it doesn't actually stat() the file.

/dev/lofi/1 > 2:
/dev/lofi/1 > :ls -l
/:
i#: 2           ./
i#: 2           ../
i#: 4           bin/
i#: d           etc/
i#: 3           lost+found/
i#: 5           sbin/

:ls is a shorthand for listing the current directory or inode. There is also :cd which is easier than listing the current directory, finding the entry you want, and then updating the value of : to it.

Note that all the inodes are in hex. There is a :base command to change both the input and output bases (:base=0xa is decimal; :base=0x8 is octal, etc).

Updating a directory entry is done with N:dir=M. This sets directory slot N (starting from 0) to inode M. For example:

/dev/lofi/1 > :cd bin
/dev/lofi/1 > :ls -l
/bin:
i#: 4           ./
i#: 2           ../
i#: 9           alink?
i#: a           blink?
i#: b           clink@
i#: 6           cp*
i#: 8           ls*
i#: 7           mv*
/dev/lofi/1 > 6:dir:nm,10/c
   58454:       b   l   i   n   k   \0  \0  \0  \0  \0  \0  \?  \?  \?  \0  \?
/dev/lofi/1 > 6:dir=0x09
i#: 9           blink
/dev/lofi/1 > :ls -l
/bin:
i#: 4           ./
i#: 2           ../
i#: 9           alink?
i#: 9           blink?
i#: b           clink@
i#: 6           cp*
i#: 8           ls*
i#: 7           mv*

So, what have we done here? Since blink and alink now share the same inode number, they are hard links of the same symlink. Running 9:inode?ino reveals that fsdb updated the link count for the inode automatically, so we don't have to worry about file system corruption if we unlink one of these later.

N:dir:nm,10/c outputs the first 16 characters of the name of directory slot N (directory slot N's name to ". plus 0x10", unformatted output, characters). The man page seems to point to outputting the name of a file being possible by N:dir:nm,*/c, but that reads to the end of the block, not to the first terminating null.

Renaming a file is done by writing to the "nm" value. This won't allocate any extra space for the filename, so the filename is truncated if it is longer than the already allocated space. Here is the hard way to re-name those nasty files named "\008\008\008\008...".

/dev/lofi/1 > :ls -l
/bin:
i#: 4           ./
i#: 2           ../
i#: 9           alink?
i#: 9           blink?
i#: b           clink@
i#: 6           cp*
i#: 8           ls*
i#: 7           mv*
/dev/lofi/1 > 7:dir:nm,10/c
   58464:       c   l   i   n   k   \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0
/dev/lofi/1 > 7:dir:nm="dlink"
i#: b           dlink
/dev/lofi/1 > :ls -l
/bin:
i#: 4           ./
i#: 2           ../
i#: 9           alink?
i#: 9           blink?
i#: 6           cp*
i#: b           dlink@
i#: 8           ls*
i#: 7           mv*

Now you can impress all your sysadmin friends by creating hard links and renaming files.

But what about something you can't do with normal shell tools?

/dev/lofi/1 > :cd
/dev/lofi/1 > :cd etc
/dev/lofi/1 > :ls -l
/etc:
i#: d           ./
i#: 2           ../
i#: e           etc@
/dev/lofi/1 > 2:dir:nm,10/c
  178c20:       e   t   c   \0  t   \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0
/dev/lofi/1 > 2:dir=0xd
i#: d           etc
/dev/lofi/1 > :ls -l
/etc:
i#: d           ./
i#: 2           ../
i#: d           etc/

Exit fsdb and remount the file system to see changes (yes, this is required; I suspected caching, but this occurs even with files that haven't been looked at yet).

$ ls -lain etc
total 6
        13 drwxr-xr-x   2 10679    300          512 Nov 30 16:26 .
         2 drwxr-xr-x   6 10679    300          512 Nov 30 16:26 ..
        13 drwxr-xr-x   2 10679    300          512 Nov 30 16:26 etc

And there you have it, a hard-linked directory. ln has been lying to you this entire time.

:wq

2009-12-03

GraphViz for Fun and Profit

A long time ago, in a data center far, far away, we had a NIS server. It was a good little NIS server. It knew of usernames, and passwords, and automounter maps, and netgroups. Ah, the joys of NIS netgroups. There is one basic form of netgroup that we used:

([computer],[user],-)

Specifies a computer, user, or computer/user combination ("-" indicates "any user"). In addition, netgroups can contain other netgroups, so you get a nice graph of which netgroups are part of other netgroups.

Along with this wonderful little NIS server, there was an old Python script which would run through and generate a set of webpages to graphically display netgroup relations. If netgroup A contains netgroups B and C, and C contains D, we could check the generated graph to see:

    A
   / \
  B   C
      |
      D

Fast forward a decade or so to an insanely large NIS tree, with netgroups for things we've long since thrown away (e.g. line-printer-access). When we upgraded from NIS to LDAP as the backend directory service, we kept the netgroups around, though. Still in their NIS format. Of course, our wonderful little Python app broke because of the transition to LDAP, but nobody wanted to admit to knowing enough Python to fix it.

So in working on the replacement for our Python app, I got to learn a whole new set of tools. Graphviz is a suite of tools for displaying graphs and trees. A friend of mine showed me his Perl program to generate "dot" diagrams for Tic-tac-toe (turns out the only winning move really is not to play), and I realized that just redoing the generator in ruby or Perl would be much easier than trying to tackle Python's LDAP bindings (not to mention debugging Python).

The "dot" language spec, while exhaustive, isn't very helpful for learning the language. The User Manual, though slightly dated, serves as a much gentler introduction. The syntax allows for a lot of room for error, once you get the basics down: semi-colons are (nearly) optional; whitespace isn't counted for or against you; and nodes that aren't pre-declared are created without complaint.

The most basic directed graph is something like:

digraph G {
    foo -> bar;
    bar -> blort;
    foo -> quux;
}

Generating that from a list of netgroups in ruby is also quite simple:

puts "digraph G {"

netgroups.each do |netgroup|
    netgroup.children.each do |child|
        puts "\"#{netgroup.name}\" -> \"#{child.name}\";"
    end
end

puts "}"

Which can then be used to generate a nice image by:

./generator.rb | dot -Tpng -o image.png

This is exactly what we used to have (except in dia) for our Python/NIS version, except that that had a page for the subgraph at every node. So, clicking on C (using dot-generated HTML image maps) should pop up a page with:

    C
    |
    D

The original script had all the busy work to figure out which nodes to include on subgraphs done in native Python, and tons of generated dia files that got passed on to generate the images and image maps. Graphviz, however, includes "gvpr," an awk-like tool for graphs written in "dot."

BEGIN{} and END{} blocks function exactly the same as in awk.
BEG_G{} and END_G{} blocks are called at the beginning and end of each graph to be processed.
N{} blocks are called for each node, and
E{} blocks are called for each edge.

Just like awk, there is an optional test parameter (inside [], not //) to specify which "things" to operate on. For example:

N [ color == "blue" ] { color = "red" }
E [ color == "red" ] { color = "blue" }

turns all the blue nodes red and all the red edges blue. There is a whole API built in to work with graphs, nodes, and edges within gvpr, which includes a rich set of tools for "subgraphs."

Say we want to generate a graph from a couple nodes in the original graph we were given (known as "root" in gvpr).

graph_t g = subg( root, "SubGraph" ); /* create a new subgraph */
subnode( g, node( root, "C" ) );  /* add node "C" to the subgraph */
subnode( g, node( root, "D" ) );  /* add node "D" to the subgraph */

Now, this is just the nodes. To copy the edges, we could loop through all the edges from "C" (there are for and while in gvpr), or, we can "induce" the edge relations:

induce( g );

Which the man page states "extends g to its node-induced subgraph extension in its root graph." Roughly translated to English, this means "draw all the edges as they are in the original graph."

Add in some writeG() calls to output to files, and several Python files are now around 15 lines of gvpr, 40 lines of ruby, and a shell script to fire it all off.

:wq