static UWord stats__vts__join = 0; // # calls to VTS__join
static UWord stats__vts__cmpLEQ = 0; // # calls to VTS__cmpLEQ
static UWord stats__vts__cmp_structural = 0; // # calls to VTS__cmp_structural
-static UWord stats__vts__cmp_structural_slow = 0; // # calls to VTS__cmp_structural w/ slow case
-static UWord stats__vts__indexat_slow = 0; // # calls to VTS__indexAt_SLOW
-static UWord stats__vts_set__fadoa = 0; // # calls to vts_set__find_and_dealloc__or_add
-static UWord stats__vts_set__fadoa_d = 0; // # calls to vts_set__find_and_dealloc__or_add
- // that lead to a deallocation
+
+// # calls to VTS__cmp_structural w/ slow case
+static UWord stats__vts__cmp_structural_slow = 0;
+
+// # calls to VTS__indexAt_SLOW
+static UWord stats__vts__indexat_slow = 0;
+
+// # calls to vts_set__find__or__clone_and_add
+static UWord stats__vts_set__focaa = 0;
+
+// # calls to vts_set__find__or__clone_and_add that lead to an
+// allocation
+static UWord stats__vts_set__focaa_a = 0;
static inline Addr shmem__round_to_SecMap_base ( Addr a ) {
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
-#ifndef __HB_VTS_H
-#define __HB_VTS_H
-/* VtsIDs can't exceed 30 bits, since they have to be packed into the
- lowest 30 bits of an SVal. */
+/* There's a 1-1 mapping between Thr and ThrIDs -- the latter merely
+ being compact stand-ins for Thr*'s. Use these functions to map
+ between them. */
+static ThrID Thr__to_ThrID ( Thr* thr ); /* fwds */
+static Thr* Thr__from_ThrID ( ThrID thrid ); /* fwds */
+
+
+/* Scalar Timestamp. We have to store a lot of these, so there is
+ some effort to make them as small as possible. Logically they are
+ a pair, (Thr*, ULong), but that takes 16 bytes on a 64-bit target.
+ We pack it into 64 bits by representing the Thr* using a ThrID, a
+ small integer (18 bits), and a 46 bit integer for the timestamp
+ number. The 46/18 split is arbitary, but has the effect that
+ Helgrind can only handle programs that create 2^18 or fewer threads
+ over their entire lifetime, and have no more than 2^46 timestamp
+ ticks (synchronisation operations on the same thread).
+
+ This doesn't seem like much of a limitation. 2^46 ticks is
+ 7.06e+13, and if each tick (optimistically) takes the machine 1000
+ cycles to process, then the minimum time to process that many ticks
+ at a clock rate of 5 GHz is 162.9 days. And that's doing nothing
+ but VTS ticks, which isn't realistic.
+
+ NB1: SCALARTS_N_THRBITS must be 32 or lower, so they fit in a ThrID
+ (== a UInt).
+
+ NB2: thrid values are issued upwards from 1024, and values less
+ than that aren't valid. This isn't per se necessary (any order
+ will do, so long as they are unique), but it does help ensure they
+ are less likely to get confused with the various other kinds of
+ small-integer thread ids drifting around (eg, TId).
+
+ NB3: this probably also relies on the fact that Thr's are never
+ deallocated -- they exist forever. Hence the 1-1 mapping from
+ Thr's to thrid values (set up in Thr__new) persists forever.
+
+ NB4: temp_max_sized_VTS is allocated at startup and never freed.
+ It is a maximum sized VTS, so has (1 << SCALARTS_N_TYMBITS)
+ ScalarTSs. So we can't make SCALARTS_N_THRBITS too large without
+ making the memory use for this go sky-high. With
+ SCALARTS_N_THRBITS at 18, it occupies 2MB of memory, which seems
+ like an OK tradeoff. If more than 256k threads need to be
+ supported, we could change SCALARTS_N_THRBITS to 20, which would
+ facilitate supporting 1 million threads at the cost of 8MB storage
+ for temp_max_sized_VTS.
+*/
+#define SCALARTS_N_THRBITS 18 /* valid range: 11 to 32 inclusive */
+#define SCALARTS_N_TYMBITS (64 - SCALARTS_N_THRBITS)
+typedef
+ struct {
+ ThrID thrid : SCALARTS_N_THRBITS;
+ ULong tym : SCALARTS_N_TYMBITS;
+ }
+ ScalarTS;
+
+#define ThrID_MAX_VALID ((1 << SCALARTS_N_THRBITS) - 1)
+
+
+__attribute__((noreturn))
+static void scalarts_limitations_fail_NORETURN ( Bool due_to_nThrs )
+{
+ if (due_to_nThrs) {
+ HChar* s =
+ "\n"
+ "Helgrind: cannot continue, run aborted: too many threads.\n"
+ "Sorry. Helgrind can only handle programs that create\n"
+ "%'llu or fewer threads over their entire lifetime.\n"
+ "\n";
+ VG_(umsg)(s, (ULong)(ThrID_MAX_VALID - 1024));
+ } else {
+ HChar* s =
+ "\n"
+ "Helgrind: cannot continue, run aborted: too many\n"
+ "synchronisation events. Sorry. Helgrind can only handle\n"
+ "programs which perform %'llu or fewer\n"
+ "inter-thread synchronisation events (locks, unlocks, etc).\n"
+ "\n";
+ VG_(umsg)(s, (1ULL << SCALARTS_N_TYMBITS) - 1);
+ }
+ VG_(exit)(1);
+ /*NOTREACHED*/
+ tl_assert(0); /*wtf?!*/
+}
+
+
+/* VtsIDs: Unique small-integer IDs for VTSs. VtsIDs can't exceed 30
+ bits, since they have to be packed into the lowest 30 bits of an
+ SVal. */
typedef UInt VtsID;
#define VtsID_INVALID 0xFFFFFFFF
VtsID_INVALID. */
typedef
struct {
- VtsID id;
- XArray* ts; /* XArray* ScalarTS(abstract) */
+ VtsID id;
+ UInt usedTS;
+ UInt sizeTS;
+ ScalarTS ts[0];
}
VTS;
+/* Allocate a VTS capable of storing 'sizeTS' entries. */
+static VTS* VTS__new ( HChar* who, UInt sizeTS );
-/* Create a new, empty VTS. */
-static VTS* VTS__new ( void );
+/* Make a clone of 'vts', resizing the array to exactly match the
+ number of ScalarTSs present. */
+static VTS* VTS__clone ( HChar* who, VTS* vts );
/* Delete this VTS in its entirety. */
static void VTS__delete ( VTS* vts );
-/* Create a new singleton VTS. */
-static VTS* VTS__singleton ( Thr* thr, ULong tym );
+/* Create a new singleton VTS in 'out'. Caller must have
+ pre-allocated 'out' sufficiently big to hold the result in all
+ possible cases. */
+static void VTS__singleton ( /*OUT*/VTS* out, Thr* thr, ULong tym );
-/* Return a new VTS in which vts[me]++, so to speak. 'vts' itself is
- not modified. */
-static VTS* VTS__tick ( Thr* me, VTS* vts );
+/* Create in 'out' a VTS which is the same as 'vts' except with
+ vts[me]++, so to speak. Caller must have pre-allocated 'out'
+ sufficiently big to hold the result in all possible cases. */
+static void VTS__tick ( /*OUT*/VTS* out, Thr* me, VTS* vts );
-/* Return a new VTS constructed as the join (max) of the 2 args.
- Neither arg is modified. */
-static VTS* VTS__join ( VTS* a, VTS* b );
+/* Create in 'out' a VTS which is the join (max) of 'a' and
+ 'b'. Caller must have pre-allocated 'out' sufficiently big to hold
+ the result in all possible cases. */
+static void VTS__join ( /*OUT*/VTS* out, VTS* a, VTS* b );
/* Compute the partial ordering relation of the two args. Although we
could be completely general and return an enumeration value (EQ,
LT, GT, UN), in fact we only need LEQ, and so we may as well
hardwire that fact.
- Returns NULL iff LEQ(A,B), or non-NULL if not. In the latter case,
- the returned Thr* indicates the discovered point for which they are
- not. There may be more than one such point, but we only care about
- seeing one of them, not all of them. This rather strange
- convention is used because sometimes we want to know the actual
- index at which they first differ. */
-static Thr* VTS__cmpLEQ ( VTS* a, VTS* b );
+ Returns zero iff LEQ(A,B), or a valid ThrID if not (zero is an
+ invald ThrID). In the latter case, the returned ThrID indicates
+ the discovered point for which they are not. There may be more
+ than one such point, but we only care about seeing one of them, not
+ all of them. This rather strange convention is used because
+ sometimes we want to know the actual index at which they first
+ differ. */
+static UInt VTS__cmpLEQ ( VTS* a, VTS* b );
/* Compute an arbitrary structural (total) ordering on the two args,
based on their VCs, so they can be looked up in a table, tree, etc.
/* Debugging only. Return vts[index], so to speak. */
static ULong VTS__indexAt_SLOW ( VTS* vts, Thr* idx );
-#endif /* ! __HB_VTS_H */
-
/*--------------- to do with Vector Timestamps ---------------*/
-/* Scalar Timestamp */
-typedef
- struct {
- Thr* thr;
- ULong tym;
- }
- ScalarTS;
-
-
static Bool is_sane_VTS ( VTS* vts )
{
UWord i, n;
ScalarTS *st1, *st2;
if (!vts) return False;
if (!vts->ts) return False;
- n = VG_(sizeXA)( vts->ts );
+ if (vts->usedTS > vts->sizeTS) return False;
+ n = vts->usedTS;
+ if (n == 1) {
+ st1 = &vts->ts[0];
+ if (st1->tym == 0)
+ return False;
+ }
+ else
if (n >= 2) {
for (i = 0; i < n-1; i++) {
- st1 = VG_(indexXA)( vts->ts, i );
- st2 = VG_(indexXA)( vts->ts, i+1 );
- if (st1->thr >= st2->thr)
+ st1 = &vts->ts[i];
+ st2 = &vts->ts[i+1];
+ if (st1->thrid >= st2->thrid)
return False;
if (st1->tym == 0 || st2->tym == 0)
return False;
/* Create a new, empty VTS.
*/
-VTS* VTS__new ( void )
+static VTS* VTS__new ( HChar* who, UInt sizeTS )
{
- VTS* vts;
- vts = HG_(zalloc)( "libhb.VTS__new.1", sizeof(VTS) );
- tl_assert(vts);
- vts->id = VtsID_INVALID;
- vts->ts = VG_(newXA)( HG_(zalloc), "libhb.VTS__new.2",
- HG_(free), sizeof(ScalarTS) );
- tl_assert(vts->ts);
+ VTS* vts = HG_(zalloc)(who, sizeof(VTS) + (sizeTS+1) * sizeof(ScalarTS));
+ tl_assert(vts->usedTS == 0);
+ vts->sizeTS = sizeTS;
+ *(ULong*)(&vts->ts[sizeTS]) = 0x0ddC0ffeeBadF00dULL;
return vts;
}
+/* Clone this VTS.
+*/
+static VTS* VTS__clone ( HChar* who, VTS* vts )
+{
+ tl_assert(vts);
+ tl_assert( *(ULong*)(&vts->ts[vts->sizeTS]) == 0x0ddC0ffeeBadF00dULL);
+ UInt nTS = vts->usedTS;
+ VTS* clone = VTS__new(who, nTS);
+ clone->id = vts->id;
+ clone->sizeTS = nTS;
+ clone->usedTS = nTS;
+ UInt i;
+ for (i = 0; i < nTS; i++) {
+ clone->ts[i] = vts->ts[i];
+ }
+ tl_assert( *(ULong*)(&clone->ts[clone->sizeTS]) == 0x0ddC0ffeeBadF00dULL);
+ return clone;
+}
+
/* Delete this VTS in its entirety.
*/
-void VTS__delete ( VTS* vts )
+static void VTS__delete ( VTS* vts )
{
tl_assert(vts);
- tl_assert(vts->ts);
- VG_(deleteXA)( vts->ts );
+ tl_assert(vts->usedTS <= vts->sizeTS);
+ tl_assert( *(ULong*)(&vts->ts[vts->sizeTS]) == 0x0ddC0ffeeBadF00dULL);
HG_(free)(vts);
}
/* Create a new singleton VTS.
*/
-VTS* VTS__singleton ( Thr* thr, ULong tym ) {
- ScalarTS st;
- VTS* vts;
+static void VTS__singleton ( /*OUT*/VTS* out, Thr* thr, ULong tym )
+{
tl_assert(thr);
tl_assert(tym >= 1);
- vts = VTS__new();
- st.thr = thr;
- st.tym = tym;
- VG_(addToXA)( vts->ts, &st );
- return vts;
+ tl_assert(out);
+ tl_assert(out->usedTS == 0);
+ tl_assert(out->sizeTS >= 1);
+ UInt hi = out->usedTS++;
+ out->ts[hi].thrid = Thr__to_ThrID(thr);
+ out->ts[hi].tym = tym;
}
/* Return a new VTS in which vts[me]++, so to speak. 'vts' itself is
not modified.
*/
-VTS* VTS__tick ( Thr* me, VTS* vts )
+static void VTS__tick ( /*OUT*/VTS* out, Thr* me, VTS* vts )
{
- ScalarTS* here = NULL;
- ScalarTS tmp;
- VTS* res;
- Word i, n;
+ UInt i, n;
+ ThrID me_thrid;
+ Bool found = False;
stats__vts__tick++;
+ tl_assert(out);
+ tl_assert(out->usedTS == 0);
+ if (vts->usedTS >= ThrID_MAX_VALID)
+ scalarts_limitations_fail_NORETURN( True/*due_to_nThrs*/ );
+ tl_assert(out->sizeTS >= 1 + vts->usedTS);
+
tl_assert(me);
+ me_thrid = Thr__to_ThrID(me);
tl_assert(is_sane_VTS(vts));
- //if (0) VG_(printf)("tick vts thrno %ld szin %d\n",
- // (Word)me->errmsg_index, (Int)VG_(sizeXA)(vts) );
- res = VTS__new();
- n = VG_(sizeXA)( vts->ts );
-
- /* main loop doesn't handle zero-entry case correctly, so
- special-case it. */
- if (n == 0) {
- tmp.thr = me;
- tmp.tym = 1;
- VG_(addToXA)( res->ts, &tmp );
- tl_assert(is_sane_VTS(res));
- return res;
- }
+ n = vts->usedTS;
+ /* Copy all entries which precede 'me'. */
for (i = 0; i < n; i++) {
- here = VG_(indexXA)( vts->ts, i );
- if (me < here->thr) {
- /* We just went past 'me', without seeing it. */
- tmp.thr = me;
- tmp.tym = 1;
- VG_(addToXA)( res->ts, &tmp );
- tmp = *here;
- VG_(addToXA)( res->ts, &tmp );
- i++;
- break;
- }
- else if (me == here->thr) {
- tmp = *here;
- tmp.tym++;
- VG_(addToXA)( res->ts, &tmp );
- i++;
+ ScalarTS* here = &vts->ts[i];
+ if (UNLIKELY(here->thrid >= me_thrid))
break;
- }
- else /* me > here->thr */ {
- tmp = *here;
- VG_(addToXA)( res->ts, &tmp );
- }
- }
+ UInt hi = out->usedTS++;
+ out->ts[hi] = *here;
+ }
+
+ /* 'i' now indicates the next entry to copy, if any.
+ There are 3 possibilities:
+ (a) there is no next entry (we used them all up already):
+ add (me_thrid,1) to the output, and quit
+ (b) there is a next entry, and its thrid > me_thrid:
+ add (me_thrid,1) to the output, then copy the remaining entries
+ (c) there is a next entry, and its thrid == me_thrid:
+ copy it to the output but increment its timestamp value.
+ Then copy the remaining entries. (c) is the common case.
+ */
tl_assert(i >= 0 && i <= n);
- if (i == n && here && here->thr < me) {
- tmp.thr = me;
- tmp.tym = 1;
- VG_(addToXA)( res->ts, &tmp );
+ if (i == n) { /* case (a) */
+ UInt hi = out->usedTS++;
+ out->ts[hi].thrid = me_thrid;
+ out->ts[hi].tym = 1;
} else {
+ /* cases (b) and (c) */
+ ScalarTS* here = &vts->ts[i];
+ if (me_thrid == here->thrid) { /* case (c) */
+ if (UNLIKELY(here->tym >= (1ULL << SCALARTS_N_TYMBITS) - 2ULL)) {
+ /* We're hosed. We have to stop. */
+ scalarts_limitations_fail_NORETURN( False/*!due_to_nThrs*/ );
+ }
+ UInt hi = out->usedTS++;
+ out->ts[hi].thrid = here->thrid;
+ out->ts[hi].tym = here->tym + 1;
+ i++;
+ found = True;
+ } else { /* case (b) */
+ UInt hi = out->usedTS++;
+ out->ts[hi].thrid = me_thrid;
+ out->ts[hi].tym = 1;
+ }
+ /* And copy any remaining entries. */
for (/*keepgoing*/; i < n; i++) {
- here = VG_(indexXA)( vts->ts, i );
- tmp = *here;
- VG_(addToXA)( res->ts, &tmp );
+ ScalarTS* here2 = &vts->ts[i];
+ UInt hi = out->usedTS++;
+ out->ts[hi] = *here2;
}
}
- tl_assert(is_sane_VTS(res));
- //if (0) VG_(printf)("tick vts thrno %ld szou %d\n",
- // (Word)me->errmsg_index, (Int)VG_(sizeXA)(res) );
- return res;
+
+ tl_assert(is_sane_VTS(out));
+ tl_assert(out->usedTS == vts->usedTS + (found ? 0 : 1));
+ tl_assert(out->usedTS <= out->sizeTS);
}
/* Return a new VTS constructed as the join (max) of the 2 args.
Neither arg is modified.
*/
-VTS* VTS__join ( VTS* a, VTS* b )
+static void VTS__join ( /*OUT*/VTS* out, VTS* a, VTS* b )
{
- Word ia, ib, useda, usedb;
+ UInt ia, ib, useda, usedb;
ULong tyma, tymb, tymMax;
- Thr* thr;
- VTS* res;
+ ThrID thrid;
+ UInt ncommon = 0;
stats__vts__join++;
- tl_assert(a && a->ts);
- tl_assert(b && b->ts);
- useda = VG_(sizeXA)( a->ts );
- usedb = VG_(sizeXA)( b->ts );
+ tl_assert(a);
+ tl_assert(b);
+ useda = a->usedTS;
+ usedb = b->usedTS;
+
+ tl_assert(out);
+ tl_assert(out->usedTS == 0);
+ /* overly conservative test, but doing better involves comparing
+ the two VTSs, which we don't want to do at this point. */
+ if (useda + usedb >= ThrID_MAX_VALID)
+ scalarts_limitations_fail_NORETURN( True/*due_to_nThrs*/ );
+ tl_assert(out->sizeTS >= useda + usedb);
- res = VTS__new();
ia = ib = 0;
while (1) {
- /* This logic is to enumerate triples (thr, tyma, tymb) drawn
- from a and b in order, where thr is the next Thr*
+ /* This logic is to enumerate triples (thrid, tyma, tymb) drawn
+ from a and b in order, where thrid is the next ThrID
occurring in either a or b, and tyma/b are the relevant
scalar timestamps, taking into account implicit zeroes. */
tl_assert(ia >= 0 && ia <= useda);
} else if (ia == useda && ib != usedb) {
/* a empty, use up b */
- ScalarTS* tmpb = VG_(indexXA)( b->ts, ib );
- thr = tmpb->thr;
- tyma = 0;
- tymb = tmpb->tym;
+ ScalarTS* tmpb = &b->ts[ib];
+ thrid = tmpb->thrid;
+ tyma = 0;
+ tymb = tmpb->tym;
ib++;
} else if (ia != useda && ib == usedb) {
/* b empty, use up a */
- ScalarTS* tmpa = VG_(indexXA)( a->ts, ia );
- thr = tmpa->thr;
- tyma = tmpa->tym;
- tymb = 0;
+ ScalarTS* tmpa = &a->ts[ia];
+ thrid = tmpa->thrid;
+ tyma = tmpa->tym;
+ tymb = 0;
ia++;
} else {
- /* both not empty; extract lowest-Thr*'d triple */
- ScalarTS* tmpa = VG_(indexXA)( a->ts, ia );
- ScalarTS* tmpb = VG_(indexXA)( b->ts, ib );
- if (tmpa->thr < tmpb->thr) {
- /* a has the lowest unconsidered Thr* */
- thr = tmpa->thr;
- tyma = tmpa->tym;
- tymb = 0;
+ /* both not empty; extract lowest-ThrID'd triple */
+ ScalarTS* tmpa = &a->ts[ia];
+ ScalarTS* tmpb = &b->ts[ib];
+ if (tmpa->thrid < tmpb->thrid) {
+ /* a has the lowest unconsidered ThrID */
+ thrid = tmpa->thrid;
+ tyma = tmpa->tym;
+ tymb = 0;
ia++;
- } else if (tmpa->thr > tmpb->thr) {
- /* b has the lowest unconsidered Thr* */
- thr = tmpb->thr;
- tyma = 0;
- tymb = tmpb->tym;
+ } else if (tmpa->thrid > tmpb->thrid) {
+ /* b has the lowest unconsidered ThrID */
+ thrid = tmpb->thrid;
+ tyma = 0;
+ tymb = tmpb->tym;
ib++;
} else {
- /* they both next mention the same Thr* */
- tl_assert(tmpa->thr == tmpb->thr);
- thr = tmpa->thr; /* == tmpb->thr */
- tyma = tmpa->tym;
- tymb = tmpb->tym;
+ /* they both next mention the same ThrID */
+ tl_assert(tmpa->thrid == tmpb->thrid);
+ thrid = tmpa->thrid; /* == tmpb->thrid */
+ tyma = tmpa->tym;
+ tymb = tmpb->tym;
ia++;
ib++;
+ ncommon++;
}
}
useful with it. */
tymMax = tyma > tymb ? tyma : tymb;
if (tymMax > 0) {
- ScalarTS st;
- st.thr = thr;
- st.tym = tymMax;
- VG_(addToXA)( res->ts, &st );
+ UInt hi = out->usedTS++;
+ out->ts[hi].thrid = thrid;
+ out->ts[hi].tym = tymMax;
}
}
- tl_assert(is_sane_VTS( res ));
-
- return res;
+ tl_assert(is_sane_VTS(out));
+ tl_assert(out->usedTS <= out->sizeTS);
+ tl_assert(out->usedTS == useda + usedb - ncommon);
}
-/* Determine if 'a' <= 'b', in the partial ordering. Returns NULL if
- they are, or the first Thr* for which they are not. This rather
- strange convention is used because sometimes we want to know the
- actual index at which they first differ. */
-static Thr* VTS__cmpLEQ ( VTS* a, VTS* b )
+/* Determine if 'a' <= 'b', in the partial ordering. Returns zero if
+ they are, or the first ThrID for which they are not (no valid ThrID
+ has the value zero). This rather strange convention is used
+ because sometimes we want to know the actual index at which they
+ first differ. */
+static UInt/*ThrID*/ VTS__cmpLEQ ( VTS* a, VTS* b )
{
Word ia, ib, useda, usedb;
ULong tyma, tymb;
stats__vts__cmpLEQ++;
- tl_assert(a && a->ts);
- tl_assert(b && b->ts);
- useda = VG_(sizeXA)( a->ts );
- usedb = VG_(sizeXA)( b->ts );
+ tl_assert(a);
+ tl_assert(b);
+ useda = a->usedTS;
+ usedb = b->usedTS;
ia = ib = 0;
/* This logic is to enumerate doubles (tyma, tymb) drawn
from a and b in order, and tyma/b are the relevant
scalar timestamps, taking into account implicit zeroes. */
- Thr* thr;
+ ThrID thrid;
tl_assert(ia >= 0 && ia <= useda);
tl_assert(ib >= 0 && ib <= usedb);
} else if (ia == useda && ib != usedb) {
/* a empty, use up b */
- ScalarTS* tmpb = VG_(indexXA)( b->ts, ib );
- tyma = 0;
- tymb = tmpb->tym;
- thr = tmpb->thr;
+ ScalarTS* tmpb = &b->ts[ib];
+ tyma = 0;
+ tymb = tmpb->tym;
+ thrid = tmpb->thrid;
ib++;
} else if (ia != useda && ib == usedb) {
/* b empty, use up a */
- ScalarTS* tmpa = VG_(indexXA)( a->ts, ia );
- tyma = tmpa->tym;
- thr = tmpa->thr;
- tymb = 0;
+ ScalarTS* tmpa = &a->ts[ia];
+ tyma = tmpa->tym;
+ thrid = tmpa->thrid;
+ tymb = 0;
ia++;
} else {
- /* both not empty; extract lowest-Thr*'d triple */
- ScalarTS* tmpa = VG_(indexXA)( a->ts, ia );
- ScalarTS* tmpb = VG_(indexXA)( b->ts, ib );
- if (tmpa->thr < tmpb->thr) {
- /* a has the lowest unconsidered Thr* */
- tyma = tmpa->tym;
- thr = tmpa->thr;
- tymb = 0;
+ /* both not empty; extract lowest-ThrID'd triple */
+ ScalarTS* tmpa = &a->ts[ia];
+ ScalarTS* tmpb = &b->ts[ib];
+ if (tmpa->thrid < tmpb->thrid) {
+ /* a has the lowest unconsidered ThrID */
+ tyma = tmpa->tym;
+ thrid = tmpa->thrid;
+ tymb = 0;
ia++;
}
else
- if (tmpa->thr > tmpb->thr) {
- /* b has the lowest unconsidered Thr* */
- tyma = 0;
- tymb = tmpb->tym;
- thr = tmpb->thr;
+ if (tmpa->thrid > tmpb->thrid) {
+ /* b has the lowest unconsidered ThrID */
+ tyma = 0;
+ tymb = tmpb->tym;
+ thrid = tmpb->thrid;
ib++;
} else {
- /* they both next mention the same Thr* */
- tl_assert(tmpa->thr == tmpb->thr);
- tyma = tmpa->tym;
- thr = tmpa->thr;
- tymb = tmpb->tym;
+ /* they both next mention the same ThrID */
+ tl_assert(tmpa->thrid == tmpb->thrid);
+ tyma = tmpa->tym;
+ thrid = tmpa->thrid;
+ tymb = tmpb->tym;
ia++;
ib++;
}
if (tyma > tymb) {
/* not LEQ at this index. Quit, since the answer is
determined already. */
- tl_assert(thr);
- return thr;
+ tl_assert(thrid >= 1024);
+ return thrid;
}
}
- return NULL; /* all points are LEQ */
+ return 0; /* all points are LEQ => return an invalid ThrID */
}
tl_assert(a);
tl_assert(b);
- VG_(getContentsXA_UNSAFE)( a->ts, (void**)&ctsa, &useda );
- VG_(getContentsXA_UNSAFE)( b->ts, (void**)&ctsb, &usedb );
+ ctsa = &a->ts[0]; useda = a->usedTS;
+ ctsb = &b->ts[0]; usedb = b->usedTS;
if (LIKELY(useda == usedb)) {
ScalarTS *tmpa = NULL, *tmpb = NULL;
for (i = 0; i < useda; i++) {
tmpa = &ctsa[i];
tmpb = &ctsb[i];
- if (LIKELY(tmpa->tym == tmpb->tym && tmpa->thr == tmpb->thr))
+ if (LIKELY(tmpa->tym == tmpb->tym
+ && tmpa->thrid == tmpb->thrid))
continue;
else
break;
tl_assert(i >= 0 && i < useda);
if (tmpa->tym < tmpb->tym) return -1;
if (tmpa->tym > tmpb->tym) return 1;
- if (tmpa->thr < tmpb->thr) return -1;
- if (tmpa->thr > tmpb->thr) return 1;
+ if (tmpa->thrid < tmpb->thrid) return -1;
+ if (tmpa->thrid > tmpb->thrid) return 1;
/* we just established them as non-identical, hence: */
}
/*NOTREACHED*/
/* Debugging only. Display the given VTS in the buffer.
*/
-void VTS__show ( HChar* buf, Int nBuf, VTS* vts ) {
+void VTS__show ( HChar* buf, Int nBuf, VTS* vts )
+{
ScalarTS* st;
HChar unit[64];
Word i, n;
tl_assert(nBuf > 16);
buf[0] = '[';
buf[1] = 0;
- n = VG_(sizeXA)( vts->ts );
+ n = vts->usedTS;
for (i = 0; i < n; i++) {
tl_assert(avail >= 40);
- st = VG_(indexXA)( vts->ts, i );
+ st = &vts->ts[i];
VG_(memset)(unit, 0, sizeof(unit));
- VG_(sprintf)(unit, i < n-1 ? "%p:%lld " : "%p:%lld",
- st->thr, st->tym);
+ VG_(sprintf)(unit, i < n-1 ? "%u:%llu " : "%u:%llu",
+ st->thrid, (ULong)st->tym);
if (avail < VG_(strlen)(unit) + 40/*let's say*/) {
VG_(strcat)(buf, " ...]");
buf[nBuf-1] = 0;
/* Debugging only. Return vts[index], so to speak.
*/
-ULong VTS__indexAt_SLOW ( VTS* vts, Thr* idx ) {
+ULong VTS__indexAt_SLOW ( VTS* vts, Thr* idx )
+{
UWord i, n;
+ ThrID idx_thrid = Thr__to_ThrID(idx);
stats__vts__indexat_slow++;
tl_assert(vts && vts->ts);
- n = VG_(sizeXA)( vts->ts );
+ n = vts->usedTS;
for (i = 0; i < n; i++) {
- ScalarTS* st = VG_(indexXA)( vts->ts, i );
- if (st->thr == idx)
+ ScalarTS* st = &vts->ts[i];
+ if (st->thrid == idx_thrid)
return st->tym;
}
return 0;
tl_assert(vts_set);
}
-/* Given a newly made VTS, look in vts_set to see if we already have
- an identical one. If yes, free up this one and return instead a
- pointer to the existing one. If no, add this one to the set and
- return the same pointer. Caller differentiates the two cases by
- comparing returned pointer with the supplied one (although that
- does require that the supplied VTS is not already in the set).
-*/
-static VTS* vts_set__find_and_dealloc__or_add ( VTS* cand )
+/* Given a VTS, look in vts_set to see if we already have a
+ structurally identical one. If yes, return the pair (True, pointer
+ to the existing one). If no, clone this one, add the clone to the
+ set, and return (False, pointer to the clone). */
+static Bool vts_set__find__or__clone_and_add ( /*OUT*/VTS** res, VTS* cand )
{
UWord keyW, valW;
- stats__vts_set__fadoa++;
+ stats__vts_set__focaa++;
+ tl_assert(cand->id == VtsID_INVALID);
/* lookup cand (by value) */
if (VG_(lookupFM)( vts_set, &keyW, &valW, (UWord)cand )) {
/* found it */
tl_assert(valW == 0);
/* if this fails, cand (by ref) was already present (!) */
tl_assert(keyW != (UWord)cand);
- stats__vts_set__fadoa_d++;
- VTS__delete(cand);
- return (VTS*)keyW;
+ *res = (VTS*)keyW;
+ return True;
} else {
- /* not present. Add and return pointer to same. */
- VG_(addToFM)( vts_set, (UWord)cand, 0/*val is unused*/ );
- return cand;
+ /* not present. Clone, add and return address of clone. */
+ stats__vts_set__focaa_a++;
+ VTS* clone = VTS__clone( "libhb.vts_set_focaa.1", cand );
+ tl_assert(clone != cand);
+ VG_(addToFM)( vts_set, (UWord)clone, 0/*val is unused*/ );
+ *res = clone;
+ return False;
}
}
}
-/* Look up 'cand' in our collection of VTSs. If present, deallocate
- it and return the VtsID for the pre-existing version. If not
- present, add it to both vts_tab and vts_set, allocate a fresh VtsID
- for it, and return that. */
-static VtsID vts_tab__find_and_dealloc__or_add ( VTS* cand )
+/* Look up 'cand' in our collection of VTSs. If present, return the
+ VtsID for the pre-existing version. If not present, clone it, add
+ the clone to both vts_tab and vts_set, allocate a fresh VtsID for
+ it, and return that. */
+static VtsID vts_tab__find__or__clone_and_add ( VTS* cand )
{
- VTS* auld;
+ VTS* in_tab = NULL;
tl_assert(cand->id == VtsID_INVALID);
- auld = vts_set__find_and_dealloc__or_add(cand);
- if (auld != cand) {
- /* We already have an Aulde one. Use that. */
+ Bool already_have = vts_set__find__or__clone_and_add( &in_tab, cand );
+ tl_assert(in_tab);
+ if (already_have) {
+ /* We already have a copy of 'cand'. Use that. */
VtsTE* ie;
- tl_assert(auld->id != VtsID_INVALID);
- ie = VG_(indexXA)( vts_tab, auld->id );
- tl_assert(ie->vts == auld);
- return auld->id;
+ tl_assert(in_tab->id != VtsID_INVALID);
+ ie = VG_(indexXA)( vts_tab, in_tab->id );
+ tl_assert(ie->vts == in_tab);
+ return in_tab->id;
} else {
VtsID ii = get_new_VtsID();
VtsTE* ie = VG_(indexXA)( vts_tab, ii );
- ie->vts = cand;
+ ie->vts = in_tab;
ie->rc = 0;
ie->freelink = VtsID_INVALID;
- cand->id = ii;
+ in_tab->id = ii;
return ii;
}
}
// //
/////////////////////////////////////////////////////////
+//////////////////////////
+/* A temporary, max-sized VTS which is used as a temporary (the first
+ argument) in VTS__singleton, VTS__tick and VTS__join operations. */
+static VTS* temp_max_sized_VTS = NULL;
+
//////////////////////////
static ULong stats__cmpLEQ_queries = 0;
static ULong stats__cmpLEQ_misses = 0;
////--
v1 = VtsID__to_VTS(vi1);
v2 = VtsID__to_VTS(vi2);
- leq = VTS__cmpLEQ( v1, v2 ) == NULL;
+ leq = VTS__cmpLEQ( v1, v2 ) == 0;
////++
cmpLEQ_cache[hash].vi1 = vi1;
cmpLEQ_cache[hash].vi2 = vi2;
static VtsID VtsID__join2_WRK ( VtsID vi1, VtsID vi2 ) {
UInt hash;
VtsID res;
- VTS *vts1, *vts2, *nyu;
+ VTS *vts1, *vts2;
//if (vi1 == vi2) return vi1;
tl_assert(vi1 != vi2);
////++
////--
vts1 = VtsID__to_VTS(vi1);
vts2 = VtsID__to_VTS(vi2);
- nyu = VTS__join(vts1,vts2);
- res = vts_tab__find_and_dealloc__or_add(nyu);
+ temp_max_sized_VTS->usedTS = 0;
+ VTS__join(temp_max_sized_VTS, vts1,vts2);
+ res = vts_tab__find__or__clone_and_add(temp_max_sized_VTS);
////++
join2_cache[hash].vi1 = vi1;
join2_cache[hash].vi2 = vi2;
/* create a singleton VTS, namely [thr:1] */
static VtsID VtsID__mk_Singleton ( Thr* thr, ULong tym ) {
- VTS* nyu = VTS__singleton(thr,tym);
- return vts_tab__find_and_dealloc__or_add(nyu);
+ temp_max_sized_VTS->usedTS = 0;
+ VTS__singleton(temp_max_sized_VTS, thr,tym);
+ return vts_tab__find__or__clone_and_add(temp_max_sized_VTS);
}
/* tick operation, creates value 1 if specified index is absent */
static VtsID VtsID__tick ( VtsID vi, Thr* idx ) {
VTS* vts = VtsID__to_VTS(vi);
- VTS* nyu = VTS__tick(idx,vts);
- return vts_tab__find_and_dealloc__or_add(nyu);
+ temp_max_sized_VTS->usedTS = 0;
+ VTS__tick(temp_max_sized_VTS, idx,vts);
+ return vts_tab__find__or__clone_and_add(temp_max_sized_VTS);
}
/* index into a VTS (only for assertions) */
static Thr* VtsID__findFirst_notLEQ ( VtsID vi1, VtsID vi2 )
{
VTS *vts1, *vts2;
- Thr* diffthr;
+ Thr* diffthr;
+ ThrID diffthrid;
tl_assert(vi1 != vi2);
vts1 = VtsID__to_VTS(vi1);
vts2 = VtsID__to_VTS(vi2);
tl_assert(vts1 != vts2);
- diffthr = VTS__cmpLEQ(vts1, vts2);
+ diffthrid = VTS__cmpLEQ(vts1, vts2);
+ diffthr = Thr__from_ThrID(diffthrid);
tl_assert(diffthr); /* else they are LEQ ! */
return diffthr;
}
has done a low-level exit. */
Bool still_alive;
+ /* A small integer giving a unique identity to this Thr. See
+ comments on the definition of ScalarTS for details. */
+ ThrID thrid : SCALARTS_N_THRBITS;
+
/* A filter that removes references for which we believe that
msmcread/msmcwrite will not change the state, nor report a
race. */
Filter* filter;
- /* opaque (to us) data we hold on behalf of the library's user. */
- void* opaque;
+ /* A pointer back to the top level Thread structure. There is a
+ 1-1 mapping between Thread and Thr structures -- each Thr points
+ at its corresponding Thread, and vice versa. Really, Thr and
+ Thread should be merged into a single structure. */
+ Thread* hgthread;
/* The ULongs (scalar Kws) in this accumulate in strictly
increasing order, without duplicates. This is important because
XArray* /* ULong_n_EC */ local_Kws_n_stacks;
};
-static Thr* Thr__new ( void ) {
+
+/* Maps ThrID values to their Thr*s (which contain ThrID values that
+ should point back to the relevant slot in the array. Lowest
+ numbered slot (0) is for thrid = 1024, (1) is for 1025, etc. */
+static XArray* /* of Thr* */ thrid_to_thr_map = NULL;
+
+/* And a counter to dole out ThrID values. For rationale/background,
+ see comments on definition of ScalarTS (far) above. */
+static ThrID thrid_counter = 1024; /* runs up to ThrID_MAX_VALID */
+
+static ThrID Thr__to_ThrID ( Thr* thr ) {
+ return thr->thrid;
+}
+static Thr* Thr__from_ThrID ( UInt thrid ) {
+ Thr* thr = *(Thr**)VG_(indexXA)( thrid_to_thr_map, thrid - 1024 );
+ tl_assert(thr->thrid == thrid);
+ return thr;
+}
+
+static Thr* Thr__new ( void )
+{
Thr* thr = HG_(zalloc)( "libhb.Thr__new.1", sizeof(Thr) );
thr->viR = VtsID_INVALID;
thr->viW = VtsID_INVALID;
= VG_(newXA)( HG_(zalloc),
"libhb.Thr__new.3 (local_Kws_and_stacks)",
HG_(free), sizeof(ULong_n_EC) );
+
+ /* Add this Thr* <-> ThrID binding to the mapping, and
+ cross-check */
+ if (!thrid_to_thr_map) {
+ thrid_to_thr_map = VG_(newXA)( HG_(zalloc), "libhb.Thr__new.4",
+ HG_(free), sizeof(Thr*) );
+ tl_assert(thrid_to_thr_map);
+ }
+
+ if (thrid_counter >= ThrID_MAX_VALID) {
+ /* We're hosed. We have to stop. */
+ scalarts_limitations_fail_NORETURN( True/*due_to_nThrs*/ );
+ }
+
+ thr->thrid = thrid_counter++;
+ Word ix = VG_(addToXA)( thrid_to_thr_map, &thr );
+ tl_assert(ix + 1024 == thr->thrid);
+
return thr;
}
Thread* hist1_conf_thr = NULL;
tl_assert(acc_thr);
- tl_assert(acc_thr->opaque);
+ tl_assert(acc_thr->hgthread);
+ tl_assert(acc_thr->hgthread->hbthr == acc_thr);
tl_assert(HG_(clo_history_level) >= 0 && HG_(clo_history_level) <= 2);
if (HG_(clo_history_level) == 1) {
// seg_start could be NULL iff this is the first stack in the thread
//if (seg_start) VG_(pp_ExeContext)(seg_start);
//if (seg_end) VG_(pp_ExeContext)(seg_end);
- hist1_conf_thr = confThr->opaque;
+ hist1_conf_thr = confThr->hgthread;
}
}
- HG_(record_error_Race)( acc_thr->opaque, acc_addr,
+ HG_(record_error_Race)( acc_thr->hgthread, acc_addr,
szB, isWrite,
hist1_conf_thr, hist1_seg_start, hist1_seg_end );
}
{
Thr* thr;
VtsID vi;
+
+ // We will have to have to store a large number of these,
+ // so make sure they're the size we expect them to be.
+ tl_assert(sizeof(ScalarTS) == 8);
+ tl_assert(SCALARTS_N_THRBITS >= 11); /* because first 1024 unusable */
+ tl_assert(SCALARTS_N_THRBITS <= 32); /* so as to fit in a UInt */
+
tl_assert(get_stacktrace);
tl_assert(get_EC);
main_get_stacktrace = get_stacktrace;
// No need to initialise hg_wordfm.
// No need to initialise hg_wordset.
+ /* Allocated once and never deallocated. Used as a temporary in
+ VTS singleton, tick and join operations. */
+ temp_max_sized_VTS = VTS__new( "libhb.libhb_init.1", ThrID_MAX_VALID );
+ temp_max_sized_VTS->id = VtsID_INVALID;
vts_set_init();
vts_tab_init();
event_map_init();
stats__vts__tick, stats__vts__join, stats__vts__cmpLEQ );
VG_(printf)( " libhb: VTSops: cmp_structural %'lu (%'lu slow)\n",
stats__vts__cmp_structural, stats__vts__cmp_structural_slow );
- VG_(printf)( " libhb: VTSset: find_and_dealloc__or_add %'lu (%'lu deallocd)\n",
- stats__vts_set__fadoa, stats__vts_set__fadoa_d );
+ VG_(printf)( " libhb: VTSset: find__or__clone_and_add %'lu (%'lu allocd)\n",
+ stats__vts_set__focaa, stats__vts_set__focaa_a );
VG_(printf)( " libhb: VTSops: indexAt_SLOW %'lu\n",
stats__vts__indexat_slow );
if (0 && TRACEME(a,szB)) trace(thr,a,szB,"nw-after ");
}
-void libhb_srange_noaccess ( Thr* thr, Addr a, SizeT szB )
+void libhb_srange_noaccess_NoFX ( Thr* thr, Addr a, SizeT szB )
{
/* do nothing */
}
+void libhb_srange_noaccess_AHAE ( Thr* thr, Addr a, SizeT szB )
+{
+ /* This really does put the requested range in NoAccess. It's
+ expensive though. */
+ SVal sv = SVal_NOACCESS;
+ tl_assert(is_sane_SVal_C(sv));
+ zsm_sset_range( a, szB, sv );
+ Filter__clear_range( thr->filter, a, szB );
+}
+
void libhb_srange_untrack ( Thr* thr, Addr a, SizeT szB )
{
SVal sv = SVal_NOACCESS;
if (0 && TRACEME(a,szB)) trace(thr,a,szB,"untrack-after ");
}
-void* libhb_get_Thr_opaque ( Thr* thr ) {
+Thread* libhb_get_Thr_hgthread ( Thr* thr ) {
tl_assert(thr);
- return thr->opaque;
+ return thr->hgthread;
}
-void libhb_set_Thr_opaque ( Thr* thr, void* v ) {
+void libhb_set_Thr_hgthread ( Thr* thr, Thread* hgthread ) {
tl_assert(thr);
- thr->opaque = v;
+ thr->hgthread = hgthread;
}
void libhb_copy_shadow_state ( Thr* thr, Addr src, Addr dst, SizeT len )
projects / l4.git / blobdiff