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.*

 
AAPL
$119.00
Apple Inc.
+1.40
MSFT
$47.75
Microsoft Corpora
+0.28
GOOG
$540.37
Google Inc.
-0.71

MacTech Search:
Community Search:

Software Updates via MacUpdate

Skype 7.2.0.412 - Voice-over-internet ph...
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
HoudahSpot 3.9.6 - Advanced file search...
HoudahSpot is a powerful file search tool built upon MacOS X Spotlight. Spotlight unleashed Create detailed queries to locate the exact file you need Narrow down searches. Zero in on files Save... Read more
RapidWeaver 6.0.3 - Create template-base...
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
iPhoto Library Manager 4.1.10 - Manage m...
iPhoto Library Manager lets you organize your photos into multiple iPhoto libraries. Separate your high school and college photos from your latest summer vacation pictures. Or keep some photo... Read more
iExplorer 3.5.1.9 - View and transfer al...
iExplorer is an iPhone browser for Mac lets you view the files on your iOS device. By using a drag and drop interface, you can quickly copy files and folders between your Mac and your iPhone or... Read more
MacUpdate Desktop 6.0.3 - Discover and i...
MacUpdate Desktop 6 brings seamless 1-click installs and version updates to your Mac. With a free MacUpdate account and MacUpdate Desktop 6, Mac users can now install almost any Mac app on macupdate.... Read more
SteerMouse 4.2.2 - Powerful third-party...
SteerMouse is an advanced driver for USB and Bluetooth mice. It also supports Apple Mighty Mouse very well. SteerMouse can assign various functions to buttons that Apple's software does not allow,... Read more
iMazing 1.1 - Complete iOS device manage...
iMazing (was DiskAid) is the ultimate iOS device manager with capabilities far beyond what iTunes offers. With iMazing and your iOS device (iPhone, iPad, or iPod), you can: Copy music to and from... Read more
PopChar X 7.0 - Floating window shows av...
PopChar X helps you get the most out of your font collection. With its crystal-clear interface, PopChar X provides a frustration-free way to access any font's special characters. Expanded... Read more
OneNote 15.4 - Free digital notebook fro...
OneNote is your very own digital notebook. With OneNote, you can capture that flash of genius, that moment of inspiration, or that list of errands that's too important to forget. Whether you're at... Read more

Latest Forum Discussions

See All

Lucha Amigos (Games)
Lucha Amigos 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Forget Ninja Turtles, and meet Wrestlers Turtles! Crazier, Spicier and…Bouncier! Sling carapaces of 7 Luchadores to knock all... | Read more »
Raby (Games)
Raby 1.0.3 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.3 (iTunes) Description: ***WARNING - Raby runs on: iPhone 5, iPhone 5C, iPhone 5S, iPhone 6, iPhone 6 Plus, iPad Mini Retina, iPad Mini 3, iPad 4, iPad Air,... | Read more »
Oddworld: Stranger's Wrath (Games)
Oddworld: Stranger's Wrath 1.0 Device: iOS Universal Category: Games Price: $5.99, Version: 1.0 (iTunes) Description: ** PLEASE NOTE: Oddworld Stranger's Wrath requires at least an iPhone 4S, iPad 2, iPad Mini or iPod Touch 5th gen... | Read more »
Bounce On Back (Games)
Bounce On Back 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: | Read more »
Dwelp (Games)
Dwelp 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: === 50% off for a limited time, to celebrate release === Dwelp is an elegant little puzzler with a brand new game mechanic. To complete a... | Read more »
Make Way for Fat Chicken, from the Maker...
Make Way for Fat Chicken, from the Makers of Scrap Squad Posted by Jessica Fisher on November 26th, 2014 [ permalink ] Relevant Games has announced they will be releasing their reverse tower defense game, | Read more »
Tripnary Review
Tripnary Review By Jennifer Allen on November 26th, 2014 Our Rating: :: TRAVEL BUCKET LISTiPhone App - Designed for the iPhone, compatible with the iPad Want to create a travel bucket list? Tripnary is a fun way to do exactly that... | Read more »
Ossian Studios’ RPG, The Shadow Sun, is...
Ossian Studios’ RPG, The Shadow Sun, is Now Available for $4.99 Posted by Jessica Fisher on November 26th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Mmmm, Tasty – Having the Angry Birds for...
The very first Angry Birds debuted on iOS back in 2009. When you sit back and tally up the number of Angry Birds games out there and the impact they’ve had on pop culture as a whole, you just need to ask yourself: “How would the birds taste... | Read more »
Rescue Quest Review
Rescue Quest Review By Jennifer Allen on November 26th, 2014 Our Rating: :: PATH BASED MATCH-3Universal App - Designed for iPhone and iPad Guide a wizard to safety by matching gems. Rescue Quest might not be an entirely original... | Read more »

Price Scanner via MacPrices.net

Apple Store Black Friday sale for 2014: $100...
BLACK FRIDAY The Apple Store has posted their Black Friday deals for 2014. Receive a $100 PRODUCT(RED) branded iTunes gift card with the purchase of select Macs, $50 with iPads, and $25 with iPods,... Read more
Black Friday: 15% off iTunes Gift Cards
Staples is offering 15% off $50 and $100 iTunes Gift Cards on their online store as part of their Black Friday sale. Click here for more information. Shipping is free. Best Buy is offering $100... Read more
BEVL Releases Dock Tailored for iPhone 6 and...
Seattle based BEVL has released their first product: an iPhone dock that is divergent in build quality, rock-solid function and visual simplicity to complement the iPhone. BEVL is now accepting... Read more
Black Friday: $150 off 13-inch Retina MacBook...
 Best Buy has 13-inch 2.6GHz Retina MacBook Pros on sale for $150 off MSRP on their online store as part of their Black Friday sale. Choose free shipping or free local store pickup (if available).... Read more
Black Friday: $300 off 15-inch Retina MacBook...
 B&H Photo has the new 2014 15″ Retina MacBook Pros on sale for $300 off MSRP as part of their Black Friday sale. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina... Read more
Black Friday: Up to $140 off MacBook Airs, fr...
 B&H Photo has 2014 MacBook Airs on sale for up to $140 off MSRP as part of their Black Friday sale. Shipping is free, and B&H charges NY sales tax only: - 11″ 128GB MacBook Air: $799 $100... Read more
Black Friday: 13-inch 2.5GHz MacBook Pro on s...
 Best Buy has the 13″ 2.5GHz MacBook Pro on sale for $899.99 on their online store as part of their Black Friday sale. Choose free shipping or free instant local store pickup (if available). Their... Read more
Black Friday: 21-inch 1.4GHz iMac on sale for...
 Best Buy has the 21″ 1.4GHz iMac on sale for $899.99 on their online store as part of their Black Friday sale. Their price is $200 off MSRP. Choose free shipping or free local store pick up. Price... Read more
Black Friday iPad Air 2 sale prices, $100 off...
 Best Buy has iPad Air 2s on sale for $100 off MSRP on their online store for Black Friday. Choose free shipping or free local store pickup (if available). Sale prices available for online orders... Read more
2014 1.4GHz Mac mini on sale for $449, save $...
 B&H Photo has the new 1.4GHz Mac mini on sale for $449.99 including free shipping plus NY tax only. Their price is $50 off MSRP, and it’s the lowest price available for this new model. Adorama... Read more

Jobs Board

*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.