From: meissner@osf.org (Michael Meissner)
Subject: Re: Duplication of malloc() definition
Organization: Open Software Foundation
Date: 21 Jul 92 11:38:57

In article <1992Jul18.002407.20753@druid.uucp> darcy@druid.uucp (D'Arcy J.M. Cain) writes:

| jmp@moscom.UUCP (Joe Palumbos) writes:
| >Can someone tell me why the memmory allocation routines are
| >defined in both malloc.h and in stdlib.h?  (i.e.: malloc(),
| 
| Because some older compilers used malloc.h and so for compatibility with
| programs which use it malloc.h is included.  ANSI puts these functions
| in stdlib.h and this is the right header to use.

Actually, it is not the compiler per se, but the operating system.
Specifically, the early System V.x strain have two malloc's, one in
libc.a, and the other in libmalloc.a (I dunno about V.4).  I can't
remember exactly which System V.x release released libmalloc.a, but I
have V.2 on-line, and it has it.  The header file malloc.h defines the
interface to the routines in libmalloc.a, and adds a structure
mallinfo, a function mallinfo (which returns a pointer to the mallinfo
structure), and a function mallopt (which allows you to control the
malloc algortihms).

The libc.a malloc was the original V7 malloc, and the libmalloc.a
malloc was generally much faster than the V7 malloc, but used a little
more memory by default.  It also did not preserve the V7 semantics
that the data in freed blocks was untouched until the block was
reallocated (awk and bc being the biggest two offenders if I remember
correctly).

Here is the initial comment from the V.2 libmalloc malloc.c:

/*     use level memory allocater (malloc, free, realloc)

	-malloc, free, realloc and mallopt form a memory allocator
	similar to malloc, free, and realloc.  The routines
	here are much faster than the original, with slightly worse
	space usage (a few percent difference on most input).  They
	do not have the property that data in freed blocks is left
	untouched until the space is reallocated.

	-Memory is kept in the "arena", a singly linked list of blocks.
	These blocks are of 3 types.
		1. A free block.  This is a block not in use by the
		   user.  It has a 3 word header. (See description
		   of the free queue.)
		2. An allocated block.  This is a block the user has
		   requested.  It has only a 1 word header, pointing
		   to the next block of any sort.
		3. A permanently allocated block.  This covers space
		   aquired by the user directly through sbrk().  It
		   has a 1 word header, as does 2.
	Blocks of type 1 have the lower bit of the pointer to the
	nextblock = 0.  Blocks of type 2 and 3 have that bit set,
	to mark them busy.

	-Unallocated blocks are kept on an unsorted doubly linked
	free list.  

	-Memory is allocated in blocks, with sizes specified by the
	user.  A circular first-fit startegy is used, with a roving
	head of the free queue, which prevents bunching of small
	blocks at the head of the queue.

	-Compaction is performed at free time of any blocks immediately
	following the freed block.  The freed block will be combined
	with a preceding block during the search phase of malloc.
	Since a freed block is added at the front of the free queue,
	which is moved to the end of the queue if considered and
	rejected during the search, fragmentation only occurs if
	a block with a contiguious preceding block that is free is
	freed and reallocated on the next call to malloc.  The
	time savings of this strategy is judged to be worth the
	occasional waste of memory.

	-Small blocks (of size < MAXSIZE)  are not allocated directly.
	A large "holding" block is allocated via a recursive call to
	malloc.  This block contains a header and ?????? small blocks.
	Holding blocks for a given size of small block (rounded to the
	nearest ALIGNSZ bytes) are kept on a queue with the property that any
	holding block with an unused small block is in front of any without.
	A list of free blocks is kept within the holding block.
*/

--
Michael Meissner	email: meissner@osf.org		phone: 617-621-8861
Open Software Foundation, 11 Cambridge Center, Cambridge, MA, 02142

You are in a twisty little passage of standards, all conflicting.
Newsgroups: comp.unix.programmer