US 5,963,982 AGranted

Defragmentation of stored data without pointer indirection

AssigneeWebTV Networks, Inc.

InventorPhillip Y. Goldman

Life of this patent

Estimating the term…

Loading patent…

Abstract

A technique for defragmenting data stored in memory in a computer system includes the step of creating a table in memory including the locations of all pointers associated with stored data. The pointers are stored in a separate block of memory from the table. Data is defragmented only at idle time. In response to the defragmentation, only the values of the pointers are updated, while the locations of the pointers and the corresponding table entries remain fixed. Pointers can be updated using pointer update methods that are specific to particular classes of objects or using a generic method for all classes in conjunction with a list of pointer offsets. Pointer fields may be locating using a bit mask having values which indicate whether a particular byte or group of bytes in memory associated with an object include a pointer field.

Claims14

Dependent claims

In a computer system including a processor and a memory coupled to the processor, and one or more I/O devices connected to the processor, and wherein the memory is organized to include a plurality of data blocks, some of which are stored with data and some of which are empty, at least some of the data blocks containing data having one or more empty data blocks interspersed therebetween so that the stored data is fragmented, a method of reducing fragmentation of the stored data in the memory, the method comprising the steps of:

storing in the memory a plurality of pointers each of which includes a value that identifies an address of a data block in which data is stored;
storing in the memory a table which includes the locations of all pointers;
while the processor is not receiving input from any I/O device, defragmenting the stored data by performing the steps of:
compacting the stored data by rearranging at least some of the data blocks so that the stored data is contained in data blocks that arc more closely adjacent to one another;
and
updating the value of each pointer that identifies a data block that has been moved without changing the location of any such pointer in said stored table.

3 more elements

A computer program product for use in a computer system including a processor and a memory coupled to the processor, and one or more I/O devices connected to the processor, and wherein the memory is organized to include a plurality of data blocks, some of which are stored with data and some of which are empty, at least some of the data blocks containing data having one or more empty data blocks interspersed therebetween so that the stored data is fragmented, the computer program product comprising a computer readable medium for storing executable instructions by which the computer system will implement a method of reducing fragmentation of the stored data in the memory, the method comprising the steps of:

storing in the memory a plurality of pointers each of which includes a value that identifies an address of a data block in which data is stored;
storing in the memory a table which includes the locations of all pointers;
while the processor is not receiving input from any I/O device, defragmenting the stored data by performing the steps of:
compacting the stored data by rearranging at least some of the data blocks so that the stored data is contained in data blocks that are more closely adjacent to one another;
and
updating the value of each pointer that identifies a data block that has been moved, without changing the location of any such pointer in said stored table.

3 more elements

Dependencies are inferred from the claim text.