// 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 acces to
//                                          Start, 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
//           acls(700d)/
//             data(700d)                 - the AccessLists for this instance. These
//                                          AccessLists control access to Refresh,
//                                          Restart, Resume, Stop and
//                                          Suspend.
//             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 ACLs for Debug access to the application. Shared
//                                          with the application.
//             signature(644)/            - the signature for these ACLs.
//         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 resumes the
// ones that are not suspended.  If the application was still running, it
// suspends it first.  If an application fails to resume, it stays suspended.
//
// When device manager shuts down, it suspends all running instances.
//
// Start starts an instance.  Suspend kills the process but leaves the workspace
// untouched. Resume restarts the process. Stop kills the process and prevents
// future resumes (it also eventually gc's the workspace).
//
// If the process dies on its own, it stays dead and is assumed suspended.
// 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 (any running instances will be
// stopped). 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 an instance Start, the Start 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 Start, it is placed in state 'suspended'.
// To run the instance, Start transitions 'suspended' to 'starting' and then
// 'started' (upon success) or the instance is deleted (upon failure).
//
// - Suspend attempts to transition from 'started' to 'suspending' (if the
// instance was not in 'started' state, Suspend fails). From 'suspending', the
// instance transitions to 'suspended' upon success or back to 'started' upon
// failure.
//
// - Resume attempts to transition from 'suspended' to 'starting' (if the
// instance was not in 'suspended' state, Resume fails). From 'starting', the
// instance transitions to 'started' upon success or back to 'suspended' upon
// failure.
//
// - Stop attempts to transition from 'started' to 'stopping' and then to
// 'stopped' (upon success) or back to 'started' (upon failure); or from
// 'suspended' to 'stopped'.  If the initial state is neither 'started' or
// 'suspended', Stop 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"
	"crypto/rand"
	"encoding/base64"
	"encoding/hex"
	"encoding/json"
	"fmt"
	"io/ioutil"
	"os"
	"os/exec"
	"path"
	"path/filepath"
	"reflect"
	"strconv"
	"strings"
	"text/template"
	"time"

	"v.io/v23"
	"v.io/v23/context"
	"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/x/lib/vlog"

	"v.io/x/ref/envvar"
	vexec "v.io/x/ref/lib/exec"
	"v.io/x/ref/lib/mgmt"
	vsecurity "v.io/x/ref/security"
	"v.io/x/ref/security/agent"
	"v.io/x/ref/security/agent/keymgr"
	iconfig "v.io/x/ref/services/mgmt/device/config"
	"v.io/x/ref/services/mgmt/lib/acls"
	libpackages "v.io/x/ref/services/mgmt/lib/packages"
)

// instanceInfo holds state about a running instance.
type instanceInfo struct {
	AppCycleMgrName          string
	Pid                      int
	DeviceManagerPeerPattern string
	SecurityAgentHandle      []byte
}

func saveInstanceInfo(ctx *context.T, dir string, info *instanceInfo) error {
	jsonInfo, err := json.Marshal(info)
	if err != nil {
		return verror.New(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(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(ErrOperationFailed, ctx, fmt.Sprintf("ReadFile(%v) failed: %v", infoPath, err))
	} else if err := json.Unmarshal(infoBytes, info); err != nil {
		return nil, verror.New(ErrOperationFailed, ctx, fmt.Sprintf("Unmarshal(%v) failed: %v", infoBytes, err))
	}
	return info, nil
}

type securityAgentState struct {
	// Security agent key manager client.
	keyMgrAgent *keymgr.Agent
}

// appService implements the Device manager's Application interface.
type appService struct {
	callback *callbackState
	config   *iconfig.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
	aclstore *acls.PathStore
	// Reference to the devicemanager top-level AccessList list.
	deviceAccessList access.Permissions
	// securityAgent holds state related to the security agent (nil if not
	// using the agent).
	securityAgent *securityAgentState
	// mtAddress is the address of the local mounttable.
	mtAddress string
	// reap is the app process monitoring subsystem.
	reap reaper
}

func saveEnvelope(ctx *context.T, dir string, envelope *application.Envelope) error {
	jsonEnvelope, err := json.Marshal(envelope)
	if err != nil {
		return verror.New(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(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(ErrOperationFailed, ctx, fmt.Sprintf("ReadFile(%v) failed: %v", path, err))
	} else if err := json.Unmarshal(envelopeBytes, envelope); err != nil {
		return nil, verror.New(ErrOperationFailed, ctx, fmt.Sprintf("Unmarshal(%v) failed: %v", envelopeBytes, err))
	}
	return envelope, nil
}

func saveConfig(ctx *context.T, dir string, config device.Config) error {
	jsonConfig, err := json.Marshal(config)
	if err != nil {
		return verror.New(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(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(ErrOperationFailed, ctx, fmt.Sprintf("ReadFile(%v) failed: %v", path, err))
	} else if err := json.Unmarshal(configBytes, &config); err != nil {
		return nil, verror.New(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(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(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(ErrOperationFailed, ctx, fmt.Sprintf("ReadFile(%v) failed: %v", path, err))
	} else if err := json.Unmarshal(packagesBytes, &packages); err != nil {
		return nil, verror.New(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(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(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)
}

// generateRandomString returns a cryptographically-strong random string.
func generateRandomString() (string, error) {
	b := make([]byte, 16)
	_, err := rand.Read(b)
	if err != nil {
		return "", err
	}
	return hex.EncodeToString(b), nil
}

// 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?

// 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 "app-" + hash
}

func installationDirName(installationID string) string {
	return "installation-" + installationID
}

func instanceDirName(instanceID string) string {
	return "instance-" + instanceID
}

func mkdir(dir string) error {
	return mkdirPerm(dir, 0700)
}

func mkdirPerm(dir string, permissions int) error {
	perm := os.FileMode(permissions)
	if err := os.MkdirAll(dir, perm); err != nil {
		vlog.Errorf("MkdirAll(%v, %v) failed: %v", dir, perm, err)
		return err
	}
	return 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(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(versionDir, 0711); err != nil {
		return "", verror.New(ErrOperationFailed, ctx, err)
	}
	if err := saveEnvelope(ctx, versionDir, envelope); err != nil {
		return versionDir, err
	}
	pkgDir := filepath.Join(versionDir, "pkg")
	if err := mkdir(pkgDir); err != nil {
		return "", verror.New(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(ErrOperationFailed, ctx, fmt.Sprintf("installPackages(%v, %v) failed: %v", installationDir, versionDir, err))
	}
	if err := os.RemoveAll(pkgDir); err != nil {
		return versionDir, verror.New(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(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(call rpc.ServerCall, applicationVON string, config device.Config, packages application.Packages) (string, error) {
	if len(i.suffix) > 0 {
		return "", verror.New(ErrInvalidSuffix, call.Context())
	}
	ctx, cancel := context.WithTimeout(call.Context(), 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(installationDir, "")
	}
	if err := mkdirPerm(installationDir, 0711); err != nil {
		return "", verror.New(ErrOperationFailed, nil)
	}
	defer func() {
		if deferrer != nil {
			deferrer()
		}
	}()
	if newOrigin, ok := config[mgmt.AppOriginConfigKey]; ok {
		delete(config, mgmt.AppOriginConfigKey)
		applicationVON = newOrigin
	}
	if err := saveOrigin(call.Context(), installationDir, applicationVON); err != nil {
		return "", err
	}
	if err := saveConfig(call.Context(), installationDir, config); err != nil {
		return "", err
	}
	if err := savePackages(call.Context(), installationDir, packages); err != nil {
		return "", err
	}
	pkgDir := filepath.Join(installationDir, "pkg")
	if err := mkdir(pkgDir); err != nil {
		return "", verror.New(ErrOperationFailed, call.Context(), 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(call.Context(), security.Blessings{}, packages, pkgDir); err != nil {
		return "", err
	}
	if _, err := newVersion(call.Context(), 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(call.Context())
	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 (*appService) Refresh(rpc.ServerCall) error {
	// TODO(jsimsa): Implement.
	return nil
}

func (*appService) Restart(rpc.ServerCall) error {
	// TODO(jsimsa): Implement.
	return 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(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(ErrOperationFailed, nil, fmt.Sprintf("Stat(%v) failed: %v", installationDir, err))
	}
	return installationDir, nil
}

// agentPrincipal creates a Principal backed by the given agent connection,
// taking ownership of the connection.  The returned cancel function is to be
// called when the Principal is no longer in use.
func agentPrincipal(ctx *context.T, conn *os.File) (security.Principal, func(), error) {
	agentctx, cancel := context.WithCancel(ctx)
	var err error
	if agentctx, err = v23.SetNewStreamManager(agentctx); err != nil {
		cancel()
		conn.Close()
		return nil, nil, err
	}
	p, err := agent.NewAgentPrincipal(agentctx, int(conn.Fd()), v23.GetClient(agentctx))
	if err != nil {
		cancel()
		conn.Close()
		return nil, nil, err
	}
	// conn will be closed when the connection to the agent is shut down, as
	// a result of cancel shutting down the stream manager.  No need to
	// explicitly call conn.Close() with cancel.
	return p, cancel, nil
}

// setupPrincipal sets up the instance's principal, with the right blessings.
func setupPrincipal(ctx *context.T, instanceDir string, call device.ApplicationStartServerCall, securityAgent *securityAgentState, info *instanceInfo) error {
	var p security.Principal
	if securityAgent != nil {
		// TODO(caprita): Part of the cleanup upon destroying an
		// instance, we should tell the agent to drop the principal.
		handle, conn, err := securityAgent.keyMgrAgent.NewPrincipal(ctx, false)
		if err != nil {
			return verror.New(ErrOperationFailed, ctx, fmt.Sprintf("NewPrincipal() failed %v", err))
		}
		var cancel func()
		if p, cancel, err = agentPrincipal(ctx, conn); err != nil {
			return verror.New(ErrOperationFailed, ctx, fmt.Sprintf("agentPrincipal failed: %v", err))
		}
		defer cancel()
		info.SecurityAgentHandle = handle
		// conn will be closed when the connection to the agent is shut
		// down, as a result of cancel() shutting down the stream
		// manager.  No need to call conn.Close().
	} else {
		credentialsDir := filepath.Join(instanceDir, "credentials")
		// TODO(caprita): The app's system user id needs access to this dir.
		// Use the suidhelper to chown it.
		var err error
		if p, err = vsecurity.CreatePersistentPrincipal(credentialsDir, nil); err != nil {
			return verror.New(ErrOperationFailed, ctx, fmt.Sprintf("CreatePersistentPrincipal(%v, nil) failed: %v", credentialsDir, err))
		}
	}
	mPubKey, err := p.PublicKey().MarshalBinary()
	if err != nil {
		return verror.New(ErrOperationFailed, ctx, fmt.Sprintf("PublicKey().MarshalBinary() failed: %v", err))
	}
	if err := call.SendStream().Send(device.StartServerMessageInstancePublicKey{mPubKey}); err != nil {
		return err
	}
	if !call.RecvStream().Advance() {
		return verror.New(ErrInvalidBlessing, ctx, fmt.Sprintf("no blessings on stream: %v", call.RecvStream().Err()))
	}
	msg := call.RecvStream().Value()
	appBlessings, ok := msg.(device.StartClientMessageAppBlessings)
	if !ok {
		return verror.New(ErrInvalidBlessing, ctx, fmt.Sprintf("wrong message type: %#v", msg))
	}
	if appBlessings.Value.IsZero() {
		return verror.New(ErrInvalidBlessing, ctx)
	}
	if err := p.BlessingStore().SetDefault(appBlessings.Value); err != nil {
		return verror.New(ErrOperationFailed, ctx, fmt.Sprintf("BlessingStore.SetDefault() failed: %v", err))
	}
	if _, err := p.BlessingStore().Set(appBlessings.Value, security.AllPrincipals); err != nil {
		return verror.New(ErrOperationFailed, ctx, fmt.Sprintf("BlessingStore.Set() failed: %v", err))
	}
	if err := p.AddToRoots(appBlessings.Value); err != nil {
		return verror.New(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.
	//
	// 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).
	//
	// TODO(caprita): Figure out if there is any feature value in providing
	// the app with a device manager-derived blessing (e.g., may the app
	// need to prove it's running on the device?).
	dmPrincipal := v23.GetPrincipal(call.Context())
	dmBlessings, err := dmPrincipal.Bless(p.PublicKey(), dmPrincipal.BlessingStore().Default(), "callback", security.UnconstrainedUse())
	// Put the names of the device manager's default blessings as patterns
	// for the child, so that the child uses the right blessing when talking
	// back to the device manager.
	for n, _ := range dmPrincipal.BlessingsInfo(dmPrincipal.BlessingStore().Default()) {
		if _, err := p.BlessingStore().Set(dmBlessings, security.BlessingPattern(n)); err != nil {
			return verror.New(ErrOperationFailed, ctx, fmt.Sprintf("BlessingStore.Set() failed: %v", err))
		}
	}
	// We also want to override the app cycle manager's server blessing in
	// the child (so that the device manager can send RPCs to it).  We
	// signal to the child's app manager to use a randomly generated pattern
	// to extract the right blessing to use from its store for this purpose.
	randomPattern, err := generateRandomString()
	if err != nil {
		return verror.New(ErrOperationFailed, ctx, fmt.Sprintf("generateRandomString() failed: %v", err))
	}
	if _, err := p.BlessingStore().Set(dmBlessings, security.BlessingPattern(randomPattern)); err != nil {
		return verror.New(ErrOperationFailed, ctx, fmt.Sprintf("BlessingStore.Set() failed: %v", err))
	}
	info.DeviceManagerPeerPattern = randomPattern
	if err := p.AddToRoots(dmBlessings); err != nil {
		return verror.New(ErrOperationFailed, ctx, fmt.Sprintf("AddToRoots() failed: %v", err))
	}
	return 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(packages application.Packages, sourceDir string) error {
		for pkg, _ := range packages {
			pkgFile := filepath.Join(sourceDir, "pkg", pkg)
			dst := filepath.Join(packagesDir, pkg)
			if err := libpackages.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 acl for instance-specific ACLs
func (i *appService) initializeSubAccessLists(instanceDir string, blessings []string, acl access.Permissions) error {
	for _, b := range blessings {
		for _, tag := range access.AllTypicalTags() {
			acl.Add(security.BlessingPattern(b), string(tag))
		}
	}
	aclDir := path.Join(instanceDir, "acls")
	return i.aclstore.Set(aclDir, acl, "")
}

func (i *appService) newInstance(call device.ApplicationStartServerCall) (string, string, error) {
	installationDir, err := i.installationDir()
	if err != nil {
		return "", "", err
	}
	if !installationStateIs(installationDir, device.InstallationStateActive) {
		return "", "", verror.New(ErrInvalidOperation, call.Context())
	}
	instanceID := generateID()
	instanceDir := filepath.Join(installationDir, "instances", instanceDirName(instanceID))
	// Set permissions for app to have access.
	if mkdirPerm(instanceDir, 0711) != nil {
		return "", "", verror.New(ErrOperationFailed, call.Context())
	}
	rootDir := filepath.Join(instanceDir, "root")
	if err := mkdir(rootDir); err != nil {
		return instanceDir, instanceID, verror.New(ErrOperationFailed, call.Context(), err)
	}
	installationLink := filepath.Join(instanceDir, "installation")
	if err := os.Symlink(installationDir, installationLink); err != nil {
		return instanceDir, instanceID, verror.New(ErrOperationFailed, call.Context(), 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(ErrOperationFailed, call.Context(), 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(ErrOperationFailed, call.Context(), 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(ErrOperationFailed, call.Context(), fmt.Sprintf("Symlink(%v, %v) failed: %v", packagesDir, packagesLink, err))
	}
	instanceInfo := new(instanceInfo)
	if err := setupPrincipal(call.Context(), instanceDir, call, i.securityAgent, instanceInfo); err != nil {
		return instanceDir, instanceID, err
	}
	if err := saveInstanceInfo(call.Context(), instanceDir, instanceInfo); err != nil {
		return instanceDir, instanceID, err
	}
	blessings, _ := security.RemoteBlessingNames(call.Context())
	aclCopy := i.deviceAccessList.Copy()
	if err := i.initializeSubAccessLists(instanceDir, blessings, aclCopy); err != nil {
		return instanceDir, instanceID, err
	}
	if err := initializeInstance(instanceDir, device.InstanceStateSuspended); 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(call.Context())
	if err := setACLsForDebugging(dmBlessings, aclCopy, instanceDir, i.aclstore); err != nil {
		return instanceDir, instanceID, err
	}
	return instanceDir, instanceID, nil
}

func genCmd(ctx *context.T, instanceDir, helperPath, systemName string, nsRoot string) (*exec.Cmd, error) {
	versionLink := filepath.Join(instanceDir, "version")
	versionDir, err := filepath.EvalSymlinks(versionLink)
	if err != nil {
		return nil, verror.New(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(ErrOperationFailed, ctx, fmt.Sprintf("Stat(%v) failed: %v", binPath, err))
	}

	cmd := exec.Command(helperPath)

	switch yes, err := suidHelper.suidhelperEnabled(systemName, helperPath); {
	case err != nil:
		return nil, err
	case yes:
		cmd.Args = append(cmd.Args, "--username", systemName)
	case !yes:
		cmd.Args = append(cmd.Args, "--username", systemName, "--dryrun")
	}

	// 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)

	cmd.Args = append(cmd.Args, "--progname", appName)

	// Set the app's default namespace root to the local namespace.
	cmd.Env = envvar.DoNotUse_AppendNamespaceRoot(nsRoot, cmd.Env)
	cmd.Env = append(cmd.Env, envelope.Env...)
	rootDir := filepath.Join(instanceDir, "root")
	cmd.Dir = rootDir
	cmd.Args = append(cmd.Args, "--workspace", rootDir)

	logDir := filepath.Join(instanceDir, "logs")
	if err := mkdirPerm(logDir, 0755); err != nil {
		return nil, err
	}
	cmd.Args = append(cmd.Args, "--logdir", logDir)
	timestamp := time.Now().UnixNano()

	stdoutLog := filepath.Join(logDir, fmt.Sprintf("STDOUT-%d", timestamp))
	if cmd.Stdout, err = openWriteFile(stdoutLog); err != nil {
		return nil, verror.New(ErrOperationFailed, ctx, fmt.Sprintf("OpenFile(%v) failed: %v", stdoutLog, err))
	}
	stderrLog := filepath.Join(logDir, fmt.Sprintf("STDERR-%d", timestamp))
	if cmd.Stderr, err = openWriteFile(stderrLog); err != nil {
		return nil, verror.New(ErrOperationFailed, ctx, fmt.Sprintf("OpenFile(%v) failed: %v", stderrLog, err))
	}
	cmd.Args = append(cmd.Args, "--run", binPath)
	cmd.Args = append(cmd.Args, "--")

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

	cmd.Args = append(cmd.Args, appArgs...)
	return cmd, nil
}

func (i *appService) 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(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(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)
	}
	cfg.Set(mgmt.ParentNameConfigKey, listener.name())
	cfg.Set(mgmt.ProtocolConfigKey, "tcp")
	cfg.Set(mgmt.AddressConfigKey, "127.0.0.1:0")
	cfg.Set(mgmt.ParentBlessingConfigKey, info.DeviceManagerPeerPattern)

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

	// Set up any agent-specific state.
	// NOTE(caprita): This ought to belong in genCmd.
	var agentCleaner func()
	if sa := i.securityAgent; sa != nil {
		file, err := sa.keyMgrAgent.NewConnection(info.SecurityAgentHandle)
		if err != nil {
			vlog.Errorf("NewConnection(%v) failed: %v", info.SecurityAgentHandle, err)
			return 0, err
		}
		agentCleaner = func() {
			file.Close()
		}
		// We need to account for the file descriptors corresponding to
		// std{err|out|in} as well as the implementation-specific pipes
		// that the vexec library adds to ExtraFiles during
		// handle.Start.  vexec.FileOffset properly offsets fd
		// accordingly.
		fd := len(cmd.ExtraFiles) + vexec.FileOffset
		cmd.ExtraFiles = append(cmd.ExtraFiles, file)
		cfg.Set(mgmt.SecurityAgentFDConfigKey, strconv.Itoa(fd))
	} else {
		cmd.Env = envvar.DoNotUse_AppendCredentials(filepath.Join(instanceDir, "credentials"), cmd.Env)
	}
	handle := vexec.NewParentHandle(cmd, vexec.ConfigOpt{cfg})
	defer func() {
		if handle != nil {
			if err := handle.Clean(); err != nil {
				vlog.Errorf("Clean() failed: %v", err)
			}
		}
	}()
	// Start the child process.
	if err := handle.Start(); err != nil {
		if agentCleaner != nil {
			agentCleaner()
		}
		return 0, verror.New(ErrOperationFailed, ctx, fmt.Sprintf("Start() failed: %v", err))
	}
	if agentCleaner != nil {
		agentCleaner()
	}

	// Wait for the suidhelper to exit.
	if err := handle.Wait(0); err != nil {
		return 0, verror.New(ErrOperationFailed, ctx, fmt.Sprintf("Wait() on suidhelper failed: %v", err))
	}

	// Wait for the process invoked by suidhelper to become ready.
	if err := handle.WaitForReady(childReadyTimeout); err != nil {
		return 0, verror.New(ErrOperationFailed, ctx, fmt.Sprintf("WaitForReady(%v) failed: %v", childReadyTimeout, err))
	}
	pid := handle.ChildPid()
	childName, err := listener.waitForValue(childReadyTimeout)
	if err != nil {
		return 0, verror.New(ErrOperationFailed, nil)
	}

	// Because suidhelper uses Go's in-built support for setuid forking,
	// handle.Pid() is the pid of suidhelper, not the pid of the app
	// so use the pid returned in the app's ready status.
	info.AppCycleMgrName, info.Pid = childName, pid
	if err := saveInstanceInfo(ctx, instanceDir, info); err != nil {
		return 0, err
	}
	handle = nil
	return pid, nil
}

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

	cmd, err := genCmd(ctx, instanceDir, i.config.Helper, systemName, i.mtAddress)
	if err == nil {
		pid, err = i.startCmd(ctx, instanceDir, cmd)
	}
	if err != nil {
		transitionInstance(instanceDir, device.InstanceStateStarting, device.InstanceStateSuspended)
		return err
	}
	if err := transitionInstance(instanceDir, device.InstanceStateStarting, device.InstanceStateStarted); err != nil {
		return err
	}
	i.reap.startWatching(instanceDir, pid)
	return nil
}

func (i *appService) Start(call device.ApplicationStartServerCall) error {
	helper := i.config.Helper
	instanceDir, instanceID, err := i.newInstance(call)
	if err != nil {
		cleanupDir(instanceDir, helper)
		return err
	}

	systemName := suidHelper.usernameForPrincipal(call, i.uat)
	if err := saveSystemNameForInstance(instanceDir, systemName); err != nil {
		cleanupDir(instanceDir, helper)
		return err
	}
	if err := call.SendStream().Send(device.StartServerMessageInstanceName{instanceID}); err != nil {
		return verror.New(ErrOperationFailed, call.Context(), err)
	}
	if err = i.run(call.Context(), instanceDir, systemName); err != nil {
		// TODO(caprita): We should call cleanupDir here, but we don't
		// in order to not lose the logs for the instance (so we can
		// debug why run failed).  Clean this up.
		// cleanupDir(instanceDir, helper)
		return err
	}
	return 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(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
}

// instanceDir returns the path to the directory containing the app instance
// referred to by the invoker's suffix, as well as the corresponding stopped
// 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) Resume(call rpc.ServerCall) error {
	instanceDir, err := i.instanceDir()
	if err != nil {
		return err
	}

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

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

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

func stop(ctx *context.T, instanceDir string, reap reaper) error {
	info, err := loadInstanceInfo(ctx, instanceDir)
	if err != nil {
		return err
	}
	err = stopAppRemotely(ctx, info.AppCycleMgrName)
	if err == nil {
		reap.stopWatching(instanceDir)
	}
	return err
}

// TODO(caprita): implement deadline for Stop.

func (i *appService) Stop(call rpc.ServerCall, deadline uint32) error {
	instanceDir, err := i.instanceDir()
	if err != nil {
		return err
	}
	if err := transitionInstance(instanceDir, device.InstanceStateSuspended, device.InstanceStateStopped); verror.ErrorID(err) == ErrOperationFailed.ID || err == nil {
		return err
	}
	if err := transitionInstance(instanceDir, device.InstanceStateStarted, device.InstanceStateStopping); err != nil {
		return err
	}
	if err := stop(call.Context(), instanceDir, i.reap); err != nil {
		transitionInstance(instanceDir, device.InstanceStateStopping, device.InstanceStateStarted)
		return err
	}
	return transitionInstance(instanceDir, device.InstanceStateStopping, device.InstanceStateStopped)
}

func (i *appService) Suspend(call rpc.ServerCall) error {
	instanceDir, err := i.instanceDir()
	if err != nil {
		return err
	}
	if err := transitionInstance(instanceDir, device.InstanceStateStarted, device.InstanceStateSuspending); err != nil {
		return err
	}
	if err := stop(call.Context(), instanceDir, i.reap); err != nil {
		transitionInstance(instanceDir, device.InstanceStateSuspending, device.InstanceStateStarted)
		return err
	}
	return transitionInstance(instanceDir, device.InstanceStateSuspending, device.InstanceStateSuspended)
}

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

func updateInstance(instanceDir string, ctx *context.T) (err error) {
	// Only suspended instances can be updated.
	//
	// TODO(caprita): Consider enabling updates for started instances as
	// well, and handle the suspend/resume automatically.
	if err := transitionInstance(instanceDir, device.InstanceStateSuspended, device.InstanceStateUpdating); err != nil {
		return err
	}
	defer func() {
		terr := transitionInstance(instanceDir, device.InstanceStateUpdating, device.InstanceStateSuspended)
		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(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(ErrOperationFailed, ctx, fmt.Sprintf("EvalSymlinks(%v) failed: %v", latestVersionLink, err))
	}
	if versionDir == latestVersionDir {
		return verror.New(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(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(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(ErrAppTitleMismatch, ctx)
	}
	if reflect.DeepEqual(oldEnvelope, newEnvelope) {
		return verror.New(ErrUpdateNoOp, ctx)
	}
	versionDir, err := newVersion(ctx, installationDir, newEnvelope, oldVersionDir)
	if err != nil {
		cleanupDir(versionDir, "")
		return err
	}
	return nil
}

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

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

func (i *appService) Revert(call rpc.ServerCall) error {
	installationDir, err := i.installationDir()
	if err != nil {
		return err
	}
	if !installationStateIs(installationDir, device.InstallationStateActive) {
		return verror.New(ErrInvalidOperation, call.Context())
	}
	// 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(ErrOperationFailed, call.Context(), 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(ErrUpdateNoOp, call.Context())
		}
		return verror.New(ErrOperationFailed, call.Context(), fmt.Sprintf("Lstat(%v) failed: %v", previousLink, err))
	}
	prevVersionDir, err := filepath.EvalSymlinks(previousLink)
	if err != nil {
		return verror.New(ErrOperationFailed, call.Context(), fmt.Sprintf("EvalSymlinks(%v) failed: %v", previousLink, err))
	}
	return updateLink(prevVersionDir, currLink)
}

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, "installation-*", "*", "envelope"}
	envelopes, err := filepath.Glob(filepath.Join(envGlob...))
	if err != nil {
		vlog.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 {
			vlog.Errorf("unexpected number of path components: %q (%q)", elems, path)
			continue
		}
		installID := strings.TrimPrefix(elems[1], "installation-")
		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", "instance-*", "info"}
	instances, err := filepath.Glob(filepath.Join(infoGlob...))
	if err != nil {
		vlog.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
	}
	relpath, _ := filepath.Rel(i.config.Root, instanceDir)
	elems := strings.Split(relpath, string(filepath.Separator))
	if len(elems) < 4 {
		vlog.Errorf("unexpected number of path components: %q (%q)", elems, instanceDir)
		return
	}
	installID := strings.TrimPrefix(elems[1], "installation-")
	instanceID := strings.TrimPrefix(elems[3], "instance-")
	tree.find([]string{title, installID, instanceID, "logs"}, true)
	if instanceStateIs(instanceDir, device.InstanceStateStarted) {
		for _, obj := range []string{"pprof", "stats"} {
			tree.find([]string{title, installID, instanceID, obj}, true)
		}
	}
}

func (i *appService) GlobChildren__(call rpc.ServerCall) (<-chan string, error) {
	tree := newTreeNode()
	switch len(i.suffix) {
	case 0:
		i.scanEnvelopes(call.Context(), tree, "app-*")
	case 1:
		appDir := applicationDirName(i.suffix[0])
		i.scanEnvelopes(call.Context(), tree, appDir)
	case 2:
		i.scanInstances(call.Context(), tree)
	case 3:
		dir, err := i.instanceDir()
		if err != nil {
			break
		}
		i.scanInstance(call.Context(), tree, i.suffix[0], dir)
	default:
		return nil, verror.New(verror.ErrNoExist, nil, i.suffix)
	}
	n := tree.find(i.suffix, false)
	if n == nil {
		return nil, verror.New(ErrInvalidSuffix, nil)
	}
	ch := make(chan string)
	go func() {
		for child, _ := range n.children {
			ch <- child
		}
		close(ch)
	}()
	return ch, nil
}

// TODO(rjkroege): Refactor to eliminate redundancy with newAppSpecificAuthorizer.
func dirFromSuffix(suffix []string, root string) (string, bool, error) {
	if len(suffix) == 2 {
		p, err := installationDirCore(suffix, root)
		if err != nil {
			vlog.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 {
			vlog.Errorf("dirFromSuffix failed: %v", err)
			return "", false, err
		}
		return p, true, nil
	}
	return "", false, verror.New(ErrInvalidSuffix, nil)
}

// TODO(rjkroege): Consider maintaining an in-memory Permissions cache.
func (i *appService) SetPermissions(call rpc.ServerCall, acl access.Permissions, etag string) error {
	dir, isInstance, err := dirFromSuffix(i.suffix, i.config.Root)
	if err != nil {
		return err
	}
	if isInstance {
		dmBlessings := security.LocalBlessingNames(call.Context())
		if err := setACLsForDebugging(dmBlessings, acl, dir, i.aclstore); err != nil {
			return err
		}
	}
	return i.aclstore.Set(path.Join(dir, "acls"), acl, etag)
}

func (i *appService) GetPermissions(call rpc.ServerCall) (acl access.Permissions, etag string, err error) {
	dir, _, err := dirFromSuffix(i.suffix, i.config.Root)
	if err != nil {
		return nil, "", err
	}
	return i.aclstore.Get(path.Join(dir, "acls"))
}

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

func (i *appService) installationDebug(call rpc.ServerCall) (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(call.Context(), installationDir); err != nil {
		return "", err
	} else {
		debugInfo.Origin = origin
	}

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

	if config, err := loadConfig(call.Context(), 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(call rpc.ServerCall) (string, error) {
	const instanceDebug = `Instance dir: {{.InstanceDir}}

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

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

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

Principal: {{.PrincipalType}}
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
		Info                                     *instanceInfo
		Principal                                security.Principal
		PrincipalType                            string
	}{}
	debugInfo.InstanceDir = instanceDir

	debugInfo.SystemName = suidHelper.usernameForPrincipal(call, i.uat)
	if startSystemName, err := readSystemNameForInstance(instanceDir); err != nil {
		return "", err
	} else {
		debugInfo.StartSystemName = startSystemName
	}
	if cmd, err := genCmd(call.Context(), instanceDir, i.config.Helper, debugInfo.SystemName, i.mtAddress); err != nil {
		return "", err
	} else {
		debugInfo.Cmd = cmd
	}
	if info, err := loadInstanceInfo(call.Context(), instanceDir); err != nil {
		return "", err
	} else {
		debugInfo.Info = info
	}

	if sa := i.securityAgent; sa != nil {
		file, err := sa.keyMgrAgent.NewConnection(debugInfo.Info.SecurityAgentHandle)
		if err != nil {
			vlog.Errorf("NewConnection(%v) failed: %v", debugInfo.Info.SecurityAgentHandle, err)
			return "", err
		}
		var cancel func()
		if debugInfo.Principal, cancel, err = agentPrincipal(call.Context(), file); err != nil {
			return "", err
		}
		defer cancel()
		debugInfo.PrincipalType = "Agent-based"
	} else {
		credentialsDir := filepath.Join(instanceDir, "credentials")
		var err error
		if debugInfo.Principal, err = vsecurity.LoadPersistentPrincipal(credentialsDir, nil); err != nil {
			return "", err
		}
		debugInfo.PrincipalType = fmt.Sprintf("Credentials dir-based (%v)", credentialsDir)
	}
	var buf bytes.Buffer
	if err := instanceDebugTemplate.Execute(&buf, debugInfo); err != nil {
		return "", err
	}
	return buf.String(), nil
}

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

func (i *appService) installationStatus(call rpc.ServerCall) (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(ErrOperationFailed, call.Context(), fmt.Sprintf("EvalSymlinks(%v) failed: %v", versionLink, err))
	}
	return device.InstallationStatus{
		State:   state,
		Version: filepath.Base(versionDir),
	}, nil
}

func (i *appService) instanceStatus(call rpc.ServerCall) (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(ErrOperationFailed, call.Context(), fmt.Sprintf("EvalSymlinks(%v) failed: %v", versionLink, err))
	}
	return device.InstanceStatus{
		State:   state,
		Version: filepath.Base(versionDir),
	}, nil
}