DOM Storage Implementation notes

This is a work in progress document at this stage helping review and land bug 600307.

Overview

Implementation has been completely overhauled and practically all in dom/src/storage has been thrown away.

The core implementation has been layered, from top to bottom, as:

• DOMStorageManager
  • class creating and managing DOMStorage and DOMStorageCache (bellow) instances for each origin
  • implements (updated) nsIDOMStorageManager
  • there are two derived classes, DOMLocalStorageManager and DOMSessionStorageManager
  • DOMLocalStorageManager is intended to be used as a service managing localStorage instances in scope of the whole application
  • each top-level doc shell keeps its own instance of DOMSessionStorageManager to manage per top-level browsing context sessionStorage instances
  • DOMLocalStorageManager object doesn't refer any objects in this hierarchy
  • DOMSessionStorageManager object hard-refers sessionStorage caches

• DOMStorage
  • class exposed to web content scripts as either localStorage or sessionStorage
  • implements nsIDOMStorage
  • can be obtained only through a DOMStorageManager
  • references a DOMStorageCache object for its origin (described bellow) and its DOMStorageManager
  • more then just a single instance of DOMStorage per origin may exist, while all of them reference the same DOMStorageCache object
  • this class is responsible for access security checks ; holds reference to a principal it has been created for
  • keeps track of whether is running in a private browsing window and whether should keep data only per-session
  • previously implemented by mishmash of nsDOMStorage2, nsDOMStorage, DOMStorageBase, DOMStorageImpl, DOMStorageChild and DOMStorageParent classes

• DOMStorageCache
  • class collecting and caching data per a single origin in a hash table, internally created by DOMStorageManager
  • exposes methods, similar to methods of nsIDOMStorage, to manipulate origin data ; DOMStorage forwards to them
  • there is always only a single instance per origin within a DOMStorageManager object
  • cache never overlives its manager
  • a cache holds 3 sets of data, a cache selects the proper data set by inspecting properties of DOMStorage demanding the manipulation:
    • default "normal browsing" data, whom changes are persisted for localStorage
    • private browsing data
    • session-only data
  • localStorage (persisting) cache specifics:
    • when data modification has to be persisted, asynchronous tasks are posted by the cache to a background I/O thread (DOMStorageDBThread, bellow)
    • before data can be read, the cache asynchronously preloads, such preload starts early during opening of a DOM window
    • caches are referencing its manager to be able to remove them self from the manager's hash table when no longer used by any DOMStorage object
    • a cache is held alive by DOMStorage objects who refer it
    • a cache is held alive for 20 seconds after preload or after release from the last DOMStorage instance
    • a cache is held alive by async tasks scheduled on the DB thread ; this way it cannot happen that data pending to write are only present in the task list but neither in the database nor in a cache
    • a cache removes it self from its manager's hash table when the cache is completely released, i.e. not used for some time
  • sessionStorage (just in-memory) cache specifics:
    • a cache is hard-referenced by its manager to never lose the in-memory data
    • a cache is not referencing the manager to prevent cycles
    • there is no keep-alive timer

• DOMStorageDBThread
  • class responsible for all database I/O
  • all database I/O operations are executed on a background thread when possible and optimal
  • there is only a single instance per application (even with child processes)
  • exposes methods to schedule asynchronous tasks to preload and to set/remove/clear key-value pairs of an origin as well as delete data per domain (and its sub-domains), app data and complete erase
  • asynchronous preloads are processed immediately ; but only if there is not a pending update task for the scope to preserve cached data consistency (this may happen actually only in the IPC scenario)
  • asynchronous updates, such as set/remove/clear/clear domain/clear all, are queued, being coalesced when overlapping and in short interval (~5 seconds) are flushed as a batch in a single transaction
  • when flush fails, the task list is retried until the number of unsuccessful continues flushes reaches 5 ; then the database thread refuses to work and all localStorage operations start synchronously fail
  • there are two database connections, one used by the background thread for r/w, other for the main thread to do only read operations such as sync preload

Start-up

Database is being open early during the browser start to minimize waits for preloads that are only cause of main thread blocking now.

In "sessionstore-windows-restored" observer notification a timer with 0ms delay *) is scheduled.  When the timer fires, the background I/O thread is started that opens the database.  Pre-loads of about:blank pages are blocked to prevent earlier database opening from influencing session restore time.  This way, when about:home or any web page set as a home page waits for its load from network or cache, we silently open the localStorage database in the background.  When response from the network or cache starts to be fetched, we may start preload of the localStorage data if present for the origin as soon as possible.

*) Timer is used just because of some legacy start up mechanism to be able to play with the timing.  If it's found out there is no need for a delay, this will turn to just an even dispatch to the main thread.

Preloading

When a DOM window is opening and there are data for the origin, preload of it is triggered.  This creates a cache object, if not already existing, and queues a task to load it with the origin's localStorage data.  The background thread executes the SELECT query as soon as possible and calls cache->LoadData(key, value) for each key found in the database.  After all keys has been loaded, cache->LoadDone() is called to tell the cache the load has been finished. LoadDone() method switches mLoaded flag on the cache from false to true. Since this time access to the cache no more blocks the main UI thread.  The mLoaded flag then never goes back to false.

It may happen, however, that the preload has not yet finished before a script makes access to localStorage data.  At this moment we do either of two things:

1. if the preload has already started, which means we have already started getting data, we just wait for the preload to finish
2. if the preload has not started so far, we do an immediate synchronous load of origin data on the main thread ; we can do this only when WAL mode could be set on the database connection, otherwise we fallback to the first option

According the telemetry collected so far, synchronous loads of origin data are very quick, and since we have a good chance to preload at least some data, blocking of the main thread should definitely be no worse then with the original implementation.

Here is some space to optimize.

Reading a key, it will obviously always have to block when the key has not yet been loaded:

• most obvious is if we want to read just a single key and that key has already been loaded, don't wait for the whole load
• if we want to read just a single key that has not yet been loaded, load just that one key synchronously when WAL is enabled ; according telemetry, reads from the database are very fast

Writing a key, it may be asynchronous, but we may have a problem with checking on quota usage.  However, there are bugs to make quota checking also better:

• if we want to modify just a single key and that key has already been loaded, don't wait, but be careful with quota checking
• and finally, if we want to modify just a single key that has not yet been loaded, do a rough quota check only and post StorageEvent that has to expose the old value after the key actually loaded

Cleanup is obvious, but still may hit problems with quota usage update:

• if we want to clear the whole storage, just do it and ignore the preload ; however, I don't think this is a usual scenario, who would delete persistent storage as the first operation?

I don't want to do the complicated optimization for writing before I get telemetry results.

IPC

The IPC "cut" has been made between caches (DOMStorageCache) and the database (DOMStorageDBThread).  It is an obvious edge because of its asynchronous nature.

DOMStorageDBThread is running only on the parent process.  Data are cached only on the child process(es).

There is DOMStorageCacheBridge abstract class, implemented primarily by DOMStorageCache, exposing methods to load items into the cache, already described in the 'Preloading' section.  DOMStorageCacheBridge is an interface passed as a target callback to all asynchronous tasks queued on DOMStorageDBThread.

Then, there is DOMStorageDBBridge abstract class, implemented primarily by DOMStorageDBThread, having all the methods to schedule asynchronous tasks.

On the child process, instead of DOMStorageDBThread, DOMStorageDBChild is transparently used in place of a true DB implementation.  DOMStorageDBChild, implementing DOMStorageDBBridge, forwards tasks to the parent process.

On the parent process DOMStorageDBParent is running.  It receives all requests for asynchronous tasks from its child side.  Fake DOMStorageCacheBridge implementations are passed to the real DOMStorageDBThread running on the parent process.  For a preload, that fake implementation just purely sends the loaded origin data back to the child process where DOMStorageDBChild forwards the data to the originally requesting cache.  A cache is identified across processes simply by its origin scope string.

There is one glitch, however.  When a content script demands access to localStorage sooner the preload has finished, we have to do a synchronous IPC call to finish the preload.  It is optimized at least to load only the data we didn't get so far.  I implemented it this way since IPC messages are received on the main thread and there is no WaitForMessages-like API in the chromium IPC code to just let the messages (actually processed on a background thread) be received by the main thread in a blocking way.  Time to wait for the preload can be minimized by optimizations outlined in the 'Preloading' section.  I was also thinking of sending just key names and only later send the corresponding values, maybe urgently on demand when accessing a key.  I'll be waiting for telemetry data here first to decide.

Clear cookies and other chrome initiated eviction operations

DOMStorageObserver is a singleton, started as one of the layout-statics. It observes all chrome notifications regarding cookie, domain, app, private browsing or session-only data eviction.  It schedules tasks on the database to do the actual cleanup and also notifies all existing DOMStorageManager objects they have to update their respective caches according the cleanup operation.

The DOMStorageDBChild/Parent pair is used to communicate these notifications to the child process.  DOMStorageDBChild forwards notifications to DOMStorageObserver running on the child process.  DOMStorageDBChild's implementation of clear-all and clear-domain operations is just no-op since those operations were already processed on the parent process.  Existence of the IPC bridge is ensured by instantiation of DOMLocalStorageManager happening soon during the child process startup.

Telemetry

Existing probes have not been touched.

To see how often we are blocked by a preload I introduced a new boolean probe, LOCALDOMSTORAGE_PRELOAD_PENDING_ON_FIRST_ACCESS, giving a rate of preload state on first access to localStorage data by content scripts (whether we had to wait or preload was fast enough we didn't have to block at all.)

I've added new probes to measure how long and which operation (getItem/setItem/length/key/clear) blocks on first access, if preload has not completed and we must wait.  These new probes are not accumulated when preload has already completed before first access.

Access security checks

window.localStorage:

• Access is denied when DOM storage has been disabled. 
• Access is denied from third-party IFrames if the user has disabled third-party cookies (Firefox implements this behaviour from version 43 onwards.)
• A localStorage object can be otherwise obtained from a DOM window at any time and is bound to window's principal.  The localStorage object is cached in the window.
• Following access on the cached localStorage object is always granted since localStorage is scoped by origin, not by principal objects.

window.sessionStorage:

• Access is denied when DOM storage has been disabled.
• Access is denied from third-party IFrames if the user has disabled third-party cookies (Firefox implements this behaviour from version 43 onwards.)
• If window.sessionStorage for the window has not yet been accessed, a new sessionStorage object is created and bound to the window's principal.  The sessionStorage object is cached in the window. 
• Following access to window.sessionStorage checks the current window's principal is equal-ignoring-domain with cached sessionStorage object's principal.  On a failure sessionStorage object is uncached from the window and the previous step is applied.

localStorage.* and sessionStorage.*:

Every method of DOM storage exposed to DOM and every access to storage data are checked against the subject's (caller) principal as:

• Access denied when DOM storage has been disabled.
• Access denied from third-party IFrames if the user has disabled third-party cookies (Firefox implements this behaviour from version 43 onwards.)
• Access always granted to chrome callers.
• Access denied when cookies have been disabled for a domain.
• Access denied when cookies have been globally disabled.
• Access denied when cookies lifetime decision needs to be prompted to user.
• Access denied when subject neither subsumes nor subsumes-ignoring-domain the storage principal.
• Otherwise, access is granted.