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	status = fVolume->WriteBlockGroup(transaction, blockGroup);
88	if (status != B_OK)
89		return status;
90
91	return _UnmarkInBitmap(transaction,
92		group->InodeBitmap(fVolume->Has64bitFeature()), numInodes, id);
93}
94
95
96status_t
97InodeAllocator::_Allocate(Transaction& transaction, uint32 preferredBlockGroup,
98	bool isDirectory, ino_t& id)
99{
100	MutexLocker lock(fLock);
101
102	uint32 blockGroup = preferredBlockGroup;
103	uint32 lastBlockGroup = fVolume->NumGroups() - 1;
104
105	for (int i = 0; i < 2; ++i) {
106		for (; blockGroup < lastBlockGroup; ++blockGroup) {
107			if (_AllocateInGroup(transaction, blockGroup,
108				isDirectory, id, fVolume->InodesPerGroup()) == B_OK)
109				return B_OK;
110		}
111
112		if (i == 0 && _AllocateInGroup(transaction, blockGroup,
113			isDirectory, id, fVolume->NumInodes() - blockGroup
114				* fVolume->InodesPerGroup()) == B_OK)
115			return B_OK;
116
117		blockGroup = 0;
118		lastBlockGroup = preferredBlockGroup;
119	}
120
121	ERROR("InodeAllocator::_Allocate() device is full\n");
122	return B_DEVICE_FULL;
123}
124
125
126status_t
127InodeAllocator::_AllocateInGroup(Transaction& transaction, uint32 blockGroup,
128	bool isDirectory, ino_t& id, uint32 numInodes)
129{
130	ext2_block_group* group;
131	status_t status = fVolume->GetBlockGroup(blockGroup, &group);
132	if (status != B_OK) {
133		ERROR("InodeAllocator::_Allocate() GetBlockGroup() failed\n");
134		return status;
135	}
136
137	fsblock_t block = group->InodeBitmap(fVolume->Has64bitFeature());
138	_InitGroup(transaction, group, block, fVolume->InodesPerGroup());
139	uint32 freeInodes = group->FreeInodes(fVolume->Has64bitFeature());
140	if (freeInodes == 0)
141		return B_DEVICE_FULL;
142	TRACE("InodeAllocator::_Allocate() freeInodes %ld\n",
143		freeInodes);
144	group->SetFreeInodes(freeInodes - 1, fVolume->Has64bitFeature());
145	if (isDirectory) {
146		group->SetUsedDirectories(group->UsedDirectories(
147			fVolume->Has64bitFeature()) + 1,
148			fVolume->Has64bitFeature());
149	}
150
151	uint32 pos = 0;
152	status = _MarkInBitmap(transaction, block, blockGroup,
153		fVolume->InodesPerGroup(), pos);
154	if (status != B_OK)
155		return status;
156
157	if (fVolume->HasChecksumFeature() && pos > (fVolume->InodesPerGroup() - 1
158		- group->UnusedInodes(fVolume->Has64bitFeature()))) {
159		group->SetUnusedInodes(fVolume->InodesPerGroup() - 1 - pos,
160			fVolume->Has64bitFeature());
161	}
162
163	status = fVolume->WriteBlockGroup(transaction, blockGroup);
164	if (status != B_OK)
165		return status;
166
167	id = pos + blockGroup * fVolume->InodesPerGroup() + 1;
168
169	return status;
170}
171
172
173status_t
174InodeAllocator::_MarkInBitmap(Transaction& transaction, fsblock_t bitmapBlock,
175	uint32 blockGroup, uint32 numInodes, uint32& pos)
176{
177	BitmapBlock inodeBitmap(fVolume, numInodes);
178
179	if (!inodeBitmap.SetToWritable(transaction, bitmapBlock)) {
180		ERROR("Unable to open inode bitmap (block number: %llu) for block group "
181			"%lu\n", bitmapBlock, blockGroup);
182		return B_IO_ERROR;
183	}
184
185	pos = 0;
186	inodeBitmap.FindNextUnmarked(pos);
187
188	if (pos == inodeBitmap.NumBits()) {
189		ERROR("Even though the block group %lu indicates there are free "
190			"inodes, no unmarked bit was found in the inode bitmap at block "
191			"%llu (numInodes %lu).\n", blockGroup, bitmapBlock, numInodes);
192		return B_ERROR;
193	}
194
195	if (!inodeBitmap.Mark(pos, 1)) {
196		ERROR("Failed to mark bit %lu at bitmap block %llu\n", pos,
197			bitmapBlock);
198		return B_BAD_DATA;
199	}
200
201	return B_OK;
202}
203
204
205status_t
206InodeAllocator::_UnmarkInBitmap(Transaction& transaction, fsblock_t bitmapBlock,
207	uint32 numInodes, ino_t id)
208{
209	BitmapBlock inodeBitmap(fVolume, numInodes);
210
211	if (!inodeBitmap.SetToWritable(transaction, bitmapBlock)) {
212		ERROR("Unable to open inode bitmap at block %llu\n", bitmapBlock);
213		return B_IO_ERROR;
214	}
215
216	uint32 pos = (id - 1) % fVolume->InodesPerGroup();
217	if (!inodeBitmap.Unmark(pos, 1)) {
218		ERROR("Unable to unmark bit %lu in inode bitmap block %llu\n", pos,
219			bitmapBlock);
220		return B_BAD_DATA;
221	}
222
223	return B_OK;
224}
225
226
227status_t
228InodeAllocator::_InitGroup(Transaction& transaction, ext2_block_group* group,
229	fsblock_t bitmapBlock, uint32 numInodes)
230{
231	uint16 flags = group->Flags();
232	if ((flags & EXT2_BLOCK_GROUP_INODE_UNINIT) == 0)
233		return B_OK;
234
235	TRACE("InodeAllocator::_InitGroup() initing group\n");
236	BitmapBlock inodeBitmap(fVolume, numInodes);
237	if (!inodeBitmap.SetToWritable(transaction, bitmapBlock))
238		return B_ERROR;
239	inodeBitmap.Unmark(0, numInodes, true);
240	group->SetFlags(flags & ~EXT2_BLOCK_GROUP_INODE_UNINIT);
241
242	return B_OK;
243}
244
245