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 32 InodeAllocator::InodeAllocator(Volume* volume) 33 : 34 fVolume(volume) 35 { 36 mutex_init(&fLock, "ext2 inode allocator"); 37 } 38 39 40 InodeAllocator::~InodeAllocator() 41 { 42 mutex_destroy(&fLock); 43 } 44 45 46 /*virtual*/ status_t 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 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 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 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 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 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 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 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