nemo
/
hn-classics
1
0
Fork 0
Code Issues Pull Requests Releases Wiki Activity
hn-classics/_stories/2007/13805096.md

30 KiB
Raw Permalink Blame History

created_at title url author points story_text comment_text num_comments story_id story_title story_url parent_id created_at_i _tags objectID year
2017-03-06T19:02:11.000Z Newton Storage History (2007) http://www.dadhacker.com/blog/?p=948 jsnell 78 10 1488826931
story
author_jsnell
story_13805096
13805096 2007

Source

Newton Storage History | Dadhacker

Dadhacker

Instant Wisdom Worth What You Paid

Skip to content

← I knew FORTH was evil

Warnock on continuations and my favorite beverage →

Newton Storage History

Posted on October 23, 2007 by landon

I joined the Newton group in early June of 1992. I’d been at Apple since 1987 working on tools and then a database engine in the development tools group, but after a bunch of bad politics that I won’t dwell upon I wound up needing a new position pretty quickly. I managed to land a gig working on a device driver framework for the Newton.

I arrived in Newton just as the group had decided to do “Junior,” the product that was to become the first Newton MessagePad. Up to that point there were a bunch of people happily noodling away in Ralph (the object-oriented dialect of Scheme that the Newton tablet product was going to be based on), but the decision was made (over CES, I gather) to do Junior in C++ and what later would become NewtonScript. When I arrived there were a bunch of ex-LISP hackers wandering the hallways clutching C++ reference books and looking unhappy. Really unhappy. The expensive tablet product (“Senior”) wasn’t entirely shelved — they kept doing revs of its plastic — but it was soft-pedalled and eventually died.

I did a simple driver model for devices (in retrospect, probably way too simple), and inherited a heap manager that I eventually made work pretty well. I worked with some early storage stuff with Tim Harrington, another engineer in the kernel group.

At first the store inside the Newton itself just kept objects in a heap in the Newton’s battery backed RAM. We also worked out a scheme for keeping heaps on removable PCMCIA RAM cards, but the problem was that the heaps had to be located at particular virtual address to work, and the virtual address of the card could vary depending on the slot you plugged the card into. We could have simply relocated the heap structures, but the problem remained that the power could fail (or the user could remove the card) in the middle of store update, whereupon you’d lose all the data (or worse, it would become flakily corrupt). We needed a storage system that was address-independent and that would also survive restarts.

The group was starting to realize that the Newton platform was way over budget on RAM. There was some neat work done by the kernel team to reduce the stack and other memory needed for threads, and I did some work in the heap managers to minimize virtual memory usage and fragmentation, but it was clear that we wouldn’t have enough RAM to store as much user data as we would need to; even reducing the application heap, we’d need another 128K or more to make people (ahem: Marketing) happy.

So the hardware team added a single byte lane of RAM. Basically this was a region of memory where every fourth byte was valid (and the agreement between the hardware folks and the OS team was that they could populate more lanes of bytes, until they filled all four lanes and it became just like the rest of RAM). This was easy for the hardware folks to do (just solder another chip on the board), but the heap-based store couldn’t deal with byte lanes.

We also had to support Flash devices. The type of flash we planned to support could be read directly like RAM, but not written to without going through funny little state-machine gyrations. Given the wacky byte-lanes of RAM and the non-RAM-nature of Flash, it was clear we had to do a bunch of work on the storage layer. So I did that; the object store talked to the actual backing store through an abstraction and the callers had no idea what kind of wacky stuff the store was going through in order to make things persistent. In fact, for the internal store of the OMP we used 128K of byte-lane memory plus another 64K of ordinary memory “stolen” from the rest of the system.  The abstraction glued all this wacky memory together and the NewtonScript world never knew the difference.

But there were still windows where resets or power failures would cause the store to become corrupt; it wasn’t crash-proof or reset-proof. We all knew this, and I’d done some thinking about putting a transaction system in, but none of us thought we had time to fix things before ship.

One afternoon Michael Culbert, the Newton Technologist, came into my office to discuss battery contact bounce. I’d been nervous about the robustness of the storage system and had talked with him about it before, and now he confirmed my worst fears. Battery contact bounce is the jiggling of the power connectors when you toss a device onto a hard surface; the device can easily momentarily lose power and reset, and if the Newton was in the middle of a storage update all the data would be lost. As I said, we’d been talking about doing transactions in the stores for a while, and Michael finally had a good argument for why they were going to be critical.

“We have to do this,” I said, “Or we’re fucked.”

“We have to do this or we’re fucked,” he echoed. “I’ll go tell Fi [the software manager of Newton] and Gaston [the head of the division].”

“Okay. It’ll take a few weeks.”

“I know.”

This was maybe four months before the product was scheduled to ship. The first thing I did was to leave work for a couple of hours to visit some bookstores I liked, buy a couple of CDs I’d been thinking of getting, and take a long walk. Then I came back that evening, closed the door to my office and worked 18-20 hour days for the next five or six weeks.

A couple of evenings into this effort Gaston came into my office and tried some small talk. He wasn’t very good at it. I was concentrating on the design of the transaction log at that point, and really didn’t want to be disturbed.

Gaston said, “Fi tells me you’re the guy who’s going to save the product.”

“I guess so.”

“All by yourself? You don’t need any help?”

“Not right now.” Some things aren’t partitionable.  I knew what I had to do, practically down to each subroutine to write.

After Gaston left, I tracked down Fi and told her, “No offense, but please tell Gaston not to come around my office anymore. He makes me nervous.” She did get some other folks on the team to help out on some pieces that I was able to partition and farm out, but for the most part the things that had to be done simply couldn’t be parceled out to other people, there just wasn’t time to get them up to speed.  “Adding people to a late project makes it later.”

The only thing I remember clearly about the next couple of weeks was that I dreamed a whole lot about transaction systems. I stuck the changes into the system (we had mandatory code reviews; I spent the two days prior to checking-in talking myself hoarse, walking through the code with Greg Seitz, another kernel guy). I did my only all-nighter at Apple getting that build out, and I recall only a couple of bug fixes to it.

The upshot of the transaction system was that you could do a bunch of updates to the objects on a store, crash in the middle, and recover everything prior to the update that crashed. It was pretty cool.

Here’s roughly how it worked:

Imagine that you have a notepad entry, with a bunch of text. The NewtonScript storage layer breaks up the notes into a bunch of small objects, including the text itself, plus some extra objects for searching. There are objects containing structures that allow the text to be quickly searched, and so on.

Now say your original note was, “Buy milk,” and that you add “Bread, too!” to it. What the Newton does is create a whole set of shadow objects, just like the old ones but with your changes applied. Then, with a single write to a single byte somewhere in the store the storage system commits your changes, then goes back and deletes the outdated objects.

If the power fails before the commit point, the Newton just deletes the new objects and you haven’t lost much work (you just have to remember to buy bread). If the power fails after the commit point, the Newton just ensures that all of the old objects have been gotten rid of (so it can re-use the space they take up).

This sounds simple in principle, but in fact it’s quite difficult to get correct. Additionally, the flash storage we were using had the amusing characteristic that bits could go bad, which is a little like having to design a car with an engine that might lose a gear or two and still have to maintain freeway speeds without the driver even noticing.

Flash-based file systems in 1992 were kind of rocket science; the existing stuff from Microsoft had to be manually compacted, which as you can well imagine was a really awful pain the rear. The Newton’s flash store did all of this transparently and in real-time, too; during a technical presentation we got some questions about this (I always assumed they were from Microsofties):

“When do users have to compact the flash cards?”

“You don’t, it’s all done for you.”

There was some refusal to believe this, and we got the question several times. That was fun. Nowadays users just expect this stuff to work, but back then all the existing Flash file systems were pretty icky.  It felt great to have something cool out there.

After 1.0 shipped we added large binary support. The idea was to use the virtual memory system of the Newton OS to dynamically page in modifiable binary objects that could be significantly larger than the amount of RAM in the system (e.g., faxes). The first couple of cuts at this were pretty miserable until I had the idea of hooking the objects into the NewtonScript garbage collector.

The idea was that a large binary not associated with a persistent slot would live in a kind of limbo; if it was garbage-collected it would be deleted, and if the system crashed before it was deleted it would be cleaned-up as part of the normal transaction “undo” phase. But if a object was persisted and had a large binary as a slot, the large binary would be kept alive. It took a while to do, but the result was a system with only 512K of RAM that could receive a multi-megabyte FAX over a modem, or work with bitmap images larger than main memory, or play sounds that were likewise really large.

There was a lot of great technology hidden away in the guts of Newton.  I worked on some other pieces that were neat, but this is what I’m most happy about having shipped. It was a lot of fun to work on. Newton was one of those projects I always felt it was a privilege to be part of.

This entry was posted in Rantage. Bookmark the permalink.

← I knew FORTH was evil

Warnock on continuations and my favorite beverage →

8 Responses to Newton Storage History

  1. Brant Sears says:

December 3, 2007 at 4:59 pm

I was a Newton programmer for a few years writing medical records software. The persistent storage solution on the newton was really wonderful. I remember working with it very fondly. It was my first real job as a professional programmer. Our company made versions of our software for Newton and Windows CE. We only had one Newton engineer (me) and many Windows engineers. I was always able to keep the newton product ahead of CE despite working alone because of the tremendously powerful APIs of the the Newton. Even a year after cancelation our Newton software was far outselling the Windows version. I am a professional software developer today because I truly fell in love with the Newton and I like to think that a little bit of the design philosophy of the Newton rubbed off on me.

Reply

  1. desp says:

December 3, 2007 at 5:11 pm

Thanks for writing this. I remember being highly impressed with the way storage worked on my MP2100.

Please write more about your experiences at Apple.

Reply

  1. NAL says:

December 4, 2007 at 5:54 pm

You did an amazing job with the technology that you had. Only just a year ago, I wrote the majority of my PhD dissertation from an eMate 300 that I bought at a recycled computer store for $10 because I couldn’t afford a laptop and couldn’t take most of my research materials outside of the library. The formatting was done with MS Word after the fact, of course.

Obviously I wish I owned an MP2100 because the eMate’s processor is so slow, but still, the machine is remarkably resilient. I did have some flash memory corruption once that caused one of those crazy backlight-flashing errors, but a brain wipe did the trick.

Reply

  1. Matthias says:

March 11, 2008 at 4:03 pm

Thanks for this great article. You probably know about the Newton emulator “Einstein”. The emulator works quite wel (great work by Paul Guyot!)l, but is too slow to run on most PDAs. Which is why I started to rewrite parts of Newton OS, using the known Netwon API’s. I know, this is probably an endless project, but it’s fun nevertheless.

Feel free to peek into the source code at code.google.com or download the disk image. Comments and suggestions are very welcome.

Matthias

Reply

  1. Pingback: DadHacker: working on Newton storage « Newton Poetry

  2. Morgan Aldridge says:

March 24, 2008 at 12:17 pm

This is such a great story! Please contact Paul Potts and get this, and any others you may have, added to the new Newton project on Folklore.org:

http://folklore.org/ProjectView.py?name=Newton

See Paul’s recent announcement to the NewtonTalk mailing list:

http://marc.info/?l=newtontalk&m=120633234403859&w=2

Reply

  1. Thomas says:

April 19, 2008 at 12:47 am

This is a cool story – I remember that I read a feature story about the Newton storage system in a Byte magazine around that time…

I had already been programming for about a decade at that point, but the complexity of the Newton OS and the number of brand-new concepts in the code was staggering to me. You are my hero! 🙂

Reply

  1. Jeff Sheldon says:

August 5, 2014 at 12:10 pm

This is a tremendous memoir which provides wonderful insight into problem solving, product design, and concern for user data integrity. I recall moments where the transaction system really saved my butt. Special thanks to myapplenewton.blogspot.com for reviving attention to Landon’s post.

Reply

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Comment

Name *

Email *

Website

Dadhacker

Proudly powered by WordPress.

[*RSS]: Really Simple Syndication