as United States
`a2) Patent Application Publication co) Pub. No.: US 2002/0095479 A1
`
` Schmidt (43) Pub. Date: Jul. 18, 2002
`
`
`US 20020095479A1
`
`(76)
`
`(54) METHOD AND APPARATUS FOR VIRTUAL
`NAMESPACES FOR ACTIVE COMPUTING
`ENVIRONMENTS
`Inventor: Brian Keith Schmidt, Mountain View,
`CA (US)
`Correspondence Address:
`J.D. Harriman II
`COUDERT BROTHERS
`23rd Floor
`333 South HopeStreet
`Los Angeles, CA 90071 (US)
`,
`Oe
`(21) Appl. No.:
`09/765,879
`
`(22)
`
`Filed:
`
`Jan. 18, 2001
`
`Publication Classification
`
`(SV) Tite C07 aieceeeccccessceeeeenneeeeeeeceeeenenee GO6F 15/16
`
`(52) US. Ce eecececssssssssessccsesssessnnnnnneseeee 709/218; 709/200
`
`ABSTRACT
`(57)
`invention provides private namespaces for
`The present
`active computing environments. The invention uses one or
`more “compute capsules”. A compute capsule is a private,
`portable, persistent environment. Each compute capsule
`comprises an arbitrary set of active processes and their
`associated state information. In onc embodiment, compute
`capsules provide a private, customizable view of a shared
`file system, so that users can modify arbitrary files without
`the expense of providing each person with a separate and
`complete file system image. In one embodiment, the inven-
`tion provides environments with different personalities, each
`of which can be contained within a capsule. For example, a
`user can have one capsule for normal desktop usage, a
`fail-safe capsule with a minimal environmentand no exter-
`nal dependencies, capsules for work-related and personal
`activities, etc. In one embodiment, capsules are given access
`rights.
`
`420
`
`CREATE ROOT-LEVEL
`DIRECTORY
`400
`
`MAP ELEMENTS FROM THE
`GLOBAL FILE SYSTEM INTO
`THE ROOT LEVEL DIRECTORY
`410
`
`POPULATE VIEW WITH SYSTEM
`DIRECTORIES AND FILES
`NECESSARY FOR NORMAL
`OPERATION
`415
`
`ALTER CAPSULE ENVIRONMENT
`TO ACCESS FILES RELATIVE TO
`THE ROOT OF THE VIEW
`
`Google Exhibit 1008
`Google v. VirtaMove
`
`Google Exhibit 1008
`Google v. VirtaMove
`
`

`

`Patent Application Publication
`
`Jul. 18,2002 Sheet 1 of 15
`
`US 2002/0095479 Al
`
`HARDWARE
`
`RESOURCE INTERFACE
`
`OPERATING SYSTEM
`
`FIGURE 1
`
`

`

`Patent Application Publication
`
`Jul. 18, 2002 Sheet 2 of 15
`
`US 2002/0095479 Al
`
`USER1
`
`USER 2
`
`PROCESS
`
`PROCESS
`
`0
`
`1
`
`OPERATING SYSTEM
`
`RESOURCE INTERFACE
`
`FIGURE 2
`
`

`

`Patent Application Publication
`
`Jul. 18, 2002 Sheet 3 of 15
`
`US 2002/0095479 Al
`
`PROCESS
`
`0
`
`CAPSULE1
`
`CAPSULE 2
`
`VIRTUAL NAMESPACE VIRTUAL NAMESPACE
`OPERATING SYSTEM
`
`FIGURE 3
`
`

`

`Patent Application Publication
`
`Jul. 18,2002 Sheet 4 of 15
`
`US 2002/0095479 Al
`
`MAP ELEMENTSFROM THE
`GLOBAL FILE SYSTEM INTO
`THE ROOT LEVEL DIRECTORY
`410
`
`420
`
`CREATE ROOT-LEVEL
`DIRECTORY
`400
`
`POPULATE VIEW WITH SYSTEM
`DIRECTORIES AND FILES
`NECESSARY FOR NORMAL
`OPERATION
`415
`
`ALTER CAPSULE ENVIRONMENT
`TO ACCESS FILES RELATIVE TO
`THE ROOT OF THE VIEW
`
`FIGURE 4
`
`

`

`Patent Application Publication
`
`Jul. 18, 2002 Sheet 5 of 15
`
`US 2002/0095479 Al
`
`FIGURE 5
`
`CAPSULE NAMESPACE
`CONTENTS
`
`FILE SYSTEM NAMESPACE
`
`FILE CONTENTS
`
`STRUCTURE
`
`

`

`Patent Application Publication
`
`Jul. 18,2002 Sheet 6 of 15
`
`US 2002/0095479 Al
`
`START
`
`FIGURE 6
`
`
`GIVE EACH RESOURCE
`WITHIN THE CAPSULE A
`VIRTUAL TOKEN
`600
`
`
`
`INTERPOSE A NAME
`
`
`TRANSLATOR BETWEEN THE
`CAPSULE AND THE RESOURCE
`610
`
`BIND VIRTUAL TOKEN TO
`THE RESOURCE
`620
`
`
`
`
`
`
`
`
`
`
`IS CAPSULE NAMING A
`RESOURCE?
`630
`
`
`
`
`USE TRANSLATOR TO TRANSLATE THE NAMED
`RESOURCEIN THE PERSONAL NAMESPACE TO
`THE ACTUAL PHYSICAL RESOURCE
`640
`
`
`
`

`

`Patent Application Publication
`
`Jul. 18,2002 Sheet 7 of 15
`
`US 2002/0095479 Al
`
`FIGURE 7
`
`700
`
`
`PHYSICAL
`VIRTUAL
`
`RESOURCE
`RESOURCE
`
`ID 0
`
`ID 0
`
`
`
`
`
`PHYSICAL
`VIRTUAL
`RESOURCE
`RESOURCE
`
`ID 1
`
`ID |
`
`
`PHYSICAL
`RESOURCE
`ID 2
`
`
`
`RESOURCE
`ID 2
`
`
`
` VIRTUAL
`
`

`

`Patent Application Publication
`
`Jul. 18,2002 Sheet 8 of 15
`
`US 2002/0095479 Al
`
`
`
`bset GOX
`Interconnect
`Interface
`
`4563 FOL
`Internal Bus
`Controller
`
`$505 HG
`Graphics
`Renderer
`
`Controller
`
`KG. 200
`Video
`Controller/Interface
`
`
`
`41503 $93
`Sound
`
`h
`Figure §: HID Single Chip Implementation
`
`

`

`Patent Application Publication
`
`Jul. 18, 2002 Sheet 9 of 15
`
`US 2002/0095479 Al
`
`;
`
`FIGURE 9
`
`900
`
`
`
`MAP A PORTION OF THE
`UNDERLYING FILE SYSTEM INTO
`THE CAPSULE'S NAMESPACE
`
`DOES THE USER WISH TO
`MODIFY THEFILE SYSTEM
`VIEW?
`310
`
`DOES THE USER WISH TO
`
`
`MODIFY A READ-ONLY OR A
`
`SYSTEMFILE?
`
`
`920
`
`
`
`MODIFY THEFILE IN THE
`
`CAPSULE'S NAMESPACE
`
`930
`
`
`
`MODIFY FILE IN
`COPY-ON-WRITE MODE
`940
`
`
`

`

`Patent Application Publication
`
`Jul. 18,2002 Sheet 10 of 15
`
`ADD FIRST NAME TRANSLATION
`TABLE TO THE KERNEL
`1000
`
`FIGURE 10
`
`ADD SECOND NAME TRANSLATION
`TABLE TO THE KERNEL
`1010
`
`1040 US 2002/0095479 Al
`
`HAS A SYSTEM OBJECT
`BEEN CREATED?
`1020
`
`ASSIGN CAPSULE LOCAL NAME
`1030
`
`ENTER OBJECTS INTO THE FIRST
`AND SECOND TABLES
`
`

`

`Patent Application Publication
`
`Jul. 18,2002 Sheet 11 of 15
`
`US 2002/0095479 Al
`
`\
`
`
`» Capsule 0
`Capsule 1
`
`
`PID
`
`
`Traditional OS
`
`Capsule OS
`
`a F
`
`igure VI
`
`

`

`Patent Application Publication
`
`Jul. 18,2002 Sheet 12 of 15
`
`US 2002/0095479 Al
`
`
`
`PROCESSOR
`
`1213
`
`
`
`
`
`NETWORK LINK 1221
`
`
`
`FIGURE 12
`
`
`
`

`

`Patent Application Publication
`
`Jul. 18,2002 Sheet 13 of 15
`
`US 2002/0095479 Al
`
`FIGURE Is
`
`CENTRAL SERVER
`
`INSTALLATION
`
`Ave
`
`(30
`
`13"
`
`END USER HARDWARE
`
`were
`
`

`

`US 2002/0095479 Al
`
`FIGURE 8 14
`
`Patent Application Publication
`
`Jul. 18,2002 Sheet 14 0f15
`
`th)
`
`8
`
`i4MoL
`
`mo
`
`mt
`
`=|
`34t
`spit
`
`+ 369—
`
`

`

`Patent Application Publication
`
`Jul. 18,2002 Sheet 15 of 15
`
`US 2002/0095479 Al
`
`1205
`Flash Memory
`
` 1804
`
`Embedded
`Processor
`<
`1406
`DRAM
`
`
`
`1408
`Smartcard
`
`Interface
`
`\ 5
`1412
`PCI Bus
`
`1201
`USB Controller
`
`103
`Audio Codec
`
`\
`
`1413
`
`\
`
`1416
`
`15
`Figure #: HID
`
`14
`
`02
`
`
`
`§
`JL 1415
`
`‘
`1410
`Video Decoder
`
`s
`
`Video Controller
`
`1iWW
`Video Encoder
`
`
`
`1414
`
`Network Contro Block
`
`

`

`US 2002/0095479 Al
`
`Jul. 18, 2002
`
`METHOD AND APPARATUS FOR VIRTUAL
`NAMESPACES FOR ACTIVE COMPUTING
`ENVIRONMENTS
`
`BACKGROUND OF THE INVENTION
`
`{0001]
`
`1. Field of the Invention
`
`[0002] The present invention relates to virtual namespaces
`for active computing environments.
`
`[0003] Portions of the disclosure of this patent document
`contain material that is subject to copyright protection. The
`copyright owner has no objection to the facsimile reproduc-
`tion by anyone of the patent documentor the patent disclo-
`sure as it appears in the Patent and Trademark Officefile or
`records, but otherwise reserves all copyright rights whatso-
`ever.
`
`[0004]
`
`2. Background Art
`
`In modern computingit is desirable for a user to be
`[0005]
`interacting with a computer, to stop the interaction with the
`computer, to move to a new computer, and to begin inter-
`acting with the new computerat precisely the point where
`the user stopped interacting with the first computer. Using
`current schemes, however, this is not possible because the
`user’s computing environment cannot be represented in a
`form that can be understood by both computers and moved
`between the computers.
`
`in co-pending U.S. patent application
`[0006] However,
`entitled “Method and Apparatus for Representing and
`Encapsulating Active Computing Environments” Applica-
`tion No. _/_,__ filed on Jan. 16, 2001, assigned to the
`assignee of the present application, and hereby fully incor-
`porated into the present application by reference,
`it was
`described how a group of active processes and their asso-
`ciated state could be represented in a form that made it
`possible to halt the active processes,
`to move them to a
`different binary compatible machine, or to suspend them on
`disk for later revival on the same or a different machine.
`
`In such an environment, many users may be
`{0007]
`accessing data or computer programs on a single remote
`computer. It would be desirable if the users could arrange
`and organize the appearance of the data and computer
`programs in a waythat is suitable for them. Furthermore, it
`would be desirable if the user’s system interface was virtu-
`alized in a manner that allowed for portability. Current
`schemes, however, do not allow for such customization or
`virtualization. Before further discussing the drawbacks of
`current schemes,it is instructive to discuss how the nature
`of computing is changing.
`
`The Nature of Computing
`
`[0008] The nature of computing is changing. Until
`recently, modem computing was mostly “machine-centric”,
`where a user accessed a dedicated computer at a single
`location. The dedicated computer had all
`the data and
`computer programs necessary for the user to operate the
`computer, and ideally,
`it had large amounts of hardware,
`such as disk drives, memory, processors, and the like. With
`the advent of computer networks, however, different com-
`puters have become more desirable and the focus of com-
`puting has become “service-oriented”. In particular, com-
`puter networks allow a user to access data and computer
`programs that exist elsewhere in the network When the user
`accesses such data or computer programs, the remote com-
`
`puter is said to be providing a service to the user. With the
`improvementin services available to users, the need to have
`a dedicated computer following the machine-centric para-
`digm is greatly reduced. The machine-centric paradigm also
`becomes muchless practical in this environment because
`distributing services is much more cost-effective.
`
`In particular, computers in a service-oriented envi-
`[0009]
`ronment have little need for powerful hardware. For
`instance,
`the remote computer processes the instructions
`before providing the service, so a powerful processoris not
`needed on the local access hardware. Similarly, since the
`service is providing the data,there is little need to have large
`capacitydisk drives on the local access hardware. In such an
`environment, one advantage is that computer systems have
`been implemented that allow a user to access any computer
`in the system andstill usc the computer in the same manner
`(i.e., have access to the same data and computer programs).
`
`{0010] For instance, a user may be in location A and
`running a word processor, a web browser, and an interactive
`multimedia simulation. In a service-oriented environment,
`the user might stop using the computer in location A and
`move to location B where the user could resume these
`
`computer programs ona different machine at the exact point
`where the user stopped using the machine at location A, as
`long as both computers had access via the computer network
`to the servers where the programs were being executed. The
`programs in this example, however, cannot be moved
`between computers when they are active because of the
`design of current operating systems.
`
`Resource Naming
`
`Ona typical machine object namesare host-depen-
`(0011]
`dent and not the resource interface between the kernel and
`
`user is not cleanly separated. Tokens used bythe kernel to
`identify resources encapsulate the binding to the underlying
`physical resource as well, and resource tokensare only valid
`for a specific machine. This creates unnecessary dependen-
`cies that irreversibly couple processes to particular instances
`of an operating system on particular machines
`
`[0012] One scheme, for instance, uses a Unix process
`identifier (PID), which is a token by which one process may
`refer to another process. The PID, however, is actually an
`index into an active process table inside the kernel, (i.e., it
`is the physical resource itself). A PID is only valid on a
`particular machine and is not globally unique. A process
`cannot moveto another machine and maintain the same PID.
`Thus, a scheme using a PID limits the ability for a group of
`active processes to move between machinesandstill be able
`to access the resources they need to continue to run.
`
`Customization
`
`It is desirable to retain some of the benefits of
`[0013]
`machine-centric computing. In particular, machine-centric
`computing allows a user to customize their computing
`environment, for instance by arranging and namingtheirfile
`system. This is trivial
`in a machine-centric environment
`because typically only one user controls the machine. In a
`service-oriented environment, however, remote computers
`are often accessed by many users, and the samefiles are
`shared between all of these users. In such environments,
`uscrs havelittle opportunity to customize their environment.
`
`

`

`US 2002/0095479 Al
`
`Jul. 18, 2002
`
`Privacy, Isolation, and Security
`
`[0014] Other benefits from machine-centric computing
`that are desirable to retain are privacy, isolation, and secu-
`rity. In particular, machine centric computing gives the user
`a dedicated machine that is completely secure and private,
`and totally isolated from everyone else. In a shared envi-
`ronment, however, such security, privacy, and isolation is
`difficult to achieve.
`
`Ina service-oriented environment remote comput-
`[0015]
`ers are often accessed by manyusers, and the same resources
`are shared betweenall of these users. In such environments,
`users can view and sometimes manipulate the resources in
`use by others. These issues are all related to the naming of
`resource objects in the system (e.g.,
`files, processors,
`memory, and attached devices). One scheme, for instance,
`shares the names of objects across manyusers. This limits
`isolation and privacy because every user can name and
`access all objects in the system, including those controlled
`by others. This further limits security because every user has
`access to the same objects and may perform unwanted
`modifications on them.
`
`SUMMARY OF THE INVENTION
`
`[0016] The present invention provides virtual namespaces
`for active computing environments. According to one or
`more embodiments of the present invention a “compute
`capsule” is implemented. Each compute capsule serves to
`represent and encapsulate an active computing environment.
`An active computing environment comprises one or more
`active processes and the complete state necessary to allow
`the encapsulation to be suspended and revived on any binary
`compatible machine.
`
`[0017] Using the compute capsule, one embodimentofthe
`present invention providesa private, customizable view of a
`shared file system, so that users can modify arbitrary files
`without the expense of providing each person with a sepa-
`rate and complete file system image. The underlying file
`system is mapped into the compute capsule in a portion of
`the capsule called a “virtual namespace”. The owner of the
`capsule (or other entity with access rights) is permitted to
`alter the files in the virtual namespace in a mannersimilar to
`the way a user might alter the file system on a dedicated
`computer in a machine-centric environment.
`
`[0018] The virtual namespace is host-independent, mean-
`ing that resources (e.g.,
`files, processors, memory, and
`attached devices) have location-transparent names. This
`enables the capsule to migrate between binary compatible
`machines and provides privacy and isolation between mul-
`tiple capsules.
`
`In another embodiment, the files mapped into the
`[0019]
`capsule maybe read-onlyfiles. In this case, the ownerof the
`capsule is permitted to modify the file within their virtual
`namespace
`only, while
`the underlying file
`remains
`unchanged. This is termed “copy-on-write mode”.
`
`In onc embodiment, the invention provides envi-
`[0020]
`ronments with different personalities, each of which can be
`contained within a capsule. For example, a user can have one
`capsule for normal desktop usage, a fail-safe capsule with a
`minimal environment and no external dependencies, and
`capsules for work-related and personal activities. This is
`achieved bycontrolling the contents of the namespacc. For
`
`instance, a capsule might be created for an untrusted guest
`user by populating the namespace with reference to a limited
`set of resources. In one embodiment, capsules are given
`accessrights.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0021] These and otherfeatures, aspects and advantages of
`the present invention will become better understood with
`regard to the following description, appended claims and
`accompanying drawings where:
`
`[0022] FIG. 1 provides an overview of a multi-tier com-
`puter architecture.
`
`[0023] FIG. 2 showsa typical arrangement of a resource
`interface in a machine-centric environment.
`
`[0024] FIG. 3 showsa typical arrangement of a resource
`interface in a shared environment.
`
`[0025] FIG. 4 shows the creation of a file system view
`according to an embodiment of the present invention.
`
`(0026] FIG. 5 is a diagram showingthe file system view
`and how it is mapped from the underlying file system into
`the capsule according to an embodiment of the present
`invention.
`
`[0027] FIG. 6 shows how an embodimentof the present
`invention names resources.
`
`FIG.7 is a nametranslation table according to an
`[0028]
`embodiment of the present invention.
`
`FIG.8 is a block diagram of a single chip imple-
`[0029]
`mentation of a human interface device.
`
`FIG.9 is a flowchart showing the manner in which
`[0030]
`one embodiment of the present invention maintains a per-
`sonal view of the underlying operating system.
`
`[0031] FIG. 10 shows how an embodimentof the present
`invention names resources.
`
`[0032] FIG. 11 shows the namespace of a traditional
`operating system compared to a compute capsule.
`
`[0033] FIG. 12 is an embodimentof a computer execution
`environment in which one or more embodiments of the
`present invention can be implemented.
`
`[0034] FIG. 13 shows an example of a thin client topology
`called a virtual desktop system architecture.
`
`[0035] FIG. 14 displays the partitioning of the function-
`ality of the virtual desktop system architecture.
`
`[0036] FIG. 15 is a block diagram of an example embodi-
`ment of a humaninterface device.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`[0037] The invention is personal namespaces for active
`computing cnvironments.
`In the following description,
`numerous specific details are set forth to provide a more
`thorough description of embodiments of the invention. It is
`apparent, however, to one skilled in the art, that the inven-
`tion may be practiced without these specific details. In other
`instances, well known features have not been described in
`detail so as not to obscure the invention.
`
`

`

`US 2002/0095479 Al
`
`Jul. 18, 2002
`
`Compute Capsules
`
`[0043] FIG. 2 shows a shared system. There, multiple
`processes labeled process 0, process 1, process N-1, and
`[0038] A compute capsule comprises one or more pro-
`process N. Processes 0 and 1 are owned byafirst user.
`cesses and their associated system environment. A compute
`Processes N-1 and N are owned by a second user. Thefirst
`capsule is configured to provide an encapsulated form that is
`and second users’
`interactions with the system will be
`capable of being moved between computers or stored off-
`through a resource interface coupled to the operating system,
`line, for instance on a disk drive or other non-volatile storage
`which is in turn coupled to the machine hardware. In this
`medium. The system environment in a capsule comprises
`example, as with the example of FIG. 1,
`the resource
`state information relating to exactly what the processes are
`interface is irreversibly coupled to the operating system and
`doing at any given time in a form that is understandable by
`the hardware, which makes it impossible for processes 1
`any binary compatible machine. System environmentinfor-
`through N to ever migrate from the machine.
`mation mayinclude, for instance, privileges, configuration
`[0044] FIG.3showsthe virtualized namespace according
`settings, working directories and files, assigned resources,
`to an embodimentof the present invention. There, capsules
`open devices, installed software, and internal program state.
`1 and 2 each have two processes active within them, labeled
`processes 0, 1, N-1, and N respectively. Additionally, cap-
`sules 1 and 2 have a virtual namespace within them. The
`virtual namespaces of each capsule are able to communicate
`with the operating system and then to the computer hard-
`ware coupled to the operating system. The capsules, how-
`ever, are not bound to the naming system used by the
`specific instance of the operating system shown in the
`example. Instead, they may communicate with hardware in
`a host-independent manner through the virtual namespace
`and could do so as well if migrated to a different instance of
`an operating system on a different machine.
`
`In one embodiment, the operating system is re-
`[0039]
`partitioned so that some of the internal program’s state is
`moved into the capsule. This includes moving one or more
`elements of the CPU state, the file system state, the device
`state, the virtual memory state, and the inter-process com-
`munication (IPC) state into the capsule.
`
`[0040] Processes in the same capsule may communicate
`with each other and share data, for instance using pipes,
`shared memory, or signals. Communication with processes
`outside the capsule, on the other hand,
`is restricted to
`Internet sockets and globally shared files. This ensures that
`capsules can move without restriction. For example, a pipe
`between processes in different capsules would force both
`capsules to reside on the same machine, but a socket can be
`redirected. The use of compute capsules is completely
`transparent, and applications need not
`take any special
`measures, such as source code modification, re-compilation,
`or linking with special librarics. In addition, a system using
`compute capsules can seamlesslyinter-operate with systems
`that do not.
`
`Virtual Namespace
`
`isolation, and security
`[0041] Capsules offer privacy,
`within a
`shared environment by providing a virtual
`namespace within each capsule. Current systems allowusers
`to access all processes and other system resources. For
`instance, anyone can gather (and sometimes manipulate)
`information about the activities of others. Compute capsules
`address this issue by providing a virtual namespace forits
`member processes where all name references are local to a
`capsule (i.e., they are valid only within the capsule), and
`capsule contents are not externally visible or accessible
`(unless they are explicitly exported). Thus, capsules provide
`privacy and isolation because they are completely disjoint,
`(ie., it is impossible for an object in one capsule to name an
`object in another capsule).
`
`[0042] To provide a virtualized namespace the interface
`with which a process accesses resources must be changed.
`FIGS. 1 and 2 show examples of how resource interfaces
`are typically arranged. FIG. 1 showsa dedicated system in
`a common machine-centric environment. There, multiple
`processeslabeled process 1 through process N are owned by
`a single uscr. Their intcraction with the system will be
`through a resource interface coupled to the operating system,
`which is in turn coupled to the machine hardware. In this
`example the resource interface is irreversibly coupled to the
`operating system and the hardware, which makesit impos-
`sible for processes 1 through N to ever migrate from the
`machine.
`
`neOo
`
`Tile System View
`[0045] One componentof the virtual namespaceis the fi
`system view. The file system view gives each capsule
`personal view of the underlying file system and provide
`capsule owners with the ability to customize their capsu
`environments within a shared system. To create the fi
`system view for a compute capsule, each user is assigne
`globally accessible capsule storage to contain the view.
`Whereas a compute capsule resides entirely within a single
`machine at any given time, the underlying file system is
`globally available. This provides a simple mechanism for
`sharing data between capsules, as well as for maintaining a
`coherent view of the operating environment as the capsule
`moves. For example, a user may own multiple capsulesthat
`access a shared database, or software packages can be made
`globally available for use byall capsules.
`
`ao0
`
`[0046] Capsules map portions of the file system into their
`namespace, thereby leveraging the underlying system for
`most file administration tasks (e.g., backups, maintaining
`software packages, installing disks, configuringfile servers,
`etc.). The file system view is private to a capsule and fully
`modifiable by its owner, and it provides a copy-on-write
`modeoffile access to support the modification of read-only
`or systemfiles. In addition, capsules may export portions of
`their view to other capsules in order to support data sharing.
`
`In one embodiment, when a capsule is created, a
`[0047]
`newfile system view is synthesized as shown in FIG.4. At
`step 400 a root-level directory is created. Then, at step 410,
`elements from the global file system are mapped into the
`root-level directory. Next, the view is populated with system
`dircctorics and files necessary for normal operation at step
`415. Thereafter, the system alters the environment of the
`compute capsule so that it will accessfiles relative to the root
`of this view at step 420. This cnhances both sccurity and
`privacy, as capsules are restricted to accessing onlyfiles
`within their private views. Protection of files mapped into
`different views is provided by the underlying file system.
`
`

`

`US 2002/0095479 Al
`
`Jul. 18, 2002
`
`In one embodiment, by default, file system views
`[0048]
`are automatically populated with system directories andfiles
`necessary for normal user operation as shown at step 430.
`Such files include, for instance: application binaries,librar-
`ies, certain device drivers, user home directory and data
`files, etc. The contents of the view are fully configurable by
`the owner of the capsule, which means that system-level
`files can be modified. Because thesefiles are shared byother
`capsules,
`they are mapped into a file system view in a
`copy-on-write mode. When a capsule modifies such a sys-
`tem file, a private copy is added to the capsule, and the
`altered file follows the capsule so that the changespersist. In
`this way, changes only affect the capsule that made the
`modifications. Files and directories normally assumed to
`reside in local storage (e.g., the Unix swap directory where
`temporary files are offen created) must move with the
`capsule. Conversely, there are many standard, machine-local
`directories that are the same across systems (e.g.,
`/bin
`contains application programs on Unix systems), which may
`be mapped into the file system view directly from the local
`machine for improved performance.
`
`[0049] FIG. 5 is a diagram showing the file system view
`and how it is mapped from the underlying file system into
`the capsule. The file system namespacestructure is internal
`to the capsule and fully modifiable by its owner. The names
`of the files in the file system namespace structure, 530 for
`instance, maybe changed by the capsule owner. File 530
`references the contents of a file in the underlying globalfile
`system. File 500 is an example ofa file stored locally that is
`mapped into the capsule namespace 540.
`
`File 510 is an example of a system file that is
`[0050]
`copied into the capsule namespace 550 because it was
`modified by the capsule owner. File 520 is a read-onlyfile
`that is copied into the capsule namespace 560 for update.
`File 520 is read-only because it is owned by the adminis-
`trator in the underlying file system, who did not allow
`normal users to modify it. In the capsule the ownerplays the
`administrator role, so file 520 is copied into the capsule
`where it is owned by the capsule owner. This is termed
`copy-on-write mode which means that when the capsule
`ownerwants to write to file 560, it is copied into the capsule
`from file 520.
`
`{0051] Elements from the underlying file system are
`mapped into the view based on the contents of two configu-
`ration files,
`in one embodiment. The first
`file provides
`site-wide defaults, which enables all capsules to access
`standard software and data in the system. The secondfile is
`located within a user’s capsule storage and contains custom
`mappings. In one embodiment, the default set offile system
`view mappings includes standard system directories, such as
`/bin for applications, /lib for system libraries, Aisr/man for
`manualpages, etc. These system files are typically cached on
`local disks, and it is assumed their contents are uniform
`across machines in the system. Given that such files are
`rarely changed and that system administrators maintain
`consistency among the machinesin the system, this is a valid
`assumption. In one embodiment, a special directory called
`/capsule is mapped into all capsules, and it contains global
`capsule information, such as the capsule name database.
`
`[0052] To create the file system view from the configura-
`tion files, mount points are established for each of the
`required dircctorics, and then the loopback file system is
`
`used to map them into the view from the local machine.
`Although capsule ownersare free to modify theirfile system
`views, it is not desirable for them to modify the underlying
`local system-level
`files (for which they may not have
`permission). Thus, mounts of directories such as /lib are
`made read-only. If users wish to modify a directory such as
`/lib, they make a copy in their view and remove the map to
`the underlying file system. Then, changes only affect the
`copy, which will remainin the user’s private capsule storage.
`For directories like /tmp, the system creates a unique sub-
`directory inside and then uses the loopback file system to
`map the subdirectory into the view with the original direc-
`tory name. The contents of such directories are cached on the
`local machine but maintained in capsule storage. In one
`embodiment, once mounts have been established, a chroot
`system call re-assigns the root of the file system to be the
`root of the file system view, which gives capsules the
`illusion of a private file system.
`
`[0053] The manner in which one embodiment of the
`present
`invention implements the personal view of the
`underlying operating system is shown in FIG. 9. At step
`900, a portion of the underlying file system is mapped into
`the capsule’s virtual namespace. Then, at step 910,
`it is
`determined whether the owneror user of the capsule wishes
`to modify the file system view. If not, the algorithm con-
`linues to wail until the user does wish lo modify the file
`system view.If so, it is next determined at step 920 whether
`the user wishes to modify a read-only or a system file. If the
`file is not read-only or a systemfile, the file in the capsule’s
`namespace is modified at step 930 and the process repeats at
`step 910. If the file is read-only or a system file, the file is
`modified in a copy-on-write mode at step 940 and the
`process repeats at step 910.
`
`Resource Naming
`
`[0054] Capsules provide host-independence and isolation
`via a name translation mechanism within the virtual
`namespace that allows capsules to name resources. Each
`resource a compute capsule can nameis assigned a virtual
`token that is only valid within the capsule. The tokens are
`unique to each capsule and valid across all machines in the
`system. They are transparently and dynamically bound to
`ditterent physical resources on any host in the system. In this
`way, capsules separate the naming of resources from their
`physical embodiment. When a process passes a reference to
`a resource object to the kernel, the virtual name is mapped
`to the physical resource in the local system. This procedure
`is reversed for return values from the kernel.
`
`[0055] Resource objects include processes, process iden-
`tifiers, shared memory segments, open devices, message
`queue keys, semaphore keys, and Internet addresses, for
`instance. A nametranslation table binds user-visible tokens
`
`to the physical resources on the underlying machine. Aname
`translator is interposed between user processes operating in
`the capsule virtual namespace and the rest of the system,
`which operates on the physical namespace of the machine.
`Translation is transparent to the operating system and appli-
`cations,(i.e., they require no modifications).
`
`[0056] Consider the example of process identificrs (PIDs).
`Each process in a compute capsule is assigned a virtual PID,
`which is mapped to the system-level PID on the underlying
`machine. Processes can name other processes only bytheir
`
`

`

`US 2002/0095479 Al
`
`Jul. 18, 2002
`
`remote mounts. From the perspective of the capsule system,
`there are two capsules, (capsules 0 and 1), each containing
`two processes and separate views of the file system.
`[0062] Consider process 55, which has been assigned
`VPID 20 in capsule 0. If this process were to execute the ps
`command on a UNIX-based operating system or execute
`“Is/proc”. the result would be to return the values 20 and 21.
`Ifit were to execute the shell command “kill 56”or “kill 22”,
`it would receive an error since 56 is the PID for the process
`with VPID 21, and there is no process in capsule 0 with
`VPID 22. Similarly, if it tried to issue a “cd” command to
`directory 1100, it would receive an error.
`
`virtual PIDs. If the capsule movesto a new host, its member
`processes may be assigned