Core/Util/BlockAllocator.cpp

   1 // Copyright (c) 2012- PPSSPP Project.
   2
   3 // This program is free software: you can redistribute it and/or modify
   4 // it under the terms of the GNU General Public License as published by
   5 // the Free Software Foundation, version 2.0 or later versions.
   6
   7 // This program is distributed in the hope that it will be useful,
   8 // but WITHOUT ANY WARRANTY; without even the implied warranty of
   9 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10 // GNU General Public License 2.0 for more details.
  11
  12 // A copy of the GPL 2.0 should have been included with the program.
  13 // If not, see http://www.gnu.org/licenses/
  14
  15 // Official git repository and contact information can be found at
  16 // https://github.com/hrydgard/ppsspp and http://www.ppsspp.org/.
  17
  18 #include <cstring>
  19
  20 #include "Common/Log.h"
  21 #include "Common/ChunkFile.h"
  22 #include "Core/Util/BlockAllocator.h"
  23 #include "Core/Reporting.h"
  24
  25 // Slow freaking thing but works (eventually) :)
  26
  27 BlockAllocator::BlockAllocator(int grain) : bottom_(NULL), top_(NULL), grain_(grain)
  28 {
  29 }
  30
  31 BlockAllocator::~BlockAllocator()
  32 {
  33         Shutdown();
  34 }
  35
  36 void BlockAllocator::Init(u32 rangeStart, u32 rangeSize)
  37 {
  38         Shutdown();
  39         rangeStart_ = rangeStart;
  40         rangeSize_ = rangeSize;
  41         //Initial block, covering everything
  42         top_ = new Block(rangeStart_, rangeSize_, false, NULL, NULL);
  43         bottom_ = top_;
  44 }
  45
  46 void BlockAllocator::Shutdown()
  47 {
  48         while (bottom_ != NULL)
  49         {
  50                 Block *next = bottom_->next;
  51                 delete bottom_;
  52                 bottom_ = next;
  53         }
  54         top_ = NULL;
  55 }
  56
  57 u32 BlockAllocator::AllocAligned(u32 &size, u32 sizeGrain, u32 grain, bool fromTop, const char *tag)
  58 {
  59         // Sanity check
  60         if (size == 0 || size > rangeSize_) {
  61                 ERROR_LOG(HLE, "Clearly bogus size: %08x - failing allocation", size);
  62                 return -1;
  63         }
  64
  65         // It could be off step, but the grain should generally be a power of 2.
  66         if (grain < grain_)
  67                 grain = grain_;
  68         if (sizeGrain < grain_)
  69                 sizeGrain = grain_;
  70
  71         // upalign size to grain
  72         size = (size + sizeGrain - 1) & ~(sizeGrain - 1);
  73
  74         if (!fromTop)
  75         {
  76                 //Allocate from bottom of mem
  77                 for (Block *bp = bottom_; bp != NULL; bp = bp->next)
  78                 {
  79                         Block &b = *bp;
  80                         u32 offset = b.start % grain;
  81                         if (offset != 0)
  82                                 offset = grain - offset;
  83                         u32 needed = offset + size;
  84                         if (b.taken == false && b.size >= needed)
  85                         {
  86                                 if (b.size == needed)
  87                                 {
  88                                         b.taken = true;
  89                                         b.SetTag(tag);
  90                                         return b.start + offset;
  91                                 }
  92                                 else
  93                                 {
  94                                         InsertFreeAfter(&b, b.start + needed, b.size - needed);
  95                                         b.taken = true;
  96                                         b.size = needed;
  97                                         b.SetTag(tag);
  98                                         return b.start + offset;
  99                                 }
 100                         }
 101                 }
 102         }
 103         else
 104         {
 105                 // Allocate from top of mem.
 106                 for (Block *bp = top_; bp != NULL; bp = bp->prev)
 107                 {
 108                         Block &b = *bp;
 109                         u32 offset = (b.start + b.size - size) % grain;
 110                         u32 needed = offset + size;
 111                         if (b.taken == false && b.size >= needed)
 112                         {
 113                                 if (b.size == needed)
 114                                 {
 115                                         b.taken = true;
 116                                         b.SetTag(tag);
 117                                         return b.start;
 118                                 }
 119                                 else
 120                                 {
 121                                         InsertFreeBefore(&b, b.start, b.size - needed);
 122                                         b.taken = true;
 123                                         b.start += b.size - needed;
 124                                         b.size = needed;
 125                                         b.SetTag(tag);
 126                                         return b.start;
 127                                 }
 128                         }
 129                 }
 130         }
 131
 132         //Out of memory :(
 133         ListBlocks();
 134         ERROR_LOG(HLE, "Block Allocator (%08x-%08x) failed to allocate %i (%08x) bytes of contiguous memory", rangeStart_, rangeStart_ + rangeSize_, size, size);
 135         return -1;
 136 }
 137
 138 u32 BlockAllocator::Alloc(u32 &size, bool fromTop, const char *tag)
 139 {
 140         // We want to make sure it's aligned in case AllocAt() was used.
 141         return AllocAligned(size, grain_, grain_, fromTop, tag);
 142 }
 143
 144 u32 BlockAllocator::AllocAt(u32 position, u32 size, const char *tag)
 145 {
 146         CheckBlocks();
 147         if (size > rangeSize_) {
 148                 ERROR_LOG(HLE, "Clearly bogus size: %08x - failing allocation", size);
 149                 return -1;
 150         }
 151
 152         // Downalign the position so we're allocating full blocks.
 153         u32 alignedPosition = position;
 154         u32 alignedSize = size;
 155         if (position & (grain_ - 1)) {
 156                 DEBUG_LOG(HLE, "Position %08x does not align to grain.", position);
 157                 alignedPosition &= ~(grain_ - 1);
 158
 159                 // Since the position was decreased, size must increase.
 160                 alignedSize += alignedPosition - position;
 161         }
 162
 163         // Upalign size to grain.
 164         alignedSize = (alignedSize + grain_ - 1) & ~(grain_ - 1);
 165         // Tell the caller the allocated size from their requested starting position.
 166         size = alignedSize - (alignedPosition - position);
 167
 168         Block *bp = GetBlockFromAddress(alignedPosition);
 169         if (bp != NULL)
 170         {
 171                 Block &b = *bp;
 172                 if (b.taken)
 173                 {
 174                         ERROR_LOG(HLE, "Block allocator AllocAt failed, block taken! %08x, %i", position, size);
 175                         return -1;
 176                 }
 177                 else
 178                 {
 179                         // Make sure the block is big enough to split.
 180                         if (b.start + b.size < alignedPosition + alignedSize)
 181                         {
 182                                 ERROR_LOG(HLE, "Block allocator AllocAt failed, not enough contiguous space %08x, %i", position, size);
 183                                 return -1;
 184                         }
 185                         //good to go
 186                         else if (b.start == alignedPosition)
 187                         {
 188                                 InsertFreeAfter(&b, b.start + alignedSize, b.size - alignedSize);
 189                                 b.taken = true;
 190                                 b.size = alignedSize;
 191                                 b.SetTag(tag);
 192                                 CheckBlocks();
 193                                 return position;
 194                         }
 195                         else
 196                         {
 197                                 int size1 = alignedPosition - b.start;
 198                                 InsertFreeBefore(&b, b.start, size1);
 199                                 if (b.start + b.size > alignedPosition + alignedSize)
 200                                         InsertFreeAfter(&b, alignedPosition + alignedSize, b.size - (alignedSize + size1));
 201                                 b.taken = true;
 202                                 b.start = alignedPosition;
 203                                 b.size = alignedSize;
 204                                 b.SetTag(tag);
 205
 206                                 return position;
 207                         }
 208                 }
 209         }
 210         else
 211         {
 212                 ERROR_LOG(HLE, "Block allocator AllocAt failed :( %08x, %i", position, size);
 213         }
 214
 215
 216         //Out of memory :(
 217         ListBlocks();
 218         ERROR_LOG(HLE, "Block Allocator (%08x-%08x) failed to allocate %i (%08x) bytes of contiguous memory", rangeStart_, rangeStart_ + rangeSize_, alignedSize, alignedSize);
 219         return -1;
 220 }
 221
 222 void BlockAllocator::MergeFreeBlocks(Block *fromBlock)
 223 {
 224         DEBUG_LOG(HLE, "Merging Blocks");
 225
 226         Block *prev = fromBlock->prev;
 227         while (prev != NULL && prev->taken == false)
 228         {
 229                 DEBUG_LOG(HLE, "Block Alloc found adjacent free blocks - merging");
 230                 prev->size += fromBlock->size;
 231                 if (fromBlock->next == NULL)
 232                         top_ = prev;
 233                 else
 234                         fromBlock->next->prev = prev;
 235                 prev->next = fromBlock->next;
 236                 delete fromBlock;
 237                 fromBlock = prev;
 238                 prev = fromBlock->prev;
 239         }
 240
 241         if (prev == NULL)
 242                 bottom_ = fromBlock;
 243         else
 244                 prev->next = fromBlock;
 245
 246         Block *next = fromBlock->next;
 247         while (next != NULL && next->taken == false)
 248         {
 249                 DEBUG_LOG(HLE, "Block Alloc found adjacent free blocks - merging");
 250                 fromBlock->size += next->size;
 251                 fromBlock->next = next->next;
 252                 delete next;
 253                 next = fromBlock->next;
 254         }
 255
 256         if (next == NULL)
 257                 top_ = fromBlock;
 258         else
 259                 next->prev = fromBlock;
 260 }
 261
 262 bool BlockAllocator::Free(u32 position)
 263 {
 264         Block *b = GetBlockFromAddress(position);
 265         if (b && b->taken)
 266         {
 267                 b->taken = false;
 268                 MergeFreeBlocks(b);
 269                 return true;
 270         }
 271         else
 272         {
 273                 ERROR_LOG(HLE, "BlockAllocator : invalid free %08x", position);
 274                 return false;
 275         }
 276 }
 277
 278 bool BlockAllocator::FreeExact(u32 position)
 279 {
 280         Block *b = GetBlockFromAddress(position);
 281         if (b && b->taken && b->start == position)
 282         {
 283                 b->taken = false;
 284                 MergeFreeBlocks(b);
 285                 return true;
 286         }
 287         else
 288         {
 289                 ERROR_LOG(HLE, "BlockAllocator : invalid free %08x", position);
 290                 return false;
 291         }
 292 }
 293
 294 BlockAllocator::Block *BlockAllocator::InsertFreeBefore(Block *b, u32 start, u32 size)
 295 {
 296         Block *inserted = new Block(start, size, false, b->prev, b);
 297         b->prev = inserted;
 298         if (inserted->prev == NULL)
 299                 bottom_ = inserted;
 300         else
 301                 inserted->prev->next = inserted;
 302
 303         return inserted;
 304 }
 305
 306 BlockAllocator::Block *BlockAllocator::InsertFreeAfter(Block *b, u32 start, u32 size)
 307 {
 308         Block *inserted = new Block(start, size, false, b, b->next);
 309         b->next = inserted;
 310         if (inserted->next == NULL)
 311                 top_ = inserted;
 312         else
 313                 inserted->next->prev = inserted;
 314
 315         return inserted;
 316 }
 317
 318 void BlockAllocator::CheckBlocks() const
 319 {
 320         for (const Block *bp = bottom_; bp != NULL; bp = bp->next)
 321         {
 322                 const Block &b = *bp;
 323                 if (b.start > 0xc0000000) {  // probably free'd debug values
 324                         ERROR_LOG_REPORT(HLE, "Bogus block in allocator");
 325                 }
 326                 // Outside the valid range, probably logic bug in allocation.
 327                 if (b.start + b.size > rangeStart_ + rangeSize_ || b.start < rangeStart_) {
 328                         ERROR_LOG_REPORT(HLE, "Bogus block in allocator");
 329                 }
 330         }
 331 }
 332
 333 const char *BlockAllocator::GetBlockTag(u32 addr) const {
 334         const Block *b = GetBlockFromAddress(addr);
 335         return b->tag;
 336 }
 337
 338 inline BlockAllocator::Block *BlockAllocator::GetBlockFromAddress(u32 addr)
 339 {
 340         for (Block *bp = bottom_; bp != NULL; bp = bp->next)
 341         {
 342                 Block &b = *bp;
 343                 if (b.start <= addr && b.start + b.size > addr)
 344                 {
 345                         // Got one!
 346                         return bp;
 347                 }
 348         }
 349         return NULL;
 350 }
 351
 352 const BlockAllocator::Block *BlockAllocator::GetBlockFromAddress(u32 addr) const
 353 {
 354         for (const Block *bp = bottom_; bp != NULL; bp = bp->next)
 355         {
 356                 const Block &b = *bp;
 357                 if (b.start <= addr && b.start + b.size > addr)
 358                 {
 359                         // Got one!
 360                         return bp;
 361                 }
 362         }
 363         return NULL;
 364 }
 365
 366 u32 BlockAllocator::GetBlockStartFromAddress(u32 addr) const
 367 {
 368         const Block *b = GetBlockFromAddress(addr);
 369         if (b)
 370                 return b->start;
 371         else
 372                 return -1;
 373 }
 374
 375 u32 BlockAllocator::GetBlockSizeFromAddress(u32 addr) const
 376 {
 377         const Block *b = GetBlockFromAddress(addr);
 378         if (b)
 379                 return b->size;
 380         else
 381                 return -1;
 382 }
 383
 384 void BlockAllocator::ListBlocks() const
 385 {
 386         INFO_LOG(HLE,"-----------");
 387         for (const Block *bp = bottom_; bp != NULL; bp = bp->next)
 388         {
 389                 const Block &b = *bp;
 390                 INFO_LOG(HLE, "Block: %08x - %08x size %08x taken=%i tag=%s", b.start, b.start+b.size, b.size, b.taken ? 1:0, b.tag);
 391         }
 392         INFO_LOG(HLE,"-----------");
 393 }
 394
 395 u32 BlockAllocator::GetLargestFreeBlockSize() const
 396 {
 397         u32 maxFreeBlock = 0;
 398         for (const Block *bp = bottom_; bp != NULL; bp = bp->next)
 399         {
 400                 const Block &b = *bp;
 401                 if (!b.taken)
 402                 {
 403                         if (b.size > maxFreeBlock)
 404                                 maxFreeBlock = b.size;
 405                 }
 406         }
 407         if (maxFreeBlock & (grain_ - 1))
 408                 WARN_LOG_REPORT(HLE, "GetLargestFreeBlockSize: free size %08x does not align to grain %08x.", maxFreeBlock, grain_);
 409         return maxFreeBlock;
 410 }
 411
 412 u32 BlockAllocator::GetTotalFreeBytes() const
 413 {
 414         u32 sum = 0;
 415         for (const Block *bp = bottom_; bp != NULL; bp = bp->next)
 416         {
 417                 const Block &b = *bp;
 418                 if (!b.taken)
 419                 {
 420                         sum += b.size;
 421                 }
 422         }
 423         if (sum & (grain_ - 1))
 424                 WARN_LOG_REPORT(HLE, "GetTotalFreeBytes: free size %08x does not align to grain %08x.", sum, grain_);
 425         return sum;
 426 }
 427
 428 void BlockAllocator::DoState(PointerWrap &p)
 429 {
 430         auto s = p.Section("BlockAllocator", 1);
 431         if (!s)
 432                 return;
 433
 434         int count = 0;
 435
 436         if (p.mode == p.MODE_READ)
 437         {
 438                 Shutdown();
 439                 p.Do(count);
 440
 441                 bottom_ = new Block(0, 0, false, NULL, NULL);
 442                 bottom_->DoState(p);
 443                 --count;
 444
 445                 top_ = bottom_;
 446                 for (int i = 0; i < count; ++i)
 447                 {
 448                         top_->next = new Block(0, 0, false, top_, NULL);
 449                         top_->next->DoState(p);
 450                         top_ = top_->next;
 451                 }
 452         }
 453         else
 454         {
 455                 for (const Block *bp = bottom_; bp != NULL; bp = bp->next)
 456                         ++count;
 457                 p.Do(count);
 458
 459                 bottom_->DoState(p);
 460                 --count;
 461
 462                 Block *last = bottom_;
 463                 for (int i = 0; i < count; ++i)
 464                 {
 465                         last->next->DoState(p);
 466                         last = last->next;
 467                 }
 468         }
 469
 470         p.Do(rangeStart_);
 471         p.Do(rangeSize_);
 472         p.Do(grain_);
 473 }
 474
 475 BlockAllocator::Block::Block(u32 _start, u32 _size, bool _taken, Block *_prev, Block *_next)
 476 : start(_start), size(_size), taken(_taken), prev(_prev), next(_next)
 477 {
 478         strcpy(tag, "(untitled)");
 479 }
 480
 481 void BlockAllocator::Block::SetTag(const char *_tag)
 482 {
 483         if (_tag)
 484                 strncpy(tag, _tag, 32);
 485         else
 486                 strncpy(tag, "---", 32);
 487         tag[31] = 0;
 488 }
 489
 490 void BlockAllocator::Block::DoState(PointerWrap &p)
 491 {
 492         auto s = p.Section("Block", 1);
 493         if (!s)
 494                 return;
 495
 496         p.Do(start);
 497         p.Do(size);
 498         p.Do(taken);
 499         p.DoArray(tag, sizeof(tag));
 500 }