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