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
19namespace BFS {
20#endif
21
22#ifndef _BOOT_MODE
23extern fs_volume_ops gBFSVolumeOps;
24extern fs_vnode_ops gBFSVnodeOps;
25#endif
26
27struct 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
47typedef 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
59struct 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
119struct 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
145struct bfs_inode;
146
147struct 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
182class 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
192inline uint32 unique_from_nsec(uint32 time);
193
194struct 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
254enum 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
274struct 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*/
294inline uint32
295unique_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
308inline bool
309block_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
317inline bool
318block_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
326inline bool
327block_run::IsZero() const
328{
329	return allocation_group == 0 && start == 0 && length == 0;
330}
331
332
333inline bool
334block_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
343inline void
344block_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
352inline block_run
353block_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
366inline char*
367small_data::Name() const
368{
369	return const_cast<char*>(name);
370}
371
372
373inline uint8*
374small_data::Data() const
375{
376	return (uint8*)Name() + NameSize() + 3;
377}
378
379
380inline uint32
381small_data::Size() const
382{
383	return sizeof(small_data) + NameSize() + 3 + DataSize() + 1;
384}
385
386
387inline small_data*
388small_data::Next() const
389{
390	return (small_data*)((uint8*)this + Size());
391}
392
393
394inline bool
395small_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