src/mem/memblock.c File Reference

#include "memint.h"
Include dependency graph for memblock.c:

Go to the source code of this file.

Functions

void exit ()
void mem_copy (pointer dest, pointer src, SIZE_T size)
void mem_zero (pointer ptr, SIZE_T size)
void mem_fatal (char *message)
SIZE_T mem_allocation ()
static int ceiling_log_2 (SIZE_T i)
static int block_size_index (SIZE_T size)
static void add_to_free_list (block b)
static block remove_from_free_list (block b)
static block buddy (block b)
static void trim_to_size (block b, int size_index)
static void merge_and_free (block b)
pointer mem_get_block (SIZE_T size)
void mem_free_block (pointer p)
pointer mem_resize_block (pointer p, SIZE_T new_size)

Variables

static SIZE_T block_allocation
static block avail [MAX_SIZE_INDEX+1]
static struct segment_ dummy_seg = {(pointer)0, (SIZE_T)0}
static segment curr_seg = &dummy_seg

Function Documentation

static void add_to_free_list ( block  b  )  [static]

Definition at line 145 of file memblock.c.

00148 {
00149   int i;
00150 
00151   i=b->size_index;
00152   if (!avail[i])
00153     {
00154       b->next=b;
00155       b->prev=b;
00156       avail[i]=b;
00157     }
00158   else
00159     {
00160       b->next=avail[i]->next;
00161       avail[i]->next->prev=b;
00162       avail[i]->next=b;
00163       b->prev=avail[i];
00164     }
00165   b->used=0;
00166 }

static int block_size_index ( SIZE_T  size  )  [static]

Definition at line 124 of file memblock.c.

00127 {
00128   if (size < 1)
00129     return (-1);
00130   if (size > MAX_SIZE)
00131     mem_fatal("block_size_index: block size too large");
00132   else
00133     size+=HEADER_SIZE;
00134   return (ceiling_log_2(size));
00135 }

static block buddy ( block  b  )  [static]

Definition at line 206 of file memblock.c.

00209 {
00210   SIZE_T buddy_offset;
00211 
00212   buddy_offset=(SIZE_T)(((INT_PTR)b-(INT_PTR)b->seg->base_address) ^ ((SIZE_T)1 << b->size_index));
00213   if (buddy_offset < b->seg->limit)
00214     return ((block)((INT_PTR)b->seg->base_address+buddy_offset));
00215   else
00216     return ((block)0);
00217 }

static int ceiling_log_2 ( SIZE_T  i  )  [static]

Definition at line 105 of file memblock.c.

00108 {
00109   SIZE_T j;
00110   int result;
00111 
00112   for (result=0, j=1; j < i; ++result, j*=2);
00113   return (result);
00114 }

void exit (  ) 
SIZE_T mem_allocation (  ) 

Definition at line 73 of file memblock.c.

00075 {
00076   /* This will always returns zero when we're using malloc and free, */
00077   /* but you can maybe change it depending on your system. */
00078   return (block_allocation);
00079 }

void mem_copy ( pointer  dest,
pointer  src,
SIZE_T  size 
)

Definition at line 29 of file memblock.c.

00034 {
00035   MEM_COPY(dest, src, size);
00036 }

void mem_fatal ( char *  message  ) 

Definition at line 60 of file memblock.c.

00063 {
00064   fprintf(stderr, "Memory management library: error: %s\n", message);
00065   exit(1);
00066 }

void mem_free_block ( pointer  p  ) 

Definition at line 359 of file memblock.c.

00362 {
00363   block b;
00364 
00365   if (!p)
00366     return;
00367   b=(block)((INT_PTR)p-HEADER_SIZE);
00368   if (!b->used)
00369     mem_fatal("mem_free_block: block not in use");
00370   if (b->size_index < 0 || b->size_index > MAX_SIZE_INDEX)
00371     mem_fatal("mem_free_block: invalid block header");
00372   merge_and_free(b);
00373 }

pointer mem_get_block ( SIZE_T  size  ) 

Definition at line 279 of file memblock.c.

00282 {
00283   int i;
00284   int size_index;
00285   int alloc_size_index;
00286   int new_seg;
00287   SIZE_T alloc_size;
00288   pointer sbrk_ret;
00289   block b;
00290 
00291   if ((size_index=block_size_index(size)) < 0)
00292     return ((pointer)0);
00293   /* Find smallest free block which is large enough. */
00294   for (i=size_index; i <= MAX_SIZE_INDEX && !avail[i]; ++i);
00295   if (i > MAX_SIZE_INDEX)
00296     {
00297       /* We must get more storage; don't allocate less than */
00298       /* 2^MIN_ALLOC_SIZE_INDEX. */
00299       if (size_index < MIN_ALLOC_SIZE_INDEX)
00300         alloc_size_index=MIN_ALLOC_SIZE_INDEX;
00301       else
00302         alloc_size_index=size_index;
00303       alloc_size=((SIZE_T)1 << alloc_size_index);
00304       /* Pad current segment to be a multiple of 2^alloc_size_index in */
00305       /* length. */
00306       alloc_size+=((curr_seg->limit+alloc_size-1) & ~(alloc_size-1))-curr_seg->limit;
00307       if ((sbrk_ret=(pointer)SBRK(0)) != (pointer)((INT_PTR)curr_seg->base_address+curr_seg->limit) ||
00308           alloc_size+curr_seg->limit > MAX_SEG_SIZE)
00309         {
00310           /* Segment is too large or someone else has moved the break. */
00311           /* Pad to get to appropriate boundary. */
00312           alloc_size=ROUNDUP((INT_PTR)sbrk_ret)-(INT_PTR)sbrk_ret;
00313           /* Pad allocation request with storage for new segment */
00314           /* information and indicate that a new segment must be */
00315           /* created. */
00316           alloc_size+=((SIZE_T)1 << alloc_size_index)+ROUNDUP(sizeof(struct segment_));
00317           new_seg=1;
00318         }
00319       else
00320         new_seg=0;
00321       sbrk_ret=(pointer)SBRK(alloc_size);
00322       if (sbrk_ret == (pointer)-1)
00323         mem_fatal("mem_get_block: allocation failed");
00324       block_allocation+=alloc_size;
00325       if (new_seg)
00326         {
00327           curr_seg=(segment)ROUNDUP((INT_PTR)sbrk_ret);
00328           curr_seg->base_address=(pointer)((INT_PTR)curr_seg+ROUNDUP(sizeof(struct segment_)));
00329           curr_seg->limit=0;
00330           /* Readjust allocation size. */
00331           alloc_size=(1l << alloc_size_index);
00332         }
00333       /* Carve allocated space up into blocks and add to free lists. */
00334       while (alloc_size)
00335         {
00336           size=alloc_size-(alloc_size & (alloc_size-1));
00337           b=(block)((INT_PTR)curr_seg->base_address+curr_seg->limit);
00338           b->size_index=ceiling_log_2(size);
00339           b->seg=curr_seg;
00340           add_to_free_list(b);
00341           curr_seg->limit+=size;
00342           alloc_size-=size;
00343         }
00344       /* Find free block of appropriate size. */
00345       for (i=size_index; i <= MAX_SIZE_INDEX && !avail[i]; ++i);
00346     }
00347   b=remove_from_free_list(avail[i]);
00348   trim_to_size(b, size_index);
00349   return ((pointer)((INT_PTR)b+HEADER_SIZE));
00350 }

pointer mem_resize_block ( pointer  p,
SIZE_T  new_size 
)

Definition at line 384 of file memblock.c.

00388 {
00389   int new_size_index;
00390   block b;
00391   block bb;
00392   pointer q;
00393   SIZE_T old_size;
00394 
00395   if (!p)
00396     return (mem_get_block(new_size));
00397   b=(block)((INT_PTR)p-HEADER_SIZE);
00398   if (!b->used)
00399     mem_fatal("mem_resize_block: block not in use");
00400   if (b->size_index < 0 || b->size_index > MAX_SIZE_INDEX)
00401     mem_fatal("mem_resize_block: invalid block header");
00402   if ((new_size_index=block_size_index(new_size)) < 0)
00403     {
00404       mem_free_block(p);
00405       return ((pointer)0);
00406     }
00407   if (b->size_index >= new_size_index)
00408     {
00409       /* Shrink block. */
00410       trim_to_size(b, new_size_index);
00411       return (p);
00412     }
00413   old_size=(1l << b->size_index)-HEADER_SIZE;
00414   /* Try to expand by adding buddies at higher addresses. */
00415   for (bb=buddy(b);
00416        bb && (INT_PTR)b < (INT_PTR)bb && !bb->used && bb->size_index == b->size_index;
00417        bb=buddy(b))
00418     {
00419       remove_from_free_list(bb);
00420       if (++(b->size_index) == new_size_index)
00421         return (p);
00422     }
00423   /* Couldn't expand all the way to needed size; allocate a new block */
00424   /* and move the contents of the old one. */
00425   q=mem_get_block(new_size);
00426   mem_copy(q, p, old_size);
00427   merge_and_free(b);
00428   return (q);
00429 }

void mem_zero ( pointer  ptr,
SIZE_T  size 
)

Definition at line 45 of file memblock.c.

00049 {
00050   MEM_ZERO(ptr, size);
00051 }

static void merge_and_free ( block  b  )  [static]

Definition at line 256 of file memblock.c.

00259 {
00260   block bb;
00261 
00262   for (bb=buddy(b); bb && !bb->used && bb->size_index == b->size_index; bb=buddy(b))
00263     {
00264       remove_from_free_list(bb);
00265       if ((INT_PTR)bb < (INT_PTR)b)
00266         b=bb;
00267       b->size_index++;
00268     }
00269   add_to_free_list(b);
00270 }

static block remove_from_free_list ( block  b  )  [static]

Definition at line 177 of file memblock.c.

00180 {
00181   int i;
00182 
00183   i=b->size_index;
00184   if (b->next == b)
00185     avail[i]=0;
00186   else
00187     {
00188       b->next->prev=b->prev;
00189       b->prev->next=b->next;
00190       if (avail[i] == b)
00191         avail[i]=b->next;
00192     }
00193   b->used=1;
00194   return (b);
00195 }

static void trim_to_size ( block  b,
int  size_index 
) [static]

Definition at line 229 of file memblock.c.

00233 {
00234   block bb;
00235 
00236   while (b->size_index > size_index)
00237     {
00238       b->size_index--;
00239       bb=buddy(b);
00240       bb->size_index=b->size_index;
00241       bb->seg=b->seg;
00242       add_to_free_list(bb);
00243     }
00244 }

Variable Documentation

block avail[MAX_SIZE_INDEX+1] [static]

Definition at line 87 of file memblock.c.

SIZE_T block_allocation [static]

Definition at line 20 of file memblock.c.

segment curr_seg = &dummy_seg [static]

Definition at line 97 of file memblock.c.

struct segment_ dummy_seg = {(pointer)0, (SIZE_T)0} [static]

Definition at line 92 of file memblock.c.

Generated on Tue Jan 12 13:57:27 2010 for glu-2.2 by  doxygen 1.6.1