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
InodeAllocator(Volume * volume)32 InodeAllocator::InodeAllocator(Volume* volume)
33 :
34 fVolume(volume)
35 {
36 mutex_init(&fLock, "ext2 inode allocator");
37 }
38
39
~InodeAllocator()40 InodeAllocator::~InodeAllocator()
41 {
42 mutex_destroy(&fLock);
43 }
44
45
46 /*virtual*/ status_t
New(Transaction & transaction,Inode * parent,int32 mode,ino_t & id)47 InodeAllocator::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
Free(Transaction & transaction,ino_t id,bool isDirectory)59 InodeAllocator::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
98 status_t
_Allocate(Transaction & transaction,uint32 preferredBlockGroup,bool isDirectory,ino_t & id)99 InodeAllocator::_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
128 status_t
_AllocateInGroup(Transaction & transaction,uint32 blockGroup,bool isDirectory,ino_t & id,uint32 numInodes)129 InodeAllocator::_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
183 status_t
_MarkInBitmap(Transaction & transaction,fsblock_t bitmapBlock,uint32 blockGroup,uint32 numInodes,uint32 & pos,uint32 & checksum)184 InodeAllocator::_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
218 status_t
_UnmarkInBitmap(Transaction & transaction,fsblock_t bitmapBlock,uint32 numInodes,ino_t id,uint32 & checksum)219 InodeAllocator::_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
243 status_t
_InitGroup(Transaction & transaction,ext2_block_group * group,fsblock_t bitmapBlock,uint32 numInodes)244 InodeAllocator::_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
262 void
_SetInodeBitmapChecksum(ext2_block_group * group,uint32 checksum)263 InodeAllocator::_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