aboutsummaryrefslogtreecommitdiff
path: root/nx-X11/util/memleak
diff options
context:
space:
mode:
authorReinhard Tartler <siretart@tauware.de>2011-10-10 17:43:39 +0200
committerReinhard Tartler <siretart@tauware.de>2011-10-10 17:43:39 +0200
commitf4092abdf94af6a99aff944d6264bc1284e8bdd4 (patch)
tree2ac1c9cc16ceb93edb2c4382c088dac5aeafdf0f /nx-X11/util/memleak
parenta840692edc9c6d19cd7c057f68e39c7d95eb767d (diff)
downloadnx-libs-f4092abdf94af6a99aff944d6264bc1284e8bdd4.tar.gz
nx-libs-f4092abdf94af6a99aff944d6264bc1284e8bdd4.tar.bz2
nx-libs-f4092abdf94af6a99aff944d6264bc1284e8bdd4.zip
Imported nx-X11-3.1.0-1.tar.gznx-X11/3.1.0-1
Summary: Imported nx-X11-3.1.0-1.tar.gz Keywords: Imported nx-X11-3.1.0-1.tar.gz into Git repository
Diffstat (limited to 'nx-X11/util/memleak')
-rw-r--r--nx-X11/util/memleak/Imakefile97
-rw-r--r--nx-X11/util/memleak/README70
-rw-r--r--nx-X11/util/memleak/find-rtns.sh50
-rw-r--r--nx-X11/util/memleak/fmalloc.c1256
-rw-r--r--nx-X11/util/memleak/ftest.c55
-rw-r--r--nx-X11/util/memleak/getreti386.c54
-rw-r--r--nx-X11/util/memleak/getretmips.c198
-rw-r--r--nx-X11/util/memleak/getretspar.c66
-rw-r--r--nx-X11/util/memleak/getrettest.c48
-rw-r--r--nx-X11/util/memleak/mipsstack.s43
-rw-r--r--nx-X11/util/memleak/sparcsolstack.s11
-rw-r--r--nx-X11/util/memleak/sparcstack.s11
-rw-r--r--nx-X11/util/memleak/stackbottom.c119
13 files changed, 2078 insertions, 0 deletions
diff --git a/nx-X11/util/memleak/Imakefile b/nx-X11/util/memleak/Imakefile
new file mode 100644
index 000000000..8ec6cc26c
--- /dev/null
+++ b/nx-X11/util/memleak/Imakefile
@@ -0,0 +1,97 @@
+XCOMM $Xorg: Imakefile,v 1.3 2000/08/17 19:55:19 cpqbld Exp $
+
+
+
+
+XCOMM $XFree86: xc/util/memleak/Imakefile,v 3.4 2000/02/12 03:40:07 dawes Exp $
+
+#define DoNormalLib YES
+#define DoSharedLib NO
+#define DoDebugLib NO
+#define DoProfileLib NO
+#define IncSubdir X11
+#include <Library.tmpl>
+
+#ifdef MipsArchitecture
+#define TopOfStack 0x7fffbbb0
+#define BottomOfData 0x10000000
+#define HasGetReturnAddress YES
+GRA_OBJS = getretmips.o mipsstack.o
+GRA_SRCS = getretmips.c
+#endif
+
+#ifdef SparcArchitecture
+#define HasGetReturnAddress YES
+#define BottomOfData \&environ
+#ifdef SystemV4
+GRA_OBJS = getretspar.o sparcsolstack.o
+#define TopOfStack 0xeffffc70
+#else
+LOCAL_DEFS = -Datexit=on_exit
+GRA_OBJS = getretspar.o sparcstack.o
+#define TopOfStack 0xf7fffbdc
+#endif
+GRA_SRCS = getretspar.c
+#endif
+
+#ifdef i386BsdArchitecture
+#define HasGetReturnAddress YES
+#define TopOfStack 'GC_get_stack_base()'
+#define BottomOfData \&etext
+GRA_OBJS = getreti386.o stackbottom.o
+GRA_SRCS = getreti386.c stackbottom.c
+#endif
+
+#if defined(LinuxArchitecture) || defined(__GLIBC__)
+#ifdef i386Architecture
+#define HasGetReturnAddress YES
+#define TopOfStack 0xbffff800
+#define BottomOfData \&__data_start
+GRA_OBJS = getreti386.o stackbottom.o
+GRA_SRCS = getreti386.c stackbottom.c
+#endif
+#endif
+
+#ifdef AlphaArchitecture
+#define HasGetReturnAddress NO
+#define TopOfData \&_end
+#define TopOfStack 0x11ffffff0
+#define BottomOfData \&xf86DriverList
+#endif
+
+#ifndef HasGetReturnAddress
+#define HasGetReturnAddress NO
+#endif
+
+#if HasGetReturnAddress
+ GRA_DEFS = -DHAS_GET_RETURN_ADDRESS
+#endif
+
+#ifdef TopOfData
+ TOD_DEFS = -DTOP_OF_DATA=TopOfData
+#endif
+
+DEFINES = -DTOP_OF_STACK=TopOfStack -DBOTTOM_OF_DATA=BottomOfData\
+ $(GRA_DEFS) $(TOD_DEFS) $(LOCAL_DEFS)
+
+CDEBUGFLAGS = DebuggableCDebugFlags
+
+SRCS = fmalloc.c $(GRA_SRCS)
+
+OBJS = fmalloc.o $(GRA_OBJS)
+
+LibraryObjectRule()
+
+#if DoNormalLib
+NormalLibraryTarget(memleak,$(OBJS))
+InstallLibrary(memleak,$(USRLIBDIR))
+#endif
+
+InstallNamedProg(find-rtns.sh,find-routines,$(BINDIR))
+
+LintLibraryTarget(memleak,$(SRCS))
+InstallLintLibrary(memleak,$(LINTLIBDIR))
+
+DependTarget()
+
+NormalLintTarget($(SRCS))
diff --git a/nx-X11/util/memleak/README b/nx-X11/util/memleak/README
new file mode 100644
index 000000000..9be2d9ca5
--- /dev/null
+++ b/nx-X11/util/memleak/README
@@ -0,0 +1,70 @@
+.\" $Xorg: README,v 1.3 2000/08/17 19:55:19 cpqbld Exp $
+
+This library replaces the C library allocator;
+providing malloc, free, realloc and calloc (sorry, no valloc)
+
+In doing so, it provides extensive memory bug checking, locating:
+
+ Lost memory; memory which has not been freed and which has no
+ references
+
+ In use free memory; memorhy which has been freed and still has
+ references to it.
+
+ Stores to freed memory
+
+ free/realloc with invalid pointers -- if you pass in a pointer to
+ the middle of an allocated block, it will even tell you which one
+
+For each of these errors, a report entry is generated which includes
+the stack backtrace of either the allocation or free (which ever occured
+last) along with the current stack, when relevant.
+
+Unreferenced allocated memory, stores to freed memory and referenced freed
+memory are only caught when CheckMemory is called. It is automatically
+called each time 1m of data has been freed, and is called when the program
+exits (by registering with atexit(3)/on_exit(3)). You can call it whenever
+you want.
+
+Both the X server and font servers call CheckMemory after each reset when
+their respective os/utils.c are compiled -DMEMBUG.
+
+There are a few global variables you can set with the debugger to
+help isolate problems:
+
+ FindLeakWarnMiddlePointers
+ Normally, memleak ignores pointers to the middle of
+ freed memory. These are frequently simply random data
+ which happens to look like a pointer. Turning this
+ on will generate additional messages.
+ FindLeakAllocBreakpoint
+ At each allocation, memleak increments a serial number
+ and stores it in the allocation header. By rerunning
+ the program, you can stop when that piece of memory
+ is going to be allocated. Store the serial number
+ in this global variable and put a debugger breakpoint inside
+ AddActiveBlock at the indicated line.
+ FindLeakFreeBreakpoint
+ Similarly for freeing memory.
+ FindLeakTime
+ The current serial number
+ FindLeakCheckAlways
+ When set, memleak checks the entire memory system after
+ each allocation or free. This is very expensive, but
+ may catch errors not otherwise found until too late.
+
+To include this in your application, simply place libmemleak.a before the
+end of the link line; it will then override the C library allocator.
+
+To port this system to a new machine, you must provide two values, one
+indicating the lowest data address in a program and one indicating the
+highest stack address. In addition, to get return stack traces (which are
+almost essential for debugging), you must provide the function
+getReturnStack. Samples for MIPS and SPARC are included already.
+
+The output from the leak tracer includes only PC values in the stack
+traces. To convert these into useful values, run the output of
+the leak tracer through the find-routines script; after making sure you have
+built the modified version of gdb-4.4 on your machine.
+
+-keith
diff --git a/nx-X11/util/memleak/find-rtns.sh b/nx-X11/util/memleak/find-rtns.sh
new file mode 100644
index 000000000..91431c770
--- /dev/null
+++ b/nx-X11/util/memleak/find-rtns.sh
@@ -0,0 +1,50 @@
+#!/bin/sh
+#
+# $Xorg: find-rtns.sh,v 1.3 2000/08/17 19:55:19 cpqbld Exp $
+#
+# find-routines - convert leak tracer stack traces into file/lineno traces
+# modified to work with the an unmodified version of
+# gdb-4.18
+#
+# Usage: find-routines <program-name> {leak-tracing-output-files}
+#
+# $XFree86$
+#
+
+TMP1=find-routine.tmp1
+TMP=find-routine.tmp
+trap "rm -f $TMP $TMP1" 0
+OBJ=$1
+shift
+echo 'set width 500' > $TMP1
+# To load shared libs set breakpoint and run
+echo 'break main' >> $TMP1
+echo 'r' >> $TMP1
+for i in `grep '\(return stack:\)\|\(allocated at\)' $* |
+ tr ' ' '\012' |
+ grep 0x | sort -u`;
+ do
+ echo 'x/i '$i >> $TMP1
+ echo 'i line * '$i >> $TMP1
+done
+
+cat $TMP1 | gdb $OBJ \
+ | awk '\
+ /^\(gdb\) \(?g?d?b?\)? ?0x[[:xdigit:]]*.*:.*/ \
+ {a = gensub(/^\(gdb\) \(?g?d?b?\)? ?(0x[[:xdigit:]]*).*:.*/,"\\1","G");\
+ b = gensub(/^\(gdb\) \(?g?d?b?\)? ?(0x[[:xdigit:]]*.*):.*/,"\\1","G");\
+ printf("s;%s;%s",a,b); next; } \
+ /.*No line.*/ \
+ {printf(";\n",a);next} \
+ /.*Line [[:digit:]]+.*/ \
+ {a = gensub(/.*(Line [[:digit:]]+ of .*) starts.*/,"\\1","G"); \
+ printf(" at %s;\n", a); next}'>> $TMP
+
+awk '/return stack/ { printf ("return stack\n");
+ for (i = 3; i <= NF; i++)
+ printf ("\troutine %s\n", $i); }
+ /allocated at/ { printf ("allocated at\n");
+ for (i = 3; i <= NF; i++)
+ printf ("\t\troutine %s\n", $i); }
+ /^[A-Z]/ { print }' $* |
+ sed -f $TMP
diff --git a/nx-X11/util/memleak/fmalloc.c b/nx-X11/util/memleak/fmalloc.c
new file mode 100644
index 000000000..bce5c4388
--- /dev/null
+++ b/nx-X11/util/memleak/fmalloc.c
@@ -0,0 +1,1256 @@
+/*
+ * $Xorg: fmalloc.c,v 1.5 2001/02/09 02:06:19 xorgcvs Exp $
+ *
+Copyright 1992, 1998 The Open Group
+
+Permission to use, copy, modify, distribute, and sell this software and its
+documentation for any purpose is hereby granted without fee, provided that
+the above copyright notice appear in all copies and that both that
+copyright notice and this permission notice appear in supporting
+documentation.
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
+AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+Except as contained in this notice, the name of The Open Group shall not be
+used in advertising or otherwise to promote the sale, use or other dealings
+in this Software without prior written authorization from The Open Group.
+ *
+ * Author: Keith Packard, MIT X Consortium
+ */
+
+/* $XFree86: xc/util/memleak/fmalloc.c,v 3.12 2001/02/16 13:24:10 eich Exp $ */
+
+
+/*
+ * Leak tracing allocator -- using C lib malloc/free, tracks
+ * all allocations. When requested, performs a garbage-collection
+ * style mark/sweep on static memory (data and stack), locating
+ * objects referenced therein. Recursively marks objects.
+ * Sweeps through all allocations, warning of possible violations
+ * (unreferenced allocated, referenced freed etc).
+ */
+
+#include <stdio.h>
+
+extern char **environ;
+extern xf86DriverList;
+extern etext;
+extern _etext;
+extern __data_start;
+extern _end;
+
+#ifndef TOP_OF_DATA
+#define TOP_OF_DATA 0
+#endif
+
+#ifndef FALSE
+#define FALSE 0
+#endif
+#ifndef TRUE
+#define TRUE 1
+#endif
+
+#ifdef X_NOT_POSIX
+#define NO_ATEXIT
+#endif
+
+typedef unsigned long mem;
+typedef unsigned int magic;
+
+#ifdef HAS_GET_RETURN_ADDRESS
+#define MAX_RETURN_STACK 16
+#endif
+
+#define MAX_FREED_MEMORY (1*1024*1024)
+
+#define ACTIVE_HEAD_MAGIC 0xff1111ff
+#define ACTIVE_TAIL_MAGIC 0xee2222ee
+#define ACTIVE_DATA_MAGIC 0xdd3333dd
+#define FREED_HEAD_MAGIC 0xcc4444cc
+#define FREED_TAIL_MAGIC 0xbb5555bb
+#define FREED_DATA_MAGIC 0xcc6666cc
+
+/*
+ * the marked fields in each head have two bits - one indicating
+ * references to the head of the block, and one indicating references
+ * to the middle of the block
+ */
+#define UNREFERENCED 0
+#define REFERENCED_HEAD 1
+#define REFERENCED_MIDDLE 2
+
+typedef struct _head {
+ struct _head *left, *right;
+ struct _head *next;
+ int balance;
+#ifdef HAS_GET_RETURN_ADDRESS
+ mem returnStack[MAX_RETURN_STACK];
+#endif
+ mem *from;
+ mem *fromReturnStack;
+ unsigned long allocTime;
+ unsigned long freeTime;
+ int size;
+ int desiredsize;
+ int actualSize;
+ int marked;
+ magic headMagic;
+} HeadRec, *HeadPtr;
+
+typedef struct _tail {
+ magic tailMagic;
+ magic tailPad;
+} TailRec, *TailPtr;
+
+#define Header(p) ((HeadPtr) (((char *) (p)) - sizeof (HeadRec)))
+#define DataForHead(h) ((mem *) ((h) + 1))
+#define Tailer(p) ((TailPtr) (((char *) (p)) + Header(p)->size))
+#define TailForHead(h) (Tailer(DataForHead(h)))
+#define RoundSize (sizeof (mem))
+#define RoundUp(s) (((s) + RoundSize - 1) & ~(RoundSize - 1))
+#define TotalSize(s) ((s) + sizeof (HeadRec) + sizeof (TailRec))
+#define CheckInit() if (!endOfStaticMemory) endOfStaticMemory = sbrk(0)
+#define BlockContains(h,p) (DataForHead(h) <= (p) && (p) < (mem *) TailForHead(h))
+
+typedef HeadRec tree;
+typedef mem *tree_data;
+
+#define COMPARE_ADDR(a,b,op) (((mem) (a)) op ((mem) (b)))
+#define COMPARE(a,b,op,s) ((!s) ? \
+ COMPARE_ADDR(a,b,op) :\
+ (((a)->actualSize op (b)->actualSize) || \
+ ((a)->actualSize == (b)->actualSize && \
+ COMPARE_ADDR(a,b,op))))
+
+
+#define LESS_THAN(a,b,s) COMPARE(a,b,<,s)
+#define GREATER_THAN(a,b,s) COMPARE(a,b,>,s)
+
+#define SEARCH(top,result,p) for (result = top; result;) {\
+ if ((mem *) (p) < DataForHead(result)) \
+ result = result->left; \
+ else if ((mem *) TailForHead(result) < (mem *) (p)) \
+ result = result->right; \
+ else \
+ break; \
+}
+
+
+static tree *activeMemory, *freedMemory, *deadMemory;
+
+static mem *endOfStaticMemory = (mem *) TOP_OF_DATA;
+static mem *highestAllocatedMemory;
+
+static int freedMemoryTotal;
+static int freedMemoryCount;
+static int activeMemoryTotal;
+static int activeMemoryCount;
+static int deadMemoryTotal;
+static int unreferencedAllocatedTotal;
+static int unreferencedAllocatedCount;
+
+int FindLeakWarnMiddlePointers = 0;
+unsigned long FindLeakAllocBreakpoint = ~0;
+unsigned long FindLeakFreeBreakpoint = ~0;
+unsigned long FindLeakTime;
+int FindLeakCheckAlways = 0;
+int FindLeakValidateAlways = 0;
+int FindPrintAllocations = 0;
+
+static void MarkActiveBlock ();
+static int tree_insert (), tree_delete ();
+void CheckMemory ();
+char *malloc (), *realloc (), *calloc ();
+void free ();
+extern char *sbrk ();
+
+#ifdef HAS_GET_RETURN_ADDRESS
+static void
+PrintReturnStack (m, ra)
+ char *m;
+ mem *ra;
+{
+ int i;
+
+ fprintf (stderr, " %s:", m);
+ for (i = 0; i < MAX_RETURN_STACK && ra[i]; i++)
+ fprintf (stderr, " 0x%lx", ra[i]);
+ fprintf (stderr, "\n");
+}
+#endif
+
+static void
+MemError (s, h, ourRet)
+ char *s;
+ HeadPtr h;
+ int ourRet;
+{
+ mem *ra;
+ int i;
+
+ if (h)
+ {
+ fprintf (stderr, "%s 0x%08lx (size %d) (from 0x%lx) ",
+ s, DataForHead(h), h->desiredsize, h->from);
+#ifdef HAS_GET_RETURN_ADDRESS
+ if (h->fromReturnStack)
+ PrintReturnStack ("\nallocated at", h->fromReturnStack);
+ else
+ fprintf(stderr,"\n");
+ PrintReturnStack ("Saved return stack", h->returnStack);
+#else
+ fprintf(stderr,"\n");
+#endif
+ }
+ else
+ fprintf (stderr, "%s\n", s);
+#ifdef HAS_GET_RETURN_ADDRESS
+ if (ourRet)
+ {
+ mem returnStack[MAX_RETURN_STACK];
+
+ getStackTrace (returnStack, MAX_RETURN_STACK);
+ PrintReturnStack ("Current return stack", returnStack);
+ }
+#endif
+}
+
+static void
+MarkMemoryRegion (low, high)
+ mem *low, *high;
+{
+ mem **start = (mem **) low, **end = (mem **) high;
+ mem *p;
+
+ while (start < end) {
+ p = *start;
+ if (endOfStaticMemory <= p && p < highestAllocatedMemory)
+ MarkActiveBlock (p, (mem *) start);
+ start++;
+ }
+}
+
+static void
+MarkActiveBlock (p, from)
+ mem *p, *from;
+{
+ HeadPtr h, hh;
+ int marked;
+ int oldMarked;
+
+ SEARCH(activeMemory, h, p)
+ if (h) {
+ marked = REFERENCED_HEAD;
+ if (p != DataForHead(h))
+ marked = REFERENCED_MIDDLE;
+ oldMarked = h->marked;
+ if (!(oldMarked & marked))
+ {
+ h->marked |= marked;
+ h->from = from;
+#ifdef HAS_GET_RETURN_ADDRESS
+ SEARCH(activeMemory, hh, h->from)
+ if (hh)
+ h->fromReturnStack = hh->returnStack;
+#endif
+ if (!oldMarked)
+ MarkMemoryRegion (DataForHead(h), (mem *) TailForHead(h));
+ }
+ return;
+ }
+ SEARCH(freedMemory, h, p)
+ if (h)
+ {
+ marked = REFERENCED_HEAD;
+ if (p != DataForHead(h))
+ marked = REFERENCED_MIDDLE;
+ if (!(h->marked & marked))
+ {
+ h->marked |= marked;
+ h->from = from;
+#ifdef HAS_GET_RETURN_ADDRESS
+ SEARCH(activeMemory, hh, h->from)
+ if (hh)
+ h->fromReturnStack = hh->returnStack;
+#endif
+ }
+ return;
+ }
+}
+
+static void
+ClearTree (t)
+ tree *t;
+{
+ if (!t)
+ return;
+ ClearTree (t->left);
+ t->marked = 0;
+ t->from = 0;
+ ClearTree (t->right);
+}
+
+static void
+SweepActiveTree (t)
+ tree *t;
+{
+ if (!t)
+ return;
+ SweepActiveTree (t->left);
+ if (!t->marked) {
+ unreferencedAllocatedTotal += t->desiredsize;
+ unreferencedAllocatedCount++;
+ MemError ("Unreferenced allocated", t, FALSE);
+ }
+ else if (!(t->marked & REFERENCED_HEAD))
+ MemError ("Referenced allocated middle", t, FALSE);
+ SweepActiveTree (t->right);
+}
+
+/*
+ * run a thread through the tree at the same time
+ * - the thread runs
+ *
+ * root -> left_child ... -> right_child ... -> null
+ */
+
+static tree *
+SweepFreedTree (t)
+ tree *t;
+{
+ tree *left_last, *right_last;
+
+ if (!t)
+ return 0;
+
+ left_last = SweepFreedTree (t->left);
+ if (t->marked)
+ {
+ if (t->marked & REFERENCED_HEAD)
+ MemError ("Referenced freed base", t, FALSE);
+ else if (FindLeakWarnMiddlePointers)
+ MemError ("Referenced freed middle", t, FALSE);
+ }
+ right_last = SweepFreedTree (t->right);
+
+ if (t->left)
+ t->next = t->left;
+ else
+ t->next = t->right;
+ if (left_last)
+ left_last->next = t->right;
+ if (!right_last)
+ right_last = left_last;
+ if (!right_last)
+ right_last = t;
+ return right_last;
+}
+
+static void
+SweepFreedMemory ()
+{
+ tree *t, *n;
+ int count, shouldCount;
+
+ (void) SweepFreedTree (freedMemory);
+ count = 0;
+ shouldCount = freedMemoryCount;
+ for (t = freedMemory; t; t = n) {
+ n = t->next;
+ count++;
+ if (!t->marked)
+ {
+ (void) tree_delete (&freedMemory, t, FALSE);
+ freedMemoryTotal -= t->desiredsize;
+ freedMemoryCount--;
+ tree_insert (&deadMemory, t, TRUE);
+ }
+ }
+ if (count != shouldCount)
+ abort ();
+}
+
+static void
+ValidateTree (head, headMagic, tailMagic, bodyMagic, mesg)
+ tree *head;
+ mem headMagic, tailMagic, bodyMagic;
+ char *mesg;
+{
+ TailPtr tail;
+ magic *p;
+ int i;
+
+ if (!head)
+ return;
+ ValidateTree (head->left, headMagic, tailMagic, bodyMagic, mesg);
+ tail = TailForHead (head);
+ if (head->headMagic != headMagic)
+ MemError (mesg, head, FALSE);
+ if (tail->tailMagic != tailMagic)
+ MemError (mesg, head, FALSE);
+ if (bodyMagic) {
+ i = head->size / sizeof (magic);
+ p = (magic *) DataForHead(head);
+ while (i--) {
+ if (*p++ != bodyMagic)
+ {
+ MemError (mesg, head, FALSE);
+ break;
+ }
+ }
+ }
+ ValidateTree (head->right, headMagic, tailMagic, bodyMagic, mesg);
+}
+
+static void
+ValidateActiveMemory ()
+{
+ ValidateTree (activeMemory, ACTIVE_HEAD_MAGIC, ACTIVE_TAIL_MAGIC,
+ 0, "Store outside of active memory");
+}
+
+static void
+ValidateFreedMemory ()
+{
+ ValidateTree (freedMemory, FREED_HEAD_MAGIC, FREED_TAIL_MAGIC,
+ FREED_DATA_MAGIC, "Store into freed memory");
+}
+
+static void
+AddActiveBlock (h)
+ HeadPtr h;
+{
+ TailPtr t = TailForHead(h);
+ magic *p;
+ int i;
+
+ tree_insert (&activeMemory, h, FALSE);
+ if ((mem *) t > highestAllocatedMemory)
+ highestAllocatedMemory = (mem *) t;
+
+ /*
+ * Breakpoint position - assign FindLeakAllocBreakpoint with
+ * debugger and set a breakpoint in the conditional clause below
+ */
+ if (FindLeakTime == FindLeakAllocBreakpoint)
+ h->headMagic = ACTIVE_HEAD_MAGIC; /* set breakpoint here */
+
+ h->allocTime = FindLeakTime++;
+
+ h->headMagic = ACTIVE_HEAD_MAGIC;
+ t->tailMagic = ACTIVE_TAIL_MAGIC;
+ i = h->size / sizeof (magic);
+ p = (magic *) DataForHead(h);
+ while (i--)
+ *p++ = ACTIVE_DATA_MAGIC;
+ activeMemoryTotal += h->desiredsize;
+ activeMemoryCount++;
+}
+
+static void
+RemoveActiveBlock (h)
+ HeadPtr h;
+{
+ activeMemoryTotal -= h->desiredsize;
+ activeMemoryCount--;
+ tree_delete (&activeMemory, h, FALSE);
+}
+
+static void
+AddFreedBlock (h)
+ HeadPtr h;
+{
+ TailPtr t = TailForHead(h);
+ int i;
+ magic *p;
+
+ tree_insert (&freedMemory, h, FALSE);
+
+ /*
+ * Breakpoint position - assign FindLeakFreeBreakpoint with
+ * debugger and set a breakpoint in the conditional clause below
+ */
+ if (FindLeakTime == FindLeakFreeBreakpoint)
+ h->headMagic = FREED_HEAD_MAGIC; /* set breakpoint here */
+
+ h->freeTime = FindLeakTime++;
+
+ h->headMagic = FREED_HEAD_MAGIC;
+ t->tailMagic = FREED_TAIL_MAGIC;
+ i = h->size / sizeof (magic);
+ p = (magic *) DataForHead(h);
+ while (i--)
+ *p++ = FREED_DATA_MAGIC;
+ freedMemoryTotal += h->desiredsize;
+ freedMemoryCount++;
+ /* GC if we've got piles of unused memory */
+ if (freedMemoryTotal - deadMemoryTotal >= MAX_FREED_MEMORY)
+ CheckMemory ();
+}
+#if 0
+static void
+WarnReferencedRange(rangeStart,rangeEnd,from,to)
+ mem *rangeStart;
+ mem *rangeEnd;
+ mem *from;
+ mem *to;
+{
+ mem *range = rangeStart;
+
+ while ( range < rangeEnd) {
+ if ((mem *)*range >= from && (mem *)*range <= to)
+ fprintf(stderr, "0x%lx still points into newly allocated range\n",
+ (unsigned long) range);
+ range++;
+ }
+}
+
+static void
+WarnReferencedTree(head, from, to)
+ tree *head;
+ char *from;
+ char *to;
+{
+ if (!head) return;
+ WarnReferencedTree(head->right,from,to);
+ WarnReferencedRange(DataForHead(head),TailForHead(head),from,to);
+ WarnReferencedTree(head->left,from,to);
+}
+
+static void
+WarnReferenced(from, to)
+ char *from;
+ char *to;
+{
+ mem foo;
+
+ foo = 1;
+ WarnReferencedTree(activeMemory,from,to);
+ WarnReferencedRange(BOTTOM_OF_DATA, endOfStaticMemory,from,to);
+ WarnReferencedRange(&foo, TOP_OF_STACK,from,to);
+}
+#endif
+/*
+ * Entry points:
+ *
+ * CheckMemory () -- Verifies heap
+ * malloc (size) -- Allocates memory
+ * free (old) -- Deallocates memory
+ * realloc (old, size) -- Allocate, copy, free
+ * calloc (num, size_per) -- Allocate and zero
+ */
+
+void
+CheckMemory ()
+{
+#if 0
+ mem foo;
+
+ unreferencedAllocatedTotal = 0;
+ unreferencedAllocatedCount = 0;
+ foo = 1;
+ fprintf (stderr, "\nCheckMemory\n");
+ fprintf (stderr, "Static Memory Area: 0x%lx to 0x%lx\n",
+ BOTTOM_OF_DATA, endOfStaticMemory);
+ fprintf (stderr, "%d bytes active memory in %d allocations\n",
+ activeMemoryTotal, activeMemoryCount);
+ fprintf (stderr, "%d bytes freed memory held from %d allocations\n",
+ freedMemoryTotal, freedMemoryCount);
+ ValidateActiveMemory ();
+ ValidateFreedMemory ();
+ ClearTree (activeMemory);
+ ClearTree (freedMemory);
+ MarkMemoryRegion (BOTTOM_OF_DATA, endOfStaticMemory);
+ MarkMemoryRegion (&foo, TOP_OF_STACK);
+ SweepActiveTree (activeMemory);
+ SweepFreedMemory ();
+ fprintf (stderr, "%d bytes freed memory still held from %d allocations\n",
+ freedMemoryTotal, freedMemoryCount);
+ fprintf (stderr,
+ "%d bytes of allocated memory not referenced from %d allocations\n",
+ unreferencedAllocatedTotal,unreferencedAllocatedCount);
+ deadMemoryTotal = freedMemoryTotal;
+ fprintf (stderr, "CheckMemory done\n");
+#endif
+}
+
+/*
+ * Allocator interface -- malloc and free (others in separate files)
+ */
+
+#define CORE_CHUNK 16384
+
+static char *core;
+static unsigned core_left;
+static unsigned total_core_used;
+
+static char *
+morecore (size)
+ unsigned size;
+{
+ unsigned alloc_size;
+ char *alloc, *newcore;
+
+ if (core_left < size)
+ {
+ alloc_size = (size + CORE_CHUNK - 1) & ~(CORE_CHUNK-1);
+ newcore = sbrk (alloc_size);
+ if (((long) newcore) == -1)
+ return 0;
+ core = newcore;
+ core_left = alloc_size;
+ total_core_used += alloc_size;
+ }
+ alloc = core;
+ core += size;
+ core_left -= size;
+ return alloc;
+}
+
+char *
+malloc (desiredsize)
+ unsigned desiredsize;
+{
+ char *ret;
+ unsigned size;
+ unsigned totalsize;
+ HeadPtr h;
+
+ if (!endOfStaticMemory)
+ endOfStaticMemory = (mem *) sbrk(0);
+ if (FindLeakCheckAlways)
+ CheckMemory ();
+ else if (FindLeakValidateAlways)
+ {
+ ValidateActiveMemory ();
+ ValidateFreedMemory ();
+ }
+ size = RoundUp(desiredsize);
+ totalsize = TotalSize (size);
+
+ h = deadMemory;
+ while (h)
+ {
+ if (h->actualSize == size)
+ break;
+ else if (h->actualSize < size)
+ h = h->right;
+ else {
+ if (!h->left)
+ break;
+ h = h->left;
+ }
+ }
+ if (h)
+ {
+ tree_delete (&deadMemory, h, TRUE);
+ }
+ else
+ {
+ h = (HeadPtr) morecore (totalsize);
+ if (!h)
+ return NULL;
+ h->actualSize = size;
+ }
+ h->desiredsize = desiredsize;
+ h->size = size;
+#ifdef HAS_GET_RETURN_ADDRESS
+ getStackTrace (h->returnStack, MAX_RETURN_STACK);
+#endif
+ AddActiveBlock (h);
+ ret = (char *) DataForHead(h);
+ if (FindPrintAllocations) {
+ fprintf(stderr,"Allocated %i bytes at 0x%lx\n",desiredsize,ret);
+#ifdef HAS_GET_RETURN_ADDRESS
+ PrintReturnStack ("at",h->returnStack);
+#endif
+ }
+ return ret;
+}
+
+void
+free (p)
+ char *p;
+{
+ HeadPtr h;
+ static int beenHere;
+
+#ifndef NO_ATEXIT
+ /* do it at free instead of malloc to avoid recursion? */
+ if (!beenHere)
+ {
+ beenHere = TRUE;
+ atexit (CheckMemory);
+ }
+#endif
+ if (!p)
+ {
+ MemError ("Freeing NULL", (HeadPtr) 0, TRUE);
+ return;
+ }
+ SEARCH (activeMemory, h, p);
+ if (!h)
+ {
+ SEARCH(freedMemory, h, p);
+ if (h)
+ MemError ("Freeing something twice", h, TRUE);
+ else
+ MemError ("Freeing something never allocated", h, TRUE);
+ return;
+ }
+ if (DataForHead(h) != (mem *) p)
+ {
+ MemError ("Freeing pointer to middle of allocated block", h, TRUE);
+ return;
+ }
+ if (h->headMagic != ACTIVE_HEAD_MAGIC ||
+ TailForHead(h)->tailMagic != ACTIVE_TAIL_MAGIC)
+ MemError ("Freeing corrupted data", h, TRUE);
+ RemoveActiveBlock (h);
+#ifdef HAS_GET_RETURN_ADDRESS
+ getStackTrace (h->returnStack, MAX_RETURN_STACK);
+#endif
+ AddFreedBlock (h);
+ if (FindLeakCheckAlways)
+ CheckMemory ();
+ else if (FindLeakValidateAlways)
+ {
+ ValidateActiveMemory ();
+ ValidateFreedMemory ();
+ }
+ if (FindPrintAllocations) {
+ fprintf(stderr,"Freed at: 0x%lx\n",p);
+ PrintReturnStack ("at",h->returnStack);
+ }
+
+}
+
+char *
+realloc (old, desiredsize)
+ char *old;
+ unsigned desiredsize;
+{
+ char *new;
+ HeadPtr h, fh;
+ int copysize;
+
+ new = malloc (desiredsize);
+ if (!new)
+ return NULL;
+ if (!old)
+ return new;
+ SEARCH(activeMemory, h, old);
+ if (!h)
+ {
+ SEARCH(freedMemory, fh, old);
+ if (fh)
+ MemError ("Reallocing from freed data", fh, TRUE);
+ else
+ MemError ("Reallocing from something not allocated", h, TRUE);
+ }
+ else
+ {
+ if (DataForHead(h) != (mem *) old)
+ {
+ MemError ("Reallocing from pointer to middle of allocated block", h, TRUE);
+ }
+ else
+ {
+ if (h->headMagic != ACTIVE_HEAD_MAGIC ||
+ TailForHead(h)->tailMagic != ACTIVE_TAIL_MAGIC)
+ MemError ("Reallocing corrupted data", h, TRUE);
+ copysize = desiredsize;
+ if (h->desiredsize < desiredsize)
+ copysize = h->desiredsize;
+#ifdef SVR4
+ memmove (new, old, copysize);
+#else
+ bcopy (old, new, copysize);
+#endif
+ RemoveActiveBlock (h);
+#ifdef HAS_GET_RETURN_ADDRESS
+ getStackTrace (h->returnStack, MAX_RETURN_STACK);
+#endif
+ AddFreedBlock (h);
+ }
+ }
+ if (FindPrintAllocations) {
+ fprintf(stderr,"Freed at: 0x%lx\n",old);
+ fprintf(stderr,"Reallocated: %i bytes at: 0x%lx\n",desiredsize,new);
+#ifdef HAS_GET_RETURN_ADDRESS
+ PrintReturnStack ("at", h->returnStack);
+#endif
+ }
+ return new;
+}
+
+char *
+calloc (num, size)
+ unsigned num, size;
+{
+ char *ret;
+
+ size *= num;
+ ret = malloc (size);
+ if (!ret)
+ return NULL;
+#ifdef SVR4
+ memset (ret, 0, size);
+#else
+ bzero (ret, size);
+#endif
+ return ret;
+}
+
+/*
+ * Semi-Balanced trees (avl). This only contains two
+ * routines - insert and delete. Searching is
+ * reserved for the client to write.
+ */
+
+static rebalance_right (), rebalance_left ();
+
+/*
+ * insert a new node
+ *
+ * this routine returns non-zero if the tree has grown
+ * taller
+ */
+
+static int
+tree_insert (treep, new, bySize)
+tree **treep;
+tree *new;
+int bySize;
+{
+ if (!(*treep)) {
+ (*treep) = new;
+ (*treep)->left = 0;
+ (*treep)->right = 0;
+ (*treep)->balance = 0;
+ return 1;
+ } else {
+ if (LESS_THAN (*treep, new, bySize)) {
+ if (tree_insert (&((*treep)->right), new, bySize))
+ switch (++(*treep)->balance) {
+ case 0:
+ return 0;
+ case 1:
+ return 1;
+ case 2:
+ (void) rebalance_right (treep);
+ }
+ return 0;
+ } else if (GREATER_THAN(*treep, new, bySize)) {
+ if (tree_insert (&((*treep)->left), new, bySize))
+ switch (--(*treep)->balance) {
+ case 0:
+ return 0;
+ case -1:
+ return 1;
+ case -2:
+ (void) rebalance_left (treep);
+ }
+ return 0;
+ } else {
+ return 0;
+ }
+ }
+ /*NOTREACHED*/
+}
+
+/*
+ * delete a node from a tree
+ *
+ * this routine return non-zero if the tree has been shortened
+ */
+
+static int
+tree_delete (treep, old, bySize)
+tree **treep;
+tree *old;
+int bySize;
+{
+ tree *to_be_deleted;
+ tree *replacement;
+ tree *replacement_parent;
+ int replacement_direction;
+ int delete_direction;
+ tree *swap_temp;
+ int balance_temp;
+
+ if (!*treep)
+ /* node not found */
+ return 0;
+ if (LESS_THAN(*treep, old, bySize)) {
+ if (tree_delete (&(*treep)->right, old, bySize))
+ /*
+ * check the balance factors
+ * Note that the conditions are
+ * inverted from the insertion case
+ */
+ switch (--(*treep)->balance) {
+ case 0:
+ return 1;
+ case -1:
+ return 0;
+ case -2:
+ return rebalance_left (treep);
+ }
+ return 0;
+ } else if (GREATER_THAN(*treep, old, bySize)) {
+ if (tree_delete (&(*treep)->left, old, bySize))
+ switch (++(*treep)->balance) {
+ case 0:
+ return 1;
+ case 1:
+ return 0;
+ case 2:
+ return rebalance_right (treep);
+ }
+ return 0;
+ } else {
+ to_be_deleted = *treep;
+ /*
+ * find an empty down pointer (if any)
+ * and rehook the tree
+ */
+ if (!to_be_deleted->right) {
+ (*treep) = to_be_deleted->left;
+ return 1;
+ } else if (!to_be_deleted->left) {
+ (*treep) = to_be_deleted->right;
+ return 1;
+ } else {
+ /*
+ * if both down pointers are full, then
+ * move a node from the bottom of the tree up here.
+ *
+ * This builds an incorrect tree -- the replacement
+ * node and the to_be_deleted node will not
+ * be in correct order. This doesn't matter as
+ * the to_be_deleted node will obviously not leave
+ * this routine alive.
+ */
+ /*
+ * if the tree is left heavy, then go left
+ * else go right
+ */
+ replacement_parent = to_be_deleted;
+ if (to_be_deleted->balance == -1) {
+ delete_direction = -1;
+ replacement_direction = -1;
+ replacement = to_be_deleted->left;
+ while (replacement->right) {
+ replacement_parent = replacement;
+ replacement_direction = 1;
+ replacement = replacement->right;
+ }
+ } else {
+ delete_direction = 1;
+ replacement_direction = 1;
+ replacement = to_be_deleted->right;
+ while (replacement->left) {
+ replacement_parent = replacement;
+ replacement_direction = -1;
+ replacement = replacement->left;
+ }
+ }
+ /*
+ * swap the replacement node into
+ * the tree where the node is to be removed
+ *
+ * this would be faster if only the data
+ * element was swapped -- but that
+ * won't work for findleak. The alternate
+ * code would be:
+ data_temp = to_be_deleted->data;
+ to _be_deleted->data = replacement->data;
+ replacement->data = data_temp;
+ */
+ swap_temp = to_be_deleted->left;
+ to_be_deleted->left = replacement->left;
+ replacement->left = swap_temp;
+ swap_temp = to_be_deleted->right;
+ to_be_deleted->right = replacement->right;
+ replacement->right = swap_temp;
+ balance_temp = to_be_deleted->balance;
+ to_be_deleted->balance = replacement->balance;
+ replacement->balance = balance_temp;
+ /*
+ * if the replacement node is directly below
+ * the to-be-removed node, hook the to_be_deleted
+ * node below it (instead of below itself!)
+ */
+ if (replacement_parent == to_be_deleted)
+ replacement_parent = replacement;
+ if (replacement_direction == -1)
+ replacement_parent->left = to_be_deleted;
+ else
+ replacement_parent->right = to_be_deleted;
+ (*treep) = replacement;
+ /*
+ * delete the node from the sub-tree
+ */
+ if (delete_direction == -1) {
+ if (tree_delete (&(*treep)->left, old, bySize)) {
+ switch (++(*treep)->balance) {
+ case 2:
+ abort ();
+ case 1:
+ return 0;
+ case 0:
+ return 1;
+ }
+ }
+ return 0;
+ } else {
+ if (tree_delete (&(*treep)->right, old, bySize)) {
+ switch (--(*treep)->balance) {
+ case -2:
+ abort ();
+ case -1:
+ return 0;
+ case 0:
+ return 1;
+ }
+ }
+ return 0;
+ }
+ }
+ }
+ /*NOTREACHED*/
+}
+
+/*
+ * two routines to rebalance the tree.
+ *
+ * rebalance_right -- the right sub-tree is too long
+ * rebalance_left -- the left sub-tree is too long
+ *
+ * These routines are the heart of avl trees, I've tried
+ * to make their operation reasonably clear with comments,
+ * but some study will be necessary to understand the
+ * algorithm.
+ *
+ * these routines return non-zero if the resultant
+ * tree is shorter than the un-balanced version. This
+ * is only of interest to the delete routine as the
+ * balance after insertion can never actually shorten
+ * the tree.
+ */
+
+static
+rebalance_right (treep)
+tree **treep;
+{
+ tree *temp;
+ /*
+ * rebalance the tree
+ */
+ if ((*treep)->right->balance == -1) {
+ /*
+ * double whammy -- the inner sub-sub tree
+ * is longer than the outer sub-sub tree
+ *
+ * this is the "double rotation" from
+ * knuth. Scheme: replace the tree top node
+ * with the inner sub-tree top node and
+ * adjust the maze of pointers and balance
+ * factors accordingly.
+ */
+ temp = (*treep)->right->left;
+ (*treep)->right->left = temp->right;
+ temp->right = (*treep)->right;
+ switch (temp->balance) {
+ case -1:
+ temp->right->balance = 1;
+ (*treep)->balance = 0;
+ break;
+ case 0:
+ temp->right->balance = 0;
+ (*treep)->balance = 0;
+ break;
+ case 1:
+ temp->right->balance = 0;
+ (*treep)->balance = -1;
+ break;
+ }
+ temp->balance = 0;
+ (*treep)->right = temp->left;
+ temp->left = (*treep);
+ (*treep) = temp;
+ return 1;
+ } else {
+ /*
+ * a simple single rotation
+ *
+ * Scheme: replace the tree top node
+ * with the sub-tree top node
+ */
+ temp = (*treep)->right->left;
+ (*treep)->right->left = (*treep);
+ (*treep) = (*treep)->right;
+ (*treep)->left->right = temp;
+ /*
+ * only two possible configurations --
+ * if the right sub-tree was balanced, then
+ * *both* sides of it were longer than the
+ * left side, so the resultant tree will
+ * have a long leg (the left inner leg being
+ * the same length as the right leg)
+ */
+ if ((*treep)->balance == 0) {
+ (*treep)->balance = -1;
+ (*treep)->left->balance = 1;
+ return 0;
+ } else {
+ (*treep)->balance = 0;
+ (*treep)->left->balance = 0;
+ return 1;
+ }
+ }
+}
+
+static
+rebalance_left (treep)
+tree **treep;
+{
+ tree *temp;
+ /*
+ * rebalance the tree
+ */
+ if ((*treep)->left->balance == 1) {
+ /*
+ * double whammy -- the inner sub-sub tree
+ * is longer than the outer sub-sub tree
+ *
+ * this is the "double rotation" from
+ * knuth. Scheme: replace the tree top node
+ * with the inner sub-tree top node and
+ * adjust the maze of pointers and balance
+ * factors accordingly.
+ */
+ temp = (*treep)->left->right;
+ (*treep)->left->right = temp->left;
+ temp->left = (*treep)->left;
+ switch (temp->balance) {
+ case 1:
+ temp->left->balance = -1;
+ (*treep)->balance = 0;
+ break;
+ case 0:
+ temp->left->balance = 0;
+ (*treep)->balance = 0;
+ break;
+ case -1:
+ temp->left->balance = 0;
+ (*treep)->balance = 1;
+ break;
+ }
+ temp->balance = 0;
+ (*treep)->left = temp->right;
+ temp->right = (*treep);
+ (*treep) = temp;
+ return 1;
+ } else {
+ /*
+ * a simple single rotation
+ *
+ * Scheme: replace the tree top node
+ * with the sub-tree top node
+ */
+ temp = (*treep)->left->right;
+ (*treep)->left->right = (*treep);
+ (*treep) = (*treep)->left;
+ (*treep)->right->left = temp;
+ /*
+ * only two possible configurations --
+ * if the left sub-tree was balanced, then
+ * *both* sides of it were longer than the
+ * right side, so the resultant tree will
+ * have a long leg (the right inner leg being
+ * the same length as the left leg)
+ */
+ if ((*treep)->balance == 0) {
+ (*treep)->balance = 1;
+ (*treep)->right->balance = -1;
+ return 0;
+ } else {
+ (*treep)->balance = 0;
+ (*treep)->right->balance = 0;
+ return 1;
+ }
+ }
+}
+
+#ifdef DEBUG
+
+static
+depth (treep)
+tree *treep;
+{
+ int ldepth, rdepth;
+
+ if (!treep)
+ return 0;
+ ldepth = depth (treep->left);
+ rdepth = depth (treep->right);
+ if (ldepth > rdepth)
+ return ldepth + 1;
+ return rdepth + 1;
+}
+
+static tree *
+left_most (treep)
+tree *treep;
+{
+ while (treep && treep->left)
+ treep = treep->left;
+ return treep;
+}
+
+static tree *
+right_most (treep)
+tree *treep;
+{
+ while (treep && treep->right)
+ treep = treep->right;
+ return treep;
+}
+
+tree_verify (treep)
+tree *treep;
+{
+ tree_data left_data, right_data;
+
+ if (!treep)
+ return 1;
+ if (treep->left)
+ left_data = right_most (treep->left)->data;
+ else
+ left_data = treep->data - 1;
+ if (treep->right)
+ right_data = left_most (treep->right)->data;
+ else
+ right_data = treep->data + 1;
+ if (treep->data < left_data || treep->data > right_data) {
+ abort ();
+ return 0;
+ }
+ if (treep->balance != depth (treep->right) - depth (treep->left)) {
+ abort ();
+ return 0;
+ }
+ return tree_verify (treep->left) && tree_verify (treep->right);
+}
+
+#endif
diff --git a/nx-X11/util/memleak/ftest.c b/nx-X11/util/memleak/ftest.c
new file mode 100644
index 000000000..420f42c2f
--- /dev/null
+++ b/nx-X11/util/memleak/ftest.c
@@ -0,0 +1,55 @@
+/*
+ * $Xorg: ftest.c,v 1.4 2001/02/09 02:06:19 xorgcvs Exp $
+ *
+Copyright 1992, 1998 The Open Group
+
+Permission to use, copy, modify, distribute, and sell this software and its
+documentation for any purpose is hereby granted without fee, provided that
+the above copyright notice appear in all copies and that both that
+copyright notice and this permission notice appear in supporting
+documentation.
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
+AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+Except as contained in this notice, the name of The Open Group shall not be
+used in advertising or otherwise to promote the sale, use or other dealings
+in this Software without prior written authorization from The Open Group.
+ *
+ * Author: Keith Packard, MIT X Consortium
+ */
+
+static char *foo, *bar, *bletch, *snarf;
+static char *glorf[100];
+
+extern char *malloc ();
+
+main ()
+{
+ int i;
+
+ foo = malloc (1000);
+ bar = malloc (2000);
+ bletch = malloc (3000);
+ snarf = malloc(1000);
+ for (i = 0; i < 100; i++)
+ glorf[i] = malloc (i * 200);
+ for (i = 0; i < 100; i++) {
+ free (glorf[i]);
+ glorf[i] = 0;
+ }
+ *(char **)snarf = bletch;
+ free (foo);
+ free (bletch);
+ bletch = 0;
+ *foo = 'a';
+ bar = 0;
+ CheckMemory ();
+}
diff --git a/nx-X11/util/memleak/getreti386.c b/nx-X11/util/memleak/getreti386.c
new file mode 100644
index 000000000..80038b7cc
--- /dev/null
+++ b/nx-X11/util/memleak/getreti386.c
@@ -0,0 +1,54 @@
+/*
+ * some bits copied from mprof by Ben Zorn
+ *
+ * Copyright (c) 1995 Jeffrey Hsu
+ */
+
+/* $XFree86: xc/util/memleak/getreti386.c,v 3.2 1996/10/16 14:46:28 dawes Exp $ */
+
+#define get_current_fp(first_local) ((unsigned)&(first_local) + 4)
+#define prev_fp_from_fp(fp) *((unsigned *) fp)
+#define ret_addr_from_fp(fp) *((unsigned *) (fp+4))
+
+#ifdef __FreeBSD__
+#define CRT0_ADDRESS 0x10d3
+#endif
+#if defined(__NetBSD__) || defined(__OpenBSD__)
+#define CRT0_ADDRESS 0x109a
+#endif
+#ifdef linux
+#define CRT0_ADDRESS 0x80482fc
+#endif
+
+static unsigned long
+junk (int *foo)
+{
+ return (unsigned long) foo + 4;
+}
+
+void
+getStackTrace(unsigned long *results, int max)
+{
+
+ int first_local;
+ unsigned long fp, ret_addr;
+
+ first_local = 0;
+ fp = junk(&first_local);
+ fp = get_current_fp(first_local);
+ ret_addr = ret_addr_from_fp(fp);
+
+ while (ret_addr > CRT0_ADDRESS && max-- > 1) {
+ *results++ = ret_addr;
+ if (fp < (unsigned long) &first_local)
+ break;
+ fp = prev_fp_from_fp(fp);
+ if (!fp)
+ break;
+ if (fp < (unsigned long) &first_local)
+ break;
+ ret_addr = ret_addr_from_fp(fp);
+ }
+ *results++ = 0;
+
+}
diff --git a/nx-X11/util/memleak/getretmips.c b/nx-X11/util/memleak/getretmips.c
new file mode 100644
index 000000000..3b89c6f51
--- /dev/null
+++ b/nx-X11/util/memleak/getretmips.c
@@ -0,0 +1,198 @@
+/*
+ * $Xorg: getretmips.c,v 1.4 2001/02/09 02:06:19 xorgcvs Exp $
+ *
+Copyright 1992, 1998 The Open Group
+
+Permission to use, copy, modify, distribute, and sell this software and its
+documentation for any purpose is hereby granted without fee, provided that
+the above copyright notice appear in all copies and that both that
+copyright notice and this permission notice appear in supporting
+documentation.
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
+AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+Except as contained in this notice, the name of The Open Group shall not be
+used in advertising or otherwise to promote the sale, use or other dealings
+in this Software without prior written authorization from The Open Group.
+ *
+ * Author: Keith Packard, MIT X Consortium
+ */
+
+/* Return stack generation for MIPS processors
+ * This is tricky as MIPS stack frames aren't
+ * easily unrolled -- we look for pc restoration
+ * and stack adjustment instructions beyond the return
+ * address to discover the correct values
+ */
+
+/* lw $31,const($sp) is : 100 011 11101 11111 const */
+/* 1000 1111 1011 1111 */
+
+#define RESTORE_RETURNVAL 0x8fbf0000
+#define RESTORE_RETURNVAL_MASK 0xffff0000
+
+/* addiu $sp, $sp, const is 001 001 11101 11101 const */
+/* 0010 0111 1011 1101 const */
+
+#define ADJUST_STACKP_C 0x27bd0000
+#define ADJUST_STACKP_C_MASK 0xffff0000
+
+/* addu $sp, $sp, $at is 000 000 11101 00001 11101 00000 100 001 */
+/* 0000 0011 1010 0001 1110 1000 0010 0001 */
+
+#define ADJUST_STACKP_V 0x03a1e821
+#define ADJUST_STACKP_V_MASK 0xffffffff
+
+/* lui $at, const is 001 111 00000 00001 const */
+/* 0011 1100 0000 0001 const */
+
+#define SET_UPPER_C 0x3c010000
+#define SET_UPPER_C_MASK 0xffff0000
+
+/* ori $at, $at, const is 001 101 00001 00001 const */
+/* 0011 0100 0010 0001 const */
+
+#define OR_LOWER_C 0x34210000
+#define OR_LOWER_C_MASK 0xffff0000
+
+/* ori $at, $zero, const is 001 101 00000 00001 const */
+/* 0011 0100 0000 0001 const */
+
+#define SET_LOWER_C 0x34010000
+#define SET_LOWER_C_MASK 0xffff0000
+
+/* jr $ra */
+#define RETURN 0x03e00008
+
+#define CALL(f) (0x0c000000 | (((int) (f)) >> 2))
+
+/*
+ * This computation is expensive, so we cache the results;
+ * a simple hash function and straight-forward replacement.
+ */
+
+#define HASH_SIZE 256
+
+typedef struct _returnCache {
+ unsigned long *returnAddress;
+ long raOffset;
+ long spAdjust;
+} ReturnCacheRec, *ReturnCachePtr;
+
+static ReturnCacheRec returnCache[HASH_SIZE];
+
+#define HASH(ra) ((((int) (ra)) >> 2) & (HASH_SIZE - 1))
+
+typedef int Bool;
+
+#define TRUE 1
+#define FALSE 0
+
+getStackTrace (results, max)
+ unsigned long *results;
+ int max;
+{
+ extern unsigned long *getReturnAddress (), *getStackPointer ();
+ extern int main ();
+ unsigned long *ra, *ra_limit;
+ unsigned long *sp;
+ unsigned long inst;
+ unsigned long mainCall;
+ unsigned short const_upper;
+ unsigned short const_lower;
+ long ra_offset;
+ long sp_adjust;
+ Bool found_ra_offset, found_sp_adjust;
+ Bool found_const_upper, found_const_lower;
+ ReturnCachePtr rc;
+
+ ra = getReturnAddress ();
+ sp = getStackPointer ();
+ mainCall = CALL(main);
+ while (ra && max) {
+ rc = &returnCache[HASH(ra)];
+ if (rc->returnAddress != ra)
+ {
+ found_ra_offset = FALSE;
+ found_sp_adjust = FALSE;
+ found_const_upper = FALSE;
+ found_const_lower = FALSE;
+ const_upper = 0;
+ const_lower = 0;
+ rc->returnAddress = ra;
+ ra_limit = (unsigned long *) 0x10000000;
+ ra_offset = 0;
+ sp_adjust = -1;
+ while ((!found_ra_offset || !found_sp_adjust) && ra < ra_limit)
+ {
+ inst = *ra;
+ /* look for the offset of the PC in the stack frame */
+ if ((inst & RESTORE_RETURNVAL_MASK) == RESTORE_RETURNVAL)
+ {
+ ra_offset = inst & ~RESTORE_RETURNVAL_MASK;
+ found_ra_offset = TRUE;
+ }
+ else if ((inst & ADJUST_STACKP_C_MASK) == ADJUST_STACKP_C)
+ {
+ sp_adjust = inst & ~ADJUST_STACKP_C_MASK;
+ found_sp_adjust = TRUE;
+ }
+ else if ((inst & ADJUST_STACKP_V_MASK) == ADJUST_STACKP_V)
+ {
+ sp_adjust = 0;
+ found_sp_adjust = TRUE;
+ }
+ else if ((inst & SET_UPPER_C_MASK) == SET_UPPER_C)
+ {
+ const_upper = inst & ~SET_UPPER_C_MASK;
+ const_lower = 0;
+ found_const_upper = TRUE;
+ }
+ else if ((inst & OR_LOWER_C_MASK) == OR_LOWER_C)
+ {
+ const_lower = inst & ~OR_LOWER_C_MASK;
+ found_const_lower = TRUE;
+ }
+ else if ((inst & SET_LOWER_C_MASK) == SET_LOWER_C)
+ {
+ const_lower = inst & ~SET_LOWER_C_MASK;
+ const_upper = 0;
+ found_const_lower = TRUE;
+ }
+ else if (inst == RETURN)
+ ra_limit = ra + 2;
+ ra++;
+ }
+ if (sp_adjust == 0 && (found_const_upper || found_const_lower))
+ sp_adjust = (const_upper << 16) | const_lower;
+ rc->raOffset = ra_offset;
+ rc->spAdjust = sp_adjust;
+ }
+ /* if something went wrong, punt */
+ if (rc->spAdjust <= 0)
+ {
+ *results++ = 0;
+ break;
+ }
+ ra = (unsigned long *) sp[rc->raOffset>>2];
+ sp += rc->spAdjust >> 2;
+ if (ra[-2] == mainCall)
+ {
+ *results++ = 0;
+ break;
+ }
+ else
+ {
+ *results++ = ((unsigned long) ra) - 8;
+ }
+ max--;
+ }
+}
diff --git a/nx-X11/util/memleak/getretspar.c b/nx-X11/util/memleak/getretspar.c
new file mode 100644
index 000000000..4ed71ce2c
--- /dev/null
+++ b/nx-X11/util/memleak/getretspar.c
@@ -0,0 +1,66 @@
+/*
+ * $Xorg: getretspar.c,v 1.4 2001/02/09 02:06:19 xorgcvs Exp $
+ *
+Copyright 1992, 1998 The Open Group
+
+Permission to use, copy, modify, distribute, and sell this software and its
+documentation for any purpose is hereby granted without fee, provided that
+the above copyright notice appear in all copies and that both that
+copyright notice and this permission notice appear in supporting
+documentation.
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
+AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+Except as contained in this notice, the name of The Open Group shall not be
+used in advertising or otherwise to promote the sale, use or other dealings
+in this Software without prior written authorization from The Open Group.
+ *
+ * Author: Keith Packard, MIT X Consortium
+ */
+
+/* Trace up the stack and build a call history -- SPARC specific code */
+
+/* hack -- flush out the register windows by recursing */
+
+static void
+flushWindows (depth)
+{
+ if (depth == 0)
+ return;
+ flushWindows (depth-1);
+}
+
+getStackTrace (results, max)
+ unsigned long *results;
+ int max;
+{
+ unsigned long *sp, *getStackPointer (), *getFramePointer();
+ unsigned long *ra, mainCall;
+ extern int main ();
+
+ flushWindows (32);
+ sp = getFramePointer ();
+ while (max)
+ {
+ /* sparc stack traces are easy -- chain up the saved FP/SP values */
+ ra = (unsigned long *) sp[15];
+ sp = (unsigned long *) sp[14];
+ /* stop when we get the call to main */
+ mainCall = ((((unsigned long) main) - ((unsigned long) ra)) >> 2) | 0x40000000;
+ if (ra[0] == mainCall)
+ {
+ *results++ = 0;
+ break;
+ }
+ *results++ = (unsigned long) ra;
+ max--;
+ }
+}
diff --git a/nx-X11/util/memleak/getrettest.c b/nx-X11/util/memleak/getrettest.c
new file mode 100644
index 000000000..7f3c88641
--- /dev/null
+++ b/nx-X11/util/memleak/getrettest.c
@@ -0,0 +1,48 @@
+/*
+ * $Xorg: getrettest.c,v 1.4 2001/02/09 02:06:19 xorgcvs Exp $
+ *
+Copyright 1992, 1998 The Open Group
+
+Permission to use, copy, modify, distribute, and sell this software and its
+documentation for any purpose is hereby granted without fee, provided that
+the above copyright notice appear in all copies and that both that
+copyright notice and this permission notice appear in supporting
+documentation.
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
+AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+Except as contained in this notice, the name of The Open Group shall not be
+used in advertising or otherwise to promote the sale, use or other dealings
+in this Software without prior written authorization from The Open Group.
+ *
+ * Author: Keith Packard, MIT X Consortium
+ */
+
+main ()
+{
+ f ();
+}
+
+f ()
+{
+ g ();
+}
+
+
+g ()
+{
+ unsigned long returnStack[16];
+ int i;
+
+ getStackTrace (returnStack, 16);
+ for (i = 0; i < 16 && returnStack[i]; i++)
+ printf ("%2d: 0x%lx\n", i, returnStack[i]);
+}
diff --git a/nx-X11/util/memleak/mipsstack.s b/nx-X11/util/memleak/mipsstack.s
new file mode 100644
index 000000000..bc69ba971
--- /dev/null
+++ b/nx-X11/util/memleak/mipsstack.s
@@ -0,0 +1,43 @@
+/*
+ * $Xorg: mipsstack.s,v 1.4 2001/02/09 02:06:19 xorgcvs Exp $
+ *
+Copyright 1992, 1998 The Open Group
+
+Permission to use, copy, modify, distribute, and sell this software and its
+documentation for any purpose is hereby granted without fee, provided that
+the above copyright notice appear in all copies and that both that
+copyright notice and this permission notice appear in supporting
+documentation.
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
+AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+Except as contained in this notice, the name of The Open Group shall not be
+used in advertising or otherwise to promote the sale, use or other dealings
+in this Software without prior written authorization from The Open Group.
+ *
+ * Author: Keith Packard, MIT X Consortium
+ */
+
+ .globl getReturnAddress
+ .ent getReturnAddress
+getReturnAddress:
+ .frame $sp, 0, $31
+ move $2,$31
+ j $31
+ .end getReturnAddress
+
+ .globl getStackPointer
+ .ent getStackPointer
+getStackPointer:
+ .frame $sp, 0, $31
+ move $2,$29
+ j $31
+ .end getStackPointer
diff --git a/nx-X11/util/memleak/sparcsolstack.s b/nx-X11/util/memleak/sparcsolstack.s
new file mode 100644
index 000000000..3f6ab0586
--- /dev/null
+++ b/nx-X11/util/memleak/sparcsolstack.s
@@ -0,0 +1,11 @@
+! $Xorg: sparcsolstack.s,v 1.3 2000/08/17 19:55:20 cpqbld Exp $
+ .seg "text"
+ .proc 16
+ .globl getStackPointer
+getStackPointer:
+ retl
+ mov %sp,%o0
+ .globl getFramePointer
+getFramePointer:
+ retl
+ mov %fp,%o0
diff --git a/nx-X11/util/memleak/sparcstack.s b/nx-X11/util/memleak/sparcstack.s
new file mode 100644
index 000000000..a67114f24
--- /dev/null
+++ b/nx-X11/util/memleak/sparcstack.s
@@ -0,0 +1,11 @@
+# $Xorg: sparcstack.s,v 1.3 2000/08/17 19:55:20 cpqbld Exp $
+ .seg "text"
+ .proc 16
+ .globl _getStackPointer
+_getStackPointer:
+ retl
+ mov %sp,%o0
+ .globl _getFramePointer
+_getFramePointer:
+ retl
+ mov %fp,%o0
diff --git a/nx-X11/util/memleak/stackbottom.c b/nx-X11/util/memleak/stackbottom.c
new file mode 100644
index 000000000..bd1a97a6a
--- /dev/null
+++ b/nx-X11/util/memleak/stackbottom.c
@@ -0,0 +1,119 @@
+/*
+ * cut and paste from gc 4.4 by Hans-J. Boehm and Alan J. Demers
+ *
+ * Cutter and Paster: Jeffrey Hsu
+ */
+
+/* $XFree86: xc/util/memleak/stackbottom.c,v 3.1 1996/12/31 05:02:27 dawes Exp $ */
+
+#include <signal.h>
+
+typedef char * ptr_t; /* A generic pointer to which we can add */
+ /* byte displacements. */
+ /* Preferably identical to caddr_t, if it */
+ /* exists. */
+
+#ifndef bool
+typedef int bool;
+#endif
+
+#define VOLATILE volatile
+
+# ifndef STACK_GROWS_UP
+# define STACK_GROWS_DOWN
+# endif
+
+typedef unsigned long word;
+
+#define TRUE 1
+
+#if defined(__alpha) || defined(__alpha__)
+ extern __start
+# define HEURISTIC2_LIMIT ((ptr_t)((word)(&__start) & ~(getpagesize()-1)))
+#endif
+
+void GC_noop() {}
+
+ /* Some tools to implement HEURISTIC2 */
+# define MIN_PAGE_SIZE 256 /* Smallest conceivable page size, bytes */
+# include <setjmp.h>
+ /* static */ jmp_buf GC_jmp_buf;
+
+ /*ARGSUSED*/
+ void GC_fault_handler(sig)
+ int sig;
+ {
+ longjmp(GC_jmp_buf, 1);
+ }
+
+ typedef void (*handler)(int);
+
+ /* Return the first nonaddressible location > p (up) or */
+ /* the smallest location q s.t. [q,p] is addressible (!up). */
+ ptr_t GC_find_limit(p, up)
+ ptr_t p;
+ bool up;
+ {
+ static VOLATILE ptr_t result;
+ /* Needs to be static, since otherwise it may not be */
+ /* preserved across the longjmp. Can safely be */
+ /* static since it's only called once, with the */
+ /* allocation lock held. */
+
+ static handler old_segv_handler, old_bus_handler;
+ /* See above for static declaration. */
+
+ old_segv_handler = signal(SIGSEGV, GC_fault_handler);
+# ifdef SIGBUS
+ old_bus_handler = signal(SIGBUS, GC_fault_handler);
+# endif
+ if (setjmp(GC_jmp_buf) == 0) {
+ result = (ptr_t)(((word)(p))
+ & ~(MIN_PAGE_SIZE-1));
+ for (;;) {
+ if (up) {
+ result += MIN_PAGE_SIZE;
+ } else {
+ result -= MIN_PAGE_SIZE;
+ }
+ GC_noop(*result);
+ }
+ }
+ (void) signal(SIGSEGV, old_segv_handler);
+# ifdef SIGBUS
+ (void) signal(SIGBUS, old_bus_handler);
+# endif
+ if (!up) {
+ result += MIN_PAGE_SIZE;
+ }
+ return(result);
+ }
+
+ptr_t GC_get_stack_base()
+{
+ word dummy;
+ static ptr_t result;
+
+ if (!result) {
+
+# ifdef STACK_GROWS_DOWN
+ result = GC_find_limit((ptr_t)(&dummy), TRUE);
+# ifdef HEURISTIC2_LIMIT
+ if (result > HEURISTIC2_LIMIT
+ && (ptr_t)(&dummy) < HEURISTIC2_LIMIT) {
+ result = HEURISTIC2_LIMIT;
+ }
+# endif
+# else
+ result = GC_find_limit((ptr_t)(&dummy), FALSE);
+# ifdef HEURISTIC2_LIMIT
+ if (result < HEURISTIC2_LIMIT
+ && (ptr_t)(&dummy) > HEURISTIC2_LIMIT) {
+ result = HEURISTIC2_LIMIT;
+ }
+# endif
+# endif
+ }
+
+ return(result);
+}