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

jAlbum 19.2 - Create custom photo galler...
With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code! Beginner-friendly, with pro results - Simply drag and drop photos into groups, choose a design... Read more
BlueStacks 4.140.13 - Run Android applic...
BlueStacks App Player lets you run your Android apps fast and fullscreen on your Mac. Feature comparison chart Version 4.140.13: Highlights/Bug Fixes: Feel free to use BlueStacks as your go to... Read more
Adobe Premiere Pro CC 2020 14.0.1 - Digi...
Premiere Pro CC 2020 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
VirtualBox 6.1.2 - x86 virtualization so...
VirtualBox is a family of powerful x86 virtualization products for enterprise as well as home use. Not only is VirtualBox an extremely feature rich, high performance product for enterprise customers... Read more
RoboForm 8.6.8 - Password manager; syncs...
RoboForm is a password manager that offers one-click login, mobile syncing, easy form filling, and reliable security. Password Manager. RoboForm remembers your passwords so you don't have to! Just... Read more
Postbox 7.0.11 - 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
calibre 4.9.0 - Complete e-book library...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital librarian... Read more
Notability 4.2 - Note-taking and annotat...
Notability is a powerful note-taker to annotate documents, sketch ideas, record lectures, take notes and more. It combines, typing, handwriting, audio recording, and photos so you can create notes... Read more
FoldersSynchronizer 5.0.1 - Synchronize...
FoldersSynchronizer is a popular and useful utility that synchronizes and backs-up files, folders, disks and boot disks. On each session you can apply special options like Timers, Multiple Folders,... Read more
Sketch 62 - 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

Latest Forum Discussions

See All

The Alliance update to Out There: Omega...
Out There is an old go-to recommendation for a lot of mobile stalwarts, but I could never really get into it. This sci-fi survival game that blended elements of interactive fiction and roguelike mechanics just felt a little off-balance and a little... | Read more »
Animal Fury Destination is an action-adv...
Animal Fury Destination is an action-adventure game from independent, Colombian developer Ignicion Games. It's a 3D action game where you'll play as various different characters as you embark on a quest to stop an evil crow sorcerer. [Read more] | Read more »
Shadowgun War Games Closed Beta Impressi...
Shadowgun: War Games is an upcoming free-to-play multiplayer shooter that’s essentially just an Overwatch knock-off. There are hero characters with special abilities, and you compete in 5-v-5 game modes where the goal is to use superior team... | Read more »
Slingsters is a physics-based puzzler fo...
Slingsters is a physics-based puzzle game where the aim is to collect various different monsters by flinging them from one side of a level to the other and into a box. It's also the first game from Nappy Cat and is available now for iOS and... | Read more »
Spiritwish's latest update sees the...
A sizeable update has hit Nexon's MMORPG Spiritwish today. It brings a new game mode, characters and there will also be a special event to celebrate the update with a firework display. [Read more] | Read more »
Maze Machina, a turn-based puzzler from...
The latest game from Arnold Rauers also known as Tiny Touch Tales is now available. You may be familiar with one of his many excellent titles such as Card Crawl, Enyo and Card Thief. His latest endeavour is called Maze Machina and you can grab it... | Read more »
Mario Kart Tour's Ice Tour races to...
Can you believe Mario Kart Tour is already on its 9th tour? The game only launched back in September, and since then it's become increasingly tricky to keep on top of the amount of new content Nintendo is pumping out. [Read more] | Read more »
Apple Arcade: Ranked - Top 50 [Updated 1...
In case you missed it, I am on a quest to rank every Apple Arcade game there is. [Read more] | Read more »
Marvel Future Fight's latest update...
Marvel Future Fight's latest update has added an all-new team of heroes to recruit and do battle with. The 'Warriors of the Sky' include Blue Dragon, War Tiger, Sun Bird, and Shadow Shell. As is the norm, each character comes with their own unique... | Read more »
Klee: Spacetime Cleaners is a fast-paced...
Klee: Spacetime Cleaners is a fast-paced auto-shooter that sports a cute retro aesthetic thathad racked up an impressive 100,000 pre-registers prior to its release. It's available now for both iOS and Android. [Read more] | Read more »

Price Scanner via MacPrices.net

Just in! Apple iMacs on sale for $100-$150 of...
B&H Photo has new 2019 21″ and 27″ 5K iMacs on stock today and on sale for up to $150 off Apple’s MSRP, with prices starting at only $999. These are the same iMacs sold by Apple in their retail... Read more
Save $100 on the 13″ 1.4GHz MacBook Pro at th...
Apple resellers have 13″ 1.4GHz MacBook Pros on sale today for $100 off Apple’s MSRP, and some are including free overnight delivery: (1) Amazon has new 2019 13″ 1.4GHz MacBook Pros on sale for $100... Read more
AT&T offers free 64GB Apple iPhone XS wit...
Open a new line of service with AT&T, and they will include a free 64GB iPhone XS. Credit for the phone is applied monthly over a 30 month lease. The fine print: “Limited Time Requires new line... Read more
New Verizon deal: Apple iPhone XR for $300 of...
Switch to Verizon and sign up with one of their Unlimited plans, and Verizon will take $300 off the price of an Apple iPhone XR (regularly $749), plus get a free $200 prepaid Mastercard. This is an... Read more
Amazon’s popular AirPods sale is back with mo...
Amazon has new 2019 Apple AirPods on sale today ranging up to $40 off MSRP, starting at $129, as part of their popular Apple AirPods sale. Shipping is free: – AirPods Pro: $234.98 $15 off MSRP –... Read more
Apple’s top of the line 10.5″ 256GB WiFi + Ce...
B&H Photo has the top of the line 10.5″ 256GB WiFi + Cellular iPad Air on sale for $599 shipped. That’s $180 off Apple’s MSRP for this model and the cheapest price available. Overnight shipping... Read more
Apple’s refurbished iPad Pros are the cheapes...
Apple has Certified Refurbished 11″ iPad Pros available on their online store for up to $220 off the cost of new models. Prices start at $679. Each iPad comes with a standard Apple one-year warranty... Read more
Just in: Take $100 off the price of the 3.0GH...
Apple resellers are offering new 2018 6-Core Mac minis for $100 off Apple’s MSRP today, only $999. B&H Photo has 6-Core Mac minis on sale for $100 off Apple’s standard MSRP. Overnight shipping is... Read more
Apple has 4-core and 6-core 2018 Mac minis av...
Apple has Certified Refurbished 2018 Mac minis available on their online store for $120-$170 off the cost of new models. Each mini comes with a new outer case plus a standard Apple one-year warranty... Read more
Amazon offers $200 discount on 13″ MacBook Ai...
Amazon has new 2019 13″ MacBook Airs with 256GB SSDs on sale for $200 off Apple’s MSRP, now only $1099, each including free shipping. Be sure to select Amazon as the seller during checkout, rather... Read more

Jobs Board

*Apple* Mobility Pro - Best Buy (United Stat...
**744429BR** **Job Title:** Apple Mobility Pro **Job Category:** Store Associates **Store NUmber or Department:** 000574-Garner-Store **Job Description:** At Best Read more
Geek Squad *Apple* Consultation Professiona...
**757963BR** **Job Title:** Geek Squad Apple Consultation Professional **Job Category:** Store Associates **Store NUmber or Department:** 000433-Henrietta-Store Read more
*Apple* Computing Professional - Best Buy (U...
**754611BR** **Job Title:** Apple Computing Professional **Job Category:** Store Associates **Store NUmber or Department:** 000142-Milpitas-Store **Job Read more
Best Buy *Apple* Computing Master - Best Bu...
**745058BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Store Associates **Store NUmber or Department:** 001080-Lake Charles-Store **Job Read more
Geek Squad *Apple* Consultation Professiona...
**756640BR** **Job Title:** Geek Squad Apple Consultation Professional **Job Category:** Store Associates **Store NUmber or Department:** 000484-Manchester-Store Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.