Need some advice on threading on a Z80

[brucehoult]

I don't know why it should be impossible. Adding external MMU was common on all such CPUs, even if only for bank switching (but it's the same thing). Preventing access to some banks is not hard. The only hard thing is being able to recover from an illegal access, make it legal, and continue the program. Some early 68000 machines with MMU had two chips with one running a couple of clock cycles behind the other so it could be halted before hitting the exception the first CPU hit.

[RoGeorge]

If you're envisioning some kind of memory protection, you can watch this:
video
(although the title is a bit "catchy", you may find a couple ideas in this.)

That video was discussed 2 years ago in another topic, it's a clickbait, and no Z80 feature discovery.

My conclusion from the other thread, after watching the video back in 2022:

Not a clickbait title, it's a lying title.

To spare others' time, no Z80 secret feature was discovered.  He wants to emulate protected mode in software, after adding some external hardware, then starts to fantasize about generic advantages of protected mode as if Z80 would have such a mode, except Z80 doesn't have any hidden protected mode feature.

[bson]

You always know when next to interrupt for a context switch; when you switch to a thread you look at the runlist, and if there's anything else that wants to run at the same priority you set a timer for your round-robin timeshare quantum, whatever that is.  100ms should be fine.  Anything else, like a button press, will interrupt the processor, and in the ISR you simply check to see if any thread is waiting for this, and if so flag it as runnable.  If it's higher priority than the currently running thread you switch to it (switch to its stack so that on exit from the ISR you return to its saved state); if it's lower you let the current one run, if it's the same you can use a number of scheduling approaches, but it's common to switch to it, temporarily slightly bump its priority by 1, and set a shortened quantum for the next context switch so it can process the event, then when it has run out of its quantum you drop it back down to its actual priority and let it compete like other threads.  Or you can simply switch to it.  Or you can do nothing, requiring a strict priority order where if two threads have the same priority they can only cooperatively context switch between themselves.  All scheduling can be done by setting a timer to a known quantum and allow ISRs to context switch, no "heartbeat" needed.  For clock you keep a timestamp in memory and run another timer; the current timestamp is the value in memory plus the timer; when the timer rolls over you update the value in memory.

[JamesIsAwkward]

Do you think a simple push/pop would keep track of thread data or should I dedicate some static kernel/OS RAM space to a certain number of threads to store this data?

[tggzzz]

Do you think a simple push/pop would keep track of thread data or should I dedicate some static kernel/OS RAM space to a certain number of threads to store this data?

Linked list of structures containing the thread data, principally the location of a thread's stack pointer.

Traversing linked lists is much more of a pain in the Z80 than it is in the 6800 While the IX and IY registers look useful, doing anything with them requires more instructions than is "reasonable". In practice using the 8080 registers is just as good, if not better (source: memory from >40 years ago )

[brucehoult]

Do you think a simple push/pop would keep track of thread data or should I dedicate some static kernel/OS RAM space to a certain number of threads to store this data?

Push/pop is for sure the fastest way to save the 4 main register pairs (11 cycles to push a pair, 10 to pop) and IX/IY (15 each to push, 14 to pop) compared to ld instructions.

The question is: do you push registers onto the thread's own stack (risks stack overflow), or to a dedicated area after first saving SP somewhere (which has essentially got to be a global variable, at least initially) and then setting it to point to the thread's register save area, however you find that (global array of threads, linked list ...)

[bson]

You have to reserve space for the saved registers somewhere... might as well be on the thread stack.  It's usually more straightforward as it can be done without clobbering registers.  If you're going to point SP somewhere you need to save it first, which means you need to load it, which means you clobber it.  So you'd have to push AF, HL and maybe more just to set up SP to point to the storage area, in which case you might as well just push the rest on the stack at the same time.

[JamesIsAwkward]

Okay you guys have a lot of good points.


I admit I'm out of my depth here so let me ask this to clarify...


Are you saying it would likely be easier/better to have a thread table in kernel space, and use that to save the thread data? I have a simple mocked up thread structure here, does this seem like the right path?

Code: [Select]

; Global thread memory map:
; 2 bytes for current running thread
; 1 byte for number of active threads - likely limited to 4 or 8
; 2 bytes to store temp SP value

; local memory structure per thread:
;   2 bytes for current thread struct address
;   1 byte for IO classification - for future use if I ever move to a priority based threading system, then I could set slow I/O to low priority and etc
;   1 byte for thread status - active or suspended, so thread handler can skip over the thread if it needs to
;   12 bytes for registers - dump of all thread registers
;   2 bytes for SP
;   2 bytes for PC -        possible to save with some trickery
;   10 bytes or so for future use
;   2 bytes for pointer to next thread


OR would it just be better to have a hybrid scenario. Use the thread table but don't push the registers there. I could push them to the stack and so long as I set the SP back to the correct place I could pop them all back out. Actually after thinking this out I think this is probably the better way.



What do you guys think?

Thanks for all of the advice, you all have been incredibly helpful. This has been a really fun project to work on!

[floobydust]

I don't see the Z80 alternate registers mentioned in the thread. In my day with the Z80 used the prime register set for fast context swaps with EX and EXX op-codes. Instead of time pushing registers on/off the stack.

[brucehoult]

Pushing the registers on to the same thread's stack is certainly the least code and the fastest. But sometimes stacks get full. How are you going to handle (prevent!) stack overflow during register saving?

Going the other way you'll need more than just a temporary (absolute address) to store the SP. I think you're going to need at least HL there too? Or maybe you have a global pointing directly to the current thread's register-save area. So you can start:

Code: [Select]

ld (spTmp),sp
ld sp,(currThreadRegSave)
push af
push bc
push de
push hl
push ix
push iy
ld hl,(spTmp)
push hl

And then at that point you have all registers free to figure out what thread to run next, but you don't have a stack. I guess if nothing else you need to make sure interrupts stay disabled.

I've forgotten (if you mentioned it) what kind of threading you're doing: cooperative, or interrupt-driven?

If the latter then of course PC and PSW are already on the current stack. And you do have to preserve everything else.

If it's cooperative threading where task switch looks like a function call then depending on what ABI you use for function calls you might not need to save and restore many registers at all -- or even none. I seem to recall a lot of compilers in the late 70s/early 80s didn't preserve the non-8080 IX and IY registers, even after the 8080 was dead and forgotten.

ISTR z80 function calls did mostly preserve registers. While 6502 code generally treated the registers (all 3 bytes of them!) as volatile except to whatever extent they were used to pass arguments or function results.

[brucehoult]

I don't see the Z80 alternate registers mentioned in the thread. In my day with the Z80 used the prime register set for fast context swaps with EX and EXX op-codes. Instead of time pushing registers on/off the stack.

That doesn't scale to more than two threads. You could let the OS/scheduler use the alternate register set, but when it comes time to switch user threads you have no choice but to switch to the main registers and save and restore them.

Potentially you could keep the address of current thread's register save area in an alternate register pair, and stash the SP in another temporarily.  But it's tricky. You can only move hl to sp (or ix, iy, but they don't have shadow registers), and you can't move sp to any registers -- you can only add (or subtract) it to hl. Which means you have to zero hl first, and so you can't be storing the new sp value there.

So you end up with a shuffle like:

Code: [Select]

exx
ld hl,0x0000
add hl,sp
ld b,h
ld c,l
ld h,d
ld l,e
ld sp,hl
exx
[code]

... instead of the previously mentioned ...

[code]
ld (spTmp),sp
ld sp,(currThreadRegSave)

.. which is 11 bytes of code vs 6, and I think more cycles too .. 51 vs 40?

[tggzzz]

Pushing the registers on to the same thread's stack is certainly the least code and the fastest. But sometimes stacks get full. How are you going to handle (prevent!) stack overflow during register saving?

You just take the stack size required for each thread's internal processing (varies according to each thread's call graph, fun when recursion is involved ), and add the constant space required by the RTOS (constant for all tasks, defined by the RTOS creator, therefore easy).

Whether you have enough RAM for all the task stacks is a separate issue.

Are you saying it would likely be easier/better to have a thread table in kernel space, and use that to save the thread data?

In a Z80, there is no "kernel space" per se. There is just a single uniform unprotected address space.

Keep the thread-specific data (i.e. registers) on the relevant thread's stack. Keep the kernel-specific data somewhere else.

The kernel only needs to keep a linked-list of nodes, each node representing one thread. The node only contains a pointer to the stack pointer for its thread. The kernel chases along the linked list until it finds the relevant thread/node, then follows the pointer to the stack, pops the registers off the stack, and resumes that thread.

[cruff]

Keep the thread-specific data (i.e. registers) on the relevant thread's stack. Keep the kernel-specific data somewhere else.

Allocate the thread structure at the top of the thread's stack area (assuming the stack grows down) and set the thread's stack pointer just below that structure when starting it. That way you know you always have the required storage to switch threads. Of course you can't protect it from under flow by the thread, but that won't happen in properly written code.

[JamesIsAwkward]

In a Z80, there is no "kernel space" per se. There is just a single uniform unprotected address space.

Yeah, I should have put "kernel space" in quotes there too. What I meant by that is literally kernel space in RAM.

Keep the thread-specific data (i.e. registers) on the relevant thread's stack. Keep the kernel-specific data somewhere else.

Yeah this is my goal! I'm writing the kernel code in a unix-like way that will abstract the hardware and stuff away from user-space programs. Syscalls and the like.
I think doing that will minimize me ever entering kernel space unintentionally. Granted I am very new at this and so I'm still learning the concepts haha

Allocate the thread structure at the top of the thread's stack area (assuming the stack grows down)

Okay I'm trying to wrap my head around this so bare with me 
When you say thread stack do you mean to have a separate thread stack allocated in the kernel RAM area? Or are you just calling the thread's SP and register data that is saved somewhere in the true stack a "thread stack"?

and set the thread's stack pointer just below that structure when starting it. That way you know you always have the required storage to switch threads. Of course you can't protect it from under flow by the thread, but that won't happen in properly written code.

I understand what you are saying and this is a great idea, but as far as having RAM space for additional threads when they are created I think I will just do a hard coded number of threads for now. I can worry about a dynamic number later where RAM size will be an issue. I don't really see needing to run more than 8 threads... but I'll get back to you when I add networking and other I/O lol


I finally have my hardware back up and running again, I moved earlier this year and my breadboard needed some TLC to get it all in working order. I'm going to do some experiments with 2 simple threads today and see if I can put yalls advice into action!

[bson]

Pushing the registers on to the same thread's stack is certainly the least code and the fastest. But sometimes stacks get full. How are you going to handle (prevent!) stack overflow during register saving?

You still have to allocate the memory somewhere.  Might as well add it to the stack size.

[bson]

Allocate the thread structure at the top of the thread's stack area (assuming the stack grows down)

Okay I'm trying to wrap my head around this so bare with me 
When you say thread stack do you mean to have a separate thread stack allocated in the kernel RAM area? Or are you just calling the thread's SP and register data that is saved somewhere in the true stack a "thread stack"?

Not sure what you're talking about.  Each thread has a stack and when you context switch you change to the running thread's stack.  There is no such thing as "the true stack".  It's also common to have a separate interrupt stack, so even though an interrupt may push context onto the running thread's stack, whenever non-trivial processing needs to occur a switch is made to a dedicated interrupt stack.  This is so each thread doesn't have to provision for the overhead of interrupt processing.  On a Z80 this may not matter, but "real" systems will do things like drain ethernet buffers/respond to drain events (DMA completion) and do real work at lowered interrupt priority levels (IPL) as such systems need interrupt nesting.  Some systems also have high-priority kernel threads for this, so instead of switching to an interrupt stack they switch to a kernel thread, which runs at high enough priority that only a higher-priority kernel thread (for a higher priority hardware event) can preempt them.  This is preferable on SMP and NUMA systems with multiple sockets, especially in the latter where you want the socket close to the hardware, so you run a kernel interrupt service thread with a socket affinity.  On SMP systems you can't just block out interrupts and user space code while servicing interrupts, and a thread model allows for locking and such.  But, fundamentally, a thread is pretty much a stack.

[JamesIsAwkward]

Not sure what you're talking about.

Hey don't worry, I don't either! 

Sorry let me try to articulate better, I'm doing a poor job!
"True stack" was a poor description of what I meant.

By "true stack" I was trying to describe the stack as a whole, not just the thread stacks, but the actual z80 stack itself.
But I got myself confused on that last post so you can ignore it lol. I was getting worried about the different thread stacks overwriting each other if one of them extends too far or something.

But it is obvious that problem is solved by just defining the stack space for each thread in the table. It also wouldn't be very difficult to add a dynamic stack size when calling for a new thread and supply the desired size.



Sorry I feel kinda dumb here haha, so yeah just disregard that last post!

[tggzzz]

Not sure what you're talking about.

Hey don't worry, I don't either! 

Sorry let me try to articulate better, I'm doing a poor job!
"True stack" was a poor description of what I meant.

By "true stack" I was trying to describe the stack as a whole, not just the thread stacks, but the actual z80 stack itself.

At any instant, one thread is executing and there is one SP pointing to the location of that thread's stack.
At a different instant there may be a different thread executing, and therefore the same SP pointing to the different location of the different thread's stack.

When threadA relinquishes control, your scheduler is responsible for

• saving the registers (including PC) at that instant on the stack (i.e. in this case threadA's stack)
• saving threadA's SP in some structure which includes whether threadA is runnable. Typically all those structures are stored in an array or linked list within the scheduler.
• determining which thread to run next (e.g. thread N), based on the information in each of those structures
• loading threadN's SP from the structure
• loading threadN's registers from the stack (i.e. in this case threadN's stack)
• setting the PC to be the value loaded from the stack

For the avoidance of doubt, that cannot be done in C, since C has no concept of an SP. You have to use a small amount of machine code to twiddle SP.

[brucehoult]

For the avoidance of doubt, that cannot be done in C, since C has no concept of an SP. You have to use a small amount of machine code to twiddle SP.

Having done this a few times over the years, I can say that you can SWITCH between threads in pure C, using setjmp & longjmp. The only thing you can't do in C is initially set up the PC and SP for a new thread.

Not that it matters -- no one should be afraid of writing a little assembly language.

When we ported our embedded software to Windows I had to write my own setjmp & longjump anyway, as Microsoft's ones did some extra SEH bollocks which made them not work for either switching threads or exception handling the way we used them.

[cruff]

When you say thread stack do you mean to have a separate thread stack allocated in the kernel RAM area? Or are you just calling the thread's SP and register data that is saved somewhere in the true stack a "thread stack"?

In a system with address space protection you can save it in the kernel writable area, although it doesn't really matter as the time period during which you have to save the registers that thread is not executing and thus cannot modify that storage area. As others have said you have to allocate the space for them somewhere.

Although for the thread specific metadata you obviously wouldn't want to allocate that in the thread's address space as that data is used by the OS to perform scheduling decisions and unexpected alterations can lead to crashes or security problems (think gaining privileged access or altering the thread's scheduling priority).

However, since you are on a Z80 you likely don't have protected memory so those conceptual distinctions, while being good for documentation and reasoning about data use, it could be susceptible to wild pointer access problems, etc.

One example of hardware managed protected address space is on the Harris HD6120 PDP-8 on a chip where there is an address space known as "control panel memory" which can be used to emulate the old front panel lights and switches of older PDP-8 computers. That is not accessible by the normal code you'd think of as being in control over a computer like that. There is support for trap entry into control panel mode that switches state, which is similar to the kernel/user mode support on many current CPUs.

[cruff]

Also push the address of your OS's thread exit function at the top of the thread's stack when creating it, then if the thread returns from the entry point routine, your OS will automatically gain control and perform cleanup.

[tggzzz]

For the avoidance of doubt, that cannot be done in C, since C has no concept of an SP. You have to use a small amount of machine code to twiddle SP.

Having done this a few times over the years, I can say that you can SWITCH between threads in pure C, using setjmp & longjmp. The only thing you can't do in C is initially set up the PC and SP for a new thread.

Does that require any restrictions on how C is used, e.g. not yield()ing within a function invoked by a thread?

I've managed to avoid using evade setjump and longjump. Anytime they might have been beneficial I've either used a different language/environment, or preferred to code sufficiently defensively (i.e. visibly, understandably  ) that they weren't necessary.

Not that it matters -- no one should be afraid of writing a little assembly language.

I'll take it slightly further: everybody should expect to have to look at the machine code output, to verify the machine will do what they think they've told it to do.

When we ported our embedded software to Windows I had to write my own setjmp & longjump anyway, as Microsoft's ones did some extra SEH bollocks which made them not work for either switching threads or exception handling the way we used them.

"Embedded" and "Windows": two concepts I've managed to completely compartmentalise As far as I'm concerned, they are orthogonal concepts.

That was one of the good things about DOS: it was a program loader that your program could completely ignore

[brucehoult]

For the avoidance of doubt, that cannot be done in C, since C has no concept of an SP. You have to use a small amount of machine code to twiddle SP.

Having done this a few times over the years, I can say that you can SWITCH between threads in pure C, using setjmp & longjmp. The only thing you can't do in C is initially set up the PC and SP for a new thread.

Does that require any restrictions on how C is used, e.g. not yield()ing within a function invoked by a thread?

Absolutely not!

That's the whole point of using setjmp/longjmp. They preserve PC, SP, and all callee-save registers.

If you can only yield() from the main function of a thread then that's just a matter of structuring the main function as a switch (nextState) { } and yield() is just setting nextState and returning from the main function.

setjmp/longjmp gives proper yield()

When we ported our embedded software to Windows I had to write my own setjmp & longjmp anyway, as Microsoft's ones did some extra SEH bollocks which made them not work for either switching threads or exception handling the way we used them.

"Embedded" and "Windows": two concepts I've managed to completely compartmentalise As far as I'm concerned, they are orthogonal concepts.

It's always beneficial to be able to unit test embedded software on a desktop PC, if not run the entire program.

It worked on Mac and Linux using the standard libc setjmp & longjmp. Only Windows needed custom ones.

[tggzzz]

When we ported our embedded software to Windows I had to write my own setjmp & longjmp anyway, as Microsoft's ones did some extra SEH bollocks which made them not work for either switching threads or exception handling the way we used them.

"Embedded" and "Windows": two concepts I've managed to completely compartmentalise As far as I'm concerned, they are orthogonal concepts.

It's always beneficial to be able to unit test embedded software on a desktop PC, if not run the entire program.

It worked on Mac and Linux using the standard libc setjmp & longjmp. Only Windows needed custom ones.

Agreed. Not difficult either, provided you give a little thought to structuring your code so it includes an informal HAL layer

I first did it with a MicroSoft operating system, running on a PDP-11. Happy daze.

[JamesIsAwkward]

Alright I have it figured out!

It took me a ton of experimentation to get it to work right, and with only 2 threads, ha!
Most of my bugs were just bad memory management. I had to brush up on Z80 endianness and what not.

@tggzzz pretty much summed up the process perfectly.
I created a thread handler that fires off when my external interrupt goes active, this pushes the current thread's registers to its stack, then saves the thread's stack pointer value inside of the thread's data structure in memory. Next it grabs the next thread's data structure, grabs the next thread's stack pointer value, changes the SP to the new thread's SP value, POP's the registers and then RETs.  This pushes the new thread's program counter back to the value it was when running previously.


I created a very basic NEW_THREAD routine that helped stage a couple of test routines (routine0 prints 0 to terminal, and routine1 prints 1). It set the areas of memory where the PC's should be to their routine start addresses, then set each routine's SP 16 bytes back in order to account for the POPs from the thread handler.


It's very rough but it is a proof of concept.

Improvements to be made:

• Remove hard coded 2 thread system, move to dynamic system that uses flags on the thread structure to determine status and act from there
• Create routine for closing threads and freeing up their memory
• Create a way for threads to request more or less stack space when first init'd, right now it's a static amount. This would require my routines or "executables" to follow some kind of standard and have headers similar to ELF... and would also increase the complexity of the routines that handle finding each thread's stack. I'd have to end up using linked lists or something
• MAYBE: Allow some threads to have higher priority (I/O limited threads can be checked less often and core services will be ran more etc)

Threading will be integral to my overall design because I want to create a rudimentary GUI desktop in the future, which is pretty much impossible without threading.

Now that I kind of have my head wrapped around how this works I think I'm going to start actually designing my "kernel".
Maybe that discussion would make for another fun thread?