Mercurial > cgi-bin > hgwebdir.cgi > VMS > VMS_Implementations > VMS_impls > VMS__MC_shared_impl
view vmalloc.c @ 102:def70e32cf2c
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 |
line source
1 /*
2 * Copyright 2009 OpenSourceCodeStewardshipFoundation.org
3 * Licensed under GNU General Public License version 2
4 *
5 * Author: seanhalle@yahoo.com
6 *
7 * Created on November 14, 2009, 9:07 PM
8 */
10 #include <malloc.h>
11 #include <inttypes.h>
12 #include <stdlib.h>
13 #include <stdio.h>
14 #include <string.h>
15 #include <math.h>
17 #include "VMS.h"
18 #include "Histogram/Histogram.h"
20 //A MallocProlog is a head element if the HigherInMem variable is NULL
21 //A Chunk is free if the prevChunkInFreeList variable is NULL
23 /*
24 * This calculates the container which fits the given size.
25 */
26 inline
27 uint32 getContainer(size_t size)
28 {
29 return (log10(size)-LOG128)/LOG54;
30 }
32 /*
33 * This calculates the size of a given container
34 */
35 inline
36 size_t getContainerSize(uint32 idx)
37 {
38 return pow(CHUNK_INCREASE_RATE,idx)*LOWER_BOUND;
39 }
41 /*
42 * Removes the first chunk of a freeList
43 * The chunk is removed but not set as free. There is no check if
44 * the free list is empty, so make sure this is not the case.
45 */
46 inline
47 MallocProlog *removeChunk(MallocProlog** container)
48 {
49 MallocProlog *removedChunk = *container;
50 *container = removedChunk->nextChunkInFreeList;
52 if(removedChunk->nextChunkInFreeList)
53 removedChunk->nextChunkInFreeList->prevChunkInFreeList =
54 (MallocProlog*)container;
56 return removedChunk;
57 }
59 inline
60 void recycleSmallChunks(MallocProlog** container)
61 {
62 //TODO recycle small chunks
63 }
65 /*
66 * Removes a chunk from a free list.
67 */
68 inline
69 void extractChunk(MallocProlog* chunk)
70 {
71 chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;
72 if(chunk->nextChunkInFreeList)
73 chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;
74 }
76 /*
77 * Merges two chunks.
78 * Chunk A has to be before chunk B in memory. Both have to be removed from
79 * a free list
80 */
81 inline
82 MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB)
83 {
84 chunkA->nextHigherInMem = chunkB->nextHigherInMem;
85 return chunkA;
86 }
87 /*
88 * Inserts a chunk into a free list.
89 */
90 inline
91 void insertChunk(MallocProlog* chunk, MallocProlog** container)
92 {
93 chunk->nextChunkInFreeList = *container;
94 chunk->prevChunkInFreeList = (MallocProlog*)container;
95 if(*container)
96 (*container)->prevChunkInFreeList = chunk;
97 *container = chunk;
98 }
100 /*
101 * Divides the chunk that a new chunk of newSize is created.
102 * There is no size check, so make sure the size value is valid.
103 */
104 inline
105 MallocProlog *divideChunk(MallocProlog* chunk, size_t newSize)
106 {
107 MallocProlog* newChunk = (MallocProlog*)((uintptr_t)chunk->nextHigherInMem -
108 newSize - sizeof(MallocProlog));
110 newChunk->nextLowerInMem = chunk;
111 newChunk->nextHigherInMem = chunk->nextHigherInMem;
113 chunk->nextHigherInMem = newChunk;
114 chunk->nextHigherInMem->nextLowerInMem = newChunk;
116 return newChunk;
117 }
119 inline
120 size_t getChunkSize(MallocProlog* chunk)
121 {
122 return (uintptr_t)chunk->nextHigherInMem -
123 (uintptr_t)chunk - sizeof(MallocProlog);
124 }
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));
136 uint32 containerIdx = getContainer(addedSize)+4;
137 while(freeLists->bigChunks[containerIdx] == NULL )
138 containerIdx++;
140 MallocProlog *foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
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]);
149 }
151 /*
152 * This is sequential code, meant to only be called from the Master, not from
153 * any slave VPs.
154 */
155 void *VMS__malloc( size_t sizeRequested )
156 {
157 //============================= MEASUREMENT STUFF ========================
158 #ifdef MEAS__TIME_MALLOC
159 int32 startStamp, endStamp;
160 saveLowTimeStampCountInto( startStamp );
161 #endif
162 //========================================================================
165 MallocArrays* freeList = _VMSMasterEnv->freeLists;
167 //Return a small chunk if the requested size is smaller than 128B
168 if(sizeRequested <= LOWER_BOUND)
169 {
170 uint32 freeListIdx = (sizeRequested-1)/32;
171 if(freeList->smallChunkCount[freeListIdx] == 0)
172 {
173 makeChunks((freeListIdx+1)*32, &freeList->smallChunks[freeListIdx]);
174 freeList->smallChunkCount[freeListIdx] += 5;
175 }
177 freeList->smallChunkCount[freeListIdx]--;
178 return removeChunk(&freeList->smallChunks[freeListIdx]) + 1;
179 }
181 //Calculate the expected container. Start one higher to have a Chunk that's
182 //always big enough.
183 uint32 targetContainerIdx = getContainer(sizeRequested);
184 uint32 containerIdx = targetContainerIdx + 1;
186 MallocProlog* foundChunk;
187 if(freeList->bigChunks[containerIdx] == NULL)
188 {
189 while(freeList->bigChunks[containerIdx] == NULL)
190 {
191 containerIdx++;
192 if(containerIdx >= freeList->containerCount)
193 {
194 printf("VMS malloc failed: low memory");
195 exit(1);
196 }
197 }
199 foundChunk = removeChunk(&freeList->bigChunks[containerIdx]);
200 size_t chunkSize = getChunkSize(foundChunk);
202 if(chunkSize > sizeRequested + sizeof(MallocProlog))
203 {
204 MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);
205 containerIdx = getContainer(chunkSize - sizeRequested - sizeof(MallocProlog));
206 insertChunk(foundChunk,&freeList->bigChunks[containerIdx]);
207 foundChunk = newChunk;
208 }
209 }
210 else
211 {
212 foundChunk = removeChunk(&freeList->bigChunks[containerIdx]);
213 }
215 //Mark as allocated
216 foundChunk->prevChunkInFreeList = NULL;
218 //============================= MEASUREMENT STUFF ========================
219 #ifdef MEAS__TIME_MALLOC
220 saveLowTimeStampCountInto( endStamp );
221 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
222 #endif
223 //========================================================================
225 //skip over the prolog by adding its size to the pointer return
226 return foundChunk + 1;
227 }
229 /*
230 * This is sequential code, meant to only be called from the Master, not from
231 * any slave VPs.
232 */
233 void
234 VMS__free( void *ptrToFree )
235 {
237 //============================= MEASUREMENT STUFF ========================
238 #ifdef MEAS__TIME_MALLOC
239 int32 startStamp, endStamp;
240 saveLowTimeStampCountInto( startStamp );
241 #endif
242 //========================================================================
244 MallocArrays* freeLists = _VMSMasterEnv->freeLists;
245 MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1;
246 uint32 containerIdx;
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]++;
255 if(freeLists->smallChunkCount[containerIdx] > 20)
256 recycleSmallChunks(&freeLists->smallChunks[containerIdx]);
258 return;
259 }
261 //Check for free neighbors
262 if(chunkToFree->nextLowerInMem)
263 {
264 if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)
265 {//Chunk is not allocated
266 if(getChunkSize(chunkToFree->nextLowerInMem) > LOWER_BOUND)
267 {
268 extractChunk(chunkToFree->nextLowerInMem);
269 chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);
270 }
271 }
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 }
285 containerIdx = getContainer(chunkSize);
286 insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);
288 //============================= MEASUREMENT STUFF ========================
289 #ifdef MEAS__TIME_MALLOC
290 saveLowTimeStampCountInto( endStamp );
291 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist );
292 #endif
293 //========================================================================
295 }
298 /*Allocates memory from the external system -- higher overhead
299 *
300 *Because of Linux's malloc throwing bizarre random faults when malloc is
301 * used inside a VMS virtual processor, have to pass this as a request and
302 * have the core loop do it when it gets around to it -- will look for these
303 * chores leftover from the previous animation of masterVP the next time it
304 * goes to animate the masterVP -- so it takes two separate masterVP
305 * animations, separated by work, to complete an external malloc or
306 * external free request.
307 *
308 *Thinking core loop accepts signals -- just looks if signal-location is
309 * empty or not --
310 */
311 void *
312 VMS__malloc_in_ext( size_t sizeRequested )
313 {
314 /*
315 //This is running in the master, so no chance for multiple cores to be
316 // competing for the core's flag.
317 if( *(_VMSMasterEnv->coreLoopSignalAddr[ 0 ]) != 0 )
318 { //something has already signalled to core loop, so save the signal
319 // and look, next time master animated, to see if can send it.
320 //Note, the addr to put a signal is in the coreloop's frame, so just
321 // checks it each time through -- make it volatile to avoid GCC
322 // optimizations -- it's a coreloop local var that only changes
323 // after jumping away. The signal includes the addr to send the
324 //return to -- even if just empty return completion-signal
325 //
326 //save the signal in some queue that the master looks at each time
327 // it starts up -- one loc says if empty for fast common case --
328 //something like that -- want to hide this inside this call -- but
329 // think this has to come as a request -- req handler gives procr
330 // back to master loop, which gives it back to req handler at point
331 // it sees that core loop has sent return signal. Something like
332 // that.
333 saveTheSignal
335 }
336 coreSigData->type = malloc;
337 coreSigData->sizeToMalloc = sizeRequested;
338 coreSigData->locToSignalCompletion = &figureOut;
339 _VMSMasterEnv->coreLoopSignals[ 0 ] = coreSigData;
340 */
341 //just risk system-stack faults until get this figured out
342 return malloc( sizeRequested );
343 }
346 /*Frees memory that was allocated in the external system -- higher overhead
347 *
348 *As noted in external malloc comment, this is clunky 'cause the free has
349 * to be called in the core loop.
350 */
351 void
352 VMS__free_in_ext( void *ptrToFree )
353 {
354 //just risk system-stack faults until get this figured out
355 free( ptrToFree );
357 //TODO: fix this -- so
358 }
361 /*Designed to be called from the main thread outside of VMS, during init
362 */
363 MallocArrays *
364 VMS_ext__create_free_list()
365 {
366 //Initialize containers for small chunks and fill with zeros
367 _VMSMasterEnv->freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) );
368 MallocArrays *freeLists = _VMSMasterEnv->freeLists;
370 freeLists->smallChunks =
371 (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
372 memset((void*)freeLists->smallChunks,
373 0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
374 memset((void*)freeLists->smallChunkCount,
375 0,SMALL_CHUNK_COUNT*sizeof(uint32));
377 //Calculate number of containers for big chunks
378 uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;
379 freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*));
380 memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*));
381 freeLists->containerCount = container;
383 //Create first element in lastContainer
384 MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
385 if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);}
386 freeLists->memSpace = firstChunk;
388 firstChunk->nextLowerInMem = NULL;
389 firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk +
390 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog*));
391 firstChunk->nextChunkInFreeList = NULL;
392 //previous element in the queue is the container
393 firstChunk->prevChunkInFreeList = freeLists->bigChunks[container-1];
395 freeLists->bigChunks[container-1] = firstChunk;
397 //Create dummy chunk to mark the top of stack this is of course
398 //never freed
399 MallocProlog *dummyChunk = firstChunk->nextHigherInMem;
400 dummyChunk->nextHigherInMem = dummyChunk+1;
401 dummyChunk->nextLowerInMem = NULL;
402 dummyChunk->nextChunkInFreeList = NULL;
403 dummyChunk->prevChunkInFreeList = NULL;
405 return freeLists;
406 }
409 /*Designed to be called from the main thread outside of VMS, during cleanup
410 */
411 void
412 VMS_ext__free_free_list( MallocArrays *freeLists )
413 {
414 free(freeLists->memSpace);
415 free(freeLists->bigChunks);
416 free(freeLists->smallChunks);
418 }