Method of deterministic garbage collection

Abstract

A garbage collection method that distinguishes between local objects and managed objects, and between an ordinary pointer to an object, an owning pointer to an object, and a non-owning pointer to an object is presented. Ordinary pointers point only to local objects, and owning and non-owning pointers point only to managed objects. Managed objects have attributes including a count of the number of owning pointers referring to them, and a linked list of non-owning pointers referring to them. Managed objects only possess non-owning pointers. Only an invocation of a subroutine within a thread can possess an owning pointer. Using this method, when an invocation exits, its exit code gives up ownership of all objects it owned. When an object is no longer reachable from any owning pointer, either directly, or indirectly through non-owning pointers, the object is immediately de-allocated. By implementing data structures and methods to support owning pointers, non-owning pointers, and managed objects, and by enforcing rules regarding the use of ordinary pointers, owning pointers, and non-owning pointers, efficient and deterministic garbage collection is achieved, memory leaks and dangling pointers are eliminated, and objects containing circular references to each other are not a source of memory leaks.

1. A garbage collection method comprising:
 providing ordinary pointers to point only to local objects, said local objects are objects that must expire before invocations that create them;  
 providing owning and non-owning pointers to point only to managed objects, said managed objects are objects that may outlive invocations that create them;  
 determining whether said managed objects are reachable from at least one of said owning pointers;  
 destroying or marking for destruction at least one of said managed objects when said at least one of said managed objects is un-reachable through said at least one of said owning pointers or said at least one of said non-owning pointers; and  
 nullifying said non-owning pointers pointing to said at least one of said managed objects when said at least one of said managed objects is destroyed or marked for destruction.  
 
     
     
       2. The method of  claim 1  wherein said determining whether said managed objects are reachable from said at least one of said owning pointers comprises:
 determining whether said managed objects are reachable from said at least one of said owning pointers through said at least one of said owning pointers or at least one of said non-owning pointers.  
 
     
     
       3. The method of  claim 1  further comprising:
 defining classes of said owning and non-owning pointers.  
 
     
     
       4. The method of  claim 3  further comprising:
 restricting use of said classes according to rules of a programing language.  
 
     
     
       5. The method of  claim 1  wherein any one of said invocations comprises a subroutine invocation. 
     
     
       6. The method of  claim 1  further comprising:
 sharing said managed objects with multiple threads of control within a single process; and  
 accessing a shared memory allocation pool serialized by a lock accessible by said threads, said managed objects that are shared are allocated to said shared memory allocation pool, said lock controlling access to said managed objects that are shared.  
 
     
     
       7. The method of  claim 6  further comprising:
 defining classes of said owning and non-owning pointers; and  
 restricting use of said classes according to rules of a programming language.  
 
     
     
       8. The method of  claim 1  further comprising:
 sharing said managed objects with multiple processes within a single system; and  
 accessing a shared memory allocation pool serialized by a lock accessible by said processes, said managed objects that are shared are allocated to said shared memory allocation pool, said lock controlling access to said managed objects that are shared.  
 
     
     
       9. The method of  claim 8  further comprising:
 defining classes of said owning and non-owning pointers; and  
 restricting use of said classes according to rules of a programming language.  
 
     
     
       10. The method of  claim 1  utilized with a POSIX®-compliant file system. 
     
     
       11. A storage medium encoded with machine-readable code, the code including instructions for causing a computer to implement a method of garbage collection comprising:
 providing ordinary pointers to point only to local objects, said local objects are objects that must expire before invocations that create them;  
 providing owning and non-owning pointers to point only to managed objects, said managed objects are objects that may outlive invocations that create them;  
 determining whether said managed objects are reachable from at least one of said owning pointers;  
 destroying or marking for destruction at least one of said managed objects when said at least one of said managed objects is un-reachable through said at least one of said owning pointers or said at least ore of said non-owning pointers; and  
 nullifying said non-owning pointers pointing to said at least one of said managed objects when said at least one of said managed objects is destroyed or marked for destruction.  
 
     
     
       12. The storage medium of  claim 11  wherein said determining whether said managed objects are reachable from said at least one of said owning pointers comprises:
 determining whether said managed objects are reachable from said at least one of said owning pointers through said at least one of said owning pointers or at least one of said non-owning pointers.  
 
     
     
       13. The storage medium of  claim 11  wherein the method further comprises:
 defining classes of said owning and non-owning pointers.  
 
     
     
       14. The storage medium of  claim 13  wherein the method further comprises:
 restricting use of said classes according to rules of a programming language.  
 
     
     
       15. The storage medium of  claim 11  wherein any one of said invocations comprises a subroutine invocation. 
     
     
       16. The storage medium of  claim 11  wherein the method further comprises:
 sharing said managed objects with multiple threads of control within a single process; and  
 accessing a shared memory allocation pool serialized by a lock accessible by said threads, said managed objects that are shared are allocated to said shared memory allocation pool, said lock controlling access to said managed objects that are shared.  
 
     
     
       17. The storage medium of  claim 16  wherein the method further comprises:
 defining classes of said owning and non-owning pointers; and  
 restricting use of said classes according to rules of a programming language.  
 
     
     
       18. The storage medium of  claim 11  wherein the method further comprises:
 sharing said managed objects with multiple processes within a single system; and  
 accessing a shared memory allocation pool serialized by a lock accessible by said processes, said managed objects that are shared are allocated to said shared memory allocation pool, said lock controlling access to said managed objects that are shared.  
 
     
     
       19. The storage medium of  claim 18  wherein the method further comprises:
 defining classes of said owning and non-owning pointers; and  
 restricting use of said classes according to rules of a programming language.  
 
     
     
       20. A signal propagated over a propagation medium, the signal encoded with code, the code including instructions for causing a computer to implement a method of garbage collection comprising:
 providing ordinary pointers to point only to local objects, said local objects are objects that must expire before invocations that create them;    providing owning and non-owning pointers to point only to managed objects, said managed objects are objects that may outlive invocations that create them;    determining whether said managed objects are reachable from at least one of said owning pointers;    destroying or marking for destruction at least one of said managed objects when said at least one of said managed objects is un-reachable through said at least one of said owning pointers or said at least one of said non-owning pointers; and    nullifying said non-owning pointers pointing to said at least one of said managed objects when said at least one of said managed objects is destroyed or marked for destruction.    
     
     
       21. The signal propagated over the propagation medium of  claim 20  wherein said determining whether said managed objects are reachable from said at least one of said owning pointers comprises:
 determining whether said managed objects are reachable from said at least one of said owning pointers through said at least one of said owning pointers or at least one of said non-owning pointers.  
 
     
     
       22. The signal propagated over the propagation medium of  claim 20  wherein the method further comprises:
 defining classes of said owning and non-owning pointers.  
 
     
     
       23. The signal propagated over the propagation medium of  claim 22  wherein the method further comprises:
 restricting use of said classes according to rules of a programming language.  
 
     
     
       24. The signal propagated over the propagation medium of  claim 20  wherein any one of said invocations comprises a subroutine invocation. 
     
     
       25. The signal propagated over the propagation medium of  claim 20  wherein the method further comprises:
 sharing said managed objects with multiple threads of control within a single process; and  
 accessing a shared memory allocation pool serialized by a lock accessible by said threads, said managed objects that are shared are allocated to said shared memory allocation pool, said lock controlling access to said managed objects that are shared.  
 
     
     
       26. The signal propagated over the propagation medium of  claim 25  wherein the method further comprises:
 defining classes of said owning and non-owning pointers; and  
 restricting use of said classes according to rules of a programming language.  
 
     
     
       27. The signal propagated over the propagation medium of  claim 20  wherein the method farther comprises:
 sharing said managed objects with multiple processes within a single system; and  
 accessing a shared memory allocation pool serialized by a lock accessible by said processes, said managed objects that are shared are allocated to said shared memory allocation pool, said lock controlling access to said managed objects that are shared.  
 
     
     
       28. The signal propagated over the propagation medium of  claim 27  wherein the method further comprises:
 defining classes of said owning and non-owning pointers; and  
 restricting use of said classes according to rules of a programming language.  
 
     
     
       29. A method of garbage collection in computer memory, the method comprising:
   pointing by a processor one or more owning pointers or non - owning pointers, or a combination thereof, to one or more managed objects, the managed objects being created in the computer memory during a first invocation, and capable of outliving one or more subsequent invocations;        determining by the processor, whether at least one or more of the managed objects is reachable from at least one of the owning pointers; and        marking by the processor, for destruction at least one of the managed objects if one or more of the managed objects is unreachable through at least one or more of the owning pointers or the non - owning pointers.     
     
     
       30. The method as claimed in  claim 29 , further comprising pointing by the processor, one or more ordinary pointers to one or more local objects, the local objects configured to be able to expire before invocations that created the local objects expire. 
     
     
       31. The method as claimed in  claim 29 , further comprising:
   nullifying by the processor, one or more of the non - owning pointers pointing to one or more of the unreachable managed objects if one or more of the unreachable managed objects is destroyed or marked for destruction, or a combination thereof.     
     
     
       32. The method as claimed in  claim 29 , further comprising:
   destroying by the processor, at least one of the managed objects if one or more of the managed objects is unreachable through at least one or more of the owning pointers or the non - owning pointers.     
     
     
       33. The method as claimed in  claim 29 , wherein determining comprises determining whether the managed objects are reachable from at least one of the owning pointers through at least one of the owning pointers or at least one of the non- owning pointers.   
     
     
       34. The method as claimed in  claim 29 , further comprising:
   defining by the processor, classes of the owning pointers or the non - owning pointers, or a combination thereof.     
     
     
       35. The method as claimed in  claim 29 , further comprising:
   defining by the processor, classes of the owning pointers or the non - owning pointers, or a combination thereof; and        restricting by the processor, at least in part, one or more uses of the classes according to one or more rules of a programming language.     
     
     
       36. The method as claimed in  claim 29 , wherein one or more of the invocations comprises a subroutine invocation. 
     
     
       37. The method as claimed in  claim 29 , further comprising:
   sharing by the processor, the managed objects with one or more threads of control within a single process; and        accessing by the processor, a shared memory allocation pool serialized by a lock, the lock being accessible by the one or more threads, managed objects that are shared being allocable to the shared memory allocation pool, wherein the lock is configured to control access to one or more of the managed objects that are shared.     
     
     
       38. The method as claimed in  claim 29 , further comprising:
   sharing by the processor, the managed objects with one or more threads of control within a single process;        accessing by the processor, a shared memory allocation pool serialized by a lock, the lock being accessible by the one or more threads, managed objects that are shared being allocable to the shared memory allocation pool, wherein the lock is configured to control access to one or more of the managed objects that are shared;        defining by the processor, one or more classes of the owning pointer or the non - owning pointers, or a combination thereof; and        restricting by the processor, at least in part, one or more uses of the classes according to one or more rules of a programming language.     
     
     
       39. The method as claimed in  claim 29 , further comprising:
   sharing by the processor, said managed objects with one or more processes within a single system; and        accessing by the processor, a shared memory allocation pool serialized by a lock, the lock being accessible by one or more of the processes, managed objects that are shared being allocable to the shared memory allocation pool, wherein the lock is configured to control access to one or more of the managed objects that are shared.     
     
     
       40. The method as claimed in  claim 29 , further comprising:
   sharing by the processor, said managed objects with one or more processes within a single system;        accessing by the processor, a shared memory allocation pool serialized by a lock, the lock being accessible by one or more of the processes, managed objects that are shared being allocable to the shared memory allocation pool, wherein the lock is configured to control access to one or more of the managed objects that are shared;        defining by the processor, one or more classes of the owning pointers or the non - owning pointers, or a combination thereof; and        restricting by the processor, at least in part, one or more uses of the classes according to one or more rules of a programming language.     
     
     
       41. The method of  claim 29 , wherein the pointing, determining and marking are performed in conjunction with a POSIX®- compliant type file system.   
     
     
       42. A computer memory management system, comprising:
   means for storing one or more managed objects; and        means for maintaining one or more owning pointers or one or more non - owning pointers, or a combination thereof, being capable of pointing to one or more of the managed objects;        wherein one or more of the owning pointers or one or more of the non - owning pointers, or a combination thereof, is configured to point to one or more of the managed objects;        said one or more managed objects are configured to be able to be destroyed if one or more of the managed objects is unreachable through one or more of the owning pointers or the non - owning pointers;        wherein the managed objects are capable of outliving one or more invocations that created the managed objects.     
     
     
       43. The computer memory management system as claimed in  claim 42 , further comprising:
   means for maintaining one or more ordinary pointers configured to point to one or more local objects, wherein the local objects are configured to be able to expire before invocations that created the local objects expire.     
     
     
       44. The computer memory management system as claimed in  claim 42 , wherein one or more of the owning pointers or the non- owning pointers, or a combination thereof, are configured to be able to be nullified if one or more of the unreachable managed objects is destroyed or marked for destruction, or a combination thereof.   
     
     
       45. The computer memory management system as claimed in  claim 42 , further comprising means for one or more invocations configured to access one or more of the managed objects. 
     
     
       46. The computer memory management system as claimed in  claim 42 , further comprising one or more subroutines configured to access one or more of the managed objects. 
     
     
       47. The computer memory management system as claimed in  claim 42 , further comprising a shared memory allocation pool serialized by a lock, wherein the lock is configured to be accessed by one or more threads of control within a process, wherein one or more of the managed objects are allocable to the shared memory allocation pool, and wherein the lock is configured to control access to one or more of the managed objects that are shared. 
     
     
       48. The computer memory management system as claimed in  claim 42 , further comprising means for accessing a shared memory allocation pool serialized by a lock, wherein the lock is configured to be accessible by one or more processes, wherein one or more of the managed objects are allocable to the shared memory allocation pool, and the lock is configured to control access to one or more of the managed objects that are shared. 
     
     
       49. The computer memory management system as claimed in  claim 42 , further comprising a POSIX®- compliant type file system configure to utilize one or more of the managed objects.