Memory allocation improvements

[richiware]

To be able to use this product in critical systems, the product must not be allowed to allocate or free memory during its execution.
It has to either use static memory or allocate the memory at the creation of the entities (participant, writer, reader...).

We can describe the following formal requirement:

It must be possible to configure the product in a way that no (de)allocations should happen after the local participants, publishers, and subscribers have been created.

Basic strategy

Resource-limited STL containers

There are several places where the number of elements present on STL containers depends on the discovered number of participants/publishers/subscribers.
For these cases, several approaches may be considered:

1. Create custom containers wrapping the STL containers and adding configurable resource limits.
2. Use something like this library and let the user set the pools configuration.
3. Add traits on participant/publisher/subscriber creation methods to let the user select the allocators used for STL containers and/or the container types themselves.

All these options are compatible and can be addressed one on top of the other.
The first one provides control over the number of elements to be used in the internal data collections and can be designed with an API similar to other QoS of the product.
The second one would allow the user to control the total amount of memory to be used in an easy way but would add an additional dependency to the project.
The third one would provide the most flexibility but would imply to spread the traits through a high number of classes.

As DDS compliance API is on our roadmap, we will leave the decision for the third approach until we address that feature, and start with the first approach only.
The STL wrappers would be ready for the other approaches, having the corresponding traits on the wrapping container and the allocator used.

This strategy will be used for every std::vector<GuidPrefix_t>, std::vector<ParticipantProxyData*>,
std::vector<WriterProxyData*>, std::vector<WriterProxy*>, std::vector<RemoteWriterAttributes>,
std::vector<ReaderProxyData*>, std::vector<ReaderProxy*>, std::vector<RemoteReaderAttributes>,
std::vector<ChangeForReader_t>, std::vector<ChangeFromWriter_t>, std::vector<Locator_t>, std::set<RTPSWriter*> and the maps on RTPSReader.

Specific design below

Strings and other STL containers

• The std::string attributes on ParticipantProxyData, ReaderProxyData and WriterProxyData will be transformed into fixed_string<255>.
• The std::vector<SequenceNumber_t> on SequenceNumberSet_t and the std::vector<FragmentNumber_t> on FragmentNumberSet_t will be transformed into bitmaps of a static size.
• Class ParameterList_t and its std::vector<Parameter_t*> will be removed.
• The std::vector<uint32_t>* on CacheChange_t, the std::unordered_multiset on FragmentedChangePitStop and the std::set<FragmentNumber_t> on ChangeForReader_t will be removed as part of the fragment management refactor.
• Template class RTPSWriterCollector and its std::set<RTPSWriterCollector::Item> will be removed as part of the flow controllers refactor.
• All std::string and std::vector on Property, BinaryProperty and PropertyPolicy classes will be removed as part of the properties refactor.

Specific design

Resource limited collections [#386, #406, #423, #479]

A new struct ResourceLimitedContainerConfig with initial, maximum and increment fields of type size_t. Setting the same value on initial and maximum will define a preallocated policy.

Several QoS policies of type ResourceLimitedContainerConfig will be added:

• matchingReaderNumberQos on WriterAttributes
• matchingWriterNumberQos on ReaderAttributes
• remoteParticipantNumberQos on RTPSParticipantAttributes
• readerNumberQos on RTPSParticipantAttributes
• writerNumberQos on RTPSParticipantAttributes

A wrapper of std::vector will be developed:

template <class T,
   class Alloc = std::allocator<T>,
   class Vec = std::vector<T, Alloc>>
class ResourceLimitedVector;

Only need following functionality:

• Constructor receiving a ResourceLimitedContainerConfig
• Adding elements: T* push_back() (copy and move) and T* emplace_back(...)
• Removing elements: bool remove(const T&) and bool remove_if(predicate)
• Traversing the collection: begin, end
• Other basics as empty, clear, size, capacity

Fixed size strings [#361]

A template<size_t N> fixed_string class containing an array of N + 1 characters will be developed.
Only basic operations are necessary:

• Basic construction (empty, copy, move)
• Construct from a const char* / std::string
• Converters to const char* / std::string
• Assignment operators from fixed_string / const char* / std::string
• Equality comparisons with fixed_string / const char* / std::string

Fixed size bitmaps [#370]

A template<class T, size_t NBITS=256> BitmapRange class will be developed.
Type T is required to behave like an unsigned integer type, and shall at least have addition with size_t,
post-increment and comparison operators.
The BitmapRange class will have the following fields:

// Alias to improve readability.
using bitmap_type = std::array<uint32_t, (NBITS + 31) / 32>;

T base;              // Holds first item in the range.
bitmap_type bitmap;  // Holds bitmap.
size_t num_bits;     // Number of significant bits set in the bitmap.

Required functionality:

• Default/copy/move constructors
• Constructor from base: explicit BitmapRange(const T& base)
• Copy/move assignment operators
• Getter for base
• Add an item: bool add(const T& item)
• Bitmap getter for serialization: void bitmap_get(size_t& num_bits, bitmap_type& bitmap, size_t& num_longs_used)
• Bitmap setter for deserialization: void bitmap_set(size_t num_bits, const uint32_t* bitmap)

Removing ParameterList_t [#379]

All *ProxyData classes will have a bool writeToCDRMessage(CDRMessage_t* msg, bool write_encapsulation) method instead of their current AllQostoParameterList or toParameterList, that will create each Parameter_t as a local variable and serialize it directly on the destination message.
This is consistent with their current readFromCDRMessage method and avoids the use of a ParameterList_t

The signature of ParameterList::readParameterListfromCDRMsg will be changed to bool readParameterListfromCDRMsg(CDRMessage_t* msg, std::function<void (const Parameter_t*)> processor, bool use_encapsulation, uint32_t& qos_size).
It will parse each of the parameters received on the message using local variables (stack allocated) and pass each of them to the function received.

New bool ParameterList::updateCacheChangeFromInlineQos(rtps::CacheChange_t& change, rtps::CDRMessage_t* msg, uint32_t& qos_size) method that will directly parse the received inline qos, parameter by parameter.

Flow controllers refactor

Current interface on flow controllers is as follows:

virtual void operator () (RTPSWriterCollector<ReaderLocator*>& changesToSend);
virtual void operator () (RTPSWriterCollector<ReaderProxy*>& changesToSend);

We want to get rid of RTPSWriterCollector by changing the interface to:

// InputIt               template  an input iterator to ChangeForReader_t
// [first, last]         input     range of all pending changes
// last_change           output    points to the first change that cannot be completely sent
// num_fragments_allowed output    indicates the number of fragments allowed to be sent for the change
//                                 pointed to by last_change
template <typename InputIt>
virtual void operator () (InputIt first, InputIt last, InputIt& last_change, size_t& num_fragments_allowed);

Class RTPSWriter will have a ResourceLimitedVector<ChangeForReader_t> with the queue of changes pending to be sent, and child classes StatelessWriter and StatefulWriter will manage the queue accordingly.
The resource limits configuration of the pending queue will be automatically calculated based on the resource limits of the writer's history.

[MiguelCompany]

@dejanpan FYI, work in progress

[vmayoral]

@ahcorde and @carlossv, ping

[deeplearningrobotics]

@richiware, @MiguelCompany:
Regarding ResourceLimitedVector:

1. Why do you only provide a limited subset of the std::vector functionality?
2. What other containers to you plant to use with it? I see it not working on any other container which allocates memory on an item by item base. There an allocator would be enough.

Would it make sense to replace the std::vector occurrences in your code with a vector implementation that behaves exactly like a std::vector just with a fixed size (and is non-copyable)?

[MiguelCompany]

1. Why do you only provide a limited subset of the std::vector functionality?

This is going to be part of Fast-RTPS internals, thus we are only providing the functionality that is currently being used in the code of Fast-RTPS. We don't plan to export this as a general-purpose library.

2. What other containers to you plant to use with it? I see it not working on any other container which allocates memory on an item by item base. There an allocator would be enough.

I agree. The idea for other containers, like map or set is to configure the allocator based on the values of ResourceLimitedContainerConfig

Would it make sense to replace the std::vector occurrences in your code with a vector implementation that behaves exactly like a std::vector just with a fixed size (and is non-copyable)?

You can check the implementation on #386. It cannot have a fixed size, as we want the user to configure the allocation behavior by setting values on participant, writer and reader attributes.

Regarding the non-copyable pattern, as we may have items of a vector having vectors inside, we may sometimes need them to be copied.

[deeplearningrobotics]

@MiguelCompany:

You can check the implementation on #386. It cannot have a fixed size, as we want the user to configure the allocation behavior by setting values on participant, writer and reader attributes.

This use case is not clear to me. I would say users accept or do not accept memory allocation during steady time. Can you explain me the use case for initial < maximum in #386.

[MiguelCompany]

@deeplearningrobotics:

This use case is not clear to me. I would say users accept or do not accept memory allocation during steady time. Can you explain me the use case for initial < maximum in #386.

The user may accept memory allocation on steady time, but have some knowledge about typical values, thus wanting to configure an initial allocation on creation. For instance, if we have 50 robots in a big warehouse, but we know that typically only 10 are within communication range, we may use an initial value of 10 and a maximum value of 50.

[deeplearningrobotics]

@MiguelCompany: Why should he not reserve 50 in the first place? Memory usually never freed from a vector, shrink_to_fit is not supported by your implementation and not even guaranteed to do anything in the C++ standard. So either the user has enough memory for the maximum amount of entities or he will run into a bad_alloc at some point.

Just trying to understand the exact requirement.

[MiguelCompany]

@deeplearningrobotics: You may be right for the case I exposed. But there is at least one other case which is not having a maximum limit but having an initial reserved value.

In commit 65ee6a065181ba499ee546277e907fac90605a06, I have added the configuration struct as a template parameter, so if we consider it necessary in the future, we could specialize the template for a size_t on that parameter and then use an implementation based on std::array.

[nickolai-voyage]

For fixed size string and vectors, have you considered using the embedded template library? https://www.etlcpp.com/string.html. It seems like a great opportunity to capitalize on an existing project that could be re-used by others as well.