Home | History | Annotate | Download | only in util
      1 /**************************************************************************
      2  *
      3  * Copyright (C) 1999 Wittawat Yamwong
      4  *
      5  * Permission is hereby granted, free of charge, to any person obtaining a
      6  * copy of this software and associated documentation files (the "Software"),
      7  * to deal in the Software without restriction, including without limitation
      8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
      9  * and/or sell copies of the Software, and to permit persons to whom the
     10  * Software is furnished to do so, subject to the following conditions:
     11  *
     12  * The above copyright notice and this permission notice shall be included
     13  * in all copies or substantial portions of the Software.
     14  *
     15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
     16  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
     17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
     18  * WITTAWAT YAMWONG, OR ANY OTHER CONTRIBUTORS BE LIABLE FOR ANY CLAIM,
     19  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
     20  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
     21  * OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
     22  *
     23  **************************************************************************/
     24 
     25 
     26 #include "pipe/p_compiler.h"
     27 #include "util/u_debug.h"
     28 
     29 #include "util/u_memory.h"
     30 #include "util/u_mm.h"
     31 
     32 
     33 void
     34 u_mmDumpMemInfo(const struct mem_block *heap)
     35 {
     36    debug_printf("Memory heap %p:\n", (void *) heap);
     37    if (heap == 0) {
     38       debug_printf("  heap == 0\n");
     39    }
     40    else {
     41       const struct mem_block *p;
     42       int total_used = 0, total_free = 0;
     43 
     44       for (p = heap->next; p != heap; p = p->next) {
     45 	 debug_printf("  Offset:%08x, Size:%08x, %c%c\n", p->ofs, p->size,
     46                       p->free ? 'F':'.',
     47                       p->reserved ? 'R':'.');
     48          if (p->free)
     49             total_free += p->size;
     50          else
     51             total_used += p->size;
     52       }
     53 
     54       debug_printf("'\nMemory stats: total = %d, used = %d, free = %d\n",
     55                    total_used + total_free, total_used, total_free);
     56       debug_printf("\nFree list:\n");
     57 
     58       for (p = heap->next_free; p != heap; p = p->next_free) {
     59 	 debug_printf(" FREE Offset:%08x, Size:%08x, %c%c\n", p->ofs, p->size,
     60                       p->free ? 'F':'.',
     61                       p->reserved ? 'R':'.');
     62       }
     63 
     64    }
     65    debug_printf("End of memory blocks\n");
     66 }
     67 
     68 
     69 struct mem_block *
     70 u_mmInit(int ofs, int size)
     71 {
     72    struct mem_block *heap, *block;
     73 
     74    if (size <= 0)
     75       return NULL;
     76 
     77    heap = CALLOC_STRUCT(mem_block);
     78    if (!heap)
     79       return NULL;
     80 
     81    block = CALLOC_STRUCT(mem_block);
     82    if (!block) {
     83       FREE(heap);
     84       return NULL;
     85    }
     86 
     87    heap->next = block;
     88    heap->prev = block;
     89    heap->next_free = block;
     90    heap->prev_free = block;
     91 
     92    block->heap = heap;
     93    block->next = heap;
     94    block->prev = heap;
     95    block->next_free = heap;
     96    block->prev_free = heap;
     97 
     98    block->ofs = ofs;
     99    block->size = size;
    100    block->free = 1;
    101 
    102    return heap;
    103 }
    104 
    105 
    106 static struct mem_block *
    107 SliceBlock(struct mem_block *p,
    108            int startofs, int size,
    109            int reserved, int alignment)
    110 {
    111    struct mem_block *newblock;
    112 
    113    /* break left  [p, newblock, p->next], then p = newblock */
    114    if (startofs > p->ofs) {
    115       newblock = CALLOC_STRUCT(mem_block);
    116       if (!newblock)
    117 	 return NULL;
    118       newblock->ofs = startofs;
    119       newblock->size = p->size - (startofs - p->ofs);
    120       newblock->free = 1;
    121       newblock->heap = p->heap;
    122 
    123       newblock->next = p->next;
    124       newblock->prev = p;
    125       p->next->prev = newblock;
    126       p->next = newblock;
    127 
    128       newblock->next_free = p->next_free;
    129       newblock->prev_free = p;
    130       p->next_free->prev_free = newblock;
    131       p->next_free = newblock;
    132 
    133       p->size -= newblock->size;
    134       p = newblock;
    135    }
    136 
    137    /* break right, also [p, newblock, p->next] */
    138    if (size < p->size) {
    139       newblock = CALLOC_STRUCT(mem_block);
    140       if (!newblock)
    141 	 return NULL;
    142       newblock->ofs = startofs + size;
    143       newblock->size = p->size - size;
    144       newblock->free = 1;
    145       newblock->heap = p->heap;
    146 
    147       newblock->next = p->next;
    148       newblock->prev = p;
    149       p->next->prev = newblock;
    150       p->next = newblock;
    151 
    152       newblock->next_free = p->next_free;
    153       newblock->prev_free = p;
    154       p->next_free->prev_free = newblock;
    155       p->next_free = newblock;
    156 
    157       p->size = size;
    158    }
    159 
    160    /* p = middle block */
    161    p->free = 0;
    162 
    163    /* Remove p from the free list:
    164     */
    165    p->next_free->prev_free = p->prev_free;
    166    p->prev_free->next_free = p->next_free;
    167 
    168    p->next_free = 0;
    169    p->prev_free = 0;
    170 
    171    p->reserved = reserved;
    172    return p;
    173 }
    174 
    175 
    176 struct mem_block *
    177 u_mmAllocMem(struct mem_block *heap, int size, int align2, int startSearch)
    178 {
    179    struct mem_block *p;
    180    const int mask = (1 << align2)-1;
    181    int startofs = 0;
    182    int endofs;
    183 
    184    assert(size >= 0);
    185    assert(align2 >= 0);
    186    assert(align2 <= 12); /* sanity check, 2^12 (4KB) enough? */
    187 
    188    if (!heap || align2 < 0 || size <= 0)
    189       return NULL;
    190 
    191    for (p = heap->next_free; p != heap; p = p->next_free) {
    192       assert(p->free);
    193 
    194       startofs = (p->ofs + mask) & ~mask;
    195       if ( startofs < startSearch ) {
    196 	 startofs = startSearch;
    197       }
    198       endofs = startofs+size;
    199       if (endofs <= (p->ofs+p->size))
    200 	 break;
    201    }
    202 
    203    if (p == heap)
    204       return NULL;
    205 
    206    assert(p->free);
    207    p = SliceBlock(p,startofs,size,0,mask+1);
    208 
    209    return p;
    210 }
    211 
    212 
    213 struct mem_block *
    214 u_mmFindBlock(struct mem_block *heap, int start)
    215 {
    216    struct mem_block *p;
    217 
    218    for (p = heap->next; p != heap; p = p->next) {
    219       if (p->ofs == start)
    220 	 return p;
    221    }
    222 
    223    return NULL;
    224 }
    225 
    226 
    227 static INLINE int
    228 Join2Blocks(struct mem_block *p)
    229 {
    230    /* XXX there should be some assertions here */
    231 
    232    /* NOTE: heap->free == 0 */
    233 
    234    if (p->free && p->next->free) {
    235       struct mem_block *q = p->next;
    236 
    237       assert(p->ofs + p->size == q->ofs);
    238       p->size += q->size;
    239 
    240       p->next = q->next;
    241       q->next->prev = p;
    242 
    243       q->next_free->prev_free = q->prev_free;
    244       q->prev_free->next_free = q->next_free;
    245 
    246       FREE(q);
    247       return 1;
    248    }
    249    return 0;
    250 }
    251 
    252 int
    253 u_mmFreeMem(struct mem_block *b)
    254 {
    255    if (!b)
    256       return 0;
    257 
    258    if (b->free) {
    259       debug_printf("block already free\n");
    260       return -1;
    261    }
    262    if (b->reserved) {
    263       debug_printf("block is reserved\n");
    264       return -1;
    265    }
    266 
    267    b->free = 1;
    268    b->next_free = b->heap->next_free;
    269    b->prev_free = b->heap;
    270    b->next_free->prev_free = b;
    271    b->prev_free->next_free = b;
    272 
    273    Join2Blocks(b);
    274    if (b->prev != b->heap)
    275       Join2Blocks(b->prev);
    276 
    277    return 0;
    278 }
    279 
    280 
    281 void
    282 u_mmDestroy(struct mem_block *heap)
    283 {
    284    struct mem_block *p;
    285 
    286    if (!heap)
    287       return;
    288 
    289    for (p = heap->next; p != heap; ) {
    290       struct mem_block *next = p->next;
    291       FREE(p);
    292       p = next;
    293    }
    294 
    295    FREE(heap);
    296 }
    297