Abstract:
A system and method for releasing storage space at the beginning of a byte stream while maintaining sequential byte stream semantics is provided. A ghost offset is initialized when a file is instantiated or opened. When information is deleted at the beginning of the sequential byte stream, the ghost offset is incremented in the amount of the number of bytes being deleted. The ghost offset continues to increment while the file is opened and information is being deleted at the beginning of the data stream. The virtual offset is the ghost offset added to the real offset of a particular entry in the data stream which maintains sequential byte stream semantics. When the file is closed, storage space is released in the amount of the ghost offset. Applications are provided with virtual offsets corresponding to data locations which are converted to real offsets for accessing data in the data stream.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Technical Field  
           [0002]    The present invention relates in general to a method and system for using a ghost offset to track the truncation of information. Still more particularly, the present invention relates to a method and system for releasing storage space while keeping sequential byte stream semantics.  
           [0003]    2. Description of the Related Art  
           [0004]    Operating systems, such as the UNIX operating system, use a file system for managing files. UNIX uses a hierarchical directory structure for organizing and maintaining files. There are three types of files in the UNIX file system: (1) ordinary files, which may be executable programs, text, or other types of data used as input or produced as output from some operation; (2) directory files, which contain lists of files in directories outlined above; and (3) special files, which provide a standard method of accessing input/output devices. The UNIX operating system organizes files into directories which are stored in a hierarchical tree-type configuration. At the top of the tree is the root directory which is represented by a slash (/} character. The root directory contains one or more directories. These directories, in turn, may contain further directories containing user files and other system files.  
           [0005]    File system objects are viewed as sequential byte stream entities. A sequential byte stream is a series of bytes positioned next to each other. Data files consist of sequential byte streams. Directories, however, consist of a set of entries. Directory operations by applications are typically to access each entry randomly, or to access the entire directory when the application chooses to list or delete the directory. An example of an application is a word processing program or file manager program. In either case, the directory is implemented as a sequential byte stream. The position of an entry is reported to the application by an offset which specifies the distance from the start of the directory to the entry. For example, if the start of a sub-directory is twenty bytes from beginning of the start of the directory being viewed, the offset reported to the application is twenty.  
           [0006]    A challenge found with existing art is that it prevents the release of storage space after a deletion from the front of the file object. For a directory, entries at the front of the file object can be deleted. However, the standard sequential byte stream implementation still prevents releasing data space associated with deleted entries in that segment. If the data space for the deleted entries is released, the offset of the remaining entries decreases by the size of the preceding deleted entries and thus invalidates the offsets of the remaining entries reported to the application.  
           [0007]    Retaining data space of deleted entries of a directory results in less efficient storage utilization. More serious challenges occur if the underlying directory implementation is based on an efficient balanced tree data structure rather than a sequential data structure. In a balanced tree data structure, deleted entries must be removed to avoid complications of tree searches complications with maintaining the balanced tree. Balanced tree data structures are used as a method for quickly searching and retrieving information.  
           [0008]    What is needed, therefore, is a way to release storage space at the beginning of a sequential byte stream after a deletion and still maintain sequential byte stream semantics.  
         SUMMARY  
         [0009]    It has been discovered that providing a new mechanism called a ghost offset to maintain the semantics of the original “offset” of the sequential byte stream allows the release the data space associated with the deleted entries when truncation at or from the front of the directory file object. The ghost offset is used for balanced tree as well as sequential byte stream implementations. Sequential file abstraction for the application viewpoint is maintained while allowing efficient underlying implementation.  
           [0010]    When a file object is instantiated or opened in memory, a ghost offset, G, is associated with the file object. The ghost offset is initialized to zero, and tracks the length of a truncated segment from the front of the file object since the instantiation. Whenever the leftmost entries of the file object are deleted from the front, the data space of the deleted entries is removed from the file object and the ghost offset G is incremented by the size of the entry. The underlying implementation assigns a real offset, R, to an entry by computing its current position from the start of the actual remaining file object. For example, if the position of an entry is twenty bytes away from the beginning of the data stream, the real offset is twenty. If the first ten bytes of the data stream are released, the real offset is now ten for the same entry. The offset communicated between the application and the underlying implementation is the virtual offset, V, which is the summation of the ghost offset, G, and the real offset, R. When the application specifies an offset, V, to be instantiated or opened, the real offset is calculated by subtracting the ghost offset from the received virtual offset. When the file is closed, storage space is released at the beginning of the byte stream in the amount of G, and the ghost offset is discarded.  
           [0011]    The foregoing is a summary and thus contains, by necessity, simplifications, generalizations, and omissions of detail; consequently, those skilled in the art will appreciate that the summary is illustrative only and is not intended to be in any way limiting. Other aspects, inventive features, and advantages of the present invention, as defined solely by the claims, will become apparent in the non-limiting detailed description set forth below.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0012]    The present invention may be better understood, and its numerous objects, features, and advantages made apparent to those skilled in the art by referencing the accompanying drawings. The use of the same reference symbols in different drawings indicates similar or identical items.  
         [0013]    [0013]FIG. 1 is a high level diagram showing a process truncating a directory;  
         [0014]    [0014]FIG. 2A is a diagram showing a ghost offset incrementing as pages are truncated;  
         [0015]    [0015]FIG. 2B is a diagram showing how the ghost offset manages truncations that are not in full pages;  
         [0016]    [0016]FIG. 3 is a flowchart showing the truncation process and the release of storage;  
         [0017]    [0017]FIG. 4 is a flowchart showing the front truncation process;  
         [0018]    [0018]FIG. 5 is a flowchart showing the truncation process at an area not in the front of a data stream; and  
         [0019]    [0019]FIG. 6 is a block diagram of an information handling system capable of performing the present invention.  
     
    
     DETAILED DESCRIPTION  
       [0020]    The following is intended to provide a detailed description of an example of the invention and should not be taken to be limiting of the invention itself. Rather, any number of variations may fall within the scope of the invention which is defined in the claims following the description.  
         [0021]    [0021]FIG. 1 is a high level diagram showing an application truncating a directory. Application  100  sends open directory  105  request to file system  110 . The requested directory resides in non-volatile storage device  160 . An example of a non-volatile storage device is a disk drive or other computer operable media that retains storage values when power is removed from the device. When file system  110  receives the request to open the directory, calculate process  120  reads real offset  150  that corresponds with the requested directory. At the start of a file being opened, ghost offset is initialized to zero. Calculate  120  computes virtual offset  140  by adding real offset  150  to ghost offset  130 . Since the ghost offset is zero at the beginning of instantiation, virtual offset  140  equals real offset  150 . Virtual offset  140  is the virtual location of the beginning of the requested sequential data stream. The virtual offset is provided (step  170 ) to application  100  so the application can use a pointer to the location of the requested file. Application  100  sends read request V′ ( 145 ) to file system  110 . In one embodiment, the application reads file information prior to truncation. In other embodiments, the application simply truncates information without reading the file information. V′ can be the same virtual offset (V) provided by the file system, or it can be a different virtual offset corresponding to information that is not at the beginning of sequential data stream  155 . File system  110  calculates the real offset of the requested read by subtracting the ghost offset from the V′ offset.  
         [0022]    Application  100  can send truncate request  180  to file system  110  in order to truncate data beginning at V′ from sequential data stream  155 . File system  110  calculates the real offset by subtracting the ghost offset from the V′ offset, and truncates data stream  155  accordingly (step  185 ). In this example, V′ is the first block of data (i.e., a directory) in sequential data stream  155 . In other embodiments, V′ could be in the middle or at the end of the sequential data stream.  
         [0023]    [0023]FIG. 2A is a diagram showing a ghost offset incrementing as pages are truncated. Sequential data stream  200  includes n pages. P 0  ( 202 ) is the first page, P 1  ( 204 ) is the second page, P 2  ( 206 ) is the third page, and Pn ( 208 ) is the last page. The beginning of each page has a real offset, R, and a virtual offset, V. Real offsets are the true location of the beginning of corresponding pages. R 1  ( 212 ) is the real offset location of the beginning of page 1. In the top example, R 1  is offset by 10 bytes. R 2  ( 214 ) is the real offset location of the beginning of page. In the top example, R 2  is offset by 20. R 3  ( 216 ) is the real offset location of the beginning of page 3. In the top example, R 3  is offset by  30 . Virtual offsets are provided to applications, and are consistent while data is truncated at the beginning of a data stream. Virtual offsets are calculated by adding the ghost offset to the real offset. In the top example, the ghost offset is initialized to zero ( 218 ), as is the case when a file is instantiated. Therefore, V 1  ( 220 ) is the same as R 1  ( 212 ) which is 10. V 2  ( 222 ) is the same as R 2  ( 214 ) which is 20. V 3  ( 224 ) is the same as R 3  ( 216 ) which is 30.  
         [0024]    The middle example in FIG. 2A shows P 0  being truncated ( 230 ). With P 0  being truncated, the real offsets shift by the amount of P 0 . Therefore, R 1  ( 232 ) becomes 0, R 2  ( 234 ) becomes 10, and R 3  ( 236 ) becomes 20. The ghost offset increments by the amount of data deleted at the beginning of the data stream. Therefore, the ghost offset is now 10 ( 238 ). Virtual offsets are unaffected by deleting P 0  because virtual offsets are the summation of the real offset and the ghost offset. Therefore, V 1  ( 240 ) is still 10, V 2  ( 242 ) is still 20, and V 3  ( 244 ) is still 30.  
         [0025]    The bottom example of FIG. 2A shows P 1  being truncated ( 250 ). With P 1  truncated, the real offsets shift by the amount of P 1 . Therefore, R 1  ( 252 ) is not existent, R 2  ( 254 ) becomes 0, and R 3  ( 256 ) becomes 10. The ghost offset increments by the amount of data deleted for P 1 . Therefore, the ghost offset increments to 20 ( 258 ). Virtual offset locations are unaffected by deleting P 1  because virtual offsets are the summation of the real offset and the ghost offset. However, V 1  ( 260 ) is no longer existent due to P 1  being removed. V 2  ( 262 ) is still 20, and V 3  ( 264 ) is still 30.  
         [0026]    [0026]FIG. 2B is a diagram showing the ghost offset managing truncations that are not in full pages. In the example to the left in FIG. 2B, sequential data stream  268  includes multiple pages. Real offset  274  is at the 30 th  entry on the second page (2,30). Ghost offset  272  is initialized to zero, as is the case when a file is instantiated. Since Ghost offset  272  is zero, virtual offset  270  is the same value as its corresponding real offset  274 , which is (2,30). In the example to the right of FIG. 2B, sequential data stream  278  is truncated at the front in the amount of one page and twenty entries ( 286 ). Ghost offset  282  is incremented by the amount of data that is deleted and is now (1,20). Real offset  284  becomes (1,30)=V−G=(2, 30)−(1,20). When sequential data streams are segmented in pages, information is released on a page by page basis. Therefore, P 0  is released but the first twenty entries of P 1   288  are not released. Virtual offset  280  is calculated by adding the number of pages of ghost offset  282  to real offset  284 . Virtual offset  288  remains at (2,30) because it is real offset  284  plus one page from ghost offset  282 . V=G+R, when G and R do not refer to the same page, the index of G is ignored and only the page number of G is used for calculations.  
         [0027]    [0027]FIG. 3 is a flowchart showing the truncation process and the release of storage. Initialization commences at  300 , whereupon a request is received (step  302 ) from application  301 . Examples of requests received from applications are a request to read directory information, file information, or to truncate a directory. A snapshot of the requested data is retrieved (step  305 ), whereupon the file object is instantiated or opened (step  310 ). The system provides a virtual offset to application  301  corresponding to the location of the requested information (step  315 ). At this point in the process, the virtual offset is the same as the real offset. The ghost offset initializes to zero (step  320 ) and waits for a truncation request from application  301 . Once the truncation request is received (step  325 ), a determination is made as to whether the truncation request is at the front of the data stream or somewhere else in the data stream (decision  330 ). If the truncation request is not at the front of the data stream, decision  330  branches to “no” branch  333  whereupon non-front truncation is processed (pre-defined process block  335 , see FIG. 5 for further details). On the other hand, if the truncation request is at the front of the data stream, decision  330  branches to “yes” branch  338  whereupon front truncation is processed (pre-defined process block  340 , see FIG. 4 for further details).  
         [0028]    Following either truncation process ( 335  or  340 ), a determination is made as to whether another truncation request is received (decision  345 ). If another truncation request is received, decision  345  branches to “yes” branch  348  which loops back to handle the next truncation request. During “yes” branch  348 , the virtual offset is calculated by adding the ghost offset to the real offset (step  350 ). The new virtual offset is provided to the application (step  355 ) whereupon the system loops back to decision  330  and determines whether the truncation request is at the front of the data stream. This looping continues until there are no more truncations to perform, whereupon decision  345  branches to “no” branch  358 . The cumulated ghost value is retrieved (step  360 ). The front of the data stream storage space is released (i.e., deleted) by the amount of the ghost offset (step  365 ), whereupon processing ends at  370 .  
         [0029]    [0029]FIG. 4 is a flowchart showing the front truncation process. Front truncation processing commences at  400 , whereupon virtual offset  420  of the requested file to be truncated is retrieved (step  410 ) from application  405 . The ghost offset is retrieved from the system (step  430 ), whereupon the real offset location of the file is calculated (step  440 ). When a file is first opened or instantiated, the real and virtual offsets are the same and the ghost offset is initialized to zero.  
         [0030]    The real offset is calculated by subtracting the ghost offset from the virtual offset retrieved from the application. Data is retrieved at the real offset location in the amount of bytes (N) requested by the application (step  450 ). Requested data  465  is provided to application  405  (step  460 ), and the ghost offset is incremented by the amount of bytes N (step  470 ). In some embodiments, the application does not request to read the data, and only delete it. In these cases, steps  450  and  460  are omitted. The data is deleted (step  480 ), and processing returns at  490 . During subsequent invocations of front truncation process  400 , the ghost value (G) is retained to determine the virtual offsets and real offsets.  
         [0031]    [0031]FIG. 5 is a flowchart showing the truncation process of an area that is not in the front of a data stream. Non-front truncation processing commences at  500 , whereupon virtual offset  520  of the requested file to be truncated is retrieved (step  510 ) from application  505 . The ghost offset is retrieved from the system (step  530 ), whereupon the real offset location of the file is calculated (step  540 ). When a file is first opened or instantiated, the ghost offset is initialized to zero and the virtual offset is initialized to equal the real offset.  
         [0032]    The real offset is calculated by subtracting the ghost offset from the virtual offset retrieved from the application. Data is retrieved at the real offset location in the amount of bytes (N) requested by application  505  (step  550 ). The data is provided to application  505  (step  560 ). In one embodiment, the application does not request to read the data, and only delete it. In these cases, steps  550  and  560  are omitted. Ghost offsets prior to the truncation are not incremented. The data is deleted (step  570 ), and processing returns at  580 . In one embodiment, an array of ghost offsets can be used to track truncations at various parts of the data stream. For example, ghost offsets G 1 , G 2 , G 3 , etc. can be associated with real offsets R 1 , R 2 , R 3 , etc. When a directory is truncated in the middle of the data stream, directory  2  for example, ghost offsets at and after the truncation would be incremented (i.e., G 2 , G 3 , etc. are incremented, but G 1  is not).  
         [0033]    [0033]FIG. 6 illustrates information handling system  601  which is a simplified example of a computer system capable of performing the copy processing described herein. Computer system  601  includes processor  600  which is coupled to host bus  605 . A level two (L2) cache memory  610  is also coupled to the host bus  605 . Host-to-PCI bridge  615  is coupled to main memory  620 , includes cache memory and main memory control functions, and provides bus control to handle transfers among PCI bus  625 , processor  600 , L2 cache  610 , main memory  620 , and host bus  605 . PCI bus  625  provides an interface for a variety of devices including, for example, LAN card  630 . PCI-to-ISA bridge  635  provides bus control to handle transfers between PCI bus  625  and ISA bus  640 , universal serial bus (USB) functionality  645 , IDE device functionality  650 , power management functionality  655 , and can include other functional elements not shown, such as a real-time clock (RTC), DMA control, interrupt support, and system management bus support. Peripheral devices and input/output (I/O) devices can be attached to various interfaces  660  (e.g., parallel interface  662 , serial interface  664 , infrared (IR) interface  666 , keyboard interface  668 , mouse interface  670 , and fixed disk (FDD)  672 ) coupled to ISA bus  640 . Alternatively, many I/O devices can be accommodated by a super I/O controller (not shown) attached to ISA bus  640 .  
         [0034]    BIOS  680  is coupled to ISA bus  640 , and incorporates the necessary processor executable code for a variety of low-level system functions and system boot functions. BIOS  680  can be stored in any computer readable medium, including magnetic storage media, optical storage media, flash memory, random access memory, read only memory, and communications media conveying signals encoding the instructions (e.g., signals from a network). In order to attach computer system  601  another computer system to copy files over a network, LAN card  630  is coupled to PCI-to-ISA bridge  635 . Similarly, to connect computer system  601  to an ISP to connect to the Internet using a telephone line connection, modem  675  is connected to serial port  664  and PCI-to-ISA Bridge  635 .  
         [0035]    While the computer system described in FIG. 6 is capable of executing the copying processes described herein, this computer system is simply one example of a computer system. Those skilled in the art will appreciate that many other computer system designs are capable of performing the copying process described herein.  
         [0036]    One of the preferred implementations of the invention is a client application, namely, a set of instructions (program code) in a code module which may, for example, be resident in the random access memory of the computer. Until required by the computer, the set of instructions may be stored in another computer memory, for example, in a hard disk drive, or in a removable memory such as an optical disk (for eventual use in a CD ROM) or floppy disk (for eventual use in a floppy disk drive), or downloaded via the Internet or other computer network. Thus, the present invention may be implemented as a computer program product for use in a computer. In addition, although the various methods described are conveniently implemented in a general purpose computer selectively activated or reconfigured by software, one of ordinary skill in the art would also recognize that such methods may be carried out in hardware, in firmware, or in more specialized apparatus constructed to perform the required method steps.  
         [0037]    While particular embodiments of the present invention have been shown and described, it will be obvious to those skilled in the art that, based upon the teachings herein, changes and modifications may be made without departing from this invention and its broader aspects and, therefore, the appended claims are to encompass within their scope all such changes and modifications as are within the true spirit and scope of this invention. Furthermore, it is to be understood that the invention is solely defined by the appended claims. It will be understood by those with skill in the art that is a specific number of an introduced claim element is intended, such intent will be explicitly recited in the claim, and in the absence of such recitation no such limitation is present. For non-limiting example, as an aid to understanding, the following appended claims contain usage of the introductory phrases “at least one” and “one or more” to introduce claim elements. However, the use of such phrases should not be construed to imply that the introduction of a claim element by the indefinite articles “a” or “an” limits any particular claim containing such introduced claim element to inventions containing only one such element, even when the same claim includes the introductory phrases “one or more” or “at least one”, and indefinite articles such as “a” or “an”; the same holds true for the use in the claims of definite articles.