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_super_block |]---+ 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 }; 123 124 /* Header included at the beginning of all metadata records on the disk. */ 125 struct incfs_md_header { 126 __u8 h_md_entry_type; 127 128 /* 129 * Size of the metadata record. 130 * (e.g. inode, dir entry etc) not just this struct. 131 */ 132 __le16 h_record_size; 133 134 /* 135 * CRC32 of the metadata record. 136 * (e.g. inode, dir entry etc) not just this struct. 137 */ 138 __le32 h_record_crc; 139 140 /* Offset of the next metadata entry if any */ 141 __le64 h_next_md_offset; 142 143 /* Offset of the previous metadata entry if any */ 144 __le64 h_prev_md_offset; 145 146 } __packed; 147 148 /* Backing file header */ 149 struct incfs_file_header { 150 /* Magic number: INCFS_MAGIC_NUMBER */ 151 __le64 fh_magic; 152 153 /* Format version: INCFS_FORMAT_CURRENT_VER */ 154 __le64 fh_version; 155 156 /* sizeof(incfs_file_header) */ 157 __le16 fh_header_size; 158 159 /* INCFS_DATA_FILE_BLOCK_SIZE */ 160 __le16 fh_data_block_size; 161 162 /* Padding, also reserved for future use. */ 163 __le32 fh_dummy; 164 165 /* Offset of the first metadata record */ 166 __le64 fh_first_md_offset; 167 168 /* 169 * Put file specific information after this point 170 */ 171 172 /* Full size of the file's content */ 173 __le64 fh_file_size; 174 175 /* File uuid */ 176 incfs_uuid_t fh_uuid; 177 } __packed; 178 179 enum incfs_block_map_entry_flags { 180 INCFS_BLOCK_COMPRESSED_LZ4 = (1 << 0), 181 }; 182 183 /* Block map entry pointing to an actual location of the data block. */ 184 struct incfs_blockmap_entry { 185 /* Offset of the actual data block. Lower 32 bits */ 186 __le32 me_data_offset_lo; 187 188 /* Offset of the actual data block. Higher 16 bits */ 189 __le16 me_data_offset_hi; 190 191 /* How many bytes the data actually occupies in the backing file */ 192 __le16 me_data_size; 193 194 /* Block flags from incfs_block_map_entry_flags */ 195 __le16 me_flags; 196 } __packed; 197 198 /* Metadata record for locations of file blocks. Type = INCFS_MD_BLOCK_MAP */ 199 struct incfs_blockmap { 200 struct incfs_md_header m_header; 201 202 /* Base offset of the array of incfs_blockmap_entry */ 203 __le64 m_base_offset; 204 205 /* Size of the map entry array in blocks */ 206 __le32 m_block_count; 207 } __packed; 208 209 /* Metadata record for file attribute. Type = INCFS_MD_FILE_ATTR */ 210 struct incfs_file_attr { 211 struct incfs_md_header fa_header; 212 213 __le64 fa_offset; 214 215 __le16 fa_size; 216 217 __le32 fa_crc; 218 } __packed; 219 220 /* Metadata record for file attribute. Type = INCFS_MD_SIGNATURE */ 221 struct incfs_file_signature { 222 struct incfs_md_header sg_header; 223 224 __u8 sg_hash_alg; /* Value from incfs_hash_tree_algorithm */ 225 226 __le32 sg_hash_tree_size; /* The size of the hash tree. */ 227 228 __le64 sg_hash_tree_offset; /* Hash tree offset in the backing file */ 229 230 __u8 sg_root_hash[INCFS_MAX_HASH_SIZE]; 231 232 __le32 sg_sig_size; /* The size of the pkcs7 signature. */ 233 234 __le64 sg_sig_offset; /* pkcs7 signature's offset in the backing file */ 235 236 __le32 sg_add_data_size; /* The size of the additional data. */ 237 238 __le64 sg_add_data_offset; /* Additional data's offset */ 239 } __packed; 240 241 /* State of the backing file. */ 242 struct backing_file_context { 243 /* Protects writes to bc_file */ 244 struct mutex bc_mutex; 245 246 /* File object to read data from */ 247 struct file *bc_file; 248 249 /* 250 * Offset of the last known metadata record in the backing file. 251 * 0 means there are no metadata records. 252 */ 253 loff_t bc_last_md_record_offset; 254 }; 255 256 257 /* Backing file locations of things required for signature validation. */ 258 struct ondisk_signature { 259 260 loff_t add_data_offset; /* Additional data's offset */ 261 262 loff_t sig_offset; /* pkcs7 signature's offset in the backing file */ 263 264 loff_t mtree_offset; /* Backing file offset of the hash tree. */ 265 266 u32 add_data_size; /* The size of the additional data. */ 267 268 u32 sig_size; /* The size of the pkcs7 signature. */ 269 270 u32 mtree_size; /* The size of the hash tree. */ 271 }; 272 273 struct metadata_handler { 274 loff_t md_record_offset; 275 loff_t md_prev_record_offset; 276 void *context; 277 278 union { 279 struct incfs_md_header md_header; 280 struct incfs_blockmap blockmap; 281 struct incfs_file_attr file_attr; 282 struct incfs_file_signature signature; 283 } md_buffer; 284 285 int (*handle_blockmap)(struct incfs_blockmap *bm, 286 struct metadata_handler *handler); 287 int (*handle_file_attr)(struct incfs_file_attr *fa, 288 struct metadata_handler *handler); 289 int (*handle_signature)(struct incfs_file_signature *sig, 290 struct metadata_handler *handler); 291 }; 292 #define INCFS_MAX_METADATA_RECORD_SIZE \ 293 FIELD_SIZEOF(struct metadata_handler, md_buffer) 294 295 loff_t incfs_get_end_offset(struct file *f); 296 297 /* Backing file context management */ 298 struct backing_file_context *incfs_alloc_bfc(struct file *backing_file); 299 300 void incfs_free_bfc(struct backing_file_context *bfc); 301 302 /* Writing stuff */ 303 int incfs_write_blockmap_to_backing_file(struct backing_file_context *bfc, 304 u32 block_count, loff_t *map_base_off); 305 306 int incfs_write_fh_to_backing_file(struct backing_file_context *bfc, 307 incfs_uuid_t *uuid, u64 file_size); 308 309 int incfs_write_data_block_to_backing_file(struct backing_file_context *bfc, 310 struct mem_range block, 311 int block_index, loff_t bm_base_off, 312 u16 flags); 313 314 int incfs_write_hash_block_to_backing_file(struct backing_file_context *bfc, 315 struct mem_range block, 316 int block_index, loff_t hash_area_off); 317 318 int incfs_write_file_attr_to_backing_file(struct backing_file_context *bfc, 319 struct mem_range value, struct incfs_file_attr *attr); 320 321 int incfs_write_signature_to_backing_file(struct backing_file_context *bfc, 322 u8 hash_alg, u32 tree_size, 323 struct mem_range root_hash, struct mem_range add_data, 324 struct mem_range sig); 325 326 int incfs_make_empty_backing_file(struct backing_file_context *bfc, 327 incfs_uuid_t *uuid, u64 file_size); 328 329 /* Reading stuff */ 330 int incfs_read_file_header(struct backing_file_context *bfc, 331 loff_t *first_md_off, incfs_uuid_t *uuid, 332 u64 *file_size); 333 334 int incfs_read_blockmap_entry(struct backing_file_context *bfc, int block_index, 335 loff_t bm_base_off, 336 struct incfs_blockmap_entry *bm_entry); 337 338 int incfs_read_blockmap_entries(struct backing_file_context *bfc, 339 struct incfs_blockmap_entry *entries, 340 int start_index, int blocks_number, 341 loff_t bm_base_off); 342 343 int incfs_read_next_metadata_record(struct backing_file_context *bfc, 344 struct metadata_handler *handler); 345 346 ssize_t incfs_kread(struct file *f, void *buf, size_t size, loff_t pos); 347 ssize_t incfs_kwrite(struct file *f, const void *buf, size_t size, loff_t pos); 348 349 #endif /* _INCFS_FORMAT_H */ 350