Electrical computers and digital processing systems: memory – Address formation – Slip control – misaligning – boundary alignment
Reexamination Certificate
2001-06-28
2004-05-04
Portka, Gary (Department: 2188)
Electrical computers and digital processing systems: memory
Address formation
Slip control, misaligning, boundary alignment
C711S220000
Reexamination Certificate
active
06732248
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
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.
2. Description of the Related Art
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.
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.
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.
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.
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
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.
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.
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.
REFERENCES:
patent: 5727090 (1998-03-01), Yellin
patent: 5890169 (1999-03-01), Wong et al.
patent: 5895503 (1999-04-01), Belgard
patent: 5928352 (1999-07-01), Gochman et al.
patent: 5940868 (1999-08-01), Wagner
patent: 5946716 (1999-08-01), Karp et al.
patent: 5960466 (1999-09-01), Belgard
patent: 5963984 (1999-10-01), Garibay, Jr. et al.
patent: 5978795 (1999-11-01), Poutanen et al.
patent: 6006312 (1999-12-01), Kohn et al.
patent: 6075545 (2000-06-01), De Bonet et al.
patent: 6081301 (2000-06-01), Limberg
patent: 6088747 (2000-07-01), Cotugno et al.
patent: 6374250 (2002-04-01), Ajtai et al.
Chang Joon
Shi Amy Yi-mei
International Business Machines - Corporation
Leeuwen Joseph T. Van
Portka Gary
Roberts Diana L.
Schmok Scott A.
LandOfFree
System and method for ghost offset utilization in sequential... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for ghost offset utilization in sequential..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for ghost offset utilization in sequential... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3251708