Yes, I know. I'm aware. He has a lot of data to transfer in from the disk in order to do the reverse lookup, with that much data on the disk.
I'm confused. In situations where you need to do reverse lookups, don't you normally tend to create doubly-linked lists, or other structures that you can traverse quickly and efficiently?
He could change the code so that that everything that wasn't in use was zeroed. That would help, since then he could just create a second CG map in an empty file by traversing all inodes and indirect blocks for non-zero values, not caring if the indirect blocks were referenced by inodes. Assuming indirect blocks and data blocks were distinguishable.
Like I said, there are a lot of FS changes that could help.
I'm not sure I understand how this would be a filesystem change. Since this second CG map would be used only during fsck and not otherwise present on the system, couldn't you just throw it away when you were done, resulting in a filesystem that was structurally unchanged from before?
The *reason* it doesn't matter in the CG bitmap case, is that a bitmap can only tell "allocated" vs. "unallocated"; there is no third state that means "I haven't checked this bit yet".
So you can only load up however many bitmaps you are going to check in a given pass (hopefully they all fit in memory, but if they don't fitting in the address space does you no good, because they still aren't tri-state), and then iterate every single bit reference in existance, and compare them to the ones you have, and clear them if they aren't referenced by *anyone*.
Seems to me that you could easily solve this with a second CG map (as you proposed above), that starts of initially zeroed for all blocks, and as you go through the "normal" CG maps, you turn on all the corresponding bits in the corresponding second map as you touch the blocks that are referenced.
This should be a single linear pass, and then you'd be done. If you had one I/O process and multiple worker processes actually scanning the CG maps and updating the second copy, this should just absolutely *fly*.
What am I missing here?
-- Brad Knowles, <[EMAIL PROTECTED]>
"They that can give up essential liberty to obtain a little temporary
safety deserve neither liberty nor safety."
-Benjamin Franklin, Historical Review of Pennsylvania.GCS/IT d+(-) s:+(++)>: a C++(+++)$ UMBSHI++++$ P+>++ L+ !E-(---) W+++(--) N+ !w--- O- M++ V PS++(+++) PE- Y+(++) PGP>+++ t+(+++) 5++(+++) X++(+++) R+(+++) tv+(+++) b+(++++) DI+(++++) D+(++) G+(++++) e++>++++ h--- r---(+++)* z(+++)
To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
