VMS/VMS_Implementations/VMS_impls/VMS__MC_shared

view vmalloc.c @ 139:99798e4438a6

Merge of Malloc2 and inter master requests

author	Merten Sach <msach@mailbox.tu-berlin.de>
date	Mon, 19 Sep 2011 16:12:01 +0200
parents	d0aa5a796fc5 99343ffe1918
children	2c8f3cf6c058

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 "Histogram/Histogram.h"

20 #define MAX_UINT64 0xFFFFFFFFFFFFFFFF

22 inline void

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

25 inline void

26 sendFreeReqst_master(int receiverID, void *ptrToFree);

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

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

31 /*

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

33 */

34 inline

35 uint32 getContainer(size_t size)

36 {

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

38 }

40 /*

41 * Removes the first chunk of a freeList

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

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

44 */

45 inline

46 MallocProlog *removeChunk(MallocArrays* freeLists, uint32 containerIdx)

47 {

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

49 MallocProlog* removedChunk = *container;

50 *container = removedChunk->nextChunkInFreeList;

52 if(removedChunk->nextChunkInFreeList)

53 removedChunk->nextChunkInFreeList->prevChunkInFreeList =

54 (MallocProlog*)container;

56 if(*container == NULL)

57 {

58 if(containerIdx < 64)

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

60 else

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

62 }

64 return removedChunk;

65 }

67 /*

68 * Removes the first chunk of a freeList

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

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

71 */

72 inline

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

74 {

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

76 MallocProlog* removedChunk = *container;

77 *container = removedChunk->nextChunkInFreeList;

79 if(removedChunk->nextChunkInFreeList)

80 removedChunk->nextChunkInFreeList->prevChunkInFreeList =

81 (MallocProlog*)container;

83 return removedChunk;

84 }

86 inline

87 size_t getChunkSize(MallocProlog* chunk)

88 {

89 return (uintptr_t)chunk->nextHigherInMem -

90 (uintptr_t)chunk - sizeof(MallocProlog);

91 }

93 /*

94 * Removes a chunk from a free list.

95 */

96 inline

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

98 {

99 chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;

100 if(chunk->nextChunkInFreeList)

101 chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;

102

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

104 //to NULL the container is empty

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

106 {

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

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

109 if(containerIdx < (uint32)64)

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

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

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

113

114 }

115 }

116

117 /*

118 * Merges two chunks.

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

120 * a free list

121 */

122 inline

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

124 {

125 chunkA->nextHigherInMem = chunkB->nextHigherInMem;

126 chunkB->nextHigherInMem->nextLowerInMem = chunkA;

127 return chunkA;

128 }

129 /*

130 * Inserts a chunk into a free list.

131 */

132 inline

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

134 {

135 chunk->nextChunkInFreeList = *container;

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

137 if(*container)

138 (*container)->prevChunkInFreeList = chunk;

139 *container = chunk;

140 }

141

142 /*

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

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

145 */

146 inline

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

148 {

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

150 newSize - sizeof(MallocProlog));

151

152 newChunk->nextLowerInMem = chunk;

153 newChunk->nextHigherInMem = chunk->nextHigherInMem;

154

155 chunk->nextHigherInMem->nextLowerInMem = newChunk;

156 chunk->nextHigherInMem = newChunk;

157

158 return newChunk;

159 }

160

161 /*

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

163 */

164 inline

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

166 {

167 MallocProlog* foundChunk;

168

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

170 //set small chunk bits to zero

171 searchVector &= MAX_UINT64 << containerIdx;

172 containerIdx = __builtin_ffsl(searchVector);

173

174 if(containerIdx == 0)

175 {

176 searchVector = freeLists->bigChunksSearchVector[1];

177 containerIdx = __builtin_ffsl(searchVector);

178 if(containerIdx == 0)

179 {

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

181 exit(1);

182 }

183 containerIdx += 64;

184 }

185 containerIdx--;

186

187

188 foundChunk = removeChunk(freeLists, containerIdx);

189 size_t chunkSize = getChunkSize(foundChunk);

190

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

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

193 {

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

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

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

197 if(containerIdx < 64)

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

199 else

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

201 foundChunk = newChunk;

202 }

203

204 return foundChunk;

205 }

206

207 /*

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

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

210 * in VMS__malloc_on_core

211 */

212 void *

213 VMS__malloc( size_t sizeRequested)

214 {

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

216 }

217

218 /*

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

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

221 */

222 void *

223 VMS__malloc_in_lib(size_t sizeRequested, VirtProcr *VProcr)

224 {

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

226 }

227

228 /*

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

230 * any slave VPs.

231 */

232 void *VMS__malloc_on_core( size_t sizeRequested, int procrID )

233 {

234 //============================= MEASUREMENT STUFF ========================

235 #ifdef MEAS__TIME_MALLOC

236 int32 startStamp, endStamp;

237 saveLowTimeStampCountInto( startStamp );

238 #endif

239 //========================================================================

240

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

242 MallocProlog* foundChunk;

243 MallocPrologAllocated* returnChunk;

244

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

246 if(sizeRequested <= LOWER_BOUND)

247 {

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

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

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

251 else

252 foundChunk = removeSmallChunk(freeLists, freeListIdx);

253

254 returnChunk = (MallocPrologAllocated*)foundChunk;

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

256 returnChunk->procrID = procrID;

257 return returnChunk + 1;

258 }

259

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

261 //always big enough.

262 uint32 containerIdx = getContainer(sizeRequested);

263

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

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

266 else

267 foundChunk = removeChunk(freeLists, containerIdx);

268

269 //Mark as allocated

270 returnChunk = (MallocPrologAllocated*)foundChunk;

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

272 returnChunk->procrID = procrID;

273

274 //============================= MEASUREMENT STUFF ========================

275 #ifdef MEAS__TIME_MALLOC

276 saveLowTimeStampCountInto( endStamp );

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

278 #endif

279 //========================================================================

280

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

282 return returnChunk + 1;

283 }

284

285 /*

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

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

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

289 */

290 void

291 VMS__free(void *ptrToFree)

292 {

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

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

295 {

296 VMS__free_on_core(ptrToFree, _VMSMasterEnv->currentMasterProcrID);

297 }

298 else

299 {

300 sendFreeReqst_master(chunk->procrID, ptrToFree);

301

302 }

303 }

304

305 /*

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

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

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

309 */

310 void

311 VMS__free_in_lib(void *ptrToFree, VirtProcr *VProc)

312 {

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

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

315 {

316 VMS__free_on_core(ptrToFree, VProc->coreAnimatedBy);

317 }

318 else

319 {

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

321 }

322 }

323

324 /*

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

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

327 */

328 inline void

329 sendFreeReqst_master(int receiverID, void *ptrToFree)

330 {

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

332 freeReqst->freePtr = ptrToFree;

333 freeReqst->secondReqType = transfer_free_ptr;

334

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

336 }

337

338 /*

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

340 * master request from his master.

341 */

342 inline void

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

344 {

345 VMSSemReq reqData;

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

347 freeReqst->freePtr = ptrToFree;

348 freeReqst->secondReqType = transfer_free_ptr;

349

350 reqData.reqType = interMasterReqst;

351 reqData.receiverID = receiverID;

352 reqData.data = (void*)freeReqst;

353

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

355 }

356

357 /*

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

359 * any slave VPs.

360 */

361 void

362 VMS__free_on_core( void *ptrToFree, int procrID )

363 {

364

365 //============================= MEASUREMENT STUFF ========================

366 #ifdef MEAS__TIME_MALLOC

367 int32 startStamp, endStamp;

368 saveLowTimeStampCountInto( startStamp );

369 #endif

370 //========================================================================

371

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

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

374 uint32 containerIdx;

375

376 //Check for free neighbors

377 if(chunkToFree->nextLowerInMem)

378 {

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

380 {//Chunk is not allocated

381 extractChunk(chunkToFree->nextLowerInMem, freeLists);

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

383 }

384 }

385 if(chunkToFree->nextHigherInMem)

386 {

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

388 {//Chunk is not allocated

389 extractChunk(chunkToFree->nextHigherInMem, freeLists);

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

391 }

392 }

393

394 size_t chunkSize = getChunkSize(chunkToFree);

395 if(chunkSize < BIG_LOWER_BOUND)

396 {

397 containerIdx = (chunkSize/SMALL_CHUNK_SIZE)-1;

398 if(containerIdx > SMALL_CHUNK_COUNT-1)

399 containerIdx = SMALL_CHUNK_COUNT-1;

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

401 }

402 else

403 {

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

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

406 if(containerIdx < 64)

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

408 else

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

410 }

411

412 //============================= MEASUREMENT STUFF ========================

413 #ifdef MEAS__TIME_MALLOC

414 saveLowTimeStampCountInto( endStamp );

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

416 #endif

417 //========================================================================

418

419 }

420

421 /*

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

423 */

424 MallocArrays *

425 VMS_ext__create_free_list()

426 {

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

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

429

430 freeLists->smallChunks =

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

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

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

434

435 //Calculate number of containers for big chunks

436 uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;

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

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

439 freeLists->containerCount = container;

440

441 //Create first element in lastContainer

442 MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );

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

444 freeLists->memSpace = firstChunk;

445

446 //Touch memory to avoid page faults

447 void *ptr,*endPtr;

448 endPtr = (void*)firstChunk+MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE;

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

450 {

451 *(char*)ptr = 0;

452 }

453

454 firstChunk->nextLowerInMem = NULL;

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

456 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog*));

457 firstChunk->nextChunkInFreeList = NULL;

458 //previous element in the queue is the container

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

460

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

462 //Insert into bit search list

463 if(container <= 65)

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

465 else

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

467

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

469 //never freed

470 MallocProlog *dummyChunk = firstChunk->nextHigherInMem;

471 dummyChunk->nextHigherInMem = dummyChunk+1;

472 dummyChunk->nextLowerInMem = NULL;

473 dummyChunk->nextChunkInFreeList = NULL;

474 dummyChunk->prevChunkInFreeList = NULL;

475

476 return freeLists;

477 }

478

479

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

481 */

482 void

483 VMS_ext__free_free_list( MallocArrays *freeLists )

484 {

485 free(freeLists->memSpace);

486 free(freeLists->bigChunks);

487 free(freeLists->smallChunks);

488 free(freeLists);

489 }

490

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

view vmalloc.c @ 139:99798e4438a6