TweetFollow Us on Twitter

Memman
Volume Number:7
Issue Number:9
Column Tag:Programmer's Forum

Related Info: Memory Manager

A Memory Manager for the Rest of US

By Jordan Zimmerman, Pacific Grove, CA

A Memory Manager for the Rest Of Us: The Evolution of Portable Virtual Memory

[Jordan Zimmerman lives in Burbank, California where he drinks fresh ale, plays Smash T.V. and writes Movie Magic Scheduling for Screenplay Systems, Inc.]

Introduction

Our story begins with a humble Macintosh programmer faced with what is becoming the issue of the 90’s: there are people in the world who insist on having windows on their blue boxes.

I was confronted with the task of reconciling the different memory management schemes of the Macintosh and Windows 3.0. In the process of solving this, a memory management scheme was developed that would be useful regardless of the porting issues. This memory manager automatically handles virtual memory (without the need for System 7 or a PMMU), is portable, and traps a multitude of errors and crashes caused by mistakes in memory usage.

While the full-blown manager is beyond the scope of this article; what follows is an outline that should be all one needs to write such a manager.

At this point, I must give due credit to my co-workers Ken Smith and Mark Guidarelli who helped design our Memory Manager, Memman.

In the Beginning

It has been my experience that the Windows 3 API (Application Programming Interface) is less flexible than the Macintosh’s. A perfect example is the respective memory managers.

While both platforms use the label “Handle” for their basic type of memory, they are really very different animals. On the Mac, a Handle points to a real location in memory. At that location there is another pointer that points to your data. Once the OS returns an allocated Handle, you are free to use it at will - you don’t need to check with the OS before using it (except, of course, to lock it).

Under Windows, the Handle it returns is merely a reference. It doesn’t point to any real memory. In order to get a pointer to real memory, you have to go through an OS call. When you are done using the real memory, you make another call to let the OS know you’re through.

The restrictions of the Windows model didn’t give us a lot of choice. Ultimately, it made a lot more sense to try to fit the Mac model into the Windows model than it did to try it the other way around.

And Then There Was Light

It quickly became apparent how much control the memory manager would have, given the constraints on the user of the manager. I could count on several things:

a) I’d know whenever memory was or wasn’t being used;

b) I’d have knowledge of every allocation made; and

c) I could do whatever I wanted with the data of an allocation when it wasn’t being used so long as I restored its condition before it was needed again.

The Window’s Model

Windows has five basic memory routines. They are:

a) GlobalAlloc() - allocates a block of memory;

b) GlobalReAlloc() - changes the size of an allocation;

c) GlobalLock() - returns a real pointer to memory;

d) GlobalUnLock() - signals that real memory is done being used; and

e) GlobalFree() - disposes of an allocation.

So, it seemed simple enough to fit the Macintosh memory model into Windows’ - just put wrappers around all memory calls.

Memman is born

This is the basic structure of Memman:

/* 1 */

#ifdef windows
typedef cookie_t HANDLE
#elif macintosh
typedef cookie_t Handle
#endif

cookie_t MMAlloc(long size);
void MMRealloc(cookie_t hdl, 
 long new_size);
void *MMUse(cookie_t hdl);
void MMUnuse(cookie_t hdl);
void MMFree(cookie_t hdl);

The cookie_t is what we call around the office a “magic cookie” - a reference to something that is unusable by itself. In Memman, the magic cookie is a Handle on the Macintosh and a HANDLE on Windows. But that doesn’t really matter to the user of the manager.

The Memman model ports perfectly between the two platforms:

MEMMAN Macintosh Windows

-------------------------------------------------

MMAlloc NewHandle GlobalAlloc

MMRealloc SetHandleSize GlobalReAlloc

MMUse HLock GlobalLock

MMUnuse HUnlock GlobalUnLock

MMFree DisposHandle GlobalFree

Memman imposes some constraints on a program that Macintosh programmers won’t be used to.

Before you read to or write from memory, you MUST call MMUse() to get a real pointer to memory. When you are through reading/writing, you MUST call MMUnuse(). This is a very different way of coding. The program becomes a “client” of the Operating System. On the Mac, it’s somewhat the other way around normally.

MMUse() can be unlimitedly nested. However, for every MMUse(), there must be an MMUnuse() eventually.

Here’s an example:

/* 2 */

/* the Mac way of allocating memory and
then writing to it */
. . .
short   **short_array;
short   *short_ptr;

short_array = (short **)NewHandle(10 * 
 sizeof(short);
short_ptr = *short_array;
short_ptr[1] = 1;
short_ptr[2] = 2;
...

/* now, the Memman way */
. . .
cookie_treference;
short   *short_ptr;

reference = MMAlloc(10 * sizeof(short));
short_ptr = (short *)MMUse(reference);
short_ptr[1] = 1;
short_ptr[2] = 2;
/* etc. */
MMUnuse(reference);
. . .

Where’s the VM Beef?

So how does this get us Virtual Memory? Given the control that Memman has over memory allocation and usage, Virtual Memory becomes somewhat simple.

What is Virtual Memory, Anyway?

Virtual Memory is a technique that allows an application to access more memory than is physically present in the system. Data is paged to and from disk as needed, thus giving the appearance of more memory than is really available.

Under System 7, this is done on a hardware level by the Paged Memory Management Unit (PMMU). This is the fastest and most desirable way to implement Virtual Memory. But there is nothing stopping the lowly software programmer from doing it manually.

Today’s operating systems provide sophisticated disk I/O and memory managers. These are all a programmer needs to do Virtual Memory.

Memman knows about every allocation that is made. It also knows whenever an allocation is or isn’t being used. So, the first thing to do is to keep track of every allocation made through MMAlloc().

/* 3 */

typedef longhdl_t;

typedef struct {
 cookie_t platform_hdl;
 long   size;
 void   *ptr;
 short  access_cnt;
} alloc_rec;

Memman keeps an array of alloc_recs. Every time MMAlloc() is called, an entry into this array is stored. platform_hdl is a Handle on the Mac or a HANDLE on Windows. Because there is no equivalent to the Mac’s GetHandleSize() on Windows, size stores the size of the allocation.

Instead of MMAlloc() returning a cookie_t, Memman defines its own “magic cookie”, hdl_t. This is an offset into the array of alloc_recs.

ptr is NULL if the allocation isn’t currently being “used” (i.e. MMUse() hasn’t been called) or a real memory location if it is being used. This is done as an optimization. If MMUse() is called in a nested way, there is no need to go through the OS (HLock() or GlobalLock() ) to get a pointer.

access_cnt is the number of unbalanced times MMUse() has been called for the allocation. This is how Memman determines if an allocation is in use or not. When allocated, the access_cnt is set to zero. Every time MMUse() is called, it is incremented by one. Every time MMUnuse() is called it is decremented by one. When the access_cnt is zero, Memman knows that the allocation is not being used.

It is the knowledge of when an allocation is in use or not that allows us to do VM. When an allocation isn’t in use, its data can be stored on disk (however, you’d probably only want to do this when memory is tight). Let’s change alloc_rec a little.

/* 4 */

typedef longhdl_t;

typedef struct {
 cookie_t platform_hdl;
 long   size;
 void   *ptr;
 short  access_cnt;
 long   location;
} alloc_rec;

Memman uses the location field to determine whether or not an allocation is in memory or on disk. MMUse() is responsible for reading in a paged allocation. If location >= 0, then the allocation’s data is on disk; otherwise, location == -1.

A simple implementation of MMAlloc(), MMUse() and MMUnuse() for the Mac might look like this:

/* 5 */

alloc_rec **alloc_array;

hdl_t MMAlloc(long size)
{

 alloc_rec*alloc_ptr;
 Handle h;
 long   old_size;
 hdl_t  hdl;

 /* get some real memory from the OS */
 h = NewHandle(size);
 if ( MemError() )
 DoError();

 /* add another alloc_rec */
 old_size = GetHandleSize(alloc_array);
 SetHandleSize(alloc_array,old_size + 
 sizeof(alloc_rec));
 if ( MemError() )
 DoError();

 /* get the index into the array */
 hdl = old_size / sizeof(alloc_rec);
 alloc_ptr = (*alloc_array)[hdl];

 /* store away the information */
 alloc_ptr->platform_hdl = h;
 alloc_ptr->size = size;
 alloc_ptr->ptr = NULL;
 alloc_ptr->access_cnt = 0;
 alloc_ptr->location = -1;/* in memory */

 return hdl;

} /* MMAlloc */

void *MMUse(hdl_t hdl)
{

 alloc_rec*alloc_ptr;
 void   *ptr;

 /* hdl is an index into the array of alloc_recs */
 HLock(alloc_array);
 alloc_ptr = (*alloc_array)[hdl];

 /* make sure it’s in memory */
 if ( alloc_ptr->location >= 0 )
 load_from_disk(alloc_ptr);

 /* increment the access_cnt and lock the Handle if necessary */
 if ( ++alloc_ptr->access_cnt > 1 )
 ptr = alloc_ptr->ptr;
 else {
 HLock(alloc_ptr->platform_hdl);
 ptr = *alloc_ptr->platform_hdl;
 }

 HUnlock(alloc_array);

 return ptr;

} /* MMUse */

void MMUnuse(hdl_t hdl)
{

 alloc_rec*alloc_ptr;

 alloc_ptr = (*alloc_array)[hdl];

 if ( --alloc_ptr->access_cnt > 0 )
 return;/* handle is still in use, keep it locked */

 alloc_ptr->ptr = NULL;

 HUnlock(alloc_ptr->platform_hdl);

} /* MMUnuse */

Memman opens a temp file that stores any paged data. Memman defines a function, MMPage(), that is used to page data to disk. This would probably be called from the GrowZone or could be setup to be called automatically by MMAlloc() (if NewHandle() failed).

Here’s a simple implementation of MMPage():

/* 6 */

/* page out “needed” bytes of data */
void MMPage(long needed)
{

 alloc_rec*alloc_ptr;
 long   total = 0;
 long   i;
 long   size;

 size = GetHandleSize(alloc_array);
 HLock(alloc_array);

 alloc_ptr = *alloc_array;

 /* go through all allocations paging them out until total >= needed 
*/
 for ( i = 0; i < size; ++i  ) {
 if ( alloc_ptr->location == -1 ) {
 long   offset;

 offset = get_disk_block(alloc_ptr->size);
 write_data(alloc_ptr->platform_hdl,
 alloc_ptr->size,offset);
 alloc_ptr->location = offset;
 DisposHandle(alloc_ptr->platform_hdl);
 
 if ( (total += alloc_ptr->size) >= needed )
 break;
 }
 }

 HUnlock(alloc_array);

} /* MMPage */

You might consider writing MMPage() so that it pages allocations in a “least recently used” fashion. The way Memman does this is by keeping a field (a short) in the alloc_rec that is incremented every time MMUse() is called on the allocation. Allocations with the smallest “time stamp” are the oldest and are paged first. This reduces the likelihood of a lot of swapping to and from disk because an allocation is paged and then read back in, etc.

Ideally, you’ll keep track of any “free” blocks within your temp file and reuse these (a free block is one to which data was paged and then re-read into memory; thus, the block is no longer being used).

Debugging - The Best Benefit

The final benefit of Memman is the automatic debugging it provides. There are several debugging tools that can be built into this memory model.

The first is inherent in the design: Handles are always locked when they are being used. It is a common plague of the Macintosh that a lot of bugs are caused by unlocked handles. With Memman, this is no longer an issue.

The other tools must be added to the memory manager. The following is a list of things we’ve added to Memman at the office. It is by no means an exhaustive list. It seems we are always finding new debugging code to add. You should surround all your debugging code with

/* 7 */

#ifndef NDEBUG
...
#endif

so that it can be turned off easily for the shipping product.

Overdraft Protection

We’ve changed MMAlloc() so that it always allocates 2 bytes more than requested. These two bytes are then set to some unlikely value like 0x1234. Every time MMUse() or MMUnuse() are called, the last two bytes of the allocation are checked and Memman asserts if the value isn’t 0x1234. This catches those pesky bugs where the program writes past the end of an allocation (at a resolution that even Protected Memory can’t achieve!).

Corruption Police

Our Memman has an extra field (a short) in the alloc_rec. This field is used to store a checksum of the data. A checksum of the allocation’s data is stored at MMUnuse() time when the access_cnt gets set to zero (we use a public domain CRC routine). Whenever MMUse() is called, this checksum is verified and Memman asserts if the checksum doesn’t match. This catches memory corruption errors.

The Enforcers

Whenever MMFree() is called, every byte of the allocation’s data is set to 0xff before DisposHandle() is called. This sets up a condition that will always produce incorrect results if an allocation is accessed after it is disposed.

Whenever MMUnuse() is called and the access_cnt gets set to zero, HandToHand() is called on the allocation to duplicate it. The old Handle has every byte set to 0xff and is then disposed. This is the Memman equivalent of Heap Scrambling.

Conclusion

We are using Memman at our office. It has already proved invaluable in weeding out bugs and cleaning up the way we look at memory allocations. Our Memman has been ported to the Mac, Windows and Unix without a hitch.

Even if porting is not an issue for you, the memory model laid out in this article is valuable for any situation. Indeed, the Memman model, I believe, is ideal for every situation and has become an integral part of all the code that I currently write and plan on writing.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Live Home 3D Pro 3.6.2 - $49.99
Live Home 3D Pro is powerful yet intuitive home design software that lets you build the house of your dreams right on your Mac, iPhone or iPad. It has every feature of Live Home 3D, plus some... Read more
RapidWeaver 8.2 - Create template-based...
RapidWeaver is a next-generation Web design application to help you easily create professional-looking Web sites in minutes. No knowledge of complex code is required, RapidWeaver will take care of... Read more
Opera 60.0.3255.109 - High-performance W...
Opera is a fast and secure browser trusted by millions of users. With the intuitive interface, Speed Dial and visual bookmarks for organizing favorite sites, news feature with fresh, relevant content... Read more
DEVONthink Pro 3.0beta2 - Knowledge base...
DEVONthink Pro is your essential assistant for today's world, where almost everything is digital. From shopping receipts to important research papers, your life often fills your hard drive in the... Read more
Tunnelblick 3.7.9 - GUI for OpenVPN.
Tunnelblick is a free, open source graphic user interface for OpenVPN on OS X. It provides easy control of OpenVPN client and/or server connections. It comes as a ready-to-use application with all... Read more
Carbon Copy Cloner 5.1.9 - Easy-to-use b...
Carbon Copy Cloner backups are better than ordinary backups. Suppose the unthinkable happens while you're under deadline to finish a project: your Mac is unresponsive and all you hear is an ominous,... Read more
Dropbox 73.4.118 - Cloud backup and sync...
Dropbox is an application that creates a special Finder folder that automatically syncs online and between your computers. It allows you to both backup files and keeps them up-to-date between systems... Read more
Postbox 6.1.18 - Powerful and flexible e...
Postbox is a new email application that helps you organize your work life and get stuff done. It has all the elegance and simplicity of Apple Mail, but with more power and flexibility to manage even... Read more
Wireshark 3.0.2 - Network protocol analy...
Wireshark is one of the world's foremost network protocol analyzers, and is the standard in many parts of the industry. It is the continuation of a project that started in 1998. Hundreds of... Read more
BetterTouchTool 2.856 - Customize multi-...
BetterTouchTool adds many new, fully customizable gestures to the Magic Mouse, Multi-Touch MacBook trackpad, and Magic Trackpad. These gestures are customizable: Magic Mouse: Pinch in / out (zoom... Read more

AFK Arena guide - Everything you need to...
Ok, so if you're like me, you've been playing (and sometimes waiting) your way through AFK Arena, only to learn there's a lot more to it than there appears on the surface. There's guilds, a PvP arena, and all sorts of other systems and game modes... | Read more »
Explore an epic fantasy world in MMORPG...
Webzen have just announced the official launch date for its stunning MMORPG ‘MU Origin 2’ which will arrive for iOS and Android on May 28th. It will be the second spinoff from the classic PC-based MU Online, and it looks to further refine the... | Read more »
Solar Explorer: New Dawn guide - Tips an...
Solar Explorer: New Dawn is a lunar lander game that really ratchets the intensity up to 11. With all of the asteroids flying around as you fly around at seemingly breakneck speeds, it can be easy to feel overwhelmed bythe whole thing. | Read more »
The Dalaran Heist - How Hearthstone...
I am someone who wrote Hearthstone off a while ago. It was hard not to try and stick with it. The game has incredible production values and a core of really great talent working on the game continuously to keep it feeling fresh and fun (full... | Read more »
Steam Link App - Everything You Need to...
Steam Link has finally released for iOS! That’s right, you can play your epic backlog of PC games on the go now. Well… sort of. While the Steam Link app was announced seemingly ages ago, it only got actual approval for release last night. Check out... | Read more »
Pre-register now for endless superhero r...
Talking Tom Hero Dash is set to take the ever-popular Talking Tom and Friends franchise in a brand new direction as it opens pre-registration to players worldwide. Not only does it promise to be a beautifully rendered, fast-paced, action-packed... | Read more »
AFK Arena - Guild Wars guide
Ok, so if you're like me, you've been playing (and sometimes waiting) your way through AFK Arena, only to learn there's a lot more to it than there appears on the surface. There's guilds, a PvP arena, and all sorts of other systems and game modes... | Read more »
Superhero-themed Talking Tom Hero Dash i...
One of the exciting releases that we’re looking forward to is Talking Tom Hero Dash, an upcoming superhero-themed runner created by Outfit7. This new game is an action-packed endless runner that takes you on an epic adventure to assemble the... | Read more »
Kingdom Rush Vengeance Update Guide 2 -...
Kingdom Rush: Vengeance just got updated once again to add more content to the game. This addition, called The Frozen Nightmare, adds three new levels, five new enemies, two new heroes, and some new achievements. | Read more »
Save the world with SCIENCE in the upcom...
Previous versions of space colonization game TerraGenesis encouraged you to explore the galaxy and settle its planets. The eagerly-awaited 5.0 update will try to smash them to bits. Yep, with a new "world killers" setting, you can unleash... | Read more »

Price Scanner via MacPrices.net

12″ 1.2GHz MacBooks on sale for $999, $300 of...
Amazon has current-generation 12″ 1.2GHz Retina MacBooks on sale for $300 off Apple’s MSRP. Shipping is free: 12″ 1.2GHz Space Gray MacBook: $999.99 $300 off MSRP 12″ 1.2GHz Silver MacBook: $999.99 $... Read more
Here’s how to save $200 on Apple’s new 8-Core...
Apple has released details of their Education discount associated with the new 2019 15″ 6-Core and 8-Core MacBook Pros. Take $200 off the price of the new 8-Core model (now $2599) and $150 off the 15... Read more
Price drops! 2018 15″ 2.2GHz 6-Core MacBook P...
Amazon has dropped prices on clearance 2018 15″ 2.2GHz 6-Core Touch Bar MacBook Pros by $300 with models now available for $2099. These are the same models sold by Apple in their retail and online... Read more
Apple drops prices on 2018 13″ 2.3GHz Quad-Co...
Apple has dropped prices on Certified Refurbished 2018 13″ 2.3GHz 4-Core Touch Bar MacBook Pros with prices now starting at $1489. Apple’s one-year warranty is included, shipping is free, and each... Read more
Apple drops prices on 2018 Certified Refurbis...
Apple has dropped prices on clearance 2018 15″ 6-Core Touch Bar MacBook Pro, Certified Refurbished, with models available starting at only $1999. Each model features a new outer case, shipping is... Read more
Price drops! Clearance 2018 13″ Quad Core Mac...
Amazon has dropped prices on 2018 13″ Apple Quad-Core MacBook Pros with models now available for $250 off original MSRP. Shipping is free. Select Amazon as the seller, rather than a third-party, to... Read more
How Much Is ‘Solace’ Of Mind Worth When Buyin...
COMMENTARY: 05.22.19- Smartphone cases give us peace of mind by providing ample protection for such a fragile gadget and the sky’s the limit as far as choices go with a plethora of brands, styles,... Read more
Get a 13″ Touch Bar MacBook Pro for the lowes...
Apple has Certified Refurbished 2017 13″ 3.1GHz Dual-Core i5 Touch Bar MacBook Pros available starting at $1439, ranging up to $390 off original MSRP. Each MacBook features a new outer case, shipping... Read more
Apple adds new 15″ 8-Core MacBook Pro to line...
Apple has added a new 15″ MacBook Pro to its lineup featuring a 9th generation 2.3GHz 8-Core Intel i9 processor, 16GB of RAM, a 512GB SSD, and a Radeon Pro 560X with 4GB of GDDR5 memory for $2799.... Read more
21″ 2.3GHz iMac available for $999 at B&H...
B&H Photo has the 2018 21″ 2.3GHz Apple iMac on sale for $100 off MSRP. This is the same model offering by Apple in their retail and online stores. Shipping is free: – 21″ 2.3GHz iMac (MMQA2LL/A... Read more

Jobs Board

Best Buy *Apple* Computing Master - Best Bu...
**690427BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Location Number:** 000860-Charlottesville-Store **Job Description:** **What Read more
*Apple* Mobile Master - Best Buy (United Sta...
**696430BR** **Job Title:** Apple Mobile Master **Job Category:** Store Associates **Location Number:** 001012-Bismarck-Store **Job Description:** **What does a Best Read more
Manager - *Apple* Team - SHI International...
…opportunity available in the Hardware & Advanced Solutions Department as the Manager of the Apple Team The Manager must be familiar with all aspects of Apple Read more
Best Buy *Apple* Computing Master - Best Bu...
**696375BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Location Number:** 000203-North Austin-Store **Job Description:** **What does a Read more
Geek Squad *Apple* Master Consultation Agen...
**696286BR** **Job Title:** Geek Squad Apple Master Consultation Agent **Job Category:** Services/Installation/Repair **Location Number:** 000172-Rivergate-Store Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.