malloc(3) vs. malloc(3x)

[Tony Parkhurst_TEMP]

In article <1418 at leah.Albany.Edu> rds95 at leah.Albany.Edu (Robert Seals) writes:

>How much can a single malloc get? 

As much as a bunch of small mallocs added together?

No, actually, a single malloc can get as much memory as a process can get
less malloc's overhead.  Malloc is just a library routine that uses
sbrk() to get memory for the process.  (Note that sbrk() is NOT in the SVID
but is in AT&T System V implementation).

>And why does Ultrix have 2 kinds of
>malloc, while 4.3-tahoe (the first one, I think) only has 1?

Because Ultrix is using the SVID for malloc(), while 4.3-tahoe is bazerkley(BSD)

So, the question could be, why does SVID have two definitions for malloc()?

Because the default one is for compatibility, and the other (newer) one is
for enhanced control.

First off, some background....

   Kernighan & Ritchie in "The C Programming Language" present a simple version
of a malloc() and free() that does the memory compaction (or coalescing)
during the free() routine.  These are a modified first fit algorithm that was
probably taken from Knuth Vol ??.  One problem with these routines is that
a realloc() would not be too trivial.  At some point someone wrote the 
routines where the compaction of free blocks was done during malloc() instead 
of free(), along with some other enhancements.  This made for an easier 
implementation of realloc(), and provided some interesting features.  So, at 
least by Version 6 UNIX, there were some interesting points in the manual 
pages for these routines:

1)  "...after 'free' is performed this space is made available for further
    allocation, but its contents are left undisturbed."

    Note:  I would not write programs that expect this feature, would you?

2)  "'Malloc' allocates the first big enough contiguous reach of free space
    found in a circular search from the last block allocated or freed,
    coalescing adjacent free blocks as it searches."

    Note:  the "last block allocated" pointer is also the "last block freed"
    pointer.  So either a malloc or a free will change this pointer.

and
3)  "'Realloc' also works if [the pointer argument] points to a block freed
    since the last call of 'malloc', 'realloc', or 'calloc'; thus sequences
    of 'free', 'malloc' and 'realloc' can exploit the search strategy of
    'malloc' to do storage compaction."

    Note that this does not really make logical sense:  That is, "a block
    freed since the last call of 'malloc'", then "sequences of 'free',
    'malloc' and 'realloc'" are not compatable statements.

It is not clear that a program should have the ability to continue to
use memory after it is freed.  Also, it is not clear why one would need to
do routine storage compaction as in point 3, because the compaction will occur
whenever you need more memory.  But, this notwithstanding, these points led to
a very questionable coding practice, and you will still see code like this:

...

	free(myblock);		/* free memory to be realloced (pt 1) */

	free(dummy);		/* small block used only for the purpose of
				   moving the "last block" pointer in the
				   malloc routines away from "myblock" 
				   which forces a search in realloc (pt 2) */
	
	dummy = malloc(1);	/* go ahead and get the dummy back, will be
				   the same block as just freed, see point 2 */
	
	myblock = realloc(myblock, newsize);

				/* Now, get a new (or same) block after the
				   malloc routine makes a search for a large
				   enough block which will cause coalescing
				   during the search.  The returned block
				   may be right after "dummy" in the free
				   block list, so the "amount" of coalescing
				   may be minimal anyway.  (pts 2 and 3) */

...


If you don't believe me, look in the source for utilities like 'dc'
and 'diff'.  (Of course you won't see worthwhile comments).  Both of these
programs will break if the malloc routines do NOT allow the above practice.

Now, this coding practice, and those sections of the manual pages

(Point 1 about preserving freed blocks,
 point 2, which actually makes a statement about the implementation of malloc, 
 and point 3 which suggests a method for taking advantage of a particular
 implementation of memory management)

is terribly non-portible, and writing malloc routines to comply with both
that manual page and those code fragments is a pain.  What happened
to the "UNIX philosophy" here?!

So, to implement new versions of malloc(), BSD has one that someone put
much effort into preserving the compatibility and has a higher performance
(relative since this is in user context anyway), and is more efficient with
usage of smaller blocks.  It is bucket pool type of implementation.

System V on the other hand, has a nice elaborate scheme with lots of 
control and statistics collecting code, but since it is not compatible,
and is big, it is relegated to a separate library instead of the default libc.



>Eh? I thought that there must be some resource limit defined by the system,
>and in Ultrix (1.2 and 2.2), there is a "ulimit" call, but 4.3-tahoe
>only has "getrlimit", so I wrote a little smidge to find out what my
>"RLIMIT_DATA" and "RLIMIT_RSS" were. They were way bigger than the
>amount I got from malloc. Are they the right thing to check?

Did you account for malloc's overhead which is in user space along with
the requested memory.  RLIMIT_DATA should at least have been close.  Of
course this will also include all the static variable space.

>So I thought mebbe a physical memory limit? Nah, why would I (consistently)
>get 2 different values depending on the library version I used?

They are different implementations with much different constraints and overhead.

>AND, why did the 3x version (the one used when -lmalloc is included)
>have such extravagant core(?) requirements - 780k vs. 19k for libc?

Because it is came from AT&T which has complexity on the brain.

>AND, why isn't there a (old-style) prototype for malloc anywhere in
>/usr/include, even though it doesn't return an int? Isn't that the
>way it's supposed to go? Like /usr/include/malloc.h...char *malloc();...

Usually a header file is provided if there are implementation defined constants:

#define	M_MXFAST...
#define	M_NLBLKS...
#define M_GRAIN...

or structures involved:

struct mallinfo...

which are needed for the 3x version of malloc(), but the libc version of malloc
doesn't have any.

>Remember, this is the NEOPHYTES group, so keep the fires low.

These are good questions that you asked.  Just remember when you are trying
to figure these things out that routines in section 3 of the manual are
library routines, not system calls, so system limits and constraints do
not corelate directly with these routines.

Hope this helps.

-- Tony

P.S.  Someone with more knowledge of malloc's history may want to fill in gaps.

-- 

Tony Parkhurst	( tony at hp-sdd.HP.COM )