Invalid node structure under Mac OS X 10.5 Leopard

So my Finder froze up today during a Time Machine backup operation.  After trying several standard tricks to get my Finder back, I finally rebooted.  Upon rebooting, Timebook, my Time Machine drive, wasn't mounting.

Bah!

This wouldn't have made me so nervous, but my iMac had a drive freak out about two months ago, and I had to recover fully from a Time Machine backup.  So there was a better chance than not that both could die on me if I didn't get this fixed soon enough.

Upon running Disk Utility, I received the always hair-raising Invalid Node structure.

From the logs;

Apr  7 10:39:19 magneto Disk Utility[456]: Invalid node structure^[
Apr  7 10:39:19 magneto Disk Utility[456]: Volume check failed.
Apr  7 10:39:19 magneto Disk Utility[456]: Error: Filesystem verify or repair failed.
Apr  7 10:39:19 magneto Disk Utility[456]:
Apr  7 10:39:19 magneto Disk Utility[456]: Disk Utility stopped verifying “Timebook” because the following error was encountered:\n\nFilesystem verify or repair failed.
Apr  7 10:39:19 magneto Disk Utility[456]:
Apr  7 10:39:24 magneto Disk Utility[456]: Verify and Repair volume “Timebook”
Apr  7 10:39:24 magneto Disk Utility[456]: Starting repair tool:
Apr  7 10:39:24 magneto Disk Utility[456]: Checking Journaled HFS Plus volume.
Apr  7 10:39:24 magneto Disk Utility[456]: Checking Extents Overflow file.
Apr  7 10:39:24 magneto Disk Utility[456]: Checking Catalog file.
Apr  7 10:41:02 magneto Disk Utility[456]: Invalid node structure^[
Apr  7 10:41:02 magneto Disk Utility[456]: Volume check failed.
Apr  7 10:41:02 magneto Disk Utility[456]: Error: Filesystem verify or repair failed.
Apr  7 10:41:02 magneto Disk Utility[456]:
Apr  7 10:41:02 magneto Disk Utility[456]: Disk Utility stopped repairing “Timebook” because the following error was encountered:\n\nFilesystem verify or repair failed.

When you do a Google search, some sites suggest using the command line utility fsck_hfs with the -y option (assume Yes to every question.. if you run an fsck on a damaged filesystem you'll usually see why this is a good idea).  That didn't work for me, it would just crap out again the same way Disk Utility had.  What DID work was the following.. (after a sudo su -)

# fsck_hfs -rf /dev/disk1s3

Now, a lot of people suggest Diskwarrior to fix this problem.  I agree this is probably a good idea for Mac disk maintenance tasks.  The problem; Disk Warrior is $99 USD, and I'm cheap.  Hell, the Timebook was on or about $99 USD.  Disk Warrior will have to wait, but I will likely invest in it in the future.

After I ran the fsck command with the -f flag (to force fsck to check `clean' filesystems when preening.. don't ask me how or why this works over a -ry) the drive was mountable from Disk Utility. The first Time Machine run had this error in the console though, but I think it's harmless.

Apr  7 19:13:02 magneto /System/Library/CoreServices/backupd[1000]: Starting standard backup
Apr  7 19:13:03 magneto /System/Library/CoreServices/backupd[1000]: Backing up to: /Volumes/Timebook/Backups.backupdb
Apr  7 19:13:07 magneto /System/Library/CoreServices/backupd[1000]: Event store UUIDs don't match for volume: Macintosh HD
Apr  7 19:13:07 magneto /System/Library/CoreServices/backupd[1000]: Node requires deep traversal:/

Here's the full text of the command output below, for reference;

magneto:~ root# fsck_hfs -rf /dev/disk1s3
** /dev/rdisk1s3
** Checking Journaled HFS Plus volume.
** Checking Extents Overflow file.
** Checking Catalog file.
** Rebuilding Catalog B-tree.
   Invalid node structure
(4, 75586)
** Rechecking volume.
** Checking Journaled HFS Plus volume.
** Checking Extents Overflow file.
** Checking Catalog file.
   Incorrect number of thread records
(4, 32659)
** Checking multi-linked files.
   Incorrect number of file hard links
** Checking Catalog hierarchy.
   Invalid directory item count
   (It should be 1178851 instead of 1178880)
** Checking Extended Attributes file.
   Incorrect number of Extended Attributes
   (It should be 1690486 instead of 1690462)
   Incorrect number of Access Control Lists
   (It should be 1690472 instead of 1690448)
   Invalid leaf record count
   (It should be 3699221 instead of 3699235)
** Checking multi-linked directories.
   Incorrect number of directory hard links
** Checking volume bitmap.
   Volume Bit Map needs minor repair
** Checking volume information.
   Invalid volume free block count
   (It should be 36497060 instead of 29689387)
   Volume Header needs minor repair
(2, 0)
** Repairing volume.
   Orphaned file hard link (id = 8785918)
   Orphaned file hard link (id = 8785919)
   Orphaned file hard link (id = 8785920)
   Orphaned file hard link (id = 8785921)
[[ message repeated etc ...]]
   Orphaned file hard link (id = 11098150)
   Invalid first link in hard link chain (id = 11995430)
   (It should be 12024532 instead of 12023278)
** Rechecking volume.
** Checking Journaled HFS Plus volume.
** Checking Extents Overflow file.
** Checking Catalog file.
** Checking multi-linked files.
** Checking Catalog hierarchy.
** Checking Extended Attributes file.
   Invalid map node
(8, 61440)
** Checking multi-linked directories.
** Checking volume bitmap.
** Checking volume information.
** Repairing volume.
** Rechecking volume.
** Checking Journaled HFS Plus volume.
** Checking Extents Overflow file.
** Checking Catalog file.
** Checking multi-linked files.
** Checking Catalog hierarchy.
** Checking Extended Attributes file.
** Checking multi-linked directories.
** Checking volume bitmap.
** Checking volume information.
** The volume Timebook was repaired successfully.

Update: Jan 4, 2010 - While doing some digging, I found this article at Jthon's Place that describes how to fix a corrupted Time Machine backup.  NICE!