Security

Could a thread manipulate its own spReg to allow it to make calls without overflowing the stack, BUT overflowing the state in the spiller?

Not unless it had rights to the MMIO register that shadows spReg, and if it has rights like that then it’s part of the OS and better know what it is doing. spReg (and nearly all the specRegs) are not user-assignable except via MMIO. Ofg course, they change all the time as a side effect of executed operations like call, but not directly.

Could a thread do a grant in a loop, generating regions until something breaks? It sounds like the OS won’t get a chance to stop it until PLB eviction occurs. Also, if it’s on a family member which does it in hardware, that removes the OSs ability to regulate a rogue process.

The grant quantum, while set by policy, is managed by hardware and will throw a fault if exceeded. We didn’t want to track it at evict time in case we have members that do evicts (with PLB entry creation) in hardware.

If sounds like if a thread fills the region table with regions overlapping one address, the augmented interval tree will handle it happily (ignoring the previous question), however what if the PLB is (mostly) full of regions that all overlap an address, which a thread then accesses? Would it need to hit an excessive amount of regions in the cache to resolve the final permission set?

The region table is searched until the first entry that would give permission is found. Entries are not concatenated during the search; permission for the whole access must be provided by a single entry. That keeps the search cost manageable; if you really need to have an access that is part permitted in different entries then you must use a service that will push a new grant covering the union of your existing entries.

On the topic of overlapping regions, I assume it’s an OR of the permissions, not an AND?

Any single entry is satisfied if all of the region, thread, turf and rights match.

Does the iPLB ignore read permissions? (ie, can code be execute, non-read)

The iPLB is used only for execute access, and its entries need only distinguish eXecute from Portal. Similarly the dPLB is used only for load and store, and need only have Read and Write permission bits. Table entries have all the bits so as to reduce the number of entries.

• This reply was modified 10 years, 8 months ago by  Ivan Godard.

Yes, you can use the stack to pass arguments between frames.

You may also use the heap. And how you do it depends a lot on whether you make a distinction between objects and primitives, and how you do garbage collection.

Normal calls within a compilation unit are very conventional and all the normal approaches work; its only if you want to take advantage of the Mill protection mechanism or its convenient for dynamic linking that you use portals.

A bit more – while you can use your convention-of-choice to pass arguments in memory, passing them in the belt will be much faster, with a performance difference roughly equal to the difference between passing in registers vs. memory on a legacy architecture. So I’d expect performance-oriented Lisp/JS implementations to use the belt when they can, and restrict the always-varargs approach to blind calls when they can’t optimize.

We are working on a reference port of Linux/L4 (https://en.wikipedia.org/wiki/L4_microkernel). Other implementers will have their own approach; Windows on a Mill is an interesting idea 🙂

Turfs, threads, and portals (other than the first, created by the hardware) are built by trusted services, principally the loader. The critical steps include allocating turf and thread ids and blessing a hunk of address spaces with the Portal permission. Family members vary in the hardware help for these steps, but all unsafe parts of the work are done via MMIO, so only those with rights to the relevant MMIO regions can do it.

The software that does these steps will presumably have some notion of quantum, to prevent “portal bombs” such as you suggest. However, that’s all policy, and so not defined by the Mill architecture.

We have had no problem mapping Mill security to the C API. The general strategy is to use a user-space shim that is linked right into the app. The app calls the shim, and the shim does the portal call, any necessary passing of arguments, and so on. However, we are far from done with the work and may find a gotcha as we get further. If so we’ll deal with it then.

Callbacks are handled much like linking of dynamic libraries (.so files). hen you link to a dynlib on a conventional system, the app must itself export its callback entry points so the linker can fix up the calls in the library just like it fixes up the calls in the all to point to the entry points in the library; thgis is a fairly sophisticated use of the linker, but well known and quite routine.

On a Mill you do the same thing, only the exported entries are made into portal by the loader, rather than rewriting the code addresses. However, if you are a JIT so the entry address isn’t known at load time then the entry portals (in either direction) must point to trampoline code at fixed addresses, where the trampoline indirects to the moveable entry point. It costs one more cycle in and out, so no buig deal.

There’s currently no way to grants something unless you have the same access yourself. It’s doable – another permission bit – but we have no use case that needs it.

Ivan

• This reply was modified 10 years, 8 months ago by  Ivan Godard.

Neither threads nor turfs are processes in the Unix sense, so pid_t can remain unchanged. A Unix process can be seen as an initial thread residing in a new turf, but you can have turfs without threads on the Mill, which is not possible on Unix because there is no way to have an isolated load module that is a pure service.

Stack segments can be arbitrary sized, subject to OS enforced quanta per usual. The info block describes the top segment of the segmented stack. A new service call (not a callback) will always use the reserved stacklet, but it initially has no data frame (spiller has a frame of course). Creating a frame is a distinct Mill operation stackf, which carries a size in bytes. If that exceeds the current limit then the hardware traps to a handler (which would ordinarily be a portal to a service) that runs out and allocates enough space for another segment, fixes up the links and the frame and stack pointer registers, and updates the info block. The handler enforces whatever quantum policy is desired. The alloca operation can also trigger stack overflow, with similar handling.

Subsequent callbacks will use the new segment. An exit followed by a new call can be optimized if the handler keeps a previous, now empty, segment around to avoid allocate/deallocate overhead when call/returns are bouncing over a segment boundary.

Hi rpjohnst,

For low-level hardware things I’ll leave that to Ivan or someone else formally of Mill Computing.

However, for all hardware Linux runs on, memory management, pids/threads and the like are also an abstraction. Where there’s more required than hardware provides, you’d never see a difference in code, as that’s also abstracted: that sort of thing is handled the same way virtual memory is. That a pid is 32 bits is purely a housekeeping detail that is convenient for the software, and has no connection with the hardware it runs on or its limitations. All those tables can be swapped out as needed by the OS to handle as many as desired.

And, seriously: I’d be shocked if there’s a single CPU with any number of cores that Linux runs on that you’ll find 2^22 threads/processes in-use at any given time 😉

The Mill does good with a lot of things 🙂

Seriously, while we know that we will do a reference microkernel, the decision of which extant system to build on must wait until the new compiler is up enough to take the load, which won’t be for a while yet. It also depends on who we find as partners in the effort; if a grad student at University A gets fired up about porting system X to the Mill then we will arrange access to our tools and simulators and, eventually, hardware. We’ll also support ports by B of Y, C of Z and so on; may the best and fastest win. The Mill is intended to be policy-agnostic, so the more different systems that get ported the more confident we are in the hardware model provided. As research ports come out, we will be working to make one or another be commercial grade, or driving a merger of the most successful ideas of several.

But all that waits on the tool chain for now.

Actually there is hardware virtual memory on the Mill, and paging and all the rest, and the virtual-to-physical translation, page traps and so on take place in the TLB in a quite ordinary way. It’s just that the TLB is in an unusual place in the architecture, after rather than before the caches as seen from the core, and protection is divorced from paging and moved to a different unit.

Well, that’s not quite true: there are some extras in the Mill MMU: virtual zero (described in the talk), and some NYF dealing with Unix fork(). But it’s mostly true.

As for embedded work, the problem with a smaller address space footprint is aliasing. If an embedded application had sufficiently small address space needs that everything would fit in 32 bits with no memory mapping/aliasing the the Mill single-address-space model would work; it would be a full normal Mill with an implied (and ot represented) zero in the high-order word of pointers. Note that you would still want a PLB. Whether the market for a 32-bit-no-MMU Mill is big enough to justify the work is unknown.

Which brings me to your market questions. The Mill innovations tend to interlock righter tightly, so it is difficult to pull just one out and apply it to some other architecture. For example, you could pull Mill split-stream encoding out and apply it to a VLIW to be able to decode 30 ops per cycle like the Mill does. But without things like the Belt in the execution engine you wouldn’t be able to execute all the ops you decoded. And so on. We’re not opposed to licensing, and would take NRE contracts to port some of the ideas to other machines, but we see the opportunities as being rather limited. We feel that more likely we will sell hard macros of full Mills into SOCs.

In contrast, we are actively interested in partners for the Mill itself. We know that large buyers will demand second-source availability, which means a license/partner. In addition there are specialized markets – rad-hardened, for example – where the existing vendors have expertise we will never have and a license seems the way to go. It’s the usual business story though – nobody wants to be the first to stick their neck out about a new architecture, but as soon as one bites everybody will be at our door.

To which we will say: we are not an ARM with a license-based business model, so it’s going to be first-come-first-served.

Please distinguish alias mapping from paging. 32-bits systems don’t have enough address-space bits, so they have to reuse addresses; this is mapping,. In addition, physical pages may be present or not. For efficiency, conventional systems combine the mapping task and the paging task in one MMU/TLB machine.

With a 60-bit space the Mill has no need for mapping; there’s all the virtual space that everybody wants there for the taking. However, virtual space may still exceed physical DRAM, so there remains a need for paging, and the Mill does paging.

The paging is done in the TLB and its associated OS tables. Those are only looked at when we miss in cache and have to go to memory, and they tell where in physical memory a given virtual page is located, just as on a conventional machine. Or not located, if the page is swapped out to disk. So a Mill can still get page traps.

Mill code is position-independent (PIC), but jump table and the like have full-width pointers with virtual addresses where the code has been mapped. The underlying DRAM may be swapped out and paged back in at a different physical address, but the virtual address remains the same and the pointers still work.

Re MMU use by garbage collectors:

One certainly could use Mill protection for this purpose, but there’s a better way.

Mill protection has byte granularity, so the GC would need only one region descriptor for the whole of any one kind of space. In a generational GC for example, you might use one descriptor per generation (typical GCs use three generations). This would be an easy port, just replacing the small amount of code that manages the page tables with similar code that manages the region descriptors.

However, there’s a better way, one that uses the GC support “event bits” in the pointer format. With these, the GC can work at the granularity of single objects rather than pages or regions, and would be expected to have sharply reduced overheads. Porting a GC to use these would probably be a bit more work, because the model changes and that requires a bit of thought. The actual code changes should be near trivial though, mostly involving taking stuff out.

Re JITs and member-specific code:

JITs will generate member-independent code and call an API to get that code specialized for the actual target.

Thanks for the answer. Based on the Security talk that’s what I expected.

I can imagine all kinds of novel uses for the “protection environment switch via portal” (i.e. essentially a double function-call sans prediction). “Green” thread implementations will rock on the Mill, as will simple system calls. Simply elegant.

Very good! Yes, you can see the Novel bit as implementing a writeback cache, and deferred table update (described as “lazy” in the talk) works as you suggest.

As for the missed question (with my hearing I miss quite a few), the “next call” is for explicit calls, not for interrupts, traps, or faults. The pending grant(s) are state. We once had a way to push them in the PLB and fix them later, but there were issues if they got evicted before the call, so it’s just spiller-food now.

A region descriptor cannot have both execute and portal permission, but you could create two overlapping descriptors. Which you got would be search happenstance. If you wound up looking at a portal block as code then you would not transit and would be due for an invalidInstruction fault Real Soon Now. If you wound up looking at code as a portal, and by accident you happened to pass the security check by satisfying the ids that the bits in the id fields implied, then you would transit to the turf implied by the bits in the turf field, and then try to jump to the address implied by the bits in the target field. That address would have to have execute permission, and be in fact the address of an EBB entry (or you are up for invalidInstruction again) and probably must be the address of the entry of a function with no arguments or you are up for invalidOperand because the belt contents wouldn’t match what the code expects.

So, if the OS portal-bless service screws up and does overlap two descriptors, and the bitsies are just exactly right, then you can call a function in a random service. That’s why portal-bless is in the kernel.

As for distinguishing portal from non-portal calls, the basic reason is uniformity. We wanted a single pointer representation, one you could pass on to code that did not know whether it’s a portal or not. Consider a numeric integration package, which takes a data vector and a pointer to the function to integrate. The integrator should work the same whether the function pointer is to an application function, or a portal pointer to something in a math service.

First class hardware random number generators aren’t difficult. The old Atari systems C. 1980 had them. But I don’t see them as a core feature of CPU hardware. An opcode in the generic code representation wouldn’t hurt, with an option for the generator as a specialty register.

We have not put hardware encryption into the base Mill, because we expect encryption methods to change over the life of the architecture and don’t want to be saddled with outdated legacy requirements.

That said, the Mill has enough horsepower to do a reasonable software crypto. For application that want more, the Mill defines an extension interface to which things like crypto and other specialized engines can be hooked. The interface makes the engine look like an i/o device from the program using it.

We have also considered supporting a physical seed unit. Such units give only a few bits of entropy and so cannot themselves be used for crypto, but the provide an uncrackable seed for regular algorithms. The decision on that has been deferred until after the FPGA version.

If the Mill doesn’t have some other solution I think you could roll your own protocol using regions to allow the service to be sure who is calling the portal. Have the portal put a random value only readable by the desired calling thread into memory. When the calling thread wants to make the portal call, it passes the number provided by the service that only it knows, and the service then verifies that the caller’s number is equal to its, and then sets its number to a new random value in anticipation of the next call. Critically when the check fails the service needs to sleep for a period or fault or cause the caller to fault somehow, and pick a new random value for the next challenge, otherwise the caller can brute force retry. Random numbers need to be used rather than just an incrementing counter, because otherwise a malicious thread can guess the current value from information like how long the system has been running or how many times the service has likely been invoked.

Edit: this scheme assumes the calling thread is not ‘in cahoots’ with a malicious thread and thus won’t deliberately share the random value with it. But since the Mill protection model is that threads with a given permission can always grant other threads a subset of their permissions, I think this is OK.

• This reply was modified 10 years, 7 months ago by  joseph.h.garvin. Reason: simplified scheme considerably
• This reply was modified 10 years, 7 months ago by  joseph.h.garvin.

As suggested by the comments above, the thread id is unchanged through a portal call – it’s the same thread, just running in another protection environment. The current thread id is a readable specReg, so the service can know who it is working for. From that it can find more info in data structures it or other services maintain.

However, it also can keep client-specific info in Thread Local Storage. Each client/service combination has its own TLS just like it has its own stacklet, addressed by a hardware base register like the hardware frame pointer.

Speaking of operating systems, while it has gotten on in years I think AmigaOS would be a great fit. If I recall everything correctly, it already assumes a flat memory model, uses by-reference IPC data passing, and OS calls are normal function calls. Memory allocation requires protection descriptions as to how they’ll be shared.

I don’t know how much of this has changed in AmigaOS 4, but the assumptions made for simplicity and speed back then would gave great alignment with how the Mill accelerates and secures those assumptions.

1) Bottom stacklets are fixed size. Stack overflow (which can happen on the very first frame if it’s big enough) pushes a grant of the occupied part of the overflowing segment, allocates a bigger (policy) stack segment somewhere, and sets the various specRegs to describe it and thereby grant permission. Return unwinds. Unwind is lazy so you don’t get ping-ponging segments if you are real close to a segment boundary.

2) I doubt that the search hardware would be exposed. To specialized, and will vary by member so not portable.

3) I looked at the exokernel work. So far as I can see “exokernel” is just marketese for “microkernel” plus libraries. The libs would be services on a Mill, but otherwise I haven’t seen anything that novel compared to prior work in microkernels and capability architectures. Please point out anything I have missed.

The TLB supports scaled sizes, as many modern TLBs do, but is unusual in that the smallest size is one line rather than 4KB. However, one-line pages exist to permit on-th-fly allocation of backing DRAM when a dirty line is evicted from the last-level cache. The one-line pages are scavenged by a system process and consolidated into more conventionally-sized pages. If scavenging were not done then the number of one-line entries would grow to the point that the underlying page tables would occupy most of physical memory, which is rather pointless.

There’s another difference between the PLB and the TLB structure: while the granularity of pages in the TLB varies, it is always a multiple of lines, whereas the PLB has byte granularity. Consequently you can protect a single byte (which is actually done, for example to protect an MMIO register for a device), but you can’t page one to disk.

Moving on to your suggestion to use the TLB for checking for use-after-free. A crawling allocation only works if it has a crawling free, or you wind up with internal fragmentation and, again, a lot of tracking entries and poor performance. If you do have a crawling free, for example if you are using a copying garbage collector, then it becomes possible to protect the freed region. However, the TLB is probably not the right place to do it. That’s because on the Mill there is not necessarily any memory backing the address space – at all. Backless memory lets data have an existence only in cache, and is a significant performance win for transient data. The problem is that the hardware does not know that the software considered the data to be free, so if it is dirty (which it necessarily will be), it will eventually age out of cache, be evicted, and have physical DRAM allocated for it, all pointlessly.

The hardware handles the case of transient data in the stack, because allocated frames are automatically freed on return, and the whole call/return protocol is built into the hardware so the hardware knows to discard the lines covering the exited frame. For random memory it doesn’t know about free unless the software tells it.

The good news is that the software is able to tell it. There are several cache management operations in the Mill that let software convey useful information to the cache. One of those operations tells it that an address range is dead, and lines covering that range can be discarded, nominally dirty or not. However, these ops do not recover allocated backing DRAM if it exists, because tracking DRAM is too complex for hardware and the OS must get involved.

And here’s where the TLB gets back in the act. Once the crawling free has freed a whole page, and discarded the lines in cache, it is possible to remap the page in the TLB from physical memory to an error trap. There’s your use-after-free case. However, I don’t think that it is quite what you were hoping for, because it doesn’t protect free spaces in fragmented memory, and it only protects a page granularity. Hence there’s a window of vulnerability while waiting for a partially free page to become wholly free.

I’m not sure I have answered your question in this; feel free to expand or refine it here.

Your understanding is correct.

There are further subtleties that make me say “like an i/o device”. For testing, programs often need to have repeatable random number sequences, so that it is important that a program be able to glom onto a RNG and take all the numbers generated, without some other thread or process grabbing one in the middle of the sequence. That is, the RNG needs to be (able to be) single-user exclusive use. Most of the other bulk-algorithm hardware has the same characteristic: you don’t want someone else getting the result of the MD4 that you started, and so on.

This exclusive use capability is characteristic of many i/o devices. Even those we often think of as having multiple concurrent users (a disk for example) actually has only one user (the driver) when you look closely at the hardware.

In contrast, operations are usable by all, and the hardware does the save-restore that gives the illusion that everybody has their own belt. It is impractical for hardware to provide the illusion that everyone has their own RNG. So the Mill provides an interface that supports exclusive use (using MMIO and the standard memory protection system) and asynchronous (or semi-synchronous) access.

You assume correctly; you can pass any subset of the rights you have, and the “r” is explicitly not passing “w”.

About the arena: the concern is, if the arena is passed with “w” rights and contains both data and administration (which is the way many heaps are organized) the the recipient can tromp on the administration. However, if the administration is disjoint from the contained data (which is the way some heaps are organized) then only the data and not the administration is exposed. Of course, if the callee needs to add or remove nodes in the arena, the latter approach would require also giving the callee portals to the client routines that do the arena malloc and free, because the service would not be able to play with the administration directly itself.

It’s clear that the Mill primitives can be used in many different ways to support many different models, and we expect the users and the field as a whole to spend happy hours exploring the possibilities and discovering what policies and protocols provide the best of both function and performance. Have fun 🙂

There is considerable member-dependent variation possible in the formats of these things, and there are probably variations that we haven’t thought of yet that will be used some day. Consequently you should see this answer as representative rather than graven.

ID sizes (turf, task) are member dependent. The most important constraint on their sizes is that the product of a task and a turf is used as the implicit address to locate the root stacklet in a portal call, and hence must fit together in a virtual address (60 bits) together with a stacklet size and enough bits for non-stacklet memory as well. All these bit fields are per-member fixed, and the member designer can increase one only by shrinking another. A representative number might be 23 bits each for turf and task ids.

We don’t seem to be constrained by the size of a portal data structure, although I suspect that when we implement that part of an OS that we’ll find we want to put more, or more kinds or, data in the portal than we have now thought of. There is some need for the access to be power-of-two sized and aligned, and for hardware reasons it will probably be a multiple of the vector size even if we don’t need the bits.

In general, such member-specific details are of interest only to the OS and will sit behind a member-independent API.

The IDs are unforgeable not because they are unguessable but because they are managed by hardware.