Home | History | Annotate | Download | only in main
      1 /*
      2  * GLX Hardware Device Driver common code
      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 #include <assert.h>
     26 #include <stdio.h>
     27 #include <stdlib.h>
     28 
     29 #include "compiler.h"
     30 #include "mm.h"
     31 
     32 
     33 void
     34 mmDumpMemInfo(const struct mem_block *heap)
     35 {
     36    fprintf(stderr, "Memory heap %p:\n", (void *)heap);
     37    if (heap == 0) {
     38       fprintf(stderr, "  heap == 0\n");
     39    } else {
     40       const struct mem_block *p;
     41 
     42       for(p = heap->next; p != heap; p = p->next) {
     43 	 fprintf(stderr, "  Offset:%08x, Size:%08x, %c%c\n",p->ofs,p->size,
     44 		 p->free ? 'F':'.',
     45 		 p->reserved ? 'R':'.');
     46       }
     47 
     48       fprintf(stderr, "\nFree list:\n");
     49 
     50       for(p = heap->next_free; p != heap; p = p->next_free) {
     51 	 fprintf(stderr, " FREE Offset:%08x, Size:%08x, %c%c\n",p->ofs,p->size,
     52 		 p->free ? 'F':'.',
     53 		 p->reserved ? 'R':'.');
     54       }
     55 
     56    }
     57    fprintf(stderr, "End of memory blocks\n");
     58 }
     59 
     60 struct mem_block *
     61 mmInit(unsigned ofs, unsigned size)
     62 {
     63    struct mem_block *heap, *block;
     64 
     65    if (!size)
     66       return NULL;
     67 
     68    heap = (struct mem_block *) calloc(1, sizeof(struct mem_block));
     69    if (!heap)
     70       return NULL;
     71 
     72    block = (struct mem_block *) calloc(1, sizeof(struct mem_block));
     73    if (!block) {
     74       free(heap);
     75       return NULL;
     76    }
     77 
     78    heap->next = block;
     79    heap->prev = block;
     80    heap->next_free = block;
     81    heap->prev_free = block;
     82 
     83    block->heap = heap;
     84    block->next = heap;
     85    block->prev = heap;
     86    block->next_free = heap;
     87    block->prev_free = heap;
     88 
     89    block->ofs = ofs;
     90    block->size = size;
     91    block->free = 1;
     92 
     93    return heap;
     94 }
     95 
     96 
     97 static struct mem_block *
     98 SliceBlock(struct mem_block *p,
     99            unsigned startofs, unsigned size,
    100            unsigned reserved, unsigned alignment)
    101 {
    102    struct mem_block *newblock;
    103 
    104    /* break left  [p, newblock, p->next], then p = newblock */
    105    if (startofs > p->ofs) {
    106       newblock = (struct mem_block*) calloc(1, sizeof(struct mem_block));
    107       if (!newblock)
    108 	 return NULL;
    109       newblock->ofs = startofs;
    110       newblock->size = p->size - (startofs - p->ofs);
    111       newblock->free = 1;
    112       newblock->heap = p->heap;
    113 
    114       newblock->next = p->next;
    115       newblock->prev = p;
    116       p->next->prev = newblock;
    117       p->next = newblock;
    118 
    119       newblock->next_free = p->next_free;
    120       newblock->prev_free = p;
    121       p->next_free->prev_free = newblock;
    122       p->next_free = newblock;
    123 
    124       p->size -= newblock->size;
    125       p = newblock;
    126    }
    127 
    128    /* break right, also [p, newblock, p->next] */
    129    if (size < p->size) {
    130       newblock = (struct mem_block*) calloc(1, sizeof(struct mem_block));
    131       if (!newblock)
    132 	 return NULL;
    133       newblock->ofs = startofs + size;
    134       newblock->size = p->size - size;
    135       newblock->free = 1;
    136       newblock->heap = p->heap;
    137 
    138       newblock->next = p->next;
    139       newblock->prev = p;
    140       p->next->prev = newblock;
    141       p->next = newblock;
    142 
    143       newblock->next_free = p->next_free;
    144       newblock->prev_free = p;
    145       p->next_free->prev_free = newblock;
    146       p->next_free = newblock;
    147 
    148       p->size = size;
    149    }
    150 
    151    /* p = middle block */
    152    p->free = 0;
    153 
    154    /* Remove p from the free list:
    155     */
    156    p->next_free->prev_free = p->prev_free;
    157    p->prev_free->next_free = p->next_free;
    158 
    159    p->next_free = 0;
    160    p->prev_free = 0;
    161 
    162    p->reserved = reserved;
    163    return p;
    164 }
    165 
    166 
    167 struct mem_block *
    168 mmAllocMem(struct mem_block *heap, unsigned size, unsigned align2, unsigned startSearch)
    169 {
    170    struct mem_block *p;
    171    const unsigned mask = (1 << align2)-1;
    172    unsigned startofs = 0;
    173    unsigned endofs;
    174 
    175    if (!heap || !size)
    176       return NULL;
    177 
    178    for (p = heap->next_free; p != heap; p = p->next_free) {
    179       assert(p->free);
    180 
    181       startofs = (p->ofs + mask) & ~mask;
    182       if ( startofs < startSearch ) {
    183 	 startofs = startSearch;
    184       }
    185       endofs = startofs+size;
    186       if (endofs <= (p->ofs+p->size))
    187 	 break;
    188    }
    189 
    190    if (p == heap)
    191       return NULL;
    192 
    193    assert(p->free);
    194    p = SliceBlock(p,startofs,size,0,mask+1);
    195 
    196    return p;
    197 }
    198 
    199 
    200 struct mem_block *
    201 mmFindBlock(struct mem_block *heap, unsigned start)
    202 {
    203    struct mem_block *p;
    204 
    205    for (p = heap->next; p != heap; p = p->next) {
    206       if (p->ofs == start)
    207 	 return p;
    208    }
    209 
    210    return NULL;
    211 }
    212 
    213 
    214 static inline int
    215 Join2Blocks(struct mem_block *p)
    216 {
    217    /* XXX there should be some assertions here */
    218 
    219    /* NOTE: heap->free == 0 */
    220 
    221    if (p->free && p->next->free) {
    222       struct mem_block *q = p->next;
    223 
    224       assert(p->ofs + p->size == q->ofs);
    225       p->size += q->size;
    226 
    227       p->next = q->next;
    228       q->next->prev = p;
    229 
    230       q->next_free->prev_free = q->prev_free;
    231       q->prev_free->next_free = q->next_free;
    232 
    233       free(q);
    234       return 1;
    235    }
    236    return 0;
    237 }
    238 
    239 int
    240 mmFreeMem(struct mem_block *b)
    241 {
    242    if (!b)
    243       return 0;
    244 
    245    if (b->free) {
    246       fprintf(stderr, "block already free\n");
    247       return -1;
    248    }
    249    if (b->reserved) {
    250       fprintf(stderr, "block is reserved\n");
    251       return -1;
    252    }
    253 
    254    b->free = 1;
    255    b->next_free = b->heap->next_free;
    256    b->prev_free = b->heap;
    257    b->next_free->prev_free = b;
    258    b->prev_free->next_free = b;
    259 
    260    Join2Blocks(b);
    261    if (b->prev != b->heap)
    262       Join2Blocks(b->prev);
    263 
    264    return 0;
    265 }
    266 
    267 
    268 void
    269 mmDestroy(struct mem_block *heap)
    270 {
    271    struct mem_block *p;
    272 
    273    if (!heap)
    274       return;
    275 
    276    for (p = heap->next; p != heap; ) {
    277       struct mem_block *next = p->next;
    278       free(p);
    279       p = next;
    280    }
    281 
    282    free(heap);
    283 }
    284