Abstract:
One embodiment of the present invention provides a system that uses versioned pointers to facilitate reusing memory without having to reclaim the objects solely through garbage collection. The system operates by first receiving a request to allocate an object. Next, the system obtains the object from a pool of free objects, and sets an allocated/free flag in the object to indicate that the object is allocated. The system also increments a version number in the object, and also encodes the version number into a pointer for the object. The system then returns the pointer, which includes the encoded version number. In this way, subsequent accesses to the object through the pointer can compare the version number encoded in the pointer with the version number in the object to determine whether the object has been reused since the pointer was generated.

Description:
RELATED APPLICATIONS 
       [0001]    This application is a continuation application of, and hereby claims priority under 35 U.S.C. §120 to, pending U.S. patent application Ser. No. 11/054,508, entitled “Using Versioned Pointers to Facilitate Reusing Memory with a Reduced Need to Reclaim Objects through Garbage Collection,” by inventor David R. Chase, filed on 9 Feb. 2005 (atty. docket no. SUN04-1135). 
     
    
     BACKGROUND 
       [0002]    The present invention relates to the process of allocating memory in a computer system. 
         [0003]    One of the major problems with some programming languages arises from the process of allocating and de-allocating memory. Having the programmer allocate and de-allocate memory provides many advantages when done correctly. However, programmers routinely fail to de-allocate memory when it is no longer needed, and programmers commonly re-use memory that has been de-allocated. Both of these actions can cause a program to behave incorrectly, and can lead to erroneous results or to a “crash” of the computer system. 
         [0004]    In order to obviate these problems, designers have created so-called “safe” languages, such as the JAVA™ programming language, Lisp, Modula-3, Perl, Smalltalk, ML, BASIC, C#, and the SafeC programming language. Safe programming languages typically do not trust programmers to recycle storage, because allocation errors can break the language abstraction. Instead, they either make use of a garbage collection mechanism, or use restrictive type systems to ensure that memory is recycled properly. Garbage collection generally runs quickly enough, but often has a substantial storage overhead, which can reduce the amount of storage that is available to do useful computing. 
       SUMMARY 
       [0005]    One embodiment of the present invention provides a system that uses versioned pointers to facilitate reusing memory without having to reclaim the objects solely through garbage collection. The system operates by first receiving a request to allocate an object. Next, the system obtains the object from a pool of free objects, and sets an allocated/free flag within the object to indicate that the object is allocated. The system also increments a version number within the object, and also encodes the version number into a pointer for the object. The system then returns the pointer, which includes the encoded version number. In this way, subsequent accesses to the object through the pointer can compare the version number encoded in the pointer with the version number within the object to determine whether the object has been reused since the pointer was generated. 
         [0006]    In a variation of this embodiment, the system receives a request to write data in the object. In response to the request, the system starts a memory transaction that ensures atomicity of a defined group of memory operations. Next, the system reads the object&#39;s header, compares the encoded version number in the object&#39;s pointer with the version number in the object&#39;s header, and determines if the allocated/free flag indicates the object is allocated. If the allocated/free flag indicates the object is allocated, and the encoded version number and the version number match, the system writes the data in the object and completes the memory transaction. 
         [0007]    In a further variation, if the encoded version number and the version number do not match, the system reports a failed write. 
         [0008]    In a further variation, if the memory transaction fails to complete, the system retries the memory transaction. 
         [0009]    In a further variation, the system receives a request to read data from the object. In response to the request, the system reads the object, compares the encoded version number in the object&#39;s pointer with the version number in the object&#39;s header, and determines if the allocated/free flag indicates the object is allocated. If the allocated/free flag indicates the object is allocated, and the encoded version number and the version number match, the system returns the data. Otherwise, the system returns an error. 
         [0010]    In a further variation, the system receives a request to free the object. In response to the request, the system sets the allocated/free flag to free, and if the object&#39;s version number is less than a maximum value, the system returns the object to the free pool. 
         [0011]    In a further variation, the system receives a request to perform a garbage collection of the pool of free objects. In response, the system sequences through the objects in the pool of free objects and compares the encoded version number in each object&#39;s pointer with the version number in the object&#39;s header. If the encoded version number in the pointer and the version number in the header match, the system resets the encoded version number in the pointer to zero. 
         [0012]    In a further variation, if the encoded version number in the pointer and the version number in the header do not match, the encoded version number in the pointer is either reset to an error value that will never be valid, or the pointer is modified to reference a special error object. All header version numbers on objects that survive garbage collection are reset to zero. Mark-and-sweep collectors accomplish this during their sweep phase; copying collectors accomplish this during their copying phase. 
     
    
     
       BRIEF DESCRIPTION OF THE FIGURES 
         [0013]      FIG. 1  illustrates a computer system in accordance with an embodiment of the present invention. 
           [0014]      FIG. 2  illustrates a memory organization in accordance with an embodiment of the present invention. 
           [0015]      FIG. 3  illustrates a container in accordance with an embodiment of the present invention. 
           [0016]      FIG. 4  illustrates an object in accordance with an embodiment of the present invention. 
           [0017]      FIG. 5  illustrates a pointer in accordance with an embodiment of the present invention. 
           [0018]      FIG. 6  presents a flowchart illustrating the process of creating a container in accordance with an embodiment of the present invention. 
           [0019]      FIG. 7  presents a flowchart illustrating the process of allocating an object in accordance with an embodiment of the present invention. 
           [0020]      FIG. 8  illustrates a flowchart illustrating the process of writing data to an object in accordance with an embodiment of the present invention. 
           [0021]      FIG. 9  presents a flowchart illustrating the process of reading data from an object in accordance with an embodiment of the present invention. 
           [0022]      FIG. 10  presents a flowchart illustrating the process of de-allocating an object in accordance with an embodiment of the present invention. 
           [0023]      FIG. 11  presents a flowchart illustrating the process of performing garbage collection in accordance with an embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0024]    The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein. 
         [0025]    The data structures and code described in this detailed description are typically stored on a computer readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs) and DVDs (digital versatile discs or digital video discs), and computer instruction signals embodied in a transmission medium (with or without a carrier wave upon which the signals are modulated). For example, the transmission medium may include a communications network, such as the Internet. 
       Computer System 
       [0026]      FIG. 1  illustrates a computer system  100  in accordance with an embodiment of the present invention. Computer system includes processor  102 , bridge  104 , and memory  106 . Processor  102  can generally include any type of processor, including, but not limited to, a microprocessor, a mainframe computer, a digital signal processor, a personal organizer, a device controller, and a computational engine within an appliance. 
         [0027]    Memory  106  includes random-access memory (RAM) which is used to store program instructions and data during execution of a program by processor  102 . Bridge  104  couples processor  102  to memory  106  and controls the flow of instructions and data between processor  102  and memory  106 . 
       Memory 
       [0028]      FIG. 2  illustrates a system memory organization in accordance with an embodiment of the present invention. Memory  106  includes heap  202 . Heap  202  provides storage for containers  204  and  206 . Each container provides storage for a pool of objects, which are the same size. Different containers provide storage for objects of different sizes. 
       Container 
       [0029]      FIG. 3  illustrates a container  204  in accordance with an embodiment of the present invention. Container  204  provides storage for objects  301 - 309 . Note that container  204  can provide storage for more or fewer objects than shown. The structure of each object is described in more detail in conjunction with  FIG. 4  below. 
       Object 
       [0030]      FIG. 4  illustrates an object  302  in accordance with an embodiment of the present invention. Object  302  is exemplary of the objects stored within the various containers in heap  202 . Object  302  includes header data  402 , allocated/free flag  404 , new/old flag  406 , version number  408 , and data  410 . Header data  402  and data  410  are commonly found in objects and will not be discussed further herein. 
         [0031]    Allocated/free flag  404  indicates whether object  302  is allocated or not, while new/old flag  406  is a standard flag that is commonly used during garbage collection operations. Version number  408  indicates the version number for the current allocation of object  302 . Allocated/free flag  404 , new/old flag  406 , and version number  408  are described in detail in conjunction with  FIGS. 6-11  below. 
       Pointer 
       [0032]      FIG. 5  illustrates a pointer in accordance with an embodiment of the present invention. The pointer includes stale flag  502 , new/old flag  504 , version number  506 , and address  508 . Note that for the immediate future, four petabytes (2 52 ) is probably a reasonable upper limit on the memory that might be directly addressed in a computer. Given 64-bit pointers, this provides 12 bits for tagging (1 bit each for stale flag  502  and new/old flag  504  and 10 bits for version number  506 ). 
         [0033]    After masking off stale flag  502 , new/old flag  504 , and version number  506  in the pointer, the pointer includes only address  508 , which is the address where the related object is stored. 
       Creating a Container 
       [0034]      FIG. 6  presents a flowchart illustrating the process of creating a container in accordance with an embodiment of the present invention. The system starts by determining the size and quantity of objects needed for the program to execute efficiently (step  602 ). Next, the system creates a container within the heap for each size of object (step  604 ). 
         [0035]    After the containers have been created, the system initializes each object in each container (step  606 ). This initialization includes setting the allocated/free flag to free, the new/old flag to new, and the version number to zero. Finally, the system initializes a pointer to each object in each container (step  608 ). This initialization involves clearing the stale flag, setting the new/old flag to new, setting the version number to zero, and setting the address to point to the object. 
       Allocating an Object 
       [0036]      FIG. 7  presents a flowchart illustrating the process of allocating an object in accordance with an embodiment of the present invention. The system starts by incrementing the version number in the object&#39;s header (step  702 ). Next, the system sets the allocated/free bit to allocated (step  704 ). Finally, the system copies the version number from the object header to the tag area of the pointer (step  706 ). 
       Writing Data 
       [0037]      FIG. 8  illustrates a flowchart illustrating the process of writing data to an object in accordance with an embodiment of the present invention. This process assumes that the computer system includes transactional memory to ensure that given memory transactions are either committed as a block or failed as a block to maintain memory coherence. 
         [0038]    The system starts by starting a memory transaction (step  802 ). Next, the system reads the version number from the object (step  804 ). After reading the version number from the object, the system compares this version number with the version number stored in the pointer (step  806 ). If the version numbers are equal, the object has not been reallocated and the system next checks the free/allocated flag to see if the object is allocated (step  806 ). 
         [0039]    If the free/allocated flag is set to allocated in step  808 , the system writes the data to the object (step  810 ). Next, the system commits the transaction (step  812 ). After committing the transaction, the system determines if the transaction has failed (step  814 ). If not, the process is complete. Otherwise, the process returns to step  802  to make another attempt. 
         [0040]    If the version numbers do not match at step  806  or the free/allocated flag is equal to free at step  808  the system throws an exception (step  816 ). 
       Reading Data 
       [0041]      FIG. 9  presents a flowchart illustrating the process of reading data from an object in accordance with an embodiment of the present invention. The system starts by reading the object including the header (step  902 ). Next, the system determines if the version number in the header matches the version number in the pointer (step  904 ). If the version numbers match, the system returns the data (step  906 ). Otherwise, the system throws an exception (step  908 ). 
       De-Allocating an Object 
       [0042]      FIG. 10  presents a flowchart illustrating the process of de-allocating an object in accordance with an embodiment of the present invention. The system starts by setting the allocated/free flag to free in the object&#39;s header (step  1002 ). Next, the system determines if the version number is less than a maximum allowed version number (step  1004 ). If not, the system places the object on a free list of objects (step  1006 ). Otherwise, the system marks the object as unusable (step  1008 ). Note that this can be accomplished in any number of ways—for example, by setting the version number to a specific reserved value. Note also that object marked as unusable can be reclaimed during a garbage collection as described below in conjunction with  FIG. 11 . 
       Garbage Collection 
       [0043]      FIG. 11  presents a flowchart illustrating the process of performing garbage collection in accordance with an embodiment of the present invention. Note that the garbage collection operation can be performed by any available technique, one of which is described herein. A practitioner with ordinary skill in the art can readily adapt this invention to other garbage collectors. The system starts by reversing the meaning of the new/old flag (step  1102 ). Since all of the objects were marked as new, by reversing the meaning of the new/old flag, all objects become old. Next, the system sets the stale flag in each pointer in the root set (step  1104 ). 
         [0044]    The system then examines a pointer as part of any object read or write operation (step  1106 ). Next, the system reads the object associated with the pointer (step  1108 ). After reading the object, the system compares the state and version of the object with the state and version of the pointer (step  1110 ). This comparison involves masking the header so that only the allocated/free flag, the old/new flag, and the version number are present. It also involves arithmetically shifting the stale flag, the new/old flag, and the version number to the right most position in the pointer. Note that using an arithmetic shift ensures that no stale pointer will match. 
         [0045]    If there is no match (step  1112 ), the system copies the object, resets the stale flag, and sets the new/old flag to new (step  1114 ). Note that the only way for a match to occur is for the pointer to be not stale, the object to be allocated, and the version number to match. After copying the object at step  1114  or if there is a match at step  1112 , the system determines if all pointers have been visited (step  1116 ). If not, the process returns to step  1106  to select another pointer. Otherwise, the process is terminated. 
       Garbage Collection Techniques 
       [0046]    The following garbage collection techniques are based on existing techniques for mark-and-sweep, copying-compacting, and Appel-Ellis-Li-like garbage collectors. Modifications necessary to support versioned pointers are underlined. 
       Common Code 
       [0047]    The following examples provide pointer operations that are common to several garbage collection implementations. Note that other bit assignments may be more efficient for specific garbage collections implementations. 
         [0048]    Return true if and only if a pointer is obsolete with respect to the object it references. 
         [0049]    obsolete(P:pointer):pointer 
         [0050]    version(P) !=header version(*P)∥freed(P) 
         [0051]    Construct a version-tagged pointer from an address and tag value. 
         [0052]    tagged pointer(A:address, T:tag):pointer=A+(T&lt;&lt;52) 
         [0053]    Extract the version number (bits  52 - 63 ) from a pointer. 
         [0054]    version(P:pointer):tag=P&gt;&gt;&gt;52 
         [0055]    Extract the version number (bits  0 - 11 ) from an object header word. 
         [0056]    header version(W:word):tag=return P&amp;)0xfff) 
         [0057]    Extract the freed bit ( 12 ) from an object header word 
         [0058]    freed(W:word):Boolean=(P&gt;&gt;12)&amp;1 
         [0059]    Allocate memory from the free list for a particular size. 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 allocate(size:integer):pointer 
               
               
                   
                  transactionally 
               
               
                   
                   I = frelists[size] 
               
               
                   
                   if I empty then refill I 
               
               
                   
                   remove o from I 
               
               
                   
                   set freed(o) = false 
               
               
                   
                   return 0 
               
               
                   
                 end 
               
               
                   
                   
               
             
          
         
       
     
         [0060]    Free a previously allocated object and return it to the appropriate free list. 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 free(P:pointer) = 
               
               
                   
                  transactionally 
               
               
                   
                   O = Ps object 
               
               
                   
                   size = size of O 
               
               
                   
                   v = version(P) 
               
               
                   
                   if v &lt; MAXIMUM VERSION then 
               
               
                   
                    if not obsolete(P) then 
               
               
                   
                     version(O) = version(O) + 1 
               
               
                   
                     freed(O) = true 
               
               
                   
                     put O on freelists[size] 
               
               
                   
                    else report error 
               
               
                   
                   else set freed(o) = true 
               
               
                   
                 end 
               
               
                   
                   
               
             
          
         
       
     
         [0061]    Write barrier for all three collectors (new with versioned pointers). Translation of P.f=X. 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 write barrier(P:pointer) = 
               
               
                   
                  transactionally 
               
               
                   
                   A = addrbits(P) 
               
               
                   
                   To = otagbits(*A) 
               
               
                   
                   Tp = ptagbits(P) 
               
               
                   
                  if To != Tp then 
               
               
                   
                   if version(To) != version(Tp) then throw error 
               
               
                   
                   if freed(To) != freed(Tp) then throw error 
               
               
                   
                  *(A+f) = X 
               
               
                   
                  return 
               
               
                   
                   
               
             
          
         
       
     
         [0062]    Read barrier for mark-sweep and copying-compacting. Translation of X=P.f. 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 read barrier(P:pointer):data = 
               
               
                   
                  transactionally 
               
               
                   
                   A = addrbits(P) 
               
               
                   
                   X = *(A+f) 
               
               
                   
                   To = otagbits(*A) 
               
               
                   
                   Tp = ptagbits(P) 
               
               
                   
                   if To != Tp then 
               
               
                   
                    if version(To) != version(Tp) then throw error 
               
               
                   
                    if freed(To) != freed(Tp) then throw error 
               
               
                   
                   return X 
               
               
                   
                   
               
             
          
         
       
     
       Concurrent Collector Operations 
       [0063]    Extract tag bits from an object header. 
         [0064]    otagbits(W:word)=W&amp;0x3fff 
         [0065]    Extract tag bits from a pointer. 
         [0066]    ptagbits(W&gt;&gt;&gt;52)+(W&gt;&gt;(51-13) &amp; 0x2000) 
         [0067]    Extract the age bit ( 13 ) from an object header word or a tag. 
         [0068]    age(W:word or tag):Boolean=(W&gt;&gt;13) &amp; 1 
         [0069]    Extract the age bit ( 51 ) from a pointer. 
         [0070]    age(P:pointer):Boolean=W&gt;&gt;51) &amp; 1 
         [0071]    Invert an age. 
         [0072]    flip(b:Boolean)=b XOR 1 
       Copying Collector Operations 
       [0073]    Has the object been forwarded? 
         [0074]    forwarded(W:word):Boolean=(W&gt;&gt;14) &amp; 1 
         [0075]    The address to which the object was forwarded (assume 8-byte alignment). 
         [0076]    forward(W:word):Address=(W&gt;&gt;&gt;12) &amp; 0xffffFFFFffffFFF8 
         [0077]    Mark-and Sweep garbage collection with versioned pointers. 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 mark_sweep_gc( ) = 
               
               
                   
                  bag = new Bag 
               
               
                   
                  //process registers 
               
               
                   
                  foreach register R 
               
               
                   
                   R = process_ms(R, bag) 
               
               
                   
                  //process every pointer in bag 
               
               
                   
                  while bag not empty 
               
               
                   
                   take P from bag 
               
               
                   
                   foreach pointer index I of Ps object 
               
               
                   
                    P[i] = process_ms(P[i], bag) 
               
               
                   
                  //sweep 
               
               
                   
                  foreach object(o) in heap 
               
               
                   
                   version(o) = 0 
               
               
                   
                   if visited(o) then reset viited(o) 
               
               
                   
                   else 
               
               
                   
                    set freed(o) = true 
               
               
                   
                    put o on freelists[size(o)] 
               
               
                   
                 end 
               
               
                   
                 process_ms(P:pointer, bag:Bag):pointer = 
               
               
                   
                  if obsolete(P) then return error pointer 
               
               
                   
                  else if not visited(P) then 
               
               
                   
                   set visited in Ps objects header 
               
               
                   
                   put P in bag 
               
               
                   
                  return tagged pointer(address(P), o) 
               
               
                   
                   
               
             
          
         
       
     
         [0078]    Copying-compacting collection with versioned pointers. 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 scanned:address 
               
               
                   
                 unscanned:address 
               
               
                   
                 copy_compact_gc( ) = 
               
               
                   
                  scanned = unscanned = address of new memory 
               
               
                   
                  foreach register R 
               
               
                   
                   R = process_cc(R) 
               
               
                   
                  while scanned &lt; unscanned do 
               
               
                   
                   P = scanned 
               
               
                   
                   O = object at P 
               
               
                   
                   scanned = scanned + size(O) 
               
               
                   
                   foreach pointer index I of O 
               
               
                   
                    P[i] = process_cc(P[i]) 
               
               
                   
                 end 
               
               
                   
                 process_cc(P:pointer):pointer = 
               
               
                   
                  if obsolete(P) then return error pointer 
               
               
                   
                  else if forwarded(P) then 
               
               
                   
                   return tagged pointer(forward(*P), 0) 
               
               
                   
                  else 
               
               
                   
                   O = object at P 
               
               
                   
                   size = size(P) 
               
               
                   
                   F = unscanned 
               
               
                   
                   unscanned = unscanned + size 
               
               
                   
                   copy O form P to F 
               
               
                   
                   set version of copied object at F to 0 
               
               
                   
                   set forward(*P) to F 
               
               
                   
                   return tagged pointer(F, 0) 
               
               
                   
                 end 
               
               
                   
                   
               
             
          
         
       
     
         [0079]    Appel-Ellis-Li-style concurrent collection with versioned pointers. 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 scanned, unscanned:address 
               
               
                   
                  ael_integrated_gc( ) = 
               
               
                   
                   scanned = unscanned = address of new memory 
               
               
                   
                   foreach register R 
               
               
                   
                    R = process_ael(R) //old pointer become new 
               
               
                   
                  end 
               
               
                   
                  process_ael(P:pointer):pointer = 
               
               
                   
                   if obsolete(P) then return error pointer 
               
               
                   
                   else if forwarded(*P) then 
               
               
                   
                    return age_tagged_pointer(forward(*P), 
               
               
                   
                             0, flip(age(P))) 
               
               
                   
                   else 
               
               
                   
                    O = object at P 
               
               
                   
                    size − size(O) 
               
               
                   
                    F = unscanned 
               
               
                   
                    unscanned = unscanned + size 
               
               
                   
                    copy O from P to F 
               
               
                   
                    set version of copied object at F to 0 
               
               
                   
                    set age of copied object at F to age(P)//old age 
               
               
                   
                    set forward(*P) to F 
               
               
                   
                    return age_tagged_pointer(F, 0, flip(age(P))) 
               
               
                   
                 end 
               
               
                   
                   
               
             
          
         
       
     
         [0080]    Translation of X=P.f. 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 read_barrier(P:pointer):data = 
               
               
                   
                  transactionally 
               
               
                   
                   A = addrbits(P) 
               
               
                   
                   X = *(A + f) 
               
               
                   
                   To = otagbits(*A) 
               
               
                   
                   Tp = ptagbits(P) 
               
               
                   
                   if To != Tp then 
               
               
                   
                    if version(To) != version(Tp) then throw error 
               
               
                   
                    if freed(To) != freed(Tp) then throw error 
               
               
                   
                    if age(To) != age(Tp) then promote_object(A, Tp) 
               
               
                   
                    return X 
               
               
                   
                  promote_object(A:address, T:tag) = 
               
               
                   
                   foreach pointer index I of object at A do 
               
               
                   
                    A[i] = process_ael(A[i]) 
               
               
                   
                   set age of object at A to age(Tp) 
               
               
                   
                   
               
             
          
         
       
     
         [0081]    The foregoing descriptions of embodiments of the present invention have been presented for purposes of illustration and description only. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.