Method and apparatus for processing recursive hard links in a data processing system

[0002] 1. Technical Field

[0003] The present invention relates generally to an improved data processing system and in particular to a method and apparatus for processing errors in a data structure in a data processing system. Still more particularly, the present invention relates generally to a method and apparatus for handling recursive hard links in a directory structure in a data processing system.

[0004] 2. Description of Related Art

[0005] The manipulation of data in a data processing system is well known in the prior art. Data may be manipulated in many ways in a modern state-of-the-art data processing system including: data accessing, data encoding, data communications, data compression, data conversion, data entry, data exchange, data filing, data linking, data locking, data manipulation, data mapping, data modeling, data processing, data recording, data sorting, and data transferring. The large amounts of data that are available to the user of a modern state-of-the-art data processing system often become overwhelming in magnitude and complexity.

[0006] In today's information systems environment, recovery from computer problems whether from hardware or software difficulties, or from administrator error needs to be accomplished quickly and effectively. The first two error classes, hardware and software, are well documented, as computer solutions evolve with both platform advances and the introduction of inadvertent program errors. The later problem type, administrator error, is one which would not be a concern in a perfect world, but which unfortunately occurs all too often. The problem of recursive link creation has stemmed from the actions of inexperienced system administrators as they try to create soft, symbolic links. In particular, the creation of such links, using the UNIX command “ln-s” is standard fare, and is executed often. The purpose of this command is to create a “soft” link pointing to another file or directory, such that the latter entity can be accessed through the symbolic link. A vastly different command, “link” also exists within the UNIX world. This latter command actually redirects the inodes, the file indexing pointers, to physically point at the file or directory in question. The difference between the two commands can be illustrated by comparing the effects of deleting a soft or hard link. If a symbolic link “d” is created to another file “a”, then the link “d” is deleted, the file “a” remains intact. That is to say that only the link is deleted. If a hard link “d” is created to another file “a”, then the link “d” is deleted, the file “a” is also deleted.

[0007] Returning back to the fundamental problem, what happens when a recursive hard link, connecting a low-level directory to a higher-level directory, is inadvertently created? The result can be a directory chain like: /usr/a/b/c/d/a/b/c/d/a/b/c/d . . . where “d” has a hard link back to directory “a”. The first inclination in such a case is to try to unlink “a” from “d”. This operation, once the link is created, is not permitted by many UNIX operating system varieties. One solution which has been used in the past is to move one level above “d”, the bad link, and unlink form directory “c”. This operation is permitted by Advance Interactive Executive (AIX), an operating system from International Business Machines Corporation, although it has unpleasant implications. Any other files and/or directories beneath directory “c” would be lost, in addition to the undesired hard link. For example, if the directory structure /a/b/c/d housed a corporate web site, comprising over 10,000 files and the content beneath “c” alone totaled 2,000 files, these 2,000 files could not be accessed and would normally be lost. Losing 2,000 files to save the filesystem is an unattractive option. To complicate matters, the nature of a recursive hard link prohibits standard backups from being accomplished. Any backup command, from “mksysb” to more selective techniques, will use a “find” command to explore the depths of the directory structure. However, the “find” command will never return from such an infinite structure. Such a situation may crash a data processing system when trying to run backups because the mksysb process may create a rootvg map, a map file, that fills up the entire hard disk, resulting in subsequent system failures. As a result, in such a situation, a back up of some files in the file system cannot be made.

[0008] Therefore, it would be advantageous to have an improved method and apparatus for handling recursive links.

[0009] The present invention provides a method and apparatus in a data system for processing a recursive link in a directory structure in a data processing system. A path to a directory is identified including the recursive link in the directory structure, wherein the path includes a hierarchy towards a root directory, which is a highest directory. Responsive to identifying the path, a highest unprocessed directory in the path is selected as a current directory and all directories in the directory structure beneath the current directory are identified, excluding a directory below the current directory in the path. This step is performed until all directories in the path down to the directory having the recursive link have been processed to form a set of identified directories. All files within the set of directories are identified to form a set of identified files, which then permits backup operations to proceed.

[0010] The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as a preferred mode of use, further objectives and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

[0011] FIG. 1 is a pictorial representation depicting a data processing system in which the present invention may be implemented in accordance with a preferred embodiment of the present invention;

[0012] FIG. 2 is a block diagram illustrating a data processing system in which the present invention may be implemented;

[0013] FIG. 3 is a diagram illustrating a directory structure depicted in accordance with a preferred embodiment of the present invention;

[0014] FIG. 4 is a flowchart of a process for processing a recursive link depicted in accordance with a preferred embodiment of the present invention;

[0015] FIG. 5 is a flowchart of a process for creating a new file system without the recursive link depicted in accordance with a preferred embodiment of the present invention; and

[0016] FIGS. 6A-6F are diagrams illustrating a script used to process recursive links depicted in accordance with a preferred embodiment of the present invention.

[0017] With reference now to the figures and in particular with reference to FIG. 1, a pictorial representation depicting a data processing system in which the present invention may be implemented in accordance with a preferred embodiment of the present invention. A personal computer 100 is depicted which includes a system unit 110, a video display terminal 102, a keyboard 104, storage devices 108, which may include floppy drives and other types of permanent and removable storage media, and mouse 106. Additional input devices may be included with personal computer 100. Personal computer 100 can be implemented using any suitable computer, such as an IBM Aptiva™ computer, a product of International Business Machines Corporation, located in Armonk, N.Y. Although the depicted representation shows a personal computer, other embodiments of the present invention may be implemented in other types of data processing systems, such as network computers, Web based television set top boxes, Internet appliances, etc. Computer 100 also preferably includes a graphical user interface that may be implemented by means of systems software residing in computer readable media in operation within computer 100.

[0018] With reference now to FIG. 2, a block diagram illustrates a data processing system in which the present invention may be implemented. Data processing system 200 is an example of a computer, such as computer 100 in FIG. 1, in which code or instructions implementing the processes of the present invention may be located. Data processing system 200 employs a peripheral component interconnect (PCI) local bus architecture. Although the depicted example employs a PCI bus, other bus architectures such as Micro Channel and ISA may be used. Processor 202 and main memory 204 are connected to PCI local bus 206 through PCI bridge 208. PCI bridge 208 also may include an integrated memory controller and cache memory for processor 202. Additional connections to PCI local bus 206 may be made through direct component interconnection or through add-in boards. In the depicted example, local area network (LAN) adapter 210, SCSI host bus adapter 212, and expansion bus interface 214 are connected to PCI local bus 206 by direct component connection. In contrast, audio adapter 216, graphics adapter 218, and audio/video adapter 219 are connected to PCI local bus 206 by add-in boards inserted into expansion slots. Expansion bus interface 214 provides a connection for a keyboard and mouse adapter 220, modem 222, and additional memory 224. SCSI host bus adapter 212 provides a connection for hard disk drive 226, tape drive 228, and CD-ROM drive 230. Typical PCI local bus implementations will support three or four PCI expansion slots or add-in connectors.

[0019] An operating system runs on processor 202 and is used to coordinate and provide control of various components within data processing system 200 in FIG. 2. The operating system may be a commercially available operating system such as OS/2, which is available from International Business Machines Corporation. “OS/2” is a trademark of International Business Machines Corporation. An object oriented programming system such as Java may run in conjunction with the operating system and provides calls to the operating system from Java programs or applications executing on data processing system 200. “Java” is a trademark of Sun Microsystems, Inc. Instructions for the operating system, the object-oriented operating system, and applications or programs are located on storage devices, such as hard disk drive 226, and may be loaded into main memory 204 for execution by processor 202.

[0020] Those of ordinary skill in the art will appreciate that the hardware in FIG. 2 may vary depending on the implementation. Other internal hardware or peripheral devices, such as flash ROM (or equivalent nonvolatile memory) or optical disk drives and the like, may be used in addition to or in place of the hardware depicted in FIG. 2. Also, the processes of the present invention may be applied to a multiprocessor data processing system.

[0021] For example, data processing system 200, if optionally configured as a network computer, may not include SCSI host bus adapter 212, hard disk drive 226, tape drive 228, and CD-ROM 230, as noted by dotted line 232 in FIG. 2 denoting optional inclusion. In that case, the computer, to be properly called a client computer, must include some type of network communication interface, such as LAN adapter 210, modem 222, or the like. As another example, data processing system 200 may be a stand-alone system configured to be bootable without relying on some type of network communication interface, whether or not data processing system 200 comprises some type of network communication interface. As a further example, data processing system 200 may be a Personal Digital Assistant (PDA) device which is configured with ROM and/or flash ROM in order to provide non-volatile memory for storing operating system files and/or user-generated data.

[0022] The depicted example in FIG. 2 and above-described examples are not meant to imply architectural limitations.

[0023] The present invention provides a method, apparatus, and instructions for processing recursive links. In particular, the present invention is directed towards the processing of recursive hard links or other links that cannot be or are not easily unlinked. Beginning at the highest level directory above the recursive link, in the sample case /usr/, a list of all subdirectories directly beneath it is built. Examples would be, /usr/a, /usr/another_dir, /usr/yet_another₁₃dir, or /usr/guess_what_another_dir. Then from the resultant list, the directory leading to the bad link in the sample case, directory “a” is removed. Next, formatting is performed such that this list contains only crisply stated subdirectory data with no extraneous characters. The next step is to run a “find” command with the “print” option against the resultant list with the bad link removed to begin building a “master list” of all files beneath the “good” subdirectories. The master list may appear as, /usr/another_dir, /usr/another_dir/file_a, /usr/another_dir/file_b, /usr/another_dir/subdir, /usr/another_dir/subdir/file_c, etc.

[0024] The names of all the files explicitly at this directory level are captured and placed into a temporary file, such as, for example, /usr/file_—1, /usr/file_—2, etc. In this example, file_—1 and file_—2 are files at the directory level. Thereafter, formatting is performed on the temporary files to eliminate extraneous characters. Next, the resultant filename list is written into the master list. Then, the process progresses one directory level down toward the bad link. In the depicted example, this progression is into directory “a”. A determination is made as to whether the process has progressed all the way down to the bad link. If not, the next lower subdirectory in the path is processed as described above for directory “a”. In particular, the steps described above would be performed with respect to directory “b”.

[0025] After stepping through the above process all the way down to the origin of the recursive link, a back up of the filesystem may be made, minus the bad link. This back up is made using the information placed in the master list. A new filesystem can then be created and data restored from the back up. Then, the contents of the new filesystem may be verified. After inspection of filesystem equivalency minus the bad link, the mount points of the two filesystems may be switched, such that the changes will be transparent to applications and users.

[0026] With reference now to FIG. 3, a diagram illustrating a directory structure is depicted in accordance with a preferred embodiment of the present invention. Directory structure 300 is an example of a filesystem with U 302 being the root directory. In this example, directory dog 304 is the directory having a hard cursive link 306 back to directory apple 308. The process of the present invention would identify the path to the bad directory, 304. In the depicted example, this path would be U 302, user 310, apple 308, banana 312, coke 314, and dog 304. All of the directories would be placed in a master file list except for any directories below dog 304, which contains a recursive link back to apple 308. The search process involves starting at the top of directory structure 300 and capturing file names and subdirectories down the top branches of directory structure 300.

[0027] The process then moves further down the identified path and record names and subdirectories of all files for intermediate branches. The search for files and directories, however, would exclude a subdirectory in the identified path. When a search is conducted down a “good” subdirectory, i.e., one which is not on the bad path, the search is made through the depths of the good subdirectory. It does this before any further steps down the bad path are taken. Once all of the data has been recorded in the master file list, a back up of the identified files and directories may be made, excluding the bad link.

[0028] With reference next to FIG. 4, a flowchart of a process for processing a recursive link is depicted in accordance with a preferred embodiment of the present invention. The process begins by receiving user input identifying the bad path containing the recursive link (step 400). In the depicted example, is in a standard “/dir1/dir2/dir3 . . . ” format. The path is identified based on user input. Of course, this input may be received from a program analysis of the filesystem. Thereafter, the syntax is parsed to ensure correct usage(step 402). A determination is then made as to whether the user input was correct (step 404). If the user input is incorrect, an error message is returned (step 406) with the process terminating thereafter. Otherwise, the process stores the input in a file for further manipulation (step 408). Then, the input in the file is reformatted to replace each “/” with “ ”(step 410).

[0029] A determination is then made as to whether a prior master file list is present (step 412). If a prior master file list is present, this file list is moved to a different extension (step 414), such as *.old, in case the file is to be examined at a later time. Thereafter, the relative path is ascertained (step 416). In ascertaining the relative path, the current directory being processed is identified. For example, if the current directory is “a” in the path “a/b/c/d”, “a” is the relative path. The process proceeds directly to step 416 from step 412 if a prior master file list is absent.

[0030] Next, the name of the next directory down the bad path is retrieved as the current directory (step 418). For example, in the path “a/b/c/d” if “a” was the relative path, “b” is the name of the directory that will be the current directory. A list of directories beneath the current directory is identified (step 420). The directory beneath the current directory in the bad path is removed from the list (step 422). For example, if “b” is the current directory, then “c” would be removed from the directory list.

[0031] Thereafter, all paths and file names are identified from the list of directories (step 424). This may be performed by using a search command on the list of directories. The result is stored in a master file list (step 426). All files located in the current directory are identified (step 428). This result is stored in the master file list (step 430). A determination is then made as to whether the recursive directory has been processed (step 432). Step 432 is used to stop processing just above the recursive directory so that the bad link is avoided. Files in the recursive directory, however, are processed. The recursive directory is the directory containing the recursive link. If the recursive directory has not been processed, the process returns to step 416 as described above. Otherwise, the process terminates. This master file will describe the entire directory structure, minus the bad links.

[0032] Turning next to FIG. 5, a flowchart of a process for creating a new file system without the recursive link is depicted in accordance with a preferred embodiment of the present invention. The process begins by creating a back up using the master file list (step 500). Thereafter, a new file system is created (step 502). The data from the backup is restored to the new file system (step 504). The restored data recreates the directory structure without the bad links. The restored data is verified (step 506) with the process terminating thereafter.

[0033] The processes described in FIGS. 4 and 5 are with respect to UNIX. Of course, these processes may be applied to other types of operating systems, such as, for example, OS/2 from International Business Machines Corporation and Windows NT from Microsoft Corporation.

[0034] With reference now to FIGS. 6A-6F, diagrams illustrating a script used to process recursive links are depicted in accordance with a preferred embodiment of the present invention. The script illustrated in these diagrams is designed for UNIX, but the processes performed by the script may be applied to other operating systems to handle recursive links.

[0035] The script illustrated in these figures begins by providing file and variable declarations in section 600 in FIG. 6B. In FIG. 6B, the syntax and usage of the user input are checked in section 602. In FIG. 6C, section 604, the instructions will echo or write the entire subdirectory structure into a temporary file. Reformatting of the file occurs in section 606 of the script. This section replaces “/” characters with spaces. In section 608, a prior master file list, if present is moved.

[0036] In section 610, the script will set the first level directory. Section 612 is the beginning of a loop for processing directories in the file system. In FIG. 6D, a complete path name is built for the current directory in section 614 of the script. In FIG. 6E, the name of the next directory in the path entered by the user is pulled out in section 616 of the script. Directory information for all subdirectories beneath the current directory are gathered and stored into a directory list by the instructions in section 618 of the script. Any bad directories are removed from the directory list by the instructions in section 620. In section 622 of the script, the master directory list is generated from the directory list. In FIG. 6F, file information for files in the current directory are gathered by the script instructions in section 624. The index is then incremented by the script in section 626 to process the next level in the filesystem. A message is sent to the user by the instructions in section 628 when the process has completed.

[0037] It is important to note that while the present invention has been described in the context of a fully functioning data processing system, those of ordinary skill in the art will appreciate that the processes of the present invention are capable of being distributed in the form of a computer readable medium of instructions and a variety of forms and that the present invention applies equally regardless of the particular type of signal bearing media actually used to carry out the distribution. Examples of computer readable media include recordable-type media such a floppy disc, a hard disk drive, a RAM, and CD-ROMs and transmission-type media such as digital and analog communications links.

[0038] The description of the present invention has been presented for purposes of illustration and description, but is not intended to be exhaustive or limited to the invention in the form disclosed. For example, although the depicted examples are illustrated in a UNIX operating system, the processes of the present invention may be applied to other operating systems to handle recursive links, such as NT Windows. Many modifications and variations will be apparent to those of ordinary skill in the art. The embodiment was chosen and described in order to best explain the principles of the invention, the practical application, and to enable others of ordinary skill in the art to understand the invention for various embodiments with various modifications as are suited to the particular use contemplated.