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;