Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  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.