Map
Index
Random
Help
Topics
th

Topic: safe use of pointers

topics > computer science > data > Group: access to data



Group:
memory management

Topic:
access to objects by a path
Topic:
aliasing
Topic:
code optimization by flow analysis
Topic:
concurrency control by monitors
Topic:
dangling pointers
Topic:
error safe systems
Topic:
flavor analysis and typestates for supplementary type checking
Topic:
managing shared memory
Topic:
memory management by garbage collection
Topic:
memory management by regions or memory pool
Topic:
namespace
Topic:
owned resources and data objects
Topic:
pointer rotation
Topic:
pointers to data
Topic:
preventing accidental errors
Topic:
programming without errors
Topic:
recursive data structures
Topic:
referential transparency
Topic:
run-time assertions
Topic:
safety, liveness, and system properties
Topic:
shared objects
Topic:
static single assignment; SSA
Topic:
undefined, null, and other signal values

Summary

Unrestrained use of pointers can wreak havoc in a program. They are controlled by limiting their use to cluster definitions or by using them solely as object references. Pointer references can be limited to dynamically allocated objects or abstract data types. The allowable operations are access, re-assignment, nullify, and equality test. (cbb 5/80)
Subtopic: problems with pointers up

Quote: references have no meaning independent of a particular run of a program; cannot be input or output [»hoarCA_1974]
Quote: references are like jumps, leading wildly from one part of a data structure to another; change can update any location
Quote: object IDs produce a pointer free-for-all as found in prerelational databases
Quote: pointer-linked data structures are error prone due to unconstrained use of pointers [»franRS4_1983]
Quote: C allows pointer beyond end of array; leads to buffer overflow [»jimT6_2002]

Subtopic: pointer analysis up

Quote: CCured identifies safe pointers, sequence pointers that require bounds check, and wild pointers that require a type checks [»necuGC5_2005]
Quote: use binary decision diagrams (BDD) for subset-based points-to analysis; BDDs from model checking; simple, less space, scales well [»bernM6_2003]
Quote: bddbddb generates efficient, binary decision diagrams for stratified Datalog programs; e.g., context-sensitive pointer analysis, side effect analysis, type analysis, and escape analysis [»whalJ6_2004]
Quote: store points-to information as binary decision diagrams in bddbddb; from Whaley and Lam's pointer alias analysis; query with Datalog [»martM10_2005]
Quote: field-based Andersen-style points-to analysis of a million lines of code in under a second [»heinN6_2001]
Quote: points-to analysis with a database, on-the-fly transitive closure, caching of reachability computations, and cycle elimination
Quote: practical algorithm for eliminating null pointer checks in Java; maintains precise exception support; converted to hardware traps [»kawaM11_2000]

Subtopic: abstract data types up

Quote: restrict pointers to implementation of abstract data types; only inside clusters [»berrDM4_1977]

Subtopic: memory or type safety up

Quote: Java guarantees memory and type safety at runtime and compile time; programs cannot forge pointers, overrun arrays, or apply an operator to the wrong type [»hartPH12_2001]
Quote: in ESP, memory safety is a local property of each process; reference counting of link/unlink; communicates immutable, acyclic objects; easily verified by SPIN [»kumaS6_2001]
Quote: ESP makes memory allocation correctness a local property of each process; checked by Spin [»kumaS6_2002]
Quote: detect invalid references by partitioning memory according to its points-to graph; homogeneous pools avoid dangling pointers and run-time checks [»dhurD6_2006]

Subtopic: distributed pointer up

Quote: ESP reference counts for multi-process malloc/free cost 1.5 to 7.4% of messaging costs
Quote: ESP transmits deep copies of immutable objects by incrementing deep reference counts; keeps memory allocation local to a process [»kumaS6_2002]
Quote: traditionally, pointer arguments should be hidden; but communication of names is needed for a process calculus [»milnR1_1993]

Subtopic: capability up

Quote: SPIN capabilities are Modula pointers; pointers cannot be forged or dereferenced incorrectly; minimal overhead [»bersBN12_1995]
Quote: SPIN uses externalized references for user-level access to in-kernal data structures; i.e., index into a per-application table [»bersBN12_1995]
Quote: region-based, capability language tracks unique memory accesses; i.e., non-aliased accesses [»walkD7_2000]

Subtopic: garbage collected references up

Quote: garbage collection is essential for reliability; avoids memory leaks and dangling pointers which are expensive to correct [»goslJ6_1997]
Quote: Oberon's garbage collector must be safe; use type guards, range checks, and NIL tests for all pointers [»wirtN9_1989]
Quote: each Oberon module includes a pointer reference list of all global pointers; used for garbage collection [»wirtN9_1989]
Quote: Cedar reference variable contains address of collectible, single typed, data object; called a REF
Quote: Cedar initializes reference variables to nil; has new operator and garbage collection
Quote: Cedar reference variables can be freely replicated and discarded due to garbage collection [»swinDC7_1985]
Quote: prevent dereferencing a deallocated heap pointer by replacing malloc with a garbage collector [»necuGC5_2005]

Subtopic: reference variable up

Quote: a C++ reference to a type is a synonym for the variable it is initialized to; used for overloaded operators, functions, and both sides of assignments [»stroB_1991]
Quote: a reference is an alias (another name) for an object that already exists prior to the reference's initialization; no null reference, different than a pointer [»dewhSC_2005]

Subtopic: typed reference up

Quote: a reference consists of a descriptive name, a target set (its qualification), and a target (its value or NONE) [»handP_1981]
Quote: a reference type conforms with a variable if it is a reference to the mode of the variable [»bekiH_1971, OK]
Quote: restrict reference variables to a specific type; prevents accessing the incorrect class [»wirtN6_1966]
QuoteRef: branP11_1971 ;; a name is a REF type i.e. a reference to a type
QuoteRef: kiebRB9_1973 ;;2.2 reference to a var produces an object of that type (eg ->real)
QuoteRef: sammJE_1969 ;;566 Declare p pointer, alpha float based (p) means reference to alpha is reference to real number pointed to by p
QuoteRef: wirtN1_1971 ;;38 class: each alloc returns a bound pointer (pointer may be nil
QuoteRef: wirtN7_1973 ;;5 dynamic pointers (access and equality test) to object of one type or nil
QuoteRef: wirtN1_1971 ;;44 class [maximum number of components] of pointer by class type eg p= integer
QuoteRef: demeA3_1979 ;;5 "'Ref, which when applied to a type T, yields a type with a single constant 'nil and no defined ordering.
QuoteRef: sammJE_1969 ;;555 pointer data can only have equality tested no other operations allowed

Subtopic: const ref, read-only type up

Quote: a 'const' reference can be the address of an initialized temporary; allows flexible initialization; useful for function arguments [»stroB_1991]
Quote: Guava methods are read or update; by default, read methods and update constructors [»bacoDF10_2000]
Quote: local read methods in Guava are idempotent unless they return a new value; can replace multiple calls with a single call
Quote: control aliasing through read-only types with read-only methods; does not change the transitive state of an object [»knieG5_2001]

Subtopic: reference pointer up

Quote: restrict stack pointers to call-by-reference; can not store in the heap or globals [»necuGC5_2005]

Subtopic: unique pointer, owned pointer up

Quote: use unique pointers to avoid pointer-induced aliasing; helps encapsulation, reasoning, thread interactions, storage management; practical [»minsNH7_1996]
Quote: CLEAN maintains referential transparency of mutable arguments by guaranteeing unique references; e.g., via a copy
Quote: Guava monitors are always synchronized; other instances are uniquely owned by a single monitor and never need synchronizing [»bacoDF10_2000]
Quote: Guava has a 'move' operator that sets the source to null [»bacoDF10_2000]
Quote: Guava variables assigned to regions with the same owner, i.e., a monitor, value, or no owner for new objects [»bacoDF10_2000]
Quote: Guava parameters may be kept or lent; a lent parameter is not retained; a kept parameter has the same owner as 'this [»bacoDF10_2000]
Quote: Guava methods should return newly allocated objects since they may be linked into any region [»bacoDF10_2000]
Quote: use Flanagan and Abadi's race-free type system to prove that Guava objects are never concurrently accessed [»bacoDF10_2000]
Quote: in Guava every variable has a region type and every method has a region type signature
Quote: memory leak detector based on owning pointers; automatically inferred; a class member always or never owns its pointee at public method boundaries; found errors in binutils and apache [»heinDL6_2003]

Subtopic: balloon type up

Quote: a balloon type explicitly restricts sharing state between types; it helps with reasoning about programs [»almePS6_1997]
Quote: objects of a balloon type can not share internal state with other objects; e.g., primitive data types such as integers and booleans [»almePS6_1997]
Quote: a balloon type has only one static reference, the reference is external, and no external reference to an internal object [»almePS6_1997]
Quote: state variables can not store a reference to a pre-existing balloon object; variables and parameters can store references [»almePS6_1997]
Quote: balloon type checking verifies that only one external reference exists; e.g., free clusters may be captured by only one balloon and captured clusters can not merge [»almePS6_1997]
Quote: an opaque balloon type does not expose references to its internal state; internal state can not change between invocations [»almePS6_1997]

Subtopic: memory region up

Quote: track non-aliasing of memory regions via tagged capabilities and type system [»walkD7_2000]
Quote: uses growable regions for safe, explicit memory allocation without relying on a garbage collector [»jimT6_2002]
Quote: use static, region analysis to prevent dereference of a non-live region; e.g., a block's local variables [»jimT6_2002]

Subtopic: null pointer up

Note: should access to a None object always create one? [»cbb_1990, OK]

Subtopic: temporary alias up

Quote: a borrowed variable (a dynamic alias) is never stored in a field; owned elsewhere; may be used for computation or local variable, but it is never returned [»boylJ5_2001]
Quote: with dynamic aliases there may be data dependencies between writes through a unique field and reads through a dynamic alias [»boylJ5_2001]
Quote: using borrowed variables and annotations, defer read nullification until the variable becomes dead; need annotations on fields and method interfaces [»boylJ5_2001]
Quote: use alias burying to avoid destructive reads of 'read-once' variables; aliases must be dead when reading a unique field of possibly shared objects; static enforcement by restricting aliases across procedure calls [»boylJ5_2001]
Quote: alias burying guarantees that aliases are never used; fields are never null unless explicitly set [»boylJ5_2001]
Quote: for alias burying, annotate parameters, return values, and fields as unique or borrowed; restricts use; need to analyze local variables [»boylJ5_2001]
Quote: alias burying my be used with existing compilers and run-time systems [»boylJ5_2001]
Quote: alias burying requires a complex, intraprocedural analysis; minor source-level changes may lead to confusing error messages

Subtopic: limited aliasing up

Quote: C's 'restrict' annotation splits aliases of p created outside of a procedure from those inside; enables better program checking and optimization [»aikeA6_2003]
Quote: use 'confine' annotation to restrict aliasing of a pointer expression; like 'restrict' over common sub-expression elimination [»aikeA6_2003]
Quote: type and effect system and formal semantics for 'restrict' annotations; O(kn) constraint-based algorithm and O(n^2) inference algorithm [»aikeA6_2003]
Quote: use 'confine' and 'restrict' to track lock state; removed spurious type errors in 138 of 152 device driver modules [»aikeA6_2003]

Subtopic: copy vs. share up

Quote: instead of smart pointers or handles, use copy-on-update for heap structures; duplicate those parts that are changed [»simoAJ10_1998]
Quote: mutable objects may be shared as long as pointer manipulation is disallowed [»liskB_1996]
Quote: Guava uses deep-copying for values and objects within values; does not copy references to monitors
Quote: pass values by reference when source is dead or when neither copy will be updated; e.g., if value has no update methods [»bacoDF10_2000]

Subtopic: swap vs. copy up

Quote: a language should replace copying with swapping, and disallow pointers at the client level [»harmDE5_1991]
Quote: under swapping style, a procedure call swaps arguments with parameters at entry and exit [»harmDE5_1991]
Quote: semantics differ for copying pointers and values; swapping is both efficient and consistent [»harmDE5_1991]
Quote: assignment by replica() assigns a copy of the parameter; example of function assignment swapping the result [»harmDE5_1991]

Subtopic: safe pointer, fat pointer up

Quote: check all pointer and array accesses with an extended safe pointer representation; 2-6x time cost, less than 2x space cost [»austTM6_1994]
Quote: safe pointer representation with base address, size, storage class, and liveness property; check all accesses with unnecessary checks avoided via runtime tests [»austTM6_1994]
Quote: Cyclone has never-NULL pointers (@...) and fat pointers (?...) with run-time checking (e.g., varargs) [»jimT6_2002]
Quote: convert C to Cyclone by changing less than 10% of lines; 20-50% of these are fat pointers (?...) [»jimT6_2002]
Quote: Simula provides safe reference by separating reference from the thing itself; e.g., queue elements have succ, pred, out, and into [»nygaK10_1983, OK]
Quote: SafeTSA includes safe-ref that cannot be null, and safe-index-arr that cannot be out of range; via runtime checks [»ammeW6_2001]
Quote: Cedar's safe pointers ensure integrity of system data structures and code [»swinDC7_1985]
Quote: a pointer to a zero-terminated array is safe as long as the pointer only moves inside the array and the terminator is safe [»jimT6_2002]

Subtopic: locking up

Quote: global methods in Guava might acquire a lock; maybe not idempotent; if also update, can not use from read methods [»bacoDF10_2000]
Quote: Guava avoids lock fields in object headers; only monitors require locks [»bacoDF10_2000]

Subtopic: runtime type checking up

Quote: a Cedar REF ANY variable requires runtime type verification before access or modification [»swinDC7_1985]
Quote: data structures of different extended types that use the same base type [»wirtN7_1988]
Quote: add padding between allocated blocks to avoid pointer jumping from one block to another; like Purify [»logiA4_2001]
Quote: run-time checks of actual types; unallocated, uninitialized, integral, real, and pointer; shows exact location of errors; 20x slower
[»logiA4_2001]

Related Topics up

Group: memory management   (11 topics, 367 quotes)

Topic: access to objects by a path (13 items)
Topic: aliasing (28 items)
Topic: code optimization by flow analysis (47 items)
Topic: concurrency control by monitors (24 items)
Topic: dangling pointers (13 items)
Topic: error safe systems (76 items)
Topic: flavor analysis and typestates for supplementary type checking (68 items)
Topic: managing shared memory (74 items)
Topic: memory management by garbage collection (116 items)
Topic: memory management by regions or memory pool (17 items)
Topic: namespace (19 items)
Topic: owned resources and data objects (12 items)
Topic: pointer rotation (11 items)
Topic: pointers to data (55 items)
Topic: preventing accidental errors (37 items)
Topic: programming without errors (28 items)
Topic: recursive data structures (18 items)
Topic: referential transparency (26 items)
Topic: run-time assertions (25 items)
Topic: safety, liveness, and system properties (22 items)
Topic: shared objects (13 items)
Topic: static single assignment; SSA (19 items)
Topic: undefined, null, and other signal values
(34 items)


Updated barberCB 11/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.