Author: Remi Meier <remi.me...@gmail.com> Branch: stmgc-c8 Changeset: r82527:f1e7aa419f98 Date: 2016-02-26 12:14 +0100 http://bitbucket.org/pypy/pypy/changeset/f1e7aa419f98/
Log: import stmgc 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 @@ -d31c9f671775 +8c9162341945 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 @@ -109,164 +109,6 @@ } -/* ############# signal handler ############# */ - -static void copy_bk_objs_in_page_from(int from_segnum, uintptr_t pagenum, - bool only_if_not_modified) -{ - /* looks at all bk copies of objects overlapping page 'pagenum' and - copies the part in 'pagenum' back to the current segment */ - dprintf(("copy_bk_objs_in_page_from(%d, %ld, %d)\n", - from_segnum, (long)pagenum, only_if_not_modified)); - - assert(modification_lock_check_rdlock(from_segnum)); - struct list_s *list = get_priv_segment(from_segnum)->modified_old_objects; - struct stm_undo_s *undo = (struct stm_undo_s *)list->items; - struct stm_undo_s *end = (struct stm_undo_s *)(list->items + list->count); - - import_objects(only_if_not_modified ? -2 : -1, - pagenum, undo, end); -} - -static void go_to_the_past(uintptr_t pagenum, - struct stm_commit_log_entry_s *from, - struct stm_commit_log_entry_s *to) -{ - assert(modification_lock_check_wrlock(STM_SEGMENT->segment_num)); - assert(from->rev_num >= to->rev_num); - /* walk BACKWARDS the commit log and update the page 'pagenum', - initially at revision 'from', until we reach the revision 'to'. */ - - /* XXXXXXX Recursive algo for now, fix this! */ - if (from != to) { - struct stm_commit_log_entry_s *cl = to->next; - go_to_the_past(pagenum, from, cl); - - struct stm_undo_s *undo = cl->written; - struct stm_undo_s *end = cl->written + cl->written_count; - - import_objects(-1, pagenum, undo, end); - } -} - - - -static void handle_segfault_in_page(uintptr_t pagenum) -{ - /* assumes page 'pagenum' is ACCESS_NONE, privatizes it, - and validates to newest revision */ - - dprintf(("handle_segfault_in_page(%lu), seg %d\n", pagenum, STM_SEGMENT->segment_num)); - - /* XXX: bad, but no deadlocks: */ - acquire_all_privatization_locks(); - - long i; - int my_segnum = STM_SEGMENT->segment_num; - - assert(get_page_status_in(my_segnum, pagenum) == PAGE_NO_ACCESS); - - /* find who has the most recent revision of our page */ - int copy_from_segnum = -1; - uint64_t most_recent_rev = 0; - for (i = 1; i < NB_SEGMENTS; i++) { - if (i == my_segnum) - continue; - - struct stm_commit_log_entry_s *log_entry; - log_entry = get_priv_segment(i)->last_commit_log_entry; - if (get_page_status_in(i, pagenum) != PAGE_NO_ACCESS - && (copy_from_segnum == -1 || log_entry->rev_num > most_recent_rev)) { - copy_from_segnum = i; - most_recent_rev = log_entry->rev_num; - } - } - OPT_ASSERT(copy_from_segnum != my_segnum); - - /* make our page write-ready */ - page_mark_accessible(my_segnum, pagenum); - - /* account for this page now: XXX */ - /* increment_total_allocated(4096); */ - - if (copy_from_segnum == -1) { - /* this page is only accessible in the sharing segment seg0 so far (new - allocation). We can thus simply mark it accessible here. */ - pagecopy(get_virtual_page(my_segnum, pagenum), - get_virtual_page(0, pagenum)); - release_all_privatization_locks(); - return; - } - - /* before copying anything, acquire modification locks from our and - the other segment */ - uint64_t to_lock = (1UL << copy_from_segnum); - acquire_modification_lock_set(to_lock, my_segnum); - pagecopy(get_virtual_page(my_segnum, pagenum), - get_virtual_page(copy_from_segnum, pagenum)); - - /* if there were modifications in the page, revert them. */ - copy_bk_objs_in_page_from(copy_from_segnum, pagenum, false); - - /* we need to go from 'src_version' to 'target_version'. This - might need a walk into the past. */ - struct stm_commit_log_entry_s *src_version, *target_version; - src_version = get_priv_segment(copy_from_segnum)->last_commit_log_entry; - target_version = STM_PSEGMENT->last_commit_log_entry; - - - dprintf(("handle_segfault_in_page: rev %lu to rev %lu\n", - src_version->rev_num, target_version->rev_num)); - /* adapt revision of page to our revision: - if our rev is higher than the page we copy from, everything - is fine as we never read/modified the page anyway - */ - if (src_version->rev_num > target_version->rev_num) - go_to_the_past(pagenum, src_version, target_version); - - release_modification_lock_set(to_lock, my_segnum); - release_all_privatization_locks(); -} - -static void _signal_handler(int sig, siginfo_t *siginfo, void *context) -{ - assert(_stm_segfault_expected > 0); - - int saved_errno = errno; - char *addr = siginfo->si_addr; - dprintf(("si_addr: %p\n", addr)); - if (addr == NULL || addr < stm_object_pages || - addr >= stm_object_pages+TOTAL_MEMORY) { - /* actual segfault, unrelated to stmgc */ - fprintf(stderr, "Segmentation fault: accessing %p\n", addr); - detect_shadowstack_overflow(addr); - abort(); - } - - int segnum = get_segment_of_linear_address(addr); - OPT_ASSERT(segnum != 0); - if (segnum != STM_SEGMENT->segment_num) { - fprintf(stderr, "Segmentation fault: accessing %p (seg %d) from" - " seg %d\n", addr, segnum, STM_SEGMENT->segment_num); - abort(); - } - dprintf(("-> segment: %d\n", segnum)); - - char *seg_base = STM_SEGMENT->segment_base; - uintptr_t pagenum = ((char*)addr - seg_base) / 4096UL; - if (pagenum < END_NURSERY_PAGE) { - fprintf(stderr, "Segmentation fault: accessing %p (seg %d " - "page %lu)\n", addr, segnum, pagenum); - abort(); - } - - DEBUG_EXPECT_SEGFAULT(false); - handle_segfault_in_page(pagenum); - DEBUG_EXPECT_SEGFAULT(true); - - errno = saved_errno; - /* now return and retry */ -} /* ############# commit log ############# */ diff --git a/rpython/translator/stm/src_stm/stm/core.h b/rpython/translator/stm/src_stm/stm/core.h --- a/rpython/translator/stm/src_stm/stm/core.h +++ b/rpython/translator/stm/src_stm/stm/core.h @@ -303,6 +303,14 @@ static bool _stm_validate(void); static void _core_commit_transaction(bool external); +static void import_objects( + int from_segnum, /* or -1: from undo->backup, + or -2: from undo->backup if not modified */ + uintptr_t pagenum, /* or -1: "all accessible" */ + struct stm_undo_s *undo, + struct stm_undo_s *end); + + static inline bool was_read_remote(char *base, object_t *obj) { uint8_t other_transaction_read_version = 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 @@ -78,6 +78,7 @@ stm_hashtable_table_t *table; stm_hashtable_table_t initial_table; uint64_t additions; + uint64_t pickitem_index; }; @@ -490,6 +491,90 @@ return nresult; } +stm_hashtable_entry_t *stm_hashtable_pickitem(object_t *hobj, + stm_hashtable_t *hashtable) +{ + /* We use hashtable->pickitem_index as a shared index counter (not + initialized, any initial garbage is fine). The goal is + two-folds: + + - This is used to implement popitem(). Like CPython and PyPy's + non-STM dict implementations, the goal is that repeated calls + to pickitem() maintains a roughly O(1) time per call while + returning different items (in the case of popitem(), the + returned items are immediately deleted). + + - Additionally, with STM, if several threads all call + pickitem(), this should give the best effort to distribute + different items to different threads and thus minimize + conflicts. (At least that's the theory; it should be tested + in practice.) + */ + restart:; + uint64_t startindex = VOLATILE_HASHTABLE(hashtable)->pickitem_index; + + /* 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; + + /* Find the first entry with a non-NULL object, starting at + 'index'. */ + uintptr_t mask = table->mask; + uintptr_t count; + stm_hashtable_entry_t *entry; + + for (count = 0; count <= mask; ) { + entry = VOLATILE_TABLE(table)->items[(startindex + count) & mask]; + count++; + if (entry != NULL && entry->object != NULL) { + /* + Found the next entry. Update pickitem_index now. If + it was already changed under our feet, we assume that + it is because another thread just did pickitem() too + and is likely to have got the very same entry. In that + case we start again from scratch to look for the + following entry. + */ + if (!__sync_bool_compare_and_swap(&hashtable->pickitem_index, + startindex, + startindex + count)) + goto restart; + + /* Here we mark the entry as as read and return it. + + Note a difference with notably stm_hashtable_list(): we + only call stm_read() after we checked that + entry->object is not NULL. If we find NULL, we don't + mark the entry as read from this thread at all in this + step---this is fine, as we can return a random + different entry here. + */ + stm_read((object_t *)entry); + return entry; + } + } + + /* Didn't find any entry. We have to be sure that the dictionary + is empty now, in the sense that returning NULL must guarantee + conflicts with a different thread adding items. This is done + by marking both the dict and all entries' read marker. */ + stm_read(hobj); + + /* Reload the table after setting the read marker */ + uintptr_t i; + table = VOLATILE_HASHTABLE(hashtable)->table; + mask = table->mask; + for (i = 0; i <= mask; i++) { + entry = VOLATILE_TABLE(table)->items[i]; + if (entry != NULL) { + stm_read((object_t *)entry); + assert(entry->object == NULL); + } + } + return NULL; +} + static void _stm_compact_hashtable(struct object_s *hobj, stm_hashtable_t *hashtable) { diff --git a/rpython/translator/stm/src_stm/stm/setup.c b/rpython/translator/stm/src_stm/stm/setup.c --- a/rpython/translator/stm/src_stm/stm/setup.c +++ b/rpython/translator/stm/src_stm/stm/setup.c @@ -39,20 +39,6 @@ } -static void setup_signal_handler(void) -{ - struct sigaction act; - memset(&act, 0, sizeof(act)); - - act.sa_sigaction = &_signal_handler; - /* The SA_SIGINFO flag tells sigaction() to use the sa_sigaction field, not sa_handler. */ - act.sa_flags = SA_SIGINFO | SA_NODEFER; - - if (sigaction(SIGSEGV, &act, NULL) < 0) { - perror ("sigaction"); - abort(); - } -} void stm_setup(void) { @@ -301,13 +287,15 @@ if (addr == NULL) return; stm_thread_local_t *tl = stm_all_thread_locals; - while (tl != NULL) { + if (tl == NULL) + return; + do { char *trap = _shadowstack_trap_page(tl->shadowstack_base); if (trap <= addr && addr <= trap + 4095) { fprintf(stderr, "This is caused by a stack overflow.\n" - "Sorry, proper RuntimeError support is not implemented yet.\n"); + "Sorry, proper RuntimeError support is not implemented yet.\n"); return; } tl = tl->next; - } + } while (tl != stm_all_thread_locals); } diff --git a/rpython/translator/stm/src_stm/stm/signal_handler.c b/rpython/translator/stm/src_stm/stm/signal_handler.c new file mode 100644 --- /dev/null +++ b/rpython/translator/stm/src_stm/stm/signal_handler.c @@ -0,0 +1,178 @@ +/* Imported by rpython/translator/stm/import_stmgc.py */ +#ifndef _STM_CORE_H_ +# error "must be compiled via stmgc.c" +#endif + + +static void setup_signal_handler(void) +{ + struct sigaction act; + memset(&act, 0, sizeof(act)); + + act.sa_sigaction = &_signal_handler; + /* The SA_SIGINFO flag tells sigaction() to use the sa_sigaction field, not sa_handler. */ + act.sa_flags = SA_SIGINFO | SA_NODEFER; + + if (sigaction(SIGSEGV, &act, NULL) < 0) { + perror ("sigaction"); + abort(); + } +} + + +static void copy_bk_objs_in_page_from(int from_segnum, uintptr_t pagenum, + bool only_if_not_modified) +{ + /* looks at all bk copies of objects overlapping page 'pagenum' and + copies the part in 'pagenum' back to the current segment */ + dprintf(("copy_bk_objs_in_page_from(%d, %ld, %d)\n", + from_segnum, (long)pagenum, only_if_not_modified)); + + assert(modification_lock_check_rdlock(from_segnum)); + struct list_s *list = get_priv_segment(from_segnum)->modified_old_objects; + struct stm_undo_s *undo = (struct stm_undo_s *)list->items; + struct stm_undo_s *end = (struct stm_undo_s *)(list->items + list->count); + + import_objects(only_if_not_modified ? -2 : -1, + pagenum, undo, end); +} + +static void go_to_the_past(uintptr_t pagenum, + struct stm_commit_log_entry_s *from, + struct stm_commit_log_entry_s *to) +{ + assert(modification_lock_check_wrlock(STM_SEGMENT->segment_num)); + assert(from->rev_num >= to->rev_num); + /* walk BACKWARDS the commit log and update the page 'pagenum', + initially at revision 'from', until we reach the revision 'to'. */ + + /* XXXXXXX Recursive algo for now, fix this! */ + if (from != to) { + struct stm_commit_log_entry_s *cl = to->next; + go_to_the_past(pagenum, from, cl); + + struct stm_undo_s *undo = cl->written; + struct stm_undo_s *end = cl->written + cl->written_count; + + import_objects(-1, pagenum, undo, end); + } +} + + + +static void handle_segfault_in_page(uintptr_t pagenum) +{ + /* assumes page 'pagenum' is ACCESS_NONE, privatizes it, + and validates to newest revision */ + + dprintf(("handle_segfault_in_page(%lu), seg %d\n", pagenum, STM_SEGMENT->segment_num)); + + /* XXX: bad, but no deadlocks: */ + acquire_all_privatization_locks(); + + long i; + int my_segnum = STM_SEGMENT->segment_num; + + assert(get_page_status_in(my_segnum, pagenum) == PAGE_NO_ACCESS); + + /* find who has the most recent revision of our page */ + int copy_from_segnum = -1; + uint64_t most_recent_rev = 0; + for (i = 1; i < NB_SEGMENTS; i++) { + if (i == my_segnum) + continue; + + struct stm_commit_log_entry_s *log_entry; + log_entry = get_priv_segment(i)->last_commit_log_entry; + if (get_page_status_in(i, pagenum) != PAGE_NO_ACCESS + && (copy_from_segnum == -1 || log_entry->rev_num > most_recent_rev)) { + copy_from_segnum = i; + most_recent_rev = log_entry->rev_num; + } + } + OPT_ASSERT(copy_from_segnum != my_segnum); + + /* make our page write-ready */ + page_mark_accessible(my_segnum, pagenum); + + /* account for this page now: XXX */ + /* increment_total_allocated(4096); */ + + if (copy_from_segnum == -1) { + /* this page is only accessible in the sharing segment seg0 so far (new + allocation). We can thus simply mark it accessible here. */ + pagecopy(get_virtual_page(my_segnum, pagenum), + get_virtual_page(0, pagenum)); + release_all_privatization_locks(); + return; + } + + /* before copying anything, acquire modification locks from our and + the other segment */ + uint64_t to_lock = (1UL << copy_from_segnum); + acquire_modification_lock_set(to_lock, my_segnum); + pagecopy(get_virtual_page(my_segnum, pagenum), + get_virtual_page(copy_from_segnum, pagenum)); + + /* if there were modifications in the page, revert them. */ + copy_bk_objs_in_page_from(copy_from_segnum, pagenum, false); + + /* we need to go from 'src_version' to 'target_version'. This + might need a walk into the past. */ + struct stm_commit_log_entry_s *src_version, *target_version; + src_version = get_priv_segment(copy_from_segnum)->last_commit_log_entry; + target_version = STM_PSEGMENT->last_commit_log_entry; + + + dprintf(("handle_segfault_in_page: rev %lu to rev %lu\n", + src_version->rev_num, target_version->rev_num)); + /* adapt revision of page to our revision: + if our rev is higher than the page we copy from, everything + is fine as we never read/modified the page anyway + */ + if (src_version->rev_num > target_version->rev_num) + go_to_the_past(pagenum, src_version, target_version); + + release_modification_lock_set(to_lock, my_segnum); + release_all_privatization_locks(); +} + +static void _signal_handler(int sig, siginfo_t *siginfo, void *context) +{ + assert(_stm_segfault_expected > 0); + + int saved_errno = errno; + char *addr = siginfo->si_addr; + dprintf(("si_addr: %p\n", addr)); + if (addr == NULL || addr < stm_object_pages || + addr >= stm_object_pages+TOTAL_MEMORY) { + /* actual segfault, unrelated to stmgc */ + fprintf(stderr, "Segmentation fault: accessing %p\n", addr); + detect_shadowstack_overflow(addr); + abort(); + } + + int segnum = get_segment_of_linear_address(addr); + OPT_ASSERT(segnum != 0); + if (segnum != STM_SEGMENT->segment_num) { + fprintf(stderr, "Segmentation fault: accessing %p (seg %d) from" + " seg %d\n", addr, segnum, STM_SEGMENT->segment_num); + abort(); + } + dprintf(("-> segment: %d\n", segnum)); + + char *seg_base = STM_SEGMENT->segment_base; + uintptr_t pagenum = ((char*)addr - seg_base) / 4096UL; + if (pagenum < END_NURSERY_PAGE) { + fprintf(stderr, "Segmentation fault: accessing %p (seg %d " + "page %lu)\n", addr, segnum, pagenum); + abort(); + } + + DEBUG_EXPECT_SEGFAULT(false); + handle_segfault_in_page(pagenum); + DEBUG_EXPECT_SEGFAULT(true); + + errno = saved_errno; + /* now return and retry */ +} diff --git a/rpython/translator/stm/src_stm/stm/signal_handler.h b/rpython/translator/stm/src_stm/stm/signal_handler.h new file mode 100644 --- /dev/null +++ b/rpython/translator/stm/src_stm/stm/signal_handler.h @@ -0,0 +1,8 @@ +/* Imported by rpython/translator/stm/import_stmgc.py */ +static void copy_bk_objs_in_page_from(int from_segnum, uintptr_t pagenum, + bool only_if_not_modified); + +static void handle_segfault_in_page(uintptr_t pagenum); + + +static void setup_signal_handler(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 @@ -4,6 +4,7 @@ #include "stm/atomic.h" #include "stm/list.h" #include "stm/smallmalloc.h" +#include "stm/signal_handler.h" #include "stm/core.h" #include "stm/pagecopy.h" #include "stm/pages.h" @@ -36,6 +37,7 @@ #include "stm/forksupport.c" #include "stm/setup.c" #include "stm/hash_id.c" +#include "stm/signal_handler.c" #include "stm/core.c" #include "stm/extra.c" #include "stm/fprintcolor.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 @@ -749,6 +749,7 @@ 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 *); +stm_hashtable_entry_t *stm_hashtable_pickitem(object_t *, stm_hashtable_t *); /* WARNING: stm_hashtable_list does not do a stm_write() on the 'results' argument. 'results' may point inside an object. So if 'results' may be _______________________________________________ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit