Author: Armin Rigo <[email protected]>
Branch: c5
Changeset: r557:49446e74e137
Date: 2013-12-18 17:09 +0100
http://bitbucket.org/pypy/stmgc/changeset/49446e74e137/
Log: Initial import.
diff --git a/c5/Makefile b/c5/Makefile
new file mode 100644
--- /dev/null
+++ b/c5/Makefile
@@ -0,0 +1,10 @@
+
+H_FILES = core.h pagecopy.h
+C_FILES = core.c pagecopy.c
+
+
+demo1: demo1.c $(C_FILES) $(H_FILES)
+ gcc -o $@ -O2 -g demo1.c $(C_FILES) -Wall
+
+clean:
+ rm -f demo1
diff --git a/c5/core.c b/c5/core.c
new file mode 100644
--- /dev/null
+++ b/c5/core.c
@@ -0,0 +1,537 @@
+#define _GNU_SOURCE
+#include <stdlib.h>
+#include <stdio.h>
+#include <sys/mman.h>
+#include <errno.h>
+#include <assert.h>
+#include <string.h>
+
+#include "core.h"
+#include "pagecopy.h"
+
+
+/* This file only works on 64-bit Linux for now. The logic is based on
+ remapping pages around, which can get a bit confusing. Each "thread"
+ runs in its own process, so that it has its own mapping. The
+ processes share an mmap of length NB_PAGES, which is created shared
+ but anonymous, and passed to subprocesses by forking.
+
+ The mmap's content does not depend on which process is looking at it:
+ it contains what we'll call "mm pages", which is 4096 bytes of data
+ at some file offset (which all processes agree on). The term "pgoff"
+ used below means such an offset. It is a uint32_t expressed in units
+ of 4096 bytes; so the underlying mmap is limited to 2**32 pages or
+ 16TB.
+
+ The mm pages are then mapped in each process at some address, and
+ their content is accessed with regular pointers. We'll call such a
+ page a "local page". The term "local" is used because each process
+ has its own, different mapping. As it turns out, mm pages are
+ initially mapped sequentially as local pages, but this changes over
+ time. To do writes in a transaction, the data containing the object
+ is first duplicated --- so we allocate a fresh new mm page in the
+ mmap file, and copy the contents to it. Then we remap the new mm
+ page over the *same* local page as the original. So from this
+ process' point of view, the object is still at the same address, but
+ writes to it now happen to go to the new mm page instead of the old
+ one.
+
+ The local pages are usually referenced by pointers, but may also be
+ expressed as an index, called the "local index" of the page.
+*/
+
+#ifdef STM_TESTS
+# define NB_PAGES (256*10) // 10MB
+#else
+# define NB_PAGES (256*1024) // 1GB
+#endif
+#define MAP_PAGES_FLAGS (MAP_SHARED|MAP_ANONYMOUS)
+
+#define CACHE_LINE_SIZE 128 // conservatively large value to avoid aliasing
+
+#define PGKIND_NEVER_USED 0
+#define LARGE_OBJECT_WORDS 36 /* range(2, LARGE_OBJECT_WORDS) */
+#define PGKIND_FREED 0xff
+#define PGKIND_WRITE_HISTORY 0xfe
+#define PGKIND_SHARED_DESCRIPTOR 0xfd /* only for the first mm page */
+
+struct page_header_s {
+ /* Every page starts with one such structure */
+ uint16_t version; /* when the data in the page was written */
+ uint8_t modif_head; /* head of a chained list of objects in this
+ page that have modified == this->version */
+ uint8_t kind; /* either PGKIND_xxx or a number in
+ range(2, LARGE_OBJECT_WORDS) */
+ uint32_t pgoff; /* the mm page offset */
+};
+
+struct read_marker_s {
+ /* We associate a single byte to every object, by simply dividing
+ the address of the object by 16. This is the last byte of the
+ last time we have read the object. See stm_read(). */
+ unsigned char c;
+};
+
+struct write_history_s {
+ struct write_history_s *previous_older_transaction;
+ uint16_t transaction_version;
+ uint32_t nb_updates;
+ uint32_t updates[]; /* pairs (local_index, new_pgoff) */
+};
+
+struct shared_descriptor_s {
+ /* There is a single shared descriptor. This regroups all data
+ that needs to be dynamically shared among processes. The
+ first mm page is used for this. */
+ union {
+ struct page_header_s header;
+ char _pad0[CACHE_LINE_SIZE];
+ };
+ union {
+ uint64_t index_page_never_used;
+ char _pad1[CACHE_LINE_SIZE];
+ };
+ union {
+ unsigned int next_transaction_version;
+ char _pad2[CACHE_LINE_SIZE];
+ };
+ union {
+ struct write_history_s *most_recent_committed_transaction;
+ char _pad3[CACHE_LINE_SIZE];
+ };
+};
+
+struct alloc_for_size_s {
+ char *next;
+ char *end;
+};
+
+struct local_data_s {
+ /* This is just a bunch of global variables, but during testing,
+ we save it all away and restore different ones to simulate
+ different forked processes. */
+ char *read_markers;
+ struct read_marker_s *current_read_markers;
+ uint16_t transaction_version;
+ struct write_history_s *base_page_mapping;
+ struct write_history_s *writes_by_this_transaction;
+ struct alloc_for_size_s alloc[LARGE_OBJECT_WORDS];
+};
+
+struct shared_descriptor_s *stm_shared_descriptor;
+struct local_data_s stm_local;
+
+
+void stm_read(struct object_s *object)
+{
+ stm_local.current_read_markers[((uintptr_t)object) >> 4].c =
+ (unsigned char)(uintptr_t)stm_local.current_read_markers;
+}
+
+_Bool _stm_was_read(struct object_s *object)
+{
+ return (stm_local.current_read_markers[((uintptr_t)object) >> 4].c ==
+ (unsigned char)(uintptr_t)stm_local.current_read_markers);
+}
+
+void _stm_write_slowpath(struct object_s *);
+
+void stm_write(struct object_s *object)
+{
+ if (__builtin_expect(object->modified != stm_local.transaction_version,
+ 0))
+ _stm_write_slowpath(object);
+}
+
+_Bool _stm_was_written(struct object_s *object)
+{
+ return (object->modified == stm_local.transaction_version);
+}
+
+
+struct page_header_s *_stm_reserve_page(void)
+{
+ /* Grab a free mm page, and map it into the address space.
+ Return a pointer to it. It has kind == PGKIND_FREED. */
+
+ // XXX look in some free list first
+
+ /* Return the index'th mm page, which is so far NEVER_USED. It
+ should never have been accessed so far, and be already mapped
+ as the index'th local page. */
+ struct shared_descriptor_s *d = stm_shared_descriptor;
+ uint64_t index = __sync_fetch_and_add(&d->index_page_never_used, 1);
+ if (index >= NB_PAGES) {
+ fprintf(stderr, "Out of mmap'ed memory!\n");
+ abort();
+ }
+ struct page_header_s *result = (struct page_header_s *)
+ (((char *)stm_shared_descriptor) + index * 4096);
+ assert(result->kind == PGKIND_NEVER_USED);
+ result->kind = PGKIND_FREED;
+ result->pgoff = index;
+ return result;
+}
+
+
+static uint32_t get_pgoff(struct page_header_s *page)
+{
+ assert(page->pgoff > 0);
+ assert(page->pgoff < NB_PAGES);
+ return page->pgoff;
+}
+
+static uint32_t get_local_index(struct page_header_s *page)
+{
+ uint64_t index = ((char *)page) - (char *)stm_shared_descriptor;
+ assert((index & 4095) == 0);
+ index /= 4096;
+ assert(0 < index && index < NB_PAGES);
+ return index;
+}
+
+static struct page_header_s *get_page_by_local_index(uint32_t index)
+{
+ assert(0 < index && index < NB_PAGES);
+ uint64_t ofs = ((uint64_t)index) * 4096;
+ return (struct page_header_s *)(((char *)stm_shared_descriptor) + ofs);
+}
+
+void _stm_write_slowpath(struct object_s * object)
+{
+ stm_read(object);
+
+ struct page_header_s *page;
+ page = (struct page_header_s *)(((uintptr_t)object) & ~4095);
+ assert(2 <= page->kind && page->kind < LARGE_OBJECT_WORDS);
+
+ if (page->version != stm_local.transaction_version) {
+ struct page_header_s *newpage = _stm_reserve_page();
+ uint32_t old_pgoff = get_pgoff(page);
+ uint32_t new_pgoff = get_pgoff(newpage);
+
+ pagecopy(newpage, page);
+ newpage->version = stm_local.transaction_version;
+ newpage->modif_head = 0xff;
+ newpage->pgoff = new_pgoff;
+ assert(page->version != stm_local.transaction_version);
+ assert(page->pgoff == old_pgoff);
+
+ remap_file_pages((void *)page, 4096, 0, new_pgoff, MAP_PAGES_FLAGS);
+
+ assert(page->version == stm_local.transaction_version);
+ assert(page->pgoff == new_pgoff);
+
+ struct write_history_s *cur = stm_local.writes_by_this_transaction;
+ uint64_t i = cur->nb_updates++;
+ size_t history_size_max = 4096 - (((uintptr_t)cur) & 4095);
+ assert(sizeof(*cur) + cur->nb_updates * 8 <= history_size_max);
+ cur->updates[i * 2 + 0] = get_local_index(page);
+ cur->updates[i * 2 + 1] = new_pgoff;
+ }
+ object->modified = stm_local.transaction_version;
+ object->modif_next = page->modif_head;
+ page->modif_head = (uint8_t)(((uintptr_t)object) >> 4);
+ assert(page->modif_head != 0xff);
+}
+
+char *_stm_alloc_next_page(size_t i)
+{
+ struct page_header_s *newpage = _stm_reserve_page();
+ newpage->modif_head = 0xff;
+ newpage->kind = i; /* object size in words */
+ newpage->version = stm_local.transaction_version;
+ stm_local.alloc[i].next = ((char *)(newpage + 1)) + (i * 8);
+ stm_local.alloc[i].end = ((char *)newpage) + 4096;
+ assert(stm_local.alloc[i].next <= stm_local.alloc[i].end);
+ return (char *)(newpage + 1);
+}
+
+struct object_s *stm_allocate(size_t size)
+{
+ assert(size % 8 == 0);
+ size_t i = size / 8;
+ assert(2 <= i && i < LARGE_OBJECT_WORDS);
+ struct alloc_for_size_s *alloc = &stm_local.alloc[i];
+
+ char *p = alloc->next;
+ alloc->next += size;
+ if (alloc->next > alloc->end)
+ p = _stm_alloc_next_page(i);
+
+ struct object_s *result = (struct object_s *)p;
+ result->modified = stm_local.transaction_version;
+ /*result->modif_next is uninitialized*/
+ result->flags = 0x42; /* for debugging */
+ return result;
+}
+
+
+unsigned char stm_get_read_marker_number(void)
+{
+ return (unsigned char)(uintptr_t)stm_local.current_read_markers;
+}
+
+void stm_set_read_marker_number(uint8_t num)
+{
+ char *stm_pages = ((char *)stm_shared_descriptor) + 4096;
+ uintptr_t delta = ((uintptr_t)stm_pages) >> 4;
+ struct read_marker_s *crm = (struct read_marker_s *)stm_local.read_markers;
+ stm_local.current_read_markers = crm - delta;
+ assert(stm_get_read_marker_number() == 0);
+ stm_local.current_read_markers += num;
+}
+
+void stm_setup(void)
+{
+ if (sizeof(char *) != 8) {
+ fprintf(stderr, "Only works on 64-bit Linux systems for now!\n");
+ abort();
+ }
+ if (NB_PAGES > (1ull << 32)) {
+ fprintf(stderr, "Cannot use more than 1<<32 pages of memory");
+ abort();
+ }
+ char *stm_pages = mmap(NULL, NB_PAGES*4096, PROT_READ|PROT_WRITE,
+ MAP_PAGES_FLAGS, -1, 0);
+ if (stm_pages == MAP_FAILED) {
+ perror("mmap stm_pages failed");
+ abort();
+ }
+ assert(sizeof(struct shared_descriptor_s) <= 4096);
+ stm_shared_descriptor = (struct shared_descriptor_s *)stm_pages;
+ stm_shared_descriptor->header.kind = PGKIND_SHARED_DESCRIPTOR;
+ /* the page at index 0 contains the '*stm_shared_descriptor' structure */
+ /* the page at index 1 is reserved for history_fast_forward() */
+ stm_shared_descriptor->index_page_never_used = 2;
+ stm_shared_descriptor->next_transaction_version = 1;
+}
+
+void _stm_teardown(void)
+{
+ munmap((void *)stm_shared_descriptor, NB_PAGES*4096);
+ stm_shared_descriptor = NULL;
+}
+
+void stm_setup_process(void)
+{
+ memset(&stm_local, 0, sizeof(stm_local));
+ stm_local.read_markers = mmap(NULL, NB_PAGES*(4096 >> 4) + 1,
+ PROT_READ|PROT_WRITE,
+ MAP_PRIVATE|MAP_ANONYMOUS,
+ -1, 0);
+ if (stm_local.read_markers == MAP_FAILED) {
+ perror("mmap stm_read_markers failed");
+ abort();
+ }
+
+ stm_set_read_marker_number(42);
+ assert(stm_get_read_marker_number() == 42);
+ stm_set_read_marker_number(1);
+}
+
+void _stm_teardown_process(void)
+{
+ munmap((void *)stm_local.read_markers, NB_PAGES*(4096 >> 4) + 1);
+ memset(&stm_local, 0, sizeof(stm_local));
+}
+
+static size_t get_obj_size_in_words(struct page_header_s *page)
+{
+ size_t result = page->kind;
+ assert(2 <= result && result < LARGE_OBJECT_WORDS);
+ return result;
+}
+
+static
+struct object_s *get_object_in_page(struct page_header_s *page, size_t index)
+{
+ /* Slight complication here, because objects are aligned to 8 bytes,
+ but we divides their page offset by 16 to fit a byte (4096/16 =
+ 256) and reduce memory overhead of the read markers. Objects are
+ at least 16 bytes in size, so there is no ambiguity. Example for
+ objects of 24 bytes of the organization inside a page (each word
+ of the first line is 8 bytes):
+
+ [HDR][OBJ.ECT.24][OBJ.ECT.24][OBJ.ECT.24][OBJ.ECT.24][..
+ 0 (16) 32 48 (64) 80 96
+
+ The second line is all possible offsets, which are multiples of
+ 16. They are the rounded-down version of the real offsets.
+ object and round it down to a mutiple of 16. For objects of size
+ 24, the numbers in parenthesis above are not reachable this way.
+ The number 255 is never reachable. To go from the number to the
+ object address, we have to add either 0 or 8.
+ */
+ size_t obj_size_in_words = get_obj_size_in_words(page);
+ size_t offset = (index << 4) +
+ ((index << 1) % obj_size_in_words == 0 ? 8 : 0);
+ return (struct object_s *)(((char *)page) + offset);
+}
+
+static int history_fast_forward(struct write_history_s *new, int conflict)
+{
+ /* XXX do a non-recursive version, which also should avoid repeated
+ remap_file_pages() on the same local-index-ed page */
+ if (stm_local.base_page_mapping != new->previous_older_transaction) {
+ conflict = history_fast_forward(new->previous_older_transaction,
+ conflict);
+ }
+ assert(stm_local.base_page_mapping == new->previous_older_transaction);
+
+ uint64_t i, nb_updates = new->nb_updates;
+ for (i = 0; i < nb_updates; i++) {
+ retry:;
+ /* new->updates[] is an array of pairs (local_index, new_pgoff) */
+ uint32_t local_index = new->updates[i * 2 + 0];
+ uint32_t new_pgoff = new->updates[i * 2 + 1];
+ struct page_header_s *page = get_page_by_local_index(local_index);
+ struct page_header_s *mypage = page;
+
+ if (!conflict && page->version == stm_local.transaction_version) {
+ /* If we have also modified this page, then we must merge our
+ changes with the ones done at 'new_pgoff'. In this case
+ we map 'new_pgoff' at the local index 1. */
+ page = get_page_by_local_index(1);
+ }
+
+ remap_file_pages((void *)page, 4096, 0, new_pgoff, MAP_PAGES_FLAGS);
+ assert(page->pgoff == new_pgoff);
+
+ if (conflict)
+ continue;
+
+ /* look for read-from-me, write-from-others conflicts */
+ if (mypage == page) {
+ /* only look for conflicts: for every object modified by the
+ other transaction, check that it was not read by us. */
+ size_t modif_index = page->modif_head;
+ while (modif_index != 0xff) {
+ struct object_s *obj = get_object_in_page(page, modif_index);
+ assert(obj->flags == 0x42);
+ if (_stm_was_read(obj)) {
+ fprintf(stderr, "# conflict: %p\n", obj);
+ conflict = 1;
+ break;
+ }
+ modif_index = obj->modif_next;
+ }
+ }
+ else {
+ /* Merge two versions of the page: for every object modified
+ by the other transaction, check that it was not read by us,
+ and then copy it over into our own page at 'mypage'. */
+ size_t obj_size = get_obj_size_in_words(page) << 3;
+ uint64_t diff_to_mypage = ((char *)mypage) - (char *)page;
+ size_t modif_index = page->modif_head;
+ while (modif_index != 0xff) {
+ struct object_s *obj = get_object_in_page(page, modif_index);
+ struct object_s *myobj = (struct object_s *)
+ (((char *)obj) + diff_to_mypage);
+ assert(obj->flags == 0x42);
+ assert(myobj->flags == 0x42); // || myobj->flags == 0);
+ if (_stm_was_read(myobj)) {
+ fprintf(stderr, "# conflict: %p\n", myobj);
+ conflict = 1;
+ goto retry;
+ }
+ memcpy(myobj, obj, obj_size);
+ modif_index = obj->modif_next;
+ }
+ }
+ }
+ stm_local.base_page_mapping = new;
+ return conflict;
+}
+
+void stm_start_transaction(void)
+{
+ struct shared_descriptor_s *d = stm_shared_descriptor;
+ stm_local.transaction_version =
+ __sync_fetch_and_add(&d->next_transaction_version, 1u);
+ assert(stm_local.transaction_version <= 0xffff);
+
+ struct page_header_s *newpage = _stm_reserve_page();
+ newpage->kind = PGKIND_WRITE_HISTORY;
+
+ struct write_history_s *cur = (struct write_history_s *)(newpage + 1);
+ cur->previous_older_transaction = NULL;
+ cur->transaction_version = stm_local.transaction_version;
+ cur->nb_updates = 0;
+ assert(stm_local.writes_by_this_transaction == NULL);
+ stm_local.writes_by_this_transaction = cur;
+
+ struct write_history_s *hist = d->most_recent_committed_transaction;
+ if (hist != stm_local.base_page_mapping) {
+ history_fast_forward(hist, 1);
+ }
+}
+
+_Bool stm_stop_transaction(void)
+{
+ struct shared_descriptor_s *d = stm_shared_descriptor;
+ assert(stm_local.writes_by_this_transaction != NULL);
+ int conflict = 0;
+ //fprintf(stderr, "stm_stop_transaction\n");
+
+ while (1) {
+ struct write_history_s *hist = d->most_recent_committed_transaction;
+ if (hist != stm_local.base_page_mapping) {
+ conflict = history_fast_forward(hist, 0);
+ if (conflict)
+ break;
+ else
+ continue; /* retry from the start of the loop */
+ }
+ struct write_history_s *cur = stm_local.writes_by_this_transaction;
+ cur->previous_older_transaction = hist;
+ if (__sync_bool_compare_and_swap(&d->most_recent_committed_transaction,
+ hist, cur))
+ break;
+ }
+ stm_local.writes_by_this_transaction = NULL;
+
+ assert(stm_get_read_marker_number() < 0xff);
+ stm_local.current_read_markers++;
+ return !conflict;
+}
+
+#ifdef STM_TESTS
+struct local_data_s *_stm_save_local_state(void)
+{
+ uint64_t i, page_count = stm_shared_descriptor->index_page_never_used;
+ uint32_t *pgoffs;
+ struct local_data_s *p = malloc(sizeof(struct local_data_s) +
+ page_count * sizeof(uint32_t));
+ assert(p != NULL);
+ memcpy(p, &stm_local, sizeof(stm_local));
+
+ pgoffs = (uint32_t *)(p + 1);
+ pgoffs[0] = page_count;
+ for (i = 2; i < page_count; i++) {
+ pgoffs[i] = get_pgoff(get_page_by_local_index(i));
+ }
+
+ return p;
+}
+
+void _stm_restore_local_state(struct local_data_s *p)
+{
+ uint64_t i, page_count;
+ uint32_t *pgoffs;
+
+ remap_file_pages((void *)stm_shared_descriptor, 4096 * NB_PAGES,
+ 0, 0, MAP_PAGES_FLAGS);
+
+ pgoffs = (uint32_t *)(p + 1);
+ page_count = pgoffs[0];
+ for (i = 2; i < page_count; i++) {
+ struct page_header_s *page = get_page_by_local_index(i);
+ remap_file_pages((void *)page, 4096, 0, pgoffs[i], MAP_PAGES_FLAGS);
+ assert(get_pgoff(page) == pgoffs[i]);
+ }
+
+ memcpy(&stm_local, p, sizeof(struct local_data_s));
+ free(p);
+}
+#endif
diff --git a/c5/core.h b/c5/core.h
new file mode 100644
--- /dev/null
+++ b/c5/core.h
@@ -0,0 +1,30 @@
+#ifndef _STM_CORE_H
+#define _STM_CORE_H
+
+#include <stdint.h>
+
+struct object_s {
+ /* Every objects starts with one such structure */
+ uint16_t modified;
+ uint8_t modif_next;
+ uint8_t flags;
+};
+
+void stm_setup(void);
+void stm_setup_process(void);
+
+void stm_start_transaction(void);
+_Bool stm_stop_transaction(void);
+struct object_s *stm_allocate(size_t size);
+
+void stm_read(struct object_s *object);
+void stm_write(struct object_s *object);
+_Bool _stm_was_read(struct object_s *object);
+_Bool _stm_was_written(struct object_s *object);
+
+struct local_data_s *_stm_save_local_state(void);
+void _stm_restore_local_state(struct local_data_s *p);
+void _stm_teardown(void);
+void _stm_teardown_process(void);
+
+#endif
diff --git a/c5/demo1.c b/c5/demo1.c
new file mode 100644
--- /dev/null
+++ b/c5/demo1.c
@@ -0,0 +1,100 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <unistd.h>
+#include <assert.h>
+#include <sys/types.h>
+#include <sys/wait.h>
+
+#include "core.h"
+
+
+#define NUM_THREADS 4
+
+
+typedef struct {
+ struct object_s header;
+ int val1, val2;
+} obj_t;
+
+void do_run_in_thread(int i)
+{
+ stm_start_transaction();
+ obj_t *ob1 = (obj_t *)stm_allocate(16);
+ obj_t *ob2 = (obj_t *)stm_allocate(16);
+
+ assert(!_stm_was_read(&ob1->header));
+ assert(!_stm_was_read(&ob2->header));
+ stm_read(&ob1->header);
+ stm_read(&ob2->header);
+ assert(_stm_was_read(&ob1->header));
+ assert(_stm_was_read(&ob2->header));
+ assert(_stm_was_written(&ob1->header));
+ assert(_stm_was_written(&ob2->header));
+ stm_write(&ob1->header);
+ stm_write(&ob2->header);
+ assert(_stm_was_written(&ob1->header));
+ assert(_stm_was_written(&ob2->header));
+ ob1->val1 = 100;
+ ob1->val2 = 200;
+ ob2->val1 = 300;
+ ob2->val2 = 400;
+
+ stm_stop_transaction();
+
+ int j;
+ for (j=0; j<2; j++) {
+ stm_start_transaction();
+
+ assert(!_stm_was_read(&ob1->header));
+ assert(!_stm_was_read(&ob2->header));
+ assert(!_stm_was_written(&ob1->header));
+ assert(!_stm_was_written(&ob2->header));
+ stm_read(&ob1->header);
+ printf("thread %d: ob1.val2=%d\n", i, ob1->val2);
+
+ stm_write(&ob1->header);
+ assert(_stm_was_written(&ob1->header));
+ assert(!_stm_was_written(&ob2->header));
+
+ stm_stop_transaction();
+ }
+
+ printf("thread %d: %p, %p\n", i, ob1, ob2);
+}
+
+void do_test(void)
+{
+ int i;
+ pid_t child_pids[NUM_THREADS];
+
+ for (i = 0; i < NUM_THREADS; i++) {
+ child_pids[i] = fork();
+ if (child_pids[i] == -1) {
+ perror("fork");
+ abort();
+ }
+ if (child_pids[i] == 0) {
+ stm_setup_process();
+ do_run_in_thread(i);
+ exit(0);
+ }
+ }
+
+ for (i = 0; i < NUM_THREADS; i++) {
+ int status;
+ if (waitpid(child_pids[i], &status, 0) == -1) {
+ perror("waitpid");
+ abort();
+ }
+ }
+}
+
+
+int main(int argc, char *argv[])
+{
+ stm_setup();
+
+ do_test();
+
+ return 0;
+}
diff --git a/c5/pagecopy.c b/c5/pagecopy.c
new file mode 100644
--- /dev/null
+++ b/c5/pagecopy.c
@@ -0,0 +1,60 @@
+
+void pagecopy(void *dest, const void *src)
+{
+ asm volatile("0:\n"
+ "movdqa (%0), %%xmm0\n"
+ "movdqa 16(%0), %%xmm1\n"
+ "movdqa 32(%0), %%xmm2\n"
+ "movdqa 48(%0), %%xmm3\n"
+ "movdqa 64(%0), %%xmm4\n"
+ "movdqa 80(%0), %%xmm5\n"
+ "movdqa 96(%0), %%xmm6\n"
+ "movdqa 112(%0), %%xmm7\n"
+ "addq $128, %0\n"
+ "movdqa %%xmm0, (%1)\n"
+ "movdqa %%xmm1, 16(%1)\n"
+ "movdqa %%xmm2, 32(%1)\n"
+ "movdqa %%xmm3, 48(%1)\n"
+ "movdqa %%xmm4, 64(%1)\n"
+ "movdqa %%xmm5, 80(%1)\n"
+ "movdqa %%xmm6, 96(%1)\n"
+ "movdqa %%xmm7, 112(%1)\n"
+ "addq $128, %1\n"
+ "cmpq %2, %0\n"
+ "jne 0b"
+ : "=r"(src), "=r"(dest)
+ : "r"((char *)src + 4096), "0"(src), "1"(dest)
+ : "xmm0", "xmm1", "xmm2", "xmm3",
+ "xmm4", "xmm5", "xmm6", "xmm7");
+}
+
+#if 0 /* XXX enable if detected on the cpu */
+void pagecopy_ymm8(void *dest, const void *src)
+{
+ asm volatile("0:\n"
+ "vmovdqa (%0), %%ymm0\n"
+ "vmovdqa 32(%0), %%ymm1\n"
+ "vmovdqa 64(%0), %%ymm2\n"
+ "vmovdqa 96(%0), %%ymm3\n"
+ "vmovdqa 128(%0), %%ymm4\n"
+ "vmovdqa 160(%0), %%ymm5\n"
+ "vmovdqa 192(%0), %%ymm6\n"
+ "vmovdqa 224(%0), %%ymm7\n"
+ "addq $256, %0\n"
+ "vmovdqa %%ymm0, (%1)\n"
+ "vmovdqa %%ymm1, 32(%1)\n"
+ "vmovdqa %%ymm2, 64(%1)\n"
+ "vmovdqa %%ymm3, 96(%1)\n"
+ "vmovdqa %%ymm4, 128(%1)\n"
+ "vmovdqa %%ymm5, 160(%1)\n"
+ "vmovdqa %%ymm6, 192(%1)\n"
+ "vmovdqa %%ymm7, 224(%1)\n"
+ "addq $256, %1\n"
+ "cmpq %2, %0\n"
+ "jne 0b"
+ : "=r"(src), "=r"(dest)
+ : "r"((char *)src + 4096), "0"(src), "1"(dest)
+ : "xmm0", "xmm1", "xmm2", "xmm3",
+ "xmm4", "xmm5", "xmm6", "xmm7");
+}
+#endif
diff --git a/c5/pagecopy.h b/c5/pagecopy.h
new file mode 100644
--- /dev/null
+++ b/c5/pagecopy.h
@@ -0,0 +1,2 @@
+
+void pagecopy(void *dest, const void *src);
diff --git a/c5/test/support.py b/c5/test/support.py
new file mode 100644
--- /dev/null
+++ b/c5/test/support.py
@@ -0,0 +1,107 @@
+import os
+import cffi
+
+# ----------
+
+parent_dir = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
+
+header_files = [os.path.join(parent_dir, _n) for _n in
+ "core.h pagecopy.h".split()]
+source_files = [os.path.join(parent_dir, _n) for _n in
+ "core.c pagecopy.c".split()]
+
+_pycache_ = os.path.join(parent_dir, 'test', '__pycache__')
+if os.path.exists(_pycache_):
+ _fs = [_f for _f in os.listdir(_pycache_) if _f.startswith('_cffi_')]
+ if _fs:
+ _fsmtime = min(os.stat(os.path.join(_pycache_, _f)).st_mtime
+ for _f in _fs)
+ if any(os.stat(src).st_mtime >= _fsmtime
+ for src in header_files + source_files):
+ import shutil
+ shutil.rmtree(_pycache_)
+
+# ----------
+
+ffi = cffi.FFI()
+ffi.cdef("""
+void stm_setup(void);
+void stm_setup_process(void);
+
+void stm_start_transaction(void);
+_Bool stm_stop_transaction(void);
+struct object_s *stm_allocate(size_t size);
+
+void stm_read(struct object_s *object);
+void stm_write(struct object_s *object);
+_Bool _stm_was_read(struct object_s *object);
+_Bool _stm_was_written(struct object_s *object);
+
+struct local_data_s *_stm_save_local_state(void);
+void _stm_restore_local_state(struct local_data_s *p);
+void _stm_teardown(void);
+void _stm_teardown_process(void);
+""")
+
+lib = ffi.verify('''
+#include "core.h"
+''', sources=source_files,
+ define_macros=[('STM_TESTS', '1')],
+ undef_macros=['NDEBUG'],
+ include_dirs=[parent_dir],
+ extra_compile_args=['-g', '-O0'])
+
+def intptr(p):
+ return int(ffi.cast("intptr_t", p))
+
+def stm_allocate(size):
+ return ffi.cast("char *", lib.stm_allocate(size))
+
+def stm_read(ptr):
+ lib.stm_read(ffi.cast("struct object_s *", ptr))
+
+def stm_write(ptr):
+ lib.stm_write(ffi.cast("struct object_s *", ptr))
+
+def _stm_was_read(ptr):
+ return lib._stm_was_read(ffi.cast("struct object_s *", ptr))
+
+def _stm_was_written(ptr):
+ return lib._stm_was_written(ffi.cast("struct object_s *", ptr))
+
+def stm_start_transaction():
+ lib.stm_start_transaction()
+
+def stm_stop_transaction(expected_conflict):
+ res = lib.stm_stop_transaction()
+ if expected_conflict:
+ assert res == 0
+ else:
+ assert res == 1
+
+
+class BaseTest(object):
+
+ def setup_method(self, meth):
+ lib.stm_setup()
+ lib.stm_setup_process()
+ self.saved_states = {}
+ self.current_proc = "main"
+
+ def teardown_method(self, meth):
+ lib._stm_teardown_process()
+ for saved_state in self.saved_states.values():
+ lib._stm_restore_local_state(saved_state)
+ lib._stm_teardown_process()
+ del self.saved_states
+ lib._stm_teardown()
+
+ def switch(self, process_name):
+ self.saved_states[self.current_proc] = lib._stm_save_local_state()
+ try:
+ target_saved_state = self.saved_states.pop(process_name)
+ except KeyError:
+ lib.stm_setup_process()
+ else:
+ lib._stm_restore_local_state(target_saved_state)
+ self.current_proc = process_name
diff --git a/c5/test/test_basic.py b/c5/test/test_basic.py
new file mode 100644
--- /dev/null
+++ b/c5/test/test_basic.py
@@ -0,0 +1,153 @@
+from support import *
+
+
+class TestBasic(BaseTest):
+
+ def test_thread_local_allocations(self):
+ p1 = stm_allocate(16)
+ p2 = stm_allocate(16)
+ assert intptr(p2) - intptr(p1) == 16
+ p3 = stm_allocate(16)
+ assert intptr(p3) - intptr(p2) == 16
+ #
+ self.switch("sub1")
+ p1s = stm_allocate(16)
+ assert abs(intptr(p1s) - intptr(p3)) >= 4000
+ #
+ self.switch("main")
+ p4 = stm_allocate(16)
+ assert intptr(p4) - intptr(p3) == 16
+
+ def test_read_write_1(self):
+ stm_start_transaction()
+ p1 = stm_allocate(16)
+ p1[8] = 'a'
+ stm_stop_transaction(False)
+ #
+ self.switch("sub1")
+ stm_start_transaction()
+ stm_write(p1)
+ assert p1[8] == 'a'
+ p1[8] = 'b'
+ #
+ self.switch("main")
+ stm_start_transaction()
+ stm_read(p1)
+ assert p1[8] == 'a'
+ #
+ self.switch("sub1")
+ stm_stop_transaction(False)
+ #
+ self.switch("main")
+ assert p1[8] == 'a'
+
+ def test_start_transaction_updates(self):
+ stm_start_transaction()
+ p1 = stm_allocate(16)
+ p1[8] = 'a'
+ stm_stop_transaction(False)
+ #
+ self.switch("sub1")
+ stm_start_transaction()
+ stm_write(p1)
+ assert p1[8] == 'a'
+ p1[8] = 'b'
+ stm_stop_transaction(False)
+ #
+ self.switch("main")
+ assert p1[8] == 'a'
+ stm_start_transaction()
+ assert p1[8] == 'b'
+
+ def test_resolve_no_conflict_empty(self):
+ stm_start_transaction()
+ #
+ self.switch("sub1")
+ stm_start_transaction()
+ stm_stop_transaction(False)
+ #
+ self.switch("main")
+ stm_stop_transaction(False)
+
+ def test_resolve_no_conflict_write_only_in_already_committed(self):
+ stm_start_transaction()
+ p1 = stm_allocate(16)
+ p1[8] = 'a'
+ stm_stop_transaction(False)
+ stm_start_transaction()
+ #
+ self.switch("sub1")
+ stm_start_transaction()
+ stm_write(p1)
+ p1[8] = 'b'
+ stm_stop_transaction(False)
+ #
+ self.switch("main")
+ assert p1[8] == 'a'
+ stm_stop_transaction(False)
+ assert p1[8] == 'b'
+
+ def test_resolve_write_read_conflict(self):
+ stm_start_transaction()
+ p1 = stm_allocate(16)
+ p1[8] = 'a'
+ stm_stop_transaction(False)
+ stm_start_transaction()
+ #
+ self.switch("sub1")
+ stm_start_transaction()
+ stm_write(p1)
+ p1[8] = 'b'
+ stm_stop_transaction(False)
+ #
+ self.switch("main")
+ stm_read(p1)
+ assert p1[8] == 'a'
+ stm_stop_transaction(expected_conflict=True)
+ assert p1[8] in ('a', 'b')
+ stm_start_transaction()
+ assert p1[8] == 'b'
+
+ def test_resolve_write_write_conflict(self):
+ stm_start_transaction()
+ p1 = stm_allocate(16)
+ p1[8] = 'a'
+ stm_stop_transaction(False)
+ stm_start_transaction()
+ #
+ self.switch("sub1")
+ stm_start_transaction()
+ stm_write(p1)
+ p1[8] = 'b'
+ stm_stop_transaction(False)
+ #
+ self.switch("main")
+ assert p1[8] == 'a'
+ stm_write(p1)
+ p1[8] = 'c'
+ stm_stop_transaction(expected_conflict=True)
+ assert p1[8] in ('a', 'b')
+ stm_start_transaction()
+ assert p1[8] == 'b'
+
+ def test_resolve_write_write_no_conflict(self):
+ stm_start_transaction()
+ p1 = stm_allocate(16)
+ p2 = stm_allocate(16)
+ p1[8] = 'a'
+ p2[8] = 'A'
+ stm_stop_transaction(False)
+ stm_start_transaction()
+ #
+ self.switch("sub1")
+ stm_start_transaction()
+ stm_write(p1)
+ p1[8] = 'b'
+ stm_stop_transaction(False)
+ #
+ self.switch("main")
+ stm_write(p2)
+ p2[8] = 'C'
+ stm_stop_transaction(False)
+ assert p1[8] == 'b'
+ assert p2[8] == 'C'
diff --git a/c5/test/test_bug.py b/c5/test/test_bug.py
new file mode 100644
--- /dev/null
+++ b/c5/test/test_bug.py
@@ -0,0 +1,429 @@
+from support import *
+
+
+class TestBug(BaseTest):
+
+ def test_bug1(self):
+ stm_start_transaction()
+ p8 = stm_allocate(16)
+ p8[8] = '\x08'
+ stm_stop_transaction(False)
+ #
+ self.switch("sub1")
+ self.switch("main")
+ stm_start_transaction()
+ stm_write(p8)
+ p8[8] = '\x97'
+ #
+ self.switch("sub1")
+ stm_start_transaction()
+ stm_read(p8)
+ assert p8[8] == '\x08'
+
+ def test_bug2(self):
+ stm_start_transaction()
+ p0 = stm_allocate(16)
+ p1 = stm_allocate(16)
+ p2 = stm_allocate(16)
+ p3 = stm_allocate(16)
+ p4 = stm_allocate(16)
+ p5 = stm_allocate(16)
+ p6 = stm_allocate(16)
+ p7 = stm_allocate(16)
+ p8 = stm_allocate(16)
+ p9 = stm_allocate(16)
+ p0[8] = '\x00'
+ p1[8] = '\x01'
+ p2[8] = '\x02'
+ p3[8] = '\x03'
+ p4[8] = '\x04'
+ p5[8] = '\x05'
+ p6[8] = '\x06'
+ p7[8] = '\x07'
+ p8[8] = '\x08'
+ p9[8] = '\t'
+ stm_stop_transaction(False)
+ self.switch(0)
+ self.switch(1)
+ self.switch(2)
+ #
+ self.switch(1)
+ stm_start_transaction()
+ stm_read(p7)
+ assert p7[8] == '\x07'
+ #
+ self.switch(1)
+ stm_read(p0)
+ assert p0[8] == '\x00'
+ #
+ self.switch(1)
+ stm_read(p4)
+ assert p4[8] == '\x04'
+ #
+ self.switch(0)
+ stm_start_transaction()
+ stm_read(p3)
+ assert p3[8] == '\x03'
+ #
+ self.switch(2)
+ stm_start_transaction()
+ stm_read(p8)
+ assert p8[8] == '\x08'
+ stm_write(p8)
+ p8[8] = '\x08'
+ #
+ self.switch(0)
+ stm_read(p0)
+ assert p0[8] == '\x00'
+ #
+ self.switch(0)
+ stm_read(p0)
+ assert p0[8] == '\x00'
+ #
+ self.switch(1)
+ stm_read(p2)
+ assert p2[8] == '\x02'
+ #
+ self.switch(2)
+ stm_read(p2)
+ assert p2[8] == '\x02'
+ #
+ self.switch(2)
+ stm_read(p2)
+ assert p2[8] == '\x02'
+ stm_write(p2)
+ p2[8] = 'm'
+ #
+ self.switch(0)
+ stm_read(p4)
+ assert p4[8] == '\x04'
+ stm_write(p4)
+ p4[8] = '\xc5'
+ #
+ self.switch(2)
+ stm_read(p1)
+ assert p1[8] == '\x01'
+ #
+ self.switch(2)
+ stm_stop_transaction(False) #1
+ # ['\x00', '\x01', 'm', '\x03', '\x04', '\x05', '\x06', '\x07',
'\x08', '\t']
+ # log: [8, 2]
+ #
+ self.switch(0)
+ stm_stop_transaction(False) #2
+ # ['\x00', '\x01', 'm', '\x03', '\xc5', '\x05', '\x06', '\x07',
'\x08', '\t']
+ # log: [4]
+ #
+ self.switch(0)
+ stm_start_transaction()
+ stm_read(p6)
+ assert p6[8] == '\x06'
+ #
+ self.switch(0)
+ stm_read(p4)
+ assert p4[8] == '\xc5'
+ #
+ self.switch(0)
+ stm_read(p4)
+ assert p4[8] == '\xc5'
+ #
+ self.switch(1)
+ stm_read(p0)
+ assert p0[8] == '\x00'
+ #
+ self.switch(1)
+ stm_stop_transaction(True) #3
+ # conflict: 0xdf0a8028
+ #
+ self.switch(2)
+ stm_start_transaction()
+ stm_read(p6)
+ assert p6[8] == '\x06'
+ #
+ self.switch(1)
+ stm_start_transaction()
+ stm_read(p1)
+ assert p1[8] == '\x01'
+ #
+ self.switch(0)
+ stm_read(p4)
+ assert p4[8] == '\xc5'
+ stm_write(p4)
+ p4[8] = '\x0c'
+ #
+ self.switch(2)
+ stm_read(p2)
+ assert p2[8] == 'm'
+ stm_write(p2)
+ p2[8] = '\x81'
+ #
+ self.switch(2)
+ stm_read(p7)
+ assert p7[8] == '\x07'
+ #
+ self.switch(0)
+ stm_read(p5)
+ assert p5[8] == '\x05'
+ stm_write(p5)
+ p5[8] = 'Z'
+ #
+ self.switch(1)
+ stm_stop_transaction(False) #4
+ # ['\x00', '\x01', 'm', '\x03', '\xc5', '\x05', '\x06', '\x07',
'\x08', '\t']
+ # log: []
+ #
+ self.switch(2)
+ stm_read(p8)
+ assert p8[8] == '\x08'
+ #
+ self.switch(0)
+ stm_read(p0)
+ assert p0[8] == '\x00'
+ #
+ self.switch(1)
+ stm_start_transaction()
+ stm_read(p0)
+ assert p0[8] == '\x00'
+ #
+ self.switch(2)
+ stm_read(p9)
+ assert p9[8] == '\t'
+ stm_write(p9)
+ p9[8] = '\x81'
+ #
+ self.switch(0)
+ stm_read(p0)
+ assert p0[8] == '\x00'
+ #
+ self.switch(1)
+ stm_read(p2)
+ assert p2[8] == 'm'
+ #
+ self.switch(2)
+ stm_read(p9)
+ assert p9[8] == '\x81'
+ stm_write(p9)
+ p9[8] = 'g'
+ #
+ self.switch(1)
+ stm_read(p3)
+ assert p3[8] == '\x03'
+ #
+ self.switch(2)
+ stm_read(p7)
+ assert p7[8] == '\x07'
+ #
+ self.switch(1)
+ stm_read(p1)
+ assert p1[8] == '\x01'
+ #
+ self.switch(0)
+ stm_read(p2)
+ assert p2[8] == 'm'
+ stm_write(p2)
+ p2[8] = 'T'
+ #
+ self.switch(2)
+ stm_read(p4)
+ assert p4[8] == '\xc5'
+ #
+ self.switch(2)
+ stm_read(p9)
+ assert p9[8] == 'g'
+ #
+ self.switch(2)
+ stm_read(p1)
+ assert p1[8] == '\x01'
+ stm_write(p1)
+ p1[8] = 'L'
+ #
+ self.switch(0)
+ stm_read(p0)
+ assert p0[8] == '\x00'
+ #
+ self.switch(2)
+ stm_read(p0)
+ assert p0[8] == '\x00'
+ stm_write(p0)
+ p0[8] = '\xf3'
+ #
+ self.switch(1)
+ stm_stop_transaction(False) #5
+ # ['\x00', '\x01', 'm', '\x03', '\xc5', '\x05', '\x06', '\x07',
'\x08', '\t']
+ # log: []
+ #
+ self.switch(0)
+ stm_read(p1)
+ assert p1[8] == '\x01'
+ stm_write(p1)
+ p1[8] = '*'
+ #
+ self.switch(1)
+ stm_start_transaction()
+ stm_read(p3)
+ assert p3[8] == '\x03'
+ stm_write(p3)
+ p3[8] = '\xd2'
+ #
+ self.switch(0)
+ stm_stop_transaction(False) #6
+ # ['\x00', '*', 'T', '\x03', '\x0c', 'Z', '\x06', '\x07', '\x08', '\t']
+ # log: [1, 2, 4, 5]
+ #
+ self.switch(1)
+ stm_read(p7)
+ assert p7[8] == '\x07'
+ stm_write(p7)
+ p7[8] = '.'
+ #
+ self.switch(0)
+ stm_start_transaction()
+ stm_read(p7)
+ assert p7[8] == '\x07'
+ #
+ self.switch(1)
+ stm_read(p2)
+ assert p2[8] == 'm'
+ stm_write(p2)
+ p2[8] = '\xe9'
+ #
+ self.switch(1)
+ stm_read(p0)
+ assert p0[8] == '\x00'
+ #
+ self.switch(0)
+ stm_read(p1)
+ assert p1[8] == '*'
+ #
+ self.switch(0)
+ stm_read(p8)
+ assert p8[8] == '\x08'
+ stm_write(p8)
+ p8[8] = 'X'
+ #
+ self.switch(2)
+ stm_stop_transaction(True) #7
+ # conflict: 0xdf0a8018
+ #
+ self.switch(1)
+ stm_read(p9)
+ assert p9[8] == '\t'
+ #
+ self.switch(0)
+ stm_read(p8)
+ assert p8[8] == 'X'
+ #
+ self.switch(1)
+ stm_read(p4)
+ assert p4[8] == '\xc5'
+ stm_write(p4)
+ p4[8] = '\xb2'
+ #
+ self.switch(0)
+ stm_read(p9)
+ assert p9[8] == '\t'
+ #
+ self.switch(2)
+ stm_start_transaction()
+ stm_read(p5)
+ assert p5[8] == 'Z'
+ stm_write(p5)
+ p5[8] = '\xfa'
+ #
+ self.switch(2)
+ stm_read(p3)
+ assert p3[8] == '\x03'
+ #
+ self.switch(1)
+ stm_read(p9)
+ assert p9[8] == '\t'
+ #
+ self.switch(1)
+ stm_read(p8)
+ assert p8[8] == '\x08'
+ stm_write(p8)
+ p8[8] = 'g'
+ #
+ self.switch(1)
+ stm_read(p8)
+ assert p8[8] == 'g'
+ #
+ self.switch(2)
+ stm_read(p5)
+ assert p5[8] == '\xfa'
+ stm_write(p5)
+ p5[8] = '\x86'
+ #
+ self.switch(2)
+ stm_read(p6)
+ assert p6[8] == '\x06'
+ #
+ self.switch(1)
+ stm_read(p4)
+ assert p4[8] == '\xb2'
+ stm_write(p4)
+ p4[8] = '\xce'
+ #
+ self.switch(2)
+ stm_read(p2)
+ assert p2[8] == 'T'
+ stm_write(p2)
+ p2[8] = 'Q'
+ #
+ self.switch(1)
+ stm_stop_transaction(True) #8
+ # conflict: 0xdf0a8028
+ #
+ self.switch(2)
+ stm_stop_transaction(False) #9
+ # ['\x00', '*', 'Q', '\x03', '\x0c', '\x86', '\x06', '\x07', '\x08',
'\t']
+ # log: [2, 5]
+ #
+ self.switch(0)
+ stm_read(p0)
+ assert p0[8] == '\x00'
+ #
+ self.switch(1)
+ stm_start_transaction()
+ stm_read(p3)
+ assert p3[8] == '\x03'
+ #
+ self.switch(1)
+ stm_read(p5)
+ assert p5[8] == '\x86'
+ #
+ self.switch(2)
+ stm_start_transaction()
+ stm_read(p4)
+ assert p4[8] == '\x0c'
+ stm_write(p4)
+ p4[8] = '{'
+ #
+ self.switch(1)
+ stm_read(p2)
+ assert p2[8] == 'Q'
+ #
+ self.switch(2)
+ stm_read(p3)
+ assert p3[8] == '\x03'
+ stm_write(p3)
+ p3[8] = 'V'
+ #
+ self.switch(1)
+ stm_stop_transaction(False) #10
+ # ['\x00', '*', 'Q', '\x03', '\x0c', '\x86', '\x06', '\x07', '\x08',
'\t']
+ # log: []
+ #
+ self.switch(1)
+ stm_start_transaction()
+ stm_read(p7)
+ assert p7[8] == '\x07'
+ #
+ self.switch(2)
+ stm_read(p0)
+ assert p0[8] == '\x00'
+ stm_write(p0)
+ p0[8] = 'P'
+ #
+ self.switch(0)
+ stm_stop_transaction(False) #11
diff --git a/c5/test/test_random.py b/c5/test/test_random.py
new file mode 100644
--- /dev/null
+++ b/c5/test/test_random.py
@@ -0,0 +1,85 @@
+from support import *
+import sys, random
+
+
+class TestRandom(BaseTest):
+
+ def test_fixed_16_bytes_objects(self):
+ rnd = random.Random(1010)
+
+ N_OBJECTS = 10
+ N_THREADS = 3
+ print >> sys.stderr, 'stm_start_transaction()'
+ stm_start_transaction()
+ plist = [stm_allocate(16) for i in range(N_OBJECTS)]
+ read_sets = [{} for i in range(N_THREADS)]
+ write_sets = [{} for i in range(N_THREADS)]
+ active_transactions = {}
+
+ for i in range(N_OBJECTS):
+ print >> sys.stderr, 'p%d = stm_allocate(16)' % i
+ for i in range(N_OBJECTS):
+ print >> sys.stderr, 'p%d[8] = %r' % (i, chr(i))
+ plist[i][8] = chr(i)
+ head_state = [[chr(i) for i in range(N_OBJECTS)]]
+ commit_log = []
+ print >> sys.stderr, 'stm_stop_transaction(False)'
+ stm_stop_transaction(False)
+
+ for i in range(N_THREADS):
+ print >> sys.stderr, 'self.switch(%d)' % i
+ self.switch(i)
+ stop_count = 1
+
+ for i in range(10000):
+ n_thread = rnd.randrange(0, N_THREADS)
+ print >> sys.stderr, '#\nself.switch(%d)' % n_thread
+ self.switch(n_thread)
+ if n_thread not in active_transactions:
+ print >> sys.stderr, 'stm_start_transaction()'
+ stm_start_transaction()
+ active_transactions[n_thread] = len(commit_log)
+
+ action = rnd.randrange(0, 7)
+ if action < 6:
+ is_write = action >= 4
+ i = rnd.randrange(0, N_OBJECTS)
+ print >> sys.stderr, "stm_read(p%d)" % i
+ stm_read(plist[i])
+ got = plist[i][8]
+ print >> sys.stderr, "assert p%d[8] ==" % i,
+ my_head_state = head_state[active_transactions[n_thread]]
+ prev = read_sets[n_thread].setdefault(i, my_head_state[i])
+ print >> sys.stderr, "%r" % (prev,)
+ assert got == prev
+ #
+ if is_write:
+ print >> sys.stderr, 'stm_write(p%d)' % i
+ stm_write(plist[i])
+ newval = chr(rnd.randrange(0, 256))
+ print >> sys.stderr, 'p%d[8] = %r' % (i, newval)
+ plist[i][8] = newval
+ read_sets[n_thread][i] = write_sets[n_thread][i] = newval
+ else:
+ src_index = active_transactions.pop(n_thread)
+ conflict = False
+ for i in range(src_index, len(commit_log)):
+ for j in commit_log[i]:
+ if j in read_sets[n_thread]:
+ conflict = True
+ print >> sys.stderr, "stm_stop_transaction(%r) #%d" % (
+ conflict, stop_count)
+ stop_count += 1
+ stm_stop_transaction(conflict)
+ #
+ if not conflict:
+ hs = head_state[-1][:]
+ for i, newval in write_sets[n_thread].items():
+ hs[i] = newval
+ assert plist[i][8] == newval
+ head_state.append(hs)
+ commit_log.append(write_sets[n_thread].keys())
+ print >> sys.stderr, '#', head_state[-1]
+ print >> sys.stderr, '# log:', commit_log[-1]
+ write_sets[n_thread].clear()
+ read_sets[n_thread].clear()
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
