Application-Specific Resolution

of Kiss Coda Wiki

The original Application-Specific Resolution framework has been brought up-to-date in several branches of the Coda file system for Linux 2.6 kernels, with more development in progress for robustness and compatibility with other operating systems.

Getting Started

The Application-Specific Resolution framework provides a way for both users and system administrators to automatically launch arbitrary binary files (resolvers, or ASRs) upon detection of a conflict. This allows for the possibility of repairing file system conflicts transparently to the user with a minimal performance penalty.

Getting the official Coda client with ASR

The ASR framework has been ported to the official Coda 6.1 release, available from any of the servers listed on Coda’s download webpage.

Getting the Coda write-disconnected client with ASR

It is also located in the coda.cs.cmu.edu experimental Coda 7 git repositories, accessible at /coda/coda.cs.cmu.edu/project/coda/dev/coda.git/. The best way to start using git is to follow the instructions at the Coda git page http://www.coda.cs.cmu.edu/git.html. Build the git tools locally, clone the shared git repository, and then run the following command in the root directory of the cloned git repository

    git pull origin jaharkes/expand-wdonly

which will pull in the current state of the Coda 7 branch.

Configuring the Coda Client

It is often necessary to rerun bootstrap.sh so that the configure scripts notice the new coda-src/asrlauncher subdirectory, then configure to create the Makefile in that subdirectory, and rebuild the source. Also, it is necessary to add the new variables asrlauncher_path and asrpolicy_path to venus.conf. You must build the asrlauncher binary and put its full pathname here:

    # ASRLauncher
    #
    # This is the path to the ASRLauncher, which will be executed
    # to repair conflicts upon detection. This variable exists to
    # allow the user to turn off ASRs as a Coda feature, by
    # omitting the variable or leaving its value blank.
    #
    asrlauncher_path=/usr/bin/asrlauncher
    # 
    # This is the path to the ASR local security policy, a text file
    # which contains a list of directories in which rules files may 
    # be found and used.
    #
    asrpolicy_path=/etc/coda/asrpolicy

Then, reload any Venus processes and Coda should be ready for ASRs.

Design and Implementation Overview

Framework Diagram

Framework Diagram

Above is a diagram displaying the Application-Specific Resolution framework, where arrows indicate forks or exits. Note that ideally, Venus will be a user-mode process, but at the moment it is a kernel-mode one (FIXME a confusing statement about Venus being a kernel process?). This diagram reflects the ideal ASR framework.

Upon detecting a conflict, Venus launches ASRLauncher and assigns it the privileges of the owner of the conflict. The ASRLauncher then searches through the conflict’s volume for a rules file containing a rule whose trigger executes successfully. When found, it executes the commands associated with this trigger – the ASR. The ASR repairs the conflict and returns success to ASRLauncher, which in turn reports success to Venus. Venus then retries the upcall that detected the conflict, and normal system operation continues.

Steps in a typical server/server resolution (assume callback is held on conflict):

  1. Venus receives a callback message from Vice, noting the file that has fallen into conflict. An intermediary resolve call to Vice may occur here.
  2. Venus checks whether this is an appropriate time to launch an ASR. If it is not (reasons explained later), Venus marks the object inconsistent (in conflict) and future accesses are prevented.
  3. Venus locks the volume holding a conflict and prepares to launch ASRLauncher by checking several conditions, including whether ASRs are enabled for this volume, whether the system can launch ASRs at the moment, that no other ASRs are running, and whether valid tokens exist to repair this conflict.
  4. Venus forks and execs the ‘asrlauncher’ binary, passing the pathname, volume root pathname, conflict type, and local ASR policy file as parameters.
  5. ASRLauncher performs lexical scoping. It looks in the conflict’s parent directory for an .asr rules file. If it is not found, it recurses to the parent of this parent, and again if necessary, stopping only after failing in the volume root. If a file is not found, the ASRLauncher terminates and returns an error code to Venus.
  6. ASRLauncher parses the rules file line-by-line, executing triggers until one returns status zero (success). If a rule is not found, the ASRLauncher terminates and returns an error code to Venus.
  7. ASRLauncher then reads the dependencies following the matched rule on the same line, and determines whether any of them are in conflict. If at least one is, the ASRLauncher terminates and returns an error code to Venus.
  8. ASRLauncher then reads the commands on the lines following the matched rule, until the beginning of the next rule or end-of-file is reached.
  9. ASRLauncher then forks and executes the ASR command, and waits for the child process to terminate.
  10. The ASR terminates, returning a status code to ASRLauncher.
  11. ASRLauncher terminates, returning the status of the ASR to Venus.
  12. If the ASR succeeded, the consistent object is left marked consistent, and the changes uploaded on the next reintegration. If failure is returned by ASRLauncher, the object is marked inconsistent and future accesses are prevented.

Local/global conflicts differ in their conflict discovery (step 1), but the ASR launching process is identical.

Rules Files

The pairing of conflict and ASR is done within a “rules file”, similar in structure and function to Makefiles. The key difference lies in dependency resolution; Makefiles execute commands based on the modification times of dependencies, while ASR rules files execute commands based on whether dependencies are in conflict. Only one command is allowed; this forces the user to treat a batch of commands as a single unit (an ASR) and avoid having ASRLauncher handle partially successful ASRs.

A rules file is placed anywhere within the Coda file system and applies to all children of the directory in which it resides, both directories and files, as long as they are contained within the same volume as the rules file, and are enabled in the client’s local security policy. Rules files are by definition named .asr.

Rule Syntax

The ASR rule syntax takes its structure from Makefiles:

    `[custom-trigger]`: [dependency-list]
                        [command-list]

where [custom-trigger] is the trigger command that launches this rule upon its successful completion, dependency-list are conditionals that must be checked, and command-list are actions to be taken if the conditions are met. The trigger launches whenever the command(s) within return(s) success. All three sections are parsed for environment variables, which are replaced as described below.

Custom Triggering

Custom triggers replace the old pathname triggering feature of ASR. They are simply a series of shell commands contained within two ticks. They are piped to /bin/sh and executed if the rule is reached in normal ASR launching. If the series of commands exit with return code 0, the rule is considered a hit, and the associated ASR commands are launched. A nonzero return code indicates that the trigger was not hit, and to try the next rule.

The change allows for more flexible triggering based on content. For instance, text files' filenames often contain little or no hint that they are a textfile. The new triggering method, however, could run a script isTextfile.sh as follows:

    `/home/awolbach/isTextfile.sh $=`:
      /home/awolbach/mergeTextfiles.sh $=

and then isASCII.sh could parse the content of the file to see if it actually is text:

    filetype=`file $= | cut -d' ' -f2`
    if [ filetype = "ASCII" ]
      return 0
    fi
    return 1

which would only launch the ASR command list if it actually was an ASCII text file.

Dependency Resolution

Before an ASR command is executed, all of the file and directory names to the right of the matched rule are checked for consistency. This allows the user a way to declare some files to be semantically dependent on others – a common example is how object files are dependent on their C source files. If a dependency is found to be in conflict, the launching is aborted; a file cannot be repaired from other inconsistencies. Otherwise, the ASR command is executed.

ASR Commands

ASR commands related to a rule follow it on the lines after the rule’s definition. They are simply piped into /bin/sh via stdin, thus any features your local shell supports are also supported within the command list. The command list ends when another rule’s start is detected, i.e. the first word of the line is of the form `[custom-trigger]`:.

Environment Variables

ASRLauncher replaces several builtin 2- and 3-character environment variables when executing triggers, resolving dependencies, and executing commands.

    $= 
        Full pathname of the conflict.

    $> 
        Basename of the conflict (filename relative to its parent directory).

    $< 
        Full pathname of the parent directory of the conflict.

    $: 
        Full pathname of the volume root of this conflict.

    $@ 
        Architecture and operating system on which the Coda client is running (identical to cfs @sys).

    $! 
        Integer declaring the type of conflict. The actual number is abstracted by the following:

        $!S 
            Server/server conflict integer.

        $!L 
            Local/global or client/server conflict integer.

        $!M 
            Mixed or client/server/server conflict integer.

Take the following rule:

    `isFoo.sh`:
            removeinc $=

In this example with a local/global conflict on “/coda/coda.cs.cmu.edu/usr/awolbach/dir/conflict.o” on an x86 machine running Linux,

    $= is replaced by /coda/coda.cs.cmu.edu/usr/awolbach/dir/conflict.o
    $> is replaced by conflict.o
    $< is replaced by /coda/coda.cs.cmu.edu/usr/awolbach/dir/
    $: is replaced by /coda/coda.cs.cmu.edu/usr/awolbach/
    $@ is replaced by i386_linux
    $! is replaced by 2
        $!S is replaced by 1
        $!L is replaced by 2
        $!M is replaced by 3

Full Example

    awolbach@isrdebian:/coda/coda.cs.cmu.edu/usr/awolbach/ooffice$ cat .asr
    # OpenDocument ASR
    `str=\`file $=\`; test str = "$=: OpenDocument Text"`:
            $@/ASRs/ooasr.sh $=

ASRLauncher

A launchpad for ASR’s that performs several tasks, including finding and parsing the appropriate rules file.

Lexical Scoping

Upon receiving a conflict, ASRLauncher will immediately try to find a rules files associated with the conflict. The search for a .asr file is done recursively, starting in the parent directory and recursing all the way up to the volume root, if necessary. If an ASR rules file is found, it is parsed to search for a matching rule. If no rule is found, ASRLauncher resumes its climb up the directory tree, returning failure to Venus if no match is found at any point.

This recursive search is known as lexical scoping, and it allows for the placement of a rules file at the base of a volume that could potentially apply to every file within the volume, saving an administrator a lot of work if a common ASR command is used for a class of files within a volume.

Limiting Runtime

To preserve a consistent view of a volume for the ASR, the volume is locked at launch time and throughout the ASR’s execution. However, ASR’s are considered untrusted software and it is possible for a faulty or malicious ASR to run indefinitely. To combat this problem, after a timeout period ASRLauncher sends a kill signal to the process group of the ASR that was initially forked, and returns an error to Venus. At the moment, the timeout period is the same as the RPC2 timeout, 60 seconds, though this is subject to change.

Local ASR Execution Policy

One symptom of storing rules files within Coda itself is that in shared volumes, users may execute ASRs that other users have defined, simply by looking in their subdirectories and noticing a conflict. Malicious users could use this to corrupt the state of another user. To prevent this, ASRLauncher checks venus.conf for a local access policy file that lists the directories for which ASR’s may be executed. To enable a rules file, you must list its containing directory or directory hierarchy in this file.

The file is named within venus.conf, by the variable asrpolicy_path. The file can exist anywhere in your file system, including within /coda in a private directory, if you want the policy distributed. The file structure is simple, consisting of one directory per line in which to enable any .asr file:

    /coda/coda.cs.cmu.edu/usr/awolbach/foo1
    /coda/coda.cs.cmu.edu/usr/awolbach/foo2/

To enable an entire hierarchy (all rules files that have this directory as an ancestor), end the directory pathname with a double forwards slash (//):

    /coda/coda.cs.cmu.edu/usr/awolbach/foo3//

Additions to Venus

To reintroduce the ASR framework, several significant changes were added to Venus in addition to the execution of ASRLauncher.

Security: Token Assignment

ASRs are designed to run with user privileges in the context of a special user local to the client, called asr-uid. To achieve this, the Coda authentication token associated with this Coda user is assigned to asr-uid. If the invoking user is unauthenticated, no token exists and Venus will stop the launch process and mark the object in conflict. If the assignment succeeds, the ASR then shares all of the same privileges as the invoking user, allowing the ASR to attempt a repair. This protects Coda from an errant or malicious ASR writing over all authenticated users' data, limiting the damage to the invoking user’s data. This was the optimal availability versus security tradeoff made in the original ASR implementation.

For compatibility reasons, this change will not become effective until the new major release of Coda 7.0. Therefore, until that time comes, a setuid to the invoking user’s uid is performed before exec-ing ASRLauncher. In the worst case this gives the ASR root privileges (if you happen to be exploring Coda space as root), but hopefully contains the problem to user-space most of the time.

Robustness: Launch Frequency Controls

ASRLauncher depends on the return code of the ASR to report success or failure. Since ASRs are untrusted, it is possible that an errant ASR could report success without actually repairing the conflict. Venus would then retry the operation, note another conflict, and relaunch the ASR, causing an infinite loop of non-repairs that essentially lock the user out of the containing volume.

To mitigate this problem, Venus controls the frequency of launches for conflicts. An ASR can be launched for a conflict once every minute (subject to change). The rest of the time, the volume is available for use.

Atomicity: Atomic Repair Tools

Atomicity is ensured in the write-disconnected state through the use of repair tools. That is, there is no other way to alter a conflict’s data than using an atomic repair command/utility (such as cfs discardlocal or filerepair), which either succeeds or fails.

This is obvious for server/server conflicts, as the methods to repair them are removeinc, filerepair and the repair utility, which either succeed or fail.

This is not immediately obvious for local/global conflicts. What is important to note is that in Coda, a local/global conflict is considered to be the conflicting update or CML entry and not every update associated with the actual file. Therefore, the CML manipulation commands listed below are atomic, and local/global ASRs should be written to handle per-CML-entry conflicts. Methods to repair local/global conflicts are the repair utility, as well as the new cfs pioctls listed below, and of course cfs purgeml.

The atomicity of an ASR that attempts to repair multiple conflicts, however, is not guaranteed. Currently there is no mechanism to backup the CML during ASR execution and restore it upon failure, or undo changes that have made it to the server. Therefore to avoid potential loss of data, it is recommended that ASR’s deal with only one conflict at a time. This was the intention of the new framework design.

Isolation: Volume Locking

After discovering a conflict but before executing the ASRLauncher binary, Venus will lock the volume in which the conflict is contained to preserve a consistent view for the ASR throughout its execution. To achieve this, it prevents any read or write accesses in the conflict’s volume that do not come from the ASRLauncher’s process group, which is set with the ASRLauncher’s process id. As a result it is important not to invoke any commands that call setpgid(), as they will fail on any access to the conflict’s volume.

When the ASR completes and ASRLauncher returns, the SIGCHLD handler in Venus will unlock the volume and normal access resumes.

Key Differences from Original Implementation

There are a number of major differences between Puneet Kumar’s original implementation of Application-Specific Resolution in the early 1990’s and the recent redevelopment:

  1. Local/global conflict resolution is possible now; disconnected operation was not well-supported back then.
  2. Directory conflicts can be launched for and repaired, which was not available in the original implementation.
  3. There is one consolidated ASRLauncher, forked directly from venus and passed the necessary parameters, rather than the several ASR starter and executor processes that communicated via RPC2 calls.
  4. The new design aims to be cross-platform between Linux, Unix and Windows, and possibly Mac OS X also.
  5. Atomicity is guaranteed in a different way: previously, all ASR actions were logged (outside of the CML); now, all possible repair operations are necessarily atomic through the use of provided utilities.
  6. There is now a mechanism to prevent a malicious user from running errant ASRs on your system, through the ASR local security policy.

Example ASRs

Main article: Example ASRs

Current Status

Linux

The Linux version of Application-Specific Resolution is alive and running with one practical ASR in use, namely the OpenOffice.org one listed below. It is still under development but is relatively stable. It was based on an experimental branch that aims to be a major release in the future, but is incompatible with the current release.

A backport of the experimental branch to the official release has been completed, integrating all of the features listed above.

Related Tools

How to run Graphical ASRs in the X Server

After the X server has initialized, perform the following as an X authenticated user:

    user@host$ xauth extract - $DISPLAY > ~/xauth.key

As the user with whom you want to launch graphical applications (usually root at the moment):

    root@host: xauth merge /home/user/xauth.key

Now before launching graphical applications, make sure you:

    export DISPLAY=:0.0     # or something better if you know

This is also possible without the xauth key extraction if the other user is root, but since venus is moving away from root in the near future, this should be avoided and therefore the method is not listed here. Also, note that this will usually fail on multi-user systems as only one person’s display is “:0.0”.

Related/New cfs pioctl’s

ASR

The cfs interface provides a way to enable or disable ASR execution on a per-volume basis. The default is to disable ASR launching in all volumes.

    cfs enableasr [volume] 
        Enable ASR launching in this volume.
    cfs disableasr [volume] 
        Disable ASR launching in this volume.

Conflict Expansion

Along with the ASR framework, a new interface for exposing the replicas of a file system object was developed (existing only in the experimental Coda 7 “write-disconnect-only” branch). This is known as object expansion and is used through two new cfs commands (venus pioctls). It can be used on any replicated object in the Coda file system. In the experimental Coda 7 write-disconnect branch, cfs beginrepair and cfs endrepair are aliased to cfs expand and cfs collapse, respectively.

    cfs expand [filename] 
        Expose the underlying replicas of [filename] as descendants of a directory named [filename].
    cfs collapse [filename] 
        Hide the underlying replicas of [filename].

When an object is expanded, it becomes a directory. Each replica is attached to this directory with the filename of the server owning the replica, as well as one named localhost if a locally cached copy exists or a broken symlink named .localhost if no local copy is cached. This differs from the original ASR implementation in that there is no fakeify’d directory that is served during volume-wide repair operations. The directory structure is actually altered. An example:

    awolbach@isrdebian:/coda/coda.cs.cmu.edu/usr/awolbach$ cfs expand conflict.odt
    awolbach@isrdebian:/coda/coda.cs.cmu.edu/usr/awolbach$ ls conflict.odt/
    localhost  marais.coda.cs.cmu.edu  mozart.coda.cs.cmu.edu  verdi.coda.cs.cmu.edu
    awolbach@isrdebian:/coda/coda.cs.cmu.edu/usr/awolbach$ cfs collapse conflict.odt/
    awolbach@isrdebian:/coda/coda.cs.cmu.edu/usr/awolbach$ ls conflict.odt 
    conflict.odt

Client Modify Log

To better expose the CML to editing by an ASR, several commands exist to alter individual CML entries or the CML as a whole.

    cfs listlocal [volume] 
        List all unreintegrated CML entries within [volume].
    cfs preservelocal [volume] 
        Attempt a semantic repair of the head of [volume]'s CML.
    cfs discardlocal [volume] 
        Discard the head of a [volume]'s CML.

Note: preservelocal is identical in function to the historic local/global preserve command in the Coda repair utility.

Repair Utility

With the new expansion tools described above, the Coda repair utility underwent a rewrite to take advantage of the new interface. Thus, the repair tool in the experimental Coda branch is very different than the one in official releases, and it attempts to generalize over conflict type (viewing a local copy as a replicated server named “localhost”), rather than view conflicts as local/global or server/server.

Known Bugs

A known bug within Venus is resolving full pathnames via the fsobj::GetPath or cmlent::GetPath functions. These functions recursively climb the directory hierarchy to build a pathname string. If any file system object in this hierarchy does not have its full status (it is a runt), the function will put a ‘???’ instead of the object’s name in the pathname string and terminate. Since the ASRLauncher depends on the pathname string of the conflict, ASR’s cannot be launched for any object which does not have status in every level of its pathname. One way in which this could happen is if cfs flush is called on some level of parent of the conflict before the conflict is detected.

Future Work

Rebuild/rewrite removeinc and filerepair for new expansion interface in the Coda 7 “write-disconnect only” experimental branch.

Links

Original Research

Kumar, P. Mitgating the Effects of Optimistic Replication in a Distributed File System http://www.cs.cmu.edu/afs/cs/project/coda-www/ResearchWebPages/docdir/pkumar-thesis.pdf. School of Computer Science, Carnegie Mellon University, Dec. 1994, CMU-CS-94-215.

Kumar, P., Satyanarayanan, M. Flexible and Safe Resolution of File Conflicts http://www.cs.cmu.edu/afs/cs/project/coda-www/ResearchWebPages/docdir/usenix95.pdf. Proceedings of the USENIX Winter 1995 Technical Conference, Jan. 1995, New Orleans, LA.

Kumar, P., Satyanarayanan, M. Supporting Application-Specific Resolution in an Optimistically Replicated File System http://www.cs.cmu.edu/afs/cs/project/coda-www/ResearchWebPages/docdir/wwos4.pdf. Proceedings of the Fourth IEEE Workshop on Workstation Operating Systems, Oct. 1993, Napa, CA, pp. 66-70.

Miscellaneous

Coda mailing list thread on potential ASR applications http://www.coda.cs.cmu.edu/maillists/codalist/codalist-2006/7936.html


At its former host wikidev.net this page has been accessed 4666 times.


Last modified: Thu Jun 26 07:36:58 UTC 2014