diff --git a/compiler-rt/lib/tsan/CMakeLists.txt b/compiler-rt/lib/tsan/CMakeLists.txt --- a/compiler-rt/lib/tsan/CMakeLists.txt +++ b/compiler-rt/lib/tsan/CMakeLists.txt @@ -87,6 +87,7 @@ rtl/tsan_flags.h rtl/tsan_flags.inc rtl/tsan_ignoreset.h + rtl/tsan_ilist.h rtl/tsan_interceptors.h rtl/tsan_interface.h rtl/tsan_interface_ann.h diff --git a/compiler-rt/lib/tsan/rtl/tsan_ilist.h b/compiler-rt/lib/tsan/rtl/tsan_ilist.h new file mode 100644 --- /dev/null +++ b/compiler-rt/lib/tsan/rtl/tsan_ilist.h @@ -0,0 +1,189 @@ +//===-- tsan_ilist.h --------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file is a part of ThreadSanitizer (TSan), a race detector. +// +//===----------------------------------------------------------------------===// +#ifndef TSAN_ILIST_H +#define TSAN_ILIST_H + +#include "sanitizer_common/sanitizer_internal_defs.h" + +namespace __tsan { + +class INode { + public: + INode() = default; + + private: + INode* next_ = nullptr; + INode* prev_ = nullptr; + + template + friend class IList; + INode(const INode&) = delete; + void operator=(const INode&) = delete; +}; + +// Intrusive doubly-linked list. +// +// The node class (MyNode) needs to include "INode foo" field, +// then the list can be declared as IList. +// This design allows to link MyNode into multiple lists using +// different INode fields. +// The optional Elem template argument allows to specify node MDT +// (most derived type) if it's different from MyNode. +template +class IList { + public: + IList(); + + void PushFront(Elem* e); + void PushBack(Elem* e); + void Remove(Elem* e); + + Elem* PopFront(); + Elem* PopBack(); + Elem* Front(); + Elem* Back(); + + // Prev links point towards front of the queue. + Elem* Prev(Elem* e); + // Next links point towards back of the queue. + Elem* Next(Elem* e); + + uptr Size() const; + bool Empty() const; + bool Queued(Elem* e) const; + + private: + INode node_; + uptr size_ = 0; + + void Push(Elem* e, INode* after); + static INode* ToNode(Elem* e); + static Elem* ToElem(INode* n); + + IList(const IList&) = delete; + void operator=(const IList&) = delete; +}; + +template +IList::IList() { + node_.next_ = node_.prev_ = &node_; +} + +template +void IList::PushFront(Elem* e) { + Push(e, &node_); +} + +template +void IList::PushBack(Elem* e) { + Push(e, node_.prev_); +} + +template +void IList::Push(Elem* e, INode* after) { + INode* n = ToNode(e); + DCHECK_EQ(n->next_, nullptr); + DCHECK_EQ(n->prev_, nullptr); + INode* next = after->next_; + n->next_ = next; + n->prev_ = after; + next->prev_ = n; + after->next_ = n; + size_++; +} + +template +void IList::Remove(Elem* e) { + INode* n = ToNode(e); + INode* next = n->next_; + INode* prev = n->prev_; + DCHECK(next); + DCHECK(prev); + DCHECK(size_); + next->prev_ = prev; + prev->next_ = next; + n->prev_ = n->next_ = nullptr; + size_--; +} + +template +Elem* IList::PopFront() { + Elem* e = Front(); + if (e) + Remove(e); + return e; +} + +template +Elem* IList::PopBack() { + Elem* e = Back(); + if (e) + Remove(e); + return e; +} + +template +Elem* IList::Front() { + return size_ ? ToElem(node_.next_) : nullptr; +} + +template +Elem* IList::Back() { + return size_ ? ToElem(node_.prev_) : nullptr; +} + +template +Elem* IList::Prev(Elem* e) { + INode* n = ToNode(e); + DCHECK(n->prev_); + return n->prev_ != &node_ ? ToElem(n->prev_) : nullptr; +} + +template +Elem* IList::Next(Elem* e) { + INode* n = ToNode(e); + DCHECK(n->next_); + return n->next_ != &node_ ? ToElem(n->next_) : nullptr; +} + +template +uptr IList::Size() const { + return size_; +} + +template +bool IList::Empty() const { + return size_ == 0; +} + +template +bool IList::Queued(Elem* e) const { + INode* n = ToNode(e); + DCHECK_EQ(!n->next_, !n->prev_); + return n->next_; +} + +template +INode* IList::ToNode(Elem* e) { + return &(e->*Node); +} + +template +Elem* IList::ToElem(INode* n) { + return static_cast(reinterpret_cast( + reinterpret_cast(n) - + reinterpret_cast(&(reinterpret_cast(0)->*Node)))); +} + +} // namespace __tsan + +#endif diff --git a/compiler-rt/lib/tsan/tests/unit/CMakeLists.txt b/compiler-rt/lib/tsan/tests/unit/CMakeLists.txt --- a/compiler-rt/lib/tsan/tests/unit/CMakeLists.txt +++ b/compiler-rt/lib/tsan/tests/unit/CMakeLists.txt @@ -2,6 +2,7 @@ tsan_clock_test.cpp tsan_dense_alloc_test.cpp tsan_flags_test.cpp + tsan_ilist_test.cpp tsan_mman_test.cpp tsan_shadow_test.cpp tsan_stack_test.cpp diff --git a/compiler-rt/lib/tsan/tests/unit/tsan_ilist_test.cpp b/compiler-rt/lib/tsan/tests/unit/tsan_ilist_test.cpp new file mode 100644 --- /dev/null +++ b/compiler-rt/lib/tsan/tests/unit/tsan_ilist_test.cpp @@ -0,0 +1,125 @@ +//===-- tsan_ilist_test.cpp -----------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file is a part of ThreadSanitizer (TSan), a race detector. +// +//===----------------------------------------------------------------------===// +#include "tsan_ilist.h" + +#include "gtest/gtest.h" + +namespace __tsan { + +struct Node { + INode node1; + INode node2; +}; + +struct Parent : Node {}; + +TEST(IList, Empty) { + IList list; + Node node; + + EXPECT_TRUE(list.Empty()); + EXPECT_EQ(list.Size(), 0); + EXPECT_EQ(list.Back(), nullptr); + EXPECT_EQ(list.Front(), nullptr); + EXPECT_EQ(list.PopBack(), nullptr); + EXPECT_EQ(list.PopFront(), nullptr); + EXPECT_FALSE(list.Queued(&node)); +} + +TEST(IList, OneNode) { + IList list; + Node node; + + list.PushBack(&node); + EXPECT_FALSE(list.Empty()); + EXPECT_EQ(list.Size(), 1); + EXPECT_EQ(list.Back(), &node); + EXPECT_EQ(list.Front(), &node); + EXPECT_TRUE(list.Queued(&node)); + EXPECT_EQ(list.Prev(&node), nullptr); + EXPECT_EQ(list.Next(&node), nullptr); + + EXPECT_EQ(list.PopFront(), &node); + EXPECT_TRUE(list.Empty()); + EXPECT_EQ(list.Size(), 0); + EXPECT_FALSE(list.Queued(&node)); +} + +TEST(IList, MultipleNodes) { + IList list; + Node nodes[3]; + + list.PushBack(&nodes[1]); + list.PushBack(&nodes[0]); + list.PushFront(&nodes[2]); + + EXPECT_EQ(list.Size(), 3); + EXPECT_EQ(list.Back(), &nodes[0]); + EXPECT_EQ(list.Front(), &nodes[2]); + + EXPECT_EQ(list.Next(&nodes[0]), nullptr); + EXPECT_EQ(list.Prev(&nodes[0]), &nodes[1]); + + EXPECT_EQ(list.Next(&nodes[1]), &nodes[0]); + EXPECT_EQ(list.Prev(&nodes[1]), &nodes[2]); + + EXPECT_EQ(list.Next(&nodes[2]), &nodes[1]); + EXPECT_EQ(list.Prev(&nodes[2]), nullptr); + + EXPECT_EQ(list.PopBack(), &nodes[0]); + EXPECT_EQ(list.PopFront(), &nodes[2]); + EXPECT_EQ(list.PopFront(), &nodes[1]); + EXPECT_TRUE(list.Empty()); +} + +TEST(IList, TwoLists) { + IList list1; + IList list2; + Parent nodes[3]; + + list1.PushBack(&nodes[2]); + list1.PushBack(&nodes[1]); + list1.PushBack(&nodes[0]); + + list2.PushFront(&nodes[1]); + + EXPECT_EQ(list1.Size(), 3); + EXPECT_TRUE(list1.Queued(&nodes[0])); + EXPECT_TRUE(list1.Queued(&nodes[1])); + EXPECT_TRUE(list1.Queued(&nodes[2])); + + EXPECT_EQ(list2.Size(), 1); + EXPECT_FALSE(list2.Queued(&nodes[0])); + EXPECT_TRUE(list2.Queued(&nodes[1])); + EXPECT_FALSE(list2.Queued(&nodes[2])); + + EXPECT_EQ(list1.Next(&nodes[1]), &nodes[0]); + EXPECT_EQ(list1.Prev(&nodes[1]), &nodes[2]); + + EXPECT_EQ(list2.Next(&nodes[1]), nullptr); + EXPECT_EQ(list2.Prev(&nodes[1]), nullptr); + + list1.Remove(&nodes[1]); + EXPECT_EQ(list1.Size(), 2); + EXPECT_FALSE(list1.Queued(&nodes[1])); + EXPECT_EQ(list2.Size(), 1); + EXPECT_TRUE(list2.Queued(&nodes[1])); + + EXPECT_EQ(list1.PopBack(), &nodes[0]); + EXPECT_EQ(list1.PopBack(), &nodes[2]); + EXPECT_EQ(list1.Size(), 0); + + EXPECT_EQ(list2.PopBack(), &nodes[1]); + EXPECT_EQ(list2.Size(), 0); +} + +} // namespace __tsan