$A MARK=1
$A PAGENO=42


$A LEFT=0; LINE=69; PAGE=57
$A TOP=4; BOTTOM=9
$A NLS=2
$A TAB=1,7,13,19,25
$B5
$L1 CM
CHAPTER 2.
$B5
$L1 CM
OVERVIEW OF CAPABILITY BASED PROTECTION.
$N
2.0.- .INTRODUCTION.
$P2
@IN THE PRESENT WORK WE ARE CONCERNED WITH PROTECTION MECHANISMS
WITH SPECIAL EMPHASIS ON THE PROVISION OF A SUITABLE SKELETON FOR THE
SUPPORT OF USER AVAILABLE SYNCHRONISING PRIMITIVES.
$P
@THE DEMAND FOR POWERFUL PROTECTION MECHANISMS IS BY NO MEANS AN
EXCLUSIVE PREROGATIVE OF THE IMPLEMENTATION OF SYNCHRONISATION
MECHANISMS. @HOWEVER, THE APPLICATION EXHIBITS MOST, IF NOT ALL, OF
THE PROBLEMS ENCOUNTERED IN THE PROTECTION OF A GENERIC RESOURCE.
@FIRSTLY, SEMAPHORES (OR SEMAPHORE DATA STRUCTURES) ARE, BY
DEFINITION, SHARED RESOURCES. @IN FACT, SEMAPHORES ARE MORE GENERAL
THAN OTHER SHARED SESOURCES IN THAT THE HARMONIOUS SHARING OF SOME OF
THE LATTER RELIES ON SYNCHRONISATION DATA STRUCTURES AND THE
SYNCHRONISING PRIMITIVES. @SECONDLY, THE INTEGRITY OF SEMAPHORES IS
CRUCIAL TO THE SYSTEM'S WELL BEING. @WITHOUT IT, IT WOULD BE
IMPOSSIBLE TO DETECT HARMFUL SITUATIONS ARISING FROM THE USE OF
SEMAPHORES BY USER PROCESSES.
$P
@EARLY EXAMPLES OF THE USE OF PROTECTED DATA TO CONTROL ACCESS TO
MEMORY SEGMENTS ARE THE DESCRIPTORS OF THE @BURROUGHS SYSTEMS AND THE
@RICE @UNIVERSITY COMPUTERS, AND THE CODEWORDS OF @ILLIFFE'S @BASIC
MACHINE [@IL68]. @DENNIS AND @VAN @HORN GENERALISED THE CONCEPT WITH
THE
INTRODUCTION OF A PROTECTED PIECE OF DATA, CALLED A CAPABILITY, TO
CONTROL ACCESS TO EVERY SYSTEM RESOURCE [@DE66]. @ONLY THE SYSTEM CAN
CREATE AND MODIFY CAPABILITIES; HENCE, THEY ARE PROTECTED.
$P
@IN A CAPABILITY SYSTEM THE BASIC UNIT OF ACCESS IS AN OBJECT AND
EVERY OBJECT IS ASSOCIATED WITH A CAPABILITY. @PROTECTION IS ACHIEVED
BY REQUIRING THAT ACCESS TO AN OBJECT BE ACCOMPLISHED ONLY IF ITS
ASSOCIATED CAPABILITY IS PRESENTED. @THE PROTECTION MECHANISM CAN
THEN VERIFY THAT THE CAPABILITY FOR THE OBJECT ALLOW THE REQUESTED
ACCESS MODE BEFORE PERMITTING THE OPERATION TO TAKE PLACE. @THUS,
PROCESSES ATTEMPT TO PERFORM OPERATIONS ON OBJECTS SUBJECT TO THE
RESTRICTIONS IMPOSED BY THE PROTECTION SYSTEM AND THE PROTECTION
MECHANISM USES THE CAPABILITIES FOR THE OBJECTS IN ORDER TO DETERMINE
THE PROPRIETY OF THE OPERATIONS WHICH THE PROCESSES ATTEMPT TO
EXECUTE.
$P
@IN PRINCIPLE, CAPABILITY BASED PROTECTION OFFERS COMPLETE SECURITY
AND SUBSTANTIAL FLEXIBILITY. @THE FORMER DERIVES FROM THE FACT THAT
CAPABILITIES CAN BE MANUFACTURED AND MODIFIED ONLY BY THE SYSTEM AND,
THEREFORE, BECOME UNFORGEABLE KEYS WITHOUT WHICH THE SYSTEM'S OBJECTS
CANNOT BE MANIPULATED. @THE FLEXIBILITY IS BASED ON THE SYSTEM'S
FREEDOM TO STORE WITHIN THE CAPABILITIES ALL THE INFORMATION WHICH IT
DEEMS NECESSARY IN ORDER TO ENFORCE CONTROLLED ACCESS TO THE VARIOUS
RESOURCES. @MOREOVER, RESOURCE SHARING CAN BE SIMPLIFIED GREATLY BY
ALLOWING A MORE OR LESS FREE POLICY IN THE COPYING AND DISTRIBUTION
OF CAPABILITIES.
$P
@THESE ARE PRECISELY THE PROTECTION AND SHARING REQUIREMENTS SOUGHT
FOR THE SUPPORT OF SYNCHRONISING PRIMITIVES AVAILABLE TO USER
PROCESSES.
$P
@THE VERSATILITY OF CAPABILITY BASED PROTECTION SYSTEMS IS A
FUNCTION OF THE SET OF OPERATIONS WHICH THE SYSTEM IS WILLING TO
PERFORM REGARDING THE CREATION AND MODIFICATION OF CAPABILITIES.
@CLEARLY, THE OPERATIONS ARE INTIMATELY RELATED WITH THE INFORMATION
CONTAINED IN THE CAPABILITIES. @IN THE PRESENT CHAPTER WE EXPOSE THE
GENERAL ASPECTS OF CAPABILITY BASED PROTECTION SYSTEMS IN THE FORM OF
A REVIEW OF SEVERAL SYSTEM DESIGNS, SOME OF WHICH HAVE BEEN
IMPLEMENTED [@FE74,@LA76,@NE72,@NE74,@RE74,@JO74, @WU74]. @THIS WILL
SERVE
TO IDENTIFY THE FEATURES WHICH CAN BE ADAPTED FOR OUR PURPOSES.
$P
@IN SECTIONS 2.1 AND 2.2, RESPECTIVELY, WE DELVE INTO THE FORMAT
AND INTGERITY OF CAPABILITIES. @THE SURVEY OF TYPE EXTENSION
FACILITIES OF SECTION 2.4 IS PRECEDED BY AN ANALYSIS OF THE DOMAIN
TYPE, ON WHICH TYPE EXTENSION IS BASED, OF SECTION 2.3. @WE CONCLUDE
THE CHAPTER WITH A PRELIMINARY VIEW OF THE OPERATIONS ON CAPABILITIES
REQUIRED TO SUPPORT TYPE EXTENSION.
$N
2.1.- .FORMAT .OF .CAPABILITIES.
$P2
@ACCORDING TO THE DESCRIPTION OF THE BEHAVIOUR OF A CAPABILITY
BASED PROTECTION SYSTEM PRESENTED IN SECTION 2.0, A PROCESS SEES ONLY
A COLLECTION OF CAPABILITIES. @WHEN A PROCESS WISHES TO ACCESS AN
OBJECT, IT PRESENTS TO THE PROTECTION SYSTEM A CAPABILITY, TOGETHER
WITH AN INDICATION ABOUT THE OPERATION IT WISHES TO PERFORM.
@THEREFORE, A CAPABILITY MUST CONVEY TO THE PROTECTION MECHANISM THE
FOLLOWING INFORMATION:
$A INDENT=2
$C-3 1) @THE IDENTIFIER OF THE OBJECT; THAT IS TO SAY, A NAME WHICH
DISTINGUISHES THE OBJECT FROM OTHER OBJECTS EXISTING IN THE
SYSTEM.
$B0
$C-3 2) @A SET OF ACCESS RIGHTS PERTAINING TO THE VARIOUS WAYS IN
WHICH
THE PARTICULAR OBJECT MAY BE ACCESSED.
$A INDENT=0
$P0
$B0
@THE PROTECTION MECHANISMS CAN THEN VERIFY THAT THE ACCESS RIGHTS
PERMIT THE REQUESTED OPERATION TO TAKE PLACE. @THE ACCESS RIGHTS OF
AN OBJECT WILL BE OUR FIRST TOPIC OF DISCUSSION.
$P
@ASSOCIATED WITH EVERY OBJECT IS A TYPE: @THE ATTRIBUTE WHICH
IDENTIFIES THE PHYSICAL AND LOGICAL CHARACTERISTICS OF THE OBJECT.
@AN INTRINSIC PROPERTY OF A GIVEN TYPE IS THE MEANINGFUL SET OF
OPERATIONS WHICH MAY BE PERFORMED ON AN OBJECT OF HAT TYPE.
$P
@EXAMPLES OF TWO DIFFERENT TYPES OF OBJECTS ARE A SEGMENT; I. E. A
COLLECTION OF MEMORY WORDS, AND A SEMAPHORE DATA SRUCTURE AS
DESCRIBED IN CHAPTER 1. @THE RESPECTIVE OPERATIONS DEFINED ON THESE
TYPES ARE: READ, WRITE, EXECUTE AND .P, .V, RESPECTIVELY.
$P
@IN A SYSTEM IN WHICH ALL THE TYPES AND HENCE ALL THE POSSIBLE
OPERATIONS DEFINED IN THE SYSTEM ARE KNOWN A PRIORI, ACCESS CONTROL
CAN BE ACCOMPLISHED WITH A SET OF BITS. @EACH BIT IS ASSOCIATED WITH
ONE OF THE POSSIBLE OPERATIONS DEFINED IN THE SYSTEM AND THIS WOULD
SUFFICE FOR THE PROTECTION MECHANISM TO VALIDATE ACCESS TO ANY TYPE
OF OBJECT.
$P

@IN THE EXAMPLES MENTIONED ABOVE, ACCESS RIGHTS COULD BE
IMPLEMENTED BY A BIT SEQUENCE OF THE FORM:
$B0
$A INDENT=2
$A NLS=1
V P E W R
$B0
0 0 0 1 1
$A INDENT=0
$A NLS=2
$B
WHERE A 1 ALLOWS AND A 0 FORBIDS THE CORRESPONDING ACCESS TO THE
OBJECT IN QUESTION.
$P
@THIS KIND OF ACCESS CONTROL IMPOSES A SEVERE LIMIT ON THE TOTAL
NUMBER OF TYPES WHICH CAN BE DEFINED IN THE SYSTEM. @IT IS SUITABLE
ONLY IN SYSTEMS CONSISTING OF A SMALL NUMBER OF PRE-DEFINED TYPES.
$P
@ONE PARTICULAR INCONVENIENCE OF THIS KIND OF ARRANGEMENT IS THAT
THE TYPE OF AN OBJECT CAN BE DETERMINED ONLY BY THE PRESENCE OF ONE
OR MORE NON-ZERO ACCESS BITS WITHIN THE PART OF THE ACCESS RIGHTS
FIELD PERTAINING TO THE OPERATIONS DEFINED ON THAT TYPE. @IN
PARTICULAR, IT WOULD BE IMPOSSIBLE TO DISCOVER THE TYPE OF AN OBJECT
WHOSE CAPABILITY DID NOT ALLOW ANY FORM OF ACCESS.
$P
@CONSIDER APPENDING A TYPE MARK TO THE ACCESS RIGHTS FIELD
DESCRIBED ABOVE. @THAT IS, AN ADDITIONAL FIELD CONTAINING A VALUE
WHICH IDENTIFIES UNAMBIGUOUSLY THE TYPE OF THE OBJECT. @THE TYPE
FIELD MAKES IT POSSIBLE TO IMPOSE A LIMIT ON THE SIZE OF THE ACCESS
RIGHTS FIELD SINCE THE FORMER INDICATES TO THE PROTECTION MECHANISM
THE MEANING OF THE ACCESS RIGHTS IN THE CAPABILITY. @ALTHOUGH THE
INCLUSION OF A TYPE FIELD INTRODUCES A CORRESPONDING INCREASE IN THE
SIZE OF THE CAPABILITY, IT ALSO INCREASES THE NUMBER OF DIFFERENT
TYPES OF OBJECTS WHICH CAN BE SUPPORTED BY THE PROTECTION MECHANISM -
A CONSIDERABLE ADVANTAGE IN A SYSTEM PROVIDING TYPE EXTENSION
FACILITIES. @NOTE THAT THE INCLUSION OF A T-BIT TYPE FIELD PERMITS
THE DEFINITION OF 2**T DISTINCT TYPES. @A BY PRODUCT OF THE INCREASE
OF THE SIZE OF CAPABILITIES IS THE CONVENIENCE OF BEING ABLE TO
DETERMINE THE TYPE OF AN OBJECT BY EXAMINING ITS CAPABILITY.
$P
@IN A SENSE, THE INCLUSION OF A TYPE FIELD MAKES IT POSSIBLE FOR
DIFFERENT TYPES OF OBJECTS TO SHARE THE SAME ACCESS BITS.
$P
@THE SIZE OF THE ACCESS RIGHTS FIELD STILL IMPOSES A LIMIT ON THE
MAXIMUM NUMBER OF OPERATIONS WHICH CAN BE DEFINED FOR ANY ONE TYPE.
@IN PRACTICE, THIS LIMITATION CAN BE SIDE-STEPED BY A SUITABLE
DECOMPOSITION OF THE TYPE INTO A COLLECTION OF COMPONENT TYPES. @THE
DETAILS WILL BE EXAMINED IN THE DISCUSSION ON TYPE EXTENSION.
@CLEARLY, UNLESS VARIABLE SIZED ACCESS RIGHTS FIELDS ARE
CONTEMPLATED,
A CERTAIN NUMBER OF BITS WILL BE WASTED IN ALL TYPES WHOSE NUMBER OF
OPERATIONS IS LESS THAN THE ALLOTTED MAXIMUM. @THIS CALCULATED WASTE
PROBABLY OUTWEIGHS THE COMPLICATIONS WHICH ARISE IN IMPLEMENTING
VARIABLE SIZE CAPABILITIES.
$V0
$P
@A CAPABILITY WIH THE THREE FIELDS MENTIONED SO FAR IS SHOWN IN
FIGURE 2.1-1(A). @WE NOW PROCEED WITH A CLOSER SCRUTINY OF THE
IDENTIFIER FIELD.
$P
@FOLLOWING THE VERIFICATION OF TYPE AND ACCESS RIGHTS, IT IS
NECESSARY TO LOCATE THE PHYSICAL REPRESENTATION OF THE OBJECT WHICH
THE OPERATION DESIRES TO ACCESS; THE IDENTIFIER FIELD FULFILLS THIS
NEED. @IT IS POSSIBLE TO USE THE LOCATION OF THE OBJECT (E. G. THE
STARTING ADDRESS OF A SEGMENT OR OF THE SEMAPHORE DATA STRUCTURES) AS
ITS UNIQUE IDENTIFIER SINCE IT IS NECESSARILY DISTINCT FROM THAT OF
EVERY OTHER OBJECT. @HOWEVER, IN ORDER TO FACILITATE THE RELOCATION
OF OBJECTS, IT IS DESIRABLE TO SEPARATE THE OBJECT'S PHYSICAL ADDRESS
FROM THE IDENTIFIER CONTAINED IN THE OBJECT'S CAPABILITY. @THIS IS
PARTICULARLY IMPORTANT WHEN RESOURCE SHARING IS ACHIEVED BY MEANS OF
A GREATER OR LESSER FREEDOM IN THE PRODUCTION AND DISTRIBUTION OF
COPIES OF THE CAPABILITY FOR THE SHARED RESOURCE. @IN MOST SYSTEMS,
THIS SEPARATION IS ACCOMPLISHED BY PLACING THE UNIQUE NAME OF EVERY
OBJECT WITHIN ITS CAPABILITY AND KEEPING THE ASSOCIATION OF THE
OBJECT'S IDENTIFIER WITH ITS PHYSICAL LOCATION IN A GLOBAL SYSTEM
DATA BASE. @THE DATA BASE HAS BEEN CALLED @CAPABILITY @TABLE [@EN74],
@GLOBAL @SYMBOL @TABLE [@WU74], @MASTER @OBJECT @TABLE [@LA76], AND
@MASTER
@SEGMENT @TABLE [@NE74] AMONG OTHER NAMES. @WE WILL CALL IT THE @MAP
[@RE74]. @PART (B) OF FIGURE 2.1.1 SHOWS A POSSIBLE @MAP ENTRY.
$P
@THE ADDITIONAL FIELD LABELLED 'LENGTH' IS USED IN CONNECTION WITH
CERTAIN TYPES OF OBJECTS, E. G. SEGMENTS. @IT ENABLES THE PROTECTION
MECHANISM TO PERFORM A BOUNDS CHECK ON THE PROGRAM GENERATED ADDRESS.
@IT IS IMPORTANT TO NOTE THAT THE @MAP ENTRY FOR A GIVEN OBJECT IS
UNIQUE; IN CONTRAST, THE SYSTEM MAY NOT KNOW THE NUMBER OF COPIES OF
THE OBJECT'S CAPABILITY.
$P
@THE JOB OF THE PROTECTION MECHANISM HAS BEEN AUGMENTED. @IN
ADDITION TO THE VERIFICATION OF ACCESS RIGHTS IT MUST RETRIEVE THE
@MAP ENTRY FOR THE OBJECT IN ORDER TO DETERMINE THE PHYSICAL
LOCATION.
@MOREOVER, THE SYSTEM MUST MAINTAIN THE @MAP. @THE NUMBER OF OBJECTS
WHICH HAVE BEEN CREATED IN THE SYSTEM WILL PROBABLY BE MUCH LARGER
THAN THE NUMBER OF OBJECTS WHICH ARE USED DURING AN ARBITRARY PERIOD
OF TIME. @HENCE, THE @MAP MUST BE STORED IN A HIGHLY PRIVILEGED
AUXILIARY STORAGE DEVICE. @THE PROTECTION MECHANISM WILL RETRIEVE
FROM THAT DEVICE ONLY THOSE ENTRIES CORRESPONDING TO THE CURRENTLY
USED CAPABILITIES AND KEEP THEM IN A GLOBAL HASH TABLE. @THE REASON
FOR REPRODUCING THE OBJECT'S IDENTIFIER IN THE @MAP ENTRY IS NOW
CLEAR. @TO USE A SIMPLE POINTER FROM THE CAPABILITY TO A UNIQUE SLOT
WITHIN THE @MAP AS THE OBJECT'S UNIQUE NAME WOULD LIMIT THE SYSTEM'S
FREEDOM IN THE ADMINISTRATION OF THE @MAP. @IN THE INTEREST OF
EFFICIENCY, IT WILL PROBABLY BE NECESSARY TO MAKE USE OF AN
ASSOCIATIVE MEMORY TO ACCELERATE THE CORRELATION OF THE MOST RECENTLY
USED ENTRIES.
$P
@THE DESTRUCTION OF OBJECTS, IN CONJUNCTION WITH THE FREE
COPYABILITY OF CAPABILITIES IMPOSES THE REQUIREMENT OF UNIVERSAL
UNIQUENESS OF OBJECT NAMES. @THAT IS TO SAY, AN OBJECT'S IDENTIFIER
MUST BE DISTINCT FROM THE IDENTIFIER OF EVERY OTHER OBJECT PAST,
PRESENT OR FUTURE EXISTING IN THE SYSTEM. @THE REQUIREMENT IS
EXPLAINED IN THE FOLLOWING OBSERVATIONS.
$P
@WHEN AN OBJECT IS DESTROYED, ITS CORRESPONDING @MAP ENTRY CAN BE
REMOVED. @THE DELETION OF ALL THE COPIES OF THE CAPABILITY REFERRING
TO THAT ENTRY WOULD HAVE TO BE BASED ON A FRAGILE AND EXPENSIVE
STRUCTURE OF BACK POINTERS OR ON A MASSIVE SEARCH OF ALL CAPABILITIES
IN THE SYSTEM. @BARRING THOSE ALTERNATIVES, THE SYSTEM MUST PREVENT
OBSOLETE CAPABILITIES FROM AUTHORISING ACCESS TO ANY OBJECT. @THIS
CAN BE ACCOMPLISHED BY PROVIDING UNIVERSALLY UNIQUE NAMES FOR
OBJECTS. @THE IMPLEMENTATION CONSISTS IN PROVIDING A GENERATOR OF AN
ORDERED SEQUENCE OF UNIQUE LONG INTEGERS. @USUALLY, THE IDENTIFIER
FIELD IS DEFINED AS A SUFFICIENTLY LARGE INTEGER TO ALLOW AN
INEXHAUSTIBLE NUMBER OF OBJECTS TO BE CREATED. @THAT IS TO SAY, THE
NAME SPACE SHOULD BE LARGE ENOUGH SO THAT IT CAN ACCOMODATE MORE
OBJECTS THAN THE SYSTEM'S LIFE-TIME REQUIRES. @FOR EXAMPLE, IF A NEW
NAME IS GENERATED EVERY MILLISECOND, A 32 BIT NAME FIELD ALLOWS THE
SYSTEM TO RUN CONTINUOUSLY DURING APPROXIMATELY 40 DAYS. @NOTE THAT
IT IS IMPERATIVE TO GUARANTEE THAT THE NAME GENERATOR PRODUCES NEW
NAMES EVEN AFTER A SYSTEM FAILURE.
$P
@A CONVERSE PROBLEM ARISES WHEN WHEN ALL THE COPIES OF THE
CAPABILITY FOR AN OBJECT ARE DESTROYED. @THE SYSTEM IS FACED WITH THE
NEED OF RECOVERING THE PHYSICAL RESOURCES OCCUPIED BY THE
REPRESENTATION OF THE OBJECT, INCLUDING THE @MAP ENTRY. @THIS 'LOST
OBJECT' PROBLEM IS ANALOGOUS TO THE RECOVERY OF UNUSED CELLS IN LIST
PROCESSING SYSTEMS [@KN68,@ST75].
$P
@ONE OF TWO TECHNIQUES HAVE BEEN USED TO RECOVER LOST OBJECTS:
@REFERENCE COUNT AND GARBAGE COLLECTION. @THE FIRST ONE REQUIRES THE
INCLUSION, IN THE MAP ENTRY, OF A COUNTER OF THE NUMBER OF EXISTING
COPIES OF CAPABILITIES FOR AN OBJECT. @THE COUNTER IS INITIALISED TO
1 AND INCREMENTED OF DECREMENTED WHEN A CAPABILITY IS COPIED OR
ERASED. @THE OBJECT CAN BE DESTROYED WHEN THE COUNTER REACHES THE
VALUE ZERO. @IN ADDITION TO THE OVERHEAD OF MAINTAINING THE VALUE OF
THE REFERENCE COUNT AND INCLUDING YET ANOTHER FIELD IN THE
CAPABILITY, THE SCHEME DOES NOT LEND ITSELF TO THE MANIPULATION OF
SELF-REFERENCING DATA STRUCTURES. @HOWEVER, THE LAST OF THESE POBLEMS
IS NOT CRUCIAL IN THE CASE OF CAPABILITY SYSTEMS. @THE APPROACH HAS
BEEN IMPLEMENTED IN ONE EXISTING SYSTEM [@WU74]. @GARBAGE COLLECTION
CONSISTS IN SCANNING ALL CAPABILITIES AND MARKING THE MAP ENTRY OF
EVERY OBJECT WHICH CAN BE REACHED. @A SUBSEQUENT STAGE IS IN CHARGE
OF RECOVERING ALL UNMARKED OBJECTS. @THE GARBAGE COLLECTION APPROACH
ALLOWS THE RECOVERY OF SELF-REFERENCING DATA STRUCTURES AND DOES NOT
IMPOSE A LIMIT ON THE NUMBER OF CAPABILITIES WHICH CAN REFERENCE A
GIVEN OBJECT. @ALSO, THE MARKER NEED NOT BE LARGER THAN ONE OR TWO
BITS, IN CONTRAST WITH THE REFERENCE COUNTER WHICH MUST BE BIG ENOUGH
TO ALLOW A CONVENIENT NUMBER OF COPIES OF CAPABILITIES FOR AN OBJECT.
$P
@IN A MULTIPROCESSOR ENVIRONMENT THE REFERENCE COUNT APPROACH
INTRODUCES A SERIOUS PROBLEM: @EVERY EXECUTION OF A COPY/DELETE
CAPABILITY OPERATION DEMANDS EXCLUSIVE ACCESS OF THE CORRESPONDING
MAP ENTRY. @IN CONTRAST, IT CAN BE EXPECTED THAT GARBAGE COLLECTION
REQUIRES LESS FREQUENT EXCLUSIVE ACCESS TO MAP ENTRIES. @IN
PARTICULAR, THE MARK STAGE OF A GARBAGE COLLECTOR CAN PROCEED
CONCURRENTLY, AND WITHOUT MAJOR INTERFERENCE, WITH THE USE OF MAP
ENTRIES [@ST75]. @IN GENERAL, IT CAN BE SAID THAT GARBAGE COLLECTION
AFFORDS A MORE EFFICIENT UTILISATION OF CONCURRENT PROCESSING; THE
TECHNIQUE IS THEREFORE MORE ADEQUATE FOR OUR PURPOSES. @NEVERTHELESS,
IT MUST BE POINTED OUT THAT IT IS EXTREMELY DIFFICULT TO ATTEMPT TO
GRANT EXCLUSIVE ACCESS TO THE MAP (OR SUBSTANTIAL PARTS THEREOF)
STRICTLY AND ONLY WHEN LOGICAL CONSIDERATIONS DEMAND EXCLUSIVENESS.
@THE DIFFICULTY OF CONSTRUCTING ALGORITHMS TO ACHIEVE SELECTIVE
ACCESS
TO RESOURCES HAS BEEN MADE CLEAR ONLY TOO OFTEN [@PA75,@CO71,@ST75].
$N
2.2.- .INTEGRITY .OF .CAPABILITIES.
$P2
@THE INTEGRITY OF CAPABILITIES IS CRUCIAL TO THE PROTECTION
MECHANISM. @A PROCESS CAPABLE OF FORGING OR ALTERING A CAPABILITY
COULD OBTAIN ACCESS TO ANY OBJECT; AS A RESULT, THE PROTECTION
MECHANISM WOULD BECOME SENSELESS.
$P
@A HIGHLY PRIVILEGED PART OF THE SYSTEM CALLED THE KERNEL, NUCLEUS,
OF BASE-LEVEL SYSTEM BY DIFFERENT AUTHORS [@DE66,@WU74,@RE74] IS THE
SOLE COMPONENT AUTHORIZED TO CREATE AND MODIFY CAPABILITIES. @ALL
OTHER COMPONENTS OF THE SYSTEM, INCLUDING THE OPERATING SYSTEM
PROGRAMS, ARE FORCED TO ADHERE TO THE RESTRICTIONS IMPOSED BY THE
KERNEL.
$P
@THERE ARE TWO TECHNIQUES TO IMPLEMENT THE INTEGRITY OF
CAPABILITIES: @TAGGED STORAGE AND @SEGMENTED STORAGE.
$P
@IN THE TAGGED STORAGE APPROACH, EVERY MEMORY WORD CONTAINS ONE OR
MORE 'TAG' BITS WHICH DIFFERENTIATE CAPABILITIES FROM NORMAL DATA.
@THIS ALLOWS THE DEFINITION OF SPECIAL MACHINE INSTRUCTIONS TO
MANIPULATE ITEMS WHICH CONTAIN DIFFERENT TAGS. @THUS, EVERY MEMORY
WORD CONTAINS A TYPE FIELD AND THE PROCESSOR PERFORMS A TYPE CHECK ON
THE OPERAND OF EVERY INSTRUCTION. @THE TYPE CHECK CONSISTS IN
VERIFYING THAT THE TAG FIELD IN THE MEMORY WORD BE CONSISTENT WITH
THE INSTRUCTION TYPE.
$P
@IN THE SEGMENTED STORAGE APPROACH CAPABILITIES AND NORMAL DATA
RESIDE IN DIFFERENT TYPES OF SEGMENTS. @THAT IS TO SAY, MEMORY
SEGMENTS CONTAINING CAPABILITIES ARE TREATED AS DIFFERENT TYPES OF
OBJECTS FROM THOSE CONTAINING NORMAL DATA. @THE INTEGRITY OF
CAPABILITIES IS GUARANTEED BY MEANS OF THE APPROPIATE DEFINITION OF
THE OPERATIONS FOR EACH TYPE OF OBJECT. @THE TWO TECHNIQUES ARE
EQUIVALENT IN THE SENSE THAT BOTH GUARANTEE THE INTEGRITY OF
CAPABILITIES.
$P
@TAGGED STORAGE IS BY FAR THE MORE CONVENIENT OF THE TWO TECHNIQUES
SINCE IT ALLOWS DATA AND CAPABILITIES TO INTERTWINE FREELY IN THE
SAME SEGMENTS. @UNFORTUNATELY, IT DEMANDS CONSIDERABLY MORE HARDWARE
SUPPORT THAN ITS COUNTERPART. @IN A SENSE, TAGGED STORAGE CONSISTS IN
THE HARDWARE IMPLEMENTATION OF A MICRO CAPABILITIY SYSTEM; THE MICRO
CAPABILITIES BEING THE TAGS IN THE MEMORY WORDS. @THE KERNEL IS
IMPLEMENTED ON TOP OF THIS SYSTEM. @THE @BURROUGHS AND @PLESSEY 250
ARE
THE ONLY COMMERCIALLY AVAILABLE MACHINES WHICH OFFER TAGGED STORAGE;
ONLY THE LATTER IS A CAPABILITY SYSTEM [@IL68,@EN74]. @THE FOLLOWING
IS
A VERY BRIEF EXPOSITION OF SOME ASPECTS OF TAGGED STORAGE OF
CAPABILITIES. @FOR EXTENSIVE PRESENTATIONS OF THE TOPIC SEE
[@FE73,@RE74].
$P
@THE RESPECTIVE SIZES OF CAPABILITIES AND THE ELEMENTARY
ADDRESSABLE ITEMS (WORDS,BYTES) INFLUENCES THE NUMBER OF TAG BITS
WHICH MUST BE RESERVED IN EACH ITEM. @THE CONSIDERATION IS IMPORTANT
BECAUSE OF THE TENDENCY OF DEFINING SMALL ITEMS IN CURRENT
ARCHITECTURES. @THE TENDENCY IS BASED ON THE OBSERVATION THAT THE
COST OF ADDRESSING; I$.E. THE SIZE OF A MEMORY ADDRESS GROWS
LOGARITHMICALLY WITH DECREASING ITEM SIZE. @IN CONTRAST, THE COST OF
TAGGING GROWS LINEARLY. @IF THE SIZE OF A CAPABILITY IS NOT GREATER
THAN THAT OF AN ITEM, ONE TAG BIT IS SUFFICIENT TO DIFFERENTIATE
BETWEEN DATA AND CAPABILITIES. @IF THIS IS NOT THE CASE, MORE THAN
ONE TAG BIT IS REQUIRED IN ORDER TO PREVENT ACCESSING THE MIDDLE OF A
CAPABILITY. @ALTERNATIVELY, CAPABILITY ADDRESSES CAN BE DEFINED TO
CONFORM WITH 'CAPABILITY BOUNDARIES'. @THAT IS, THE ADDRESS OF A
CAPABILITY MUST BE A MULTIPLE OF N, N BEING THE SIZE, IN ITEMS, OF A
CAPABILITY. @THIS, HOWEVER, INTRODUCES INCONVENIENCES IN THE
MANIPULATION OF CAPABILITIES. @THE PROBLEMS ARE INCREASED IF IT IS
DESIRED TO SUPPORT VARIABLE SIZED CAPABILITIES. @IN SHORT, IT CAN BE
SAID THAT TECHNICAL DIFFICULTIES ARE THE LIMITING FACTOR IN THE USE
OF TAGGED ARCHITECHTURES [@FA74].
$P
@IN SPITE OF THE ADVANTAGES OF TAGGED STORAGE, PRACTICAL
CONSIDERATIONS HAVE INFLUENCED THE SELECTION OF THE SEGMENTED SCHEME
FOR OUR CAPABILITY SYSTEM. @THE DESIGN IS INTENDED TO BE IMPLEMENTED
IN A MODIFIED HALF WORD (16 BIT) ADDRESSABLE MACHINE [@IN71]. @ONE OF
THE PRESSING CONSTRAINTS IS TO AVOID EXCESSIVE MODIFICATION OF THE
HOST MACHINE.
$P
@HEREINAFTER, WE ASSUME THE EXISTENCE OF TWO TYPES OF OBJECTS: @THE
@NORMAL SEGMENT TYPE OR @N-SEG AND THE @CAPABILITY SEGMENT TYPE OR
@C-SEG. @INDIVIDUAL INSTANCES OF OBJECTS OF THOSE TYPES CONTAIN,
RESPECTIVELY, NORMAL DATA AND CAPABILITIES. @THE OPERATIONS DEFINED
ON OBJECTS OF TYPE @N-SEG ARE READ, WRITE AND EXECUTE. @THE
DEFINITION
OF OPERATIONS ON THE @C-SEG TYPE IS ONE OF THE MAIN PURSUITS OF THE
PRESENT WORK.
$N
2.3.- .PROTECTION .DOMAINS.
$P2
@SO FAR, CAPABILITIES HAVE BEEN DESCRIBED ONLY AS TOOLS TO CONTROL
ACCESS TO PARTICULAR INSTANCES OF THE VARIOUS SYSTEM OBJECTS. @AN
ESSENTIAL PART OF PROTECTION MECHANISMS FOR MULTIPROGRAMMING SYSTEMS
IS THE CONGLOMERATION OF FACILITIES WHICH ENABLE THE CONTROL OF THE
ENVIRONMENT OF EXECUTION OF PROCESES.
$P
@IN ABSTRACT TERMS, THE ENVIRONMENT OF A PROCESS IS DEFINED AS THE
SET OF OBJECTS WHICH CAN BE ACCESSED BY THE PROCESS AT A GIVEN TIME.
@IN A CAPABILITY SYSTEM, THIS CAN BE TRANSLATED AS THE COLLECTION OF
CAPABILITIES WHICH A PROCESS IS CAPABLE OF PRESENTING TO THE
PROTECTION MECHANISM.
$P
@THE ENVIRONMENT OF A PROCESS CAN BE EASILY CONTROLLED BY ENCLOSING
A SET OF CAPABILITIES WITHIN A SPECIAL TYPE OF OBJECT AND DEFINING
THE TRANSITION RULES OF THE PROCESS IN SUCH A WAY THAT IT CAN ADDRESS
( I. E. PRESENT TO THE PROTECTION MECHANISM) ONLY THOSE CAPABILITIES
WHICH ARE ENCLOSED WITHIN ONE OF THE OBJECTS OF THAT SPECIAL TYPE.
$P
@FOR CONCISENESS, WE EMPLOY THE TERM 'DOMAIN' INSTEAD OF THE
LENGTHY 'OBJECT OF TYPE DOMAIN'. @THE TERM 'PROTECTED PROCEDURE' IS
OFTEN USED IN THE LITERATURE TO DENOTE THE PROTECTION REGIMES OF
PROCESSES [@WU74,@NE74].
$P
@A PROCESS IS SAID TO BE %BOUND TO OR %EXECUTING %IN ITS %CURRENT
DOMAIN WHEN IT EXECUTES INSTRUCTIONS WHICH ADDRESS THE CAPABILITIES
FOR THE OBJECTS CONTAINED WITHIN THE DOMAIN IN QUESTION. @IT IS
IMPORTANT TO NOTE THAT THE INSTRUCTIONS DIRECTING THE EXECUTION OF A
PROCESS ARE STORED WITHIN, AND THEREFORE MUST BE FETCHED FROM, A
PARTICULAR SYSTEM OBJECT. @SINCE THE PROCESS CAN ONLY ACCESS OBJECTS
WHOSE CAPABILITIES ARE ENCLOSED IN THE DOMAIN IN WHICH THE PROCESS
EXECUTES, IT FOLLOWS THAT THE INSTRUCTION STREAM ORIGINATES FROM THAT
DOMAIN. @AGAIN, FOR THE SAKE OF BREVITY, WE WILL TALK ABOUT DOMAINS
AS IF THEY WERE ACTIVE ENTITIES ALTHOUGH, STRICTLY, WE INTEND TO
REFER TO THE PROCESS(ES) WHICH EXECUTE IN THE DOMAIN.
$P
@ASSOCIATED WITH EVERY DOMAIN IS A LIST OF CAPABILIIES WHICH
DEFINES THE TOTALITY OF OBJECTS WHICH CAN BE ACCESSED BY ANY PROCESS
BOUND TO THE DOMAIN. @SOME OF THE NAMES WHICH HAVE BEEN GIVEN TO THIS
LIST ARE: @CAPABILITY @LIST (@C-LIST) [@DE66], @LOCAL @NAME @SPACE
.(LNS)
[@JO74,@WU74] AND @IMPLICIT @SEGMENT (@I-SEG) [@RE74]. @WE HAVE
CHOSEN TO
EMPLOY THE LAST OF THEM.
$P
@THE STRUCTURE OF AN OBJECT OF TYPE DOMAIN IS DEPICTED IN FIGURE
2.3-1. @IT CONSISTS OF A CAPABILITY CONTAINING THE UNIQUE .ID FIELD,
THE 'DOMAIN' TYPE MARK, A SET OF ACCESS RIGHTS AND A POINTER TO (THE
LOCATION OF) THE @I-SEG OF THE DOMAIN. @THE @I-SEG ITSELF IS A MEMORY
SEGMENT CONTAINING THE LIST OF CAPABILITIES LABELLED .C1, .C2, $.$.$.,
.CN
WHICH CAN BE ADDRESSED BY THE DOMAIN (I. E., BY A PROCESS OR
PROCESSES BOUND TO THE DOMAIN).
$P
$V0
@DOMAINS ARE THE LOGICAL ENTITIES WHICH ENABLE THE PROTECTION
MECHANISM TO CONTROL THE HARMONIOUS SHARING OF SYSTEM RESOURCES BY
THE VARIOUS PROCESSES. @CONSEQUENTLY, THE RELATIONSHIP BETWEEN
PROCESSES AND DOMAINS IS VITALLY IMPORTANT. @THE CHARACTERISATION OF
DOMAINS AS PASSIVE OBJECTS IS IMPRECISE IN THE SENSE THAT DOMAINS
PLAY AN ACTIVE ROLE IN THE CONTROL OF THE ACTIVITIES OF PROCESSES.
@IN PRINCIPLE, HOWEVER, ALLOWING A PROCESS TO CHANGE ITS PROTECTION
REGIME IS MERELY A MATTER OF DEFINING THE OPERATIONS ON OBJECTS OF
TYPE DOMAIN. @BECAUSE OF THE FACT THAT DOMAINS ARE OBJECTS, THE RIGHT
OF A PROCESS TO ACCESS A DOMAIN CAN BE AUTHORISED BY A CAPABILITY
(FOR AN OBJECT OF TYPE DOMAIN) STORED WITHIN THE @I-SEG OF THE
PROCESS' CURRENT DOMAIN.
$P
@THE OPERATIONS DEFINED ON DOMAINS ARE: DOMAIN CALL OR %ENTER DOMAIN
AND DOMAIN RETURN OR %EXIT DOMAIN. @THE OPERATIONS ARE SIMILAR TO THE
SUBROUTINE CALL AND RETURN OPERATIONS OF PROGRAMMING LANGUAGES.
$P
@THE %ENTER OPERATION INCLUDES AN %EXIT-CURRENT-DOMAIN OPERATION.
@OTHERWISE A PROCESS COULD HAVE THE POWER TO ADDRESS CAPABILITIES
FROM
THE @I-SEG'S OF TWO DIFFERENT DOMAINS. @THE %EXIT OPERATION RETURNS
CONTROL TO THE DOMAIN FROM WHICH THE %ENTER OPERATION WHICH CAUSED
THE
ACTIVATION OF THE CURRENT DOMAIN WAS ISSUED. @A DOMAIN WHICH EXECUTES
AN %ENTER OPERATION IS SAID TO REMAIN DORMANT OR INACTIVE UNTIL THE
CORRESPONDING %EXIT OPERATION IS EXECUTED. @AN %EXIT OPERATION CAUSES
THE COMPLETE DISASSOCIATION OF THE PROCESS FROM THE DOMAIN IN
QUESTION. @IN CONTRAST, A PROCESS WHICH EXECUTES AN %ENTER OPERATION
IS SAID TO LEAVE THE CURRENT DOMAIN IN AN INACTIVE STATE; IN THAT
CASE WE SAY THAT THE DOMAIN IS A DORMANT DOMAIN OF THE PROCESS.
$P
@THE CHANGE IN THE ENVIRONMENT OF A PROCESS IMPLICIT IN THE DOMAIN
CALL OPERATION AMOUNTS TO A REDEFINITION OF THE @I-SEG WHICH CAN BE
ACCESSED BY THE PROCESS. @THE PROTECTION MECHANISM MUST SAVE THE
CAPABILITY FOR THE CALLING DOMAIN AND THE 'TEXTUAL INDEX' [@DI71] OF
THE DOMAIN AT THE POINT OF CALL IN ORDER TO BE ABLE TO RESTORE THE
OLD PROTECTION REGIME OF THE PROCESS WHEN AN %EXIT OPERATION IS
ISSUED
FROM THE CALLED DOMAIN. @STRICTLY, A DOMAIN CAN EXECUTE AN %EXIT
OPERATION ONLY IF IT POSSESSES A CAPABILITY FOR THE DOMAIN TO WHICH
IT WISHES TO RETURN. @THUS, IN PRINCIPLE, THE PROTECTION MECHANISM
SHOULD STORE THE CAPABILITY FOR THE CALLING DOMAIN AND THE TEXTUAL
INDEX AT THE TIME OF CALL INTO INTO A SET OF SLOTS OF THE CALLED
DOMAIN'S @I-SEG. @THIS 'DOMAIN RETURN ADDRESS' CAN BE VIEWED AS A
(CAPABILITY) PARAMETER PASSED BY THE PROTECTION MECHANISM FROM THE
CALLING TO THE CALLED DOMAIN. @THE ACTIVITY FALLS INTO THE MORE
GENERAL CATEGORY OF @INTER-DOMAIN @COMMUNICATION .(IDC) MECHANISMS:
@THE
CONGLOMERATION OF FACILITIES NEEDED TO SUPPORT THE OPERATIONS ON
DOMAINS AND THE PASSING OF PARAMETERS BETWEEN THEM.
$P
@WE WILL ANALYSE PARAMETER PASSING IN CONJUNCTION WITH THE POLICY
FOR THE DISTRIBUTION OF CAPABILITIES FOR OBJECTS OF TYPE DOMAIN,
BECAUSE BOTH ASPECTS ARE INTIMATELY RELATED.
$P
@ASSUME THAT THE KERNEL SUPPLIES AN OPERATION OF THE FORM:
$B0
$T2
@X = CREATE DOMAIN(@L@I@S@T)
$B0
WHERE .LIST IS THE CAPABILITY FOR AN OBJECT, E. G. A @C-SEG,
CONTAINING
A LIST .C1, .C2, $.$.$., .CN OF CAPABILITIES. @THE KERNEL USES THE
SET OF
CAPABILITIES TO CREATE A NEW OBJECT OF TYPE DOMAIN AND RETURNS THE
NEWLY CREATED CAPABILITY TO THE CALLER. @THE STRUCTURE OF THE NEW
OBJECT IS SHOWN IN FIGURE 2.3.1. @NOW, SUPPOSE THAT A PROCESS IS
BOUND TO A GIVEN DOMAIN, SAY .A, AND WISHES TO CREATE A NEW DOMAIN
WHICH WE WILL CALL .B. @THERE ARE TWO WAYS TO GIVE @B THE PRIVILEGE
TO
ACCESS A THIRD DOMAIN, SAY .Z. A) THE CAPABILITY FOR @Z IS INCLUDED
BY
@A IN THE LIST OF CAPABILITIES TO BE DEPOSITED INTO @B'S @I-SEG AND
B)
@THE CAPABILITY FOR @Z WILL BE PASSED TO @B AS A PARAMETER AT THE
TIME
IT IS ENTERED BY SOME PROCESS. @CASE A) IMPLIES THAT DOMAIN @A
POSSESSES A COPY OF THE CAPABILITY FOR .Z. @FOR SIMPLICITY, ASSUME
THAT THE PROTECTION MECHANISM FORBIDS CASE B). @DOMAIN @A HAS A
CAPABILITY FOR @Z BY VIRTUE OF HAVING CREATED IT AT AN EARLIER TIME
OR
BECAUSE THE CREATOR OF @A (A PROCESS BOUND TO SOME OTHER DOMAIN)
REQUESTED THE KERNEL TO INCLUDE THE CAPABILITY FOR @Z IN THE @I-SEG
OF
.A.
$P
@CONSIDER THE SIMPLER SITUATION: @A IS THE CREATOR OF DOMAIN .Z. @IF
WE ASSUME THAT DOMAIN @B IS ENTITLED TO USE THE CREATE-DOMAIN KERNEL
FUNCTION AND THAT THE CREATOR OF @B (I. E. DOMAIN .A) DID NOT IMPOSE
ANY RESTRICTION ON THE USE OF THE CAPABILITY FOR .Z, THEN @B CAN
SPECIFY THAT THE CAPABILITY FOR @Z BE INCLUDED IN THE @I-SEG OF ANY
NEW
DOMAIN. @IN CONCLUSION, BARRING A NUMBER OF VERY STRONG RESTRICTIONS
(E. G. CERTAIN CAPABILITIES FOR DOMAINS CANNOT BE SPECIFIED AS
PARAMETERS TO THE CREATE-DOMAIN OPRATION) THE CREATOR OF DOMAIN @Z
CANNOT KNOW THE IDENTITY OF THE DOMAINS FROM WHICH %ENTER .(Z) WILL
BE
ISSUED. @THEREFORE, THE PARAMETERS OF A DOMAIN CALL, INCLUDING THE
DOMAIN RETURN ADDRESS, MUST BE DEPOSITED WITHIN SOME SLOTS OF THE
@I-SEG OF THE CALLED DOMAIN. @THE INTERESTING THING TO NOTICE IS THAT
PARAMETER PASSING DEMANDS THAT DOMAINS HAVE SOME KIND OF ACCESS,
ALBEIT VERY RESTRICTED, TO THE @I-SEG'S OF OTHER DOMAINS. @THE
RESTRICTED ACCESS MUST BE LEFT COMPLETELY IN THE HANDS OF THE
PROTECTION MECHANISM BY MEANS OF DEFINING THE %ENTER KERNEL OPERATION
AS:
$B0
$T2
%ENTER (<DOMAIN> , <ARGUMENT>)
$B0
WHERE <DOMAIN> IS THE CAPABILITY FOR THE DOMAIN TO BE ENTERED AND
<ARGUMENT> IS A CAPABILITY FOR AN OBJECT, E. G. A @C-SEG, CONTAINING
THE LIST OF CAPABILITIES WHICH THE CALLER WISHES TO PASS TO THE
CALLEE.
$P
@FURTHER COMPLICATIONS ARISE IF CAPABILITIES FOR DOMAINS CAN BE
TRANSFERRED BETWEEN PROCESSES. @IT IS NOW NECESSARY FOR THE
PROTECTION MECHANISM TO ACCOMMODATE THE PARAMETERS OF THE TWO
POSSIBLY SIMULTANEOUS %ENTER OPERATIONS ORIGINATED FROM TWO DIFFERENT
PROCESSES.
$P
@THE PROTECTION MECHANISM MUST CATER FOR TWO DIFFICULTIES.
@FIRSTLY, THE PARAMETERS RELATING TO EACH OF THE TWO %ENTER
OPERATIONS
MUST ARRIVE AT THE SINGLE SET OF PARAMETER SLOTS OF THE @I-SEG OF THE
TARGET DOMAIN IN STRICT SEQUENCE. @ONE OF THE TWO PROCESES ATTEMPTING
TO ENTER THE DOMAIN WOULD HAVE TO WAIT UNTIL THE PROCESS WHICH
SUCCEEDED IN ITS ATTEMPT REMOVES THE PARAMETERS AND RELEASES CONTROL
OF THE CRITICAL SECTION. @MOREOVER, IT IS STILL NECESSARY FOR THE
PROTECTION MECHANISM TO OFFER FACILITIES TO PROTECT THE PARAMETERS OF
ONE PROCESS FROM ACCESS BY THE OTHER PROCESSES IN THE DOMAIN. @AN
OBVIOUS WAY TO IMPLEMENT THIS PROTECTION IS TO IMPLEMENT EVERY DOMAIN
AS A CRITICAL SECTION WHICH CAN BE ACTIVATED BY AT MOST ONE PROCESS
AT ANY GIVEN TIME. @HOWEVER, ALL THESE PSEUDO-SOLUTIONS RESTRICT
CONCURRENT EXECUTION EVEN WHEN THE ACTIVITIES OF THE VARIOUS
PROCESSES IN THE DOMAIN ARE LOGICALLY NON-INTERFERING.
$P
@A SPECIES OF LOAD TIME DEFINITION OF THE COMMUNICATION LINKS
BETWEEN DOMAINS PRESENTS SEVERAL PROBLEMS. @IN ORDER TO BE CONSISTENT
WITH THE PROPOSED DEFINITION OF THE BINDING OF PROCESSES TO DOMAINS,
THE CREATION OF A PROCESS MUST BE SIMULTANEOUS WITH THE BINDING OF
THE PROCESS TO A DOMAIN. @THEREFORE, IN PRINCIPLE, LOAD TIME
COINCIDES WITH PROCESS CREATION TIME. @TO AVOID FURTHER
COMPLICATIONS, SUPPOSE DOMAINS CANNOT BE ENTERED RECURSIVELY AND THAT
THE PROCESS CANNOT CREATE NEW DOMAINS. @THE INITIAL DOMAIN OF A
PROCESS CONTAINS THE SET OF CAPABILITIES FOR DOMAINS WHICH CAN BE
ENTERED BY THE PROCESS DURING ITS LIFE-TIME. @FIGURE 2.3-2 SHOWS A
POSSIBLE DOMAIN STRUCTURE OF A PROCESS; NODES REPRESENT DOMAINS AND
AN ARC ORIGINATING FROM A NODE INDICATES THAT THE DOMAIN'S @I-SEG
CONTAINS A CAPABILITY TO ENABLE THE PROCESS TO ENTER THE SUCCESSOR
DOMAIN.
$P
$V0
@IN THE CASE OF A PROCESS CREATED ON BEHALF OF AN INTERACTIVE USER,
IT IS REASONABLE TO ENCLOSE THE DICTIONARY OF THE USER'S PRIVATE
OBJECTS WITHIN THE INITIAL DOMAIN OF THE PROCESS. @HOWEVER, THIS
WOULD IMPLY THAT THE KERNEL SHOULD LINK EVERY POSSSIBLE DOMAIN WHICH
THE USER MIGHT ATTEMPT TO REACH DURING THE SESSION. @WE CAN CONCEIVE
TWO ALTERNATIVES TO AVOID THE RESULTING WASTE OF RESOURCES. @THE
FIRST IS TO LINK DOMAINS ON DEMAND, AS OPPOSED TO RUN-TIME LINKING.
@THE INITIAL DOMAIN OF A PROCESS CAN INCLUDE A LOADER. @THE LOADER IS
IN CHARGE OF ESTABLISHING LINKS BETWEEN THE MEMBERS OF THE GROUP OF
SUB-DOMAINS BEFORE THE PROCESS IS ALLOWED TO ENTER THE HEAD OF THE
GROUP. @THE OTHER ALTERNATIVE IS TO DEFINE A PROCESS IN CHARGE OF
RECEIVING AND INTERPRETING THE USER'S COMMANDS AND CREATE A NEW
PROCESS TO HANDLE EVERY COMMAND. @THIS APPROACH IS CONGRUENT WITH THE
BINDING OF PROCESSES TO DOMAINS AT CREATE TIME; UNFORTUNATELY,
PROCESS CREATION IS A NON-TRIVIAL, TIME CONSUMING OPERATION.
@MOREOVER, IN ONE CASE, THE SYSTEM LINKING LOADER, AND IN THE OTHER,
THE PROCESS CREATOR, MUST ENJOY ENORMOUS PRIVILEGES OF ACCESS TO
OBJECTS OF TYPE DOMAIN IN ORDER TO BE ABLE TO ESTABLISH THE NEEDED
LINKS BETWEEN THEM. @AS A RESULT, OUR PROPOSED DEFINITION OF DOMAINS
WOULD HAVE TO BE MODIFIED: @THE CAPABILITIES CONTAINED IN THE
DOMAIN'S
@I-SEG MUST NO LONGER BE ACCESSIBLE ONLY TO PROCESSES BOUND TO THE
DOMAIN.
$P
@AN INTERESTING APPROACH TO THE LOAD-TIME LINKING OF DOMAINS IS
DESCRIBED IN [@LA76]. @IN @BERKEKEY'S .CAL SYSTEM, DOMAINS ARE NOT
BASIC
OBJECTS. @THE USER SYSTEM (OPERATING SYSTEM) IS IN CHARGE OF THE
ADMINISTRATION OF DOMAINS AND THE LOAD-TIME LINKING BETWEEN DOMAINS.
@NONETHELESS, THE PROTECTION SYSTEM IS RESPONSIBLE FOR THE RUN-TIME
BINDING OF PROCESSES TO DOMAINS (DOMAIN CALLS) BY MEANS OF BASIC
TYPES OF OBJECTS KNOWN AS 'OPERATIONS' [@LA76].
$P
@THE GENERAL WAY TO DEFINE PARAMETER PASSING IS TO USE THE
TECHNIQUES EMPLOYED IN THE IMPLEMENTATION OF PURE PROCEDURES. @IN
OTHER WORDS, THE @I-SEG OF EVERY DOMAIN IS EXTENDED TO INCLUDE A SET
OF DISJOINT STORAGE SEGMENTS. @THE RESULTING STRUCTURE OF A DOMAIN'S
@I-SEG IS SHOWN SCHEMATICALLY IN FIGURE 2.3-3. @THE EXTENSION
CONSISTS
OF A COLLECTION OF CAPABILITY SEGMENTS, EACH OF WHICH IS ASSOCIATED
UNIQUELY WITH ONE PROCESS.
$P
$V0
@THE EXTENSION OF THE @I-SEG CAN BE CREATED BY THE KERNEL WHEN AN
%ENTER OPERATION IS EXECUTED. @IN PRACTICE, THIS CAN BE SIMULATED BY
MEANS OF A SECTIONED CAPABILITY STACK ASSOCIATED WITH EACH PROCESS
[@RO73]. @THE KERNEL IS IN CHARGE OF DEFINING THE VALUES OF A BASE
AND
A LIMIT REGISTER WHICH ARE USED BY THE PROCESSOR IN ORDER TO DELIMIT
THE WINDOW WITHIN THE STACK WHICH CAN BE ACCESSED BY THE PROCESS AT
EVERY POINT IN TIME.
$P
@WHERE PROGRAMMABLE CAPABILITY REGISTERS ARE AVAILABLE, AS IN THE
@PLESSEY 250 [@EN74], THEY CAN BE USED FOR PARAMETER PASSING.
@HOWEVER,
THIS DOES NOT RELIEVE THE SYSTEM FROM THE NEED TO SUPPLY INDIVIDUAL
WORKING STORAGE FOR THE VARIOUS PROCESSES WHICH MAY BE BOUND
SIMULTANEOUSLY TO A DOMAIN. @IN OUR DEFINITION, THE @I-SEG IS COMMON
TO ALL ACTIVATIONS OF THE DOMAIN. @THEREFORE, IF THE CONTENTS OF A
CAPABILITY REGISTER ARE STORED INTO THE @I-SEG, THE CAPABILITY
BECOMES
TACITLY AVAILABLE TO ANY OTHER PROCESS BOUND TO THE DOMAIN.
@FURTHERMORE, THE PROCESS WHICH WISHES TO STORE A CAPABILITY INTO THE
@I-SEG MUST EXCLUDE OTHER PROCESSES FROM DOING SO. @THIS MAY
INTRODUCE
SYNCHRONISATION CONFLICTS WHEN THE LOGICAL ACTIVITIES OF THE
PROCESSES DO NOT DEMAND MUTUAL EXCLUSION.
$P
@IN @CAMBRIDGE @UNIVERSITY'S .CAP MACHINE, THE INSTANTANEOUS
PROTECTION REGIME OF A PROCESS IS DELIMITED BY A COLLECTION OF
'INDIRECTORIES'. @THE VARIOUS INDIRECTORIES CONTAIN CAPABILITIES FOR
OBJECTS LOCAL TO THE PROCESS BUT GLOBAL TO EVERY DOMAIN EVER ENTERED
BY THE PROCESS; FOR OBJECTS WHICH ARE PRIVATE TO THE DOMAIN AND
SHARED BY ALL PROCESSES BOUND TO THE DOMAIN AND FOR OBJECTS LOCAL TO
THE DOMAIN AND THE PROCESS IN QUESTION. @THE ENTER DOMAIN OPERATION
REQUIRES TWO ARGUMENTS: THE CAPABILITY FOR THE TARGET DOMAIN AND A
SPECIFIER OF AN INDIRECTORY WHICH IS TO BE PASSED TO THE CALLED
DOMAIN [@NE72,@NE74]. @ACCORDING TO @LAUER'S CLASSIFICATION [@LA74],
THE
PROTECTION PHILOSOPHY OF THE .CAP MACHINE BELONGS TO '@NESTED @ADDRESS
@SPACE' SYSTEMS, AS OPPOSING TO WHAT HE CALLS '@GLOBAL @OBJECT @NAME'
SYSTEMS @THE FUNDAMENTAL DIFFERENCE BETWEEN BOTH APPROACHES IS THAT
IN
@NESTED @ADDRESS @SPACE ARCHITECTURES, CAPABILITIES ARE ALWAYS
INTERPRETED IN RELATION TO THE EXECUTING PROCESS. @MOREOVER, THE
CAPABILITY IS A POINTER INTO THE ADDRESS SPACE OF ANOTHER PROCESS:
THE CREATOR AND CONTROLLER OF THE PROCESS. @THE RECURSIVE APPLICATION
OF THIS RULE RESULTS IN A TREE STRUCTURED PROCESS HIERARCHY IN WHICH
THE ROOT PROCESS OR 'MASTER COORDINATOR' [@LI75] IS THE ONLY PROCESS
WHICH SEES THE ABSOLUTE POSITION OF OBJECTS WITHIN THE SYSTEM. @AS
@LAUER POINTS OUT, IT IS VERY DIFFICULT TO ADAPT RECURSIVE PROTECTION
PHILOSOPHY TO MULTIPROCESSOR ENVIRONMENTS.
$P
@THE AUTHORS OF .HYDRA [@JO74,@WU74] DESCRIBE THE CREATION OF A NEW
INSTANCE OF A DOMAIN (PROTECTED PROCEDURE) FOR EVERY PROTECTED
PROCEDURE CALL. @THE CAPABILITY FOR A PROTECTED PROCEDURE CONTAINS
ONLY THE PRESCRIPTION NEEDED TO CREATE A NEW PROTECTION REGIME AT THE
TIME OF CALL. @THUS, THEY CORRESPOND EXACTLY TO THE PROCEDURES OF
@ALGOL.
$P
@WE PROPOSE TO TREAT DOMAINS AS OBJECTS WHICH ARE CREATED ONCE AND
FOR ALL. @THE BINDING OF PROCESSES TO DOMAINS AND THE PASSING OF
PARAMETERS IS PERFORMED AT RUN-TIME WITH THE AID OF PROCESS
CAPABILITY STACKS. @DOMAINS ARE TO BE EMPLOYED TO EXECUTE VERY SIMPLE
OPERATIONS SUCH AS SYNCHRONISING PRIMITIVES. @THEREFORE, IT IS
IMPORTANT TO MINIMISE THE RUN-TIME COST OF INTER-DOMAIN COMMUNICATION
.$(IDC) MECHANISMS. @IN VIEW OF THIS, IT MAY SEEM MORE APPROPIATE TO
ESTABLISH COMMUNICATION LINKS BETWEEN DOMAINS AT THE TIME WHEN THE
PROCESS ENTERS THE HEAD OF A CHAIN OF DOMAINS; I. E. A KIND OF
LOAD-TIME LINKING OF DOMAINS. @AS DESCRIBED ABOVE, THIS APPROACH
INCREASES THE COMPLEXITY OF THE KERNEL. @ON THE OTHER HAND, THE
INCREASE IN THE RUN-TIME COSTS OF THE MORE GENERAL OPTION NEED NOT BE
EXCESSIVE. @IT IS IMPORTANT TO NOTE THAT A PERMANENT @I-SEG CAN BE
USED TO RETAIN A CAPABILITY PASSED AS PARAMETER TO THE DOMAIN BY A
GIVEN PROCESS. @NEVERTHELESS, IN THE NEXT SECTION WE WILL MENTION
THAT THIS SHOULD NOT BE POSSIBLE. @IN CHAPTER 4 WE WILL DISCUSS IN
DETAIL THE RESTRICTIONS WHICH MUST BE IMPOSED ON @I-SEG'S IN ORDER TO
PREVENT DOMAINS FROM REMEMBERING AND DISTRIBUTING CAPABILITIES TO
UNAUTHORISED PROCESSES.
$P
@THE FOLLOWING OBSERVATIONS ARE INCLUDED MAINLY FOR THE SAKE OF
COMPLETENESS.
$P
@IT IS POSSIBLE TO DISPENSE WITH .IDC MECHANISMS AND TO DEFINE A
ONE-TO-ONE CORRESPONDENCE BETWEEN PROCESSES AND DOMAINS. @THIS IS THE
ATTITUDE OBSERVED IN MOST CONVENTIONAL ARCHITECTURES. @AN
INCONVENIENCE OF THIS KIND OF ARRANGEMENT IS THAT THE SYSTEM
IMPLEMENTOR IS FORCED TO DEFINE IN TERMS OF @INTER-PROCESS
@COMMUNICATIONS ACTIVITIES WHICH FALL MORE NATURALLY INTO THE
CATEGORY
OF @INTER-DOMAIN CALLS. @THE .EMAS DIRECTOR PROCESSES ARE A GOOD
EXAMPLE OF THIS CIRCUMSTANCE [@WH74,@RE75]. @THE FUNCTION OF A
DIRECTOR
PROCESS IS TO HIDE FROM THE USER'S VIRTUAL MEMORY THE PORTION
CONTAINING THE THE DICTIONARY OF THE USER FILES. @HAD .IDC MECHANISMS
BEEN AVAILABLE, THIS COULD HAVE BEEN ACCOMPLISHED BY ENCLOSING THE
DICTIONARY DATA STRUCTURES AND THE PROGRAMS WHICH GUARANTEE THEIR
CONSISTENCY WITHIN A DOMAIN WHICH COULD BE ENTERED BY THE USER
PROCESS. @THE MESSAGE SYSTEM DESCRIBED BY @LAMPSON AND USED IN .PRIME
IS ANOTHER EXAMPLE [@LA71]. @ANOTHER DISADVANTAGE OF THE APPROACH IS
THE LIMITATION IMPOSED IN CONCURRENT EXECUTION; A PROCESS CAN SATISFY
ONLY ONE REQUEST AT A TIME. @THE .EMAS DESIGNERS GET ROUND THIS
HINDRANCE BY DEFINING ONE INSTANCE OF A DIRECTOR PROCESS FOR EVERY
USER PROCESS.
$N
2.4.- .TYPE .EXTENSION .FACILITIES.
$P3
@THE KERNEL CAN READILY SUPPORT A LIMITED NUMBER OF BASIC TYPES OF
OBJECTS. @EXAMPLES ARE THE @N-SEG AND @C-SEG OF SECTION 2.2 AND THE
DOMAIN TYPE DISCUSSED IN THE PREVIOUS SECTION. @CLEARLY, THE KERNEL
CAN DEFINE ONLY ACCESS RIGHTS FOR THE BASIC SET OF TYPES, FOR IT
KNOWS NOTHING ABOUT THE SEMANTICS OF OBJECTS WHICH WILL BE EMPLOYED
BY THE DESIGNERS OF THE @OPERATING @SYSTEM FOR THE MACHINE OR BY THE
USERS OF THE VIRTUAL MACHINES CREATED BY THE OPERATING SYSTEM. @BY
PROVIDING FACILITIES TO CREATE CAPABILITIES FOR TYPES OF OBJECTS
UNKNOWN TO IT, THE KERNEL CAN ALLOW ITS USERS TO DEFINE NEW OBJECTS
WHOSE ACCESS RIGHTS HAVE DIFFERENT MEANINGS FROM THOSE OF BASIC
OBJECTS. @YET THE VALIDATION OF ACCESS TO INSTANCES OF OBJECTS OF
USER DEFINED TYPES CAN BE PERFORMED BY THE KERNEL.
$P
@ONE PARTICULARLY ATTRACTIVE ASPECT OF TYPE EXTENSION IS THE
CONSEQUENT SIMPLIFICATION IN THE CONSTRUCTION OF OPERATING SYSTEMS AS
SEQUENCES OF LAYERS [@DI68B]. @AT EVERY NEW STAGE IN THE HIERARCHY,
NEW TYPES OF OBJECTS CAN BE BUILT FROM THOSE DEFINED IN THE PREVIOUS
LAYERS. @THE FACILITIES AFFORDED BY THE KERNEL TO MANIPULATE AND
PROTECT ALL OBJECTS, REGARDLESS OF TYPE, IN A UNIFORM FASHION RELEIVE
THE DESIGNER OF A NEW LAYER FROM THE BURDEN OF DEFINING AND
IMPLEMENTING NAMING AND PROTECTION MECHANISMS PECULIAR TO THAT LEVEL.
$P
@THE MAIN GOALS OF THIS SECTION ARE TO SELECT THE CAPABILITY FOR AN
OBJECT OF EXTENDED TYPE FROM A GROUP OF CANDIDATES AND TO IDENTIFY
THE NATURE OF THE OPERATIONS WHICH THE KERNEL SHOULD PROVIDE IN ORDER
TO CREATE AND MANIPULATE CAPABILITIES FOR OBJECTS OF EXTENDED TYPES.
$P
@NOTABLE DESIGNS OF SYSTEMS PROVIDING TYPE EXTENSION FACILITIES ARE
DESCRIBED BY @FERRIE ET. AL. [@FE74], @REDELL [@RE74,@RE74B], @LAMPSON
[@LA76] AND @WULF ET. AL. [@WU74,@JO74]. @THE LAST TWO HAVE BEEN
IMPLEMENTED IN THE .CAL AND .HYDRA SYSTEMS, RESPECTIVELY. @WE WILL
DELVE INTO SALIENT ASPECTS OF THESE SYSTEMS IN ORDER TO IDENTIFY THE
CHARACTERISTICS DESIRED FOR KERNEL SUPPORTED TYPE EXTENSION
FACILITIES. @FIRSTLY, WE DEVIATE BRIEFLY TO EXPOSE OUR NOTATION AND
TERMINOLOGY.
$P
@CONSIDER THE TWO TYPES OF OBJECTS INTRODUCED IN SECTION 2.2; THEIR
STRUCTURE IS DEPICTED IN FIGURE 2.4-1. @NOTE THAT THE @MAP ENTRY FOR
THE OBJECT HAS BEEN COMPRESSED INTO THE CAPABILITY.
$P
$V0
@WE CAN IMMEDIATELY IDENTIFY TWO CONSTITUENTS OF THESE OBJECTS: @THE
CAPABILITY FOR THE OBJECT AND THE %REPRESENTATION OF THE OBJECT. @THE
REPRESENTATION OF AN OBJECT CAN BE DEFINED AS THE ENTITY WHICH THE
CAPABILITY FOR THE OBJECT IS INTENDED TO NAME, LOCATE AND PROTECT.
@CAPABILITIES WILL ALWAYS BE DRAWN AS SQUARE BLOCKS AND THE
REPRESENTATIONS OF OBJECTS OF THE @N-SEG OR @C-SEG TYPES AS WELL AS
THE
REPRESENTATIONS OF DOMAINS (SEE FIGURE 2.4-3 BELOW) WILL BE DEPICTED
AS A TORN SECTION OF TAPE.
$P
@MNEMONICS ARE USED IN THE TYPE AND NAME FIELDS OF CAPABILITIES FOR
CONVENIENCE; IN REALITY, THESE FIELDS CONTAIN INTEGERS SUPPLIED BY
THE KERNEL WHEN THE CAPABILITY IS CREATED. @THE LENGTH FIELD WILL
SUBSEQUENTLY BE OMITTED. @WHERE A PARTICULAR MNEMONIC IS USED IN
PLACE OF THE GENERIC .'ID' IN THE NAME FIELD, WE WILL USE THAT
MNEMONIC TO REFER TO THE OBJECT. @THE NAME WILL BE QUALIFIED BY THE
WORDS 'THE CAPABILITY FOR' OR 'THE REPRESENTATION OF' WHEN SPECIFIC
DISTINCTION OF ONE OF THE TWO CONSTITUENTS IS DESIRED. @LIKEWISE, WE
REFER TO A GENERIC OBJECT OF A PARTICULAR TYPE BY MEANS OF
EXPRESSIONS SUCH AS 'A DOMAIN' OR 'A @C-SEG'.
$P2
@WE WILL IGNORE THE EXISTENCE OF OTHER BASIC TYPES OF OBJECTS
CORRESPONDING FOR EXAMPLE TO PERIPHERAL DEVICES, SINCE THEIR
TREATMENT IS ANALOGOUS TO THAT OF SEGMENTS. @MOREOVER, THE ACCESS TO
THE ACTUAL DEVICES CAN BE CONCENTRATED IN A COLLECTION OF SPECIALISED
PROCESSES IN CHARGE OF PROVIDING THE COMMUNICATION FACILITIES BETWEEN
OTHER PROCESSES AND THE OUTSIDE WORLD.
$P2
@THE ULTIMATE OBJECTIVE OF EVERY OPERATION IN A COMPUTER SYSTEM IS
TO ACCESS ONE OF THE BASIC SYSTEM OBJECTS HAVING A TANGIBLE, PHYSICAL
REPRESENTATION. @FOR EXAMPLE, THE OBJECTS OF THE DOMAIN TYPE
DESCRIBED IN SECTION 2.3 ARE ENTERED BY PROCESSES FOR THE PURPOSE OF
OBTAINING ACCESS TO THE @I-SEG OF THE DOMAIN AND HENCE TO THE OBJECTS
WHOSE CAPABILITIES ARE CONTAINED THEREIN. @THUS, THE REPRESENTATION
OF EVERY NEW TYPE OF OBJECT MUST BE CONSTRUCTED FROM OBJECTS WHICH
HAVE ALREADY BEEN DEFINED, AND EVERY OBJECT IS ULTIMATELY
CHARACTERISED IN TERMS OF THE TWO BASIC TYPES: @C-SEG AND @N-SEG.
$P
@IT IS ALWAYS POSSIBLE TO GATHER THE SET OF CAPABILITIES FOR THE
OBJECTS COMPRISING THE REPRESENTATION OF AN OBJECT OF EXTENDED TYPE
INTO A SINGLE @C-SEG. @THEREFORE, IT IS REASONABLE TO USE THAT OBJECT
OF TYPE @C-SEG AS THE %REPRESENTATION OF THE NEW, CONSTRUCTED OBJECT.
@WE USE THE TERMS 'EXTENDED OBJECT' TO REFER TO AN OBJECT OF A NEW,
CONSTRUCTED TYPE AND THE WORDS 'EXTENDED TYPE' TO REFER TO A TYPE
CREATED BY THE KERNEL ON BEHALF OF ONE OF ITS USERS [@RE74].
$P
@FIGURE 2.4-2 DEPICTS THE STRUCTURE OF AN OBJECT CALLED .R. @R
CONTAINS THE CAPABILITIES FOR TWO OBJECTS NAMED .NOR AND .CAP.
@SUPPOSE
THE STRUCTURE OF .R, AS SHOWN IN THE FIGURE, DEFINED THE GENERAL FORM
OF THE MEMBERS OF AN EXTENDED TYPE. @WE REFER TO THE CAPABILITY FOR @R
(ENCLOSED IN THE DOTTED LINES) AS THE %CAPABILITY %FOR %THE
%REPRESENTATION OF THE EXTENDED OBJECT. @IT IS IMPORTANT TO EMPHASISE
THAT THIS MAY BE QUITE DIFFERENT FROM THE (YET TO BE DEFINED)
CAPABILITY FOR THE EXTENDED OBJECT, OF WHICH @R IS THE
REPRESENTATION.
@THE INDIVIDUAL OBJECTS, .NOR AND .CAP, WHOSE CAPABILITIES ARE
CONTAINED
WITHIN THE REPRESENTATION OF @R ARE CALLED THE COMPONENTS OF THE
EXTENDED OBJECT.
$P
$V0
@IT FOLLOWS FROM THE FINAL PURPOSE OF EVERY SYSTEM ACTION THAT THE
OPERATIONS ON EXTENDED OBJECTS MUST BE DEFINED IN TERMS OF THE
OPERATIONS WHICH CAN BE PERFORMED BY THE NAKED SYSTEM. @WE MENTIONED
IN SECTION 2.3 THAT DOMAINS CAN CONTAIN INSTRUCTION SEQUENCES TO
DIRECT THE EXECUTION OF THE PROCESS BOUND TO THE DOMAIN.
@CONSEQUENTLY, THE LOGICAL CANDIDATE TO DEFINE AND IMPLEMENT
OPERATIONS ON EXTENDED OBJECTS IS THE DOMAIN. @INDEED, DOMAINS OR
THEIR NEAR SYNONYMS HAVE BEEN EMPLOYED FOR THIS PURPOSE IN EVERY
CAPABILITY SYSTEM DESCRIBED IN THE LITERATURE.
$P
@FOR THE TIME BEING, WE ASSUME THAT DOMAINS HAVE THE STRUCTURE
SHOWN IN FIGURE 2.4-3. @THE UNIQUE ACCESS RIGHT OF OBJECTS OF TYPE
DOMAIN IS THE ENTER ACCESS. @IT IS ASSUMED THAT EVERY DOMAIN HAS THE
PRIVILEGE OF RETURNING TO ITS CALLER. @THE REPRESENTATION OF THE
DOMAIN IS THE @IMPLICIT SEGMENT, LABELLED @I-SEG IN THE FIGURE. @THE
THREE COMPONENTS, .P, @D AND @A ARE, RESPECTIVELY, THE PROGRAM
SEGMENT,
DATA SEGMENT AND ARGUMENT SEGMENT OF THE DOMAIN. @THE @P AND @D
SEGMENTS ARE FIXED. @THE SLOT CONTAINING THE ARGUMENT SEGMENT IS
FILLED BY THE %ENTER OPERATION AT THE TIME OF CALL.
$P
@FINALLY, WE WILL USE THE TERM 'IMPLEMENTOR' TO REFER TO THE DOMAIN
WHICH IMPLEMENTS THE OPERATIONS ON AN EXTENDED OBJECT AND THE WORD
'USER' TO DENOTE THE DOMAIN WHICH POSSESSES THE CAPABILITY FOR THE
EXTENDED OBJECT AND WISHES TO ENTER THE IMPLEMENTOR DOMAIN FOR THE
PURPOSE OF PERFORMING AN OPERATION ON THE EXTENDED OBJECT.
$P
@WHEN THE USER WISHES TO PERFORM AN OPERATION ON AN EXTENDED
OBJECT, IS MUST CALL THE IMPLEMENTOR AND PRESENT IT WITH THE
CAPABILITY FOR THE EXTENDED OBJECT. @THE IMPLEMENTOR SHOULD BE
EMPOWERED TO ASSOCIATE THE CAPABILITY FOR THE EXTENDED OBJECT
PRESENTED TO IT WITH THE CAPABILITY FOR THE REPRESENTATION OF THE
EXTENDED OBJECT: @THE IMPLEMENTOR WILL PERFORM THE OPERATION ON THE
REPRESENTATION OF THE EXTENDED OJECT. @THE FOLLOWING SEQUENCE OF
CONSTRAINTS HAVE TO BE IMPOSED ON CAPABILITIES FOR EXTENDED OBJECTS:
$A INDENT=2
$B0
$C-3 1) @THE EXTENDED OBJECT'S CAPABILITY MUST BE ASSOCIATED SOMEHOW
WITH THE CAPABILITY FOR THE REPRESENTATION OF THE EXTENDED
OBJECT.
$B0
$C-3 2) @THE CAPABILITY FOR THE EXTENDED OBJECT MUST NOT ALLOW ITS
POSSESSOR TO ACCESS THE REPRESENTATION OF THE EXTENDED OBJECT.
@OTHERWISE, THE USER DOMAIN WOULD BE CAPABLE OF PERFORMING
OPERATIONS ON THE REPRESENTATION OF THE EXTENDED OBJECT
DIRECTLY.
$B0
$C-3
3) @WHEN INVOKED TO PERFORM THE OPERATION, THE IMPLEMENTOR MUST BE
ABLE TO REACH THE CAPABILITY FOR THE REPRESENTATION OF THE
EXTENDED OBJECT FROM THE CAPABILITY FOR THE EXTENDED OBJECT.
$B0
$C-3
4) @THE IMPLEMENTOR SHOULD BE ABLE TO OPERATE ON THE REPRESENTATION
OF THE EXTENDED OBJECT ONLY UPON REQUEST. @THEREFORE, IS SHOULD
BE PREVENTED FROM USING THE CAPABILITY FOR THE EXTENDED OBJECT
AT ANY OTHER TIMES.
$B
$A INDENT=0
$P
@THE FIRST THREE CONDITIONS ARE NECESSARY TO GUARANTEE THE
INTEGRITY OF THE SEMANTICS OF OBJECTS OF EXTENDED TYPES, UNDER THE
ASSUMPTION THAT IMPLEMENTOR DOMAINS ARE NOT SUBVERSIVE. @CONDITION 4)
CAN BE ELIMINATED WITHOUT ENDANGERING THE INTEGRITY OF EXTENDED
OBJECTS. @HOWEVER, IN THE CASE OF NON-SHARED EXTENDED OBJECTS, IT IS
REASONABLE FOR THE USER TO EXPECT THAT THE VALUE OF THE OBJECT REMAIN
INVARIANT BETWEEN TWO SUCCESSIVE OPERATIONS ON THE OBJECT. @IN THIS
SENSE, CONDITION 4) IS NECESSARY TO ENSURE THE INTEGRITY OF EXTENDED
OBJECTS. @OTHER PRIVACY CONSIDERATIONS WILL BE MENTIONED BRIEFLY IN
CHAPTER 3.
$P
@THE SIMPLEST APPROACH TO TYPE EXTENSION CONSISTS IN DEPOSITING THE
REPRESENTATION, OR MORE PRECISELY, THE CAPABILITIES FOR THE
COMPONENTS OF THE REPRESENTATION OF THE EXTENDED OBJECT WITHIN THE @D
COMPONENT OF A DOMAIN; THE USER DOMAINS ARE FURNISHED WITH THE
CAPABILITY FOR THE DOMAIN WHICH ENGLOBES THE REPRESENTATION OF THE
EXTENDED OBJECT. @THUS, CAPABILITIES FOR EXTENDED OBJECTS ARE REALLY
THE CAPABILITIES FOR THE DOMAINS WHICH CONTAIN THE REPRESENTATIONS OF
THE OBJECTS AND IMPLEMENT OPERATIONS ON THOSE EXTENDED OBJECTS. @IT
IS NOT DIFFICULT TO VERIFY THAT THE TECHNIQUE SATISFIES THE
CONSTRAINTS. @IN THIS SENSE, THE SCHEME IS QUITE SATISFACTORY;
HOWEVER, IS SEEMS MORE APPROPIATE TO REGARD IT AS AN INGENIOUS USAGE
OF DOMAINS TO PROVIDE FURTHER CONTROL OF ACCESS TO BASIC OBJECTS
RATHER THAT A TYPE EXTENSION MECHANISM [@EN74,@NE74]. @THE SCHEME IS
ANALOGOUS TO THE USE OF PROCEDURES TO SIMULATE SYNTACTIC EXTENSION IN
A PROGRAMMING LANGUAGE. @SOME PROBLEMS ARISING FROM THIS APPROACH ARE
DISCUSSED BELOW IN ORDER TO HIGHLIGHT THE ADVANTAGES OF PROVIDING
PROPER TYPE EXTENSION FACILITIES. @FIRSTLY, THE TYPE OF AN OBJECT CAN
ONLY BE DETERMINED BY ESTABLISHING A SYSTEM WIDE CONVENTION OF
STORING THE TYPE IDENTIFIER IN A PREVIOUSLY AGREED PLACE OF EVERY
DOMAIN. @FURTHERMORE, THE TYPE CAN BE RETRIEVED ONLY BY CALLING THE
DOMAIN, UNLESS AN AD-HOC OPERATION WHICH EXAMINES THE RESERVED SLOT
OF DOMAINS IS DEFINED. @SECONDLY, ACCESS RIGHTS CORRESPONDING TO THE
DIFFERENT OPERATIONS DEFINED ON THE EXTENDED OBJECT ARE IMPLICIT IN
THE OPERATIONS WHICH THE DOMAIN IS WILLING TO PERFORM. @THEREFORE,
THE DISTRIBUTION OF THE CAPABILITY FOR AN EXTENDED OBJECT WITH TWO OR
MORE SETS OF DIFFERENT ACCESS RIGHTS ESSENTIALLY REQUIRES THAT TWO OR
MORE VERSIONS OF THE @P COMPONENT OF THE IMPLEMENTOR DOMAIN BE
PROVIDED. @THIS CAN BE VERY WASTEFUL IN SPITE OF THE FACT THAT THE
VARIOUS VERSIONS COULD SHARE SUB-COMPONENTS OF A SINGLE @P SEGMENT.
@NOTE THAT THIS APPROACH PERMITS THE ELIMINATION OF THE TYPE FIELD IN
THE CAPABILITIES, SINCE THE NUMBER OF DIFFERENT TYPES OF OBJECTS IS
LIMITED TO THE BASIC TYPES. @THE BASIC TYPES ARE CERTAINLY KNOWN IN
ADVANCE AND, PRESUMABLY, THE NUMBER OF DISTINCT OPERATIONS IS
RELATIVELY SMALL.
$P
@THE NEXT APPROACH USES THE CAPABILITY FOR THE REPRESENTATION OF
THE EXTENDED OBJECT AS THE CAPABILITY FOR THE EXTENDED OBJECT.
$P
@THE REPRESENTATION OF THE EXTENDED OBJECT CONTAINS THE INFORMATION
WHICH THE IMPLEMENTOR OF THE OPERATION ON THE EXTENDED TYPE WILL NEED
TO ACCESS. @CONSEQUENTLY, IS IS TEMPTING TO USE THE CAPABILITY FOR
THE REPRESENTATION OF THE EXTENDED OBJECT AS THAT OF THE EXTENDED
OBJECT. @AS IS STANDS, THE CAPABILITY FOR THE REPRESENTATION OF AN
OBJECT CANNOT BE MADE AVAILABLE TO THE USER OF THE EXTENDED OBJECT.
@THE CAPABILITY WOULD EMPOWER THE USER TO PERFORM ALL THE OPERATIONS
DEFINED ON THE REPRESENTATION AND THEREBY VIOLATE THE SEMANTICS OF
THE EXTENDED TYPE. @THE ACCESS RIGHTS OF THE VERSION POSSESSED BY THE
USER DOMAIN MUST BE ADJUSTED TO REFLECT ONLY THE OPERATIONS WHICH ARE
DEFINED ON THE EXTENDED TYPE. @THE DIAGRAM OF FIGURE 2.4-4
ILLUSTRATES THE SCHEME. @THE CROSSED PARTS OF THE ACCESS RIGHTS FIELD
IN THE TWO VERSIONS OF THE CAPABILITY ARE INTENDED TO EMPHASISE THE
DISJOINTNESS OF THE PRIVILEGES POSSESSED BY EACH OF THE DOMAINS.
$P
$V0
@WHEN THE IMPLEMENTOR IS CALLED BY THE USER, IT RECEIVES AS
PARAMETER THE CAPABILITY WHOSE ACCESS RIGHTS FIELD PERMIT THE
EXTENDED OPERATION. @THE IMPLEMENTOR MUST NOW BE ABLE TO MODIFY THE
ACCESS RIGHTS FIELD OF THE CAPABILITY IN ORDER TO BE ABLE TO PERFORM
THE REQUESTED OPERATION ON THE REPRESENTATION OF THE EXTENDED OBJECT.
@THE PIVILEGE TO 'AMPLIFY' THE ACCESS RIGHTS OF A CAPABILITY MUST BE
CONTROLLED CAREFULLY; IT SHOULD CERTAINLY NOT BE GIVEN TO THE USER
DOMAIN OF THE EXTENDED TYPE. @MOREOVER, THE MODIFICATION OF A PART OF
A CAPABILITY CAN BE CARRIED OUT ONLY BY THE KERNEL. @IN OTHER WORDS,
AMPLIFICATION IS A KERNEL OPERATION AND THE RIGHT TO PERFORM THE
OPERATION CANNOT BE MADE PUBLICLY AVAILABLE; IT SHOULD BE CONTROLLED
BY A CAPABILITY. @NOTE THAT THE USER DOMAIN MAY, IN GENERAL, BE THE
IMPLEMENTOR OF OPERATIONS ON FURTHER EXTENSIONS OF THE ALREADY
EXTENDED OBJECT. @THIS COMPLICATES THE AMPLIFICATION OPERATION SINCE
A WEAK-TO-FULL AMPLIFICATION OF ACCESS RIGHTS WOULD ALLOW ONLY ONE
EXTENSION OF AN OBJECT OF A GIVEN TYPE. @THE IMPLICATION OF THE LAST
OBSERVATION IS THAT THE SET OF RIGHTS WHICH THE AMPLIFICATION
OPERATION GRANTS TO THE EXECUTOR DEPENDS ON THE SET OF RIGHTS WHICH
ARE PRESENT IN THE CAPABILITY WHEN THE OPERATION IS PERFORMED. @THUS,
THE CAPABILITY WHICH AUTHORISES THE AMPLIFICATION OPERATION MUST
INDICATE TO THE KERNEL THE SET OF RIGHTS WHICH MUST BE PRESENT IN THE
CAPABILITY WHICH WILL BE AMPLIFIED, IN ADDITION TO THE SET OF RIGHTS
WHICH WILL BE GRANTED IF THE AMPLIFICATION IS SUCCESSFULL. @CLEARLY,
ACCESS RIGHTS VERIFICATION OF EXTENDED OBJECTS BECOMES AN IMPLICIT
PART OF THE AMPLIFICATION OPERATION. @IN .HYDRA, THE SPECIFICATION OF
EVERY DOMAIN (PROTECTED PROCEDURE) CONTAINS A NUMBER OF PARAMETER
SLOTS. @EACH SLOT CONTAINS A 'TEMPLATE' WITH THE WEAK AND STRONG
ACCESS RIGHTS OF THE WOULD BE PARAMETERS TO THE CALL. @THE PROCEDURE
CALL MECHANISM USES THE INFORMATION IN THE TEMPLATES AND
AUTOMATICALLY PERFORMS AN AMPLIFICATION OPERATION ON EVERY ACTUAL
PARAMETER [@JO74]. @IN ORDER TO SATISFY CONDITION 4) IT IS NECESSARY
TO ENSURE THAT THE IMPLEMENTOR DESTROY THE CAPABILITIES PASSED AS
ARGUMENTS BY THE CALLER BEFORE EXECUTING THE %EXIT OPERATION. @IN
.HYDRA, THIS DESTRUCTION OF THE PARAMETERS OF A DOMAIN IS IMPLICIT IN
THE DESTRUCTION OF THE INSTANCE OF THE DOMAIN WHICH EXECUTES AN %EXIT
OPERATION. @THE MAIN DISADVANTAGE OF THIS SCHEME IS THE IMPOSIBILITY
OF DETERMINING THE ATTRIBUTES OF AN OBJECT SOLELY FROM THE TYPE FIELD
OF ITS CAPABILITY. @WHILE THE TYPE FIELD DETERMINES THE STRUCTURE OF
AN OBJECT, THE SET OF OPERATIONS WHICH ARE APPLICABLE TO THAT OBJECT
CAN BE DETERMINED ONLY FROM THE COMBINED EXAMINATION OF THE TYPE AND
ACCESS RIGHTS FIELD OF THE OBJECT'S CAPABILITY. @NOTE THAT THE SIZE
OF THE ACCESS RIGHTS FIELD IN THE CAPABILITY IMPOSES A LIMIT ON THE
NUMBER OF TIMES THAT AN OBJECT OF A GIVEN STRUCTURE MAY BE EXTENDED.
@IN SYSTEMS PROVIDING A TYPE FIELD IN CAPABILITIES, E. G. .HYDRA,
THIS
IS NOT A MAJOR PROBLEM. @WHEN THE ACCESS RIGHTS FIELD OF A CAPABILITY
HAS BEEN EXHAUSTED, THE CAPABILITY FOR THE OBJECT CAN BE STORED
WITHIN THE REPRESENTATION OF AN OBJECT OF A NEW TYPE; I. E. AN OBJECT
WHOSE TYPE FIELD IS DIFFERENT FROM THAT OF THE OBJECT ON WHICH
ADDITIONAL OPERATIONS NEED TO BE DEFINED. @THE ADDITIONAL OPERATIONS
CAN BE IMPLEMENTED BY A DOMAIN WHICH SUPPORTS OPERATIONS ON THE
COMPLETELY NEW TYPE.
$P
@FERRIE ET. AL. [@FE74] PRESENT A TYPE EXTENSION SCHEME IN WHICH THE
TYPE FIELD OF THE CAPABILITY FOR THE EXTENDED OBJECT DIFFERS FROM THE
TYPE MARK OF THE CAPABILITY FOR THE REPRESENTATION OF THE OBJECT.
@THE ASSOCIATION BETWEEN THE EXTENDED TYPE AND THE TYPE OF THE
REPRESENTATION IS ACHIEVED VIA TWO KERNEL 'TRANSITION' OPERATIONS
NAMED .CASE AND .UNCASE.
$P
$V0
@THE TRANSITION CAPABILITY CONTAINS TWO PAIRS OF TYPE/ACCESS RIGHTS
FIELDS CORRESPONDING, RESPECTIVELY, TO THOSE OF THE EXTENDED TYPE AND
THE TYPE OF THE REPRESENTATION OF THE EXTENDED TYPE. @A DIAGRAM OF A
TRANSITION CAPABILITY IS SHOWN IN FIGURE 2.4-5; THE UNIQUE .ID FIELD
OF THE CAPABILITY IS USED AS THE DEPOSITORY OF THE TYPE/ACCESS RIGHTS
OF THE TWO TYPES IN QUESTION. @THE ACCESS RIGHTS GUARD THE .CASE AND
.UNCASE OPERATIONS. @WHEN THE IMPLEMENTOR OF AN EXTENDED TYPE NEEDS
TO
EXECUTE AN OPERATION, IT ISSUES THE .UNCASE OPERATION PRESENTING AS
PARAMETERS THE TRANSITION CAPABILITY AND THE CAPABILITY FOR THE
EXTENDED OBJECT. @THE KERNEL VERIFIES THAT THE TYPE AND ACCESS RIGHTS
OF THE EXTENDED OBJECT'S CAPABILITY BE CONGRUENT WITH THE
CORRESPONDING PAIR IN THE TRANSITION CAPABILITY BEFORE GRANTING THE
IMPLEMENTOR THE CAPABILITY WITH THE TYPE AND ACCESS RIGHTS OF THE
OBJECT'S REPRESENTATION. @THE .CASE OPERATION IS THE INVERSE OF
.UNCASE; IT IS USED TO CREATE NEW INSTANCES OF OBJECTS OF EXTENDED
TYPES. @IT IS IMPORTANT TO NOTE THAT .CASE AND .UNCASE DO NOT MODIFIY
THE UNIQUE .ID FIELD OF THE CAPABILITY; HENCE, THE MAP ENTRY
CORRESPONDING TO THE CAPABILITY FOR THE EXTEDED OBJECT POINTS TO THE
STARTING ADDRESS OF THE REPRESENTATION OF THE OBJECT. @THEREFORE, IF
THE TRANSITION OPERATION DELIVERS THE CAPABILITY FOR THE
REPRESENTATION OF THE EXTENDED OBJECT IN SITU, THE IMPLEMENTOR MUST
REQUEST A .CASE FROM THE KERNEL BEFORE RETURNING TO THE USER DOMAIN.
@IN ANY CASE, THE KERNEL MUST ENSURE THAT THE IMPLEMENTOR DOES NOT
KEEP COPIES OF THE CAPABILITY FOR THE REPRESENTATION OF THE EXTENDED
OBJECT, LEST IT VIOLATE CONDITION 4). @AN IMPORTANT GAIN OF THIS
APPROACH TO TYPE EXTENSION IS THAT THE TYPE OF AN OBJECT IS NOW
DETERMINED UNAMBIGUOUSLY BY THE VALUE IN THE TYPE FIELD OF ITS
CAPABILITY. @THERE IS AN IMPLEMENTATION PROBLEM ARISING FROM THE NEED
TO ACCOMMODATE THREE TYPE MARKS IN THE TRANSITION CAPABILITY. @WE
WILL DISCUSS BELOW THAT IT IS EXTREMELY CONVENIENT TO SUPPORT A
PRACTICALLY INFINITE NUMBER OF DISTINCT TYPES. @THE IMPLICATION BEING
THAT A TYPE FIELD MUST BE OF THE SAME SIZE AS THE UNIQUE .ID FIELD OF
A CAPABILITY. @HOWEVER, THIS WOULD PRECLUDE THE IMPEMENTATION OF
TRANSITION CAPABILITIES AS PROPOSED IN [@FE74].
$P
@IN THE DESIGN OF THE @NEW @CAPABILITY @SYSTEM .(NCS), @REDELL TAKES
ADVANTAGE OF THE FOLLOWING OBSERVATIONS [@RE74A]: @THE CAPABILITY FOR
AN EXTENDED OBJECT IS INTENDED TO PREVENT ITS POSSESSOR FROM
ACCESSING THE REPRESENTATION OF THE OBJECT DIRECTLY. @INSTEAD, THE
USER DOMAIN HAS TO ENTER A DOMAIN (THE IMPLEMENTOR) WHICH WILL BE IN
CHARGE OF ACCESSING THE REPRESENTATION OF THE OBJECT. @CONSEQUENTLY,
THE LOCATION FIELD OF THE CAPABILITY FOR THE EXTENDED OBJECT CAN BE
USED TO STORE A POINTER TO THE CAPABILITY FOR THE EXTENDED OBJECT'S
REPRESENTATION INSTEAD OF THE ADDRESS OF A MEMORY SEGMENT WHICH IS
NEVER USED. @ACCORDINGLY, AN EXTENDED OBJECT COULD HAVE THE STRUCTURE
DEPICTED IN FIGURE 2.4-6. @THE LOCATION FIELD OF THE CAPABILITY FOR
THE EXTENDED OBJECT DOES NOT POINT TO THE REPRESENTATION OF THE
OBJECT BUT TO ANOTHER CAPABILITY; NAMELY, THE CAPABILITY FOR THE
REPRESENTATION FOR THE EXTENDED OBJECT. @THE PROBLEM IS TO IMPLEMENT
THE STORAGE OF A POINTER FROM ONE CAPABILITY TO ANOTHER.
$P
$V0
@IN THE IMPLEMENTATION OF CAPABILITIES OF .NCS, THE MAP ENTRY OF AN
OBJECT IS ENLARGED TO INCLUDE THE TYPE AND ACCESS RIGHTS FIELDS, BOTH
OF WHICH ARE ELIMINATED FROM THE 'SHORT' VERSIONS OF CAPABILITIES
CONTAINED IN THE @I-SEG'S OF DOMAINS. @THE FORM OF A CAPABILITY AND
ITS CORRESPONDING MAP ENTRY ARE SHOWN IN FIGURE 2.4-7. @DEPENDING ON
WHETHER THE OBJECT IS OF BASIC OR EXTENDED TYPE, THE LOCATION FIELD
OF THE MAP ENTRY OF A CAPABILITY CONTAINS EITHER THE ADDRESS OF THE
OBJECT IN PRIMARY OR SECONDARY STORAGE OF THE UNIQUE .ID OF ANOTHER
MAP ENTRY. @THE LATTER IS THE HASH INDEX REQUIRED TO LOCATE THE
CAPABILITY IN THE MAP. @THUS, ALL THE INFORMATION NEEDED BY THE
PROTECTION MECHANISM TO CONTROL ACCESS TO AN OBJECT IS CONCENTRATED
IN THE MAP WHICH IS ACCESSIBLE ONLY TO THE KERNEL. @IN FACT, THE
CAPABILITIES ARE WHOLLY CONTAINED WITHIN THE MAP; DOMAINS POSSESS
MERELY POINTERS TO THE CAPABILITIES FOR OBJECTS.
$P
@A SIGNIFICANT ADVANTAGE OF STORING ALL THE INFORMATION NEEDED TO
PROTECT AN OBJECT WITHIN THE MAP ENTRY IS THAT THE COST OF KEEPING
MULTIPLE COPIES OF A CAPABILITY IS REDUCED, SINCE ONLY THE UNIQUE .ID
FIELD OF THE CAPABILITY FOR AN OBJECT MUST BE KEPT IN THE @I-SEG'S OF
DOMAINS. @IN PARTICULAR, THE COST OF TREATING THE TYPE IDENTIFIER IN
THE SAME FASHION AS THE UNIQUE .ID FIELD IS KEPT AT A REASONABLE
LEVEL. @IT IS EXTREMELY CONVENIENT TO DEFINE A TYPE FIELD WHICH IS
LARGE ENOUGH TO ACCOMMODATE AN INEXHAUSTIBLE SUPPLY OF DISTINCT
VALUES. @THIS RELIEVES THE OPERATING SYSTEM FROM THE BURDEN OF
ALLOCATING YET ANOTHER RESOURCE. @ON THE OTHER HAND, THERE IS A
SERIOUS INCREASE IN THE COST OF MAINTAINING THE MAP. @MOREOVER, THE
MAP ENTRY OF A CAPABILITY MUST BE CONSULTED WHENEVER AN OPERATION IS
ATTEMPTED. @HENCE, THERE IS AN OVERHEAD EVEN IN CASES WHEN THE TYPE
OR ACCESS RIGHTS OF THE CAPABILITY DO NOT PERMIT THE OPERATION TO
TAKE PLACE.
$P
@TWO KERNEL OPERATIONS CALLED .SEAL AND .UNSEAL [@RE74,@MO73] ARE
PROVIDED TO ALLOW THE CREATION OF NEW INSTANCES OF EXTENDED OBJECTS
AND THE RETRIEVAL OF THE CAPABILITY FOR THE REPRESENTATION OF
EXTENDED OBJECTS. @A SPECIAL CAPABILITY CALLED THE 'TYPE' CAPABILITY
MUST BE PRESENTED TO THE KERNEL WHEN A .SEAL$/UNSEAL OPERATION IS
REQUESTED. @THE MAIN DIFFERENCE BETWEEN THE .SEAL$/UNSEAL AND
.CASE$/UNCASE OPERATIONS DISCUSSED ABOVE IS THAT THE .SEAL$/UNSEAL
OPERATIONS DO NOT INCLUDE THE TYPE OR ACCESS RIGHTS CHECKS PERFORMED
BY .CASE$/UNCASE ON THE CAPABILITY FOR THE REPRESENTATION OF THE
EXTENDED OBJECT; THEY CONSIDER ONLY THE TYPE AND ACCESS RIGHTS OF THE
CAPABILITY FOR THE EXTENDED OBJECT. @IN OTHER WORDS, THE OWNER OF THE
'TYPE' CAPABILITY FOR TYPE T CAN REQUEST THE KERNEL TO CREATE A NEW
EXTENDED OBJECT OF TYPE T SPECIFYING ANY OTHER OBJECT TO BE THE
REPRESENTATION OF THE OBJECT OF TYPE T.
$P
@REDELL COMBINES THE 'GENERALISED SEALING' APPROACH TO TYPE
EXTENSION WITH THE DEFINITION OF DISTINGUISHED TYPES CALLED 'BOXES'
TO PROVIDE A FLEXIBLE MECHANISM FOR THE SELECTIVE REVOCATION OF
ACCESS PRIVILEGES [@RE74,@FA74]. @SELECTIVE REVOCATION PERMITS THE
USER
DOMAIN TO CHOOSE WHETHER OR NOT THE IMPLEMENTOR DOMAIN IS FORCED TO
RELINQUISH ITS ACCESS PRIVILIGES TO THE REPRESENTATION OF THE
EXTENDED OBJECT. @WE WILL EXAMINE THE REVOCATION SCHEME IN MORE
DETAIL IN THE NEXT SECTION.
$P
@THE GENERALISED SEALING APPROACH TO TYPE EXTENSION COMBINES THE
PHILOSOPHY OF NESTED ADDRESS SPACE SYSTEMS [@NE72,@LA74] WITH THE
PRINCIPLES OF GLOBAL OBJECT NAME SYSTEMS [@DE66]. @WHEN AN EXTENDED
OBJECT IS CREATED, A MAPPING IS DEFINED BY THE KERNEL FROM THE
CAPABILITY FOR THE EXTENDED OBJECT THROUGH THE CAPABILITY FOR THE
REPRESENTATION OF THE OBJECT TO THE ACTUAL, PHYSICAL REPRESENTATION
OF THE OBJECT IN TERMS OF BASIC TYPES OF OBJECTS. @IN ADDITION, THE
INTERMEDIATE CAPABILITY; I. E. THE CAPABILITY FOR THE REPRESENTATION
OF THE EXTENDED OBJECT CAN BE REGARDED AS BEING CONTAINED WITHIN THE
ADDRESS SPACE OF THE DOMAIN WHICH IMPLEMENTS THE EXTENDED TYPE. @OF
COURSE, THE LAST OBSERVATION ASSUMES THAT THE IMPLEMENTOR DOMAIN IS
THE SOLE POSSESSOR OF THE 'TYPE' CAPABILITY FOR THE EXTENDED TYPE;
THEREFORE, NO OTHER DOMAIN CAN ACHIEVE ACCESS TO THE CAPABILITY FOR
THE REPRESENTATION OF THE EXTENDED OBJECT.
$P
@THE PRINCIPAL VIRTUE OF THE APPROACH USED IN .NCS TO SUPPORT TYPE
EXTENSION IS THE CONSISTENCY IN THE TREATMENT OF BASIC AND EXTENDED
TYPES OF OBJECTS. @WE HAVE DEFINED THE REPRESENTATION OF AN OBJECT AS
THE ENTITY WHICH THE OBJECT'S CAPABILITY IS INTENDED TO PROTECT.
@HOWEVER, THE REPRESENTATION OF AN EXTENDED OBJECT IS, IN ITS TURN,
ANOTHER OBJECT; CAPABILITY AND REPRESENTATION INCLUDED.
@CONSEQUENTLY, ACCESS TO THAT OBJECT (THE REPRESENTATION OF THE
OBJECT) MUST BE ALLOWED ONLY IF ITS CAPABILITY IS PRESENTED. @IN THE
GENERALISED SEALING APPROACH TO TYPE EXTENSION THE ASSOCIATION
BETWEEN THE CAPABILITY FOR THE EXTENDED OBJECT AND THE COMPLETE
OBJECT COMPRISING THE REPRESENTATION OF THE EXTENDED OBJECT IS
ACCOMPLISHED BY CONSTRUCTION OF THE CAPABILITIES FOR EXTENDED OBJECT
@IN CONTRAST, OTHER SCHEMES ACHIEVE THE SAME EFFECT BY MANIPULATING
THE CAPABILITIES IN DIFFERENT WAYS DEPENDING ON WHETHER OR NOT THEY
REFER TO BASIC TYPES OF OBJECTS.
$P
@IN THE NEXT CHAPTER WE DEVELOP A FUNCTIONAL APPROACH TO CAPABILITY
BASED PROTECTION WHICH MAKES USE OF THIS ARCHITECTURAL PROPERTY OF
@REDELL'S TYPE EXTENSION SCHEME.
$N
$N
2.5- .PREVIEW .OF .OPERATIONS .ON .CAPABILITIES.
$P3
@THE PREVIOUS SECTIONS PROVIDE A BASIS FOR ANALYSING THE NATURE OF
THE OPERATIONS WHICH THE KERNEL MUST SUPPLY IN ORDER TO ALLOW THE
CREATION AND MANIPULATION OF CAPABILITIES.
$P
@FOR SIMPLICITY, SYMBOLIC NAMES ARE USED TO DENOTE CAPABILITIES.
@IN REALITY, A CAPABILITY DESIGNATOR CONSISTS OF A PAIR .<C,D> WHOSE
COMPONENTS SPECIFY, RESPECTIVELY, THE CAPABILITY FOR THE @C-SEG WHERE
THE DESIRED CAPABILITY RESIDES, AND A DISPLACEMENT INDICATING THE
PARTICULAR SLOT WITHIN THE @C-SEG. @A PROCESS SEES ONLY THE SET OF
CAPABILITIES CONTAINED WITHIN THE @I-SEG OF ITS CURRENT DOMAIN.
@THEREFORE, THE FIRST COMPONENT, NAMELY .C, OF A CAPABILITY
DESIGNATOR
CONSISTS OF A DISPLACEMENT RELATIVE TO THE START OF THE @I-SEG OF THE
DOMAIN TO WHICH THE PROCESS IS BOUND.
$P
@IN ORDER TO CREATE A NEW OBJECT, IT IS NECESSARY TO SPECIFY THE
TYPE OF THE OBJECT TO BE CREATED. @THUS, IT IS APPROPIATE TO BEGIN
OUR DISCUSSION WITH TYPE CREATION.
$P
@THE SIZE OF THE TYPE FIELD OF CAPABILITIES AFFECTS, ON THE ONE
HAND, THE SIZE OF CAPABILITIES, AND ON THE OTHER, THE NUMBER OF
DIFFERENT TYPES WHICH THE SYSTEM CAN SUPPORT. @THE PROVISION OF A
RELATIVELY SMALL TYPE FIELD FORCES THE SYSTEM TO TREAT TYPES AS AN
EXHAUSTIBLE RESOURCE. @A MORE CONVENIENT ALTERNATIVE IS TO IMPLEMENT
SUFFICIENTLY LONG TYPE FIELDS TO ACCOMMODATE A PRACTICALLY INFINITE
NUMBER OF TYPE IDENTIFIERS. @THE GENERATION OF TYPE IDENTIFIERS CAN
MAKE USE OF THE MECHANISM WHICH SUPPLIES OBJECT IDENTIFIERS.
@HEREINAFTER, WE ASSUME THAT THE TYPE FIELDS OF CAPABILITIES ARE OF
THE SAME SIZE AS UNIQUE .ID FIELDS [@DE66,@WU74,@RE74,@LA76]. @THE
AUTHORS
OF @HYDRA EMPLOY THIS SCHEME TO DEFINE A VERY ELEGANT
CHARACTERISATION
OF OBJECT TYPES WHICH AVOIDS THE PROVISION OF AN EXPLICIT KERNEL
OPERATION TO CREATE NEW TYPES [@WU74]. @THIS IS ACCOMPLISHED BY
DEFINING THE TYPE ITSELF AS AN OBJECT OF THE DISTINGUISHED TYPE
'TYPE'. @THE TYPE IDENTIFIERS OF CAPABILITIES CAN BE VIEWED AS
FORMING A TREE AS DEPICTED FIGURE 2.5-1. @AN OBJECT IS A TYPE IF ITS
TYPE IDENTIFIER REFERENCES THE ROOT OBJECT; OTHERWISE IT IS A NORMAL
OBJECT.
$P
$V0
@THE CAPABILITY VALUED FUNCTION:
$B0
$T2
.NEW = .CREATE .OBJECT ( .OLD )
$B0
PRODUCES A NEW CAPABILITY. @THE PARAMETER TO THE KERNEL FUNCTION IS
THE CAPABILITY FOR AN EXISTING OBJECT. @THE KERNEL COPIES THE UNIQUE
.ID FIELD OF .OLD INTO THE TYPE FIELD OF THE NEWLY CREATED
CAPABILITY,
PROVIDED THAT THE TYPE FIELD OF .OLD BEARS THE DISTINGUISHED MARK
'TYPE'; OTHERWISE AN ERROR IS SIGNALLED. @THUS, .NEW WILL BE THE
CAPABILITY FOR A NEW TYPE OR THE CAPABILITY FOR A NORMAL OBJECT OF AN
EXISTING TYPE DEPENDING ON WHETHER .OLD REFERENCES THE ROOT OBJECT OR
A TYPE OBJECT CREATED PREVIOUSLY. @THE TYPE CAPABILITY IS USED BY THE
KERNEL TO CONTROL GENERIC OPERATIONS ON TYPES. @CONCRETE EXAMPLES OF
THESE OPERATIONS ARE: CREATION OF NEW INSTANCES OF OBJECTS OF THE
EXTENDED TYPE; .SEAL, .UNSEAL, .CASE, .UNCASE, AMPLIFICATION OF
ACCESS
RIGHTS; ETC. @IN SHORT, THE CREATOR OF THE FULLY PRIVILEGED TYPE
CAPABILITY FOR A GIVEN TYPE IS THE SOLE CONTROLLER OF THE TYPE IN
QUESTION. @IT MAY CREATE DOMAINS WHICH IMPLEMENT OPERATIONS ON THAT
TYPE AND EVEN DISTRIBUTE THE TYPE CAPABILITY TO EMPOWER OTHER DOMAINS
TO CREATE NEW OPERATIONS.
$P
@SUCH A UNIFIED OPERATION IS ENOUGH TO CREATE THE CAPABILITY FOR
ANY NEW OBJECT. @HOWEVER, IT IS NOT SUFFICIENT TO CREATE THE COMPLETE
OBJECT SINCE THE STRUCTURE OF AN EXTENDED OBJECT IS, IN GENERAL, NOT
KNOWN TO THE KERNEL. @IN PRACTICE, THE CREATION OF A NEW EXTENDED
OBJECT OF A GIVEN TYPE, SAY .T, MUST PROCEED IN VARIOUS STAGES.
@FIRST, THE REPRESENTATION OF THE OBJECT IS CONSTRUCTED AND
INITIALISED. @THEN, THE KERNEL IS REQUESTED TO MANUFACTURE A
CAPABILITY FOR THE NEW OBJECT. @THIS SECOND OPERATION IS PERFORMED BY
THE KERNEL ONLY IF THE CREATING DOMAIN PRESENTS THE TYPE CAPABILITY
FOR TYPE .T. @FINALLY, THE NEW CAPABILITY CREATED BY THE KERNEL MUST
BE ASSOCIATED WITH THE CAPABILITY FOR THE REPRESENTATION OF THE
OBJECT. @THE LAST TWO ACTIONS CAN BE COMBINED INTO A SINGLE KERNEL
OPERATION OF THE FORM:
$B0
$T2
.NEW = CREATE EXTENDED OBJECT ( .CTYPE , .CREP)
$B0
WHERE .CTYPE IS THE TYPE CAPABILITY FOR TYPE @T AND .CREP IS THE
CAPABILITY FOR THE REPRESENTATION OF THE EXTENDED OBJECT. @THE KERNEL
CREATES A COMPLETELY NEW CAPABILITY FOR THIS NEW INSTANCE OF AN
OBJECT OF TYPE .T. @ACCORDING TO THE TYPE EXTENSION SCHEME WHICH IS
BEING USED, THE KERNEL MODIFIES THE TYPE FIELD AND/OR THE ACCESS
RIGHTS FIELD OF CAPABILITY .CREP OR CONSTRUCTS A COMPLETELY NEW
CAPABILITY. @IN THE LATTER CASE, THE LOCATION FIELD OF THE NEW
CAPABILITY IS GIVEN THE VALUE OF THE UNIQUE .ID FIELD OF CAPABILITY
.CREP.
$P
@THE COUNTERPART OF THE ABOVE OPERATION CAN BE DESCRIBED BY:
$B0
$T2
.CREP = OBTAIN REPRESENTATION .$(CTYPE , .CEXT)
$B0
WHERE .CTYPE IS THE TYPE CAPABILITY FOR TYPE @T AND .CEXT IS THE
CAPABILITY FOR AN EXTENDED OBJECT WHICH MUST BE OF TYPE .T. @THE
KERNEL FUNCTION RETURNS AS VALUE THE CAPABILITY WHICH PERMITS ACCESS
TO THE REPRESENTATION OF THE EXTENDED OBJECT. @IN THE TYPE EXTENSION
SCHEMES DISCUSSED IN THE PREVIOUS SECTION, THE NAME OF THE FUNCTION
COULD HAVE BEEN: AMPLIFY [@JO74], .UNCASE [@FE74] AND .UNSEAL [@RE74].
$P
@RESOURCE SHARING BETWEEN DOMAINS AND PROCESSES AND THE PASSING OF
PARAMETERS BETWEEN DOMAINS IS SIMPLIFIED WITH THE PROVISION OF A
KERNEL OPERATION OF THE FORM:
$B0
$T2
COPY ( .OLD , .NEW)
$B0
WHICH PRODUCES IN .NEW AN IDENTICAL COPY OF THE CAPABILITY GIVEN IN
THE FIRST PARAMETER. @ASSUMING THAT THE OPERATION IS IMPLEMENTED IN
HARDWARE, HENCE AVAILABLE TO EVERY DOMAIN, THE RIGHT TO COPY A
CAPABILITY IS RESTRICTED BY THE ACCESS RIGHTS OF THE CAPABILITY FOR
THE @C-SEG WHERE THE ORIGINAL CAPABILITY IS STORED. @FOR EXAMPLE, THE
COPY OPERATION CANNOT BE PERFORMED ON A @C-SEG WHICH DOES NOT ALLOW
READ ACCESS.
$P
@THE REVOCATION PROBLEM ARISES WITH THE FREE COPYABILITY OF
CAPABILITIES IN CONJUNCTION WITH VARYING DEGREES OF TRUST BETWEEN
DOMAINS. @A DOMAIN WHICH PASSES A COPY OF AN OBJECT'S CAPABILITY TO
ANOTHER DOMAIN MAY BE FACED WITH THE PROBLEM OF WITHDRAWING ACCESS
RIGHTS TO THE OBJECT AT A LATER TIME, WHEN THE RECEIVER OF THE FIRST
COPY MAY HAVE PRODUCED FURTHER COPIES OF THE CAPABILITY AND
DISTRIBUTED SOME OF THEM TO OTHER DOMAINS. @REVOCATION OF ACCESS
RIGHTS HAS BEEN DISCUSSED IN MOST CAPABILITY SYSTEMS; IT IS BASED ON
DIFFERENT WAYS OF IMPLEMENTING INDIRECT ACCESS TO CAPABILITIES.
CAPABILITY FOR AN OBJECT @WE EXPOSE SEVERAL APPROACHES TO REVOCATION
MAINLY FOR THE SAKE OF COMPLETENESS. @THE PROBLEM IS DISCUSSED
EXTENSIVELY IN [@RE74A].
$P
@A STRAIGHTFORWARD APPROACH TO REVOCATION OF ACCESS RIGHTS IS TO
IMPOSE A DOMAIN BETWEEN THE CAPABILITY TO BE REVOKED AND THE USER OF
THE CAPABILITY. @IN OUR TERMINOLOGY, AN EXTENDED OBJECT IS
CONSTRUCTED WHOSE REPRESENTATION CONTAINS THE CAPABILITY TO BE
REVOKED. @THE DESIGNER OF THE EXTENDED TYPE - THE DOMAIN WHICH
ANTICIPATES THE NEED TO REVOKE ACCESS AT A LATER TIME - RESERVES
OPERATIONS WHICH DIRECT THE IMPLEMENTOR TO REFUSE TO PERFORM
SUBSEQUENT ACTIONS TO ACCESS THE CAPABILITY FOR THE EXTENDED OBJECT.
@THIS IS AN EXPENSIVE SCHEME WHICH CAN BE USED ONLY IN PECULIAR
SITUATIONS IN SYSTEMS WHICH DO NOT SUPPORT EXPLICIT REVOCATION
MECHANISMS.
$P
@ANOTHER REVOCATION SCHEME CONSISTS IN ENCLOSING THE CAPABILITY
WHOSE ACCESS RIGHTS ARE TO BE REVOKED WITHIN A @C-SEG ALLOWING ONLY
INDIRECT ACCESS; I. E., THE CAPABILITIES ENCLOSED IN THE INDIRECT
ONLY @C-SEG CANNOT BE COPIED OUT. @REVOCATION CONSISTS IN REMOVING
THE
CAPABILITY FROM THE INDIRECT ONLY @C-SEG. @IN THIS CASE, THE
DISADVANTAGE LIES IN THE PROLIFERATION OF SMALL CAPABILITY SEGMENTS
USED EXCLUSIVELY TO REVOKE ACCESS TO OBJECTS. @THERE ARE ADDITIONAL
PROBLEMS RELATING TO THE ADDRESSING OF SUCH CAPABILITIES. @THE
CAPABILITY DESIGNATOR FOR A REVOCABLE CAPABILITY BECOMES, NOT A PAIR
.<C,D> BUT A CHAIN <( $.$.$. .(<(<C,0>),0>), $.$.$. .D>.
$P
@IN .NCS, REVOCATION IS INTEGRATED WITH TYPE EXTENSION AS DESCRIBED
IN SECTION 2.4. @ACCESS TO EVERY OBJECT TAKES PLACE THROUGH A CHAIN
OF CAPABILITIES, ALL OF WHICH ARE CENTRALISED IN THE SYSTEM MAP.
@THEREFORE, REVOCATION DEVOLVES INTO ESTABLISHING A DISTINGUISHED
TYPE
USED SOLELY FOR REVOCATION PURPOSES. @IN THE PROCESS OF FOLLOWING THE
CHAIN FROM THE CAPABILITY FOR AN EXTENDED OBJECT TO THE CAPABILITY OF
THE REPRESENTATION OF THE OBJECT, THE PROTECTION MECHANISM DETECTS
THE DISTINGUISHED TYPE. @THE ACCESS RIGHTS FIELD OF THE CAPABILITY OF
THE DISTINGUISHED TYPE IS USED AS ONE OF THE OPERANDS OF AN .AND
OPERATION. @THE OTHER OPERAND IS TAKEN FROM THE ACCESS RIGHTS FIELD
OF THE NEXT CAPABILITY IN THE CHAIN. @THE PROCESS IS REPEATED IF THE
NEW LINK IS ALSO A MEMBER OF THE DISTINGUISHED TYPE. @OTHERWISE, THE
ACCESS RIGHTS RESULTING FROM THE SEQUENCE OF .AND OPERATIONS IS USED
TO VALIDATE ACCESS TO THE OBJECT. @THIS IS COMBINED WITH THE
PROVISION OF THE KERNEL OPERATION:
$B0
$T2
REVOKE ( .CAP , M )
$B0
WHERE .CAP IS A CAPABILITY FOR AN OBJECT WHICH MUST BE OF THE
DISTINGUISHED TYPE AND M IS A MASK WHICH INDICATES THE ACCESS BITS IN
THE ACCESS RIGHTS OF .CAP WHICH SHOULD BE REVOKED. @THE REVOKE
OPERATIONS AND OPERATIONS TO CREATE OBJECTS OF THE DISTINGUISHED TYPE
ARE PUBLICLY AVAILABLE. @THE COMBINATION OF FACILITIES OF .NCS
PROVIDE
SUBSTANTIAL FLEXIBILITY IN THE DISTRIBUTION AND REVOCATION OF ACCESS
RIGHTS IN AN ENVIRONMENT WHERE THE DEGREEE OF TRUST BETWEEN DOMAINS
VARIES DYNAMICALLY [@RE74B].
$P
@FINALLY, ANOTHER ALTERNATIVE TO THE SUPPORT OF REVOCATION IS TO
INCLUDE A COPY BIT, INITIALLY 1, IN EVERY CAPABILITY [@GR72]. @AFTER
THE COPY BIT IS SET TO 0, THE COPY OPERATION REFUSES TO SATISFY THE
REQUEST. @THE COPY BIT CAN BE USED BY THE DISTRIBUTOR TO ENSURE THAT
THE CAPABILITY IS NOT SCATTERED BY THE RECEIVER. @SOME OF HE
DRAWBACKS OF THIS SIMPLE APPROACH TO REVOCATION ARE: @THE OWNER OF
THE
OBJECT IS FORCED TO KEEP TRACK OF THE LOCATION OF EVERY REVOCABLE
CAPABILITY WHICH ORIGINATED FROM ITS ADDRESS SPACE. @THE RECEIVER
MUST NOT BE ABLE TO PREVENT THE DISTRIBUTOR FROM ACCESSING THE SLOT
WHERE THE REVOCABLE CAPABILITY IS CONTAINED; THUS, IT REMAINS UNDER
CONTROL OF THE DOMAIN WHICH OWNS THE OBJECT. @IF THE PASSING OF
PARAMETERS BETWEEN DOMAINS IS BASED ON COPYING, THE NON-COPYABLE
CAPABILITY MAY BE USELESS TO THE RECEIVER DOMAIN. @IN SUMMARY, THE
TECHNIQUE AFFORDS VERY LITLLE FLEXIBILITY.
$P
@THE DESTRUCTION OF OBJECTS BASED ON REFERENCE COUNTS AND GARBAGE
COLLECTION WAS OUTLINED IN SECTION 2.1. @THE OPERATIONS WHICH MUST BE
PROVIDED BY THE KERNEL TO EMPOWER IT TO DESTROY SYSTEM OBJECTS ARE
DEPENDENT ON THE RECOVERY PROCEDURE AS WELL AS IN THE SYSTEM'S POLICY
FOR ERASING CAPABILITIES FROM THE CAPABILITY SEGMENTS IN WHICH THEY
RESIDE. @CLEARLY, THE COPY OPERATION CAN BE USED TO ERASE
CAPABILITIES WHICH ARE NO LONGER USED. @HOWEVER, IS ADVISABLE TO
INCLUDE AN EXPLICIT KERNEL OPERATION OF THE FORM:
$B0
$T2
FORGET ( @C )
$B0
WHICH SIMPLY ERASES THE CAPABILITY SLOT SPECIFIED IN THE PARAMETER.
@MORE STRICTLY, IT SUBSTITUTES THE EXISTING CAPABILITY FOR THE
CAPABILITY OF THE DISTINGUISHED .NIL OBJECT. @THIS IS COMBINED WITH
THE REQUIREMENT THAT THE DESTINATION OF THE COPY OPERATION BE
INITIALLY EMPTY TO REDUCE THE LIKELYHOOD OF UNINTENTIONAL ERASURE OF
CAPABILITIES.
$P
@IN THE REFERENCE COUNT APPROACH, THE OPERATIONS REQUIRED TO
DESTROY AN OBJECT AND RECOVER THE PHYSICAL RESOURCES WHICH IT
OCCUPIES ARE AN INHERENT PART OF THE KERNEL FORGET OPERATION. @IN
CONTRAST, GARBAGE COLLECTION REQUIRES THE DEFINITION OF A KERNEL
OPERATION OF THE FORM:
$B0
$T2
MARK ( @C )
$B0
WHICH MARKS THE MAP ENTRY FOR THE OBJECT WHOSE CAPABILITY IS GIVEN IN
.C. @THE OPERATION IS USED TO MARK ALL THE OBJECTS WHICH CAN BE
REACHED FROM CAPABILITIES CONTAINED IN A WELL DEFINED SET OF
CAPABILITY SEGMENTS USED AS SYSTEM DIRECTORIES. @NOTE THAT THE KERNEL
MUST HAVE 'MARK' ACCESS TO ALL OBJECTS; E. G. @C-SEG'S AND @I-SEG'S,
WHOSE REPRESENTATIONS CONTAIN OTHER CAPABILITIES. @ALL UNMARKED
ENTRIES AND, IN THE CASE OF BASIC OBJECTS, THE PHYSICAL RESOURCES
WHICH THEY OCCUPY CAN BE COLLECTED AT A LATER STAGE.
$P
@IN ADDITION TO THE AUTOMATIC DESTRUCTION OF OBSOLETE OBJECTS, IT
IS IMPORTANT, FOR EFFICIENCY CONSIDERATIONS, TO SUPPLY AN EXPLICIT:
$B0
$T2
DESTROY ( @C )
$B0
KERNEL OPERATION. @THE EFFECT OF THE OPERATION IS TO ERASE THE SLOT
CONTAINING @C AND TO RECOVER THE ASSOCIATED MAP ENTRY. @IN THE CASE
OF
BASIC OBJECTS, THE PHYSICAL RESOURCES USED BY THE REPRESENTATION ARE
ALSO RECLAIMED. @IN OTHER WORDS, THE OPERATION PERFORMS THE SAME
ACTIONS AS THOSE REQUIRED WHEN THE REFERENCE COUNT REACHES THE VALUE
ZERO OR DURING THE COLLECTION STAGE OF AN UNMARKED OBJECT. @INCREASED
EFFICIENCY FOLLOWS FROM THE REDUCTION IN THE FREQUENCY OF GARBAGE
COLLECTION IN ONE CASE. @IN THE OTHER, THE KERNEL NEED NOT WAIT UNTIL
ALL THE CAPABILITIES FOR A GIVEN OBJECT ARE FORGOTTEN BEFORE
RECLAIMING THE PHYSICAL RESOURCES. @CONSEQUENTLY, OVERALL RESOURCE
REQUIREMENTS MAY BE AMELIORATED. @IT IS IMPRTANT TO NOTE THAT THE
DESTRUCTION OF AN OBJECT SHOULD NOT IMPLY DESTRUCTION OF OBJECTS
WHOSE CAPABILITIES ARE CONTAINED WITHIN THE REPRESENTATION OF THE
OBJECT TO BE DESTROYED. @FOR EXAMPLE, WHEN A DOMAIN IS DESTROYED, THE
CAPABILITIES STORED IN ITS @I-SEG ARE FORGOTTEN, BUT THEIR ASSOCIATED
MAP ENTRIES ARE NOT MODIFIED. @THIS IS AN OBVIOUS IMPLICATION OF THE
OBSERVATION THAT THE POSSESSOR OF THE CAPABILITY FOR AN OBJECT NEED
NOT BE THE OWNER OF THE SET OF OBJECTS COMPRISING ITS REPRESENTATION.
$P
@NATURALLY, THE PRIVILEGE TO DESTROY AN OBJECT MUST BE CONTROLLED.
@IN SOME SYSTEMS, A DESTROY ACCESS BIT IS CONTAINED WITHIN EVERY
CAPABILITY [@WU74,@FE74]. @THIS IS CERTAINLY NECESSARY IN THE CASE OF
BASIC OBJECTS SUCH AS @C-SEG'S AND @N-SEG'S. @THE RIGHT TO CREATE AND
DESTROY OBJECTS OF THOSE TWO TYPES IS PUBLICLY AVAILABLE,
CONSEQUENTLY, THE RIGHT TO DESTROY THEM MUST BE CONTROLLED
INDIVIDUALLY. @ON THE OTHER HAND, DESTRUCTION OF AN EXTENDED OBJECT
OUGHT TO BE ACCOMPANIED BY THE EXPLICIT DESTRUCTION OF THE OBJECT'S
COMPONENTS; OTHERWISE THE THE GAIN OF THE DESTROY OPERATION WOULD BE
MINIMAL. @RECALLING THAT THE POSSESSOR OF THE CAPABILITY FOR AN
EXTENDED OBJECT, THE USER DOMAIN, IS UNAWARE OF THE OBJECT'S
STRUCTURE, IT IS NOT UNREASONABLE TO CONTROL DESTRUCTION BY AN ACCESS
BIT CONTAINED IN THE TYPE CAPABILITY. @THUS, THE DESTRUCTION OF AN
EXTENDED OBJECT CAN BE IMPLEMENTED AS ONE OF THE EXTENDED OPERATIONS
ON THAT TYPE.
$P
@A FINAL ASPECT OF OBJECT DESTRUCTION IS THAT THE PROTECTION
MECHANISM MUST BE ABLE TO COPE WITH CAPABILITIES MADE OBSOLETE AS A
SIDE EFFECT OF THE DESTROY AND REVOKE OPERATIONS. @IN THE FIRST
PLACE, THE .UNSEAL OPERATION MUST TAKE THIS POSSIBILITY INTO ACCOUNT.
@IN ADDITION, WITH THE USE OF GENERALISED SEALING, CHAINS OF
CAPABILITIES WHICH ARE EVENTUALLY BROKEN MAY APPEAR. @MOREOVER, EVERY
CAPABILITY IN THE CHAIN OCCUPIES A MAP ENTRY. @NOTE THAT THESE MAP
ENTRIES CANNOT BE RECOVERED BY A GARBAGE COLLECTOR WITHOUT
INTRODUCING A COMPLEX STRUCTURE OF BACK POINTERS IN THE GARBAGE
COLLECTION MARK PHASE. @A FURTHER KERNEL OPERATION OF THE FORM:
$B0
$T2
EXERCISE ( @C )
$B0
MUST BE PROVIDED BY THE KERNEL FOR THIS PURPOSE. THE EXERCISE
OPERATION 'TOUCHES' THE CAPABILITY @C AS IF IT WERE INTENDING TO
PERFORM AN OPERATION ON THE OBJECT. @WHEN THE KERNEL DETECTS THE
ABSENCE OF A VALID LOCATION FIELD IT CAN RECOVER THE MAP ENTRY.
$E