Joined: Thu May 28, 2009 9:46 pm
Posts: 8191
Location: Midwestern USA
|
Having gotten SCSI mass storage working to a reasonable level of satisfaction on my POC V1, I am now heading toward the goal of writing a lightweight kernel for the unit. The kernel, of course, has to be able to handle the mass storage, and that means a filesystem is needed, as well as a means to get the kernel loaded into RAM and executing. If I can accomplish that then I'm on my way to writing an operating system that can do something useful.
As I'm somewhat (!) partial to UNIX-like operating systems, I am going to model my first effort on some aspects of the old UNIX System V environment that was popular for so long. For the sake of discussion, I've dubbed this yet-to-be-designed kernel 816NIX. Since I will be, in effect, creating a very lightweight form of System V, I'm going to base my filesystem on the venerable S51K filesystem that native to System V.
S51K is not too difficult to implement on 16 bit hardware like the POC. Using 32 bit integer arithmetic, a very large (1 TB) filesystem can be supported and a maximum file size of 16.7 GB is possible. Neither is possible, of course, on the ancient Seagate Hawk SCSI disk that is attached to POC. However, I certainly can set up a filesystem with pretty good capacity. Of course, before firing up the assembler, I had to work out one or two little details.
One of the first details to be hashed out has to do with a basic characteristic of the S51K filesystem and the hardware on which it was originally used. The 1K part of S51K refers to the 1 KB disk block size used in the DEC PDP-11 minicomputer on which so much UNIX development took place. I don't recall anymore if that block size was an embedded hardware feature or something that could be programmed in some fashion or another. In contrast, all SCSI disks since inception of the standard (and the SASI-controlled ST-506/412 disks that preceded embedded controller SCSI units) use 512 byte blocks by default. SCSI commands that access the medium using a logical block address (LBA) are able to access multiple blocks in a single operation, so it is possible in software achieve the effect of a virtual 1 KB block size.
Contemplation of the S51K's design (incidentally, S51K is still supported in Linux), as well as the basic mannerisms of most SCSI disks, led me to decide on a 1 KB block size. From a structural standpoint, the S51K filesystem's architecture better fits a block size that is an even multiple of 1 KB. This characteristic nicely dovetails with another important feature of modern SCSI disks, which is full-track buffering. Since a 1 KB block size means two contiguous 512 byte blocks are accessed in a single transaction, and since filesystem structure access involves contiguous blocks, the aggregate time consumed in disk access, when measured on a per block basis, is less than that of a single 512 byte block access. Full-track buffering also means access of other blocks on the same track do not require access to the medium.
Just about all SCSI disks that conform to the SCSI-2 standard of 1994 also support being formatted to some block size other than 512 bytes. For example, the Seagate Product Manual for their line of SCSI-2 disks says that block sizes from 256 to 4096 bytes are possible. I briefly thought about doing this but dismissed the idea. Not all disk accesses would necessarily be 1 KB in size—reading the master boot block, for example. Making 1 KB the default could lead to some awkward coding situations. So I decided to stay with the default 512 byte size.
The next step was to contemplate the S51K filesystem structure and see if there were areas that could benefit from changes that would ease adaptation of the filesystem to the POC's environment. Actually, there is little about the S51K filesystem that can be improved without going into more esoteric features, such as transaction intent logging and journaling (both of which help in reducing filesystem damage in the event of a crash). Ken Thompson did a good job in anticipating the future, especially the growth of disk sizes as the SCSI standard evolved. However, I did come up with some changes that I thought would be benificial.
The first was to increase the maximum filename size from the S51K's 14 characters to 30 characters. I did this by increasing the size of a directory "slot" from 16 to 32 bytes. Of the 32 bytes, two are used for the 16 bit inode number associated with the filename, leaving the balance of the slot for the filename. While this change increases the amount of space consumed by a directory with an arbitrary number of filenames, it's not much of a concern with the capacity of modern disks. Although a filename search of an S51K directory is linear, the full-track buffering of modern drives greatly reduces the across-the-bus transfer time required to read in pieces of the directory.
Another change I came up with is the notion of separating internal file block addresses from the physical structure of the disk. By way of explanation, a SCSI disk is accessed using a zero-based logical block address (LBA), which the drive's controller internally translates into a cylinder-head-sector address. This feature assures that the disk drivers in any operating system kernel will work with any SCSI disk, regardless of size and/or manufacturer. In order for a 1 KB filesystem block access to occur, two physical blocks must be accessed in succession, using the LBA of the first block only and specifying two blocks in the command descriptor block (CDB) sent to the disk when the command is issued. Since block addresses effectively skip by twos, some odd math gets involved that actually increases the MPU's workload in determining where on the disk accesses must occur.
So what I have done is used the idea of a logical block offset (LBO) within the filesystem. The offset is zero-based to the filesystem block which is the first physical block of an S51K filesystem. If during the access of a file LBO 21 is required, the MPU simple takes that number, doubles it and adds the result to the superblock's LBA. If the filesystem gets relocated it can be moved en masse, since the LBOs associated with all files don't have to change. Also, use of an LBO simplifies allocation of a block to a file when needed. The translation from an LBO to an LBA is simple 32 bit integer arithmetic—doubling an LBO is a case of a 16 bit ASL followed by a 16 bit ROL. By design, filesystems will always start on an even LBA, although there is no special requirement for this. However, even addressing takes better advantage of full-track buffering, which will help overall performance.
The rest of my filesystem would be recognizable to Ken Thompson, since, as I earlier said, there's little to improve. Here are the notes from the declarations file I wrote that describes the layout of a bootable disk with two filesystems.
Code: DISK LAYOUT & SYSTEM START-UP INFORMATION
———————————————————————————————————————————————————————————————————————————————
The POC series includes a SCSI-2 subsystem equipped with an 8 bit bus, which
means up to 7 devices of various types may be attached. It is only possible to
create a filesystem on a random access device. In the following discussion,
"disk" will refer to any random access storage device, be it a hard drive, CD-
ROM or other mass storage device.
Each disk can support up to 4 filesystems. Each defined filesystem has an en-
try in the filesystem table that is located in physical block $00 of the disk.
Traditionally, this block is referred to as the "boot block" (or master boot
block), even if the disk is not bootable.
If a disk is bootable, the boot block will also contain the master boot machine
code that is the 1st step in bringing the system up to full operation. The 1st
filesystem on this disk will be the boot filesystem & will contain the kernel.
Pictorially, the layout of a bootable disk with 2 filesystems is as follows:
DISK LAYOUT Starting Physical Block LBA
+===============================+ ======================================
| | The starting LBA of this filesystem is
| | defined by pb_fs002, which is equal to
| user filesystem | the root filesystem's size (physical
| | blocks) added to the root filesystem's
| | starting LBA (defined by pb_fs001).
+===============================+ $???????? (pb_fs002)
| |
| root filesystem |
| |
+===============================+ $00000022 (pb_fs001)
| reserved |
+———————————————————————————————+ $00000012 (pb_rsrvd)
| stage 1 boot blocks |
+———————————————————————————————+ $00000002 (pb_stag1)
| not used |
+———————————————————————————————+ $00000001 (pb_unusd)
| master boot block |
+===============================+ $00000000 (pb_mboot)
By convention, the boot filesystem is called root & is referred to in the dir-
ectory tree as "/". The user filesystem can be given an arbitrary name, other
than root, & is often referred to as "/u" in the directory tree, "/u" being the
mount point in the root filesystem for the user filesystem (i.e., the command
cd /u will place the user in the user filesystem).
The above layout also applies to a non-boot disk. However, blocks $00000002
through $00000011 inclusive aren't used & no master boot code is present in the
boot block. Refer to the boot.65s & stage1.65s source files for more informa-
tion.
—————————————————
FILESYSTEM LAYOUT
—————————————————
The filesystem models some aspects of the UNIX S51K filesystem, but with addit-
ions & changes to better acclimate to the W65C816S environment. Like the S51K
filesystem, the 816NIX filesystem uses a 1 KB logical block size, which on a
hard disk, is 2 contiguous 512 byte physical blocks. Although handling storage
in this fashion is less efficient in terms of disk space utilization (consider
that a file with 1 byte would consume 1024 bytes on a hard disk), it tends to
promote better structural efficiency.
Pictorially, the layout of a filesystem is as follows:
MODIFIED S51K FILESYSTEM LAYOUT Logical Block Offset (LBO)
+=================================+ ==================================
| | starting LBO depends on the number
| data block array | of data blocks in filesystem
+—————————————————————————————————+ $?????? (fs_dba)
| data block allocation map (BAM) |
+—————————————————————————————————+ $000409 (fs_bam)
| inode array |
+—————————————————————————————————+ $000009 (fs_inode)
| inode allocation map (IAM) |
+—————————————————————————————————+ $000001 (fs_iam)
| superblock |
+=================================+ $000000 (fs_super)
All filesystem accesses are in "logical blocks," using a "logical block offset"
or LBO, which is not to be confused with a physical block address (LBA). The
number of physical blocks in a logical block is 2^n, where n is any positive
integer. Hence 2^0 means a logical block is 1 physical block, 2^1 is 2 physi-
cal blocks, etc. This arrangement simplifies the conversion of an LBO to an
LBA.
The following discussion will elaborate on each major element in a filesystem.
§ Superblock. The superblock contains the administrative data needed by the
kernel to mount the filesystem, that is, to make it accessible to both kernel
functions & applications. A corrupted superblock will render the filesystem
inaccessible.
§ Inodes. In a sense, the inodes are the files, as inodes encapsulate the ad-
ministrative data needed to access file contents. Inodes identify where each
file is located, how much data is in it, when that data was last accessed, &
so forth. Each inode is assigned a 16 bit number ranging from $0001 (1) to
$FFFF (65535). An inode number in one filesystem has no relationship to the
same inode number in another filesystem.
§ Data blocks. The data blocks are where file data are stored. In the case of
large files, indirect address blocks are used to track where the data blocks
proper are located. This arrangement allows the kernel to use non-contiguous
blocks in an efficient manner. Each file's inode has a block address table
that points to the 1st 10 data blocks & up to 3 indirect address blocks.
Hence the data in any file whose size is no more than 10 KB can be accessed
with a single disk access.
§ Inode allocation map. The IAM is a bitmap that indicates which inodes are in
use & which are not. The 1st bit indicates the status of inode $01, the 2nd,
inode $02, etc., with a set bit indicating that the corresponding inode is
available. Inode $00 is not used, as $0000 in the inode field in a directory
slot indicates a deleted file. When a new file is created, the kernel will
scan the IAM to find the 1st available inode.
§ Block allocation map. The BAM is a bitmap that indicates which data blocks
are in use & which are not. The 1st bit indicates the status of the 1st data
block, the 2nd bit, the 2nd data block, etc., with a set bit indicating that
the corresponding block is available.
When data is written to a new or truncated file, the kernel will scan the BAM
to find the 1st available block. If data is appended to an existing file, a
new block will be allocated only when the last block in the file is filled.
If the file size exceeds 10 KB following a write, an indirect block will be
allocated, as well as a data block.
As previously noted, all locations within a filesystem are addressed by a logi-
cal block offset (LBO), which is a signed 32 bit value & is zero-based relative
to the superblock. The corresponding LBA for any LBO is computed as follows:
LBA = LBO * (2^n) + SLBA
where LBO is the zero-based logical block number & SLBA is the LBA of the sup-
erblock. The number of physical blocks to be accessed will be 2^n. LBOs with-
in files are stored as 24 bit quantities & expanded to 32 bits by the kernel
during file access, allowing a theoretical maximum file size of 16.7 GB. In
practice, this limit cannot be attained, as indirect blocks count as part of
the total block count of a file.
Note in the above filesystem pictograph that the space assigned to the super-
block, IAM & inode array is fixed, as the sizes of these data structures are
atomically hard coded in the present implementation. The size of the BAM is
determined by the number of data blocks in the filesystem, which in turn, is
determined by the size of the filesystem minus the overhead of the superblock &
inode structures. This relationship may be expressed as:
O = (N_SB + 1) + N_IAM + N_INA
and:
FSS = O + (D + (D / r))
where (letter) O is the space consumed by the superblock (N_SB), IAM (N_IAM) &
inode array (N_INA), D is the number of data blocks & r is the number of bits
in a logical block. FSS is the total filesystem size. All block expressions
are logical blocks.
In the above equation, the only unknown is D. FSS is set by the administrator
at the time the filesystem is created, O is static & r may be empirically deter-
mined:
r = (2^n) × b
As earlier explained, 2^n is the number of physical blocks in a logical block &
b is a constant equal to the number of bits in a physical block.
To determine D:
FSS - O = D + (D / r)
For simplification purposes:
U = FSS - O
followed by:
U = D + (D / r)
where U is the number of blocks available for data & the BAM.
With U & r known, D can be determined by:
D = r × U / (r + 1)
With D known, the number of BAM blocks required for D data blocks can also be
determined:
B = U - D
The number of active bits in the BAM would be equal to D.
——————————————
SYSTEM STARTUP
——————————————
At power-on or reset, the MPU jumps through the hardware reset vector, which is
atomically defined as $00FFFC-$00FFFD. The reset code in the BIOS ROM starts
by disabling IRQs, setting binary arithmetic mode & switching the MPU to 65C02
emulation & then back to 65C816 native mode. The disabling of IRQs & resetting
to binary mode is necessary to deal with the case when software calls the reset
routine—these actions are automatic when a hardware reset occurs.
The effect of switching MPU modes is to default the direct page & program bank
registers, reset the stack pointer to $000100, & set the accumulator & index
registers sizes to 8 bits. Hence the MPU starts off in a known state before
executing the balance of the reset code.
With these preliminary operations completed, normal system startup will proceed
as follows:
1) The BIOS will start by testing zero page & stack memory. Any failure will
cause an immediate system halt. The BIOS will not be able to report that
the test has failed, as no hardware intialization will have been performed
at this stage of the boot process & thus no ouput to the console will be
possible.
2) Next, the timekeeping & I/O hardware will initialized & jiffy IRQs will be
started. The power-on self-test (POST) banner will be displayed & the bal-
ance of memory will tested. As testing proceeds, a memory count will be
displayed. If defective memory is encountered, a terse error message will
be displayed & the system will be halted.
3) Following POST, the SCSI subsystem will tested & configured, & the SCSI bus
will be reset. If testing fails, a terse error message will be displayed &
control will be given to the ROM-resident machine code monitor.
4) Following SCSI subsystem configuration, the SCSI bus will be interrogated
for the presence of devices & the SCSI device table located at $000110 in
RAM will be populated for each detected device. Disks will be issued the
"start unit" command & tape drives will be issued the "load tape" command.
A device enumeration will be displayed.
5) Next, the BIOS will attempt to load the boot block from the designated boot
device (usually SCSI ID 0) into RAM at $000400. Note that the BIOS knows
nothing about filesystems & can only load the boot block & execute the mas-
ter boot code therein. If the boot device fails to respond or doesn't have
a valid boot block, control will be given to the machine code monitor. No
error message will be displayed should this happen.
6) If step 5 was successful, the master boot code will be executed. As space
in the boot block for executable code is constrained, master boot will load
the stage 1 boot code, which is stored at physical block 2 on the disk, in-
to RAM at $000600. A total of 16 physical blocks will be loaded. If stage
1 code cannot be loaded, an error message will be displayed & control will
be given to the machine code monitor.
7) Master boot will examine the stage 1 boot image to verify that it contains
valid code. If stage 1 is invalid, an error message will be displayed &
control will be given to the machine code monitor. Otherwise, master boot
will pass control to the stage 1 boot code.
8) The stage 1 boot code will examine the filesystem table located in the boot
block (which will remain resident in RAM) to find the root filesystem on
the disk. If it is found, an error message will be displayed & control
will be given to the machine code monitor.
9) If the root filesystem is found, "Stage 1 boot..." will be displayed & the
root directory will be searched for the file bootos, which contains the
stage 2 boot code. As bootos is loaded it will be checked for corruption
to avoid the potential for root filesystem damage. If bootos cannot be
found, is found to be corrupted or if the root directory is unreadable, an
error message will be displayed & control will be given to the machine code
monitor.
10) If found, bootos will be loaded into RAM at $00A000 & executed. bootos is
the 1st program executed during the boot sequence that is interactive. It
will start by clearing the console screen, displaying a banner & searching
the root filesystem for the file 816nix, which is the default kernel. If
816nix is not present, bootos will issue a warning message but will contin-
ue to the next step.
11) bootos will display the boot prompt & wait for up to 15 seconds for user
input. If there is no user response, bootos will time out & attempt to
continue the boot process.
12) If the user presses [CR] without typing anything, bootos will continue the
boot process in the same fashion as if it had timed out.
13) If the user enters a recognizable command it will be executed & then bootos
will await another command.
14) Upon being commanded to boot or having timed out at the boot prompt, bootos
will load the main kernel into RAM at $000200 & interrupt handler code into
RAM at $00E000. As the kernel is read in from 816nix, it will be checked
for possible corruption. Should corruption be detected, or if 816nix can-
not be found, bootos will display an error message & give control to the
machine code monitor.
15) Upon successfully loading the kernel, bootos will go to the kernel's start
vector. The kernel, in turn, will complete the system initialization proc-
ess & initd. initd will complete the startup & when everything is ready it
will be possible to log in.
———————————————————————————————————————————————————————————————————————————————
_________________ x86? We ain't got no x86. We don't NEED no stinking x86!
Last edited by BigDumbDinosaur on Wed May 18, 2022 8:47 pm, edited 2 times in total.
|
|
Login
Register
FAQ
Search
