When Wil manages memory with refcounting, he subclasses a base node class yn centralizing all details. Wil also uses a specific handle type to hold node refs because this style can be centrally and automatically audited (if you choose). Class yht is a handle template that's basically a smart pointer.
The base yh0 handle is a managed pointer to one yn node instance. The pointer is stored in member h_n, and it can be nil to say "no node" referenced. The rest of the yh0 api, as well as api in derived template yht, aims to ensure pointer h_n is non-nil if and only if a reference was added to that node for this handle.
In this sense yh0 is a kind of RAII guard ensuring h_n is released when a handle is destroyed. The handle destructor ensures h_n is released so exceptions cannot subvert correct refcounting since stack-based destructors execute when exceptions are thrown past them.
class yh0
The 16-bit h_kind contains either e_hweak for a weak ref or e_hstrong for a strong ref, and this can be set only when a handle is constructed. (The difference is described in the yn api — but briefly, a node stays usable while n_uses is nonzero and stays allocated while n_refs is nonzero. A strong ref increments both, but a weak ref increments only n_refs, not n_uses.)
Byte h_gen in a handle is a copy of byte n_gen in the node, and is captured when a ref is added. Because a node's generation number is constant during a node's lifetime, this handle copy helps verify the node has not been destroyed and recreated, which could happen in the presence of refcount errors.
Private _hsetn is the only method changing the value of h_n, so this is where correct refcounting is enforced. It's called only by yn (e.g. the constructor), template yht, and ~yh0() below.
The private constructors and destructor are called only by template yht, so you cannot directly instantiate yh0 — you can only make yht template instances. Note the destructor makes h_kind invalid in a way clearly marking the handle as destroyed. This can reveal bugs in trying to use handles after destruction.
These public getters let you query handle state. The strength of a handle never changes. If a handle is neither weak nor strong, you can call hbadkind() to log a description.
Method hn() returns the node, but aggressively checks for nil, so you can use hn() to get the node inside when nil would be a disaster. For example, when template yht acts as a smart pointer dereferencing the pointer, hn() can report first — or perhaps throw an exception if you prefer that to crashing (and if you aren't vehemently anti-exceptions).
Method hgood() decides whether the handle and node both look good. A nil h_n pointer counts as good, but h_kind must be either weak or strong. When h_n is non-nil, the node itself must check out too.
Most of the rest of the api supports handle printing — including nodes inside as well. So you can print a node simply by printing any handle to that node. The quote and out demos are a good place to find intros to printing.
Unlike quote nested structs for most objects, the Hq quote for a handle takes an optional nul-terminated C string label for use as the "arc" attribute when printing a node inside:
Note the quote and cite inlines are quite unusual compared with similar quote support in other classes, because they take an extra optional argument to describe the handle itself (for example a member variable name) used as the "arc" attribute when printing the node inside.
yh0.cpp
The following yh0 base handle methods are non-inlines, in constrast to template yht with all inlines. (The separation between yh0 and yht is partly motivated by a desire to have one canonical copy of code for these methods.)
Private method _hsetn() effects the central feature of handles: setting the node in a handle releases the old node and acquires a reference to the new node — provided the new node is not the same pointer as the node.
Note the ref to new node must be added before releasing the ref to old, since otherwise the last ref to node might disappear first as an indirect effect of releasing old. (Releasing the old node first is a classic refcounting mistake.)
When old is released, its current generation number must match the copy stored in h_n when old was first set into this handle. Any change in a node's generation number means either the node is corrupt or it's been freed and reallocated (incorrectly) without regard to the ref from this handle. Verifying node generation is a form of refcount error detection.
The h_kind of the handle controls whether a weak or strong ref is added to each node set in the handle.
Member h_kind is set once only when a handle is constructed — it defaults to strong when unspecified.
When a node is passed to a handle's constructor, it adds a ref to the node by setting the node into the handle:
Method hgood() is true when the handle is good: either the node is nil (a normal case) or the node must look valid instatic check of base class yn using non-virtual nfine(), as well as a dynamic check of the subclass with virtual ngood().
The generation number must agree between node and handle, and the kind of handle must be valid.
Note the extensive use of macro yunlikely() described on this page (high column right) aims to tell the compiler the test condition is unlikely to be true and predict the branch accordingly: the handle is expected to be good, so the slow branch prediction path only occurs on error.
Method hbadkind() logs odd h_kind values:
Method hn() below returns the node in the handle while objecting loudly if the node is nil. An assert here is appropriate, as is throwing an exception — if you use exceptions — when the node is nil or near nil, because the caller requires a non-nil node. Note hn() is called by smart pointer operators that dereference the node pointer, so nil is a disaster.
The archaic, vestigial hdumpf() method prints to FILE* instead of a yo out stream.
The following print methods are consistent with style used elsewhere in these demos. If the handle has a non-nil node, it's dumped as well. By convention, the arc argument is a name or description of the handle.
Note ndump() and ncite() are virtual yn methods, so a node is printed in subclass specific detail.
Methods hkin() and hkind() return short and long names for h_kind, which must be either strong or weak (and yet if the value is ever invalid, we'd like to see what it is).
Note the use of static (global) string buffers for formatting when h_kind is invalid. This approach is technically not thread safe, but no contention is expected.
Because the node api refers to it, the following forward to yht appears, along with a typedef for ynh which means thorn node handle. It means exactly the same thing as yht<yn>, which is a handle to some node subclass.
Take special note of typedef ynh for two different reasons. First, as result of the typedef, ynh is synonymous with yht<yn> so it's a handle to any node subclass. By convention, Wil appends h to say handle — so fooh is a handle to a foo node.
Second, even though yht and yn are still just forward declarations, yht<yn> can still be used to declare typedef ynh. You can always forward declare specialization of a template T for node N when both are still just forwards.
Every yn node subclass begins with these state members, the most important of which are n_refs and n_uses:
class yn
If we do not distinguish strong refs from weak, only n_refs is needed: a node is deallocated when n_refs hits zero. In conventional refcounting schemes without weak refs, a node is also destroyed right before deallocation, because you're also done using a node if n_refs hits zero.
C++ conflates destruction and deallocation: you're encouraged to destroy and free objects in one go using delete(). So one count using n_refs fits a normal C++ model perfectly: when n_refs hits zero, destroy and deallocate, both.
But that's not how yn works. Instead, a node is destroyed (ie halted, shutdown, turned off, etc) when n_uses hits zero, when an owner is done using a node. This happens strictly before n_refs hits zero, even when both are decremented together, because n_uses is always decremented before n_refs.
Under yn's ref model, a strong ref increments n_uses and n_refs, both. So a strong ref not only stops an object from being freed, it also stops an object from shutting down.
But a weak ref increments n_refs alone, which only stops a node's memory from being freed. A weak ref does not stop an object from shutting down when an owner releases the last use associated with a strong ref. A weak ref makes it safe for you to check an object to see if it's still up and running.
The purpose of weak refs is to make strong ref graphs acyclic, so graph cycles will not stop object networks from shutting down properly. By convention, a child node refers to one or more parent nodes using weak refs as "back pointers" — this prevents cycles in a graph of strong refs.
(However, most uses of refcounting are not very complex, nor do they build elaborate networks of inter-node refs. So extra flexibility afforded by weak refs might not be useful to you anytime soon — the extra baggage is pure overhead if you don't need it. Though not shown here, a simplified verison of nodes using n_refs alone is easy to derive from this one.)
Okay, now back to private yn members:
The seven-bit magic numbers above are used in several different one-byte members below. Since these values are private, you need only track them to understand code, debug data structures, and read print formats.
Member n_tag must have value e_nlive to be valid; any other value makes the node look corrupt. All these byte members are cheap to see when you aim to touch the cache line containing n_refs and n_uses anyway.
Readonly versus mutable status is indicated by n_thaw, but obeying is informal, unmonitored, and inconsistent — in short, this byte is there only if immutable status is useful to some subclass. Otherwise it might be ignored. (This style of coding is somewhat hard to explain, so let's leave it there.)
The n_risk byte says whether refcounting must be done atomically or not. More specfically, when this byte contains e_nrace the node should be treated as shared between threads and thus at higher risk that should be mitigated by making as few changes as possible — for example, some cow optimizations are turned off once a node is shared.
The n_risk byte lets you negotiate a graceful transition between early object life full of cheap modification before sharing, to later shared object life when mutation is dangerous or costly. Instead of designing a node around either early use or later use, you can do both and use n_risk to keep track. So you can write imperatively at first then switch to functional style.
The last n_gen byte is an 8-bit generation number for a node assigned when each node is constructed, then later changed only when that node is destroyed. The purpose? n_gen validates refs to the node saved elsewhere: mainly in yh0 handles which copy this byte into each handle that refs a node.
This generation number handshake between handles and nodes addresses one of the big risks in diagnosing refcount errors incorrectly or sporadically — early node destruction by releasing one ref too many (something handles aim to avoid but cannot prevent if you stomp on handles) can result in a node that enters a free pool only to be reallocated again before an old stale ref to the last lifetime even notices. The change in generation numbers is a telltale sign to signal dire alarms, since otherwise deeply confusing runtime behavior can occur.
Private methods above changing n_refs and n_uses are called only by yh0 — in fact, these methods are called only by yh0::_hsetn() (cf «). And these methods are the only ones that change n_refs and n_uses. This draconian narrowing of refcount modification aims to make auditing feasible, since it becomes possible to reason about node lifetime in terms of which handles have a ref to which nodes. You can instrument yh0::_hsetn() alone to capture backtraces. (But any swap method would also need to swap backtraces.)
The getters and setters above are kinda obvious. Note nfreeze() and nshare() are one-way operations and can't safely be undone if you're being pessimistic. When you decide to start working with immutable data in functional subsystems, don't ruin the rigor by changing your mind.
Note when you have a weak ref to an object, a nonzero value returned from nuses() tells you the object has not been shut down (if you need to avoid calling methods on an object that has halted operations but has not been freed).
Once natomic() returns true, meaning the object is potentially shared with other threads, you can no longer really tell the current value of nrefs() (or nuses()) no matter what values are returned — but you can always safely tell zero from nonzero, since zero is a sticky state.
"What happens if I forget to call nshare() when an object is shared with other threads," Dex wondered, "How do I tell if it's safe to look at values of nrefs() and nuses()?"
"That would mean you're an idiot," Wil replied. "Don't blame me if you use the api wrong and get random results."
"Thought so," Dex nodded. "Just checking."
"Ooh," Dex crooned when he saw the methods above. "What does nice() do? Am I an idiot if I use those wrong?"
"No," Wil assured. "Method nice() expressed an idea I needed in my last copy-on-write prototype. It means 'need-cow' when you want to know if you can safely modify an object, or whether you should make a new copy because the old one is shared."
"Why isn't needCow() the name then?" Dex asked.
"That was the name, but I changed it," Wil noted. "I figured folks would ask 'What the hell does that mean?'"
"Well I'm still asking that," Dex chimed.
"I chose nice to mean node-frozen (because ice is cold) and 'share nicely with others' both at once," Wil explained. "So it's a double entendre, and I like it that way."
"Stop using big words," Dex joked, or pretended to.
"Anyway, nice() returns true when you should be nice to another party by not changing a shared object," Wil continued. "It returns false if you can reckon you're the only current user of the object. When you know you personally account for N of the refs, then you don't need to be nice when the refcount is no more than N, and you see no risk of race on another ref appearing from another thread."
"And when you see it's not readonly," Dex added. "I only interrupt because I hope you're out of breath."
"Oh no," Wil said, "I can talk til your eyes glaze over."
"Tell me about it," Dex rolled his eyes.
Non-public _fine_node() is a special case version of public nfine() below used only in yn::_add_strong() and yn::_add_weak() (cf », ») where a zero starting value for n_refs must be allowed when the first ref to a node after construction occurs. This method means "node looks fine."
Getters above check apparent node validity. Note the unconventional check for nil which considers any very small address too tiny to be valid. (Typically page zero is never mapped in virtual address spaces, so less than 4096 is a more accurate check than 1024.)
The first constructor above taking a yh0 handle is the preferred way to construct every node, to ensure each and every node ref is safely managed by a handle instance, including the very first. This constructor makes a node with nonzero refs and all is right with the world.
The second empty constructor is provided only because it's blessedly awkward not to have an empty constructor for C++ objects in many situations — for example, how else can you declare arrays of nodes? (Actually, this example is cooked because you must not declare arrays of nodes since they are managed individually and not in arrays. But there are other times when you want an empty constructor too.)
The empty constructor should be used only as a last resort while recognizing you're taking a risk exercising an odd edge condition in refcount behavior since the node constructed has zero refs initially until you assign it to a handle. The state of zero refs is basically illegal and must be temporary — it's forgiven as long as you don't use a node before it gets a first ref.
These methods start virtual yn api for subclasses to override. For example, nclass() should always return the name of the subclass (pretend you don't have RTTI support enabled).
To copy a node you can clone the original, which ought to make a deep copy, but can make copy-on-write shallow copies of nested objects — just not the topmost node because the caller has already decided this node must be copied.
(If you find this confusing, just you wait. You'll need to spend a lot of time thinking about copying if you do it much, especially if you dabble in copy-on-write. It comes with the territory, so just cope. The ncow() method below might or might not return a clone or new copy, but for generic copy-on-write algorithms to work, nclone() should copy and leave decision-making to higher layers. Cloning is low level mechanism.)
The n2iovec() and nclonez() methods are kludges that awkwardly reveal an expectation — easily untrue — that subclasses consist of content in the form of mostly raw byte sequences you can describe as an iovec. Obviously not all nodes are like this, so these methods ought not to be used with nodes that can't map meaningful behavior on them. The idea behind these methods is subsetting parts of existing byte sequences by selecting one part to clone instead of all of it.
Note these are not virtual — polymorphic behavior comes from overriding virtual clone().
Methods above focus on copy-on-write effects: ncow() should clone() if this node must be nice() and avoid modification. The ncowz() version is more of the iovec subset kludge business mentioned above, and the template versions are something of an experiment Wil explored whose usefulness is little confirmed. You should avoid them unless you're ready to dive into cow and your own extentions for copy-on-write.
If you need to override default behavior when refs and uses hit zero, do it here: nzeroUses() is called when n_uses hits zero, and nzeroRefs() is called when n_refs hits zero. The calls will occur in this order because uses are always decremented before refs: so nzeroUses() is always called when a node has nonzero n_refs because it hasn't been decremented yet.
By default nzeroUses() does nothing and nzeroRefs() calls delete this. So you need only override when you want something else to happen. You might want to move some destruction into nzeroUses() — for example, you must release all refs here to unwind graphs. And you might want to free a node differently in nzeroRefs() — for example, by putting a node back in a free list or particular heap.
Method ngood() is similar in spirit to nfine() which says whether a node looks valid (cf «) but ngood() is polymorphic so subclasses can add more kinds of consistency checking. For example, y8vn::ngood() shown on this page looks at before and after guard bytes surrounding the string to detect overwrites and underwrites (cf »). Implementations of ngood() should call nfine() first to rule out simple node failure first.
Method nout() writes node content to a yo out stream in as native and undecorated fashion as possible. For example, if a node contains a sequence of bytes, nout() should write those bytes in binary. Actually nout() is somewhat underspecified — you should really write whatever you find useful to have serialized, in contrast to print methods below that should write human-readable debug descriptions:
By convention, printing methods write verbose multi-line dump format and concise single line cite format in style used by demos found on other pages, using style and api explained in the out and quote demos. But you can look at example subclass y8vn for example print code (column right »).
Because ndump() is virtual, nprint() which calls it need not be. Method npr() calls ncite() the same way nprint() calls ndump(). Both are intended for use under gdb.
Nested struct Nq is a wrapper in style explained by the quote demo, used to overload operator<<() to call ndump() as shown immediately after this class (cf »).
By convention all node subclasses must have protected destructors, just as virtual yn::~yn() is declared above. Nodes must not be stack allocated, and the destructor must not be called by anything besides nzeroUses() or nzeroRefs() — and only the latter is a good idea.
These inline operator<<() methods resemble boilerplate used everywhere in demos for printing.
This section contains implementations of yn node methods declared in the class api above.
yn.cpp
Method _nrandgen() uses pseudo random number generator h32rand() from the rand demo (cf «) to populate node generation byte n_gen every time a node is constructed. Of the four bytes generated, only one is used in n_gen because work spent trying to use the other bytes in subsequent calls might cost more (and would be far more complex) than simply calling h32rand() again.
The cost of populating n_gen with a suitably random value at node construction time might not seem warranted to you, because you're not very concerned about detecting memory corruption or noticing whether your refcount discipline is wrong. You're welcome to change the code in your clone. (Wil certainly changes this code to suit the whims of anyone needing refcount code in day jobs.) However, when you're debugging, it's a very good idea to make n_gen start very random.
Methods logging error conditions are shown above and below; ndead() attempts to log why either nfine() or nlive() returns false. For debug purposes, the more detailed job it does of explaining a problem, the better. The speed of ndead() doesn't matter at all since it's only called when a disaster occurs (a node seems corrupt) and you would normally throw an exception in C++ coding styles free with exception use.
refcount methods «
Each method changing refcounts tries to verify the node looks valid, as a minimal rate at which to seek negative evidence the world is still okay.
Adding a strong ref, shown below, adds one to both n_uses and n_refs. Because _add_strong() is called only from yh0::_hsetn() (cf «) and because handles do not change ref strength, this means _sub_strong() will be called later by that handle when it loses that ref.
When a handle releases a strong ref to a node added earlier with _add_strong(), the handle calls _sub_strong() below to undo changes to n_uses and n_refs. Each time either value hits zero, the appropriate virtual handler is called.
When uses hit zero, nzeroUses() must release any resources held by the node besides the node memory itself, which must remain until nzeroRefs() is called on zero refs.
When refs hit zero, nzeroRefs() must finish destruction (if any state remains to destroy) then free a node's memory. Note node generation number n_gen is changed (flipping all bits) before calling nzeroRefs(), so nzeroRefs() must tolerate this if anyone aims to check n_gen. (But since no handle exists with a ref to this node, how can anyone object?)
Weak versions below (of strong refcount methods above) are nearly the same, but n_uses never changes in weak refs, so a weak ref plays no role in preserving resources in a node or stopping a node from half destruction in nzeroUses() when the last ref from a strong handle goes away.
Note weak ref methods (to add or subtract a weak ref) are called only by yh0::_hsetn() when a node is added to or removed from a handle (cf «). So a weak ref is held only by a weak handle, and only changes in state of a handle cause changes in node refcounts.
This means any analysis you do studying node lifetimes can be expressed completely in terms of the set of handles referring to nodes. This was designed purposefully, so control flow of refcounting is determined by graphs of handle refs alone. This is another kind of scope limiting tactic, since you can reason about refcounts for a population of nodes by studying only those locations with handles to nodes in that population.
node construction «
You should use this yn constructor when possible:
The resulting node is well-formed and has a valid relationship with at least one handle holding a first ref to the node. It's a bad idea to construct a node without passing a handle to receive the first ref, because that creates an opportunity to leak a node that never had a first ref in a handle.
The following yn constructor is a leak waiting to happen: if you never put this node in a handle, refcounting methods will never be called and neither nzeroUses() nor nzeroRefs() will be called, which would be bad. However, in C++ it's quite awkward when an object has no empty constructor, and the þ library does not induce pain in the name of purity.
However, you've been warned: if you use the empty constructor to make a node, your duty is to ensure each such node gets assigned to a handle later to ensure resources are later released when nzeroUses() and nzeroRefs() are called — which occurs only yh0::_hsetn() as a side effect of removing a node ref from a handle (cf «) when refcount methods are called.
(Note Wil sometimes defaults n_risk to shared e_nrace in constructors for testing since this should also work. Printed output in demo sample code might or might not show nodes start in a shared state where natomic() is true.)
Nodes are destroyed only as a side effect of releasing a node ref from a handle in yh0::_hsetn() when a new node is assigned or the old one is simply cleared (cf «).
In effect, by convention yn::~yn() is never called except inside nzeroRefs() which can only be called by handles. You may not decide when a node is destroyed except as a side effect of ensuring the last ref to a node goes away. However, you cannot control how many refs to a node exists, unless you also control visibility of any handles that hold refs involved. Anyone who sees a node or a handle to it can take a new ref.
If you dislike this model, you should not use yn nodes. Don't show a node to anyone you don't trust with the right to take a new ref. Sight is permission to refer. More complex contracts are subclass specific, which yn cannot enforce.
The defaults to halt on zero uses and free memory on zero refs are quite simple: nzeroUses() does nothing and nzeroRefs() just deletes (which obviously also calls the virtual destructor). How you override these — and whether you do — depends completely on the node subclass.
By default ngood() is the same as nfine(), but logs the problem when false is returned. By convention, all ngood() implementations should log when they return false.
Method ndumpf() is for use in shops where folks find yo out streams deeply disturbing.
By default ndump() calls single-line oriented ncite() because there's nothing else to print.
By default nout() writes the class name inside of square brackets. It might instead write whatever is returned by n2iovec(), but adding more dependencies among methods is a source of potential confusion.
The base n2iovec() returns an empty iovec because no other state is present besides yn meta data. A subclass can override this to return actual contiguous content if it makes sense in a subclass (cf y8vn::n2iovec(): »).
Base cloning methods that copy a node subclass do nothing but log aggressive complaints. You need only override these methods if you subclass will actually be copied.
Both variations of ncow() below assume the hout handle argument is already the handle that refers to this. But since ncow() consistently returns the node hout references, just to make sure, the else clause sets this into hout when the node pointer is different:
Both the copy-on-write methods are shallow layers atop the virtual clone methods. When a node cannot be safely modified, because it might be shared with other users who would be undermined by change, these cow methods return a fresh copy (that can be changed) when being nice to other parties will forbid simply returning the original node itself.
Note neither cow method above is type-safe, in the sense any yh0 can be passed even if it's yht<N> for subclass N which is not the same subclass as the node. You can see why that's a problem. For this reason, Wil added template versions of these cow methods when you want to use a typesafe api (cf »).
The handle template class shown below is the primary way you'll use handles with nodes.
Although base handle class yh0 does all the real work in yh0::_hsetn() which does all refcounting (cf «), handle template yht is how you actually use handles.
You should declare yht<N> with node subclass N specific to your needs for type-safe api use. The main reason? Using yht<N> avoids casting, which is inherently dangerous since you might make a mistake. If you ever did make a mistake, it could take a painful amount of debugging to correct, especially if the effect was very indirect refcount failures.
Wil doesn't really like templates, but yht<N> smart pointer handles are one of the most helpful template applications Wil has seen, tending to result in code that works correctly the first time more often than not. Template handles support generic refcount support while keeping stringent compiler type checks. So yht<N> is a time saver without too high an api complexity cost.
class yht
Remember: ultimately everything is done by the yh0 base class, except for type-safe inline casting effects.
When you construct a handle, you must choose strong or weak — default is strong — and the kind of handle cannot later be changed. The norm is a strong handle.
You can release the node in a handle by assigning 0 — understood as (N*)0 — or you can assign magic value singleton ynil whose type if y1nil.
The following constructors dangerously allow you to mix and match the node subclass; use at your own risk. (Or remove them if your system need not tolerate this risk.)
Using constructors below you can copy construct a new handle from an old, and you can change handle strength in the new handle: either strong or new.
Method hset() is the same as operator=(), but uses a unique name for later source code searches.
Operators bool() and N*() are consistent in terms of returning zero when the pointer is nil.
You can swap references with another handle, so each handle takes over responsibilities of another. Handle strength must be the same, or else a leak of n_uses can occur.
Swapping content of one handle with another is a good way to avoid refcount overhead when it would otherwise occur.
The following operator->() turns each yht handle instance into a "smart pointer" because you can treat type yht<N> the same as N* when calling a method using handle->method() syntax. And operator*() lets you do the same with handle.method() syntax.
Both smart pointer operators call hn() to get the node pointer because it objects strenuously if the pointer is nil (since you are likey to crash when the call dispatches).
Comparison of handles — and difference of two handles — is based on node address alone.
The following hup() and hdown() methods tell you whether the handle looks up for use, or down and out of commission. They help when you need to add aggressive checks in code asserting handles used are still in valid states as expected.
Copy-on-write support extends to handle api below, where methods on handles perform approximately the same thing as nodes by asking the node within to perform the operation.
Note how semantics of cow methods in nodes have this effect here in cow handle methods above: hcow() and hcowz() force this handle to refer to a node that can be safely modified, it is has to copy the original node to get a new one that can be updated. Note this really only works when your model is almost strictly "by value" and replacing an old node with a new clone interferes with no old relationships.
The last h2iovec() method above is a way to call n2iovec() polymorphically if a node is present, defaulting to an empty iovec when the pointer is nil.
thorn: todo, names, fd, iovec, assert, log, run, hex, crc, buf, in, out, quote, escape, compare, file, deck, cow, arc, blob, tree, slice, rand, time, stat, hash, heap, node « Þ, primes, page, book, pile, stack, atomic, lock, mutex, thread, map, meter, list, iter, ctype
(mu: toy, peg, imm, tag, box, symbol, token, number, bigint, class, method, reader, writer, eval, env, vm, gc, world, pcode, compiler, asm, lathe, lisp, smalltalk, design, weight, jar, card, harp, debug, profile)
Some demos are stubs: todo is a demo guide. See toy for mu updates on language pages; names introduces naming schemes.
The name of class yn means thorn node and the name of class yh0 means thorn handle origin — it's the non-template base class for yht<N> meaning thorn handle template, which is what you'll actually use as a smart pointer to nodes.
Nodes and handles are tightly intertwined: each class depends on the other. Getting order in a header file right is awkward. An order that works so far is: yh0, then yn, then yht.
We start with the yh0 base handle because yn node inlines use it's api. It's basically an annotated pointer.
The style of refcounting shown on this page is a bit complex compared to normal practice in most shops: doing the simplest possible thing that can work. But any very simple form of refcounting is subject to byzantine failure — often devlish to diagnose because the purpose of refcounting is shared ownership. You see, it's hard to pin blame on an owner for errors when many possible owners leave no audit trail. Suppose a refcounting object leaks: who did it? At least one of the refs added was never released — finding one owner at fault is hard.
In contrast, handle-based refcounting — the kind shown on this page — can hold an interned stack backtrace in a handle denoting the point where a refcount was incremented. This permits auditing for each reference: each backtrace counts up and down changes in refs, so any backtrace with a nonzero balance is suspect.
However — and this might seem like a tease — the backtrace support for auditing won't be shown in code below. If you need it, roll your own, or shell out the bucks for someone else to code it for you. Wil usually does backtraces on Linux with good, fast, standard backtrace support — but most of this demo code is being developed on an Intel Mac laptop with lousy backtrace support.
(A future backtrace demo might be added specifically to add this feature. But it won't appear on this page.)
Starting in this demo, macros to override the compiler's default branch prediction will be used when an early test is performed to handle an unlikely edge case — macro yunlikely() below calls gcc supported __builtin_expect() with arguments saying, "The expected result of expression x is false."
yunlikely()
So if you test for an error like this:
You can instead write the same test like this:
The second version using yunlikely() has exactly the same behavior as the first, except for one difference: the compiler will predict the expression is false and optimizes to take the branch on false. So the code usually runs faster when the unlikely test is untrue.
Use of this macro was avoided earlier in demos as an obfuscating detail. But now it seems better to start showing good coding style with respect to branch prediction hints.
(I've been told an Intel compiler implements this branch prediction hint by moving the code inside the if-block to the end of the function, so as a side effect, the cache line locality of code not inside the if statement is also improved.)
This page is a rewrite of a refcounting page done ten months ago in Oct2007. This version renames several enums, member variables, and methods when it seemed to clarify detail. You might find a comparison only slightly interesting, at best.
This version has several cow (copy-on-write) features from the last major revision, including several experimental hacks with messy api boundaries that poorly separate base class from subclasses: yn assumes too much about the nature of subclass copy-on-write implementations. So you'll see some mess Wil did not clean up.
This yn node api draft includes many warts from experimental code done several years ago when Wil last drafted a version of deck for refcounted pseudo-mbufs. (If you don't know what an mbuf is, don't worry about it. But if you do, a deck is just a fancy kind of mbuf.) You should expect aspects of copy-on-write api look really weird, or at least awkward and lopsided. So any feeling cow code is ugly or wrong in a few places is appropriate: Wil agrees with you.
Wil might redo copy-on-write api for a future deck demo to make it cleaner; this page will be updated if that happens. Until then, if you can't stand warts, just ignore all copy-on-write methods. Or if you want to rework a new clean copy-on-write api, start with the warts for clues in the right direction. It won't kill you.
The way Wil uses inheritance for refcounting isn't necessary — it's a choice. Refcounting is often done by others with (for example) template-based interfaces with no inheritance involved. Note that sort of api can be contructed using the one seen here.
But in þ Wil conflates two different purposes in one class: 1) desire for smart refcounting, and 2) desire for a root object class.
Once Wil adds refcounting to an object, he prefers to add a lot more semantics to go along with it, so he can assume more about nodes than he does other þ classes. For example, all nodes know how to print themselves, with specific virtual methods for it. So yn for a node instance is a bit like an Object root base class in oo inheritance hierarchies. However, most þ classes are not nodes and do not inherit from yn because this would impose to much on subclasses; for example, the yo out stream base class is not a node subclass, and neither are most þ types.
Basically, subclassing yn to get refcounting is a step in the heavyweight direction, so Wil just keeps going that way. You're a node? Fine, then you're heavyweight compared to stack-based flyweight structs and a little more root-object api won't increase cost that much more. Any time Wil is tempted to make some api common to all objects, this is a candidate for addition in yn. The node class is really a stub where global common behavior might be added. In this light, you might see yn is actually stripped down compared to what might have been put in a base "object" class.
This is one reason Wil needn't worry about slight variation in cost for node refcounting. Having already decided nodes are heavyweight, Wil commits to avoid making most objects nodes, because it's costly. So nodes are objects with low population counts, but needing as much fancy support as they can get. Or nodes are objects whose size is substantially more than sizeof(yn) — like pages and books — so the extra cost of yn is not significant, especially since managing large objects might normally already be costly.
In some applications, memory allocation itself is costly when it fragments memory and pressure from high volumes of processing traffic make non-static allocation expensive. In this sort of context, using the node api for allocation is a way to manage pools of pre-allocated objects, with low free node counts acting as back pressure to throttle further requests processing.
The refcounting node api shown here is a kitchen sink version, including most things you might want to do (with the exception of missing backtrace audits as noted earlier).
Most of Wil's day jobs use stripped down versions with unused parts removed, because coworkers find them disturbing — superfluous code looks like over-engineering, and poisons first impressions with folks who prefer simple over correct. (Yes, many folks prefer incorrect code as long as it's simple and failures occur sufficiently far in the future.)
It's easier to remove features than add them. Just cut anything you don't need: hack away, suit yourself.
Wil is tempted to post a version using one refcount only instead of counting both refs and uses separately, because cyclic ref graphs seldom occur. One count is much simpler, but a two-count shown below supports weak refs, and Wil wants this page to show a good approach to weak references.
When Wil refcounts objects, the amount of time he spends changing refcounts is carefully designed not to matter very much. For example, not every object need be refcounted, and the fewer the better when you want fewer degrees of freedom in a system permitting odd behvior. Wil's nodes and handles look more expensive than simpler refcounting — but Wil aims to make up for it by refcounting less often.
Back in the 80's in college, Wil thought graph theory was cool when exposed during his computer science curriculum. While graphs never became a main part of every day calculations when solving normal problems, Wil found the central metaphor of graphs very helpful. Wil started telling others, "Everything in computing systems is just a graph." Systems were just code and data arranged in graphs, and you could explain everything that happened as operations on the graph describing your system. In other words, a graph view is inclusive: you can model any other view you like as a graph.
For example, you can think of structs and records — and any other sort of object — as a node in a graph. And an arc is anything that connects one node to another: a pointer, a unqiue ID, a name, or more generally any key in a map whose value is the node. (You can think of an address space as a map with address keys as arcs and memory block values as nodes.)
Wil's use of term node for a refcounted object is consistent with this view, if graph nodes are object state. In this context, an arc is anything that points at something else — but more specifically a yht<N> node handle is an arc pointing at the node it references. Arcs in the form of handles are usually embedded in other nodes as members. So Wil sometimes use the term arc to mean a member variable in an object referring to another object.
When debug printing data structures, Wil thinks of this as printing part of a system graph reachable from a particular node. A nested tree structure shows each child node at greater indentation than its parent node. (Obviously in the presence of cycles, cite format must be used to force a tree so a printed graph is acyclic.) But the arcs in the graph are — by convention — seldom labeled this way when printing. However, you might as well say the arc for each node printed is the name of the reference in the parent node: usually a handle member variable or a collection of handles.
This explains the use of "arc" in the printed format of nodes: it's the name of whatever pointed at a node causing that node to be printed. At the topmost level, starting with a first node printed — the root of the graph being shown — the "arc" might be the reason you decided to print a node, if a print method has an arc name argument.
The following inline template methods are type-safe versions of yn::ncow() and yn::ncowz() shown earlier (cf «, «). Wil thought they seemed the right thing to do, but these have not seen much use and debugging yet.
In both these cow methods, note use of a temporary handle to receive a first ref to a cloned node if this happens, partly to ensure no complex sequence of refcount releases can cause the original node to disappear during a clone call if one occurs.
If a new node is returned, the old original node is not released until the guard handle is destroyed, since by then hswap() will have put the original ref there.
Note the casts and assignment operators used above link code implementions called on this page, so you can see what happens.
The y8vn class shown below is a sample node subclass illustrating heap storage of yv run instances in refcounted node format. The result is a refcounted octet string format suitable for prototyping applications of refcounted strings.
(In fact, something almost identical to y8vn has been used in some of Wil's past day jobs because it was close enough to what was desired, even with the creepy absence of string pools for better long term fragmentation avoidance.)
The last prototype of the deck demo done several years ago was based on this y8vn prototype, as you can see below in sample code using a deck instance to test behavior of y8vn. But a new future deck version will replace y8vn with a better node subclass.
When you examine y8vn's heap allocation behavior, you can see it uses malloc() and free() directly in a slightly funky way via operator new(). It was very tempting to clean this up with a new api using a yH heap for allocation.
In short, y8vn is almost but not quite a throw-away sample code class. It's good enough for production use if you already blithely use malloc() and free() without any fragmentation concerns (which is not a good idea). But Wil thinks it's a little creepy, and best reserved for experimentation and prototyping on the way more specific stable variations tuned for specific usage contexts.
The name y8vn means thorn u8 vector node; it's basically a node version of yv in which the u8 part is implied since unspecified. But since node-based vectors might later come in many flavors, here it's best to explicitly note 8-bit format in the name.
The comment above explains a guaranteed property of y8vn not generally true of yv run instances in general: the byte at v_p[v_n] (when converted to yv) contains a null byte, so the format is also a valid C string even though yv typically is not. For this reason, the api supports a c_str() method imitating std::string.
class y8vn «
The value of m_before must equal 0xBB for any given y8vn to be valid. This is the "before" guard byte used to detect underwrites clobbering the node before a first content byte at m_dat[0].
The octet at m_dat[m_len] must contain zero and m_dat[m_len+1] must contain 0xAA, which is the "after" guard byte detecting overwrites.
The declaration of m_dat[4] reserves four bytes for content above and beyond m_len extra bytes allocated to hold more. So y8vn allocates sizeof(y8vn)+m_len bytes in order to simplify arithmetic while ensuring more than enough bytes are present for guards.
A large number of inline consructors are defined below. Some of them copy an input octet sequence into space allocated, and some of them do nothing more than establish guard bytes and length.