[PATCH 1/9] apfsck: refactor hash table code

[Ernesto A. Fernández]

Rework all hash table code to be shared by dstreams and inodes, and
move it into the new htable.c and htable.h files.

Signed-off-by: Ernesto A. Fernández <ernesto.mn...@gmail.com>
---
apfsck/Makefile | 2 +-
apfsck/dir.c | 4 +--
apfsck/extents.c | 86 ++++++++++++++----------------------------------
apfsck/extents.h | 14 ++++----
apfsck/htable.c | 88 +++++++++++++++++++++++++++++++++++++++++++++++++
apfsck/htable.h | 40 +++++++++++++++++++++++
apfsck/inode.c | 99 ++++++++++++++++----------------------------------------
apfsck/inode.h | 15 +++++----
apfsck/super.c | 5 +--
apfsck/super.h | 6 ++--
apfsck/xattr.c | 4 +--
11 files changed, 209 insertions(+), 154 deletions(-)
create mode 100644 apfsck/htable.c
create mode 100644 apfsck/htable.h

diff --git a/apfsck/Makefile b/apfsck/Makefile
index 3beeb38..67f8d21 100644
--- a/apfsck/Makefile
+++ b/apfsck/Makefile
@@ -1,4 +1,4 @@
-SRCS = apfsck.c btree.c crc32c.c dir.c extents.c \
+SRCS = apfsck.c btree.c crc32c.c dir.c extents.c htable.c \
inode.c key.c object.c super.c unicode.c xattr.c
OBJS = $(SRCS:.c=.o)
DEPS = $(SRCS:.c=.d)
diff --git a/apfsck/dir.c b/apfsck/dir.c
index d53589d..fc4de1a 100644
--- a/apfsck/dir.c
+++ b/apfsck/dir.c
@@ -104,7 +104,7 @@ void parse_dentry_record(struct apfs_drec_hashed_key *key,
report("Dentry record", "value is too small.");

ino = le64_to_cpu(val->file_id);
- inode = get_inode(ino, vsb->v_inode_table);
+ inode = get_inode(ino);
inode->i_link_count++;

if (!inode->i_first_name) {
@@ -120,7 +120,7 @@ void parse_dentry_record(struct apfs_drec_hashed_key *key,
parent_ino = cat_cnid(&key->hdr);
check_inode_ids(ino, parent_ino);
if (parent_ino != APFS_ROOT_DIR_PARENT) {
- parent = get_inode(parent_ino, vsb->v_inode_table);
+ parent = get_inode(parent_ino);
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)
diff --git a/apfsck/extents.c b/apfsck/extents.c
index a99a2f9..c98f7b0 100644
--- a/apfsck/extents.c
+++ b/apfsck/extents.c
@@ -8,25 +8,11 @@
#include <stdio.h>
#include "apfsck.h"
#include "extents.h"
+#include "htable.h"
#include "key.h"
#include "super.h"

/**
- * alloc_dstream_table - Allocates and returns an empty dstream hash table
- */
-struct dstream **alloc_dstream_table(void)
-{
- struct dstream **table;
-
- table = calloc(DSTREAM_TABLE_BUCKETS, sizeof(*table));
- if (!table) {
- perror(NULL);
- exit(1);
- }
- return table;
-}
-
-/**
* check_dstream_stats - Verify the stats gathered by the fsck vs the metadata
* @dstream: dstream structure to check
*/
@@ -55,63 +41,39 @@ static void check_dstream_stats(struct dstream *dstream)
}

/**
- * free_dstream_table - Free the dstream hash table and all its dstreams
+ * free_dstream - Free a dstream structure after performing some final checks
+ * @entry: the entry to free
+ */
+static void free_dstream(union htable_entry *entry)
+{
+ struct dstream *dstream = &entry->dstream;
+
+ check_dstream_stats(dstream);
+ free(entry);
+}
+
+/**
+ * free_dstream_table - Free the dstream hash table and all its dentries
* @table: table to free
*/
-void free_dstream_table(struct dstream **table)
+void free_dstream_table(union htable_entry **table)
{
- struct dstream *current;
- struct dstream *next;
- int i;
-
- for (i = 0; i < DSTREAM_TABLE_BUCKETS; ++i) {
- current = table[i];
- while (current) {
- check_dstream_stats(current);
-
- next = current->d_next;
- free(current);
- current = next;
- }
- }
- free(table);
+ free_htable(table, free_dstream);
}

/**
- * get_dstream - Find or create a dstream structure in a hash table
+ * get_dstream - Find or create a dstream structure in the dstream hash table
* @id: id of the dstream
- * @table: the hash table
*
* Returns the dstream structure, after creating it if necessary.
*/
-struct dstream *get_dstream(u64 id, struct dstream **table)
+struct dstream *get_dstream(u64 id)
{
- int index = id % DSTREAM_TABLE_BUCKETS; /* Trivial hash function */
- struct dstream **entry_p = table + index;
- struct dstream *entry = *entry_p;
- struct dstream *new;
-
- /* Dstreams are ordered by id in each linked list */
- while (entry) {
- if (id == entry->d_id)
- return entry;
- if (id < entry->d_id)
- break;
-
- entry_p = &entry->d_next;
- entry = *entry_p;
- }
-
- new = calloc(1, sizeof(*new));
- if (!new) {
- perror(NULL);
- exit(1);
- }
+ union htable_entry *entry;

- new->d_id = id;
- new->d_next = entry;
- *entry_p = new;
- return new;
+ entry = get_htable_entry(id, sizeof(struct dstream),
+ vsb->v_dstream_table);
+ return &entry->dstream;
}

/**
@@ -142,7 +104,7 @@ void parse_extent_record(struct apfs_file_extent_key *key,
if (flags)
report("Extent record", "no flags should be set.");

- dstream = get_dstream(cat_cnid(&key->hdr), vsb->v_dstream_table);
+ dstream = get_dstream(cat_cnid(&key->hdr));
if (dstream->d_bytes != le64_to_cpu(key->logical_addr))
report("Data stream", "extents are not consecutive.");
dstream->d_bytes += length;
@@ -167,7 +129,7 @@ void parse_dstream_id_record(struct apfs_dstream_id_key *key,
if (len != sizeof(*val))
report("Dstream id record", "wrong size of value.");

- dstream = get_dstream(cat_cnid(&key->hdr), vsb->v_dstream_table);
+ dstream = get_dstream(cat_cnid(&key->hdr));
dstream->d_seen = true;
dstream->d_refcnt = le32_to_cpu(val->refcnt);
}
diff --git a/apfsck/extents.h b/apfsck/extents.h
index 7c42ba5..35229d4 100644
--- a/apfsck/extents.h
+++ b/apfsck/extents.h
@@ -39,7 +39,12 @@ struct apfs_dstream_id_val {
* Dstream data in memory
*/
struct dstream {
- u64 d_id; /* Id of the dstream */
+ /* Hash table entry header (struct htable_entry_header from htable.h) */
+ struct {
+ union htable_entry *d_next;
+ u64 d_id;
+ };
+
u8 d_obj_type; /* Type of the owner objects */
bool d_seen; /* Has the dstream record been seen? */

@@ -52,13 +57,10 @@ struct dstream {
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 */
};

-extern struct dstream **alloc_dstream_table();
-extern void free_dstream_table(struct dstream **table);
-extern struct dstream *get_dstream(u64 ino, struct dstream **table);
+extern void free_dstream_table(union htable_entry **table);
+extern struct dstream *get_dstream(u64 ino);
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,
diff --git a/apfsck/htable.c b/apfsck/htable.c
new file mode 100644
index 0000000..4e0f33d
--- /dev/null
+++ b/apfsck/htable.c
@@ -0,0 +1,88 @@
+/*
+ * apfsprogs/apfsck/htable.c
+ *
+ * Copyright (C) 2019 Ernesto A. Fernández <ernesto.mn...@gmail.com>
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include "apfsck.h"
+#include "htable.h"
+#include "types.h"
+
+/**
+ * alloc_htable - Allocates and returns an empty hash table
+ */
+union htable_entry **alloc_htable(void)
+{
+ union htable_entry **table;
+
+ table = calloc(HTABLE_BUCKETS, sizeof(*table));
+ if (!table) {
+ perror(NULL);
+ exit(1);
+ }
+ return table;
+}
+
+/**
+ * free_htable - Free a hash table and all its entries
+ * @table: the catalog table to free
+ * @free_entry: function that checks and frees an entry
+ */
+void free_htable(union htable_entry **table,
+ void (*free_entry)(union htable_entry *))
+{
+ union htable_entry *current;
+ union htable_entry *next;
+ int i;
+
+ for (i = 0; i < INODE_TABLE_BUCKETS; ++i) {
+ current = table[i];
+ while (current) {
+ next = current->header.h_next;
+ free_entry(current);
+ current = next;
+ }
+ }
+ free(table);
+}
+
+/**
+ * get_htable_entry - Find or create an entry in a hash table
+ * @id: id of the entry
+ * @size: size of the entry
+ * @table: the hash table
+ *
+ * Returns the entry, after creating it if necessary.
+ */
+union htable_entry *get_htable_entry(u64 id, int size,
+ union htable_entry **table)
+{
+ int index = id % INODE_TABLE_BUCKETS; /* Trivial hash function */
+ union htable_entry **entry_p = table + index;
+ union htable_entry *entry = *entry_p;
+ union htable_entry *new;
+
+ /* In each linked list, entries are ordered by id */
+ while (entry) {
+ if (id == entry->header.h_id)
+ return entry;
+ if (id < entry->header.h_id)
+ break;
+
+ entry_p = &entry->header.h_next;
+ entry = *entry_p;
+ }
+
+ new = calloc(1, size);
+ if (!new) {
+ perror(NULL);
+ exit(1);
+ }
+
+ new->header.h_id = id;
+ new->header.h_next = entry;
+ *entry_p = new;
+ return new;
+}
diff --git a/apfsck/htable.h b/apfsck/htable.h
new file mode 100644
index 0000000..b6100c6
--- /dev/null
+++ b/apfsck/htable.h
@@ -0,0 +1,40 @@
+/*
+ * apfsprogs/apfsck/htable.h
+ *
+ * Copyright (C) 2019 Ernesto A. Fernández <ernesto.mn...@gmail.com>
+ */
+
+#ifndef _HTABLE_H
+#define _HTABLE_H
+
+#include "extents.h"
+#include "inode.h"
+#include "key.h"
+#include "types.h"
+
+#define HTABLE_BUCKETS 512 /* So the hash table array fits in 4k */
+
+/*
+ * Structure of the common header for hash table entries
+ */
+struct htable_entry_header {
+ union htable_entry *h_next; /* Next entry in linked list */
+ u64 h_id; /* Catalog object id of entry */
+};
+
+/*
+ * Generic hash table entry
+ */
+union htable_entry {
+ struct htable_entry_header header; /* Common header */
+ struct inode inode; /* Inode data */
+ struct dstream dstream; /* Dstream data */
+};
+
+extern union htable_entry **alloc_htable();
+extern void free_htable(union htable_entry **table,
+ void (*free_entry)(union htable_entry *));
+extern union htable_entry *get_htable_entry(u64 id, int size,
+ union htable_entry **table);
+
+#endif /* _HTABLE_H */
diff --git a/apfsck/inode.c b/apfsck/inode.c
index 6dedd6c..1f14651 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -10,6 +10,7 @@
#include <string.h>
#include "apfsck.h"
#include "extents.h"
+#include "htable.h"
#include "inode.h"
#include "key.h"
#include "super.h"
@@ -36,7 +37,7 @@ static void check_inode_stats(struct inode *inode)
report("Inode record", "wrong link count.");
}

- dstream = get_dstream(inode->i_private_id, vsb->v_dstream_table);
+ dstream = get_dstream(inode->i_private_id);
if (dstream->d_sparse_bytes != inode->i_sparse_bytes)
report("Inode record", "wrong count of sparse bytes.");

@@ -53,29 +54,11 @@ static void check_inode_stats(struct inode *inode)
}

/**
- * 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_names - Free all data on an inode's names
* @inode: inode to free
*
* Frees the primary name and all sibling links, but not before running a few
* remaining consistency checks.
- * remaining checking that
- * the number of listed siblings is correct, that all of them had both a record
- * and a dentry xfield, and that the primary link matches the primary name.
*/
static void free_inode_names(struct inode *inode)
{
@@ -124,68 +107,42 @@ static void free_inode_names(struct inode *inode)
}

/**
- * free_inode_table - Free the inode hash table and all its inodes
+ * free_inode - Free an inode structure after performing some final checks
+ * @entry: the entry to free
+ */
+static void free_inode(union htable_entry *entry)
+{
+ struct inode *inode = &entry->inode;
+
+ check_inode_stats(inode);
+ free_inode_names(inode);
+ free(entry);
+}
+
+/**
+ * free_inode_table - Free the inode hash table and all its entries
* @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)
+void free_inode_table(union htable_entry **table)
{
- struct inode *current;
- struct inode *next;
- int i;
-
- for (i = 0; i < INODE_TABLE_BUCKETS; ++i) {
- current = table[i];
- while (current) {
- check_inode_stats(current);
- free_inode_names(current);
-
- next = current->i_next;
- free(current);
- current = next;
- }
- }
- free(table);
+ free_htable(table, free_inode);
}

/**
- * get_inode - Find or create an inode structure in a hash table
- * @ino: inode number
- * @table: the hash table
+ * get_inode - Find or create an inode structure in the inode hash table
+ * @ino: inode number
*
* Returns the inode structure, after creating it if necessary.
*/
-struct inode *get_inode(u64 ino, struct inode **table)
+struct inode *get_inode(u64 ino)
{
- 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;
- }
+ union htable_entry *entry;

- new = calloc(1, 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;
+ entry = get_htable_entry(ino, sizeof(struct inode), vsb->v_inode_table);
+ return &entry->inode;
}

/**
@@ -310,7 +267,7 @@ static int read_dstream_xfield(char *xval, int len, struct inode *inode)
size = le64_to_cpu(dstream_raw->size);
alloced_size = le64_to_cpu(dstream_raw->alloced_size);

- dstream = get_dstream(inode->i_private_id, vsb->v_dstream_table);
+ dstream = get_dstream(inode->i_private_id);
if (dstream->d_references) {
/* A dstream structure for this id has already been seen */
if (dstream->d_obj_type != APFS_TYPE_INODE)
@@ -607,7 +564,7 @@ void parse_inode_record(struct apfs_inode_key *key,
if (len < sizeof(*val))
report("Inode record", "value is too small.");

- inode = get_inode(cat_cnid(&key->hdr), vsb->v_inode_table);
+ inode = get_inode(cat_cnid(&key->hdr));
if (inode->i_seen)
report("Catalog", "inode numbers are repeated.");
inode->i_seen = true;
@@ -758,7 +715,7 @@ void parse_sibling_record(struct apfs_sibling_link_key *key,
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);
+ inode = get_inode(cat_cnid(&key->hdr));
if (!inode->i_seen) /* The b-tree keys are in order */
report("Sibling link record", "inode is missing");

@@ -789,7 +746,7 @@ void parse_sibling_map_record(struct apfs_sibling_map_key *key,
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);
+ inode = get_inode(le64_to_cpu(val->file_id));
sibling = get_sibling(cat_cnid(&key->hdr), inode);
sibling->s_mapped = true;
}
diff --git a/apfsck/inode.h b/apfsck/inode.h
index fb4f33d..04f0356 100644
--- a/apfsck/inode.h
+++ b/apfsck/inode.h
@@ -12,6 +12,7 @@
struct apfs_inode_key;
struct apfs_sibling_link_key;
struct apfs_sibling_map_key;
+union htable_entry;

/* Inode numbers for special inodes */
#define APFS_INVALID_INO_NUM 0
@@ -187,7 +188,12 @@ struct apfs_sibling_map_val {
* Inode data in memory
*/
struct inode {
- u64 i_ino; /* Inode number */
+ /* Hash table entry header (struct htable_entry_header from htable.h) */
+ struct {
+ union htable_entry *i_next;
+ u64 i_ino; /* Inode number */
+ };
+
u64 i_private_id; /* Id of the inode's data stream */
bool i_seen; /* Has this inode been seen? */

@@ -208,8 +214,6 @@ struct inode {
u32 i_link_count; /* Number of dentries for file */
char *i_first_name; /* Name of first dentry encountered */
struct sibling *i_siblings; /* Linked list of siblings for inode */
-
- struct inode *i_next; /* Next inode in linked list */
};

/*
@@ -226,9 +230,8 @@ struct sibling {
u8 *s_name; /* In-memory copy of the 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 free_inode_table(union htable_entry **table);
+extern struct inode *get_inode(u64 ino);
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);
diff --git a/apfsck/super.c b/apfsck/super.c
index aba654f..2771c76 100644
--- a/apfsck/super.c
+++ b/apfsck/super.c
@@ -11,6 +11,7 @@
#include "apfsck.h"
#include "btree.h"
#include "extents.h"
+#include "htable.h"
#include "inode.h"
#include "object.h"
#include "types.h"
@@ -183,8 +184,8 @@ void parse_super(void)
perror(NULL);
exit(1);
}
- vsb->v_dstream_table = alloc_dstream_table();
- vsb->v_inode_table = alloc_inode_table();
+ vsb->v_dstream_table = alloc_htable();
+ vsb->v_inode_table = alloc_htable();

vsb_raw = map_volume_super(vol, vsb);
if (!vsb_raw) {
diff --git a/apfsck/super.h b/apfsck/super.h
index 26b332f..7c81698 100644
--- a/apfsck/super.h
+++ b/apfsck/super.h
@@ -10,6 +10,8 @@
#include "types.h"
#include "object.h"

+union htable_entry;
+
/*
* Structure used to store a range of physical blocks
*/
@@ -258,8 +260,8 @@ struct volume_superblock {
struct apfs_superblock *v_raw;
struct btree *v_omap;
struct btree *v_cat;
- struct inode **v_inode_table; /* Hash table of all inodes */
- struct dstream **v_dstream_table; /* Hash table of all dstreams */
+ union htable_entry **v_inode_table; /* Hash table of all inodes */
+ union htable_entry **v_dstream_table; /* Hash table of all dstreams */

/* Volume stats as measured by the fsck */
u64 v_file_count; /* Number of files */
diff --git a/apfsck/xattr.c b/apfsck/xattr.c
index 00d1dbd..d594cd6 100644
--- a/apfsck/xattr.c
+++ b/apfsck/xattr.c
@@ -43,7 +43,7 @@ static void parse_xattr_dstream(struct apfs_xattr_dstream *xstream)
size = le64_to_cpu(dstream_raw->size);
alloced_size = le64_to_cpu(dstream_raw->alloced_size);

- dstream = get_dstream(id, vsb->v_dstream_table);
+ dstream = get_dstream(id);
if (dstream->d_references) {
/* A dstream structure for this id has already been seen */
if (dstream->d_obj_type != APFS_TYPE_XATTR)
@@ -96,7 +96,7 @@ void parse_xattr_record(struct apfs_xattr_key *key,
report("Xattr record", "bad length for embedded data.");
}

- inode = get_inode(cat_cnid(&key->hdr), vsb->v_inode_table);
+ inode = get_inode(cat_cnid(&key->hdr));
if (!inode->i_seen)
report("Catalog", "xattr record with no inode.");

--
2.11.0

[Ernesto A. Fernández]

It seems that the ids of inodes, dstreams and sibling links all come
from the same pool. While their lists are being freed, assemble a new
common list of ids for the purpose of checking that they are not
repeated.

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

apfsck/extents.c | 11 +++++++++++
apfsck/htable.c | 26 ++++++++++++++++++++++++++
apfsck/htable.h | 21 +++++++++++++++++++++
apfsck/inode.c | 22 ++++++++++++++++++++++
apfsck/super.c | 3 +++
apfsck/super.h | 1 +
6 files changed, 84 insertions(+)

diff --git a/apfsck/extents.c b/apfsck/extents.c
index c98f7b0..38a5dbf 100644
--- a/apfsck/extents.c
+++ b/apfsck/extents.c
@@ -4,6 +4,7 @@

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

*/

+#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include "apfsck.h"
@@ -47,6 +48,16 @@ static void check_dstream_stats(struct dstream *dstream)
static void free_dstream(union htable_entry *entry)
{

struct dstream *dstream = &entry->dstream;

+ struct listed_cnid *cnid;
+
+ /* The dstreams must be freed before the cnids */
+ assert(vsb->v_cnid_table);
+
+ /* To check for reuse, put all filesystem object ids in a list */
+ cnid = get_listed_cnid(dstream->d_id);
+ if (cnid->c_state == CNID_USED)
+ report("Catalog", "a filesystem object id was used twice.");
+ cnid->c_state = CNID_USED;

check_dstream_stats(dstream);
free(entry);
diff --git a/apfsck/htable.c b/apfsck/htable.c
index 4e0f33d..9bb401a 100644
--- a/apfsck/htable.c
+++ b/apfsck/htable.c
@@ -8,6 +8,7 @@
#include <stdio.h>
#include "apfsck.h"
#include "htable.h"
+#include "super.h"
#include "types.h"

/**
@@ -86,3 +87,28 @@ union htable_entry *get_htable_entry(u64 id, int size,
*entry_p = new;
return new;
}
+
+/**
+ * free_cnid_table - Free the cnid hash table and all its entries
+ * @table: table to free
+ */
+void free_cnid_table(union htable_entry **table)
+{
+ /* No checks needed here, just call free() on each entry */
+ free_htable(table, (void (*)(union htable_entry *))free);
+}
+
+/**
+ * get_listed_cnid - Find or create a cnid structure in the cnid hash table
+ * @id: the cnid
+ *
+ * Returns the cnid structure, after creating it if necessary.
+ */
+struct listed_cnid *get_listed_cnid(u64 id)
+{
+ union htable_entry *entry;
+
+ entry = get_htable_entry(id, sizeof(struct listed_cnid),
+ vsb->v_cnid_table);
+ return &entry->listed_cnid;

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

index b6100c6..5e7e0a2 100644
--- a/apfsck/htable.h
+++ b/apfsck/htable.h
@@ -22,6 +22,24 @@ struct htable_entry_header {

u64 h_id; /* Catalog object id of entry */

};

+/* State of the in-memory listed cnid structure */
+#define CNID_UNUSED 0 /* The cnid is unused */
+#define CNID_USED 1 /* The cnid is used, and can't be reused */
+#define CNID_DSTREAM_ALLOWED 2 /* The cnid can be reused by one dstream */
+
+/*
+ * Structure used to register each catalog node id (cnid) that has been seen,
+ * and check that they are not repeated.
+ */
+struct listed_cnid {
+ /* Hash table entry header (struct htable_entry_header) */
+ struct {
+ union htable_entry *c_next;
+ u64 c_id;
+ };
+ u8 c_state;
+};
+
/*

* Generic hash table entry

*/
@@ -29,6 +47,7 @@ union htable_entry {

struct htable_entry_header header; /* Common header */

struct inode inode; /* Inode data */

struct dstream dstream; /* Dstream data */

+ struct listed_cnid listed_cnid; /* Catalog id data */
};

extern union htable_entry **alloc_htable();
@@ -36,5 +55,7 @@ extern void free_htable(union htable_entry **table,
void (*free_entry)(union htable_entry *));

extern union htable_entry *get_htable_entry(u64 id, int size,

union htable_entry **table);
+extern void free_cnid_table(union htable_entry **table);
+extern struct listed_cnid *get_listed_cnid(u64 id);

#endif /* _HTABLE_H */
diff --git a/apfsck/inode.c b/apfsck/inode.c

index 1f14651..d16e995 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -86,10 +86,19 @@ static void free_inode_names(struct inode *inode)
inode->i_first_name = NULL;

while (current) {
+ struct listed_cnid *cnid;
+
+ /* Put all filesystem object ids in a list to check for reuse */
+ cnid = get_listed_cnid(current->s_id);
+ if (cnid->c_state != CNID_UNUSED)
+ report("Catalog", "a filesystem object id was reused.");
+ cnid->c_state = CNID_USED;
+
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);
@@ -113,6 +122,19 @@ static void free_inode_names(struct inode *inode)
static void free_inode(union htable_entry *entry)
{

struct inode *inode = &entry->inode;

+ struct listed_cnid *cnid;
+
+ /* The inodes must be freed before the cnids */
+ assert(vsb->v_cnid_table);
+
+ /* To check for reuse, put all filesystem object ids in a list */
+ cnid = get_listed_cnid(inode->i_ino);
+ if (cnid->c_state != CNID_UNUSED)
+ report("Catalog", "a filesystem object id was used twice.");
+ if (inode->i_ino != inode->i_private_id)
+ cnid->c_state = CNID_USED;
+ else /* The inode and its dstream share an id */
+ cnid->c_state = CNID_DSTREAM_ALLOWED;

check_inode_stats(inode);
free_inode_names(inode);
diff --git a/apfsck/super.c b/apfsck/super.c
index 2771c76..d5e5668 100644
--- a/apfsck/super.c
+++ b/apfsck/super.c
@@ -184,6 +184,7 @@ void parse_super(void)
perror(NULL);
exit(1);
}
+ vsb->v_cnid_table = alloc_htable();
vsb->v_dstream_table = alloc_htable();
vsb->v_inode_table = alloc_htable();

@@ -205,6 +206,8 @@ void parse_super(void)
vsb->v_inode_table = NULL;
free_dstream_table(vsb->v_dstream_table);
vsb->v_dstream_table = NULL;
+ free_cnid_table(vsb->v_cnid_table);
+ vsb->v_cnid_table = NULL;

if (le64_to_cpu(vsb_raw->apfs_num_files) !=
vsb->v_file_count)
diff --git a/apfsck/super.h b/apfsck/super.h
index 7c81698..f07b5a1 100644
--- a/apfsck/super.h
+++ b/apfsck/super.h
@@ -262,6 +262,7 @@ struct volume_superblock {
struct btree *v_cat;

union htable_entry **v_inode_table; /* Hash table of all inodes */

union htable_entry **v_dstream_table; /* Hash table of all dstreams */

+ union htable_entry **v_cnid_table; /* Hash table of all cnids */

/* Volume stats as measured by the fsck */
u64 v_file_count; /* Number of files */

--
2.11.0

[Ernesto A. Fernández]

Since it was first added, check_inode_stats() has been creating dstream
structures for every inode it checks. This was not a problem when we
were only checking the size, because the newly created dstream would be
empty anyway.

But when checks were added for the number of references, I started to
notice a large number of dstreams that seemed to have none. I thought
this was a sign of some sort of garbage collection and put messy checks
in place to deal with it.

Stop calling get_dstream() from check_inode_stats(), and instead keep a
pointer to the dstream in the inode structure. Report dstreams with no
references as corruption.

Fixes: 647278ebfa25 ("apfsck: check dstream id records")

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

apfsck/extents.c | 11 ++++-------
apfsck/inode.c | 12 +++++++++---
apfsck/inode.h | 1 +
3 files changed, 14 insertions(+), 10 deletions(-)

diff --git a/apfsck/extents.c b/apfsck/extents.c
index 38a5dbf..359a67a 100644
--- a/apfsck/extents.c
+++ b/apfsck/extents.c
@@ -19,22 +19,19 @@
*/

static void check_dstream_stats(struct dstream *dstream)

{
+ if (!dstream->d_references)
+ report("Data stream", "has no references.");
+
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)
+ if (!dstream->d_seen)
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)
diff --git a/apfsck/inode.c b/apfsck/inode.c
index d16e995..bcca9a7 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -37,9 +37,14 @@ static void check_inode_stats(struct inode *inode)

report("Inode record", "wrong link count.");
}

- dstream = get_dstream(inode->i_private_id);
- if (dstream->d_sparse_bytes != inode->i_sparse_bytes)
- report("Inode record", "wrong count of sparse bytes.");
+ dstream = inode->i_dstream;
+ if (dstream) {
+ if (dstream->d_sparse_bytes != inode->i_sparse_bytes)
+ report("Inode record", "wrong count of sparse bytes.");
+ } else {
+ if (inode->i_sparse_bytes)
+ report("Inode record", "sparse bytes without dstream.");
+ }

if ((bool)(inode->i_xattr_bmap & XATTR_BMAP_SYMLINK) !=
(bool)((inode->i_mode & S_IFMT) == S_IFLNK))
@@ -307,6 +312,7 @@ static int read_dstream_xfield(char *xval, int len, struct inode *inode)
}

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

diff --git a/apfsck/inode.h b/apfsck/inode.h
index 04f0356..20f4fa8 100644
--- a/apfsck/inode.h
+++ b/apfsck/inode.h
@@ -207,6 +207,7 @@ struct inode {
u64 i_flags; /* Internal flags */
u32 i_rdev; /* Device ID */
char *i_name; /* Name of primary link */
+ struct dstream *i_dstream; /* The inode's dstream (can be NULL) */

/* Inode stats measured by the fsck */
u8 i_xattr_bmap; /* Bitmap of system xattrs for inode */
--
2.11.0

[Ernesto A. Fernández]

Check that the id of a data stream is above APFS_MIN_USER_INO_NUM, like
we do for the inode and sibling ids.

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 359a67a..4edbafe 100644
--- a/apfsck/extents.c
+++ b/apfsck/extents.c
@@ -10,6 +10,7 @@
#include "apfsck.h"
#include "extents.h"
#include "htable.h"
+#include "inode.h"
#include "key.h"
#include "super.h"

@@ -21,6 +22,8 @@ static void check_dstream_stats(struct dstream *dstream)
{
if (!dstream->d_references)

report("Data stream", "has no references.");

+ if (dstream->d_id < APFS_MIN_USER_INO_NUM)
+ report("Data stream", "invalid or reserved id.");

if (dstream->d_obj_type == APFS_TYPE_XATTR) {
if (dstream->d_seen || dstream->d_references != 1)

--
2.11.0

[Ernesto A. Fernández]

Verify that no data stream is present on directories, symlinks or
special files.

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 bcca9a7..7ea77f3 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -287,6 +287,9 @@ static int read_dstream_xfield(char *xval, int len, struct inode *inode)
struct dstream *dstream;
u64 size, alloced_size;

+ if ((inode->i_mode & S_IFMT) != S_IFREG)
+ report("Inode record", "has dstream but isn't a regular file.");
+
if (len < sizeof(*dstream_raw))
report("Dstream xfield", "doesn't fit in inode record.");
dstream_raw = (struct apfs_dstream *)xval;
--
2.11.0

[Ernesto A. Fernández]

Verify that the id of all filesystem objects (inodes, siblings and data
streams) comes before the next id to be assigned according to the volume
superblock.

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

apfsck/extents.c | 2 ++
apfsck/inode.c | 5 +++++
apfsck/super.c | 1 +
apfsck/super.h | 1 +
4 files changed, 9 insertions(+)

diff --git a/apfsck/extents.c b/apfsck/extents.c
index 4edbafe..1578f58 100644
--- a/apfsck/extents.c
+++ b/apfsck/extents.c
@@ -24,6 +24,8 @@ static void check_dstream_stats(struct dstream *dstream)

report("Data stream", "has no references.");

if (dstream->d_id < APFS_MIN_USER_INO_NUM)

report("Data stream", "invalid or reserved id.");

+ if (dstream->d_id >= vsb->v_next_obj_id)
+ report("Data stream", "free id in use.");

if (dstream->d_obj_type == APFS_TYPE_XATTR) {
if (dstream->d_seen || dstream->d_references != 1)

diff --git a/apfsck/inode.c b/apfsck/inode.c
index 7ea77f3..9153772 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -543,6 +543,9 @@ static void check_inode_internal_flags(u64 flags)
*/

void check_inode_ids(u64 ino, u64 parent_ino)

{
+ if (ino >= vsb->v_next_obj_id || parent_ino >= vsb->v_next_obj_id)
+ report("Inode record", "free inode number in use.");
+
if (ino < APFS_MIN_USER_INO_NUM) {
switch (ino) {
case APFS_INVALID_INO_NUM:
@@ -755,6 +758,8 @@ void parse_sibling_record(struct apfs_sibling_link_key *key,
/* It seems that sibling ids come from the same pool as inode numbers */
if (sibling->s_id < APFS_MIN_USER_INO_NUM)
report("Sibling record", "invalid sibling id.");
+ if (sibling->s_id >= vsb->v_next_obj_id)
+ report("Sibling record", "free id in use.");

set_or_check_sibling(le64_to_cpu(val->parent_id), namelen, val->name,
sibling);
diff --git a/apfsck/super.c b/apfsck/super.c
index d5e5668..755645d 100644
--- a/apfsck/super.c
+++ b/apfsck/super.c
@@ -155,6 +155,7 @@ static struct apfs_superblock *map_volume_super(int vol,
if (le32_to_cpu(vsb->v_raw->apfs_magic) != APFS_MAGIC)
report("Volume superblock", "wrong magic.");

+ vsb->v_next_obj_id = le64_to_cpu(vsb->v_raw->apfs_next_obj_id);
vsb->v_next_doc_id = le32_to_cpu(vsb->v_raw->apfs_next_doc_id);
return vsb->v_raw;
}
diff --git a/apfsck/super.h b/apfsck/super.h
index f07b5a1..4146292 100644
--- a/apfsck/super.h
+++ b/apfsck/super.h
@@ -271,6 +271,7 @@ struct volume_superblock {
u64 v_special_count; /* Number of other filesystem objects */

/* Volume information read from the on-disk structure */
+ u64 v_next_obj_id; /* Next cnid to be assigned */
u32 v_next_doc_id; /* Next document identifier to be assigned */

struct object v_obj; /* Object holding the volume sb */
--
2.11.0

[Ernesto A. Fernández]

Check that the parent id reported by an inode matches the parent of its
primary link.

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

apfsck/dir.c | 21 +++++++++++----------
apfsck/inode.c | 7 ++++++-
apfsck/inode.h | 2 ++
3 files changed, 19 insertions(+), 11 deletions(-)

diff --git a/apfsck/dir.c b/apfsck/dir.c
index fc4de1a..6cf45be 100644
--- a/apfsck/dir.c
+++ b/apfsck/dir.c
@@ -107,16 +107,6 @@ void parse_dentry_record(struct apfs_drec_hashed_key *key,

inode = get_inode(ino);
inode->i_link_count++;

- if (!inode->i_first_name) {
- /* No dentry for this inode has been seen before */
- inode->i_first_name = malloc(namelen);
- if (!inode->i_first_name) {

- perror(NULL);
- exit(1);
- }

- strcpy(inode->i_first_name, (char *)key->name);
- }
-

parent_ino = cat_cnid(&key->hdr);
check_inode_ids(ino, parent_ino);
if (parent_ino != APFS_ROOT_DIR_PARENT) {

@@ -128,6 +118,17 @@ void parse_dentry_record(struct apfs_drec_hashed_key *key,
parent->i_child_count++;
}

+ if (!inode->i_first_name) {
+ /* No dentry for this inode has been seen before */
+ inode->i_first_name = malloc(namelen);
+ if (!inode->i_first_name) {

+ perror(NULL);
+ exit(1);
+ }

+ strcpy(inode->i_first_name, (char *)key->name);
+ inode->i_first_parent = parent_ino;
+ }
+
dtype = le16_to_cpu(val->flags) & APFS_DREC_TYPE_MASK;
if (dtype != le16_to_cpu(val->flags))
report("Dentry record", "reserved flags in use.");
diff --git a/apfsck/inode.c b/apfsck/inode.c
index 9153772..f2d2e80 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -80,10 +80,14 @@ static void free_inode_names(struct inode *inode)
/* Primary link has lowest id, so it comes first in the list */
if (strcmp(inode->i_name, (char *)current->s_name))
report("Inode record", "wrong name for primary link.");
+ if (inode->i_parent_id != current->s_parent_ino)
+ report("Inode record", "bad parent for primary link.");
} else {
/* No siblings, so the primary link is the first and only */
if (strcmp(inode->i_name, inode->i_first_name))
report("Inode record", "wrong name for only link.");
+ if (inode->i_parent_id != inode->i_first_parent)
+ report("Inode record", "bad parent for only link.");
}
free(inode->i_name);
inode->i_name = NULL;
@@ -604,7 +608,8 @@ void parse_inode_record(struct apfs_inode_key *key,
inode->i_seen = true;
inode->i_private_id = le64_to_cpu(val->private_id);

- check_inode_ids(inode->i_ino, le64_to_cpu(val->parent_id));
+ inode->i_parent_id = le64_to_cpu(val->parent_id);
+ check_inode_ids(inode->i_ino, inode->i_parent_id);

inode->i_flags = le64_to_cpu(val->internal_flags);
check_inode_internal_flags(inode->i_flags);
diff --git a/apfsck/inode.h b/apfsck/inode.h
index 20f4fa8..1a0e3da 100644
--- a/apfsck/inode.h
+++ b/apfsck/inode.h

@@ -207,6 +207,7 @@ struct inode {
u64 i_flags; /* Internal flags */
u32 i_rdev; /* Device ID */
char *i_name; /* Name of primary link */

+ u64 i_parent_id; /* Parent id for the primary link */

struct dstream *i_dstream; /* The inode's dstream (can be NULL) */

/* Inode stats measured by the fsck */
@@ -214,6 +215,7 @@ struct inode {
u32 i_child_count; /* Number of children of directory */

u32 i_link_count; /* Number of dentries for file */
char *i_first_name; /* Name of first dentry encountered */

+ u64 i_first_parent; /* Parent id of the first dentry seen */

struct sibling *i_siblings; /* Linked list of siblings for inode */

};

--
2.11.0

[Ernesto A. Fernández]

The root and private directories must be present in all volumes, so add
a check for that.

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

apfsck/inode.c | 5 +++++
apfsck/super.c | 5 +++++
apfsck/super.h | 2 ++
3 files changed, 12 insertions(+)

diff --git a/apfsck/inode.c b/apfsck/inode.c
index f2d2e80..2e2e477 100644
--- a/apfsck/inode.c
+++ b/apfsck/inode.c
@@ -611,6 +611,11 @@ void parse_inode_record(struct apfs_inode_key *key,

inode->i_parent_id = le64_to_cpu(val->parent_id);

check_inode_ids(inode->i_ino, inode->i_parent_id);

+ if (inode->i_ino == APFS_ROOT_DIR_INO_NUM)
+ vsb->v_has_root = true;
+ if (inode->i_ino == APFS_PRIV_DIR_INO_NUM)
+ vsb->v_has_priv = true;
+

inode->i_flags = le64_to_cpu(val->internal_flags);
check_inode_internal_flags(inode->i_flags);

diff --git a/apfsck/super.c b/apfsck/super.c
index 755645d..ad68897 100644
--- a/apfsck/super.c
+++ b/apfsck/super.c
@@ -210,6 +210,11 @@ void parse_super(void)
free_cnid_table(vsb->v_cnid_table);
vsb->v_cnid_table = NULL;

+ if (!vsb->v_has_root)
+ report("Catalog", "the root directory is missing.");
+ if (!vsb->v_has_priv)
+ report("Catalog", "the private directory is missing.");
+

if (le64_to_cpu(vsb_raw->apfs_num_files) !=
vsb->v_file_count)

/* Sometimes this is off by one. TODO: why? */
diff --git a/apfsck/super.h b/apfsck/super.h
index 4146292..ab4db77 100644
--- a/apfsck/super.h
+++ b/apfsck/super.h
@@ -269,6 +269,8 @@ struct volume_superblock {
u64 v_dir_count; /* Number of directories */
u64 v_symlink_count; /* Number of symlinks */

u64 v_special_count; /* Number of other filesystem objects */

+ bool v_has_root; /* Is there a root directory? */
+ bool v_has_priv; /* Is there a private directory? */

/* Volume information read from the on-disk structure */

u64 v_next_obj_id; /* Next cnid to be assigned */

--
2.11.0

[Ernesto A. Fernández]

The root and private directories must be named "root" and "private-dir",
respectively. Check this when reading their dentries.

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

apfsck/dir.c | 8 +++++++-
1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/apfsck/dir.c b/apfsck/dir.c
index 6cf45be..795ed3d 100644
--- a/apfsck/dir.c
+++ b/apfsck/dir.c
@@ -95,6 +95,7 @@ void parse_dentry_record(struct apfs_drec_hashed_key *key,
{
u64 ino, parent_ino;
struct inode *inode, *parent;
+ char *name = (char *)key->name;
int namelen = le32_to_cpu(key->name_len_and_hash) & 0x3FFU;
u16 filetype, dtype;
u64 sibling_id;
@@ -107,6 +108,11 @@ void parse_dentry_record(struct apfs_drec_hashed_key *key,

inode = get_inode(ino);
inode->i_link_count++;

+ if (ino == APFS_ROOT_DIR_INO_NUM && strcmp(name, "root"))
+ report("Root directory", "wrong name.");
+ if (ino == APFS_PRIV_DIR_INO_NUM && strcmp(name, "private-dir"))
+ report("Private directory", "wrong name.");
+

parent_ino = cat_cnid(&key->hdr);
check_inode_ids(ino, parent_ino);
if (parent_ino != APFS_ROOT_DIR_PARENT) {

@@ -125,7 +131,7 @@ void parse_dentry_record(struct apfs_drec_hashed_key *key,
perror(NULL);
exit(1);

}
- strcpy(inode->i_first_name, (char *)key->name);

+ strcpy(inode->i_first_name, name);
inode->i_first_parent = parent_ino;
}

--
2.11.0