1205408Srdivacky/* 2205408Srdivacky * Copyright 2001-2011, Haiku Inc. All rights reserved. 3205408Srdivacky * This file may be used under the terms of the MIT License. 4205408Srdivacky * 5205408Srdivacky * Authors: 6205408Srdivacky * J��r��me Duval 7205408Srdivacky * Janito V. Ferreira Filho 8205408Srdivacky */ 9205408Srdivacky 10205408Srdivacky 11205408Srdivacky#include "InodeAllocator.h" 12205408Srdivacky 13205408Srdivacky#include <util/AutoLock.h> 14205408Srdivacky 15205408Srdivacky#include "BitmapBlock.h" 16212904Sdim#include "Inode.h" 17249423Sdim#include "Volume.h" 18212904Sdim 19249423Sdim 20249423Sdim#undef ASSERT 21205408Srdivacky//#define TRACE_EXT2 22249423Sdim#ifdef TRACE_EXT2 23249423Sdim# define TRACE(x...) dprintf("\33[34mext2:\33[0m " x) 24249423Sdim# define ASSERT(x) { if (!(x)) kernel_debugger("ext2: assert failed: " #x "\n"); } 25205408Srdivacky#else 26226633Sdim# define TRACE(x...) ; 27249423Sdim# define ASSERT(x) ; 28263508Sdim#endif 29249423Sdim#define ERROR(x...) dprintf("\33[34mext2:\33[0m " x) 30249423Sdim 31249423Sdim 32205408SrdivackyInodeAllocator::InodeAllocator(Volume* volume) 33205408Srdivacky : 34219077Sdim fVolume(volume) 35249423Sdim{ 36249423Sdim mutex_init(&fLock, "ext2 inode allocator"); 37249423Sdim} 38249423Sdim 39249423Sdim 40249423SdimInodeAllocator::~InodeAllocator() 41243830Sdim{ 42205408Srdivacky mutex_destroy(&fLock); 43226633Sdim} 44226633Sdim 45249423Sdim 46226633Sdim/*virtual*/ status_t 47243830SdimInodeAllocator::New(Transaction& transaction, Inode* parent, int32 mode, 48226633Sdim ino_t& id) 49226633Sdim{ 50205408Srdivacky // Apply allocation policy 51226633Sdim uint32 preferredBlockGroup = parent != NULL ? (parent->ID() - 1) 52249423Sdim / parent->GetVolume()->InodesPerGroup() : 0; 53239462Sdim 54226633Sdim return _Allocate(transaction, preferredBlockGroup, S_ISDIR(mode), id); 55205408Srdivacky} 56205408Srdivacky 57205408Srdivacky 58205408Srdivacky/*virtual*/ status_t 59205408SrdivackyInodeAllocator::Free(Transaction& transaction, ino_t id, bool isDirectory) 60205408Srdivacky{ 61205408Srdivacky TRACE("InodeAllocator::Free(%d, %c)\n", (int)id, isDirectory ? 't' : 'f'); 62205408Srdivacky MutexLocker lock(fLock); 63205408Srdivacky 64205408Srdivacky uint32 numInodes = fVolume->InodesPerGroup(); 65205408Srdivacky uint32 blockGroup = (id - 1) / numInodes; 66205408Srdivacky ext2_block_group* group; 67205408Srdivacky 68205408Srdivacky status_t status = fVolume->GetBlockGroup(blockGroup, &group); 69205408Srdivacky if (status != B_OK) 70205408Srdivacky return status; 71205408Srdivacky 72205408Srdivacky if (group->Flags() & EXT2_BLOCK_GROUP_INODE_UNINIT) 73205408Srdivacky panic("InodeAllocator::Free() can't free inodes if uninit\n"); 74205408Srdivacky 75234353Sdim if (blockGroup == fVolume->NumGroups() - 1) 76205408Srdivacky numInodes = fVolume->NumInodes() - blockGroup * numInodes; 77205408Srdivacky 78205408Srdivacky TRACE("InodeAllocator::Free(): Updating block group data\n"); 79205408Srdivacky group->SetFreeInodes(group->FreeInodes(fVolume->Has64bitFeature()) + 1, 80205408Srdivacky fVolume->Has64bitFeature()); 81205408Srdivacky if (isDirectory) { 82205408Srdivacky group->SetUsedDirectories( 83205408Srdivacky group->UsedDirectories(fVolume->Has64bitFeature()) - 1, 84208600Srdivacky fVolume->Has64bitFeature()); 85208600Srdivacky } 86208600Srdivacky 87208600Srdivacky uint32 checksum = 0; 88208600Srdivacky status = _UnmarkInBitmap(transaction, 89208600Srdivacky group->InodeBitmap(fVolume->Has64bitFeature()), numInodes, id, 90208600Srdivacky checksum); 91205408Srdivacky if (status != B_OK) 92205408Srdivacky return status; 93205408Srdivacky _SetInodeBitmapChecksum(group, checksum); 94205408Srdivacky return fVolume->WriteBlockGroup(transaction, blockGroup); 95205408Srdivacky} 96205408Srdivacky 97205408Srdivacky 98205408Srdivackystatus_t 99205408SrdivackyInodeAllocator::_Allocate(Transaction& transaction, uint32 preferredBlockGroup, 100205408Srdivacky bool isDirectory, ino_t& id) 101234353Sdim{ 102205408Srdivacky MutexLocker lock(fLock); 103208600Srdivacky 104205408Srdivacky uint32 blockGroup = preferredBlockGroup; 105205408Srdivacky uint32 lastBlockGroup = fVolume->NumGroups() - 1; 106205408Srdivacky 107205408Srdivacky for (int i = 0; i < 2; ++i) { 108226633Sdim for (; blockGroup < lastBlockGroup; ++blockGroup) { 109205408Srdivacky if (_AllocateInGroup(transaction, blockGroup, 110205408Srdivacky isDirectory, id, fVolume->InodesPerGroup()) == B_OK) 111205408Srdivacky return B_OK; 112205408Srdivacky } 113205408Srdivacky 114205408Srdivacky if (i == 0 && _AllocateInGroup(transaction, blockGroup, 115205408Srdivacky isDirectory, id, fVolume->NumInodes() - blockGroup 116205408Srdivacky * fVolume->InodesPerGroup()) == B_OK) 117205408Srdivacky return B_OK; 118205408Srdivacky 119205408Srdivacky blockGroup = 0; 120205408Srdivacky lastBlockGroup = preferredBlockGroup; 121205408Srdivacky } 122205408Srdivacky 123226633Sdim ERROR("InodeAllocator::_Allocate() device is full\n"); 124205408Srdivacky return B_DEVICE_FULL; 125205408Srdivacky} 126205408Srdivacky 127205408Srdivacky 128205408Srdivackystatus_t 129205408SrdivackyInodeAllocator::_AllocateInGroup(Transaction& transaction, uint32 blockGroup, 130205408Srdivacky bool isDirectory, ino_t& id, uint32 numInodes) 131205408Srdivacky{ 132205408Srdivacky ext2_block_group* group; 133205408Srdivacky status_t status = fVolume->GetBlockGroup(blockGroup, &group); 134205408Srdivacky if (status != B_OK) { 135205408Srdivacky ERROR("InodeAllocator::_Allocate() GetBlockGroup() failed\n"); 136218893Sdim return status; 137218893Sdim } 138218893Sdim 139218893Sdim fsblock_t block = group->InodeBitmap(fVolume->Has64bitFeature()); 140218893Sdim if (block == 0) { 141218893Sdim ERROR("_AllocateInGroup(%" B_PRIu32 "): inodeBitmap is zero\n", 142218893Sdim blockGroup); 143218893Sdim return B_BAD_VALUE; 144218893Sdim } 145205408Srdivacky 146205408Srdivacky _InitGroup(transaction, group, block, fVolume->InodesPerGroup()); 147218893Sdim uint32 freeInodes = group->FreeInodes(fVolume->Has64bitFeature()); 148226633Sdim if (freeInodes == 0) 149226633Sdim return B_DEVICE_FULL; 150226633Sdim TRACE("InodeAllocator::_Allocate() freeInodes %" B_PRId32 "\n", 151226633Sdim freeInodes); 152226633Sdim group->SetFreeInodes(freeInodes - 1, fVolume->Has64bitFeature()); 153226633Sdim if (isDirectory) { 154226633Sdim group->SetUsedDirectories(group->UsedDirectories( 155226633Sdim fVolume->Has64bitFeature()) + 1, 156218893Sdim fVolume->Has64bitFeature()); 157218893Sdim } 158218893Sdim 159218893Sdim uint32 pos = 0; 160221345Sdim uint32 checksum = 0; 161226633Sdim status = _MarkInBitmap(transaction, block, blockGroup, 162249423Sdim fVolume->InodesPerGroup(), pos, checksum); 163218893Sdim if (status != B_OK) 164226633Sdim return status; 165218893Sdim 166218893Sdim if ((fVolume->HasChecksumFeature() || fVolume->HasMetaGroupChecksumFeature()) 167205408Srdivacky && pos > (fVolume->InodesPerGroup() 168205408Srdivacky - group->UnusedInodes(fVolume->Has64bitFeature()) - 1)) { 169205408Srdivacky group->SetUnusedInodes(fVolume->InodesPerGroup() - pos - 1, 170205408Srdivacky fVolume->Has64bitFeature()); 171205408Srdivacky } 172205408Srdivacky _SetInodeBitmapChecksum(group, checksum); 173205408Srdivacky status = fVolume->WriteBlockGroup(transaction, blockGroup); 174205408Srdivacky if (status != B_OK) 175218893Sdim return status; 176249423Sdim 177226633Sdim id = pos + blockGroup * fVolume->InodesPerGroup() + 1; 178205408Srdivacky 179205408Srdivacky return status; 180205408Srdivacky} 181205408Srdivacky 182205408Srdivacky 183205408Srdivackystatus_t 184205408SrdivackyInodeAllocator::_MarkInBitmap(Transaction& transaction, fsblock_t bitmapBlock, 185205408Srdivacky uint32 blockGroup, uint32 numInodes, uint32& pos, uint32& checksum) 186205408Srdivacky{ 187205408Srdivacky BitmapBlock inodeBitmap(fVolume, numInodes); 188205408Srdivacky 189205408Srdivacky if (!inodeBitmap.SetToWritable(transaction, bitmapBlock)) { 190239462Sdim ERROR("Unable to open inode bitmap (block number: %" B_PRIu64 191239462Sdim ") for block group %" B_PRIu32 "\n", bitmapBlock, blockGroup); 192239462Sdim return B_IO_ERROR; 193239462Sdim } 194239462Sdim 195239462Sdim pos = 0; 196205408Srdivacky inodeBitmap.FindNextUnmarked(pos); 197205408Srdivacky 198205408Srdivacky if (pos == inodeBitmap.NumBits()) { 199205408Srdivacky ERROR("Even though the block group %" B_PRIu32 " indicates there are " 200226633Sdim "free inodes, no unmarked bit was found in the inode bitmap at " 201226633Sdim "block %" B_PRIu64 " (numInodes %" B_PRIu32 ").\n", blockGroup, 202226633Sdim bitmapBlock, numInodes); 203226633Sdim return B_ERROR; 204226633Sdim } 205205408Srdivacky 206226633Sdim if (!inodeBitmap.Mark(pos, 1)) { 207205408Srdivacky ERROR("Failed to mark bit %" B_PRIu32 " at bitmap block %" B_PRIu64 208205408Srdivacky "\n", pos, bitmapBlock); 209205408Srdivacky return B_BAD_DATA; 210205408Srdivacky } 211205408Srdivacky 212205408Srdivacky checksum = inodeBitmap.Checksum(fVolume->InodesPerGroup()); 213205408Srdivacky 214205408Srdivacky return B_OK; 215205408Srdivacky} 216205408Srdivacky 217205408Srdivacky 218205408Srdivackystatus_t 219205408SrdivackyInodeAllocator::_UnmarkInBitmap(Transaction& transaction, fsblock_t bitmapBlock, 220205408Srdivacky uint32 numInodes, ino_t id, uint32& checksum) 221212904Sdim{ 222212904Sdim BitmapBlock inodeBitmap(fVolume, numInodes); 223205408Srdivacky 224205408Srdivacky if (!inodeBitmap.SetToWritable(transaction, bitmapBlock)) { 225205408Srdivacky ERROR("Unable to open inode bitmap at block %" B_PRIu64 "\n", 226205408Srdivacky bitmapBlock); 227205408Srdivacky return B_IO_ERROR; 228205408Srdivacky } 229234353Sdim 230218893Sdim uint32 pos = (id - 1) % fVolume->InodesPerGroup(); 231206084Srdivacky if (!inodeBitmap.Unmark(pos, 1)) { 232207619Srdivacky ERROR("Unable to unmark bit %" B_PRIu32 " in inode bitmap block %" 233205408Srdivacky B_PRIu64 "\n", pos, bitmapBlock); 234218893Sdim return B_BAD_DATA; 235205408Srdivacky } 236205408Srdivacky 237205408Srdivacky checksum = inodeBitmap.Checksum(fVolume->InodesPerGroup()); 238205408Srdivacky 239205408Srdivacky return B_OK; 240205408Srdivacky} 241205408Srdivacky 242205408Srdivacky 243207619Srdivackystatus_t 244207619SrdivackyInodeAllocator::_InitGroup(Transaction& transaction, ext2_block_group* group, 245207619Srdivacky fsblock_t bitmapBlock, uint32 numInodes) 246207619Srdivacky{ 247207619Srdivacky uint16 flags = group->Flags(); 248207619Srdivacky if ((flags & EXT2_BLOCK_GROUP_INODE_UNINIT) == 0) 249207619Srdivacky return B_OK; 250226633Sdim 251226633Sdim TRACE("InodeAllocator::_InitGroup() initing group\n"); 252234353Sdim BitmapBlock inodeBitmap(fVolume, numInodes); 253234353Sdim if (!inodeBitmap.SetToWritable(transaction, bitmapBlock)) 254226633Sdim return B_ERROR; 255226633Sdim inodeBitmap.Unmark(0, numInodes, true); 256207619Srdivacky group->SetFlags(flags & ~EXT2_BLOCK_GROUP_INODE_UNINIT); 257207619Srdivacky 258207619Srdivacky return B_OK; 259207619Srdivacky} 260207619Srdivacky 261234353Sdim 262205408Srdivackyvoid 263205408SrdivackyInodeAllocator::_SetInodeBitmapChecksum(ext2_block_group* group, uint32 checksum) 264206084Srdivacky{ 265205408Srdivacky if (fVolume->HasMetaGroupChecksumFeature()) { 266205408Srdivacky group->inode_bitmap_csum = checksum & 0xffff; 267205408Srdivacky if (fVolume->GroupDescriptorSize() >= offsetof(ext2_block_group, 268205408Srdivacky _reserved)) { 269205408Srdivacky group->inode_bitmap_csum_high = checksum >> 16; 270205408Srdivacky } 271205408Srdivacky } 272205408Srdivacky} 273205408Srdivacky 274205408Srdivacky