|
Bugs might be present in this code which
I haven't noticed yet. I use this code a lot, but it's tested little.
The main idea of this page is to show refcounting
style using handles in the form of smartrefs (done
as templates in this API).
Many code comments have
been removed and shortened to reduce the display size on this page.
The following types
are used in this interface. Class yn is a node
base class for all refcounted objects if you want both
weak and strong
refs handled by yht<n> handle
smartrefs (which merely wrap base yh0 handle behavior).
typedef unsigned char u8; // 8 bit unsigned int
typedef unsigned short u16; // 16 bit unsigned int
typedef unsigned long u32; // 32 bit unsigned int
typedef long i32; // 32 bit signed int
class yo; // outstream
class yn; // refcounted node
class yh0; // non-template handle base
template <class N> class yht; // handle template
typedef yht<yn> ynh; // ref to any node subclass
The following trivial
template only exists to give a unique type to expression
ycite(foo) so operators can be overloaded
to accept ywee<Foo> as a printable source.
template <typename T> struct ywee { // T wrapper
// "wee" is a shorter word for "tiny"
T const& w_t; // just a reference to T
ywee(T const& t) : w_t(t) { } // trivial wrapper
};
// wee wrapper for T requests cite rather than dump
template <typename T> ywee<T>
ycite(T const& t) { return ywee<T>(t); }
(The definition of
ycite() is only provided to explain how you'd
manage to call yn::ncite() using an inline
convenience operator<<() shown later.)
Handle base class
yh0 is the unusual part of this refcounting
scheme: all refcounting is done by yh0
alone as a side effect of assigning nodes to handles. Only
yh0 has permission to call node methods
changing the refcount.
A node
lives only as long as at least one handle still has a ref to it.
Class
yh0
begins with enum EHabit defining the 16-bit
magic values for weak and strong references.
class yh0 { // base handle to node
public:
enum EHabit { // handle kind: weak or strong
e_hweak = 0x774b /*'wK'*/,
e_hstrong = 0x5374 /*'St'*/,
e_hdead = 0xdead /* destroyed */
};
The enum values
for weak and strong are passed to yh0
constructors to say whether any given handle holds only
weak or strong refs.
Copy construction
is not allowed, and the state of a handle can only be intialized
or changed using _hsetn() to set the current
node pointer.
private: // cannot be copied this way:
yh0(const yh0&); yh0& operator=(const yh0&);
protected:
void _hsetn(yn* n); // release old, assign new n
// constructors used only called by yht template:
// \brief refs default to strong (both ref & use)
explicit yh0(EHabit habit=e_hstrong); // NIL ref
explicit yh0(yn* n, EHabit habit=e_hstrong);
~yh0() { h_habit = e_hdead; }
The last two constructors
are only used by the yht<node>
template farther below. The explicit keyword
ensures a node pointer can never be implicitly promoted to a handle.
You must mention a constructor name explicitly get get a handle
constructed.
Handle members are
protected so only yht<node> can use them.
protected: // yh0 member variables
yn* h_n; // main purpose of yh0: refcounted ptr
#ifdef USE_AUDIT_NODE_BT
ybt* h_bt; // backtrace for ref leak auditing
#endif /*USE_AUDIT_NODE_BT*/
u16 h_habit; // either e_hweak or e_hstrong
u8 h_gen; // copy of h_n->n_gen gen number
u8 h_pad; // one byte reserved for future use
friend class yn; // yn adds first ref by _hsetn()
// First node ref must allow zero start values.
Not shown here is
any backtrace state used for auditing refcount leaks. Note if a handle
has a backtrace taken at node addref() time, this
backtrace follows a node ref wherever it goes. So swapping
node pointers in two handles also swaps backtraces.
Handles allow public
node and ref strength access.
typedef EHabit h_t;
public: // getters checking state of this handle
yn* hn() const; // \return h_n (but check for nil 1st)
const char* hhabit() const; // habit as static string
bool hdead() const { return e_hdead == (h_t)h_habit; }
bool hweak() const { return e_hweak == (h_t)h_habit; }
bool hstrong() const { return e_hstrong==(h_t)h_habit; }
void hbadhabit() const; // log error on bad h_habit
// \return true if h_n is good (and h_gen==h_n->n_gen)
bool hgood() const; // true if ref & h_n BOTH look good
// returns true if h_n is nil, or failing that, if all
// these are true: h_n->nfine() & h_n->ngood().
}; // class yh0
The
hgood() method checks whether the handle looks
valid (possibly asserting when not). After a handle destructor has
run, hdead() returns true.
yh0 printing
¶
Printing support for
handles and nodes is not shown here. (The API would be twice a big.)
handle template
¶
The
yht<node> template class is defined after
the yn node class so the node
API is known.
The
yn base class for refcounted nodes
has two different count member variables when both weak
and strong refs are supported. A strong ref increments
both n_refs and
n_uses, while a weak ref increments
only n_refs. (If weak refs are not
needed, you can discard n_uses.)
Values of
n_refs and n_uses only change
as a side effect of references nodes from handles
(incrementing counts), or of
removing node refs from handles (decrementing counts).
When n_refs
hits zero, a node is "destroyed" by calling virtual
nzeroRefs() which defaults to deletion.
When n_uses hits zero a node is "shutdown" by calling
virtual nzeroUses(), and this always happens
before n_refs hits zero, because uses are
always decremented first. (So the refcount is guaranteed nonzero
when a node shuts down.) Among other things,
nzeroUses() should release all other refs by putting
nil into any child handles.
class yn { // node base refcounting
private: // cannot copy refcounted objects this way:
yn(const yn&); yn& operator=(const yn&); // no copy
private: // NOT protected (subclasses cannot change)
// number of refs (maybe changed atomically)
i32 n_refs; // the number of REFs to this object
i32 n_uses; // the number of USEs of this object
enum {
e_nlive = 'n',
e_ndead = '~',
e_natomic = 'a', /*some specific nonzero value*/
e_nmutable = 'm', // not readonly
e_nfrozen = 'R' // readonly
};
u8 n_tag; // tag: must equal e_nlive
u8 n_frozen; // indicates mutable or readonly
u8 n_atomic; // change n_refs & n_uses atomically?
u8 n_gen; // 8-bit gen: constant for lifetime
static u8 _nrandgen(); // byte from random sequence
The last four bytes
of node state are metainfo.
n_tag shows absence of corruption (and destruction)
if equal to e_nlive. The value of
n_gen is initialized to pseudo random byte from
_nrandgen() and never changes until a node is
destroyed. Handles copy n_gen to detect early
change in node state before all refs are gone.
Whether to change
counts atomically for thread-safety is indicated by
n_atomic, which remains equal to
e_natomic if it ever gets that value.
The n_frozen byte can be used to manage
cooperative dynamic mutability control.
yn
¶
construction & getters
Constructing a node
normally requires a handle to create a first ref, because
we never want a node to "float" with zero refs
just after construction. So yn assigns itself
to the handle arg before construction ends. The best constructor
never makes nodes with an initial zero ref count.
However, absence of
an empty constructor makes life difficult in some situations.
(We would be unable to create arrays of nodes, for example —
which is actually okay, since nodes must have lifetimes
independent of one another. It's arrays of handles you
want to make, not arrays of nodes.)
So an empty constructor exists which makes a node with zero
starting refs, until that node is first assigned to a handle.
Use of the empty constructor is strongly discouraged but not
forbidden when impossible to avoid.
public: // yn constructors & getters
// \brief BEST constructor: 1st ref to yn in handle
explicit yn(yh0& handle); // refs=1 uses=1
// \brief make yn w/ zero refs & zero uses
yn(); // refs=0, uses=0 til first handle
bool nlive() const { return e_nlive == n_tag; }
void ndead() const; // log when not good or not fine
void nbadgen(int expected) const; // log bad n_gen
// \return whether good only after avoiding nil deref:
bool nfine() const { // better than just 'good'
// \return whether this, refs, & tag are okay:
return (1024 < (u32) this // not nil or near nil
&& e_nlive == n_tag // must have good tag
&& n_refs > 0 // must have refs
&& n_refs >= n_uses); // all uses need ref
}
public: // misc node getters
struct Nid { int n_id; Nid(int x) : n_id(x) { } };
u8 ngen() const { return n_gen; } // node's gen
i32 nrefs() const { return n_refs; } // (unsafe peek)
i32 nuses() const { return n_uses; } // (unsafe peek)
bool nusable() const { return n_uses > 0; } // not atomic
bool natomic() const { return e_natomic == n_atomic; }
bool nmutable() const { return e_nmutable == n_frozen; }
bool nreadonly() const { return e_nfrozen == n_frozen; }
// once atomic, can't safely go non-atomic again:
void nfreeze() { n_frozen = e_nfrozen; }
void nsetatomic() { n_atomic = e_natomic; }
bool nownersPlus(i32 N) const { // cow needed?
// if atomic, can't know if ++n_refs is pending:
return n_refs > N || e_natomic == n_atomic;
}
bool ncowNeed() const { // need copy-on-write?
return n_refs > 1 || e_nfrozen == n_frozen;
}
bool ncowNeed(i32 x) const { // need copy-on-write?
return n_refs > x || e_nfrozen == n_frozen;
}
virtual const char* nclass() const { return "yn"; }
Some node
getters report whether a node looks valid. Others check node
metainfo. Some experimental copy-on-write support is present
here, but it's only half-baked, and can be ignored.
(Additional copy-on-write virtual method support for cloning nodes
has been elided from this interface, since it doesn't affect
refcounting much per se.)
Internal nodes methods
alter counts and check validity:
private: // yn internals
friend class yh0; // only yh0 changes n_refs & n_uses
void _bad_atomic() const; // not 0 nor e_natomic
bool _add_strong(); // +strong ref (++n_refs & ++n_uses)
bool _add_weak(); // +weak ref (++n_refs only)
// \param gen is caller's copy of the expected gen
void _sub_strong(u8 gen); // strong (--n_uses, --n_refs)
void _sub_weak(u8 gen); // weak (--n_refs)
protected:
// \return whether good for 1st ref (n_refs can be ZERO):
bool _fine_node() const { // better than just 'good'
// \return whether address, refs, & tag are okay:
return (1024 < (u32) this // cannot be nil or near nil
&& e_nlive == n_tag // must have good tag
&& n_refs >= 0 // cannot be neg (zero okay)
&& n_refs >= n_uses); // all uses must have a ref
}
The internal
version of _fine_node() tolerates refs
equal to zero, since this must be okay when a node is first
assigned to the handle provided at construction time.
Virtual methods
below need overriding in subclasses when appropriate.
protected:
// called ONLY from _sub_weak() or _sub_strong()
// \brief override to 'stop' when uses hit zero:
virtual void nzeroUses(); // called on --n_uses == 0
// \brief called to notify subclass when refs hit zero:
virtual void nzeroRefs(); // called on --n_refs == 0
public: // virtual methods (or using virtual methods)
// \return true if subclass looks valid
virtual bool ngood() const; // looks valid?
virtual void ndumpf(FILE* f) const; // debug-print
virtual void nout(yo& o) const; // node content
virtual void ndump(yo& o) const; // debug-print
virtual void ncite(yo& o) const; // one line print
void nprint() const; // { ndump(stdout); } // for gdb
void npr() const; // { ncite(stdout); } // for gdb
struct Nq { // unique type for quote() to return
yn const& q_n; Nq(yn const& n): q_n(n) { }
};
Nq quote() const { return Nq(*this); } // quoted node
protected: // delete ONLY from nzeroRefs()
// \brief must be protected so subclasses can call:
virtual ~yn(); // called when n_refs goes to zero
}; // class yn
// gratuitous examples of convenience print operators
inline yo& operator<<(yo& o, yn& n) {
n.nout(o); return o; // node content only
}
inline yo& operator<<(yo& o, yn::Nq const& x) {
x.q_n.ndump(o); return o; // full print of node
}
inline yo& operator<<(yo& o, ywee<yn> const& x) {
x.w_t.ncite(o); return o; // node as single line
}
Note the
node destructor ~yn() is protected because it
must never be called explicitly -- node instances can never be
deleted manually, since this must occur only when from
nzeroRefs() when n_refs
hits zero. Also node subclasses must also declare destructors
protected, for the same reasons. (Nodes cannot be stack
allocated, because their lifetime must be driven by
count of node refs.)
yn printing
¶
Althrough the abstract
node printing API is shown here, the yo
outstream class will not be described. Dumping a node in
with ndump() prints a node in full while
ncite() is required to write a single line
only. (Among other things, this allows cycles to be printed
safely by citation when ncite() does not
print children to recurse.) Use nout()
to write a node's content instead of a node description.
Template
yht<N> is a handle template
smartref to yn node subclass N.
In other words, even though base handle yh0
does all the work, you should use a type specific smartref
for better type-safety, and in order to get convenient behavior
like smart pointer dereferencing via
operator->().
Note because
yht<N> is a public subclass of
yh0, you can pass a templated handle to
the yn constructor, which is what every subclass
of yn will do. (For better type-safety,
constructors for each node subclass N
should define a
N::N(yht<N>& h)
constructor instead of
N::N(yh0&)), but they will pass
arg h into yn::yn(yh0&).)
template <class N> // typesafety specific to class N
class yht : public yh0 { // yh0 handles basic work
public: // NOTE: once constructed, habit never changes
explicit yht(EHabit h=e_hstrong) : yh0(h) { } // nil
explicit yht(N* p, EHabit h=e_hstrong) : yh0(p, h) { }
The two constructors above
simply call yh0 constructors inline. Nothing is
added here but type safety.
~yht() { this->_hsetn(0); }
yht& operator=(y1nil const&) {
this->_hsetn(0); return *this;
}
The destructor assigns
nil to the pointer, releasing an old node ref, if any. Assigning
ynil (of type y1nil) does
the same thing. (Additionally of course, the destructor make
the handle invalid for future use in base ~yh0().)
yht<N>& operator=(const yht& rhs) { // assign same type:
this->_hsetn(rhs.h_n); return *this; // replace ref
}
// \brief assign from pointer to N:
yht<N>& operator=(N* p) { // same as hset() below
this->_hsetn(p); return *this; // replace ref
}
// \brief assign from ref to another type:
template <class X> yht<N>&
operator=(const yht<X>& rhs) {
this->_hsetn(rhs.h_n); return *this; // replace ref
}
Assignment always just
calls inherited yh0::_hsetn(). This is just C++
games for different type signatures.
// \brief construct from ref to another type:
template <class X> yht(const yht<X>& o) : yh0(o.h_n) { }
template <class X> yht(const yht<X>& o, EHabit k)
: yh0(o.h_n, k) { }
yht(const yht& rhs) : yh0(rhs.h_n) { } // same type:
yht(const yht& rhs, EHabit k) : yh0(rhs.h_n, k) { }
Constructors always just
call the base yh0 constructor. This is just C++
games for different type signatures.
// \brief assign a new N (same as operator=(N*))
void hset(N* rhs) { this->_hsetn(rhs); }
// \brief assign nil pointer (release old ref)
void hclear() { this->_hsetn(0); } // zero old ref
These are alternate ways
to assign pointers, only using explicitly named methods.
// \return not nil
operator bool() const { return 0 != h_n; }
// \return current value of h_n (without nil check)
operator N*() const { return (N*)h_n; }
You can cast the node
pointer in a handle to bool or a node pointer. So a handle acts like
a node pointer and implicitly converts to one. You can test a handle
for nil this way, trivially, by seeing whether it is equal to zero.
void hswap(yht<N>& rhs) { // swap without change
N* tmp = h_n;
h_n = (N*) rhs.h_n;
rhs.h_n = tmp;
}
You can exchange node
refs beween two handles using hswap(). Neither
reference has a count change in refs here because the same net number
of handles and references is still there before and after. (When audit
backtraces are used, you need to swap the backtraces as well.)
// \brief deref (log & maybe throw on nil h_n)
N* operator->() const { // get node (must not be nil)
return (N*)(h_n? h_n: this->hn()); // log on nil
}
N& operator*() const { // get node (must not be nil)
return *(N*)(h_n? h_n: this->hn()); // log on nil
}
These operators overload
the arrow and star operators to return the node instance inside.
Since these methods are likely to crash on a non-nil pointer,
the inherited yh0::hn() method is called to
get the node pointer and log (or assert) it is not nil, so a better debug
report occurs.
// compare by == or - is by address of node
bool operator==(const yht& x) const { return h_n==x.h_n; }
bool operator!=(const yht& x) const { return h_n!=x.h_n; }
long operator-(const yht& x) const { return h_n-x.h_n; }
Comparison of two handles
occurs in terms of the node addresses inside. Subtracting two handles is
the same as address arithmetic on node pointers.
bool hdown() { return h_n && !this->hgood(); } // broken
bool hup() { return !h_n || this->hgood(); } // valid
} // class yht
These methods ask whether
a handle is valid or not. An up handle is either nil or contains
a good node. A down node contains a non-nil pointer that isn't
a good node. (When you want to assert a handle is currently respectable,
these two methods are a good way to do it.)
Normally I don't bother
printing to FILE streams, but occasionally I throw
one in for use under gdb. (Typically zero arg print()
methods are specifically for use under gdb.)
/*virtual*/ void yn::ndumpf(FILE* f) const {
int us = (int) n_uses; const char* atomic =
(e_natomic == n_atomic)? "@": "+";
if (e_nlive == n_tag) { // looks good?
fprintf(f, " <yn refs=%d uses=%d gn=%02x"
" up=%s/>\n", (int) n_refs, us,
(int) n_gen, atomic);
}
else if (e_ndead == n_tag) { // destroyed?
fprintf(f, " <yn-DEAD refs=%d uses=%d"
" gn=%02x up=%s/>\n", (int) n_refs,
us, (int) n_gen, atomic);
}
else { // random tag (probably not a node)?
fprintf(f, " <yn ?=%lx refs=%d uses=%d"
" gn=%02x up=%s/>\n", (long) n_tag,
(int) n_refs, us, (int) n_gen, atomic);
}
}
void yn::nprint() const {
this->ndumpf(stdout);
}
| |
For more context on refcounting
you can read log commentary from
last September
(generation-numbers)
and archived treedragon material from several years ago
(refcounting). But
neither is necessary; this page should stand alone. A new version of this
page will soon appear as the node
demo under þ.
license
All this code is
available only under the BriarPig mu-babel license described
fully on the rights page. You do
not have permission to reprint this page in any way.
No feeds or repackaging allowed. You can link this page
if you want folks to read it.
Handle-based refcounting
on this page includes several options you can ditch:
- weak as well as strong refs
- non-atomic incr as well as atomic
Weak refs support cyclic
graphs of counted nodes with good behavior when all backpointers are weak,
which makes the strong ref graph acyclic. Most refcounting systems
only do strong refs.
For thread-safe refcounting,
any change in refcount for an object shared among threads must use some
form of atomic integer update with mutexes or assembler. But atomic
changes flush chip caches and are therefore more expensive. This API
allows you to manually select atomic update, which becomes a byte-sized
node attribute.
Not shown on this page is
another recommended option:
- auditing with backtraces in handles
To debug refcount errors
automatically you'll want to add a field to handles capturing a
backtrace (plus stats) at time of addref(), so a
later release can be tracked. This allows you to find refcount leaks
via backtraces of
handles that incremented a ref but didn't decrement. This info
must be stored on a handle by handle basis, which is a main reason
to use handle-based refcounts.
yh0.cpp
¶
_hsetn() assigmnent
When a handle instance
is updated with a new node pointer, this method does
the assignment. Attempts to assign the same node are noops.
When a new pointer differs from old, the new is acquired and
the old is released. Either pointer can be nil: old or new or both.
A new node is always acquired first in case only
alive because reachable from the old. (If you release old first,
the new node might be destroyed as a side effect.)
// assign new node pointer to ref slot in handle
void yh0::_hsetn(yn* node) {
if (node == h_n) return; // same: no-op
bool strong = (e_hstrong == h_habit);
if (!strong && e_hweak != h_habit) // bad habit?
this->hbadhabit(); // log h_habit error
u8 gen = h_gen; // save for release of old ref
yn* old = h_n; // old ref to release if not nil
h_n = 0; // remove old ref (AFTER getting old)
// add new ref FIRST before releasing old ref:
if (node) { // need to add new ref?
bool added = (strong)?
node->_add_strong() : node->_add_weak();
if (added) { // seems a valid node?
h_n = node; // store only after add succeeds
h_gen = node->ngen(); // copy gen for later
}
}
if (old) { // need to release old reference?
if (strong) // handle for strong refs only?
old->_sub_strong(gen); // strong ref -1
else
old->_sub_weak(gen); // weak ref -1
}
}
Note the handle always
has the same habit, either weak or strong, which governs
whether weak or strong counting is performed. Strength is a property of
ref handles, not of nodes (but reflected in different
ref and use counts in a node).
A handle captures a node's
generation number when first assigned, which gets passed later to the
node release method, so the node can assert the gen is still correct.
fewer branches
¶
Note
_hsetn() method might be faster without branches
testing habit strength; two different handle base classes
— separating weak and strong —
would have smaller methods. But that kind of code duplication
for optimization purposes can always be done later.
Handle construction is
trivial.
yh0::yh0(EHabit habit/*=e_hstrong*/) // nil ref
: h_n(0), h_habit(habit), h_gen(0), h_pad(0)
{
if (e_hweak != h_habit && e_hstrong != h_habit)
this->hbadhabit();
}
yh0::yh0(yn* node, EHabit habit/*=e_hstrong*/)
: h_n(0), h_habit(habit), h_gen(0), h_pad(0)
{
if (node) this->_hsetn(node);
}
The second constructor
simply uses _hsetn().
yh0 goodness
¶
These methods check
a handle for goodness and log bad habits (which might be better
asserted than logged).
bool yh0::hgood() const {
// true if this ref and h_n both look good
// returns true if h_n is nil, or failing that, if
// these are true: h_n->nfine() & h_n->ngood().
if (h_n) { // need to check more conditions?
if (!h_n->nfine()) { h_n->ndead(); return false; }
if (h_gen != h_n->ngen()) {
h_n->nbadgen(h_gen); return false;
}
if (!h_n->ngood())
return false; // h_n logs
if (e_hweak != h_habit && e_hstrong != h_habit) {
this->hbadhabit(); return false;
}
}
return true;
}
void yh0::hbadhabit() const {
// call to log error when h_habit is wrong
if (e_hweak != h_habit && e_hstrong != h_habit) {
if (e_hdead == h_habit) {
ylog(1, "habit: dead=0x%lx "
"(not weak=%04lx nor strong=%04lx)\n",
(long) e_hdead, (long) e_hweak,
(long) e_hstrong);
}
else {
ylog(1, "habit=0x%04lx not "
"weak=%04lx nor strong=%04lx\n",
(long) h_habit, (long) e_hweak,
(long) e_hstrong);
}
}
}
yh0 node getter
¶
Log
unexpected nil node (then possibly throw).
long yh0_nil_ref_error = 0; // count nil nodes
yn* yh0::hn() const { // check h_n for nil)
if ( 1024 > (unsigned long) h_n ) { // close to nil?
++yh0_nil_ref_error; // count errors
ylog(1, "hn() deref throws=%ld: h_n=0x%08lx\n",
(long) yh0_nil_ref_error, (long) h_n);
// throw better than crashing on nil deref?:
//throw( NilError( __FUNCTION__, "h_n < 1024") );
}
return h_n;
}
yh0 habit string
¶
Strings for
enums are convenient in printing:
const char* yh0::hhabit() const { // habit string
switch(h_habit) {
case e_hweak: return "e_hweak";
case e_hstrong: return "e_hstrong";
case e_hdead: return "e_hdead";
}
// static local so space lives beyond call:
static char local[64]; // space is global
sprintf(local, "EHabit#%04lx", (long) h_habit);
return local;
}
The static local is never
be used unless habit is bad.
Bytes for member
n_gen are generated randomly during
construction. It might be faster to use only one byte of each
four generated rather than maintain a stream. But more
importantly, we have
fewer thread-safety issues too, if we don't need to mutex the seed.
// random stream seed for _nrandgen()
static u32 _yn_rand_gen = 0x7263676e; // arbitrary
/*static*/ u8 yn::_nrandgen() { // pseudo random byte
_yn_rand_gen = rand_j(_yn_rand_gen); // four bytes
// avoid most significant byte: it uses less bits
return ((u8*) &_yn_rand_gen)[1]; // pick mid byte
}
log bad gen
¶
Wrong node
gen observed? Log it:
void yn::nbadgen(int want) const {
ylog(1, "yn bad gen: saw=%u, want=%u\n",
(int) n_gen, want);
}
pseudo random
¶
Where does the
rand_j() method used above come from?
This is a
pseudo random number generator I've used since 1988 when
I read it in CACM
(cf 
Random
number generators: good ones are hard to find Park & Miller
Oct88). Hope I have no typos:
#define yk_kPrime ((long) 0x7FFFFFFF) /* mersenne */
#define yk_kMul ((long) 48271) /* prime P */
#define yk_kQuo ((long) 44488) /* mersenne / P */
#define yk_kRem ((long) 3399) /* mersenne % P */
u32 rand_j(u32 n) { // Park & Miller pseudo rand
if ( n ) { // non-zero (we won't return zero)?
long high = (long) n / yk_kQuo;
long low = (long) n % yk_kQuo;
long test = (yk_kMul * low) - (yk_kRem * high);
n = (u32) ((test > 0)? test : test + yk_kPrime);
}
else n = 1; // never return zero
return n;
}
Exercise for the
reader: write r64_j() returning a pseudo
random floating point number distributed uniformly between
0.0 and 1.0
while never being exactly equal to zero or one.
(Hint: rand_j() above returns values
uniformly distributed between
0 and yk_kPrime,
but never as small as zero or as big as yk_kPrime.
Park & Miller Oct88 says all integer values from
one to yk_kPrime-1 are visited exactly one
time before repeating, which explains the uniform distribution.)
See a node that looks
bad? Check if it's dead, or has some other problem:
void yn::ndead() const { // saw bad node?
if ( 1024 > (u32) this) { // close to nil?
ylog(1, "this=0x%lx near nil\n", (long) this);
}
else if (e_nlive != n_tag) { // wrong tag?
if (e_ndead == n_tag) { // dead?
ylog(1, "tag dead=%lx not live=%lx (r=%d u=%d)\n",
(long) e_ndead, (long) e_nlive,
(int) n_refs, (int) n_uses);
}
else { // some random tag then...
ylog(1, "n_tag=%lx, not live=%lx (r=%d u=%d)\n",
(long) n_tag, (long) e_nlive,
(int) n_refs, (int) n_uses);
}
}
else if (n_refs <= 0) { // refs not positive?
ylog(1, "n_refs not positive (refs=%d uses=%d)\n",
(int) n_refs, (int) n_uses);
}
else if (n_refs < n_uses) { // low refs for uses?
ylog(1, "uses exceed refs (refs=%d uses=%d)\n",
(int) n_refs, (int) n_uses);
}
else { // why was ndead() called?
ylog(1, "ndead() but why? (r=%ld u=%ld)\n",
(long) n_refs, (long) n_uses);
}
}
bad atomic
¶
Node has
surprise byte in n_atomic? Log it:
void yn::_bad_atomic() const {
ylog(1, "n_atomic=%02x\n", (int) n_atomic);
}
If you don't have
the assembler in hand for your platform to perform atomic
(thread-safe) integer increments and decrements, you can use the
following stubs until you find suitable assembler:
// placeholders for later asm
inline i32 atomic_dec(i32* ip) { return --*ip; }
inline i32 atomic_inc(i32* ip) { return ++*ip; }
One can usually find
assembler for this in pthread implementations of mutex, which typically
need to perform atomic integer operations.
These protected
yn methods are only called by
yh0 handles as a side effect of changing
node pointers inside handles, because node lifetime is tied
solely the number of handle references.
strong increment
¶
Perform
addref() for a strong reference:
// \brief private methods used only by friend yh0
bool yn::_add_strong() { // (++n_refs & ++n_uses)
// use _fine_node() to allow n_refs==0 as okay:
if (!_fine_node()) { this->ndead(); return false; }
// assert: n_refs >= 0 and n_refs >= n_uses
assert(n_refs >= 0 && n_refs >= n_uses);
bool at = (e_natomic == n_atomic); // thread safety?
if (!at && 0 != n_atomic) this->_bad_atomic();
if (at) { atomic_inc(&n_refs); atomic_inc(&n_uses); }
else { ++n_refs; ++n_uses; }
return true;
}
strong decrement
¶
Perform
release() for a strong reference:
// \param gen is caller's copy of expected gen
void yn::_sub_strong(u8 gen) { // --n_uses --n_refs
if (!this->nfine()) { this->ndead(); return; }
// assert: n_refs > 0 and n_refs >= n_uses
assert(n_refs > 0 && n_refs >= n_uses);
if (gen != n_gen) this->nbadgen(gen); // problem
bool atomic = (e_natomic == n_atomic);
if (!atomic && 0 != n_atomic) _bad_atomic();
if (atomic) { // need atomic for thread safety?
if (n_uses && !atomic_dec(&n_uses)) // no uses?
this->nzeroUses(); // shut down
if (!atomic_dec(&n_refs)) { // zero refs?
assert(0 == n_uses); n_gen = ~n_gen;
this->nzeroRefs(); // deallocate node
}
}
else { // fast and simple arithmetic
if (n_uses && --n_uses <= 0) // zero uses?
this->nzeroUses(); // stop
if (--n_refs <= 0) { // zero refs?
assert(0 == n_uses); n_gen = ~n_gen;
this->nzeroRefs(); // deallocate node
}
}
}
weak increment
¶
Perform
addref() for a weak reference:
// \brief private methods used only by friend yh0
bool yn::_add_weak() { // weak (++n_refs only)
// use _fine_node() to allow n_refs==0 as okay:
if (!this->_fine_node()) { ndead(); return false; }
// assert: n_refs >= 0 and n_refs >= n_uses
assert(n_refs >= 0 && n_refs >= n_uses);
bool atomic = (e_natomic == n_atomic);
if (!atomic && 0 != n_atomic) _bad_atomic();
if (atomic) { atomic_inc(&n_refs); }
else { ++n_refs; }
return true;
}
weak decrement
¶
Perform
release() for a weak reference:
// \param gen is caller's copy of the expected gen
void yn::_sub_weak(u8 gen) { // weak (--n_refs)
if (!this->nfine()) { this->ndead(); return; }
// assert: n_refs > 0 and n_refs >= n_uses
assert(n_refs > 0 && n_refs >= n_uses);
if (gen != n_gen) this->nbadgen(gen); // oops
bool atomic = (e_natomic == n_atomic);
if (!atomic && 0 != n_atomic) _bad_atomic();
if (atomic) { // atomically for thread safety?
if (!atomic_dec(&n_refs)) { // zero refs?
assert(0 == n_uses); n_gen = ~n_gen;
this->nzeroRefs(); // deallocate node
}
}
else { // fast and simple arithmetic
if (--n_refs <= 0) { // zero refs?
assert(0 == n_uses); n_gen = ~n_gen;
this->nzeroRefs(); // deallocate node
}
}
}
Construction is trivial.
The handle arg form is preferred so a node gets first ref
in constructor.
yn::yn(yh0& handle) // refs=1 (if strong uses=1)
: n_refs(0) // zero until handle->_hsetn()
, n_uses(0) // zero until first use is a added
, n_tag(e_nlive) // must equal this for lifetime
, n_frozen(e_nmutable) // until nfreeze()
, n_atomic(0) // until nsetatomic() : e_natomic
, n_gen(yn::_nrandgen()) // pseudo random 8-bits
{
handle._hsetn(this); // 1st ref (maybe 1st use)
}
yn::yn() // \brief create w/ zero refs & zero uses
//refs=0, uses=0 until first assigned to yh0 or yht
: n_refs(0) // zero until handle->_hsetn()
, n_uses(0) // zero until first use is a added
, n_tag(e_nlive) // must equal this for lifetime
, n_frozen(e_nmutable) // until nfreeze()
, n_atomic(0) // until nsetatomic() : e_natomic
, n_gen(yn::_nrandgen()) // pseudo random 8-bits
{
}
The empty
constructor is dangerous since refs are zero until first
assigned to a handle; so avoid it.
yn destructor
¶
The destructor
under normal operation only marks members invalid, taking special
care to change n_gen so it disagrees with
any stale handle to this node. Any n_gen change
is good except one's complement (~n_gen)
since that was used earlier when refs hit zero.
long yn_already_destroyed = 0; // dead before
long yn_bad_destroy = 0; // nlive() is false
long yn_nonzero_refs_or_uses = 0;
yn::~yn() { // called when n_refs goes to zero
if (e_ndead != n_tag) { // not dead yet?
if (!nlive()) { ndead(); ++yn_bad_destroy; }
if (n_refs || n_uses) { // still nonzero??
++yn_nonzero_refs_or_uses; // count these
ylog(1, "not zero: refs=%ld uses=%ld)\n",
(long) n_refs, (long) n_uses);
}
n_tag = e_ndead; // explicitly destroyed
++n_gen; // need different; zero is weak
n_atomic = '$'; // not e_natomic nor zero
}
else
++yn_already_destroyed; // count these
}
We looks for
several error conditions and count some of them for later
statistics reporting.
These virtual methods
are typically overridden by all subclasses, unless the defaults are
fine (most likely for nzeroUses()
and nzeroRefs()). The printing methods are
typically a pain to write, but are often the most useful in
debugging once written.
/*virtual*/ void yn::nzeroUses() { // on zero
// default: nothing (free refs & owned space)
}
/*virtual*/ void yn::nzeroRefs() { // on zero refs
delete this; // default: free on zero refs
}
/*virtual*/ bool yn::ngood() const {
if (!this->nfine()) { ndead(); return false; }
return true;
}
/*virtual*/ void yn::ncite(yo& o) const {
const char* rw =
(e_nfrozen == n_frozen)? "r": "w";
const char* atomic =
(e_natomic == n_atomic)? "@": "+";
if (e_nlive == n_tag) { // looks good?
o.of(" <yn refs=%d uses=%d gn=%02x rw=%s"
" up=%s/>", (int) n_refs, (int) n_uses,
(int) n_gen, rw, atomic);
}
else if (e_ndead == n_tag) { // destroyed?
o.of(" <yn-DEAD refs=%d uses=%d gn=%02x rw=%s"
" up=%s/>", (int) n_refs, (int) n_uses,
(int) n_gen, rw, atomic);
}
else { // random tag (probably not a node)?
o.of(" <yn ?=%lx refs=%d uses=%d gn=%02x rw=%s"
" up=%s/>", (long) n_tag, (int) n_refs,
(int) n_uses, (int) n_gen, rw, atomic);
}
}
/*virtual*/ void yn::ndump(yo& o) const {
this->ncite(o);
}
/*virtual*/ void yn::nout(yo& o) const {
o.o1c('['); o << this->nclass(); o.o1c(']');
}
void yn::npr() const { // { ncite(stdout); }
yout << yendl; this->ncite(yout);
yout << yendl << ynow;
}
Note
ndump() would work equally well in
nprint(), so the use of ndumpf()
for that is a gratuitous variation to make an example.
|
|
