Author: Armin Rigo <[email protected]>
Branch:
Changeset: r232:db385d3d043d
Date: 2013-06-22 11:12 +0200
http://bitbucket.org/pypy/stmgc/changeset/db385d3d043d/
Log: hg merge implement-id
Right now test_multi_thread doesn't pass, but I'll investigate
diff --git a/c4/demo_random.c b/c4/demo_random.c
--- a/c4/demo_random.c
+++ b/c4/demo_random.c
@@ -13,7 +13,7 @@
#define NUMTHREADS 4
-#define STEPS 100000
+#define STEPS 1000000
#define NUMROOTS 10 // per thread
#define PREBUILT 3 // per thread
#define MAXROOTS 1000
@@ -27,6 +27,7 @@
struct node {
struct stm_object_s hdr;
long value;
+ revision_t id;
struct node *next;
};
typedef struct node * nodeptr;
@@ -82,6 +83,7 @@
gcptr x = calloc(1, size);
x->h_tid = PREBUILT_FLAGS | tid;
x->h_revision = PREBUILT_REVISION;
+ x->h_original = 0;
return x;
}
@@ -183,12 +185,12 @@
return result1;
}
-static const revision_t C_PRIVATE_FROM_PROTECTED = 1;
-static const revision_t C_PRIVATE = 2;
-static const revision_t C_STUB = 3;
-static const revision_t C_PUBLIC = 4;
-static const revision_t C_BACKUP = 5;
-static const revision_t C_PROTECTED = 6;
+static const int C_PRIVATE_FROM_PROTECTED = 1;
+static const int C_PRIVATE = 2;
+static const int C_STUB = 3;
+static const int C_PUBLIC = 4;
+static const int C_BACKUP = 5;
+static const int C_PROTECTED = 6;
int classify(gcptr p)
{
int priv_from_prot = (p->h_tid & GCFLAG_PRIVATE_FROM_PROTECTED) != 0;
@@ -260,7 +262,7 @@
num = get_rand(SHARED_ROOTS);
_sr = shared_roots[num];
- k = get_rand(14);
+ k = get_rand(17);
switch (k) {
case 0: // remove a root
@@ -316,8 +318,34 @@
w_sr = (nodeptr)write_barrier(_sr);
w_sr->next = (nodeptr)shared_roots[get_rand(SHARED_ROOTS)];
break;
- default:
+ case 14:
+ push_roots();
+ stmgc_minor_collect();
+ pop_roots();
+ p = NULL;
break;
+ case 15: /* test stm_id on non-shared roots */
+ w_r = (nodeptr)read_barrier(_r);
+ if (w_r->id) {
+ assert(w_r->id == stm_id((gcptr)w_r));
+ assert(w_r->id == stm_id((gcptr)_r));
+ }
+ else {
+ w_r = (nodeptr)write_barrier(_r);
+ w_r->id = stm_id((gcptr)w_r);
+ assert(w_r->id == stm_id((gcptr)_r));
+ }
+ case 16: /* test stm_id on shared roots */
+ w_sr = (nodeptr)read_barrier(_sr);
+ if (w_sr->id) {
+ assert(w_sr->id == stm_id((gcptr)w_sr));
+ assert(w_sr->id == stm_id((gcptr)_sr));
+ }
+ else {
+ w_sr = (nodeptr)write_barrier(_sr);
+ w_sr->id = stm_id((gcptr)w_sr);
+ assert(w_sr->id == stm_id((gcptr)_sr));
+ }
}
return p;
}
@@ -344,17 +372,21 @@
int interruptible_callback(gcptr arg1, int retry_counter)
{
td.num_roots = td.num_roots_outside_perform;
- copy_roots(td.roots_outside_perform, td.roots, td.num_roots);
+ // done & overwritten by the following pop_roots():
+ // copy_roots(td.roots_outside_perform, td.roots, td.num_roots);
+ // refresh td.roots:
arg1 = stm_pop_root();
+ assert(arg1 == NULL);
pop_roots();
push_roots();
stm_push_root(arg1);
int p = run_me();
- int restart = p == -1 ? get_rand(3) != 1 : 0;
+ if (p == -1) // maybe restart transaction
+ return get_rand(3) != 1;
- return restart;
+ return 0;
}
int run_me()
diff --git a/c4/et.c b/c4/et.c
--- a/c4/et.c
+++ b/c4/et.c
@@ -447,7 +447,15 @@
B = stmgc_duplicate_old(P);
B->h_tid |= GCFLAG_BACKUP_COPY;
-
+ B->h_tid &= ~GCFLAG_HAS_ID;
+ if (!(P->h_original) && (P->h_tid & GCFLAG_OLD)) {
+ /* if P is old, it must be the original
+ if P is young, it will create a shadow original later
+ or it's getting decided when backup gets stolen.
+ */
+ B->h_original = (revision_t)P;
+ }
+
P->h_tid |= GCFLAG_PRIVATE_FROM_PROTECTED;
P->h_revision = (revision_t)B;
@@ -474,6 +482,13 @@
/* note that stmgc_duplicate() usually returns a young object, but may
return an old one if the nursery is full at this moment. */
gcptr L = stmgc_duplicate(R);
+ if (!(L->h_original)) {
+ /* if we don't have an original object yet,
+ it must be the old public R */
+ assert(R->h_tid & GCFLAG_OLD); // if not, force stm_id??
+ L->h_original = (revision_t)R;
+ }
+
assert(!(L->h_tid & GCFLAG_BACKUP_COPY));
assert(!(L->h_tid & GCFLAG_STUB));
assert(!(L->h_tid & GCFLAG_PRIVATE_FROM_PROTECTED));
@@ -1010,7 +1025,19 @@
stub->h_tid = (L->h_tid & STM_USER_TID_MASK) | GCFLAG_PUBLIC
| GCFLAG_STUB
| GCFLAG_OLD;
+ assert(!(L->h_tid & GCFLAG_HAS_ID));
stub->h_revision = ((revision_t)L) | 2;
+ if (L->h_original) {
+ stub->h_original = L->h_original;
+ }
+ else if (L->h_tid & GCFLAG_OLD) {
+ stub->h_original = (revision_t)L;
+ }
+ else {
+ L->h_original = (revision_t)stub;
+ assert(0);
+ }
+
item->val = stub;
} G2L_LOOP_END;
@@ -1076,6 +1103,8 @@
if (B->h_tid & GCFLAG_PUBLIC)
{
+ assert(!(P->h_tid & GCFLAG_HAS_ID));
+
/* B was stolen */
while (1)
{
@@ -1086,7 +1115,15 @@
if (bool_cas(&B->h_revision, v, (revision_t)P))
break;
}
- }
+ }
+ else if (P->h_original == (revision_t)B) {
+ /* The backup is the "id object" */
+ assert(!(P->h_tid & GCFLAG_HAS_ID));
+
+ B->h_tid &= ~GCFLAG_BACKUP_COPY;
+ B->h_tid |= GCFLAG_PUBLIC;
+ B->h_revision = (revision_t)P;
+ }
else
{
stmgcpage_free(B);
@@ -1118,6 +1155,7 @@
{
assert(!(B->h_tid & GCFLAG_BACKUP_COPY));
P->h_tid |= GCFLAG_PUBLIC;
+ P->h_tid &= ~GCFLAG_HAS_ID; // just in case
if (!(P->h_tid & GCFLAG_OLD)) P->h_tid |= GCFLAG_NURSERY_MOVED;
/* P becomes a public outdated object. It may create an
exception documented in doc-objects.txt: a public but young
@@ -1126,10 +1164,20 @@
stealing will follow its h_revision (to B).
*/
}
+ else if (P->h_original == (revision_t)B) {
+ /* The backup is the "id object". P becomes outdated. */
+ assert(!(P->h_tid & GCFLAG_HAS_ID));
+ P->h_tid |= GCFLAG_PUBLIC;
+ B->h_tid |= GCFLAG_PUBLIC;
+ B->h_tid &= ~GCFLAG_BACKUP_COPY;
+ if (!(P->h_tid & GCFLAG_OLD)) P->h_tid |= GCFLAG_NURSERY_MOVED;
+ }
else
{
/* copy the backup copy B back over the now-protected object P,
and then free B, which will not be used any more. */
+ assert(!(P->h_original)
+ || (B->h_original == (revision_t)P->h_original));
size_t size = stmcb_size(B);
assert(B->h_tid & GCFLAG_BACKUP_COPY);
memcpy(((char *)P) + offsetof(struct stm_object_s, h_revision),
diff --git a/c4/et.h b/c4/et.h
--- a/c4/et.h
+++ b/c4/et.h
@@ -57,6 +57,9 @@
* but converted from a protected. These are precisely the objects
* that have a backup copy (in h_revision), which gives a copy of the
* original protected object.
+ *
+ * GCFLAG_HAS_ID is set on young objects that have an old reserved
+ * memory to be copied to in minor collections (obj->h_original)
*/
static const revision_t GCFLAG_OLD = STM_FIRST_GCFLAG << 0;
static const revision_t GCFLAG_VISITED = STM_FIRST_GCFLAG << 1;
@@ -68,6 +71,7 @@
static const revision_t GCFLAG_BACKUP_COPY /*debug*/ = STM_FIRST_GCFLAG << 7;
static const revision_t GCFLAG_STUB /*debug*/ = STM_FIRST_GCFLAG << 8;
static const revision_t GCFLAG_PRIVATE_FROM_PROTECTED = STM_FIRST_GCFLAG << 9;
+static const revision_t GCFLAG_HAS_ID = STM_FIRST_GCFLAG << 10;
/* this value must be reflected in PREBUILT_FLAGS in stmgc.h */
#define GCFLAG_PREBUILT (GCFLAG_VISITED | \
diff --git a/c4/nursery.c b/c4/nursery.c
--- a/c4/nursery.c
+++ b/c4/nursery.c
@@ -59,6 +59,7 @@
assert(tid == (tid & STM_USER_TID_MASK));
P->h_tid = tid;
P->h_revision = stm_private_rev_num;
+ P->h_original = 0;
return P;
}
@@ -71,6 +72,8 @@
memcpy(L, P, size);
L->h_tid &= ~GCFLAG_OLD;
+ L->h_tid &= ~GCFLAG_HAS_ID;
+
return L;
}
@@ -80,11 +83,93 @@
gcptr L = (gcptr)stmgcpage_malloc(size);
memcpy(L, P, size);
L->h_tid |= GCFLAG_OLD;
+
return L;
}
/************************************************************/
+
+revision_t stm_hash(gcptr p)
+{
+ return stm_id(p);
+}
+
+revision_t stm_id(gcptr p)
+{
+ struct tx_descriptor *d = thread_descriptor;
+ revision_t result;
+
+
+ if (p->h_original) { /* fast path */
+ fprintf(stderr, "stm_id(%p) has orig fst: %p\n",
+ p, (gcptr)p->h_original);
+ return p->h_original;
+ }
+ else if (!(p->h_tid & GCFLAG_PRIVATE_FROM_PROTECTED)
+ && (p->h_tid & GCFLAG_OLD)) {
+ /* we can be sure that p->h_original doesn't
+ get set during the if and the else-if */
+ fprintf(stderr, "stm_id(%p) is old, orig=0 fst: %p\n", p, p);
+ return (revision_t)p;
+ }
+
+ spinlock_acquire(d->public_descriptor->collection_lock, 'I');
+ /* old objects must have an h_original xOR be
+ the original itself.
+ if some thread stole p when it was still young,
+ it must have set h_original. stealing an old obj
+ makes the old obj "original".
+ */
+ if (p->h_original) { /* maybe now? */
+ result = p->h_original;
+ fprintf(stderr, "stm_id(%p) has orig: %p\n",
+ p, (gcptr)p->h_original);
+ }
+ else if (p->h_tid & GCFLAG_OLD) {
+ /* it must be this exact object */
+ result = (revision_t)p;
+ fprintf(stderr, "stm_id(%p) is old, orig=0: %p\n", p, p);
+ }
+ else {
+ /* must create shadow original object or use
+ backup, if exists */
+ if (p->h_tid & GCFLAG_PRIVATE_FROM_PROTECTED) {
+ gcptr B = (gcptr)p->h_revision;
+ /* don't set, otherwise nursery will copy over backup */
+ //p->h_tid |= GCFLAG_HAS_ID; // see AbortPrivateFromProtected
+ p->h_original = (revision_t)B;
+ // B->h_tid |= GCFLAG_PUBLIC; done by CommitPrivateFromProtected
+
+ result = (revision_t)B;
+ fprintf(stderr, "stm_id(%p) young, pfp, use backup %p\n",
+ p, (gcptr)p->h_original);
+ }
+ else {
+ gcptr O = stmgc_duplicate_old(p);
+ p->h_original = (revision_t)O;
+ p->h_tid |= GCFLAG_HAS_ID;
+ O->h_tid |= GCFLAG_PUBLIC;
+
+ result = (revision_t)O;
+ fprintf(stderr, "stm_id(%p) young, make shadow %p\n", p, O);
+ }
+ }
+
+ spinlock_release(d->public_descriptor->collection_lock);
+ return result;
+}
+
+revision_t stm_pointer_equal(gcptr p1, gcptr p2)
+{
+ /* types must be the same */
+ if ((p1->h_tid & STM_USER_TID_MASK) != (p2->h_tid & STM_USER_TID_MASK))
+ return 0;
+ return stm_id(p1) == stm_id(p2);
+}
+
+/************************************************************/
+
static inline gcptr create_old_object_copy(gcptr obj)
{
assert(!(obj->h_tid & GCFLAG_PUBLIC));
@@ -100,6 +185,18 @@
return fresh_old_copy;
}
+inline void copy_to_old_id_copy(gcptr obj, gcptr id)
+{
+ assert(!is_in_nursery(thread_descriptor, id));
+ assert(id->h_tid & GCFLAG_OLD);
+
+ size_t size = stmcb_size(obj);
+ memcpy(id, obj, size);
+ id->h_tid &= ~GCFLAG_HAS_ID;
+ id->h_tid |= GCFLAG_OLD;
+ fprintf(stderr, "copy_to_old_id_copy(%p -> %p)\n", obj, id);
+}
+
static void visit_if_young(gcptr *root)
{
gcptr obj = *root;
@@ -111,17 +208,29 @@
}
else {
/* it's a nursery object. Was it already moved? */
-
if (UNLIKELY(obj->h_tid & GCFLAG_NURSERY_MOVED)) {
/* yes. Such an object can be a public object in the nursery
too (such objects are always NURSERY_MOVED). For all cases,
- we can just fix the ref. */
+ we can just fix the ref.
+ Can be stolen objects or those we already moved.
+ */
*root = (gcptr)obj->h_revision;
return;
}
- /* make a copy of it outside */
- fresh_old_copy = create_old_object_copy(obj);
+ if (obj->h_tid & GCFLAG_HAS_ID) {
+ /* already has a place to go to */
+ gcptr id_obj = (gcptr)obj->h_original;
+
+ copy_to_old_id_copy(obj, id_obj);
+ fresh_old_copy = id_obj;
+ obj->h_tid &= ~GCFLAG_HAS_ID;
+ }
+ else {
+ /* make a copy of it outside */
+ fresh_old_copy = create_old_object_copy(obj);
+ }
+
obj->h_tid |= GCFLAG_NURSERY_MOVED;
obj->h_revision = (revision_t)fresh_old_copy;
diff --git a/c4/steal.c b/c4/steal.c
--- a/c4/steal.c
+++ b/c4/steal.c
@@ -11,6 +11,8 @@
struct stm_object_s stubs[STUB_NB_OBJS];
};
+inline void copy_to_old_id_copy(gcptr obj, gcptr id);
+
gcptr stm_stub_malloc(struct tx_public_descriptor *pd)
{
assert(pd->collection_lock != 0);
@@ -80,6 +82,16 @@
| GCFLAG_STUB
| GCFLAG_OLD;
stub->h_revision = ((revision_t)obj) | 2;
+ if (obj->h_original) {
+ stub->h_original = obj->h_original;
+ }
+ else if (obj->h_tid & GCFLAG_OLD) {
+ stub->h_original = (revision_t)obj;
+ }
+ else {
+ obj->h_original = (revision_t)stub;
+ }
+
g2l_insert(&sd->all_stubs, obj, stub);
if (!(obj->h_tid & GCFLAG_OLD))
@@ -107,6 +119,24 @@
*/
if (L->h_tid & GCFLAG_PRIVATE_FROM_PROTECTED) {
gcptr B = (gcptr)L->h_revision; /* the backup copy */
+
+ if (L->h_original) {
+ /* L has an original, may be GCFLAG_HAS_ID */
+ B->h_original = L->h_original;
+ }
+ else if (L->h_tid & GCFLAG_OLD) {
+ /* If old, it must be the original */
+ assert(!(L->h_tid & GCFLAG_HAS_ID));
+ /* original must be L */
+ B->h_original = (revision_t)L;
+ assert(0);
+ }
+ else {
+ /* we can make the backup the "original"
+ since L hasn't decided yet */
+ L->h_original = (revision_t)B;
+ assert(0);
+ }
/* 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
@@ -150,10 +180,28 @@
fprintf(stderr, "stolen: %p -> %p\n", P, L);
- /* Copy the object out of the other thread's nursery, if needed */
- if (!(L->h_tid & GCFLAG_OLD)) {
- gcptr O = stmgc_duplicate_old(L);
- L->h_revision = (revision_t)O;
+
+ if (!(L->h_tid & GCFLAG_OLD)) {
+ gcptr O;
+
+ if (L->h_tid & GCFLAG_HAS_ID) {
+ /* use id-copy for us */
+ O = (gcptr)L->h_original;
+ L->h_tid &= ~GCFLAG_HAS_ID;
+ L->h_revision = (revision_t)O;
+ copy_to_old_id_copy(L, (gcptr)L->h_original);
+ } else {
+ /* Copy the object out of the other thread's nursery,
+ if needed */
+ O = stmgc_duplicate_old(L);
+ L->h_revision = (revision_t)O;
+
+ /* young and without original?
+ we may lose the HAS_ID flag like above */
+ if (!(L->h_original))
+ L->h_original = (revision_t)O;
+ }
+
L->h_tid |= GCFLAG_PUBLIC | GCFLAG_NURSERY_MOVED;
/* subtle: we need to remove L from the fxcache of the target
thread, otherwise its read barrier might not trigger on it.
@@ -165,6 +213,7 @@
L = O;
fprintf(stderr, "\t---> %p\n", L);
}
+
assert(L->h_tid & GCFLAG_OLD);
}
diff --git a/c4/steal.h b/c4/steal.h
--- a/c4/steal.h
+++ b/c4/steal.h
@@ -2,7 +2,7 @@
#define _SRCSTM_STEAL_H
-#define STUB_BLOCK_SIZE (16 * WORD) /* power of two */
+#define STUB_BLOCK_SIZE (32 * WORD) /* power of two */
#define STUB_THREAD(h) (*(struct tx_public_descriptor **) \
(((revision_t)(h)) & ~(STUB_BLOCK_SIZE-1)))
diff --git a/c4/stmgc.h b/c4/stmgc.h
--- a/c4/stmgc.h
+++ b/c4/stmgc.h
@@ -10,6 +10,7 @@
typedef struct stm_object_s {
revision_t h_tid;
revision_t h_revision;
+ revision_t h_original;
} *gcptr;
@@ -28,6 +29,14 @@
/* allocate an object out of the local nursery */
gcptr stm_allocate(size_t size, unsigned long tid);
+/* returns a never changing hash for the object */
+revision_t stm_hash(gcptr);
+/* returns an for the object which is unique during its lifetime */
+revision_t stm_id(gcptr);
+/* returns nonzero if the two object-copy pointers belong to the
+same original object */
+revision_t stm_pointer_equal(gcptr, gcptr);
+
/* to push/pop objects into the local shadowstack */
/* (could be turned into macros or something later) */
void stm_push_root(gcptr);
diff --git a/c4/test/support.py b/c4/test/support.py
--- a/c4/test/support.py
+++ b/c4/test/support.py
@@ -32,6 +32,7 @@
typedef struct stm_object_s {
revision_t h_tid;
revision_t h_revision;
+ revision_t h_original;
} *gcptr;
int gettid(gcptr);
@@ -41,6 +42,9 @@
#define PREBUILT_REVISION ...
gcptr stm_allocate(size_t size, unsigned int tid);
+ revision_t stm_hash(gcptr);
+ revision_t stm_id(gcptr);
+ revision_t stm_pointer_equal(gcptr, gcptr);
void stm_push_root(gcptr);
gcptr stm_pop_root(void);
void stm_set_max_aborts(int max_aborts);
@@ -107,6 +111,7 @@
#define GCFLAG_NURSERY_MOVED ...
#define GCFLAG_STUB ...
#define GCFLAG_PRIVATE_FROM_PROTECTED ...
+ #define GCFLAG_HAS_ID ...
#define ABRT_MANUAL ...
typedef struct { ...; } page_header_t;
''')
@@ -606,4 +611,10 @@
assert (r % 4) == 0
return ffi.cast("gcptr", r)
+def follow_original(p):
+ r = p.h_original
+ assert (r % 4) == 0
+ return ffi.cast("gcptr", r)
+
+
nrb_protected = ffi.cast("gcptr", -1)
diff --git a/c4/test/test_et.py b/c4/test/test_et.py
--- a/c4/test/test_et.py
+++ b/c4/test/test_et.py
@@ -198,6 +198,49 @@
assert p4 == p2
assert list_of_read_objects() == [p2]
+
+def test_id_young_to_old():
+ # move out of nursery with shadow original
+ p = nalloc(HDR)
+ assert p.h_original == 0
+ pid = lib.stm_id(p)
+ assert p.h_tid & GCFLAG_HAS_ID
+ porig = follow_original(p)
+ assert porig.h_tid & GCFLAG_OLD
+ lib.stm_push_root(p)
+ minor_collect()
+ p = lib.stm_pop_root()
+ assert not lib.in_nursery(p)
+ assert pid == lib.stm_id(p)
+
+def test_id_private_from_protected():
+ # read and write from protected
+ p = oalloc(HDR)
+ pid = lib.stm_id(p)
+ porig = follow_original(p)
+ # impl detail {
+ # old objects have id==itself, if not set differently
+ assert porig == ffi.NULL
+ assert ffi.cast("gcptr", pid) == p
+ # }
+
+ p1 = oalloc(HDR)
+ p1id = lib.stm_id(p1)
+ p1r = lib.stm_read_barrier(p1)
+ assert lib.stm_id(p1r) == p1id
+ p1w = lib.stm_write_barrier(p1)
+ assert lib.stm_id(p1w) == p1id
+
+ p2 = oalloc(HDR)
+ p2w = lib.stm_write_barrier(p2)
+ p2id = lib.stm_id(p2)
+ assert p2id == lib.stm_id(p2w)
+ # impl detail {
+ assert p2w.h_original == 0
+ assert follow_revision(p2w).h_original == lib.stm_id(p2w)
+ # }
+
+
def test_stealing_old():
p = palloc(HDR + WORD)
plist = [p]
diff --git a/c4/test/test_gcpage.py b/c4/test/test_gcpage.py
--- a/c4/test/test_gcpage.py
+++ b/c4/test/test_gcpage.py
@@ -12,7 +12,7 @@
def test_HDR():
import struct
- assert HDR == struct.calcsize("PP")
+ assert HDR == struct.calcsize("PPP")
def test_malloc_simple():
assert count_pages() == 0
_______________________________________________
pypy-commit mailing list
[email protected]
http://mail.python.org/mailman/listinfo/pypy-commit
