SeqManager<T>::SeqLowerThan() crashes when used as compare function in abseil set or map (only in debug mode) about mediasoup

[shaymagsumov]

I think i got it. I build and run it in debug mode, so assert is not optimized away and crashes.

[shaymagsumov]

Looks like std::set imposes same requirements on compare function

• https://en.cppreference.com/w/cpp/container/set
• https://en.cppreference.com/w/cpp/named_req/Compare

if comp(a, b) == true and comp(b, c) == true then comp(a, c) == true. 

[jmillan]

@shaymagsumov, that the provider snippet generate the crash?

[shaymagsumov]

I mean that snippet reproduces the same crash as in NackGenerator. Same assert is failing in absl's btree container. Assert code in file absl/container/internal/btree.h is:

assert(
      iter.node_->is_ordered_correctly(static_cast<field_type>(iter.position_),
                                       original_key_compare(key_comp())) &&
      "If this assert fails, then either (1) the comparator may violate "
      "transitivity, i.e. comp(a,b) && comp(b,c) -> comp(a,c) (see "
      "https://en.cppreference.com/w/cpp/named_req/Compare), or (2) a "
      "key may have been mutated after it was inserted into the tree.");

[ibc]

comp(a,b) && comp(b,c) -> comp(a,c)

I feel that this may indeed happen due to SeqManager<uint16_t>::SeqLowerThan comparator...

[ibc]

template<typename T, uint8_t N>
bool SeqManager<T, N>::SeqLowerThan::operator()(T lhs, T rhs) const
{
	return ((rhs > lhs) && (rhs - lhs <= MaxValue / 2)) ||
	       ((lhs > rhs) && (lhs - rhs > MaxValue / 2));
}

template<typename T, uint8_t N>
bool SeqManager<T, N>::IsSeqLowerThan(T lhs, T rhs)
{
	return isSeqLowerThan(lhs, rhs);
}

absl::btree_set<uint16_t, SeqManager<uint16_t>::SeqLowerThan> recoveredList;

recoveredList.insert(10000);
recoveredList.insert(40000);
recoveredList.insert(60000);

transitivity, i.e. comp(a,b) && comp(b,c) -> comp(a,c)

So a = 10000, b = 40000, c = 60000. Let's see:

// Compare a: 10000 with b: 40000:
SeqManager<16, 0>::IsSeqLowerThan(10000, 40000);
// => true

// Compare b: 40000 with c: 60000:
SeqManager<16, 0>::IsSeqLowerThan(40000, 60000);
// => true

// Compare a: 10000 with c: 60000:
SeqManager<16, 0>::IsSeqLowerThan(10000, 60000);
// => false       <-------------- UPPPPPS

UPPPPS

NOTE: I DO KNOW that this is the expected result given how SeqManager is designed, I KNOW THAT. What I mean is that it violates "transitivity, i.e. comp(a,b) && comp(b,c) -> comp(a,c)" as absl docs clearly say.

[ibc]

Said that, I've added these tests in TestNackGenerator.cpp and it does NOT crash at all:

SCENARIO("ISSUE 1366: https://github.com/versatica/mediasoup/issues/1366")
{
	SECTION("absl::btree_set")
	{
		REQUIRE(RTC::SeqManager<uint16_t>::IsSeqLowerThan(10000, 40000) == true);
		REQUIRE(RTC::SeqManager<uint16_t>::IsSeqLowerThan(40000, 60000) == true);
		REQUIRE(RTC::SeqManager<uint16_t>::IsSeqLowerThan(10000, 60000) == false);
	}

	SECTION("std::set")
	{
		std::set<uint16_t, RTC::SeqManager<uint16_t>::SeqLowerThan> recoveredList;

		recoveredList.insert(10000);
		recoveredList.insert(40000);
		recoveredList.insert(60000);

		REQUIRE(recoveredList.size() == 3);
	}

	SECTION("absl::btree_set")
	{
		absl::btree_set<uint16_t, RTC::SeqManager<uint16_t>::SeqLowerThan> recoveredList;

		recoveredList.insert(10000);
		recoveredList.insert(40000);
		recoveredList.insert(60000);

		REQUIRE(recoveredList.size() == 3);
	}
}

[shaymagsumov]

Said that, I've added these tests in TestNackGenerator.cpp and it does NOT crash at all:

SCENARIO("ISSUE 1366: https://github.com/versatica/mediasoup/issues/1366")
{
	SECTION("std::set")
	{
		std::set<uint16_t, RTC::SeqManager<uint16_t>::SeqLowerThan> recoveredList;

		recoveredList.insert(10000);
		recoveredList.insert(40000);
		recoveredList.insert(60000);

		REQUIRE(recoveredList.size() == 3);
	}

	SECTION("absl::btree_set")
	{
		absl::btree_set<uint16_t, RTC::SeqManager<uint16_t>::SeqLowerThan> recoveredList;

		recoveredList.insert(10000);
		recoveredList.insert(40000);
		recoveredList.insert(60000);

		REQUIRE(recoveredList.size() == 3);
	}
}

May be it will crash, when you change
https://github.com/versatica/mediasoup/blob/v3/worker/test/src/RTC/TestNackGenerator.cpp#L136
to
nackGenerator.ReceivePacket(packet, /*isRecovered*/ true);

[ibc]

May be it will, when you change https://github.com/versatica/mediasoup/blob/v3/worker/test/src/RTC/TestNackGenerator.cpp#L136 to nackGenerator.ReceivePacket(packet, /*isRecovered*/ true);

No no, you said that this exact code should crash:

absl::btree_set<uint16_t, SeqManager<uint16_t>::SeqLowerThan> recoveredList;

recoveredList.insert(10000);
recoveredList.insert(40000);
recoveredList.insert(60000);

This is not about NackGenerator at all.

[shaymagsumov]

Yes, you're right, my bad

[ibc]

Yes, you're right, my bad

Then how is it possible that it doesn't crash for me and it crashes for you? We are supposed to use the very same version of abseil.

[shaymagsumov]

Just added this section to the end of TestNackGenerator.cpp:

SECTION("absl::btree_set")
{
	absl::btree_set<uint16_t, RTC::SeqManager<uint16_t>::SeqLowerThan> recoveredList;

	recoveredList.insert(10000);
	recoveredList.insert(40000);
	recoveredList.insert(60000);

	REQUIRE(recoveredList.size() == 3);
}

Result:

Randomness seeded to: 3364192858
mediasoup-worker-test: ../../../subprojects/abseil-cpp-20230802.0/absl/container/internal/btree.h:2888: absl::lts_20230802::container_internal::btree<Params>::iterator absl::lts_20230802::container_internal::btree<Params>::internal_emplace(absl::lts_20230802::container_internal::btree<Params>::iterator, Args&& ...) [with Args = {short unsigned int}; Params = absl::lts_20230802::container_internal::set_params<short unsigned int, RTC::SeqManager<short unsigned int>::SeqLowerThan, std::allocator<short unsigned int>, 256, false>; absl::lts_20230802::container_internal::btree<Params>::iterator = absl::lts_20230802::container_internal::btree_iterator<absl::lts_20230802::container_internal::btree_node<absl::lts_20230802::container_internal::set_params<short unsigned int, RTC::SeqManager<short unsigned int>::SeqLowerThan, std::allocator<short unsigned int>, 256, false> >, short unsigned int&, short unsigned int*>]: Assertion `iter.node_->is_ordered_correctly(static_cast<field_type>(iter.position_), original_key_compare(key_comp())) && "If this assert fails, then either (1) the comparator may violate " "transitivity, i.e. comp(a,b) && comp(b,c) -> comp(a,c) (see " "https://en.cppreference.com/w/cpp/named_req/Compare), or (2) a " "key may have been mutated after it was inserted into the tree."' failed.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mediasoup-worker-test is a Catch2 v3.4.0 host application.
Run with -? for options

-------------------------------------------------------------------------------
Scenario: NACK generator
  absl::btree_set
-------------------------------------------------------------------------------
../../../test/src/RTC/TestNackGenerator.cpp:285
...............................................................................

../../../test/src/RTC/TestNackGenerator.cpp:285: FAILED:
due to a fatal error condition:
  SIGABRT - Abort (abnormal termination) signal

===============================================================================
test cases:   2 |   1 passed | 1 failed
assertions: 115 | 114 passed | 1 failed

Aborted (core dumped)
make: *** [Makefile:97: test] Error 134

[ibc]

The thing is: we DONT want to honor that "transitivity, i.e. comp(a,b) && comp(b,c) -> comp(a,c)". Is this a abseil thing? If so we should use std::set assuming it doesn't implement that "transitivity" thing.

[ibc]

No idea what to do here. We do want current behavior. In fact we want this:

REQUIRE(RTC::SeqManager<uint16_t>::IsSeqLowerThan(10000, 40000) == true);
REQUIRE(RTC::SeqManager<uint16_t>::IsSeqLowerThan(40000, 60000) == true);
REQUIRE(RTC::SeqManager<uint16_t>::IsSeqLowerThan(10000, 60000) == false);

However this desired behavior violates "transitivity, i.e. comp(a,b) && comp(b,c) -> comp(a,c)".

[ibc]

So interestingly, in debug mode only abseil aborts:

SCENARIO("ISSUE 1366: https://github.com/versatica/mediasoup/issues/1366")
{
	SECTION("absl::btree_set")
	{
		REQUIRE(RTC::SeqManager<uint16_t>::IsSeqLowerThan(10000, 40000) == true);
		REQUIRE(RTC::SeqManager<uint16_t>::IsSeqLowerThan(40000, 60000) == true);
		REQUIRE(RTC::SeqManager<uint16_t>::IsSeqLowerThan(10000, 60000) == false);
	}

	SECTION("std::set")
	{
		std::set<uint16_t, RTC::SeqManager<uint16_t>::SeqLowerThan> recoveredList;

		recoveredList.insert(10000);
		recoveredList.insert(40000);
		recoveredList.insert(60000);

		REQUIRE(recoveredList.size() == 3);
	}

	SECTION("absl::btree_set")
	{
		absl::btree_set<uint16_t, RTC::SeqManager<uint16_t>::SeqLowerThan> recoveredList;

		recoveredList.insert(10000);
		recoveredList.insert(40000);
		recoveredList.insert(60000);

		REQUIRE(recoveredList.size() == 3);
	}
}

Assertion failed: (iter.node_->is_ordered_correctly(static_cast<field_type>(iter.position_), original_key_compare(key_comp())) && "If this assert fails, then either (1) the comparator may violate " "transitivity, i.e. comp(a,b) && comp(b,c) -> comp(a,c) (see " "https://en.cppreference.com/w/cpp/named_req/Compare), or (2) a " "key may have been mutated after it was inserted into the tree."), function internal_emplace, file btree.h, line 2894.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mediasoup-worker-test is a Catch2 v3.4.0 host application.
Run with -? for options

-------------------------------------------------------------------------------
Scenario: ISSUE 1366: https://github.com/versatica/mediasoup/issues/1366
  absl::btree_set
-------------------------------------------------------------------------------
../../../test/src/RTC/TestNackGenerator.cpp:162
...............................................................................

../../../test/src/RTC/TestNackGenerator.cpp:162: FAILED:
due to a fatal error condition:
  SIGABRT - Abort (abnormal termination) signal

[ibc]

Let's see how std::set behaves in debug mode in all supported archs and OSs:

#1368

[ibc]

PR fixing the issue done: #1369

[penguinol]

Well, WebRTC uses uint64_t for seq nums instead, it takes more memory and cpu usage, but it's easier to understand and more reliable. uint64_t is big enought to avoid wrap around.

[ibc]

Well, WebRTC uses uint64_t for seq nums instead, it takes more memory and cpu usage, but it's easier to understand and more reliable. uint64_t is big enought to avoid wrap around.

It may use uint64_t when it uses values of 8 bytes as keys in maps or sets. It cannot do that with RTP seq numbers which are 2 bytes long by definition.

[penguinol]

What i mean is when receiving packet, unwarp uint16_t seq num to uint64_t by roc * 65535 + seq, and then store and use the uint64_t value
As in https://webrtc.googlesource.com/src/+/refs/heads/main/rtc_base/numerics/sequence_number_unwrapper.h

[ibc]

What i mean is when receiving packet, unwarp uint16_t seq num to uint64_t by roc * 65535 + seq, and then store and use the uint64_t value As in https://webrtc.googlesource.com/src/+/refs/heads/main/rtc_base/numerics/sequence_number_unwrapper.h

What is roc? And how do you know if a received seq belongs to current cycle or previous one? If we sum such a roc thing (assuming it's the uint16 cycle) to every received packet then it will always look good but it may not be good.

[ibc]

@penguinol this issue is closed because I've merged a PR that, among other things, fixes this. However we can keep discussing your suggestion.

[penguinol]

Yes, roc is round of cycles. libwebrtc creates a SeqNumUnwrapper object for every steam which stores the uint64_t value of the last packet. When a new packet arrived, it calculates the distance between the seq of the packet and the last seq in SeqNumUnwrapper by something like SeqLowerThan, to determine which cycle does the packet belongs to.
I'm not sure whether there is any side effect of using SeqLowerThan in map or set

[ibc]

And what haI've created a separate task for this: #1370