Page MenuHomePhabricator

[scudo][standalone] Consolidate lists

Authored by cryptoad on Oct 21 2019, 8:43 AM.



I was going to introduce a couple more lists and realized that our
lists are currently a bit all over the place. While we have a singly
linked list type relatively well defined, we are using doubly linked
lists defined on the fly for the stats and for the secondary blocks.

This CL adds a doubly linked list object, reorganizing the singly list
one to extract as much of the common code as possible. We use this
new type in the stats and the secondary. We also reorganize the list
tests to benefit from this consolidation.

There are a few side effect changes such as using for iterator loops
that are, in my opinion, cleaner in a couple of places.

Event Timeline

cryptoad created this revision.Oct 21 2019, 8:43 AM
Herald added projects: Restricted Project, Restricted Project. · View Herald TranscriptOct 21 2019, 8:43 AM
Herald added subscribers: Restricted Project, jfb, delcypher. · View Herald Transcript

Can we consider adding a fuzz target for the linked lists? I recently did a similar thing in android for a ringbuffer, which you can see here. If you get it checked in, I can help with getting it running on OSS-Fuzz.


Why does the requirements to call clear() exist for non-zero-inited objects? For globally zero-init'ed instances of this object, we don't encounter a perf overhead of having Size, First, and Last be initialised to zero. For non-global instances, we have to call clear(), which seems easy to forget, and moving this initialisation into the c'tor doesn't cause any additional overhead (and I'd assume the call is elided, making it faster).

It also feels easy to forget to call clear(), and if any global objects are moved into static scopage, it may be incredibly hard to patch any instances where clear() isn't called.


Looks like this is test-only, can we move it out of the core header?


Shouldn't need this-> if you add using IntrusiveList<T>::empty;

(and similar elsewhere)


Why /s/DCHECK/CHECK here? This shouldn't fail in normal program execution, right?




Isn't there an invariant held that if empty() == true, then First == nullptr? In which case, can't we hoist the X->Next = First; out from this conditional?


Would the specialisation:

if (Y == First)
  return push_front(X);

be more performant?

You should then be able to remove the if (Prev) check below, as assumedly there's an invariant that if Y isn't the first element, it has a Prev.






Same as push_front, isn't there an invariant that if empty() == true, Last == nullptr, and the X->Prev = Last can be hoisted out?




DCHECK? (and throughout this function)

cryptoad marked 16 inline comments as done.Oct 25 2019, 8:29 AM

Mitch, thanks for the review! You made excellent points.


Part of the issue, even with constexpr explicit constructors is that __thread can't seem to deal with them (as opposed to thread_local) and complains about it needing "dynamic initialization". It circles back to the choices made with init & initLinkerInitialized.
While your point makes sense, I don't think I can do it, unless I am missing something which is also very possible.


You are right. I initially thought that it would be important to ensure consistency, but extract is only called with X being Prev->Next, and while someone could attempt to TOCTOU it, I don't see that happening with a meaningful success chance.


Good point thank you!


Good point again, thanks!


Removed as part of the previously suggested change.


On this one I don't want to change the CHECKs to DCHECKs because doubly-lists unlinking is often the source of a mirrored write-4 primitive for exploitation.
Some examples can be found in
Since it's being used in a large block header, I can't rule out that this could be targeted.
I can probably relax the nullptr CHECKs as they are probably less relevant to prevent further exploitation.

cryptoad updated this revision to Diff 226434.Oct 25 2019, 8:32 AM
cryptoad marked 5 inline comments as done.

Addressing Mitch's comments:

  • changing some CHECK to DCHECK where I felt it could be done "safely";
  • reorganizing some code to make a clever use of the invariants;
  • moving checkConsistency out of the main definition;
hctim added inline comments.Oct 25 2019, 2:21 PM

So I think I remember the same problem from gwp_asan, but it was solved for us by marking the c'tor as constexpr.
^ works with constexpr c'tor with __thread and thread_local, fails for __thread if not constexpr c'tor. Sounds like this might be the same problem?


Sounds good to me, and the rationale sounds very reasonable. Is it possible to add a comment here to clarify this deliberate intent to future readers?

cryptoad updated this revision to Diff 226507.Oct 25 2019, 3:20 PM
cryptoad marked an inline comment as done.

Adding comment to remove justifying the CHECKs.

cryptoad marked an inline comment as done.Oct 25 2019, 3:29 PM
cryptoad added inline comments.

I gave a shot earlier to constexpr as well without success.
Using a constexpr explicit constructor for the lists, it bubbles up to the TSD:

.../compiler-rt/lib/scudo/standalone/tsd_exclusive.h:93:28: error: non-local variable ‘scudo::TSDRegistryExT<scudo::Allocator<scudo::DefaultConfig> >::ThreadTSD’ declared ‘__thread’ needs dynamic initialization
 THREADLOCAL TSD<Allocator> TSDRegistryExT<Allocator>::ThreadTSD;
.../compiler-rt/lib/scudo/standalone/tsd_exclusive.h:93:28: note: C++11 ‘thread_local’ allows dynamic initialization and destruction

Part of the issue is probably that all of the TSD sub components as well as the TSD itself should all have constexpr constructors, but that's a rabbit hole I am not keen to look into at this moment.

hctim accepted this revision.Oct 25 2019, 4:02 PM

LGTM with final comments.


I see. Might be worth adding a strong TODO to go and sprinkle constexpr around where necessary to make this more bullet proof, but I don't want to block you on this.


if empty(), then First == nullptr as invariant, can hoist X->Next = First and this line out as well, right?



This revision is now accepted and ready to land.Oct 25 2019, 4:02 PM
cryptoad marked 4 inline comments as done and an inline comment as not done.Oct 28 2019, 7:37 AM
cryptoad added inline comments.

You are right, I missed those, thank you.
I changed that and also extracted the Size increment since it will be 0 when empty.


On this one, same as with the doubly linked lists, since we are writing Prev->Next I want to make sure that the list is consistent in the event of an intentional corruption of Y->Prev.
I added a comment.

cryptoad updated this revision to Diff 226664.EditedOct 28 2019, 7:40 AM
cryptoad marked 2 inline comments as done.

Addressed Mitch's last comments:

  • make use of invariants in lists to reorganize some code blocks
  • added a comment to justify a hard CHECK in place of a DCHECK
cryptoad closed this revision.Oct 29 2019, 9:21 AM

This has landed.