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

comparison vmalloc.c @ 209:0c83ea8adefc

find changesets by author, revision, files, or words in the commit message
Close to compilable version of common_ancestor -- still includes HW dep stuff
author Some Random Person <seanhalle@yahoo.com>
date Sun, 04 Mar 2012 14:26:35 -0800
parents eaf7e4c58c9e
children a18539c0bc37
comparison
equal deleted inserted replaced
37:c455a1119ef0 38:b8325aedd0f2
9 9
10 #include <malloc.h> 10 #include <malloc.h>
11 #include <inttypes.h> 11 #include <inttypes.h>
12 #include <stdlib.h> 12 #include <stdlib.h>
13 #include <stdio.h> 13 #include <stdio.h>
14 #include <string.h>
15 #include <math.h>
14 16
15 #include "VMS.h" 17 #include "VMS.h"
16 #include "C_Libraries/Histogram/Histogram.h" 18 #include "C_Libraries/Histogram/Histogram.h"
17 19
18 /*Helper function 20 #define MAX_UINT64 0xFFFFFFFFFFFFFFFF
19 *Insert a newly generated free chunk into the first spot on the free list. 21
20 * The chunk is cast as a MallocProlog, so the various pointers in it are 22 //A MallocProlog is a head element if the HigherInMem variable is NULL
21 * accessed with C's help -- and the size of the prolog is easily added to 23 //A Chunk is free if the prevChunkInFreeList variable is NULL
22 * the pointer when a chunk is returned to the app -- so C handles changes 24
23 * in pointer sizes among machines. 25 /*
24 * 26 * This calculates the container which fits the given size.
25 *The list head is a normal MallocProlog struct -- identified by its 27 */
26 * prevChunkInFreeList being NULL -- the only one. 28 inline
27 * 29 uint32 getContainer(size_t size)
28 *The end of the list is identified by next chunk being NULL, as usual. 30 {
29 */ 31 return (log2(size)-LOG128)/LOG54;
30 void inline 32 }
31 add_chunk_to_free_list( MallocProlog *chunk, MallocProlog *listHead ) 33
32 { 34 /*
33 chunk->nextChunkInFreeList = listHead->nextChunkInFreeList; 35 * Removes the first chunk of a freeList
34 if( chunk->nextChunkInFreeList != NULL ) //if not last in free list 36 * The chunk is removed but not set as free. There is no check if
35 chunk->nextChunkInFreeList->prevChunkInFreeList = chunk; 37 * the free list is empty, so make sure this is not the case.
36 chunk->prevChunkInFreeList = listHead; 38 */
37 listHead->nextChunkInFreeList = chunk; 39 inline
38 } 40 MallocProlog *removeChunk(MallocArrays* freeLists, uint32 containerIdx)
39 41 {
40 42 MallocProlog** container = &freeLists->bigChunks[containerIdx];
41 /*This is sequential code, meant to only be called from the Master, not from 43 MallocProlog* removedChunk = *container;
42 * any slave VPs. 44 *container = removedChunk->nextChunkInFreeList;
43 *Search down list, checking size by the nextHigherInMem pointer, to find 45
44 * first chunk bigger than size needed. 46 if(removedChunk->nextChunkInFreeList)
45 *Shave off the extra and make it into a new free-list element, hook it in 47 removedChunk->nextChunkInFreeList->prevChunkInFreeList =
46 * then return the address of the found element plus size of prolog. 48 (MallocProlog*)container;
47 * 49
50 if(*container == NULL)
51 {
52 if(containerIdx < 64)
53 freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx);
54 else
55 freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64));
56 }
57
58 return removedChunk;
59 }
60
61 /*
62 * Removes the first chunk of a freeList
63 * The chunk is removed but not set as free. There is no check if
64 * the free list is empty, so make sure this is not the case.
65 */
66 inline
67 MallocProlog *removeSmallChunk(MallocArrays* freeLists, uint32 containerIdx)
68 {
69 MallocProlog** container = &freeLists->smallChunks[containerIdx];
70 MallocProlog* removedChunk = *container;
71 *container = removedChunk->nextChunkInFreeList;
72
73 if(removedChunk->nextChunkInFreeList)
74 removedChunk->nextChunkInFreeList->prevChunkInFreeList =
75 (MallocProlog*)container;
76
77 return removedChunk;
78 }
79
80 inline
81 size_t getChunkSize(MallocProlog* chunk)
82 {
83 return (uintptr_t)chunk->nextHigherInMem -
84 (uintptr_t)chunk - sizeof(MallocProlog);
85 }
86
87 /*
88 * Removes a chunk from a free list.
89 */
90 inline
91 void extractChunk(MallocProlog* chunk, MallocArrays *freeLists)
92 {
93 chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;
94 if(chunk->nextChunkInFreeList)
95 chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;
96
97 //The last element in the list points to the container. If the container points
98 //to NULL the container is empty
99 if(*((void**)(chunk->prevChunkInFreeList)) == NULL && getChunkSize(chunk) >= BIG_LOWER_BOUND)
100 {
101 //Find the approppiate container because we do not know it
102 uint64 containerIdx = ((uintptr_t)chunk->prevChunkInFreeList - (uintptr_t)freeLists->bigChunks) >> 3;
103 if(containerIdx < (uint32)64)
104 freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx);
105 if(containerIdx < 128 && containerIdx >=64)
106 freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64));
107
108 }
109 }
110
111 /*
112 * Merges two chunks.
113 * Chunk A has to be before chunk B in memory. Both have to be removed from
114 * a free list
115 */
116 inline
117 MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB)
118 {
119 chunkA->nextHigherInMem = chunkB->nextHigherInMem;
120 chunkB->nextHigherInMem->nextLowerInMem = chunkA;
121 return chunkA;
122 }
123 /*
124 * Inserts a chunk into a free list.
125 */
126 inline
127 void insertChunk(MallocProlog* chunk, MallocProlog** container)
128 {
129 chunk->nextChunkInFreeList = *container;
130 chunk->prevChunkInFreeList = (MallocProlog*)container;
131 if(*container)
132 (*container)->prevChunkInFreeList = chunk;
133 *container = chunk;
134 }
135
136 /*
137 * Divides the chunk that a new chunk of newSize is created.
138 * There is no size check, so make sure the size value is valid.
139 */
140 inline
141 MallocProlog *divideChunk(MallocProlog* chunk, size_t newSize)
142 {
143 MallocProlog* newChunk = (MallocProlog*)((uintptr_t)chunk->nextHigherInMem -
144 newSize - sizeof(MallocProlog));
145
146 newChunk->nextLowerInMem = chunk;
147 newChunk->nextHigherInMem = chunk->nextHigherInMem;
148
149 chunk->nextHigherInMem->nextLowerInMem = newChunk;
150 chunk->nextHigherInMem = newChunk;
151
152 return newChunk;
153 }
154
155 /*
156 * Search for chunk in the list of big chunks. Split the block if it's too big
157 */
158 inline
159 MallocProlog *searchChunk(MallocArrays *freeLists, size_t sizeRequested, uint32 containerIdx)
160 {
161 MallocProlog* foundChunk;
162
163 uint64 searchVector = freeLists->bigChunksSearchVector[0];
164 //set small chunk bits to zero
165 searchVector &= MAX_UINT64 << containerIdx;
166 containerIdx = __builtin_ffsl(searchVector);
167
168 if(containerIdx == 0)
169 {
170 searchVector = freeLists->bigChunksSearchVector[1];
171 containerIdx = __builtin_ffsl(searchVector);
172 if(containerIdx == 0)
173 {
174 printf("VMS malloc failed: low memory");
175 exit(1);
176 }
177 containerIdx += 64;
178 }
179 containerIdx--;
180
181
182 foundChunk = removeChunk(freeLists, containerIdx);
183 size_t chunkSize = getChunkSize(foundChunk);
184
185 //If the new chunk is larger than the requested size: split
186 if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + BIG_LOWER_BOUND)
187 {
188 MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);
189 containerIdx = getContainer(getChunkSize(foundChunk)) - 1;
190 insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]);
191 if(containerIdx < 64)
192 freeLists->bigChunksSearchVector[0] |= ((uint64)1 << containerIdx);
193 else
194 freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (containerIdx-64));
195 foundChunk = newChunk;
196 }
197
198 return foundChunk;
199 }
200
201
202 /*
203 * This is sequential code, meant to only be called from the Master, not from
204 * any slave Slvs.
48 */ 205 */
49 void *VMS_int__malloc( size_t sizeRequested ) 206 void *VMS_int__malloc( size_t sizeRequested )
50 { MallocProlog *foundElem = NULL, *currElem, *newElem; 207 {
51 ssize_t amountExtra, sizeConsumed,sizeOfFound;
52 uint32 foundElemIsTopOfHeap;
53
54 //============================= MEASUREMENT STUFF ======================== 208 //============================= MEASUREMENT STUFF ========================
55 #ifdef MEAS__TIME_MALLOC 209 #ifdef MEAS__TIME_MALLOC
56 int32 startStamp, endStamp; 210 int32 startStamp, endStamp;
57 saveLowTimeStampCountInto( startStamp ); 211 saveLowTimeStampCountInto( startStamp );
58 #endif 212 #endif
59 //======================================================================== 213 //========================================================================
60 214
61 //step up the size to be aligned at 16-byte boundary, prob better ways 215 MallocArrays* freeLists = _VMSMasterEnv->freeLists;
62 sizeRequested = (sizeRequested + 16) & ~15; 216 MallocProlog* foundChunk;
63 currElem = (_VMSMasterEnv->freeListHead)->nextChunkInFreeList; 217
64 218 //Return a small chunk if the requested size is smaller than 128B
65 while( currElem != NULL ) 219 if(sizeRequested <= LOWER_BOUND)
66 { //check if size of currElem is big enough 220 {
67 sizeOfFound=(size_t)((uintptr_t)currElem->nextHigherInMem -(uintptr_t)currElem); 221 uint32 freeListIdx = (sizeRequested-1)/SMALL_CHUNK_SIZE;
68 amountExtra = sizeOfFound - sizeRequested - sizeof(MallocProlog); 222 if(freeLists->smallChunks[freeListIdx] == NULL)
69 if( amountExtra > 0 ) 223 foundChunk = searchChunk(freeLists, SMALL_CHUNK_SIZE*(freeListIdx+1), 0);
70 { //found it, get out of loop 224 else
71 foundElem = currElem; 225 foundChunk = removeSmallChunk(freeLists, freeListIdx);
72 currElem = NULL; 226
73 } 227 //Mark as allocated
74 else 228 foundChunk->prevChunkInFreeList = NULL;
75 currElem = currElem->nextChunkInFreeList; 229 return foundChunk + 1;
76 } 230 }
77 231
78 if( foundElem == NULL ) 232 //Calculate the expected container. Start one higher to have a Chunk that's
79 { ERROR("\nmalloc failed\n") 233 //always big enough.
80 return (void *)NULL; //indicates malloc failed 234 uint32 containerIdx = getContainer(sizeRequested);
81 } 235
82 //Using a kludge to identify the element that is the top chunk in the 236 if(freeLists->bigChunks[containerIdx] == NULL)
83 // heap -- saving top-of-heap addr in head's nextHigherInMem -- and 237 foundChunk = searchChunk(freeLists, sizeRequested, containerIdx);
84 // save addr of start of heap in head's nextLowerInMem
85 //Will handle top of Heap specially
86 foundElemIsTopOfHeap = foundElem->nextHigherInMem ==
87 _VMSMasterEnv->freeListHead->nextHigherInMem;
88
89 //before shave off and try to insert new elem, remove found elem
90 //note, foundElem will never be the head, so always has valid prevChunk
91 foundElem->prevChunkInFreeList->nextChunkInFreeList =
92 foundElem->nextChunkInFreeList;
93 if( foundElem->nextChunkInFreeList != NULL )
94 { foundElem->nextChunkInFreeList->prevChunkInFreeList =
95 foundElem->prevChunkInFreeList;
96 }
97 foundElem->prevChunkInFreeList = NULL;//indicates elem currently allocated
98
99 //if enough, turn extra into new elem & insert it
100 if( amountExtra > 64 )
101 { //make new elem by adding to addr of curr elem then casting
102 sizeConsumed = sizeof(MallocProlog) + sizeRequested;
103 newElem = (MallocProlog *)( (uintptr_t)foundElem + sizeConsumed );
104 newElem->nextLowerInMem = foundElem; //This is evil (but why?)
105 newElem->nextHigherInMem = foundElem->nextHigherInMem; //This is evil (but why?)
106 foundElem->nextHigherInMem = newElem;
107 if( ! foundElemIsTopOfHeap )
108 { //there is no next higher for top of heap, so can't write to it
109 newElem->nextHigherInMem->nextLowerInMem = newElem;
110 }
111 add_chunk_to_free_list( newElem, _VMSMasterEnv->freeListHead );
112 }
113 else 238 else
114 { 239 foundChunk = removeChunk(freeLists, containerIdx);
115 sizeConsumed = sizeOfFound; 240
116 } 241 //Mark as allocated
117 _VMSMasterEnv->amtOfOutstandingMem += sizeConsumed; 242 foundChunk->prevChunkInFreeList = NULL;
118 243
119 //============================= MEASUREMENT STUFF ======================== 244 //============================= MEASUREMENT STUFF ========================
120 #ifdef MEAS__TIME_MALLOC 245 #ifdef MEAS__TIME_MALLOC
121 saveLowTimeStampCountInto( endStamp ); 246 saveLowTimeStampCountInto( endStamp );
122 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist ); 247 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
123 #endif 248 #endif
124 //======================================================================== 249 //========================================================================
125 250
126 //skip over the prolog by adding its size to the pointer return 251 //skip over the prolog by adding its size to the pointer return
127 return (void*)((uintptr_t)foundElem + sizeof(MallocProlog)); 252 return foundChunk + 1;
128 } 253 }
129 254
130 /*This is sequential code, meant to only be called from the Master, not from 255 /*
131 * any slave VPs. 256 * This is sequential code, meant to only be called from the Master, not from
132 *Search down list, checking size by the nextHigherInMem pointer, to find 257 * any slave Slvs.
133 * first chunk bigger than size needed.
134 *Shave off the extra and make it into a new free-list element, hook it in
135 * then return the address of the found element plus size of prolog.
136 *
137 * The difference to the regular malloc is, that all the allocated chunks are
138 * aligned and padded to the size of a CACHE_LINE_SZ. Thus creating a new chunk
139 * before the aligned chunk.
140 */
141 void *VMS_int__malloc_aligned( size_t sizeRequested )
142 { MallocProlog *foundElem = NULL, *currElem, *newElem;
143 ssize_t amountExtra, sizeConsumed,sizeOfFound,prevAmount;
144 uint32 foundElemIsTopOfHeap;
145
146 //============================= MEASUREMENT STUFF ========================
147 #ifdef MEAS__TIME_MALLOC
148 uint32 startStamp, endStamp;
149 saveLowTimeStampCountInto( startStamp );
150 #endif
151 //========================================================================
152
153 //step up the size to be multiple of the cache line size
154 sizeRequested = (sizeRequested + CACHE_LINE_SZ) & ~(CACHE_LINE_SZ-1);
155 currElem = (_VMSMasterEnv->freeListHead)->nextChunkInFreeList;
156
157 while( currElem != NULL )
158 { //check if size of currElem is big enough
159 sizeOfFound=(size_t)((uintptr_t)currElem->nextHigherInMem -(uintptr_t)currElem);
160 amountExtra = sizeOfFound - sizeRequested - sizeof(MallocProlog);
161 if( amountExtra > 0 )
162 {
163 //look if the found element is already aligned
164 if((((uintptr_t)currElem+sizeof(MallocProlog)) & (uintptr_t)(CACHE_LINE_SZ-1)) == 0){
165 //found it, get out of loop
166 foundElem = currElem;
167 break;
168 }else{
169 //find first aligned address and check if it's still big enough
170 //check also if the space before the aligned address is big enough
171 //for a new element
172 void *firstAlignedAddr = (void*)(((uintptr_t)currElem + 2*CACHE_LINE_SZ) & ~((uintptr_t)(CACHE_LINE_SZ-1)));
173 prevAmount = (uintptr_t)firstAlignedAddr - (uintptr_t)currElem;
174 sizeOfFound=(uintptr_t)currElem->nextHigherInMem -(uintptr_t)firstAlignedAddr + sizeof(MallocProlog);
175 amountExtra= sizeOfFound - sizeRequested - sizeof(MallocProlog);
176 if(prevAmount > 2*sizeof(MallocProlog) && amountExtra > 0 ){
177 //found suitable element
178 //create new previous element and exit loop
179 MallocProlog *newAlignedElem = (MallocProlog*)firstAlignedAddr - 1;
180
181 //insert new element into free list
182 if(currElem->nextChunkInFreeList != NULL)
183 currElem->nextChunkInFreeList->prevChunkInFreeList = newAlignedElem;
184 newAlignedElem->prevChunkInFreeList = currElem;
185 newAlignedElem->nextChunkInFreeList = currElem->nextChunkInFreeList;
186 currElem->nextChunkInFreeList = newAlignedElem;
187
188 //set higherInMem and lowerInMem
189 newAlignedElem->nextHigherInMem = currElem->nextHigherInMem;
190 foundElemIsTopOfHeap = currElem->nextHigherInMem ==
191 _VMSMasterEnv->freeListHead->nextHigherInMem;
192 if(!foundElemIsTopOfHeap)
193 currElem->nextHigherInMem->nextLowerInMem = newAlignedElem;
194 currElem->nextHigherInMem = newAlignedElem;
195 newAlignedElem->nextLowerInMem = currElem;
196
197 //Found new element leaving loop
198 foundElem = newAlignedElem;
199 break;
200 }
201 }
202
203 }
204 currElem = currElem->nextChunkInFreeList;
205 }
206
207 if( foundElem == NULL )
208 { ERROR("\nmalloc failed\n")
209 return (void *)NULL; //indicates malloc failed
210 }
211 //Using a kludge to identify the element that is the top chunk in the
212 // heap -- saving top-of-heap addr in head's nextHigherInMem -- and
213 // save addr of start of heap in head's nextLowerInMem
214 //Will handle top of Heap specially
215 foundElemIsTopOfHeap = foundElem->nextHigherInMem ==
216 _VMSMasterEnv->freeListHead->nextHigherInMem;
217
218 //before shave off and try to insert new elem, remove found elem
219 //note, foundElem will never be the head, so always has valid prevChunk
220 foundElem->prevChunkInFreeList->nextChunkInFreeList =
221 foundElem->nextChunkInFreeList;
222 if( foundElem->nextChunkInFreeList != NULL )
223 { foundElem->nextChunkInFreeList->prevChunkInFreeList =
224 foundElem->prevChunkInFreeList;
225 }
226 foundElem->prevChunkInFreeList = NULL;//indicates elem currently allocated
227
228 //if enough, turn extra into new elem & insert it
229 if( amountExtra > 64 )
230 { //make new elem by adding to addr of curr elem then casting
231 sizeConsumed = sizeof(MallocProlog) + sizeRequested;
232 newElem = (MallocProlog *)( (uintptr_t)foundElem + sizeConsumed );
233 newElem->nextHigherInMem = foundElem->nextHigherInMem;
234 newElem->nextLowerInMem = foundElem;
235 foundElem->nextHigherInMem = newElem;
236
237 if( ! foundElemIsTopOfHeap )
238 { //there is no next higher for top of heap, so can't write to it
239 newElem->nextHigherInMem->nextLowerInMem = newElem;
240 }
241 add_chunk_to_free_list( newElem, _VMSMasterEnv->freeListHead );
242 }
243 else
244 {
245 sizeConsumed = sizeOfFound;
246 }
247 _VMSMasterEnv->amtOfOutstandingMem += sizeConsumed;
248
249 //============================= MEASUREMENT STUFF ========================
250 #ifdef MEAS__TIME_MALLOC
251 saveLowTimeStampCountInto( endStamp );
252 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
253 #endif
254 //========================================================================
255
256 //skip over the prolog by adding its size to the pointer return
257 return (void*)((uintptr_t)foundElem + sizeof(MallocProlog));
258 }
259
260
261 /*This is sequential code -- only to be called from the Master
262 * When free, subtract the size of prolog from pointer, then cast it to a
263 * MallocProlog. Then check the nextLower and nextHigher chunks to see if
264 * one or both are also free, and coalesce if so, and if neither free, then
265 * add this one to free-list.
266 */ 258 */
267 void 259 void
268 VMS_int__free( void *ptrToFree ) 260 VMS_int__free( void *ptrToFree )
269 { MallocProlog *elemToFree, *nextLowerElem, *nextHigherElem; 261 {
270 size_t sizeOfElem; 262
271 uint32 lowerExistsAndIsFree, higherExistsAndIsFree;
272
273 //============================= MEASUREMENT STUFF ======================== 263 //============================= MEASUREMENT STUFF ========================
274 #ifdef MEAS__TIME_MALLOC 264 #ifdef MEAS__TIME_MALLOC
275 int32 startStamp, endStamp; 265 int32 startStamp, endStamp;
276 saveLowTimeStampCountInto( startStamp ); 266 saveLowTimeStampCountInto( startStamp );
277 #endif 267 #endif
278 //======================================================================== 268 //========================================================================
279 269
280 if( ptrToFree < (void*)_VMSMasterEnv->freeListHead->nextLowerInMem || 270 MallocArrays* freeLists = _VMSMasterEnv->freeLists;
281 ptrToFree > (void*)_VMSMasterEnv->freeListHead->nextHigherInMem ) 271 MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1;
282 { //outside the range of data owned by VMS's malloc, so do nothing 272 uint32 containerIdx;
283 return; 273
284 } 274 //Check for free neighbors
285 //subtract size of prolog to get pointer to prolog, then cast 275 if(chunkToFree->nextLowerInMem)
286 elemToFree = (MallocProlog *)((uintptr_t)ptrToFree - sizeof(MallocProlog)); 276 {
287 sizeOfElem =(size_t)((uintptr_t)elemToFree->nextHigherInMem-(uintptr_t)elemToFree); 277 if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)
288 278 {//Chunk is not allocated
289 if( elemToFree->prevChunkInFreeList != NULL ) 279 extractChunk(chunkToFree->nextLowerInMem, freeLists);
290 { printf( "error: freeing same element twice!" ); exit(1); 280 chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);
291 }
292
293 _VMSMasterEnv->amtOfOutstandingMem -= sizeOfElem;
294
295 nextLowerElem = elemToFree->nextLowerInMem;
296 nextHigherElem = elemToFree->nextHigherInMem;
297
298 if( nextHigherElem == NULL )
299 higherExistsAndIsFree = FALSE;
300 else //okay exists, now check if in the free-list by checking back ptr
301 higherExistsAndIsFree = (nextHigherElem->prevChunkInFreeList != NULL);
302
303 if( nextLowerElem == NULL )
304 lowerExistsAndIsFree = FALSE;
305 else //okay, it exists, now check if it's free
306 lowerExistsAndIsFree = (nextLowerElem->prevChunkInFreeList != NULL);
307
308
309 //now, know what exists and what's free
310 if( lowerExistsAndIsFree )
311 { if( higherExistsAndIsFree )
312 { //both exist and are free, so coalesce all three
313 //First, remove higher from free-list
314 nextHigherElem->prevChunkInFreeList->nextChunkInFreeList =
315 nextHigherElem->nextChunkInFreeList;
316 if( nextHigherElem->nextChunkInFreeList != NULL ) //end-of-list?
317 nextHigherElem->nextChunkInFreeList->prevChunkInFreeList =
318 nextHigherElem->prevChunkInFreeList;
319 //Now, fix-up sequence-in-mem list -- by side-effect, this also
320 // changes size of the lower elem, which is still in free-list
321 nextLowerElem->nextHigherInMem = nextHigherElem->nextHigherInMem;
322 if( nextHigherElem->nextHigherInMem !=
323 _VMSMasterEnv->freeListHead->nextHigherInMem )
324 nextHigherElem->nextHigherInMem->nextLowerInMem = nextLowerElem;
325 //notice didn't do anything to elemToFree -- it simply is no
326 // longer reachable from any of the lists. Wonder if could be a
327 // security leak because left valid addresses in it,
328 // but don't care for now.
329 } 281 }
330 else 282 }
331 { //lower is the only of the two that exists and is free, 283 if(chunkToFree->nextHigherInMem)
332 //In this case, no adjustment to free-list, just change mem-list. 284 {
333 // By side-effect, changes size of the lower elem 285 if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL)
334 nextLowerElem->nextHigherInMem = elemToFree->nextHigherInMem; 286 {//Chunk is not allocated
335 if( elemToFree->nextHigherInMem != 287 extractChunk(chunkToFree->nextHigherInMem, freeLists);
336 _VMSMasterEnv->freeListHead->nextHigherInMem ) 288 chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem);
337 elemToFree->nextHigherInMem->nextLowerInMem = nextLowerElem;
338 } 289 }
339 } 290 }
291
292 size_t chunkSize = getChunkSize(chunkToFree);
293 if(chunkSize < BIG_LOWER_BOUND)
294 {
295 containerIdx = (chunkSize/SMALL_CHUNK_SIZE)-1;
296 if(containerIdx > SMALL_CHUNK_COUNT-1)
297 containerIdx = SMALL_CHUNK_COUNT-1;
298 insertChunk(chunkToFree, &freeLists->smallChunks[containerIdx]);
299 }
340 else 300 else
341 { //lower either doesn't exist or isn't free, so check higher 301 {
342 if( higherExistsAndIsFree ) 302 containerIdx = getContainer(getChunkSize(chunkToFree)) - 1;
343 { //higher exists and is the only of the two free 303 insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);
344 //First, in free-list, replace higher elem with the one to free 304 if(containerIdx < 64)
345 elemToFree->nextChunkInFreeList=nextHigherElem->nextChunkInFreeList; 305 freeLists->bigChunksSearchVector[0] |= (uint64)1 << containerIdx;
346 elemToFree->prevChunkInFreeList=nextHigherElem->prevChunkInFreeList; 306 else
347 elemToFree->prevChunkInFreeList->nextChunkInFreeList = elemToFree; 307 freeLists->bigChunksSearchVector[1] |= (uint64)1 << (containerIdx-64);
348 if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list? 308 }
349 elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree; 309
350 //Now chg mem-list. By side-effect, changes size of elemToFree
351 elemToFree->nextHigherInMem = nextHigherElem->nextHigherInMem;
352 if( elemToFree->nextHigherInMem !=
353 _VMSMasterEnv->freeListHead->nextHigherInMem )
354 elemToFree->nextHigherInMem->nextLowerInMem = elemToFree;
355 }
356 else
357 { //neither lower nor higher is availabe to coalesce so add to list
358 // this makes prev chunk ptr non-null, which indicates it's free
359 elemToFree->nextChunkInFreeList =
360 _VMSMasterEnv->freeListHead->nextChunkInFreeList;
361 _VMSMasterEnv->freeListHead->nextChunkInFreeList = elemToFree;
362 if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list?
363 elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree;
364 elemToFree->prevChunkInFreeList = _VMSMasterEnv->freeListHead;
365 }
366 }
367 //============================= MEASUREMENT STUFF ======================== 310 //============================= MEASUREMENT STUFF ========================
368 #ifdef MEAS__TIME_MALLOC 311 #ifdef MEAS__TIME_MALLOC
369 saveLowTimeStampCountInto( endStamp ); 312 saveLowTimeStampCountInto( endStamp );
370 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist ); 313 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist );
371 #endif 314 #endif
372 //======================================================================== 315 //========================================================================
373 316
374 } 317 }
375 318
376 319 /*
377 /*Allocates memory from the external system -- higher overhead 320 * Designed to be called from the main thread outside of VMS, during init
378 * 321 */
379 *Because of Linux's malloc throwing bizarre random faults when malloc is 322 MallocArrays *
380 * used inside a VMS virtual processor, have to pass this as a request and
381 * have the core loop do it when it gets around to it -- will look for these
382 * chores leftover from the previous animation of masterVP the next time it
383 * goes to animate the masterVP -- so it takes two separate masterVP
384 * animations, separated by work, to complete an external malloc or
385 * external free request.
386 *
387 *Thinking core loop accepts signals -- just looks if signal-location is
388 * empty or not --
389 */
390 void *
391 VMS__malloc_in_ext( size_t sizeRequested )
392 {
393 /*
394 //This is running in the master, so no chance for multiple cores to be
395 // competing for the core's flag.
396 if( *(_VMSMasterEnv->coreLoopSignalAddr[ 0 ]) != 0 )
397 { //something has already signalled to core loop, so save the signal
398 // and look, next time master animated, to see if can send it.
399 //Note, the addr to put a signal is in the coreloop's frame, so just
400 // checks it each time through -- make it volatile to avoid GCC
401 // optimizations -- it's a coreloop local var that only changes
402 // after jumping away. The signal includes the addr to send the
403 //return to -- even if just empty return completion-signal
404 //
405 //save the signal in some queue that the master looks at each time
406 // it starts up -- one loc says if empty for fast common case --
407 //something like that -- want to hide this inside this call -- but
408 // think this has to come as a request -- req handler gives procr
409 // back to master loop, which gives it back to req handler at point
410 // it sees that core loop has sent return signal. Something like
411 // that.
412 saveTheSignal
413
414 }
415 coreSigData->type = malloc;
416 coreSigData->sizeToMalloc = sizeRequested;
417 coreSigData->locToSignalCompletion = &figureOut;
418 _VMSMasterEnv->coreLoopSignals[ 0 ] = coreSigData;
419 */
420 //just risk system-stack faults until get this figured out
421 return malloc( sizeRequested );
422 }
423
424
425 /*Frees memory that was allocated in the external system -- higher overhead
426 *
427 *As noted in external malloc comment, this is clunky 'cause the free has
428 * to be called in the core loop.
429 */
430 void
431 VMS__free_in_ext( void *ptrToFree )
432 {
433 //just risk system-stack faults until get this figured out
434 free( ptrToFree );
435
436 //TODO: fix this -- so
437 }
438
439
440 /*Designed to be called from the main thread outside of VMS, during init
441 */
442 MallocProlog *
443 VMS_ext__create_free_list() 323 VMS_ext__create_free_list()
444 { MallocProlog *freeListHead, *firstChunk; 324 {
445 325 //Initialize containers for small chunks and fill with zeros
446 //Note, this is running in the main thread -- all increases in malloc 326 _VMSMasterEnv->freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) );
447 // mem and all frees of it must be done in this thread, with the 327 MallocArrays *freeLists = _VMSMasterEnv->freeLists;
448 // thread's original stack available 328
449 freeListHead = malloc( sizeof(MallocProlog) ); 329 freeLists->smallChunks =
450 firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE ); 330 (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
451 if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);} 331 memset((void*)freeLists->smallChunks,
332 0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
333
334 //Calculate number of containers for big chunks
335 uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;
336 freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*));
337 memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*));
338 freeLists->containerCount = container;
339
340 //Create first element in lastContainer
341 MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
342 if( firstChunk == NULL ) {printf("Can't allocate initial memory\n"); exit(1);}
343 freeLists->memSpace = firstChunk;
452 344
453 //Touch memory to avoid page faults 345 //Touch memory to avoid page faults
454 void *ptr,*endPtr; 346 void *ptr,*endPtr;
455 endPtr = (void*)firstChunk+MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE; 347 endPtr = (void*)firstChunk+MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE;
456 for(ptr = firstChunk; ptr < endPtr; ptr+=PAGE_SIZE) 348 for(ptr = firstChunk; ptr < endPtr; ptr+=PAGE_SIZE)
457 { 349 {
458 *(char*)ptr = 0; 350 *(char*)ptr = 0;
459 } 351 }
460 352
461 freeListHead->prevChunkInFreeList = NULL; 353 firstChunk->nextLowerInMem = NULL;
462 //Use this addr to free the heap when cleanup 354 firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk +
463 freeListHead->nextLowerInMem = firstChunk; 355 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog));
464 //to identify top-of-heap elem, compare this addr to elem's next higher 356 firstChunk->nextChunkInFreeList = NULL;
465 freeListHead->nextHigherInMem = (void*)( (uintptr_t)firstChunk + 357 //previous element in the queue is the container
466 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE); 358 firstChunk->prevChunkInFreeList = &freeLists->bigChunks[container-2];
467 freeListHead->nextChunkInFreeList = firstChunk; 359
468 360 freeLists->bigChunks[container-2] = firstChunk;
469 firstChunk->nextChunkInFreeList = NULL; 361 //Insert into bit search list
470 firstChunk->prevChunkInFreeList = freeListHead; 362 if(container <= 65)
471 //next Higher has to be set to top of chunk, so can calc size in malloc 363 {
472 firstChunk->nextHigherInMem = (void*)( (uintptr_t)firstChunk + 364 freeLists->bigChunksSearchVector[0] = ((uint64)1 << (container-2));
473 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE); 365 freeLists->bigChunksSearchVector[1] = 0;
474 firstChunk->nextLowerInMem = NULL; //identifies as bott of heap 366 }
475 367 else
476 _VMSMasterEnv->amtOfOutstandingMem = 0; //none allocated yet 368 {
477 369 freeLists->bigChunksSearchVector[0] = 0;
478 return freeListHead; 370 freeLists->bigChunksSearchVector[1] = ((uint64)1 << (container-66));
371 }
372
373 //Create dummy chunk to mark the top of stack this is of course
374 //never freed
375 MallocProlog *dummyChunk = firstChunk->nextHigherInMem;
376 dummyChunk->nextHigherInMem = dummyChunk+1;
377 dummyChunk->nextLowerInMem = NULL;
378 dummyChunk->nextChunkInFreeList = NULL;
379 dummyChunk->prevChunkInFreeList = NULL;
380
381 return freeLists;
479 } 382 }
480 383
481 384
482 /*Designed to be called from the main thread outside of VMS, during cleanup 385 /*Designed to be called from the main thread outside of VMS, during cleanup
483 */ 386 */
484 void 387 void
485 VMS_ext__free_free_list( MallocProlog *freeListHead ) 388 VMS_ext__free_free_list( MallocArrays *freeLists )
486 { 389 {
487 //stashed a ptr to the one and only bug chunk malloc'd from OS in the 390 free(freeLists->memSpace);
488 // free list head's next lower in mem pointer 391 free(freeLists->bigChunks);
489 free( freeListHead->nextLowerInMem ); 392 free(freeLists->smallChunks);
490 393
491 //don't free the head -- it'll be in an array eventually -- free whole
492 // array when all the free lists linked from it have already been freed
493 } 394 }
494 395