Re: architecture.md interrupt timing

[sam-falvo]

I would not have a fixed set of queues for interrupt types; rather, I'd make them dynamic.

The reason is I could envision a computer (almost certainly a general purpose computer) which has so many drivers installed that each require the 5ms jiffy service that unconditionally calling each handler on this queue results in violating timing requirements for other services.

Another approach that might work better is a dedicated "timer device" which offers a "call me back at or after this time passes" service. That way, devices (and maybe applications) opt-in to the timer's service, and callbacks happen only for those devices that need to be called.

An example of what I'm talking about is the AmigaOS "timer.device".

Let me know if this makes sense, or if I need to clarify.

[zuiko21]

Perhaps I didn't explain it correctly, and/or I'm not completely understanding your comment (language barrier!) but I think I'm doing it in a similar way than you describe.

The only unconditionally called routines are those for startup & shutdown procedures, as they will be executed just once per session. But things done ~200 times a second need to be carefully selected for performance, of course.

If a lot of drivers are installed on a system, but none of them needs to use, say, the jiffy task queue, then that queue will be empty and will be skipped altogether at interrupt time, making very little overhead. I think this is what you mean by:

callbacks happen only for those devices that need to be called.

There is a queue size variable for each queue which gets set at boot (or whenever a driver is installed/removed) which controls how many entries are to be used (and called); there are no holes on it, thus the loop iterates for the strict number of routines installed (which could be much less than the number of installed drivers). But in a worst case (many drivers, all of them with interrupt tasks and very heavy ones) the ISR would take a lot of time and the system will "drown on interrupts"... but I suppose there's a limit on what a 65xx could do...

About the timer device (would love to know more of its Amiga implementation) I believe it's a similar thing, just more versatile -- not just 5 or 1000 ms frequency. And also for a single shot delayed callbacks. Some drivers I already wrote (or stubbed) do not need to execute their interrupt task at every jiffy interrupt, but at a lower frequency (say, 50 Hz). Currently I'm doing this on a driver's internal counter that gets updated on every jiffy; when expired, the whole interrupt task is executed; but the OS has no knowledge about this, it just executes the (wrapper) routine at 200 Hz rate -- sometimes will quickly regain control, others not.

Perhaps a way to integrate this into the current scheme (without too much effort) would be adding a frequency parameter for each interrupt task on drivers, thus the ISR can keep track of its own counter and do the callback only when really needed, while drivers just provide the proper routine without "filtering" counters. This could also integrate the jiffy and slow queues, as they will just differ on the frequency parameter.

Another advantage of this approach is that would easily implement some interrupt balancing feature: for any task to be executed less-than-every-jiffy, the counter could be initially set randomly between 0 and the maximum value, so if many tasks are to be done at the same rate, they won't be done at the same time but somewhat spread out over time, and thus won't cause a "hiccup" on the system, violating timings etc. Already thought about this for the 1-second interrupt, but this way seems more useful...

[sam-falvo]

If a lot of drivers are installed on a system, but none of them needs to use, say, the jiffy task queue, then that queue will be empty and will be skipped altogether at interrupt time, making very little overhead.

Right; but, this decision appears to be made at driver initialization time, rather than at run-time. I was thinking more along the lines of something like GEOS "process lists," which are also periodically invoked, but which can be turned on and off dynamically, or AmigaOS's timer.device, where the list of callbacks is always curated to include only those things which are known to need calling back at a certain time.

I think an example would be better than an explanation here. I'll work on some (untested!) 65816 code to help illustrate what I mean.

[zuiko21]

I see... each task on the interrupt queue(s) can be enabled/disabled at runtime. Do you think a simple on/off control would suffice, or would be a real advantage to be able to modify that frequency parameter we discussed earlier?

The on/off control seems easily implemented. Doesn't matter whether the toggling is asked by an app or the driver itself, as both ways should be done via the Kernel's API.

Regarding my previous suggestion of variable frequency interrupt tasks, I think it's a good idea anyway as it has several advantages:

• Unifies jiffy & slow queues (and scanning one big list is faster than scanning two smaller ones)
• Finer load adjustment (not only 5/1000 ms)
• The on/off feature is more easily managed (single enable list)
• Simplifies the (already ugly) driver startup code

However, I think the asynchronous queue should be kept separated from the periodic one. It does make sense to implement the on/off feature on it, but some questions arise.

The 65xx "killer feature" of low interrupt latency somehow vanishes in the realm of such a "complex" system, but I don't want to make it worse. If you look at the ISR code, once a periodic interrupt is discarded (usually from VIA T1, it's the only hardware-dependent instruction in the ISR, for performance reasons) the async queue is managed ASAP -- and as soon as a driver acknowledges (and serves) the IRQ, the loop is aborted and user code is quickly resumed.

Please note that the async queue allows for accidental prioritizing, since the tasks at the end of the list will be called sooner (the list is scanned backwards). In case some entry has to be (temporarily) disabled, there are two ways of doing it:

• Replace the existing pointer for the address of a mere RTS. Simpler, but will waste some CPU time as the queue doesn't get shorter.
• Remove the entry from the queue, actually shrinking it. Disabling will be slower but, as it won't be a very frequent operation (or will it?) it's worth the faster ISR execution.

The second option seems better. But when it's time to reenable the task, will it be appended at the end of the list (altering priorities)? Or should it be kept at the original position/priority? If altered priorities are deemed acceptable, could be just done disabling the whole driver (via the not-yet-done DR_SHUT function), but that would prevent simple I/O operations, not just the interrupt tasks. Respecting original priorities seems feasible, but complicated.

[sam-falvo]

On Tue, May 9, 2017 at 9:47 AM, Carlos Santisteban ***@***.***> wrote: I see... each task on the interrupt queue(s) can be enabled/disabled at runtime. Do you think a simple on/off control would suffice, or would be a real advantage to be able to modify that frequency parameter we discussed earlier?

This is an interesting question. GEOS works by having a count-down timer. Every "process" (forgive their terminology; it has a reason for it, but I'll skip explaining it here) is described by a data structure, which looks kind-of like this: .word callbackHandler, timer .byt flags (I don't remember if this is precisely the layout, but the essentials are there.) The `flags` field has a bit in it which serves as an on/off switch. When it's clear, the process structure is skipped completely. I seem to recall this was bit 7, allowing a single BPL or BMI instruction to test for it. The `timer` field was a count-down. Every timer interrupt, it would decrement this field if not already zero. When it reaches zero, it then calls the callbackHandler subroutine. If the handler was not stopped/blocked, it would then reset the timer to its former value. In this way, a background process (hence the name) can run periodically, but not necessarily at the full rate. To make a process that runs at the full rate, you'd set `timer` to 0. ``` ; This is just my own implementation of the algorithm. ; This may not match what GEOS does in fact. ; ; This requires that the application somehow install a list of processes, ; which sets a pointer p2_proctab. (P2_ prefix == page 2 or higher.) ; ; Each entry in the proctab looks like this: ; .WORD callback (+0) (Must be biased by -1 ahead of time) ; .WORD timer (+2) ; and is copied into a kernel-maintained table at p2_proctab. ; ; The kernel maintains a separate table that looks like this: ; .WORD currentTimer (+0) ; .BYTE flags (+2) ; .BYTE padding ; Each entry corresponds to a process table entry, and maintains kernel- ; maintained state for the process. It's deliberately designed to be the same ; number of bytes as the main process table entry, to make coding easier/faster. ; ; p2_maxprocs tells how many processes exist in the table. NOTE that it is ; shifted by 2 bits, so if you have N processes, p2_maxprocs = 4*N. This allows ; the code to use a single CPX instruction for range checking instead of relying ; on all manner of expensive bit-shifting instructions. ; ; The routine which "installs" a process table is responsible for making sure ; these invariants hold. runProcesses: ; Start with first process timer. LDX #$00 ; WHILE process number < maximum number of processes DO rp_again: CPX p2_maxprocs BCC rp_done BEQ rp_done ; IF process is runnable THEN LDA p2_prcstat+2,X BPL rp_blocked ; Decrement counter. DEC p2_prcstat+0,X BPL *+3 DEC p2_prcstat+1,X ; IF counter is zero THEN LDA p2_prcstat+1,X BNE rp_not_elapsed LDA p2_prcstat+0,X BNE rp_not_elapsed ; Call the process handler. TXA PHA JSR rp_callback PLA TAX ; Reset the counter. LDA p2_proctab+2,X STA p2_prcstat,X LDA p2_proctab+3,X STA p2_prcstat+1,X ; END (if) rp_not_elapsed: ; END (if) rp_is_blocked: ; Look at next process. INX INX INX INX ; END (while) JMP rp_again rp_done: ; Return RTS rp_callback: LDA p2_proctab+0,X PHA LDA p2_proctab+1,X PHA RTS ```

However, I think the asynchronous queue should be kept separated from the periodic one. It does make sense to implement the on/off feature on it, but some questions arise.

I'm still not quite sure how the asynchronous queue works just yet. I'm still studying the code.

The 65xx "killer feature" of low interrupt latency somehow vanishes in the realm of such a "complex" system, but I don't want to make it worse. If you look at the ISR code, once a periodic interrupt is discarded (usually from VIA T1, it's the only hardware-dependent instruction in the ISR, for performance reasons) the async queue is managed ASAP -- and as soon as a driver acknowledges (and serves) the IRQ, the loop is aborted and user code is quickly resumed.

Correct; that's as it should be. AmigaOS works in a similar way. In AmigaOS, device drivers "register" themselves (versus having the kernel do it for them) on various interrupt lists. Of course, they can (as usual) deregister at any time as well. For example, a floppy disk driver doesn't need to respond to FDC interrupts if there's no disk in the drive, so it can unregister itself in that situation.

The second option seems better. But when it's time to reenable the task, will it be appended at the end of the list (altering priorities)? Or should it be kept at the original position/priority? If altered priorities are deemed acceptable, could be just done disabling the whole driver (via the not-yet-done DR_SHUT function), but that would prevent simple I/O operations, not just the interrupt tasks. Respecting original priorities seems feasible, but complicated.

If you maintain the invariant that one driver binds to one (type of) device, then it shouldn't matter in which order the drivers are scanned. I think altering priorities is an acceptable solution provided: 1) You make it obvious to the device driver developer that this is the case, and, 2) You make it a best-practice that devices should be orthogonal to each other (that is, a device driver should respond only to its own sources of interrupts). It's really bad practice to have more than one driver responding to a single interrupt source anyway. AmigaOS has similar rules in place (although it allows some limited control over device priorities, it never really served any useful purpose).

…

-- Samuel A. Falvo II

[zuiko21]

A quick reply: I like the GEOS' approach and your sample code and made the picture pretty clear. A simple flag for each driver in the queue will enable/disable its execution. Adds very little overhead and it's easily implemented, too.

Still have to treat differently the periodic (jiffy) queue from the asynchronous one. For periodic interrupt tasks, priorities and execution order are irrelevant, thus forget my previous comments. As long as they get executed with the specified frequency, all is OK. Anyway, since I'll be using a flag bit for temporary disable, the queue order will remain unchanged.

Priorities are still a thing for the asynchronous queue, though. As these interrupts are inexpectedly generated, they should of course be serviced ASAP. Since the 65xx CPUs have a very simple interrupt mechanism (only one IRQ line besides NMI) the only way to identify the interrupt source is to sequentially execute each handler until one acknoledges and serves the interrupt. Frequency makes no sense here, but the ability to temporarily disable some of them will definitely reduce latency of the following (less priority) handlers. This time I thinks it's best not to modify the queue order (and thus priorities) but the GEOS approach will respect that anyway.

Checking that flag will add a bit of overhead, but it's well worth it. Something like this (in full 65816 dialect):

    LDX dreq_mx  ; get queue size to scan backwards (faster)
    BEQ ir_done  ; queue is empty, go away!
i_req:
        LDA async_flags-2, X  ; ### is this task enabled? ###
        BPL async_skip  ; ### nope, just go for next ###
            PHX  ; just in case...
            JSR (drv_async-2, X)  ; call the handler
            PLX
                BCC isr_done  ; terminate as soon as the IRQ gets acknowledged (C=0)
async_skip:
        DEX  ; go for next entry
        DEX
        BNE i_req  ; loop until all done
ir_done:

This is pretty much the same code as seen on OS/isr/irq16.s for handling the asynchronous interrupts, the only additions being the instructions commented with ###... this only adds a 6 clock cycles overhead and, best of all, in case a task is disabled, will save a lot of cycles as the most time-consuming part of the loop is skipped.

Just in case you were puzzled by the -2 offset on the indexed addressings... I prefer doing these time-critical loops backwards as I don't need to compare the loop register against the loop limit, but just let it go down to zero so BNE will do. But since I'll be one position after (e.g. a 10 el. queue [0...9] will start at 10 itself, down to 1) a correction is needed. Elements are 2-byte words (bank 0 addresses, and I keep the same spacing in async_flags for faster, single index management), thus the minus 2 offset and the couple of DEX in the loop.

The only doubt I still have about this is the API for enabling/disabling the interrupt tasks. Perhaps should be able to change the frequency (in case of periodic tasks) also? If so, I'd use a value of 1 for tasks to be executed at every jiffy and so on, while zero would mean disabled, all within a single parameter. Would it need some function to check the current status of an interrupt task, and the currently set frequency value? I'd love to keep as little API functions as possible...

[sam-falvo]

Stand by. I should be able to respond to this by this weekend (if I remember to check it!). Preparing to entertain family and starting new job this week, so I'll be a bit scattered.

…

On Sat, May 13, 2017 at 1:24 PM, Carlos Santisteban < ***@***.***> wrote: A quick reply: I like the GEOS' approach and your sample code and made the picture pretty clear. A simple *flag* for each driver in the queue will *enable/disable* its execution. Adds very little overhead and it's easily implemented, too. Still have to treat differently the *periodic* (jiffy) queue from the *asynchronous* one. For periodic interrupt tasks, *priorities and execution order are irrelevant*, thus forget my previous comments. As long as they get executed with the specified *frequency*, all is OK. Anyway, since I'll be using a flag bit for temporary disable, the *queue order will remain unchanged*. Priorities are still a thing for the *asynchronous* queue, though. As these interrupts are *inexpectedly generated*, they should of course be serviced ASAP. Since the 65xx CPUs have a very simple interrupt mechanism (only one IRQ line besides NMI) the only way to identify the interrupt *source* is to *sequentially execute each handler* *until one acknoledges and serves* the interrupt. *Frequency* makes no sense here, but the ability to temporarily disable some of them will definitely reduce *latency* of the following (less priority) handlers. This time I thinks it's best *not* to modify the queue order (and thus *priorities*) but the GEOS approach will respect that anyway. Checking that flag will add *a bit* of overhead, but it's well worth it. Something like this (in full 65816 dialect): LDX dreq_mx ; get queue size to scan backwards (faster) BEQ ir_done ; queue is empty, go away! i_req: LDA async_flags-2, X ; ### is this task enabled? ### BPL async_skip ; ### nope, just go for next ### PHX ; just in case... JSR (drv_async-2, X) ; call the handler PLX BCC isr_done ; terminate as soon as the IRQ gets acknowledged (C=0) async_skip: DEX ; go for next entry DEX BNE i_req ; loop until all done ir_done: This is pretty much *the same code* as seen on OS/isr/irq16.s for handling the *asynchronous* interrupts, the only additions being the instructions commented with ###... this only adds a *6 clock cycles overhead* and, best of all, in case a task is disabled, will *save a lot* of cycles as the most time-consuming part of the loop is skipped. Just in case you were puzzled by the -2 offset on the indexed addressings... I prefer doing these time-critical loops *backwards* as I don't need to compare the loop register against the loop *limit*, but just let it go *down to zero* so BNE will do. But since I'll be one position *after* (e.g. a 10 el. queue [0...9] will start at 10 itself, down to 1) a correction is needed. Elements are 2-byte words (bank 0 addresses, and I keep *the same spacing* in async_flags for *faster*, single index management), thus the *minus 2* offset and the couple of DEX in the loop. The only doubt I still have about this is the *API* for enabling/disabling the interrupt tasks. Perhaps should be able to change the *frequency* (in case of *periodic* tasks) also? If so, I'd use a value of *1* for tasks to be executed at *every* jiffy and so on, while *zero* would mean *disabled*, all within a single parameter. Would it need some function to *check* the current *status* of an interrupt task, and the *currently set* frequency value? I'd love to keep as *little* API functions as possible... — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#2 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABbP-KP-0hdDXfBnBdJrakWOoYZrwpb3ks5r5hFigaJpZM4NUf-W> .

-- Samuel A. Falvo II