Source:SLASH'EM 0.0.7E7F2/alloc.c
Revision as of 18:45, 7 March 2008 by Kernigh bot (talk | contribs) (SLASH'EM 0.0.7E7F2/alloc.c moved to Source:SLASH'EM 0.0.7E7F2/alloc.c: Robot: moved page)
Below is the full text to alloc.c from the source code of SLASH'EM 0.0.7E7F2. To link to a particular line, write [[SLASH'EM 0.0.7E7F2/alloc.c#line123]], for example.
The latest source code for vanilla NetHack is at Source code.
The NetHack General Public License applies to screenshots, source code and other content from NetHack.
This content was modified from the original NetHack source code distribution (by splitting up NetHack content between wiki pages, and possibly further editing). See the page history for a list of who changed it, and on what dates.
1. /* SCCS Id: @(#)alloc.c 3.4 1995/10/04 */ 2. /* Copyright (c) Stichting Mathematisch Centrum, Amsterdam, 1985. */ 3. /* NetHack may be freely redistributed. See license for details. */ 4. 5. /* to get the malloc() prototype from system.h */ 6. #define ALLOC_C /* comment line for pre-compiled headers */ 7. /* since this file is also used in auxiliary programs, don't include all the 8. * function declarations for all of nethack 9. */ 10. #define EXTERN_H /* comment line for pre-compiled headers */ 11. #include "config.h" 12. 13. /* [Ali] 14. * There are a number of preprocessor symbols which affect how this 15. * file is compiled: 16. * 17. * NHALLOC_DLL When set this causes the alloc module to build as a stand-alone 18. * allocator (which can either be used in object form for use 19. * with utility programs or combined with panic.o to form a DLL 20. * for dynamic linking with the game - this last allows for the 21. * possibility of 3rd party libraries to allocate memory via the 22. * module and thus be represented in the heap monitoring). 23. * 24. * Global symbols defined: malloc, calloc etc. 25. * monitor_heap_push, monitor_heap_pop etc. 26. * 27. * Warning: The version of panic defined in panic.o does _not_ 28. * attempt to save the game. nhalloc.dll should therefore only be 29. * used for testing. 30. * 31. * WIZARD When set this causes the definition of the fmt_ptr function. 32. * 33. * MONITOR_HEAP When set this causes the alloc module to define the nhalloc and 34. * nhfree functions (which can then be used by the alloc and free 35. * macros). This allows some basic monitoring of the heap for 36. * memory leaks by dumping the heap to a log file on exit. 37. * 38. * Note: This symbol also causes fmt_ptr to be defined. 39. * 40. * Note: If the INTERNAL_MALLOC symbol is also defined, then 41. * nhalloc and nhfree will use the monitor_heap_ functions to 42. * store information about where the memory was allocated from. 43. * Unless compiling on the WIN32 platform, this will also cause 44. * the definition of the monitor_heap_ functions, the trivial 45. * allocator and a standard front end (malloc and friends). 46. * On the WIN32 platform, the monitor_heap_ and standard allocator 47. * functions are left as external references. 48. */ 49. 50. /* to get the definitons of ENOMEM and errno */ 51. #if defined(NHALLOC_DLL) || defined(MONITOR_HEAP) && defined(INTERNAL_MALLOC) 52. #include <stdlib.h> 53. #include <errno.h> 54. #ifdef WIN32 55. #include <win32api.h> 56. #endif 57. #endif 58. 59. #ifdef NHALLOC_DLL 60. #undef free 61. #else /* NHALLOC_DLL */ 62. #if defined(MONITOR_HEAP) || defined(WIZARD) 63. char *FDECL(fmt_ptr, (const genericptr,char *)); 64. #endif 65. 66. #ifdef MONITOR_HEAP 67. #undef alloc 68. #undef free 69. extern void FDECL(free,(genericptr_t)); 70. static void NDECL(heapmon_init); 71. 72. static FILE *heaplog = 0; 73. static boolean tried_heaplog = FALSE; 74. #endif 75. 76. long *FDECL(alloc,(unsigned int)); 77. extern void VDECL(panic, (const char *,...)) PRINTF_F(1,2); 78. 79. 80. long * 81. alloc(lth) 82. register unsigned int lth; 83. { 84. #ifdef LINT 85. /* 86. * a ridiculous definition, suppressing 87. * "possible pointer alignment problem" for (long *) malloc() 88. * from lint 89. */ 90. long dummy = ftell(stderr); 91. 92. if(lth) dummy = 0; /* make sure arg is used */ 93. return(&dummy); 94. #else 95. register genericptr_t ptr; 96. 97. ptr = malloc(lth); 98. #ifndef MONITOR_HEAP 99. if (!ptr) panic("Memory allocation failure; cannot get %u bytes", lth); 100. #endif 101. return((long *) ptr); 102. #endif 103. } 104. 105. 106. #if defined(MONITOR_HEAP) || defined(WIZARD) 107. 108. # if defined(MICRO) || defined(WIN32) 109. /* we actually want to know which systems have an ANSI run-time library 110. * to know which support the new %p format for printing pointers. 111. * due to the presence of things like gcc, NHSTDC is not a good test. 112. * so we assume microcomputers have all converted to ANSI and bigger 113. * computers which may have older libraries give reasonable results with 114. * the cast. 115. */ 116. # define MONITOR_PTR_FMT 117. # endif 118. 119. # ifdef MONITOR_PTR_FMT 120. # define PTR_FMT "%p" 121. # define PTR_TYP genericptr_t 122. # else 123. # define PTR_FMT "%06lx" 124. # define PTR_TYP unsigned long 125. # endif 126. 127. /* format a pointer for display purposes; caller supplies the result buffer */ 128. char * 129. fmt_ptr(ptr, buf) 130. const genericptr ptr; 131. char *buf; 132. { 133. Sprintf(buf, PTR_FMT, (PTR_TYP)ptr); 134. return buf; 135. } 136. 137. #endif /* MONITOR_HEAP || WIZARD */ 138. #endif /* !NHALLOC_DLL */ 139. 140. #if defined(MONITOR_HEAP) && !defined(NHALLOC_DLL) 141. 142. /* If ${NH_HEAPLOG} is defined and we can create a file by that name, 143. then we'll log the allocation and release information to that file. */ 144. static void 145. heapmon_init() 146. { 147. char *logname = getenv("NH_HEAPLOG"); 148. 149. if (logname && *logname) 150. heaplog = fopen(logname, "w"); 151. tried_heaplog = TRUE; 152. } 153. 154. long * 155. nhalloc(lth, file, line) 156. unsigned int lth; 157. const char *file; 158. int line; 159. { 160. long *ptr; 161. char ptr_address[20]; 162. 163. #ifdef INTERNAL_MALLOC 164. monitor_heap_push(file, line); 165. #endif 166. ptr = alloc(lth); 167. #ifdef INTERNAL_MALLOC 168. (void)monitor_heap_pop(file, line, 0); 169. #endif 170. if (!tried_heaplog) heapmon_init(); 171. if (heaplog) 172. (void) fprintf(heaplog, "+%5u %s %4d %s\n", lth, 173. fmt_ptr((genericptr_t)ptr, ptr_address), 174. line, file); 175. /* potential panic in alloc() was deferred til here */ 176. if (!ptr) panic("Cannot get %u bytes, line %d of %s", 177. lth, line, file); 178. 179. return ptr; 180. } 181. 182. void 183. nhfree(ptr, file, line) 184. genericptr_t ptr; 185. const char *file; 186. int line; 187. { 188. char ptr_address[20]; 189. 190. if (!tried_heaplog) heapmon_init(); 191. if (heaplog) 192. (void) fprintf(heaplog, "- %s %4d %s\n", 193. fmt_ptr((genericptr_t)ptr, ptr_address), 194. line, file); 195. 196. free(ptr); 197. } 198. #endif /* MONITOR_HEAP && !NHALLOC_DLL */ 199. 200. /* 201. * Under Win32, the trivial allocator and monitor front end are 202. * placed in nhalloc.dll rather than in the main executable. 203. */ 204. 205. #if defined(NHALLOC_DLL) || (defined(INTERNAL_MALLOC) && !defined(WIN32)) 206. /* 207. * [Ali] A trivial malloc implementation. 208. * 209. * Notes: 210. * 211. * If attempting to port to a non-UNIX environment, you will need 212. * a replacement for the sbrk() call. Under UNIX, sbrk() returns 213. * contiguous blocks. If there is no equivalent call in the target 214. * environment, you will either need to make this allocator rather 215. * more intelligent, or just increase PAGESIZE to something huge like 216. * 1Mb to keep the resultant fragmentation under control. 217. * 218. * The alignment implementation is advisory at best; we assume that 219. * if the target enviroment is that bothered by alignment, sbrk() 220. * will return aligned blocks and the compiler will pad the triv_head 221. * structure appropriately. If either of these assumptions is not 222. * correct, the alignment will be relaxed, which is presumably okay. 223. * 224. * This implementation is _very_ vulnerable to memory allocation bugs 225. * in the main code. Don't enable it unless you are confident that 226. * no such bugs exist. 227. */ 228. 229. #define TRIV_ALIGN sizeof(double) 230. #define TRIV_PAGESIZE 4096 231. 232. struct triv_head { 233. size_t triv_size; /* Total block size (excluding header) */ 234. union { 235. struct { 236. size_t nb; /* Number of bytes allocated by user */ 237. void *userdata; 238. } alloc; 239. struct triv_head *next; /* Next free block */ 240. double d; /* Dummy for alignment */ 241. } u; 242. #define triv_nb u.alloc.nb 243. #define triv_userdata u.alloc.userdata 244. #define triv_next u.next /* Free blocks only */ 245. }; 246. 247. static struct triv_head *triv_freelist = NULL; 248. #ifdef WIN32 249. /* 250. * MS-Windows rounds size request up to a system page, so we need to 251. * ensure we always request an exact number of system pages. This 252. * variable holds TRIV_PAGESIZE rounded up accordingly. 253. */ 254. static unsigned int triv_pagesize = 0; 255. #endif 256. 257. #define ROUNDUP(nbytes, align) (((nbytes) + (align) - 1) / (align) * (align)) 258. 259. void *triv_get_userdata(void *p) 260. { 261. struct triv_head *h; 262. if (!p) 263. return p; 264. h = (struct triv_head *)p - 1; 265. return h->triv_userdata; 266. } 267. 268. void triv_set_userdata(void *p, void *d) 269. { 270. struct triv_head *h; 271. if (p) { 272. h = (struct triv_head *)p - 1; 273. h->triv_userdata = d; 274. } 275. } 276. 277. #define IS_CONTIGUOUS(h1,h2) ((h2) == \ 278. (struct triv_head *)((unsigned char *)((h1) + 1) + (h1)->triv_size)) 279. 280. void triv_free(void *p) 281. { 282. struct triv_head *f, *lf, *h; 283. if (!p) 284. return; 285. h = (struct triv_head *)p - 1; 286. /* Find f, the first free block _after_ h in memory */ 287. for (lf = NULL, f = triv_freelist; f; lf = f, f = f->triv_next) 288. if (f > h) 289. break; 290. if (IS_CONTIGUOUS(h, f)) { 291. /* f is contiguous with h; merge them */ 292. h->triv_size += sizeof(struct triv_head) + f->triv_size; 293. h->triv_next = f->triv_next; 294. } 295. else 296. /* f is not contiguous; insert new block */ 297. h->triv_next = f; 298. /* Update pointer from previous block */ 299. if (lf) 300. lf->triv_next = h; 301. else 302. triv_freelist = h; 303. /* Then check last free block _below_ h in memory */ 304. if (lf && IS_CONTIGUOUS(lf, h)) { 305. /* h is contiguous with lf; merge them */ 306. lf->triv_size += sizeof(struct triv_head) + h->triv_size; 307. lf->triv_next = h->triv_next; 308. } 309. } 310. 311. void *triv_malloc(size_t nb) 312. { 313. struct triv_head *f, *lf, *nf; 314. size_t size = ROUNDUP(nb, TRIV_ALIGN); 315. size_t pagesize; 316. if (!nb) 317. return NULL; /* _Not_ an error; don't set errno */ 318. for (lf = NULL, f = triv_freelist; f; lf = f, f = f->triv_next) 319. /* Use first block found which is large enough */ 320. if (f->triv_size >= size) { 321. /* Split the free block if there's enough space left over */ 322. if (f->triv_size - size > sizeof(struct triv_head)) { 323. nf = (struct triv_head *)((unsigned char *)(f + 1) + size); 324. nf->triv_size = f->triv_size - size - sizeof(struct triv_head); 325. nf->triv_next = f->triv_next; 326. f->triv_next = nf; 327. f->triv_size = size; 328. } 329. /* Remove block from freelist */ 330. if (lf) 331. lf->triv_next = f->triv_next; 332. else 333. triv_freelist = f->triv_next; 334. /* Initialise header and return */ 335. f->triv_nb = nb; 336. f->triv_userdata = NULL; 337. return f + 1; 338. } 339. /* Get new block */ 340. #ifdef WIN32 341. if (triv_pagesize == 0) { 342. SYSTEM_INFO si; 343. GetSystemInfo(&si); 344. triv_pagesize = ROUNDUP(TRIV_PAGESIZE, si.dwPageSize); 345. } 346. pagesize = ROUNDUP(sizeof(struct triv_head) + size, triv_pagesize); 347. f = VirtualAlloc(NULL, pagesize, MEM_COMMIT, PAGE_READWRITE); 348. #else 349. pagesize = ROUNDUP(sizeof(struct triv_head) + size, TRIV_PAGESIZE); 350. f = sbrk(pagesize); 351. #endif 352. if (!f) { 353. errno = ENOMEM; 354. return f; 355. } 356. /* Initialise header */ 357. f->triv_size = pagesize - sizeof(struct triv_head); 358. f->triv_nb = nb; 359. f->triv_userdata = NULL; 360. /* Split the new block if there's enough space left over */ 361. if (f->triv_size - size > sizeof(struct triv_head)) { 362. nf = (struct triv_head *)((unsigned char *)(f + 1) + size); 363. nf->triv_size = f->triv_size - size - sizeof(struct triv_head); 364. f->triv_size = size; 365. /* And contribute it to the free list */ 366. triv_free(nf + 1); 367. } 368. return f + 1; 369. } 370. 371. void *triv_calloc(size_t nobj, size_t size) 372. { 373. void *p; 374. size_t nb = nobj * size; 375. if (nb / nobj != size) { /* Check overflow */ 376. errno = ENOMEM; 377. return NULL; 378. } 379. p = triv_malloc(nb); 380. if (p) 381. memset(p, 0, nb); 382. return p; 383. } 384. 385. void *triv_realloc(void *p, size_t size) 386. { 387. struct triv_head *h; 388. void *np; 389. if (!size) { 390. triv_free(p); 391. return NULL; 392. } 393. if (!p) 394. return triv_malloc(size); 395. h = (struct triv_head *)p - 1; 396. if (size <= h->triv_size) { 397. h->triv_nb = size; 398. return p; 399. } 400. np = triv_malloc(size); 401. if (np) { 402. memcpy(np, p, h->triv_nb); 403. triv_set_userdata(np, triv_get_userdata(p)); 404. triv_free(p); 405. } 406. return np; 407. } 408. 409. /* Monitoring front-end */ 410. 411. struct monitor_id { 412. const char *id; /* Typically file name */ 413. int subid; /* Typically line number */ 414. }; 415. 416. static char *monitor_id_stack_default_id = "<none>"; 417. static int monitor_id_stack_depth = 0; 418. static struct monitor_id *monitor_id_stack = NULL; 419. static size_t monitor_mem_in_use = 0; 420. static boolean monitor_trace = 0; 421. static FILE *monitor_fp = NULL; 422. 423. #define MHF_MARKED 1 424. 425. struct monitor_head { 426. void *p; 427. size_t size; 428. struct monitor_id id; 429. unsigned long flags; 430. struct monitor_head *next, *prev; 431. }; 432. 433. static struct monitor_head *monitor_heap = NULL; 434. 435. void monitor_heap_push(const char *id, int subid) 436. { 437. ++monitor_id_stack_depth; 438. monitor_id_stack = triv_realloc(monitor_id_stack, 439. monitor_id_stack_depth * sizeof (*monitor_id_stack)); 440. if (!monitor_id_stack) 441. panic("monitor_heap_push: not enough memory"); 442. monitor_id_stack[monitor_id_stack_depth - 1].id = id; 443. monitor_id_stack[monitor_id_stack_depth - 1].subid = subid; 444. } 445. 446. /* retval is to make writing macros which use monitor_heap_push/pop easier */ 447. 448. unsigned long monitor_heap_pop(const char *id, int subid, unsigned long retval) 449. { 450. if (!monitor_id_stack_depth) 451. panic("monitor_heap_pop: empty stack"); 452. if (monitor_id_stack[monitor_id_stack_depth - 1].id != id || 453. monitor_id_stack[monitor_id_stack_depth - 1].subid != subid) 454. panic("monitor_heap_pop: mismatch: (%s, %d) != (%s, %d)", 455. monitor_id_stack[monitor_id_stack_depth - 1].id, 456. monitor_id_stack[monitor_id_stack_depth - 1].subid, 457. id, subid); 458. --monitor_id_stack_depth; 459. monitor_id_stack = triv_realloc(monitor_id_stack, 460. monitor_id_stack_depth * sizeof (*monitor_id_stack)); 461. return retval; 462. } 463. 464. void monitor_heap_set_subid(const char *id, int subid) 465. { 466. if (!monitor_id_stack_depth) 467. panic("monitor_heap_set_subid: empty stack"); 468. if (monitor_id_stack[monitor_id_stack_depth - 1].id != id) 469. panic("monitor_heap_set_subid: mismatch: %s != %s", 470. monitor_id_stack[monitor_id_stack_depth - 1].id, id); 471. monitor_id_stack[monitor_id_stack_depth - 1].subid = subid; 472. } 473. 474. size_t monitor_heap_getmem(void) 475. { 476. return monitor_mem_in_use; 477. } 478. 479. boolean monitor_heap_trace(boolean flag) 480. { 481. boolean retval = !!monitor_trace; 482. if (flag) 483. monitor_trace++; 484. else 485. monitor_trace--; 486. return retval; 487. } 488. 489. void monitor_heap_mark(void) 490. { 491. struct monitor_head *m; 492. for(m = monitor_heap; m; m = m->next) 493. m->flags |= MHF_MARKED; 494. } 495. 496. void monitor_heap_release(void) 497. { 498. int first = 1; 499. struct monitor_head *m; 500. if (!monitor_fp) 501. return; 502. for(m = monitor_heap; m; m = m->next) 503. m->flags ^= MHF_MARKED; 504. for(m = monitor_heap; m; m = m->next) 505. if (m->flags & MHF_MARKED) { 506. if (first) { 507. fprintf(monitor_fp, 508. "Blocks allocated but not freed during mark/release:\n"); 509. fprintf(monitor_fp, "Address Size Sub-ID ID\n"); 510. first = 0; 511. } 512. fprintf(monitor_fp, 513. "%-16p%-8lu%-8d%s\n", m->p, m->size, m->id.subid, m->id.id); 514. } 515. } 516. 517. static void monitor_dump(void) 518. { 519. int first = 1; 520. struct monitor_head *m; 521. FILE *fp; 522. size_t used = 0; 523. if (!monitor_fp) 524. return; 525. monitor_heap_mark(); 526. fprintf(monitor_fp, "Dump of all monitored blocks in heap:\n"); 527. for(m = monitor_heap; m; m = m->next) { 528. if (m->flags & MHF_MARKED) { 529. used += m->size; 530. if (m->id.id == monitor_id_stack_default_id) 531. continue; 532. if (first) { 533. fprintf(monitor_fp, "Address Size Sub-ID ID\n"); 534. first = 0; 535. } 536. fprintf(monitor_fp, 537. "%-16p%-8lu%-8d%s\n", m->p, m->size, m->id.subid, m->id.id); 538. } 539. } 540. if (first) 541. fprintf(monitor_fp, 542. "No monitored blocks in heap with non-default ID.\n"); 543. fprintf(monitor_fp, "Total used space: %lu bytes\n", used); 544. } 545. 546. void *malloc(size_t nb) 547. { 548. static int busy = 0; 549. static int inited = 0; 550. struct monitor_head *m; 551. if (!busy && !(inited&1) && !monitor_id_stack_depth) { 552. inited|=1; 553. monitor_heap_push(monitor_id_stack_default_id, 0); 554. } 555. if (!busy && !(inited&2)) { 556. char *s; 557. inited|=2; 558. atexit(monitor_dump); 559. s = getenv("NH_HEAPDUMP"); 560. monitor_fp = s ? fopen(s, "w"): NULL; 561. } 562. if (!nb) 563. return NULL; 564. busy++; 565. m = triv_malloc(sizeof(*m)); 566. if (!m) { 567. busy--; 568. return m; 569. } 570. m->size = nb; 571. m->flags = 0; 572. m->p = triv_malloc(nb); 573. if (monitor_trace) 574. fprintf(stderr, "malloc(%d) = %p\n", nb, m->p); 575. if (!m->p) { 576. triv_free(m); 577. busy--; 578. return NULL; 579. } 580. monitor_mem_in_use += nb; 581. m->prev = NULL; 582. m->next = monitor_heap; 583. m->id = monitor_id_stack[monitor_id_stack_depth - 1]; 584. if (monitor_heap) 585. monitor_heap->prev = m; 586. monitor_heap = m; 587. triv_set_userdata(m->p, m); 588. busy--; 589. return m->p; 590. } 591. 592. void *calloc(size_t nobj, size_t size) 593. { 594. void *p; 595. size_t nb = nobj * size; 596. if (nb / nobj != size) { /* Check overflow */ 597. errno = ENOMEM; 598. return NULL; 599. } 600. p = malloc(nb); 601. if (p) 602. memset(p, 0, nb); 603. return p; 604. } 605. 606. void *realloc(void *p, size_t size) 607. { 608. struct monitor_head *m; 609. void *np; 610. if (!size) { 611. free(p); 612. return NULL; 613. } 614. if (!p) 615. return malloc(size); 616. m = triv_get_userdata(p); 617. np = triv_realloc(p, size); 618. if (monitor_trace) 619. fprintf(stderr, "realloc(%p, %d) = %p\n", p, size, np); 620. if (np) { 621. monitor_mem_in_use += size - m->size; 622. m->size = size; 623. m->p = np; 624. } 625. return np; 626. } 627. 628. void free(void *p) 629. { 630. struct monitor_head *m; 631. if (p) 632. { 633. if (monitor_trace) 634. fprintf(stderr, "free(%p)\n", p); 635. m = triv_get_userdata(p); 636. monitor_mem_in_use -= m->size; 637. triv_free(p); 638. if (m->prev) 639. m->prev->next = m->next; 640. else 641. monitor_heap = m->next; 642. if (m->next) 643. m->next->prev = m->prev; 644. triv_free(m); 645. } 646. } 647. 648. #endif /* NHALLOC_DLL || INTERNAL_MALLOC && !WIN32 */ 649. 650. /*alloc.c*/
