| // Copyright 2019 The Chromium Authors |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifdef UNSAFE_BUFFERS_BUILD |
| // TODO(crbug.com/40284755): Remove this and spanify to fix the errors. |
| #pragma allow_unsafe_buffers |
| #endif |
| |
| #include "base/task/sequence_manager/atomic_flag_set.h" |
| |
| #include <bit> |
| #include <utility> |
| |
| #include "base/check_op.h" |
| #include "base/functional/callback.h" |
| |
| namespace base { |
| namespace sequence_manager { |
| namespace internal { |
| |
| AtomicFlagSet::AtomicFlagSet( |
| scoped_refptr<const AssociatedThreadId> associated_thread) |
| : associated_thread_(std::move(associated_thread)) {} |
| |
| AtomicFlagSet::~AtomicFlagSet() { |
| DCHECK(!alloc_list_head_); |
| DCHECK(!partially_free_list_head_); |
| } |
| |
| AtomicFlagSet::AtomicFlag::AtomicFlag() = default; |
| |
| AtomicFlagSet::AtomicFlag::~AtomicFlag() { |
| ReleaseAtomicFlag(); |
| } |
| |
| AtomicFlagSet::AtomicFlag::AtomicFlag(AtomicFlagSet* outer, |
| Group* element, |
| size_t flag_bit) |
| : outer_(outer), group_(element), flag_bit_(flag_bit) {} |
| |
| AtomicFlagSet::AtomicFlag::AtomicFlag(AtomicFlag&& other) |
| : outer_(other.outer_), group_(other.group_), flag_bit_(other.flag_bit_) { |
| other.outer_ = nullptr; |
| other.group_ = nullptr; |
| } |
| |
| void AtomicFlagSet::AtomicFlag::SetActive(bool active) { |
| DCHECK(group_); |
| if (active) { |
| // Release semantics are required to ensure that all memory accesses made on |
| // this thread happen-before any others done on the thread running the |
| // active callbacks. |
| group_->flags.fetch_or(flag_bit_, std::memory_order_release); |
| } else { |
| // No operation is being performed based on the bit *not* being set (i.e. |
| // state of other memory is irrelevant); hence no memory order is required |
| // when unsetting it. |
| group_->flags.fetch_and(~flag_bit_, std::memory_order_relaxed); |
| } |
| } |
| |
| void AtomicFlagSet::AtomicFlag::ReleaseAtomicFlag() { |
| if (!group_) |
| return; |
| |
| DCHECK_CALLED_ON_VALID_THREAD(outer_->associated_thread_->thread_checker); |
| SetActive(false); |
| |
| // If |group_| was full then add it on the partially free list. |
| if (group_->IsFull()) |
| outer_->AddToPartiallyFreeList(group_); |
| |
| int index = Group::IndexOfFirstFlagSet(flag_bit_); |
| DCHECK(!group_->flag_callbacks[index].is_null()); |
| group_->flag_callbacks[index] = RepeatingClosure(); |
| group_->allocated_flags &= ~flag_bit_; |
| |
| // If |group_| has become empty delete it. |
| if (group_->IsEmpty()) { |
| auto ptr = group_.ExtractAsDangling(); |
| outer_->RemoveFromPartiallyFreeList(ptr); |
| outer_->RemoveFromAllocList(ptr); |
| } |
| |
| outer_ = nullptr; |
| group_ = nullptr; |
| } |
| |
| AtomicFlagSet::AtomicFlag AtomicFlagSet::AddFlag(RepeatingClosure callback) { |
| DCHECK_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker); |
| // Allocate a new Group if needed. |
| if (!partially_free_list_head_) { |
| AddToAllocList(std::make_unique<Group>()); |
| AddToPartiallyFreeList(alloc_list_head_.get()); |
| } |
| |
| DCHECK(partially_free_list_head_); |
| Group* group = partially_free_list_head_; |
| size_t first_unoccupied_index = |
| static_cast<size_t>(group->FindFirstUnallocatedFlag()); |
| DCHECK(!group->flag_callbacks[first_unoccupied_index]); |
| group->flag_callbacks[first_unoccupied_index] = std::move(callback); |
| |
| size_t flag_bit = size_t{1} << first_unoccupied_index; |
| group->allocated_flags |= flag_bit; |
| |
| if (group->IsFull()) |
| RemoveFromPartiallyFreeList(group); |
| |
| return AtomicFlag(this, group, flag_bit); |
| } |
| |
| void AtomicFlagSet::RunActiveCallbacks() const { |
| DCHECK_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker); |
| for (Group* iter = alloc_list_head_.get(); iter; iter = iter->next.get()) { |
| // Acquire semantics are required to guarantee that all memory side-effects |
| // made by other threads that were allowed to perform operations are |
| // synchronized with this thread before it returns from this method. |
| size_t active_flags = std::atomic_exchange_explicit( |
| &iter->flags, size_t{0}, std::memory_order_acquire); |
| // This is O(number of bits set). |
| while (active_flags) { |
| int index = Group::IndexOfFirstFlagSet(active_flags); |
| // Clear the flag. |
| active_flags ^= size_t{1} << index; |
| iter->flag_callbacks[index].Run(); |
| } |
| } |
| } |
| |
| AtomicFlagSet::Group::Group() = default; |
| |
| AtomicFlagSet::Group::~Group() { |
| DCHECK_EQ(allocated_flags, 0u); |
| DCHECK(!partially_free_list_prev); |
| DCHECK(!partially_free_list_next); |
| } |
| |
| bool AtomicFlagSet::Group::IsFull() const { |
| return (~allocated_flags) == 0u; |
| } |
| |
| bool AtomicFlagSet::Group::IsEmpty() const { |
| return allocated_flags == 0u; |
| } |
| |
| int AtomicFlagSet::Group::FindFirstUnallocatedFlag() const { |
| size_t unallocated_flags = ~allocated_flags; |
| DCHECK_NE(unallocated_flags, 0u); |
| int index = IndexOfFirstFlagSet(unallocated_flags); |
| DCHECK_LT(index, kNumFlags); |
| return index; |
| } |
| |
| // static |
| int AtomicFlagSet::Group::IndexOfFirstFlagSet(size_t flag) { |
| DCHECK_NE(flag, 0u); |
| return std::countr_zero(flag); |
| } |
| |
| void AtomicFlagSet::AddToAllocList(std::unique_ptr<Group> group) { |
| DCHECK_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker); |
| if (alloc_list_head_) |
| alloc_list_head_->prev = group.get(); |
| |
| group->next = std::move(alloc_list_head_); |
| alloc_list_head_ = std::move(group); |
| } |
| |
| void AtomicFlagSet::RemoveFromAllocList(Group* group) { |
| DCHECK_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker); |
| if (group->next) |
| group->next->prev = group->prev; |
| |
| if (group->prev) { |
| group->prev->next = std::move(group->next); |
| } else { |
| alloc_list_head_ = std::move(group->next); |
| } |
| } |
| |
| void AtomicFlagSet::AddToPartiallyFreeList(Group* group) { |
| DCHECK_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker); |
| DCHECK_NE(partially_free_list_head_, group); |
| DCHECK(!group->partially_free_list_prev); |
| DCHECK(!group->partially_free_list_next); |
| if (partially_free_list_head_) |
| partially_free_list_head_->partially_free_list_prev = group; |
| |
| group->partially_free_list_next = partially_free_list_head_; |
| partially_free_list_head_ = group; |
| } |
| |
| void AtomicFlagSet::RemoveFromPartiallyFreeList(Group* group) { |
| DCHECK_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker); |
| DCHECK(partially_free_list_head_); |
| // Check |group| is in the list. |
| DCHECK(partially_free_list_head_ == group || group->partially_free_list_prev); |
| if (group->partially_free_list_next) { |
| group->partially_free_list_next->partially_free_list_prev = |
| group->partially_free_list_prev; |
| } |
| |
| if (group->partially_free_list_prev) { |
| group->partially_free_list_prev->partially_free_list_next = |
| group->partially_free_list_next; |
| } else { |
| partially_free_list_head_ = group->partially_free_list_next; |
| } |
| |
| group->partially_free_list_prev = nullptr; |
| group->partially_free_list_next = nullptr; |
| } |
| |
| } // namespace internal |
| } // namespace sequence_manager |
| } // namespace base |