PROJECT : 21st NOV

Agenda: Deciding upon the Data structures Required



These are some the Data structures that we have thought as per the
initial design of the system:


1. Structure used for saving the register context of the CPU

It will have the following members
all the CPU registers

2. An array of the above declared structured for saving the
registers/contexts.

* The size of this array will be static
* 25 will be an average value
* This value will generally depend upon the
application. If it has lots of system calls and library
routines then this number has to be increased.

3. A buffer which will contain the complete text segment

* This segment of the code will be provided by the
bfd library.
* The size of this buffer can be static or dynamic.
but dynamic is more preferable, as bfd is capable
of providing us with the size of this segment.



4. START_ADDR, which will be taken from the e_entry of the elf header

* This variable will hold the address from where the
actual interpretation of the code will start, once
the control comes to our system.



5. PROG_CTR , it will hold the linear virtual address for the interpreter

* The interpreter always assumes that it has to start
its interpretation from this address only. So whenever
control changes, this value must be updated.


6. LINEAR EXECUTABLE PAGE

* The sizeof this page can be static as well as dynamic.
* Dynamic : The number of bytes to be executed linearly
can be obained. This functionality is provided by our
/binutils/opcodes or say our disassembler.

7. TRACE LOOKUP TABLE

* A sturucture holding the information about the
entries of the traces that have been encountered.
It has the following members,

* flag ; /* indictaing wether a function or a loop */
* validity /* To inform wether its still in the fragement, if
was present */
* head_trace /* head of the trace */
* end_trace /* end of the trace */
* start_frag /* Its only valid if validity is TRUE */
* count /* number of hits of start_trace */

8. HIST_BUFFER

* A strcuture holding information about the various basic blocks
which have been encountered previously. It saves the overhead
re-interpretation of the code that has already been interpreted.
Also, It contains an extra member insn, which contains the
control transfer insn, which follows this basic block.

* The member of this structure are :
* vma_start_addr /* It is the start of the basic block */
* linear_byt_count /* number of linear bytes in this basic block */
* char insn[30] /* holds the next insn */

Example :

1000 : mov eax,abx
1002 : addl eax,#30
1004 : nop
1005 : ....some linear inmstructions
..
..
..
1020 : cmp eax,#400
1023 : jnz 1020

Now, in this case,
vma_start_addr = 1000;
linear_byt_count = 1022
insn = "jnz 1020"

Now when we encounter this start_addr again for interetation, we simply copy
linear_byt_count number of bytes from the text segment starting from
vma_start_addr into a linear executable page and execute it. Now we
have the next control transfer insn also, so removed the overhead of
decoding the control transfer insn.


9. COMPLEMETARY_ADDR_TABLE

/* This would simply be an array, which will store the start address of all
the non taken branches during trace collection . So that after collection
we can select the lowest value from this array and move the code lying
between this selected value and the end of trace.

* The basic motto is to move the complete loop in the fragment.


10. COMPLY_FRAG_PAGE

* This will be just a page that will be allocted by malloc. It will
actually contain the complimentary piece of code that we will get
from the point No . 9.

* This page will also be finally moved into the fraagement cache,
along with the fragement.

* The size of this page cannot be known before hand.

11. IR

* This structure will actually hold the IR that we are gonna get
from the disasembler.

* It will have the following members :
* menmonics /* menmonics of the insn */
* opnd1
* opnd2

12. An array of the above structure will be used to pass to the optimizer for optimization.


13. FRAG_LOOK_TABLE

* This will hold all the information related to the
fragments that are present in the fragment cache

* It will have the following members

* original_vma /* the actual vma of start_addr before relocation */
* frag_start_addr /* start adress inside the fragement */
* offset_complementary_fragement_page /* start of somplementary page */
* fragment_size /* size of the fragment */
* SOME MORE MEMBERS FOR AGING POLICIES.

These were some of the most important data structures that would be
required as per the initial design of the system.

We are still deciding on :

1. Fragement

a. Memory Alloctaion policies
b. Placement policies ( procedure sorting )
c. Relocation Policies
d. Eviction policies ( based on aging, count etc ).

2. Data structures required for the optimizer.

3. Study on how many shared object would make our system
flexible as well as robust. Currently discussing on keeping it two.

a. The first consists of
i> preloader
ii> boostrapper
iii>interpreter
iv>disassembler

b. The second consists of
i> Relocator
ii>optimizer
iii>epilog & prolog adder
iv>fragment

We will have a DISPATCHER, which is responsible for the communication
between these shared objects.

4. The Relocation

Not much work is required for direct jumps as we are removing direct jumps from the trace.

Relocation during the optimization is a mojor issue.
i> When a piece of code is inserted.
ii> When a piece of code is removed.