Important Chat logs

December 18th 2014 - Execution Model Discussion

[22:26:03] <alevy> the next thing i was going to do is add a syscall for registering a callback (i'll start with just a timer) and re-implement blink in user space
[22:26:23] <alevy> all without any memory protection yet
[22:27:05] <immesys> ok
[22:27:14] <immesys> so callback semantics need some thought
[22:27:24] <alevy> i agree
[22:27:33] <immesys> we could either have it that callbacks are injected whenever the process stack fully unwinds
[22:27:45] <immesys> e.g main exits()
[22:28:09] <alevy> oh excellent point... i hadn't thought of that
[22:28:16] <immesys> which means that when we call main, we just set the LR to point to some handler that pops off callbacks from a queue
[22:28:22] <immesys> the handler being in OS space
[22:28:32] <immesys> or...
[22:28:38] <immesys> and I think this is more flexible
[22:28:47] <immesys> the callbacks happen when there is a yield() syscall
[22:28:52] <immesys> or some other name
[22:29:01] <alevy> yeah, i like that more
[22:29:03] <immesys> and the stack unwinding is an implicit yield
[22:29:09] <alevy> so reiterating...
[22:29:53] <immesys> and for timer delays, the process can decide whether or not those constitute a yield
[22:30:22] <alevy> hrm... i'm confused by that last part
[22:30:27] <alevy> you mean timer delays in main?
[22:31:06] <immesys> Well its like this. I am executing a syscall which will block, do I want callbacks to execute while I am blocked or not
[22:31:13] <immesys> you don't want it to happen always
[22:31:20] <immesys> but if you _do_ want it to happen
[22:31:34] <immesys> you can't express it as the_syscall(); _yield();
[22:31:38] <immesys> because that is not the same as
[22:31:42] <immesys> _syscall_and_yield()
[22:32:16] <alevy> i see. sure so we'll a syscall argument that determines whether it consitutes a yield or not
[22:32:40] <alevy> (so many mistakes in that last sentence...)
[22:32:50] <alevy> (but you get it...)
[22:33:45] <alevy> but we expect the common case to be "queue this callback to be registered when I yield"?
[22:34:18] <immesys> yes
[22:34:29] <alevy> where for the most part, `initialize()` will add a bunch of callbacks that should be registered at once when initialize returns 
[22:34:43] <immesys> yeah
[22:34:51] <immesys> although some might be timer callbacks
[22:35:16] <alevy> inside of initialize()? like for waiting for some hardware to finish setting up or something?
[22:35:52] <immesys> no
[22:35:57] <immesys> I mean like say blink()
[22:36:06] <immesys> blink would have
[22:36:17] <immesys> start_periodic(interval, callback)
[22:36:24] <immesys> callback = {toggle led}
[22:37:08] <immesys> 89% on rust clone
[22:37:11] <immesys> hope it compiles faster
[22:37:14] <alevy> so, in my head, that would be implemented as:
[22:37:50] <alevy> blink_callback() { LED.toggle() }  initialize() { start_periodic(1000, blink_callback); }
[22:38:01] <immesys> yeah that's right
[22:38:21] <immesys> although if it were a different language, the callback could be a closure, which I like. But that is the same yes
[22:38:22] <alevy> in which case it's still fine for start_periodic to actually be registered after initialize returns
[22:38:44] <immesys> can you explain what you mean by "registered"
[22:38:47] <alevy> yes agreed, just trying to think about it closer to the metal
[22:38:56] <alevy> ah... so when i call `start_interval` in C
[22:39:04] <alevy> that invokes a system call
[22:39:29] <alevy> which will enqueue the callback in some data structure for the app in the kernel, but not actually invoke that callback...
[22:39:30] <alevy> until
[22:39:34] <alevy> initialize returns
[22:39:55] <immesys> until the yield syscall is invoked
[22:39:58] <alevy> yes
[22:40:02] <immesys> initialize returning is an implicit yield
[22:40:03] <immesys> s oyes
[22:40:05] <immesys> so yes*
[22:40:10] <alevy> yeah, that's what i meant
[22:40:31] <immesys> it's run to completion so a callback will never be invoked while you have stuff on the stack, unless you explicitly yield.
[22:40:36] <immesys> so yeah you are right
[22:40:57] <immesys> so the timer threw me off
[22:41:09] <immesys> because I would imagine the timer would start counting immediatly
[22:41:15] <immesys> so say in initialize I had:
[22:41:40] <immesys> { start_one_shot(1ns, callback); do_stuff_for_longer_than_1ns(); }
[22:41:53] <immesys> then the timer would fire _as soon as_ initialize returned
[22:41:57] <immesys> which would be longer than 1ns
[22:42:00] <alevy> correct
[22:42:02] <alevy> i think that's OK
[22:42:06] <immesys> yes me too
[22:42:32] <immesys> so
[22:42:38] <immesys> I think phil might bring this up
[22:42:48] <immesys> once upon a time, TinyOS task queues worked like this
[22:42:58] <immesys> and they had problems because the queue size was dynamic
[22:43:01] <immesys> and it could overflow
[22:43:07] <immesys> so they changed it to a fixed size
[22:43:12] <immesys> where tasks can only be posted once
[22:43:24] <immesys> are we ok with the callback queue being dynamic, and possibly overflowable?
[22:43:35] <immesys> like start_periodic(1ns, callback) is like game over
[22:43:46] <alevy> well, it depends how it's implemented
[22:43:48] <immesys> callbacks will queue faster than they can execute
[22:44:05] <alevy> or it depends what the semantics are
[22:44:32] <alevy> i think there should be at most one outstanding task for each callback
[22:44:37] <immesys> hmm
[22:44:43] <immesys> I don't know that I agree with that
[22:45:09] <alevy> or, at least at the ABI level
[22:45:09] <immesys> I'll listen to your justification though
[22:45:33] <alevy> well the main reasons are (1) exactly the problem you said, and (2) it's what the hardware gives us
[22:45:45] <immesys> I disagree with (2)
[22:45:48] <alevy> ok
[22:45:56] <immesys> say the callback is for an interrupt
[22:46:07] <immesys> the hardware restricts us to one interrupt per ISR invocation
[22:46:10] <immesys> but thats in kernel space
[22:46:18] <immesys> and we will almost certainly process those fast enough
[22:46:32] <immesys> but then those get queued for the application in software
[22:46:39] <immesys> so we are free to queue multiple
[22:46:47] <alevy> ok yes i agree with that
[22:46:51] <alevy> i guess what i mean is more
[22:47:04] <alevy> it's a closer representation of what you would get writing bare metal
[22:47:13] <immesys> true
[22:47:19] <alevy> if you're handlers are fast enough, you won't miss interrupts
[22:47:26] <alevy> and you can always implement a queue in user space
[22:47:29] <immesys> but I can tell you that it complicates code immensely worrying about missed interrupts
[22:47:32] <alevy> (or lua can do it for you)
[22:47:33] <immesys> deadlocks abound
[22:47:38] <alevy> hrm...
[22:47:43] <alevy> i buy that...
[22:47:59] <alevy> so i think, then, here's the question:
[22:48:33] <alevy> is there a significant advantage to implemnting the queue in the kernel as opposed to in the user-level runtime-library
[22:48:40] <immesys> my gut feeling is that as long as an application cannot affect the kernel or other applications by overflowing the task queue, we should let it have multiple outstanding tasks
[22:48:54] <immesys> how would you do it in userland?
[22:49:01] <immesys> I don't think its possible
[22:49:36] <immesys> there is a third option
[22:49:36] <alevy> you're right... hold on...
[22:49:47] <immesys> that we can limit callbacks to N>1
[22:49:52] <immesys> but N < infinity
[22:49:57] <immesys> like the accept() queue
[22:49:58] <alevy> because an app only has one thread in our model
[22:50:04] <alevy> right
[22:50:18] <alevy> like, for a userland library that's most flexible, we want basically the same model as hardware
[22:50:35] <alevy> where there is an execution thread, and tasks in the kernel are run to completion, but they can be interrupted by ISRs
[22:50:51] <immesys> so I thought about userland interrupt context
[22:51:03] <immesys> and I think that it would be a disservice
[22:51:16] <immesys> because the resulting race protection would complicate life
[22:51:42] <alevy> OK, I'm becoming convinced
[22:51:50] <immesys> I mean even userland linux does not do IRQ
[22:51:52] <alevy> so you're suggested a fixed sized task queue for each app
[22:52:02] <immesys> so I am suggesting one of two things
[22:52:03] <alevy> well, aren't signals like that kind of?
[22:52:25] <immesys> fixed size queue for each app so it doesn't affect kernel or other apps
[22:52:37] <immesys> and possibly a limit argument for number of outstanding callbacks
[22:52:46] <immesys> for a given callback generator
[22:52:53] <alevy> yeah
[22:53:04] <immesys> so start_periodic(interval=X, callback=Y, max_outstanding=Z)
[22:53:06] <immesys> tail drop
[22:53:13] <alevy> and the queue could be in the app's memory, so it can decide how large it should be
[22:53:24] <immesys> yeah
[22:53:33] <alevy> yeah, that makes a lot of sense to me
[22:53:58] <immesys> I like that model
[22:54:56] <alevy> do you specify max_outstanding (or implicitly 1 or something) for each callback, and the kernel figures out how big of a queue that requires (presumeably the sum)?
[22:55:00] <immesys> or actually start_periodic(interval=X, callback=Y, max_outstanding=Z, is_yield)
[22:55:17] <alevy> or do you separately allocate a task queue in initialize with a certain size
[22:55:19] <immesys> no I would imagine the queue is decided in advance, like the stack
[22:55:36] <immesys> but then you count the callbacks in the queue before inserting a new one
[22:55:53] <immesys> yes, what yo usaid
[22:55:53] <alevy> ok, so the sum of max_outstanding of all the callback kinds can be larger than the size of the queue
[22:55:56] <immesys> allocate in initialize
[22:55:58] <immesys> yes
[22:56:00] <alevy> kk
[22:56:03] <ppannuto_> I thought we had the design where the only function known to the kernel at program load was `init`, and init has to register other callbacks for every other signal / event
[22:56:04] <immesys> statistical multiplexing for the win
[22:56:11] <ppannuto_> it seems like that's where to set queue depth on register
[22:56:14] <immesys> initialize == init
[22:56:18] <alevy> ppannuto_ yes
[22:56:39] <ppannuto_> great
[22:57:04] <alevy> where, by the way, I'm assuming "knows about" just means the function that starts at instruction offset zero
[22:57:08] <immesys> presumably init also sets up the SP and stuff?
[22:57:19] <alevy> nah
[22:57:21] <immesys> probably not zero, but a known offset, yes
[22:57:28] <alevy> i would think the kernel decides on SP
[22:57:30] <immesys> init is really _start() right?
[22:57:33] <alevy> yeah
[22:57:33] <ppannuto_> wouldn't SP be set up on load?
[22:57:43] <immesys> so _start must do crt0 stuff too
[22:58:01] <immesys> like SP, and relocation and BSS
[22:58:10] <alevy> immesys, no i don't think so
[22:58:16] <ppannuto_> That feels like boilerplate, feels like we should supply something like a c runtime that provides _start and calls init
[22:58:17] <immesys> who's going to do that?
[22:58:24] <alevy> that's the point of the kernel loader should do
[22:58:34] <immesys> kernel loader can't know the necessary symbols
[22:58:47] <alevy> the necessary symbols?
[22:58:53] <immesys> its much easier to have a _start entry point into the payload that gets given its memory range
[22:58:59] <immesys> and it does all the boilerplate
[22:59:14] <immesys> to do that stuff you need to know where the BSS is, how big it is, where the relocation is etc
[22:59:54] <immesys> ppannuto_: yes, its library boilerplate, but still in payload right?
[23:00:05] <alevy> oh ok fine. so you're suggesting, there is a libstorm that has the actual _start() and gets linked to my app and calls my app's initialize()
[23:00:11] <immesys> yes
[23:00:21] <ppannuto_> yes to both
[23:00:27] <immesys> but libstorm == libcrt.a
[23:00:28] <immesys> yes
[23:00:32] <immesys> .o*
[23:00:57] <immesys> and we would compile with nostartfiles