Kestrel-3

Check-in [e485309137]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Bring in the project report org-mode document. Tracks stepwise refinement of system firmware, hardware design choices, etc.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: e485309137bacc7970a3701b04ac05fde00e2c531dbf2cd0c9ffa543a64b7bfc
User & Date: kc5tja 2019-09-08 23:48:01.114
Context
2019-09-09
00:34
Missing word radically alters intended meaning of a sentence. check-in: 2c2434a794 user: kc5tja tags: trunk
2019-09-08
23:48
Bring in the project report org-mode document. Tracks stepwise refinement of system firmware, hardware design choices, etc. check-in: e485309137 user: kc5tja tags: trunk
2019-09-05
03:41
.skip and .zero support check-in: 447c21378e user: kc5tja tags: trunk
Changes
Unified Diff Ignore Whitespace Patch
Added REPORT.org.




















































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
* Introduction

Part of me is inspired by the book, Project Oberon, to write up a kind
of report of what I'd like to see in one embodiment of the Kestrel-3
homebrew computer, pre-video-hardware of course.  I happen to have a
RISC-V software emulator, e2, which I believe can be used to emulate
to reasonable fidelity what the finished hardware will be like.

The hardware will consist of a single FPGA board, with the following
equipment on-board:

1. At least 512KB of RAM
2. At least 2MB of flash ROM, at least a portion of which is also used
   to program the FPGA itself.
3. One UART for the human operator.
4. One UART serving to provide access to secondary storage resources.
5. A programmable interval timer.
6. A KCP53000-compatible processor driving everything.

Notably absent are things like DMA channels and other intelligent
controllers.  Similarly, expansion buses and the like won't exist in
this embodiment, as there won't be enough resources on the FPGA to
house them.  Future configurations will be built to include these
things, however.

In particular, I'd like to study the use of various design techniques
which I hope will make my life much easier.  As I write this, I'm
finding my time to work on the Kestrel Computer Project at an all-time
minimum; having even several hours of productivity per week to devote
to the project is today a dear luxury.

I will be switching between various different design and
implementation methods.  In particular, I'd like to explore the use of
[[https://en.wikipedia.org/wiki/Top-down_and_bottom-up_design#Software_development][Stepwise Refinement]], a technique I haven't used in a long time.  In
particular, I'm interested in seeing how it can be applied both at the
systems level as well as individual procedure development.  Of course,
[[https://en.wikipedia.org/wiki/Test-driven_development][Test-Driven Development]] will continue to play a critical role as well.
It's a matter of knowing where one method works better than another,
and applying and switching amongst these tools accordingly.

* Goal for Kestrel-3 Pre-Media
The first release of the Kestrel-3 homebrew computer might seem
perhaps a bit schitzophrenic.  One of the core requirements for the
computer is that it remain useful to its owner even in the total
absence of secondary storage.  Insofar as it is possible, that means a
fully functional programming environment should be made available in
the firmware of the computer.  Historically, most computers have
elected to use a variant of the BASIC programming language for this
purpose.  However, for the Kestrel-3, I opt for a dialect of Forth
instead.  The Forth environment would give the user an environment
powerful enough to perform basic integer calculations.  With secondary
storage present, the Forth environment also allows for the storage and
retrieval of Forth software from block storage.

With secondary storage, it becomes possible to support more
sophisticated operating systems beyond the built-in Forth environment.
One such candidate is a port of the Tripos operating system,
tentatively called VertigOS.[fn::This name was chosen back in 2018
through an informally conducted on-line poll between both Twitter and
Mastodon social media sites.  VertigOS was suggested as a joke on my
furry character's name, Vertigo; nonetheless, it won in both
communities without much competition.]

Given some secondary storage device with a properly installed VertigOS
image, the Kestrel-3 should support a mechanism to automate
bootstrapping it.  Currently, I envision the user typing a command at
the Forth OK prompt, such as ~go-vertigos~ to boot directly into it,
or ~boot-menu~ to bring up a built-in boot manager, through which the
user can then select the VertigOS image desired.  However, this might
change in the future, especially post-media.  In this configuration,
the user might need to press a key combination during the boot
sequence to /force/ the computer to drop into ROM-resident Forth if an
external OS is available to bootstrap automatically.  While this is
more inline with how other computers work, it remains to be seen if
this is a preferred approach.  I'll cross that bridge when I get
there.

* Hard Reset/Power-On ("Cold") Bootstrap Process
When powering on the Kestrel-3, the computer will present a boot menu
to the operator.  The operator should type the letter or number
corresponding to the boot option desired.  In the absence of any
attached storage, only two items should appear:

1. Forth with auto-boot
2. Forth without auto-boot

With attached storage, additional items may appear if bootable images
are properly installed on any attached storage media.

The boot menu itself can be implemented in Forth, before the user ever
sees an OK prompt.  Selecting option 1 simply exits the menu, clears
the dictionary and stacks, and invokes ~LOAD~ on a well-defined block.
When that's done, it drops to the OK prompt.  Selecting option 2 exits
the menu, clears the dictionary and stacks, but just drops to an OK
prompt.  No attempt is made to auto-load any blocks.

The user may re-enter the boot menu at any time by invoking the word
~BYE~, so as to exit from the Forth environment.

I anticipate that this is what the firmware should perform upon
cold-boot:

#+BEGIN_SRC
TO cold-boot the Kestrel-3 DO
  Relocate the ROM image into RAM for faster performance.
  Initialize the Forth binary interface.
  Cold-boot the Forth interpreter.
END
#+END_SRC

Since the system's flash ROM is a serial device, the processor will
need to wait hundreds of clock cycles for each instruction it executes
out of ROM.  This is why we relocate the software image in ROM into
RAM before executing the rest of the bootstrap process.

Initializing the Forth binary interface involves determining
(statically or dynamically) where to place the data and return stacks,
any user variables, and of course the dictionary itself.

Once the VM has been established, we can then "cold boot" the Forth
environment.  It is here that the boot menu is built and presented to
the user.

#+BEGIN_SRC
TO cold-boot the Forth interpreter DO
  Discover the operator's console.
  Configure the Forth bootmenu items.
  Show startup banner.
  Discover available bootable volumes.
  DO FOREVER
    Present menu to the operator.
    Wait for a key.
    IF selection made identifies a boot option THEN
      Attempt to boot from the selected source.
      Notify the user of the failed boot attempt.
    ELSE
      Notify the user of the erroneous selection.
    END
  END
END
#+END_SRC

Device discovery necessarily implies device configuration as well.  In
the case of the operator's console, this should be configured
automatically when the computer comes out of reset.  (Still, when
media hardware is later contributed to the computer's configuration,
somehow choosing between the debug console and the VGA/keyboard
interface will need to happen.)

Discovery and configuration of mass storage devices will need to
happen as well; however, I'll defer the details of this step until
later in this document.

When booting into the Forth environment, the following sequence of
code can be performed.  Note that the decision of whether or not to
auto-load was made when the user selected the appropriate menu
selection in the boot screen.

#+BEGIN_SRC
TO boot into Forth environment DO
  IF user wants to perform auto-boot sequence DO
    Find valid Forth auto-start block.
    IF found THEN
      Load Forth auto-start block.
    ELSE
      Report that no auto-start block was found.
    END
  ELSE
    Report that auto-start was skipped on user request.
  END
  Quit into Forth interpreter.
END
#+END_SRC

* Forth Interpreter
** Interpreter
I probably won't delve as deeply into the innards of the Forth
environment as I will other components of the firmware, if only
because of how fluid Forth's implementation details can be.  However,
I think it's useful to sketch something out if only to have a crude
idea of how I'd like the system software to be structured.

The interpreter is entered via the word called ~QUIT~.

#+BEGIN_SRC
TO Quit into the Forth interpreter DO
  Reset the return stack pointer.
  Set input source to the operator's console.
  DO FOREVER
    Read one line of text.
    Interpret the line of text received.
    IF OK prompt is enabled THEN Print "OK" END
  END
END
#+END_SRC

Note that this "outer interpreter" (as it's known formally in the
Forth community) resets the return stack pointer, but not the data
stack pointer.  When something produces an error, however, the data
stack does get reset.

#+BEGIN_SRC
TO Handle uncaught exception DO
  Direct output to operator's console.
  Print error code of current exception.
  IF error code is a valid system exception code THEN
    Print descriptive error message.
  END
  Reset data stack.
  Quit into the Forth interpreter.
END
#+END_SRC

** Exception Handling
An uncaught exception happens when a program issues a ~THROW~ command
without a matching ~CATCH~ for it.  The simplest way to make this work
is to define ~THROW~ so that it just handles the "uncaught" exception
and immediately re-enters the Forth interpreter.  This results in the
data and return stacks being reset, so there's chance for infinite
regression.

When ~CATCH~ is invoked, however, then ~THROW~ must somehow return
from the ~CATCH~ exactly as if the definition had returned to it.
This might involve skipping a potentially large number of nested
definitions.

The most obvious way I know to implement this kind of either-or
behavior is with a dispatch vector for ~THROW~.  By default, before
any code is able to run ~CATCH~, it is configured to refer to the
unhandled exception handler above.  In this way, any
exception-throwing code will (in)directly find themselves invoking
~QUIT~, which is the intended behavior.

#+BEGIN_SRC
TO Throw an exception DO
  Delegate through the current throw handler vector.
END
#+END_SRC

The ~CATCH~ word is responsible for /trying/ to execute a Forth word
that is capable of throwing an exception.  Since we desire strongly to
catch such exceptions, we need to establish some runtime attributes
that allow us to recover gracefully instead of just dropping into
~QUIT~.  Part of this is telling ~THROW~ not to just invoke the
unhandled exception handler directly.  Additionally, we need to know
where to restore the return stack pointer to when an exception does
occur.

This code should work for the happy path situation as well.  Assuming
the supervised word does /not/ raise an exception, we want to dispose
of the exception handling scaffolding seamlessly, and return a 0 to
the calling procedure, indicating that no exception happened.

#+BEGIN_SRC
TO Try to run a Forth word capable of throwing an exception DO
  Create an exception handling frame with the current return stack pointer and system variables.
  Prepend the frame onto a list of exception handler frames.
  Set the throw vector to catch an exception.
  Execute the referenced colon definition.
  Unlink the head of the exception handler list.
  Restore system variables.
  Restore the return stack pointer.
  Return literal 0 indicating no exception.
END
#+END_SRC

But, in the event of an exception, a third routine is necessary to
restore the environment.  At a minimum, this environment includes the
data stack and return stack pointers, the current throw vector, and
the current input source specification.  This is the routine that the
above code will need to vector invokations of ~THROW~

The first thing we check for is if the exception code is 0; if so, we
eat the value and just return like nothing ever happened.  This is
required semantics by ANS Forth, and is what allows code fragments
like ~S" DEVICE:PATH/FILE" R/W OPEN-FILE THROW handle !~ to work as
intended.

However, if the exception code is non-zero, we need to return that
code back to the caller of the corresponding ~CATCH~.  We do this by
restoring the environment from the exception handler frame (but
without disturbing the current data stack contents) and unlinking it,
just as we did in the happy path scenario.

#+BEGIN_SRC
TO Catch an exception DO
  IF exception code is 0 THEN Do nothing and just return. END
  Save exception code in exception frame.
  Unlink the head of the exception handler list.
  Restore system variables.
  Put exception code back onto the data stack.
  Restore the return stack pointer.
END
#+END_SRC

Thus, for the exception handling mechanism to work, we need two user
variables:

- Pointer to head of exception frame list.
- Vector to ~THROW~ implementation.

Each exception handler frame will need, at a minimum, the following
structure (in no particular order):

| Field                                       | Purpose                                                                          |
|---------------------------------------------+----------------------------------------------------------------------------------|
| next                                        | Links to the next oldest exception handler; 0 if none.                           |
| throw vector                                | Preserves the throw vector that was in effect at the time the frame was created. |
| input source parameters                     | Preserves the caller's input source.                                             |
| data stack pointer                          | Preserves the caller's data stack.                                               |
| return stack pointer                        | Preserves the caller's return stack.                                             |
| floating point stack pointer (if supported) | Preserves the caller's FP stack.                                                 |

Note that we don't store the USER variable pointer, because the
exception handling chain is itself a USER variable.

** Secondary Storage
At some point in time, the computer will need to be turned off.  When
this happens, the operator probably has a number of programs and data
that they wish to be preserved for the next time the computer is to be
used.  To facilitate this, the Kestrel-3 (like all reasonable
computers) provides access to "offline storage", "secondary storage",
"direct access storage", "attached storage", or any manner of other
descriptions of memories which hold their contents when the power is
removed.

In this document, as you might have already guessed, I use the term
"secondary storage" to refer to this non-volatile memory.  However,
this is not to be intended to be taken as official verbiage for the
concept.  It's just what comes naturally and conveniently to me.

*** Concepts
**** Partitions, Volumes, Media, Units, Controllers, and Devices
*Physical media* is required to store information when power is off.
These media can take the form of solid-state storage devices, like USB
memory sticks, SD cards, or SATA-type solid-state hard drives.  Media
can also take other forms, like spinning disks of magnetic material
(e.g., floppy disks, hard disks, zip disks, etc.), or even strips of
magnetic tape.  It is frequently the case that these media are
uniquely identified for the operator's convenience ("where did I store
that file again?  Oh, yeah, it's on DH0:, drive B:, etc.").  However,
there are storage systems which use multiple media to implement a
single logical storage space, such has RAID systems.  Similarly, a
single medium can even store /multiple distinct storage spaces/, such
as a hard disk with multiple *partitions*.

For clarity, then, we'll call these logical storage spaces *volumes*,
and simply say that /usually/ a single volume consists of a single
medium; however, in some cases, a single volume can be spread across a
number of different media, or that a single medium can host multiple
volumes.

Sometimes, storage media are permanently mounted into a "drive" or
other controlling piece of hardware.  Other times, media can be
removed and changed for others.  For this reason, we distinguish
between *units* (into which volumes can be mounted) and the volumes
and media they support.  These units, then, are controlled by some
kind of *device*.  Frequently, a single, physical storage device
combines the role of device and unit into a single package (hence the
word "integrated" in the old "integrated drive electronics," or IDE,
hard drives).  In other cases, these concepts are split (e.g., as with
a floppy disk controller chip controlling two physical disk drive
mechanisms).

The following table helps to relate the roles each of these concepts
takes in the complete storage implementation.

| Role   | Purpose                                                                                   |
|--------+-------------------------------------------------------------------------------------------|
| Medium | Physically holds the 1s and 0s that comprise your data.                                   |
| Volume | A logical collection of storage space.                                                    |
| Unit   | A physical mechanism that is responsible for reading the 1s and 0s on its media.          |
| Device | AKA controller.  This is responsible for coordinating the activities of all of its units. |

Another note on vocabulary: in colloquial terms, the word /device/ can
refer to either the physical controller /or to its device driver
software,/ depending upon context.  In most cases, it's either clear
what that context is, or it doesn't practically matter.  Where I need
to make a distinction in this document, I will opt to use /device/ to
refer to the device driver and /controller/ for the physical piece of
hardware that software is responsible for.

Let's pretend an operator has configured a Kestrel-3 with a 128MB SD
card, a RAID-10 controller with four 2GB hard drives, and two 1.44MB
floppy drives.  The following configuration illustrates the logical
relationships between controllers and units, and the media they
interact with.  Note that floppy drive #1 has no disk inserted, hence
no medium.

#+BEGIN_SRC
+------------+    +------------+    +---------+    +--------+
|            |    |            |    |         |    |        |
| Computer   |<-->| Controller |<-->| Unit    |<-->| Medium | (SD Card)
|            |    |            |    |         |    |        |
+------------+    +------------+    +---------+    +--------+
    ^    ^
    |    |        +------------+    +---------+    +--------+.
    |    |        |            |    |         |    |        | |
    |    +------->| Controller |<-->| Unit    |<-->| Medium | |  (RAID-10 Drives x4)
    |             |            |    |         |    |        | | 
    |             +------------+    +---------+    +--------+ | 
    |                                                `--------+
    | 
    |             +------------+    +---------+              
    |             |            |    |         |              
    +------------>| Controller |<-->| Unit    |               (Floppy Drive #1)
                  |            |    |         |              
                  +------------+    +---------+               
                         ^
                         |          +---------+    +--------+
                         |          |         |    |        |
                         +--------->| Unit    |<-->| Medium | (Floppy Drive #2)
                                    |         |    |        |
                                    +---------+    +--------+
#+END_SRC

(Remember this example; we'll be referring to it frequently as we
discuss further implementation concepts.)

**** Block Space
As you can see, there are a lot of moving parts that cooperate in any
reasonable storage system.  At some level, Forth, too, must deal with
all these components and how they relate to each other.  For /most/
needs, however, we can get away with a significantly simplified view
of the storage landscape.

Historically, Forth systems with block I/O do not attempt to provide
/any/ abstractions for fixed secondary storage.  Entire devices are
assigned unique ranges of block numbers.  Referring back to our
hypothetical storage configuration, the table below shows the raw
storage capacity of each of these devices:

| Device       | # of Blocks |
|--------------+-------------|
| SD Card      |      131072 |
| RAID Storage |     2097152 |
| Floppy #1    |        1440 |
| Floppy #2    |        1440 |

In order to be available for use in Forth, these all have to be
"placed" somewhere in the unified block space.  Arbitrarily, we might
just line them all back to back, like this:

| Device       | # of Blocks | First Block | Last Block |
|--------------+-------------+-------------+------------|
| SD Card      |      131072 |           0 |     131071 |
| RAID Storage |     2097152 |      131072 |    2228223 |
| Floppy #1    |        1440 |     2228224 |    2229663 |
| Floppy #2    |        1440 |     2229664 |    2231103 |

Block storage has always been meant to provide raw access to attached
storage.  Respecting the boundaries of different partitions was the
responsibility of the software you ran on top of Forth.  Further, if
your computer supported /removable/ media like floppies, then you had
two options: you either treated the floppy as a hard drive (in that
you could never remove the disk once your application was running);
or, it was never mapped into block space at all, requiring you to
depend upon special accessor programs to transfer data between the
removable media and fixed media.  Despite how draconian these
solutions might seem, it works surprisingly well for a vast array of
applications, particularly once you realize most applications /want/
to work in logical records of some kind, and not in the specific
details of any byte-oriented filesystem interface.[fn::This is not to
undermine the value of filesystems; they absolutely do have their
uses.  It's just that Forth recognizes that most applications are
simpler in design if you can avoid having to adapt what was originally
designed for reel-to-reel tape drives to what is most natural for the
application.]

Kestrel's Forth tries to offer a similarly simplified view of
secondary storage to the operator; rather than providing individual
names to every layer in the stroage abstraction, it exposes a single,
unified, flat namespace into which /all/ attached secondary storage
devices and/or their units are accessed.  Just as in the earliest
Forth systems, this storage space is addressed by /number/, not by
name; it is chopped up into 1024-byte long *blocks* (sometimes also
referred to as *screens*, especially used to hold Forth program
listings).

Going back to our hypothetical storage configuration, if you wanted to
copy a 1MB chunk of data from the SD card to the second floppy drive,
you'd arrange to copy blocks from, say, 512 to 1536 over to 2230000
to 2231024.  To do the reverse, you'd obviously swap the block numbers
in the copy operation.

The Kestrel's Forth environment is a 64-bit Forth environment.  Since
each block is sized at 1024 bytes (2^10 bytes), and there are
approximately 2^64 unique block numbers, that means that Kestrel's
Forth makes just shy of *19 zettabytes* (2^74 bytes) of logical
storage space available for your use.

**** Identifying Volumes
Volumes which are made accessible to a running Forth system are said
to be *mounted* into a unit, and have a range of logical block numbers
assigned to that volume.  Correspondingly, mounted volumes can be
uniquely identified by any block number within its assigned range; by
convention, however, the first block number is used to identify a
volume.

Volumes which are inaccessible to a running Forth system are said to
be *unmounted*.  Unmounted volumes can be identified through whichever
means is most appropriate to the operator and/or the software they're
running; no standard mechanism exists for this purpose.

The placement of a volume in the Forth block space is somewhat
arbitrary, seeing as it depends largely on how the device driver
software is written.  Some device drivers will assign a range of
blocks based on which unit a volume is mounted in.  In our previous
example, the two floppy disk drives each had a fixed set of blocks
allocated to them.  If the floppy disk is taken out of the second
drive and inserted into the first, this could cause the data to appear
in a different location in the block space.  Other device drivers
might instead choose to allocate a block range based on other
algorithms.  For example, in a system with many volumes in frequent
use, maybe a first-fit approach would serve the operator better.  In
this case, the relationship between blocks occupied and the physical
unit a volume is inserted into doesn't exist.

This begs the question, how do we discover the first block of a
volume?  We need a way of determining the first block assigned to a
given unit, which requires us to have a method of naming devices and
units independently of a block number.

**** Identifying Devices and Units
No standard for Forth to date specifies how devices are to be
identified.  Since the block number of a volume must also indirectly
reference the device driver that controls it, you might think that
this is sufficient for identifying the device.  Usually, it is;
however, consider the case where we need to interact with the device
even though no volumes have been mounted through it.  For example, how
does one query the device for volume-independent information, such as
media change status, or maximum capacity of a supported unit?  Or, how
do we interact with the device to /create/ a volume in the first
place?

For this reason, devices and the units they control are in a distinct
namespace.  Devices are identified by number, starting at 0 and
increasing as required.  There's no particular significance to device
0 versus device 100, except perhaps that device 0 was detected and
initialized in the system before device 100.  Similarly, each unit
controlled by a device is also identified starting at 0 and increasing
as required.  The significance of unit 0 versus unit 1 is up to the
device they belong to; for example, a floppy disk controller might
associate unit 0 with the first attached floppy disk drive, unit 1
with the next attached disk drive, while a NAS implementation might
associate the unit number with a network address.

To facilitate the construction of human-readable unit names, though,
devices do have a standard /type/ associated with them.  While units
are always intended to be referenced by the (device id, unit id)
tuple, remembering which device is which can be aided by a helpful
summary of what the device is.  When presenting a list of volumes to
the user, the device type can be used to remind the user which device
is which.  

Going back to our previous example configuration, each device and unit
might be allocated as follows:

| Device ID | Type         | # Units | Other device-specific fields ... |
|-----------+--------------+---------+----------------------------------|
|         0 | SD Card      |       1 | ...                              |
|         1 | RAID Storage |       1 | ...                              |
|         2 | Floppy       |       2 | ...                              |

Given this configuration, if someone were to ask Forth to provide a
list of mounted volumes somehow, it's possible the result might look
something like this:

#+BEGIN_SRC
( previous output )  OK
.VOLUMES ( get list of volumes )
DEVICE   UNIT    FIRST     LAST  TYPE
     0      0        0   131071  SD Card
     1      0   131072  2228223  RAID Storage
     2      0  2228224  2229663  Floppy
     2      1  2229664  2231103  Floppy
  OK
_
#+END_SRC

*** Discovering Available Bootable Volumes
When Forth starts up, it must find out what storage devices exist and
which ones can potentially be booted from.  Using this information, it
can populate the initial boot menu, which lets the operator select how
they want to use their computer from that moment forward.

#+BEGIN_SRC
TO discover available bootable volumes DO
  Discover attached devices and volumes.
  FOR each mounted volume discovered DO
    Check for a valid boot block.
  END
END
#+END_SRC

One way to iterate through the list of detected volumes is to walk
throught a linked list of volume descriptors.  This implies that we
need a /mount list/, which maps mounted volumes and their allocated
spans of logical block numbers to physical devices somehow.

#+BEGIN_SRC
TO discover available bootable volumes DO
  Discover attached devices and volumes.
  Start with first mount list record.
  DO WHILE not nil
    Read in first block of volume.
    IF block has valid boot image match key THEN
      Create boot menu item record from boot block contents.
    END
    Step to the next volume in the mount list.
  END
END
#+END_SRC

Mount list records have, at a minimum, the following fields:

| Field       | Purpose                                                                           |
|-------------+-----------------------------------------------------------------------------------|
| next        | Link to the next record                                                           |
| start block | The first logical block number for the volume                                     |
| last block  | The last logical block number for the volume                                      |
| device      | Pointer to the device responsible for handling I/O requests to or from the volume |
| unit        | The unit in which this volume can be found                                        |

The start and last blocks allows block I/O words like ~BLOCK~ and
~BUFFER~ to direct I/O operations to the correct device driver for the
desired block.  The device and unit ID tells exactly which device and
unit should handle the I/O request.

A valid boot block is a record kept in secondary storage, and is thus
non-volatile and portable with the volume itself.  This means that a
possible boot source can be found in any attached device, and for
removable devices, can appear in different parts of the block space
after every reboot.  As a first pass, a boot block will need to have
the following information:

| Field     | Purpose                                                                                               |
|-----------+-------------------------------------------------------------------------------------------------------|
| Match key | A known constant value intended to prevent random blocks from looking like valid boot information.    |
| Name      | A human-readable name for the bootable software.  This text appears in a boot menu item.              |

More fields will be needed for both of these structures later; but
this will suffice for this level of abstraction.

*** Discovery of Storage Devices and Volumes
Since the present Kestrel-3 concept does not include any expansion
buses or auto-configuration mechanisms, and in fact only a single UART
for talking to external storage devices, it's sufficient to hard-wire
the device descriptor for handling block I/O.

However, although only a single device driver is required for this to
work, we can still end up with a number of /units/, each of which can
either be empty or be associated with an image file.  Therefore, when
initializing the device driver, we need to probe the server for how
many units it supports.  These units can have image files bound and
unbound at any time; in this respect, they will behave analogously to
floppy disk drives.

In addition, each unit with a medium inserted can potentially have
more than one partition as well.  We know that partitions can come and
go at any time as well, as anyone who has used a partitioning tool
like ~fdisk~ can attest.

#+BEGIN_SRC
TO Discover attached devices and volumes DO
  Ask emulator for its complete unit list.
  IF emulator responded THEN
    DO WHILE not at end of unit list
      Create a unit descriptor for the unit.
      IF unit is mounted THEN
        Create a mount-list descriptor.
      END
    END
    Create device descriptor of type "Storage Emulator" as device 0.
  END
END
#+END_SRC

I'm of two minds when it comes to deciding whether or not to parse out
partitions from the storage media.  On one hand, we don't wish for
erroneous Forth software to corrupt the state of filesystems belonging
to other operating systems.  On the other, supporting partitions
introduces an extra level of complexity in the system software and
supporting data structures.  Moreover, media reserved for Forth
software will generally only have one partition on them.  Thus, as a
simplification, I've decided to not bother parsing out partitions
during this step.  Thus, each inserted /medium/ is mapped to a single
/volume/ in the Forth environment.

This behavior can be changed in the future with no known impact to
software not explicitly designed to manage storage devices.

* Data Structures and Variables
** Global Data
| Description                                   | Type                                               |
|-----------------------------------------------+----------------------------------------------------|
| Flag that determines if OK prompt is visible. | BOOLEAN                                            |
| Mount list                                    | Pointer to volume descriptor                       |
| Device vector                                 | Maps device ID to device driver entry points, etc. |

** Forth USER Variables
These variables refer back to values deemed to be necessary in
previous sections of this document.  This list is not meant to be
exhaustive.

| Description            | Type                                              |
|------------------------+---------------------------------------------------|
| Exception Frame List   | Pointer to a record or NIL                        |
| ~THROW~ handler vector | Execution token of run-time semantics for ~THROW~ |

** Records and Control Blocks
Some of the material presented here will be duplicates from earlier
sections.  Where the two definitions differ, the version presented
with the specific section is to be taken to be normative.

*** Exception Handler Frame
| Field                                       | Purpose                                                                          |
|---------------------------------------------+----------------------------------------------------------------------------------|
| next                                        | Links to the next oldest exception handler; 0 if none.                           |
| throw vector                                | Preserves the throw vector that was in effect at the time the frame was created. |
| input source parameters                     | Preserves the caller's input source.                                             |
| data stack pointer                          | Preserves the caller's data stack.                                               |
| return stack pointer                        | Preserves the caller's return stack.                                             |
| floating point stack pointer (if supported) | Preserves the caller's FP stack.                                                 |

*** Device Driver
| Field       | Purpose                                                                                  |
|-------------+------------------------------------------------------------------------------------------|
| Type        | A short string describing the type of device this driver controls (e.g., "floppy disk"). |
| Units       | Device-driver specific field intended to help a driver locate and manage its units.      |
| Read block  | The Forth word to execute when it's time to read a block of data from a device unit.     |
| Write block | The Forth word to execute when it's time to write a block of data to a device unit.      |

*** Volume Descriptor
| Field  | Purpose                                                           |
|--------+-------------------------------------------------------------------|
| Next   | Link to the next volume in the mount list.                        |
| Start  | First block allocated to the volume.                              |
| Last   | Last block allocated to the volume.                               |
| Device | The ID of or pointer to the device driver managing this volume.   |
| Unit   | The ID of or pointer to the unit in which the volume is inserted. |

*** Boot Block
| Field     | Purpose                                                                                                  |
|-----------+----------------------------------------------------------------------------------------------------------|
| Match key | A known constant value intended to prevent random blocks from looking like valid boot information.       |
| Name      | A human-readable name for the bootable software.  This text would appear in the boot menu, for instance. |

* Unresolved Issues
These are design issues that either need resolution prior to further
refinement, or I know how to refine them but just haven't gotten
around to it yet.

- How to relocate ROM image into RAM?
  - Load from hunk-format image (does not require statically linked or PIC image)
  - Copy directly from ROM address space into RAM (assumes statically linked and/or PIC image)?
- "Initialize the Forth Binary Interface"
  - Devise register conventions, memory layouts, etc.
  - Sounds like an assembly language/intrinsic level function.
- "Discover the operator's console"
- "Configure the Forth bootmenu items."
- "Present menu to the operator."
- "Attempt to boot from the selected source."
- "Find valid Forth auto-start block."
- "Set input source to the operator's console."
- "Read one line of text."
- "Interpret the line of text received."
  - This one is going to be a heavy-weight item, since this gets into the internals of the dictionary, etc.
  - The above will necessarily be very tightly bound to the implementation of the compiler.
  - So, in a sense, we'll need to decide how the compiler will work before deciding how the outer interpreter is going to work.
- "Direct output to operator's console."
- "Create an exception handling frame with the current return stack pointer and system variables."
- "Restore system variables."
- Refine format of boot block format
- Create device descriptor of type "Storage Emulator" as device 0.
- Ask emulator for its complete unit list.
- Create a unit descriptor for the unit.
- Create a mount-list record for the unit.