Abstract:
An apparatus for defragmenting disks by incorporating a copy function in the logic controlling a disk, so that a disk can be instructed to copy the contents of tracks from one area to another on the disk without requiring a series of data transfers between the disk and the host computer to which it is assigned. Conventional defragmentation techniques can be used to determine which files need to be defragmented and how much contiguous free space is available on the disk. Once this has been determined, the present invention enables the defragmentation program to send copy commands to the disk to cause the copy function in the logic controlling the disk to perform the data transfers, thus freeing up the host computer to perform other processing until the logic controlling the disk signals completion of the copy function&#39;s operation.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates generally to the field of mass storage devices and more particularly to systems and methods for defragmenting mass storage devices. 
     2. Background 
     Advances in mass storage technology have considerably increased the amount of data that can be stored on individual random access magnetic disk devices used with computers. As users add files to a disk, and then update and change those files, a phenomenon known as fragmentation tends to occur in most disk storage systems, whether the disks are attached to mainframe computers, workstations, or personal computers. 
     When a file is first created, many operating systems or file systems will cause the file to be allocated to a contiguous area, such as series of tracks or cylinders on the disk in mainframe systems, or blocks in open systems, if it is possible to get a contiguous area. For illustration, as shown in the allocation map of FIG. 4 a , if a simplified hypothetical disk has 80 tracks, the first file might be placed on tracks 0-30. However, if a second file is created on that disk it may be allocated at tracks 30-40. When the user wants to add data to the first file, most file systems and/or operating systems will accomplish this by allocating some additional space at another physical location on the disk for the addition, and updating pointers in the directory or volume table of contents on that disk to indicate that the first part of the file is still at tracks 0-30, but a second part has been added at tracks 40-50. When the second file needs to expand, it may be allocated space from tracks 50-80. 
     If the second file in this example is subsequently deleted, tracks 30-40 and 50-80 may be freed up, but the first file will still have two parts located at different sets of tracks—0-30 and 40-50. Thus, the first file has become and remains fragmented. (In this example, the second file was fragmented as well.) 
     Fragmentation tends to build up over time, as more files are added, deleted and modified on the mass storage system. Two problems occur as disks and files get more and more fragmented. The first, and usually more significant one, is that performance degrades when fragmented files on a fragmented disk are accessed. When a file is located in one contiguous area, it usually requires fewer seeks, or moving and repositioning of the read/write heads on the disk to find and read or write the data. As the file becomes fragmented and thus more spread out over the disk, more seeks will be needed to find a number of additional small sections or fragmented extents of the file. These additional seeks for many small fragments usually add to the time it takes to read or write or update the file. Now that disks can be not only many megabytes, but even gigabytes or greater in size, this can literally add minutes or sometimes hours to processing time, especially if all or a substantial portion of the file is being accessed. 
     A second problem arising from disk fragmentation is that space on the disk tends to be wasted. In the hypothetical example given above, after the second file has been deleted, there are two “holes” or empty areas free on the disk, from tracks 30-40 and from 50-80—a total of about 40 tracks. However, depending on the operating system and file system in use, a new file that needs 40 tracks might not be allocated to this disk, even though 40 tracks are free, simply because they are not contiguous. Many file systems will allow the user to indicate to which disk a file should be allocated—another way in which files may become fragmented when they otherwise might not if the user repeatedly selects an already fragmented disk. 
     One way to address the problem, at least in some filesystems, is to increase the initial allocation size for each file. For example, making all allocations at least 4 megabytes in size. Some filesystems will permit this, while others, such as some personal computer systems may make this difficult or impossible for a user to do. 
     Software programs known as defragmentation programs have also been written to address these problems. In the flow diagram of FIG. 5, a prior art approach with a defragmentation program operating in a host computer is shown. As noted there, a conventional defragmentation program reads the directories or volume table of contents on a disk (at step  510 ) in a mass storage system connected to that host to locate files that have significant fragmentation. Generally speaking, a defragmentation program finds or frees up enough space on the same disk for those files, and then writes them back out from the host computer&#39;s memory to a contiguous area on the selected disk(s). (See steps  520 - 560 ). Since each fragmented file is read from the disk into the host computer and then written back out to disk in the loop shown at steps  530  to  550 , it can be seen that as the files and disks get larger, this may take longer and longer to accomplish. Also in FIG. 5, the darkened arrows I/O indicate the transfer of data between the host computer and a disk  15 . As can be seen with this prior art approach, the loop at steps  530 - 550 , can involve a significant number of I/O transfers between the host computer and the disk. Even in small personal computer systems, these I/O requests to read in and then rewrite all fragments may be slowed down by competing requests for other disks or devices on the same bus as the disk that is being defragmented. 
     Whether the defragmentation program handles only a file or even a fragment at a time, it will read the file or fragment into the host computer over a bus, then write it out from the host computer over a bus to the disk. Thus, although defragmentation programs help return mass storage systems to optimal performance, they may also create risk. If the system crashes while the program is reading and writing a file or fragment back out to disk, one or more files could be corrupted. Thus, the longer it takes for the defragmentation program to run, the greater is the risk that unexpected occurrences may cause a system failure or crash. As the size of the files being defragmented increases, more time is spent reading the files into the host computer and writing them back out to the disk. Thus, defragmenting larger files takes more elapsed time due to the number of I/O transfers to and from the host and may also increase the risk of file corruption in the event of a system failure. Many defragmentation programs attempt to minimize this risk by not allocating the new, defragmented file, until the whole operation is complete and error-free. While this tends to minimize the risk of corruption, if the system crashes before defragmentation is complete, minutes or hours of time could still be wasted by the conventional approach of defragmentation programs. 
     One attempt to avoid fragmentation is used by some database programs that allocate very large areas of contiguous space to a database file when the file is first created. While this tends to minimize the performance problem, it does waste space. And it is typically limited to sophisticated database application programs. Most other types of files, on most computer systems, whether large or small, tend to be subject to file fragmentation over time. 
     It is an object of this invention to minimize the need to transfer fragmented file data from a disk into a host computer and back to the disk again. 
     It is another object of the present invention to improve the performance of defragmentation operations. 
     SUMMARY OF THE INVENTION 
     The present invention incorporates a copy function in the logic controlling a disk, so that a disk system can be instructed to copy the contents of tracks from one area to another on the disk without requiring a series of data transfers between the disk and the host computer to which it is assigned. Conventional defragmentation techniques can be used to determine which files need to be defragmented and how much contiguous free space is available on the disk. Once this has been determined, the present invention enables the defragmentation program to send copy commands to the disk to cause the copy function in the logic controlling the disk to effectuate the data transfers, thus freeing up the host computer to perform other processing until the logic controlling the disk signals completion of the copy function&#39;s operation. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 a  is a schematic drawing of one preferred embodiment of the present invention. 
     FIG. 1 b  is a schematic drawing of an alternative preferred embodiment of the present invention. 
     FIG. 1 c  is a schematic drawing of another preferred embodiment of the present invention. 
     FIG. 1 d  is a schematic drawing of yet another preferred embodiment of the present invention. 
     FIG. 1 e  is a schematic drawing of still another preferred embodiment of the present invention. 
     FIG. 1 f  is a schematic drawing of yet one more alternative preferred embodiment of the present invention. 
     FIG. 1 g  is a schematic drawing of still one more alternative preferred embodiment of the present invention. 
     FIG. 2 is a flow diagram of the present invention. 
     FIG. 3 a  is a schematic drawing showing the syntax of a copy command according to the method and apparatus of the present invention. 
     FIG. 3 b  is a schematic drawing showing a local level buffered implementation of a preferred embodiment of the present invention. 
     FIG. 4 a  is a schematic diagram showing two fragmented files. 
     FIG. 4 b  is a schematic diagram showing one fragmented file. 
     FIG. 4 c  is a schematic drawing of a fragmented disk. 
     FIG. 4 d  is a schematic drawing of a fragmented disk after partial defragmentation. 
     FIG. 4 e  is a schematic drawing of a disk with defragmented files. 
     FIG. 5 is a flow diagram of the prior art. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     In FIG. 1 a , a schematic block drawing of one preferred embodiment is shown. As seen there, disk subsystem  30  is connected to bus  05 , which, in turn, communicates with host  00 . Host  00  is shown executing an operating system  02  and a defragmentation program  04 . Disk subsystem  30 , according to the method and apparatus of the present invention, includes control logic  10  for generally controlling the operation of disk  15 . In this preferred embodiment, control logic  10  includes a copy function  20  as part of its logic. Copy function  20 , in a preferred embodiment, is capable of copying a specified number of tracks from one physical address on disk  15  to another physical address on disk  15 , without having to transfer these tracks to and from host  00 . In a preferred embodiment, defragmentation program  04  supplies these addresses, together with the number of tracks to be copied, to copy function  20 . As will be apparent to those skilled in the art, host  00  could be a mainframe computer system, in which case bus  05  might be a channel or channel subsystem or ESCON subsystem. Similarly, host  00  could be a workstation or a personal computer, in which bus  05  might be some form of SCSI bus interface between the host and the disk subsystem  30 . 
     For mainframe computer systems or larger workstation systems, where the logic controlling disks often involves several components, a preferred embodiment such as that shown in FIG. 1 b  might be used. In FIG. 1 b , host  00  is connected to bus  05 , which in turn, is connected to disk controller  07 , which controls disk subsystems  30 . In this preferred embodiment, each disk subsystem  30  includes control logic  10  with a copy function  20  and a disk  15 . 
     Turning briefly to FIG. 3 b , a preferred embodiment of disk subsystem  30  is shown in which a buffer  22  is included in control logic  10 . In this embodiment, buffer  22  can be used by copy function  20  to hold all or part of the data contents of the tracks being copied from one area to another on disk  15 . As will be apparent to those skilled in the art, whether a buffer is needed and the size required for it, will depend on the specifications of the disks  15  being used for such matters as transfer speeds, latency times, costs, etc., as well as the design features of the controlling logic components and the other parts of the mass storage system. The preferred embodiments of the present invention use a buffer when copy function  20  is part of control logic  10  in disk subsystem  30 . 
     Now turning to FIG. 1 c , another alternative preferred embodiment is shown. Here host  00  is connected to bus  05 , to which, in turn, controller  07  is connected. Controller  07 , in FIG. 1 c  controls conventional disk subsystems  31 , but controller  07  includes copy function  20  and buffer  22 . 
     In FIG. 1 d , a more complex control scheme for disks is shown, such as might be used more typically in large mainframe computers. In FIG. 1 d , host  00  is connected to bus  05  which, in turn, is connected to a disk adapter  08 , which includes copy function  20 . Disk adapter  08 &#39;s logic controls two disk controllers  07 , which, in turn control several conventional disk subsystems  31  apiece. In this preferred embodiment, buffer  22  might be located in controllers  07 . 
     FIG. 1 e  shows another preferred embodiment for a large mainframe configuration. In FIG. 1 e , multiple hosts  00  share a large multiple disk system  12 . In this preferred embodiment, each host  00  is connected by means of one or more buses  05  to a host director  08  in multiple disk system  12 . In applicant&#39;s Assignee&#39;s Symmetrix 5XXX series, a host director  08  is also connected to global shared memory M and to either internal bus X or internal bus Y. Internal bus X and internal bus Y are also connected to several disk directors  07 . In this preferred embodiment, disk directors  07  are connected to a plurality of disk subsystems  30  of the present invention, such as those shown in FIG. 3 b . As noted in connection with FIG. 3 b , each disk subsystem  30  of the present invention includes control logic  10 , copy function  20  and buffer  22 , as well as disk  15 . Thus, in this preferred embodiment, each individual disk  15  in multiple disk system  12  has its own copy function  20  as part of its logic. 
     As will be apparent to those skilled in the art, variations of this embodiment could be implemented as well, such as that shown in FIG. 1 f . There multiple disk system  12  includes host directors  08  and disk directors  07 , too. In FIG. 1 f , however, copy function  20  is incorporated into disk directors  07 , thus allowing conventional disk subsystems  31  to be used. In this preferred embodiment, buffer  22 , if needed can be a specified area in global shared memory M. 
     Similarly, FIG. 1 g  shows another alternative preferred embodiment using applicant&#39;s Assignee&#39;s Symmetrix 5XXX multiple disk system. In FIG. 1 g , multiple disk system  12  is configured with copy function  20  as part of the host directors  08 , again allowing the use of conventional disk subsystems  31  with disk directors  07 . 
     Turning briefly to FIG. 4 c , a schematic drawing of a disk with several fragmented files is shown. In FIG. 4 c , the directory dir, shows there are three files, A, B and C allocated or placed on disk  15 . File A is in three sections or fragments A 1 , A 2  and A 3 , which are pointed to by directory dir. Those skilled in the art will appreciate that directory dir will typically ‘point’ to these fragments or extents of file A by using starting and ending addresses on the disk or starting address and counts indicating size. File B also comprises three fragments while file C is spread over only two fragments on the disk. In the example shown in FIG. 4 c , there are only two free areas, F 1  and F 2  on disk  15 . With heavily fragmented file systems there are usually many more free areas that are smaller in size interspersed amongst the allocated files. However, as in this example, many, if not most disks usually have at least 20% of their total area free. 
     Now turning to FIG. 2, a flow diagram of a defragmentation program  04  used in conjunction with the present invention is shown. At step  200 , defragmentation program  04  reads the directory dir of a disk to find a file and its fragments. If the disk were the one shown in FIG. 4 c  and file A were the file in question, this step would locate the three fragments A 1 , A 2  and A 3  shown in FIG. 4 c . Back in FIG. 2, at step  210 , defragmentation program  04  would also read the directory dir to locate contiguous free areas large enough to hold the complete file A. Again using the disk illustrated in FIG. 4 c , free area F 2  would be large enough to hold all of file A. 
     Now back in FIG. 2 again, at step  220 , a defragmentation program  04  according to the method and apparatus of the present invention would compute the addresses to be used for the copy function  20  of the invention. In the example used, this would be the starting addresses of A 1 , A 2  and A 3 , and their respective sizes, as well as the starting address of free area F 2 . Next, at step  230 , defragmentation program  04  according to the method and apparatus of the present invention would temporarily allocate a free area (F 2  in the above example) on the disk to hold the new copy of file A, and send a copy command with the addresses required for the first fragment, A 1 , over bus  05  to copy function  20  in the logic controlling the disk containing file A. Next, in a preferred embodiment, defragmentation program  04  would wait, at step  240 , for the copy function to complete copying this fragment. As will be apparent to those skilled in the art, while defragmentation program  04  is waiting, other tasks can be performed by host  00 , and other devices can be accessed on bus  05 , while the copy function  20  of the present invention copies this fragment. 
     When a successful completion has been received at step  240  in FIG. 2, defragmentation program  04  according to the present invention checks, at decision block  250  to see if there are more fragments to be copied. In the example of File A, there are, so defragmentation program  04  of the present invention loops through steps  230 ,  240  and  250  until there are no more fragments to be copied. At that point, at step  255 , defragmentation program  04  of the present invention would permanently allocate the new area holding the defragmented file A and free the old areas A 1 , A 2  and A 3 . 
     Still in FIG. 2, at step  260 , the flow of copy function  20  is shown starting with a wait for a copy command to be sent to it. At step  270 , copy function  20  copies from a first address addra, to a second address addrb and decrements a count ct accordingly. At decision block  280  the present invention checks to see if the count equals zero for this fragment. If not, the copy function goes back to step  270  to continue the copying of this fragment into the newly allocated space. If the count is zero at decision block  280 , the invention checks at step  290  to see if there have been any errors. If there are, an error signal is generated at step  300 . If there are no errors, copy function  20  will signal successful completion of the copy of this fragment at step  310 . 
     At the end of a successful defragmentation of file A, the disk might look like the example shown in FIG. 4 d , where the three original segments of file A have now been consolidated into one file with one extent. In FIG. 4 d , it can be seen that disk  15  now has four free areas interspersed throughout the disk. If the remaining fragmented files on disk  15  were defragmented using the present invention, disk  15  might appear as shown in FIG. 4 e , with files A, B and C defragmented. 
     As will be apparent to those skilled in the art, there are several ways in which copy function  20  could be implemented without deviating from the spirit of the invention. For example, rather than identify a fragment at a time and send that address in a copy command to copy function  20 , defragmentation program  04  could identify all fragments and their addresses in one copy command, provided there is sufficient memory available to copy function  20  to store and queue these additional addresses. In the preferred embodiment diagrammed in FIG. 2, each fragment is copied without interim input/output data transfers between the disk control logic and host  00 . 
     Referring back to FIG. 1 b , now it can be seen that defragmentation program  04  could initiate defragmentation operations in each disk subsystem  30  attached to controller  07 , so that all three disk subsystems  30  shown here could be executing a copy function  20  at the same time. Once a copy function has been initiated in a disk subsystem  30  as shown here, data transfers occur between control logic  10  and disk  15  internal to disk subsystem  30 , thus leaving the other disk subsystems  30  free to perform normal input/output transactions. If two of the three disk subsystems  30  of FIG. 1 b  are executing copy functions  20  to defragment files, host  00  could have other programs executing and issuing ordinary input/output commands to the third disk subsystem  30  connected to controller  07 . 
     Those skilled in the art will appreciate that when copy function  20  is placed in the control logic closest to each individual disk, as shown in FIGS. 1 b  and  3   b , performance tends to be optimized, since copy function  20  allows each disk to undergo defragmentation without requiring significant data transfers over the controls between the disk  15  and host  00 . In other words, if copy function  20  is embedded in control logic  10  as shown in FIG. 3 b  and control logic  10  has immediate control over disk  15 , this should provide better overall performance for defragmentation operations. 
     By contrast, FIG. 1 g  illustrates a design where performance of defragmentation operations may be slower than that of FIG. 1 b , since copy function  20  is embedded in the control logic “farthest” from disk  15  in conventional disk subsystem  31 , namely in host director  08 . As shown in FIG. 1 g , there are several levels of control logic controlling disk subsystems  31 —ranging from the most immediate control logic  10 , (not visible in this view) to disk director  07  to host director  08 . However, a placement such as this in host controller  08  allows the use of existing or conventional disk subsystems  31  and disk directors  07 . The placement shown in FIG. 1 f , where copy function  20  is embedded in the intermediate control logic of disk director  07 , might provide performance benefits while still permitting the use of existing conventional disk subsystems  31 . 
     In a preferred embodiment, copy function  20  would be implemented in hardware circuitry that forms part of the disk control logic component selected. As will be apparent to those skilled in the art, however, it could also be implemented in microcode or in software if the control logic component selected is fast enough to permit timely processing by the copy function. 
     Those skilled in the art will appreciate that the embodiments described above are illustrative only, and that other systems in the spirit of the teachings herein fall within the scope of the invention.