1// Copyright (c) Microsoft Corporation. All rights reserved.
2// Licensed under the MIT license.
3
4#pragma once
5
6#include <atomic>
7#include <cassert>
8#include <cstdint>
9#include <thread>
10
11#include "address.h"
12#include "constants.h"
13#include "malloc_fixed_page_size.h"
14
15namespace FASTER {
16namespace core {
17
18static_assert(Address::kAddressBits == 48, "Address::kAddressBits != 48");
19
20/// Entry stored in a hash bucket. Packed into 8 bytes.
21struct HashBucketEntry {
22 /// Invalid value in the hash table
23 static constexpr uint64_t kInvalidEntry = 0;
24
25 HashBucketEntry()
26 : control_{ 0 } {
27 }
28 HashBucketEntry(Address address, uint16_t tag, bool tentative)
29 : address_{ address.control() }
30 , tag_{ tag }
31 , reserved_{ 0 }
32 , tentative_{ tentative } {
33 }
34 HashBucketEntry(uint64_t code)
35 : control_{ code } {
36 }
37 HashBucketEntry(const HashBucketEntry& other)
38 : control_{ other.control_ } {
39 }
40
41 inline HashBucketEntry& operator=(const HashBucketEntry& other) {
42 control_ = other.control_;
43 return *this;
44 }
45 inline bool operator ==(const HashBucketEntry& other) const {
46 return control_ == other.control_;
47 }
48 inline bool operator !=(const HashBucketEntry& other) const {
49 return control_ != other.control_;
50 }
51 inline bool unused() const {
52 return control_ == 0;
53 }
54 inline Address address() const {
55 return Address{ address_ };
56 }
57 inline uint16_t tag() const {
58 return static_cast<uint16_t>(tag_);
59 }
60 inline bool tentative() const {
61 return static_cast<bool>(tentative_);
62 }
63 inline void set_tentative(bool desired) {
64 tentative_ = desired;
65 }
66
67 union {
68 struct {
69 uint64_t address_ : 48; // corresponds to logical address
70 uint64_t tag_ : 14;
71 uint64_t reserved_ : 1;
72 uint64_t tentative_ : 1;
73 };
74 uint64_t control_;
75 };
76};
77static_assert(sizeof(HashBucketEntry) == 8, "sizeof(HashBucketEntry) != 8");
78
79/// Atomic hash-bucket entry.
80class AtomicHashBucketEntry {
81 public:
82 AtomicHashBucketEntry(const HashBucketEntry& entry)
83 : control_{ entry.control_ } {
84 }
85 /// Default constructor
86 AtomicHashBucketEntry()
87 : control_{ HashBucketEntry::kInvalidEntry } {
88 }
89
90 /// Atomic access.
91 inline HashBucketEntry load() const {
92 return HashBucketEntry{ control_.load() };
93 }
94 inline void store(const HashBucketEntry& desired) {
95 control_.store(desired.control_);
96 }
97 inline bool compare_exchange_strong(HashBucketEntry& expected, HashBucketEntry desired) {
98 uint64_t expected_control = expected.control_;
99 bool result = control_.compare_exchange_strong(expected_control, desired.control_);
100 expected = HashBucketEntry{ expected_control };
101 return result;
102 }
103
104 private:
105 /// Atomic address to the hash bucket entry.
106 std::atomic<uint64_t> control_;
107};
108
109/// Entry stored in a hash bucket that points to the next overflow bucket (if any).
110struct HashBucketOverflowEntry {
111 HashBucketOverflowEntry()
112 : control_{ 0 } {
113 }
114 HashBucketOverflowEntry(FixedPageAddress address)
115 : address_{ address.control() }
116 , unused_{ 0 } {
117 }
118 HashBucketOverflowEntry(const HashBucketOverflowEntry& other)
119 : control_{ other.control_ } {
120 }
121 HashBucketOverflowEntry(uint64_t code)
122 : control_{ code } {
123 }
124
125 inline HashBucketOverflowEntry& operator=(const HashBucketOverflowEntry& other) {
126 control_ = other.control_;
127 return *this;
128 }
129 inline bool operator ==(const HashBucketOverflowEntry& other) const {
130 return control_ == other.control_;
131 }
132 inline bool operator !=(const HashBucketOverflowEntry& other) const {
133 return control_ != other.control_;
134 }
135 inline bool unused() const {
136 return address_ == 0;
137 }
138 inline FixedPageAddress address() const {
139 return FixedPageAddress{ address_ };
140 }
141
142 union {
143 struct {
144 uint64_t address_ : 48; // corresponds to logical address
145 uint64_t unused_ : 16;
146 };
147 uint64_t control_;
148 };
149};
150static_assert(sizeof(HashBucketOverflowEntry) == 8, "sizeof(HashBucketOverflowEntry) != 8");
151
152/// Atomic hash-bucket overflow entry.
153class AtomicHashBucketOverflowEntry {
154 private:
155 static constexpr uint64_t kPinIncrement = (uint64_t)1 << 48;
156 static constexpr uint64_t kLocked = (uint64_t)1 << 63;
157
158 public:
159 AtomicHashBucketOverflowEntry(const HashBucketOverflowEntry& entry)
160 : control_{ entry.control_ } {
161 }
162 /// Default constructor
163 AtomicHashBucketOverflowEntry()
164 : control_{ HashBucketEntry::kInvalidEntry } {
165 }
166
167 /// Atomic access.
168 inline HashBucketOverflowEntry load() const {
169 return HashBucketOverflowEntry{ control_.load() };
170 }
171 inline void store(const HashBucketOverflowEntry& desired) {
172 control_.store(desired.control_);
173 }
174 inline bool compare_exchange_strong(HashBucketOverflowEntry& expected,
175 HashBucketOverflowEntry desired) {
176 uint64_t expected_control = expected.control_;
177 bool result = control_.compare_exchange_strong(expected_control, desired.control_);
178 expected = HashBucketOverflowEntry{ expected_control };
179 return result;
180 }
181
182 private:
183 /// Atomic address to the hash bucket entry.
184 std::atomic<uint64_t> control_;
185};
186
187/// A bucket consisting of 7 hash bucket entries, plus one hash bucket overflow entry. Fits in
188/// a cache line.
189struct alignas(Constants::kCacheLineBytes) HashBucket {
190 /// Number of entries per bucket (excluding overflow entry).
191 static constexpr uint32_t kNumEntries = 7;
192 /// The entries.
193 AtomicHashBucketEntry entries[kNumEntries];
194 /// Overflow entry points to next overflow bucket, if any.
195 AtomicHashBucketOverflowEntry overflow_entry;
196};
197static_assert(sizeof(HashBucket) == Constants::kCacheLineBytes,
198 "sizeof(HashBucket) != Constants::kCacheLineBytes");
199
200}
201} // namespace FASTER::core
202