6 Memory

This chapter helps you understand memory use on Palm OS^®.

• Introduction to Palm OS Memory Use provides information about Palm OS hardware relevant to memory management.
  
  
• Memory Architecture discusses in detail how memory is structured on Palm OS. It also examines the structure of the basic building blocks of Palm OS memory: heaps, chunks, and records.
  
  
• The Memory Manager discusses how to use the Palm OS memory manager in your applications. The memory manager maintains the location and size of each memory chunk in nonvolatile storage, volatile storage, and ROM. It provides functions for allocating chunks, disposing of chunks, resizing chunks, locking and unlocking chunks, and compacting the heap when it becomes fragmented.
  

Introduction to Palm OS Memory Use

The Palm OS system software supports applications on low-cost, low-power, handheld devices. Given these constraints, Palm OS is efficient in its use of both memory and processing resources. This section presents two aspects of Palm OS devices that contribute to this efficiency: Hardware Architecture and PC Connectivity.

Hardware Architecture

The first implementation of Palm OS provides nearly instantaneous response to user input while running on a 16 MHz Motorola^® 68000 type processor with a minimum of 128K of nonvolatile storage memory and 512 KB of ROM. Subsequent Palm OS devices provide additional RAM and ROM in varying amounts.

The ROM and RAM for each Palm OS device resides on a memory module known as a card. Each memory card can contain ROM, RAM, or both. There is no RAM or ROM storage on the motherboard of the device.

Though all previous and current Palm OS devices hold one card in a user-accessible hardware slot, it is unwise to assume that any Palm OS device has a memory module that can be removed physically. A "card" is simply a logical construct used by the operating system--Palm OS devices can have one card, multiple cards, or no cards. For example, the Simulator provided by the Palm OS SDK on Macintosh can simulate a device that has two cards.

The ROM and RAM on each card is divided into one or more heaps of 64K (in the current implementation) or less. All the RAM-based heaps on a memory card are treated as the RAM store, and all the ROM-based heaps are treated as the ROM store. The heaps for a store do not have to be adjacent to each other in address space--they can be scattered throughout the memory space on the card--but they must all reside on the same card.

The main suite of applications provided with each Palm OS device is built into ROM. This design permits the user to replace the operating system and the entire applications suite simply by installing a single replacement module. Additional or replacement applications and system extensions can be loaded into RAM, but doing so is not always practical in this RAM-constrained environment.

PC Connectivity

PC connectivity is an integral component of the Palm OS device. The device comes with a cradle that connects to a desktop PC and with software for the PC that provides "one-button" backup and synchronization of all data on the device with the user's PC.

Because all user data can be backed up on the PC, replacement of the nonvolatile storage area of the Palm OS device becomes a simple matter of installing the new module in place of the old one and resynchronizing with the PC. The format of the user's data in storage RAM can change with a new version of the ROM; the connectivity software on the PC is responsible for translating the data into the correct format when downloading it onto a device with a new ROM.

Memory Architecture

---

IMPORTANT: This section describes the current (3.X) implementation of Palm OS memory architecture. This implementation may change as the Palm OS evolves. Do not rely on implementation-specific information described here; instead, always use the API provided to manipulate memory.

---

The Palm OS system software is designed around a 32-bit architecture. The system uses 32-bit addresses, and its basic data types are 8, 16, and 32 bits long.

The 32-bit addresses available to software provide a total of 4 GB of address space for storing code and data. This address space affords a large growth potential for future revisions of both the hardware and software without affecting the execution model. Although a large memory space is available, Palm OS was designed to work efficiently with small amounts of RAM. For example, the first commercial Palm OS device has less than 1 MB of memory, or .025% of this address space.

The Motorola 68328 processor's 32-bit registers and 32 internal address lines support a 32-bit execution model as well, although the external data bus is only 16 bits wide. This design reduces cost without impacting the software model. The processor's bus controller automatically breaks down 32-bit reads and writes into multiple 16-bit reads and writes externally.

Each memory card in the Palm OS device has 256 MB of address space reserved for it. Memory card 0 starts at address $1000000, memory card 1 starts at address $2000000, and so on.

The Palm OS divides the total available RAM store into two logical areas: dynamic RAM and storage RAM. Dynamic RAM is used as working space for temporary allocations, and is analogous to the RAM installed in a typical desktop system. The remainder of the available RAM on the card is designated as storage RAM and is analogous to disk storage on a typical desktop system.

Because power is always applied to the memory system, both areas of RAM preserve their contents when the device is turned "off" (i.e., is in low-power sleep mode.) See "Palm OS Power Modes" in the chapter "Palm System Features" in this book. All of storage memory is preserved even when the device is reset explicitly. As part of the boot sequence, the system software reinitializes the dynamic area, and leaves the storage area intact.

The entire dynamic area of RAM is used to implement a single heap that provides memory for dynamic allocations. From this dynamic heap, the system provides memory for dynamic data such as global variables, system dynamic allocations (TCP/IP, IrDA, and so on, as applicable), application stacks, temporary memory allocations, and application dynamic allocations (such as those performed when the application calls the MemHandleNew function).

The entire amount of RAM reserved for the dynamic heap is always dedicated to this use, regardless of whether it is actually used for allocations. The size of the dynamic area of RAM on a particular device varies according to the OS version running, the amount of physical RAM available, and the requirements of pre-installed software such as the TCP/IP stack or IrDA stack. Table 6.1 provides more information about the dynamic heap space that currently available combinations of OS and hardware provide.

Table 6.1 Dynamic Heap Space 

RAM Usage	OS 3.5 4 MB TCP/IP & IrDA	OS 3.5 2 MB TCP/IP & IrDA	OS 3.0 > 3.3 > 1 MB TCP/IP & IrDA (Palm III™)	OS 2.0 1 MB TCP/IP only (Professional)-	OS 2.0/1.0 512 KB no TCP/IP or IrDA (Personal)
Total dynamic area	256 KB	128 KB	96 KB	64 KB	32 KB
System Globals (screen buffer, UI globals, database references, etc.)	40 KB (OS)	40 KB (OS)	~2.5 KB	~2.5 KB	~2.5 KB
TCP/IP stack	32 KB	32 KB	32 KB	32 KB	0 KB
System dynamic allocation (IrDA, "Find" window, temporary allocations)	variable	variable	variable amount	~15 KB (no IrDA in this OS)	~15 KB
Application stack (call stack and local vars)	N/A (see note)	N/A (see note)	4 KB (default)	2.5 KB	2.5 KB
Remaining dynamic space (dynamic allocations, application global variables, and static variables)	184 KB	56 KB	36 KB	12 KB	12 KB

The remaining portion of RAM not dedicated to the dynamic heap is configured as one or more storage heaps used to hold nonvolatile user data such as appointments, to do lists, memos, address lists, and so on. An application accesses a storage heap by calling the database manager or resource manager, according to whether it needs to manipulate user data or resources.

---

NOTE:  

Starting with Palm OS 3.5, the dynamic heap is sized based on the amount of memory available to the system.

---

The size and number of storage heaps available on a particular device varies according to the OS version that is running; the amount of physical RAM that is available; and the storage requirements of end-user application software such as the Address List, Date Book, or third-party applications.

Versions 1.0 and 2.0 of Palm OS subdivide storage RAM into multiple storage heaps of 64 KB each. Palm OS 3.X configures all storage RAM on a card as a single storage heap. Under all versions of Palm OS, system overhead limits the maximum usable data storage available in a single chunk to slightly less than 64 KB.

In the Palm OS environment, all data are stored in memory manager chunks. A chunk is an area of contiguous memory between 1 byte and slightly less than 64 KB in size that has been allocated by the Palm OS memory manager. (Because system overhead requirements may vary, an exact figure for the maximum amount of usable data storage for all chunks cannot be specified.) Currently, all Palm OS implementations limit the maximum size of any chunk to slightly less than 64 KB; however, the API does not have this constraint, and it may be relaxed in the future.

Each chunk resides in a heap. Some heaps are ROM-based and contain only nonmovable chunks; some are RAM-based and may contain movable or nonmovable chunks. A RAM-based heap may be a dynamic heap or a storage heap. The Palm OS memory manager allocates memory in the dynamic heap (for dynamic allocations, stacks, global variables, and so on). The Palm OS data manager allocates memory in one or more storage heaps (for nonvolatile user data).

Every memory chunk used to hold storage data (as opposed to memory chunks that store dynamic data) is a record in a database implemented by the Palm OS data manager. In the Palm OS environment, a database is simply a list of memory chunks and associated database header information. Normally, the items in a database share some logical association; for example, a database may hold a collection of all address book entries, all datebook entries, and so on.

A database is analogous to a file in a desktop system. Just as a traditional file system can create, delete, open, and close files, Palm OS applications can create, delete, open, and close databases as necessary. There is no restriction on where the records for a particular database reside as long as they are all on the same memory card. The records from one database can be interspersed with the records from one or more other databases in memory.

Storing data by database fits nicely with the Palm OS memory manager design. Each record in a database is in fact a memory manager chunk. The data manager can use memory manager calls to allocate, delete, and resize database records. All heaps except for the dynamic heap are nonvolatile, so database records can be stored in any heap except the dynamic heap. Because records can be stored anywhere on the memory card, databases can be distributed over multiple discontiguous areas of physical RAM, but all records belonging to a particular database must reside on the same card.

To understand how database records are manipulated, it helps to know something about the way the memory manager allocates and tracks memory chunks, as the next section describes.

Heap Overview

---

IMPORTANT: This section describes the current (3.X) implementation of Palm OS memory architecture. This implementation may change as the Palm OS evolves. Do not rely on implementation-specific information described here; instead, always use the API provided to manipulate memory.

---

Recall that a heap is a contiguous area of memory used to contain and manage one or more smaller chunks of memory. When applications work with memory (allocate, resize, lock, etc.) they usually work with chunks of memory. An application can specify whether to allocate a new chunk of memory in the storage heap or the dynamic heap. The memory manager manages each heap independently and rearranges chunks as necessary to defragment heaps and merge free space.

Heaps in the Palm OS environment are referenced through heap IDs. A heap ID is a unique 16-bit value that the memory manager uses to identify a heap within the Palm OS address space. Heap IDs start at 0 and increment sequentially by units of 1. Values are assigned beginning with the RAM heaps on card 0, continuing with the ROM heaps on card 0, and then continuing through RAM and ROM heaps on subsequent cards. The sequence of heap IDs is continuous; that is, no values in the sequence are skipped.

The first heap (heap 0) on card 0 is the dynamic heap. This heap is reinitialized every time the Palm OS device is reset. When an application quits, the system frees any chunks allocated by that application in the dynamic heap. All other heaps are nonvolatile storage heaps that retain their contents through soft reset cycles.

When a Palm OS device is presented with multiple dynamic heaps, the first heap (heap 0) on card 0 is the active dynamic heap. All other potential dynamic heaps are ignored. For example, it is possible that a future Palm OS device supporting multiple cards might be presented with two cards, each having its own dynamic heap; if so, only the dynamic heap residing on card 0 would be active--the system would not treat any heaps on other cards as dynamic heaps, nor would heap IDs be assigned to these heaps. Subsequent storage heaps would be assigned IDs in sequential order, as always beginning with RAM heaps, followed by ROM heaps.

---

NOTE:  

In Palm OS 3.5, the dynamic heap is sized based on the amount of memory available to the system.

---

Overview of Memory Chunk Structure

Memory chunks can be movable or nonmovable. Applications need to store data in movable chunks whenever feasible, thereby enabling the memory manager to move chunks as necessary to create contiguous free space in memory for allocation requests.

When the memory manager allocates a nonmovable chunk it returns a pointer to that chunk. The pointer is simply that chunk's address in memory. Because the chunk cannot move, its pointer remains valid for the chunk's lifetime; thus, the pointer can be passed "as is" to the caller that requested the allocation.

When the memory manager allocates a moveable chunk, it generates a pointer to that chunk, just as it did for the nonmovable chunk, but it does not return the pointer to the caller. Instead, it stores the pointer to the chunk, called the master chunk pointer, in a master pointer table that is used to track all of the moveable chunks in the heap, and returns a reference to the master chunk pointer. This reference to the master chunk pointer is known as a handle. It is this handle that the memory manager returns to the caller that requested the allocation of a moveable chunk.

Using handles imposes a slight performance penalty over direct pointer access but permits the memory manager to move chunks around in the heap without invalidating any chunk references that an application might have stored away. As long as an application uses handles to reference data, only the master pointer to a chunk needs to be updated by the memory manager when it moves a chunk during defragmentation.

An application typically locks a chunk handle for a short time while it has to read or manipulate the contents of the chunk. The process of locking a chunk tells the memory manager to mark that data chunk as immobile. When an application no longer needs the data chunk, it should unlock the handle immediately to keep heap fragmentation to a minimum.

Note that any handle is good only until the system is reset. When the system resets, it reinitializes all dynamic memory areas and relaunches applications. Therefore, you must not store a handle in a database record or a resource.

Each chunk on a memory card is actually located by means of a card-relative reference called a local ID. A local ID is a reference to a data chunk that the system computes from the base address of the card. The local ID of a nonmovable chunk is simply the offset of the chunk from the base address of the card. The local ID of a movable chunk is the offset of the master pointer to the chunk from the base address of the card, but with the low-order bit set. Since chunks are always aligned on word boundaries, only local IDs of movable chunks have the low-order bit set. Once the base address of the card is determined at runtime, a local ID can be converted quickly to a pointer or handle.

For example, when an application needs the handle to a particular data record, it calls the data manager to retrieve the record by index from the appropriate database. The data manager fetches the local ID of the record out of the database header and uses it to compute the handle to the record. The handle to the record is never actually stored in the database itself.

Although currently available Palm OS devices do not provide hardware support for multiple cards, the use of local IDs provides support in software for future devices that may allow the user to remove or insert memory cards. If the user moves a memory card to a slot having a different base address, the handle to a memory chunk on that card is likely to change, but the local ID associated with that chunk does not change.

The Memory Manager

The Palm OS memory manager is responsible for maintaining the location and size of every memory chunk in nonvolatile storage, volatile storage, and ROM. It provides an API for allocating new chunks, disposing of chunks, resizing chunks, locking and unlocking chunks, and compacting heaps when they become fragmented. Because of the limited RAM and processor resources of the Palm OS device, the memory manager is efficient in its use of processing power and memory.

This section provides background information on the organization of memory in Palm OS and provides an overview of the memory manager API, discussing these topics:

• Memory Manager Structures
  
  
• Using the Memory Manager
  

Memory Manager Structures

This section discusses the different structures the memory manager uses:

• Heap Structures
  
  
• Chunk Structures
  
  
• Local ID Structures
  

Heap Structures

---

IMPORTANT: Expect the heap structure to change in the future. Use the API to work with heaps.

---

A heap consists of the heap header, master pointer table, and the heap chunks.

• Heap header. The heap header is located at the beginning of the heap. It holds the size of the heap and contains flags for the heap that provide certain information to the memory manager; for example, whether the heap is ROM-based.
  
  
• Master pointer table. Following the heap header is a master pointer table. It is used to store 32-bit pointers to movable chunks in the heap.
  
  • When the memory manager moves a chunk to compact the heap, the pointer for that chunk in the master pointer table is updated to the chunk's new location. The handles an application uses to track movable chunks reference the address of the master pointer to the chunk, not the chunk itself. In this way, handles remain valid even after a chunk is moved. The OS compacts the heap automatically when available contiguous space is not sufficient to fulfill an allocation request.
  • If the master pointer table becomes full, another is allocated and its offset is stored in the nextMstrPtrTable field of the previous master pointer table. Any number of master pointer tables can be linked in this way. Because additional master pointer chunks are nonmovable, they are allocated at the end of the heap, according to the guidelines described in the "Heap chunks" section following immediately.
  
  
• Heap chunks. Following the master pointer table are the actual chunks in the heap.
  
  • Movable chunks are generally allocated at the beginning of the heap, and nonmovable chunks at the end of the heap.
  • Nonmovable chunks do not need an entry in the master pointer table since they are never relocated by the memory manager.
  • Applications can easily walk the heap by hopping from chunk to chunk because each chunk header contains the size of the chunk. All free and nonmovable chunks can be found in this manner by checking the flags in each chunk header.

    Because heaps can be ROM-based, there is no information in the header that must be changed when using a heap. Also, ROM-based heaps contain only nonmovable chunks and have a master pointer table with 0 entries.

Chunk Structures

---

IMPORTANT: Expect the chunk structure to change in the future. Use the API to work with chunks.

---

Each chunk begins with an 8-byte header followed by that chunk's data. The chunk header consists of a Flags:size adjustment byte, 3 bytes of size information, a lock:owner byte, and 3 bytes of hOffset information.

• Flags:sizeAdj byte.This byte contains flags in the high nibble and a size adjustment in the low nibble.
  
  • The flags nibble has 1 bit currently defined, which is set for free chunks.
  • The size adjustment nibble can be used to calculate the requested size of the chunk, given the actual size. The requested size is computed by taking the size as stored in the chunk header and subtracting the size of the header and the size adjustment field. The actual size of a chunk is always a multiple of two so that chunks always start on a word boundary.
  
  
• size field (3 bytes). This three-byte value describes the size of the chunk, which is larger than the size requested by the application and includes the size of the chunk header itself. The maximum data size for a chunk is slightly less than 64 KB.
  
  
• Lock:owner byte. Following the size information is a byte that holds the lock count in the high nibble and the owner ID in the low nibble.
  
  • The lock count is incremented every time a chunk is locked and decremented every time a chunk is unlocked. A movable chunk can be locked a maximum of 14 times before being unlocked. Nonmovable chunks always have 15 in the lock field.
  • The owner ID determines the owner of a memory chunk and is set by the memory manager when allocating a new chunk. Owner ID information is useful for debugging and for garbage collection when an application terminates abnormally.
  
  
• hOffset field (3 bytes). The last three bytes in the chunk header is the distance from the master pointer for the chunk to the chunk's header, divided by two. Note that this offset could be a negative value if the master pointer table is at a higher address than the chunk itself. For nonmovable chunks that do not need an entry in the master pointer table, this field is 0.
  

Local ID Structures

---

IMPORTANT: Expect the local ID structure to change in the future. Use the API to work with chunks.

---

Chunks that contain database records or other database information are tracked by the data manager through local IDs. A local ID is card relative and is always valid no matter what memory slot the card resides in. A local ID can be easily converted to a pointer or the handle to a chunk once the base address of the card is known.

The upper 31 bits of a local ID contain the offset of the chunk or master pointer to the chunk from the beginning of the card. The low-order bit is set for local IDs of handles and clear for local IDs of pointers.

The MemLocalIDToGlobal function converts a local ID and card number (either 0 or 1) to a pointer or handle. It looks at the card number and adds the appropriate card base address to convert the local ID to a pointer or handle for that card.

Using the Memory Manager

Use the memory manager API to allocate memory in the dynamic heap (for dynamic allocations, stacks, global variables, and so on) and use the data manager API to allocate memory in one or more storage heaps (for user data). The data manager calls the memory manager as appropriate to perform low-level allocations. (See The Data Manager for more information.)

Overview of the Memory Manager API

To allocate a movable chunk, call MemHandleNew and pass the desired chunk size. Before you can read or write data to this chunk, you must call MemHandleLock to lock it and get a pointer to it. Every time you lock a chunk, its lock count is incremented. You can lock a chunk a maximum of 14 times before an error is returned. (Recall that unmovable chunks hold the value 15 in the lock field.) MemHandleUnlock reverses the effect of MemHandleLock--it decrements the value of the lock field by 1. When the lock count is reduced to 0, the chunk is free to be moved by the memory manager.

When an application allocates memory in the dynamic heap, the memory manager uses an owner ID to associate that chunk with the application. The system further distinguishes chunks belonging to the currently active allocation by setting a special bit in the owner ID information. When the application quits, all chunks in the dynamic heap having this bit set are freed automatically.

If the system needs to allocate a chunk that is not disposed of when an application quits, it changes the chunk's owner ID to 0 by calling the system functions MemHandleSetOwner or MemPtrSetOwner. These functions are not generally used by applications, except in special circumstances. For example, when the current application is passing a parameter block to a new application that it is launching, the owner of the block must be set to the system; otherwise, when the current application exits, the system deletes the block when it frees all memory allocated by the current application.

To determine the size of a movable chunk, pass its handle to MemHandleSize. To resize it, call MemHandleResize. You generally cannot increase the size of a chunk if it's locked unless there happens to be free space in the heap immediately following the chunk. If the chunk is unlocked, the memory manager is allowed to move it to another area of the heap to increase its size.When you no longer need the chunk, call MemHandleFree, which releases the chunk even if it is locked.

If you have a pointer to a locked, movable chunk, you can recover the handle by calling MemPtrRecoverHandle. In fact, all of the MemPtrXxx calls, including MemPtrSize, also work on pointers to locked, movable chunks.

To allocate a nonmovable chunk, call MemPtrNew and pass the desired size of the chunk. This call returns a pointer to the chunk, which can be used directly to read or write to it.

---

NOTE:  

You cannot allocate a zero-size chunk.

---

To determine the size of a nonmovable chunk, call MemPtrSize. To resize it, call MemPtrResize. You generally can't increase the size of a nonmovable chunk unless there is free space in the heap immediately following the chunk. When you no longer need the chunk, call MemPtrFree, which releases the chunk even if it's locked.

Use the memory manager utility routines MemMove and MemSet to move memory from one place to another or to fill memory with a specific value.

In most situations, the proper way to free memory is by calling one of the MemPtrFree or MemHandleFree functions.

---

NOTE:  

For important cautions and practical advice regarding the proper use of memory on Palm OS devices, be sure to read "Writing Robust Code" in the chapter "Good Design Practices" in this book.

---

Storage Heap Sizes and Memory Management Schemes

In Palm OS version 1.0, individual storage heaps were limited to a maximum size of 64 KB each and the memory manager moved objects automatically among multiple storage heaps to prevent any of them from becoming too full. This strategy tended to decrease the availability of contiguous space for large objects. The version 2.0 memory manager abandoned this approach, increasing the availability of contiguous heap space; however, it still limited the maximum size of individual heaps to 64 KB each. Palm OS version 3.X removes the 64 KB maximum size restriction on individual heaps and creates just two heaps: one 96K dynamic heap and one storage heap that is the size of all remaining RAM on the card.

---

NOTE:  

Starting with PalmOS 3.5, the dynamic heap is sized based on the amount of memory available to the system. The size which will be used is as follows:

Device RAM size	Heap size
< 2 mb of ram	64 k
>= 2 mb	128 k
>= 4 mb	256 k

                                                                          

---

Optimizing Memory Manager Performance

Because Palm OS applications must perform well in a RAM-constrained environment, proper code segmentation is critical to achieving optimum performance.

If your application segments are too large, your application may not perform well (or to run at all) when large contiguous blocks of memory are not available. Conversely, if your application segments are too small, performance may be hindered by the overhead required to find and load resources too frequently.

Unfortunately, it impossible to specify a single size for memory chunks that will perform optimally for all applications.You will need to experiment with segmenting your code in different ways while measuring your application's performance in order to discover the size and arrangement of resource chunks that will optimize your particular application's responsiveness and overall performance. The Metrowerks CodeWarrior Debugger, Palm OS Debugger, and the Simulator provide tools for examining the internal structure of heaps, viewing the amount of free space available, manipulating blocks, and so on.

Summary of Memory Management