The Secret Life Of The Memory Manager

RICHARD CLARK

The Macintosh Memory Manager has changed in some subtle ways since it was documented in Inside Macintosh . This, combined with the difficulty of observing what the Memory Manager actually does, has led to a general misunderstanding of how the Memory Manager works. This article first discusses some common myths about the Memory Manager, then describes some ways to avoid memory-related errors and control fragmentation without sacrificing execution speed.

Few parts of the Macintosh operating system raise as many questions as the Memory Manager. Since the contents of RAM change dynamically, it's hard to really examine the Memory Manager's behavior. This, combined with the unusual concept of relocatable blocks and the fact that the Memory Manager is used by most of the operating system, has left many Macintosh programmers confused about the behavior of the Memory Manager and, more important, about the impact of this behavior on their applications.

MYTHS ABOUT THE MEMORY MANAGER

Several myths have grown up around the Memory Manager, serving to increase the confusion about its real behavior. Three of the most prevalent--but mistaken-- beliefs are that (1) the Memory Manager will move and delete blocks, and otherwise mangle the heap, at random; (2) using nonrelocatable blocks will cause serious heap fragmentation; and (3) if you use Virtual Memory you don't need to worry about the Memory Manager. We'll demolish each of these myths in turn.

MYTH 1: THE MEMORY MANAGER WILL MOVE AND DELETE BLOCKS, AND OTHERWISE MANGLE THE HEAP, AT RANDOM
This simply isn't so. The Memory Manager is in fact quite predictable. It only moves blocks under these circumstances:

• When your application calls a routine that allocates new blocks or enlarges existing ones, when you request that blocks be moved, or when your application calls a routine that in turn calls a ROM routine that may trigger block relocation. Appendix A of the Inside Macintosh XRef lists all routines defined in Inside Macintosh that may cause blocks to move.
• When the called routine is in a different segment from the code that makes the call, or when the called routine is in the same segment as the caller, but the called routine calls a routine or routines in a different segment. If a called routine lies in a different code segment, the Segment Loader may need to call the code segment in from disk and/or move it to the top of the heap. Either of these actions can cause blocks to move.

MYTH 2: USING NONRELOCATABLE BLOCKS WILL CAUSE SERIOUS MEMORY FRAGMENTATION
This is a half-truth at best. The Memory Manager actually does a good job of allocating nonrelocat- able blocks, but can fragment the heap when these blocks are deallocated and new ones allocated. Similar problems can happen when you start locking relocatable blocks.

This myth actually has a basis in reality, as the earliest versions of the Memory Manager did a poor job of allocating nonrelocatable blocks. Before the 128K ROMs (introduced with the Macintosh 512Ke and Macintosh Plus), the Memory Manager would not move a relocatable block around a nonrelocatable block in its quest to allocate a new nonrelocatable block. This made the heap into a patchwork of relocatable and nonrelocatable blocks, and caused general fragmentation problems, as illustrated in Figure 1.

Figure 1. Fragmentation of Free Space

But that has long since changed, as NewPtr will now move a relocatable block around a nonrelocatable block when allocating memory. This tends to partition the heap into two active areas, with all of the nonrelocatable blocks at the bottom of the heap, and the relocatable blocks located immediately above. (See the sidebar "How the Memory Manager Allocates Heap Space" for further details.)

On the other hand, for all of the improvements in allocation of nonrelocatable blocks, there is still a problem withde allocation of these blocks. Since the Memory Manager uses a "find the first free block that fulfills the request" strategy (as opposed to "find a block that fits the request exactly"), if you allocate a subsequent block that is smaller than the block you just deleted, the heap will become fragmented and the amount of usable memory will likely decrease, as illustrated in Figure 3.

Figure 3. The Effect of Deallocating and Reallocating a Nonrelocatable Block

Locking too many relocatable blocks can cause the same kind of fragmentation problems as deallocating and reallocating nonrelocatable blocks. A well-trained programmer uses the callMoveHHito move a relocatable block to the top of the heap before locking it. This has the effect of partitioning the heap into four areas, as shown in Figure 4. The idea of usingMoveHHi is to keep the contiguous free space as large as possible. However,MoveHHi will only move a block upward until it meets either a nonrelocatable block or a locked relocatable block. UnlikeNewPtr (andResrvMem),MoveHHi will not move a relocatable block around one that is not relocatable.

Even if you succeed in moving a relocatable block to the top of the heap, your problems are far from over. Unlocking or deleting locked blocks can also cause fragmentation, unless they are unlocked beginning with the lowest locked block. In the case illustrated in Figure 4, unlocking and deleting blocks in the middle of the locked area has resulted in heap fragmentation. The relocatable blocks thus trapped in the middle won't be moved until the locked block below them is unlocked.

Figure 4. The Effect of Unlocking Locked Blocks

MYTH 3: IF YOU USE VIRTUAL MEMORY, YOU DON'T NEED TO WORRY ABOUT THE MEMORY MANAGER
Many people believe that the wide availability of Virtual Memory will remove the need for careful memory management. Wrong! The Virtual Memory system is based on a series of "pages" of memory that can be swapped to and from the disk, rather than on individual blocks of memory. If you fragment RAM, you also "fragment" the contents of the swap file and gain nothing. In fact, Virtual Memory makes careful memory management even more critical, for two reasons. First, fragmenting the swap file will degrade system performance worse than fragmenting physical memory will, since disk access speeds are obviously slower than the RAM access speed. Second, the combination of Virtual Memory and MultiFinder encourages users to run more programs at the same time than they used to, and users often reduce the partition sizes of their applications to squeeze in "one more program."

THE EXPERT'S GUIDE TO MEMORY MANAGEMENT

Now you know that the Memory Manager moves blocks of memory only at certain well-defined times; that nonrelocatable blocks can be allocated without causing serious fragmentation in the heap, although deallocation and reallocation of these blocks, and locking too many relocatable blocks, can cause problems; and that use of Virtual Memory makes careful memory management even more important. It's time to put this knowledge into action. In this section, you'll learn how you can work cooperatively with the Memory Manager to increase the efficiency and robustness of your applications.

TO AVOID DANGLING POINTERS
As every programmer learns early on, the gravest side effect of the Memory Manager's penchant for moving blocks of memory is the peril of dangling pointers. (For a refresher on how these come about, see the sidebar entitled "A Primer on Handles and Their Pitfalls" in Curt Bianchi's article "Using Objects Safely in Object Pascal" in this issue.) And the best defense against having to spend hours--or days--debugging errors caused by dangling pointers is to anticipate situations in which block movement might occur, and if it does occur, will throw a monkey wrench into the works. In these situations, much grief can be saved by using a temporary local or global variable to store a duplicate of the relocatable block. (Note, though, that this trick only works properly if the block can stand on its own--that is, it's not part of a linked list.)

Some of the situations that might get you into trouble are well documented, such as the use of the WITH statement in Pascal. Other dangerous situations are less obvious, so we'll explore them here.

Be careful when evaluating expressions. There are times when evaluating a seemingly innocent expression might have serious side effects. For example, look at the following code:

TYPE
    windowInfoHdl = ^windowInfoPtr;
    windowInfoPtr = ^windowInfo;
    windowInfo = RECORD
        aControlHdl: ControlHandle;
        aWindowPtr: WindowPtr;
    END;

VAR
    myHandle : windowInfoHdl;

BEGIN
    myHandle := windowInfoHdl(NewHandle(sizeof(windowInfo)));
    { The next 2 statements have problems. }
    myHandle^^.aWindowPtr := GetNewWindow(1000, NIL, WindowPtr(-1));
    myHandle^^.aControlHdl :=
        GetNewControl(1000, myHandle^^.aWindowPtr);
END;

In Pascal, the above statements would probably cause a run-time error. The problem is in the expression " myHandle^^.something :=" as the compiler evaluates expressions from left to right and calculates the address on the left side of the assignment statement before making the toolbox call. When GetNewWindow is called, myHandle^^ is moved (we passed in NII to force a call to NewPtr) and the address on the left- hand side is no longer valid! This means that the returned WindowPtr will be written into the wrong area of memory, and the program will probably crash.

While both statements suffer from the same basic problem, the first one is more likely to cause a crash than the second one and is therefore easier to debug. Why is this?

The statement containing GetNewWindow will make a call to NewPtr to allocate a nonrelocatable block at the bottom of the heap, forcing relocatable blocks upward in the process. The other statement, containing GetNewControl, allocates a relocatable block, which usually appears above the existing blocks, with block movement happening only if a compaction is required.

While this problem occurs most frequently in Pascal, C programs are not immune. Most C compilers on the Macintosh evaluate the right- hand side of an assignment before the left-hand side--which avoids this problem entirely--but the order of evaluation is not guaranteed by the ANSI standard.

This problem can be solved easily by using a temporary variable. The following code avoids the problem:

VAR
 myHandle:    windowInfoHdl;
 aWindowPtr:   WindowPtr;        { This is allocated on the }
                                 { stack, so it won't move. }
 aControlHandle: ControlHandle;  { Also on the stack. }

BEGIN
 myHandle := windowInfoHdl(NewHandle(sizeof(windowInfo)));

 { Copy the result into a temporary variable, then copy }
 { that into the relocatable block. }
 aWindowPtr := GetNewWindow(1000, NIL, WindowPtr(-1));
 myHandle^^.aWindowPtr := aWindowPtr;

 aControlHandle := GetNewControl(1000, aWindowPtr);
 myHandle^^.aControlHdl := aControlHandle;
END;

Be careful when using callback routines. When you pass pointers to your routines, say as a ROM callback routine, and your routines are in multiple segments, you need to be careful.

The following code is fine now, but we'll soon edit it to demonstrate the problem:

{$S Main }
PROCEDURE MyCallback(ctl: ControlHandle; part: INTEGER);
{ This represents a callback routine used for continuous }
{ tracking in controls. }
BEGIN
 { Do whatever you need to do. }
END;

PROCEDURE HandleMyControl(theControl: ControlHandle;
             pt: Point);
BEGIN
 part := TrackControl(theControl, pt, @MyCallback);
END;

The expression @MyCallbackpushes the address of the callback routine onto the stack before calling TrackControl. If the two routines are in the same segment, as in the preceding example, all is fine. The segment is locked in memory when @MyCallback is both evaluated and used; therefore, the address is valid. If the two routines are in different segments, this also works, as the compiler takes the address of the jump table entry for MyCallback.

In some cases, and especially in C, you may choose to set up a table of procedure addresses. But if you store the address of the routine into a variable, strange things may happen. Take a look at the following code:

{ ----------------------------- }
{ For an example, we'll place the addresses of two control }
{ tracking routines into an array, then use them. }

VAR
 gCallbackArray: ARRAY [1..2] OF ProcPtr;

{ ----------------------------- }
{$S Segment1 }

 PROCEDURE MyVScrollCallback(theControl: ControlHandle;
               part: INTEGER);
 BEGIN
  { This will get called if our control is a vertical }
  { scrollbar. }
 END;


 PROCEDURE MyVScrollCallback(theControl: ControlHandle;
               part: INTEGER);
 BEGIN
  { This will get called if our control is a horizontal }
  { scrollbar. }
 END;

 PROCEDURE InitCallbackArray;
 { Fill in the addresses in the global "Callback" array. }
 BEGIN
  { Problem: Since we're in the same segment, these aren't }
  { addresses of the jump table entries, but are absolute }
  { locations in RAM! If the segment moves (i.e., if }
  { UnloadSeg is called), the addresses will be invalid. }
  gCallbackArray[1] := @MyVScrollCallback; 
  gCallbackArray[2] := @MyHScrollCallback; 
 END;
END.

{ ----------------------------- }
{$S Main }

PROCEDURE HandleAScrollbar(theControl: ControlHandle;
             pt: Point);
{ We'll call this if the user clicks in our scrollbar (except }
{ if she clicks in the thumb, which uses a different kind of }
{ callback.) If it's a vertical scrollbar, use one callback; }
{ if horizontal, use the other. }
VAR
 part:    INTEGER;
 theCallback: ProcPtr;
 isVertical: Boolean;
 aRect:    Rect;
 cntlWidth:  INTEGER;

BEGIN
 aRect := theControl^^.cntrlRect;
 cntlWidth := aRect.right - aRect.left;
 isVertical := cntlWidth = 16;
 IF isVertical THEN
  part := TrackControl(theControl, pt, gCallbackArray[1])
 ELSE
  part := TrackControl(theControl, pt, gCallbackArray[2])
 { The TrackControl calls will probably crash if }
 { Segment1 has been unloaded since the table was built. }
 { You'll have a wonderful time trying to find the bug! }
END;

When setting up a table of such procedure addresses, or even a single global variable, you should do one of the following things: (1) make sure that the setup procedure is in a different segment from the procedures being called, thus insuring that you get the address of a jump table entry; (2) keep everything in one segment and never unload it; or (3) always load the segment and build the table before using any of the addresses (and make sure that the segment doesn't get unloaded in the meantime).

Be careful when passing parameters. Another problem area occurs when you pass parameters to routines that allocate or move memory. Can you spot the problem in the following code?

PROCEDURE ValidateControl(theControl: ControlHandle);
BEGIN
    ValidRect(theControl^^.contrlRect);
END;

ValidRect receives the address of a rectangle, which is pushed onto the stack before the trap is called. The problem is that beforeValidRect uses the rectangle's address, it often allocates memory of its own, which can cause theControl^^ to move and therefore invalidate the rectangle's address.

This problem happens when you pass (1) any parameter larger than four bytes, or (2) any VAR parameter. Again, the solution requires a temporary variable:

PROCEDURE ValidateControl(theControl: ControlHandle);
VAR
    r : Rect; { r is stack-based, so it doesn't move. }
BEGIN
    r := theControl^^.contrlRect;
    ValidRect(r);
END;

Pascal compilers often avoid this problem for user-defined functions by making a local copy of non-VAR parameters that are passed by address. The ROM doesn't make such a copy, so you need to be careful. This is discussed at length by Scott Knaster in How to Write Macintosh Software , 2nd ed. (Hayden Books, 1988).

TO CONTROL HEAP FRAGMENTATION
As you will recall, heap fragmentation can be caused by (1) deallocating and reallocating nonrelocatable blocks, and (2) locking too many relocatable blocks. To keep heap fragmentation under control, follow a few simple rules.

Use nonrelocatable blocks sparingly. To avoid the potential problems that deallocation and reallocation of nonrelocatable blocks can cause, you should theoretically use relocatable blocks for everything. However, in practice, there are areas where you must use nonrelocatable blocks, such as forGrafPorts and WindowRecords. In light of this reality, here are three suggestions to help you control fragmentation.

First, remember that you should not choose to use nonrelocatable blocks lightly. Use them only when the Macintosh operating system requires them, or when you can demonstrate a severe performance penalty for using relocatable blocks.

Second, avoid allocating nonrelocatable blocks unless they will never be deleted. If you know about such blocks ahead of time, then you can allocate them at program start-up. This works well if you'll have a single large "image buffer" or the like, or a limit on the number of available windows. In these cases, allocating your large fixed blocks at start-up time will avoid potential fragmentation problems.

Third, if you must allocate and deallocate nonrelocatable blocks on demand, you can add some additional memory management code of your own. When you want to deallocate a block of RAM, you can add it to a linked list of free blocks (that you maintain), and then check this list for a free block of the exact size you need each time you want to allocate a new block. Of course, this works best if the range of block sizes you support is limited, and you still have to decide what to do if the block you want doesn't fit any of the free blocks exactly. If you have to allocate a large number of nonrelocatable blocks, or have other special needs, you should consider allocating a large block of memory and doing your own memory management within that. Donald Knuth's bookThe Art of Computer Programming, volume 2, 2nd ed. (Addison-Wesley, 1973) contains a useful overview of memory management techniques under the heading "Dynamic Storage Allocation" (pp. 435-55 and 460-61).

Note that this strategy of reusing nonrelocatable blocks works best under the 128K ROM (and later) Memory Manager, since that version does the best job of allocating nonrelocatable blocks. If you plan to write software under the 64K ROMs (Macintosh 128K or 512K), you should consult Scott Knaster's How to Write Macintosh Software , which describes a strategy that does a better job with the old Memory Manager than this strategy does.

Lock selectively and consider alternatives. Fear of dangling pointers often drives new programmers to lock down everything in sight, quickly fragmenting the heap and impeding the application's performance. More experienced programmers try to avoid locking relocatable blocks, preferring instead to predict when the Memory Manager will move blocks of memory and then only locking a relocatable block if they must. If done infrequently, locking has a negligible impact on your application.

If you must lock a relocatable block, you should unlock it as soon as possible. This will lessen the probability of another block being moved in underneath (by MoveHHi) and locked. Also, if you move and lock several blocks together, you should unlock all of them together, or at least in the reverse of the order in which they were moved high. This will help ensure that the free area is kept together in the heap.

As an alternative to locking relocatable blocks, consider using temporary variables. We've already seen the use of temporary variables for such small items as window pointers and rectangles, but this approach can also be used for entire structures. Using temporary variables can simplify your code by removing the need for HLock and HUnlock calls. For example, many programs use a window's reference constant (RefCon) field to hold a handle to a data structure. Programs that do so look something like this:

TYPE
 windowInfoHdl = ^windowInfoPtr;
 windowInfoPtr = ^windowInfo;
 windowInfo = RECORD
  rectArray: ARRAY [1..10] OF Rect;
 END;

PROCEDURE UpdateWindow(wp: WindowPtr);
{ The window's RefCon contains a handle to the data structure shown }
{ above. The rectArray field contains an array of rectangles that }
{ we want to draw. }

VAR
 myHandle: windowInfoHdl;
 count:   INTEGER;

BEGIN
 { Get the window information, then lock the block so that it }
 { doesn't move while drawing the rectangles. }
 myHandle := windowInfoHdl(GetWRefCon(wp));
 MoveHHi(Handle(myHandle));
 HLock(Handle(myHandle));
 
 BeginUpdate(wp);
 FOR count := 1 TO 10 DO
  { Working with the heap-based window information, draw each }
  { rectangle. }
  FrameRect(myHandle^^.rectArray[count]);
 EndUpdate(wp);
 HUnlock(Handle(myHandle));
END;

Notice that we had to perform several type casts, and use MoveHHi,HLock, and HUnlock. Now, let's see how this would look using a temporary variable:

{ Type declarations omitted for brevity. }

PROCEDURE GetWindowInfo (wp: WindowPtr; VAR info: windowInfo);
{ Utility routine to make a copy (usually stack-based) of our }
{ window information structure. }
VAR
 myHandle: windowInfoHdl;

BEGIN
 { First, do a little error checking. }
 IF (wp <> NIL) THEN BEGIN
  myHandle := windowInfoHdl(GetWRefCon(wp));
  { You can incorporate extra error checking here. For example, }
  { this is a good place to compare the handle's size to the }
  { window information structure's size, or to verify that the }
  { contents of the block are legal values. }
  {                              }
  { Next, go ahead and copy the contents of the relocatable }
  { block to the specified location. We don't have to lock }
  { things down, since BlockMove won't cause compaction. }
  BlockMove(Ptr(myHandle^), @info, sizeof(windowInfo));
 END;
END;

PROCEDURE UpdateWindow(wp: WindowPtr);
VAR
 info: windowInfo;  { This storage is on the stack, therefore it }
                    { won't move. }


BEGIN
 GetWindowInfo(wp, info);  { Get a copy of the window information. }
 BeginUpdate(wp);
 FOR count := 1 TO 10 DO
  { Working with the stack-based copy of the window information, }
  { draw each rectangle. }
  FrameRect(info.rectArray[count]);
 EndUpdate(wp);
END;

This approach has two major advantages: safety and code simplification. If you have one central routine that gets the window information (and another similar one to set it), you can add quite a bit of error checking and catch a large number of potential errors. Speed shouldn't be a problem, as the single BlockMove operation is generally faster than the corresponding MoveHHi since the latter may need to move an old relocatable block out of the way first.

Of course, you have to beextremely careful when using this technique, as it is easy to exceed the stack size limit when using recursive or heavily nested procedures. If you have a series of nested procedures that all use the window information structure, you can get the structure in the topmost procedure and pass the block down as aVAR parameter (pass-by-address in C) so that an extra copy of the data structure isn't made.

FINAL WORDS OF ADVICE

In this article, we've taken a quick look inside the Memory Manager, but we have not been able to cover everything. If you want to have a fuller understanding of Macintosh memory management, there are a few things you can do. First, reread chapter 3 of Inside Macintosh , volume I, and chapter 1 of Inside Macintosh , volume II. Next, take a look at Scott Knaster's How to Write Macintosh Software , mentioned earlier, which has an excellent discussion of memory management. (In fact, I recommend the book highly to anybody who wants a better understanding of developing and debugging Macintosh software.) Finally, examine the Memory Manager's behavior in real-life situations.develop, the disc, contains the source and object code for the Heap Demo application, which sets up a small heap independent of the main application heap and allows you to manipulate handles and pointers in that environment. If you do these things, you'll be well on the way to mastering the Memory Manager.

HOW THE MEMORY MANAGER ALLOCATES HEAP SPACE

The Memory Manager uses two basic techniques to create space for blocks on the heap: compaction and reservation. It uses compaction to create space for new relocatable blocks, and reservation to create space for new nonrelocatable blocks.

When your application (or the operating system) calls NewHandle to allocate a new relocatable block, the Memory Manager first looks for a large enough space to hold a block of the requested size. If a large enough space is found (and it need not be a perfect fit), the block is allocated. If there is not enough free space to satisfy the request, compaction takes place--relocatable blocks are moved downward (toward low memory) to make space for the new block. As a rule, the Memory Manager allocates new relocatable blocks as low in the heap as possible without compaction. If the heap must be compacted, the Memory Manager begins with the lowest blocks and gradually works its way upward until it has created a large enough free space to accommodate the new relocatable block or until the entire heap has been compacted.

On the other hand, when your application (or the operating system) calls NewPtr to allocate a new nonrelocatable block, the Memory Manager calls ResrvMem to create an empty space at the bottom of the heap for the new nonrelocatable block. This technique is known as reservation (after the call), although you won't find this term anywhere in Inside Macintosh.

The Memory Manager always allocates nonrelocatable blocks as low as possible on the heap, even if it means that other blocks have to be moved. In the case shown in Figure 2, the Memory Manager has to move a relocatable block twice when the user allocates two nonrelocatable blocks. Note that each time the 4KB relocatable block is moved, it leaves a 4KB space behind. This is a result of the way the Memory Manager reserves memory. It first moves the block upward into the first free area above its former position large enough to hold it, then uses the old space for the new block.

Figure 2. The Effect of Allocating Nonrelocatable Blocks

In summary, allocating a new nonrelocatable block is likely to move other (relocatable) blocks upward, while allocating a new relocatable block may cause compaction, which moves relocatable blocks downward.

ABOUT LOCAL AND GLOBAL VARIABLES

While in this article we're primarily interested in information stored on the heap, there are actually three places you can store information in memory: in a relocatable or nonrelocatable block on the heap, in a local variable, or in a global variable. In terms of storage efficiency, relocatable blocks are your best bet. But if you need to store information in an area that will not move, you can use local or global variables.

Local variables are allocated on the machine's stack, and only exist as long as the enclosing procedure is running. Global variables are stored in a special block above the top of the application's stack and heap, and exist as long as the program is running. Both of these areas share one disadvantage: limited space. You can only allocate 32KB of global variables, and the maximum available stack space typically varies between 8KB and 24KB, depending on the machine, the operating system version, and whether or not the application has requested a larger stack when launched.

RICHARD "TIGGER" CLARK wears brightly colored clothes, writes odd graffiti, tells horrible puns, and is amazingly graceful when running for the bus. He earned a BS in social science (which he says is a hybrid psychology/computer science degree) from the University of California-Irvine in 1985. When he's not teaching at Developer U, you can find him stunt-kite flying (sometimes indoors), mountain climbing (sometimes indoors), or collecting Disney memorabilia. An avid reader, he has totally worn out his copy of Winnie the Pooh in Latin. In his time he has been a Valley Boy, a Macintosh repairman, a software developer, King Henry VIII's head steward, a Renaissance bishop, and probably a few other things he won't tell us about. But hey, he's from southern California. *