ext2 driver readdir is O(N^2)
If would probably be better if the kernel used an iterator cookie so the seek can continue from an efficient point. But what about race conditions? Well, dirents don't cross block boundaries, it could store the block index and a logical dirent offset into that block, that way it has to seek less. Also, it would probably be more efficient if it could ask for multiple dirents at once. Maybe all of them? The kernel could queue them up and deliver them efficiently (a snapshot) without race condition to userland.