Wand: Concurrent Boxing System For All Pointers With Or Without Garbage Collection
First Claim
1. A boxing system for any pointer in a program such that a pointer box accessed by one or more threads or processes can be recycled with no intervening garbage collection.
0 Assignments
0 Petitions
Accused Products
Abstract
Boxed pointers are disclosed, for all pointers, for safe and sequential or parallel use. Since a pointer box can be arbitrarily large, it supports any fat pointer encoding possible. The boxed pointers are managed out of the same heap or stack space as ordinary objects, providing scalability by a shared use of the entire program memory. The boxed pointers and objects are managed together by the same parallel, safe, memory management system including an optional precise, parallel garbage collector. To manage boxes independently of the garbage collector, explicit allocation and de-allocation means are provided including explicit killing of boxes using immediate or deferred frees. The entire system is constructed out of atomic registers as the sole shared memory primitive, avoiding all synchronization primitives and related expenses. Atomic pointer operations including pointer creation or deletion (malloc or free) are provided.
12 Citations
36 Claims
- 1. A boxing system for any pointer in a program such that a pointer box accessed by one or more threads or processes can be recycled with no intervening garbage collection.
- 14. A parallel, safe, memory management system comprising a heap partitioned among threads, boxed pointers, and deferred frees for providing safe manual memory management integrated with an optional precise garbage collector.
- 23. A parallel, work completion consensus system comprising a means for passing a baton round robin among threads till a complete round is made in which no fresh work is recorded by any thread in the baton.
-
25. A tagged union system comprising an object layout or type means for identifying a union containing variable or location, and a boxed means for implementing the union that substitutes the union with a pointer to a box wherein the box specifies the tag of the union and its contents, the contents thereby getting a fully unconstrained storage, despite being placed in a union that occupies the same space as the contents.
- 26. A parallel garbage collection system, that collects in parallel, with each thread collecting its own heap partition, clearing marking work sent to the thread on bounded buffers instantly using a deferred tag, thereby keeping all buffers readily available to work producers so that garbage collection progresses monotonically without deadlock, with completion consensus for works like marking transpiring by baton passing among threads.
- 28. A parallel deferred freeing system comprising a barrier means using which all threads free cached objects in parallel and completion consensus is arrived at by baton passing.
-
31. A boxing method for any pointer in a program such that a pointer box accessed by one or more threads or processes can be recycled with no intervening garbage collection.
-
32. A parallel, safe, memory management method for providing safe manual memory management operations integrated with an optional precise garbage collector, comprising the steps of partitioning heap among threads, boxing pointers, and deferred freeing.
-
33. A parallel, work completion consensus method comprising a step for passing a baton round robin among threads till a complete round is made in which no fresh work is recorded by any thread in the baton.
-
34. A tagged union method comprising an object layout or type step for identifying a union containing variable or location, and a boxing step for implementing the union by substituting the union with a pointer to a box wherein the box specifies the tag of the union and its contents, the contents thereby getting a fully unconstrained storage, despite being placed in a union that occupies the same space as the contents.
-
35. A parallel garbage collection method, that collects in parallel, with each thread collecting its own heap partition, clearing marking work sent to the thread on bounded buffers instantly using a deferred tag, thereby keeping all buffers readily available to work producers so that garbage collection progresses monotonically without deadlock, with completion consensus for works like marking transpiring by baton passing among threads.
-
36. A parallel deferred freeing method comprising a barrier step using which all threads free cached objects in parallel and completion consensus is arrived at by baton passing.
Specification