/* Satoria's malloc intended to be optimized for lpmud. ** this memory manager distinguishes between two sizes ** of blocks: small and large. It manages them separately ** in the hopes of avoiding fragmentation between them. ** It expects small blocks to mostly be temporaries. ** It expects an equal number of future requests as small ** block deallocations. */ #include "config.h" #include <stdio.h> #include <varargs.h> #define fake(s) #define SMALL_BLOCK_MAX_BYTES 64 #define SMALL_CHUNK_SIZE 0x4000 #define CHUNK_SIZE 0x10000 #define SINT sizeof(int) #define SMALL_BLOCK_MAX (SMALL_BLOCK_MAX_BYTES/SINT) #define PREV_BLOCK 0x80000000 #define THIS_BLOCK 0x40000000 #define MASK 0x3FFFFFFF /* SMALL BLOCK info */ typedef unsigned int u; static u *sfltable[SMALL_BLOCK_MAX]; /* freed list */ static u *next_unused; static u unused_size; /* until we need a new chunk */ /* LARGE BLOCK info */ static u *free_list; static u *start_next_block; /* STATISTICS */ static int small_count[SMALL_BLOCK_MAX]; static int small_total[SMALL_BLOCK_MAX]; static int small_max[SMALL_BLOCK_MAX]; static int small_free[SMALL_BLOCK_MAX]; typedef struct { unsigned counter, size; } stat; #define count(a,b) { a.size+=(b); if ((b)<0) --a.counter; else ++a.counter; } /********************************************************/ /* SMALL BLOCK HANDLER */ /********************************************************/ static char *large_malloc(); static void large_free(); #define s_size_ptr(p) (p) #define s_next_ptr(p) ((u **) (p+1)) stat small_alloc_stat; stat small_free_stat; stat small_chunk_stat; /*char *smalloc(size)*/ char *malloc(size) u size; { int i; u *temp; if (size>SMALL_BLOCK_MAX_BYTES) return large_malloc(size,0); i = (size - 1) >> 2; size = i+2; /* block size in ints */ count(small_alloc_stat,size << 2); small_count[i] += 1; /* update statistics */ small_total[i] += 1; if (small_count[i] >= small_max[i]) small_max[i] = small_count[i]; if (sfltable[i]) { /* allocate from the free list */ count(small_free_stat, -(int) (size << 2)); temp = sfltable[i]; sfltable[i] = * (u **) (temp+1); fake("From free list."); return (char *) (temp+1); } /* else allocate from the chunk */ if (unused_size<size) /* no room in chunk, get another */ { fake("Allocating new small chunk."); next_unused = (u *) large_malloc(SMALL_CHUNK_SIZE,1); count(small_chunk_stat, SMALL_CHUNK_SIZE+SINT); unused_size = SMALL_CHUNK_SIZE / SINT; } else fake("Allocated from chunk."); temp = (u *) s_next_ptr(next_unused); *s_size_ptr(next_unused) = size; next_unused += size; unused_size -= size; return (char *) temp; } /*void sfree(ptr)*/ void free(ptr) char *ptr; { u *block; u i; block = (u *) ptr; block -= 1; if ((*s_size_ptr(block) & MASK) > SMALL_BLOCK_MAX + 1) { large_free(ptr); return; } i = *block - 2; count(small_alloc_stat, - (int) ((i+2) << 2)); count(small_free_stat, (i+2) << 2); *s_next_ptr(block) = sfltable[i]; sfltable[i] = block; small_free[i] += 1; fake("Freed"); } /************************************************/ /* LARGE BLOCK HANDLER */ /************************************************/ #define BEST_FIT 0 #define FIRST_FIT 1 #define HYBRID 2 int fit_style =BEST_FIT; #define l_size_ptr(p) (p) #define l_next_ptr(p) (*((u **) (p+1))) #define l_prev_ptr(p) (*((u **) (p+2))) #define l_next_block(p) (p + (*(p))) #define l_prev_block(p) (p - (*(p-1))) #define l_prev_free(p) (!(*p & PREV_BLOCK)) #define l_next_free(p) (!(*l_next_block(p) & THIS_BLOCK)) void show_block(ptr) u *ptr; { printf("[%c%d: %d] ",(*ptr & THIS_BLOCK ? '+' : '-'), (int) ptr, *ptr & MASK); } void show_free_list() { u *p; p = free_list; while (p) { show_block(p); p = l_next_ptr(p); } printf("\n"); } stat large_free_stat; void remove_from_free_list(ptr) u *ptr; { count(large_free_stat, - (int) (*ptr & MASK) << 2); if (l_prev_ptr(ptr)) l_next_ptr(l_prev_ptr(ptr)) = l_next_ptr(ptr); else free_list = l_next_ptr(ptr); if (l_next_ptr(ptr)) l_prev_ptr(l_next_ptr(ptr)) = l_prev_ptr(ptr); } void add_to_free_list(ptr) u *ptr; { count(large_free_stat, (*ptr & MASK) << 2); if (free_list && l_prev_ptr(free_list)) puts("Free list consistency error."); l_next_ptr(ptr) = free_list; if (free_list) l_prev_ptr(free_list) = ptr; l_prev_ptr(ptr) = 0; free_list = ptr; } build_block(ptr, size) /* build a properly annotated unalloc block */ u *ptr; u size; { *(ptr) = (*ptr & PREV_BLOCK) | size; /* mark this block as free */ *(ptr+size-1) = size; *(ptr+size) &= (MASK | THIS_BLOCK); /* unmark previous block */ } static void mark_block(ptr) /* mark this block as allocated */ u *ptr; { *l_next_block(ptr) |= PREV_BLOCK; *ptr |= THIS_BLOCK; } stat sbrk_stat; static char *esbrk(size) u size; { extern char *sbrk(); char *temp; count(sbrk_stat,size); temp = sbrk(size); if (temp == (char *) -1) { fprintf(stderr, "Error: out of memory; sbrk() returned -1.\n"); exit(1); } return temp; } stat large_alloc_stat; static char *large_malloc(size, force_more) u size; int force_more; { u best_size, real_size; u *first, *best, *ptr; size = (size + 7) >> 2; /* plus overhead */ count(large_alloc_stat, size << 2); first = best = 0; best_size = MASK; if (force_more) ptr = 0; else ptr = free_list; while (ptr) { u tempsize; /* Perfect fit? */ tempsize = *ptr & MASK; if (tempsize == size) { best = first = ptr; break; /* always accept perfect fit */ } /* does it really even fit at all */ if (tempsize >= size + SMALL_BLOCK_MAX + 1) { /* try first fit */ if (!first) { first = ptr; if (fit_style == FIRST_FIT) break; /* just use this one! */ } /* try best fit */ tempsize -= size; if (tempsize>0 && tempsize<=best_size) { best = ptr; best_size = tempsize; } } ptr = l_next_ptr(ptr); } /* end while */ if (fit_style==BEST_FIT) ptr = best; else ptr = first; /* FIRST_FIT and HYBRID both leave it in first */ if (!ptr) /* no match, allocate more memory */ { u chunk_size, block_size; block_size = size*SINT; if (force_more || (block_size>CHUNK_SIZE)) chunk_size = block_size; else chunk_size = CHUNK_SIZE; if (!start_next_block) { start_next_block = (u *) esbrk(SINT); *(start_next_block) = PREV_BLOCK; fake("Allocated little fake block"); } ptr = (u *) esbrk(chunk_size); ptr -= 1; /* overlap old memory block */ block_size = chunk_size / SINT; /* configure header info on chunk */ build_block(ptr,block_size); if (force_more) fake("Build little block"); else fake("Built memory block description."); *l_next_block(ptr)=THIS_BLOCK; add_to_free_list(ptr); } /* end of creating a new chunk */ remove_from_free_list(ptr); real_size = *ptr & MASK; if (real_size != size) { /* split block pointed to by ptr into two blocks */ build_block(ptr+size, real_size-size); fake("Built empty block"); add_to_free_list(ptr+size); build_block(ptr, size); } mark_block(ptr); fake("built allocated block"); return (char *) (ptr + 1); } static void large_free(ptr) char *ptr; { u size, *p; p = (u *) ptr; p-=1; size = *p & MASK; count(large_alloc_stat, - (int) (size << 2)); if (l_next_free(p)) { remove_from_free_list(l_next_block(p)); size += (*l_next_block(p) & MASK); *p = (*p & PREV_BLOCK) | size; } if (l_prev_free(p)) { remove_from_free_list(l_prev_block(p)); size += (*l_prev_block(p) & MASK); p = l_prev_block(p); } build_block(p, size); add_to_free_list(p); } /*char *srealloc(p, size)*/ char *realloc(p, size) char *p; unsigned size; { unsigned *q; char *t; q = (unsigned *) p; --q; if (((*q & MASK)-1)*sizeof(int) >= size) return p; /*t = smalloc(size);*/ t = malloc(size); if (t == 0) return (char *) 0; memcpy(t, p, (*q-1)); /*sfree(p);*/ free(p); return t; } void add_message(); resort_free_list() { return 0; } #define dump_stat(str,stat) add_message(str,stat.counter,stat.size) void dump_malloc_data() { add_message("Type Count Space (bytes)\n"); dump_stat("sbrk requests: %8d %10d (a)\n",sbrk_stat); dump_stat("large blocks: %8d %10d (b)\n",large_alloc_stat); dump_stat("large free blocks: %8d %10d (c)\n\n",large_free_stat); dump_stat("small chunks: %8d %10d (d)\n",small_chunk_stat); dump_stat("small blocks: %8d %10d (e)\n",small_alloc_stat); dump_stat("small free blocks: %8d %10d (f)\n",small_free_stat); add_message( "unused from current chunk %10d (g)\n\n",unused_size<<2); add_message( " Small blocks are stored in small chunks, which are allocated as\n"); add_message( "large blocks. Therefore, the total large blocks allocated (b) plus\n"); add_message( "the large free blocks (c) should equal total storage from sbrk (a).\n"); add_message( "Similarly, (e) + (f) + (g) equals (d). The total amount of storage\n"); add_message( "wasted is (c) + (f) + (g); the amount allocated is (b) - (f) - (g).\n"); } void add_message(va_alist) va_dcl { char *fmt; va_list args; va_start(args); fmt = va_arg(args, char *); vfprintf(stderr, fmt, args); va_end(args); }