Dr.Dobb's journal.2006.03

(continued from page 20)

fullsize or halfsize frames, and the compression method to be employed. We’ve been using a simple lossless keyframe/deltaframe scheme. In this scheme, no special processing is required for stereo frames because the left and right images are stored as one continuous buffer (top/bottom), and to the compression code, it just looks like one double-height frame. The 24-bit color depth images are first compressed to 5-6-5 16-bits per pixel. Run-length encoded full frames are sent every second to allow clients to synchronize fully after a maximum delay of one second. The remaining video frames (up to a rate of 25 fps) are sent as run-length differences from the last frame. Key features

from the compression routines appear in Listing Eleven (all listings are available electronically).

The Client Program

Like the server, the client is a standard Win32 application. The implementation has much in common with the server so the details can be followed in the comments from the full source codes. A couple of points worth mentioning are the use of a timer to send instructions to the server for it to send video frames and that the client is configured to allow several requests to be in the pipeline at any one time. (This helps to minimize communication delays. The TCP/IP mechanism handles buffering and ensures that frames arrive in the correct order.)

The organization of the double-height image buffer mirrors that of the server. A data acquisition thread is responsible for filling this buffer by receiving compressed video frames from the server and uncompressing them into the image buffer. OpenGL pixel-drawing functions copy the image data from the double-sized image buffer into the left and right off-screen buffers with the glDrawPixels( ) function.

Tools

We built the programs using both Microsoft’s Visual Studio .NET 2003 and Visual Studio 6.0. The Direct X 9.0 SDK is needed. This changes frequently; we used a distribution from 2004, but the dxsdk_feb2005 will do the job, too. You’ll need the dxsdk_feb2005_extras for DirectShow, and it will be necessary to build the libraries from the DirectShow BaseClasses in the Samples\C++ folder and configure your development environment with the appropriate search paths for headers and libraries. The DirectX SDK is available at http://www

.microsoft.com/windows/directx/default

.aspx. Our project code is available electronically from DDJ; see “Resource Center,” page 5.

Trying It Out

To test our setup, we placed the server on top of a tall building and connected it to one node on our campus computer network. The stereo projection equipment in our VR theater is equipped with a highend stereo projector and it was a simple matter to run a client there. Both ends of the pipe were hooked in via 10-MB Ethernet networks separated by at least two router hops.

We ran our programs for several hours and used sources with resolutions of 320× 240 and 640× 480. The lower resolution worked very well up to frame rates of 25 fps, while the higher was quite capable of achieving 15 fps. Our initial fear that we would not be able to provide suitable synchronization between the left and right images proved groundless; with USB 2.0 cameras and the 15 fps, we were able to achieve quite satisfactory results for all the motion video scenarios we investigated.

Conclusion

With a couple of pieces of simple software, two webcams from the local mart, and almost any off-the-shelf PC, you can build a pretty good experimental stereoscopic web TV. The fact that the necessary hardware costs a fraction of what is being spent in big-budget VR projects might, just might, open up access to use virtual reality in applications not previously considered worthy of the cost.

DDJ

22

Dr. Dobb’s Journal, March 2006

http://www.ddj.com

Getting Personal with J2ME’s PIM API

Yes, Java programmers can access a mobile phone’s personal information

TOM THOMPSON

Ever wonder why the PDA market isn’t as large as that of desktop computers? The competition fits neatly into your hand — it’s the mobile phone. Mobile phones can store contact information and an event calendar, just like a PDA. The mobile phone can also do the PDA one better in that when you glance at a contact name, with just the push of a button you can call that person. Or, it can automatically capture a new client’s number if they call your mobile phone. Certainly PDAs can do things that mobile phones can’t, and the PDA’s UI is much easier to use. However, consider that Nokia alone sold its billionth mobile phone last September (with 2 billion mobile phone subscribers worldwide), compared to the tens of millions of PDAs sold, and you can grasp that the phone’s limited address book/calendar capabilities

are quite adequate for many people. However, while this is a fine state for

consumers, the situation drives Java 2 Mobile Edition (J2ME) programmers nuts. That’s because J2ME, the Java platform tailored for portable devices such as mobile phones, doesn’t allow access to the device’s address book. If you wrote a killer app that leveraged this information, and could sell it into a market with, conservatively, tens of millions of customers…

Tom is a technical writer providing support for J2ME wireless technologies at KPI Consulting Inc. He can be contacted at [e-mail].

Not surprisingly, as a mobile phone tech-support person I often get asked if J2ME can access a mobile phone’s address book. Until recently, all I could do was explain that this missing capability was for the sake of security, which is not an idle concern when your mobile phone carries all sorts of personal data on it.

However, I’ve recently had to change my tune. That’s because the Java Community Process (JCP), a consortium of companies that develops standards and new technologies for the Java platform, ratified the final version of Java Specification Request 75 (JSR 75). This specification defines two optional Java packages that implement highly desired PDA functions on the J2ME platform:

•The JSR 75 Personal Information Management (PIM) package provides access to a mobile phone’s address book and calendar.

•The JSR 75 FileConnection (FC) package offers a unified interface to a mobile phone’s filesystem, especially those on removable media.

These specifications are available on the JCP web site (http://www.jcp.org/ en/jsr/detail?id=75). In this article, I focus only on the JSR 75 PIM API.

Because there’s a lag anywhere from 6 months to 18 months between the final ratification of a JSR specification and when the API appears in shipping phones, JSR 75-capable phones have only recently appeared on the market. So, this is as good a time as any to delve into the details of the PIM API.

Overview of the PIM API

The PIM API provides a standard interface to the contact, event, and to-do information in a device’s PIM database. Quite often it acts as the front end to the phone’s native PIM database, although for other portable devices the database could be implemented in Java. Critically, the PIM API was designed to access databases ex-

ternal to the device as well as its internal one. The external PIM database might be stored on a removable memory card, or reside on a remote server in the corporation. If the device has more than one database (perhaps an internal one in nonvolatile memory and the other on a removable card), the PIM implementation automatically uses the default database.

“The PIM API provides a standard interface to the contact, event, and to-do information”

A major problem for any PIM interface is how to get data in/out of the database it manages. The PIM API supports the import/export of PIM information using “virtual cards” that comply with the standardsbased vCard 2.1 and vCalendar 1.0 formats. A vCard carries address book data (contacts), while a vCalendar contains events and to-do data. These formats were developed by the Internet Mail Consortium for the exchange of contact and calendar data among computer systems (http:// www.imc.org/pdi/pdiproddev.html). The PIM API only supports a subset of the data fields these formats describe. This restriction lets mobile phones interoperate with the largest number of disparate platforms.

Both vCard and vCalendar use cleartext encoding that permits data transfers between devices with 7-bit interfaces, limited bandwidth, and short line lengths — making them ideal for wireless communications. This encoding simplifies the

http://www.ddj.com

Dr. Dobb’s Journal, March 2006

23

design of the reader/writer programs that manage the data import/export operations. This in turn significantly reduces the processing overhead of both the reader/writer programs, so portable devices can implement them. Both of these formats support 8-bit data transfers.

The PIM API maintains several distinct objects called “lists”:

•The contact list manages names, addresses, and phone numbers, and serves as an address book.

•The event list handles activities such as appointments, daily tasks, and reminders. These activities are dependent upon a time, date, or time interval (usually for a recurring task or reminder). The event list typically acts as a calendar.

•The to-do list stores activities that a user needs to complete. Because to-dos of-

ten have a time dependency such as a deadline date, the to-do list is often considered an extension of the calendar, even though it is implemented as a separate object with its own fields and methods in the PIM API.

To understand how these lists interface with the native database, I briefly review the J2ME architecture.

Getting Outside of the Box

A J2ME platform consists of a configuration and a profile. A configuration specifies the basic hardware and software required to implement the Java platform on a device, while a profile describes the software required to implement the device’s runtime environment and system services. Other profiles can specify additional hardware and their software support classes.

	PIM
	PIMList	PIMItem
	ContactList	Contact
RepeatRule	EventList	Event
	ToDoList	ToDo
	Interface	Class

Figure 1: The JSR 75 PIM API object hierarchy.

(a)

PIM	Implements the static methods that gather information about
	PIM lists and provides access to them. Also handles the
	import and export of PIM data.
RepeatRule	Describes an Event item’s repeating interval, which is used
	to determine when the associated Event occurs.
FieldEmptyException	Thrown when an attempt is made to access a field that
	doesn’t contain any data values.
FieldFullException	Thrown when an attempt is made to add data to a field when
	all of its data slots are occupied.
PIMException	Thrown when a PIM class generates an error.
UnSupportedFieldException	Thrown when the PIM list element doesn’t support the
	referenced field.

(b)

Contact	Represents one entry in a Contact database.
ContactList	Represents a list that contains Contact items. Also manages
	access to those items supported by the PIM database.
Event	Represents one entry in an Event database.
EventList	Represents an event list that contains Event items. Also
	manages access to those items supported by the PIM
	database.
PIMItem	Defines the core interfaces for accessing an item stored in a
	PIM list.
PIMList	Describes core methods that access and maintain PIM items.
ToDo	Represents one entry in a ToDo database.
ToDoList	Represents a list that contains ToDo items. Also manages
	access to those items supported by the PIM database.

Table 1: (a) Class description; (b) interface description.

For example, a profile might add support for Bluetooth hardware and the Object Exchange (OBEX) protocol to manage file transfers through this wireless interface. A J2ME device has only one configuration layered over the device’s hardware and native OS, while multiple profiles can be layered atop of the configuration to add other capabilities.

For most portable devices, the J2ME platform uses the Connected Limited Device Configuration (CLDC). The connection is assumed to be low bandwidth and intermittent, making the configuration suitable for wireless devices. The most common profile present on mobile devices is the Mobile Information Device Profile (MIDP), which defines a runtime execution environment that provides event queues, a GUI, and additional security. Often you’ll hear the term “MIDlet” used to describe Java applications written for this profile.

Optional packages extend the capabilities of the J2ME platform, such as support for wireless messaging and multimedia. JSR 75 is also an optional package. Many optional packages extend the capabilities of the MIDP, but JSR 75 extends the CLDC. MIDlets can still use these APIs, however.

The PIM API’s capability has important security implications: Personal data that resides outside of the J2ME sandbox security model is no longer sacrosanct. Put another way, an application inside the sandbox can now access information outside of the sandbox, courtesy of the PIM API. To safeguard such data, the PIM API has a security mechanism that implements read-only, write-only, and read/write access controls for the data. In addition, a JSR 75 PIM implementation must respond to any SecurityExceptions its methods throw.

A mobile phone with a MIDP 2.0 profile can extend the PIM API’s security with its trusted code mechanism. One aspect of this scheme is that only trusted code in the form of a digitally signed MIDlet can access any privileged (restricted) APIs. For security, phone vendors often implement the PIM API as a restricted API. As a result, a MIDlet has to be digitally signed by a trusted code authority before it is granted access to the PIM API. This reduces the potential for downloading a spyware MIDlet that reads your personal data and phones it home to a hacker. However, bear in mind that the trusted code security mechanism only safeguards access to the API, and not to the data. If a program glitch inadvertently corrupts the information within the native database, you’re on your own. Therefore, the promise and peril of the PIM API is that while it grants access to the phone’s personal data and

(continued on page 27)

24

Dr. Dobb’s Journal, March 2006

http://www.ddj.com

(continued from page 24)

so offers great potential for application developers, it also opens the door to great mischief.

PIM Classes and Interfaces

Given the wide diversity of the personal data it handles, the PIM API’s object hierarchy is starkly simple. It has six classes, four of which handle exception conditions. The other two classes, PIM and RepeatRule, provide access to the native database or establish a recurring event, respectively. Figure 1 displays the API’s class and interface hierarchy. The four exception-handling classes, FieldEmptyException, FieldFullException, PIMException, and UnSupportFieldException, are not shown in the figure. Table 1 lists these classes and interfaces and provides a summary of their purpose.

Another eight interfaces specify how to access PIM data. The PIM API maintains contact, event, and task information through appropriately named Contact, Event, and ToDo interfaces. Each interface contains items that represent various data entries in the database. You access the data within an item’s object through the fields the interface provides. Each PIM item defines these fields according to their purpose, such as a NAME field for a contact’s name. The PIMItem interface provides access to an item’s data through getter/setter methods that manipulate standard Java data types.

PIMItem is the superclass for the Contact, Event, and ToDo interfaces. These interfaces inherit PIMItem’s core methods, while extending them to handle the unique characteristics of their data. For example, the Event interface defines a pair of methods used to set or retrieve a RepeatRule object, and it has START and END fields that describe the Event’s start and end times.

JSR 75 organizes related PIM items into lists, letting you manage and maintain the PIMItems populating the database. If you need to search through to-do information, then you access the ToDoList. The PIMList interface implements the core functions that create and delete PIMItems. This interface also has methods for organizing the data and examining some of its characteristics. A PIMList also dictates which fields it supports for data storage and retrieval. While a PIMItem specifies all of the possible fields supported by the vCard and vCalendar, it is the corresponding PIMList that determines which fields in the PIMItem the device’s PIM implementation actually supports.

Similar to PIMItem, PIMList is the superclass for the ContactList, EventList, and

ToDoList interfaces. Each of these interfaces provides specialized methods for im-

porting, creating, and removing the PIMItems that they manage.

Using the PIM API

To make use of the PIM API, your MIDlet code first imports the javax.microedition.pim package. Because the JSR 75 PIM API is an optional package, it may not be present on the mobile phone. A prudent programmer should first discover if the package is present. This is done by invoking System.getProperty( ) with a query string of microedition.pim.version. If the package is present, the method returns a version number and you’re set. If the query returns null, the package is absent and you should present a polite message stating such. One gotcha here is that the CLDC lets a J2ME device refuse to load applications that reference classes missing from its implementation. Because the PIM API is an optional extension to the CLDC, the device might not load the MIDlet, rather than give it a chance to run and check for the PIM API’s presence.

Once you’ve confirmed that the PIM API is available, you obtain an instance of PIM to gain access to the phone’s database. Quite often you’ll combine this step with an operation that involves fetching a PIM list, as Listing One (available electronically; see “Resource Center,” page 5) illustrates. Not only does the code get an instance of PIM, but also opens a ContactList with read and write access.

Now that you’ve connected to the database, you’ll search it for any PIMLists it contains. The listPIMLists( ) method returns the names of all PIM lists of the specified type (say, EventList) in a String array. The first name in this array is the default list.

With the list names in hand, the next step is to open the desired list with the openPIMList( ) method. The constants

PIM.CONTACT_LIST, PIM.EVENT_LIST, and

PIM.TODO_LIST determine the type of list this method opens. Or, a list can be referenced by name. If a name isn’t specified, openPIMList( ) opens the default list of the specified type. Listing Two (also available electronically) locates and opens the default PIMLists. The openPIMList( ) method is also where you set the list’s access mode (readonly, writeonly, or read/write). Because you’re working with personal data, it goes without saying that you should code defensively and be prepared to catch any exceptions that occur.

We’re almost ready to work with a particular PIMItem. However, while an item describes all of its fields from the vCard/ vCalendar specifications, recall that the PIM API implementation supports only a subset of them. To confirm support for a particular field, you invoke PIMList’s isSupportedField( ) method, which returns

a Boolean value of true if the field is accessible. In addition, you can consult the device’s technical documentation to verify which fields the PIM implementation supports. Usually, this information is buried in an appendix or implementation notes, but is well worth tracking down to confirm that the target phone permits access to the desired information.

If the requested field is available, use PIMList’s items( ) method to fetch the list’s items. Provide the field name to the

PIMItem’s countValue( ) method to obtain the number of data values stored in it. If countValue( ) returns nonzero, call the appropriate getter/setter methods to read and revise the values. Listing Three (available electronically) shows how to access all of the names in the default Contact list. As a safety feature, none of the changes you make propagate into the native database until you invoke the commit( ) method. The Sun Microsystems Wireless Toolkit (WTK) Version 2.2 provides an excellent demo MIDlet that uses the JSR 75 PIM API to access and update a mobile phone’s database (http://java.sun.com/ products/sjwtoolkit/download-2_2.html).

Last but not least, recall that the PIM API can import and export PIM data. The method fromSerialFormat( ) imports data for one or more PIMItems from an InputStream. The InputStream could be connected to another mobile device, or over the air to a corporate mainframe. The method toSerialFormat( ) writes one PIMItem to an OutputStream. Listing Four (also available electronically) shows how Contacts can be read from a resource containing vCards to populate a ContactList, and then commit the new information into the native database. I’ve written a simple demo MIDlet (also available electronically) that imports various PIM items and displays them.

Conclusion

The JSR 75 PIM API offers a standard way to access the database on many mobile phones. This capability lets J2ME developers enhance many existing applications. For example, a wireless messaging application that formerly had to maintain its own list of contacts and electronic addresses can now access the phone’s native database for this information. This makes for a smaller (no separate contact list code required) and more robust application (the contact information comes from a reliable native database). In addition, the PIM API offers the means to develop a new breed of person-savvy applications. What might those be? Only time — and the ingenuity of J2ME programmers — will tell.

DDJ

http://www.ddj.com

Dr. Dobb’s Journal, March 2006

27

Keeping C/C++

Code Scalable

Techniques for identifying committed virtual address space

KIRK J. KRAUSS

Many of today’s 32-bit application programs are becoming limited by the amount of available virtual memory on 32-bit platforms. For

those of us who must maintain 32-bit versions of our software, even as we begin to focus on 64-bit platforms, we need ways to ensure that both versions of our code remain scalable.

Current memory profiling tools can help determine what’s happening when peak memory usage occurs. But the focus of such tools is on allocated memory blocks, rather than total committed virtual address space. These two metrics don’t necessarily have a direct correlation. Factors such as leaks, fragmentation, intrablock waste, and overly delayed deallocation can cause virtual memory to be unnecessarily committed. Runtime analysis tools such as IBM’s Rational Purify or Parasoft’s Inuse can pro-

Kirk is a software developer working in the Rational Software division of IBM. He can be contacted at [e-mail].

vide descriptions of memory leaks and memory in use. This can be informative, but a particular memory block may or may not affect the virtual memory footprint. Even a small block in a fragmented heap memory range can directly contribute to the virtual memory footprint. On the other hand, any blocks — even leaked ones — in a range that is mostly getting active use will not make a difference to the virtual memory footprint unless there’s a chance that every useful block in that range could get relocated to a more compacted range. That is something likely to occur in Java/managed applications during garbage collection, but it’s highly unlikely for most native C/C++ applications, where memory blocks remain indefinitely in their original positions in the virtual address space.

For native code, the actual problem of unnecessary virtual memory use can be more relevant than the theoretical problem of missed cleanup of memory blocks that are no longer in use. That missed cleanup may cause wasteful virtual memory overhead, or it may not. It all depends on whether the heap manager must commit more virtual memory to sustain the waste. A few small unused blocks generally will not cause unnecessary heap spread. Rather than leave you to guess which and how many wasted blocks cause the heap to spread, I present in this article ways for you to determine what is meaningful waste. By adding checks for missed opportunities to shrink each heap when it contains memory blocks that are

no longer being accessed, you can identify the needed memory block cleanup that makes the most difference in your program’s virtual memory requirements.

“Memory block tracking can be done via a custom memory allocator function”

To figure out which heap memory blocks to focus on, you need to build your program with some additional code that tracks heap memory ranges and allocated memory blocks. A special build, with conditional compilation of this extra code, is probably the best way to go.

To get this done, you need to write a custom memory allocation routine that keeps track of each memory block, a custom deallocation routine, and routines that keep track of where the heap resides within the virtual address space using the

28

Dr. Dobb’s Journal, March 2006

http://www.ddj.com

(continued from page 28)

algorithms in Listings One and Two. You also need custom accessor functions to tag memory blocks when they’re accessed for use in determining when an opportunity to shrink the virtual memory footprint could have been taken sooner. All of this can be done without adding a great deal of memory overhead. On the other hand, the performance impact can be significant enough that if your program uses lots of heap memory, this technique should probably be applied only for relatively short runs.

Tracking

Heap Memory Blocks

Memory block tracking can be done via a custom memory allocator function. This function first calls an ordinary memory allocation function; for example, C programs typically call malloc( ). Right afterwards, your custom memory allocator invokes a routine that does several things:

•Tracks the newly allocated memory block in a list of currently allocated blocks.

•Determines whether the system has committed virtual memory to accommodate the block.

•If virtual memory has been committed, tracks the updated heap range containing that block, and updates the aforementioned list of that heap’s memory blocks to indicate that none of them has been accessed since this time.

You also need custom deallocator/ reallocator functions that jointly keep your list of memory blocks updated with the addresses and sizes of all the memory blocks in use by your program. Your list of tracked heap memory blocks should contain structures with these fields:

•The memory block’s base address.

•Its size.

•A Boolean value indicating whether the block has been accessed since the last time virtual memory was committed for the heap.

When a memory block has been deallocated, the custom deallocator code invokes a routine that does the following:

•Reports if the memory block’s tracking element indicates that the block hasn’t been accessed since the last time the heap spread.

•Deletes that block’s tracking element from the list.

•Determines whether the system has decommitted the virtual memory containing that block.

•If virtual memory has been decommitted, updates heap range tracking to reflect only the remaining ranges of the heap.

When a memory block has been reallocated, your custom reallocator code may invoke both of the routines just outlined: First, the routine that updates memory block tracking after deallocation because the reallocated block may no longer be in the same position; and second, the routine that updates memory block tracking after allocation to track the new base address and size of the reallocated block. As an alternative, you can add a check for whether the reallocated block has moved. If it hasn’t moved, you can simply update the memory block tracking list to indicate that the size of the tracked block has changed. But if it has grown while remaining at the same base address, you still need the check for heap spread, along with the same follow-up logic I’ve just outlined for typical allocation scenarios.

Tracking the Heap Itself

Heap range tracking depends on making system calls to determine whether virtual

30

Dr. Dobb’s Journal, March 2006

http://www.ddj.com

memory has been committed or decommitted when memory blocks are allocated and deallocated, respectively. This lets you keep a list of tracked heap memory ranges, so you can know exactly where heaps reside in the virtual address space at any point during the run. Your list of tracked heap memory ranges should contain structures with these fields:

•The range’s base address.

•Its size.

On Microsoft Windows, these values can be determined by calling HeapWalk( ) and storing the results in a list. HeapWalk( ) is such an expensive function that you want your program to invoke it only as necessary, and not whenever memory is allocated and deallocated. That’s why you need to consider fast ways to determine whether virtual memory is committed. One way to do this, again on Windows, is to use the IsBadReadPointer( ) function. When a memory block has been deallocated, you can call this function to quickly determine whether the virtual memory that contained the block has been decommitted. An alternative that may work on multiple platforms is to try to access the virtual memory that contained the block and to catch an access exception if one occurs. Only then do you need to make more expensive calls, such as HeapWalk( ) calls on Windows, to determine where the remaining nearby committed heap ranges are.

Your list of tracked heap memory ranges will be populated via an algorithm that detects when heap memory is committed, outlined in Listing One. Again, when your program allocates a memory block, your custom allocator code can track that memory block. It can also invoke the algorithm in Listing One to update tracking for the ranges of the heap containing that memory block. If allocation of a memory block causes additional virtual memory to be committed, this will be clear from the fact that the virtual memory occupied by that block was previously free or perhaps used for some other purpose before. In either case, you’ll want to update your heap range tracking list, conditionally, as outlined in Listing One:

•If you’re already tracking the base of that committed range, then you only need to update the size of the range to indicate its new upper limit.

•Otherwise, you have a new heap memory range to track.

These conditions are only reached if a new memory block appears in a range that was not previously tracked as a heap

range. This judicious use of system calls can help you to efficiently track heap memory ranges.

When your program deallocates a memory block, your custom deallocator code can invoke the algorithm outlined in Listing Two. This algorithm first determines whether the deallocated memory was associated with a tracked range of heap memory. If you find that this condition is often true, you may want to validate your implementation of the algorithm outlined in Listing One. Next, there is a check for whether the space that was occupied by the deallocated block is still committed. If so, this indicates that the virtual memory footprint hasn’t changed even though the memory block was deallocated. Otherwise,

your code should make system calls as described toward the end of Listing Two — for example, to HeapWalk( ) on Windows — to ensure that tracking for that heap is up to date now that the virtual memory that contained the heap memory block has been decommitted.

If virtual memory has been decommitted, then you should check the range that used to contain the most recently deallocated heap memory block to find out whether any of that range is still committed. Any committed portion of that range should still be a heap memory range, particularly if it contains memory blocks tracked on your memory block list; you can validate that for extra accuracy. Then you can do the following, as in Listing Two:

http://www.ddj.com

Dr. Dobb’s Journal, March 2006

31

•If any portion of the tracked heap memory range is still committed, update your tracking for that range.

•Otherwise, delete the list element that tracks the range.

It’s possible that a heap memory range could be broken into multiple ranges if a portion of it, in the middle, is decommitted. You can check for this by walking through the old tracked range to find out which portions of that range are still committed, before you quit tracking the old range altogether.

Your program may use multiple heaps. On Windows, this happens if you call HeapCreate( ) and then specify the returned handle in subsequent calls to

HeapAlloc( ), HeapReAlloc( ), and HeapFree( ). It also happens on Windows if you load multiple instances of the C Runtime DLL, each of which uses its own heap. You have the choice of tracking multiple heaps in separate lists, and you can track their memory blocks in separate lists, too. An advantage of doing so is that list lookups may be faster. Another advantage is that when a heap is destroyed, you can clean up all of the tracking for it with confidence. But this will require that you add code that runs when a heap is created and destroyed, to re-

spectively set up and eliminate the appropriate lists. Otherwise, you can just manage one list of heap memory blocks,

“When virtual memory is committed for a heap, your custom allocator code should ‘untag’ all of the memory blocks in

that heap”

and one list of heap ranges, both of which can be established at the beginning of the run.

The algorithms I described in “Range Tracking & Comparison Algorithms” (DDJ, February 2006) may be useful in

heap range tracking. That article presents an algorithm for creating a list of ranges, in which contiguous committed heap regions might be treated as a single combined range. When multiple ranges need to be updated, you can use an algorithm for splicing a new list of ranges into an existing list. A third algorithm describes a way to compare an old list of ranges with a new one. When ranges of virtual heap memory have been decommitted, you can use that algorithm to compare the decommitted ranges with your list of tracked memory blocks to identify any tracked blocks that no longer exist.

Some professional runtime analysis tools perform tracking of allocated memory blocks and heap ranges, much like the custom allocator and deallocator described here. A professional tool can go further by tracking the underlying virtual memory regions as well, using that tracked information to make this and other higher level tracking reliable enough for accurate runtime error detection. But the scheme described here is sufficient to help you understand where opportunities may be found to decrease the virtual memory overhead created by the heap memory blocks that your program can control.

32

Dr. Dobb’s Journal, March 2006

http://www.ddj.com

Finding Useful Cleanup Opportunities

To use all this tracked information to pinpoint the heap memory blocks that are contributing the most to unnecessary virtual memory bloat, you will additionally record memory accesses, tagging the appropriate memory block tracking structure whenever your program reads from or writes to heap memory. Finding all the places where your code reads from and writes to memory will be simplest if your heap memory blocks are routinely accessed via accessor functions. In your conditionally compiled build, these accessors can look up the memory block to be accessed on your list of memory blocks and tag it by setting the Boolean flag described previously.

When virtual memory is committed for a heap, your custom allocator code should “untag” all of the memory blocks in that heap. They’ll subsequently be retagged, one by one, as your program accesses them. When an untagged block is deallocated and virtual memory is decommitted as a result, your custom deallocator routine can report the opportunity to keep the virtual memory footprint smaller by deallocating the block sooner.

You can also arrange to run occasional scans through a heap’s memory blocks, perhaps each time that virtual memory is committed for that heap. If a block remains untagged through multiple scans (that is, for sort of a long time), the virtual memory range containing that block may be subject to inspection by checking the number of tracked blocks in that range. If that block, or a set of similarly neglected blocks, is solely responsible for the commitment of virtual memory, then you may have found an opportunity to reduce the program’s virtual memory requirement by deallocating or relocating those blocks.

You may have to be pretty diligent to implement all of the memory block and heap range tracking code described here. And performance while all of this tracking is in place will be slow, particularly because of the list lookups at each heap memory access. The list lookup time can be reduced via fast list lookup schemes involving binary searches, skiplists, or the like. And as I mentioned earlier, you might be able to speed things up by using separate lists for tracking multiple heaps. If your program uses lots of heap memory blocks, your patience may pay off when you find ways to eliminate extra virtual memory overhead.

DDJ

(Listings begin on page 34.)

http://www.ddj.com

Dr. Dobb’s Journal, March 2006

33

Listing One

/* The Track Heap Commitment algorithm		*/
/* Determines whether the specified memory range,		*/
/* corresponding to a recently allocated heap memory block,		*/
/* resides completely within the tracked committed regions of */
/* the heap.	Tracks new heap ranges in a list.	*/
/* The caller should ascertain that the specified address		*/
/* actually belongs to a heap: in other words, that it is		*/
/* from a heap operation on a specific heap, or it is from a		*/
/* local or C runtime allocation and is therefore on the		*/
/* default local or C runtime heap.		*/
/* Input parameters */
ADDRESS	triggerAddr
SIZE	triggerSize
LIST	a list of tracked heap ranges
IF (the virtual memory at triggerAddr is tracked on the list
as part of a heap range)
DO
IF (triggerAddr + triggerSize >
(the tracked upper boundary of that heap range))
DO
/* An existing heap range has spread.		*/
make system call(s) to determine the base and extent of
the newly committed range that contains the addresses
from triggerAddr to (triggerAddr + triggerSize)
update the size of the tracked heap range to indicate
its new upper limit
END
END
ELSE DO
/* There is a new heap range at triggerAddr.		*/
make system call(s) to determine the base and extent of the
newly committed range that contains the addresses from
triggerAddr to (triggerAddr + triggerSize)
track the new committed range in the list of heap ranges
END

Listing Two

/* The Track Heap Decommitment algorithm	*/
/*	*/
/* Determines whether the specified memory range,	*/
/* corresponding to a recently deallocated heap memory block, */
/* has evidently become decommitted. Cleans up tracking of	*/
/* decommitted heap ranges.	*/

/* Input parameters */
ADDRESS	triggerAddr
SIZE	triggerSize
LIST	a list of tracked heap ranges
/* Local variables */
ADDRESS	origRangeBase
SIZE	origRangeSize
BOOL	bFoundChange
bFoundChange = FALSE
IF (the virtual memory at triggerAddr is not tracked on the
heap range list as part of a heap range)
DO
/* Looks like we already know about this decommitment. */
END
ELSE IF (an access exception occurs when memory at triggerAddr
DO	is read)
bFoundChange = TRUE
END
IF (bFoundChange) DO
/* The set of virtual memory ranges occupied by the heap		*/
/* has changed to decommit space formerly occupied by		*/
/* memory blocks.		*/
/*		*/
make system calls to determine the bases and extents of the
tracked committed heap ranges in the immediate vicinity of
the decommitted range that includes the addresses from
triggerAddr to (triggerAddr + triggerSize)
/* Update heap range tracking to reflect only the		*/
/* remaining committed ranges.		*/
/*		*/
IF (any portion of the tracked heap range that contained the
	block at TriggerAddr is still committed)
	DO
	update the heap range list to track just the portion(s)
	of that range that remain committed
ELSE	END
	DO
	delete the list element that tracks the range
END	END

DDJ

34

Dr. Dobb’s Journal, March 2006

http://www.ddj.com