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 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 96 status_t 97 InodeAllocator::_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 126 status_t 127 InodeAllocator::_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 173 status_t 174 InodeAllocator::_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 205 status_t 206 InodeAllocator::_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 227 status_t 228 InodeAllocator::_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