Contexts, Threads, Capabilities and Interfaces

[Crazed123]

Well, I'm done with physical and virtual memory managers (they work, at least), paging and a kernel heap. There is basic text console support in the kernel, and basic IRQ support. It's time to add the ability to put stuff outside the kernel, and I've got ideas to toss around.

I've had this wierd idea about processes. I won't do processes. Nowadays, we have threads, often multiple ones per process, and so if you seperate the information in a thread from the information in a process you get what I want to call an executable context. Mmmm... buzzword. Anyway, a context would contain the virtual memory information, a context identifier (cid of course!), child contexts, stacks, and possibly something else. The reason for the small amount of information is that a lot of things go under a thread, and I'm planning on putting filesystems in a prolary (PROcess/librARY, with l thrown in because a consonant is needed) that'll run outside the kernel, but that would be part of context information also.

Threads would contain most of what we call process information now, a thread id, scheduling information, associated context, parent thread, child threads, priority, thread state, all of that stuff that describes a running thread.

Given that my system will be able to mount a context at a given location in another for use as a prolary, I think the seperation is appropriate.

Since I'm putting things in outside-kernelspace now, I should design in the security protections HERE. I think a sensible model is to have each object keep a check-number or whatnot (read about that in MOS) for each user and make a default-deny capability system based on that. This way an object can repeal a given user's capabilities. Or possibly normal capabilities if that's too expensive to implement. Anyway, I think it should security should be implemented at this low level, and thus wrote this here.

Finally, if most functionality is in prolaries, then a way is needed to identify what functionality a prolary has. What I mean is that, for example, there needs to be a way to talk about a VFS-type prolary interface even though what's really running might be ext2fs here, reiserfs there and fat32 in the other. Each of those might have their own driver, and there needs to be a mechanism to talk to them all in a uniform way other than what I'm willing to include in a distribution. The same thing happens with graphics cards, how to check a driver for an OpenGL implementation without attempting to actually load it and getting a failed link? Basically, a mechanism is needed to query a prolary for having a desired interface, because you don't want to do endless dlsym()'s only to find the final standard VFS function isn't supported.

That's pretty much everything, I'm really looking for ideas, feedback, tips and that sort of thing before I put code to keyboard on what is undoubtedly one of the most important parts of the kernel.

[proxy]

ok, i have a question, how is this drastically different from the linux model of "i only schedule processes". Basically it sounds like you are mostely combining the concept of a process (address space information) with a thread (stream of execution). It's not a bad idea, but unless i missed something, it's not new either.

proxy

[Crazed123]

I'm seperating a process from a thread. In most systems the two are kept in ONE structure and manipulated with the same code (roughly, multithreading is common nowadays, but this is the theoretical model it started from). In my system they are kept in seperate structures and can be manipulated with different code.

For example, one context's memory can be mounted so it appears in another address space at a given location. Also, I've thought of shifting native stacks (ie: for a ring X thread the native stack is stack for ring X) into the thread structure, allowing threads to migrate between contexts.

And I really could use some ideas on the security protections (MUCHO IMPORTANTE) and the interfaces.

[JoeKayzA]

For example, one context's memory can be mounted so it appears in another address space at a given location.

I hope I didn't get that all wrong, but isn't that shared memory?

Also, I've thought of shifting native stacks (ie: for a ring X thread the native stack is stack for ring X) into the thread structure, allowing threads to migrate between contexts.

I'm quite interested in that one. When you allow a thread to migrate from one context to another, how do you exactly handle the stacks? Just map it into the other one, or do you allocate a new stack in the new context? If the latter is the case, what is actually the difference to having two seperate threads (one in each context) and do a RPC? I'm asking this because I was thinking about migrating threads too, but for now I came to the conclusion that I would not allow a running thread to migrate, the only possibility would be to manually move the 'thread-object' into the new context, but that would require to manually set the new stack and eip, just like with a starting thread.

And I really could use some ideas on the security protections (MUCHO IMPORTANTE) and the interfaces.

First off, do I understand it right that a 'prolary' is actually an execution context on its own, say, it has its own address space? And to do calls, you actually do some sort of RPC?

So, you could provide a system wide method to 'reflect' interfaces. That means, every service must implement a basic 'service'-interface, that allows any client to discover the other interfaces it supports. How far you want to go here is up to you: you could either give each interface its own GUID (like corba does it, AFAIK), and then just negotiate about IDs, but you could also let the service describe each method, with name, input and output parameters, so that the client could examine every single method it needs to be present.

About security: If that helps you, I could explain a bit about what I'm planning for security in my system. The foundation of security is that every process (or context or whatever ::) ) has its own set of interface handles (much like the handles in NT), where each handle has its own ID that is valid only inside that process. A handle connects to an object handler, which can reside either in a user space service or a kernel module, and every handle represents a specific interface. These interfaces are used for every type of system call - be it address space manipulation, thread creation or termination, synchronization, messaging, up to higher lever things like device and filesystem operations.

The key is that every process can only access the ressources it has access to, via an interface handle. It can only gain access to a new interface when it obtains it from someone else (and that happens through interfaces too). And this 'someone else' should follow a specific security policy then - be it ACLs with users and groups (for filesystems) or capability-based security (every app can only consume a certain amount of network bandwith, a certain space on screen, and has to share that with any child processes it creates), or most likely, a mixture of that all.

Hope I could give you some ideas!

cheers Joe

[Crazed123]

I hope I didn't get that all wrong, but isn't that shared memory?

In a sense, I didn't really explain earlier. Within a given virtual memory tree each node (page) is either marked as sharable or not with a flag. When a tree is mounted onto another copies of all its virtual mappings are made, and for each sharable page the physical page node is shared as well, adding one to its reference count. However, for non-sharable pages a new physical page node is created (which could be on swap or disk, or could be nil for demand paging).

Yes, prolaries are contexts containing executable substance. They can have threads spawned within them or be RPC'd be some other context.

The design of this is so that entire prolary contexts can be mounted, producing empty copies of private data where necessary while still sharing the storage of the code and shared data.

A subset operation of mounting is therefore sharing a single page or group of pages.

When expanding this notion from just the virtual memory code to context code, mounting will probably involve linking in new symbols, as well. Thus, to mount a context is to map its code and public data within a new address space, and get access to exported symbols.

Though you make a point to say it could be reduced to page sharing with symbol work built on top of it. I think the main advantage of this approach is that pages can be protected from being shared within an otherwise sharable tree. Of course, I haven't seen a reference implementation of shared memory, so there very likely is a better way to share code and data.

About the threads and stacks.... Each thread could have its own stacks that would be mapped in the context that thread is currently tied to, probably at some special section of address space to make this extra neat. When a thread wants to migrate it can do so into any context that's already mounted in the current context. In order to do this it must either 1. Have its eip within that context or 2. Specify an entry point into the new context. Assuming threads aren't suicidal and don't wish to throw themselves into Random EIP Hell, they would probably switch to the entry of some kind of known function. To migrate, the stack pages are remapped into the target context, and the eip changed (accounting at a kernel level for where the new context is mapped in the old and new address spaces). Since stack storage was kept seperate, the only erroneous code at this point would be that which sets a pointer to a stack-allocated variable. Thus the new esp could be set and the thread scheduled under its new context. I assume, of course, that programmers are reasonably able to write code that can context migrate without using any pointers to stack variables. Even though they usually can, I'm starting to wonder if that's a safe operation...

Just a question, but what would happen if a program made a reference to an imported symbol that had been left undefined at runtime? Specifically, would it trigger some kind of trap to the operating system that the kernel could use to throw an exception back at the process?

While I have fond memories of admiring the way COM worked (when it worked), I personally don't like the idea of 128-bit long GUIDs that have to be "signed up" with the system. It reeks of keeping a Registry. I know this much: To access the services of a prolary, you must specify its cid (context id, just like a process id but again, seperate from what's actually executing in it) to a system call. I'd like threads to be able to ask for a list of exported symbols in one fell swoop (lots of code to dlsym() a VFS interface)... So really, a GUID type thing is fine... Combine some kind of say... name-type string with a CID and it'd probably be reasonably unique. What I'm wondering is how to tie that IID (interface ID) to an actual set of exported symbols. I'm reading the COM system calls, and the whole thing just seems way clunky and bloated. Hell, I still can't figure out how Windoze is supposed to know what an interface really contains! Ideally, I want a way to contain the information about interfaces in the executable file, which right now means in an ELF file. If a special sort of symbol could be exported containing a list of symbol names to associate with an interface name... But not all languages (particularly not Pascal) support exporting/importing data. However, a standardly named function could be implemented to return such a structure...

Here's more ideas, and sorry for the core dump.

JoeKayzA, that stuff in interface handles is kind of wierd. Aren't those really just capabilities of a sort that access a given interface? Though I do like the idea of letting every object implement its own security protections once an interface has been obtained.

[Pype.Clicker]

i've not yet gone through the whole thread (only the first post), and i must admit i don't exactly see how your "executable contexts" actually differ from the definition of 'process' in a multithreaded system. Okay they are not like old singlethreaded unix process, nor like the linux process (which basically has no consistent shape).

But how does it differ from "a process is an program under execution that contains the threads, and that defines a way to rule them all" ?

Also, aren't your "prolaries" simply server processes ? or am i missing something very important such as moving from AS to AS, etc. Honnestly, i feels like your ideas would be better expressed if illustrated by some examples (yeah, i know: i always need figures to get things correctly).

That sounds interresting, however.

[JoeKayzA]

The design of this is so that entire prolary contexts can be mounted, producing empty copies of private data where necessary while still sharing the storage of the code and shared data.

I suspect I still haven't fully understood how you would actually handle prolaries, as pype mentioned, a figure would really be fine . So, does _every_ running (or loaded) prolary get its own address space, or is it mapped into other address spaces? That's the important point, I think.

JoeKayzA, that stuff in interface handles is kind of wierd. Aren't those really just capabilities of a sort that access a given interface? Though I do like the idea of letting every object implement its own security protections once an interface has been obtained.

At kernel level, they are nothing more than entrypoint capabilies, indeed. Everything that has to do with interface handling - choosing a method, marshalling and passing the parameters - will be declared by the rpc-protocol, which is implemented in user space, at both the client and server side, probably in language-specific helper and stub libraries. Note that the system core itself (the kernel) probably doesn't know about interface IDs, class IDs and the like, it just routes RPCs, and manages lists of access capabilities for each process. The only big difference to the common component systems is that these RPCs can also go into kernel space, and that they form the foundation of the system.

I made up my mind about migrating threads a bit. The concept has one big advantage: It resembles the logical flow of control much better than the current workerthread models. So when a thread calls a procedure in another process (another address space), it more or less continues running in the destination address space, under the same id, with the same timeslice (this one is important!) and the same priority settings, unless something else is explicitly set.

The big problem is, however, that a new stack has to be allocated in the destination AS, and that the old stack has to be preserved in the caller AS, as well as the old eip.

Therefore, we might consider seperating the 'thread'-object again - into a process specific, and an independent part, let's call them 'thread slots' (that belong to a specific process) and 'thread schedules' (that are independent). An empty thread slot consists of nothing more than a stack. In order to turn it into a running thread, we also need a thread schedule, associate these two and initialize them with an entry point, and we have a thread.

For thread migration, we also need another object type, the entrypoints, which are exposed by a process. An entrypoint can be offered to another process and points to the address of a function in the owner process. In addition, it also gets a couple of idle thread slots, and thus a set of pre-allocated stacks. When a thread migrates from process A to process B, for example, the thread slot in process A will hold the old stack top, eip, and the entrypoint that the thread migrated to. One of the idle thread slots from process B will get associated with the thread's schedule, initialized with the entrypoint's address as eip, and already has a new and valid stack for that process' address space.

I hope that wasn't too fast or too much . Also, I don't know if you couldn't achieve the same results with a synchronous RPC system, when the peers are smartly implemented, mainly efficient caching of worker threads, as well as preserving/passing timeslices and scheduling settings during messaging. The point is that you still have to allocate a set of thread slots for the stacks on the server side, and somehow, you could see those thread slots pretty much like full worker threads....Comments/Critics welcome!

cheers Joe

[Crazed123]

i've not yet gone through the whole thread (only the first post), and i must admit i don't exactly see how your "executable contexts" actually differ from the definition of 'process' in a multithreaded system. Okay they are not like old singlethreaded unix process, nor like the linux process (which basically has no consistent shape).

But how does it differ from "a process is an program under execution that contains the threads, and that defines a way to rule them all" ?

Also, aren't your "prolaries" simply server processes ? or am i missing something very important such as moving from AS to AS, etc. Honnestly, i feels like your ideas would be better expressed if illustrated by some examples (yeah, i know: i always need figures to get things correctly).

That sounds interresting, however.

The main difference between a context and a process (with any number of threads > 0) is that it can have 0 threads if needed and doesn't necessarily have to define or export a main() function. Also, depending on how this is designed a context may not even know which threads are running in it. Plus, I think that having contexts without threads as a primitive works better in a system where threads can migrate, because if a context's only thread migrates away, it isn't necessarily good to destroy it. There would probably be a reference count or something like one telling the number of threads using this context + the number of places it's mounted. When that count hits zero, THEN destroy the context.

Prolaries aren't server processes, because they don't isolate in a single address space. Instead, they get their context mounted into a new address space and are linked in similar to libraries with an interface model. Hence calling them prolaries. The main difference is that a call to a prolary doesn't need to be marshalled. Parameters are just placed on the stack, which is in turn accessed by the callee to perform the task required of it. When the call is finished, parameters are cleaned from the stack.

A prolary is position independent code. This is how they can be loaded into other address spaces at any location. Also, by allowing data pages to be marked sharable or non-sharable a flag could be implemented for context creation determining if a prolary has one copy of data that all callers get access to or if new copies of its data section are created for each context that mounts it. For a prolary with a thread in it, this would still leave the original data section with the original context that the thread is using.

I suppose you could call a context a process that doesn't need to have ANY threads in it, but wouldn't that just be slightly more confusing to everyone who thinks processes always have at least one thread?

Joe, my brain is sorting through what you wrote.

[proxy]

yea i think i see what you mean now, but one thing. In my experience, I was never under the impression that a process HAD to have a thread to be defined as a process. Like I said, the way i learned it and have always viewed it is that a process is just an address space with the needed information to manage that space, nothing more. The threads provide the stream of execution.

so for example, in my OS at the kernel level, creating a process has nothing to do with threads at all.

i end up doing something like this:

Code: Select all

Process *const proc = new Process;
proc->mapPage(addr1, PageManager::instance()->acquire());
proc->copyToProccess(addr1, code, size);
new UserThread(proc, addr, "test", 0);

so a process can exist with no threads associated with it...in fact, just for orthogonality my kernel fits the decription of a process with no thread (since all processes get the kernel mapped into it...all it has is kernel pages in it).

personally I feel this is a very flexible model in general since it is trivial to have small wrapper functions to do things like create a process with one thread in it based on these primitives I've established.

proxy

[Crazed123]

Yeah, that's pretty much what it's like. I just don't call it a process because it doesn't process anything without a thread.

Reading up on ELF and symbol tables...

Had this idea about interfaces. They could be integrated with how an executable is linked and loaded at runtime so that every external reference is by default mapped to a certain region of address space. This region is never mapped with any data, and always marked as not-present. That way, if a reference to that region is ever made and a page fault triggers the system can know that that's a bad import reference rather than an ordinary page fault and give the faulting context/thread a signal telling it so. When an interface is found correctly and imported at runtime, the kernel can go through an internal table of imports filling in each one defined by that interface, unless of course it is already defined from somewhere else, which causes an error. This way the user programs never have to deal with an object or interface model. All they see is submitting an Interface ID to another context asking whether it's supported, and calling the kernel to import that interface if it is.

Lots of ELF reading to do.

The thing about keeping RPC accounting in the kernel without the kernel knowing about IIDs and all of that sounds fine to me for some situations where there's a standard way to ask for interfaces. I think that I'll probably just have one system call to ask a target context if it supports a given IID, and the kernel will define a standard Ask() function that everyone must export in order to be loaded. Though if it's a standard, then you could actually link it by default and call it from userspace... Yeah, Ask() will be a standard call that can be used to ask if an IID is valid, and then a kernel call like say... Import() can be used to actually link it.

Though in light of wanting to use security features I'd make it both Ask() and Import() kernel calls. Instead of a user level Ask() I'd go with my old idea of a Permit() function that the kernel would call to make a capability. It could perform the encryption necessary after the kernel does its security checks, and could take a flag determining whether it was making a new capability or checking an old one. When a running thread tries to Import() a context, the kernel takes the capability as a parameter to Import() and calls Permit() again to check it. If it's valid, the kernel performs the import. This would work on a per-interface basis.

I'm still wondering how a prolary could group functions and data together into interfaces together for export. That is, who is going to define what functions and data an IID refers to, and where are they doing it?

About the migrating threads, I really just think that a thread carries around its OWN VMM nodes that represent a stack and get mapped into every context in a small section reserved for stacks. Then the thread's esp pointer is set to the new virtual location and things are good to go. This design confines threads to stay within whichever protection level they were created in, but I view that as a benefit. I think it's more secure to tell threads they can't migrate into kernel (or device driver) space at all than to tell them they need the right capability. After all, how to determine which threads to grant the capabilities to? So each thread gets its own stack pages and can migrate among contexts of its protection level. Yay.

Sorry I forgot all about it, but I'll finally define a prolary. A prolary is a unit of code and data that sits in its very own context. It can export functions and data, own threads if they're given entry points and contain global data.

The idea of sharing contexts (I've renamed it under the KISS principle) is that if a VMM node is encountered that isn't marked as sharable its virtual mapping will be copied, but new physical storage will be allocated for it.

Another core dump, it seems...

[JoeKayzA]

*reading*

Hmm, about component/interface management: Interesting ideas, it's actually combining interfaces with our dynamic linking techniques today. Mind however, that dynamic linking and symbol resolution do _not_ neccessarily have to be placed at kernel level, they can perfectly well (and often are) done in user space. So you could do all the negotiation about an interface, whether it is supported and the like without the kernel's help, and then, when you finally got hold of it, let your code link those open symbols appropriately.

But there is one thing left I haven't yet got: When symbols reside in a seperate address space, how do you want to link them in? I think you can't link them directly, you would have to generate a set of stub functions (or at least some extended hunks), that then do the rpc neccessary. The point is that a linked symbol (for a procedure) can only be used for 'call' instructions, and these need the entry point be present in the current address space.

All the interface handling code, as well as the dynamic linking code could then go into a helper library. Sorry, I know that opinions can differ, but that's just the way my brain would design it.

About migrating threads: Are you sure that you need all those stack pages everytime a thread migrates? I mean, the stack is normally used as a call history (return addresses) as well as for local storage, but a function normally does not touch any variables that reside outside of its own stack frame, since these belong to the previos, the caller function. Another worry is that, at least in my C programming style, the stack variables hardly contain much data - everything larger than integer-size is placed in the heap. So you would have to map these heap-regions too, when a migrating thread passes larger amounts of data. At least, a thread could not migrate without explicitly knowing that this one specific call issues a migration - it has to prepare for this event (placing the arguments in the right locations, record where it came from and where it will go to...).

About the migrating threads, I really just think that a thread carries around its OWN VMM nodes that represent a stack and get mapped into every context in a small section reserved for stacks.

That's exactly why I was so worried about mapping _all_ the stack space when a thread migrates: A 'small' region of virtual memory would probably not suffice. Imagine a thread that migrates over several execution contexts would probably need a stack of more than 1 MB, of which in the current execution context, only the top most, say, 4 pages would ever be touched.

Analysis of your core dump

cheers Joe

[Pype.Clicker]

okay, so if i try to draw a parallel with something closer to the "real world" (oh, actually, RPG games), the "context" are somehow rooms. They contain stuff (code to be executed, data that 'belong' to the room), but there's noone there.

Instead, "threads" are much like players: they carry their own goods (their 'private heap') with them in every room they travel. Of course they have their own stack and code too (/dev/mind) ... When a thread enters a room, it can interact with objects in that room (run code, operate on data), and possibly talk to other players.

(still trying to find an appropriate image of prolaries ...)

...
but a function normally does not touch any variables that reside outside of its own stack frame, since these belong to the previos, the caller function. Another worry is that, at least in my C programming style, the stack variables hardly contain much data - everything larger than integer-size is placed in the heap.

That's *very* specific to your programming style, which looks more like Java style, actually. Other people doing C might have local string arrays on the stack and pass the reference of that to the called function, etc.

Sorry I forgot all about it, but I'll finally define a prolary. A prolary is a unit of code and data that sits in its very own context. It can export functions and data, own threads if they're given entry points and contain global data.

So somehow a prolary looks like an NPC that runs a business: inns, weapon shops, goodies shops, etc. The 'non-playing characters' there (e.g. the prolary's thread's) can interact with "player" threads, but it also "protects" some stuff (e.g. items to be bought cannot be manipulated directly) though it can give you hint (item price, etc.) and operate them for you (want a demonstration of how those bombs work ? ...) before they finally deliver the object to you.

Hm. Hope that doesn't sound too childish to talk about your design like that.

And still using the same idea, you create villages, dungeons, etc. by "mounting" rooms in a certain order ... So that you (as the game architect) create more complex environments by defining relationships among pre-configured smaller environments.

[JoeKayzA]

That's *very* specific to your programming style, which looks more like Java style, actually. Other people doing C might have local string arrays on the stack and pass the reference of that to the called function, etc.

That is very likely to be the case, since I've done my first serious programming projects in Java. But in the C++ course I recently attended, we were also adviced to put larger objects (and strings belong to that category too) onto the heap, mainly because many application platforms around offer rather limited stack space, so unneccessary stack space consumption should be avoided when possible.

*gg* you seem to have a talent for making theories 'visible' . Probably a very useful attitude. Are you an artist?

Instead, "threads" are much like players: they carry their own goods (their 'private heap') with them in every room they travel. Of course they have their own stack and code too (/dev/mind) ... When a thread enters a room, it can interact with objects in that room (run code, operate on data), and possibly talk to other players.

So you mean it could really be useful to carry _all_ the stack with you, in every room you are in? The reason why I seem to have problems with this thought is that, for me, stack frames always belong to a specific function - and when you left the room where this function lives, it won't be neccessary any more - you could leave it there. But I might be wrong - remember, I'm influenced by evil Java .

However, I very much like the idea of carrying your private heap with you! That would resolve quite a lot of quirks with passing arguments during thread migration.

cheers Joe

[proxy]

But in the C++ course I recently attended, we were also adviced to put larger objects (and strings belong to that category too) onto the heap, mainly because many application platforms around offer rather limited stack space, so unneccessary stack space consumption should be avoided when possible.

i certainly hope that they weren't refering to std::string as in the primary string class in c++. Because in all but the small string cases, even if you put the std::string object on the stack, the actual character array it is abstracting will certainly go on the heap. This goes for just about every container in the standard library. Notice how they all have an "allocator" variable which defaults to the standard allocator when you don't specify it? Well, that allocation uses new/delete....heap.

proxy

[JoeKayzA]

No, the talk was only about the C-style string, the typical char-array.

cheers Joe