Hi BDD
in another thread you said
which intrigued me.

Are you thinking of copying 48k chunks of data from one mapped bank to another? Or are these transfers to and from mass storage? Or to and from a main (single) data bank?

Do you envisage your interpreter living in one 48k bank, and the BASIC program in another, with the variables being found in a collection of many others?

Cheers
Ed

I haven't fully thought it out at this point (the above quote was more-or-less out-loud musing). However, here's what I've been chewing on.

POC V2's design embodies the concept of independent stacks and zero pages for each bank, allowing for true sandboxing of running processes—the kernel would trap attempts to read or write outside of the bank. This will create a suitable environment in which EhBASIC could be run, using a basic memory map somewhat like the following:


In the above, the xx in the address is the bank number.

The text of the currently-executing BASIC program would be loaded at the first page boundary immediately following the end of the interpreter proper. For example, if the interpreter occupies RAM up to $xx0FBA, the start of program text would be at $xx1000.

As far as variable storage goes, I've contemplated several possible methods. The first is to allocate two 48K banks for variable storage, one for descriptor storage—which includes storage for the numeric values associated with integer and floating point variables, and the other for storing the text associated with string variables. The cross-bank transfer function I mentioned would actually be part of the kernel and would be located in high common RAM ($00E000-$00FFFF). Cross-bank transfer would work in principle somewhat like the INDSTA and INDFET subroutines in the Commodore 128 kernel, but in a more efficient way—no translation between "bank numbers" and MMU mask patterns. I already have coded an MMU in WinCUPL that simulates on an Atmel ATF2500C CPLD, and am waiting for an opportunity to build the prototype for testing. With the 65C816's 16 bit registers, a cross-bank transfer should be less difficult to code than what was required in the C-128.

An obvious advantage to the above method is variable storage is independent of program storage and hence variable preservation is possible when chaining programs. Also, with a full 48K allocated to string text, more strings could be stored with less frequent garbage collection. With 48K available for variable descriptors, longer variable names would be practical, and there would be room for a lexically sorted variable name index, which would help speed up the location of a variable when many have been created.

A corollary advantage is all RAM above the end of BASIC program text is uncommitted, which means, in the case of the 65C816, the stack can grow downward from the top of the bank, giving plenty of room for FOR-NEXT and GOSUB pushes, etc., as well as the usual stack stuff that occurs in a running program.

The principle downside is the need for cross-bank transfers, which will affect execution speed, since the BASIC interpreter itself could not directly manipulate descriptor or string storage space. Each time access to the variables was required, the cross-bank transfer functions would be required in order to get, put or compare bytes. However, there may be a way to mitigate this to some extent, and that would be for the interpreter, at start-up, to copy code into the variable descriptor bank that could be locally executed to search the descriptor table. I'd have to allocate RAM in that bank for a stack and zero page as well, but those structures could be small (especially the stack, which only has to be one page).

Another way to handle the variable storage would be to use the "traditional" method of allocating space at the end of the BASIC program text, a la Microsoft BASIC and EhBASIC, i.e., between the end of BASIC text and the bottom of the MPU stack. It's actually fairly easy to do, and requires no cross-bank transferring. As all activity occurs within one bank, data movement can be implemented via the 65C816's rapid-acting MVN and MVP instructions—which I use in my M/L monitor to handle the T (memory copy) command.

The downside to setting up variable storage at the end of the program is the same as in the Commodore 64: big programs result in small variable storage space and more frequent garbage collection. Also, preserving variables when chaining programs becomes a problem. If a small program runs a large one, the large one will step on part of the variable descriptor area that was set up by the earlier (smaller) program. The solution to that would be to dynamically relocate the descriptor space to make room for the larger program (or move it downward if a smaller program is run). However, if a lot of strings have been created, upward relocation may cause a collision between the top of descriptor storage and the bottom of string storage.

Yet another method would be a hybrid of the two. Store variable descriptors in the same bank as the BASIC program but string text in a different bank. Cross-bank transfers would be required only to access string text, not variable descriptors.

In all cases, stack growth must be constrained to avoid collision with data structures lying above the end of BASIC text or with the BASIC text itself.

As you can see, it's no simple matter and until I get around to building the next-gen POC and writing a practical operating system for it, it's all conjecture.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

Thanks for the explanation! Any reason not to allow 2 or even 3 banks to be in use by each process? (Perhaps you are intent on maximising the number of available process slots? But 80 processes is quite a healthy number.) It would allow you to avoid the copying.

Cheers
Ed

Well, let's suppose a running process of any type needs to run a different program on disk in order to complete its mission. For example:

which would print a directory of all files ending in .c. In order for that to work, both ls and lp have to simultaneously run in separate workspace and communicate with each other through a pipeline set up through the kernel. So right there, two banks are needed. Also, the command interpreter shell has to be running, which is a third bank.

Now suppose I type something like:

The above lists files ending in .c, sorts them according to the file size, saves a copy of the generated list to the file sizelist, excludes all filenames that don't have the word basic in them and then generates a printed list. That's five concurrently running processes started by a single command, each requiring a bank in which to run. Plus the shell, of course, is running in its own bank.

Now, in a live system, there's quite a bit of background stuff that gets started, each requiring a bank. The kernel requires a bank, at least one bank is required for I/O buffers, etc. Adding to the confusion, the system might not have a full 16 MB of RAM, so there won't necessarily be 256 banks. The SRAM decoding logic is such that RAM can be as small as 4 MB, which translates into 64 banks total. SRAM isn't real cheap, so I might not build the unit with a full complement of RAM.

So being extravagant with RAM for BASIC variable storage could quickly result in an "out of memory" or "can't fork" error (the latter if no bank is available in which to run a program).

Something to consider in passing is how important large variable storage space might be. In business BASIC implementations, huge variable storage space is not the norm, since the biggest consumers of space, string variables, tend to be scalar, not indexed, as file indexing is used for the latter purpose. Were I to figure out how to implement file indexing, I'd not go to the trouble to set up huge variable storage space.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

Hi BDD
indeed, pipes are very handy. Note that some OSes will implement them using temporary files rather than communicating processes.

But, I realise that I went off at a tangent there. Your picture for BASIC has a single BASIC process communicating with two other processes which hold the extended data. (This seems almost like a RAM disk: the storage is in RAM, but accessible only through the OS.) I wondered if you could allow all three banks to be accessible by a single process, and so avoid the kernel's involvement (you could use the DBR or use 24-bit pointers.) I then went two far and supposed that every process might need access to three banks - but this isn't necessary. Only some processes might need three banks. So the idea that the maximum number of supported processes just got divided by three was a piece of fiction on my part. Oops.

Cheers
Ed

In most UNIX-like OSes, one can create a named pipe, which is a FIFO on disk. I use them on my office UNIX box to implement a custom network line printer daemon. I could also use the kernel's pipe mechanism, which is an abstraction in RAM. The problem with doing so, aside from RAM consumption, is that it has to be set up and torn down with each print job. So a named pipe is more efficient.


Clarification: a bank wouldn't necessarily be home to a running process. There would be a mechanism in the kernel analogous to the shmop set of UNIX kernel calls that would allow one process to request a block of memory outside of its own bank. The kernel would return the bank number of the first available bank, and then the process could perform (indirect) read and write operations on that bank, with guaranteed exclusivity. The requesting process could, if needed, designate the bank as shared memory, thus giving other processes the right to access the same memory if the proper "credentials" were made available to the kernel when access was requested.

In the case of BASIC, let's suppose I implement the hybrid variable storage model. Variable descriptors would be stored above the end of BASIC text and string text would be stored in a separate bank, which would be requested from the kernel when BASIC was initialized. The string bank would not be shared memory, so only the requesting process would have access. In this case, each running instance of BASIC would consume two banks: the one in which the interpreter itself is running and the one in which strings are stored. Only the bank with the interpreter would be a running process and under the control of the kernel's scheduler.

Incidentally, in this kernel that is slowly taking shape in my head, pipes could be implemented in a block of common RAM that spans from $00C000-$00CFFF. I envision using a 64 byte circular buffer for each pipe, with simple indexing, a write index for the input end and a read index for the output end. Assuming the entire common RAM space was used for pipes (which may not be the case), up to 64 concurrent pipes would be possible.

Yet another piping alternative would be to set aside some blind disk space for the purpose. As SCSI I/O performance will be limited by the performance of the 65C816, not the disk subsystem, such a move would be effectively like using RAM. Choices, choices...

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

Something I haven't grasped yet: how do you prevent processes from accessing outside the bank you expect them to? Perhaps you are running in 6502 mode, so only the kernel has access to the bank structure?

I'm using the 65C816 in native mode, although memory protection could be implemented in emulation mode.

The key to it is in using the 65C816's /ABORT hardware interrupt. WDC's original intent for this signal was to allow a virtual memory system to be set up (e.g., detecting and managing page faults). However, it can be used to detect just about any kind of a memory fault if suitable logic is provisioned.

Generally speaking, if /ABORT is asserted prior to Ø2 going high during a valid memory cycle (see below), the current instruction is completed but no changes are made to the registers or memory, e.g., STA ACIAFLAG will not actually change the content of ACIAFLAG. Upon completion of the current instruction, the /ABORT interrupt is then handled like any other hardware interrupt, but jumps through a specific vector. Code pointed to by that vector can then do whatever is required to deal with the cause of the /ABORT interrupt. Typically, the abort handler would cause an execution fault in the errant process, just as a UNIX system will cause a segfault or similar if a program tries to go where it shouldn't. The process would be terminated and control returned to the parent process, along with an error indication to tell the parent what happened.

Policing memory accesses is actually fairly simple with the memory arrangement I envision, and should be possible in a 22V10 type GAL if fast enough (10ns or faster). Alternatively, a high density CPLD could be used, thus putting all of the glue logic in one package. In the POC unit, all addresses from $C000 onward are not banked, and hence have an effective bank number of $00. $00C000 upward constains RAM, ROM and I/O, which can be mapped in various ways (e.g., RAM at $00C000, I/O at $00D000 and ROM at $00E000). Hence the RAM boundaries for running processes (including the kernel) are $xx0000 to $xxBFFF, where xx is the bank ($00-$FF). By definition, $00C000 onward is a system area and should not be touched by anything except the kernel. In considering this arrangement, it should be understood that any address that asserts A14 and A15 is accessing the system area. Hence detection of an attempt to touch anything in the system area can be made by ANDing A14 and A15. In order to allow the kernel to access the system area, it is run in bank $00 and the policing logic grants an exception to that bank. Therefore, in pseudo-code, the logic is effectively:


where & is logical AND, | is logical OR and ! is logical NOT. VDA and VPA qualify '816 memory cycles, so the above logic is not affected by address bus transitions during "dead" MPU cycles. Simply stated, /ABORT will be pulled low if the address is $C000 or higher, the bank is not $00 and the MPU is in a valid memory cycle. There's a bit more to it than that (e.g., allowing the MPU to read the hardware vectors when an interrupt occurs), but the above is the essence.

A note about bank detection. The MMU logic actually emits a 3-of-8 output that represents the A16-A23 component of the physical RAM address. Hence if the sum-of-bits of that output is zero, bank $00 is mapped in. The 3-of-8 bits select a portion of the available SRAM in a way that gives the MPU the impression that the $0000-$BFFF address range is always in the MPU's bank $00. Hence the independent stack and zero page concept works as expected.

There is one potential booby trap, which is more theoretical than actual, and that is what happens if a user process changes the stack pointer to an address higher than $BFFF. The next stack operation would attempt to read or write in the system area and hence would trigger an abort. However, as part of reacting to /ABORT, the MPU will push stuff to the stack. The problem, of course, is the stack is in the system area, so the /ABORT-instigated push will trigger another /ABORT, eventually causing the MPU to auger in. In a program like BASIC, where the user normally would not be allowed to access the MPU registers, it's theoretical. In an assembly language program, it's possible.

There really is no way to prevent the relocation of the stack into to the system area without examining each opcode fetch memory cycle to see if a TCS or TXS instruction is about to be executed, and if so, somehow determining what address is being stored in the stack pointer. The problem, as eluded in another series of posts, is there are no privileged instructions in the '816, and of course, no way to look backward and see what address was loaded into .A or .X prior to executing the TCS or TXS instruction.

/ABORT on the '816 is a bit tricky with its timing requirements, but manageable in a fast GAL or CPLD, even at 20 MHz. Generally speaking, when the '816 presents a valid address it will do so midway through Ø2 low and assert VDA and/or VPA to indicate the address is valid. As /ABORT must be asserted before Ø2 goes high in order to give the MPU time to react and not change anything as the aborted instruction completes, it is logical (!) to assert /ABORT as soon as possible after the address bus goes valid. Once /ABORT has been asserted it must stay so through the subsequent Ø2 high and then be deasserted on the fall of Ø2. If the latter requirement is not met, the /ABORT interrupt itself may be aborted, either causing the MPU to erroneously change something that it should not or augering in.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

Ah yes, it's ringing a bell. So userspace always thinks it's in bank0, so page zero and the stack always work in the local bank. And this scuppers any possibility of direct access to 'foreign' banks, unless your (fast) abort logic can look up some kind of permission table, which would be asking a lot.

Cheers
Ed

Correct, although it's the MPU that thinks it's always in bank 0. The user process itself has no concept of banks, as it is the MMU that maps the user's virtual address space to physical RAM..


Correct. That can't be allowed to happen without the kernel working on behalf of the user process. Otherwise, one process could scribble on another's space, or worse yet, on the kernel. If a user process were to attempt to change the memory map it would be accessing system space (the MMU shows up at $00DF00), which would trigger an exception and assert /ABORT.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

Just make sure you have block transfer routines to write to and read from the buffer. In my own kernel I have only byte-transfer which slows it down a loooot. Block transfer is planned in the next release. Don't know when I get to that though...

André

There will be cross-bank transfer functions high in common RAM, so it could be done a byte at a time or en masse using MVN and MVP. However...

This iteration of POC will have SCSI I/O (synchronous SCSI-2) and, at least according to my calculations, the SCSI bus throughput will be nearly twice as fast as the 65C816 can physically move bytes from one place to another at 20 MHz. Since SCSI I/O will be as fast as working in core, I may use blind space on the boot disk to implement pipes like you'd use on a real UNIX system with the pipe() kernel call. Each kernel pipe would occupy one disk block, so I'd have an array of 512 byte FIFOs. Even 100 of these would barely make a scratch in the available disk storage (I have some old but functional 4 GB Seagates with which to test). I'd also implement named pipes since they can be useful in some tasks.

First I have to finish up with the design work and get a prototype built. I'm using an NCR 53C94 SCSI ASIC and it has a kind of hinky bus interface (apparently optimized for use with Motorola 68K MPUs).

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

Just a thought on this.

If A16 were brought in conditionally on a mode bit, then bank 1 would be allowable - (aligned) pairs of physical banks would be mapped to bank 0 and 1 and could act as a single user processs. Similarly, make A17 conditional and you get (aligned) sets of four banks mapped to 00 to 03. It's not arbitrary mappings, but it does allow for double or quad-sized processes which can then use the usual 816 mechanisms to access code or data across the banks.

Of course the mode bit or bits are only accessible to the kernel. And of course if you're prepared to do some packing you can allow for processes to be of different types - most perhaps are single-bank sized.

Cheers
Ed

I've temporarily put this project on the back burner. I was able to concoct a way to attach a SCSI host adapter to my POC V1 unit so I can develop driver code on hardware that already works. With POC V2, I'd be introducing new features (CPLD glue logic) that could make it more difficult to get working SCSI.

The host adapter will piggy-back on top of the POC board and plug into the Dallas watchdog's socket, with the watchdog itself being installed on the host adapter. A minor patch to the POC board is all that is required to bring needed signals to the host adapter, using two pin positions on the socket not used by the watchdog. I'll post more details in the POC V1 thread.
----------
Added a link to the host adapter posts.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

Remind me to send you the schematic and things for my Pinball Mind. I revamped to page bank both RAM and ROM in a fairly simple method. see how this would work with yours:

0000-5fff 24K fixed RAM (tis 32k, but we only address 24K)
6000-7fff 8k page banked area, 128 pages RAM 128 pages ROM
8000-80ff 256 byte IO
8100-FFFF 32k (-256 byte) fixed ROM

The page bank is a simple byte, 00-7f is ram, 80-ff = rom. A mirror byte would let you read the present page. am also trying to figure out a small hardware gig to access the 8000-80ff in the main ROM as an ID table read. (the logic would be handled in a CPLD)

_________________
"My biggest dream in life? Building black plywood Habitrails"