Mercurial > cgi-bin > hgwebdir.cgi > VMS > VMS_Implementations > VMS_impls > VMS__MC_shared_impl
view vmalloc.c @ 206:a262abf4b8d5
brch file for new WestmereEx 4x10 HW Branch
| author | Merten Sach <msach@mailbox.tu-berlin.de> |
|---|---|
| date | Fri, 17 Feb 2012 18:43:52 +0100 |
| parents | de5e7c522f1f |
| children |
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 "C_Libraries/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 (log2(size)-LOG128)/LOG54;
32 }
34 /*
35 * Removes the first chunk of a freeList
36 * The chunk is removed but not set as free. There is no check if
37 * the free list is empty, so make sure this is not the case.
38 */
39 inline
40 MallocProlog *removeChunk(MallocArrays* freeLists, uint32 containerIdx)
41 {
42 MallocProlog** container = &freeLists->bigChunks[containerIdx];
43 MallocProlog* removedChunk = *container;
44 *container = removedChunk->nextChunkInFreeList;
46 if(removedChunk->nextChunkInFreeList)
47 removedChunk->nextChunkInFreeList->prevChunkInFreeList =
48 (MallocProlog*)container;
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 }
58 return removedChunk;
59 }
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;
73 if(removedChunk->nextChunkInFreeList)
74 removedChunk->nextChunkInFreeList->prevChunkInFreeList =
75 (MallocProlog*)container;
77 return removedChunk;
78 }
80 inline
81 size_t getChunkSize(MallocProlog* chunk)
82 {
83 return (uintptr_t)chunk->nextHigherInMem -
84 (uintptr_t)chunk - sizeof(MallocProlog);
85 }
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;
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));
108 }
109 }
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 }
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);
146 newChunk = __align_adress((uintptr_t)newChunk+CACHELINE_SIZE-1)-sizeof(MallocProlog);
148 newChunk->nextLowerInMem = chunk;
149 newChunk->nextHigherInMem = chunk->nextHigherInMem;
151 chunk->nextHigherInMem->nextLowerInMem = newChunk;
152 chunk->nextHigherInMem = newChunk;
154 return newChunk;
155 }
157 /*
158 * Search for chunk in the list of big chunks. Split the block if it's too big
159 */
160 inline
161 MallocProlog *searchChunk(MallocArrays *freeLists, size_t sizeRequested, uint32 containerIdx)
162 {
163 MallocProlog* foundChunk;
165 uint64 searchVector = freeLists->bigChunksSearchVector[0];
166 //set small chunk bits to zero
167 searchVector &= MAX_UINT64 << containerIdx;
168 containerIdx = __builtin_ffsl(searchVector);
170 if(containerIdx == 0)
171 {
172 searchVector = freeLists->bigChunksSearchVector[1];
173 containerIdx = __builtin_ffsl(searchVector);
174 if(containerIdx == 0)
175 {
176 printf("VMS malloc failed: low memory");
177 exit(1);
178 }
179 containerIdx += 64;
180 }
181 containerIdx--;
184 foundChunk = removeChunk(freeLists, containerIdx);
185 size_t chunkSize = getChunkSize(foundChunk);
187 //If the new chunk is larger than the requested size: split
188 if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + BIG_LOWER_BOUND)
189 {
190 MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);
191 containerIdx = getContainer(getChunkSize(foundChunk)) - 1;
192 insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]);
193 if(containerIdx < 64)
194 freeLists->bigChunksSearchVector[0] |= ((uint64)1 << containerIdx);
195 else
196 freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (containerIdx-64));
197 foundChunk = newChunk;
198 }
200 return foundChunk;
201 }
204 /*
205 * This is sequential code, meant to only be called from the Master, not from
206 * any slave VPs.
207 */
208 void *VMS_int__malloc( size_t sizeRequested )
209 {
210 //============================= MEASUREMENT STUFF ========================
211 #ifdef MEAS__TIME_MALLOC
212 int32 startStamp, endStamp;
213 saveLowTimeStampCountInto( startStamp );
214 #endif
215 //========================================================================
217 sizeRequested += (2*CACHELINE_SIZE); //Allocate more than cacheline_size to avoid false sharing
219 MallocArrays* freeLists = _VMSMasterEnv->freeLists;
220 MallocProlog* foundChunk;
222 //Return a small chunk if the requested size is smaller than 128B
223 if(sizeRequested <= LOWER_BOUND)
224 {
225 uint32 freeListIdx = (sizeRequested-1)/SMALL_CHUNK_SIZE;
226 if(freeLists->smallChunks[freeListIdx] == NULL)
227 foundChunk = searchChunk(freeLists, SMALL_CHUNK_SIZE*(freeListIdx+1), 0);
228 else
229 foundChunk = removeSmallChunk(freeLists, freeListIdx);
231 //Mark as allocated
232 foundChunk->prevChunkInFreeList = NULL;
233 return foundChunk + 1;
234 }
236 //Calculate the expected container. Start one higher to have a Chunk that's
237 //always big enough.
238 uint32 containerIdx = getContainer(sizeRequested);
240 if(freeLists->bigChunks[containerIdx] == NULL)
241 foundChunk = searchChunk(freeLists, sizeRequested, containerIdx);
242 else
243 foundChunk = removeChunk(freeLists, containerIdx);
245 //Mark as allocated
246 foundChunk->prevChunkInFreeList = NULL;
248 //============================= MEASUREMENT STUFF ========================
249 #ifdef MEAS__TIME_MALLOC
250 saveLowTimeStampCountInto( endStamp );
251 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
252 #endif
253 //========================================================================
255 //skip over the prolog by adding its size to the pointer return
256 return foundChunk + 1;
257 }
259 /*
260 * This is sequential code, meant to only be called from the Master, not from
261 * any slave VPs.
262 */
263 void
264 VMS_int__free( void *ptrToFree )
265 {
267 //============================= MEASUREMENT STUFF ========================
268 #ifdef MEAS__TIME_MALLOC
269 int32 startStamp, endStamp;
270 saveLowTimeStampCountInto( startStamp );
271 #endif
272 //========================================================================
274 MallocArrays* freeLists = _VMSMasterEnv->freeLists;
275 MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1;
276 uint32 containerIdx;
278 //Check for free neighbors
279 if(chunkToFree->nextLowerInMem)
280 {
281 if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)
282 {//Chunk is not allocated
283 extractChunk(chunkToFree->nextLowerInMem, freeLists);
284 chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);
285 }
286 }
287 if(chunkToFree->nextHigherInMem)
288 {
289 if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL)
290 {//Chunk is not allocated
291 extractChunk(chunkToFree->nextHigherInMem, freeLists);
292 chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem);
293 }
294 }
296 size_t chunkSize = getChunkSize(chunkToFree);
297 if(chunkSize < BIG_LOWER_BOUND)
298 {
299 containerIdx = (chunkSize/SMALL_CHUNK_SIZE)-1;
300 if(containerIdx > SMALL_CHUNK_COUNT-1)
301 containerIdx = SMALL_CHUNK_COUNT-1;
302 insertChunk(chunkToFree, &freeLists->smallChunks[containerIdx]);
303 }
304 else
305 {
306 containerIdx = getContainer(getChunkSize(chunkToFree)) - 1;
307 insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);
308 if(containerIdx < 64)
309 freeLists->bigChunksSearchVector[0] |= (uint64)1 << containerIdx;
310 else
311 freeLists->bigChunksSearchVector[1] |= (uint64)1 << (containerIdx-64);
312 }
314 //============================= MEASUREMENT STUFF ========================
315 #ifdef MEAS__TIME_MALLOC
316 saveLowTimeStampCountInto( endStamp );
317 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist );
318 #endif
319 //========================================================================
321 }
323 /*
324 * Designed to be called from the main thread outside of VMS, during init
325 */
326 MallocArrays *
327 VMS_ext__create_free_list()
328 {
329 //Initialize containers for small chunks and fill with zeros
330 _VMSMasterEnv->freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) );
331 MallocArrays *freeLists = _VMSMasterEnv->freeLists;
333 freeLists->smallChunks =
334 (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
335 memset((void*)freeLists->smallChunks,
336 0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
338 //Calculate number of containers for big chunks
339 uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;
340 freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*));
341 memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*));
342 freeLists->containerCount = container;
344 //Create first element in lastContainer
345 MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
346 if( firstChunk == NULL ) {printf("Can't allocate initial memory\n"); exit(1);}
347 freeLists->memSpace = firstChunk;
349 //Touch memory to avoid page faults
350 void *ptr,*endPtr;
351 endPtr = (void*)firstChunk+MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE;
352 for(ptr = firstChunk; ptr < endPtr; ptr+=PAGE_SIZE)
353 {
354 *(char*)ptr = 0;
355 }
357 firstChunk->nextLowerInMem = NULL;
358 firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk +
359 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog));
360 firstChunk->nextChunkInFreeList = NULL;
361 //previous element in the queue is the container
362 firstChunk->prevChunkInFreeList = &freeLists->bigChunks[container-2];
364 freeLists->bigChunks[container-2] = firstChunk;
365 //Insert into bit search list
366 if(container <= 65)
367 {
368 freeLists->bigChunksSearchVector[0] = ((uint64)1 << (container-2));
369 freeLists->bigChunksSearchVector[1] = 0;
370 }
371 else
372 {
373 freeLists->bigChunksSearchVector[0] = 0;
374 freeLists->bigChunksSearchVector[1] = ((uint64)1 << (container-66));
375 }
377 //Create dummy chunk to mark the top of stack this is of course
378 //never freed
379 MallocProlog *dummyChunk = firstChunk->nextHigherInMem;
380 dummyChunk->nextHigherInMem = dummyChunk+1;
381 dummyChunk->nextLowerInMem = NULL;
382 dummyChunk->nextChunkInFreeList = NULL;
383 dummyChunk->prevChunkInFreeList = NULL;
385 return freeLists;
386 }
389 /*Designed to be called from the main thread outside of VMS, during cleanup
390 */
391 void
392 VMS_ext__free_free_list( MallocArrays *freeLists )
393 {
394 free(freeLists->memSpace);
395 free(freeLists->bigChunks);
396 free(freeLists->smallChunks);
398 }