Mercurial > repos > rhope

comparison runtime/fixed_alloc.c @ 41:1b86a1ee500a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added faster allocator for small objects
author Mike Pavone <pavone@retrodev.com>
date Sat, 10 Oct 2009 16:40:50 -0400
parents
children a24eb366195c
comparison
equal deleted inserted replaced
40:789a146a48e1 41:1b86a1ee500a
1 #include "fixed_alloc.h"
2 #include <stdlib.h>
3
4 uint16_t max_free[(MAX_SIZE-MIN_SIZE)/STRIDE];
5
6 void fixed_alloc_init()
7 {
8 int i;
9 for(i = 0; i < (MAX_SIZE-MIN_SIZE)/STRIDE; ++i)
10 max_free[i] = (BLOCK_SIZE - sizeof(mem_block)+1)*8/((i*STRIDE+MIN_SIZE)*8+1);
11 }
12
13 mem_manager * new_mem_manager()
14 {
15 int i;
16 mem_manager * ret = malloc(sizeof(mem_manager));
17 memset(ret, 0, sizeof(mem_manager));
18 return ret;
19 }
20
21 void * falloc(size_t size, mem_manager * manager)
22 {
23 uint16_t i,bit;
24 uint16_t bucket;
25 mem_block * block,*temp;
26 if(size > MAX_SIZE)
27 return malloc(size);
28 //puts("falloc");
29 size = ADJUST_SIZE(size);
30 bucket = (size-MIN_SIZE)/STRIDE;
31 block = manager->inuse[bucket];
32 if(!block)
33 {
34 block = manager->freelist;
35 if(block)
36 {
37 --manager->freecount;
38 manager->freelist = block->next;
39 }
40 else
41 {
42 block = block_alloc(BLOCK_SIZE);
43 }
44 manager->inuse[bucket] = block;
45 block->next = NULL;
46 block->last = NULL;
47 block->numfree = max_free[bucket];
48 block->firstfree = 0;
49 memset(block->bitmap, 0xFF, max_free[bucket]/8+1);
50 }
51 //printf("block: %X,numfree: %d, firstfree: %d, maxfree: %d\n", block, block->numfree, block->firstfree, max_free[bucket]);
52 /*if(block->numfree > max_free[bucket])
53 {
54 puts("uh oh!");
55 exit(1);
56 }*/
57 //find first free
58 i = block->firstfree;
59 while(!block->bitmap[i])
60 ++i;
61 //printf("i:%d,bitmap:%X\n", i, block->bitmap[i]);
62 bit = 0;
63 while(!((1 << bit) & block->bitmap[i]))
64 ++bit;
65 //update free bitmask
66 block->bitmap[i] ^= 1 << bit;
67 //If current bitmap has no more free elements, set firstfree to the next bitmap
68 if(!block->bitmap[i])
69 block->firstfree = i+1;
70 else
71 block->firstfree = i;
72 --block->numfree;
73 if(!block->numfree)
74 {
75 //Remove from linked list if there are no more free elements
76 manager->inuse[bucket] = block->next;
77 if(block->next)
78 block->next->last = block->last;
79 }
80 i = i*8+bit;
81 //printf("%X\n", ((char *)block)+BLOCK_SIZE-((i+1)*size));
82 return (void *)(((char *)block)+BLOCK_SIZE-((i+1)*size));
83 }
84
85 void ffree(void * ptr, size_t size, mem_manager * manager)
86 {
87 mem_block * block,*temp;
88 uint16_t i,bit,bucket;
89 if(size > MAX_SIZE)
90 {
91 free(ptr);
92 return;
93 }
94 //puts("ffree");
95 size = ADJUST_SIZE(size);
96 block = GET_BLOCK(ptr);
97 i = (((((char *)block) + BLOCK_SIZE) - ((char *)ptr))/size)-1;
98 bit = i & 0x7;
99 i = (i&0xFFFFFFF8) >> 3;
100 //printf("ptr:%X,block:%X,i:%d,bit:%d\n", ptr,block,bit,i);
101 block->bitmap[i] |= 1 << bit;
102 if(i < block->firstfree)
103 block->firstfree = i;
104 ++block->numfree;
105 bucket = (size-MIN_SIZE)/STRIDE;
106 //printf("numfree:%d,max_free:%d,last:%X,next:%X\n", block->numfree, max_free[bucket], block->last, block->next);
107 /*if(block->numfree > max_free[bucket])
108 {
109 puts("uh oh!");
110 exit(1);
111 }*/
112 if(block->numfree == max_free[bucket])
113 {
114 //Block is now unused, remove it from the inuse list
115 if(block->last)
116 block->last->next = block->next;
117 else
118 manager->inuse[bucket] = block->next;
119 if(block->next)
120 block->next->last = block->last;
121 if(manager->freecount == MAX_FREE)
122 block_free(block, BLOCK_SIZE);
123 else
124 {
125 block->next = manager->freelist;
126 manager->freelist = block;
127 ++manager->freecount;
128 }
129 } else if(block->numfree == 1) {
130 //Block was previously full, add it to the inuse list
131 block->next = manager->inuse[bucket];
132 block->last = NULL;
133 manager->inuse[bucket] = block;
134 if(block->next)
135 block->next->last = block;
136 } else if(block->next && block->next->numfree < block->numfree) {
137 //We want to use more filled blockes before less filled ones
138 //so we can return empty ones to the OS more often
139 //so if we now have more free nodes in this block than the
140 //next one swap them
141 temp = block->next;
142 block->next = temp->next;
143 temp->last = block->last;
144 block->last = temp;
145 temp->next = block;
146 if(block->next)
147 block->next->last = block;
148 if(temp->last)
149 temp->last->next = temp;
150 else
151 manager->inuse[bucket] = temp;
152 }
153 }