1 /* SPDX-License-Identifier: GPL-2.0 */ 2 /* 3 * Copyright 2018 Google LLC 4 */ 5 6 /* 7 * Overview 8 * -------- 9 * The backbone of the incremental-fs ondisk format is an append only linked 10 * list of metadata blocks. Each metadata block contains an offset of the next 11 * one. These blocks describe files and directories on the 12 * file system. They also represent actions of adding and removing file names 13 * (hard links). 14 * 15 * Every time incremental-fs instance is mounted, it reads through this list 16 * to recreate filesystem's state in memory. An offset of the first record in 17 * the metadata list is stored in the superblock at the beginning of the backing 18 * file. 19 * 20 * Most of the backing file is taken by data areas and blockmaps. 21 * Since data blocks can be compressed and have different sizes, 22 * single per-file data area can't be pre-allocated. That's why blockmaps are 23 * needed in order to find a location and size of each data block in 24 * the backing file. Each time a file is created, a corresponding block map is 25 * allocated to store future offsets of data blocks. 26 * 27 * Whenever a data block is given by data loader to incremental-fs: 28 * - A data area with the given block is appended to the end of 29 * the backing file. 30 * - A record in the blockmap for the given block index is updated to reflect 31 * its location, size, and compression algorithm. 32 33 * Metadata records 34 * ---------------- 35 * incfs_blockmap - metadata record that specifies size and location 36 * of a blockmap area for a given file. This area 37 * contains an array of incfs_blockmap_entry-s. 38 * incfs_file_signature - metadata record that specifies where file signature 39 * and its hash tree can be found in the backing file. 40 * 41 * incfs_file_attr - metadata record that specifies where additional file 42 * attributes blob can be found. 43 * 44 * Metadata header 45 * --------------- 46 * incfs_md_header - header of a metadata record. It's always a part 47 * of other structures and served purpose of metadata 48 * bookkeeping. 49 * 50 * +-----------------------------------------------+ ^ 51 * | incfs_md_header | | 52 * | 1. type of body(BLOCKMAP, FILE_ATTR..) | | 53 * | 2. size of the whole record header + body | | 54 * | 3. CRC the whole record header + body | | 55 * | 4. offset of the previous md record |]------+ 56 * | 5. offset of the next md record (md link) |]---+ 57 * +-----------------------------------------------+ | 58 * | Metadata record body with useful data | | 59 * +-----------------------------------------------+ | 60 * +---> 61 * 62 * Other ondisk structures 63 * ----------------------- 64 * incfs_super_block - backing file header 65 * incfs_blockmap_entry - a record in a blockmap area that describes size 66 * and location of a data block. 67 * Data blocks dont have any particular structure, they are written to the 68 * backing file in a raw form as they come from a data loader. 69 * 70 * Backing file layout 71 * ------------------- 72 * 73 * 74 * +-------------------------------------------+ 75 * | incfs_file_header |]---+ 76 * +-------------------------------------------+ | 77 * | metadata |<---+ 78 * | incfs_file_signature |]---+ 79 * +-------------------------------------------+ | 80 * ......................... | 81 * +-------------------------------------------+ | metadata 82 * +------->| blockmap area | | list links 83 * | | [incfs_blockmap_entry] | | 84 * | | [incfs_blockmap_entry] | | 85 * | | [incfs_blockmap_entry] | | 86 * | +--[| [incfs_blockmap_entry] | | 87 * | | | [incfs_blockmap_entry] | | 88 * | | | [incfs_blockmap_entry] | | 89 * | | +-------------------------------------------+ | 90 * | | ......................... | 91 * | | +-------------------------------------------+ | 92 * | | | metadata |<---+ 93 * +----|--[| incfs_blockmap |]---+ 94 * | +-------------------------------------------+ | 95 * | ......................... | 96 * | +-------------------------------------------+ | 97 * +-->| data block | | 98 * +-------------------------------------------+ | 99 * ......................... | 100 * +-------------------------------------------+ | 101 * | metadata |<---+ 102 * | incfs_file_attr | 103 * +-------------------------------------------+ 104 */ 105 #ifndef _INCFS_FORMAT_H 106 #define _INCFS_FORMAT_H 107 #include <linux/types.h> 108 #include <linux/kernel.h> 109 #include <uapi/linux/incrementalfs.h> 110 111 #include "internal.h" 112 113 #define INCFS_MAX_NAME_LEN 255 114 #define INCFS_FORMAT_V1 1 115 #define INCFS_FORMAT_CURRENT_VER INCFS_FORMAT_V1 116 117 enum incfs_metadata_type { 118 INCFS_MD_NONE = 0, 119 INCFS_MD_BLOCK_MAP = 1, 120 INCFS_MD_FILE_ATTR = 2, 121 INCFS_MD_SIGNATURE = 3, 122 INCFS_MD_STATUS = 4, 123 INCFS_MD_VERITY_SIGNATURE = 5, 124 }; 125 126 enum incfs_file_header_flags { 127 INCFS_FILE_MAPPED = 1 << 1, 128 }; 129 130 /* Header included at the beginning of all metadata records on the disk. */ 131 struct incfs_md_header { 132 __u8 h_md_entry_type; 133 134 /* 135 * Size of the metadata record. 136 * (e.g. inode, dir entry etc) not just this struct. 137 */ 138 __le16 h_record_size; 139 140 /* 141 * Was: CRC32 of the metadata record. 142 * (e.g. inode, dir entry etc) not just this struct. 143 */ 144 __le32 h_unused1; 145 146 /* Offset of the next metadata entry if any */ 147 __le64 h_next_md_offset; 148 149 /* Was: Offset of the previous metadata entry if any */ 150 __le64 h_unused2; 151 152 } __packed; 153 154 /* Backing file header */ 155 struct incfs_file_header { 156 /* Magic number: INCFS_MAGIC_NUMBER */ 157 __le64 fh_magic; 158 159 /* Format version: INCFS_FORMAT_CURRENT_VER */ 160 __le64 fh_version; 161 162 /* sizeof(incfs_file_header) */ 163 __le16 fh_header_size; 164 165 /* INCFS_DATA_FILE_BLOCK_SIZE */ 166 __le16 fh_data_block_size; 167 168 /* File flags, from incfs_file_header_flags */ 169 __le32 fh_flags; 170 171 union { 172 /* Standard incfs file */ 173 struct { 174 /* Offset of the first metadata record */ 175 __le64 fh_first_md_offset; 176 177 /* Full size of the file's content */ 178 __le64 fh_file_size; 179 180 /* File uuid */ 181 incfs_uuid_t fh_uuid; 182 }; 183 184 /* Mapped file - INCFS_FILE_MAPPED set in fh_flags */ 185 struct { 186 /* Offset in original file */ 187 __le64 fh_original_offset; 188 189 /* Full size of the file's content */ 190 __le64 fh_mapped_file_size; 191 192 /* Original file's uuid */ 193 incfs_uuid_t fh_original_uuid; 194 }; 195 }; 196 } __packed; 197 198 enum incfs_block_map_entry_flags { 199 INCFS_BLOCK_COMPRESSED_LZ4 = 1, 200 INCFS_BLOCK_COMPRESSED_ZSTD = 2, 201 202 /* Reserve 3 bits for compression alg */ 203 INCFS_BLOCK_COMPRESSED_MASK = 7, 204 }; 205 206 /* Block map entry pointing to an actual location of the data block. */ 207 struct incfs_blockmap_entry { 208 /* Offset of the actual data block. Lower 32 bits */ 209 __le32 me_data_offset_lo; 210 211 /* Offset of the actual data block. Higher 16 bits */ 212 __le16 me_data_offset_hi; 213 214 /* How many bytes the data actually occupies in the backing file */ 215 __le16 me_data_size; 216 217 /* Block flags from incfs_block_map_entry_flags */ 218 __le16 me_flags; 219 } __packed; 220 221 /* Metadata record for locations of file blocks. Type = INCFS_MD_BLOCK_MAP */ 222 struct incfs_blockmap { 223 struct incfs_md_header m_header; 224 225 /* Base offset of the array of incfs_blockmap_entry */ 226 __le64 m_base_offset; 227 228 /* Size of the map entry array in blocks */ 229 __le32 m_block_count; 230 } __packed; 231 232 /* 233 * Metadata record for file signature. Type = INCFS_MD_SIGNATURE 234 * 235 * The signature stored here is the APK V4 signature data blob. See the 236 * definition of incfs_new_file_args::signature_info for an explanation of this 237 * blob. Specifically, it contains the root hash, but it does *not* contain 238 * anything that the kernel treats as a signature. 239 * 240 * When FS_IOC_ENABLE_VERITY is called on a file without this record, an APK V4 241 * signature blob and a hash tree are added to the file, and then this metadata 242 * record is created to record their locations. 243 */ 244 struct incfs_file_signature { 245 struct incfs_md_header sg_header; 246 247 __le32 sg_sig_size; /* The size of the signature. */ 248 249 __le64 sg_sig_offset; /* Signature's offset in the backing file */ 250 251 __le32 sg_hash_tree_size; /* The size of the hash tree. */ 252 253 __le64 sg_hash_tree_offset; /* Hash tree offset in the backing file */ 254 } __packed; 255 256 /* In memory version of above */ 257 struct incfs_df_signature { 258 u32 sig_size; 259 u64 sig_offset; 260 u32 hash_size; 261 u64 hash_offset; 262 }; 263 264 struct incfs_status { 265 struct incfs_md_header is_header; 266 267 __le32 is_data_blocks_written; /* Number of data blocks written */ 268 269 __le32 is_hash_blocks_written; /* Number of hash blocks written */ 270 271 __le32 is_dummy[6]; /* Spare fields */ 272 } __packed; 273 274 /* 275 * Metadata record for verity signature. Type = INCFS_MD_VERITY_SIGNATURE 276 * 277 * This record will only exist for verity-enabled files with signatures. Verity 278 * enabled files without signatures do not have this record. This signature is 279 * checked by fs-verity identically to any other fs-verity signature. 280 */ 281 struct incfs_file_verity_signature { 282 struct incfs_md_header vs_header; 283 284 /* The size of the signature */ 285 __le32 vs_size; 286 287 /* Signature's offset in the backing file */ 288 __le64 vs_offset; 289 } __packed; 290 291 /* In memory version of above */ 292 struct incfs_df_verity_signature { 293 u32 size; 294 u64 offset; 295 }; 296 297 /* State of the backing file. */ 298 struct backing_file_context { 299 /* Protects writes to bc_file */ 300 struct mutex bc_mutex; 301 302 /* File object to read data from */ 303 struct file *bc_file; 304 305 /* 306 * Offset of the last known metadata record in the backing file. 307 * 0 means there are no metadata records. 308 */ 309 loff_t bc_last_md_record_offset; 310 311 /* 312 * Credentials to set before reads/writes 313 * Note that this is a pointer to the mount_info mi_owner field so 314 * there is no need to get/put the creds 315 */ 316 const struct cred *bc_cred; 317 }; 318 319 struct metadata_handler { 320 loff_t md_record_offset; 321 loff_t md_prev_record_offset; 322 void *context; 323 324 union { 325 struct incfs_md_header md_header; 326 struct incfs_blockmap blockmap; 327 struct incfs_file_signature signature; 328 struct incfs_status status; 329 struct incfs_file_verity_signature verity_signature; 330 } md_buffer; 331 332 int (*handle_blockmap)(struct incfs_blockmap *bm, 333 struct metadata_handler *handler); 334 int (*handle_signature)(struct incfs_file_signature *sig, 335 struct metadata_handler *handler); 336 int (*handle_status)(struct incfs_status *sig, 337 struct metadata_handler *handler); 338 int (*handle_verity_signature)(struct incfs_file_verity_signature *s, 339 struct metadata_handler *handler); 340 }; 341 #define INCFS_MAX_METADATA_RECORD_SIZE \ 342 sizeof_field(struct metadata_handler, md_buffer) 343 344 /* Backing file context management */ 345 struct mount_info; 346 struct backing_file_context *incfs_alloc_bfc(struct mount_info *mi, 347 struct file *backing_file); 348 349 void incfs_free_bfc(struct backing_file_context *bfc); 350 351 /* Writing stuff */ 352 int incfs_write_blockmap_to_backing_file(struct backing_file_context *bfc, 353 u32 block_count); 354 355 int incfs_write_fh_to_backing_file(struct backing_file_context *bfc, 356 incfs_uuid_t *uuid, u64 file_size); 357 358 int incfs_write_mapping_fh_to_backing_file(struct backing_file_context *bfc, 359 incfs_uuid_t *uuid, u64 file_size, u64 offset); 360 361 int incfs_write_data_block_to_backing_file(struct backing_file_context *bfc, 362 struct mem_range block, 363 int block_index, loff_t bm_base_off, 364 u16 flags); 365 366 int incfs_write_hash_block_to_backing_file(struct backing_file_context *bfc, 367 struct mem_range block, 368 int block_index, 369 loff_t hash_area_off, 370 loff_t bm_base_off, 371 loff_t file_size); 372 373 int incfs_write_signature_to_backing_file(struct backing_file_context *bfc, 374 struct mem_range sig, u32 tree_size, 375 loff_t *tree_offset, loff_t *sig_offset); 376 377 int incfs_write_status_to_backing_file(struct backing_file_context *bfc, 378 loff_t status_offset, 379 u32 data_blocks_written, 380 u32 hash_blocks_written); 381 int incfs_write_verity_signature_to_backing_file( 382 struct backing_file_context *bfc, struct mem_range signature, 383 loff_t *offset); 384 385 /* Reading stuff */ 386 int incfs_read_file_header(struct backing_file_context *bfc, 387 loff_t *first_md_off, incfs_uuid_t *uuid, 388 u64 *file_size, u32 *flags); 389 390 int incfs_read_blockmap_entry(struct backing_file_context *bfc, int block_index, 391 loff_t bm_base_off, 392 struct incfs_blockmap_entry *bm_entry); 393 394 int incfs_read_blockmap_entries(struct backing_file_context *bfc, 395 struct incfs_blockmap_entry *entries, 396 int start_index, int blocks_number, 397 loff_t bm_base_off); 398 399 int incfs_read_next_metadata_record(struct backing_file_context *bfc, 400 struct metadata_handler *handler); 401 402 ssize_t incfs_kread(struct backing_file_context *bfc, void *buf, size_t size, 403 loff_t pos); 404 ssize_t incfs_kwrite(struct backing_file_context *bfc, const void *buf, 405 size_t size, loff_t pos); 406 407 #endif /* _INCFS_FORMAT_H */ 408