1/* 2 * Copyright 2016, NICTA 3 * 4 * This software may be distributed and modified according to the terms of 5 * the GNU General Public License version 2. Note that NO WARRANTY is provided. 6 * See "LICENSE_GPLv2.txt" for details. 7 * 8 * @TAG(NICTA_GPL) 9 */ 10 11#ifndef __BILBYFS_H__ 12#define __BILBYFS_H__ 13 14#include <wrapper.h> 15 16#define bilbyfs_assert(v) BUG_ON(!(v)) 17 18#define bilbyfs_err(...) \ 19 printk(KERN_ERR __VA_ARGS__) 20 21#define bilbyfs_msg(...) \ 22 printk(KERN_INFO __VA_ARGS__) 23 24#ifndef BILBYFS_DEBUG 25#define bilbyfs_debug(...) \ 26 do {} while (0) 27#else 28#define bilbyfs_debug(...) \ 29 printk(KERN_ERR __VA_ARGS__) 30#endif /* !BILBYFS_DEBUG */ 31 32#define BILBYFS_SUPER_MAGIC 0x0b17b9f5 33#define BILBYFS_ROOT_INO 24 34#define BILBYFS_FIRST_SQNUM 1 /* Must be greater than 0 */ 35#define BILBYFS_FIRST_INO (BILBYFS_ROOT_INO + 1) 36#define BILBYFS_SUP_LNUM 0 37#define BILBYFS_LOG_FST_LNUM 3 38#define BILBYFS_MIN_USABLE_LOG_SZ 2 39#define BILBYFS_MAX_READDIR_DATA_SIZE 64 40#define BILBYFS_BD_MAX_NLEN 16 /* maximum length of block device */ 41#define BILBYFS_MAX_NLEN 255 /* maximum length of a file name */ 42#define BILBYFS_DEFAULT_NB_RESERVED_GC 3 43#define BILBYFS_DEFAULT_NB_RESERVED_DEL 3 44 45 46#define BILBYFS_OBJ_MAGIC 0xb17b9f50 47#define BILBYFS_PAD_BYTE 0x42 48#define BILBYFS_OBJ_PADDING 8 49#define BILBYFS_CRC32_INIT 0xFFFFFFFFU 50 51#define BILBYFS_TRUE (1) 52#define BILBYFS_FALSE (0) 53 54/* 55 * BILBYFS inode types. 56 * 57 * BILBYFS_ITYPE_REG: regular file 58 * BILBYFS_ITYPE_DIR: directory 59 * BILBYFS_ITYPE_LNK: soft link 60 * BILBYFS_ITYPE_BLK: block device node 61 * BILBYFS_ITYPE_CHR: character device node 62 * BILBYFS_ITYPE_FIFO: fifo 63 * BILBYFS_ITYPE_SOCK: socket 64 * BILBYFS_ITYPES_CNT: count of supported file types 65 */ 66enum { 67 BILBYFS_ITYPE_REG, 68 BILBYFS_ITYPE_DIR, 69 BILBYFS_ITYPE_LNK, 70 BILBYFS_ITYPE_BLK, 71 BILBYFS_ITYPE_CHR, 72 BILBYFS_ITYPE_FIFO, 73 BILBYFS_ITYPE_SOCK, 74 BILBYFS_ITYPES_CNT, 75}; 76 77/* 78 * Object types. 79 * 80 * BILBYFS_INODE_OBJ: inode object 81 * BILBYFS_DATA_OBJ: data object 82 * BILBYFS_DENTARR_OBJ: directory entry array object 83 * BILBYFS_PAD_OBJ: padding object 84 * BILBYFS_OBJ_TYPES_CNT: count of supported object types 85 * 86 * Note: we use these constants for id types as well. 87 * Directory entry array (dentarr) is a collection of obj_dentry 88 * see the definition of obj_dentry. 89 */ 90enum { 91 BILBYFS_INODE_OBJ, 92 BILBYFS_DATA_OBJ, 93 BILBYFS_DENTARR_OBJ, 94 BILBYFS_SUP_OBJ, 95 BILBYFS_PAD_OBJ, 96 BILBYFS_DEL_OBJ, 97 BILBYFS_SUM_OBJ, 98 BILBYFS_OBJ_TYPES_CNT, 99}; 100 101/* Object inode flags (on-flash inode flags) 102 * BILBYFS_ORPHAN_INODE: orhpan inode flag 103 */ 104enum { 105 BILBYFS_ORPHAN_FL = 0x01, 106 BILBYFS_APPEND_FL = 0x02, 107 BILBYFS_IMMUTABLE_FL = 0x04, 108}; 109 110/* Super object flags 111 * BILBYFS_SUP_ISDIRTY: was the file system unmount cleanly? 112 */ 113enum { 114 BILBYFS_SUP_ISDIRTY = 0x01, 115}; 116 117/* obj_id: id to retrieve an object from the index. 118 * This id is 64 bits long organised differently for each 119 * type of object: 120 * - inode: inode number (32 bits), zero (32 bits) 121 * - dentarr: inode number (32 bits), type dentry (3 bits), name hash (29 bits) 122 * - data: inode number (32 bits), type data (3 bits), block index (29 bits) 123 */ 124typedef u64 obj_id; 125typedef __le64 __le_obj_id; /* little endian version: as we store it on the media */ 126 127/* NIL_ID: Key returned by next_obj_id() when the id passed as argument is the 128 * highest id present in the index: there is no next id. 129 */ 130#define NIL_ID ((u64)~0) 131 132/* Number of bits available to store extra information in an id */ 133#define BILBYFS_ID_XINFO_BITS 29 134#define BILBYFS_ID_XINFO_MASK 0x1FFFFFF 135 136#define BILBYFS_MAX_FILE_SZ (1ULL << (BILBYFS_ID_XINFO_BITS + BILBYFS_BLOCK_SHIFT)) 137 138/* inum_from_id: extract the inode number from an id 139 * @id: id to analyse 140 * Returns the inode number of the id. 141 */ 142static inline ino_t inum_from_id(obj_id id) 143{ 144 return id >> 32; 145} 146/* type_from_id: extract the type of an id 147 * @id: id to analyse 148 * Returns the type of the id (BILBYFS_INODE_OBJ, BILBYFS_DATA_OBJ...). 149 */ 150static inline u32 type_from_id(obj_id id) 151{ 152 return (id >> BILBYFS_ID_XINFO_BITS) & 7; 153} 154 155static inline u32 xinfo_from_id(obj_id id) 156{ 157 return (id & BILBYFS_ID_XINFO_MASK); 158} 159 160/* inode_id_init: Initialise an inode id. 161 * ino: inode number of the id 162 * returns the id 163 */ 164static inline obj_id inode_id_init(ino_t ino) 165{ 166 obj_id id = (u64)ino << 32; 167 return id; 168} 169 170/** 171 * id_hash_nm - R5 hash function (borrowed from reiserfs). 172 * @s: dentry name 173 * @len: name length 174 */ 175static inline uint32_t id_hash_nm(const char *s, int len) 176{ 177 uint32_t a = 0; 178 const signed char *str = (const signed char *)s; 179 180 while (*str) { 181 a += *str << 4; 182 a += *str >> 4; 183 a *= 11; 184 str++; 185 } 186 return (a & BILBYFS_ID_XINFO_MASK); 187} 188 189/* dentarr_id_init: Initialise an `dentry array' id. 190 * ino: inode number of the id 191 * returns the id 192 */ 193static inline obj_id dentarr_id_init(ino_t ino, const char *name) 194{ 195 obj_id id = (u64)ino << 32 | 196 (BILBYFS_DENTARR_OBJ << BILBYFS_ID_XINFO_BITS) | 197 id_hash_nm(name, strlen(name)); 198 return id; 199} 200 201/* data_id_init: Initialise an data id. 202 * ino: inode number of the id 203 * block: block index number 204 * returns the id 205 */ 206static inline obj_id data_id_init(ino_t ino, u32 block) 207{ 208 obj_id id = (u64)ino << 32 | 209 (BILBYFS_DATA_OBJ << BILBYFS_ID_XINFO_BITS) | 210 block; 211 return id; 212} 213 214 215/* is_inode_id: assess if the id is a inode id 216 * @id: id to assess 217 * Returns 1 if id is a inode id 0 otherwise 218 */ 219static inline int is_inode_id(obj_id id) 220{ 221 return (type_from_id(id) == BILBYFS_INODE_OBJ); 222} 223 224/* is_dentarr_id: assess if the id is a `dentry array' id 225 * @id: id to assess 226 * Returns 1 if id is a `dentry array' id 0 otherwise 227 */ 228static inline int is_dentarr_id(obj_id id) 229{ 230 return (type_from_id(id) == BILBYFS_DENTARR_OBJ); 231} 232 233/* is_data_id: assess if the id is a data id 234 * @id: id to assess 235 * Returns 1 if id is a data id 0 otherwise 236 */ 237static inline int is_data_id(obj_id id) 238{ 239 return (type_from_id(id) == BILBYFS_DATA_OBJ); 240} 241 242/* struct obj_addr: Address of an object on-disk 243 * @lnum: logical-erase block number 244 * @offs: offset inside the logical-erase block 245 * @len: length of the object 246 */ 247struct obj_addr { 248 u32 lnum; 249 u32 offs; 250 u32 len; 251 u64 sqnum; 252}; 253 254/* 255 * struct bilbyfs_wbuf - BilbyFs write-buffer. 256 * @buf: write-buffer (of min. flash I/O unit size) 257 * @size: write-buffer size (in [@c->min_io_size, @c->max_write_size] range) 258 * @avail: number of bytes available in the write-buffer 259 * @used: number of used bytes in the write-buffer 260 * @sync_offs: offset to which data was synchronised to disk 261 * 262 */ 263struct bilbyfs_wbuf { 264 void *buf; 265 int size; 266 int avail; 267 int used; 268 int sync_offs; 269}; 270 271/* 272 * struct bilbyfs_rbuf - BilbyFs read-buffer. 273 * @buf: buffer of leb_size 274 * @offs: read-buffer offset in this logical eraseblock 275 * @size: read-buffer size (usually leb_size) 276 */ 277struct bilbyfs_rbuf { 278 void *buf; 279 int size; 280 int offs; 281}; 282 283/* struct bilbyfs_inode: in-memory inode representation 284 * @vfs_inode: VFS inode is embedded and MUST be the first field for 285 * container_of to work. 286 * @creat_sqnum: sequence number generated when the inode was created 287 * @flags: flags that will be stored on flash 288 */ 289struct bilbyfs_inode { 290 struct inode vfs_inode; 291 u64 creat_sqnum; 292 int flags; 293}; 294 295/* inode_to_binode: obtain a bilbyfs_inode from a VFS inode. 296 * @inode: inode to introspect 297 * Returns the bilbyfs_inode pointer attached to @inode. 298 */ 299static inline struct bilbyfs_inode *inode_to_binode(struct inode *inode) 300{ 301 return (void *)inode; 302} 303 304static inline void inode_init_perm(struct inode *inode, const struct inode *dir, 305 umode_t mode) 306{ 307 inode->i_uid = current_fsuid(); 308 if (dir && dir->i_mode & S_ISGID) { 309 inode->i_gid = dir->i_gid; 310 if (S_ISDIR(mode)) 311 mode |= S_ISGID; 312 } else 313 inode->i_gid = current_fsgid(); 314 inode->i_mode = mode; 315} 316 317/* struct bilbyfs_dirent: Generic directory entry structure used for readdir 318 * The structure allows to abstract away the Linux VFS filldir callback. 319 * @d_ino: inode number the directory entry is pointing to 320 * @d_off: offset of the directory entry in the directory 321 * @d_reclen: length of the name 322 * @d_type: type of inode (DT_REG, DT_DIR, DT_LNK...) 323 * @d_name: name of the (file/directory/link...) 324 */ 325struct bilbyfs_dirent { 326 unsigned long d_ino; 327 unsigned long d_off; 328 unsigned short d_reclen; 329 unsigned int d_type; 330 char d_name[BILBYFS_MAX_NLEN]; 331}; 332 333/* struct bilbyfs_super: in-memory superblock object representation 334 * @uuid: UUID from superblock 335 * @flags: (%BILBYFS_SUP_ISDIRTY, ...) 336 * @sqnum: sequence number of the super object, is the highest one if the FS was 337 * cleanly unmounted. 338 * @leb_size: size of a LEB for the media. 339 * @leb_cnt: number of LEB for the fs. 340 * @nb_reserved_gc: number of LEB reserved for GC 341 * @nb_reserved_del: number of LEB reserved for deletion 342 * @min_io_size: minimum amount of data we can write in a LEB in one go 343 * @max_io_size: maximum amount of data we can write in a LEB in one go 344 * @log_lnum: last erase-block number in the log (likely partially written) 345 * @log_offs: offset in the last erase-block of the log. 346 * @lowest_sqnum: lowest sqnum of a valid object on-flash (therefore indexed) 347 * @last_inum: last inode number used when unmount (next one is +1). 348 */ 349struct bilbyfs_super { 350 u8 uuid[16]; 351 u32 flags; 352 u64 sqnum; 353 int leb_cnt; 354 int leb_size; 355 int nb_reserved_gc; 356 int nb_reserved_del; 357 int min_io_size; 358 int max_io_size; 359 u32 log_lnum; 360 u32 log_offs; 361 u64 lowest_sqnum; 362 u64 last_inum; 363}; 364 365/* Red-Black tree node */ 366struct rbt_node { 367 unsigned long rbt_parent_color; 368#define RBT_RED 0 369#define RBT_BLACK 1 370 struct rbt_node *rbt_left; 371 struct rbt_node *rbt_right; 372}; 373 374struct rbt_root { 375 struct rbt_node *rbt_node; 376}; 377 378/* idx_node: Node index 379 * node: red-black tree node 380 * addr: address and sqnum of the object stored in the index 381 */ 382struct idx_node { 383 struct rbt_node node; 384 struct obj_addr addr; 385 obj_id id; 386}; 387 388/* gim_node: Node for GIM tree 389 * @node: red-black tree node 390 * @id: object id 391 * @sqnum: sequence number of the newest garbage object 392 * @count: number of objects with the same id 393 */ 394struct gim_node { 395 struct rbt_node node; 396 obj_id id; 397 u64 sqnum; 398 u32 count; 399}; 400 401#define NODE_SIZE max(sizeof(struct idx_node), sizeof(struct gim_node)) 402 403/* alloc_pool: Pool of pre-allocated content 404 * @arr: array of content 405 * @len: length of array of content 406 */ 407struct alloc_pool { 408 int tot_nodes_needed; 409 void **arr; 410 int len; 411 int i; 412 int sz_obj; 413}; 414 415/* 416 * Transactional object store flags 417 * BILBYFS_TRANS_ST: first object of a transaction with multiple objects 418 * BILBYFS_TRANS_IN: object in a transaction that is not the first nor the last 419 * one 420 * BILBYFS_TRANS_END: last object of a transaction 421 * BILBYFS_TRANS_ATOM: transaction of a single object 422 * 423 * Valid sequences pattern: (ST IN* END | ATOM) 424 */ 425enum { 426 BILBYFS_TRANS_ST = 0x1, 427 BILBYFS_TRANS_IN = 0x2, 428 BILBYFS_TRANS_END = 0x4, 429 BILBYFS_TRANS_ATOM = 0x1 | 0x4, 430}; 431 432/** 433 * struct obj_ch - object common header. 434 * @magic: object magic number (%BILBYFS_NODE_MAGIC) 435 * @crc: CRC-32 checksum of the object header 436 * @sqnum: sequence number 437 * @len: full object length (including this header) 438 * @type: object type (%BILBYFS_INODE_OBJ, %BILBYFS_EXPR_OBJ...) 439 * @trans: position in transaction (%BILBYFS_TRANS_*) 440 * @padding: reserved for future, zeroes 441 * 442 * Every object on-flash starts with this common part. If the object has an id, the 443 * id always goes next. 444 */ 445struct obj_ch { 446 __le32 magic; 447 __le32 crc; 448 __le64 sqnum; 449 __le32 len; 450 __u8 type; 451 __u8 trans; 452 __u8 padding[2]; 453} __packed; 454 455static inline void zero_obj_ch_unused(struct obj_ch *ch) 456{ 457 memset(ch->padding, 0, 2); 458} 459 460/** 461 * struct obj_inode - inode object. 462 * @ch: common header 463 * @id: object id 464 * @creat_sqnum: sequence number at time of creation 465 * @size: inode size in bytes 466 * @atime_sec: access time seconds 467 * @ctime_sec: creation time seconds 468 * @mtime_sec: modification time seconds 469 * @nlink: number of hard links 470 * @uid: owner ID 471 * @gid: group ID 472 * @mode: access flags, inode type... 473 * @flags: BILBYFS_ORPHAN_FL, BILBYFS_APPEND_FL... 474 */ 475struct obj_inode { 476 struct obj_ch ch; 477 __le_obj_id id; 478 __le64 creat_sqnum; 479 __le64 size; 480 __le64 atime_sec; 481 __le64 ctime_sec; 482 __le64 mtime_sec; 483 __le32 nlink; 484 __le32 uid; 485 __le32 gid; 486 __le32 mode; 487 __le32 flags; 488 __le32 padding; 489} __packed; 490 491static inline void zero_obj_inode_unused(struct obj_inode *ino) 492{ 493 ino->padding = 0; 494} 495 496/** 497 * struct obj_dentarr - `directory entry array' object. 498 * @ch: common header 499 * @id: object id 500 * @nb_dentry: number of dentry object in the array (i.e. hash collisions) 501 * @size: size in bytes of the obj_dentarr including the header (ch) but as 502 * opposed to ch.len, @size is not aligned. 503 */ 504struct obj_dentarr { 505 struct obj_ch ch; 506 __le_obj_id id; 507 __le32 nb_dentry; 508 __le32 size; 509} __packed; 510 511static inline void zero_obj_dentarr_unused(struct obj_dentarr *dentarr) 512{ 513} 514 515/* struct obj_dentry - directory entry object. 516 * @ino: target inode number 517 * @type: type of the target inode (%BILBYFS_ITYPE_REG, %BILBYFS_ITYPE_DIR, etc) 518 * @nlen: name length 519 * @name: zero-terminated name 520 * 521 * No padding here for simplicity. 522 */ 523struct obj_dentry { 524 __le32 ino; 525 __u8 type; 526 __le16 nlen; 527 __u8 name[]; 528} __packed; 529 530static inline void zero_obj_dentry_unused(struct obj_dentry *de) 531{ 532} 533 534/** 535 * struct obj_data - data object. 536 * @ch: common header 537 * @id: object id 538 * @size: data size in bytes 539 * @padding: reserved for future, zeroes 540 * @data: data 541 */ 542struct obj_data { 543 struct obj_ch ch; 544 __le_obj_id id; 545 __le32 size; 546 __u8 padding[4]; 547 __u8 data[]; 548} __packed; 549 550static inline void zero_obj_data_unused(struct obj_data *data) 551{ 552 memset(data->padding, 0, 4); 553} 554 555/** 556 * struct obj_del - deletion object 557 * @ch: common header 558 * @id: id of the object which is deleted 559 */ 560struct obj_del { 561 struct obj_ch ch; 562 __le_obj_id id; 563} __packed; 564 565static inline void zero_obj_del_unused(struct obj_del *del) 566{ 567} 568 569/** 570 * struct obj_sum_entry - summary object 571 * @id: obj id 572 * @sqnum: sequence number of the object 573 * @len: length of the object 574 * @del_flag_and_offs: the most significant bit indicates whether this 575 * is a deletion entry, the rest of bits are the offset of the object 576 * within the erase-block. 577 * @count: number of objects covered by deletion object (can't we use len 578 * for this for deletion objects? Their size is fixed isn't it? 579 */ 580struct obj_sum_entry { 581 __le_obj_id id; 582 __le64 sqnum; 583 __le32 len; 584 __le32 del_flag_and_offs; 585#define BILBYFS_SUM_ENTRY_DEL_FLAG_MASK 0x80000000 586 __le16 count; 587} __packed; 588 589static inline void zero_obj_sum_entry_unused(struct obj_sum_entry *sum_entry) 590{ 591} 592 593static inline u32 obj_sum_entry_offs(struct obj_sum_entry *sum_entry) 594{ 595 return (le32_to_cpu(sum_entry->del_flag_and_offs) & ~ BILBYFS_SUM_ENTRY_DEL_FLAG_MASK); 596} 597 598static inline u32 obj_sum_entry_is_del(struct obj_sum_entry *sum_entry) 599{ 600 return !!(le32_to_cpu(sum_entry->del_flag_and_offs) & BILBYFS_SUM_ENTRY_DEL_FLAG_MASK); 601} 602 603/** 604 * struct obj_sum - summary object 605 * @ch: common header 606 * @nb_sum_entry: number of entries in the summary 607 * @entries: summary entries 608 */ 609struct obj_sum { 610 struct obj_ch ch; 611 __le32 nb_sum_entry; 612 struct obj_sum_entry entries[]; 613 /* __le32 offs; The very last word32 is an offset to the summary object */ 614#define BILBYFS_OBJ_SUM_OFFS_SZ 4 615} __packed; 616 617static inline void zero_obj_sum_unused(struct obj_sum *sum) 618{} 619 620static inline u32 *obj_sum_offs(struct obj_sum *sum) 621{ 622 return (u32 *)((void *)sum + le32_to_cpu(sum->ch.len) - BILBYFS_OBJ_SUM_OFFS_SZ); 623} 624 625/* get_obj_id: Get the obj_id of an object 626 * @obj: pointer to the object 627 * 628 * Note that only indexed objects have an ID. 629 * Object ID has to be positioned right after the common header. 630 */ 631static inline obj_id get_obj_id(void *obj) 632{ 633 struct obj_ch *ch = obj; 634 __le_obj_id *le_id = (__le_obj_id *)(ch + 1); 635 636 bilbyfs_assert(ch->type == BILBYFS_INODE_OBJ || 637 ch->type == BILBYFS_DENTARR_OBJ || 638 ch->type == BILBYFS_DATA_OBJ || 639 ch->type == BILBYFS_DEL_OBJ ); 640 return le64_to_cpu(*le_id); 641} 642 643/** 644 * struct obj_super - super object. 645 * @ch: common header 646 * @flags: various flags (%BILBYFS_FS_DIRTY, etc) 647 * @gc_lnum: LEB reserved for garbage collection 648 * @total_free: total free space in bytes 649 * @total_dirty: total dirty space in bytes 650 * @total_used: total used space in bytes (includes only data LEBs) 651 * @total_dead: total dead space in bytes (includes only data LEBs) 652 * @total_dark: total dark space in bytes (includes only data LEBs) 653 * @empty_lebs: number of empty logical eraseblocks 654 * @leb_cnt: count of LEBs used by file-system 655 * @nb_reserved_gc: Number of LEBs reserved for garbage collection 656 * @log_head_leb: where was the head of log at last unmount 657 * @log_head_offs: and its offset in the leb 658 * @lowest_sqnum: Lowest valid sqnum on FS? 659 * @last_inum: Last inode number generated 660 */ 661struct obj_super { 662 struct obj_ch ch; 663#define BILBYFS_FS_DIRTY 0x1 664 __le32 flags; 665 __le32 gc_lnum; 666 __le64 total_free; 667 __le64 total_dirty; 668 __le64 total_used; 669 __le64 total_dead; 670 __le64 total_dark; 671 __le32 empty_lebs; 672 __le32 leb_size; 673 __le32 leb_cnt; 674 __le32 nb_reserved_gc; 675 __le32 nb_reserved_del; 676 __le32 log_head_leb; 677 __le32 log_head_offs; 678 __le64 lowest_sqnum; 679 __le64 last_inum; 680 __u8 padding[4]; 681} __packed; 682 683static inline void zero_obj_super_unused(struct obj_super *o) 684{ 685 memset(o->padding, 0, 4); 686} 687 688/* Size of objects */ 689#define BILBYFS_CH_SZ sizeof(struct obj_ch) 690#define BILBYFS_INODE_SZ sizeof(struct obj_inode) 691#define BILBYFS_DATA_SZ sizeof(struct obj_data) 692#define BILBYFS_DENTARR_SZ sizeof(struct obj_dentarr) 693#define BILBYFS_SUPER_SZ sizeof(struct obj_super) 694/* Note: obj_dentry objects do NOT have a common header */ 695#define BILBYFS_DENTRY_SZ sizeof(struct obj_dentry) 696#define BILBYFS_DEL_SZ sizeof(struct obj_del) 697#define BILBYFS_SUM_SZ sizeof(struct obj_sum) 698#define BILBYFS_SUM_ENTRY_SZ sizeof(struct obj_sum_entry) 699 700/* BILBYFS_BLOCK_SIZE: Block granularity of the index and maximum amount 701 * of data attached to a obj_data. 702 */ 703#define BILBYFS_BLOCK_SIZE 4096 704#define BILBYFS_BLOCK_SHIFT 12 705 706/* Maximum object size (must all be aligned on 8) */ 707#define BILBYFS_MAX_DATA_SZ (BILBYFS_DATA_SZ + BILBYFS_BLOCK_SIZE) 708#define BILBYFS_MAX_DENTRY_SZ (BILBYFS_DENTRY_SZ + BILBYFS_MAX_NLEN + 1) 709/* Maximum number of entries stored in a dentarr. 710 * We put this limitation to ensure that all transactions fits in a leb even 711 * in the worst case scenario. 712 */ 713#define BILBYFS_MAX_DENTARR_ENTRIES 16 714#define BILBYFS_MAX_DENTARR_SZ (BILBYFS_DENTARR_SZ + \ 715 BILBYFS_MAX_DENTARR_ENTRIES * BILBYFS_MAX_DENTRY_SZ) 716/* dentarr clearly has the biggest obj size */ 717#define BILBYFS_MAX_OBJ_SZ BILBYFS_MAX_DENTARR_SZ 718#define BILBYFS_MIN_OBJ_SZ BILBYFS_CH_SZ 719 720/* Maximum number of object in one transaction 721 * A transaction can span a whole erase-block, hence this number should 722 * be large enough to commodate this 723 */ 724#define BILBYFS_MAX_OBJ_PER_TRANS 2048 725 726#define BILBYFS_LAST_INUM 0xFFFFFF00 /* max inode number */ 727 728static inline int obj_dentry_size(struct obj_dentry *de) 729{ 730 return BILBYFS_DENTRY_SZ + le16_to_cpu(de->nlen) + 1; 731} 732 733static inline int obj_dentarr_size(struct obj_dentarr *dearr) 734{ 735 return (!le32_to_cpu(dearr->size) ? BILBYFS_DENTARR_SZ : le32_to_cpu(dearr->size)); 736} 737 738static inline int obj_dentry_size_from_nm(const char *name) 739{ 740 return BILBYFS_DENTRY_SZ + strlen(name) + 1; 741} 742 743static inline int obj_dentarr_size_with_nm(struct obj_dentarr *dentarr, 744 const char *name) 745{ 746 return obj_dentarr_size(dentarr) + obj_dentry_size_from_nm(name); 747} 748 749static inline int obj_data_size_with_data(int data_size) 750{ 751 return BILBYFS_DATA_SZ + data_size; 752} 753 754static inline int obj_sum_size(struct obj_sum *sum) 755{ 756 return ALIGN(BILBYFS_SUM_SZ + le32_to_cpu(sum->nb_sum_entry) * BILBYFS_SUM_ENTRY_SZ + BILBYFS_OBJ_SUM_OFFS_SZ, BILBYFS_OBJ_PADDING); 757} 758 759/* struct bilbyfs_info: 760 * @vfs_sb: VFS superblock structure 761 * @ubi: UBI volume descriptor 762 * @di: UBI device information 763 * @vi: UBI volume information 764 * @next_inum: next inode number to use 765 * @next_sqnum: next sequence number to use 766 * @is_ro: Is the FS in read-only mode? 767 * @wbuf: write-buffer for writing objects in a transaction 768 * @rbuf: read-buffer to store an entire leb 769 * @super: super block structure 770 * @super_offs: superblock on-flash address 771 * @dirty_list: a list containing how much garbage each erase-block has 772 * @used_leb_list: a list indicating whether an erase-block is used 773 * @fsm_lnum: lnum of currently active LEB 774 * @fsm_offs: offset of next free space in currently active LEB 775 * @gc_buf: buffer for garbage collection 776 * @no_summary: mount option value 777 */ 778struct bilbyfs_info { 779 struct wrapper_data wd; 780 /* VFS specific */ 781 struct super_block *vfs_sb; 782 /* UBI */ 783 struct ubi_volume_desc *ubi; 784 struct ubi_device_info di; 785 struct ubi_volume_info vi; 786 /* BilbyFs */ 787 /* FsOp */ 788 u32 next_inum; 789 u64 next_sqnum; 790 u32 is_ro; 791 struct bilbyfs_dirent dirent; 792 struct obj_data *odata; 793 /* Index */ 794 struct rbt_root *idx_hash; 795 /* Wbuf */ 796 struct bilbyfs_wbuf wbuf; 797 struct bilbyfs_rbuf rbuf; 798 /* Ostore */ 799 struct bilbyfs_super super; 800 struct bilbyfs_wbuf sup_wbuf; 801 int super_offs; 802 struct alloc_pool node_pool; 803 struct obj_sum *summary; 804 struct obj_addr *addrs; 805 u32 is_mounting; 806 807 /* FSM */ 808 u32 *dirty_list; 809 u8 *used_leb_list; 810 u32 fsm_lnum; 811 u32 fsm_nb_free_eb; 812 /* GIM */ 813 struct rbt_root *gim_hash; 814 /* GC */ 815 struct bilbyfs_rbuf gc_buf; 816 /* Mount */ 817 int no_summary; 818 int nb_pages; 819 int nb_extra_pages; 820 int gim_allocated_for_nothing; 821}; 822 823/** 824 * next_sqnum: obtain a unique sequence number. 825 * @bi: global fs info 826 * This function returns an unique sequence number and 827 * should be the only function accessing @bi->next_sqnum. 828 */ 829static inline u64 next_sqnum(struct bilbyfs_info *bi) 830{ 831 bi->next_sqnum++; 832 return bi->next_sqnum; 833} 834 835/** 836 * next_inum: obtain a unused inode number. 837 * @bi: global fs info 838 * This function returns an unused inode number and 839 * should be the only function accessing @bi->next_inum. 840 */ 841static inline u32 next_inum(struct bilbyfs_info *bi) 842{ 843 bi->next_inum++; 844 return bi->next_inum; 845} 846 847/** 848 * inode_current_time - round current time to time granularity. 849 * @inode: inode 850 */ 851struct timespec64 inode_current_time(struct inode *inode); 852 853/* ReadDir ConteXt: This component helps to list a inline diretory by sequentially 854 * reading all directory entries in a directory. 855 * 856 * fsop_readdir_ctx: current position of the directory listing. 857 * @dentarr: current dentarr evaluated. 858 * @de: current diretory entry in the dentarr 859 * @id: id of the current dentarr; 860 */ 861struct fsop_readdir_ctx { 862 struct obj_dentarr *dentarr; 863 struct obj_dentry *de; 864 obj_id id; 865}; 866 867/* rdx_init: initialise a readdir context 868 * @bi: global fs info 869 * @rdx: context holder 870 * @ino: inode number of the directory to list 871 */ 872void rdx_init(struct bilbyfs_info *bi, struct fsop_readdir_ctx *rdx, ino_t ino); 873 874/* rdx_clean: clean a readdir context by freeing the potentially allocated 875 * dentarr. 876 * @bi: global fs info 877 * @rdx: context holder 878 */ 879void rdx_clean(struct fsop_readdir_ctx *rdx); 880 881/* rdx_next_dentry: obtain the next directory entry given a context. 882 * dentarr. 883 * @bi: global fs info 884 * @rdx: context holder 885 */ 886struct obj_dentry *rdx_next_dentry(struct bilbyfs_info *bi, struct fsop_readdir_ctx *rdx); 887 888/* File System Operations (fsop) component: 889 * This component implements all the logic of the file system. 890 * It only manipulates objects using their ID, every filesystem operation is 891 * implemented as a list of objects modifications. 892 * 893 * See fsop.c. 894 */ 895 896/* fsop_iget: Read an inode from the disk. 897 * @bi: global fs info 898 * @inum: inode number to read 899 * @inode: inode pointer to store the result to 900 * 901 * The function returns a negative error code if unsuccessful and zero 902 * otherwise. 903 */ 904int fsop_iget(struct bilbyfs_info *bi, unsigned long inum, struct inode *inode); 905 906/* fsop_lookup: Inspect a directory to find a name 907 * @bi: global fs info 908 * @dir: inode of the directory to inspect 909 * @name: name of the file/directory to find 910 * @ino: pointer where to store the inode number 911 * 912 * fsop_lookup will look for the name specified by @dentry->d_name and store 913 * the inode number in the parameter @ino. 914 * The function returns a negative error code if unsuccessful and zero 915 * otherwise 916 */ 917int fsop_lookup(struct bilbyfs_info *bi, struct inode *dir, const char *name, ino_t *ino); 918 919/* fsop_link: Create a hardlink 920 * @bi: global fs info 921 * @inode: target inode 922 * @dir: source inode from which we want to add a directory entry 923 * @name: name of the link to create 924 * 925 * Add a link (directory entry) from @dir to @inode. The function 926 * has to deal with the nlink counters of inodes. The function returns a 927 * negative error code if unsuccessful and zero otherwise. 928 */ 929int fsop_link(struct bilbyfs_info *bi, struct inode *inode, struct inode *dir, const char *name); 930 931/* fsop_create: Create a file in a directory 932 * @bi: global fs info 933 * @dir: directory inode in which the file is created 934 * @name: name of the file to create 935 * @mode: permission, inode type... 936 * @excl: NFS specific exclusion flag? FIXME 937 * @inode: inode to fill 938 * 939 * If the function is successful it creates a file on disk in @dir and fill in 940 * information about the file in @inode. 941 * The function returns a negative error code if unsuccessful and zero 942 * otherwise. 943 */ 944int fsop_create(struct bilbyfs_info *bi, struct inode *dir, const char *name, 945 umode_t mode, int excl, struct inode *inode); 946 947/* fsop_unlink: Remove a hardlink from a file inode 948 * @bi: global fs info 949 * @dir: directory inode from which we remove a directory entry 950 * @name: name of the file to unlink 951 * @inode: inode to which @dentry points 952 * 953 * The function removes @dentry and decrements the nlink counter of the inode 954 * pointed by @dentry. If the counter reaches 0, the inode is removed as well 955 * The function returns a negative error code if unsuccessful and zero 956 * otherwise. 957 */ 958int fsop_unlink(struct bilbyfs_info *bi, struct inode *dir, const char *name, struct inode *inode); 959 960/* fsop_rmdir: Remove an entry from a directory 961 * @bi: global fs info 962 * @dir: directory inode from which we remove a directory entry 963 * @dentry: directory entry to remove 964 * @inode: inode to which @dentry points 965 * 966 * The function removes @dentry from the directory @dir. 967 * The function returns a negative error code if unsuccessful and zero 968 * otherwise. 969 */ 970int fsop_rmdir(struct bilbyfs_info *bi, struct inode *dir, const char *name, struct inode *inode); 971 972/* fsop_mkdir: Create a directory 973 * @bi: global fs info 974 * @dir: directory inode from which we create a directory entry 975 * @name: name of the directory to create 976 * @mode: permission... 977 * @inode: inode to fill 978 * 979 * The function removes @dentry from the directory @dir. 980 * The function returns a negative error code if unsuccessful and zero 981 * otherwise. 982 */ 983int fsop_mkdir(struct bilbyfs_info *bi, struct inode *dir, const char *name, umode_t mode, struct inode *inode); 984 985/* fsop_readdir: Read a directory sequentially 986 * @bi: global fs info 987 * @inode: directory inode 988 * @ctx: context for FS use 989 * The function returns a negative error code if unsuccessful and zero 990 * otherwise. 991 */ 992int fsop_readdir(struct bilbyfs_info *bi, struct inode *inode, struct dir_context *ctx, struct fsop_readdir_ctx **rdx); 993void fsop_dir_release(struct fsop_readdir_ctx *rdx); 994 995/* fsop_symlink: Create a symbolic link 996 * @bi: global fs info 997 * @dir: directory inode in which we create symlink 998 * @name: the name of the symlink 999 * @symname: path to which the symlink points 1000 * @inode: inode to fill 1001 * 1002 * If the function is successful it creates a symlink inode on disk 1003 * and fill in information about the symlink in @inode. The new symlink's 1004 * path is put into a data object pointed to by the inode. 1005 * The function returns a negative error code if unsuccessful and zero 1006 * otherwise. 1007 */ 1008int fsop_symlink(struct bilbyfs_info *bi, struct inode *dir, const char *name, const char *symname, struct inode *inode); 1009 1010/* fsop_rename: Change the name and parent for an inode 1011 * @bi: global fs info 1012 * @old_dir: parent directory inode of the source inode 1013 * @old_name: source inode to be renamed 1014 * @old_inode: inode to which @old_dentry points 1015 * @new_dir: parent directory inode for destination inode (can be the same as old_dir) 1016 * @new_name: new name for the destination inode 1017 * @new_inode: destination inode, can be null if destination inode is the same as source inode 1018 * 1019 * The function returns a negative error code if unsuccessful and zero 1020 * otherwise. 1021 */ 1022int fsop_rename(struct bilbyfs_info *bi, struct inode *old_dir, const char *old_name, 1023 struct inode *old_inode, struct inode *new_dir, const char *new_name, 1024 struct inode *new_inode); 1025 1026/* fsop_readpage: Read a page (could be multiple blocks) from a file inode 1027 * @bi: global fs info 1028 * @inode: file inode we read a page from 1029 * @block: block index in the file 1030 * @addr: address to store read data to 1031 * 1032 * The function returns a negative error code if unsuccessful and zero 1033 * otherwise. 1034 */ 1035int fsop_readpage(struct bilbyfs_info *bi, struct inode *inode, pgoff_t block, void *addr); 1036 1037/* fsop_write_begin: Read pages overlapping range of data for a future write 1038 * @bi: global fs info 1039 * @inode: file inode we read a page from 1040 * @pos: position in file from which we want to write 1041 * @len: number of bytes we want to write 1042 * @addr: address to store read data to 1043 * 1044 * Storage devices only allow to write data by blocks (e.g. 4096 bytes), so 1045 * this function is meant to read data that is needed to be able to update the 1046 * file from offset @pos to @pos + @len. 1047 * The function returns a negative error code if unsuccessful and zero 1048 * otherwise. 1049 */ 1050int fsop_write_begin(struct bilbyfs_info *bi, struct inode *inode, int pos, int len, void *addr); 1051 1052/* fsop_write_end: Write file data to disk 1053 * @bi: global fs info 1054 * @inode: file inode we read a page from 1055 * @pos: position in file from which we want to write 1056 * @len: number of bytes we want to write 1057 * @addr: address to store read data to 1058 * 1059 * This function writes back the actual @file's data stored in @addr to disk. 1060 * The function returns a negative error code if unsuccessful and zero 1061 * otherwise. 1062 */ 1063int fsop_write_end(struct bilbyfs_info *bi, struct inode *inode, int pos, int len, void *addr); 1064 1065/* fsop_follow_link: Read a symbolic link inode 1066 * @bi: global fs info 1067 * @inode: inode in which the path is stored 1068 * @path: pointer where to store the path read 1069 * 1070 * The function returns a negative error code if unsuccessful and zero 1071 * otherwise. 1072 */ 1073int fsop_follow_link(struct bilbyfs_info *bi, struct inode *inode, char *path); 1074 1075/* fsop_setattr: Set attributes of an inode (file/directory/symlink) 1076 * @bi: global fs info 1077 * @dentry: inode to modify 1078 * @attr: attributes to modify and their new value 1079 * 1080 * This function also handles truncate, which is just an inode size 1081 * modification. 1082 * The function returns a negative error code if unsuccessful and zero 1083 * otherwise. 1084 */ 1085int fsop_setattr(struct bilbyfs_info *bi, struct inode *inode, struct iattr *attr); 1086 1087/* fsop_getattr: Read inode attributes 1088 * @bi: global fs info 1089 * @inode: inode to read 1090 * @stat: stat structure to fill 1091 * 1092 * The function returns a negative error code if unsuccessful and zero 1093 * otherwise. 1094 */ 1095int fsop_getattr(struct bilbyfs_info *bi, struct inode *inode, struct kstat *stat); 1096 1097/* fsop_evict_inode: Inode cache eviction 1098 * @bi: global fs info 1099 * @inode: inode to evict 1100 * 1101 * If the OS caches inodes, fsop_evict_inode will be called when the OS decides 1102 * to remove the inode from the cache. 1103 * The function returns a negative error code if unsuccessful and zero 1104 * otherwise. 1105 */ 1106void fsop_evict_inode(struct bilbyfs_info *bi, struct inode *inode); 1107 1108/* fsop_evict_inode: Get statistic about the FS 1109 * @bi: global fs info 1110 * @kstat: kstat structure to fill 1111 * 1112 * This function enables reporting the amount of free space available among 1113 * other stats. 1114 * The function returns a negative error code if unsuccessful and zero 1115 * otherwise. 1116 */ 1117int fsop_statfs(struct bilbyfs_info *bi, struct kstatfs *kstat); 1118 1119int fsop_budget_data_update(struct bilbyfs_info *bi); 1120void fsop_budget_cancel_data_update(struct bilbyfs_info *bi); 1121 1122/* fsop_sync_fs: Synchronise the FS to disk 1123 * @bi: global fs info 1124 * @sb: superblock data structure 1125 * @wait: flag indicated whether the function is allowed to wait 1126 * 1127 * The function returns a negative error code if unsuccessful and zero 1128 * otherwise. 1129 */ 1130int fsop_sync_fs(struct bilbyfs_info *bi, struct super_block *sb, int wait); 1131 1132/* fsop_test_is_mount: Check whether the FS is already mounted 1133 * @bi1: global fs info 1134 * @bi2: global fs info 1135 * 1136 * The function returns 0 if the FS is not already mounted, 1 otherwise. 1137 */ 1138int fsop_test_is_mount(struct bilbyfs_info *bi1, struct bilbyfs_info *bi2); 1139 1140/* fsop_fill_super: Read the super block and fills the structure 1141 * @bi: global fs info 1142 * @sb: super block to fill 1143 * @silent: flag indicated whether the FS should print error messages or not 1144 * @rootino: pointer to an inode number 1145 * 1146 * The function must read the super block and find the root inode number. 1147 * If successful the function set the root inode number in @rootino and 1148 * returns 0. A negative error code is returned in case of failure. 1149 */ 1150int fsop_fill_super(struct bilbyfs_info *bi, struct super_block *sb, int silent, ino_t *rootino, struct inode *root); 1151 1152/* fsop_init: Initialise the FS 1153 * @bi: global fs info 1154 * @name: mount command line device name 1155 * @bd_name: backing device name to be filled 1156 * 1157 * The function allocates vital FS data structures and open the storage 1158 * device. The @bd_name must be filled with the backing device name. 1159 * The function returns a negative error code in case of failure, 0 otherwise. 1160 */ 1161int fsop_init(struct bilbyfs_info *bi, const char *name, char *bd_name); 1162 1163/* fsop_umount: unmount the fs 1164 * @bi: global fs info 1165 * 1166 * this function must deallocate most data structures allocated in init. 1167 */ 1168void fsop_unmount(struct bilbyfs_info *bi); 1169 1170/* fsop_clean: Free the remaining data structures left allocated by unmount 1171 * @bi: global fs info 1172 */ 1173void fsop_clean(struct bilbyfs_info *bi); 1174 1175/* Linux Helpers */ 1176struct ubi_volume_desc *open_ubi(const char *name, int mode); 1177 1178/* 1179 * Object Store () component: 1180 * Reading/Writing objects from their id, writing is transactional using the 1181 * `trans' propertry stored in objects' header. 1182 */ 1183 1184/* ostore_init: Initialise Ostore component 1185 * @bi: global fs info 1186 * 1187 */ 1188int ostore_init(struct bilbyfs_info *bi); 1189 1190/* ostore_clean: Clean up Ostore component 1191 * @bi: global fs info 1192 * 1193 */ 1194void ostore_clean(struct bilbyfs_info *bi); 1195 1196/* ostore_get_obj_size: request the size of an object 1197 * @bi: global fs info 1198 * @id: id of the object 1199 * 1200 * This function returns the size of an object or a negative error code. 1201 */ 1202int ostore_get_obj_size(struct bilbyfs_info *bi, obj_id id); 1203 1204/* ostore_read_obj: read an obj using its id 1205 * @bi: global fs info 1206 * @id: id of the object 1207 * @buf: buffer to store data in 1208 * @len: size of the buffer 1209 * 1210 * It is possible to read an object before, after and while a transaction. 1211 * ostore_read_obj will only return an object written once the transaction 1212 * has been commited. 1213 * Return non-zero value if it fails. 1214 */ 1215int ostore_read_obj(struct bilbyfs_info *bi, obj_id id, void *buf, u32 len); 1216 1217enum { OSW_NONE = 0, 1218 OSW_DEL = 1, 1219 OSW_GC = 2, 1220 OSW_SYNC = 4, 1221}; 1222 1223/* ostore_write_obj_list: write objects in the list to disk 1224 * @bi: global fs info 1225 * @obj_list: an array of objects to write, the header must be complete and 1226 * the object cannot be modified as its CRC has been calculated. 1227 * @count: number of objects in the list 1228 * @write_flag: OSW_NONE, OSW_DEL (Deletion), OSW_GC (Garbage Collection) 1229 * 1230 * This function will writes all the objects in the list into the disk 1231 * in one single transaction. 1232 * 1233 * Note that this function will set the object command header 1234 * according to their position in the transaction 1235 * 1236 * A successful execution is indicated by a return value of 0. 1237 * A failure is indicated by a negative error-code. 1238 * 1239 */ 1240int ostore_write_obj_list(struct bilbyfs_info *bi, void **obj_list, int count, int write_flag); 1241int ostore_sync(struct bilbyfs_info *bi, int force_summary); 1242 1243/* ostore_erase: Erase an erase-block 1244 * @bi: global fs info 1245 * @lnum: LEB number of the erase-block 1246 */ 1247int ostore_erase(struct bilbyfs_info *bi, int lnum); 1248 1249/* ostore_scan_obj: Scan an erase-block and build a list of objects in the block 1250 * @bi: global fs info 1251 * @rbuf: buffer used to store the objects 1252 * @lnum: LEB number of the erase-block 1253 * @list: list to store object addresses in the buffer 1254 * @max_count: maximum number of objects the list can store 1255 * 1256 * This function return the number of object in the erase block 1257 * It also return a negative error code if unsuccessful 1258 */ 1259int ostore_scan_obj(struct bilbyfs_info *bi, struct bilbyfs_rbuf *rbuf, int lnum, 1260 void **list, int max_count); 1261int ostore_scan_leb_obj(struct bilbyfs_info *bi, struct bilbyfs_rbuf *rbuf, int lnum, 1262 void **list, int max_count); 1263 1264/* ostore_next_obj_id: return the next id from an id 1265 * @bi: global fs info 1266 * @id: id of the object 1267 * 1268 * This function just calls tix_next_obj_id, see def for doc. 1269 */ 1270obj_id ostore_next_obj_id(struct bilbyfs_info *bi, obj_id id); 1271 1272/* ostore_mount: scan the media and initialises underlying components 1273 * @bi: global fs info 1274 * 1275 * This function initialises fsm and tindex components by scanning 1276 * and reading all objects present on the media. 1277 */ 1278int ostore_mount(struct bilbyfs_info *bi); 1279 1280/* ostore_unmount: free all memory allocated by trans. 1281 * @bi: global fs info 1282 * 1283 * This function frees all the memory allocated by trans. 1284 */ 1285void ostore_unmount(struct bilbyfs_info *bi); 1286 1287/* ostore_get_free_space: returns how much free space available on the media 1288 * @bi: global fs info 1289 */ 1290unsigned long long ostore_get_free_space(struct bilbyfs_info *bi); 1291unsigned long long ostore_get_available_space(struct bilbyfs_info *bi); 1292 1293/* ostore_write_super: update the superblock on-flash 1294 * @bi: global fs info 1295 * 1296 * This function is used by mount() to store the initial super-block. 1297 * The function ostore_unmount() also implicitly call it. 1298 * The function returns a negative error-code in case of failure. 1299 */ 1300int ostore_write_super(struct bilbyfs_info *bi); 1301 1302/* 1303 * Write Buffer component: 1304 * Reading/Writing objects in a buffer that is then flushed by wbuf_commit(). 1305 */ 1306 1307/* wbuf_init: initialise wbuf component 1308 * @bi: global fs info 1309 */ 1310int wbuf_init(struct bilbyfs_info *bi); 1311 1312/* wbuf_clean: clean-up wbuf component 1313 * @bi: global fs info 1314 */ 1315void wbuf_clean(struct bilbyfs_info *bi); 1316 1317/* wbuf_start: initialise bi->wbuf for a transaction 1318 * @bi: global fs info 1319 */ 1320void wbuf_start(struct bilbyfs_info *bi, struct bilbyfs_wbuf *wbuf); 1321 1322/* wbuf_read_obj: read an obj from wbuf if in cache or from UBI otherwise. 1323 * @bi: global fs info 1324 * @buf: buffer to store data in 1325 * @addr: object's address 1326 * 1327 */ 1328int wbuf_read_obj(struct bilbyfs_info *bi, void *buf, struct obj_addr *addr); 1329 1330/* wbuf_write_obj: write an object in a group 1331 * @bi: global fs info 1332 * @buf: buffer where to get data to write. 1333 * @wbuf: write-buffer to use 1334 * This function returns 0 if the object has been added to the transaction. 1335 */ 1336int wbuf_write_obj(struct bilbyfs_info *bi, void *buf, int len, struct bilbyfs_wbuf *wbuf); 1337 1338/* wbuf_prepare_commit: prepare (padding) the wbuf for a commit 1339 * @bi: global fs info 1340 * @paading_sz: when function return, amount of padding will be stored 1341 * if set to NULL, no value will be stored 1342 * @wbuf: write-buffer to use 1343 * 1344 * This function never fails, it always returns the size of the transaction 1345 * including padding in bytes. 1346 */ 1347int wbuf_prepare_commit(struct bilbyfs_info *bi, u32 *padding_sz, struct bilbyfs_wbuf *wbuf); 1348 1349 1350/* wbuf_commit: commit the buffer on-flash 1351 * @bi: global fs info 1352 * @lnum: LEB to write to 1353 * @wbuf: write-buffer to use 1354 * 1355 * The function either succeed or fail, if the returned value is greater than 1356 * 0, it means that the entire transaction has been successfully flushed 1357 * on-flash and the return value is the number of bytes written to the LEB. 1358 * In case of failure the function returns a negative error-code. 1359 * 1360 */ 1361int wbuf_commit(struct bilbyfs_info *bi, u32 lnum, struct bilbyfs_wbuf *wbuf); 1362 1363/* wbuf_atom_leb_commit: update an LEB on flash atomically 1364 * @bi: global fs info 1365 * @lnum: LEB to update 1366 * @wbuf: write-buffer to use 1367 * 1368 * This function overwrites @leb regardless of the current status of LEB, 1369 * it enssentially unmap the leb and map to an empty one to write the data. 1370 * This operation is quite slow and should only be used when strictly 1371 * necessary. 1372 * 1373 * In case of failure the function returns a negative error-code. 1374 * 1375 */ 1376int wbuf_atom_leb_commit(struct bilbyfs_info *bi, int lnum, struct bilbyfs_wbuf *wbuf); 1377 1378/* wbuf_read_leb: Reads an entire LEB in memory 1379 * @bi: global fs info 1380 * @lnum: LEB number to read 1381 * @rbuf: read-buffer where to store the data read 1382 * 1383 * This function returns a negative error-code if unsuccessful. 1384 */ 1385int wbuf_read_leb(struct bilbyfs_info *bi, int lnum, struct bilbyfs_rbuf *rbuf); 1386int wbuf_read_leb_fast(struct bilbyfs_info *bi, int lnum, struct bilbyfs_rbuf *rbuf); 1387 1388/* wbuf_read_sum: Reads pages covering the summary object and returns offset in 1389 * @sum_offs_ret 1390 * @bi: global fs info 1391 * @lnum: LEB number to read 1392 * @rbuf: read-buffer where to store the data read 1393 * @sum_offs_ret: pointer used to store the offset of the summary object. 1394 * 1395 * This function returns a negative error-code if unsuccessful. 1396 */ 1397int wbuf_read_sum(struct bilbyfs_info *bi, int lnum, struct bilbyfs_rbuf *rbuf, u32 *sum_offs_ret); 1398 1399/* wbuf_erase: Erase an earse-block 1400 * @bi: global fs info 1401 * @lnum: LEB number of the erase-block 1402 */ 1403int wbuf_erase(struct bilbyfs_info *bi, int lnum); 1404 1405/* wbuf_next_obj_addr: Find the next object in a read-buffer 1406 * @bi: global fs info 1407 * @addr: address to start from 1408 * @rbuf: read-buffer to analyse 1409 * 1410 * Read the next object present in a LEB starting from 1411 * addr->offs + addr->len in LEB addr->lnum. 1412 * 1413 * If there isn't any object present in the LEB the function 1414 * returns %-ENOENT. In this case addr is unchanged. 1415 * 1416 * If addr->len = 0, as the function cannot find the next object, 1417 * it will return the object at addr->offs if one exists. 1418 * 1419 * This function is needed to implement the mount operation and the 1420 * transaction commit operation. 1421 * We use it to perform the initial media scanning to populate the 1422 * components fsm and index. 1423 * We also use it to update the index & fsm components when the 1424 * transaction in progress has been committed on-flash. 1425 * 1426 * This function returns a pointer to the next object if successful and 1427 * writes the address of the next object stored on the media in @addr. 1428 * If unsuccessful it returns %-ENOENT as mentionned above. 1429 */ 1430void *wbuf_next_obj_addr(struct bilbyfs_info *bi, struct obj_addr *addr, 1431 struct bilbyfs_rbuf *rbuf); 1432 1433/* 1434 * Object pool component: Preallocates tree nodes to protect against 1435 * memory allocation errors in critical section of the FS where not 1436 * updating an in-memory data structure would lead to an inconsistency 1437 * between the in-mem state and on-disk state. 1438 */ 1439int allocpool_init(struct alloc_pool *pool); 1440void allocpool_destroy(struct alloc_pool *pool); 1441int allocpool_alloc(struct alloc_pool *pool, int sz_pool, int sz_obj); 1442void allocpool_empty(struct alloc_pool *pool); 1443void *allocpool_pop(struct alloc_pool *pool); 1444void allocpool_free_single(void *p); 1445 1446/* 1447 * Free Space Management (fsm) component: 1448 * Find logical erase-blocks with enough free space for wbuf's purpose. 1449 */ 1450 1451/* fsm_init: initialise the fsm component 1452 * @bi: global fs info 1453 */ 1454int fsm_init(struct bilbyfs_info *bi); 1455 1456 1457/* fsm_clean: clean-up the fsm component 1458 * @bi: global fs info 1459 */ 1460void fsm_clean(struct bilbyfs_info *bi); 1461 1462/* fsm_alloc_eb: find a leb with @req_size free space to write objects. 1463 * @bi: global fs info 1464 * @osw_flag: Flags helping choosing erase-blocks to allocate 1465 * 1466 * This function returns a leb number >0 if successful or a negative error code. 1467 */ 1468int fsm_alloc_eb(struct bilbyfs_info *bi, int osw_flag); 1469 1470/* fsm_get_lnum: return current leb allocated 1471 * @bi: global fs info 1472 */ 1473u32 fsm_get_lnum(struct bilbyfs_info *bi); 1474 1475/* fsm_mark_dirty: mark the address of an object as dirty space for garbage 1476 * collection. 1477 * @bi: global fs info 1478 * @addr: address of the dirty object 1479 * 1480 */ 1481void fsm_mark_dirty(struct bilbyfs_info *bi, struct obj_addr *addr); 1482 1483/* fsm_mark_used: mark a leb as used 1484 * @bi: global fs info 1485 * @lnum: which LEB 1486 */ 1487void fsm_mark_used(struct bilbyfs_info *bi, int lnum); 1488 1489/* fsm_mark_erased: Mark the erase-block as empty 1490 * @bi: global fs info 1491 * @lnum: LEB number of the erase-block that has been erased 1492 */ 1493void fsm_mark_erased(struct bilbyfs_info *bi, int lnum); 1494 1495/* fsm_get_free_space: returns how much free space available on the media 1496 * @bi: global fs info 1497 */ 1498unsigned long long fsm_get_free_space(struct bilbyfs_info *bi); 1499unsigned long long fsm_get_available_space(struct bilbyfs_info *bi); 1500 1501/* fsm_get_dirtiest_eb: get erase-block with most garbage 1502 * @bi: global fs info 1503 * 1504 * This function return erase-block logical number if the dirtiest 1505 * erase-block is found. 1506 * It returns -1 if no block is found 1507 */ 1508int fsm_get_dirtiest_eb(struct bilbyfs_info *bi); 1509/* Red-Black tree component 1510 */ 1511 1512 1513#define rbt_parent(r) ((struct rbt_node *)((r)->rbt_parent_color & ~3)) 1514#define rbt_color(r) ((r)->rbt_parent_color & 1) 1515#define rbt_is_red(r) (!rbt_color(r)) 1516#define rbt_is_black(r) rbt_color(r) 1517#define rbt_set_red(r) do { (r)->rbt_parent_color &= ~1; } while (0) 1518#define rbt_set_black(r) do { (r)->rbt_parent_color |= 1; } while (0) 1519 1520static inline void rbt_set_parent(struct rbt_node *rb, struct rbt_node *p) 1521{ 1522 rb->rbt_parent_color = (rb->rbt_parent_color & 3) | (unsigned long)p; 1523} 1524static inline void rbt_set_color(struct rbt_node *rb, int color) 1525{ 1526 rb->rbt_parent_color = (rb->rbt_parent_color & ~1) | color; 1527} 1528 1529#define RBT_ROOT (struct rbt_root) { NULL, } 1530#define rbt_entry(ptr, type, member) container_of(ptr, type, member) 1531 1532#define RBT_EMPTY_ROOT(root) ((root)->rbt_node == NULL) 1533#define RBT_EMPTY_NODE(node) (rbt_parent(node) == node) 1534#define RBT_CLEAR_NODE(node) (rbt_set_parent(node, node)) 1535 1536void rbt_insert_color(struct rbt_node *, struct rbt_root *); 1537struct rbt_node *rbt_first(const struct rbt_root *root); 1538void rbt_erase(struct rbt_node *, struct rbt_root *); 1539void rbt_link_node(struct rbt_node * node, struct rbt_node * parent, 1540 struct rbt_node ** rbt_link); 1541 1542/* 1543 * Index functions: 1544 * The index caches the address of an object to avoid scanning the entire 1545 * disk to find the object. 1546 */ 1547 1548/* idx_init: Initialise Index component 1549 * @bi: global fs info 1550 * 1551 */ 1552int idx_init(struct bilbyfs_info *bi); 1553 1554/* idx_clean: Clean up Index component 1555 * @bi: global fs info 1556 * 1557 */ 1558void idx_clean(struct bilbyfs_info *bi); 1559 1560/* idx_get_obj_addr: retrieve the address of an object from the index. 1561 * @bi: global fs info 1562 * @id: id of the object 1563 * @addr: obj_addr struct to store the object's address in. 1564 * 1565 * This function returns 0 if the object was found in the index and addr is set. 1566 * A negative error code is return otherwise, including -ENOENT if the object 1567 * wasn't found. 1568 */ 1569int idx_get_obj_addr(struct bilbyfs_info *bi, obj_id id, struct obj_addr *addr); 1570struct idx_node *idx_get_or_create_obj_addr_node(struct bilbyfs_info *bi, obj_id id); 1571 1572/* idx_set_obj_addr: sets the address of an object designated by @id 1573 * @id: id of the object 1574 * @addr: address to store for the id 1575 * @node: preallocated node that is freed by the function if unused. 1576 * 1577 * This function always returns 0. 1578 */ 1579int idx_set_obj_addr(struct bilbyfs_info *bi, obj_id id, struct obj_addr *addr, struct idx_node *node); 1580 1581/* idx_next_obj_id: returns the next id stored in the index. 1582 * An id can be interpreted as a u64 and therefore each object is ordered 1583 * using this interpretation. 1584 * If there is no id greater than @id stored in the index, the function 1585 * returns ~0 1586 * @bi: global fs info 1587 * @id: id of the object 1588 */ 1589obj_id idx_next_obj_id(struct bilbyfs_info *bi, obj_id id); 1590 1591/* idx_del_obj_addr: delete an object address from the index. 1592 * @bi: global fs info 1593 * @id: id of the object 1594 * 1595 * The function returns the removed node. 1596 * The function cannot be called if the node doesn't exists, doing so 1597 * will break an assertion check. 1598 */ 1599void *idx_del_obj_addr(struct bilbyfs_info *bi, obj_id id); 1600 1601 1602/* 1603 * DentArr component: Ideally we would store directory entry directly in the 1604 * index and retrieve entries as we need. In practice, object IDs are limited 1605 * in size (64 bits) and we cannot store the entire name attached to an 1606 * directory entry in the object ID. Accessing a directory entry by name is 1607 * required for the ->lookup() operation to be efficient. 1608 * Therefore we only store a hash of the name in object IDs and we deal with 1609 * collisions by storing arrays of directory entry (dentarr) in the index. 1610 */ 1611/* dentarr_add_dentry: adds a directory entry in a dentarr 1612 * @bi: global fs info 1613 * @dentarr: dentarr where to add the directory entry 1614 * @inode: inode to initialise the dentry with 1615 * @name: name to initialise the dentry with 1616 * 1617 * The function can return -ENAMETOOLONG if the maximum number of collision for 1618 * a name in a directory has been reached. 1619 * Otherwise the function returns the size in bytes of the directory entry 1620 * freshly added. 1621 */ 1622int dentarr_add_dentry(struct bilbyfs_info *bi, struct obj_dentarr *dentarr, 1623 struct inode *inode, const char *name); 1624 1625/* dentarr_del_dentry: deletes a directory entry from a dentarr 1626 * @bi: global fs info 1627 * @dentarr: dentarr where to add the directory entry 1628 * @name: name to delete 1629 * 1630 * This function can return -ENOMEM as error, when successul it returns 1631 * the number of bytes removed from the dentarr. 1632 * If the name was not found in the dentarr, the function returns 0. 1633 */ 1634int dentarr_del_dentry(struct bilbyfs_info *bi, struct obj_dentarr *dentarr, 1635 const char *name); 1636 1637/* dentarr_check_empty: checks whether a dentarr is empty 1638 * @bi: global fs info 1639 * @dentarr: dentarr to examine 1640 * 1641 * This function return -ENOTEMPTY if the dentarr is not empty otherwise 0 is 1642 * returned. 1643 */ 1644int dentarr_check_empty(struct bilbyfs_info *bi, struct obj_dentarr *dentarr); 1645 1646/* dentarr_lookup_nm: lookup a name in a `directory entry array' 1647 * @bi: global fs info 1648 * @darr: directory entry array object 1649 * @name: name to lookup 1650 * 1651 * The function returns a pointer to the obj_dentry if the entry was found, 1652 * %-ENOENT if the name was not found and a negative error code otherwise. 1653 */ 1654struct obj_dentry *dentarr_lookup_nm(struct bilbyfs_info *bi, 1655 struct obj_dentarr *dentarr, 1656 const char *name); 1657struct obj_dentry *dentarr_first_dentry(struct obj_dentarr *dentarr); 1658struct obj_dentry *dentarr_next_dentry(struct obj_dentarr *dentarr, 1659 struct obj_dentry *dentry); 1660/* dentarr_read: allocate and read a dentarr 1661 * @bi: global fs info 1662 * @id: id of the object to read 1663 * 1664 * This function returns a negative error code if the object 1665 * does not exist. 1666 */ 1667struct obj_dentarr *dentarr_read(struct bilbyfs_info *bi, obj_id id); 1668 1669/* dentarr_read_or_create: read a dentarr or create one if it doesn't exist. 1670 * @bi: global fs info 1671 * @id: id of the object to read 1672 * 1673 * If the function creates a new dentarr, it allocates the memory space for 1674 * a dentry. 1675 * This function returns a negative error code if an error happens. 1676 */ 1677struct obj_dentarr *dentarr_read_or_create(struct bilbyfs_info *bi, obj_id id); 1678 1679/* PackObj component: 1680 * 1681 * stateless component that prepares objects to be written on the med$a. 1682 */ 1683/** 1684 * pack_obj_header - prepare object header to be written to flash. 1685 * @obj: object pointer 1686 * @sqnum: sequence number to store in the object. 1687 * @trans_pos: position in transaction (%BILBYFS_TRANS_ST, ...) 1688 * 1689 * This function prepares an object headeer - it calculates the CRC and 1690 * fills the common header. 1691 */ 1692void pack_obj_header(void *obj, u64 sqnum, u8 trans_pos); 1693 1694/** 1695 * check_obj_header - check whether the pointer passed is an object header 1696 * @buf: object pointer 1697 * @max_obj_sz: maximum possible valid size of this object. 1698 * 1699 * The maximum possible object size must be calculated from the object offset 1700 * in a LEB (an object cannot spread over multiple LEBs). 1701 * It returns 0 if the pointer points to an object. 1702 */ 1703int check_obj_header(void *obj, int max_obj_sz); 1704 1705/** 1706 * pack_obj_inode - pack an inode object. 1707 * @ino: obj where to store the inode 1708 * @inode: inode to pack 1709 */ 1710void pack_obj_inode(struct obj_inode *ino, struct inode *inode); 1711 1712/** 1713 * pack_obj_dentarr - pack a dentarr object. 1714 * @dentarr: obj dentarr to pack 1715 * @id: id of the object to pack 1716 * @nbdentry: number of dentry embedded in the dentarr 1717 * @size: size in bytes of the dentarr object 1718 */ 1719void pack_obj_dentarr(struct obj_dentarr *dentarr, obj_id id, 1720 int nbdentry, int size); 1721 1722/** 1723 * pack_obj_data - pack a data object. 1724 * @odata: obj data to pack 1725 * @id: id of the object to pack 1726 * @sz_data: size of the data to store in the obj_data 1727 * @data: pointer to the data to store in the obj_data 1728 */ 1729void pack_obj_data(struct obj_data *odata, obj_id id, int sz_data, 1730 const void *data); 1731 1732/** 1733 * pack_obj_dentry - pack a dentry object. 1734 * @de: obj dentry to pack 1735 * @inode: inode the dentry is linked with 1736 * @name: name to store in the dentry 1737 */ 1738void pack_obj_dentry(struct obj_dentry *de, struct inode *inode, const char *name); 1739 1740/** 1741 * pack_obj_pad - pad a padding object. 1742 * @pad: padding object to pack 1743 * @pad_sz: padding size; 1744 */ 1745void pack_obj_pad(struct obj_ch *pad, int pad_sz); 1746 1747/** 1748 * unpack_obj_inode - unpack an inode object. 1749 * @inode: inode where to store the object inode 1750 * @ino: obj inode to unpack 1751 */ 1752void unpack_obj_inode(struct inode *inode, struct obj_inode *ino); 1753 1754/** 1755 * pack_obj_super - pack a super object. 1756 * @super: obj super to unpack 1757 * @bsuper: super object memory representation 1758 */ 1759void pack_obj_super(struct obj_super *super, const struct bilbyfs_super *bsuper); 1760 1761/** 1762 * unpack_obj_super - unpack a super object. 1763 * @bsuper: super in memory representation where to store the obj_super 1764 * @super: obj super to unpack 1765 */ 1766void unpack_obj_super(struct bilbyfs_super *bsuper, struct obj_super *super); 1767 1768/** 1769 * pack_obj_del - pack a deletion object 1770 * @obj: potentially a deletion object, but other objects can be casted to 1771 * deletion object as well 1772 * @id: object id of the object to be deleted 1773 */ 1774void pack_obj_del(void *obj, obj_id id); 1775 1776/** 1777 * pack_obj_sum - pack a summary object 1778 * @sum: summary object to pack 1779 * @offs: erase-block offset to at which the summary object itself lives. 1780 */ 1781void pack_obj_sum(struct obj_sum *sum, u32 offs); 1782 1783/** 1784 * GIM - garbage information manager 1785 * GIM manages the all information about garbage on disk. 1786 * It maintains dirty list which specify how much garbage each erase block has. 1787 * It also keep a garbage object list 1788 */ 1789/* gim_init: Initialise GIM component 1790 * @bi: global fs info 1791 */ 1792int gim_init(struct bilbyfs_info *bi); 1793 1794/* gim_clean: clean up GIM component 1795 * @bi: global fs info 1796 */ 1797void gim_clean(struct bilbyfs_info *bi); 1798 1799/* gim_mark_garbage: mark an object as garbage 1800 * @bi: global fs info 1801 * @id: object id 1802 * @addr: object address containing sequence number 1803 * @node: preallocated node that is freed by the function if not used. 1804 * 1805 * This function return negative error code upon failure 1806 */ 1807int gim_mark_garbage(struct bilbyfs_info *bi, obj_id id, struct obj_addr *addr, struct gim_node *node); 1808int gim_mark_garbage_cnt(struct bilbyfs_info *bi, obj_id id, struct obj_addr *addr, u32 count, struct gim_node *allocated_node); 1809 1810 1811/* gim_is_removable: determine if an object can be garbage collected 1812 * @bi: global fs info 1813 * @obj: object to be tested 1814 * 1815 * This function return a boolean indicate whether the garbage can be removed 1816 * from disk or not 1817 */ 1818int gim_is_removable(struct bilbyfs_info *bi, struct obj_ch *obj); 1819 1820/* gim_garbage_collected: mark as object has been garbage collected 1821 * @bi: global fs info 1822 * @obj: object that have been garbage collected 1823 * 1824 * This function return negative error code upon failure 1825 */ 1826int gim_garbage_collected(struct bilbyfs_info *bi, struct obj_ch *obj); 1827 1828/** 1829 * Garbage Collector 1830 */ 1831/* gc_init: Initialise the garbage collector 1832 * @bi: global fs info 1833 * 1834 * The function returns a negative error code in case of failure, 0 otherwise 1835 */ 1836int gc_init(struct bilbyfs_info *bi); 1837 1838/* gc_clean: Clean up GC component 1839 * @bi: global fs info 1840 */ 1841void gc_clean(struct bilbyfs_info *bi); 1842 1843/* gc_garbage_collect: Perform garbage collection 1844 * @bi: global fs info 1845 */ 1846int gc_garbage_collect(struct bilbyfs_info *bi); 1847 1848 1849/* Debug functions */ 1850void dump_sum_entry( struct obj_sum_entry *entry); 1851void dump_obj_addr( struct obj_addr *addr); 1852 1853#endif /* !__BILBYFS_H__ */ 1854