src/kits/media/RealtimeAlloc.cpp

   1 /*
   2  * Copyright 2009, Axel Dörfler, axeld@pinc-software.de.
   3  * Distributed under the terms of the MIT License.
   4  */
   5
   6
   7 /*!     A simple allocator that works directly on an area, based on the boot
   8         loader's heap. See there for more information about its inner workings.
   9 */
  10
  11
  12 #include <RealtimeAlloc.h>
  13
  14 #include <pthread.h>
  15 #include <stdlib.h>
  16 #include <stdio.h>
  17 #include <string.h>
  18
  19 #include <OS.h>
  20
  21 #include <locks.h>
  22 #include <kernel/util/DoublyLinkedList.h>
  23
  24
  25 //#define TRACE_RTM
  26 #ifdef TRACE_RTM
  27 #       define TRACE(x...) printf(x);
  28 #else
  29 #       define TRACE(x...) ;
  30 #endif
  31
  32
  33 class FreeChunk {
  34 public:
  35                         void                            SetTo(size_t size, FreeChunk* next);
  36
  37                         uint32                          Size() const;
  38                         uint32                          CompleteSize() const { return fSize; }
  39
  40                         FreeChunk*                      Next() const { return fNext; }
  41                         void                            SetNext(FreeChunk* next) { fNext = next; }
  42
  43                         FreeChunk*                      Split(uint32 splitSize);
  44                         bool                            IsTouching(FreeChunk* link);
  45                         FreeChunk*                      Join(FreeChunk* link);
  46                         void                            Remove(rtm_pool* pool,
  47                                                                         FreeChunk* previous = NULL);
  48                         void                            Enqueue(rtm_pool* pool);
  49
  50                         void*                           AllocatedAddress() const;
  51         static  FreeChunk*                      SetToAllocated(void* allocated);
  52         static  addr_t                          NextOffset() { return sizeof(size_t); }
  53
  54 private:
  55                         size_t                          fSize;
  56                         FreeChunk*                      fNext;
  57 };
  58
  59
  60 struct rtm_pool : DoublyLinkedListLinkImpl<rtm_pool> {
  61         area_id         area;
  62         void*           heap_base;
  63         size_t          max_size;
  64         size_t          available;
  65         FreeChunk       free_anchor;
  66         mutex           lock;
  67
  68         bool Contains(void* buffer) const;
  69         void Free(void* buffer);
  70 };
  71
  72 typedef DoublyLinkedList<rtm_pool> PoolList;
  73
  74
  75 const static uint32 kAlignment = 256;
  76         // all memory chunks will be a multiple of this
  77
  78 static mutex sPoolsLock = MUTEX_INITIALIZER("rtm pools");
  79 static PoolList sPools;
  80
  81
  82 void
  83 FreeChunk::SetTo(size_t size, FreeChunk* next)
  84 {
  85         fSize = size;
  86         fNext = next;
  87 }
  88
  89
  90 /*!     Returns the amount of bytes that can be allocated
  91         in this chunk.
  92 */
  93 uint32
  94 FreeChunk::Size() const
  95 {
  96         return fSize - FreeChunk::NextOffset();
  97 }
  98
  99
 100 /*!     Splits the upper half at the requested location
 101         and returns it.
 102 */
 103 FreeChunk*
 104 FreeChunk::Split(uint32 splitSize)
 105 {
 106         splitSize = (splitSize - 1 + kAlignment) & ~(kAlignment - 1);
 107
 108         FreeChunk* chunk
 109                 = (FreeChunk*)((uint8*)this + FreeChunk::NextOffset() + splitSize);
 110         chunk->fSize = fSize - splitSize - FreeChunk::NextOffset();
 111         chunk->fNext = fNext;
 112
 113         fSize = splitSize + FreeChunk::NextOffset();
 114
 115         return chunk;
 116 }
 117
 118
 119 /*!     Checks if the specified chunk touches this chunk, so
 120         that they could be joined.
 121 */
 122 bool
 123 FreeChunk::IsTouching(FreeChunk* chunk)
 124 {
 125         return chunk
 126                 && (((uint8*)this + fSize == (uint8*)chunk)
 127                         || (uint8*)chunk + chunk->fSize == (uint8*)this);
 128 }
 129
 130
 131 /*!     Joins the chunk to this chunk and returns the pointer
 132         to the new chunk - which will either be one of the
 133         two chunks.
 134         Note, the chunks must be joinable, or else this method
 135         doesn't work correctly. Use FreeChunk::IsTouching()
 136         to check if this method can be applied.
 137 */
 138 FreeChunk*
 139 FreeChunk::Join(FreeChunk* chunk)
 140 {
 141         if (chunk < this) {
 142                 chunk->fSize += fSize;
 143                 chunk->fNext = fNext;
 144
 145                 return chunk;
 146         }
 147
 148         fSize += chunk->fSize;
 149         fNext = chunk->fNext;
 150
 151         return this;
 152 }
 153
 154
 155 void
 156 FreeChunk::Remove(rtm_pool* pool, FreeChunk* previous)
 157 {
 158         if (previous == NULL) {
 159                 // find the previous chunk in the list
 160                 FreeChunk* chunk = pool->free_anchor.fNext;
 161
 162                 while (chunk != NULL && chunk != this) {
 163                         previous = chunk;
 164                         chunk = chunk->fNext;
 165                 }
 166
 167                 if (chunk == NULL)
 168                         return;
 169         }
 170
 171         previous->fNext = fNext;
 172         fNext = NULL;
 173 }
 174
 175
 176 void
 177 FreeChunk::Enqueue(rtm_pool* pool)
 178 {
 179         FreeChunk* chunk = pool->free_anchor.fNext;
 180         FreeChunk* last = &pool->free_anchor;
 181         while (chunk && chunk->Size() < fSize) {
 182                 last = chunk;
 183                 chunk = chunk->fNext;
 184         }
 185
 186         fNext = chunk;
 187         last->fNext = this;
 188 }
 189
 190
 191 void*
 192 FreeChunk::AllocatedAddress() const
 193 {
 194         return (void*)&fNext;
 195 }
 196
 197
 198 FreeChunk*
 199 FreeChunk::SetToAllocated(void* allocated)
 200 {
 201         return (FreeChunk*)((addr_t)allocated - FreeChunk::NextOffset());
 202 }
 203
 204
 205 // #pragma mark - rtm_pool
 206
 207
 208 bool
 209 rtm_pool::Contains(void* buffer) const
 210 {
 211         return (addr_t)heap_base <= (addr_t)buffer
 212                 && (addr_t)heap_base - 1 + max_size >= (addr_t)buffer;
 213 }
 214
 215
 216 void
 217 rtm_pool::Free(void* allocated)
 218 {
 219         FreeChunk* freedChunk = FreeChunk::SetToAllocated(allocated);
 220         available += freedChunk->CompleteSize();
 221
 222         // try to join the new free chunk with an existing one
 223         // it may be joined with up to two chunks
 224
 225         FreeChunk* chunk = free_anchor.Next();
 226         FreeChunk* last = &free_anchor;
 227         int32 joinCount = 0;
 228
 229         while (chunk) {
 230                 if (chunk->IsTouching(freedChunk)) {
 231                         // almost "insert" it into the list before joining
 232                         // because the next pointer is inherited by the chunk
 233                         freedChunk->SetNext(chunk->Next());
 234                         freedChunk = chunk->Join(freedChunk);
 235
 236                         // remove the joined chunk from the list
 237                         last->SetNext(freedChunk->Next());
 238                         chunk = last;
 239
 240                         if (++joinCount == 2)
 241                                 break;
 242                 }
 243
 244                 last = chunk;
 245                 chunk = chunk->Next();
 246         }
 247
 248         // enqueue the link at the right position; the
 249         // free link queue is ordered by size
 250
 251         freedChunk->Enqueue(this);
 252 }
 253
 254
 255 // #pragma mark -
 256
 257
 258 static rtm_pool*
 259 pool_for(void* buffer)
 260 {
 261         MutexLocker _(&sPoolsLock);
 262
 263         PoolList::Iterator iterator = sPools.GetIterator();
 264         while (rtm_pool* pool = iterator.Next()) {
 265                 if (pool->Contains(buffer))
 266                         return pool;
 267         }
 268
 269         return NULL;
 270 }
 271
 272
 273 // #pragma mark - public API
 274
 275
 276 status_t
 277 rtm_create_pool(rtm_pool** _pool, size_t totalSize, const char* name)
 278 {
 279         rtm_pool* pool = (rtm_pool*)malloc(sizeof(rtm_pool));
 280         if (pool == NULL)
 281                 return B_NO_MEMORY;
 282
 283         if (name != NULL)
 284                 mutex_init_etc(&pool->lock, name, MUTEX_FLAG_CLONE_NAME);
 285         else
 286                 mutex_init(&pool->lock, "realtime pool");
 287
 288         // Allocate enough space for at least one allocation over \a totalSize
 289         pool->max_size = (totalSize + sizeof(FreeChunk) - 1 + B_PAGE_SIZE)
 290                 & ~(B_PAGE_SIZE - 1);
 291
 292         area_id area = create_area(name, &pool->heap_base, B_ANY_ADDRESS,
 293                 pool->max_size, B_LAZY_LOCK, B_READ_AREA | B_WRITE_AREA);
 294         if (area < 0) {
 295                 mutex_destroy(&pool->lock);
 296                 free(pool);
 297                 return area;
 298         }
 299
 300         pool->area = area;
 301         pool->available = pool->max_size - FreeChunk::NextOffset();
 302
 303         // declare the whole heap as one chunk, and add it
 304         // to the free list
 305
 306         FreeChunk* chunk = (FreeChunk*)pool->heap_base;
 307         chunk->SetTo(pool->max_size, NULL);
 308
 309         pool->free_anchor.SetTo(0, chunk);
 310
 311         *_pool = pool;
 312
 313         MutexLocker _(&sPoolsLock);
 314         sPools.Add(pool);
 315         return B_OK;
 316 }
 317
 318
 319 status_t
 320 rtm_delete_pool(rtm_pool* pool)
 321 {
 322         if (pool == NULL)
 323                 return B_BAD_VALUE;
 324
 325         mutex_lock(&pool->lock);
 326
 327         {
 328                 MutexLocker _(&sPoolsLock);
 329                 sPools.Remove(pool);
 330         }
 331
 332         delete_area(pool->area);
 333         mutex_destroy(&pool->lock);
 334         free(pool);
 335
 336         return B_OK;
 337 }
 338
 339
 340 void*
 341 rtm_alloc(rtm_pool* pool, size_t size)
 342 {
 343         if (pool == NULL)
 344                 return malloc(size);
 345
 346         if (pool->heap_base == NULL || size == 0)
 347                 return NULL;
 348
 349         MutexLocker _(&pool->lock);
 350
 351         // align the size requirement to a kAlignment bytes boundary
 352         size = (size - 1 + kAlignment) & ~(size_t)(kAlignment - 1);
 353
 354         if (size > pool->available) {
 355                 TRACE("malloc(): Out of memory!\n");
 356                 return NULL;
 357         }
 358
 359         FreeChunk* chunk = pool->free_anchor.Next();
 360         FreeChunk* last = &pool->free_anchor;
 361         while (chunk && chunk->Size() < size) {
 362                 last = chunk;
 363                 chunk = chunk->Next();
 364         }
 365
 366         if (chunk == NULL) {
 367                 // could not find a free chunk as large as needed
 368                 TRACE("malloc(): Out of memory!\n");
 369                 return NULL;
 370         }
 371
 372         if (chunk->Size() > size + sizeof(FreeChunk) + kAlignment) {
 373                 // if this chunk is bigger than the requested size,
 374                 // we split it to form two chunks (with a minimal
 375                 // size of kAlignment allocatable bytes).
 376
 377                 FreeChunk* freeChunk = chunk->Split(size);
 378                 last->SetNext(freeChunk);
 379
 380                 // re-enqueue the free chunk at the correct position
 381                 freeChunk->Remove(pool, last);
 382                 freeChunk->Enqueue(pool);
 383         } else {
 384                 // remove the chunk from the free list
 385
 386                 last->SetNext(chunk->Next());
 387         }
 388
 389         pool->available -= size + sizeof(size_t);
 390
 391         TRACE("malloc(%lu) -> %p\n", size, chunk->AllocatedAddress());
 392         return chunk->AllocatedAddress();
 393 }
 394
 395
 396 status_t
 397 rtm_free(void* allocated)
 398 {
 399         if (allocated == NULL)
 400                 return B_OK;
 401
 402         TRACE("rtm_free(%p)\n", allocated);
 403
 404         // find pool
 405         rtm_pool* pool = pool_for(allocated);
 406         if (pool == NULL) {
 407                 free(allocated);
 408                 return B_OK;
 409         }
 410
 411         MutexLocker _(&pool->lock);
 412         pool->Free(allocated);
 413         return B_OK;
 414 }
 415
 416
 417 status_t
 418 rtm_realloc(void** _buffer, size_t newSize)
 419 {
 420         if (_buffer == NULL)
 421                 return B_BAD_VALUE;
 422
 423         TRACE("rtm_realloc(%p, %lu)\n", *_buffer, newSize);
 424
 425         void* oldBuffer = *_buffer;
 426
 427         // find pool
 428         rtm_pool* pool = pool_for(oldBuffer);
 429         if (pool == NULL) {
 430                 void* buffer = realloc(oldBuffer, newSize);
 431                 if (buffer != NULL) {
 432                         *_buffer = buffer;
 433                         return B_OK;
 434                 }
 435                 return B_NO_MEMORY;
 436         }
 437
 438         MutexLocker _(&pool->lock);
 439
 440         if (newSize == 0) {
 441                 TRACE("realloc(%p, %lu) -> NULL\n", oldBuffer, newSize);
 442                 pool->Free(oldBuffer);
 443                 *_buffer = NULL;
 444                 return B_OK;
 445         }
 446
 447         size_t copySize = newSize;
 448         if (oldBuffer != NULL) {
 449                 FreeChunk* oldChunk = FreeChunk::SetToAllocated(oldBuffer);
 450
 451                 // Check if the old buffer still fits, and if it makes sense to keep it
 452                 if (oldChunk->Size() >= newSize && newSize > oldChunk->Size() / 3) {
 453                         TRACE("realloc(%p, %lu) old buffer is large enough\n",
 454                                 oldBuffer, newSize);
 455                         return B_OK;
 456                 }
 457
 458                 if (copySize > oldChunk->Size())
 459                         copySize = oldChunk->Size();
 460         }
 461
 462         void* newBuffer = rtm_alloc(pool, newSize);
 463         if (newBuffer == NULL)
 464                 return B_NO_MEMORY;
 465
 466         if (oldBuffer != NULL) {
 467                 memcpy(newBuffer, oldBuffer, copySize);
 468                 pool->Free(oldBuffer);
 469         }
 470
 471         TRACE("realloc(%p, %lu) -> %p\n", oldBuffer, newSize, newBuffer);
 472         *_buffer = newBuffer;
 473         return B_OK;
 474 }
 475
 476
 477 status_t
 478 rtm_size_for(void* buffer)
 479 {
 480         if (buffer == NULL)
 481                 return 0;
 482
 483         FreeChunk* chunk = FreeChunk::SetToAllocated(buffer);
 484         // TODO: we currently always return the actual chunk size, not the allocated
 485         // one
 486         return chunk->Size();
 487 }
 488
 489
 490 status_t
 491 rtm_phys_size_for(void* buffer)
 492 {
 493         if (buffer == NULL)
 494                 return 0;
 495
 496         FreeChunk* chunk = FreeChunk::SetToAllocated(buffer);
 497         return chunk->Size();
 498 }
 499
 500
 501 size_t
 502 rtm_available(rtm_pool* pool)
 503 {
 504         if (pool == NULL) {
 505                 // whatever - might want to use system_info instead
 506                 return 1024 * 1024;
 507         }
 508
 509         return pool->available;
 510 }
 511
 512
 513 rtm_pool*
 514 rtm_default_pool()
 515 {
 516         // We always return NULL - the default pool will just use malloc()/free()
 517         return NULL;
 518 }
 519
 520
 521 #if 0
 522 extern "C" {
 523
 524 // undocumented symbols that BeOS exports
 525 status_t rtm_create_pool_etc(rtm_pool ** out_pool, size_t total_size, const char * name, int32 param4, int32 param5, ...);
 526 void rtm_get_pool(rtm_pool *pool,void *data,int32 param3,int32 param4, ...);
 527
 528 }
 529 #endif