TweetFollow Us on Twitter

May 92 - KON & BAL'S PUZZLE PAGE

KON & BAL'S PUZZLE PAGE

SLEEPING BEAUTY

KONSTANTIN OTHMER AND BRUCE LEAK

See if you can solve this programming puzzle, presented in the form of a dialog between Konstantin Othmer (KON) and Bruce Leak (BAL). 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. These problems are supposed to be tough. If you don't get a high score, at least you'll learn interesting Macintosh trivia.


During the development of QuickTime, a number of interesting bugs reared their ugly heads. Try to figure out this one before KON does.

120 BAL Here's the problem: When you play a movie on a Macintosh IIfx the machine hangs after about six hours. If you turn off the sound, or try it on any Macintosh other than an fx, it doesn't hang.

KON How does it hang? Is the Macintosh locked up?

115 BAL Well, the movies aren't playing. They just all freeze about halfway through. Menus still work, though. You can even switch to the Finder and click between windows and move icons around, but when you launch an application or open a folder, the Finder draws one of the zoom rectangles and then hangs.

KON Like a time bomb. Can you get into MacsBug?

110 BAL Yeah.

KON Whew. For a second I thought this was going to be really tough. You've got MacsBug, so what's the problem?

BAL I don't know, you tell me.

KON How do movies get time? SystemTask or something?

105 BAL No, you have to call MoviesTask.

KON Figures. So I set a break on MoviesTask; is it getting called?

100 BAL Nope.

KON The application is supposed to call it?

95 BAL Yep.

KON So is WaitNextEvent getting called?

90 BAL Nope.

KON But menus work???

85 BAL Yep.

KON WaitNextEvent is being called with a bogus sleep time. I set a breakpoint on it, pull down a menu, and see what the sleep time parameter is.

80 BAL Now you're thinking, Kon! But no. The sleep time is 1, just as it's supposed to be.

KON Hmmm. So I trace 50 times and see where I'm spinning.

75 BAL There's a bunch of stuff going on; it's not just some simple loop.

KON So I record A-traps.

70 BAL There are three traps getting called: ABF7 from inside MF, A0DD (PPCToolbox) from a big block in the system heap that's not QuickTime, and A030 (EventAvail) from a 'scod' resource that's different from the block calling ABF7.

KON There are no null events coming through to the application, so MoviesTask never gets called. The sleep time must never be expiring. Are ticks running?

BAL How do you figure that out?

KON I DM ticks, continue executing, and then DM ticks again.

65 BAL Ticks doesn't change.

KON It's updated by some hardware mechanism at interrupt time, right?

BAL Sure, a hardware mechanism . Is that what they teach you at Caltech?

KON OK, OK. There's a heartbeat task that generates a level-1 interrupt that updates ticks, right?

60 BAL Yeah.

KON So is the level-1 interrupt happening?

BAL How do you check that?

KON I know from reading this cool develop  column that the level-1 interrupt vector is at location $64, so I set a break there and see if it's firing.

55 BAL Wait a second. That's the way ticks are updated on every Macintosh except the fx. This problem happens only on an fx.

KON Why is the fx different?

50 BAL The guy that designed the hardware assumed that the heartbeat task--and thus ticks-- was supposed to happen every 60th of a second. Unfortunately it's supposed to be every 60.14th of a second or something, so Gary Davidian fixed it by installing a Time Manager task that updates ticks. The extended Time Manager, found in System 6.0.4 and later, adds a drift-free mode for Time Manager callbacks. This allows for accurate scheduling of periodic events without long-term drift. With the extended Time Manager, the next callback is scheduled with respect to when the current callback should have fired, rather than the current time. So as of System 6.0.4 there are two types of Time Manager tasks: the regular ones and the drift-free ones. Ticks are updated via a drift-free task, so they advance accurately over time.

KON Hmmm. So is the Time Manager task that updates ticks getting called?

45 BAL Obviously not; ticks aren't changing.

KON How are the tasks in the queue organized?

40 BAL They're kept in the order that they fire in.

KON So where is the ticks task in the queue?

35 BAL Well, it's not the first one, and the first one is scheduled for sometime tomorrow.

KON Fine. I leave and come back tomorrow. Does my movie start playing?

30 BAL It could be. But we're shipping before then.

KON So the first element is getting messed up and never completes. Then none of the other items in the queue get executed because they're all deltas off the first element and the movies hang.

25 BAL Now we're getting somewhere.

KON So how is that first element getting confused?

BAL Whose problem is this?

KON OK. Who owns the first item?

BAL How do you figure that out?

KON I do an IL to see what traps it's calling. I see where it is in the heap. I set a breakpoint on it, force it to fire, and see what it does.

20 BAL You're knee deep in spaghetti. You could probably figure it out this way but it's pretty nasty.

KON OK. I break on InsTime to see who installs it. I break on PrimeTime to see who starts it up. I figure out whether it's using InsTime or InsXTime.

15 BAL The PrimeTime comes from an 'snth' resource. It was installed with InsXTime.

KON Aha! The Sound Manager. That's why it works when the sound is turned off.

BAL They don't pay you enough, Kon.

KON So how does this element get updated in the queue? Don't Time Manager tasks call PrimeTime to reschedule themselves?

10 BAL Yeah.

KON So is someone calling PrimeTime on the Sound Manager task with a bogus value?

5 BAL Not really. It always calls PrimeTime with a value of 0, indicating that it wants to be called right away. The Sound Manager does this since it's not reentrant. By scheduling a task, it knows it won't be called until it's finished servicing the current interrupt, avoiding reentrancy problems.

KON I'm sure everyone that's reading this has figured it out by now. I know I have.

BAL You're bluffing again, Kon.

KON It's easy. Since the drift-free Time Manager schedules tasks based on when they should occur, and since this sound task is using a count of 0 when calling PrimeTime, its backlog gets bigger and bigger. So each PrimeTime call schedules an event that should have occurred further and further in the past. The task is executed immediately, of course, but the backlog builds. It always puts this element at the head of the queue, but eventually it overflows the long that contains the backlog, and the scheduling time becomes incredibly large. There are about 4 billion microseconds in a long, which is about an hour. The Time Manager counts in units that are about 20 microseconds, so it would take about 20 hours to overflow. Take away a bit for signed math and another because it's calculating scheduling times, and I would guess it should hang about once every 5 hours. It must have taken forever to find that one.

BAL Yeah, it was a drag. We fixed it before we shipped QuickTime, of course. But it's just the kind of thing that makes scheduling software projects so hard.

KON Nasty.

BAL Yeah.

KONSTANTIN OTHMER AND BRUCE LEAK have been puzzling about reality, life, the universe, and even computers for a long time. Since the great success of their Graphics '90 World Tour, which included peace-keeping, hostage-freeing, and wall-smashing, they settled down, shipped a few QuickDraw packages, and cleaned out their closets. Then came the coup: da division of da Union. Konstantin got QuickDraw, 200 rubles, and a guaranteed spot at the front of the bread line. Official party line on Bruce: "vacationing in the Crimea." Bruce was actually working on the first QuickDraw spinoff. To provide a seamless upgrade path, and to leverage off of brand awareness, he decided to call this project QuickTime. *

SCORING

  • 100-120 Members of the QuickTime team and their immediate family aren't eligible.
  • 75-95 Scores count only on the first reading!
  • 50-70 Not bad--buy yourself an ice cream.
  • 25-45 The next one will be easier.
  • 5-20 Stick to word searches.*

Thanks to Gary Davidian and Jean-Charles Mourey for reviewing this column.*

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Skype 7.9.746 - Voice-over-internet phon...
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
Apple GarageBand 10.1 - Complete recordi...
The new GarageBand is a whole music creation studio right inside your Mac -- complete with keyboard, synths, orchestral and percussion instruments, presets for guitar and voice, an entirely... Read more
Duplicate Annihilator 5.7.7 - Find and d...
Duplicate Annihilator takes on the time-consuming task of comparing the images in your iPhoto library using effective algorithms to make sure that no duplicate escapes. Duplicate Annihilator... Read more
OS X Server 4.1.3 - For OS X 10.10 Yosem...
Designed for OS X and iOS devices, OS X Server makes it easy to share files, schedule meetings, synchronize contacts, develop software, host your own website, publish wikis, configure Mac, iPhone,... Read more
Firefox 39.0 - Fast, safe Web browser. (...
Firefox offers a fast, safe Web browsing experience. Browse quickly, securely, and effortlessly. With its industry-leading features, Firefox is the choice of Web development professionals and casual... Read more
pwSafe 4.1 - Secure password management...
pwSafe provides simple and secure password management across devices and computers. pwSafe uses iCloud to keep your password databases backed-up and synced between Macs and iOS devices. It is... Read more
Kodi 15.0.rc1 - Powerful media center to...
Kodi (was XBMC) is an award-winning free and open-source (GPL) software media player and entertainment hub that can be installed on Linux, OS X, Windows, iOS, and Android, featuring a 10-foot user... Read more
Coda 2.5.11 - One-window Web development...
Coda is a powerful Web editor that puts everything in one place. An editor. Terminal. CSS. Files. With Coda 2, we went beyond expectations. With loads of new, much-requested features, a few surprises... Read more
Bookends 12.5.7 - Reference management a...
Bookends is a full-featured bibliography/reference and information-management system for students and professionals. Access the power of Bookends directly from Mellel, Nisus Writer Pro, or MS Word (... Read more
Maya 2016 - Professional 3D modeling and...
Maya is an award-winning software and powerful, integrated 3D modeling, animation, visual effects, and rendering solution. Because Maya is based on an open architecture, all your work can be scripted... Read more

This Week at 148Apps: June 29-July 3, 20...
Into July With 148Apps How do you know what apps are worth your time and money? Just look to the review team at 148Apps. We sort through the chaos and find the apps you're looking for. The ones we love become Editor’s Choice, standing out above the... | Read more »
Sonic Runners Guide
Despite its flaws, Sonic Runners' platforming action is actually quite fun. Though it can be a little more complicated than old-school Sonic games. Here's how to make sure you're up to speed when jumping in. [Read more] | Read more »
Rage of Bahamut is Giving Almost All of...
The App Store isn't what it used to be back in 2012, so it's not unexpected to see some games changing their structures with the times. Now we can add Rage of Bahamut to that list with the recent announcement that the game is severely cutting back... | Read more »
Adventures of Pip (Games)
Adventures of Pip 1.0 Device: iOS iPhone Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: ** ONE WEEK ONLY — 66% OFF! *** “Adventures of Pip is a delightful little platformer full of charm, challenge and impeccable... | Read more »
Divide By Sheep - Tips, Tricks, and Stre...
Who would have thought splitting up sheep could be so involved? Anyone who’s played Divide by Sheep, that’s who! While we’re not about to give you complete solutions to everything (because that’s just cheating), we will happily give you some... | Read more »
NaturalMotion and Zynga Have Started Tea...
An official sequel to 2012's CSR Racing is officially on the way, with Zynga and NaturalMotion releasing a short teaser trailer to get everyone excited. Well, as excited as one can get from a trailer with no gameplay footage, anyway. [Read more] | Read more »
Grab a Friend and Pick up Overkill 3, Be...
Overkill 3 is a pretty enjoyable third-person shooter that was sort of begging for some online multiplayer. Fortunately the begging can stop, because its newest update has added an online co-op mode. [Read more] | Read more »
Scanner Pro's Newest Update Adds Au...
Scanner Pro is one of the most popular document scanning apps on iOS, thanks in no small part to its near-constant updates, I'm sure. Now we're up to update number six, and it adds some pretty handy new features. [Read more] | Read more »
Heroki (Games)
Heroki 1.0 Device: iOS Universal Category: Games Price: $7.99, Version: 1.0 (iTunes) Description: CLEAR THE SKIES FOR A NEW HERO!The peaceful sky village of Levantia is in danger! The dastardly Dr. N. Forchin and his accomplice,... | Read more »
Wars of the Roses (Games)
Wars of the Roses 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: | Read more »

Price Scanner via MacPrices.net

13-inch 1.6GHz MacBook Air on sale for $849,...
Amazon has the 2015 13″ 1.6GHz/128GB MacBook Air on sale for $849.99 including free shipping. Their price is $150 off MSRP, and it’s the lowest price available for this model. Read more
RamDisk4Mac App Helps Run Your Mac Faster And...
Ever use a RAM disk? If you’ve come to the Mac in the OS X era, likely not. The Classic Mac OS had a RAM disk function built-in, but that was dropped in the conversion to OS X. What is a RAM disk?... Read more
13-inch 1.6GHz MacBook Air on sale for $849,...
Best Buy has the 2015 13″ 1.6GHz/128GB MacBook Air on sale for $849.99 on their online store this weekend. Choose free shipping or free local store pickup (if available). Sale price for online orders... Read more
Apple Refurbished iMacs available for up to $...
The Apple Store has Apple Certified Refurbished iMacs available for up to $380 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 27″ 3.5GHz 5K iMac – $1949 $... Read more
Apple refurbished 2014 13-inch Retina MacBook...
The Apple Store has Apple Certified Refurbished 2014 13″ Retina MacBook Pros available for up to $400 off original MSRP, starting at $979. An Apple one-year warranty is included with each model, and... Read more
Seagate Backup Plus Drives Feature 200GB of C...
Seagate Technology plc has announced that its Backup Plus family of external storage offerings will now include 200GB of OneDrive cloud storage, a major added value, and the addition of Lyve’s photo... Read more
Canon PIXMA MG3620 Wireless Inkjet All-in-One...
Canon U.S.A., Inc. has announced the PIXMA MG3620 Wireless (1) Inkjet All-in-One (AIO) printer for high-quality photo and document printing. Built with convenience in mind for the everyday home user... Read more
July 4th Holiday Weekend 13-inch MacBook Pro...
Save up to $150 on the purchase of a new 2015 13″ Retina MacBook Pro at the following resellers this weekend. Shipping is free with each model: 2.7GHz/128GB MSRP $1299 2.7GHz/... Read more
27-inch 3.5GHz 5K iMac on sale for $2149, sav...
Best Buy has the 27″ 3.5GHz 5K iMac on sale for $2149.99. Choose free shipping or free local store pickup (if available). Sale price for online orders only, in-store prices may vary. Their price is $... Read more
Apple now offering refurbished 2015 11-inch...
The Apple Store is now offering Apple Certified Refurbished 2015 11″ MacBook Airs as well as 13″ MacBook Airs (the latest models), available for up to $180 off the cost of new models. An Apple one-... Read more

Jobs Board

*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
Senior Payments Security Manager - *Apple*...
**Job Summary** Apple , Inc. is looking for a highly motivated, innovative and hands-on senior payments security manager to join the Apple Pay security team. You will Read more
Sr. Technical Services Consultant, *Apple*...
**Job Summary** Apple Professional Services (APS) has an opening for a senior technical position that contributes to Apple 's efforts for strategic and transactional Read more
Sr. Payment Program Manager, *Apple* Pay -...
**Job Summary** Apple Pay is an exciting environment and a…devices in a simple, private and secure way. The Apple Pay Team is looking for an experienced Senior Read more
Project Manager - *Apple* Pay Security - Ap...
**Job Summary** The Apple Pay Security team is seeking a highly organized, results-driven Project Manager to drive the development of Apple Pay Security. If you are Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.