Systems And Methods Of Memory And Access Management

• US 20150227414A1
• Filed: 08/24/2013
• Published: 08/13/2015
• Est. Priority Date: 08/31/2012
• Status: Abandoned Application

• Current Assignee: Varma, Pradeep
• Original Assignee: Varma, Pradeep
• Inventors: Varma, Pradeep
• Application Number:
  US14/422,628
• Publication Number:
  US 20150227414A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/073 in a memory management context, e.g. virtual memory or cache management memory management G06F12/00; testing of static memory units G11C29/00
• CPC Class Codes: G06F 11/0793 Remedial or corrective actions recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2212/251 Local memory within processor subsystem
• CPC Class Codes: G06F 2212/702 Conservative garbage collection

Abstract

A memory and access management system for reducing memory access errors or management errors or runtime errors while dynamically allocating, moving or de-allocating memory to one or more objects of an application program is disclosed. The object may have a data part containing one or more values and a pointer part containing one or more pointers. The system may include a heap memory pool containing memory space to be assigned to the object and a processor for reading the pointer part. An interface coupled with the processor may be provided for dynamically allocating, moving or de-allocating the data part of the object to defragment, manage or optimize the heap memory pool and updating the address location of the data part contained in one or more pointers upon moving the data part, thereby reducing memory access errors, management errors or runtime errors while allocating, moving or de-allocating memory to the object.

Claims

1. A memory and access management system for reducing both memory access errors and memory management errors for a language with features comprising synchronization-free, atomic pointers comprising atomic dereferencing of a pointer to scalar, the language furthermore featuring manual memory management, automatic memory management, or both, such that pointer metadata tracking by the system for reducing the errors is necessary, the language supporting dynamically allocating, moving or de-allocating memory to one or more objects of an application program, an object having a data part containing one or more values and a pointer part containing one or more pointers, the system comprising:

a heap memory pool containing a memory space to be assigned to an object of the application program;

a processor configured for reading the pointer part of the object and checking access to the object; and

an interface coupled with the processor for dynamically allocating, moving or de-allocating the data part of the object to defragment, manage or optimize the heap memory pool and, updating the address location of the data part contained in one or more pointers in the pointer part upon moving the data part, thereby eliminating all errors comprising inter-object spatial memory access violations, temporal memory access violations, pointers invulnerability violations, and memory management errors for the object.

2. The system of claim 1 wherein the pointer part comprises one or more live pointer, dangling pointer, inbound pointer, out-of-bounds pointer, uninitialized pointer, manufactured pointer or hidden pointer.

3. The system of claim 1 wherein the interface comprises a garbage collector for moving or de-allocating memory to the object.

4. The system of claim 1 wherein the interface comprises a manual management unit including support for allocating or de-allocating memory to the object.

5. The system of claim 3 wherein the garbage collector is a precise garbage collector for moving data part of the object in order to de-fragment the heap memory pool and improve cache or locality performance.

6. The system of claim 3 wherein the garbage collector is a complete conservative garbage collector configured without the object moving functionality and to effectively track the pointer part of the object.

7. The system of claim 3 wherein the garbage collector is a hybrid precise garbage collector with partial object moving functionality and configured to effectively track the pointer part of the object.

8. The system of claim 1 further comprising:

an invulnerability compliance unit for ensuring the pointers are invulnerable;

an access checking unit for ensuring safe memory access; and

a management checking unit for ensuring safe memory management.

9. The system of claim 3 wherein the garbage collector builds or uses a hash table comprising a plurality of buckets for containing lists of live or free objects.

10. The system of claim 1 wherein the pointer of the object is maintained in an encoded state.

11. The system of claim 4 wherein the manual management unit is a substitute to the memory management functions in stdlib.h, section 7.20.3 of the ANSI/ISO C99 manual such that spatially and temporally safe use and management of memory is obtained.

12. The system of claim 1 wherein the system is an automatically managed memory and access system supporting complete manually managed memory standards of C and C++ programming languages.

13. The system of claim 1 wherein the heap memory pool comprises a non-contiguous memory space to be increased or decreased at run-time, based on the needs of the application program.

14. The system of claim 1 wherein the system manages the heap memory pool via an arrangement of management structures, each for a specific allocation size used by the application program.

15. The system of claim 14 wherein the management structures comprises a dsizeof(0) structure where dsizeof(0) is doubleword sizeof(0) and a dsizeof(gh) structure where gh is a gap header and a dsizeof(m) structure where m is a management structure, such that one or more of the structures are created at system initialization time.

16. The system of claim 15 wherein the dsizeof(0) structure is configured for housing an eNULL object whose data size excluding meta-data is 0, the dsizeof(gh) structure contains gap headers on the internal allocated and internal free lists of the dsizeof(gh) structure and the dsizeof(m) structure contains management structures on the internal allocated list of the dsizeof(m) structure.

17. The system of claim 16 wherein outside of paired creation times the total number of free or live gap headers equals the total number of arranged management structures in the heap memory pool at any time.

18. The system of claim 14 wherein the management structures are arranged in a doubly linked sorted-by-size list such that each management structure tracks at least five allocated/free object lists and one gap header (gh) pertinent to allocations of the management structure'"'"'s size.

19. The system of claim 3 wherein the garbage collector is further configured to quarantine the live or free objects having a dangling pointer.

20. The system of claim 18 wherein the gap header points to lists of gaps using fields gaps, fit_nxt, or fit_nxt_nxt wherein fit_nxt and fit_nxt_nxt point to consumable gaps and gaps points to non-consumable gaps.

21. The system of claim 20 wherein an allocation request with an existing management structure uses a free object or a consumable gap on the fit_nxt or fit_nxt_nxt lists unless none exist.

22. The system of claim 20 wherein management structure creation leads to a re-partitioning of the lists of gaps such that consumable-gaps stored on fit_nxt or fit_nxt_nxt lists are maximized.

23. The system of claim 20 wherein all objects and gaps in the heap memory pool are doubleword aligned.

24. The system of claim 20 wherein each gap created from a free object of doubleword size s by a garbage collector can serve allocation requests of doubleword size s among possibly others.

25. The system of claim 1 wherein the object data part comprises a meta-data part, the meta-data part includes one or more fields for storing next and previous links of objects for a doubly-linked object arrangement and, for storing an object layout key, version, size, markers or multi-purpose markers.

26. The system of claim 25 further comprises a hash table built by a garbage collector such that one or more lists of free or live objects stored in the hash table are built by re-using one of the links of the doubly-linked objects in the heap memory pool.

27. The system of claim 1 wherein the one or more pointers are invulnerable pointers, invulnerable encoded pointers, scalar invulnerable encoded pointers or atomic scalar invulnerable encoded pointers.

28. The system of claim 25 wherein the object layout key identifies a layout data structure or a constant to represent that the object does not yet have a layout or the object'"'"'s layout is special, such as for an eNULL object.

29. An invulnerable pointer for identifying an object in a heap memory pool and supporting pointer-to-pointer cast or pointer arithmetic such that the pointer cannot be overwritten by a non-pointer value or read as a non-pointer value.

30. A deferred free operation over an object for manual memory management, the operation comprising the steps of:

saving the object in a cache of objects; and

freeing the cached objects later as a group using barrier synchronization.

31. The operation of claim 30, wherein the barrier synchronization is lock-free.

32. A read-only memory layout for a static type comprising bitwise representation of pointer-sized or pointer-aligned entities including pointer and non-pointer data, with one bit value representing a pointer datum and the other bit value representing non-pointer data.

33. The memory layout of claim 32 wherein the layout is generated by compacting a recognized repeat pattern in the layout into an un-repeated representation.

34. The memory layout of claim 32, wherein the memory layout is represented in a data structure comprising bitstrings of appended combinations of un-repeated bitstring pattern and one or more unrolls of repeat bitstring pattern.

35. Pointer invulnerability compliance checks based on a static type layout of claim 32.

36. The pointer invulnerability compliance checks of claim 35 are carried out dynamically for compliance operations comprising pointer casts, pointer arithmetic and stored pointer reads.

37. The pointer invulnerability compliance checks of claim 36, wherein a dynamic check for a pointer cast are performed in a forward direction, the forward direction includes type void * to type T * where T is not void, and no check is performed in the reverse direction.

38. The pointer invulnerability compliance checks of claim 35 wherein the shared checking occurs when compliance checks or memory access checks can be shifted to a dominating or effectively dominating position.

39. The pointer invulnerability compliance checks of claim 35 are static or dynamic and comprise layout or bitstring or layout key comparisons.

40. The pointer invulnerability compliance checks of claim 35 are optimized if an object'"'"'s layout does not comprise an un-repeated bitstring or if the repeat bitstring is not manifested in the un-repeated bitstring.

41. The pointer invulnerability compliance checks of claim 35 wherein the checks are lock-free.

42. The pointer invulnerability compliance checks of claim 35 wherein the pointer invulnerability checks are shared with memory access checks.

43. The pointer invulnerability compliance checks of claim 35 wherein the shared checking occurs when a compliance check operation dominates a memory access operation or a memory access operation dominates a compliance check operation or a set of one or more compliance check operations effectively dominates a memory access operation or a set of one or more memory access operations effectively dominates a compliance check operation.

44. A method of shielding a vulnerable resource in the heap memory pool, the method comprises the steps of:

storing the vulnerable resource in an object in the heap memory pool; and

representing the vulnerable resource by an invulnerable pointer to the object.

45. The method of claim 44 further comprising storing the resource in a free object in the heap memory pool and referencing the free object by a dangling pointer allowing only special-purpose accesses to the resource through the dangling pointer and disallowing other accesses such as dereferences of the dangling pointer through normal access checking.

46. A method for encoding an un-encoded pointer comprising the steps of:

identifying an object for the un-encoded pointer by searching through a cache of previously decoded pointers'"'"' objects or using the object of a hinted encoded pointer or deferring the identification till a hash table of objects is dynamically constructed; and

using the address location or version of the object to build the encoded pointer.

47. An extended gap structure comprising at least four fields stored at one end of an unused memory block of a heap memory pool comprising:

a first field pointing to the other end of the memory block;

a second field pointing to a list of gaps;

a third and fourth field maintaining a doubly-linked list of gaps according to location-wise sorted order among gaps representing the entire set of unused memory blocks in the heap memory pool.

48. The extended gap structure of claim 47 wherein the extended gaps in a sorted state defragment the heap memory pool by maximizing matched memory allocations that consume an extended gap apiece, and enable linear time coalescing or addition of gaps within a constant-space garbage collector.

49. A probabilistically-applicable deterministic, precise garbage collector comprising:

a precise garbage collector with object moving functionality having a lightweight screening mechanism for determining applicability that decides whether collected putative pointers are also precise pointers.

50. The probabilistically-applicable deterministic, precise garbage collector of claim 49 wherein the lightweight screening mechanism comprises comparing a count of putative pointers that cover all actual pointers with a separately collected count of actual pointers, equality indicating that each putative pointer is an actual pointer.

51. A method for reducing both memory access errors and memory management errors for a language with features comprising synchronization-free, atomic pointers comprising atomic dereferencing of a pointer to scalar, the language furthermore featuring manual memory management, automatic memory management, or both, such that pointer metadata tracking by the system for reducing the errors is necessary, the language supporting dynamically allocating, moving or de-allocating memory to one or more objects of an application program, an object having a data part containing one or more values and a pointer part containing one or more pointers, the method comprising the steps of:

assigning a memory space contained in a heap memory pool to an object of the application program, reading the pointer part of the object and checking access to the object;

dynamically allocating, moving or de-allocating the data part of the object to defragment, manage or optimize the heap memory pool; and

updating the address location of the object'"'"'s data part contained in one or more pointers in the object'"'"'s pointer part upon moving the data part, thereby eliminating all errors comprising inter-object spatial memory access violations, temporal memory access violations, pointer invulnerability violations, and memory management errors for the object.

52. A mark method for a conservative garbage collector, such that the method identifies memory reachable from a root set of an application program, the root set comprising a stack, globals and static data section, and registers for the application program, the mark method comprising the steps of:

identifying putative encoded pointers in the root set;

recognizing a putative encoded pointer as a discovered encoded pointer only if a live or free object in the heap memory pool exists for the putative encoded pointer;

marking a live object pointed by a live putative encoded pointer as reachable memory;

adding marked live objects to the root set; and

repeating the above steps again till the root set stops changing.

53. The method of claim 52, wherein an object in the heap memory pool is marked or traversed only once to identify the reachable memory.

54. The method of claim 52, further comprises tracking a putative encoded pointer effectively by screening the pointer for proper size and alignment, the proper alignment and memory range of the pointer'"'"'s pointed object, the presence of proper markers in the pointed object, the putative validity of the next or previous objects linked from the pointed object, or the equality or non-equality of the pointer and pointed object versions the former of which is indicative of a live pointer to a live object and the latter of which is indicative of a dangling pointer.

55. A recursive formulation of a mark method of a garbage collector, comprising the steps of:

marking an object with a deferred-marking tag for deferring the recursive marking of the object when the recursion depth has exceeded a user-specified bound; and

executing the mark method on the deferred-marking tagged objects.

56. The recursive formulation of claim 55, further comprising:

storing deferred-marking objects in a cache.

57. A method for re-cycling object version in a memory and access management system, the method comprises the steps of:

enumerating locally optimized last version candidates; and

choosing the best last version candidate among locally optimized last version candidates by selecting the candidate with maximum total version space for objects.

58. The method of claim 57 further comprises reusing one of the links of doubly linked objects and a multipurpose marker for computing the best last version candidate.

59. The method of claim 57 further comprising a gap creation method execution before the version-recycling method.

60. The method of claim 57 further comprising reusing one of the links of a doubly linked objects to build a list of sorted versions optionally reusing the hash table of the system.

61. A try block for backward compatibility, such that the try block runs in a scope where free variables comprising pointers consist only of decoded pointers.

62. A mark method for precise garbage collectors (GC), such that the method identifies memory reachable from a root set of an application program, the root set comprising a stack, global and static data section, and registers for the application program, the mark method comprising the steps of:

a. identifying invulnerable, encoded pointers in the root set;

b. marking a live object pointed by a live encoded pointer as reachable memory;

c. adding marked live objects to the root set; and

d. repeating the above steps again till the root set stops changing.

63. The mark method of claim 62 wherein marking an object in the heap memory pool or traversing only once to identify the reachable memory.

64. The mark method of claim 62 further comprising checking an encoded pointer for the pointer'"'"'s version equality with the pointer'"'"'s object version, equality indicating a live encoded pointer to a live object and inequality indicating a dangling pointer.

65. (canceled)

66. A manual memory management system operable in a computing environment comprising a means for deferred freeing of an object, comprising:

a means for saving the object in a cache of objects; and

a means for freeing the cached objects later as a group using barrier synchronization.

67. A conservative garbage collector operable in a computing environment comprising a mark means for identifying memory reachable from a root set of an application program, the root set comprising a stack, globals and static data section, and registers for an application program, the mark means comprising:

a means for identifying putative encoded pointers in the root set;

a means for recognizing a putative encoded pointer as a discovered encoded pointer only if a live or free object in a heap memory pool exists for the putative encoded pointer;

a means for marking a live object pointed by a live discovered encoded pointer as reachable memory;

a means for adding marked live objects to the root set; and

a means for repeatedly applying the above means till the root set stops changing.

68. A garbage collector operable in a computing environment with a recursive marking means comprising:

a means for marking an object with a deferred-marking tag for deferring the recursive marking of the object when the recursion depth exceeds a user-specified bound; and

a means for executing the recursive marking means on the deferred-marking tagged objects.

69. A precise garbage collector operable in a computing environment comprising a mark means for identifying memory reachable from a root set of an application program, the root set comprising a stack, global and static data section, and registers for the application program, the mark means comprising:

a means for identifying invulnerable, encoded pointers in the root set;

a means for marking a live object pointed by a live encoded pointer as reachable memory;

a means for adding marked live objects to the root set; and

a means for repeatedly applying the above means till the root set stops changing.

70. A memory and access management system, for reducing both memory access errors and memory management errors for a language with features comprising synchronization-free, atomic pointers comprising atomic dereferencing of a pointer to scalar, the language furthermore featuring manual memory management, automatic memory management, or both, the language allowing expression of one or more programs containing one or more reducible errors, the language supporting dynamically allocating, moving or de-allocating memory to one or more objects of an application program, an object having a data part containing one or more values and a pointer part containing one or more pointers, the system comprising:

a heap memory pool containing a memory space to be assigned to an object of the application program;

a processor configured for reading the pointer part of the object and checking access to the object; and

an interface coupled with the processor for dynamically allocating, moving or de-allocating the data part of the object to defragment, manage or optimize the heap memory pool and, updating the address location of the data part contained in one or more pointers in the pointer part upon moving the data part, thereby eliminating all errors comprising inter-object spatial memory access violations, temporal memory access violations, pointer invulnerability violations, and memory management errors for the object.