Author: Armin Rigo <[email protected]>
Branch:
Changeset: r93:2d0f4e06ce3a
Date: 2013-06-11 22:49 +0200
http://bitbucket.org/pypy/stmgc/changeset/2d0f4e06ce3a/
Log: Fixes. Now I have a clear idea about which thread can change
exactly which parts of which objects.
diff --git a/c4/doc-objects.txt b/c4/doc-objects.txt
--- a/c4/doc-objects.txt
+++ b/c4/doc-objects.txt
@@ -245,3 +245,28 @@
make a stub with h_revision = private object | 2
after a CPU write barrier, make the public h_revision to point to the stub
+
+
+
+Change to the flags and h_revision
+----------------------------------
+
+The flags are in `h_tid`. Changes to this field and `h_revision` must
+not occur uncontrolled:
+
+- private copies: the thread that owns the private copy can change
+freely the `h_tid` and `h_revision` fields. The other threads must not
+touch them, and must read them carefully. This concerns only stealing
+threads, on GCFLAG_PRIVATE_FROM_PROTECTED objects. The flag
+GCFLAG_PRIVATE_FROM_PROTECTED itself is only changed when the owning
+thread has got its collection_lock, and as long as it is set, h_revision
+points to the backup copy.
+
+- protected copies (includes backup copies): any change requires the
+owning thread's collection_lock. During stealing, other threads
+might add (with the collection_lock) the flags GCFLAG_PUBLIC or
+GCFLAG_PUBLIC_TO_PRIVATE.
+
+- public copies: must be changed carefully: `h_tid` is only modified to
+add GCFLAG_PUBLIC_TO_PRIVATE; and `h_revision` changes are done with
+bool_cas() in a thread-controlled way.
diff --git a/c4/et.c b/c4/et.c
--- a/c4/et.c
+++ b/c4/et.c
@@ -75,9 +75,11 @@
gcptr P = G;
revision_t v;
+ restart_all:
if (P->h_tid & GCFLAG_PRIVATE_FROM_PROTECTED)
{
- private_from_protected:
+ assert(!(P->h_revision & 1)); /* pointer to the backup copy */
+
/* check P->h_revision->h_revision: if a pointer, then it means
the backup copy has been stolen into a public object and then
modified by some other thread. Abort. */
@@ -86,15 +88,20 @@
goto add_in_recent_reads_cache;
}
+ /* else, for the rest of this function, we can assume that P was not
+ a private copy */
if (P->h_tid & GCFLAG_PUBLIC)
{
/* follow the chained list of h_revision's as long as they are
- regular pointers */
- retry:
+ regular pointers. We will only find more public objects
+ along this chain.
+ */
+ restart_all_public:
v = ACCESS_ONCE(P->h_revision);
if (!(v & 1)) // "is a pointer", i.e.
{ // "has a more recent revision"
+ retry:
if (v & 2)
goto follow_stub;
@@ -114,23 +121,33 @@
doing this write occasionally based on a counter in d */
P_prev->h_revision = v;
P = (gcptr)v;
- goto retry;
+ v = ACCESS_ONCE(P->h_revision);
+ if (!(v & 1)) // "is a pointer", i.e. "has a more recent rev"
+ goto retry;
+ }
+
+ /* We reach this point if P != G only. Check again the
+ read_barrier_cache: if P now hits the cache, just return it
+ */
+ if (FXCACHE_AT(P) == P)
+ {
+ fprintf(stderr, "read_barrier: %p -> %p fxcache\n", G, P);
+ return P;
}
}
- /* if we land on a P in read_barrier_cache: just return it */
- if (FXCACHE_AT(P) == P)
- {
- fprintf(stderr, "read_barrier: %p -> %p fxcache\n", G, P);
- return P;
- }
-
+ /* If we land on a P with GCFLAG_PUBLIC_TO_PRIVATE, it might be
+ because *we* have an entry in d->public_to_private. (It might
+ also be someone else.)
+ */
if (P->h_tid & GCFLAG_PUBLIC_TO_PRIVATE)
{
wlog_t *item;
retry_public_to_private:;
G2L_FIND(d->public_to_private, P, item, goto no_private_obj);
+ /* We have a key in 'public_to_private'. The value is the
+ corresponding private object. */
P = item->val;
assert(!(P->h_tid & GCFLAG_PUBLIC));
assert(is_private(P));
@@ -138,6 +155,8 @@
return P;
no_private_obj:
+ /* Key not found. It might be because there really is none, or
+ because we still have it waiting in 'stolen_objects'. */
if (d->public_descriptor->stolen_objects.size > 0)
{
spinlock_acquire(d->public_descriptor->collection_lock, 'N');
@@ -147,7 +166,8 @@
}
}
- if (UNLIKELY(v > d->start_time)) // object too recent?
+ /* The answer is a public object. Is it too recent? */
+ if (UNLIKELY(v > d->start_time))
{
if (v >= LOCKED)
{
@@ -161,10 +181,17 @@
}
else
{
+ /* Not private and not public: it's a protected object
+ */
fprintf(stderr, "read_barrier: %p -> %p protected\n", G, P);
+
+ /* The risks are not high, but in parallel it's possible for the
+ object to be stolen by another thread and become public, after
+ which it can be outdated by another commit. So the following
+ assert can actually fail in that case. */
+ /*assert(P->h_revision & 1);*/
}
- register_in_list_of_read_objects:
gcptrlist_insert(&d->list_of_read_objects, P);
add_in_recent_reads_cache:
@@ -172,43 +199,32 @@
return P;
follow_stub:;
+ /* We know that P is a stub object, because only stubs can have
+ an h_revision that is == 2 mod 4.
+ */
struct tx_public_descriptor *foreign_pd = STUB_THREAD(P);
if (foreign_pd == d->public_descriptor)
{
- /* same thread */
+ /* Same thread: dereference the pointer directly. It's possible
+ we reach any kind of object, even a public object, in case it
+ was stolen. So we just repeat the whole procedure. */
P = (gcptr)(v - 2);
- assert(!(P->h_tid & GCFLAG_PUBLIC));
- if (P->h_revision == stm_private_rev_num)
- {
- fprintf(stderr, "read_barrier: %p -> %p handle "
- "private\n", G, P);
- return P;
- }
- else if (P->h_tid & GCFLAG_PRIVATE_FROM_PROTECTED)
- {
- fprintf(stderr, "read_barrier: %p -> %p handle "
- "private_from_protected\n", G, P);
- goto private_from_protected;
- }
- else if (FXCACHE_AT(P) == P)
- {
- fprintf(stderr, "read_barrier: %p -> %p handle "
- "protected fxcache\n", G, P);
- return P;
- }
- else
- {
- fprintf(stderr, "read_barrier: %p -> %p handle "
- "protected\n", G, P);
- goto register_in_list_of_read_objects;
- }
+ fprintf(stderr, "read_barrier: %p -> %p via stub\n ", G, P);
+
+ if (UNLIKELY((P->h_revision != stm_private_rev_num) &&
+ (FXCACHE_AT(P) != P)))
+ goto restart_all;
+
+ return P;
}
else
{
/* stealing */
fprintf(stderr, "read_barrier: %p -> stealing %p...\n ", G, P);
stm_steal_stub(P);
- goto retry;
+
+ assert(P->h_tid & GCFLAG_PUBLIC);
+ goto restart_all_public;
}
}
@@ -327,21 +343,12 @@
return L;
}
-static gcptr LocalizePublic(struct tx_descriptor *d, gcptr R);
-
static gcptr LocalizeProtected(struct tx_descriptor *d, gcptr P)
{
gcptr B;
- spinlock_acquire(d->public_descriptor->collection_lock, 'L');
-
- if (P->h_tid & GCFLAG_PUBLIC)
- {
- /* became PUBLIC while waiting for the collection_lock */
- spinlock_release(d->public_descriptor->collection_lock);
- return LocalizePublic(d, P);
- }
assert(P->h_revision != stm_private_rev_num);
+ assert(P->h_revision & 1);
assert(!(P->h_tid & GCFLAG_PUBLIC_TO_PRIVATE));
assert(!(P->h_tid & GCFLAG_BACKUP_COPY));
assert(!(P->h_tid & GCFLAG_STUB));
@@ -355,7 +362,6 @@
gcptrlist_insert(&d->private_from_protected, P);
- spinlock_release(d->public_descriptor->collection_lock);
return P;
}
@@ -406,11 +412,17 @@
if (is_private(R))
return R;
+ spinlock_acquire(d->public_descriptor->collection_lock, 'L');
+ if (d->public_descriptor->stolen_objects.size != 0)
+ stm_normalize_stolen_objects(d);
+
if (R->h_tid & GCFLAG_PUBLIC)
W = LocalizePublic(d, R);
else
W = LocalizeProtected(d, R);
+ spinlock_release(d->public_descriptor->collection_lock);
+
fprintf(stderr, "write_barrier: %p -> %p -> %p\n", P, R, W);
return W;
diff --git a/c4/steal.c b/c4/steal.c
--- a/c4/steal.c
+++ b/c4/steal.c
@@ -55,25 +55,60 @@
gcptr L = (gcptr)(v - 2);
+ /* L might be a private_from_protected, or just a protected copy.
+ To know which case it is, read GCFLAG_PRIVATE_FROM_PROTECTED.
+ */
if (L->h_tid & GCFLAG_PRIVATE_FROM_PROTECTED) {
gcptr B = (gcptr)L->h_revision; /* the backup copy */
+
+ /* B is now a backup copy, i.e. a protected object, and we own
+ the foreign thread's collection_lock, so we can read/write the
+ flags
+ */
+ assert(B->h_tid & GCFLAG_BACKUP_COPY);
B->h_tid &= ~GCFLAG_BACKUP_COPY;
- /* add {B: L} in 'public_to_private', but lazily, because we don't
- want to walk over the feet of the foreign thread */
- B->h_tid |= GCFLAG_PUBLIC_TO_PRIVATE;
- gcptrlist_insert2(&foreign_pd->stolen_objects, B, L);
-
+ if (B->h_tid & GCFLAG_PUBLIC_TO_PRIVATE) {
+ /* already stolen */
+ }
+ else {
+ B->h_tid |= GCFLAG_PUBLIC_TO_PRIVATE;
+ /* add {B: L} in 'public_to_private', but lazily, because we
+ don't want to walk over the feet of the foreign thread
+ */
+ gcptrlist_insert2(&foreign_pd->stolen_objects, B, L);
+ }
fprintf(stderr, "stolen: %p -> %p - - -> %p\n", P, B, L);
-
L = B;
}
- /* change L from protected to public */
+ /* Here L is a protected (or backup) copy, and we own the foreign
+ thread's collection_lock, so we can read/write the flags. Change
+ it from protected to public.
+ */
L->h_tid |= GCFLAG_PUBLIC;
- smp_wmb(); /* the following update must occur "after" the flag
- GCFLAG_PUBLIC was added, for other threads */
+ /* Note that all protected or backup copies have a h_revision that
+ is odd.
+ */
+ assert(L->h_revision & 1);
+
+ /* At this point, the object can only be seen by its owning foreign
+ thread and by us. No 3rd thread can see it as long as we own
+ the foreign thread's collection_lock. For the foreign thread,
+ it might suddenly see the GCFLAG_PUBLIC being added to L
+ (but it may not do any change to the flags itself, because
+ it cannot grab its own collection_lock). L->h_revision is an
+ odd number that is also valid on a public up-to-date object.
+ */
+
+ /* If another thread (the foreign or a 3rd party) does a read
+ barrier from P, it must only reach L if all writes to L are
+ visible; i.e. it must not see P->h_revision => L that still
+ doesn't have the GCFLAG_PUBLIC. So we need a CPU write
+ barrier here.
+ */
+ smp_wmb();
/* update the original P->h_revision to point directly to L */
P->h_revision = (revision_t)L;
@@ -92,6 +127,8 @@
gcptr L = items[i + 1];
assert(L->h_tid & GCFLAG_PRIVATE_FROM_PROTECTED);
+ assert(!(B->h_tid & GCFLAG_BACKUP_COPY)); /* already removed */
+
g2l_insert(&d->public_to_private, B, L);
}
gcptrlist_clear(&d->public_descriptor->stolen_objects);
_______________________________________________
pypy-commit mailing list
[email protected]
http://mail.python.org/mailman/listinfo/pypy-commit
