Mercurial > cgi-bin > hgwebdir.cgi > VMS > VMS_Implementations > VMS_impls > VMS__MC_shared_impl
view vmalloc.c @ 115:62c59f2ac9f1
first changes malloc
| author | Merten Sach <msach@mailbox.tu-berlin.de> |
|---|---|
| date | Thu, 25 Aug 2011 16:32:13 +0200 |
| parents | def70e32cf2c |
| children | 35547e66b971 |
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 #define MAX_UINT64 0xFFFFFFFFFFFFFFFF
22 //A MallocProlog is a head element if the HigherInMem variable is NULL
23 //A Chunk is free if the prevChunkInFreeList variable is NULL
25 /*
26 * This calculates the container which fits the given size.
27 */
28 inline
29 uint32 getContainer(size_t size)
30 {
31 return (log10(size)-LOG128)/LOG54;
32 }
34 /*
35 * This calculates the size of a given container
36 */
37 inline
38 size_t getContainerSize(uint32 idx)
39 {
40 return pow(CHUNK_INCREASE_RATE,idx)*LOWER_BOUND;
41 }
43 /*
44 * Removes the first chunk of a freeList
45 * The chunk is removed but not set as free. There is no check if
46 * the free list is empty, so make sure this is not the case.
47 */
48 inline
49 MallocProlog *removeChunk(MallocProlog** container)
50 {
51 MallocProlog *removedChunk = *container;
52 *container = removedChunk->nextChunkInFreeList;
54 if(removedChunk->nextChunkInFreeList)
55 removedChunk->nextChunkInFreeList->prevChunkInFreeList =
56 (MallocProlog*)container;
58 return removedChunk;
59 }
61 inline
62 void recycleSmallChunks(MallocProlog** container)
63 {
64 //TODO recycle small chunks
65 }
67 /*
68 * Removes a chunk from a free list.
69 */
70 inline
71 void extractChunk(MallocProlog* chunk, MallocArrays *freeLists)
72 {
73 chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;
74 if(chunk->nextChunkInFreeList)
75 chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;
76 if(*(chunk->prevChunkInFreeList) == NULL)
77 {
78 uint32 containerIdx = (uintptr_t)(chunk->prevChunkInFreeList - freeLists->bigChunks) / sizeof(MallocProlog*);
79 freeLists->bigChunksSearchVector &= ~(1 << containerIdx);
80 }
81 }
83 /*
84 * Merges two chunks.
85 * Chunk A has to be before chunk B in memory. Both have to be removed from
86 * a free list
87 */
88 inline
89 MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB)
90 {
91 chunkA->nextHigherInMem = chunkB->nextHigherInMem;
92 return chunkA;
93 }
94 /*
95 * Inserts a chunk into a free list.
96 */
97 inline
98 void insertChunk(MallocProlog* chunk, MallocProlog** container)
99 {
100 chunk->nextChunkInFreeList = *container;
101 chunk->prevChunkInFreeList = (MallocProlog*)container;
102 if(*container)
103 (*container)->prevChunkInFreeList = chunk;
104 *container = chunk;
105 }
107 /*
108 * Divides the chunk that a new chunk of newSize is created.
109 * There is no size check, so make sure the size value is valid.
110 */
111 inline
112 MallocProlog *divideChunk(MallocProlog* chunk, size_t newSize)
113 {
114 MallocProlog* newChunk = (MallocProlog*)((uintptr_t)chunk->nextHigherInMem -
115 newSize - sizeof(MallocProlog));
117 newChunk->nextLowerInMem = chunk;
118 newChunk->nextHigherInMem = chunk->nextHigherInMem;
120 chunk->nextHigherInMem = newChunk;
121 chunk->nextHigherInMem->nextLowerInMem = newChunk;
123 return newChunk;
124 }
126 inline
127 size_t getChunkSize(MallocProlog* chunk)
128 {
129 return (uintptr_t)chunk->nextHigherInMem -
130 (uintptr_t)chunk - sizeof(MallocProlog);
131 }
134 /*
135 * This makes 5 Chunks of the requested size.
136 */
137 inline
138 void makeChunks(size_t size, MallocProlog **container)
139 {
140 MallocArrays *freeLists = _VMSMasterEnv->freeLists;
141 size_t addedSize = 5*(size + sizeof(MallocProlog));
143 uint32 containerIdx = getContainer(addedSize)+4;
144 while(freeLists->bigChunks[containerIdx] == NULL )
145 containerIdx++;
147 MallocProlog *foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
149 int i;
150 for(i=0; i<5; i++)
151 {
152 insertChunk(divideChunk(foundChunk,size), container);
153 }
154 containerIdx = getContainer(getChunkSize(foundChunk));
155 insertChunk(foundChunk, &freeLists->bigChunks[containerIdx]);
156 }
158 /*
159 * This is sequential code, meant to only be called from the Master, not from
160 * any slave VPs.
161 */
162 void *VMS__malloc( size_t sizeRequested )
163 {
164 //============================= MEASUREMENT STUFF ========================
165 #ifdef MEAS__TIME_MALLOC
166 int32 startStamp, endStamp;
167 saveLowTimeStampCountInto( startStamp );
168 #endif
169 //========================================================================
172 MallocArrays* freeLists = _VMSMasterEnv->freeLists;
174 //Return a small chunk if the requested size is smaller than 128B
175 if(sizeRequested <= LOWER_BOUND)
176 {
177 uint32 freeListIdx = (sizeRequested-1)/32;
178 if(freeLists->smallChunkCount[freeListIdx] == 0)
179 {
180 makeChunks((freeListIdx+1)*32, &freeLists->smallChunks[freeListIdx]);
181 freeLists->smallChunkCount[freeListIdx] += 5;
182 }
184 freeLists->smallChunkCount[freeListIdx]--;
185 return removeChunk(&freeLists->smallChunks[freeListIdx]) + 1;
186 }
188 //Calculate the expected container. Start one higher to have a Chunk that's
189 //always big enough.
190 uint32 targetContainerIdx = getContainer(sizeRequested);
191 uint32 containerIdx = targetContainerIdx + 1;
193 MallocProlog* foundChunk;
194 if(freeLists->bigChunks[containerIdx] == NULL)
195 {
196 uint64 searchVector = freeLists->bigChunksSearchVector;
197 //set small chunk bits to zero
198 searchVector &= MAX_UINT64 << containerIdx;
199 containerIdx = __builtin_ffsl(searchVector);
201 if(containerIdx == 0)
202 {
203 printf("VMS malloc failed: low memory");
204 exit(1);
205 }
206 /*
207 while(freeList->bigChunks[containerIdx] == NULL)
208 {
209 containerIdx++;
210 if(containerIdx >= freeList->containerCount)
211 {
212 printf("VMS malloc failed: low memory");
213 exit(1);
214 }
215 }*/
217 foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
218 size_t chunkSize = getChunkSize(foundChunk);
220 //If the new chunk is larger than the requested size: split
221 if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + LOWER_BOUND)
222 {
223 MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);
224 containerIdx = getContainer(getChunkSize(newChunk));
225 insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]);
226 freeLists->bigChunksSearchVector |= 1 << containerIdx;
227 foundChunk = newChunk;
228 }
229 }
230 else
231 {
232 foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
233 }
235 //Mark as allocated
236 foundChunk->prevChunkInFreeList = NULL;
238 //============================= MEASUREMENT STUFF ========================
239 #ifdef MEAS__TIME_MALLOC
240 saveLowTimeStampCountInto( endStamp );
241 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
242 #endif
243 //========================================================================
245 //skip over the prolog by adding its size to the pointer return
246 return foundChunk + 1;
247 }
249 /*
250 * This is sequential code, meant to only be called from the Master, not from
251 * any slave VPs.
252 */
253 void
254 VMS__free( void *ptrToFree )
255 {
257 //============================= MEASUREMENT STUFF ========================
258 #ifdef MEAS__TIME_MALLOC
259 int32 startStamp, endStamp;
260 saveLowTimeStampCountInto( startStamp );
261 #endif
262 //========================================================================
264 MallocArrays* freeLists = _VMSMasterEnv->freeLists;
265 MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1;
266 uint32 containerIdx;
268 size_t chunkSize = getChunkSize(chunkToFree);
269 if(chunkSize <= LOWER_BOUND)
270 {
271 containerIdx = (chunkSize-1)/32;
272 insertChunk(chunkToFree,&freeLists->smallChunks[containerIdx]);
273 freeLists->smallChunkCount[containerIdx]++;
275 if(freeLists->smallChunkCount[containerIdx] > 20)
276 recycleSmallChunks(&freeLists->smallChunks[containerIdx]);
278 return;
279 }
281 //Check for free neighbors
282 if(chunkToFree->nextLowerInMem)
283 {
284 if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)
285 {//Chunk is not allocated
286 if(getChunkSize(chunkToFree->nextLowerInMem) > LOWER_BOUND)
287 {
288 extractChunk(chunkToFree->nextLowerInMem);
289 chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);
290 }
291 }
292 }
293 if(chunkToFree->nextHigherInMem)
294 {
295 if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL)
296 {//Chunk is not allocated
297 if(getChunkSize(chunkToFree->nextHigherInMem) > LOWER_BOUND)
298 {
299 extractChunk(chunkToFree->nextHigherInMem);
300 chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem);
301 }
302 }
303 }
305 containerIdx = getContainer(chunkSize);
306 insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);
308 //============================= MEASUREMENT STUFF ========================
309 #ifdef MEAS__TIME_MALLOC
310 saveLowTimeStampCountInto( endStamp );
311 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist );
312 #endif
313 //========================================================================
315 }
318 /*Allocates memory from the external system -- higher overhead
319 *
320 *Because of Linux's malloc throwing bizarre random faults when malloc is
321 * used inside a VMS virtual processor, have to pass this as a request and
322 * have the core loop do it when it gets around to it -- will look for these
323 * chores leftover from the previous animation of masterVP the next time it
324 * goes to animate the masterVP -- so it takes two separate masterVP
325 * animations, separated by work, to complete an external malloc or
326 * external free request.
327 *
328 *Thinking core loop accepts signals -- just looks if signal-location is
329 * empty or not --
330 */
331 void *
332 VMS__malloc_in_ext( size_t sizeRequested )
333 {
334 /*
335 //This is running in the master, so no chance for multiple cores to be
336 // competing for the core's flag.
337 if( *(_VMSMasterEnv->coreLoopSignalAddr[ 0 ]) != 0 )
338 { //something has already signalled to core loop, so save the signal
339 // and look, next time master animated, to see if can send it.
340 //Note, the addr to put a signal is in the coreloop's frame, so just
341 // checks it each time through -- make it volatile to avoid GCC
342 // optimizations -- it's a coreloop local var that only changes
343 // after jumping away. The signal includes the addr to send the
344 //return to -- even if just empty return completion-signal
345 //
346 //save the signal in some queue that the master looks at each time
347 // it starts up -- one loc says if empty for fast common case --
348 //something like that -- want to hide this inside this call -- but
349 // think this has to come as a request -- req handler gives procr
350 // back to master loop, which gives it back to req handler at point
351 // it sees that core loop has sent return signal. Something like
352 // that.
353 saveTheSignal
355 }
356 coreSigData->type = malloc;
357 coreSigData->sizeToMalloc = sizeRequested;
358 coreSigData->locToSignalCompletion = &figureOut;
359 _VMSMasterEnv->coreLoopSignals[ 0 ] = coreSigData;
360 */
361 //just risk system-stack faults until get this figured out
362 return malloc( sizeRequested );
363 }
366 /*Frees memory that was allocated in the external system -- higher overhead
367 *
368 *As noted in external malloc comment, this is clunky 'cause the free has
369 * to be called in the core loop.
370 */
371 void
372 VMS__free_in_ext( void *ptrToFree )
373 {
374 //just risk system-stack faults until get this figured out
375 free( ptrToFree );
377 //TODO: fix this -- so
378 }
381 /*Designed to be called from the main thread outside of VMS, during init
382 */
383 MallocArrays *
384 VMS_ext__create_free_list()
385 {
386 //Initialize containers for small chunks and fill with zeros
387 _VMSMasterEnv->freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) );
388 MallocArrays *freeLists = _VMSMasterEnv->freeLists;
390 freeLists->smallChunks =
391 (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
392 memset((void*)freeLists->smallChunks,
393 0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
394 memset((void*)freeLists->smallChunkCount,
395 0,SMALL_CHUNK_COUNT*sizeof(uint32));
397 //Calculate number of containers for big chunks
398 uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;
399 freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*));
400 memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*));
401 freeLists->containerCount = container;
403 //Create first element in lastContainer
404 MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
405 if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);}
406 freeLists->memSpace = firstChunk;
408 firstChunk->nextLowerInMem = NULL;
409 firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk +
410 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog*));
411 firstChunk->nextChunkInFreeList = NULL;
412 //previous element in the queue is the container
413 firstChunk->prevChunkInFreeList = freeLists->bigChunks[container-1];
415 freeLists->bigChunks[container-1] = firstChunk;
416 //Insert into bit search list
417 freeLists->bigChunksSearchVector |= (1 << (container-1));
419 //Create dummy chunk to mark the top of stack this is of course
420 //never freed
421 MallocProlog *dummyChunk = firstChunk->nextHigherInMem;
422 dummyChunk->nextHigherInMem = dummyChunk+1;
423 dummyChunk->nextLowerInMem = NULL;
424 dummyChunk->nextChunkInFreeList = NULL;
425 dummyChunk->prevChunkInFreeList = NULL;
427 return freeLists;
428 }
431 /*Designed to be called from the main thread outside of VMS, during cleanup
432 */
433 void
434 VMS_ext__free_free_list( MallocArrays *freeLists )
435 {
436 free(freeLists->memSpace);
437 free(freeLists->bigChunks);
438 free(freeLists->smallChunks);
440 }