Mercurial > repos > rhope

annotate runtime/fixed_alloc.c @ 177:e57c151f351e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Get bytecode engine working well enough for naive fib
author Mike Pavone <pavone@retrodev.com>
date Sun, 12 Jun 2011 03:49:51 -0700
parents 72c648bca43b
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
41
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
1 #include "fixed_alloc.h"
105
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
2 #include "object.h"
67
d1569087348f Some small optimizations
Mike Pavone <pavone@retrodev.com>
parents: 49
diff changeset
3 #include <stdlib.h>
48
a24eb366195c Fixed some bugs introduced in previous commit and moved definition of integer methods out of runtime and into the compiler
Mike Pavone <pavone@retrodev.com>
parents: 41
diff changeset
4 #include <string.h>
89
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
5 #include <stdio.h>
41
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
6
92
e73a93fb5de1 Beginning of port of compiler to itself, some bugfixes and a refcount optimization
Mike Pavone <pavone@retrodev.com>
parents: 89
diff changeset
7 uint16_t max_free[(MAX_SIZE-MIN_SIZE)/STRIDE+1];
41
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
8
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
9 void fixed_alloc_init()
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
10 {
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
11 int i;
92
e73a93fb5de1 Beginning of port of compiler to itself, some bugfixes and a refcount optimization
Mike Pavone <pavone@retrodev.com>
parents: 89
diff changeset
12 for(i = 0; i < ((MAX_SIZE-MIN_SIZE)/STRIDE+1); ++i)
41
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
13 max_free[i] = (BLOCK_SIZE - sizeof(mem_block)+1)*8/((i*STRIDE+MIN_SIZE)*8+1);
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
14 }
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
15
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
16 mem_manager * new_mem_manager()
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
17 {
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
18 int i;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
19 mem_manager * ret = malloc(sizeof(mem_manager));
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
20 memset(ret, 0, sizeof(mem_manager));
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
21 return ret;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
22 }
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
23
89
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
24 void print_mem_info(mem_manager * manager)
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
25 {
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
26 int i,count,freeobjs;
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
27 mem_block * cur;
105
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
28 //printf("Free blocks: %d\n", manager->freecount);
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
29 if (manager->fullcount)
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
30 printf("Full Blocks: %d\n", manager->fullcount);
89
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
31 for (i = 0; i < (MAX_SIZE-MIN_SIZE)/STRIDE; i++)
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
32 {
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
33 count = 0;
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
34 freeobjs = 0;
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
35 cur = manager->inuse[i];
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
36 while(cur)
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
37 {
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
38 count++;
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
39 freeobjs += ((int)cur->numfree);
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
40 cur = cur->next;
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
41 }
105
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
42 if (freeobjs)
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
43 printf("Bucket %d(size: %d) has %d blocks in use with %d free slots out of %d\n", i, i*STRIDE+MIN_SIZE,count, freeobjs, max_free[i]*count);
89
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
44 }
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
45 fflush(stdout);
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
46 }
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
47
119
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
48 void find_live_objects_oftype(mem_manager * manager, int32_t type_id, void ** output)
105
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
49 {
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
50 object * obj;
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
51 mem_block * cur;
119
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
52 int32_t i,j,bitslots,bit,outpos=0;
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
53 for (i = 0; i < (MAX_SIZE-MIN_SIZE)/STRIDE; i++)
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
54 {
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
55 cur = manager->inuse[i];
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
56 while(cur)
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
57 {
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
58 bitslots = max_free[i]/8;
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
59 if(max_free[i]&7)
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
60 ++bitslots;
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
61 for(j = 0; j < bitslots; ++j)
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
62 if(cur->bitmap[j] != 0xFF)
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
63 {
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
64 for (bit = 0; bit < 8; ++bit)
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
65 {
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
66 if (!(cur->bitmap[j] & (1 << bit)))
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
67 {
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
68 obj = (object *)(((char *)cur)+BLOCK_SIZE-(((j*8+bit)+1)*(i*STRIDE+MIN_SIZE)));
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
69 if(obj->bprint->type_id == type_id)
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
70 output[outpos++] = obj;
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
71 }
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
72 }
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
73 }
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
74 cur = cur->next;
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
75 }
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
76 }
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
77 }
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
78
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
79 void get_live_object_counts(mem_manager * manager, int32_t * counts)
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
80 {
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
81 object * obj;
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
82 mem_block * cur;
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
83 int32_t i,j,bitslots,bit;
105
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
84 memset(counts, 0, sizeof(int32_t)*max_registered_type);
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
85 for (i = 0; i < (MAX_SIZE-MIN_SIZE)/STRIDE; i++)
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
86 {
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
87 cur = manager->inuse[i];
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
88 while(cur)
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
89 {
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
90 bitslots = max_free[i]/8;
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
91 if(max_free[i]&7)
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
92 ++bitslots;
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
93 for(j = 0; j < bitslots; ++j)
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
94 if(cur->bitmap[j] != 0xFF)
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
95 {
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
96 for (bit = 0; bit < 8; ++bit)
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
97 {
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
98 if (!(cur->bitmap[j] & (1 << bit)))
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
99 {
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
100 obj = (object *)(((char *)cur)+BLOCK_SIZE-(((j*8+bit)+1)*(i*STRIDE+MIN_SIZE)));
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
101 counts[obj->bprint->type_id]++;
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
102 }
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
103 }
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
104 }
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
105 cur = cur->next;
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
106 }
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
107 }
119
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
108 }
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
109
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
110 void print_live_object_types(mem_manager * manager)
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
111 {
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
112 int32_t i,*counts = malloc(sizeof(int32_t)*max_registered_type);
72c648bca43b Improved memory debug output and fixed memory leak in Array
Mike Pavone <pavone@retrodev.com>
parents: 105
diff changeset
113 get_live_object_counts(manager, counts);
105
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
114 for (i = 0; i < max_registered_type; ++i)
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
115 if(counts[i])
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
116 printf("%d live objects of type %d\n", counts[i], i);
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
117 fflush(stdout);
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
118 }
43cc42df26cc Various compiler improvements
Mike Pavone <pavone@retrodev.com>
parents: 92
diff changeset
119
41
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
120 void * falloc(size_t size, mem_manager * manager)
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
121 {
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
122 uint16_t i,bit;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
123 uint16_t bucket;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
124 mem_block * block,*temp;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
125 if(size > MAX_SIZE)
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
126 return malloc(size);
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
127 //puts("falloc");
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
128 size = ADJUST_SIZE(size);
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
129 bucket = (size-MIN_SIZE)/STRIDE;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
130 block = manager->inuse[bucket];
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
131 if(!block)
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
132 {
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
133 block = manager->freelist;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
134 if(block)
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
135 {
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
136 --manager->freecount;
67
d1569087348f Some small optimizations
Mike Pavone <pavone@retrodev.com>
parents: 49
diff changeset
137 manager->freelist = block->next;
d1569087348f Some small optimizations
Mike Pavone <pavone@retrodev.com>
parents: 49
diff changeset
138 //memset(block, 0xCD, BLOCK_SIZE);
41
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
139 }
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
140 else
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
141 {
67
d1569087348f Some small optimizations
Mike Pavone <pavone@retrodev.com>
parents: 49
diff changeset
142 block = block_alloc(BLOCK_SIZE);
d1569087348f Some small optimizations
Mike Pavone <pavone@retrodev.com>
parents: 49
diff changeset
143 //memset(block, 0xAB, BLOCK_SIZE);
41
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
144 }
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
145 manager->inuse[bucket] = block;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
146 block->next = NULL;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
147 block->last = NULL;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
148 block->numfree = max_free[bucket];
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
149 block->firstfree = 0;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
150 memset(block->bitmap, 0xFF, max_free[bucket]/8+1);
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
151 }
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
152 //printf("block: %X,numfree: %d, firstfree: %d, maxfree: %d\n", block, block->numfree, block->firstfree, max_free[bucket]);
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
153 /*if(block->numfree > max_free[bucket])
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
154 {
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
155 puts("uh oh!");
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
156 exit(1);
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
157 }*/
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
158 //find first free
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
159 i = block->firstfree;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
160 while(!block->bitmap[i])
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
161 ++i;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
162 //printf("i:%d,bitmap:%X\n", i, block->bitmap[i]);
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
163 bit = 0;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
164 while(!((1 << bit) & block->bitmap[i]))
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
165 ++bit;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
166 //update free bitmask
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
167 block->bitmap[i] ^= 1 << bit;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
168 //If current bitmap has no more free elements, set firstfree to the next bitmap
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
169 if(!block->bitmap[i])
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
170 block->firstfree = i+1;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
171 else
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
172 block->firstfree = i;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
173 --block->numfree;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
174 if(!block->numfree)
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
175 {
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
176 //Remove from linked list if there are no more free elements
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
177 manager->inuse[bucket] = block->next;
89
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
178 manager->fullcount++;
41
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
179 if(block->next)
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
180 block->next->last = block->last;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
181 }
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
182 i = i*8+bit;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
183 return (void *)(((char *)block)+BLOCK_SIZE-((i+1)*size));
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
184 }
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
185
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
186 void ffree(void * ptr, size_t size, mem_manager * manager)
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
187 {
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
188 mem_block * block,*temp;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
189 uint16_t i,bit,bucket;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
190 if(size > MAX_SIZE)
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
191 {
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
192 free(ptr);
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
193 return;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
194 }
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
195 //puts("ffree");
67
d1569087348f Some small optimizations
Mike Pavone <pavone@retrodev.com>
parents: 49
diff changeset
196 size = ADJUST_SIZE(size);
d1569087348f Some small optimizations
Mike Pavone <pavone@retrodev.com>
parents: 49
diff changeset
197 //memset(ptr, 0xEF, size);
41
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
198 block = GET_BLOCK(ptr);
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
199 i = (((((char *)block) + BLOCK_SIZE) - ((char *)ptr))/size)-1;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
200 bit = i & 0x7;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
201 i = (i&0xFFFFFFF8) >> 3;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
202 //printf("ptr:%X,block:%X,i:%d,bit:%d\n", ptr,block,bit,i);
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
203 block->bitmap[i] |= 1 << bit;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
204 if(i < block->firstfree)
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
205 block->firstfree = i;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
206 ++block->numfree;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
207 bucket = (size-MIN_SIZE)/STRIDE;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
208 //printf("numfree:%d,max_free:%d,last:%X,next:%X\n", block->numfree, max_free[bucket], block->last, block->next);
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
209 /*if(block->numfree > max_free[bucket])
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
210 {
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
211 puts("uh oh!");
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
212 exit(1);
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
213 }*/
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
214 if(block->numfree == max_free[bucket])
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
215 {
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
216 //Block is now unused, remove it from the inuse list
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
217 if(block->last)
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
218 block->last->next = block->next;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
219 else
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
220 manager->inuse[bucket] = block->next;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
221 if(block->next)
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
222 block->next->last = block->last;
67
d1569087348f Some small optimizations
Mike Pavone <pavone@retrodev.com>
parents: 49
diff changeset
223 if(manager->freecount == MAX_FREE)
49
3e20ed8959c4 Added initial FFI implementation, Array type and 64-bit integers
Mike Pavone <pavone@retrodev.com>
parents: 48
diff changeset
224 {
67
d1569087348f Some small optimizations
Mike Pavone <pavone@retrodev.com>
parents: 49
diff changeset
225 block_free(block, BLOCK_SIZE);
49
3e20ed8959c4 Added initial FFI implementation, Array type and 64-bit integers
Mike Pavone <pavone@retrodev.com>
parents: 48
diff changeset
226 }
41
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
227 else
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
228 {
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
229 block->next = manager->freelist;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
230 manager->freelist = block;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
231 ++manager->freecount;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
232 }
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
233 } else if(block->numfree == 1) {
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
234 //Block was previously full, add it to the inuse list
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
235 block->next = manager->inuse[bucket];
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
236 block->last = NULL;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
237 manager->inuse[bucket] = block;
89
5a195ee08eac Fix memory leak and bug that was preventing First@Dictionary from working properly
Mike Pavone <pavone@retrodev.com>
parents: 67
diff changeset
238 manager->fullcount--;
41
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
239 if(block->next)
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
240 block->next->last = block;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
241 } else if(block->next && block->next->numfree < block->numfree) {
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
242 //We want to use more filled blockes before less filled ones
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
243 //so we can return empty ones to the OS more often
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
244 //so if we now have more free nodes in this block than the
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
245 //next one swap them
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
246 temp = block->next;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
247 block->next = temp->next;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
248 temp->last = block->last;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
249 block->last = temp;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
250 temp->next = block;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
251 if(block->next)
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
252 block->next->last = block;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
253 if(temp->last)
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
254 temp->last->next = temp;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
255 else
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
256 manager->inuse[bucket] = temp;
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
257 }
1b86a1ee500a Added faster allocator for small objects
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
258 }