Data structures and algorithms Part - I (all except Interpreter )

1.Bootstrapper.

Data structures:
1.Buffer to hold elf-header
2. Location for address of start-up code where control has to go .
3. START_ADDR: location for storing address of _start .
4. Pointers for storing handles of shared libraries.


Algorithm
1.Load the modules of DOS using dlopen.
2.Store the handles.
3.mmap the ELF header and mprotect it.
4.Get address of startup code using dlsym on module containing it.
5.Save the address of start in START_ADDR.
6.Overwrite this address with address of startup code.
7.Unmap the header.




2.Startup-code

Data structures.

1.Context save area for the registers (array of structures).
2.Buffer to be used as stack.
3.Buffer to hold complete text segment.
4.PROG_CTR to hold linear virtual address.



Algorithm
1.Save the context into context save area.
2.Initialize PROG_CTR to 0.
3.Open the executable using bfd and get canonical form into buffer.
4.Give control to interpreter.






Interpreter
Data structures


Algorithm
It will get control from the startup code.

It will call disassember to disassemble the instructions from PROG_CTR.
The disassembler will return the no of bytes of sequential code and the next control transfer instruction..
The interpreter calls linear executor and execute those sequential instructions natively.
It then determines the type of control transfer instruction as given by disassembler.

Types
1 unconditional jump
2.conditional jump
3 call
4 ret
5 leave

if unconditional and forward then change PROG_CTR to target of jump.
Else





Prologue and epilogue adder.


Data structures.

1.Buffer for trace- TRACE BUFFER.
This will be dynamic and will be big enough to hold prologue ,epilogue
Trace and compensation code.

2..Stub lookup table.
It will contain 3 fields.

Virtual address of the exit instruction's destination.
Stub address.
Pointer (index) to compensation code buffer.
no of instructions

3.Next-counter NEXT_CTR.
Gives the next free position in trace buffer.

Algorithm

1.Add code in trace buffer to restore the machine context.
2.This is prologue code.
3.Increment the NEXT_CTR by size of above code.
4.Add the code for trace into buffer.
5.Increment the NEXT_CTR by size of above code.
6.Traverse this code and fill the stub address in the stub table with the exit addresses i.e those coming out of trace.
7.The optimizer will have filled some exits which have compensation code.
8.Any remaining exits are to filled.
9.Now in the stub-table fill in all stub address in the following way
10.Save NEXT_CTR .
11.The first stub address is NEXT_CTR.
12.The next address is NEXT_CTR + sizeof(compensation code) + 2 .
13.The 2 is for jump instruction to epilogue and saving the address from which to start interpretation.
In this way the table is filled.

14.Now we traverse the trace and change all the exit lvirtual addresses to stub addresses by stub-table lookup.

15. Also add the stubs and compensation code.
After this add the code for storing the register context in context save area and jumping to dispatch.








Dispatcher

Algorithm
Adding trace
1.Give control to optimizer
2.It will transfer the trace to optimizer and receive the assembled trace from 3.assembler.
4.This assembled trace is given to fragment cache.
5.After inserting fragment cache gives control to dispatch.

Fragment execution
Trace selector or trace collector gives fragment address .
Dispatch checks from where control has come.
If from trace collector it saves the address to be collected next.
It transfers control to fragment cache.
After receiving control back it gives control to either trace collector or trace selector.











Fragment cache.


Data structures

1.List of buffers having the structure
header containing size ,start address
buffer to hold fragment
pointer to next .

2..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.

2.Free pointer FREE_PTR.
This will point to the next free buffer on list.

Algorithm
For adding a fragment
1.Make an entry in FRAG_LOOK_TABLE.
2.Insert fragment in position pointed by FREE_PTR.
3. Insert the complementry fragment in next position.
4. advance the FREE_PTR BY 2.
5. Fill the headers of above fragments.
6.Return control to dispatch.

For execution.

1.Get the fragment address.
2.Change ip to that address.