Brrian to go.

Some related work for Timelapse. Sadly, I can’t seem to find many details about ToonTalk, except that it’s some kind of robot-controlling kids programming game. However, their VCR metaphor is pretty close to Timelapse’s.

It also appears that ToonTalk was open sourced (er, dumped) on Google Code. Not that I have much use for gnarly Windows source.

How WebKit’s event model works

First, here are some definitions of major parts of WebKit:

  • JavaScriptCore: the JavaScript execution engine. It has no dependencies on other components.

  • WebCore: the page rendering/layout/event dispatching component. This is the vast majority of the codebase in size and complexity. It depends on JavaScriptCore (JSC). Several portions have different implementations for each platform, such as graphics, sound, network, user input handling, and run loop integration.

  • WebKit: a fairly small layer that makes WebCore easier to embed by exposing a higher-level interface. It depends on all of the above.

  • WebKit2: a more complicated split-process layer for embedding WebKit. It depends on all of the above.

What controls the course of computation?

WebKit2 uses a split process model, where the Web process runs WebCore to handle parsing, layout, rendering, and script running for one web view. The browser/chrome process handles non-rendering tasks such as network communications and niceties for the user, like bookmarks and printing. The browser process communicates with all of its Web processes via inter-process communication (IPC). Essentially, one can view these messages as a queue of events to be handled. I’ll refer to these events as IPC messages.

Occasionally during the course of rendering a page or running a script, WebKit needs to perform (possibly a lot of) computation some time in the future, using timer callbacks. Common uses are implementing JavaScript timers or animations, which must run frequently to fill in many animation frames. I’ll refer to these callbacks as timers.

Timers allow asynchronous computation, and fire in a FIFO fashion: several callbacks with the same timer interval (say, 100ms) will fire in the order that they were registered. But, if an interval for 1s is set immediately after an interval for 10s, the 1s timer should fire first. This is accomplished by using a priority queue to keep track of which timers to fire next. Intervals with less time remaining to completion have greater priority than longer intervals. Among intervals with the same time remaining, those registered earlier have greater priority.

Thus, computation in WebKit is initiated by processing messages on one of two queues:

  • Callbacks from the timer priority queue.
  • Messages from the Browser process across IPC..

How internal timers are implemented

Periodically, all timers that are due for firing are fired synchronously and evicted from the queue (or re-inserted, for reoccuring timers). This periodic action is performed by a platform-level timer, whose base class is WebCore::SharedTimer. Each platform has its own event loop implementation, so each platform defines its own SharedTimer subclass that hooks into native event loops. The OSX subclass of SharedTimer (SharedTimerMac), for example, registers a Cocoa CFRunLoopTimer. This is later called periodically by the native event loop, which is invoked inside the WebKit2::RunLoop implementation (RunLoopMac), which is called in the main() method of the Web process.

The shared timer callback is registered via the following code path:

ThreadTimers::setSharedTimer(SharedTimer* timer)
-> MainThreadSharedTimer->setFiredFunction(ThreadTimers::sharedTimerFired)
-> SharedTimer->setFiredFunction(void*)
-> SharedTimerMac->setSharedTimerFiredFunction(void*)

The SharedTimer's interval is continously adjusted to the interval of the next due timer. This reduces the number of callbacks by SharedTimer to ThreadTimers::sharedTimerFired in cases where few timers are active (or a long ways into the future).

When it’s time for a timer to fire, the code path looks something like:

[NSApplication run] (native loop)
-> timerFired()
-> ThreadTimers::sharedTimerFired()
-> threadGlobalData().threadTimers().sharedTimerFiredInternal()  [1]
-> WebCore::Timer<WebCore::YourClass>->fired()

Inside of [1] is where eligible timers are looped over and fired, and the SharedTimer interval is possibly adjusted. The gist of routine is to fire events until none are ready to fire or we have exceeded a time limit.

The native run loop fires lots of other native timers and callbacks, as well. At every such point (notably in file IO, streams, networking, and graphics), WebKit includes an implementation for each port/platform, which may add or remove native events from the native RunLoop.

How IPC messages are handled

The Browser process sends messages to each Web process to communicate information such as resource data, user input, window resize, etc. These messages are piped to the Web process, which creates a WorkItem for each message. These work items are queued on the native event loop, and performed in course. In the OSX port, the RunLoop::performWork method is registered as a CFRunLoopSource—-in essence, it is registered as an additional source of events for the event loop. The body of performWork copies the list of WorkItems present upon method entry, works through the copied items, and then returns. Note that new work items may arrive when copied ones are being processed; these will be handled in the next call to performWork. Below is a typical sequence of calls leading from the native event loop through processing the IPC message to calling the respective WebCore handler.

[NSApplication run] (native event loop)
-> RunLoopMac::performWork(void*)
-> RunLoop::performWork()
-> CoreIPC::Connection::dispatchMessages()
-> CoreIPC::Connection::dispatchMessage()
-> WebKit::WebProcess::didReceiveMessage(connection, messageID, arguments)
-> WebKit::WebPage::didReceiveWebPageMessage(connection, messageId, arguments)
-> CoreIPC::handleMessage(arguments, WebPageMessageReceiver, targetFn)
-> targetFn(args...)

At the point of targetFn, the message can be handled in several ways. The important thing to note is that once these handlers reach WebCore, they are handled synchronously.

Where do DOM events fit into this picture?

DOM events are the abstraction for event-driven programming in web applications and JavaScript. (The Mugshot paper has a good overview of the DOM event model.) However, DOM events have not yet come into the picture—-where do they originate from?

Most user input DOM events, such as clicks, scroll wheel, and keyboard, are created in response to corresponding IPC messages. In that case, the targetFn above will mediate between the native or browser view of user input and the DOM event standards. This mediation also converts from raw screen coordinates to a DOM target, and excludes some events that should not be reflected into the DOM model as input (for example, clicking on a scrollbar). Here is a typical sequence of calls from IPC targetFn to DOM dispatch as described in the above link:

WebKit::WebPage::mouseEvent(WebMouseEvent)
-> WebKit::handleMouseEvent(WebMouseEvent, Page)
-> WebCore::EventHandler::dispatchMouseEvent(eventType, targetNode, clickCount, PlatformMouseEvent)
-> Node::dispatchMouseEvent(...)
-> EventDispatcher::dispatchEvent(Node, EventDispatchMediator)
-> MouseEventDispatchMediator::dispatchEvent(EventDispatcher)
-> EventDispatcher::dispatchEvent(Event)    // performs event dispatch according to DOM standard.

It is possible for some DOM events to immediately fire other DOM events synchronously. For example, the default event handler for the space or enter keyboard event on the <input type=”submit”> element will typically fire a second DOM “submit” event on the containing <form> element. This can be seen in the body and callers of HTMLFormElement::submitImplicitly.

What are the important points?

The top-level event loop is usually defined by the respective WebKit port, such as Cocoa, QT, GTK, etc. Timers internal to WebCore are manually tracked and dispatched by a single native timer that participates in the native run (event) loop. IPC messages are also handled according to the native run loop, and sometimes lead to dispatching DOM user input events. DOM events can potentially be triggered directly by timers internal to WebCore. An example is that animation-related DOM events are triggered by a timer in the AnimationController::animationTimerFired callback. In general though, user input is only triggered by IPC messages.

Timelapse progress, 11/16—11-23

In the past week, I have finished determinising Math.random and new Date()/Date.now(). Recording and replaying through the UI now determinises these features. I have created some manual test web pages for each kind of determinism (useful during development/debugging).

Today, I managed to create some _automated_ tests, as well. These hook into the test infrastructure that already exists for Web Inspector and the rest of WebKit. This means that relatively little scaffolding needs to be written for testing, aside from Timelapse-specific stuff. I might even try test-driven development in the next few weeks.

As for next week, I will be implementing event capture and re-dispatch. Previously, I thought that it would be easiest to capture user input events at a low level before they are turned into full-blown DOM events. My thinking was that since these are basically structs without any dispatch targets, it would be easier to record them.

That approach is probably unworkable in the long term. Instead, it is a lot more fool- and future-proof (and cross-browser) to record the DOM events as event data + target node. This way, there is a clean semantics to what exactly is being recorded, as opposed to raw click events, which may be swallowed by other non-webpage UI, like a context menu. Ostensibly there will be a lot less to record, since I only care about events that cause handlers (aka JavaScript) to fire.

The two main tricky implementation bits are to find a place in the event loop to capture/inject replayable events, and to uniquely identify event target nodes at the time of the event’s dispatch. The latter is most straightforward to do by numbering the path from root to node. In other words, a numbering [2,4,1,1,5] would mean the node is located by root.child(2).child(4).. and so on.

Timelapse, week of 10/31

This week, I have concentrated on re-integrating portions of Timelapse that live in WebCore, a.k.a. the non-JavaScript engine parts of WebKit. This has a few major parts: the integration with Web Inspector UI, Web Inspector backend, the protocol between UI and backend, as well as some instrumentation and glue code between the JSC and WebCore parts of Timelapse.

The first three tasks pertaining to Web Inspector have been somewhat laborious, because Web Inspector has changed a lot in the past year. In particular, the protocol between UI and backend has changed from a IDL to JSON format; the backend instrumentation enable/disable mechanisms have been unified; and there have been many changes to the actual UI.

The other tasks have mainly been “code cleanup” of bitrotted and changed classes. I have also started ripping out the old attempt at a determinism capture/replay mechanism in preparation for a new implementation next week.

Hopefully by the end of next week, I’ll have a (simple) demo of determinism in the Date constructor and Math.random.

Timelapse, week of 10/17 and 10/24

(I’m behind on my posts and work… mostly because I was at SPLASH 2011 last week!)

Over the two week period of 10/17—10/30, I worked quite a bit to integrate my instrumentation of JavaScriptCore (JSC) to the new upstream version. This was not too difficult on its own, as the parts of JSC that I care about (interpreter, mainly) do not change much. The actual merging was not hard, but testing the merge went horribly awry.

Most of my problems were configuration and changes in the build system. The default compiler on OSX Lion is llvm-clang, but this is apparently unable to build all of WebCore’s Objective C bindings. It took a while to figure out the correct compiler to use, since reaching the failing point of the build takes quite a long time.

Most of WebKit’s toggle-able features are controlled by build flags, as preprocessor “feature defines”. In the last year of changes, JSC stopped receiving the list of feature defines—-effectively making it impossible to toggle features like Timelapse on or off at the build system invocation. I think this was done because almost all of these feature defines are WebCore related (except Timelapse). Debugging this took two days. Once this was figured out, testing and fixing build breaks was straightforward.

In the next week, I’ll start re-integrating things in WebCore, starting with the Web Inspector’s Timelapse agent.

Timelapse, week of 10/10.

Last week, I created a new repository that contains full history ported over from Subversion. This was decided after two previous unsatisfying configurations: 1) periodically importing a tarball (losing any upstream history, and really hard to pull from upstream), and 2) maintaining a patch queue on top of a repository maintained via hgsubversion (too much work and complexity, and impossible to collaborate).

I created the “new” repository with hgsubversion, to convert the WebKit Subversion repository into a Mercurial one (the first time, this takes >30 hours, by the way). I then converted this repository so that everything lives below a top-level ./WebKit/ directory (this takes another >30 hours, by the way). I stripped documents and other non-WebKit things from my old repository and force pulled the changes into the new repository, preserving most history. Lastly, I “finished” my patches from 2), converting them to real changesets.

With all this done, I still have a lot of re-landing of old diffs from 1) before I can make progress on new features. Another reason for all this monkeying around is so that I can be much less behind WebKit trunk, and benefit from speed increases in the last year or two. Since I haven’t pulled in a while, I have to re-integrate 2.3MB worth of diffs from repository 1) with a recent WebKit version. That’s what is going on this week (10/17).

(By the way, the new repository lives on Bitbucket, at https://bitbucket.org/burg/timelapase/)

Timelapse website forthcoming.

For now, you can peek at the source on Bitbucket (burg/timelapse).