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
AllocationGroupblock_run32 int32 AllocationGroup() const
33 { return BFS_ENDIAN_TO_HOST_INT32(allocation_group); }
Startblock_run34 uint16 Start() const { return BFS_ENDIAN_TO_HOST_INT16(start); }
Lengthblock_run35 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
Magic1disk_super_block83 int32 Magic1() const { return BFS_ENDIAN_TO_HOST_INT32(magic1); }
Magic2disk_super_block84 int32 Magic2() const { return BFS_ENDIAN_TO_HOST_INT32(magic2); }
Magic3disk_super_block85 int32 Magic3() const { return BFS_ENDIAN_TO_HOST_INT32(magic3); }
ByteOrderdisk_super_block86 int32 ByteOrder() const { return BFS_ENDIAN_TO_HOST_INT32(fs_byte_order); }
BlockSizedisk_super_block87 uint32 BlockSize() const { return BFS_ENDIAN_TO_HOST_INT32(block_size); }
BlockShiftdisk_super_block88 uint32 BlockShift() const { return BFS_ENDIAN_TO_HOST_INT32(block_shift); }
NumBlocksdisk_super_block89 off_t NumBlocks() const { return BFS_ENDIAN_TO_HOST_INT64(num_blocks); }
UsedBlocksdisk_super_block90 off_t UsedBlocks() const { return BFS_ENDIAN_TO_HOST_INT64(used_blocks); }
InodeSizedisk_super_block91 int32 InodeSize() const { return BFS_ENDIAN_TO_HOST_INT32(inode_size); }
BlocksPerAllocationGroupdisk_super_block92 int32 BlocksPerAllocationGroup() const
93 { return BFS_ENDIAN_TO_HOST_INT32(blocks_per_ag); }
AllocationGroupsdisk_super_block94 int32 AllocationGroups() const { return BFS_ENDIAN_TO_HOST_INT32(num_ags); }
AllocationGroupShiftdisk_super_block95 int32 AllocationGroupShift() const
96 { return BFS_ENDIAN_TO_HOST_INT32(ag_shift); }
Flagsdisk_super_block97 int32 Flags() const { return BFS_ENDIAN_TO_HOST_INT32(flags); }
LogStartdisk_super_block98 off_t LogStart() const { return BFS_ENDIAN_TO_HOST_INT64(log_start); }
LogEnddisk_super_block99 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
MaxDirectRangedata_stream128 off_t MaxDirectRange() const
129 { return BFS_ENDIAN_TO_HOST_INT64(max_direct_range); }
MaxIndirectRangedata_stream130 off_t MaxIndirectRange() const
131 { return BFS_ENDIAN_TO_HOST_INT64(max_indirect_range); }
MaxDoubleIndirectRangedata_stream132 off_t MaxDoubleIndirectRange() const
133 { return BFS_ENDIAN_TO_HOST_INT64(max_double_indirect_range); }
Sizedata_stream134 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
Typesmall_data153 uint32 Type() const
154 { return BFS_ENDIAN_TO_HOST_INT32(type); }
NameSizesmall_data155 uint16 NameSize() const
156 { return BFS_ENDIAN_TO_HOST_INT16(
157 name_size); }
DataSizesmall_data158 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
Magic1bfs_inode221 int32 Magic1() const { return BFS_ENDIAN_TO_HOST_INT32(magic1); }
UserIDbfs_inode222 int32 UserID() const { return BFS_ENDIAN_TO_HOST_INT32(uid); }
GroupIDbfs_inode223 int32 GroupID() const { return BFS_ENDIAN_TO_HOST_INT32(gid); }
Modebfs_inode224 int32 Mode() const { return BFS_ENDIAN_TO_HOST_INT32(mode); }
Flagsbfs_inode225 int32 Flags() const { return BFS_ENDIAN_TO_HOST_INT32(flags); }
Typebfs_inode226 int32 Type() const { return BFS_ENDIAN_TO_HOST_INT32(type); }
InodeSizebfs_inode227 int32 InodeSize() const { return BFS_ENDIAN_TO_HOST_INT32(inode_size); }
LastModifiedTimebfs_inode228 int64 LastModifiedTime() const
229 { return BFS_ENDIAN_TO_HOST_INT64(last_modified_time); }
CreateTimebfs_inode230 int64 CreateTime() const
231 { return BFS_ENDIAN_TO_HOST_INT64(create_time); }
StatusChangeTimebfs_inode232 int64 StatusChangeTime() const
233 { return BFS_ENDIAN_TO_HOST_INT64(status_change_time); }
SmallDataStartbfs_inode234 small_data* SmallDataStart() { return small_data_start; }
235
236 status_t InitCheck(Volume* volume) const;
237 // defined in Inode.cpp
238
ToInodebfs_inode239 static int64 ToInode(bigtime_t time)
240 { return ((time / 1000000) << INODE_TIME_SHIFT)
241 + unique_from_nsec((time % 1000000) * 1000); }
ToInodebfs_inode242 static int64 ToInode(const timespec& tv)
243 { return ((int64)tv.tv_sec << INODE_TIME_SHIFT)
244 + unique_from_nsec(tv.tv_nsec); }
245
ToSecsbfs_inode246 static time_t ToSecs(int64 time)
247 { return time >> INODE_TIME_SHIFT; }
ToNsecsbfs_inode248 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
unique_from_nsec(uint32 time)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
IsZero()327 block_run::IsZero() const
328 {
329 return allocation_group == 0 && start == 0 && length == 0;
330 }
331
332
333 inline bool
MergeableWith(block_run run)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
SetTo(int32 _group,uint16 _start,uint16 _length)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
Run(int32 group,uint16 start,uint16 length)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*
Name()367 small_data::Name() const
368 {
369 return const_cast<char*>(name);
370 }
371
372
373 inline uint8*
Data()374 small_data::Data() const
375 {
376 return (uint8*)Name() + NameSize() + 3;
377 }
378
379
380 inline uint32
Size()381 small_data::Size() const
382 {
383 return sizeof(small_data) + NameSize() + 3 + DataSize() + 1;
384 }
385
386
387 inline small_data*
Next()388 small_data::Next() const
389 {
390 return (small_data*)((uint8*)this + Size());
391 }
392
393
394 inline bool
IsLast(const bfs_inode * inode)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