plan.odin (2722B)
1 package ntfs 2 3 import "core:mem" 4 5 // A byte range of the MFT's logical address space that is worth reading. 6 @(private) 7 Read_Extent :: struct { 8 offset: u64, 9 length: u64, 10 } 11 12 /* 13 Decide which parts of the MFT to read. 14 15 $MFT carries its own $BITMAP, one bit per record slot, so which slots are dead is 16 known before a single record is fetched. On a volume that has seen a lot of churn the 17 dead slots can be a third of the table, and reading them is pure waste. 18 19 Skipping is only a win when the dead run is long enough that not reading it beats 20 breaking the sequential stream and paying for another request, so gaps shorter than 21 `min_gap` are read through instead. Extents are cluster aligned because a cluster can 22 hold several records and unbuffered reads must cover whole sectors; a cluster counts 23 as live when any record touching it is live. 24 25 A slot the bitmap calls dead may briefly hold a record the file system is still 26 allocating. The reader is already looking at a live volume without a snapshot, so 27 that race is the same one the whole scan lives with. 28 */ 29 @(private) 30 plan_reads :: proc( 31 bitmap: []byte, 32 mft_bytes: u64, 33 record_size, cluster, min_gap: u64, 34 allocator: mem.Allocator, 35 ) -> ( 36 extents: []Read_Extent, 37 err: Error, 38 ) { 39 out := make([dynamic]Read_Extent, allocator) 40 total_clusters := (mft_bytes + cluster - 1) / cluster 41 records := mft_bytes / record_size 42 43 start, end: u64 // current extent, in clusters; end is exclusive 44 open := false 45 for c: u64 = 0; c < total_clusters; c += 1 { 46 if !cluster_has_live_record(bitmap, c, records, record_size, cluster) { 47 continue 48 } 49 switch { 50 case !open: 51 start, end, open = c, c + 1, true 52 case (c - end) * cluster < min_gap: 53 end = c + 1 // the gap is too short to be worth skipping 54 case: 55 append(&out, Read_Extent{start * cluster, (end - start) * cluster}) 56 start, end = c, c + 1 57 } 58 } 59 if open { 60 append(&out, Read_Extent{start * cluster, (end - start) * cluster}) 61 } 62 63 // The last extent may run past the attribute's length once rounded to a cluster. 64 if len(out) > 0 { 65 last := &out[len(out) - 1] 66 if last.offset + last.length > mft_bytes { 67 last.length = mft_bytes - last.offset 68 } 69 } 70 return out[:], .None 71 } 72 73 @(private) 74 cluster_has_live_record :: proc "contextless" ( 75 bitmap: []byte, 76 c, records, record_size, cluster: u64, 77 ) -> bool { 78 first := c * cluster / record_size 79 last := ((c + 1) * cluster - 1) / record_size 80 for r := first; r <= last && r < records; r += 1 { 81 if bit_is_set(bitmap, r) { 82 return true 83 } 84 } 85 return false 86 } 87 88 @(private) 89 bit_is_set :: proc "contextless" (b: []byte, i: u64) -> bool { 90 byte_index := i / 8 91 if byte_index >= u64(len(b)) { 92 return false 93 } 94 return b[byte_index] & (1 << uint(i % 8)) != 0 95 }