1// Copyright (c) Microsoft Corporation. All rights reserved.
2// Licensed under the MIT license.
3
4#pragma once
5
6#include <algorithm>
7#include <atomic>
8#include <cassert>
9#include <cstdint>
10
11namespace FASTER {
12namespace core {
13
14class PageOffset;
15
16/// (Logical) address into persistent memory. Identifies a page and an offset within that page.
17/// Uses 48 bits: 25 bits for the offset and 23 bits for the page. (The remaining 16 bits are
18/// reserved for use by the hash table.)
19/// Address
20class Address {
21 public:
22 friend class PageOffset;
23
24 /// An invalid address, used when you need to initialize an address but you don't have a valid
25 /// value for it yet. NOTE: set to 1, not 0, to distinguish an invalid hash bucket entry
26 /// (initialized to all zeros) from a valid hash bucket entry that points to an invalid address.
27 static constexpr uint64_t kInvalidAddress = 1;
28
29 /// A logical address is 8 bytes.
30 /// --of which 48 bits are used for the address. (The remaining 16 bits are used by the hash
31 /// table, for control bits and the tag.)
32 static constexpr uint64_t kAddressBits = 48;
33 static constexpr uint64_t kMaxAddress = ((uint64_t)1 << kAddressBits) - 1;
34 /// --of which 25 bits are used for offsets into a page, of size 2^25 = 32 MB.
35 static constexpr uint64_t kOffsetBits = 25;
36 static constexpr uint32_t kMaxOffset = ((uint32_t)1 << kOffsetBits) - 1;
37 /// --and the remaining 23 bits are used for the page index, allowing for approximately 8 million
38 /// pages.
39 static constexpr uint64_t kPageBits = kAddressBits - kOffsetBits;
40 static constexpr uint32_t kMaxPage = ((uint32_t)1 << kPageBits) - 1;
41
42 /// Default constructor.
43 Address()
44 : control_{ 0 } {
45 }
46 Address(uint32_t page, uint32_t offset)
47 : reserved_{ 0 }
48 , page_{ page }
49 , offset_{ offset } {
50 }
51 /// Copy constructor.
52 Address(const Address& other)
53 : control_{ other.control_ } {
54 }
55 Address(uint64_t control)
56 : control_{ control } {
57 assert(reserved_ == 0);
58 }
59
60 inline Address& operator=(const Address& other) {
61 control_ = other.control_;
62 return *this;
63 }
64 inline Address& operator+=(uint64_t delta) {
65 assert(delta < UINT32_MAX);
66 control_ += delta;
67 return *this;
68 }
69 inline Address operator-(const Address& other) {
70 return control_ - other.control_;
71 }
72
73 /// Comparison operators.
74 inline bool operator<(const Address& other) const {
75 assert(reserved_ == 0);
76 assert(other.reserved_ == 0);
77 return control_ < other.control_;
78 }
79 inline bool operator<=(const Address& other) const {
80 assert(reserved_ == 0);
81 assert(other.reserved_ == 0);
82 return control_ <= other.control_;
83 }
84 inline bool operator>(const Address& other) const {
85 assert(reserved_ == 0);
86 assert(other.reserved_ == 0);
87 return control_ > other.control_;
88 }
89 inline bool operator>=(const Address& other) const {
90 assert(reserved_ == 0);
91 assert(other.reserved_ == 0);
92 return control_ >= other.control_;
93 }
94 inline bool operator==(const Address& other) const {
95 return control_ == other.control_;
96 }
97 inline bool operator!=(const Address& other) const {
98 return control_ != other.control_;
99 }
100
101 /// Accessors.
102 inline uint32_t page() const {
103 return static_cast<uint32_t>(page_);
104 }
105 inline uint32_t offset() const {
106 return static_cast<uint32_t>(offset_);
107 }
108 inline uint64_t control() const {
109 return control_;
110 }
111
112 private:
113 union {
114 struct {
115 uint64_t offset_ : kOffsetBits; // 25 bits
116 uint64_t page_ : kPageBits; // 23 bits
117 uint64_t reserved_ : 64 - kAddressBits; // 16 bits
118 };
119 uint64_t control_;
120 };
121};
122static_assert(sizeof(Address) == 8, "sizeof(Address) != 8");
123
124}
125} // namespace FASTER::core
126
127/// Implement std::min() for Address type.
128namespace std {
129template <>
130inline const FASTER::core::Address& min(const FASTER::core::Address& a,
131 const FASTER::core::Address& b) {
132 return (b < a) ? b : a;
133}
134}
135
136namespace FASTER {
137namespace core {
138
139/// Atomic (logical) address.
140class AtomicAddress {
141 public:
142 AtomicAddress(const Address& address)
143 : control_{ address.control() } {
144 }
145
146 /// Atomic access.
147 inline Address load() const {
148 return Address{ control_.load() };
149 }
150 inline void store(Address value) {
151 control_.store(value.control());
152 }
153 inline bool compare_exchange_strong(Address& expected, Address desired) {
154 uint64_t expected_control = expected.control();
155 bool result = control_.compare_exchange_strong(expected_control, desired.control());
156 expected = Address{ expected_control };
157 return result;
158 }
159
160 /// Accessors.
161 inline uint32_t page() const {
162 return load().page();
163 }
164 inline uint32_t offset() const {
165 return load().offset();
166 }
167 inline uint64_t control() const {
168 return load().control();
169 }
170
171 private:
172 /// Atomic access to the address.
173 std::atomic<uint64_t> control_;
174};
175
176}
177} // namespace FASTER::core
178