98 std::size_t valid_bytes = 0;
100 std::uint64_t age = 0;
105 static constexpr std::size_t no_slot = std::numeric_limits<std::size_t>::max();
118 bool detached() const noexcept {
return bool(*
this) && slot_ == no_slot; }
121 void reset() noexcept;
129 std::size_t slot_ = no_slot;
137 : policy_(
policy), backing_(backing), allocator_(allocator), transaction_(transaction) {
139 if (!line || !backing.
read ||
bool(allocator.allocate) !=
bool(allocator.deallocate)
145 || (write_back() && !transaction.
write)) {
153 if (!memory_)
return;
154 for (std::size_t i = 0; i < slots_; ++i) slot(i).~Slot();
155 if (allocator_.deallocate) allocator_.deallocate(allocator_.context, memory_, allocated_bytes_);
156 else ::operator
delete(memory_);
167 static std::size_t
line_bytes(std::size_t page_size)
noexcept {
168 return page_size && page_size <= std::numeric_limits<std::size_t>::max() -
sizeof(Slot)
169 ?
sizeof(Slot) + page_size : 0;
176 increment(stats_.get_calls);
179 return load(
key, destination).status;
182 increment(stats_.pin_calls);
184 if (!valid_span(caller_workspace.data, caller_workspace.size))
186 const auto loaded = load(
key, caller_workspace);
188 if (loaded.slot != no_slot) ++slot(loaded.slot).pins;
189 increment(stats_.current_pins);
190 if (stats_.current_pins > stats_.pin_high_water)
191 stats_.pin_high_water = stats_.current_pins;
193 {loaded.slot == no_slot ? caller_workspace.data : payload(loaded.slot),
194 caller_workspace.size});
197 if (lease.owner_ ==
this) lease.reset();
201 increment(stats_.put_calls);
203 if (!valid_span(
source.data,
source.size) || (!write_back() && !backing_.write))
206 const auto old = find(
key);
208 if (old != no_slot && slot(old).dirty &&
source.size < slot(old).valid_bytes) {
209 const auto result = flush_slot(old);
212 const auto target = old != no_slot && !slot(old).pins ? old : choose(
key);
213 const bool dirty_victim = target != no_slot && target != old && slot(target).dirty;
215 const auto result = flush_slot(target);
218 const Slot old_tag = old == no_slot ? Slot{} : slot(old);
219 const Slot target_tag = target == no_slot ? Slot{} : slot(target);
220 if (old != no_slot) invalidate_slot(old);
221 if (target != no_slot) invalidate_slot(target);
223 if (write_back() && target != no_slot) {
224 count_eviction(target_tag,
key, dirty_victim);
231 const auto result = write(
key,
source,
false);
233 if (old != no_slot && (old_tag.dirty || result.unchanged_on_failure))
235 if (target != no_slot && target != old) slot(target) = target_tag;
236 return result.status;
238 if (target != no_slot) {
239 count_eviction(target_tag,
key, dirty_victim);
246 return invalidate_if([
key](
const Slot& line)
noexcept {
return line.key ==
key; });
249 return invalidate_if([](
const Slot&)
noexcept {
return true; });
252 std::uint64_t byte_offset)
noexcept {
254 const auto first = byte_offset / policy_.page_size;
255 return invalidate_if([=](
const Slot& line)
noexcept {
262 std::uint64_t old_size_bytes)
noexcept {
266 std::uint64_t new_size_bytes)
noexcept {
270 std::uint64_t new_generation)
noexcept {
271 return invalidate_if([=](
const Slot& line)
noexcept {
287 for (std::size_t i = 0; i < slots_; ++i) {
288 const auto result = flush_slot(i);
299 for (std::size_t i = 0; i < slots_; ++i) dirty = dirty || slot(i).dirty;
301 if (!transaction_.discard_allowed || !transaction_.discard_allowed(transaction_.context))
303 for (std::size_t i = 0; i < slots_; ++i)
304 if (slot(i).dirty) invalidate_slot(i);
311 std::size_t slot = no_slot;
313 static void increment(std::uint64_t& counter, std::uint64_t count = 1) noexcept {
314 const auto available = std::numeric_limits<std::uint64_t>::max() - counter;
315 counter += count <= available ? count : available;
317 bool write_back() const noexcept {
320 bool valid_span(
const void*
data, std::size_t size)
const noexcept {
323 Slot& slot(std::size_t i)
noexcept {
325 return *std::launder(
reinterpret_cast<Slot*
>(
326 static_cast<std::byte*
>(memory_) + i *
sizeof(Slot)));
328 const Slot& slot(std::size_t i)
const noexcept {
329 return *std::launder(
reinterpret_cast<const Slot*
>(
330 static_cast<const std::byte*
>(memory_) + i *
sizeof(Slot)));
332 std::byte* payload(std::size_t i)
noexcept {
333 return static_cast<std::byte*
>(memory_) + slots_ *
sizeof(Slot) + i * policy_.page_size;
335 void allocate_slots() noexcept {
336 if (!slots_ || allocation_attempted_)
return;
337 allocation_attempted_ =
true;
340 allocated_bytes_ = slots_ *
line_bytes(policy_.page_size);
341 memory_ = allocator_.allocate
342 ? allocator_.allocate(allocator_.context, allocated_bytes_)
343 : ::operator
new(allocated_bytes_, std::nothrow);
346 allocated_bytes_ = 0;
347 increment(stats_.allocation_bypass_count);
350 for (std::size_t i = 0; i < slots_; ++i)
351 ::new (
static_cast<void*
>(
static_cast<std::byte*
>(memory_) + i *
sizeof(Slot))) Slot{};
352 stats_.current_payload_bytes = slots_ * policy_.page_size;
353 stats_.current_metadata_bytes = slots_ *
sizeof(Slot);
354 stats_.current_bytes = allocated_bytes_;
355 stats_.peak_payload_bytes = stats_.current_payload_bytes;
356 stats_.peak_metadata_bytes = stats_.current_metadata_bytes;
357 stats_.peak_bytes = stats_.current_bytes;
359 std::size_t mapped(ReadThroughCacheKey
key)
const noexcept {
360 const auto hash =
key.page_number
361 ^ (
key.backing_identity * 0x9e3779b97f4a7c15ULL)
362 ^ (
key.generation * 0xbf58476d1ce4e5b9ULL);
363 return static_cast<std::size_t
>(hash % slots_);
365 std::size_t find(ReadThroughCacheKey
key)
const noexcept {
366 if (!memory_)
return no_slot;
368 const auto i = mapped(
key);
369 return slot(i).valid && slot(i).key ==
key ? i : no_slot;
371 for (std::size_t i = 0; i < slots_; ++i)
372 if (slot(i).valid && slot(i).
key ==
key)
return i;
375 std::size_t choose(ReadThroughCacheKey
key)
noexcept {
376 if (!memory_)
return no_slot;
378 const auto i = mapped(
key);
379 return slot(i).pins ? no_slot : i;
381 for (std::size_t i = 0; i < slots_; ++i)
382 if (!slot(i).valid && !slot(i).pins)
return i;
385 for (
unsigned pass = 0; pass < 2; ++pass) {
386 for (std::size_t count = 0; count < slots_; ++count) {
387 const auto i = clock_hand_;
388 clock_hand_ = clock_hand_ + 1 == slots_ ? 0 : clock_hand_ + 1;
389 if (slot(i).pins)
continue;
390 if (!slot(i).recent)
return i;
391 slot(i).recent =
false;
396 std::size_t victim = no_slot;
397 for (std::size_t i = 0; i < slots_; ++i)
398 if (!slot(i).pins && (victim == no_slot || slot(i).age > slot(victim).age))
402 void touch(std::size_t i)
noexcept {
403 slot(i).recent =
true;
405 for (std::size_t j = 0; j < slots_; ++j) {
406 auto& line = slot(j);
407 if (j != i && line.valid && line.age != std::numeric_limits<std::uint64_t>::max())
413 void invalidate_slot(std::size_t i)
noexcept {
414 slot(i).valid =
false;
415 slot(i).dirty =
false;
418 void install(std::size_t i, ReadThroughCacheKey
key, ScratchBytes bytes,
bool dirty)
noexcept {
419 std::memmove(payload(i), bytes.data, bytes.size);
420 auto& line = slot(i);
422 line.valid_bytes = bytes.size;
427 void count_eviction(
const Slot& previous, ReadThroughCacheKey
key,
bool dirty)
noexcept {
428 if (previous.valid && previous.key !=
key) {
429 increment(stats_.evictions);
430 if (dirty) increment(stats_.dirty_evictions);
433 ReadThroughCacheIoResult normalize(ReadThroughCacheIoResult result,
434 std::size_t
requested,
bool reading)
noexcept {
435 const auto completed = result.transferred_bytes <=
requested
437 increment(reading ? stats_.backing_read_bytes : stats_.backing_write_bytes, completed);
438 if (result.transferred_bytes >
requested) {
440 result.unchanged_on_failure =
false;
443 result.unchanged_on_failure =
false;
449 ReadThroughCacheIoResult write(ReadThroughCacheKey
key, ScratchBytes bytes,
450 bool flushing)
noexcept {
451 const auto result = normalize(write_back()
452 ? transaction_.write(transaction_.context,
key, bytes)
453 : backing_.write(backing_.context,
key, bytes), bytes.size,
false);
454 if (flushing && result.status !=
ScratchStatus::ok) increment(stats_.flush_errors);
458 auto& line = slot(i);
460 const auto result = write(line.key, {payload(i), line.valid_bytes},
true);
463 return result.status;
465 Loaded load(ReadThroughCacheKey
key, ScratchBuffer destination)
noexcept {
467 const auto old = find(
key);
468 if (old != no_slot && slot(old).valid_bytes >= destination.size) {
469 increment(stats_.hits);
471 std::memmove(destination.data, payload(old), destination.size);
474 increment(stats_.misses);
475 const auto target = old != no_slot && !slot(old).pins ? old : choose(
key);
476 const Slot previous = target == no_slot ? Slot{} : slot(target);
477 const bool dirty_prefix = old != no_slot && slot(old).dirty;
478 if (target != no_slot) {
479 if (!previous.dirty) {
480 count_eviction(previous,
key,
false);
481 invalidate_slot(target);
484 increment(stats_.bypass_reads);
486 if (old != no_slot && !dirty_prefix) invalidate_slot(old);
489 const auto result = normalize(backing_.read(backing_.context,
key, destination),
490 destination.size,
true);
495 std::memmove(destination.data, payload(old), slot(old).valid_bytes);
497 if (target != no_slot) {
498 if (previous.dirty && target != old) {
499 const auto flushed = flush_slot(target);
501 count_eviction(previous,
key,
true);
503 if (old != no_slot) invalidate_slot(old);
504 invalidate_slot(target);
505 install(target,
key, {destination.data, destination.size}, dirty_prefix);
509 template<
class Predicate>
515 for (std::size_t i = 0; i < slots_; ++i)
516 if (slot(i).valid && slot(i).dirty && matches(slot(i)))
518 for (std::size_t i = 0; i < slots_; ++i)
519 if (slot(i).valid && matches(slot(i))) invalidate_slot(i);
522 void release_pin(std::size_t i)
noexcept {
523 if (i != no_slot) --slot(i).pins;
524 if (stats_.current_pins) --stats_.current_pins;
527 ReadThroughCachePolicy policy_;
528 ReadThroughCacheBacking backing_;
529 ReadThroughCacheAllocator allocator_;
530 ReadThroughCacheTransactionOrder transaction_;
531 ReadThroughCacheStats stats_{};
533 const ReportScratchIoError* failure_ =
nullptr;
534 void* memory_ =
nullptr;
535 std::size_t slots_ = 0;
536 std::size_t allocated_bytes_ = 0;
537 std::size_t clock_hand_ = 0;
538 bool allocation_attempted_ =
false;