| 1 | //! Provides the following guarantees: |
| 2 | //! * `deinit` reports all leaks and frees all backing memory. |
| 3 | //! * All allocation mismatches result in either a panic or segmentation fault. |
| 4 | //! * Allocations from other `SafeAllocator` instances cause a panic (if `Options.canary` differ). |
| 5 | //! * Double frees and operation (resize, remap, and free) races panic or segmentation fault. |
| 6 | //! |
| 7 | //! Given the backing allocator does not reuse memory, this does not reuse memory either and |
| 8 | //! * Most writes after free will segmentation fault or are eventually detected and panic. |
| 9 | //! |
| 10 | //! Thread-safe |
| 11 | |
| 12 | // General Design: |
| 13 | // |
| 14 | // Every allocation is trailed by an `AllocFooter` which contains metadata for the allocation and |
| 15 | // stack traces. It is protected by a checksum to catch corruption from allocation overwrites and |
| 16 | // report canary mismatches. An allocation's memory has a minimum alignment of `AllocFooter` so |
| 17 | // that the footer is at a fixed offset determined from the allocation size. An allocation's memory |
| 18 | // is stored either: |
| 19 | // * Inside linearly-filled buckets for small allocations. |
| 20 | // * Inside an allocation directly from the backing allocator. |
| 21 | // |
| 22 | // To track allocations, each thread maintains a table of backing allocations. The table may be |
| 23 | // modified by other threads in the case of a producer-consumer operation, so the table is a linked |
| 24 | // list only expanded by creating new segments. Each thread maintains a linked list of free |
| 25 | // entries, which may contain entries from other threads' tables. |
| 26 | // |
| 27 | // In the case of producer-consumer operations, acquire/release ordering is assumed to be provided |
| 28 | // externally. This is also assumed by all other thread-safe allocators that reuse memory as |
| 29 | // otherwise there would be data races on reuse of allocated memory. |
| 30 | |
| 31 | const std = @import("../std.zig"); |
| 32 | const math = std.math; |
| 33 | const mem = std.mem; |
| 34 | const Alignment = mem.Alignment; |
| 35 | const assert = std.debug.assert; |
| 36 | const panic = std.debug.panic; |
| 37 | |
| 38 | const SafeAllocator = @This(); |
| 39 | const scoped_log = std.log.scoped(.SafeAllocator); |
| 40 | |
| 41 | pub const Options = struct { |
| 42 | const is_debug = @import("builtin").mode == .debug; |
| 43 | const page_size_log2 = @max(math.log2_int(usize, std.heap.page_size_max), 8); |
| 44 | |
| 45 | stack_trace_frames: usize = if (is_debug and std.debug.sys_can_stack_trace) 7 else 0, |
| 46 | check_write_after_free: bool = is_debug, |
| 47 | /// A unique value used to check that allocations created by other |
| 48 | /// `SafeAllocator` instances are not passed to this one. |
| 49 | canary: u32 = 0x85dff10f, |
| 50 | |
| 51 | /// Controls the block size and alignment of allocation buckets. |
| 52 | /// |
| 53 | /// Changing this is useful to save memory if the backing allocator offers better granuality, |
| 54 | /// or if the backing allocator has a limit on active allocations, however decreasing this |
| 55 | /// can harm performance. |
| 56 | /// |
| 57 | /// Asserted to be >= 8 |
| 58 | bucket_size_log2: u5 = @max(page_size_log2, 13), |
| 59 | /// Controls the block size of internal metadata. |
| 60 | /// |
| 61 | /// Changing this is useful to save memory if the backing allocator offers better granuality, |
| 62 | /// or if the backing allocator has a limit on active allocations, however decreasing this |
| 63 | /// can harm performance. |
| 64 | /// |
| 65 | /// Asserted to be >= 8 |
| 66 | block_size_log2: u5 = page_size_log2, |
| 67 | }; |
| 68 | |
| 69 | var n_threads: usize = 0; |
| 70 | threadlocal var thread_index: usize = 0; |
| 71 | |
| 72 | backing: mem.Allocator, |
| 73 | // Needs to be a fixed size so the max `n_threads` value is agreed upon by all instances. |
| 74 | threads: [128]Thread, |
| 75 | |
| 76 | bucket_size_log2: u5, |
| 77 | block_size_log2: u5, |
| 78 | /// In `usize`s |
| 79 | stack_trace_size: usize, |
| 80 | /// In `usize`s |
| 81 | allocs_entry_count: usize, |
| 82 | large_alloc_threshold: usize, |
| 83 | |
| 84 | canary: u32, |
| 85 | check_write_after_free: bool, |
| 86 | |
| 87 | fn bucketSize(s: *SafeAllocator) u32 { |
| 88 | return @as(u32, 1) << s.bucket_size_log2; |
| 89 | } |
| 90 | |
| 91 | fn bucketMask(s: *SafeAllocator) u32 { |
| 92 | return s.bucketSize() - 1; |
| 93 | } |
| 94 | |
| 95 | const Thread = struct { |
| 96 | /// Avoid false sharing. |
| 97 | _: void align(std.atomic.cache_line) = {}, |
| 98 | |
| 99 | mutex: std.atomic.Mutex, |
| 100 | fill_bucket: ?*Bucket, |
| 101 | free_entry: ?*Allocs.Entry, |
| 102 | allocs_next: usize, |
| 103 | allocs_first: ?*Allocs, |
| 104 | }; |
| 105 | |
| 106 | /// Trailed by `[allocs_entry_count]Entry` |
| 107 | const Allocs = extern struct { |
| 108 | next: ?*Allocs, |
| 109 | |
| 110 | comptime { |
| 111 | assert(@alignOf(@This()) == @alignOf(usize)); |
| 112 | assert(@sizeOf(@This()) == @sizeOf(usize)); |
| 113 | } |
| 114 | |
| 115 | fn usizes(a: *Allocs, s: *SafeAllocator) []usize { |
| 116 | return @as([*]usize, @ptrCast(a))[0 .. 1 + s.allocs_entry_count]; |
| 117 | } |
| 118 | |
| 119 | fn entries(a: *Allocs, s: *SafeAllocator) []Entry { |
| 120 | return @as([*]Entry, @ptrCast(a))[1..][0..s.allocs_entry_count]; |
| 121 | } |
| 122 | |
| 123 | const Entry = packed struct(usize) { |
| 124 | kind: Kind, |
| 125 | ptr_high: @Int(.unsigned, @bitSizeOf(usize) - 2), |
| 126 | |
| 127 | const Kind = enum(u2) { free, bucket, large_alloc }; |
| 128 | |
| 129 | comptime { |
| 130 | assert(@alignOf(Entry) >= 4); |
| 131 | assert(@alignOf(Bucket) >= 4); |
| 132 | assert(@alignOf(AllocFooter) >= 4); |
| 133 | } |
| 134 | |
| 135 | fn fromFree(ptr: ?*Entry) Entry { |
| 136 | return .{ |
| 137 | .ptr_high = @intCast(@intFromPtr(ptr) >> 2), |
| 138 | .kind = .free, |
| 139 | }; |
| 140 | } |
| 141 | |
| 142 | fn fromBucket(ptr: *Bucket) Entry { |
| 143 | return .{ |
| 144 | .ptr_high = @intCast(@intFromPtr(ptr) >> 2), |
| 145 | .kind = .bucket, |
| 146 | }; |
| 147 | } |
| 148 | |
| 149 | fn fromLargeAlloc(ptr: *AllocFooter) Entry { |
| 150 | return .{ |
| 151 | .ptr_high = @intCast(@intFromPtr(ptr) >> 2), |
| 152 | .kind = .large_alloc, |
| 153 | }; |
| 154 | } |
| 155 | |
| 156 | fn toFree(ent: Entry) ?*Entry { |
| 157 | assert(ent.kind == .free); |
| 158 | return @ptrFromInt(@as(usize, ent.ptr_high) << 2); |
| 159 | } |
| 160 | |
| 161 | fn toBucket(ent: Entry) *Bucket { |
| 162 | assert(ent.kind == .bucket); |
| 163 | return @ptrFromInt(@as(usize, ent.ptr_high) << 2); |
| 164 | } |
| 165 | |
| 166 | fn toLargeAlloc(ent: Entry) *AllocFooter { |
| 167 | assert(ent.kind == .large_alloc); |
| 168 | return @ptrFromInt(@as(usize, ent.ptr_high) << 2); |
| 169 | } |
| 170 | }; |
| 171 | }; |
| 172 | |
| 173 | /// This struct contains the header for a bucket. It is always part of a larger |
| 174 | /// allocations of length and alignment `bucketSize()`. |
| 175 | /// |
| 176 | /// All allocations inside buckets have a minimum of 8-byte alignment (including length) |
| 177 | /// so that allocations with 8-byte alignment or less do not need to store the location |
| 178 | /// of the previous footer since it is directly before it. This property is used by non- |
| 179 | /// extended footers to omit the offset of the previous footer. |
| 180 | const Bucket = struct { |
| 181 | entry: *Allocs.Entry, |
| 182 | /// Accesed atomically with `.acquire` / `.release` ordering to |
| 183 | /// provide memory ordering for allocation footers, **expect for |
| 184 | /// the `modify` field**. This needs `.acquire` fenced every time |
| 185 | /// footer data is updated (`AllocCount.fenceAcqRel`). |
| 186 | alloc_count: AllocCount, |
| 187 | /// Accesed atomically with `.monotonic` ordering. Alternatively, |
| 188 | /// this is also synchronized by `alloc_count`. |
| 189 | fill: Fill, |
| 190 | |
| 191 | /// So that `@sizeOf(Bucket)` is the start of first allocation if it is 8-byte aligned or less. |
| 192 | _: void align(8) = {}, |
| 193 | comptime { |
| 194 | assert(@alignOf(@This()) >= 8); |
| 195 | } |
| 196 | |
| 197 | const AllocCount = packed struct(u32) { |
| 198 | n: u31, |
| 199 | /// If `true`, this bucket cannot be freed yet. |
| 200 | filling: bool, |
| 201 | |
| 202 | fn fenceAcqRel(a: *AllocCount) void { |
| 203 | _ = @atomicRmw(AllocCount, a, .Or, .{ .n = 0, .filling = false }, .acq_rel); |
| 204 | } |
| 205 | }; |
| 206 | |
| 207 | const Fill = packed struct(u32) { |
| 208 | at: u31, |
| 209 | last_is_extended: bool, |
| 210 | }; |
| 211 | |
| 212 | fn of(s: *SafeAllocator, ptr: [*]u8) *Bucket { |
| 213 | const size_log2 = s.bucket_size_log2; |
| 214 | return @ptrFromInt(@intFromPtr(ptr) >> @intCast(size_log2) << @intCast(size_log2)); |
| 215 | } |
| 216 | |
| 217 | fn fillAt(s: *SafeAllocator, ptr: [*]const u8) u32 { |
| 218 | return @intCast(@intFromPtr(ptr) & s.bucketMask()); |
| 219 | } |
| 220 | |
| 221 | fn bytes(b: *Bucket, s: *SafeAllocator) []u8 { |
| 222 | assert(@intFromPtr(b) & s.bucketMask() == 0); |
| 223 | return @as([*]u8, @ptrCast(b))[0..s.bucketSize()]; |
| 224 | } |
| 225 | |
| 226 | fn lastAlloc(b: *Bucket, s: *SafeAllocator, fill: Fill) ?*AllocFooter { |
| 227 | return b.allocFooterBefore(s, fill.at, fill.last_is_extended); |
| 228 | } |
| 229 | |
| 230 | fn allocFooterBefore(b: *Bucket, s: *SafeAllocator, at: u32, is_extended: bool) ?*AllocFooter { |
| 231 | if (at - @sizeOf(Bucket) == 0) return null; |
| 232 | const off = at - AllocFooter.lenBucket(s, is_extended); |
| 233 | assert(off >= @sizeOf(Bucket)); |
| 234 | return @ptrCast(@alignCast(b.bytes(s)[off..])); |
| 235 | } |
| 236 | |
| 237 | /// Checks that no writes after frees were performed. |
| 238 | /// |
| 239 | /// Assumes `b.alloc_count` has been loaded with `.acquire` ordering. |
| 240 | fn check(b: *Bucket, s: *SafeAllocator) void { |
| 241 | var footer = b.lastAlloc(s, b.fill).?; |
| 242 | while (true) { |
| 243 | const modify = @atomicLoad( |
| 244 | AllocFooter.Modify, |
| 245 | &footer.modify, |
| 246 | // The only possible value should be `.freed` since `b.alloc_count` |
| 247 | // has been loaded with `.acquire`. However, another thread may be trying to |
| 248 | // modify the allocation after it is freed and so the other thread is going |
| 249 | // to panic even if this thread still sees `.freed`. |
| 250 | .unordered, |
| 251 | ).storedXor(&footer.modify); |
| 252 | if (modify != .freed or footer.actualChecksum(s) != footer.checksum ^ s.canary) { |
| 253 | panic("corrupted footer metadata in bucket at *{x}", .{@intFromPtr(&footer)}); |
| 254 | } |
| 255 | |
| 256 | s.checkFreed(footer); |
| 257 | footer = footer.bucketPrev(b, s) orelse break; |
| 258 | } |
| 259 | } |
| 260 | }; |
| 261 | |
| 262 | /// Trails the allocation, which has the following advantages: |
| 263 | /// * For buckets, the footer of the last allocation is always at the current fill. |
| 264 | /// * Aligning the allocation is simpler and wastes less space. |
| 265 | /// * Allocation overwrites are more likely to be caught by the footer getting corrupted. |
| 266 | /// For bucket allocs, this is trailed by `[2][stack_trace_size]usize`. |
| 267 | /// For large allocs, this is trailed by `[1][stack_trace_size]usize`. |
| 268 | const AllocFooter = struct { |
| 269 | /// Hash of `data` with the seed as the hash of its address so that memcpys of allocation |
| 270 | /// metadata are detected or are at least caught across runs. |
| 271 | /// |
| 272 | /// This stored value is xored with the canary value so that canary mismatches are detected. |
| 273 | checksum: u32, |
| 274 | /// Accesed atomically with `.monotonic` ordering to catch operation races. |
| 275 | /// |
| 276 | /// This stored value is xored with the hash of its address so that memcpys of allocation |
| 277 | /// metadata are detected or are at least caught across runs. |
| 278 | modify: Modify, |
| 279 | data: Data, |
| 280 | |
| 281 | /// `8`: minimum alignment for `Bucket` allocations |
| 282 | /// `@alignOf(usize)`: so that the offset of trailing data is at `@sizeOf(@This())` |
| 283 | _: void align(@max(8, @alignOf(usize))) = {}, |
| 284 | |
| 285 | comptime { |
| 286 | assert(@alignOf(@This()) >= @max(8, @alignOf(usize))); |
| 287 | } |
| 288 | |
| 289 | const Data = packed struct(u16) { |
| 290 | len: Len, |
| 291 | /// Low bits of the alignment. |
| 292 | /// |
| 293 | /// For non-extended headers, this is the entire alignment. The location of the previous |
| 294 | /// header is directly before this allocation since footers in `Bucket` are gauraunteed to |
| 295 | /// have at least 8-byte alignment. |
| 296 | alignment: u2, |
| 297 | /// Used only for bucket allocations. |
| 298 | prev_extended: bool, |
| 299 | |
| 300 | const Len = enum(u13) { |
| 301 | _, |
| 302 | |
| 303 | /// This footer is trailed (before the traces) by `Extended`. |
| 304 | /// The high bits of the alignment are encoded as the offset from `extended_start`. |
| 305 | /// |
| 306 | /// This may be set even if `Extended` is not strictly necesary |
| 307 | /// as a result of resizes and remaps. |
| 308 | const extended_start: u13 = math.maxInt(u13) - ((@bitSizeOf(usize) - 1) >> 2); |
| 309 | }; |
| 310 | }; |
| 311 | |
| 312 | const Extended = struct { |
| 313 | len: usize, |
| 314 | container: Container, |
| 315 | |
| 316 | const Container = union { |
| 317 | bucket_prev: ?*AllocFooter, |
| 318 | large_entry: *Allocs.Entry, |
| 319 | }; |
| 320 | |
| 321 | comptime { |
| 322 | // Exactly `usize` so this is directly after the regular footer |
| 323 | // and so that traces start directly after `@sizeOf(@This())`. |
| 324 | assert(@alignOf(@This()) == @alignOf(usize)); |
| 325 | } |
| 326 | }; |
| 327 | |
| 328 | const Modify = enum(u16) { |
| 329 | // Random non-linear enum values to decrease the chance of undetected corruption. |
| 330 | none = 0x2962, |
| 331 | resized = 0x0030, |
| 332 | remaped = 0x9068, |
| 333 | freeing = 0x7f3d, |
| 334 | freed = 0xb98b, |
| 335 | _, |
| 336 | |
| 337 | fn setNone(m: *Modify) void { |
| 338 | _ = @atomicRmw(Modify, m, .Xchg, .storedXor(.none, m), .monotonic); |
| 339 | } |
| 340 | |
| 341 | fn opName(m: Modify) []const u8 { |
| 342 | return switch (m) { |
| 343 | .resized => "resize", |
| 344 | .remaped => "remap", |
| 345 | .freeing => "free", |
| 346 | _, .none, .freed => unreachable, |
| 347 | }; |
| 348 | } |
| 349 | |
| 350 | fn stateName(m: Modify) []const u8 { |
| 351 | return switch (m) { |
| 352 | .resized => "after resize", |
| 353 | .remaped => "after remap", |
| 354 | .freeing => "during free", |
| 355 | .freed => "after free", |
| 356 | _, .none => unreachable, |
| 357 | }; |
| 358 | } |
| 359 | |
| 360 | fn storedXor(m: Modify, ptr: *Modify) Modify { |
| 361 | const addr_hash: u16 = @truncate(std.hash.int(@intFromPtr(ptr))); |
| 362 | return @fromBackingInt(@intCast(@backingInt(m) ^ addr_hash)); |
| 363 | } |
| 364 | }; |
| 365 | |
| 366 | fn isExtended(f: *AllocFooter) bool { |
| 367 | return @backingInt(f.data.len) >= Data.Len.extended_start; |
| 368 | } |
| 369 | |
| 370 | fn extended(f: *AllocFooter) *Extended { |
| 371 | assert(f.isExtended()); |
| 372 | return @ptrFromInt(@intFromPtr(f) + @sizeOf(AllocFooter)); |
| 373 | } |
| 374 | |
| 375 | fn userMemory(f: *AllocFooter) []u8 { |
| 376 | const memory_addr = @intFromPtr(f) - allocOffset(f.userLen()); |
| 377 | assert(f.userAlign().check(memory_addr)); |
| 378 | const memory_ptr: [*]u8 = @ptrFromInt(memory_addr); |
| 379 | return memory_ptr[0..f.userLen()]; |
| 380 | } |
| 381 | |
| 382 | fn userLen(f: *AllocFooter) usize { |
| 383 | const len_int = @backingInt(f.data.len); |
| 384 | return if (len_int < Data.Len.extended_start) len_int else f.extended().len; |
| 385 | } |
| 386 | |
| 387 | fn userAlign(f: *AllocFooter) Alignment { |
| 388 | const high = (@backingInt(f.data.len) -| Data.Len.extended_start) << 2; |
| 389 | return @fromBackingInt(@intCast(high | f.data.alignment)); |
| 390 | } |
| 391 | |
| 392 | fn bucketPrev(f: *AllocFooter, b: *Bucket, s: *SafeAllocator) ?*AllocFooter { |
| 393 | if (f.isExtended()) return f.extended().container.bucket_prev; |
| 394 | return b.allocFooterBefore(s, Bucket.fillAt(s, f.userMemory().ptr), f.data.prev_extended); |
| 395 | } |
| 396 | |
| 397 | fn tracesPtr(f: *AllocFooter) [*]usize { |
| 398 | const off_footer = @divExact(@sizeOf(AllocFooter), @sizeOf(usize)); |
| 399 | const off_extended = @as(usize, @divExact(@sizeOf(Extended), @sizeOf(usize))) * |
| 400 | @intFromBool(f.isExtended()); |
| 401 | return @as([*]usize, @ptrCast(f))[off_footer + off_extended ..]; |
| 402 | } |
| 403 | |
| 404 | fn allocTrace(f: *AllocFooter, s: *SafeAllocator) []usize { |
| 405 | return f.tracesPtr()[0..s.stack_trace_size]; |
| 406 | } |
| 407 | |
| 408 | fn freeTrace(f: *AllocFooter, s: *SafeAllocator) []usize { |
| 409 | const trace_size = s.stack_trace_size; |
| 410 | return f.tracesPtr()[trace_size..][0..trace_size]; |
| 411 | } |
| 412 | |
| 413 | fn actualChecksum(f: *AllocFooter, s: *SafeAllocator) u32 { |
| 414 | if (f.isExtended()) { |
| 415 | const len = f.extended().len; |
| 416 | const addr: usize = if (s.isLarge(len, f.userAlign())) |
| 417 | @intFromPtr(f.extended().container.large_entry) |
| 418 | else |
| 419 | @intFromPtr(f.extended().container.bucket_prev); |
| 420 | |
| 421 | const len_bytes: [@sizeOf(usize)]u8 = @bitCast(len); |
| 422 | const container: [@sizeOf(usize)]u8 = @bitCast(addr); |
| 423 | const regular_bytes: [2]u8 = @bitCast(f.data); |
| 424 | const data_bytes = len_bytes ++ container ++ regular_bytes; |
| 425 | |
| 426 | return @truncate(std.hash.Wyhash.hash(@truncate(@intFromPtr(f)), &data_bytes)); |
| 427 | } |
| 428 | return @truncate(std.hash.int(@as(u16, @bitCast(f.data)) ^ @intFromPtr(f))); |
| 429 | } |
| 430 | |
| 431 | fn allocOffset(len: usize) usize { |
| 432 | return Alignment.of(AllocFooter).forward(len); |
| 433 | } |
| 434 | |
| 435 | fn allocAlign(a: Alignment) Alignment { |
| 436 | return a.max(.of(AllocFooter)); |
| 437 | } |
| 438 | |
| 439 | /// Assumes the footer is in a bucket allocation; all |
| 440 | /// large allocations require an extended header. |
| 441 | fn requiresExtended(len: usize, alignment: Alignment) bool { |
| 442 | return len >= Data.Len.extended_start or @backingInt(alignment) > math.maxInt(u2); |
| 443 | } |
| 444 | |
| 445 | fn lenBucket(s: *SafeAllocator, is_extended: bool) usize { |
| 446 | return Alignment.forward(.@"8", @sizeOf(AllocFooter) + |
| 447 | @as(usize, @sizeOf(Extended)) * @intFromBool(is_extended) + |
| 448 | s.stack_trace_size * @sizeOf(usize) * 2); |
| 449 | } |
| 450 | |
| 451 | fn lenLarge(s: *SafeAllocator) usize { |
| 452 | return @sizeOf(AllocFooter) + @sizeOf(Extended) + s.stack_trace_size * @sizeOf(usize); |
| 453 | } |
| 454 | |
| 455 | fn allocLenBucket(s: *SafeAllocator, len: usize, is_extended: bool) usize { |
| 456 | return allocOffset(len) + lenBucket(s, is_extended); |
| 457 | } |
| 458 | |
| 459 | fn allocLenLarge(s: *SafeAllocator, len: usize) usize { |
| 460 | return allocOffset(len) + lenLarge(s); |
| 461 | } |
| 462 | |
| 463 | fn allocOffsetOrOom(len: usize) error{OutOfMemory}!usize { |
| 464 | return alignForwardOrOom(.of(AllocFooter), len); |
| 465 | } |
| 466 | |
| 467 | fn allocLenBucketOrOom( |
| 468 | s: *SafeAllocator, |
| 469 | len: usize, |
| 470 | is_extended: bool, |
| 471 | ) error{OutOfMemory}!usize { |
| 472 | return addOrOom(try allocOffsetOrOom(len), lenBucket(s, is_extended)); |
| 473 | } |
| 474 | |
| 475 | fn of(user_memory: []u8) *AllocFooter { |
| 476 | // Avoid panicing now if `memory.ptr` is not correctly aligned since a more |
| 477 | // useful panic will be provided later by a mismatch or invalid footer. |
| 478 | const aligned_start = Alignment.backward(.of(AllocFooter), @intFromPtr(user_memory.ptr)); |
| 479 | return @ptrFromInt(aligned_start + allocOffset(user_memory.len)); |
| 480 | } |
| 481 | |
| 482 | fn startModify(f: *AllocFooter, m: Modify, s: *SafeAllocator, mem_fmt: FormatMemory) void { |
| 483 | const prev = @atomicRmw( |
| 484 | Modify, |
| 485 | &f.modify, |
| 486 | .Xchg, |
| 487 | .storedXor(m, &f.modify), |
| 488 | .monotonic, |
| 489 | ).storedXor(&f.modify); |
| 490 | |
| 491 | if (prev != .none) { |
| 492 | @branchHint(.cold); |
| 493 | const op_name = m.opName(); |
| 494 | switch (prev) { |
| 495 | .none => unreachable, |
| 496 | .resized, .remaped => panic( |
| 497 | \\{s} {s} of {f} |
| 498 | \\alloc: {f} |
| 499 | \\{s}: |
| 500 | // (panic stack trace) |
| 501 | , .{ |
| 502 | op_name, |
| 503 | prev.stateName(), |
| 504 | mem_fmt, |
| 505 | // The stack trace may have been overwritten, but at least give it a try |
| 506 | formatStackTrace(f.allocTrace(s)), |
| 507 | op_name, |
| 508 | }), |
| 509 | .freeing, .freed => { |
| 510 | if (prev == .freeing) { |
| 511 | // Wait for trace to become available |
| 512 | const complete: Modify = .storedXor(.freed, &f.modify); |
| 513 | while (@atomicLoad(Modify, &f.modify, .monotonic) != complete) {} |
| 514 | const b: *Bucket = .of(s, @ptrCast(f)); |
| 515 | b.alloc_count.fenceAcqRel(); |
| 516 | } |
| 517 | if (m == .freeing) { |
| 518 | panic( |
| 519 | \\double free of {f} |
| 520 | \\alloc: {f} |
| 521 | \\first free: {f} |
| 522 | \\second free: |
| 523 | // (panic stack trace) |
| 524 | , .{ |
| 525 | mem_fmt, |
| 526 | formatStackTrace(f.allocTrace(s)), |
| 527 | formatStackTrace(f.freeTrace(s)), |
| 528 | }); |
| 529 | } else { |
| 530 | panic( |
| 531 | \\{s} {s} of {f} |
| 532 | \\alloc: {f} |
| 533 | \\free: {f} |
| 534 | \\{s}: |
| 535 | // (panic stack trace) |
| 536 | , .{ |
| 537 | op_name, |
| 538 | prev.stateName(), |
| 539 | mem_fmt, |
| 540 | formatStackTrace(f.allocTrace(s)), |
| 541 | formatStackTrace(f.freeTrace(s)), |
| 542 | op_name, |
| 543 | }); |
| 544 | } |
| 545 | }, |
| 546 | _ => panic( |
| 547 | "{s} of invalid memory {f} or corrupted metadata", |
| 548 | .{ m.opName(), mem_fmt }, |
| 549 | ), |
| 550 | } |
| 551 | comptime unreachable; |
| 552 | } |
| 553 | |
| 554 | const expected_checksum = f.actualChecksum(s); |
| 555 | if (f.checksum ^ s.canary != expected_checksum) { |
| 556 | @branchHint(.cold); |
| 557 | const other_canary = f.checksum ^ expected_checksum; |
| 558 | panic( |
| 559 | "{s} of invalid memory {f}, corrupted metadata, or foreign allocation from canary 0x{x}", |
| 560 | .{ m.opName(), mem_fmt, other_canary }, |
| 561 | ); |
| 562 | } |
| 563 | |
| 564 | if (f.userLen() != mem_fmt.memory.len or f.userAlign() != mem_fmt.alignment) { |
| 565 | const op_name = m.opName(); |
| 566 | panic( |
| 567 | \\{s} of {f} mismatches allocation of {f} |
| 568 | \\alloc: {f} |
| 569 | \\{s}: |
| 570 | // (panic stack trace) |
| 571 | , .{ op_name, mem_fmt, FormatMemory{ |
| 572 | .memory = f.userMemory(), |
| 573 | .alignment = f.userAlign(), |
| 574 | }, formatStackTrace(f.allocTrace(s)), op_name }); |
| 575 | } |
| 576 | } |
| 577 | |
| 578 | /// It is the caller's responsibility to `.acquire` fence the respective `Bucket.alloc_count`. |
| 579 | fn populate( |
| 580 | memory: []align(@alignOf(AllocFooter)) u8, |
| 581 | len: usize, |
| 582 | alignment: Alignment, |
| 583 | ra: usize, |
| 584 | /// `true` for large allocations |
| 585 | is_extended: bool, |
| 586 | /// `false` for large allocations |
| 587 | prev_extended: bool, |
| 588 | container: Extended.Container, |
| 589 | s: *SafeAllocator, |
| 590 | ) *AllocFooter { |
| 591 | const footer: *AllocFooter = @ptrCast(@alignCast(memory[allocOffset(len)..].ptr)); |
| 592 | |
| 593 | if (!is_extended) { |
| 594 | footer.data = .{ |
| 595 | .len = @fromBackingInt(@intCast(len)), |
| 596 | .alignment = @intCast(@backingInt(alignment)), |
| 597 | .prev_extended = prev_extended, |
| 598 | }; |
| 599 | assert(!footer.isExtended()); |
| 600 | } else { |
| 601 | footer.data = .{ |
| 602 | .len = @fromBackingInt(@intCast(Data.Len.extended_start + (@backingInt(alignment) >> 2))), |
| 603 | .alignment = @truncate(@backingInt(alignment)), |
| 604 | .prev_extended = prev_extended, |
| 605 | }; |
| 606 | assert(footer.isExtended()); |
| 607 | footer.extended().* = .{ |
| 608 | .len = len, |
| 609 | .container = container, |
| 610 | }; |
| 611 | } |
| 612 | |
| 613 | captureStackTrace(footer.allocTrace(s), ra); |
| 614 | footer.checksum = footer.actualChecksum(s) ^ s.canary; |
| 615 | footer.modify.setNone(); |
| 616 | |
| 617 | return footer; |
| 618 | } |
| 619 | }; |
| 620 | |
| 621 | pub fn init( |
| 622 | /// Must be thread-safe for this allocator to be thread-safe |
| 623 | backing: mem.Allocator, |
| 624 | options: Options, |
| 625 | ) SafeAllocator { |
| 626 | assert(options.block_size_log2 >= 8); |
| 627 | assert(options.bucket_size_log2 >= 8); |
| 628 | |
| 629 | const allocs_entry_count = (@as(usize, 1) << options.block_size_log2) / @sizeOf(usize); |
| 630 | return .{ |
| 631 | .backing = backing, |
| 632 | .threads = @splat(.{ |
| 633 | .mutex = .unlocked, |
| 634 | .fill_bucket = null, |
| 635 | .free_entry = null, |
| 636 | .allocs_next = allocs_entry_count, |
| 637 | .allocs_first = null, |
| 638 | }), |
| 639 | |
| 640 | .bucket_size_log2 = options.bucket_size_log2, |
| 641 | .block_size_log2 = options.block_size_log2, |
| 642 | .stack_trace_size = options.stack_trace_frames + |
| 643 | @intFromBool(options.stack_trace_frames != 0), |
| 644 | .allocs_entry_count = allocs_entry_count, |
| 645 | .large_alloc_threshold = (@as(usize, 1) << options.bucket_size_log2) * 3 / 4, |
| 646 | |
| 647 | .canary = options.canary, |
| 648 | .check_write_after_free = options.check_write_after_free, |
| 649 | }; |
| 650 | } |
| 651 | |
| 652 | /// Returns the number of leaks |
| 653 | pub fn deinit(s: *SafeAllocator) usize { |
| 654 | return s.deinitLog(true); |
| 655 | } |
| 656 | |
| 657 | /// Same as `deinit`, expect if `log` is `false`, it will not log leaks. |
| 658 | pub fn deinitLog(s: *SafeAllocator, log: bool) usize { |
| 659 | var leaks: usize = 0; |
| 660 | const thread_count = @atomicRmw(usize, &n_threads, .Or, 0, .monotonic); |
| 661 | for (s.threads[0..@max(1, thread_count)]) |*t| { |
| 662 | assert(t.mutex == .unlocked); // use of allocator during `deinit` |
| 663 | |
| 664 | var maybe_allocs = t.allocs_first; |
| 665 | var n_entries = t.allocs_next; |
| 666 | while (maybe_allocs) |allocs| { |
| 667 | for (allocs.entries(s)[0..n_entries]) |*ent| { |
| 668 | switch (ent.kind) { |
| 669 | .free => { |
| 670 | @branchHint(.likely); |
| 671 | }, |
| 672 | .bucket => leaks += s.deinitLeakedBucket(ent.toBucket(), log), |
| 673 | .large_alloc => { |
| 674 | leaks += 1; |
| 675 | s.deinitLargeAlloc(ent.toLargeAlloc(), log); |
| 676 | }, |
| 677 | } |
| 678 | } |
| 679 | maybe_allocs = allocs.next; |
| 680 | n_entries = s.allocs_entry_count; |
| 681 | s.backing.rawFree(@ptrCast(allocs.usizes(s)), .of(usize), 0); |
| 682 | } |
| 683 | } |
| 684 | return leaks; |
| 685 | } |
| 686 | |
| 687 | /// Returns the true count of leaks |
| 688 | fn deinitLeakedBucket(s: *SafeAllocator, b: *Bucket, log: bool) usize { |
| 689 | var leaks: usize = 0; |
| 690 | |
| 691 | const expected = @atomicLoad(Bucket.AllocCount, &b.alloc_count, .acquire); |
| 692 | if (expected.n == 0) assert(expected.filling); |
| 693 | |
| 694 | var footer = b.lastAlloc(s, b.fill).?; |
| 695 | while (true) { |
| 696 | const modify = @atomicRmw( |
| 697 | AllocFooter.Modify, |
| 698 | &footer.modify, |
| 699 | .Xchg, |
| 700 | undefined, |
| 701 | .monotonic, |
| 702 | ).storedXor(&footer.modify); |
| 703 | |
| 704 | const bad_modify = modify != .none and modify != .freed; |
| 705 | if (bad_modify or footer.actualChecksum(s) != footer.checksum ^ s.canary) { |
| 706 | panic("corrupted footer metadata in bucket at *{x}", .{@intFromPtr(&footer)}); |
| 707 | } |
| 708 | |
| 709 | switch (modify) { |
| 710 | .none => { |
| 711 | leaks += 1; |
| 712 | if (log) scoped_log.err("leaked {f} allocated at: {f}", .{ FormatMemory{ |
| 713 | .memory = footer.userMemory(), |
| 714 | .alignment = footer.userAlign(), |
| 715 | }, formatStackTrace(footer.allocTrace(s)) }); |
| 716 | }, |
| 717 | .freed => s.checkFreed(footer), |
| 718 | else => unreachable, |
| 719 | } |
| 720 | |
| 721 | footer = footer.bucketPrev(b, s) orelse break; |
| 722 | } |
| 723 | s.backing.rawFree(b.bytes(s), @fromBackingInt(@intCast(s.bucket_size_log2)), 0); |
| 724 | |
| 725 | assert(leaks == expected.n); |
| 726 | return leaks; |
| 727 | } |
| 728 | |
| 729 | fn deinitLargeAlloc(s: *SafeAllocator, footer: *AllocFooter, log: bool) void { |
| 730 | const modify = footer.modify.storedXor(&footer.modify); |
| 731 | if (modify != .none or footer.checksum ^ s.canary != footer.actualChecksum(s)) { |
| 732 | panic("corrupted footer metadata at *{x}", .{@intFromPtr(&footer)}); |
| 733 | } |
| 734 | |
| 735 | const memory = footer.userMemory(); |
| 736 | if (log) scoped_log.err("leaked {f} allocated at {f}", .{ FormatMemory{ |
| 737 | .memory = memory, |
| 738 | .alignment = footer.userAlign(), |
| 739 | }, formatStackTrace(footer.allocTrace(s)) }); |
| 740 | |
| 741 | s.backing.rawFree( |
| 742 | memory.ptr[0..AllocFooter.allocLenLarge(s, memory.len)], |
| 743 | AllocFooter.allocAlign(footer.userAlign()), |
| 744 | 0, |
| 745 | ); |
| 746 | } |
| 747 | |
| 748 | /// Returned allocator is thread-safe |
| 749 | pub fn allocator(s: *SafeAllocator) mem.Allocator { |
| 750 | return .{ .ptr = s, .vtable = &vtable }; |
| 751 | } |
| 752 | |
| 753 | fn acquireThread(s: *SafeAllocator) *Thread { |
| 754 | while (true) { |
| 755 | const t = &s.threads[thread_index]; |
| 756 | if (t.mutex.tryLock()) { |
| 757 | @branchHint(.likely); |
| 758 | return t; |
| 759 | } |
| 760 | |
| 761 | var max = @atomicLoad(usize, &n_threads, .unordered); |
| 762 | if (max == 0) { |
| 763 | @branchHint(.unlikely); |
| 764 | max = @min(std.Thread.getCpuCount() catch s.threads.len, s.threads.len); |
| 765 | max = @cmpxchgStrong(usize, &n_threads, 0, max, .monotonic, .monotonic) orelse max; |
| 766 | } |
| 767 | |
| 768 | thread_index += 1; |
| 769 | // thread_index may be greater than max if the zero is returned by getCpuCount |
| 770 | thread_index *= @intFromBool(thread_index < max); |
| 771 | } |
| 772 | } |
| 773 | |
| 774 | fn alignForwardOrOom(a: Alignment, addr: usize) error{OutOfMemory}!usize { |
| 775 | const x = a.toByteUnits() - 1; |
| 776 | return try addOrOom(addr, x) & ~x; |
| 777 | } |
| 778 | |
| 779 | fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize { |
| 780 | return math.add(usize, a, b) catch error.OutOfMemory; |
| 781 | } |
| 782 | |
| 783 | fn isLarge(s: *SafeAllocator, len: usize, alignment: Alignment) bool { |
| 784 | const max_align_waste = alignment.toByteUnits() - 1; |
| 785 | const max_use = max_align_waste + AllocFooter.allocLenBucket(s, len, true); |
| 786 | return max_use >= s.large_alloc_threshold; |
| 787 | } |
| 788 | |
| 789 | fn isLargeOrOom(s: *SafeAllocator, len: usize, alignment: Alignment) error{OutOfMemory}!bool { |
| 790 | const max_align_waste = alignment.toByteUnits() - 1; |
| 791 | const max_use = try addOrOom(max_align_waste, try AllocFooter.allocLenBucketOrOom(s, len, true)); |
| 792 | return max_use >= s.large_alloc_threshold; |
| 793 | } |
| 794 | |
| 795 | fn newAllocEntry(s: *SafeAllocator, t: *Thread, ra: usize) error{OutOfMemory}!*Allocs.Entry { |
| 796 | if (t.free_entry) |ent| { |
| 797 | @branchHint(.likely); |
| 798 | t.free_entry = ent.toFree(); |
| 799 | return ent; |
| 800 | } |
| 801 | |
| 802 | if (s.allocs_entry_count - t.allocs_next != 0) { |
| 803 | @branchHint(.likely); |
| 804 | const ent = &t.allocs_first.?.entries(s)[t.allocs_next]; |
| 805 | t.allocs_next += 1; |
| 806 | return ent; |
| 807 | } |
| 808 | |
| 809 | const new_segment: *Allocs = @ptrCast(@alignCast(s.backing.rawAlloc( |
| 810 | (1 + s.allocs_entry_count) * @sizeOf(usize), |
| 811 | .of(usize), |
| 812 | ra, |
| 813 | ) orelse return error.OutOfMemory)); |
| 814 | new_segment.next = t.allocs_first; |
| 815 | t.allocs_first = new_segment; |
| 816 | t.allocs_next = 1; |
| 817 | return &new_segment.entries(s)[0]; |
| 818 | } |
| 819 | |
| 820 | fn freeAllocEntry(t: *Thread, ent: *Allocs.Entry) void { |
| 821 | ent.* = .fromFree(t.free_entry); |
| 822 | t.free_entry = ent; |
| 823 | } |
| 824 | |
| 825 | fn overwriteFreed(s: *SafeAllocator, bytes: []u8) void { |
| 826 | if (!s.check_write_after_free) return; |
| 827 | // 0x55 is used so that undefined writes of 0xaa are still caught. Another option would be a |
| 828 | // stream of random bytes seeded by the address, however that makes debugging reads after frees |
| 829 | // more difficult and has a performance penalty and so is not worth catching slightly more |
| 830 | // writes after frees. |
| 831 | @memset(bytes, 0x55); |
| 832 | } |
| 833 | |
| 834 | /// Returns the first address of a write after free |
| 835 | fn checkFreed(s: *SafeAllocator, footer: *AllocFooter) void { |
| 836 | if (!s.check_write_after_free) return; |
| 837 | const memory = footer.userMemory(); |
| 838 | for (memory) |*b| if (b.* != 0x55) { |
| 839 | panic( |
| 840 | \\write after free at *{x} |
| 841 | \\original alloc of {f}: {f} |
| 842 | \\free: {f} |
| 843 | \\stack trace: |
| 844 | // (panic stack trace) |
| 845 | , .{ |
| 846 | @intFromPtr(b), |
| 847 | FormatMemory{ .memory = memory, .alignment = footer.userAlign() }, |
| 848 | formatStackTrace(footer.allocTrace(s)), |
| 849 | formatStackTrace(footer.freeTrace(s)), |
| 850 | }); |
| 851 | }; |
| 852 | } |
| 853 | |
| 854 | const FormatMemory = struct { |
| 855 | memory: []const u8, |
| 856 | alignment: Alignment, |
| 857 | |
| 858 | pub fn format(m: FormatMemory, w: *std.Io.Writer) std.Io.Writer.Error!void { |
| 859 | return w.print( |
| 860 | "[addr: {x}, len: {} (0x{x}) align: {}]", |
| 861 | .{ @intFromPtr(m.memory.ptr), m.memory.len, m.memory.len, m.alignment.toByteUnits() }, |
| 862 | ); |
| 863 | } |
| 864 | }; |
| 865 | |
| 866 | /// The first element stores the length of the stack trace including skipped frames. |
| 867 | /// The remaining elements store the return addresses. |
| 868 | fn captureStackTrace(trace_buf: []usize, ra: usize) void { |
| 869 | if (trace_buf.len == 0) return; |
| 870 | |
| 871 | if (ra == 0) { // No return address provided |
| 872 | @branchHint(.unlikely); |
| 873 | trace_buf[0] = 0; |
| 874 | return; |
| 875 | } |
| 876 | |
| 877 | const t = std.debug.captureCurrentStackTrace(.{ .first_address = ra }, trace_buf[1..]); |
| 878 | const skipped = @backingInt(t.skipped) * |
| 879 | @intFromBool(t.return_addresses.len == trace_buf[1..].len); |
| 880 | trace_buf[0] = t.return_addresses.len +| skipped; |
| 881 | } |
| 882 | |
| 883 | fn formatStackTrace(trace_buf: []usize) std.debug.FormatStackTrace { |
| 884 | return .{ |
| 885 | .stack_trace = if (trace_buf.len != 0) trace: { |
| 886 | const frames = trace_buf[0]; |
| 887 | const addrs = trace_buf[1..]; |
| 888 | break :trace .{ |
| 889 | .return_addresses = addrs[0..@min(frames, addrs.len)], |
| 890 | .skipped = switch (frames) { |
| 891 | else => @fromBackingInt(@intCast(frames -| addrs.len)), |
| 892 | 0, math.maxInt(usize) => .unknown, |
| 893 | }, |
| 894 | }; |
| 895 | } else .{ |
| 896 | .return_addresses = &.{}, |
| 897 | .skipped = .unknown, |
| 898 | }, |
| 899 | .terminal_mode = std.log.terminalMode(), |
| 900 | }; |
| 901 | } |
| 902 | |
| 903 | /// If this fails, future allocations to the bucket are illegal |
| 904 | fn allocBucket( |
| 905 | s: *SafeAllocator, |
| 906 | t: *Thread, |
| 907 | b: *Bucket, |
| 908 | len: usize, |
| 909 | alignment: Alignment, |
| 910 | ra: usize, |
| 911 | ) ?[*]u8 { |
| 912 | const fill = &b.fill; |
| 913 | const is_extended = AllocFooter.requiresExtended(len, alignment); |
| 914 | const alloc_len: u32 = @intCast(AllocFooter.allocLenBucket(s, len, is_extended)); |
| 915 | const alloc_align = AllocFooter.allocAlign(alignment); |
| 916 | |
| 917 | var prev_fill = @atomicLoad(Bucket.Fill, fill, .monotonic); |
| 918 | var start: u32 = undefined; |
| 919 | var end: u32 = undefined; |
| 920 | while (true) { |
| 921 | start = @intCast(alloc_align.forward(prev_fill.at)); |
| 922 | end = start + alloc_len; |
| 923 | |
| 924 | if (end > s.bucketSize()) { |
| 925 | @branchHint(.unlikely); |
| 926 | |
| 927 | const prev_count = @atomicRmw( |
| 928 | Bucket.AllocCount, |
| 929 | &b.alloc_count, |
| 930 | .Sub, |
| 931 | .{ .filling = true, .n = 0 }, |
| 932 | .acq_rel, |
| 933 | ); |
| 934 | assert(prev_count.filling); |
| 935 | |
| 936 | if (prev_count.n == 0) { |
| 937 | @branchHint(.unlikely); |
| 938 | freeAllocEntry(t, b.entry); |
| 939 | b.check(s); |
| 940 | s.backing.rawFree(b.bytes(s), @fromBackingInt(@intCast(s.bucket_size_log2)), ra); |
| 941 | } |
| 942 | |
| 943 | return null; |
| 944 | } |
| 945 | |
| 946 | prev_fill = @cmpxchgWeak( |
| 947 | Bucket.Fill, |
| 948 | fill, |
| 949 | prev_fill, |
| 950 | .{ .at = @intCast(end), .last_is_extended = is_extended }, |
| 951 | .monotonic, |
| 952 | .monotonic, |
| 953 | ) orelse { |
| 954 | @branchHint(.likely); |
| 955 | break; |
| 956 | }; |
| 957 | // b.fill was changed during a resize (or a sporadic cmpxchgWeak failure) |
| 958 | } |
| 959 | |
| 960 | const memory = b.bytes(s)[start..end]; |
| 961 | _ = AllocFooter.populate( |
| 962 | @alignCast(memory), |
| 963 | len, |
| 964 | alignment, |
| 965 | ra, |
| 966 | is_extended, |
| 967 | prev_fill.last_is_extended, |
| 968 | .{ .bucket_prev = b.lastAlloc(s, prev_fill) }, |
| 969 | s, |
| 970 | ); |
| 971 | |
| 972 | assert(@atomicRmw( |
| 973 | Bucket.AllocCount, |
| 974 | &b.alloc_count, |
| 975 | .Add, |
| 976 | .{ .filling = false, .n = 1 }, |
| 977 | .acq_rel, |
| 978 | ).filling); |
| 979 | |
| 980 | return memory.ptr; |
| 981 | } |
| 982 | |
| 983 | fn growingResizeBucket( |
| 984 | s: *SafeAllocator, |
| 985 | f: *AllocFooter, |
| 986 | memory: []const u8, |
| 987 | alignment: Alignment, |
| 988 | new_len: usize, |
| 989 | ra: usize, |
| 990 | ) bool { |
| 991 | assert(new_len >= memory.len); |
| 992 | return s.advanceBucketAlloc(f, Bucket.fillAt(s, memory.ptr), false, alignment, new_len, ra); |
| 993 | } |
| 994 | |
| 995 | fn advanceBucketAlloc( |
| 996 | s: *SafeAllocator, |
| 997 | old: *AllocFooter, |
| 998 | new_start: u32, |
| 999 | start_moved: bool, |
| 1000 | alignment: Alignment, |
| 1001 | new_len: usize, |
| 1002 | ra: usize, |
| 1003 | ) bool { |
| 1004 | assert(AllocFooter.allocAlign(alignment).check(new_start)); |
| 1005 | const b: *Bucket = .of(s, @ptrCast(old)); |
| 1006 | |
| 1007 | const old_is_extended = old.isExtended(); |
| 1008 | const old_footer_len = AllocFooter.lenBucket(s, old_is_extended); |
| 1009 | const old_fill: u32 = @intCast(Bucket.fillAt(s, @ptrCast(old)) + old_footer_len); |
| 1010 | |
| 1011 | const new_is_extended = old_is_extended or start_moved or |
| 1012 | AllocFooter.requiresExtended(new_len, alignment); |
| 1013 | const new_footer_len = AllocFooter.lenBucket(s, new_is_extended); |
| 1014 | const new_fill: u32 = @intCast(new_start + AllocFooter.allocOffset(new_len) + new_footer_len); |
| 1015 | |
| 1016 | assert(old_fill <= new_fill); |
| 1017 | if (new_fill > s.bucketSize()) { |
| 1018 | return false; |
| 1019 | } |
| 1020 | |
| 1021 | if (old_fill == new_fill or @cmpxchgStrong( |
| 1022 | Bucket.Fill, |
| 1023 | &b.fill, |
| 1024 | .{ .last_is_extended = old_is_extended, .at = @intCast(old_fill) }, |
| 1025 | .{ .last_is_extended = new_is_extended, .at = @intCast(new_fill) }, |
| 1026 | .monotonic, |
| 1027 | .monotonic, |
| 1028 | ) != null) { |
| 1029 | return false; |
| 1030 | } |
| 1031 | |
| 1032 | _ = AllocFooter.populate( |
| 1033 | @alignCast(b.bytes(s)[new_start..new_fill]), |
| 1034 | new_len, |
| 1035 | alignment, |
| 1036 | ra, |
| 1037 | new_is_extended, |
| 1038 | old.data.prev_extended, |
| 1039 | .{ .bucket_prev = old.bucketPrev(b, s) }, |
| 1040 | s, |
| 1041 | ); |
| 1042 | b.alloc_count.fenceAcqRel(); |
| 1043 | return true; |
| 1044 | } |
| 1045 | |
| 1046 | const vtable: mem.Allocator.VTable = .{ |
| 1047 | .alloc = alloc, |
| 1048 | .free = free, |
| 1049 | .resize = resize, |
| 1050 | .remap = remap, |
| 1051 | }; |
| 1052 | |
| 1053 | fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, ra: usize) ?[*]u8 { |
| 1054 | assert(len != 0); |
| 1055 | |
| 1056 | const s: *SafeAllocator = @ptrCast(@alignCast(ctx)); |
| 1057 | const t = s.acquireThread(); |
| 1058 | defer t.mutex.unlock(); |
| 1059 | |
| 1060 | if (s.isLargeOrOom(len, alignment) catch return null) { |
| 1061 | @branchHint(.unlikely); |
| 1062 | |
| 1063 | const entry = s.newAllocEntry(t, ra) catch return null; |
| 1064 | const alloc_len = AllocFooter.allocLenLarge(s, len); |
| 1065 | const alloc_align = AllocFooter.allocAlign(alignment); |
| 1066 | const alloc_ptr = s.backing.rawAlloc(alloc_len, alloc_align, ra) orelse { |
| 1067 | freeAllocEntry(t, entry); |
| 1068 | return null; |
| 1069 | }; |
| 1070 | |
| 1071 | const footer = AllocFooter.populate( |
| 1072 | @alignCast(alloc_ptr[0..alloc_len]), |
| 1073 | len, |
| 1074 | alignment, |
| 1075 | ra, |
| 1076 | true, |
| 1077 | false, |
| 1078 | .{ .large_entry = entry }, |
| 1079 | s, |
| 1080 | ); |
| 1081 | entry.* = .fromLargeAlloc(footer); |
| 1082 | |
| 1083 | return alloc_ptr; |
| 1084 | } |
| 1085 | |
| 1086 | if (t.fill_bucket) |bucket| { |
| 1087 | @branchHint(.likely); |
| 1088 | if (s.allocBucket(t, bucket, len, alignment, ra)) |ptr| { |
| 1089 | @branchHint(.likely); |
| 1090 | return ptr; |
| 1091 | } |
| 1092 | } |
| 1093 | t.fill_bucket = null; // In case of OOM below, this bucket will still be unusable for future |
| 1094 | // allocations. |
| 1095 | |
| 1096 | const entry = s.newAllocEntry(t, ra) catch return null; |
| 1097 | const bucket: *Bucket = @ptrCast(@alignCast(s.backing.rawAlloc( |
| 1098 | s.bucketSize(), |
| 1099 | @fromBackingInt(@intCast(s.bucket_size_log2)), |
| 1100 | ra, |
| 1101 | ) orelse { |
| 1102 | freeAllocEntry(t, entry); |
| 1103 | return null; |
| 1104 | })); |
| 1105 | bucket.* = .{ |
| 1106 | .entry = entry, |
| 1107 | // No atomic stores necessary because this thread is the |
| 1108 | // first to atomically update these below in allocBucket. |
| 1109 | .alloc_count = .{ .filling = true, .n = 0 }, |
| 1110 | .fill = .{ .at = @sizeOf(Bucket), .last_is_extended = false }, |
| 1111 | }; |
| 1112 | entry.* = .fromBucket(bucket); |
| 1113 | |
| 1114 | t.fill_bucket = bucket; |
| 1115 | return s.allocBucket(t, bucket, len, alignment, ra); |
| 1116 | } |
| 1117 | |
| 1118 | fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, ra: usize) void { |
| 1119 | const s: *SafeAllocator = @ptrCast(@alignCast(ctx)); |
| 1120 | const f: *AllocFooter = .of(memory); |
| 1121 | f.startModify(.freeing, s, .{ .memory = memory, .alignment = alignment }); |
| 1122 | |
| 1123 | if (s.isLarge(memory.len, alignment)) { |
| 1124 | @branchHint(.unlikely); |
| 1125 | |
| 1126 | const t = s.acquireThread(); |
| 1127 | freeAllocEntry(t, f.extended().container.large_entry); |
| 1128 | t.mutex.unlock(); |
| 1129 | s.backing.rawFree( |
| 1130 | memory.ptr[0..AllocFooter.allocLenLarge(s, memory.len)], |
| 1131 | AllocFooter.allocAlign(alignment), |
| 1132 | ra, |
| 1133 | ); |
| 1134 | return; |
| 1135 | } |
| 1136 | |
| 1137 | const b: *Bucket = .of(s, memory.ptr); |
| 1138 | s.overwriteFreed(memory); |
| 1139 | captureStackTrace(f.freeTrace(s), ra); |
| 1140 | |
| 1141 | // Fence the alloc count before setting `f.modify` to `.freed`. |
| 1142 | // This way, if another thread is waiting for the trace to become |
| 1143 | // available, it will not be racing with us to see this `.release`. |
| 1144 | // |
| 1145 | // The below alloc count update can not be moved up here instead |
| 1146 | // since that would allow another thread to see the `.freeing` state. |
| 1147 | b.alloc_count.fenceAcqRel(); |
| 1148 | |
| 1149 | // If this result is different than .freeing, then some other thread |
| 1150 | // is in the process of panicing. So, just ignore it. (This is also |
| 1151 | // the reasoning for several other places.) |
| 1152 | _ = @atomicRmw( |
| 1153 | AllocFooter.Modify, |
| 1154 | &f.modify, |
| 1155 | .Xchg, |
| 1156 | .storedXor(.freed, &f.modify), |
| 1157 | .monotonic, |
| 1158 | ); |
| 1159 | |
| 1160 | const prev_count = @atomicRmw( |
| 1161 | Bucket.AllocCount, |
| 1162 | &b.alloc_count, |
| 1163 | .Sub, |
| 1164 | .{ .filling = false, .n = 1 }, |
| 1165 | .acq_rel, |
| 1166 | ); |
| 1167 | |
| 1168 | if (prev_count.n - 1 == 0 and !prev_count.filling) { |
| 1169 | @branchHint(.unlikely); |
| 1170 | const t = s.acquireThread(); |
| 1171 | freeAllocEntry(t, b.entry); |
| 1172 | t.mutex.unlock(); |
| 1173 | b.check(s); |
| 1174 | s.backing.rawFree(b.bytes(s), @fromBackingInt(@intCast(s.bucket_size_log2)), ra); |
| 1175 | } |
| 1176 | } |
| 1177 | |
| 1178 | fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) bool { |
| 1179 | assert(new_len != 0); |
| 1180 | |
| 1181 | const s: *SafeAllocator = @ptrCast(@alignCast(ctx)); |
| 1182 | const f: *AllocFooter = .of(memory); |
| 1183 | f.startModify(.resized, s, .{ .memory = memory, .alignment = alignment }); |
| 1184 | |
| 1185 | // Check that the allocation is not moving between a bucket and large allocation. This is |
| 1186 | // done after the above so that it is still checked that valid memory is passed and there |
| 1187 | // is no double modify. |
| 1188 | const from_large_alloc = s.isLarge(memory.len, alignment); |
| 1189 | const to_large_alloc = s.isLargeOrOom(new_len, alignment) catch { |
| 1190 | f.modify.setNone(); |
| 1191 | return false; |
| 1192 | }; |
| 1193 | if (from_large_alloc != to_large_alloc) { |
| 1194 | @branchHint(.unlikely); |
| 1195 | f.modify.setNone(); |
| 1196 | return false; |
| 1197 | } |
| 1198 | |
| 1199 | if (from_large_alloc) { |
| 1200 | @branchHint(.unlikely); |
| 1201 | |
| 1202 | const entry = f.extended().container.large_entry; |
| 1203 | const new_alloc_len = AllocFooter.allocLenLarge(s, new_len); |
| 1204 | if (!s.backing.rawResize( |
| 1205 | memory.ptr[0..AllocFooter.allocLenLarge(s, memory.len)], |
| 1206 | AllocFooter.allocAlign(alignment), |
| 1207 | new_alloc_len, |
| 1208 | ra, |
| 1209 | )) { |
| 1210 | f.modify.setNone(); |
| 1211 | return false; |
| 1212 | } |
| 1213 | |
| 1214 | const new_footer = AllocFooter.populate( |
| 1215 | @alignCast(memory.ptr[0..new_alloc_len]), |
| 1216 | new_len, |
| 1217 | alignment, |
| 1218 | ra, |
| 1219 | true, |
| 1220 | false, |
| 1221 | .{ .large_entry = entry }, |
| 1222 | s, |
| 1223 | ); |
| 1224 | assert(entry.kind == .large_alloc); |
| 1225 | entry.* = .fromLargeAlloc(new_footer); |
| 1226 | return true; |
| 1227 | } |
| 1228 | |
| 1229 | if (new_len < memory.len) { |
| 1230 | // Resize shrinks are disallowed in all cases since the linked list would be broken. Even |
| 1231 | // if this footer is the final one, the fill value would need decreased which would allow |
| 1232 | // memory to be reused. |
| 1233 | f.modify.setNone(); |
| 1234 | return false; |
| 1235 | } |
| 1236 | |
| 1237 | if (s.growingResizeBucket(f, memory, alignment, new_len, ra)) { |
| 1238 | @branchHint(.likely); |
| 1239 | return true; |
| 1240 | } else { |
| 1241 | f.modify.setNone(); |
| 1242 | return false; |
| 1243 | } |
| 1244 | } |
| 1245 | |
| 1246 | fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) ?[*]u8 { |
| 1247 | assert(new_len != 0); |
| 1248 | |
| 1249 | const s: *SafeAllocator = @ptrCast(@alignCast(ctx)); |
| 1250 | const f: *AllocFooter = .of(memory); |
| 1251 | f.startModify(.remaped, s, .{ .memory = memory, .alignment = alignment }); |
| 1252 | |
| 1253 | // Check that the allocation is not moving between a bucket and large allocation. This is |
| 1254 | // done after the above so that it is still checked that valid memory is passed and there |
| 1255 | // is no double modify. |
| 1256 | const from_large_alloc = s.isLarge(memory.len, alignment); |
| 1257 | const to_large_alloc = s.isLargeOrOom(new_len, alignment) catch { |
| 1258 | f.modify.setNone(); |
| 1259 | return null; |
| 1260 | }; |
| 1261 | if (from_large_alloc != to_large_alloc) { |
| 1262 | @branchHint(.unlikely); |
| 1263 | f.modify.setNone(); |
| 1264 | return null; |
| 1265 | } |
| 1266 | |
| 1267 | if (from_large_alloc) { |
| 1268 | @branchHint(.unlikely); |
| 1269 | |
| 1270 | const entry = f.extended().container.large_entry; |
| 1271 | const new_alloc_len = AllocFooter.allocLenLarge(s, new_len); |
| 1272 | const new_memory = s.backing.rawRemap( |
| 1273 | memory.ptr[0..AllocFooter.allocLenLarge(s, memory.len)], |
| 1274 | AllocFooter.allocAlign(alignment), |
| 1275 | new_alloc_len, |
| 1276 | ra, |
| 1277 | ) orelse { |
| 1278 | f.modify.setNone(); |
| 1279 | return null; |
| 1280 | }; |
| 1281 | |
| 1282 | const new_footer = AllocFooter.populate( |
| 1283 | @alignCast(new_memory[0..new_alloc_len]), |
| 1284 | new_len, |
| 1285 | alignment, |
| 1286 | ra, |
| 1287 | true, |
| 1288 | false, |
| 1289 | .{ .large_entry = entry }, |
| 1290 | s, |
| 1291 | ); |
| 1292 | assert(entry.kind == .large_alloc); |
| 1293 | entry.* = .fromLargeAlloc(new_footer); |
| 1294 | return new_memory; |
| 1295 | } |
| 1296 | |
| 1297 | if (new_len < memory.len) { |
| 1298 | // Move the allocation forward to avoid bucket reuse |
| 1299 | |
| 1300 | const fixed_start = Bucket.fillAt(s, @ptrCast(f)) - AllocFooter.allocOffset(new_len); |
| 1301 | const moved_start = alignment.forward(fixed_start); |
| 1302 | if (moved_start != fixed_start or !f.isExtended()) { |
| 1303 | @branchHint(.unlikely); |
| 1304 | // For `moved_start != fixed_start`: the footer needs moved forward as well to |
| 1305 | // maintain the correct allocOffset. |
| 1306 | // |
| 1307 | // For `!f.isExtended()`: since the memory will no longer be directly after the |
| 1308 | // previous footer, the footer needs promoted to an extended one to encode the |
| 1309 | // location of the previous footer. |
| 1310 | if (!s.advanceBucketAlloc(f, @intCast(moved_start), true, alignment, new_len, ra)) { |
| 1311 | @branchHint(.unlikely); |
| 1312 | f.modify.setNone(); |
| 1313 | return null; |
| 1314 | } |
| 1315 | const new_memory = Bucket.bytes(.of(s, @ptrCast(f)), s)[moved_start..][0..new_len]; |
| 1316 | @memmove(new_memory, memory[0..new_memory.len]); |
| 1317 | return new_memory.ptr; |
| 1318 | } |
| 1319 | |
| 1320 | // The footer can be modified in place |
| 1321 | const b: *Bucket = .of(s, @ptrCast(f)); |
| 1322 | f.extended().len = new_len; |
| 1323 | f.checksum = f.actualChecksum(s) ^ s.canary; |
| 1324 | captureStackTrace(f.allocTrace(s), ra); |
| 1325 | |
| 1326 | f.modify.setNone(); |
| 1327 | b.alloc_count.fenceAcqRel(); |
| 1328 | |
| 1329 | const new_memory = f.userMemory(); |
| 1330 | @memmove(new_memory, memory[0..new_memory.len]); |
| 1331 | return new_memory.ptr; |
| 1332 | } |
| 1333 | |
| 1334 | if (s.growingResizeBucket(f, memory, alignment, new_len, ra)) { |
| 1335 | @branchHint(.likely); |
| 1336 | return memory.ptr; |
| 1337 | } else { |
| 1338 | f.modify.setNone(); |
| 1339 | return null; |
| 1340 | } |
| 1341 | } |
| 1342 | |
| 1343 | const Smith = std.testing.Smith; |
| 1344 | |
| 1345 | /// Shared between single-threaded and multi-threaded fuzzing. |
| 1346 | const fuzz_probs = struct { |
| 1347 | const alignment: []const Smith.Weight = &.{ |
| 1348 | .rangeAtMost(Alignment, .@"1", .@"16", 32), // ~75% |
| 1349 | .rangeAtMost(Alignment, .@"16", @fromBackingInt(@intCast(@bitSizeOf(usize) - 1)), 1), |
| 1350 | .value(Alignment, @fromBackingInt(@intCast(@bitSizeOf(usize) - 1)), 32), // More likely overflow cases |
| 1351 | }; |
| 1352 | |
| 1353 | const eos: []const Smith.Weight = &.{ |
| 1354 | // Very high false weight so that expanding allocation tables, OOM cases, |
| 1355 | // and multi-threaded consumer-producer cases get tested thoroughly. |
| 1356 | .value(bool, false, 255), |
| 1357 | .value(bool, true, 1), |
| 1358 | }; |
| 1359 | |
| 1360 | fn generateOptions(smith: *Smith) Options { |
| 1361 | @disableInstrumentation(); |
| 1362 | |
| 1363 | const size_log2_weights: []const Smith.Weight = &.{ |
| 1364 | .value(u5, 8, 1024), // 8x odds of below |
| 1365 | .rangeAtMost(u5, 8, 16, 16), |
| 1366 | .rangeAtMost(u5, 17, 31, 1), // 1/32 odds of above since these just OOM with the fixed buffer |
| 1367 | }; |
| 1368 | return .{ |
| 1369 | .stack_trace_frames = smith.valueWeighted(u16, &.{ |
| 1370 | .value(u16, 0, 1 << 18), // 4x - stack traces have no tested properties except I.B. |
| 1371 | .rangeAtMost(u16, 0, math.maxInt(u16), 1), |
| 1372 | }), |
| 1373 | // If set, it is aimed to allocate much fewer bytes since freeing becomes O(n). |
| 1374 | // Without this, it is O(1) since mem.Allocator is bypassed so there is no memsets |
| 1375 | // of the data. |
| 1376 | .check_write_after_free = smith.valueWeighted(bool, &.{ |
| 1377 | .value(bool, false, 31), |
| 1378 | .value(bool, false, 1), |
| 1379 | }), |
| 1380 | .canary = smith.value(u32), |
| 1381 | |
| 1382 | .block_size_log2 = smith.valueWeighted(u5, size_log2_weights), |
| 1383 | .bucket_size_log2 = smith.valueWeighted(u5, size_log2_weights), |
| 1384 | }; |
| 1385 | } |
| 1386 | |
| 1387 | const Op = enum(u8) { alloc, free, resize, remap }; |
| 1388 | fn generateOp(smith: *Smith, any_allocs: bool) Op { |
| 1389 | @disableInstrumentation(); |
| 1390 | return if (any_allocs) smith.valueWeighted(Op, &.{ |
| 1391 | .rangeAtMost(Op, .alloc, .free, 4), |
| 1392 | .rangeAtMost(Op, .resize, .remap, 1), |
| 1393 | }) else .alloc; |
| 1394 | } |
| 1395 | |
| 1396 | fn generateSplat(smith: *Smith) ?u8 { |
| 1397 | @disableInstrumentation(); |
| 1398 | |
| 1399 | // Same rationale for `check_write_after_free` |
| 1400 | const n = smith.valueWeighted(u16, &.{ |
| 1401 | .value(u16, 256, 256 * 31), |
| 1402 | .rangeAtMost(u16, 0, 255, 1), |
| 1403 | }); |
| 1404 | return if (n == 256) null else @intCast(n); |
| 1405 | } |
| 1406 | |
| 1407 | fn generateLen(smith: *Smith, will_memset: bool) usize { |
| 1408 | @disableInstrumentation(); |
| 1409 | |
| 1410 | // 1 << 24 indicates to generate an unweighted usize. |
| 1411 | // 1 << 25 indicates to provide a value relative to the maximum usize. |
| 1412 | const len = smith.valueWeightedWithHash( |
| 1413 | u32, |
| 1414 | if (!will_memset) comptime &.{ |
| 1415 | // zig fmt: off |
| 1416 | .rangeLessThan(u32, 1 , 1 << 6 , 1 << 15), // 2^21 - 2^4 times below so 16x odds |
| 1417 | .rangeLessThan(u32, 1 << 6, 1 << 17, 1 ), // 2^17 - 2^4 times below so 16x odds |
| 1418 | .value (u32, 1 << 24, 1 << 12), // 2^12 |
| 1419 | .value (u32, 1 << 25, 1 << 12), // 2^12 |
| 1420 | // zig fmt: on |
| 1421 | } else comptime &.{ |
| 1422 | // zig fmt: off |
| 1423 | .rangeLessThan(u32, 1 , 1 << 6, 1 << 17), // 2^23 - 2^6 times below so 64x odds |
| 1424 | .rangeLessThan(u32, 1 << 6, 1 << 17, 1 ), // 2^17 - 2^6 times below so 64x odds |
| 1425 | .value (u32, 1 << 24, 1 << 10), // 2^10 |
| 1426 | .value (u32, 1 << 25, 1 << 10), // 2^10 |
| 1427 | // zig fmt: on |
| 1428 | }, |
| 1429 | // Give the fuzzer different hashes when the weights used differ |
| 1430 | // so that it does not reuse values from other probabilities. |
| 1431 | if (!will_memset) 0x38a74424 else 0xec581ff0, |
| 1432 | ); |
| 1433 | |
| 1434 | if (len == 1 << 24) return @max(1, smith.value(usize)); |
| 1435 | if (len == 1 << 25) return @as(usize, math.maxInt(usize)) - smith.value(u16); |
| 1436 | return len; |
| 1437 | } |
| 1438 | |
| 1439 | fn checkSplat(splat: ?u8, bytes: []const u8) void { |
| 1440 | @disableInstrumentation(); |
| 1441 | |
| 1442 | const byte = splat orelse return; |
| 1443 | for (bytes) |*b| if (b.* != byte) { |
| 1444 | panic("SafeAllocator corrupted allocation data at *{x}", .{@intFromPtr(b)}); |
| 1445 | }; |
| 1446 | } |
| 1447 | }; |
| 1448 | |
| 1449 | test "fuzz single threaded" { |
| 1450 | // This single threaded fuzz test has the following advantages: |
| 1451 | // * Higher throughput and deterministic, which helps the fuzzer. |
| 1452 | // * Easier debugging of single-threaded reproducable bugs. |
| 1453 | const testing_buf = try std.testing.allocator.alloc(u8, 65536); |
| 1454 | defer std.testing.allocator.free(testing_buf); |
| 1455 | const backing_buf = try std.testing.allocator.alloc(u8, 1 << 17); |
| 1456 | defer std.testing.allocator.free(backing_buf); |
| 1457 | try std.testing.fuzz(FuzzSingleThreadedContext{ |
| 1458 | .testing_buf = testing_buf, |
| 1459 | .backing_buf = backing_buf, |
| 1460 | }, fuzzSingleThreaded, .{}); |
| 1461 | } |
| 1462 | |
| 1463 | const FuzzSingleThreadedContext = struct { |
| 1464 | testing_buf: []u8, |
| 1465 | backing_buf: []u8, |
| 1466 | }; |
| 1467 | |
| 1468 | /// Guarantees memory will not be reused. |
| 1469 | const FuzzSingleThreadedAllocator = struct { |
| 1470 | gpa: mem.Allocator, |
| 1471 | smith: *std.testing.Smith, |
| 1472 | |
| 1473 | buf: []u8, |
| 1474 | fill: usize, |
| 1475 | allocs: std.MultiArrayList(AllocInfo), |
| 1476 | |
| 1477 | const AllocInfo = struct { |
| 1478 | ptr: [*]u8, |
| 1479 | len: usize, |
| 1480 | alignment: Alignment, |
| 1481 | }; |
| 1482 | |
| 1483 | fn allocator(f: *FuzzSingleThreadedAllocator) mem.Allocator { |
| 1484 | @disableInstrumentation(); |
| 1485 | return .{ .ptr = f, .vtable = &.{ |
| 1486 | .alloc = FuzzSingleThreadedAllocator.alloc, |
| 1487 | .free = FuzzSingleThreadedAllocator.free, |
| 1488 | .resize = FuzzSingleThreadedAllocator.resize, |
| 1489 | .remap = FuzzSingleThreadedAllocator.remap, |
| 1490 | } }; |
| 1491 | } |
| 1492 | |
| 1493 | fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, _: usize) ?[*]u8 { |
| 1494 | @disableInstrumentation(); |
| 1495 | |
| 1496 | const f: *FuzzSingleThreadedAllocator = @ptrCast(@alignCast(ctx)); |
| 1497 | f.allocs.ensureUnusedCapacity(f.gpa, 1) catch return null; |
| 1498 | |
| 1499 | const ptr = f.allocInner(len, alignment) orelse return null; |
| 1500 | f.allocs.appendAssumeCapacity(.{ |
| 1501 | .ptr = ptr, |
| 1502 | .len = len, |
| 1503 | .alignment = alignment, |
| 1504 | }); |
| 1505 | return ptr; |
| 1506 | } |
| 1507 | |
| 1508 | fn allocInner(f: *FuzzSingleThreadedAllocator, len: usize, alignment: Alignment) ?[*]u8 { |
| 1509 | @disableInstrumentation(); |
| 1510 | |
| 1511 | const start_addr = alignment.forward(@intFromPtr(f.buf[f.fill..].ptr)); |
| 1512 | const start = @as([*]u8, @ptrFromInt(start_addr)) - f.buf.ptr; |
| 1513 | if (start +| len > f.buf.len or f.smith.boolWeighted(31, 1)) return null; |
| 1514 | f.fill = start + len; |
| 1515 | return f.buf[start..][0..len].ptr; |
| 1516 | } |
| 1517 | |
| 1518 | fn allocIndex(f: *FuzzSingleThreadedAllocator, memory: []u8, alignment: Alignment) usize { |
| 1519 | @disableInstrumentation(); |
| 1520 | |
| 1521 | const allocs_slice = f.allocs.slice(); |
| 1522 | const i = mem.findScalar([*]u8, allocs_slice.items(.ptr), memory.ptr) orelse panic( |
| 1523 | "invalid SafeAllocator free of {f}", |
| 1524 | .{FormatMemory{ .memory = memory, .alignment = alignment }}, |
| 1525 | ); |
| 1526 | const expected_len = allocs_slice.items(.len)[i]; |
| 1527 | const expected_align = allocs_slice.items(.alignment)[i]; |
| 1528 | if (memory.len != expected_len or allocs_slice.items(.alignment)[i] != expected_align) { |
| 1529 | panic("SafeAllocator free {f} mismatches alloc {f}", .{ |
| 1530 | FormatMemory{ .memory = memory, .alignment = alignment }, |
| 1531 | FormatMemory{ .memory = memory.ptr[0..expected_len], .alignment = expected_align }, |
| 1532 | }); |
| 1533 | } |
| 1534 | return i; |
| 1535 | } |
| 1536 | |
| 1537 | fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, _: usize) void { |
| 1538 | @disableInstrumentation(); |
| 1539 | |
| 1540 | const f: *FuzzSingleThreadedAllocator = @ptrCast(@alignCast(ctx)); |
| 1541 | f.allocs.swapRemove(f.allocIndex(memory, alignment)); |
| 1542 | } |
| 1543 | |
| 1544 | fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, _: usize) bool { |
| 1545 | @disableInstrumentation(); |
| 1546 | |
| 1547 | const f: *FuzzSingleThreadedAllocator = @ptrCast(@alignCast(ctx)); |
| 1548 | const i = f.allocIndex(memory, alignment); |
| 1549 | |
| 1550 | const start = memory.ptr - f.buf.ptr; |
| 1551 | const old_end = start + memory.len; |
| 1552 | const new_end = start +| new_len; |
| 1553 | if (new_end > f.buf.len or f.smith.value(bool)) { |
| 1554 | return false; |
| 1555 | } |
| 1556 | |
| 1557 | if (new_len <= memory.len) { |
| 1558 | // The fill is not decreased so memory is not reused. |
| 1559 | } else if (f.fill == old_end) { |
| 1560 | f.fill = new_end; |
| 1561 | } else { |
| 1562 | return false; |
| 1563 | } |
| 1564 | f.allocs.items(.len)[i] = new_len; |
| 1565 | return true; |
| 1566 | } |
| 1567 | |
| 1568 | fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, _: usize) ?[*]u8 { |
| 1569 | @disableInstrumentation(); |
| 1570 | |
| 1571 | const f: *FuzzSingleThreadedAllocator = @ptrCast(@alignCast(ctx)); |
| 1572 | if (f.smith.value(bool)) { |
| 1573 | const resized = FuzzSingleThreadedAllocator.resize( |
| 1574 | ctx, |
| 1575 | memory, |
| 1576 | alignment, |
| 1577 | new_len, |
| 1578 | undefined, |
| 1579 | ); |
| 1580 | return if (resized) memory.ptr else null; |
| 1581 | } |
| 1582 | |
| 1583 | const i = f.allocIndex(memory, alignment); |
| 1584 | if (f.smith.value(bool)) return null; |
| 1585 | |
| 1586 | const new_ptr = f.allocInner(new_len, alignment) orelse return null; |
| 1587 | const copy_len = @min(memory.len, new_len); |
| 1588 | @memcpy(new_ptr[0..copy_len], memory[0..copy_len]); |
| 1589 | |
| 1590 | f.allocs.set(i, .{ |
| 1591 | .ptr = new_ptr, |
| 1592 | .len = new_len, |
| 1593 | .alignment = alignment, |
| 1594 | }); |
| 1595 | return new_ptr; |
| 1596 | } |
| 1597 | }; |
| 1598 | |
| 1599 | fn fuzzSingleThreaded(ctx: FuzzSingleThreadedContext, smith: *Smith) !void { |
| 1600 | @disableInstrumentation(); |
| 1601 | |
| 1602 | var gpa_instance: std.heap.FixedBufferAllocator = .init(ctx.testing_buf); |
| 1603 | const gpa = gpa_instance.allocator(); |
| 1604 | var backing_gpa_instance: FuzzSingleThreadedAllocator = .{ |
| 1605 | .gpa = gpa, |
| 1606 | .smith = smith, |
| 1607 | |
| 1608 | .buf = ctx.backing_buf, |
| 1609 | .fill = 0, |
| 1610 | .allocs = .empty, |
| 1611 | }; |
| 1612 | const backing_gpa = backing_gpa_instance.allocator(); |
| 1613 | |
| 1614 | const options = fuzz_probs.generateOptions(smith); |
| 1615 | var s: SafeAllocator = .init(backing_gpa, options); |
| 1616 | const no_ra: usize = 0; |
| 1617 | |
| 1618 | var allocs: std.MultiArrayList(struct { |
| 1619 | memory: []u8, |
| 1620 | alignment: Alignment, |
| 1621 | splat: ?u8, |
| 1622 | }) = .empty; |
| 1623 | var used_memory: std.ArrayList(struct { |
| 1624 | start: usize, |
| 1625 | end: usize, |
| 1626 | }) = .empty; |
| 1627 | |
| 1628 | while (!smith.eosWeighted(fuzz_probs.eos)) { |
| 1629 | const op = fuzz_probs.generateOp(smith, allocs.len != 0); |
| 1630 | const new_mem: []const u8, const old_mem: ?[]const u8 = new_alloc: switch (op) { |
| 1631 | .alloc => { |
| 1632 | used_memory.ensureUnusedCapacity(gpa, 1) catch break; |
| 1633 | allocs.ensureUnusedCapacity(gpa, 1) catch break; |
| 1634 | |
| 1635 | const splat = fuzz_probs.generateSplat(smith); |
| 1636 | const will_memset = options.check_write_after_free or splat != null; |
| 1637 | const len = fuzz_probs.generateLen(smith, will_memset); |
| 1638 | const alignment = smith.valueWeighted(Alignment, fuzz_probs.alignment); |
| 1639 | |
| 1640 | const ptr = alloc(&s, len, alignment, no_ra) orelse continue; |
| 1641 | if (!alignment.check(@intFromPtr(ptr))) @panic("bad returned alignment"); |
| 1642 | const memory = ptr[0..len]; |
| 1643 | if (splat) |b| @memset(memory, b); |
| 1644 | |
| 1645 | allocs.appendAssumeCapacity(.{ |
| 1646 | .memory = memory, |
| 1647 | .alignment = alignment, |
| 1648 | .splat = splat, |
| 1649 | }); |
| 1650 | break :new_alloc .{ memory, null }; |
| 1651 | }, |
| 1652 | .free => { |
| 1653 | const i = smith.valueRangeLessThan(u32, 0, @intCast(allocs.len)); |
| 1654 | const alloc_info = allocs.get(i); |
| 1655 | allocs.swapRemove(i); |
| 1656 | |
| 1657 | fuzz_probs.checkSplat(alloc_info.splat, alloc_info.memory); |
| 1658 | free(&s, alloc_info.memory, alloc_info.alignment, no_ra); |
| 1659 | continue; |
| 1660 | }, |
| 1661 | .resize => { |
| 1662 | used_memory.ensureUnusedCapacity(gpa, 1) catch break; |
| 1663 | const i = smith.valueRangeLessThan(u32, 0, @intCast(allocs.len)); |
| 1664 | const allocs_slice = allocs.slice(); |
| 1665 | |
| 1666 | const prev_alloc = allocs_slice.get(i); |
| 1667 | const old_len = prev_alloc.memory.len; |
| 1668 | |
| 1669 | const alloc_memory = &allocs_slice.items(.memory)[i]; |
| 1670 | const splat = prev_alloc.splat; |
| 1671 | const will_memset = options.check_write_after_free or splat != null; |
| 1672 | |
| 1673 | const new_len = fuzz_probs.generateLen(smith, will_memset); |
| 1674 | if (!resize(&s, prev_alloc.memory, prev_alloc.alignment, new_len, no_ra)) { |
| 1675 | fuzz_probs.checkSplat(prev_alloc.splat, prev_alloc.memory); |
| 1676 | continue; |
| 1677 | } |
| 1678 | alloc_memory.len = new_len; |
| 1679 | |
| 1680 | fuzz_probs.checkSplat(prev_alloc.splat, alloc_memory.*[0..@min(old_len, new_len)]); |
| 1681 | if (splat) |b| @memset(alloc_memory.*[@min(old_len, new_len)..], b); |
| 1682 | |
| 1683 | break :new_alloc .{ alloc_memory.*, prev_alloc.memory }; |
| 1684 | }, |
| 1685 | .remap => { |
| 1686 | used_memory.ensureUnusedCapacity(gpa, 1) catch break; |
| 1687 | const i = smith.valueRangeLessThan(u32, 0, @intCast(allocs.len)); |
| 1688 | const allocs_slice = allocs.slice(); |
| 1689 | |
| 1690 | const prev_alloc = allocs_slice.get(i); |
| 1691 | const old_len = prev_alloc.memory.len; |
| 1692 | |
| 1693 | const alloc_memory = &allocs_slice.items(.memory)[i]; |
| 1694 | const alignment = prev_alloc.alignment; |
| 1695 | const splat = prev_alloc.splat; |
| 1696 | const will_memset = options.check_write_after_free or splat != null; |
| 1697 | |
| 1698 | const new_len = fuzz_probs.generateLen(smith, will_memset); |
| 1699 | const new_ptr = remap( |
| 1700 | &s, |
| 1701 | prev_alloc.memory, |
| 1702 | prev_alloc.alignment, |
| 1703 | new_len, |
| 1704 | no_ra, |
| 1705 | ) orelse { |
| 1706 | fuzz_probs.checkSplat(prev_alloc.splat, prev_alloc.memory); |
| 1707 | continue; |
| 1708 | }; |
| 1709 | alloc_memory.* = new_ptr[0..new_len]; |
| 1710 | |
| 1711 | if (!alignment.check(@intFromPtr(new_ptr))) @panic("bad returned alignment"); |
| 1712 | fuzz_probs.checkSplat(prev_alloc.splat, alloc_memory.*[0..@min(old_len, new_len)]); |
| 1713 | if (splat) |b| @memset(alloc_memory.*[@min(old_len, new_len)..], b); |
| 1714 | |
| 1715 | break :new_alloc .{ alloc_memory.*, prev_alloc.memory }; |
| 1716 | }, |
| 1717 | }; |
| 1718 | |
| 1719 | const new_start = @intFromPtr(new_mem.ptr); |
| 1720 | const new_end = new_start + new_mem.len; |
| 1721 | const old_start = if (old_mem) |old| @intFromPtr(old.ptr) else 0; |
| 1722 | const old_end = new_start + if (old_mem) |old| old.len else 0; |
| 1723 | for (used_memory.items) |used| { |
| 1724 | if (old_start <= used.end and used.start <= old_end) { |
| 1725 | continue; |
| 1726 | } |
| 1727 | if (new_start <= used.end and used.start <= new_end) { |
| 1728 | panic( |
| 1729 | "memory reuse between [addr: {x}, len: {}] and new [addr: {x}, len: {}]", |
| 1730 | .{ used.start, used.end, new_start, new_end }, |
| 1731 | ); |
| 1732 | } |
| 1733 | } |
| 1734 | used_memory.appendAssumeCapacity(.{ .start = new_start, .end = new_end }); |
| 1735 | } |
| 1736 | |
| 1737 | try std.testing.expectEqual(allocs.len, s.deinitLog(false)); |
| 1738 | const leaks_slice = backing_gpa_instance.allocs.slice(); |
| 1739 | for (0..leaks_slice.len) |i| { |
| 1740 | const leak = leaks_slice.get(i); |
| 1741 | std.log.err("SafeAllocator leaked {f}", .{FormatMemory{ |
| 1742 | .memory = leak.ptr[0..leak.len], |
| 1743 | .alignment = leak.alignment, |
| 1744 | }}); |
| 1745 | } |
| 1746 | try std.testing.expectEqual(0, leaks_slice.len); // no leaks |
| 1747 | } |
| 1748 | |
| 1749 | test "fuzz multi threaded" { |
| 1750 | if (@import("builtin").single_threaded) return error.SkipZigTest; |
| 1751 | |
| 1752 | const testing_buf = try std.testing.allocator.alloc(u8, 65536); |
| 1753 | defer std.testing.allocator.free(testing_buf); |
| 1754 | const backing_buf = try std.testing.allocator.alloc(u8, 1 << 17); |
| 1755 | defer std.testing.allocator.free(backing_buf); |
| 1756 | |
| 1757 | // `std.testing` instances are overwritten during `std.testing.fuzz` so |
| 1758 | // it is necessary to use our own io and gpa instances. |
| 1759 | var threaded_io: std.Io.Threaded = .init(std.heap.smp_allocator, .{}); |
| 1760 | defer threaded_io.deinit(); |
| 1761 | const io = threaded_io.io(); |
| 1762 | |
| 1763 | var ops: FuzzMultiThreadedContext.ThreadOps = undefined; |
| 1764 | ops.run = .{ .n = false }; |
| 1765 | var group: std.Io.Group = .init; |
| 1766 | defer group.cancel(io); |
| 1767 | for (0..FuzzMultiThreadedContext.n_threads) |_| { |
| 1768 | try group.concurrent(io, fuzzMultiThreadedWorker, .{ io, &ops }); |
| 1769 | } |
| 1770 | |
| 1771 | try std.testing.fuzz(FuzzMultiThreadedContext{ |
| 1772 | .testing_buf = testing_buf, |
| 1773 | .backing_buf = backing_buf, |
| 1774 | |
| 1775 | .io = io, |
| 1776 | .ops = &ops, |
| 1777 | }, fuzzMultiThreaded, .{}); |
| 1778 | } |
| 1779 | |
| 1780 | const FuzzMultiThreadedContext = struct { |
| 1781 | testing_buf: []u8, |
| 1782 | backing_buf: []u8, |
| 1783 | |
| 1784 | io: std.Io, |
| 1785 | ops: *ThreadOps, |
| 1786 | |
| 1787 | const n_threads = 4; |
| 1788 | |
| 1789 | const ThreadOps = struct { |
| 1790 | /// Switches between two values for each time a run starts. |
| 1791 | run: Run, |
| 1792 | /// While this can be calculated as `n_threads - (i -| ops.items.len)`, |
| 1793 | /// this also serves as `.release` synchronization for each thread. |
| 1794 | running: u32, |
| 1795 | |
| 1796 | instance: SafeAllocator, |
| 1797 | i: usize, |
| 1798 | items: []Op, |
| 1799 | |
| 1800 | const Run = packed struct(u32) { |
| 1801 | n: bool, |
| 1802 | pad: u31 = 0, |
| 1803 | |
| 1804 | fn wait(ptr: *Run, val: Run, io: std.Io) error{Canceled}!void { |
| 1805 | assert(val.pad == 0); |
| 1806 | while (true) { |
| 1807 | // This cannot load a previous value since this thread previously loaded the |
| 1808 | // latest value. |
| 1809 | const prev = @atomicLoad(Run, ptr, .acquire); |
| 1810 | assert(prev.pad == 0); |
| 1811 | if (prev == val) break; |
| 1812 | |
| 1813 | try io.futexWait(Run, ptr, prev); |
| 1814 | } |
| 1815 | } |
| 1816 | |
| 1817 | fn next(r: Run) Run { |
| 1818 | assert(r.pad == 0); |
| 1819 | return .{ .n = !r.n }; |
| 1820 | } |
| 1821 | }; |
| 1822 | |
| 1823 | const Op = union(fuzz_probs.Op) { |
| 1824 | alloc: struct { |
| 1825 | len: usize, |
| 1826 | alignment: Alignment, |
| 1827 | |
| 1828 | splat: ?u8, |
| 1829 | /// Not embeded directly in the struct as a workaround for tsan since a |
| 1830 | /// switch directly on `Op` loads the entire value non-atomically. |
| 1831 | result: *MemoryDependency, |
| 1832 | }, |
| 1833 | free: struct { |
| 1834 | memory: *MemoryDependency, |
| 1835 | alignment: Alignment, |
| 1836 | |
| 1837 | splat: ?u8, |
| 1838 | }, |
| 1839 | resize: Realloc, |
| 1840 | remap: Realloc, |
| 1841 | |
| 1842 | const Realloc = struct { |
| 1843 | memory: *MemoryDependency, |
| 1844 | alignment: Alignment, |
| 1845 | new_len: usize, |
| 1846 | |
| 1847 | splat: ?u8, |
| 1848 | /// Not embeded directly in the struct as a workaround for tsan since a |
| 1849 | /// switch directly on `Op` loads the entire value non-atomically. |
| 1850 | result: *MemoryDependency, |
| 1851 | }; |
| 1852 | |
| 1853 | const MemoryDependency = struct { |
| 1854 | ready: std.Io.Event, |
| 1855 | /// Null if the memory failed to be allocated |
| 1856 | memory: ?[]u8, |
| 1857 | |
| 1858 | const init: MemoryDependency = .{ |
| 1859 | .ready = .unset, |
| 1860 | .memory = undefined, |
| 1861 | }; |
| 1862 | |
| 1863 | fn get(dep: *MemoryDependency, io: std.Io) ?[]u8 { |
| 1864 | dep.ready.waitUncancelable(io); |
| 1865 | return dep.memory; |
| 1866 | } |
| 1867 | }; |
| 1868 | }; |
| 1869 | }; |
| 1870 | }; |
| 1871 | |
| 1872 | /// Guarantees memory will not be reused. |
| 1873 | const FuzzMultiThreadedAllocator = struct { |
| 1874 | gpa: mem.Allocator, |
| 1875 | |
| 1876 | fill: usize, |
| 1877 | active_allocs: usize, |
| 1878 | fail_i: usize, |
| 1879 | fixed_remap_i: usize, |
| 1880 | |
| 1881 | // The below are assumed to be externally synchronized |
| 1882 | // i.e. each thread has an acquire fence before **first** using the allocator |
| 1883 | buf: []u8, |
| 1884 | fails: []const bool, |
| 1885 | fixed_remaps: []const bool, |
| 1886 | |
| 1887 | fn allocator(f: *FuzzMultiThreadedAllocator) mem.Allocator { |
| 1888 | @disableInstrumentation(); |
| 1889 | return .{ .ptr = f, .vtable = &.{ |
| 1890 | .alloc = FuzzMultiThreadedAllocator.alloc, |
| 1891 | .free = FuzzMultiThreadedAllocator.free, |
| 1892 | .resize = FuzzMultiThreadedAllocator.resize, |
| 1893 | .remap = FuzzMultiThreadedAllocator.remap, |
| 1894 | } }; |
| 1895 | } |
| 1896 | |
| 1897 | fn maybeFail(f: *FuzzMultiThreadedAllocator) bool { |
| 1898 | @disableInstrumentation(); |
| 1899 | const i = @atomicRmw(usize, &f.fail_i, .Add, 1, .monotonic); |
| 1900 | return i < f.fails.len and f.fails[i]; |
| 1901 | } |
| 1902 | |
| 1903 | fn maybeFixedRemap(f: *FuzzMultiThreadedAllocator) bool { |
| 1904 | @disableInstrumentation(); |
| 1905 | const i = @atomicRmw(usize, &f.fixed_remap_i, .Add, 1, .monotonic); |
| 1906 | return i < f.fixed_remaps.len and f.fixed_remaps[i]; |
| 1907 | } |
| 1908 | |
| 1909 | fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, _: usize) ?[*]u8 { |
| 1910 | @disableInstrumentation(); |
| 1911 | |
| 1912 | const f: *FuzzMultiThreadedAllocator = @ptrCast(@alignCast(ctx)); |
| 1913 | const memory = f.allocInner(len, alignment) orelse return null; |
| 1914 | _ = @atomicRmw(usize, &f.active_allocs, .Add, 1, .monotonic); |
| 1915 | return memory; |
| 1916 | } |
| 1917 | |
| 1918 | fn allocInner(f: *FuzzMultiThreadedAllocator, len: usize, alignment: Alignment) ?[*]u8 { |
| 1919 | var prev_fill = @atomicLoad(usize, &f.fill, .monotonic); |
| 1920 | var start: usize = undefined; |
| 1921 | while (true) { |
| 1922 | const start_addr = alignment.forward(@intFromPtr(f.buf[prev_fill..].ptr)); |
| 1923 | start = @as([*]u8, @ptrFromInt(start_addr)) - f.buf.ptr; |
| 1924 | if (start +| len > f.buf.len or f.maybeFail()) return null; |
| 1925 | prev_fill = @cmpxchgStrong( |
| 1926 | usize, |
| 1927 | &f.fill, |
| 1928 | prev_fill, |
| 1929 | start + len, |
| 1930 | .monotonic, |
| 1931 | .monotonic, |
| 1932 | ) orelse { |
| 1933 | @branchHint(.likely); |
| 1934 | break; |
| 1935 | }; |
| 1936 | } |
| 1937 | return f.buf[start..][0..len].ptr; |
| 1938 | } |
| 1939 | |
| 1940 | fn free(ctx: *anyopaque, _: []u8, _: Alignment, _: usize) void { |
| 1941 | @disableInstrumentation(); |
| 1942 | |
| 1943 | const f: *FuzzMultiThreadedAllocator = @ptrCast(@alignCast(ctx)); |
| 1944 | assert(@atomicRmw(usize, &f.active_allocs, .Sub, 1, .monotonic) != 0); |
| 1945 | } |
| 1946 | |
| 1947 | fn resize(ctx: *anyopaque, memory: []u8, _: Alignment, new_len: usize, _: usize) bool { |
| 1948 | @disableInstrumentation(); |
| 1949 | |
| 1950 | const f: *FuzzMultiThreadedAllocator = @ptrCast(@alignCast(ctx)); |
| 1951 | const start = memory.ptr - f.buf.ptr; |
| 1952 | const old_end = start + memory.len; |
| 1953 | const new_end = start +| new_len; |
| 1954 | if (new_end > f.buf.len or f.maybeFail()) { |
| 1955 | return false; |
| 1956 | } |
| 1957 | |
| 1958 | if (new_len <= memory.len) { |
| 1959 | // The fill is not decreased so memory is not reused. |
| 1960 | return true; |
| 1961 | } |
| 1962 | |
| 1963 | return @cmpxchgStrong(usize, &f.fill, old_end, new_end, .monotonic, .monotonic) == null; |
| 1964 | } |
| 1965 | |
| 1966 | fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, _: usize) ?[*]u8 { |
| 1967 | @disableInstrumentation(); |
| 1968 | |
| 1969 | if (maybeFixedRemap(@ptrCast(@alignCast(ctx)))) { |
| 1970 | const resized = FuzzMultiThreadedAllocator.resize( |
| 1971 | ctx, |
| 1972 | memory, |
| 1973 | alignment, |
| 1974 | new_len, |
| 1975 | undefined, |
| 1976 | ); |
| 1977 | return if (resized) memory.ptr else null; |
| 1978 | } |
| 1979 | |
| 1980 | const f: *FuzzMultiThreadedAllocator = @ptrCast(@alignCast(ctx)); |
| 1981 | const new_ptr = f.allocInner(new_len, alignment) orelse return null; |
| 1982 | const copy_len = @min(memory.len, new_len); |
| 1983 | @memcpy(new_ptr[0..copy_len], memory[0..copy_len]); |
| 1984 | return new_ptr; |
| 1985 | } |
| 1986 | }; |
| 1987 | |
| 1988 | fn fuzzMultiThreaded(ctx: FuzzMultiThreadedContext, smith: *Smith) !void { |
| 1989 | @disableInstrumentation(); |
| 1990 | |
| 1991 | var gpa_instance: std.heap.FixedBufferAllocator = .init(ctx.testing_buf); |
| 1992 | const gpa = gpa_instance.allocator(); |
| 1993 | |
| 1994 | var op_count: u32 = 0; |
| 1995 | while (!smith.eosWeighted(fuzz_probs.eos)) op_count += 1; |
| 1996 | const Op = FuzzMultiThreadedContext.ThreadOps.Op; |
| 1997 | const ops = gpa.alloc(Op, op_count) catch return error.SkipZigTest; |
| 1998 | const op_results = gpa.alloc(Op.MemoryDependency, op_count) catch return error.SkipZigTest; |
| 1999 | @memset(op_results, .init); |
| 2000 | |
| 2001 | const allocs = gpa.alloc(struct { |
| 2002 | memory: *FuzzMultiThreadedContext.ThreadOps.Op.MemoryDependency, |
| 2003 | alignment: Alignment, |
| 2004 | splat: ?u8, |
| 2005 | }, op_count) catch return error.SkipZigTest; |
| 2006 | var allocs_n: u32 = 0; |
| 2007 | var expected_remaps: usize = 0; |
| 2008 | |
| 2009 | const options = fuzz_probs.generateOptions(smith); |
| 2010 | for (ops, op_results) |*op, *result| switch (fuzz_probs.generateOp(smith, allocs_n != 0)) { |
| 2011 | .alloc => { |
| 2012 | const splat = fuzz_probs.generateSplat(smith); |
| 2013 | const will_memset = options.check_write_after_free or splat != null; |
| 2014 | op.* = .{ .alloc = .{ |
| 2015 | .len = fuzz_probs.generateLen(smith, will_memset), |
| 2016 | .alignment = smith.valueWeighted(Alignment, fuzz_probs.alignment), |
| 2017 | |
| 2018 | .splat = splat, |
| 2019 | .result = result, |
| 2020 | } }; |
| 2021 | allocs[allocs_n] = .{ |
| 2022 | .memory = result, |
| 2023 | .alignment = op.alloc.alignment, |
| 2024 | .splat = splat, |
| 2025 | }; |
| 2026 | allocs_n += 1; |
| 2027 | }, |
| 2028 | .free => { |
| 2029 | const i = smith.valueRangeLessThan(u32, 0, allocs_n); |
| 2030 | op.* = .{ .free = .{ |
| 2031 | .memory = allocs[i].memory, |
| 2032 | .alignment = allocs[i].alignment, |
| 2033 | |
| 2034 | .splat = allocs[i].splat, |
| 2035 | } }; |
| 2036 | |
| 2037 | allocs_n -= 1; |
| 2038 | allocs[i] = allocs[allocs_n]; |
| 2039 | }, |
| 2040 | .resize, .remap => |kind| { |
| 2041 | op.* = switch (kind) { |
| 2042 | .remap => .{ .remap = undefined }, |
| 2043 | .resize => .{ .resize = undefined }, |
| 2044 | else => unreachable, |
| 2045 | }; |
| 2046 | const realloc = switch (kind) { |
| 2047 | .remap => &op.remap, |
| 2048 | .resize => &op.resize, |
| 2049 | else => unreachable, |
| 2050 | }; |
| 2051 | expected_remaps += @intFromBool(kind == .remap); |
| 2052 | |
| 2053 | const i = smith.valueRangeLessThan(u32, 0, allocs_n); |
| 2054 | realloc.* = .{ |
| 2055 | .memory = allocs[i].memory, |
| 2056 | .alignment = allocs[i].alignment, |
| 2057 | .new_len = fuzz_probs.generateLen(smith, options.check_write_after_free), |
| 2058 | |
| 2059 | .splat = allocs[i].splat, |
| 2060 | .result = result, |
| 2061 | }; |
| 2062 | allocs[i].memory = result; |
| 2063 | }, |
| 2064 | }; |
| 2065 | |
| 2066 | const fails: []bool = gpa.alloc(bool, ops.len * 2 + smith.value(u8)) catch &.{}; |
| 2067 | const fixed_remaps: []bool = gpa.alloc(bool, expected_remaps + smith.value(u8)) catch &.{}; |
| 2068 | for (fails) |*f| f.* = smith.boolWeighted(31, 1); |
| 2069 | for (fixed_remaps) |*f| f.* = smith.value(bool); |
| 2070 | var backing_gpa_instance: FuzzMultiThreadedAllocator = .{ |
| 2071 | .gpa = gpa, |
| 2072 | |
| 2073 | .fill = 0, |
| 2074 | .active_allocs = 0, |
| 2075 | .fail_i = 0, |
| 2076 | .fixed_remap_i = 0, |
| 2077 | |
| 2078 | .buf = ctx.backing_buf, |
| 2079 | .fails = fails, |
| 2080 | .fixed_remaps = fixed_remaps, |
| 2081 | }; |
| 2082 | const backing_gpa = backing_gpa_instance.allocator(); |
| 2083 | |
| 2084 | ctx.ops.instance = .init(backing_gpa, options); |
| 2085 | ctx.ops.i = 0; |
| 2086 | ctx.ops.items = ops; |
| 2087 | |
| 2088 | ctx.ops.running = FuzzMultiThreadedContext.n_threads; |
| 2089 | // Loading `ctx.ops.run` non-atomically is fine since this is the only thread that writes to it. |
| 2090 | @atomicStore(FuzzMultiThreadedContext.ThreadOps.Run, &ctx.ops.run, ctx.ops.run.next(), .release); |
| 2091 | ctx.io.futexWake(FuzzMultiThreadedContext.ThreadOps.Run, &ctx.ops.run, math.maxInt(u32)); |
| 2092 | while (true) { |
| 2093 | const prev_running = @atomicLoad(u32, &ctx.ops.running, .acquire); |
| 2094 | if (prev_running == 0) break; |
| 2095 | ctx.io.futexWaitUncancelable(u32, &ctx.ops.running, prev_running); |
| 2096 | } |
| 2097 | |
| 2098 | var expected_allocs = allocs_n; |
| 2099 | for (allocs[0..allocs_n]) |a| { |
| 2100 | expected_allocs -= @intFromBool(a.memory.memory == null); |
| 2101 | } |
| 2102 | try std.testing.expectEqual(expected_allocs, ctx.ops.instance.deinitLog(false)); |
| 2103 | try std.testing.expectEqual(0, backing_gpa_instance.active_allocs); // no leaks |
| 2104 | } |
| 2105 | |
| 2106 | fn fuzzMultiThreadedWorker( |
| 2107 | io: std.Io, |
| 2108 | ops: *FuzzMultiThreadedContext.ThreadOps, |
| 2109 | ) error{Canceled}!void { |
| 2110 | const no_ra: usize = 0; |
| 2111 | var next_run: FuzzMultiThreadedContext.ThreadOps.Run = .{ .n = true }; |
| 2112 | while (true) { |
| 2113 | try ops.run.wait(next_run, io); |
| 2114 | next_run = .next(next_run); |
| 2115 | |
| 2116 | while (true) { |
| 2117 | const i = @atomicRmw(usize, &ops.i, .Add, 1, .monotonic); |
| 2118 | if (i >= ops.items.len) { |
| 2119 | // `.acq_rel` is necessary since acquire loads only synchronize with the thread |
| 2120 | // which the read value was written from, not all previous writer threads. |
| 2121 | const prev_rem = @atomicRmw(u32, &ops.running, .Sub, 1, .acq_rel); |
| 2122 | if (prev_rem - 1 == 0) { |
| 2123 | io.futexWake(u32, &ops.running, 1); |
| 2124 | } |
| 2125 | break; |
| 2126 | } |
| 2127 | |
| 2128 | switch (ops.items[i]) { |
| 2129 | .alloc => |call| { |
| 2130 | const alloc_ptr = alloc(&ops.instance, call.len, call.alignment, no_ra); |
| 2131 | if (alloc_ptr) |memory_ptr| { |
| 2132 | const memory = memory_ptr[0..call.len]; |
| 2133 | if (call.splat) |b| @memset(memory, b); |
| 2134 | call.result.memory = memory; |
| 2135 | } else { |
| 2136 | call.result.memory = null; |
| 2137 | } |
| 2138 | call.result.ready.set(io); |
| 2139 | }, |
| 2140 | .free => |call| { |
| 2141 | const memory = call.memory.get(io) orelse continue; |
| 2142 | fuzz_probs.checkSplat(call.splat, memory); |
| 2143 | free(&ops.instance, memory, call.alignment, no_ra); |
| 2144 | }, |
| 2145 | .resize, .remap => |call, kind| { |
| 2146 | const memory = call.memory.get(io) orelse { |
| 2147 | call.result.memory = null; |
| 2148 | call.result.ready.set(io); |
| 2149 | continue; |
| 2150 | }; |
| 2151 | const new_memory: []u8 = switch (kind) { |
| 2152 | .remap => if (remap( |
| 2153 | &ops.instance, |
| 2154 | memory, |
| 2155 | call.alignment, |
| 2156 | call.new_len, |
| 2157 | no_ra, |
| 2158 | )) |new_ptr| new_ptr[0..call.new_len] else memory, |
| 2159 | .resize => if (resize( |
| 2160 | &ops.instance, |
| 2161 | memory, |
| 2162 | call.alignment, |
| 2163 | call.new_len, |
| 2164 | no_ra, |
| 2165 | )) memory.ptr[0..call.new_len] else memory, |
| 2166 | else => unreachable, |
| 2167 | }; |
| 2168 | |
| 2169 | const old_len = memory.len; |
| 2170 | const new_len = new_memory.len; |
| 2171 | fuzz_probs.checkSplat(call.splat, new_memory[0..@min(old_len, new_len)]); |
| 2172 | if (call.splat) |b| @memset(new_memory[@min(old_len, new_len)..], b); |
| 2173 | |
| 2174 | call.result.memory = new_memory; |
| 2175 | call.result.ready.set(io); |
| 2176 | }, |
| 2177 | } |
| 2178 | } |
| 2179 | } |
| 2180 | } |