next up previous index
Next: Complement Arcs Up: Programmer's Manual Previous: Compiling and Linking

Reference Counts


Garbage  collection in the CUDD package is based on reference counts. Each node stores the sum of the external references and internal references. An internal BDD or ADD node is created by a call to cuddUniqueInter , an internal ZDD node is created by a call to cuddUniqueInterZdd , and a terminal  node is created by a call to cuddUniqueConst . If the node returned by these functions is new, its reference count is zero. The function that calls cuddUniqueInter , cuddUniqueInterZdd , or cuddUniqueConst  is responsible for increasing the reference count of the node. This is accomplished by calling Cudd_Ref .

When a function is no longer needed by an application, the memory used by its diagram can be recycled by calling Cudd_RecursiveDeref  (BDDs and ADDs) or Cudd_RecursiveDerefZdd  (ZDDs). These functions decrease the reference   count of the node passed to them. If the reference count becomes 0, then two things happen:

  1. The node is declared ``dead ;" this entails increasing the counters  of the dead nodes. (One counter for the subtable  to which the node belongs, and one global counter for the unique  table to which the node belongs.) The node itself is not affected.
  2. The function is recursively called on the two children of the node.
For instance, if the diagram of a function does not share any nodes with other diagrams, then calling Cudd_RecursiveDeref  or Cudd_RecursiveDerefZdd  on its root will cause all the nodes of the diagram to become dead.

When the number of dead nodes reaches a given level (dynamically determined by the package) garbage collection takes place. During garbage  collection dead nodes are returned to the node free list .

When a new node is created, it is important to increase its reference  count before one of the two following events occurs:

  1. A call to cuddUniqueInter , to cuddUniqueInterZdd , to cuddUniqueConst , or to a function that may eventually cause a call to them.
  2. A call to Cudd_RecursiveDeref , to Cudd_RecursiveDerefZdd , or to a function that may eventually cause a call to it.
In practice, it is recommended to increase the reference count as soon as the returned pointer has been tested for not being NULL.

NULL Return Values


The interface to the memory management functions (e.g., malloc) used by CUDD intercepts NULL return values and calls a handler. The default handler exits with an error message. If the application does not install another handler, therefore, a NULL return value from an exported function of CUDD signals an internal error.

If the aplication, however, installs another handler that lets execution continue, a NULL pointer returned by an exported function typically indicates that the process has run out of memory. Cudd_ReadErrorCode  can be used to ascertain the nature of the problem.

An application that tests for the result being NULL can try some remedial action, if it runs out of memory. For instance, it may free some memory that is not strictly necessary, or try a slower algorithm that takes less space. As an example, CUDD overrides the default handler when trying to enlarge the cache or increase the number of slots of the unique table. If the allocation fails, the package prints out a message and continues without resizing the cache.


Cudd_RecursiveDeref vs.


It is often the case that a recursive procedure has to protect the result it is going to return, while it disposes of intermediate results. (See the previous discussion on when to increase reference counts.) Once the intermediate results have been properly disposed of, the final result must be returned to its pristine state, in which the root node may have a reference count of 0. One cannot use Cudd_RecursiveDeref  (or Cudd_RecursiveDerefZdd) for this purpose, because it may erroneously make some nodes dead. Therefore, the package provides a different function: Cudd_Deref . This function is not recursive, and does not change the dead node counts. Its use is almost exclusively the one just described: Decreasing the reference count of the root of the final result before returning from a recursive procedure.

When Increasing the Reference Count is Unnecessary


When a copy of a predefined constant  or of a simple BDD variable is needed for comparison purposes, then calling Cudd_Ref  is not necessary, because these simple functions are guaranteed to have reference counts greater than 0 at all times. If no call to Cudd_Ref is made, then no attempt to free the diagram by calling Cudd_RecursiveDeref  or Cudd_RecursiveDerefZdd  should be made.

Saturating Increments and Decrements


On 32-bit machines, the CUDD package stores the reference  counts in unsigned short int's. For large diagrams, it is possible for some reference counts to exceed the capacity of an unsigned short int. Therefore, increments and decrements of reference counts are saturating. This means that once a reference count has reached the maximum possible value, it is no longer changed by calls to Cudd_Ref, Cudd_RecursiveDeref , Cudd_RecursiveDerefZdd , or Cudd_Deref . As a consequence, some nodes that have no references may not be declared dead. This may result in a small waste of memory, which is normally more than offset by the reduction in size of the node structure.

When using 64-bit pointers, there is normally no memory advantage from using short int's instead of int's in a DdNode. Therefore, increments and decrements are not saturating in that case. What option is in effect depends on two macros, SIZEOF_VOID_P  and SIZEOF_INT , defined in the external header  file (cudd.h ). The increments and decrements of the reference counts are performed using two macros: cuddSatInc  and cuddSatDec , whose definitions depend on SIZEOF_VOID_P  and SIZEOF_INT .

next up previous index
Next: Complement Arcs Up: Programmer's Manual Previous: Compiling and Linking

Fabio Somenzi
Tue May 12 18:47:58 MDT 1998