Mercurial > cgi-bin > hgwebdir.cgi > VMS > VMS_Implementations > VMS_impls > VMS__MC_shared_impl

comparison vmalloc.c @ 102:def70e32cf2c

find changesets by author, revision, files, or words in the commit message
Malloc with easy shave off
author Merten Sach <msach@mailbox.tu-berlin.de>
date Wed, 03 Aug 2011 13:23:32 +0200
parents ca154ebe2b6c
children 62c59f2ac9f1
comparison
equal deleted inserted replaced
13:07daf0c09527 14:533fe4146879
15 #include <math.h> 15 #include <math.h>
16 16
17 #include "VMS.h" 17 #include "VMS.h"
18 #include "Histogram/Histogram.h" 18 #include "Histogram/Histogram.h"
19 19
20 //A MallocProlog is a head element if the HigherInMem variable is NULL
21 //A Chunk is free if the prevChunkInFreeList variable is NULL
22
20 /* 23 /*
21 * This calculates the container which fits the given size. 24 * This calculates the container which fits the given size.
22 */ 25 */
23 inline 26 inline
24 uint32 getContainer(size_t size) 27 uint32 getContainer(size_t size)
25 { 28 {
26 return floor((log10(size)-LOG128)/LOG54); 29 return (log10(size)-LOG128)/LOG54;
27 } 30 }
28 31
29 /* 32 /*
30 * This calculates the size of a given container 33 * This calculates the size of a given container
31 */ 34 */
51 (MallocProlog*)container; 54 (MallocProlog*)container;
52 55
53 return removedChunk; 56 return removedChunk;
54 } 57 }
55 58
59 inline
60 void recycleSmallChunks(MallocProlog** container)
61 {
62 //TODO recycle small chunks
63 }
64
56 /* 65 /*
57 * Removes a chunk from a free list. 66 * Removes a chunk from a free list.
58 */ 67 */
59 inline 68 inline
60 MallocProlog *extractChunk(MallocProlog* chunk) 69 void extractChunk(MallocProlog* chunk)
61 { 70 {
62 71 chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;
72 if(chunk->nextChunkInFreeList)
73 chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;
63 } 74 }
64 75
65 /* 76 /*
66 * Merges two chunks. 77 * Merges two chunks.
67 * Chunk A has to be before chunk B in memory. 78 * Chunk A has to be before chunk B in memory. Both have to be removed from
79 * a free list
68 */ 80 */
69 inline 81 inline
70 MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB) 82 MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB)
71 { 83 {
72 84 chunkA->nextHigherInMem = chunkB->nextHigherInMem;
85 return chunkA;
73 } 86 }
74 /* 87 /*
75 * Inserts a chunk into a free list. 88 * Inserts a chunk into a free list.
76 */ 89 */
77 inline 90 inline
106 inline 119 inline
107 size_t getChunkSize(MallocProlog* chunk) 120 size_t getChunkSize(MallocProlog* chunk)
108 { 121 {
109 return (uintptr_t)chunk->nextHigherInMem - 122 return (uintptr_t)chunk->nextHigherInMem -
110 (uintptr_t)chunk - sizeof(MallocProlog); 123 (uintptr_t)chunk - sizeof(MallocProlog);
124 }
125
126
127 /*
128 * This makes 5 Chunks of the requested size.
129 */
130 inline
131 void makeChunks(size_t size, MallocProlog **container)
132 {
133 MallocArrays *freeLists = _VMSMasterEnv->freeLists;
134 size_t addedSize = 5*(size + sizeof(MallocProlog));
135
136 uint32 containerIdx = getContainer(addedSize)+4;
137 while(freeLists->bigChunks[containerIdx] == NULL )
138 containerIdx++;
139
140 MallocProlog *foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
141
142 int i;
143 for(i=0; i<5; i++)
144 {
145 insertChunk(divideChunk(foundChunk,size), container);
146 }
147 containerIdx = getContainer(getChunkSize(foundChunk));
148 insertChunk(foundChunk, &freeLists->bigChunks[containerIdx]);
111 } 149 }
112 150
113 /* 151 /*
114 * This is sequential code, meant to only be called from the Master, not from 152 * This is sequential code, meant to only be called from the Master, not from
115 * any slave VPs. 153 * any slave VPs.
121 int32 startStamp, endStamp; 159 int32 startStamp, endStamp;
122 saveLowTimeStampCountInto( startStamp ); 160 saveLowTimeStampCountInto( startStamp );
123 #endif 161 #endif
124 //======================================================================== 162 //========================================================================
125 163
164
126 MallocArrays* freeList = _VMSMasterEnv->freeLists; 165 MallocArrays* freeList = _VMSMasterEnv->freeLists;
127 166
128 //Return a small chunk if the requested size is smaller than 128B 167 //Return a small chunk if the requested size is smaller than 128B
129 //TODO: for now set size to 129B 168 if(sizeRequested <= LOWER_BOUND)
130 if(sizeRequested < 128) 169 {
131 sizeRequested = 129; 170 uint32 freeListIdx = (sizeRequested-1)/32;
132 171 if(freeList->smallChunkCount[freeListIdx] == 0)
172 {
173 makeChunks((freeListIdx+1)*32, &freeList->smallChunks[freeListIdx]);
174 freeList->smallChunkCount[freeListIdx] += 5;
175 }
176
177 freeList->smallChunkCount[freeListIdx]--;
178 return removeChunk(&freeList->smallChunks[freeListIdx]) + 1;
179 }
180
133 //Calculate the expected container. Start one higher to have a Chunk that's 181 //Calculate the expected container. Start one higher to have a Chunk that's
134 //always big enough. 182 //always big enough.
135 uint32 targetContainerIdx = getContainer(sizeRequested); 183 uint32 targetContainerIdx = getContainer(sizeRequested);
136 uint32 containerIdx = targetContainerIdx + 1; 184 uint32 containerIdx = targetContainerIdx + 1;
137 185
139 if(freeList->bigChunks[containerIdx] == NULL) 187 if(freeList->bigChunks[containerIdx] == NULL)
140 { 188 {
141 while(freeList->bigChunks[containerIdx] == NULL) 189 while(freeList->bigChunks[containerIdx] == NULL)
142 { 190 {
143 containerIdx++; 191 containerIdx++;
144 if(containerIdx > freeList->containerCount) 192 if(containerIdx >= freeList->containerCount)
145 { 193 {
146 printf("VMS malloc failed: low memory"); 194 printf("VMS malloc failed: low memory");
147 exit(1); 195 exit(1);
148 } 196 }
149 } 197 }
150 198
151 foundChunk = removeChunk(&freeList->bigChunks[containerIdx]); 199 foundChunk = removeChunk(&freeList->bigChunks[containerIdx]);
152 //Found bigger Element, so we have to divide until it fits the
153 //requested size
154 containerIdx--;
155 size_t containerSize = getContainerSize(containerIdx);
156 size_t chunkSize = getChunkSize(foundChunk); 200 size_t chunkSize = getChunkSize(foundChunk);
157 201
158 while(containerIdx > targetContainerIdx) 202 if(chunkSize > sizeRequested + sizeof(MallocProlog))
159 { 203 {
160 if(chunkSize > containerSize + sizeRequested + sizeof(MallocProlog)) 204 MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);
161 { 205 containerIdx = getContainer(chunkSize - sizeRequested - sizeof(MallocProlog));
162 MallocProlog *newChunk = divideChunk(foundChunk,containerSize); 206 insertChunk(foundChunk,&freeList->bigChunks[containerIdx]);
163 insertChunk(newChunk,&freeList->bigChunks[containerIdx]); 207 foundChunk = newChunk;
164 chunkSize = getChunkSize(foundChunk); 208 }
165 }
166 containerIdx--;
167 containerSize /= CHUNK_INCREASE_RATE;
168 }
169 } 209 }
170 else 210 else
171 { 211 {
172 foundChunk = removeChunk(&freeList->bigChunks[containerIdx]); 212 foundChunk = removeChunk(&freeList->bigChunks[containerIdx]);
173 } 213 }
179 #ifdef MEAS__TIME_MALLOC 219 #ifdef MEAS__TIME_MALLOC
180 saveLowTimeStampCountInto( endStamp ); 220 saveLowTimeStampCountInto( endStamp );
181 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist ); 221 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
182 #endif 222 #endif
183 //======================================================================== 223 //========================================================================
184 224
185 //skip over the prolog by adding its size to the pointer return 225 //skip over the prolog by adding its size to the pointer return
186 return (void*)((uintptr_t)foundChunk + sizeof(MallocProlog)); 226 return foundChunk + 1;
187 } 227 }
188 228
189 /* 229 /*
190 * This is sequential code, meant to only be called from the Master, not from 230 * This is sequential code, meant to only be called from the Master, not from
191 * any slave VPs. 231 * any slave VPs.
199 int32 startStamp, endStamp; 239 int32 startStamp, endStamp;
200 saveLowTimeStampCountInto( startStamp ); 240 saveLowTimeStampCountInto( startStamp );
201 #endif 241 #endif
202 //======================================================================== 242 //========================================================================
203 243
204 MallocArrays* freeList = _VMSMasterEnv->freeLists; 244 MallocArrays* freeLists = _VMSMasterEnv->freeLists;
205 MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1; 245 MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1;
246 uint32 containerIdx;
247
248 size_t chunkSize = getChunkSize(chunkToFree);
249 if(chunkSize <= LOWER_BOUND)
250 {
251 containerIdx = (chunkSize-1)/32;
252 insertChunk(chunkToFree,&freeLists->smallChunks[containerIdx]);
253 freeLists->smallChunkCount[containerIdx]++;
254
255 if(freeLists->smallChunkCount[containerIdx] > 20)
256 recycleSmallChunks(&freeLists->smallChunks[containerIdx]);
257
258 return;
259 }
206 260
207 //Check for free neighbors 261 //Check for free neighbors
208 if(chunkToFree->nextLowerInMem) 262 if(chunkToFree->nextLowerInMem)
209 { 263 {
210 if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL) 264 if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)
211 {//Chunk is not allocated 265 {//Chunk is not allocated
212 mergeChunks() 266 if(getChunkSize(chunkToFree->nextLowerInMem) > LOWER_BOUND)
267 {
268 extractChunk(chunkToFree->nextLowerInMem);
269 chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);
270 }
213 } 271 }
214 } 272 }
273 if(chunkToFree->nextHigherInMem)
274 {
275 if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL)
276 {//Chunk is not allocated
277 if(getChunkSize(chunkToFree->nextHigherInMem) > LOWER_BOUND)
278 {
279 extractChunk(chunkToFree->nextHigherInMem);
280 chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem);
281 }
282 }
283 }
284
285 containerIdx = getContainer(chunkSize);
286 insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);
287
215 //============================= MEASUREMENT STUFF ======================== 288 //============================= MEASUREMENT STUFF ========================
216 #ifdef MEAS__TIME_MALLOC 289 #ifdef MEAS__TIME_MALLOC
217 saveLowTimeStampCountInto( endStamp ); 290 saveLowTimeStampCountInto( endStamp );
218 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist ); 291 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist );
219 #endif 292 #endif
296 369
297 freeLists->smallChunks = 370 freeLists->smallChunks =
298 (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*)); 371 (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
299 memset((void*)freeLists->smallChunks, 372 memset((void*)freeLists->smallChunks,
300 0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*)); 373 0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
374 memset((void*)freeLists->smallChunkCount,
375 0,SMALL_CHUNK_COUNT*sizeof(uint32));
301 376
302 //Calculate number of containers for big chunks 377 //Calculate number of containers for big chunks
303 uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1; 378 uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;
304
305 freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*)); 379 freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*));
306 memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*)); 380 memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*));
307 freeLists->containerCount = container; 381 freeLists->containerCount = container;
308 382
309 //Create first element in lastContainer 383 //Create first element in lastContainer
310 MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE ); 384 MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
311 if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);} 385 if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);}
386 freeLists->memSpace = firstChunk;
312 387
313 firstChunk->nextLowerInMem = NULL; 388 firstChunk->nextLowerInMem = NULL;
314 firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk + 389 firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk +
315 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog*)); 390 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog*));
316 firstChunk->nextChunkInFreeList = NULL; 391 firstChunk->nextChunkInFreeList = NULL;
332 407
333 408
334 /*Designed to be called from the main thread outside of VMS, during cleanup 409 /*Designed to be called from the main thread outside of VMS, during cleanup
335 */ 410 */
336 void 411 void
337 VMS_ext__free_free_list( MallocProlog *freeListHead ) 412 VMS_ext__free_free_list( MallocArrays *freeLists )
338 { 413 {
339 //stashed a ptr to the one and only bug chunk malloc'd from OS in the 414 free(freeLists->memSpace);
340 // free list head's next lower in mem pointer 415 free(freeLists->bigChunks);
341 free( freeListHead->nextLowerInMem ); 416 free(freeLists->smallChunks);
342 417
343 //don't free the head -- it'll be in an array eventually -- free whole 418 }
344 // array when all the free lists linked from it have already been freed 419
345 }
346