Ross Harvey writes:
|> 
|> > From: Hauke Fath <hauke@Espresso.Rhein-Neckar.DE>
|> > At 8:46 Uhr +0100 16.12.1998, Todd Whitesel wrote:
|> > >> kernel malloc operates on buckets of size power-of-two.  each page is
|> > >> subdivided into buckets.  they're never subdivided.
|> > >
|> > >"Excellent."
|> > >
|> > >BTW Does anyone know how popular this algorithm is among the various unices?
|> 
|> AFAIK it is used by *BSD and by Digital Unix.

Not exactly for DU.  It used to have power of two buckets but
that led to too much fragmentation.  Here's what it does now,
from <sys/malloc.h>:

#define BUCKETINDEX(size)  \
        (((size) <= 768) \
            ? (((size) <= 256) \
                ? (((size) <= 96) \
                    ? (((size) <= 32) \
                        ? (((size) <= 16) ? 0 : 1) \
                        : (((size) <= 64) ? 2 : 16)) \
                    : (((size) <= 160) \
                        ? (((size) <= 128) ? 3 : 17) \
                        : (((size) <= 192) ? 18 : 4))) \
                : (((size) <= 512) \
                    ? (((size) <= 384) \
                         ? (((size) <= 320) ? 19 : 20)  \
                         : (((size) <= 448) ? 21 : 5)) \
                    : (((size) <= 640) \
                        ? (((size) <= 576) ? 22 : 23)  \
                        : (((size) <= 704) ? 24 : 25)))) \
            : (((size) <= 4096) \
                ? (((size) <= 1344) \
                    ? (((size) <= 1024) \
                        ? (((size) <=  896) ? 26 : 6) \
                        : (((size) <= 1152) ? 27 : 28)) \
                    : (((size) <= 2048) \
                        ? (((size) <= 1600) ? 29 : 7) \
                        : (((size) <= 2688) ? 30 : 8))) \
                : (((size) <= 32*1024) \
                    ? (((size) <= 12*1024) \
                         ? (((size) <=  8*1024) ? 9 : 31)  \
                         : (((size) <= 16*1024) ? 10 : 11)) \
                    : (((size) <= 128*1024) \
                        ? (((size) <= 64*1024) ? 12 : 13)  \
                        : (((size) <= 256*1024) ? 14 : 15)))))

It's malloc also has debug modes that do auditing, leak detection,
internal consistency checking and even a mode where virtual addresses
are never reused and are always unmapped after being freed so any 
access to that address will fault.  This is great for finding use
of pointers after freeing the memory.

-- 
Dave Cherkus ------- UniMaster, Inc. ------ Contract Software Development
Specialties: UNIX Internals/Kernel TCP/IP Alpha Clusters Performance ISDN
Email: cherkus@UniMaster.COM  When the music's over, turn out the lights!