Author: Armin Rigo <ar...@tunes.org>
Branch: hashtable
Changeset: r1485:083635ad2834
Date: 2014-10-31 11:33 +0100
http://bitbucket.org/pypy/stmgc/changeset/083635ad2834/
Log: in-progress: enough to pass the tests, but more testing needed
diff --git a/c7/stm/hashtable.c b/c7/stm/hashtable.c
--- a/c7/stm/hashtable.c
+++ b/c7/stm/hashtable.c
@@ -158,7 +158,8 @@
}
}
-static stm_hashtable_entry_t *_stm_hashtable_lookup(stm_hashtable_t *hashtable,
+static stm_hashtable_entry_t *_stm_hashtable_lookup(object_t *hashtableobj,
+ stm_hashtable_t *hashtable,
uintptr_t index)
{
stm_hashtable_table_t *table;
@@ -220,19 +221,29 @@
item in the current table.
*/
if (rc > 6) {
- char *p =
allocate_outside_nursery_large(sizeof(stm_hashtable_entry_t));
- entry = (stm_hashtable_entry_t *)(p - stm_object_pages);
+ if (_is_from_same_transaction(hashtableobj)) {
+ entry = (stm_hashtable_entry_t *)
+ stm_allocate(sizeof(stm_hashtable_entry_t));
+ entry->userdata = stm_hashtable_entry_userdata;
+ entry->index = index;
+ entry->object = NULL;
+ }
+ else {
+ char *p = allocate_outside_nursery_large(
+ sizeof(stm_hashtable_entry_t));
+ entry = (stm_hashtable_entry_t *)(p - stm_object_pages);
- long j;
- for (j = 0; j <= NB_SEGMENTS; j++) {
- struct stm_hashtable_entry_s *e = (struct stm_hashtable_entry_s *)
- REAL_ADDRESS(get_segment_base(j), entry);
- e->header.stm_flags = GCFLAG_WRITE_BARRIER;
- e->userdata = stm_hashtable_entry_userdata;
- e->index = index;
- e->object = NULL;
+ long j;
+ for (j = 0; j <= NB_SEGMENTS; j++) {
+ struct stm_hashtable_entry_s *e;
+ e = (struct stm_hashtable_entry_s *)
+ REAL_ADDRESS(get_segment_base(j), entry);
+ e->header.stm_flags = GCFLAG_WRITE_BARRIER;
+ e->userdata = stm_hashtable_entry_userdata;
+ e->index = index;
+ e->object = NULL;
+ }
}
-
write_fence(); /* make sure 'entry' is fully initialized here */
table->items[i] = entry;
write_fence(); /* make sure 'table->items' is written here */
@@ -242,13 +253,15 @@
else {
/* if rc is smaller than 6, we must allocate a new bigger table.
*/
- uintptr_t biggercount = (table->mask + 1) * 2;
+ uintptr_t biggercount = table->mask + 1;
if (biggercount < 50000)
+ biggercount *= 4;
+ else
biggercount *= 2;
size_t size = (offsetof(stm_hashtable_table_t, items)
+ biggercount * sizeof(stm_hashtable_entry_t *));
stm_hashtable_table_t *biggertable = malloc(size);
- assert(biggertable);
+ assert(biggertable); // XXX
table->resize_counter = (uintptr_t)biggertable;
/* unlock, but put the new table, so IS_EVEN() is still true */
@@ -265,7 +278,7 @@
}
biggertable->resize_counter = rc;
- write_fence(); /* make sure as well that 'biggertable' is valid here;
+ write_fence(); /* make sure that 'biggertable' is valid here,
and make sure 'table->resize_counter' is updated
('table' must be immutable from now on). */
VOLATILE_HASHTABLE(hashtable)->table = biggertable;
@@ -273,17 +286,34 @@
}
}
-object_t *stm_hashtable_read(stm_hashtable_t *hashtable, uintptr_t index)
+object_t *stm_hashtable_read(object_t *hashtableobj, stm_hashtable_t
*hashtable,
+ uintptr_t index)
{
- stm_hashtable_entry_t *e = _stm_hashtable_lookup(hashtable, index);
+ stm_hashtable_entry_t *e = _stm_hashtable_lookup(hashtableobj, hashtable,
+ index);
stm_read((object_t *)e);
return e->object;
}
-void stm_hashtable_write(stm_hashtable_t *hashtable, uintptr_t index,
- object_t *nvalue)
+void stm_hashtable_write(object_t *hashtableobj, stm_hashtable_t *hashtable,
+ uintptr_t index, object_t *nvalue)
{
- stm_hashtable_entry_t *e = _stm_hashtable_lookup(hashtable, index);
+ stm_hashtable_entry_t *e = _stm_hashtable_lookup(hashtableobj, hashtable,
+ index);
stm_write((object_t *)e);
e->object = nvalue;
}
+
+void stm_hashtable_tracefn(stm_hashtable_t *hashtable, void trace(object_t **))
+{
+ stm_hashtable_table_t *table;
+ table = VOLATILE_HASHTABLE(hashtable)->table;
+
+ uintptr_t j, mask = table->mask;
+ for (j = 0; j <= mask; j++) {
+ stm_hashtable_entry_t **pentry = &table->items[j];
+ if (*pentry != NULL) {
+ trace((object_t **)pentry);
+ }
+ }
+}
diff --git a/c7/stm/nursery.c b/c7/stm/nursery.c
--- a/c7/stm/nursery.c
+++ b/c7/stm/nursery.c
@@ -44,6 +44,10 @@
tree_contains(STM_PSEGMENT->young_outside_nursery, (uintptr_t)obj));
}
+static inline bool _is_from_same_transaction(object_t *obj) {
+ return _is_young(obj) || IS_OVERFLOW_OBJ(STM_PSEGMENT, obj);
+}
+
long stm_can_move(object_t *obj)
{
/* 'long' return value to avoid using 'bool' in the public interface */
diff --git a/c7/stmgc.h b/c7/stmgc.h
--- a/c7/stmgc.h
+++ b/c7/stmgc.h
@@ -536,9 +536,11 @@
typedef struct stm_hashtable_s stm_hashtable_t;
stm_hashtable_t *stm_hashtable_create(void);
void stm_hashtable_free(stm_hashtable_t *);
-object_t *stm_hashtable_read(stm_hashtable_t *, uintptr_t key);
-void stm_hashtable_write(stm_hashtable_t *, uintptr_t key, object_t *nvalue);
+object_t *stm_hashtable_read(object_t *, stm_hashtable_t *, uintptr_t key);
+void stm_hashtable_write(object_t *, stm_hashtable_t *, uintptr_t key,
+ object_t *nvalue);
extern uint32_t stm_hashtable_entry_userdata;
+void stm_hashtable_tracefn(stm_hashtable_t *, void (object_t **));
/* ==================== END ==================== */
diff --git a/c7/test/support.py b/c7/test/support.py
--- a/c7/test/support.py
+++ b/c7/test/support.py
@@ -169,11 +169,15 @@
typedef struct stm_hashtable_s stm_hashtable_t;
stm_hashtable_t *stm_hashtable_create(void);
void stm_hashtable_free(stm_hashtable_t *);
-object_t *stm_hashtable_read(stm_hashtable_t *, uintptr_t key);
-bool _check_hashtable_read(stm_hashtable_t *, uintptr_t key);
+bool _check_hashtable_read(object_t *, stm_hashtable_t *, uintptr_t key);
object_t *hashtable_read_result;
-bool _check_hashtable_write(stm_hashtable_t *, uintptr_t key, object_t
*nvalue);
+bool _check_hashtable_write(object_t *, stm_hashtable_t *, uintptr_t key,
+ object_t *nvalue);
uint32_t stm_hashtable_entry_userdata;
+void stm_hashtable_tracefn(stm_hashtable_t *, void (object_t **));
+
+void _set_hashtable(object_t *obj, stm_hashtable_t *h);
+stm_hashtable_t *_get_hashtable(object_t *obj);
""")
@@ -251,14 +255,15 @@
object_t *hashtable_read_result;
-bool _check_hashtable_read(stm_hashtable_t *h, uintptr_t key)
+bool _check_hashtable_read(object_t *hobj, stm_hashtable_t *h, uintptr_t key)
{
- CHECKED(hashtable_read_result = stm_hashtable_read(h, key));
+ CHECKED(hashtable_read_result = stm_hashtable_read(hobj, h, key));
}
-bool _check_hashtable_write(stm_hashtable_t *h, uintptr_t key, object_t
*nvalue)
+bool _check_hashtable_write(object_t *hobj, stm_hashtable_t *h, uintptr_t key,
+ object_t *nvalue)
{
- CHECKED(stm_hashtable_write(h, key, nvalue));
+ CHECKED(stm_hashtable_write(hobj, h, key, nvalue));
}
#undef CHECKED
@@ -289,6 +294,20 @@
return *WEAKREF_PTR(obj, size);
}
+void _set_hashtable(object_t *obj, stm_hashtable_t *h)
+{
+ stm_char *field_addr = ((stm_char*)obj);
+ field_addr += SIZEOF_MYOBJ; /* header */
+ *(stm_hashtable_t *TLPREFIX *)field_addr = h;
+}
+
+stm_hashtable_t *_get_hashtable(object_t *obj)
+{
+ stm_char *field_addr = ((stm_char*)obj);
+ field_addr += SIZEOF_MYOBJ; /* header */
+ return *(stm_hashtable_t *TLPREFIX *)field_addr;
+}
+
void _set_ptr(object_t *obj, int n, object_t *v)
{
long nrefs = (long)((myobj_t*)obj)->type_id - 421420;
@@ -317,7 +336,14 @@
ssize_t stmcb_size_rounded_up(struct object_s *obj)
{
struct myobj_s *myobj = (struct myobj_s*)obj;
+ assert(myobj->type_id != 0);
if (myobj->type_id < 421420) {
+ if (myobj->type_id == 421419) { /* hashtable */
+ return sizeof(struct myobj_s) + 1 * sizeof(void*);
+ }
+ if (myobj->type_id == 421418) { /* hashtable entry */
+ return 8 * 3;
+ }
/* basic case: tid equals 42 plus the size of the object */
assert(myobj->type_id >= 42 + sizeof(struct myobj_s));
assert((myobj->type_id - 42) >= 16);
@@ -337,6 +363,17 @@
{
int i;
struct myobj_s *myobj = (struct myobj_s*)obj;
+ if (myobj->type_id == 421419) {
+ /* hashtable */
+ stm_hashtable_t *h = *((stm_hashtable_t **)(myobj + 1));
+ stm_hashtable_tracefn(h, visit);
+ return;
+ }
+ if (myobj->type_id == 421418) {
+ /* hashtable entry */
+ object_t **ref = ((object_t **)myobj) + 2;
+ visit(ref);
+ }
if (myobj->type_id < 421420) {
/* basic case: no references */
return;
@@ -355,6 +392,8 @@
{
int i;
struct myobj_s *myobj = (struct myobj_s*)obj;
+ assert(myobj->type_id != 421419);
+ assert(myobj->type_id != 421418);
if (myobj->type_id < 421420) {
/* basic case: no references */
return;
@@ -425,7 +464,7 @@
CARD_SIZE = lib._STM_CARD_SIZE # 16b at least
NB_SEGMENTS = lib.STM_NB_SEGMENTS
FAST_ALLOC = lib._STM_FAST_ALLOC
-lib.stm_hashtable_entry_userdata = 42 + HDR + 2 * 8
+lib.stm_hashtable_entry_userdata = 421418
class Conflict(Exception):
pass
@@ -463,6 +502,18 @@
lib._set_weakref(o, point_to_obj)
return o
+def stm_allocate_hashtable():
+ o = lib.stm_allocate(16)
+ tid = 421419
+ lib._set_type_id(o, tid)
+ h = lib.stm_hashtable_create()
+ lib._set_hashtable(o, h)
+ return o
+
+def get_hashtable(o):
+ assert lib._get_type_id(o) == 421419
+ return lib._get_hashtable(o)
+
def stm_get_weakref(o):
return lib._get_weakref(o)
diff --git a/c7/test/test_hashtable.py b/c7/test/test_hashtable.py
--- a/c7/test/test_hashtable.py
+++ b/c7/test/test_hashtable.py
@@ -3,112 +3,118 @@
import py
-class StmHashTable(object):
- def __init__(self):
- self.h = lib.stm_hashtable_create()
+def htget(o, key):
+ h = get_hashtable(o)
+ res = lib._check_hashtable_read(o, h, key)
+ if res:
+ raise Conflict
+ return lib.hashtable_read_result
- def free(self):
- lib.stm_hashtable_free(self.h)
-
- def __getitem__(self, key):
- res = lib._check_hashtable_read(self.h, key)
- if res:
- raise Conflict
- return lib.hashtable_read_result
-
- def __setitem__(self, key, nvalue):
- res = lib._check_hashtable_write(self.h, key, nvalue)
- if res:
- raise Conflict
+def htset(o, key, nvalue):
+ h = get_hashtable(o)
+ res = lib._check_hashtable_write(o, h, key, nvalue)
+ if res:
+ raise Conflict
class TestHashtable(BaseTest):
def test_empty(self):
self.start_transaction()
- h = StmHashTable()
+ h = stm_allocate_hashtable()
for i in range(100):
index = random.randrange(0, 1<<64)
- got = h[index]
+ got = htget(h, index)
assert got == ffi.NULL
- h.free()
def test_set_value(self):
self.start_transaction()
- h = StmHashTable()
+ h = stm_allocate_hashtable()
lp1 = stm_allocate(16)
- h[12345678901] = lp1
- assert h[12345678901] == lp1
+ htset(h, 12345678901, lp1)
+ assert htget(h, 12345678901) == lp1
for i in range(64):
index = 12345678901 ^ (1 << i)
- assert h[index] == ffi.NULL
- assert h[12345678901] == lp1
- h.free()
+ assert htget(h, index) == ffi.NULL
+ assert htget(h, 12345678901) == lp1
def test_no_conflict(self):
- h = StmHashTable()
lp1 = stm_allocate_old(16)
lp2 = stm_allocate_old(16)
#
self.start_transaction()
+ h = stm_allocate_hashtable()
+ self.push_root(h)
stm_set_char(lp1, 'A')
- h[1234] = lp1
+ htset(h, 1234, lp1)
self.commit_transaction()
#
self.start_transaction()
+ h = self.pop_root()
stm_set_char(lp2, 'B')
- h[9991234] = lp2
+ htset(h, 9991234, lp2)
#
self.switch(1)
self.start_transaction()
- lp1b = h[1234]
+ lp1b = htget(h, 1234)
+ assert lp1b != ffi.NULL
assert stm_get_char(lp1b) == 'A'
assert lp1b == lp1
self.commit_transaction()
#
self.switch(0)
- assert h[9991234] == lp2
+ assert htget(h, 9991234) == lp2
assert stm_get_char(lp2) == 'B'
- assert h[1234] == lp1
- h[1234] = ffi.NULL
+ assert htget(h, 1234) == lp1
+ htset(h, 1234, ffi.NULL)
self.commit_transaction()
- h.free()
def test_conflict(self):
- h = StmHashTable()
lp1 = stm_allocate_old(16)
lp2 = stm_allocate_old(16)
#
self.start_transaction()
- h[1234] = lp1
+ h = stm_allocate_hashtable()
+ self.push_root(h)
+ self.commit_transaction()
+ #
+ self.start_transaction()
+ h = self.pop_root()
+ self.push_root(h)
+ htset(h, 1234, lp1)
#
self.switch(1)
self.start_transaction()
- py.test.raises(Conflict, "h[1234] = lp2")
+ py.test.raises(Conflict, "htset(h, 1234, lp2)")
def test_keepalive_minor(self):
- h = StmHashTable()
self.start_transaction()
+ h = stm_allocate_hashtable()
+ self.push_root(h)
lp1 = stm_allocate(16)
stm_set_char(lp1, 'N')
- h[1234] = lp1
+ htset(h, 1234, lp1)
stm_minor_collect()
- lp1b = h[1234]
+ h = self.pop_root()
+ lp1b = htget(h, 1234)
assert lp1b != ffi.NULL
assert stm_get_char(lp1b) == 'N'
assert lp1b != lp1
def test_keepalive_major(self):
- h = StmHashTable()
lp1 = stm_allocate_old(16)
#
self.start_transaction()
+ h = stm_allocate_hashtable()
+ self.push_root(h)
stm_set_char(lp1, 'N')
- h[1234] = lp1
+ htset(h, 1234, lp1)
self.commit_transaction()
#
self.start_transaction()
stm_major_collect()
- lp1b = h[1234]
+ h = self.pop_root()
+ self.push_root(h)
+ lp1b = htget(h, 1234)
assert lp1b == lp1
assert stm_get_char(lp1b) == 'N'
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
