UNIVERSITY MATHEMATICAL LABORATORY, CAMBRIDGE

Cambridge Supervisor : Planning Document 11
The File Dictionary System
I - General Description

1. Introduction

This scheme supersedes that outlined in Planning Document 6. The objectives listed in §1 of P.D.6. still apply.

2. How the user accesses the file

Before outlining the dictionary system, it is as well to describe how the user will get at his files since this affects the philosophy behind the dictionary. Following Planning Document 2, a file can be either in Character mode or Binary mode. No indication of the mode of the file is carried internally: the distinction is solely one of whether the character I/O extracodes or the backing store extracodes are used to access the file. In the former case the unit is the character or the line ("record" in the Atlas jargon), in the latter case the unit is the 512-word block. It is permissible, and sometimes useful, to write a file in one mode and read it in the other.

File names are of the usual Titan form a/b/c, where a,b,c, are alphameric strings of not more than 8 characters. a identifies the user (but see below for a precise definition of user) and b,c are the user's name for his file. In many contexts, a may be implicit, and the file name will just be a two-part name, b/c.

The programmer is provided with extracodes for associating stream numbers or backing-store logical device numbers with files. Informal definitions of these are:

1. "Create input stream n from file a/b/c". The file can then be read by selecting stream n and using the read character or read line extracodes.
2. "Create output stream n as file a/b/c". The file can then be written by selecting stream n and using the write character or write line extracodes.
3. An alternative way of writing to a file is by using two extracodes:
   1. "Create output stream n : I will tell you what to do with it later", and at a subsequent point in the program
   2. "Create file a/b/c from output stream n".
4. "Create backing store device n as file a/b/c". The file can then be read or written in blocks of 512 words by use of the backing store extracodes.

The effect of these extracodes is possibly to create a file, and to open it. Files are closed at the end of a program or in response to a specific command, e.g. the FILE command creates, opens, writes and closes the file. "Anonymous" streams (i.e. streams coming in from a console or tape reader, or being produced by a program with unspecified destination) are entirely the affair of the stream handler. The File Dictionary Program only has cognizance of them when a FILE command is given.

"Create input stream from file" will alarm if the file does not exist. "Create file from output stream" will always create a new file. If a file of the same name exists already it will be deleted. (It may be desirable to delay this deletion for a short time, say 15 min., to allow the programmer to retrieve the situation should he have made a careless error, such as editing the wrong file.) "Create backing store device as file" will use an existing file if one of that name exists, and will create a new file otherwise.

Other facilities available to the user are

1. delete file
2. rename file
3. change status of file (see below).

3. Restrictions on File Access

Obviously access to files must be restricted in some way. What is required is a system that permits sharing of files without excessive complications, yet guarantees security to private files. For example, everyone must be able to get at library routines easily, but only the administration may have access to the logging and accounting files. The philosophy of the system envisaged is that sharing of files on a read-only basis is easy to arrange, and does not involve a lot of work for the file dictionary program. Sharing of files on other than a read-only basis is permitted, but involves more work both in setting up the files and in dynamic checking. We return to this subject in §5 below.

4. Structure of the Dictionary

4.1 Terminology.

This is important.

A user is defined as a person who can "log-in" to the system, or who can put jobs in via the queue, and has access to the filing system. For purposes of the filing system, users may be split into groups, a group consisting of two or more users. Note that the system allows a particular user to be a member of more than one group.

4.2 Structure of the Dictionary

The dictionary system is made up of:

1. a main file directory (MFD)
2. a number of user file directories (UFD's)
3. a number of communal file directories (CFD's)
4. a group and user identification file (GUF).

There is one UFD per user: the user is said to own the files in his UFD. (A UFD entry always points to a file, not another directory). A CFD is for most purposes the same as a UFD, the only difference being that they are associated not with a real user but a notional user (e.g. "the CPL group"). The distinction only becomes important when we consider the question of restrictions on access. The MFD contains one entry per user (real or notional), the entry pointing to the UFD (or CFD).

The GUF contains one entry for each user (real, not notional), and one entry for each group. The entry contains interalia, the following items:

1. privileges e.g. use of special facilities
2. allocations (disc space, time, etc)
3. logging information (summarised)
4. for a group, a list of names of members of the group
5. a list of UFD's and CFD's to which the user or group is allowed access, with restrictions on access for each.

The GUF is consulted in two circumstances. The first is when a user attempts to log in, to determine if he is allowed access, and if so, to which files he is allowed access. The second is when he logs out, when the logging information must be updated.

5. File Status and Restrictions

The operations that can be carried out on a file are

1. read it
2. write to it (i.e. append information)
3. delete it
4. change its status (e.g. set "write inhibit")

Change of status implies writing to the UFD. If we regard the UFD as a file, the operations that can be carried out are

1. search it (for a particular entry)
2. read it (to print it, say)
3. write to it (to add items or change items)
4. delete it (in very special circumstances).

Any or all of these operations may be restricted. We must also, however, consider the different categories of people who may want to carry out these operations. These are

1. the owner
2. a "part-owner" i.e. a user or group whose GUF entry specifies that access to this UFD is allowed
3. a user who has the "key" to unlock the file (see below)
4. the system
5. any user.

We require a flexible scheme whereby the restriction on each operation can be made to depend on who is requesting it, independently of restrictions on other operations: thus we associate with a file (in the UFD) a status matrix:

	Owner	Part-owner	Key-owner	System	Anyone
Read
Write
Delete
Change Status

An element a_ij of the matrix is a 1 if the action of row i is allowed to the class of user in column j. Certain elements of the matrix may be constrained to be always zero. Note that "owner" is not a meaningful concept for files in a CFD. An overall restriction on access to files in a UFD can be specified in the GUF: this is combined with the status matrix of the file by an "OR".

6. Shared Files

It is instructive at this point to summarize the ways in which files can be shared.

1. Communal directories. The only difference between a CFD and a UFD is that the files in a CFD do not have a unique owner. CFD's are provided so as to give an easy naming scheme for the common files of a group of users.
2. "Library" files. The status matrix may indicate that reading is permitted to anyone.
3. Group-sharing. By suitable entries in the GUF, a group of users may be given access to each others' UFD's.
4. Key sharing. The status matrix may indicate that access is allowed only to those who can quote the correct key. The key counts as part of the status of the file, and can be changed by anyone who is allowed to change status.

7. The mechanism of File Access

A request for access to a file involves three pieces of information:

1. the file name a/b/c
2. the requesting user's name n
3. the operation required.

The first step is to find the UFD, using the first part of the file name a to index the MFD. The next step is to see if the required operation is freely available (i.e. not prohibited to "others"). If so, no more checking is required. If not, the next step is to test if a = n. If so, then the operation required is tested against the "owner" prohibitions in the status matrix. If not, n is examined to see if it is permissible for user n to access this UFD. (See below for the mechanism by which this is achieved.)

8. Access Trap

The UFD can specify that if an attempt is made to access a file a trap is to occur. This can be set by the system to indicate that the file is not available on disc.

9. The File Dictionary Control Program

The FCP is written as an ordinary program. It will, however, reside permanently in core (in the first instance, at least) and will be specially treated by the Supervisor. Associated with the program is a communication region: the FCP takes a request from this region, processes it, and returns output data (if any) to the communication region. It then obeys a special extracode which informs the supervisor that it has finished. In the FCP, this extracode is followed by a jump back to the beginning, so that it appears to be a continuously running program. In fact, each time it returns control to the supervisor it will be halted, and restarted when there is another request to be serviced. It has certain other privileges concerning access to the disc. The communication region additionally contains a half-word which indicates whether the FCP is busy or free.

The FCP needs to communicate with the disc-allocation program. This can be done by extracode: the operations needed are:

1. get next block (element) of chain c,
2. write next block of chain c,
3. take last element of chain c as garbage,
4. take the whole of chain c as garbage.

It also needs an extracode to obtain the identification of the current user, and the list of UFD's to which he is allowed access. It is envisaged that this list will be obtained from, or via, the OP base.

10. Calls on the FCP

The FCP is called in by extracodes. These are

1. create input stream from file,
2. create output stream to file,
3. create backing store device as file,
4. delete file,
5. rename file,
6. change status of file.

11. Requests and responses

In general, a request to the FCP will include

1. user's name
2. a file name,
3. action required.

The response can be

1. "OK", with relevant information e.g. position of file on disc,
2. "NO", i.e. request is illegal,
   or
3. "WAIT", i.e. request cannot be serviced at present (e.g. deletion request when somebody else is still using the file).

12. Interlocks

Associated with each UFD entry is an interlock word. This is zero if nobody is currently referring to the file. If it is non-zero it can indicate

1. writing interlock: someone is writing to the file at present. This holds up any reading or writing request,
2. writing request interlock: someone has requested writing but has been held up. No further reading or writing requests can be accepted,
3. reading interlock: someone is reading the file at present. This holds up any writing request.

(a) and (b) can each be single digit markers. (c) is a count, which is incremented by one each time the file is opened for reading, and is decreased by one each time the file is closed. The question of freeing programs halted for interlock reasons needs thought.

13. Summary of External Requests

We can now summarize the requests that can come to the FCP from outside, with a brief indication of action and response. All requests cause a check on restriction, and may produce the response "NO".

Request	Action if accepted	Response
Open file for reading	Find track Increase read interlock	Track number or WAIT
Open file for writing	Find track Set write interlock or write request interlock	Track number or WAIT
Close file after read	Adjust interlocks	-
Close file after write	"        "	-
Delete file	Delete	Nil or WAIT
Re-name file	Re-name	Nil or WAIT
Change file status	Change	Nil or WAIT
Create entry in UFD with specified track number	Make entry	-
Create entry in UFD without track number	Make entry	-
Add track number to UFD entry	Amend entry	-
Change track number of UFD entry	Amend entry	-

It would be convenient to keep a file which had been deleted (or re-named) for a short period so that the user could recover from a mistake such as accidental deletion. This, however, need not be implemented in the first place. "Open file for writing" has two options: if the file does not exist one can be created or a fault can be indicated.

14. Operations on File Dictionaries, etc.

1. The MFD. The administration can request the FCP to perform the following operations on the MFD:
   1. create new entry (and new UFD)
   2. delete entry (and UFD),
2. The UFD's. Apart from the creation and deletion of UFD's already mentioned, all other operations are in response to users requests as listed in §5.
3. The GUF. This is manipulated by administrative programs using the normal user's mechanisms for operation on files.

15. Passwords

It is suggested that each user's password should be in a separate file. The password file for user a will be accessed via his file dictionary in the normal way: it will have status "read by system or owner, write by owner only, status change forbidden". Thus the user can change his password as often as he pleases.

DWB
11 February 1966

Copyright © 1966 University of Cambridge Computer Laboratory. Distributed by permission. Thanks to Barry Landy, Roger Needham and David Hartley for giving permission to distribute these documents. Thanks to Barry Landy for lending me the paper document from which this was scanned. Any typographical errors probably arose in the course of OCR.

Previous Planning Document: 10. Software for the Titan/PDP-7 link, C.A.L., 2 December 1965
Next Planning Document: 12. Organizational Extracodes for Input/Output, B.L., 9 February 1966
Return to Cambridge Supervisor Planning Documents
Return to CUCPS TITAN page
Return to CUCPS home page
Return to University of Cambridge home page