Allowed Process Slice Buffered API #4023

alexandruradovici · 2024-06-07T08:05:16Z

Pull Request Overview

This pull request adds a ringbuffer like API to the WritableProcessSlice and ports the can driver to use it.

This is connected to #3252 and #3258.

The problem

As of Tock 2.1, drivers are not in charge of handling these system calls, but the kernel performs them in the driver's name. This makes drivers unaware of what happens with an application's upcalls and buffers. While most drivers do not need this information, some drivers might want to know when a an application swaps a buffer.

Applications are not allowed to access buffers while they are shared with a driver. In most cases, when an application swaps out a buffer (either unallows it, either provides a replacement for it) it means that the application is consuming the provided data. An example of such behaviour is the touch driver and the can driver.

touch - the driver receives touch events and places them into a readwrite allowed buffer and notifies the application using an upcall. When the application needs to consume the buffer, it has to swap it out with an empty one. This notification function provides the means to inform the driver that the application has swapped the buffer and that the driver has a new buffer in which it can place a new set of events.
can - the driver uses the buffer to store incoming packets back to back. The driver could keep the current buffer head position in application's grant, but has now way of knowing when the buffer was swapped. Proposed solutions for this are syscall: add notification mechanism #3252 and Add attributes to shared buffers #3258. Both of them do increase code size and seem to generalise a specific problem.

In both cases, the application could issue a supplementary command system call to inform the driver about the consumption of the buffer. This leads to a data race, as there capsule might execute in between the application's allow and command.

Solution

The implementation from this pull request provides a simple mechanism, that does not need any kernel changes and seems to keep code size the same as long as it is not used. It uses the first four bytes of the buffer to keep the current buffer head position and a checksum for the index. The checksum is necessary as applications might not initialise the buffer correctly or simply not initialise it at all, placing random data in the first four bytes.

The format of the buffer is described below:

0          1          2          3          4          5
+----------+----------+----------+----------+----------+-------------------...
| flags    | buffer length                             | slice
+----------+----------+----------+----------+----------+-------------------...
| 00000000 | 32 bits little endian                     | data

the first byte is reserved to store flags, for this version of the buffer the value has to be 0
the next 4 bytes store the used space in a 32 bit little endian format

Advantages

no kernel changes are required
the buffer functions should be optimised out by the compiler if they are not used
the capsules can use the buffer as before or just use them as ring buffers with the new API

Disadvantages

in the current layout, the buffer length is limited to 16 MB (2^24 B), this could be extended if the checksum is decreased to a smaller number of bytes
the application still has to clear a previously used buffer:
- buffer1 is shared, it contains either full 0 either random data, the drivers detects the failed checksum and resets the buffer position
- buffer2 is shared while buffer1 is swapped out, it contains either full 0 either random data, the drivers detects the failed checksum and resets the buffer position
- buffer1 si shared while buffer2 is swapped out, this is where the problem arises. If the application does not reset the buffer length, it will contain a valid checksum and a position different from 0. The driver will write to it starting from the previous position, instead of writing from the beginning.

Testing Strategy

This pull request was not yet tested.

TODO or Help Wanted

Feedback

Documentation Updated

Updated the relevant files in /docs, or no updates are required.

Formatting

Ran make prepush.

bradjc

This makes sense to me.

Two questions:

What is the "ring"?
If the length starts at 0, the xor of 0,0,0 is 0, and a blank (ie all 0) buffer will pass the check. Is that intentional?

kernel/src/processbuffer.rs

bradjc · 2024-06-07T13:45:43Z

kernel/src/processbuffer.rs

+    pub fn append_to_ringbuffer(&self, data: &[u8]) -> Result<(), ErrorCode> {
+        let len = self.ringbuffer_len()?;
+        if data.len() + len <= self.slice.len() {
+            self[len..len + data.len()].copy_from_slice(data);
+            self.set_ringbuffer_len(len + data.len())?;
+            Ok(())
+        } else {
+            Err(ErrorCode::SIZE)
+        }
+    }


Given where this code lives (core kernel), if we go with this approach I think this should be rewritten with .set() and not with [].

I am not sure I follow this.

phil-levis · 2024-06-07T15:23:54Z

Can you explain the reasoning behind the XOR? Is there a concern about concurrent access, and this tries to ensure that the kernel knows when the length value is in an inconsistent state? What does the kernel do if this is the case? This seems like it will lead to a need or DeferredCalls.

Another approach is to use a u32 and require using atomic writes of the value (which is easier with a u32)?

Being sure it is a correct ring buffer would seem better served by having a magic value?

bradjc · 2024-06-07T16:46:42Z

I think we should drop the XOR and use a 4 byte length. Applications really need to initialize this correctly. Maybe not on the first allow, but applications need to reset the length after reading from the buffer before the app re-allows the buffer.

lschuermann · 2024-06-07T16:53:14Z

Talked about this on the core call; this should not be called "ring buffer". Really the benefits here are that this enables streaming of packets and/or raw data, and it implements a queue, and so the name should presumably reflect that.

As an aside, I think that the implementation should probably be its own wrapper type around a ProcessSlice, and not extend the types in processbuffer.rs. That file, and the types contained therein, use unsafe extensively and should avoid providing too many high-level abstractions. I don't see a reason why this would need to be unsafe and couldn't just use the existing abstractions in the form of a wrapper type.

bradjc · 2024-06-07T17:18:19Z

capsules/extra/src/can.rs

@@ -461,36 +460,20 @@ impl<'a, Can: can::Can> can::ReceiveClient<{ can::STANDARD_CAN_PACKET_SIZE }>
                                        buffer_ref
                                            .mut_enter(|user_buffer| {


@lschuermann Do we need a different API here then? How does a capsule get an object of the wrapper type?

Given that our grant API yields a ReadOnlyProcessBuffer reference, I was thinking that we can just wrap this type into $ThisPRsTypeName(ReadOnlyProcessBuffer) that then exposes the APIs proposed here.

We'd rely on capsules correctly wrapping the process buffers prior to interacting with them, but that's similar to how we currently trust capsules to actually enforce their driver API contracts.

That makes sense to me.

Ok, so if you want to use the ProcessBufferSlice as a Buffer, wrap it first into a Buffer type?

bradjc · 2024-06-07T17:21:59Z

WriteableProcessSliceAppendable? WriteableProcessSliceBuffered?

bradjc · 2024-06-07T17:35:10Z

Ok bear with me for a second:

What if we make this functionality the default, and make applications/drivers opt-out (I'm not exactly sure how they opt out, but let's ignore that for now). Capsules then get allow buffers that "start" (at least as far as the API they have to use the allow buffer is concerned) wherever they last wrote to (or the beginning if the buffer was just allowed).

Even if we don't make it the default, can we just have the process slice implementation do all the length tracking? That way we wouldn't need to the application to clear the length field, it would just happen on the allow syscall. Also, the capsule doesn't need to do anything, it just writes to the buffer like it always has (it would just happen to write to the middle of the buffer sometimes).

Note: I'm concerned this idea is crossing over the "magic" threshold too far. It's just that capsules are already so hard to write, this would simplify something.

8000

Co-authored-by: Brad Campbell <bradjc5@gmail.com>

bradjc · 2024-06-10T16:56:41Z

After reading through #4024, I think the main question is: do we make any changes to the kernel to support this?

I lean towards no, with potentially one exception. The main functionality can be done in the capsule. The capsule can track where in the buffer it is, and only issue an upcall after the first write. Userspace is expected to do "atomic" buffer swaps (ie after an upcall call allow only once with the new buffer, rather than something like an "unallow" and then later doing an allow). Really then what this PR would accomplish is creating a standard way for handling this so individual capsules don't have to re-invent the process.

The exception I'm thinking about is: it would be convenient to have the kernel reset the header metadata when a new buffer is allowed. The capsule cannot do this and must entirely rely on the application to reset this. It would be very easy for an app to forget to do this. It would also be trivial for the core kernel to do this. However, having the kernel do this would require some way to configure an allow as one where the kernel should do this. I'm not sure that overhead is worthwhile.

bradjc · 2024-06-10T16:58:37Z

Also after reading through #4024, it might be easiest to specify only a minimum header: say a 4 byte length. Anything extra (overflow bit, version, type of overflow, number of packets, etc.) could be capsule/driver specific.

alexandruradovici · 2024-06-26T17:32:22Z

The exception I'm thinking about is: it would be convenient to have the kernel reset the header metadata when a new buffer is allowed. The capsule cannot do this and must entirely rely on the application to reset this. It would be very easy for an app to forget to do this. It would also be trivial for the core kernel to do this. However, having the kernel do this would require some way to configure an allow as one where the kernel should do this. I'm not sure that overhead is worthwhile.

This is a little tricky. We need to make sure that the use case is the kernel sending data to the app and not vice-versa. If we have write-only buffers, this would be clear.

lschuermann · 2024-07-05T23:21:13Z

The exception I'm thinking about is: it would be convenient to have the kernel reset the header metadata when a new buffer is allowed.

I thought we talked about this on the calls and reached agreement that, while the app can forget to do this, this will not meaningfully impact the kernel. Capsules will always have to perform appropriate length checks, and just start writing at the specified offset -- and if the app forgets to change the header or (for any reason) deliberately does not reset the offset, the capsule will need to simply discard pending data.

I don't think this is something that the kernel should concern itself with, and I think that it's an easy but obvious mistake to make: swapping buffers is as easy as making an allow system call, and the only thing an app to do is zero the first couple bytes of this buffer before it's allowed. It's a single operation in an app's source, and it will break more or less immediately after the first few buffer swaps.

bradjc · 2024-07-07T03:40:39Z

The exception I'm thinking about is: it would be convenient to have the kernel reset the header metadata when a new buffer is allowed.

I thought we talked about this on the calls and reached agreement that, while the app can forget to do this, this will not meaningfully impact the kernel. Capsules will always have to perform appropriate length checks, and just start writing at the specified offset -- and if the app forgets to change the header or (for any reason) deliberately does not reset the offset, the capsule will need to simply discard pending data.

I don't think this is something that the kernel should concern itself with, and I think that it's an easy but obvious mistake to make: swapping buffers is as easy as making an allow system call, and the only thing an app to do is zero the first couple bytes of this buffer before it's allowed. It's a single operation in an app's source, and it will break more or less immediately after the first few buffer swaps.

I generally agree, it's just a little odd for the kernel to defer something so trivial that would break the operation of the capsule. From the application's point of view, the kernel can only do the correct thing if the application zeroes the buffer. This is because of valid reasons within the kernel and how it's implemented, but I think it's still a fairly strange API that the capsule would rather break than just initialize the buffer on behalf of the application.

lschuermann · 2024-07-07T14:49:40Z

I think it's still a fairly strange API that the capsule would rather break than just initialize the buffer on behalf of the application.

I view it the other way around: the capsule works as intended. It does not permanently break, it just continues writing at the old offset; if there's no more space available it buffers or discards data. Userspace can, at any time, share a new buffer or reset the offset, and the capsule will continue writing data. This is not an edge case that can only occur when userspace doesn't reset the offset, it's a perfectly normal thing to happen during normal operation as well. I think this constitutes a significant part of the elegance and simplicity of this API: userspace tells capsule where to write, capsule writes and increments current offset.

The freedom for userspace to select where the capsule starts writing can even be a feature, for instance for capsules that do internally buffer, where now userspace can "peek" into the buffer and re-allow it for the capsule to continue writing at the old offset. I think that's a more fringe use-case, but the simplicity of this API makes that possible.

bradjc · 2024-07-07T23:36:32Z

I think you make a good point, I just think userspace is better off not having to manage this complexity. It adds another step in the learning curve as some buffers you can just allow and now others you have to zero. Also, I don't really see why we need to support allowing userspace to ask the kernel to write to the middle of the buffer.

lschuermann · 2024-07-08T13:48:15Z

Okay, I can see both arguments. My proposal for a way to move forward with this is to -- for now -- not reset offsets on a re-allow. We don't have a mechanism for this, and introducing one on the core-kernel level would raise similar concerns as with #3258. Then we can see how useful this feature would be and, given sufficient motivation, implement a solution in a follow-up PR.

I think what this PR proposes right now is very simple at its core, shouldn't need to touch the core kernel at all, and has been extensively discussed. In other words, as soon as we have an implementation that is a wrapper around a process buffer struct I think this should be good to go any time.

bradjc · 2024-07-08T13:54:10Z

I agree. I would like to see documentation that says that userspace must reset the header by zeroing it. That gives us more flexibility going forward.

hudson-ayers · 2024-08-30T16:25:48Z

08/30 update: this design is not fully implemented, that is the next step for this PR

alexandruradovici · 2024-09-23T18:35:45Z

I think I made all the requested modifications.

alexandruradovici · 2024-10-09T15:32:24Z

I don't know why those checks fail, but the required ones seem to pass. I think this is good to go.

lschuermann · 2024-10-09T15:51:26Z

Netlify appears to be failing because of these warnings which are unrelated to this PR:

4:27:20 AM: warning: /opt/build/repo/libraries/enum_primitive/Cargo.toml: no edition set: defaulting to the 2015 edition while the latest is 2021
4:27:20 AM: warning: /opt/build/repo/libraries/tock-cells/Cargo.toml: no edition set: defaulting to the 2015 edition while the latest is 2021

This PR is branched off of a relatively old commit which did not include these edition definitions in the Cargo.toml files, and Netlify apparently builds based off the pushed revision, not the merged result. Rustdoc shows no other errors, and thus these checks should succeed once this is merged.

bradjc

This looks good.

bradjc · 2024-10-09T17:22:36Z

kernel/src/processbuffer.rs

+// the offset where the buffer data starts
+// - skip the flags field (1 byte)
+// - skip the len field (size_of::<u32>() bytes)
+const BUFFER_OFFSET: usize = 1 + size_of::<u32>();


Can we move this into the impl ala https://github.com/tock/tock/blob/master/kernel/src/process_standard.rs#L1300?

I'm working on a small refactor that includes this change.

bradjc · 2024-10-09T17:22:52Z

kernel/src/processbuffer.rs

@@ -886,6 +892,96 @@ pub struct WriteableProcessSlice {
    slice: [Cell<u8>],
 }

+#[repr(transparent)]
+pub struct ProcessSliceBuffer<'a> {


Need comment.

lschuermann

@alexandruradovici I think this is great. The interface seems right to me, and the code looks good too. One minor change that I'd make is rename the "length" field to "offset", to distinguish it from the underlying buffer's length.

Also, I took the liberty to do some refactoring of this code with the goal of removing all* possibly panicing index operations from the code. Process buffers are an area where it's really easy to make mistakes, and Rust's combinators often provide clean and concise ways to express your goals while also reducing dynamic control flow and potential panic points. Here's the code -- have a look, and if it's good to you feel free to pull it in: ~~lschuermann@430e3cd~~

Edit: @cherrypiejam reported some indexing bugs of my version (and a slightly incorrect ASCII figure), here's an updated version: lschuermann@344024b

Finally, I think that I'd like to see this moved out of the processbuffer.rs file. That file is complex enough as it is, and littered with unsafes. Given that this infrastructure does not require either unsafe, nor any changes to the core process buffer infrastructure (pretty cool!), I'd rather we move it to some other file like utilities/process_slice_buffer.rs or something like that. Thoughts?

bradjc · 2024-10-09T18:46:49Z

Given that this infrastructure does not require either unsafe, nor any changes to the core process buffer infrastructure (pretty cool!), I'd rather we move it to some other file like utilities/process_slice_buffer.rs or something like that. Thoughts?

I support this.

Also, what do we call this? Process slices are already buffers. ProcessSliceWithHeader?

bradjc · 2024-10-18T16:35:37Z

StreamingProcessSlice?

Add `StreamingProcessSlice` helper, based on `ProcessSliceBuffer` design (#4023)

brghena · 2024-11-11T03:35:48Z

Handled in #4208

Patched from url: github.com/lschuermann/tock rev: 430e3cd

first iteration of a ringbuffer api

d79e214

github-actions bot added kernel WG-Network In the purview of the Network working group. labels Jun 7, 2024

bradjc reviewed Jun 7, 2024

View reviewed changes

github-actions bot assigned bradjc Jun 8, 2024

Update kernel/src/processbuffer.rs

7b2c829

Co-authored-by: Brad Campbell <bradjc5@gmail.com>

alexandruradovici changed the title ~~Ringbuffer API~~ Buffer API Jun 10, 2024

updates

ce6d6d1

bradjc changed the title ~~Buffer API~~ Allowed Process Slice Buffered API Jun 11, 2024

This was referenced Jul 8, 2024

Add attributes to shared buffers #3258

Closed

syscall: add notification mechanism #3252

Closed

alevy added the waiting-on-author label Aug 30, 2024

use a seperate structure and rename the buffer

080bdf5

format doc

ea53b0f

alexandruradovici requested review from bradjc and lschuermann September 23, 2024 18:38

alexandruradovici added 3 commits September 24, 2024 11:17

make clippy happy

27f578c

use constant

ecc265f

use inspect_err

dd553c3

alexandruradovici removed the waiting-on-author label Oct 9, 2024

bradjc reviewed Oct 9, 2024

View reviewed changes

lschuermann reviewed Oct 9, 2024

View reviewed changes

lschuermann mentioned this pull request Oct 20, 2024

Add StreamingProcessSlice helper, based on ProcessSliceBuffer design (#4023) #4208

Merged

2 tasks

github-merge-queue bot pushed a commit that referenced this pull request Nov 1, 2024

Merge pull request #4208 from lschuermann/dev/streaming-process-slice

7d9d16b

Add `StreamingProcessSlice` helper, based on `ProcessSliceBuffer` design (#4023)

brghena closed this Nov 11, 2024

cherrypiejam added a commit to cherrypiejam/tock that referenced this pull request Feb 10, 2025

Experiment ProcessSliceBuffer discussed in tock#4023

db944da

Patched from url: github.com/lschuermann/tock rev: 430e3cd

		@@ -461,36 +460,20 @@ impl<'a, Can: can::Can> can::ReceiveClient<{ can::STANDARD_CAN_PACKET_SIZE }>
		buffer_ref
		.mut_enter(\|user_buffer\| {

Allowed Process Slice Buffered API #4023

Allowed Process Slice Buffered API #4023

Uh oh!

Conversation

Uh oh!

Pull Request Overview

The problem

Solution

Advantages

Disadvantages

Testing Strategy

TODO or Help Wanted

Documentation Updated

Formatting

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!