/dev/why!?!/dev/why!?!http://www.devwhy.com/blog/2012-06-19T04:56:42ZSquarespaceDeveloping a Bluetooth Low Energy Device for iOShttp://www.devwhy.com/blog/2012/6/19/developing-a-bluetooth-low-energy-device-for-ios.htmlLouis Gerbarg2012-06-19T04:55:23Z2012-06-19T04:55:23ZOn Sunday my partner and I launched our new product Hone on Kickstarter and we've been getting a lot of great feedback and questions. I wanted to address some here with more technical information than is appropriate for Kickstarter, and discuss some of the underlying technology.

What is Bluetooth Low Energy

Bluetooth Low Energy, or BLE, is a new technology designed for low data rate wireless applications. It enables smart devices to run for months on small batteries. Despite the name, it isn't a slight modification to Bluetooth, but rather a completely new protocol with all-new radio hardware. A Bluetooth 4.0 chipset is basically a Bluetooth 3.0 chipset and a BLE chipset stapled together.

Why BLE

BLE was the enabling technology that made Hone possible. Recharging a key fob every few days means you probably won't have power when you need to actually find it.

Deciding on BLE limited us to support for iPhone 4S and the new iPad. We've been getting requests to support older iPhones and iPod Touch, which we can't do with BLE; we came down on the side of battery life over legacy compatibility. Given every new Apple design supports BLE, we think it's the right choice for Hone.

Android

In addition to questions about other iOS devices, we've seen a lot of interest from people wanting Hone to work with Android. We are iOS users, but we aren't ideological about it and if a viable market for our product exists, we want to support it. Unfortunately we can't support Android at this time. The simple reason why is fragmentation.

When people talk about Android fragmentation they usually mean supporting multiple releases of Android and different screen resolutions. All of that is a lot of work, but it is tractable if the expected sales are high enough. In the case of BLE, Android is in much worse shape. Google has yet to include a BLE stack as of Ice Cream Sandwich. That has not prevented a number of vendors from shipping Bluetooth 4.0 capable hardware in their phones, but the situation is a mess. Some vendors turn off their BLE radios and simply label the devices as BT 3.0. Motorola shipped their own BLE implementations. Some vendors may be using BLE implementations provided by their chipset suppliers, such as Broadcom.

That leaves us in a horrible position. We don't even know how to describe to consumers which Android phones would work short of explicitly listing the models and in some cases the specific OS releases running on those models. We'd have to implement and test two full sets of BLE code to support the limited percentage of Android phones we could work with, and probably a third set if and when Google adds support in the base Android distribution. We would not be able to drop support for the legacy stacks even after Google releases an official one, as there would still be a lot of deployed devices that either won't or can't be upgraded.

This is a problem that may resolve itself if we wait. Hopefully Google will add support for BLE in the base Android distribution, maybe for Jelly Bean. At that point we could use the default implementation and only support Bluetooth 4.0 capable handsets running that release. This is something we intend to actively re-evaluate with each Android release - hopefully at some point in the future it makes sense.

Integrating with other devices

Now, having just gone through why we are not going to provide an Android app at this time, I want to make it clear we want to integrating with other devices where supporting them makes sense. We are very interested in integrating with Pebble, for example, and have discussed it with them.

We also intend to publish enough details about how Hone works that anyone who has a device that acts as a "BLE central" can write software to use Hone. Hone uses a custom UUID and advertising packet, but otherwise it employs standard BLE pairing and publishes Immediate Alert Service and Battery Service. We'll publish more specific details before we start shipping, once the firmware is final.

Electronic leashes

One of the other features people have really taken an interest in is our proximity detection. We think it's cool too, but there are misconceptions about what it can and cannot do.

One request we had was from an engineer who wanted to have his computer start and stop playing music when he enters his office. While we are not going to support it, it should be doable using the information we're going to publish. All he should need to do is write a daemon for his computer that watches for Hone's broadcast packets, which contain information about the strength they were broadcast at, compare it to the apparent strength of the incoming signal and use that to estimate distance. Tuning the exact numbers for general usage is tricky, but for a single fixed setup it should be easy enough to figure out by trial and error.

The most important thing to remember about this is that it isn't geofencing. If you place Hone on your dog's collar we can't tell when it has left your yard unless your yard is circular, has no obstructions, and you place your iPhone in the middle of it. Also, unless you keep the Hone app running we can't prevent it from being evicted from memory on an iPhone if your foreground apps need the memory. That would result in the leash randomly failing to notify users, which defeats the purpose. Again, if users want to try to make it work with the technical information we provide then we think it is really cool, but since we cannot make it work simply and reliably we are not going to do it.

In conclusion

We're very excited about our project and the response it's generated so far. We're also really excited about BLE in general and other devices using it, such as Pebble and Find My Car Smarter. Our goal is to keep Hone simple and easy to use, which means passing up some neat ideas. We think providing information for hackers is a reasonable compromise for now, but keep sending us your ideas - just because we haven't figured out how to do a feature in our initial release doesn't mean we won't in the future, especially if there's a lot of demand for it.

If you want to get Hone for a special pre-release price you can make a pledge and support our Kickstarter here.

]]>iPhone, iPad, Security, and Privacy. Oh my!http://www.devwhy.com/blog/2010/4/23/iphone-ipad-security-and-privacy-oh-my.htmlLouis Gerbarg2010-04-23T13:11:07Z2010-04-23T13:11:07ZIntro

Plenty of people are debating the significance of the iPad. Opinions range from those who believe it represents the future of computing, to those who think it is just a toy or a diversion. There are lots of aspects to these new types of devices, and any discussion about their impact that would necessarily look at a lot of different issues.

Personally, I find the iPad very interesting for many reasons, though most of them are probably different than what excites the average consumer. One of the aspects I find most exciting is that the iPad (and iPhone) represent a new platform that has been designed from the ground up in such a way that they can avoid a number of the security problems that have plagued computers in past, problems that cannot be fixed because legacy operatings need to support legacy applications that cannot be made to work securely. This is a key advantage of these new platforms, but it is also one that could easily evaporate if Apple is not careful as it designs and implements new APIs.

In this post I am going to walk through a brief history of computer security, an explanation of why iPhone OS can be more secure than Mac OS X or Windows, describe some API flaws in iPhone OS 2.x/3.x that reduce user security, and explain potential exploit vector in iPhone OS, and ways they can be fixed. Finally, I will take a quick look at some of the features announced at the iPhone OS 4.0 event, and their potential security and privacy implications, though I will not discuss their actual APIs or any specific analysis I have done.

It should be noted, that I do not, and have never, worked professionally in software security. Having said that, everyone who writes software needs to be concerned with these sorts of issues and have some expertise with them, especially people who deal with any potentially sensitive data. It should probably also be noted that most of the issues I am about to raise are not security issues in the traditional sense (they are technically privacy issues), but to the end user they are the same thing. It doesn't matter whether a nefarious application gets personal information by exploiting a bug, or because the system was designed to let applications get that data.

In the beginning

When the first computers were built, security was a non-issue. Early computers took teams of people to operate, could only input and output through switches and lights (and slightly later terminals), could only run a single program at a time, and that program was generally written by the people operating the machine.

Over time the machines were enhanced, but for decades they were very expensive. As any buisness person will tell you, if you have an expensive fixed asset sitting idle you are wasting money, so people needed to find ways to keep those machines utilized. The first common way to do this was through batch processing. With batch processing you would write a program, and send it to the computer. When the computer finished one program the operators would take the next program from the queue and run it immediately. This had the benefit of keeping the computer busy, but it had some pretty substantial downsides as well. The most obvious one (in hindsight) was that it was impossible to deal with the computer interactively. If your program had a bug, you couldn't just fix your program while it was on the computer and rerun it, you would wait until you got the batch results, fix the bug, and put it back in the queue, and wait another day until it was scheduled to run again.

The benefits of interactive computing were pretty obvious once it was technologically feasible, but that still didn't solve the cost issues. A new way of sharing computers had to be invented: Time-sharing. In a time-sharing system, the computer runs multiple programs at once, and keeps switching between them. If a program isn't using its timeslice (because it is waiting for the user to type something, for instance), it can yield its time to other programs. One of the first such systems was MIT CTSS. CTSS was arguably the first OS to resemble what we now call a modern OS, and among other significant achievements, it hosted the first known electronic mail implementation, the first interactive shell, was the first computer to run background only daemon processes, and the first system to use a virtual machine to support legacy applications. In fact, you can track iPhone OS's lineage back to it: iPhone OS -> Mac OS X -> BSD Unix -> AT&T Unix -> Multics -> CTSS.

One of the other things that became obvious once time-sharing came into being was that it changed fundamental assumptions about how computers, and the programs they ran, worked. In order to even demo the first time sharing code the IBM 704 at MIT required hardware changed to support interrupts. Before CTSS was implemented several other modifications were made to allow for memory relocation (early virtual memory), and memory protection. This changed what had previous been invariant assumptions about the environment in which a program ran, and resulted in CTSS having a slightly more dubious distinction. CTSS wass the first operating system to have a known software security issue.

Enter the sandbox

Until that point, all software had been written assuming it was the only software running, and programmers had never had to consider the issues involved when multiple programs ran. It was clear that some sort of mechanism to isolate users would be advantaguous, but since the segmentation and protection mechanisms were retrofit into an existing piece of hardware they were not necessarily as flexible or well thought out as one would hope.

The relocation and protection features IBM added to the 704 allowed CTSS to implement the first ever sandbox. A sandbox is a small virtual world within a computer. The important thing to understand about the a sandbox is that once something is in a sandbox, it cannot get out of the sandbox (absent a bug or design flaw in the OS). Unfortunately, since those features were retrofitted into an existing (deployed!) piece of hardware they were not as flexible or well thought out as they might have been, which meant there were ways in which to breach the sandbox. Despite those design flaws, the security issue that occured was not due to breaching a sandbox. It was instead due to a race condition that existed because of the assumption that only a single program would run at the same time, and an administrative decision allowing two users to play in the same sandbox.

What happened was that there was a single system account that multiple people needed to login to in order to do system maintenance. When two admins both logged in, they were both inside the system sandbox. In addition to that, the editor software assumed only one copy of itself could be running at a time, so it stored its temporary data fixed location. One day two people were logged in doing two unrelated system tasks, one was editting the message of the day, the other was modifying user account information by editing the system password file. Since both of their editors were using the same temp file, the system system password file ended up being written out as the message of the day, and everyone who logged in could see everyone else's passwords. This incident also resulted in the idea of using hashed passwords.

Evolution

After CTSS, a number of time-sharing systems came into existence, but given iPhone OS's lineage, it is best to look at how Unix handled this situation. Unix was an OS inspired by Multics. By the time it came into existence hardware had evolved enough to support isolating user processes in a fairly robust manner. The world was still pretty different back then. Computers will still expensive, they still tended to have dedicated administrators, and the amount of software available for them was still pretty small compared to today.

While the notion of a hostile user certainly existed, most of the software you were running was likely to have been provided as part of the AT&T Unix distribution (and later the BSD Unix distribution), or written in house. Networking still wasn't prevelent. As a consequence, when Unix was designed the goal was to sandbox off the users from each other, but no effort was made to isolate any of a user's data from a program they themselves ran. This is a completely different than the environment of the average user today, where most systems only have one user accessing them at a time, and are running lots of third party code of unknown provenance.

Mac OS X is a modern version of Unix, and as such it inherits Unix's basic security design. The result is we have a system which has great support for isolating things into seperate sandboxes, but for the most part everything runs in a single sandbox (the user's account). The unfortunate thing is that most programs need to run in the same sandbox, because the way the Cocoa API's are designed they won't function properly if they are not. In many cases the necessary API changes to secure things are difficult and incompatible with existing applications. Since Apple has no way to analyze all existing software, force developers to update their apps, or provide compatibility without opening up the exact same holes they would want to close, they can't fix them with long difficult transitions.

The situation on the iPhone is far better, but there are still some very serious issues. iPhone OS shares much of OS X's code, but it is a new platform that does not need to maintain compatibility with all the software on Mac OS X that depends on now invalid security assumptions. iPhone OS can fix them without the pain of breaking old software, but if Apple is not careful it can just as easily make the same mistakes again.

The CoreLocation and Address Book APIs

So lets look at two APIs available on iPhone, the CoreLocation API, and the Address Book API, as an example of where iPhone has screwed up its security, and an example of where iPhone has gotten it right.

CoreLocation

There are obvious privacy concerns with applications being able to determine a user's location. Apple handles this from a user perspective by asking the user if an application should be allowed to access their current location. What happens under the hood was that if CoreLocation access is approved by the user, CoreLocation signals over to a background service (running its own sandbox) asking for the location information. That service would check the system preference, confirm the app asking for information was allowed to have it, and send it back.

That is not to say that CoreLocation was perfect in iPhone OS 2.0. While the basic design was right, it turned out that Apple actually cached location data inside the application's sandbox in a way that allowed it be accessed using private APIs. As a result, it was possible to get a (sometimes stale) location without the user knowing. Apple stopped caching the data, and now all CoreLocation access is gated messaging the background service. Fixing this particular bug did not break any apps that were using the CoreLocation API, since the API has always been able to return an error saying there was no access, so all apps using CoreLocation have always had to deal with the fact that sometimes the user does not give them access. Obviously the apps using the private APIs broke, but that is a separate issue.

In iPhone OS 4.0 this is being greatly improved, so much so that the improvements were demoed in the keynote. In 4.0 there will be a status bar indicating that an app has recently used CoreLocation, it will be possible to look at the list apps to see what has used your location in the las day, and turn on and off their access. All of this works without changes to the existing APIs, so all existing apps the CoreLocation will be effected, resulting in much better security of the user's location information, and the ability to notice and identify if something is using the data without your consent. For more details people can watch the event stream.

AddressBook

Now lets look at the address book. The AddressBook API is basically the opposite of CoreLocation, in that Apple completely botched the security of the API, and the implementation, on multiple levels. The mistakes are so deeply ingrained that they cannot be fixed in any meaningful way without break a ton of apps. For that reason, the only viable options are to leave it broken, or fix it incrementally over several releases.

The most obvious failure is that there are no controls on what can access your address book. Any app can read the address book, and there is no visible indication to the user, no log of the events, and no way to turn it off. In addition to that, all software currently using the address book has an implicit presumption it can read and write to the address book. This has actually caused fairly public incidents, such as the original Aurora Feint incident. In that case it was noticed by people monitoring network traffic of the app after it had been approved for the store, and the app wasn't actually trying to do anything malicious. An app actually trying to steal that data could encrypt its transmissions, and hide what it is doing in such a way that Apple would not notice it during the approval process. Fixing the API is not simple, because if the existing API were changed such that it could return an error most apps would be unable to cope with it, and either crash or behave unexpectedly. An option might be fore the OS to return an empty address book to such apps, but that could cause some serious problems for users as well.

Even ignoring the API related issues, the infrastructure for restricting access to the address book doesn't exist. Rather than keeping address book database in its own sandbox with a daemon to arbitrate access, Apple exposes the address book database (/var/mobile/Library/AddressBook/AddressBook.sqlitedb) into all sandboxes and the API they provide directly accesses it. That sounds similiar to the above story about CTSS and the motd, though we have 40 years more experience and address book handles concurrent access to the database just fine. In an environment with no malicious apps that would be fine, but that is not the environment we live in. By exposing the address book database in this way not only has Apple introduced a way for applications to read all of the address book data without going through the AddressBook API, they have also exposed an attack vector for applications to insert poisoned address data that can be synced back to other device, or even attack other applications inside their own sandboxes.

By carefully constructing a malformed address book database file it may be possible to exploit bugs in either sqlite3, the AddressBook API, or the code of a specific application stack in order to corrupt their stack. At that that point it is possible to run arbitrary code using a return-to-libc payload, despite countermeasures like an non-executable stack. All the app has to do is overwrite the users address book database with the new one, then the next the user runs a targetted app that accesses the database the exploit can occur. To be fair, sqlite3 is heavily vetted against malformed files, but that is no guarantee that this is not possible, and by directly accessing the database Apple has added an potential exploit vector that just doesn't need to be there.

What I want to see in the future

Well, the first thing I want is for Apple to expose the same sort of UI for managing AddressBook as exists for CoreLocation. I want notification when things are accessing it (especially when apps are writing to it). Furthur more, I want it to be possible to turn off an app's access to the address book, despite the potential for current apps to break, since I would rather risk the app crashing then it stealing information or inserting information. I want the API expanded to support read only and read/write access. As a compatibility measure Apple should default to permissive access to the address book for 4.0 using the existing APIs (that way no apps would break unless the user explicitly denied access). In addition, Apple should start testing all 4.0 apps submitted to make sure they operate correctly when address book access is denied. That way, when 5.0 comes out all apps submitted in the previous year will work correctly if they change the default to asking the user for access and the user tends to deny access.

I also think there is room for some significant improvements to the UI features added for CoreLocation privacy in 4.0. Aside for the basic UI for notifying users about access, the system should log accesses somewhere that is accessible via iPhone Configuration Utility. Also, if Apple adds the ability to control address book read and write access there may be a need to rethink how to layout the UI in the Settings app, as having seperate table views for Push Notifications, Location, Address Book (read), and Address Book (read/write) is excessive and unintuitive. It would probably better to have a single app security table where each app should a synopsis of what it was trying to use, and could be expanded in order to inspect them more closely and edit them. Ultimately I trust Apple's abilities to create a UI that can handle presenting the necessary information to the user, that is the sort of thing they excel at.

While I am at it, I also want applications to state up front what they want access to, rather than asking me as they access them. This could be handled by embedding it as metadata in the application's plist. That way the first time an application attempts to access anything that requires permission the OS could bring interface for approving everything at once (instead of multiple dialogs as accesses to different services happen).

Why did I decide to write this blog post

I decided to write this blog post because I think iPhone OS is at a crossroads, where it is either going to end up with up as a much more secure platform then we currently have, or it could end up throwing away all of that progress. This is especially important if the iPhone OS ends up being the basis for most of my computer usage through products like the iPad. Its fundamental sandboxing design allows it to be much more secure, but in order for that to remain the case Apple has to carefully vet every API that allows access to user data, and provide the user ways to control that access. At this point there are a fairly limited amount of data exposed to applications:

  • Location
    • Well secured
  • Address Book
    • Insecure
    • No worse than on Windows or Mac OS X, but it could be better
  • iTunes database metadata
    • Insecure
    • Not particularly sensitive
  • Camera access
    • Currently imited to Apple provided UI (see below)
    • Can be globally turned off via iPCU).

The thing is, Steve announced some very exciting features for 4.0 that have potential privacy concerns. As you can see from my artistic rendition below, there are 3 features I want to call out. They are:

iPhone 4.0 Privacy Risks

  • Calender
    • If knowing where I am is a privacy concern, then knowing where I am going to be certainly is)
  • Photo Library Access
    • Apps stealing your photos and uploading them to a server is a very real privacy issue, just wait until apps can read all the photos and movies you have taken without going through the OS's UI.
  • Raw access to the camera data
    • This a particularly nasty one, since iPhones do not include visible indicators that the camera is turned on. A similiar issue has been the subject of a recent lawsuit in the Lower Merion School District. In that sort of case the situation is even worse, because companies and schools can create their own applications under the iPhone Enterprise Program, that don't have conform the public API or be vetted by Apple, eliminating any safety derived from Apple's approval process.

It is important that all of these APIs are designed in such a way that they can expose restricted access to apps, since if apps can simply pull all of this data with no restrictions then we have effectively given up a lot of the value of the sandboxes. After all, who cares that apps can't get out of their sandbox when all the user's personal data is right there for them to play with. Apple needs to use their sandbox not just as way to protect the integrity of the OS on the phone, but also to protect the privacy of the user's data.

(For any Apple readers, please check out these 6 radars).

]]>Its all about the framework…http://www.devwhy.com/blog/2010/4/12/its-all-about-the-framework.htmlLouis Gerbarg2010-04-12T05:05:39Z2010-04-12T05:05:39ZSection 3.3.1

There are a lot of posts right now about Flash and iPhone. It is pretty heated, a lot of people have very real amounts of time and money tied up in this. I am an iPhone developer, so I am not going to reveal anything covered under NDA, but the text of the relevant license changes has been widely disseminated. Based on my reading of the aforementioned text, I have a few opinions.

In my opinion this is not purely aimed at Flash, but it is certainly precipitated by Flash CS5. I can't imagine Apple is happy about environments like MonoTouch, Unity3D, PhoneGap, Appcelerator, or Corona, but I am doubtful they would have changed the license in this way just to stop developers using those environments. Some of the people using those environments actually claim they approve of Apple blocking Flash, and are complaining that their tool of choice is merely collateral damage. I think that is very naive, Apple probably doesn't want these environments, they just weren't motivated to stop them until it was clear Adobe was going to pursue Flash apps on the iPhone despite Apple's wishes. They are not collateral damage, they are opportunistic targets that Apple decided to kill once they decided they would have to take action to stop Flash as an iPhone runtime environment anyway.

The more interesting thing from my standpoint is that this makes it a license violation to include a language interpreter inside a game. If you aren't a game developer you might not be familiar with how large games are structured, but most games consist of a game engine, which is high performance code for doing things like rendering graphics, and an interpreter which runs the game logic (determining how sprites move, determining when to pop up in game text boxes, etc). This is how practically every commercial RPG works, as well as many (most?) other types of games. This affects major app store publishers, like EA, Gameloft, Tapulous, and ngmoco:). Looking at the top ten lists on the app store right now I see several titles that I know have embedded Lua interpreters. In this case I think these apps are genuine collateral damage, though I honestly doubt Apple would attempt to enforce the clause against them. In fact, using an interpretted language for game logic is already technically in violation of section 3.3.2 in the current agreement, though many developers may not realize it because under the original agreement it was okay, and the change that made it verboten was very subtle (changing an "and" to an "or"). I am actually not sure exactly when that changed, and only noticed it myself while I was researching this blog post.

Why doesn't Apple like 3rd party runtime environments?

People have speculated about why Apple doesn't like these 3rd party runtimes. The general conclusion is that Apple craves control over the user experience. While they do want control over the user experience, that is generally not a reason to object to 3rd party tools. After all, the majority of developers using these tools are using them to write games, many of which present their own user experience written completely in OpenGL even when using Apple's tools.

What Apple does care about is their ability to control their own development cycles. iPhoneOS runs on extremely tight schedules, with a very high degree of secrecy, and at a pace completely controlled by Apple. I know it is popular to claim that maintaining binary compatibility is easy, that is the argument du jour made by people claiming Apple should just support developers using private APIs. Well, they are just wrong. Ask anyone who has been involved with a couple of releases of Mac OS or Windows about the amount of effort involved in keeping old apps working, especially those using private APIs. There is a reason why the majority of current and former framework engineers who comment on the issue come out really strongly against any use of private APIs. To really delve into what it takes would be an entire blog post.

So, if you will indulge my claim that backwards compatibility is hard (even absent the private API issue) it is pretty easy to see why supporting other runtimes is ceding a lot of control to a 3rd party. Imagine if 10% of the apps on iPhone came from Flash. If that was the case, then ensuring Flash didn’t break release to release would be a big deal, much bigger than any other compatibility issues. Since Apple doesn’t have access to Flash CS5’s runtime library code or compiler frontend, they might be put in a position where they would need to coordinate with Adobe to resolve those issues. Shipping a new release where Apple breaks any specific application, even a top seller, is not an issue if the release is compelling, most apps work, and Apple has the option of working with the vendor to help them fix their app. Shipping a release where they break a large percentage of apps is not generally an option. Letting any of these secondary runtimes develop a significant base of applications in the store risks putting Apple in a position where the company that controls that runtime can cause delays in Apple’s release schedule, or worse, demand specific engineering decisions from Apple, under the threat of withholding the information necessary to keep their runtime working.

This isn’t some perceived risk, I can think of incidents where Apple reverted OS changes, dumped new APIs, or was forced to committing massive engineering resources to something it did not want to do because a Must Not Break™ app vendor told them to. Apple does not want to give anyone that sort of influence over them. So ultimately, preventing Flash on the platform is about control, but is not control over the user experience of the Flash applications, or even the languages used. It is about the runtimes they bring on to the system, and Apple's control over future releases of iPhone OS.

So who is to blame?

It is easy to blame all this on Apple, and you will find no end of blogs screaming about their monopolistic power-hungry tendencies. I certainly agree that Apple should probably be more open, and that they are the party with the power to resolve this. If people want to complain about that, you will not hear me defending Apple. The developers using Flash, Unity3D, and MonoTouch have my sympathy, and I understand their anger with Apple. The Adobe evangelists writing screeds get none though.

The reason is that I think Adobe holds much more of the blame. Adobe is a large company with a significant, and complicated, relationship with Apple. They have frequent high level contacts and meetings. Adobe has known for quite some time about Apple's desire not to have Flash on the iPhone. There is no doubt in my mind that if they asked Apple to bless this they were rebuffed, and if they didn't ask the only reason they didn't was because they knew Apple would say no. In either event, they announced the product to their customers and sold them on an idea they were not in a position to deliver, hoping Apple would be unwilling to piss off developers by not fulfilling Adobe's promises. They tried to force Apple's hand by putting Apple in a position where in order stop the Flash they would have to do it publicly in front of Adobe's users. That was a bad call on Adobe's part.

Personally, in this whole thing the most distasteful part is that Adobe used its userbase and their livelihood as a bargaining chip. These kinds of high stakes negotiations have happened in the past many times. They are much more common than people think, and until the last few years Apple was more likely to be on the weaker side of the negotiation. The story of MacBasic is a classic example, but I can think of other (not publicly disclosed) incidents involving Adobe and Macromedia (which was acquired by Adobe, and is where the Flash team comes from) applying extreme pressure to Apple. This is the only case where I feel an active user community was publicly jerked around like this in order for one side to try to gain leverage over the other. That is saying a lot, because I am not pleased with Apple's actions either, but Adobe put Apple in a position where either Adobe got its way or Apple screwed developers.

What Adobe can do

If Adobe actually wants to persuade Apple to support Flash on iPhone (either as a plugin or compiled to native apps), I know how they can do it. They can get an awesome, high performance, Flash environment working on Android, and get a bunch of great Flash apps running on Android phones. As much as Apple wants to control iPhone, I am willing to bet they want to beat Android more. Currently Adobe is asking Apple to put Adobe in a position where they wield influence over Apple, in exchange for the promise of apps in the future, apps that Apple thinks will be low quality. That is a bad deal. On the other hand, if Adobe proved the apps were high quality by deploying them on competitor's platform, and was offering a library of existing high quality apps that neutralized another competitor's advantage, then there is enough value that Apple probably could be influenced.

I hear that Flash Player 10.1 is the real deal, and it is going to work fairly well on the HTC EVO 4G. This is an oppurtunity window that is quickly closing. If Adobe had delivered a decent solution two years ago it would have carried a lot more weight, but at this point Apple has managed to cultivate its own 3rd party apps, and convince a lot of major sites to support html5. Every day Adobe does not have a widely deployed mobile Flash, is a day they are not having Flash based mobile apps developed, and is a day the odds of mobile Flash being successful goes down a little bit.

If Android was making significant gains against Apple, and all of its best apps were Flash based, then Adobe could offer Apple access to all of Android's best apps, which would give them a lot of power. The fact is that there have yet to be any widely deployed Android phones that support Flash. That's right, Adobe has been making the case for Flash on iPhone for 3 years, but still hasn't deployed a non-lite version of Flash on any phones, even when Apple is not obstructing them.

What I want from Apple

I am comfortable with what Apple has done with Flash, it doesn't change my view on the platform. It sucks for some developers, but there are not a large number of deployed apps out there. If I were Apple, at this point I would not want to allow Adobe’s tools explicitly because of how they have acted. If this is the kind of crap they try to pull when they don't have influence over Apple through being a major toolchain vendor, imagine the kind of crap they could pull if a substantial portion of the apps on the store were dependent on them. Note that this has nothing to do with the performance or features of the apps themselves.

I would like Apple to find a way to work with the existing vendors who have (for the most part) been good citizens, and find some way to let them continue. As I said above, I suspect Apple doesn't like their runtimes on the iPhone, but there is still some value in those platforms and I would like Apple to find some way to support them. I think Apple can probably achieve the control it wants over the runtime, and allow for more language flexibility than current license allows.

Apple should also find some way to loosen the license to officially allow games to use included interpreters for their internal logic. I don't know how to do that without opening up loopholes, but that is what lawyers are for. If they don't do that then effectively they are just using their discretion on a case by case basis, which is completely legitimate, but causes significant uncertainty for developers. Ideally Apple should have some provisions for adjunct or secondary runtimes that let developers use internal scripting. Failing that, Apple should include some language interpreters on the system that games can use for their app logic. While not as flexible as letting games include their own interpreters, if Apple exposed JavascriptCore outside of UIWebView, and included a Lua interpreter in the base system it would solve this as practical a issue for many games.

Oh, and while I am at it, I want them to do a rapid development tool aimed at light apps. Having a rapid development tool that could be used by non-programmers would probably quench some of the desire for Flash, which is largely driven by the ability of designers to actually create functional apps without significant programming resources. While we are at it, it should run right on the iPad. In other words, I want "HyperCard Touch." And a pony.

]]>New themehttp://www.devwhy.com/blog/2009/10/28/new-theme.htmlLouis Gerbarg2009-10-29T00:45:00Z2009-10-29T00:45:00ZI have changed the this blogs theme since a number complained that it was hard to read light text on a dark background. I am still fiddling around with them template, so if something is broken, that is probably why.

 

]]>The loss of ZFShttp://www.devwhy.com/blog/2009/10/24/the-loss-of-zfs.htmlLouis Gerbarg2009-10-24T17:03:00Z2009-10-24T17:03:00ZWell, in case you haven't read any of the myriad stories about it, it appears that Apple has decided not to use ZFS on Mac OS X. Gruber has sources that say it was primarily licensing concerns, which is consistent with what people have implied to me, both recently, and around WWDC (although at that time I think there was probably still hope of resolving the issues).

Now, some people jump may comment that it couldn't be licensing issues, since ZFS is opensource (under the CDDL), and that Apple already uses CDDL software (DTrace). That may be true, but often in deals that involve large companies there is more to it than that. Apple may have wanted guarantees of indemnification in the NetApp lawsuit. Maybe it wanted guarantees that certain modifications it wanted to make would be accepted upstream, or even to get Sun to make certain changes. It also might have wanted additional distribution rights that were not granted under the CDDL. It is typical for companies to negotiate custom agreements in such cases (and for some money to change hands), so the idea that licensing issues are why it fell through is entirely reasonable, even though it is an opensource product. Obviously Sun's steady decline in the market place, and the uncertainty caused by the Oracle acquisition may have greatly complicated any such negotiations.

Why not do a new filesystem?

Apple has a lot of talented filesystem engineers. They are certainly capable of doing something comparable to ZFS, at least for their target market. The problem with developing a new modern filesystem is that it generally takes longer than a single OS release cycle. Most companies are really bad at having large teams focused on projects that will not ship in the next version of the project they are working on.

This is a particularly acute problem at Apple, which traditionally has done things with very few engineers. I don't want to get into exact numbers, but I recall having a discussion with the head of a university FS team who was discussing the FS he was working on. He was pitching it to a group of Apple engineers. It was some interesting work, but there were some unsolved problems. When he was asked about them he commented that they didn't have enough people to deal with them, but he had some ideas and it shouldn't be an issue for a company with a real FS team. It turned out his research team had about the same number of people working on their FS as Apple had working on HFS, HFS+, UFS, NFS, WebDAV, FAT, and NTFS combined. I think people don't appreciate how productive Apple is on a per-engineer basis. The downside of that is that sometimes it is hard to find the resources to do something large and time consuming, particularly when it is not something that most users will notice in a direct sense. That is especially true if senior management is not excited about the idea.

Because of that, I was fairly convinced ZFS was a credible future primary FS for Apple. Not because it was an optimal design for them (it isn't), but because it was a lot less work than doing a new design from scratch. The fact its fundamental architecture is 20 years newer than HFS meant it would still be better than HFS+ in almost all respects even if it was not designed for Apple's exact needs. Clearly I was wrong, since Apple has stopped the ZFS project.

What changed?

Well, a couple of things have happened. The first is that Mac OS X has gotten more mature. They no longer need to port all of those FSes, they already have them working, and in most cases they work fairly well. That frees up some engineers. Apple has also greatly expanded the number of people working on their kernel since it is amortized over many different products (Mac OS X, iPhone, AppleTV, etc).

Suddenly the notion of doing a new filesystem seems doable, so long as it is a real priority and the FS team doesn't get pulled to keep adding features or doing major work to legacy FSes. That is still a lot of work when Apple had ZFS approaching production quality on OS X.

Apple can do better than ZFS

Sun calls ZFS "The Last Word in Filesystems", but that is hyperbole. ZFS is one of the first widely deployed copy on write FSes. That certainly makes it a tremendous improvement over existing FSes, but pioneers are the ones with arrows in their back. By looking at ZFS's development it is certainly possible to identify mistakes that they made, and ways to do things better if one were to start from scratch. From where I sit, there are 3 obvious ways doing a new FS will be better for Apple than ZFS:

  1. There have been new fundamental research since ZFS was designed that simplifies many of the issues involved with it. In particular the "B-trees, Shadowing, and Clones" (PDF). That paper is the basis for the design of BtrFS, which has a very similar feature set to ZFS, but internally is entirely different. LWN has an article about BtrFS that explains the significance in some detail (it is written Valerie Aurora, who worked on ZFS at Sun).

  2. ZFS was designed for the storage interfaces available a decade ago. Spinning disks are going to be with us for a long time, especially for bulk storage in data centers and on backup devices. The future is all about solid state. Flash SSDs have significantly different performance characteristics than spinning media, and there may be FS design decisions one could make that would benefit from that. Now, any FS Apple designs will have to work acceptably on traditional drives, but if they are designing for the future then flash is what to target.

    ZFS has had some optimization work for flash, but it is all in terms of using flash as part of a storage hierarchy. That makes complete sense, since ZFS's primary deployment targets are high-end systems and data center storage. Those systems have multiple drives, so the idea of separate flash drives for a ZIL and L2ARC are completely reasonable. Most consumers have one drive in their system, and maybe an external drive for bulk data, data exchange, and backup.

  3. That brings up the last point. ZFS is designed for big systems. It works on small systems, but most of the tradeoffs favor very large computers, with lots of drives. This shows up in a number of ways. The first is that ZFS is not currently capable of adding single drives to an existing vdev or migrating vdevs between various types (mirror, raidz, raidz2). This is a major feature for smaller users who might want to add a single drive, but is a non-issue for data center users who tend to add large number of drives all at once, since they will add whole vdevs. Another issue is that ZFS assumes you have a lot of ram. NEC has been doing a port of OpenSolaris to ARM, and they determined they could not get ZFS to use less than 8 megabytes of ram without making incompatible format changes (Compacted ZFS). With those changes they could squeeze it into a more reasonable 2 megabytes. On a desktop that doesn't seem like a big deal, but on an iPhone 3G or a Time Capsule 8MB of wired memory is an enormous issue.

The only major downside is that if Apple is just starting on a next generation FS now it could be a long time before we get our hands on it.

But now we are going to have another incompatible next generation filesystem

Wolf brought this point up during some of the ZFS talk on twitter yesterday. My general opinion is that it doesn't matter. People use drives for two largely unrelated tasks. One is running their computers. This is fixed storage. The other is for data exchange. In the old days people used floppies for their sneakernet media, which made the situation much simpler to understand. In recent years the market realities have caused people to move to using SD cards, thumbdrives, and hard drives as the exchange medium of sneakernet.

The important point is that understand is that while the physical devices may be the same, the use model is different, just as the using a floppy disk and an internal hard drive were different. Nobody would balk at the notion that floppies should use different FSes than internal drives. Likewise, most people shouldn't care that their external drives are formatted differently than their internal drives.

There are complicated features you want for your boot drives and system disks. Ideally you could have them on your interchange disks, but there are other features that are more important, particularly interoperability, and simplicity. ZFS didn't bring either of those. There might have been a few people who were psyched to be able to use ZFS to share disks between a Mac and a Solaris or FreeBSD box, but honestly those people are few and far between. Whether Apple used ZFS or something else it is just as interoperable with Linux and Windows (which is to say, not at all). So that fact that Apple looks to be doing a new FS does not impact interoperability in any real sense.

The other feature you really want for an interchange FS is simplicity. There are a lot of devices out there that use an FS to communicate with a computer. The simplest example is a digital camera via its media cards, but there are many others. Something like ZFS is way too complex for those devices, and honestly most of the features of ZFS like multiple drive support and snapshots are useless since the devices don't have the physical interconnects or user interfaces to expose those features. There is certainly an argument to be made that we could use something a bit better than FAT32 or exFAT as that format, but ZFS was not the right solution for that.

In other words, for that disk you want to use as an external drive to drag between computers you don't want something like ZFS, you want something that is simple enough that a firmware engineer can write a read-only implementation from the specs in less than a week. For the disk embedded in your computer (operationally or literally) you want something like ZFS, but it doesn't matter if it is interoperable with anything else because you won't be moving it between systems.

This is basically how Windows works. Microsoft generally uses NTFS for internal drives, but FAT for external drives. Ultimately somebody should design a filesystem explicitly for use as an interchange format and license it for free, then everyone can deal with their internal FSes and do what makes the most sense for their OSes and markets.

]]>Flash on the iPhonehttp://www.devwhy.com/blog/2009/10/8/flash-on-the-iphone.htmlLouis Gerbarg2009-10-08T06:49:00Z2009-10-08T06:49:00ZUpdate: One of the developers of Trading Stuff posted a comment below, and has a great blog post about his experience getting it running on the iPhone.

There has been a lot of discussion about running Flash apps on the iPhone over
the last few days. It was precipitated by Adobe's announcement that Flash
Professional CS5 would have support for publishing apps as iPhone native
executables. They went into a little more detail, saying that they were going to
use an Ahead of Time (AOT) compiler backend based on LLVM, and that
there are already several apps on the store using it. This generated a large
number of responses from various people, some knee-jerk, some well
reasoned out. Of course, the fact that there are samples we can dissect means
that it is possible to make some informed analysis about them.

 

Personal views

 

Before we get into the technical details of this, let me go into my background a
bit, lest I be accused of being biased or having an agenda. I have around 10
years of Objective C development experience, and almost no experience writing
anything substantial with Flash or ActionScript. I am also primarily a Macintosh
user, where the Flash experience (even in the browser) is often less than ideal.
I am told it is a better experience on Windows. I do use the Hulu Desktop app, which is written in Flash, and think it is pretty nice (though
they should make cut and paste work in their text fields, grrr). Of course,
something like Hulu is an immersive app that has no need to integrate with the
native OS experience, but neither do most games.

There are a lot of neat little web games and what not that are written in Flash,
that I would like to run. If that was the tool the author felt it best to
express their ideas and it worked for them then great. In particular, for
software that I don't feel needs interface with OS and which can use a
completely custom UI (in other words, games) I think there is no difference to
the user. So long as the environment generates good code that can run at full
frame rate without killing the battery I am in favor of getting Flash apps to
run on the iPhone.

 

Warm up

 

Okay, so first off lets look at what we know. Adobe is using the LLVM arm
backend to generate code. Right off the bat that gets me bit worried. Don't get
me wrong, I love LLVM. Hell, I was one of the people who wrote
the LLVM ppc backend. Having said that, I wouldn't use the LLVM arm backend at
this time. The reason I wouldn't is because every time I have asked the
people who are actively working on it they tell me it is not ready for prime
time. That is the reason why LLVM-gcc and clang are not supported compiler
targets for iPhone, despite them being supported (and encouraged) for development
on Snow Leopard. Apple has a lot of compiler engineers and has basically stated
that LLVM is their future compiler direction, so if those guys are telling us to
hold back, then how is it good enough for AOT Flash?

Now, Adobe could potentially have another arm backend they developed, or maybe
they branched off a particular build and have fixed whatever bugs would impact
them while ignoring stuff they didn't need. It is entirely possible that they
could have reasonable code coming out of this thing, and I don't have access to
the toolchain itself to inspect it, but it definitely gets me nervous. This may
also be one of the reasons why they are not ready to widely release the tools
yet.

 

Lets get to it

 

Okay, so I downloaded one of the games that was available, Trading
Stuff, decompressed its IPA and had a look inside. At first
glance it looked like a pretty normal iPhone app. Then I noticed there were no
resources besides a basic MainWindow.nib. No images, no sounds, no
localizations. The next thing I noticed was that the binary was ~13 megabytes,
or approximately ~95% the size of the entire app. That is enormous for a binary.
For reference, compare that to a normal iPhone game, like The Oregon
Trail, which is ~106 megabyte game has ~1 megabyte executable, or
about 1% the size of the app.

What is going on is that the Flash build environment is not using any of the
standard Mac OS X/iPhone OS bundling or localization mechanisms. Instead they
are transforming all their assets into embeddable objects and shoving them
directly into their application's TEXT section. At first glance that might not
seem so bad, but it has a bunch of consequences. It defeats almost any sort of
caching or prefetch logic the OS has for specific data types (like images), and
instead places all of the pressure directly on the VM and paging subsystems.

To be clear this is no way violation of the SDK agreement, and embedding objects
into an app in this way is occasionally appropriate, but the degree to which it
is happening with these cross compiled apps is different, and likely will have a
number of significant (negative) performance implications.

Now, moving on from the obvious, its time to actually start poking at the
generated code. If we just take a cursory look at the linkage, we can see some
bad stuff going on here. Why are they calling dlopen, dlclose, and dlsym? The
only reason to use those is load in frameworks and resolve symbols after launch,
something that is strictly verboten. In the best case that might be some dead
code they use from debugging that should have been stripped that should have
out. In the worst case, they depend on them to get access to symbols they are
not supposed to use. I want to be clear about this: There is no legitimate
reason why any app that follows the terms of the SDK agreement should use these
functions, and I find it shocking that Apple lets apps that link against them
on the store at all. I should also note this is not exhaustive, those are just the most obvious things, but in my cursory inspection I saw a dozen or so objective C selectors that I believe are private.

Actually that brings up another point. Despite the app developer doing nothing
wrong, one of their toolchain or middleware vendors is doing something that could
be an issue. When I write apps for the store I might choose to play fast and
loose with something if there is a compelling reason, but if I am providing a
library for someone else I never do. Using private APIs is putting your
customer's apps at risk. Not only do I find that unacceptable,
but I think any vendor who does that is generally irresponsible and makes it me
hesitate to use any of their other products because I feel it shows a certain
casualness about how you treat their customers. If there is a legitimate reason
you need to do something that risks your customer's products, then as a company
you need to disclose it so your customers can make an informed decision.

I should note this is not an intrinsic issue with Flash, I know for a fact
certain major vendors ship iPhone libraries that call APIs that can get your app
rejected from the store without informing developers. For instance, various analytics companies
really shouldn't be poking at private APIs to try to find cached location
framework data. It isn't just a privacy breach, it places your clients apps at risk.

 

So what. How does it run?

 

On my iPhone 3G it runs really choppy, on my 3GS it runs acceptably, but it
still isn't smooth. Given the OpenGL performance people have seen on the 3GS
that is still pretty bad. I have not done any invasive tests by instrumenting
the binary, that is just what I can get via basic usage. The sad thing is that
there is no reason it has to have performance like this. This is not an inherent
issue with the ActionScript used in this app (though that may have issues), it
is that what is coming out of the toolchain is a huge, monstrous binary that stresses
the runtime and has performance characteristics completely different than
anything the iPhone is currently setup for.

Also, remember, the slower the frame rate the more work the phone is doing per frame, and the
more battery the app is using. When you see an app that can do 120 FPS in its
demo loop, that means that when it is running at 30 FPS it is using ~25% of the
CPU/GPU assets. When you see one that can only get 20 FPS that means it cannot
hit 30 FPS to clamp at despite maxing some or the costly (in terms of battery)
system assets.

 

Punchline

 

Technically speaking, these do appear to basically be within letter of the SDK
agreement, modulo the fact that Adobe appears to making private API calls. They
should be able to do what they need to without making those calls, so ultimately
that should be a non-issue.

Now, the notion that what this thing emits is indistinguishable from
something Xcode emits is laughable. They are very different, and not in a good
way. While the apps may get acceptable frame rates on an iPhone 3GS, they don't
on earlier hardware, and they almost certainly use substantially more
battery power than native games.

I want to be excited about this thing, both because it is a seriously cool
piece of tech, and because there are Flash games I would like to run on my
phone, but looking at what this thing is spitting out I think the apps it will
generate will perpetuate the stereotypes about Flash (especially on cell
phones), and give Objective C programmers a (somewhat misplaced) sense of
vindication about their views on Flash.

This is all still in beta, it could end up a lot better than it currently is. It
could be something that can make some great games available on the iPhone.
Unfortunately looking it right now I am very skeptical, and I think that is the
right position to have given Flash's performance elsewhere. Yes, this is
entirely new technology, but it comes from the same company with the same
priorities. Given the product they have delivered to me on my desktop for the
last 5 years they don't get benefit the doubt, they have to pull themselves out
of the doghouse as far as I am concerned. Come on Adobe, prove me wrong!

]]>C4[3]http://www.devwhy.com/blog/2009/9/27/c43.htmlLouis Gerbarg2009-09-27T22:11:00Z2009-09-27T22:11:00ZC4[3] has just ended, and I am sitting in the hotel lobby right now. It was a great show this year, a lot of interesting talks, I hope everyone had as much fun as I did. I am posting the slides from my Blitz Talk (How to become a compiler engineer in 5 minutes) here (PDF).

]]>Apple has opensourced libdispatchhttp://www.devwhy.com/blog/2009/9/11/apple-has-opensourced-libdispatch.htmlLouis Gerbarg2009-09-11T03:39:00Z2009-09-11T03:39:00ZApple has opensourced the libdispatch Mac OS X implementation. This is excellent news, and hopefully we will quickly see ports to other platforms. This is a the last core piece of GCD that was proprietary, so it is a very exciting piece of news.

]]>Grand Central Dispatchhttp://www.devwhy.com/blog/2009/8/28/grand-central-dispatch.htmlLouis Gerbarg2009-08-28T11:48:00Z2009-08-28T11:48:00ZOne of the really cool features of Mac OS X Snow Leopard is a new set of technologies to make developing for multicore systems easier, named Grand Central Dispatch. There has been a lot of hype about what they are, and until recently you needed an NDA to discuss them. With the release of Snow Leopard it is now possible to discuss those technologies publicly.

Not so new...

The first thing I need to say is that the assorted technologies involved with GCD are not new. It is a number of existing technologies that have been combined in a fairly innovative way and with a killer implementation.

I think the best way to explain this is to look at Apple's approach to devices like the iPod and iPhone. Apple has a reputation for innovative devices, but usually they don't innovate by inventing a category, they reinvent it. In other words they find some market that exists but is poorly served, and they throw their resources at it, blowing away the existing competition. Sometimes they own the category, sometimes new competitors come in to try to compete on the raised playing field.

The simplistic explanation is that GCD is a combination of thread pooling and closures. The honest truth is that if thread pooling is a Motorola ROKR then GCD is an iPhone 3GS... while they are both phones and nominally do the same thing, no one would ever claim they are equal, or even in the same league. The guys at Apple who came up with it deserve a ton of credit.

First off clos^H^H^H^H^H Blocks

The first piece of GCD is Apple's new C extension, Blocks. In short, blocks are closures. For those of you are into the all the hot new scripting languages, closures should not be anything new. For all the old LISP heads reading this, closures are in fact a very old thing. For everyone who spends most of their time writing C and C++ code, the basic idea is that a closure is a bundle of a function pointer and a context pointer. So, everywhere you setup a callback function and pass in a context pointer that gets passed into that function you are manually forming a closure. The big difference with language level support is the syntax:

//Without blocks

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

void myCallback(void **context) {
  uintptr_t number = (uintptr_t)(*context);
  printf("Out: %" PRIuPTR "\n", number);
  *context = (void *)(number + 1);
}

void call_100_times(void (*callback)(void **context)) {
  void *context = NULL;
  uint32_t i;

  for (i = 0; i < 100; i++) {
    callback(&context);
  }
}

int main(void) {
  call_100_times(myCallback);

  return 0;
}

vs

//With blocks

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

void call_100_times(void (^callback)()) {
  uint32_t i;

  for (i = 0; i < 100; i++) {
    callback();
  }
}

int main(void) {
  __block uint32_t context = 0;

  call_100_times(^{
    printf("Out: %" PRIu32 "\n", context);
    i++;
  });

  return 0;
}

So, lets do a quick analysis of the changes. First, rather than writing a function and passing a pointer to it into call_100_times() I was able to write the block right at the call site of the function I am passing it into, which makes things easier to read.

Also, the function takes an explicit context pointer which I need to cast around into what I know it is. In more complex case you may need to build structs to pass into function. Our block doesn't take any parameters (they can, but often they do not need to). Instead it captures the context variable from the scope it is declared in. The reason we declare context as a "__block uint32_t" is to tell the compiler that when blocks read and write to it they should share the one from that scope, instead of getting their own copies. The result is a very logical construction where I declare a variable with in an interior scope that I pass into another function.

At the end of the day it is basically syntactic sugar with a small amount of runtime code to deal with copying blocks to and from the heap, etc. But it makes a huge difference when you are trying to write code.

Apple actually publicly disclosed Blocks a long time ago, and several good blog posts about them exist. They have been proposed to WG14 for inclusion in C1X.

libdispatch

The other part of GCD is libdispatch. As I said earlier, GCD is basically a combination of closures and thread pooling. Since Blocks are Apple's closure implementation, it is reasonable to assume libdispatch is their thread pooling implementation, and that is exactly what it is.

For those unfamiliar, the basic concept of a thread pool is that rather than having specific threads for specific tasks, you instead have a pool of generic worker threads. The program issues chunks of work (traditionally as a function pointer and a context pointer, but in this case generally a Block) to a queue, the worker threads pull the work units off of the queue and runs them.

This approach has a number of advantages over fixed partitioning. First, it is really hard to estimate how much work each thread should do. With a thread pool the system handles that dynamically, it can spawn as many threads as it wants and pull the work units off the queue, which tends to result in much better CPU utilization. It can also shutdown threads if the queue is drained, which lets the system reclaim dormant resources. All the dispatch logic runs very quickly with no contention, since wait-free queues are well understood.

libdispatch is a new system library provided with Snow Leopard. It provides a system wide set of thread pool APIs. The default use for most users will be to create sequential queues, which issue blocks in order and wait until one block has completed before the next one begins. That means that you can create a queue and issue your critical sections to it, guaranteeing mutual exclusion without taking a lock (though the code now runs asynchronously). Lets revisit our example above, but with 2 additional constraints. First, lets run our block on a queue. Second, lets assume that printf is only safe to run from the main thread (printf's thread safety is actually unspecified in the C standard since C does not actually specify anything about threading or memory models, but as a practical matter most implementations are thread safe).

//With blocks and libdispatch

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>

#include 

//We add a completion handler that gets called when all the work is done,
//it is just another block

void call_100_times(void (^callback)(void), void (^completion)(void)) {
  uint32_t i;

  //Create a queue to issue blocks against
  dispatch_queue_t queue = dispatch_queue_create("com.blogspot.devwhy", NULL);

  for (i = 0; i < 100; i++) {
    dispatch_async(queue, callback);
  }

  dispatch_async(queue, completion);
  dispatch_release(queue);
}

int main(void) {
  __block uint32_t i = 0;
  dispatch_queue_t main_queue = dispatch_get_main_queue();

  call_100_times(^{
    //Issue an asynch printf from whatever queue we are on to the main queue

    dispatch_async(main_queue, ^{
      printf("Out: %" PRIu32 "\n", i);
      i++;
    });
  },
  ^{
    //Need to explicitly call exit now that the end of main is never reached
    //We do it here in the completion block

    dispatch_async(main_queue, ^{
      exit(0);
    });
  });

  //Start the dispatcher
  dispatch_main();

  //NOT REACHED
}

Okay, so that is a lot more code than before, but it has the benefit of allowing some of the code run other CPUs, while still keeping everything in order. I also never created a thread or a lock! In short, we made the whole thing run asynchronously, sort of how jQuery works. First we call call_100_times(), which creates a dispatch queue and adds the 100 blocks to it. Those blocks will be handled in a completely serial manner (when one is finished the next is started) by libdispatch, so they will only use one CPU at a time, though the queue may migrate between threads and CPUs as appropriate. Obviously this is a toy example that might not generate enough work for GCD to bother spinning up a second thread, but it can if it deems that to be advantageous, and it requires no programmer intervention.

We then call dispatch_main(), which starts the queues. As the blocks are dequeued and run they start queuing the printf()'s onto the main queue (which is a special queue that runs exclusively on the main thread), followed by the exit() from the completion block. As those blocks are running the main queue starts dequeuing its blocks and printing stuff out, so now our program is doing the adding on one thread and the writing to the screen on another.

Once the completion block is dequeued it sends a block containing exit() to the main queue. Once the main queue finishes all the proceeding printf blocks it calls the exit() block and the app terminates. So, what we have done here shows how we can implement critical sections without using locks, and queue things to run on the main thread in an appropriate order. Another big benefit of doing everything asynchronously is that it greatly cuts down on spinning beachballs, since those are generally caused by something synchronously waiting on the main thread.

Besides this, there are several other features of libdispatch, such as concurrent queues (which do not guarantee blocks they issue complete before the next one is run), semaphores, event sources, finalizers, and all of the other frills necessary to push everything through GCD. The manpages for GCD are very good, I recommend reading them: man 3 dispatch

Now, looking at the above, you might be thinking that it is very cool, and while thinking up all of the bits must have been difficult, it seems fairly simple to implement. That where Apple's integration expertise comes in. Not only have they tuned the hell out of the library and made tons of optimizations, but they also have implemented kernel hooks, and made their dispatcher system aware so it can manage threads based on the overall system state. That means instead of every program checking how many CPUs the system has and trying to consume them all (causing contention between programs and wasting time in the scheduler) the system selects how many threads should be running based on the global system state and divys them up between all the programs on the system.

Apple has released a PDF that provides a high level overview of GCD, including a number of nice pictures.

Downsides

Any major shift has some downsides, though in GCDs case they seem pretty small. The first downside is that makes programmers change some of their fundamental assumptions. The most obvious is that when a function returns that no longer means that the code you declared inside it has necessarily run. Moving to this sort of asynchronous model takes some getting used to, but honestly it is far simpler than understanding threads and locks. Of course if you are already familiar with traditional threading it is something new to learn.

Another issue is that the interactions with traditional threaded code can be complicated. The unfortunate truth is that a lot of code that would have been better implemented using GCD already exists and is using threads, and converting it might not be worth the effort. That means GCD code may need to interact with traditional threaded code. In general that should work fine with some minor effort, especially if they existing code uses a single threaded facade. If you need to actually directly manipulate threads from inside GCD queues there are a lot of constraints, but they are well documented in the manpages.

Finally, the biggest issue for me is that GCD is not cross platform. Apple has released the Blocks patches for GCC, include Blocks in CLANG, and implemented a C to C++ source level transformer ("clang-cc -rewrite-blocks") that rewrites blocks code into traditional C++ code, as well as an open sourced Blocks runtime. Unfortunately they have not (yet) been so forth coming with libdispatch implementation. While it might a competitive advantage, I suspect that getting it freely available so that the various open source packages Apple uses can consider moving to GCD would be a significant benefit. Ultimately I think this is a temporary issue, because the actual blocks API is not that complex to implement if one only cares about compatibility. Extracting all of the performance Apple has gotten through their system wide implementation and optimization would probably require quite a bit of work, which would also work in Apple's favor (GCD is good everywhere, but best on OS X!).

Conclusion

GCD will improve the utilization of multiple processors, and reduce the number of spinning beachballs (even in what are nominally single threaded programs). It is not a panacea, and how effective is depends on how pervasively it used. I suspect it will end up being quite pervasive, because the paradigm it is trying to replace have proved difficult to use.

]]>From write() down to the flash chipshttp://www.devwhy.com/blog/2009/8/4/from-write-down-to-the-flash-chips.htmlLouis Gerbarg2009-08-04T19:46:00Z2009-08-04T19:46:00ZLike a lot of people, I have made the move to an SSD, and I love it. While there is quite a bit of variability between the different vendors of high end drives, all of them far exceed the performance of any conventional HDs. Moving to an SSD has easily been the best improvement in terms of performance and experience of any HW upgrade I have purchased this decade.

Anyway, the catch with these new SSDs is that they are really new. They all have had some bumpy firmware issues, so unless you are an enthusiast who pays attention to those sorts of things and keeps your firmware up to date I can't quite recommend without reservations. While discussing an upcoming firmware upgrade for my drive (OCZ Technology Vertex 250GB) it became clear that a number of people did not understand how the entire storage stack above the SSD worked, and that was causing some serious misunderstandings about what a firmware up date could and could not do.

Because of that, I decided it might be worthwhile to write up an explanation of how a modern storage stack (FS through flash chips) worked. For the sake of this discussion we will assume an overwrite filesystem (such as NTFS, HFS+, or ext4), an ATA bus, and what is generally referred to as a 2nd Generation FTL (Flash Translation Layer). Obviously the exact details may change quite a bit if any of these parameters are changed. But this is by far the most common setup people use today.

The filesystem's view of the world

The filesystem is responsible for a number of things, like permissions and name lookup, but none of those has an impact on where it puts blocks on a drive. Once we remove all of that, we can consider the file system to be an "object to block" mapping layer. In general a storage object just means a separate distinct entity, so each file is an object.

It is the file systems job to take these various object requests (create, delete, read write) and service them using the chunk of block storage it is provided by some underlying device.

ATA's view of the world

ATA is a command based transport that allows a lot of things, but for example we don't care about ATAPI and all that stuff, we just care about the block storage services it provides. ATA doesn't have any object commands, it just has block commands. Basically your entire drive divided into a series of LBAs (logical block addresses). The drive has commands to read and write data to a particular LBA. Note that it does not have a command to delete an LBA, that will become an enormous issue later.

Flash's view of the world

Flash is a relatively complicated storage medium, and has its own view of the world. It works in terms of pages and blocks. Usually a page is the smallest amount of space you can reasonably read or write to a a flash chip (for our discussion, 4K), and a block is the smallest chunk of space you can erase at a time (for our discussion 128 pages). With a fresh (unwritten block) all the bits are set to "1", and during a write they can only be transition to "0." That means in order to rewrite a page you must erase it first. This is a very important point, you can't just go and erase a page of the flash, you need to erase the 128 contiguous pages contained in a whole block at a the same time.

The SSD controller's view of the world

Okay, the SSD controller has to deal with ATAs view of the world on one side (LBA), but it also has to deal with flash chips view of the world on the other. This is a hugely complicated task, and it is the reason that the quality of drives varies widely. Because the SSD only deals with those points of view, and not the higher level parts of the OS view (objects) we can characterize its behaviors in those terms, though later we will look at how the stack operates as a whole.

Okay, so lets assume for a second we have a 1MB flash device with 2 512KB blocks. This would be sold to the consumer as a 512KB flash drive, because some amount of the internal storage needs to be used for bookkeeping as we shall see. When the controller starts up what the flash looks like (from the point of view of the controller) is this:

 

empty.png

 

In the above picture the blue page represents the internal tracking data the drive controller is using for remembering things like wear counts and page indirections. The OS cannot see that page, it is completely internal to the drive.

The controller can see all of that flash, but it tells the ATA chip on your motherboard there is a 1 512KB ATA device there. Now, lets imagine you go to write a page to the drive, what happens:

 

first-write.png

 

Okay, the SSD was handed a chunk of data from the ATA bus (the green page). It found somewhere to put it. It also needs to update its tables so it can find it in the future. But if you recall in order to erase the original table it would have to erase the whole block. That would be super wasteful, since most of the block is empty and flash has a limited number of erase cycles, so instead it just writes a new copy to a free spot in the block, and the old copy of the drives control data is marked as invalid. Lets imagine we write another page to the drive, we will see something similiar occur:

 

second-write.png

 

Now, lets write over the first page. This is where things get interesting. We do basically the same thing is as before, except that when the write occurs the SSD looks in its tables and sees that the address we are writing to is in use, so it goes and marks the page as invalid in its tables.

 

overwrite.png

 

Going on in this manner eventually a flash block will have more invalid pages than valid. At that time the drive will sweep through and gather all the valid data into a new page:

 

gc1.png

 

Then erase the old page:

 

gc2.png

 

At the moment the only way a user generated piece of data can be marked as invalid is if it is overwritten (though that is changing). This has some serious repercussions for the drive GC, as we will see.

Throwing in the filesystem

Okay, so we have a basic understanding of how a modern SSD works. Now lets throw a file system into the mix. Lets imagine we have a filesystem with a single file in it:

 

fs1.png

 

In the above picture the blue page is the SSDs internal tables (which the OS cannot see), the orange is the FSes internal tables (which the SSD can see, but cannot understand), and the green is the actual file data. Since the FS cannot see the SSDs tables and the SSD cannot understand the FSes tables we are now in a situation where no part of the stack has a complete understanding of what is going on. The repercussions of this are most apparent when you delete a file.

 

fs2.png

 

So in the above case the filesystem updated its internal tables and wrote it out to the SSD, the SSD then found somewhere to put the new page and modified its tables. But notice how nothing happened to the actual file data (now colored dark green), since a deletion is just a matter of marking a few bits in the FSes tables. The SSD does not know those pages no longer needed by the FS since it doesn't understand the FSes internal structures, so when the SSD runs its GC algorithms it must preserve them:

 

fs2-gc.png

 

Note that drive preserved all those pages that will never be read again, since the OS considers them free and will use them to write out new files. This is where the new ATA TRIM command makes a difference. What TRIM does is let the OS tell the drive "I have not yet overwritten this data, but I never need it again, so you can throw it out." Lets redo the last scenario with a TRIM aware drive:

 

fs1.png

 

Now we delete the file and the OS sends TRIMs for the file pages to the drive:

 

fs2-trim.png

 

Notice how the file pages are not marked invalid. At this point when GC runs it can throw them out:

 

fs2-trim-gc.png

 

Which results in the drive needing to preserve fewer pages during its GC process. That has several impacts, including:

 


  1. Reducing the time GC takes

  2. Increasing the amount of freespace available after a GC (which increases the time it takes for performance to degrade after a GC)

  3. It lets the FTL have a wider selection of pages to choose from when it when it need a new page to write to, which means it has a better chance of finding low write count pages, increasing the lifespan of the drive

 

Now, I want to be clear, a sufficiently clever GC on a drive that has enough reserved space might be able to do very well on its own, but ultimately what TRIM does is give a drive GC algorithm better information to work with, which of course makes the GC more effective. What I showed above was a super simple GC, real drive GCes take a lot more information into account. First off they have to deal with more than two blocks, and their data takes up more than a single page. They track data locality, they only run against blocks have hit certain threshold of invalid pages or have really bad data locality. There are a ton of research papers and patents on the various techniques they use. But they all have to follow certain rules based on on the environment they work in, hopefully this post makes some of those clear.

]]>