Author: Armin Rigo <ar...@tunes.org>
Branch:
Changeset: r958:cb55e6140145
Date: 2014-03-05 10:10 +0100
http://bitbucket.org/pypy/stmgc/changeset/cb55e6140145/
Log: Finish copying the shadow logic from pypy.
diff --git a/c7/stm/core.c b/c7/stm/core.c
--- a/c7/stm/core.c
+++ b/c7/stm/core.c
@@ -36,7 +36,7 @@
by finding that we already own the write-lock. */
uintptr_t lock_idx = (((uintptr_t)obj) >> 4) - WRITELOCK_START;
uint8_t lock_num = STM_PSEGMENT->write_lock_num;
- assert((intptr_t)lock_idx >= 0);
+ assert(lock_idx < sizeof(write_locks));
retry:
if (write_locks[lock_idx] == 0) {
if (UNLIKELY(!__sync_bool_compare_and_swap(&write_locks[lock_idx],
@@ -179,6 +179,7 @@
assert(list_is_empty(STM_PSEGMENT->modified_old_objects));
assert(tree_is_cleared(STM_PSEGMENT->young_outside_nursery));
+ assert(tree_is_cleared(STM_PSEGMENT->nursery_objects_shadows));
assert(STM_PSEGMENT->objects_pointing_to_nursery == NULL);
assert(STM_PSEGMENT->large_overflow_objects == NULL);
@@ -300,7 +301,7 @@
/* clear the write-lock (note that this runs with all other
threads paused, so no need to be careful about ordering) */
uintptr_t lock_idx = (((uintptr_t)item) >> 4) - WRITELOCK_START;
- assert((intptr_t)lock_idx >= 0);
+ assert(lock_idx < sizeof(write_locks));
assert(write_locks[lock_idx] == STM_PSEGMENT->write_lock_num);
write_locks[lock_idx] = 0;
@@ -371,7 +372,8 @@
/* update 'overflow_number' if needed */
if (STM_PSEGMENT->overflow_number_has_been_used) {
highest_overflow_number += GCFLAG_OVERFLOW_NUMBER_bit0;
- assert(highest_overflow_number != 0); /* XXX else, overflow! */
+ assert(highest_overflow_number != /* XXX else, overflow! */
+ (uint32_t)-GCFLAG_OVERFLOW_NUMBER_bit0);
STM_PSEGMENT->overflow_number = highest_overflow_number;
STM_PSEGMENT->overflow_number_has_been_used = false;
}
@@ -440,7 +442,7 @@
/* clear the write-lock */
uintptr_t lock_idx = (((uintptr_t)item) >> 4) - WRITELOCK_START;
- assert((intptr_t)lock_idx >= 0);
+ assert(lock_idx < sizeof(write_locks));
assert(write_locks[lock_idx] == pseg->write_lock_num);
write_locks[lock_idx] = 0;
}));
diff --git a/c7/stm/core.h b/c7/stm/core.h
--- a/c7/stm/core.h
+++ b/c7/stm/core.h
@@ -95,11 +95,16 @@
current transaction spanned a minor collection. */
struct list_s *large_overflow_objects;
- /* List of all young objects outside the nursery ("young" in the
+ /* Set of all young objects outside the nursery ("young" in the
sense that they should be in the nursery, but were too big for
that). */
struct tree_s *young_outside_nursery;
+ /* Support for id and identityhash: this is a dict mapping nursery
+ objects with GCFLAG_HAS_SHADOW to their future location at the
+ next minor collection. */
+ struct tree_s *nursery_objects_shadows;
+
/* Start time: to know approximately for how long a transaction has
been running, in contention management */
uint64_t start_time;
diff --git a/c7/stm/gcpage.c b/c7/stm/gcpage.c
--- a/c7/stm/gcpage.c
+++ b/c7/stm/gcpage.c
@@ -151,7 +151,6 @@
static inline uintptr_t mark_loc(object_t *obj)
{
uintptr_t lock_idx = (((uintptr_t)obj) >> 4) - WRITELOCK_START;
- assert(lock_idx >= 0);
assert(lock_idx < sizeof(write_locks));
return lock_idx;
}
diff --git a/c7/stm/hash_id.c b/c7/stm/hash_id.c
--- a/c7/stm/hash_id.c
+++ b/c7/stm/hash_id.c
@@ -17,7 +17,7 @@
if (obj != NULL) {
if (_is_in_nursery(obj)) {
- abort();//obj = find_shadow(obj);
+ obj = find_shadow(obj);
}
else if (is_hash) {
if (obj->stm_flags & GCFLAG_HAS_SHADOW) {
diff --git a/c7/stm/nursery.c b/c7/stm/nursery.c
--- a/c7/stm/nursery.c
+++ b/c7/stm/nursery.c
@@ -53,10 +53,12 @@
return _is_in_nursery(obj);
}
+static object_t *find_existing_shadow(object_t *obj);
+
/************************************************************/
-#define GCWORD_MOVED ((object_t *) -42)
+#define GCWORD_MOVED ((object_t *) -1)
#define FLAG_SYNC_LARGE 0x01
@@ -76,18 +78,33 @@
to GCWORD_MOVED. In that case, the forwarding location, i.e.
where the object moved to, is stored in the second word in 'obj'. */
object_t *TLPREFIX *pforwarded_array = (object_t *TLPREFIX *)obj;
+ char *realobj;
+ size_t size;
- if (pforwarded_array[0] == GCWORD_MOVED) {
- *pobj = pforwarded_array[1]; /* already moved */
- return;
+ if (obj->stm_flags & GCFLAG_HAS_SHADOW) {
+ /* ^^ the single check above detects both already-moved objects
+ and objects with HAS_SHADOW. This is because GCWORD_MOVED
+ overrides completely the stm_flags field with 1's bits. */
+
+ if (LIKELY(pforwarded_array[0] == GCWORD_MOVED)) {
+ *pobj = pforwarded_array[1]; /* already moved */
+ return;
+ }
+ else {
+ /* really has a shadow */
+ nobj = find_existing_shadow(obj);
+ obj->stm_flags &= ~GCFLAG_HAS_SHADOW;
+ realobj = REAL_ADDRESS(STM_SEGMENT->segment_base, obj);
+ size = stmcb_size_rounded_up((struct object_s *)realobj);
+ goto copy_large_object;
+ }
}
-
/* We need to make a copy of this object. It goes either in
a largemalloc.c-managed area, or if it's small enough, in
one of the small uniform pages from gcpage.c.
*/
- char *realobj = REAL_ADDRESS(STM_SEGMENT->segment_base, obj);
- size_t size = stmcb_size_rounded_up((struct object_s *)realobj);
+ realobj = REAL_ADDRESS(STM_SEGMENT->segment_base, obj);
+ size = stmcb_size_rounded_up((struct object_s *)realobj);
if (1 /*size >= GC_N_SMALL_REQUESTS*8*/) {
@@ -97,6 +114,7 @@
nobj = (object_t *)(allocated - stm_object_pages);
/* Copy the object */
+ copy_large_object:;
char *realnobj = REAL_ADDRESS(STM_SEGMENT->segment_base, nobj);
memcpy(realnobj, realobj, size);
@@ -229,6 +247,8 @@
tree_clear(pseg->young_outside_nursery);
}
+
+ tree_clear(pseg->nursery_objects_shadows);
}
#define MINOR_NOTHING_TO_DO(pseg) \
@@ -340,7 +360,7 @@
char *result = allocate_outside_nursery_large(size_rounded_up);
object_t *o = (object_t *)(result - stm_object_pages);
- tree_insert(STM_PSEGMENT->young_outside_nursery, (intptr_t)o, 0);
+ tree_insert(STM_PSEGMENT->young_outside_nursery, (uintptr_t)o, 0);
memset(REAL_ADDRESS(STM_SEGMENT->segment_base, o), 0, size_rounded_up);
return o;
@@ -413,3 +433,60 @@
set_gs_register(get_segment_base(original_num));
}
+
+static object_t *allocate_shadow(object_t *obj)
+{
+ char *realobj = REAL_ADDRESS(STM_SEGMENT->segment_base, obj);
+ size_t size = stmcb_size_rounded_up((struct object_s *)realobj);
+
+ /* always gets outside as a large object for now */
+ char *allocated = allocate_outside_nursery_large(size);
+ object_t *nobj = (object_t *)(allocated - stm_object_pages);
+
+ /* Initialize the shadow enough to be considered a valid gc object.
+ If the original object stays alive at the next minor collection,
+ it will anyway be copied over the shadow and overwrite the
+ following fields. But if the object dies, then the shadow will
+ stay around and only be freed at the next major collection, at
+ which point we want it to look valid (but ready to be freed).
+
+ Here, in the general case, it requires copying the whole object.
+ It could be more optimized in special cases like in PyPy, by
+ copying only the typeid and (for var-sized objects) the length
+ field. It's probably overkill to add a special stmcb_xxx
+ interface just for that.
+ */
+ char *realnobj = REAL_ADDRESS(STM_SEGMENT->segment_base, nobj);
+ memcpy(realnobj, realobj, size);
+
+ obj->stm_flags |= GCFLAG_HAS_SHADOW;
+ tree_insert(STM_PSEGMENT->nursery_objects_shadows,
+ (uintptr_t)obj, (uintptr_t)nobj);
+ return nobj;
+}
+
+static object_t *find_existing_shadow(object_t *obj)
+{
+ wlog_t *item;
+
+ TREE_FIND(*STM_PSEGMENT->nursery_objects_shadows,
+ (uintptr_t)obj, item, goto not_found);
+
+ /* The answer is the address of the shadow. */
+ return (object_t *)item->val;
+
+ not_found:
+ stm_fatalerror("GCFLAG_HAS_SHADOW but no shadow found");
+}
+
+static object_t *find_shadow(object_t *obj)
+{
+ /* The object 'obj' is still in the nursery. Find or allocate a
+ "shadow" object, which is where the object will be moved by the
+ next minor collection
+ */
+ if (obj->stm_flags & GCFLAG_HAS_SHADOW)
+ return find_existing_shadow(obj);
+ else
+ return allocate_shadow(obj);
+}
diff --git a/c7/stm/nursery.h b/c7/stm/nursery.h
--- a/c7/stm/nursery.h
+++ b/c7/stm/nursery.h
@@ -19,3 +19,5 @@
}
static void assert_memset_zero(void *s, size_t n);
+
+static object_t *find_shadow(object_t *obj);
diff --git a/c7/stm/setup.c b/c7/stm/setup.c
--- a/c7/stm/setup.c
+++ b/c7/stm/setup.c
@@ -58,6 +58,7 @@
pr->large_overflow_objects = NULL;
pr->modified_old_objects = list_create();
pr->young_outside_nursery = tree_create();
+ pr->nursery_objects_shadows = tree_create();
pr->overflow_number = GCFLAG_OVERFLOW_NUMBER_bit0 * (i + 1);
highest_overflow_number = pr->overflow_number;
}
@@ -94,6 +95,7 @@
assert(pr->large_overflow_objects == NULL);
list_free(pr->modified_old_objects);
tree_free(pr->young_outside_nursery);
+ tree_free(pr->nursery_objects_shadows);
}
munmap(stm_object_pages, TOTAL_MEMORY);
diff --git a/c7/test/test_hash_id.py b/c7/test/test_hash_id.py
--- a/c7/test/test_hash_id.py
+++ b/c7/test/test_hash_id.py
@@ -37,3 +37,38 @@
h2 = lib.stm_id(lp2)
assert h1 == int(ffi.cast("long", lp1))
assert h2 == int(ffi.cast("long", lp2))
+
+ def test_hash_nursery(self):
+ self.start_transaction()
+ lp1 = stm_allocate(16)
+ lp2 = stm_allocate(16)
+ lp3 = stm_allocate(16)
+ lp4 = stm_allocate(16)
+ h1 = lib.stm_identityhash(lp1)
+ h2 = lib.stm_identityhash(lp2)
+ h3 = lib.stm_identityhash(lp3)
+ h4 = lib.stm_identityhash(lp4)
+ assert len(set([h1, h2, h3, h4])) == 4 # guaranteed by the algo
+
+ def test_hash_lower_bits(self):
+ self.start_transaction()
+ lp1 = stm_allocate(32)
+ lp2 = stm_allocate(32)
+ lp3 = stm_allocate(32)
+ lp4 = stm_allocate(32)
+ h1 = lib.stm_identityhash(lp1)
+ h2 = lib.stm_identityhash(lp2)
+ h3 = lib.stm_identityhash(lp3)
+ h4 = lib.stm_identityhash(lp4)
+ assert len(set([h1 & 15, h2 & 15, h3 & 15, h4 & 15])) == 4
+
+ def test_hash_around_minor_collect(self):
+ self.start_transaction()
+ lp = stm_allocate(16)
+ h1 = lib.stm_identityhash(lp)
+ self.push_root(lp)
+ stm_minor_collect()
+ lp = self.pop_root()
+ h2 = lib.stm_identityhash(lp)
+ assert h2 == h1
+ assert h2 != lib.stm_id(lp)
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
