Author: Armin Rigo <ar...@tunes.org>
Branch: c7-refactor
Changeset: r867:e6d52f7b3ef1
Date: 2014-02-26 14:13 +0100
http://bitbucket.org/pypy/stmgc/changeset/e6d52f7b3ef1/
Log: The tree data structure can explode when fed non-aligned addresses.
Assert that they are aligned and fix the tests.
diff --git a/c7/stm/list.c b/c7/stm/list.c
--- a/c7/stm/list.c
+++ b/c7/stm/list.c
@@ -54,23 +54,23 @@
static void tree_free(struct tree_s *tree)
{
free(tree->raw_start);
+ assert(memset(tree, 0xDD, sizeof(struct tree_s)));
free(tree);
}
static void _tree_compress(struct tree_s *tree)
{
- wlog_t *item;
- struct tree_s tree_copy;
- memset(&tree_copy, 0, sizeof(struct tree_s));
+ wlog_t *item;
+ struct tree_s tree_copy;
+ memset(&tree_copy, 0, sizeof(struct tree_s));
- TREE_LOOP_FORWARD(*tree, item)
- {
- tree_insert(&tree_copy, item->addr, item->val);
+ TREE_LOOP_FORWARD(*tree, item) {
+ tree_insert(&tree_copy, item->addr, item->val);
} TREE_LOOP_END;
- free(tree->raw_start);
- *tree = tree_copy;
+ free(tree->raw_start);
+ *tree = tree_copy;
}
static wlog_t *_tree_find(char *entry, uintptr_t addr)
@@ -122,6 +122,7 @@
static void tree_insert(struct tree_s *tree, uintptr_t addr, uintptr_t val)
{
assert(addr != 0); /* the NULL key is reserved */
+ assert(!(addr & (sizeof(void *) - 1))); /* the key must be aligned */
retry:;
wlog_t *wlog;
uintptr_t key = addr;
@@ -129,6 +130,7 @@
char *p = (char *)(tree->toplevel.items);
char *entry;
while (1) {
+ assert(shift < TREE_DEPTH_MAX * TREE_BITS);
p += (key >> shift) & TREE_MASK;
shift += TREE_BITS;
entry = *(char **)p;
diff --git a/c7/stm/list.h b/c7/stm/list.h
--- a/c7/stm/list.h
+++ b/c7/stm/list.h
@@ -138,6 +138,7 @@
continue; \
if (((long)_entry) & 1) \
{ /* points to a further level: enter it */ \
+ assert(_stackp - _stack < TREE_DEPTH_MAX); \
_stackp->next = _next; \
_stackp->end = _end; \
_stackp++; \
diff --git a/c7/test/test_list.py b/c7/test/test_list.py
--- a/c7/test/test_list.py
+++ b/c7/test/test_list.py
@@ -65,34 +65,34 @@
def test_tree_add():
t = lib.tree_create()
- lib.tree_insert(t, 23, 456)
- for i in range(100):
- assert lib.tree_contains(t, i) == (i == 23)
+ lib.tree_insert(t, 23000, 456)
+ for i in range(0, 100000, 1000):
+ assert lib.tree_contains(t, i) == (i == 23000)
lib.tree_free(t)
def test_tree_is_cleared():
t = lib.tree_create()
assert lib.tree_is_cleared(t)
- lib.tree_insert(t, 23, 456)
+ lib.tree_insert(t, 23000, 456)
assert not lib.tree_is_cleared(t)
lib.tree_free(t)
def test_tree_delete_item():
t = lib.tree_create()
- lib.tree_insert(t, 23, 456)
- lib.tree_insert(t, 42, 34289)
+ lib.tree_insert(t, 23000, 456)
+ lib.tree_insert(t, 42000, 34289)
assert not lib.tree_is_cleared(t)
- assert lib.tree_contains(t, 23)
- res = lib.tree_delete_item(t, 23)
+ assert lib.tree_contains(t, 23000)
+ res = lib.tree_delete_item(t, 23000)
assert res
- assert not lib.tree_contains(t, 23)
- res = lib.tree_delete_item(t, 23)
+ assert not lib.tree_contains(t, 23000)
+ res = lib.tree_delete_item(t, 23000)
assert not res
- res = lib.tree_delete_item(t, 21)
+ res = lib.tree_delete_item(t, 21000)
assert not res
assert not lib.tree_is_cleared(t)
- assert lib.tree_contains(t, 42)
- res = lib.tree_delete_item(t, 42)
+ assert lib.tree_contains(t, 42000)
+ res = lib.tree_delete_item(t, 42000)
assert res
assert not lib.tree_is_cleared(t) # not cleared, but still empty
for i in range(100):
@@ -101,18 +101,18 @@
def test_tree_walk():
t = lib.tree_create()
- lib.tree_insert(t, 23, 456)
- lib.tree_insert(t, 42, 34289)
+ lib.tree_insert(t, 23000, 456)
+ lib.tree_insert(t, 42000, 34289)
a = ffi.new("uintptr_t[10]")
res = lib.test_tree_walk(t, a)
assert res == 2
- assert a[0] == 23
- assert a[1] == 42
+ assert ((a[0] == 23000 and a[1] == 42000) or
+ (a[0] == 42000 and a[1] == 23000))
lib.tree_free(t)
def test_tree_walk_big():
t = lib.tree_create()
- values = [random.randrange(0, 1000000) for i in range(300)]
+ values = random.sample(xrange(0, 1000000, 8), 300)
for x in values:
lib.tree_insert(t, x, x)
a = ffi.new("uintptr_t[1000]")
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
