From owner-freebsd-hackers Tue Sep 1 23:46:29 1998 Return-Path: Received: (from majordom@localhost) by hub.freebsd.org (8.8.8/8.8.8) id XAA26666 for freebsd-hackers-outgoing; Tue, 1 Sep 1998 23:46:29 -0700 (PDT) (envelope-from owner-freebsd-hackers@FreeBSD.ORG) Received: from word.smith.net.au (castles304.castles.com [208.214.167.4]) by hub.freebsd.org (8.8.8/8.8.8) with ESMTP id XAA26659 for ; Tue, 1 Sep 1998 23:46:25 -0700 (PDT) (envelope-from mike@word.smith.net.au) Received: from word.smith.net.au (localhost [127.0.0.1]) by word.smith.net.au (8.9.1/8.8.8) with ESMTP id XAA01336; Tue, 1 Sep 1998 23:43:09 GMT (envelope-from mike@word.smith.net.au) Message-Id: <199809012343.XAA01336@word.smith.net.au> X-Mailer: exmh version 2.0.2 2/24/98 To: zhihuizhang cc: Mike Smith , hackers Subject: Re: FFS questions In-reply-to: Your message of "Tue, 01 Sep 1998 18:33:18 -0400." Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Tue, 01 Sep 1998 23:43:08 +0000 From: Mike Smith Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG > > 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