sm64

A Super Mario 64 decompilation
Log | Files | Refs | README | LICENSE

gd_memory.c (9113B)


      1 #include <PR/ultratypes.h>
      2 
      3 #include "debug_utils.h"
      4 #include "gd_memory.h"
      5 #include "renderer.h"
      6 
      7 /**
      8  * @file gd_memory.c
      9  *
     10  * This file contains the functions need to manage allocation in
     11  * goddard's heap. However, the actual, useable allocation functions
     12  * are `gd_malloc()`, `gd_malloc_perm()`, and `gd_malloc_temp()`, as
     13  * well as `gd_free()`. This file is for managing the underlying memory
     14  * block lists.
     15  */
     16 
     17 /* bss */
     18 static struct GMemBlock *sFreeBlockListHead;
     19 static struct GMemBlock *sUsedBlockListHead;
     20 static struct GMemBlock *sEmptyBlockListHead;
     21 
     22 /* Forward Declarations */
     23 void empty_mem_block(struct GMemBlock *);
     24 struct GMemBlock *into_free_memblock(struct GMemBlock *);
     25 struct GMemBlock *make_mem_block(u32, u8);
     26 u32 print_list_stats(struct GMemBlock *, s32, s32);
     27 
     28 /**
     29  * Empty a `GMemBlock` into a default state. This empty block
     30  * doesn't point to any data, nor does it have any size. The
     31  * block is removed from whatever list is was in, and is added
     32  * to the empty block list.
     33  */
     34 void empty_mem_block(struct GMemBlock *block) {
     35     if (block->next != NULL) {
     36         block->next->prev = block->prev;
     37     }
     38 
     39     if (block->prev != NULL) {
     40         block->prev->next = block->next;
     41     }
     42 
     43     switch (block->blockType) {
     44         case G_MEM_BLOCK_FREE:
     45             if (block->prev == NULL) {
     46                 sFreeBlockListHead = block->next;
     47             }
     48             break;
     49         case G_MEM_BLOCK_USED:
     50             if (block->prev == NULL) {
     51                 sUsedBlockListHead = block->next;
     52             }
     53             break;
     54     }
     55 
     56     block->next = sEmptyBlockListHead;
     57     if (block->next != NULL) {
     58         sEmptyBlockListHead->prev = block;
     59     }
     60 
     61     sEmptyBlockListHead = block;
     62     block->prev = NULL;
     63     block->ptr = NULL;
     64     block->size = 0;
     65 }
     66 
     67 /**
     68  * Transform a `GMemBlock` into a free block that points to memory available
     69  * for allocation.
     70  *
     71  * @returns pointer to the free `GMemBlock` */
     72 struct GMemBlock *into_free_memblock(struct GMemBlock *block) {
     73     struct GMemBlock *freeBlock;
     74     void *ptr;
     75     u8 permanence;
     76     u32 space;
     77 
     78     ptr = block->ptr;
     79     space = block->size;
     80     permanence = block->permFlag;
     81 
     82     empty_mem_block(block);
     83     freeBlock = make_mem_block(G_MEM_BLOCK_FREE, permanence);
     84     freeBlock->ptr = ptr;
     85     freeBlock->size = space;
     86     freeBlock->permFlag = permanence;
     87 
     88     return freeBlock;
     89 }
     90 
     91 /**
     92  * Allocate a new `GMemBlock` structure of the given type and permanence.
     93  * It does not assign any heap space to the new block.
     94  *
     95  * @param blockType either `G_MEM_BLOCK_FREE` or `G_MEM_BLOCK_USED`
     96  * @param permFlag  some sort of permanence value, where setting one the upper
     97  *                  four bits imply a permanent block, while setting one the lower
     98  *                  four bits imply a temporary block
     99  * @returns a pointer to the new `GMemBlock`
    100  */
    101 struct GMemBlock *make_mem_block(u32 blockType, u8 permFlag) {
    102     struct GMemBlock *newMemBlock;
    103 
    104     if (sEmptyBlockListHead == NULL) {
    105         sEmptyBlockListHead = (struct GMemBlock *) gd_allocblock(sizeof(struct GMemBlock));
    106 
    107         if (sEmptyBlockListHead == NULL) {
    108             fatal_printf("MakeMemBlock() unable to allocate");
    109         }
    110 
    111         sEmptyBlockListHead->next = NULL;
    112         sEmptyBlockListHead->prev = NULL;
    113     }
    114 
    115     newMemBlock = sEmptyBlockListHead;
    116     if ((sEmptyBlockListHead = newMemBlock->next) != NULL) {
    117         newMemBlock->next->prev = NULL;
    118     }
    119 
    120     switch (blockType) {
    121         case G_MEM_BLOCK_FREE:
    122             newMemBlock->next = sFreeBlockListHead;
    123             if (newMemBlock->next != NULL) {
    124                 sFreeBlockListHead->prev = newMemBlock;
    125             }
    126             sFreeBlockListHead = newMemBlock;
    127             break;
    128         case G_MEM_BLOCK_USED:
    129             newMemBlock->next = sUsedBlockListHead;
    130             if (newMemBlock->next != NULL) {
    131                 sUsedBlockListHead->prev = newMemBlock;
    132             }
    133             sUsedBlockListHead = newMemBlock;
    134             break;
    135         default:
    136             fatal_printf("unkown memblock type");
    137     }
    138     newMemBlock->prev = NULL;
    139     newMemBlock->blockType = (u8) blockType;
    140     newMemBlock->permFlag = permFlag;
    141 
    142     return newMemBlock;
    143 }
    144 
    145 /**
    146  * Free memory allocated on the goddard heap.
    147  *
    148  * @param ptr pointer to heap allocated memory
    149  * @returns size of memory freed
    150  * @retval  0    `ptr` did not point to a valid memory block
    151  */
    152 u32 gd_free_mem(void *ptr) {
    153     register struct GMemBlock *curBlock;
    154     u32 bytesFreed;
    155     register u8 *targetBlock = ptr;
    156 
    157     for (curBlock = sUsedBlockListHead; curBlock != NULL; curBlock = curBlock->next) {
    158         if (targetBlock == curBlock->ptr) {
    159             bytesFreed = curBlock->size;
    160             into_free_memblock(curBlock);
    161             return bytesFreed;
    162         }
    163     }
    164 
    165     fatal_printf("Free() Not a valid memory block");
    166     return 0;
    167 }
    168 
    169 /**
    170  * Request a pointer to goddard heap memory of at least `size` and
    171  * of the same `permanence`.
    172  *
    173  * @return pointer to heap
    174  * @retval NULL could not fulfill the request
    175  */
    176 void *gd_request_mem(u32 size, u8 permanence) {
    177     struct GMemBlock *foundBlock = NULL;
    178     struct GMemBlock *curBlock;
    179     struct GMemBlock *newBlock;
    180 
    181     newBlock = make_mem_block(G_MEM_BLOCK_USED, permanence);
    182     curBlock = sFreeBlockListHead;
    183 
    184     while (curBlock != NULL) {
    185         if (curBlock->permFlag & permanence) {
    186             if (curBlock->size == size) {
    187                 foundBlock = curBlock;
    188                 break;
    189             } else {
    190                 if (curBlock->size > size) {
    191                     if (foundBlock != NULL) { /* find closest sized block */
    192                         if (curBlock->size < foundBlock->size) {
    193                             foundBlock = curBlock;
    194                         }
    195                     } else {
    196                         foundBlock = curBlock;
    197                     }
    198                 }
    199             }
    200         }
    201         curBlock = curBlock->next;
    202     }
    203 
    204     if (foundBlock == NULL) {
    205         return NULL;
    206     }
    207 
    208     if (foundBlock->size > size) { /* split free block */
    209         newBlock->ptr = foundBlock->ptr;
    210         newBlock->size = size;
    211 
    212         foundBlock->size -= size;
    213         foundBlock->ptr += size;
    214     } else if (foundBlock->size == size) { /* recycle whole free block */
    215         newBlock->ptr = foundBlock->ptr;
    216         newBlock->size = size;
    217         empty_mem_block(foundBlock);
    218     }
    219 
    220     return newBlock->ptr;
    221 }
    222 
    223 /**
    224  * Add memory of `size` at `addr` to the goddard heap for later allocation.
    225  *
    226  * @returns `GMemBlock` that contains info about the new heap memory
    227  */
    228 struct GMemBlock *gd_add_mem_to_heap(u32 size, void *addr, u8 permanence) {
    229     struct GMemBlock *newBlock;
    230     /* eight-byte align the new block's data stats */
    231     size = (size - 8) & ~7;
    232     addr = (void *)(((uintptr_t) addr + 8) & ~7);
    233 
    234     newBlock = make_mem_block(G_MEM_BLOCK_FREE, permanence);
    235     newBlock->ptr = addr;
    236     newBlock->size = size;
    237 
    238     return newBlock;
    239 }
    240 
    241 /**
    242  * NULL the various `GMemBlock` list heads
    243  */
    244 void init_mem_block_lists(void) {
    245     sFreeBlockListHead = NULL;
    246     sUsedBlockListHead = NULL;
    247     sEmptyBlockListHead = NULL;
    248 }
    249 
    250 /**
    251  * Print information (size, entries) about the `GMemBlock` list. It can print
    252  * information for individual blocks as well as summary info for the entry list.
    253  *
    254  * @param block          `GMemBlock` to start reading the list
    255  * @param printBlockInfo If `TRUE`, print information about every block
    256  *                       in the list
    257  * @param permanence     Limit info printed to blocks with this permanence
    258  * @returns number of entries
    259  */
    260 u32 print_list_stats(struct GMemBlock *block, s32 printBlockInfo, s32 permanence) {
    261     u32 entries = 0;
    262     u32 totalSize = 0;
    263 
    264     while (block != NULL) {
    265         if (block->permFlag & permanence) {
    266             entries++;
    267             if (printBlockInfo) {
    268                 gd_printf("     %6.2fk (%d bytes)\n",
    269                           (f32) block->size / 1024.0, //? 1024.0f
    270                           block->size);
    271             }
    272             totalSize += block->size;
    273         }
    274         block = block->next;
    275     }
    276 
    277     gd_printf("Total %6.2fk (%d bytes) in %d entries\n",
    278               (f32) totalSize / 1024.0, //? 1024.0f
    279               totalSize, entries);
    280 
    281     return entries;
    282 }
    283 
    284 /**
    285  * Print summary information about all used, free, and empty
    286  * `GMemBlock`s.
    287  */
    288 void mem_stats(void) {
    289     struct GMemBlock *list;
    290 
    291     gd_printf("Perm Used blocks:\n");
    292     list = sUsedBlockListHead;
    293     print_list_stats(list, FALSE, PERM_G_MEM_BLOCK);
    294     gd_printf("\n");
    295 
    296     gd_printf("Perm Free blocks:\n");
    297     list = sFreeBlockListHead;
    298     print_list_stats(list, FALSE, PERM_G_MEM_BLOCK);
    299     gd_printf("\n");
    300 
    301     gd_printf("Temp Used blocks:\n");
    302     list = sUsedBlockListHead;
    303     print_list_stats(list, FALSE, TEMP_G_MEM_BLOCK);
    304     gd_printf("\n");
    305 
    306     gd_printf("Temp Free blocks:\n");
    307     list = sFreeBlockListHead;
    308     print_list_stats(list, FALSE, TEMP_G_MEM_BLOCK);
    309     gd_printf("\n");
    310 
    311     gd_printf("Empty blocks:\n");
    312     list = sEmptyBlockListHead;
    313     print_list_stats(list, FALSE, PERM_G_MEM_BLOCK | TEMP_G_MEM_BLOCK);
    314 }