ext2 searching

[PavelChekov]

Hi

This is more of a theory question than like code review, so I hope I've put it in the right forum. I've written a basic ext2 driver in assembly for my bootloader, that searches for the kernel under the root directory. I simply loop through the block addresses, looking for it, and then the indirected, and doubly indirected, and triply, but it takes nearly 10 minutes to loop through all of the blocks and check them for the appropriate directory entry. Am I going about this the wrong way? Is there some more efficient algorithm?

Thanks

[Octocontrabass]

Assuming you're not using an indexed directory, there's no more efficient algorithm. If you want to search for an entry in the directory, you have to read each block in the directory until you either find the matching entry or reach the end of the directory.

For most directories, ten seconds would be way too long. What are you doing that takes ten minutes?

[PavelChekov]

Yes, I thought it was way too long. I am doing a disk read into memory for each block which was my only thought, but I suspect there may be something wrong with the way I implemented it. I will reexamine my code.

[iansjack]

Reading 1024 byte blocks one at a time is pretty inefficient. Have you thought about implementing some buffering so that you can load larger amounts? How big is your root directory that you need to do a large search? On my Mac the root directory only has sixteen entries, and most Linux systems are that order of size. It should only take a moment to search through that for a particular file/directory.

[PavelChekov]

I think I found my problem: I was not checking for and skipping over the zero entries and sparse files was enabled. That said, is implementing linked list directories even worth it, or is that so rare as to be obscure?

Also, the documentation explicitly states that indexed directories are backwards-compatible with linked directories, however, looking at the actual on-disk specification for how the directory blocks are laid out, this does not make sense. Am I missing something, or can you not read an indexed directory the same way you would a linked one?

Reading 1024 byte blocks one at a time is pretty inefficient. Have you thought about implementing some buffering so that you can load larger amounts? How big is your root directory that you need to do a large search? On my Mac the root directory only has sixteen entries, and most Linux systems are that order of size. It should only take a moment to search through that for a particular file/directory.

I do have buffering, which is why this really puzzled me. My root directory has a comparable number of entries.

[Octocontrabass]

I think I found my problem: I was not checking for and skipping over the zero entries and sparse files was enabled.

I don't know if directories can be sparse files, but assuming they can, it would have to be an enormous directory to take ten minutes to read the whole thing. Are you sure the problem is really fixed and not just hidden?

That said, is implementing linked list directories even worth it, or is that so rare as to be obscure?

Linux's ext2 driver doesn't support indexed directories, so I'd say implementing linked-list directories is worth it.

Am I missing something, or can you not read an indexed directory the same way you would a linked one?

The index data is stored in the padding between linked-list entries. As long as you're properly skipping over the padding, you can read an indexed directory exactly the same way you read a linked-list directory.