| 1 |
\chapter{Smart Memory Allocation} |
| 2 |
\label{blb:TheChapterStart4} |
| 3 |
\index{Detection!Smart Memory Allocation With Orphaned Buffer } |
| 4 |
\index{Smart Memory Allocation With Orphaned Buffer Detection } |
| 5 |
|
| 6 |
\bimageH{smartall}{Smart Memory Allocation with Orphaned Buffer Detection}{} |
| 7 |
Few things are as embarrassing as a program that leaks, yet few errors are so |
| 8 |
easy to commit or as difficult to track down in a large, complicated program |
| 9 |
as failure to release allocated memory. SMARTALLOC replaces the standard C |
| 10 |
library memory allocation functions with versions which keep track of buffer |
| 11 |
allocations and releases and report all orphaned buffers at the end of program |
| 12 |
execution. By including this package in your program during development and |
| 13 |
testing, you can identify code that loses buffers right when it's added and |
| 14 |
most easily fixed, rather than as part of a crisis debugging push when the |
| 15 |
problem is identified much later in the testing cycle (or even worse, when the |
| 16 |
code is in the hands of a customer). When program testing is complete, simply |
| 17 |
recompiling with different flags removes SMARTALLOC from your program, |
| 18 |
permitting it to run without speed or storage penalties. |
| 19 |
|
| 20 |
In addition to detecting orphaned buffers, SMARTALLOC also helps to find other |
| 21 |
common problems in management of dynamic storage including storing before the |
| 22 |
start or beyond the end of an allocated buffer, referencing data through a |
| 23 |
pointer to a previously released buffer, attempting to release a buffer twice |
| 24 |
or releasing storage not obtained from the allocator, and assuming the initial |
| 25 |
contents of storage allocated by functions that do not guarantee a known |
| 26 |
value. SMARTALLOC's checking does not usually add a large amount of overhead |
| 27 |
to a program (except for programs which use {\tt realloc()} extensively; see |
| 28 |
below). SMARTALLOC focuses on proper storage management rather than internal |
| 29 |
consistency of the heap as checked by the malloc\_debug facility available on |
| 30 |
some systems. SMARTALLOC does not conflict with malloc\_debug and both may be |
| 31 |
used together, if you wish. SMARTALLOC makes no assumptions regarding the |
| 32 |
internal structure of the heap and thus should be compatible with any C |
| 33 |
language implementation of the standard memory allocation functions. |
| 34 |
|
| 35 |
\subsection{ Installing SMARTALLOC} |
| 36 |
\index{SMARTALLOC!Installing } |
| 37 |
\index{Installing SMARTALLOC } |
| 38 |
|
| 39 |
SMARTALLOC is provided as a Zipped archive, |
| 40 |
\bref{http://www.fourmilab.ch/smartall/smartall.zip}{smartall.zip}; see the |
| 41 |
download instructions below. |
| 42 |
|
| 43 |
To install SMARTALLOC in your program, simply add the statement: |
| 44 |
|
| 45 |
to every C program file which calls any of the memory allocation functions |
| 46 |
({\tt malloc}, {\tt calloc}, {\tt free}, etc.). SMARTALLOC must be used for |
| 47 |
all memory allocation with a program, so include file for your entire program, |
| 48 |
if you have such a thing. Next, define the symbol SMARTALLOC in the |
| 49 |
compilation before the inclusion of smartall.h. I usually do this by having my |
| 50 |
Makefile add the ``{\tt -DSMARTALLOC}'' option to the C compiler for |
| 51 |
non-production builds. You can define the symbol manually, if you prefer, by |
| 52 |
adding the statement: |
| 53 |
|
| 54 |
{\tt \#define SMARTALLOC} |
| 55 |
|
| 56 |
At the point where your program is all done and ready to relinquish control to |
| 57 |
the operating system, add the call: |
| 58 |
|
| 59 |
{\tt \ \ \ \ \ \ \ \ sm\_dump(}{\it datadump}{\tt );} |
| 60 |
|
| 61 |
where {\it datadump} specifies whether the contents of orphaned buffers are to |
| 62 |
be dumped in addition printing to their size and place of allocation. The data |
| 63 |
are dumped only if {\it datadump} is nonzero, so most programs will normally |
| 64 |
use ``{\tt sm\_dump(0);}''. If a mysterious orphaned buffer appears that can't |
| 65 |
be identified from the information this prints about it, replace the statement |
| 66 |
with ``{\tt sm\_dump(1)};''. Usually the dump of the buffer's data will |
| 67 |
furnish the additional clues you need to excavate and extirpate the elusive |
| 68 |
error that left the buffer allocated. |
| 69 |
|
| 70 |
Finally, add the files ``smartall.h'' and ``smartall.c'' from this release to |
| 71 |
your source directory, make dependencies, and linker input. You needn't make |
| 72 |
inclusion of smartall.c in your link optional; if compiled with SMARTALLOC not |
| 73 |
defined it generates no code, so you may always include it knowing it will |
| 74 |
waste no storage in production builds. Now when you run your program, if it |
| 75 |
leaves any buffers around when it's done, each will be reported by {\tt |
| 76 |
sm\_dump()} on stderr as follows: |
| 77 |
|
| 78 |
\begin{bVerbatim} |
| 79 |
Orphaned buffer: 120 bytes allocated at line 50 of gutshot.c |
| 80 |
\end{bVerbatim} |
| 81 |
\normalsize |
| 82 |
|
| 83 |
\subsection{ Squelching a SMARTALLOC} |
| 84 |
\index{SMARTALLOC!Squelching a } |
| 85 |
\index{Squelching a SMARTALLOC } |
| 86 |
|
| 87 |
Usually, when you first install SMARTALLOC in an existing program you'll find |
| 88 |
it nattering about lots of orphaned buffers. Some of these turn out to be |
| 89 |
legitimate errors, but some are storage allocated during program |
| 90 |
initialisation that, while dynamically allocated, is logically static storage |
| 91 |
not intended to be released. Of course, you can get rid of the complaints |
| 92 |
about these buffers by adding code to release them, but by doing so you're |
| 93 |
adding unnecessary complexity and code size to your program just to silence |
| 94 |
the nattering of a SMARTALLOC, so an escape hatch is provided to eliminate the |
| 95 |
need to release these buffers. |
| 96 |
|
| 97 |
Normally all storage allocated with the functions {\tt malloc()}, {\tt |
| 98 |
calloc()}, and {\tt realloc()} is monitored by SMARTALLOC. If you make the |
| 99 |
function call: |
| 100 |
|
| 101 |
\begin{bVerbatim} |
| 102 |
sm_static(1); |
| 103 |
\end{bVerbatim} |
| 104 |
\normalsize |
| 105 |
|
| 106 |
you declare that subsequent storage allocated by {\tt malloc()}, {\tt |
| 107 |
calloc()}, and {\tt realloc()} should not be considered orphaned if found to |
| 108 |
be allocated when {\tt sm\_dump()} is called. I use a call on ``{\tt |
| 109 |
sm\_static(1);}'' before I allocate things like program configuration tables |
| 110 |
so I don't have to add code to release them at end of program time. After |
| 111 |
allocating unmonitored data this way, be sure to add a call to: |
| 112 |
|
| 113 |
\begin{bVerbatim} |
| 114 |
sm_static(0); |
| 115 |
\end{bVerbatim} |
| 116 |
\normalsize |
| 117 |
|
| 118 |
to resume normal monitoring of buffer allocations. Buffers allocated while |
| 119 |
{\tt sm\_static(1}) is in effect are not checked for having been orphaned but |
| 120 |
all the other safeguards provided by SMARTALLOC remain in effect. You may |
| 121 |
release such buffers, if you like; but you don't have to. |
| 122 |
|
| 123 |
\subsection{ Living with Libraries} |
| 124 |
\index{Libraries!Living with } |
| 125 |
\index{Living with Libraries } |
| 126 |
|
| 127 |
Some library functions for which source code is unavailable may gratuitously |
| 128 |
allocate and return buffers that contain their results, or require you to pass |
| 129 |
them buffers which they subsequently release. If you have source code for the |
| 130 |
library, by far the best approach is to simply install SMARTALLOC in it, |
| 131 |
particularly since this kind of ill-structured dynamic storage management is |
| 132 |
the source of so many storage leaks. Without source code, however, there's no |
| 133 |
option but to provide a way to bypass SMARTALLOC for the buffers the library |
| 134 |
allocates and/or releases with the standard system functions. |
| 135 |
|
| 136 |
For each function {\it xxx} redefined by SMARTALLOC, a corresponding routine |
| 137 |
named ``{\tt actually}{\it xxx}'' is furnished which provides direct access to |
| 138 |
the underlying system function, as follows: |
| 139 |
|
| 140 |
\LTXtable{\linewidth}{t-dev-systemsfunctions} |
| 141 |
|
| 142 |
For example, suppose there exists a system library function named ``{\tt |
| 143 |
getimage()}'' which reads a raster image file and returns the address of a |
| 144 |
buffer containing it. Since the library routine allocates the image directly |
| 145 |
with {\tt malloc()}, you can't use SMARTALLOC's {\tt free()}, as that call |
| 146 |
expects information placed in the buffer by SMARTALLOC's special version of |
| 147 |
{\tt malloc()}, and hence would report an error. To release the buffer you |
| 148 |
should call {\tt actuallyfree()}, as in this code fragment: |
| 149 |
|
| 150 |
\begin{bVerbatim} |
| 151 |
struct image *ibuf = getimage("ratpack.img"); |
| 152 |
display_on_screen(ibuf); |
| 153 |
actuallyfree(ibuf); |
| 154 |
\end{bVerbatim} |
| 155 |
\normalsize |
| 156 |
|
| 157 |
Conversely, suppose we are to call a library function, ``{\tt putimage()}'', |
| 158 |
which writes an image buffer into a file and then releases the buffer with |
| 159 |
{\tt free()}. Since the system {\tt free()} is being called, we can't pass a |
| 160 |
buffer allocated by SMARTALLOC's allocation routines, as it contains special |
| 161 |
information that the system {\tt free()} doesn't expect to be there. The |
| 162 |
following code uses {\tt actuallymalloc()} to obtain the buffer passed to such |
| 163 |
a routine. |
| 164 |
|
| 165 |
\begin{bVerbatim} |
| 166 |
struct image *obuf = |
| 167 |
(struct image *) actuallymalloc(sizeof(struct image)); |
| 168 |
dump_screen_to_image(obuf); |
| 169 |
putimage("scrdump.img", obuf); /* putimage() releases obuf */ |
| 170 |
\end{bVerbatim} |
| 171 |
\normalsize |
| 172 |
|
| 173 |
It's unlikely you'll need any of the ``actually'' calls except under very odd |
| 174 |
circumstances (in four products and three years, I've only needed them once), |
| 175 |
but they're there for the rare occasions that demand them. Don't use them to |
| 176 |
subvert the error checking of SMARTALLOC; if you want to disable orphaned |
| 177 |
buffer detection, use the {\tt sm\_static(1)} mechanism described above. That |
| 178 |
way you don't forfeit all the other advantages of SMARTALLOC as you do when |
| 179 |
using {\tt actuallymalloc()} and {\tt actuallyfree()}. |
| 180 |
|
| 181 |
\subsection{ SMARTALLOC Details} |
| 182 |
\index{SMARTALLOC Details } |
| 183 |
\index{Details!SMARTALLOC } |
| 184 |
|
| 185 |
When you include ``smartall.h'' and define SMARTALLOC, the following standard |
| 186 |
system library functions are redefined with the \#define mechanism to call |
| 187 |
corresponding functions within smartall.c instead. (For details of the |
| 188 |
redefinitions, please refer to smartall.h.) |
| 189 |
|
| 190 |
\begin{bVerbatim} |
| 191 |
void *malloc(size_t size) |
| 192 |
void *calloc(size_t nelem, size_t elsize) |
| 193 |
void *realloc(void *ptr, size_t size) |
| 194 |
void free(void *ptr) |
| 195 |
void cfree(void *ptr) |
| 196 |
\end{bVerbatim} |
| 197 |
\normalsize |
| 198 |
|
| 199 |
{\tt cfree()} is a historical artifact identical to {\tt free()}. |
| 200 |
|
| 201 |
In addition to allocating storage in the same way as the standard library |
| 202 |
functions, the SMARTALLOC versions expand the buffers they allocate to include |
| 203 |
information that identifies where each buffer was allocated and to chain all |
| 204 |
allocated buffers together. When a buffer is released, it is removed from the |
| 205 |
allocated buffer chain. A call on {\tt sm\_dump()} is able, by scanning the |
| 206 |
chain of allocated buffers, to find all orphaned buffers. Buffers allocated |
| 207 |
while {\tt sm\_static(1)} is in effect are specially flagged so that, despite |
| 208 |
appearing on the allocated buffer chain, {\tt sm\_dump()} will not deem them |
| 209 |
orphans. |
| 210 |
|
| 211 |
When a buffer is allocated by {\tt malloc()} or expanded with {\tt realloc()}, |
| 212 |
all bytes of newly allocated storage are set to the hexadecimal value 0x55 |
| 213 |
(alternating one and zero bits). Note that for {\tt realloc()} this applies |
| 214 |
only to the bytes added at the end of buffer; the original contents of the |
| 215 |
buffer are not modified. Initializing allocated storage to a distinctive |
| 216 |
nonzero pattern is intended to catch code that erroneously assumes newly |
| 217 |
allocated buffers are cleared to zero; in fact their contents are random. The |
| 218 |
{\tt calloc()} function, defined as returning a buffer cleared to zero, |
| 219 |
continues to zero its buffers under SMARTALLOC. |
| 220 |
|
| 221 |
Buffers obtained with the SMARTALLOC functions contain a special sentinel byte |
| 222 |
at the end of the user data area. This byte is set to a special key value |
| 223 |
based upon the buffer's memory address. When the buffer is released, the key |
| 224 |
is tested and if it has been overwritten an assertion in the {\tt free} |
| 225 |
function will fail. This catches incorrect program code that stores beyond the |
| 226 |
storage allocated for the buffer. At {\tt free()} time the queue links are |
| 227 |
also validated and an assertion failure will occur if the program has |
| 228 |
destroyed them by storing before the start of the allocated storage. |
| 229 |
|
| 230 |
In addition, when a buffer is released with {\tt free()}, its contents are |
| 231 |
immediately destroyed by overwriting them with the hexadecimal pattern 0xAA |
| 232 |
(alternating bits, the one's complement of the initial value pattern). This |
| 233 |
will usually trip up code that keeps a pointer to a buffer that's been freed |
| 234 |
and later attempts to reference data within the released buffer. Incredibly, |
| 235 |
this is {\it legal} in the standard Unix memory allocation package, which |
| 236 |
permits programs to free() buffers, then raise them from the grave with {\tt |
| 237 |
realloc()}. Such program ``logic'' should be fixed, not accommodated, and |
| 238 |
SMARTALLOC brooks no such Lazarus buffer`` nonsense. |
| 239 |
|
| 240 |
Some C libraries allow a zero size argument in calls to {\tt malloc()}. Since |
| 241 |
this is far more likely to indicate a program error than a defensible |
| 242 |
programming stratagem, SMARTALLOC disallows it with an assertion. |
| 243 |
|
| 244 |
When the standard library {\tt realloc()} function is called to expand a |
| 245 |
buffer, it attempts to expand the buffer in place if possible, moving it only |
| 246 |
if necessary. Because SMARTALLOC must place its own private storage in the |
| 247 |
buffer and also to aid in error detection, its version of {\tt realloc()} |
| 248 |
always moves and copies the buffer except in the trivial case where the size |
| 249 |
of the buffer is not being changed. By forcing the buffer to move on every |
| 250 |
call and destroying the contents of the old buffer when it is released, |
| 251 |
SMARTALLOC traps programs which keep pointers into a buffer across a call on |
| 252 |
{\tt realloc()} which may move it. This strategy may prove very costly to |
| 253 |
programs which make extensive use of {\tt realloc()}. If this proves to be a |
| 254 |
problem, such programs may wish to use {\tt actuallymalloc()}, {\tt |
| 255 |
actuallyrealloc()}, and {\tt actuallyfree()} for such frequently-adjusted |
| 256 |
buffers, trading error detection for performance. Although not specified in |
| 257 |
the System V Interface Definition, many C library implementations of {\tt |
| 258 |
realloc()} permit an old buffer argument of NULL, causing {\tt realloc()} to |
| 259 |
allocate a new buffer. The SMARTALLOC version permits this. |
| 260 |
|
| 261 |
\subsection{ When SMARTALLOC is Disabled} |
| 262 |
\index{When SMARTALLOC is Disabled } |
| 263 |
\index{Disabled!When SMARTALLOC is } |
| 264 |
|
| 265 |
When SMARTALLOC is disabled by compiling a program with the symbol SMARTALLOC |
| 266 |
not defined, calls on the functions otherwise redefined by SMARTALLOC go |
| 267 |
directly to the system functions. In addition, compile-time definitions |
| 268 |
translate calls on the ''{\tt actually}...{\tt ()}`` functions into the |
| 269 |
corresponding library calls; ''{\tt actuallymalloc(100)}``, for example, |
| 270 |
compiles into ''{\tt malloc(100)}``. The two special SMARTALLOC functions, |
| 271 |
{\tt sm\_dump()} and {\tt sm\_static()}, are defined to generate no code |
| 272 |
(hence the null statement). Finally, if SMARTALLOC is not defined, compilation |
| 273 |
of the file smartall.c generates no code or data at all, effectively removing |
| 274 |
it from the program even if named in the link instructions. |
| 275 |
|
| 276 |
Thus, except for unusual circumstances, a program that works with SMARTALLOC |
| 277 |
defined for testing should require no changes when built without it for |
| 278 |
production release. |
| 279 |
|
| 280 |
\subsection{ The {\tt alloc()} Function} |
| 281 |
\index{Function!alloc } |
| 282 |
\index{Alloc() Function } |
| 283 |
|
| 284 |
Many programs I've worked on use very few direct calls to {\tt malloc()}, |
| 285 |
using the identically declared {\tt alloc()} function instead. Alloc detects |
| 286 |
out-of-memory conditions and aborts, removing the need for error checking on |
| 287 |
every call of {\tt malloc()} (and the temptation to skip checking for |
| 288 |
out-of-memory). |
| 289 |
|
| 290 |
As a convenience, SMARTALLOC supplies a compatible version of {\tt alloc()} in |
| 291 |
the file alloc.c, with its definition in the file alloc.h. This version of |
| 292 |
{\tt alloc()} is sensitive to the definition of SMARTALLOC and cooperates with |
| 293 |
SMARTALLOC's orphaned buffer detection. In addition, when SMARTALLOC is |
| 294 |
defined and {\tt alloc()} detects an out of memory condition, it takes |
| 295 |
advantage of the SMARTALLOC diagnostic information to identify the file and |
| 296 |
line number of the call on {\tt alloc()} that failed. |
| 297 |
|
| 298 |
\subsection{ Overlays and Underhandedness} |
| 299 |
\index{Underhandedness!Overlays and } |
| 300 |
\index{Overlays and Underhandedness } |
| 301 |
|
| 302 |
String constants in the C language are considered to be static arrays of |
| 303 |
characters accessed through a pointer constant. The arrays are potentially |
| 304 |
writable even though their pointer is a constant. SMARTALLOC uses the |
| 305 |
compile-time definition {\tt ./smartall.wml} to obtain the name of the file in |
| 306 |
which a call on buffer allocation was performed. Rather than reserve space in |
| 307 |
a buffer to save this information, SMARTALLOC simply stores the pointer to the |
| 308 |
compiled-in text of the file name. This works fine as long as the program does |
| 309 |
not overlay its data among modules. If data are overlayed, the area of memory |
| 310 |
which contained the file name at the time it was saved in the buffer may |
| 311 |
contain something else entirely when {\tt sm\_dump()} gets around to using the |
| 312 |
pointer to edit the file name which allocated the buffer. |
| 313 |
|
| 314 |
If you want to use SMARTALLOC in a program with overlayed data, you'll have to |
| 315 |
modify smartall.c to either copy the file name to a fixed-length field added |
| 316 |
to the {\tt abufhead} structure, or else allocate storage with {\tt malloc()}, |
| 317 |
copy the file name there, and set the {\tt abfname} pointer to that buffer, |
| 318 |
then remember to release the buffer in {\tt sm\_free}. Either of these |
| 319 |
approaches are wasteful of storage and time, and should be considered only if |
| 320 |
there is no alternative. Since most initial debugging is done in non-overlayed |
| 321 |
environments, the restrictions on SMARTALLOC with data overlaying may never |
| 322 |
prove a problem. Note that conventional overlaying of code, by far the most |
| 323 |
common form of overlaying, poses no problems for SMARTALLOC; you need only be |
| 324 |
concerned if you're using exotic tools for data overlaying on MS-DOS or other |
| 325 |
address-space-challenged systems. |
| 326 |
|
| 327 |
Since a C language ''constant`` string can actually be written into, most C |
| 328 |
compilers generate a unique copy of each string used in a module, even if the |
| 329 |
same constant string appears many times. In modules that contain many calls on |
| 330 |
allocation functions, this results in substantial wasted storage for the |
| 331 |
strings that identify the file name. If your compiler permits optimization of |
| 332 |
multiple occurrences of constant strings, enabling this mode will eliminate |
| 333 |
the overhead for these strings. Of course, it's up to you to make sure |
| 334 |
choosing this compiler mode won't wreak havoc on some other part of your |
| 335 |
program. |
| 336 |
|
| 337 |
\subsection{ Test and Demonstration Program} |
| 338 |
\index{Test and Demonstration Program } |
| 339 |
\index{Program!Test and Demonstration } |
| 340 |
|
| 341 |
A test and demonstration program, smtest.c, is supplied with SMARTALLOC. You |
| 342 |
can build this program with the Makefile included. Please refer to the |
| 343 |
comments in smtest.c and the Makefile for information on this program. If |
| 344 |
you're attempting to use SMARTALLOC on a new machine or with a new compiler or |
| 345 |
operating system, it's a wise first step to check it out with smtest first. |
| 346 |
|
| 347 |
\subsection{ Invitation to the Hack} |
| 348 |
\index{Hack!Invitation to the } |
| 349 |
\index{Invitation to the Hack } |
| 350 |
|
| 351 |
SMARTALLOC is not intended to be a panacea for storage management problems, |
| 352 |
nor is it universally applicable or effective; it's another weapon in the |
| 353 |
arsenal of the defensive professional programmer attempting to create reliable |
| 354 |
products. It represents the current state of evolution of expedient debug code |
| 355 |
which has been used in several commercial software products which have, |
| 356 |
collectively, sold more than third of a million copies in the retail market, |
| 357 |
and can be expected to continue to develop through time as it is applied to |
| 358 |
ever more demanding projects. |
| 359 |
|
| 360 |
The version of SMARTALLOC here has been tested on a Sun SPARCStation, Silicon |
| 361 |
Graphics Indigo2, and on MS-DOS using both Borland and Microsoft C. Moving |
| 362 |
from compiler to compiler requires the usual small changes to resolve disputes |
| 363 |
about prototyping of functions, whether the type returned by buffer allocation |
| 364 |
is {\tt char\ *} or {\tt void\ *}, and so forth, but following those changes |
| 365 |
it works in a variety of environments. I hope you'll find SMARTALLOC as useful |
| 366 |
for your projects as I've found it in mine. |
| 367 |
|
| 368 |
\section{Download smartall.zip (Zipped archive)} |
| 369 |
\index{Archive! Download smartall.zip Zipped } |
| 370 |
\index{ Download smartall.zip (Zipped archive) } |
| 371 |
|
| 372 |
SMARTALLOC is provided as |
| 373 |
\bref{http://www.fourmilab.ch/smartall/smartall.zip}{smartall.zip}, a |
| 374 |
\bref{http://www.pkware.com/}{Zipped} archive containing source code, |
| 375 |
documentation, and a {\tt Makefile} to build the software under Unix. |
| 376 |
|
| 377 |
\subsection{ Copying} |
| 378 |
\index{Copying } |
| 379 |
|
| 380 |
\begin{quote} |
| 381 |
SMARTALLOC is in the public domain. Permission to use, copy, modify, and |
| 382 |
distribute this software and its documentation for any purpose and without fee |
| 383 |
is hereby granted, without any conditions or restrictions. This software is |
| 384 |
provided ''as is`` without express or implied warranty. |
| 385 |
\end{quote} |
| 386 |
|
| 387 |
{\it |
| 388 |
\bref{http://www.fourmilab.ch}{by John Walker} |
| 389 |
October 30th, 1998 } |