WASM and ocaps

[Mark Miller]

At the latest wasm (Web Assembly) standards meeting, I pointed out that wasm is already an OS-like ocap system: A wasm instance, with its linear data space + table of opaque external functions/objects is already a process-granularity-like unit of isolation with an address space and a clist. A wasm computation addresses its clist entries by clist index as expected. In addition, wasm currently obeys the following restriction.

> WebAssembly instances must never be able to cause effects other than by wielding explicitly granted access (e.g. the importObject in a JS embedding).

According to Andreas Rossberg (cc'ed), this is on purpose, even though the people in the room at the time did not seem to know that. I suggested that it be made normative, so security uses of this restriction would not be compromised by later "enhancements" that accidentally break this unarticulated restriction.

https://github.com/WebAssembly/meetings/issues/104

is the one to watch. Assuming I do a good job clarifying the agreement we just came to, and assuming the agreement holds in the face of these clarifications, it looks like wasm will explicitly be the object-capability system it was designed to be.

Andreas and Bradley (also cc'ed), please clarify or expand as appropriate. If you don't want to subscribe to these lists, send your posts to me and I will forward. Thanks.

--

  Cheers,
  --MarkM

[Mark Miller]

[Forwarded by request]

On Sat, Nov 4, 2017 at 1:17 AM, Andreas Rossberg <ross...@mpi-sws.org> wrote:

To clarify for the broader crowd, to me this quote about (module) instances just describes an aspect of proper modularity, which naturally consists of two dual properties:

1. A module can only access what it (is given as) imports.
2. A client can only access what a module exports.

Of course, whether this implies an “ocap" system also depends on what exactly “what” quantifiers over. Formally this usually refers to free names or variables or addresses, which of course could still be side-stepped by a language providing ambient capabilities in an unnamed fashion, e.g. as primitive instructions.

Ben Titzer (CC’ed) initially prototyped Wasm that way, and as far as he told me, he consciously decided not to include any such primitives, even though he didn’t frame it as ocap. Given the diversity of environments that Wasm is supposed to be embeddable in that is almost a necessity: there practically is no interesting (non-computational) resource that can be assumed to exist in all possible embeddings, and hence you cannot build any into the language even if you wanted. In particular, Wasm shall neither depend on the web nor JavaScript nor any specific form of OS.

(A minor quibble I have with the quote is formulating the “what” as “effects”, because under the usual semantic interpretation of the term, a Wasm computation can still have observable effects, such as traps, non-determinism, or non-termination. But these (hopefully) are benign effects wrt security considerations.)

/Andreas


I suspect that most people in the room just

--

  Cheers,
  --MarkM

[Mark Miller]

On these lists, sometimes we cross-post when introducing a topic but then announce that further discussion is to continue on one of these lists. For this topic I think the appropriate list is e-lang.

https://groups.google.com/forum/#!forum/e-lang

I will reply to Andreas there.

--

  Cheers,
  --MarkM

[Mark Miller]

On Sat, Nov 4, 2017 at 1:17 AM, Andreas Rossberg <ross...@mpi-sws.org> wrote:

To clarify for the broader crowd, to me this quote about (module) instances just describes an aspect of proper modularity, which naturally consists of two dual properties:

1. A module can only access what it (is given as) imports.
2. A client can only access what a module exports.

 

At the granularity of wasm modules, wasm is still not an ocap system for the very reason that multiple wasm modules within a wasm instance share a linear address space and can step on each other's data freely. This violates your criteria #1.

Also, criteria #1 is insufficient anyway as it admits the module system itself as a global communications channel. Worse, if a module X, i.e., the thing imported, can have mutable state, then two other modules Y and Z can communicate with each other merely by both importing module X.

On your criteria #2, exports to whom? What can import what a given module exports?

Java is a good example of three ocap relevant aspects of module systems --- two of which Java gets wrong and one that Java once got right.

a) By the rules of Java, any module may import java.io.File and proceed to delete all my files. It is not clear to me that this violates your criteria #1 --- the importing module is only "given" what it imports. But it is unconditionally allowed to import the ability to cause external effects. Joe-E's imports whitelist excludes all such effectful modules, and so prevents all such imports.

b) A Java module is a top level class. A top level class can contain static mutable state. Thus, modules Y and Z can communicate by both importing class X, via X's static state. Joe-E prevents all mutable static state.

c) In Java prior to Java 1.2, the import namespace was not global but relative to a ClassLoader. The J-Kernel leveraged this to build an ocap system where the unit of isolation is not an object, class, or top level class, but a ClassLoader together with all the classes it loaded, together with all the instances of those classes. (To enable these to interact without accessing each other's ClassLoaders, the J-Kernel also leveraged RMI to build a full membrane between each of these units.)

Java lost virtue #c as of Java 1.2 when it decided ClassLoaders could no longer override the binding of java.lang.System, which therefore provides ambient access to stdin, stdout, and stderr. The J-Kernel no longer worked starting with Java 1.2

There were several presentations at the recent OCAP 2017 workshop at Splash https://2017.splashcon.org/track/ocap-2017#program that touched on these matters. Specifically, the module systems of Monte and Wyvern follow ocap principles.

Some videos and papers from OCap 2017 coming soon!

For all these reasons, for wasm the unit of isolation is the wasm instance, not the wasm module. A wasm instance is not given what it imports because there is no prior module system that a wasm instance can import from. Rather, each instance is explicitly granted what it is given. Each wasm instance then has its own internal module system which violates ocap rules, but does not compromise the isolation of the instance within which it operates.

Of course, whether this implies an “ocap" system also depends on what exactly “what” quantifiers over. Formally this usually refers to free names or variables or addresses, which of course could still be side-stepped by a language providing ambient capabilities in an unnamed fashion, e.g. as primitive instructions.

Ben Titzer (CC’ed) initially prototyped Wasm that way, and as far as he told me, he consciously decided not to include any such primitives, even though he didn’t frame it as ocap. Given the diversity of environments that Wasm is supposed to be embeddable in that is almost a necessity: there practically is no interesting (non-computational) resource that can be assumed to exist in all possible embeddings, and hence you cannot build any into the language even if you wanted. In particular, Wasm shall neither depend on the web nor JavaScript nor any specific form of OS.

(A minor quibble I have with the quote is formulating the “what” as “effects”, because under the usual semantic interpretation of the term, a Wasm computation can still have observable effects, such as traps, non-determinism, or non-termination. But these (hopefully) are benign effects wrt security considerations.)

These are good points. Not minor quibbles! Historically, when we speak of "causing or sensing effects on the world outside itself" we mean something different, such as mutation of external locations, reading changeable locations, or I/O.

JavaScript's Date.now() is an example of an ocap violation because it enables the sensing of effects from the outside world, even though it does not enable the causing of any outside effects.

By ocap significant effects, I generally do not include exceptions, non-termination, or non-determinism.

Consumption of computational resources are not classically considered effects, and are not generally considered effects by any ocap languages. However, they are treated as capability controlled effects by OSes of the KeyKOS family (KeyKOS, EROS, Coyotos, seL4), which Norm talked about at his OCap 2017 keynote.

The Capabilities and Effects paper at OCap 2017 is also relevant:

http://homepages.ecs.vuw.ac.nz/~alex/files/CraigPotaninGrovesAldrichOCAP2017.pdf

/Andreas


I suspect that most people in the room just

> On Nov 3, 2017, at 22:56 , Mark Miller <eri...@gmail.com> wrote:
>

--

  Cheers,
  --MarkM

[Mark Miller]

Perhaps the more relevant starting point for what should be considered an effect is the criteria used to determine what computations can be done purely by user mode instructions without possibility of kernel intervention. The classic paper is Popek and Goldberg's

Formal Requirements for Virtualizable Third Generation Architectures

https://www.princeton.edu/~rblee/ELE572Papers/Fall04Readings/secureOS/popek_virtualizable.pdf

This includes input, output, causing or sensing external mutation, and resource use. It does not include internal mutation or control transfer, or non-termination per se (as distinct from resource use).

From an OS perspective, I would argue that proper user mode instructions cannot sequentially be non-deterministic, and cannot by themselves spawn threads. However, once threads are spawned, they can obviously interact with each other in non-deterministic ways. Whether this means that non-determinism per se should be considered an effect from this perspective is puzzling.

--

  Cheers,
  --MarkM

[Mark Miller]

I note that user mode instructions also have no builtin notion of import, export, or module name spaces.

--

  Cheers,
  --MarkM

[Mark Miller]

(Forwarding again. Will reply separately.)

---------- Forwarded message ----------
From: Andreas Rossberg <ross...@mpi-sws.org>
Date: Sat, Nov 4, 2017 at 8:23 AM
Subject: Re: WASM and ocaps
To: Mark Miller <eri...@gmail.com>


[Hi Mark, if you could please forward again. :)]

> On Nov 4, 2017, at 13:41 , Mark Miller <eri...@gmail.com> wrote:
>
> On Sat, Nov 4, 2017 at 1:17 AM, Andreas Rossberg <ross...@mpi-sws.org> wrote:
> > To clarify for the broader crowd, to me this quote about (module) instances just describes an aspect of proper modularity, which naturally consists of two dual properties:
> >
> > 1. A module can only access what it (is given as) imports.
> > 2. A client can only access what a module exports.
>
> At the granularity of wasm modules, wasm is still not an ocap system for the very reason that multiple wasm modules within a wasm instance share a linear address space and can step on each other's data freely. This violates your criteria #1.

No, that’s incorrect, there may be a misunderstanding about what an “instance” is in Wasm. “Instance" refers to the runtime representation of a module, so module and instance are the same concept — the spec explicitly speaks of module instances for clarity.

Multiple module instances only share an address space if they explicitly export/import a linear memory, which is just another kind of module-level definition. A module can define its own linear memory and not export it, in which case nobody else can access it.

> Also, criteria #1 is insufficient anyway as it admits the module system itself as a global communications channel. Worse, if a module X, i.e., the thing imported, can have mutable state, then two other modules Y and Z can communicate with each other merely by both importing module X.

No, a module cannot directly import from another module. Such access has to mitigated by the embedding glue code performing the instantiations, which thereby has full control over how modules are linked together and what they are “given". There are no communication channels between modules unless the linking code creates them.

> On your criteria #2, exports to whom? What can import what a given module exports?

Exports are what can be accessed by whoever instantiates the module or is otherwise given a reference to a module instance. But exports are all anybody can access. E.g., if a module does not export its memory then it’s private and safely encapsulated.

> Java is a good example of three ocap relevant aspects of module systems --- two of which Java gets wrong and one that Java once got right.
>
> a) By the rules of Java, any module may import java.io.File and proceed to delete all my files. It is not clear to me that this violates your criteria #1 --- the importing module is only "given" what it imports. But it is unconditionally allowed to import the ability to cause external effects. Joe-E's imports whitelist excludes all such effectful modules, and so prevents all such imports.

By "being given” I meant to imply that this can be controlled externally. Wrt Java, I was under the assumption that it enables that by defining custom class loaders that fully control and sandbox how imports are resolved, but apparently I was wrong.

> b) A Java module is a top level class. A top level class can contain static mutable state. Thus, modules Y and Z can communicate by both importing class X, via X's static state. Joe-E prevents all mutable static state.

Here too a custom class loader would have control over such imports, I thought.

I suppose I don’t fully understand why private global state would break ocap, assuming that you can control references to classes/modules like all other references.

> c) In Java prior to Java 1.2, the import namespace was not global but relative to a ClassLoader. The J-Kernel leveraged this to build an ocap system where the unit of isolation is not an object, class, or top level class, but a ClassLoader together with all the classes it loaded, together with all the instances of those classes. (To enable these to interact without accessing each other's ClassLoaders, the J-Kernel also leveraged RMI to build a full membrane between each of these units.)
>
> Java lost virtue #c as of Java 1.2 when it decided ClassLoaders could no longer override the binding of java.lang.System, which therefore provides ambient access to stdin, stdout, and stderr. The J-Kernel no longer worked starting with Java 1.2

Really?? Wow, I wasn’t aware of that. That sounds absolutely stupid, and I agree that it breaks what I described. Do you have any reference on why that change was made?

> There were several presentations at the recent OCAP 2017 workshop at Splash https://2017.splashcon.org/track/ocap-2017#program that touched on these matters. Specifically, the module systems of Monte and Wyvern follow ocap principles.
>
> Some videos and papers from OCap 2017 coming soon!
>
>
> For all these reasons, for wasm the unit of isolation is the wasm instance, not the wasm module. A wasm instance is not given what it imports because there is no prior module system that a wasm instance can import from. Rather, each instance is explicitly granted what it is given. Each wasm instance then has its own internal module system which violates ocap rules, but does not compromise the isolation of the instance within which it operates.

I’m really confused now what you are referring to as an “instance”. Do you mean something like a VM instance, i.e., what ES calls an "agent cluster”? Or are you referring to a “realm” (which doesn’t have any analogy in core Wasm)?

> > Of course, whether this implies an “ocap" system also depends on what exactly “what” quantifiers over. Formally this usually refers to free names or variables or addresses, which of course could still be side-stepped by a language providing ambient capabilities in an unnamed fashion, e.g. as primitive instructions.
> >
> > Ben Titzer (CC’ed) initially prototyped Wasm that way, and as far as he told me, he consciously decided not to include any such primitives, even though he didn’t frame it as ocap. Given the diversity of environments that Wasm is supposed to be embeddable in that is almost a necessity: there practically is no interesting (non-computational) resource that can be assumed to exist in all possible embeddings, and hence you cannot build any into the language even if you wanted. In particular, Wasm shall neither depend on the web nor JavaScript nor any specific form of OS.
> >
> > (A minor quibble I have with the quote is formulating the “what” as “effects”, because under the usual semantic interpretation of the term, a Wasm computation can still have observable effects, such as traps, non-determinism, or non-termination. But these (hopefully) are benign effects wrt security considerations.)
>
> These are good points. Not minor quibbles! Historically, when we speak of "causing or sensing effects on the world outside itself" we mean something different, such as mutation of external locations, reading changeable locations, or I/O.
>
> JavaScript's Date.now() is an example of an ocap violation because it enables the sensing of effects from the outside world, even though it does not enable the causing of any outside effects.

Oh yes, reads of external state are effects, too. In language semantics, “effect” usually is anything that prevents you from replacing a (closed) computation with its result (or vice versa) without changing the meaning of the overall program.

> By ocap significant effects, I generally do not include exceptions, non-termination, or non-determinism.
> Consumption of computational resources are not classically considered effects, and are not generally considered effects by any ocap languages. However, they are treated as capability controlled effects by OSes of the KeyKOS family (KeyKOS, EROS, Coyotos, seL4), which Norm talked about at his OCap 2017 keynote.
>
> The Capabilities and Effects paper at OCap 2017 is also relevant:
> http://homepages.ecs.vuw.ac.nz/~alex/files/CraigPotaninGrovesAldrichOCAP2017.pdf
>
>
>
>

> > On Nov 3, 2017, at 22:56 , Mark Miller <eri...@gmail.com> wrote:
> >
> > At the latest wasm (Web Assembly) standards meeting, I pointed out that wasm is already an OS-like ocap system: A wasm instance, with its linear data space + table of opaque external functions/objects is already a process-granularity-like unit of isolation with an address space and a clist. A wasm computation addresses its clist entries by clist index as expected. In addition, wasm currently obeys the following restriction.
> >
> > > WebAssembly instances must never be able to cause effects other than by wielding explicitly granted access (e.g. the importObject in a JS embedding).
> >
> > According to Andreas Rossberg (cc'ed), this is on purpose, even though the people in the room at the time did not seem to know that. I suggested that it be made normative, so security uses of this restriction would not be compromised by later "enhancements" that accidentally break this unarticulated restriction.
> >
> > https://github.com/WebAssembly/meetings/issues/104
> > is the one to watch. Assuming I do a good job clarifying the agreement we just came to, and assuming the agreement holds in the face of these clarifications, it looks like wasm will explicitly be the object-capability system it was designed to be.
> >
> > Andreas and Bradley (also cc'ed), please clarify or expand as appropriate. If you don't want to subscribe to these lists, send your posts to me and I will forward. Thanks.
> >

-- 

  Cheers,
  --MarkM

[Mark Miller]

Hi Andreas, just briefly for now:

I clearly misunderstood the relationship between wasm modules and wasm instances. Wasm instances are as principled as I hoped. But apparently so is the wasm module system, as it is much less of a separate concept than I thought. I will look again, as I need to unwind several other misunderstandings that I formed based on this one. Thanks!

--

  Cheers,
  --MarkM

[Kevin Reid]

From: Andreas Rossberg <ross...@mpi-sws.org>
Date: Sat, Nov 4, 2017 at 8:23 AM
Subject: Re: WASM and ocaps

I suppose I don’t fully understand why private global state would break ocap, assuming that you can control references to classes/modules like all other references.

I'm not following this thread in detail but I thought I could say something about this:

If you have a system where modules are not themselves global in any way (e.g. it is possible to load more than one copy), then strictly speaking having mutable state in a module does not break capability rules. However, it does discourage good capability design, because it means that ordinary object instances might decide to share something via their defining module when they really ought to have been explicitly constructed with it (or from it) instead. It means that you can't conclude that objects are isolated just because you constructed them separately. (There is nothing special about modules here; in general you can get new objects from asking other objects (factories, if you like), and it is better — all else being equal — if those factories are not mutable.)

It's like having static non-final fields in Java classes: technically you can have another ClassLoader, but nobody wants to do that as part of ordinary programming. They'd rather use dependency injection frameworks!

(Dependency injection, in the sense of the principle of "do not have static state/references-to-other-significant-objects, pass them as constructor parameters instead", is aligned with capability principles. Dependency injection frameworks are, as far as as far as I know (I haven't actually programmed with one myself), things which manage a bag of ambient authority to pass to those constructors, and so are not so aligned.)

[Mark Miller]

(Forwarded with permission)

---------- Forwarded message ----------
From: Ben L. Titzer <tit...@google.com>
Date: Wed, Nov 8, 2017 at 11:34 AM
Subject: Re: WASM and ocaps

To: Mark Miller <eri...@gmail.com>
Cc: Andreas Rossberg <ross...@mpi-sws.org>, Discussion of E and other capability languages <e-l...@googlegroups.com>, Bradley Nelson <bradn...@google.com>

On Sat, Nov 4, 2017 at 5:41 AM, Mark Miller <eri...@gmail.com> wrote:

On Sat, Nov 4, 2017 at 1:17 AM, Andreas Rossberg <ross...@mpi-sws.org> wrote:

To clarify for the broader crowd, to me this quote about (module) instances just describes an aspect of proper modularity, which naturally consists of two dual properties:

1. A module can only access what it (is given as) imports.
2. A client can only access what a module exports.

 

At the granularity of wasm modules, wasm is still not an ocap system for the very reason that multiple wasm modules within a wasm instance share a linear address space and can step on each other's data freely. This violates your criteria #1.

Memories are imported and exported just like functions. Thus access to the memory is an explicit capability.

 

Also, criteria #1 is insufficient anyway as it admits the module system itself as a global communications channel. Worse, if a module X, i.e., the thing imported, can have mutable state, then two other modules Y and Z can communicate with each other merely by both importing module X.

Modules don't explicitly import modules, they import finer grained pieces such as tables, functions, memories or globals. 

 

On your criteria #2, exports to whom? What can import what a given module exports?

The embedding (host) environment can access exports, and provide exports of one instance as the imports to another instance.

--

  Cheers,
  --MarkM

[Mark Miller]

I wrote:

> I clearly misunderstood the relationship between wasm modules and wasm instances. Wasm instances are as principled as I hoped. But apparently so is the wasm module system, as it is much less of a separate concept than I thought. I will look again, as I need to unwind several other misunderstandings that I formed based on this one. Thanks!

I went back and reread the manual and had multiple clarifying conversations with Ben Titzer. What I had previously said about "instances" was correct but incomplete. What I said about "modules" was totally incorrect. My confusion was caused by the difference between foundational rules vs expected patterns of use. Untangling this leads me to make the following claims:

a) The wasm foundation as currently speced already has the safety property of ocaps stated at https://github.com/WebAssembly/meetings/issues/104 :

WebAssembly instances must never be able to cause effects [outside itself] other than by wielding explicitly granted access (e.g. the importObject in a JS embedding).

given a suitable definition of "effects".

b) The wasm foundation as currently speced does not have the expressiveness properties of ocaps. In particular, invocations can only pass data, not capabilities.

c) This loss of expressiveness has not been an obvious pain point is because of a dominant pattern of use that links all code together into one address space, losing all the safety advantages that should have derived from wasm's inter-instance safe separation properties. Patterns of use that seem plausible from reading the wasm spec, that attempt to make use of these safety properties, fail in painful ways that should be fixed.

d) The Host Bindings proposal https://github.com/WebAssembly/host-bindings/blob/master/proposals/host-bindings/Overview.md does not suffer from this expressiveness gap. Rather, its mappings between Table indexes and Table entries already is exactly the c-list manipulation needed on each side of a capability invocation, such as an IPC in an ocap operating system.

e) Generalizing this host bindings proposal to apply not just wasm-embedder but wasm-wasm solves the problem in general, and makes wasm into a full ocap system, regarding both safety and expressiveness.

-------------------------

Wasm as an OCap-safe Module System

For all these, we must first clarify what a wasm module is, and what a wasm module instance is. Verbally Ben was happy with the following summary. Ben, I'm elaborating the summary to make it more precise. However, if you're not happy with it, please explain. Thanks.

A wasm module is effectively a closed function from named parameters to a wasm instance. A wasm instance is effectively a record mapping export named to exported values. These exported values are created by the module's code and static data, given only the values of these named import parameters. This sense in which a wasm module is such a function is not to be confused with wasm functions, which is a kind of wasm value that can be invoked within wasm. Only the embedder invokes a wasm module to create a wasm instance, which we refer to as "instantiating" the module. 

A wasm module is made from data describing a module (e.g., the contents of a *.wasm file) by "compiling".

Stated this way, this is already the ideal starting point for an ocap module system, and indeed is similar to the module systems of Monte and Wyvern. It goes further by omitting from wasm any logic for dereferencing a module name to a file or for fetching the contents of a file to get the data.

An instantiated module has several flat address spaces indexable by numbers:

A "memory", i.e., a flat linear address space of data (bytes).

Global variables holding data.

Various forms of table holding functions, memories, (values of) global variables, and tables-of-functions.

Entries in these spaces are designated by numeric indexes into these spaces.

Let's call each index into a memory an "address". Let's call each table that holds non-data a "clist", and each index into one a "clist index". A non-data value found in a clist is a "capability".

All of this exactly parallels those ocap operating systems that keep capabilities in clists. In these terms, a wasm instance is a process-like (though without its own thread, which is good and orthogonal to the issues here). Each process has its own address space and its own clists.

Wasm Lacks OCap Expressiveness

A wasm function (i.e., the wasm value that wasm code can invoke) is currently speced to take only numbers as arguments and to return only numbers as results. It may at first seem puzzling why this is sufficient, given that wasm is the target of compilation from languages in which functions can be passed as parameters to functions. The answer is that, in the dominant pattern of use, both calling function (f) and called function (g) are assumed to be share the same indexable spaces, so a clist index that a f uses to refer to a function h1 can be used by g to refer to the same function h1, by virtue of indexing into the same clist.

If f and g are in the same instance, then this assumption is necessarily true. However, many uses of wasm cross module instance boundaries: g might have been exported from g's module G and imported into f's module F. In this case, the assumption does not necessarily hold. The index f uses to index into F's clists to designate h1, if transmitted to g and used by g to index into G's clists, might designate instead completely unrelated function h2.

Language compilers targeting wasm may map intermodule linkage of their source language to inter-instance linkage of their wasm target. They do not encounter this confusion in practice because they use wasm's ability to import and export memories and clists so that all instances linked together share the same memory and the same set of clists. Among all instances linked together in this way, a clist index as used by any designate the same thing as that clist index used by any other. Likewise for numbers to be interpreted as addresses: they can simply be passed as numbers because they index into the same memory.

Instances vs Isolates

This linkage pattern is so common that we need a name for it. Because there is no isolation between a bunch of instances linked together in this manner, let's call the whole bunch an isolate. Mostly, the clists of an isolate simply designate other functions within the same isolate, which are uninteresting from an ocap perspective. In addition, some of these clists hold functions provided by the embedder, that code within the isolate can invoke, designating them by their clist index. These functions may either be host functions --- functions not implemented in wasm --- or they may be functions exported by another isolate.

Returning to our ocap OS analogy, host functions are like kernel-provided objects; in KeyKOS, every capability other than "start keys" and "resume keys". Invoking a host function is like performing a system call to employ the kernel-provided service reified by this kernel provided object. Invoking a wasm function exported by another isolate is like IPC, but an IPC in an OS in which only data may be passed.

If f and g are in separate isolates, there's no way for f to invoke g giving it access to F's h1. However, if g is a host function, then the host binding proposal would solve the problem. Unwound into wasm-to-wasm IPC, it's four binding mechanisms are like the four parts into which we could divide an ocap IPC. Chronologically:

Caller's arguments:

Caller passes data arguments by copy. Caller designates capability arguments by clist index into caller's isolate, which by definition is the same as designating by clist index into caller's instance.

Callee's parameter binding:

New clist indexes are (somehow) allocated with the callee's clist, the capabilities the caller designated are placed in the callee's clist as these locations, and the callee function is invoked with these clist indexes.

Callee's return:

Much like caller's arguments, Callee's designates return capabilities by clist index into its own clists.

Caller's return:

The returned capability results are placed into the caller's clist at a clist index provided by the caller during the call. Since the caller already knows where the result was placed, at the wasm level, it need not be returned.

The host binding proposal also specifies similar copying of bulk data by address. It can be read in a similar manner to provide for the copying of bulk data from one isolate's memory to another's.

Deeper Wasm Integration

The host binding proposal's descriptors seem different than wasm's existing types, and different from the separately proposed wasm-gc types

https://github.com/WebAssembly/gc/blob/master/proposals/gc/Overview.md . With the web as the expected embedder of interest, there is desire to derive these descriptors from WebIDL types. This has interesting parallels with other cap-oriented IDLs like CapIDL or Cap'n Proto. But WebIDL is also bizarre and idiosyncratic, and no longer makes any claim of being language neutral.

Rather, these descriptors should be, or be derived from, a type notion more directly aligned with wasm or wasm-gc. It should be applicable to any function typing, enabling functions within an isolate, external functions in other isolates, and host functions to be polymorphic with each other. Compilers that know they are supporting only intra-isolate calls can continue to do use only data parameters. Otherwise, for compilers not making this assumption, if both caller and caller happen to be in the same isolate, the descriptors can be ignored and all this mechanism can be bypassed by wasm at the cost of an extra runtime test. The IPC-like translation cost should only be paid when invoking a host function or a function in a different isolate.

--

  Cheers,
  --MarkM

[Mark Miller]

Had a great talk with Bradley Nelson (cc'ed) about all this. Several refinements:

The term "isolate" is too overloaded, particularly for something that will be part of a v8 engine. We're both happy with "compartment".

Where the WebAssembly spec says:

    functype ::= [vec(valtype)] -> [vec(valtype)] 
    valtype ::= i32 | i64 | f32 | f64

change to

    functype ::= [vec(argtype)] -> [vec(argtype)]

    argtype ::= valtype | cap(tableid) | mem(memid)

    tableid ::= u32

    memid ::= u32

    valtype ::= i32 | i64 | f32 | f64

To understand this, we first need to know that a wasm instance (and therefore a wasm compartment) has some number of tables indexed by tableid, and some number of memories indexed by memid. Each table contains only elements (currently always functions) of the same static type, associated with that tableid. IOW, (somewhere?) there's a mapping between tableids and typeids. A table entry is thus designated by a pair of a tableid and an index into that table. The argument type provides the tableid statically. The corresponding argument provides the index into that table dynamically as a u32.

Likewise, a contiguous region of linear data memory is designated by a triple of 

* the memid of a memory

* a u32 as the "address" of the start of that region in that memory

* a u32 as the length of that region

For passing data, the argument type provides the memid statically and a pair of arguments then provides the start and length dynamically as a pair of u32 arguments.

To pass an argument of type valtype, the implementation does exactly what it does now: it conveys the dynamic argument number from caller to callee.

To pass an argument of type cap(tableid), the implementation checks whether the caller's table at tableid is the same table as the callee's table at tableid. If so, then the dynamic argument number is conveyed from caller to callee, just as it is for a valtype. This means that, within a compartment, cap passing acts the same as value passing, preserving compat with all current intra-compartment code.

If the caller and callee have different tables at tableid, these tables must still have compatible types, which can be checked statically when binding imports. In this case, the caller's table entry at (tableid, argument) is looked up and placed at some(*) index in the table at the callee's tableid. This index into the callee's table at tableid is then passed as the dynamic argument number to the callee.

To pass an argument of type mem(memid), the implementation checks whether the caller's memory at memid is the same memory as the callee's memory at memid. If so, then the dynamic pair of argument numbers is conveyed from caller to callee, just as for a pair of valtype-typed arguments. This means that within a compartment, a region of memory is passed by pointer with no copying.

If the caller and callee have different memories at memid, then the caller's data is copied to somewhere(*) in the callee'd memory at memid, and the address and length that the data are copied into passed as a pair of numeric arguments to the callee.

(*) Allocating new addresses / indexes.

The indexes or addresses at which caps or data is received can be allocated somehow, or sometimes can be somehow specified by the receiver. For example, following the host binding proposal, we could allow a caller to say where its return value should be placed. When actually calling between compartments, it will indeed be placed there. When short circuiting the call within a compartment, the extra data copy would be wasteful. For the sake of uniformity with the current intra-compartment behavior, we make it optional for a caller to provide placement for the return value, and we always return the actual placement dynamically, whether or not one was provided by the call.

Likewise, following the host binding proposal, the callee could provide an allocation function for the IPC to call first, to determine where in the callee's memory the data is to be copied.

Finally, the upcoming wasm-gc would do parameter passing of capabilities on the normal call stack, by extending the type language of stack variable types. Perhaps that mechanism would subsume this one, and provide better allocation system for capability passing. Passed data might be copied into separately allocated objects, and a capability to that allocation unit be passed.

Conversions:

The current host binding proposal contains descriptors that imply conversions, such as a JSON parse or a utf8 to utf16 conversion. In this new proposal, we omit all such builtin conversions. Rather, to perform any desired conversion, explicitly call a converter function. It is up to the users of wasm whether these converters are wasm functions or host functions, but either way they do not need any special mechanism. (A host converter may be able to avoid an extra copy that a wasm converter cannot.)

[Mark Miller]

[forwarding again]

On Thu, Nov 16, 2017 at 7:25 AM, Andreas Rossberg <ross...@mpi-sws.org> wrote:

Hi Mark,

to summarise, you want to be able to pass table elements or memory contents between Wasm functions without them sharing a “global" table or memory. That makes sense, and I agree that the inability to do so (short of the GC proposal) is a hole.

However, as is, your concrete proposal probably isn't the best fit for WebAssembly, because it involves quite a bit of ad-hoc magic (implicit type coercions, implicit identity checks, implicit allocation callbacks, even a form of dependent typing) that doesn’t quite match the low-level nature of Wasm. Moreover, it abuses module-internal(!) table/memory ids with cross-module semantics in a way that is brittle at best — you should think of a module’s index spaces as a purely local naming mechanism whose order should be unobservable externally.

That said, I see at least two possible options for simplifying it:

1. Multiple tables / memories (plus instructions for copying/clearing elements). Two functions could pass back and forth data by sharing an auxiliary table/memory for passing arguments/results. A caller would copy its args there, the callee would use them or copy them as it sees fit. Vice versa for results. Essentially, exporting a function that takes or returns resources would always be paired with exporting an associated scratch table/memory.

Advantage: Simple and general mechanism; we want to add this anyway.

Disadvantage: Requires copying twice if the receiver needs to keep the values (no obvious way to optimise that in an engine)

2. The ability to form a read-only “slice” of a table or memory. Such a slice would be a first-class value type (a kind of bounds-checked pointer) that would allow accessing the contained elements but doesn’t provide a reference to the rest of a table/memory. A caller would form a slice, the callee can use or copy the contents as it sees fit. (This is a sort of generalisation of your proposal, but minus any magic.)

Advantage: More efficient than option (1) in various cases; if done right might be a basis for unraveling the bindings proposal.

Disadvantage: More complexity; requires new types, instructions for creating and accessing slices; slice values can keep tables/memories alive, might require reference counting.


As an aside, I note that in general you probably need the ability to pass lists of elements, not just individual ones, so both these options support that.

/Andreas

--

  Cheers,
  --MarkM

[Mark Miller]

On Thu, Nov 16, 2017 at 7:25 AM, Andreas Rossberg <ross...@mpi-sws.org> wrote:

Hi Mark,

to summarise, you want to be able to pass table elements or memory contents between Wasm functions without them sharing a “global" table or memory. That makes sense, and I agree that the inability to do so (short of the GC proposal) is a hole.

However, as is, your concrete proposal probably isn't the best fit for WebAssembly, because it involves quite a bit of ad-hoc magic (implicit type coercions, implicit identity checks, implicit allocation callbacks, even a form of dependent typing) that doesn’t quite match the low-level nature of Wasm. Moreover, it abuses module-internal(!) table/memory ids with cross-module semantics in a way that is brittle at best — you should think of a module’s index spaces as a purely local naming mechanism whose order should be unobservable externally.

These all sound like criticisms I would also like to see solved, thanks. In particular, I fully agree it is important to maintain a principled stance on encapsulation and unobservability. The "dependent typing" in your list surprised me. How does my proposed mechanism touch on that?

Nevertheless, from your response, it achieved its important goal: to explain what's missing, and demonstrate that the mechanism needed to address it should both subsume the core host binding mechanism, and be at least as simple as the host binding proposal.

However, from your suggestions below I am not sure that I've explained adequately what's missing, or rather, what goals the new mechanism should achieve. Let's take the function-calling form of the canonical Granovetter-diagram example:

Say there are three functions, alice, bob, and carol, that appear in three module instances, A, B, and C, that have no sharing relationships beyond those implied by the following scenario. In the initial conditions alice, and therefore A, has access to (is able to call) bob, as exported from B. alice, and therefore A, also has access to carol as exported from C. In these initial conditions, B has no access to carol and C has no access to bob.

 alice says:

    bob(carol)

transferring control to bob in B, giving bob, and therefore B, the ability to call carol as exported from C.

I think the existing host binding proposal already satisfies all of this, provided only that each wasm-to-wasm call is instead a wasm-to-trivial-host-wrapper-to-wasm call. For something to subsume the host binding mechanism, it should preserve this property, from which should follow most of the advantages of ocaps. (One more element will be needed to obtain the full benefits, but we can postpone that till we answer the current questions.)

I don't understand your proposals well enough to tell if they satisfy these goals, so let's try testing them against the above scenario.

 

That said, I see at least two possible options for simplifying it:

1. Multiple tables / memories (plus instructions for copying/clearing elements). Two functions could pass back and forth data by sharing an auxiliary table/memory for passing arguments/results. A caller would copy its args there, the callee would use them or copy them as it sees fit. Vice versa for results. Essentially, exporting a function that takes or returns resources would always be paired with exporting an associated scratch table/memory.

To represent the initial conditions of my scenario in terms of your option #1, I take it that there would be a table AB shared between A and B, used by alice to pass parameters like carol to bob, and a table AC between A and C, supporting alice's ability to call carol. In the initial conditions, there would be no table BC between B and C, since in the initial conditions neither B nor C have any need to call anything in the other.

For alice to call bob passing bob access to carol, alice would store something into the table AB at index ci, that provides the same ability to call carol that alice has. alice would then pass ci in that argument position to bob. bob would then (somehow) know to look up carol at index ci in table AB.

However, if carol is also a function like bob that takes such parameters, then B and C would now need to share a table BC, for arguments that bob might pass to carol. Within option #1, how could this come about?

I'll get to your option #2 in another message, possibly tomorrow. But there's no need wait for that before reacting to the text above. Thanks.

Advantage: Simple and general mechanism; we want to add this anyway.

Disadvantage: Requires copying twice if the receiver needs to keep the values (no obvious way to optimise that in an engine)

2. The ability to form a read-only “slice” of a table or memory. Such a slice would be a first-class value type (a kind of bounds-checked pointer) that would allow accessing the contained elements but doesn’t provide a reference to the rest of a table/memory. A caller would form a slice, the callee can use or copy the contents as it sees fit. (This is a sort of generalisation of your proposal, but minus any magic.)

Advantage: More efficient than option (1) in various cases; if done right might be a basis for unraveling the bindings proposal.

Disadvantage: More complexity; requires new types, instructions for creating and accessing slices; slice values can keep tables/memories alive, might require reference counting.


As an aside, I note that in general you probably need the ability to pass lists of elements, not just individual ones, so both these options support that.

/Andreas

--

  Cheers,
  --MarkM

[Mark Miller]

(forwarding again)

On Nov 17, 2017 11:33 AM, "Andreas Rossberg" <ross...@mpi-sws.org> wrote:

> > to summarise, you want to be able to pass table elements or memory contents between Wasm functions without them sharing a “global" table or memory. That makes sense, and I agree that the inability to do so (short of the GC proposal) is a hole.
>
> > However, as is, your concrete proposal probably isn't the best fit for WebAssembly, because it involves quite a bit of ad-hoc magic (implicit type coercions, implicit identity checks, implicit allocation callbacks, even a form of dependent typing) that doesn’t quite match the low-level nature of Wasm. Moreover, it abuses module-internal(!) table/memory ids with cross-module semantics in a way that is brittle at best — you should think of a module’s index spaces as a purely local naming mechanism whose order should be unobservable externally.
>
> These all sound like criticisms I would also like to see solved, thanks. In particular, I fully agree it is important to maintain a principled stance on encapsulation and unobservability. The "dependent typing" in your list surprised me. How does my proposed mechanism touch on that?

A type like mem(memid) contains a reference to a value-level entity, whose identity is dynamic (e.g., it might be imported). Technically, that’s a dependent type, and it’s not entirely clear to me how to handle it during type checking without the index space conflation I mentioned.

> Nevertheless, from your response, it achieved its important goal: to explain what's missing, and demonstrate that the mechanism needed to address it should both subsume the core host binding mechanism, and be at least as simple as the host binding proposal.
>
> However, from your suggestions below I am not sure that I've explained adequately what's missing, or rather, what goals the new mechanism should achieve. Let's take the function-calling form of the canonical Granovetter-diagram example:
>
> Say there are three functions, alice, bob, and carol, that appear in three module instances, A, B, and C, that have no sharing relationships beyond those implied by the following scenario. In the initial conditions alice, and therefore A, has access to (is able to call) bob, as exported from B. alice, and therefore A, also has access to carol as exported from C. In these initial conditions, B has no access to carol and C has no access to bob.
>
>  alice says:
>
>     bob(carol)
>
> transferring control to bob in B, giving bob, and therefore B, the ability to call carol as exported from C.

This would be the simplest example of a higher-order function. Let’s call a function that takes or returns “resources” a resourceful function. Resources include host objects, but also functions or tables themselves. In your example, bob is a 2nd-order resourceful function, because it takes another resourceful function as argument.

Using option (1) in the general case means performing a simple form of “lowering" of resourceful functions to Wasm’s more primitive functions plus tables. This is completely compositional and mechanical. Best understood by simply looking at the types of these functions.

As mentioned, a 1st-order resourceful function type like

  (obj, obj, obj, i32) -> i32

(a function taking three opaque host objects as arguments plus an int and returning an int) would be lowered to a pair

  ((i32 -> i32), table(obj))

of the simplified function (taking only the int) and a table over opaque host objects (of size 3 in this case). So concretely, instead of exporting just one function a module would export a function and a table. In general, though, the result of lowering is a tuple, because tables are typed, so that you'll need a separate table for each different type of argument.

That generalises to the higher-order case straightforwardly. For the sake of example and differentiation, let’s assume the resourceful types of your three functions are:

  alice : (obj, i64) -> i64
  bob : (obj -> i32) -> f32
  carol : obj -> i32

Note how bob takes a function of carol’s type as argument, which corresponds to the call you want to perform. The types of alice and bob are again just 1st-order resourceful function types that lower as before:

  alice : (i64 -> i64, table(obj))
  carol : (() -> i32, table(obj))

The type of bob is resourceful as well, because a function is itself a resource. But its 2nd-order. In a first step its parameter type lowers recursively to yield a pair of arguments:

  bob : (() -> i32, table(obj)) -> f32

Both these arguments are still resource types, so the overall type further lowers to the tuple

  bob : (() -> f32, table(() -> i32)), table(table(obj)))

We can already put functions into tables, so all we need here is the ability to also put tables themselves into other tables (they are resources, too). In fact, we could already do that indirectly with obj, but you'll want a type transparent to Wasm in this case.

As said, this lowering composes at arbitrary order, but I doubt anything beyond 2nd order will show up much in practice.

> To represent the initial conditions of my scenario in terms of your option #1, I take it that there would be a table AB shared between A and B, used by alice to pass parameters like carol to bob, and a table AC between A and C, supporting alice's ability to call carol. In the initial conditions, there would be no table BC between B and C, since in the initial conditions neither B nor C have any need to call anything in the other.

Right.

> For alice to call bob passing bob access to carol, alice would store something into the table AB at index ci, that provides the same ability to call carol that alice has. alice would then pass ci in that argument position to bob. bob would then (somehow) know to look up carol at index ci in table AB.
>
> However, if carol is also a function like bob that takes such parameters, then B and C would now need to share a table BC, for arguments that bob might pass to carol. Within option #1, how could this come about?

To summarise the above, roughly speaking, by using the table you call BC to also pass the table AC to bob, not just the function. However, because of types, you actually have to split that BC into two separate tables, as shown above.

Does that make sense? Really, this is just a fairly conventional form of lowering, similar e.g. to how a C compiler might convert functions that take/return structs by value to functions that instead pass pointers to temporary local buffers.

/Andreas

[Mark Miller]

Hi Andreas, Bradley and I just stared at your message for over an hour and could not figure it out, though we have some hypotheses. The key thing is that you explain in terms of static types, perhaps assuming it is clear what runtime behavior it implies. However, Bradley and I have not arrived at this clarity. Questions below, as well as some hypotheses about the runtime behavior you have in mind.

On Fri, Nov 17, 2017 at 11:33 AM, Andreas Rossberg <ross...@mpi-sws.org> wrote:

> > to summarise, you want to be able to pass table elements or memory contents between Wasm functions without them sharing a “global" table or memory. That makes sense, and I agree that the inability to do so (short of the GC proposal) is a hole.
>
> > However, as is, your concrete proposal probably isn't the best fit for WebAssembly, because it involves quite a bit of ad-hoc magic (implicit type coercions, implicit identity checks, implicit allocation callbacks, even a form of dependent typing) that doesn’t quite match the low-level nature of Wasm. Moreover, it abuses module-internal(!) table/memory ids with cross-module semantics in a way that is brittle at best — you should think of a module’s index spaces as a purely local naming mechanism whose order should be unobservable externally.
>
> These all sound like criticisms I would also like to see solved, thanks. In particular, I fully agree it is important to maintain a principled stance on encapsulation and unobservability. The "dependent typing" in your list surprised me. How does my proposed mechanism touch on that?

A type like mem(memid) contains a reference to a value-level entity, whose identity is dynamic (e.g., it might be imported). Technically, that’s a dependent type, and it’s not entirely clear to me how to handle it during type checking without the index space conflation I mentioned.

Good. I get the index space conflation and see why it is a problem.

 

> Nevertheless, from your response, it achieved its important goal: to explain what's missing, and demonstrate that the mechanism needed to address it should both subsume the core host binding mechanism, and be at least as simple as the host binding proposal.
>
> However, from your suggestions below I am not sure that I've explained adequately what's missing, or rather, what goals the new mechanism should achieve. Let's take the function-calling form of the canonical Granovetter-diagram example:
>
> Say there are three functions, alice, bob, and carol, that appear in three module instances, A, B, and C, that have no sharing relationships beyond those implied by the following scenario. In the initial conditions alice, and therefore A, has access to (is able to call) bob, as exported from B. alice, and therefore A, also has access to carol as exported from C. In these initial conditions, B has no access to carol and C has no access to bob.
>
>  alice says:
>
>     bob(carol)
>
> transferring control to bob in B, giving bob, and therefore B, the ability to call carol as exported from C.

This would be the simplest example of a higher-order function. Let’s call a function that takes or returns “resources” a resourceful function. Resources include host objects, but also functions or tables themselves. In your example, bob is a 2nd-order resourceful function, because it takes another resourceful function as argument.

Using option (1) in the general case means performing a simple form of “lowering" of resourceful functions to Wasm’s more primitive functions plus tables. This is completely compositional and mechanical. Best understood by simply looking at the types of these functions.

As mentioned, a 1st-order resourceful function type like

  (obj, obj, obj, i32) -> i32

(a function taking three opaque host objects as arguments plus an int and returning an int) would be lowered to a pair

  ((i32 -> i32), table(obj))

of the simplified function (taking only the int) and a table over opaque host objects (of size 3 in this case). So concretely, instead of exporting just one function a module would export a function and a table. In general, though, the result of lowering is a tuple, because tables are typed, so that you'll need a separate table for each different type of argument.

So when a caller invokes a callee of this type, the caller would copy the three obj arguments into this table, and the callee would immediately copy out before doing any other function calls, to avoid reentrancy hazards? In this sense, the table is serving as parameter passing registers for calling this one function?

Currently, if modules D and E both import a function f from module F, D and E can then interact to the extent that f's behavior allows. They can both call f but do not have and direct shared mutable state.

Assume the above is the type of f. With this lowering, both D and E would import this tuple, giving them shared access to this one table. After D uses this table to call f, can E read the table to obtain whatever D passed to f?

 

That generalises to the higher-order case straightforwardly. For the sake of example and differentiation, let’s assume the resourceful types of your three functions are:

  alice : (obj, i64) -> i64
  bob : (obj -> i32) -> f32
  carol : obj -> i32

Good. This corresponds exactly to the high level types I have in mind for bob and carol. The type of alice is irrelevant, right? You just provided a type because alice must have some type? 

To restate our same confusion, with these signatures, do we agree that A (and therefore alice) should never get access to the obj that bob passes to carol?

 

Note how bob takes a function of carol’s type as argument, which corresponds to the call you want to perform. The types of alice and bob are again just 1st-order resourceful function types that lower as before:

  alice : (i64 -> i64, table(obj))
  carol : (() -> i32, table(obj))

The type of bob is resourceful as well, because a function is itself a resource. But its 2nd-order. In a first step its parameter type lowers recursively to yield a pair of arguments:

  bob : (() -> i32, table(obj)) -> f32

Both these arguments are still resource types, so the overall type further lowers to the tuple

  bob : (() -> f32, table(() -> i32)), table(table(obj)))

When alice imports bob, is alice obtaining a table of tables of obj? Or is alice passing such a table to bob on invoking him. I think the former.

For all the tables above, what arity do they have when? What do they actually contain when? Bradley and I were imagining that, for this scenario, they are at most singleton tables. Is this right?

Can you step us through the lowered implementation of the following dynamic sequence of actions, restating as a corresponding dynamic sequence of actions? Assume nothing is being passed other than what is stated.

embedder: instantiate module B, providing obj1 as B's "obj" import. B exports bob as "bob".

embedder: instantiate module C providing no imports. C exports carol as "carol".

embedder: instantiate module A providing bob as "bob" and carol as "carol". A exports alice.

embedder: call alice with arguments (obj2, 77).

alice: call bob with arguments (carol).

bob: call carol with arguments (obj1).

embedder: call alice again with (obj2, 77). Can alice obtain obj1?

Thanks!

 

We can already put functions into tables, so all we need here is the ability to also put tables themselves into other tables (they are resources, too). In fact, we could already do that indirectly with obj, but you'll want a type transparent to Wasm in this case.

As said, this lowering composes at arbitrary order, but I doubt anything beyond 2nd order will show up much in practice.

> To represent the initial conditions of my scenario in terms of your option #1, I take it that there would be a table AB shared between A and B, used by alice to pass parameters like carol to bob, and a table AC between A and C, supporting alice's ability to call carol. In the initial conditions, there would be no table BC between B and C, since in the initial conditions neither B nor C have any need to call anything in the other.

Right.

> For alice to call bob passing bob access to carol, alice would store something into the table AB at index ci, that provides the same ability to call carol that alice has. alice would then pass ci in that argument position to bob. bob would then (somehow) know to look up carol at index ci in table AB.
>
> However, if carol is also a function like bob that takes such parameters, then B and C would now need to share a table BC, for arguments that bob might pass to carol. Within option #1, how could this come about?

To summarise the above, roughly speaking, by using the table you call BC to also pass the table AC to bob, not just the function. However, because of types, you actually have to split that BC into two separate tables, as shown above.

Does that make sense? Really, this is just a fairly conventional form of lowering, similar e.g. to how a C compiler might convert functions that take/return structs by value to functions that instead pass pointers to temporary local buffers.

/Andreas

--

  Cheers,
  --MarkM

[Mark Miller]

[Forwarding again]

On Tue, Nov 21, 2017 at 9:45 AM, Andreas Rossberg <ross...@mpi-sws.org> wrote:

> On Nov 21, 2017, at 00:53 , Mark Miller <eri...@gmail.com> wrote:
> On Fri, Nov 17, 2017 at 11:33 AM, Andreas Rossberg <ross...@mpi-sws.org> wrote:
> >As mentioned, a 1st-order resourceful function type like
> >
> >  (obj, obj, obj, i32) -> i32
> >
> >(a function taking three opaque host objects as arguments plus an int and returning an int) would be lowered to a pair
> >
> >  ((i32 -> i32), table(obj))
> >
> >of the simplified function (taking only the int) and a table over opaque host objects (of size 3 in this case). So concretely, instead of exporting just one function a module would export a function and a table. In general, though, the result of lowering is a tuple, because tables are typed, so that you'll need a separate table for each different type of argument.
>
> So when a caller invokes a callee of this type, the caller would copy the three obj arguments into this table, and the callee would immediately copy out before doing any other function calls, to avoid reentrancy hazards? In this sense, the table is serving as parameter passing registers for calling this one function?

Yes. Of course, stateful protocols are nasty, so you have to be careful if you want to achieve reentrancy and not leak information. I should have expected your follow-up question. :)

> Currently, if modules D and E both import a function f from module F, D and E can then interact to the extent that f's behavior allows. They can both call f but do not have and direct shared mutable state.
>
> Assume the above is the type of f. With this lowering, both D and E would import this tuple, giving them shared access to this one table. After D uses this table to call f, can E read the table to obtain whatever D passed to f?

Well, not if you make it part of the parameter passing protocol that f clears the buffer before returning or calling out to a third party. That is necessary if you want to support or guard against reentrancy.

> >That generalises to the higher-order case straightforwardly. For the sake of example and differentiation, let’s assume the resourceful types of your three functions are:
> >
> >  alice : (obj, i64) -> i64
> >  bob : (obj -> i32) -> f32
> >  carol : obj -> i32
>
> Good. This corresponds exactly to the high level types I have in mind for bob and carol. The type of alice is irrelevant, right? You just provided a type because alice must have some type?

Yes, that’s right.

> To restate our same confusion, with these signatures, do we agree that A (and therefore alice) should never get access to the obj that bob passes to carol?

Yes.

> >Note how bob takes a function of carol’s type as argument, which corresponds to the call you want to perform. The types of alice and bob are again just 1st-order resourceful function types that lower as before:
> >
> >  alice : (i64 -> i64, table(obj))
> >  carol : (() -> i32, table(obj))
> >
> >The type of bob is resourceful as well, because a function is itself a resource. But its 2nd-order. In a first step its parameter type lowers recursively to yield a pair of arguments:
> >
> >  bob : (() -> i32, table(obj)) -> f32
> >
> >Both these arguments are still resource types, so the overall type further lowers to the tuple
> >
> >  bob : (() -> f32, table(() -> i32)), table(table(obj)))
>
> When alice imports bob, is alice obtaining a table of tables of obj? Or is alice passing such a table to bob on invoking him. I think the former.

A imports from B the function and the two buffer tables. When it invokes the function it first fills the tables. In the case of the second table, it fills it with a reference to a third table.

> For all the tables above, what arity do they have when? What do they actually contain when? Bradley and I were imagining that, for this scenario, they are at most singleton tables. Is this right?

Yes, the fact that a table can have more than one entry is not essential for this. You could use a separate singleton table for each parameter, since their number is statically known. But as the earlier example shows combining multiple parameters of the same type into a single table is an obvious optimisation.

(Also, I could imagine examples where you need to pass lists of things.)

> Can you step us through the lowered implementation of the following dynamic sequence of actions, restating as a corresponding dynamic sequence of actions? Assume nothing is being passed other than what is stated.
>
> embedder: instantiate module B, providing obj1 as B's "obj" import. B exports bob as "bob”.

It exports the function “bob” plus the associated parameter-passing tables, say as “bob-param1-buf” and “bob-param2-buf”.

> embedder: instantiate module C providing no imports. C exports carol as "carol”.

It exports the function “carol” and the associated table, say “carol-param-buf”.

> embedder: instantiate module A providing bob as "bob" and carol as "carol". A exports alice.

A imports, and is provided with, all three entities that B exports. It exports the function “alice” and the associated table, say “alice-param-buf".

> embedder: call alice with arguments (obj2, 77).

It sets alice-param-buf[0] to obj2 and calls alice(77).
Alice copies obj2 somewhere else and unsets alice-param-buf[0].

> alice: call bob with arguments (carol).

Alice sets bob-param1-buf[0] to the function carol, and bob-param2-buf[0] to (a reference to) table carol-param-buf, and then calls bob().
Bob copies both arguments somewhere else and clears the tables.

> bob: call carol with arguments (obj1).

Bob sets carol-param-buf[0] (as previously received and saved) to obj1 and calls carol().
Carol unsets the table entry.

(I’m not sure if this was meant to be the same obj1 that was used as an import descriptor above? If so, I’m not sure why the two should be related.)

> embedder: call alice again with (obj2, 77). Can alice obtain obj1?

Not if carol-param-buf[0] was properly unset (nulled out) by carol after receiving it, as shown in the previous step.


The setting and clearing tables in this protocol is kind of brittle, as all stateful approaches. If that is not reliable enough, there would be another option based on a fairly simple language extension: introduce read-only and write-only views of tables/memories as supertypes and allow a module to export as a supertype. Then all the table types in my examples would be write-only tables and only the originating module could read them. So D and E in your earlier example could not use F's table as a communication channel between them, since only F can read it. Similarly, alice could not read obj1 out of carol's table, even if it wasn't cleared by carol.

(This restriction is easy to achieve with types, but unfortunately it is less clear how to elegantly reflect such type restrictions in an untyped embedder API like the JS one.)


/Andreas

--

  Cheers,
  --MarkM

[Mark Miller]

Andreas, thanks for the tremendously clear answers! Only a few questions left regarding option #1.

> Currently, if modules D and E both import a function f from module F, D and E can then interact to the extent that f's behavior allows. They can both call f but do not have and direct shared mutable state.
>
> Assume the above is the type of f. With this lowering, both D and E would import this tuple, giving them shared access to this one table. After D uses this table to call f, can E read the table to obtain whatever D passed to f?

Well, not if you make it part of the parameter passing protocol that f clears the buffer before returning or calling out to a third party. That is necessary if you want to support or guard against reentrancy.

[...]

> To restate our same confusion, with these signatures, do we agree that A (and therefore alice) should never get access to the obj that bob passes to carol?

Yes.

I agree this guards against reentrancy. What about concurrency? IIUC, right now wasm threads only interact on mems as shared array buffers, where each wasm thread is in its own worker. Thus, right now, each module instance is in the one thread it was born into. Right now, there is no mechanism to share tables across threads, and thus each table is in the thread it was born into. Given these constraints, we don't need to worry about concurrent access to tables.

But I don't understand our plans for concurrency in wasm. In some of these plans, is there a danger that, while bob is transferring obj1 to carol, that alice might have spawned a thread that might be able to read obj1 out of the table before carol clears that table entry? If so, and if there's no reasonable way to fix it, then we can (further) disqualify option #1.

Given the transient manner in which these table entries are used, they seem most analogous to cpu registers used for parameter passing. All the copying and clearing is analogous to the reuse of registers across function calls. In other ways, of course, they are not analogous: they are statically allocated per exported function rather than per core, and there's no mechanism to give each thread its own registers for concurrent calls to the same function. Hence this new worry.

> embedder: instantiate module B, providing obj1 as B's "obj" import. B exports bob as "bob”.

It exports the function “bob” plus the associated parameter-passing tables, say as “bob-param1-buf” and “bob-param2-buf”.

> embedder: instantiate module C providing no imports. C exports carol as "carol”.

It exports the function “carol” and the associated table, say “carol-param-buf”.

> embedder: instantiate module A providing bob as "bob" and carol as "carol". A exports alice.

A imports, and is provided with, all three entities that B exports. It exports the function “alice” and the associated table, say “alice-param-buf".

Just being fully careful here to ensure I fully understand. A also imports both objects that C exports, the carol function and carol-param-buf, right?

 

> embedder: call alice with arguments (obj2, 77).

It sets alice-param-buf[0] to obj2 and calls alice(77).
Alice copies obj2 somewhere else and unsets alice-param-buf[0].

> alice: call bob with arguments (carol).

Alice sets bob-param1-buf[0] to the function carol, and bob-param2-buf[0] to (a reference to) table carol-param-buf, and then calls bob().
Bob copies both arguments somewhere else and clears the tables.

> bob: call carol with arguments (obj1).

Bob sets carol-param-buf[0] (as previously received and saved) to obj1 and calls carol().
Carol unsets the table entry.

(I’m not sure if this was meant to be the same obj1 that was used as an import descriptor above? If so, I’m not sure why the two should be related.)

Only for a pedagogical reason --- so that actions taken with obj1 could be output actions on the outside world, so that there's no question that it is important who can wield it.

> embedder: call alice again with (obj2, 77). Can alice obtain obj1?

Not if carol-param-buf[0] was properly unset (nulled out) by carol after receiving it, as shown in the previous step.


The setting and clearing tables in this protocol is kind of brittle, as all stateful approaches. If that is not reliable enough, there would be another option based on a fairly simple language extension: introduce read-only and write-only views of tables/memories as supertypes and allow a module to export as a supertype. Then all the table types in my examples would be write-only tables and only the originating module could read them. So D and E in your earlier example could not use F's table as a communication channel between them, since only F can read it. Similarly, alice could not read obj1 out of carol's table, even if it wasn't cleared by carol.

I see how this should work, and how it even prevents the specific concurrency danger above. But it has a dual concurrency danger: if alice can write into the buffers while bob's call to carol is in progress, she might be able to cause carol to receive obj2 rather than obj1 during this call from bob.

--

  Cheers,
  --MarkM

[Mark Miller]

[forwarding again]

On Tue, Nov 21, 2017 at 7:21 PM, Andreas Rossberg <ross...@mpi-sws.org> wrote:

> On Nov 21, 2017, at 21:19 , Mark Miller <eri...@gmail.com> wrote:
> I agree this guards against reentrancy. What about concurrency? IIUC, right now wasm threads only interact on mems as shared array buffers, where each wasm thread is in its own worker. Thus, right now, each module instance is in the one thread it was born into. Right now, there is no mechanism to share tables across threads, and thus each table is in the thread it was born into. Given these constraints, we don't need to worry about concurrent access to tables.
>
> But I don't understand our plans for concurrency in wasm. In some of these plans, is there a danger that, while bob is transferring obj1 to carol, that alice might have spawned a thread that might be able to read obj1 out of the table before carol clears that table entry? If so, and if there's no reasonable way to fix it, then we can (further) disqualify option #1.
>
> Given the transient manner in which these table entries are used, they seem most analogous to cpu registers used for parameter passing. All the copying and clearing is analogous to the reuse of registers across function calls. In other ways, of course, they are not analogous: they are statically allocated per exported function rather than per core, and there's no mechanism to give each thread its own registers for concurrent calls to the same function. Hence this new worry.

I think the way concurrency currently works (at least in the web embedding), you need to instantiate the modules separately in each thread (i.e., worker), so you already create separate per-thread copies of all the tables. But I’m not a 100% sure about respective future plans either.

> Just being fully careful here to ensure I fully understand. A also imports both objects that C exports, the carol function and carol-param-buf, right?

Ah, right.

> >The setting and clearing tables in this protocol is kind of brittle, as all stateful approaches. If that is not reliable enough, there would be another option based on a fairly simple language extension: introduce read-only and write-only views of tables/memories as supertypes and allow a module to export as a supertype. Then all the table types in my examples would be write-only tables and only the originating module could read them. So D and E in your earlier example could not use F's table as a communication channel between them, since only F can read it. Similarly, alice could not read obj1 out of carol's table, even if it wasn't cleared by carol.
>
> I see how this should work, and how it even prevents the specific concurrency danger above. But it has a dual concurrency danger: if alice can write into the buffers while bob's call to carol is in progress, she might be able to cause carol to receive obj2 rather than obj1 during this call from bob.

Yes, but I think any approach based on tables, and thus state, would have a potential problem with concurrency if you didn’t ensure that they are per-thread. I believe that is the case even for your original proposal.

/Andreas

--

  Cheers,
  --MarkM

[Mark Miller]

I agree that the status quo, where module instances, tables, and everything except mems are per thread (worker), and where the *only* synchronous interaction between threads is via "global" mems which are shared array buffers, is the better way to avoid concurrency hazards. Hopefully we'll hold to this line and not introduce concurrency hazards beyond those we've already accepted. Hopefully we'll hold this line even with wasm-gc, where all the heap-allocated managed objects are per thread (worker) as well, and where the only racy memory remains the "global" mems which are shared array buffers. Holding this line implies giving up the goal of compiling jvm or dot-net to wasm-gc where jvm or dot-net managed objects are mapped into wasm-gc managed objects. I would be happy with this outcome, but many would not be. So I proceed below assuming we lose this battle.

 

Yes, but I think any approach based on tables, and thus state, would have a potential problem with concurrency if you didn’t ensure that they are per-thread. I believe that is the case even for your original proposal.

In my original proposal, there is the mysterious allocation of a new index into a table. As long as this is atomic, i.e. that two concurrent allocations of a next index into the same table each get a unique index, then I don't see how my proposal suffers from concurrency hazards. Am I missing something? I ask not because I'm going back to advocating my original proposal, but because I want to understand the nature of the hazards that any proposal might have to think about.

-- 

  Cheers,
  --MarkM

[Mark Miller]

On Wed, Nov 22, 2017 at 7:13 AM, Andreas Rossberg <ross...@mpi-sws.org> wrote:

On 11/22/2017 06:00 AM, Mark Miller wrote:

In my original proposal, there is the mysterious allocation of a new index into a table. As long as this is atomic, i.e. that two concurrent allocations of a next index into the same table each get a unique index, then I don't see how my proposal suffers from concurrency hazards. Am I missing something? I ask not because I'm going back to advocating my original proposal, but because I want to understand the nature of the hazards that any proposal might have to think about.

Couldn't another thread come along and mutate the _source_ table before the callee is done copying from it?

In my proposal, neither the caller nor the callee does the copying. In fact, they can't because the caller does not have access to the callee's table and the callee does not have access to the caller's table. Either form of access would already be a fatal breach, as it would enable, respectively, the caller to access other entries of the callee's table, or the callee to access other entries of the caller's table. Rather, the invocation mechanism itself, during the call, copies an entry from the designated clist index in the caller's table to a newly allocated clist index in the callee's table; then passes, in that parameter position, that newly allocated clist index to the callee. 

* This is analogous to the IPC mechanisms of ocap microkernel operating systems (e.g. any of the KeyKOS family including seL4) where the caller tells the microkernel what capability arguments it wishes to pass by using clist indexes into its own clist, the callee tells the microkernel where it wants to receive passed arguments by using clist indexes into its clist, and the microkernel does the copying. What clist indexes they each use are unrelated. The important thing is that they end up referring to the same capabilities. (In these OSes, the receiving clist index can be specified by the callee, rather than having the kernel allocate a new index, because the IPC is rendezvous-based.)

* The corresponding language analogy substitutes "environment" (mapping from variable name to capability) for clist, and "variable name" for clist index. The code of a caller uses names in their scope to say what capabilities to pass. The callee uses names in its scope to say what names to bind these capabilities to. The names are unrelated, but they talk about the same capabilities. Neither caller nor callee ever has access to the other's environment or knows what names the other uses to talk about the same capabilities. (In languages, the receiving parameter name can be specified by the callee because it designates a newly allocated stack location rather than reusing a global variable of that name.)

But this all may be besides the point you're actually raising. Is your concern that another thread in the caller, while the call is in progress, might overwrite that table entry in the caller's clist before the call mechanism itself copies it? This is only a problem of the caller messing themselves up, which is a hazard that can lead to vulnerabilities but is not itself a vulnerability.

Anyone can always mess themselves up. By contrast, in my concurrency attack on option #1 compartment/instance A messes up and interaction between B and C that A should not have been able to influence. This is the kind of influence-over-another that I don't think my original proposal is vulnerable to.

--

  Cheers,
  --MarkM

[Mark Miller]

[forwarding again, though accidentally after my reply]

On Wed, Nov 22, 2017 at 7:13 AM, Andreas Rossberg <ross...@mpi-sws.org> wrote:

On 11/22/2017 06:00 AM, Mark Miller wrote:

In my original proposal, there is the mysterious allocation of a new index into a table. As long as this is atomic, i.e. that two concurrent allocations of a next index into the same table each get a unique index, then I don't see how my proposal suffers from concurrency hazards. Am I missing something? I ask not because I'm going back to advocating my original proposal, but because I want to understand the nature of the hazards that any proposal might have to think about.

Couldn't another thread come along and mutate the _source_ table before the callee is done copying from it?

/Andreas

--

  Cheers,
  --MarkM

[Mark Miller]

should be "... messes up an interaction ..."

 

between B and C that A should not have been able to influence. This is the kind of influence-over-another that I don't think my original proposal is vulnerable to.

--

  Cheers,
  --MarkM

--

  Cheers,
  --MarkM

[Mark Miller]

(Forwarding again)

On Wed, Nov 22, 2017 at 9:27 AM, Andreas Rossberg <ross...@mpi-sws.org> wrote:

On 11/22/2017 05:41 PM, Mark Miller wrote:

On Wed, Nov 22, 2017 at 7:13 AM, Andreas Rossberg <ross...@mpi-sws.org <mailto:ross...@mpi-sws.org>> wrote:

    On 11/22/2017 06:00 AM, Mark Miller wrote:

        In my original proposal, there is the mysterious allocation of a
        new index into a table. As long as this is atomic, i.e. that two
        concurrent allocations of a next index into the same table each
        get a unique index, then I don't see how my proposal suffers
        from concurrency hazards. Am I missing something? I ask not
        because I'm going back to advocating my original proposal, but
        because I want to understand the nature of the hazards that any
        proposal might have to think about.


    Couldn't another thread come along and mutate the _source_ table
    before the callee is done copying from it?

[...]

But this all may be besides the point you're actually raising. Is your concern that another thread in the caller, while the call is in progress, might overwrite that table entry in the caller's clist before the call mechanism itself copies it?

Yes, sorry for wording it sloppily.

This is only a problem of the caller messing themselves up, which is a hazard that can lead to vulnerabilities but is not itself a vulnerability.

Are you assuming that all callers follow the same strict conventions regarding their tables? In a hypothetical multi-threaded setting, other threads may have valid reasons to mutate a table. Clearly, that would demand for synchronisation, but it's not clear how source table mutations can be synchronised with calls under your proposal. The caller could take a lock on the table but it has no way of releasing it timely. AFAICS synchronisation would only work if it was part of the built-in parameter-passing mechanism, i.e., it would need to provide hooks for locking somehow -- which sounds scary.

/Andreas

--

  Cheers,
  --MarkM

[Mark Miller]

New proposal:

https://github.com/erights/wasm-linkage/blob/master/proposals/wasm-linkage/Baseline.md

Still rough, but I've been getting good reactions. Ready now for public commentary, either here on by opening issues on that github repository.

Thanks!

--

  Cheers,
  --MarkM