zomo technology

Directory sizes and filesystems

Monday, 03. 19. 2012  –  Category: sw

kyero@fs02 ~/log $ du -hs .
1.7M
kyero@fs02 ~/log $ ls | wc -l
24
kyero@fs02 ~/log $ ls -ild .
909313 drwxr-xr-x 2 kyero kyero 1630208 Mar 19 05:25 .

This log directory was allowed to grow indefinitely (ahem) until I trimmed it this morning. Now it is mostly empty (1.7MB), but the directory entry is still huge (at 1.6MB, compared to the default 4kB). I had a vague idea of why this happens but realised I was unclear on the specifics so it was time for The Learning.

On traditional filesystems (here, FFS on FreeBSD and ext2 on GNU/Linux) directories look much like files, just with special content. They have an inode that points to either blocks on disk or to indirection blocks that themselves point to blocks (or to other indirection blocks, up to three levels of indirection). The contents of these directory blocks are reasonably straightforward: they’re a sequence of dirent structures that generally contain a filename and that file’s inode number along with some small housekeeping data.

As a directory fills this sequence of dirents grows to fill all the direct blocks, then starts on the indirect blocks and so on. Each time the sequence crosses a block boundary the directory’s own size, rather than the total of the files it contains, grows by another block. Since filenames have variable length a single block will contain a variable number of dirents.

So far so good. What happens you delete a file from a directory? Other than freeing the actual file’s inode and respective blocks something must happen to its dirent entry in the directory’s data. What doesn’t happen is that the dirent is removed and all the ones after it get bumped towards the front of the list, which would lead to fewer overall directory blocks given enough deletions and ultimately smaller directories.

Why this doesn’t happen partly relates to the guarantees that telldir and friends make to programs with the directory open: a file’s relative position in the sequence of dirent will not change for any process that has the directory open. The deletion process can’t compact the directory itself without breaking that guarantee. Both FFS and ext2 blank out the file’s inode in the dirent record (ext2 with zero, FFS with a special value). Subsequent directory operations will ignore this blanked dirent, and processes which knew its sequence number via telldir will error if they attempt operations on it.

To recover the disk space used by a directory that has ballooned and then contracted its simplest to simply delete it entirely and recreate it. ext2 has an option (-D) in its filesystem check to compact the directory offline.

Interestingly this behaviour isn’t present on all filesystems, particularly those that use indexes instead of special files for directories: for example ZFS and HFS+. They can remove a file’s entry in the directory index yet still keep the remaining files appearing at their same positions by informed updates to the index.

Here is these four filesystem’s compared by

• Creating an empty directory
• Filling it with a million files
• Removing all but one of those files

The comparison shows how on ext2 and FFS the directory itself remains at its peak size after the test files are removed, whereas ZFS and HFS+ contract.

ext2

[build@centos-x86-64-build tmp]$ df -ih .
Filesystem            Inodes   IUsed   IFree IUse% Mounted on
/dev/sdb                1.3M      11    1.3M    1% /mnt/tmp
[build@centos-x86-64-build tmp]$ ls -ild .
2 drwxr-xr-x. 3 build build 4096 Mar 19 08:58 .

[build@centos-x86-64-build tmp]$ seq --format 'f%06g' 0 999999 | xargs touch
[build@centos-x86-64-build tmp]$ df -ih .
Filesystem            Inodes   IUsed   IFree IUse% Mounted on
/dev/sdb                1.3M    977K    304K   77% /mnt/tmp
[build@centos-x86-64-build tmp]$ ls -ild .
2 drwxr-xr-x. 3 build build 23224320 Mar 19 08:59 .

[build@centos-x86-64-build tmp]$ seq --format 'f%06g' 0 999998 | xargs rm
[build@centos-x86-64-build tmp]$ df -ih .
Filesystem            Inodes   IUsed   IFree IUse% Mounted on
/dev/sdb                1.3M      12    1.3M    1% /mnt/tmp
[build@centos-x86-64-build tmp]$ ls -ild .
2 drwxr-xr-x. 3 build build 23224320 Mar 19 09:02 .

FFS

[lemon@zest ~/tmp]$ df -ih .
Filesystem            Size    Used   Avail Capacity iused ifree %iused  Mounted on
/dev/mirror/gm0s1a     19G     10G    7.5G    58%    587k  2.1M   22%   /
[lemon@zest ~/tmp]$ ls -ild .
521826 drwxr-xr-x  2 lemon  lemon  512 Mar 19 14:50 .

[lemon@zest ~/tmp]$ jot -w "f%06d" 1000000 0 | xargs touch
[lemon@zest ~/tmp]$ df -ih .
Filesystem            Size    Used   Avail Capacity iused ifree %iused  Mounted on
/dev/mirror/gm0s1a     19G     10G    7.5G    58%    1.6M  1.1M   60%   /
[lemon@zest ~/tmp]$ ls -ild . 
521826 drwxr-xr-x  2 lemon  lemon  16000512 Mar 20 01:10 .

[lemon@zest ~/tmp]$ jot -w "f%06d" 999999 0 | xargs rm
[lemon@zest ~/tmp]$ df -ih .
Filesystem            Size    Used   Avail Capacity iused ifree %iused  Mounted on
/dev/mirror/gm0s1a     19G     10G    7.5G    58%    587k  2.1M   22%   /
[lemon@zest ~/tmp]$ ls -ild .
521826 drwxr-xr-x  2 lemon  lemon  16000512 Mar 20 01:44 .

ZFS

[lemon@zest /mnt/ark/tmp]$ df -ih .
Filesystem    Size    Used   Avail Capacity iused ifree %iused  Mounted on
ark           207G    686M    206G     0%     58k  432M    0%   /mnt/ark
[lemon@zest /mnt/ark/tmp]$ ls -ild
5 drwxrwsr-x  2 root  wheel  2 Mar 20 06:18 .

[lemon@zest /mnt/ark/tmp]$ jot -w "f%06d" 1000000 0 | xargs touch
[lemon@zest /mnt/ark/tmp]$ df -ih .
Filesystem    Size    Used   Avail Capacity iused ifree %iused  Mounted on
ark           207G    859M    206G     0%    1.1M  432M    0%   /mnt/ark
[lemon@zest /mnt/ark/tmp]$ ls -ild .
5 drwxrwsr-x  2 root  wheel  1000002 Mar 20 07:53 .

[lemon@zest /mnt/ark/tmp]$ jot -w "f%06d" 999999 0 | xargs rm
[lemon@zest /mnt/ark/tmp]$ df -ih .
Filesystem    Size    Used   Avail Capacity iused ifree %iused  Mounted on
ark           207G    727M    206G     0%     58k  432M    0%   /mnt/ark
[lemon@zest /mnt/ark/tmp]$ ls -ild
5 drwxrwsr-x  2 root  wheel  3 Mar 20 09:27 .

HFS+

[lemon@further tmp] 0 $ df -ih .
Filesystem   Size   Used  Avail Capacity  iused    ifree %iused  Mounted on
/dev/disk1  233Gi  185Gi   48Gi    80% 48506927 12484688   80%   /
[lemon@further tmp] 0 $ ls -ild .
12149971 drwxr-xr-x  2 lemon  staff  68 19 Mar 16:06 .

[lemon@further tmp] 0 $ jot -w "f%06d" 1000000 0 | xargs touch
[lemon@further tmp] 0 $ df -ih .
Filesystem   Size   Used  Avail Capacity  iused    ifree %iused  Mounted on
/dev/disk1  233Gi  185Gi   48Gi    80% 48492686 12498929   80%   /
[lemon@further tmp] 0 $ ls -ild .
12149971 drwxr-xr-x  2 lemon  staff  34000068 19 Mar 17:32 .

[lemon@further tmp] 0 $ jot -w "f%06d" 999999 0 | xargs rm
[lemon@further tmp] 0 $ df -ih .
Filesystem   Size   Used  Avail Capacity  iused    ifree %iused  Mounted on
/dev/disk1  233Gi  185Gi   48Gi    80% 48524492 12467123   80%   /
[lemon@further tmp] 0 $ ls -ild .
12149971 drwxr-xr-x  2 lemon  staff  102 19 Mar 19:08 .

pf on OS X 10.7

Wednesday, 09. 14. 2011  –  Category: sw

Today’s the first day that my new laptop, which runs OS X 10.7 (Lion), will sit on an untrusted network so I figured it was time to port my firewall rules across from the old one, that ran OS X 10.6 (Snow Leopard).

I cut my UNIX teeth at a cryptoanarchist shop whose culture of paranoia makes me wary of Apple’s own firewall with its emphasis on letting all the hot shinyness Just Work rather than being overly fussy about inbound connections. Furthermore, with IPv6 tunnels like aiccu, you aren’t behind the warm fuzzy comfort of NAT, you’re just there on the net with all the fun that entails. So, worth having some extra protection I reckon.

10.6 (and earlier) came with ipfw, a packet filter that’s knocked around the BSD world for some time. It works but isn’t overly featuresome (for example, it doesn’t support NAT in-kernel, so you monkey about passing packets to an external daemon). But it was Good Enough for an end system so I supplemented the system’s “Application Firewall” with an additional ipfw ruleset to give an approximation of safety when out and about, and way more permissive when on networks I trust.

On 10.6 I used WaterRoof to sort-of manage the ipfw rules: in that I only really used its launchd loader and would hack on the rules by hand. In the spirit of decrufting I figured I’d sort that myself and went to remind myself how to load ipfw rules enmasse. I noticed at the top of man page:

NAME
     ipfw -- IP firewall and traffic shaper control program (DEPRECATED)
...
DESCRIPTION
     Note that use of this utility is DEPRECATED. Please use pfctl(8) instead

Deprecated? Use pfctl instead? Good news everyone – OS X 10.7 now comes with pf, another BSD packet filter that I’ve chosen of ipfw on BSD hosts for years off the back of its featureset (native NAT, state syncing between failover firewall pairs, traffic queing…).

Anyway, the point of this post is to point out a few things I noticed which are intriguing. Firstly, pf is not enabled by default. Further, Apple have added some moving parts around how it is enabled. From /etc/pf.conf:

# This file contains the main ruleset, which gets automatically loaded
# at startup.  PF will not be automatically enabled, however.  Instead,
# each component which utilizes PF is responsible for enabling and disabling
# PF via -E and -X as documented in pfctl(8).  That will ensure that PF
# is disabled only when the last enable reference is released.

These two flags, -E and -X, are absent from pf on BSD. Here’s how they’re documented on OS X:

     -E      Enable the packet filter and increment the pf enable reference count.
     -X token
             Release the pf enable reference represented by the token passed.

This suggests that different system components might choose to enable and disable pf, and this is the mechanism to coordinate that. There’s a clue about which components in /etc/pf.anchors/com.apple, which is loaded by the main /etc/pf.conf. It defines additional rule anchors:

anchor "100.InternetSharing/*"
anchor "200.AirDrop/*"
anchor "250.ApplicationFirewall/*"

Interestingly, this host’s ApplicationFirewall has a bunch of entries in when viewed in the Preferences GUI, yet the pf anchor of the same name is empty (and pf was disabled when I started out):

$ sudo pfctl -a com.apple/250.ApplicationFirewall -s rules
Password:
No ALTQ support in kernel
ALTQ related functions disabled

so I’m unsure what the status of this mechanism is. I’ve not had occasion to use AirDrop or connection sharing, but would be curious to see if either use these anchors and enable pf temporarily.

Finally, what’s the token that’s passed to -X? You can ask pfctl for the current tokens:

$ sudo pfctl -s References
No ALTQ support in kernel
ALTQ related functions disabled
TOKENS:
PID      Process Name                 TOKEN                    TIMESTAMP
17013    pfctl                        18446743524308110600     0 days 01:05:50

I enabled pf with pfctl, so that makes sense. When I did so it didn’t inform me of the token, but I suppose an enabling process would spelunk the token shortly after enabling pf by merit of its name and PID and pass it back when it’s finished with pf.

Now, on with the actual job of ruleset writing and puzzling out the launchd voodoo required to enable it at boot.

Minor whinge: Apple could do with updating /etc/protocols:

# $FreeBSD: src/etc/protocols,v 1.14 2000/09/24 11:20:27 asmodai Exp $

Why whinge? It doesn’t know icmp6 is a valid alias for ipv6-icmp. Yep, minor.

Cyrus saslauthd and passwords containing quote marks

Saturday, 06. 11. 2011  –  Category: sw

n the back of reading how affordable and powerful GPUs make for insanely fast brute-force software (eg: whitepixel2) I recently did a round of password strengthening, even for accounts that aren’t immediately vulnerable to 30 billion MD5s a second (yes!) attacks.

I then found then whenever I sent mail using authenticated SMTP my mail server would lock up with saslauthd chewing the CPU. This authentication daemon is the glue between the MTA (Exim) and the IMAP server (Courier) – it logs into the IMAP service to test the SMTP user’s credentials. This little kink of indirection comes about because the IMAP daemon is downstream from the Exim host, in a BSD jail host, so its own authentication mechanisms aren’t visible to the MTA.

My new mail password contained a double-quote mark, which made me wonder if the password wasn’t being quoted properly. Testing a bit with openssl:

$ openssl s_client -starttls smtp -connect localhost:25
CONNECTED(00000003)
---
250 HELP
EHLO localhost
250-svc9.zomo.co.uk Hello localhost [127.0.0.1]
250-SIZE 52428800
250-PIPELINING
250-AUTH PLAIN LOGIN
250 HELP
AUTH PLAIN AGZvbwAi < -- this is Base64 for username foo, password "

[ hang ]

Compiling a -g debug variant of the daemon and aiming gdb at it:

$ sudo gdb /usr/local/sbin/saslauthd-debug 97103
GNU gdb 6.1.1 [FreeBSD]
Copyright 2004 Free Software Foundation, Inc.
...
(gdb) bt
#0  0x284250d1 in strchr () from /lib/libc.so.7
#1  0x0804a823 in qstring ()
#2  0x0804ac45 in auth_rimap ()
#3  0x0804f8e3 in do_auth ()
#4  0x0804e1f4 in do_request ()
#5  0x0804e53b in ipc_loop ()
#6  0x0805018d in main ()

What’s qstring()? It’s a function for escaping the quote marks in strings passed to the IMAP daemon. Turns out count-the-quotemark logic wasn’t properly advancing along the string, so it would sit there spinning forever.

Trivial patch ((Gist if it’s not inlined above)) fixes:

$ openssl s_client -starttls smtp -connect localhost:25
CONNECTED(00000003)
---
250 HELP
EHLO localhost
250-svc9.zomo.co.uk Hello localhost [127.0.0.1]
250-SIZE 52428800
250-PIPELINING
250-AUTH PLAIN LOGIN
250 HELP
AUTH PLAIN AGZvbwAi
535 Incorrect authentication data

Better :)