// Copyright 2015 The Vanadium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package impl

// The app invoker is responsible for managing the state of applications on the
// device manager.  The device manager manages the applications it installs and
// runs using the following directory structure.  Permissions and owners are
// noted as parentheses enclosed octal perms with an 'a' or 'd' suffix for app
// or device manager respectively.  For example: (755d)
//
// TODO(caprita): Not all is yet implemented.
//
// <config.Root>(711d)/
//   app-<hash 1>(711d)/                  - the application dir is named using a hash of the application title
//     installation-<id 1>(711d)/         - installations are labelled with ids
//       acls(700d)/
//         data(700d)                     - the AccessList data for this
//                                          installation. Controls access to
//                                          Instantiate, Uninstall, Update,
//                                          UpdateTo and Revert.
//         signature(700d)                - the signature for the AccessLists in data
//       <status>(700d)                   - one of the values for InstallationState enum
//       origin(700d)                     - object name for application envelope
//       config(700d)                     - Config provided by the installer
//       packages(700d)                   - set of packages specified by the installer
//       pkg(700d)/                       - downloaded packages
//         <pkg name>(700d)
//         <pkg name>.__info(700d)
//         ...
//       <version 1 timestamp>(711d)/     - timestamp of when the version was downloaded
//         bin(755d)                      - application binary
//         previous                       - symbolic link to previous version directory
//         envelope                       - application envelope (JSON-encoded)
//         packages(755d)/                - installed packages (from envelope+installer)
//           <pkg name>(755d)/
//           ...
//       <version 2 timestamp>(711d)
//       ...
//       current                          - symbolic link to the current version
//       instances(711d)/
//         instance-<id a>(711d)/         - instances are labelled with ids
//           credentials(700d)/           - holds vanadium credentials (unless running
//                                          through security agent)
//           root(700a)/                  - workspace that the instance is run from
//             packages                   - symbolic link to version's packages
//           logs(755a)/                  - stderr/stdout and log files generated by instance
//           info(700d)                   - metadata for the instance (such as app
//                                          cycle manager name and process id)
//           installation                 - symbolic link to installation for the instance
//           version                      - symbolic link to installation version for the instance
//           agent-sock-dir               - symbolic link to the agent socket dir
//           acls(700d)/
//             data(700d)                 - the AccessLists for this instance. These
//                                          AccessLists control access to Run,
//                                          Kill and Delete.
//             signature(700d)            - the signature for these AccessLists.
//           <status>(700d)               - one of the values for InstanceState enum
//           systemname(700d)             - the system name used to execute this instance
//           debugacls (711d)/
//             data(644)/                 - the Permissions for Debug access to the application. Shared
//                                          with the application.
//             signature(644)/            - the signature for these Permissions.
//         instance-<id b>(711d)
//         ...
//     installation-<id 2>(711d)
//     ...
//   app-<hash 2>(711d)
//   ...
//
// The device manager uses the suid helper binary to invoke an application as a
// specified user.  The path to the helper is specified as config.Helper.

// When device manager starts up, it goes through all instances and launches the
// ones that are not running.  If an instance fails to launch, it stays not
// running.
//
// Instantiate creates an instance.  Run launches the process.  Kill kills the
// process but leaves the workspace untouched.  Delete prevents future launches
// (it also eventually gc's the workspace, logs, and other instance state).
//
// If the process dies on its own, it stays dead and is assumed not running.
// TODO(caprita): Later, we'll add auto-restart option.
//
// Concurrency model: installations can be created independently of one another;
// installations can be removed at any time (TODO(caprita): ensure all instances
// are Deleted).  The first call to Uninstall will rename the installation dir
// as a first step; subsequent Uninstall's will fail.  Instances can be created
// independently of one another, as long as the installation exists (if it gets
// Uninstall'ed during a Instantiate, the Instantiate call may fail).
//
// The status file present in each instance is used to flag the state of the
// instance and prevent concurrent operations against the instance:
//
// - when an instance is created with Instantiate, it is placed in state
// 'not-running'.
//
// - Run attempts to transition from 'not-running' to 'launching' (if the
// instance was not in 'not-running' state, Run fails).  From 'launching', the
// instance transitions to 'running' upon success or back to 'not-running' upon
// failure.
//
// - Kill attempts to transition from 'running' to 'dying' (if the
// instance was not in 'running' state, Kill fails).  From 'dying', the
// instance transitions to 'not-running' upon success or back to 'running' upon
// failure.
//
// - Delete transitions from 'not-running' to 'deleted'.  If the initial
// state is not 'not-running', Delete fails.
//
// TODO(caprita): There is room for synergy between how device manager organizes
// its own workspace and that for the applications it runs.  In particular,
// previous, origin, and envelope could be part of a single config.  We'll
// refine that later.

import (
	"bytes"
	"crypto/md5"
	"encoding/base64"
	"encoding/json"
	"fmt"
	"io/ioutil"
	"os"
	"os/exec"
	"path"
	"path/filepath"
	"reflect"
	"regexp"
	"strconv"
	"strings"
	"text/template"
	"time"

	"v.io/v23"
	"v.io/v23/context"
	"v.io/v23/glob"
	"v.io/v23/naming"
	"v.io/v23/rpc"
	"v.io/v23/security"
	"v.io/v23/security/access"
	"v.io/v23/services/appcycle"
	"v.io/v23/services/application"
	"v.io/v23/services/device"
	"v.io/v23/verror"
	"v.io/v23/vom"
	"v.io/x/ref"
	vexec "v.io/x/ref/lib/exec"
	"v.io/x/ref/lib/mgmt"
	"v.io/x/ref/services/agent"
	"v.io/x/ref/services/device/internal/config"
	"v.io/x/ref/services/device/internal/errors"
	"v.io/x/ref/services/internal/packages"
	"v.io/x/ref/services/internal/pathperms"
)

// instanceInfo holds state about an instance.
type instanceInfo struct {
	AppCycleMgrName string
	Pid             int

	// Blessings to provide the AppCycleManager in the app with so that it can talk
	// to the device manager.
	AppCycleBlessings  string
	Restarts           int32
	RestartWindowBegan time.Time
}

func saveInstanceInfo(ctx *context.T, dir string, info *instanceInfo) error {
	jsonInfo, err := json.Marshal(info)
	if err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Marshal(%v) failed: %v", info, err))
	}
	infoPath := filepath.Join(dir, "info")
	if err := ioutil.WriteFile(infoPath, jsonInfo, 0600); err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("WriteFile(%v) failed: %v", infoPath, err))
	}
	return nil
}

func loadInstanceInfo(ctx *context.T, dir string) (*instanceInfo, error) {
	infoPath := filepath.Join(dir, "info")
	info := new(instanceInfo)
	if infoBytes, err := ioutil.ReadFile(infoPath); err != nil {
		return nil, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("ReadFile(%v) failed: %v", infoPath, err))
	} else if err := json.Unmarshal(infoBytes, info); err != nil {
		return nil, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Unmarshal(%v) failed: %v", infoBytes, err))
	}
	return info, nil
}

// appRunner is the subset of the appService object needed to
// (re)start an application.
type appRunner struct {
	callback *callbackState
	// principalMgr handles principals for the apps.
	principalMgr principalManager
	// reap is the app process monitoring subsystem.
	reap *reaper
	// mtAddress is the address of the local mounttable.
	mtAddress string
	// appServiceName is a name by which the appService can be reached
	appServiceName string
	stats          *stats
}

// appService implements the Device manager's Application interface.
type appService struct {
	config *config.State
	// suffix contains the name components of the current invocation name
	// suffix.  It is used to identify an application, installation, or
	// instance.
	suffix     []string
	uat        BlessingSystemAssociationStore
	permsStore *pathperms.PathStore
	// Reference to the devicemanager top-level AccessList list.
	deviceAccessList access.Permissions
	// State needed to (re)start an application.
	runner *appRunner
	stats  *stats
}

func saveEnvelope(ctx *context.T, dir string, envelope *application.Envelope) error {
	jsonEnvelope, err := json.Marshal(envelope)
	if err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Marshal(%v) failed: %v", envelope, err))
	}
	path := filepath.Join(dir, "envelope")
	if err := ioutil.WriteFile(path, jsonEnvelope, 0600); err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("WriteFile(%v) failed: %v", path, err))
	}
	return nil
}

func loadEnvelope(ctx *context.T, dir string) (*application.Envelope, error) {
	path := filepath.Join(dir, "envelope")
	envelope := new(application.Envelope)
	if envelopeBytes, err := ioutil.ReadFile(path); err != nil {
		return nil, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("ReadFile(%v) failed: %v", path, err))
	} else if err := json.Unmarshal(envelopeBytes, envelope); err != nil {
		return nil, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Unmarshal(%v) failed: %v", envelopeBytes, err))
	}
	return envelope, nil
}

func loadEnvelopeForInstance(ctx *context.T, instanceDir string) (*application.Envelope, error) {
	versionLink := filepath.Join(instanceDir, "version")
	versionDir, err := filepath.EvalSymlinks(versionLink)
	if err != nil {
		return nil, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("EvalSymlinks(%v) failed: %v", versionLink, err))
	}
	return loadEnvelope(ctx, versionDir)
}

func saveConfig(ctx *context.T, dir string, config device.Config) error {
	jsonConfig, err := json.Marshal(config)
	if err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Marshal(%v) failed: %v", config, err))
	}
	path := filepath.Join(dir, "config")
	if err := ioutil.WriteFile(path, jsonConfig, 0600); err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("WriteFile(%v) failed: %v", path, err))
	}
	return nil
}

func loadConfig(ctx *context.T, dir string) (device.Config, error) {
	path := filepath.Join(dir, "config")
	var config device.Config
	if configBytes, err := ioutil.ReadFile(path); err != nil {
		return nil, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("ReadFile(%v) failed: %v", path, err))
	} else if err := json.Unmarshal(configBytes, &config); err != nil {
		return nil, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Unmarshal(%v) failed: %v", configBytes, err))
	}
	return config, nil
}

func savePackages(ctx *context.T, dir string, packages application.Packages) error {
	jsonPackages, err := json.Marshal(packages)
	if err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Marshal(%v) failed: %v", packages, err))
	}
	path := filepath.Join(dir, "packages")
	if err := ioutil.WriteFile(path, jsonPackages, 0600); err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("WriteFile(%v) failed: %v", path, err))
	}
	return nil
}

func loadPackages(ctx *context.T, dir string) (application.Packages, error) {
	path := filepath.Join(dir, "packages")
	var packages application.Packages
	if packagesBytes, err := ioutil.ReadFile(path); err != nil {
		return nil, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("ReadFile(%v) failed: %v", path, err))
	} else if err := json.Unmarshal(packagesBytes, &packages); err != nil {
		return nil, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Unmarshal(%v) failed: %v", packagesBytes, err))
	}
	return packages, nil
}

func saveOrigin(ctx *context.T, dir, originVON string) error {
	path := filepath.Join(dir, "origin")
	if err := ioutil.WriteFile(path, []byte(originVON), 0600); err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("WriteFile(%v) failed: %v", path, err))
	}
	return nil
}

func loadOrigin(ctx *context.T, dir string) (string, error) {
	path := filepath.Join(dir, "origin")
	if originBytes, err := ioutil.ReadFile(path); err != nil {
		return "", verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("ReadFile(%v) failed: %v", path, err))
	} else {
		return string(originBytes), nil
	}
}

// generateID returns a new unique id string.  The uniqueness is based on the
// current timestamp.  Not cryptographically secure.
func generateID() string {
	const timeFormat = "20060102-15:04:05.0000"
	return time.Now().UTC().Format(timeFormat)
}

// TODO(caprita): Nothing prevents different applications from sharing the same
// title, and thereby being installed in the same app dir.  Do we want to
// prevent that for the same user or across users?

const (
	appDirPrefix       = "app-"
	installationPrefix = "installation-"
	instancePrefix     = "instance-"
)

// applicationDirName generates a cryptographic hash of the application title,
// to be used as a directory name for installations of the application with the
// given title.
func applicationDirName(title string) string {
	h := md5.New()
	h.Write([]byte(title))
	hash := strings.TrimRight(base64.URLEncoding.EncodeToString(h.Sum(nil)), "=")
	return appDirPrefix + hash
}

func installationDirName(installationID string) string {
	return installationPrefix + installationID
}

func instanceDirName(instanceID string) string {
	return instancePrefix + instanceID
}

func mkdir(ctx *context.T, dir string) error {
	return mkdirPerm(ctx, dir, 0700)
}

func mkdirPerm(ctx *context.T, dir string, permissions int) error {
	perm := os.FileMode(permissions)
	if err := os.MkdirAll(dir, perm); err != nil {
		ctx.Errorf("MkdirAll(%v, %v) failed: %v", dir, perm, err)
		return err
	}
	return nil
}

func sockPath(instanceDir string) (string, error) {
	sockLink := filepath.Join(instanceDir, "agent-sock-dir")
	sock, err := filepath.EvalSymlinks(sockLink)
	if err != nil {
		return "", err
	}
	return filepath.Join(sock, "s"), nil
}

func fetchAppEnvelope(ctx *context.T, origin string) (*application.Envelope, error) {
	envelope, err := fetchEnvelope(ctx, origin)
	if err != nil {
		return nil, err
	}
	if envelope.Title == application.DeviceManagerTitle {
		// Disallow device manager apps from being installed like a
		// regular app.
		return nil, verror.New(errors.ErrInvalidOperation, ctx, "DeviceManager apps cannot be installed")
	}
	return envelope, nil
}

// newVersion sets up the directory for a new application version.
func newVersion(ctx *context.T, installationDir string, envelope *application.Envelope, oldVersionDir string) (string, error) {
	versionDir := filepath.Join(installationDir, generateVersionDirName())
	if err := mkdirPerm(ctx, versionDir, 0711); err != nil {
		return "", verror.New(errors.ErrOperationFailed, ctx, err)
	}
	if err := saveEnvelope(ctx, versionDir, envelope); err != nil {
		return versionDir, err
	}
	pkgDir := filepath.Join(versionDir, "pkg")
	if err := mkdir(ctx, pkgDir); err != nil {
		return "", verror.New(errors.ErrOperationFailed, ctx, err)
	}
	publisher := envelope.Publisher
	// TODO(caprita): Share binaries if already existing locally.
	if err := downloadBinary(ctx, publisher, &envelope.Binary, versionDir, "bin"); err != nil {
		return versionDir, err
	}
	if err := downloadPackages(ctx, publisher, envelope.Packages, pkgDir); err != nil {
		return versionDir, err
	}
	if err := installPackages(ctx, installationDir, versionDir); err != nil {
		return versionDir, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("installPackages(%v, %v) failed: %v", installationDir, versionDir, err))
	}
	if err := os.RemoveAll(pkgDir); err != nil {
		return versionDir, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("RemoveAll(%v) failed: %v", pkgDir, err))
	}
	if oldVersionDir != "" {
		previousLink := filepath.Join(versionDir, "previous")
		if err := os.Symlink(oldVersionDir, previousLink); err != nil {
			return versionDir, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Symlink(%v, %v) failed: %v", oldVersionDir, previousLink, err))
		}
	}
	// UpdateLink should be the last thing we do, after we've ensured the
	// new version is viable (currently, that just means it installs
	// properly).
	return versionDir, UpdateLink(versionDir, filepath.Join(installationDir, "current"))
}

func (i *appService) Install(ctx *context.T, call rpc.ServerCall, applicationVON string, config device.Config, packages application.Packages) (string, error) {
	if len(i.suffix) > 0 {
		return "", verror.New(errors.ErrInvalidSuffix, ctx)
	}
	ctx, cancel := context.WithTimeout(ctx, rpcContextLongTimeout)
	defer cancel()
	envelope, err := fetchAppEnvelope(ctx, applicationVON)
	if err != nil {
		return "", err
	}
	installationID := generateID()
	installationDir := filepath.Join(i.config.Root, applicationDirName(envelope.Title), installationDirName(installationID))
	deferrer := func() {
		CleanupDir(ctx, installationDir, "")
	}
	if err := mkdirPerm(ctx, installationDir, 0711); err != nil {
		return "", verror.New(errors.ErrOperationFailed, nil)
	}
	defer func() {
		if deferrer != nil {
			deferrer()
		}
	}()
	if newOrigin, ok := config[mgmt.AppOriginConfigKey]; ok {
		delete(config, mgmt.AppOriginConfigKey)
		applicationVON = newOrigin
	}
	if err := saveOrigin(ctx, installationDir, applicationVON); err != nil {
		return "", err
	}
	if err := saveConfig(ctx, installationDir, config); err != nil {
		return "", err
	}
	if err := savePackages(ctx, installationDir, packages); err != nil {
		return "", err
	}
	pkgDir := filepath.Join(installationDir, "pkg")
	if err := mkdir(ctx, pkgDir); err != nil {
		return "", verror.New(errors.ErrOperationFailed, ctx, err)
	}
	// We use a zero value publisher, meaning that any signatures present in the
	// package files are not verified.
	// TODO(caprita): Issue warnings when signatures are present and ignored.
	if err := downloadPackages(ctx, security.Blessings{}, packages, pkgDir); err != nil {
		return "", err
	}
	if _, err := newVersion(ctx, installationDir, envelope, ""); err != nil {
		return "", err
	}
	// TODO(caprita,rjkroege): Should the installation AccessLists really be
	// seeded with the device AccessList? Instead, might want to hide the deviceAccessList
	// from the app?
	blessings, _ := security.RemoteBlessingNames(ctx, call.Security())
	if err := i.initializeSubAccessLists(installationDir, blessings, i.deviceAccessList.Copy()); err != nil {
		return "", err
	}
	if err := initializeInstallation(installationDir, device.InstallationStateActive); err != nil {
		return "", err
	}
	deferrer = nil
	// TODO(caprita): Using the title without cleaning out slashes
	// introduces extra name components that mess up the device manager's
	// apps object space.  We should fix this either by santizing the title,
	// or disallowing slashes in titles to begin with.
	return naming.Join(envelope.Title, installationID), nil
}

func openWriteFile(path string) (*os.File, error) {
	perm := os.FileMode(0644)
	return os.OpenFile(path, os.O_WRONLY|os.O_CREATE, perm)
}

// TODO(gauthamt): Make sure we pass the context to installationDirCore.
func installationDirCore(components []string, root string) (string, error) {
	if nComponents := len(components); nComponents != 2 {
		return "", verror.New(errors.ErrInvalidSuffix, nil)
	}
	app, installation := components[0], components[1]
	installationDir := filepath.Join(root, applicationDirName(app), installationDirName(installation))
	if _, err := os.Stat(installationDir); err != nil {
		if os.IsNotExist(err) {
			return "", verror.New(verror.ErrNoExist, nil, naming.Join(components...))
		}
		return "", verror.New(errors.ErrOperationFailed, nil, fmt.Sprintf("Stat(%v) failed: %v", installationDir, err))
	}
	return installationDir, nil
}

// setupPrincipal sets up the instance's principal, with the right blessings.
func setupPrincipal(ctx *context.T, instanceDir string, call device.ApplicationInstantiateServerCall, principalMgr principalManager, info *instanceInfo, rootDir string) error {
	if err := principalMgr.Create(instanceDir); err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Create(%v) failed: %v", instanceDir, err))
	}
	if err := principalMgr.Serve(instanceDir, nil); err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Serve(%v) failed: %v", instanceDir, err))
	}
	defer principalMgr.StopServing(instanceDir)
	p, err := principalMgr.Load(instanceDir)
	if err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Load(%v) failed: %v", instanceDir, err))
	}
	defer p.Close()

	mPubKey, err := p.PublicKey().MarshalBinary()
	if err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("PublicKey().MarshalBinary() failed: %v", err))
	}
	if err := call.SendStream().Send(device.BlessServerMessageInstancePublicKey{Value: mPubKey}); err != nil {
		return err
	}
	if !call.RecvStream().Advance() {
		return verror.New(errors.ErrInvalidBlessing, ctx, fmt.Sprintf("no blessings on stream: %v", call.RecvStream().Err()))
	}
	msg := call.RecvStream().Value()
	appBlessingsFromInstantiator, ok := msg.(device.BlessClientMessageAppBlessings)
	if !ok {
		return verror.New(errors.ErrInvalidBlessing, ctx, fmt.Sprintf("wrong message type: %#v", msg))
	}
	// Should we move this after the addition of publisher blessings, and thus allow
	// apps to run with only publisher blessings?
	if appBlessingsFromInstantiator.Value.IsZero() {
		return verror.New(errors.ErrInvalidBlessing, ctx)
	}
	if err := p.BlessingStore().SetDefault(appBlessingsFromInstantiator.Value); err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("BlessingStore.SetDefault() failed: %v", err))
	}
	// If there were any publisher blessings in the envelope, add those to the set of blessings
	// sent to servers by default
	appBlessings, err := addPublisherBlessings(ctx, instanceDir, p, appBlessingsFromInstantiator.Value)
	if _, err := p.BlessingStore().Set(appBlessings, security.AllPrincipals); err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("BlessingStore.Set() failed: %v", err))
	}
	if err := security.AddToRoots(p, appBlessings); err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("AddToRoots() failed: %v", err))
	}
	// In addition, we give the app separate blessings for the purpose of
	// communicating with the device manager.
	info.AppCycleBlessings, err = createCallbackBlessings(ctx, p.PublicKey())
	return err
}

func addPublisherBlessings(ctx *context.T, instanceDir string, p security.Principal, b security.Blessings) (security.Blessings, error) {
	// Load the envelope for the instance, and get the publisher blessings in it
	envelope, err := loadEnvelopeForInstance(ctx, instanceDir)
	if err != nil {
		return security.Blessings{}, err
	}

	// Extend the device manager blessing with each publisher blessing provided
	dmPrincipal := v23.GetPrincipal(ctx)
	dmBlessings, _ := dmPrincipal.BlessingStore().Default()

	blessings, _ := publisherBlessingNames(ctx, *envelope)
	for _, s := range blessings {
		ctx.VI(2).Infof("adding publisher blessing %v for app %v", s, envelope.Title)
		tmpBlessing, err := dmPrincipal.Bless(p.PublicKey(), dmBlessings, "a"+security.ChainSeparator+s, security.UnconstrainedUse())
		if err != nil {
			return b, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Bless failed: %v", err))
		}
		if b, err = security.UnionOfBlessings(b, tmpBlessing); err != nil {
			return b, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("UnionOfBlessings failed: %v %v", b, tmpBlessing))
		}
	}

	return b, nil
}

// installationDir returns the path to the directory containing the app
// installation referred to by the invoker's suffix.  Returns an error if the
// suffix does not name an installation or if the named installation does not
// exist.
func (i *appService) installationDir() (string, error) {
	return installationDirCore(i.suffix, i.config.Root)
}

// installPackages installs all the packages for a new version.
func installPackages(ctx *context.T, installationDir, versionDir string) error {
	overridePackages, err := loadPackages(ctx, installationDir)
	if err != nil {
		return err
	}
	envelope, err := loadEnvelope(ctx, versionDir)
	if err != nil {
		return err
	}
	for pkg, _ := range overridePackages {
		delete(envelope.Packages, pkg)
	}
	packagesDir := filepath.Join(versionDir, "packages")
	if err := os.MkdirAll(packagesDir, os.FileMode(0755)); err != nil {
		return err
	}
	installFrom := func(pkgs application.Packages, sourceDir string) error {
		for pkg, _ := range pkgs {
			pkgFile := filepath.Join(sourceDir, "pkg", pkg)
			dst := filepath.Join(packagesDir, pkg)
			if err := packages.Install(pkgFile, dst); err != nil {
				return err
			}
		}
		return nil
	}
	if err := installFrom(envelope.Packages, versionDir); err != nil {
		return err
	}
	return installFrom(overridePackages, installationDir)
}

// initializeSubAccessLists updates the provided perms for instance-specific
// Permissions.
func (i *appService) initializeSubAccessLists(instanceDir string, blessings []string, perms access.Permissions) error {
	for _, b := range blessings {
		b = b + string(security.ChainSeparator) + string(security.NoExtension)
		for _, tag := range access.AllTypicalTags() {
			perms.Add(security.BlessingPattern(b), string(tag))
		}
	}
	permsDir := path.Join(instanceDir, "acls")
	return i.permsStore.Set(permsDir, perms, "")
}

func (i *appService) newInstance(ctx *context.T, call device.ApplicationInstantiateServerCall) (string, string, error) {
	installationDir, err := i.installationDir()
	if err != nil {
		return "", "", err
	}
	if !installationStateIs(installationDir, device.InstallationStateActive) {
		return "", "", verror.New(errors.ErrInvalidOperation, ctx)
	}
	instanceID := generateID()
	instanceDir := filepath.Join(installationDir, "instances", instanceDirName(instanceID))
	// Set permissions for app to have access.
	if mkdirPerm(ctx, instanceDir, 0711) != nil {
		return "", "", verror.New(errors.ErrOperationFailed, ctx)
	}
	rootDir := filepath.Join(instanceDir, "root")
	if err := mkdir(ctx, rootDir); err != nil {
		return instanceDir, instanceID, verror.New(errors.ErrOperationFailed, ctx, err)
	}
	installationLink := filepath.Join(instanceDir, "installation")
	if err := os.Symlink(installationDir, installationLink); err != nil {
		return instanceDir, instanceID, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Symlink(%v, %v) failed: %v", installationDir, installationLink, err))
	}
	currLink := filepath.Join(installationDir, "current")
	versionDir, err := filepath.EvalSymlinks(currLink)
	if err != nil {
		return instanceDir, instanceID, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("EvalSymlinks(%v) failed: %v", currLink, err))
	}
	versionLink := filepath.Join(instanceDir, "version")
	if err := os.Symlink(versionDir, versionLink); err != nil {
		return instanceDir, instanceID, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Symlink(%v, %v) failed: %v", versionDir, versionLink, err))
	}
	packagesDir, packagesLink := filepath.Join(versionLink, "packages"), filepath.Join(rootDir, "packages")
	if err := os.Symlink(packagesDir, packagesLink); err != nil {
		return instanceDir, instanceID, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Symlink(%v, %v) failed: %v", packagesDir, packagesLink, err))
	}
	instanceInfo := new(instanceInfo)
	if err := setupPrincipal(ctx, instanceDir, call, i.runner.principalMgr, instanceInfo, i.config.Root); err != nil {
		return instanceDir, instanceID, err
	}
	if err := saveInstanceInfo(ctx, instanceDir, instanceInfo); err != nil {
		return instanceDir, instanceID, err
	}
	blessings, _ := security.RemoteBlessingNames(ctx, call.Security())
	permsCopy := i.deviceAccessList.Copy()
	if err := i.initializeSubAccessLists(instanceDir, blessings, permsCopy); err != nil {
		return instanceDir, instanceID, err
	}
	if err := initializeInstance(instanceDir, device.InstanceStateNotRunning); err != nil {
		return instanceDir, instanceID, err
	}
	// TODO(rjkroege): Divide the permission lists into those used by the device manager
	// and those used by the application itself.
	dmBlessings := security.LocalBlessingNames(ctx, call.Security())
	if err := setPermsForDebugging(dmBlessings, permsCopy, instanceDir, i.permsStore); err != nil {
		return instanceDir, instanceID, err
	}
	return instanceDir, instanceID, nil
}

func genCmd(ctx *context.T, instanceDir, nsRoot string) (*exec.Cmd, error) {
	systemName, err := readSystemNameForInstance(instanceDir)
	if err != nil {
		return nil, err
	}

	versionLink := filepath.Join(instanceDir, "version")
	versionDir, err := filepath.EvalSymlinks(versionLink)
	if err != nil {
		return nil, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("EvalSymlinks(%v) failed: %v", versionLink, err))
	}
	envelope, err := loadEnvelope(ctx, versionDir)
	if err != nil {
		return nil, err
	}
	binPath := filepath.Join(versionDir, "bin")
	if _, err := os.Stat(binPath); err != nil {
		return nil, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Stat(%v) failed: %v", binPath, err))
	}

	saArgs := suidAppCmdArgs{targetUser: systemName, binpath: binPath}

	// Pass the displayed name of the program (argv0 as seen in ps output)
	// Envelope data comes from the user so we sanitize it for safety
	_, relativeBinaryName := naming.SplitAddressName(envelope.Binary.File)
	rawAppName := envelope.Title + "@" + relativeBinaryName + "/app"
	sanitize := func(r rune) rune {
		if strconv.IsPrint(r) {
			return r
		} else {
			return '_'
		}
	}
	appName := strings.Map(sanitize, rawAppName)
	saArgs.progname = appName

	// Set the app's default namespace root to the local namespace.
	saArgs.env = []string{ref.EnvNamespacePrefix + "=" + nsRoot}
	saArgs.env = append(saArgs.env, envelope.Env...)
	rootDir := filepath.Join(instanceDir, "root")
	saArgs.dir = rootDir
	saArgs.workspace = rootDir

	logDir := filepath.Join(instanceDir, "logs")
	suidHelper.chownTree(ctx, suidHelper.getCurrentUser(), instanceDir, os.Stdout, os.Stdin)
	if err := mkdirPerm(ctx, logDir, 0755); err != nil {
		return nil, err
	}
	saArgs.logdir = logDir
	timestamp := time.Now().UnixNano()

	stdoutLog := filepath.Join(logDir, fmt.Sprintf("STDOUT-%d", timestamp))
	if saArgs.stdout, err = openWriteFile(stdoutLog); err != nil {
		return nil, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("OpenFile(%v) failed: %v", stdoutLog, err))
	}
	stderrLog := filepath.Join(logDir, fmt.Sprintf("STDERR-%d", timestamp))
	if saArgs.stderr, err = openWriteFile(stderrLog); err != nil {
		return nil, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("OpenFile(%v) failed: %v", stderrLog, err))
	}

	// Args to be passed by helper to the app.
	appArgs := []string{"--log_dir=../logs"}
	appArgs = append(appArgs, envelope.Args...)

	saArgs.appArgs = appArgs
	return suidHelper.getAppCmd(ctx, &saArgs)
}

// instanceNameFromDir returns the instance name, given the instanceDir.
func instanceNameFromDir(ctx *context.T, instanceDir string) (string, error) {
	_, _, installation, instance := parseInstanceDir(instanceDir)
	if installation == "" || instance == "" {
		return "", fmt.Errorf("Unable to parse instanceDir %v", instanceDir)
	}

	env, err := loadEnvelopeForInstance(ctx, instanceDir)
	if err != nil {
		return "", err
	}
	return env.Title + "/" + installation + "/" + instance, nil
}

func (i *appRunner) startCmd(ctx *context.T, instanceDir string, cmd *exec.Cmd) (int, error) {
	info, err := loadInstanceInfo(ctx, instanceDir)
	if err != nil {
		return 0, err
	}
	// Setup up the child process callback.
	callbackState := i.callback
	listener := callbackState.listenFor(ctx, mgmt.AppCycleManagerConfigKey)
	defer listener.cleanup()
	cfg := vexec.NewConfig()
	installationLink := filepath.Join(instanceDir, "installation")
	installationDir, err := filepath.EvalSymlinks(installationLink)
	if err != nil {
		return 0, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("EvalSymlinks(%v) failed: %v", installationLink, err))
	}
	config, err := loadConfig(ctx, installationDir)
	if err != nil {
		return 0, err
	}
	for k, v := range config {
		cfg.Set(k, v)
	}
	publisherBlessingsPrefix, _ := v23.GetPrincipal(ctx).BlessingStore().Default()
	cfg.Set(mgmt.ParentNameConfigKey, listener.name())
	cfg.Set(mgmt.ProtocolConfigKey, "tcp")
	cfg.Set(mgmt.AddressConfigKey, "127.0.0.1:0")
	cfg.Set(mgmt.PublisherBlessingPrefixesKey, publisherBlessingsPrefix.String())
	if len(info.AppCycleBlessings) == 0 {
		return 0, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("info.AppCycleBessings is missing"))
	}
	cfg.Set(mgmt.AppCycleBlessingsKey, info.AppCycleBlessings)

	if instanceName, err := instanceNameFromDir(ctx, instanceDir); err != nil {
		return 0, err
	} else {
		cfg.Set(mgmt.InstanceNameKey, naming.Join(i.appServiceName, instanceName))
	}

	appPermsDir := filepath.Join(instanceDir, "debugacls", "data")
	cfg.Set("v23.permissions.file", "runtime:"+appPermsDir)

	// This adds to cmd.Extrafiles. The helper expects a fixed fd, so this call needs
	// to go before anything that conditionally adds to Extrafiles, like the agent
	// setup code immediately below.
	var handshaker appHandshaker
	if err := handshaker.prepareToStart(ctx, cmd); err != nil {
		return 0, err
	}
	defer handshaker.cleanup()

	if err := i.principalMgr.Serve(instanceDir, cfg); err != nil {
		return 0, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Serve(%v) failed: %v", instanceDir, err))
	}
	stopServing := true
	defer func() {
		if !stopServing {
			return
		}
		if err := i.principalMgr.StopServing(instanceDir); err != nil {
			ctx.Errorf("StopServing failed: %v", err)
		}
	}()
	env, err := vexec.WriteConfigToEnv(cfg, cmd.Env)
	if err != nil {
		return 0, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("encoding config failed %v", err))
	}
	cmd.Env = env

	// Start the child process.
	if startErr := cmd.Start(); startErr != nil {
		return 0, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Start() failed: %v", err))
	}

	// Wait for the suidhelper to exit. This is blocking as we assume the
	// helper won't get stuck.
	if err := cmd.Wait(); err != nil {
		return 0, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Wait() on suidhelper failed: %v", err))
	}

	defer ctx.FlushLog()
	pid, childName, err := handshaker.doHandshake(ctx, cmd, listener)

	if err != nil {
		return 0, err
	}

	info.AppCycleMgrName, info.Pid = childName, pid
	if err := saveInstanceInfo(ctx, instanceDir, info); err != nil {
		return 0, err
	}
	stopServing = false
	return pid, nil
}

func (i *appRunner) run(ctx *context.T, instanceDir string) error {
	if err := transitionInstance(instanceDir, device.InstanceStateNotRunning, device.InstanceStateLaunching); err != nil {
		return err
	}
	var pid int

	cmd, err := genCmd(ctx, instanceDir, i.mtAddress)
	if err == nil {
		pid, err = i.startCmd(ctx, instanceDir, cmd)
	}
	// TODO(caprita): If startCmd fails, we never reach startWatching; this
	// means that the restart policy never kicks in, and the app stays dead.
	// We should allow the app to be considered for restart if startCmd
	// fails after having successfully started the app process.
	if err != nil {
		transitionInstance(instanceDir, device.InstanceStateLaunching, device.InstanceStateNotRunning)
		return err
	}
	if err := transitionInstance(instanceDir, device.InstanceStateLaunching, device.InstanceStateRunning); err != nil {
		return err
	}
	i.reap.startWatching(instanceDir, pid)
	return nil
}

func synchronizedShouldRestart(ctx *context.T, instanceDir string) bool {
	info, err := loadInstanceInfo(nil, instanceDir)
	if err != nil {
		ctx.Error(err)
		return false
	}

	envelope, err := loadEnvelopeForInstance(nil, instanceDir)
	if err != nil {
		ctx.Error(err)
		return false
	}

	shouldRestart := newBasicRestartPolicy().decide(envelope, info)

	if err := saveInstanceInfo(nil, instanceDir, info); err != nil {
		ctx.Error(err)
		return false
	}
	return shouldRestart
}

// restartAppIfNecessary restarts an application if its daemon
// configuration indicates that it should be running but the reaping
// functionality has previously determined that it is not.
// TODO(rjkroege): This routine has a low-likelyhood race condition in
// which it fails to restart an application when the app crashes and the
// device manager then crashes between the reaper marking the app not
// running and the go routine invoking this function having a chance to
// complete.
func (i *appRunner) restartAppIfNecessary(ctx *context.T, instanceDir string) {
	if err := transitionInstance(instanceDir, device.InstanceStateNotRunning, device.InstanceStateLaunching); err != nil {
		ctx.Error(err)
		return
	}
	shouldRestart := synchronizedShouldRestart(ctx, instanceDir)

	if err := transitionInstance(instanceDir, device.InstanceStateLaunching, device.InstanceStateNotRunning); err != nil {
		ctx.Error(err)
		return
	}

	if !shouldRestart {
		return
	}

	if instanceName, err := instanceNameFromDir(ctx, instanceDir); err != nil {
		ctx.Error(err)
		i.stats.incrRestarts("unknown")
	} else {
		i.stats.incrRestarts(instanceName)
	}

	if err := i.run(ctx, instanceDir); err != nil {
		ctx.Error(err)
	}
}

func (i *appService) Instantiate(ctx *context.T, call device.ApplicationInstantiateServerCall) (string, error) {
	helper := i.config.Helper
	instanceDir, instanceID, err := i.newInstance(ctx, call)
	if err != nil {
		CleanupDir(ctx, instanceDir, helper)
		return "", err
	}
	systemName := suidHelper.usernameForPrincipal(ctx, call.Security(), i.uat)
	if err := saveSystemNameForInstance(instanceDir, systemName); err != nil {
		CleanupDir(ctx, instanceDir, helper)
		return "", err
	}
	return instanceID, nil
}

// instanceDir returns the path to the directory containing the app instance
// referred to by the given suffix relative to the given root directory.
// TODO(gauthamt): Make sure we pass the context to instanceDir.
func instanceDir(root string, suffix []string) (string, error) {
	if nComponents := len(suffix); nComponents != 3 {
		return "", verror.New(errors.ErrInvalidSuffix, nil)
	}
	app, installation, instance := suffix[0], suffix[1], suffix[2]
	instancesDir := filepath.Join(root, applicationDirName(app), installationDirName(installation), "instances")
	instanceDir := filepath.Join(instancesDir, instanceDirName(instance))
	return instanceDir, nil
}

// parseInstanceDir is a partial inverse of instanceDir. It cannot retrieve the app name,
// as that has been hashed so it returns an appDir instead.
func parseInstanceDir(dir string) (prefix, appDir, installation, instance string) {
	dirRE := regexp.MustCompile("(/.*)(/" + appDirPrefix + "[^/]+)/" + installationPrefix + "([^/]+)/" + "instances/" + instancePrefix + "([^/]+)$")
	matches := dirRE.FindStringSubmatch(dir)
	if len(matches) < 5 {
		return "", "", "", ""
	}
	return matches[1], matches[2], matches[3], matches[4]
}

// instanceDir returns the path to the directory containing the app instance
// referred to by the invoker's suffix, as well as the corresponding not-running
// instance dir.  Returns an error if the suffix does not name an instance.
func (i *appService) instanceDir() (string, error) {
	return instanceDir(i.config.Root, i.suffix)
}

func (i *appService) Run(ctx *context.T, call rpc.ServerCall) error {
	instanceDir, err := i.instanceDir()
	if err != nil {
		return err
	}

	systemName := suidHelper.usernameForPrincipal(ctx, call.Security(), i.uat)
	startSystemName, err := readSystemNameForInstance(instanceDir)
	if err != nil {
		return err
	}

	if startSystemName != systemName {
		return verror.New(verror.ErrNoAccess, ctx, "Not allowed to resume an application under a different system name.")
	}

	i.stats.incrRuns(naming.Join(i.suffix...))

	// TODO(caprita): We should reset the Restarts and RestartWindowBegan
	// fields in the instance info when the instance is started with Run.

	return i.runner.run(ctx, instanceDir)
}

func stopAppRemotely(ctx *context.T, appVON string, deadline time.Duration) error {
	appStub := appcycle.AppCycleClient(appVON)
	ctx, cancel := context.WithTimeout(ctx, deadline)
	defer cancel()
	stream, err := appStub.Stop(ctx)
	if err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("%v.Stop() failed: %v", appVON, err))
	}
	rstream := stream.RecvStream()
	for rstream.Advance() {
		ctx.VI(2).Infof("%v.Stop() task update: %v", appVON, rstream.Value())
	}
	if err := rstream.Err(); err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Advance() failed: %v", err))
	}
	if err := stream.Finish(); err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Finish() failed: %v", err))
	}
	return nil
}

// stop attempts to stop the instance's process; returns true if successful, or
// false if the process is still running.
func (i *appService) stop(ctx *context.T, instanceDir string, info *instanceInfo, reap *reaper, deadline time.Duration) (bool, error) {
	pid := info.Pid
	// The reaper should stop tracking this instance, and, in particular,
	// not attempt to restart it.
	reap.stopWatching(instanceDir)
	processExited, stopGoroutine := make(chan struct{}), make(chan struct{})
	defer close(stopGoroutine)
	go func() {
		for {
			if !isAlive(ctx, pid) {
				close(processExited)
				return
			}
			select {
			case <-stopGoroutine:
				return
			default:
			}
			time.Sleep(time.Millisecond)
		}
	}()
	deadlineExpired := time.After(deadline)
	err := stopAppRemotely(ctx, info.AppCycleMgrName, deadline)
	select {
	case <-processExited:
		if err != nil {
			err = verror.New(errStoppedWithErrors, ctx, fmt.Sprintf("process exited uncleanly upon remote stop: %v", err))
		}
		return true, err
	case <-deadlineExpired:
	}
	reap.forciblySuspend(instanceDir)
	// Give it some grace period for the process to die after forceful
	// shutdown.
	gracePeriod := 5 * time.Second
	deadlineExpired = time.After(gracePeriod)
	select {
	case <-processExited:
		return true, verror.New(errStoppedWithErrors, ctx, fmt.Sprintf("process failed to exit cleanly upon remote stop (%v) and was forcefully terminated", err))
	case <-deadlineExpired:
		// The process just won't die.  We'll declare the stop operation
		// unsuccessful and switch the instance back to running
		// state. We let the reaper deal with it going forward
		// (including restarting it if restarts are enabled).
		reap.startWatching(instanceDir, pid)
		return false, verror.New(errStopFailed, ctx, fmt.Sprintf("process failed to exit within %v after force stop", gracePeriod))
	}
}

func (i *appService) Delete(ctx *context.T, _ rpc.ServerCall) error {
	instanceDir, err := i.instanceDir()
	if err != nil {
		return err
	}
	return transitionInstance(instanceDir, device.InstanceStateNotRunning, device.InstanceStateDeleted)
}

func (i *appService) Kill(ctx *context.T, _ rpc.ServerCall, deadline time.Duration) error {
	instanceDir, err := i.instanceDir()
	if err != nil {
		return err
	}
	if err := transitionInstance(instanceDir, device.InstanceStateRunning, device.InstanceStateDying); err != nil {
		return err
	}
	info, err := loadInstanceInfo(ctx, instanceDir)
	if err != nil {
		return err
	}
	if exited, err := i.stop(ctx, instanceDir, info, i.runner.reap, deadline); !exited {
		// If the process failed to terminate, it's going back in state
		// running (as if the Kill never happened).  The client may try
		// again.
		if err := transitionInstance(instanceDir, device.InstanceStateDying, device.InstanceStateRunning); err != nil {
			ctx.Errorf("transitionInstance(%v, %v, %v): %v", instanceDir, device.InstanceStateDying, device.InstanceStateRunning, err)
		}
		// Return the stop error.
		return err
	} else if err != nil {
		ctx.Errorf("stop %v ultimately succeeded, but had encountered an error: %v", instanceDir, err)
	}
	// The app exited, so we can stop serving the principal.
	if err := i.runner.principalMgr.StopServing(instanceDir); err != nil {
		ctx.Errorf("StopServing(%v) failed: %v", instanceDir, err)
	}
	return transitionInstance(instanceDir, device.InstanceStateDying, device.InstanceStateNotRunning)
}

func (i *appService) Uninstall(*context.T, rpc.ServerCall) error {
	installationDir, err := i.installationDir()
	if err != nil {
		return err
	}
	return transitionInstallation(installationDir, device.InstallationStateActive, device.InstallationStateUninstalled)
}

func updateInstance(ctx *context.T, instanceDir string) (err error) {
	// Only not-running instances can be updated.
	if err := transitionInstance(instanceDir, device.InstanceStateNotRunning, device.InstanceStateUpdating); err != nil {
		return err
	}
	defer func() {
		terr := transitionInstance(instanceDir, device.InstanceStateUpdating, device.InstanceStateNotRunning)
		if err == nil {
			err = terr
		}
	}()
	// Check if a newer version of the installation is available.
	versionLink := filepath.Join(instanceDir, "version")
	versionDir, err := filepath.EvalSymlinks(versionLink)
	if err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("EvalSymlinks(%v) failed: %v", versionLink, err))
	}
	latestVersionLink := filepath.Join(instanceDir, "installation", "current")
	latestVersionDir, err := filepath.EvalSymlinks(latestVersionLink)
	if err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("EvalSymlinks(%v) failed: %v", latestVersionLink, err))
	}
	if versionDir == latestVersionDir {
		return verror.New(errors.ErrUpdateNoOp, ctx)
	}
	// Update to the newer version.  Note, this is the only mutation
	// performed to the instance, and, since it's atomic, the state of the
	// instance is consistent at all times.
	return UpdateLink(latestVersionDir, versionLink)
}

func updateInstallation(ctx *context.T, installationDir string) error {
	if !installationStateIs(installationDir, device.InstallationStateActive) {
		return verror.New(errors.ErrInvalidOperation, ctx)
	}
	originVON, err := loadOrigin(ctx, installationDir)
	if err != nil {
		return err
	}
	ctx, cancel := context.WithTimeout(ctx, rpcContextLongTimeout)
	defer cancel()
	newEnvelope, err := fetchAppEnvelope(ctx, originVON)
	if err != nil {
		return err
	}
	currLink := filepath.Join(installationDir, "current")
	oldVersionDir, err := filepath.EvalSymlinks(currLink)
	if err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("EvalSymlinks(%v) failed: %v", currLink, err))
	}
	// NOTE(caprita): A race can occur between two competing updates, where
	// both use the old version as their baseline.  This can result in both
	// updates succeeding even if they are updating the app installation to
	// the same new envelope.  This will result in one of the updates
	// becoming the new 'current'.  Both versions will point their
	// 'previous' link to the old version.  This doesn't appear to be of
	// practical concern, so we avoid the complexity of synchronizing
	// updates.
	oldEnvelope, err := loadEnvelope(ctx, oldVersionDir)
	if err != nil {
		return err
	}
	if oldEnvelope.Title != newEnvelope.Title {
		return verror.New(errors.ErrAppTitleMismatch, ctx)
	}
	if reflect.DeepEqual(oldEnvelope, newEnvelope) {
		return verror.New(errors.ErrUpdateNoOp, ctx)
	}
	versionDir, err := newVersion(ctx, installationDir, newEnvelope, oldVersionDir)
	if err != nil {
		CleanupDir(ctx, versionDir, "")
		return err
	}
	return nil
}

func (i *appService) Update(ctx *context.T, _ rpc.ServerCall) error {
	if installationDir, err := i.installationDir(); err == nil {
		return updateInstallation(ctx, installationDir)
	}
	if instanceDir, err := i.instanceDir(); err == nil {
		return updateInstance(ctx, instanceDir)
	}
	return verror.New(errors.ErrInvalidSuffix, nil)
}

func (*appService) UpdateTo(_ *context.T, _ rpc.ServerCall, von string) error {
	// TODO(jsimsa): Implement.
	return nil
}

func revertInstance(ctx *context.T, instanceDir string) (err error) {
	// Only not-running instances can be reverted.
	if err := transitionInstance(instanceDir, device.InstanceStateNotRunning, device.InstanceStateUpdating); err != nil {
		return err
	}
	defer func() {
		terr := transitionInstance(instanceDir, device.InstanceStateUpdating, device.InstanceStateNotRunning)
		if err == nil {
			err = terr
		}
	}()
	versionLink := filepath.Join(instanceDir, "version")
	versionDir, err := filepath.EvalSymlinks(versionLink)
	if err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("EvalSymlinks(%v) failed: %v", versionLink, err))
	}
	previousLink := filepath.Join(versionDir, "previous")
	if _, err := os.Lstat(previousLink); err != nil {
		if os.IsNotExist(err) {
			// No 'previous' link -- must be the first version.
			return verror.New(errors.ErrUpdateNoOp, ctx)
		}
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Lstat(%v) failed: %v", previousLink, err))
	}
	prevVersionDir, err := filepath.EvalSymlinks(previousLink)
	if err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("EvalSymlinks(%v) failed: %v", previousLink, err))
	}
	return UpdateLink(prevVersionDir, versionLink)
}

func revertInstallation(ctx *context.T, installationDir string) error {
	if !installationStateIs(installationDir, device.InstallationStateActive) {
		return verror.New(errors.ErrInvalidOperation, ctx)
	}
	// NOTE(caprita): A race can occur between an update and a revert, where
	// both use the same current version as their starting point.  This will
	// render the update inconsequential.  This doesn't appear to be of
	// practical concern, so we avoid the complexity of synchronizing
	// updates and revert operations.
	currLink := filepath.Join(installationDir, "current")
	currVersionDir, err := filepath.EvalSymlinks(currLink)
	if err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("EvalSymlinks(%v) failed: %v", currLink, err))
	}
	previousLink := filepath.Join(currVersionDir, "previous")
	if _, err := os.Lstat(previousLink); err != nil {
		if os.IsNotExist(err) {
			// No 'previous' link -- must be the first version.
			return verror.New(errors.ErrUpdateNoOp, ctx)
		}
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("Lstat(%v) failed: %v", previousLink, err))
	}
	prevVersionDir, err := filepath.EvalSymlinks(previousLink)
	if err != nil {
		return verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("EvalSymlinks(%v) failed: %v", previousLink, err))
	}
	return UpdateLink(prevVersionDir, currLink)
}

func (i *appService) Revert(ctx *context.T, _ rpc.ServerCall) error {
	if installationDir, err := i.installationDir(); err == nil {
		return revertInstallation(ctx, installationDir)
	}
	if instanceDir, err := i.instanceDir(); err == nil {
		return revertInstance(ctx, instanceDir)
	}
	return verror.New(errors.ErrInvalidSuffix, nil)
}

type treeNode struct {
	children map[string]*treeNode
}

func newTreeNode() *treeNode {
	return &treeNode{children: make(map[string]*treeNode)}
}

func (n *treeNode) find(names []string, create bool) *treeNode {
	for {
		if len(names) == 0 {
			return n
		}
		if next, ok := n.children[names[0]]; ok {
			n = next
			names = names[1:]
			continue
		}
		if create {
			nn := newTreeNode()
			n.children[names[0]] = nn
			n = nn
			names = names[1:]
			continue
		}
		return nil
	}
}

func (i *appService) scanEnvelopes(ctx *context.T, tree *treeNode, appDir string) {
	// Find all envelopes, extract installID.
	envGlob := []string{i.config.Root, appDir, installationPrefix + "*", "*", "envelope"}
	envelopes, err := filepath.Glob(filepath.Join(envGlob...))
	if err != nil {
		ctx.Errorf("unexpected error: %v", err)
		return
	}
	for _, path := range envelopes {
		env, err := loadEnvelope(ctx, filepath.Dir(path))
		if err != nil {
			continue
		}
		relpath, _ := filepath.Rel(i.config.Root, path)
		elems := strings.Split(relpath, string(filepath.Separator))
		if len(elems) != len(envGlob)-1 {
			ctx.Errorf("unexpected number of path components: %q (%q)", elems, path)
			continue
		}
		installID := strings.TrimPrefix(elems[1], installationPrefix)
		tree.find([]string{env.Title, installID}, true)
	}
	return
}

func (i *appService) scanInstances(ctx *context.T, tree *treeNode) {
	if len(i.suffix) < 2 {
		return
	}
	title := i.suffix[0]
	installDir, err := installationDirCore(i.suffix[:2], i.config.Root)
	if err != nil {
		return
	}
	// Add the node corresponding to the installation itself.
	tree.find(i.suffix[:2], true)
	// Find all instances.
	infoGlob := []string{installDir, "instances", instancePrefix + "*", "info"}
	instances, err := filepath.Glob(filepath.Join(infoGlob...))
	if err != nil {
		ctx.Errorf("unexpected error: %v", err)
		return
	}
	for _, path := range instances {
		instanceDir := filepath.Dir(path)
		i.scanInstance(ctx, tree, title, instanceDir)
	}
	return
}

func (i *appService) scanInstance(ctx *context.T, tree *treeNode, title, instanceDir string) {
	if _, err := loadInstanceInfo(ctx, instanceDir); err != nil {
		return
	}
	rootDir, _, installID, instanceID := parseInstanceDir(instanceDir)
	if installID == "" || instanceID == "" || filepath.Clean(i.config.Root) != filepath.Clean(rootDir) {
		ctx.Errorf("failed to parse instanceDir %v (got: %v %v %v)", instanceDir, rootDir, installID, instanceID)
		return
	}

	tree.find([]string{title, installID, instanceID, "logs"}, true)
	if instanceStateIs(instanceDir, device.InstanceStateRunning) {
		for _, obj := range []string{"pprof", "stats"} {
			tree.find([]string{title, installID, instanceID, obj}, true)
		}
	}
}

func (i *appService) GlobChildren__(ctx *context.T, call rpc.GlobChildrenServerCall, m *glob.Element) error {
	tree := newTreeNode()
	switch len(i.suffix) {
	case 0:
		i.scanEnvelopes(ctx, tree, appDirPrefix+"*")
	case 1:
		appDir := applicationDirName(i.suffix[0])
		i.scanEnvelopes(ctx, tree, appDir)
	case 2:
		i.scanInstances(ctx, tree)
	case 3:
		dir, err := i.instanceDir()
		if err != nil {
			break
		}
		i.scanInstance(ctx, tree, i.suffix[0], dir)
	default:
		return verror.New(verror.ErrNoExist, nil, i.suffix)
	}
	n := tree.find(i.suffix, false)
	if n == nil {
		return verror.New(errors.ErrInvalidSuffix, nil)
	}
	for child, _ := range n.children {
		if m.Match(child) {
			call.SendStream().Send(naming.GlobChildrenReplyName{Value: child})
		}
	}
	return nil
}

// TODO(rjkroege): Refactor to eliminate redundancy with newAppSpecificAuthorizer.
func dirFromSuffix(ctx *context.T, suffix []string, root string) (string, bool, error) {
	if len(suffix) == 2 {
		p, err := installationDirCore(suffix, root)
		if err != nil {
			ctx.Errorf("dirFromSuffix failed: %v", err)
			return "", false, err
		}
		return p, false, nil
	} else if len(suffix) > 2 {
		p, err := instanceDir(root, suffix[0:3])
		if err != nil {
			ctx.Errorf("dirFromSuffix failed: %v", err)
			return "", false, err
		}
		return p, true, nil
	}
	return "", false, verror.New(errors.ErrInvalidSuffix, nil)
}

// TODO(rjkroege): Consider maintaining an in-memory Permissions cache.
func (i *appService) SetPermissions(ctx *context.T, call rpc.ServerCall, perms access.Permissions, version string) error {
	dir, isInstance, err := dirFromSuffix(ctx, i.suffix, i.config.Root)
	if err != nil {
		return err
	}
	if isInstance {
		dmBlessings := security.LocalBlessingNames(ctx, call.Security())
		if err := setPermsForDebugging(dmBlessings, perms, dir, i.permsStore); err != nil {
			return err
		}
	}
	return i.permsStore.Set(path.Join(dir, "acls"), perms, version)
}

func (i *appService) GetPermissions(ctx *context.T, _ rpc.ServerCall) (perms access.Permissions, version string, err error) {
	dir, _, err := dirFromSuffix(ctx, i.suffix, i.config.Root)
	if err != nil {
		return nil, "", err
	}
	return i.permsStore.Get(path.Join(dir, "acls"))
}

func (i *appService) Debug(ctx *context.T, call rpc.ServerCall) (string, error) {
	switch len(i.suffix) {
	case 2:
		return i.installationDebug(ctx)
	case 3:
		return i.instanceDebug(ctx, call.Security())
	default:
		return "", verror.New(errors.ErrInvalidSuffix, nil)
	}
}

func (i *appService) installationDebug(ctx *context.T) (string, error) {
	const installationDebug = `Installation dir: {{.InstallationDir}}

Origin: {{.Origin}}

Envelope: {{printf "%+v" .Envelope}}

Config: {{printf "%+v" .Config}}
`
	installationDebugTemplate, err := template.New("installation-debug").Parse(installationDebug)
	if err != nil {
		return "", err
	}

	installationDir, err := i.installationDir()
	if err != nil {
		return "", err
	}
	debugInfo := struct {
		InstallationDir, Origin string
		Envelope                *application.Envelope
		Config                  device.Config
	}{}
	debugInfo.InstallationDir = installationDir

	if origin, err := loadOrigin(ctx, installationDir); err != nil {
		return "", err
	} else {
		debugInfo.Origin = origin
	}

	currLink := filepath.Join(installationDir, "current")
	if envelope, err := loadEnvelope(ctx, currLink); err != nil {
		return "", err
	} else {
		debugInfo.Envelope = envelope
	}

	if config, err := loadConfig(ctx, installationDir); err != nil {
		return "", err
	} else {
		debugInfo.Config = config
	}

	var buf bytes.Buffer
	if err := installationDebugTemplate.Execute(&buf, debugInfo); err != nil {
		return "", err
	}
	return buf.String(), nil

}

func (i *appService) instanceDebug(ctx *context.T, call security.Call) (string, error) {
	const instanceDebug = `Instance dir: {{.InstanceDir}}

System name / start system name: {{.SystemName}} / {{.StartSystemName}}

Cmd: {{printf "%+v" .Cmd}}

Envelope: {{printf "%+v" .Envelope}}

Info: {{printf "%+v" .Info}}

Principal: {{.PrincipalDebug}}
Public Key: {{.Principal.PublicKey}}
Blessing Store: {{.Principal.BlessingStore.DebugString}}
Roots: {{.Principal.Roots.DebugString}}
`
	instanceDebugTemplate, err := template.New("instance-debug").Parse(instanceDebug)
	if err != nil {
		return "", err
	}

	instanceDir, err := i.instanceDir()
	if err != nil {
		return "", err
	}
	debugInfo := struct {
		InstanceDir, SystemName, StartSystemName string
		Cmd                                      *exec.Cmd
		Envelope                                 *application.Envelope
		Info                                     *instanceInfo
		Principal                                agent.Principal
		PrincipalDebug                           string
	}{}
	debugInfo.InstanceDir = instanceDir

	debugInfo.SystemName = suidHelper.usernameForPrincipal(ctx, call, i.uat)
	if startSystemName, err := readSystemNameForInstance(instanceDir); err != nil {
		return "", err
	} else {
		debugInfo.StartSystemName = startSystemName
	}

	if info, err := loadInstanceInfo(ctx, instanceDir); err != nil {
		return "", err
	} else {
		debugInfo.Info = info
	}
	if cmd, err := genCmd(ctx, instanceDir, i.runner.mtAddress); err != nil {
		return "", err
	} else {
		debugInfo.Cmd = cmd
	}

	if envelope, err := loadEnvelopeForInstance(ctx, instanceDir); err != nil {
		return "", err
	} else {
		debugInfo.Envelope = envelope
	}
	// TODO(caprita): Load requires that the principal be Serve-ing.
	if debugInfo.Principal, err = i.runner.principalMgr.Load(instanceDir); err != nil {
		return "", err
	}
	defer debugInfo.Principal.Close()
	debugInfo.PrincipalDebug = i.runner.principalMgr.Debug(instanceDir)
	var buf bytes.Buffer
	if err := instanceDebugTemplate.Execute(&buf, debugInfo); err != nil {
		return "", err
	}
	return buf.String(), nil
}

func (i *appService) Status(ctx *context.T, _ rpc.ServerCall) (device.Status, error) {
	switch len(i.suffix) {
	case 2:
		status, err := i.installationStatus(ctx)
		return device.StatusInstallation{Value: status}, err
	case 3:
		status, err := i.instanceStatus(ctx)
		return device.StatusInstance{Value: status}, err
	default:
		return nil, verror.New(errors.ErrInvalidSuffix, ctx)
	}
}

func (i *appService) installationStatus(ctx *context.T) (device.InstallationStatus, error) {
	installationDir, err := i.installationDir()
	if err != nil {
		return device.InstallationStatus{}, err
	}
	state, err := getInstallationState(installationDir)
	if err != nil {
		return device.InstallationStatus{}, err
	}
	versionLink := filepath.Join(installationDir, "current")
	versionDir, err := filepath.EvalSymlinks(versionLink)
	if err != nil {
		return device.InstallationStatus{}, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("EvalSymlinks(%v) failed: %v", versionLink, err))
	}
	return device.InstallationStatus{
		State:   state,
		Version: filepath.Base(versionDir),
	}, nil
}

func (i *appService) instanceStatus(ctx *context.T) (device.InstanceStatus, error) {
	instanceDir, err := i.instanceDir()
	if err != nil {
		return device.InstanceStatus{}, err
	}
	state, err := getInstanceState(instanceDir)
	if err != nil {
		return device.InstanceStatus{}, err
	}
	versionLink := filepath.Join(instanceDir, "version")
	versionDir, err := filepath.EvalSymlinks(versionLink)
	if err != nil {
		return device.InstanceStatus{}, verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("EvalSymlinks(%v) failed: %v", versionLink, err))
	}
	return device.InstanceStatus{
		State:   state,
		Version: filepath.Base(versionDir),
	}, nil
}

func createCallbackBlessings(ctx *context.T, app security.PublicKey) (string, error) {
	dm := v23.GetPrincipal(ctx) // device manager principal
	dmB, _ := dm.BlessingStore().Default()
	// NOTE(caprita/ataly): Giving the app an unconstrained blessing from
	// the device manager's default presents the app with a blessing that's
	// potentially more powerful than what is strictly needed to allow
	// communication between device manager and app (which could be more
	// narrowly accomplished by using a custom-purpose self-signed blessing
	// that the device manger produces solely to talk to the app).
	b, err := dm.Bless(app, dmB, "callback", security.UnconstrainedUse())
	if err != nil {
		return "", verror.New(errors.ErrOperationFailed, ctx, err)
	}
	bytes, err := vom.Encode(b)
	if err != nil {
		return "", verror.New(errors.ErrOperationFailed, ctx, fmt.Sprintf("failed to encode app cycle blessings: %v", err))
	}
	return base64.URLEncoding.EncodeToString(bytes), nil
}