OCaps and metering

[Mark S. Miller]

Normally ocaps are about access control. Metering is about excess control.

--

  Cheers,
  --MarkM

[Matt Rice]

On Mon, Aug 25, 2025 at 9:26 PM Mark S. Miller <eri...@gmail.com> wrote:
>
> Normally ocaps are about access control. Metering is about excess control.
>

Curious if there is a name for this notion of what to call behaviors
like metering, or consensus which is almost the inverse
in the sense that a metered capability diminishes over time as
invocation produces some decreasing side effect until it reaches a
limit.

Where consensus guarded capabilities provide no authority, until they
are unlocked via side effects thus their authority is increasing.
I generally just consider them propositions providing potential
authority, but never had a good name for the general concept
encompassing both mechanisms.

[Matt Rice]

Sorry... If it isn't clear what I mean by consensus in this, just
consider the shamir secret sharing
equivalent of a bunch of capabilities that need to be invoked before
invoking a separate capability
produces any effect.

[Matt Rice]

On Mon, Aug 25, 2025 at 9:26 PM Mark S. Miller <eri...@gmail.com> wrote:
>

> Normally ocaps are about access control. Metering is about excess control.
>

So to roll back to Marks original message, and part of the reason I ask what we
would call the general principle that encompasses both metering, and
this SSS-esque consensus,
is the first name that came to mind for this general principle was
something like: "predicated access"
or describing them as limits. The problem being that "predicated
access" seems like it is *entirely*
counter to the point that you are trying to make here. Hence my
attempt to weasel out of that by calling
them both forms of limits (which is admittedly kind of vague, but maybe works?)

E.g. if you were going to describe them in a chapter:

# Limits

* Metering
Meters are a limit on the usage of a capability such that the
resources are limited to being below a certain threshold.
* Consensus
Consensus capabilities ensure that the usage of a capability is
limited to such cases that consensus has been reached
that the capability provided should have any effect.

[Jonathan S. Shapiro]

On Mon, Aug 25, 2025 at 2:26 PM Mark S. Miller <eri...@gmail.com> wrote:

Normally ocaps are about access control. Metering is about excess control.

[Waves fist] Curse you Mark Miller!!!

Another quarter for the pun jar, please.

[Jonathan S. Shapiro]

I'm coming to this late, and I feel like there is a prior existing conversation that I don't have context on.

Are we talking about metering in the KeyKOS/EROS sense, or in some more general sense? One of the conclusions in EROS was that the meter tree was inconsistent with hard or soft real-time scheduling.

Jonathan

--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/cap-talk/CACTLOFpMpofB8ggUdGOwiXOdF-Ech13rfhPZAHucjA3qRYFbOw%40mail.gmail.com.

[Matt Rice]

No prior context really, just me being short on details because I felt
they were pretty irrelevant,
yes I was assuming mark meant something akin to meters in the
KeyKOS/EROS sense, or the gas
sense of blockchain. My point is that besides the obvious low-level
system tie-in of allocation/resource accounting
meters are a fairly general concept of adding a predicate check onto
an unsealer.

Without that low-level tie-in they can be made a general purpose concept.

Many CI systems for instance have a series of static analysis checks,
and code formatting checks.
all of which must pass for committing to be allowed.

When implemented as a general wrapper around a capability, this looks
much like metering in reverse,
where access is to the "commit" capability acts like a null cap, until
the code formatting checks, and the static analysis
checks all reach consensus that the "commit" capability should
actually be non-null.

A simple way to implement that is using a counter that increases and
returns a non null cap once the counter has
reached the consensus limit. In this case it doesn't really require a
meter tree, but can be some sort of wrapper cap
around CRUD

> To view this discussion visit https://groups.google.com/d/msgid/cap-talk/CAAP%3D3QNtHaUmPT9LPcXQsyYCkVnRxeKu5p-FLbArNfVzugzrPA%40mail.gmail.com.

[Jonathan S. Shapiro]

Reducing this to grossly oversimplified terms, here's a summary of where we ended up on KeyKOS meters.

The KeyKOS meter abstraction tacitly assumes that (a) scheduler time is arbitrarily subdivisible, and (b) in practice, scheduler time is non-monotonic. Under favorable conditions of execution pressure, these assumptions give you a dynamically adjustable form of proportional scheduling. The first assumption, in practice, is not correct; there is a minimum number of instructions that have to execute in order to dispatch a process, which translates on any given piece of hardware to a minimum number of usefully dispatchable picoseconds or microseconds. The second assumption means that you can't rely on execution at known times. Lest this be read in an over-negative light, real-time scheduling simply wasn't a thing in the context of 1970s time sharing platforms. If nothing else, the underlying hardware wasn't remotely fast enough. Nor was it fast enough in 1992 when we were putting the first versions of EROS together.

I definitely don't claim to have a solution to these issues in general, but I have a strong desire to be able to watch videos that don't blow their frame deadlines. Well, actually, I want the audio to sync right, which makes the video requirements look easy. Meters do not provide a contract about when (in a rate-periodic sense) you get scheduled. Then there's a question about what happens when when an inter-process communication passes from a source on schedule A to a recipient on [unrelated] scheduler B. Most solutions yield both bounded scheduler inversion and a variation of confused deputies in the time domain. I'm a decade out of date, but nothing that I recall from the scheduling research world addresses this (or really attempts to). The closest I know about is Borrowed Virtual Time (BVT), which seems very relevant but has some shortcomings that can be thought of as bounded priority inversions. This is one of those problems that will not admit of a solution until some excessively clever researcher re-frames the question.

Abstracting time is hard enough that the entire universe proceeds monotonically in submission. :-)

Coyotos was headed in a direction based on BVT, abandoning meters entirely. A key intuition here is that there is a de facto minimum number of cycles that can constructively be assigned to a process on a given platform. Below this minimum, the process doesn't get enough time to actually run. Not that you'd ever assign a duration this low intentionally, but it simplifies a bunch of the kernel data structures.

I'd have to re-immerse myself in the kernel scheduling implementation, but IIRC we implemented a simple priority scheduling system as an initial placeholder.

Jonathan

To view this discussion visit https://groups.google.com/d/msgid/cap-talk/CACTLOFpDgPmi8dsgN8fE-8K9GU4TaByquRiX6vc4_7aa-4DhxQ%40mail.gmail.com.

[Mark S. Miller]

Shortly after I joined Electric Communities, in some meeting I made some awful pun. Someone (Arturo I think) held up the pun jar and asked me to contribute a quarter. 

I tossed in a $20 bill saying "I'd like to prepay".

Between then and now, I'm sure I have exhausted the remaining balance ;)

--

  Cheers,
  --MarkM

[Mark S. Miller]

What do you think of the seL4 support for mixed criticality?

https://trustworthy.systems/publications/full_text/Lyons_MAH_18.pdf

https://www.youtube.com/watch?v=ijTTZgQ8cB4

https://sel4.systems/About/seL4-whitepaper.pdf chapter 5

To view this discussion visit https://groups.google.com/d/msgid/cap-talk/CAAP%3D3QNRbSfW2f1O%2B%3DnUHJj8yP3oHnJrZidTporVvkWybE667g%40mail.gmail.com.

--

  Cheers,
  --MarkM

[William ML Leslie]

On Tue, 26 Aug 2025 at 15:43, Jonathan S. Shapiro <jonathan....@gmail.com> wrote: 

I'd have to re-immerse myself in the kernel scheduling implementation, but IIRC we implemented a simple priority scheduling system as an initial placeholder.

It was a global queue with round-robin scheduling at the last public release, with a FIFO slot for replies.

We had lots of plans.  I'm still not confident which ones are the right ones.

Oh, and on mixed criticality: I know Shap voiced some reservations.  I don't mind the implementation that seL4 went with, but personally, I'd rather have reliable message delivery order.  If you can NBRecv from a select endpoint, you kind of already have everything you need to implement mixed criticality.

--

William ML Leslie

[William ML Leslie]

On Wed, 27 Aug 2025 at 12:30, William ML Leslie <william.l...@gmail.com> wrote:

On Tue, 26 Aug 2025 at 15:43, Jonathan S. Shapiro <jonathan....@gmail.com> wrote: 

I'd have to re-immerse myself in the kernel scheduling implementation, but IIRC we implemented a simple priority scheduling system as an initial placeholder.

It was a global queue with round-robin scheduling at the last public release, with a FIFO slot for replies.

Correction: the FIFO slot applies to the common case of call/return as a whole.  We only place the receiver at the back of the queue when we're not performing a receive phase, or in the case of pre-emption.

--

William ML Leslie