src/bin/makeudfimage/Allocator.cpp

   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 */
  21 Allocator::Allocator(uint32 blockSize)
  22         : fLength(0)
  23         , fBlockSize(blockSize)
  24         , fBlockShift(0)
  25         , fInitStatus(B_NO_INIT)
  26 {
  27         status_t error = get_block_shift(BlockSize(), fBlockShift);
  28         if (!error)
  29                 fInitStatus = B_OK;
  30 }
  31
  32 status_t
  33 Allocator::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 */
  44 status_t
  45 Allocator::GetBlock(uint32 block)
  46 {
  47         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 */
  58 status_t
  59 Allocator::GetExtent(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                                 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<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                                                 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 */
 123 status_t
 124 Allocator::GetNextBlock(uint32 &block, uint32 minimumBlock)
 125 {
 126         status_t error = InitCheck();
 127         if (!error) {
 128                 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 */
 155 status_t
 156 Allocator::GetNextExtent(uint32 _length, bool contiguous,
 157                          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<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                                                 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                                                 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                                 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 */
 249 uint32
 250 Allocator::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 }