From 26d98ca94f2f049e8767b4a9a33d185a3d7ea0fd Mon Sep 17 00:00:00 2001 From: Josh Haberman Date: Thu, 24 Oct 2013 12:43:19 -0700 Subject: Merge from Google-internal development: - rewritten decoder; interpreted decoder is bytecode-based, JIT decoder no longer falls back to the interpreter. - C++ improvements: C++11-compatible iterators, upb::reffed_ptr for RAII refcounting, better upcast/downcast support. - removed the gross upb_value abstraction from public upb.h. --- upb/refcounted.c | 200 ++++++++++++++++++++++++++----------------------------- 1 file changed, 95 insertions(+), 105 deletions(-) (limited to 'upb/refcounted.c') diff --git a/upb/refcounted.c b/upb/refcounted.c index 1e517b7..fbeca64 100644 --- a/upb/refcounted.c +++ b/upb/refcounted.c @@ -24,6 +24,7 @@ #include uint32_t static_refcount = 1; +static void freeobj(upb_refcounted *o); /* arch-specific atomic primitives *******************************************/ @@ -74,90 +75,26 @@ void upb_unlock(); // 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) +#define CHECK_OOM(predicate) if (!(predicate)) { assert(predicate); exit(1); } 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 *trackedref_new(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) { - upb_value v; - return upb_inttable_lookupptr(&reftracks, p, &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); upb_value v; - if (upb_inttable_lookup(refs, obfuscate(r), &v)) { - trackedref *ref = (trackedref*)unobfuscate_v(v); + if (upb_inttable_lookupptr(r->refs, owner, &v)) { + trackedref *ref = upb_value_getptr(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 @@ -167,29 +104,38 @@ static void track(const upb_refcounted *r, const void *owner, bool 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)); + trackedref *ref = trackedref_new(ref2); + bool ok = upb_inttable_insertptr(r->refs, owner, upb_value_ptr(ref)); CHECK_OOM(ok); + if (ref2) { + // We know this cast is safe when it is a ref2, because it's coming from + // another refcounted object. + const upb_refcounted *from = owner; + assert(!upb_inttable_lookupptr(from->ref2s, r, NULL)); + ok = upb_inttable_insertptr(from->ref2s, r, upb_value_ptr(NULL)); + CHECK_OOM(ok); + } } upb_unlock(); } static void untrack(const upb_refcounted *r, const void *owner, bool ref2) { upb_lock(); - upb_inttable *refs = gettab(owner); upb_value v; - bool found = upb_inttable_lookup(refs, obfuscate(r), &v); + bool found = upb_inttable_lookupptr(r->refs, owner, &v); // This assert will fail if an owner attempts to release a ref it didn't have. UPB_ASSERT_VAR(found, found); - trackedref *ref = (trackedref*)unobfuscate_v(v); + trackedref *ref = upb_value_getptr(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_inttable_removeptr(r->refs, owner, NULL); + if (ref2) { + // We know this cast is safe when it is a ref2, because it's coming from + // another refcounted object. + const upb_refcounted *from = owner; + bool removed = upb_inttable_removeptr(from->ref2s, r, NULL); + assert(removed); } } upb_unlock(); @@ -197,12 +143,10 @@ static void untrack(const upb_refcounted *r, const void *owner, bool ref2) { static void checkref(const upb_refcounted *r, const void *owner, bool ref2) { upb_lock(); - upb_inttable *refs = gettab(owner); upb_value v; - bool found = upb_inttable_lookup(refs, obfuscate(r), &v); + bool found = upb_inttable_lookupptr(r->refs, owner, &v); UPB_ASSERT_VAR(found, found); - trackedref *ref = (trackedref*)unobfuscate_v(v); - assert(ref->obj == r); + trackedref *ref = upb_value_getptr(v); assert(ref->is_ref2 == ref2); upb_unlock(); } @@ -211,18 +155,20 @@ static void checkref(const upb_refcounted *r, const void *owner, bool ref2) { // 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_inttable_iter i; + upb_inttable_begin(&i, owner->ref2s); + for(; !upb_inttable_done(&i); upb_inttable_next(&i)) { + upb_refcounted *to = (upb_refcounted*)upb_inttable_iter_key(&i); + + // To get the count we need to look in the target's table. + upb_value v; + bool found = upb_inttable_lookupptr(to->refs, owner, &v); + assert(found); + trackedref *ref = upb_value_getptr(v); + upb_value count = upb_value_int32(ref->count); + + bool ok = upb_inttable_insertptr(tab, to, count); + CHECK_OOM(ok); } upb_unlock(); } @@ -269,6 +215,30 @@ static void visit(const upb_refcounted *r, upb_refcounted_visit *v, if (r->vtbl->visit) r->vtbl->visit(r, v, closure); } +static bool trackinit(upb_refcounted *r) { + r->refs = malloc(sizeof(*r->refs)); + r->ref2s = malloc(sizeof(*r->ref2s)); + if (!r->refs || !r->ref2s) goto err1; + + if (!upb_inttable_init(r->refs, UPB_CTYPE_PTR)) goto err1; + if (!upb_inttable_init(r->ref2s, UPB_CTYPE_PTR)) goto err2; + return true; + +err2: + upb_inttable_uninit(r->refs); +err1: + free(r->refs); + free(r->ref2s); + return false; +} + +static void trackfree(const upb_refcounted *r) { + upb_inttable_uninit(r->refs); + upb_inttable_uninit(r->ref2s); + free(r->refs); + free(r->ref2s); +} + #else static void track(const upb_refcounted *r, const void *owner, bool ref2) { @@ -289,6 +259,15 @@ static void checkref(const upb_refcounted *r, const void *owner, bool ref2) { UPB_UNUSED(ref2); } +static bool trackinit(upb_refcounted *r) { + UPB_UNUSED(r); + return true; +} + +static void trackfree(const upb_refcounted *r) { + UPB_UNUSED(r); +} + static void visit(const upb_refcounted *r, upb_refcounted_visit *v, void *closure) { if (r->vtbl->visit) r->vtbl->visit(r, v, closure); @@ -505,7 +484,8 @@ static void crossref(const upb_refcounted *r, const upb_refcounted *subobj, } } -static bool freeze(upb_refcounted *const*roots, int n, upb_status *s) { +static bool freeze(upb_refcounted *const*roots, int n, upb_status *s, + int maxdepth) { volatile bool ret = false; // We run in two passes so that we can allocate all memory before performing @@ -514,7 +494,7 @@ static bool freeze(upb_refcounted *const*roots, int n, upb_status *s) { tarjan t; t.index = 0; t.depth = 0; - t.maxdepth = UPB_MAX_TYPE_DEPTH * 2; // May want to make this a parameter. + t.maxdepth = maxdepth; 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; @@ -628,7 +608,7 @@ static bool freeze(upb_refcounted *const*roots, int n, upb_status *s) { o = obj; do { o->group = NULL; } while ((o = o->next) != obj); } - obj->vtbl->free(obj); + freeobj(obj); } } @@ -680,11 +660,11 @@ static void release_ref2(const upb_refcounted *obj, const upb_refcounted *subobj, void *closure) { UPB_UNUSED(closure); + untrack(subobj, obj, true); if (!merged(obj, subobj)) { assert(subobj->is_frozen); unref(subobj); } - untrack(subobj, obj, true); } static void unref(const upb_refcounted *r) { @@ -700,12 +680,17 @@ static void unref(const upb_refcounted *r) { do { const upb_refcounted *next = o->next; assert(o->is_frozen || o->individual_count == 0); - o->vtbl->free((upb_refcounted*)o); + freeobj((upb_refcounted*)o); o = next; } while(o != r); } } +static void freeobj(upb_refcounted *o) { + trackfree(o); + o->vtbl->free((upb_refcounted*)o); +} + /* Public interface ***********************************************************/ @@ -719,6 +704,10 @@ bool upb_refcounted_init(upb_refcounted *r, r->group = malloc(sizeof(*r->group)); if (!r->group) return false; *r->group = 0; + if (!trackinit(r)) { + free(r->group); + return false; + } upb_refcounted_ref(r, owner); return true; } @@ -728,37 +717,37 @@ bool upb_refcounted_isfrozen(const upb_refcounted *r) { } void upb_refcounted_ref(const upb_refcounted *r, const void *owner) { + track(r, owner, false); 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) { + untrack(r, owner, false); 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. + track(r, from, true); 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. + untrack(r, from, true); if (r->is_frozen) { unref(r); } else { assert(merged(r, from)); } - untrack(r, from, true); } void upb_refcounted_donateref( @@ -774,9 +763,10 @@ 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) { +bool upb_refcounted_freeze(upb_refcounted *const*roots, int n, upb_status *s, + int maxdepth) { for (int i = 0; i < n; i++) { assert(!roots[i]->is_frozen); } - return freeze(roots, n, s); + return freeze(roots, n, s, maxdepth); } -- cgit v1.2.3