1//---------------------------------------------------------------------- 2// This software is part of the OpenBeOS distribution and is covered 3// by the OpenBeOS license. 4// 5// Copyright (c) 2003 Tyler Dauwalder, tyler@dauwalder.net 6//---------------------------------------------------------------------- 7 8/*! \file Allocator.cpp 9 10 Physical block allocator class implementation. 11*/ 12 13#include "Allocator.h" 14 15#include <limits.h> 16 17#include "Utils.h" 18 19/*! \brief Creates a new Allocator object. 20*/ 21Allocator::Allocator(uint32 blockSize) 22 : fLength(0) 23 , fBlockSize(blockSize) 24 , fBlockShift(0) 25 , fInitStatus(B_NO_INIT) 26{ 27 status_t error = Udf::get_block_shift(BlockSize(), fBlockShift); 28 if (!error) 29 fInitStatus = B_OK; 30} 31 32status_t 33Allocator::InitCheck() const 34{ 35 return fInitStatus; 36} 37 38/*! \brief Allocates the given block, if available. 39 40 \return 41 - B_OK: Success. 42 - error code: Failure, the block has already been allocated. 43*/ 44status_t 45Allocator::GetBlock(uint32 block) 46{ 47 Udf::extent_address extent(block, BlockSize()); 48 return GetExtent(extent); 49} 50 51/*! \brief Allocates the given extent, if available. 52 53 \return 54 - B_OK: Success. 55 - error code: Failure, the extent (or some portion of it) has already 56 been allocated. 57*/ 58status_t 59Allocator::GetExtent(Udf::extent_address extent) 60{ 61 status_t error = InitCheck(); 62 if (!error) { 63 uint32 offset = extent.location(); 64 uint32 length = BlocksFor(extent.length()); 65 // First see if the extent is past the allocation tail, 66 // since we then don't have to do any chunklist traversal 67 if (offset >= Length()) { 68 // Add a new chunk to the end of the chunk list if 69 // necessary 70 if (offset > Length()) { 71 Udf::extent_address chunk(Length(), (offset-Length())<<BlockShift()); 72 fChunkList.push_back(chunk); 73 } 74 // Adjust the tail 75 fLength = offset+length; 76 return B_OK; 77 } else { 78 // Block is not past tail, so check the chunk list 79 for (list<Udf::extent_address>::iterator i = fChunkList.begin(); 80 i != fChunkList.end(); 81 i++) 82 { 83 uint32 chunkOffset = i->location(); 84 uint32 chunkLength = BlocksFor(i->length()); 85 if (chunkOffset <= offset && (offset+length) <= (chunkOffset+chunkLength)) { 86 // Found it. Split the chunk. First look for an orphan 87 // before the block, then after. 88 if (chunkOffset < offset) { 89 // Orhpan before; add a new chunk in front 90 // of the current one 91 Udf::extent_address chunk(chunkOffset, (offset-chunkOffset)<<BlockShift()); 92 fChunkList.insert(i, chunk); 93 } 94 if ((offset+length) < (chunkOffset+chunkLength)) { 95 // Orphan after; resize the original chunk 96 i->set_location(offset+length); 97 i->set_length(((chunkOffset+chunkLength)-(offset+length))<<BlockSize()); 98 } else { 99 // No orphan after; remove the original chunk 100 fChunkList.erase(i); 101 } 102 return B_OK; 103 } 104 } 105 // No matching chunk found, we're SOL. 106 error = B_ERROR; 107 } 108 } 109 return error; 110} 111 112/*! \brief Allocates the next available block. 113 114 \param block Output parameter into which the number of the 115 allocated block is stored. 116 \param minimumBlock The minimum acceptable block number (used 117 by the physical partition allocator). 118 119 \return 120 - B_OK: Success. 121 - error code: Failure, no blocks available. 122*/ 123status_t 124Allocator::GetNextBlock(uint32 &block, uint32 minimumBlock) 125{ 126 status_t error = InitCheck(); 127 if (!error) { 128 Udf::extent_address extent; 129 error = GetNextExtent(BlockSize(), true, extent, minimumBlock); 130 if (!error) 131 block = extent.location(); 132 } 133 return error; 134} 135 136/*! \brief Allocates the next available extent of given length. 137 138 \param length The desired length (in bytes) of the extent. 139 \param contiguous If false, signals that an extent of shorter length will 140 be accepted. This allows for small chunks of 141 unallocated space to be consumed, provided a 142 contiguous chunk is not needed. 143 \param extent Output parameter into which the extent as allocated 144 is stored. Note that the length field of the extent 145 may be shorter than the length parameter passed 146 to this function is \a contiguous is false. 147 \param minimumStartingBlock The minimum acceptable starting block 148 for the extent (used by the physical 149 partition allocator). 150 151 \return 152 - B_OK: Success. 153 - error code: Failure. 154*/ 155status_t 156Allocator::GetNextExtent(uint32 _length, bool contiguous, 157 Udf::extent_address &extent, 158 uint32 minimumStartingBlock) 159{ 160 DEBUG_INIT_ETC("Allocator", ("length: %lld, contiguous: %d", _length, contiguous)); 161 uint32 length = BlocksFor(_length); 162 bool isPartial = false; 163 status_t error = InitCheck(); 164 PRINT(("allocation length: %lu\n", Length())); 165 if (!error) { 166 for (list<Udf::extent_address>::iterator i = fChunkList.begin(); 167 i != fChunkList.end(); 168 i++) 169 { 170 uint32 chunkOffset = i->location(); 171 uint32 chunkLength = BlocksFor(i->length()); 172 if (chunkOffset < minimumStartingBlock) 173 { 174 if (minimumStartingBlock < chunkOffset+chunkLength) { 175 // Start of chunk is below min starting block. See if 176 // any part of the chunk would make for an acceptable 177 // allocation 178 uint32 difference = minimumStartingBlock - chunkOffset; 179 uint32 newOffset = minimumStartingBlock; 180 uint32 newLength = chunkLength-difference; 181 if (length <= newLength) { 182 // new chunk is still long enough 183 Udf::extent_address newExtent(newOffset, _length); 184 if (GetExtent(newExtent) == B_OK) { 185 extent = newExtent; 186 return B_OK; 187 } 188 } else if (!contiguous) { 189 // new chunk is too short, but we're allowed to 190 // allocate a shorter extent, so we'll do it. 191 Udf::extent_address newExtent(newOffset, newLength<<BlockShift()); 192 if (GetExtent(newExtent) == B_OK) { 193 extent = newExtent; 194 return B_OK; 195 } 196 } 197 } 198 } else if (length <= chunkLength) { 199 // Chunk is larger than necessary. Allocate first 200 // length blocks, and resize the chunk appropriately. 201 extent.set_location(chunkOffset); 202 extent.set_length(_length); 203 if (length != chunkLength) { 204 i->set_location(chunkOffset+length); 205 i->set_length((chunkLength-length)<<BlockShift()); 206 } else { 207 fChunkList.erase(i); 208 } 209 return B_OK; 210 } else if (!contiguous) { 211 extent.set_location(chunkOffset); 212 extent.set_length(chunkLength<<BlockShift()); 213 fChunkList.erase(i); 214 return B_OK; 215 } 216 } 217 // No sufficient chunk found, so try to allocate from the tail 218 PRINT(("ULONG_MAX: %lu\n", ULONG_MAX)); 219 uint32 maxLength = ULONG_MAX-Length(); 220 PRINT(("maxLength: %lu\n", maxLength)); 221 error = maxLength > 0 ? B_OK : B_DEVICE_FULL; 222 if (!error) { 223 if (minimumStartingBlock > Tail()) 224 maxLength -= minimumStartingBlock - Tail(); 225 uint32 tail = minimumStartingBlock > Tail() ? minimumStartingBlock : Tail(); 226 if (length > maxLength) { 227 if (contiguous) 228 error = B_DEVICE_FULL; 229 else { 230 isPartial = true; 231 length = maxLength; 232 } 233 } 234 if (!error) { 235 Udf::extent_address newExtent(tail, isPartial ? length<<BlockShift() : _length); 236 if (GetExtent(newExtent) == B_OK) { 237 extent = newExtent; 238 return B_OK; 239 } 240 } 241 } 242 } 243 return error; 244} 245 246/*! \brief Returns the number of blocks needed to accomodate the 247 given number of bytes. 248*/ 249uint32 250Allocator::BlocksFor(off_t bytes) 251{ 252 if (BlockSize() == 0) { 253 DEBUG_INIT_ETC("Allocator", ("bytes: %ld\n", bytes)); 254 PRINT(("WARNING: Allocator::BlockSize() == 0!\n")); 255 return 0; 256 } else { 257 off_t blocks = bytes >> BlockShift(); 258 if (bytes % BlockSize() != 0) 259 blocks++; 260 uint64 mask = 0xffffffff; 261 mask <<= 32; 262 if (blocks & mask) { 263 // ToDo: Convert this to actually signal an error 264 DEBUG_INIT_ETC("Allocator", ("bytes: %ld\n", bytes)); 265 PRINT(("WARNING: bytes argument too large for corresponding number " 266 "of blocks to be specified with a uint32! (bytes: %Ld, blocks: %Ld, " 267 "maxblocks: %ld).\n", bytes, blocks, ULONG_MAX)); 268 blocks = 0; 269 } 270 return blocks; 271 } 272} 273