Relative positioning and access of memory objects

A garbage collector including a bit mapper operative to designate a plurality of regions within a memory, associate any of a plurality of objects with any of the regions if the start address of the object to be associated lies within the region, and record the relative location of a group of objects within any of the regions, a mover operative to relocate any of the groups of objects found within a source region from among the regions to begin at a destination address, and a fixer operative to record the destination address at an index corresponding to the source region.

FIELD OF THE INVENTION

The present invention relates to computer memory garbage collection in general, and more particularly to object relocation and reference fixup.

BACKGROUND OF THE INVENTION

Computer operating environments, such as the Java Virtual Machine (JVM), typically provide a mechanism for applications to store “objects” of data. Often, the operating environment dynamically allocates a section of memory for utilization by the application into which the application places its objects. In the course of its execution, an application may no longer require an object, allowing the object's location in memory to be reclaimed for storing other objects. This process of reclamation is popularly known as garbage collection (GC).

Garbage collectors from the mark-sweep family suffer from memory fragmentation, which refers to the creation of relatively small holes of unused space between objects. To reduce fragmentation the GC may compact memory by reducing the space between objects and thus create chunks of larger free space, making allocation more efficient, and practically reducing the memory footprint of the application. During compaction, “fixup” of object memory addresses is typically performed to keep track of each object's new location for future reference.

Unfortunately, compaction algorithms tend to require large amounts of auxiliary data structures, such as forwarding references or break tables. Moreover when searching for a previously stored objects, forwarding references may require additional auxiliary memory accesses.

SUMMARY OF THE INVENTION

The present invention discloses a system and method for relative positioning of memory objects.

In one aspect of the present invention a garbage collector is provided including a bit mapper operative to designate a plurality of regions within a memory, associate any of a plurality of objects with any of the regions if the start address of the object to be associated lies within the region, and record the relative location of a group of objects within any of the regions, a mover operative to relocate any of the groups of objects found within a source region from among the regions to begin at a destination address, and a fixer operative to record the destination address at an index corresponding to the source region.

In another aspect of the present invention the bit mapper is operative to construct an old relative location bitmap including a series of bits, with each bit onpositionally corresponding to a block bnin the memory.

In another aspect of the present invention the bit mapper is operative to set any of the bits to indicate that the corresponding block includes the start address of any of the objects that lay within the source region.

In another aspect of the present invention the mover is operative to compact the group of objects.

In another aspect of the present invention the mover is operative to preserve the relative order and position of the objects within the group of objects to one another.

In another aspect of the present invention the mover is operative to relocate the group of objects such that no other object from outside the group of objects is inserted between objects within the relocated group.

In another aspect of the present invention the bit mapper is operative to construct a new relative location bitmap including a series of bits, with each bit onpositionally corresponding to a block bnin the memory.

In another aspect of the present invention the bit mapper is operative to set any of the bits to indicate that the corresponding block includes the start address of any of the relocated objects.

In another aspect of the present invention the fixer further includes a calculator operative to determine the new start address of a desired object among any of the relocated objects.

In another aspect of the present invention the fixer is operative to reassign a pointer to any of the objects in the source region to the address of the object after the object is relocated.

In another aspect of the present invention the calculator is operative to receive the old start address of the desired object, determine the source region within which the desired object originated, determine the relative position of the desired object within the source region, determine the new start address of the first object in the relocated group of objects, determine the block in which the start address of the desired object lies as being at the same relative position from the destination address as in the source region, and calculate the current address of the desired object by adding multiples of the block size to the new start address until the block in which the start address of the desired object lies is reached.

In another aspect of the present invention a garbage collector is provided including a bit mapper operative to designate a plurality of regions within a memory, and associate any of a plurality of objects with any of the regions if the start address of the object to be associated lies within the region, a mover operative to relocate each object in a group of the objects found within a source region from among the regions at an offset within the memory from its current location in the source region such that the distances between the objects within the group are preserved, and a fixer operative to record the offset at an index corresponding to the source region.

In another aspect of the present invention the mover is operative to preserve the relative order and position of the objects within the group of objects to one another.

In another aspect of the present invention the mover is operative to relocate the group of objects such that no other object from outside the group of objects are inserted between objects within the relocated group.

In another aspect of the present invention the fixer further includes a calculator operative to determine the new start address of a desired object among any of the moved objects.

In another aspect of the present invention the fixer is operative to reassign a pointer to any of the objects in the source region to the address of the object at the offset.

In another aspect of the present invention the calculator is operative to receive the old start address of the desired object, determine the source region within which the desired object originated, determine the offset corresponding to the source region, and calculate the current address of the desired object by adding the offset to the old start address.

In another aspect of the present invention a method is provided for relative positioning of memory objects, the method including designating a plurality of regions within a memory, associating any of a plurality of objects with any of the regions if the start address of the object to be associated lies within the region, recording the relative location of a group of objects within any of the regions, relocating any of the groups of objects found within a source region from among the regions to begin at a destination address, and storing the destination address at an index corresponding to the source region.

In another aspect of the present invention the recording step includes constructing an old relative location bitmap including a series of bits, with each bit onpositionally corresponding to a block bnin the memory.

In another aspect of the present invention the recording step includes setting any of the bits to indicate that the corresponding block includes the start address of any of the objects that lay within the source region.

In another aspect of the present invention the relocating step includes compact the group of objects.

In another aspect of the present invention the relocating step includes preserving the relative order and position of the objects within the group of objects to one another.

In another aspect of the present invention the relocating step includes relocating the group of objects such that no other object from outside the group of objects is inserted between objects within the relocated group.

In another aspect of the present invention the method further includes constructing a new relative location bitmap including a series of bits, with each bit onpositionally corresponding to a block bnin the memory.

In another aspect of the present invention the method further includes setting any of the bits to indicate that the corresponding block includes the start address of any of the relocated objects.

In another aspect of the present invention the method further includes determining the new start address of a desired object among any of the relocated objects.

In another aspect of the present invention the method further includes reassigning a pointer to any of the objects in the source region to the address of the object after the object is relocated.

In another aspect of the present invention the determining step includes receiving the old start address of the desired object, determining the source region within which the desired object originated, determining the relative position of the desired object within the source region, determining the new start address of the first object in the relocated group of objects, determining the block in which the start address of the desired object lies as being at the same relative position from the destination address as in the source region, and calculating the current address of the desired object by adding multiples of the block size to the new start address until the block in which the start address of the desired object lies is reached.

In another aspect of the present invention a method is provided for relative positioning of memory objects, the method including designating a plurality of regions within a memory, and associating any of a plurality of objects with any of the regions if the start address of the object to be associated lies within the region, relocating each object in a group of the objects found within a source region from among the regions at an offset within the memory from its current location in the source region such that the distances between the objects within the group are preserved, and storing the offset at an index corresponding to the source region.

In another aspect of the present invention the relocating step includes preserving the relative order and position of the objects within the group of objects to one another.

In another aspect of the present invention the relocating step includes relocating the group of objects such that no other object from outside the group of objects are inserted between objects within the relocated group.

In another aspect of the present invention the method further includes determining the new start address of a desired object among any of the moved objects.

In another aspect of the present invention the method further includes reassigning a pointer to any of the objects in the source region to the address of the object at the offset.

In another aspect of the present invention the determining step includes receiving the old start address of the desired object, determining the source region within which the desired object originated, determining the offset corresponding to the source region, and calculating the current address of the desired object by adding the offset to the old start address.

In another aspect of the present invention a computer program is provided embodied on a computer-readable medium, the computer program including a first code segment operative to designate a plurality of regions within a memory, a second code segment operative to associate any of a plurality of objects with any of the regions if the start address of the object to be associated lies within the region, a third code segment operative to record the relative location of a group of objects within any of the regions, a fourth code segment operative to relocate any of the groups of objects found within a source region from among the regions to begin at a destination address, and a fifth code segment operative to store the destination address at an index corresponding to the source region.

In another aspect of the present invention a computer program is provided embodied on a computer-readable medium, the computer program including a first code segment operative to designate a plurality of regions within a memory, and a second code segment operative to associate any of a plurality of objects with any of the regions if the start address of the object to be associated lies within the region, a third code segment operative to relocate each object in a group of the objects found within a source region from among the regions at an offset within the memory from its current location in the source region such that the distances between the objects within the group are preserved, and a fourth code segment operative to storing the offset at an index corresponding to the source region.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

Reference is now made toFIG. 1A, which is a simplified block diagram of a computer system, and additionally toFIG. 1B, which is a simplified pictorial representation of memory storage, both useful in understanding the present invention. A typical Computer System100includes a Processor110and a Memory120, such as Heap Memory. Processor110typically processes data and stores data objects in Memory120for later retrieval.

Memory120typically includes one or more contiguous Blocks130of memory, each block denoted as Bn. Each Block130is typically of a fixed size of n bytes, and may be used to store an Object140or part thereof. Preferably, the start of each Object140is aligned with the start of a Block130.

Computer System100may utilize an Available Block Bitmap150to help identify blocks in Memory120in which objects are stored. Available Block Bitmap150is typically composed of a memory bit vector where the first bit M1in Available Block Bitmap150positionally corresponds to the first Block B1in Memory120, the second bit M2in Available Block Bitmap150positionally corresponds to the second Block B2in Memory120, and so on (the scale of Available Block Bitmap150and of Memory120are not depicted equally inFIG. 1B). Each bit Miis typically set, such as to 1, if an Object140or a part thereof occupies its corresponding block Bi, or “unset,” such as to 0, if the corresponding block Biis not used for storing an object. In this manner Available Block Bitmap150provides a means for determining the availability of blocks in Memory120for storing new objects.

Reference is now made toFIG. 2A, which is a simplified block diagram of a memory compaction and fixup system,FIG. 2B, which is a simplified pictorial representation of an exemplary memory storage configuration prior to compaction and fixup,FIG. 2C, which is a simplified pictorial representation of an exemplary memory storage configuration after compaction and fixup, and toFIG. 2D, which is a simplified flow chart illustration of a method for compaction and fixup, constructed and operative in accordance with preferred embodiments of the present invention.

Computer System100may employ an operating environment, such as a Java Virtual Machine (JVM), to provide an execution environment for an Application200and a Garbage Collector210to compact Memory120. In the course of execution, Application200may store one or more Objects140in Memory120. For Example,FIG. 2bdepicts a series of Objects140, labeled Object1through Object5, stored in Memory120.

Garbage Collector210preferably includes a Bit Mapper220, a Mover230and a Fixer240. Bit Mapper220typically designates one or more Regions250within Memory120such that each Region250is of a predefined size, and preferably of approximately equal size. Bit Mapper220may then associate one or more Objects140with a particular Region250if the start address of the Object140lies within the Region250.

InFIG. 2b, Memory120is shown as having three regions designated Region1, Region2and Region3. Region1defines an unused section of Memory120that includes Blocks B1through B5. Region2defines a section of Memory120that includes Blocks B6through B10and includes the start addresses of Object1and Object2. Region3defines a section of Memory120that includes Blocks B11through B15and includes the start addresses of Object3, Object4and Object5.

During compaction, Mover230typically chooses a source region in Memory120, such as Region3, and a destination address in Memory120, such as an address in Region1. The destination address may lie in the same region as the source region or in a different region, and need not coincide with a region boundary, but should preferably coincide with a block boundary. Bit Mapper220typically constructs an Old Relative Location Bitmap260similar to Available Block Bitmap150, with each bit Onpositionally corresponding to a block Bnin Memory120. However, unlike Available Block Bitmap150, each of the set bits in Old Relative Location Bitmap260indicates that a corresponding block in Memory120includes the start address of an Object140. Bit Mapper220set the bits in Old Relative Location Bitmap260that are associated with the Objects140that lay within the source region chosen by Mover230. Thus, inFIG. 2B, set bits O11, O13and O15correspond to the start address of Object3, Object4and Object5respectively.

Mover230typically moves and compacts Objects140located in the source region to the destination address. Preferably, one or more Objects140in the source region are moved as a group to the destination address, including all objects between the first and last objects in the group as it appears in the source region, where the relative order and position of the Objects140to one another are preserved, although the distances between the Objects140may be reduced or eliminated, and where no other objects from outside the group are inserted between objects within the group. Thus, inFIG. 2C, the relative position of Object3, Object4and Object5within Memory120is preserved after they have been moved from Region3and compacted into Region1.

Fixer240then places the new start address of the first Object140in the group of objects, being the destination address, into an Offset Vector270at an index corresponding to the source Region prior to the group of objects being moved. Thus, inFIG. 2C, the index of Offset Vector270corresponding to source Region3is used to store the start address B1of Object3in Region1.

Bit Mapper220typically constructs a New Relative Location Bitmap280that is similar to Old Relative Location Bitmap260, with each bit Nnpositionally corresponding to a block Bnin Memory120. New Relative Location Bitmap280preferably indicates blocks in Memory120in which the start address of moved Objects140are found. Thus, inFIG. 2C, N1, N3and N4in New Relative Location Bitmap280are set, such as to 1, to correspond to the blocks B1, B3and B4that include the start address of Object3, Object4and Object5respectively.

Reference is now made toFIG. 3A, which is a simplified block diagram of a compacted object location system,FIG. 3B, which is a pictorial representation of an exemplary compact memory storage configuration, and toFIG. 3C, which is a simplified flow chart illustration of a method for compacted object location, constructed and operative in accordance with preferred embodiments of the present invention.

In addition to the elements described hereinabove with reference toFIG. 2A, Garbage Collector210may employ Fixer240to reassign pointers to the objects within Memory120during compaction by utilizing a Calculator300to determine the new start address of an object as follows.

Calculator300receives the old start address of the desired Object140, and queries Bit Mapper220to determine the old Region250within which the desired Object140resided. Bit Mapper220consults Old Relative Location Bitmap260to determine the relative position of the desired Object140within Region250. Calculator300queries Fixer240, which in turn consults Offset Vector270for the new start address of the first Object140in the group of objects that were relocated from the old Region250to the destination address within Memory120.

Given that the relative position of the desired Object140among the relocated group of objects is the same in both its old and new locations as the n-th object in the group of objects, Calculator300queries Bit Mapper220which consults New Relative Location Bitmap280and identifies the n-th set bit from the block corresponding to the new starting address of the first object in the relocated group of objects as corresponding to the block in which the start address of the desired Object140lies. The current address of the desired Object140may then be calculated by adding multiples of the block size to the new start address of the first Object140in the relocated group of objects until the block corresponding to the n-th set bit is reached.

Thus, inFIG. 3B, to fix the pointers to Object5in Memory120, the old start address of Object5, B15, is first determined. The old Region250within which Object5resided, Region3, is also determined, and Old Relative Location Bitmap260is consulted to determine the relative position of Object5within Region3, which inFIG. 2Bis shown as the third Object140within Region3.

Offset Vector270is then consulted to determine the new start address of the first object in the relocated group of objects that were previously in Region3within Memory120, now being B1.

New Relative Location Bitmap280is then consulted to determine the address of the block in Region, corresponding to the third Object140in the region, being block B4. Three block lengths are then added to address B1, yielding the start address of block B4, and thus the start address of Object5, which may be employed to adjust the pointers to the Object140.

One method for determining the relative position of a desired Object140is to traverse Old Relative Location Bitmap260, counting the number of set bits starting from the first Object140in the Region250, i.e. Object3in Region3.

Yet another method for determining the relative location of a desired Object140is to directly traverse the Objects140in Memory120. While this methodology requires Memory120to store the size of each Object140, there is no need for New Relative Location Bitmap280. Bit Mapper220may traverse Memory120, counting the memory Objects140as they are encountered, starting at the new start address of the first object in the relocated group of objects.

Reference is now made toFIG. 4A, which is a simplified pictorial representation of an exemplary memory storage configuration prior to relocation and fixup, toFIG. 4B, which is a simplified pictorial representation of an exemplary memory storage configuration after relocation and fixup, and toFIG. 4C, which is a simplified flow chart illustration of a method for relocation and fixup, constructed and operative in accordance with preferred embodiments of the present invention.FIGS. 4A,4B, and4C are similar toFIGS. 2A,2B, and2C respectively, with the notable exception that during the relocation phase each object in a group of Objects140located in the source region is relocated at an offset from its current location in the source region preferably such that the distances between the Objects within the group are preserved. An Address Offset Vector400corresponding to the source region is used to store the offset of the new location of each object relative to its previous location. For example, inFIG. 4B, Object3, Object4and Object5are relocated from Region3to a destination address at an offset of minus eleven blocks. The address offset, minus eleven blocks of memory, is stored in Address Offset Vector400.

During the fixup stage, the address of a desired Object140is calculated by adding the Address Offset Vector400corresponding to the desired object's previous region to the object's previous address. In the example presented hereinabove Object5is located eleven blocks from its original location, thus pointers to Object5, which previously pointed to B15are adjusted to point to B4.

It is appreciated that one or more of the steps of any of the methods described herein may be omitted or carried out in a different order than that shown, without departing from the true spirit and scope of the invention.

While the methods and apparatus disclosed herein may or may not have been described with reference to specific computer hardware or software, it is appreciated that the methods and apparatus described herein may be readily implemented in computer hardware using conventional techniques.