[m-rev.] for review: stm runtime and library

[Julien Fischer]

On Wed, 26 Sep 2007, Leon Ilario MIKA wrote:

> Estimated hours taken: 8
>
> Modifcation of Software Transactional Memory runtime and library to handle
> blocking and nested STM transactions.

I suggest:

 	Support blocking and nested transactions in the STM runtime.

> runtime/mercury_stm.c
> runtime/mercury_stm.h

Add a colon after each filename.

> 	Defined condition variables for the high-level C grade.  This

s/grade/grades/

> 	is used for the scheduling of threads with blocking transactions.
> 	Such grades used POSIX condition variables for this purpose.

s/POSIX/pthreads/

> 	Added wait queues to transaction variables.  These data structures
> 	maintain a list of all threads waiting for the value of the
> 	corresponding transaction variable to change.
>
> 	Added a function to block a transaction until the value of a
> 	transaction variable has changed.

> 	Added a function which permits the merging of a transaction log
> 	with it's parent.

I suggest:

 	Add a function that merges a transaction log with that of its
 	parent.

> runtime/stm_builtin.m

That should be, library/stm_builtin.m:

> 	Added utility predicates which will assist the checking of atomic
> 	goals durring the semantic analysis and error checking phase of the

s/durring/during/ (and below).

> 	compiler.  These are automatically inserted durring the construction
> 	of the hlds and automatically removed durring the expansion of
> 	stm_goals.
>
> 	Completed the implementation of the predicate "stm_block".

...

> Index: runtime/mercury_stm.c
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_stm.c,v
> retrieving revision 1.5
> diff -u -u -r1.5 mercury_stm.c
> --- runtime/mercury_stm.c	21 Sep 2007 06:13:12 -0000	1.5
> +++ runtime/mercury_stm.c	26 Sep 2007 05:22:51 -0000
>

...

> +void
> +MR_STM_merge_transactions(MR_STM_TransLog *tlog) {
> +
> +    MR_STM_TransLog     *parent_log;
> +    MR_STM_TransRecord  *parent_current;
> +    MR_STM_TransRecord  *current;
> +    MR_STM_TransRecord  *records_to_append_to_parent;
> +    MR_bool             found_tvar_in_parent;
> +
> +    MR_assert(tlog != NULL);
> +    MR_assert(tlog->MR_STM_tl_parent != NULL);
> +
> +    parent_log = tlog->MR_STM_tl_parent;
> +
> +    current = tlog->MR_STM_tl_records;
> +    while (current != NULL) {
> +
> +        found_tvar_in_parent = MR_NO;
> +        parent_current = parent_log->MR_STM_tl_records;
> +
> +        while (parent_current != NULL) {
> +            if (current->MR_STM_tr_var == parent_current->MR_STM_tr_var) {
> +                parent_current->MR_STM_tr_new_value =
> +                    current->MR_STM_tr_new_value;
> +                found_tvar_in_parent = MR_YES;
> +                break;
> +            }
> +
> +            parent_current = parent_current->MR_STM_tr_next;
> +        }
> +
> +        if (! found_tvar_in_parent) {
> +            MR_STM_record_transaction(parent_log,
> +                    current->MR_STM_tr_var, current->MR_STM_tr_old_value,
> +                    current->MR_STM_tr_new_value);
> +        }
> +
> +        current = current->MR_STM_tr_next;
> +    }
> +
> +    /* Deallocate child log */
> +#if !defined(MR_CONSERVATIVE_GC)
> +    /* XXX -- Free tlog and log entries */
> +#endif
> +}
> +
> +void
> +MR_STM_block_thread(MR_STM_TransLog *tlog) {
> +
> +#if defined(MR_THREAD_SAFE)
> +    #if defined(MR_HIGHLEVEL_CODE)
> +        MR_STM_ConditionVar     *thread_condvar;
> +
> +        thread_condvar = MR_GC_NEW(MR_STM_ConditionVar);
> + +        MR_STM_condvar_init(thread_condvar)
> +        MR_STM_wait(tlog);
> +
> +        MR_STM_condvar_wait(tlog, MR_STM_lock);
> +
> +        MR_STM_unwait(tlog, thread_condvar);
> +        MR_STM_condvar_destroy(thread_condvar);
> +
> +        MR_GC_free(thread_condvar);
> +    #else
> +        MR_fatal_error("Low-Level backend: Not implemented");
> +    #endif
> +#else
> +    MR_fatal_error("Blocking thread in non-parallel grade");

Mention STM in these assertion messages.

> +#endif


That's not quite right because (eventually) all low-level grades
will support STM, since they all support concurrency.
It should be something like:

#if defined(MR_THREAD_SAFE) || !defined(MR_HIGHLEVEL_CODE)

 	... as above ...

#else
 	MR_fatal_error("STM: blocking in non-parallel high-level C
 		grade.");
#endif

For the first case you will need to add a bit more code that causes
an abort in low-level grades (at least for now), e.g.

 	#if !defined(MR_HIGHLEVEL_CODE)
 		MR_fatal_error(...);
 	#endif

...

> Index: runtime/mercury_stm.h
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_stm.h,v
> retrieving revision 1.5
> diff -u -u -r1.5 mercury_stm.h
> --- runtime/mercury_stm.h	17 Sep 2007 13:28:56 -0000	1.5
> +++ runtime/mercury_stm.h	25 Sep 2007 05:35:24 -0000

...

> /*
> +** The type MR_STM_ConditionVar provides an abstract method of blocking and
> +** signalling threads based on conditions.
> +*/
> +#if defined(MR_HIGHLEVEL_CODE)
> +
> +    #if defined(MR_THREAD_SAFE)
> +        typedef pthread_cond_t  MR_STM_ConditionVar;
> +
> +        #define MR_STM_condvar_init(x)        pthread_cond_init(x, NULL)
> +        #define MR_STM_condvar_wait(x, y)     pthread_cond_wait(x, y)
> +        #define MR_STM_condvar_signal(x)      pthread_cond_signal(x)

Should that not be pthread_cond_broadcast()?

> +        #define MR_STM_condvar_destroy(x)     pthread_cond_destroy(x)
> +    #else
> +        typedef MR_Integer      MR_STM_ConditionVar;
> +        /*
> +        ** Since these grades don't support concurrency, there is no
> +        ** need to block the thread. +        */
> +        #define MR_STM_condvar_init(x)
> +        #define MR_STM_condvar_wait(x, y)
> +        #define MR_STM_condvar_signal(x)
> +        #define MR_STM_condvar_destroy(x)
> +    #endif
> +



> /*
> +** Blocks a thread from execution.  This method is called by the thread
> +** which is to be blocked.  The STM lock MUST be aquired by the +** thread 
> before this method is called and acquires the lock when the thread
> +** is signalled.
> +*/
> +extern void
> +MR_STM_block_thread(MR_STM_TransLog *tlog);
> +
> +/*
> +** Merges a transaction with its parent.  Do not merge it with any
> +** other ancestors.  Aborts if the given transaction log does not have a
> +** parent.
> +*/
> +extern void
> +MR_STM_merge_transactions(MR_STM_TransLog *tlog);
> +
> +/*
> +** Reschedules all threads currently waiting on the given transaction
> +** variables.

s/variables/variable/

...


> Index: library/stm_builtin.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/library/stm_builtin.m,v
> retrieving revision 1.12
> diff -u -u -r1.12 stm_builtin.m
> --- library/stm_builtin.m	17 Sep 2007 13:28:55 -0000	1.12
> +++ library/stm_builtin.m	26 Sep 2007 05:07:44 -0000
> @@ -171,6 +171,15 @@
> :- type stm_dummy_output
>     --->    stm_dummy_output.
>
> +    % Used to enforce the uniqueness of outer and inner variables.

 	... of out and inner variables in atomic scopes.

> +    % Will be removed before stm_expansion.
> +    %
> +:- pred stm_from_outer_to_inner_io(io::di, stm::uo) is det.
> +:- pred stm_from_outer_to_inner_stm(stm::di, stm::uo) is det.
> +
> +:- pred stm_from_inner_to_outer_io(stm::di, io::uo) is det.
> +:- pred stm_from_inner_to_outer_stm(stm::di, stm::uo) is det.
> +
> %-----------------------------------------------------------------------------%
> %-----------------------------------------------------------------------------%
>
> @@ -276,12 +285,43 @@
>     MR_STM_commit(STM);
> ").
>
> +:- pragma foreign_proc("C",
> +    stm_from_outer_to_inner_io(IO::di, STM::uo),
> +    [promise_pure, will_not_call_mercury, thread_safe],
> +"
> +    STM = NULL;
> +    MR_final_io_state(IO);
> +").
> +
> +:- pragma foreign_proc("C",
> +    stm_from_outer_to_inner_stm(STM0::di, STM::uo),
> +    [promise_pure, will_not_call_mercury, thread_safe],
> +"
> +    STM = STM0;
> +").
> +
> +:- pragma foreign_proc("C",
> +    stm_from_inner_to_outer_io(STM0::di, IO::uo),
> +    [promise_pure, will_not_call_mercury, thread_safe],
> +"
> +    STM0 = NULL;
> +    IO = MR_initial_io_state();
> +").
> +
> +:- pragma foreign_proc("C",
> +    stm_from_inner_to_outer_stm(STM0::di, STM::uo),
> +    [promise_pure, will_not_call_mercury, thread_safe],
> +"
> +    STM0 = NULL;
> +    STM = NULL;
> +").

These foreign procs should just call MR_fatal_error() since the bodies
here aren't ever supposed to be used.

The rest looks okay.

Julien.
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------