Source:SLASH'EM 0.0.7E7F2/alloc.c

From NetHackWiki
Jump to navigation Jump to search

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*/