Author: Remi Meier <remi.me...@inf.ethz.ch> Branch: Changeset: r1350:8a58897dff57 Date: 2014-09-04 13:25 +0200 http://bitbucket.org/pypy/stmgc/changeset/8a58897dff57/
Log: make modified_old_objs a tree diff --git a/c8/stm/core.c b/c8/stm/core.c --- a/c8/stm/core.c +++ b/c8/stm/core.c @@ -45,7 +45,8 @@ void _dbg_print_commit_log() { - struct stm_commit_log_entry_s *cl = &commit_log_root; + volatile struct stm_commit_log_entry_s *cl = (volatile struct stm_commit_log_entry_s *) + &commit_log_root; fprintf(stderr, "root (%p, %d)\n", cl->next, cl->segment_num); while ((cl = cl->next)) { @@ -70,7 +71,8 @@ void stm_validate(void *free_if_abort) { - struct stm_commit_log_entry_s *cl = STM_PSEGMENT->last_commit_log_entry; + volatile struct stm_commit_log_entry_s *cl = (volatile struct stm_commit_log_entry_s *) + STM_PSEGMENT->last_commit_log_entry; /* Don't check 'cl'. This entry is already checked */ while ((cl = cl->next)) { @@ -79,10 +81,6 @@ object_t *obj; while ((obj = cl->written[i])) { - /* in case this entry's transaction has not yet discarded - the backup copies, wait. */ - while (cl->committing) - spin_loop(); _update_obj_from(cl->segment_num, obj); @@ -95,33 +93,37 @@ }; /* last fully validated entry */ - STM_PSEGMENT->last_commit_log_entry = cl; + STM_PSEGMENT->last_commit_log_entry = (struct stm_commit_log_entry_s *)cl; } } static struct stm_commit_log_entry_s *_create_commit_log_entry() { - struct list_s *lst = STM_PSEGMENT->modified_old_objects; - size_t count = list_count(lst); + struct tree_s *tree = STM_PSEGMENT->modified_old_objects; + size_t count = tree_count(tree); size_t byte_len = sizeof(struct stm_commit_log_entry_s) + (count + 1) * sizeof(object_t*); struct stm_commit_log_entry_s *result = malloc(byte_len); - int i; result->next = NULL; result->segment_num = STM_SEGMENT->segment_num; - for (i = 0; i < count; i++) { - result->written[i] = (object_t*)list_item(lst, i); - } + + int i = 0; + wlog_t *item; + TREE_LOOP_FORWARD(tree, item); + result->written[i] = (object_t*)item->addr; + i++; + TREE_LOOP_END; + + OPT_ASSERT(count == i); result->written[count] = NULL; - result->committing = false; - spinlock_acquire(result->committing); /* =true */ return result; } static struct stm_commit_log_entry_s *_validate_and_add_to_commit_log() { - struct stm_commit_log_entry_s *new, **to; + struct stm_commit_log_entry_s *new; + volatile struct stm_commit_log_entry_s **to; new = _create_commit_log_entry(); fprintf(stderr,"%p\n", new); @@ -169,7 +171,7 @@ dprintf(("prot %lu, len=%lu in seg %lu\n", first_page, (end_page - first_page + 1), i)); } - LIST_APPEND(STM_PSEGMENT->modified_old_objects, obj); + tree_insert(STM_PSEGMENT->modified_old_objects, (uintptr_t)obj, 0); LIST_APPEND(STM_PSEGMENT->objects_pointing_to_nursery, obj); obj->stm_flags &= ~GCFLAG_WRITE_BARRIER; @@ -221,7 +223,7 @@ reset_transaction_read_version(); } - assert(list_is_empty(STM_PSEGMENT->modified_old_objects)); + assert(tree_count(STM_PSEGMENT->modified_old_objects) == 0); assert(list_is_empty(STM_PSEGMENT->objects_pointing_to_nursery)); check_nursery_at_transaction_start(); } @@ -260,7 +262,6 @@ struct stm_commit_log_entry_s* entry = _validate_and_add_to_commit_log(); /* XXX:discard backup copies */ - spinlock_release(entry->committing); s_mutex_lock(); diff --git a/c8/stm/core.h b/c8/stm/core.h --- a/c8/stm/core.h +++ b/c8/stm/core.h @@ -48,7 +48,7 @@ struct stm_priv_segment_info_s { struct stm_segment_info_s pub; - struct list_s *modified_old_objects; + struct tree_s *modified_old_objects; struct list_s *objects_pointing_to_nursery; uint8_t privatization_lock; @@ -64,8 +64,7 @@ /* Commit Log things */ struct stm_commit_log_entry_s { - struct stm_commit_log_entry_s *next; - bool committing; /* true while not yet removed backup copies */ + volatile struct stm_commit_log_entry_s *next; int segment_num; object_t *written[]; /* terminated with a NULL ptr */ }; diff --git a/c8/stm/list.c b/c8/stm/list.c --- a/c8/stm/list.c +++ b/c8/stm/list.c @@ -43,6 +43,7 @@ if (tree->raw_current != tree->raw_start) { _tree_clear_node(&tree->toplevel); tree->raw_current = tree->raw_start; + tree->count = 0; } } @@ -64,7 +65,7 @@ struct tree_s tree_copy; memset(&tree_copy, 0, sizeof(struct tree_s)); - TREE_LOOP_FORWARD(*tree, item) { + TREE_LOOP_FORWARD(tree, item) { tree_insert(&tree_copy, item->addr, item->val); } TREE_LOOP_END; @@ -99,7 +100,7 @@ newtree.raw_current = newitems; newtree.raw_end = newitems + newalloc; _tree_clear_node(&newtree.toplevel); - TREE_LOOP_FORWARD(*tree, item) + TREE_LOOP_FORWARD(tree, item) { tree_insert(&newtree, item->addr, item->val); } TREE_LOOP_END; @@ -145,6 +146,7 @@ /* reuse the deleted entry and that's it */ wlog1->addr = addr; wlog1->val = val; + tree->count++; return; } /* the key must not already be present */ @@ -166,15 +168,29 @@ wlog->addr = addr; wlog->val = val; *(char **)p = (char *)wlog; + tree->count++; } static bool tree_delete_item(struct tree_s *tree, uintptr_t addr) { wlog_t *entry; - TREE_FIND(*tree, addr, entry, goto missing); + TREE_FIND(tree, addr, entry, goto missing); entry->addr = 0; + tree->count--; return true; missing: return false; } + +static wlog_t *tree_item(struct tree_s *tree, int index) +{ + int i = 0; + wlog_t *item; + TREE_LOOP_FORWARD(tree, item); + if (i == index) + return item; + i++; + TREE_LOOP_END; + return NULL; +} diff --git a/c8/stm/list.h b/c8/stm/list.h --- a/c8/stm/list.h +++ b/c8/stm/list.h @@ -125,6 +125,7 @@ struct tree_s { char *raw_start, *raw_current, *raw_end; + uintptr_t count; wlog_node_t toplevel; }; @@ -137,12 +138,16 @@ return tree->raw_current == tree->raw_start; } +static inline uintptr_t tree_count(struct tree_s *tree) { + return tree->count; +} + #define _TREE_LOOP(tree, item, INITIAL, _PLUS_) \ { \ struct { char **next; char **end; } _stack[TREE_DEPTH_MAX], *_stackp; \ char **_next, **_end, *_entry; \ long _deleted_factor = 0; \ - struct tree_s *_tree = &(tree); \ + struct tree_s *_tree = (tree); \ /* initialization */ \ _stackp = _stack; /* empty stack */ \ _next = _tree->toplevel.items + INITIAL; \ @@ -189,12 +194,12 @@ #define TREE_LOOP_END } } #define TREE_LOOP_END_AND_COMPRESS \ } if (_deleted_factor > 9) _tree_compress(_tree); } -#define TREE_LOOP_DELETE(item) { (item)->addr = NULL; _deleted_factor += 6; } +#define TREE_LOOP_DELETE(tree, item) { (tree)->count--; (item)->addr = NULL; _deleted_factor += 6; } #define TREE_FIND(tree, addr1, result, goto_not_found) \ { \ uintptr_t _key = TREE_HASH(addr1); \ - char *_p = (char *)((tree).toplevel.items); \ + char *_p = (char *)((tree)->toplevel.items); \ char *_entry = *(char **)(_p + (_key & TREE_MASK)); \ if (_entry == NULL) \ goto_not_found; /* common case, hopefully */ \ @@ -208,10 +213,11 @@ static void tree_insert(struct tree_s *tree, uintptr_t addr, uintptr_t val); static bool tree_delete_item(struct tree_s *tree, uintptr_t addr) __attribute__((unused)); +static wlog_t *tree_item(struct tree_s *tree, int index); /* SLOW */ static inline bool tree_contains(struct tree_s *tree, uintptr_t addr) { wlog_t *result; - TREE_FIND(*tree, addr, result, return false); + TREE_FIND(tree, addr, result, return false); return true; } diff --git a/c8/stm/misc.c b/c8/stm/misc.c --- a/c8/stm/misc.c +++ b/c8/stm/misc.c @@ -48,7 +48,7 @@ { if (STM_PSEGMENT->modified_old_objects == NULL) return -1; - return list_count(STM_PSEGMENT->modified_old_objects); + return tree_count(STM_PSEGMENT->modified_old_objects); } long _stm_count_objects_pointing_to_nursery(void) @@ -60,8 +60,8 @@ object_t *_stm_enum_modified_old_objects(long index) { - return (object_t *)list_item( - STM_PSEGMENT->modified_old_objects, index); + wlog_t* entry = tree_item(STM_PSEGMENT->modified_old_objects, index); + return (object_t*)entry->addr; } object_t *_stm_enum_objects_pointing_to_nursery(long index) diff --git a/c8/stm/setup.c b/c8/stm/setup.c --- a/c8/stm/setup.c +++ b/c8/stm/setup.c @@ -130,7 +130,7 @@ assert(0 <= i && i < 255); /* 255 is WL_VISITED in gcpage.c */ pr->pub.segment_num = i; pr->pub.segment_base = segment_base; - pr->modified_old_objects = list_create(); + pr->modified_old_objects = tree_create(); pr->objects_pointing_to_nursery = list_create(); pr->last_commit_log_entry = &commit_log_root; pr->pub.transaction_read_version = 0xff; @@ -162,7 +162,7 @@ struct stm_priv_segment_info_s *pr = get_priv_segment(i); assert(list_is_empty(pr->objects_pointing_to_nursery)); list_free(pr->objects_pointing_to_nursery); - list_free(pr->modified_old_objects); + tree_free(pr->modified_old_objects); } munmap(stm_object_pages, TOTAL_MEMORY); _______________________________________________ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit