lib/tldr/src/incremental/patch.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const incremental = @import("root.zig");
3
4 const Allocator = std.mem.Allocator;
5 const ContributionKind = incremental.ContributionKind;
6 const ContributionRecord = incremental.ContributionRecord;
7 const Manifest = incremental.Manifest;
8
9 pub const ReplacementContribution = struct {
10 input_name: []const u8,
11 input_index: usize,
12 kind: ContributionKind,
13 name: []const u8,
14 ordinal: u32,
15 size: u64,
16 alignment: u64,
17 output_section_name: ?[]const u8 = null,
18 address: ?u64 = null,
19 file_offset: ?u64 = null,
20 reserved_size: ?u64 = null,
21 payload: []const u8 = &.{},
22 payload_owned: bool = false,
23 unchanged: bool = false,
24 };
25
26 pub const FileRange = struct {
27 offset: usize,
28 len: usize,
29 };
30
31 pub fn replacementFileRange(record: ContributionRecord, replacement: ReplacementContribution) ?FileRange {
32 if (replacement.unchanged) return null;
33 if (record.file_size == 0 and record.size != 0) return null;
34 const offset = std.math.cast(usize, record.file_offset) orelse return null;
35 const len = std.math.cast(usize, record.reserved_size) orelse return null;
36 if (len == 0) return null;
37 return .{ .offset = offset, .len = len };
38 }
39
40 pub fn freeReplacementContributions(allocator: Allocator, replacements: []const ReplacementContribution) void {
41 for (replacements) |replacement| {
42 if (replacement.payload_owned) allocator.free(replacement.payload);
43 }
44 if (replacements.len != 0) allocator.free(replacements);
45 }
46
47 pub const MemberHashUpdate = struct {
48 member_index: usize,
49 hash: u64,
50 };
51
52 pub const DirectRelinkEvidence = struct {
53 replacements: []const ReplacementContribution = &.{},
54 member_updates: []const MemberHashUpdate = &.{},
55 inputs_proven: bool = false,
56
57 pub fn deinit(self: DirectRelinkEvidence, allocator: Allocator) void {
58 freeReplacementContributions(allocator, self.replacements);
59 if (self.member_updates.len != 0) allocator.free(self.member_updates);
60 }
61 };
62
63 pub const PatchDecision = enum {
64 in_place,
65 full_link,
66 };
67
68 pub const PatchBlocker = enum {
69 missing_contribution,
70 unpatchable_contribution,
71 layout_changed,
72 grew_past_reserve,
73 alignment_increased,
74 };
75
76 pub const PatchPlan = struct {
77 decision: PatchDecision,
78 blocker: ?PatchBlocker = null,
79 blocking_index: ?usize = null,
80 };
81
82 pub const PatchApplication = struct {
83 plan: PatchPlan,
84 contributions_written: usize = 0,
85 bytes_written: usize = 0,
86 zero_fill_bytes: usize = 0,
87 };
88
89 pub const PatchApplyError = error{
90 PatchPayloadMismatch,
91 PatchRangeOutOfBounds,
92 };
93
94 pub const ContributionMatch = struct {
95 record: ContributionRecord,
96 index: usize,
97 };
98
99 pub const ContributionCursor = struct {
100 index: usize = 0,
101
102 pub fn find(
103 self: *ContributionCursor,
104 manifest: Manifest,
105 replacement: ReplacementContribution,
106 ) ?ContributionMatch {
107 const match = findContributionFrom(manifest, replacement, self.index) orelse
108 findContributionFrom(manifest, replacement, 0) orelse return null;
109 if (match.index >= self.index) self.index = match.index + 1;
110 return match;
111 }
112 };
113
114 const ContributionKey = struct {
115 input_name: []const u8,
116 input_index: usize,
117 kind: ContributionKind,
118 name: []const u8,
119 ordinal: u32,
120
121 fn fromRecord(manifest: Manifest, record: ContributionRecord) ContributionKey {
122 return .{
123 .input_name = manifest.string(record.input_name_id),
124 .input_index = @intCast(record.input_index),
125 .kind = record.kind,
126 .name = manifest.string(record.name_id),
127 .ordinal = record.ordinal,
128 };
129 }
130
131 fn fromReplacement(replacement: ReplacementContribution) ContributionKey {
132 return .{
133 .input_name = replacement.input_name,
134 .input_index = replacement.input_index,
135 .kind = replacement.kind,
136 .name = replacement.name,
137 .ordinal = replacement.ordinal,
138 };
139 }
140 };
141
142 const ContributionKeyContext = struct {
143 pub fn hash(_: ContributionKeyContext, key: ContributionKey) u64 {
144 var hasher = std.hash.Wyhash.init(0);
145 hasher.update(key.input_name);
146 hasher.update(&.{0});
147 var input_index_bytes: [@sizeOf(usize)]u8 = undefined;
148 std.mem.writeInt(usize, &input_index_bytes, key.input_index, .little);
149 hasher.update(&input_index_bytes);
150 hasher.update(&.{0});
151 hasher.update(&.{@backingInt(key.kind)});
152 hasher.update(&.{0});
153 hasher.update(key.name);
154 hasher.update(&.{0});
155 var ordinal_bytes: [4]u8 = undefined;
156 std.mem.writeInt(u32, &ordinal_bytes, key.ordinal, .little);
157 hasher.update(&ordinal_bytes);
158 return hasher.final();
159 }
160
161 pub fn eql(_: ContributionKeyContext, a: ContributionKey, b: ContributionKey) bool {
162 return a.kind == b.kind and
163 a.ordinal == b.ordinal and
164 a.input_index == b.input_index and
165 std.mem.eql(u8, a.input_name, b.input_name) and
166 std.mem.eql(u8, a.name, b.name);
167 }
168 };
169
170 const contribution_key_context = ContributionKeyContext{};
171 const ContributionIndexMap = std.HashMapUnmanaged(ContributionKey, usize, ContributionKeyContext, 80);
172
173 const DuplicateContributionError = error{
174 DuplicateContribution,
175 };
176
177 pub const IndexError = Allocator.Error || DuplicateContributionError;
178
179 pub const ContributionIndex = struct {
180 map: ContributionIndexMap = .empty,
181
182 pub fn init(allocator: Allocator, manifest: Manifest) IndexError!ContributionIndex {
183 var index = ContributionIndex{};
184 errdefer index.deinit(allocator);
185 try index.map.ensureTotalCapacity(allocator, @intCast(manifest.contributions.len));
186 for (manifest.contributions, 0..) |contribution, contribution_index| {
187 const gop = index.map.getOrPutAssumeCapacityContext(
188 ContributionKey.fromRecord(manifest, contribution),
189 contribution_key_context,
190 );
191 if (gop.found_existing) return error.DuplicateContribution;
192 gop.value_ptr.* = contribution_index;
193 }
194 return index;
195 }
196
197 pub fn initForReplacements(
198 allocator: Allocator,
199 manifest: Manifest,
200 replacements: []const ReplacementContribution,
201 ) IndexError!ContributionIndex {
202 var index = ContributionIndex{};
203 errdefer index.deinit(allocator);
204 if (replacements.len == 0 or manifest.contributions.len == 0) return index;
205
206 var max_input_index: usize = 0;
207 for (manifest.contributions) |contribution| {
208 max_input_index = @max(max_input_index, contribution.input_index);
209 }
210 var inputs = try std.DynamicBitSetUnmanaged.initEmpty(allocator, max_input_index + 1);
211 defer inputs.deinit(allocator);
212 for (replacements) |replacement| {
213 if (replacement.input_index <= max_input_index) inputs.set(replacement.input_index);
214 }
215
216 var filtered: usize = 0;
217 for (manifest.contributions) |contribution| {
218 if (inputs.isSet(contribution.input_index)) filtered += 1;
219 }
220 if (filtered == 0) return index;
221
222 try index.map.ensureTotalCapacity(allocator, @intCast(filtered));
223 for (manifest.contributions, 0..) |contribution, contribution_index| {
224 if (!inputs.isSet(contribution.input_index)) continue;
225 const gop = index.map.getOrPutAssumeCapacityContext(
226 ContributionKey.fromRecord(manifest, contribution),
227 contribution_key_context,
228 );
229 if (gop.found_existing) return error.DuplicateContribution;
230 gop.value_ptr.* = contribution_index;
231 }
232 return index;
233 }
234
235 pub fn deinit(self: *ContributionIndex, allocator: Allocator) void {
236 self.map.deinit(allocator);
237 self.* = .{};
238 }
239
240 pub fn contributionIndexForReplacement(self: ContributionIndex, replacement: ReplacementContribution) ?usize {
241 return self.map.getContext(
242 ContributionKey.fromReplacement(replacement),
243 contribution_key_context,
244 );
245 }
246
247 pub fn planContributionReplacement(
248 self: ContributionIndex,
249 manifest: Manifest,
250 replacements: []const ReplacementContribution,
251 ) PatchPlan {
252 for (replacements, 0..) |replacement, replacement_index| {
253 const contribution_index = self.contributionIndexForReplacement(replacement) orelse return .{
254 .decision = .full_link,
255 .blocker = .missing_contribution,
256 .blocking_index = replacement_index,
257 };
258 if (contribution_index >= manifest.contributions.len) {
259 return .{
260 .decision = .full_link,
261 .blocker = .missing_contribution,
262 .blocking_index = replacement_index,
263 };
264 }
265 const record = manifest.contributions[contribution_index];
266 if (!contribution_key_context.eql(ContributionKey.fromRecord(manifest, record), ContributionKey.fromReplacement(replacement))) {
267 return .{
268 .decision = .full_link,
269 .blocker = .missing_contribution,
270 .blocking_index = replacement_index,
271 };
272 }
273 if (blockerForRecord(manifest, record, replacement, replacement_index)) |plan| {
274 return plan;
275 }
276 }
277 return .{ .decision = .in_place };
278 }
279
280 pub fn applyContributionReplacement(
281 self: ContributionIndex,
282 image: []u8,
283 manifest: Manifest,
284 replacements: []const ReplacementContribution,
285 ) PatchApplyError!PatchApplication {
286 var application = PatchApplication{
287 .plan = self.planContributionReplacement(manifest, replacements),
288 };
289 if (application.plan.decision == .full_link) return application;
290 for (replacements, 0..) |replacement, replacement_index| {
291 const contribution_index = self.contributionIndexForReplacement(replacement) orelse {
292 application.plan = .{
293 .decision = .full_link,
294 .blocker = .missing_contribution,
295 .blocking_index = replacement_index,
296 };
297 return application;
298 };
299 if (contribution_index >= manifest.contributions.len) {
300 application.plan = .{
301 .decision = .full_link,
302 .blocker = .missing_contribution,
303 .blocking_index = replacement_index,
304 };
305 return application;
306 }
307 try applyReplacementBytes(
308 image,
309 manifest.contributions[contribution_index],
310 replacement,
311 &application,
312 );
313 }
314 return application;
315 }
316
317 pub fn applyContributionReplacementInPlace(
318 self: ContributionIndex,
319 image: []u8,
320 manifest: Manifest,
321 replacements: []const ReplacementContribution,
322 ) PatchApplyError!PatchApplication {
323 var application = PatchApplication{
324 .plan = .{ .decision = .in_place },
325 };
326 for (replacements, 0..) |replacement, replacement_index| {
327 const contribution_index = self.contributionIndexForReplacement(replacement) orelse {
328 application.plan = .{
329 .decision = .full_link,
330 .blocker = .missing_contribution,
331 .blocking_index = replacement_index,
332 };
333 return application;
334 };
335 if (contribution_index >= manifest.contributions.len) {
336 application.plan = .{
337 .decision = .full_link,
338 .blocker = .missing_contribution,
339 .blocking_index = replacement_index,
340 };
341 return application;
342 }
343 try applyReplacementBytes(
344 image,
345 manifest.contributions[contribution_index],
346 replacement,
347 &application,
348 );
349 }
350 return application;
351 }
352 };
353
354 pub fn planContributionReplacement(
355 manifest: Manifest,
356 replacements: []const ReplacementContribution,
357 ) PatchPlan {
358 var cursor = ContributionCursor{};
359 for (replacements, 0..) |replacement, replacement_index| {
360 const contribution_match = cursor.find(manifest, replacement) orelse return .{
361 .decision = .full_link,
362 .blocker = .missing_contribution,
363 .blocking_index = replacement_index,
364 };
365 if (blockerForRecord(manifest, contribution_match.record, replacement, replacement_index)) |plan| {
366 return plan;
367 }
368 }
369 return .{ .decision = .in_place };
370 }
371
372 pub fn applyContributionReplacement(
373 manifest: Manifest,
374 image: []u8,
375 replacements: []const ReplacementContribution,
376 ) PatchApplyError!PatchApplication {
377 const application = PatchApplication{
378 .plan = planContributionReplacement(manifest, replacements),
379 };
380 if (application.plan.decision == .full_link) return application;
381 return try applyPlannedContributionReplacement(manifest, image, replacements, application);
382 }
383
384 pub fn applyContributionReplacementInPlace(
385 manifest: Manifest,
386 image: []u8,
387 replacements: []const ReplacementContribution,
388 ) PatchApplyError!PatchApplication {
389 const application = PatchApplication{
390 .plan = .{ .decision = .in_place },
391 };
392 return try applyPlannedContributionReplacement(manifest, image, replacements, application);
393 }
394
395 fn applyPlannedContributionReplacement(
396 manifest: Manifest,
397 image: []u8,
398 replacements: []const ReplacementContribution,
399 accepted: PatchApplication,
400 ) PatchApplyError!PatchApplication {
401 var application = accepted;
402 var cursor = ContributionCursor{};
403 for (replacements, 0..) |replacement, replacement_index| {
404 const contribution_match = cursor.find(manifest, replacement) orelse {
405 application.plan = .{
406 .decision = .full_link,
407 .blocker = .missing_contribution,
408 .blocking_index = replacement_index,
409 };
410 return application;
411 };
412 try applyReplacementBytes(image, contribution_match.record, replacement, &application);
413 }
414 return application;
415 }
416
417 fn findContributionFrom(
418 manifest: Manifest,
419 replacement: ReplacementContribution,
420 start_index: usize,
421 ) ?ContributionMatch {
422 var contribution_index = start_index;
423 while (contribution_index < manifest.contributions.len) : (contribution_index += 1) {
424 const contribution = manifest.contributions[contribution_index];
425 if (!contributionMatchesReplacement(manifest, contribution, replacement)) continue;
426 return .{
427 .record = contribution,
428 .index = contribution_index,
429 };
430 }
431 return null;
432 }
433
434 fn contributionMatchesReplacement(
435 manifest: Manifest,
436 contribution: ContributionRecord,
437 replacement: ReplacementContribution,
438 ) bool {
439 return contribution.kind == replacement.kind and
440 contribution.ordinal == replacement.ordinal and
441 contribution.input_index == replacement.input_index and
442 std.mem.eql(u8, manifest.string(contribution.input_name_id), replacement.input_name) and
443 std.mem.eql(u8, manifest.string(contribution.name_id), replacement.name);
444 }
445
446 fn blockerForRecord(
447 manifest: Manifest,
448 record: ContributionRecord,
449 replacement: ReplacementContribution,
450 replacement_index: usize,
451 ) ?PatchPlan {
452 if (replacement.unchanged) return null;
453 if (record.file_size != record.size and !(record.file_size == 0 and replacement.payload.len == 0)) {
454 return .{
455 .decision = .full_link,
456 .blocker = .unpatchable_contribution,
457 .blocking_index = replacement_index,
458 };
459 }
460 if (replacement.output_section_name) |output_section_name| {
461 if (!std.mem.eql(u8, manifest.string(record.output_section_name_id), output_section_name)) {
462 return .{
463 .decision = .full_link,
464 .blocker = .layout_changed,
465 .blocking_index = replacement_index,
466 };
467 }
468 }
469 if (replacement.address) |address| {
470 if (record.address != address) {
471 return .{
472 .decision = .full_link,
473 .blocker = .layout_changed,
474 .blocking_index = replacement_index,
475 };
476 }
477 }
478 if (replacement.file_offset) |file_offset| {
479 if (record.file_offset != file_offset) {
480 return .{
481 .decision = .full_link,
482 .blocker = .layout_changed,
483 .blocking_index = replacement_index,
484 };
485 }
486 }
487 if (replacement.reserved_size) |reserved_size| {
488 if (record.reserved_size != reserved_size) {
489 return .{
490 .decision = .full_link,
491 .blocker = .layout_changed,
492 .blocking_index = replacement_index,
493 };
494 }
495 }
496 if (@max(replacement.alignment, 1) > @max(record.alignment, 1)) {
497 return .{
498 .decision = .full_link,
499 .blocker = .alignment_increased,
500 .blocking_index = replacement_index,
501 };
502 }
503 if (replacement.size > record.reserved_size) {
504 return .{
505 .decision = .full_link,
506 .blocker = .grew_past_reserve,
507 .blocking_index = replacement_index,
508 };
509 }
510 return null;
511 }
512
513 fn applyReplacementBytes(
514 image: []u8,
515 record: ContributionRecord,
516 replacement: ReplacementContribution,
517 application: *PatchApplication,
518 ) PatchApplyError!void {
519 if (replacement.unchanged) return;
520 const size = std.math.cast(usize, replacement.size) orelse return error.PatchRangeOutOfBounds;
521 if (record.file_size == 0 and record.size != 0) {
522 if (replacement.payload.len != 0) return error.PatchPayloadMismatch;
523 if (size > record.reserved_size) return error.PatchRangeOutOfBounds;
524 application.contributions_written += 1;
525 return;
526 }
527
528 const start = std.math.cast(usize, record.file_offset) orelse return error.PatchRangeOutOfBounds;
529 const reserve = std.math.cast(usize, record.reserved_size) orelse return error.PatchRangeOutOfBounds;
530 if (replacement.payload.len != size) return error.PatchPayloadMismatch;
531 if (start > image.len or reserve > image.len - start) return error.PatchRangeOutOfBounds;
532 if (size > reserve) return error.PatchRangeOutOfBounds;
533 var wrote = false;
534 const payload = image[start..][0..size];
535 if (size != 0 and !std.mem.eql(u8, payload, replacement.payload)) {
536 @memcpy(payload, replacement.payload);
537 application.bytes_written += size;
538 wrote = true;
539 }
540 const zero_fill = reserve - size;
541 const zero_fill_payload = image[start + size ..][0..zero_fill];
542 if (zero_fill != 0 and !allZero(zero_fill_payload)) {
543 @memset(zero_fill_payload, 0);
544 application.zero_fill_bytes += zero_fill;
545 wrote = true;
546 }
547 if (wrote) application.contributions_written += 1;
548 }
549
550 fn allZero(bytes: []const u8) bool {
551 for (bytes) |byte| {
552 if (byte != 0) return false;
553 }
554 return true;
555 }
556
557 test "contribution index accepted in-place application reports stale replacements" {
558 const allocator = std.testing.allocator;
559 var builder = try incremental.Builder.init(allocator, .{});
560 defer builder.deinit();
561 try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
562
563 var manifest = try builder.finish();
564 defer manifest.deinit(allocator);
565
566 var index = try ContributionIndex.init(allocator, manifest);
567 defer index.deinit(allocator);
568
569 var image = @as([16]u8, @splat(0xaa));
570 const application = try index.applyContributionReplacementInPlace(
571 image[0..],
572 manifest,
573 &.{
574 .{ .input_name = "missing.o", .input_index = 9, .kind = .section, .name = ".text.missing", .ordinal = 1, .size = 4, .alignment = 16, .payload = "miss" },
575 },
576 );
577
578 try std.testing.expectEqual(PatchDecision.full_link, application.plan.decision);
579 try std.testing.expectEqual(PatchBlocker.missing_contribution, application.plan.blocker.?);
580 try std.testing.expectEqual(@as(?usize, 0), application.plan.blocking_index);
581 try std.testing.expectEqual(@as(usize, 0), application.contributions_written);
582 try std.testing.expectEqual(@as(usize, 0), application.bytes_written);
583 try std.testing.expectEqual(@as(u8, 0xaa), image[4]);
584 }
585
586 test "contribution replacement skips byte-identical image writes" {
587 const allocator = std.testing.allocator;
588 var builder = try incremental.Builder.init(allocator, .{});
589 defer builder.deinit();
590 try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
591
592 var manifest = try builder.finish();
593 defer manifest.deinit(allocator);
594
595 const replacement = [_]ReplacementContribution{
596 .{ .input_name = "a.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 3, .alignment = 16, .payload = "old" },
597 };
598
599 var clean_image = @as([16]u8, @splat(0xaa));
600 @memcpy(clean_image[4..7], "old");
601 @memset(clean_image[7..12], 0);
602 const clean_application = try manifest.applyContributionReplacement(clean_image[0..], &replacement);
603
604 try std.testing.expectEqual(PatchDecision.in_place, clean_application.plan.decision);
605 try std.testing.expectEqual(@as(usize, 0), clean_application.contributions_written);
606 try std.testing.expectEqual(@as(usize, 0), clean_application.bytes_written);
607 try std.testing.expectEqual(@as(usize, 0), clean_application.zero_fill_bytes);
608 try std.testing.expectEqualSlices(u8, "old", clean_image[4..7]);
609 try std.testing.expectEqualSlices(u8, &.{ 0, 0, 0, 0, 0 }, clean_image[7..12]);
610
611 var dirty_padding_image = @as([16]u8, @splat(0xaa));
612 @memcpy(dirty_padding_image[4..7], "old");
613 const dirty_padding_application = try manifest.applyContributionReplacement(dirty_padding_image[0..], &replacement);
614
615 try std.testing.expectEqual(PatchDecision.in_place, dirty_padding_application.plan.decision);
616 try std.testing.expectEqual(@as(usize, 1), dirty_padding_application.contributions_written);
617 try std.testing.expectEqual(@as(usize, 0), dirty_padding_application.bytes_written);
618 try std.testing.expectEqual(@as(usize, 5), dirty_padding_application.zero_fill_bytes);
619 try std.testing.expectEqualSlices(u8, "old", dirty_padding_image[4..7]);
620 try std.testing.expectEqualSlices(u8, &.{ 0, 0, 0, 0, 0 }, dirty_padding_image[7..12]);
621 }