If an inode has hard links, each one of them must have its own sibling
link record; the dentry will point to this record in its xfields, and
the name and parent will match. To run all these checks, keep both
xfields and sibling records in a linked list for each inode.
apfsck/btree.c | 3 ++
apfsck/dir.c | 38 ++++++++++++++--
apfsck/inode.c | 135 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
apfsck/inode.h | 34 ++++++++++++++-
4 files changed, 205 insertions(+), 5 deletions(-)
diff --git a/apfsck/btree.c b/apfsck/btree.c
index 6724a40..f2200cf 100644
--- a/apfsck/btree.c
+++ b/apfsck/btree.c
@@ -509,6 +509,9 @@ static void parse_cat_record(void *key, void *val, int len)
case APFS_TYPE_FILE_EXTENT:
parse_extent_record(key, val, len);
break;
+ case APFS_TYPE_SIBLING_LINK:
+ parse_sibling_record(key, val, len);
+ break;
default:
break;
}
diff --git a/apfsck/dir.c b/apfsck/dir.c
index a252327..c14ac87 100644
--- a/apfsck/dir.c
+++ b/apfsck/dir.c
@@ -11,19 +11,43 @@
#include "super.h"
/**
+ * read_sibling_id_xfield - Parse a sibling id xfield and check its consistency
+ * @xval: pointer to the xfield value
+ * @len: remaining length of the dentry value
+ * @sibling_id: on return, the sibling id
+ *
+ * Returns the length of the xfield value.
+ */
+static int read_sibling_id_xfield(char *xval, int len, u64 *sibling_id)
+{
+ __le64 *id_raw;
+
+ if (len < 8)
+ report("Sibling link xfield", "doesn't fit in dentry record.");
+ id_raw = (__le64 *)xval;
+
+ *sibling_id = le64_to_cpu(*id_raw);
+
+ return sizeof(*id_raw);
+}
+
+/**
* 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
+ * @sibling_id: on return, the sibling id (0 if none)
*
* Internal consistency of @key must be checked before calling this function.
*/
-static void parse_dentry_xfields(struct apfs_xf_blob *xblob, int len)
+static void parse_dentry_xfields(struct apfs_xf_blob *xblob, int len,
+ u64 *sibling_id)
{
struct apfs_x_field *xfield;
char *xval;
int xcount;
int i;
+ *sibling_id = 0;
if (len == 0) /* No extended fields */
return;
@@ -49,7 +73,7 @@ static void parse_dentry_xfields(struct apfs_xf_blob *xblob, int len)
switch (xfield[i].x_type) {
case APFS_DREC_EXT_TYPE_SIBLING_ID:
- xlen = 8;
+ xlen = read_sibling_id_xfield(xval, len, sibling_id);
break;
default:
report("Dentry xfield", "invalid type.");
@@ -88,7 +112,10 @@ void parse_dentry_record(struct apfs_drec_hashed_key *key,
{
u64 ino, parent_ino;
struct inode *inode, *parent;
+ int namelen = le32_to_cpu(key->name_len_and_hash) & 0x3FFU;
u16 filetype, dtype;
+ u64 sibling_id;
+ struct sibling *sibling;
if (len < sizeof(*val))
report("Dentry record", "value is too small.");
@@ -121,5 +148,10 @@ void parse_dentry_record(struct apfs_drec_hashed_key *key,
inode->i_mode |= dtype << 12;
parse_dentry_xfields((struct apfs_xf_blob *)val->xfields,
- len - sizeof(*val));
+ len - sizeof(*val), &sibling_id);
+
+ if (!sibling_id) /* No sibling record for this dentry */
+ return;
+ sibling = get_sibling(sibling_id, namelen, inode);
+ set_or_check_sibling(parent_ino, namelen, key->name, sibling);
}
diff --git a/apfsck/inode.c b/apfsck/inode.c
index eae78d3..c1da183 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -61,6 +61,37 @@ struct inode **alloc_inode_table(void)
}
/**
+ * free_sibling_links - Free the sibling links for an inode
+ * @inode: inode to free
+ *
+ * Also checks that the number of listed siblings is correct, and that all
+ * of them had both a record and a dentry xfield.
+ */
+static void free_sibling_links(struct inode *inode)
+{
+ struct sibling *current = inode->i_siblings;
+ struct sibling *next;
+ u32 count = 0;
+
+ while (current) {
+ if (!current->s_checked)
+ report("Catalog", "orphaned or missing sibling link.");
+ next = current->s_next;
+ free(current);
+ current = next;
+ ++count;
+ }
+
+ /* Inodes with one link can have a sibling record, but don't need it */
+ if (inode->i_link_count == 1 && count == 0)
+ return;
+
+ if (count != inode->i_link_count)
+ report("Inode record",
+ "link count inconsistent with sibling records.");
+}
+
+/**
* free_inode_table - Free the inode hash table and all its inodes
* @table: table to free
*
@@ -77,6 +108,7 @@ void free_inode_table(struct inode **table)
current = table[i];
while (current) {
check_inode_stats(current);
+ free_sibling_links(current);
next = current->i_next;
free(current);
@@ -428,3 +460,106 @@ void parse_inode_record(struct apfs_inode_key *key,
if ((filetype == S_IFCHR || filetype == S_IFBLK) && !inode->i_rdev)
report("Inode record", "device file with no device ID.");
}
+
+/**
+ * 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 **entry_p = &inode->i_siblings;
+ struct sibling *entry = *entry_p;
+ struct sibling *new;
+
+ /* Siblings are ordered by id in the inode's linked list */
+ while (entry) {
+ if (id == entry->s_id)
+ return entry;
+ if (id < entry->s_id)
+ break;
+
+ entry_p = &entry->s_next;
+ entry = *entry_p;
+ }
+
+ new = calloc(1, sizeof(*new) + namelen);
+ if (!new) {
+ perror(NULL);
+ exit(1);
+ }
+
+ new->s_checked = false;
+ new->s_id = id;
+ new->s_next = entry;
+ *entry_p = new;
+ return new;
+}
+
+/**
+ * set_or_check_sibling - Set or check the fields of a sibling structure
+ * @parent_id: parent id
+ * @namelen: length of the name
+ * @name: name of the sibling
+ * @sibling: the sibling structure
+ *
+ * When first called for @sibling, sets the three given fields. On the second
+ * call, checks that they are set to the correct values.
+ */
+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) {
+ sibling->s_name_len = namelen;
+ strcpy((char *)sibling->s_name, (char *)name);
+ sibling->s_parent_ino = parent_id;
+ return;
+ }
+
+ /* Fields already set, check them */
+ if (sibling->s_name_len != namelen)
+ report("Sibling record", "name length doesn't match dentry's.");
+ if (strcmp((char *)sibling->s_name, (char *)name))
+ report("Sibling record", "name doesn't match dentry's.");
+ if (sibling->s_parent_ino != parent_id)
+ report("Sibling record", "parent id doesn't match dentry's.");
+ sibling->s_checked = true;
+}
+
+/**
+ * parse_sibling_record - Parse and check a sibling link 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_record(struct apfs_sibling_link_key *key,
+ struct apfs_sibling_val *val, int len)
+{
+ struct inode *inode;
+ struct sibling *sibling;
+ int namelen;
+
+ if (len < sizeof(*val))
+ report("Sibling link record", "value is too small.");
+ namelen = le16_to_cpu(val->name_len);
+
+ if (len != sizeof(*val) + namelen)
+ report("Sibling link record", "wrong size of value.");
+ if (val->name[namelen - 1] != 0)
+ report("Sibling link record", "name lacks NULL-termination.");
+ /* Name length doesn't need checking: it's the same for the dentry */
+
+ inode = get_inode(cat_cnid(&key->hdr), vsb->v_inode_table);
+ 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);
+ set_or_check_sibling(le64_to_cpu(val->parent_id), namelen, val->name,
+ sibling);
+}
diff --git a/apfsck/inode.h b/apfsck/inode.h
index ec274dc..ba09eb2 100644
--- a/apfsck/inode.h
+++ b/apfsck/inode.h
@@ -10,6 +10,7 @@
#include "types.h"
struct apfs_inode_key;
+struct apfs_sibling_link_key;
/* Inode numbers for special inodes */
#define APFS_INVALID_INO_NUM 0
@@ -126,6 +127,16 @@ struct apfs_dir_stats_val {
__le64 gen_count;
} __packed;
+/*
+ * Structure of the value for a sibling link record. These are used to
+ * list the hard links for a given inode.
+ */
+struct apfs_sibling_val {
+ __le64 parent_id;
+ __le16 name_len;
+ u8 name[0];
+} __packed;
+
#define INODE_TABLE_BUCKETS 512 /* So the hash table array fits in 4k */
/*
@@ -148,17 +159,36 @@ struct inode {
u32 i_rdev; /* Device ID */
/* Inode stats measured by the fsck */
- u32 i_child_count; /* Number of children of directory */
- u32 i_link_count; /* Number of dentries for file */
+ u32 i_child_count; /* Number of children of directory */
+ u32 i_link_count; /* Number of dentries for file */
+ struct sibling *i_siblings; /* Linked list of siblings for inode */
struct inode *i_next; /* Next inode in linked list */
};
+/*
+ * Sibling link data in memory
+ */
+struct sibling {
+ struct sibling *s_next; /* Next sibling in linked list */
+ u64 s_id; /* Sibling id */
+ bool s_checked; /* Has this sibling been checked? */
+
+ u64 s_parent_ino; /* Inode number for parent */
+ u16 s_name_len; /* Name length */
+ u8 s_name[0]; /* Name */
+};
+
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 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 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);
#endif /* _INODE_H */
--
2.11.0