src/add-ons/kernel/drivers/graphics/common/memory_manager.c

   1 /*
   2  * Copyright 2006, Haiku Inc.
   3  * Copyright 2002, Thomas Kurschel.
   4  *
   5  * Distributed under the terms of the MIT license.
   6  */
   7
   8 /**     Memory manager used for graphics mem
   9  *
  10  *      It has the following features
  11  *      - doesn't access memory to be managed
  12  *      - memory block's owner is identified by tag,
  13  *        tag is verified during free, and all memory
  14  *        belonging to one tag can be freed at once
  15  *      - multi-threading save
  16  */
  17
  18 #include "memory_manager.h"
  19
  20 #include <KernelExport.h>
  21 #include <stdlib.h>
  22
  23
  24 //#define TRACE_MEMORY_MANAGER
  25 #ifdef TRACE_MEMORY_MANAGER
  26 #       define TRACE(x) dprintf x
  27 #else
  28 #       define TRACE(x) ;
  29 #endif
  30
  31
  32 // allocated memory block
  33 typedef struct mem_block {
  34         struct mem_block *prev, *next;
  35         uint32 base;
  36         uint32 size;
  37         void *tag;
  38         bool allocated;
  39 } mem_block;
  40
  41 // memory heap
  42 struct mem_info {
  43         mem_block *first;
  44         area_id heap_area;
  45         uint32 block_size;
  46         sem_id lock;
  47         mem_block *heap;
  48         mem_block *unused;
  49         uint32 heap_entries;
  50 };
  51
  52
  53 /** merge "block" with successor */
  54
  55 static void
  56 merge(mem_info *mem, mem_block *block)
  57 {
  58         mem_block *next = block->next;
  59
  60         block->size += next->size;
  61
  62         if (next->next)
  63                 next->next->prev = block;
  64
  65         block->next = next->next;
  66         next->next = mem->unused;
  67         mem->unused = next;
  68 }
  69
  70
  71 /** free memory block including merge */
  72
  73 static mem_block *
  74 freeblock(mem_info *mem, mem_block *block)
  75 {
  76         mem_block *prev, *next;
  77
  78         block->allocated = false;
  79         prev = block->prev;
  80
  81         if (prev && !prev->allocated) {
  82                 block = prev;
  83                 merge(mem, prev);
  84         }
  85
  86         next = block->next;
  87
  88         if (next && !next->allocated)
  89                 merge(mem, block);
  90
  91         return block;
  92 }
  93
  94
  95 //      #pragma mark -
  96
  97
  98 /** Init memory manager.
  99  *
 100  *      \param start start of address space
 101  *      \param length length of address space
 102  *      \param blockSize - granularity
 103  *      \param heapEntries - maximum number of blocks
 104  */
 105
 106 mem_info *
 107 mem_init(const char* name, uint32 start, uint32 length,
 108         uint32 blockSize, uint32 heapEntries)
 109 {
 110         mem_block *first;
 111         mem_info *mem;
 112         uint i;
 113         uint32 size;
 114
 115         TRACE(("mem_init(name=%s, start=%lx, length=%lx, blockSize=%lx, heapEntries=%ld)\n",
 116                 name, start, length, blockSize, heapEntries));
 117
 118         mem = malloc(sizeof(*mem));
 119         if (mem == NULL)
 120                 goto err1;
 121
 122         mem->block_size = blockSize;
 123         mem->heap_entries = heapEntries;
 124         mem->lock = create_sem(1, name);
 125         if (mem->lock < 0)
 126                 goto err2;
 127
 128         // align size to B_PAGE_SIZE
 129         size = heapEntries * sizeof(mem_block);
 130         size = (size + B_PAGE_SIZE - 1) & ~(B_PAGE_SIZE - 1);
 131
 132         mem->heap_area = create_area(name, (void **)&mem->heap,
 133                 B_ANY_ADDRESS, size, B_FULL_LOCK, B_READ_AREA | B_WRITE_AREA);
 134
 135         if (mem->heap_area < 0 || mem->heap == NULL)
 136                 goto err3;
 137
 138         for (i = 1; i < heapEntries; ++i) {
 139                 mem->heap[i - 1].next = &mem->heap[i];
 140         }
 141
 142         mem->heap[heapEntries - 1].next = NULL;
 143         mem->unused = &mem->heap[1];
 144
 145         first = &mem->heap[0];
 146         mem->first = first;
 147
 148         first->base = start;
 149         first->size = length;
 150         first->prev = first->next = NULL;
 151         first->allocated = false;
 152
 153         return mem;
 154
 155 err3:
 156         delete_sem(mem->lock);
 157 err2:
 158         free(mem);
 159 err1:
 160         return NULL;
 161 }
 162
 163
 164 /** destroy heap */
 165
 166 void
 167 mem_destroy(mem_info *mem)
 168 {
 169         TRACE(("mem_destroy(mem %p)\n", mem));
 170
 171         delete_area(mem->heap_area);
 172         delete_sem(mem->lock);
 173         free(mem);
 174 }
 175
 176
 177 /** Allocate memory block
 178  *
 179  *      \param mem heap handle
 180  *      \param size size in bytes
 181  *      \param tag owner tag
 182  *
 183  *      \param blockID - returns block id
 184  *      \param offset - returns start address of block
 185  */
 186
 187 status_t
 188 mem_alloc(mem_info *mem, uint32 size, void *tag, uint32 *blockID, uint32 *offset)
 189 {
 190         mem_block *current, *newEntry;
 191         status_t status;
 192
 193         TRACE(("mem_alloc(mem %p, size=%lx, tag=%p)\n", mem, size, tag));
 194
 195         status = acquire_sem(mem->lock);
 196         if (status != B_OK)
 197                 return status;
 198
 199         // we assume block_size is power of two
 200         size = (size + mem->block_size - 1) & ~(mem->block_size - 1);
 201
 202         // simple first fit
 203         for (current = mem->first; current; current = current->next) {
 204                 if (!current->allocated && current->size >= size)
 205                         break;
 206         }
 207
 208         if (current == NULL) {
 209                 TRACE(("mem_alloc: out of memory\n"));
 210                 goto err;
 211         }
 212
 213         if (size != current->size) {
 214                 newEntry = mem->unused;
 215
 216                 if (newEntry == NULL) {
 217                         TRACE(("mem_alloc: out of blocks\n"));
 218                         goto err;
 219                 }
 220
 221                 mem->unused = newEntry->next;
 222
 223                 newEntry->next = current->next;
 224                 newEntry->prev = current;
 225                 newEntry->allocated = false;
 226                 newEntry->base = current->base + size;
 227                 newEntry->size = current->size - size;
 228
 229                 if (current->next)
 230                         current->next->prev = newEntry;
 231
 232                 current->next = newEntry;
 233                 current->size = size;
 234         }
 235
 236         current->allocated = true;
 237         current->tag = tag;
 238
 239         *blockID = current - mem->heap + 1;
 240         *offset = current->base;
 241
 242         release_sem(mem->lock);
 243
 244         TRACE(("mem_alloc(block_id=%ld, offset=%lx)\n", *blockID, *offset));
 245         return B_OK;
 246
 247 err:
 248         release_sem(mem->lock);
 249         return B_NO_MEMORY;
 250 }
 251
 252
 253 /** Free memory
 254  *      \param mem heap handle
 255  *      \param blockID block id
 256  *      \param tag owner tag (must match tag passed to mem_alloc())
 257  */
 258
 259 status_t
 260 mem_free(mem_info *mem, uint32 blockID, void *tag)
 261 {
 262         mem_block *block;
 263         status_t status;
 264
 265         TRACE(("mem_free(mem %p, blockID=%ld, tag=%p)\n", mem, blockID, tag));
 266
 267         status = acquire_sem(mem->lock);
 268         if (status != B_OK)
 269                 return status;
 270
 271         --blockID;
 272
 273         if (blockID >= mem->heap_entries) {
 274                 TRACE(("mem_free: invalid ID %lu\n", blockID));
 275                 goto err;
 276         }
 277
 278         block = &mem->heap[blockID];
 279         if (!block->allocated || block->tag != tag) {
 280                 TRACE(("mem_free: not owner\n"));
 281                 goto err;
 282         }
 283
 284         freeblock(mem, block);
 285
 286         release_sem(mem->lock);
 287         return B_OK;
 288
 289 err:
 290         release_sem(mem->lock);
 291         return B_BAD_VALUE;
 292 }
 293
 294
 295 /** Free all memory belonging to owner "tag" */
 296
 297 status_t
 298 mem_freetag(mem_info *mem, void *tag)
 299 {
 300         mem_block *current;
 301         status_t status;
 302
 303         TRACE(("mem_freetag(mem %p, tag=%p)\n", mem, tag));
 304
 305         status = acquire_sem(mem->lock);
 306         if (status != B_OK)
 307                 return status;
 308
 309         for (current = mem->first; current; current = current->next) {
 310                 if (current->allocated && current->tag == tag)
 311                         current = freeblock(mem, current);
 312         }
 313
 314         release_sem(mem->lock);
 315         return B_OK;
 316 }