Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1999-07-30
2001-10-09
Nguyen, Hiep T. (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S156000, C711S170000
Reexamination Certificate
active
06301646
ABSTRACT:
BACKGROUND OF THE INVENTION
In recent years, the number of users on the Internet has increased exponentially. With this increase in popularity, there has also come an increased demand for languages that enhance the “on-line” experience. To this end, new object-oriented computer-programming languages such as Curl™ and JAVA™ have been developed, which ostensibly provide not only platform independence, but also increased functionality.
A common problem for these languages is the utilization of memory. These languages allocate memory from free storage and reclaim (“garbage collect”) the allocated memory once it is no longer in use. An important aspect of garbage collection is the mapping of object pointers to information about those pointers. Thus, a set of auxiliary data structures are used for things like marking the object “alive” and figuring out which other objects this one points to. The problem of finding this data is compounded in conservative garbage collectors where pointers to objects are followed and the memory utilized by those objects is reclaimed only under a conservative standard.
In such systems, a value that looks like a pointer may in fact be junk with no associated information. Therefore, a system for efficient determination of the validity of a pointer is needed.
SUMMARY OF THE INVENTION
This invention executed on a computer, provides an efficient and compact way to map pointers to auxiliary data by which the validity of pointers can be determined. The invention relies on a data structure which can be efficiently updated as a memory is allocated to memory blocks and as those memory blocks are deallocated. The data structure allows for efficiently determining whether a particular pointer or set of pointers points to a valid portion of allocated memory.
In accordance with one aspect of the invention, a table of the memory pages may be indexed by each pointer during memory allocation, deallocation, and status checking. An index entry in the table points to a memory block which contains at least a portion of the indexed page. Memory blocks, including memory blocks of multiple pages, into which the memory pointers point, indicate whether the pointer is valid. For example, each memory block may include an array of bits, each associated with a word in the memory block to indicate whether the pointer to that word is valid. A memory block which covers multiple pages will have a table entry for each page, each entry pointing to the same memory block which provides the information required to determine whether the pointer is valid.
Where more than one memory block overlaps an indexed page, it is preferred that the table entry point to only one of the overlapping memory blocks and that the memory block, to which the indexed table entry points, itself points to any other memory block overlapping the indexed page. Preferably, each memory block in the system is at least the size of one page so that the information is found in either the memory block to which the table entry points or a single memory block to which that memory block points.
In accordance with the preferred embodiment, each memory block allocated from a pool of free memory has a size that is at least as large as a predefined page size and further includes slots for storing representations (such as an address or index) of a starting address, an ending address, a next memory block address, and data. The slot for the representation of a starting address is initialized with a representation of the starting address of the data; the slot for the representation of an ending address is initialized with a representation of the ending address of the data; and if a previously created memory that starts on the last page of this memory block exists, a representation of the address of this newly created memory block is entered in the next memory block address slot of the previously allocated memory block.
Each of the pages in the memory block is indexed into a set of tables. In a system with two page tables, the first page table is checked for an entry found by indexing into the first page table with a first portion of the address to the first page of the memory block. If the entry is null, then a second page table is created, this page table having a set of entries for storing representations of addresses to memory blocks. An entry is created in the first page table entry selected by the first portion of the address of the memory block to store a representation of the address of the second page table. In addition, in the second page table, at the entry selected by a second portion of the address of the memory block, an entry is created for a representation of the address to the memory block.
If the entry in the first page table is not null, then the second page table is selected by using the representation of the address to the second page table found in the first page table. A second page table entry is found by indexing into the second page table with the second portion of the address of the page of the memory block, and if this entry is null, entering the representation of the memory block address.
If this page entry is not null, then a previously indexed memory block is present. If this is the first page of the memory block in question, then the previously indexed memory block starts on this page. A representation of the address of this newly created memory block is then entered in the next memory block address slot of the previously allocated memory block. If this is not the first page of the memory block in question, then the previously indexed memory block ends on this page. A representation of the address of this newly created memory block is then entered into to the second page table entry and the former contents of this entry are placed in the next memory block address slot of the newly allocated memory block. This also represents the ending page of the newly allocated memory block and thus the method is complete.
The invention further includes a system and method for determining the validity of a pointer in a system having a first page table, a set of zero or more second page tables, and a set of zero or more memory blocks. The first page table has a sequence of for storing representations of addresses for a second page table; the second page table has a sequence of entries for storing representations of addresses for a memory block; and the memory blocks have slots to store representations of a starting address, an ending address, a next memory block address, and data.
The system and method utilize the steps of checking for an entry in the first page table found by indexing into the first page table with a first portion of the address of the pointer. If the entry thus found is null, then the pointer is invalid. If the entry is not null, then a second page table is selected using the representation of the address to the second page table found in the entry from the first page table. The second page table is checked by indexing into the table with the second portion of the pointer. If the entry thus found is null, the pointer is invalid. If the entry is not null, then a memory block is selected from the set of one or more memory blocks using the entry in the second page table. The pointer is then checked for validity in the selected memory block or in a separate memory block pointed to by the selected memory block.
Thus, the system and method can efficiently allocate memory blocks. In addition, the system and method can determine the validity of a pointer via a series of table lookups.
REFERENCES:
patent: 6088780 (2000-07-01), Yamada et al.
Jones, R., et al., “Garbage Collection for C” inGarbage Collection, Algorithms for Automatic Dynamic Memory Management,(West Sussex, England: John Wiley & Sons, Ltd.), pp. 233-235 (1996).
Curl Corporation
Hamilton Brook Smith & Reynolds P.C.
Nguyen Hiep T.
LandOfFree
Pointer verification system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pointer verification system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pointer verification system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2592648