tree.odin (5190B)
1 package ntfs 2 3 import "core:mem" 4 5 import "../scan" 6 7 /* 8 Carried between projections so repeating one is cheap and adds nothing twice. 9 10 `settled` remembers which records have been folded in for good. A record is only 11 finished with once its parent reference is final, because a parent not yet published 12 may still turn out to hold the name, and a node written before then would be left 13 rooted at itself forever. 14 15 `fresh` is what became final since the last call, which is the only work an 16 incremental consumer has to do. 17 */ 18 Projection :: struct { 19 // What to call the root. NTFS names it ".", which says nothing in a path, and the 20 // caller is the one that knows where the volume is mounted. Setting it here rather 21 // than afterwards keeps a watching thread from ever catching the placeholder. 22 root_name: string, 23 links_done: int, 24 settled: []u64, // one bit per record 25 allocator: mem.Allocator, 26 } 27 28 /* 29 Forget what has been projected, so the next call redoes every record. 30 31 A settled record is skipped on later calls, which is what makes a frame cheap, but it 32 also means its size is never re-read. Extension records add to a base record after it 33 was published, and a badly fragmented file can hold most of its allocation there, so 34 a projection taken during a scan under-reports them. Call this once the scan has 35 finished to get an exact answer. 36 */ 37 projection_reset :: proc(p: ^Projection) { 38 for i in 0 ..< len(p.settled) { 39 p.settled[i] = 0 40 } 41 p.links_done = 0 42 } 43 44 projection_destroy :: proc(p: ^Projection) { 45 delete(p.settled, p.allocator) 46 p^ = {} 47 } 48 49 /* 50 Project a table into the normalised tree, or bring an earlier projection up to date. 51 52 The table stays the native form and keeps what only NTFS has: record and sequence 53 numbers, per-stream allocation, the resident-file accounting. A caller wanting the 54 truth reads it directly. This is the lossy view everything above the reader shares 55 with the other readers. 56 57 Record numbers become node indices unchanged, so the tree has a slot per record slot, 58 including the dead ones. That wastes the slots but keeps every parent reference valid 59 without a second mapping, and a dead slot is simply not marked used. 60 61 Safe to call while a scan runs: only records the reader has finished with are read, 62 and names are borrowed from the table's arenas rather than copied, so repeating this 63 allocates nothing. The table must therefore outlive the tree. 64 */ 65 to_tree :: proc(m: ^Mft, t: ^scan.Tree, p: ^Projection) -> scan.Error { 66 // Hard links are merged into the table in one go at the very end, so reading them 67 // before that would race the reader appending them, and would size the tree from 68 // a count that was still growing. 69 links := len(m.links) if mft_complete(m) else 0 70 71 // Records take slot per slot, extra names the range directly above them. Sizing 72 // for both up front is what lets a replay land on the same slots as the pass 73 // before it, so repeating one never has to empty the tree first. 74 if err := scan.reserve(t, u32(len(m.entries) + links)); err != nil { 75 return err 76 } 77 if p.settled == nil { 78 p.allocator = t.allocator 79 bits, err := make([]u64, (len(m.entries) + 63) / 64, p.allocator) 80 if err != nil { 81 return .Out_Of_Memory 82 } 83 p.settled = bits 84 } 85 86 used, bytes: u64 87 88 for i in 0 ..< u32(len(m.entries)) { 89 if marked(p.settled, i) { 90 used += 1 91 bytes += m.entries[i].allocated 92 continue 93 } 94 e := &m.entries[i] 95 // Only records the reader has finished with, so a name is never half written. 96 if !entry_published(e) || e.name == "" { 97 continue 98 } 99 n := scan.node(t, i) 100 // Borrowed, not copied: names live in the table's arenas and stay put for its 101 // life, so repeating this projection allocates nothing. 102 n.name = e.name 103 n.size = e.size 104 n.disk = e.allocated 105 106 flags := scan.Node_Flags{.Used} 107 if .Directory in e.flags { 108 flags |= {.Directory} 109 } 110 if .Reparse_Point in e.attributes { 111 flags |= {.Reparse} 112 } 113 parent, settled := entry_parent_settled(m, i) 114 n.parent = parent 115 if settled { 116 flags |= {.Settled} 117 mark(p.settled, i) 118 } 119 // Last, so a builder watching this tree never sees a node before its parent. 120 scan.node_publish(n, flags) 121 used += 1 122 bytes += e.allocated 123 } 124 125 // Extra names for a file already counted. They belong in the tree so a file can 126 // be found at every path it has, but their bytes must not be counted twice. Each 127 // sits at its ordinal above the record range, so a link written twice is written 128 // to the same slot. Links are merged when the scan ends, so this is empty 129 // until then. 130 for l, k in m.links[p.links_done:links] { 131 index := u32(len(m.entries) + p.links_done + k) 132 n := scan.node(t, index) 133 n.parent = l.parent 134 n.name = l.name 135 n.disk = m.entries[l.record].allocated 136 n.size = m.entries[l.record].size 137 scan.node_publish(n, {.Used, .Settled, .Extra_Name}) 138 } 139 p.links_done = links 140 141 t.root = RECORD_ROOT 142 if p.root_name != "" { 143 scan.node(t, RECORD_ROOT).name = p.root_name 144 } 145 t.nodes_done = used 146 t.bytes_done = bytes 147 return .None 148 } 149 150 @(private) 151 marked :: proc(b: []u64, i: u32) -> bool { 152 return b[i >> 6] & (1 << uint(i & 63)) != 0 153 } 154 155 @(private) 156 mark :: proc(b: []u64, i: u32) { 157 b[i >> 6] |= 1 << uint(i & 63) 158 }