Author: Armin Rigo <ar...@tunes.org> Branch: stmgc-c8-dictiter Changeset: r80560:deb2b12c5415 Date: 2015-11-06 06:37 +0000 http://bitbucket.org/pypy/pypy/changeset/deb2b12c5415/
Log: import stmgc/72facb6e4533 diff --git a/rpython/translator/stm/src_stm/revision b/rpython/translator/stm/src_stm/revision --- a/rpython/translator/stm/src_stm/revision +++ b/rpython/translator/stm/src_stm/revision @@ -1,1 +1,1 @@ -41227d7659ac +72facb6e4533 diff --git a/rpython/translator/stm/src_stm/stm/core.c b/rpython/translator/stm/src_stm/stm/core.c --- a/rpython/translator/stm/src_stm/stm/core.c +++ b/rpython/translator/stm/src_stm/stm/core.c @@ -1374,6 +1374,8 @@ from its segment. Better do it as soon as possible, because other threads might be spin-looping, waiting for the -1 to disappear. */ + /* but first, emit commit-event of this thread: */ + timing_event(STM_SEGMENT->running_thread, STM_TRANSACTION_COMMIT); STM_SEGMENT->running_thread = NULL; write_fence(); assert(_stm_detached_inevitable_from_thread == -1); diff --git a/rpython/translator/stm/src_stm/stm/detach.c b/rpython/translator/stm/src_stm/stm/detach.c --- a/rpython/translator/stm/src_stm/stm/detach.c +++ b/rpython/translator/stm/src_stm/stm/detach.c @@ -127,6 +127,7 @@ // XXX: not sure if the next line is a good idea tl->last_associated_segment_num = remote_seg_num; ensure_gs_register(remote_seg_num); + timing_event(STM_SEGMENT->running_thread, STM_TRANSACTION_REATTACH); commit_external_inevitable_transaction(); } dprintf(("reattach_transaction: start a new transaction\n")); @@ -185,6 +186,7 @@ assert(segnum > 0); ensure_gs_register(segnum); + timing_event(STM_SEGMENT->running_thread, STM_TRANSACTION_REATTACH); commit_external_inevitable_transaction(); ensure_gs_register(mysegnum); } diff --git a/rpython/translator/stm/src_stm/stm/finalizer.c b/rpython/translator/stm/src_stm/stm/finalizer.c --- a/rpython/translator/stm/src_stm/stm/finalizer.c +++ b/rpython/translator/stm/src_stm/stm/finalizer.c @@ -501,7 +501,17 @@ /* XXX: become inevitable, bc. otherwise, we would need to keep around the original g_finalizers.run_finalizers to restore it in case of an abort. */ - _stm_become_inevitable("finalizer-Tx"); + _stm_become_inevitable(MSG_INEV_DONT_SLEEP); + /* did it work? */ + if (STM_PSEGMENT->transaction_state != TS_INEVITABLE) { /* no */ + /* avoid blocking here, waiting for another INEV transaction. + If we did that, application code could not proceed (start the + next transaction) and it will not be obvious from the profile + why we were WAITing. */ + _stm_commit_transaction(); + stm_rewind_jmp_leaveframe(tl, &rjbuf); + return; + } while (__sync_lock_test_and_set(&g_finalizers.lock, 1) != 0) { /* somebody is adding more finalizers (_commit_finalizer()) */ diff --git a/rpython/translator/stm/src_stm/stm/gcpage.c b/rpython/translator/stm/src_stm/stm/gcpage.c --- a/rpython/translator/stm/src_stm/stm/gcpage.c +++ b/rpython/translator/stm/src_stm/stm/gcpage.c @@ -224,6 +224,9 @@ version and thus don't need tracing. */ static struct list_s *marked_objects_to_trace; +/* a list of hobj/hashtable pairs for all hashtables seen */ +static struct list_s *all_hashtables_seen = NULL; + /* we use the sharing seg0's pages for the GCFLAG_VISITED flag */ static inline struct object_s *mark_loc(object_t *obj) @@ -301,8 +304,6 @@ } -#define TRACE_FOR_MAJOR_COLLECTION (&mark_record_trace) - static void mark_and_trace( object_t *obj, char *segment_base, /* to trace obj in */ @@ -791,6 +792,7 @@ /* marking */ LIST_CREATE(marked_objects_to_trace); + LIST_CREATE(all_hashtables_seen); mark_visit_from_modified_objects(); mark_visit_from_markers(); mark_visit_from_roots(); @@ -815,6 +817,10 @@ sweep_large_objects(); sweep_small_objects(); + /* hashtables */ + stm_compact_hashtables(); + LIST_FREE(all_hashtables_seen); + dprintf((" | used after collection: %ld\n", (long)pages_ctl.total_allocated)); dprintf((" `----------------------------------------------\n")); diff --git a/rpython/translator/stm/src_stm/stm/hashtable.c b/rpython/translator/stm/src_stm/stm/hashtable.c --- a/rpython/translator/stm/src_stm/stm/hashtable.c +++ b/rpython/translator/stm/src_stm/stm/hashtable.c @@ -49,8 +49,12 @@ #define PERTURB_SHIFT 5 #define RESIZING_LOCK 0 -typedef struct { - uintptr_t mask; +#define TRACE_FLAG_OFF 0 +#define TRACE_FLAG_ONCE 1 +#define TRACE_FLAG_KEEPALIVE 2 + +struct stm_hashtable_table_s { + uintptr_t mask; /* 'mask' is always immutable. */ /* 'resize_counter' start at an odd value, and is decremented (by 6) for every new item put in 'items'. When it crosses 0, we @@ -63,8 +67,10 @@ */ uintptr_t resize_counter; + uint8_t trace_flag; + stm_hashtable_entry_t *items[INITIAL_HASHTABLE_SIZE]; -} stm_hashtable_table_t; +}; #define IS_EVEN(p) (((p) & 1) == 0) @@ -79,6 +85,7 @@ { table->mask = itemcount - 1; table->resize_counter = itemcount * 4 + 1; + table->trace_flag = TRACE_FLAG_OFF; memset(table->items, 0, itemcount * sizeof(stm_hashtable_entry_t *)); } @@ -162,6 +169,7 @@ assert(biggertable); // XXX stm_hashtable_table_t *table = hashtable->table; + table->trace_flag = TRACE_FLAG_ONCE; table->resize_counter = (uintptr_t)biggertable; /* ^^^ this unlocks the table by writing a non-zero value to table->resize_counter, but the new value is a pointer to the @@ -485,6 +493,41 @@ static void _stm_compact_hashtable(struct object_s *hobj, stm_hashtable_t *hashtable) { + /* Walk the chained list that starts at 'hashtable->initial_table' + and follows the 'resize_counter' fields. Remove all tables + except (1) the initial one, (2) the most recent one, and (3) + the ones on which stm_hashtable_iter_tracefn() was called. + */ + stm_hashtable_table_t *most_recent_table = hashtable->table; + assert(!IS_EVEN(most_recent_table->resize_counter)); + /* set the "don't free me" flag on the most recent table */ + most_recent_table->trace_flag = TRACE_FLAG_KEEPALIVE; + + stm_hashtable_table_t *known_alive = &hashtable->initial_table; + known_alive->trace_flag = TRACE_FLAG_OFF; + /* a KEEPALIVE flag is ignored on the initial table: it is never + individually freed anyway */ + + while (known_alive != most_recent_table) { + uintptr_t rc = known_alive->resize_counter; + assert(IS_EVEN(rc)); + assert(rc != RESIZING_LOCK); + + stm_hashtable_table_t *next_table = (stm_hashtable_table_t *)rc; + if (next_table->trace_flag != TRACE_FLAG_KEEPALIVE) { + /* free this next table and relink the chained list to skip it */ + assert(IS_EVEN(next_table->resize_counter)); + known_alive->resize_counter = next_table->resize_counter; + free(next_table); + } + else { + /* this next table is kept alive */ + known_alive = next_table; + known_alive->trace_flag = TRACE_FLAG_OFF; + } + } + /* done the first part */ + stm_hashtable_table_t *table = hashtable->table; uintptr_t rc = table->resize_counter; assert(!IS_EVEN(rc)); @@ -515,35 +558,24 @@ dprintf(("compact with %ld items:\n", num_entries_times_6 / 6)); _stm_rehash_hashtable(hashtable, count, segnum); } +} - table = hashtable->table; - assert(!IS_EVEN(table->resize_counter)); - - if (table != &hashtable->initial_table) { - uintptr_t rc = hashtable->initial_table.resize_counter; - while (1) { - assert(IS_EVEN(rc)); - assert(rc != RESIZING_LOCK); - - stm_hashtable_table_t *old_table = (stm_hashtable_table_t *)rc; - if (old_table == table) - break; - rc = old_table->resize_counter; - free(old_table); - } - hashtable->initial_table.resize_counter = (uintptr_t)table; - assert(IS_EVEN(hashtable->initial_table.resize_counter)); +static void stm_compact_hashtables(void) +{ + uintptr_t i = all_hashtables_seen->count; + while (i > 0) { + i -= 2; + _stm_compact_hashtable( + (struct object_s *)all_hashtables_seen->items[i], + (stm_hashtable_t *)all_hashtables_seen->items[i + 1]); } } -void stm_hashtable_tracefn(struct object_s *hobj, stm_hashtable_t *hashtable, - void trace(object_t **)) +static void _hashtable_tracefn(stm_hashtable_table_t *table, + void trace(object_t **)) { - if (trace == TRACE_FOR_MAJOR_COLLECTION) - _stm_compact_hashtable(hobj, hashtable); - - stm_hashtable_table_t *table; - table = VOLATILE_HASHTABLE(hashtable)->table; + if (table->trace_flag == TRACE_FLAG_ONCE) + table->trace_flag = TRACE_FLAG_OFF; uintptr_t j, mask = table->mask; for (j = 0; j <= mask; j++) { @@ -554,3 +586,105 @@ } } } + +void stm_hashtable_tracefn(struct object_s *hobj, stm_hashtable_t *hashtable, + void trace(object_t **)) +{ + if (all_hashtables_seen != NULL) + all_hashtables_seen = list_append2(all_hashtables_seen, + (uintptr_t)hobj, + (uintptr_t)hashtable); + + _hashtable_tracefn(VOLATILE_HASHTABLE(hashtable)->table, trace); +} + + +/* Hashtable iterators */ + +/* TRACE_FLAG_ONCE: the table must be traced once if it supports an iterator + TRACE_FLAG_OFF: the table is the most recent table, or has already been + traced once + TRACE_FLAG_KEEPALIVE: during major collection only: mark tables that + must be kept alive because there are iterators +*/ + +struct stm_hashtable_table_s *stm_hashtable_iter(stm_hashtable_t *hashtable) +{ + /* 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. */ + return VOLATILE_HASHTABLE(hashtable)->table; +} + +stm_hashtable_entry_t ** +stm_hashtable_iter_next(object_t *hobj, stm_hashtable_table_t *table, + stm_hashtable_entry_t **previous) +{ + /* Set the read marker on hobj for every item, in case we have + transaction breaks in-between. + */ + stm_read(hobj); + + /* Get the bounds of the part of the 'stm_hashtable_entry_t *' array + that we have to check */ + stm_hashtable_entry_t **pp, **last; + if (previous == NULL) + pp = table->items; + else + pp = previous + 1; + last = table->items + table->mask; + + /* Find the first non-null entry */ + stm_hashtable_entry_t *entry; + + while (pp <= last) { + entry = *(stm_hashtable_entry_t *volatile *)pp; + if (entry != NULL) { + stm_read((object_t *)entry); + if (entry->object != NULL) { + //fprintf(stderr, "stm_hashtable_iter_next(%p, %p, %p) = %p\n", + // hobj, table, previous, pp); + return pp; + } + } + ++pp; + } + //fprintf(stderr, "stm_hashtable_iter_next(%p, %p, %p) = %p\n", + // hobj, table, previous, NULL); + return NULL; +} + +void stm_hashtable_iter_tracefn(stm_hashtable_table_t *table, + void trace(object_t **)) +{ + if (all_hashtables_seen == NULL) { /* for minor collections */ + + /* During minor collection, tracing the table is only required + the first time: if it contains young objects, they must be + kept alive and have their address updated. We use + TRACE_FLAG_ONCE to know that. We don't need to do it if + our 'table' is the latest version, because in that case it + will be done by stm_hashtable_tracefn(). That's why + TRACE_FLAG_ONCE is only set when a more recent table is + attached. + + It is only needed once: non-latest-version tables are + immutable. We mark once all the entries as old, and + then these now-old objects stay alive until the next + major collection. + + Checking the flag can be done without synchronization: it + never wrong to call _hashtable_tracefn() too much, and the + only case where it *has to* be called occurs if the + hashtable object is still young (and not seen by other + threads). + */ + if (table->trace_flag == TRACE_FLAG_ONCE) + _hashtable_tracefn(table, trace); + } + else { /* for major collections */ + + /* Set this flag for _stm_compact_hashtable() */ + table->trace_flag = TRACE_FLAG_KEEPALIVE; + } +} diff --git a/rpython/translator/stm/src_stm/stm/hashtable.h b/rpython/translator/stm/src_stm/stm/hashtable.h new file mode 100644 --- /dev/null +++ b/rpython/translator/stm/src_stm/stm/hashtable.h @@ -0,0 +1,2 @@ +/* Imported by rpython/translator/stm/import_stmgc.py */ +static void stm_compact_hashtables(void); diff --git a/rpython/translator/stm/src_stm/stmgc.c b/rpython/translator/stm/src_stm/stmgc.c --- a/rpython/translator/stm/src_stm/stmgc.c +++ b/rpython/translator/stm/src_stm/stmgc.c @@ -20,6 +20,7 @@ #include "stm/finalizer.h" #include "stm/locks.h" #include "stm/detach.h" +#include "stm/hashtable.h" #include "stm/queue.h" #include "stm/misc.c" #include "stm/list.c" diff --git a/rpython/translator/stm/src_stm/stmgc.h b/rpython/translator/stm/src_stm/stmgc.h --- a/rpython/translator/stm/src_stm/stmgc.h +++ b/rpython/translator/stm/src_stm/stmgc.h @@ -100,6 +100,8 @@ #define _stm_detach_inevitable_transaction(tl) do { \ write_fence(); \ assert(_stm_detached_inevitable_from_thread == 0); \ + if (stmcb_timing_event != NULL && tl->self_or_0_if_atomic != 0) \ + {stmcb_timing_event(tl, STM_TRANSACTION_DETACH, NULL);} \ _stm_detached_inevitable_from_thread = tl->self_or_0_if_atomic; \ } while (0) void _stm_reattach_transaction(intptr_t); @@ -416,69 +418,6 @@ #endif -/* Entering and leaving a "transactional code zone": a (typically very - large) section in the code where we are running a transaction. - This is the STM equivalent to "acquire the GIL" and "release the - GIL", respectively. stm_read(), stm_write(), stm_allocate(), and - other functions should only be called from within a transaction. - - Note that transactions, in the STM sense, cover _at least_ one - transactional code zone. They may be longer; for example, if one - thread does a lot of stm_enter_transactional_zone() + - stm_become_inevitable() + stm_leave_transactional_zone(), as is - typical in a thread that does a lot of C function calls, then we - get only a few bigger inevitable transactions that cover the many - short transactional zones. This is done by having - stm_leave_transactional_zone() turn the current transaction - inevitable and detach it from the running thread (if there is no - other inevitable transaction running so far). Then - stm_enter_transactional_zone() will try to reattach to it. This is - far more efficient than constantly starting and committing - transactions. - - stm_enter_transactional_zone() and stm_leave_transactional_zone() - preserve the value of errno. -*/ -#ifdef STM_DEBUGPRINT -#include <stdio.h> -#endif -static inline void stm_enter_transactional_zone(stm_thread_local_t *tl) { - intptr_t self = tl->self_or_0_if_atomic; - if (__sync_bool_compare_and_swap(&_stm_detached_inevitable_from_thread, - self, 0)) { -#ifdef STM_DEBUGPRINT - fprintf(stderr, "stm_enter_transactional_zone fast path\n"); -#endif - } - else { - _stm_reattach_transaction(self); - /* _stm_detached_inevitable_from_thread should be 0 here, but - it can already have been changed from a parallel thread - (assuming we're not inevitable ourselves) */ - } -} -static inline void stm_leave_transactional_zone(stm_thread_local_t *tl) { - assert(STM_SEGMENT->running_thread == tl); - if (stm_is_inevitable(tl)) { -#ifdef STM_DEBUGPRINT - fprintf(stderr, "stm_leave_transactional_zone fast path\n"); -#endif - _stm_detach_inevitable_transaction(tl); - } - else { - _stm_leave_noninevitable_transactional_zone(); - } -} - -/* stm_force_transaction_break() is in theory equivalent to - stm_leave_transactional_zone() immediately followed by - stm_enter_transactional_zone(); however, it is supposed to be - called in CPU-heavy threads that had a transaction run for a while, - and so it *always* forces a commit and starts the next transaction. - The new transaction is never inevitable. See also - stm_should_break_transaction(). */ -void stm_force_transaction_break(stm_thread_local_t *tl); - /* Abort the currently running transaction. This function never returns: it jumps back to the start of the transaction (which must not be inevitable). */ @@ -596,6 +535,10 @@ STM_TRANSACTION_COMMIT, STM_TRANSACTION_ABORT, + /* DETACH/REATTACH is used for leaving/reentering the transactional */ + STM_TRANSACTION_DETACH, + STM_TRANSACTION_REATTACH, + /* inevitable contention: all threads that try to become inevitable have a STM_BECOME_INEVITABLE event with a position marker. Then, if it waits it gets a STM_WAIT_OTHER_INEVITABLE. It is possible @@ -688,6 +631,75 @@ } while (0) + +/* Entering and leaving a "transactional code zone": a (typically very + large) section in the code where we are running a transaction. + This is the STM equivalent to "acquire the GIL" and "release the + GIL", respectively. stm_read(), stm_write(), stm_allocate(), and + other functions should only be called from within a transaction. + + Note that transactions, in the STM sense, cover _at least_ one + transactional code zone. They may be longer; for example, if one + thread does a lot of stm_enter_transactional_zone() + + stm_become_inevitable() + stm_leave_transactional_zone(), as is + typical in a thread that does a lot of C function calls, then we + get only a few bigger inevitable transactions that cover the many + short transactional zones. This is done by having + stm_leave_transactional_zone() turn the current transaction + inevitable and detach it from the running thread (if there is no + other inevitable transaction running so far). Then + stm_enter_transactional_zone() will try to reattach to it. This is + far more efficient than constantly starting and committing + transactions. + + stm_enter_transactional_zone() and stm_leave_transactional_zone() + preserve the value of errno. +*/ +#ifdef STM_DEBUGPRINT +#include <stdio.h> +#endif +static inline void stm_enter_transactional_zone(stm_thread_local_t *tl) { + intptr_t self = tl->self_or_0_if_atomic; + if (__sync_bool_compare_and_swap(&_stm_detached_inevitable_from_thread, + self, 0)) { + if (self != 0 && stmcb_timing_event != NULL) { + /* for atomic transactions, we don't emit DETACH/REATTACH */ + stmcb_timing_event(tl, STM_TRANSACTION_REATTACH, NULL); + } +#ifdef STM_DEBUGPRINT + fprintf(stderr, "stm_enter_transactional_zone fast path\n"); +#endif + } + else { + _stm_reattach_transaction(self); + /* _stm_detached_inevitable_from_thread should be 0 here, but + it can already have been changed from a parallel thread + (assuming we're not inevitable ourselves) */ + } +} +static inline void stm_leave_transactional_zone(stm_thread_local_t *tl) { + assert(STM_SEGMENT->running_thread == tl); + if (stm_is_inevitable(tl)) { +#ifdef STM_DEBUGPRINT + fprintf(stderr, "stm_leave_transactional_zone fast path\n"); +#endif + _stm_detach_inevitable_transaction(tl); + } + else { + _stm_leave_noninevitable_transactional_zone(); + } +} + +/* stm_force_transaction_break() is in theory equivalent to + stm_leave_transactional_zone() immediately followed by + stm_enter_transactional_zone(); however, it is supposed to be + called in CPU-heavy threads that had a transaction run for a while, + and so it *always* forces a commit and starts the next transaction. + The new transaction is never inevitable. See also + stm_should_break_transaction(). */ +void stm_force_transaction_break(stm_thread_local_t *tl); + + /* Support for light finalizers. This is a simple version of finalizers that guarantees not to do anything fancy, like not resurrecting objects. */ @@ -755,6 +767,21 @@ object_t *object; }; +/* Hashtable iterators. You get a raw 'table' pointer when you make + an iterator, which you pass to stm_hashtable_iter_next(). This may + or may not return items added after stm_hashtable_iter() was + called; there is no logic so far to detect changes (unlike Python's + RuntimeError). When the GC traces, you must keep the table pointer + alive with stm_hashtable_iter_tracefn(). The original hashtable + object must also be kept alive. */ +typedef struct stm_hashtable_table_s stm_hashtable_table_t; +stm_hashtable_table_t *stm_hashtable_iter(stm_hashtable_t *); +stm_hashtable_entry_t ** +stm_hashtable_iter_next(object_t *hobj, stm_hashtable_table_t *table, + stm_hashtable_entry_t **previous); +void stm_hashtable_iter_tracefn(stm_hashtable_table_t *table, + void trace(object_t **)); + /* Queues. The items you put() and get() back are in random order. Like hashtables, the type 'stm_queue_t' is not an object type at _______________________________________________ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit