1/*
2 * Copyright 2001-2011, Haiku Inc. All rights reserved.
3 * This file may be used under the terms of the MIT License.
4 *
5 * Authors:
6 *		J��r��me Duval
7 *		Janito V. Ferreira Filho
8 */
9
10
11#include "InodeAllocator.h"
12
13#include <util/AutoLock.h>
14
15#include "BitmapBlock.h"
16#include "Inode.h"
17#include "Volume.h"
18
19
20#undef ASSERT
21//#define TRACE_EXT2
22#ifdef TRACE_EXT2
23#	define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
24#	define ASSERT(x) { if (!(x)) kernel_debugger("ext2: assert failed: " #x "\n"); }
25#else
26#	define TRACE(x...) ;
27#	define ASSERT(x) ;
28#endif
29#define ERROR(x...) dprintf("\33[34mext2:\33[0m " x)
30
31
32InodeAllocator::InodeAllocator(Volume* volume)
33	:
34	fVolume(volume)
35{
36	mutex_init(&fLock, "ext2 inode allocator");
37}
38
39
40InodeAllocator::~InodeAllocator()
41{
42	mutex_destroy(&fLock);
43}
44
45
46/*virtual*/ status_t
47InodeAllocator::New(Transaction& transaction, Inode* parent, int32 mode,
48	ino_t& id)
49{
50	// Apply allocation policy
51	uint32 preferredBlockGroup = parent != NULL ? (parent->ID() - 1)
52		/ parent->GetVolume()->InodesPerGroup() : 0;
53
54	return _Allocate(transaction, preferredBlockGroup, S_ISDIR(mode), id);
55}
56
57
58/*virtual*/ status_t
59InodeAllocator::Free(Transaction& transaction, ino_t id, bool isDirectory)
60{
61	TRACE("InodeAllocator::Free(%d, %c)\n", (int)id, isDirectory ? 't' : 'f');
62	MutexLocker lock(fLock);
63
64	uint32 numInodes = fVolume->InodesPerGroup();
65	uint32 blockGroup = (id - 1) / numInodes;
66	ext2_block_group* group;
67
68	status_t status = fVolume->GetBlockGroup(blockGroup, &group);
69	if (status != B_OK)
70		return status;
71
72	if (group->Flags() & EXT2_BLOCK_GROUP_INODE_UNINIT)
73		panic("InodeAllocator::Free() can't free inodes if uninit\n");
74
75	if (blockGroup == fVolume->NumGroups() - 1)
76		numInodes = fVolume->NumInodes() - blockGroup * numInodes;
77
78	TRACE("InodeAllocator::Free(): Updating block group data\n");
79	group->SetFreeInodes(group->FreeInodes(fVolume->Has64bitFeature()) + 1,
80		fVolume->Has64bitFeature());
81	if (isDirectory) {
82		group->SetUsedDirectories(
83			group->UsedDirectories(fVolume->Has64bitFeature()) - 1,
84			fVolume->Has64bitFeature());
85	}
86
87	uint32 checksum = 0;
88	status = _UnmarkInBitmap(transaction,
89		group->InodeBitmap(fVolume->Has64bitFeature()), numInodes, id,
90		checksum);
91	if (status != B_OK)
92		return status;
93	_SetInodeBitmapChecksum(group, checksum);
94	return fVolume->WriteBlockGroup(transaction, blockGroup);
95}
96
97
98status_t
99InodeAllocator::_Allocate(Transaction& transaction, uint32 preferredBlockGroup,
100	bool isDirectory, ino_t& id)
101{
102	MutexLocker lock(fLock);
103
104	uint32 blockGroup = preferredBlockGroup;
105	uint32 lastBlockGroup = fVolume->NumGroups() - 1;
106
107	for (int i = 0; i < 2; ++i) {
108		for (; blockGroup < lastBlockGroup; ++blockGroup) {
109			if (_AllocateInGroup(transaction, blockGroup,
110				isDirectory, id, fVolume->InodesPerGroup()) == B_OK)
111				return B_OK;
112		}
113
114		if (i == 0 && _AllocateInGroup(transaction, blockGroup,
115			isDirectory, id, fVolume->NumInodes() - blockGroup
116				* fVolume->InodesPerGroup()) == B_OK)
117			return B_OK;
118
119		blockGroup = 0;
120		lastBlockGroup = preferredBlockGroup;
121	}
122
123	ERROR("InodeAllocator::_Allocate() device is full\n");
124	return B_DEVICE_FULL;
125}
126
127
128status_t
129InodeAllocator::_AllocateInGroup(Transaction& transaction, uint32 blockGroup,
130	bool isDirectory, ino_t& id, uint32 numInodes)
131{
132	ext2_block_group* group;
133	status_t status = fVolume->GetBlockGroup(blockGroup, &group);
134	if (status != B_OK) {
135		ERROR("InodeAllocator::_Allocate() GetBlockGroup() failed\n");
136		return status;
137	}
138
139	fsblock_t block = group->InodeBitmap(fVolume->Has64bitFeature());
140	if (block == 0) {
141		ERROR("_AllocateInGroup(%" B_PRIu32 "): inodeBitmap is zero\n",
142			blockGroup);
143		return B_BAD_VALUE;
144	}
145
146	_InitGroup(transaction, group, block, fVolume->InodesPerGroup());
147	uint32 freeInodes = group->FreeInodes(fVolume->Has64bitFeature());
148	if (freeInodes == 0)
149		return B_DEVICE_FULL;
150	TRACE("InodeAllocator::_Allocate() freeInodes %" B_PRId32 "\n",
151		freeInodes);
152	group->SetFreeInodes(freeInodes - 1, fVolume->Has64bitFeature());
153	if (isDirectory) {
154		group->SetUsedDirectories(group->UsedDirectories(
155			fVolume->Has64bitFeature()) + 1,
156			fVolume->Has64bitFeature());
157	}
158
159	uint32 pos = 0;
160	uint32 checksum = 0;
161	status = _MarkInBitmap(transaction, block, blockGroup,
162		fVolume->InodesPerGroup(), pos, checksum);
163	if (status != B_OK)
164		return status;
165
166	if ((fVolume->HasChecksumFeature() || fVolume->HasMetaGroupChecksumFeature())
167		&& pos > (fVolume->InodesPerGroup()
168			- group->UnusedInodes(fVolume->Has64bitFeature()) - 1)) {
169		group->SetUnusedInodes(fVolume->InodesPerGroup() - pos - 1,
170			fVolume->Has64bitFeature());
171	}
172	_SetInodeBitmapChecksum(group, checksum);
173	status = fVolume->WriteBlockGroup(transaction, blockGroup);
174	if (status != B_OK)
175		return status;
176
177	id = pos + blockGroup * fVolume->InodesPerGroup() + 1;
178
179	return status;
180}
181
182
183status_t
184InodeAllocator::_MarkInBitmap(Transaction& transaction, fsblock_t bitmapBlock,
185	uint32 blockGroup, uint32 numInodes, uint32& pos, uint32& checksum)
186{
187	BitmapBlock inodeBitmap(fVolume, numInodes);
188
189	if (!inodeBitmap.SetToWritable(transaction, bitmapBlock)) {
190		ERROR("Unable to open inode bitmap (block number: %" B_PRIu64
191			") for block group %" B_PRIu32 "\n", bitmapBlock, blockGroup);
192		return B_IO_ERROR;
193	}
194
195	pos = 0;
196	inodeBitmap.FindNextUnmarked(pos);
197
198	if (pos == inodeBitmap.NumBits()) {
199		ERROR("Even though the block group %" B_PRIu32 " indicates there are "
200			"free inodes, no unmarked bit was found in the inode bitmap at "
201			"block %" B_PRIu64 " (numInodes %" B_PRIu32 ").\n", blockGroup,
202			bitmapBlock, numInodes);
203		return B_ERROR;
204	}
205
206	if (!inodeBitmap.Mark(pos, 1)) {
207		ERROR("Failed to mark bit %" B_PRIu32 " at bitmap block %" B_PRIu64
208			"\n", pos, bitmapBlock);
209		return B_BAD_DATA;
210	}
211
212	checksum = inodeBitmap.Checksum(fVolume->InodesPerGroup());
213
214	return B_OK;
215}
216
217
218status_t
219InodeAllocator::_UnmarkInBitmap(Transaction& transaction, fsblock_t bitmapBlock,
220	uint32 numInodes, ino_t id, uint32& checksum)
221{
222	BitmapBlock inodeBitmap(fVolume, numInodes);
223
224	if (!inodeBitmap.SetToWritable(transaction, bitmapBlock)) {
225		ERROR("Unable to open inode bitmap at block %" B_PRIu64 "\n",
226			bitmapBlock);
227		return B_IO_ERROR;
228	}
229
230	uint32 pos = (id - 1) % fVolume->InodesPerGroup();
231	if (!inodeBitmap.Unmark(pos, 1)) {
232		ERROR("Unable to unmark bit %" B_PRIu32 " in inode bitmap block %"
233			B_PRIu64 "\n", pos, bitmapBlock);
234		return B_BAD_DATA;
235	}
236
237	checksum = inodeBitmap.Checksum(fVolume->InodesPerGroup());
238
239	return B_OK;
240}
241
242
243status_t
244InodeAllocator::_InitGroup(Transaction& transaction, ext2_block_group* group,
245	fsblock_t bitmapBlock, uint32 numInodes)
246{
247	uint16 flags = group->Flags();
248	if ((flags & EXT2_BLOCK_GROUP_INODE_UNINIT) == 0)
249		return B_OK;
250
251	TRACE("InodeAllocator::_InitGroup() initing group\n");
252	BitmapBlock inodeBitmap(fVolume, numInodes);
253	if (!inodeBitmap.SetToWritable(transaction, bitmapBlock))
254		return B_ERROR;
255	inodeBitmap.Unmark(0, numInodes, true);
256	group->SetFlags(flags & ~EXT2_BLOCK_GROUP_INODE_UNINIT);
257
258	return B_OK;
259}
260
261
262void
263InodeAllocator::_SetInodeBitmapChecksum(ext2_block_group* group, uint32 checksum)
264{
265	if (fVolume->HasMetaGroupChecksumFeature()) {
266		group->inode_bitmap_csum = checksum & 0xffff;
267		if (fVolume->GroupDescriptorSize() >= offsetof(ext2_block_group,
268			_reserved)) {
269			group->inode_bitmap_csum_high = checksum >> 16;
270		}
271	}
272}
273
274