From 7d3e2bd2c4cfd1296d1d6f996d7548de26540d41 Mon Sep 17 00:00:00 2001 From: Josh Haberman Date: Fri, 15 Feb 2013 16:27:18 -0800 Subject: Sync with 8 months of Google-internal development. Many things have changed and been simplified. The memory-management story for upb_def and upb_handlers is much more robust; upb_def and upb_handlers should be fairly stable interfaces now. There is still much work to do for the runtime component (upb_sink). --- upb/refcounted.c | 776 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 776 insertions(+) create mode 100644 upb/refcounted.c (limited to 'upb/refcounted.c') diff --git a/upb/refcounted.c b/upb/refcounted.c new file mode 100644 index 0000000..54ad735 --- /dev/null +++ b/upb/refcounted.c @@ -0,0 +1,776 @@ +/* + * upb - a minimalist implementation of protocol buffers. + * + * Copyright (c) 2012 Google Inc. See LICENSE for details. + * Author: Josh Haberman + * + * Our key invariants are: + * 1. reference cycles never span groups + * 2. for ref2(to, from), we increment to's count iff group(from) != group(to) + * + * The previous two are how we avoid leaking cycles. Other important + * invariants are: + * 3. for mutable objects "from" and "to", if there exists a ref2(to, from) + * this implies group(from) == group(to). (In practice, what we implement + * is even stronger; "from" and "to" will share a group if there has *ever* + * been a ref2(to, from), but all that is necessary for correctness is the + * weaker one). + * 4. mutable and immutable objects are never in the same group. + */ + +#include "upb/refcounted.h" + +#include +#include + +uint32_t static_refcount = 1; + +/* arch-specific atomic primitives *******************************************/ + +#ifdef UPB_THREAD_UNSAFE ////////////////////////////////////////////////////// + +static void atomic_inc(uint32_t *a) { (*a)++; } +static bool atomic_dec(uint32_t *a) { return --(*a) == 0; } + +#elif (__GNUC__ == 4 && __GNUC_MINOR__ >= 1) || __GNUC__ > 4 /////////////////// + +static void atomic_inc(uint32_t *a) { __sync_fetch_and_add(a, 1); } +static bool atomic_dec(uint32_t *a) { return __sync_sub_and_fetch(a, 1) == 0; } + +#elif defined(WIN32) /////////////////////////////////////////////////////////// + +#include + +static void atomic_inc(upb_atomic_t *a) { InterlockedIncrement(&a->val); } +static bool atomic_dec(upb_atomic_t *a) { + return InterlockedDecrement(&a->val) == 0; +} + +#else +#error Atomic primitives not defined for your platform/CPU. \ + Implement them or compile with UPB_THREAD_UNSAFE. +#endif + + +/* Reference tracking (debug only) ********************************************/ + +#ifdef UPB_DEBUG_REFS + +#ifdef UPB_THREAD_UNSAFE + +static void upb_lock() {} +static void upb_unlock() {} + +#else + +// User must define functions that lock/unlock a global mutex and link this +// file against them. +void upb_lock(); +void upb_unlock(); + +#endif + +// UPB_DEBUG_REFS mode counts on being able to malloc() memory in some +// code-paths that can normally never fail, like upb_refcounted_ref(). Since +// we have no way to propagage out-of-memory errors back to the user, and since +// these errors can only occur in UPB_DEBUG_REFS mode, we immediately fail. +#define CHECK_OOM(predicate) assert(predicate) + +typedef struct { + const upb_refcounted *obj; // Object we are taking a ref on. + int count; // How many refs there are (duplicates only allowed for ref2). + bool is_ref2; +} trackedref; + +trackedref *trackedref_new(const upb_refcounted *obj, bool is_ref2) { + trackedref *ret = malloc(sizeof(*ret)); + CHECK_OOM(ret); + ret->obj = obj; + ret->count = 1; + ret->is_ref2 = is_ref2; + return ret; +} + +// A reversible function for obfuscating a uintptr_t. +// This depends on sizeof(uintptr_t) <= sizeof(uint64_t), so would fail +// on 128-bit machines. +static uintptr_t obfuscate(const void *x) { return ~(uintptr_t)x; } + +static upb_value obfuscate_v(const void *x) { + return upb_value_uint64(obfuscate(x)); +} + +static const void *unobfuscate_v(upb_value x) { + return (void*)~upb_value_getuint64(x); +} + +// +// Stores tracked references according to the following scheme: +// (upb_inttable)reftracks = { +// (void*)owner -> (upb_inttable*) = { +// obfuscate((upb_refcounted*)obj) -> obfuscate((trackedref*)is_ref2) +// } +// } +// +// obfuscate() is a function that hides the link from the heap checker, so +// that it is not followed for the purposes of deciding what has "indirectly +// leaked." Even though we have a pointer to the trackedref*, we want it to +// appear leaked if it is not freed. +// +// This scheme gives us the following desirable properties: +// +// 1. We can easily determine whether an (owner->obj) ref already exists +// and error out if a duplicate ref is taken. +// +// 2. Because the trackedref is allocated with malloc() at the point that +// the ref is taken, that memory will be leaked if the ref is not released. +// Because the malloc'd memory points to the refcounted object, the object +// itself will only be considered "indirectly leaked" by smart memory +// checkers like Valgrind. This will correctly blame the ref leaker +// instead of the innocent code that allocated the object to begin with. +// +// 3. We can easily enumerate all of the ref2 refs for a given owner, which +// allows us to double-check that the object's visit() function is +// correctly implemented. +// +static upb_inttable reftracks = UPB_EMPTY_INTTABLE_INIT(UPB_CTYPE_PTR); + +static upb_inttable *trygettab(const void *p) { + const upb_value *v = upb_inttable_lookupptr(&reftracks, p); + return v ? upb_value_getptr(*v) : NULL; +} + +// Gets or creates the tracking table for the given owner. +static upb_inttable *gettab(const void *p) { + upb_inttable *tab = trygettab(p); + if (tab == NULL) { + tab = malloc(sizeof(*tab)); + CHECK_OOM(tab); + upb_inttable_init(tab, UPB_CTYPE_UINT64); + upb_inttable_insertptr(&reftracks, p, upb_value_ptr(tab)); + } + return tab; +} + +static void track(const upb_refcounted *r, const void *owner, bool ref2) { + upb_lock(); + upb_inttable *refs = gettab(owner); + const upb_value *v = upb_inttable_lookup(refs, obfuscate(r)); + if (v) { + trackedref *ref = (trackedref*)unobfuscate_v(*v); + // Since we allow multiple ref2's for the same to/from pair without + // allocating separate memory for each one, we lose the fine-grained + // tracking behavior we get with regular refs. Since ref2s only happen + // inside upb, we'll accept this limitation until/unless there is a really + // difficult upb-internal bug that can't be figured out without it. + assert(ref2); + assert(ref->is_ref2); + ref->count++; + } else { + trackedref *ref = trackedref_new(r, ref2); + bool ok = upb_inttable_insert(refs, obfuscate(r), obfuscate_v(ref)); + CHECK_OOM(ok); + } + upb_unlock(); +} + +static void untrack(const upb_refcounted *r, const void *owner, bool ref2) { + upb_lock(); + upb_inttable *refs = gettab(owner); + const upb_value *v = upb_inttable_lookup(refs, obfuscate(r)); + // This assert will fail if an owner attempts to release a ref it didn't have. + assert(v); + trackedref *ref = (trackedref*)unobfuscate_v(*v); + assert(ref->is_ref2 == ref2); + if (--ref->count == 0) { + free(ref); + upb_inttable_remove(refs, obfuscate(r), NULL); + if (upb_inttable_count(refs) == 0) { + upb_inttable_uninit(refs); + free(refs); + upb_inttable_removeptr(&reftracks, owner, NULL); + } + } + upb_unlock(); +} + +static void checkref(const upb_refcounted *r, const void *owner, bool ref2) { + upb_lock(); + upb_inttable *refs = gettab(owner); + const upb_value *v = upb_inttable_lookup(refs, obfuscate(r)); + assert(v); + trackedref *ref = (trackedref*)unobfuscate_v(*v); + assert(ref->obj == r); + assert(ref->is_ref2 == ref2); + upb_unlock(); +} + +// Populates the given UPB_CTYPE_INT32 inttable with counts of ref2's that +// originate from the given owner. +static void getref2s(const upb_refcounted *owner, upb_inttable *tab) { + upb_lock(); + upb_inttable *refs = trygettab(owner); + if (refs) { + upb_inttable_iter i; + upb_inttable_begin(&i, refs); + for(; !upb_inttable_done(&i); upb_inttable_next(&i)) { + trackedref *ref = (trackedref*)unobfuscate_v(upb_inttable_iter_value(&i)); + if (ref->is_ref2) { + upb_value count = upb_value_int32(ref->count); + bool ok = upb_inttable_insertptr(tab, ref->obj, count); + CHECK_OOM(ok); + } + } + } + upb_unlock(); +} + +typedef struct { + upb_inttable ref2; + const upb_refcounted *obj; +} check_state; + +static void visit_check(const upb_refcounted *obj, const upb_refcounted *subobj, + void *closure) { + check_state *s = closure; + assert(obj == s->obj); + assert(subobj); + upb_inttable *ref2 = &s->ref2; + upb_value v; + bool removed = upb_inttable_removeptr(ref2, subobj, &v); + // The following assertion will fail if the visit() function visits a subobj + // that it did not have a ref2 on, or visits the same subobj too many times. + assert(removed); + int32_t newcount = upb_value_getint32(v) - 1; + if (newcount > 0) { + upb_inttable_insert(ref2, (uintptr_t)subobj, upb_value_int32(newcount)); + } +} + +static void visit(const upb_refcounted *r, upb_refcounted_visit *v, + void *closure) { + // In DEBUG_REFS mode we know what existing ref2 refs there are, so we know + // exactly the set of nodes that visit() should visit. So we verify visit()'s + // correctness here. + check_state state; + state.obj = r; + bool ok = upb_inttable_init(&state.ref2, UPB_CTYPE_INT32); + CHECK_OOM(ok); + getref2s(r, &state.ref2); + + // This should visit any children in the ref2 table. + if (r->vtbl->visit) r->vtbl->visit(r, visit_check, &state); + + // This assertion will fail if the visit() function missed any children. + assert(upb_inttable_count(&state.ref2) == 0); + upb_inttable_uninit(&state.ref2); + if (r->vtbl->visit) r->vtbl->visit(r, v, closure); +} + +#else + +static void track(const upb_refcounted *r, const void *owner, bool ref2) { + UPB_UNUSED(r); + UPB_UNUSED(owner); + UPB_UNUSED(ref2); +} + +static void untrack(const upb_refcounted *r, const void *owner, bool ref2) { + UPB_UNUSED(r); + UPB_UNUSED(owner); + UPB_UNUSED(ref2); +} + +static void checkref(const upb_refcounted *r, const void *owner, bool ref2) { + UPB_UNUSED(r); + UPB_UNUSED(owner); + UPB_UNUSED(ref2); +} + +static void visit(const upb_refcounted *r, upb_refcounted_visit *v, + void *closure) { + if (r->vtbl->visit) r->vtbl->visit(r, v, closure); +} + +#endif // UPB_DEBUG_REFS + + +/* freeze() *******************************************************************/ + +// The freeze() operation is by far the most complicated part of this scheme. +// We compute strongly-connected components and then mutate the graph such that +// we preserve the invariants documented at the top of this file. And we must +// handle out-of-memory errors gracefully (without leaving the graph +// inconsistent), which adds to the fun. + +// The state used by the freeze operation (shared across many functions). +typedef struct { + int depth; + int maxdepth; + uint64_t index; + // Maps upb_refcounted* -> attributes (color, etc). attr layout varies by + // color. + upb_inttable objattr; + upb_inttable stack; // stack of upb_refcounted* for Tarjan's algorithm. + upb_inttable groups; // array of uint32_t*, malloc'd refcounts for new groups + upb_status *status; + jmp_buf err; +} tarjan; + +static void release_ref2(const upb_refcounted *obj, + const upb_refcounted *subobj, + void *closure); + +// Node attributes ///////////////////////////////////////////////////////////// + +// After our analysis phase all nodes will be either GRAY or WHITE. + +typedef enum { + BLACK = 0, // Object has not been seen. + GRAY, // Object has been found via a refgroup but may not be reachable. + GREEN, // Object is reachable and is currently on the Tarjan stack. + WHITE, // Object is reachable and has been assigned a group (SCC). +} color_t; + +UPB_NORETURN static void err(tarjan *t) { longjmp(t->err, 1); } +UPB_NORETURN static void oom(tarjan *t) { + upb_status_seterrliteral(t->status, "out of memory"); + err(t); +} + +uint64_t trygetattr(const tarjan *t, const upb_refcounted *r) { + const upb_value *v = upb_inttable_lookupptr(&t->objattr, r); + return v ? upb_value_getuint64(*v) : 0; +} + +uint64_t getattr(const tarjan *t, const upb_refcounted *r) { + const upb_value *v = upb_inttable_lookupptr(&t->objattr, r); + assert(v); + return upb_value_getuint64(*v); +} + +void setattr(tarjan *t, const upb_refcounted *r, uint64_t attr) { + upb_inttable_removeptr(&t->objattr, r, NULL); + upb_inttable_insertptr(&t->objattr, r, upb_value_uint64(attr)); +} + +static color_t color(tarjan *t, const upb_refcounted *r) { + return trygetattr(t, r) & 0x3; // Color is always stored in the low 2 bits. +} + +static void set_gray(tarjan *t, const upb_refcounted *r) { + assert(color(t, r) == BLACK); + setattr(t, r, GRAY); +} + +// Pushes an obj onto the Tarjan stack and sets it to GREEN. +static void push(tarjan *t, const upb_refcounted *r) { + assert(color(t, r) == BLACK || color(t, r) == GRAY); + // This defines the attr layout for the GREEN state. "index" and "lowlink" + // get 31 bits, which is plenty (limit of 2B objects frozen at a time). + setattr(t, r, GREEN | (t->index << 2) | (t->index << 33)); + if (++t->index == 0x80000000) { + upb_status_seterrliteral(t->status, "too many objects to freeze"); + err(t); + } + upb_inttable_push(&t->stack, upb_value_ptr((void*)r)); +} + +// Pops an obj from the Tarjan stack and sets it to WHITE, with a ptr to its +// SCC group. +static upb_refcounted *pop(tarjan *t) { + upb_refcounted *r = upb_value_getptr(upb_inttable_pop(&t->stack)); + assert(color(t, r) == GREEN); + // This defines the attr layout for nodes in the WHITE state. + // Top of group stack is [group, NULL]; we point at group. + setattr(t, r, WHITE | (upb_inttable_count(&t->groups) - 2) << 8); + return r; +} + +static void newgroup(tarjan *t) { + uint32_t *group = malloc(sizeof(*group)); + if (!group) oom(t); + // Push group and empty group leader (we'll fill in leader later). + if (!upb_inttable_push(&t->groups, upb_value_ptr(group)) || + !upb_inttable_push(&t->groups, upb_value_ptr(NULL))) { + free(group); + oom(t); + } + *group = 0; +} + +static uint32_t idx(tarjan *t, const upb_refcounted *r) { + assert(color(t, r) == GREEN); + return (getattr(t, r) >> 2) & 0x7FFFFFFF; +} + +static uint32_t lowlink(tarjan *t, const upb_refcounted *r) { + if (color(t, r) == GREEN) { + return getattr(t, r) >> 33; + } else { + return UINT32_MAX; + } +} + +static void set_lowlink(tarjan *t, const upb_refcounted *r, uint32_t lowlink) { + assert(color(t, r) == GREEN); + setattr(t, r, ((uint64_t)lowlink << 33) | (getattr(t, r) & 0x1FFFFFFFF)); +} + +uint32_t *group(tarjan *t, upb_refcounted *r) { + assert(color(t, r) == WHITE); + uint64_t groupnum = getattr(t, r) >> 8; + const upb_value *v = upb_inttable_lookup(&t->groups, groupnum); + assert(v); + return upb_value_getptr(*v); +} + +// If the group leader for this object's group has not previously been set, +// the given object is assigned to be its leader. +static upb_refcounted *groupleader(tarjan *t, upb_refcounted *r) { + assert(color(t, r) == WHITE); + uint64_t leader_slot = (getattr(t, r) >> 8) + 1; + const upb_value *v = upb_inttable_lookup(&t->groups, leader_slot); + assert(v); + if (upb_value_getptr(*v)) { + return upb_value_getptr(*v); + } else { + upb_inttable_remove(&t->groups, leader_slot, NULL); + upb_inttable_insert(&t->groups, leader_slot, upb_value_ptr(r)); + return r; + } +} + + +// Tarjan's algorithm ////////////////////////////////////////////////////////// + +// See: +// http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm +static void do_tarjan(const upb_refcounted *obj, tarjan *t); + +static void tarjan_visit(const upb_refcounted *obj, + const upb_refcounted *subobj, + void *closure) { + tarjan *t = closure; + if (++t->depth > t->maxdepth) { + upb_status_seterrf(t->status, "graph too deep to freeze (%d)", t->maxdepth); + err(t); + } else if (subobj->is_frozen || color(t, subobj) == WHITE) { + // Do nothing: we don't want to visit or color already-frozen nodes, + // and WHITE nodes have already been assigned a SCC. + } else if (color(t, subobj) < GREEN) { + // Subdef has not yet been visited; recurse on it. + do_tarjan(subobj, t); + set_lowlink(t, obj, UPB_MIN(lowlink(t, obj), lowlink(t, subobj))); + } else if (color(t, subobj) == GREEN) { + // Subdef is in the stack and hence in the current SCC. + set_lowlink(t, obj, UPB_MIN(lowlink(t, obj), idx(t, subobj))); + } + --t->depth; +} + +static void do_tarjan(const upb_refcounted *obj, tarjan *t) { + if (color(t, obj) == BLACK) { + // We haven't seen this object's group; mark the whole group GRAY. + const upb_refcounted *o = obj; + do { set_gray(t, o); } while ((o = o->next) != obj); + } + + push(t, obj); + visit(obj, tarjan_visit, t); + if (lowlink(t, obj) == idx(t, obj)) { + newgroup(t); + while (pop(t) != obj) + ; + } +} + + +// freeze() //////////////////////////////////////////////////////////////////// + +static void crossref(const upb_refcounted *r, const upb_refcounted *subobj, + void *_t) { + tarjan *t = _t; + assert(color(t, r) > BLACK); + if (color(t, subobj) > BLACK && r->group != subobj->group) { + // Previously this ref was not reflected in subobj->group because they + // were in the same group; now that they are split a ref must be taken. + atomic_inc(subobj->group); + } +} + +static bool freeze(upb_refcounted *const*roots, int n, upb_status *s) { + volatile bool ret = false; + + // We run in two passes so that we can allocate all memory before performing + // any mutation of the input -- this allows us to leave the input unchanged + // in the case of memory allocation failure. + tarjan t; + t.index = 0; + t.depth = 0; + t.maxdepth = UPB_MAX_TYPE_DEPTH * 2; // May want to make this a parameter. + t.status = s; + if (!upb_inttable_init(&t.objattr, UPB_CTYPE_UINT64)) goto err1; + if (!upb_inttable_init(&t.stack, UPB_CTYPE_PTR)) goto err2; + if (!upb_inttable_init(&t.groups, UPB_CTYPE_PTR)) goto err3; + if (setjmp(t.err) != 0) goto err4; + + + for (int i = 0; i < n; i++) { + if (color(&t, roots[i]) < GREEN) { + do_tarjan(roots[i], &t); + } + } + + // If we've made it this far, no further errors are possible so it's safe to + // mutate the objects without risk of leaving them in an inconsistent state. + ret = true; + + // The transformation that follows requires care. The preconditions are: + // - all objects in attr map are WHITE or GRAY, and are in mutable groups + // (groups of all mutable objs) + // - no ref2(to, from) refs have incremented count(to) if both "to" and + // "from" are in our attr map (this follows from invariants (2) and (3)) + + // Pass 1: we remove WHITE objects from their mutable groups, and add them to + // new groups according to the SCC's we computed. These new groups will + // consist of only frozen objects. None will be immediately collectible, + // because WHITE objects are by definition reachable from one of "roots", + // which the caller must own refs on. + upb_inttable_iter i; + upb_inttable_begin(&i, &t.objattr); + for(; !upb_inttable_done(&i); upb_inttable_next(&i)) { + upb_refcounted *obj = (upb_refcounted*)upb_inttable_iter_key(&i); + // Since removal from a singly-linked list requires access to the object's + // predecessor, we consider obj->next instead of obj for moving. With the + // while() loop we guarantee that we will visit every node's predecessor. + // Proof: + // 1. every node's predecessor is in our attr map. + // 2. though the loop body may change a node's predecessor, it will only + // change it to be the node we are currently operating on, so with a + // while() loop we guarantee ourselves the chance to remove each node. + while (color(&t, obj->next) == WHITE && + group(&t, obj->next) != obj->next->group) { + // Remove from old group. + upb_refcounted *move = obj->next; + if (obj == move) { + // Removing the last object from a group. + assert(*obj->group == obj->individual_count); + free(obj->group); + } else { + obj->next = move->next; + // This may decrease to zero; we'll collect GRAY objects (if any) that + // remain in the group in the third pass. + assert(*move->group >= move->individual_count); + *move->group -= move->individual_count; + } + + // Add to new group. + upb_refcounted *leader = groupleader(&t, move); + if (move == leader) { + // First object added to new group is its leader. + move->group = group(&t, move); + move->next = move; + *move->group = move->individual_count; + } else { + // Group already has at least one object in it. + assert(leader->group == group(&t, move)); + move->group = group(&t, move); + move->next = leader->next; + leader->next = move; + *move->group += move->individual_count; + } + + move->is_frozen = true; + } + } + + // Pass 2: GRAY and WHITE objects "obj" with ref2(to, obj) references must + // increment count(to) if group(obj) != group(to) (which could now be the + // case if "to" was just frozen). + upb_inttable_begin(&i, &t.objattr); + for(; !upb_inttable_done(&i); upb_inttable_next(&i)) { + upb_refcounted *obj = (upb_refcounted*)upb_inttable_iter_key(&i); + visit(obj, crossref, &t); + } + + // Pass 3: GRAY objects are collected if their group's refcount dropped to + // zero when we removed its white nodes. This can happen if they had only + // been kept alive by virtue of sharing a group with an object that was just + // frozen. + // + // It is important that we do this last, since the GRAY object's free() + // function could call unref2() on just-frozen objects, which will decrement + // refs that were added in pass 2. + upb_inttable_begin(&i, &t.objattr); + for(; !upb_inttable_done(&i); upb_inttable_next(&i)) { + upb_refcounted *obj = (upb_refcounted*)upb_inttable_iter_key(&i); + if (obj->group == NULL || *obj->group == 0) { + if (obj->group) { + // We eagerly free() the group's count (since we can't easily determine + // the group's remaining size it's the easiest way to ensure it gets + // done). + free(obj->group); + + // Visit to release ref2's (done in a separate pass since release_ref2 + // depends on o->group being unmodified so it can test merged()). + upb_refcounted *o = obj; + do { visit(o, release_ref2, NULL); } while ((o = o->next) != obj); + + // Mark "group" fields as NULL so we know to free the objects later in + // this loop, but also don't try to delete the group twice. + o = obj; + do { o->group = NULL; } while ((o = o->next) != obj); + } + obj->vtbl->free(obj); + } + } + +err4: + if (!ret) { + upb_inttable_begin(&i, &t.groups); + for(; !upb_inttable_done(&i); upb_inttable_next(&i)) + free(upb_value_getptr(upb_inttable_iter_value(&i))); + } + upb_inttable_uninit(&t.groups); +err3: + upb_inttable_uninit(&t.stack); +err2: + upb_inttable_uninit(&t.objattr); +err1: + return ret; +} + + +/* Misc internal functions ***************************************************/ + +static bool merged(const upb_refcounted *r, const upb_refcounted *r2) { + return r->group == r2->group; +} + +static void merge(upb_refcounted *r, upb_refcounted *from) { + if (merged(r, from)) return; + *r->group += *from->group; + free(from->group); + upb_refcounted *base = from; + + // Set all refcount pointers in the "from" chain to the merged refcount. + // + // TODO(haberman): this linear algorithm can result in an overall O(n^2) bound + // if the user continuously extends a group by one object. Prevent this by + // using one of the techniques in this paper: + // ftp://www.ncedc.org/outgoing/geomorph/dino/orals/p245-tarjan.pdf + do { from->group = r->group; } while ((from = from->next) != base); + + // Merge the two circularly linked lists by swapping their next pointers. + upb_refcounted *tmp = r->next; + r->next = base->next; + base->next = tmp; +} + +static void unref(const upb_refcounted *r); + +static void release_ref2(const upb_refcounted *obj, + const upb_refcounted *subobj, + void *closure) { + UPB_UNUSED(closure); + if (!merged(obj, subobj)) { + assert(subobj->is_frozen); + unref(subobj); + } + untrack(subobj, obj, true); +} + +static void unref(const upb_refcounted *r) { + if (atomic_dec(r->group)) { + free(r->group); + + // In two passes, since release_ref2 needs a guarantee that any subobjs + // are alive. + const upb_refcounted *o = r; + do { visit(o, release_ref2, NULL); } while((o = o->next) != r); + + o = r; + do { + const upb_refcounted *next = o->next; + assert(o->is_frozen || o->individual_count == 0); + o->vtbl->free((upb_refcounted*)o); + o = next; + } while(o != r); + } +} + + +/* Public interface ***********************************************************/ + +bool upb_refcounted_init(upb_refcounted *r, + const struct upb_refcounted_vtbl *vtbl, + const void *owner) { + r->next = r; + r->vtbl = vtbl; + r->individual_count = 0; + r->is_frozen = false; + r->group = malloc(sizeof(*r->group)); + if (!r->group) return false; + *r->group = 0; + upb_refcounted_ref(r, owner); + return true; +} + +bool upb_refcounted_isfrozen(const upb_refcounted *r) { + return r->is_frozen; +} + +void upb_refcounted_ref(const upb_refcounted *r, const void *owner) { + if (!r->is_frozen) + ((upb_refcounted*)r)->individual_count++; + atomic_inc(r->group); + track(r, owner, false); +} + +void upb_refcounted_unref(const upb_refcounted *r, const void *owner) { + if (!r->is_frozen) + ((upb_refcounted*)r)->individual_count--; + unref(r); + untrack(r, owner, false); +} + +void upb_refcounted_ref2(const upb_refcounted *r, upb_refcounted *from) { + assert(!from->is_frozen); // Non-const pointer implies this. + if (r->is_frozen) { + atomic_inc(r->group); + } else { + merge((upb_refcounted*)r, from); + } + track(r, from, true); +} + +void upb_refcounted_unref2(const upb_refcounted *r, upb_refcounted *from) { + assert(!from->is_frozen); // Non-const pointer implies this. + if (r->is_frozen) { + unref(r); + } else { + assert(merged(r, from)); + } + untrack(r, from, true); +} + +void upb_refcounted_donateref( + const upb_refcounted *r, const void *from, const void *to) { + assert(from != to); + assert(to != NULL); + upb_refcounted_ref(r, to); + if (from != NULL) + upb_refcounted_unref(r, from); +} + +void upb_refcounted_checkref(const upb_refcounted *r, const void *owner) { + checkref(r, owner, false); +} + +bool upb_refcounted_freeze(upb_refcounted *const*roots, int n, upb_status *s) { + for (int i = 0; i < n; i++) { + assert(!roots[i]->is_frozen); + } + return freeze(roots, n, s); +} -- cgit v1.2.3