HazptrObjLinked.h

Go to the documentation of this file.

/*
 * Copyright 2018-present Facebook, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#pragma once

#include <folly/synchronization/Hazptr-fwd.h>
#include <folly/synchronization/HazptrObj.h>

#include <glog/logging.h>

#include <atomic>
#include <stack>


namespace folly {

template <typename T, template <typename> class Atom>
class hazptr_root {
  Atom<T*> link_;

 public:
  explicit hazptr_root(T* p = nullptr) noexcept : link_(p) {}

  ~hazptr_root() {
    auto p = link_.load(std::memory_order_relaxed);
    if (p) {
      p->unlink();
    }
  }

  const Atom<T*>& operator()() const noexcept {
    return link_;
  }

  Atom<T*>& operator()() noexcept {
    return link_;
  }
}; // hazptr_root

template <template <typename> class Atom>
class hazptr_obj_linked : public hazptr_obj<Atom> {
  using Count = uint32_t;

  static constexpr Count kRef = 1u;
  static constexpr Count kLink = 1u << 16;
  static constexpr Count kRefMask = kLink - 1u;
  static constexpr Count kLinkMask = ~kRefMask;

  Atom<Count> count_{0};

 public:
  void acquire_link() noexcept {
    count_inc(kLink);
  }

  void acquire_link_safe() noexcept {
    count_inc_safe(kLink);
  }

  void acquire_ref() noexcept {
    count_inc(kRef);
  }

  void acquire_ref_safe() noexcept {
    count_inc_safe(kRef);
  }

 private:
  template <typename, template <typename> class, typename>
  friend class hazptr_obj_base_linked;

  Count count() const noexcept {
    return count_.load(std::memory_order_acquire);
  }

  void count_set(Count val) noexcept {
    count_.store(val, std::memory_order_release);
  }

  void count_inc(Count add) noexcept {
    auto oldval = count_.fetch_add(add, std::memory_order_acq_rel);
    DCHECK_LT(oldval & kLinkMask, kLinkMask);
    DCHECK_LT(oldval & kRefMask, kRefMask);
  }

  void count_inc_safe(Count add) noexcept {
    auto oldval = count();
    count_set(oldval + add);
    DCHECK_LT(oldval & kLinkMask, kLinkMask);
    DCHECK_LT(oldval & kRefMask, kRefMask);
  }

  bool count_cas(Count& oldval, Count newval) noexcept {
    return count_.compare_exchange_weak(
        oldval, newval, std::memory_order_acq_rel, std::memory_order_acquire);
  }

  bool release_link() noexcept {
    auto sub = kLink;
    auto oldval = count();
    while (true) {
      DCHECK_GT(oldval & kLinkMask, 0u);
      if (oldval == kLink) {
        count_set(0u);
        return true;
      }
      if (count_cas(oldval, oldval - sub)) {
        return false;
      }
    }
  }

  bool release_ref() noexcept {
    auto sub = kRef;
    auto oldval = count();
    while (true) {
      if (oldval == 0u) {
        if (kIsDebug) {
          count_set(kRefMask);
        }
        return true;
      }
      DCHECK_GT(oldval & kRefMask, 0u);
      if (count_cas(oldval, oldval - sub)) {
        return false;
      }
    }
  }

  bool downgrade_link() noexcept {
    auto oldval = count();
    auto sub = kLink - kRef;
    while (true) {
      if (oldval == kLink) {
        count_set(kRef);
        return true;
      }
      if (count_cas(oldval, oldval - sub)) {
        return (oldval & kLinkMask) == kLink;
      }
    }
  }
}; // hazptr_obj_linked

template <typename T, template <typename> class Atom, typename D>
class hazptr_obj_base_linked : public hazptr_obj_linked<Atom>,
                               public hazptr_deleter<T, D> {
  using Stack = std::stack<hazptr_obj_base_linked<T, Atom, D>*>;

 public:
  void retire() {
    this->pre_retire_check(); // defined in hazptr_obj
    set_reclaim();
    this->push_to_retired(
        default_hazptr_domain<Atom>()); // defined in hazptr_obj
  }

  /* unlink: Retire object if last link is released. */
  void unlink() {
    if (this->release_link()) { // defined in hazptr_obj_linked
      downgrade_retire_immutable_descendants();
      retire();
    }
  }

  /* unlink_and_reclaim_unchecked: Reclaim object if the last link is
     released, without checking hazard pointers. To be called only
     when the object cannot possibly be protected by any hazard
     pointers. */
  void unlink_and_reclaim_unchecked() {
    if (this->release_link()) { // defined in hazptr_obj_linked
      DCHECK_EQ(this->count(), 0u);
      delete_self();
    }
  }

 private:
  void set_reclaim() noexcept {
    this->reclaim_ = [](hazptr_obj<Atom>* p, hazptr_obj_list<Atom>& l) {
      auto obj = static_cast<hazptr_obj_base_linked<T, Atom, D>*>(p);
      if (obj->release_ref()) { // defined in hazptr_obj_linked
        obj->release_delete_immutable_descendants();
        obj->release_retire_mutable_children(l);
        obj->delete_self();
      }
    };
  }

  void downgrade_retire_immutable_descendants() {
    Stack s;
    call_push_links(false, s);
    while (!s.empty()) {
      auto p = s.top();
      s.pop();
      if (p && p->downgrade_link()) {
        p->call_push_links(false, s);
        p->retire();
      }
    }
  }

  void release_delete_immutable_descendants() {
    Stack s;
    call_push_links(false, s);
    while (!s.empty()) {
      auto p = s.top();
      s.pop();
      if (p && p->release_ref()) {
        p->call_push_links(false, s);
        p->delete_self();
      }
    }
  }

  void release_retire_mutable_children(hazptr_obj_list<Atom>& l) {
    Stack s;
    call_push_links(true, s);
    while (!s.empty()) {
      auto p = s.top();
      s.pop();
      if (p->release_link()) {
        p->pre_retire_check(); // defined in hazptr_obj
        p->set_reclaim();
        l.push(p); // treated as if retired immediately
      }
    }
  }

  void call_push_links(bool m, Stack& s) {
    static_cast<T*>(this)->push_links(m, s); // to be defined in T
  }

  void delete_self() {
    this->delete_obj(static_cast<T*>(this)); // defined in hazptr_deleter
  }
}; // hazptr_obj_base_linked

} // namespace folly