base/task/promise/dependent_list.cc - chromium/src - Git at Google

 // Copyright 2019 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #include "base/task/promise/dependent_list.h"

 #include <algorithm>
 #include <atomic>
 #include <cstdint>

 #include "base/logging.h"
 #include "base/task/promise/abstract_promise.h"

 namespace base {
 namespace internal {

 // static
 DependentList::Node* DependentList::ReverseList(DependentList::Node* list) {
   DependentList::Node* prev = nullptr;
   while (list) {
     DependentList::Node* next = list->next_;
     list->next_ = prev;
     prev = list;
     list = next;
   }
   return prev;
 }

 // static
 void DependentList::DispatchAll(DependentList::Node* head,
                                 DependentList::Visitor* visitor,
                                 bool retain_prerequsites) {
   head = ReverseList(head);
   DependentList::Node* next = nullptr;
   while (head) {
     next = head->next_;
     if (retain_prerequsites)
       head->RetainSettledPrerequisite();
     // |visitor| might delete the node, so no access to node past this
     // call!
     visitor->Visit(std::move(head->dependent_));
     head = next;
   }
 }

 DependentList::Visitor::~Visitor() = default;

 DependentList::Node::Node() = default;

 DependentList::Node::Node(Node&& other) noexcept {
   prerequisite_ = other.prerequisite_.load(std::memory_order_relaxed);
   other.prerequisite_ = 0;
   dependent_ = std::move(other.dependent_);
   DCHECK_EQ(other.next_, nullptr);
 }

 DependentList::Node::Node(AbstractPromise* prerequisite,
                           scoped_refptr<AbstractPromise> dependent)
     : prerequisite_(reinterpret_cast<intptr_t>(prerequisite)),
       dependent_(std::move(dependent)) {}

 DependentList::Node::~Node() {
   ClearPrerequisite();
 }

 DependentList::DependentList(State initial_state)
     : data_(CreateData(nullptr,
                        initial_state,
                        initial_state == State::kUnresolved ? kAllowInserts
                                                            : kBlockInserts)) {}

 DependentList::DependentList(ConstructUnresolved)
     : DependentList(State::kUnresolved) {}

 DependentList::DependentList(ConstructResolved)
     : DependentList(State::kResolved) {}

 DependentList::DependentList(ConstructRejected)
     : DependentList(State::kRejected) {}

 DependentList::~DependentList() = default;

 void DependentList::Node::Reset(AbstractPromise* prerequisite,
                                 scoped_refptr<AbstractPromise> dependent) {
   SetPrerequisite(prerequisite);
   dependent_ = std::move(dependent);
   next_ = nullptr;
 }

 void DependentList::Node::SetPrerequisite(AbstractPromise* prerequisite) {
   DCHECK(prerequisite);
   intptr_t prev_value = prerequisite_.exchange(
       reinterpret_cast<intptr_t>(prerequisite), std::memory_order_acq_rel);

   if (prev_value & kIsRetained)
     reinterpret_cast<AbstractPromise*>(prev_value & ~kIsRetained)->Release();
 }

 AbstractPromise* DependentList::Node::prerequisite() const {
   return reinterpret_cast<AbstractPromise*>(
       prerequisite_.load(std::memory_order_acquire) & ~kIsRetained);
 }

 void DependentList::Node::RetainSettledPrerequisite() {
   intptr_t prerequisite = prerequisite_.load(std::memory_order_acquire);
   DCHECK((prerequisite & kIsRetained) == 0) << "May only be called once";
   if (!prerequisite)
     return;

   // Mark as retained, note we could have another thread trying to call
   // ClearPrerequisite.
   if (prerequisite_.compare_exchange_strong(
           prerequisite, prerequisite | kIsRetained, std::memory_order_release,
           std::memory_order_acquire)) {
     reinterpret_cast<AbstractPromise*>(prerequisite)->AddRef();
   }
 }

 void DependentList::Node::ClearPrerequisite() {
   intptr_t prerequisite = prerequisite_.exchange(0, std::memory_order_acq_rel);
   if (prerequisite & kIsRetained)
     reinterpret_cast<AbstractPromise*>(prerequisite & ~kIsRetained)->Release();
 }

 DependentList::InsertResult DependentList::Insert(Node* node) {
   DCHECK(!node->next_);

   // std::memory_order_acquire for hapens-after relation with
   // SettleAndDispatchAllDependents completing and thus this this call returning
   // an error.
   uintptr_t prev_data = data_.load(std::memory_order_acquire);
   bool did_insert = false;
   while (IsAllowingInserts(prev_data) && !did_insert) {
     node->next_ = ExtractHead(prev_data);

     // On success std::memory_order_release so that all memory operations become
     // visible in SettleAndDispatchAllDependents when iterating the list.
     // On failure std::memory_order_acquire for happens-after relation with
     // SettleAndDispatchAllDependents completing and thus this this call
     // returning an error.
     //
     // Note: ABA is not an issue here as we do not care that head_ might now be
     // pointing to a different node (but with same address) we only need to
     // guarantee that node->next points to the current head (which is now the
     // new node but with the same address so node->next is still valid).
     if (data_.compare_exchange_weak(
             prev_data, CreateData(node, ExtractState(prev_data), kAllowInserts),
             std::memory_order_seq_cst, std::memory_order_seq_cst)) {
       did_insert = true;
     } else {
       // Cleanup in case the loop terminates
       node->next_ = nullptr;
     }
   }

   if (did_insert) {
     return InsertResult::SUCCESS;
   }

   switch (ExtractState(prev_data)) {
     case State::kResolved:
       return InsertResult::FAIL_PROMISE_RESOLVED;

     case State::kRejected:
       return InsertResult::FAIL_PROMISE_REJECTED;

     case State::kCanceled:
       return InsertResult::FAIL_PROMISE_CANCELED;

     case State::kUnresolved:
       // We must have inserted, as inserts must be allowed if in state
       // kUnresolved
       NOTREACHED();
       return InsertResult::SUCCESS;
   }
 }

 bool DependentList::SettleAndDispatchAllDependents(const State settled_state,
                                                    Visitor* visitor) {
   DCHECK_NE(settled_state, State::kUnresolved);

   // Whether this invocation won the settlement race. If so, it will now keep
   // dispatching all nodes in as many attempts as it takes to win the race
   // against Insert()'s.
   bool did_set_state = false;

   // This load, and the ones in for compare_exchange_weak failures can be
   // std::memory_order_relaxed as we do not make any ordering guarantee when
   // this method returns false.
   uintptr_t prev_data = data_.load(std::memory_order_seq_cst);
   while (true) {
     if (!did_set_state && ExtractState(prev_data) != State::kUnresolved) {
       // Somebody else set the state.
       return false;
     }

     if (!IsListEmpty(prev_data)) {
       // List is not empty and we might have set the state previously
       // We need to:
       //  * Settle the state (or leave as is if we already did).
       //  * allow_inserts. As we are going to dispatch the nodes we need to
       //    make sure that other threads can still insert to the list
       //    (instead of just resolving themselves) to preserve dispatch order.
       //  * Take ownership of all nodes currently in the queue, i.e. set the
       //    head to nullptr, marking it empty
       DCHECK_EQ(ExtractState(prev_data),
                 did_set_state ? settled_state : State::kUnresolved);
       DCHECK(IsAllowingInserts(prev_data));
       uintptr_t new_data = CreateData(nullptr, settled_state, kAllowInserts);

       // On success std::memory_order_acquire for happens-after relation with
       // with the last successful Insert().
       if (!data_.compare_exchange_weak(prev_data, new_data,
                                        std::memory_order_seq_cst,
                                        std::memory_order_relaxed)) {
         continue;
       }
       did_set_state = true;
       // We don't want to retain prerequisites when cancelling.
       DispatchAll(ExtractHead(prev_data), visitor,
                   settled_state != State::kCanceled);
       prev_data = new_data;
     }

     // List is empty and we might have set the state previously, so we
     // can settle the state (or leave as is if we already did) and freeze
     // the list.
     DCHECK(IsListEmpty(prev_data));
     DCHECK_EQ(ExtractState(prev_data),
               did_set_state ? settled_state : State::kUnresolved);
     // On success std::memory_order_release for happens-before relation with
     // Insert returning an error.
     if (data_.compare_exchange_weak(
             prev_data, CreateData(nullptr, settled_state, kBlockInserts),
             std::memory_order_seq_cst, std::memory_order_relaxed)) {
       // Inserts no longer allowed, state settled and list is empty. We are
       // done!
       return true;
     }
   }
 }

 // The following methods do not make any ordering guarantees, false return
 // values are always stale. A true return value just means that
 // SettleAndDispatchAllDependents was called but it gives no guarantees as
 // whether any of the nodes was dispatched or the call finished. Thus
 // std::memory_order_relaxed.

 bool DependentList::IsSettled() const {
   return ExtractState(data_.load(std::memory_order_seq_cst)) !=
          State::kUnresolved;
 }

 bool DependentList::IsResolved() const {
   DCHECK(IsSettled()) << "This check is racy";
   return ExtractState(data_.load(std::memory_order_seq_cst)) ==
          State::kResolved;
 }

 bool DependentList::IsRejected() const {
   DCHECK(IsSettled()) << "This check is racy";
   return ExtractState(data_.load(std::memory_order_seq_cst)) ==
          State::kRejected;
 }

 bool DependentList::IsCanceled() const {
   return ExtractState(data_.load(std::memory_order_seq_cst)) ==
          State::kCanceled;
 }

 bool DependentList::IsResolvedForTesting() const {
   return ExtractState(data_.load(std::memory_order_seq_cst)) ==
          State::kResolved;
 }

 bool DependentList::IsRejectedForTesting() const {
   return ExtractState(data_.load(std::memory_order_seq_cst)) ==
          State::kRejected;
 }

 }  // namespace internal
 }  // namespace base
	// Copyright 2019 The Chromium Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#include "base/task/promise/dependent_list.h"

	#include <algorithm>
	#include <atomic>
	#include <cstdint>

	#include "base/logging.h"
	#include "base/task/promise/abstract_promise.h"

	namespace base {
	namespace internal {

	// static
	DependentList::Node* DependentList::ReverseList(DependentList::Node* list) {
	DependentList::Node* prev = nullptr;
	while (list) {
	DependentList::Node* next = list->next_;
	list->next_ = prev;
	prev = list;
	list = next;
	}
	return prev;
	}

	// static
	void DependentList::DispatchAll(DependentList::Node* head,
	DependentList::Visitor* visitor,
	bool retain_prerequsites) {
	head = ReverseList(head);
	DependentList::Node* next = nullptr;
	while (head) {
	next = head->next_;
	if (retain_prerequsites)
	head->RetainSettledPrerequisite();
	// \|visitor\| might delete the node, so no access to node past this
	// call!
	visitor->Visit(std::move(head->dependent_));
	head = next;
	}
	}

	DependentList::Visitor::~Visitor() = default;

	DependentList::Node::Node() = default;

	DependentList::Node::Node(Node&& other) noexcept {
	prerequisite_ = other.prerequisite_.load(std::memory_order_relaxed);
	other.prerequisite_ = 0;
	dependent_ = std::move(other.dependent_);
	DCHECK_EQ(other.next_, nullptr);
	}

	DependentList::Node::Node(AbstractPromise* prerequisite,
	scoped_refptr<AbstractPromise> dependent)
	: prerequisite_(reinterpret_cast<intptr_t>(prerequisite)),
	dependent_(std::move(dependent)) {}

	DependentList::Node::~Node() {
	ClearPrerequisite();
	}

	DependentList::DependentList(State initial_state)
	: data_(CreateData(nullptr,
	initial_state,
	initial_state == State::kUnresolved ? kAllowInserts
	: kBlockInserts)) {}

	DependentList::DependentList(ConstructUnresolved)
	: DependentList(State::kUnresolved) {}

	DependentList::DependentList(ConstructResolved)
	: DependentList(State::kResolved) {}

	DependentList::DependentList(ConstructRejected)
	: DependentList(State::kRejected) {}

	DependentList::~DependentList() = default;

	void DependentList::Node::Reset(AbstractPromise* prerequisite,
	scoped_refptr<AbstractPromise> dependent) {
	SetPrerequisite(prerequisite);
	dependent_ = std::move(dependent);
	next_ = nullptr;
	}

	void DependentList::Node::SetPrerequisite(AbstractPromise* prerequisite) {
	DCHECK(prerequisite);
	intptr_t prev_value = prerequisite_.exchange(
	reinterpret_cast<intptr_t>(prerequisite), std::memory_order_acq_rel);

	if (prev_value & kIsRetained)
	reinterpret_cast<AbstractPromise*>(prev_value & ~kIsRetained)->Release();
	}

	AbstractPromise* DependentList::Node::prerequisite() const {
	return reinterpret_cast<AbstractPromise*>(
	prerequisite_.load(std::memory_order_acquire) & ~kIsRetained);
	}

	void DependentList::Node::RetainSettledPrerequisite() {
	intptr_t prerequisite = prerequisite_.load(std::memory_order_acquire);
	DCHECK((prerequisite & kIsRetained) == 0) << "May only be called once";
	if (!prerequisite)
	return;

	// Mark as retained, note we could have another thread trying to call
	// ClearPrerequisite.
	if (prerequisite_.compare_exchange_strong(
	prerequisite, prerequisite \| kIsRetained, std::memory_order_release,
	std::memory_order_acquire)) {
	reinterpret_cast<AbstractPromise*>(prerequisite)->AddRef();
	}
	}

	void DependentList::Node::ClearPrerequisite() {
	intptr_t prerequisite = prerequisite_.exchange(0, std::memory_order_acq_rel);
	if (prerequisite & kIsRetained)
	reinterpret_cast<AbstractPromise*>(prerequisite & ~kIsRetained)->Release();
	}

	DependentList::InsertResult DependentList::Insert(Node* node) {
	DCHECK(!node->next_);

	// std::memory_order_acquire for hapens-after relation with
	// SettleAndDispatchAllDependents completing and thus this this call returning
	// an error.
	uintptr_t prev_data = data_.load(std::memory_order_acquire);
	bool did_insert = false;
	while (IsAllowingInserts(prev_data) && !did_insert) {
	node->next_ = ExtractHead(prev_data);

	// On success std::memory_order_release so that all memory operations become
	// visible in SettleAndDispatchAllDependents when iterating the list.
	// On failure std::memory_order_acquire for happens-after relation with
	// SettleAndDispatchAllDependents completing and thus this this call
	// returning an error.
	//
	// Note: ABA is not an issue here as we do not care that head_ might now be
	// pointing to a different node (but with same address) we only need to
	// guarantee that node->next points to the current head (which is now the
	// new node but with the same address so node->next is still valid).
	if (data_.compare_exchange_weak(
	prev_data, CreateData(node, ExtractState(prev_data), kAllowInserts),
	std::memory_order_seq_cst, std::memory_order_seq_cst)) {
	did_insert = true;
	} else {
	// Cleanup in case the loop terminates
	node->next_ = nullptr;
	}
	}

	if (did_insert) {
	return InsertResult::SUCCESS;
	}

	switch (ExtractState(prev_data)) {
	case State::kResolved:
	return InsertResult::FAIL_PROMISE_RESOLVED;

	case State::kRejected:
	return InsertResult::FAIL_PROMISE_REJECTED;

	case State::kCanceled:
	return InsertResult::FAIL_PROMISE_CANCELED;

	case State::kUnresolved:
	// We must have inserted, as inserts must be allowed if in state
	// kUnresolved
	NOTREACHED();
	return InsertResult::SUCCESS;
	}
	}

	bool DependentList::SettleAndDispatchAllDependents(const State settled_state,
	Visitor* visitor) {
	DCHECK_NE(settled_state, State::kUnresolved);

	// Whether this invocation won the settlement race. If so, it will now keep
	// dispatching all nodes in as many attempts as it takes to win the race
	// against Insert()'s.
	bool did_set_state = false;

	// This load, and the ones in for compare_exchange_weak failures can be
	// std::memory_order_relaxed as we do not make any ordering guarantee when
	// this method returns false.
	uintptr_t prev_data = data_.load(std::memory_order_seq_cst);
	while (true) {
	if (!did_set_state && ExtractState(prev_data) != State::kUnresolved) {
	// Somebody else set the state.
	return false;
	}

	if (!IsListEmpty(prev_data)) {
	// List is not empty and we might have set the state previously
	// We need to:
	// * Settle the state (or leave as is if we already did).
	// * allow_inserts. As we are going to dispatch the nodes we need to
	// make sure that other threads can still insert to the list
	// (instead of just resolving themselves) to preserve dispatch order.
	// * Take ownership of all nodes currently in the queue, i.e. set the
	// head to nullptr, marking it empty
	DCHECK_EQ(ExtractState(prev_data),
	did_set_state ? settled_state : State::kUnresolved);
	DCHECK(IsAllowingInserts(prev_data));
	uintptr_t new_data = CreateData(nullptr, settled_state, kAllowInserts);

	// On success std::memory_order_acquire for happens-after relation with
	// with the last successful Insert().
	if (!data_.compare_exchange_weak(prev_data, new_data,
	std::memory_order_seq_cst,
	std::memory_order_relaxed)) {
	continue;
	}
	did_set_state = true;
	// We don't want to retain prerequisites when cancelling.
	DispatchAll(ExtractHead(prev_data), visitor,
	settled_state != State::kCanceled);
	prev_data = new_data;
	}

	// List is empty and we might have set the state previously, so we
	// can settle the state (or leave as is if we already did) and freeze
	// the list.
	DCHECK(IsListEmpty(prev_data));
	DCHECK_EQ(ExtractState(prev_data),
	did_set_state ? settled_state : State::kUnresolved);
	// On success std::memory_order_release for happens-before relation with
	// Insert returning an error.
	if (data_.compare_exchange_weak(
	prev_data, CreateData(nullptr, settled_state, kBlockInserts),
	std::memory_order_seq_cst, std::memory_order_relaxed)) {
	// Inserts no longer allowed, state settled and list is empty. We are
	// done!
	return true;
	}
	}
	}

	// The following methods do not make any ordering guarantees, false return
	// values are always stale. A true return value just means that
	// SettleAndDispatchAllDependents was called but it gives no guarantees as
	// whether any of the nodes was dispatched or the call finished. Thus
	// std::memory_order_relaxed.

	bool DependentList::IsSettled() const {
	return ExtractState(data_.load(std::memory_order_seq_cst)) !=
	State::kUnresolved;
	}

	bool DependentList::IsResolved() const {
	DCHECK(IsSettled()) << "This check is racy";
	return ExtractState(data_.load(std::memory_order_seq_cst)) ==
	State::kResolved;
	}

	bool DependentList::IsRejected() const {
	DCHECK(IsSettled()) << "This check is racy";
	return ExtractState(data_.load(std::memory_order_seq_cst)) ==
	State::kRejected;
	}

	bool DependentList::IsCanceled() const {
	return ExtractState(data_.load(std::memory_order_seq_cst)) ==
	State::kCanceled;
	}

	bool DependentList::IsResolvedForTesting() const {
	return ExtractState(data_.load(std::memory_order_seq_cst)) ==
	State::kResolved;
	}

	bool DependentList::IsRejectedForTesting() const {
	return ExtractState(data_.load(std::memory_order_seq_cst)) ==
	State::kRejected;
	}

	} // namespace internal
	} // namespace base