5 ms·

Show HN: Preemptive Multitasking on an AVR Microcontroller

63 points by jwmhjwmh 6y ago

andrewstuart 6y ago
From the github: >> I do not see a practical use for this library, but I think it's interesting. +100 This is the essence of hacking.
- Lerc 6y ago
  indeed. Yet I might have a use for this library in a project I have no practical use for.
magicalhippo 6y ago
Ahhh this reminded me of when I as a teen saved up and bought "Assembly Language Master Class"[1], the only assembly-related book I could find in my local bookstore that didn't look like a complete intro-book. I had learned a bit of asm from some articles I had downloaded from various BBSes, and wanted to take the next step. After reading through it a few times I got the idea to try to write a pre-emptive scheduler myself. This was way before the internet so I just knew the concept existed, and the book didn't have anything like that in it per se. So I spent a day or two figuring out by my self how to preserve and restore the registers and flags without disturbing them. I wrote it in Turbo Pascal, using the inline asm for the task switcher. Each "process" was just a procedure (subroutine) that ran in a loop until a global bool was set. I decided to hook the RTC[2] for switching tasks, but nothing more. So each time-slice was fixed at 18.2ms which didn't make things terribly interactive. Never got further, it was more of a "can I do it" type project, but boy that feeling when I saw my three "processes" running one after another without cooperation... priceless! [1]: https://www.amazon.com/Assembly-Language-Master-Class-Press/dp/1874416346 https://www.amazon.com/Assembly-Language-Master-Class-Press/... [2]: https://en.wikipedia.org/wiki/Interrupt_request_%28PC_architecture%29#Slave_PIC https://en.wikipedia.org/wiki/Interrupt_request_%28PC_archit...
- magicalhippo 6y ago
  Ah found the code. Not pasting the whole thing, but here's the relevant bits of the task switching. Keep in mind this was me with a few years of programming in general under my belt so yeah, still bit of a noob. type task_type = record stack: array[0..1023] of byte; eax, ebx, ecx, edx, esi, edi, ebp, esp, eip, flags: longint; es, ds, cs, ss, fs, gs: word; end; task_type_ptr = ^task_type; procedure MTaskHandler; assembler; asm cli { save vital information } { eax, ebx, ecx, edx, esi, edi, ebp, esp, eip, dflags: longint; es, ds, cs, ss, fs, gs: word; } db $66; mov word ptr [@@tmp], ax db $66; mov word ptr [@@tmp+4], bx db $66; mov word ptr [@@tmp+8], cx db $66; mov word ptr [@@tmp+12], dx db $66; mov word ptr [@@tmp+16], si db $66; mov word ptr [@@tmp+20], di { get ip } db $66; xor ax, ax pop ax { pop the ip from stack } db $66; mov word ptr [@@tmp+32], ax { ip } { get cs } pop dx { get flags } db $66; pushf db $66; pop ax pop ax db $66; mov word ptr [@@tmp+36], ax { dflags } { save bp and sp after the modification } db $66; mov word ptr [@@tmp+24], bp db $66; mov word ptr [@@tmp+28], sp mov word ptr [@@tmp+40], es mov word ptr [@@tmp+42], ds mov word ptr [@@tmp+44], dx { cs } mov word ptr [@@tmp+46], ss { setup own stack } db $66; mov word ptr [@@bp], bp db $66; mov word ptr [@@sp], sp mov word ptr [@@ss], ss db $66; xor bp, bp db $66; xor sp, sp mov sp, offset Stack + 1022 mov bp, sp mov ax, seg Stack mov ss, ax { restore data segment } mov ax, seg @data mov ds, ax { call old interrupt } pushf call dword ptr Int8_Save { save task info } mov dx, word ptr [@@cur_t] mov bx, dx shl bx, 2 les di, dword ptr Tasks[bx] { skip stack } add di, 1024 { save register info } mov cx, 13 push ds mov ax, cs mov ds, ax mov si, offset @@tmp db $66; rep movsw pop ds { get next task } mov dx, word ptr [@@cur_t] @@task_loop: inc dx and dx, 7 mov bx, dx shl bx, 2 { load task info pointer } les di, dword ptr Tasks[bx] { if valid task, go out } mov ax, es cmp ax, 0 jne @@got_task { if looped, exit } cmp dx, word ptr [@@cur_t] je @@exit jmp @@task_loop @@got_task: { save new task id } mov word ptr [@@cur_t], dx jmp @@exit @@exit: { restore information } mov dx, es mov si, di { skip stack } add si, 1024 { save register info } mov cx, 13 mov ds, dx mov ax, cs mov es, ax mov di, offset @@tmp db $66; rep movsw { restore registers from prev. task } db $66; mov bx, word ptr [@@tmp+4] db $66; mov cx, word ptr [@@tmp+8] db $66; mov dx, word ptr [@@tmp+12] db $66; mov si, word ptr [@@tmp+16] db $66; mov di, word ptr [@@tmp+20] db $66; mov bp, word ptr [@@tmp+24] db $66; mov sp, word ptr [@@tmp+28] mov es, word ptr [@@tmp+40] mov ds, word ptr [@@tmp+42] mov ax, word ptr [@@tmp+46] mov ss, ax xor ax, ax xor ax, ax { set new return address and return the proper way } mov ax, word ptr [@@tmp+36] push ax mov ax, word ptr [@@tmp+44] push ax mov ax, word ptr [@@tmp+32] push ax { restore used register } db $66; mov ax, word ptr [@@tmp] iret { temporary storage } @@tmp: { eax, ebx, ecx, edx, esi, edi, ebp, esp, eip, dflags: longint; es, ds, cs, ss, fs, gs: word; } dd 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 dw 0, 0, 0, 0, 0, 0 { current task } @@cur_t: dw 0 @@bp: dd 0 @@sp: dd 0 @@ss: dw 0 end;
avian 6y ago
I'm looking at these long series of pushes and pops [1]. You have 26 general-purpose registers plus X, Y, Z. I wonder if it would be possible to have e.g. only 4 threads and have dedicated registers for each thread, avoiding the need to store/load all of them on each context switch. This would reduce the overhead and might make this a bit more usable in the real world. I mean, this is certainly possible when writing assembly. But I wonder if you can convince avr-gcc to do it. To have it limit its use of registers for a part of the compiled C code. A similar problem appears with interrupt handlers in C [2]. avr-gcc is smart enough to only push/pop registers in a handler that were actually clobbered in the code. But if you call a function pointer from an interrupt handler, it will always push/pop entire CPU state since it will assume that the code the pointer points to will potentially clobber everything. This significantly increases interrupt latency. [1] https://github.com/TurkeyMcMac/avr_threads/blob/master/avrt.S#L133 https://github.com/TurkeyMcMac/avr_threads/blob/master/avrt.... [2] https://www.avrfreaks.net/forum/calling-function-pointers-isr https://www.avrfreaks.net/forum/calling-function-pointers-is...
- jwmhjwmh 6y ago
  Maybe one could use the option -ffixed-reg and put different threads in different compilation units with different options. Even so, one would not be able to use the standard library, since it is not compiled with the right options, and even custom functions would have to be compiled separately for each thread. It would be a lot of hassle, but it might work.
  - captncraig 6y ago
    If you are gonna go through all that work with this chip in particular, you'd probably be better off putting four of them on one board. It's all kinda moot with more powerful chips available for cheaper anyway.
    - jwmhjwmh 6y ago
      I wasn't planning on actually doing it, I was just thinking of how it could be done.
kwhitefoot 6y ago
> /* Don't change these flag values! */ Rant: It always annoys me when I see comments like this in the source. If it is important enough to implore people not to change something then it is surely important enough to explain why. When I saw comments like this during code reviews I always asked the author to add a comment that briefly explained the reason for the values being the way they are. Of course this was rather rare because most developers don't write many comments in the first place.
- jwmhjwmh 6y ago
  You're right. I have added a description. Thanks.
  - analognoise 6y ago
    I love the HN live code review.
  - kwhitefoot 6y ago
    Much clearer. That's a faster reaction to a code review than I used to get when I was doing them 'in real life'!
goldenshale 6y ago
I wrote a pre-emptive, multi-threaded OS for the AVR atmega 128 back in college as a sensor networking operating system called Mantis OS (mos). For anyone interested in this direction, it also provides a device layer and “drivers” for timers, ADCs, eeprom, serial port, networking, etc. A great group of folks kept improving it for years so there is a lot there to learn from just as a resource too. https://github.com/rosejn/mantis https://github.com/rosejn/mantis
- andrewguy9 6y ago
  I also wrote a preemptive threaded operating system for AVR atmega 128. At the start we had threads, pipes between threads, serial io, interrupts. After we finished the project, I ported the system to standard UNIX system calls. Now I can tinker on it, and get full access to GDB/prints/profilers. I use signals, timers and pipes to simulate interrupts, clock and serial ports respectively. Because I’m targeting UNIX it’s pretty easy to get started and build little toy experiments. I haven’t gotten it to compile on AVR for 10 years. But I have been maintaining it as a playground for new ideas. Some recent additions are resumable functions (like python generators), A lisp user space, and a performance regression test suite. https://github.com/andrewguy9/kernelpanic https://github.com/andrewguy9/kernelpanic
mmastrac 6y ago
I love it. The next level of this hack would be integrating it with the Rust/AVR work and building pseudo-threads with memory and thread safety on the platform (for no reason other than to do it).

63 points by jwmhjwmh 6y ago

From the github: >> I do not see a practical use for this library, but I think it's interesting. +100 This is the essence of hacking.

Lerc 6y ago
indeed. Yet I might have a use for this library in a project I have no practical use for.

magicalhippo 6y ago

Ahhh this reminded me of when I as a teen saved up and bought "Assembly Language Master Class"[1], the only assembly-related book I could find in my local bookstore that didn't look like a complete intro-book. I had learned a bit of asm from some articles I had downloaded from various BBSes, and wanted to take the next step. After reading through it a few times I got the idea to try to write a pre-emptive scheduler myself. This was way before the internet so I just knew the concept existed, and the book didn't have anything like that in it per se. So I spent a day or two figuring out by my self how to preserve and restore the registers and flags without disturbing them. I wrote it in Turbo Pascal, using the inline asm for the task switcher. Each "process" was just a procedure (subroutine) that ran in a loop until a global bool was set. I decided to hook the RTC[2] for switching tasks, but nothing more. So each time-slice was fixed at 18.2ms which didn't make things terribly interactive. Never got further, it was more of a "can I do it" type project, but boy that feeling when I saw my three "processes" running one after another without cooperation... priceless! [1]: https://www.amazon.com/Assembly-Language-Master-Class-Press/dp/1874416346 https://www.amazon.com/Assembly-Language-Master-Class-Press/... [2]: https://en.wikipedia.org/wiki/Interrupt_request_%28PC_architecture%29#Slave_PIC https://en.wikipedia.org/wiki/Interrupt_request_%28PC_archit...

magicalhippo 6y ago
Ah found the code. Not pasting the whole thing, but here's the relevant bits of the task switching. Keep in mind this was me with a few years of programming in general under my belt so yeah, still bit of a noob. type task_type = record stack: array[0..1023] of byte; eax, ebx, ecx, edx, esi, edi, ebp, esp, eip, flags: longint; es, ds, cs, ss, fs, gs: word; end; task_type_ptr = ^task_type; procedure MTaskHandler; assembler; asm cli { save vital information } { eax, ebx, ecx, edx, esi, edi, ebp, esp, eip, dflags: longint; es, ds, cs, ss, fs, gs: word; } db $66; mov word ptr [@@tmp], ax db $66; mov word ptr [@@tmp+4], bx db $66; mov word ptr [@@tmp+8], cx db $66; mov word ptr [@@tmp+12], dx db $66; mov word ptr [@@tmp+16], si db $66; mov word ptr [@@tmp+20], di { get ip } db $66; xor ax, ax pop ax { pop the ip from stack } db $66; mov word ptr [@@tmp+32], ax { ip } { get cs } pop dx { get flags } db $66; pushf db $66; pop ax pop ax db $66; mov word ptr [@@tmp+36], ax { dflags } { save bp and sp after the modification } db $66; mov word ptr [@@tmp+24], bp db $66; mov word ptr [@@tmp+28], sp mov word ptr [@@tmp+40], es mov word ptr [@@tmp+42], ds mov word ptr [@@tmp+44], dx { cs } mov word ptr [@@tmp+46], ss { setup own stack } db $66; mov word ptr [@@bp], bp db $66; mov word ptr [@@sp], sp mov word ptr [@@ss], ss db $66; xor bp, bp db $66; xor sp, sp mov sp, offset Stack + 1022 mov bp, sp mov ax, seg Stack mov ss, ax { restore data segment } mov ax, seg @data mov ds, ax { call old interrupt } pushf call dword ptr Int8_Save { save task info } mov dx, word ptr [@@cur_t] mov bx, dx shl bx, 2 les di, dword ptr Tasks[bx] { skip stack } add di, 1024 { save register info } mov cx, 13 push ds mov ax, cs mov ds, ax mov si, offset @@tmp db $66; rep movsw pop ds { get next task } mov dx, word ptr [@@cur_t] @@task_loop: inc dx and dx, 7 mov bx, dx shl bx, 2 { load task info pointer } les di, dword ptr Tasks[bx] { if valid task, go out } mov ax, es cmp ax, 0 jne @@got_task { if looped, exit } cmp dx, word ptr [@@cur_t] je @@exit jmp @@task_loop @@got_task: { save new task id } mov word ptr [@@cur_t], dx jmp @@exit @@exit: { restore information } mov dx, es mov si, di { skip stack } add si, 1024 { save register info } mov cx, 13 mov ds, dx mov ax, cs mov es, ax mov di, offset @@tmp db $66; rep movsw { restore registers from prev. task } db $66; mov bx, word ptr [@@tmp+4] db $66; mov cx, word ptr [@@tmp+8] db $66; mov dx, word ptr [@@tmp+12] db $66; mov si, word ptr [@@tmp+16] db $66; mov di, word ptr [@@tmp+20] db $66; mov bp, word ptr [@@tmp+24] db $66; mov sp, word ptr [@@tmp+28] mov es, word ptr [@@tmp+40] mov ds, word ptr [@@tmp+42] mov ax, word ptr [@@tmp+46] mov ss, ax xor ax, ax xor ax, ax { set new return address and return the proper way } mov ax, word ptr [@@tmp+36] push ax mov ax, word ptr [@@tmp+44] push ax mov ax, word ptr [@@tmp+32] push ax { restore used register } db $66; mov ax, word ptr [@@tmp] iret { temporary storage } @@tmp: { eax, ebx, ecx, edx, esi, edi, ebp, esp, eip, dflags: longint; es, ds, cs, ss, fs, gs: word; } dd 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 dw 0, 0, 0, 0, 0, 0 { current task } @@cur_t: dw 0 @@bp: dd 0 @@sp: dd 0 @@ss: dw 0 end;

avian 6y ago

I'm looking at these long series of pushes and pops [1]. You have 26 general-purpose registers plus X, Y, Z. I wonder if it would be possible to have e.g. only 4 threads and have dedicated registers for each thread, avoiding the need to store/load all of them on each context switch. This would reduce the overhead and might make this a bit more usable in the real world. I mean, this is certainly possible when writing assembly. But I wonder if you can convince avr-gcc to do it. To have it limit its use of registers for a part of the compiled C code. A similar problem appears with interrupt handlers in C [2]. avr-gcc is smart enough to only push/pop registers in a handler that were actually clobbered in the code. But if you call a function pointer from an interrupt handler, it will always push/pop entire CPU state since it will assume that the code the pointer points to will potentially clobber everything. This significantly increases interrupt latency. [1] https://github.com/TurkeyMcMac/avr_threads/blob/master/avrt.S#L133 https://github.com/TurkeyMcMac/avr_threads/blob/master/avrt.... [2] https://www.avrfreaks.net/forum/calling-function-pointers-isr https://www.avrfreaks.net/forum/calling-function-pointers-is...

jwmhjwmh 6y ago
Maybe one could use the option -ffixed-reg and put different threads in different compilation units with different options. Even so, one would not be able to use the standard library, since it is not compiled with the right options, and even custom functions would have to be compiled separately for each thread. It would be a lot of hassle, but it might work.
- captncraig 6y ago
  If you are gonna go through all that work with this chip in particular, you'd probably be better off putting four of them on one board. It's all kinda moot with more powerful chips available for cheaper anyway.
  - jwmhjwmh 6y ago
    I wasn't planning on actually doing it, I was just thinking of how it could be done.

kwhitefoot 6y ago

> /* Don't change these flag values! */ Rant: It always annoys me when I see comments like this in the source. If it is important enough to implore people not to change something then it is surely important enough to explain why. When I saw comments like this during code reviews I always asked the author to add a comment that briefly explained the reason for the values being the way they are. Of course this was rather rare because most developers don't write many comments in the first place.

jwmhjwmh 6y ago
You're right. I have added a description. Thanks.
- analognoise 6y ago
  I love the HN live code review.
- kwhitefoot 6y ago
  Much clearer. That's a faster reaction to a code review than I used to get when I was doing them 'in real life'!

goldenshale 6y ago

I wrote a pre-emptive, multi-threaded OS for the AVR atmega 128 back in college as a sensor networking operating system called Mantis OS (mos). For anyone interested in this direction, it also provides a device layer and “drivers” for timers, ADCs, eeprom, serial port, networking, etc. A great group of folks kept improving it for years so there is a lot there to learn from just as a resource too. https://github.com/rosejn/mantis https://github.com/rosejn/mantis

andrewguy9 6y ago
I also wrote a preemptive threaded operating system for AVR atmega 128. At the start we had threads, pipes between threads, serial io, interrupts. After we finished the project, I ported the system to standard UNIX system calls. Now I can tinker on it, and get full access to GDB/prints/profilers. I use signals, timers and pipes to simulate interrupts, clock and serial ports respectively. Because I’m targeting UNIX it’s pretty easy to get started and build little toy experiments. I haven’t gotten it to compile on AVR for 10 years. But I have been maintaining it as a playground for new ideas. Some recent additions are resumable functions (like python generators), A lisp user space, and a performance regression test suite. https://github.com/andrewguy9/kernelpanic https://github.com/andrewguy9/kernelpanic

mmastrac 6y ago

I love it. The next level of this hack would be integrating it with the Rust/AVR work and building pseudo-threads with memory and thread safety on the platform (for no reason other than to do it).