Draft

Table of Contents

Introduction

For Portable Native Client [PNaCl] (http://nativeclient.googlecode.com/svn/data/site/pnacl.pdf), we wish to be able to cache the translation of portable bitcode files to architecture-specific ELF files. The question we wish to answer in this document is: “What should manage the cache”? Should we implement caching as a web app, or implement it in the browser?

Here is a typical scenario: a user just opened multiple window tabs, each trying to load the same PNaCl app composed of N bitcode files from M different domains. These bitcode files need to be translated to ELF files that are eventually used by the dynamic linker (a nexe). The system should cache the ELF files to avoid re-translating the bitcode when unchanged.

Here is the high-level flow for a single bitcode file:


  function getPnaclTranslation(url, hash) {
    var elf_file = GetFromCache(hash);
    if (!elf_file) {
      var pnacl_file = plugin.fetchUrl(url);

      // Compute hash, since bitcode may have changed in the meantime.
      var hash2 = CalcHash(pnacl_file);

      // May want to simply stop and retry if hash != hash2

      var elf_file_w = CreateCacheEntry(hash2);

      Translate(pnacl_file, elf_file_w);

      elf_file = MakeReadOnly(elf_file_w);
    }
    return elf_file;
  }
  // Dynamic Linker will use the elf_file...

Note: for details on specifying URLs of libraries, see NameResolutionForDynamicLibraries.

Here is a diagram of how the components interact:


 [ Bitcode1 ] <------\
 [ Bitcode2 ] <-------\
 [ PNaCl App.html ] <-----> [ Cache Manager ] <--> [ Translator.nexe ]
 [ Dyn Linker.nexe ] <--/

All boxes besides the Cache Manager represent data and nexes that are likely from different domains.

Requirements

This cache and translation system must at the very least satisfy the following requirements:

  • Handle concurrency.
    • Avoid redundant concurrent translations.
    • Avoid races in writing to the cache.
  • Supply file descriptors to the translator nexe.
  • The cross-domain fetch permission should propagate to the derived data (translated ELF files in the cache).
    • I.e., the ELF files should be available to the consumer (dynamic linker) that is pulled from another domain.
  • Supply file descriptors of cache entries to dynamic linker.
  • Evict and unlink files when at capacity.
  • Use immutable files so that the linker will be able to map files directly instead of copying the data.

Other (important) requirements:

  • Be sure not to block the UI threads.
  • Handle crashes: Cache “put” operation should be atomic. Put another way, the cache should never return a partially-written file.
  • Do not cache the bitcode files (only the ELF files), since the bitcode files can be quite large and are redundant.
  • Clear cache when browser cache is cleared, or via other mechanisms.
    • Useful for deterministic testing.
    • Possibly relevant to privacy / not revealing browsing history via timing.
  • Retain ability to test translator as a standalone program.
  • Compatibility with third-party translator.nexes (e.g., one with fewer optimizations but faster startup), or multiple versions of translator.nexes.
  • Reuse cache mechanism for other purposes (e.g., Mono assemblies).
  • Have per-app, per-domain, per-X quotas.

Other issues to consider:

  • Portability of approach to other browsers.
  • Do we reuse translator instances to translate multiple bitcode files?

Options

There are at least two options to consider:

  • Option A: Manage the cache via a web app and back it with HTML FS.
  • Option B: Manage the cache in a browser broker process and back it with real files in a reserved directory.

Let's consider how the requirements will be satisfied by each option.

Option A: Manage the cache via a web app, backed by HTML FS

Being a Web App, it will need storage. The only HTML storage option that appears to have the capacity and capabilities required is the HTML Filesystem API (spec, [demo] (http://www.html5rocks.com/tutorials/file/filesystem/)). This filesystem provides domain-specific storage.

Let's go over what is needed:

  • Manage concurrent requests

  • Get file descriptors out of files in cache

    • Ideally we would have urlAsNaClDesc apply to HTML FS based URLs.
    • i.e., fd = plugin.urlAsNaClDesc(fileEntry.toURI())

  • Pass file descriptors out of the cache to dynamic linker and translator nexes.

  • Unlink files

    • Use [fileEntry.remove] (http://dev.w3.org/2009/dap/file-system/pub/FileSystem/#widl-Entry-remove)(succCB, errCB). The spec doesn't specify the semantics if a file is still in use. A worry is that, depending on the implementation on Windows, you may an error, and this would introduce platform differences (if the files are created on Windows without FILE_SHARE_DELETE).
    • Perhaps we can just gracefully handle errors.
    • We can only gracefully handle the case where remove() gets the error, not the reader/writer getting the error.
    • If the cache is full, we would have to delay a cache-put until a remove is finally successful. If we cannot unlink anything (all files are busy), then we would have to fail to add to the cache and the subsequent load will fail.

  • Immutable files

    • The Cache Web App does have a domain-isolated HTML FS, but how do we feel about making it trusted code?

Extensions made will be available to all Web Apps and not used solely by the translation cache.

In summary, the extensions appear to be:

  • plugin.urlAsNaClDesc(fileEntry.toURI())
  • window.postMessage for an FD
  • Make semantics of unlinking concrete

Option B: Manage the cache in a browser broker process, backed by a single directory

With this option, the browser will have a Cache Broker Process that is given access to a single directory in the native file system. We do not extend the capabilities of web apps (besides supplying a bitcode translation cache).

  • Manage concurrent requests

    • We will need a broker process in the browser.

  • Get file descriptors out of files in cache

    • Trivial to get.

  • Pass file descriptors out of the cache to dynamic linker and translator nexes.

    • Use chrome IPC between cache broker and NaCl plugins.
    • Re: garbage collection -- ownership transfer from cache to consumer.

  • Unlink files

    • Chrome correctly uses FILE_SHARE_DELETE so that in-use files can still be marked for deletion.

  • Immutable files

    • The cache broker manages the directory. One problem is that files are externally visible, but if that is the only way to modify cached files then you have already been owned?

Variants of Options

Here, we explore variations on the above options.

Option B-prime: Manage the cache in a browser broker process, backed by browser cache

We could go with Option B, but instead of giving the cache broker ownership of a fresh/isolated directory we could reuse the browser cache ([e.g., the Chromium Disk Cache] (http://www.chromium.org/developers/design-documents/network-stack/disk-cache)).

  • The chrome cache has an option to store entries as as individual files, so we can still get FDs.
    • Will need to investigate.
  • Chrome already has separate caches for video, etc., so we can still tune the size of the cache, don't have to worry about competing with other types of files for cache space, etc.
  • We get to reuse the chrome cache meta-data for LRU, journaling, clearing the cache happens naturally, etc.

Option B-double-prime: Manage the cache in the browser process, backed by browser cache

This is a variation of Option B where we add logic to the browser process instead of having a separate broker process.

  • May be easiest for a first-cut.
  • Do not need to wait for a general Pepper Broker Abstraction.

Current Leanings

Go with Option B double-prime, since it does not need to face unspecified behavior (unlink behavior in the FS), and does not require extensions to the web app platform. We also get to reuse much of the chrome code including its cache. The drawback is that this appears to be chrome-specific. However, every browser has a browser cache, so presumably this can be done for other browsers. Once Pepper has a broker abstraction, we could move this cache logic out of the browser process into a broker process.

Other Requirements / Issues

This section explores the secondary requirements and issues related to client-side translation caches.

Compatiblity with Alternative Translator.nexes

We can create a separate cache instance based on a hash of the translator.nexe. TODO: Look into the details of doing so with each option.

The Translator May Consist of Multiple Components

The “translator” component will actually involve two nexes (llc and ld) for quite a while. It will not be a single nexe until llc is taught all of the linker logic -- optimize TLS accesses, generate GOT and PLT entries, generate DT_NEEDED, etc.. This also means that:

  • We may need two files -- one more for the intermediate file -- instead of just the one for the final output. Alternatively, we can try to use shared memory tagged with an explicit file size for the intermediate data.
  • We need to be able to atomically update the translator and linker. This is possible if we specify them in the manifest file and update the hashes (assuming we use the hashing scheme) atomically.

Notes on Persisting Instances of the Translator to Translate Multiple BC files

Persisting and reusing instances of the translator nexe will save on startup cost. However, even if we limit this persistence/sharing to a single domain there are ways in which a malicious individual could affect multiple domains. Mark's example:

  • Translator starts up
  • Translator receives a malicious.bc and gets owned
  • Translator behavior is now changed
  • Changed translator persists and mistranslates domainA:libgood.so.bc, which has hash X. The mistranslation doubles numeric literals that may refer to prices.
  • Next time another app wants to use domainB:libgood.so.bc which also has hash X. Since we only check hashes in the cache, the dynamic linker will be supplied with the cached mistranslated version.

Not Storing Bitcode vs Not Using Hashes

See the ShareByHash document for background. It is possible to detect that files have changed without ShareByHash using the typical Browser Cache mechanisms (e.g., Timestamp + ETags). That option has the following implications:

  • We would need to store the bitcode file in the browser cache, since we need to know if the bitcode has changed. The bitcode files are typically larger than the ELF files and are redundant.
  • This would imply using Option B, since it is unlikely that the Web App Platform would be extended with an API for checking if data is already in the browser cache.
  • ETags have zero guarantees in the case that the same bitcode file is hosted at different URLs (we would not be able to share cached ELF files).
  • Unknown: How to allow developers to opt-in to silent updates of libraries like libpepper and libc with the content-hash scheme.

Related

  • DSO name resolution design document: NameResolutionForDynamicLibraries
  • Share-by-hash design document: ShareByHash