Date: Tue, 18 Mar 2003 15:26:12 +0100 From: Brad Knowles <brad.knowles@skynet.be> To: Terry Lambert <tlambert2@mindspring.com> Cc: Bakul Shah <bakul@bitblocks.com>, Julian Elischer <julian@elischer.org>, FreeBSD current users <current@FreeBSD.ORG>, fs@FreeBSD.ORG Subject: Re: Anyone working on fsck? Message-ID: <a05200f0aba9cdad802e9@[10.0.1.2]> In-Reply-To: <3E76C15F.D3C7F9A7@mindspring.com> References: <200303180459.XAA15021@goliath.cnchost.com> <3E76C15F.D3C7F9A7@mindspring.com>
next in thread | previous in thread | raw e-mail | index | archive | help
At 10:49 PM -0800 2003/03/17, Terry Lambert wrote:
> 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, <brad.knowles@skynet.be>
"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 majordomo@FreeBSD.org
with "unsubscribe freebsd-fs" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?a05200f0aba9cdad802e9>