Apple's open-source XNU kernel on Android phones: its own loader and drivers, Metal on the Adreno. Runs from RAM; a reboot gives the phone back to Android.
C
#!/usr/bin/env python3
"""Build an APFS container from directories: the port's own read-only volumes, as images.
usage: mkapfs.py -o IMAGE [-z [--plain DIR]...] [--time SECONDS] [--slack BLOCKS] NAME=DIR[,manifest=FILE] [NAME=DIR ...]
Each NAME=DIR becomes one volume of the container (volume 0 first), case-sensitive and
normalization-insensitive like the Darwin volumes, unencrypted, read-only content laid out once.
Permission bits and symbolic links are taken from DIR; everything is owned by root:wheel
unless a manifest says otherwise (lines of: mode in octal with the type bits, uid, gid, path,
[link target]; sysimage/system.manifest is one; a directory or symbolic link that is only in the
manifest is made). With -z a regular file is stored compressed when that makes it smaller,
as Apple stores most of the Darwin root volume: a small one whole in its decmpfs attribute (type
3, no block of its own at all), a bigger one in 64 KB zlib pieces in its resource fork (type 4); but not what is under a --plain DIR (relative to the volume's root), which stays as
it is and in one piece -- the firmware a driver uses where it lies in memory. Times are all --time (default: 2023-05-12, the Darwin userland 16.5 images'), so the same
input gives the same image byte for byte.
The image is what Apple's newfs_apfs and a single transaction would leave (one checkpoint,
transaction 1): the container superblock, the checkpoint (its map, the space manager with
its internal pool, the reaper, the two free queues), the container's object map, and per
volume its superblock, object map, file-system tree, extent-reference tree and an empty
snapshot tree; then the files' data. What the layout of the space manager has to be is
taken from linux-apfs/apfsprogs' mkapfs (and checked with its apfsck, which has to find the
image clean: tools/apfs/check-image.sh). Hard links are not made: a name is a file.
"""
import argparse
import concurrent.futures
import hashlib
import os
import stat
import struct
import sys
import unicodedata
import zlib
BS = 4096
XID = 1
OID_NX = 1
OID_RESERVED = 1024 # the first object id that is not reserved
ROOT_DIR_PARENT, ROOT_DIR_INO, PRIV_DIR_INO = 1, 2, 3
MIN_USER_INO = 16
# object types
T_NX, T_BTREE, T_BTNODE, T_SPACEMAN, T_CAB, T_CIB = 0x1, 0x2, 0x3, 0x5, 0x6, 0x7
T_FREE_QUEUE, T_OMAP, T_CPMAP, T_FS, T_FSTREE, T_BLOCKREF, T_SNAPMETA, T_REAPER = 0x9, 0xb, 0xc, 0xd, 0xe, 0xf, 0x10, 0x11
VIRTUAL, EPHEMERAL, PHYSICAL = 0x0, 0x80000000, 0x40000000
# b-tree node flags, tree flags
BTNODE_ROOT, BTNODE_LEAF, BTNODE_FIXED = 0x1, 0x2, 0x4
BTREE_ALLOW_GHOSTS, BTREE_EPHEMERAL, BTREE_PHYSICAL, BTREE_KV_NONALIGNED = 0x4, 0x8, 0x10, 0x40
BTOFF_INVALID = 0xffff
# file-system records
J_SNAP_METADATA, J_EXTENT, J_INODE, J_XATTR, J_SIBLING_LINK, J_DSTREAM_ID = 1, 2, 3, 4, 5, 6
J_FILE_EXTENT, J_DIR_REC = 8, 9
DT_DIR, DT_REG, DT_LNK = 4, 8, 10
INODE_HAS_RSRC_FORK, INODE_NO_RSRC_FORK, INODE_HAS_UNCOMPRESSED_SIZE = 0x4000, 0x8000, 0x40000
UF_COMPRESSED = 0x20
INO_EXT_TYPE_NAME, INO_EXT_TYPE_DSTREAM = 4, 8
XF_DO_NOT_COPY, XF_SYSTEM_FIELD = 0x2, 0x20
XATTR_DATA_STREAM, XATTR_DATA_EMBEDDED, XATTR_FS_OWNED = 0x1, 0x2, 0x4
KIND_NEW = 1
DECMPFS_MAGIC = 0x636d7066 # 'cmpf'
DECMPFS_ZLIB_ATTR, DECMPFS_ZLIB_RSRC = 3, 4
XATTR_MAX_EMBEDDED = 3804 # the most an attribute's value can hold in its record
PIECE = 65536
SM_BITMAP_XID_OFF = 0x150 # (apfsprogs' mkapfs: from a test image)
IP_BM_TX_MULTIPLIER = 16
IP_BM_INDEX_INVALID = 0xffff
def fletcher64(block):
"""The checksum of an object: Fletcher-64 over its 32-bit words after the first eight bytes."""
words = struct.unpack_from('<%dI' % ((len(block) - 8) // 4), block, 8)
s1 = s2 = 0
for w in words:
s1 = (s1 + w) % 0xffffffff
s2 = (s2 + s1) % 0xffffffff
c1 = 0xffffffff - ((s1 + s2) % 0xffffffff)
c2 = 0xffffffff - ((s1 + c1) % 0xffffffff)
return (c2 << 32) | c1
def seal(obj, oid, otype, subtype=0):
"""Fill in an object's header (oid, transaction, type) and its checksum, in place."""
struct.pack_into('<QQII', obj, 8, oid, XID, otype, subtype)
struct.pack_into('<Q', obj, 0, fletcher64(obj))
_CRC32C = []
for _i in range(256):
_c = _i
for _ in range(8):
_c = (_c >> 1) ^ 0x82F63B78 if _c & 1 else _c >> 1
_CRC32C.append(_c)
def name_hash(name):
"""A directory record's hash: CRC-32C (no final inversion) over the name decomposed, as UTF-32."""
h = 0xffffffff
for ch in unicodedata.normalize('NFD', name):
for b in struct.pack('<I', ord(ch)):
h = (h >> 8) ^ _CRC32C[(h ^ b) & 0xff]
return h & 0x3fffff
def div_up(a, b):
return (a + b - 1) // b
# ---------------------------------------------------------------------- the input tree
class Node:
def __init__(self, name, mode, source=None, target=None):
self.name = name # str
self.mode = mode # st_mode
self.uid = self.gid = 0
self.source = source # a regular file's path on this machine
self.target = target # a symbolic link's target, bytes
self.children = {} # name -> Node, for a directory
self.oid = 0
def read_tree(path, name=''):
st = os.lstat(path)
if stat.S_ISDIR(st.st_mode):
node = Node(name, st.st_mode)
for entry in sorted(os.listdir(path)):
child = read_tree(os.path.join(path, entry), entry)
if child is not None:
node.children[entry] = child
return node
if stat.S_ISREG(st.st_mode):
return Node(name, st.st_mode, source=path)
if stat.S_ISLNK(st.st_mode):
return Node(name, st.st_mode, target=os.fsencode(os.readlink(path)))
return None # device nodes, FIFOs, sockets: /dev is devfs
def apply_manifest(root, manifest):
for raw in open(manifest, 'rb'):
fields = raw.rstrip(b'\n').split(b'\t')
if len(fields) < 4 or not fields[3]:
continue
mode, uid, gid = int(fields[0], 8), int(fields[1]), int(fields[2])
parts = fields[3].decode('utf-8', 'surrogateescape').split('/')
node = root
for part in parts[:-1]:
node = node.children.get(part)
if node is None or not stat.S_ISDIR(node.mode):
break
else:
leaf = node.children.get(parts[-1])
if leaf is None:
if stat.S_ISDIR(mode):
leaf = node.children[parts[-1]] = Node(parts[-1], mode)
elif stat.S_ISLNK(mode) and len(fields) > 4:
leaf = node.children[parts[-1]] = Node(parts[-1], mode, target=fields[4])
else:
continue
# (owner, group and permissions; not the kind: a link this tree has where the manifest
# says directory -- the system image's LaunchDaemons -- stays a link)
if stat.S_IFMT(leaf.mode) == stat.S_IFMT(mode):
leaf.mode, leaf.uid, leaf.gid = mode, uid, gid
# ---------------------------------------------------------------------- b-tree nodes
class Tree:
"""A b-tree laid out from records already in order, leaves first, full nodes."""
def __init__(self, subtype, storage, fixed=None, tree_flags=0):
self.subtype = subtype # T_FSTREE, T_OMAP, ...
self.storage = storage # VIRTUAL or PHYSICAL
self.fixed = fixed # (key_size, val_size) for a tree of fixed sizes
self.tree_flags = tree_flags
self.levels = [] # [[(records, ...)]] per level, leaves first
@staticmethod
def entry_size(fixed, klen, vlen):
return (4 if fixed else 8) + klen + vlen
def plan(self, records):
"""records: [(key bytes, value bytes)] in order. Splits them into nodes (no addresses yet)."""
self.records = records
self.levels = []
level = self._pack(records, leaf=True)
self.levels.append(level)
while len(level) > 1:
index = [(node[0][0], b'\0' * 8) for node in level] # child pointers come later
level = self._pack(index, leaf=False)
self.levels.append(level)
return sum(len(lv) for lv in self.levels)
def toc_len(self, n, leaf):
"""The table of contents for n entries: a node of a fixed-size tree has its whole table up
front (as newfs_apfs and mkapfs make it), any other a multiple of 8 entries."""
if self.fixed is not None:
# (index nodes too, their values being 8-byte child pointers -- apfsck insists)
ks, vs = self.fixed
return ((BS - 56) // (ks + (vs if leaf else 8) + 4)) * 4
entry = 4 if self.fixed is not None else 8
return div_up(max(n, 8), 8) * 8 * entry
def _pack(self, records, leaf):
nodes, cur, kv = [], [], 0
for k, v in records:
# every node is sized as though it were the root, with its 40-byte btree_info
if cur and 56 + self.toc_len(len(cur) + 1, leaf) + kv + len(k) + len(v) > BS - 40:
nodes.append(cur)
cur, kv = [], 0
cur.append((k, v))
kv += len(k) + len(v)
nodes.append(cur)
return nodes
def node_count(self):
return sum(len(lv) for lv in self.levels)
def build(self, addrs, oids):
"""Make the nodes. addrs: block address of every node, root first (top level down);
oids: their object ids (= addresses for a physical tree). Returns {address: block}."""
out = {}
flat = []
for lvl in range(len(self.levels) - 1, -1, -1):
for i in range(len(self.levels[lvl])):
flat.append((lvl, i))
where = {key: (addrs[n], oids[n]) for n, key in enumerate(flat)}
longest_k = max((len(k) for k, v in self.records), default=0)
longest_v = max((len(v) for k, v in self.records), default=0)
for (lvl, i), (addr, oid) in where.items():
recs = self.levels[lvl][i]
if lvl > 0:
# the child pointers: the children's ids (virtual) or addresses (physical)
first_child = sum(len(n) for n in self.levels[lvl - 1][:0])
children_before = sum(len(self.levels[lvl][j]) for j in range(i))
recs = [(k, struct.pack('<Q', where[(lvl - 1, children_before + c)][1]))
for c, (k, _) in enumerate(recs)]
is_root = (lvl == len(self.levels) - 1)
out[addr] = self._node(recs, lvl, is_root, oid, longest_k, longest_v)
return out
def _node(self, recs, level, is_root, oid, longest_k, longest_v):
block = bytearray(BS)
fixed = self.fixed is not None
leaf = level == 0
flags = (BTNODE_ROOT if is_root else 0) | (BTNODE_LEAF if leaf else 0) | (BTNODE_FIXED if fixed else 0)
val_end = BS - (40 if is_root else 0)
toc_len = self.toc_len(len(recs), leaf)
key_base = 56 + toc_len
koff = 0
voff = 0
for n, (k, v) in enumerate(recs):
block[key_base + koff:key_base + koff + len(k)] = k
voff += len(v)
block[val_end - voff:val_end - voff + len(v)] = v
if fixed:
struct.pack_into('<HH', block, 56 + 4 * n, koff, voff)
else:
struct.pack_into('<HHHH', block, 56 + 8 * n, koff, len(k), voff, len(v))
koff += len(k)
free = val_end - voff - (key_base + koff)
if free < 0:
raise RuntimeError('a b-tree node overflows')
struct.pack_into('<HHI', block, 32, flags, level, len(recs))
struct.pack_into('<HHHHHHHH', block, 40, 0, toc_len, koff, free, BTOFF_INVALID, 0, BTOFF_INVALID, 0)
if is_root:
ks, vs = self.fixed if fixed else (0, 0)
lk, lv = (ks, vs) if fixed else (longest_k, longest_v)
struct.pack_into('<IIIIIIQQ', block, BS - 40, self.tree_flags, BS, ks, vs, lk, lv,
len(self.records), self.node_count())
otype = (T_BTREE if is_root else T_BTNODE) | self.storage
seal(block, oid, otype, self.subtype)
return bytes(block)
# ---------------------------------------------------------------------- volumes
def jkey(oid, jtype):
return struct.pack('<Q', oid | (jtype << 60))
def xfields(fields):
"""An inode's (or a record's) extended fields: [(type, flags, data bytes)] in that order."""
head = struct.pack('<HH', len(fields), sum(div_up(len(d), 8) * 8 for _, _, d in fields))
descs = b''.join(struct.pack('<BBH', t, f, len(d)) for t, f, d in fields)
data = b''.join(d + b'\0' * (div_up(len(d), 8) * 8 - len(d)) for _, _, d in fields)
return head + descs + data
class Volume:
def __init__(self, index, name, root, compress, when, spool=None, plain=()):
self.spool = spool # where compressed resource forks wait to be written (a file)
self.plain = tuple(d.strip('/') + '/' for d in plain) # never compressed below these
self.index = index
self.name = name
self.root = root
self.compress = compress
self.when = when
self.streams = [] # (owning private id, bytes, is_rsrc) -- data to place
self.counts = {'files': 0, 'dirs': 0, 'symlinks': 0}
self.next_oid = MIN_USER_INO
def new_oid(self):
oid = self.next_oid
self.next_oid += 1
return oid
def collect(self):
"""Inode numbers, contents (compressed or not) and the records that do not depend on
where the data lands; the extents are added once it is known (place_data)."""
self.items = [] # (node, parent oid)
self.root.oid = ROOT_DIR_INO
def walk(node, parent, path):
for name in sorted(node.children):
child = node.children[name]
child.oid = self.new_oid()
child.path = path + name
self.items.append((child, node.oid))
if stat.S_ISDIR(child.mode):
walk(child, child.oid, child.path + '/')
walk(self.root, ROOT_DIR_INO, '')
# private id -> where its bytes are: ('file', path, size) or ('spool', offset, size); never in memory
self.data = {}
self.decmpfs = {} # file oid -> (header, rsrc stream id)
self.inline = {} # file oid -> its decmpfs attribute: header and the zlib stream
files = [node for node, parent in self.items if stat.S_ISREG(node.mode)]
for node in files:
node.size = os.path.getsize(node.source)
forks = iter(())
if self.compress:
# compressed by as many processes as there are processors, taken in the files' order
pool = concurrent.futures.ProcessPoolExecutor()
forks = pool.map(compressed_fork, [n.source for n in files if n.size > 0 and not self.is_plain(n)],
chunksize=16)
for node in files:
if node.size == 0:
continue
if self.compress and not self.is_plain(node):
kind, rsrc = next(forks)
if kind == 'inline':
self.inline[node.oid] = struct.pack('<IIQ', DECMPFS_MAGIC, DECMPFS_ZLIB_ATTR, node.size) + rsrc
continue
if kind == 'rsrc':
sid = self.new_oid()
self.spool.seek(0, 2)
self.data[sid] = ('spool', self.spool.tell(), len(rsrc))
self.spool.write(rsrc)
self.decmpfs[node.oid] = (struct.pack('<IIQ', DECMPFS_MAGIC, DECMPFS_ZLIB_RSRC, node.size), sid)
continue
self.data[node.oid] = ('file', node.source, node.size)
if self.compress:
pool.shutdown()
def is_plain(self, node):
return any(node.path.startswith(p) for p in self.plain)
def place(self, first_block):
"""Data in order of private id, each stream in one extent. Returns the next free block."""
self.extents = {}
at = first_block
for sid in sorted(self.data):
n = div_up(self.data[sid][2], BS)
self.extents[sid] = (at, n)
at += n
self.data_blocks = at - first_block
return at
def fs_records(self):
"""Every record of the file-system tree, in key order."""
recs = []
self.counts = {'files': 0, 'dirs': 0, 'symlinks': 0}
t = self.when
children = {ROOT_DIR_INO: 0}
for node, parent in self.items:
children[parent] = children.get(parent, 0) + 1
def inode(oid, parent, node_mode, uid, gid, name, nchild_or_link, internal, bsd_flags=0,
dstream=None, uncompressed=0):
fields = [(INO_EXT_TYPE_NAME, XF_DO_NOT_COPY, name.encode('utf-8', 'surrogateescape') + b'\0')]
if dstream is not None:
fields.append((INO_EXT_TYPE_DSTREAM, XF_SYSTEM_FIELD, dstream))
val = struct.pack('<QQQQQQQiIIIIIHHQ', parent, oid, t, t, t, t, internal, nchild_or_link, 0, 0,
bsd_flags, uid, gid, node_mode, 0, uncompressed) + xfields(fields)
return (jkey(oid, J_INODE), val)
def dstream(size, blocks):
return struct.pack('<QQQQQ', size, blocks * BS, 0, 0, 0)
def drec(parent, name, oid, dtype):
enc = name.encode('utf-8', 'surrogateescape') + b'\0'
key = jkey(parent, J_DIR_REC) + struct.pack('<I', (name_hash(name) << 10) | len(enc)) + enc
return (key, struct.pack('<QQH', oid, t, dtype))
def xattr(oid, name, flags, data):
enc = name.encode() + b'\0'
return (jkey(oid, J_XATTR) + struct.pack('<H', len(enc)) + enc,
struct.pack('<HH', flags, len(data)) + data)
def extents(sid, own_stream=True):
"""A stream's extent, and for a file's own stream its reference count; an attribute's
stream has none (apfsck: \"xattrs can't be cloned\")."""
start, n = self.extents[sid]
recs = [(jkey(sid, J_FILE_EXTENT) + struct.pack('<Q', 0), struct.pack('<QQQ', n * BS, start, 0))]
if own_stream:
recs.insert(0, (jkey(sid, J_DSTREAM_ID), struct.pack('<I', 1)))
return recs
by_oid = {}
# the two special directories, named by records of the root's parent
by_oid.setdefault(ROOT_DIR_PARENT, []).extend([
drec(ROOT_DIR_PARENT, 'private-dir', PRIV_DIR_INO, DT_DIR),
drec(ROOT_DIR_PARENT, 'root', ROOT_DIR_INO, DT_DIR)])
r = self.root
by_oid.setdefault(ROOT_DIR_INO, []).append(
inode(ROOT_DIR_INO, ROOT_DIR_PARENT, r.mode, r.uid, r.gid, 'root', children.get(ROOT_DIR_INO, 0),
INODE_NO_RSRC_FORK))
by_oid.setdefault(PRIV_DIR_INO, []).append(
inode(PRIV_DIR_INO, ROOT_DIR_PARENT, stat.S_IFDIR | 0o755, 0, 0, 'private-dir', 0, INODE_NO_RSRC_FORK))
for node, parent in self.items:
oid = node.oid
mine = by_oid.setdefault(oid, [])
if stat.S_ISDIR(node.mode):
self.counts['dirs'] += 1
mine.append(inode(oid, parent, node.mode, node.uid, node.gid, node.name, children.get(oid, 0),
INODE_NO_RSRC_FORK))
dtype = DT_DIR
elif stat.S_ISLNK(node.mode):
self.counts['symlinks'] += 1
mine.append(inode(oid, parent, node.mode, node.uid, node.gid, node.name, 1, INODE_NO_RSRC_FORK))
mine.append(xattr(oid, 'com.apple.fs.symlink', XATTR_DATA_EMBEDDED | XATTR_FS_OWNED,
node.target + b'\0'))
dtype = DT_LNK
else:
self.counts['files'] += 1
if oid in self.inline:
mine.append(inode(oid, parent, node.mode, node.uid, node.gid, node.name, 1,
INODE_NO_RSRC_FORK | INODE_HAS_UNCOMPRESSED_SIZE, UF_COMPRESSED,
uncompressed=node.size))
mine.append(xattr(oid, 'com.apple.decmpfs', XATTR_DATA_EMBEDDED, self.inline[oid]))
elif oid in self.decmpfs:
header, sid = self.decmpfs[oid]
rsrc_len = self.data[sid][2]
mine.append(inode(oid, parent, node.mode, node.uid, node.gid, node.name, 1,
INODE_HAS_RSRC_FORK | INODE_HAS_UNCOMPRESSED_SIZE, UF_COMPRESSED,
uncompressed=node.size))
xd = struct.pack('<Q', sid) + dstream(rsrc_len, self.extents[sid][1])
mine.append(xattr(oid, 'com.apple.ResourceFork', XATTR_DATA_STREAM, xd))
mine.append(xattr(oid, 'com.apple.decmpfs', XATTR_DATA_EMBEDDED, header))
by_oid.setdefault(sid, []).extend(extents(sid, own_stream=False))
elif oid in self.data:
mine.append(inode(oid, parent, node.mode, node.uid, node.gid, node.name, 1, INODE_NO_RSRC_FORK,
dstream=dstream(node.size, self.extents[oid][1])))
mine.extend(extents(oid))
else:
mine.append(inode(oid, parent, node.mode, node.uid, node.gid, node.name, 1, INODE_NO_RSRC_FORK))
dtype = DT_REG
by_oid.setdefault(parent, []).append(drec(parent, node.name, oid, dtype))
for oid in sorted(by_oid):
recs.extend(sorted(by_oid[oid], key=self.sort_key))
return recs
@staticmethod
def sort_key(rec):
k = rec[0]
jtype = struct.unpack_from('<Q', k)[0] >> 60
if jtype == J_DIR_REC:
return (jtype, struct.unpack_from('<I', k, 8)[0] & ~0x3ff, k[12:])
if jtype == J_XATTR:
return (jtype, 0, k[10:])
if jtype == J_FILE_EXTENT:
return (jtype, struct.unpack_from('<Q', k, 8)[0], b'')
return (jtype, 0, b'')
def extentref_records(self):
recs = []
for sid in sorted(self.extents, key=lambda s: self.extents[s][0]):
start, n = self.extents[sid]
recs.append((jkey(start, J_EXTENT), struct.pack('<QQI', n | (KIND_NEW << 60), sid, 1)))
return recs
def compressed_fork(path):
"""How a file is best kept: ('inline', its zlib stream) when that fits the decmpfs attribute,
('rsrc', its resource fork) when that takes fewer blocks, else (None, None)."""
content = open(path, 'rb').read()
if len(content) <= PIECE:
z = zlib.compress(content, 9)
if 16 + len(z) <= XATTR_MAX_EMBEDDED:
return 'inline', z
rsrc = zlib_rsrc(content)
return ('rsrc', rsrc) if div_up(len(rsrc), BS) < div_up(len(content), BS) else (None, None)
def zlib_rsrc(content):
"""A resource fork as decmpfs keeps zlib pieces in it (type 4): an HFS resource fork whose one
resource is a table of the 64 KB pieces, each zlib (or stored, after a 0xff)."""
pieces = []
for at in range(0, len(content), PIECE):
chunk = content[at:at + PIECE]
z = zlib.compress(chunk, 9)
pieces.append(z if len(z) < len(chunk) else b'\xff' + chunk)
count = len(pieces)
table_len = 4 + 8 * count
body = bytearray(struct.pack('<I', count))
off = table_len
for p in pieces:
body += struct.pack('<II', off, len(p))
off += len(p)
for p in pieces:
body += p
data_off = 0x100
data = struct.pack('>I', len(body)) + bytes(body)
# the resource map: Apple's own for these forks (the 'cmpf' resource, id 1, named nothing)
rmap = bytearray(50)
rmap_off = data_off + len(data)
struct.pack_into('>IIII', rmap, 0, data_off, rmap_off, len(data), 50)
struct.pack_into('>HH', rmap, 24, 28, 50) # type list at 28, name list at 50 (none)
struct.pack_into('>H', rmap, 28, 0) # one type (count - 1)
rmap[30:34] = b'cmpf'
struct.pack_into('>HH', rmap, 34, 0, 10) # one resource of it, its list at 10 from the type list
struct.pack_into('>hHI', rmap, 38, 1, 0xffff, 0) # id 1, no name, data at 0 (attrs 0)
head = struct.pack('>IIII', data_off, rmap_off, len(data), 50)
out = head + b'\0' * (data_off - len(head)) + data + bytes(rmap)
return out
# ---------------------------------------------------------------------- the container
def cpoint_desc_blocks(block_count):
if block_count < 512 * 1024 // 4:
return 8
if block_count < 1024 * 1024 // 4:
return 12
if block_count < 50 * 1024 * 1024 // 4:
return 20 + 60 * ((block_count - 1024 * 1024 // 4) // (512 * 1024 // 4)) // 23
return 280
def cpoint_data_blocks(block_count):
b = block_count
if b < 4545:
return 52
if b < 13633:
return 124
if b < 36353:
return 160 + 36 * ((b - 13633) // 4544)
if b < 131777:
return 308 + 4 * ((b - 36353) // 4544)
if b < 262144:
return 648 + 4 * ((b - 131777) // 4544)
if b == 262144:
return 992
if b < 1048576:
off = (b - 262144) // 131072
return 1248 + 488 * off + 4 * ((b - (261280 + off * 131776)) // 2272)
if b < 4063232:
return 4112 + 256 * ((b - 1048576) // 131072)
if b < 13107200:
return 10000 + 256 * ((b - 4063232) // 131072)
return 27672
def main_fq_node_limit(blocks):
if blocks < 0x40000:
r = 1 + (blocks - 1) // 4544
elif blocks < 0x100000:
r = 116 + (blocks - 261281) // 2272
else:
r = 512
return 3 if r == 2 else r
def ip_fq_node_limit(chunks):
r = 3 * (chunks + 751) // 1127 - 1
return 3 if r == 2 else r
class Container:
def __init__(self, volumes, slack, uuid_seed):
self.vols = volumes
self.slack = slack
self.seed = uuid_seed
def uuid(self, what):
return hashlib.sha256((self.seed + what).encode()).digest()[:16]
def layout(self):
"""Decide every block: done twice, since the container's size decides the sizes of the
checkpoint areas and of the space manager, which come before everything else."""
for v in self.vols:
v.collect()
guess = 1024
while True:
total = self._layout(guess)
if total + self.slack <= guess:
break
guess = total + self.slack
self.block_count = guess
def _layout(self, block_count):
self.bc = block_count
bpc = BS * 8 # blocks per chunk: one bitmap block each
self.chunks = div_up(block_count, bpc)
self.chunks_per_cib = (BS - 40) // 32
self.cibs = div_up(self.chunks, self.chunks_per_cib)
self.cibs_per_cab = (BS - 40) // 8
cabs = div_up(self.cibs, self.cibs_per_cab)
self.cabs = 0 if cabs == 1 else cabs
self.ip_blocks = (self.chunks + self.cibs + self.cabs) * 3
self.ip_bm_size = div_up(self.ip_blocks, bpc)
self.ip_bmap_blocks = 16 * self.ip_bm_size
self.bm_addr_off = SM_BITMAP_XID_OFF + 8 * self.ip_bm_size
self.bm_free_next_off = self.bm_addr_off + div_up(2 * self.ip_bm_size, 8) * 8
self.cib_addr_off = self.bm_free_next_off + self.ip_bmap_blocks * 2
entries = self.cabs if self.cabs > 1 else self.cibs
self.sm_size = div_up(entries * 8 + self.cib_addr_off, BS) * BS
self.sm_blocks = self.sm_size // BS
self.desc_base = 1
self.desc_blocks = cpoint_desc_blocks(block_count)
self.data_base = self.desc_base + self.desc_blocks
self.data_blocks = cpoint_data_blocks(block_count)
self.reaper_bno = self.data_base
self.sm_bno = self.reaper_bno + 1
self.ipfq_bno = self.sm_bno + self.sm_blocks
self.mainfq_bno = self.ipfq_bno + 1
self.eph_blocks = self.mainfq_bno - self.reaper_bno + 1
at = self.data_base + self.data_blocks
self.nx_omap_bno, self.nx_omap_root = at, at + 1
at += 2
# object ids: the ephemeral objects, then each volume's superblock and tree nodes
oid = OID_RESERVED
self.sm_oid, self.reaper_oid, self.ipfq_oid, self.mainfq_oid = oid, oid + 1, oid + 2, oid + 3
oid += 4
for v in self.vols:
v.oid = oid
oid += 1
v.sb_bno = at
v.omap_bno = at + 1
at += 2
# the trees: their shapes do not depend on the data's addresses (fixed-size fields)
v.place(0)
v.fs_tree = Tree(T_FSTREE, VIRTUAL, tree_flags=BTREE_KV_NONALIGNED)
n_fs = v.fs_tree.plan(v.fs_records())
v.fs_oids = list(range(oid, oid + n_fs))
oid += n_fs
v.omap_tree = Tree(T_OMAP, PHYSICAL, fixed=(16, 16), tree_flags=BTREE_PHYSICAL)
n_om = v.omap_tree.plan([(struct.pack('<QQ', o, XID), b'\0' * 16) for o in v.fs_oids])
v.omap_addrs = list(range(at, at + n_om))
at += n_om
v.fs_addrs = list(range(at, at + n_fs))
at += n_fs
v.er_tree = Tree(T_BLOCKREF, PHYSICAL, tree_flags=BTREE_PHYSICAL | BTREE_KV_NONALIGNED)
n_er = v.er_tree.plan(v.extentref_records())
v.er_addrs = list(range(at, at + n_er))
at += n_er
v.snap_bno = at
at += 1
self.next_oid = oid
self.ip_bm_base = at
at += self.ip_bmap_blocks
self.ip_base = at
at += self.ip_blocks
for v in self.vols:
at = v.place(at)
# the extents are known now: the records again, with them (same sizes, same shape)
v.fs_tree.plan(v.fs_records())
v.er_tree.plan(v.extentref_records())
self.used_end = at
return at
def write(self, path):
bc = self.bc
blocks = {}
used = bytearray(div_up(bc, 8))
def mark(start, n=1):
b, end = start, start + n
while b < end and b & 7:
used[b >> 3] |= 1 << (b & 7)
b += 1
if end - b >= 8:
used[b >> 3:(end >> 3)] = b'\xff' * ((end >> 3) - (b >> 3))
b = end & ~7
while b < end:
used[b >> 3] |= 1 << (b & 7)
b += 1
def put(bno, data):
assert len(data) % BS == 0
blocks[bno] = data
bpc = BS * 8
used_chunks = div_up(self.used_end, bpc)
chunk_bmap_base = self.ip_base
cib_base = chunk_bmap_base + used_chunks
cab_base = cib_base + self.cibs
# --- per volume: trees, object map, superblock
for v in self.vols:
fs_blocks = v.fs_tree.build(v.fs_addrs, v.fs_oids)
for b, d in fs_blocks.items():
put(b, d)
omap_recs = [(struct.pack('<QQ', o, XID), struct.pack('<IIQ', 0, BS, a))
for o, a in zip(v.fs_oids, v.fs_addrs)]
v.omap_tree.plan(omap_recs)
for b, d in v.omap_tree.build(v.omap_addrs, v.omap_addrs).items():
put(b, d)
omap = bytearray(BS)
struct.pack_into('<IIIIQ', omap, 32, 0, 0, PHYSICAL | T_BTREE, PHYSICAL | T_BTREE, v.omap_addrs[0])
seal(omap, v.omap_bno, PHYSICAL | T_OMAP)
put(v.omap_bno, bytes(omap))
for b, d in v.er_tree.build(v.er_addrs, v.er_addrs).items():
put(b, d)
snap = Tree(T_SNAPMETA, PHYSICAL, tree_flags=BTREE_PHYSICAL | BTREE_KV_NONALIGNED)
snap.plan([])
for b, d in snap.build([v.snap_bno], [v.snap_bno]).items():
put(b, d)
alloc = 1 + len(v.omap_addrs) + len(v.fs_addrs) + len(v.er_addrs) + 1 + v.data_blocks
sb = bytearray(BS)
struct.pack_into('<4sI', sb, 32, b'APSB', v.index)
struct.pack_into('<QQQ', sb, 40, 0x2, 0, 0x8) # hard-link map records; normalization-insensitive
struct.pack_into('<Q', sb, 0x58, alloc)
struct.pack_into('<HHIIIHH', sb, 0x60, 5, 0, 0, 6, 0, 1, 0) # meta crypto: v5.0, class F, revision 1
struct.pack_into('<III', sb, 0x74, VIRTUAL | T_BTREE, PHYSICAL | T_BTREE, PHYSICAL | T_BTREE)
struct.pack_into('<QQQQ', sb, 0x80, v.omap_bno, v.fs_oids[0], v.er_addrs[0], v.snap_bno)
struct.pack_into('<Q', sb, 0xb0, v.next_oid)
struct.pack_into('<QQQQQ', sb, 0xb8, v.counts['files'], v.counts['dirs'], v.counts['symlinks'], 0, 0)
struct.pack_into('<QQ', sb, 0xe0, alloc, 0)
sb[0xf0:0x100] = self.uuid('volume %d' % v.index)
struct.pack_into('<QQ', sb, 0x100, v.when, 1) # last modified; unencrypted
fmt = b'mkapfs.py (darwin-redwood)'
sb[0x110:0x110 + len(fmt)] = fmt
struct.pack_into('<QQ', sb, 0x130, v.when, XID)
nm = v.name.encode()[:255]
sb[0x2c0:0x2c0 + len(nm)] = nm
struct.pack_into('<I', sb, 0x3c0, 3) # next document id
seal(sb, v.oid, VIRTUAL | T_FS)
put(v.sb_bno, bytes(sb))
for b in [v.sb_bno, v.omap_bno] + v.omap_addrs + v.fs_addrs + v.er_addrs + [v.snap_bno]:
mark(b)
for start, n in v.extents.values():
mark(start, n)
# --- the container's object map: the volumes' superblocks
nx_omap = Tree(T_OMAP, PHYSICAL, fixed=(16, 16), tree_flags=BTREE_PHYSICAL)
nx_omap.plan([(struct.pack('<QQ', v.oid, XID), struct.pack('<IIQ', 0, BS, v.sb_bno)) for v in self.vols])
assert nx_omap.node_count() == 1
for b, d in nx_omap.build([self.nx_omap_root], [self.nx_omap_root]).items():
put(b, d)
omap = bytearray(BS)
struct.pack_into('<IIIIQ', omap, 32, 1, 0, PHYSICAL | T_BTREE, PHYSICAL | T_BTREE, self.nx_omap_root)
seal(omap, self.nx_omap_bno, PHYSICAL | T_OMAP)
put(self.nx_omap_bno, bytes(omap))
# --- what else is in use: block 0, the checkpoint areas, the internal pool and its bitmaps
mark(0)
mark(self.desc_base, self.desc_blocks)
mark(self.data_base, self.data_blocks)
mark(self.nx_omap_bno, 2)
mark(self.ip_bm_base, self.ip_bmap_blocks)
mark(self.ip_base, self.ip_blocks)
# --- the space manager: chunk bitmaps, chunk-info blocks, the internal pool's own bitmap
free_total = 0
cib_blocks = []
chunk = 0
for c in range(self.cibs):
cib = bytearray(BS)
n = min(self.chunks_per_cib, self.chunks - chunk)
struct.pack_into('<II', cib, 32, c, n)
for i in range(n):
start = chunk * bpc
count = min(bpc, bc - start)
bm = bytes(used[start // 8:(start + count + 7) // 8])
in_use = sum(bin(x).count('1') for x in bm)
bmap_addr = 0
if chunk < used_chunks:
bmap_addr = chunk_bmap_base + chunk
put(bmap_addr, bm + b'\0' * (BS - len(bm)))
struct.pack_into('<QQIIQ', cib, 40 + 32 * i, XID, start, count, count - in_use, bmap_addr)
free_total += count - in_use
chunk += 1
seal(cib, cib_base + c, PHYSICAL | T_CIB)
cib_blocks.append(bytes(cib))
put(cib_base + c, bytes(cib))
for c in range(self.cabs):
cab = bytearray(BS)
n = min(self.cibs_per_cab, self.cibs - c * self.cibs_per_cab)
struct.pack_into('<II', cab, 32, c, n)
for i in range(n):
struct.pack_into('<Q', cab, 40 + 8 * i, cib_base + c * self.cibs_per_cab + i)
seal(cab, cab_base + c, PHYSICAL | T_CAB)
put(cab_base + c, bytes(cab))
ip_bm = bytearray(self.ip_bm_size * BS)
for b in list(range(chunk_bmap_base, chunk_bmap_base + used_chunks)) + \
list(range(cib_base, cib_base + self.cibs)) + list(range(cab_base, cab_base + self.cabs)):
r = b - self.ip_base
ip_bm[r >> 3] |= 1 << (r & 7)
put(self.ip_bm_base, bytes(ip_bm))
for i in range(self.ip_bm_size, self.ip_bmap_blocks):
put(self.ip_bm_base + i, bytes(BS))
sm = bytearray(self.sm_size)
struct.pack_into('<IIII', sm, 32, BS, bpc, self.chunks_per_cib, self.cibs_per_cab)
struct.pack_into('<QQIIQIIQ', sm, 48, bc, self.chunks, self.cibs, self.cabs, free_total,
self.cib_addr_off, 0, 0)
struct.pack_into('<IIQIIQQQQ', sm, 144, 0, IP_BM_TX_MULTIPLIER, self.ip_blocks, self.ip_bm_size,
self.ip_bmap_blocks, self.ip_bm_base, self.ip_base, 0, 0)
struct.pack_into('<QQQHHIQ', sm, 200, 0, self.ipfq_oid, 0, ip_fq_node_limit(self.chunks), 0, 0, 0)
struct.pack_into('<QQQHHIQ', sm, 240, 0, self.mainfq_oid, 0, main_fq_node_limit(bc), 0, 0, 0)
struct.pack_into('<HHIII', sm, 320, self.ip_bm_size, self.ip_bmap_blocks - 1, SM_BITMAP_XID_OFF,
self.bm_addr_off, self.bm_free_next_off)
for i in range(self.ip_bm_size):
struct.pack_into('<Q', sm, SM_BITMAP_XID_OFF + 8 * i, XID)
struct.pack_into('<H', sm, self.bm_addr_off + 2 * i, i)
for i in range(self.ip_bmap_blocks):
if i < self.ip_bm_size or i == self.ip_bmap_blocks - 1:
nxt = IP_BM_INDEX_INVALID
else:
nxt = i + 1
struct.pack_into('<H', sm, self.bm_free_next_off + 2 * i, nxt)
if self.cabs:
for i in range(self.cabs):
struct.pack_into('<Q', sm, self.cib_addr_off + 8 * i, cab_base + i)
else:
for i in range(self.cibs):
struct.pack_into('<Q', sm, self.cib_addr_off + 8 * i, cib_base + i)
seal(sm, self.sm_oid, EPHEMERAL | T_SPACEMAN)
put(self.sm_bno, bytes(sm))
# --- the reaper and the two free queues (empty)
reaper = bytearray(BS)
struct.pack_into('<Q', reaper, 32, 1)
struct.pack_into('<I', reaper, 64, 1) # nr_flags: BHM
struct.pack_into('<I', reaper, 108, BS - 112) # nr_state_buffer_size
seal(reaper, self.reaper_oid, EPHEMERAL | T_REAPER)
put(self.reaper_bno, bytes(reaper))
for bno, oid in ((self.ipfq_bno, self.ipfq_oid), (self.mainfq_bno, self.mainfq_oid)):
fq = bytearray(BS)
toc = ((BS - 56) // (16 + 8 + 4)) * 4
struct.pack_into('<HHI', fq, 32, BTNODE_ROOT | BTNODE_LEAF | BTNODE_FIXED, 0, 0)
struct.pack_into('<HHHHHHHH', fq, 40, 0, toc, 0, BS - 56 - toc - 40, BTOFF_INVALID, 0, BTOFF_INVALID, 0)
struct.pack_into('<IIIIIIQQ', fq, BS - 40, BTREE_EPHEMERAL | BTREE_ALLOW_GHOSTS, BS, 16, 8, 16, 8, 0, 1)
seal(fq, oid, EPHEMERAL | T_BTREE, T_FREE_QUEUE)
put(bno, bytes(fq))
# --- the container superblock, the checkpoint map, the superblock's copy
nx = bytearray(BS)
struct.pack_into('<4sIQQQQ', nx, 32, b'NXSB', BS, bc, 0, 0, 0x2) # incompatible: version 2
nx[72:88] = self.uuid('container')
struct.pack_into('<QQ', nx, 88, self.next_oid, XID + 1)
struct.pack_into('<IIQQIIIIII', nx, 104, self.desc_blocks, self.data_blocks, self.desc_base, self.data_base,
2, self.eph_blocks, 0, 2, 0, self.eph_blocks)
struct.pack_into('<QQQII', nx, 152, self.sm_oid, self.nx_omap_bno, self.reaper_oid, 0,
min(100, div_up(bc * BS, 512 * 1024 * 1024)))
for i, v in enumerate(self.vols):
struct.pack_into('<Q', nx, 184 + 8 * i, v.oid)
min_blocks = main_fq_node_limit(bc) if bc * BS < 128 * 1024 * 1024 else 8
struct.pack_into('<Q', nx, 1312, (min_blocks << 32) | (4 << 16) | 1)
seal(nx, OID_NX, EPHEMERAL | T_NX)
put(0, bytes(nx))
cpm = bytearray(BS)
maps = [(EPHEMERAL | T_REAPER, 0, BS, self.reaper_oid, self.reaper_bno),
(EPHEMERAL | T_SPACEMAN, 0, self.sm_size, self.sm_oid, self.sm_bno),
(EPHEMERAL | T_BTREE, T_FREE_QUEUE, BS, self.ipfq_oid, self.ipfq_bno),
(EPHEMERAL | T_BTREE, T_FREE_QUEUE, BS, self.mainfq_oid, self.mainfq_bno)]
struct.pack_into('<II', cpm, 32, 1, len(maps)) # the last map of the checkpoint
for i, (t, st, size, oid, paddr) in enumerate(maps):
struct.pack_into('<IIIIQQQ', cpm, 40 + 40 * i, t, st, size, 0, 0, oid, paddr)
seal(cpm, self.desc_base, PHYSICAL | T_CPMAP)
put(self.desc_base, bytes(cpm))
put(self.desc_base + 1, bytes(nx))
# --- out, in order (holes stay holes in a sparse file); the files' data straight from where it is
with open(path, 'wb') as f:
f.truncate(bc * BS)
for bno in sorted(blocks):
f.seek(bno * BS)
f.write(blocks[bno])
for v in self.vols:
for sid, (start, n) in sorted(v.extents.items(), key=lambda e: e[1][0]):
kind, where, size = v.data[sid]
f.seek(start * BS)
if kind == 'file':
with open(where, 'rb') as src:
left = size
while left > 0:
chunk = src.read(min(left, 1 << 22))
if not chunk:
raise RuntimeError('%s is shorter than it was' % where)
f.write(chunk)
left -= len(chunk)
else:
v.spool.seek(where)
f.write(v.spool.read(size))
return free_total
def main():
ap = argparse.ArgumentParser(description=__doc__.split('\n')[0])
ap.add_argument('-o', '--output', required=True)
ap.add_argument('-z', '--compress', action='store_true', help='zlib in the resource fork where it saves space')
ap.add_argument('--plain', action='append', default=[], help='with -z: never compress what is under this directory')
ap.add_argument('--time', type=int, default=1683900000, help='every timestamp, in seconds')
ap.add_argument('--slack', type=int, default=256, help='free blocks to leave (at least)')
ap.add_argument('volumes', nargs='+', help='NAME=DIR[,manifest=FILE]')
args = ap.parse_args()
vols = []
spool = open(args.output + '.spool', 'w+b') if args.compress else None
for i, spec in enumerate(args.volumes):
name, _, rest = spec.partition('=')
parts = rest.split(',')
root = read_tree(parts[0])
for opt in parts[1:]:
k, _, val = opt.partition('=')
if k == 'manifest':
apply_manifest(root, val)
vols.append(Volume(i, name, root, args.compress, args.time * 1000000000, spool, args.plain))
c = Container(vols, args.slack, os.path.basename(args.output))
c.layout()
free = c.write(args.output)
if spool is not None:
spool.close()
os.unlink(args.output + '.spool')
for v in vols:
print('mkapfs.py: volume %d "%s": %d files, %d directories, %d symbolic links, %d blocks of data%s' % (
v.index, v.name, v.counts['files'], v.counts['dirs'], v.counts['symlinks'], v.data_blocks,
' (%d compressed in their resource fork, %d whole in their attribute)' % (len(v.decmpfs), len(v.inline))
if v.compress else ''))
print('mkapfs.py: %s: %d blocks of %d bytes, %d free' % (args.output, c.block_count, BS, free))
if __name__ == '__main__':
main()