1 /****^  ***********************************************************
  2         *                                                         *
  3         * Copyright, (C) Honeywell Bull Inc., 1987                *
  4         *                                                         *
  5         * Copyright, (C) Honeywell Information Systems Inc., 1982 *
  6         *                                                         *
  7         * Copyright (c) 1972 by Massachusetts Institute of        *
  8         * Technology and Honeywell Information Systems, Inc.      *
  9         *                                                         *
 10         *********************************************************** */
 11 
 12 
 13 get_aste:
 14      procedure (csl) returns (ptr);
 15 
 16 dcl csl fixed bin (17) parameter;
 17 
 18 /*
 19    astep = get_aste (csl)
 20    astep = get_aste$synchronized (csl);
 21 
 22    FUNCTION -
 23 
 24    The procedure "get_aste" returns a pointer to  a  free  ASTE  whose  page  table
 25    length  is  equal to or greater than the input argument "csl". If it cannot find
 26    such an ASTE, it returns a null pointer.
 27 
 28    "get_aste" does not concern itself with the AST lock. It  assumes  there  is  no
 29    race  condition.  It is the responsibility of the caller to issue the call after
 30    the AST has been locked and to unlock it upon return, as soon as it is  safe  to
 31    do  so.  Of  course,  the  initializer  or  shutdown may call "get_aste" without
 32    locking the AST since they know they are alone.
 33 
 34    The ASTE is threaded in the circular list, at the end.
 35 
 36    All items of the ASTE are zero with the exception of fb and bp which thread  the
 37    ASTE  in  the  circular list, and ptsi and marker which are engraved in the ASTE
 38    forever.
 39 
 40    All PTW's are initialized with a page not in core flag and  with  a  coded  null
 41    device address.
 42 
 43    IMPLEMENTATION -
 44 
 45    First,  the  argument "csl" is used to determine what is the appropriate size of
 46    the page table. Then the circular list associated with the  determined  size  is
 47    scanned,  starting  from  the ASTE which happens to be pointed to by the current
 48    pointer associated with this list.
 49 
 50    If there is a free ASTE at the head of the list, it will be selected.
 51    Otherwise, the list is searched for an ASTE which is not entry-held,
 52    has no inferiors, no pages in memory, and aste.init not set.  ASTE's
 53    which are rejected have their file maps updated if aste.fmchanged = "1"b.
 54 
 55    If no ASTE's are found above, a much more careful search is done.
 56    The estimated cost of deactivating each segment is computed by computing
 57    a 'cost' equal to the sum of pages used, pages modified, and 1 for the
 58    VTOCE I/O.  The cost for a directory also includes the sum of the costs
 59    of its inferiors.  The segment with the lowest cost will be selected.
 60 
 61    The selected segment is deactivated with the "deactivate" routine.
 62    If this segment is a directory with active inferiors, all inferiors
 63    are also deactivated (in a bottom-up manner, thereby adhering to the
 64    dictum that all ancestor segments of an active segment must be active).
 65 
 66    No matter if the selected ASTE was free or if it has been deactivated, it is now
 67    threaded in the list, at the FIRST position. It is  put  at  the  last  position
 68    merely by moving the current position forward by 1 position.
 69 
 70    Synchronized segments are special-cased. If the per-pool limit on these
 71    is exceeded, only synchronized segments are considered for deactivation.
 72 
 73    MODIFICATIONS -
 74 
 75    04/08/75 Totally rewritten by Andre Bensoussan for the new storage system.
 76    06/76 by D.Vinograd to skip ast entries in use by the volume dumper
 77    03/23/77 by Greenberg for get_aste$flush_ast_pool
 78    10/07/80 by C. Hornig for new replacement algorithm
 79    03/21/81 W. Olin Sibert, for ADP PTWs
 80    04/19/81 by W. Olin Sibert, to get rid of aste.ic
 81    05/31/81 by J. Bongiovanni to return null ptr on invalid csl
 82    10/25/82 by J. Bongiovanni for synchronized segments
 83 */
 84 
 85 dcl N_PROTECTED_ASTES fixed bin static options (constant) init (4);
 86 
 87 dcl (fastep, lastep, mp_astep) ptr;
 88 dcl aste_count fixed bin;
 89 dcl (cost_total, best_cost) fixed bin;
 90 dcl pts fixed bin;
 91 dcl code fixed bin (35);
 92 dcl ptsi fixed bin (3);
 93 dcl ptp pointer;
 94 dcl synchronized_call bit (1) aligned;
 95 dcl synchronized_only bit (1) aligned;
 96 
 97 dcl error_table_$deact_in_mem fixed bin (35) external;
 98 dcl pds$process_group_id char (32) external;
 99 dcl sys_info$system_type fixed bin external static;
100 
101 dcl deactivate entry (ptr, fixed bin (35));
102 dcl hc_dm_util$check_activate entry (fixed bin (3), fixed bin (35));
103 dcl hc_dm_util$activate entry (fixed bin (3));
104 dcl syserr entry options (variable);
105 dcl syserr$error_code entry options (variable);
106 dcl update_vtoce entry (ptr);
107 
108 dcl (addr, addrel, binary, hbound, lbound, null, pointer, rel) builtin;
109 
110 %page;
111 /* * * * * * * * * * GET_ASTE * * * * * * * * */
112 
113           synchronized_call = "0"b;
114           goto common;
115 
116 synchronized:
117           entry (csl) returns (ptr);
118 
119           synchronized_call = "1"b;
120 
121 common:
122           sstp = addr (sst_seg$);                           /* get a pointer to the SST */
123 
124           do ptsi = hbound (sst.pts, 1) by -1 to lbound (sst.pts, 1) + 1 while (csl <= sst.pts (ptsi - 1));
125           end;                                              /* search for the correct index */
126 
127           pts = sst.pts (ptsi);                             /* save real size of the page table array */
128 
129           if csl > pts then do;                             /* invalid csl                                    */
130                call syserr (0, "get_aste: Invalid csl ^d", csl);
131                return (null());
132           end;
133 
134 
135           sst.aneedsize (ptsi) = sst.aneedsize (ptsi) + 1;  /* meter */
136 
137           if sst.ausedp (ptsi) = ""b then goto err_out;     /* none on the list */
138 
139           synchronized_only = "0"b;
140           if synchronized_call then do;
141                sst.synch_activations = sst.synch_activations + 1;
142                call hc_dm_util$check_activate (ptsi, code);
143                if code ^= 0 then synchronized_only = "1"b;
144           end;
145 
146 /*   First, check the beginning of the aste list for a free aste.
147      During deactivation, put_aste threads the newly-freed aste
148      to the beginning of the list
149                                                                                                               */
150 
151 
152           fastep, lastep, astep = pointer (sstp, sst.ausedp (ptsi));
153 
154 
155           if ^aste.usedf & ^synchronized_only then do;
156                sst.stepsa = sst.stepsa + 1;
157                sst.asteps (ptsi) = sst.asteps (ptsi) + 1;
158 return_aste:
159                sst.ausedp (ptsi) = aste.fp;                 /* Move current ptr forward by 1 position */
160                if synchronized_call
161                     then call hc_dm_util$activate (ptsi);
162                return (astep);                              /* Return astep - ASTE is now last in list */
163                end;
164 
165 /*   Next, protect a number of aste's from being deactivated during this
166      this call to get_aste.  The number of protected aste's is given
167      by the constant N_PROTECTED_ASTES; the aste's protected are those
168      in the list immediately preceding the current position (and hence,
169      the protected aste's are those activated most recently).  The purpose
170      of this protection is to prevent "ping-ponging" of aste's, a phenomenon
171      wherein the system hangs on a single instruction (e.g., a multi-word EIS
172      instruction referencing multiple segments alternately taking segment
173      faults on two segments, where the segment fault of one causes
174      deactivation of the other segment).                                                                      */
175 
176           do aste_count = 1 to N_PROTECTED_ASTES;           /* walk back to protect */
177                astep = pointer (astep, aste.bp);            /* recently used ASTE's */
178                if ^aste.usedf & ^synchronized_only then goto return_aste;
179                if astep = fastep then goto small_ast;       /* ridiculous */
180           end;
181 small_ast:
182           lastep = astep;
183 
184 /*   This is the main loop of aste allocation.  The entire list is walked
185      (except for aste's which have been protected above) until one of the
186      following happens:
187 
188           1. an aste is found which can be deactivated (entry-hold-switch,
189              dumper-in-use, ddnp, and deact_error all off), is not in
190              "grace" lap (the first lap after activation), has no active
191              inferiors, and no pages in memory.
192 
193           2. the end of the list is reached.
194 
195      With reasonable number of aste's in the pools (set via the SST card),
196      and normal system behavior, an aste should almost always be found
197      in this loop                                                                                             */
198 
199 
200           do astep = fastep repeat (pointer (astep, aste.fp)) while (aste.fp ^= rel (lastep));
201                if ^aste.usedf & ^synchronized_only then goto return_aste;  /* aste free -allocate it                              */
202 
203 
204                sst.stepsa = sst.stepsa + 1;                 /* count total steps                              */
205                sst.asteps (ptsi) = sst.asteps (ptsi) + 1;   /* count steps for this size */
206 
207                if aste.dius then do;                        /* volume dumper is using it */
208                     sst.askipdius = sst.askipdius + 1;
209                     goto skip;
210                     end;
211 
212                if aste.ehs | aste.ddnp | aste.deact_error then do;
213                                                             /* Check for ehs = entry_hold, or ddnp
214                                                                without that, which = being prewithdrawn. */
215                     sst.askipsehs = sst.askipsehs + 1;
216                     go to skip;
217                     end;
218 
219                if aste.init then do;                        /* check for grace lap flag */
220                     aste.init = "0"b;                       /* turn off flag */
221                     sst.askipsinit = sst.askipsinit + 1;
222                     go to skip;
223                     end;
224 
225                if (aste.np ^= ""b) | (aste.infp ^= ""b) then do; /* check for no inferiors, no pages in memory*/
226                     sst.askipslevel = sst.askipslevel + 1;
227                     goto skip;
228                     end;
229 
230                if synchronized_only & ^aste.synchronized then do;     /* check for synch seg restrictions */
231                     sst.synch_skips = sst.synch_skips + 1;
232                     goto skip;
233                end;
234 
235                sst.ausedp (ptsi) = rel (astep);
236                call my_deactivate (astep, code);
237                if code = 0 then goto return_aste;
238 
239 skip:
240                if aste.fmchanged & ^aste.per_process then do;
241                                                             /* check for AST trickle */
242                     call update_vtoce (astep);              /* update the vtoc entry */
243                     sst.updates = sst.updates + 1;
244                     end;
245           end;
246 %page;
247 /*   This is the tough search.  At this point we are willing to do a lot
248      more work to find the right aste to deactivate.  We assume that this
249      search is rarely needed, and so we are not concerned with the overhead
250      involved.
251 
252      In this search, the entire aste list is walked (again, excepting aste's
253      which are protected for this call to get_aste), and a cost is computed
254      for deactivating each aste which can be deactivated.  Since we are in
255      desparate straights, we are willing to deactivate inferiors (if necessary).
256      However, the restrictions of entry-hold switch, dumper-in-use, ddnp,
257      and deact_error still apply; further, an aste cannot be deactivated if
258      any of these conditions prevent an inferior from being deactivated.
259      After a walk of the entire list, the aste with the lowest cost is
260      deactivated (following a bottom-up deactivation of all of its inferiors).
261 
262      Synchronized segments are special-cased if the per-pool limit on these
263      is exceeded. The first such segment which can be deactivated is deactivated.
264      This logic is a hedge against flooding the system with de-facto entry-held
265      segments. It is expected to be executed rarely.
266 */
267 
268 deact_error:
269           best_cost = 1f16b;
270           mp_astep = null ();
271           do astep = fastep repeat (pointer (astep, aste.fp)) while (aste.fp ^= rel (lastep));
272                cost_total = 0;
273                if ^synchronized_only then do;               /* Normal case */
274                     call check (astep, code);               /* calculate the cost */
275                     if code ^= 0 then goto ddir_loop;
276                     call walk_ast (check, code);            /* check the inferior hierarchy */
277                     if code ^= 0 then goto ddir_loop;
278 
279                     if cost_total < best_cost then do;
280                          best_cost = cost_total;
281                          mp_astep = astep;
282                     end;
283                end;
284                else do;                                     /* Synchronized only */
285                     call check (astep, code);
286                     if code ^= 0 then goto ddir_loop;
287                     sst.ausedp (ptsi) = rel (astep);
288                     call my_deactivate (astep, code);
289                     if code = 0 then goto return_aste;
290                end;
291 ddir_loop:
292           end;
293 
294           if mp_astep = null () then do;                    /* didn't find anything */
295 err_out:
296                if ^synchronized_only then
297                     call syserr (0, "get_aste: No removable ^dk AST entries.", pts);
298                else call syserr (4, "get_aste: No removable ^dk synchronized AST entries.", pts);
299                return (null ());
300                end;
301 
302           astep = mp_astep;
303           call walk_ast (my_deactivate, code);              /* deactivate all inferiors */
304           if code ^= 0 then goto deact_error;
305 
306           sst.ausedp (ptsi) = rel (astep);
307           call my_deactivate (astep, code);
308           if code ^= 0 then goto deact_error;
309 
310           sst.asearches = sst.asearches + 1;
311           sst.acost = sst.acost + best_cost;
312 
313           goto return_aste;
314 
315 /* * * * * * * * * * WALK_AST * * * * * * * * * */
316 
317 walk_ast:
318      procedure (Proc, Code);
319 dcl Proc variable entry (ptr, fixed bin (35)) parameter;
320 dcl Code fixed bin (35) parameter;
321 dcl inf_astep ptr;
322 dcl next_astep ptr;
323 dcl brother bit (1) aligned;
324 
325 /* This procedure walks the tree of active inferiors of an active directory,
326    calling the supplied procedure on each branch.  The branches are processed
327    bottom-up. */
328 
329           Code = 0;
330           inf_astep = astep;
331 find_son:                                                   /* walk to the bottom of the subtree */
332           do while (inf_astep -> aste.infp ^= ""b);
333                inf_astep = pointer (inf_astep, inf_astep -> aste.infp);
334           end;
335 process_aste:
336           if inf_astep = astep then return;                 /* we have walked the whole tree */
337           if inf_astep -> aste.infl ^= ""b then do;         /* next do his brother */
338                next_astep = pointer (inf_astep, inf_astep -> aste.infl);
339                brother = "1"b;
340                end;
341           else do;
342                next_astep = pointer (inf_astep, inf_astep -> aste.par_astep);
343                brother = "0"b;
344                end;
345           call Proc (inf_astep, Code);                      /* process the branch */
346           if Code ^= 0 then return;
347           inf_astep = next_astep;
348           if brother then goto find_son;
349           else goto process_aste;
350      end walk_ast;
351 
352 %page;
353 
354 /* * * * * * * * * * CHECK * * * * * * * * * * */
355 
356 check:
357      procedure (Astep, Code);
358 dcl Astep ptr parameter;
359 dcl Code fixed bin (35) parameter;
360 
361 dcl pn fixed bin;
362 
363 /* check makes sure that a directory can be deactivated safely
364    It also increments the cost function.  At the same time, it checks
365    whether this aste (an inferior to the one being considered for
366    deactivation) is in the same aste pool as the aste being considered.
367    If it is, a non-zero code is returned, since we know that there is
368    an aste in the pool with lower cost than the one being considered currently
369    (namely, this one).                                                                                        */
370 
371 
372           if (Astep -> aste.ehs) | (Astep -> aste.ddnp) | (Astep -> aste.dius) | (Astep -> aste.deact_error)
373           then goto cant_do_it;
374           if synchronized_only & ^(Astep -> aste.synchronized)
375           then goto cant_do_it;
376           if (binary (Astep -> aste.ptsi) = ptsi) & (astep ^= Astep) then do;
377 cant_do_it:
378                Code = -1;
379                return;
380                end;
381 
382           Code = 0;
383           ptp = addrel (Astep, sst.astsize);                /* Start with page zero */
384           cost_total = cost_total + 1;                      /* Costs one for the ASTE itself */
385 
386           do pn = 1 to pts;
387                cost_total = cost_total + ptw_cost (ptp);
388                ptp = addrel (ptp, 1);
389                end;
390 
391           if cost_total > best_cost then Code = -1;         /* aste being considered cannot win               */
392 
393      end check;
394 %page;
395 
396 /* * * * * * * * * * PTW_COST * * * * * * * * * */
397 
398 ptw_cost: proc (Ptwp) returns (fixed bin);
399 
400 /* This procedure returns the "cost" of flushing one PTW. If the PTW
401    has not been used or modified, the cost is zero. If it has been either
402    used or modified, the cost is one. If it has been both, the cost is two.
403    */
404 
405 dcl  Ptwp pointer parameter;
406 
407 dcl  used bit (1) aligned;
408 dcl  mod bit (1) aligned;
409 
410 
411           if sys_info$system_type = ADP_SYSTEM then
412                used = (Ptwp -> adp_ptw.phu) | (Ptwp -> adp_ptw.phu1);
413           else used = (Ptwp -> l68_ptw.phu) | (Ptwp -> l68_ptw.phu1);
414 
415           if sys_info$system_type = ADP_SYSTEM then
416                mod = (Ptwp -> adp_ptw.phm) | (Ptwp -> adp_ptw.phm1);
417           else mod = (Ptwp -> l68_ptw.phm) | (Ptwp -> l68_ptw.phm1);
418 
419           if (used & mod) then return (2);
420           else if (used | mod) then return (1);
421           else return (0);
422 
423           end ptw_cost;
424 
425 
426 %page;
427 
428 /* * * * * * * * * * MY_DEACTIVATE * * * * * * * * * * */
429 
430 /* Internal procedure to deactivate an aste.
431    If an error of any sort occurs here, a message is printed on the console,
432    and the flag aste.deact_error is set so that this aste will be skipped
433    in the aste replacement search.  This flag is reset by flush_ast_pool.                                     */
434 
435 
436 my_deactivate:
437      procedure (Astep, Code);
438 dcl Astep ptr parameter;
439 dcl Code fixed bin (35) parameter;
440 
441           call deactivate (Astep, Code);
442           if Code ^= 0 then
443                if ^(Astep -> aste.synchronized) | (Code ^= error_table_$deact_in_mem) then do;
444                Astep -> aste.deact_error = "1"b;
445                call syserr$error_code (3, Code,
446                     "get_aste: Error deactivating ^w (VTOCE ^o on pvt ^o) to free ^dK ASTE for ^a.", Astep -> aste.uid,
447                     Astep -> aste.vtocx, Astep -> aste.pvtx, pts, pds$process_group_id);
448                end;
449      end my_deactivate;
450 
451 %page; %include sst;
452 %page; %include aste;
453 %page; %include system_types;
454 %page; %include "ptw.l68";
455 %page; %include "ptw.adp";
456 
457 /* ^L */
458 
459 /* BEGIN MESSAGE DOCUMENTATION
460 
461    Message:
462    get_aste: no removable XXXk ast entries
463 
464    S: $info
465 
466    T: $run
467 
468    M: An AST entry was needed for a segment of size XXX k, but no free
469    entries of that size were present, and no segments occupying such
470    entries could be deactivated. This could be symptomatic of a
471    logic problem, but may also indicate a grossly mistuned AST.
472 
473    A:
474    Substantially increase the number of AST entries of this size as
475    given on the SST CONFIG card. If the problem persists, contact the
476    system programming staff.
477 
478    Message:
479    get_aste: no removable XXXk synchronized AST entries
480 
481    S: $log
482 
483    T: $run
484 
485    M: An AST entry was needed for a synchronized segment of size XXX k, and
486    the per-ASTE-pool limit on synchronized segments was reached. No synchronized
487    segments in that pool could be deactivated.
488 
489    A: Contact the system programming staff.
490 
491    Message:
492    get_aste: Invalid csl x
493 
494    S:     $log
495 
496    T:     $run
497 
498    M:     get_aste was called to activate a segment with x pages,
499 which is larger than the maximum segment size.  This is indicative
500 of hardware or software failure (a typical problem is an invalid
501 VTOCE).
502 
503    A:     If the problem persists, contact the system programming staff.
504 
505 
506    Message:
507    get_aste: Error deactivating UUUU (vtoc V of pvt PV) to free XXXk ASTE for USERNAME.
508 
509    S: $log
510 
511    T: $run
512 
513    M: The system encountered an error deactivating an AST entry which was
514    selected for deactivation by the AST replacement algorithm.  The AST
515    on which the error was encountered will be flagged to be ingored by
516    further passes of the algorithm; this flag will be reset during the next
517    run of flush_ast_pool.
518 
519    A: If the problem persists, contact the system programming staff.
520 
521    END MESSAGE DOCUMENTATION */
522 
523      end get_aste;