871e2986123348df172ee63d0fb87c0a81e1da6b
[its.git] / sysdoc / locks.108
1                                                                 -*- Text -*-
2 Copyright (c) 1999 Massachusetts Institute of Technology
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or (at
7 your option) any later version.
8
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
17 ------------------------------
18
19
20
21         This file contains documentation for both the LOCK device,
22         and the locked switch list and critical routine features.
23
24
25
26 THE LOCK DEVICE.        [ In ITS version 1630 and later ]
27
28 The LOCK device provides a simple and foolproof technique for interlocking
29 between jobs.  While not as efficient as using an AOSE-style switch in
30 shared memory, the LOCK device is much easier to use and is suitable for
31 use in those situations where a lock is only rarely seized, and is only
32 held for brief periods of time.
33
34 Locks are identified using a single SIXBIT word as a lock name.  (Actually,
35 and non-zero 36-bit word can be used.)  A job can lock the FOO lock by
36 opening "LOCK:FOO" for output.  The LOCK device ignores any second filename
37 or directory name you might supply.  The lock will be released when the
38 channel is closed.  As long as the job keeps the lock channel open, any
39 other attempts to lock the same lock result in a %ENAFL (FILE LOCKED)
40 error.
41
42 When opening the LOCK device, bit 1.4 indicates that the opener wishes to
43 hang waiting for the lock, rather than receiving a %ENAFL error.
44
45 It is also possible to receive a %EFLDV (DEVICE FULL) error when opening
46 the LOCK device if the table of currently held locks that ITS maintains
47 overflows.
48
49 Here is the registry of all lock names.  Any program that uses the LOCK
50 device should register the name of the locks it uses here.
51
52         Name            Purpose
53         ------          ------
54         NUTMEG          This lock is used in an example later
55                         on in this file.
56
57         MBXxxx          The set of locks whose names start with the
58                         characters "MBX" are used by COMSAT and GMSGS to
59                         coordinate access to mailboxes.  The algorithm for
60                         computing the lock for the mailbox named
61                         SNAME;NAME1 NAME2 is:
62
63                                 MOVE A,NAME1
64                                 ROT A,1
65                                 ADD A,NAME2
66                                 ROT A,1
67                                 ADD A,SNAME
68                                 IDIVI A,777773          ; Largest prime < 1,,0
69                                 HRLI B,(SIXBIT /MBX/)   ; Result in B = A + 1
70
71 \f
72
73
74 THE LOCKED SWITCH LIST AND CRITICAL ROUTINE FEATURES.
75
76 There is an obvious technique for interlocking between jobs on
77 the PDP-10 - namely, the use of AOSE - which has been unusable
78 under ITS simply because a job might be killed while it had a
79 switch locked, thus causing the switch to remain locked forever.
80 These implemented features allow that problem, and the similar
81 problem of system crashes while a switch in a permanent data
82 base is locked, to be solved without any loss of efficiency.
83
84 The locked switch list feature allows a program to maintain a
85 list of switches which it has locked, so that ITS can unlock
86 them when the job is killed (or logs out, or is gunned)
87 or is reset (for example, $l'd by DDT). The critical routine
88 feature allows the program to cause ITS to perform certain
89 actions if the job is killed or reset with the PC in a specified range.
90
91 These features do not prevent bugs in the programs accessing
92 a switch from causing the switch not to be unlocked. They make
93 possible successful interlocking but do not guarantee it.
94
95
96 A. THE DEFINITIONS OF THE FEATURES.
97
98 These features are all activated by setting the %OPLOK bit in
99 the .OPTION USET-variable to 1 (This bit is 1000,,). If that is
100 not done, words 43 and 44 are not in any way special. Also, the
101 addresses used do not have to be 43 and 44; that is merely their
102 default values. The actual adresses used are relative to the
103 contents of the .40ADDR USET-variable, which initially contains
104 40 . If .40ADDR were set to 1000, locations 1003 and 1004 would
105 used. Of course, all system actions that normally use locations
106 40, 41 and 42 would use 1000, 1001 and 1002.
107
108  1. THE LOCKED SWITCH LIST.
109
110 When the %OPLOK bit is 1, location 43 is taken to be the pointer
111 to the job's locked switch list. The list pointer
112 should either be 0, meaning the list is empty, or the address of
113 the first two-word switch block. The format of a switch block is
114 as follows:
115
116  1st word:      the switch, or, if the indirect bit is set in
117                  the second word, the address of the switch
118                  (multiple indirection is not allowed).
119  2nd word:      the RH holds the address of the next switch
120                  block, or 0 (this is the CDR of the list).
121                 the LH holds the instruction to be executed to
122                  unlock the switch. The index field is ignored.
123                  The instruction must either be an AOS or SOS
124                  with 0 in the AC field, a logical instruction
125                  (such as SETAM, IORM, SETOM, ANDCAM), a halfword
126                  instruction, a MOVEM, MOVNM, MOVSM, MOVMM,
127                  ADDM or SUBM. The AC will never be modified
128                  even if the instruction
129                  says to do so. If the LH is 0, the instruction
130                  SETOM is used, as the most common choice.
131
132 When the job is killed or reset, if the locked switch list is
133 not null, the system looks at the first switch block, unlocks
134 the switch by executing the unlock instruction with the switch
135 word as its memory argument, and the copying the RH of the
136 second word of the switch block into 43 to remove the block
137 from the list (this makes sure that no switch is ever unlocked
138 twice due to PCLSR'ing).
139 This procedure is repeated until 43 contains 0,
140 thus unlocking all the switches in the list. Obviously since the
141 job's pages are about to be discarded this action will have no
142 consequence unless the switches are in pages shared with other
143 jobs.
144
145 If in the process of unlocking the switches
146 the system tries to read from a nonexistent page or write in a
147 pure page, it gives up entirely, ignoring the rest of the
148 locked switch list, and also the critical routine table. Also
149 if the end of the list is not reached after 512. switch blocks
150 have been unlocked, the system gives up.
151
152  2. THE CRITICAL ROUTINE TABLE.
153
154 When the %OPLOK bit is 1, location 44 is considered to be an
155 AOBJN pointer to a table of critical sections of code, which are
156 involved in the manipulation of switches or the locked switch
157 list. The table should be a vector of two-word entries, one for
158 each critical section of code. The first word of each entry
159 should give the boundaries of the critical section: the left
160 half should have the the address of the first instruction of the
161 critical section; the right half, the address of the first
162 instruction after the critical section. The second word of the
163 entry should have an unlock instruction, subject to the same
164 restrictions as for locked switch list unlock instructions,
165 the only difference being that the address field of the
166 instruction is taken from the RH of the word, as one would expect,
167 whereas in unlock instructions in switch blocks the address of
168 the switch block is used, and the RH of the word is the CDR.
169 Examples will make all this clear.
170
171 If the job is killed or reset while the PC is in the range
172 specified by a critical routine table entry, the switch
173 specified by the entry will be unlocked by executing the unlock
174 instruction. It is possible
175 for the ranges specified by two entries to overlap; to make sure
176 that no entry is processed more than once, the system updates 44
177 as it processes each entry.
178
179 As with the switch list unlocking, the system abandons the whole
180 thing if it needs to read or write in a page that won't allow it.
181
182  3. FATAL INTERRUPTS IN TOP-LEVEL JOBS WITH LOCKED LOCKS.
183
184 When the %OPLKF bit in a job's .OPTION variable is set to 1, and if the job
185 is the top-level job of a non-disowned tree, then if that job ever receives
186 a fatal interrupt its locks will be unlocked by the system job as part of
187 the process of detaching it.  Thus fatal interrupts in network servers,
188 toplevel DDTs, system demons, etc. that happen while those jobs have shared
189 databases locked, will not keep other jobs blocked waiting for someone to
190 gun down the corpse.  
191
192 The reason you might not want to set %OPLKF is that after a jobs locks are
193 unlocked, it will not in general work to proceed the job.  Such a detached
194 corpse will only be good for autopsy, not revival.
195
196
197 B. USING THE FEATURES FOR SWITCHES IN A SHARED PAGE.
198
199 In this section it is assumed that the page is not part of a
200 disk file, and will not survive through a system crash. That
201 means that it is not necessary to worry about unlocking switches
202 that are locked at the time of a system crash.
203
204  1. LOCKING AN AOSE-STYLE SWITCH.
205
206 The proper routine to use for locking a switch follows:
207 The address of the two-word switch block is assumed to be in A.
208
209 LOCK:   AOSE (A)                ;LOCK THE SWITCH, OR WAIT TILL WE CAN.
210          .HANG
211 LOCK1:  MOVE B,43               ;PUT THE SWITCH ON THE
212         HRLI B,(SETOM)
213         MOVEM B,1(A)            ;LOCKED SWITCH LIST
214         MOVEM A,43
215 LOCK2:  POPJ P,
216
217 This routine will set up the switch as a switch block, and make
218 43 point to it. The contents of the switch block will be:
219
220         0               ;This word is the switch itself!
221         SETOM <previous contents of 43>
222                         ;The SETOM is the unlock instruction.
223                         ;The RH has nothing to do with the SETOM;
224                         ;it points to the next block of the list.
225
226 Note that the HRLI instruction is superfluous, because 0 in the
227 left half of the second word of the block is the same as (SETOM).
228
229 The three instructions starting at LOCK1 are critical because
230 the switch has been locked but is not on the locked switch list.
231 Therefore, an entry in the critical routine table of the form
232
233         LOCK1,,LOCK2
234         SETOM @A
235
236 is needed, in case the job is killed while executing there.
237
238
239  2. UNLOCKING AN AOSE-STYLE SWITCH.
240
241 The correct way to unlock a switch follows:
242 (assuming that A points to the switch block and that
243 the switch block is the first item on the locked switch list).
244
245 UNLOCK: HRRZ B,1(A)     ;REMOVE THE SWITCH FROM THE
246         MOVEM B,43      ;LOCKED SWITCH LIST.
247 UNLOC1: SETOM (A)       ;THEN UNLOCK THE SWITCH.
248 UNLOC2: POPJ P,
249
250 The instruction at UNLOC1 is critical because the switch is
251 locked but not on the locked switch list. Therefore, an entry
252 is needed in the critical routine table as follows:
253
254         UNLOC1,,UNLOC2
255         SETOM @A
256
257 Note that the switch must be removed from the list before
258 unlocking. That is because if the switch is locked but not on
259 the list, the critical routine table may be used to unlock it,
260 but if the switch is on the list but not locked, it will be set
261 to -1 if the job is killed, and that could cause problems if
262 some other job had locked the switch.
263
264
265 C. HANDLING SWITCHES IN DISK FILES.
266
267 The extra problem here is to make sure that if the system crashes, the next
268 time the data base is accessed after the system is reloaded all the
269 switches will be reinitialized.  This may be done by using the time and
270 date that the system was started to distinguish different incarnations of
271 it.
272
273 The technique uses a variable INITDN, stored in the database, and a LOCK
274 device lock named "NUTMEG".  Whenever a program accesses the database for
275 the first time, it must check INITDN.  If INITDN does not equal the time
276 the system was started, the database requires initialization.  If a job
277 detects that the database requires initialization, it seizes the NUTMEG
278 lock, checks to see that initialization really is required, performs the
279 initialization, updates INITDN, and releases the lock.
280
281 The skeleton of the necessary routine is as follows, assuming that the file
282 has already been opened and its pages mapped into core with a CORBLK system
283 call, and INITDN is the address of the variable and SWIT1, SWIT2, etc. are
284 the addresses of switches.
285
286 INIT:   .CALL [ SETZ ? SIXBIT /RQDATE/
287                 MOVEM A         ; Ignore 1st value
288                 SETZM A]        ; 2nd value is time of system startup.
289          .LOSE 1000
290         JUMPL A,[MOVEI A,300.   ; System doesn't know time,
291                  .SLEEP A,      ; Sleep 10. sec and hope it
292                  JRST INIT]     ; finds out the time.
293         CAMN A,INITDN           ; Init needed?
294          POPJ P,                ; No => No need for the lock, just return.
295         .CALL [ SETZ ? SIXBIT /OPEN/
296                 MOVSI 10\.UAO   ; 1.4 => Hang waiting for initialization lock
297                 MOVEI CH
298                 MOVE [SIXBIT /LOCK/]
299                 SETZ [SIXBIT /NUTMEG/]] ; Registered, database specific lock
300          .LOSE
301         CAMN A,INITDN           ; Init needed?
302          JRST INIT1             ; No => someone else did it, unlock and return.
303         SETOM SWIT1             ; Start setting switches to unlocked
304         SETOM SWIT2             ; state. These insns should address
305         SETOM SWIT3             ; locations in the mapped file pages.
306         ;; etc.
307         SETOM SWIT9
308         MOVEM A,INITDN          ; Mark init complete.
309 INIT1:  .CLOSE CH,
310         POPJ P,
311
312 Note that the first CAMN A,INITDN can be omitted, and the algorithm is
313 still correct, but the second CAMN A,INITDN can -not- be safely omitted.
314
315
316 D. REFERENCE COUNTS.
317
318 Sometimes it is desirable to keep a count of the number of jobs
319 looking at a data base. When the count is AOS'd, an entry must
320 be put on the locked switch list to cause it to be SOS'd if the
321 job is killed. For example, assuming that A points to the count
322 and B points to an available two word block of memory:
323
324 LOOK:   AOS (A)
325 LOOK1:  MOVEM A,(B)
326         MOVSI C,(SOS @)
327         HRR C,43
328         MOVEM C,1(B)    ;SET UP UNLOCK INSN & CDR POINTER.
329         MOVEM B,43      ;PUT THE BLOCK ON THE LIST.
330 LOOK2:  POPJ P,
331
332 The critical code table entry needed is:
333
334         LOOK1,,LOOK2
335         SOS @A
336
337 When finished looking, the count must be SOS'd, and removed from
338 the list. The following routine will work, assuming only that
339 the block at the front of the list was put on by the LOOK routine
340 above:
341
342 UNLOOK: MOVE B,43
343         HRRZ A,(B)      ;GET ADDRESS OF THE COUNT VARIABLE TO BE SOS'D .
344         HRRZ B,1(B)     ;GET CDR POINTER.
345 UNLOO1: MOVEM B,43      ;REMOVE BLOCK FROM LIST.
346 UNLOO2: SOS (A)         ;DECREMENT THE COUNT.
347         POPJ P,
348
349 The critical code table entry needed is:
350
351         UNLOO1,,UNLOO2
352         SOS @A
353
354
355 E. THE .HANG INSTRUCTION.
356
357 The .HANG UUO is to make it easy for programs to wait for various
358 conditions, such as locks becoming unlocked.  It should be used the way a
359 JRST .-1 would be used in a stand-alone program.  .HANG is documented
360 completely in .INFO.;ITS UUOS.
361
362
363 F. THE UNLOCK SYSTEM CALL.
364
365 The UNLOCK system call can be used to unlock the switches of a specified
366 job.  Usually this is used by a job to unlock its own switches, but it can
367 be used on the switches of any job that the executing job is allowed to
368 write.
369
370 Usual case:
371
372         .CALL [ SETZ ? SIXBIT /UNLOCK/
373                 SETZI %JSELF ]  ; Unlock all my switches
374          .LOSE %LSSYS
375
376 (Note that this has nothing to do with the LOCK device.  In particular it
377 will -not- close LOCK device channels.)