We have 2 sets of machines used for large memory intensive processing
jobs.  Alphas running Digital Unix 4.0B and PentiumPro 200 running
NetBSD 1.2.1.

All have 128Mbyte of phyiscal memory and 512Mbytes of swap.

We have noticed that several programs that run OK on the Digital Unix but
fail due to lack of memory on NetBSD.

One of our researchers has noticed that the malloc routine on NetBSD
appears have a large memory overhead. It is not yet clear if
this is the cause of our problem but wondered if anyone could shed any
light on the algorithm used by the malloc routine in this regard.

I have appended his test program and comments.

Many Thanks

Tim.


>From ponting  Tue Aug 19 11:08:43 1997
From: "Keith M. Ponting" <ponting>
        by byron.dra.hmg.gb (8.8.5/) with ESMTP id LAA11234;
        Tue, 19 Aug 1997 11:08:41 +0100 (BST)
Date: Tue, 19 Aug 1997 11:08:41 +0100 (BST)
Message-Id: <LAA13461@thomas.dra.hmg.gb>
To: janes
Subject: memory holes on titan/NetBSD
Status: RO


Tim, 

The magic number for 100000 bytes requested seems to be 135168 =
0x21000. I would be interested in response from the newsgroup.

Sundry other tests show the algorithm to be something like:
  up to 2044 bytes requested, use next highest power of 2
  more than 2044 bytes requested next highest ((power of 2+1)* 0x1000)
Thus the allocation chains appear to be associated with chunks of
sizes: 8 16 32 64 128 256 512 1024 2048 then a step to
       0x2000=8192 0x3000=12288 0x5000=20480 etc.

I am not quite sure I see the logic!

Keith

/***--------------------------------------------------------------------------
 * TITLE:  memory.c
 * IDENT:  $Id: memory.c,v 1.1 1997/08/19 09:51:27 ponting Exp $
 * AUTHOR: Dr.K.M.Ponting  Defence Research Agency, Malvern
 * ENVIR:  ANSI 'C'
 * USAGE:  main program
 * TASKS:  test memory allocator
 *  (C)    Crown Copyright $Date: 1997/08/19 09:51:27 $
 * DATES: <rcs change log automatically inserted here>
 * $Log: memory.c,v $
 * Revision 1.1  1997/08/19 09:51:27  ponting
 * Initial revision
 *
--------------------------------------------------------------------------***/

/********************************
* include files                	*
********************************/

#include <stdio.h>		/* needed for printf function call */
#include <stdlib.h>		/* needed for EXIT_SUCCESS */

/********************************
* local constant declarations  	*
********************************/


/********************************
* local structure declarations  *
********************************/


/********************************
* local function prototypes     *
********************************/


/********************************
* local macro definitions       *
********************************/

/* gcc -Wall memory.c -lc -o memory */

/************************************************************************
* main program								*
************************************************************************/
int main(int argc,char **argv)
{
  if ( argc < 2 ) 
    {
      printf("usage: %s memory_chunk_size [count=5]\n",argv[0]) ;
    }
  else
    {
      size_t chunk_size = strtoul(argv[1],NULL,0) ;
      int count = 5 ;
      int k ;
      char * old = NULL ;
      if ( argc > 2 )
	{
	  count = strtol(argv[2],NULL,0) ;
	}
      for ( k = 0 ; k < count ; ++k )
	{
	  char * base = (char*)malloc(chunk_size) ;
	  if ( k > 0 )		/* meaningless on first allocation */
	    {
	      printf("size %lu base %p change 0x%lx=%ld overhead %ld\n",
		     (unsigned long)chunk_size,
		     base, (long)(base-old), (long)(base-old), 
		     (long)(base-old)-chunk_size) ;
	    }
	  old = base ;
	}
    }
  return(EXIT_SUCCESS);
}

/*-----------------------------------------------------------------------
Output:

1) Compiled on NetBSD. I can believe the extra overhead 0x5000
on one of the prints is due to memory grabbed by the printf statement.
BUT why am I losing huge amounts of overhead space on the bigger 
allocations -- the worst case is allocating 135168 bytes which 
leaves a memory gap of 131072 bytes? 

gcc -Wall memory.c -lc -o memory

titan8:~/astrec/tests% memory 100
size 100 base 0x3080 change 0x80=128 overhead 28
size 100 base 0x3100 change 0x80=128 overhead 28
size 100 base 0x3180 change 0x80=128 overhead 28
size 100 base 0x3200 change 0x80=128 overhead 28
titan8:~/astrec/tests% memory 1000
size 1000 base 0x3400 change 0x400=1024 overhead 24
size 1000 base 0x3800 change 0x400=1024 overhead 24
size 1000 base 0x3c00 change 0x400=1024 overhead 24
size 1000 base 0x9000 change 0x5400=21504 overhead 20504
titan8:~/astrec/tests% memory 10000
size 10000 base 0x6000 change 0x3000=12288 overhead 2288
size 10000 base 0xe000 change 0x8000=32768 overhead 22768
size 10000 base 0x11000 change 0x3000=12288 overhead 2288
size 10000 base 0x14000 change 0x3000=12288 overhead 2288
titan8:~/astrec/tests% memory 100000
size 100000 base 0x24000 change 0x21000=135168 overhead 35168
size 100000 base 0x4a000 change 0x26000=155648 overhead 55648
size 100000 base 0x6b000 change 0x21000=135168 overhead 35168
size 100000 base 0x8c000 change 0x21000=135168 overhead 35168
titan8:~/astrec/tests% memory 135164
size 135164 base 0x24000 change 0x21000=135168 overhead 4
size 135164 base 0x4a000 change 0x26000=155648 overhead 20484
size 135164 base 0x6b000 change 0x21000=135168 overhead 4
size 135164 base 0x8c000 change 0x21000=135168 overhead 4
titan8:~/astrec/tests% memory 135168
size 135168 base 0x44000 change 0x41000=266240 overhead 131072
size 135168 base 0x8a000 change 0x46000=286720 overhead 151552
size 135168 base 0xcb000 change 0x41000=266240 overhead 131072
size 135168 base 0x10c000 change 0x41000=266240 overhead 131072

2) Compiled on alpha/osf1 -- the overhead ranges between 8 and
36 bytes, which seems much more sensible.

gcc -Wall memory.c -lc -o memory

thomas:astrec/tests% memory 100
size 100 base 140000980 change 0x80=128 overhead 28
size 100 base 140000a00 change 0x80=128 overhead 28
size 100 base 140000a80 change 0x80=128 overhead 28
size 100 base 140000b00 change 0x80=128 overhead 28
thomas:astrec/tests% memory 1000
size 1000 base 140002400 change 0x400=1024 overhead 24
size 1000 base 140002800 change 0x400=1024 overhead 24
size 1000 base 140002c00 change 0x400=1024 overhead 24
size 1000 base 140003000 change 0x400=1024 overhead 24
thomas:astrec/tests% memory 10000
size 10000 base 140004720 change 0x2720=10016 overhead 16
size 10000 base 140006e40 change 0x2720=10016 overhead 16
size 10000 base 140009560 change 0x2720=10016 overhead 16
size 10000 base 14000bc80 change 0x2720=10016 overhead 16
thomas:astrec/tests% memory 100000
size 100000 base 14001a6c0 change 0x186c0=100032 overhead 32
size 100000 base 140032d80 change 0x186c0=100032 overhead 32
size 100000 base 14004b440 change 0x186c0=100032 overhead 32
size 100000 base 140063b00 change 0x186c0=100032 overhead 32
thomas:astrec/tests% memory 135160
size 135160 base 140023000 change 0x21000=135168 overhead 8
size 135160 base 140044000 change 0x21000=135168 overhead 8
size 135160 base 140065000 change 0x21000=135168 overhead 8
size 135160 base 140086000 change 0x21000=135168 overhead 8
thomas:astrec/tests% memory 135164
size 135164 base 140023020 change 0x21020=135200 overhead 36
size 135164 base 140044040 change 0x21020=135200 overhead 36
size 135164 base 140065060 change 0x21020=135200 overhead 36
size 135164 base 140086080 change 0x21020=135200 overhead 36
thomas:astrec/tests% memory 135168
size 135168 base 140023020 change 0x21020=135200 overhead 32
size 135168 base 140044040 change 0x21020=135200 overhead 32
size 135168 base 140065060 change 0x21020=135200 overhead 32
size 135168 base 140086080 change 0x21020=135200 overhead 32

*/