Author: Remi Meier
Branch:
Changeset: r1097:e43e756ae446
Date: 2014-03-26 18:21 +0100
http://bitbucket.org/pypy/stmgc/changeset/e43e756ae446/
Log: initial HTM version
diff --git a/duhton/Makefile b/duhton/Makefile
--- a/duhton/Makefile
+++ b/duhton/Makefile
@@ -25,5 +25,13 @@
clang -DSTM_DEBUGPRINT -pthread -g -DDu_DEBUG -o duhton_debug_nostm *.c
../gil-c7/stmgc.c -Wall -DUSE_GIL -ferror-limit=1
+duhton_htm: *.c *.h ../htm-c7/stmgc.? ../htm-c7/htm.h
+ clang -pthread -g -DNDEBUG -O2 -o duhton_htm *.c ../htm-c7/stmgc.c
-Wall -DUSE_HTM
+
+
+duhton_debug_htm: *.c *.h ../htm-c7/stmgc.? ../htm-c7/htm.h
+ clang -DSTM_DEBUGPRINT -pthread -g -DDu_DEBUG -o duhton_debug_htm *.c
../htm-c7/stmgc.c -Wall -DUSE_HTM -ferror-limit=1
+
+
clean:
rm -f duhton duhton_debug duhton_release
diff --git a/duhton/duhton.h b/duhton/duhton.h
--- a/duhton/duhton.h
+++ b/duhton/duhton.h
@@ -6,11 +6,16 @@
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
+
#ifdef USE_GIL
# include "../gil-c7/stmgc.h"
#else
+#ifdef USE_HTM
+# include "../htm-c7/stmgc.h"
+#else
# include "../c7/stmgc.h"
#endif
+#endif
extern __thread stm_thread_local_t stm_thread_local;
diff --git a/gil-c7/stmgc.h b/gil-c7/stmgc.h
--- a/gil-c7/stmgc.h
+++ b/gil-c7/stmgc.h
@@ -11,6 +11,8 @@
#define TLPREFIX /* nothing */
+#define STM_NB_SEGMENTS 4
+
typedef struct { /* empty */ } stm_jmpbuf_t;
diff --git a/htm-c7/htm.h b/htm-c7/htm.h
new file mode 100644
--- /dev/null
+++ b/htm-c7/htm.h
@@ -0,0 +1,73 @@
+#ifndef _HTM_H
+#define _HTM_H
+
+#include <stdio.h>
+#include <assert.h>
+#include <pthread.h>
+
+
+
+#define XBEGIN_OK (~0)
+#define XBEGIN_UNKNOWN (0)
+#define XBEGIN_XABORT (1 << 0)
+#define XBEGIN_MAYBE_RETRY (1 << 1)
+#define XBEGIN_NORMAL_CONFLICT (1 << 2)
+#define XBEGIN_BUFFER_OVERFLOW (1 << 3)
+#define XBEGIN_DEBUG (1 << 4)
+#define XBEGIN_NESTED_ABORT (1 << 5)
+#define XBEGIN_XABORT_ARG(x) (((x) >> 24) & 0xFF)
+
+static __thread char buf[128];
+char* xbegin_status(int status)
+{
+ if (status == XBEGIN_OK)
+ snprintf(buf, 128, "OK");
+ else if (status == XBEGIN_UNKNOWN)
+ snprintf(buf, 128, "UNKNOWN");
+ else if (status & XBEGIN_XABORT)
+ snprintf(buf, 128, "XABORT(%d)", XBEGIN_XABORT_ARG(status));
+ else if (status & XBEGIN_MAYBE_RETRY)
+ snprintf(buf, 128, "MAYBE_RETRY");
+ else if (status & XBEGIN_NORMAL_CONFLICT)
+ snprintf(buf, 128, "NORMAL_CONFLICT");
+ else if (status & XBEGIN_BUFFER_OVERFLOW)
+ snprintf(buf, 128, "BUFFER_OVERFLOW");
+ else if (status & XBEGIN_DEBUG)
+ snprintf(buf, 128, "DEBUG");
+ else if (status & XBEGIN_NESTED_ABORT)
+ snprintf(buf, 128, "NESTED_ABORT");
+ return buf;
+}
+
+static __attribute__((__always_inline__)) inline int xbegin()
+{
+ int result = XBEGIN_OK;
+ asm volatile(".byte 0xC7, 0xF8; .long 0" : "+a" (result) :: "memory");
+ return result;
+}
+
+static __attribute__((__always_inline__)) inline void xend()
+{
+ asm volatile(".byte 0x0F, 0x01, 0xD5" ::: "memory");
+}
+
+#define xabort(argument) do { asm volatile(".byte 0xC6, 0xF8, %P0" :: "i"
(argument) : "memory"); } while (0);
+
+
+
+static __attribute__((__always_inline__)) inline int xtest()
+{
+ unsigned char result;
+ asm volatile(".byte 0x0F, 0x01, 0xD6; setnz %0" : "=r" (result) ::
"memory");
+ return result;
+}
+
+
+static __attribute__((__always_inline__)) inline int
mutex_locked(pthread_mutex_t* mut)
+{
+ return !!mut->__data.__lock;
+}
+
+
+
+#endif
diff --git a/htm-c7/stmgc.c b/htm-c7/stmgc.c
new file mode 100644
--- /dev/null
+++ b/htm-c7/stmgc.c
@@ -0,0 +1,402 @@
+#include "stmgc.h"
+#include <string.h>
+#include <stdio.h>
+#include "htm.h"
+
+pthread_mutex_t _stm_gil = PTHREAD_MUTEX_INITIALIZER;
+stm_thread_local_t *_stm_tloc;
+struct stm_segment_info_s _stm_segment;
+
+
+
+
+static void acquire_gil(stm_thread_local_t *tl) {
+ if (pthread_mutex_lock(&_stm_gil) == 0) {
+ _stm_tloc = tl;
+ return;
+ }
+ abort();
+}
+
+void stm_start_inevitable_transaction(stm_thread_local_t *tl) {
+ if (mutex_locked(&_stm_gil)) {
+ acquire_gil(tl);
+ return;
+ }
+
+ int status;
+ transaction_retry:
+ if ((status = xbegin()) == XBEGIN_OK) {
+ if (mutex_locked(&_stm_gil))
+ xabort(0);
+ /* transaction OK */
+ }
+ else {
+ if (mutex_locked(&_stm_gil))
+ acquire_gil(tl);
+ else if (status & (XBEGIN_MAYBE_RETRY | XBEGIN_NORMAL_CONFLICT))
+ goto transaction_retry;
+ else
+ acquire_gil(tl);
+ }
+
+ _stm_tloc = tl;
+}
+
+void stm_commit_transaction(void) {
+ stm_collect(0);
+ _stm_tloc = NULL;
+ if (mutex_locked(&_stm_gil)) {
+ assert(!xtest());
+ if (pthread_mutex_unlock(&_stm_gil) != 0) abort();
+ } else {
+ xend();
+ }
+}
+
+
+
+
+
+
+/************************************************************/
+
+struct list_s {
+ uintptr_t count;
+ uintptr_t last_allocated;
+ uintptr_t items[];
+};
+
+static struct list_s *list_create(void);
+
+static inline void list_free(struct list_s *lst)
+{
+ free(lst);
+}
+
+#define LIST_FREE(lst) (list_free(lst), (lst) = NULL)
+
+
+static struct list_s *_list_grow(struct list_s *, uintptr_t);
+
+static inline struct list_s *list_append(struct list_s *lst, uintptr_t item)
+{
+ uintptr_t index = lst->count++;
+ if (UNLIKELY(index > lst->last_allocated))
+ lst = _list_grow(lst, index);
+ lst->items[index] = item;
+ return lst;
+}
+
+#define LIST_APPEND(lst, e) ((lst) = list_append((lst), (uintptr_t)(e)))
+
+
+__attribute__((unused))
+static inline void list_clear(struct list_s *lst)
+{
+ lst->count = 0;
+}
+
+static inline bool list_is_empty(struct list_s *lst)
+{
+ return (lst->count == 0);
+}
+
+__attribute__((unused))
+static inline uintptr_t list_count(struct list_s *lst)
+{
+ return lst->count;
+}
+
+static inline uintptr_t list_pop_item(struct list_s *lst)
+{
+ assert(lst->count > 0);
+ return lst->items[--lst->count];
+}
+
+__attribute__((unused))
+static inline uintptr_t list_item(struct list_s *lst, uintptr_t index)
+{
+ return lst->items[index];
+}
+
+__attribute__((unused))
+static inline void list_set_item(struct list_s *lst, uintptr_t index,
+ uintptr_t newitem)
+{
+ lst->items[index] = newitem;
+}
+
+#define LIST_FOREACH_R(lst, TYPE, CODE) \
+ do { \
+ struct list_s *_lst = (lst); \
+ uintptr_t _i; \
+ for (_i = _lst->count; _i--; ) { \
+ TYPE item = (TYPE)_lst->items[_i]; \
+ CODE; \
+ } \
+ } while (0)
+
+#define LIST_SETSIZE(n) (sizeof(struct list_s) + LIST_ITEMSSIZE(n))
+#define LIST_ITEMSSIZE(n) ((n) * sizeof(uintptr_t))
+#define LIST_OVERCNT(n) (33 + ((((n) / 2) * 3) | 1))
+
+static struct list_s *list_create(void)
+{
+ uintptr_t initial_allocation = 32;
+ struct list_s *lst = malloc(LIST_SETSIZE(initial_allocation));
+ if (lst == NULL)
+ abort();
+
+ lst->count = 0;
+ lst->last_allocated = initial_allocation - 1;
+ return lst;
+}
+
+static struct list_s *_list_grow(struct list_s *lst, uintptr_t nalloc)
+{
+ nalloc = LIST_OVERCNT(nalloc);
+ lst = realloc(lst, LIST_SETSIZE(nalloc));
+ if (lst == NULL)
+ abort();
+
+ lst->last_allocated = nalloc - 1;
+ return lst;
+}
+
+/************************************************************/
+
+#define GCFLAG_WRITE_BARRIER _STM_GCFLAG_WRITE_BARRIER
+
+static struct list_s *objects_pointing_to_nursery;
+static struct list_s *young_weakrefs;
+
+void stm_setup(void)
+{
+ objects_pointing_to_nursery = list_create();
+ young_weakrefs = list_create();
+}
+
+void stm_teardown(void)
+{
+ list_free(objects_pointing_to_nursery);
+}
+
+void _stm_write_slowpath(object_t *obj)
+{
+ obj->gil_flags &= ~GCFLAG_WRITE_BARRIER;
+ LIST_APPEND(objects_pointing_to_nursery, obj);
+}
+
+object_t *_stm_allocate_old(ssize_t size)
+{
+ char *p = malloc(size);
+ assert(p);
+ memset(p, 0, size);
+ ((object_t *)p)->gil_flags = _STM_GCFLAG_WRITE_BARRIER;
+ return (object_t *)p;
+}
+
+object_t *_stm_allocate_external(ssize_t size)
+{
+ char *p = malloc(size);
+ assert(p);
+ memset(p, 0, size);
+ _stm_write_slowpath((object_t *)p);
+ return (object_t *)p;
+}
+
+/************************************************************/
+
+
+#define NB_NURSERY_PAGES 1024 // 4MB
+#define NURSERY_SIZE (NB_NURSERY_PAGES * 4096UL)
+
+char *_stm_nursery_base = NULL;
+char *_stm_nursery_current = NULL;
+char *_stm_nursery_end = NULL;
+#define _stm_nursery_start ((uintptr_t)_stm_nursery_base)
+
+static bool _is_in_nursery(object_t *obj)
+{
+ return ((char *)obj >= _stm_nursery_base &&
+ (char *)obj < _stm_nursery_end);
+}
+
+long stm_can_move(object_t *obj)
+{
+ return _is_in_nursery(obj);
+}
+
+#define GCWORD_MOVED ((object_t *) -42)
+
+static void minor_trace_if_young(object_t **pobj)
+{
+ object_t *obj = *pobj;
+ object_t *nobj;
+
+ if (obj == NULL)
+ return;
+
+ if (_is_in_nursery(obj)) {
+ /* If the object was already seen here, its first word was set
+ to GCWORD_MOVED. In that case, the forwarding location, i.e.
+ where the object moved to, is stored in the second word in 'obj'. */
+ object_t *TLPREFIX *pforwarded_array = (object_t *TLPREFIX *)obj;
+
+ if (pforwarded_array[0] == GCWORD_MOVED) {
+ *pobj = pforwarded_array[1]; /* already moved */
+ return;
+ }
+
+ /* We need to make a copy of this object.
+ */
+ size_t size = stmcb_size_rounded_up(obj);
+
+ nobj = malloc(size);
+ assert(nobj);
+
+ /* Copy the object */
+ memcpy(nobj, obj, size);
+
+ /* Done copying the object. */
+ //dprintf(("\t\t\t\t\t%p -> %p\n", obj, nobj));
+ pforwarded_array[0] = GCWORD_MOVED;
+ pforwarded_array[1] = nobj;
+ *pobj = nobj;
+ }
+
+ else {
+ /* The object was not in the nursery at all */
+ return;
+ }
+
+ /* Must trace the object later */
+ LIST_APPEND(objects_pointing_to_nursery, nobj);
+}
+
+static void collect_roots_in_nursery(void)
+{
+ object_t **current = _stm_tloc->shadowstack;
+ object_t **base = _stm_tloc->shadowstack_base;
+ while (current-- != base) {
+ minor_trace_if_young(current);
+ }
+ minor_trace_if_young(&_stm_tloc->thread_local_obj);
+}
+
+static inline void _collect_now(object_t *obj)
+{
+ assert(!_is_in_nursery(obj));
+
+ /* We must not have GCFLAG_WRITE_BARRIER so far. Add it now. */
+ assert(!(obj->gil_flags & GCFLAG_WRITE_BARRIER));
+ obj->gil_flags |= GCFLAG_WRITE_BARRIER;
+
+ /* Trace the 'obj' to replace pointers to nursery with pointers
+ outside the nursery, possibly forcing nursery objects out and
+ adding them to 'objects_pointing_to_nursery' as well. */
+ stmcb_trace(obj, &minor_trace_if_young);
+}
+
+static void collect_oldrefs_to_nursery(void)
+{
+ struct list_s *lst = objects_pointing_to_nursery;
+
+ while (!list_is_empty(lst)) {
+ object_t *obj = (object_t *)list_pop_item(lst);
+
+ _collect_now(obj);
+
+ /* the list could have moved while appending */
+ lst = objects_pointing_to_nursery;
+ }
+}
+
+static void throw_away_nursery(void)
+{
+ if (_stm_nursery_base == NULL) {
+ _stm_nursery_base = malloc(NURSERY_SIZE);
+ assert(_stm_nursery_base);
+ _stm_nursery_end = _stm_nursery_base + NURSERY_SIZE;
+ }
+
+ _stm_nursery_current = _stm_nursery_base;
+ memset(_stm_nursery_base, 0, NURSERY_SIZE);
+}
+
+#define WEAKREF_PTR(wr, sz) ((object_t * TLPREFIX *)(((char *)(wr)) + (sz) -
sizeof(void*)))
+
+static void move_young_weakrefs(void)
+{
+ LIST_FOREACH_R(
+ young_weakrefs,
+ object_t * /*item*/,
+ ({
+ assert(_is_in_nursery(item));
+ object_t *TLPREFIX *pforwarded_array = (object_t *TLPREFIX *)item;
+
+ /* the following checks are done like in nursery.c: */
+ if (pforwarded_array[0] != GCWORD_MOVED) {
+ /* weakref dies */
+ continue;
+ }
+
+ item = pforwarded_array[1]; /* moved location */
+
+ assert(!_is_in_nursery(item));
+
+ ssize_t size = 16;
+ object_t *pointing_to = *WEAKREF_PTR(item, size);
+ assert(pointing_to != NULL);
+
+ if (_is_in_nursery(pointing_to)) {
+ object_t *TLPREFIX *pforwarded_array = (object_t *TLPREFIX
*)pointing_to;
+ /* the following checks are done like in nursery.c: */
+ if (pforwarded_array[0] != GCWORD_MOVED) {
+ /* pointing_to dies */
+ *WEAKREF_PTR(item, size) = NULL;
+ continue; /* no need to remember in old_weakrefs */
+ }
+ else {
+ /* moved location */
+ *WEAKREF_PTR(item, size) = pforwarded_array[1];
+ }
+ }
+ else {
+ /* pointing_to was already old */
+ }
+ //LIST_APPEND(STM_PSEGMENT->old_weakrefs, item);
+ }));
+ list_clear(young_weakrefs);
+}
+
+void stm_collect(long level)
+{
+ /* 'level' is ignored, only minor collections are implemented */
+ collect_roots_in_nursery();
+ collect_oldrefs_to_nursery();
+ move_young_weakrefs();
+ throw_away_nursery();
+}
+
+object_t *_stm_allocate_slowpath(ssize_t size_rounded_up)
+{
+ /* run minor collection */
+ //fprintf(stderr, "minor collect\n");
+ stm_collect(0);
+
+ char *p = _stm_nursery_current;
+ char *end = p + size_rounded_up;
+ assert(end <= _stm_nursery_end);
+ _stm_nursery_current = end;
+ return (object_t *)p;
+}
+
+object_t *stm_allocate_weakref(ssize_t size_rounded_up)
+{
+ assert(size_rounded_up == 16);
+ object_t *obj = stm_allocate(size_rounded_up);
+ LIST_APPEND(young_weakrefs, obj);
+ return obj;
+}
diff --git a/htm-c7/stmgc.h b/htm-c7/stmgc.h
new file mode 100644
--- /dev/null
+++ b/htm-c7/stmgc.h
@@ -0,0 +1,152 @@
+#ifndef _STMGC_H
+#define _STMGC_H
+
+#include <stddef.h>
+#include <stdint.h>
+#include <stdbool.h>
+#include <assert.h>
+#include <unistd.h>
+#include <stdlib.h>
+#include <pthread.h>
+
+#define TLPREFIX /* nothing */
+
+#define STM_NB_SEGMENTS 4
+
+typedef struct { /* empty */ } stm_jmpbuf_t;
+
+typedef struct object_s {
+ uint32_t gil_flags;
+} object_t;
+
+typedef struct stm_thread_local_s {
+ object_t **shadowstack;
+ object_t **shadowstack_base;
+ object_t *thread_local_obj;
+ long last_abort__bytes_in_nursery;
+} stm_thread_local_t;
+
+extern stm_thread_local_t *_stm_tloc;
+extern char *_stm_nursery_current, *_stm_nursery_end;
+
+struct stm_segment_info_s {
+ stm_jmpbuf_t *jmpbuf_ptr; /* compat only -- always NULL */
+ char *nursery_current; /* compat only -- always NULL */
+};
+extern struct stm_segment_info_s _stm_segment;
+#define STM_SEGMENT (&_stm_segment)
+
+#ifdef NDEBUG
+#define OPT_ASSERT(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)
+#else
+#define OPT_ASSERT(cond) assert(cond)
+#endif
+#define UNLIKELY(x) __builtin_expect(x, false)
+
+#define _STM_GCFLAG_WRITE_BARRIER 0x01
+#define _STM_FAST_ALLOC (66*1024)
+
+
+object_t *_stm_allocate_old(ssize_t size);
+
+object_t *_stm_allocate_external(ssize_t);
+object_t *_stm_allocate_slowpath(ssize_t);
+object_t *stm_allocate_weakref(ssize_t size_rounded_up);
+
+__attribute__((always_inline))
+inline static object_t *stm_allocate(ssize_t size_rounded_up) {
+ OPT_ASSERT(size_rounded_up >= 16);
+ OPT_ASSERT((size_rounded_up & 7) == 0);
+
+ if (UNLIKELY(size_rounded_up >= _STM_FAST_ALLOC))
+ return _stm_allocate_external(size_rounded_up);
+
+ char *p = _stm_nursery_current;
+ char *end = p + size_rounded_up;
+ _stm_nursery_current = end;
+ if (UNLIKELY(end > _stm_nursery_end))
+ return _stm_allocate_slowpath(size_rounded_up);
+
+ return (object_t *)p;
+}
+
+inline static void stm_register_thread_local(stm_thread_local_t *tl) {
+ tl->thread_local_obj = NULL;
+ tl->shadowstack_base = (object_t **)malloc(768*1024);
+ assert(tl->shadowstack_base);
+ tl->shadowstack = tl->shadowstack_base;
+ tl->last_abort__bytes_in_nursery = 0;
+}
+inline static void stm_unregister_thread_local(stm_thread_local_t *tl) {
+ free(tl->shadowstack_base);
+}
+
+extern pthread_mutex_t _stm_gil;
+
+void stm_setup(void);
+void stm_teardown(void);
+void stm_collect(long level);
+
+
+void stm_start_inevitable_transaction(stm_thread_local_t *tl);
+void stm_commit_transaction(void);
+
+inline static void stm_become_inevitable(
+ stm_thread_local_t *tl, const char *msg) { }
+inline static void _stm_become_inevitable(const char *msg) { }
+inline static void stm_become_globally_unique_transaction(
+ stm_thread_local_t *tl, const char *msg) { }
+
+static inline int stm_is_inevitable(void) { return 1; }
+inline static void stm_read(object_t *ob) { }
+
+void _stm_write_slowpath(object_t *);
+
+__attribute__((always_inline))
+inline static void stm_write(object_t *ob) {
+ if (UNLIKELY(ob->gil_flags & _STM_GCFLAG_WRITE_BARRIER))
+ _stm_write_slowpath(ob);
+}
+
+inline static char *_stm_real_address(object_t *ob) { return (char *)ob; }
+static inline void stm_safe_point(void) { }
+
+#define STM_START_TRANSACTION(tl, here) do { \
+ (void)&(here); \
+ stm_start_inevitable_transaction(tl); \
+} while (0)
+
+#define STM_PUSH_ROOT(tl, p) (*((tl).shadowstack++) = (object_t *)(p))
+#define STM_POP_ROOT(tl, p) ((p) = (typeof(p))*(--(tl).shadowstack))
+#define STM_POP_ROOT_RET(tl) (*(--(tl).shadowstack))
+
+
+extern ssize_t stmcb_size_rounded_up(struct object_s *);
+extern void stmcb_trace(struct object_s *, void (object_t **));
+
+inline static object_t *stm_setup_prebuilt(object_t *preb) {
+ if (preb != NULL)
+ preb->gil_flags |= _STM_GCFLAG_WRITE_BARRIER;
+ return preb;
+}
+inline static object_t *stm_setup_prebuilt_weakref(object_t *preb) {
+ return stm_setup_prebuilt(preb);
+}
+
+inline static long stm_identityhash(object_t *obj) {
+ return (long)obj; // XXX fails after a minor collection
+}
+inline static long stm_id(object_t *obj) {
+ return (long)obj;
+}
+inline static void stm_set_prebuilt_identityhash(object_t *obj, long hash) {
+ // XXX ignored
+}
+long stm_can_move(object_t *);
+
+inline static void stm_call_on_abort(stm_thread_local_t *tl, void *key,
+ void callback(void *)) {
+ // XXX ignored
+}
+
+#endif
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
