1 /* 2 * Copyright 2001-2017, Axel Dörfler, axeld@pinc-software.de. 3 * Parts of this code is based on work previously done by Marcus Overhagen. 4 * 5 * This file may be used under the terms of the MIT License. 6 */ 7 #ifndef BFS_H 8 #define BFS_H 9 10 11 //! BFS definitions and helper functions 12 13 14 #include "bfs_endian.h" 15 #include "system_dependencies.h" 16 17 18 #ifdef _BOOT_MODE 19 namespace BFS { 20 #endif 21 22 #ifndef _BOOT_MODE 23 extern fs_volume_ops gBFSVolumeOps; 24 extern fs_vnode_ops gBFSVnodeOps; 25 #endif 26 27 struct block_run { 28 int32 allocation_group; 29 uint16 start; 30 uint16 length; 31 32 int32 AllocationGroup() const 33 { return BFS_ENDIAN_TO_HOST_INT32(allocation_group); } 34 uint16 Start() const { return BFS_ENDIAN_TO_HOST_INT16(start); } 35 uint16 Length() const { return BFS_ENDIAN_TO_HOST_INT16(length); } 36 37 inline bool operator==(const block_run &run) const; 38 inline bool operator!=(const block_run &run) const; 39 inline bool IsZero() const; 40 inline bool MergeableWith(block_run run) const; 41 inline void SetTo(int32 group, uint16 start, uint16 length = 1); 42 43 inline static block_run Run(int32 group, uint16 start, uint16 length = 1); 44 // can't have a constructor because it's used in a union 45 } _PACKED; 46 47 typedef block_run inode_addr; 48 49 // Since the block_run::length field spans 16 bits, the largest number of 50 // blocks covered by a block_run is 65535 (as long as we don't want to 51 // break compatibility and take a zero length for 65536). 52 #define MAX_BLOCK_RUN_LENGTH 65535 53 54 //************************************** 55 56 57 #define BFS_DISK_NAME_LENGTH 32 58 59 struct disk_super_block { 60 char name[BFS_DISK_NAME_LENGTH]; 61 int32 magic1; 62 int32 fs_byte_order; 63 uint32 block_size; 64 uint32 block_shift; 65 int64 num_blocks; 66 int64 used_blocks; 67 int32 inode_size; 68 int32 magic2; 69 int32 blocks_per_ag; 70 int32 ag_shift; 71 int32 num_ags; 72 int32 flags; 73 block_run log_blocks; 74 int64 log_start; 75 int64 log_end; 76 int32 magic3; 77 inode_addr root_dir; 78 inode_addr indices; 79 int32 _reserved[8]; 80 int32 pad_to_block[87]; 81 // this also contains parts of the boot block 82 83 int32 Magic1() const { return BFS_ENDIAN_TO_HOST_INT32(magic1); } 84 int32 Magic2() const { return BFS_ENDIAN_TO_HOST_INT32(magic2); } 85 int32 Magic3() const { return BFS_ENDIAN_TO_HOST_INT32(magic3); } 86 int32 ByteOrder() const { return BFS_ENDIAN_TO_HOST_INT32(fs_byte_order); } 87 uint32 BlockSize() const { return BFS_ENDIAN_TO_HOST_INT32(block_size); } 88 uint32 BlockShift() const { return BFS_ENDIAN_TO_HOST_INT32(block_shift); } 89 off_t NumBlocks() const { return BFS_ENDIAN_TO_HOST_INT64(num_blocks); } 90 off_t UsedBlocks() const { return BFS_ENDIAN_TO_HOST_INT64(used_blocks); } 91 int32 InodeSize() const { return BFS_ENDIAN_TO_HOST_INT32(inode_size); } 92 int32 BlocksPerAllocationGroup() const 93 { return BFS_ENDIAN_TO_HOST_INT32(blocks_per_ag); } 94 int32 AllocationGroups() const { return BFS_ENDIAN_TO_HOST_INT32(num_ags); } 95 int32 AllocationGroupShift() const 96 { return BFS_ENDIAN_TO_HOST_INT32(ag_shift); } 97 int32 Flags() const { return BFS_ENDIAN_TO_HOST_INT32(flags); } 98 off_t LogStart() const { return BFS_ENDIAN_TO_HOST_INT64(log_start); } 99 off_t LogEnd() const { return BFS_ENDIAN_TO_HOST_INT64(log_end); } 100 101 // implemented in Volume.cpp: 102 bool IsValid() const; 103 void Initialize(const char *name, off_t numBlocks, uint32 blockSize); 104 } _PACKED; 105 106 #define SUPER_BLOCK_FS_LENDIAN 'BIGE' /* BIGE */ 107 108 #define SUPER_BLOCK_MAGIC1 'BFS1' /* BFS1 */ 109 #define SUPER_BLOCK_MAGIC2 0xdd121031 110 #define SUPER_BLOCK_MAGIC3 0x15b6830e 111 112 #define SUPER_BLOCK_DISK_CLEAN 'CLEN' /* CLEN */ 113 #define SUPER_BLOCK_DISK_DIRTY 'DIRT' /* DIRT */ 114 115 //************************************** 116 117 #define NUM_DIRECT_BLOCKS 12 118 119 struct data_stream { 120 block_run direct[NUM_DIRECT_BLOCKS]; 121 int64 max_direct_range; 122 block_run indirect; 123 int64 max_indirect_range; 124 block_run double_indirect; 125 int64 max_double_indirect_range; 126 int64 size; 127 128 off_t MaxDirectRange() const 129 { return BFS_ENDIAN_TO_HOST_INT64(max_direct_range); } 130 off_t MaxIndirectRange() const 131 { return BFS_ENDIAN_TO_HOST_INT64(max_indirect_range); } 132 off_t MaxDoubleIndirectRange() const 133 { return BFS_ENDIAN_TO_HOST_INT64(max_double_indirect_range); } 134 off_t Size() const 135 { return BFS_ENDIAN_TO_HOST_INT64(size); } 136 } _PACKED; 137 138 // This defines the size of the indirect and double indirect 139 // blocks. 140 #define NUM_ARRAY_BLOCKS 4 141 #define DOUBLE_INDIRECT_ARRAY_SIZE 4096 142 143 //************************************** 144 145 struct bfs_inode; 146 147 struct small_data { 148 uint32 type; 149 uint16 name_size; 150 uint16 data_size; 151 char name[0]; // name_size long, followed by data 152 153 uint32 Type() const 154 { return BFS_ENDIAN_TO_HOST_INT32(type); } 155 uint16 NameSize() const 156 { return BFS_ENDIAN_TO_HOST_INT16( 157 name_size); } 158 uint16 DataSize() const 159 { return BFS_ENDIAN_TO_HOST_INT16( 160 data_size); } 161 162 inline char* Name() const; 163 inline uint8* Data() const; 164 inline uint32 Size() const; 165 inline small_data* Next() const; 166 inline bool IsLast(const bfs_inode* inode) const; 167 } _PACKED; 168 169 // The file name is part of the small_data structure 170 #define FILE_NAME_TYPE 'CSTR' 171 #define FILE_NAME_NAME 0x13 172 #define FILE_NAME_NAME_LENGTH 1 173 174 // The maximum key length of attribute data that is put in the index. 175 // This excludes a terminating null byte. 176 // This must be smaller than or equal as BPLUSTREE_MAX_KEY_LENGTH. 177 #define MAX_INDEX_KEY_LENGTH 255 178 179 180 //************************************** 181 182 class Volume; 183 184 #define SHORT_SYMLINK_NAME_LENGTH 144 185 // length incl. terminating '\0' 186 187 #define INODE_MAGIC1 0x3bbe0ad9 188 #define INODE_FILE_NAME_LENGTH 256 189 #define INODE_TIME_SHIFT 16 190 #define INODE_TIME_MASK 0xfff0 191 192 inline uint32 unique_from_nsec(uint32 time); 193 194 struct bfs_inode { 195 int32 magic1; 196 inode_addr inode_num; 197 int32 uid; 198 int32 gid; 199 int32 mode; // see sys/stat.h 200 int32 flags; 201 int64 create_time; 202 int64 last_modified_time; 203 inode_addr parent; 204 inode_addr attributes; 205 uint32 type; // attribute type 206 207 int32 inode_size; 208 uint32 etc; 209 210 union { 211 data_stream data; 212 char short_symlink[SHORT_SYMLINK_NAME_LENGTH]; 213 }; 214 bigtime_t status_change_time; 215 int32 pad[2]; 216 // on 32 bit architectures we use this member as a doubly linked list 217 // link 218 219 small_data small_data_start[0]; 220 221 int32 Magic1() const { return BFS_ENDIAN_TO_HOST_INT32(magic1); } 222 int32 UserID() const { return BFS_ENDIAN_TO_HOST_INT32(uid); } 223 int32 GroupID() const { return BFS_ENDIAN_TO_HOST_INT32(gid); } 224 int32 Mode() const { return BFS_ENDIAN_TO_HOST_INT32(mode); } 225 int32 Flags() const { return BFS_ENDIAN_TO_HOST_INT32(flags); } 226 int32 Type() const { return BFS_ENDIAN_TO_HOST_INT32(type); } 227 int32 InodeSize() const { return BFS_ENDIAN_TO_HOST_INT32(inode_size); } 228 int64 LastModifiedTime() const 229 { return BFS_ENDIAN_TO_HOST_INT64(last_modified_time); } 230 int64 CreateTime() const 231 { return BFS_ENDIAN_TO_HOST_INT64(create_time); } 232 int64 StatusChangeTime() const 233 { return BFS_ENDIAN_TO_HOST_INT64(status_change_time); } 234 small_data* SmallDataStart() { return small_data_start; } 235 236 status_t InitCheck(Volume* volume) const; 237 // defined in Inode.cpp 238 239 static int64 ToInode(bigtime_t time) 240 { return ((time / 1000000) << INODE_TIME_SHIFT) 241 + unique_from_nsec((time % 1000000) * 1000); } 242 static int64 ToInode(const timespec& tv) 243 { return ((int64)tv.tv_sec << INODE_TIME_SHIFT) 244 + unique_from_nsec(tv.tv_nsec); } 245 246 static time_t ToSecs(int64 time) 247 { return time >> INODE_TIME_SHIFT; } 248 static uint32 ToNsecs(int64 time) 249 { return (time & INODE_TIME_MASK) << 14; } 250 // the 16 bits internal resolution shifted by 14 gives us 2^30 251 // which is roughly 10^9, the maximum value in nanoseconds 252 } _PACKED; 253 254 enum inode_flags { 255 INODE_IN_USE = 0x00000001, // always set 256 INODE_ATTR_INODE = 0x00000004, 257 INODE_LOGGED = 0x00000008, // log changes to the data stream 258 INODE_DELETED = 0x00000010, 259 INODE_NOT_READY = 0x00000020, // used during Inode construction 260 INODE_LONG_SYMLINK = 0x00000040, // symlink in data stream 261 262 INODE_PERMANENT_FLAGS = 0x0000ffff, 263 264 INODE_WAS_WRITTEN = 0x00020000, 265 INODE_IN_TRANSACTION = 0x00040000, 266 267 // The rest is only used by the file system check functionality 268 INODE_DONT_FREE_SPACE = 0x00080000 269 }; 270 271 272 //************************************** 273 274 struct file_cookie { 275 bigtime_t last_notification; 276 off_t last_size; 277 int open_mode; 278 }; 279 280 #define BFS_OPEN_MODE_USER_MASK 0x7fffffff 281 #define BFS_OPEN_MODE_CHECKING 0x80000000 282 283 // notify every second if the file size has changed 284 #define INODE_NOTIFICATION_INTERVAL 1000000LL 285 286 287 /*! Converts the nano seconds given to the internal 16 bit resolution that 288 BFS uses. If \a time is zero, 12 bits will get a monotonically increasing 289 number. For all other values, only the lower 4 bits are changed this way. 290 291 This is done to decrease the number of duplicate time values, which speeds 292 up the way BFS handles the time indices. 293 */ 294 inline uint32 295 unique_from_nsec(uint32 time) 296 { 297 static vint32 number; 298 if (time != 0) 299 return (((time + 16383) >> 14) & INODE_TIME_MASK) | (++number & 0xf); 300 301 return ++number & 0xfff; 302 } 303 304 305 // #pragma mark - block_run inline functions 306 307 308 inline bool 309 block_run::operator==(const block_run &run) const 310 { 311 return allocation_group == run.allocation_group 312 && start == run.start 313 && length == run.length; 314 } 315 316 317 inline bool 318 block_run::operator!=(const block_run &run) const 319 { 320 return allocation_group != run.allocation_group 321 || start != run.start 322 || length != run.length; 323 } 324 325 326 inline bool 327 block_run::IsZero() const 328 { 329 return allocation_group == 0 && start == 0 && length == 0; 330 } 331 332 333 inline bool 334 block_run::MergeableWith(block_run run) const 335 { 336 // 65535 is the maximum allowed run size for BFS 337 return allocation_group == run.allocation_group 338 && Start() + Length() == run.Start() 339 && (uint32)Length() + run.Length() <= MAX_BLOCK_RUN_LENGTH; 340 } 341 342 343 inline void 344 block_run::SetTo(int32 _group,uint16 _start,uint16 _length) 345 { 346 allocation_group = HOST_ENDIAN_TO_BFS_INT32(_group); 347 start = HOST_ENDIAN_TO_BFS_INT16(_start); 348 length = HOST_ENDIAN_TO_BFS_INT16(_length); 349 } 350 351 352 inline block_run 353 block_run::Run(int32 group, uint16 start, uint16 length) 354 { 355 block_run run; 356 run.allocation_group = HOST_ENDIAN_TO_BFS_INT32(group); 357 run.start = HOST_ENDIAN_TO_BFS_INT16(start); 358 run.length = HOST_ENDIAN_TO_BFS_INT16(length); 359 return run; 360 } 361 362 363 // #pragma mark - small_data inline functions 364 365 366 inline char* 367 small_data::Name() const 368 { 369 return const_cast<char*>(name); 370 } 371 372 373 inline uint8* 374 small_data::Data() const 375 { 376 return (uint8*)Name() + NameSize() + 3; 377 } 378 379 380 inline uint32 381 small_data::Size() const 382 { 383 return sizeof(small_data) + NameSize() + 3 + DataSize() + 1; 384 } 385 386 387 inline small_data* 388 small_data::Next() const 389 { 390 return (small_data*)((uint8*)this + Size()); 391 } 392 393 394 inline bool 395 small_data::IsLast(const bfs_inode* inode) const 396 { 397 // we need to check the location first, because if name_size is already beyond 398 // the block, we would touch invalid memory (although that can't cause wrong 399 // results) 400 return (addr_t)this > (addr_t)inode 401 + inode->InodeSize() - sizeof(small_data) || name_size == 0; 402 } 403 404 #ifdef _BOOT_MODE 405 } // namespace BFS 406 #endif 407 408 #endif /* BFS_H */ 409