reeder@cs.utexas.edu (William P. Reeder) (01/31/89)
Fellow Spotters, I need your help.
A friend of mine has been developing a program which is a kind of
architectural CAD package. Not being an architect, I'm not sure what one
might do with it, but it produces some pretty pictures in the process.
This program is having problems with malloc.
To start with, we are dealing with Sun 3's of various flavors, all with
color tubes. They are running SunOS 3.4, using SunView, and SunCore. The
programming is in C.
Malloc!! Boy, what a mess. Muses (the package mentioned above) maintains
a large number of linked lists, malloc'ing and free'ing space for nodes as
needed. There is a LOT of malloc'ing and free'ing going on, and nodes
come in only a few sizes. This last point is important. Imagine the
following code fragment:
node1 = malloc(N);
node2 = malloc(N);
free(node1);
node3 = malloc(N);
Node3 does not get the memory which node1 released. Instead, malloc asks
the system for additional memory to satisfy the malloc. This is BUSTED!
Muses does a *****LOT***** of this, and grows and grows and grows in
memory, even though it may not need to. Eventually, muses crashes, with
the program counter usually pointing into malloc.
I fetched the malloc replacement written by Bill Sebok at Princeton
University and plugged that in, but it didn't help tremendously because
something in SunCore and/or SunView seems to be calling variants of malloc
(calloc is one that comes to mind) and those suck up memory and crash.
Does anyone have a solution? Upgrading to SunOS 4.0[.1] is not helpful
because the malloc problem still exists there. In fact, here is a nice
little program which shows it. (I sent in a bug report to sunbugs a day
or two ago, but haven't heard anything back. Besides, I think we only
have update service, so they probably threw it into the trash.)
__________cut here for program
/*
* NAME
* mtest - test memory allocation.
*
* COMPILATION
* cc -o mtest mtest.c
*
* SYNOPSIS
* mtest
*
* DESCRIPTION
* mtest demonstrates that malloc is broken. Specifically, that
* malloc is not smart enough to use a piece of memory of exactly
* the right size when it is available (unless it is at the end
* of memory).
*/
#include <stdio.h>
#include <sys/errno.h>
#include <sys/types.h>
#define BIGBUF 1000000 /* 1 MBytes */
#define SMALLBUF 10240 /* 10 KBytes */
char *malloc();
caddr_t sbrk();
extern int errno;
main()
{
char *buf1, *buf2; /* buffer pointers */
caddr_t topmem; /* upper limit of memory */
printf("beginning memory allocation test\n");
printf("All values are reported in decimal.\n");
topmem = sbrk(0);
printf("The end of memory is initially at %d\n\n",(int) topmem);
/*
* Demonstrate that you can (sometimes) re-use memory which has
* been malloc'ed and subsequently free'd.
*/
buf1 = malloc(BIGBUF);
if (buf1 == 0) {
perror("test");
errno = 0;
exit(1);
}
else {
printf("requested %d bytes of memory\n", BIGBUF);
topmem = sbrk(0);
printf("The end of memory is now at %d\n", (int) topmem);
}
if (free(buf1) == 0) {
perror("test");
errno = 0;
exit(2);
}
else {
printf("%d bytes of memory freed\n", BIGBUF);
printf("There is now a %d byte piece of memory available.\n", BIGBUF);
topmem = sbrk(0);
printf("The end of memory is still at %d\n", (int) topmem);
}
buf1 = malloc(BIGBUF);
if (buf1 == 0) {
perror("test");
errno = 0;
exit(1);
}
else {
printf("requested another %d bytes of memory -- ", BIGBUF);
printf("Should use available space.\n");
topmem = sbrk(0);
printf("The end of memory is still at %d\n\n", (int) topmem);
}
/*
* Now demonstrate that if a block of free memory is surrounded
* by other chunks of memory, then a memory request of that size
* will NOT use the available piece.
*/
buf2 = malloc(SMALLBUF);
if (buf2 == 0) {
perror("test");
errno = 0;
exit(1);
}
else {
printf("Requested %d bytes of memory.\n", SMALLBUF);
topmem = sbrk(0);
printf("The end of memory is now at %d\n", (int) topmem);
}
if (free(buf1) == 0) {
perror("test");
errno = 0;
exit(2);
}
else {
printf("Freed %d bytes of memory.\n", BIGBUF);
printf("There is now a %d byte piece of memory available.\n", BIGBUF);
topmem = sbrk(0);
printf("The end of memory is still at %d\n", (int) topmem);
}
buf1 = malloc(BIGBUF);
if (buf1 == 0) {
perror("test");
errno = 0;
exit(1);
}
else {
printf("Requested another %d bytes of memory -- ", BIGBUF);
printf("Should use available space.\n");
topmem = sbrk(0);
printf("WHOA! The end of memory is now at %d\n",(int) topmem);
}
exit(0);
}
__________cut here for program
Please email responses to me, it will be quicker than posting to
sun-spots. I'll post a summary if anyone requests it. In the mean time,
how can Sun, or any vendor, allow malloc and co. to be so busted? It
boggles my mind.
William Reeder, University of Texas, Computation Center
ARPA: reeder@emx.utexas.edu UUCP: ..!uunet!cs.utexas.edu!ut-emx!reeder
BITNET: CCCD001 @ UTA3081chris@uunet.uu.net (Chris Brown) (02/16/89)
In v7n127 W.P. Reeder describes a problem concerning repeated use of malloc and free. Since the nodes he is allocating "come in only a few sizes", a solution would be to maintain one's own linked list of free nodes. There would be one such list for each size of node. Often there is a pointer field already within the node's struct which can be pressed into service as the 'next' pointer in the linked list. If not, you'll have to use a cast or a union to get one. Then, instead of calling malloc(), you pop a node off the list. Of course, if the list is empty, you have to call the real malloc() to get a new node. This happens lots of times whilst the memory usage is developing, then tails off. Instead of a call to free(), you push the node back onto the appropriate linked list. free() is never called. Even if you didn't have a problem with malloc() to work around, you'll find this technique much more efficient if you are frequently creating and destroying nodes in a small range of sizes.