VMS/VMS_Implementations/VMS_impls/VMS__MC_shared

view vmalloc.c @ 140:2c8f3cf6c058

Free memory calculation

author	Merten Sach <msach@mailbox.tu-berlin.de>
date	Mon, 19 Sep 2011 18:43:08 +0200
parents	99798e4438a6
children	79bb48d7d93b

line source

1 /*

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 "vmalloc.h"

19 #include "Histogram/Histogram.h"

21 #define MAX_UINT64 0xFFFFFFFFFFFFFFFF

23 inline void

24 sendFreeReqst_lib(int receiverID, void *ptrToFree, VirtProcr *animPr);

26 inline void

27 sendFreeReqst_master(int receiverID, void *ptrToFree);

29 //A MallocProlog is a head element if the HigherInMem variable is NULL

30 //A Chunk is free if the prevChunkInFreeList variable is NULL

32 /*

33 * This calculates the container which fits the given size.

34 */

35 inline

36 uint32 getContainer(size_t size)

37 {

38 return (log2(size)-LOG128)/LOG54;

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(MallocArrays* freeLists, uint32 containerIdx)

48 {

49 MallocProlog** container = &freeLists->bigChunks[containerIdx];

50 MallocProlog* removedChunk = *container;

51 *container = removedChunk->nextChunkInFreeList;

53 if(removedChunk->nextChunkInFreeList)

54 removedChunk->nextChunkInFreeList->prevChunkInFreeList =

55 (MallocProlog*)container;

57 if(*container == NULL)

58 {

59 if(containerIdx < 64)

60 freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx);

61 else

62 freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64));

63 }

65 return removedChunk;

66 }

68 /*

69 * Removes the first chunk of a freeList

70 * The chunk is removed but not set as free. There is no check if

71 * the free list is empty, so make sure this is not the case.

72 */

73 inline

74 MallocProlog *removeSmallChunk(MallocArrays* freeLists, uint32 containerIdx)

75 {

76 MallocProlog** container = &freeLists->smallChunks[containerIdx];

77 MallocProlog* removedChunk = *container;

78 *container = removedChunk->nextChunkInFreeList;

80 if(removedChunk->nextChunkInFreeList)

81 removedChunk->nextChunkInFreeList->prevChunkInFreeList =

82 (MallocProlog*)container;

84 return removedChunk;

85 }

87 inline

88 size_t getChunkSize(MallocProlog* chunk)

89 {

90 return (uintptr_t)chunk->nextHigherInMem -

91 (uintptr_t)chunk - sizeof(MallocProlog);

92 }

94 /*

95 * Removes a chunk from a free list.

96 */

97 inline

98 void extractChunk(MallocProlog* chunk, MallocArrays *freeLists)

99 {

100 chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;

101 if(chunk->nextChunkInFreeList)

102 chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;

103

104 //The last element in the list points to the container. If the container points

105 //to NULL the container is empty

106 if(*((void**)(chunk->prevChunkInFreeList)) == NULL && getChunkSize(chunk) >= BIG_LOWER_BOUND);

107 {

108 //Find the approppiate container because we do not know it

109 uint64 containerIdx = ((uintptr_t)chunk->prevChunkInFreeList - (uintptr_t)freeLists->bigChunks) >> 3;

110 if(containerIdx < (uint64)64)

111 freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx);

112 if(containerIdx < 128 && containerIdx >=64)

113 freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64));

114

115 }

116 }

117

118 /*

119 * Merges two chunks.

120 * Chunk A has to be before chunk B in memory. Both have to be removed from

121 * a free list

122 */

123 inline

124 MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB)

125 {

126 chunkA->nextHigherInMem = chunkB->nextHigherInMem;

127 chunkB->nextHigherInMem->nextLowerInMem = chunkA;

128 return chunkA;

129 }

130 /*

131 * Inserts a chunk into a free list.

132 */

133 inline

134 void insertChunk(MallocProlog* chunk, MallocProlog** container)

135 {

136 chunk->nextChunkInFreeList = *container;

137 chunk->prevChunkInFreeList = (MallocProlog*)container;

138 if(*container)

139 (*container)->prevChunkInFreeList = chunk;

140 *container = chunk;

141 }

142

143 /*

144 * Divides the chunk that a new chunk of newSize is created.

145 * There is no size check, so make sure the size value is valid.

146 */

147 inline

148 MallocProlog *divideChunk(MallocProlog* chunk, size_t newSize)

149 {

150 MallocProlog* newChunk = (MallocProlog*)((uintptr_t)chunk->nextHigherInMem -

151 newSize - sizeof(MallocProlog));

152

153 newChunk->nextLowerInMem = chunk;

154 newChunk->nextHigherInMem = chunk->nextHigherInMem;

155

156 chunk->nextHigherInMem->nextLowerInMem = newChunk;

157 chunk->nextHigherInMem = newChunk;

158

159 return newChunk;

160 }

161

162 /*

163 * Search for chunk in the list of big chunks. Split the block if it's too big

164 */

165 inline

166 MallocProlog *searchChunk(MallocArrays *freeLists, size_t sizeRequested, uint32 containerIdx)

167 {

168 MallocProlog* foundChunk;

169

170 uint64 searchVector = freeLists->bigChunksSearchVector[0];

171 //set small chunk bits to zero

172 searchVector &= MAX_UINT64 << containerIdx;

173 containerIdx = __builtin_ffsl(searchVector);

174

175 if(containerIdx == 0)

176 {

177 searchVector = freeLists->bigChunksSearchVector[1];

178 containerIdx = __builtin_ffsl(searchVector);

179 if(containerIdx == 0)

180 {

181 printf("VMS malloc failed: low memory");

182 exit(1);

183 }

184 containerIdx += 64;

185 }

186 containerIdx--;

187

188

189 foundChunk = removeChunk(freeLists, containerIdx);

190 size_t chunkSize = getChunkSize(foundChunk);

191

192 //If the new chunk is larger than the requested size: split

193 if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + BIG_LOWER_BOUND)

194 {

195 MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);

196 containerIdx = getContainer(getChunkSize(foundChunk)) - 1;

197 insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]);

198 if(containerIdx < 64)

199 freeLists->bigChunksSearchVector[0] |= ((uint64)1 << containerIdx);

200 else

201 freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (containerIdx-64));

202 foundChunk = newChunk;

203 }

204

205 return foundChunk;

206 }

207

208 /*

209 * This function is called by code which is part of the master loop.

210 * This reads the animating coreID from the MasterEnv and calls the normal malloc

211 * in VMS__malloc_on_core

212 */

213 void *

214 VMS__malloc( size_t sizeRequested)

215 {

216 return VMS__malloc_on_core(sizeRequested, _VMSMasterEnv->currentMasterProcrID);

217 }

218

219 /*

220 * This is called by the plugin. This call to VMS_malloc_on_core is run on the

221 * slave VPs stack so there is no switch to the VMS runtime.

222 */

223 void *

224 VMS__malloc_in_lib(size_t sizeRequested, VirtProcr *VProcr)

225 {

226 return VMS__malloc_on_core(sizeRequested, VProcr->coreAnimatedBy);

227 }

228

229 /*

230 * This is sequential code, meant to only be called from the Master, not from

231 * any slave VPs.

232 */

233 void *VMS__malloc_on_core( size_t sizeRequested, int procrID )

234 {

235 //============================= MEASUREMENT STUFF ========================

236 #ifdef MEAS__TIME_MALLOC

237 int32 startStamp, endStamp;

238 saveLowTimeStampCountInto( startStamp );

239 #endif

240 //========================================================================

241

242 MallocArrays* freeLists = _VMSMasterEnv->freeLists[procrID];

243 MallocProlog* foundChunk;

244 MallocPrologAllocated* returnChunk;

245

246 //Return a small chunk if the requested size is smaller than 128B

247 if(sizeRequested <= LOWER_BOUND)

248 {

249 uint32 freeListIdx = (sizeRequested-1)/SMALL_CHUNK_SIZE;

250 if(freeLists->smallChunks[freeListIdx] == NULL)

251 foundChunk = searchChunk(freeLists, SMALL_CHUNK_SIZE*(freeListIdx+1), 0);

252 else

253 foundChunk = removeSmallChunk(freeLists, freeListIdx);

254

255 _VMSMasterEnv->amtOfOutstandingMem -= getChunkSize(foundChunk) + sizeof(MallocProlog);

256 returnChunk = (MallocPrologAllocated*)foundChunk;

257 returnChunk->prevChunkInFreeList = NULL;//indicates elem currently allocated

258 returnChunk->procrID = procrID;

259 return returnChunk + 1;

260 }

261

262 //Calculate the expected container. Start one higher to have a Chunk that's

263 //always big enough.

264 uint32 containerIdx = getContainer(sizeRequested);

265

266 if(freeLists->bigChunks[containerIdx] == NULL)

267 foundChunk = searchChunk(freeLists, sizeRequested, containerIdx);

268 else

269 foundChunk = removeChunk(freeLists, containerIdx);

270

271 //Mark as allocated

272 _VMSMasterEnv->amtOfOutstandingMem -= getChunkSize(foundChunk) + sizeof(MallocProlog);

273 returnChunk = (MallocPrologAllocated*)foundChunk;

274 returnChunk->prevChunkInFreeList = NULL;//indicates elem currently allocated

275 returnChunk->procrID = procrID;

276

277 //============================= MEASUREMENT STUFF ========================

278 #ifdef MEAS__TIME_MALLOC

279 saveLowTimeStampCountInto( endStamp );

280 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );

281 #endif

282 //========================================================================

283

284 //skip over the prolog by adding its size to the pointer return

285 return returnChunk + 1;

286 }

287

288 /*

289 * This free is called for a master loop. It decides whether the allocation of

290 * chunk was done on the same core. If it was it calls VMS__free_on_core

291 * otherwise it sends a message to the responsible core.

292 */

293 void

294 VMS__free(void *ptrToFree)

295 {

296 MallocPrologAllocated *chunk = (MallocPrologAllocated*)ptrToFree - 1;

297 if(chunk->procrID == _VMSMasterEnv->currentMasterProcrID)

298 {

299 VMS__free_on_core(ptrToFree, _VMSMasterEnv->currentMasterProcrID);

300 }

301 else

302 {

303 sendFreeReqst_master(chunk->procrID, ptrToFree);

304

305 }

306 }

307

308 /*

309 * This free is called for the plugins. It decides whether the allocation of

310 * chunk was done on the same core. If it was it calls VMS__free_on_core

311 * otherwise it sends a message to the responsible core.

312 */

313 void

314 VMS__free_in_lib(void *ptrToFree, VirtProcr *VProc)

315 {

316 MallocPrologAllocated *chunk = (MallocPrologAllocated*)ptrToFree - 1;

317 if(chunk->procrID == VProc->coreAnimatedBy)

318 {

319 VMS__free_on_core(ptrToFree, VProc->coreAnimatedBy);

320 }

321 else

322 {

323 sendFreeReqst_lib(chunk->procrID, ptrToFree, VProc);

324 }

325 }

326

327 /*

328 * This is called form a masterVP and request an free from a different masterVP.

329 * The free of the request structure is done after the request is handled.

330 */

331 inline void

332 sendFreeReqst_master(int receiverID, void *ptrToFree)

333 {

334 InterVMSCoreReqst *freeReqst = VMS__malloc(sizeof(InterVMSCoreReqst));

335 freeReqst->freePtr = ptrToFree;

336 freeReqst->secondReqType = transfer_free_ptr;

337

338 sendInterMasterReqst(receiverID, (InterMasterReqst*)freeReqst);

339 }

340

341 /*

342 * This is called if the free is called from the plugin. This requests an inter

343 * master request from his master.

344 */

345 inline void

346 sendFreeReqst_lib(int receiverID, void *ptrToFree, VirtProcr *animPr )

347 {

348 VMSSemReq reqData;

349 InterVMSCoreReqst *freeReqst = VMS__malloc(sizeof(InterVMSCoreReqst));

350 freeReqst->freePtr = ptrToFree;

351 freeReqst->secondReqType = transfer_free_ptr;

352

353 reqData.reqType = interMasterReqst;

354 reqData.receiverID = receiverID;

355 reqData.data = (void*)freeReqst;

356

357 VMS__send_VMSSem_request( (void*)&reqData, animPr );

358 }

359

360 /*

361 * This is sequential code, meant to only be called from the Master, not from

362 * any slave VPs.

363 */

364 void

365 VMS__free_on_core( void *ptrToFree, int procrID )

366 {

367

368 //============================= MEASUREMENT STUFF ========================

369 #ifdef MEAS__TIME_MALLOC

370 int32 startStamp, endStamp;

371 saveLowTimeStampCountInto( startStamp );

372 #endif

373 //========================================================================

374

375 MallocArrays* freeLists = _VMSMasterEnv->freeLists[procrID];

376 MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1;

377 uint32 containerIdx;

378 _VMSMasterEnv->amtOfOutstandingMem += getChunkSize(chunkToFree) + sizeof(MallocProlog);

379

380 //Check for free neighbors

381 if(chunkToFree->nextLowerInMem)

382 {

383 if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)

384 {//Chunk is not allocated

385 extractChunk(chunkToFree->nextLowerInMem, freeLists);

386 chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);

387 }

388 }

389 if(chunkToFree->nextHigherInMem)

390 {

391 if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL)

392 {//Chunk is not allocated

393 extractChunk(chunkToFree->nextHigherInMem, freeLists);

394 chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem);

395 }

396 }

397

398 size_t chunkSize = getChunkSize(chunkToFree);

399 if(chunkSize < BIG_LOWER_BOUND)

400 {

401 containerIdx = (chunkSize/SMALL_CHUNK_SIZE)-1;

402 if(containerIdx > SMALL_CHUNK_COUNT-1)

403 containerIdx = SMALL_CHUNK_COUNT-1;

404 insertChunk(chunkToFree, &freeLists->smallChunks[containerIdx]);

405 }

406 else

407 {

408 containerIdx = getContainer(getChunkSize(chunkToFree)) - 1;

409 insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);

410 if(containerIdx < 64)

411 freeLists->bigChunksSearchVector[0] |= (uint64)1 << containerIdx;

412 else

413 freeLists->bigChunksSearchVector[1] |= (uint64)1 << (containerIdx-64);

414 }

415

416 //============================= MEASUREMENT STUFF ========================

417 #ifdef MEAS__TIME_MALLOC

418 saveLowTimeStampCountInto( endStamp );

419 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist );

420 #endif

421 //========================================================================

422

423 }

424

425 /*

426 * Designed to be called from the main thread outside of VMS, during init

427 */

428 MallocArrays *

429 VMS_ext__create_free_list()

430 {

431 //Initialize containers for small chunks and fill with zeros

432 MallocArrays *freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) );

433

434 freeLists->smallChunks =

435 (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*));

436 memset((void*)freeLists->smallChunks,

437 0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*));

438

439 //Calculate number of containers for big chunks

440 uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;

441 freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*));

442 memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*));

443 freeLists->containerCount = container;

444

445 //Create first element in lastContainer

446 MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );

447 if( firstChunk == NULL ) {printf("Can't allocate initial memory\n"); exit(1);}

448 freeLists->memSpace = firstChunk;

449

450 //Touch memory to avoid page faults

451 void *ptr,*endPtr;

452 endPtr = (void*)firstChunk+MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE;

453 for(ptr = firstChunk; ptr < endPtr; ptr+=PAGE_SIZE)

454 {

455 *(char*)ptr = 0;

456 }

457

458 firstChunk->nextLowerInMem = NULL;

459 firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk +

460 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog*));

461 firstChunk->nextChunkInFreeList = NULL;

462 //previous element in the queue is the container

463 firstChunk->prevChunkInFreeList = (MallocProlog*)&freeLists->bigChunks[container-2];

464

465 freeLists->bigChunks[container-2] = firstChunk;

466 //Insert into bit search list

467 if(container <= 65)

468 freeLists->bigChunksSearchVector[0] = ((uint64)1 << (container-2));

469 else

470 freeLists->bigChunksSearchVector[1] = ((uint64)1 << (container-66));

471

472 //Create dummy chunk to mark the top of stack this is of course

473 //never freed

474 MallocProlog *dummyChunk = firstChunk->nextHigherInMem;

475 dummyChunk->nextHigherInMem = dummyChunk+1;

476 dummyChunk->nextLowerInMem = NULL;

477 dummyChunk->nextChunkInFreeList = NULL;

478 dummyChunk->prevChunkInFreeList = NULL;

479

480 return freeLists;

481 }

482

483

484 /*Designed to be called from the main thread outside of VMS, during cleanup

485 */

486 void

487 VMS_ext__free_free_list( MallocArrays *freeLists )

488 {

489 free(freeLists->memSpace);

490 free(freeLists->bigChunks);

491 free(freeLists->smallChunks);

492 free(freeLists);

493 }

494

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

view vmalloc.c @ 140:2c8f3cf6c058