folly/experimental/StampedPtr.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #pragma once
  18
  19 #include <folly/lang/SafeAssert.h>
  20
  21 #include <stdint.h>
  22
  23 namespace folly {
  24
  25 /**
  26  * StampedPtr packs both a pointer to T and a uint16_t into a 64-bit value,
  27  * exploiting the fact that current addresses are limited to 48 bits on
  28  * all current x86-64 and ARM64 processors.
  29  *
  30  * For both x86-64 and ARM64, 64-bit pointers have a canonical
  31  * form in which the upper 16 bits are equal to bit 47.  Intel has
  32  * announced a 57-bit addressing mode (see https://software.intel.com/
  33  * sites/default/files/managed/2b/80/5-level_paging_white_paper.pdf),
  34  * but it is not yet available.  The first problematic platform will
  35  * probably be ARMv8.2, which supports 52-bit virtual addresses.
  36  *
  37  * This code works on all of the platforms I have available for test,
  38  * and probably on all currently-shipping platforms that have a hope of
  39  * compiling folly.  Rather than enumerating the supported platforms via
  40  * ifdef, this code dynamically validates its packing assumption in debug
  41  * builds on each call to a mutating function.  Presumably by the time we
  42  * are running this process in an operating system image that can address
  43  * more than 256TB of memory, RAM cost and the latency of 128-bit CAS
  44  * will have improved enough that this optimization is no longer impactful.
  45  *
  46  * A common approach to this kind of packing seems to be to just assume
  47  * the top 16 bits are zero, but https://github.com/LuaJIT/LuaJIT/issues/49
  48  * indicates that ARM64 platforms in the wild are actually setting bit 47
  49  * in their stack addresses.  That means that we need to extend bit 47 to
  50  * do the right thing (it's not expensive, it compiles to one instruction
  51  * on x86-64 and arm64).
  52  *
  53  * Compare to PackedSyncPtr and DiscriminatedPtr, which perform similar
  54  * packing but add additional functionality.  The name is taken from
  55  * Java's AtomicStampedReference.  Unlike PackedSyncPtr, which tries to
  56  * act pointer-like, this class acts more like a pair whose elements are
  57  * named ptr and stamp.  It also allows direct access to the internal
  58  * raw field: since we're already at the metal you might want to play
  59  * additional games.  It is guaranteed that a zero raw value gets decoded
  60  * as a (ptr,stamp) of (nullptr,0).
  61  */
  62 template <typename T>
  63 struct StampedPtr {
  64   /**
  65    * The packing is not guaranteed, except that it is guaranteed that
  66    * raw == 0 iff ptr() == nullptr && stamp() == 0.
  67    */
  68   uint64_t raw;
  69
  70   /* IMPORTANT: default initialization doesn't result in a sane state */
  71
  72   T* ptr() const {
  73     return unpackPtr(raw);
  74   }
  75
  76   uint16_t stamp() const {
  77     return unpackStamp(raw);
  78   }
  79
  80   void set(T* ptr, uint16_t stamp) {
  81     raw = pack(ptr, stamp);
  82   }
  83
  84   void setPtr(T* ptr) {
  85     raw = pack(ptr, unpackStamp(raw));
  86   }
  87
  88   void setStamp(uint16_t stamp) {
  89     raw = pack(unpackPtr(raw), stamp);
  90   }
  91
  92   static T* unpackPtr(uint64_t raw) {
  93     // Canonical form means we need to extend bit 47 of the pointer to
  94     // bits 48..63 (unless the operating system never hands those pointers
  95     // to us, which is difficult to prove).  Signed right-shift of a
  96     // negative number is implementation-defined in C++ (not undefined!),
  97     // but actually does the right thing on all the platforms I can find.
  98     auto extended = static_cast<int64_t>(raw) >> kInternalStampBits;
  99     return reinterpret_cast<T*>(static_cast<intptr_t>(extended));
 100   }
 101
 102   static uint16_t unpackStamp(uint64_t raw) {
 103     return static_cast<uint16_t>(raw);
 104   }
 105
 106   static uint64_t pack(T* ptr, uint16_t stamp) {
 107     auto shifted = static_cast<uint64_t>(reinterpret_cast<uintptr_t>(ptr))
 108         << kInternalStampBits;
 109     uint64_t raw = shifted | stamp;
 110     FOLLY_SAFE_DCHECK(unpackPtr(raw) == ptr, "ptr mismatch.");
 111     FOLLY_SAFE_DCHECK(unpackStamp(raw) == stamp, "stamp mismatch.");
 112     return raw;
 113   }
 114
 115  private:
 116   // On 32-bit platforms it works okay to store a ptr in the top 48
 117   // bits of a 64-bit value, but it will result in unnecessary work.
 118   // If we align the pointer part at word granularity when we have the
 119   // space then no shifting will ever be needed.
 120   static constexpr unsigned kInternalStampBits = sizeof(void*) == 4 ? 32 : 16;
 121 };
 122
 123 template <typename T>
 124 StampedPtr<T> makeStampedPtr(T* ptr, uint16_t stamp) {
 125   return StampedPtr<T>{StampedPtr<T>::pack(ptr, stamp)};
 126 }
 127
 128 } // namespace folly