1/*
2 * Copyright 2002-2020, Axel D��rfler, axeld@pinc-software.de.
3 * Copyright 2012, Andreas Henriksson, sausageboy@gmail.com
4 * This file may be used under the terms of the MIT License.
5 */
6
7
8//! File system error checking
9
10
11#include "CheckVisitor.h"
12
13#include "BlockAllocator.h"
14#include "BPlusTree.h"
15#include "Inode.h"
16#include "Volume.h"
17
18
19struct check_index {
20	check_index()
21		:
22		inode(NULL)
23	{
24	}
25
26	char				name[B_FILE_NAME_LENGTH];
27	block_run			run;
28	Inode*				inode;
29};
30
31
32CheckVisitor::CheckVisitor(Volume* volume)
33	:
34	FileSystemVisitor(volume),
35	fCheckBitmap(NULL)
36{
37}
38
39
40CheckVisitor::~CheckVisitor()
41{
42	free(fCheckBitmap);
43}
44
45
46status_t
47CheckVisitor::StartBitmapPass()
48{
49	if (!_ControlValid())
50		return B_BAD_VALUE;
51
52	// Lock the volume's journal and block allocator
53	GetVolume()->GetJournal(0)->Lock(NULL, true);
54	recursive_lock_lock(&GetVolume()->Allocator().Lock());
55
56	size_t size = _BitmapSize();
57	fCheckBitmap = (uint32*)malloc(size);
58	if (fCheckBitmap == NULL) {
59		recursive_lock_unlock(&GetVolume()->Allocator().Lock());
60		GetVolume()->GetJournal(0)->Unlock(NULL, true);
61		return B_NO_MEMORY;
62	}
63
64	memset(&Control().stats, 0, sizeof(check_control::stats));
65
66	// initialize bitmap
67	memset(fCheckBitmap, 0, size);
68	for (off_t block = GetVolume()->ToBlock(GetVolume()->Log())
69		+ GetVolume()->Log().Length(); block-- > 0;) {
70		_SetCheckBitmapAt(block);
71	}
72
73	Control().pass = BFS_CHECK_PASS_BITMAP;
74	Control().stats.block_size = GetVolume()->BlockSize();
75
76	// TODO: check reserved area in bitmap!
77
78	Start(VISIT_REGULAR | VISIT_INDICES | VISIT_REMOVED
79		| VISIT_ATTRIBUTE_DIRECTORIES);
80
81	return B_OK;
82}
83
84
85status_t
86CheckVisitor::WriteBackCheckBitmap()
87{
88	if (GetVolume()->IsReadOnly())
89		return B_OK;
90
91	// calculate the number of used blocks in the check bitmap
92	size_t size = _BitmapSize();
93	off_t usedBlocks = 0LL;
94
95	// TODO: update the allocation groups used blocks info
96	for (uint32 i = size >> 2; i-- > 0;) {
97		uint32 compare = 1;
98		// Count the number of bits set
99		for (int16 j = 0; j < 32; j++, compare <<= 1) {
100			if ((compare & fCheckBitmap[i]) != 0)
101				usedBlocks++;
102		}
103	}
104
105	Control().stats.freed = GetVolume()->UsedBlocks() - usedBlocks
106		+ Control().stats.missing;
107	if (Control().stats.freed < 0)
108		Control().stats.freed = 0;
109
110	// Should we fix errors? Were there any errors we can fix?
111	if ((Control().flags & BFS_FIX_BITMAP_ERRORS) != 0
112		&& (Control().stats.freed != 0 || Control().stats.missing != 0)) {
113		// If so, write the check bitmap back over the original one,
114		// and use transactions here to play safe - we even use several
115		// transactions, so that we don't blow the maximum log size
116		// on large disks, since we don't need to make this atomic.
117#if 0
118		// prints the blocks that differ
119		off_t block = 0;
120		for (int32 i = 0; i < fNumGroups; i++) {
121			AllocationBlock cached(fVolume);
122			for (uint32 j = 0; j < fGroups[i].NumBlocks(); j++) {
123				cached.SetTo(fGroups[i], j);
124				for (uint32 k = 0; k < cached.NumBlockBits(); k++) {
125					if (cached.IsUsed(k) != _CheckBitmapIsUsedAt(block)) {
126						dprintf("differ block %lld (should be %d)\n", block,
127							_CheckBitmapIsUsedAt(block));
128					}
129					block++;
130				}
131			}
132		}
133#endif
134
135		GetVolume()->SuperBlock().used_blocks
136			= HOST_ENDIAN_TO_BFS_INT64(usedBlocks);
137
138		size_t blockSize = GetVolume()->BlockSize();
139		off_t numBitmapBlocks = GetVolume()->NumBitmapBlocks();
140
141		for (uint32 i = 0; i < numBitmapBlocks; i += 512) {
142			Transaction transaction(GetVolume(), 1 + i);
143
144			uint32 blocksToWrite = 512;
145			if (blocksToWrite + i > numBitmapBlocks)
146				blocksToWrite = numBitmapBlocks - i;
147
148			status_t status = transaction.WriteBlocks(1 + i,
149				(uint8*)fCheckBitmap + i * blockSize, blocksToWrite);
150			if (status < B_OK) {
151				FATAL(("error writing bitmap: %s\n", strerror(status)));
152				return status;
153			}
154			transaction.Done();
155		}
156	}
157
158	return B_OK;
159}
160
161
162status_t
163CheckVisitor::StartIndexPass()
164{
165	// if we don't have indices to rebuild, this pass is done
166	if (indices.IsEmpty())
167		return B_ENTRY_NOT_FOUND;
168
169	Control().pass = BFS_CHECK_PASS_INDEX;
170
171	status_t status = _PrepareIndices();
172	if (status != B_OK) {
173		Control().status = status;
174		return status;
175	}
176
177	Start(VISIT_REGULAR);
178	return Next();
179}
180
181
182status_t
183CheckVisitor::StopChecking()
184{
185	if (GetVolume()->IsReadOnly()) {
186		// We can't fix errors on this volume
187		Control().flags = 0;
188	}
189
190	if (Control().status != B_ENTRY_NOT_FOUND)
191		FATAL(("CheckVisitor didn't run through\n"));
192
193	_FreeIndices();
194
195	recursive_lock_unlock(&GetVolume()->Allocator().Lock());
196	GetVolume()->GetJournal(0)->Unlock(NULL, true);
197	return B_OK;
198}
199
200
201status_t
202CheckVisitor::VisitDirectoryEntry(Inode* inode, Inode* parent,
203	const char* treeName)
204{
205	Control().inode = inode->ID();
206	Control().mode = inode->Mode();
207
208	if (Pass() != BFS_CHECK_PASS_BITMAP)
209		return B_OK;
210
211	// check if the inode's name is the same as in the b+tree
212	if (inode->IsRegularNode()) {
213		RecursiveLocker locker(inode->SmallDataLock());
214		NodeGetter node(GetVolume());
215		status_t status = node.SetTo(inode);
216		if (status != B_OK) {
217			Control().errors |= BFS_COULD_NOT_OPEN;
218			Control().status = status;
219			return B_OK;
220		}
221
222		const char* localName = inode->Name(node.Node());
223		if (localName == NULL || strcmp(localName, treeName)) {
224			Control().errors |= BFS_NAMES_DONT_MATCH;
225			FATAL(("Names differ: tree \"%s\", inode \"%s\"\n", treeName,
226				localName));
227
228			if ((Control().flags & BFS_FIX_NAME_MISMATCHES) != 0) {
229				// Rename the inode
230				Transaction transaction(GetVolume(), inode->BlockNumber());
231
232				// Note, this may need extra blocks, but the inode will
233				// only be checked afterwards, so that it won't be lost
234				status_t status = inode->SetName(transaction, treeName);
235				if (status == B_OK)
236					status = inode->WriteBack(transaction);
237				if (status == B_OK)
238					status = transaction.Done();
239				if (status != B_OK) {
240					Control().status = status;
241					return B_OK;
242				}
243			}
244		}
245	}
246
247	// Check for the correct mode of the node (if the mode of the
248	// file don't fit to its parent, there is a serious problem)
249	if (((parent->Mode() & S_ATTR_DIR) != 0
250			&& !inode->IsAttribute())
251		|| ((parent->Mode() & S_INDEX_DIR) != 0
252			&& !inode->IsIndex())
253		|| (is_directory(parent->Mode())
254			&& !inode->IsRegularNode())) {
255		FATAL(("inode at %" B_PRIdOFF " is of wrong type: %o (parent "
256			"%o at %" B_PRIdOFF ")!\n", inode->BlockNumber(),
257			inode->Mode(), parent->Mode(), parent->BlockNumber()));
258
259		// if we are allowed to fix errors, we should remove the file
260		if ((Control().flags & BFS_REMOVE_WRONG_TYPES) != 0
261			&& (Control().flags & BFS_FIX_BITMAP_ERRORS) != 0) {
262			Control().status = _RemoveInvalidNode(parent, NULL, inode,
263				treeName);
264		} else
265			Control().status = B_ERROR;
266
267		Control().errors |= BFS_WRONG_TYPE;
268	}
269	return B_OK;
270}
271
272
273status_t
274CheckVisitor::VisitInode(Inode* inode, const char* treeName)
275{
276	Control().inode = inode->ID();
277	Control().mode = inode->Mode();
278		// (we might have set these in VisitDirectoryEntry already)
279
280	// set name
281	if (treeName == NULL) {
282		if (inode->GetName(Control().name) < B_OK) {
283			if (inode->IsContainer())
284				strcpy(Control().name, "(dir has no name)");
285			else
286				strcpy(Control().name, "(node has no name)");
287		}
288	} else
289		strcpy(Control().name, treeName);
290
291	status_t status = B_OK;
292
293	switch (Pass()) {
294		case BFS_CHECK_PASS_BITMAP:
295		{
296			status = _CheckInodeBlocks(inode, NULL);
297			if (status != B_OK)
298				return status;
299
300			// Check the B+tree as well
301			if (inode->IsContainer()) {
302				bool repairErrors = (Control().flags & BFS_FIX_BPLUSTREES) != 0;
303				bool errorsFound = false;
304
305				status = inode->Tree()->Validate(repairErrors, errorsFound);
306
307				if (errorsFound) {
308					Control().errors |= BFS_INVALID_BPLUSTREE;
309					if (inode->IsIndex() && treeName != NULL && repairErrors) {
310						// We completely rebuild corrupt indices
311						check_index* index = new(std::nothrow) check_index;
312						if (index == NULL)
313							return B_NO_MEMORY;
314
315						strlcpy(index->name, treeName, sizeof(index->name));
316						index->run = inode->BlockRun();
317						Indices().Push(index);
318					}
319				}
320			}
321
322			break;
323		}
324
325		case BFS_CHECK_PASS_INDEX:
326			status = _AddInodeToIndex(inode);
327			break;
328	}
329
330	Control().status = status;
331	return B_OK;
332}
333
334
335status_t
336CheckVisitor::OpenInodeFailed(status_t reason, ino_t id, Inode* parent,
337		char* treeName, TreeIterator* iterator)
338{
339	FATAL(("Could not open inode at %" B_PRIdOFF ": %s\n", id,
340		strerror(reason)));
341
342	if (treeName != NULL)
343		strlcpy(Control().name, treeName, B_FILE_NAME_LENGTH);
344	else
345		strcpy(Control().name, "(node has no name)");
346
347	Control().inode = id;
348	Control().errors = BFS_COULD_NOT_OPEN;
349
350	// TODO: check other error codes; B_IO_ERROR might be a temporary
351	// issue, so it should be guarded by a force mode
352	if (reason == B_BAD_VALUE || reason == B_BAD_DATA || reason == B_IO_ERROR) {
353		// Remove inode from the tree if we can
354		if (parent != NULL && iterator != NULL
355			&& (Control().flags & BFS_REMOVE_INVALID) != 0) {
356			Control().status = _RemoveInvalidNode(parent, iterator->Tree(),
357				NULL, treeName);
358		} else
359			Control().status = B_ERROR;
360	} else {
361		Control().status = B_OK;
362	}
363
364	return B_OK;
365}
366
367
368status_t
369CheckVisitor::OpenBPlusTreeFailed(Inode* inode)
370{
371	FATAL(("Could not open b+tree from inode at %" B_PRIdOFF "\n",
372		inode->ID()));
373	return B_OK;
374}
375
376
377status_t
378CheckVisitor::TreeIterationFailed(status_t reason, Inode* parent)
379{
380	// Iterating over the B+tree failed - we let the checkfs run
381	// fail completely, as we would delete all files we cannot
382	// access.
383	// TODO: maybe have a force parameter that actually does that.
384	// TODO: we also need to be able to repair broken B+trees!
385	return reason;
386}
387
388
389status_t
390CheckVisitor::_RemoveInvalidNode(Inode* parent, BPlusTree* tree,
391	Inode* inode, const char* name)
392{
393	// It's safe to start a transaction, because Inode::Remove()
394	// won't touch the block bitmap (which we hold the lock for)
395	// if we set the INODE_DONT_FREE_SPACE flag - since we fix
396	// the bitmap anyway.
397	Transaction transaction(GetVolume(), parent->BlockNumber());
398	status_t status;
399
400	if (inode != NULL) {
401		inode->Node().flags |= HOST_ENDIAN_TO_BFS_INT32(INODE_DONT_FREE_SPACE);
402
403		status = parent->Remove(transaction, name, NULL, false, true);
404	} else {
405		parent->WriteLockInTransaction(transaction);
406
407		// does the file even exist?
408		off_t id;
409		status = tree->Find((uint8*)name, (uint16)strlen(name), &id);
410		if (status == B_OK)
411			status = tree->Remove(transaction, name, id);
412	}
413
414	if (status == B_OK) {
415		entry_cache_remove(GetVolume()->ID(), parent->ID(), name);
416		transaction.Done();
417	}
418
419	return status;
420}
421
422
423bool
424CheckVisitor::_ControlValid()
425{
426	if (Control().magic != BFS_IOCTL_CHECK_MAGIC) {
427		FATAL(("invalid check_control!\n"));
428		return false;
429	}
430
431	return true;
432}
433
434
435bool
436CheckVisitor::_CheckBitmapIsUsedAt(off_t block) const
437{
438	size_t size = _BitmapSize();
439	uint32 index = block / 32;	// 32bit resolution
440	if (index > size / 4)
441		return false;
442
443	return BFS_ENDIAN_TO_HOST_INT32(fCheckBitmap[index])
444		& (1UL << (block & 0x1f));
445}
446
447
448void
449CheckVisitor::_SetCheckBitmapAt(off_t block)
450{
451	size_t size = _BitmapSize();
452	uint32 index = block / 32;	// 32bit resolution
453	if (index > size / 4)
454		return;
455
456	fCheckBitmap[index] |= HOST_ENDIAN_TO_BFS_INT32(1UL << (block & 0x1f));
457}
458
459
460size_t
461CheckVisitor::_BitmapSize() const
462{
463	return GetVolume()->BlockSize() * GetVolume()->NumBitmapBlocks();
464}
465
466
467status_t
468CheckVisitor::_CheckInodeBlocks(Inode* inode, const char* name)
469{
470	status_t status = _CheckAllocated(inode->BlockRun(), "inode");
471	if (status != B_OK)
472		return status;
473
474	if (inode->IsSymLink() && (inode->Flags() & INODE_LONG_SYMLINK) == 0) {
475		// symlinks may not have a valid data stream
476		if (strlen(inode->Node().short_symlink) >= SHORT_SYMLINK_NAME_LENGTH)
477			return B_BAD_DATA;
478
479		return B_OK;
480	}
481
482	data_stream* data = &inode->Node().data;
483
484	// check the direct range
485
486	if (data->max_direct_range) {
487		for (int32 i = 0; i < NUM_DIRECT_BLOCKS; i++) {
488			if (data->direct[i].IsZero())
489				break;
490
491			status = _CheckAllocated(data->direct[i], "direct");
492			if (status < B_OK)
493				return status;
494
495			Control().stats.direct_block_runs++;
496			Control().stats.blocks_in_direct
497				+= data->direct[i].Length();
498		}
499	}
500
501	CachedBlock cached(GetVolume());
502
503	// check the indirect range
504
505	if (data->max_indirect_range) {
506		status = _CheckAllocated(data->indirect, "indirect");
507		if (status != B_OK)
508			return status;
509
510		off_t block = GetVolume()->ToBlock(data->indirect);
511
512		for (int32 i = 0; i < data->indirect.Length(); i++) {
513			status = cached.SetTo(block + i);
514			if (status != B_OK)
515				RETURN_ERROR(status);
516
517			block_run* runs = (block_run*)cached.Block();
518			int32 runsPerBlock = GetVolume()->BlockSize() / sizeof(block_run);
519			int32 index = 0;
520			for (; index < runsPerBlock; index++) {
521				if (runs[index].IsZero())
522					break;
523
524				status = _CheckAllocated(runs[index], "indirect->run");
525				if (status < B_OK)
526					return status;
527
528				Control().stats.indirect_block_runs++;
529				Control().stats.blocks_in_indirect
530					+= runs[index].Length();
531			}
532			Control().stats.indirect_array_blocks++;
533
534			if (index < runsPerBlock)
535				break;
536		}
537	}
538
539	// check the double indirect range
540
541	if (data->max_double_indirect_range) {
542		status = _CheckAllocated(data->double_indirect, "double indirect");
543		if (status != B_OK)
544			return status;
545
546		int32 runsPerBlock = runs_per_block(GetVolume()->BlockSize());
547		int32 runsPerArray = runsPerBlock * data->double_indirect.Length();
548
549		CachedBlock cachedDirect(GetVolume());
550
551		for (int32 indirectIndex = 0; indirectIndex < runsPerArray;
552				indirectIndex++) {
553			// get the indirect array block
554			status = cached.SetTo(GetVolume()->ToBlock(data->double_indirect)
555					+ indirectIndex / runsPerBlock);
556			if (status != B_OK)
557				return status;
558
559			block_run* array = (block_run*)cached.Block();
560			block_run indirect = array[indirectIndex % runsPerBlock];
561			// are we finished yet?
562			if (indirect.IsZero())
563				return B_OK;
564
565			status = _CheckAllocated(indirect, "double indirect->runs");
566			if (status != B_OK)
567				return status;
568
569			int32 maxIndex
570				= ((uint32)indirect.Length() << GetVolume()->BlockShift())
571					/ sizeof(block_run);
572
573			for (int32 index = 0; index < maxIndex; ) {
574				status = cachedDirect.SetTo(GetVolume()->ToBlock(indirect)
575						+ index / runsPerBlock);
576				if (status != B_OK)
577					return status;
578
579				block_run* runs = (block_run*)cachedDirect.Block();
580
581				do {
582					// are we finished yet?
583					if (runs[index % runsPerBlock].IsZero())
584						return B_OK;
585
586					status = _CheckAllocated(runs[index % runsPerBlock],
587						"double indirect->runs->run");
588					if (status != B_OK)
589						return status;
590
591					Control().stats.double_indirect_block_runs++;
592					Control().stats.blocks_in_double_indirect
593						+= runs[index % runsPerBlock].Length();
594				} while ((++index % runsPerBlock) != 0);
595			}
596
597			Control().stats.double_indirect_array_blocks++;
598		}
599	}
600
601	return B_OK;
602}
603
604
605status_t
606CheckVisitor::_CheckAllocated(block_run run, const char* type)
607{
608	BlockAllocator& allocator = GetVolume()->Allocator();
609
610	// make sure the block run is valid
611	if (!allocator.IsValidBlockRun(run, type)) {
612		Control().errors |= BFS_INVALID_BLOCK_RUN;
613		return B_OK;
614	}
615
616	status_t status;
617
618	off_t start = GetVolume()->ToBlock(run);
619	off_t end = start + run.Length();
620
621	// check if the run is allocated in the block bitmap on disk
622	off_t block = start;
623
624	while (block < end) {
625		off_t firstMissing;
626		status = allocator.CheckBlocks(block, end - block, true, &firstMissing);
627		if (status == B_OK)
628			break;
629		else if (status != B_BAD_DATA)
630			return status;
631
632		off_t afterLastMissing;
633		status = allocator.CheckBlocks(firstMissing, end - firstMissing, false,
634			&afterLastMissing);
635		if (status == B_OK)
636			afterLastMissing = end;
637		else if (status != B_BAD_DATA)
638			return status;
639
640		PRINT(("%s: block_run(%" B_PRId32 ", %" B_PRIu16 ", %" B_PRIu16 ")"
641			": blocks %" B_PRIdOFF " - %" B_PRIdOFF " are not allocated!\n",
642			type, run.AllocationGroup(), run.Start(),
643			run.Length(), firstMissing, afterLastMissing - 1));
644
645		Control().stats.missing += afterLastMissing - firstMissing;
646
647		block = afterLastMissing;
648	}
649
650	// set bits in check bitmap, while checking if they're already set
651	off_t firstSet = -1;
652
653	for (block = start; block < end; block++) {
654		if (_CheckBitmapIsUsedAt(block)) {
655			if (firstSet == -1) {
656				firstSet = block;
657				Control().errors |= BFS_BLOCKS_ALREADY_SET;
658			}
659			Control().stats.already_set++;
660		} else {
661			if (firstSet != -1) {
662				FATAL(("%s: block_run(%d, %u, %u): blocks %" B_PRIdOFF
663					" - %" B_PRIdOFF " are already set!\n", type,
664					(int)run.AllocationGroup(), run.Start(), run.Length(),
665					firstSet, block - 1));
666				firstSet = -1;
667			}
668			_SetCheckBitmapAt(block);
669		}
670	}
671
672	return B_OK;
673}
674
675
676status_t
677CheckVisitor::_PrepareIndices()
678{
679	int32 count = 0;
680
681	for (int32 i = 0; i < Indices().CountItems(); i++) {
682		check_index* index = Indices().Array()[i];
683		Vnode vnode(GetVolume(), index->run);
684		Inode* inode;
685		status_t status = vnode.Get(&inode);
686		if (status != B_OK) {
687			FATAL(("check: Could not open index at %" B_PRIdOFF "\n",
688				GetVolume()->ToBlock(index->run)));
689			return status;
690		}
691
692		BPlusTree* tree = inode->Tree();
693		if (tree == NULL) {
694			// TODO: We can't yet repair those
695			continue;
696		}
697
698		status = tree->MakeEmpty();
699		if (status != B_OK)
700			return status;
701
702		index->inode = inode;
703		vnode.Keep();
704		count++;
705	}
706
707	return count == 0 ? B_ENTRY_NOT_FOUND : B_OK;
708}
709
710
711void
712CheckVisitor::_FreeIndices()
713{
714	for (int32 i = 0; i < Indices().CountItems(); i++) {
715		check_index* index = Indices().Array()[i];
716		if (index->inode != NULL) {
717			put_vnode(GetVolume()->FSVolume(),
718				GetVolume()->ToVnode(index->inode->BlockRun()));
719		}
720		delete index;
721	}
722	Indices().MakeEmpty();
723}
724
725
726status_t
727CheckVisitor::_AddInodeToIndex(Inode* inode)
728{
729	Transaction transaction(GetVolume(), inode->BlockNumber());
730
731	for (int32 i = 0; i < Indices().CountItems(); i++) {
732		check_index* index = Indices().Array()[i];
733		if (index->inode == NULL)
734			continue;
735
736		index->inode->WriteLockInTransaction(transaction);
737
738		BPlusTree* tree = index->inode->Tree();
739		if (tree == NULL)
740			return B_ERROR;
741
742		status_t status = B_OK;
743
744		if (!strcmp(index->name, "name")) {
745			if (inode->InNameIndex()) {
746				char name[B_FILE_NAME_LENGTH];
747				if (inode->GetName(name, B_FILE_NAME_LENGTH) != B_OK)
748					return B_ERROR;
749
750				status = tree->Insert(transaction, name, inode->ID());
751			}
752		} else if (!strcmp(index->name, "last_modified")) {
753			if (inode->InLastModifiedIndex()) {
754				status = tree->Insert(transaction, inode->OldLastModified(),
755					inode->ID());
756			}
757		} else if (!strcmp(index->name, "size")) {
758			if (inode->InSizeIndex())
759				status = tree->Insert(transaction, inode->Size(), inode->ID());
760		} else {
761			uint8 key[MAX_INDEX_KEY_LENGTH];
762			size_t keyLength = sizeof(key);
763			if (inode->ReadAttribute(index->name, B_ANY_TYPE, 0, key,
764					&keyLength) == B_OK) {
765				status = tree->Insert(transaction, key, keyLength, inode->ID());
766			}
767		}
768
769		if (status != B_OK)
770			return status;
771	}
772
773	return transaction.Done();
774}
775