Repository navigation
Expand file tree
/
Copy pathmain.zig
More file actions
9879 lines (8921 loc) · 420 KB
/
Copy pathmain.zig
File metadata and controls
9879 lines (8921 loc) · 420 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
const std = @import("std");
const net = std.Io.net;
const posix = std.posix;
const Allocator = std.mem.Allocator;
const builtin = @import("builtin");
const build_options = @import("build_options");
const acl = @import("acl.zig");
pub var app_io: std.Io = undefined;
const MAX_HEADER_SIZE = 8 * 1024;
const MAX_BODY_SIZE = 5 * 1024 * 1024 * 1024;
const MAX_KEY_LENGTH = 1024;
const MAX_BUCKET_LENGTH = 63;
const MAX_CONNECTIONS = 1024;
// Distributed mode constants
const CHUNK_SIZE = 4 * 1024 * 1024; // 4MB chunks for large files
const MAX_PEERS = 100;
const GOSSIP_INTERVAL_MS = 30_000;
const REPLICATION_TARGET = 3;
const TOMBSTONE_TTL_SECS = 24 * 60 * 60; // 24 hours before tombstone cleanup
const INLINE_THRESHOLD = 4 * 1024; // Objects <= 4KB stored inline in metadata
const GC_GRACE_PERIOD_SECS = 10 * 60; // 10 min delay before deleting unreferenced blocks
const QUORUM_SIZE = 2; // Need 2 matching responses for quorum reads
const MAX_BROADCAST_PEERS = 64; // Max peers a metadata/announce broadcast reaches
const MAX_META_RESPONSE = 16 * 1024; // Meta entries are small: header + inline data
const MAX_INDEX_SYNC_SIZE = 256 * 1024 * 1024; // Cap on a full index dump during join sync
const PEER_IO_TIMEOUT_SECS = 5; // Socket timeout for peer-to-peer requests
const ERROR_403 = "HTTP/1.1 403 Forbidden\r\nContent-Length: 6\r\nConnection: keep-alive\r\n\r\nDenied";
const ERROR_431 = "HTTP/1.1 431 Request Header Fields Too Large\r\nContent-Length: 0\r\nConnection: close\r\n\r\n";
const ERROR_400_ENTITY_TOO_LARGE = "HTTP/1.1 400 Bad Request\r\nContent-Length: 0\r\nConnection: close\r\n\r\n";
// Crash-safety knob. Default ON: PUT/CopyObject/multipart-complete fsync file
// contents (and best-effort parent dirs) so an acknowledged write survives a
// crash or power loss — the "SQLite for objects" claim requires it. Pass
// --fast (benchmark mode) or --no-fsync to restore the no-fsync fast path and
// the original benchmark numbers.
var enable_fsync: bool = true;
fn fsyncFile(file: std.Io.File) void {
if (!enable_fsync) return;
file.sync(app_io) catch {};
}
fn fsyncParentDir(path: []const u8) void {
if (!enable_fsync) return;
if (std.fs.path.dirname(path)) |dir| {
var d = std.Io.Dir.cwd().openDir(app_io, dir, .{}) catch return;
defer d.close(app_io);
// fsync the dir fd so the rename entry is durable. Best-effort:
// ignore failures (filesystems that reject dir fsync). Raw syscall
// on Linux to keep the static musl build libc-free.
if (builtin.os.tag == .linux) {
_ = std.os.linux.fsync(d.handle);
} else {
_ = std.c.fsync(d.handle);
}
}
}
// Lightweight process metrics, mutated only on the event-loop thread so no
// atomics are needed (the background PushWorker never touches these).
const Metrics = struct {
start_time_secs: i64 = 0,
requests: u64 = 0,
errors_4xx: u64 = 0,
errors_5xx: u64 = 0,
put_bytes: u64 = 0,
get_bytes: u64 = 0,
};
var metrics: Metrics = .{};
/// Format a Unix timestamp (seconds) as an HTTP date (RFC 7231).
/// Returns a 29-byte string like "Mon, 02 Jan 2006 15:04:05 GMT".
/// When using with Response.setHeader, the returned slice must outlive
/// the response — use allocHttpDate to get a heap-allocated copy.
pub fn formatHttpDate(buf: *[29]u8, timestamp: i64) void {
const secs: u64 = if (timestamp > 0) @intCast(timestamp) else 0;
const es = std.time.epoch.EpochSeconds{ .secs = secs };
const day = es.getEpochDay();
const yd = day.calculateYearDay();
const md = yd.calculateMonthDay();
const ds = es.getDaySeconds();
const dow = @mod(@as(i32, @intCast(day.day)) + 4, 7); // epoch was Thursday=4
const day_names = [7]*const [3]u8{ "Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat" };
const month_names = [12]*const [3]u8{ "Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec" };
const mon_idx = @intFromEnum(md.month) - 1;
_ = std.fmt.bufPrint(buf, "{s}, {d:0>2} {s} {d:0>4} {d:0>2}:{d:0>2}:{d:0>2} GMT", .{
day_names[@intCast(dow)],
md.day_index + 1,
month_names[mon_idx],
yd.year,
ds.getHoursIntoDay(),
ds.getMinutesIntoHour(),
ds.getSecondsIntoMinute(),
}) catch unreachable;
}
/// Format a Unix timestamp (seconds) as ISO 8601 for S3 XML responses.
/// Returns a 20-byte string like "2006-01-02T15:04:05Z".
pub fn formatIso8601(buf: *[20]u8, timestamp: i64) void {
const secs: u64 = if (timestamp > 0) @intCast(timestamp) else 0;
const es = std.time.epoch.EpochSeconds{ .secs = secs };
const day = es.getEpochDay();
const yd = day.calculateYearDay();
const md = yd.calculateMonthDay();
const ds = es.getDaySeconds();
_ = std.fmt.bufPrint(buf, "{d:0>4}-{d:0>2}-{d:0>2}T{d:0>2}:{d:0>2}:{d:0>2}Z", .{
yd.year,
@intFromEnum(md.month),
md.day_index + 1,
ds.getHoursIntoDay(),
ds.getMinutesIntoHour(),
ds.getSecondsIntoMinute(),
}) catch unreachable;
}
/// Result of decoding AWS chunked transfer encoding: the payload, plus the raw
/// trailer block that follows the terminating 0-size chunk (empty when absent).
pub const ChunkedBody = struct {
data: []const u8,
trailers: []const u8,
};
/// Decode AWS chunked transfer encoding.
/// Format: <hex-size>;chunk-signature=...\r\n<data>\r\n repeated, terminated by 0-size chunk.
/// The -TRAILER variants append `x-amz-checksum-*: <base64>` lines after that
/// final chunk; they are returned rather than discarded so the checksum can be
/// verified against the payload.
pub fn decodeAwsChunkedFull(allocator: Allocator, body: []const u8) !ChunkedBody {
var result: std.ArrayListUnmanaged(u8) = .empty;
errdefer result.deinit(allocator);
var trailers: []const u8 = "";
var pos: usize = 0;
while (pos < body.len) {
// Find the end of the chunk header line (terminated by \r\n)
const line_end = std.mem.indexOfPos(u8, body, pos, "\r\n") orelse break;
const chunk_header = body[pos..line_end];
// Parse hex chunk size (before the first ';')
const size_end = std.mem.indexOf(u8, chunk_header, ";") orelse chunk_header.len;
const hex_str = chunk_header[0..size_end];
const chunk_size = std.fmt.parseInt(usize, hex_str, 16) catch break;
if (chunk_size == 0) {
// Everything past the terminating chunk's CRLF is the trailer block.
trailers = body[@min(line_end + 2, body.len)..];
break;
}
// Data starts after \r\n
const data_start = line_end + 2;
if (data_start + chunk_size > body.len) break;
try result.appendSlice(allocator, body[data_start .. data_start + chunk_size]);
// Skip past data + \r\n
pos = data_start + chunk_size + 2;
}
return .{ .data = try result.toOwnedSlice(allocator), .trailers = trailers };
}
/// Payload-only wrapper for callers with no interest in trailers.
pub fn decodeAwsChunked(allocator: Allocator, body: []const u8) ![]const u8 {
const decoded = try decodeAwsChunkedFull(allocator, body);
return decoded.data;
}
// ============================================================================
// PAYLOAD CHECKSUMS (x-amz-checksum-*, header or trailer form)
// ============================================================================
/// CRC-64/NVME is absent from Zig's CRC catalog, so build it from the generic
/// implementation. Check value for "123456789" is 0xae8b14860a799888.
const Crc64Nvme = std.hash.crc.Crc(u64, .{
.polynomial = 0xad93d23594c93659,
.initial = 0xffffffffffffffff,
.reflect_input = true,
.reflect_output = true,
.xor_output = 0xffffffffffffffff,
});
pub const ChecksumAlgo = enum {
crc32,
crc32c,
crc64nvme,
sha1,
sha256,
/// Map a full header name ("x-amz-checksum-crc32c") to its algorithm.
pub fn fromHeaderName(name: []const u8) ?ChecksumAlgo {
const prefix = "x-amz-checksum-";
if (!std.mem.startsWith(u8, name, prefix)) return null;
const suffix = name[prefix.len..];
if (std.mem.eql(u8, suffix, "crc32")) return .crc32;
if (std.mem.eql(u8, suffix, "crc32c")) return .crc32c;
if (std.mem.eql(u8, suffix, "crc64nvme")) return .crc64nvme;
if (std.mem.eql(u8, suffix, "sha1")) return .sha1;
if (std.mem.eql(u8, suffix, "sha256")) return .sha256;
return null;
}
};
/// Compute the base64 digest S3 carries in x-amz-checksum-<algo>.
pub fn computeChecksum(allocator: Allocator, algo: ChecksumAlgo, data: []const u8) ![]const u8 {
var digest: [32]u8 = undefined;
const raw: []const u8 = switch (algo) {
.crc32 => blk: {
std.mem.writeInt(u32, digest[0..4], std.hash.crc.Crc32IsoHdlc.hash(data), .big);
break :blk digest[0..4];
},
.crc32c => blk: {
std.mem.writeInt(u32, digest[0..4], std.hash.crc.Crc32Iscsi.hash(data), .big);
break :blk digest[0..4];
},
.crc64nvme => blk: {
std.mem.writeInt(u64, digest[0..8], Crc64Nvme.hash(data), .big);
break :blk digest[0..8];
},
.sha1 => blk: {
std.crypto.hash.Sha1.hash(data, digest[0..20], .{});
break :blk digest[0..20];
},
.sha256 => blk: {
std.crypto.hash.sha2.Sha256.hash(data, digest[0..32], .{});
break :blk digest[0..32];
},
};
const encoder = std.base64.standard.Encoder;
const out = try allocator.alloc(u8, encoder.calcSize(raw.len));
return encoder.encode(out, raw);
}
/// Verify every x-amz-checksum-* the client supplied against the received
/// payload. Returns the name of the first header that disagrees, or null when
/// all of them match (including when none were sent).
///
/// Composite values ("<base64>-<partcount>", returned by CompleteMultipartUpload)
/// describe an assembled object rather than this request body, so they are
/// skipped.
pub fn mismatchedChecksum(allocator: Allocator, req: *const Request) !?[]const u8 {
var it = req.headers.iterator();
while (it.next()) |entry| {
const algo = ChecksumAlgo.fromHeaderName(entry.key_ptr.*) orelse continue;
const want = std.mem.trim(u8, entry.value_ptr.*, " \t");
if (want.len == 0) continue;
if (std.mem.indexOfScalar(u8, want, '-') != null) continue;
const got = try computeChecksum(allocator, algo, req.body);
if (!std.mem.eql(u8, got, want)) return entry.key_ptr.*;
}
return null;
}
/// Heap-allocate an RFC 7231 date string suitable for Response.setHeader.
fn allocHttpDate(allocator: Allocator, timestamp: i64) ![]const u8 {
var buf: [29]u8 = undefined;
formatHttpDate(&buf, timestamp);
return allocator.dupe(u8, &buf);
}
// ============================================================================
// DISTRIBUTED TYPES
// ============================================================================
const ContentHash = [20]u8; // 160-bit truncated BLAKE3
const NodeId = [20]u8; // 160-bit node identifier
/// Format bytes as lowercase hex string
fn bytesToHex(bytes: []const u8, out: []u8) void {
const hex_chars = "0123456789abcdef";
for (bytes, 0..) |b, i| {
out[i * 2] = hex_chars[b >> 4];
out[i * 2 + 1] = hex_chars[b & 0x0f];
}
}
/// Content-Addressed Store - stores objects by their hash
const CAS = struct {
data_dir: []const u8,
const Blake3 = std.crypto.hash.Blake3;
/// Store data and return its content hash (deduplicates automatically)
pub fn store(self: *const CAS, allocator: Allocator, data: []const u8) !ContentHash {
var hasher = Blake3.init(.{});
hasher.update(data);
var full_hash: [32]u8 = undefined;
hasher.final(&full_hash);
const hash: ContentHash = full_hash[0..20].*;
const path = try self.hashToPath(allocator, hash);
defer allocator.free(path);
// Check if already exists (deduplication)
if (std.Io.Dir.cwd().access(app_io, path, .{})) |_| {
return hash;
} else |_| {}
// Write the blob atomically (temp file + rename) so a concurrent reader
// never sees a half-written blob under a content hash.
var af = try std.Io.Dir.cwd().createFileAtomic(app_io, path, .{
.make_path = true,
.replace = true,
});
defer af.deinit(app_io);
try af.file.writeStreamingAll(app_io, data);
try af.replace(app_io);
return hash;
}
/// Retrieve data by content hash
pub fn retrieve(self: *const CAS, allocator: Allocator, hash: ContentHash) ![]const u8 {
const path = try self.hashToPath(allocator, hash);
defer allocator.free(path);
var file = std.Io.Dir.cwd().openFile(app_io, path, .{}) catch return error.NotFound;
defer file.close(app_io);
const stat = try file.stat(app_io);
const data = try allocator.alloc(u8, stat.size);
const bytes_read = try file.readPositionalAll(app_io, data, 0);
return data[0..bytes_read];
}
/// Check if content exists locally
pub fn exists(self: *const CAS, allocator: Allocator, hash: ContentHash) bool {
const path = self.hashToPath(allocator, hash) catch return false;
defer allocator.free(path);
return if (std.Io.Dir.cwd().access(app_io, path, .{})) |_| true else |_| false;
}
/// Convert hash to filesystem path: .cas/xx/xxxx....blob
fn hashToPath(self: *const CAS, allocator: Allocator, hash: ContentHash) ![]const u8 {
var hex: [40]u8 = undefined;
bytesToHex(&hash, &hex);
return std.fs.path.join(allocator, &.{ self.data_dir, ".cas", hex[0..2], hex[2..] ++ ".blob" });
}
/// Compute hash without storing
pub fn computeHash(data: []const u8) ContentHash {
var hasher = Blake3.init(.{});
hasher.update(data);
var full_hash: [32]u8 = undefined;
hasher.final(&full_hash);
return full_hash[0..20].*;
}
/// Garbage collect unreferenced blocks
/// Scans metadata index to build reference set, then removes orphaned CAS blobs
pub fn garbageCollect(self: *const CAS, allocator: Allocator, meta_index: *const MetaIndex) !struct { scanned: usize, deleted: usize } {
var referenced = std.AutoHashMap(ContentHash, void).init(allocator);
defer referenced.deinit();
// Phase 1: Collect all referenced hashes from metadata index
const index_path = try std.fs.path.join(allocator, &.{ meta_index.data_dir, ".index" });
defer allocator.free(index_path);
var index_dir = std.Io.Dir.cwd().openDir(app_io, index_path, .{ .iterate = true }) catch {
return .{ .scanned = 0, .deleted = 0 };
};
defer index_dir.close(app_io);
var bucket_iter = index_dir.iterate();
while (try bucket_iter.next(app_io)) |bucket_entry| {
if (bucket_entry.kind == .directory) {
try self.collectReferencedHashes(allocator, meta_index, bucket_entry.name, &referenced);
}
}
// Phase 2: Scan CAS directory and delete unreferenced blocks
const cas_path = try std.fs.path.join(allocator, &.{ self.data_dir, ".cas" });
defer allocator.free(cas_path);
var cas_dir = std.Io.Dir.cwd().openDir(app_io, cas_path, .{ .iterate = true }) catch {
return .{ .scanned = 0, .deleted = 0 };
};
defer cas_dir.close(app_io);
var scanned: usize = 0;
var deleted: usize = 0;
const now = std.Io.Clock.real.now(app_io).toSeconds();
var prefix_iter = cas_dir.iterate();
while (try prefix_iter.next(app_io)) |prefix_entry| {
if (prefix_entry.kind == .directory and prefix_entry.name.len == 2) {
const prefix_path = try std.fs.path.join(allocator, &.{ cas_path, prefix_entry.name });
defer allocator.free(prefix_path);
var blob_dir = std.Io.Dir.cwd().openDir(app_io, prefix_path, .{ .iterate = true }) catch continue;
defer blob_dir.close(app_io);
var blob_iter = blob_dir.iterate();
while (try blob_iter.next(app_io)) |blob_entry| {
if (blob_entry.kind == .file and std.mem.endsWith(u8, blob_entry.name, ".blob")) {
scanned += 1;
// Reconstruct hash from path: prefix + name (without .blob)
const name_without_ext = blob_entry.name[0 .. blob_entry.name.len - 5];
if (name_without_ext.len != 38) continue; // 40 - 2 prefix = 38
var hex: [40]u8 = undefined;
@memcpy(hex[0..2], prefix_entry.name);
@memcpy(hex[2..], name_without_ext);
var hash: ContentHash = undefined;
_ = std.fmt.hexToBytes(&hash, &hex) catch continue;
// Check if referenced
if (!referenced.contains(hash)) {
// Check grace period using mtime
const blob_path = try std.fs.path.join(allocator, &.{ prefix_path, blob_entry.name });
defer allocator.free(blob_path);
const file = std.Io.Dir.cwd().openFile(app_io, blob_path, .{}) catch continue;
const stat = file.stat(app_io) catch {
file.close(app_io);
continue;
};
file.close(app_io);
const mtime_secs = stat.mtime.toSeconds();
const age = now - mtime_secs;
if (age > GC_GRACE_PERIOD_SECS) {
std.Io.Dir.cwd().deleteFile(app_io, blob_path) catch continue;
deleted += 1;
}
}
}
}
}
}
return .{ .scanned = scanned, .deleted = deleted };
}
fn collectReferencedHashes(self: *const CAS, allocator: Allocator, meta_index: *const MetaIndex, bucket: []const u8, referenced: *std.AutoHashMap(ContentHash, void)) !void {
_ = self;
const bucket_path = try std.fs.path.join(allocator, &.{ meta_index.data_dir, ".index", bucket });
defer allocator.free(bucket_path);
try collectHashesFromDir(allocator, bucket_path, bucket, "", meta_index, referenced);
}
};
/// Recursively collect hashes from metadata directory for GC reference counting
fn collectHashesFromDir(allocator: Allocator, dir_path: []const u8, bucket: []const u8, prefix: []const u8, meta_index: *const MetaIndex, referenced: *std.AutoHashMap(ContentHash, void)) !void {
var dir = std.Io.Dir.cwd().openDir(app_io, dir_path, .{ .iterate = true }) catch return;
defer dir.close(app_io);
var iter = dir.iterate();
while (try iter.next(app_io)) |entry| {
const full_name = if (prefix.len > 0)
try std.fmt.allocPrint(allocator, "{s}/{s}", .{ prefix, entry.name })
else
try allocator.dupe(u8, entry.name);
defer allocator.free(full_name);
if (entry.kind == .directory) {
const subdir = try std.fs.path.join(allocator, &.{ dir_path, entry.name });
defer allocator.free(subdir);
try collectHashesFromDir(allocator, subdir, bucket, full_name, meta_index, referenced);
} else if (std.mem.endsWith(u8, entry.name, ".meta")) {
// Read hash from metadata file (even tombstones - they still reference content)
const key = full_name[0 .. full_name.len - 5]; // Remove .meta
const path = try meta_index.metaPath(allocator, bucket, key);
defer allocator.free(path);
var file = std.Io.Dir.cwd().openFile(app_io, path, .{}) catch continue;
defer file.close(app_io);
var buf: [128]u8 = undefined;
const bytes_read = file.readPositionalAll(app_io, &buf, 0) catch continue;
const content = buf[0..bytes_read];
var lines = std.mem.splitScalar(u8, content, '\n');
const hash_hex = lines.next() orelse continue;
if (hash_hex.len != 40) continue;
var hash: ContentHash = undefined;
_ = std.fmt.hexToBytes(&hash, hash_hex) catch continue;
try referenced.put(hash, {});
}
}
}
/// Metadata Index - maps S3 paths to content hashes
/// Supports tombstones for delete propagation and inline storage for small objects
const MetaIndex = struct {
data_dir: []const u8,
const ObjectMeta = struct {
hash: ContentHash,
size: u64,
created: i64,
deleted: i64, // 0 = not deleted, >0 = tombstone timestamp
inline_data: ?[]const u8, // For small objects (<= INLINE_THRESHOLD)
};
/// Store metadata for an S3 object (with optional inline data for small objects)
pub fn put(self: *const MetaIndex, allocator: Allocator, bucket: []const u8, key: []const u8, hash: ContentHash, size: u64) !void {
try self.putWithData(allocator, bucket, key, hash, size, null);
}
/// Store metadata with optional inline data
pub fn putWithData(self: *const MetaIndex, allocator: Allocator, bucket: []const u8, key: []const u8, hash: ContentHash, size: u64, inline_data: ?[]const u8) !void {
const path = try self.metaPath(allocator, bucket, key);
defer allocator.free(path);
// Write the index entry atomically (temp file + rename) so a concurrent
// reader never sees a half-written .meta file.
var af = try std.Io.Dir.cwd().createFileAtomic(app_io, path, .{
.make_path = true,
.replace = true,
});
defer af.deinit(app_io);
// Format: hex_hash\nsize\ncreated\ndeleted\n[inline_data_base64]
var hash_hex: [40]u8 = undefined;
bytesToHex(&hash, &hash_hex);
const created = std.Io.Clock.real.now(app_io).toSeconds();
var buf: [128]u8 = undefined;
const header = std.fmt.bufPrint(&buf, "{s}\n{d}\n{d}\n0\n", .{ hash_hex, size, created }) catch unreachable;
try af.file.writeStreamingAll(app_io, header);
// Write inline data if provided
if (inline_data) |data| {
try af.file.writeStreamingAll(app_io, data);
}
try af.replace(app_io);
}
/// Get metadata for an S3 object (returns null for tombstones)
pub fn get(self: *const MetaIndex, allocator: Allocator, bucket: []const u8, key: []const u8) !?struct { hash: ContentHash, size: u64 } {
const meta = try self.getFull(allocator, bucket, key) orelse return null;
if (meta.inline_data) |data| allocator.free(data);
return .{ .hash = meta.hash, .size = meta.size };
}
/// Get full metadata including inline data
pub fn getFull(self: *const MetaIndex, allocator: Allocator, bucket: []const u8, key: []const u8) !?ObjectMeta {
const path = try self.metaPath(allocator, bucket, key);
defer allocator.free(path);
var file = std.Io.Dir.cwd().openFile(app_io, path, .{}) catch return null;
defer file.close(app_io);
const stat = try file.stat(app_io);
const content = try allocator.alloc(u8, stat.size);
defer allocator.free(content);
_ = try file.readPositionalAll(app_io, content, 0);
// Parse: hex_hash\nsize\ncreated\ndeleted\n[inline_data]
var lines = std.mem.splitScalar(u8, content, '\n');
const hash_hex = lines.next() orelse return null;
const size_str = lines.next() orelse return null;
const created_str = lines.next() orelse return null;
const deleted_str = lines.next() orelse return null;
if (hash_hex.len != 40) return null;
var hash: ContentHash = undefined;
_ = std.fmt.hexToBytes(&hash, hash_hex) catch return null;
const size = std.fmt.parseInt(u64, size_str, 10) catch return null;
const created = std.fmt.parseInt(i64, created_str, 10) catch return null;
const deleted = std.fmt.parseInt(i64, deleted_str, 10) catch 0;
// Check tombstone - return null if deleted
if (deleted > 0) return null;
// Check for inline data after the 4th newline
var header_end: usize = 0;
var newline_count: usize = 0;
for (content, 0..) |c, i| {
if (c == '\n') {
newline_count += 1;
if (newline_count == 4) {
header_end = i + 1;
break;
}
}
}
var inline_data: ?[]const u8 = null;
if (header_end < content.len) {
inline_data = try allocator.dupe(u8, content[header_end..]);
}
return .{
.hash = hash,
.size = size,
.created = created,
.deleted = 0,
.inline_data = inline_data,
};
}
/// Read the raw meta file content (including tombstones) for replication
pub fn readRaw(self: *const MetaIndex, allocator: Allocator, bucket: []const u8, key: []const u8) !?[]u8 {
const path = try self.metaPath(allocator, bucket, key);
defer allocator.free(path);
var file = std.Io.Dir.cwd().openFile(app_io, path, .{}) catch return null;
defer file.close(app_io);
const stat = try file.stat(app_io);
const content = try allocator.alloc(u8, stat.size);
errdefer allocator.free(content);
_ = try file.readPositionalAll(app_io, content, 0);
return content;
}
/// Write raw meta file content verbatim, preserving origin timestamps
pub fn writeRaw(self: *const MetaIndex, allocator: Allocator, bucket: []const u8, key: []const u8, content: []const u8) !void {
const path = try self.metaPath(allocator, bucket, key);
defer allocator.free(path);
if (std.fs.path.dirname(path)) |dir| {
std.Io.Dir.cwd().createDirPath(app_io, dir) catch {};
}
var file = try std.Io.Dir.cwd().createFile(app_io, path, .{});
defer file.close(app_io);
try file.writeStreamingAll(app_io, content);
}
/// Delete metadata by writing a tombstone (prevents resurrection during sync)
pub fn delete(self: *const MetaIndex, allocator: Allocator, bucket: []const u8, key: []const u8) void {
self.writeTombstone(allocator, bucket, key) catch {
// Fallback: just delete the file if tombstone fails
const path = self.metaPath(allocator, bucket, key) catch return;
defer allocator.free(path);
std.Io.Dir.cwd().deleteFile(app_io, path) catch {};
};
}
/// Write tombstone marker (preserves hash for GC reference counting)
fn writeTombstone(self: *const MetaIndex, allocator: Allocator, bucket: []const u8, key: []const u8) !void {
const path = try self.metaPath(allocator, bucket, key);
defer allocator.free(path);
// Read existing metadata to preserve hash
var file = std.Io.Dir.cwd().openFile(app_io, path, .{}) catch return;
var buf: [128]u8 = undefined;
const bytes_read = file.readPositionalAll(app_io, &buf, 0) catch return;
file.close(app_io);
const content = buf[0..bytes_read];
var lines = std.mem.splitScalar(u8, content, '\n');
const hash_hex = lines.next() orelse return;
const size_str = lines.next() orelse return;
const created_str = lines.next() orelse return;
// Rewrite with tombstone timestamp
var out_file = try std.Io.Dir.cwd().createFile(app_io, path, .{});
defer out_file.close(app_io);
const deleted = std.Io.Clock.real.now(app_io).toSeconds();
var out_buf: [128]u8 = undefined;
const new_content = std.fmt.bufPrint(&out_buf, "{s}\n{s}\n{s}\n{d}\n", .{ hash_hex, size_str, created_str, deleted }) catch unreachable;
try out_file.writeStreamingAll(app_io, new_content);
}
/// Check if entry is a tombstone (for cleanup)
pub fn isTombstone(self: *const MetaIndex, allocator: Allocator, bucket: []const u8, key: []const u8) bool {
const path = self.metaPath(allocator, bucket, key) catch return false;
defer allocator.free(path);
var file = std.Io.Dir.cwd().openFile(app_io, path, .{}) catch return false;
defer file.close(app_io);
var buf: [128]u8 = undefined;
const bytes_read = file.readPositionalAll(app_io, &buf, 0) catch return false;
const content = buf[0..bytes_read];
var lines = std.mem.splitScalar(u8, content, '\n');
_ = lines.next(); // hash
_ = lines.next(); // size
_ = lines.next(); // created
const deleted_str = lines.next() orelse return false;
const deleted = std.fmt.parseInt(i64, deleted_str, 10) catch return false;
return deleted > 0;
}
/// Cleanup expired tombstones
pub fn cleanupTombstones(self: *const MetaIndex, allocator: Allocator) !void {
const now = std.Io.Clock.real.now(app_io).toSeconds();
const index_path = try std.fs.path.join(allocator, &.{ self.data_dir, ".index" });
defer allocator.free(index_path);
var dir = std.Io.Dir.cwd().openDir(app_io, index_path, .{ .iterate = true }) catch return;
defer dir.close(app_io);
var iter = dir.iterate();
while (try iter.next(app_io)) |entry| {
if (entry.kind == .directory) {
try self.cleanupBucketTombstones(allocator, entry.name, now);
}
}
}
fn cleanupBucketTombstones(self: *const MetaIndex, allocator: Allocator, bucket: []const u8, now: i64) !void {
const bucket_path = try std.fs.path.join(allocator, &.{ self.data_dir, ".index", bucket });
defer allocator.free(bucket_path);
self.cleanupDirTombstones(allocator, bucket_path, bucket, "", now) catch {};
}
fn cleanupDirTombstones(self: *const MetaIndex, allocator: Allocator, dir_path: []const u8, bucket: []const u8, prefix: []const u8, now: i64) !void {
var dir = std.Io.Dir.cwd().openDir(app_io, dir_path, .{ .iterate = true }) catch return;
defer dir.close(app_io);
var iter = dir.iterate();
while (try iter.next(app_io)) |entry| {
const full_name = if (prefix.len > 0)
try std.fmt.allocPrint(allocator, "{s}/{s}", .{ prefix, entry.name })
else
try allocator.dupe(u8, entry.name);
defer allocator.free(full_name);
if (entry.kind == .directory) {
const subdir = try std.fs.path.join(allocator, &.{ dir_path, entry.name });
defer allocator.free(subdir);
try self.cleanupDirTombstones(allocator, subdir, bucket, full_name, now);
} else if (std.mem.endsWith(u8, entry.name, ".meta")) {
// Check if expired tombstone
const key = full_name[0 .. full_name.len - 5]; // Remove .meta
if (self.getTombstoneAge(allocator, bucket, key, now)) |age| {
if (age > TOMBSTONE_TTL_SECS) {
const path = try self.metaPath(allocator, bucket, key);
defer allocator.free(path);
std.Io.Dir.cwd().deleteFile(app_io, path) catch {};
}
}
}
}
}
fn getTombstoneAge(self: *const MetaIndex, allocator: Allocator, bucket: []const u8, key: []const u8, now: i64) ?i64 {
const path = self.metaPath(allocator, bucket, key) catch return null;
defer allocator.free(path);
var file = std.Io.Dir.cwd().openFile(app_io, path, .{}) catch return null;
defer file.close(app_io);
var buf: [128]u8 = undefined;
const bytes_read = file.readPositionalAll(app_io, &buf, 0) catch return null;
const content = buf[0..bytes_read];
var lines = std.mem.splitScalar(u8, content, '\n');
_ = lines.next(); // hash
_ = lines.next(); // size
_ = lines.next(); // created
const deleted_str = lines.next() orelse return null;
const deleted = std.fmt.parseInt(i64, deleted_str, 10) catch return null;
if (deleted == 0) return null;
return now - deleted;
}
fn metaPath(self: *const MetaIndex, allocator: Allocator, bucket: []const u8, key: []const u8) ![]const u8 {
const key_with_ext = try std.fmt.allocPrint(allocator, "{s}.meta", .{key});
defer allocator.free(key_with_ext);
const path = try std.fs.path.join(allocator, &.{ self.data_dir, ".index", bucket, key_with_ext });
// Same filesystem guards as S3Context.objectPath (NAME_MAX per
// component, PATH_MAX total): an un-storable key must surface as a
// client error, not a 500. Note key_with_ext includes the ".meta"
// suffix, so its components are the ones that land on disk.
var component_itr = std.mem.splitScalar(u8, key_with_ext, '/');
while (component_itr.next()) |component| {
if (component.len >= std.posix.NAME_MAX) {
allocator.free(path);
return error.NameTooLong;
}
}
if (path.len >= std.posix.PATH_MAX) {
allocator.free(path);
return error.PathTooLong;
}
return path;
}
};
// ============================================================================
// DISTRIBUTED OBJECT ATTRIBUTES
// ============================================================================
// Content-Type / user metadata / checksums for distributed objects live in
// `.index/<bucket>/<key>.attrs` (same `name: value` text format as the
// standalone sidecar). They replicate alongside metadata: pushed synchronously
// on write (`POST /_zs3/attrs`), pulled on read misses (`POST /_zs3/attrs_get`),
// and included in join-time index dumps (frames prefixed with a kind line).
fn distAttrsPath(allocator: Allocator, data_dir: []const u8, bucket: []const u8, key: []const u8) ![]const u8 {
const key_with_ext = try std.fmt.allocPrint(allocator, "{s}.attrs", .{key});
defer allocator.free(key_with_ext);
const path = try std.fs.path.join(allocator, &.{ data_dir, ".index", bucket, key_with_ext });
var component_itr = std.mem.splitScalar(u8, key_with_ext, '/');
while (component_itr.next()) |component| {
if (component.len >= std.posix.NAME_MAX) {
allocator.free(path);
return error.NameTooLong;
}
}
if (path.len >= std.posix.PATH_MAX) {
allocator.free(path);
return error.PathTooLong;
}
return path;
}
fn attrsToText(allocator: Allocator, attrs: *const ObjectAttrs) ![]const u8 {
var buf: std.ArrayListUnmanaged(u8) = .empty;
errdefer buf.deinit(allocator);
try attrsToTextInto(allocator, &buf, attrs);
return buf.toOwnedSlice(allocator);
}
fn writeDistAttrs(allocator: Allocator, dist: *const DistributedContext, bucket: []const u8, key: []const u8, attrs: *const ObjectAttrs) void {
const path = distAttrsPath(allocator, dist.meta_index.data_dir, bucket, key) catch return;
defer allocator.free(path);
const text = attrsToText(allocator, attrs) catch return;
defer allocator.free(text);
if (std.fs.path.dirname(path)) |dir| {
std.Io.Dir.cwd().createDirPath(app_io, dir) catch {};
}
var file = std.Io.Dir.cwd().createFile(app_io, path, .{}) catch return;
defer file.close(app_io);
file.writeStreamingAll(app_io, text) catch {};
if (enable_fsync) {
fsyncFile(file);
fsyncParentDir(path);
}
}
fn readDistAttrs(allocator: Allocator, dist: *const DistributedContext, bucket: []const u8, key: []const u8) ?ObjectAttrs {
const path = distAttrsPath(allocator, dist.meta_index.data_dir, bucket, key) catch return null;
defer allocator.free(path);
var file = std.Io.Dir.cwd().openFile(app_io, path, .{}) catch return null;
defer file.close(app_io);
const content = readToEndAlloc(file, allocator, 64 * 1024) catch return null;
defer allocator.free(content);
return parseAttrsContent(allocator, content) catch null;
}
fn deleteDistAttrs(allocator: Allocator, dist: *const DistributedContext, bucket: []const u8, key: []const u8) void {
const path = distAttrsPath(allocator, dist.meta_index.data_dir, bucket, key) catch return;
defer allocator.free(path);
std.Io.Dir.cwd().deleteFile(app_io, path) catch {};
}
/// Last-write-wins bookkeeping for bucket create/delete propagation.
///
/// Bucket create and delete are broadcast by different nodes at different
/// times, so a peer can receive them in either order. Without ordering, a
/// late-arriving "bucket created" message resurrects a bucket that was
/// deleted moments earlier (issue: flaky `HEAD <bucket>` on replicas).
/// Each node persists per-bucket wall-clock timestamps for the last create
/// and last delete; an incoming op only applies if it is newer, and on a
/// timestamp tie the delete wins (matching the object-metadata tombstone
/// convention, so a delete issued in the same second as a create sticks).
///
/// Persisted as `<create_ts>\n<delete_ts>\n` in `data_dir/.buckets/<bucket>`
/// (a dot-directory, invisible to ListBuckets and index dumps).
const BucketOps = struct {
data_dir: []const u8,
const State = struct {
create_ts: i64 = 0,
delete_ts: i64 = 0, // 0 = never deleted
};
fn path(self: *const BucketOps, allocator: Allocator, bucket: []const u8) ![]const u8 {
return std.fs.path.join(allocator, &.{ self.data_dir, ".buckets", bucket });
}
/// Read the persisted state; returns zeros when absent or unreadable.
fn read(self: *const BucketOps, allocator: Allocator, bucket: []const u8) State {
const p = self.path(allocator, bucket) catch return .{};
defer allocator.free(p);
var file = std.Io.Dir.cwd().openFile(app_io, p, .{}) catch return .{};
defer file.close(app_io);
const stat = file.stat(app_io) catch return .{};
if (stat.size > 128) return .{};
var buf: [128]u8 = undefined;
_ = file.readPositionalAll(app_io, buf[0..@intCast(stat.size)], 0) catch return .{};
var lines = std.mem.splitScalar(u8, buf[0..@intCast(stat.size)], '\n');
const create_ts = std.fmt.parseInt(i64, lines.next() orelse return .{}, 10) catch return .{};
const delete_ts = std.fmt.parseInt(i64, lines.next() orelse return .{}, 10) catch return .{};
return .{ .create_ts = create_ts, .delete_ts = delete_ts };
}
fn write(self: *const BucketOps, allocator: Allocator, bucket: []const u8, state: State) void {
const p = self.path(allocator, bucket) catch return;
defer allocator.free(p);
if (std.fs.path.dirname(p)) |dir| {
std.Io.Dir.cwd().createDirPath(app_io, dir) catch {};
}
var file = std.Io.Dir.cwd().createFile(app_io, p, .{}) catch return;
defer file.close(app_io);
var buf: [64]u8 = undefined;
const text = std.fmt.bufPrint(&buf, "{d}\n{d}\n", .{ state.create_ts, state.delete_ts }) catch return;
file.writeStreamingAll(app_io, text) catch {};
}
/// Record a local or accepted create at `ts`.
fn noteCreate(self: *const BucketOps, allocator: Allocator, bucket: []const u8, ts: i64) void {
const state = self.read(allocator, bucket);
self.write(allocator, bucket, .{ .create_ts = @max(state.create_ts, ts), .delete_ts = state.delete_ts });
}
/// Record a local or accepted delete at `ts`.
fn noteDelete(self: *const BucketOps, allocator: Allocator, bucket: []const u8, ts: i64) void {
const state = self.read(allocator, bucket);
self.write(allocator, bucket, .{ .create_ts = state.create_ts, .delete_ts = @max(state.delete_ts, ts) });
}
/// A peer's create is applicable when it is strictly newer than any local
/// delete; on a tie the delete wins so a deleted bucket cannot resurrect.
fn shouldApplyCreate(self: *const BucketOps, allocator: Allocator, bucket: []const u8, create_ts: i64) bool {
const state = self.read(allocator, bucket);
if (state.delete_ts == 0) return true;
return create_ts > state.delete_ts;
}
/// A peer's delete is applicable when it is at least as new as any local
/// create; on a tie the delete wins.
fn shouldApplyDelete(self: *const BucketOps, allocator: Allocator, bucket: []const u8, delete_ts: i64) bool {
const state = self.read(allocator, bucket);
return delete_ts >= state.create_ts;
}
};
/// Peer information for DHT
const PeerInfo = struct {
id: NodeId,
address: net.IpAddress,
last_seen: i64,
content_count: u32,
};
/// Full Kademlia DHT implementation
/// XOR metric, 160 k-buckets, iterative lookup
const Kademlia = struct {
const K = 20; // Bucket size (replication parameter)
const ALPHA = 3; // Concurrency parameter for lookups
const ID_BITS = 160; // 20 bytes * 8 bits
self_id: NodeId,
buckets: [ID_BITS]KBucket,
// Provider records are only touched from the event-loop thread
providers: std.AutoHashMap(ContentHash, std.ArrayListUnmanaged(NodeId)),
allocator: Allocator,
// Guards `buckets`: the push worker reads/updates the routing table
// (gossip, peer snapshots) concurrently with the event loop
mutex: std.Io.Mutex = .init,
/// A single k-bucket holding up to K peers
const KBucket = struct {
peers: [K]?PeerInfo = [_]?PeerInfo{null} ** K,
count: usize = 0,
last_updated: i64 = 0,
/// Add peer to bucket (LRU eviction if full)
fn add(self: *KBucket, peer: PeerInfo) void {
// Check if already exists, update if so
for (&self.peers) |*slot| {
if (slot.*) |*p| {
if (std.mem.eql(u8, &p.id, &peer.id)) {
p.* = peer;
self.last_updated = std.Io.Clock.real.now(app_io).toSeconds();
return;
}
}
}
// Add to first empty slot
if (self.count < K) {
for (&self.peers) |*slot| {
if (slot.* == null) {
slot.* = peer;
self.count += 1;
self.last_updated = std.Io.Clock.real.now(app_io).toSeconds();
return;
}
}
}