Composefs: an opportunistically sharing verified image filesystem

This commit adds the on-disk layout header file of composefs.

Signed-off-by Alexander Larsson <[email protected]>

Co-developed-by Giuseppe Scrivano <[email protected]>

Signed-off-by Giuseppe Scrivano <[email protected]>

---
 fs/composefs/cfs.h | 203 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 203 insertions(+)
 create mode 100644 fs/composefs/cfs.h

fs/composefs/cfs.h new file +10 -0

new file mode 100644
index 000000000000..658df728e366
@@ -0,0 +1,203 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * composefs
+ *
+ * Copyright (C) 2021 Giuseppe Scrivano
+ * Copyright (C) 2022 Alexander Larsson
+ *
+ * This file is released under the GPL.
+ */
+

fs/composefs/cfs.h new file +37 -0

+
+static inline int cfs_digest_from_payload(const char *payload, size_t payload_len,
+					  u8 digest_out[SHA256_DIGEST_SIZE])
+{
+	const char *p, *end;
+	u8 last_digit = 0;
+	int digit = 0;
+	size_t n_nibbles = 0;
+
+	/* This handles payloads (i.e. path names) that are "essentially" a
+	 * digest as the digest (if the DIGEST_FROM_PAYLOAD flag is set). The
+	 * "essential" part means that we ignore hierarchical structure as well
+	 * as any extension. So, for example "ef/deadbeef.file" would match the
+	 * (too short) digest "efdeadbeef".
+	 *
+	 * This allows images to avoid storing both the digest and the pathname,
+	 * yet work with pre-existing object store formats of various kinds.
+	 */
+
+	end = payload + payload_len;
+	for (p = payload; p != end; p++) {
+		/* Skip subdir structure */
+		if (*p == '/')
+			continue;
+
+		/* Break at (and ignore) extension */
+		if (*p == '.')
+			break;
+
+		if (n_nibbles == SHA256_DIGEST_SIZE * 2)
+			return -EINVAL; /* Too long */
+
+		digit = hex_to_bin(*p);
+		if (digit == -1)
+			return -EINVAL; /* Not hex digit */
+
+		n_nibbles++;

fs/composefs/cfs.h new file +6 -0

+
+static inline u32 cfs_inode_encoded_size(u32 flags)
+{
+	return sizeof(u32) /* flags */ +
+	       CFS_INODE_FLAG_CHECK_SIZE(flags, PAYLOAD, sizeof(u32)) +
+	       CFS_INODE_FLAG_CHECK_SIZE(flags, MODE, sizeof(u32)) +

Quoted 1 line · Alexander Larsson

This commit adds the on-disk layout header file of composefs.

This isn't really a useful commit message.

Perhaps it should actually explain what the overall goals of the on-disk format are - space usage, complexity trade-offs, potential issues with validation of variable payload sections, etc.

Quoted 30 lines

Signed-off-by Alexander Larsson <[email protected]>

Co-developed-by Giuseppe Scrivano <[email protected]>

Signed-off-by Giuseppe Scrivano <[email protected]>

---
 fs/composefs/cfs.h | 203
+++++++++++++++++++++++++++++++++++++++++++++

 1 file changed, 203 insertions(+)

 create mode 100644 fs/composefs/cfs.h

fs/composefs/cfs.h new file +15 -0

new file mode 100644
index 000000000000..658df728e366
@@ -0,0 +1,203 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * composefs
+ *
+ * Copyright (C) 2021 Giuseppe Scrivano
+ * Copyright (C) 2022 Alexander Larsson
+ *
+ * This file is released under the GPL.
+ */
+
+#ifndef _CFS_H
+#define _CFS_H
+
+#include <asm/byteorder.h>
+#include <crypto/sha2.h>

fs/composefs/cfs.h line 20

Quoted 5 lines

fs/composefs/cfs.h new file +5 -0

+#include <linux/fs.h>
+#include <linux/stat.h>
+#include <linux/types.h>
+
+#define CFS_VERSION 1

This should start with a description of the on-disk format for the version 1 format.

fs/composefs/cfs.h line 25

Quoted 5 lines

fs/composefs/cfs.h new file +5 -0

+
+#define CFS_MAGIC 0xc078629aU
+
+#define CFS_MAX_DIR_CHUNK_SIZE 4096
+#define CFS_MAX_XATTRS_SIZE 4096

How do we store 64kB xattrs in this format if the max attr size is 4096 bytes? Or is that the maximum total xattr storage?

A comment telling us what these limits are would be nice.

Quoted 50 lines

fs/composefs/cfs.h new file +2 -0

+
+static inline int cfs_digest_from_payload(const char *payload,

size_t payload_len,
+                                         u8 digest_out[SHA256_DIGEST_SIZE])

fs/composefs/cfs.h new file +7 -0

+{
+       const char *p, *end;
+       u8 last_digit = 0;
+       int digit = 0;
+       size_t n_nibbles = 0;
+
+       /* This handles payloads (i.e. path names) that are

"essentially" a
+        * digest as the digest (if the DIGEST_FROM_PAYLOAD flag is set). The
+        * "essential" part means that we ignore hierarchical structure as well
+        * as any extension. So, for example "ef/deadbeef.file" would match the
+        * (too short) digest "efdeadbeef".
+        *
+        * This allows images to avoid storing both the digest and the pathname,
+        * yet work with pre-existing object store formats of various kinds.
+        */

fs/composefs/cfs.h new file +21 -0

+
+       end = payload + payload_len;
+       for (p = payload; p != end; p++) {
+               /* Skip subdir structure */
+               if (*p == '/')
+                       continue;
+
+               /* Break at (and ignore) extension */
+               if (*p == '.')
+                       break;
+
+               if (n_nibbles == SHA256_DIGEST_SIZE * 2)
+                       return -EINVAL; /* Too long */
+
+               digit = hex_to_bin(*p);
+               if (digit == -1)
+                       return -EINVAL; /* Not hex digit */
+
+               n_nibbles++;
+               if ((n_nibbles % 2) == 0)
+                       digest_out[n_nibbles / 2 - 1] = (last_digit

<< 4) | digit;
+               last_digit = digit;
+       }

fs/composefs/cfs.h line 72

Quoted 6 lines

fs/composefs/cfs.h new file +6 -0

+
+       if (n_nibbles != SHA256_DIGEST_SIZE * 2)
+               return -EINVAL; /* Too short */
+
+       return 0;
+}

Too big to be a inline function.

fs/composefs/cfs.h

Quoted 2 lines

fs/composefs/cfs.h new file +2 -0

+
+struct cfs_vdata_s {

Drop the "_s" suffix to indicate the type is a structure - that's waht "struct" tells us.

Quoted 2 lines

+       u64 off;
+       u32 len;

If these are on-disk format structures, why aren't the defined as using the specific endian they are encoded in? i.e. __le64, __le32, etc? Otherwise a file built on a big endian machine won't be readable on a little endian machine (and vice versa).

fs/composefs/cfs.h line 82

Quoted 7 lines

fs/composefs/cfs.h new file +6 -0

+} __packed;
+
+struct cfs_header_s {
+       u8 version;
+       u8 unused1;
+       u16 unused2;

Why are you hyper-optimising these structures for minimal space usage? This is 2023 - we can use a __le32 for the version number, the magic number and then leave....

fs/composefs/cfs.h line 88

Quoted 6 lines

fs/composefs/cfs.h new file +6 -0

+
+       u32 magic;
+       u64 data_offset;
+       u64 root_inode;
+
+       u64 unused3[2];

a whole heap of space to round it up to at least a CPU cacheline size using something like "__le64 unused[15]".

That way we don't need packed structures nor do we care about having weird little holes in the structures to fill....

Quoted 10 lines

fs/composefs/cfs.h new file +10 -0

+} __packed;
+
+enum cfs_inode_flags {
+       CFS_INODE_FLAGS_NONE = 0,
+       CFS_INODE_FLAGS_PAYLOAD = 1 << 0,
+       CFS_INODE_FLAGS_MODE = 1 << 1,
+       CFS_INODE_FLAGS_NLINK = 1 << 2,
+       CFS_INODE_FLAGS_UIDGID = 1 << 3,
+       CFS_INODE_FLAGS_RDEV = 1 << 4,
+       CFS_INODE_FLAGS_TIMES = 1 << 5,

Quoted 5 lines

+       CFS_INODE_FLAGS_TIMES_NSEC = 1 << 6,
+       CFS_INODE_FLAGS_LOW_SIZE = 1 << 7, /* Low 32bit of st_size */
+       CFS_INODE_FLAGS_HIGH_SIZE = 1 << 8, /* High 32bit of st_size */

Why do we need to complicate things by splitting the inode size like this?

Quoted 10 lines

+       CFS_INODE_FLAGS_XATTRS = 1 << 9,
+       CFS_INODE_FLAGS_DIGEST = 1 << 10, /* fs-verity sha256 digest */
+       CFS_INODE_FLAGS_DIGEST_FROM_PAYLOAD = 1 << 11, /* Compute digest from payload */

fs/composefs/cfs.h new file +3 -0

+};
+
+#define CFS_INODE_FLAG_CHECK(_flag,

_name)                                     \
+       (((_flag) & (CFS_INODE_FLAGS_##_name)) != 0)

Check what about a flag? If this is a "check that a feature is set", then open coding it better, but if you must do it like this, then please use static inline functions like:

        if (cfs_inode_has_xattrs(inode->flags)) {
                .....
        }

Quoted 3 lines

+#define CFS_INODE_FLAG_CHECK_SIZE(_flag, _name, _size)                         \
+       (CFS_INODE_FLAG_CHECK(_flag, _name) ? (_size) : 0)

This doesn't seem particularly useful, because you've still got to test is the return value is valid. i.e.

        size = CFS_INODE_FLAG_CHECK_SIZE(inode->flags, XATTRS, 32); if (size == 32) {
                /* got xattrs, decode! */
        }

vs
        if (cfs_inode_has_xattrs(inode->flags)) {
                /* decode! */
        }

fs/composefs/cfs.h line 117

Quoted 8 lines

fs/composefs/cfs.h new file +7 -0

+
+#define CFS_INODE_DEFAULT_MODE 0100644
+#define CFS_INODE_DEFAULT_NLINK 1
+#define CFS_INODE_DEFAULT_NLINK_DIR 2
+#define CFS_INODE_DEFAULT_UIDGID 0
+#define CFS_INODE_DEFAULT_RDEV 0
+#define CFS_INODE_DEFAULT_TIMES 0

Where do these get used? Are they on disk defaults or something else? (comment, please!)

fs/composefs/cfs.h line 122

Quoted 4 lines

fs/composefs/cfs.h new file +4 -0

+struct cfs_inode_s {
+       u32 flags;
+
+       /* Optional data: (selected by flags) */

WHy would you make them optional given that all the fields are still defined in the structure?

It's much simpler just to decode the entire structure into memory than to have to check each flag value to determine if a field needs to be decoded...

Quoted 4 lines

+       /* This is the size of the type specific data that comes directly after
+        * the inode in the file. Of this type:
+        *

Quoted 8 lines

+        * directory: cfs_dir_s
+        * regular file: the backing filename +        * symlink: the target link
+        *
+        * Canonically payload_length is 0 for empty dir/file/symlink.
+        */
+       u32 payload_length;

How do you have an empty symlink?

Quoted 10 lines

+       u32 st_mode; /* File type and mode.  */
+       u32 st_nlink; /* Number of hard links, only for regular files.  */
+       u32 st_uid; /* User ID of owner.  */
+       u32 st_gid; /* Group ID of owner.  */
+       u32 st_rdev; /* Device ID (if special file).  */ +       u64 st_size; /* Size of file, only used for regular files */
+
+       struct cfs_vdata_s xattrs; /* ref to variable data */

This is in the payload that follows the inode?  Is it included in the payload_length above?

If not, where is this stuff located, how do we validate it points to the correct place in the on-disk format file, the xattrs belong to this specific inode, etc? I think that's kinda important to describe, because xattrs often contain important security information...

Quoted 3 lines

+
+       u8 digest[SHA256_DIGEST_SIZE]; /* fs-verity digest */

Why would you have this in the on-disk structure, then also have "digest from payload" that allows the digest to be in the payload section of the inode data?

Quoted 6 lines

+
+       struct timespec64 st_mtim; /* Time of last modification. */
+       struct timespec64 st_ctim; /* Time of last status change. */
+};

This really feels like an in-memory format inode, not an on-disk format inode, because this:

Quoted 22 lines

fs/composefs/cfs.h new file +5 -0

+
+static inline u32 cfs_inode_encoded_size(u32 flags)
+{
+       return sizeof(u32) /* flags */ +
+              CFS_INODE_FLAG_CHECK_SIZE(flags, PAYLOAD,

sizeof(u32)) +
+              CFS_INODE_FLAG_CHECK_SIZE(flags, MODE, sizeof(u32))

fs/composefs/cfs.h new file +8 -0

+
+              CFS_INODE_FLAG_CHECK_SIZE(flags, NLINK, sizeof(u32))
+
+              CFS_INODE_FLAG_CHECK_SIZE(flags, UIDGID, sizeof(u32)
+ sizeof(u32)) +
+              CFS_INODE_FLAG_CHECK_SIZE(flags, RDEV, sizeof(u32))
+
+              CFS_INODE_FLAG_CHECK_SIZE(flags, TIMES, sizeof(u64)

* 2) +
+              CFS_INODE_FLAG_CHECK_SIZE(flags, TIMES_NSEC, sizeof(u32) * 2) +
+              CFS_INODE_FLAG_CHECK_SIZE(flags, LOW_SIZE, sizeof(u32)) +
+              CFS_INODE_FLAG_CHECK_SIZE(flags, HIGH_SIZE, sizeof(u32)) +

Quoted 5 lines

+              CFS_INODE_FLAG_CHECK_SIZE(flags, XATTRS, sizeof(u64)
+ sizeof(u32)) +
+              CFS_INODE_FLAG_CHECK_SIZE(flags, DIGEST, SHA256_DIGEST_SIZE);
+}

looks like the on-disk format is an encoded format hyper-optimised for minimal storage space usage?

Without comments to explain it, I'm not exactly sure what is stored in the on-disk format inodes, nor the layout of the variable payload section or how payload sections are defined and verified.

Seems overly complex to me - it's far simpler just to have a fixed inode structure and just decode it directly into the in-memory structure when it is read....

Quoted 3 lines

+struct cfs_dentry_s {
+       /* Index of struct cfs_inode_s */

Not a useful (or correct!) comment :/

Also, the typical term for this on disk structure in a filesystem is a "dirent", and this is also what readdir() returns to userspace. dentry is typically used internally in the kernel to refer to the VFS cache layer objects, not the filesystem dirents the VFS layers look up to populate it's dentry cache.

Quoted 4 lines

+       u64 inode_index;
+       u8 d_type;
+       u8 name_len;
+       u16 name_offset;

What's this name_offset refer to?

fs/composefs/cfs.h line 177

Quoted 6 lines

fs/composefs/cfs.h new file +6 -0

+} __packed;
+
+struct cfs_dir_chunk_s {
+       u16 n_dentries;
+       u16 chunk_size;
+       u64 chunk_offset;

What's this chunk offset refer to?

fs/composefs/cfs.h line 183

Quoted 6 lines

fs/composefs/cfs.h new file +6 -0

+} __packed;
+
+struct cfs_dir_s {
+       u32 n_chunks;
+       struct cfs_dir_chunk_s chunks[];
+} __packed;

So directory data is packed in discrete chunks? Given that this is a static directory format, and the size of the directory is known at image creation time, why does the storage need to be chunked?

Quoted 6 lines

fs/composefs/cfs.h new file +2 -0

+
+#define

cfs_dir_size(_n_chunks)
    \
+       (sizeof(struct cfs_dir_s) + (_n_chunks) * sizeof(struct cfs_dir_chunk_s))

static inline, at least.

Also, this appears to be the size of the encoded directory header, not the size of the directory itself. cfs_dir_header_size(), perhaps, to match the cfs_xattr_header_size() function that does the same thing?

Quoted 9 lines · Dave Chinner

Quoted 1 line · Alexander Larsson

This commit adds the on-disk layout header file of composefs.

This isn't really a useful commit message.

Perhaps it should actually explain what the overall goals of the on-disk format are - space usage, complexity trade-offs, potential issues with validation of variable payload sections, etc.

I agree, will flesh it out. But, as for below discussions, one of the overall goals is to keep the on-disk file size low.

Quoted 30 lines

Quoted 30 lines

Signed-off-by Alexander Larsson <[email protected]>

Co-developed-by Giuseppe Scrivano <[email protected]>

Signed-off-by Giuseppe Scrivano <[email protected]>

---
 fs/composefs/cfs.h | 203
+++++++++++++++++++++++++++++++++++++++++++++

 1 file changed, 203 insertions(+)

 create mode 100644 fs/composefs/cfs.h

fs/composefs/cfs.h new file +15 -0

new file mode 100644
index 000000000000..658df728e366
@@ -0,0 +1,203 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * composefs
+ *
+ * Copyright (C) 2021 Giuseppe Scrivano
+ * Copyright (C) 2022 Alexander Larsson
+ *
+ * This file is released under the GPL.
+ */
+
+#ifndef _CFS_H
+#define _CFS_H
+
+#include <asm/byteorder.h>
+#include <crypto/sha2.h>

Quoted 8 lines

fs/composefs/cfs.h line 20

Quoted 5 lines

fs/composefs/cfs.h new file +5 -0

+#include <linux/fs.h>
+#include <linux/stat.h>
+#include <linux/types.h>
+
+#define CFS_VERSION 1

This should start with a description of the on-disk format for the version 1 format.

There are some format descriptions in the later document patch. What is the general approach here, do we document in the header, or in separate doc file? For example, I don't see much of format descriptions in the xfs headers. I mean, I should probably add *some* info here for easier reading of the stuff below, but I don't feel like headers are a great place for docs.

Quoted 8 lines

fs/composefs/cfs.h line 25

Quoted 5 lines

fs/composefs/cfs.h new file +5 -0

+
+#define CFS_MAGIC 0xc078629aU
+
+#define CFS_MAX_DIR_CHUNK_SIZE 4096
+#define CFS_MAX_XATTRS_SIZE 4096

How do we store 64kB xattrs in this format if the max attr size is 4096 bytes? Or is that the maximum total xattr storage?

This is a current limitation of the composefs file format.

I am aware
that the kernel maximum size is 64k,

Quoted 4 lines

Quoted 4 lines

fs/composefs/cfs.h new file +1 -0

+static inline int cfs_digest_from_payload(const char *payload,

size_t payload_len,
+                                         u8 digest_out[SHA256_DIGEST_SIZE])

Quoted 1 line

Too big to be a inline function.

Yeah, I'm aware of this. I mainly put it in the header as the implementation of it is sort of part of the on-disk format. But, I can move it to a .c file instead.

Quoted 4 lines

Quoted 1 line

+struct cfs_vdata_s {

Drop the "_s" suffix to indicate the type is a structure - that's waht "struct" tells us.

Sure.

Quoted 7 lines

Quoted 2 lines

+       u64 off;
+       u32 len;

If these are on-disk format structures, why aren't the defined as using the specific endian they are encoded in? i.e. __le64, __le32, etc? Otherwise a file built on a big endian machine won't be readable on a little endian machine (and vice versa).

On disk all fields are little endian. However, when we read them from disk we convert them using e.g. le32_to_cpu(), and then we use the same structure in memory, with native endian. So, it seems wrong to mark them as little endian.

Quoted 23 lines

fs/composefs/cfs.h line 82

Quoted 8 lines

fs/composefs/cfs.h new file +6 -0

+} __packed;
+
+struct cfs_header_s {
+       u8 version;
+       u8 unused1;
+       u16 unused2;

Why are you hyper-optimising these structures for minimal space usage? This is 2023 - we can use a __le32 for the version number, the magic number and then leave....

fs/composefs/cfs.h line 88

Quoted 6 lines

fs/composefs/cfs.h new file +6 -0

+
+       u32 magic;
+       u64 data_offset;
+       u64 root_inode;
+
+       u64 unused3[2];

a whole heap of space to round it up to at least a CPU cacheline size using something like "__le64 unused[15]".

Quoted 2 lines

That way we don't need packed structures nor do we care about having weird little holes in the structures to fill....

Sure.

Quoted 10 lines

Quoted 10 lines

fs/composefs/cfs.h new file +10 -0

+} __packed;
+
+enum cfs_inode_flags {
+       CFS_INODE_FLAGS_NONE = 0,
+       CFS_INODE_FLAGS_PAYLOAD = 1 << 0,
+       CFS_INODE_FLAGS_MODE = 1 << 1,
+       CFS_INODE_FLAGS_NLINK = 1 << 2,
+       CFS_INODE_FLAGS_UIDGID = 1 << 3,
+       CFS_INODE_FLAGS_RDEV = 1 << 4,
+       CFS_INODE_FLAGS_TIMES = 1 << 5,

Quoted 9 lines

Quoted 5 lines

+       CFS_INODE_FLAGS_TIMES_NSEC = 1 << 6,
+       CFS_INODE_FLAGS_LOW_SIZE = 1 << 7, /* Low 32bit of st_size */
+       CFS_INODE_FLAGS_HIGH_SIZE = 1 << 8, /* High 32bit of st_size */

Why do we need to complicate things by splitting the inode size like this?

The goal is to minimize the image size for a typical rootfs or container image. Almost zero files in any such images are > 4GB.

Also, we don't just "not decode" the items with the flag not set, they are not even stored on disk.

Quoted 16 lines

Quoted 11 lines

+       CFS_INODE_FLAGS_XATTRS = 1 << 9,
+       CFS_INODE_FLAGS_DIGEST = 1 << 10, /* fs-verity sha256 digest */
+       CFS_INODE_FLAGS_DIGEST_FROM_PAYLOAD = 1 << 11, /* Compute digest from payload */

fs/composefs/cfs.h new file +3 -0

+};
+
+#define CFS_INODE_FLAG_CHECK(_flag,

_name)                                     \
+       (((_flag) & (CFS_INODE_FLAGS_##_name)) != 0)

Check what about a flag? If this is a "check that a feature is set", then open coding it better, but if you must do it like this, then please use static inline functions like:

Quoted 4 lines

        if (cfs_inode_has_xattrs(inode->flags)) {
                .....
        }

The check is if the flag is set, so maybe CFS_INODE_FLAG_IS_SET is a better name. This is used only when decoding the on-disk version of the inode to the in memory one, which is a bunch of:

	if (CFS_INODE_FLAG_CHECK(ino->flags, THE_FIELD))
		ino->the_field = cfs_read_u32(&data);
	else
		ino->the_field = THE_FIELD_DEFUALT;

I can easily open-code these checks, although I'm not sure it makes a great difference either way.

Quoted 9 lines

fs/composefs/cfs.h line 117

Quoted 6 lines

fs/composefs/cfs.h new file +6 -0

+#define CFS_INODE_DEFAULT_MODE 0100644
+#define CFS_INODE_DEFAULT_NLINK 1
+#define CFS_INODE_DEFAULT_NLINK_DIR 2
+#define CFS_INODE_DEFAULT_UIDGID 0
+#define CFS_INODE_DEFAULT_RDEV 0
+#define CFS_INODE_DEFAULT_TIMES 0

Where do these get used? Are they on disk defaults or something else? (comment, please!)

They are the defaults that are used when inode fields on disk are missing. I'll add some comments.

Quoted 11 lines

Quoted 10 lines

+       u32 st_mode; /* File type and mode.  */
+       u32 st_nlink; /* Number of hard links, only for regular files.  */
+       u32 st_uid; /* User ID of owner.  */
+       u32 st_gid; /* Group ID of owner.  */
+       u32 st_rdev; /* Device ID (if special file).  */ +       u64 st_size; /* Size of file, only used for regular files */
+
+       struct cfs_vdata_s xattrs; /* ref to variable data */

Quoted 8 lines

This is in the payload that follows the inode?  Is it included in the payload_length above?

If not, where is this stuff located, how do we validate it points to the correct place in the on-disk format file, the xattrs belong to this specific inode, etc? I think that's kinda important to describe, because xattrs often contain important security information...

No, all inodes are packed into the initial part of the file, each containing a flags set, a variable size (from flags) chunk of fixed size elements and an variable size payload. The payload is either the target symlink for symlinks, or the path of the backing file for regular files.

Other data, such as xattrs and dirents are stored in a separate part of the file and the offsets for those in the inode refer to offsets into that area.

Quoted 3 lines

Why would you have this in the on-disk structure, then also have "digest from payload" that allows the digest to be in the payload section of the inode data?

The payload is normally the path to the backing file, and then you need to store the verity digest separately. This is what would be needed when using this with ostree for instance, because we have an existing backing file repo format we can't change.

However, if your backing
store files are stored by their fs-verity digest already (which is the default for mkcomposefs), then we can set this flag and avoid storing the digest unnecessary.

Quoted 8 lines

fs/composefs/cfs.h line 183

Quoted 4 lines

fs/composefs/cfs.h new file +4 -0

+struct cfs_dir_s {
+       u32 n_chunks;
+       struct cfs_dir_chunk_s chunks[];
+} __packed;

So directory data is packed in discrete chunks? Given that this is a static directory format, and the size of the directory is known at image creation time, why does the storage need to be chunked?

We chunk the data such that each chunk fits inside a single page in the image file. I did this to make accessing image data directly from the page cache easier.

Quoted 1 line

Quoted 1 line

+#define CFS_MAX_DIR_CHUNK_SIZE 4096

We can just kmap_page_local() each chunk and treat
it as a non-split continuous dirent array, then move on to the next chunk in the next page.

If we had dirent data spanning multiple pages
then we would either need to map the pages consecutively (which seems hard/costly) or have complex in-kernel code to handle the case where a dirent straddles two pages.

Quoted 57 lines · Alexander Larsson

Quoted 11 lines · Dave Chinner

Quoted 1 line · Alexander Larsson

This commit adds the on-disk layout header file of composefs.

This isn't really a useful commit message.

Perhaps it should actually explain what the overall goals of the on-disk format are - space usage, complexity trade-offs, potential
issues with validation of variable payload sections, etc.

I agree, will flesh it out. But, as for below discussions, one of the
overall goals is to keep the on-disk file size low.

Quoted 31 lines

Quoted 31 lines

Signed-off-by Alexander Larsson <[email protected]>

Co-developed-by Giuseppe Scrivano <[email protected]>

Signed-off-by Giuseppe Scrivano <[email protected]>

---
 fs/composefs/cfs.h | 203
+++++++++++++++++++++++++++++++++++++++++++++

 1 file changed, 203 insertions(+)

 create mode 100644 fs/composefs/cfs.h

fs/composefs/cfs.h new file +16 -0

new file mode 100644
index 000000000000..658df728e366
@@ -0,0 +1,203 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * composefs
+ *
+ * Copyright (C) 2021 Giuseppe Scrivano
+ * Copyright (C) 2022 Alexander Larsson
+ *
+ * This file is released under the GPL.
+ */
+
+#ifndef _CFS_H
+#define _CFS_H
+
+#include <asm/byteorder.h>
+#include <crypto/sha2.h>
+#include <linux/fs.h>

Quoted 8 lines

fs/composefs/cfs.h line 20

Quoted 4 lines

fs/composefs/cfs.h new file +4 -0

+#include <linux/stat.h>
+#include <linux/types.h>
+
+#define CFS_VERSION 1

This should start with a description of the on-disk format for the
version 1 format.

Quoted 11 lines

There are some format descriptions in the later document patch. What is
the general approach here, do we document in the header, or in separate
doc file? For example, I don't see much of format descriptions in the
xfs headers. I mean, I should probably add *some* info here for easier
reading of the stuff below, but I don't feel like headers are a great
place for docs.

it's fine to describe the format in the docs, but when reading the code there needs to at least an overview of the structure the code is implementing so that the code makes some sense without having to go find the external place the format is documented.

Quoted 10 lines

Quoted 9 lines

fs/composefs/cfs.h line 25

Quoted 5 lines

fs/composefs/cfs.h new file +4 -0

+#define CFS_MAGIC 0xc078629aU
+
+#define CFS_MAX_DIR_CHUNK_SIZE 4096
+#define CFS_MAX_XATTRS_SIZE 4096

How do we store 64kB xattrs in this format if the max attr size is
4096 bytes? Or is that the maximum total xattr storage?

Quoted 1 line

This is a current limitation of the composefs file format.

Yes, but is that 4kB limit the maximum size of a single xattr, or is it the total xattr storage space for an inode?

Quoted 2 lines

I am aware
that the kernel maximum size is 64k,

For a single xattr, yes. Hence my question....

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

fs/composefs/cfs.h new file +1 -0

+static inline int cfs_digest_from_payload(const char *payload,

size_t payload_len,
+                                         u8 digest_out[SHA256_DIGEST_SIZE])

.....

Quoted 6 lines

Quoted 1 line

Too big to be a inline function.

Yeah, I'm aware of this. I mainly put it in the header as the implementation of it is sort of part of the on-disk format. But, I can
move it to a .c file instead.

Please do - it's really part of the reader implementation, not the structure definition.

Quoted 16 lines

Quoted 4 lines

Quoted 1 line

+struct cfs_vdata_s {

Drop the "_s" suffix to indicate the type is a structure - that's waht "struct" tells us.

Sure.

Quoted 8 lines

Quoted 2 lines

+       u64 off;
+       u32 len;

If these are on-disk format structures, why aren't the defined as using the specific endian they are encoded in? i.e. __le64, __le32,
etc? Otherwise a file built on a big endian machine won't be readable on a little endian machine (and vice versa).

Quoted 6 lines

On disk all fields are little endian. However, when we read them from
disk we convert them using e.g. le32_to_cpu(), and then we use the same
structure in memory, with native endian. So, it seems wrong to mark them as little endian.

Then these structures do not define "on-disk format". Looking a bit further through the patchset, these are largely intermediate structures that are read once to instatiate objects in memory, then never used again. The cfs_inode_s is a good example of this - I'll come back to that.

Quoted 25 lines

Quoted 24 lines

fs/composefs/cfs.h line 82

Quoted 6 lines

fs/composefs/cfs.h new file +6 -0

+} __packed;
+
+struct cfs_header_s {
+       u8 version;
+       u8 unused1;
+       u16 unused2;

Why are you hyper-optimising these structures for minimal space usage? This is 2023 - we can use a __le32 for the version number, the magic number and then leave....

fs/composefs/cfs.h line 88

Quoted 6 lines

fs/composefs/cfs.h new file +6 -0

+
+       u32 magic;
+       u64 data_offset;
+       u64 root_inode;
+
+       u64 unused3[2];

a whole heap of space to round it up to at least a CPU cacheline size using something like "__le64 unused[15]".

That way we don't need packed structures nor do we care about having
weird little holes in the structures to fill....

Quoted 1 line

Sure.

FWIW, now I see how this is used, this header kinda defines what we'd call the superblock in the on-disk format of a filesystem. It's at a fixed location in the image file, so there should be a #define somewhere in this file to document it's fixed location.

Also, if this is the in-memory representation of the structure and not the actual on-disk format, why does it even need padding, packing or even store the magic number?

i.e. this information could simply be stored in a few fields in the cfs
superblock structure that wraps the vfs superblock, and the superblock read function could decode straight into those fields...

Quoted 21 lines

Quoted 11 lines

Quoted 11 lines

fs/composefs/cfs.h new file +11 -0

+} __packed;
+
+enum cfs_inode_flags {
+       CFS_INODE_FLAGS_NONE = 0,
+       CFS_INODE_FLAGS_PAYLOAD = 1 << 0,
+       CFS_INODE_FLAGS_MODE = 1 << 1,
+       CFS_INODE_FLAGS_NLINK = 1 << 2,
+       CFS_INODE_FLAGS_UIDGID = 1 << 3,
+       CFS_INODE_FLAGS_RDEV = 1 << 4,
+       CFS_INODE_FLAGS_TIMES = 1 << 5,
+       CFS_INODE_FLAGS_TIMES_NSEC = 1 << 6,

Quoted 9 lines

Quoted 5 lines

+       CFS_INODE_FLAGS_LOW_SIZE = 1 << 7, /* Low 32bit of st_size
*/
+       CFS_INODE_FLAGS_HIGH_SIZE = 1 << 8, /* High 32bit of st_size */

Why do we need to complicate things by splitting the inode size like this?

Quoted 2 lines

The goal is to minimize the image size for a typical rootfs or container image. Almost zero files in any such images are > 4GB.

Sure, but how much space does this typically save, versus how much complexity it adds to runtime decoding of inodes?

I mean, in a dense container system the critical resources that need to be saved is runtime memory and CPU overhead of operations, not the storage space. Saving a 30-40 bytes of storage space per inode means a typical image might ber a few MB smaller, but given the image file is not storing data we're only talking about images the use maybe 500 bytes of data per inode. Storage space for images is not a limiting factor, nor is network transmission (because compression), so it comes back to runtime CPU and memory usage.

The inodes are decoded out of the page cache, so the memory for the raw inode information is volatile and reclaimed when needed. Similarly, the VFS inode built from this information is reclaimable when not in use, too. So the only real overhead for runtime is the decoding time to find the inode in the image file and then decode it.

Given the decoding of the inode -all branches- and is not straight-line code, it cannot be well optimised and the CPU branch predictor is not going to get it right every time. Straight line code that decodes every field whether it is zero or not is going to be faster.

Further, with a fixed size inode in the image file, the inode table can be entirely fixed size, getting rid of the whole unaligned data retreival problem that code currently has (yes, all that "le32_to_cpu(__get_unaligned(__le32, data)" code) because we can ensure that all the inode fields are aligned in the data pages. This will significantly speed up decoding into the in-memory inode structures.

And to take it another step, the entire struct cfs_inode_s structure could go away - it is entirely a temporary structure used to shuffle data from the on-disk encoded format to the the initialisation of the VFS inode. The on-disk inode data could be decoded directly into the VFS inode after it has been instantiated, rather than decoding the inode from the backing file and the instantiating the in-memory inode.

i.e. instead of:

cfs_lookup()
        cfs_dir_lookup(&index) cfs_get_ino_index(index, &inode_s) cfs_get_inode_data_max(index, &data) inode_s->st_.... = cfs_read_....(&data); inode_s->st_.... = cfs_read_....(&data); inode_s->st_.... = cfs_read_....(&data); inode_s->st_.... = cfs_read_....(&data); cfs_make_inode(inode_s, &vfs_inode) inode = new_inode(sb) inode->i_... = inode_s->st_....; inode->i_... = inode_s->st_....; inode->i_... = inode_s->st_....; inode->i_... = inode_s->st_....;

You could collapse this straight down to:

cfs_lookup()
        cfs_dir_lookup(&index) cfs_make_inode(index, &vfs_inode) inode = new_inode(sb) cfs_get_inode_data_max(index, &data) inode->i_... = cfs_read_....(&data); inode->i_... = cfs_read_....(&data); inode->i_... = cfs_read_....(&data); inode->i_... = cfs_read_....(&data);

This removes an intermediately layer from the inode instantiation fast path completely. ANd if the inode table is fixed size and always well aligned, then the cfs_make_inode() code that sets up the VFS inode is almost unchanged from what it is now. There are no new branches, the file image format is greatly simplified, and the runtime overhead of instantiating inodes is significantly reduced.

Similar things can be done with the rest of the "descriptor" abstraction - the intermediate in-memory structures can be placed directly in the cfs_inode structure that wraps the VFS inode, and the initialisation of them can call the decoding code directly instead of using intermediate structures as is currently done.

This will remove a chunk of code from the implemenation and make it run faster....

Quoted 3 lines

Also, we don't just "not decode" the items with the flag not set, they
are not even stored on disk.

Yup, and I think that is a mistake - premature optimisation and all that...

Quoted 29 lines

Quoted 18 lines

Quoted 10 lines

+       CFS_INODE_FLAGS_XATTRS = 1 << 9,
+       CFS_INODE_FLAGS_DIGEST = 1 << 10, /* fs-verity sha256 digest */
+       CFS_INODE_FLAGS_DIGEST_FROM_PAYLOAD = 1 << 11, /* Compute
digest from payload */

fs/composefs/cfs.h new file +3 -0

+};
+
+#define CFS_INODE_FLAG_CHECK(_flag,

Quoted 2 lines

_name)                                     \
+       (((_flag) & (CFS_INODE_FLAGS_##_name)) != 0)

Check what about a flag? If this is a "check that a feature is set",
then open coding it better, but if you must do it like this, then please use static inline functions like:

Quoted 4 lines

        if (cfs_inode_has_xattrs(inode->flags)) {
                .....
        }

The check is if the flag is set, so maybe CFS_INODE_FLAG_IS_SET is a
better name. This is used only when decoding the on-disk version of the
inode to the in memory one, which is a bunch of:

Quoted 8 lines

        if (CFS_INODE_FLAG_CHECK(ino->flags, THE_FIELD)) ino->the_field = cfs_read_u32(&data); else
                ino->the_field = THE_FIELD_DEFUALT;

I can easily open-code these checks, although I'm not sure it makes a
great difference either way.

If they are used only once, then it should be open coded. But I think the whole "optional inode fields" stuff should just go away entirely at this point...

Quoted 10 lines

Quoted 9 lines

fs/composefs/cfs.h line 117

Quoted 6 lines

fs/composefs/cfs.h new file +6 -0

+#define CFS_INODE_DEFAULT_MODE 0100644
+#define CFS_INODE_DEFAULT_NLINK 1
+#define CFS_INODE_DEFAULT_NLINK_DIR 2
+#define CFS_INODE_DEFAULT_UIDGID 0
+#define CFS_INODE_DEFAULT_RDEV 0
+#define CFS_INODE_DEFAULT_TIMES 0

Where do these get used? Are they on disk defaults or something else? (comment, please!)

Quoted 2 lines

They are the defaults that are used when inode fields on disk are missing. I'll add some comments.

They go away entirely with fixed size on-disk inodes.

Quoted 23 lines

Quoted 15 lines

Quoted 11 lines

+       u32 st_mode; /* File type and mode.  */
+       u32 st_nlink; /* Number of hard links, only for regular files.  */
+       u32 st_uid; /* User ID of owner.  */
+       u32 st_gid; /* Group ID of owner.  */
+       u32 st_rdev; /* Device ID (if special file).  */ +       u64 st_size; /* Size of file, only used for regular files
*/
+
+       struct cfs_vdata_s xattrs; /* ref to variable data */

This is in the payload that follows the inode?  Is it included in the payload_length above?

Quoted 7 lines

If not, where is this stuff located, how do we validate it points to
the correct place in the on-disk format file, the xattrs belong to
this specific inode, etc? I think that's kinda important to describe, because xattrs often contain important security information...

Quoted 6 lines

No, all inodes are packed into the initial part of the file, each containing a flags set, a variable size (from flags) chunk of fixed size elements and an variable size payload. The payload is either the
target symlink for symlinks, or the path of the backing file for regular files.

Ok, I think you need to stop calling that a "payload", then. It's the path name to the backing file. The backing file is only relevant for S_IFREG and S_IFLINK types - directories don't need path names as they only contain pointers to other inodes in the image file. Types like S_IFIFO, S_IFBLK, etc should not have backing files, either - they should just be instantiated as the correct type in the VFS inode and not require any backing file interactions at all...

Hence I think this "payload" should be called something like "backing path" or something similar.

.....

Quoted 11 lines

Quoted 10 lines

fs/composefs/cfs.h line 183

Quoted 4 lines

fs/composefs/cfs.h new file +4 -0

+struct cfs_dir_s {
+       u32 n_chunks;
+       struct cfs_dir_chunk_s chunks[];
+} __packed;

So directory data is packed in discrete chunks? Given that this is a
static directory format, and the size of the directory is known at
image creation time, why does the storage need to be chunked?

Quoted 5 lines

We chunk the data such that each chunk fits inside a single page in the
image file. I did this to make accessing image data directly from the
page cache easier.

Hmmmm. So you defined a -block size- that matched the x86-64 -page size- to avoid page cache issues.  Now, what about ARM or POWER which has 64kB page sizes?

IOWs, "page size" is not the same on all machines, whilst the on-disk format for a filesystem image needs to be the same on all machines. Hence it appears that this:

Quoted 1 line

Quoted 1 line

Quoted 1 line

+#define CFS_MAX_DIR_CHUNK_SIZE 4096

should actually be defined in terms of the block size for the filesystem image, and this size of these dir chunks should be recorded in the superblock of the filesystem image. That way it is clear that the image has a specific chunk size, and it also paves the way for supporting more efficient directory structures using larger-than-page size chunks in future.

Quoted 6 lines

If we had dirent data spanning multiple pages
then we would either need to map the pages consecutively (which seems
hard/costly) or have complex in-kernel code to handle the case where a
dirent straddles two pages.

Actually pretty easy - we do this with XFS for multi-page directory buffers. We just use vm_map_ram() on a page array at the moment, but in the near future there will be other options based on multipage folios.

That is, the page cache now stores folios rather than pages, and is capable of using contiguous multi-page folios in the cache. As a result, multipage folios could be used to cache multi-page structures in the page cache and efficiently map them as a whole.

That mapping code isn't there yet - kmap_local_folio() only maps the page within the folio at the offset given - but the foundation is there for supporting this functionality natively....

I certainly wouldn't be designing a new filesystem these days that has it's on-disk format constrained by the x86-64 4kB page size...

Quoted 31 lines · Dave Chinner

Quoted 29 lines · Alexander Larsson

Quoted 23 lines · Dave Chinner

fs/composefs/cfs.h line 82

Quoted 6 lines · Alexander Larsson

fs/composefs/cfs.h new file +6 -0

+} __packed;
+
+struct cfs_header_s {
+       u8 version;
+       u8 unused1;
+       u16 unused2;

Why are you hyper-optimising these structures for minimal space usage? This is 2023 - we can use a __le32 for the version number, the magic number and then leave....

fs/composefs/cfs.h line 88

Quoted 6 lines

fs/composefs/cfs.h new file +6 -0

+
+       u32 magic;
+       u64 data_offset;
+       u64 root_inode;
+
+       u64 unused3[2];

a whole heap of space to round it up to at least a CPU cacheline size using something like "__le64 unused[15]".

Quoted 3 lines

That way we don't need packed structures nor do we care about having
weird little holes in the structures to fill....

Sure.

Quoted 4 lines

FWIW, now I see how this is used, this header kinda defines what we'd call the superblock in the on-disk format of a filesystem. It's at a fixed location in the image file, so there should be a #define somewhere in this file to document it's fixed location.

It is at offset zero. I don't really think that needs a define, does it? Maybe a comment though.

Quoted 3 lines

Also, if this is the in-memory representation of the structure and not the actual on-disk format, why does it even need padding, packing or even store the magic number?

In this case it is the on-disk format though.

Quoted 27 lines

Quoted 21 lines

Quoted 11 lines

Quoted 11 lines

fs/composefs/cfs.h new file +11 -0

+} __packed;
+
+enum cfs_inode_flags {
+       CFS_INODE_FLAGS_NONE = 0,
+       CFS_INODE_FLAGS_PAYLOAD = 1 << 0,
+       CFS_INODE_FLAGS_MODE = 1 << 1,
+       CFS_INODE_FLAGS_NLINK = 1 << 2,
+       CFS_INODE_FLAGS_UIDGID = 1 << 3,
+       CFS_INODE_FLAGS_RDEV = 1 << 4,
+       CFS_INODE_FLAGS_TIMES = 1 << 5,
+       CFS_INODE_FLAGS_TIMES_NSEC = 1 << 6,

Quoted 9 lines

Quoted 5 lines

+       CFS_INODE_FLAGS_LOW_SIZE = 1 << 7, /* Low 32bit of st_size
*/
+       CFS_INODE_FLAGS_HIGH_SIZE = 1 << 8, /* High 32bit of st_size */

Why do we need to complicate things by splitting the inode size like this?

Quoted 2 lines

The goal is to minimize the image size for a typical rootfs or container image. Almost zero files in any such images are > 4GB.

Sure, but how much space does this typically save, versus how much complexity it adds to runtime decoding of inodes?

Quoted 8 lines

I mean, in a dense container system the critical resources that need to be saved is runtime memory and CPU overhead of operations, not the storage space. Saving a 30-40 bytes of storage space per inode means a typical image might ber a few MB smaller, but given the image file is not storing data we're only talking about images the use maybe 500 bytes of data per inode. Storage space for images is not a limiting factor, nor is network transmission (because compression), so it comes back to runtime CPU and memory usage.

Here are some example sizes of composefs images with the current packed inodes:

6.2M cs9-developer-rootfs.composefs
2.1M cs9-minimal-rootfs.composefs
1.2M fedora-37-container.composefs
433K ubuntu-22.04-container.composefs

If we set all the flags for the inodes (i.e. fixed size inodes) we get:

8.8M cs9-developer-rootfs.composefs
3.0M cs9-minimal-rootfs.composefs
1.6M fedora-37-container.composefs
625K ubuntu-22.04-container.composefs

So, images are about 40% larger with fixed size inodes.

Quoted 6 lines

The inodes are decoded out of the page cache, so the memory for the raw inode information is volatile and reclaimed when needed. Similarly, the VFS inode built from this information is reclaimable when not in use, too. So the only real overhead for runtime is the decoding time to find the inode in the image file and then decode it.

I disagree with this characterization. It is true that page cache is volatile, but if you can fit 40% less inode data in the page cache then there is additional overhead where you need to read this from disk. So, decoding time is not the only thing that affects overhead.

Additionally, just by being larger and less dense, more data has to be read from disk, which itself is slower.

Quoted 6 lines

Given the decoding of the inode -all branches- and is not straight-line code, it cannot be well optimised and the CPU branch predictor is not going to get it right every time. Straight line code that decodes every field whether it is zero or not is going to be faster.

Quoted 7 lines

Further, with a fixed size inode in the image file, the inode table can be entirely fixed size, getting rid of the whole unaligned data retreival problem that code currently has (yes, all that "le32_to_cpu(__get_unaligned(__le32, data)" code) because we can ensure that all the inode fields are aligned in the data pages. This will significantly speed up decoding into the in-memory inode structures.

I agree it could be faster. But is inode decode actually the limiting factor, compared to things like disk i/o or better use of page cache?

Quoted 25 lines

Quoted 11 lines

Quoted 10 lines

fs/composefs/cfs.h line 183

Quoted 4 lines

fs/composefs/cfs.h new file +4 -0

+struct cfs_dir_s {
+       u32 n_chunks;
+       struct cfs_dir_chunk_s chunks[];
+} __packed;

So directory data is packed in discrete chunks? Given that this is a
static directory format, and the size of the directory is known at
image creation time, why does the storage need to be chunked?

Quoted 5 lines

We chunk the data such that each chunk fits inside a single page in the
image file. I did this to make accessing image data directly from the
page cache easier.

Hmmmm. So you defined a -block size- that matched the x86-64 -page size- to avoid page cache issues.  Now, what about ARM or POWER which has 64kB page sizes?

IOWs, "page size" is not the same on all machines, whilst the on-disk format for a filesystem image needs to be the same on all machines. Hence it appears that this:

Quoted 8 lines

Quoted 1 line

Quoted 1 line

Quoted 1 line

+#define CFS_MAX_DIR_CHUNK_SIZE 4096

should actually be defined in terms of the block size for the filesystem image, and this size of these dir chunks should be recorded in the superblock of the filesystem image. That way it is clear that the image has a specific chunk size, and it also paves the way for supporting more efficient directory structures using larger-than-page size chunks in future.

Yes, its true that assuming a (min) 4k page size is wasteful on some arches, but it would be hard to read a filesystem created for 64k pages on a 4k page machine, which is not ideal. However, wrt your commend on multi-page mappings, maybe we can just totally drop these limits. I'll have a look at that.

Quoted 22 lines

Quoted 7 lines

If we had dirent data spanning multiple pages
then we would either need to map the pages consecutively (which seems
hard/costly) or have complex in-kernel code to handle the case where a
dirent straddles two pages.

Actually pretty easy - we do this with XFS for multi-page directory buffers. We just use vm_map_ram() on a page array at the moment, but in the near future there will be other options based on multipage folios.

That is, the page cache now stores folios rather than pages, and is capable of using contiguous multi-page folios in the cache. As a result, multipage folios could be used to cache multi-page structures in the page cache and efficiently map them as a whole.

That mapping code isn't there yet - kmap_local_folio() only maps the page within the folio at the offset given - but the foundation is there for supporting this functionality natively....

Quoted 2 lines

I certainly wouldn't be designing a new filesystem these days that has it's on-disk format constrained by the x86-64 4kB page size...

Yes, I agree. I'm gonna look at using multi-page mapping for both dirents and xattr data, which should completely drop these limits, as well as get rid of the dirent chunking.

fs/composefs/cfs.c new file +46 -0

+	res = cfs_init_inode_data(ctx, ino, ino_num, &inode_data);
+	if (res < 0)
+		return ERR_PTR(res);
+
+	inode = new_inode(sb);
+	if (inode) {
+		inode_init_owner(&init_user_ns, inode, dir, ino->st_mode);
+		inode->i_mapping->a_ops = &cfs_aops;
+
+		cino = CFS_I(inode);
+		cino->inode_data = inode_data;
+
+		inode->i_ino = ino_num;
+		set_nlink(inode, ino->st_nlink);
+		inode->i_rdev = ino->st_rdev;
+		inode->i_uid = make_kuid(current_user_ns(), ino->st_uid);
+		inode->i_gid = make_kgid(current_user_ns(), ino->st_gid);
+		inode->i_mode = ino->st_mode;
+		inode->i_atime = ino->st_mtim;
+		inode->i_mtime = ino->st_mtim;
+		inode->i_ctime = ino->st_ctim;
+
+		switch (ino->st_mode & S_IFMT) {
+		case S_IFREG:
+			inode->i_op = &cfs_file_inode_operations;
+			inode->i_fop = &cfs_file_operations;
+			inode->i_size = ino->st_size;
+			break;
+		case S_IFLNK:
+			inode->i_link = cino->inode_data.path_payload;
+			inode->i_op = &cfs_link_inode_operations;
+			inode->i_fop = &cfs_file_operations;
+			break;
+		case S_IFDIR:
+			inode->i_op = &cfs_dir_inode_operations;
+			inode->i_fop = &cfs_dir_operations;
+			inode->i_size = 4096;
+			break;
+		case S_IFCHR:
+		case S_IFBLK:
+			if (current_user_ns() != &init_user_ns) {
+				ret = -EPERM;
+				goto fail;
+			}
+			fallthrough;
+		default:

fs/composefs/cfs.c new file +5 -0

+	kfree(xattrs);
+	cfs_inode_data_put(&inode_data);
+	return ERR_PTR(ret);
+}
+

fs/composefs/cfs.c new file +27 -0

+	return cfs_make_inode(&fsi->cfs_ctx, sb, index, ino, NULL);
+}
 
+static struct dentry *cfs_lookup(struct inode *dir, struct dentry *dentry,
+				 unsigned int flags)
+{
+	struct cfs_info *fsi = dir->i_sb->s_fs_info;
+	struct cfs_inode *cino = CFS_I(dir);
+	struct cfs_inode_s ino_buf;
+	struct cfs_inode_s *ino_s;
+	struct inode *inode;
+	u64 index;
+	int ret;
+
+	if (dentry->d_name.len > NAME_MAX)
+		return ERR_PTR(-ENAMETOOLONG);
+
+	ret = cfs_dir_lookup(&fsi->cfs_ctx, dir->i_ino, &cino->inode_data,
+			     dentry->d_name.name, dentry->d_name.len, &index);
+	if (ret < 0)
+		return ERR_PTR(ret);
+	if (ret == 0)
+		goto return_negative;
+
+	ino_s = cfs_get_ino_index(&fsi->cfs_ctx, index, &ino_buf);
+	if (IS_ERR(ino_s))
+		return ERR_CAST(ino_s);
+

fs/composefs/cfs.c new file +12 -0

+static void cfs_put_super(struct super_block *sb)
+{
+	struct cfs_info *fsi = sb->s_fs_info;
+
+	cfs_ctx_put(&fsi->cfs_ctx);
+	if (fsi->bases) {
+		kern_unmount_array(fsi->bases, fsi->n_bases);
+		kfree(fsi->bases);
+	}
+	kfree(fsi->base_path);
+
+	kfree(fsi);

fs/composefs/cfs.c new file +13 -0

+
+	/* Don't inherit atime flags */
+	mnt->mnt_flags &= ~(MNT_NOATIME | MNT_NODIRATIME | MNT_RELATIME);
+
+	return mnt;
+
+out_put:
+	path_put(&path);
+out:
+	return ERR_PTR(err);
+}
 
+
+static int cfs_fill_super(struct super_block *sb, struct fs_context *fc)

        Several random observations:

Adds documentation about the composefs filesystem and how to use it.

Documentation/filesystems/composefs.rst new file +55 -0

new file mode 100644
index 000000000000..306f0e2e22ba
@@ -0,0 +1,169 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Composefs Filesystem
+====================
+
+Introduction
+============
+
+Composefs is a read-only file system that is backed by regular files
+(rather than a block device). It is designed to help easily share
+content between different directory trees, such as container images in
+a local store or ostree checkouts. In addition it also has support for
+integrity validation of file content and directory metadata, in an
+efficient way (using fs-verity).
+
+The filesystem mount source is a binary blob called the descriptor. It
+contains all the inode and directory entry data for the entire
+filesystem. However, instead of storing the file content each regular
+file inode stores a relative path name, and the filesystem gets the
+file content from the filesystem by looking up that filename in a set
+of base directories.
+
+Given such a descriptor called "image.cfs" and a directory with files
+called "/dir" you can mount it like::
+
+  mount -t composefs image.cfs -o basedir=/dir /mnt
+
+Content sharing
+===============
+
+Suppose you have a single basedir where the files are content
+addressed (i.e. named by content digest), and a set of composefs
+descriptors using this basedir. Any file that happen to be shared
+between two images (same content, so same digest) will now only be
+stored once on the disk.
+
+Such sharing is possible even if the metadata for the file in the
+image differs (common reasons for metadata difference are mtime,
+permissions, xattrs, etc). The sharing is also anonymous in the sense
+that you can't tell the difference on the mounted files from a
+non-shared file (for example by looking at the link count for a
+hardlinked file).
+
+In addition, any shared files that are actively in use will share
+page-cache, because the page cache for the file contents will be
+addressed by the backing file in the basedir, This means (for example)
+that shared libraries between images will only be mmap:ed once across
+all mounts.
+
+Integrity validation
+====================
+
+Composefs uses :doc:`fs-verity <fsverity>` for integrity validation,
+and extends it by making the validation also apply to the directory

Documentation/filesystems/composefs.rst new file +46 -0

+
+For file validation, the descriptor can contain digest for each
+backing file, and you can enable fs-verity on the backing
+files. Composefs will validate the digest before using the backing
+files. This means any (accidental or malicious) modification of the
+basedir will be detected at the time the file is used.
+
+Expected use-cases
+==================
+
+Container Image Storage
+```````````````````````
+
+Typically a container image is stored as a set of "layer"
+directories. merged into one mount by using overlayfs.  The lower
+layers are read-only image content and the upper layer is the
+writable state of a running container. Multiple uses of the same
+layer can be shared this way, but it is hard to share individual
+files between unrelated layers.
+
+Using composefs, we can instead use a shared, content-addressed
+store for all the images in the system, and use a composefs image
+for the read-only image content of each image, pointing into the
+shared store. Then for a running container we use an overlayfs
+with the lower dir being the composefs and the upper dir being
+the writable state.
+
+
+Ostree root filesystem validation
+`````````````````````````````````
+
+Ostree uses a content-addressed on-disk store for file content,
+allowing efficient updates and sharing of content. However to actually
+use these as a root filesystem it needs to create a real
+"chroot-style" directory, containing hard links into the store. The
+store itself is validated when created, but once the hard-link
+directory is created, nothing validates the directory structure of
+that.
+
+Instead of a chroot we can we can use composefs. We create a composefs
+image pointing into the object store, enable fs-verity for everything
+and encode the fs-verity digest of the descriptor in the
+kernel-command line. This will allow booting a trusted system where
+all directory metadata and file content is validated lazily at use.
+
+

Documentation/filesystems/composefs.rst new file +38 -0

+
+digest
+    A fs-verity sha256 digest that the descriptor file must match. If set,
+    `verity_check` defaults to 2.
+
+
+Filesystem format
+=================
+
+The format of the descriptor is contains three sections: header,
+inodes and variable data. All data in the file is stored in
+little-endian form.
+
+The header starts at the beginning of the file and contains version,
+magic value, offsets to the variable data and the root inode nr.
+
+The inode section starts at a fixed location right after the
+header. It is a array of inode data, where for each inode there is
+first a variable length chunk and then a fixed size chunk. An inode nr
+is the offset in the inode data to the start of the fixed chunk.
+
+The fixed inode chunk starts with a flag that tells what parts of the
+inode are stored in the file (meaning it is only the maximal size that
+is fixed). After that the various inode attributes are serialized in
+order, such as mode, ownership, xattrs, and payload length. The
+payload length attribute gives the size of the variable chunk.
+
+The inode variable chunk contains different things depending on the
+file type.  For regular files it is the backing filename. For symlinks
+it is the symlink target. For directories it is a list of references to
+dentries, stored in chunks of maximum 4k. The dentry chunks themselves
+are stored in the variable data section.
+
+The variable data section is stored after the inode section, and you
+can find it from the offset in the header. It contains dentries and
+Xattrs data. The xattrs are referred to by offset and size in the
+xattr attribute in the inode data. Each xattr data can be used by many
+inodes in the filesystem. The variable data chunks are all smaller than

Quoted 2 lines · Alexander Larsson

Adds documentation about the composefs filesystem and how to use it.

s/Adds documentation/Add documentation/

Giuseppe Scrivano and I have recently been working on a new project we call composefs. This is the first time we propose this publically and we would like some feedback on it.

At its core, composefs is a way to construct and use read only images that are used similar to how you would use e.g. loop-back mounted squashfs images. On top of this composefs has two fundamental features. First it allows sharing of file data (both on disk and in page cache) between images, and secondly it has dm-verity like validation on read.

Let me first start with a minimal example of how this can be used, before going into the details:

Suppose we have this source for an image:

rootfs/

├── dir
│   └── another_a
├── file_a
└── file_b

We can then use this to generate an image file and a set of content-addressed backing files:

# mkcomposefs --digest-store=objects rootfs/ rootfs.img
# ls -l rootfs.img objects/*/*

(quoted diff) +0 -3

-rw-------. 1 root root   10 Nov 18 13:20 objects/02/927862b4ab9fb69919187bb78d394e235ce444eeb0a890d37e955827fe4bf4
-rw-------. 1 root root   10 Nov 18 13:20 objects/cc/3da5b14909626fc99443f580e4d8c9b990e85e0a1d18883dc89b23d43e173f
-rw-r--r--. 1 root root 4228 Nov 18 13:20 rootfs.img

The rootfs.img file contains all information about directory and file metadata plus references to the backing files by name. We can now mount this and look at the result:

# mount -t composefs rootfs.img -o basedir=objects /mnt
# ls  /mnt/
dir  file_a  file_b
# cat /mnt/file_a
content_a

When reading this file the kernel is actually reading the backing file, in a fashion similar to overlayfs. Since the backing file is content-addressed, the objects directory can be shared for multiple images, and any files that happen to have the same content are shared. I refer to this as opportunistic sharing, as it is different than the more course-grained explicit sharing used by e.g. container base images.