Roy

Created originally on Bitbucket by Anonymous

Changesets for this Pull Request have not been imported, because it had been already declined on Bitbucket. Marked as closed by the import user.

• Document the progress

• Remove this tag, documented explicitly in README.txt.

• Document this flag

• Comments

• Start importing "c3/gcpage".

• Copy some more code from c3.

• Next test

• Next test

• Move to the test runner a general fix for thread-order problems.

• Next test

• Next test

• Next test

• Mention this.

• Copy and adapt more code and a test.

• Next test: link again all tx_descriptors in a chained list (duh, and I still cannot get chained list manipulations bug-free the first time)

• next test passes

• Next test

• Next test, and the simplest fix so far: move a "#if 0" one line.

• update_next_threshold()

• Next test

• Port more code, next test passes.

• Next test

• Next test

• passes

• minor stuff and a multi_thread test that still fails

• Update

• Skip this again. Moved the problematic iteration into its own test.

• Can't assert this

• Remove a bogus assert: it's possible that older, protected objects were stolen in parallel.

• Fix

• add demo2 (bubble sort)

• first random-test version in C. may have some bugs..

• demo_random: thread locals -> thread descriptor

• demo_random: remove ambiguous naming

• Check that the test passes if written this way, retrying up to 1000 times for stm_read_barrier() to return the same pointer.

• demo_random: more checks

• add more stm_normalize_stolen_objects where needed

• Revert a part of 9507e1b05a3c: it's not the first time I mess this up. Add a comment.

• Revert changes, checked in by accident

• Unsure here

• Copy from c3: mark_prebuilt_roots()

• Next test and implementation

• No, it's fine

• Re-add this check here: in the current version 'stolen_objects' should really be empty at the shut-down of a thread

• progress

• gcpage: private_from_protected

• In inevitable transactions, clear the list_of_read_objects when collecting, rather than fixing it.

• Run the spinloop up to 1'000'000 times, it seems that 1'000 times is not enough...

• The next test is complete I think, but leads to unexpected aborts

• in-progress

• Pass this test

• minor changes

• work in progress

• doesn't crash

• intermediate backup before rewrite

• amazingly seems to not crash..

• minor changes

• Running major collections in test_random starts to work.

• mark some paths with assert(0) because they don't seem to be reached in demo_random.c

• fix tests and remove some of the assert(0), as they at least seem to be hit in tests

• fix issue when HAS_ID flag gets removed

  • updated demo_random

• add simple tests

• Two tests and two fixes.

• Fixes probably (but the tests fail a bit unpredictably...)

• More asserts. The next issue is that we need to reset GCFLAG_VISITED on stubs (and free unused stubs, too).

• Reset this to False in the check-in version until it passes more reliably.

• Simplify the allocation of stubs, at the cost of ~9/10th of a pointer :-) For now it's good enough. We'll try later to compress one or two pointer fields off some objects.

• Fix the test to avoid a thread-order-dependent failure.

• After a major GC, make sure the other threads abort if the major GC found that they should.

• Fix in the test: allow for other threads that want to abort us after a major gc.

• typo

• demo_random shows another livelock with this spinloop. Added it to the comment, revert again to always abort.

• Next issue

• Fix

• Fix

• This XXX is fine now, as stubs are no longer in specially allocated pieces of memory.

• Add http://bitbucket.org/arigo/duhton

• Tweak the compilation.

• in-progress

• in-progress

• add some comments; add hash_mangling

• add multiple thread start/finish to demo_random

• Add a comment about dead threads.

• move to the current issue

• remove assert

• fix

• more tests

• Fix

• add support for predefined hash in prebuilt objects

• Two extras passing tests

• add demo_random as a test

• Bah, it was only missing this

• Next small issue with the test

• 200 random tests pass again.

• add hash to demo_random, crashes sometimes..

• Replace fprintf(stderr, ...) with dprintf((...)), which is turned off if _GC_DEBUG is not defined. Now the "build-demo*" executables are incredibly fast --- almost all the time was spent printing this debug stuff.

• Give different seeds to each thread.

• Adapt mangle_hash() to its docstring and always return different results for different arguments. (So it may now give negative results too.)

• Tweak mangle_hash() to be only called from stm_hash(), not stm_id()

• Add an XXX

• Give a 3rd compilation mode, "release", which disables even the asserts. (The gain in speed is inconsistent.)

• Use stm_pointer_equal().

• in-progress

• do not use backup as shadow-original, always use additional shadow

• stm_id cleanups and fixes

• in-progress

• Progress

• clean only used part of nursery

• Fix Du_Types[]

• fixes fixes

• Generalize the tuple's stmcb_size()

• fix validation of priv_from_prot

• break the huge switch in demo_random

• Sanity checks

• Add debugging checks.

• Fix again (or attempt to) this case...

• Copy this test from c3.

• Untested, checked in in case it's needed later

• Starting on allocating big objects (larger than 36 words)

• Clean up sweep_pages()

• Finish support for big objects (missing: LARGE objects, the ones too big for the nursery)

• Divide the nursery into sections that are cleared incrementally, like in minimark.py. This gives a code reorganization that makes it easy to implement the real goal: stm_allocate() of objects that are very large (here defined as "more than one section large").

• Start to fix the tests

• Fix this test

• Duh, the default values need to be multiples of 135168.

• The 'clear_section_count' was broken: it was never different than GC_NURSERY_SECTION. Try to fix it another way.

• Improve the previous hack.

• Fixes

• Return a boolean, not a revision_t.

• Update

• Tweak

• Progress

• Redo the thread-local object.

• Fix threadlocals.

• Implement transactions (incomplete so far)

• Fix

• Adapt the tests to the large amount of stderr output

• Add tons of debugging support, found where I forgot the save/restore.

• Finish the tests, which all pass now. Yay!

• Add a longer version

• Finish transaction.c

• Optimize

• Test and fix

• The original test showing the problem fixed in c43233de7f0e.

• Passing tests.

• Add a test for the gcptrlist_insert(&d->old_objects_to_trace) after stmgcpage_malloc()

• Tests, asserts, and fixes for stm_allocate() returning correctly cleared memory.

• Updates

• Re-add counting reads

• Redo the hack about END_MARKERs in the shadowstack.

• Port here the changes done to test_random.

• Tests for should_break_transaction() and set_transaction_length().

• stm_atomic().

• add major collections to test

• fix uninitialized shadowstack problem during major collection

• Add asserts

• add atomic transactions in demo_random

• Avoids doing this (I fixed the nursery to always really be null-allocated)

• Fix(?) the logic, I believe, and remove the recursion; but demo_random crashes. To investigate.

• More fixes

• in-progress

• in-progress

• Fix: we must explicitly keep the property that L->h_revision==R that some pairs in public_to_private have got.

• stm_enter_callback_call(), for possibly-recursive invocations

• add build and release versions of demo_random to tests

• this assert can fail

• add stm_thread_local_obj to demo_random.c

• Add more checks

• Bah?? No clue. Move -lrt at the end of the gcc invocation, for pleasing gcc on tannit.

• Fix a hard bug.

• add _GC_DEBUGPRINTS, comments, and some fairly untested code about tracing h_original in major_collections

• refactor keeping alive the h_originals in major collections

• add test and fix

• fix also the duhton target

• Make some use of command-line parameters. Very ad-hoc, but works for now

• fix: don't trace stubs

• Do we need to trace at all? The tests pass like this

• Typo

• Kill the undolog. It was done for the purpose of thread-local refs, but now this uses 'old_thread_local_obj' playing the role of a one-item undolog.

• Move the stm_hash/stm_id/stm_pointer_equal to a new file, extra.c, whose purpose is to contain "non-core" things offered in stmgc.h.

• Start to copy the abortinfo from pypy's stm-gc-2's rpyintf.c.

• In-progress

• Test and pass with integers

• Unsigned

• Strings

• NULL

• Read the latest version of an object inside the aborting transaction.

• Use a more ad-hoc string variant

• Officialize stm_abort_and_retry()

• Add stm_{minor,major}_collect() with the semantics needed for the users.

• Test and fix for stm_pointer_equal with null pointers

• add division

• fix division

• add a benchmark walking trees that are global and read-only

• Another example (that unfortunately segfaults)

• fix

• backout 840ac0a8867a, demo/trees2.duh seems to crash without tracing

• repeat/do write barrier after minor_collection. I think the problem was that minor_collect clears old_objects_to_trace and the object needs to be reregistered there if it is modified again.

• A test that fails. Maybe should fail, waiting for arigato's OK

• change / to - so we can run it on older duhton

• implement cons

• implement pair?

• fix pair and use it in tree demos

• fix writing to write-ready objects after a minor collection

• add cache of writeables to demo_random.c and fix a bug

• Test '/'

• untabiffy

• Improve the test: check that pair? really evaluates its argument

• improve demo_random

• A branch to implement weakref support (as small immutable objects only, like needed by PyPy)

• Starting

• A weakref-kept-alive test

• Weakrefs to old objects

• fix one bug and use a "big stub" in case it is also needed as the h_original of an object

• Potential bug: stmgc_size() can return a number smaller than needed for a stub.

• new approach doing the work of copying over h_original in visit()

• update comment

• uncomment jumping forward in visit() again

• use NURSERY_MOVED instead of ~OLD when copying an object over its original during major collections

• rename GCFLAG_NURSERY_MOVED to GCFLAG_MOVED

• In-progress: move the weakref code in its own file, and start writing logic for major collections.

• Weakrefs in major collections. Tests are a bit light here given that there are a lot of possible corner cases.

• try to add weakrefs to demo_random.c

• implementing immutables and trying to fix the stealing of weakrefs

• typo that doesn't change much

• clean it up a bit

• and there was a bug in demo_random

• Comment

• add stm_dbg_get_hdr_str() that prints the flags and tid of an object

• Avoid doing changes in this debug-only function

• An extra test, with explanation

• Add comments about the barrier placement

• more debug output

• Backed out changeset: 191c168da60e (readding of objects during minor collections to old_objects_to_trace)

• more backout

• demo_random should not use the writeables cache anymore, since that is invalid again

• add another test that passes, not sure why

• understand and fix tests

• a bit of documentation

• magically make it work (we shouldn't run over list_of_read_objects after a major collection decided to partially fix it (or not at all))

• Kill this attempted test. I now belive that mark_private_from_protected() would always result in the young private_from_protected objects having the GCFLAG_WRITE_BARRIER eventually added.

• Add a comment that finally settles my mind

• Tweak the code for the case of a stub in h_original (tested by run #931 of test_more_multi_thread)

• Expand the explanation

• Add a (temporary?) flag for debugging, and found out that sometimes we do get a small stub at the wrong place (gcpage:copy_over_original)

• Bah, no

• Current status: fails here

• In-progress: refactor gcpage.visit() and related code

• Some fixes

• Fix the test

• More fixes in the tests

• More test fixes

• in-progress

• Fix

• Use the dbgmem.c logic for the shadowstack too

• in-progress

• Found the source of the bug

• Fix (argh), by adding a reasonable assert, and fix all tests to pass this condition.

• More fixes.

• Experimental: during major collection, find out private/protected objects that point to public objects with a most recent version that is also private/protected by the same thread. In this case we can replace the pointer with a direct pointer.

• fix tests

• Make two flags: VISITED vs MARKED. See doc in et.h.

• Fix test

• Fix the assert

• Remove a memcpy() which is not needed any more, I believe

• Fix.

• Fix test

• Fix (probably, but it seems confirmed by the fact that test_random doesn't complain about unexpected aborts)

• Two extra passing tests

• I think this is necessary, but I don't manage to write a test

• hg backout 5c385b2b629a: it's still needed

• Increase the size, now that the shadowstacks are also allocated via dbgmem.c

• All tests pass including test_zdemo_random now.

• Set the debugging flag SMALLSTUB if we allocated a small stub here.

• I think that by now stm_pointer_equal() can be done more simply, without needing to get the stm_id().

• Fix the strange error of the debugging mprotect() calls by simply running the example for less long.

  http://stackoverflow.com/questions/17896297/mprotect-does-not-always-collapse-adjacent-lines-in-proc-pid-maps

• Print 'Test OK!' when exiting normally, to be sure

• "static inline" functions are not quite as good as macros. gcc seems to inline the functions partially only.

• Better code this way

• add stm_clear_on_abort

• Implement the repeat read barrier (actually mostly just expose it to the user, with a fast-path logic).

• stm_immut_read_barrier()

• stm_repeat_write_barrier()

• stm_pointer_equal_prebuilt()

• Fix warnings

• Forgot that d->abortinfo also contains gc ptrs

• implement stm_allocate_public_integer_address(). They need to be explicitely unregistered (freed), otherwise they survive everything.

• fix embarrassing bug

• other test

• Probably doesn't change anything, but you never know

• add debug print

• another bug with h_original :(

• Add the first nice checkfence demo with a minimal stm.

  Add the 'howto-checkfence' from arigo/arigo, complete it with how to run the demo.

• Increase the value of LOCKED. For some reason too large values increase the run-time significantly, but at least 99 is large enough for practical purposes here.

• Updates

• Yet another kind of barrier.

• Conditionally compile counters for the slow- and fast-path of all barriers.

• Duh, the point is to always print the results if compiled in.

• Close branch about to be merged

• Add a passing test

• Subtle bug and fix: v_atomic should not be re-read just before CommitTransaction, because the latter can still abort.

• A passing test

• Kill v_atomic. After any abort, reset the "atomic" flag to 0, because we're anyway then resuming from a transaction start. This happens to fix a crash on pypy-stm, but I didn't manage to write a test here...

• Fix a bug found by running PyPy (graphwalktest.py, which I will check in together with other test files I'm writing).

• stm_decode_abort_info: the current hack for strings doesn't really work. Need to think about a different one...

• fix wrong assumption about h_revision of stubs

• stubs should have a thread assigned to them

• clear MARKED flag too

• remove size parameter in stm_free and introduce new _GC_MEMPROTECT define to enable the use of mprotect to find invalid accesses

• in don't use zones when not _GC_MEMPROTECT

• Add stm_dump_dbg(), maybe useful for debugging with gdb

• if atomic and inevitable, don't change reads_size_limit_nonatomic

• extra asserts

• fix assert

• Tweak

• fix test and GC_MEMPROTECT

• fix old protected immutables that need stubs

• Skip these two tests for now.

• failing test for weakref

• fix test by tracing the weakptr in weakrefs manually when stealing

• in-progress trying to fix weakrefs. still get a freed weakptr on an existing weakref

• more work, still not correct

• FINALLY

• Another test that the pushed abort_info objects are kept alive

• Even more complications in the decoding of abort info: move the (missing-so-far) stm_read_barrier() later, during the call to stm_inspect_abort_info().

• Add a passing test for stm_clear_on_abort()

• stm_clear_on_abort(): move the thread-local variables into the tx_descriptor structure.

  Add stm_call_on_abort() for invoking callbacks (like free()) if the current transaction is aborted.

• Ignore callbacks if we're outside a transaction or in an inevitable transaction (which cannot abort)

• Skip this assert, after discussion with Remi.

• Move 'd->active = 0' a bit earlier. This should be enough to ensure the new comment.

• I think this is what is needed

• Support non-aligned keys in g2l_insert(), as needed for stm_call_on_abort().

• Print the full name of the abort reason

• Add abort and inevitable fprinting to stmgc too for now

• in-progress: API for the pypy jit, with support for a custom implementation of setjmp/longjmp.

• Fix running test_zdemo_random, at least on some Linuxes where too many mprotect() eventually fail.

• Fix message

• Hackish but simple: add here the call to stm_begin_transaction().

• Add asserts, tweak debug prints

• remove copy-paste left-over

• make thread_descriptor accessible to pypy

• make nursery_current, nursery_nextlimit and active real thread-locals

• fix wrong assert

• make allocate_public_integer_address use the h_original (not always allocate stubs) if it is already public

• fastpaths for stm_pointer_equal(_prebuilt)

• add a constant to disable the madvise() nursery clearing for use with valgrind

• implement stm_stop_all_other_threads() and stm_partial_commit_and_resume_other_threads()

• fix impersonating the other thread when forcing minor collections in other threads. also use the direct thread locals in some places (for better or worse).

• allow nesting of stm_stop_all_other_threads()-stm_partial_commit_and_resume_other_threads() pairs

• more asserts and a just-to-be-sure change that affects performance a bit

• fix some debug assert

• fix public ints (usage of public h_originals is not always right, they need to be PREBUILT_ORIGINALs to be sure...)

• document the real reason why we can't use just any h_original and prevent things like stub->stub->stub on public addresses.

• more asserts and fix the case when start_exclusivelock() returns in a transaction that needs to abort (same as after stm_start_sharedlock())

• fix possible races for minor collections that look at possibly locked, global objects

• finally reproduce crash as a testcase

• fix failing case from last commit by purging objects from aborted transactions from old_objects_to_trace

• fix bug in demo_random.c

• The "c7" version, based on clang's "%gs" prefix and Linux's remap_file_pages() in a way that should avoid any large and repeated overheads.

• Initial checkin of the code from https://bitbucket.org/arigo/arigo/raw/default/hack/stm/c7

• Comments

• tweaks

• Initial draft of this document, based on similar drafts from c5 and c6 but for c7.

• Draft the GC paragraph.

• Updates

• Use checkfence to check a particular lockfree subalgorithm used in c7/core.c

• Check both the x86 version and the general version.

• progress

• in-progress

• start adding a nursery and redo barriers without the leader-model

• add tests

• address conversion functions

• first allocs working

• re-implement thread switching

• stop_transaction hacking for tests

• simple tests

• stm_alloc_old

• tests

• try introducing safe-points

• start doing minor collections

• Add some asserts

• fix test

• extend test

• fix and add a failing test

• push modified objs to other threads

• test for tracing objects

• fix test

• adapt testing framework

• fix and add tests

• changes in testing framework and fix

• failing abort cleanup test

• partially implement aborting

• indentation

• small fix

• fix race condition in abort

• Bug fixed by previous checkin

• The basic test_random passes, yuhuu

• Kill old entries in test_bug

• add demo2 and remove stuff

• Bunch the swap_nodes

• small optimization moving the resetting of objects on abort outside of shared-lock

• reducing number of aborts by sleeping

• add spinlock implementation of reader-writer lock

• makefile update

• add files...

• in-progress

• getting closer

• tweaks

• fixes until minimal.duh works

• fix warning

• fix

• push limit even higher

• add some safepoint somewhere

• pushing some roots in duhton and reset shadowstack on abort

• Workarounds to avoid a bug of clang

• add a valgrind target to the makefile

• add a test that fills the nursery

• allocation of large objs < nursery_size

• failing test for writing to 2nd page of an object

• fix some page flags

• fix privatization of pages in write-barrier slowpath

• add failing test for partially uncommitted pages / uncommitted objects

• change test, still failing

• make test pass

• add and fix test

• some cleanup and a fix

• small comment

• WIP separate object allocation from the rest

• move a bit of the page management to its own file

• move some more code

• move the global lock to an extra file "stmsync"

• update demo makefile

• update duhton makefile

• simple page-reuse for aborted transactions

• do minor collections before acquiring the exclusive lock on commit

• add largemalloc and fix its tests

• use only largemalloc to allocate old objects

• fixes, all tests seem to pass

• update hgignore

• small fix

• re-introduce the alloc-pages for small-sized allocations (3x faster in simple duhton bench).

• remove some read barriers from duhton in case the field that is read is actually immutable (hopefully)

• remove some more barriers

• add a new demo (sorting) and implement some more operators

• fix bugs in the nursery

• test and fix for writing to old objects which are already writeable for us

• fix possible bug in duhton

• fix more possible bugs in duhton

• finally fix a missing save/restore in lst_append

• WIP: implement run-transactions in duhton

• implement inevitable transactions

• remove bogus assert; change some limits for sort.duh to work; implement 'time' builtin in duhton

• try to implement more general safe-points. not sure if successful

• add a mode to duhton that removes read-barriers and makes write-barriers like normal GC write-barriers. Meaning there is no conflict detection going on and all pages will be SHARED at all times. There are still the start/stop_transaction calls left but their influence can be reduced by the program.

• over-allocate lists

• lower the nursery size again

• allocate big objects directly outside of the nursery

• some more debug output

• WIP: allow for arbitrary number of pthreads using fixed number of thread segments. first test with duhton works

• add a teardown_pthread function to free the shadow stack

• little things

• update demo2

• minor changes

• small performance improvements thanks to cache-line alignment of locks (thanks kirma)

• performance: not always do a safe-point in stm_allocate() (still missing a way to request it though)

• simple n-queens demo for duhton

• add parallel version of n-queens

• fix missing read-barrier in duhton

• implement requesting of safe-points and older-transaction-succeeds in write-write conflicts

• small changes

• Try to be extra careful around the "lock" in nursery_current

• add a comment

• another comment

• Use __sync_synchronize() as a general fall-back. Update comments.

• Mention other OSes

• A branch to refactor c7.

• Start a refactoring step. Goal: the user program includes only "stmgc.h", and compiles only "stmgc.c".

• progress

• in-progress

• in-progress

• in-progress

• Rename "region" -> "segment".

• in-progress

• in-progress

• Enough to pass the first test.

• Align nursery sections

• in-progress

• fixing some more tests

• Next test passes.

• Replace stm_allocate_prebuilt() with stm_copy_prebuilt_objects() which is probably a better fit for PyPy.

• Two days to convince myself that this version of stm_write() gives the best trade-offs

• More prebuilt stuff from two days ago. Might get changed soon.

• Rename "stm_current_transaction_t" into "stm_creation_marker_t".

• Comments

• Fix

• Fixes

• in-progress

• in-progress

• in-progress

• In-progress: redoing the page privatization

• Copy the complete logic for _stm_write_slowpath()

• Resetting the creation markers between transactions

• Fixes, and issues

• Mutex and condition variable: the winning combo for writing reasonable code. I keep rediscovering how they are actually a good idea. Maybe later we'll figure out that we need more control to avoid spurious wake-ups, but I think that with low numbers of threads it's fine.

• in-progress

• Mostly compilation fixes

• Progress

• Port some more tests

• Pass test_abort_cleanup.

• creation_markers need to distinguish between current-transaction objects inside or outside the nursery, otherwise _stm_write_slowpath() is never going to be called for the latter

• Fix the GCFLAG_WRITE_BARRIER_CALLED when committing

• Update tests

• At transaction start, align the current_nursery and set creation markers

• Add a passing test

• Medium-size allocations from the nursery

• Tweak

• Oups, can't call this after releasing the mutex, as a different thread might get hold of our segment.

• Carefully synchronize the threads in order to run a minor collection

• in-progress

• Some more comments and figuring out that a particular point is not problematic after all

• Compilation fixes

• in-progress

• Add a passing test

• Fix things until test_commit_fresh_objects3 fails, as it was supposed to.

• Introduce GCFLAG_SMALL_UNIFORM to replace GCFLAG_CROSS_PAGE, which cannot work because even small nursery objects may cross two pages.

• Clarifications

• Fix the bug pointed out by test_commit_fresh_objects3

• Next test passes

• Fix or move away tests, and implement _stm_become_inevitable(). Now test_basic passes.

• new test-random

• Comments about v_nursery_section_end

• fix for contention_management calling cond_wait in tests

• more info in output

• Comments

• Adapt demo2.c.

• _pages_privatize() with count > 1

• Move the demo2.c in the new "demo" subdirectory. It works :-)

• Workaround for llvm bug. :-/

• Comment

• Silence a specific warning in release builds: 'unused function xyz'

• Add an LLVM patch. It might not be needed on simple examples, but I fear that it will be needed to compile large programs.

• In case of abort, restore explicitly the position of the shadowstack.

• A test for 44b81083d7cf.

• Make and run "demo2" in a test.

• more info in test_random output

• add objects with refs to test_random

• use SOME_MEDIUM_SIZE and SOME_LARGE_SIZE constants to allocate objects -> fails currently

• also randomly allocate number of refs per object (no effects so far)

• add explicit aborts to test_random

• comments for test_random

• Add dprintf from stmgc/c4.

• Getting started on duhton (nothing done so far)

• intermediate check-in, progressing in gcpage

• in-progress

• reset various markers at the end of nursery collection

• Implement this relatively easy optimization

• improvements and fixes for test_random

• write to the end of the objects, since that is more likely to fail (cross-page objects)

• up the limit of nb of refs

• cleanups

• tweaks and disable LARGE_SIZE objs for now

• add unused OpMinorCollect

• add colors to test_random

• Fix: found out how we are really supposed to get fresh zero-mapped pages in an mmap. The answer is simply to call mmap(MAP_FIXED) again.

• Kill old tests, fix test_demo.

• add stm_become_inevitable to random tests

• Simplify code here: this call to contention_management() cannot lead to a safe-point, after all.

• cleanups

• more cleanups in test_random

• keep track of object sizes and assert them sometimes

• save roots around self.switch() too

• Progress on copying the logic from minimark.py.

• Re-share the nursery pages after a minor collection

• Tweaks

• A first real test for nursery collection. Fails

• Fixes for the test.

• Next test passes

• Failing test

• In-progress: another refactoring simplifying various things, after discovering that we can after all run a minor collection after each transaction... At least running about 30'000 opcodes in PyPy consumes typically 400 KB of nursery, and lowering the nursery size from 4 MB down to 400 KB has only a 1.5% performance impact.

• Reimplement the _stm_write_slowpath().

• Tweaks

• untested additions to test_random.py

• progress

• switch from classes to functions because...

• Refactor the next test

• next few tests

• some cleanup

• enable assertion of modified objects

• Better debug prints. Fix next test.

• fix next test

• Fix tests, next one is real.

• synchronize_overflow_object_now().

• test_basic passes again

• Update demo2.c, but it still fails probably because of a core bug

• Passing test

• no MEDIUM_SIZE anymore

• fix

• Add the shadowstack

• Forgot to set 'overflow_number' when doing a non-commit-time nursery collection

• Fix _has_mutex() to actually work if there are several threads running

• Fix non-debug compilation

• in-progress

• Unify overflow_objects_pointing_to_nursery and old_objects_pointing_to_nursery: unless I'm wrong, we can merge the two lists.

• fix the test that now passes.

• fix test

• tweaks

• Phew. I think that by now this model with several condition variables should, ideally, work.

• Skip these two tests, see message

• Throw away the nursery upon abort

• Fixes.

• All of test_random.py passes

• Fix test_largemalloc.

• Use stm_fatalerror() here too

• Copy the dictionary-like trees from "c4".

• Use the trees to implement young_outside_nursery, step 1.

• Actually implement surviving young_outside_nursery

• Refactoring and small fix

• In trees, the NULL key is reserved

• add very large objects

• Fix: memset the right segment

• add demo_random.c

• fix abort_if_needed

• fix for race condition (see comment in pages.h for PRIVATE_PAGE)

• I think that with a REMAPPING_PAGE intermediate value it becomes simply this.

• Add a debugging check that fails right now if we run more than 2 threads

• Add *_no_abort() versions for cond_wait() and mutex_lock(). Needed if we don't have our own segment so far.

• extend demo_random with some objects of different sizes

• move shadow stack init/done to setup.c

• The tree data structure can explode when fed non-aligned addresses. Assert that they are aligned and fix the tests.

• start adapting duhton

• Move stuff around: this removes one check on each object.

• Workaround for another llvm bug

• lists can move

• Remove this gross hack, and reintroduce the loop: if longjmp() is called, make sure we redo the setjmp()

• Move this logic in common.py, otherwise when running only test_list.py the C files are not rebuilt

• Kill this logic and comment; no longer applies.

• (arigo, Remi) missing: preventing a transaction from starting in inevitable mode if there is already an inevitable transaction running

• close branch

• Close branch, ready to be merged

• Do we really need this?

• Only acquire the mutex_pages_lock if there are really objects to free

• Readd logic for a thread-local object.

  Helps "duhton demo/list_transaction.duh", but it still seems to be caught sometimes in infnite loops.

• Fix the big slowness that duhton's list_transaction sometimes shows.

• Fix comments (only, for now)

• Update the README document to reflect the current status. Add a TODO.

• comment fixes

• Start adapting test_gcpage

• Kill SP_SAFE_POINT_CANNOT_COLLECT.

• A Makefile to run all *.duh files, or to measure their run-time

• Keep track of how much memory we're using

• detail

• Remove old files

• become_inevitable(): was missing resetting jmpbuf_ptr to NULL

• Start laying out the logic invoking major collections at the right time.

• Improve the logic behind stm_collect(1)

• Add a comment: think more

• Step 1 is to force minor collections to occur in all segments.

• Fix

• First simplification step: unify all condition variables into one, again. Should fix obscure synchronization bugs that are theoretically possible at least with more than two threads.

• More tweaks

• Reintroduce mulitple condition variables, but this time in a more controlled fashion. In theory, let's say the code becomes clearer to follow and it's easier to check its correctness. We'll see in practice (done refactoring, some bugs left).

• Fix the last issue for the tests

• Add a space for clarity

• The first test about major gc passes.

• Next test

• Test that largemalloc_sweep() works as expected; start to work on recording modified objects

• A passing test

• Small refactoring

• in-progress. still a bug left

• Fix, but a failing test.

• in-progress

• Fixes until all tests seem to pass.

• Unify the two hacks to check that memory is correctly zeroed.

• Done major GC

• Remove outdated comments. Kill the call to reset_transaction_read_version_prebuilt().

• Add a missing thing about the major gc

• Coment out this function here too.

• In-progress: resharing of pages. Doesn't work right now, so is not enabled.

• Progress, but still disabled because I got one crash in duhton

• I could get a crash only once, and not in gdb, so I've no clue if it's related to this or not at all --- likely not.

• Add "gil-c7", a small file that presents the same API to programs but is implemented with a GIL. It contains the minor collector but no major collector.

• Start stm_setup_prebuilt()

• Finish prebuilt.c, according to its test (which I forgot to check-in earlier)

• Add passing tests

• Ah, I knew there was a bug.

• Shrink the init_prebuilt_xxx functions by using stm_setup_prebuilt(). Yay.

• Update TODO

• add a #define to disable re-sharing of pages

• Fix (from demo/demo_random): needs to check more directly if we use 'overflow_number' or not. Otherwise a badly placed major collection can run minor_collect(commit=false) in this transaction.

• Turn this to 0 again for now; occasionally segfaults in demo_random.

• fix _release of demo_random

• Add a TODO item

• The various places that fill with 0xDD bytes should not all use the same pattern.

• Useful addition for gdb

• More tweaks

• Baaah thanks Remi. Missing locks here.

• some comments and re-enable RESHARE_PAGES

• More comments. Remove a line that is actually useless. Change the value we overwrite stm_large_free chunks with. Fix a test.

• Refactor the contention management. Now become_inevitable is also a case of contention (in this case, for the right to be inevitable). Contention managers can choose to pause the running thread too.

• Clarify this assert

• Add an assert

• Small refactoring to avoid the step that clears the write locks first.

• This belongs together with 732edc0f0e90

• Bug fix

• It seems to get much more likely to crash with a lower value here

• Goes together with dacc33d175bf to make the crash more likely: a lower nursery size.

• Still debugging, I think it's safer to set this to 0 for now

• A final clean-up round of bug fixes. Now demo_random seems to pass again.

• Extra comment

• Missing one potential root inside the major gc tracing.

• Copying the hash/id logic from minimark.py, first part

• Update TODO

• Forgot to add in 8185ee16c279

• Finish copying the shadow logic from pypy.

• done

• test hash/id in demo_random

• use real prebuilts in demo_random

• a more randomness in allocation sizes

• add inevitable transactions to the mix

• we should free those lists too in abort_data_structures_from_segment_num

• fix gil-c7 with prebuilt objs

• Add stm_can_move().

• Small additions for pypy

• Protect this header

• also do minor-collects on commit in gil-c7 (otherwise we see young objs in other transactions that suddenly disappear)

• Use "long" here, like the result type of stm_hash().

• Clear bytes of raw memory on abort

• Implementation and test for stm_call_on_abort().

• PyPy calls stm_call_on_abort() even outside transactions.

• Bah. Avoid patching the built-in objects. It's probably a good idea not to, but the issue right now is that some objects are really only 8 bytes long, even if stmcb_size says it must be at least 16.

• Add last_abort__bytes_in_nursery.

• stm_is_inevitable(), and fix tests for inevitable transactions

• Tweak: expose this logic for pypy

• Add an assert to prevent double-starting transactions

• start adding weakref support

• fix

• more tests

• fix cleanup on abort

• another test

• consider major collections

• more tests

• fix some multi-threading issues

• fix the test, still passes

• fix some other test and its failure by adding some synchronize_overflow_object_now(). Maybe there is a better solution

• some cleanup

• better documentation

• fix use of STM_SEGMENT during major collections

• simplify code by assuming sizeof(weakref) == 16

• make functions static

• Created new branch roy