Find Logical Blocks A Contiguous Block Identification Utility 15-FEB-81 (Revised 19-JUN-81) J. Bradley Flippin Raytheon Service Company 2341 Jefferson Davis Highway (Suite 1200) Arlington, Virginia 22202 Phone (703) 685-2200 FLB --- A contiguous block utility program PAGE 2 Program Description Background: Disk cartridges and packs are structured into tracks and sectors. these sectors, each of which contains a block (or partial block) of data, are used by the operating system to store files. Under RSX-11M, this file structure is known as FILES-11 and consists of one (or more) header blocks and any number of associated data blocks. The data blocks are assigned by the FILES-11 Auxiliary Control Processor (F11ACP) to the respective header by means of map pointers. Basically, as the system needs blocks, they are allo- cated in a systematic way: Always from the bottom up! This process continues until the file is full. Deleting files results in the de-allocation of the respective blocks as in- dicated in the file header's map area. This makes them ava- ilable for the next user. As time progresses, it can be seen that the disk can become a "shotgun" of randomly as- signed data blocks. This fragmentation may eventually have an adverse affect, particularly when a task requires large blocks of contiguous space, such as SORT which requires them for its working files. The scattered blocks can be consolidated (or com- pressed) by using the Disk Save and Compress (DSC) utility. However, this requires that the disk be copied to another media and then re-built on the original media. If tape is used, or only a few files are destroying the contiguous space, then a faster way would be to free up the contiguous space by moving the guilty files. This would require searching every header and then searching all its map po- inters to see if any of their data blocks are in the affect- ed area. This is a long and difficult manual process. FLB, however, will find the guilty files for you. BITMAP.SYS: The one system file which holds the key to which blocks are in use (allocated) and which are available for use is BITMAP.SYS which is located in the null directory [0,0]. It is a file in itself. It has a header which maps one Storage Control Block (SCB) and "n" bitmap blocks, each capable of "mapping" 4096 decimal blocks. Thus, the floppies (RX02) use one bitmap block where the RK07 has 14 bitmap blocks (not counting the SCB which is always VBN #1). To use the FLB utility, all one needs to do is dump BITMAP.SYS and use it as a roadmap to find and identify the desired blocks. The space is freed by the simple process of moving them. The F11ACP always assigns the new blocks starting at the lowest numbered blocks. This effectively moves the files to the front of the device, unless, of FLB --- A contiguous block utility program PAGE 3 Program Description course, the device is already full. Assembling and Task Building FLB: Building FLB is relatively straight forward. The source media should contain the following files: 1. FILES.MAC;1 dated 15-FEB-81 (Source file) 2. FILES.COR (The latest correction file) 3. FILES.CMD (A command file to build FILES) 4. MOVE.CMD (A command file to move guilty files) 5. FILES.DOC (This documentation file) 6. COPY.CMD (A command file to make copies of the source media) To build FLB, simply copy the source to your media with @COPY then run @FILES. The file will ask whether or not you want a listing. If yes, it will put FILES.LST on SY:. When installed, the task will have the name "...FLB". FLB --- A contiguous block utility program PAGE 4 Program Description How to Use FLB: The following procedure is recommended (all numbers are octal unless otherwise indicated): 1. The device in question must be mounted. 2. Determine the free space available by using PIP. Enter: PIP DM:/FR (or FREE, if TDX is installed). If the number of free blocks exceeds by a large am- ount the number of contiguous free blocks, then FLB will be of some help. If not, then moving the files may simply move them to higher block numbers. 3. Dump the bitmap by entering: DMP BITMAP=DM:[0,0]BITMAP.SYS 4. Examine the bitmap dump, looking for the largest grouping of "1" bits (ie: l777777 indicates all 16 decimal blocks represented by that word are avail- able). Generally, these will be towards the end of the device. Note that the last block generally shows a large portion of allocated blocks towards the end. This is because most devices do not have an integral multiple of 4096 decimal blocks. 5. FLB can now be used to identify the desired files. Simply enter the search parameters by means of input switches. Figure 1 shows a sample output. the following are examples of various command line inputs: 1. Show all files containing blocks in virtual block number 15 of BITMAP.SYS: FLB TI:=DM:/BLK:15:15 2. Print a listing of the file using a specific LBN (ie: 4200)-(Note that the /LBN switch utilizes double precision): FLB LP:=DM:/LBN:0:4200:0:4200 3. Spool a file "FILES.LST" on SY: listing all files represented by the 16 bits of word 10 of BITMAP VBN 15: FLB =DM:/BLK:15:15/WD:10:10 4. Search the BITMAP starting with block 15 and extending to the end of the device: FLB --- A contiguous block utility program PAGE 5 Program Description FLB TI:=DM:/BLK:15 5. Search the BITMAP to the end of the device starting at a specific word: FLB TI:=DM:/BLK:15/WD:20 6. The affected files can now be moved. Go to the proper directory (UIC) and use PIP /NV/CD=filename.type;ver. Be sure to use the spec- ific file version. Once the file has been moved, the specific version can then be deleted (The same thing can be accomplished by using the MOVE command file). FLB --- A contiguous block utility program PAGE 6 Program Description Problems: Problems may be encountered during the use of FLB. Usually then can be resolved. The following are a few exam- ples (references are to the Utility Manual [AA-H268A-TC]): 1. All headers may not be listed in a UFD. This is evident when a filename.type;version cannot be found with PIP [*,*]. Solution: Run VFY with the /LO switch (see Section 13.3.5). This will find the "lost" file(s) and place them in the lost files directory [1,3] where they can be properly deleted. 2. All blocks may not be mapped to a header. This is evident when files does not list a culpret, but the bit is shown as set in the BITMAP.SYS Dump. Solution; Run VFY with the /RE switch (See Section 13.3.7). 3. Finally, it may be a bad block. This is evident when the FILES listing contains [1,1]BADBLK.SYS as one of the first entries (headers are serached in sequence - BADBLK.SYS is header number 3). Do not confuse "last track" protection provided to last track devices (ie: RK06/7, RL01/02, and RM02/03) with actual bad blocks. This can be verified by dumping the header of BADBLK.SYS. The first entry in the map area will show blocks mapped at the end, then the actual bad blocks are mapped individually. (See Section 9.3.1.2). If it is a bad block, there is no solution, except to get a new disk. FLB --- A contiguous block utility program PAGE 7 Program Description Notes: 1. Remember, all UIC's in the FLB listing are those of the OWNER. Generally this will also be the di- rectory in which they are listed. If not, then search for them using a wildcard PIP command (ie: PIP [*,*]filename,type;ver. 2. Special conditions apply to UFD's because the File ID is contained in the MFD. A UFD is identified by a filespec similar to: DM0:[001,001]007007.DIR;1. The proper procedure here is: 1. Move any files in the UFD to another UFD (using the /CD switch if desired). 2. Delete the files from the original UFD. 3. Delete the UFD (ie: PIP [0,0]007007.DIR;*/DE). 4. Create a new UFD with the same UIC (ie: UFD DM:[7,7]). 5. Run FLB again to ensure it has not put the new UFD in the same area of interest (or dump its header and check the map pointers). 6. Finally, copy back the output files to the new UFD (using the /CD switch again, if desired). 3. If the file is an installed task, then it must be removed (REM) and re-installed (INS) after the move, or the system may crash when it is called. (Don't forget to do this to your task image by run- ning VMR). 4. For additional information see the MACRO source listing. FLB --- A contiguous block utility program PAGE 8 Program Description Example: DM0:[001,001]BADBLK.SYS;1 <------ (Indicates a bad block) DM0:[104,060]EDITOR1.TMP DM0:[111,142]VSCAT.OBJ;3 DM0:[111,141]SHP733.LST;1 DM0:[111,064]AOSTUDY.TSK;2 DM0:[111,142]VSCAT.LST;10 DM0:[111,142]VSCAT.SKL;3 DM0:[111,141]SHP732.LST;1 DM0:[106,130]REPORT.FTN;6 DM0:[111,064]AOSTUDY.TSK;1 DM0:[104,060]KWIC.LST;25 DM: = 53790. BLOCKS SPAN: 4096. BLOCKS LO LBN: H:000 L:130000 = 45056. HI LBN: H:000 L:137777 = 49151. FILES FOUND: 11. ELAPSED TIME: 00:01:24 LP:=DM:/BLKS:15:15 Figure 1 - Example of FLB run on an RK07 FLB --- A contiguous block utility program PAGE 9 Technical Description INTRODUCTION The following technical notes are provided for those who desire to know what is happening within the FLB pro- gram References are to the I/O Operation and Reference Manu- al (AA-2515D-TC). Details of the command line processng, FCS, and the simpler routines are not provided. The basic assumption of FLB is that it will be work- ing on a FILES-11 structured device. This means that it will be looking for certain things in certain places. Specifically, it assumes that the device contains the stan- dard five system files (only the first one is accessed by FLB). #1 - INDEXF.SYS #2 - BITMAP.SYS #3 - BADBLK.SYS #4 - 000000.DIR #5 - CORIMG.SYS Command Line Processing The command line includes two output switches and three input switches. The output switches are /ID (to provide the program version number) and /SP (to spool the output). The defaults are /-ID and /SP, respectively. The three input switches are /LBN, /BLK, and /WD. The /LBN switch permits the user to specify a logical block number (or numbers) directly. The format is standard double precision (ie: /LBN:0:100:0:100 = LBN #100 only). The other switches are designed to match the BITMAP.SYS dump and are mutually exclusive with the /LBN switch. The /BLK switch may stand alone, but the /WD switch requires the /BLK switch. The output switches are first validated to ensure the above logic has been observed. Next the switch values are validated by "VALIDATE SWITCH VALUES." Here a stop value of zero is replaced by the SIZE parameter which was extracted from the device's Home Block by the Get LUN (GLUN$) direc- tive during the parsing of the input filespec. This value (minus one) is set into the stop LBN if it is not present (or equal to zero). The /BLK switch is validated next to ensure that is is greater than one and that the stop block is not less than the start block value. The /BLK switch was designed to per- mit the user to enter the octal block numbers from a BITMAP.SYS dump directly. Thus, the /BLK validation routine esures that the Storage Control Block (VBN #1) is passed. FLB --- A contiguous block utility program PAGE 10 Technical Description Finally, the /WD switch is validated by ensuring that it is less than 512 (decimal), that it is an even number (word aligned), and that the top value is less than the start value only in those cases when the start/stop /BLK va- lues differ (interblock search). Once the switches have been logically verified and the values validated, then the actual start and stop LBN is cal- culated. If the /LBN switch was used, then the "GENERATE THE LBN VALUES" routine is bypassed. Otherwise, the /BLK values are converted to LBN values by the equation shown on the listing. The /WD values are then added or subtracted from the resulting LBN's as required. Processing The first action, after deciding that the command line was proper, is to retrieve the Home Block, which is LBN #1 on the device. This is accomplished by the FCS procedure "RETRIEVE HOME BLOCK". The INDEXF.SYS file is non- conven- tional, in that the offsets F.HIBK (the highest block allo- cated to the file) and F.EFBK (the end-of-file block) are both zero. These must be set to their logical values so the program can scan the headers and detect an EOF condition at the appropriate time. This is acommplished by opening the file with the statisitics block, as described in Paragraph 3.1.2 under file option 3.d (Page 3-11). The statistics block is shown in Figure H-1 on Page H-1. Once the INDEXF.SYS header file FDB has been reset, then the home block is read into the buffer region named "HEADER." The important values in the home block are the first two bytes (H.IBSZ) which indicates the size of the index file bitmap, ant the next four bytes (H.IBLB) which contain the LBN of the first block of the index file bitmap in dou- ble precision format. These are important because they pro- vide the physical location (LBN) of VBN #3, which is the start of the header bitmap and its length. Adding the two together provides the LBN of the first header (1,1) which happens to be INDEXF.SYS. The program is now set to scan the headers. The "RETRIEVE A HEADER BLOCK" routine reads each header sequentially. Offset H.FNUM is checked each time. If it is zero, then it is a deleted header and the next one is read. If it is not zero, then it begins searching the map pointer region of the header. Each file header contains a map area which consists of, among other things, an offset M.USE (one byte) which is a count of the number of map pointers in use. The maximum value is 102 pointers (The actual value is the number of FLB --- A contiguous block utility program PAGE 11 Technical Description words used or twice the the number of pointers used). If this value is null, then it is either a null header or the program has checked all of its pointers. The secton of the header used in the searching is the retreival pointer sec- tion which starts at offset M.RTRV. To find this offset, the program steps past the header section (S.HDHD), the identification section (S.IDHD), to the start of the retri- eval section (M.RTRV) (See the equated symbol MPTR in the listing). Each pointer consists of two words (four bytes). The first byte contains the high order eight bits of the 24 bit LBN. Byte two contains the count field and bytes three and four contain the 16 low order bits of the LBN. Each pointer can map up to 256 (decimal) contiguous blocks. The value of the count is actually n-1, thus a zero points to one block, while a value of one points to the first of two contiguous blocks. The "SEARCH MAP POINTERS" routine checks the MUSE location first, exiting if it contains a zero. Otherwise, it extracts the two word map pointer and divides it into a count filed and a double precision LBN, then calls SEARCH which decrementes until it reaches zero (or a match is found) at which time the next header is read. The actual search routine is contained in "SEARCH FOR A MATCH." It performs a search based on the following logic: 1. If the LBN of the first block of the pointer is below the starting LBN, then there is no match pos- sible and it exits. 2. If it is equal, then there is a match of at least the first block. The OUTPUT routine is called which outputs the full filespec to the output FDB. 3. If it is greater than the first LBN of the pointer, then no immediate conclusion can be reached, so the LBN must be checked against the stop LBN. 1. If it is LT/EQ, then a match has occurred. 2. If NE, then the LBN of the last block in the pointer's contiguous group must be calculated by adding the count field to the pointer's LBN. 1. It it is LT/EQ, then a match has occurred. 2. If not, then it is outside of the range and the routine exits. FLB --- A contiguous block utility program PAGE 12 Technical Description The above process is repeated for each header until an EOF condition is reached, at which time the summary is out- putted. FLB --- A contiguous block utility program PAGE 13 Technical Description Correction File Corrections to the orginal source file will be made by means of a correction file to be used with SLP. The current correction file FILES.COR contains the code necessary to up- date FLB to version l.0A. This includes code to correct for DP LBN's, corrects some DP arithmatic errors, cleans out the high byte in CW2, plus adds a diagnostic capability. In addition, it has been tested on RSX-11M (PLUS) and an RP06 drive. The new diagnostic switch /DA acts the same as the /-LI switch plus it provides a means for the user to force a dif- ferent value into the SIZE value (number of blocks on the device). The default value will be that of the device indi- cated. Otherwise the program will use the supplied value which is stored in DASIZE. For example: FLB TI:=DM:/DA:1:1000/BLK:5:5 The above command string will force the program to set the size parameter to 66048 (decimal). (Arbitrary values must be used with either the /LBN or /BLK switches, because of the syntax. These values must be less than the selected /DA value.) -JBF