Author: Armin Rigo <ar...@tunes.org>
Branch:
Changeset: r78:98c0b1dadf35
Date: 2013-06-08 15:14 +0200
http://bitbucket.org/pypy/stmgc/changeset/98c0b1dadf35/
Log: in-progress
diff --git a/c4/doc-objects.txt b/c4/doc-objects.txt
--- a/c4/doc-objects.txt
+++ b/c4/doc-objects.txt
@@ -1,3 +1,22 @@
+
+Design goal
+-----------
+
+stm_read_barrier(P) -> P: the read barrier (containing a call in the
+slow path) can be applied on a pointer to an object, and returns a
+possibly different pointer. Afterwards, any reads from the object can
+be done normally (using the returned pointer).
+
+stm_write_barrier(P) -> P: the same for writes (actually read/write mode).
+
+The returned pointers are valid until a potential transaction break ---
+with the exception that the result of stm_read_barrier() will be
+invalidated by a stm_write_barrier() done on the same object.
+
+This means we must not modify an object in-place from thread A when
+thread B might be reading from it! It is the basis for the design
+outlined in the sequel, in which "protected" objects are seen by only
+one thread, whereas "public" objects are seen by all threads.
@@ -8,29 +27,19 @@
Private freshly created
\ Private, with backup
- \ ^ . | ^
- \ / . commit | |
- commit \ modify / . | |
- \ / . commit | | modify
- V / V | |
- Protected, no backup V |
+ \ ^ | ^
+ \ / commit | |
+ commit \ modify / | |
+ \ / | | modify
+ V / | |
+ Protected, no backup V |
^ ^ Protected, with backup
/ | gc |
commit / `----------------'
/
/
- Private copy of (the dotted arrow is followed if the
- a public obj protected backup copy was stolen)
-
-
-
- Protected backup copy
- \
- \
- stealing \ commit of newer version
- \ ,-----------------.
- V | V
- Up-to-date public copy Outdated public copy
+ Private copy of
+ a public obj
@@ -45,6 +54,7 @@
Protected objects:
- converted from fresh private obj (old PRN)
- converted from a private obj with backup ptr to backup
+- converted from a private obj from public GT
- backup copy of a private obj original h_revision
- backup copy still attached to a protected GT
- original obj after GC killed the backup GT
@@ -73,13 +83,15 @@
- the PRN (private revision number): odd, negative, changes for every
transaction that commits
-- dict active_backup_copies = {private converted from protected: backup copy}
+- list active_backup_copies =
+ [(private converted from protected, backup copy)]
- dict public_to_private = {public obj: private copy}
- list read_set containing the objects in the read set, with possibly
some duplicates (but hopefully not too many)
+- list stolen_objects = [(priv/prot object, public copy)]
Kind of object copy distinguishing feature
@@ -154,6 +166,8 @@
update the original P->h_revision to point directly to the new
public copy
+ add (P, new public copy) to stolen_objects
+
Write barrier
diff --git a/c4/doc-stmgc.txt b/c4/doc-stmgc.txt
--- a/c4/doc-stmgc.txt
+++ b/c4/doc-stmgc.txt
@@ -304,3 +304,16 @@
revision numbers of all threads, and theoretically compact each interval
of numbers down to only one number, but still keep one active revision
number per thread.
+
+
+Stealing
+--------
+
+This is done by the *stealing thread* in order to gain access to an
+object that is protected by the *foreign thread*. Stealing is triggered
+when we, the stealing thread, follow a "handle" created by a foreign
+thread. The handle has a reference to the normal protected/private
+object. The process depends on the exact state of the protected/private
+copy. As a general rule, we may carefully read, but not write, to the
+foreign copies during stealing.
+
diff --git a/c4/et.c b/c4/et.c
--- a/c4/et.c
+++ b/c4/et.c
@@ -13,11 +13,6 @@
a transaction inevitable: we then add 1 to it. */
static revision_t global_cur_time = 2;
-/* 'next_locked_value' is incremented by two for every thread that starts.
- XXX it should be fixed at some point because right now the process will
- die if we start more than 0x7fff threads. */
-static revision_t next_locked_value = (LOCKED + 1) | 1;
-
/* a negative odd number that identifies the currently running
transaction within the thread. */
__thread revision_t stm_private_rev_num;
@@ -85,6 +80,11 @@
}
#endif
+static void steal(gcptr P)
+{
+ abort();
+}
+
gcptr stm_DirectReadBarrier(gcptr G)
{
struct tx_descriptor *d = thread_descriptor;
@@ -165,9 +165,9 @@
return P;
old_to_young:;
- revision_t target_lock;
- target_lock = *(revision_t *)(v & ~(HANDLE_BLOCK_SIZE-1));
- if (target_lock == d->my_lock)
+ revision_t target_descriptor_index;
+ target_descriptor_index = *(revision_t *)(v & ~(HANDLE_BLOCK_SIZE-1));
+ if (target_descriptor_index == d->descriptor_index)
{
P = (gcptr)(*(revision_t *)(v - 2));
assert(!(P->h_tid & GCFLAG_PUBLIC));
@@ -194,6 +194,7 @@
{
/* stealing */
fprintf(stderr, "read_barrier: %p -> stealing %p...", G, (gcptr)v);
+ steal(P);
abort();
}
}
@@ -577,7 +578,7 @@
"!!!!!!!!!!!!!!!!!!!!! [%lx] abort %d\n"
"!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n"
"!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n"
- "\n", (long)d->my_lock, num);
+ "\n", (long)d->descriptor_index, num);
if (num != ABRT_MANUAL && d->max_aborts >= 0 && !d->max_aborts--)
{
fprintf(stderr, "unexpected abort!\n");
@@ -773,7 +774,7 @@
handle_block = (revision_t *)
((((intptr_t)handle_block) + HANDLE_BLOCK_SIZE-1)
& ~(HANDLE_BLOCK_SIZE-1));
- handle_block[0] = d->my_lock;
+ handle_block[0] = d->descriptor_index;
handle_block[1] = v;
revision_t w = ((revision_t)(handle_block + 1)) + 2;
@@ -947,7 +948,7 @@
(XXX statically we should know when we're outside
a transaction) */
- fprintf(stderr, "[%lx] inevitable: %s\n", (long)d->my_lock, why);
+ fprintf(stderr, "[%lx] inevitable: %s\n", (long)d->descriptor_index, why);
cur_time = acquire_inev_mutex_and_mark_global_cur_time();
if (d->start_time != cur_time)
@@ -1071,6 +1072,10 @@
/************************************************************/
+struct tx_descriptor *stm_descriptor_array[MAX_THREADS] = {0};
+static revision_t descriptor_array_next = 0;
+static revision_t descriptor_array_lock = 0;
+
int DescriptorInit(void)
{
if (GCFLAG_PREBUILT != PREBUILT_FLAGS)
@@ -1082,33 +1087,39 @@
if (thread_descriptor == NULL)
{
+ revision_t i;
struct tx_descriptor *d = stm_malloc(sizeof(struct tx_descriptor));
memset(d, 0, sizeof(struct tx_descriptor));
+ spinlock_acquire(descriptor_array_lock, 1);
- /* initialize 'my_lock' to be a unique odd number > LOCKED */
- while (1)
+ i = descriptor_array_next;
+ while (stm_descriptor_array[i] != NULL)
{
- d->my_lock = ACCESS_ONCE(next_locked_value);
- if (d->my_lock > INTPTR_MAX - 2)
+ i++;
+ if (i == MAX_THREADS)
+ i = 0;
+ if (i == descriptor_array_next)
{
- /* XXX fix this limitation */
- fprintf(stderr, "XXX error: too many threads ever created "
+ fprintf(stderr, "error: too many threads at the same time "
"in this process");
abort();
}
- if (bool_cas(&next_locked_value, d->my_lock, d->my_lock + 2))
- break;
}
+ descriptor_array_next = i;
+ stm_descriptor_array[i] = d;
+ d->descriptor_index = i;
+ d->my_lock = LOCKED + 2 * i;
assert(d->my_lock & 1);
- assert(d->my_lock > LOCKED);
+ assert(d->my_lock >= LOCKED);
stm_private_rev_num = -1;
d->private_revision_ref = &stm_private_rev_num;
d->max_aborts = -1;
thread_descriptor = d;
fprintf(stderr, "[%lx] pthread %lx starting\n",
- (long)d->my_lock, (long)pthread_self());
+ (long)d->descriptor_index, (long)pthread_self());
+ spinlock_release(descriptor_array_lock);
return 1;
}
else
@@ -1121,6 +1132,7 @@
assert(d != NULL);
assert(d->active == 0);
+ stm_descriptor_array[d->descriptor_index] = NULL;
thread_descriptor = NULL;
g2l_delete(&d->public_to_private);
@@ -1142,7 +1154,7 @@
num_spinloops += d->num_spinloops[i];
p += sprintf(p, "[%lx] finishing: %d commits, %d aborts ",
- (long)d->my_lock,
+ (long)d->descriptor_index,
d->num_commits,
num_aborts);
diff --git a/c4/et.h b/c4/et.h
--- a/c4/et.h
+++ b/c4/et.h
@@ -11,7 +11,8 @@
#define _SRCSTM_ET_H
-#define LOCKED ((INTPTR_MAX - 0xffff) | 1)
+#define MAX_THREADS 1024
+#define LOCKED (INTPTR_MAX - 2*(MAX_THREADS-1))
#define WORD sizeof(gcptr)
#define HANDLE_BLOCK_SIZE (2 * WORD)
@@ -103,6 +104,7 @@
struct tx_descriptor {
jmp_buf *setjmp_buf;
revision_t start_time;
+ revision_t descriptor_index;
revision_t my_lock;
revision_t collection_lock;
gcptr *shadowstack;
@@ -127,11 +129,11 @@
long long longest_abort_info_time;
struct FXCache recent_reads_cache;
revision_t *private_revision_ref;
- struct tx_descriptor *tx_next, *tx_prev; /* a doubly linked list */
};
extern __thread struct tx_descriptor *thread_descriptor;
extern __thread revision_t stm_private_rev_num;
+extern struct tx_descriptor *stm_descriptor_array[];
/************************************************************/
diff --git a/c4/test/support.py b/c4/test/support.py
--- a/c4/test/support.py
+++ b/c4/test/support.py
@@ -84,7 +84,7 @@
gcptr pseudoprebuilt(size_t size, int tid);
revision_t get_private_rev_num(void);
revision_t get_start_time(void);
- revision_t get_my_lock(void);
+ revision_t get_descriptor_index(void);
//gcptr *addr_of_thread_local(void);
//int in_nursery(gcptr);
@@ -93,7 +93,6 @@
/* some constants normally private that are useful in the tests */
#define WORD ...
#define GC_PAGE_SIZE ...
- #define LOCKED ...
#define HANDLE_BLOCK_SIZE ...
#define GCFLAG_OLD ...
#define GCFLAG_VISITED ...
@@ -207,9 +206,9 @@
return thread_descriptor->start_time;
}
- revision_t get_my_lock(void)
+ revision_t get_descriptor_index(void)
{
- return thread_descriptor->my_lock;
+ return thread_descriptor->descriptor_index;
}
/*gcptr *addr_of_thread_local(void)
@@ -551,7 +550,7 @@
def decode_handle(r):
assert (r & 3) == 2
p = r & ~(lib.HANDLE_BLOCK_SIZE-1)
- my_lock = ffi.cast("revision_t *", p)[0]
- assert my_lock >= lib.LOCKED
+ dindex = ffi.cast("revision_t *", p)[0]
+ assert 0 <= dindex < 20
ptr = ffi.cast("gcptr *", r - 2)[0]
- return ptr, my_lock
+ return ptr, dindex
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
@@ -138,7 +138,7 @@
lib.stm_begin_inevitable_transaction()
assert classify(p) == "public"
assert classify(p2) == "protected"
- assert decode_handle(p.h_revision) == (p2, lib.get_my_lock())
+ assert decode_handle(p.h_revision) == (p2, lib.get_descriptor_index())
assert lib.rawgetlong(p, 0) == 28971289
assert lib.rawgetlong(p2, 0) == 1289222
@@ -224,14 +224,36 @@
assert p4 == p2
assert list_of_read_objects() == [p2]
-def test_stealing_protected_without_backup():
+def test_stealing():
p = palloc(HDR + WORD)
+ plist = [p]
def f1(r):
- lib.setlong(p, 0, 2782172)
+ assert (p.h_tid & GCFLAG_PUBLIC_TO_PRIVATE) == 0
+ p1 = lib.stm_write_barrier(p) # private copy
+ assert p1 != p
+ assert classify(p) == "public"
+ assert classify(p1) == "private"
+ assert p.h_tid & GCFLAG_PUBLIC_TO_PRIVATE
+ lib.rawsetlong(p1, 0, 2782172)
lib.stm_commit_transaction()
lib.stm_begin_inevitable_transaction()
+ assert classify(p) == "public"
+ assert classify(p1) == "protected"
+ plist.append(p1)
+ # now p's most recent revision is protected
+ assert p.h_revision % 4 == 2 # a handle
r.set(2)
+ r.wait(3)
+ assert lib.list_stolen_objects() == plist[-2:]
+ p2 = lib.stm_read_barrier(p1)
+ assert p2 == plist[-1]
def f2(r):
r.wait(2)
- assert lib.getlong(p, 0) == 2782172
+ p2 = lib.stm_read_barrier(p) # steals
+ assert lib.rawgetlong(p2, 0) == 2782172
+ assert p.h_revision == int(ffi.cast("revision_t", p2))
+ assert p2 == lib.stm_read_barrier(p)
+ assert p2 not in plist
+ plist.append(p2)
+ r.set(3)
run_parallel(f1, f2)
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit
