I've noticed a small, but ongoing stream of comments coming into my "Bobs Math Answers" post from the start of this year.  That post answered the math homework problem posed in my "just before the break" post here.  Most of those questions were things like "what's the answer to problem 12"...

And then I realized what was happening.  People were googling for "Math Answers", and there was my post, at the bottom of the first page...  Apparently, just as Eric Lippert is the expert on knowing if girls like you, I've become the expert on answering math questions for kids.

I think I need to be a bit more careful about my post topics to ensure that the google searches work more accurately :)

Threat modeling isn't new, it's been a part of good design for years.  Heck, the IETF has a threat model for the entire internet :) 

Note that I didn't say good security design, IMHO, threat modeling isn't necessarily about security design.  Threat modeling's really all about understanding your design, at a level that design documents don't necessarily cover.  

Threat modeling is almost more of a discipline than an analysis tool- if it's done right, it enables you to gain a much deeper understanding of your components and how they interact.  And by applying that methodology, you learn a great deal about your component.

We're currently running through the threat modeling process in my group.  Since I'm the security nut on my team, I'm the one who volunteered to run the process.  And it's really been an interesting exercise..

The big thing that writing the threat model for your feature (or component, or protocol, or whatever) is that it really forces you to understand the interactions between the various pieces of your feature.

When threat modeling, you need to concentrate on a bunch of things.  First, there's your assets (also known as protected resources).  All threats relate to assets that need to be protected.  If you don't have assets, you don't have threats.  But sometimes the things that are your assets can be quite subtle.  For example, the audio samples being sent to a sound card might be an asset (especially if the audio samples came from DRM'ed files).  So might the privileges of the LocalSystem (or the current user) account.  The contents of a file on the disk might be an asset for a filesystem, similarly, the contents of an email message is an asset for an email system (like Exchange).  Understanding your assets is key - assets tend are attacked in different ways, the attack strategies mounted against an email message probably won't work for transient data like an audio sample.

The next thing you need to determine is the entry points to your components.  The entry points to your components are what the attacker is going to use to gain access to your component.

Related to entry points, one other thing that you need to determine are the trust boundaries in your component.  A trust boundary is a boundary (physical or virtual) across which there is a varied level of trust.  For example, when you RPC from one machine to another (or one process to another), that forms a trust boundary.  Another example of a trust boundary is the network - almost by definition, "the wire" is a trust boundary.

For some systems, there are no real trust boundaries - an interactive application running as the user that only outputs data may have no trust boundaries.  Similarly, an API that processes data and returns it to the caller may have no trust boundaries.

Related to trust boundaries are trust levels - trust levels indicates how much you "trust" a portion of the system.  For instance, if a user is an administrator, they are trusted to do more than normal users.  When data flows between entities whose trust level is different, by definition, there is a trust boundary between those two entities.

Once you've identified your entry points, assets, trust boundaries, and trust levels, the next major part of a threat model is the data flow diagrams.  A data flow diagram indicates the flow of data into and out of the various parts of your components.

All of this is the up-front work.  It lays the foundation for the "meat" of the threat model, which, of course are the threats.  I'll write more about threats tomorrow..

One of the things that I realized while writing down all the stuff above is that getting all this stuff written down provides a really cool backup for your design documents.  Much of the time, design documents don't necessarily include all the interactions of the various pieces of the system (often they do, but...).  Threat modeling forces you to write those aspects of the design down.  It also forces you to think about (and write down on paper) the design of your component in terms of the DATA manipulated by your component, instead of the CODE that makes up your component.

Btw, Frank Swiderski and Window Snyder have an excellent book on threat modeling, it's a bit dry reading, but it's really invaluable for learning about the process.  Microsoft has also provided a threat modeling tool (written by Frank) here that can be used to help guide you through the process of developing the threat model.  Microsoft's been working hard internally at making the threat modeling process require less effort - the ultimate goal of the team is "Do the DFD, turn the crank!".

There are also lots of fascinating resources on the web available, including Dan Epp's article here, and Krishnan Ranganathan's threat model checklist here.  In addition, Michael Howard's written a bunch about TM, here and here.

Edit: Included some additional information and links for Michael Howard's TM articles.

Edit2: Corrected possesive on Dana Epp's name :)

Yesterday, I talked about the design of the NT browser service.

As a brief refresher from yesterdays post, the NT browser was effectively a distributed single-master database system which was designed to run completely without administration.  All the machines that participated in the browsing architecture were elected to their position, the user wasn't involved in that process.

The WfW browser used NetBIOS names to determine which machines had what role in the workgroup.  In general, the names followed a well established pattern of naming that was used for all the MS-NET products (since MS-NET 1.0 was introduced in 1983).  NetBIOS names are 16 byte flat names, in the MS-NET naming scheme, the last byte of the name was used for a signature, the first <n> bytes of the name were used for the computer name and the bytes between <n> and 15 were filled with 0x20 (space).  For example, the MS-NET server used <name>0x20 for the computer name.  MS-NET workstations used <name>0x00.

NetBIOS names come in two flavors: Unique and Group.  Unique names are guaranteed to be associated with a single computer on the network.  Group names are shared between multiple machines on the network.  Unique names receive unicasts (directed traffic), Group names receive multicasts (broadcasts).

For the browser, the master browser was identified because it had registered a NetBIOS name of <workgroup>0x1d.  The backup browsers and potential browsers all register the group name of <workgroup>0x1e.  When servers announce themselves, they send datagrams to <workgroup>0x1d.  There were other names used, and other functionality, but...

Ok, that's enough background to describe the bug.

As I mentioned yesterday, we cooked the browser election algorithm to ensure that an NT machine would always win the browser election.  Unfortunately, when we started wide deployment of NT machines on the corporate campus, this wasn't always the case.  We had tools that monitored the state of browsing in the most common domains on the network, and about once or twice a day, browsing would simply stop working on one or more of the domains.

The maddening thing was that this behavior was totally unreproducable - all we knew is that there was a WfW machine that had held onto the master browser name, and this WfW machine was preventing the NT machine from becoming the new master browser.  The NT machine was trying, but the WfW machine kept holding onto the name.  The really annoying thing was that the WfW machine had apparently forgotten that it was a master browser (even though it was holding onto the master browser name).

We gathered sniffs, we looked at code, we were clueless.

Eventually, after talking to the WfW team, we discovered the WfW bug that was causing it to forget that it had had the master browser name - essentially there was a code path that would cause it to think it had won the election, and it started to become the master browser.  If, during the process of registering the NetBIOS name for the master browser, it received an election packet that would cause it to lose the election, it stopped functioning as the master browser, but it forgot to relinquish the NetBIOS name.  So the browser application on WfW didn't think that it owned the NetBIOS name, but the network transport on the WfW machine thought it owned the name.

Ok, we'd found the bug, and it was the WfW team's bug.  Unfortunately, by this time, they'd already shipped, so they couldn't fix their code (and it wouldn't matter because there was a significant deployed base of WfW machines).  The thing is that they'd done a LOT of testing, and they'd never seen this problem.  So why was the NT browser exposing this?

Well, we went back to the drawing boards.  We looked over the NT browser election logic.  And we looked at it again.

And again.

We stared at the code and we just didn't see it.

And then one day, I printed out the code and looked at it one final time.

And I saw what we'd missed in all those code reviews before.

You see, there was one other aspect of the election process that I didn't mention before.  As a mechanism to ensure that elections damped down quickly (there's a phenomenon called "livelock" that occurs with distributed election systems that prevents elections from finishing), there were several timers associated with the election process.  Once an election request was received, the master browser would delay for 200ms before responding, backup browsers would delay for 400ms and potential browsers would delay for 800ms.  This ordering ensured that master browsers would send their request first, thus ensuring that the election would finish quickly (because if there was a current master browser, it ought to continue to be the master browser).

Well, the code in question looked something like this (we all used text editors at the time, there weren't any GUI editors available):

When we did our code reviews, this is what we all saw (of course this isn't the real code, I just mocked it up for this article).

If I'd looked at the entire line, I'd have seen this:

Note that the master browser case is using the backup browser timer, not the master browser timer.  It turns out that this was the ENTIRE root cause of the bug - because the master browser was delaying its election response for too long, the WfW machines thought they had won the election.  And they started to become masters, and during that process, they received the election packet from the master browser.  Which quite neatly exposed the bug in their code.  Even without the WfW bug, this bug would have been disastrous for the browsing system, because it would potentially cause the very livelock scenario the election algorithm was designed to remove.

Needless to say, we quickly fixed this bug, and deployed it in the next NT build, and the problem was solved.

So what are the lessons learned here?  Clearly the first is that code reviews have to be complete - if text is wrapping off the screen, it's not guaranteed to be correct.  Also, distributed systems misbehave in really subtle ways - a simple bug in timing of a single packet can cause catastrophic behaviors.

Actually Raymond's post this morning about the network neighborhood got me thinking about the NT browser and it's design.  I've written about the NT browser before here, but never wrote up how the silly thing worked.  While reminiscing, I remembered a memorable bug I fixed back in the early 1990's that's worth writing up because it's a great example of how strange behaviors and subtle issues can appear in peer-to-peer distributed systems (and why they're so hard to get right).

Btw, the current design of the network neighborhood is rather different than this one - I'm describing code and architecture designed for systems 12 years ago, there have been a huge number of improvements to the system since then, and some massive architectural redesigns.  In particular, the "computer browser" service upon which all this depends is disabled in Windows XP SP2 due to attack surface reduction.  In current versions of Windows, Explorer uses a different mechanism to view the network neighborhood (at least on my machine at work).

The actual original design of the NT browser came from Windows for Workgroups.  Windows for Workgroups was a peer-to-peer networking solution for Windows 3.1 (and continued to be the basis of the networking code in Windows 95).  As such, all machines in a workgroup needed to be visible to all the other machines in the workgroup.  In addition, since you might have different workgroups on your LAN, it needed to be able to enumerate all the workgroups on the LAN.

One critical aspect of WfW is that it was designed for LAN environments - it was primarily based on NetBEUI, which was a LAN protocol designed by IBM back in the 1980's.  LAN protocols typically scale quite nicely to several hundred computers, after which they start to fall apart (due to collisions, etc).  For larger networks, you need a routable protocol like IPX or TCP, but at the time, it wasn't that big a deal (we're talking about 1991 here - way before the WWW existed).

As I mentioned, WfW was a peer-to-peer product.  As such, everything about WfW had to be auto-configuring.  For Lan Manager, it was ok to designate a single machine in your domain to be the "domain controller" and others as "backup domain controllers", but for WfW, all that had to be automatic.

To achieve this, the guys who designed the protocol for the WfW browser decided on a three tier design.  Most of the machine on the workgroup would be "potential browser servers".  Some of the machines in the workgroup would be declared as "browser servers", one of the machine in the workgroup was the "master browser server".

Client's periodically (every three minutes) sent a datagram to the master browser server, and the master browser would record this in it's server list.  If the server hadn't heard from the client for three announcements, it assumed that the client had been turned off and removed it from the list.  Backup browser servers would periodically (every 15 minutes) retrieve the browser list from the master browser.

When a client wanted to browse the network, the client sent a broadcast datagram to the workgroup asking who the browser servers were on the workgroup.  One of the backup or master browser servers would respond within several seconds (randomly).  The client would then ask that browser server for its list of machines, and would display that to the user.

If none of the browser servers responded, then the client would force an "election".  When the potential browser servers received the election datagram, they each broadcast a "vote" datagram that described their "worth".  If they saw a datagram from another server that had more "worth" than they did, they silently dropped out of the election.

A servers "worth" was based on a lot of factors - the system's uptime, the version of the software running, their current role as a browser (backup browsers were better than potential browsers, master browsers were better than backup browsers).

Once the master browser was elected, it nominated some number of potential browser servers to be backup browsers

This scheme worked pretty well - browsers tended to be stable, and the system was self healing.

Now once we started deploying the browser in NT, we started running into problems that caused us to make some important design changes.  The biggest one related to performance.  It turns out that in a corporate environment, peer-to-peer browsing is a REALLY bad idea.  There's no way of knowing what's going on on another persons machine, and if the machine is really busy (like if it's running NT stress tests), it impacts the browsing behavior for everyone in the domain.  Since NT had the concept of domains (and designated domain controllers), we modified the election algorithm for to ensure that NT server machines were "more worthy" than NT workstation machines, this solved that particular problem neatly.  We also biased the election algorithm towards NT machines in general, on the theory that NT machines were more likely to be more reliable than WfW machines.

There were a LOT of other details about the NT browser that I've forgotten, but that's a really brief overview, and it's enough to understand the bug.  Btw, I'm the person who coined the term "Bowser" (as in "bowser.sys") during a design review meeting with my boss (who described it as a dog) :)

Btw, Anonymous Coward's comment on Raymond's blog is remarkably accurate, and states many of the design criteria and benefits of the architecture quite nicely.  I don't know who AC is (my first guess didn't pan out), but I suspect that person has worked with this particular piece of code :)

As such, it wasn't actually that bad, and for most email addresses, it does the right thing.  This example is actually better than many email address validators I've found (some don't allow forms like user@subdomain.domain.com, which is patently legal).

But it doesn't really validate RFC 2822 email addresses.  Instead, it validates COMMON email addresses.  It turns out that it's not really possible to validate all the legal 2822 email addresses in a regular expression.

Here's the grammar for valid email addresses from RFC 2822 (ignoring the obsolete definitions).   Btw, this may not be complete - I tried to pull the relevant pieces from RFC2822, but...:

The key thing to note in this grammar is that the local-part is almost free-form when it comes to the local part.  And there are characters allowed in the local part like !, *, $, etc that are totally legal according to RFC2822 that aren't allowed.

So the validation routine in question won't accept a perfectly legal email address like "Foo!Bar@MyDomain.Org".

Kudos: Uwe Keim was the first person to catch the big issue (although Denny came REALLY close), in the first two comments on the article.

KCS also pointed out an inefficiency in the code - it uses "if (boolean) return true else return false", which is redundant.

Non Bugs: Tad pointed out that the code doesn't check for a null emailAddress.  Anyone who's been reading my blog for long enough would realize that I don't consider issues like that that to be bugs (and, in fact, I consider checking for those cases to be bugs).  The strongest change I'd make towards validating emailAddress is to put a Debug.Assert(emailAddress != null) in the code - it's a bug in the caller if they pass in a null emailAddress.

philoserf pointed out that the code "is good enough", and he's right.  On the other hand, Aaron Robinson pointed out that people in the .info and .museum top level domains are gonna be pretty unhappy.

Adi Oltean pointed out that V2 of the .Net framework contains the System.Net.MailAddress class which contains a built-in validator.  Very cool.

It's time for another "What's wrong with this code".

Today's example is really simple, and hopefully easy.  It's a snippet of code I picked up from the net that's intended to validate an email address (useful for helping to avoid SQL injection attacks, for example).

    /// <summary>
    /// Validate an email address provided by the caller.
    ///
    /// Taken from http://www.codeproject.com/aspnet/Valid_Email_Addresses.asp
    /// </summary>
    public static bool ValidateEmailAddress(string emailAddress)
    {
        string strRegex = @"^([a-zA-Z0-9_\-\.]+)@((\[[0-9]{1,3}" +
                          @"\.[0-9]{1,3}\.[0-9]{1,3}\.)|(([a-zA-Z0-9\-]+\" +
                          @".)+))([a-zA-Z]{2,4}|[0-9]{1,3})(\]?)$";
        System.Text.RegularExpressions.Regex re = new System.Text.RegularExpressions.Regex(strRegex);
        if (re.IsMatch(emailAddress))
            return (true);
        else
        return (false);
    }

As always, my next post (Monday) will include the answers and kudos to all those who got it right (and who f

I don't normally do "Me Too" posts, and I know that this one will get a lot of coverage on the Microsoft blogs, but the Seattle PI blog just mentioned that the beta of Microsoft's new anti-spyware solution was just released to the web here.

I installed it on my machines at work yesterday, and it seems pretty nice so far.  Of course I didn't have any spyware for it to find (because I'm pretty darned careful, and run as a limited user), but...  It'll be interesting to run it at home, especially since Valorie (and I) like playing some of the online games (like Popcap's) that get singled out as being spyware by some tools.

I have no knowledge of their final product plans, so it's pointless to ask.  All I know about this is what I've read in the press.

There was an internal discussion, and someone pointed to this article written by Scott Culp that describes what a "Security Vulnerability" is.

It's actually a cool article, and rather nicely points out the definition of a vulnerability:

It also explains what all the terms in this definition mean - for instance:

I've got to say that I like this definition, especially after it's been spelled out in detail.

Fibers were added to Windows (in NT 3.51 SP3, IIRC) because some customers (not just SQL server) believed that they could improve the performance of their server applications if they had more control over their threading environment.

But why on earth did these customers want fibers?

Well, it's all about scalability, especially on MP system.  On a multitasking system, it's easy to forget that a single processor can only do one thing at a time.

The ramifications of this are actually quite profound.  If you've got two tasks currently running on your system, then your operating system will have to switch between each of them.  That switch is called a context switch, and it can be expensive (just for the sake of argument, let's say a context switch takes 5000 instructions).  In a context switch, the operating system has to (at a minimum):

1. Enter Kernel Mode
2. Save all the old threads registers.
3. Acquire the dispatch spinlock.
4. Determine the next thread to run (if the next thread is in another process, this can get expensive)
5. Leave the dispatch spinlock.
6. Swap the old threads kernel state with the new threads kernel state.
7. Restore the new threads registers.
8. Leave Kernel Mode

That's a fair amount of work to perform (not outrageous, but not trivial).

The OS won't do this unless it has to.  In general, there are three things that will cause the OS to cause a context switch are (there are others, like page faults, but these are the big ones):

1. When your thread goes to sleep (either by calling Sleep() or calling WaitFor[Single|Multiple]Object[s])
2. When your thread calls SwitchToThread() or Sleep(0) (this is a special case of the Sleep() API that is identical to SwitchToThread())
3. When your thread's quanta elapses.

A thread's quanta is essentially the amount of time that the OS will dedicate to a thread if there's another thread in the system that can also run.  A quantum is something like 5-10 ticks on a workstation and 10-15 on server, and each tick is typically somewhere between 10 and 15 milliseconds, depending on the platform.  In general, your thread will get its full quanta unless there is a higher priority runnable thread in the system (please note: this is a grotesque simplification, but it's sufficient for the purposes of this discussion).

The thing is, for a highly scalable application, context switches are BAD.  They represent CPU time that the application could be spending on working for the customer, but instead is spent doing what is essentially OS bookkeeping.  So a highly scalable application REALLY wants to reduce the number of context switches.  If you ever have a service that's performing poorly, one of the first things to look for is the number of context switches/second - if it's high (for some value of high), then there's invariably a scalability issue in the application that needs to be addressed.

So why fibers?  Because for highly scalable applications, you want each of your threads to get their full quanta - in other words, you want the only reason for a context switch to be reason #3 above. 

Remember the first cause of context switches: Calling WaitFor*Object.  What that means is that if you call EnterCriticalSection on a critical section with contention, then you're highly likely to cause a context switch. The same thing happens when you wait for an I/O to complete, etc.  You absolutely want to avoid calling any Win32 APIs that might block under the covers.

So fibers were created to resolve this issue.  A fiber is effectively removes steps 1, 3, 5 and 8 from the context switch steps above, switching from one fiber to another just saves the old register state, and restores the new register state.  It's up to the application to determine which fiber runs next, etc.  But the application can make its own choices.  As a result, a server application could have a dozen or more "tasks" running on each thread, and they'd radically reduce their context switch overhead, because saving and restoring registers is significantly faster than a full context switch.  The other thing that fibers allow is the ability to avoid the dispatcher spin lock (see John Vert's comment about context switches being serialized across all processors below).  Any global lock hurts your scalability, and fibers allow an application to avoid one of the global locks in the system.

Ok, so why have fibers remained obscure?

They've remained obscure first because of the reasons Raymond mentioned in his fibers caveat here - using fibers is an all-or-nothing thing, and it's not possible to use fibers from a shared library.  As Rob Earhart pointed out in this comment on Raymond's post, some of the idiosyncrasies of the fiber APIs have been resolved in the current versions of Windows.

They're also HARD to deal with - you essentially have to write your own scheduler.

Raymond also left off a couple of other gotchas: For example, if you're using fibers to improve your apps scalability, you can't call ANY Win32 APIs that might block (including filesystem APIs) because all the Win32 blocking APIs are also have thread affinity (not surprisingly :)) So if you're running 20 fibers on a single thread, when any of the fibers blocks, your thread blocks (however, the fibers can be run from another thread, because fibers don't have thread affinity, so if you have a spare thread around, that thread can run the fibers).

The other reason that fibers have remained obscure is more fundamental.  It has to do with Moore's law (there's a reason for the posts yesterday and the day before).

Back when fibers were first implemented, CPUs were a lot slower.  Those 5000 instructions for the context switch (again, this is just a guess) took .05 millisecond (assuming one cycle/instruction) to execute on a 100MHz machine (which would be a pretty fast machine in 1995).  Well, on a 2GHz machine, that .05 is .0025 millisecond - it's an order of magnitude smaller.  The raw cost of a context switch has gone down dramatically.  In addition, there has been a significant amount of work in the base operating system to increase the scalability of the dispatcher spinlock - nowadays, the overhead of the dispatcher lock is essentially nonexistant on many MP machines (you start to see contention issues on machines with a lot of CPUs, for some value of "large").

But there's another aspect of performance that has gone up dramatically, and that's the cost of blowing the CPU cache.

As processors have gotten smarter, the performance of the CPU cache has become more and more critical to their speed - because main memory is painfully slow compared to the speed of the processor, if you're not getting your data from the CPU's cache, you're paying a huge hidden penalty.  And fibers don't fix this cost - when you switch from one fiber to another, you're going to blow the CPU cache.

Nowadays, the cost of blowing the cache has leveled the playing field between OS context switches and fibers - these days, you don't get nearly the benefit from fibers that you did ten years ago.

This isn't to say that fibers won't become useful in the future, they might.  But they're no longer as useful as they were.

Btw, it's important to note that fibers aren't the ONLY solution to the thread quantization issue mentioned above.  I/O completion ports can also be used to limit context switches - the built-in Win32 thread pool uses them (that's also what I used in my earlier post about thread pools).  In fact, the recomendation is that instead of spending your time rewriting your app to use fibers (and it IS a rewrite), instead it's better to rearchitect your app to use a "minimal context" model - instead of maintaining the state of your server on the stack, maintain it in a small data structure, and have that structure drive a small one-thread-per-cpu state machine.  You'll still have the issue of unexpected blocking points (you call malloc and malloc blocks accessing the heap critical section), but that issue exists regardless of how your app's architected.

If you're designing a scalable application, you need to architect your application to minimize the number of context switches, so it's critical that you not add unnecessary context switches to your app (like queuing a request to a worker thread, then block on the request (which forces the OS to switch to the worker, then back to the original thread)). 

Significant Edit (1/10/2005): Fixed several issues pointed out by the base performance team.

I don't quite get the argument. If my applications can't run on current hardware, I'm dead in the water. I can't wait for the next CPU.

The thing is that that's the way people have worked for the past 20 years.  A little story goes a long way of describing how the mentality works.

During the NT 3.1 ship party, a bunch of us were standing around Dave Cutler, while he was expounding on something (aside: Have you ever noticed this phenomenon?  Where everybody at a party clusters around the bigwig?  Sycophancy at its finest).  The topic on hand at this time (1993) was Windows NT's memory footprint.

When we shipped Windows NT, the minimum memory requirement for the system was 8M, the recommended was 12M, and it really shined at somewhere between 16M and 32M of memory.

The thing was that Windows 3.1 and OS/2 2.0 both were targeted at machines with between 2M and 4M of RAM.  We were discussing why NT4 was so big.

Cutlers response was something like "It doesn't matter that NT uses 16M of RAM - computer manufacturers will simply start selling more RAM, which will put pressure on the chip manufacturers to drive their RAM prices down, which will make this all moot". And the thing is, he was right - within 18 months of NT 3.1's shipping, memory prices had dropped to the point where it was quite reasonable for machines to come out with 32M and more RAM. Of course, the fact that we put NT on a severe diet for NT 3.5 didn't hurt (NT 3.5 was almost entirely about performance enhancements).

It's not been uncommon for application vendors to ship applications that only ran well on cutting edge machines with the assumption that most of their target customers would be upgrading their machine within the lifetime of the application (3-6 months for games (games are special, since gaming customers tend to have bleeding edge machines since games have always pushed the envelope), 1-2 years for productivity applications, 3-5 years for server applications), and thus it wouldn't matter if their app was slow on current machines.

It's a bad tactic, IMHO - an application should run well on both the current generation and the previous generation of computers (and so should an OS, btw).  I previously mentioned one tactic that was used (quite effectively) to ensure this - for the development of Windows 3.0, the development team was required to use 386/20's, even though most of the company was using 486s.

But the point of Herb's article is that this tactic is no longer feasible.  From now on, CPUs won't continue to improve exponentially.  Instead, the CPUs will improve in power by getting more and more parallel (and by having more and more cache, etc).  Hyper-threading will continue to improve, and while the OS will be able to take advantage of this, applications won't unless they're modified.

Interestingly (and quite coincidentally) enough, it's possible that this performance wall will effect *nix applications more than it will affect Windows applications (and it will especially effect *nix derivatives that don't have a preemptive kernel and fully asynchronous I/O like current versions of Linux do).  Since threading has been built into Windows from day one, most of the high concurrency application space is already multithreaded.  I'm not sure that that's the case for *nix server applications - for example, applications like the UW IMAP daemon (and other daemons that run under inetd) may have quite a bit of difficulty being ported to a multithreaded environment, since they were designed to be single threaded (other IMAP daemons (like Cyrus) don't have this limitation, btw).  Please note that platforms like Apache don't have this restriction since (as far as I know), Apache fully supports threads.

This posting is provided "AS IS" with no warranties, and confers no rights.

I wasn't planning on writing about the disaster, since I figured that many people more eloquent than I had already covered it.

And then I got an email from Will Poole, the Senior VP in charge of the Windows division.  Will was on Phuket at the time of the tsunami,  Will was sea kayaking on Phuket at the time of the Tsunami.  Fortunately, he and his family were safe (they were on the "unaffected" part of the island.

Will wrote up a Photostory3 photostory with his pictures of the event, and posted them on the Nikon digital photography site here (if you're running XP SP2, the content's mislabled so you need to allow the content to be downloaded).  You'll need WM10 or Photostory3 to see it, since it's encoded with the Photostory codec (which dramatically reduces the size of the WMV file).  Will ends with an ad for Photostory3, IMHO, that was unfortunate (since it detracts from his message), but...

Anyway, the video's absolutely worth watching.

And if you can somehow find the money, please, please give to one of the many charities helping out.  While the news reports currently indicate that they currently have more cash than they know what to do with, the reality is that the reason for this is simply that too much infrastructure's been lost for them to begin spending the money - the need is still there.

This posting is provided "AS IS" with no warranties, and confers no rights.

In it, he points out that developers will no longer be able to count on the fact that CPUs are getting faster to cover their performance issues.  In the past, it was ok to have slow algorithms or bloated code in your application because CPUs got exponentially faster - if you app was sluggish on a 2GHz PIII, you didn't have to worry, the 3GHz machines would be out soon, and they'd be able to run your code just fine.

Unfortunately, this is no longer the case - the CPU manufacturers have hit a wall, and are (for the foreseeable future) unable to make faster processors.

What does this mean?  It means that (as Herb says) the free lunch is over. Intel (and AMD) isn't going to be able to fix your app's performance problems, you've got to fall back on solid engineering - smart and efficient design, extensive performance analysis and tuning.

It means that using STL or other large template libraries in your code may no longer be acceptable, because they hide complexity.

It means that you've got to understand what every line of code is doing in your application, at the assembly language level.

It means that you need to investigate to discover if there is inherent parallelism in your application that you can exploit.  As Herb points out, CPU manufacturers are responding to the CPU performance wall by adding more CPU cores - this increases overall processor power, but if your application isn't designed to take advantage of it, it won't get any faster.

Much as the financial world enjoyed a 20 year bull market that recently ended (ok, it ended in 1999), the software engineering world enjoyed a 20 year long holiday that is about to end. 

The good news is that some things are still improving - memory bandwidth continues to improve, hard disks are continuing to get larger (but not faster).  CPU manufacturers are going to continue to add more L1 cache to their CPUs, and they're likely to continue to improve.

Compiler writers are also getting smarter - they're building better and better optimizers, which can do some really quite clever analysis of your code to detect parallelisms that you didn't realize were there.  Extensions like OpenMP (in VS 2005) also help to improve this.

But the bottom line is that the bubble has popped and now it's time to pay the piper (I'm REALLY mixing metaphors today).  CPU's aren't going to be getting any faster anytime soon, and we're all going to have to deal with it.

This posting is provided "AS IS" with no warranties, and confers no rights.

EDIT: Please note: This is a single post explaining the answer to a question posted earlier on this blog. 

This site is NOT intended as a general purpose site in which to get help with your math homework.

If you're having problems with your math homework, then you should consider asking your parents for help, you're not likely to find it here, sorry about that.

Ok, he's back :)  My last post was a math problem that the teacher in my wife's classroom gave to the students (mostly 11 and 12 year olds fwiw).

Here's the official answer to the problem, the kids needed to show ALL the calculations (sorry for the word-junk):

Pyramid L=W=2’ H2 = 22 – 12 so H = 1.73

V        =1/3*l*w*h

= 1/3*2*2*1.73 = 2.31 cubic feet

SA     =b2 + 2bh

= (2)2 + 2*(2)*1.73

= 4 + 6.92 = 10.92 square feet.

Triangles

V=B*h   SA = front + back + 3 sides

= 2*(1/2*l*h) + 3* L*W

Triangle #1 : L=8’, W=2’ H2 = 82 – 42 H = 6.93

V = 1/2*8*6.93*2 = 55.44 cubic feet

SA = 2(1/2*8*6.93) + 3*8*2 = 103.44 square feet

Triangle #2 : L=9’, W=2’ H2 = 92 – 4.52 H = 7.79

V = 1/2*9*7.79*2 = 70.11 cubic feet

SA = 2(1/2*9*7.79) + 3*9*2 = 124.11 square feet

Triangle #3 : L=10’, W=2’ H2 = 102 – 52 H = 8.66

V = 1/2*10*8.66*2 = 86.6 cubic feet

SA = 2(1/2*10*8.66) + 3*10*2 = 146.6 square feet

Base of Tree: L=W=2’  H= 3’

V = L*W*H = 2*2*3 = 12 cubic feet

SA     = 2(L*H) + 2(W*H) + 2(L*W)

          = 2(2*3 + 2*3 + 2*2)

          = 2(6 + 6 + 4)

          = 32 square feet

6 cones with H=1’, R=.5’, S= 1.12’

V = 1/3*π*r2h = 1/3 * 3.14*.52 * 1 = .26 cubic feet

Total volume = 6*.26 = 1.56 cubic feet

Volume before cutouts:

Pyramid                    2.31

Triangle #1           55.44

Triangle #2           70.11

Triangle #3           86.60

Base                        12.00

Cones                        1.56

TOTAL                  228.02

                             Cubic feet

 Surface Area before cutouts:

Pyramid                   10.92

Triangle #1           103.44

Triangle #2           124.11

Triangle #3           146.60

Base                        32.00

Cones                      15.30

TOTAL                  432.37

Square

---

Cutout Calculations - Volume

All of the volume of the cutouts are subtracted from the total volume of the Christmas tree.

There are 6 cylinders total.

1 has r=1, h=2

4 have r=1.5, h=2

1 has r=2, h=2

V = πr2h       SA = 2πr2 + 2πrh

V        = π*(12 + 4(1.52) + 22)*2

          = π*(1+9+4)*2

          = 3.14*14*2 = 87.92 cubic feet

Small Triangular Prisms

There are three triangular prisms.

1 has L=B=1 and W = 2’

H2 = 12 - .52 so H= .87’

2 have L=B=1.5 and W = 2

          H2 = 1.52 - .752 so H = 1.69’

V        = Bw where B=1/2*l*h

V        = (1/2*1*.87*2) + 2*(1/2*1.5*1.69*2)

          = .87 + 5.07

          = 5.94 cubic feet

Total volume to subtract:

87.92

+5.94

93.86 cubic feet

Christmas tree volume minus cutouts:

          228.02

          -93.86

134.16 Cubic Feet total

The front and back SA’s are subtracted from the total SA of the Christmas Tree but the side SA’s are added to the total.

Cylinders

Front and back SA = 2πr2

Side SA = 2πrh

Front and Back SA

          = 2π(12 + 4*1.52 + 22)

          =6.28 * (1+9+4)

          = 87.92 Square feet

Side SA

          = 2πrh

          =2*π*(1+4*1.5+2)*2

          = 12.56 * 9 = 113.04 Square feet

Small Triangular Prisms

Front and Back SA

= 2*1/2*b*h

= b*h

= 1*.87 + 2(1.5*1.69)

= .87 + 5.07

= 5.91 Square Feet

Side SA

          = 3*b*w

          = 3*(1+1.5+1.5)*2

          = 24 square feet

Twice the SA of top of Base

          =2(2*2)=8 Square Feet

SA to Add:            137.04

SA to Subtract:      101.83

Total SA to add:      35.21

Christmas Tree SA plus cutouts:

          432.37

          +35.21

          467.58 Square Feet Total

Edit: Reduced Google juice of this post by changing the title from "Bobs Math Answers" to something more accurate - this post isn't intended to be a Q&A for students who are having trouble with their math homework :)

And now for something completely different...

Well, today's no different.

For the season break, I thought I'd share one of their homework problem, also known as "The Christmas Tree Problem".

For context, this is a split class of 5th and 6th graders, they're presented with a challenging curriculum that diverges from many of the traditional 5th and 6th grade topics.  One aspect of that curriculum is known as "Bob's Math" (for the teacher, Bob Whittemore).  He covers stuff that's usually far beyond the normal course of study for 5th and 6th graders, some of them are high school subjects.

Just before the winter break, Bob traditionally assigns this homework problem...

Find the volume and surface area of the following Christmas Tree:

One pyramid with L=W=2’ S=2’   A stick with no dimension.   An equilateral triangular prism with L=8’ and W=2’. A cylinder where r=1’ and w=2’ is cut out An equilateral triangular prism with L=1’ and W=2’ is cut out Two cones with H=1’, r=.5’  Find the slope or slant height An equilateral triangular prism with L=9’ and W=2’. Two cylinders where r=1.5’ and w=2’ are cutout. An equilateral triangular prism with L=1.5’ and W=2’ is cut out. Two cones with H=1’, r=.5’ Find the slope or slant height   A triangular prism with L=10’ and W=2’. A cylinder where r=2’ and w=2’ Two cylinders where r=1.5’ and w=2’ are cut out An equilateral triangular prism with L=1.5’ and W=2’ is cut out Two cones with H=1’, r=.5’ Find the slope or slant height   A base consisting of a single rectangular prism with L=W=2’ and H=3’

Terms: L=Length     W=Width     H=Height     S = Slant Height    R=Radius

On this note, I'm off for vacation.  I'll be back late December, but until then, I don't know how spotty my internet access will be.  I'll see what I can do to keep the blog moving forward given the moderation (which I can't remove unfortunately), but ymmv.

One of the key developers on Windows Multimedia at Microsoft is Syon Bhattacharya.  Syon was responsible for many of the internal pieces of the multimedia work on windows, much of the core code was written by him.  If you've ever watched an AVI file, or seen a windows media player visualization, you've been running his code.

He started at Microsoft in June of 1995, straight out of college, and worked in the multimedia group his entire career at Microsoft.  Coincidentally, he also came from Carnegie-Mellon University (I know a bunch of the other developers from CMU that came at the same time as Syon, but didn't know him until I joined this group).

Syon was an extraordinary developer, he had an encyclopedic knowledge of the internals of the multimedia code.  When we were doing the code reviews for XP SP2, when I'd see something that I thought was a vulnerability, I'd wander over to Syon's office to ask him.  Syon not only knew the code I was looking at, but he was able to reconstruct (from his head) all of the code paths in which the potentially vulnerable routine was called.  He's the person that the multimedia team went to when they had tough problems - there didn't seem to be a problem that he couldn't solve.

In addition to being a complete technical wizard, Syon was one of the nicest persons I've ever worked with, his unflagging good humor throughout development cycles was legend around this group.

Two years ago, Syon was diagnosed with stomach cancer.

He continued to work, although it was clear that the treatments were taking their toll on him - I often saw him walking down the hall looking horrible, I'm sure that the treatments were hideously uncomfortable, but he pressed on.

Over the summer, Syon took a leave of absence to concentrate his energies on fighting the cancer that was eating away at him.

Unfortunately, yesterday he lost that battle, he passed away at a hospice in Seattle.  His family and friends were with him at the end, and it was apparently very peaceful.  He was 30 years old.

We will all miss him, the world is a smaller place without him.

Edit: I'll be adding recollections to this post as they come in...

I've asked my group (and others) to collect their memories of Syon, here's what they wrote (in no particular order):

Ji Ma:

I know Syon since I was transferred to DirectShow group almost 6 years ago.  He was hard working soul and low profile person and easy to talk to.  He has amazing ability to solve very tough computer problem and was always willing go extra miles to help others and he knows so much and so deep about computer and programming that he can solve almost anything that no other people can.  I found him to be indispensable dependent technical resources and ideas.  When ever I have difficulty or lack of idea, I will look up to him for help and he always let me a hand.

He was easy going and willing to listen and we had very good work relation since many of his developed work was tested by me so we interact a lot and we were truly perfect match to each other and great team.  Many times, I just went to his office and we chat about many things in life and he was always willing to listen and provide valuable comments and genuinely enjoy and appreciate the conversation.  It is very rare in the working environment.  I will always remember him for that.  

I have several fruit trees and some vegetables grown in our garden.  When it was harvesting time, I brought some to our group and passed to many colleges, including him.  He always admires and grateful to what he get, an apple or a tomato or what ever.  I can tell he true enjoy and appreciate the friendship that we had. 

He talks very little about his personal life so it is mystery to me and I only know he lives around green lake area. 

Syon, may you rest in peace and we will always remember you.

Tracy Shew:

When I first came to Microsoft as a contractor five years ago, it was sometimes difficult and daunting to work with developers.  These were, after all, the people who had written the code for Windows.  Many of them sometimes acted as if they were aware of this fact, and of the distinction between their station and mine – a mere software tester.  The tester – developer relationship can be antagonistic at times, particularly if I had the gall to find a bug or regression in “their” code.  Sometimes, some developers had little time for my questions, and acted as if my concerns were unimportant.  This was discouraging for me, and made me question why I was working at Microsoft at times.

Syon, more than anyone else, gave me encouragement to continue.  He was a developer, and he was brilliant, but he never – and I mean never – acted as if my concerns were unimportant.  His door was always open, and he always seemed to have the answer ready – or if not, he knew the person to go to.  And he never made me feel ignorant or inferior to him for having to answer a question.  I quickly learned that Syon was a valuable resource, a wealth of information.  But it was much more than that.  Syon taught me, through his example, that I was not a “mere tester” – that I was making an equally valuable contribution to the product.  This encouraged me to continue at Microsoft, eventually becoming a full-time employee in test.

I had the pleasure to work closely with Syon for almost four years, being the main tester responsible for checking his code.  Syon’s skill was unquestionable; problems were very rare, and, if one was encountered, Syon was extraordinary at quickly locating the difficulty – even if it was outside his area.  I do not know the number of times he has trudged over to the lab to look at one of our machines.  “Why is it doing that?” we would ask, looking at a bazaar error message or a garbled, incomprehensible stack trace.  I sometimes felt that we took advantage of his openness and generosity – not many developers will “dirty their feet” by coming into the lab to look at a sick computer, unless you can first prove it is their code at fault – they would rather have a remote, at the very least, or have you port the bug off to the “owner” – something which is sometimes difficult to determine.  I tried to use Syon as an “avenue of last resort,” lest we overuse the resource – if we absolutely couldn’t determine the issue, and know one else knew what was happening, only then would we bring in Syon.  And, in four years of steady work, day to day, I can count on one hand the number of times we managed to stump him.  And never, not on a single occasion, did Syon refuse help because he was too busy, or because it was not his area, or for any reason at all for that matter.

Since Syon’s illness took him away from work, there hasn’t been a week go by that this resource hasn’t been missed.  Very frequently, an issue will come up, and someone will say, “If Syon were here, we could figure this out.”  His combination of knowledge, intuition towards problems, and plain generosity in sharing what he knew is unequalled.  People often use the word “irreplaceable” when they lose a colleague, but for us there is no degree of exaggeration in applying it.

For me, though, Syon was more than a resource.  He demonstrated to me the value that I was contributing to Microsoft, and a vision of the partnership that should exist between development and test, and between teams, where “ownership” should not be used either as a dividing line to avoid issues, nor as a way of assigning responsibility or blame.  Syon simply loved making the best code he could, and he loved solving problems, so he saw all of our contributions, whether development or test, assisting in this process.  He encouraged everyone around him to do their best, and to be excellent.  I wished I could have known him better – losing him is a tremendous blow, certainly professionally, but also personally.  Even though we had a professional rather than social relationship – you would have to call us colleagues rather than friends – I am grateful to him for many different things, and especially for the encouragement he gave.

Eric Rudolph:

Syon always was a team player, and he ended up being the backbone of the DirectShow product at Microsoft. After many other people had been reorganized, or had moved on, Syon stuck with DirectShow and not only supported it, but he also supported it's customers and all the accompanying hassles. Not only did he do this really well, but he did it with a gracefulness and humbleness that made it seem easy. Syon knew everything about everything, he was the go-to guy when it came to something that nobody else knew. I don't know a single person at Microsoft (myself included) who wouldn't use that kind of responsibility as a bargaining chip to further their career, but not Syon. When I asked him, "why don't you try and promote yourself more?" He would say, "oohhhh, I guess I'm just lazy." But Syon was anything _but_ lazy. Maybe unmotivated for self gain, but that was one of the things that was cool about him. On a personal note, Syon wasn't easy to get too close to, but I'm proud to count myself among his friends, and he was always up for doing anything. He was my personal movie critic, if I wanted to know if a movie was good, Syon was the first person I would ask. He was an amazing guy, and the effects of who he was and what he did to help people, will ripple outwards forever. I respect him immensely, he taught me many things while I had the chance to work with him.

Martin Puryear (Dev Manager for WMDG): 

Syon was one of those rare selfless people that willingly took on any task without a complaint, regardless of the task.  Sometimes the most important tasks are the most tedious as well - ensuring that myriad far-flung fixes were ported back and forth between different OSes; painstakingly crawling through very old Windows source code looking for security vulnerabilities.  I'm fairly certain that I never heard him ever utter a complaint - if he did, then I'm sure it was accompanied with a smile that seemed to say "well, these things happen." 

 Syon was a sterling example of the phrase "still waters run deep."  Over the years he built up considerable expertise in the multimedia arena, but you might not know it from watching his actions.  He always made time to help others, answering even the most basic questions.  Upon asking, one quickly discovered that he understood the overall system and how your question related - and he usually knew the technical details that you needed as well.  After RobinSp himself (overall architect for quartz/ActiveMovie/DirectShow), SyonB was the one to which we repeatedly went with hard problems facing that architecture. 

 Syon didn't have the "rough edges" sometimes found in SW engineers (including the stereotypical MS developer).  If you were wrong, he would couch his words with a soft-spoken "I believe the way it works is…."  He didn't have an egotistical bone in his body - in fact it was understood among managers that we needed to make sure that he got the recognition he deserved. 

 Syon was a class act - in this day and age, the industry needs more like him.  Truly, the world needs more like him.  He will be sorely missed as a coworker and a friend. 

Steve Rowe:

Tuan Le: