The messages that start these jobs are always roughly the same shape. Something important has died, and the backup nobody quite got round to is now a topic of great interest. I have had to recover an array recently, and it turned into one of the more satisfying puzzles I have untangled in a while, so it deserves a proper write up. This one gets into the weeds on purpose mainly because it’s taken me months to get here. There is parity arithmetic, there is XOR, and there is a filesystem that lied about its own size, so if that is not your idea of a good evening you may want to look away now.
Names, hosts and file paths have been left out. The interesting bit is the method, not whose data it was.
The setup
A client had a file server on a hardware RAID 5. Three or four disks, controller managed, the sort of quietly reliable thing you forget exists until it stops existing. Then two disks failed close together. RAID 5 will carry on through one dead disk. It will not carry on through two, so the array went dark and stayed dark.
At which point somebody, meaning well, did the thing that makes my stomach drop. They built a brand new array straight over the top of the old disks. I understand the instinct. The server is down and creating a fresh array feels like doing something. The trouble is that it can scribble all over the exact thing you were hoping to save.
The one bit of luck is that the new array was created and then left alone. It got initialised, nobody wrote real data to it, and that made all the difference. The event count in its metadata was still sitting at zero, which is the tell that nothing had actually landed on it. The old filesystem was still underneath, mostly undisturbed.
What landed with me was a set of sector for sector images of the surviving disks, plus one rule I set before touching anything. Never write to the originals.
Rule one: make every write land somewhere disposable
Everything that follows happened on read only copies. The trick that makes this safe is a copy on write overlay. You attach each image as a read only loop device, then stack a device mapper snapshot on top whose backing store is a small scratch file. Reads fall through to the real image, and every write, including all the RAID metadata the tooling insists on stamping down, gets diverted into the scratch file. The image itself never changes a byte.
# one member: read only base loop, plus a COW overlay backed by a scratch file
base=$(losetup --read-only --find --show member.img)
truncate -s 8G cow.img
cow=$(losetup --find --show cow.img)
sectors=$(blockdev --getsz "$base")
# snapshot target: reads hit $base, writes go to $cow, 8 sector chunks, Persistent
dmsetup create ov0 --table "0 $sectors snapshot $base $cow P 8"
Do that for each member, assemble the array from the /dev/mapper/ovN overlays instead of the raw images, and you can be as reckless as you like. I got the geometry wrong several times, and each wrong guess was a dmsetup remove, a fresh scratch file, and another go. You get one copy of a dying disk. Everything else is derived, and the copy stays pristine.
Working out how the array fitted together
To reassemble a RAID 5 you need four parameters: the strip size, the disk order, the parity rotation, and the data offset. Get any one wrong and you get high entropy noise.
The leftover metadata from the rebuild was worse than useless, because it described the new array, not the old one. So I worked from the data. The parity layout on Linux is one of four algorithms, and the two that matter here place parity like this:
def parity_disk(stripe, N, layout):
# left layouts (asym=0, sym=2): parity walks backwards from the last disk
# right layouts (asym=1, sym=3): parity walks forwards from the first
return (N - 1) - (stripe % N) if layout in (0, 2) else stripe % N
def data_disks(P, N, layout):
if layout in (2, 3): # symmetric: data starts after parity
return [(P + 1 + k) % N for k in range(N - 1)]
return [d for d in range(N) if d != P] # asymmetric: data in disk order, skip P
A hardware controller of this vintage maps onto left symmetric, which is layout == 2. That still left the strip size and the disk order to find, and for that I leaned on NTFS itself.
NTFS keeps a master file table, and every record is exactly 1024 bytes with its own record number baked in at offset 0x2c. On a correctly assembled array those numbers march upward, one per kilobyte, for a very long way. On a wrongly assembled array the sequence shatters at the first strip boundary. So the scoring function is just: read a run of records off a candidate assembly and count how many stay in step.
def mft_coherence(readfn, base, n=64):
good, last = 0, None
for i in range(n):
rec = readfn(base + i * 1024, 1024)
if rec[:4] == b"FILE":
recno = int.from_bytes(rec[0x2c:0x30], "little")
good += 1 if (last is None or recno == last + 1) else 0
last = recno
else:
last = None
return good
Two facts fell straight out of the raw layout. The spacing of those record runs across the disks gave the strip size directly: 128 KiB. And the ratio between where record zero physically sat on its disk and where it belonged logically in the volume was almost exactly one half, which says two disks are carrying data, which means a three disk array. Score the three possible orderings and one of them lit up at 64 out of 64. The rest scored zero.
Assembled with the real kernel engine it looked like this, and it mounted:
mdadm --create /dev/md0 --level=5 --raid-devices=3 \
--chunk=128 --layout=left-symmetric \
--metadata=1.0 --assume-clean --bitmap=none --force \
/dev/mapper/ov0 /dev/mapper/ov1 /dev/mapper/ov2
A note on --metadata=1.0. That format keeps the superblock at the end of the member, so data starts at offset zero, which is what we want to mirror a hardware controller that parks its own housekeeping at the far end. And --assume-clean is doing a lot of load bearing work: it tells mdadm not to kick off a resync, because a resync would recompute parity and write it back, and on a recovery job the last thing you want is the array “helpfully” rewriting itself. Large files then read back with stable checksums, which is the moment you exhale.
The trap that ate most of the data
With the filesystem mounted, the obvious move is to copy everything off. I got about 45 GB out of roughly 540 before it drowned in read errors. Whole directories refused to open.
The reason is lovely, in a horrible way. On NTFS a directory is itself an on disk B tree, its index nodes stored in $INDEX_ALLOCATION runs somewhere out on the volume. A normal copy walks that tree: open a directory, read its index, recurse into each child. If a directory’s index runs happen to land in a damaged region, the read fails, and the tool skips the entire subtree beneath it. The files down there are fine, sitting a few clusters away in perfect health, but the signpost pointing at them is unreadable, so the walker never learns they exist. A few hundred wrecked index blocks were orphaning hundreds of gigabytes of healthy data. The map was torn, but the territory was fine.
Reading the table, not the tree
The master file table does not care about directories. It is a flat array of records, and each one carries the file name, a reference to its parent record, and the data runs that say exactly which clusters hold the bytes. Walk the table directly and you can reconstruct every path from those parent references, then pull each file by cluster address. The broken directory indexes never come into it.
I decoded the $DATA attribute’s run list myself for the analysis. The run list is a compact little format: each run is a header byte whose two nibbles give the lengths of the following length and offset fields, then the run length, then a signed delta added to the running logical cluster number. Offset zero means a sparse run.
def data_runs(attr, off):
p, lcn, runs = off, 0, []
while attr[p]:
ls, os = attr[p] & 0x0F, attr[p] >> 4 # nibbles: len size, offset size
p += 1
length = int.from_bytes(attr[p:p+ls], "little"); p += ls
if os: # normal run
lcn += int.from_bytes(attr[p:p+os], "little", signed=True); p += os
runs.append((lcn, length))
else: # sparse run, no backing clusters
runs.append((None, length))
p += os
return runs
For the bulk extraction I pointed a proper forensic table walker at the volume. It enumerated the whole tree, over a million entries, and pulled every file it could reach by address rather than by name. The result was 410,190 files recovered, against the 45 GB the directory walk had managed. Same disks, same damage, an order of magnitude more data, purely by not depending on the one structure that was broken.
Counting exactly what was gone
A recovery is finished when you can say precisely what did not come back. NTFS tracks allocation in $Bitmap, one bit per cluster, so I read that attribute and counted set bits beyond the last cluster the three disks could physically back. Population count on a byte array is embarrassingly simple and completely conclusive:
boundary = 244_160_448 # first cluster the 3 disk array cannot reach
cluster = 4096
used_total = sum(bin(b).count("1") for b in bitmap)
lost = sum(bin(b).count("1") for b in bitmap[boundary // 8:])
print(f"{used_total * cluster / 2**30:.1f} GiB allocated")
print(f"{lost * cluster / 2**30:.1f} GiB beyond the array (gone)")
That printed 540.4 GiB used and 147.1 GiB gone, about 27 percent, with the other 393.3 GiB sitting safely in the region the disks could reach. Then I walked every record’s run list against that same boundary to turn “damaged” into a precise list, because “damaged” flatters it. Of roughly 55,000 affected files, about 43,000 had their very first data run already past the boundary, so they were a total loss. Around 13,000 straddled it, and a good number of those were more than 90 percent intact, their readable portion already sitting in the recovered pile with only a tail missing.
The bit that kept me up: a filesystem too big for its disks
Then the puzzle. The boot sector was adamant the volume held 2,923,558,911 sectors, which is 1.36 TiB. But three disks of this size, arranged as I had proven, come to about 931 GiB. You cannot format a filesystem larger than the device under it, so how did it believe it was half a terabyte bigger than the disks that were reconstructing it so cleanly?
The arithmetic closes one way. Take the sectors the volume spans, divide by the number of data disks, and see what member size falls out:
(partition_start + volume_sectors) = 262144 + 2,923,558,911 = 2,923,821,055 sectors
/ 2 data disks = 1,461,910,527 sectors
x 512 = 748.5 GB per member
That is not the 500 GB these disks are. It is the size of a fourth member. With disks this size, 1.36 TiB is exactly three data disks in a four disk RAID 5, not two in a three disk one. The volume had been born on a four disk array. The double disk failure had not just knocked it offline, it had taken a whole member’s worth of data down with it, and what I was reconstructing so tidily was the slice that survived across three disks.
“Surely three disks can rebuild a four disk array”
In principle, yes. RAID 5 survives one lost member, so any three of four rebuild the fourth from parity, which is nothing more than the XOR of the survivors. If these three were three of four, the missing quarter would be right there. So I tested it, because a comforting theory deserves the roughest handling.
The reconstruction of an absent member is genuinely just this: when the chunk you want lives on the missing disk, read the parity chunk and the other data chunks in that stripe and XOR them together.
def read_chunk(roles, d, N, layout):
stripe, slot = divmod(d, N - 1)
P = parity_disk(stripe, N, layout)
dd = data_disks(P, N, layout)
target, off = dd[slot], stripe * CHUNK
if roles[target] is not None: # member present: read straight
return pread(roles[target], off)
acc = int.from_bytes(pread(roles[P], off), "big") # rebuild: parity XOR other data
for k, disk in enumerate(dd):
if k != slot:
acc ^= int.from_bytes(pread(roles[disk], off), "big")
return acc.to_bytes(CHUNK, "big")
I swept every degraded four disk arrangement: the missing member in each of the four slots, every ordering of the three real disks, all four parity layouts. Ninety six combinations, scored by the same MFT coherence function. Every single one came back zero.
That result is only worth anything if the XOR path is correct, and my own code is not above suspicion. So I checked the checker against ground truth. Take the known good three disk array, mark one member absent, rebuild it purely from parity, and see whether the reconstructed read still lands a coherent MFT:
all three present MFT coherence: 64/64
member 0 dropped, rebuilt MFT coherence: 64/64
member 1 dropped, rebuilt MFT coherence: 64/64
member 2 dropped, rebuilt MFT coherence: 64/64
Perfect every time, so the parity maths is sound. Finally, to get my code out of the question entirely, I rebuilt the degraded four disk arrays with the kernel’s own RAID engine and scanned the resulting block devices:
mdadm --create /dev/md9 --level=5 --raid-devices=4 \
--chunk=128 --layout=left-symmetric \
--metadata=1.0 --assume-clean --bitmap=none --force \
/dev/mapper/ov0 missing /dev/mapper/ov1 /dev/mapper/ov2
Same answer every time. The three disks reconstruct beautifully as a three disk set and not at all as three of four. And that is the crux: a set of disks can satisfy the parity equations of a three disk array, or it can be a valid three of four slice of a four disk array, but never both, because the stripe widths are different and the two layouts scatter the bytes differently. These disks were provably the former. The double failure had not left the volume one disk short of whole. It had left a self consistent trio holding two disks’ worth of data, with an entire third disk’s contribution having no representation anywhere in the surviving parity. XOR rebuilds one absent member. It cannot conjure back data that was never in the set to begin with. The only thing that brings that 147 GB home is the physical fourth disk, if it still exists in a drawer somewhere.
The scripts, in full
The snippets above are lifted from three small tools. Here they are complete, cleaned up and anonymised, in case they are useful to anyone staring at a similar mess. They are all strictly read only. Nothing here writes to a member image.
The first is the reconstruction engine itself. It emulates a RAID 5 in software, including rebuilding one missing member on the fly from parity, so you can sweep every geometry and score it by MFT coherence without assembling a single real array. Point it at the member images in a candidate order and it prints the best scoring geometries.
#!/usr/bin/env python3
"""
raid5_reconstruct.py
Reconstruct and verify a RAID 5 volume from member images, entirely read only.
The array is emulated in software, including degraded reconstruction of one
missing member via parity XOR, so geometry is swept without assembling anything.
Scoring is by NTFS $MFT coherence: MFT records are 1024 bytes and carry a
sequential record number at offset 0x2c, so a correct assembly yields a long run
of consecutively numbered FILE records where a wrong one yields none.
"""
import itertools, struct, sys
CHUNK = 128 * 1024 # strip size in bytes
SECTOR = 512
# --- RAID 5 address mapping (Linux mdadm layout numbers) -------------------
# layout: 0 left-asym, 1 right-asym, 2 left-sym, 3 right-sym
def parity_disk(stripe, N, layout):
return (N - 1) - (stripe % N) if layout in (0, 2) else stripe % N
def data_disks(P, N, layout):
if layout in (2, 3): # symmetric: data follows parity, wrapping
return [(P + 1 + k) % N for k in range(N - 1)]
return [d for d in range(N) if d != P] # asymmetric: ascending disk order, skip P
# --- member reads ----------------------------------------------------------
def pread(fh, off, n=CHUNK):
fh.seek(off)
b = fh.read(n)
return b + bytes(n - len(b)) if len(b) < n else b
def read_chunk(roles, d, N, layout):
"""Logical data chunk d. roles[i] is a file handle, or None for a missing member."""
stripe, slot = divmod(d, N - 1)
P = parity_disk(stripe, N, layout)
dd = data_disks(P, N, layout)
target, off = dd[slot], stripe * CHUNK # data offset 0: phys = stripe * CHUNK
if roles[target] is not None:
return pread(roles[target], off)
acc = int.from_bytes(pread(roles[P], off), "big") # rebuild = parity XOR other data
for k, disk in enumerate(dd):
if k != slot:
acc ^= int.from_bytes(pread(roles[disk], off), "big")
return acc.to_bytes(CHUNK, "big")
def read_logical(roles, off, length, N, layout):
out = bytearray()
while length:
d, within = divmod(off, CHUNK)
take = min(CHUNK - within, length)
out += read_chunk(roles, d, N, layout)[within:within + take]
off += take; length -= take
return bytes(out)
# --- NTFS coherence scoring ------------------------------------------------
def mft_coherence(roles, N, layout, mft_off, n=64):
blob = read_logical(roles, mft_off, n * 1024, N, layout)
good, last = 0, None
for i in range(n):
rec = blob[i*1024:(i+1)*1024]
if rec[:4] == b"FILE":
recno = int.from_bytes(rec[0x2c:0x30], "little")
good += 1 if (last is None or recno == last + 1) else 0
last = recno
else:
last = None
return good
# --- geometry sweep --------------------------------------------------------
LAYOUT = {0: "left-asym", 1: "right-asym", 2: "left-sym", 3: "right-sym"}
def sweep(members, N, part_lba, mft_lcn, spc=8, bps=SECTOR):
"""members: dict name -> handle. N: disks in the candidate array.
If len(members) == N-1 the missing slot is swept through every position."""
slots = list(members) + ["missing"] * (N - len(members))
mft_off = part_lba * bps + mft_lcn * spc * bps
results = []
for arrangement in sorted(set(itertools.permutations(slots))):
for layout in (0, 1, 2, 3):
roles = [members.get(x) if x != "missing" else None for x in arrangement]
results.append((mft_coherence(roles, N, layout, mft_off), arrangement, layout))
results.sort(key=lambda r: -r[0])
return results
if __name__ == "__main__":
# usage: raid5_reconstruct.py N part_lba mft_lcn member0.img member1.img ...
N = int(sys.argv[1])
part_lba = int(sys.argv[2])
mft_lcn = int(sys.argv[3])
members = {f"d{i}": open(p, "rb") for i, p in enumerate(sys.argv[4:])}
for score, arr, layout in sweep(members, N, part_lba, mft_lcn)[:12]:
print(f"{score:3d}/64 {','.join(arr):26s} {LAYOUT[layout]}")
Run it with N equal to the number of images to solve a present array, or with N one larger than the number of images to sweep every degraded geometry with the missing member reconstructed from parity. That second mode is how I proved the disks were not three of four.
The second tool parses a raw $MFT dump, decodes each file’s data runs, and sorts every file into fully lost, partly lost, or fine, reconstructing paths from the parent references so the output is human readable.
#!/usr/bin/env python3
"""
mft_damage.py
Parse a raw $MFT dump, decode each file's $DATA run list, and classify every
file by whether its data lies within the region the array can physically back.
Paths are reconstructed from $FILE_NAME parent references. Read only throughout.
"""
import struct, sys
REC = 1024
BOUNDARY = 244_160_448 # first cluster the surviving array cannot reach
CLUSTER = 4096
def fixup(rec):
"""Apply the NTFS update sequence array (fixups) before reading a record."""
uo, uc = struct.unpack_from("<H", rec, 4)[0], struct.unpack_from("<H", rec, 6)[0]
if not uo or not uc:
return rec
b = bytearray(rec)
for i in range(1, uc): # restore last 2 bytes of each sector
dst, src = i*512 - 2, uo + i*2
if dst + 2 <= len(b) and src + 2 <= len(rec):
b[dst:dst+2] = rec[src:src+2]
return bytes(b)
def runs(attr, off):
"""Decode a non-resident run list into (lcn, length, sparse) tuples."""
p, lcn, out = off, 0, []
while p < len(attr) and attr[p]:
ls, os = attr[p] & 0x0F, attr[p] >> 4 # nibbles: length size, offset size
p += 1
if ls == 0 or p + ls + os > len(attr):
break
length = int.from_bytes(attr[p:p+ls], "little"); p += ls
if os:
lcn += int.from_bytes(attr[p:p+os], "little", signed=True); p += os
out.append((lcn, length, False))
else:
out.append((None, length, True)) # sparse run, no backing clusters
return out
def parse(mft):
names, data = {}, {}
for i in range(len(mft) // REC):
rec = mft[i*REC:(i+1)*REC]
if rec[:4] != b"FILE":
continue
rec = fixup(rec)
flags = struct.unpack_from("<H", rec, 22)[0]
if not flags & 1: # record not in use
continue
is_dir = bool(flags & 2)
p = struct.unpack_from("<H", rec, 20)[0] # offset to first attribute
name = parent = None
runlist = []
while p + 8 <= len(rec):
atype = struct.unpack_from("<I", rec, p)[0]
if atype == 0xFFFFFFFF:
break
alen = struct.unpack_from("<I", rec, p + 4)[0]
if alen == 0 or p + alen > len(rec):
break
nonres = rec[p + 8]
if atype == 0x30: # $FILE_NAME, always resident
c = p + struct.unpack_from("<H", rec, p + 20)[0]
par = struct.unpack_from("<Q", rec, c)[0] & 0xFFFFFFFFFFFF
nlen, ns = rec[c+64], rec[c+65]
nm = rec[c+66:c+66+nlen*2].decode("utf-16le", "replace")
if name is None or ns != 2: # prefer the long name over DOS 8.3
name, parent = nm, par
elif atype == 0x80 and nonres: # $DATA, non-resident
runlist += runs(rec, p + struct.unpack_from("<H", rec, p + 32)[0])
p += alen
if name is not None:
names[i] = (name, parent, is_dir)
if runlist and not is_dir:
data[i] = runlist
return names, data
def path(names, ino):
parts, seen, cur = [], set(), ino
while cur in names and cur not in seen and cur != 5: # inode 5 is the root
seen.add(cur)
nm, par, _ = names[cur]
parts.append(nm); cur = par
return "/" + "/".join(reversed(parts))
def classify(data):
fully, partial = [], []
for ino, rl in data.items():
below = above = 0
for lcn, length, sparse in rl:
if sparse:
continue
if lcn >= BOUNDARY:
above += length
elif lcn + length - 1 >= BOUNDARY: # run straddles the boundary
below += BOUNDARY - lcn
above += lcn + length - BOUNDARY
else:
below += length
if above:
(fully if below == 0 else partial).append((ino, below, above))
return fully, partial
if __name__ == "__main__":
names, data = parse(open(sys.argv[1], "rb").read())
fully, partial = classify(data)
gib = lambda clusters: clusters * CLUSTER / 2**30
print(f"in-use files with data : {len(data)}")
print(f"fully lost : {len(fully):6d} ({gib(sum(a for _,_,a in fully)):.1f} GiB)")
print(f"partial : {len(partial):6d} "
f"({gib(sum(b for _,b,_ in partial)):.1f} GiB present, "
f"{gib(sum(a for _,_,a in partial)):.1f} GiB lost tails)")
print(f"partial >=90% intact : {sum(1 for _,b,a in partial if b/(b+a) >= 0.9)}")
with open("fully_lost.txt", "w") as out:
for ino, _, above in sorted(fully):
out.write(f"{path(names, ino)}\t{above*CLUSTER} bytes\n")
The third is barely a program at all, but it is the one that turns hand waving into a number. It reads the $Bitmap attribute, one bit per cluster, and population counts the set bits beyond the boundary the surviving disks can reach.
#!/usr/bin/env python3
"""
bitmap_loss.py
Read the NTFS $Bitmap (one bit per cluster) and count allocated clusters beyond
the last cluster the surviving array can physically back. That is the exact,
to the cluster, quantity of unrecoverable data.
"""
import sys
CLUSTER = 4096
BOUNDARY = 244_160_448 # first cluster beyond the surviving array
bitmap = open(sys.argv[1], "rb").read() # $Bitmap, dumped read only
used = sum(bin(b).count("1") for b in bitmap)
lost = sum(bin(b).count("1") for b in bitmap[BOUNDARY // 8:])
g = lambda c: c * CLUSTER / 2**30
print(f"allocated total : {used:>13,} clusters = {g(used):8.1f} GiB")
print(f"beyond array : {lost:>13,} clusters = {g(lost):8.1f} GiB (lost)")
print(f"recoverable : {used-lost:>13,} clusters = {g(used-lost):8.1f} GiB")
The boundary constant in the last two is the only number tied to this particular array: it is the count of clusters the surviving disks physically cover, worked out from the member size and the strip layout. Everything else is generic NTFS and generic RAID 5.
What I took away from it
Copy read only, onto overlays. losetup --read-only under a dmsetup snapshot means every experiment is reversible and the original never changes. It is the cheapest insurance in the business.
--assume-clean on every create. On a recovery array you never want a resync, because a resync writes computed parity back over your evidence.
When a rebuild appears to fix a dead array, stop. Recreating an array over failed disks is exactly how a recoverable incident becomes an unrecoverable one. The only reason this ended well is a metadata event count still sitting at zero.
Do not copy by directory when the filesystem is hurt. Path walkers inherit every broken $INDEX_ALLOCATION and silently abandon the healthy files behind it. Walking the MFT by parent reference and pulling files by data run turned 45 GB into 410,000 files.
Measure the loss with the bitmap, do not eyeball it. One population count over $Bitmap past the array boundary turned “some things are missing” into “147.1 GiB, here are exactly which files, and here are the 13,000 that are actually mostly fine.”
And test the theory you want to be true the hardest, with your own code validated against ground truth and then taken out of the loop entirely. “Three disks should rebuild it” was the outcome everyone was hoping for, which is precisely why it earned an emulator, a validated XOR path, and the kernel’s own engine before I would rule it out.
Three quarters of the data walked back out of the door. The last quarter went down with the disks that died, before anyone thought to call me. Sometimes the deliverable is not the bytes you save but a clean, honest account of what is gone and why, and that is worth having too. But; this might not be the end of the story; I may get the “dead” disk to play with soon and will provide an update in due course.
This site uses Akismet to reduce spam. Learn how your comment data is processed.
Leave a Reply