Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  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.