Dynamic Storage Allocator Pros and Cons

[Niels J|rgen Kruse]

rh at smds.UUCP (Richard Harter) writes:

rh >(A)    All invalid size requests (zero, negative, too large) are trapped.
njk>--------------------------------------------------^^^^^^^^^
njk> Try ``getsp (2147483646,0)''.   ;-)
rh >       ??? What machine is this on?  It worked fine on the
rh >       a couple of tests.

Sorry, i should have given more details.  It was a Vax-11/785
running MORE/Bsd 4.3, compiling with cc -g.  You must have used
a machine that zero-fill on signed right shift.  Here is the
relevant part of a gdb session:

getsp (size=2147483646, reqno=0) (getsp.c line 150)
150       if (size<=0) {                /* Bad size request             */
(gdb)
155       size += 4;                    /* Allow for check words        */
(gdb)
156       if (ninit) initsp();          /* Initialize if needful        */
(gdb) p size
$1 = -2147483646
(gdb) s
(...)
(gdb)
165       rx=(size-1)>>NSH;             /* Get requested index          */
(gdb)
166       rsz=(1+rx)<<NSH;              /* Get rounded request size     */
(gdb) p rx
$2 = -268435456
(gdb) s
(...)
(gdb)
170       if (rx>=MXSZ) fx=MXSZ;        /* Big request, set fx for big  */
(gdb)
172         if (px[rx]) fx=rx;          /* Exact fit exists             */
(gdb)
Program received signal 11, Segmentation fault

Authors of dynamic storage allocators almost never check for
overflow, when rounding up requests.  This is the first thing i
look for, when i come across a new one.

rh >                                               Best fit gains
rh >       in two ways -- the percentage of fragments is smaller
rh >       because of exact fits and the fragment size distribution
rh >       is skewed to favor very small or very large blocks.
rh >       Both advantages are much less when the request sizes
rh >       are "large".

This depends very much on the shape of the request size
distribution.  Consider what happens when you have request
sizes, that are very large and very rare.  With LIFO, the
largest free blocks tend to get nibbled at by smaller
requests, so when the very large request finally comes
along, no block is large enough and you have to grow the
heap.  Best Fit on the other hand, tend to preserve the
largest free blocks.
-- 
Niels J|rgen Kruse 	DIKU Graduate 	njk at diku.dk