[PATCH 1/5] apfsck: rework sibling name allocation

[Ernesto A. Fernández]

Move the allocation of memory for sibling names from get_sibling() to
set_or_check_sibling(). This causes more fragmentation of memory, but
will allow us to call get_sibling() without knowing the length of the
name, which is important to support sibling maps.

Signed-off-by: Ernesto A. Fernández <ernesto.mn...@gmail.com>
---
apfsck/dir.c | 2 +-
apfsck/inode.c | 18 ++++++++++++------
apfsck/inode.h | 4 ++--
3 files changed, 15 insertions(+), 9 deletions(-)

diff --git a/apfsck/dir.c b/apfsck/dir.c
index 560fe82..d53589d 100644
--- a/apfsck/dir.c
+++ b/apfsck/dir.c
@@ -145,6 +145,6 @@ void parse_dentry_record(struct apfs_drec_hashed_key *key,

if (!sibling_id) /* No sibling record for this dentry */
return;
- sibling = get_sibling(sibling_id, namelen, inode);
+ sibling = get_sibling(sibling_id, inode);
set_or_check_sibling(parent_ino, namelen, key->name, sibling);
}
diff --git a/apfsck/inode.c b/apfsck/inode.c
index 5c9e6cf..2adede2 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -106,6 +106,7 @@ static void free_inode_names(struct inode *inode)
if (!current->s_checked)
report("Catalog", "orphaned or missing sibling link.");
next = current->s_next;
+ free(current->s_name);
free(current);
current = next;
++count;
@@ -658,12 +659,11 @@ void parse_inode_record(struct apfs_inode_key *key,
/**
* get_sibling - Find or create a sibling link structure for an inode
* @id: sibling id
- * @namelen: length of the sibling name
* @inode: the inode
*
* Returns the sibling structure, after creating it if necessary.
*/
-struct sibling *get_sibling(u64 id, int namelen, struct inode *inode)
+struct sibling *get_sibling(u64 id, struct inode *inode)
{
struct sibling **entry_p = &inode->i_siblings;
struct sibling *entry = *entry_p;
@@ -680,7 +680,7 @@ struct sibling *get_sibling(u64 id, int namelen, struct inode *inode)
entry = *entry_p;
}

- new = calloc(1, sizeof(*new) + namelen);
+ new = calloc(1, sizeof(*new));
if (!new) {
perror(NULL);
exit(1);
@@ -707,10 +707,16 @@ void set_or_check_sibling(u64 parent_id, int namelen, u8 *name,
struct sibling *sibling)
{
/* Whichever was read first, dentry or sibling, sets the fields */
- if (!sibling->s_name_len) {
+ if (!sibling->s_name) {
+ sibling->s_parent_ino = parent_id;
sibling->s_name_len = namelen;
+
+ sibling->s_name = malloc(namelen);
+ if (!sibling->s_name) {
+ perror(NULL);
+ exit(1);
+ }
strcpy((char *)sibling->s_name, (char *)name);
- sibling->s_parent_ino = parent_id;
return;
}

@@ -753,7 +759,7 @@ void parse_sibling_record(struct apfs_sibling_link_key *key,
if (!inode->i_seen) /* The b-tree keys are in order */
report("Sibling link record", "inode is missing");

- sibling = get_sibling(le64_to_cpu(key->sibling_id), namelen, inode);
+ sibling = get_sibling(le64_to_cpu(key->sibling_id), inode);

/* It seems that sibling ids come from the same pool as inode numbers */
if (sibling->s_id < APFS_MIN_USER_INO_NUM)
diff --git a/apfsck/inode.h b/apfsck/inode.h
index 95a6783..9c6b7d8 100644
--- a/apfsck/inode.h
+++ b/apfsck/inode.h
@@ -221,7 +221,7 @@ struct sibling {

u64 s_parent_ino; /* Inode number for parent */
u16 s_name_len; /* Name length */
- u8 s_name[0]; /* Name */
+ u8 *s_name; /* In-memory copy of the name */
};

extern struct inode **alloc_inode_table();
@@ -230,7 +230,7 @@ extern struct inode *get_inode(u64 ino, struct inode **table);
extern void check_inode_ids(u64 ino, u64 parent_ino);
extern void parse_inode_record(struct apfs_inode_key *key,
struct apfs_inode_val *val, int len);
-extern struct sibling *get_sibling(u64 id, int namelen, struct inode *inode);
+extern struct sibling *get_sibling(u64 id, struct inode *inode);
extern void set_or_check_sibling(u64 parent_id, int namelen, u8 *name,
struct sibling *sibling);
extern void parse_sibling_record(struct apfs_sibling_link_key *key,
--
2.11.0

[Ernesto A. Fernández]

Check that every sibling record has a corresponding sibling map. I have
no idea what these are for, but they seem to be required.

Signed-off-by: Ernesto A. Fernández <ernesto.mn...@gmail.com>
---

apfsck/btree.c | 3 +++
apfsck/inode.c | 24 ++++++++++++++++++++++++
apfsck/inode.h | 11 +++++++++++
apfsck/key.h | 7 +++++++
4 files changed, 45 insertions(+)

diff --git a/apfsck/btree.c b/apfsck/btree.c
index a0a588d..e6ddd48 100644
--- a/apfsck/btree.c
+++ b/apfsck/btree.c
@@ -516,6 +516,9 @@ static void parse_cat_record(void *key, void *val, int len)
case APFS_TYPE_XATTR:
parse_xattr_record(key, val, len);
break;
+ case APFS_TYPE_SIBLING_MAP:
+ parse_sibling_map_record(key, val, len);
+ break;
default:
break;
}
diff --git a/apfsck/inode.c b/apfsck/inode.c
index 2adede2..0aa89b4 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -105,6 +105,8 @@ static void free_inode_names(struct inode *inode)
while (current) {

if (!current->s_checked)
report("Catalog", "orphaned or missing sibling link.");

+ if (!current->s_mapped)
+ report("Catalog", "no sibling map for link.");
next = current->s_next;
free(current->s_name);
free(current);
@@ -768,3 +770,25 @@ void parse_sibling_record(struct apfs_sibling_link_key *key,
set_or_check_sibling(le64_to_cpu(val->parent_id), namelen, val->name,
sibling);
}
+
+/**
+ * parse_sibling_record - Parse and check a sibling map record value
+ * @key: pointer to the raw key
+ * @val: pointer to the raw value
+ * @len: length of the raw value
+ *
+ * Internal consistency of @key must be checked before calling this function.
+ */
+void parse_sibling_map_record(struct apfs_sibling_map_key *key,
+ struct apfs_sibling_map_val *val, int len)
+{
+ struct inode *inode;
+ struct sibling *sibling;
+
+ if (len != sizeof(*val))
+ report("Sibling map record", "wrong size of value.");
+
+ inode = get_inode(le64_to_cpu(val->file_id), vsb->v_inode_table);
+ sibling = get_sibling(cat_cnid(&key->hdr), inode);
+ sibling->s_mapped = true;
+}
diff --git a/apfsck/inode.h b/apfsck/inode.h
index 9c6b7d8..a9bcb0c 100644
--- a/apfsck/inode.h
+++ b/apfsck/inode.h
@@ -11,6 +11,7 @@

struct apfs_inode_key;
struct apfs_sibling_link_key;
+struct apfs_sibling_map_key;

/* Inode numbers for special inodes */
#define APFS_INVALID_INO_NUM 0
@@ -175,6 +176,13 @@ struct apfs_sibling_val {
u8 name[0];
} __packed;

+/*
+ * Structure of the value for a sibling map record. No idea what these are for.
+ */
+struct apfs_sibling_map_val {
+ __le64 file_id;
+} __packed;
+
#define INODE_TABLE_BUCKETS 512 /* So the hash table array fits in 4k */

/* Flags for the bitmap of seen system xattrs (i_xattr_bmap) */
@@ -218,6 +226,7 @@ struct sibling {
struct sibling *s_next; /* Next sibling in linked list */
u64 s_id; /* Sibling id */
bool s_checked; /* Has this sibling been checked? */
+ bool s_mapped; /* Has the sibling map been seen? */

u64 s_parent_ino; /* Inode number for parent */
u16 s_name_len; /* Name length */

@@ -235,6 +244,8 @@ extern void set_or_check_sibling(u64 parent_id, int namelen, u8 *name,

struct sibling *sibling);
extern void parse_sibling_record(struct apfs_sibling_link_key *key,

struct apfs_sibling_val *val, int len);
+extern void parse_sibling_map_record(struct apfs_sibling_map_key *key,
+ struct apfs_sibling_map_val *val, int len);
extern void check_xfield_flags(u8 flags);

#endif /* _INODE_H */
diff --git a/apfsck/key.h b/apfsck/key.h
index 211b385..a580f6d 100644
--- a/apfsck/key.h
+++ b/apfsck/key.h
@@ -122,6 +122,13 @@ struct apfs_sibling_link_key {
} __packed;

/*
+ * Structure of the key for a siblink map record
+ */
+struct apfs_sibling_map_key {
+ struct apfs_key_header hdr;
+} __packed;
+
+/*
* In-memory representation of a key, as relevant for a b-tree query.
*/
struct key {
--
2.11.0

[Ernesto A. Fernández]

Parse all dstream id records to retrieve their refcount, and check that
it matches the actual number of references for the stream.

A few special cases exist. Streams with no references have no id
record, and neither do xattrs, which always have a single reference.

Signed-off-by: Ernesto A. Fernández <ernesto.mn...@gmail.com>
---

apfsck/btree.c | 3 +++
apfsck/extents.c | 39 +++++++++++++++++++++++++++++++++++++--
apfsck/extents.h | 15 ++++++++++++++-
apfsck/inode.c | 3 ++-
apfsck/inode.h | 7 -------
apfsck/xattr.c | 3 ++-
6 files changed, 58 insertions(+), 12 deletions(-)

diff --git a/apfsck/btree.c b/apfsck/btree.c
index e6ddd48..e092ba3 100644
--- a/apfsck/btree.c
+++ b/apfsck/btree.c
@@ -519,6 +519,9 @@ static void parse_cat_record(void *key, void *val, int len)
case APFS_TYPE_SIBLING_MAP:
parse_sibling_map_record(key, val, len);
break;
+ case APFS_TYPE_DSTREAM_ID:
+ parse_dstream_id_record(key, val, len);
+ break;
default:
break;
}
diff --git a/apfsck/extents.c b/apfsck/extents.c
index baf6c06..9d372e3 100644
--- a/apfsck/extents.c
+++ b/apfsck/extents.c
@@ -32,8 +32,22 @@ struct dstream **alloc_dstream_table(void)
*/
static void check_dstream_stats(struct dstream *dstream)
{
- if (!dstream->d_obj_type) /* The dstream structure was never seen */
- report_unknown("File extent without inode or xattr");
+ if (dstream->d_obj_type == APFS_TYPE_XATTR) {
+ if (dstream->d_seen || dstream->d_references != 1)
+ report("Data stream", "xattrs can't be cloned.");
+ } else {
+ if (!dstream->d_seen && dstream->d_references)
+ report("Data stream", "missing reference count.");
+ if (dstream->d_seen && !dstream->d_references)
+ report("Data stream", "unnecessary reference count.");
+ if (dstream->d_refcnt != dstream->d_references)
+ report("Data stream", "bad reference count.");
+ }
+
+ if (!dstream->d_references)
+ /* No dstream structure to report the length */
+ return;
+
if (dstream->d_bytes < dstream->d_size)
report("Data stream", "some extents are missing.");
if (dstream->d_bytes != dstream->d_alloced_size)
@@ -133,3 +147,24 @@ void parse_extent_record(struct apfs_file_extent_key *key,
if (!le64_to_cpu(val->phys_block_num)) /* This is a hole */
dstream->d_sparse_bytes += length;
}
+
+/**
+ * parse_dstream_id_record - Parse a dstream id record value

+ * @key: pointer to the raw key
+ * @val: pointer to the raw value
+ * @len: length of the raw value
+ *
+ * Internal consistency of @key must be checked before calling this function.
+ */

+void parse_dstream_id_record(struct apfs_dstream_id_key *key,
+ struct apfs_dstream_id_val *val, int len)
+{
+ struct dstream *dstream;

+
+ if (len != sizeof(*val))

+ report("Dstream id record", "wrong size of value.");
+
+ dstream = get_dstream(cat_cnid(&key->hdr), vsb->v_dstream_table);
+ dstream->d_seen = true;
+ dstream->d_refcnt = le32_to_cpu(val->refcnt);
+}
diff --git a/apfsck/extents.h b/apfsck/extents.h
index 69d7f0e..7c42ba5 100644
--- a/apfsck/extents.h
+++ b/apfsck/extents.h
@@ -10,6 +10,7 @@
#include "types.h"

struct apfs_file_extent_key;
+struct apfs_dstream_id_key;

/* File extent records */
#define APFS_FILE_EXTENT_LEN_MASK 0x00ffffffffffffffULL
@@ -25,6 +26,13 @@ struct apfs_file_extent_val {
__le64 crypto_id;
} __packed;

+/*
+ * Structure of a data stream record
+ */
+struct apfs_dstream_id_val {
+ __le32 refcnt;
+} __packed;
+
#define DSTREAM_TABLE_BUCKETS 512 /* So the hash table array fits in 4k */

/*
@@ -33,14 +41,17 @@ struct apfs_file_extent_val {
struct dstream {
u64 d_id; /* Id of the dstream */
u8 d_obj_type; /* Type of the owner objects */
+ bool d_seen; /* Has the dstream record been seen? */

- /* Dstream stats read from the dstream structure */
+ /* Dstream stats read from the dstream structures */
u64 d_size; /* Dstream size */
u64 d_alloced_size; /* Dstream size, including unused */
+ u32 d_refcnt; /* Reference count */

/* Dstream stats measured by the fsck */
u64 d_bytes; /* Size of the extents read so far */
u64 d_sparse_bytes; /* Size of the holes read so far */
+ u32 d_references; /* Number of references to dstream */

struct dstream *d_next; /* Next dstream in linked list */
};
@@ -50,5 +61,7 @@ extern void free_dstream_table(struct dstream **table);
extern struct dstream *get_dstream(u64 ino, struct dstream **table);
extern void parse_extent_record(struct apfs_file_extent_key *key,
struct apfs_file_extent_val *val, int len);
+extern void parse_dstream_id_record(struct apfs_dstream_id_key *key,
+ struct apfs_dstream_id_val *val, int len);

#endif /* _EXTENTS_H */
diff --git a/apfsck/inode.c b/apfsck/inode.c
index 0aa89b4..6dedd6c 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -311,7 +311,7 @@ static int read_dstream_xfield(char *xval, int len, struct inode *inode)
alloced_size = le64_to_cpu(dstream_raw->alloced_size);

dstream = get_dstream(inode->i_private_id, vsb->v_dstream_table);
- if (dstream->d_obj_type) {
+ if (dstream->d_references) {
/* A dstream structure for this id has already been seen */
if (dstream->d_obj_type != APFS_TYPE_INODE)
report("Dstream xfield", "shared by inode and xattr.");
@@ -327,6 +327,7 @@ static int read_dstream_xfield(char *xval, int len, struct inode *inode)
dstream->d_alloced_size = alloced_size;
}

+ dstream->d_references++;
return sizeof(*dstream_raw);
}

diff --git a/apfsck/inode.h b/apfsck/inode.h
index a9bcb0c..fb4f33d 100644
--- a/apfsck/inode.h
+++ b/apfsck/inode.h
@@ -139,13 +139,6 @@ struct apfs_x_field {
} __packed;

/*
- * Structure of a data stream record
- */
-struct apfs_dstream_id_val {
- __le32 refcnt;
-} __packed;
-
-/*
* Structure used to store information about a data stream
*/
struct apfs_dstream {
diff --git a/apfsck/xattr.c b/apfsck/xattr.c
index bf4d0a1..00d1dbd 100644
--- a/apfsck/xattr.c
+++ b/apfsck/xattr.c
@@ -44,7 +44,7 @@ static void parse_xattr_dstream(struct apfs_xattr_dstream *xstream)
alloced_size = le64_to_cpu(dstream_raw->alloced_size);

dstream = get_dstream(id, vsb->v_dstream_table);
- if (dstream->d_obj_type) {
+ if (dstream->d_references) {
/* A dstream structure for this id has already been seen */
if (dstream->d_obj_type != APFS_TYPE_XATTR)
report("Xattr dstream", "shared by inode and xattr.");
@@ -59,6 +59,7 @@ static void parse_xattr_dstream(struct apfs_xattr_dstream *xstream)
dstream->d_size = size;
dstream->d_alloced_size = alloced_size;
}
+ dstream->d_references++;
}

/**
--
2.11.0

[Ernesto A. Fernández]

Check that extent records always have a positive length.

Signed-off-by: Ernesto A. Fernández <ernesto.mn...@gmail.com>
---

apfsck/extents.c | 3 +++
1 file changed, 3 insertions(+)

diff --git a/apfsck/extents.c b/apfsck/extents.c
index 9d372e3..a99a2f9 100644
--- a/apfsck/extents.c
+++ b/apfsck/extents.c
@@ -133,8 +133,11 @@ void parse_extent_record(struct apfs_file_extent_key *key,

/* TODO: checks for crypto_id */
length = le64_to_cpu(val->len_and_flags) & APFS_FILE_EXTENT_LEN_MASK;
+ if (!length)
+ report("Extent record", "length is zero.");
if (length & (sb->s_blocksize - 1))
report("Extent record", "length isn't multiple of block size.");
+
flags = le64_to_cpu(val->len_and_flags) & APFS_FILE_EXTENT_FLAG_MASK;
if (flags)
report("Extent record", "no flags should be set.");
--
2.11.0

[Ernesto A. Fernández]

The fsck tool already supports inodes, dstreams, dentries, xattrs and
siblings. These should be enough for basic operation, and I don't have
access to a filesystem image with other record types, so report them as
unsupported.

Signed-off-by: Ernesto A. Fernández <ernesto.mn...@gmail.com>
---

apfsck/btree.c | 1 +
1 file changed, 1 insertion(+)

diff --git a/apfsck/btree.c b/apfsck/btree.c
index e092ba3..92c8628 100644
--- a/apfsck/btree.c
+++ b/apfsck/btree.c
@@ -523,6 +523,7 @@ static void parse_cat_record(void *key, void *val, int len)
parse_dstream_id_record(key, val, len);
break;
default:
+ report_unknown("Snapshots, encryption, directory statistics");
break;
}
}
--
2.11.0