Skip to contentSkip to conversation

Initial patches for Incremental FS

PATCH In review [email protected] 12 participants 33 messages May 2, 2019 – May 31, 2019 1 message not in the archive

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

Hi All,

Please take a look at Incremental FS.

Incremental FS is special-purpose Linux virtual file system that allows execution of a program while its binary and resource files are still being lazily downloaded over the network, USB etc. It is focused on incremental delivery for a small number (under 100) of big files (more than 10 megabytes each). Incremental FS doesn’t allow direct writes into files and, once loaded, file content never changes. Incremental FS doesn’t use a block device, instead it saves data into a backing file located on a regular file-system.

What’s it for?

It allows running big Android apps before their binaries and resources are fully loaded to an Android device. If an app reads something not loaded yet, it needs to wait for the data block to be fetched, but in most cases hot blocks can be loaded in advance and apps can run smoothly and almost instantly.

More details can be found in Documentation/filesystems/incremental.fs

Coming up next:
[PATCH 1/6] incfs: Add first files of incrementalfs [PATCH 2/6] incfs: Backing file format
[PATCH 3/6] incfs: Management of in-memory FS data structures [PATCH 4/6] incfs: Integration with VFS layer [PATCH 5/6] incfs: sample data loader for incremental-fs [PATCH 6/6] incfs: Integration tests for incremental-fs

Thanks,
Eugene.

#1 lore raw

PATCH 1/6 incfs: Add first files of incrementalfs

From: Eugene Zemtsov <[email protected]>

- fs/incfs dir
- Kconfig (CONFIG_INCREMENTAL_FS)
- Makefile
- Module and file system initialization and clean up code
- New MAINTAINERS entry
- Add incrementalfs.h UAPI header
- Register ioctl range in ioctl-numbers.txt
- Documentation

---
 Documentation/filesystems/incrementalfs.rst | 452 ++++++++++++++++++++
 Documentation/ioctl/ioctl-number.txt        |   1 +
 MAINTAINERS                                 |   7 +
 fs/Kconfig                                  |   1 +
 fs/Makefile                                 |   1 +
 fs/incfs/Kconfig                            |  10 +
 fs/incfs/Makefile                           |   4 +
 fs/incfs/main.c                             |  85 ++++
 fs/incfs/vfs.c                              |  37 ++
 include/uapi/linux/incrementalfs.h          | 189 ++++++++
 10 files changed, 787 insertions(+)
 create mode 100644 Documentation/filesystems/incrementalfs.rst
 create mode 100644 fs/incfs/Kconfig
 create mode 100644 fs/incfs/Makefile
 create mode 100644 fs/incfs/main.c
 create mode 100644 fs/incfs/vfs.c
 create mode 100644 include/uapi/linux/incrementalfs.h
Documentation/filesystems/incrementalfs.rst new file +452 -0
new file mode 100644
index 000000000000..682e3dcb6b5a
@@ -0,0 +1,452 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+=======================
+Incremental File System
+=======================
+
+Overview
+========
+Incremental FS is special-purpose Linux virtual file system that allows
+execution of a program while its binary and resource files are still being
+lazily downloaded over the network, USB etc. It is focused on incremental
+delivery for a small number (under 100) of big files (more than 10 megabytes).
+Incremental FS doesn’t allow direct writes into files and, once loaded, file
+content never changes. Incremental FS doesn’t use a block device, instead it
+saves data into a backing file located on a regular file-system.
+
+But why?
+--------
+To allow running **big** Android apps before their binaries and resources are
+fully downloaded to an Android device. If an app reads something not loaded yet,
+it needs to wait for the data block to be fetched, but in most cases hot blocks
+can be loaded in advance.
+
+Workflow
+--------
+A userspace process, called a data loader, mounts an instance of incremental-fs
+giving it a file descriptor on an underlying file system (like ext4 or f2fs).
+Incremental-fs reads content (if any) of this backing file and interprets it as
+a file system image with files, directories and data blocks. At this point
+the data loader can declare new files to be shown by incremental-fs.
+
+A process is started from a binary located on incremental-fs.
+All reads are served directly from the backing file
+without roundtrips into userspace. If the process accesses a data block that was
+not originally present in the backing file, the read operation waits.
+
+Meanwhile the data loader can feed new data blocks to incremental-fs by calling
+write() on a special .cmd pseudo-file. The data loader can request information
+about pending reads by calling poll() and read() on the .cmd pseudo-file.
+This mechanism allows the data loader to serve most urgently needed data first.
+Once a data block is given to incremental-fs, it saves it to the backing file
+and unblocks all the reads waiting for this block.
+
+Eventually all data for all files is uploaded by the data loader, and saved by
+incremental-fs into the backing file. At that moment the data loader is not
+needed any longer. The backing file will play the role of a complete
+filesystem image for all future runs of the program.
+
+Non-goals
+---------
+* Allowing direct writes by the executing processes into files on incremental-fs
+* Allowing the data loader change file size or content after it was loaded.
+* Having more than a couple hundred files and directories.
+
+
+Features
+========
+
+Read-only, but not unchanging
+-----------------------------
+On the surface a mount directory of incremental-fs would look similar to
+a read-only instance of network file system: files and directories can be
+listed and read, but can’t be directly created or modified via creat() or
+write(). At the same time the data loader can make changes to a directory
+structure via external ioctl-s. i.e. link and unlink files and directories
+(if they empty). Data can't be changed this way, once a file block is loaded
+there is no way to change it.
+
+Filesystem image in a backing file
+----------------------------------
+Instead of using a block device, all data and metadata is stored in a
+backing file provided as a mount parameter. The backing file is located on
+an underlying file system (like ext4 or f2fs). Such approach is very similar
+to what might be achieved by using loopback device with a traditional file
+system, but it avoids extra set-up steps and indirections. It also allows
+incremental-fs image to dynamically grow as new files and data come without
+having to do any extra steps for resizing.
+
+If the backing file contains data at the moment when incremental-fs is mounted,
+content of the backing file is being interpreted as filesystem image.
+New files and data can still be added through the external interface,
+and they will be saved to the backing file.
+
+Data compression
+----------------
+Incremental-fs can store compressed data. In this case each 4KB data block is
+compressed separately. Data blocks can be provided to incremental-fs by
+the data loader in a compressed form. Incremental-fs uncompresses blocks
+each time a executing process reads it (modulo page cache). Compression also
+takes care of blocks composed of all zero bytes removing necessity to handle
+this case separately.
+
+Partially present files
+-----------------------
+Data in the files consists of 4KB blocks, each block can be present or absent.
+Unlike in sparse files, reading an absent block doesn’t return all zeros.
+It waits for the data block to be loaded via the ioctl interface
+(respecting a timeout). Once a data block is loaded it never disappears
+and can’t be changed or erased from a file. This ability to frictionlessly
+wait for temporary missing data is the main feature of incremental-fs.
+
+Hard links. Multiple names for the same file
+--------------------------------------------
+Like all traditional UNIX file systems, incremental-fs supports hard links,
+i.e. different file names in different directories can refer to the same file.
+As mentioned above new hard links can be created and removed via
+the ioctl interface, but actual data files are immutable, modulo partial
+data loading. Each directory can only have at most one name referencing it.
+
+Inspection of incremental-fs internal state
+-------------------------------------------
+poll() and read() on the .cmd pseudo-file allow data loaders to get a list of
+read operations stalled due to lack of a data block (pending reads).
+
+
+Application Programming Interface
+=================================
+
+Regular file system interface
+-----------------------------
+Executing process access files and directories via regular Linux file interface:
+open, read, close etc. All the intricacies of data loading a file representation
+are hidden from them.
+
+External .cmd file interface
+----------------------------
+When incremental-fs is mounted, a mount directory contains a pseudo-file
+called '.cmd'. The data loader will open this file and call read(), write(),
+poll() and ioctl() on it inspect and change state of incremental-fs.
+
+poll() and read() are used by the data loader to wait for pending reads to
+appear and obtain an array of ``struct incfs_pending_read_info``.
+
+write() is used by the data loader to feed new data blocks to incremental-fs.
+A data buffer given to write() is interpreted as an array of
+``struct incfs_new_data_block``. Structs in the array describe locations and
+properties of data blocks loaded with this write() call.
+
+``ioctl(INCFS_IOC_PROCESS_INSTRUCTION)`` is used to change structure of
+incremental-fs. It receives an pointer to ``struct incfs_instruction``
+where type field can have be one of the following values.
+
+**INCFS_INSTRUCTION_NEW_FILE**
+Creates an inode (a file or a directory) without a name.
+It assumes ``incfs_new_file_instruction.file`` is populated with details.
+
+**INCFS_INSTRUCTION_ADD_DIR_ENTRY**
+Creates a name (aka hardlink) for an inode in a directory.
+A directory can't have more than one hardlink pointing to it, but files can be
+linked from different directories.
+It assumes ``incfs_new_file_instruction.dir_entry`` is populated with details.
+
+**INCFS_INSTRUCTION_REMOVE_DIR_ENTRY**
+Remove a name (aka hardlink) for a file from a directory.
+Only empty directories can be unlinked.
+It assumes ``incfs_new_file_instruction.dir_entry`` is populated with details.
+
+For more details see in uapi/linux/incrementalfs.h and samples below.
+
+Supported mount options
+-----------------------
+See ``fs/incfs/options.c`` for more details.
+
+    * ``backing_fd=<unsigned int>``
+        Required. A file descriptor of a backing file opened by the process
+        calling mount(2). This descriptor can be closed after mount returns.
+
+    * ``read_timeout_msc=<unsigned int>``
+        Default: 1000. Timeout in milliseconds before a read operation fails
+        if no data found in the backing file or provided by the data loader.
+
+Sysfs files
+-----------
+``/sys/fs/incremental-fs/version`` - a current version of the filesystem.
+One ASCII encoded positive integer number with a new line at the end.
+
+
+Examples
+--------
+See ``sample_data_loader.c`` for a complete implementation of a data loader.
+
+Mount incremental-fs
+~~~~~~~~~~~~~~~~~~~~
+
+::
+
+    int mount_fs(char *mount_dir, char *backing_file, int timeout_msc)
+    {
+        static const char fs_name[] = INCFS_NAME;
+        char mount_options[512];
+        int backing_fd;
+        int result;
+
+        backing_fd = open(backing_file, O_RDWR);
+        if (backing_fd == -1) {
+            perror("Error in opening backing file");
+            return 1;
+        }
+
+        snprintf(mount_options, ARRAY_SIZE(mount_options),
+            "backing_fd=%u,read_timeout_msc=%u", backing_fd, timeout_msc);
+
+        result = mount(fs_name, mount_dir, fs_name, 0, mount_options);
+        if (result != 0)
+            perror("Error mounting fs.");
+        return result;
+    }
+
+Open .cmd file
+~~~~~~~~~~~~~~
+
+::
+
+    int open_commands_file(char *mount_dir)
+    {
+        char cmd_file[255];
+        int cmd_fd;
+
+        snprintf(cmd_file, ARRAY_SIZE(cmd_file), "%s/.cmd", mount_dir);
+        cmd_fd = open(cmd_file, O_RDWR);
+        if (cmd_fd < 0)
+            perror("Can't open commands file");
+        return cmd_fd;
+    }
+
+Add a file to the file system
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+::
+
+    int create_file(int cmd_fd, char *filename, int *ino_out, size_t size)
+    {
+        int ret = 0;
+        __u16 ino = 0;
+        struct incfs_instruction inst = {
+                .version = INCFS_HEADER_VER,
+                .type = INCFS_INSTRUCTION_NEW_FILE,
+                .file = {
+                    .size = size,
+                    .mode = S_IFREG | 0555,
+                }
+        };
+
+        ret = ioctl(cmd_fd, INCFS_IOC_PROCESS_INSTRUCTION, &inst);
+        if (ret)
+            return -errno;
+
+        ino = inst.file.ino_out;
+        inst = (struct incfs_instruction){
+                .version = INCFS_HEADER_VER,
+                .type = INCFS_INSTRUCTION_ADD_DIR_ENTRY,
+                .dir_entry = {
+                    .dir_ino = INCFS_ROOT_INODE,
+                    .child_ino = ino,
+                    .name = ptr_to_u64(filename),
+                    .name_len = strlen(filename)
+                }
+            };
+        ret = ioctl(cmd_fd, INCFS_IOC_PROCESS_INSTRUCTION, &inst);
+        if (ret)
+            return -errno;
+        *ino_out = ino;
+        return 0;
+    }
+
+Load data into a file
+~~~~~~~~~~~~~~~~~~~~~
+
+::
+
+    int cmd_fd = open_commands_file(path_to_mount_dir);
+    char *data = get_some_data();
+    struct incfs_new_data_block block;
+    int err;
+
+    block.file_ino = file_ino;
+    block.block_index = 0;
+    block.compression = COMPRESSION_NONE;
+    block.data = (__u64)data;
+    block.data_len = INCFS_DATA_FILE_BLOCK_SIZE;
+
+    err = write(cmd_fd, &block, sizeof(block));
+
+
+Get an array of pending reads
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+::
+
+    int poll_res = 0;
+    struct incfs_pending_read_info reads[10];
+    int cmd_fd = open_commands_file(path_to_mount_dir);
+    struct pollfd pollfd = {
+        .fd = cmd_fd,
+        .events = POLLIN
+    };
+
+    poll_res = poll(&pollfd, 1, timeout);
+    if (poll_res > 0 && (pollfd.revents | POLLIN)) {
+        ssize_t read_res = read(cmd_fd, reads, sizeof(reads));
+        if (read_res > 0)
+            printf("Waiting reads %ld\n", read_res / sizeof(reads[0]));
+    }
+
+
+
+Ondisk format
+=============
+
+General principles
+------------------
+* The backbone of the incremental-fs ondisk format is an append only linked
+  list of metadata blocks. Each metadata block contains an offset of the next
+  one. These blocks describe files and directories on the
+  file system. They also represent actions of adding and removing file names
+  (hard links).
+  Every time incremental-fs instance is mounted, it reads through this list
+  to recreate filesystem's state in memory. An offset of the first record in the
+  metadata list is stored in the superblock at the beginning of the backing
+  file.
+
+* Most of the backing file is taken by data areas and blockmaps.
+  Since data blocks can be compressed and have different sizes,
+  single per-file data area can't be pre-allocated. That's why blockmaps are
+  needed in order to find a location and size of each data block in
+  the backing file. Each time a file is created, a corresponding block map is
+  allocated to store future offsets of data blocks.
+
+  Whenever a data block is given by data loader to incremental-fs:
+    - A data area with the given block is appended to the end of
+      the backing file.
+    - A record in the blockmap for the given block index is updated to reflect
+      its location, size, and compression algorithm.
+
+Important format details
+------------------------
+Ondisk structures are defined in the ``format.h`` file. They are all packed
+and use little-endian order.
+A backing file must start with ``incfs_super_block`` with ``s_magic`` field
+equal to 0x5346434e49 "INCFS".
+
+Metadata records:
+
+* ``incfs_inode`` - metadata record to declare a file or a directory.
+                    ``incfs_inode.i_mode`` determents if it is a file
+                    or a directory.
+* ``incfs_blockmap_entry`` - metadata record that specifies size and location
+                            of a blockmap area for a given file. This area
+                            contains an array of ``incfs_blockmap_entry``-s.
+* ``incfs_dir_action`` - metadata record that specifies changes made to a
+                    to a directory structure, e.g. add or remove a hardlink.
+* ``incfs_md_header`` - header of a metadata record. It's always a part
+                    of other structures and served purpose of metadata
+                    bookkeeping.
+
+Other ondisk structures:
+
+* ``incfs_super_block`` - backing file header
+* ``incfs_blockmap_entry`` - a record in a blockmap area that describes size
+                        and location of a data block.
+* Data blocks dont have any particular structure, they are written to the backing
+  file in a raw form as they come from a data loader.
+
+
+Backing file layout
+-------------------
+::
+
+              +-------------------------------------------+
+              |            incfs_super_block              |]---+
+              +-------------------------------------------+    |
+              |                 metadata                  |<---+
+              |                incfs_inode                |]---+
+              +-------------------------------------------+    |
+                        .........................              |
+              +-------------------------------------------+    |   metadata
+     +------->|               blockmap area               |    |  list links
+     |        |          [incfs_blockmap_entry]           |    |
+     |        |          [incfs_blockmap_entry]           |    |
+     |        |          [incfs_blockmap_entry]           |    |
+     |    +--[|          [incfs_blockmap_entry]           |    |
+     |    |   |          [incfs_blockmap_entry]           |    |
+     |    |   |          [incfs_blockmap_entry]           |    |
+     |    |   +-------------------------------------------+    |
+     |    |             .........................              |
+     |    |   +-------------------------------------------+    |
+     |    |   |                 metadata                  |<---+
+     +----|--[|               incfs_blockmap              |]---+
+          |   +-------------------------------------------+    |
+          |             .........................              |
+          |   +-------------------------------------------+    |
+          +-->|                 data block                |    |
+              +-------------------------------------------+    |
+                        .........................              |
+              +-------------------------------------------+    |
+              |                 metadata                  |<---+
+              |             incfs_dir_action              |
+              +-------------------------------------------+
+
+Unreferenced files and absence of garbage collection
+----------------------------------------------------
+Described file format can produce files that don't have any names for them in
+any directories. Incremental-fs takes no steps to prevent such situations or
+reclaim space occupied by such files in the backing file. If garbage collection
+is needed it has to be implemented as a separate userspace tool.
+
+
+Design alternatives
+===================
+
+Why isn't incremental-fs implemented via FUSE?
+----------------------------------------------
+TLDR: FUSE-based filesystems add 20-80% of performance overhead for target
+scenarios, and increase power use on mobile beyond acceptable limit
+for widespread deployment. A custom kernel filesystem is the way to overcome
+these limitations.
+
+From the theoretical side of things, FUSE filesystem adds some overhead to
+each filesystem operation that’s not handled by OS page cache:
+
+    * When an IO request arrives to FUSE driver (D), it puts it into a queue
+      that runs on a separate kernel thread
+    * Then another separate user-mode handler process (H) has to run,
+      potentially after a context switch, to read the request from the queue.
+      Reading the request adds a kernel-user mode transition to the handling.
+    * (H) sends the IO request to kernel to handle it on some underlying storage
+      filesystem. This adds a user-kernel and kernel-user mode transition
+      pair to the handling.
+    * (H) then responds to the FUSE request via a write(2) call.
+      Writing the response is another user-kernel mode transition.
+    * (D) needs to read the response from (H) when its kernel thread runs
+      and forward it to the user
+
+Together, the scenario adds 2 extra user-kernel-user mode transition pairs,
+and potentially has up to 3 additional context switches for the FUSE kernel
+thread and the user-mode handler to start running for each IO request on the
+filesystem.
+This overhead can vary from unnoticeable to unmanageable, depending on the
+target scenario. But it will always burn extra power via CPU staying longer
+in non-idle state, handling context switches and mode transitions.
+One important goal for the new filesystem is to be able to handle each page
+read separately on demand, because we don't want to wait and download more data
+than absolutely necessary. Thus readahead would need to be disabled completely.
+This increases the number of separate IO requests and the FUSE related overhead
+by almost 32x (128KB readahead limit vs 4KB individual block operations)
+
+For more info see a 2017 USENIX research paper:
+To FUSE or Not to FUSE: Performance of User-Space File Systems
+Bharath Kumar Reddy Vangoor, Stony Brook University;
+Vasily Tarasov, IBM Research-Almaden;
+Erez Zadok, Stony Brook University
+https://www.usenix.org/system/files/conference/fast17/fast17-vangoor.pdf
Documentation/ioctl/ioctl-number.txt +1 -0
index c9558146ac58..a5f8e0eaff91 100644
@@ -227,6 +227,7 @@ Code  Seq#(hex)	Include File		Comments
 'f'	00-0F	fs/ocfs2/ocfs2_fs.h	conflict!
 'g'	00-0F	linux/usb/gadgetfs.h
 'g'	20-2F	linux/usb/g_printer.h
+'g'	30-3F	include/uapi/linux/incrementalfs.h
 'h'	00-7F				conflict! Charon filesystem
 					<mailto:[email protected]>
 'h'	00-1F	linux/hpet.h		conflict!
MAINTAINERS +7 -0
index 5c38f21aee78..c92ad89ee5e5 100644
@@ -7630,6 +7630,13 @@ F:	Documentation/hwmon/ina2xx
 F:	drivers/hwmon/ina2xx.c
 F:	include/linux/platform_data/ina2xx.h
 
+INCREMENTAL FILESYSTEM
+M:	Eugene Zemtsov <[email protected]>
+S:	Supported
+F:	fs/incfs/
+F:	include/uapi/linux/incrementalfs.h
+F:	Documentation/filesystems/incrementalfs.rst
+
 INDUSTRY PACK SUBSYSTEM (IPACK)
 M:	Samuel Iglesias Gonsalvez <[email protected]>
 M:	Jens Taprogge <[email protected]>
fs/Kconfig +1 -0
index 3e6d3101f3ff..19f89c936209 100644
@@ -119,6 +119,7 @@ source "fs/quota/Kconfig"
 source "fs/autofs/Kconfig"
 source "fs/fuse/Kconfig"
 source "fs/overlayfs/Kconfig"
+source "fs/incfs/Kconfig"
 
 menu "Caches"
 
fs/Makefile +1 -0
index 427fec226fae..08c6b827df1a 100644
@@ -108,6 +108,7 @@ obj-$(CONFIG_AUTOFS_FS)		+= autofs/
 obj-$(CONFIG_ADFS_FS)		+= adfs/
 obj-$(CONFIG_FUSE_FS)		+= fuse/
 obj-$(CONFIG_OVERLAY_FS)	+= overlayfs/
+obj-$(CONFIG_INCREMENTAL_FS)	+= incfs/
 obj-$(CONFIG_ORANGEFS_FS)       += orangefs/
 obj-$(CONFIG_UDF_FS)		+= udf/
 obj-$(CONFIG_SUN_OPENPROMFS)	+= openpromfs/
fs/incfs/Kconfig new file +10 -0
new file mode 100644
index 000000000000..a810131deed0
@@ -0,0 +1,10 @@
+config INCREMENTAL_FS
+	tristate "Incremental file system support"
+	depends on BLOCK && CRC32
+	help
+	  Incremental FS is a read-only virtual file system that facilitates execution
+	  of programs while their binaries are still being lazily downloaded over the
+	  network, USB or pigeon post.
+
+	  To compile this file system support as a module, choose M here: the
+	  module will be called incrementalfs.
\ No newline at end of file
fs/incfs/Makefile new file +4 -0
new file mode 100644
index 000000000000..7892196c634f
@@ -0,0 +1,4 @@
+# SPDX-License-Identifier: GPL-2.0
+obj-$(CONFIG_INCREMENTAL_FS)	+= incrementalfs.o
+
+incrementalfs-y := main.o vfs.o
\ No newline at end of file
fs/incfs/main.c new file +85 -0

85 lines not on this page · raw message

fs/incfs/vfs.c new file +37 -0
new file mode 100644
index 000000000000..2e71f0edf8a1
@@ -0,0 +1,37 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Copyright 2018 Google LLC
+ */
+#include <linux/blkdev.h>
+#include <linux/fs.h>
+
+#include <uapi/linux/incrementalfs.h>
+
+static struct dentry *mount_fs(struct file_system_type *type, int flags,
+			       const char *dev_name, void *data);
+static void kill_sb(struct super_block *sb);
+
+struct file_system_type incfs_fs_type = {
+	.owner = THIS_MODULE,
+	.name = INCFS_NAME,
+	.mount = mount_fs,
+	.kill_sb = kill_sb,
+	.fs_flags = 0
+};
+
+static int fill_super_block(struct super_block *sb, void *data, int silent)
+{
+	return 0;
+}
+
+static struct dentry *mount_fs(struct file_system_type *type, int flags,
+			       const char *dev_name, void *data)
+{
+	return mount_nodev(type, flags, data, fill_super_block);
+}
+
+static void kill_sb(struct super_block *sb)
+{
+	generic_shutdown_super(sb);
+}
+
include/uapi/linux/incrementalfs.h new file +189 -0

189 lines not on this page · raw message

--
2.21.0.593.g511ec345e18-goog

#2 lore raw

Re: [PATCH 1/6] incfs: Add first files of incrementalfs

Documentation/filesystems/incrementalfs.rst line 416

Quoted 9 lines · On Thu, May 2, 2019 at 12:03 AM <[email protected]> wrote:
Documentation/filesystems/incrementalfs.rst new file +9 -0
+Design alternatives
+===================
+
+Why isn't incremental-fs implemented via FUSE?
+----------------------------------------------
+TLDR: FUSE-based filesystems add 20-80% of performance overhead for target
+scenarios, and increase power use on mobile beyond acceptable limit
+for widespread deployment. A custom kernel filesystem is the way to overcome
+these limitations.

he 80% performance overhead sounds bad. As fuse maintainer I'd
really be interested in finding out the causes.

Documentation/filesystems/incrementalfs.rst line 422

Quoted 6 lines
Documentation/filesystems/incrementalfs.rst new file +6 -0
+
+From the theoretical side of things, FUSE filesystem adds some overhead to
+each filesystem operation that’s not handled by OS page cache:
+
+    * When an IO request arrives to FUSE driver (D), it puts it into a queue
+      that runs on a separate kernel thread

The queue is run on a *user* thread, there's no intermediate kernel
thread involved.

Documentation/filesystems/incrementalfs.rst line 424

Quoted 2 lines
Documentation/filesystems/incrementalfs.rst new file +2 -0
+    * Then another separate user-mode handler process (H) has to run,
+      potentially after a context switch, to read the request from the queue.

Yes. How is it different from the data loader doing read(2) on .cmd?

Documentation/filesystems/incrementalfs.rst line 432

Quoted 8 lines
Documentation/filesystems/incrementalfs.rst new file +8 -0
+      Reading the request adds a kernel-user mode transition to the handling.
+    * (H) sends the IO request to kernel to handle it on some underlying storage
+      filesystem. This adds a user-kernel and kernel-user mode transition
+      pair to the handling.
+    * (H) then responds to the FUSE request via a write(2) call.
+      Writing the response is another user-kernel mode transition.
+    * (D) needs to read the response from (H) when its kernel thread runs
+      and forward it to the user

Again, you've just described exactly the same thing for data loader and .cmd. Why is the fuse case different?

Thanks,
Miklos

reviewer
#3 lore raw

Re: [PATCH 1/6] incfs: Add first files of incrementalfs

In reply to [email protected]
Quoted 11 lines · On 5/1/19 9:03 PM, [email protected] wrote:

From: Eugene Zemtsov <[email protected]>

- fs/incfs dir
- Kconfig (CONFIG_INCREMENTAL_FS)
- Makefile
- Module and file system initialization and clean up code
- New MAINTAINERS entry
- Add incrementalfs.h UAPI header
- Register ioctl range in ioctl-numbers.txt
- Documentation

Quoted 1 line

Hi,
This is just Documentation comments...

Quoted 81 lines
---
 Documentation/filesystems/incrementalfs.rst | 452 ++++++++++++++++++++
 Documentation/ioctl/ioctl-number.txt        |   1 +
 MAINTAINERS                                 |   7 +
 fs/Kconfig                                  |   1 +
 fs/Makefile                                 |   1 +
 fs/incfs/Kconfig                            |  10 +
 fs/incfs/Makefile                           |   4 +
 fs/incfs/main.c                             |  85 ++++
 fs/incfs/vfs.c                              |  37 ++
 include/uapi/linux/incrementalfs.h          | 189 ++++++++
 10 files changed, 787 insertions(+)
 create mode 100644 Documentation/filesystems/incrementalfs.rst
 create mode 100644 fs/incfs/Kconfig
 create mode 100644 fs/incfs/Makefile
 create mode 100644 fs/incfs/main.c
 create mode 100644 fs/incfs/vfs.c
 create mode 100644 include/uapi/linux/incrementalfs.h
Documentation/filesystems/incrementalfs.rst new file +56 -0
new file mode 100644
index 000000000000..682e3dcb6b5a
@@ -0,0 +1,452 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+=======================
+Incremental File System
+=======================
+
+Overview
+========
+Incremental FS is special-purpose Linux virtual file system that allows
+execution of a program while its binary and resource files are still being
+lazily downloaded over the network, USB etc. It is focused on incremental
+delivery for a small number (under 100) of big files (more than 10 megabytes).
+Incremental FS doesn’t allow direct writes into files and, once loaded, file
+content never changes. Incremental FS doesn’t use a block device, instead it
+saves data into a backing file located on a regular file-system.
+
+But why?
+--------
+To allow running **big** Android apps before their binaries and resources are
+fully downloaded to an Android device. If an app reads something not loaded yet,
+it needs to wait for the data block to be fetched, but in most cases hot blocks
+can be loaded in advance.
+
+Workflow
+--------
+A userspace process, called a data loader, mounts an instance of incremental-fs
+giving it a file descriptor on an underlying file system (like ext4 or f2fs).
+Incremental-fs reads content (if any) of this backing file and interprets it as
+a file system image with files, directories and data blocks. At this point
+the data loader can declare new files to be shown by incremental-fs.
+
+A process is started from a binary located on incremental-fs.
+All reads are served directly from the backing file
+without roundtrips into userspace. If the process accesses a data block that was
+not originally present in the backing file, the read operation waits.
+
+Meanwhile the data loader can feed new data blocks to incremental-fs by calling
+write() on a special .cmd pseudo-file. The data loader can request information
+about pending reads by calling poll() and read() on the .cmd pseudo-file.
+This mechanism allows the data loader to serve most urgently needed data first.
+Once a data block is given to incremental-fs, it saves it to the backing file
+and unblocks all the reads waiting for this block.
+
+Eventually all data for all files is uploaded by the data loader, and saved by
+incremental-fs into the backing file. At that moment the data loader is not
+needed any longer. The backing file will play the role of a complete
+filesystem image for all future runs of the program.
+
+Non-goals
+---------
+* Allowing direct writes by the executing processes into files on incremental-fs
+* Allowing the data loader change file size or content after it was loaded.
+* Having more than a couple hundred files and directories.
+
+
+Features

Documentation/filesystems/incrementalfs.rst line 66

Quoted 10 lines
Documentation/filesystems/incrementalfs.rst new file +10 -0
+========
+
+Read-only, but not unchanging
+-----------------------------
+On the surface a mount directory of incremental-fs would look similar to
+a read-only instance of network file system: files and directories can be
+listed and read, but can’t be directly created or modified via creat() or
+write(). At the same time the data loader can make changes to a directory
+structure via external ioctl-s. i.e. link and unlink files and directories
+(if they empty). Data can't be changed this way, once a file block is loaded

way; once

Documentation/filesystems/incrementalfs.rst line 71

Quoted 5 lines
Documentation/filesystems/incrementalfs.rst new file +5 -0
+there is no way to change it.
+
+Filesystem image in a backing file
+----------------------------------
+Instead of using a block device, all data and metadata is stored in a

are stored

Documentation/filesystems/incrementalfs.rst line 80

Quoted 9 lines
Documentation/filesystems/incrementalfs.rst new file +9 -0
+backing file provided as a mount parameter. The backing file is located on
+an underlying file system (like ext4 or f2fs). Such approach is very similar
+to what might be achieved by using loopback device with a traditional file
+system, but it avoids extra set-up steps and indirections. It also allows
+incremental-fs image to dynamically grow as new files and data come without
+having to do any extra steps for resizing.
+
+If the backing file contains data at the moment when incremental-fs is mounted,
+content of the backing file is being interpreted as filesystem image.

file is interpreted as

Documentation/filesystems/incrementalfs.rst line 89

Quoted 9 lines
Documentation/filesystems/incrementalfs.rst new file +9 -0
+New files and data can still be added through the external interface,
+and they will be saved to the backing file.
+
+Data compression
+----------------
+Incremental-fs can store compressed data. In this case each 4KB data block is
+compressed separately. Data blocks can be provided to incremental-fs by
+the data loader in a compressed form. Incremental-fs uncompresses blocks
+each time a executing process reads it (modulo page cache). Compression also

an executing process

Documentation/filesystems/incrementalfs.rst line 95

Quoted 6 lines
Documentation/filesystems/incrementalfs.rst new file +6 -0
+takes care of blocks composed of all zero bytes removing necessity to handle
+this case separately.
+
+Partially present files
+-----------------------
+Data in the files consists of 4KB blocks, each block can be present or absent.

blocks; each block

Quoted 16 lines
Documentation/filesystems/incrementalfs.rst new file +16 -0
+Unlike in sparse files, reading an absent block doesn’t return all zeros.
+It waits for the data block to be loaded via the ioctl interface
+(respecting a timeout). Once a data block is loaded it never disappears
+and can’t be changed or erased from a file. This ability to frictionlessly
+wait for temporary missing data is the main feature of incremental-fs.
+
+Hard links. Multiple names for the same file
+--------------------------------------------
+Like all traditional UNIX file systems, incremental-fs supports hard links,
+i.e. different file names in different directories can refer to the same file.
+As mentioned above new hard links can be created and removed via
+the ioctl interface, but actual data files are immutable, modulo partial
+data loading. Each directory can only have at most one name referencing it.
+
+Inspection of incremental-fs internal state
+-------------------------------------------

Documentation/filesystems/incrementalfs.rst line 121

Quoted 10 lines
Documentation/filesystems/incrementalfs.rst new file +10 -0
+poll() and read() on the .cmd pseudo-file allow data loaders to get a list of
+read operations stalled due to lack of a data block (pending reads).
+
+
+Application Programming Interface
+=================================
+
+Regular file system interface
+-----------------------------
+Executing process access files and directories via regular Linux file interface:

accesses

Quoted 9 lines
Documentation/filesystems/incrementalfs.rst new file +9 -0
+open, read, close etc. All the intricacies of data loading a file representation
+are hidden from them.
+
+External .cmd file interface
+----------------------------
+When incremental-fs is mounted, a mount directory contains a pseudo-file
+called '.cmd'. The data loader will open this file and call read(), write(),
+poll() and ioctl() on it inspect and change state of incremental-fs.
+

Documentation/filesystems/incrementalfs.rst line 140

Quoted 10 lines
Documentation/filesystems/incrementalfs.rst new file +10 -0
+poll() and read() are used by the data loader to wait for pending reads to
+appear and obtain an array of ``struct incfs_pending_read_info``.
+
+write() is used by the data loader to feed new data blocks to incremental-fs.
+A data buffer given to write() is interpreted as an array of
+``struct incfs_new_data_block``. Structs in the array describe locations and
+properties of data blocks loaded with this write() call.
+
+``ioctl(INCFS_IOC_PROCESS_INSTRUCTION)`` is used to change structure of
+incremental-fs. It receives an pointer to ``struct incfs_instruction``

a pointer

Quoted 195 lines
Documentation/filesystems/incrementalfs.rst new file +195 -0
+where type field can have be one of the following values.
+
+**INCFS_INSTRUCTION_NEW_FILE**
+Creates an inode (a file or a directory) without a name.
+It assumes ``incfs_new_file_instruction.file`` is populated with details.
+
+**INCFS_INSTRUCTION_ADD_DIR_ENTRY**
+Creates a name (aka hardlink) for an inode in a directory.
+A directory can't have more than one hardlink pointing to it, but files can be
+linked from different directories.
+It assumes ``incfs_new_file_instruction.dir_entry`` is populated with details.
+
+**INCFS_INSTRUCTION_REMOVE_DIR_ENTRY**
+Remove a name (aka hardlink) for a file from a directory.
+Only empty directories can be unlinked.
+It assumes ``incfs_new_file_instruction.dir_entry`` is populated with details.
+
+For more details see in uapi/linux/incrementalfs.h and samples below.
+
+Supported mount options
+-----------------------
+See ``fs/incfs/options.c`` for more details.
+
+    * ``backing_fd=<unsigned int>``
+        Required. A file descriptor of a backing file opened by the process
+        calling mount(2). This descriptor can be closed after mount returns.
+
+    * ``read_timeout_msc=<unsigned int>``
+        Default: 1000. Timeout in milliseconds before a read operation fails
+        if no data found in the backing file or provided by the data loader.
+
+Sysfs files
+-----------
+``/sys/fs/incremental-fs/version`` - a current version of the filesystem.
+One ASCII encoded positive integer number with a new line at the end.
+
+
+Examples
+--------
+See ``sample_data_loader.c`` for a complete implementation of a data loader.
+
+Mount incremental-fs
+~~~~~~~~~~~~~~~~~~~~
+
+::
+
+    int mount_fs(char *mount_dir, char *backing_file, int timeout_msc)
+    {
+        static const char fs_name[] = INCFS_NAME;
+        char mount_options[512];
+        int backing_fd;
+        int result;
+
+        backing_fd = open(backing_file, O_RDWR);
+        if (backing_fd == -1) {
+            perror("Error in opening backing file");
+            return 1;
+        }
+
+        snprintf(mount_options, ARRAY_SIZE(mount_options),
+            "backing_fd=%u,read_timeout_msc=%u", backing_fd, timeout_msc);
+
+        result = mount(fs_name, mount_dir, fs_name, 0, mount_options);
+        if (result != 0)
+            perror("Error mounting fs.");
+        return result;
+    }
+
+Open .cmd file
+~~~~~~~~~~~~~~
+
+::
+
+    int open_commands_file(char *mount_dir)
+    {
+        char cmd_file[255];
+        int cmd_fd;
+
+        snprintf(cmd_file, ARRAY_SIZE(cmd_file), "%s/.cmd", mount_dir);
+        cmd_fd = open(cmd_file, O_RDWR);
+        if (cmd_fd < 0)
+            perror("Can't open commands file");
+        return cmd_fd;
+    }
+
+Add a file to the file system
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+::
+
+    int create_file(int cmd_fd, char *filename, int *ino_out, size_t size)
+    {
+        int ret = 0;
+        __u16 ino = 0;
+        struct incfs_instruction inst = {
+                .version = INCFS_HEADER_VER,
+                .type = INCFS_INSTRUCTION_NEW_FILE,
+                .file = {
+                    .size = size,
+                    .mode = S_IFREG | 0555,
+                }
+        };
+
+        ret = ioctl(cmd_fd, INCFS_IOC_PROCESS_INSTRUCTION, &inst);
+        if (ret)
+            return -errno;
+
+        ino = inst.file.ino_out;
+        inst = (struct incfs_instruction){
+                .version = INCFS_HEADER_VER,
+                .type = INCFS_INSTRUCTION_ADD_DIR_ENTRY,
+                .dir_entry = {
+                    .dir_ino = INCFS_ROOT_INODE,
+                    .child_ino = ino,
+                    .name = ptr_to_u64(filename),
+                    .name_len = strlen(filename)
+                }
+            };
+        ret = ioctl(cmd_fd, INCFS_IOC_PROCESS_INSTRUCTION, &inst);
+        if (ret)
+            return -errno;
+        *ino_out = ino;
+        return 0;
+    }
+
+Load data into a file
+~~~~~~~~~~~~~~~~~~~~~
+
+::
+
+    int cmd_fd = open_commands_file(path_to_mount_dir);
+    char *data = get_some_data();
+    struct incfs_new_data_block block;
+    int err;
+
+    block.file_ino = file_ino;
+    block.block_index = 0;
+    block.compression = COMPRESSION_NONE;
+    block.data = (__u64)data;
+    block.data_len = INCFS_DATA_FILE_BLOCK_SIZE;
+
+    err = write(cmd_fd, &block, sizeof(block));
+
+
+Get an array of pending reads
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+::
+
+    int poll_res = 0;
+    struct incfs_pending_read_info reads[10];
+    int cmd_fd = open_commands_file(path_to_mount_dir);
+    struct pollfd pollfd = {
+        .fd = cmd_fd,
+        .events = POLLIN
+    };
+
+    poll_res = poll(&pollfd, 1, timeout);
+    if (poll_res > 0 && (pollfd.revents | POLLIN)) {
+        ssize_t read_res = read(cmd_fd, reads, sizeof(reads));
+        if (read_res > 0)
+            printf("Waiting reads %ld\n", read_res / sizeof(reads[0]));
+    }
+
+
+
+Ondisk format
+=============
+
+General principles
+------------------
+* The backbone of the incremental-fs ondisk format is an append only linked
+  list of metadata blocks. Each metadata block contains an offset of the next
+  one. These blocks describe files and directories on the
+  file system. They also represent actions of adding and removing file names
+  (hard links).
+  Every time incremental-fs instance is mounted, it reads through this list
+  to recreate filesystem's state in memory. An offset of the first record in the
+  metadata list is stored in the superblock at the beginning of the backing
+  file.
+
+* Most of the backing file is taken by data areas and blockmaps.
+  Since data blocks can be compressed and have different sizes,
+  single per-file data area can't be pre-allocated. That's why blockmaps are
+  needed in order to find a location and size of each data block in
+  the backing file. Each time a file is created, a corresponding block map is
+  allocated to store future offsets of data blocks.
+
+  Whenever a data block is given by data loader to incremental-fs:
+    - A data area with the given block is appended to the end of
+      the backing file.
+    - A record in the blockmap for the given block index is updated to reflect
+      its location, size, and compression algorithm.
+
+Important format details

Documentation/filesystems/incrementalfs.rst line 345

Quoted 10 lines
Documentation/filesystems/incrementalfs.rst new file +10 -0
+------------------------
+Ondisk structures are defined in the ``format.h`` file. They are all packed
+and use little-endian order.
+A backing file must start with ``incfs_super_block`` with ``s_magic`` field
+equal to 0x5346434e49 "INCFS".
+
+Metadata records:
+
+* ``incfs_inode`` - metadata record to declare a file or a directory.
+                    ``incfs_inode.i_mode`` determents if it is a file

determines

Documentation/filesystems/incrementalfs.rst line 353

Quoted 8 lines
Documentation/filesystems/incrementalfs.rst new file +8 -0
+                    or a directory.
+* ``incfs_blockmap_entry`` - metadata record that specifies size and location
+                            of a blockmap area for a given file. This area
+                            contains an array of ``incfs_blockmap_entry``-s.
+* ``incfs_dir_action`` - metadata record that specifies changes made to a
+                    to a directory structure, e.g. add or remove a hardlink.
+* ``incfs_md_header`` - header of a metadata record. It's always a part
+                    of other structures and served purpose of metadata

? serves

Documentation/filesystems/incrementalfs.rst line 361

Quoted 8 lines
Documentation/filesystems/incrementalfs.rst new file +8 -0
+                    bookkeeping.
+
+Other ondisk structures:
+
+* ``incfs_super_block`` - backing file header
+* ``incfs_blockmap_entry`` - a record in a blockmap area that describes size
+                        and location of a data block.
+* Data blocks dont have any particular structure, they are written to the backing

don't

Quoted 91 lines
Documentation/filesystems/incrementalfs.rst new file +91 -0
+  file in a raw form as they come from a data loader.
+
+
+Backing file layout
+-------------------
+::
+
+              +-------------------------------------------+
+              |            incfs_super_block              |]---+
+              +-------------------------------------------+    |
+              |                 metadata                  |<---+
+              |                incfs_inode                |]---+
+              +-------------------------------------------+    |
+                        .........................              |
+              +-------------------------------------------+    |   metadata
+     +------->|               blockmap area               |    |  list links
+     |        |          [incfs_blockmap_entry]           |    |
+     |        |          [incfs_blockmap_entry]           |    |
+     |        |          [incfs_blockmap_entry]           |    |
+     |    +--[|          [incfs_blockmap_entry]           |    |
+     |    |   |          [incfs_blockmap_entry]           |    |
+     |    |   |          [incfs_blockmap_entry]           |    |
+     |    |   +-------------------------------------------+    |
+     |    |             .........................              |
+     |    |   +-------------------------------------------+    |
+     |    |   |                 metadata                  |<---+
+     +----|--[|               incfs_blockmap              |]---+
+          |   +-------------------------------------------+    |
+          |             .........................              |
+          |   +-------------------------------------------+    |
+          +-->|                 data block                |    |
+              +-------------------------------------------+    |
+                        .........................              |
+              +-------------------------------------------+    |
+              |                 metadata                  |<---+
+              |             incfs_dir_action              |
+              +-------------------------------------------+
+
+Unreferenced files and absence of garbage collection
+----------------------------------------------------
+Described file format can produce files that don't have any names for them in
+any directories. Incremental-fs takes no steps to prevent such situations or
+reclaim space occupied by such files in the backing file. If garbage collection
+is needed it has to be implemented as a separate userspace tool.
+
+
+Design alternatives
+===================
+
+Why isn't incremental-fs implemented via FUSE?
+----------------------------------------------
+TLDR: FUSE-based filesystems add 20-80% of performance overhead for target
+scenarios, and increase power use on mobile beyond acceptable limit
+for widespread deployment. A custom kernel filesystem is the way to overcome
+these limitations.
+
+From the theoretical side of things, FUSE filesystem adds some overhead to
+each filesystem operation that’s not handled by OS page cache:
+
+    * When an IO request arrives to FUSE driver (D), it puts it into a queue
+      that runs on a separate kernel thread
+    * Then another separate user-mode handler process (H) has to run,
+      potentially after a context switch, to read the request from the queue.
+      Reading the request adds a kernel-user mode transition to the handling.
+    * (H) sends the IO request to kernel to handle it on some underlying storage
+      filesystem. This adds a user-kernel and kernel-user mode transition
+      pair to the handling.
+    * (H) then responds to the FUSE request via a write(2) call.
+      Writing the response is another user-kernel mode transition.
+    * (D) needs to read the response from (H) when its kernel thread runs
+      and forward it to the user
+
+Together, the scenario adds 2 extra user-kernel-user mode transition pairs,
+and potentially has up to 3 additional context switches for the FUSE kernel
+thread and the user-mode handler to start running for each IO request on the
+filesystem.
+This overhead can vary from unnoticeable to unmanageable, depending on the
+target scenario. But it will always burn extra power via CPU staying longer
+in non-idle state, handling context switches and mode transitions.
+One important goal for the new filesystem is to be able to handle each page
+read separately on demand, because we don't want to wait and download more data
+than absolutely necessary. Thus readahead would need to be disabled completely.
+This increases the number of separate IO requests and the FUSE related overhead
+by almost 32x (128KB readahead limit vs 4KB individual block operations)
+
+For more info see a 2017 USENIX research paper:
+To FUSE or Not to FUSE: Performance of User-Space File Systems
+Bharath Kumar Reddy Vangoor, Stony Brook University;
+Vasily Tarasov, IBM Research-Almaden;
+Erez Zadok, Stony Brook University
+https://www.usenix.org/system/files/conference/fast17/fast17-vangoor.pdf
Signature · 1 line
~Randy
#4 lore raw

Re: [PATCH 1/6] incfs: Add first files of incrementalfs

In reply to [email protected]

+linux-api

Quoted 10 lines · On Tue, May 7, 2019 at 4:23 PM <[email protected]> wrote:

- fs/incfs dir
- Kconfig (CONFIG_INCREMENTAL_FS)
- Makefile
- Module and file system initialization and clean up code
- New MAINTAINERS entry
- Add incrementalfs.h UAPI header
- Register ioctl range in ioctl-numbers.txt
- Documentation

[...]

Quoted 18 lines
Documentation/filesystems/incrementalfs.rst new file +12 -0
new file mode 100644
index 000000000000..682e3dcb6b5a
@@ -0,0 +1,452 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+=======================
+Incremental File System
+=======================
+
+Overview
+========
+Incremental FS is special-purpose Linux virtual file system that allows
+execution of a program while its binary and resource files are still being
+lazily downloaded over the network, USB etc. It is focused on incremental
+delivery for a small number (under 100) of big files (more than 10 megabytes).

Documentation/filesystems/incrementalfs.rst line 22

Quoted 10 lines
Documentation/filesystems/incrementalfs.rst new file +10 -0
+Incremental FS doesn’t allow direct writes into files and, once loaded, file
+content never changes. Incremental FS doesn’t use a block device, instead it
+saves data into a backing file located on a regular file-system.
+
+But why?
+--------
+To allow running **big** Android apps before their binaries and resources are
+fully downloaded to an Android device. If an app reads something not loaded yet,
+it needs to wait for the data block to be fetched, but in most cases hot blocks
+can be loaded in advance.

But the idea is that eventually, the complete application will be downloaded, right? You're not planning to download the last few chunks of an app on demand weeks after it has been installed?

Quoted 14 lines
Documentation/filesystems/incrementalfs.rst new file +14 -0
+Workflow
+--------
+A userspace process, called a data loader, mounts an instance of incremental-fs
+giving it a file descriptor on an underlying file system (like ext4 or f2fs).
+Incremental-fs reads content (if any) of this backing file and interprets it as
+a file system image with files, directories and data blocks. At this point
+the data loader can declare new files to be shown by incremental-fs.
+
+A process is started from a binary located on incremental-fs.
+All reads are served directly from the backing file
+without roundtrips into userspace. If the process accesses a data block that was
+not originally present in the backing file, the read operation waits.
+
+Meanwhile the data loader can feed new data blocks to incremental-fs by calling

Documentation/filesystems/incrementalfs.rst line 47

Quoted 10 lines
Documentation/filesystems/incrementalfs.rst new file +10 -0
+write() on a special .cmd pseudo-file. The data loader can request information
+about pending reads by calling poll() and read() on the .cmd pseudo-file.
+This mechanism allows the data loader to serve most urgently needed data first.
+Once a data block is given to incremental-fs, it saves it to the backing file
+and unblocks all the reads waiting for this block.
+
+Eventually all data for all files is uploaded by the data loader, and saved by
+incremental-fs into the backing file. At that moment the data loader is not
+needed any longer. The backing file will play the role of a complete
+filesystem image for all future runs of the program.

This means that for all future runs, you still need to mount an incfs instance to be able to access application files, even when the complete application has been downloaded already, right? Wouldn't it be nicer if, once the complete application has been downloaded, you could stop using a shim layer entirely? That way, the performance of the shim layer would also matter less.

Is there a reason why this thing is not backed by a normal directory hierarchy on the backing file system, instead of the single image file you're proposing?

Documentation/filesystems/incrementalfs.rst line 137

Quoted 13 lines
Documentation/filesystems/incrementalfs.rst new file +13 -0
+External .cmd file interface
+----------------------------
+When incremental-fs is mounted, a mount directory contains a pseudo-file
+called '.cmd'. The data loader will open this file and call read(), write(),
+poll() and ioctl() on it inspect and change state of incremental-fs.
+
+poll() and read() are used by the data loader to wait for pending reads to
+appear and obtain an array of ``struct incfs_pending_read_info``.
+
+write() is used by the data loader to feed new data blocks to incremental-fs.
+A data buffer given to write() is interpreted as an array of
+``struct incfs_new_data_block``. Structs in the array describe locations and
+properties of data blocks loaded with this write() call.

You can't do that. A write() handler must not interpret written data as pointers; that must be handled with an ioctl instead.

Quoted 8 lines
Documentation/filesystems/incrementalfs.rst new file +8 -0
+``ioctl(INCFS_IOC_PROCESS_INSTRUCTION)`` is used to change structure of
+incremental-fs. It receives an pointer to ``struct incfs_instruction``
+where type field can have be one of the following values.
+
+**INCFS_INSTRUCTION_NEW_FILE**
+Creates an inode (a file or a directory) without a name.
+It assumes ``incfs_new_file_instruction.file`` is populated with details.
+

Documentation/filesystems/incrementalfs.rst line 156

Quoted 10 lines
Documentation/filesystems/incrementalfs.rst new file +10 -0
+**INCFS_INSTRUCTION_ADD_DIR_ENTRY**
+Creates a name (aka hardlink) for an inode in a directory.
+A directory can't have more than one hardlink pointing to it, but files can be
+linked from different directories.
+It assumes ``incfs_new_file_instruction.dir_entry`` is populated with details.
+
+**INCFS_INSTRUCTION_REMOVE_DIR_ENTRY**
+Remove a name (aka hardlink) for a file from a directory.
+Only empty directories can be unlinked.
+It assumes ``incfs_new_file_instruction.dir_entry`` is populated with details.

What is the usecase for removing directory entries?

With the API you're proposing, you're always going to want to populate the entire directory hierarchy before running an application from incfs, because otherwise lookups and readdir might fail in a way the application doesn't expect, right?

Documentation/filesystems/incrementalfs.rst line 170

Quoted 13 lines
Documentation/filesystems/incrementalfs.rst new file +13 -0
+For more details see in uapi/linux/incrementalfs.h and samples below.
+
+Supported mount options
+-----------------------
+See ``fs/incfs/options.c`` for more details.
+
+    * ``backing_fd=<unsigned int>``
+        Required. A file descriptor of a backing file opened by the process
+        calling mount(2). This descriptor can be closed after mount returns.
+
+    * ``read_timeout_msc=<unsigned int>``
+        Default: 1000. Timeout in milliseconds before a read operation fails
+        if no data found in the backing file or provided by the data loader.

So... if I run an application from this incremental file system, and the application page faults on a page that hasn't been loaded yet, and my phone happens to not have connectivity for a second because it's moving between wifi and cellular or whatever, the application will crash?

Quoted 6 lines
Documentation/filesystems/incrementalfs.rst new file +6 -0
+Open .cmd file
+~~~~~~~~~~~~~~
+
+::
+
+    int open_commands_file(char *mount_dir)

Documentation/filesystems/incrementalfs.rst line 224

Quoted 10 lines
Documentation/filesystems/incrementalfs.rst new file +10 -0
+    {
+        char cmd_file[255];
+        int cmd_fd;
+
+        snprintf(cmd_file, ARRAY_SIZE(cmd_file), "%s/.cmd", mount_dir);
+        cmd_fd = open(cmd_file, O_RDWR);
+        if (cmd_fd < 0)
+            perror("Can't open commands file");
+        return cmd_fd;
+    }

How is access control for this supposed to work? The command file is created with mode 0666, so does that mean that any instance of the application can write arbitrary code into chunks that haven't been loaded yet, modulo SELinux?

Documentation/filesystems/incrementalfs.rst

Quoted 7 lines
Documentation/filesystems/incrementalfs.rst new file +7 -0
+Design alternatives
+===================
+
+Why isn't incremental-fs implemented via FUSE?
+----------------------------------------------
+TLDR: FUSE-based filesystems add 20-80% of performance overhead for target
+scenarios

Really?

Quoted 2 lines

and increase power use on mobile beyond acceptable limit +for widespread deployment.

From what I can tell, you only really need this thing to be active while the application is still being downloaded - and at that point in time, you're shoving packets over a wireless connection, checking data integrity, writing blocks to disk, and so on, right? Does FUSE add noticeable power use to that?

Quoted 2 lines

A custom kernel filesystem is the way to overcome
+these limitations.

I doubt that. I see two main alternatives that I think would both be better:

1. Use a FUSE filesystem to trap writes while files are being downloaded, then switch to native ext4.
2. Add an eBPF hook in the ext4 read path. The hook would take the inode number and the offset as input and return a value that indicates whether the kernel should let the read go through or block the read and send a notification to userspace over a file descriptor. Sort of like userfaultfd, except with an eBPF-based fastpath. (And to deal with readahead, you could perhaps add a flag that is passed through to the read code to say "this is readahead", and then throw an error instead of blocking the read.)

Documentation/filesystems/incrementalfs.rst line 419

Quoted 2 lines
Documentation/filesystems/incrementalfs.rst new file +2 -0
+From the theoretical side of things, FUSE filesystem adds some overhead to
+each filesystem operation that’s not handled by OS page cache:

How many filesystem operations do you have during application download that are not handled by the OS page cache?

Quoted 9 lines
Documentation/filesystems/incrementalfs.rst new file +9 -0
+    * When an IO request arrives to FUSE driver (D), it puts it into a queue
+      that runs on a separate kernel thread
+    * Then another separate user-mode handler process (H) has to run,
+      potentially after a context switch, to read the request from the queue.
+      Reading the request adds a kernel-user mode transition to the handling.
+    * (H) sends the IO request to kernel to handle it on some underlying storage
+      filesystem. This adds a user-kernel and kernel-user mode transition
+      pair to the handling.
+    * (H) then responds to the FUSE request via a write(2) call.

Documentation/filesystems/incrementalfs.rst

Quoted 10 lines
Documentation/filesystems/incrementalfs.rst new file +10 -0
+      Writing the response is another user-kernel mode transition.
+    * (D) needs to read the response from (H) when its kernel thread runs
+      and forward it to the user
+
+Together, the scenario adds 2 extra user-kernel-user mode transition pairs,
+and potentially has up to 3 additional context switches for the FUSE kernel
+thread and the user-mode handler to start running for each IO request on the
+filesystem.
+This overhead can vary from unnoticeable to unmanageable, depending on the
+target scenario.

Is the overhead of extra context switches really "unmanageable" compared to the latency of storage?

Documentation/filesystems/incrementalfs.rst line 445

Quoted 7 lines

But it will always burn extra power via CPU staying longer

Documentation/filesystems/incrementalfs.rst new file +6 -0
+in non-idle state, handling context switches and mode transitions.
+One important goal for the new filesystem is to be able to handle each page
+read separately on demand, because we don't want to wait and download more data
+than absolutely necessary. Thus readahead would need to be disabled completely.
+This increases the number of separate IO requests and the FUSE related overhead
+by almost 32x (128KB readahead limit vs 4KB individual block operations)

You could implement the readahead in the FUSE filesystem, no? Check if adjacent blocks are already available, and if so, shove them into the page cache without waiting for the kernel to ask for them?

Documentation/filesystems/incrementalfs.rst line 452

Quoted 6 lines
Documentation/filesystems/incrementalfs.rst new file +6 -0
+For more info see a 2017 USENIX research paper:
+To FUSE or Not to FUSE: Performance of User-Space File Systems
+Bharath Kumar Reddy Vangoor, Stony Brook University;
+Vasily Tarasov, IBM Research-Almaden;
+Erez Zadok, Stony Brook University
+https://www.usenix.org/system/files/conference/fast17/fast17-vangoor.pdf

From that paper, the workloads that are interesting for you are either the seq-rd-1th-1f or the rnd-rd-1th-1f workloads, right?

#5 lore raw

Re: [PATCH 1/6] incfs: Add first files of incrementalfs

In reply to [email protected]

Documentation/filesystems/incrementalfs.rst line 175

Quoted 4 lines · On Wed, May 01, 2019 at 09:03:26PM -0700, [email protected] wrote:
Documentation/filesystems/incrementalfs.rst new file +4 -0
+Sysfs files
+-----------
+``/sys/fs/incremental-fs/version`` - a current version of the filesystem.
+One ASCII encoded positive integer number with a new line at the end.

sysfs (no "S" please) documentation goes in Documentation/ABI/, not burried in a random file somewhere else :)

Also, "filesystem version" does not make much sense, does it? Why does userspace care about this, all they really care about is the _kernel_ version. We do not independantly version the individual components of the kernel, that way lies madness.

thanks,

greg k-h

#6 lore raw

Re: [PATCH 1/6] incfs: Add first files of incrementalfs

In reply to [email protected]

But since you did write some sysfs code, might as well review it so you know how to do it better next time around :)

fs/incfs/main.c line 20

Quoted 6 lines · On Wed, May 01, 2019 at 09:03:26PM -0700, [email protected] wrote:
fs/incfs/main.c new file +6 -0
+static struct kobject *sysfs_root;
+
+static ssize_t version_show(struct kobject *kobj,
+			    struct kobj_attribute *attr, char *buff)
+{
+	return snprintf(buff, PAGE_SIZE, "%d\n", INCFS_CORE_VERSION);

Hint about sysfs, it's "one value per file", so you NEVER care about the size of the buffer because you "know" your single little number will always fit.

So this should be:

	return sprintf(buff, "%d\n", INCFS_CORE_VERSION);

Yes, code checkers hate it, send them my way, I'll be glad to point out their folly :)

fs/incfs/main.c line 32

Quoted 10 lines
fs/incfs/main.c new file +10 -0
+static struct kobj_attribute version_attr = __ATTR_RO(version);
+
+static struct attribute *attributes[] = {
+	&version_attr.attr,
+	NULL,
+};
+
+static const struct attribute_group attr_group = {
+	.attrs = attributes,
+};

ATTRIBUTE_GROUP()?

fs/incfs/main.c line 36

Quoted 3 lines
fs/incfs/main.c new file +3 -0
+static int __init init_sysfs(void)
+{
+	int res = 0;

No need to set to 0 here.

fs/incfs/main.c line 47

Quoted 11 lines
fs/incfs/main.c new file +11 -0
+
+	sysfs_root = kobject_create_and_add(INCFS_NAME, fs_kobj);
+	if (!sysfs_root)
+		return -ENOMEM;
+
+	res = sysfs_create_group(sysfs_root, &attr_group);
+	if (res) {
+		kobject_put(sysfs_root);
+		sysfs_root = NULL;
+	}
+	return res;

To be extra "fancy", there's no real need to create a kobject for your filesystem if all you are doing is creating a subdir and some individual attributes. Just add a "named" group to the parent kobject. Can be done in a single line, no need for having to deal with fancy error cases.

fs/incfs/main.c line 55

Quoted 8 lines
fs/incfs/main.c new file +8 -0
+}
+
+static void cleanup_sysfs(void)
+{
+	if (sysfs_root) {
+		sysfs_remove_group(sysfs_root, &attr_group);
+		kobject_put(sysfs_root);
+		sysfs_root = NULL;

Why set it to NULL?

Review

Quoted 2 lines
(quoted diff) +2 -0
+	}
+}

thanks,

greg k-h

#7 lore raw

PATCH 2/6 incfs: Backing file format

In reply to [email protected]

From: Eugene Zemtsov <[email protected]>

- Read and write logic for ondisk backing file format (aka incfs image)
- Add format.c and format.h
- Utils in internal.h

---
 fs/incfs/Makefile   |   2 +-
 fs/incfs/format.c   | 554 ++++++++++++++++++++++++++++++++++++++++++++
 fs/incfs/format.h   | 294 +++++++++++++++++++++++
 fs/incfs/internal.h |  31 +++
 4 files changed, 880 insertions(+), 1 deletion(-)
 create mode 100644 fs/incfs/format.c
 create mode 100644 fs/incfs/format.h
 create mode 100644 fs/incfs/internal.h
fs/incfs/Makefile +1 -1
index 7892196c634f..cdea18c7213e 100644
@@ -1,4 +1,4 @@
 # SPDX-License-Identifier: GPL-2.0
 obj-$(CONFIG_INCREMENTAL_FS)	+= incrementalfs.o
 
-incrementalfs-y := main.o vfs.o
\ No newline at end of file
+incrementalfs-y := main.o vfs.o format.o
fs/incfs/format.c new file +554 -0

554 lines not on this page · raw message

fs/incfs/format.h new file +294 -0

294 lines not on this page · raw message

fs/incfs/internal.h new file +31 -0
new file mode 100644
index 000000000000..de8b6240e347
@@ -0,0 +1,31 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Copyright 2018 Google LLC
+ */
+#ifndef _INCFS_INTERNAL_H
+#define _INCFS_INTERNAL_H
+#include <linux/types.h>
+
+struct mem_range {
+	u8 *data;
+	size_t len;
+};
+
+static inline struct mem_range range(u8 *data, size_t len)
+{
+	return (struct mem_range){ .data = data, .len = len };
+}
+
+#ifdef DEBUG
+#define LOCK_REQUIRED(lock)                                                    \
+	do {                                                                   \
+		if (!mutex_is_locked(&(lock))) {                               \
+			pr_err(#lock " must be taken");                        \
+			panic("Lock not taken.");                              \
+		}                                                              \
+	} while (0)
+#else
+#define LOCK_REQUIRED(lock)
+#endif
+
+#endif /* _INCFS_INTERNAL_H */

--
2.21.0.593.g511ec345e18-goog

#8 lore raw

PATCH 3/6 incfs: Management of in-memory FS data structures

In reply to [email protected]

From: Eugene Zemtsov <[email protected]>

- Data structures for files, dirs, blocks, segments etc.
- Reading and uncompressing data blocks
- Waiting for temporarily missing data blocks
- Pending reads reporting
- Processing incfs instructions coming from ioctl
- Processing metadata blocks read from the backing file

---
 fs/incfs/Makefile    |    2 +-
 fs/incfs/data_mgmt.c | 1312 ++++++++++++++++++++++++++++++++++++++++++
 fs/incfs/data_mgmt.h |  213 +++++++
 3 files changed, 1526 insertions(+), 1 deletion(-)
 create mode 100644 fs/incfs/data_mgmt.c
 create mode 100644 fs/incfs/data_mgmt.h
fs/incfs/Makefile +1 -1
index cdea18c7213e..19250a09348e 100644
@@ -1,4 +1,4 @@
 # SPDX-License-Identifier: GPL-2.0
 obj-$(CONFIG_INCREMENTAL_FS)	+= incrementalfs.o
 
-incrementalfs-y := main.o vfs.o format.o
+incrementalfs-y := main.o vfs.o format.o data_mgmt.o
fs/incfs/data_mgmt.c new file +1312 -0

1,312 lines not on this page · raw message

fs/incfs/data_mgmt.h new file +213 -0

213 lines not on this page · raw message

--
2.21.0.593.g511ec345e18-goog

#9 lore raw

PATCH 4/6 incfs: Integration with VFS layer

In reply to [email protected]

From: Eugene Zemtsov <[email protected]>

Implementation of VFS callbacks for
- Reading data pages
- Traversing dir structure
- Handling ioctl-s
- Handling .cmd file reads and writes
- Mounting/unmounting file system

---
 fs/incfs/vfs.c | 834 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 834 insertions(+)
fs/incfs/vfs.c +834 -0
index 2e71f0edf8a1..7b453f19b543 100644
@@ -4,12 +4,50 @@
  */
 #include <linux/blkdev.h>
 #include <linux/fs.h>
+#include <linux/namei.h>
+#include <linux/file.h>
+#include <linux/mm.h>
+#include <linux/mount.h>
+#include <linux/kernel.h>
+#include <linux/pagemap.h>
+#include <linux/string.h>
+#include <linux/parser.h>
+#include <linux/seq_file.h>
+#include <linux/poll.h>
 
 #include <uapi/linux/incrementalfs.h>
+#include "data_mgmt.h"
 
+#define READ_EXEC_FILE_MODE 0555
+#define READ_WRITE_FILE_MODE 0666
+
+static int remount_fs(struct super_block *sb, int *flags, char *data);
 static struct dentry *mount_fs(struct file_system_type *type, int flags,
 			       const char *dev_name, void *data);
+static struct dentry *dir_lookup(struct inode *dir_inode, struct dentry *dentry,
+				 unsigned int flags);
+static int iterate_incfs_dir(struct file *file, struct dir_context *ctx);
+static int read_one_page(struct file *f, struct page *page);
+static ssize_t command_write(struct file *f, const char __user *buf,
+			size_t size, loff_t *offset);
+static ssize_t command_read(struct file *f, char __user *buf, size_t len,
+			    loff_t *ppos);
+static __poll_t command_poll(struct file *file, poll_table *wait);
+static int command_open(struct inode *inode, struct file *file);
+static int command_release(struct inode *, struct file *);
+
 static void kill_sb(struct super_block *sb);
+static int dentry_revalidate(struct dentry *dentry, unsigned int flags);
+static int dentry_revalidate_weak(struct dentry *dentry, unsigned int flags);
+static long dispatch_ioctl(struct file *f, unsigned int req, unsigned long arg);
+static int show_options(struct seq_file *, struct dentry *);
+static int show_devname(struct seq_file *, struct dentry *);
+
+/* State of an open .cmd file, unique for each file descriptor. */
+struct command_file_state {
+	/* A serial number of the last pending read obtained from this file. */
+	int last_pending_read_sn;
+};
 
 struct file_system_type incfs_fs_type = {
 	.owner = THIS_MODULE,
@@ -19,9 +57,785 @@ struct file_system_type incfs_fs_type = {
 	.fs_flags = 0
 };
 
+static const struct super_operations incfs_super_ops = {
+	.statfs = simple_statfs,
+	.remount_fs = remount_fs,
+	.show_options = show_options,
+	.show_devname = show_devname
+};
+
+static const struct inode_operations incfs_dir_inode_ops = {
+	.lookup = dir_lookup,
+};
+
+static const struct file_operations incfs_dir_fops = {
+	.llseek = generic_file_llseek,
+	.read = generic_read_dir,
+	.iterate = iterate_incfs_dir,
+};
+
+static const struct dentry_operations incfs_dentry_ops = {
+	.d_revalidate = dentry_revalidate,
+	.d_weak_revalidate = dentry_revalidate_weak,
+};
+
+static const struct address_space_operations incfs_address_space_ops = {
+	.readpage = read_one_page,
+};
+
+static const struct file_operations incfs_file_ops = {
+	.read_iter = generic_file_read_iter,
+	.mmap = generic_file_mmap,
+	.splice_read = generic_file_splice_read,
+	.llseek = generic_file_llseek
+};
+
+static const struct file_operations incfs_command_file_ops = {
+	.read = command_read,
+	.write = command_write,
+	.poll = command_poll,
+	.open = command_open,
+	.release = command_release,
+	.llseek = noop_llseek,
+	.unlocked_ioctl = dispatch_ioctl,
+	.compat_ioctl = dispatch_ioctl
+};
+
+static const struct inode_operations incfs_file_inode_ops = {
+	.setattr = simple_setattr,
+	.getattr = simple_getattr,
+};
+
+static const char command_file_name[] = ".cmd";
+static struct mem_range command_file_name_range = {
+	.data = (u8 *)command_file_name,
+	.len = ARRAY_SIZE(command_file_name) - 1
+};
+static struct mem_range dot_range = {
+	.data = (u8 *)".",
+	.len = 1
+};
+static struct mem_range dotdot_range = {
+	.data = (u8 *)"..",
+	.len = 2
+};
+
+enum parse_parameter { Opt_backing_fd, Opt_read_timeout, Opt_err };
+static const match_table_t option_tokens = {
+	{ Opt_backing_fd, "backing_fd=%u" },
+	{ Opt_read_timeout, "read_timeout_ms=%u" },
+	{ Opt_err, NULL }
+};
+
+static struct super_block *file_superblock(struct file *f)
+{
+	struct inode *inode;
+
+	inode = file_inode(f);
+	return inode->i_sb;
+}
+
+static struct mount_info *get_mount_info(struct super_block *sb)
+{
+	struct mount_info *result = sb->s_fs_info;
+
+	WARN_ON(!result);
+	return result;
+}
+
+static int validate_name(struct mem_range name)
+{
+	int i = 0;
+
+	if (name.len > INCFS_MAX_NAME_LEN)
+		return -ENAMETOOLONG;
+
+	if (incfs_equal_ranges(dot_range, name) ||
+	    incfs_equal_ranges(dotdot_range, name) ||
+	    incfs_equal_ranges(command_file_name_range, name))
+		return -EINVAL;
+
+	for (i = 0; i < name.len; i++)
+		if (name.data[i] == 0 || name.data[i] == '/')
+			return -EINVAL;
+
+	return 0;
+}
+
+static int read_one_page(struct file *f, struct page *page)
+{
+	loff_t offset = 0;
+	loff_t size = 0;
+	ssize_t bytes_to_read = 0;
+	ssize_t read_result = 0;
+	struct inode *inode = page->mapping->host;
+	int block_index = 0;
+	int result = 0;
+	struct data_file *df = NULL;
+	void *page_start = kmap(page);
+
+	offset = page_offset(page);
+	block_index = offset / INCFS_DATA_FILE_BLOCK_SIZE;
+	if (offset & (INCFS_DATA_FILE_BLOCK_SIZE - 1)) {
+		/*
+		 * Page offset must be a multiplier of
+		 * INCFS_DATA_FILE_BLOCK_SIZE
+		 */
+		pr_warn("incfs: Not aligned read from a file %d at offset %lld",
+			(int)inode->i_ino, offset);
+		result = -EINVAL;
+		goto out;
+	}
+
+	size = i_size_read(inode);
+	df = incfs_get_file_from_node((struct inode_info *)inode->i_private);
+	if (!df) {
+		result = -EBADF;
+		goto out;
+	}
+
+	if (offset < size) {
+		bytes_to_read = min_t(loff_t, size - offset, PAGE_SIZE);
+		read_result = incfs_read_data_file_block(
+			range(page_start, bytes_to_read), df, block_index);
+	} else {
+		bytes_to_read = 0;
+		read_result = 0;
+	}
+
+	if (read_result < 0)
+		result = read_result;
+	else if (read_result < PAGE_SIZE)
+		zero_user(page, read_result, PAGE_SIZE - read_result);
+
+out:
+	if (result == 0)
+		SetPageUptodate(page);
+	else
+		SetPageError(page);
+
+	flush_dcache_page(page);
+	kunmap(page);
+	unlock_page(page);
+	return result;
+}
+
+static long ioctl_process_instructions(struct mount_info *mi, void __user *arg)
+{
+	struct incfs_instruction inst = {};
+	int error = 0;
+	const ssize_t data_buf_size = 2 * INCFS_DATA_FILE_BLOCK_SIZE;
+	bool copy_inst_back = false;
+	struct incfs_instruction __user *inst_usr_ptr = arg;
+	u8 *data_buf = NULL;
+
+	data_buf = (u8 *)__get_free_pages(GFP_NOFS,
+					  get_order(data_buf_size));
+	if (!data_buf)
+		return -ENOMEM;
+
+	/*
+	 * Make sure that incfs_instruction doesn't have
+	 * anything beyond reserved.
+	 */
+	BUILD_BUG_ON(sizeof(struct incfs_instruction) >
+		offsetof(struct incfs_instruction, reserved) +
+		sizeof(inst.reserved));
+	if (copy_from_user(&inst, inst_usr_ptr, sizeof(inst)) > 0) {
+		error = -EINVAL;
+		goto out;
+	}
+
+	if (inst.version != INCFS_HEADER_VER)
+		return -ENOTSUPP;
+
+	switch (inst.type) {
+	case INCFS_INSTRUCTION_NEW_FILE: {
+		error = incfs_process_new_file_inst(mi, &inst.file);
+		copy_inst_back = true;
+		break;
+	}
+	case INCFS_INSTRUCTION_ADD_DIR_ENTRY:
+	case INCFS_INSTRUCTION_REMOVE_DIR_ENTRY: {
+		if (inst.dir_entry.name_len > data_buf_size) {
+			error = -E2BIG;
+			break;
+		}
+		if (copy_from_user(data_buf,
+				u64_to_user_ptr(inst.dir_entry.name),
+				inst.dir_entry.name_len)) {
+			error = -EFAULT;
+			break;
+		}
+		error = validate_name(range(data_buf,
+					inst.dir_entry.name_len));
+		if (error)
+			break;
+
+		error = incfs_process_new_dir_entry_inst(mi, inst.type,
+							&inst.dir_entry,
+							(char *)data_buf);
+		break;
+	}
+	default:
+		error = -EINVAL;
+		break;
+	}
+
+	if (!error && copy_inst_back) {
+		/*
+		 * Copy instruction back to populate _out fields.
+		 */
+		if (copy_to_user(inst_usr_ptr, &inst, sizeof(inst)))
+			error = -EFAULT;
+	}
+out:
+	if (data_buf)
+		free_pages((unsigned long)data_buf, get_order(data_buf_size));
+	return error;
+}
+
+static long dispatch_ioctl(struct file *f, unsigned int req, unsigned long arg)
+{
+	struct mount_info *mi = get_mount_info(file_superblock(f));
+
+	switch (req) {
+	case INCFS_IOC_PROCESS_INSTRUCTION:
+		return ioctl_process_instructions(mi, (void __user *)arg);
+	default:
+		return -EINVAL;
+	}
+}
+
+static int command_open(struct inode *inode, struct file *file)
+{
+	struct command_file_state *cmd_state = NULL;
+
+	cmd_state = kzalloc(sizeof(*cmd_state), GFP_NOFS);
+	if (!cmd_state)
+		return -ENOMEM;
+
+	file->private_data = cmd_state;
+	return 0;
+}
+
+static int command_release(struct inode *inode, struct file *file)
+{
+	kfree(file->private_data);
+	return 0;
+}
+
+static ssize_t command_write(struct file *f, const char __user *buf,
+			size_t size, loff_t *offset)
+{
+	struct mount_info *mi = get_mount_info(file_superblock(f));
+	const ssize_t data_buf_size = 2 * INCFS_DATA_FILE_BLOCK_SIZE;
+	size_t block_count = size / sizeof(struct incfs_new_data_block);
+	struct incfs_new_data_block __user *usr_blocks =
+				(struct incfs_new_data_block __user *)buf;
+	u8 *data_buf = NULL;
+	ssize_t error = 0;
+	int i = 0;
+
+	data_buf = (u8 *)__get_free_pages(GFP_NOFS,
+					  get_order(data_buf_size));
+	if (!data_buf)
+		return -ENOMEM;
+
+	for (i = 0; i < block_count; i++) {
+		struct incfs_new_data_block block = {};
+
+		if (copy_from_user(&block, &usr_blocks[i], sizeof(block)) > 0) {
+			error = -EFAULT;
+			break;
+		}
+
+		if (block.data_len > data_buf_size) {
+			error = -E2BIG;
+			break;
+		}
+		if (copy_from_user(data_buf, u64_to_user_ptr(block.data),
+					block.data_len) > 0) {
+			error = -EFAULT;
+			break;
+		}
+		block.data = 0; /* To make sure nobody uses it. */
+		error = incfs_process_new_data_block(mi, &block, data_buf);
+		if (error)
+			break;
+	}
+
+	if (data_buf)
+		free_pages((unsigned long)data_buf, get_order(data_buf_size));
+	*offset = 0;
+
+	/*
+	 * Only report the error if no records were processed, otherwise
+	 * just return how many were processed successfully.
+	 */
+	if (i == 0)
+		return error;
+
+	return i * sizeof(struct incfs_new_data_block);
+}
+
+static ssize_t command_read(struct file *f, char __user *buf, size_t len,
+			    loff_t *ppos)
+{
+	struct command_file_state *cmd_state = f->private_data;
+	struct mount_info *mi = get_mount_info(file_superblock(f));
+	struct incfs_pending_read_info *reads_buf = NULL;
+	size_t reads_to_collect = len / sizeof(*reads_buf);
+	int last_known_read_sn = READ_ONCE(cmd_state->last_pending_read_sn);
+	int new_max_sn = last_known_read_sn;
+	int reads_collected = 0;
+	ssize_t result = 0;
+	int i = 0;
+
+	if (!incfs_fresh_pending_reads_exist(mi, last_known_read_sn))
+		return 0;
+
+	reads_buf = (struct incfs_pending_read_info *)get_zeroed_page(
+		GFP_NOFS);
+	if (!reads_buf)
+		return -ENOMEM;
+
+	reads_to_collect = min_t(size_t, PAGE_SIZE / sizeof(*reads_buf),
+				reads_to_collect);
+
+	reads_collected = incfs_collect_pending_reads(
+		mi, last_known_read_sn, reads_buf, reads_to_collect);
+	if (reads_collected < 0) {
+		result = reads_collected;
+		goto out;
+	}
+
+	for (i = 0; i < reads_collected; i++)
+		if (reads_buf[i].serial_number > new_max_sn)
+			new_max_sn = reads_buf[i].serial_number;
+
+	/*
+	 * Just to make sure that we don't accidentally copy more data
+	 * to reads buffer than userspace can handle.
+	 */
+	reads_collected = min_t(size_t, reads_collected, reads_to_collect);
+	result = reads_collected * sizeof(*reads_buf);
+
+	/* Copy reads info to the userspace buffer */
+	if (copy_to_user(buf, reads_buf, result)) {
+		result = -EFAULT;
+		goto out;
+	}
+
+	 WRITE_ONCE(cmd_state->last_pending_read_sn, new_max_sn);
+	 *ppos = 0;
+out:
+	if (reads_buf)
+		free_page((unsigned long)reads_buf);
+	return result;
+}
+
+static __poll_t command_poll(struct file *file, poll_table *wait)
+{
+	struct command_file_state *cmd_state = file->private_data;
+	struct mount_info *mi = get_mount_info(file_superblock(file));
+	__poll_t ret = 0;
+
+	poll_wait(file, &mi->mi_pending_reads_notif_wq, wait);
+	if (incfs_fresh_pending_reads_exist(mi,
+		cmd_state->last_pending_read_sn))
+		ret = EPOLLIN | EPOLLRDNORM;
+
+	return ret;
+}
+
+static struct timespec64 backing_file_time(struct super_block *sb)
+{
+	struct timespec64 zero_time = { .tv_sec = 0, .tv_nsec = 0 };
+	struct mount_info *mi = get_mount_info(sb);
+	struct inode *backing_inode = NULL;
+
+	backing_inode = file_inode(mi->mi_bf_context->bc_file);
+	if (!backing_inode)
+		return zero_time;
+	return backing_inode->i_ctime;
+}
+
+static struct inode *get_inode_for_incfs_node(struct super_block *sb,
+					      struct inode_info *n_info)
+{
+	unsigned long ino = n_info->n_ino;
+	struct inode *inode = iget_locked(sb, ino);
+
+	if (!inode)
+		return NULL;
+
+	if (inode->i_state & I_NEW) {
+		inode->i_ctime = backing_file_time(sb);
+		inode->i_mtime = inode->i_ctime;
+		inode->i_atime = inode->i_ctime;
+		inode->i_ino = ino;
+		inode->i_private = n_info;
+		inode_init_owner(inode, NULL, n_info->n_mode);
+
+		switch (n_info->n_type) {
+		case INCFS_NODE_FILE: {
+			struct data_file *df = incfs_get_file_from_node(n_info);
+
+			inode->i_size = df->df_size;
+			inode->i_blocks = df->df_block_count;
+			inode->i_mapping->a_ops = &incfs_address_space_ops;
+			inode->i_op = &incfs_file_inode_ops;
+			inode->i_fop = &incfs_file_ops;
+			break;
+		}
+		case INCFS_NODE_DIR:
+			inode->i_size = 0;
+			inode->i_blocks = 1;
+			inode->i_mapping->a_ops = &incfs_address_space_ops;
+			inode->i_op = &incfs_dir_inode_ops;
+			inode->i_fop = &incfs_dir_fops;
+			break;
+
+			break;
+		default:
+			pr_warn("incfs: Unknown inode type");
+			break;
+		}
+
+		unlock_new_inode(inode);
+	}
+
+	return inode;
+}
+
+static struct inode *get_inode_for_commands(struct super_block *sb)
+{
+	struct inode *inode = iget_locked(sb, INCFS_COMMAND_INODE);
+
+	if (!inode)
+		return NULL;
+
+	if (inode->i_state & I_NEW) {
+		inode->i_ctime = backing_file_time(sb);
+		inode->i_mtime = inode->i_ctime;
+		inode->i_atime = inode->i_ctime;
+		inode->i_size = 0;
+		inode->i_ino = INCFS_COMMAND_INODE;
+		inode->i_private = NULL;
+
+		inode_init_owner(inode, NULL, S_IFREG | READ_WRITE_FILE_MODE);
+
+		inode->i_op = &incfs_file_inode_ops;
+		inode->i_fop = &incfs_command_file_ops;
+
+		unlock_new_inode(inode);
+	}
+
+	return inode;
+}
+
+static int iterate_incfs_dir(struct file *file, struct dir_context *ctx)
+{
+	struct inode *inode = file_inode(file);
+	struct directory *dir = NULL;
+	struct mount_info *mi = NULL;
+	struct dir_entry_info *entry;
+	loff_t entries_found = 0;
+	loff_t aux_entries_count = 2; // 2 for "." and ".."
+
+	dir = incfs_get_dir_from_node((struct inode_info *)inode->i_private);
+	if (!dir)
+		return -EFAULT;
+
+	if (!dir_emit_dots(file, ctx))
+		return 0;
+
+	mi = dir->d_node.n_mount_info;
+	if (ctx->pos == 2 && dir->d_node.n_ino == INCFS_ROOT_INODE) {
+		if (!dir_emit(ctx, command_file_name,
+			      ARRAY_SIZE(command_file_name) - 1,
+			      INCFS_COMMAND_INODE, DT_REG))
+			return 0;
+		ctx->pos++;
+		aux_entries_count++; //Aux entry for the .cmd file
+	}
+
+	mutex_lock(&mi->mi_dir_ops_mutex);
+	list_for_each_entry(entry, &dir->d_entries_head, de_entries_list) {
+		unsigned int type = (entry->de_child->n_type == INCFS_NODE_DIR)
+					? DT_DIR : DT_REG;
+
+		entries_found++;
+		if (entries_found > ctx->pos - aux_entries_count) {
+			if (!dir_emit(ctx, entry->de_name.data,
+					entry->de_name.len,
+					entry->de_child->n_ino, type))
+				break;
+			ctx->pos++;
+		}
+	}
+	mutex_unlock(&mi->mi_dir_ops_mutex);
+	return 0;
+}
+
+static struct dentry *dir_lookup(struct inode *dir_inode, struct dentry *dentry,
+				 unsigned int flags)
+{
+	struct inode *result = NULL;
+	struct super_block *sb = dir_inode->i_sb;
+	struct mount_info *mi = get_mount_info(sb);
+	int dir_ver = 0;
+	struct mem_range name_rng = range((u8 *)dentry->d_name.name,
+						dentry->d_name.len);
+
+	if (incfs_equal_ranges(dot_range, name_rng))
+		result = dir_inode;
+	else if (incfs_equal_ranges(dotdot_range, name_rng)) {
+		struct directory *parent_dir = NULL;
+
+		mutex_lock(&mi->mi_nodes_mutex);
+		parent_dir = incfs_get_dir_by_ino(mi, parent_ino(dentry));
+		if (parent_dir)
+			result = get_inode_for_incfs_node(sb,
+							&parent_dir->d_node);
+		mutex_unlock(&mi->mi_nodes_mutex);
+	} else if (incfs_equal_ranges(command_file_name_range, name_rng)) {
+		result = get_inode_for_commands(sb);
+	} else {
+		struct directory *dir = NULL;
+		struct inode_info *n_info = NULL;
+
+		mutex_lock(&mi->mi_nodes_mutex);
+		dir = incfs_get_dir_from_node(
+			(struct inode_info *)dir_inode->i_private);
+		n_info = incfs_get_node_by_name(dir, dentry->d_name.name,
+						&dir_ver);
+		if (n_info)
+			result = get_inode_for_incfs_node(sb, n_info);
+
+		mutex_unlock(&mi->mi_nodes_mutex);
+	}
+	dentry->d_fsdata = (void *)(long)dir_ver;
+	d_add(dentry, result);
+	return NULL;
+}
+
+static int parse_options(struct mount_options *opts, char *str)
+{
+	substring_t args[MAX_OPT_ARGS];
+	int value;
+	char *position;
+
+	if (opts == NULL)
+		return -EFAULT;
+
+	opts->backing_fd = 0;
+	opts->read_timeout_ms = 1000; /* Default: 1s */
+	if (str == NULL || *str == 0)
+		return 0;
+
+	while ((position = strsep(&str, ",")) != NULL) {
+		int token;
+
+		if (!*position)
+			continue;
+
+		token = match_token(position, option_tokens, args);
+
+		switch (token) {
+		case Opt_backing_fd:
+			if (match_int(&args[0], &value))
+				return -EINVAL;
+			opts->backing_fd = value;
+			break;
+		case Opt_read_timeout:
+			if (match_int(&args[0], &value))
+				return -EINVAL;
+			opts->read_timeout_ms = value;
+			break;
+		default:
+			return -EINVAL;
+		}
+	}
+
+	return 0;
+}
+
+static int remount_fs(struct super_block *sb, int *flags, char *data)
+{
+	struct mount_info *mi = get_mount_info(sb);
+	struct mount_options options;
+	int err = 0;
+
+	sync_filesystem(sb);
+	err = parse_options(&options, (char *)data);
+	if (err)
+		return err;
+
+	if (mi->mi_options.read_timeout_ms != options.read_timeout_ms) {
+		mi->mi_options.read_timeout_ms = options.read_timeout_ms;
+		pr_info("New Incremental-fs timeout_ms=%d",
+			options.read_timeout_ms);
+	}
+
+	return 0;
+}
+
+static int dentry_revalidate(struct dentry *dentry, unsigned int flags)
+{
+	int dentry_ver = (int)(long)dentry->d_fsdata;
+	struct inode *inode = NULL;
+	struct dentry *parent = NULL;
+	struct directory *parent_dir = NULL;
+
+	if (flags & LOOKUP_RCU)
+		return -ECHILD;
+
+	parent = dget_parent(dentry);
+	parent_dir = incfs_get_dir_from_node((struct inode_info *)
+						d_inode(parent)->i_private);
+	dput(parent);
+
+	if (!parent_dir)
+		return 0;
+
+	/*
+	 * Reload globally visible parent dir version. If it hasn't changed
+	 * since the dentry had been created, it must be still valid.
+	 */
+	smp_mb__before_atomic();
+	if (dentry_ver == atomic_read(&parent_dir->d_version))
+		return 1;
+
+	/* Root dentry is always valid. */
+	inode = d_inode(dentry);
+	if (inode && inode->i_ino == INCFS_ROOT_INODE)
+		return 1;
+
+	return 0;
+}
+
+static int dentry_revalidate_weak(struct dentry *dentry, unsigned int flags)
+{
+	/*
+	 * Weak version of revalidate only needs to make sure that inode
+	 * is still okay. Incremental-fs never deletes inodes, so no need
+	 * for extra steps here.
+	 */
+	struct inode *inode = d_inode(dentry);
+
+	if (!inode || !inode->i_private)
+		return 0;
+	return 1;
+}
+
 static int fill_super_block(struct super_block *sb, void *data, int silent)
 {
+	struct mount_options options;
+	struct inode *inode = NULL;
+	struct mount_info *mi = NULL;
+	struct file *backing_file = NULL;
+	const char *file_name = NULL;
+	int result = 0;
+
+	sb->s_op = &incfs_super_ops;
+	sb->s_d_op = &incfs_dentry_ops;
+	sb->s_flags |= S_NOATIME;
+	sb->s_magic = INCFS_MAGIC_NUMBER;
+	sb->s_time_gran = 1;
+	sb->s_blocksize = INCFS_DATA_FILE_BLOCK_SIZE;
+	sb->s_blocksize_bits = blksize_bits(sb->s_blocksize);
+	sb->s_maxbytes = MAX_LFS_FILESIZE;
+
+	BUILD_BUG_ON(PAGE_SIZE != INCFS_DATA_FILE_BLOCK_SIZE);
+
+	result = parse_options(&options, (char *)data);
+	if (result != 0)
+		goto err;
+
+	if (options.backing_fd == 0) {
+		pr_err("Backing FD not set, filesystem can't be mounted.");
+		result = -EBADFD;
+		goto err;
+	}
+
+	backing_file = fget(options.backing_fd);
+	if (!backing_file) {
+		pr_err("Invalid backing FD: %d", options.backing_fd);
+		result = -EBADFD;
+		goto err;
+	}
+
+	mi = incfs_alloc_mount_info(sb, backing_file);
+	if (IS_ERR_OR_NULL(mi)) {
+		result = PTR_ERR(mi);
+		mi = NULL;
+		goto err;
+	}
+
+	mi->mi_options = options;
+	sb->s_fs_info = mi;
+	file_name = mi->mi_bf_context->bc_file->f_path.dentry->d_name.name;
+
+	inode = new_inode(sb);
+	if (inode) {
+		inode->i_ino = INCFS_ROOT_INODE;
+		inode->i_ctime = backing_file_time(sb);
+		inode->i_mtime = inode->i_ctime;
+		inode->i_atime = inode->i_ctime;
+		inode->i_private = &mi->mi_root.d_node;
+
+		inode->i_op = &incfs_dir_inode_ops;
+		inode->i_fop = &incfs_dir_fops;
+
+		inode_init_owner(inode, NULL, S_IFDIR | READ_EXEC_FILE_MODE);
+	}
+
+	sb->s_root = d_make_root(inode);
+	if (!sb->s_root) {
+		result = -ENOMEM;
+		goto err;
+	}
+
+	if (incfs_get_end_offset(mi->mi_bf_context->bc_file) > 0) {
+		int found_mds = 0;
+
+		/*
+		 * Backing file has data,
+		 * let's try to interpret it as inc-fs image.
+		 */
+		found_mds = incfs_scan_backing_file(mi);
+		if (found_mds < 0) {
+			result = found_mds;
+			pr_err("Backing file '%s' scan error: %d",
+				file_name, -result);
+			goto err;
+		}
+	} else {
+		/*
+		 * No data in the backing file,
+		 * let's initialize a new image.
+		 */
+		result = incfs_make_empty_backing_file(mi->mi_bf_context);
+		if (result < 0) {
+			pr_err("Backing file '%s' initialization error: %d",
+				file_name, -result);
+			goto err;
+		}
+	}
 	return 0;
+err:
+	sb->s_fs_info = NULL;
+	incfs_free_mount_info(mi);
+	if (!mi && backing_file) {
+		/*
+		 * Close backing_file only if mount_info was never created.
+		 * Otherwise it's closed in incfs_free_mount_info.
+		 */
+		fput(backing_file);
+	}
+	return result;
 }
 
 static struct dentry *mount_fs(struct file_system_type *type, int flags,
@@ -32,6 +846,26 @@ static struct dentry *mount_fs(struct file_system_type *type, int flags,
 
 static void kill_sb(struct super_block *sb)
 {
+	struct mount_info *mi = sb->s_fs_info;
+
+	incfs_free_mount_info(mi);
 	generic_shutdown_super(sb);
 }
 
+static int show_devname(struct seq_file *m, struct dentry *root)
+{
+	struct mount_info *mi = get_mount_info(root->d_sb);
+	const char *backing_file =
+			mi->mi_bf_context->bc_file->f_path.dentry->d_name.name;
+
+	seq_puts(m, backing_file);
+	return 0;
+}
+
+static int show_options(struct seq_file *m, struct dentry *root)
+{
+	struct mount_info *mi = get_mount_info(root->d_sb);
+
+	seq_printf(m, ",read_timeout_ms=%u", mi->mi_options.read_timeout_ms);
+	return 0;
+}

--
2.21.0.593.g511ec345e18-goog

#10 lore raw

PATCH 6/6 incfs: Integration tests for incremental-fs

In reply to [email protected]

From: Eugene Zemtsov <[email protected]>

Testing main use cases for Incremental FS. Things like:
- interaction between consuments and producers
- basic dir operations
- mounting a backing file with existing data

---
 tools/testing/selftests/Makefile              |    1 +
 .../selftests/filesystems/incfs/.gitignore    |    1 +
 .../selftests/filesystems/incfs/Makefile      |   12 +
 .../selftests/filesystems/incfs/config        |    1 +
 .../selftests/filesystems/incfs/incfs_test.c  | 1603 +++++++++++++++++
 .../selftests/filesystems/incfs/utils.c       |  159 ++
 .../selftests/filesystems/incfs/utils.h       |   39 +
 7 files changed, 1816 insertions(+)
 create mode 100644 tools/testing/selftests/filesystems/incfs/.gitignore
 create mode 100644 tools/testing/selftests/filesystems/incfs/Makefile
 create mode 100644 tools/testing/selftests/filesystems/incfs/config
 create mode 100644 tools/testing/selftests/filesystems/incfs/incfs_test.c
 create mode 100644 tools/testing/selftests/filesystems/incfs/utils.c
 create mode 100644 tools/testing/selftests/filesystems/incfs/utils.h
tools/testing/selftests/Makefile +1 -0
index 971fc8428117..78fd8590cede 100644
@@ -11,6 +11,7 @@ TARGETS += efivarfs
 TARGETS += exec
 TARGETS += filesystems
 TARGETS += filesystems/binderfs
+TARGETS += filesystems/incfs
 TARGETS += firmware
 TARGETS += ftrace
 TARGETS += futex
tools/testing/selftests/filesystems/incfs/.gitignore new file +1 -0
new file mode 100644
index 000000000000..4cba9c219a92
@@ -0,0 +1 @@
+incfs_test
\ No newline at end of file
tools/testing/selftests/filesystems/incfs/Makefile new file +12 -0
new file mode 100644
index 000000000000..493efc23fa33
@@ -0,0 +1,12 @@
+# SPDX-License-Identifier: GPL-2.0
+CFLAGS += -D_FILE_OFFSET_BITS=64 -D_GNU_SOURCE -Wall
+CFLAGS += -I../../../../../usr/include/
+CFLAGS += -I../../../../include/uapi/
+CFLAGS += -I../../../../lib
+
+EXTRA_SOURCES := utils.c ../../../../lib/lz4.c
+TEST_GEN_PROGS := incfs_test
+
+include ../../lib.mk
+
+$(OUTPUT)/incfs_test: incfs_test.c $(EXTRA_SOURCES)
tools/testing/selftests/filesystems/incfs/config new file +1 -0
new file mode 100644
index 000000000000..b6749837a318
@@ -0,0 +1 @@
+CONFIG_INCREMENTAL_FS=y
\ No newline at end of file
tools/testing/selftests/filesystems/incfs/incfs_test.c new file +1603 -0

1,603 lines not on this page · raw message

tools/testing/selftests/filesystems/incfs/utils.c new file +159 -0

159 lines not on this page · raw message

tools/testing/selftests/filesystems/incfs/utils.h new file +39 -0
new file mode 100644
index 000000000000..c3423fe01857
@@ -0,0 +1,39 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Copyright 2019 Google LLC
+ */
+#include <stdbool.h>
+#include <sys/stat.h>
+
+#include "../../include/uapi/linux/incrementalfs.h"
+
+#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
+
+#ifdef __LP64__
+#define ptr_to_u64(p) ((__u64)p)
+#else
+#define ptr_to_u64(p) ((__u64)(__u32)p)
+#endif
+
+int mount_fs(char *mount_dir, int backing_fd, int read_timeout_ms);
+
+int send_md_instruction(int cmd_fd, struct incfs_instruction *inst);
+
+int emit_node(int fd, char *filename, int *ino_out, int parent_ino,
+		size_t size, mode_t mode);
+
+int emit_dir(int fd, char *filename, int *ino_out, int parent_ino);
+
+int emit_file(int fd, char *filename, int *ino_out, int parent_ino,
+		size_t size);
+
+int unlink_node(int fd, int parent_ino, char *filename);
+
+loff_t get_file_size(char *name);
+
+int open_commands_file(char *mount_dir);
+
+int wait_for_pending_reads(int fd, int timeout_ms,
+	struct incfs_pending_read_info *prs, int prs_count);
+
+char *concat_file_name(char *dir, char *file);

--
2.21.0.593.g511ec345e18-goog

#11 lore raw
In reply to [email protected]
Quoted 13 lines · On Thu, May 2, 2019 at 12:04 AM <[email protected]> wrote:

Hi All,

Please take a look at Incremental FS.

Incremental FS is special-purpose Linux virtual file system that allows execution of a program while its binary and resource files are still being lazily downloaded over the network, USB etc. It is focused on incremental delivery for a small number (under 100) of big files (more than 10 megabytes each). Incremental FS doesn’t allow direct writes into files and, once loaded, file content never changes. Incremental FS doesn’t use a block device, instead it saves data into a backing file located on a regular file-system.

Quoted 6 lines

What’s it for?

It allows running big Android apps before their binaries and resources are fully loaded to an Android device. If an app reads something not loaded yet, it needs to wait for the data block to be fetched, but in most cases hot blocks can be loaded in advance and apps can run smoothly and almost instantly.

This sounds very useful.

Why does it have to be a new special-purpose Linux virtual file? Why not FUSE, which is meant for this purpose?
Those are things that you should explain when you are proposing a new filesystem,
but I will answer for you - because FUSE page fault will incur high latency also after
blocks are locally available in your backend store. Right?

How about fscache support for FUSE then?
You can even write your own fscache backend if the existing ones don't fit your needs for some reason.

Do you know of the project https://vfsforgit.org/?
Not exactly the same use case but very similar. There is ongoing work on a Linux port developed by GitHub.com:
https://github.com/github/libprojfs

Piling logic into the kernel is not the answer. Adding the missing interfaces to the kernel is the answer.

Thanks,
Amir.

#12 lore raw
Quoted 10 lines · Amir Goldstein

This sounds very useful.

Why does it have to be a new special-purpose Linux virtual file? Why not FUSE, which is meant for this purpose?
Those are things that you should explain when you are proposing a new filesystem,
but I will answer for you - because FUSE page fault will incur high latency also after
blocks are locally available in your backend store. Right?

From the documentation file in the first patch:

+Why isn't incremental-fs implemented via FUSE?
+----------------------------------------------
+TLDR: FUSE-based filesystems add 20-80% of performance overhead for target +scenarios, and increase power use on mobile beyond acceptable limit +for widespread deployment. A custom kernel filesystem is the way to overcome +these limitations.
+

There are several paragraphs of more detail which I leave for the interested reader to review....

- Ted

maintainer
#13 lore raw
Quoted 10 lines · Theodore Ts'o
(quoted diff) +7 -0
+Why isn't incremental-fs implemented via FUSE?
+----------------------------------------------
+TLDR: FUSE-based filesystems add 20-80% of performance overhead for target
+scenarios, and increase power use on mobile beyond acceptable limit
+for widespread deployment. A custom kernel filesystem is the way to overcome
+these limitations.
+

There are several paragraphs of more detail which I leave for the interested reader to review....

Why not CODA, though, with local fs as cache?

#14 lore raw
Quoted 2 lines · Al Viro

Why not CODA, though, with local fs as cache?

Quoted 11 lines · Amir Goldstein

This sounds very useful.

Why does it have to be a new special-purpose Linux virtual file? Why not FUSE, which is meant for this purpose?
Those are things that you should explain when you are proposing a new filesystem,
but I will answer for you - because FUSE page fault will incur high latency also after
blocks are locally available in your backend store. Right?

Quoted 7 lines

How about fscache support for FUSE then?
You can even write your own fscache backend if the existing ones don't fit your needs for some reason.

Piling logic into the kernel is not the answer. Adding the missing interfaces to the kernel is the answer.

Thanks for the interest and feedback. What I dreaded most was silence.

Probably I should have given a bit more details in the introductory email. Important features we’re aiming for:

1. An attempt to read a missing data block gives a userspace data loader a chance to fetch it. Once a block is loaded (in advance or after a page fault) it is saved into a local backing storage and following reads of the same block are done directly by the kernel. [Implemented]

2. Block level compression. It saves space on a device, while still allowing very granular loading and mapping. Less granular compression would trigger loading of more data than absolutely necessary, and that’s the thing we want to avoid. [Implemented]

3. Block level integrity verification. The signature scheme is similar to DMverity or fs-verity. In other words, each file has a Merkle tree with crypto-digests of 4KB blocks. The root digest is signed with RSASSA or ECDSA. Each time a data block is read digest is calculated and checked with the Merkle tree, if the signature check fails the read operation fails as well. Ideally I’d like to use fs-verity API for that. [Not implemented yet.]

4. New files can be pushed into incremental-fs “externally” when an app needs a new resource or a binary. This is needed for situations when a new resource or a new version of code is available, e.g. a user just changed the system language to Spanish, or a developer rolled out an app update. Things change over time and this means that we can’t just incrementally
load a precooked ext4 image and mount it via a loopback device. [Implemented]

5. No need to support writes or file resizing. It eliminates a lot of complexity.

Currently not all of these features are implemented yet, but they all will be needed to achieve our goals:
- Apps can be delivered incrementally without having to wait for extra data. At the same time given enough time the app can be downloaded fully without having to keep a connection open after that.
- App’s integrity should be verifiable without having to read all its blocks.
- Local storage and battery need to be conserved.
- Apps binaries and resources can change over time.
Such changes are triggered by external events.

I’d like to comment on proposed alternative solutions:

FUSE
We have a FUSE based prototype and though functional it turned out to be battery hungry and read performance leaving much to be desired.
Our measurements were roughly corresponding to results in the article I link in PATCH 1 incrementalfs.rst

In this thread Amir Goldstein absolutely correctly pointed out that FUSE’s constant overhead keeps hurting app’s performance even when all blocks are available locally. But not only that, FUSE needs to be involved with each readdir() and stat() call. And to our surprise we learned that many apps do directory traversals and stat()-s much more often that it seems reasonable.

Moreover, Android has a bit of a recent history with FUSE. A big chunk of Android directory tree (“external storage”) use to be mounted via FUSE. It didn’t turn out to be a great approach and it was eventually replaced by a kernel module.

I reckon the amount of changes that we’d need to introduce to FUSE in order to make it support things mentioned above will be, to put it mildly, very substantial. And having to be as generic as FUSE (i.e. support writes etc) will make the task much more complicated than it is now.

Coda
Indeed it is somewhat similar to what we need. But according to Coda’s documentation it fetches a whole file first time it is accessed, which is opposite of what we need. It is not really obvious that adding all the things above to Coda would be simpler than creating a separate driver. Especially if Coda needs to keep supporting all of its existing features.

userfaultfd
As far as I can see this would only work for mmap-ed files. All read() and readdir() calls would never return right results.

Signature · 2 lines
Thanks,
Eugene Zemtsov.
#15 lore raw
Quoted 57 lines · Eugene Zemtsov
Quoted 2 lines · Al Viro

Why not CODA, though, with local fs as cache?

Quoted 11 lines · Amir Goldstein

This sounds very useful.

Why does it have to be a new special-purpose Linux virtual file? Why not FUSE, which is meant for this purpose?
Those are things that you should explain when you are proposing a new filesystem,
but I will answer for you - because FUSE page fault will incur high latency also after
blocks are locally available in your backend store. Right?

Quoted 7 lines

How about fscache support for FUSE then?
You can even write your own fscache backend if the existing ones don't fit your needs for some reason.

Piling logic into the kernel is not the answer. Adding the missing interfaces to the kernel is the answer.

Thanks for the interest and feedback. What I dreaded most was silence.

Probably I should have given a bit more details in the introductory email. Important features we’re aiming for:

1. An attempt to read a missing data block gives a userspace data loader a chance to fetch it. Once a block is loaded (in advance or after a page fault) it is saved into a local backing storage and following reads of the same block are done directly by the kernel. [Implemented]

2. Block level compression. It saves space on a device, while still allowing very granular loading and mapping. Less granular compression would trigger loading of more data than absolutely necessary, and that’s the thing we want to avoid. [Implemented]

3. Block level integrity verification. The signature scheme is similar to DMverity or fs-verity. In other words, each file has a Merkle tree with crypto-digests of 4KB blocks. The root digest is signed with RSASSA or ECDSA. Each time a data block is read digest is calculated and checked with the Merkle tree, if the signature check fails the read operation fails as well. Ideally I’d like to use fs-verity API for that. [Not implemented yet.]

4. New files can be pushed into incremental-fs “externally” when an app needs a new resource or a binary. This is needed for situations when a new resource or a new version of code is available, e.g. a user just changed the system language to Spanish, or a developer rolled out an app update. Things change over time and this means that we can’t just incrementally
load a precooked ext4 image and mount it via a loopback device. [Implemented]

5. No need to support writes or file resizing. It eliminates a lot of complexity.

Quoted 10 lines

Currently not all of these features are implemented yet, but they all will be needed to achieve our goals:
- Apps can be delivered incrementally without having to wait for extra data. At the same time given enough time the app can be downloaded fully without having to keep a connection open after that.
- App’s integrity should be verifiable without having to read all its blocks.
- Local storage and battery need to be conserved.
- Apps binaries and resources can change over time.
Such changes are triggered by external events.

This really sounds to me like the properties of a network filesystem with local cache. It seems that you did a thorough research, but I am not sure that you examined the fscache option properly. Remember, if an existing module does not meet your needs, it does not mean that creating a new module is the right answer. It may be that extending an existing module is something that everyone, including yourself will benefit from.

Quoted 8 lines

I’d like to comment on proposed alternative solutions:

FUSE
We have a FUSE based prototype and though functional it turned out to be battery hungry and read performance leaving much to be desired.
Our measurements were roughly corresponding to results in the article I link in PATCH 1 incrementalfs.rst

Quoted 6 lines

In this thread Amir Goldstein absolutely correctly pointed out that FUSE’s constant overhead keeps hurting app’s performance even when all blocks are available locally. But not only that, FUSE needs to be involved with each readdir() and stat() call. And to our surprise we learned that many apps do directory traversals and stat()-s much more often that it seems reasonable.

That is a real problem. Alas readdir cache, recently added probably solves your problem since your directory changes are infrequent.
stat cache also exists, but will be used depending on policy of mount options. I am sure you can come up with caching policy that will meet your needs and AFAIK FUSE protocol supports invalidating cache entries from server (i.e. on "external" changes).

Quoted 5 lines

Moreover, Android has a bit of a recent history with FUSE. A big chunk of Android directory tree (“external storage”) use to be mounted via FUSE. It didn’t turn out to be a great approach and it was eventually replaced by a kernel module.

I am aware of that history.
I suspect the decision to write sdcardfs followed similar logic to the one that has lead you to write incfs.

Quoted 5 lines

I reckon the amount of changes that we’d need to introduce to FUSE in order to make it support things mentioned above will be, to put it mildly, very substantial. And having to be as generic as FUSE (i.e. support writes etc) will make the task much more complicated than it is now.

Maybe. We won't know until you explore this option. Will we?

Thanks,
Amir.

#16 lore raw
Quoted 11 lines

This really sounds to me like the properties of a network filesystem with local cache. It seems that you did a thorough research, but I am not sure that you examined the fscache option properly. Remember, if an existing module does not meet your needs, it does not mean that creating a new module is the right answer. It may be that extending an existing module is something that everyone, including yourself will benefit from.

I am sure you can come up with caching policy that will meet your needs and AFAIK FUSE protocol supports invalidating cache entries from server (i.e. on "external" changes).

You’re right. On a very high level it looks quite plausible that incfs can be replaced by a combination of
1. fscache interface change to accomodate compression, hashes etc
2. a new fscache backend
3. a FUSE change, that would allow FUSE to load data to fscache and server data from directly fscache.

After it is all done, FUSE and fscache will have more features and support more use cases for years to come. But this approach is not without tradeoffs, features
increase support burden and FUSE interface changes are almost impossible to deprecate.

On the other hand we have a simple self-contained module, which handles incremental app loading for Android. All in all, incfs currently has about 6KLOC,
where only 3.5KLOC is actual kernel code. It is not likely to be used “as is” for other purposes, but it doesn’t increase already significant complexity of fscache, FUSE, and VFS. People working with those components won’t need to fret about extra hooks and corner cases created for incremental app loading. If for some reason incfs doesn’t gain wide adoption, it can be relatively painlessly removed from the kernel.

Having a standalone module is very important for me on a yet another level. It helps in porting it to older kernels. Patches scattered across fs/ substree will be less portable and self contained. (BTW this is the reason to have a version file in sysfs - new versions of incfs can be backported to older kernels.)

Hopefully this will clarify why I think that VFS interface is the right boundary for incremental-fs. It is sufficiently low-level to achieve all goals of incremental app loading, but at the same time sufficiently isolated not to meddle with the rest of the kernel.

Thoughts?

Thanks,
Eugene.

#17 lore raw
Quoted 26 lines · Eugene Zemtsov
Quoted 9 lines

This really sounds to me like the properties of a network filesystem with local cache. It seems that you did a thorough research, but I am not sure that you examined the fscache option properly. Remember, if an existing module does not meet your needs, it does not mean that creating a new module is the right answer. It may be that extending an existing module is something that everyone, including yourself will benefit from.

Quoted 3 lines

I am sure you can come up with caching policy that will meet your needs and AFAIK FUSE protocol supports invalidating cache entries from server (i.e. on "external" changes).

You’re right. On a very high level it looks quite plausible that incfs can be replaced by a combination of
1. fscache interface change to accomodate compression, hashes etc
2. a new fscache backend
3. a FUSE change, that would allow FUSE to load data to fscache and server data from directly fscache.

After it is all done, FUSE and fscache will have more features and support more use cases for years to come. But this approach is not without tradeoffs, features
increase support burden and FUSE interface changes are almost impossible to deprecate.

Quoted 10 lines

On the other hand we have a simple self-contained module, which handles incremental app loading for Android. All in all, incfs currently has about 6KLOC,
where only 3.5KLOC is actual kernel code. It is not likely to be used “as is” for other purposes, but it doesn’t increase already significant complexity of fscache, FUSE, and VFS. People working with those components won’t need to fret about extra hooks and corner cases created for incremental app loading. If for some reason incfs doesn’t gain wide adoption, it can be relatively painlessly removed from the kernel.

If you add NEW fscache APIs you won't risk breaking the old ones. You certainly won't make VFS more complex because you won't be changing VFS.
You know what, even if you do submit incfs a new user space fs, without FUSE, I'd rather that you used fscache frontend/backend design, so that at least it will
make it easier for someone else in the community to take the backend parts and add fronend support to FUSE or any other network fs.

And FYI, since fscache is an internal kernel API, the NEW interfaces could be just as painlessly removed if the incfs *backend* doesn't gain any adoption.

Quoted 6 lines

Having a standalone module is very important for me on a yet another level. It helps in porting it to older kernels. Patches scattered across fs/ substree will be less portable and self contained. (BTW this is the reason to have a version file in sysfs - new versions of incfs can be backported to older kernels.)

Quoted 7 lines

Hopefully this will clarify why I think that VFS interface is the right boundary for incremental-fs. It is sufficiently low-level to achieve all goals of incremental app loading, but at the same time sufficiently isolated not to meddle with the rest of the kernel.

Thoughts?

I think you have made the right choice for you and for the product you are working on to use an isolated module to provide this functionality.

But I assume the purpose of your posting was to request upstream inclusion, community code review, etc. This is not likely to happen when the implementation and design choices are derived from Employer needs vs. the community needs. Sure, you can get high level design review, which is what *this* is, but I recon not much more.

This discussion has several references to community projects that can benefit from this functionality, but not in its current form.

This development model has worked well in the past for Android and the Android user base leverage could help to get you a ticket to staging, but eventually, those modules (e.g. ashmem) often do get replaced with more community oriented APIs.

Thanks,
Amir.

A message that is not in the archive (sent off-list or not yet received): CAK8JDrEQnXTcCtAPkb+S4r4hORiKh_yX=0A0A=LYSVKUo_n4OA@mail.gmail.com

#19 lore raw
Quoted 10 lines · Amir Goldstein

I think you have made the right choice for you and for the product you are working on to use an isolated module to provide this functionality.

But I assume the purpose of your posting was to request upstream inclusion, community code review, etc. This is not likely to happen when the implementation and design choices are derived from Employer needs vs. the community needs. Sure, you can get high level design review, which is what *this* is, but I recon not much more.

Quoted 8 lines

This discussion has several references to community projects that can benefit from this functionality, but not in its current form.

This development model has worked well in the past for Android and the Android user base leverage could help to get you a ticket to staging, but eventually, those modules (e.g. ashmem) often do get replaced with more community oriented APIs.

Hi fsdevel
I'm Yurii, and I work with Eugene on the same team and the same project.

I want to explain how we ended up with a custom filesystem instead of trying to improve FUSE for everyone, and
why we think (maybe incorrectly) that it may be still pretty useful for the community.
As the project goal was to allow instant (-ish) deployment of apps from the dev environment to Android phone, we were hoping to stick with plain FUSE filesystem, and that's what we've done at first. But it turned out that even with the best tuning it was still really slow and battery-hungry (phones spent energy faster than they were charging over the cord).
At this point we've already collected the profiles for the filesystem usage, and also figured out what features are essential
to make it usable for streaming:
1. Random reads are the most common -> 4kb-sized read is the size we have to support, and may not go to usermode on each of those
2. Android tends to list the app directory and stat files in it often -> these operations need to be cached in kernel as well
3. Because of *random* reads streaming files sequentially isn't optimal -> need to be able to collect read logs from first deployment and stream in that order next time on incremental builds
4. Devices have small flash cards, need to deploy uncompressed game images for speed and mmap access ->
support storing 4kb blocks compressed
4.1. Host computer is much better at compression -> support streaming compressed blocks into the filesystem storage directly, without
recompression on the phone
5. Android has to verify app signature for installation -> need to support per-block signing and lazy verification
5.1. For big games even per-block signature data can be huge, so need to stream even the signatures
6. Development cycle is usually edit-build-try-edit-... -> need to support delta-patches from existing files
7. File names for installed apps are standard and different from what they were on the host ->
must be able to store user-supplied 'key' next to each file to identify it
8. Files never change -> no need to have complex code for mutable data in the filesystem

In the end, we saw only two ways how to make all of this work: either take sdcardfs as a base and extend it, or change FUSE to support cache in kernel; and as you can imagine, sdcardfs route got thrown out of the window immediately after looking at the code. But after learning some FUSE internals and its code what we found out is that to make it do all the listed things we'd basically have to implement a totally new filesystem inside of it. The only real use of FUSE that remained was to send FUSE_INIT, and occasional read requests. Everything else required, first of all, making a cache object inside FUSE intercept every message before it goes to the user mode, and also adding new specialized commands initiated by the usermode (e.g. prefetching data that hasn't been requested yet, or streaming hashes in). Some things even didn't make sense for a generic usecase (e.g. having a limited circular buffer of read blocks in kernel that user can ask for and flush).

In the end, after several tries we just came to a conclusion that the very set of original requirements is so specific that, funny enough, anyone who wants to create a lazy-loading experience would hit most of them, while anyone who's doing something else, would miss most of them. That's the main reason to go with a separate specialized driver module, and the reason to share it with the community - we have a feeling that people will benefit from a high-quality implementation of lazy loading in kernel, and we will benefit from the community support and guiding.

Again, we all are human and can be wrong at any step when making conclusions. E.g. we didn't know about the fscache subsystem, and were only planning to create a cache object inside FUSE instead. But for now I still feel that our original research stands, and that in the long run specialized filesystem serves its users much better than several scattered changes in other places that all pretty much look like the same filesystem split into three parts and adopted to the interfaces those places force onto it. Even more, those changes and interfaces look quite strange on their own, when not used together.

Please tell me what you think about this whole thing. We do care about the feature in general, not about making it
look as we've coded it right now. If you feel that making fscache interface that covers the whole FUSE usermode
messages + allows for those requirements is useful beyond streaming, we'll investigate that route further.

Thank you, and sorry for a long email

--
Thanks, Yurii

#20 lore raw
Quoted 62 lines · Yurii Zubrytskyi
Quoted 10 lines · Amir Goldstein

I think you have made the right choice for you and for the product you are working on to use an isolated module to provide this functionality.

But I assume the purpose of your posting was to request upstream inclusion, community code review, etc. This is not likely to happen when the implementation and design choices are derived from Employer needs vs. the community needs. Sure, you can get high level design review, which is what *this* is, but I recon not much more.

Quoted 8 lines

This discussion has several references to community projects that can benefit from this functionality, but not in its current form.

This development model has worked well in the past for Android and the Android user base leverage could help to get you a ticket to staging, but eventually, those modules (e.g. ashmem) often do get replaced with more community oriented APIs.

Hi fsdevel
I'm Yurii, and I work with Eugene on the same team and the same project.

I want to explain how we ended up with a custom filesystem instead of trying to improve FUSE for everyone, and
why we think (maybe incorrectly) that it may be still pretty useful for the community.
As the project goal was to allow instant (-ish) deployment of apps from the dev environment to Android phone, we were hoping to stick with plain FUSE filesystem, and that's what we've done at first. But it turned out that even with the best tuning it was still really slow and battery-hungry (phones spent energy faster than they were charging over the cord).
At this point we've already collected the profiles for the filesystem usage, and also figured out what features are essential
to make it usable for streaming:
1. Random reads are the most common -> 4kb-sized read is the size we have to support, and may not go to usermode on each of those
2. Android tends to list the app directory and stat files in it often -> these operations need to be cached in kernel as well
3. Because of *random* reads streaming files sequentially isn't optimal -> need to be able to collect read logs from first deployment and stream in that order next time on incremental builds
4. Devices have small flash cards, need to deploy uncompressed game images for speed and mmap access ->
support storing 4kb blocks compressed
4.1. Host computer is much better at compression -> support streaming compressed blocks into the filesystem storage directly, without
recompression on the phone
5. Android has to verify app signature for installation -> need to support per-block signing and lazy verification
5.1. For big games even per-block signature data can be huge, so need to stream even the signatures
6. Development cycle is usually edit-build-try-edit-... -> need to support delta-patches from existing files
7. File names for installed apps are standard and different from what they were on the host ->
must be able to store user-supplied 'key' next to each file to identify it
8. Files never change -> no need to have complex code for mutable data in the filesystem

Quoted 15 lines

In the end, we saw only two ways how to make all of this work: either take sdcardfs as a base and extend it, or change FUSE to support cache in kernel; and as you can imagine, sdcardfs route got thrown out of the window immediately after looking at the code. But after learning some FUSE internals and its code what we found out is that to make it do all the listed things we'd basically have to implement a totally new filesystem inside of it. The only real use of FUSE that remained was to send FUSE_INIT, and occasional read requests. Everything else required, first of all, making a cache object inside FUSE intercept every message before it goes to the user mode, and also adding new specialized commands initiated by the usermode (e.g. prefetching data that hasn't been requested yet, or streaming hashes in). Some things even didn't make sense for a generic usecase (e.g. having a limited circular buffer of read blocks in kernel that user can ask for and flush).

Hang on, fuse does use caches in the kernel (page cache, dcache/icache). The issue is probably not lack of cache, it's how the caches are primed and used. Did you disable these caches? Did you not disable invalidation for data, metadata and dcache? In recent kernels we added caching readdir as well. The only objects not cached
are (non-acl) xattrs. Do you have those? Re prefetching data:
there's the NOTIFY_STORE message.

Thanks,
Miklos

#21 lore raw
Quoted 6 lines

Hang on, fuse does use caches in the kernel (page cache, dcache/icache). The issue is probably not lack of cache, it's how the caches are primed and used. Did you disable these caches? Did you not disable invalidation for data, metadata and dcache? In recent kernels we added caching readdir as well. The only objects not cached
are (non-acl) xattrs. Do you have those?

Android (which is our primary use case) is constantly under memory pressure, so caches
don't actually last long. Our experience with FOPEN_KEEP_CACHE has shown that pages are
evicted more often than the files are getting reopened, so it doesn't help. FUSE has to re-read
the data from the backing store all the time.
We didn't use xattrs for the FUSE-based implementation, but ended up requiring a similar thing in
the Incremental FS, so the final design would have to include them.

Quoted 2 lines

Re prefetching data:
there's the NOTIFY_STORE message.

To add to the previous point, we do not have the data for prefetching, as we're loading it page-by-page
from the host. We had to disable readahead for FUSE completely, otherwise even USB3 isn't fast enough
to deliver data in that big chunks in time, and applications keep hanging on page faults.

Overall, better caching doesn't save much *on Android*; what would work is a full-blown data storage system inside
FUSE kernel code, that can intercept requests before they go into user mode and process them completely. That's how
we could keep the data out of RAM but still get rid of that extra context switch and kernel-user transition.
But this also means that FUSE becomes damn too much aware of the specific storage format and all its features, and
basically gets specialized implementation of one of its filesystem inside the generic FUSE code.
Even if we separate that out, the kernel API between the storage and FUSE ended up being complete VFS API copy,
with some additions to send data blocks and Merkle tree blocks in. The code is truly if we stuff the Incremental FS into
FUSE instead of mounting it directly.

Signature · 1 line
Thanks, Yurii
#22 lore raw
Quoted 7 lines · Yurii Zubrytskyi
Quoted 7 lines

Hang on, fuse does use caches in the kernel (page cache, dcache/icache). The issue is probably not lack of cache, it's how the caches are primed and used. Did you disable these caches? Did you not disable invalidation for data, metadata and dcache? In recent kernels we added caching readdir as well. The only objects not cached
are (non-acl) xattrs. Do you have those?

Quoted 7 lines

Android (which is our primary use case) is constantly under memory pressure, so caches
don't actually last long. Our experience with FOPEN_KEEP_CACHE has shown that pages are
evicted more often than the files are getting reopened, so it doesn't help. FUSE has to re-read
the data from the backing store all the time.

What would benefit many fuse applications is to let the kernel transfer data to/from a given location (i.e. offset within a file). So instead of transferring data directly in the READ/WRITE messages, there would be a MAP message that would return information about where the data resides (list of extents+extra parameters for compression/encryption). The returned information could be generic enough for your needs, I think. The fuse kernel module would cache this mapping, and could keep the mapping around for possibly much longer than the data itself, since it would require orders of magnitude less memory. This would not only be saving memory copies, but also the number of round trips to userspace.

There's also work currently ongoing in optimizing the overhead of userspace roundtrip. The most promising thing appears to be matching up the CPU for the userspace server with that of the task doing the request. This can apparently result in 60-500% speed improvement.

Quoted 10 lines

We didn't use xattrs for the FUSE-based implementation, but ended up requiring a similar thing in
the Incremental FS, so the final design would have to include them.

Quoted 2 lines

Re prefetching data:
there's the NOTIFY_STORE message.

To add to the previous point, we do not have the data for prefetching, as we're loading it page-by-page
from the host. We had to disable readahead for FUSE completely, otherwise even USB3 isn't fast enough

Understood. Did you re-enable readahead for the case when the file has been fully downloaded?

Thanks,
Miklos

#23 lore raw
Quoted 11 lines · Miklos Szeredi

What would benefit many fuse applications is to let the kernel transfer data to/from a given location (i.e. offset within a file). So instead of transferring data directly in the READ/WRITE messages, there would be a MAP message that would return information about where the data resides (list of extents+extra parameters for compression/encryption). The returned information could be generic enough for your needs, I think. The fuse kernel module would cache this mapping, and could keep the mapping around for possibly much longer than the data itself, since it would require orders of magnitude less memory. This would not only be saving memory copies, but also the number of round trips to userspace.

Yes, and this was _exactly_ our first plan, and it mitigates the read performance
issue. The reasons why we didn't move forward with it are that we figured out all other requirements, and fixing each of those needs another change in FUSE, up to the level when FUSE interface becomes 50% dedicated to our specific goal:
1. MAP message would have to support data compression (with different algorithms), hash verification (same thing) with hash streaming (because even the Merkle tree for a 5GB file is huge, and can't be preloaded at once)
1.1. Mapping memory usage can get out of hands pretty quickly: it has to
be at least (offset + size + compression type + hash location + hash size + hash kind) per each block. I'm not even thinking about multiple storage files here. For that 5GB file (that's a debug APK for some Android game we're targeting) we have 1.3M blocks, so ~16 bytes *1.3M = 20M of index only, without actual overhead for the lookup table.
If the kernel code owns and manages its own on-disk data store and the format, this index can be loaded and discarded on demand there.

2. We need the same kind of a MAP message but for the directory structure and for stat(2) calls - Android does way too many of these, and has no intention to fix it. These caches need to be dynamically sized as well (as I said, standard kernel caches don't hold anything long enough on Android because of the usual thing when all memory is used by running apps)

3. Several smaller features would have to be added, again with their own interface and specific code in FUSE
3.1 E.g. collecting logs of all block reads - we're planning to have a ring buffer of configurable size there, and a way to request its content from the
user space; this doesn't look that useful for other FUSE users, and may
actually be a serious security hole there. We'd not need it at all if FUSE was calling into user space on each read, so here it's almost like we're fighting ourselves and making two opposing changes in FUSE

4. All these features are much easier to implement for a readonly filesystem (cache invalidation is a big thing). But if we limit them in FUSE to readonly mode we'd make half of its interface dedicated to even smaller use case.

Quoted 4 lines

There's also work currently ongoing in optimizing the overhead of userspace roundtrip. The most promising thing appears to be matching up the CPU for the userspace server with that of the task doing the request. This can apparently result in 60-500% speed improvement.

That sounds almost too good to be true, and will be really cool. Do you have any patches or git remote available in any compilable state to try the optimization out? Android has quite complicated hardware config and I want to see how this works, especially with our model where several processes may send requests into the same filesystem FD.

Quoted 2 lines

Understood. Did you re-enable readahead for the case when the file has been fully downloaded?

Yes, and it doesn't really help - readahead wants a bunch of blocks together, but those are scattered around the backing image because they arrived separately and at different times. So usermode process still has to issue multiple read commands to respond to a single FUSE read(ahead) request, which is still slow. Even worse thing happens if CPU was in reduced frequency idling mode at that time (which is normal for mobile) - it takes couple hundred ms to ramp it up, and during that time latency is huge (milliseconds / block)

Overall, I see that it is possible to change FUSE in a way that meets our needs, but I'm not sure if that kind of change keeps FUSE interface friendly for all existing and new uses. The set of requirements is so big and the mobile platform constraints are so harsh that _as efficient as possible_ and _generic_ do, unfortunately, contradict each other.

Please tell me if you see it differently, and if you have some better ideas on how to change FUSE in a simpler way
--
Thanks, Yurii

#24 lore raw
Quoted 10 lines · Yurii Zubrytskyi

Yes, and this was _exactly_ our first plan, and it mitigates the read performance
issue. The reasons why we didn't move forward with it are that we figured out all other requirements, and fixing each of those needs another change in FUSE, up to the level when FUSE interface becomes 50% dedicated to our specific goal:
1. MAP message would have to support data compression (with different algorithms), hash verification (same thing) with hash streaming (because even the Merkle tree for a 5GB file is huge, and can't be preloaded at once)

With the proposed FUSE solution the following sequences would occur:

kernel: if index for given block is missing, send MAP message
userspace: if data/hash is missing for given block then download data/hash
userspace: send MAP reply
kernel: decompress data and verify hash based on index

The kernel would not be involved in either streaming data or hash, it would only work with data/hash that has already been downloaded. Right?

Or is your implementation doing streamed decompress/hash or partial blocks?

Quoted 8 lines

1.1. Mapping memory usage can get out of hands pretty quickly: it has to
be at least (offset + size + compression type + hash location + hash size + hash kind) per each block. I'm not even thinking about multiple storage files here. For that 5GB file (that's a debug APK for some Android game we're targeting) we have 1.3M blocks, so ~16 bytes *1.3M = 20M of index only, without actual overhead for the lookup table.
If the kernel code owns and manages its own on-disk data store and the format, this index can be loaded and discarded on demand there.

Why does the kernel have to know the on-disk format to be able to load and discard parts of the index on-demand? It only needs to know which blocks were accessed recently and which not so recently.

Quoted 10 lines
Quoted 4 lines

There's also work currently ongoing in optimizing the overhead of userspace roundtrip. The most promising thing appears to be matching up the CPU for the userspace server with that of the task doing the request. This can apparently result in 60-500% speed improvement.

That sounds almost too good to be true, and will be really cool. Do you have any patches or git remote available in any compilable state to try the optimization out? Android has quite complicated hardware config and I want to see how this works, especially with our model where several processes may send requests into the same filesystem FD.

Currently it's only a bunch of hacks, no proper interfaces yet.

I'll let you know once there's something useful for testing with a real filesystem.

BTW, which interface does your fuse filesystem use? Libfuse? Raw device?

Thanks,
Miklos

#25 lore raw
Quoted 11 lines

With the proposed FUSE solution the following sequences would occur:

kernel: if index for given block is missing, send MAP message
userspace: if data/hash is missing for given block then download data/hash
userspace: send MAP reply
kernel: decompress data and verify hash based on index

The kernel would not be involved in either streaming data or hash, it would only work with data/hash that has already been downloaded. Right?

Quoted 6 lines

Or is your implementation doing streamed decompress/hash or partial blocks?
...
Why does the kernel have to know the on-disk format to be able to load and discard parts of the index on-demand? It only needs to know which blocks were accessed recently and which not so recently.

(1) You're correct, only the userspace deals with all streaming. Kernel then sees full blocks of data (usually LZ4-compressed) and blocks of hashes
We'd need to give the location of the hash tree instead of the individual hash here though - verification has to go all the way to the top and even check the signature there. And the same 5 GB file would have over 40 MB of hashes (32 bytes of SHA2 for each 4K block), so those have to be read from disk as well.
Overall, let's just imagine a phone with 100 apps, 100MB each, installed this way. That ends up being ~10GB of data, so we'd need _at least_ 40 MB for the index and 80 MB for hashes *in kernel*. Android now fights for each megabyte of RAM used in the system services, so FUSE won't be able to cache that, going back to the user mode for almost all reads again.
(1 and 2) ... If FUSE were to know the on-disk format it would be able to simply parse and read it when needed, with as little memory footprint as it can. Requesting this data from the usermode every time with little caching defeats the whole purpose of the change.

Quoted 1 line

BTW, which interface does your fuse filesystem use? Libfuse? Raw device?

Yes, our code interacts with the raw FUSE fd via poll/read/write calls. We have tried the multithreaded approach via duping the control fd and FUSE_DEV_IOC_CLONE, but it didn't give much improvement - Android apps aren't usually use multithreaded, so there's at most two pending reads at once. I've seen 10 once, but that was some kind of miractle

And again, we have not even looked at the directory structure and stat caching yet, neither interface nor memory usage. For a general case we have to make direct disk reads from kernel and this forces even bigger part of the disk format to be defined there. The end result is what we've got when researching FUSE - a huge chunk of FUSE gets overspecialized to handle our own way of using it end to end, with no real configurability (because making it configurable makes that code even bigger and more complex)

--
Thanks, Yurii

#26 lore raw
Quoted 5 lines · Yurii Zubrytskyi

We'd need to give the location of the hash tree instead of the individual hash here though - verification has to go all the way to the top and even check the signature there. And the same 5 GB file would have over 40 MB of hashes (32 bytes of SHA2 for each 4K block), so those have to be read from disk as well.

As I think Eugene mentioned, dealing with the hash tree should be done by the verity subsystem anyway.

Quoted 3 lines

Overall, let's just imagine a phone with 100 apps, 100MB each, installed this way. That ends up being ~10GB of data, so we'd need _at least_ 40 MB for the index and 80 MB for hashes *in kernel*.

Seriously? Are those 100 apps accessing that 10G simultaneously?

I really don't know the usage pattern of those apps, but I can imagine
that some games do quite a lot of paging data in and out. And my
guess is that most of those page-ins will still be sequential, and so getting a pageful of index from userspace will allow the kernel to serve quite a few reads without having to go back to userspace.

My guess is that even really tiny amount of caching (e.g. one page of index per open file) will get 90% or more of the possible performance improvement. But those are all just guesses. If you say this is not the right direction for your project, fine.

Thanks,
Miklos

#27 lore raw
In reply to Yurii Zubrytskyi
Quoted 42 lines · Yurii Zubrytskyi
Quoted 10 lines · Amir Goldstein

I think you have made the right choice for you and for the product you are working on to use an isolated module to provide this functionality.

But I assume the purpose of your posting was to request upstream inclusion, community code review, etc. This is not likely to happen when the implementation and design choices are derived from Employer needs vs. the community needs. Sure, you can get high level design review, which is what *this* is, but I recon not much more.

Quoted 8 lines

This discussion has several references to community projects that can benefit from this functionality, but not in its current form.

This development model has worked well in the past for Android and the Android user base leverage could help to get you a ticket to staging, but eventually, those modules (e.g. ashmem) often do get replaced with more community oriented APIs.

Hi fsdevel
I'm Yurii, and I work with Eugene on the same team and the same project.

I want to explain how we ended up with a custom filesystem instead of trying to improve FUSE for everyone, and
why we think (maybe incorrectly) that it may be still pretty useful for the community.
As the project goal was to allow instant (-ish) deployment of apps from the dev environment to Android phone, we were hoping to stick with plain FUSE filesystem, and that's what we've done at first. But it turned out that even with the best tuning it was still really slow and battery-hungry (phones spent energy faster than they were charging over the cord).
At this point we've already collected the profiles for the filesystem usage, and also figured out what features are essential
to make it usable for streaming:
1. Random reads are the most common -> 4kb-sized read is the size we have to support, and may not go to usermode on each of those
2. Android tends to list the app directory and stat files in it often -> these operations need to be cached in kernel as well
3. Because of *random* reads streaming files sequentially isn't

Quoted 8 lines

optimal -> need to be able to collect read logs from first deployment
and stream in that order next time on incremental builds
4. Devices have small flash cards, need to deploy uncompressed game images for speed and mmap access ->
support storing 4kb blocks compressed
4.1. Host computer is much better at compression -> support streaming compressed blocks into the filesystem storage directly, without
recompression on the phone

Aha. It wasn't clear to me that block aligned decompression of a specific compression format was part of the filesystem.
eromfs (also for Android) also provides new block aligned decompression subsystem and I have heard the maintainer say that the decompression engine could be moved into a library like fs/crypt so that other filesystem could support the same on-the-fly decryption engine.

Quoted 12 lines

5. Android has to verify app signature for installation -> need to support per-block signing and lazy verification
5.1. For big games even per-block signature data can be huge, so need to stream even the signatures
6. Development cycle is usually edit-build-try-edit-... -> need to support delta-patches from existing files
7. File names for installed apps are standard and different from what they were on the host ->
must be able to store user-supplied 'key' next to each file to identify it
8. Files never change -> no need to have complex code for mutable data in the filesystem

Quoted 15 lines

In the end, we saw only two ways how to make all of this work: either take sdcardfs as a base and extend it, or change FUSE to support cache in kernel; and as you can imagine, sdcardfs route got thrown out of the window immediately after looking at the code. But after learning some FUSE internals and its code what we found out is that to make it do all the listed things we'd basically have to implement a totally new filesystem inside of it. The only real use of FUSE that remained was to send FUSE_INIT, and occasional read requests. Everything else required, first of all, making a cache object inside FUSE intercept every message before it goes to the user mode, and also adding new specialized commands initiated by the usermode (e.g. prefetching data that hasn't been requested yet, or streaming hashes in). Some things even didn't make sense for a generic usecase (e.g. having a limited circular buffer of read blocks in kernel that user can ask for and flush).

As Miklos pointed out and I as well in a previous message, it appears that you missed a few caching capabilities of FUSE - Those capabilities may or may not make sense to extend using fscache or by other means - I haven't studied this myself, but the study you publish does not convince me that this option has been fully exhausted.

Quoted 11 lines

In the end, after several tries we just came to a conclusion that the very set of original requirements is so specific that, funny enough, anyone who wants to create a lazy-loading experience would hit most of them, while anyone who's doing something else, would miss most of them. That's the main reason to go with a separate specialized driver module, and the reason to share it with the community - we have a feeling that people will benefit from a high-quality implementation of lazy loading in kernel, and we will benefit from the community support and guiding.

Quoted 5 lines

Again, we all are human and can be wrong at any step when making conclusions. E.g. we didn't know about the fscache subsystem, and were only planning to create a cache object inside FUSE instead. But for now I still feel that our original research stands, and that in the long run specialized filesystem serves its users much

"serves its users" - that's the difference between our perspective. I am not thinking only on users of incfs as you defined it, but on a wider variety of users that need the functionality of user space filesystem with kernel "fast path" optimizations.

Quoted 6 lines

better than several scattered changes in other places that all pretty much look like the same filesystem split into three parts and adopted to the interfaces those places force onto it. Even more, those changes and interfaces look quite strange on their own, when not used together.

Quoted 7 lines

Please tell me what you think about this whole thing. We do care about the feature in general, not about making it
look as we've coded it right now. If you feel that making fscache interface that covers the whole FUSE usermode
messages + allows for those requirements is useful beyond streaming, we'll investigate that route further.

Let me answer that with an anecdote.
The very first FUSE filesystem was AVFS (http://avf.sourceforge.net/).
It provides a VFS interface to archives (e.g. zip).
It is quite amusing that this is exactly what incfs in meant to provide (APK is a zip file, apparently with some new block aligned compression?).

Now forget Android and APK download and imagine a huge tar archive on a slow tape device, which can be browsed using AVFS/FUSE. In that case, would AVFS users benefit from local disk caching of pieces of archive read from the tape? listing read from the tape? (Yes) Would AVFS users benefit from storing the compressed blocks in local disk cache and decompressing them on first read? (Sure why not).

The decision of whether or not incfs functionality should be built into FUSE needs to take into account all the FUSE filesystems out there. How many of them would benefit from the extended functionality? My personal guess is that the answer is "a lot".

Thanks,
Amir.

#28 lore raw
In reply to Eugene Zemtsov

Eugene,

----- Ursprüngliche Mail -----

Quoted 3 lines

userfaultfd
As far as I can see this would only work for mmap-ed files. All read() and readdir() calls would never return right results.

Yep. For lazy loading a program that should be okay. But now with more details on your use-case I agree with Amir, a cached network filesystem makes more sense.

Thanks,
//richard

#29 lore raw
In reply to Eugene Zemtsov
Quoted 57 lines · Eugene Zemtsov
Quoted 2 lines · Al Viro

Why not CODA, though, with local fs as cache?

Quoted 11 lines · Amir Goldstein

This sounds very useful.

Why does it have to be a new special-purpose Linux virtual file? Why not FUSE, which is meant for this purpose?
Those are things that you should explain when you are proposing a new filesystem,
but I will answer for you - because FUSE page fault will incur high latency also after
blocks are locally available in your backend store. Right?

Quoted 7 lines

How about fscache support for FUSE then?
You can even write your own fscache backend if the existing ones don't fit your needs for some reason.

Piling logic into the kernel is not the answer. Adding the missing interfaces to the kernel is the answer.

Thanks for the interest and feedback. What I dreaded most was silence.

Probably I should have given a bit more details in the introductory email. Important features we’re aiming for:

1. An attempt to read a missing data block gives a userspace data loader a chance to fetch it. Once a block is loaded (in advance or after a page fault) it is saved into a local backing storage and following reads of the same block are done directly by the kernel. [Implemented]

2. Block level compression. It saves space on a device, while still allowing very granular loading and mapping. Less granular compression would trigger loading of more data than absolutely necessary, and that’s the thing we want to avoid. [Implemented]

3. Block level integrity verification. The signature scheme is similar to DMverity or fs-verity. In other words, each file has a Merkle tree with crypto-digests of 4KB blocks. The root digest is signed with RSASSA or ECDSA. Each time a data block is read digest is calculated and checked with the Merkle tree, if the signature check fails the read operation fails as well. Ideally I’d like to use fs-verity API for that. [Not implemented yet.]

4. New files can be pushed into incremental-fs “externally” when an app needs a new resource or a binary. This is needed for situations when a new resource or a new version of code is available, e.g. a user just changed the system language to Spanish, or a developer rolled out an app update. Things change over time and this means that we can’t just incrementally
load a precooked ext4 image and mount it via a loopback device. [Implemented]

5. No need to support writes or file resizing. It eliminates a lot of complexity.

Quoted 10 lines

Currently not all of these features are implemented yet, but they all will be needed to achieve our goals:
- Apps can be delivered incrementally without having to wait for extra data. At the same time given enough time the app can be downloaded fully without having to keep a connection open after that.
- App’s integrity should be verifiable without having to read all its blocks.
- Local storage and battery need to be conserved.
- Apps binaries and resources can change over time.
Such changes are triggered by external events.

Good summary. I understand the requirements better now.

I still have issues with this design, because it looks very android specific. For example I know that lazy download is something actually being heavily used by distributed computing (see cernvm-fs)
so it's not a specific requirement of android. By bundling these
features together into a kernel module you are basically limiting the user base and hence possibly missing out on some of the advantages of having a more varied user base.

I wonder how much of the performance issues with the fuse prototype
was because of 4k reads/disabling re adahead? I know you require
that for the data loading part, but it would be trivial to turn that
behavior off once everything is in place. Does the prototype do
that? Have you tried doing that? Is the prototype in a good enough shape to perhaps move it to a public repository for review?

I'm also wondering about some of the features you describle above. Why a new block fs? A normal fs (ext4) provides most of those things:
you can add files to it, etc... The one thing it doesn't provide is compression, and that's because it's hard for the non-incremental
case. So do we really need a new disk format for this? Or can the
missing compression feature (perhaps with limits) be implemented in ext4/f2fs? In that case we even can take that work off of fuse and just leave the loading to the fuse part. Cernvm-fs does that with a fuse fs on the lower layer that does lazy downloading, and putting already downloaded files in an upper layer of overlayfs for faster access, but it's possible that there's a better way of doing that not involving even overlayfs.

Thanks,
Miklos

#30 lore raw
In reply to Theodore Ts'o
Quoted 16 lines · Theodore Ts'o
Quoted 10 lines · Amir Goldstein

This sounds very useful.

Why does it have to be a new special-purpose Linux virtual file? Why not FUSE, which is meant for this purpose?
Those are things that you should explain when you are proposing a new filesystem,
but I will answer for you - because FUSE page fault will incur high latency also after
blocks are locally available in your backend store. Right?

From the documentation file in the first patch:

Review

Quoted 7 lines
(quoted diff) +7 -0
+Why isn't incremental-fs implemented via FUSE?
+----------------------------------------------
+TLDR: FUSE-based filesystems add 20-80% of performance overhead for target
+scenarios, and increase power use on mobile beyond acceptable limit
+for widespread deployment. A custom kernel filesystem is the way to overcome
+these limitations.
+

Fair enough. I didn't think FUSE could be an alternative as-is.
I am familiar with USENIX paper.
The question is if we need to re-intent the wheel or try to improve the wheel.

Thanks,
Amir.

#31 lore raw
In reply to Amir Goldstein
Quoted 36 lines · Amir Goldstein
Quoted 13 lines · On Thu, May 2, 2019 at 12:04 AM <[email protected]> wrote:

Hi All,

Please take a look at Incremental FS.

Incremental FS is special-purpose Linux virtual file system that allows execution of a program while its binary and resource files are still being lazily downloaded over the network, USB etc. It is focused on incremental delivery for a small number (under 100) of big files (more than 10 megabytes each). Incremental FS doesn’t allow direct writes into files and, once loaded, file content never changes. Incremental FS doesn’t use a block device, instead it saves data into a backing file located on a regular file-system.

Quoted 6 lines

What’s it for?

It allows running big Android apps before their binaries and resources are fully loaded to an Android device. If an app reads something not loaded yet, it needs to wait for the data block to be fetched, but in most cases hot blocks can be loaded in advance and apps can run smoothly and almost instantly.

This sounds very useful.

Why does it have to be a new special-purpose Linux virtual file? Why not FUSE, which is meant for this purpose?
Those are things that you should explain when you are proposing a new filesystem,
but I will answer for you - because FUSE page fault will incur high latency also after
blocks are locally available in your backend store. Right?

How about fscache support for FUSE then?
You can even write your own fscache backend if the existing ones don't fit your needs for some reason.

Quoted 7 lines

Do you know of the project https://vfsforgit.org/?
Not exactly the same use case but very similar. There is ongoing work on a Linux port developed by GitHub.com:
https://github.com/github/libprojfs

Piling logic into the kernel is not the answer. Adding the missing interfaces to the kernel is the answer.

I wonder whether userfaultfd can but used for that use-case too?

Signature · 2 lines
Thanks,
//richard
#32 lore raw
Quoted 4 lines · Richard Weinberger
Quoted 2 lines

Piling logic into the kernel is not the answer. Adding the missing interfaces to the kernel is the answer.

I wonder whether userfaultfd can but used for that use-case too?

...hit the send button too eary.

My thought is, userfaultfd is used to support live migration of VMs such that pages from the remote side are loaded on demand.
Sounds a little like the android app use-case, hm?

The loader (ld-linux) runs the app and using userfaultfd missing pages get downloaded on demand.

Signature · 2 lines
Thanks,
//richard
#33 lore raw
In reply to [email protected]

[email protected]:

Quoted 3 lines

Incremental FS is special-purpose Linux virtual file system that allows execution of a program while its binary and resource files are still being lazily downloaded over the network, USB etc. It is focused on incremental

	:::

I had developed a very similar userspace daemon many years ago which is called ULOOP. As you can guess it is based upon the loopback block device in stead of the filesystem.

(from the readme file)
----------------------------------------
1. sample for HTTP
Simple 'make' will build ./drivers/block/uloop.ko and ./ulohttp. Ulohttp application behaves like losetup(8). Additionally, ulohttp is an actual daemon which handles I/O request.
Here is a syntax.

ulohttp [-b bitmap] [-c cache] device URL

The device is /dev/loopN and the URL is a URL for fs-image file via HTTP. The http server must support byte range (Range: header). The bitmap is a new filename or previously specified as the bitmap for the same URL. Its filesize will be 'the size of the specified fs-image / pagesize (usually 4k) / bits in a byte (8)', and round-up to pagesize.
The cache is a new filename or previously specified as the cache for the same URL. Its filesize will be 'the size of the specified fs-image', and round-up to pagesize.
Note that both the bitmap and the cache are re-usable as long as you don't change the filedata and URL.

When someone reads from the specified /dev/loopN, or accesses a file on a filesystem after mounting /dev/loopN, ULOOP driver first checks the corresponding bit in the bitmap file. When the bit is not set, which means the block is not retrieved yet, it passes the offset and size of the I/O request to ulohttp daemon.
Ulohttp converts the offset and the size into HTTP GET request with Range header and send it to the http server.
Retriving the data from the http server, ulohttp stores it to the cache file, and tells ULOOP driver that the HTTP transfer completes. Then the ULOOP driver sets the corresponding bit in the bitmap, and finishes the I/O/request.

In other words, it is equivalent to this operation.

$ wget URL_for_fsimage
$ sudo mount -o loop retrieved_fsimage /mnt
But ULOOP driver and ulohttp retrieves only the data (block) on-demand,
and stores into the cache file. The first access to a block is slow
since it involves HTTP GET, but the next access to the same block is
fast since it is in the local cache file. In this case, the behaviour
is equivalent to the simple /dev/loop device.

----------------------------------------

If you are interested, then try
https://sourceforge.net/p/aufs/aufs-util/ci/aufs4.14/tree/sample/uloop/

It is just for your information.

J. R. Okajima