[m-rev.] for review: Region runtime system
Julien Fischer
juliensf at csse.unimelb.edu.au
Mon Jul 2 18:19:55 AEST 2007
On Fri, 29 Jun 2007, Quan Phan wrote:
> Estimated hours taken: 25.
> Branch: main.
>
> Implement the region runtime system and partly integrate it with the runtime
> system of Mercury. This partly integrated runtime only supports "deterministic"
> programs (deterministic programs in which no region-related actions happen in
> condition of if-then-elses, at least no removals of regions happen).
> For example, it now works with nrev, qsort, life, which are some
> small deterministic benchmarks I used in my related paper.
Works, as in works with the HLDS->HLDS transformation that you've
implemented?
> runtime/Mmakefile.m:
> Link the files that implement the region runtime to the Mercury
> runtime system.
>
> runtime/mercury_heap.m:
> Link the region runtime to the Mercury runtime when RBMM is used.
> Add a macro to allocate terms in a region.
s/a macro/macros/
>
> runtime/mercury_region.h:
> New file.
> The interface to the region runtime.
> runtime/mercury_region.c:
> New file.
> Implementation of the region runtime.
> - implement the regions themselves as a linked-list of pages.
> - basic methods for create regions, remove regions, and allocate
> words in regions.
> - implement the mechanism to support backtracking. This part has not
> been integrated into the runtime yet.
>
>
> library/region_builtin.m:
> Change the builtins to make call to the region runtime interface.
...
> Index: mercury_heap.h
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_heap.h,v
> retrieving revision 1.38
> diff -u -u -r1.38 mercury_heap.h
> --- mercury_heap.h 14 Oct 2006 16:59:41 -0000 1.38
> +++ mercury_heap.h 29 Jun 2007 00:38:48 -0000
> @@ -50,6 +50,10 @@
> #endif
> #endif
>
> +#if defined(MR_USE_REGIONS)
> + #include "mercury_region.h"
> +#endif
> +
> /***************************************************************************/
>
> /*
> @@ -225,6 +229,22 @@
>
> #endif /* not MR_CONSERVATIVE_GC */
>
> +#if defined(MR_USE_REGIONS)
> + #define MR_tag_alloc_in_region(dest, tag, region, count) \
> + ( \
> + (dest) = (MR_Word) MR_mkword(tag, \
> + (MR_Word) \
> + ((MR_Word *) MR_region_alloc_in_region( \
> + region, (count)) )), \
Put region in parentheses there.
> + (void) 0 \
> + )
> +
> +#else /* not MR_USE_REGIONS */
> + /* Dummy definitions */
> + #define MR_tag_alloc_in_region(dest, tag, region, count) \
> + MR_tag_incr_hp(dest, tag, count)
Why do you need this version? The compiler shouldn't be generating
references to MR_tag_alloc_in_region in non .rbmm grades.
> /***************************************************************************/
>
> /*
> @@ -313,6 +333,24 @@
>
> #endif /* MR_CONSERVATIVE_GC */
>
> +#if defined(MR_USE_REGIONS)
> + #define MR_alloc_in_region(dest, region, count) \
> + ( \
> + (dest) = (MR_Word) MR_mkword(tag, \
> + (MR_Word) \
> + ((MR_Word *) MR_region_alloc_in_region( \
> + region, (count)) )), \
Likwise, parentheses here.
> + (void) 0 \
> + )
> +
> +#else /* not MR_USE_REGIONS */
> +
> + /* Dummy definitions */
> + #define MR_alloc_in_region(dest, region, count) \
> + MR_tag_offset_incr_hp(dest, 0, 0, count)
Likewise, why is this needed?
...
> Index: mercury_region.c
> ===================================================================
> RCS file: mercury_region.c
> diff -N mercury_region.c
> --- /dev/null 1 Jan 1970 00:00:00 -0000
> +++ mercury_region.c 29 Jun 2007 00:44:30 -0000
> @@ -0,0 +1,765 @@
> +/*
> +** vim:sw=4 ts=4 expandtab
> +*/
> +/*
> +** Copyright (C) 2007 The University of Melbourne.
> +** This file may only be copied under the terms of the GNU Library General
> +** Public License - see the file COPYING.LIB in the Mercury distribution.
> +*/
> +
> +/*
> +** file: mercury_region.c
> +** main authors: qph
> +**
> +*/
> +
> +#include "mercury_misc.h"
> +
> +#include "mercury_region.h"
> +
> +/*
> +** Currently word_sizeof is used for MR_Region struct only. This is always
> +** the case then it should be better to make it an (inline) function.
> +*/
> +#define word_sizeof(s) (sizeof(s) / sizeof(MR_Word))
> +
> +MR_Word *ite_stack_min;
> +MR_Word *ite_stack_max;
> +MR_Word *ite_sp;
> +
> +MR_Word *nondet_stack_min;
> +MR_Word *nondet_stack_max;
> +MR_Word *nondet_maxfr;
> +
> +/*---------------------------------------------------------------------------*/
> +/*---------------------------------------------------------------------------*/
> +
> +/*---------------------------------------------------------------------------*/
> +/* Supporting list management. */
> +
> +static void region_list_add(MR_Region *region, MR_Word *sp, int frame);
> +static void region_list_remove(MR_Region *region, MR_Word *sp, int frame);
> +static Snapshot* snapshot_list_add(MR_Region *region, MR_Word *sp, int frame);
> +static void free_region_list(MR_Word *sp, int frame);
> +static void free_snapshot_list(MR_Word *sp, int frame);
> +
> +/*
> +** Add to the head of the list.
> +*/
> +static void
> +region_list_add(MR_Region *region, MR_Word *sp, int frame) {
> + Region_List *element =
> + (Region_List*) malloc(sizeof(Region_List));
Call MR_malloc() rather than malloc() there (and elsewhere.)
> + element->region = region;
> + element->prev = NULL;
> + if (sp[frame] == NULL) { // Adding the first element.
Please avoid the use of // style comments.
...
> +** Page operations.
> +*/
> +
> +/*
> +** Request for more pages from the operating system.
> +*/
> +static MR_Page *request_pages(void);
> +
> +static MR_Page *
> +request_pages() {
> + MR_Page *pages;
> + pages = (MR_Page *) malloc(MR_NUM_PAGES_TO_REQUEST*sizeof(MR_Page));
> + if (!pages) {
> + MR_fatal_error(
> + "Cannot request more memory from the operating system");
> + }
> + pages[0].next_page = NULL;
> + int i;
Please move the declaration of `i' to the top of the block.
(Some C compiler get stroppy about mixing code and declarations.)
> + for (i = 1; i < MR_NUM_PAGES_TO_REQUEST; i++) {
> + pages[i].next_page = &pages[i - 1];
> + }
> + return &(pages[MR_NUM_PAGES_TO_REQUEST - 1]);
> +}
> +
> +/*
> +** Take a page from the free page list.
> +*/
> +static MR_Page *get_free_page(void);
> +
> +static MR_Page *
> +get_free_page() {
> + if (free_page_list == 0) {
> + free_page_list = request_pages();
> + }
> +
> + MR_Page *page = free_page_list;
> + free_page_list = free_page_list->next_page;
> + // Disconnected the first free page from the free list.
> + page->next_page = NULL;
> + return page;
> +}
> +
Most of my comments above apply to the remainder of mercury_region.c
as well, but I would like to see the following changes made to
mercury_region.h before look at the rest of it more closely.
...
> Index: mercury_region.h
> ===================================================================
> RCS file: mercury_region.h
> diff -N mercury_region.h
> --- /dev/null 1 Jan 1970 00:00:00 -0000
> +++ mercury_region.h 20 Jun 2007 06:29:58 -0000
...
> +/*
> +** File: mercury_region.h
> +** main author: Quan Phan
> +*/
> +
> +#ifndef MERCURY_REGION_H
> +#define MERCURY_REGION_H
> +
> +#if !defined(MR_USE_REGIONS)
> +
> +/* Put dummy defn for MR_Region */
Explain why the dummy definition is required, e.g. because the
foreign_type pragma for region_builtin.region/0 requires it.
> +
> +typedef int MR_Region;
> +
> +#else /* defined(MR_USE_REGIONS) */
> +
> +/*
> +** XXX This should be made configurable when compiling a program.
> +*/
Ideally, these parameters should be configurable at runtime, via
the MERCURY_OPTIONS environment variable. That can be a future change
though.
> +#define MR_NUM_PAGES_TO_REQUEST 100
> +#define MR_PAGE_SPACE_SIZE 30
> +
> +#define ITE_STACK_SIZE 1024 /* 4KB, each slot is 4 bytes*/
> +#define ITE_STACK_FRAME_SIZE 3
> +#define NONDET_STACK_SIZE 1024 /* 4KB, each slot is 4 bytes*/
> +#define NONDET_STACK_FRAME_SIZE 2
> +#define SNAPSHOT_LIST -1
> +#define TERMINATION_LIST -2
> +#define REMOVAL_LIST -3
Add `MR_' prefixes to these constants.
> +typedef struct MR_Page_Struct {
> + MR_Word space[MR_PAGE_SPACE_SIZE];
> + struct MR_Page_Struct *next_page;
> +} MR_Page;
I suggest: s/MR_Page/MR_RegionPage/. MR_Page seems too generic a name.
Please document *each* of the fields in the following (and above)
structures. Also there should be an overall comment describing
each structure.
> +typedef struct MR_Region_Struct {
> + struct MR_Page_Struct *last_page;
> + MR_Word *pointer;
That's not a good name for that field. pointer to what?
> + MR_Word avail_space;
s/avail_space/available_space/
> + unsigned int removal_counter;
> +
> + /*
> + ** The fields below are redundant information, which is used to
> + ** facilitate the check if a region is in one of the list or not.
> + ** We will have to pay the price of keeping the redundancy
> + ** consistent.
> + */
> + /* A region can only be in the below lists of one frame. */
> + MR_Word *in_termination_list_of_ite_frame;
> + MR_Word *in_removal_list_of_ite_frame;
> + MR_Word *in_termination_list_of_nondet_frame;
> +
> + /* A region can have several snapshots snapshot-lists of several
> + ** nondet/ite frames.
> + **
> + ** We store the newest_snapshot (in a nondet frame) here to faciliate
> + ** shrinking the region. When shrinking we always shrink the region to
> + ** the size in the snapshot of the topmost nondet frame.
> + **
> + ** The newest frames containing a snapshot is used to check whether a
> + ** snapshot needs to be stored for an allocation or not.
> + */
> + struct Snapshot_Struct *newest_snapshot;
> + MR_Word *nondet_frame_of_newest_snapshot;
> + MR_Word *ite_frame_of_newest_snapshot;
> +} MR_Region;
> +
> +/* Region is used to represent termination list and removal list. */
> +typedef struct Region_List_Struct {
> + struct Region_List_Struct *next;
> + struct Region_List_Struct *prev;
There are a lot of structures in the runtime that have fields named
`next' and `prev' (such as the ones in the snapshot structure whose
definition follows this one ;-) ). I would add a prefix to the fields
of this structure (and the others) that distinguishes them. e.g.
typedef struct Region_List_Struct {
struct Region_List_Struct *MR_rl_next;
struct Region_List_Struct *MR_rl_prev;
MR_Region *MR_rl_region;
}
Likewise for the other structures.
> + struct MR_Region_Struct *region;
> +} Region_List;
Likewise: s/Region_List/MR_RegionList/
> +
> +/* This is to represent snapshot list. */
> +typedef struct Snapshot_Struct {
> + struct Snapshot_Struct *next;
> + struct Snapshot_Struct *prev;
> + struct MR_Region_Struct *region;
> + struct MR_Page_Struct *saved_last_page;
> + MR_Word *saved_pointer;
> + MR_Word saved_removal_counter;
> + MR_Word saved_avail_space;
> +} Snapshot;
s/Snapshot_Struct/MR_Snapshot_Struct/ and s/Snapshot/MR_Snapshot/
> +/*
> +** A region is implemented as a single-linked list of pages. A page contains
> +** a pointer to the next to form a single-linked-list and an array
> +** (of MR_Word) to store program data.
> +** The region allocator maintains a list of free pages, when we need a page
> +** for a region it is taken from the list.
> +** The information of the region itself (pointer to next available cell,
> +** removal counter, some other operational data) is stored in its first page.
> +*/
Is this comment supposed to be documenting free_page_list? It reads
more like a description of the MR_region structure.
> +
> +MR_Page *free_page_list;
I suggest s/free_page_list/MR_region_free_page_list/
The convention used by the Mercury project is that declarations for
global variables should appear in header files and definitions should
*only* appear in .c files. The above risks multiply defining
free_page_list. You should put an extern specifier in front of the
above and add definition for free_page_list to mercury_region.c.
> +MR_Region *MR_region_create_region(void);
> +void MR_region_remove_region(MR_Region *);
> +MR_Word *MR_region_alloc_in_region(MR_Region *, unsigned int);
> +
> +MR_Region *MR_region_backtrack_support_create_region(void);
> +void MR_region_backtrack_support_remove_region(MR_Region *);
> +MR_Word *MR_region_backtrack_support_region_alloc(MR_Region *,
> + unsigned int);
> +
> +void MR_region_create_ite_frame(void);
> +void MR_region_ite_then_do_removal(void);
> +void MR_region_ite_else_undo_changes(void);
> +
> +void MR_region_create_nondet_frame(void);
> +void MR_region_discard_nondet_frame(void);
> +void MR_region_undo_creations_and_allocations(void);
> +
> +void MR_region_init_region_manager(void);
Document the above functions.
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
--------------------------------------------------------------------------
More information about the reviews
mailing list