Deleting files doesn't free disk space

During work to improve BleachBit's method of wiping free disk space, I noticed a way in which deleted files do not fully free the disk space they occupied.

Process

The process is basically to create an empty partition, fill it with 2000 files each 4096 bytes, and then delete the files. If the files are in the root of the partition, then the file system keeps 45 more blocks allocated. If the 2000 files are created in a subdirectory that is deleted after the 2000 files are deleted, then all the used blocks are freed.

The following code demonstrates the issue.

#!/bin/bash
#uncomment ONE of the TWO following lines
#SUB=
SUB=sub/
echo "********* initializing"
rm /tmp/fs.ext3
mkdir /tmp/mountpoint
dd if=/dev/zero of=/tmp/fs.ext3 bs=1M count=10
mkfs.ext3 -F /tmp/fs.ext3
sudo mount -o loop /tmp/fs.ext3 /tmp/mountpoint
df /tmp/mountpoint
df -i /tmp/mountpoint
du /tmp/mountpoint
echo "********* creating many small files"
mkdir /tmp/mountpoint/${SUB}
for i in {1..2000}; do dd if=/dev/zero of=/tmp/mountpoint/${SUB}file$i bs=1K count=4 &>/dev/null; done
df /tmp/mountpoint
df -i /tmp/mountpoint
du /tmp/mountpoint
echo "******** cleaning"
for i in {1..2000}; do rm /tmp/mountpoint/${SUB}file$i ; done
rmdir /tmp/mountpoint/sub
df /tmp/mountpoint
df -i /tmp/mountpoint
du /tmp/mountpoint
echo "******** unmount"
sudo umount /tmp/mountpoint
dumpe2fs /tmp/fs.ext3

Observations

In both cases, the file system starts with 1121 used blocks. In both cases, creating the files results in the use of 9166–9167 blocks. After deleting the files from the root folder, the file system uses 1116 blocks, while after deleting the files from the subdirectory, the file system uses 1121 blocks.

Unmounting and remounting the file system (simulating a reboot) does not affect the used blocks.

This was tested with Ubuntu 13.04, Linux 3.8, and ext3.

Explanation

The Core Issue: Directories are "Append-Only" Files

In Linux, a directory is essentially a special type of file. Instead of containing user data, it contains a list of dentries (directory entries), which map filenames to inode numbers.

Growth: When adding 2000 files to a directory, the filesystem must allocate blocks to that "directory file" to store the names and inode pointers.

The "No-Shrink" Policy: For performance reasons, ext3 (and ext4) does not automatically shrink a directory file when deleting files from it. It simply marks those dentry slots as "unused" so they can be recycled if you create new files in that same directory later.

When the subdirectory is deleted, the directory file is removed entirely, and all its blocks are freed.

Fixing bloat

Run e2fsck -f /dev/sdXn to defragment the directory entries and free the unused blocks.

Another reason

By the way, another reason deleting a file may not free its space is if an active process has it open: use the lsof program to find the process or simply reboot. Of course, you should also check the trash can or run BleachBit to clean the trash and other disk space hogs.