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

shaymagsumov · 2024-04-08T09:48:50Z

This happens very rarely. I can't reproduce it nor attach core dump for now. But i have located it at:

https://github.com/versatica/mediasoup/blob/v3/worker/src/RTC/NackGenerator.cpp#L119

I can repoduce similar crash separatedly from worker in this sample:

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

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

The text was updated successfully, but these errors were encountered:

jmillan · 2024-04-08T10:07:17Z

@shaymagsumov, that the provider snippet generate the crash?

shaymagsumov · 2024-04-08T10:16:40Z

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 · 2024-04-08T10:34:46Z

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

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

ibc · 2024-04-08T15:20:00Z

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 · 2024-04-08T15:30:50Z

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 · 2024-04-08T15:34:08Z

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 · 2024-04-08T15:35:30Z

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 · 2024-04-08T15:36:35Z

Yes, you're right, my bad

ibc · 2024-04-08T15:37:47Z

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 · 2024-04-08T15:46:51Z

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

shaymagsumov · 2024-04-08T15:55:08Z

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

ibc · 2024-04-08T16:12:38Z

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.

shaymagsumov · 2024-04-08T16:19:11Z

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

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

ibc · 2024-04-08T16:26:00Z

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 · 2024-04-08T16:51:14Z

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 · 2024-04-08T18:28:18Z

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

#1368

Fixes #1366 ### Details - As demonstrated in temporal PR #1368, standard C++ STD containers do not throw (even in debug mode) when using `Compare` functions in maps/sets that do not honor transitivity, i.e. `comp(a,b) && comp(b,c) -> comp(a,c)`. - So let's not use abseil containers in those cases. ### Bonus tracks - Dupicate CI actions in debug mode. - Make mediasoup Rust building honor `MEDIASOUP_BUILDTYPE` env variable if given. - Fix an amazing bug in `AudioLevelObserver.cpp` which failed to compile because it uses a `absl::btree_multimap` without including the `absl/container/btree_map.h` header (it didn't fail before due to some absl header included by yet anothe included file, etc).

ibc · 2024-04-09T09:33:55Z

PR fixing the issue done: #1369

penguinol · 2024-04-09T11:39:37Z

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 · 2024-04-09T11:50:38Z

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 · 2024-04-09T12:30:14Z

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 · 2024-04-09T12:36:27Z

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 · 2024-04-09T13:17:36Z

@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 · 2024-04-09T13:39:42Z

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 · 2024-04-09T14:12:30Z

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

shaymagsumov added the bug label Apr 8, 2024

ibc changed the title ~~Sometimes worker crashes in NackGenerator due to failed assertion in absl library~~ SeqManager<T>::SeqLowerThan() crashes when used as compare function in abseil set or map (only in debug mode) Apr 8, 2024

ibc added a commit that referenced this issue Apr 8, 2024

Add a test to check issue #1366 and use Debug mode

f931062

ibc mentioned this issue Apr 8, 2024

Add a test to check issue #1366 and use Debug mode #1368

Closed

ibc mentioned this issue Apr 9, 2024

Avoid abseil containers with SeqManager compare functions #1369

Merged

ibc closed this as completed in #1369 Apr 9, 2024

ibc mentioned this issue Apr 9, 2024

Use uint64_t for containers with RTP seq number as key #1370

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

shaymagsumov commented Apr 8, 2024 •

edited

Loading

jmillan commented Apr 8, 2024

shaymagsumov commented Apr 8, 2024

ibc commented Apr 8, 2024

ibc commented Apr 8, 2024 •

edited

Loading

ibc commented Apr 8, 2024 •

edited

Loading

shaymagsumov commented Apr 8, 2024 •

edited

Loading

ibc commented Apr 8, 2024

shaymagsumov commented Apr 8, 2024

ibc commented Apr 8, 2024

shaymagsumov commented Apr 8, 2024

shaymagsumov commented Apr 8, 2024

ibc commented Apr 8, 2024

shaymagsumov commented Apr 8, 2024 •

edited by ibc

Loading

ibc commented Apr 8, 2024

ibc commented Apr 8, 2024

ibc commented Apr 8, 2024 •

edited

Loading

ibc commented Apr 9, 2024

penguinol commented Apr 9, 2024

ibc commented Apr 9, 2024

penguinol commented Apr 9, 2024

ibc commented Apr 9, 2024

ibc commented Apr 9, 2024

penguinol commented Apr 9, 2024

ibc commented Apr 9, 2024

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

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

Comments

shaymagsumov commented Apr 8, 2024 • edited Loading

jmillan commented Apr 8, 2024

shaymagsumov commented Apr 8, 2024

ibc commented Apr 8, 2024

ibc commented Apr 8, 2024 • edited Loading

ibc commented Apr 8, 2024 • edited Loading

shaymagsumov commented Apr 8, 2024 • edited Loading

ibc commented Apr 8, 2024

shaymagsumov commented Apr 8, 2024

ibc commented Apr 8, 2024

shaymagsumov commented Apr 8, 2024

shaymagsumov commented Apr 8, 2024

ibc commented Apr 8, 2024

shaymagsumov commented Apr 8, 2024 • edited by ibc Loading

ibc commented Apr 8, 2024

ibc commented Apr 8, 2024

ibc commented Apr 8, 2024 • edited Loading

ibc commented Apr 9, 2024

penguinol commented Apr 9, 2024

ibc commented Apr 9, 2024

penguinol commented Apr 9, 2024

ibc commented Apr 9, 2024

ibc commented Apr 9, 2024

penguinol commented Apr 9, 2024

ibc commented Apr 9, 2024

shaymagsumov commented Apr 8, 2024 •

edited

Loading

ibc commented Apr 8, 2024 •

edited

Loading

ibc commented Apr 8, 2024 •

edited

Loading

shaymagsumov commented Apr 8, 2024 •

edited

Loading

shaymagsumov commented Apr 8, 2024 •

edited by ibc

Loading

ibc commented Apr 8, 2024 •

edited

Loading