Repository navigation
Expand file tree
/
Copy pathkvflash_pager.h
More file actions
1739 lines (1647 loc) · 83.9 KB
/
Copy pathkvflash_pager.h
File metadata and controls
1739 lines (1647 loc) · 83.9 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// KvFlashPager — KVFlash core: a bounded resident pool for the
// full-attention KV cache (see optimizations/kvflash/).
//
// Lookahead-sparse-attention-style (FlashMemory, arXiv 2606.09079)
// decode-time KV residency for the qwen35 target: the cache tensors are
// allocated at POOL size (a fraction of the logical context), and this
// class owns the mapping from logical token positions to physical pool
// slots. Chunks (64 logical tokens) that fall cold are paged out to a
// host backing store and their slots are reused; paged-out chunks remain
// recallable bit-exact. GPU footprint is a hard O(pool) bound regardless
// of logical context length.
//
// Policy-agnostic by design: with no scorer, eviction is LRU over
// unprotected chunks (recency-only memory). A KvFlashScorer plugged into
// `score_hook` upgrades eviction and reselect() to relevance-driven
// residency; with pflash enabled, its drafter attaches automatically
// (KvFlashDrafterScorer) and recalls cold context the generation needs.
//
// Correctness notes (why relocating rows is legal):
// * RoPE is baked into K rows at write time from the `positions` input,
// so a row's physical slot is semantically irrelevant.
// * Attention runs over the whole pool with a slot-validity mask
// (resident = 0, free/paged-out = -inf). The mask must be re-uploaded
// before EVERY compute: input tensors live in the gallocr compute
// buffer whose regions are reused during graph execution.
// * Freed slots are additionally zeroed (defense in depth; a zero K row
// contributes exp(-max) ~ 0, the same assumption the production
// stride-256 padded span relies on in maskless mode).
// * The FWHT K-rotation and KV quantization operate per-row; page-out /
// page-in moves raw quantized bytes and is therefore bit-exact.
//
// Scope: full-attention layers only. DeltaNet/conv recurrent state is
// fixed-size, position-dependent in-place state and is never paged.
//
// Async DMA (KVFLASH_HAS_ASYNC_DMA):
// When built with a CUDA or HIP backend, page-out (D2H) and page-in
// (H2D) transfers run on a dedicated page_stream_ rather than blocking
// the decode thread via ggml_backend_tensor_get/set. Host backing
// buffers are cudaMallocHost-pinned for maximum PCIe throughput.
// alloc_span() synchronises page_stream_ only if a page-in was issued
// (H2D must complete before the next attention forward). Page-outs are
// queued, but slot_for() does not hand out the block they freed until the
// compute stream is ordered after them: a device-side wait if the backend
// registered its stream (CUDA), otherwise a host wait. So the nested
// default-path allocation can sync after a page-out, and the new K/V write
// cannot overtake the copy or the zeroing. On the same stream, page-out D2H
// always precedes the slot zero (cudaMemsetAsync), which in turn precedes any
// page-in H2D, so host_data is coherent by the time it is read back.
#pragma once
#include "ggml.h"
#include "ggml-backend.h"
#include "fnv.h"
#include "kvflash_pool_flag.h"
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <limits>
#include <string>
#include <vector>
// Async DMA via a dedicated copy stream — enabled when a GPU runtime is
// available. gpu_runtime_compat.h maps cuda* → hip* on HIP builds and
// pulls in <cuda_runtime.h> on CUDA builds.
#if defined(LUCE_BACKEND_CUDA) || defined(LUCE_BACKEND_HIP) || defined(GGML_USE_HIP)
#include "gpu_runtime_compat.h"
#define KVFLASH_HAS_ASYNC_DMA 1
// ponytail: the device-side fence re-records one event per fence, which CUDA
// allows and HIP documents as undefined while an earlier record is pending. HIP
// builds therefore stay on the host wait (one stall per reused block after a
// page-out on AMD). Upgrade: an event per pending record, or a HIP-verified reuse.
#if !defined(LUCE_BACKEND_HIP) && !defined(GGML_USE_HIP)
#define KVFLASH_EVENT_FENCE 1
#endif
#endif
// serialize()/deserialize() write and read integers and floats in host byte
// order, so the blob is little-endian only on little-endian hosts. There is no
// byte-swapping encoder; refuse to build where the blob would not be portable.
#if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__)
static_assert(__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__,
"KvFlashPager blobs are written in host byte order and are defined as little-endian");
#endif
namespace luce::common {
struct KvFlashConfig {
int chunk_tokens = 64; // logical tokens per page
int pool_tokens = 0; // resident pool capacity (multiple of chunk_tokens)
int sink_chunks = 1; // leading chunks never evicted (attention sinks)
int tail_window_chunks = 4; // trailing chunks never evicted (local window)
int row_base = 0; // first row of this pool inside a shared KV allocation (slot slice)
};
struct KvFlashStats {
int64_t page_outs = 0;
int64_t page_ins = 0;
int64_t host_bytes = 0; // backing store currently held on host
int64_t moved_bytes = 0; // cumulative D2H+H2D traffic
int64_t d2h_skipped = 0; // page-outs whose D2H was skipped: host copy already equal to the block
int64_t fence_points = 0; // block hand-outs that fenced the page stream (a host wait each on HIP when work is queued)
};
class KvFlashPager {
public:
// `attn_k` / `attn_v` are the per-full-attention-layer cache tensors,
// each [head_dim, pool_tokens, n_head_kv]. All must share dims/types
// within their K/V group.
// Minimum pool for a config: sinks + trailing window stay resident
// unconditionally, so at least 2 more chunks are required (1 evictable
// victim + the partially filled append head) or eviction deadlocks and
// slot_for() starts failing once the pool fills.
static int min_pool_tokens(const KvFlashConfig & cfg) {
return (cfg.sink_chunks + cfg.tail_window_chunks + 2) * cfg.chunk_tokens;
}
~KvFlashPager() { cleanup_(); }
bool attach(const KvFlashConfig & cfg,
const std::vector<ggml_tensor *> & attn_k,
const std::vector<ggml_tensor *> & attn_v) {
if (cfg.pool_tokens <= 0 || cfg.pool_tokens % cfg.chunk_tokens != 0) return false;
if (cfg.row_base < 0 || cfg.row_base % cfg.chunk_tokens != 0) return false;
if (cfg.pool_tokens < min_pool_tokens(cfg)) {
std::fprintf(stderr,
"kvflash: pool %d < minimum %d (%d sink + %d tail chunks must "
"leave an evictable block)\n",
cfg.pool_tokens, min_pool_tokens(cfg),
cfg.sink_chunks, cfg.tail_window_chunks);
return false;
}
if (attn_k.size() != attn_v.size()) return false;
// Reject a tensor that cannot hold the pool BEFORE touching any state,
// so a failed attach leaves the previous attachment intact.
const int64_t need_rows = (int64_t)cfg.row_base + cfg.pool_tokens;
for (size_t l = 0; l < attn_k.size(); l++)
if ((int64_t)attn_k[l]->ne[1] < need_rows || (int64_t)attn_v[l]->ne[1] < need_rows) return false;
cleanup_(); // release pinned buffers + stream from any prior attach
cfg_ = cfg;
row_base_ = cfg.row_base;
attn_k_ = attn_k;
attn_v_ = attn_v;
n_blocks_ = cfg.pool_tokens / cfg.chunk_tokens;
if (!attn_k.empty()) {
const ggml_tensor * K0 = attn_k[0];
n_head_kv_ = (int)K0->ne[2];
// Per-(tensor, head) contiguous segment of chunk_tokens rows.
k_seg_bytes_ = (size_t)cfg.chunk_tokens * K0->nb[1];
v_seg_bytes_ = (size_t)cfg.chunk_tokens * attn_v[0]->nb[1];
chunk_bytes_ = (k_seg_bytes_ + v_seg_bytes_) * (size_t)n_head_kv_ * attn_k.size();
zero_buf_.assign(std::max(k_seg_bytes_, v_seg_bytes_), 0);
} else {
n_head_kv_ = 0;
k_seg_bytes_ = 0;
v_seg_bytes_ = 0;
chunk_bytes_ = 0;
zero_buf_.clear();
}
free_blocks_.clear();
unzeroed_.assign((size_t)n_blocks_, 0);
pending_free_.clear();
for (int b = n_blocks_ - 1; b >= 0; b--) free_blocks_.push_back(b);
chunks_.clear();
pinned_.clear(); // pins belong to the previous pool geometry
stats_ = {};
clock_ = 0;
has_pending_page_in_ = false;
generation_++;
#ifdef KVFLASH_HAS_ASYNC_DMA
if (ext_page_stream_) {
page_stream_ = ext_page_stream_; // the arena's stream; never ours to destroy
} else if (cudaStreamCreate(&page_stream_) != cudaSuccess) {
std::fprintf(stderr, "[kvflash] cudaStreamCreate failed; paging "
"falls back to the (blocking) default stream\n");
page_stream_ = nullptr;
}
#ifdef KVFLASH_EVENT_FENCE
if (cudaEventCreateWithFlags(&page_event_, cudaEventDisableTiming) != cudaSuccess) {
page_event_ = nullptr; // set_compute_stream() then keeps the host wait
cudaGetLastError();
}
#endif
#endif
return true;
}
// Host backing is pinned (cudaMallocHost) on GPU builds. Pass false to use
// pageable memory instead: slower DMA, but works where pinned allocation is
// unavailable (hosted CI with a stub driver, CPU-backend tests). Set it
// before the first page_out/deserialize; each chunk remembers how its own
// buffer was allocated. No effect on builds without async DMA.
void set_pinned_host_backing(bool pinned) { pinned_host_ = pinned; }
// Optional: custom block hand-out order (e.g. shuffled placement in
// relocation tests). `order[i]` = i-th block to hand out.
// `order` holds ARENA block ids (block_of() space) of this pool, each at
// most once; anything else is refused and the free list is left alone.
bool set_block_order(const std::vector<int> & order) {
std::vector<int> local;
std::vector<char> seen((size_t)n_blocks_, 0);
const int lo = row_base_ / cfg_.chunk_tokens;
for (int b : order) {
const int l = b - lo;
if (l < 0 || l >= n_blocks_ || seen[(size_t)l]) return false;
seen[(size_t)l] = 1;
local.push_back(l);
}
free_blocks_.assign(local.rbegin(), local.rend());
return true;
}
// Drop all mappings and host backing (new request / cache reset).
// Cumulative stats are kept; the epoch advances so cached masks refill.
void reset() {
#ifdef KVFLASH_HAS_ASYNC_DMA
sync_page_stream_();
for (auto & st : chunks_) free_host_buffer_(st);
#endif
chunks_.clear();
free_blocks_.clear();
pending_free_.clear();
generation_++; // ops planned against the previous request are stale
for (int b = n_blocks_ - 1; b >= 0; b--) free_blocks_.push_back(b);
stats_.host_bytes = 0;
cur_chunk_ = 0;
epoch_++;
has_pending_page_in_ = false;
unpin_all(); // pins are per-request; the backend re-applies them
// Drop any relevance scoring from the previous request: a stale
// score_hook could otherwise select an in-flight chunk of a multi-chunk
// prefill ubatch as an eviction victim. It is re-installed by the
// decode-time reselect path, so pooled prefill falls back to LRU, where
// the just-allocated (newest) chunks are never victims.
score_hook = nullptr;
}
// Drop every logical position >= P: chunks entirely >= P give their pool
// block back to the free list and lose their host copy and score; the
// chunk containing P keeps its block (or host copy) with rows >= P zeroed.
// Pins on dropped chunks are removed, so a pin range is clipped to P. The
// result matches a pager that only ever saw P tokens. P <= 0 empties the
// pager (pins kept clipped to nothing); P at or beyond the materialized
// length is a no-op. Valid for any P because full-attention KV at a
// position does not depend on later tokens.
void truncate(int64_t P) {
if (!attached()) return;
if (P < 0) P = 0;
if (P >= (int64_t)chunks_.size() * cfg_.chunk_tokens) return;
generation_++; // page-outs planned against the longer sequence are stale
synchronize_paging(); // queued page DMA must not touch what is freed below
const int keep = (int)((P + cfg_.chunk_tokens - 1) / cfg_.chunk_tokens);
for (int c = (int)chunks_.size() - 1; c >= keep; c--) {
ChunkState & st = chunks_[(size_t)c];
if (st.block >= 0) {
zero_block(st.block);
free_blocks_.push_back(st.block);
}
if (st.on_host && has_tensor_storage()) {
release_host_(st);
stats_.host_bytes -= (int64_t)chunk_bytes_;
}
}
chunks_.resize((size_t)keep);
if (pinned_.size() > (size_t)keep) pinned_.resize((size_t)keep);
if (keep > 0 && P % cfg_.chunk_tokens != 0) {
zero_chunk_rows_(keep - 1, (int)(P % cfg_.chunk_tokens));
}
cur_chunk_ = keep > 0 ? keep - 1 : 0;
epoch_++;
synchronize_paging(); // zeroing is queued on page_stream_
if (keep <= n_blocks_) relayout_identity_(keep);
else refill_after_truncate_();
synchronize_paging(); // recalls are queued on page_stream_
}
// The retained prefix fits the pool: a pager that only ever saw it holds
// every chunk resident in block c, and pool attention reduces over physical
// slots in order, so the block map must match or the rounding differs. Move
// every retained chunk to block c (resident ones from wherever the history
// left them, host-only ones from their host copy), then rebuild the free
// stack so later appends get keep, keep+1, ... Moves go through a host
// scratch buffer, one chunk at a time, in an order that never overwrites a
// block still holding a chunk to move (a cycle parks one chunk first).
void relayout_identity_(int keep) {
std::vector<int> occ((size_t)n_blocks_, -1); // block -> retained resident chunk
for (int c = 0; c < keep; c++)
if (chunks_[(size_t)c].block >= 0) occ[(size_t)chunks_[(size_t)c].block] = c;
std::vector<int> vacated; // blocks >= keep that held a retained chunk
for (int b = keep; b < n_blocks_; b++)
if (occ[(size_t)b] >= 0) vacated.push_back(b);
std::vector<uint8_t> buf, held;
if (has_tensor_storage()) { buf.resize(chunk_bytes_); held.resize(chunk_bytes_); }
auto move_to = [&](int c) { // resident chunk c -> block c (free), via buf
ChunkState & st = chunks_[(size_t)c];
copy_block_(st.block, buf.data(), /*to_host=*/true);
synchronize_paging();
copy_block_(c, buf.data(), /*to_host=*/false);
synchronize_paging();
occ[(size_t)st.block] = -1;
st.block = c;
occ[(size_t)c] = c;
};
auto movable = [&](int d) {
const int b = chunks_[(size_t)d].block;
return b >= 0 && b != d && occ[(size_t)d] < 0;
};
for (;;) {
bool progress = false, pending = false;
for (int c = 0; c < keep; c++) {
const int b = chunks_[(size_t)c].block;
if (b < 0 || b == c) continue;
pending = true;
if (movable(c)) { move_to(c); progress = true; }
}
if (progress) continue;
if (!pending) break;
// Only cycles remain: park one chunk's bytes, which frees its block.
int c = 0;
while (chunks_[(size_t)c].block < 0 || chunks_[(size_t)c].block == c) c++;
ChunkState & st = chunks_[(size_t)c];
copy_block_(st.block, held.data(), /*to_host=*/true);
synchronize_paging();
occ[(size_t)st.block] = -1;
st.block = -1;
for (bool again = true; again;) { // unwind the cycle into the freed block
again = false;
for (int d = 0; d < keep; d++)
if (movable(d)) { move_to(d); again = true; }
}
copy_block_(c, held.data(), /*to_host=*/false);
synchronize_paging();
st.block = c;
occ[(size_t)c] = c;
}
for (int b : vacated) zero_block(b);
for (int c = 0; c < keep; c++) { // host-only chunks: recall into their own block
ChunkState & st = chunks_[(size_t)c];
if (st.block >= 0 || !st.on_host) continue;
st.block = c;
st.dirty = false;
copy_chunk(c, c, /*to_host=*/false);
stats_.page_ins++;
stats_.moved_bytes += chunk_bytes_;
}
synchronize_paging();
free_blocks_.clear();
for (int b = n_blocks_ - 1; b >= keep; b--) free_blocks_.push_back(b);
for (auto & st : chunks_) st.last_use = ++clock_;
epoch_++;
}
// After truncate the pool holds what the dropped tail left behind: after a
// long decode that is the NEWEST chunks, with older prompt chunks on host
// and free blocks to spare. A pager that only ever saw P tokens would hold
// the best ones that fit (recency, or score when a scorer is attached), so
// recall host chunks into the free blocks the same way, then renumber the
// use clock in logical order (as appending produces it) so later evictions
// pick the same victims. Residency is exact either way (host copies are
// bit-exact); this only changes which chunks decode and replay attend over.
void refill_after_truncate_() {
std::vector<int> host;
for (int c = 0; c < (int)chunks_.size(); c++)
if (chunks_[(size_t)c].block < 0 && chunks_[(size_t)c].on_host) host.push_back(c);
// Protected chunks (sink, tail window, pins) come back first, exactly
// as a fresh pager would hold them; only the rest is ranked.
auto prot = [&](int c) {
return c < cfg_.sink_chunks || c > cur_chunk_ - 1 - cfg_.tail_window_chunks ||
is_pinned(c);
};
auto mid = std::stable_partition(host.begin(), host.end(), prot);
if (score_hook)
std::stable_sort(mid, host.end(),
[&](int a, int b) { return score_hook(a) > score_hook(b); });
else
std::reverse(mid, host.end()); // newest first
std::vector<int> take(host.begin(),
host.begin() + std::min(host.size(), free_blocks_.size()));
std::sort(take.begin(), take.end()); // recall oldest first
for (int c : take) page_in(c);
for (auto & st : chunks_) st.last_use = 0;
for (int c = 0; c < (int)chunks_.size(); c++) chunks_[(size_t)c].last_use = ++clock_;
}
// Zero every currently-free block. reset() drops mappings but leaves the
// previous request's bytes in place; maskless consumers (the qwen35moe
// pipelined decode reads the whole padded pool span with no slot mask)
// need stale rows to dequantise to ~zero contribution. Masked consumers
// don't need this but it is cheap (pool-sized memset, sub-ms).
void zero_free_blocks() {
for (int b : free_blocks_) zero_block(b);
#ifdef KVFLASH_HAS_ASYNC_DMA
sync_page_stream_();
#endif
}
bool attached() const { return n_blocks_ > 0; }
int pool_tokens() const { return cfg_.pool_tokens; }
int chunk_tokens() const { return cfg_.chunk_tokens; }
// Optional external relevance score; higher = keep. Falls back to LRU.
std::function<float(int /*chunk*/)> score_hook;
// Pin the chunks overlapping logical token range [tok_lo, tok_hi)
// (half-open). Pinned chunks are never eviction victims and are always
// kept by reselect(), on top of the sink/tail protections. Pins are
// cleared by reset() (and so by deserialize()). Best-effort deadlock
// guard: if sink + tail + pinned + 2 would exceed the pool the whole span
// is refused with a warning and no pin is set. Empty/inverted ranges are
// no-ops.
void pin_range(int64_t tok_lo, int64_t tok_hi) { pin_chunks_(tok_lo, tok_hi, kPinHard); }
void pin_chunks_(int64_t tok_lo, int64_t tok_hi, uint8_t kind) {
if (!attached() || tok_lo < 0 || tok_hi <= tok_lo) return;
// Validate in 64 bits BEFORE narrowing to a chunk index: a position past
// 2^31 chunks would wrap negative and index pinned_ out of bounds, and a
// span longer than the pool could never be pinned anyway (so the scan
// below stays O(pool) and pinned_ stays small).
const int64_t lo64 = tok_lo / cfg_.chunk_tokens;
const int64_t hi64 = (tok_hi - 1) / cfg_.chunk_tokens; // inclusive
if (hi64 >= kMaxPinChunks || hi64 - lo64 + 1 > n_blocks_) {
std::fprintf(stderr,
"[kvflash] pin_range [%lld,%lld) refused: chunks [%lld,%lld] "
"outside the pinnable range (< %d chunks, span <= %d)\n",
(long long)tok_lo, (long long)tok_hi, (long long)lo64,
(long long)hi64, kMaxPinChunks, n_blocks_);
return;
}
const int c_lo = (int)lo64;
const int c_hi = (int)hi64;
int pinned = 0, fresh = 0;
for (uint8_t f : pinned_) pinned += f != 0;
for (int c = c_lo; c <= c_hi; c++) fresh += !is_pinned(c);
if (cfg_.sink_chunks + cfg_.tail_window_chunks + pinned + fresh + 2 > n_blocks_) {
std::fprintf(stderr,
"[kvflash] pin_range [%lld,%lld) refused: sink=%d tail=%d "
"pinned=%d new=%d pool_blocks=%d would deadlock eviction\n",
(long long)tok_lo, (long long)tok_hi, cfg_.sink_chunks,
cfg_.tail_window_chunks, pinned, fresh, n_blocks_);
return;
}
if (c_hi + 1 > (int)pinned_.size()) pinned_.resize((size_t)c_hi + 1, 0);
for (int c = c_lo; c <= c_hi; c++)
if (kind == kPinHard || !pinned_[(size_t)c]) pinned_[(size_t)c] = kind;
}
// Pin the chunks overlapping [tok_lo, tok_hi) until end_step(). Same
// guard and refusal as pin_range, and the step pins count against it. A
// chunk already pinned by pin_range stays hard-pinned.
void pin_step_range(int64_t tok_lo, int64_t tok_hi) { pin_chunks_(tok_lo, tok_hi, kPinStep); }
// Step boundary: step pins expire, pin_range pins stay.
void end_step() {
for (auto & f : pinned_) if (f == kPinStep) f = 0;
}
bool is_pinned(int c) const {
return c >= 0 && c < (int)pinned_.size() && pinned_[(size_t)c] != 0;
}
void unpin_all() { std::fill(pinned_.begin(), pinned_.end(), 0); }
// Allocate slots for [kv_start, kv_start + n_tok) ahead of a forward
// step (evicting LRU/low-score chunks as needed). False — with a
// diagnostic — if the pool has no evictable block left.
//
// When KVFLASH_HAS_ASYNC_DMA: page-out D2H and slot-zero transfers are
// queued on page_stream_ and left running. If any page-in (H2D) was
// issued, page_stream_ is synchronised here so that recalled KV data is
// resident before the next attention forward.
bool alloc_span(int kv_start, int n_tok) {
for (int i = 0; i < n_tok; ++i) {
if (slot_for(kv_start + i) < 0) {
std::fprintf(stderr, "[kvflash] no pool slot at pos %d "
"(pool %d exhausted)\n",
kv_start + i, cfg_.pool_tokens);
return false;
}
}
if (has_pending_page_in_ && !batch_submit_) synchronize_paging(); // batch: the step's one Fence waits
return true;
}
// Physical pool slot for logical position `pos`. Allocates (and, when
// the pool is full, evicts) at chunk granularity. Call once per
// appended token, in logical order.
// A slot_for() is a row write request: the chunk's host copy (if any) is stale
// from here on, so the next page_out copies.
int slot_for(int64_t pos) { return slot_for_(pos, /*write=*/true); }
// `write` false is a pure recall (page_in, deserialize): a chunk restored from
// host stays clean, so page_out can skip the D2H while no row is written.
int slot_for_(int64_t pos, bool write) {
const int c = (int)(pos / cfg_.chunk_tokens);
// cur_chunk_ tracks the append head only; a page_in of an older
// chunk must not shrink the protected tail window. It must advance
// BEFORE eviction (so the victim search protects the new tail), but
// a failed allocation must roll it back or the next eviction's tail
// window is computed from a chunk that never materialized.
const int prev_cur_chunk = cur_chunk_;
if (c > cur_chunk_) cur_chunk_ = c;
if ((int)chunks_.size() <= c) chunks_.resize(c + 1);
ChunkState & st = chunks_[c];
if (st.block < 0) {
if (!ensure_free_block()) {
cur_chunk_ = prev_cur_chunk;
return -1;
}
st.block = free_blocks_.back();
free_blocks_.pop_back();
epoch_++;
// A block freed without zeroing: a recall overwrites all of it, a fresh chunk needs the zeros.
if (!unzeroed_.empty() && unzeroed_[(size_t)st.block]) {
unzeroed_[(size_t)st.block] = 0;
if (!st.on_host) zero_block(st.block);
}
st.dirty = write || !st.on_host;
if (st.dirty) st.ver = ++ver_seq_;
if (st.on_host) { // recall: restore paged-out bytes
copy_chunk(c, st.block, /*to_host=*/false);
stats_.page_ins++;
stats_.moved_bytes += chunk_bytes_;
#ifdef KVFLASH_HAS_ASYNC_DMA
has_pending_page_in_ = true;
#endif
}
// The caller uses this block on the compute stream next.
fence_page_work_();
}
else if (write) { st.dirty = true; st.ver = ++ver_seq_; }
st.last_use = ++clock_;
return row_base_ + st.block * cfg_.chunk_tokens + (int)(pos % cfg_.chunk_tokens);
}
// Force a chunk out of the pool (host backing + zeroed slots). A pinned
// chunk is refused: its rows belong to the step (or request) that pinned it.
bool page_out(int c) { return page_out_(c, /*lazy_zero=*/false); }
// lazy_zero: leave the freed block unzeroed; the caller guarantees the block is
// handed to slot_for_() at once or flush_unzeroed_() runs before any attention read.
bool page_out_(int c, bool lazy_zero) {
if (c >= (int)chunks_.size() || chunks_[c].block < 0 || is_pinned(c)) return false;
ChunkState & st = chunks_[c];
if (has_tensor_storage() && !st.on_host) {
#ifdef KVFLASH_HAS_ASYNC_DMA
if (!alloc_host_buffer_(st)) return false;
#else
st.host_data.resize(chunk_bytes_);
#endif
stats_.host_bytes += (int64_t)chunk_bytes_;
}
// A chunk recalled from host and not written since holds the bytes its host
// copy already has (every row write goes through slot_for(), which sets dirty).
const bool skipped = has_tensor_storage() && st.on_host && !st.dirty;
if (skipped) stats_.d2h_skipped++;
else copy_chunk(c, st.block, /*to_host=*/true);
if (lazy_zero && !deferred_free_) unzeroed_[(size_t)st.block] = 1;
else zero_block(st.block);
st.on_host = true;
st.dirty = false;
if (deferred_free_) pending_free_.push_back({st.block, ++record_seq_});
else free_blocks_.push_back(st.block);
st.block = -1;
epoch_++;
stats_.page_outs++;
if (!skipped) stats_.moved_bytes += chunk_bytes_;
return true;
}
// Page-out for an op planned against `generation` (generation() when it was
// planned): a request that ended or restarted in between (reset/attach)
// makes the op stale, and a stale op must not evict the new request's chunk.
bool page_out_checked(int c, uint64_t generation) {
return generation == generation_ && evictable_(c) && page_out(c);
}
uint64_t generation() const { return generation_; }
// Failed step: step pins expire and every queued copy settles (the host
// wait), so deferred frees complete and nothing in flight touches a block
// the caller releases next. Idempotent; hard pins stay.
void abort_step() {
end_step();
synchronize_paging();
generation_++; // page-outs planned before the abort are stale
}
// Arena mode (KvFlashArena): copies are only queued. slot_for/alloc_span do
// not wait or fence; the step plan's one Fence orders the compute stream
// after them, and arena completion reclaims the blocks.
void set_batch_submit(bool on) { batch_submit_ = on; }
void * page_stream() const {
#ifdef KVFLASH_HAS_ASYNC_DMA
return page_stream_;
#else
return nullptr;
#endif
}
// Use the arena's page stream. Before attach(); never destroyed here.
void set_external_page_stream(void * stream) {
#ifdef KVFLASH_HAS_ASYNC_DMA
ext_page_stream_ = (cudaStream_t)stream;
#else
(void)stream;
#endif
}
// Recall a chunk into the pool (used by reselect / tests).
bool page_in(int c) {
if (c >= (int)chunks_.size() || !chunks_[c].on_host || chunks_[c].block >= 0) return false;
return slot_for_((int64_t)c * cfg_.chunk_tokens, /*write=*/false) >= 0;
}
// Optional fast path (CUDA). The stream that consumes the pool (the
// backend's compute stream) is non-blocking, so it is NOT implicitly
// ordered with page_stream_. By default slot_for() therefore waits on the
// host for the queued page work before it hands out a block. With the
// compute stream registered here it instead makes that stream wait on the
// device, with no host stall for that fence (recall in alloc_span() and
// reselect() still waits on the host). Call after attach(), which clears
// it. Only register a stream that runs EVERY graph touching the pool: a
// pool spread over several devices (layer split) has one compute stream
// per device and must stay on the default. Ignored on HIP builds.
void set_compute_stream(void * stream) {
#ifdef KVFLASH_EVENT_FENCE
compute_stream_ = (cudaStream_t)stream;
#else
(void)stream;
#endif
}
// Block until queued page DMA on page_stream_ completes. Hot paths
// (alloc_span/reselect) batch this internally after their recalls; callers
// that issue page_in()/page_out() directly and then read device KV (tests,
// tools) must call this first. No-op when async DMA is compiled out.
void synchronize_paging() {
#ifdef KVFLASH_HAS_ASYNC_DMA
sync_page_stream_();
#endif
has_pending_page_in_ = false;
complete(record_seq_); // every queued D2H has landed
}
// Deferred free: with deferral on, a page-out's block goes to a pending
// list and is allocatable only after complete(record) for a record >= its
// own. Off by default: blocks are reusable at once and slot_for() fences
// instead. With deferral on, an alloc that finds only pending blocks fails
// (no extra victim is taken) and an eviction on demand queues its block and
// fails once; the caller runs page-outs a step ahead, completes, then
// allocates.
// ponytail: completion is the caller's explicit complete() (tests) or
// synchronize_paging() (the host wait, HIP's step-end sync). The CUDA event
// query per record is a later device step.
void set_deferred_free(bool on) { deferred_free_ = on; }
uint64_t last_record() const { return record_seq_; } // record of the latest page-out
int pending_free_blocks() const { return (int)pending_free_.size(); }
void complete(uint64_t record) {
size_t keep = 0;
for (const auto & pf : pending_free_) {
if (pf.second <= record) free_blocks_.push_back(pf.first);
else pending_free_[keep++] = pf;
}
pending_free_.resize(keep);
}
bool is_resident(int c) const {
return c < (int)chunks_.size() && chunks_[c].block >= 0;
}
// True while every materialized chunk still sits in its identity block
// (chunk c in block c, nothing paged out). This is the layout contract
// identity-copy snapshots rely on; it holds from reset() until the
// first eviction of the CURRENT request (cumulative stats do not).
// Arena identity: false at any nonzero row_base, because "chunk c in
// block c" then names another slot's rows.
bool is_identity() const {
if (row_base_ != 0) return false;
for (int c = 0; c < (int)chunks_.size(); c++) {
if (chunks_[c].block >= 0 && chunks_[c].block != c) return false;
if (chunks_[c].block < 0 && chunks_[c].on_host) return false;
}
return true;
}
// True iff every chunk intersecting [0, n_tok) is resident in its identity
// block (block_of(c) == c). Expresses "the logical prefix [0, n_tok) is a
// contiguous, identity-mapped, materialized span" — the exact precondition
// the non-paged tree-verify graph relies on. Stronger than is_identity(),
// which is also true for an empty / not-yet-materialized pager.
bool identity_prefix_covers(int n_tok) const {
if (row_base_ != 0) return false; // arena identity only
if (n_tok <= 0) return true;
const int nc = (n_tok + cfg_.chunk_tokens - 1) / cfg_.chunk_tokens;
if (nc > (int)chunks_.size()) return false;
for (int c = 0; c < nc; c++)
if (chunks_[c].block != c) return false;
return true;
}
// ARENA block holding chunk c (row_base()/chunk_tokens + pool-local
// block), -1 if not resident: the block-table entry and the tensor row
// block, in the same space as slot_for()/slot_of().
int block_of(int c) const {
if (c < 0 || c >= (int)chunks_.size() || chunks_[c].block < 0) return -1;
return row_base_ / cfg_.chunk_tokens + chunks_[c].block;
}
// First arena row of this pool (0 unless it is a slot slice).
int row_base() const { return row_base_; }
// Everything that reaches a tensor, graph, mask or snapshot is in ARENA
// space: slot_for()/slot_of() rows, block_of() blocks, and the columns of
// fill_slot_pos()/fill_slot_mask() (dst holds arena_tokens() entries; the
// columns outside this slice stay empty). Pool-local ids are internal.
int arena_tokens() const { return row_base_ + cfg_.pool_tokens; }
// Const lookup (no alloc / LRU touch): physical slot currently holding
// logical `pos`, or -1 if its chunk is not resident. Callers that may
// need an allocation must use slot_for() beforehand.
int slot_of(int64_t pos) const {
const int c = (int)(pos / cfg_.chunk_tokens);
if (c >= (int)chunks_.size() || chunks_[c].block < 0) return -1;
return row_base_ + chunks_[c].block * cfg_.chunk_tokens + (int)(pos % cfg_.chunk_tokens);
}
// Logical position held by each pool slot, -1 for free blocks. `dst`
// must hold arena_tokens() entries. Lets callers build masks that need
// POSITION semantics in slot space (causal / sliding-window): the
// mask condition is evaluated on dst[slot] instead of the column index.
void fill_slot_pos(int32_t * dst) const {
for (int i = 0; i < arena_tokens(); i++) dst[i] = -1;
for (int c = 0; c < (int)chunks_.size(); c++) {
if (chunks_[c].block < 0) continue;
int32_t * p = dst + (size_t)row_base_ + (size_t)chunks_[c].block * cfg_.chunk_tokens;
for (int i = 0; i < cfg_.chunk_tokens; i++)
p[i] = (int32_t)c * cfg_.chunk_tokens + i;
}
}
const KvFlashStats & stats() const { return stats_; }
size_t chunk_bytes() const { return chunk_bytes_; }
int resident_blocks() const { return n_blocks_ - (int)free_blocks_.size() - (int)pending_free_.size(); }
int n_chunks() const { return (int)chunks_.size(); }
int cur_chunk() const { return cur_chunk_; }
int n_pool_blocks() const { return n_blocks_; }
// Bytes of one (layer, kv_head) K segment: chunk_tokens contiguous rows.
size_t k_seg_bytes() const { return k_seg_bytes_; }
// Host copy of chunk c's K rows for (layer, kv_head), or nullptr when the
// chunk is resident (read the pool tensor instead) or has no host copy.
// Host layout (see copy_chunk): per layer, K for all heads then V for all
// heads, each segment k_seg_bytes_ / v_seg_bytes_.
const uint8_t * host_k_seg(int c, int layer, int head) const {
if (!has_tensor_storage() || c < 0 || c >= (int)chunks_.size()) return nullptr;
const ChunkState & st = chunks_[(size_t)c];
if (st.block >= 0 || !st.on_host) return nullptr;
if (layer < 0 || layer >= (int)attn_k_.size() || head < 0 || head >= n_head_kv_) return nullptr;
const size_t off = (size_t)layer * n_head_kv_ * (k_seg_bytes_ + v_seg_bytes_) +
(size_t)head * k_seg_bytes_;
#ifdef KVFLASH_HAS_ASYNC_DMA
return (const uint8_t *)st.host_data + off;
#else
return st.host_data.data() + off;
#endif
}
// Identity of chunk c's rows: a new value whenever they may have changed (a row write, a truncate through the
// chunk, a deserialize), the same value while the chunk only moves between the pool and its host copy. Never
// reused within this pager; 0 = no such chunk.
uint64_t chunk_version(int c) const { return c >= 0 && c < (int)chunks_.size() ? chunks_[(size_t)c].ver : 0; }
// Bumped on every residency change (alloc / page_out / page_in).
// Callers cache the slot mask and refill only when the epoch moves.
uint64_t epoch() const { return epoch_; }
// F16 slot-validity mask for one query row: 0 for slots belonging to a
// resident chunk, -inf for free / paged-out blocks. `dst` must hold
// arena_tokens() entries. Used as the FA mask so non-resident slots are
// excluded exactly instead of via the zero-row ~exp(-max) approximation.
// valid_upto bounds the logical positions that may be attended: rows of a
// resident chunk at positions >= valid_upto (rejected drafts, a previous
// turn's tokens above a rewind) are masked off. A decode step at position p
// passes p + 1: it attends the rows below p and its own row. The default
// leaves every resident row visible, as before.
void fill_slot_mask(uint16_t * dst, int64_t valid_upto = INT64_MAX) const {
constexpr uint16_t F16_ZERO = 0x0000, F16_NEG_INF = 0xFC00;
for (int i = 0; i < arena_tokens(); i++) dst[i] = F16_NEG_INF;
for (int c = 0; c < (int)chunks_.size(); c++) {
if (chunks_[c].block < 0) continue;
uint16_t * p = dst + (size_t)row_base_ + (size_t)chunks_[c].block * cfg_.chunk_tokens;
for (int i = 0; i < cfg_.chunk_tokens; i++)
if ((int64_t)c * cfg_.chunk_tokens + i < valid_upto) p[i] = F16_ZERO;
}
}
// Reselect to the recency set (sink + the newest chunks that fit), then drop the
// hook so later evictions are plain LRU. Returns the number of page events.
int reselect_recent() {
score_hook = [](int c) { return (float)c; };
const int events = reselect(0);
score_hook = nullptr;
return events;
}
// Lookahead reselect (FlashMemory τ-step): rebuild the resident set as
// the top-pool chunks by score_hook among ALL known chunks (resident or
// host-backed). Sinks and the trailing window are always kept. Returns
// the number of page events. Call between decode steps.
// tail_override >= 0 replaces cfg tail_window_chunks for this call only.
// Score ties keep already-resident chunks, so a tail covering every chunk is a no-op.
int reselect(int tail_override = -1) {
if (!score_hook) return 0;
const int tail = tail_override >= 0 ? tail_override : cfg_.tail_window_chunks;
struct Cand { int c; float s; bool res; };
std::vector<Cand> cands;
for (int c = 0; c < (int)chunks_.size(); c++) {
const ChunkState & st = chunks_[c];
if (st.block < 0 && !st.on_host) continue; // never materialized
const bool prot = c < cfg_.sink_chunks ||
c > cur_chunk_ - 1 - tail ||
is_pinned(c);
cands.push_back({c, prot ? 3.4e38f : score_hook(c), st.block >= 0});
}
std::sort(cands.begin(), cands.end(),
[](const Cand & a, const Cand & b) {
return a.s != b.s ? a.s > b.s : a.res > b.res; // ties keep resident chunks
});
std::vector<uint8_t> want(chunks_.size(), 0);
for (int i = 0; i < (int)cands.size() && i < n_blocks_; i++) want[cands[i].c] = 1;
int events = 0;
for (int c = 0; c < (int)chunks_.size(); c++) { // out first: frees blocks
if (!want[c] && chunks_[c].block >= 0) { page_out_(c, /*lazy_zero=*/true); events++; }
}
// The recalls are one batch on page_stream_ (the block each one reuses was freed on the same stream, so
// its page-out orders before its page-in), and no graph runs until the wait below: fencing each hand-out
// would be one host wait per chunk on HIP for nothing.
defer_fence_ = true;
for (int c = 0; c < (int)chunks_.size(); c++) {
if (want[c] && chunks_[c].block < 0 && chunks_[c].on_host) {
if (page_in(c)) events++;
}
}
defer_fence_ = false;
flush_unzeroed_(); // blocks left free by this reselect must read as zero
if (has_pending_page_in_) synchronize_paging();
return events;
}
// Zero the free blocks a lazy page-out left unzeroed.
void flush_unzeroed_() {
for (int b : free_blocks_)
if (!unzeroed_.empty() && unzeroed_[(size_t)b]) { unzeroed_[(size_t)b] = 0; zero_block(b); }
}
// Resident, and not sink, tail window or pinned: what an eviction may take.
bool evictable_(int c) const {
return c >= 0 && c < (int)chunks_.size() && chunks_[c].block >= 0 && c >= cfg_.sink_chunks &&
c <= cur_chunk_ - 1 - cfg_.tail_window_chunks && !is_pinned(c);
}
// Up to n eviction victims, worst first: evictable chunks ordered by score
// (score_hook, lowest first) or by oldest use (LRU fallback); ties go to
// the lower chunk id.
std::vector<int> lru_victims(int n) const {
std::vector<std::pair<std::pair<float, uint64_t>, int>> cand;
for (int c = 0; c < (int)chunks_.size(); c++) {
if (!evictable_(c)) continue;
cand.push_back({score_hook ? std::make_pair(score_hook(c), uint64_t(0))
: std::make_pair(0.f, chunks_[c].last_use), c});
}
std::stable_sort(cand.begin(), cand.end(), [](const auto & a, const auto & b) { return a.first < b.first; });
std::vector<int> out;
for (size_t i = 0; i < cand.size() && (int)i < n; i++) out.push_back(cand[i].second);
return out;
}
// Debug: resident chunk ids as "a-b,c" ranges, and a hash of the score
// ledger of chunks < upto (LUCE_KVFLASH_DEBUG_RESIDENT).
std::string debug_resident(int upto) const {
std::string out;
char buf[48];
for (int c = 0, n = (int)chunks_.size(); c < n;) {
if (chunks_[(size_t)c].block < 0) { c++; continue; }
int e = c;
while (e + 1 < n && chunks_[(size_t)e + 1].block >= 0) e++;
std::snprintf(buf, sizeof buf, "%s%d-%d", out.empty() ? "" : ",", c, e);
out += buf;
c = e + 1;
}
uint64_t h = kFnvBasis;
for (int c = 0; c < upto && c < (int)chunks_.size(); c++) {
uint32_t b; const float sc = chunks_[(size_t)c].score;
std::memcpy(&b, &sc, 4);
h = fnv1a_mix(h, b);
}
std::snprintf(buf, sizeof buf, " nchunks=%d ledger_hash=%016llx", (int)chunks_.size(), (unsigned long long)h);
return out + buf;
}
// Per-chunk relevance ledger (QK scorer): set before serialize() so the
// scores round-trip. -inf = never scored.
void set_chunk_score(int c, float s) {
if (c >= 0 && c < (int)chunks_.size()) chunks_[(size_t)c].score = s;
}
float chunk_score(int c) const {
return c >= 0 && c < (int)chunks_.size()
? chunks_[(size_t)c].score : -std::numeric_limits<float>::infinity();
}
// Snapshot chunks [0, max_chunks) (all when max_chunks < 0 or beyond
// n_chunks) into a flat blob; pair with deserialize(). Resident chunks are
// read from the pool tensors, paged-out chunks from their host backing
// (pinned host_data on async-DMA builds), never-written chunks are zero.
//
// Layout, magic "KVFLASH3" (u64); all integers and floats are written in host
// byte order, which the static_assert at the top of this file pins to little-endian:
// 9 x uint32 header: nc, chunk_tokens, n_head_kv, k_seg_bytes,
// v_seg_bytes, chunk_bytes, ggml_type(K), has_ledger(=1),
// ggml_type(V)
// nc x chunk_bytes KV bytes, segment order of copy_chunk()
// nc x 8 bytes ledger: u8 was_resident, u8 materialized, 2 pad, f32 score
// (a hole left by a failed allocation is not materialized)
// pool layout: u32 n_blocks, u32 n_free, u64 use clock,
// nc x (i32 block or -1, u32 0, u64 LRU rank, 0 if not resident),
// n_free x i32 free blocks in free-list order (back = next)
// The pool layout lets deserialize() put every chunk back in its own block
// with its LRU stamp, so a restored pager is the pager that was saved:
// attention then reads the same slots in the same order as a cold prefill,
// and later evictions pick the same victims. Chunks past max_chunks give
// their blocks to the free list. Not serialized: pins.
//
// KVFLASH2 is the same blob without the pool layout: blob_header() +
// read_chunk(0..nc) + ledger_blob(), streamed by serialize_to(). A writer
// that keeps chunks apart (a slot bundle rewrites only the chunks a turn
// changed) assembles it; deserialize() takes both and restores a KVFLASH2
// blob in identity block order.
std::vector<uint8_t> serialize(int max_chunks = -1) const {
synchronize_page_stream_(); // queued D2H must land in host_data first
const int nc = serialized_chunks_(max_chunks);
const size_t kv_bytes = (size_t)nc * chunk_bytes_;
std::vector<int32_t> free_list(free_blocks_.begin(), free_blocks_.end());
// A block awaiting its page-out record holds no resident chunk: free in the layout.
for (const auto & pf : pending_free_) free_list.insert(free_list.begin(), pf.first);
for (int c = (int)chunks_.size() - 1; c >= nc; --c) // dropped tail: handed out last
if (chunks_[(size_t)c].block >= 0) free_list.insert(free_list.begin(), chunks_[(size_t)c].block);
const size_t ledger_end = kBlobHdr + kv_bytes + (size_t)nc * kLedgerEntry;
// LRU stamps as dense ranks among the resident chunks (0 elsewhere):
// eviction only compares stamps and new ones always exceed the clock,
// so ranks behave exactly like the raw clock values, and two pagers
// that would evict alike serialize alike.
std::vector<uint64_t> stamps;
for (int c = 0; c < nc; ++c)
if (chunks_[(size_t)c].block >= 0) stamps.push_back(chunks_[(size_t)c].last_use);
std::sort(stamps.begin(), stamps.end());
stamps.erase(std::unique(stamps.begin(), stamps.end()), stamps.end());
auto rank_of = [&](uint64_t u) {
return (uint64_t)(std::lower_bound(stamps.begin(), stamps.end(), u) - stamps.begin()) + 1;
};
std::vector<uint8_t> out(ledger_end + kPoolHdr + (size_t)nc * kPoolEntry +
free_list.size() * sizeof(int32_t), 0);
const std::vector<uint8_t> head = blob_header(max_chunks);
std::memcpy(out.data(), head.data(), kBlobHdr);
std::memcpy(out.data(), &kBlobMagic3, 8); // the pool layout below makes it KVFLASH3
for (int c = 0; c < nc; ++c) read_chunk(c, out.data() + kBlobHdr + (size_t)c * chunk_bytes_);
const std::vector<uint8_t> ledger = ledger_blob(max_chunks);
std::memcpy(out.data() + kBlobHdr + kv_bytes, ledger.data(), ledger.size());
for (int c = 0; c < nc; ++c) {
const ChunkState & st = chunks_[(size_t)c];
uint8_t * pe = out.data() + ledger_end + kPoolHdr + (size_t)c * kPoolEntry;
const int32_t blk = st.block;
const uint64_t rank = st.block >= 0 ? rank_of(st.last_use) : 0;
std::memcpy(pe, &blk, 4);
std::memcpy(pe + 8, &rank, 8);
}
uint8_t * ph = out.data() + ledger_end;
const uint32_t pool_hdr[2] = {(uint32_t)n_blocks_, (uint32_t)free_list.size()};
const uint64_t clock = stamps.size();
std::memcpy(ph, pool_hdr, 8);
std::memcpy(ph + 8, &clock, 8);
if (!free_list.empty())
std::memcpy(ph + kPoolHdr + (size_t)nc * kPoolEntry, free_list.data(),
free_list.size() * sizeof(int32_t));
return out;
}
// KVFLASH2 streamed through sink(bytes, n) -> bool, one chunk of staging
// instead of the whole blob (a disk bundle writes it straight to its file).
// False when the sink refuses.
template <class Sink>
bool serialize_to(Sink && sink, int max_chunks = -1) const {
synchronize_page_stream_(); // queued D2H must land in host_data first
const int nc = serialized_chunks_(max_chunks);
const std::vector<uint8_t> head = blob_header(max_chunks);
if (!sink(head.data(), head.size())) return false;
std::vector<uint8_t> chunk(chunk_bytes_);
for (int c = 0; c < nc; ++c) {
read_chunk(c, chunk.data());
if (!sink(chunk.data(), chunk_bytes_)) return false;
}