Wikia

Wikihack

Source:SLASH'EM 0.0.7E7F2/alloc.c

2,032pages on
this wiki
Talk0

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

Around Wikia's network

Random Wiki