Leveraging garbage collection to dynamically infer heap...

Details Leveraging garbage collection to dynamically infer heap... Leveraging garbage collection to dynamically infer heap...

2011-03-22

2011-03-22

Cottingham, John R. (Department: 2167)

Data processing: database and file management or data structures

Garbage collection

C707S821000

Reexamination Certificate

active

07912877

ABSTRACT:
A program analysis tool leverages the garbage collection process to dynamically infer invariants of objects or data structures created by a program on the heap during execution. During execution of the program in a garbage-collected execution environment, the program analysis tool tracks object allocations made by the program, and records some meta data relating to invariants tracked for the type of the object, which are initially assumed satisfied by the object. Whenever a garbage collection pass visits the object, the tool checks whether the object still satisfies the invariants, and updates the meta data accordingly. The tool finally reports the invariants reflected by the meta data upon the object's death or at termination of the program. The invariants can then be used to annotate the program source code and/or detect bugs that violate the invariants.

REFERENCES:
patent: 4862373 (1989-08-01), Meng
patent: 5220667 (1993-06-01), Ichieda
patent: 5333311 (1994-07-01), Whipple, II
patent: 5713008 (1998-01-01), Falkner
patent: 5740443 (1998-04-01), Carini
patent: 5774685 (1998-06-01), Dubey
patent: 5815720 (1998-09-01), Buzbee
patent: 5909578 (1999-06-01), Buzbee
patent: 5925100 (1999-07-01), Drewry et al.
patent: 5940618 (1999-08-01), Blandy et al.
patent: 5950003 (1999-09-01), Kaneshiro et al.
patent: 5950007 (1999-09-01), Nishiyama et al.
patent: 5953524 (1999-09-01), Meng et al.
patent: 5960198 (1999-09-01), Roediger et al.
patent: 6026234 (2000-02-01), Hanson et al.
patent: 6073232 (2000-06-01), Kroeker et al.
patent: 6079032 (2000-06-01), Peri
patent: 6145121 (2000-11-01), Levy et al.
patent: 6148437 (2000-11-01), Shah et al.
patent: 6189036 (2001-02-01), Kao
patent: 6216219 (2001-04-01), Cai et al.
patent: 6233678 (2001-05-01), Bala
patent: 6311260 (2001-10-01), Stone et al.
patent: 6321240 (2001-11-01), Chilimbi et al.
patent: 6330556 (2001-12-01), Chilimbi et al.
patent: 6360361 (2002-03-01), Larus et al.
patent: 6370684 (2002-04-01), De Pauw et al.
patent: 6381735 (2002-04-01), Hunt
patent: 6404455 (2002-06-01), Ito et al.
patent: 6446257 (2002-09-01), Pradhan et al.
patent: 6560693 (2003-05-01), Puzak et al.
patent: 6560773 (2003-05-01), Alexander et al.
patent: 6571318 (2003-05-01), Sander et al.
patent: 6598141 (2003-07-01), Dussud et al.
patent: 6628835 (2003-09-01), Brill et al.
patent: 6651243 (2003-11-01), Berry et al.
patent: 6658652 (2003-12-01), Alexander et al.
patent: 6675374 (2004-01-01), Pieper et al.
patent: 6704860 (2004-03-01), Moore
patent: 6738968 (2004-05-01), Bosworth et al.
patent: 6848029 (2005-01-01), Coldewey
patent: 6886167 (2005-04-01), Breslau et al.
patent: 6904590 (2005-06-01), Ball et al.
patent: 6951015 (2005-09-01), Thompson
patent: 6957422 (2005-10-01), Hunt
patent: 7032217 (2006-04-01), Wu
patent: 7058936 (2006-06-01), Chilimbi et al.
patent: 7140008 (2006-11-01), Chilimbi et al.
patent: 7159038 (2007-01-01), Rychlicki
patent: 7181730 (2007-02-01), Pitsianis et al.
patent: 7293260 (2007-11-01), Dmitriev
patent: 7296180 (2007-11-01), Waterhouse et al.
patent: 7343598 (2008-03-01), Chilimbi et al.
patent: 7401324 (2008-07-01), Dmitriev
patent: 7506317 (2009-03-01), Liang et al.
patent: 7587709 (2009-09-01), Chilimbi et al.
patent: 7607119 (2009-10-01), Chilimbi et al.
patent: 7770153 (2010-08-01), Chilimbi et al.
patent: 2002/0133639 (2002-09-01), Breslau et al.
patent: 2002/0144245 (2002-10-01), Lueh
patent: 2002/0178401 (2002-11-01), Ball et al.
patent: 2003/0145314 (2003-07-01), Nguyen et al.
patent: 2003/0204840 (2003-10-01), Wu
patent: 2004/0015897 (2004-01-01), Thompson et al.
patent: 2004/0015930 (2004-01-01), Wu
patent: 2004/0025145 (2004-02-01), Dawson
patent: 2004/0078381 (2004-04-01), Blandy et al.
patent: 2004/0088699 (2004-05-01), Suresh
patent: 2004/0103401 (2004-05-01), Chilimbi et al.
patent: 2004/0103408 (2004-05-01), Chilimbi et al.
patent: 2004/0111444 (2004-06-01), Garthwaite
patent: 2004/0133556 (2004-07-01), Wolczko et al.
patent: 2004/0181782 (2004-09-01), Findeisen
patent: 2004/0215880 (2004-10-01), Chilimbi et al.
patent: 2004/0216091 (2004-10-01), Groeschel
patent: 2005/0086648 (2005-04-01), Andrews et al.
patent: 2005/0091645 (2005-04-01), Chilimbi et al.
patent: 2005/0149904 (2005-07-01), Ball et al.
patent: 2005/0182603 (2005-08-01), Freitas et al.
patent: 2005/0235257 (2005-10-01), Ball et al.
patent: 2005/0246696 (2005-11-01), Alexander et al.
patent: 2006/0070040 (2006-03-01), Chilimbi et al.
patent: 2006/0155791 (2006-07-01), Tene et al.
patent: 2006/0242636 (2006-10-01), Chilimbi et al.
patent: 2006/0265438 (2006-11-01), Shankar et al.
patent: 2006/0265694 (2006-11-01), Chilimbi et al.
patent: 2007/0083856 (2007-04-01), Chilimbi et al.
patent: 2007/0169000 (2007-07-01), Havin et al.
patent: 2007/0244942 (2007-10-01), McCamant et al.
patent: 2008/0005208 (2008-01-01), Vaswani et al.
Chen, Hao. “Using build integrated static checking to preserve correctness invariants,” ACM, Oct. 2004.
Bacon, David. “A unified theory of garbage collection,” ACM, Oct. 2004.
Ball et al., “Generating Abstract Explanations of Suprious Counterexamples in C Programs,” Technical Report MSR-TR-2002-09, 13 pages, Jan. 22, 2002.
Zorn et al., “A Memory Allocation Profiler for C and Lisp Programs,” published Feb. 16, 1988, pp. 1-18.
English et al., “Loge: a self-organizing disk controller,”Proc. USENIX Winter 1992 Tech. Conf., San Francisco, pp. 237-251 (Jan. 1992).
Hatfield et al., “Program Restructuring for Virtual Memory,”IBM Sys. J., No. 3, pp. 168-192 (1971).
Kroeger et al., “Predicting Future File-system Actions from Prior Events,”Proc. USENIX Annual Tech. Conf., San Diego, pp. 1-10 (Jan. 1996).
Palmer et al., “Fido: A Cache that Learns to Fetch,”Proc. 17th Int'l Conf. on Very Large Databases, Barcelona, pp. 255-264 (Sep. 1991).
Patterson et al., “Informed Prefetching and Caching,”Proc. 15th ACM Symp. on Operating System Principles, Copper Mountain Resort, CO, pp. 79-95 (Dec. 1995).
Staelin et al., “Smart Filesystems,”Proc. USENIX—Winter '91, Dallas, TX, pp. 45-51 (1991).
Tait et al., “Detection and Exploitation of File Working Sets,”IEEE, pp. 2-9 (1991).
U.S. Appl. No. 11/134,812, filed May 20, 2005, Ganapathy et al.
U.S. Appl. No. 11/115,924, filed Apr. 26, 2005, Chilimbi et al.
Ammons et al., “Exploiting Hardware Performance Counters with Flow and Context Sensitive Profiling”, PLDI (Jun. 1997), 12 pages.
Ammons et al., “Improving Data-Flow Analysis with Path Profiles,”SIGPLAN '98(1998), pp. 72-84.
Anderson et al., “Continuous Profiling: Where Have All the Cycles Gone?”, ACM (Nov. 1997), pp. 357-390.
Annavaram et al., “Data Prefetching by Dependence Graph Precomputation”, IEEE (2001), pp. 52-61.
Arnold et al., “A Framework for Reducing the Cost of Instrumented Code”,Rutgers University Technical Report DCS-TR-424(Nov. 2000), pp. 1-10.
Bala et al., “Dynamo: A Transparent Dynamic Optimization System”, ACM (2000), pp. 1-12.
Ball et al., “Efficient Path Profiling”, IEEE (1996), pp. 46-57.
Berger et al., “Composing High-Performance Memory Allocators”, ACM (2001), 11 pages.
Cahoon et al., “Data Flow Analysis for Software Prefetching Linked Data Structures in Java”, IEEE (2001), 12 pages.
Calder et al., “Cache-Conscious Data Placement”, ACM (1998), 11 pages.
Chen et al., “Reducing Memory Latency via Non-Blocking and Prefetching Caches”, ACM (1992), pp. 51-61.
Chilimbi et al., “Cache-Conscious Structure Definition”,Proceedings of the ACM SIGPLAN '99(May 1999) 12 pages.
Chilimbi et al., “Cache-Conscious Structure Layout”,Proc. ACM SIGPLAN '99 Conf. on Programming Language Design and Impl., (May 1999), 12 pages.
Chilimbi et al., “Dynamic Hot Data Stream Prefetching for General-Purpose Programs”, ACM (2002), 11 pages.
Chilimbi, “Efficient Representations and Abstractions for Qua

Affiliated with

Also associated with

Rating

Leveraging garbage collection to dynamically infer heap... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Leveraging garbage collection to dynamically infer heap..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Leveraging garbage collection to dynamically infer heap... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2671148