Mailing-List: contact dev-help@harmony.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@harmony.apache.org
Received-SPF: pass (athena.apache.org: domain of yuri.kashnikoff@gmail.com
 designates 209.85.198.187 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=beta;
        h=message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=S80GtKh4rVbke1zDYajzPdvRjviweLlALAWBObpxWh13hGd6VWQtMvlVJBvMmwcJnH3Pvp70dtnkPGFqDeWFndP+n2Iot9xujr9taMsdIW4ZQlXArcPfuK2/DWCTiBXCezG/GoXxZO+Bnxnf4pcIYnXTtw5pdKMg64isZCtoq9A=
Message-ID: <aa01cd760803270126n14231176q1e0f66fba02bd89a@mail.gmail.com>
Date: Thu, 27 Mar 2008 14:26:31 +0600
From: "Yuri Kashnikoff" <yuri.kashnikoff@gmail.com>
To: dev@harmony.apache.org
Subject: Re: [drlvm][gc] How to iterate MOS?
In-Reply-To: <9623c9a50803270041h71d26ed8i65fdfbbfa7754d59@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <aa01cd760801282320y3a583654ia4d034bff97e97f0@mail.gmail.com>
	 <aa01cd760803032030o4027c0c3x8f76c874748f4bd3@mail.gmail.com>
	 <0vqwsoirdlz.fsf@gmail.com>
	 <9623c9a50803040505t14e15fb0k850443b7b7d175e9@mail.gmail.com>
	 <aa01cd760803052200i42f9234al747232ca07c45fd0@mail.gmail.com>
	 <aa01cd760803250144g52a03ddbg1463d9bdc158af42@mail.gmail.com>
	 <9623c9a50803260201o1bfdc25eg27e3733ee4e48b04@mail.gmail.com>
	 <aa01cd760803260217q317d0ddfgc8e589f189c4bc23@mail.gmail.com>
	 <aa01cd760803270015u1dd17f13t5481ffbead97d8ef@mail.gmail.com>
	 <9623c9a50803270041h71d26ed8i65fdfbbfa7754d59@mail.gmail.com>

Xiao-Feng,

> Yuri, I need understand your approach better so as to answer your
>  question better. It would be great if you can describe what you are
>  trying to achieve and the steps so that I have a good overall picture.
I have profile info by which I know the order of some object sequences.
For example simple linked List:
class myList {
    myList(long _data) { data = _data;}
    long data;
    myList next;
  }

We have a sequence of objects which are connected each other by some
hot field (field 'next' in our example):
o1->o2->o3->o4->...->oN

I am trying to layout objects in the heap by hot field.

My algorithm is :
1) Recognize sequences : find head and tail of the sequence.
2) Allocate separate space for sequence (outside the heap).
3) Mark left objects of these sequences in the MOS as dead.
4) Compact MOS (by move_compact algo).
5) Copy objects from the separate space (allocated and copied on steps
2-3) to the end of the MOS.
6) Update pointers.
7) Free allocated memory.

The interface look like this:
void gc_layout_build_seq_list(GC_Gen *gc);   // 1)
void gc_layout_alloc_mem();                         // 2)
void gc_layout_copy_seq_to_mem();             // 3)

4) move_compact...

void gc_layout_copy_to_mos(GC_Gen* gc);   // 5)
void gc_layout_fix_pointers(GC_Gen* gc);      // 6)
void gc_layout_free_mem();                          // 7)

In detail:

1) Method gc_layout_build_seq_list(GC_Gen *gc) has only one
side-effect - it fills up list<seqSimpleList> seq_head.
seqSimpleList is a simple structure with 2 fields :
Partial_RevealObject* head
Partial_RevealObject* tail
2) Method gc_layout_alloc_mem() takes each element of the the seq_head
and iterates sequence (having head of the sequence and hot field info
it done by Partial_Reveal_Object* gc_layout_get_obj_by_hot_field() )
incrementing size_of_space value. Then it simply allocates memory.
3) Method void gc_layout_copy_seq_to_mem() takes each element of the
seq_head, iterates sequence and copies objects of the sequence to the
previously allocated space.

4) ...

5) Method gc_layout_copy_to_mos(GC_Gen* gc) simply copies from a
separate space to the end of the MOS. (in previous letter you can find
code of this method)

6) Method void gc_layout_fix_pointers(GC_Gen* gc) is just a little bit
modified version of fix_pointers.
Only slot_fix[1] and function was modified (old_new_map gives new
place of the object by its old address, it was filled up during
copying to MOS phase[step 5]):

[1]
// slot_fix() method cloned with minimal changes (for original see
fix_repointed_refs.h)
inline void gc_layout_slot_fix(REF* p_ref)
{
    Partial_Reveal_Object* p_obj = read_slot(p_ref);
    if(!p_obj) return;

    p_obj = old_new_map[p_obj];
    if(!p_obj) return;

    assert(obj_belongs_to_gc_heap(p_obj));
    write_slot(p_ref, p_obj);
}

// this a modified version of block_fix_ref_slots()
inline void gc_layout_block_fix_ref_slots(Partial_Reveal_Object* p_obj)
{
    if( !object_has_ref_field(p_obj) ) return;

    /* scan array object */
    if (object_is_array(p_obj)) {
        Partial_Reveal_Array* array = (Partial_Reveal_Array*)p_obj;
        assert(!obj_is_primitive_array(p_obj));

        int32 array_length = array->array_len;
        REF* p_refs = (REF *)((POINTER_SIZE_INT)array +
(int)array_first_element_offset(array));
        for (int i = 0; i < array_length; i++) {
            gc_layout_slot_fix(p_refs + i);
        }
        return;
    }

    /* scan non-array object */
    unsigned int num_refs = object_ref_field_num(p_obj);
    int *ref_iterator = object_ref_iterator_init(p_obj);

    for(unsigned int i=0; i<num_refs; i++){
        REF* p_ref = object_ref_iterator_get(ref_iterator+i, p_obj);
        gc_layout_slot_fix(p_ref);
    }

    return;
}

void gc_layout_fix_pointers(GC_Gen* gc)
{
    Blocked_Space *mspace = (Blocked_Space*)gc->mos;
    Block_Header *curr_block = (Block_Header*)mspace->blocks;
    Block_Header *space_end =
(Block_Header*)&mspace->blocks[mspace->free_block_idx -
mspace->first_block_idx];
    while(curr_block < space_end) {
        POINTER_SIZE_INT p_obj = (POINTER_SIZE_INT)curr_block->base;
        POINTER_SIZE_INT p_next_obj = p_obj;
        POINTER_SIZE_INT block_end = (POINTER_SIZE_INT)curr_block->free;
        unsigned int hash_extend_size = 0;
        while(p_obj < block_end){
#ifdef USE_32BITS_HASHCODE
            hash_extend_size  =
(hashcode_is_attached((Partial_Reveal_Object*)p_obj))?GC_OBJECT_ALIGNMENT:0;
#endif
            gc_layout_block_fix_ref_slots((Partial_Reveal_Object*)p_obj);
            p_obj = p_obj + vm_object_size((Partial_Reveal_Object
*)p_obj) + hash_extend_size;
        }
        curr_block = curr_block->next;
        if(curr_block == NULL) break;
    }
}

And my problem is that I've got an assertion in this phase.


-- 
Yuri S. Kashnikov
Novosibirsk State University, Russia
2 Pirogova street
630090, Novosibirsk-90
yuri.kashnikoff@gmail.com