StampedPtr
authorNathan Bronson <ngbronson@fb.com>
Mon, 15 May 2017 19:12:55 +0000 (12:12 -0700)
committerFacebook Github Bot <facebook-github-bot@users.noreply.github.com>
Mon, 15 May 2017 19:20:25 +0000 (12:20 -0700)
Summary:
This diff adds StampedPtr, which packs a pointer and a uint16_t into
a uint64_t with maximum portability and without adding any additional
functionality.

Reviewed By: yfeldblum, davidtgoldblatt

Differential Revision: D4804614

fbshipit-source-id: 25fe7aff47d1e126ac8edfff4eb0bbb1d34071aa

folly/Makefile.am
folly/experimental/StampedPtr.h [new file with mode: 0644]
folly/experimental/test/StampedPtrTest.cpp [new file with mode: 0644]

index 1ffd730..f03ceda 100644 (file)
@@ -149,6 +149,7 @@ nobase_follyinclude_HEADERS = \
        experimental/symbolizer/StackTrace.h \
        experimental/symbolizer/Symbolizer.h \
        experimental/Select64.h \
+       experimental/StampedPtr.h \
        experimental/StringKeyedCommon.h \
        experimental/StringKeyedMap.h \
        experimental/StringKeyedSet.h \
diff --git a/folly/experimental/StampedPtr.h b/folly/experimental/StampedPtr.h
new file mode 100644 (file)
index 0000000..ac45c21
--- /dev/null
@@ -0,0 +1,127 @@
+/*
+ * Copyright 2017 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 <assert.h>
+#include <stdint.h>
+
+namespace folly {
+
+/**
+ * StampedPtr packs both a pointer to T and a uint16_t into a 64-bit value,
+ * exploiting the fact that current addresses are limited to 48 bits on
+ * all current x86-64 and ARM64 processors.
+ *
+ * For both x86-64 and ARM64, 64-bit pointers have a canonical
+ * form in which the upper 16 bits are equal to bit 47.  Intel has
+ * announced a 57-bit addressing mode (see https://software.intel.com/
+ * sites/default/files/managed/2b/80/5-level_paging_white_paper.pdf),
+ * but it is not yet available.  The first problematic platform will
+ * probably be ARMv8.2, which supports 52-bit virtual addresses.
+ *
+ * This code works on all of the platforms I have available for test,
+ * and probably on all currently-shipping platforms that have a hope of
+ * compiling folly.  Rather than enumerating the supported platforms via
+ * ifdef, this code dynamically validates its packing assumption in debug
+ * builds on each call to a mutating function.  Presumably by the time we
+ * are running this process in an operating system image that can address
+ * more than 256TB of memory, RAM cost and the latency of 128-bit CAS
+ * will have improved enough that this optimization is no longer impactful.
+ *
+ * A common approach to this kind of packing seems to be to just assume
+ * the top 16 bits are zero, but https://github.com/LuaJIT/LuaJIT/issues/49
+ * indicates that ARM64 platforms in the wild are actually setting bit 47
+ * in their stack addresses.  That means that we need to extend bit 47 to
+ * do the right thing (it's not expensive, it compiles to one instruction
+ * on x86-64 and arm64).
+ *
+ * Compare to PackedSyncPtr and DiscriminatedPtr, which perform similar
+ * packing but add additional functionality.  The name is taken from
+ * Java's AtomicStampedReference.  Unlike PackedSyncPtr, which tries to
+ * act pointer-like, this class acts more like a pair whose elements are
+ * named ptr and stamp.  It also allows direct access to the internal
+ * raw field: since we're already at the metal you might want to play
+ * additional games.  It is guaranteed that a zero raw value gets decoded
+ * as a (ptr,stamp) of (nullptr,0).
+ */
+template <typename T>
+struct StampedPtr {
+  /**
+   * The packing is not guaranteed, except that it is guaranteed that
+   * raw == 0 iff ptr() == nullptr && stamp() == 0.
+   */
+  uint64_t raw;
+
+  /* IMPORTANT: default initialization doesn't result in a sane state */
+
+  T* ptr() const {
+    return unpackPtr(raw);
+  }
+
+  uint16_t stamp() const {
+    return unpackStamp(raw);
+  }
+
+  void set(T* ptr, uint16_t stamp) {
+    raw = pack(ptr, stamp);
+  }
+
+  void setPtr(T* ptr) {
+    raw = pack(ptr, unpackStamp(raw));
+  }
+
+  void setStamp(uint16_t stamp) {
+    raw = pack(unpackPtr(raw), stamp);
+  }
+
+  static T* unpackPtr(uint64_t raw) {
+    // Canonical form means we need to extend bit 47 of the pointer to
+    // bits 48..63 (unless the operating system never hands those pointers
+    // to us, which is difficult to prove).  Signed right-shift of a
+    // negative number is implementation-defined in C++ (not undefined!),
+    // but actually does the right thing on all the platforms I can find.
+    auto extended = static_cast<int64_t>(raw) >> kInternalStampBits;
+    return reinterpret_cast<T*>(static_cast<intptr_t>(extended));
+  }
+
+  static uint16_t unpackStamp(uint64_t raw) {
+    return static_cast<uint16_t>(raw);
+  }
+
+  static uint64_t pack(T* ptr, uint16_t stamp) {
+    auto shifted = static_cast<uint64_t>(reinterpret_cast<uintptr_t>(ptr))
+        << kInternalStampBits;
+    uint64_t raw = shifted | stamp;
+    assert(unpackPtr(raw) == ptr);
+    assert(unpackStamp(raw) == stamp);
+    return raw;
+  }
+
+ private:
+  // On 32-bit platforms it works okay to store a ptr in the top 48
+  // bits of a 64-bit value, but it will result in unnecessary work.
+  // If we align the pointer part at word granularity when we have the
+  // space then no shifting will ever be needed.
+  static constexpr unsigned kInternalStampBits = sizeof(void*) == 4 ? 32 : 16;
+};
+
+template <typename T>
+StampedPtr<T> makeStampedPtr(T* ptr, uint16_t stamp) {
+  return StampedPtr<T>{StampedPtr<T>::pack(ptr, stamp)};
+}
+
+} // namespace folly
diff --git a/folly/experimental/test/StampedPtrTest.cpp b/folly/experimental/test/StampedPtrTest.cpp
new file mode 100644 (file)
index 0000000..115e28d
--- /dev/null
@@ -0,0 +1,82 @@
+/*
+ * Copyright 2017 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.
+ */
+
+#include <folly/experimental/StampedPtr.h>
+
+#include <folly/portability/GTest.h>
+
+TEST(StampedPtr, Basic) {
+  folly::StampedPtr<char> sp;
+  char target[10];
+  sp.set(target, 10);
+  EXPECT_EQ(sp.ptr(), target);
+  EXPECT_EQ(sp.stamp(), 10);
+  sp.setStamp(sp.stamp() + 1);
+  EXPECT_EQ(sp.stamp(), 11);
+  sp.setPtr(target + 1);
+  EXPECT_EQ(sp.ptr(), target + 1);
+
+  uint64_t raw = sp.raw;
+  sp.raw = 0;
+  EXPECT_NE(sp.stamp(), 11);
+  sp.raw = raw;
+  EXPECT_EQ(sp.stamp(), 11);
+  EXPECT_EQ(sp.ptr(), target + 1);
+}
+
+TEST(StampedPtr, Zero) {
+  folly::StampedPtr<char> sp{0};
+  EXPECT_TRUE(sp.ptr() == nullptr);
+  EXPECT_EQ(sp.stamp(), 0);
+}
+
+TEST(StampedPtr, Void) {
+  folly::StampedPtr<void> sp;
+  char target[10];
+  sp.set(target, 10);
+  EXPECT_EQ(sp.ptr(), target);
+}
+
+TEST(StampedPtr, Make) {
+  auto sp = folly::makeStampedPtr("abc", 0xffff);
+  EXPECT_EQ(*sp.ptr(), 'a');
+  EXPECT_EQ(sp.stamp(), 0xffff);
+
+  double x;
+  auto sp2 = folly::makeStampedPtr(&x, 0);
+  EXPECT_EQ(sp2.ptr(), &x);
+  EXPECT_EQ(sp2.stamp(), 0);
+}
+
+TEST(StampedPtr, Const) {
+  folly::StampedPtr<const char> sp{};
+  char target;
+  sp.setPtr(&target);
+}
+
+TEST(StampedPtr, BitExtension) {
+  //                                 fedcba9876543210
+  auto lo = static_cast<uintptr_t>(0x00007fff672333ecLL);
+  auto hi = static_cast<uintptr_t>(0xfffffffff72333ecLL);
+  ASSERT_TRUE(static_cast<intptr_t>(lo) > 0);
+  ASSERT_TRUE(static_cast<intptr_t>(hi) < 0);
+
+  folly::StampedPtr<char> sp{0};
+  sp.setPtr(reinterpret_cast<char*>(lo));
+  EXPECT_EQ(sp.ptr(), reinterpret_cast<char*>(lo));
+  sp.setPtr(reinterpret_cast<char*>(hi));
+  EXPECT_EQ(sp.ptr(), reinterpret_cast<char*>(hi));
+}