TweetFollow Us on Twitter

June 96 - KON & BAL's Puzzle Page: New World Order

KON & BAL's Puzzle Page: New World Order

CAMERON ESFAHANI and ALEX ROSENBERG

See if you can solve this programming puzzle, presented in the form of a dialog between Cameron Esfahani (cam) and Alex Rosenberg. The dialog gives clues to help you. Keep guessing until you're done; your score is the number to the left of the clue that gave you the correct answer. Even if you never run into the particular problems being solved here, you'll learn some valuable debugging techniques that will help you solve your own programming conundrums. And you'll also learn interesting Macintosh trivia.

Alex Hey cam, Marathon crashed in a weird manner when I tried to play it under an early version of Mac OS 8.

cam Working hard, eh? I suppose you'll tell me this was compatibility testing.

Alex Yeah, well, it makes a good demo.

cam Hey, wait a minute! If it's an early version of Mac OS 8, Puzzle Page readers won't ever find this bug, and they'll write nasty letters to the editor about it.

Alex Well, they should know that they'll learn some valuable debugging techniques that they can apply to their own programming conundrums. Don't they read the intro to the Puzzle Page?

cam I guess not. Anyway, back to your problem. So, in what way does it fail?

Alex Just after launch, the machine freezes. This happens every time; it's 100% reproducible. I can't seem to get into MacsBug.

cam Philistine! We use the one true debugger, the Macintosh Debugger for PowerPC. Mac OS 8 debugging is generally done from a second machine over a serial cable. You're probably frozen because the program has crashed and the debugger has halted the machine, waiting to start a debugging session.

Alex What? I thought I gave that up with my Lisa. This is a Macintosh, after all.

cam Kernel-based operating systems are typically developed with two-machine debuggers. Besides, think of the wonderful third-party opportunity!

Alex Um, yeah. Anyway, you've hooked up the serial cable and are running the debugger on the second machine. After watching a progress bar for a while, you see a dialog that says "Access Fault."

cam An access fault is caused by an attempt to access an illegal address. The PC is at the instruction that caused the fault.

Alex There's a Show PC command in the debugger's Extras menu. It puts me at 0x626FDE50.

cam Right. We need to isolate whether this fault occurred in application code or in the system. Choose Show Fragment Info from the Views menu and type that address into it.

Alex I can't type anything; the machine is crashed. Oh, I get it: I have to keep switching my head back and forth between machines like a spectator at a tennis match. What fun. So, how long does this barber pole thingy spin for, anyway? Hey look, the Fragment Info window highlighted the Marathon code fragment. The PC is in Marathon's code.

cam What does the code around the PC look like?

Alex It looks like this:

   626FDE34   mflr       r0
626FDE38 stw r0,0x0008(SP)
626FDE3C stwu SP,-0x0038(SP)
626FDE40 lwz r4,0x0000(r3)
626FDE44 lha r3,0x0000(r4)
626FDE48 bl _eGetDCtlEntry
626FDE4C lwz RTOC,0x0014(SP)
626FDE50 lwz r12,0x0000(r3)
626FDE54 lbz r3,0x0028(r12)
626FDE58 extsb r3,r3
626FDE5C lwz r0,0x0040(SP)
626FDE60 addic SP,SP,56
626FDE64 mtlr r0
626FDE68 blr

R3 is the return value from the function call to _eGetDCtlEntry and apparently contained a bad address.

cam Choose Show Registers from the Views menu. This will show all the registers of the current process.

Alex It looks like the return value for _eGetDCtlEntry was 0. The lwz instruction is dereferencing R3 and putting the result in R12.

cam If you select the R12 register and choose Show Memory from the Views menu, you can see the memory at that address.

Alex That entire area of memory is full of 0xEEEEEEEE's.

cam That's unmapped memory. Is _eGetDCtlEntry the internal name of the routine GetDCtlEntry?

Alex Yes, the debugger is able to pick up that name by using a "trace-back table," which is the PowerPC equivalent of MacsBug symbols. I guess the next step would be to figure out why GetDCtlEntry is returning nil. What is it supposed to be doing?

cam According to Inside Macintosh: Devices, GetDCtlEntry returns the device control entry for the device specified by the value passed in refNum.

If we look at the rest of the code in this function, right before we call GetDCtlEntry, we seem to be getting the refNum from the first 16 bits of some "handle" (or some other kind of pointer to a pointer), which is getting passed into this function.

Alex All right, but we're going to have to restart. Any information passed into this function has been lost because we're after the call to GetDCtlEntry.

cam To restart we'll need to remember the offset into the Marathon fragment where the fault will occur, because the Marathon fragment could be loaded in a different address range.

Alex The offset can be calculated by subtracting the faulting address from the beginning address for the fragment, which was shown in the Fragment Info window. For this address, the offset is 0x4832C.

cam Right, but we'd like to get control a little before the actual crash. The offset to the beginning of that function is 0x48310. Restart the system, and hold down the Control key when you relaunch Marathon. On a debugging system, this will break into the debugger after it has completely loaded the application but just before it begins to execute it.

Alex All right. The machine seems to have stopped at that point. The new start of the Marathon code fragment is 0x6337D6A0. Adding in the offset of 0x48310, we get an address of 0x633C59B0.

cam Bring up the Show Instructions window and enter 0x633C59B0 as the address. It will be exactly the same code as what we saw before. Set a breakpoint at the first instruction in this function -- the mflr instruction -- and run.

Alex We've reached that breakpoint.

cam Do a stack crawl and see who called us. Head over to the ever useful Views menu; there's a Show Stack Crawl command.

Alex All right. Apparently the caller is address 0x633988E0.

cam OK, let's step through this function and see what they end up passing to GetDCtlEntry for the refNum.

Alex It looks like they're passing in 0 for the refNum.

cam Well, there's your problem: 0 is not a valid refNum. It seems that they're getting an invalid refNum from some part of the system and passing that to GetDCtlEntry. GetDCtlEntry is returning nil and we're crashing by dereferencing nil.

Alex Uh, that's great, but I still can't play Marathon.

cam Where does the caller of this function, 0x633988E0, get the "handle" from?

Alex I'll bring up an instruction window at that address:

63398778 mflr r0

...

633987B0 lwz r24,-0x0218(RTOC)

...

633988D8 lwz r3,0x0000(r24)

633988DC addic r3,r3,0x001C

633988E0 bl $+0x2D340 ; 0x633C5C20

633988E4 nop

633988E8 stw r3,0x0000(r30)

R3 seems to be loaded from a global. Let's figure out where this global gets initialized. The "handle" lives inside a structure that's pointed to by the global at -0x218(RTOC). This pointer has the "handle" stored at offset 0x1C within it.

cam We could try to track down where the field at offset 0x1C gets initialized. A pointer wouldn't move around, so we wouldn't have to worry about relocation. We can use the Data Breakpoint window feature of the Macintosh Debugger. The PowerPC 601 has a special register that allows you to stop execution whenever a specified address is read or written to. It's like hardware support for our old friend step spy.

Alex Sounds like a plan. So, I bring up the Data Breakpoint window and will break whenever someone writes to that address.

cam Of course, you realize that just as the code fragment could be loaded in a different place each time it's launched, the RTOC could have a different value as well.

Alex Good point. I'll be sure to use the new RTOC value when I restart Marathon.

cam What happens after we set up the data breakpoint?

Alex It's kind of strange. We seem to be stopping a lot, but people aren't writing to offset 0x1C in this structure; they seem to be writing 32 bits to offset 0x1A and overwriting 0x1C.

cam I don't understand. The routine that called the crashing routine was passing in a value at offset 0x1C.

Alex Apparently we calculated something wrong.

cam I don't know where we could have gone wrong. Wait a second. Look at address 0x633988E0; it says we're branching to address 0x633C5C20, but the routine we're crashing in is at 0x633C59B0.

Alex Well, maybe it's just a call to a different code fragment, a "cross-TOC" call, and it has to use some indirection to get to the crashing function.

cam No, it can't be a cross-TOC call, for two reasons: first, there's no TOC reload after the function call, and second, the routine we crashed in is in the Marathon fragment. You saw the Fragment Info results.

Alex I'll buy that. Now let's set our breakpoint just before this function call to the unknown address. We can step through that code.

cam All right. After we hit the breakpoint, step into that function.

45 Alex Holy cow! It's some totally different piece of code.

cam Look through the instruction disassembly of this new routine. Is there anywhere in there where they call the crashing function?

633C5C98 bl 0x6337E150

633C5C9C lwz RTOC,0x0014(SP)

633C5CA0 ori r31,r3,0x0000

...

633C5CDC ori r3,r31,0x0000

* 633C5CE0 bl 0x633C59B0

Alex Yeah. At address 0x633C5CE0, they call our crashing function with a parameter obtained from R31. Working further back in the instruction disassembly, we see that a function call is made and the result of that is put in R31. This occurs at 0x633C5C98. It calls a routine at address 0x6337E150.

cam And looking at that, it appears to be a cross-TOC call. I restart Marathon and step into the routine at 0x6337E150.

Alex It appears to be cross-TOC glue:

6337E150 lwz r12,-0x0A90(RTOC)

6337E154 stw RTOC,0x0014(SP)

6337E158 lwz r0,0x0000(r12)

6337E15C lwz RTOC,0x0004(r12)

6337E160 mtctr r0

6337E164 bctr

cam So apparently Marathon is calling another library to get this mystical "handle."

Alex Yep. Whenever you're going to go from one library context to another, you need to save and restore the TOC. That's one of the things this glue code does. As you can see, R12 is loaded from -0x0A90(RTOC). R12 will contain a pointer to a transition vector, which contains an address of a routine and a new TOC value. The transition vector is imported from the library we're linking against.

cam So we should be able to plop the transition vector address into the Fragment Info window and figure out which library that comes from, right?

Alex Good idea. Dumping the address at -0x0A90(RTOC) we get the following:

0200CC0C: 01FC9D98 01FC9DA4 01FC9DB0 01FC9DBC

0200CC1C: 01FC9DE0 01FC9DEC 01FC9D80 01FC9D74

...

cam I use the Fragment Info window to find out which fragment contains the address 0x01FC9D98.

Alex It seems to live in the QuickDraw data section, which makes sense, since a transition vector is data.

cam Aha! QuickDraw! That figures. And you wondered why they call it KON & BAL's Puzzle Page. I use the Show Exports button in the Fragment Info window to list all of the exports of the QuickDraw library.

Alex I was wondering when we were going to use that button. You end up getting a long list of all the routines exported by QuickDraw, sorted alphabetically.

cam But I have an address I want to match. If you click on the Address column title, that list will get resorted by address. I search through the list for address 0x01FC9D98.

Alex That address is the address of the GetDeviceList transition vector.

cam That makes sense. This "handle" we've been worrying about has a refNum in the first 16 bits of the structure, and a GDHandle has the refNum of the associated driver stored in the first field in the structure. I bring up a memory window and examine the device list stored in low memory to see if the gdRefNum is 0.

Alex It is. Who's responsible for initializing the GDevice record?

cam NewGDevice and InitGDevice. NewGDevice will pass the refNum to InitGDevice. Let's disassemble the code for NewGDevice.

Alex Apparently it does a NewHandleClear to allocate the GDHandle, and never initializes the refNum.

cam Whoops. Ah, the joys of pre-alpha software. Well, it should be reasonably easy to get one of the QuickDraw engineers to fix this bug. I install a fixed version of the QuickDraw shared library. We should be rockin' now!

Alex Not so fast! When I restart Marathon, I crash. If I do a stack crawl and examine the code, I seem to be crashing in exactly the same place. GetDCtlEntry still seems to return nil.

cam Just another day at the salt mines. OK, it's time to step through GetDCtlEntry. I put a breakpoint just before we call it.

Alex The refNum from the GDHandle is -51.

cam That looks like a valid refNum. Step into GetDCtlEntry.

Alex We first go through the cross-TOC glue and eventually get into GetDCtlEntry.

cam What does GetDCtlEntry look like?

Alex It seems fine, but when you step through the routine and actually fetch the DCtlHandle from the unit table, it ends up being nil.

...

626FC79C cntlzw r3,r3

626FC7A0 srwi r3,r3,5

...

cam That obviously shouldn't happen. There's a driver entry in the table and the refNum seems valid. What is the code at 0x626FC79C doing?

Alex It's performing a logical NOT operation on R3. Groovy, huh?

cam But the bitwise NOT of the refNum should be used as the index into the unit table, not the logical NOT!

Alex So, you claim that GetDCtlEntry is looking at the wrong place in the unit table to get the DCtlHandle. Are you sure?

cam Let's go to the source. What does Inside Macintosh: Devices say?

Alex It says, "The device reference number is the one's complement (logical NOT) of the unit number." But the logical NOT isn't the one's complement; the bitwise NOT is.

cam Um, OK, what does Inside Macintosh Volume II say?

Alex It claims that the unit number is "equal to -1 * (refNum + 1)."

cam And that's a bitwise NOT. So it seems that Inside Macintosh: Devices is wrong. Weird, wacky stuff. But I still don't understand why the stack crawl we did earlier pointed us to the wrong place.

Alex We did the stack crawl when we had just entered the crashing function, even before it executed the mflr instruction. The debugger, when it does a stack crawl, is going to look for stack frames to see where the callers are. Since we hadn't allocated a stack frame in the crashing function yet, we were still using the caller's stack frame. So that was the stack frame the debugger started from. If we had stepped a few more instructions in and allocated our stack frame, the debugger would have figured it out. It would be interesting to see if the debugger could actually detect the case of a nonexistent stack frame and use the link register to work back to the caller.

cam That also explains why the data breakpoint stuff didn't work. We thought that the data structure we were watching held the GDHandle. It didn't; it contained something totally unrelated, which was passed into the function that called the crashing routine.

Alex So, because NewGDevice didn't initialize the gdRefNum and GetDCtlEntry was returning the wrong entry from the unit table, I don't get to teach the Pfhor about large caliber, high-velocity rounds.

cam Nasty.

Alex Yeah.

SCORING

Your performance compares to these memorable screen roles:

80-100	 Chuck Heston in El Cid

55-75 Anne Parillaud in La Femme Nikita

30-50 Chow Yun-Fat in Hard Boiled

5-25 Richard Roundtree in Shaft*

CAMERON ESFAHANI (cameron_esfahani@powertalk.apple.com, AppleLink DIRTY) SWM, 24, 5' 7", 180 pounds, brown hair, brown eyes. Apple engineer. Loves movies and music. Plays golf and tennis, rollerblades, ice-skates, and is learning to ski again. Enjoys life but has a serious side. Likes cooking, reading, shopping. Once a dog guy, now a definite cat man. Believes the American musical of the '50s and '60s to be the second greatest invention of the twentieth century. Favorites include West Side Story, The Sound of Music, Music Man, and Singin' in the Rain.*

ALEX ROSENBERG (alexr@bungie.com) Alex's left brain works on everything from communications software to the latest 3D graphics tricks. His right brain is constantly thinking up interesting T-shirts that Apple's Marketing folks don't approve of. While working as a member of the Mac OS 8 "Ministry of Information," he experimented with optimization for PowerPC, worked closely with Apple's compiler team, and contributed to IBM's The PowerPC Compiler Writer's Guide. Now one of the minions at Bungie Software, Alex recently decided that eating is overrated.*

Thanks to Tom Dowdy, Wayne Meretsky, Mike Neil, Tom Saulpaugh, KON (Konstantin Othmer), and BAL (Bruce Leak) for reviewing this column.*

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Adobe After Effects CC 2018 16.1.3 - Cre...
After Effects CC 2018 is available as part of Adobe Creative Cloud for $52.99/month (or $20.99/month for a single app license). The new, more connected After Effects CC 2018 can make the impossible... Read more
Adobe Audition CC 2019 12.1.4 - Professi...
Audition CC 2019 is available as part of Adobe Creative Cloud for as little as $20.99/month (or $9.99/month if you're a previous Audition customer). Adobe Audition CC 2019 empowers you to create and... Read more
Adobe Premiere Pro CC 2019 13.1.5 - Digi...
Premiere Pro CC 2019 is available as part of Adobe Creative Cloud for as little as $52.99/month. The price on display is a price for annual by-monthly plan for Adobe Premiere Pro only Adobe Premiere... Read more
Navicat Premium Essentials 12.1.25 - Pro...
Navicat Premium Essentials is a compact version of Navicat which provides basic and necessary features you will need to perform simple administration on a database. It supports the latest features... Read more
Sketch 58 - Design app for UX/UI for iOS...
Sketch is an innovative and fresh look at vector drawing. Its intentionally minimalist design is based upon a drawing space of unlimited size and layers, free of palettes, panels, menus, windows, and... Read more
ClipGrab 3.8.5 - Download videos from Yo...
ClipGrab is a free downloader and converter for YouTube, Vimeo, Facebook and many other online video sites. It converts downloaded videos to MPEG4, MP3 or other formats in just one easy step Version... Read more
Dash 4.6.6 - Instant search and offline...
Dash is an API documentation browser and code snippet manager. Dash helps you store snippets of code, as well as instantly search and browse documentation for almost any API you might use (for a full... Read more
FotoMagico 5.6.8 - Powerful slideshow cr...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more
Civilization VI 1.2.4 - Next iteration o...
Sid Meier’s Civilization VI is the next entry in the popular Civilization franchise. Originally created by legendary game designer Sid Meier, Civilization is a strategy game in which you attempt to... Read more
Skype 8.52.0.138 - Voice-over-internet p...
Skype allows you to talk to friends, family and co-workers across the Internet without the inconvenience of long distance telephone charges. Using peer-to-peer data transmission technology, Skype... Read more

Latest Forum Discussions

See All

Lots of premium games are going free (so...
You may have seen over the past couple weeks a that a bunch of premium games have suddenly become free. This isn’t a mistake, nor is it some last hurrah before Apple Arcade hits, and it’s important to know that these games aren’t actually becoming... | Read more »
Yoozoo Games launches Saint Seiya Awaken...
If you’re into your anime, you’ve probably seen or heard of Saint Seiya. Based on a shonen manga by Masami Kurumada, the series was massively popular in the 1980s – especially in its native Japan. Since then, it’s grown into a franchise of all... | Read more »
Five Nights at Freddy's AR: Special...
Five Nights at Freddy's AR: Special Delivery is a terrifying new nightmare from developer Illumix. Last week, FNAF fans were sent into a frenzy by a short teaser for what we now know to be Special Delivery. Those in the comments were quick to... | Read more »
Rush Rally 3's new live events are...
Last week, Rush Rally 3 got updated with live events, and it’s one of the best things to happen to racing games on mobile. Prior to this update, the game already had multiplayer, but live events are more convenient in the sense that it’s somewhat... | Read more »
Why your free-to-play racer sucks
It’s been this way for a while now, but playing Hot Wheels Infinite Loop really highlights a big issue with free-to-play mobile racing games: They suck. It doesn’t matter if you’re trying going for realism, cart racing, or arcade nonsense, they’re... | Read more »
Steam Link Spotlight - The Banner Saga 3
Steam Link Spotlight is a new feature where we take a look at PC games that play exceptionally well using the Steam Link app. Our last entry talked about Terry Cavanaugh’s incredible Dicey Dungeons. Read about how it’s a great mobile experience... | Read more »
Combo Quest (Games)
Combo Quest 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: Combo Quest is an epic, time tap role-playing adventure. In this unique masterpiece, you are a knight on a heroic quest to retrieve... | Read more »
Hero Emblems (Games)
Hero Emblems 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: ** 25% OFF for a limited time to celebrate the release ** ** Note for iPhone 6 user: If it doesn't run fullscreen on your device... | Read more »
Puzzle Blitz (Games)
Puzzle Blitz 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Puzzle Blitz is a frantic puzzle solving race against the clock! Solve as many puzzles as you can, before time runs out! You have... | Read more »
Sky Patrol (Games)
Sky Patrol 1.0.1 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0.1 (iTunes) Description: 'Strategic Twist On The Classic Shooter Genre' - Indie Game Mag... | Read more »

Price Scanner via MacPrices.net

$250 prepaid Visa card with any Apple iPhone,...
Xfinity Mobile will include a free $250 prepaid Visa card with the purchase of any new iPhone, new line activation, and transfer of phone number to Xfinity Mobile. Offer is valid through October 27,... Read more
Sprint is offering the 64GB Apple iPhone 11 P...
Sprint has the new 64GB iPhone 11 Pro available for $12.50 per month for new customers with an eligible trade-in in of iPhone 7 or newer. That’s down from their standard monthly lease of $41.67. The... Read more
Final week: Apple’s 2019 Back to School Promo...
Purchase a new Mac using Apple’s Education discount, and take up to $400 off MSRP. All teachers, students, and staff of any educational institution with a .edu email address qualify for the discount... Read more
Save $30 on Apple’s AirPods at these reseller...
Amazon is offering discounts on new 2019 Apple AirPods ranging up to $30 off MSRP as part of their Labor Day sale. Shipping is free: – AirPods with Charging Case: $144.95 $15 off MSRP – AirPods with... Read more
Preorder your Apple Watch Series 5 today at A...
Amazon has Apple Watch Series 5 GPS models available for preorder and on sale today for $15 off Apple’s MSRP. Shipping is free and starts on September 20th: – 40mm Apple Watch Series 5 GPS: $384.99 $... Read more
21″ iMacs on sale for $100 off Apple’s MSRP,...
B&H Photo has new 21″ Apple iMacs on sale for $100 off MSRP with models available starting at $999. These are the same iMacs offered by Apple in their retail and online stores. Overnight shipping... Read more
2018 4 and 6-Core Mac minis on sale today for...
Apple resellers are offering new 2018 4-Core and 6-Core Mac minis for $100-$150 off MSRP for a limited time. B&H Photo has the new 2018 4-Core and 6-Core Mac minis on sale for up to $150 off... Read more
Save $150-$250 on 10.2″ WiFi + Cellular iPads...
Verizon is offering $150-$250 discounts on Apple’s new 10.2″ WiFi + Cellular iPad with service. Buy the iPad itself and save $150. Save $250 on the purchase of an iPad along with an iPhone. The fine... Read more
Apple continues to offer 13″ 2.3GHz Dual-Core...
Apple has Certified Refurbished 2017 13″ 2.3GHz Dual-Core non-Touch Bar MacBook Pros available starting at $1019. An standard Apple one-year warranty is included with each model, outer cases are new... Read more
Apple restocks 2018 MacBook Airs, Certified R...
Apple has restocked Certified Refurbished 2018 13″ MacBook Airs starting at only $849. Each MacBook features a new outer case, comes with a standard Apple one-year warranty, and is shipped free. The... Read more

Jobs Board

Student Employment (Blue *Apple* Cafe) Spri...
Student Employment (Blue Apple Cafe) Spring 2019 Penn State University Campus/Location: Penn State Brandywine Campus City: Media, PA Date Announced: 12/20/2018 Date Read more
Geek Squad *Apple* Master Consultation Agen...
**732907BR** **Job Title:** Geek Squad Apple Master Consultation Agent **Job Category:** Services/Installation/Repair **Location Number:** 000360-Williston-Store Read more
*Apple* Mobile Master - Best Buy (United Sta...
**728519BR** **Job Title:** Apple Mobile Master **Job Category:** Store Associates **Location Number:** 000853-Jackson-Store **Job Description:** **What does a Best Read more
*Apple* Mobility Pro - Best Buy (United Stat...
**733006BR** **Job Title:** Apple Mobility Pro **Job Category:** Store Associates **Location Number:** 000865-Conroe-Store **Job Description:** At Best Buy, our Read more
*Apple* Mobility Pro-Store 149 - Best Buy (U...
**731985BR** **Job Title:** Apple Mobility Pro-Store 149 **Job Category:** Store Associates **Location Number:** 000149-Towson-Store **Job Description:** At Best Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.