commit 58ce9575b74e8f145475b7311ccd556336771733
parent 7890196b13854057d3820bd10a6b118af4f03107
Author: Jack Mordaunt <jackmordaunt.dev@gmail.com>
Date: Fri, 18 Sep 2026 07:53:25 -0400
ntfs: count allocated clusters from $Bitmap
Nothing so far checked the per-file sums against reality: if the run list
decoding dropped or double counted extents, the total would simply be wrong
with no way to tell. $Bitmap holds one bit per cluster and is maintained by
the file system itself, so counting its set bits gives an independent total
to compare against. Padding bits past the last cluster are excluded, and
reads are rounded up to whole clusters because raw volume reads must cover
whole sectors. The extent reader can now seek backwards, since record 6 sits
at the start of a table it has already streamed past.
Diffstat:
4 files changed, 145 insertions(+), 0 deletions(-)
diff --git a/ntfs/bitmap.odin b/ntfs/bitmap.odin
@@ -0,0 +1,114 @@
+package ntfs
+
+import "core:math/bits"
+import "core:mem"
+
+/*
+Count the volume's allocated clusters from $Bitmap, which holds one bit per cluster,
+set meaning allocated.
+
+This is the file system's own account of used space, arrived at without looking at any
+file. Summing every file's run list should reproduce it almost exactly, so a large
+divergence points at the run list decoding being wrong rather than at space having
+gone missing. Files small enough to live inside their MFT record occupy no clusters
+and so appear in neither figure; their bytes are counted under $MFT.
+
+`mft` must be an extent reader over the MFT's own run list. `scratch` is reused for
+the record read and then for the bitmap stream, so it must hold at least one record
+and its length must be a whole number of clusters.
+*/
+@(private)
+read_bitmap_clusters :: proc(
+ mft: ^Extent_Reader,
+ boot: Boot_Sector,
+ scratch: []byte,
+ allocator: mem.Allocator,
+) -> (clusters: u64, err: Error) {
+ record_size := int(boot.record_size)
+ cluster := u64(boot.bytes_per_cluster)
+ if len(scratch) < record_size || u64(len(scratch)) < cluster {
+ return 0, .Short_Read
+ }
+
+ rec := scratch[:record_size]
+ if read_err := read_logical(mft, u64(RECORD_BITMAP) * u64(record_size), rec); read_err != nil {
+ return 0, read_err
+ }
+ if fix_err := apply_fixups(rec); fix_err != nil {
+ return 0, fix_err
+ }
+ if .In_Use not_in record_header(rec).flags {
+ return 0, .Bad_Record
+ }
+
+ runs: []Run
+ data_size: u64
+ found := false
+ it := attributes(rec)
+ for {
+ a, ok := next_attribute(&it)
+ if !ok {
+ break
+ }
+ if a.type != .Data || len(a.name) != 0 || !a.non_resident || a.lowest_vcn != 0 {
+ continue
+ }
+ decoded, run_err := decode_runlist(a.runlist, 0, allocator)
+ if run_err != nil {
+ return 0, run_err
+ }
+ runs = decoded
+ data_size = a.data_size
+ found = true
+ break
+ }
+ if !found {
+ return 0, .Bad_Record
+ }
+ defer delete(runs, allocator)
+
+ // Bits past the last cluster are padding that NTFS leaves set, so stop counting at
+ // the volume's real cluster count instead of trusting the attribute length.
+ total := boot.total_sectors / u64(boot.sectors_per_cluster)
+ covered := runlist_clusters(runs) * cluster
+ want := (total + 7) / 8
+ limit := min(min(want, data_size), covered)
+ tail := uint(total % 8)
+ if limit < want {
+ tail = 0 // the last byte is out of reach, so there is nothing to mask
+ }
+
+ // Raw volume reads must cover whole sectors, so read whole clusters and count only
+ // the prefix that maps to real clusters.
+ read_limit := min((limit + cluster - 1) / cluster * cluster, covered)
+
+ br := Extent_Reader{v = mft.v, runs = runs, cluster = cluster}
+ for offset: u64 = 0; offset < read_limit; {
+ n := int(min(u64(len(scratch)), read_limit - offset))
+ if read_err := read_logical(&br, offset, scratch[:n]); read_err != nil {
+ return 0, read_err
+ }
+ if offset < limit {
+ countable := int(min(u64(n), limit - offset))
+ if offset + u64(countable) == limit && tail != 0 {
+ scratch[countable - 1] &= byte(1 << tail) - 1
+ }
+ clusters += count_set_bits(scratch[:countable])
+ }
+ offset += u64(n)
+ }
+ return clusters, .None
+}
+
+// Population count over a byte slice, eight bytes at a time.
+@(private)
+count_set_bits :: proc "contextless" (b: []byte) -> (n: u64) {
+ i := 0
+ for ; i + 8 <= len(b); i += 8 {
+ n += bits.count_ones((^u64)(raw_data(b[i:]))^)
+ }
+ for ; i < len(b); i += 1 {
+ n += u64(bits.count_ones(b[i]))
+ }
+ return
+}
diff --git a/ntfs/mft.odin b/ntfs/mft.odin
@@ -38,6 +38,9 @@ Mft_Stats :: struct {
// of their own, so their bytes are charged to $MFT rather than to their directory.
resident_files: u64,
resident_bytes: u64,
+ // Clusters $Bitmap reports as allocated; 0 when it could not be read. This is the
+ // file system's own total, independent of the per-file sums.
+ allocated_clusters: u64,
}
Mft :: struct {
diff --git a/ntfs/ntfs_test.odin b/ntfs/ntfs_test.odin
@@ -476,6 +476,24 @@ test_path :: proc(t: ^testing.T) {
testing.expect_value(t, mft_path(&m, 66, context.temp_allocator), `<orphan>\stale.tmp`)
}
+// ---- bitmap -------------------------------------------------------------------------
+
+@(test)
+test_count_set_bits :: proc(t: ^testing.T) {
+ testing.expect_value(t, count_set_bits(nil), u64(0))
+ testing.expect_value(t, count_set_bits([]byte{0xFF}), u64(8))
+
+ // Nine bytes exercises both the eight-byte chunk loop and the trailing bytes.
+ nine := []byte{0xFF, 0x00, 0x0F, 0xF0, 0x01, 0x80, 0xAA, 0x55, 0x03}
+ testing.expect_value(t, count_set_bits(nine), u64(28))
+
+ all := make([]byte, 64, context.temp_allocator)
+ for i in 0 ..< len(all) {
+ all[i] = 0xFF
+ }
+ testing.expect_value(t, count_set_bits(all), u64(512))
+}
+
// ---- resident data ------------------------------------------------------------------
@(test)
diff --git a/ntfs/reader.odin b/ntfs/reader.odin
@@ -157,6 +157,12 @@ read_mft_from_volume :: proc(v: ^Volume, opts := Read_Options{}, allocator := co
}
}
}
+ // $Bitmap is the file system's own count of used clusters, which checks the sums
+ // built above. Failing to read it costs nothing else, so the table still stands.
+ if c, bitmap_err := read_bitmap_clusters(&reader, boot, buf, allocator); bitmap_err == nil {
+ m.stats.allocated_clusters = c
+ }
+
ok = true
return m, .None
}
@@ -176,6 +182,10 @@ read_logical :: proc(r: ^Extent_Reader, offset: u64, buf: []byte) -> Error {
for done < len(buf) {
pos := offset + u64(done)
vcn := pos / r.cluster
+ // The cursor only walks forward, so rewind it when a read goes backwards.
+ if r.cursor >= len(r.runs) || r.runs[r.cursor].vcn > vcn {
+ r.cursor = 0
+ }
for r.cursor < len(r.runs) && r.runs[r.cursor].vcn + r.runs[r.cursor].length <= vcn {
r.cursor += 1
}
