Date: Tue, 01 Sep 1998 23:43:08 +0000 From: Mike Smith <mike@smith.net.au> To: zhihuizhang <bf20761@binghamton.edu> Cc: Mike Smith <mike@smith.net.au>, hackers <freebsd-hackers@FreeBSD.ORG> Subject: Re: FFS questions Message-ID: <199809012343.XAA01336@word.smith.net.au> In-Reply-To: Your message of "Tue, 01 Sep 1998 18:33:18 -0400." <Pine.SOL.L3.93.980901183108.3474A-100000@bingsun1>
next in thread | previous in thread | raw e-mail | index | archive | help
>
> Thanks very much for your help. This morning I though I had pretty well
> understood the subject and began to write the following summary. However,
> when I finished it in the late afternoon, I find I am still have some
> confusions.
>
> [positional/rotational table]
>
> Logically contiguous blocks should be assigned with blocks of neighboring
> rotational positions.
No; logically contiguous blocks are ideally assigned from optimally
located rotational positions.
> Blocks belonging to each rotational position are
> linked together via two tables. I call them positional table and
> rotational table. The positional table gives the first blocks belonging to
> each rotational position within each cylinder in a cycle. There are
> fs_nrpos * fs_cpc entries in the positional table. The rotational table
> links the rest blocks together via block offsets. The number of entries in
> the rotational table is equal to the number of blocks in a cycle.
...
> There can be more than one physical blocks belonging to a rotational position
> in the same cylinder. All these blocks are recorded in the above two tables.
> The number of free blocks at each position for each cylinder is recorded
> in individual cylinder groups that the cylinder belongs to. When we need a
> block at a certain rotational position, we first check if the free count
> is greater than zero. If so, we can scan through those blocks belonging
> to the rotational position until a free block is find. This is a two step
> search process.
This seems to be correct.
> The macro cbtorpos() only gives us the rotational positions within one
> cylinder (There are a total of fs_nrpos such positions in a cylinder.)
> So the offset pattern recorded in the rotational table is the same
> for every cylinder. Why we need fs_cpc cylinders?
There is no guarantee that the offset pattern will be the same for every
cylinder. Consider the case where fs_nrpos is odd and the optimal
offset between one rotational position and the next is 2.
eg., allocating blocks starting with 'A':
Rotational position: 0 1 2
+---+---+---+
Cylinder 0: | A | - | B |
+---+---+---+
1: | - | C | - |
+---+---+---+
Note that I've ignored the track interleave, etc. here.
In this case, fs_cpc is 2, and cannot be made less. To understand why
a pattern is required, consider this layout:
Rotational position: 0 1 2 3 (spare)
+---+---+---+---+---+
Cylinder 0: | A | - | - | B | |
+---+---+---+---+---+
1: | - | C | - | - | |
+---+---+---+---+---+
2: | D | - | - | E | |
+---+---+---+---+---+
Again, ignoring track interleave, you can see that the goal is to keep
the gap from one rotational position to the next constant, but that's
not always possible.
> We do not let the offset pattern repeat itself. We just calculate the
> pattern and reuse it for every fs_cpc cylinders (this way we can control
> the size of the above two tables). If we let the pattern repeat itself, it
> will not neccessary happen at a cylinder boundary and can take very long.
More the issue is that it might be very large. With the standard 8
rotational groups per cylinder, you have 32 bytes per cylinder. For a
modern IDE disk where > 10,000 cylinders is not uncommon in some modes,
this would be unacceptable.
> [hardware - interleave/disk skew]
>
> The disk is revolving at a constant speed. The old disk controllers are
> slower compared with disk revolution speed. So when it have finished
> reading a sector, the disk has moved beyond the next contiguous sector.
> This is the reason for interleaving. This is already done by hardware (the
> hardware automatically converts logical sector numbers to physical sector
> numbers - relocation or mapping). The hardware only takes care of sequential
> reading, FFS has to take acount of interrupt handling and I/O initiation.
Generally correct; ffs doesn't directly handle interrupts or I/O, it
passes these through device drivers and the block cache.
> When the disk head moves from track to track, the disk continues to
> revolve. This is the reason we have the disk skew (sector skew per
> track). This setting is to be used by software (FFS in our case).
Yes, although the track-to-track interleave may also be compensated for
in hardware (by offsetting the location of sector 0 on the physical
media).
> From the definition of cbtorpos(), FFS has take account of the above two
> factors. It converts a block number to a logical sector number and then
> to physical sector number and finally to rotational position.
>
> #define cbtorpos(fs, bno) \
> (((bno) * NSPF(fs) % (fs)->fs_spc / (fs)->fs_nsect * (fs)->fs_trackskew + \
> (bno) * NSPF(fs) % (fs)->fs_spc % (fs)->fs_nsect * (fs)->fs_interleave) % \
> (fs)->fs_nsect * (fs)->fs_nrpos / (fs)->fs_npsect)
That appears to be correct, yes.
I am curious as to why you're so interested in this extremely obscure
set of calculations. I've certainly had to think hard to remember half
of this stuff, and I can't imagine any modern application for it...
--
\\ Sometimes you're ahead, \\ Mike Smith
\\ sometimes you're behind. \\ mike@smith.net.au
\\ The race is long, and in the \\ msmith@freebsd.org
\\ end it's only with yourself. \\ msmith@cdrom.com
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-hackers" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199809012343.XAA01336>