EXT2 - What's up with unlink()?
Posted: Tue Apr 22, 2025 8:33 am
I normally wouldn't ask a question about this sort of thing here but I'm at my wits end and I need a guru somewhere to make it make sense.
I'm in the middle of redoing my EXT2 driver and everything is going great. I've got the CRU in CRUD done. Now, I have come across EXT2's unlink. This, is not super hard but there is one little snag that I am catching.
What does one do when you remove the directory entry? Old me solved this by just absorbing the directory entry into the preceeding one (If possible) and increasing its size. Job done.
Except, say that if you run a C program like this:
Where there's an EXT2 partition mounted on /mnt. You'll add a tonne of directory entries to /mnt/tmp/big. The driver will allocate blocks for it so all these new directory entries can be accomodated. Then they're all removed. Under my system, this would entail not actually freeing up any blocks and just getting rid of the dentries, leaving a waste of blocks on /mnt/tmp/big! Basically, leaving 2 dentries (For . and ..) to occupy all those blocks allocated for the directories that just got removed.
This obviously would not do! So I went to check what OpenBSD (My beloved) does. Here is a relevant comment (And function decl if someone wishes to check me):
The same thing I did... Ok, what about Linux?
This is just odd. Everyone seems to do it the naïve way? Maybe the filesystem gets cleaned up by some or other function? To test this, I mounted an EXT2 partition on a disk image using losetup and mount and ran my above C code. Leaving me with the following directory in /tmp/mnt/big:
What gives? No one seems to actually clean the directory out. The directory is 30x bigger than it needs to be. I even ran fsck.ext2fs and that did nothing. Granted, the problem does seem difficult to solve but someone out there must have solved it. Right?
No matter how much search-engine-ing I did, I could not find a single mention of this issue. So, what's the deal? Does every developer just reckon that directories won't get filled enough for it to matter. Is there some secret tool that deals with this that I don't know about? What do you folks do in your OSes?
Any help will be greatly appreciated because I really don't get what's going on here.
I'm in the middle of redoing my EXT2 driver and everything is going great. I've got the CRU in CRUD done. Now, I have come across EXT2's unlink. This, is not super hard but there is one little snag that I am catching.
What does one do when you remove the directory entry? Old me solved this by just absorbing the directory entry into the preceeding one (If possible) and increasing its size. Job done.
Except, say that if you run a C program like this:
Code: Select all
#include <stdio.h>
#include <sys/stat.h>
#include <unistd.h>
int main() {
char buf[1000] = {0};
for (int i = 0; i < 5000; i++) {
sprintf(buf, "/mnt/tmp/big/dir%04d", i);
mkdir(buf, 0666);
}
for (int i = 0; i < 5000; i++) {
sprintf(buf, "/mnt/tmp/big/dir%04d", i);
rmdir(buf);
}
return 0;
}
This obviously would not do! So I went to check what OpenBSD (My beloved) does. Here is a relevant comment (And function decl if someone wishes to check me):
Code: Select all
/*
* Remove a directory entry after a call to namei, using
* the parameters which it left in nameidata. The entry
* dp->i_offset contains the offset into the directory of the
* entry to be eliminated. The dp->i_count field contains the
* size of the previous record in the directory. If this
* is 0, the first entry is being deleted, so we need only
* zero the inode number to mark the entry as free. If the
* entry is not the first in the directory, we must reclaim
* the space of the now empty record by adding the record size
* to the size of the previous entry.
*/
int
ext2fs_dirremove(struct vnode *dvp, struct componentname *cnp)
Code: Select all
/*
* ext2_delete_entry deletes a directory entry by merging it with the
* previous entry. Page is up-to-date.
*/
int ext2_delete_entry(struct ext2_dir_entry_2 *dir, struct folio *folio)
Code: Select all
[cayden@lambda: ~]$ ls /mnt/tmp/big/
total 128K
drwxr-xr-x 2 cayden cayden 120K Apr 22 15:53 .
drwxrwxrwt 3 cayden cayden 4.0K Apr 22 15:51 ..
No matter how much search-engine-ing I did, I could not find a single mention of this issue. So, what's the deal? Does every developer just reckon that directories won't get filled enough for it to matter. Is there some secret tool that deals with this that I don't know about? What do you folks do in your OSes?
Any help will be greatly appreciated because I really don't get what's going on here.