Trailing-Edge
-
PDP-10 Archives
-
SRI_NIC_PERM_FS_1_19910112
-
c/kcc5/bugmlc.mail
There are no other files named bugmlc.mail in the archive.
5-May-88 14:58:47-PDT,2753;000000000001
Return-Path: <[email protected]>
Received: from SCIENCE.UTAH.EDU by SRI-NIC.ARPA with TCP; Thu, 5 May 88 14:58:42 PDT
Date: Thu 5 May 88 15:58:47-MDT
From: "Nelson H.F. Beebe" <[email protected]>
Subject: Improved malloc.c
To: [email protected]
cc: [email protected]
X-US-Mail: "Center for Scientific Computing, South Physics, University of Utah, Salt Lake City, UT 84112"
X-Telephone: (801) 581-5254
Message-ID: <[email protected]>
This message will be followed by 2 more, containing malloc.c
and mtest.c.
I've got the new code in malloc.c working properly.
malloc()/realloc() now write a single magic word at the end
of each allocated block, and free() checks that it is intact
when the block is freed, and aborts if it has been
clobbered. This should catch the most likely case of misuse
of dynamic memory -- writing beyond the end of the allocated
block; writing before the allocated block is much less likely.
There is actually zero space overhead for this, compared to
the old version, because (a) I've changed the rounding to
4-byte, instead of 8-byte, boundaries (quite okay for a
word-addressable machine), and (b) I found 2 more harmless
errors--2 of the 3 calls to split() passed not the desired
data length, but the length of data + overhead, resulting in
wasting 6 words (24 bytes) per split() call. The time
overhead is negligible, since it involves only a single
comparison at free() time, and a single store at
malloc()/realloc() time.
If you do
kcc -o mtest mtest.c malloc.c
you get the standard version of the memory test program I
found on the net, and
kcc -o mtest -DDBG mtest.c malloc.c
will produce a version with tracing of malloc/realloc/free
calls.
I've tried several tests:
mtest 100 100 50
mtest 200 200 75
mtest 200 200 25
mtest 200 200 10
mtest 1000 1000 10
The larger the first 2 numbers, the longer the test runs.
During development of the new malloc(), mtest caught
corruption errors numerous times that free() later detected
and aborted on, so I know the checking code works. Because
of the rounding of requests to 4-byte boundaries, the magic
checkword at the end of the block will not catch all
errors--a request for 4n+p bytes (p in 1..3) will allow
overwriting 4-p bytes before the magic checkword is
clobbered.
The value of the magic checkword was chosen to have 4 unique
9-bit bytes, all of which have the high-order bit on, and
are therefore unlikely to be generated by any non-binary
character processing application. If they are read, instead
of written, code could detect that, but in most cases would
not, since ILDB/IDBP instructions discard high-order unused
bits.
-------
5-May-88 15:00:14-PDT,20215;000000000001
Return-Path: <[email protected]>
Received: from SCIENCE.UTAH.EDU by SRI-NIC.ARPA with TCP; Thu, 5 May 88 14:59:39 PDT
Date: Thu 5 May 88 15:59:36-MDT
From: "Nelson H.F. Beebe" <[email protected]>
Subject: new malloc.c
To: [email protected]
cc: [email protected]
X-US-Mail: "Center for Scientific Computing, South Physics, University of Utah, Salt Lake City, UT 84112"
X-Telephone: (801) 581-5254
Message-ID: <[email protected]>
/*
* MALLOC - memory allocation for C programs (first fit)
*
* Copyright (C) 1986 by Ian Macky, SRI International
*
* Block in use, pointed to by a (char *) pointer:
*
* +-----------------------------------------------+
* flag | IN_USE |
* +-----------------------------------------------+
* size | Total size of block (in bytes) |
* +-----------------------------------------------+
* above | (free_block *) to block above in memory |
* +-----------------------------------------------+
* (char *) ptr ---> | . |
* . . .
* . Block data .
* . . .
* | . |
* +-----------------------------------------------+
* | MAGIC_CHECKWORD |
* +-----------------------------------------------+
*
* When a block is freed, if the next sequential block in memory is
* IN_USE, it's "above" pointer is set to point up to that free block.
* The contents of the following word are always checked against
* MAGIC_CHECKWORD to trap block overwrites.
*
* Block on freelist:
*
* +-----------------------------------------------+
* flag | FREE |
* +-----------------------------------------------+
* size | Total size of block |
* +-----------------------------------------------+
* previous| (free_block *) to previous block on freelist |
* +-----------------------------------------------+
* next | (free_block *) to next block on freelist |
* +-----------------------------------------------+
* | . |
* . . .
* . Unused .
* . . .
* | . |
* +-----------------------------------------------+
*
* The variable free_head points to the head of the linked-list of free
* blocks. When the freelist is empty, free_head contains NULL.
*
* top_block is the address of the very first block in memory, or NULL
* if none have been allocated yet.
*/
#include "c-env.h"
/* #include "stddef.h" */ /* for size_t (but conflict with sys/types) */
#include "stdio.h"
#include "sys/types.h" /* For caddr_t and size_t */
extern caddr_t sbrk();
#ifndef MALLOC_CHECK
#define MALLOC_CHECK 1 /* runtime check for block validity? */
#endif
#if 0
typedef double largest_t; /* this type requires max storage */
#else
/*
* No need on word-addressable architecture to round up to double-word
* boundary. Also, word-alignment will force MAGIC_CHECKWORD into word
* following last word requested by user, so we are more likely to trap
* errors at free() time.
*/
typedef int largest_t; /* this type requires max storage */
#endif
typedef int blksiz_t; /* maybe "long" for some machines */
struct free_header {
int flag; /* always FREE, for verification */
blksiz_t size; /* size in bytes of data area */
struct free_header *previous; /* pointer to previous block on f.l. */
struct free_header *next; /* pointer to next block in freelist */
};
#define free_block struct free_header
struct used_header {
int flag; /* always IN_USE, for verification */
blksiz_t size; /* size in bytes of data area */
free_block *above; /* pointer to above block in memory */
};
#define used_block struct used_header
/*
* these bit-patterns are pretty unlikely to stumble on by accident
*/
#define FREE (-'!' - 'F' - 'r' - 'e' - 'e' - '!')
#define IN_USE (-'I' - 'n' - ' ' - 'u' - 's' - 'e')
/*
* We want MAGIC_CHECKWORD to have some bits on in all 4 9-bit bytes,
* and also to not look like normal character data, so each byte has
* the high-order bit on.
*/
#define MAGIC_CHECKWORD 0476567675765
#define MAGIC_WORD(block,bytes) *(((int*)(block)) + \
((bytes) - sizeof(MAGIC_CHECKWORD))/sizeof(int))
/*
* make sure the block header is a multiple of CHUNK_SIZE bytes long,
* so the data area remains on a boundry suitable for any type
*/
#define CHUNK_SIZE (sizeof(largest_t))
#define ROUND_D(n, m) (((n - 1) / m) + 1)
#define ROUND_N(n, m) (ROUND_D(n, m) * m)
#define ROUNDUP(n) ROUND_N(n, CHUNK_SIZE)
/*
* Overhead accounts for the block headers, but NOT for the MAGIC_CHECKWORD
* block trailer.
*/
#define OVERHEAD ROUNDUP((sizeof(struct free_header) >\
sizeof(struct used_header))\
? sizeof(struct free_header) \
: sizeof(struct used_header))
static free_block *top_block = NULL; /* pointer to very 1st block in mem */
/*
* initialization for freelist pointer
*/
static free_block *free_head = NULL;
void free(), cfree(), _pfree(); /* free previously allocated blocks */
static void split(); /* split up a block that's too big */
static void _setup(); /* set up a new in-use block */
static int *boundrize(); /* one time only, get to a good boundry */
static void izero(), icopy(); /* zero out or copy a block of ints */
/*
* malloc - allocate a block of memory big enough to accomodate
* "size" bytes. a char pointer is returned to the data area,
* which is NOT initialized. the requested size is rounded up
* to a multiple of CHUNK_SIZE bytes, to keep blocks on boundry
* of largest data-type.
*
* mlalloc is the same as malloc, except its arg is a long instead
* of just an int - one just calls the other. who's on first
* depends on whether longs are equivalent to ints or not.
*/
char *
mlalloc(size)
unsigned long size;
{
char *malloc();
return malloc((size_t) size);
}
char *
malloc(size)
size_t size;
{
free_block *old;
used_block *new, *below;
char *area;
blksiz_t need = size; /* Get into convenient type */
if (need <= 0) /* range check argument */
return NULL;
need = ROUNDUP(need) + OVERHEAD + sizeof(MAGIC_CHECKWORD);
/* total size w/overhead */
/*
* look through the freelist for a fit
*/
for (old = free_head; old != NULL; old = old->next) {
#if MALLOC_CHECK
if (old->flag != FREE) {
fprintf(stderr, "malloc(): bad block on freelist (%o,,%o)\n",
((unsigned) old) >> 18, ((unsigned) old) & 0777777);
fflush(stderr);
abort();
}
#endif
if (old->size >= need) { /* is this block big enough for us? */
#if 0
split(old, need); /* yes, but only keep what we need */
#else
split(old, size); /* yes, but only keep what we need */
#endif
if (!old->previous) free_head = old->next;
else old->previous->next = old->next;
if (old->next) old->next->previous = old->previous;
new = (used_block *) old;
new->flag = IN_USE;
new->above = NULL;
below = (used_block *) ((char *) new + new->size);
if (below->flag == IN_USE) below->above = NULL;
return ((char *) new) + OVERHEAD; /* return ptr to data area */
}
}
/*
* didn't find a block big enough so allocate new space.
*/
if (!top_block) boundrize(); /* get on good initial boundry */
area = (char *)sbrk(need); /* allocate space */
if ((int) area == -1) /* get what we requested? */
return NULL; /* nope, no more room at the inn */
new = (used_block *) area; /* got it, make pointer */
_setup(new, need); /* mark up block */
return ((char *) new) + OVERHEAD; /* return pointer to data area */
}
/*
* get on a good initial boundry, which means an even word boundry.
* we always go to the word after what sbrk(0) says is available,
* in case that word is partly in use, plus getting on an even word
* boundry.
*/
static int *boundrize()
{
int *int_align; /* on these type boundries */
char *cp;
cp = (char *)sbrk(0); /* initial starting point */
int_align = ((int *) cp) + 1; /* turn into an int pointer */
if ((int) int_align & 1) /* if not on an even word boundry, */
int_align++; /* bump up to it. */
brk((char *) int_align); /* get on the boundry. */
top_block = (free_block *) int_align;
return int_align;
}
/*
* set up the given block as used. flag it, fill in the header,
* check the next block down in memory to see if it should point
* back up, etc.
*/
static void _setup(block, size)
used_block *block;
int size;
{
used_block *below;
block->flag = IN_USE; /* and mark that it's being used */
block->size = size; /* set total size of block */
block->above = NULL; /* for now; set by others */
MAGIC_WORD(block,size) = MAGIC_CHECKWORD;
below = (used_block *) ((char *) block + size);
if (below->flag == IN_USE) /* if below block used to have a */
below->above = NULL; /* free block above, change that. */
}
/*
* split - split a block into a chunk of given size and a remainder,
* which is freed. a remainder block is not made unless it is of at
* least CHUNK_SIZE data bytes, to keep from having too many small,
* not very useful, fragmented blocks.
*/
static void split(block, newsize)
free_block *block;
blksiz_t newsize;
{
used_block *residue;
newsize = ROUNDUP(newsize) + OVERHEAD + sizeof(MAGIC_CHECKWORD);
if (newsize > 0 && (block->size - newsize) >= CHUNK_SIZE +
OVERHEAD + sizeof(MAGIC_CHECKWORD)) {
residue = (used_block *) ((char *) block + newsize);
#if MALLOC_CHECK
residue->flag = IN_USE;
#endif
residue->size = block->size - newsize;
residue->above = NULL;
block->size = newsize;
MAGIC_WORD(block,newsize) = MAGIC_CHECKWORD;
free((char *) residue + OVERHEAD);
}
}
/*
* calloc - allocate a block of memory big enough to accomodate
* elt_count elements each of size elt_size. a pointer to the
* first region is returned, and the region itself is cleared
* to zeroes. since m(l)alloc always returns a pointer to a
* region starting on a boundry which can accomodate ANY type,
* no more boundry twiddling need be done by this routine.
*/
char *
clalloc(elt_count, elt_size)
unsigned long elt_count, elt_size;
{
char *calloc();
return calloc((size_t) elt_count, (size_t) elt_size);
}
char *
calloc(elt_count, elt_size)
size_t elt_count, elt_size;
{
blksiz_t size;
char *cp;
cp = malloc(size = elt_count * elt_size);
if (cp)
izero((int *) cp, ROUND_D(size, sizeof(int)));
return cp;
}
/*
* page allocation. alas, since the data area needs to start right at
* a page boundry, the header that comes before the data area must be
* in the previous page, rendering it useless for page allocation.
* which means sequential 1-page _palloc's return every other page, with
* smaller-than-a-page free chunks between them.
*/
#define PAGE_SIZE 512 /* number of words/page */
#define ADDRESS_SPACE 1000 /* size of address space in pages */
int _palloc(n)
int n;
{
free_block *old;
used_block *new;
int *area, map_size, need, next_page, pre_page;
if (n < 1 || n > ADDRESS_SPACE) return NULL; /* verify arg */
map_size = n * PAGE_SIZE * sizeof(int); /* # of chars in map */
need = map_size + OVERHEAD + sizeof(MAGIC_CHECKWORD);
/* same but w/OVH */
for (old = free_head; old != NULL; old = old->next) {
#if MALLOC_CHECK
if (old->flag != FREE) {
fprintf(stderr, "_palloc(): bad block on freelist (%o,,%o)\n",
((unsigned) old) >> 18, ((unsigned) old) & 0777777);
fflush(stderr);
abort();
}
#endif
if (old->size < need) continue; /* big enough for us? */
next_page = (((int) old / PAGE_SIZE) + 1) * PAGE_SIZE;
pre_page = (next_page - (int) old) * sizeof(int);
if (pre_page < sizeof(struct used_header) + CHUNK_SIZE)
continue; /* too close to next page. */
if (old->size - pre_page < map_size)
continue; /* not aligned right. */
split(old, pre_page + map_size); /* trim excess */
old->size = pre_page - OVERHEAD; /* new old size */
new = (used_block *) (next_page - (OVERHEAD / sizeof(int)));
_setup(new, need); /* set up block, flag &tc */
new->above = old; /* manually set this. */
return next_page / PAGE_SIZE; /* return page # */
}
/*
* nothing useable on the free_list, so make a new block
*/
area = (!top_block) ? boundrize() : (int *) sbrk(0); /* EOM */
next_page = (((int) area / PAGE_SIZE) + 1) * PAGE_SIZE;
pre_page = (next_page - (int) area) * sizeof(int);
if (pre_page < sizeof(struct used_header) + OVERHEAD +
sizeof(MAGIC_CHECKWORD)) {
next_page += PAGE_SIZE; /* not enough room, go to next page */
pre_page += PAGE_SIZE * sizeof(int);
}
area = (int *) sbrk(pre_page + map_size); /* allocate the space */
if ((int) area == -1) return NULL; /* no more room at the inn */
old = (free_block *) area; /* point to allocated area */
old->flag = FREE; /* leader will be FREE. */
old->size = pre_page - OVERHEAD; /* set the size of the leader */
old->previous = NULL; /* now splice it into the free list. */
old->next = free_head; /* put this at the top of the chain. */
free_head = old; /* point to part we really want */
new = (used_block *) (next_page - OVERHEAD / sizeof(int));
_setup(new, need); /* mark it up as in use */
return next_page / PAGE_SIZE; /* return the allocated page # */
}
/*
* free - free a previously allocated block.
*/
void free(cp)
char *cp;
{
used_block *current, *q;
free_block *p, *below;
#ifdef DBG
fprintf(stderr,"free(%06o) called from %06o\n",cp,(*(int*)*(int*)017)-1);
#endif
if (cp == NULL) /* Allow no-op if given null arg */
return; /* as per ANSI description. */
current = (used_block *) (cp -= OVERHEAD); /* make struct ptr to block */
#if MALLOC_CHECK
if (current->flag != IN_USE) {
fprintf(stderr, "free(): tried to free invalid block (%o,,%o)\n",
((unsigned) current) >> 18, ((unsigned) current) & 0777777);
fflush(stderr);
abort();
}
if (MAGIC_WORD(current,current->size) != MAGIC_CHECKWORD) {
fprintf(stderr,
"free(): block at (%o,,%o) overwitten past end\n",
((unsigned) current) >> 18, ((unsigned) current) & 0777777);
fflush(stderr);
abort();
}
#endif
below = (free_block *) (cp + current->size);
if (below->flag != FREE) below = NULL; /* but only if it's free! */
/*
* check to see if next and/or previous ("physical") blocks in memory
* are free also, so we can do merge.
*/
if (current->above) { /* merge with block above */
if (!below)
current->above->size += current->size;
else { /* merge w/above AND below */
current->above->size += (current->size + below->size);
if (!below->previous) free_head = below->next;
else below->previous->next = below->next;
if (below->next) below->next->previous = below->previous;
}
current = (used_block *) current->above; /* new current block */
} else {
current->flag = FREE;
p = (free_block *) current; /* this block is free now */
if (below) { /* merge with below only */
p->size += below->size;
if (!below->previous) free_head = p;
else below->previous->next = p;
p->previous = below->previous;
if (p->next = below->next) below->next->previous = p;
} else { /* no merge possible */
p->previous = NULL;
if (p->next = free_head) p->next->previous = p;
free_head = p;
}
}
q = (used_block *) ((char *) current + current->size);
if (q->flag == IN_USE) q->above = (free_block *) current;
}
void cfree(cp) /* cfree() and free() are interchangable */
char *cp;
{
free(cp);
}
void _pfree(page)
int page;
{
free((char *) (int *) (page * PAGE_SIZE)); /* turn page # into word. */
}
/*
* change the size of an existing block. reducing the size pares
* a chunk of storage off the end and frees it; increasing the
* size gets you a new block with the old data copied over.
* Note behavior follows ANSI description when given a NULL pointer
* or a zero size:
* If ptr == NULL, acts like malloc.
* Else if size == 0, acts like free and returns NULL.
*/
char *
relalloc(ptr, size)
char *ptr;
unsigned long size;
{
char *realloc();
return realloc(ptr, (size_t) size);
}
char *
realloc(ptr, size)
char *ptr;
size_t size;
{
char *new;
used_block *old;
blksiz_t need = size;
if (ptr == NULL) /* Per ANSI description, if ptr NULL */
return malloc(size); /* then just act like malloc() */
if (need <= 0) { /* Also per ANSI description, if size 0 */
free(ptr); /* then free up the old block */
return NULL; /* and return NULL */
}
old = (used_block *) (ptr - OVERHEAD);
#if MALLOC_CHECK
if (old->flag != IN_USE) {
fprintf(stderr, "realloc(): tried to reallocate invalid block (%o,,%o)\n",
((unsigned) old) >> 18, ((unsigned) old) & 0777777);
fflush(stderr);
abort();
}
#endif
need = ROUNDUP(need) + OVERHEAD + sizeof(MAGIC_CHECKWORD);
if (old->size == need) /* is it worth checking for this? */
return ptr;
else if (old->size > need) { /* if reducing, free the tail */
#if 0
split(old, need);
#else
split(old, size);
#endif
return ptr;
} else { /* bigger, so reallocate and copy */
new = malloc(size); /* allocate a bigger block */
if (new) {
icopy((int *) ptr, (int *) new,
ROUND_D(old->size - OVERHEAD, sizeof(int)));
free(ptr); /* now free the old block */
}
return new; /* return updated char pointer */
}
}
/*
* primitives to zero and copy sequential ints
* These both assume they will never see a count <= 0, since
* malloc never deals with zero-length blocks.
*/
static void icopy(from, to, count)
int *from, *to, count;
{
#if !(CPU_PDP10)
while (count-- > 0)
*to++ = *from++;
#else
#asm
JUMPG 17,xicopy
MOVE 1,-2(17) ;to NON-EXTENDED
HRL 1,-1(17) ;from,,to
MOVE 2,-3(17) ;count
ADDI 2,(1) ;to+count
BLT 1,-1(2) ;do it.
POPJ 17,
xicopy: MOVE 1,-3(17) ;count EXTENDED
MOVE 2,-1(17) ;from
MOVE 3,-2(17) ;to
EXTEND 1,[XBLT] ;do it.
POPJ 17,
#endasm
#endif
}
static void izero(to, count)
int *to, count;
{
#if !(CPU_PDP10)
while (count-- > 0)
*to++ = 0;
#else
#asm
JUMPG 17,xizero
AOS 1,-1(17) ;to+1 NON-EXTENDED
HRLI 1,-1(1) ;to,,to+1
SETZM -1(1) ;zero 1st wd
SOSG 2,-2(17) ;count-1
POPJ 17, ;only 1 word
ADDI 2,(1) ;<count-1>+<to+1> = <to+count>
BLT 1,-1(2) ;do it
POPJ 17,
xizero: MOVE 2,-1(17) ;to EXTENDED
SETZM (2) ;zero (to)
MOVE 3,2 ;to
ADDI 3,1 ;to+1
SOSLE 1,-2(17) ;count-1
EXTEND 1,[XBLT] ;do it if something left.
#endasm
#endif
}
/*
* debugging stuff
*/
void _free_list(f)
FILE *f;
{
free_block *p;
if (!free_head) fputs(" ---- freelist is empty ----\n", f);
else {
fputs(" ---- free-list ----\n", f);
p = free_head;
while (p) {
fprintf(f, " %o: %d.\n", p, p->size);
p = p->next;
}
}
}
void _memory_map(f)
FILE *f;
{
free_block *p;
used_block *q;
int *z;
z = (int *) top_block;
fprintf(f, "Top block = %o\nFree head = %o\n", z, free_head);
if (*z) fputs("-- Memory map of malloc area --\n", f);
while (*z) { /* if zero, assume EOM */
fprintf("%6o: ", z);
p = (free_block *) z;
switch (p->flag) {
case IN_USE:
q = (used_block *) p;
fprintf(f, "IN_USE\tsize = %o\tabove = %o\n",
q->size, q->above);
z += (q->size / sizeof(int));
break;
case FREE:
fprintf(f, "FREE\tsize = %o\tprev = %o\tnext = %o\n",
p->size, p->previous, p->next);
z += (p->size / sizeof(int));
break;
default:
fprintf(f, "Bad header value, not FREE or IN_USE: %o\n",
p->flag);
z = 0;
break;
}
}
}
-------
5-May-88 15:00:31-PDT,12319;000000000001
Return-Path: <[email protected]>
Received: from SCIENCE.UTAH.EDU by SRI-NIC.ARPA with TCP; Thu, 5 May 88 15:00:18 PDT
Date: Thu 5 May 88 16:00:20-MDT
From: "Nelson H.F. Beebe" <[email protected]>
Subject: mtest.c
To: [email protected]
cc: [email protected]
X-US-Mail: "Center for Scientific Computing, South Physics, University of Utah, Salt Lake City, UT 84112"
X-Telephone: (801) 581-5254
Message-ID: <[email protected]>
#include <stdio.h>
#ifndef DBG
#define DBG 0 /* non-zero value gives malloc/realloc/free traces */
#endif
#ifdef __COMPILER_KCC__
#define random rand
#define srandom srand
#define tops20 1
#endif
#if tops20
#define extern
#define add_to_events addvnt
#define cause_core_dump cordmp
#define do_stats dostat
#define dump_events dmpvnt
#define free_event frevnt
#define init_events inivnt
#define random_range ranrng
#define realloc_event reavnt
#define realloc_probability reaprb
#define run_test runtst
#endif
extern int atoi ();
extern long random ();
extern char *sbrk ();
extern char *malloc ();
extern char *realloc ();
extern int free ();
struct memevent {
int m_time; /* time to go */
char *m_memory; /* malloc'ed mem */
unsigned m_size; /* size of mem */
int m_id; /* id, for trace/debug */
int m_realloc; /* counter, for debugging */
char m_pattern; /* pattern in memory */
struct memevent *m_next; /* linked list pointer */
};
#ifndef MAX_EVENTS
#define MAX_EVENTS 10000
#endif
struct memevent eventpool[ MAX_EVENTS ];
struct memevent *events;
struct memevent *free_events;
char stdout_buf[ BUFSIZ ];
char stderr_buf[ BUFSIZ ];
int time_to_go;
int new_probability;
int realloc_probability = 25; /* XXX: should set from argv */
int stat_frequency;
main (argc, argv)
int argc;
char *argv[];
{
init (argc, argv);
run_test ();
}
/*
* run_test ()
*
* Run the actual memory test.
*/
run_test ()
{
while (time_to_go > 0) {
arrival ();
service ();
-- time_to_go;
if ((time_to_go % stat_frequency) == 0)
do_stats ();
}
}
/*
* arrival ()
*
* With probability new_probability/100, allocate a new piece
* of memory with some randomly determined size and lifetime,
* and add it to the memory event list.
*/
arrival ()
{
if (free_events && odds (new_probability, 100)) {
register struct memevent *m;
register char *p;
m = free_events;
free_events = m->m_next;
m->m_next = NULL;
/* XXX: let these be set from argv */
m->m_size = (unsigned) random_range (1, 100);
if (time_to_go < 100)
m->m_time = random_range (1, time_to_go);
else
m->m_time = random_range (1, 100);
m->m_pattern = (char) random_range (0, 127);
m->m_realloc = 0;
m->m_memory = malloc (m->m_size);
#if DBG
fprintf(stderr,"%06o <- malloc(%d) : %012o\n",
(int*)m->m_memory,m->m_size,
*((int*)(m->m_memory+m->m_size)));
fflush(stderr);
#endif
if (! m->m_memory)
out_of_memory ();
for (p = m->m_memory; p < & m->m_memory[ m->m_size ]; p++)
*p = m->m_pattern;
add_to_events (m);
}
} /* arrival */
/*
* do_stats ()
*/
do_stats ()
{
register struct memevent *m;
int i;
long total;
printf ("---------------------\nTIME Remaining: %d\n", time_to_go);
/* print other interesting but implementation-dependent stuff here
(like count of blocks in heap, size of heap, etc) */
total = 0;
for (i = 1, m = events; m != NULL; m = m->m_next, i++) {
printf ("EVENT %5d (id %5d): ", i, m->m_id);
printf ("SIZE %4d, ", m->m_size);
printf ("PATTERN 0x%02x, ", m->m_pattern & 0xFF);
printf ("TIME %4d ", m->m_time);
if (m->m_realloc > 0)
printf ("REALLOC %d", m->m_realloc);
printf ("\n");
total += m->m_size;
}
printf ("TOTAL events %d, allocated memory %d\n", i-1, total);
(void) fflush (stdout);
} /* do_stats */
/*
* service ()
*
* Decrement the time remaining on the head event. If
* it's time is up (zero), service it.
*
* Servicing an event generally means free'ing it (after checking
* for corruption). It is also possible (realloc_probability) to
* realloc the event instead.
*/
service ()
{
register struct memevent *m;
if ((m = events) != NULL)
-- m->m_time;
while (m != NULL && m->m_time == 0) {
register char *p;
for (p = m->m_memory; p < & m->m_memory[ m->m_size ]; p++) {
if (*p != m->m_pattern)
corrupted ();
}
events = m->m_next; /* delete this event */
if (time_to_go > 1 && odds (realloc_probability, 100))
realloc_event (m);
else
free_event (m);
m = events;
}
} /* service */
/*
* free_event (m)
*
* Called to free up the given event, including its memory.
*/
free_event (m)
register struct memevent *m;
{
free ((char*)m->m_memory);
m->m_next = free_events;
free_events = m;
}
/*
* realloc_event (m)
*
* Called from service(), to reallocate an event's memory,
* rather than freeing it.
*/
realloc_event (m)
register struct memevent *m;
{
register char *p;
unsigned new_size;
unsigned min_size;
/* XXX: let these be set from argv */
new_size = (unsigned) random_range (1, 100);
++ m->m_realloc; /* for stats */
p = m->m_memory;
m->m_memory = realloc (m->m_memory, new_size);
#if DBG
fprintf(stderr,"%06o <- realloc(%06o,%d) : %012o\n",
(int*)m->m_memory,p,new_size,
*((int*)(m->m_memory+m->m_size)));
fflush(stderr);
#endif
if (! m->m_memory)
out_of_memory ();
m->m_next = NULL;
if (time_to_go < 100)
m->m_time = random_range (1, time_to_go - 1);
else
m->m_time = random_range (1, 100); /* XXX: should set from argv */
min_size = new_size > m->m_size ? m->m_size : new_size;
for (p = m->m_memory; p < & m->m_memory[ min_size ]; p++) {
if (*p != m->m_pattern)
corrupted ();
}
m->m_size = new_size;
for (p = m->m_memory; p < & m->m_memory[ m->m_size ]; p++)
*p = m->m_pattern;
add_to_events (m);
} /* realloc_event */
/*
* add_to_events (m)
*
* Add the given event structure onto the time-ordered event list.
*/
add_to_events (m)
register struct memevent *m;
{
register struct memevent *l;
register struct memevent *ol;
for (ol = NULL, l = events; l != NULL; ol = l, l = l->m_next) {
if (l->m_time > m->m_time) {
if (ol == NULL) {
m->m_next = events;
events = m;
}
else {
m->m_next = l;
ol->m_next = m;
}
l->m_time -= m->m_time;
return;
}
m->m_time -= l->m_time;
}
if (events == NULL)
events = m;
else
ol->m_next = m;
} /* add_to_events */
/*
* init_events ()
*
* Set up the memevent pools.
*/
init_events ()
{
register struct memevent *m;
int i;
for (i = 0, m = eventpool; m < & eventpool[ MAX_EVENTS ]; m++, i++) {
m->m_id = i;
m->m_next = m + 1;
}
eventpool[ MAX_EVENTS-1 ].m_next = NULL;
free_events = eventpool;
}
/*
* init (argc, argv)
*
* Initialize the memory tests.
*/
init (argc, argv)
int argc;
char *argv[];
{
if (argc != 4) {
fprintf (stderr, "usage: %s new_prob time_to_go stat_freq\n", argv[ 0 ]);
exit (1);
}
new_probability = atoi (argv[ 1 ]);
time_to_go = atoi (argv[ 2 ]);
stat_frequency = atoi (argv[ 3 ]);
srandom (1);
init_events ();
/*
* Use statically allocated buffers, otherwise
* stdio() will call malloc to allocate buffers, and
* this gets confusing when debugging stuff.
*/
setbuf (stdout, stdout_buf);
setbuf (stderr, stderr_buf);
}
/*
* XXX: Should really send SIGQUIT ...
*/
cause_core_dump ()
{
* (long *) 1 = 5;
}
corrupted ()
{
printf ("Corrupted\n");
cause_core_dump ();
}
out_of_memory ()
{
printf ("Out of memory!\n");
cause_core_dump ();
}
/*
* odds (m, n)
*
* Return TRUE (non-zero) with probability m out of n.
*/
odds (m, n)
int m;
int n;
{
return ((random () % n) < m);
}
/*
* random_range (lo, hi)
*
* Pick a random integer from lo to hi (inclusive).
*/
random_range (lo, hi)
int lo;
int hi;
{
return ((random () % (hi - lo + 1)) + lo);
}
#if DBG
/*
* de_cmpf (m1,m2)
*
* compare function for qsort() in dump_events.
* Sort by memory address of the memory allocated to
* the event.
*/
int
de_cmpf (m1, m2)
struct memevent **m1;
struct memevent **m2;
{
unsigned long maddr1 = (unsigned long) (*m1)->m_memory;
unsigned long maddr2 = (unsigned long) (*m2)->m_memory;
/* sloppy */
return (maddr1 - maddr2);
}
#endif DBG
/*
* dump_events ()
*
* Useful for debugging.
*/
#if DBG
dump_events ()
{
static struct memevent *sorted[ MAX_EVENTS ];
register struct memevent *m;
register int i;
fprintf (stderr, "DUMP EVENTS (time remaining = %d)\n", time_to_go);
for (m = events, i = 0; m != NULL; m = m->m_next, i++)
sorted[ i ] = m;
if (i == 0) {
fprintf (stderr, "No events.\n");
return;
}
qsort ((char *) sorted, i, sizeof (struct memevent *), de_cmpf);
sorted[ i ] = 0;
for (i = 0, m = sorted[ 0 ]; m != NULL; m = sorted[ ++i ]) {
fprintf (stderr, "E# %3d: ", m->m_id);
fprintf (stderr, "SIZ%4d, ", m->m_size);
fprintf (stderr, "RANGE: 0x%08x -- 0x%08x ",
m->m_memory, m->m_memory + m->m_size - 1);
(void) fflush (stderr);
/* Peek at the surrounding longs,
for debugging a particular malloc
implementation. Your choices may
vary. */
fprintf (stderr, "BOUNDARY TAGS: %4d ", * (long *) (m->m_memory - 4));
(void) fflush (stderr);
fprintf (stderr, "%4d\n", * (long *) ((m->m_memory - 8) - (* (long *) (m->m_memory - 4))));
(void) fflush (stderr);
}
fprintf (stderr, "END DUMP_EVENTS\n");
(void) fflush (stderr);
} /* dump_events */
#endif DBG
-------