Mercurial > cgi-bin > hgwebdir.cgi > VMS > VMS_Implementations > VMS_impls > VMS__MC_shared_impl
view vmalloc.c @ 101:ca154ebe2b6c
Basic malloc without small chunks
| author | Merten Sach <msach@mailbox.tu-berlin.de> |
|---|---|
| date | Tue, 02 Aug 2011 15:44:28 +0200 |
| parents | 21c95d402fe6 |
| children | def70e32cf2c |
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 /*
21 * This calculates the container which fits the given size.
22 */
23 inline
24 uint32 getContainer(size_t size)
25 {
26 return floor((log10(size)-LOG128)/LOG54);
27 }
29 /*
30 * This calculates the size of a given container
31 */
32 inline
33 size_t getContainerSize(uint32 idx)
34 {
35 return pow(CHUNK_INCREASE_RATE,idx)*LOWER_BOUND;
36 }
38 /*
39 * Removes the first chunk of a freeList
40 * The chunk is removed but not set as free. There is no check if
41 * the free list is empty, so make sure this is not the case.
42 */
43 inline
44 MallocProlog *removeChunk(MallocProlog** container)
45 {
46 MallocProlog *removedChunk = *container;
47 *container = removedChunk->nextChunkInFreeList;
49 if(removedChunk->nextChunkInFreeList)
50 removedChunk->nextChunkInFreeList->prevChunkInFreeList =
51 (MallocProlog*)container;
53 return removedChunk;
54 }
56 /*
57 * Removes a chunk from a free list.
58 */
59 inline
60 MallocProlog *extractChunk(MallocProlog* chunk)
61 {
63 }
65 /*
66 * Merges two chunks.
67 * Chunk A has to be before chunk B in memory.
68 */
69 inline
70 MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB)
71 {
73 }
74 /*
75 * Inserts a chunk into a free list.
76 */
77 inline
78 void insertChunk(MallocProlog* chunk, MallocProlog** container)
79 {
80 chunk->nextChunkInFreeList = *container;
81 chunk->prevChunkInFreeList = (MallocProlog*)container;
82 if(*container)
83 (*container)->prevChunkInFreeList = chunk;
84 *container = chunk;
85 }
87 /*
88 * Divides the chunk that a new chunk of newSize is created.
89 * There is no size check, so make sure the size value is valid.
90 */
91 inline
92 MallocProlog *divideChunk(MallocProlog* chunk, size_t newSize)
93 {
94 MallocProlog* newChunk = (MallocProlog*)((uintptr_t)chunk->nextHigherInMem -
95 newSize - sizeof(MallocProlog));
97 newChunk->nextLowerInMem = chunk;
98 newChunk->nextHigherInMem = chunk->nextHigherInMem;
100 chunk->nextHigherInMem = newChunk;
101 chunk->nextHigherInMem->nextLowerInMem = newChunk;
103 return newChunk;
104 }
106 inline
107 size_t getChunkSize(MallocProlog* chunk)
108 {
109 return (uintptr_t)chunk->nextHigherInMem -
110 (uintptr_t)chunk - sizeof(MallocProlog);
111 }
113 /*
114 * This is sequential code, meant to only be called from the Master, not from
115 * any slave VPs.
116 */
117 void *VMS__malloc( size_t sizeRequested )
118 {
119 //============================= MEASUREMENT STUFF ========================
120 #ifdef MEAS__TIME_MALLOC
121 int32 startStamp, endStamp;
122 saveLowTimeStampCountInto( startStamp );
123 #endif
124 //========================================================================
126 MallocArrays* freeList = _VMSMasterEnv->freeLists;
128 //Return a small chunk if the requested size is smaller than 128B
129 //TODO: for now set size to 129B
130 if(sizeRequested < 128)
131 sizeRequested = 129;
133 //Calculate the expected container. Start one higher to have a Chunk that's
134 //always big enough.
135 uint32 targetContainerIdx = getContainer(sizeRequested);
136 uint32 containerIdx = targetContainerIdx + 1;
138 MallocProlog* foundChunk;
139 if(freeList->bigChunks[containerIdx] == NULL)
140 {
141 while(freeList->bigChunks[containerIdx] == NULL)
142 {
143 containerIdx++;
144 if(containerIdx > freeList->containerCount)
145 {
146 printf("VMS malloc failed: low memory");
147 exit(1);
148 }
149 }
151 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);
158 while(containerIdx > targetContainerIdx)
159 {
160 if(chunkSize > containerSize + sizeRequested + sizeof(MallocProlog))
161 {
162 MallocProlog *newChunk = divideChunk(foundChunk,containerSize);
163 insertChunk(newChunk,&freeList->bigChunks[containerIdx]);
164 chunkSize = getChunkSize(foundChunk);
165 }
166 containerIdx--;
167 containerSize /= CHUNK_INCREASE_RATE;
168 }
169 }
170 else
171 {
172 foundChunk = removeChunk(&freeList->bigChunks[containerIdx]);
173 }
175 //Mark as allocated
176 foundChunk->prevChunkInFreeList = NULL;
178 //============================= MEASUREMENT STUFF ========================
179 #ifdef MEAS__TIME_MALLOC
180 saveLowTimeStampCountInto( endStamp );
181 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
182 #endif
183 //========================================================================
185 //skip over the prolog by adding its size to the pointer return
186 return (void*)((uintptr_t)foundChunk + sizeof(MallocProlog));
187 }
189 /*
190 * This is sequential code, meant to only be called from the Master, not from
191 * any slave VPs.
192 */
193 void
194 VMS__free( void *ptrToFree )
195 {
197 //============================= MEASUREMENT STUFF ========================
198 #ifdef MEAS__TIME_MALLOC
199 int32 startStamp, endStamp;
200 saveLowTimeStampCountInto( startStamp );
201 #endif
202 //========================================================================
204 MallocArrays* freeList = _VMSMasterEnv->freeLists;
205 MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1;
207 //Check for free neighbors
208 if(chunkToFree->nextLowerInMem)
209 {
210 if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)
211 {//Chunk is not allocated
212 mergeChunks()
213 }
214 }
215 //============================= MEASUREMENT STUFF ========================
216 #ifdef MEAS__TIME_MALLOC
217 saveLowTimeStampCountInto( endStamp );
218 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist );
219 #endif
220 //========================================================================
222 }
225 /*Allocates memory from the external system -- higher overhead
226 *
227 *Because of Linux's malloc throwing bizarre random faults when malloc is
228 * used inside a VMS virtual processor, have to pass this as a request and
229 * have the core loop do it when it gets around to it -- will look for these
230 * chores leftover from the previous animation of masterVP the next time it
231 * goes to animate the masterVP -- so it takes two separate masterVP
232 * animations, separated by work, to complete an external malloc or
233 * external free request.
234 *
235 *Thinking core loop accepts signals -- just looks if signal-location is
236 * empty or not --
237 */
238 void *
239 VMS__malloc_in_ext( size_t sizeRequested )
240 {
241 /*
242 //This is running in the master, so no chance for multiple cores to be
243 // competing for the core's flag.
244 if( *(_VMSMasterEnv->coreLoopSignalAddr[ 0 ]) != 0 )
245 { //something has already signalled to core loop, so save the signal
246 // and look, next time master animated, to see if can send it.
247 //Note, the addr to put a signal is in the coreloop's frame, so just
248 // checks it each time through -- make it volatile to avoid GCC
249 // optimizations -- it's a coreloop local var that only changes
250 // after jumping away. The signal includes the addr to send the
251 //return to -- even if just empty return completion-signal
252 //
253 //save the signal in some queue that the master looks at each time
254 // it starts up -- one loc says if empty for fast common case --
255 //something like that -- want to hide this inside this call -- but
256 // think this has to come as a request -- req handler gives procr
257 // back to master loop, which gives it back to req handler at point
258 // it sees that core loop has sent return signal. Something like
259 // that.
260 saveTheSignal
262 }
263 coreSigData->type = malloc;
264 coreSigData->sizeToMalloc = sizeRequested;
265 coreSigData->locToSignalCompletion = &figureOut;
266 _VMSMasterEnv->coreLoopSignals[ 0 ] = coreSigData;
267 */
268 //just risk system-stack faults until get this figured out
269 return malloc( sizeRequested );
270 }
273 /*Frees memory that was allocated in the external system -- higher overhead
274 *
275 *As noted in external malloc comment, this is clunky 'cause the free has
276 * to be called in the core loop.
277 */
278 void
279 VMS__free_in_ext( void *ptrToFree )
280 {
281 //just risk system-stack faults until get this figured out
282 free( ptrToFree );
284 //TODO: fix this -- so
285 }
288 /*Designed to be called from the main thread outside of VMS, during init
289 */
290 MallocArrays *
291 VMS_ext__create_free_list()
292 {
293 //Initialize containers for small chunks and fill with zeros
294 _VMSMasterEnv->freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) );
295 MallocArrays *freeLists = _VMSMasterEnv->freeLists;
297 freeLists->smallChunks =
298 (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
299 memset((void*)freeLists->smallChunks,
300 0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
302 //Calculate number of containers for big chunks
303 uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;
305 freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*));
306 memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*));
307 freeLists->containerCount = container;
309 //Create first element in lastContainer
310 MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
311 if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);}
313 firstChunk->nextLowerInMem = NULL;
314 firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk +
315 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog*));
316 firstChunk->nextChunkInFreeList = NULL;
317 //previous element in the queue is the container
318 firstChunk->prevChunkInFreeList = freeLists->bigChunks[container-1];
320 freeLists->bigChunks[container-1] = firstChunk;
322 //Create dummy chunk to mark the top of stack this is of course
323 //never freed
324 MallocProlog *dummyChunk = firstChunk->nextHigherInMem;
325 dummyChunk->nextHigherInMem = dummyChunk+1;
326 dummyChunk->nextLowerInMem = NULL;
327 dummyChunk->nextChunkInFreeList = NULL;
328 dummyChunk->prevChunkInFreeList = NULL;
330 return freeLists;
331 }
334 /*Designed to be called from the main thread outside of VMS, during cleanup
335 */
336 void
337 VMS_ext__free_free_list( MallocProlog *freeListHead )
338 {
339 //stashed a ptr to the one and only bug chunk malloc'd from OS in the
340 // free list head's next lower in mem pointer
341 free( freeListHead->nextLowerInMem );
343 //don't free the head -- it'll be in an array eventually -- free whole
344 // array when all the free lists linked from it have already been freed
345 }