[PATCH 1/8] apfsck: keep a list of all inodes in a volume

[Ernesto A. Fernández]

While checking the catalog tree, add an entry to a hash table for every
inode record found. For now its only purpose is to verify that inode
numbers are not repeated, but more checks will be added in the future.

Signed-off-by: Ernesto A. Fernández <ernesto.mn...@gmail.com>
---
apfsck/Makefile | 2 +-
apfsck/btree.c | 31 ++++++++++++--
apfsck/inode.c | 109 ++++++++++++++++++++++++++++++++++++++++++++++++++
apfsck/inode.h | 122 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
apfsck/key.c | 25 ------------
apfsck/key.h | 25 ++++++++++++
apfsck/super.c | 5 +++
apfsck/super.h | 1 +
8 files changed, 291 insertions(+), 29 deletions(-)
create mode 100644 apfsck/inode.c
create mode 100644 apfsck/inode.h

diff --git a/apfsck/Makefile b/apfsck/Makefile
index d516a3a..a1c595a 100644
--- a/apfsck/Makefile
+++ b/apfsck/Makefile
@@ -1,4 +1,4 @@
-SRCS = apfsck.c btree.c crc32c.c key.c object.c super.c unicode.c
+SRCS = apfsck.c btree.c crc32c.c inode.c key.c object.c super.c unicode.c
OBJS = $(SRCS:.c=.o)
DEPS = $(SRCS:.c=.d)

diff --git a/apfsck/btree.c b/apfsck/btree.c
index b626a57..9028144 100644
--- a/apfsck/btree.c
+++ b/apfsck/btree.c
@@ -11,6 +11,7 @@
#include <sys/mman.h>
#include "apfsck.h"
#include "btree.h"
+#include "inode.h"
#include "key.h"
#include "object.h"
#include "super.h"
@@ -487,6 +488,25 @@ static void node_compare_bmaps(struct node *node)
}

/**
+ * parse_cat_record - Parse a catalog record value and check for corruption
+ * @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.
+ */
+static void parse_cat_record(void *key, void *val, int len)
+{
+ switch (cat_type(key)) {
+ case APFS_TYPE_INODE:
+ parse_inode_record(key, val, len);
+ break;
+ default:
+ break;
+ }
+}
+
+/**
* parse_subtree - Parse a subtree and check for corruption
* @root: root node of the subtree
* @last_key: parent key, that must come before all the keys in this subtree;
@@ -514,6 +534,7 @@ static void parse_subtree(struct node *root, struct key *last_key)
for (i = 0; i < root->records; ++i) {
struct node *child;
void *raw = root->raw;
+ void *raw_key, *raw_val;
int off, len;
u64 child_id;

@@ -521,16 +542,17 @@ static void parse_subtree(struct node *root, struct key *last_key)
if (len > btree->longest_key)
btree->longest_key = len;
bmap_mark_as_used(root->used_key_bmap, off - root->key, len);
+ raw_key = raw + off;

if (btree_is_omap(btree)) {
- read_omap_key(raw + off, len, &curr_key);
+ read_omap_key(raw_key, len, &curr_key);

/* When a key is added, the node is updated */
if (curr_key.number > root->object.xid)
report("Object map",
"node xid is older than key xid.");
} else {
- read_cat_key(raw + off, len, &curr_key);
+ read_cat_key(raw_key, len, &curr_key);
}

if (keycmp(last_key, &curr_key) > 0)
@@ -543,16 +565,19 @@ static void parse_subtree(struct node *root, struct key *last_key)

len = node_locate_data(root, i, &off);
bmap_mark_as_used(root->used_val_bmap, off - root->data, len);
+ raw_val = raw + off;

if (node_is_leaf(root)) {
if (len > btree->longest_val)
btree->longest_val = len;
+ if (!btree_is_omap(btree))
+ parse_cat_record(raw_key, raw_val, len);
continue;
}

if (len != 8)
report("B-tree", "wrong size of nonleaf record value.");
- child_id = le64_to_cpu(*(__le64 *)(raw + off));
+ child_id = le64_to_cpu(*(__le64 *)(raw_val));
child = read_node(child_id, btree);

if (child->level != root->level - 1)
diff --git a/apfsck/inode.c b/apfsck/inode.c
new file mode 100644
index 0000000..552891f
--- /dev/null
+++ b/apfsck/inode.c
@@ -0,0 +1,109 @@
+/*
+ * apfsprogs/apfsck/inode.c
+ *
+ * Copyright (C) 2018 Ernesto A. Fernández <ernesto.mn...@gmail.com>
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include "apfsck.h"
+#include "inode.h"
+#include "key.h"
+#include "super.h"
+#include "types.h"
+
+/**
+ * alloc_inode_table - Allocates and returns an empty inode hash table
+ */
+struct inode **alloc_inode_table(void)
+{
+ struct inode **table;
+
+ table = calloc(INODE_TABLE_BUCKETS, sizeof(*table));
+ if (!table) {
+ perror(NULL);
+ exit(1);
+ }
+ return table;
+}
+
+/**
+ * free_inode_table - Free the inode hash table and all its inodes
+ * @table: table to free
+ */
+void free_inode_table(struct inode **table)
+{
+ struct inode *current;
+ struct inode *next;
+ int i;
+
+ for (i = 0; i < INODE_TABLE_BUCKETS; ++i) {
+ current = table[i];
+ while (current) {
+ next = current->i_next;
+ free(current);
+ current = next;
+ }
+ }
+ free(table);
+}
+
+/**
+ * get_inode - Find or create an inode structure in a hash table
+ * @ino: inode number
+ * @table: the hash table
+ *
+ * Returns the inode structure, after creating it if necessary.
+ */
+static struct inode *get_inode(u64 ino, struct inode **table)
+{
+ int index = ino % INODE_TABLE_BUCKETS; /* Trivial hash function */
+ struct inode **entry_p = table + index;
+ struct inode *entry = *entry_p;
+ struct inode *new;
+
+ /* Inodes are ordered by ino in each linked list */
+ while (entry) {
+ if (ino == entry->i_ino)
+ return entry;
+ if (ino < entry->i_ino)
+ break;
+
+ entry_p = &entry->i_next;
+ entry = *entry_p;
+ }
+
+ new = malloc(sizeof(*new));
+ if (!new) {
+ perror(NULL);
+ exit(1);
+ }
+
+ new->i_seen = false;
+ new->i_ino = ino;
+ new->i_next = entry;
+ *entry_p = new;
+ return new;
+}
+
+/**
+ * parse_inode_record - Parse an inode record value and check for corruption
+ * @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_inode_record(struct apfs_inode_key *key,
+ struct apfs_inode_val *val, int len)
+{
+ struct inode *inode;
+
+ if (len < sizeof(*val))
+ report("Inode record", "value is too small.");
+
+ inode = get_inode(cat_cnid(&key->hdr), vsb->v_inode_table);
+ if (inode->i_seen)
+ report("Catalog", "inode numbers are repeated.");
+ inode->i_seen = true;
+}
diff --git a/apfsck/inode.h b/apfsck/inode.h
new file mode 100644
index 0000000..19e76cc
--- /dev/null
+++ b/apfsck/inode.h
@@ -0,0 +1,122 @@
+/*
+ * apfsprogs/apfsck/inode.h
+ *
+ * Copyright (C) 2018 Ernesto A. Fernández <ernesto.mn...@gmail.com>
+ */
+
+#ifndef _INODE_H
+#define _INODE_H
+
+#include "types.h"
+
+struct apfs_inode_key;
+
+/* Inode numbers for special inodes */
+#define APFS_INVALID_INO_NUM 0
+
+#define APFS_ROOT_DIR_PARENT 1 /* Root directory parent */
+#define APFS_ROOT_DIR_INO_NUM 2 /* Root directory */
+#define APFS_PRIV_DIR_INO_NUM 3 /* Private directory */
+#define APFS_SNAP_DIR_INO_NUM 6 /* Snapshots metadata */
+
+/* Smallest inode number available for user content */
+#define APFS_MIN_USER_INO_NUM 16
+
+/*
+ * Structure of an inode as stored as a B-tree value
+ */
+struct apfs_inode_val {
+/*00*/ __le64 parent_id;
+ __le64 private_id;
+/*10*/ __le64 create_time;
+ __le64 mod_time;
+ __le64 change_time;
+ __le64 access_time;
+/*30*/ __le64 internal_flags;
+ union {
+ __le32 nchildren;
+ __le32 nlink;
+ };
+ __le32 default_protection_class;
+/*40*/ __le32 write_generation_counter;
+ __le32 bsd_flags;
+ __le32 owner;
+ __le32 group;
+/*50*/ __le16 mode;
+ __le16 pad1;
+ __le64 pad2;
+/*5C*/ u8 xfields[];
+} __packed;
+
+/* Extended field types */
+#define APFS_DREC_EXT_TYPE_SIBLING_ID 1
+
+#define APFS_INO_EXT_TYPE_SNAP_XID 1
+#define APFS_INO_EXT_TYPE_DELTA_TREE_OID 2
+#define APFS_INO_EXT_TYPE_DOCUMENT_ID 3
+#define APFS_INO_EXT_TYPE_NAME 4
+#define APFS_INO_EXT_TYPE_PREV_FSIZE 5
+#define APFS_INO_EXT_TYPE_RESERVED_6 6
+#define APFS_INO_EXT_TYPE_FINDER_INFO 7
+#define APFS_INO_EXT_TYPE_DSTREAM 8
+#define APFS_INO_EXT_TYPE_RESERVED_9 9
+#define APFS_INO_EXT_TYPE_DIR_STATS_KEY 10
+#define APFS_INO_EXT_TYPE_FS_UUID 11
+#define APFS_INO_EXT_TYPE_RESERVED_12 12
+#define APFS_INO_EXT_TYPE_SPARSE_BYTES 13
+#define APFS_INO_EXT_TYPE_RDEV 14
+
+/*
+ * Structure used to store the number and size of extended fields of an inode
+ */
+struct apfs_xf_blob {
+ __le16 xf_num_exts;
+ __le16 xf_used_data;
+ u8 xf_data[];
+} __packed;
+
+/*
+ * Structure used to store an inode's extended field
+ */
+struct apfs_x_field {
+ u8 x_type;
+ u8 x_flags;
+ __le16 x_size;
+} __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 {
+ __le64 size;
+ __le64 alloced_size;
+ __le64 default_crypto_id;
+ __le64 total_bytes_written;
+ __le64 total_bytes_read;
+} __packed;
+
+#define INODE_TABLE_BUCKETS 512 /* So the hash table array fits in 4k */
+
+/*
+ * Inode data in memory
+ */
+struct inode {
+ u64 i_ino; /* Inode number */
+ bool i_seen; /* Has this inode been seen? */
+
+ struct inode *i_next; /* Next inode in linked list */
+};
+
+extern struct inode **alloc_inode_table();
+extern void free_inode_table(struct inode **table);
+extern void parse_inode_record(struct apfs_inode_key *key,
+ struct apfs_inode_val *val, int len);
+
+#endif /* _INODE_H */
diff --git a/apfsck/key.c b/apfsck/key.c
index 192564a..a15e942 100644
--- a/apfsck/key.c
+++ b/apfsck/key.c
@@ -38,31 +38,6 @@ void read_omap_key(void *raw, int size, struct key *key)
}

/**
- * cat_type - Read the record type of a catalog key
- * @key: the raw catalog key
- *
- * The record type is stored in the last byte of the cnid field; this function
- * returns that value.
- */
-static inline int cat_type(struct apfs_key_header *key)
-{
- return (le64_to_cpu(key->obj_id_and_type) & APFS_OBJ_TYPE_MASK)
- >> APFS_OBJ_TYPE_SHIFT;
-}
-
-/**
- * cat_cnid - Read the cnid value on a catalog key
- * @key: the raw catalog key
- *
- * The cnid value shares the its field with the record type. This function
- * masks that part away and returns the result.
- */
-static inline u64 cat_cnid(struct apfs_key_header *key)
-{
- return le64_to_cpu(key->obj_id_and_type) & APFS_OBJ_ID_MASK;
-}
-
-/**
* keycmp - Compare two keys
* @k1, @k2: keys to compare
*
diff --git a/apfsck/key.h b/apfsck/key.h
index 6b1516f..fa550ea 100644
--- a/apfsck/key.h
+++ b/apfsck/key.h
@@ -186,6 +186,31 @@ static inline void init_xattr_key(u64 ino, const char *name, struct key *key)
key->name = name;
}

+/**
+ * cat_type - Read the record type of a catalog key
+ * @key: the raw catalog key
+ *
+ * The record type is stored in the last byte of the cnid field; this function
+ * returns that value.
+ */
+static inline int cat_type(struct apfs_key_header *key)
+{
+ return (le64_to_cpu(key->obj_id_and_type) & APFS_OBJ_TYPE_MASK)
+ >> APFS_OBJ_TYPE_SHIFT;
+}
+
+/**
+ * cat_cnid - Read the cnid value on a catalog key
+ * @key: the raw catalog key
+ *
+ * The cnid value shares the its field with the record type. This function
+ * masks that part away and returns the result.
+ */
+static inline u64 cat_cnid(struct apfs_key_header *key)
+{
+ return le64_to_cpu(key->obj_id_and_type) & APFS_OBJ_ID_MASK;
+}
+
extern int keycmp(struct key *k1, struct key *k2);
extern void read_cat_key(void *raw, int size, struct key *key);
extern void read_omap_key(void *raw, int size, struct key *key);
diff --git a/apfsck/super.c b/apfsck/super.c
index 78f4931..0ec45fe 100644
--- a/apfsck/super.c
+++ b/apfsck/super.c
@@ -10,6 +10,7 @@
#include <sys/mman.h>
#include "apfsck.h"
#include "btree.h"
+#include "inode.h"
#include "object.h"
#include "types.h"
#include "super.h"
@@ -179,6 +180,7 @@ void parse_super(void)
perror(NULL);
exit(1);
}
+ vsb->v_inode_table = alloc_inode_table();

vsb_raw = map_volume_super(vol, vsb);
if (!vsb_raw) {
@@ -194,6 +196,9 @@ void parse_super(void)
le64_to_cpu(vsb_raw->apfs_root_tree_oid),
vsb->v_omap->root);

+ free_inode_table(vsb->v_inode_table);
+ vsb->v_inode_table = NULL;
+
sb->s_volumes[vol] = vsb;
}

diff --git a/apfsck/super.h b/apfsck/super.h
index 9af5fd0..0762d2e 100644
--- a/apfsck/super.h
+++ b/apfsck/super.h
@@ -258,6 +258,7 @@ struct volume_superblock {
struct apfs_superblock *v_raw;
struct btree *v_omap;
struct btree *v_cat;
+ struct inode **v_inode_table; /* Hash table listing the inodes */
struct object v_obj; /* Object holding the volume sb */
};

--
2.11.0

[Ernesto A. Fernández]

Verify that all inode numbers in use are valid, and that the special
directories have the expected fake parent id. I'm not sure if this
is actually correct for the snapshot metadata directory, which I have
not encountered so far.

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

apfsck/inode.c | 17 +++++++++++++++++
1 file changed, 17 insertions(+)

diff --git a/apfsck/inode.c b/apfsck/inode.c
index 552891f..927e103 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -106,4 +106,21 @@ void parse_inode_record(struct apfs_inode_key *key,
if (inode->i_seen)

report("Catalog", "inode numbers are repeated.");

inode->i_seen = true;
+

+ if (inode->i_ino < APFS_MIN_USER_INO_NUM) {
+ switch (inode->i_ino) {
+ case APFS_INVALID_INO_NUM:
+ case APFS_ROOT_DIR_PARENT:
+ report("Inode record", "invalid inode number.");
+ case APFS_ROOT_DIR_INO_NUM:
+ case APFS_PRIV_DIR_INO_NUM:
+ case APFS_SNAP_DIR_INO_NUM:
+ /* All children of this fake parent? TODO: check this */
+ if (le64_to_cpu(val->parent_id) != APFS_ROOT_DIR_PARENT)
+ report("Root inode record", "bad parent id");
+ break;
+ default:
+ report("Inode record", "reserved inode number.");
+ }
+ }
}
--
2.11.0

[Ernesto A. Fernández]

Keep count of the inodes of each type. Later, check this data against
the number reported by the volume superblock. The root and metadata
directories don't seem to be included.

The file count is sometimes off by one. Until the reason is found, do
not report that as corruption.

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

apfsck/inode.c | 22 ++++++++++++++++++++++
apfsck/inode.h | 15 +++++++++++++++
apfsck/super.c | 16 +++++++++++++++-
apfsck/super.h | 7 +++++++
4 files changed, 59 insertions(+), 1 deletion(-)

diff --git a/apfsck/inode.c b/apfsck/inode.c
index 927e103..a79a998 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -123,4 +123,26 @@ void parse_inode_record(struct apfs_inode_key *key,

report("Inode record", "reserved inode number.");
}
}
+

+ inode->i_mode = le16_to_cpu(val->mode);
+ switch (inode->i_mode & S_IFMT) {
+ case S_IFREG:
+ vsb->v_file_count++;
+ break;
+ case S_IFDIR:
+ if (inode->i_ino >= APFS_MIN_USER_INO_NUM)
+ vsb->v_dir_count++;
+ break;
+ case S_IFLNK:
+ vsb->v_symlink_count++;
+ break;
+ case S_IFSOCK:
+ case S_IFBLK:
+ case S_IFCHR:
+ case S_IFIFO:
+ vsb->v_special_count++;
+ break;
+ default:
+ report("Inode record", "invalid file mode.");

+ }
}
diff --git a/apfsck/inode.h b/apfsck/inode.h

index 19e76cc..41e7e77 100644
--- a/apfsck/inode.h
+++ b/apfsck/inode.h
@@ -22,6 +22,19 @@ struct apfs_inode_key;

/* Smallest inode number available for user content */

#define APFS_MIN_USER_INO_NUM 16

+/* File mode flags */
+#define S_IFMT 00170000
+#define S_IFSOCK 0140000
+#define S_IFLNK 0120000
+#define S_IFREG 0100000
+#define S_IFBLK 0060000
+#define S_IFDIR 0040000
+#define S_IFCHR 0020000
+#define S_IFIFO 0010000
+#define S_ISUID 0004000
+#define S_ISGID 0002000
+#define S_ISVTX 0001000
+
/*

* Structure of an inode as stored as a B-tree value

*/
@@ -111,6 +124,8 @@ struct inode {

u64 i_ino; /* Inode number */

bool i_seen; /* Has this inode been seen? */

+ u16 i_mode; /* File mode */

+
struct inode *i_next; /* Next inode in linked list */

};

diff --git a/apfsck/super.c b/apfsck/super.c
index 0ec45fe..15dfed7 100644
--- a/apfsck/super.c
+++ b/apfsck/super.c
@@ -175,7 +175,7 @@ void parse_super(void)
for (vol = 0; vol < APFS_NX_MAX_FILE_SYSTEMS; ++vol) {
struct apfs_superblock *vsb_raw;

- vsb = malloc(sizeof(*vsb));
+ vsb = calloc(1, sizeof(*vsb));
if (!vsb) {
perror(NULL);
exit(1);
@@ -199,6 +199,20 @@ void parse_super(void)
free_inode_table(vsb->v_inode_table);
vsb->v_inode_table = NULL;

+ if (le64_to_cpu(vsb_raw->apfs_num_files) !=
+ vsb->v_file_count)
+ /* Sometimes this is off by one. TODO: why? */
+ printf("Bad file count, may not be corruption.");
+ if (le64_to_cpu(vsb_raw->apfs_num_directories) !=
+ vsb->v_dir_count)
+ report("Volume superblock", "bad directory count.");
+ if (le64_to_cpu(vsb_raw->apfs_num_symlinks) !=
+ vsb->v_symlink_count)
+ report("Volume superblock", "bad symlink count.");
+ if (le64_to_cpu(vsb_raw->apfs_num_other_fsobjects) !=
+ vsb->v_special_count)
+ report("Volume superblock", "bad special file count.");

+
sb->s_volumes[vol] = vsb;
}

diff --git a/apfsck/super.h b/apfsck/super.h

index 0762d2e..7e606c8 100644
--- a/apfsck/super.h
+++ b/apfsck/super.h
@@ -259,6 +259,13 @@ struct volume_superblock {

struct btree *v_omap;
struct btree *v_cat;

struct inode **v_inode_table; /* Hash table listing the inodes */

+
+ /* Volume stats as measured by the fsck */
+ u64 v_file_count; /* Number of files */
+ u64 v_dir_count; /* Number of directories */
+ u64 v_symlink_count; /* Number of symlinks */
+ u64 v_special_count; /* Number of other filesystem objects */
+

[Ernesto A. Fernández]

Check that the padding field of an inode are set to zero. I believe the
documentation implies they might be used in the future, but for now this
should be correct.

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

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

diff --git a/apfsck/inode.c b/apfsck/inode.c
index a79a998..d5e99a9 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -145,4 +145,7 @@ void parse_inode_record(struct apfs_inode_key *key,
default:

report("Inode record", "invalid file mode.");
}
+

+ if (le16_to_cpu(val->pad1) || le64_to_cpu(val->pad2))
+ report("Inode record", "padding should be zeroes.");
}
--
2.11.0

[Ernesto A. Fernández]

Check that count and size of extended fields are consistent for each
inode record.

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

apfsck/inode.c | 94 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
apfsck/inode.h | 10 +++++++
apfsck/types.h | 2 ++
3 files changed, 106 insertions(+)

diff --git a/apfsck/inode.c b/apfsck/inode.c
index d5e99a9..caa18b8 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -6,6 +6,7 @@

#include <stdlib.h>
#include <stdio.h>
+#include <string.h>
#include "apfsck.h"
#include "inode.h"
#include "key.h"
@@ -87,6 +88,97 @@ static struct inode *get_inode(u64 ino, struct inode **table)
}

/**
+ * parse_xfields - Parse and check an inode extended fields
+ * @xblob: pointer to the beginning of the xfields in the inode value
+ * @len: length of the xfields

+ *
+ * Internal consistency of @key must be checked before calling this function.
+ */

+static void parse_xfields(struct apfs_xf_blob *xblob, int len)
+{
+ struct apfs_x_field *xfield;
+ char *xval;
+ int xcount;
+ int i;
+
+ if (len == 0) /* No extended fields */
+ return;
+
+ len -= sizeof(*xblob);
+ if (len < 0)
+ report("Inode records", "no room for extended fields.");
+ xcount = le16_to_cpu(xblob->xf_num_exts);
+
+ xfield = (struct apfs_x_field *)xblob->xf_data;
+ xval = (char *)xfield + xcount * sizeof(xfield[0]);
+ len -= xcount * sizeof(xfield[0]);
+ if (len < 0)
+ report("Inode record", "number of xfields cannot fit.");
+
+ /* The official reference seems to be wrong here */
+ if (le16_to_cpu(xblob->xf_used_data) != len)
+ report("Inode record", "value size incompatible with xfields.");
+
+ for (i = 0; i < le16_to_cpu(xblob->xf_num_exts); ++i) {
+ int xlen, xpad_len;
+
+ switch (xfield[i].x_type) {
+ case APFS_INO_EXT_TYPE_FS_UUID:
+ xlen = 16;
+ break;
+ case APFS_INO_EXT_TYPE_SNAP_XID:
+ case APFS_INO_EXT_TYPE_DELTA_TREE_OID:
+ case APFS_INO_EXT_TYPE_PREV_FSIZE:
+ case APFS_INO_EXT_TYPE_SPARSE_BYTES:
+ xlen = 8;
+ break;
+ case APFS_INO_EXT_TYPE_DOCUMENT_ID:
+ case APFS_INO_EXT_TYPE_FINDER_INFO:
+ case APFS_INO_EXT_TYPE_RDEV:
+ xlen = 4;
+ break;
+ case APFS_INO_EXT_TYPE_NAME:
+ xlen = strnlen(xval, len - 1) + 1;
+ if (xval[xlen - 1] != 0)
+ report("Inode xfield",
+ "name with no null termination");
+ break;
+ case APFS_INO_EXT_TYPE_DSTREAM:
+ xlen = sizeof(struct apfs_dstream);
+ break;
+ case APFS_INO_EXT_TYPE_DIR_STATS_KEY:
+ xlen = sizeof(struct apfs_dir_stats_val);
+ break;
+ case APFS_INO_EXT_TYPE_RESERVED_6:
+ case APFS_INO_EXT_TYPE_RESERVED_9:
+ case APFS_INO_EXT_TYPE_RESERVED_12:
+ report("Inode xfield", "reserved type in use.");
+ break;
+ default:
+ report("Inode xfield", "invalid type.");
+ }
+
+ if (xlen != le16_to_cpu(xfield[i].x_size))
+ report("Inode xfield", "wrong size");
+ len -= xlen;
+ xval += xlen;
+
+ /* Attribute length is padded with zeroes to a multiple of 8 */
+ xpad_len = ROUND_UP(xlen, 8) - xlen;
+ len -= xpad_len;
+ if (len < 0)
+ report("Inode xfield", "does not fit in record value.");
+
+ for (; xpad_len; ++xval, --xpad_len)
+ if (*xval)
+ report("Inode xfield", "non-zero padding.");
+ }
+
+ if (len)
+ report("Inode record", "length of xfields does not add up.");
+}
+
+/**

* parse_inode_record - Parse an inode record value and check for corruption

* @key: pointer to the raw key

* @val: pointer to the raw value

@@ -148,4 +240,6 @@ void parse_inode_record(struct apfs_inode_key *key,

if (le16_to_cpu(val->pad1) || le64_to_cpu(val->pad2))

report("Inode record", "padding should be zeroes.");

+
+ parse_xfields((struct apfs_xf_blob *)val->xfields, len - sizeof(*val));
}
diff --git a/apfsck/inode.h b/apfsck/inode.h
index 41e7e77..a619679 100644
--- a/apfsck/inode.h
+++ b/apfsck/inode.h
@@ -115,6 +115,16 @@ struct apfs_dstream {
__le64 total_bytes_read;
} __packed;

+/*
+ * Structure used to store directory information
+ */
+struct apfs_dir_stats_val {
+ __le64 num_children;
+ __le64 total_size;
+ __le64 chained_key;
+ __le64 gen_count;
+} __packed;
+

#define INODE_TABLE_BUCKETS 512 /* So the hash table array fits in 4k */

/*
diff --git a/apfsck/types.h b/apfsck/types.h
index 568b401..59c2047 100644
--- a/apfsck/types.h
+++ b/apfsck/types.h
@@ -46,6 +46,8 @@ typedef uint64_t __bitwise __le64;
#define le64_to_cpu(x) ((__force u64)(__le64)(x))

#define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d))
+#define __ROUND_MASK(x, y) ((__typeof__(x))((y)-1))
+#define ROUND_UP(x, y) ((((x)-1) | __ROUND_MASK(x, y))+1)

typedef u32 unicode_t;

--
2.11.0

[Ernesto A. Fernández]

Keep track of the number of dentry records linking to each inode, and of
the number of dentries inside each directory. Check that they are sane,
and consistent with the inode metadata. Since this can only be done
after the whole catalog has been parsed, let free_inode_table() take
care of it.

Signed-off-by: Ernesto A. Fernández <ernesto.mn...@gmail.com>
---
apfsck/Makefile | 2 +-

apfsck/btree.c | 4 ++++
apfsck/dir.c | 43 +++++++++++++++++++++++++++++++++++++++++++
apfsck/dir.h | 28 ++++++++++++++++++++++++++++
apfsck/inode.c | 28 ++++++++++++++++++++++++++--
apfsck/inode.h | 10 ++++++++++
6 files changed, 112 insertions(+), 3 deletions(-)
create mode 100644 apfsck/dir.c
create mode 100644 apfsck/dir.h

diff --git a/apfsck/Makefile b/apfsck/Makefile
index a1c595a..ce051b8 100644

--- a/apfsck/Makefile
+++ b/apfsck/Makefile
@@ -1,4 +1,4 @@

-SRCS = apfsck.c btree.c crc32c.c inode.c key.c object.c super.c unicode.c
+SRCS = apfsck.c btree.c crc32c.c dir.c inode.c key.c object.c super.c unicode.c

OBJS = $(SRCS:.c=.o)
DEPS = $(SRCS:.c=.d)

diff --git a/apfsck/btree.c b/apfsck/btree.c

index 9028144..7b6cfa1 100644

--- a/apfsck/btree.c
+++ b/apfsck/btree.c
@@ -11,6 +11,7 @@
#include <sys/mman.h>
#include "apfsck.h"
#include "btree.h"

+#include "dir.h"

#include "inode.h"
#include "key.h"
#include "object.h"

@@ -501,6 +502,9 @@ static void parse_cat_record(void *key, void *val, int len)
case APFS_TYPE_INODE:
parse_inode_record(key, val, len);
break;
+ case APFS_TYPE_DIR_REC:
+ parse_dentry_record(key, val, len);
+ break;
default:
break;
}
diff --git a/apfsck/dir.c b/apfsck/dir.c
new file mode 100644
index 0000000..8f994af
--- /dev/null
+++ b/apfsck/dir.c
@@ -0,0 +1,43 @@
+/*
+ * apfsprogs/apfsck/dir.c

+ *
+ * Copyright (C) 2018 Ernesto A. Fernández <ernesto.mn...@gmail.com>
+ */
+

+#include "apfsck.h"
+#include "dir.h"

+#include "inode.h"
+#include "key.h"
+#include "super.h"
+

+/**
+ * parse_dentry_record - Parse a dentry record value and check for corruption

+ * @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_dentry_record(struct apfs_drec_hashed_key *key,
+ struct apfs_drec_val *val, int len)
+{
+ u64 ino, parent_ino;
+ struct inode *inode, *parent;

+
+ if (len < sizeof(*val))

+ report("Dentry record", "value is too small.");
+
+ ino = le64_to_cpu(val->file_id);
+ inode = get_inode(ino, vsb->v_inode_table);
+ inode->i_link_count++;
+
+ parent_ino = cat_cnid(&key->hdr);
+ if (parent_ino != APFS_ROOT_DIR_PARENT) {
+ parent = get_inode(parent_ino, vsb->v_inode_table);
+ if (!parent->i_seen) /* The b-tree keys are in order */
+ report("Dentry record", "parent inode missing");
+ if ((parent->i_mode & S_IFMT) != S_IFDIR)
+ report("Dentry record", "parent inode not directory.");
+ parent->i_child_count++;
+ }
+}
diff --git a/apfsck/dir.h b/apfsck/dir.h
new file mode 100644
index 0000000..00389df
--- /dev/null
+++ b/apfsck/dir.h
@@ -0,0 +1,28 @@
+/*
+ * apfsprogs/apfsck/dir.h

+ *
+ * Copyright (C) 2018 Ernesto A. Fernández <ernesto.mn...@gmail.com>
+ */
+

+#ifndef _DIR_H
+#define _DIR_H
+
+#include "types.h"
+
+struct apfs_drec_hashed_key;
+
+/*
+ * Structure of the value of a directory entry. This is the data in
+ * the catalog nodes for record type APFS_TYPE_DIR_REC.
+ */
+struct apfs_drec_val {
+ __le64 file_id;
+ __le64 date_added;
+ __le16 flags;
+ u8 xfields[];
+} __packed;
+
+extern void parse_dentry_record(struct apfs_drec_hashed_key *key,
+ struct apfs_drec_val *val, int len);
+
+#endif /* _DIR_H */
diff --git a/apfsck/inode.c b/apfsck/inode.c
index caa18b8..6b14d83 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -14,6 +14,23 @@
#include "types.h"

/**
+ * check_inode_stats - Verify the stats gathered by the fsck vs the metadata
+ * @inode: inode structure to check
+ */
+static void check_inode_stats(struct inode *inode)
+{
+ if ((inode->i_mode & S_IFMT) == S_IFDIR) {
+ if (inode->i_link_count != 1)
+ report("Inode record", "directory has hard links.");
+ if (inode->i_nchildren != inode->i_child_count)
+ report("Inode record", "wrong directory child count.");
+ } else {
+ if (inode->i_nlink != inode->i_link_count)
+ report("Inode record", "wrong link count.");
+ }
+}
+
+/**

* alloc_inode_table - Allocates and returns an empty inode hash table

*/
struct inode **alloc_inode_table(void)
@@ -31,6 +48,9 @@ struct inode **alloc_inode_table(void)
/**

* free_inode_table - Free the inode hash table and all its inodes

* @table: table to free
+ *

+ * Also performs some consistency checks that can only be done after the whole
+ * catalog has been parsed.
*/
void free_inode_table(struct inode **table)
{
@@ -41,6 +61,8 @@ void free_inode_table(struct inode **table)

for (i = 0; i < INODE_TABLE_BUCKETS; ++i) {

current = table[i];
while (current) {
+ check_inode_stats(current);

+
next = current->i_next;

free(current);
current = next;
@@ -56,7 +78,7 @@ void free_inode_table(struct inode **table)
*

* Returns the inode structure, after creating it if necessary.

*/
-static struct inode *get_inode(u64 ino, struct inode **table)
+struct inode *get_inode(u64 ino, struct inode **table)
{

int index = ino % INODE_TABLE_BUCKETS; /* Trivial hash function */

struct inode **entry_p = table + index;

@@ -74,7 +96,7 @@ static struct inode *get_inode(u64 ino, struct inode **table)
entry = *entry_p;
}

- new = malloc(sizeof(*new));
+ new = calloc(1, sizeof(*new));
if (!new) {
perror(NULL);
exit(1);
@@ -238,6 +260,8 @@ void parse_inode_record(struct apfs_inode_key *key,

report("Inode record", "invalid file mode.");
}

+ inode->i_nlink = le32_to_cpu(val->nlink);
+

if (le16_to_cpu(val->pad1) || le64_to_cpu(val->pad2))
report("Inode record", "padding should be zeroes.");

diff --git a/apfsck/inode.h b/apfsck/inode.h
index a619679..c90c040 100644
--- a/apfsck/inode.h
+++ b/apfsck/inode.h
@@ -134,13 +134,23 @@ struct inode {

u64 i_ino; /* Inode number */

bool i_seen; /* Has this inode been seen? */

+ /* Inode information read from its record */

u16 i_mode; /* File mode */

+ union {
+ u32 i_nchildren; /* Number of children of directory */
+ u32 i_nlink; /* Number of hard links to file */
+ };
+
+ /* Inode stats measured by the fsck */
+ u32 i_child_count; /* Number of children of directory */
+ u32 i_link_count; /* Number of dentries for file */

struct inode *i_next; /* Next inode in linked list */

};

extern struct inode **alloc_inode_table();

extern void free_inode_table(struct inode **table);

+extern struct inode *get_inode(u64 ino, struct inode **table);
extern void parse_inode_record(struct apfs_inode_key *key,
struct apfs_inode_val *val, int len);

--
2.11.0

[Ernesto A. Fernández]

The mode of an inode should match the file type of its dentries, except
for a bit shift.

Several dentries may be read before the inode, so save the type into the
higher bits of the i_mode field as soon as we know it. Check that those
are the same for every dentry, and for the inode itself. When the inode
is reached, complete the lower bits.

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

apfsck/dir.c | 13 +++++++++++++
apfsck/inode.c | 12 ++++++++++--
apfsck/inode.h | 2 +-
3 files changed, 24 insertions(+), 3 deletions(-)

diff --git a/apfsck/dir.c b/apfsck/dir.c
index 8f994af..0a4acde 100644
--- a/apfsck/dir.c
+++ b/apfsck/dir.c
@@ -23,6 +23,7 @@ void parse_dentry_record(struct apfs_drec_hashed_key *key,
{
u64 ino, parent_ino;
struct inode *inode, *parent;
+ u16 filetype, dtype;

if (len < sizeof(*val))
report("Dentry record", "value is too small.");
@@ -40,4 +41,16 @@ void parse_dentry_record(struct apfs_drec_hashed_key *key,

report("Dentry record", "parent inode not directory.");

parent->i_child_count++;
}
+
+ dtype = le16_to_cpu(val->flags) & APFS_DREC_TYPE_MASK;
+ if (dtype != le16_to_cpu(val->flags))
+ report("Dentry record", "reserved flags in use.");
+
+ /* The mode may have already been set by the inode or another dentry */
+ filetype = inode->i_mode >> 12;
+ if (filetype && filetype != dtype)
+ report("Dentry record", "file mode doesn't match dentry type.");
+ if (dtype == 0) /* Don't save a 0, that means the mode is not set */
+ report("Dentry record", "invalid dentry type.");
+ inode->i_mode |= dtype << 12;
}
diff --git a/apfsck/inode.c b/apfsck/inode.c
index 6b14d83..705e53f 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -212,6 +212,7 @@ void parse_inode_record(struct apfs_inode_key *key,

struct apfs_inode_val *val, int len)

{
struct inode *inode;
+ u16 mode, filetype;

if (len < sizeof(*val))

report("Inode record", "value is too small.");

@@ -238,8 +239,15 @@ void parse_inode_record(struct apfs_inode_key *key,
}
}

- inode->i_mode = le16_to_cpu(val->mode);
- switch (inode->i_mode & S_IFMT) {
+ mode = le16_to_cpu(val->mode);
+ filetype = mode & S_IFMT;
+
+ /* A dentry may have already set the mode, but only the type bits */
+ if (inode->i_mode && inode->i_mode != filetype)
+ report("Inode record", "file mode doesn't match dentry type.");
+ inode->i_mode = mode;
+
+ switch (filetype) {
case S_IFREG:
vsb->v_file_count++;
break;
diff --git a/apfsck/inode.h b/apfsck/inode.h
index c90c040..a311e19 100644
--- a/apfsck/inode.h
+++ b/apfsck/inode.h
@@ -134,7 +134,7 @@ struct inode {

u64 i_ino; /* Inode number */

bool i_seen; /* Has this inode been seen? */

- /* Inode information read from its record */
+ /* Inode information read from its record (or from its dentries) */

u16 i_mode; /* File mode */

union {

u32 i_nchildren; /* Number of children of directory */

--
2.11.0

[Ernesto A. Fernández]

Check that count and size of extended fields are consistent for each
dentry record. The new code was mostly copied from inode.c, so it may
be a good idea to rework this with a common function in the future.

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

apfsck/dir.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
apfsck/dir.h | 3 +++
apfsck/inode.c | 7 +++---
apfsck/inode.h | 2 --
4 files changed, 75 insertions(+), 5 deletions(-)

diff --git a/apfsck/dir.c b/apfsck/dir.c
index 0a4acde..6488f4a 100644
--- a/apfsck/dir.c
+++ b/apfsck/dir.c
@@ -11,6 +11,71 @@
#include "super.h"

/**
+ * parse_dentry_xfields - Parse and check a dentry extended fields
+ * @xblob: pointer to the beginning of the xfields in the dentry value
+ * @len: length of the xfields

+ *
+ * Internal consistency of @key must be checked before calling this function.
+ */

+static void parse_dentry_xfields(struct apfs_xf_blob *xblob, int len)
+{

+ struct apfs_x_field *xfield;
+ char *xval;
+ int xcount;

+ int i;
+

+ if (len == 0) /* No extended fields */
+ return;
+
+ len -= sizeof(*xblob);
+ if (len < 0)

+ report("Dentry record", "no room for extended fields.");

+ xcount = le16_to_cpu(xblob->xf_num_exts);
+
+ xfield = (struct apfs_x_field *)xblob->xf_data;
+ xval = (char *)xfield + xcount * sizeof(xfield[0]);
+ len -= xcount * sizeof(xfield[0]);
+ if (len < 0)

+ report("Dentry record", "number of xfields cannot fit.");
+

+ /* The official reference seems to be wrong here */
+ if (le16_to_cpu(xblob->xf_used_data) != len)

+ report("Dentry record",

+ "value size incompatible with xfields.");
+
+ /* TODO: could a dentry actually have more than one xfield? */

+ for (i = 0; i < le16_to_cpu(xblob->xf_num_exts); ++i) {
+ int xlen, xpad_len;
+
+ switch (xfield[i].x_type) {

+ case APFS_DREC_EXT_TYPE_SIBLING_ID:
+ xlen = 8;
+ break;
+ default:
+ report("Dentry xfield", "invalid type.");

+ }
+
+ if (xlen != le16_to_cpu(xfield[i].x_size))

+ report("Dentry xfield", "wrong size");

+ len -= xlen;
+ xval += xlen;
+
+ /* Attribute length is padded with zeroes to a multiple of 8 */
+ xpad_len = ROUND_UP(xlen, 8) - xlen;
+ len -= xpad_len;
+ if (len < 0)

+ report("Dentry xfield", "doesn't fit in record value.");

+
+ for (; xpad_len; ++xval, --xpad_len)
+ if (*xval)

+ report("Dentry xfield", "non-zero padding.");

+ }
+
+ if (len)

+ report("Dentry record", "length of xfields does not add up.");
+}
+
+/**
* parse_dentry_record - Parse a dentry record value and check for corruption

* @key: pointer to the raw key

* @val: pointer to the raw value

@@ -53,4 +118,7 @@ void parse_dentry_record(struct apfs_drec_hashed_key *key,

if (dtype == 0) /* Don't save a 0, that means the mode is not set */

report("Dentry record", "invalid dentry type.");

inode->i_mode |= dtype << 12;

+
+ parse_dentry_xfields((struct apfs_xf_blob *)val->xfields,
+ len - sizeof(*val));
}
diff --git a/apfsck/dir.h b/apfsck/dir.h
index 00389df..e97f001 100644
--- a/apfsck/dir.h
+++ b/apfsck/dir.h
@@ -22,6 +22,9 @@ struct apfs_drec_val {
u8 xfields[];
} __packed;

+/* Extended field types */
+#define APFS_DREC_EXT_TYPE_SIBLING_ID 1
+

extern void parse_dentry_record(struct apfs_drec_hashed_key *key,
struct apfs_drec_val *val, int len);

diff --git a/apfsck/inode.c b/apfsck/inode.c
index 705e53f..0337ea3 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -110,13 +110,13 @@ struct inode *get_inode(u64 ino, struct inode **table)
}

/**
- * parse_xfields - Parse and check an inode extended fields
+ * parse_inode_xfields - Parse and check an inode extended fields

* @xblob: pointer to the beginning of the xfields in the inode value

* @len: length of the xfields
*

* Internal consistency of @key must be checked before calling this function.

*/
-static void parse_xfields(struct apfs_xf_blob *xblob, int len)
+static void parse_inode_xfields(struct apfs_xf_blob *xblob, int len)
{
struct apfs_x_field *xfield;
char *xval;
@@ -273,5 +273,6 @@ void parse_inode_record(struct apfs_inode_key *key,

if (le16_to_cpu(val->pad1) || le64_to_cpu(val->pad2))
report("Inode record", "padding should be zeroes.");

- parse_xfields((struct apfs_xf_blob *)val->xfields, len - sizeof(*val));
+ parse_inode_xfields((struct apfs_xf_blob *)val->xfields,
+ len - sizeof(*val));
}
diff --git a/apfsck/inode.h b/apfsck/inode.h
index a311e19..6b9eca4 100644
--- a/apfsck/inode.h
+++ b/apfsck/inode.h
@@ -62,8 +62,6 @@ struct apfs_inode_val {
} __packed;

/* Extended field types */
-#define APFS_DREC_EXT_TYPE_SIBLING_ID 1
-
#define APFS_INO_EXT_TYPE_SNAP_XID 1
#define APFS_INO_EXT_TYPE_DELTA_TREE_OID 2
#define APFS_INO_EXT_TYPE_DOCUMENT_ID 3
--
2.11.0