I have N ethernet frames where N is always < 256 and each ethernet frame, when serialized, will be < 1514 bytes.
I need to divide up the bytes in each ethernet frame into up to 15 “datagrams” where the datagrams can be variable length, up to the full size of the ethernet frame.
I do not want to allocate on the heap.
One could represent this like:
/// nobody will ever use more than 256 of these at once
pub const all_my_frames = [256]EthernetFrame{};
/// this can be at most 1514 bytes when serialized
pub const EthernetFrame = struct {
header: EthernetHeader,
/// there can be up to 15 of these in an ethernet frame
datagrams: []Datagram,
};
pub const Datagram = struct {
header: DatagramHeader,
/// this can be up to about 1500 bytes if this is the only
/// datagram in the ethernet frame
data: []u8,
};
The only issue with this is that its all pointers, so I still need to actually construct and destruct the data behind the slices.
My first inclination is to use a bounded array for data: [] u8, but to support 1500 bytes, I would need to nest these bounded arrays, resulting in:
1500 bytes data * 15 datagrams * 256 frames =
approx 5.7 MB of memory usage on the stack
Which is much more than what I nominally want to target, which is:
1500 bytes data * 256 frames =
approx 384 kB on the stack
And I would consider 5.7 MB of stack usage unacceptable since most stacks are limited to about 8 MB (I think). I would like to target < 1 MB.
(omitting the headers from the calculations for simplicity)
Also, if someone is stack memory limited to less than the 384 kB case, I plan to allow them to configure the 256 maximum allowable frames to 128 or whatever they want.
So my questions are:
How can I compact these variable length data structures without heap allocation?
Maybe I can have a 380 kB fixed buffer allocator in a struct or something and allocate on that? And use comptime to allow someone to configure its size?
(I havn’t touched allocators yet (I have only been using stack memory with bounded arrays). I have gotten very far with it, but I anticipate needing to use allocators and I expect some learning curve here.)
Right now, I’ve got all the nested data structures as the “slices all the way down” case.
Should I make a separate entity called a FrameBuilder perhaps that allows me to build these nested variable length data structures that returns pointers to its “owned / internally managed allocator”?
Then as you create new datagrams you increase datagrams_len and their data slice just indexes into the data that serves as a pool of memory shared by all datagrams.
This is what I was going to suggest as well. You can then have member functions to make getting a slice from the array/len pair convenient. Here’s an example of that sort of thing in the standard library:
I could do that, but if I leave datagram data as a slice, I am doing stack allocation without stack portability (the Ethernet frame will be invalid if returned from a function or passed as a parameter).
It feels a little weird to do the work of the len field without also getting stack portability.
I guess I could store both the end and start position of datagrams in the “data” field:
/// this can be at most 1514 bytes when serialized
pub const EthernetFrame = struct {
header: EthernetHeader,
datagrams: [15]Datagram,
datagrams_len: u8,
data: [1500]u8, // 1500-ish bytes
// no need to store len of data,
// if it not in a datagram,
// its not getting serialized
};
pub const Datagram = struct {
header: DatagramHeader,
// start and end position in parent "data" field
data_start: u16,
data_end: u16,
};
I decided to just go for the full stack portability to see how it feels.
One weird thing, is that it is awkward for me to access the datagram data as a slice, because the original data is part of the parent struct:
pub const EtherCATFrame = struct {
header: EtherCATHeader,
portable_datagrams: std.BoundedArray(PortableDatagram, max_datagrams),
data_store: [1500]u8,
const max_datagrams = 15;
/// Stack portable storage of a datagram.
/// This struct is packed only for reducing its size.
const PortableDatagram = packed struct(u128) {
header: Datagram.Header,
/// inclusive start of datagram data in parent data
data_start: u16,
/// exclusive end of datagram data in parent data
data_end: u16,
wkc: u16,
};
};
I could perhaps add a method to EtherCATFrame like so:
When thinking about this problem, I’m wondering what the primary data access pattern will be. It sounds like you would like to be able to copy Datagram data without relying on a reference to the EthernetFrame or the original Datagram.
Do you need to access the Datagram after it’s been constructed? I’m assuming, based on the first message, that you will need to keep (1, 256] EthernetFrames on the stack. Are you iterating over each Datagram once the EthernetFrame is constructed or will it be more likely random access? Do you need to compare or process different Datagrams across multiple EthernetFrames?
(I’m mostly ignorant with how Datagrams and internet protocal data)
Perhaps you could do the following:
pub const Datagram = struct {
header: DatagramHeader,
data: [1500]u8, // Datagram can have byte len of (0,1500]
};
pub const EthernetFrame = struct {
header: EthernetHeader,
// the total number of datagrams (0,15]
size: u4,
// for index i:size, stores the variable len of a datagram (0,1500]
lengths: [15]u11,
data: [1500]u8,
const DatagramIter = struct {
ef: *EthernetFrame,
i: u4,
pub fn next(self: *DatagramIter) []u8 {
return if (self.i < self.ef.size) {
defer self.i += 1;
self.get_datagrame_data(self.i);
} else null;
}
};
pub fn datagrame_iter(ef: *EthernetFrame) DatagramIter {
return .{ .ef = ef, .i = 0 };
}
/// Calculate the offset into the backing bytes and return a slice. From this you can
/// then make copies if you would like
pub fn get_datagram_data(ef: *EthernetFrame, i: u6) []u8 {
assert(i < ef.size);
var offset = 0;
for (ef.lengths[0..i]) |len|
offset += len;
return ef.data[offset..ef.lengths[i]];
}
/// The caller has to make space for the Datagram copy, whether it's from an allocator
/// or if you have it somewhere in the stack that is higher up
pub fn copyDatagram(ef: *EthernetFrame, i: u6, dest: *Datagram) anyerror!void {
// you can make this an error if the underlying data doesn't conform or if the
// header wrong
//
// do stuff with the header I'm guessing
@memcpy(&dest.data, ef.get_datagram_data(i));
}
};