VMS/VMS_Implementations/VMS_impls/VMS__MC_shared

view vmalloc.c @ 116:35547e66b971

malloc: multiple small chunk allocation

author	Merten Sach <msach@mailbox.tu-berlin.de>
date	Mon, 29 Aug 2011 17:09:00 +0200
parents	62c59f2ac9f1
children	07e679ee2095

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 //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 (log10(size)-LOG128)/LOG54;

32 }

34 /*

35 * This calculates the size of a given container

36 */

37 inline

38 size_t getContainerSize(uint32 idx)

39 {

40 return pow(CHUNK_INCREASE_RATE,idx)*LOWER_BOUND;

41 }

43 /*

44 * Removes the first chunk of a freeList

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

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

47 */

48 inline

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

50 {

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

52 MallocProlog* removedChunk = *container;

53 *container = removedChunk->nextChunkInFreeList;

55 if(removedChunk->nextChunkInFreeList)

56 removedChunk->nextChunkInFreeList->prevChunkInFreeList =

57 (MallocProlog*)container;

59 if(*container == NULL)

60 {

61 if(containerIdx < 64)

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

63 else

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

65 }

67 return removedChunk;

68 }

70 /*

71 * Removes the first chunk of a freeList

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

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

74 */

75 inline

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

77 {

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

79 MallocProlog* removedChunk = *container;

80 *container = removedChunk->nextChunkInFreeList;

82 if(removedChunk->nextChunkInFreeList)

83 removedChunk->nextChunkInFreeList->prevChunkInFreeList =

84 (MallocProlog*)container;

86 return removedChunk;

87 }

89 inline

90 void recycleSmallChunks(MallocProlog** container)

91 {

92 //TODO recycle small chunks

93 }

95 /*

96 * Removes a chunk from a free list.

97 */

98 inline

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

100 {

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

102 if(chunk->nextChunkInFreeList)

103 chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;

104

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

106 //to NULL the container is empty

107 if(*((void**)(chunk->prevChunkInFreeList)) == NULL)

108 {

109 uint32 containerIdx = ((uintptr_t)chunk->prevChunkInFreeList - (uintptr_t)freeLists->bigChunks) >> 6;

110 if(containerIdx < (uint32)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 * 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 return chunkA;

127 }

128 /*

129 * Inserts a chunk into a free list.

130 */

131 inline

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

133 {

134 chunk->nextChunkInFreeList = *container;

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

136 if(*container)

137 (*container)->prevChunkInFreeList = chunk;

138 *container = chunk;

139 }

140

141 /*

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

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

144 */

145 inline

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

147 {

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

149 newSize - sizeof(MallocProlog));

150

151 newChunk->nextLowerInMem = chunk;

152 newChunk->nextHigherInMem = chunk->nextHigherInMem;

153

154 chunk->nextHigherInMem = newChunk;

155 chunk->nextHigherInMem->nextLowerInMem = newChunk;

156

157 return newChunk;

158 }

159

160 inline

161 size_t getChunkSize(MallocProlog* chunk)

162 {

163 return (uintptr_t)chunk->nextHigherInMem -

164 (uintptr_t)chunk - sizeof(MallocProlog);

165 }

166

167

168 /*

169 * This makes 5 Chunks of the requested size.

170 */

171 inline

172 void makeChunks(size_t size, MallocProlog **container)

173 {

174 MallocArrays *freeLists = _VMSMasterEnv->freeLists;

175 size_t addedSize = 5*(size + sizeof(MallocProlog));

176

177 uint32 containerIdx = getContainer(addedSize)+4;

178 while(freeLists->bigChunks[containerIdx] == NULL )

179 containerIdx++;

180

181 MallocProlog *foundChunk = removeChunk(freeLists, containerIdx);

182

183 int i;

184 for(i=0; i<5; i++)

185 {

186 insertChunk(divideChunk(foundChunk,size), container);

187 }

188 containerIdx = getContainer(getChunkSize(foundChunk));

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

190 if(containerIdx < 64)

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

192 else

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

194 }

195

196 /*

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

198 * any slave VPs.

199 */

200 void *VMS__malloc( size_t sizeRequested )

201 {

202 //============================= MEASUREMENT STUFF ========================

203 #ifdef MEAS__TIME_MALLOC

204 int32 startStamp, endStamp;

205 saveLowTimeStampCountInto( startStamp );

206 #endif

207 //========================================================================

208

209 MallocArrays* freeLists = _VMSMasterEnv->freeLists;

210

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

212 if(sizeRequested <= LOWER_BOUND)

213 {

214 uint32 freeListIdx = (sizeRequested-1)/32;

215 if(freeLists->smallChunkCount[freeListIdx] == 0)

216 {

217 makeChunks((freeListIdx+1)*32, &freeLists->smallChunks[freeListIdx]);

218 freeLists->smallChunkCount[freeListIdx] += 5;

219 }

220

221 freeLists->smallChunkCount[freeListIdx]--;

222 return removeSmallChunk(freeLists, freeListIdx) + 1;

223 }

224

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

226 //always big enough.

227 uint32 containerIdx = getContainer(sizeRequested) + 1;

228

229 MallocProlog* foundChunk;

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

231 {

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

233 //set small chunk bits to zero

234 searchVector &= MAX_UINT64 << containerIdx;

235 containerIdx = __builtin_ffsl(searchVector);

236

237 if(containerIdx == 0)

238 {

239 searchVector = freeLists->bigChunksSearchVector[1];

240 containerIdx = __builtin_ffsl(searchVector);

241 if(containerIdx == 0)

242 {

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

244 exit(1);

245 }

246 containerIdx += 64;

247 }

248 containerIdx--;

249

250

251 foundChunk = removeChunk(freeLists, containerIdx);

252 size_t chunkSize = getChunkSize(foundChunk);

253

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

255 if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + LOWER_BOUND)

256 {

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

258 containerIdx = getContainer(getChunkSize(foundChunk));

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

260 if(containerIdx < 64)

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

262 else

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

264 foundChunk = newChunk;

265 }

266 }

267 else

268 {

269 foundChunk = removeChunk(freeLists, containerIdx);

270 }

271

272 //Mark as allocated

273 foundChunk->prevChunkInFreeList = NULL;

274

275 //============================= MEASUREMENT STUFF ========================

276 #ifdef MEAS__TIME_MALLOC

277 saveLowTimeStampCountInto( endStamp );

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

279 #endif

280 //========================================================================

281

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

283 return foundChunk + 1;

284 }

285

286 /*

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

288 * any slave VPs.

289 */

290 void

291 VMS__free( void *ptrToFree )

292 {

293

294 //============================= MEASUREMENT STUFF ========================

295 #ifdef MEAS__TIME_MALLOC

296 int32 startStamp, endStamp;

297 saveLowTimeStampCountInto( startStamp );

298 #endif

299 //========================================================================

300

301 MallocArrays* freeLists = _VMSMasterEnv->freeLists;

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

303 uint32 containerIdx;

304

305 size_t chunkSize = getChunkSize(chunkToFree);

306 if(chunkSize <= LOWER_BOUND)

307 {

308 containerIdx = (chunkSize-1)/32;

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

310 freeLists->smallChunkCount[containerIdx]++;

311

312 if(freeLists->smallChunkCount[containerIdx] > 20)

313 recycleSmallChunks(&freeLists->smallChunks[containerIdx]);

314

315 return;

316 }

317

318 //Check for free neighbors

319 if(chunkToFree->nextLowerInMem)

320 {

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

322 {//Chunk is not allocated

323 if(getChunkSize(chunkToFree->nextLowerInMem) > LOWER_BOUND)

324 {

325 extractChunk(chunkToFree->nextLowerInMem, freeLists);

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

327 }

328 }

329 }

330 if(chunkToFree->nextHigherInMem)

331 {

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

333 {//Chunk is not allocated

334 if(getChunkSize(chunkToFree->nextHigherInMem) > LOWER_BOUND)

335 {

336 extractChunk(chunkToFree->nextHigherInMem, freeLists);

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

338 }

339 }

340 }

341

342 containerIdx = getContainer(getChunkSize(chunkToFree));

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

344 if(containerIdx < 64)

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

346 else

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

348

349 //============================= MEASUREMENT STUFF ========================

350 #ifdef MEAS__TIME_MALLOC

351 saveLowTimeStampCountInto( endStamp );

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

353 #endif

354 //========================================================================

355

356 }

357

358

359 /*Allocates memory from the external system -- higher overhead

360 *

361 *Because of Linux's malloc throwing bizarre random faults when malloc is

362 * used inside a VMS virtual processor, have to pass this as a request and

363 * have the core loop do it when it gets around to it -- will look for these

364 * chores leftover from the previous animation of masterVP the next time it

365 * goes to animate the masterVP -- so it takes two separate masterVP

366 * animations, separated by work, to complete an external malloc or

367 * external free request.

368 *

369 *Thinking core loop accepts signals -- just looks if signal-location is

370 * empty or not --

371 */

372 void *

373 VMS__malloc_in_ext( size_t sizeRequested )

374 {

375 /*

376 //This is running in the master, so no chance for multiple cores to be

377 // competing for the core's flag.

378 if( *(_VMSMasterEnv->coreLoopSignalAddr[ 0 ]) != 0 )

379 { //something has already signalled to core loop, so save the signal

380 // and look, next time master animated, to see if can send it.

381 //Note, the addr to put a signal is in the coreloop's frame, so just

382 // checks it each time through -- make it volatile to avoid GCC

383 // optimizations -- it's a coreloop local var that only changes

384 // after jumping away. The signal includes the addr to send the

385 //return to -- even if just empty return completion-signal

386 //

387 //save the signal in some queue that the master looks at each time

388 // it starts up -- one loc says if empty for fast common case --

389 //something like that -- want to hide this inside this call -- but

390 // think this has to come as a request -- req handler gives procr

391 // back to master loop, which gives it back to req handler at point

392 // it sees that core loop has sent return signal. Something like

393 // that.

394 saveTheSignal

395

396 }

397 coreSigData->type = malloc;

398 coreSigData->sizeToMalloc = sizeRequested;

399 coreSigData->locToSignalCompletion = &figureOut;

400 _VMSMasterEnv->coreLoopSignals[ 0 ] = coreSigData;

401 */

402 //just risk system-stack faults until get this figured out

403 return malloc( sizeRequested );

404 }

405

406

407 /*Frees memory that was allocated in the external system -- higher overhead

408 *

409 *As noted in external malloc comment, this is clunky 'cause the free has

410 * to be called in the core loop.

411 */

412 void

413 VMS__free_in_ext( void *ptrToFree )

414 {

415 //just risk system-stack faults until get this figured out

416 free( ptrToFree );

417

418 //TODO: fix this -- so

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 _VMSMasterEnv->freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) );

429 MallocArrays *freeLists = _VMSMasterEnv->freeLists;

430

431 freeLists->smallChunks =

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

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

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

435 memset((void*)freeLists->smallChunkCount,

436 0,SMALL_CHUNK_COUNT*sizeof(uint32));

437

438 //Calculate number of containers for big chunks

439 uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;

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

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

442 freeLists->containerCount = container;

443

444 //Create first element in lastContainer

445 MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );

446 if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);}

447 freeLists->memSpace = firstChunk;

448

449 firstChunk->nextLowerInMem = NULL;

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

451 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog*));

452 firstChunk->nextChunkInFreeList = NULL;

453 //previous element in the queue is the container

454 firstChunk->prevChunkInFreeList = freeLists->bigChunks[container-1];

455

456 freeLists->bigChunks[container-1] = firstChunk;

457 //Insert into bit search list

458 if(container <= 64)

459 freeLists->bigChunksSearchVector[0] |= ((uint64)1 << (container-1));

460 else

461 freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (container-65));

462

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

464 //never freed

465 MallocProlog *dummyChunk = firstChunk->nextHigherInMem;

466 dummyChunk->nextHigherInMem = dummyChunk+1;

467 dummyChunk->nextLowerInMem = NULL;

468 dummyChunk->nextChunkInFreeList = NULL;

469 dummyChunk->prevChunkInFreeList = NULL;

470

471 return freeLists;

472 }

473

474

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

476 */

477 void

478 VMS_ext__free_free_list( MallocArrays *freeLists )

479 {

480 free(freeLists->memSpace);

481 free(freeLists->bigChunks);

482 free(freeLists->smallChunks);

483

484 }

485

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

view vmalloc.c @ 116:35547e66b971