Welcome to the second part of getting UDP reliability into my engine. Now with connections complete, I need a way of tracking sequence ids between packets and store histories and all that jazz, but it turns out someone already did the hard work for me!. Of course I am talking about Gaffer on Games‘ reliability.io package. If I were doing this ‘for realsies’ I would just use the package as is, as it’s a standard C library I could wrap/call into from my code. But, I’m here to learn, so I’m going to take the opportunity to port it over to C++ and use classes, generics, std:vectors and everything else C programmers hate. You can view the translation of this code here.
I am absolutely sure the purists of C here will throw up in garbage bags but hey, let’s see what this could look like in C++.
There’s only three real struct‘s I need to concern myself with:
- reliable_sequence_buffer_t – This is our sequence buffer container. It has a number of functions that work on the members and holds packet data. We’ll be translating this to it’s own class.
- reliable_fragment_reassembly_data_t – Used for large packets > individual packet size.
- reliable_endpoint_t – The primary struct that manages connection/endpoints.
Todays post will just be covering translating reliable_sequence_buffer_t. Since Glenn is a professional game developer, you’ll notice he properly provides functionality to set custom allocators/deallocators. One thing to note is that this struct can contain ‘variable’ data types as a sequence of uint8_t bytes. Meaning you pass in the size of the objects you’ll be storing, then on insertion, it will allocate the necessary bytes inside of a C array.
In C++ we are going to model this as a generic templated class, allowing the caller to determine what type of data we will store in the SequenceBuffer‘s EntryData vector.
However, we don’t really need the allocation stuff, so reliable_sequence_buffer_create becomes the following constructor in C++:
template <class T>
class SequenceBuffer
{
public:
SequenceBuffer(int NumberOfEntries) : NumEntries(NumberOfEntries)
{
EntrySequence.resize(NumberOfEntries);
EntryData.resize(NumberOfEntries);
Reset();
};
...
private:
int NumEntries;
uint16_t Sequence{0};
std::vector<uint32_t> EntrySequence;
std::vector<std::shared_ptr<T>> EntryData;
};
We are going to use std::vector instead of C arrays here, so we resize them to the expected number of entries this buffer will hold.
The basic premise of this buffer is that we will use the modulo operator to rotate back to the beginning of the buffer as we fill it up when new sequence ids come in. To signal a sequence id or data location is ’empty’ will be done by filling that location with 0xFFFFFFFF in our EntrySequence.
Overall, the translation went pretty smoothly, but let’s call out some interesting points regarding C arrays with the following function:
void * reliable_sequence_buffer_find( struct reliable_sequence_buffer_t * sequence_buffer, uint16_t sequence )
{
reliable_assert( sequence_buffer );
int index = sequence % sequence_buffer->num_entries;
return ( ( sequence_buffer->entry_sequence[index] == (uint32_t) sequence ) ) ? ( sequence_buffer->entry_data + index * sequence_buffer->entry_stride ) : NULL;
}
This function takes in a buffer, and a sequence id. It creates an index by using the modulo operator on the provided sequence and the maximum number of entries (meaning it will loop around if sequence > num_entries. Checks that the index into the buffer actually equals the provided sequence id. If it does? It does some math-y looking stuff, otherwise it says nope, does not exist and returns null.
Let’s break down the math-y stuff. All it really is, is pointer arithmetic.
sequence_buffer->entry_dataThis is the pointer to our array of dataindex * sequence_buffer->entry_strideThis is the index, multiplied by the size of the expected object that is stored inside of the entry_data C array. Meaning if we stored:
struct some_data_t
{
uint16_t sequence;
}
entry_stride would equal 2 bytes (the size of a uint16_t). So if our index = 0, we start at the beginning of the entry_data buffer. If our index is 1, we start at the entry_data[2] byte of the buffer and so on.
In C++, I’m just using a std::vector. So all I need to do is get the index into the vector to get the value. Here’s the C++ version of the Find method (I am not fan of ternary ops, so I wrote it out in a if statement):
std::shared_ptr<T> Find(const uint16_t FindSequenceId)
{
int Index = FindSequenceId % NumEntries;
auto Exists = (uint32_t)EntrySequence[Index] == (uint32_t)FindSequenceId;
if (Exists)
{
return EntryData[Index];
}
return nullptr;
};
You’ll note I don’t need to do any pointer arithmetic, all my values are created/inserted into the vector like this:
int Index = InsertSequenceId % NumEntries;
EntrySequence[Index] = InsertSequenceId;
auto Val = std::make_shared<T>();
EntryData[Index] = Val; // <-- that's it, no uint8_t bytes, just a pointer
return Val;
There was only one major hang-up when translating this struct and it’s functions to C++, and that was this little bad guy:
sequence_buffer->entry_sequence[index] == (uint32_t) sequence
When I wrote my Reset() method, I accidentally wrote 0xFF instead of 0xFFFFFFFF:
void Reset()
{
Sequence = 0;
std::fill(EntrySequence.begin(), EntrySequence.end(), 0xFF); // should be 0xFFFFFFFF
EntryData.clear();
}
What this meant was when the sequence ID was 256… or 0xff, the find function kept returning a data entry even though one didn’t exist (it should have returned a nullptr), this was after the Reset was called!
While writing this blog post I actually figured this out and fixed it by properly calling std::fill with 0xFFFFFFFF, so, yay documenting!
So that’s the first struct down. Thankfully he included tests so I am able to test my code against his unit tests and ensure things are working as expected. So thanks for that Glenn!
Next time I’ll be covering translating the endpoint and fragmentation handling code, I am looking forward to learning how it works!
a place to jot 