1/*
2 * Copyright 2001-2008, pinc Software. All Rights Reserved.
3 * Released under the terms of the MIT license.
4 */
5
6//!	handles the BFS block bitmap
7
8
9#include "Bitmap.h"
10#include "Disk.h"
11#include "Inode.h"
12
13#include <stdlib.h>
14#include <stdio.h>
15#include <string.h>
16
17
18Bitmap::Bitmap(Disk *disk)
19	:
20	fBitmap(NULL),
21	fBackupBitmap(NULL)
22{
23	SetTo(disk);
24}
25
26
27Bitmap::Bitmap()
28	:
29	fDisk(NULL),
30	fBitmap(NULL),
31	fBackupBitmap(NULL),
32	fSize(0L),
33	fByteSize(0L),
34	fUsedBlocks(0LL)
35{
36}
37
38
39Bitmap::~Bitmap()
40{
41	free(fBitmap);
42	free(fBackupBitmap);
43}
44
45
46status_t
47Bitmap::SetTo(Disk *disk)
48{
49	free(fBitmap);
50
51	fDisk = disk;
52	fSize = divide_roundup(disk->NumBlocks(),disk->BlockSize() * 8);
53	fByteSize = disk->BlockSize() * disk->SuperBlock()->num_ags
54		* disk->SuperBlock()->blocks_per_ag;
55
56	fBitmap = (uint32 *)malloc(fByteSize);
57	if (!fBitmap)
58		return B_NO_MEMORY;
59
60	fBackupBitmap = (uint32 *)malloc(fByteSize);
61	if (fBackupBitmap == NULL)
62		return B_NO_MEMORY;
63
64	memset(fBackupBitmap, 0, fByteSize);
65
66	// set root block, block bitmap, log as used
67	off_t end = disk->ToBlock(disk->Log()) + disk->Log().length;
68	for (off_t block = 0; block < end; block++) {
69		if (!BackupSetAt(block, true))
70			break;
71	}
72
73	ssize_t size;
74	if ((size = disk->ReadAt(disk->BlockSize(), fBitmap, fByteSize)) < B_OK) {
75		free(fBitmap);
76		fBitmap = NULL;
77
78		free(fBackupBitmap);
79		fBackupBitmap = NULL;
80		return size;
81	}
82
83	// calculate used blocks
84
85	fUsedBlocks = 0LL;
86	for (uint32 i = fByteSize >> 2;i-- > 0;) {
87		uint32 compare = 1;
88		for (int16 j = 0;j < 32;j++,compare <<= 1) {
89			if (compare & fBitmap[i])
90				fUsedBlocks++;
91		}
92	}
93
94	return B_OK;
95}
96
97
98status_t
99Bitmap::InitCheck()
100{
101	return fBitmap ? B_OK : B_ERROR;
102}
103
104
105off_t
106Bitmap::FreeBlocks() const
107{
108	if (fDisk == NULL)
109		return 0;
110
111	return fDisk->NumBlocks() - fUsedBlocks;
112}
113
114
115bool
116Bitmap::UsedAt(off_t block) const
117{
118	uint32 index = block / 32;	// 32bit resolution, (beginning with block 1?)
119	if (index > fByteSize / 4)
120		return false;
121
122	return fBitmap[index] & (1L << (block & 0x1f));
123}
124
125
126bool
127Bitmap::BackupUsedAt(off_t block) const
128{
129	uint32 index = block / 32;	// 32bit resolution, (beginning with block 1?)
130	if (index > fByteSize / 4)
131		return false;
132
133	return fBackupBitmap[index] & (1L << (block & 0x1f));
134}
135
136
137bool
138Bitmap::BackupSetAt(off_t block, bool used)
139{
140	uint32 index = block / 32;
141	if (index > fByteSize / 4) {
142		fprintf(stderr, "Bitmap::BackupSetAt(): Block %" B_PRIdOFF " outside "
143			"bitmap!\n", block);
144		return false;
145	}
146
147	int32 mask = 1L << (block & 0x1f);
148
149	bool oldUsed = fBackupBitmap[index] & mask;
150
151	if (used)
152		fBackupBitmap[index] |= mask;
153	else
154		fBackupBitmap[index] &= ~mask;
155
156	return oldUsed;
157}
158
159
160void
161Bitmap::BackupSet(Inode *inode, bool used)
162{
163	// set inode and its data-stream
164
165	// the attributes are ignored for now, because they will
166	// be added anyway since all inodes from disk are collected.
167
168//	printf("a: %lld\n",inode->Block());
169	BackupSetAt(inode->Block(),used);
170
171	// the data stream of symlinks is no real data stream
172	if (inode->IsSymlink() && (inode->Flags() & INODE_LONG_SYMLINK) == 0)
173		return;
174
175	// direct blocks
176
177	const bfs_inode *node = inode->InodeBuffer();
178	for (int32 i = 0; i < NUM_DIRECT_BLOCKS; i++) {
179		if (node->data.direct[i].IsZero())
180			break;
181
182		off_t start = fDisk->ToBlock(node->data.direct[i]);
183		off_t end = start + node->data.direct[i].length;
184		for (off_t block = start; block < end; block++) {
185			if (!BackupSetAt(block, used)) {
186				//dump_inode(node);
187				break;
188			}
189		}
190	}
191
192	// indirect blocks
193
194	if (node->data.max_indirect_range == 0 || node->data.indirect.IsZero())
195		return;
196
197//	printf("c: %lld\n",fDisk->ToBlock(node->data.indirect));
198	BackupSetAt(fDisk->ToBlock(node->data.indirect), used);
199
200	DataStream *stream = dynamic_cast<DataStream *>(inode);
201	if (stream == NULL)
202		return;
203
204	// load indirect blocks
205	int32 bytes = node->data.indirect.length << fDisk->BlockShift();
206	block_run *indirect = (block_run *)malloc(bytes);
207	if (indirect == NULL)
208		return;
209
210	if (fDisk->ReadAt(fDisk->ToOffset(node->data.indirect), indirect,
211			bytes) <= 0)
212		return;
213
214	int32 runs = bytes / sizeof(block_run);
215	for (int32 i = 0; i < runs; i++) {
216		if (indirect[i].IsZero())
217			break;
218
219		off_t start = fDisk->ToBlock(indirect[i]);
220		off_t end = start + indirect[i].length;
221		for (off_t block = start; block < end; block++) {
222//			printf("d: %lld\n", block);
223			if (!BackupSetAt(block, used))
224				break;
225		}
226	}
227	free(indirect);
228
229	// double indirect blocks
230
231	if (node->data.max_double_indirect_range == 0
232		|| node->data.double_indirect.IsZero())
233		return;
234
235//	printf("e: %lld\n",fDisk->ToBlock(node->data.double_indirect));
236	BackupSetAt(fDisk->ToBlock(node->data.double_indirect), used);
237
238	// FIXME: to be implemented...
239	puts("double indirect blocks to block bitmap requested...");
240}
241
242
243status_t
244Bitmap::Validate()
245{
246	return B_OK;
247}
248
249
250status_t
251Bitmap::CompareWithBackup()
252{
253	for (int32 i = fByteSize / 4;i-- > 0;) {
254		if (fBitmap[i] != fBackupBitmap[i]) {
255			printf("differ at %" B_PRId32 " (block %" B_PRId32 ") -> bitmap = "
256				"%08" B_PRIx32 ", backup = %08" B_PRIx32 "\n", i, i * 32,
257				fBitmap[i], fBackupBitmap[i]);
258		}
259	}
260	return B_OK;
261}
262
263
264bool
265Bitmap::TrustBlockContaining(off_t /*block*/) const
266{
267	return true;
268}
269
270