US 5,687,368 A · CPU-controlled garbage-collecting memory module · patentgrep

Loading patent…

Abstract

The CPU-controlled garbage-collecting memory module (CPU-C GCMM) is essentially an intelligent memory that connects to a central processing unit (CPU) and performs the routine and repetitive tasks associated with a spectrum of garbage-collecting techniques under the direction and control of the CPU. The CPU-C GCMM performs its garbage-collecting tasks as background tasks to be performed when the CPU-C GCMM is not burdened with the ordinary fetch and store operations necessitated by the application programs being run on the CPU. The CPU-C GCMM can be structured in a variety of ways. One species which embodies the essence of the invention includes a memory and a memory controller which provides the means for reading data from and writing data to the memory. The memory controller receives fetch requests directly from the CPU and returns the requested data immediately even though the data may be incorrect in certain instances. A microcontroller which exercises overall control over the component parts of the CPU-C GCMM together with a fetch monitor work together to repair any incorrect data deliveries to the CPU by the memory controller. A communication-channels unit provides the means of communication between the CPU and the microcontroller for handling all interactions between the CPU and the CPU-C GCMM except fetch requests. An object space manager unit provides a means for rapidly identifying the header of an object given a pointer to the interior of an object.

Claims98

Dependent claims

An apparatus for use with a central processing unit (CPU) comprising:

a memory for storing words and objects, an object comprising a plurality of words that share a particular attribute and occupy a contiguous region of memory, each object having a header that specifies the type and size of an object, the memory having a subspace designated as header-space, header-space having a plurality of locations for storing words, each location having a unique address, the addresses in header-space being ordered;
an arbiter having a means of communication with the CPU and a means for writing data into and reading data out of the memory, a request by the CPU to create a specified object of a specified size at a specified beginning address in the memory causing the arbiter to perform an action, the specified object having a header address, there being a plurality of addresses to be occupied by the specified object, the action being to derive and store a header-location code in header-space for each address to be occupied by the specified object, the header address of the object being derivable from the header-location code.

An apparatus for use with a central processing unit (CPU) comprising:

a memory for storing words and objects, an object comprising a plurality of words that share a particular attribute and occupy a contiguous region of memory, each object having a header that specifies the type and size of an object, the memory having a subspace designated as header-space, header-space having a plurality of locations for storing words, each location having a unique address, the addresses in header-space being ordered, the memory having subspaces designated as from-space and to-space, each subspace having a plurality of locations for storing words, each location having a unique address, the addresses in each subspace being ordered, two addresses in to-space being designated as Relocated and Reserved, the memory having a subspace designated as mark-and-sweep-space, the mark-and-sweep-space having a plurality of locations for storing words, each location having a unique address, the addresses in the mark-and-sweep-space being ordered, each object stored in mark-and-sweep-space having a link field in a predetermined location relative to the object header, an unmarked object being one where the link field contains a non-address, a non-address being a word that is not an address in the memory, a marked object being one where the link field contains a pointer to the next marked object on a marked-object list that contains all marked objects, two addresses in mark-and-sweep-space being designated as MSRelocated and MSReserved;
an arbiter having a means of communication with the CPU and a means for writing data into and reading data out of the memory, a request by the CPU to create a specified object of a specified size at a specified beginning address in the memory causing the arbiter to perform an action, the specified object having a header address, there being a plurality of addresses to be occupied by the specified object, the action being to derive and store a header-location code in header-space for each address to be occupied by the specified object, the header address of the object being derivable from the header-location code, the arbiter, upon receiving a request from the CPU to fetch data from the memory at a specified address, (1) if the specified address lies between Relocated and Reserved or between MSRelocated and MSReserved, determining the address of the header of the object containing the specified address and fetches the requested data from from-space, the header of the object in to-space or mark-and-sweep-space providing a pointer to the header of the object in from-space, or (2) if the specified address does not lie between Relocated and Reserved or between MSRelocated and MSReserved, fetching the requested data from the memory at the specified address.

An apparatus for use with a central processing unit (CPU) comprising:

a memory for storing words and objects, an object comprising a plurality of words that share a particular attribute and occupy a contiguous region of memory, each object having a header that specifies the type and size of an object, the memory having a subspace designated as header-space, header-space having a plurality of locations for storing words, each location having a unique address, the addresses in header-space being ordered, the memory having subspaces designated as from-space and to-space, each subspace having a plurality of locations for storing words, each location having a unique address, the addresses in from-space and to-space being ordered, each word in memory containing a bit that identifies the word as being a pointer or a non-pointer, a copy count being maintained in the header of each object of the number of times the object has been copied from from-space to to-space, the memory having a subspace designated as mark-and-sweep-space, the mark-and-sweep-space having a plurality of locations for storing words, each location having a unique address, the addresses in mark-and-sweep-space being ordered, each object stored in mark-and-sweep-space having a link field in a predetermined location relative to the object header, an unmarked object being one where the link field contains a non-address, a non-address being a word that is not an address in the memory, a marked object being one where the link field contains a pointer to the next marked object on a marked-object list that contains all marked objects;
an arbiter having a means of communication with the CPU and a means for writing data into and reading data out of the memory, a request by the CPU to create a specified object of a specified size at a specified beginning address in the memory causing the arbiter to perform an action, the specified object having a header address, there being a plurality of addresses to be occupied by the specified object, the action being to derive and store a header-location code in header-space for each address to be occupied by the specified object, the header address of the object being derivable from the header-location code, the arbiter, upon receiving a request from the CPU to fetch data from the memory at a specified address and the requested data is a pointer to a from-space object, determining the address of the header of the from-space object and (1) if the header contains a pointer to the header of the object in a location reserved for the object in to-space, changing the requested data to a to-space pointer, or (2) if the header does not contain a pointer to the header of the object in a location reserved for the object in to-space and if the copy count equals or exceeds a predetermined number, designating a reserved space in mark-and-sweep-space for the from-space object, adding the from-space object to a mark-and-space copy queue, the mark-and-space copy queue being a list of objects in from-space to be copied to reserved spaces in mark-and-sweep-space, deriving and storing a header-location code in header-space for each address in mark-and-sweep-space reserved for the from-space object, copying the header of the from-space object to its reserved mark-and-sweep-space location, placing a pointer in the mark-and-sweep-space header pointing to the object's location in from-space, placing a pointer in the from-space header pointing to the object's reserved location in mark-and-sweep-space, and translating the requested data into a mark-and-sweep-space pointer or (3) if the header does not contain a pointer to the header of the object in a location reserved for the object in to-space and if the copy count does not equal or exceed a predetermined number, reserving space in to-space for the from-space object, adding the from-space object to a copy queue, the copy queue being a list of objects in from-space to be copied to reserved spaces in to-space, deriving and storing a header-location code in header-space for each address in to-space reserved for the from-space object, copying the header of the from-space object to its reserved to-space location, placing a pointer in the to-space header pointing to the object's location in from-space, placing a pointer in the from-space header pointing to the object's reserved location in to-space, and translating the requested data into a to-space pointer.

An apparatus for use with a central processing unit (CPU) comprising:

a memory for storing words and objects, an object comprising a plurality of words that share a particular attribute and occupy a contiguous region of memory, each object having a header that specifies the type and size of an object, the memory having a subspace designated as header-space, header-space having a plurality of locations for storing words, each location having a unique address, the addresses in header-space being ordered, the memory having subspaces designated as from-space and to-space, each subspace having a plurality of locations for storing words, each location having a unique address, the addresses in each subspace being ordered, two addresses in to-space being designated as Relocated and Reserved, the memory having a subspace designated as mark-and-sweep-space, the mark-and-sweep-space having a plurality of locations for storing words, each location having a unique address, the addresses in the mark-and-sweep-space being ordered, each object stored in mark-and-sweep-space having a link field in a predetermined location relative to the object header, an unmarked object being one where the link field contains a non-address, a non-address being a word that is not an address in the memory, a marked object being one where the link field contains a pointer to the next marked object on a marked-object list that contains all marked objects, two addresses in mark-and-sweep-space being designated as MSRelocated and MSReserved;
an arbiter having a means of communication with the CPU and a means for writing data into and reading data out of the memory, a request by the CPU to create a specified object of a specified size at a specified beginning address in the memory causing the arbiter to perform an action, the specified object having a header address, there being a plurality of addresses to be occupied by the specified object, the action being to derive and store a header-location code in header-space for each address to be occupied by the specified object, the header address of the object being derivable from the header-location code, the arbiter, upon receiving a request from the CPU to write specified data into the memory at a specified address, (1) if the specified address lies between Relocated and Reserved or between MSRelocated and MSReserved, determining the address of the header of the object containing the specified address and writing the specified data into from-space or mark-and-sweep-space respectively, the header of the object in to-space providing a pointer to the header of the object in from-space or mark-and-sweep-space respectively, or (2) if the specified address does not lie between Relocated and Reserved or between MSRelocated and MSReserved, writing the specified data to the specified address.

An apparatus for use with a central processing unit (CPU) comprising:

a memory for storing words and objects, an object comprising a plurality of words that share a particular attribute and occupy a contiguous region of memory, each object having a header that specifies the type and size of an object, the memory having a subspace designated as header-space, header-space having a plurality of locations for storing words, each location having a unique address, the addresses in header-space being ordered, the memory having a subspace designated as mark-and-sweep-space, the mark-and-sweep-space having a plurality of locations for storing words, each location having a unique address, the addresses in the mark-and-sweep-space being ordered, each object stored in mark-and-sweep-space having a link field in a predetermined location relative to the object header, an unmarked object being one where the link field contains a non-address, a non-address being a word that is not an address in the memory, a marked object being one where the link field contains a pointer to the next marked object on a marked-object list that contains all marked objects;
an arbiter having a means of communication with the CPU and a means for writing data into and reading data out of the memory, a request by the CPU to create a specified object of a specified size at a specified beginning address in the memory causing the arbiter to perform an action, the specified object having a header address, there being a plurality of addresses to be occupied by the specified object, the action being to derive and store a header-location code in header-space for each address to be occupied by the specified object, the header address of the object being derivable from the header-location code, the arbiter, upon receiving a request from the CPU to fetch data from the mark-and-sweep-space at a specified address, determining the address of the header of the object to which the requested data points and, if the link field of the object contains a non-address, adding the object to the marked-object list.

An apparatus for use with a central processing unit (CPU) comprising:

a memory for storing words and objects, an object comprising a plurality of words that share a particular attribute and occupy a contiguous region of memory, each object having a header that specifies the type and size of an object, the memory having a subspace designated as header-space, header-space having a plurality of locations for storing words, each location having a unique address, the addresses in header-space being ordered, the memory having subspaces designated as from-space and to-space, each subspace having a plurality of locations for storing words, each location having a unique address, the addresses in each subspace being ordered, two addresses in to-space being designated as Relocated and Reserved;
an arbiter having a means of communication with the CPU and a means for writing data into and reading data out of the memory, a request by the CPU to create a specified object of a specified size at a specified beginning address in the memory causing the arbiter to perform an action, the specified object having a header address, there being a plurality of addresses to be occupied by the specified object, the action being to derive and store a header-location code in header-space for each address to be occupied by the specified object, the header address of the object being derivable from the header-location code, the arbiter, upon receiving a request from the CPU to write specified data into the memory at a specified address, (1) if the specified address lies between Relocated and Reserved, determining the address of the header of the object containing the specified address and writing the specified data into from-space, the header of the object in to-space providing a pointer to the header of the object in from-space, or (2) if the specified address does not lie between Relocated and Reserved, writing the specified data to the specified address.

A method for operating a memory under the direction of a central processing unit (CPU), the memory being used for storing words and objects, an object comprising a plurality of words that share a particular attribute and occupy a contiguous region of memory, each object having a header that specifies the type and size of an object, the memory having a subspace designated as header-space, header-space having a plurality of locations for storing words, each location having a unique address, the addresses in header-space being ordered, the CPU having requested that an object of a specified size at a specified beginning address in the memory be created, the method comprising the steps:

deriving a header-location code for each address occupied by the specified object, the header address of the object being derivable from the header-location code;
writing the header-location codes into header-space.

Dependencies are inferred from the claim text.