1/*
2 * Copyright 2019, Les De Ridder, les@lesderid.net
3 * Copyright 2017, Ch��� V�� Gia Hy, cvghy116@gmail.com.
4 * Copyright 2011, J��r��me Duval, korli@users.berlios.de.
5 * Copyright 2008-2010, Axel D��rfler, axeld@pinc-software.de.
6 *
7 * This file may be used under the terms of the MIT License.
8 */
9
10
11//! Superblock, mounting, etc.
12
13
14#include "Volume.h"
15#include "BTree.h"
16#include "CachedBlock.h"
17#include "Chunk.h"
18#include "CRCTable.h"
19#include "DeviceOpener.h"
20#include "ExtentAllocator.h"
21#include "Inode.h"
22#include "Journal.h"
23#include "Utility.h"
24
25#ifdef FS_SHELL
26#define RETURN_ERROR return
27#else
28#include "DebugSupport.h"
29#endif
30
31//#define TRACE_BTRFS
32#ifdef TRACE_BTRFS
33#	define TRACE(x...) dprintf("\33[34mbtrfs:\33[0m " x)
34#else
35#	define TRACE(x...) ;
36#endif
37
38
39//	#pragma mark -
40
41
42bool
43btrfs_super_block::IsValid() const
44{
45	// TODO: check some more values!
46	if (strncmp(magic, BTRFS_SUPER_BLOCK_MAGIC, sizeof(magic)) != 0)
47		return false;
48
49	return true;
50}
51
52
53void
54btrfs_super_block::Initialize(const char* name, off_t numBlocks,
55		uint32 blockSize, uint32 sectorSize)
56{
57	memset(this, 0, sizeof(btrfs_super_block));
58
59	uuid_generate(fsid);
60	blocknum = B_HOST_TO_LENDIAN_INT64(BTRFS_SUPER_BLOCK_OFFSET);
61	num_devices = B_HOST_TO_LENDIAN_INT64(1);
62	strncpy(magic, BTRFS_SUPER_BLOCK_MAGIC_TEMPORARY, sizeof(magic));
63	generation = B_HOST_TO_LENDIAN_INT64(1);
64	root = B_HOST_TO_LENDIAN_INT64(BTRFS_RESERVED_SPACE_OFFSET + blockSize);
65	chunk_root = B_HOST_TO_LENDIAN_INT64(Root() + blockSize);
66	total_size = B_HOST_TO_LENDIAN_INT64(numBlocks * blockSize);
67	used_size = B_HOST_TO_LENDIAN_INT64(6 * blockSize);
68	sector_size = B_HOST_TO_LENDIAN_INT32(sectorSize);
69	leaf_size = B_HOST_TO_LENDIAN_INT32(blockSize);
70	node_size = B_HOST_TO_LENDIAN_INT32(blockSize);
71	stripe_size = B_HOST_TO_LENDIAN_INT32(blockSize);
72	checksum_type = B_HOST_TO_LENDIAN_INT32(BTRFS_CSUM_TYPE_CRC32);
73	chunk_root_generation = B_HOST_TO_LENDIAN_INT64(1);
74	// TODO(lesderid): Support configurable filesystem features
75	incompat_flags = B_HOST_TO_LENDIAN_INT64(0);
76	strlcpy(label, name, BTRFS_LABEL_SIZE);
77}
78
79
80//	#pragma mark -
81
82
83Volume::Volume(fs_volume* volume)
84	:
85	fFSVolume(volume),
86	fFlags(0),
87	fChunk(NULL),
88	fChunkTree(NULL)
89{
90	mutex_init(&fLock, "btrfs volume");
91}
92
93
94Volume::~Volume()
95{
96	TRACE("Volume destructor.\n");
97}
98
99
100bool
101Volume::IsValidSuperBlock()
102{
103	return fSuperBlock.IsValid();
104}
105
106
107const char*
108Volume::Name() const
109{
110	if (fSuperBlock.label[0])
111		return fSuperBlock.label;
112
113	return fName;
114}
115
116
117status_t
118Volume::Mount(const char* deviceName, uint32 flags)
119{
120	flags |= B_MOUNT_READ_ONLY;
121		// we only support read-only for now
122
123	if ((flags & B_MOUNT_READ_ONLY) != 0) {
124		TRACE("Volume::Mount(): Read only\n");
125	} else {
126		TRACE("Volume::Mount(): Read write\n");
127	}
128
129	DeviceOpener opener(deviceName, (flags & B_MOUNT_READ_ONLY) != 0
130		? O_RDONLY : O_RDWR);
131	fDevice = opener.Device();
132	if (fDevice < B_OK) {
133		ERROR("Volume::Mount(): couldn't open device\n");
134		return fDevice;
135	}
136
137	if (opener.IsReadOnly())
138		fFlags |= VOLUME_READ_ONLY;
139
140	// read the superblock
141	status_t status = Identify(fDevice, &fSuperBlock);
142	if (status != B_OK) {
143		ERROR("Volume::Mount(): Identify() failed\n");
144		return status;
145	}
146
147	fBlockSize = fSuperBlock.BlockSize();
148	fSectorSize = fSuperBlock.SectorSize();
149	TRACE("block size %" B_PRIu32 "\n", fBlockSize);
150	TRACE("sector size %" B_PRIu32 "\n", fSectorSize);
151
152	uint8* start = (uint8*)&fSuperBlock.system_chunk_array[0];
153	uint8* end = (uint8*)&fSuperBlock.system_chunk_array[2048];
154	while (start < end) {
155		btrfs_key* key = (btrfs_key*)start;
156		TRACE("system_chunk_array object_id 0x%" B_PRIx64 " offset 0x%"
157			B_PRIx64 " type 0x%x\n", key->ObjectID(), key->Offset(),
158			key->Type());
159		if (key->Type() != BTRFS_KEY_TYPE_CHUNK_ITEM) {
160			break;
161		}
162
163		btrfs_chunk* chunk = (btrfs_chunk*)(key + 1);
164		fChunk = new(std::nothrow) Chunk(chunk, key->Offset());
165		if (fChunk == NULL)
166			return B_ERROR;
167		start += sizeof(btrfs_key) + fChunk->Size();
168	}
169
170	// check if the device size is large enough to hold the file system
171	off_t diskSize;
172	status = opener.GetSize(&diskSize);
173	if (status != B_OK)
174		return status;
175	if (diskSize < (off_t)fSuperBlock.TotalSize())
176		return B_BAD_VALUE;
177
178	fBlockCache = opener.InitCache(fSuperBlock.TotalSize() / fBlockSize,
179		fBlockSize);
180	if (fBlockCache == NULL)
181		return B_ERROR;
182
183	TRACE("Volume::Mount(): Initialized block cache: %p\n", fBlockCache);
184
185	fChunkTree = new(std::nothrow) BTree(this);
186	if (fChunkTree == NULL)
187		return B_NO_MEMORY;
188	fChunkTree->SetRoot(fSuperBlock.ChunkRoot(), NULL);
189	TRACE("Volume::Mount() chunk_root: %" B_PRIu64 " (physical block %" B_PRIu64
190		")\n", fSuperBlock.ChunkRoot(), fChunkTree->RootBlock());
191
192	fRootTree = new(std::nothrow) BTree(this);
193	if (fRootTree == NULL)
194		return B_NO_MEMORY;
195	fRootTree->SetRoot(fSuperBlock.Root(), NULL);
196	TRACE("Volume::Mount() root: %" B_PRIu64 " (physical block %" B_PRIu64 ")\n",
197		fSuperBlock.Root(), fRootTree->RootBlock());
198
199	BTree::Path path(fRootTree);
200
201	TRACE("Volume::Mount(): Searching extent root\n");
202	btrfs_key search_key;
203	search_key.SetOffset(0);
204	search_key.SetType(BTRFS_KEY_TYPE_ROOT_ITEM);
205	search_key.SetObjectID(BTRFS_OBJECT_ID_EXTENT_TREE);
206	btrfs_root* root;
207	status = fRootTree->FindExact(&path, search_key, (void**)&root);
208	if (status != B_OK) {
209		ERROR("Volume::Mount(): Couldn't find extent root\n");
210		return status;
211	}
212	TRACE("Volume::Mount(): Found extent root: %" B_PRIu64 "\n",
213		root->LogicalAddress());
214	fExtentTree = new(std::nothrow) BTree(this);
215	if (fExtentTree == NULL)
216		return B_NO_MEMORY;
217	fExtentTree->SetRoot(root->LogicalAddress(), NULL);
218	free(root);
219
220	TRACE("Volume::Mount(): Searching fs root\n");
221	search_key.SetOffset(0);
222	search_key.SetObjectID(BTRFS_OBJECT_ID_FS_TREE);
223	status = fRootTree->FindExact(&path, search_key, (void**)&root);
224	if (status != B_OK) {
225		ERROR("Volume::Mount(): Couldn't find fs root\n");
226		return status;
227	}
228	TRACE("Volume::Mount(): Found fs root: %" B_PRIu64 "\n",
229		root->LogicalAddress());
230	fFSTree = new(std::nothrow) BTree(this);
231	if (fFSTree == NULL)
232		return B_NO_MEMORY;
233	fFSTree->SetRoot(root->LogicalAddress(), NULL);
234	free(root);
235
236	TRACE("Volume::Mount(): Searching dev root\n");
237	search_key.SetOffset(0);
238	search_key.SetObjectID(BTRFS_OBJECT_ID_DEV_TREE);
239	status = fRootTree->FindExact(&path, search_key, (void**)&root);
240	if (status != B_OK) {
241		ERROR("Volume::Mount(): Couldn't find dev root\n");
242		return status;
243	}
244	TRACE("Volume::Mount(): Found dev root: %" B_PRIu64 "\n",
245		root->LogicalAddress());
246	fDevTree = new(std::nothrow) BTree(this);
247	if (fDevTree == NULL)
248		return B_NO_MEMORY;
249	fDevTree->SetRoot(root->LogicalAddress(), NULL);
250	free(root);
251
252	TRACE("Volume::Mount(): Searching checksum root\n");
253	search_key.SetOffset(0);
254	search_key.SetObjectID(BTRFS_OBJECT_ID_CHECKSUM_TREE);
255	status = fRootTree->FindExact(&path, search_key, (void**)&root);
256	if (status != B_OK) {
257		ERROR("Volume::Mount(): Couldn't find checksum root\n");
258		return status;
259	}
260	TRACE("Volume::Mount(): Found checksum root: %" B_PRIu64 "\n",
261		root->LogicalAddress());
262	fChecksumTree = new(std::nothrow) BTree(this);
263	if (fChecksumTree == NULL)
264		return B_NO_MEMORY;
265	fChecksumTree->SetRoot(root->LogicalAddress(), NULL);
266	free(root);
267
268	search_key.SetObjectID(-1);
269	search_key.SetType(0);
270	status = fFSTree->FindPrevious(&path, search_key, NULL);
271	if (status != B_OK) {
272		ERROR("Volume::Mount() Couldn't find any inode!!\n");
273		return status;
274	}
275	fLargestInodeID = search_key.ObjectID();
276	TRACE("Volume::Mount() Find larget inode id % " B_PRIu64 "\n",
277		fLargestInodeID);
278
279	if ((flags & B_MOUNT_READ_ONLY) != 0) {
280		fJournal = NULL;
281		fExtentAllocator = NULL;
282	} else {
283		// Initialize Journal
284		fJournal = new(std::nothrow) Journal(this);
285		if (fJournal == NULL)
286			return B_NO_MEMORY;
287
288		// Initialize ExtentAllocator;
289		fExtentAllocator = new(std::nothrow) ExtentAllocator(this);
290		if (fExtentAllocator == NULL)
291			return B_NO_MEMORY;
292		status = fExtentAllocator->Initialize();
293		if (status != B_OK) {
294			ERROR("could not initalize extent allocator!\n");
295			return status;
296		}
297	}
298
299	// ready
300	status = get_vnode(fFSVolume, BTRFS_FIRST_SUBVOLUME,
301		(void**)&fRootNode);
302	if (status != B_OK) {
303		ERROR("could not create root node: get_vnode() failed!\n");
304		return status;
305	}
306
307	TRACE("Volume::Mount(): Found root node: %" B_PRIu64 " (%s)\n",
308		fRootNode->ID(), strerror(fRootNode->InitCheck()));
309
310	// all went fine
311	opener.Keep();
312
313	if (!fSuperBlock.label[0]) {
314		// generate a more or less descriptive volume name
315		off_t divisor = 1ULL << 40;
316		char unit = 'T';
317		if (diskSize < divisor) {
318			divisor = 1UL << 30;
319			unit = 'G';
320			if (diskSize < divisor) {
321				divisor = 1UL << 20;
322				unit = 'M';
323			}
324		}
325
326		double size = double((10 * diskSize + divisor - 1) / divisor);
327			// %g in the kernel does not support precision...
328
329		snprintf(fName, sizeof(fName), "%g %cB Btrfs Volume",
330			size / 10, unit);
331	}
332
333	return B_OK;
334}
335
336
337status_t
338Volume::Initialize(int fd, const char* label, uint32 blockSize,
339	uint32 sectorSize)
340{
341	TRACE("Volume::Initialize()\n");
342
343	// label must != NULL and may not contain '/' or '\\'
344	if (label == NULL
345		|| strchr(label, '/') != NULL || strchr(label, '\\') != NULL) {
346		return B_BAD_VALUE;
347	}
348
349	if ((blockSize != 1024 && blockSize != 2048 && blockSize != 4096
350		&& blockSize != 8192 && blockSize != 16384)
351		|| blockSize % sectorSize != 0) {
352		return B_BAD_VALUE;
353	}
354
355	DeviceOpener opener(fd, O_RDWR);
356	if (opener.Device() < B_OK)
357		return B_BAD_VALUE;
358
359	if (opener.IsReadOnly())
360		return B_READ_ONLY_DEVICE;
361
362	fDevice = opener.Device();
363
364	uint32 deviceBlockSize;
365	off_t deviceSize;
366	if (opener.GetSize(&deviceSize, &deviceBlockSize) < B_OK)
367		return B_ERROR;
368	off_t numBlocks = deviceSize / sectorSize;
369
370	// create valid superblock
371
372	fSuperBlock.Initialize(label, numBlocks, blockSize, sectorSize);
373
374	fBlockSize = fSuperBlock.BlockSize();
375	fSectorSize = fSuperBlock.SectorSize();
376
377	// TODO(lesderid):	Initialize remaining core structures
378	//					(extent tree, chunk tree, fs tree, etc.)
379
380	status_t status = WriteSuperBlock();
381	if (status < B_OK)
382		return status;
383
384	fBlockCache = opener.InitCache(fSuperBlock.TotalSize() / fBlockSize,
385		fBlockSize);
386	if (fBlockCache == NULL)
387		return B_ERROR;
388
389	fJournal = new(std::nothrow) Journal(this);
390	if (fJournal == NULL)
391		RETURN_ERROR(B_ERROR);
392
393	// TODO(lesderid):	Perform secondary initialization (in transactions)
394	//					(add block groups to extent tree, create root dir, etc.)
395	Transaction transaction(this);
396
397	// TODO(lesderid): Write all superblocks when transactions are committed
398	status = transaction.Done();
399	if (status < B_OK)
400		return status;
401
402	opener.RemoveCache(true);
403
404	TRACE("Volume::Initialize(): Done\n");
405	return B_OK;
406}
407
408
409status_t
410Volume::Unmount()
411{
412	TRACE("Volume::Unmount()\n");
413	delete fRootTree;
414	delete fExtentTree;
415	delete fChunkTree;
416	delete fChecksumTree;
417	delete fFSTree;
418	delete fDevTree;
419	delete fJournal;
420	delete fExtentAllocator;
421	fRootTree = NULL;
422	fExtentTree = NULL;
423	fChunkTree = NULL;
424	fChecksumTree = NULL;
425	fFSTree = NULL;
426	fDevTree = NULL;
427	fJournal = NULL;
428	fExtentAllocator = NULL;
429
430	TRACE("Volume::Unmount(): Putting root node\n");
431	put_vnode(fFSVolume, RootNode()->ID());
432	TRACE("Volume::Unmount(): Deleting the block cache\n");
433	block_cache_delete(fBlockCache, !IsReadOnly());
434	TRACE("Volume::Unmount(): Closing device\n");
435	close(fDevice);
436
437	TRACE("Volume::Unmount(): Done\n");
438	return B_OK;
439}
440
441
442status_t
443Volume::LoadSuperBlock()
444{
445	CachedBlock cached(this);
446	const uint8* block = cached.SetTo(BTRFS_SUPER_BLOCK_OFFSET / fBlockSize);
447
448	if (block == NULL)
449		return B_IO_ERROR;
450
451	memcpy(&fSuperBlock, block + BTRFS_SUPER_BLOCK_OFFSET % fBlockSize,
452		sizeof(fSuperBlock));
453
454	return B_OK;
455}
456
457
458status_t
459Volume::FindBlock(off_t logical, fsblock_t& physicalBlock)
460{
461	off_t physical;
462	status_t status = FindBlock(logical, physical);
463	if (status != B_OK)
464		return status;
465	physicalBlock = physical / fBlockSize;
466	return B_OK;
467}
468
469
470status_t
471Volume::FindBlock(off_t logical, off_t& physical)
472{
473	if (fChunkTree == NULL
474		|| (logical >= (off_t)fChunk->Offset()
475			&& logical < (off_t)fChunk->End())) {
476		// try with fChunk
477		return fChunk->FindBlock(logical, physical);
478	}
479
480	btrfs_key search_key;
481	search_key.SetOffset(logical);
482	search_key.SetType(BTRFS_KEY_TYPE_CHUNK_ITEM);
483	search_key.SetObjectID(BTRFS_OBJECT_ID_FIRST_CHUNK_TREE);
484	btrfs_chunk* chunk;
485	BTree::Path path(fChunkTree);
486	status_t status = fChunkTree->FindPrevious(&path, search_key,
487		(void**)&chunk);
488	if (status != B_OK)
489		return status;
490
491	Chunk _chunk(chunk, search_key.Offset());
492	free(chunk);
493	status = _chunk.FindBlock(logical, physical);
494	if (status != B_OK)
495			return status;
496	TRACE("Volume::FindBlock(): logical: %" B_PRIdOFF ", physical: %" B_PRIdOFF
497		"\n", logical, physical);
498	return B_OK;
499}
500
501
502status_t
503Volume::WriteSuperBlock()
504{
505	uint32 checksum = calculate_crc((uint32)~1,
506			(uint8 *)(&fSuperBlock + sizeof(fSuperBlock.checksum)),
507			sizeof(fSuperBlock) - sizeof(fSuperBlock.checksum));
508
509	fSuperBlock.checksum[0] = (checksum >>  0) & 0xFF;
510	fSuperBlock.checksum[1] = (checksum >>  8) & 0xFF;
511	fSuperBlock.checksum[2] = (checksum >> 16) & 0xFF;
512	fSuperBlock.checksum[3] = (checksum >> 24) & 0xFF;
513
514	if (write_pos(fDevice, BTRFS_SUPER_BLOCK_OFFSET, &fSuperBlock,
515			sizeof(btrfs_super_block))
516		!= sizeof(btrfs_super_block))
517		return B_IO_ERROR;
518
519	return B_OK;
520}
521
522
523/* Wrapper function for allocating new block
524 */
525status_t
526Volume::GetNewBlock(uint64& logical, fsblock_t& physical, uint64 start,
527	uint64 flags)
528{
529	status_t status = fExtentAllocator->AllocateTreeBlock(logical, start, flags);
530	if (status != B_OK)
531		return status;
532
533	return FindBlock(logical, physical);
534}
535
536
537//	#pragma mark - Disk scanning and initialization
538
539
540/*static*/ status_t
541Volume::Identify(int fd, btrfs_super_block* superBlock)
542{
543	if (read_pos(fd, BTRFS_SUPER_BLOCK_OFFSET, superBlock,
544			sizeof(btrfs_super_block)) != sizeof(btrfs_super_block))
545		return B_IO_ERROR;
546
547	if (!superBlock->IsValid()) {
548		ERROR("invalid superblock!\n");
549		return B_BAD_VALUE;
550	}
551
552	return B_OK;
553}
554
555