COMPILATION LISTING OF SEGMENT buddy_alloc_ Compiled by: Multics PL/I Compiler, Release 32f, of October 9, 1989 Compiled at: Bull HN, Phoenix AZ, System-M Compiled on: 11/11/89 0959.4 mst Sat Options: optimize map 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 /* buddy_alloc_ is called to allocate space in an area. the calling sequence is: 14* call buddy_alloc_(size,area_ptr,return_ptr), where size is fixed bin(26) and is size of block desired, 15* area_ptr is the pointer to the area and return_ptr is a pointer to the allocated space. 16* area_ptr must be pointing to a legitimate base or unpredictable errors will occur. if the area pointed to by area_ptr 17* is not initialized, area_ will be called to initialize it. 18* coded 8.16.72 by Alan Downing. 19* */ 20 /* modified by A. Downing 08/73 to put in loop checks */ 21 22 /* Last modified: (date and reason) 23* 11/6/75 by S.Webber to rename it buddy_alloc_ from alloc_ 24**/ 25 26 buddy_alloc_: procedure (size, area_ptr, return_ptr); 1 1 /* area_header_v2pl1.incl.pl1 */ 1 2 dcl area_header (23) fixed bin (26) aligned based (area_ptr), 1 3 /* the first two words are 0 so that the area can be identified as of the new style, 1 4* the third word contains the size of the area in words, 1 5* the fourth word is the high water mark, 1 6* the fifth word is the first usable word in the area, 1 7* the sixth word is the stratum word number corresponding to the largest possible block in this area, 1 8* words 7 through 23 are stratum words which point to blocks which are free 1 9* and whose size is 2**2 through 2**18 */ 1 10 area_ptr ptr; /* points to the area */ 1 11 dcl exp_tbl (0:18) fixed bin (26) int static init 1 12 (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144); 1 13 dcl front fixed bin (26); 27 2 1 /* block_header_v2pl1.incl.pl1 */ 2 2 dcl 1 block_header aligned based (block_ptr), /* this structure appears at the front of every block */ 2 3 2 size fixed bin (8) unaligned, /* tells what stratum word a block of this size belongs */ 2 4 2 forwardptr fixed bin (26) unaligned, /* points to next free block of this size */ 2 5 2 new_area bit (8) unaligned, /* acts as pading as well as a flag */ 2 6 2 busy_bit bit (1) unaligned, /* if on the block is busy */ 2 7 2 backptr fixed bin (26) unaligned; /* relative pointer to the front of area */ 2 8 2 9 dcl block_ptr ptr; 2 10 2 11 2 12 dcl 1 buddy_block_header like block_header based (buddy_block_ptr) aligned; 2 13 dcl buddy_block_ptr ptr; 28 29 dcl return_ptr ptr, 30 (rel, addrel, ptr, fixed, null) builtin, 31 bit1 bit (1) init ("0"b), /* tells if entering at top */ 32 alloc_ ext entry (fixed bin (26), ptr, ptr), 33 area_ ext entry (fixed bin (26), ptr), 34 (count, stop, i, j, k, ind, save_offset, size, place, indx) fixed bin (26), 35 sys_info$max_seg_size ext static fixed bin (35), 36 (area, storage, bad_area_format) condition; 37 bit1 = "1"b; /* flag to signal the area condition if insufficient area for allocate statement */ 38 buddy_storage_: entry (size, area_ptr, return_ptr); /* for signaling storage condition instead of area */ 39 if area_ptr -> area_header (1) ^= 0 then do; /* Not buddy system area */ 40 call alloc_ (size, area_ptr, return_ptr); 41 return; 42 end; 43 restart: /* come here if area has been made right size */ 44 front = fixed (rel (area_ptr), 18); /* point to front end of area */ 45 stop = 70000; /* used to stop infinite loopking when bad area exists */ 46 i = area_ptr -> area_header (3); 47 if area_ptr -> area_header (4) = 0 then do; 48 49 /* The following code will convert the area to a new style area and then allocate 50* the block therein with the new area management code. */ 51 52 call area_ (i, area_ptr); /* must initialize */ 53 call alloc_ (size, area_ptr, return_ptr); 54 return; 55 end; 56 57 area_ptr -> area_header (4) = 58 area_ptr -> area_header (3); /* set high water mark */ 59 retry: 60 i = size; 61 if area_ptr -> area_header (6) > 23 then 62 go to bad_area; /* this word has evidently been overwritten */ 63 count = 0; 64 try_to_allocate: 65 do ind = 2 to area_ptr -> area_header (6)-5; /* find what stratum is large enough */ 66 count = count + 1; 67 if count > stop then go to bad_area; 68 if exp_tbl (ind) >= i+2 then do; /* found the right size now */ 69 i = exp_tbl (ind); 70 place = ind+5; 71 if area_ptr -> area_header (place) ^= 0 then do; /* got a chain of free blocks this size */ 72 alloc_block: 73 if area_ptr -> area_header (place)+front+size > sys_info$max_seg_size then do; 74 count = count + 1; 75 if count > stop then 76 bad_area: do; /* area is no good */ 77 signal bad_area_format; 78 go to restart; 79 end; 80 block_ptr = addrel (area_ptr, area_ptr -> area_header (place)); 81 if block_ptr -> block_header.forwardptr = 0 then go to break_up; 82 area_ptr -> area_header (place) = block_ptr -> block_header.forwardptr; 83 buddy_block_ptr = addrel (area_ptr, area_ptr -> area_header (place)); 84 block_ptr -> block_header.forwardptr = buddy_block_ptr -> buddy_block_header.forwardptr; 85 buddy_block_ptr -> buddy_block_header.forwardptr = 86 fixed (rel (block_ptr), 18)-front; 87 go to alloc_block; 88 end; 89 block_ptr = addrel (area_ptr, area_ptr -> area_header (place)); /* set block_ptr to beginning of free block */ 90 91 92 area_ptr -> area_header (place) = 93 block_ptr -> block_header.forwardptr; /* relink chain */ 94 block_ptr -> block_header.busy_bit = "1"b; /* indicate that this block is busy */ 95 block_ptr -> block_header.new_area = "11111111"b; /* used by freen_ to indicate new type block */ 96 return_ptr = addrel (block_ptr, 2); /* offset return_ptr to actual beginning of storage in this block */ 97 return; 98 end; /* thats all for allocating a block */ 99 else 100 break_up: do j = ind+1 to area_ptr -> area_header (6)-5; /* look for bigger blocks which are free */ 101 if area_ptr -> area_header (j+5) ^= 0 then do; 102 do k = j to ind+1 by -1; /* break up this block */ 103 place = k+5; 104 indx = exp_tbl (k-1); 105 buddy_block_ptr = addrel (area_ptr, area_ptr -> area_header (place)); /* point at this block */ 106 if area_ptr -> area_header (place)+indx+front > sys_info$max_seg_size then do; 107 if buddy_block_ptr -> buddy_block_header.forwardptr ^= 0 then do; 108 block_ptr = addrel (area_ptr, buddy_block_ptr -> buddy_block_header.forwardptr); 109 area_ptr -> area_header (place) = 110 buddy_block_ptr -> buddy_block_header.forwardptr; 111 buddy_block_ptr -> buddy_block_header.forwardptr = 112 block_ptr -> block_header.forwardptr; 113 block_ptr -> block_header.forwardptr = fixed (rel (buddy_block_ptr), 18) - front; 114 go to try_to_allocate; 115 end; 116 i = size * 2; 117 go to try_to_allocate; 118 end; 119 buddy_block_ptr -> buddy_block_header.size = place-1; 120 area_ptr -> area_header (place) = buddy_block_ptr -> buddy_block_header.forwardptr; 121 place = place -1; 122 save_offset = area_ptr -> area_header (place); 123 buddy_block_ptr -> buddy_block_header.forwardptr = 124 fixed (rel (buddy_block_ptr), 18)+indx-front; 125 area_ptr -> area_header (place) = fixed (rel (buddy_block_ptr), 18)-front; 126 /* have just relinked both sized stratum chains */ 127 buddy_block_ptr = addrel (buddy_block_ptr, indx); /* must free up other half of the original block */ 128 buddy_block_ptr -> buddy_block_header.busy_bit = "0"b; /* not busy */ 129 buddy_block_ptr -> buddy_block_header.backptr = fixed (rel (buddy_block_ptr), 18) - front; /* point at front of this area */ 130 buddy_block_ptr -> buddy_block_header.size = place; 131 buddy_block_ptr -> buddy_block_header.forwardptr = 132 save_offset; /* close chain */ 133 end; 134 go to alloc_block; 135 end; 136 end; 137 end; /* end of 2**ind being large enough */ 138 end; /* end of ind do loop */ 139 error_return: /* come here if there is not room to allocate desired space */ 140 if bit1 then signal area; 141 else signal storage; 142 go to retry; /* maybe some storage was freed */ 143 end; SOURCE FILES USED IN THIS COMPILATION. LINE NUMBER DATE MODIFIED NAME PATHNAME 0 11/11/89 0804.2 buddy_alloc_.pl1 >spec>install>1110>buddy_alloc_.pl1 27 1 05/06/74 1740.3 area_header_v2pl1.incl.pl1 >ldd>include>area_header_v2pl1.incl.pl1 28 2 05/06/74 1740.9 block_header_v2pl1.incl.pl1 >ldd>include>block_header_v2pl1.incl.pl1 NAMES DECLARED IN THIS COMPILATION. IDENTIFIER OFFSET LOC STORAGE CLASS DATA TYPE ATTRIBUTES AND REFERENCES (* indicates a set context) NAMES DECLARED BY DECLARE STATEMENT. addrel builtin function dcl 29 ref 80 83 89 96 105 108 127 alloc_ 000010 constant entry external dcl 29 ref 40 53 area 000120 stack reference condition dcl 29 ref 139 area_ 000012 constant entry external dcl 29 ref 52 area_header based fixed bin(26,0) array dcl 1-2 set ref 39 46 47 57* 57 61 64 71 72 80 82* 83 89 92* 99 101 105 106 109* 120* 122 125* area_ptr parameter pointer dcl 1-2 set ref 26 38 39 40* 43 46 47 52* 53* 57 57 61 64 71 72 80 80 82 83 83 89 89 92 99 101 105 105 106 108 109 120 122 125 backptr 1(09) based fixed bin(26,0) level 2 packed packed unaligned dcl 2-12 set ref 129* bad_area_format 000134 stack reference condition dcl 29 ref 77 bit1 000106 automatic bit(1) initial packed unaligned dcl 29 set ref 29* 37* 139 block_header based structure level 1 dcl 2-2 block_ptr 000102 automatic pointer dcl 2-9 set ref 80* 81 82 84 85 89* 92 94 95 96 108* 111 113 buddy_block_header based structure level 1 dcl 2-12 buddy_block_ptr 000104 automatic pointer dcl 2-13 set ref 83* 84 85 105* 107 108 109 111 113 119 120 123 123 125 127* 127 128 129 129 130 131 busy_bit 1(08) based bit(1) level 2 in structure "block_header" packed packed unaligned dcl 2-2 in procedure "buddy_alloc_" set ref 94* busy_bit 1(08) based bit(1) level 2 in structure "buddy_block_header" packed packed unaligned dcl 2-12 in procedure "buddy_alloc_" set ref 128* count 000107 automatic fixed bin(26,0) dcl 29 set ref 63* 66* 66 67 74* 74 75 exp_tbl 000000 constant fixed bin(26,0) initial array dcl 1-11 ref 68 69 104 fixed builtin function dcl 29 ref 43 85 113 123 125 129 forwardptr 0(09) based fixed bin(26,0) level 2 in structure "block_header" packed packed unaligned dcl 2-2 in procedure "buddy_alloc_" set ref 81 82 84* 92 111 113* forwardptr 0(09) based fixed bin(26,0) level 2 in structure "buddy_block_header" packed packed unaligned dcl 2-12 in procedure "buddy_alloc_" set ref 84 85* 107 108 109 111* 120 123* 131* front 000100 automatic fixed bin(26,0) dcl 1-13 set ref 43* 72 85 106 113 123 125 129 i 000111 automatic fixed bin(26,0) dcl 29 set ref 46* 52* 59* 68 69* 116* ind 000114 automatic fixed bin(26,0) dcl 29 set ref 64* 68 69 70 99 102* indx 000117 automatic fixed bin(26,0) dcl 29 set ref 104* 106 123 127 j 000112 automatic fixed bin(26,0) dcl 29 set ref 99* 101 102* k 000113 automatic fixed bin(26,0) dcl 29 set ref 102* 103 104* new_area 1 based bit(8) level 2 packed packed unaligned dcl 2-2 set ref 95* place 000116 automatic fixed bin(26,0) dcl 29 set ref 70* 71 72 80 82 83 89 92 103* 105 106 109 119 120 121* 121 122 125 130 rel builtin function dcl 29 ref 43 85 113 123 125 129 return_ptr parameter pointer dcl 29 set ref 26 38 40* 53* 96* save_offset 000115 automatic fixed bin(26,0) dcl 29 set ref 122* 131 size based fixed bin(8,0) level 2 in structure "buddy_block_header" packed packed unaligned dcl 2-12 in procedure "buddy_alloc_" set ref 119* 130* size parameter fixed bin(26,0) dcl 29 in procedure "buddy_alloc_" set ref 26 38 40* 53* 59 72 116 stop 000110 automatic fixed bin(26,0) dcl 29 set ref 45* 67 75 storage 000126 stack reference condition dcl 29 ref 141 sys_info$max_seg_size 000014 external static fixed bin(35,0) dcl 29 ref 72 106 NAMES DECLARED BY DECLARE STATEMENT AND NEVER REFERENCED. null builtin function dcl 29 ptr builtin function dcl 29 NAMES DECLARED BY EXPLICIT CONTEXT. alloc_block 000220 constant label dcl 72 ref 87 134 bad_area 000236 constant label dcl 75 ref 61 67 break_up 000305 constant label dcl 99 ref 81 buddy_alloc_ 000044 constant entry external dcl 26 buddy_storage_ 000057 constant entry external dcl 38 error_return 000461 constant label dcl 139 restart 000105 constant label dcl 43 ref 78 retry 000151 constant label dcl 59 ref 142 try_to_allocate 000162 constant label dcl 64 ref 114 117 THERE WERE NO NAMES DECLARED BY CONTEXT OR IMPLICATION. STORAGE REQUIREMENTS FOR THIS PROGRAM. Object Text Link Symbol Defs Static Start 0 0 554 572 474 564 Length 776 474 16 170 60 0 BLOCK NAME STACK SIZE TYPE WHY NONQUICK/WHO SHARES STACK FRAME buddy_alloc_ 111 external procedure is an external procedure. STORAGE FOR AUTOMATIC VARIABLES. STACK FRAME LOC IDENTIFIER BLOCK NAME buddy_alloc_ 000100 front buddy_alloc_ 000102 block_ptr buddy_alloc_ 000104 buddy_block_ptr buddy_alloc_ 000106 bit1 buddy_alloc_ 000107 count buddy_alloc_ 000110 stop buddy_alloc_ 000111 i buddy_alloc_ 000112 j buddy_alloc_ 000113 k buddy_alloc_ 000114 ind buddy_alloc_ 000115 save_offset buddy_alloc_ 000116 place buddy_alloc_ 000117 indx buddy_alloc_ THE FOLLOWING EXTERNAL OPERATORS ARE USED BY THIS PROGRAM. call_ext_out return_mac signal_op ext_entry THE FOLLOWING EXTERNAL ENTRIES ARE CALLED BY THIS PROGRAM. alloc_ area_ THE FOLLOWING EXTERNAL VARIABLES ARE USED BY THIS PROGRAM. sys_info$max_seg_size LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC 29 000035 26 000040 37 000052 38 000054 39 000065 40 000071 41 000104 43 000105 45 000113 46 000115 47 000117 52 000121 53 000132 54 000146 57 000147 59 000151 61 000154 63 000161 64 000162 66 000175 67 000176 68 000201 69 000206 70 000210 71 000213 72 000220 74 000232 75 000233 77 000236 78 000241 80 000242 81 000246 82 000252 83 000253 84 000256 85 000260 87 000264 89 000265 92 000271 94 000275 95 000277 96 000301 97 000304 99 000305 101 000321 102 000326 103 000337 104 000341 105 000344 106 000354 107 000361 108 000366 109 000371 111 000372 113 000374 114 000400 116 000401 117 000404 119 000405 120 000411 121 000415 122 000417 123 000422 125 000430 127 000433 128 000436 129 000440 130 000444 131 000447 133 000451 134 000454 136 000455 138 000457 139 000461 141 000467 142 000472 ----------------------------------------------------------- Historical Background This edition of the Multics software materials and documentation is provided and donated to Massachusetts Institute of Technology by Group BULL including BULL HN Information Systems Inc. as a contribution to computer science knowledge. This donation is made also to give evidence of the common contributions of Massachusetts Institute of Technology, Bell Laboratories, General Electric, Honeywell Information Systems Inc., Honeywell BULL Inc., Groupe BULL and BULL HN Information Systems Inc. to the development of this operating system. Multics development was initiated by Massachusetts Institute of Technology Project MAC (1963-1970), renamed the MIT Laboratory for Computer Science and Artificial Intelligence in the mid 1970s, under the leadership of Professor Fernando Jose Corbato. Users consider that Multics provided the best software architecture for managing computer hardware properly and for executing programs. Many subsequent operating systems incorporated Multics principles. Multics was distributed in 1975 to 2000 by Group Bull in Europe , and in the U.S. by Bull HN Information Systems Inc., as successor in interest by change in name only to Honeywell Bull Inc. and Honeywell Information Systems Inc. . ----------------------------------------------------------- Permission to use, copy, modify, and distribute these programs and their documentation for any purpose and without fee is hereby granted,provided that the below copyright notice and historical background appear in all copies and that both the copyright notice and historical background and this permission notice appear in supporting documentation, and that the names of MIT, HIS, BULL or BULL HN not be used in advertising or publicity pertaining to distribution of the programs without specific prior written permission. Copyright 1972 by Massachusetts Institute of Technology and Honeywell Information Systems Inc. Copyright 2006 by BULL HN Information Systems Inc. Copyright 2006 by Bull SAS All Rights Reserved