Skip to content

Fixed size bitmaps [4320]#370

Merged
richiware merged 10 commits intofeature/safety-critical-systemsfrom
feature/fixed-size-bitmaps
Jan 16, 2019
Merged

Fixed size bitmaps [4320]#370
richiware merged 10 commits intofeature/safety-critical-systemsfrom
feature/fixed-size-bitmaps

Conversation

@MiguelCompany
Copy link
Copy Markdown
Member

@MiguelCompany MiguelCompany commented Jan 9, 2019

Fixed size bitmaps

A template<class T, class Diff = DiffFunction<T>, size_t NBITS=256> BitmapRange class holding a bitmap on a fixed size array of uint32_t.
Type T is required to behave like an unsigned integer type, and shall at least have addition with uint32_t and >= 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.

Operations implemented:

  • Default constructor
  • Constructor from base: explicit BitmapRange(const T& base)
  • Getter and setter 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)
  • Basic traversal void for_each(UnaryFunc f)

@MiguelCompany
Copy link
Copy Markdown
Member Author

MiguelCompany commented Jan 9, 2019

CC @dejanpan

@deeplearningrobotics
Copy link
Copy Markdown

deeplearningrobotics commented Jan 9, 2019 •
edited
Loading

@MiguelCompany: Why do you not just use a static vector implementation?

@MiguelCompany
Copy link
Copy Markdown
Member Author

MiguelCompany commented Jan 10, 2019

@deeplearningrobotics: SequenceNumberSet and FragmentNumberSet are serialized as bitmaps as per RTPS 9.4.2.6. The implementation used here is designed to match the serialization procedure, so the internal array could be directly copied into the RTPS message. That is also the reason std::bitset is not used, as we cannot rely on the internal implementation details.

@MiguelCompany MiguelCompany changed the title Fixed size bitmaps Fixed size bitmaps [4305] Jan 10, 2019
@richiware richiware mentioned this pull request Jan 10, 2019
Closed
@richiware
Copy link
Copy Markdown
Member

richiware commented Jan 11, 2019

Build status:

  • Linux Build Status
  • Mac Build Status
  • Windows Build Status

@richiware
Copy link
Copy Markdown
Member

richiware commented Jan 11, 2019

Build status:

  • Linux Build Status
  • Mac Build Status
  • Windows Build Status

@MiguelCompany MiguelCompany changed the title Fixed size bitmaps [4305] Fixed size bitmaps [4320] Jan 11, 2019
@richiware
Copy link
Copy Markdown
Member

richiware commented Jan 11, 2019

Build status:

  • Linux Build Status
  • Mac Build Status
  • Windows Build Status

@MiguelCompany MiguelCompany force-pushed the feature/fixed-size-bitmaps branch from 3af8c05 to b38e4d0 Compare January 14, 2019 06:54
@richiware
Copy link
Copy Markdown
Member

richiware commented Jan 14, 2019

Build status:

  • Linux Build Status
  • Mac Build Status
  • Windows Build Status

richiware
richiware requested changes Jan 16, 2019
View reviewed changes
include/fastrtps/utils/fixed_size_bitmap.hpp Outdated
bool add(const T& item) noexcept
{
// Compute maximum allowed value and check item is inside the allowed range.
T max = base_ + (NBITS - 1);
Copy link
Copy Markdown
Member

@richiware richiware Jan 16, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Could be this calculated only when base_ is set?

Copy link
Copy Markdown
Member Author

@MiguelCompany MiguelCompany Jan 16, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It would mean space for an additional T, but I think it is affordable, as we only use this with fragment and sequence numbers, which are small.

Copy link
Copy Markdown
Member Author

@MiguelCompany MiguelCompany Jan 16, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

done

@richiware
Copy link
Copy Markdown
Member

richiware commented Jan 16, 2019

Build status:

  • Linux Build Status
  • Mac Build Status
  • Windows Build Status

@richiware richiware merged commit cd29fc1 into feature/safety-critical-systems Jan 16, 2019
@richiware richiware deleted the feature/fixed-size-bitmaps branch January 16, 2019 21:12
@dejanpan
Copy link
Copy Markdown

dejanpan commented Jan 18, 2019

@MiguelCompany @deeplearningrobotics I see that Andreas changed his question in #370 (comment) from std::bitset to static vector.

But Miguel answered probably at the the same time #370 (comment)?

@MiguelCompany
Copy link
Copy Markdown
Member Author

MiguelCompany commented Jan 18, 2019

But Miguel answered probably at the the same time #370 (comment)?

Correct. I also saw the edit and answered both thoughts at the same time.

@MiguelCompany MiguelCompany mentioned this pull request Mar 29, 2019
Closed
31 tasks
MiguelCompany pushed a commit that referenced this pull request Apr 11, 2019
@richiware @MiguelCompany
First features for safety critical systems (#486)
d155904 
* Fixed size strings [4216] (#361)

* Refs #4213. New template fixed_string and unit tests.

* Refs #4213. Changing participant, topic and type name to string_255.

* Refs #4213. Adapting blackbox tests.

* New Allocation test [4259] (#364)

* Allocation test improved

* Using osrf_testing_tools

* Readme improved.

* Refs #4222 Update the allocation tests to generate a csv file with the results

* Refs #4222 Update the allocation tests to receive a new argument to set a prefix for the output files.

* Refs #4222 Update cmake file to work as the rest of tests

* Refs #4222 Change the output prefix management to set the output file from outside of the program

* Refs #4222 Fix compilation issue.

* Refs #4222 Fix compilation issue.

* Refs #4222 Add a new argument to set the domain of the test

* Refs #4222 Fix compilation issue.

* Refs #4222 Update the csv export process

* Refs #4222. Restoring callgrind related code.

* Refs #4222. Using condition_variable where requested.

* Refs #4222 Fix compilation issue.

* Refs  #4222 Move the include directory on cmakelist file from "test" to "profiling"

* Refs #4259. Added python script to generate plot.

Also allocation tests now appends to csv new data.

* Fixed size bitmaps [4320] (#370)

* Refs #4292. Removed get_set from SequenceNumberSet_t.

* Refs #4292. Changed ReaderProxy::get_unsent_changes into for_each_unsent_change.

* Refs #4292. Removed get_requested_changes from ReaderProxy.

* Refs #4292. New template BitmapRange.

* Refs #4292. Using BitmapRange on SequenceNumberSet_t.

* Refs #4292. Using BitmapRange on FragmentNumberSet_t.

* Refs #4292. Added unit tests for BitmapRange.

* Refs #4320. Converting SequenceNumberSet_t into an alias.

* Refs #4320. Fixing compiler warnings.

* Refs #4320. Precalculating max when setting base.

* Remove ParameterList_t [4370] (#379)

* Refs #4306. Refactor for reading parameter list.

* Refs #4306. Refactor for writing ParticipantProxyData.

* Refs #4306. Refactor for writing ReaderProxyData.

* Refs #4306. Refactor for writing WriterProxyData.

* Refs #4306. Refactor for writing inline qos.

* Refs #4306. Remove ParameterList_t.

* Refs #4370. Addressing warnings.

* Refs #4370. Using dynamic_cast when processing parameters.

* Refs #4370. Asserting results of dynamic_cast.

* Refs #4370. Changing inheritance of Parameter_t from private to public.

* Refs #4370. Fixing errors compiling on Debug.

* Mutex wrapper with testing properties [4405] (#383)

* Refs #4403. Mutex wrapper with testing properties.

* Refs #4403. Improved doxygen.

* Fixing error initializing on windows.

* Refs #4403. Fixed compilation error on windows.

* Refs #4403. Fixed error in cmakelists.

* Refs #4403. New implementation using LD_PRELOAD.

* Refs #4403. Only tests will run on Linux.

* Refs #4403. Fixed cmake syntax error.

* Refs #4403. Fixed error preloading lib with spaces in dir.

* Refs #4403. Add label NoMemoryCheck to mutex unit tests.

* Refs #4403. Removed blank line.

* Refs #4403. Added support for pthread_mutex_timedlock()

* Resource limited vector [4421] (#386)

* Refs #4363. Resource limited vector implementation.

* Refs #4363. Unit tests for resource limited vector.

* Refs #4421. Fixing warnings.

* Refs #4421. Fixing warning on Mac.

* Refs #4421. Improved doxygen doc.

* Refs #4421. Adding a template parameter for the configuration struct.

* Refs #4421. Added all iterator related wrapper methods.

* Refs #4421. Added erase and pop_back wrapper methods.

* Refs #4421. Added element access wrapper methods.

* Refs #4421. Avoiding use of constexpr.

* Writers: Resource limits on the number of matched readers [4570] (#406)

* Refs #4364. Resource limits on RTPSWriter

* Refs #4366. Resource limits for StatelessWriter::m_matched_readers

* Refs #4366. Refactor to remove StatelessWriter::reader_locators in favour of unsent_changes_

* Refs #4366. Tidy up and apply resource limits.

* Refs #4424. Renamed attribute to matched_readers_allocation.

* Refs #4365. ReaderProxy mutex not dynamically created

* Refs #4365. Hiding ReaderProxy internals from MessageReceiver.

* Refs #4365. Removing mutex on ReaderProxy.

* Refs #4365. Using ranged for loops.

* Refs #4365. Reducing calls to set::insert on ReaderProxy.

* Refs #4365. Style and privates on ReaderProxy.

* Refs #4365. Periodic heartbeat code moved to StatefulWriter.

* Refs #4365. Periodic heartbeat uses send_heartbeat_nts.

* Refs #4365. Wakeup of AsyncWriterThread always called from StatefulWriter, never from ReaderProxy.

* Refs #4365. Styling and tidy up.

* Refs #4365. Fixing compile errors on Debug.

* Refs #4365. Resource limiting changes_for_reader on ReaderProxy.

* Refs #4365. Removing dependency of MessageReceiver from the details of the writer.

* Refs #4365. Started refactor towards ReaderProxy reuse.

* Refs #4365. Reusing ReaderProxy instances and controlling the pool size.

* Refs #4365. Fixing warnings.

* Refs #4365. Adding matched_subscriber_allocation to PublisherAttributes

* Refs #4362. Avoiding dynamic allocations on XTypes related parameters

* Refs #4424. Parsing matchedSubscribersAllocation on publisher profiles.

* Refs #4424. XSD profiles file updated.

* Refs #4424. XMLParser unit tests updated.

* Refs #4593. Added FixedSized type.

* Refs #4593. Added some blackbox tests.

* Refs #4570. Removing auto on StatefulWriter.

* Refs #4570. Removing temporary vector on check_acked_status.

* Refs #4570. Fixing warnings.

* Refs #4570. Addressing review comments.

* Refs #4570. Fixing a typo and removing unnecesary includes of ReaderProxy

* Refs #4570. Apply suggestions from code review

Co-Authored-By: MiguelCompany <miguelcompany@eprosima.com>

* Refs #4704. Using matchedSubscribersAllocation on allocations test. (#423)

* WIP: Sync write converted to non-blocking call (#426)

* Refs #4630. Main mutex was converted to timed version.

* Refs #4630. Removed unused CDRMessagePool.

* Refs #4630. Fixing warnings.

* Refs #4630. Spread max blocking time

* Refs #4630. Refactorization NetworkFactory and UDPTransportInterface.

* Refs #4630. Refactorization TCPTransportInterface.

* Refs #4630. Created TCP keep alive event.

* Refs #4630. Fixing errors with TLS.

* Refs #4630. Fixing errors with TLS.

* Refs #4630. Fixing errors with TLS.

* Refs #4630. Fixing warnings.

* Refs #4630. Fixing invalid read.

* Refs #4630. Debugging clean up.

* Refs #4630. Debugging clean up.

* Refs #4630. Debugging clean up.

* Refs #4630. Debugging clean up.

* Refs #4630. Removing warnings on windows.

* Refs #4630. Removing invalid read.

* Refs #4630 Fixing Windows crash.

* Refs #4630. Applying coding style.

* Refs #4630. Removed lock.

* Refs #4630. Removed shared from lambdas.

* Refs #4630. Invalid read.

* Refs #4630. Invalid read.

* Refs #4630. Invalid read.

* Refs #4630. Invalid read.

* Refs #4630. Using new state.

* Refs #4630. Tired.

* Refs #4630. Change in states.

* Refs #4630. Avoid block.

* Refs #4630. Fixing TLS.

* Refs #4630. Fixed windows warnings.

* Refs #4630. Fixing windows warnings.

* Refs #4630. Avoiding bad shutddown.

* Refs #4630. Applying coding style.

* Refs #4630 Different strands for write/read. Unlock promise if channel was closed before call the async operation.

* Refs #4630. Fixed extra spaces.

* Refs #5094 Added ReaderProxyTests (find_change related tests).

* Refs #5094 Fixed find_change related bug.

* Refs #5107. Fixing windows compile error.

* Fixing non deterministic tests.

* Fixed a warning on windows.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@richiware richiware richiware approved these changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@MiguelCompany @deeplearningrobotics @richiware @dejanpan