Author: Armin Rigo <[email protected]>
Branch:
Changeset: r1612:e0ff682f6615
Date: 2015-02-09 00:05 +0100
http://bitbucket.org/pypy/stmgc/changeset/e0ff682f6615/
Log: The hack to copy around the other segment's read markers doesn't
really seem to work at all. Change the approach.
diff --git a/c7/stm/core.c b/c7/stm/core.c
--- a/c7/stm/core.c
+++ b/c7/stm/core.c
@@ -373,6 +373,7 @@
assert(list_is_empty(STM_PSEGMENT->modified_old_objects));
assert(list_is_empty(STM_PSEGMENT->modified_old_objects_markers));
+ assert(list_is_empty(STM_PSEGMENT->modified_old_hashtables));
assert(list_is_empty(STM_PSEGMENT->young_weakrefs));
assert(tree_is_cleared(STM_PSEGMENT->young_outside_nursery));
assert(tree_is_cleared(STM_PSEGMENT->nursery_objects_shadows));
@@ -437,29 +438,45 @@
continue; /* no need to check: is pending immediate abort */
char *remote_base = get_segment_base(i);
+ object_t *conflicting_obj;
LIST_FOREACH_R(
STM_PSEGMENT->modified_old_objects,
object_t * /*item*/,
({
if (was_read_remote(remote_base, item)) {
- /* A write-read conflict! */
- dprintf(("write-read conflict on %p, our seg: %d, other:
%ld\n",
- item, STM_SEGMENT->segment_num, i));
- if (write_read_contention_management(i, item)) {
- /* If we reach this point, we didn't abort, but we
- had to wait for the other thread to commit. If we
- did, then we have to restart committing from our
call
- to synchronize_all_threads(). */
- return true;
- }
- /* we aborted the other transaction without waiting, so
- we can just break out of this loop on
- modified_old_objects and continue with the next
- segment */
- break;
+ conflicting_obj = item;
+ goto found_conflict;
}
}));
+
+ LIST_FOREACH_R(
+ STM_PSEGMENT->modified_old_hashtables,
+ object_t * /*item*/,
+ ({
+ if (was_read_remote(remote_base, item)) {
+ conflicting_obj = item;
+ goto found_conflict;
+ }
+ }));
+
+ continue;
+
+ found_conflict:
+ /* A write-read conflict! */
+ dprintf(("write-read conflict on %p, our seg: %d, other: %ld\n",
+ conflicting_obj, STM_SEGMENT->segment_num, i));
+ if (write_read_contention_management(i, conflicting_obj)) {
+ /* If we reach this point, we didn't abort, but we
+ had to wait for the other thread to commit. If we
+ did, then we have to restart committing from our call
+ to synchronize_all_threads(). */
+ return true;
+ }
+ /* we aborted the other transaction without waiting, so we can
+ just ignore the rest of this (now aborted) segment. Let's
+ move on to the next one. */
+ continue;
}
return false;
@@ -789,6 +806,7 @@
list_clear(STM_PSEGMENT->modified_old_objects);
list_clear(STM_PSEGMENT->modified_old_objects_markers);
+ list_clear(STM_PSEGMENT->modified_old_hashtables);
}
static void _finish_transaction(enum stm_event_e event)
@@ -950,6 +968,7 @@
list_clear(pseg->modified_old_objects);
list_clear(pseg->modified_old_objects_markers);
+ list_clear(pseg->modified_old_hashtables);
}
static void abort_data_structures_from_segment_num(int segment_num)
diff --git a/c7/stm/core.h b/c7/stm/core.h
--- a/c7/stm/core.h
+++ b/c7/stm/core.h
@@ -95,6 +95,14 @@
struct list_s *modified_old_objects_markers;
uintptr_t modified_old_objects_markers_num_old;
+ /* This list contains all old hashtables that have entries that we
+ modified. Note that several transactions can all commit if
+ they have the same hashtable listed here. The point of this
+ list is only that if another segment does a global "read" of
+ the hashtable (stm_hashtable_list), then it conflicts with this
+ segment if it has got any change to the hashtable. */
+ struct list_s *modified_old_hashtables;
+
/* List of out-of-nursery objects that may contain pointers to
nursery objects. This is used to track the GC status: they are
all objects outside the nursery on which an stm_write() occurred
@@ -281,17 +289,13 @@
static stm_thread_local_t *abort_with_mutex_no_longjmp(void);
static void abort_data_structures_from_segment_num(int segment_num);
-static inline struct stm_read_marker_s *get_read_marker(char *base,
- object_t *obj) {
- return (struct stm_read_marker_s *)(base + (((uintptr_t)obj) >> 4));
-}
-
static inline bool was_read_remote(char *base, object_t *obj)
{
uint8_t other_transaction_read_version =
((struct stm_segment_info_s *)REAL_ADDRESS(base, STM_PSEGMENT))
->transaction_read_version;
- uint8_t rm = get_read_marker(base, obj)->rm;
+ uint8_t rm = ((struct stm_read_marker_s *)
+ (base + (((uintptr_t)obj) >> 4)))->rm;
assert(rm <= other_transaction_read_version);
return rm == other_transaction_read_version;
}
diff --git a/c7/stm/gcpage.c b/c7/stm/gcpage.c
--- a/c7/stm/gcpage.c
+++ b/c7/stm/gcpage.c
@@ -475,13 +475,26 @@
}
}
-static void clean_up_segment_lists(void)
-{
#pragma push_macro("STM_PSEGMENT")
#pragma push_macro("STM_SEGMENT")
#undef STM_PSEGMENT
#undef STM_SEGMENT
+static void remove_objects_that_die(struct list_s *lst)
+{
+ if (lst != NULL) {
+ uintptr_t n = list_count(lst);
+ while (n > 0) {
+ object_t *obj = (object_t *)list_item(lst, --n);
+ if (!mark_visited_test(obj)) {
+ list_set_item(lst, n, list_pop_item(lst));
+ }
+ }
+ }
+}
+
+static void clean_up_segment_lists(void)
+{
long i;
for (i = 1; i <= NB_SEGMENTS; i++) {
struct stm_priv_segment_info_s *pseg = get_priv_segment(i);
@@ -540,21 +553,14 @@
}));
list_clear(lst);
- /* Remove from 'large_overflow_objects' all objects that die */
- lst = pseg->large_overflow_objects;
- if (lst != NULL) {
- uintptr_t n = list_count(lst);
- while (n > 0) {
- object_t *obj = (object_t *)list_item(lst, --n);
- if (!mark_visited_test(obj)) {
- list_set_item(lst, n, list_pop_item(lst));
- }
- }
- }
+ /* Remove from 'large_overflow_objects' and 'modified_old_hashtables'
+ all objects that die */
+ remove_objects_that_die(pseg->large_overflow_objects);
+ remove_objects_that_die(pseg->modified_old_hashtables);
}
+}
#pragma pop_macro("STM_SEGMENT")
#pragma pop_macro("STM_PSEGMENT")
-}
static inline bool largemalloc_keep_object_at(char *data)
{
diff --git a/c7/stm/hashtable.c b/c7/stm/hashtable.c
--- a/c7/stm/hashtable.c
+++ b/c7/stm/hashtable.c
@@ -297,34 +297,12 @@
synchronization with other pieces of the code that may
change.
*/
-
- /* First fetch the read marker of 'hashtableobj' in all
- segments, before allocate_outside_nursery_large() which
- might trigger a GC. Synchronization guarantee: if
- stm_read(hobj) in stm_hashtable_list() has set the read
- marker, then it did synchronize with us here by
- acquiring and releasing this hashtable' lock. However,
- the interval of time between reading the readmarkers of
- hobj and copying them to the new entry object might be
- enough for the other threads to do anything, including
- a reset_transaction_read_version(), so that we might in
- theory write bogus read markers that are not valid any
- more. To prevent this, reset_transaction_read_version()
- acquires the privatization_lock too.
- */
- long j;
- uint8_t readmarkers[NB_SEGMENTS];
-
acquire_privatization_lock();
- for (j = 1; j <= NB_SEGMENTS; j++) {
- readmarkers[j - 1] = get_read_marker(get_segment_base(j),
- hashtableobj)->rm;
- }
-
char *p = allocate_outside_nursery_large(
sizeof(stm_hashtable_entry_t));
entry = (stm_hashtable_entry_t *)(p - stm_object_pages);
+ long j;
for (j = 0; j <= NB_SEGMENTS; j++) {
struct stm_hashtable_entry_s *e;
e = (struct stm_hashtable_entry_s *)
@@ -335,11 +313,6 @@
e->object = NULL;
}
hashtable->additions += 0x100;
-
- for (j = 1; j <= NB_SEGMENTS; j++) {
- get_read_marker(get_segment_base(j), (object_t *)entry)->rm =
- readmarkers[j - 1];
- }
release_privatization_lock();
}
write_fence(); /* make sure 'entry' is fully initialized here */
@@ -369,15 +342,44 @@
return e->object;
}
+void stm_hashtable_write_entry(object_t *hobj, stm_hashtable_entry_t *entry,
+ object_t *nvalue)
+{
+ if (stm_write((object_t *)entry)) {
+ uintptr_t i = list_count(STM_PSEGMENT->modified_old_objects);
+ if (i > 0 && list_item(STM_PSEGMENT->modified_old_objects, i - 1)
+ == (uintptr_t)entry) {
+ /* 'modified_old_hashtables' is always obtained by taking
+ a subset of 'modified_old_objects' which contains only
+ stm_hashtable_entry_t objects, and then replacing the
+ stm_hashtable_entry_t objects with the hobj they come
+ from. It's possible to have duplicates in
+ 'modified_old_hashtables'; here we only try a bit to
+ avoid them --- at least the list should never be longer
+ than 'modified_old_objects'. */
+ i = list_count(STM_PSEGMENT->modified_old_hashtables);
+ if (i > 0 && list_item(STM_PSEGMENT->modified_old_hashtables, i -
1)
+ == (uintptr_t)hobj) {
+ /* already added */
+ }
+ else {
+ LIST_APPEND(STM_PSEGMENT->modified_old_hashtables, hobj);
+ }
+ }
+ }
+ entry->object = nvalue;
+}
+
void stm_hashtable_write(object_t *hobj, stm_hashtable_t *hashtable,
uintptr_t key, object_t *nvalue,
stm_thread_local_t *tl)
{
STM_PUSH_ROOT(*tl, nvalue);
+ STM_PUSH_ROOT(*tl, hobj);
stm_hashtable_entry_t *e = stm_hashtable_lookup(hobj, hashtable, key);
- stm_write((object_t *)e);
+ STM_POP_ROOT(*tl, hobj);
STM_POP_ROOT(*tl, nvalue);
- e->object = nvalue;
+ stm_hashtable_write_entry(hobj, e, nvalue);
}
long stm_hashtable_length_upper_bound(stm_hashtable_t *hashtable)
@@ -401,28 +403,15 @@
long stm_hashtable_list(object_t *hobj, stm_hashtable_t *hashtable,
stm_hashtable_entry_t **results)
{
- stm_hashtable_table_t *table;
- intptr_t rc;
-
/* Set the read marker. It will be left as long as we're running
the same transaction.
*/
stm_read(hobj);
- /* Acquire and immediately release the lock. We don't actually
- need to do anything while we hold the lock, but the point is to
- wait until the lock is available, and to synchronize other
- threads with the stm_read() done above.
- */
- restart:
- table = VOLATILE_HASHTABLE(hashtable)->table;
- rc = VOLATILE_TABLE(table)->resize_counter;
- if (IS_EVEN(rc)) {
- spin_loop();
- goto restart;
- }
- if (!__sync_bool_compare_and_swap(&table->resize_counter, rc, rc))
- goto restart;
+ /* Get the table. No synchronization is needed: we may miss some
+ entries that are being added, but they would contain NULL in
+ this segment anyway. */
+ stm_hashtable_table_t *table = VOLATILE_HASHTABLE(hashtable)->table;
/* Read all entries, check which ones are not NULL, count them,
and optionally list them in 'results'.
diff --git a/c7/stm/setup.c b/c7/stm/setup.c
--- a/c7/stm/setup.c
+++ b/c7/stm/setup.c
@@ -122,6 +122,7 @@
pr->large_overflow_objects = NULL;
pr->modified_old_objects = list_create();
pr->modified_old_objects_markers = list_create();
+ pr->modified_old_hashtables = list_create();
pr->young_weakrefs = list_create();
pr->old_weakrefs = list_create();
pr->young_outside_nursery = tree_create();
@@ -166,6 +167,7 @@
assert(pr->large_overflow_objects == NULL);
list_free(pr->modified_old_objects);
list_free(pr->modified_old_objects_markers);
+ list_free(pr->modified_old_hashtables);
list_free(pr->young_weakrefs);
list_free(pr->old_weakrefs);
tree_free(pr->young_outside_nursery);
diff --git a/c7/stmgc.h b/c7/stmgc.h
--- a/c7/stmgc.h
+++ b/c7/stmgc.h
@@ -187,10 +187,13 @@
necessary to call it immediately after stm_allocate().
*/
__attribute__((always_inline))
-static inline void stm_write(object_t *obj)
+static inline int stm_write(object_t *obj)
{
- if (UNLIKELY((obj->stm_flags & _STM_GCFLAG_WRITE_BARRIER) != 0))
+ if (UNLIKELY((obj->stm_flags & _STM_GCFLAG_WRITE_BARRIER) != 0)) {
_stm_write_slowpath(obj);
+ return 1;
+ }
+ return 0;
}
/* The following is a GC-optimized barrier that works on the granularity
@@ -544,6 +547,8 @@
object_t *stm_hashtable_read(object_t *, stm_hashtable_t *, uintptr_t key);
void stm_hashtable_write(object_t *, stm_hashtable_t *, uintptr_t key,
object_t *nvalue, stm_thread_local_t *);
+void stm_hashtable_write_entry(object_t *hobj, stm_hashtable_entry_t *entry,
+ object_t *nvalue);
long stm_hashtable_length_upper_bound(stm_hashtable_t *);
long stm_hashtable_list(object_t *, stm_hashtable_t *,
stm_hashtable_entry_t **results);
diff --git a/c7/test/test_hashtable.py b/c7/test/test_hashtable.py
--- a/c7/test/test_hashtable.py
+++ b/c7/test/test_hashtable.py
@@ -284,6 +284,25 @@
htset(h, 19 ^ i, stm_allocate(32), tl0)
assert htlen(h) == 29
+ def test_len_conflicts_with_additions(self):
+ self.start_transaction()
+ h = self.allocate_hashtable()
+ self.push_root(h)
+ self.commit_transaction()
+ h = self.pop_root()
+ #
+ self.start_transaction()
+ assert htlen(h) == 0
+ #
+ self.switch(1)
+ self.start_transaction()
+ tl0 = self.tls[self.current_thread]
+ htset(h, 10, stm_allocate(32), tl0)
+ py.test.raises(Conflict, self.commit_transaction)
+ #
+ self.switch(0)
+ stm_major_collect() # to get rid of the hashtable object
+
class TestRandomHashtable(BaseTestHashtable):
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
