pmacs3/code_examples/build.c

/*
 * build.c - Fragment builder. 
 *
 * Copyright (c) 2000-2003 - J. Kevin Scott and Jack W. Davidson
 *
 * This file is part of the Strata dynamic code modification infrastructure.
 * This file may be copied, modified, and redistributed for non-commercial 
 * use as long as all copyright, permission, and nonwarranty notices are 
 * preserved, and that the distributor grants the recipient permission for 
 * further redistribution as permitted by this notice.
 *
 * Please contact the authors for restrictions applying to commercial use. 
 *
 * THIS SOURCE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED 
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF 
 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.  
 *
 * Author: J. Kevin Scott
 * e-mail: jks6b@cs.virginia.edu
 * URL   : http://www.cs.virginia.edu/~jks6b
 *
 */

#ident "$Id: build.c 1063 2006-03-14 16:52:47Z williadw $"

#include "all.h"

/* Private data structures and function declarations. */


/* these macros are to the head and tail of the fragment queue 
 * replacing the head and tail globals with thread specific
 * pointers
 */
#define HEAD ((hashtable_get((*TI.thread_id)()))->fq_head)
#define TAIL ((hashtable_get((*TI.thread_id)()))->fq_tail)


#define PATCHTABSIZE 1087
static strata_patch *patch_tab[PATCHTABSIZE];

static jmp_buf strata_build_env;

int builder_opt_no_frag_linking;
int strata_entrance_count;
int strata_stop_after;


static char *frag_ty_map[] = {
	"CBRANCH",
	"IBRANCH",
	"CALL",
	"RET",
	"SWITCH",
	"SPECIAL",
	"INVALID",
	"ICALL"
};


strata_fragment* strata_install_fragment_group();
strata_fragment* strata_build_single_fragment(app_iaddr_t next_PC);
void strata_add_pc_mapping(app_iaddr_t PC, fcache_iaddr_t fPC);
void strata_create_fragment_trampolines(strata_fragment *frag);
void strata_remove_create_tramp_entry(strata_patch* cur);
void targ_create_trampoline(strata_fragment *frag, strata_patch *tramplist);


/*
 * strata_enter_builder - Perform operations necessary when entering the builder,
 * including locking mutexes, and logging.
 */
void strata_enter_builder(app_iaddr_t to_PC, strata_fragment *from_frag) {
	/* Thread locking */
	STRATA_LOG("lock", "builder lock.\n");
	(*TI.mutex_lock)();

}



/* 
 * strata_leave_builder - Perform any operation that's necessary each time we 
 * exit the builder and return execution to the fragment cache, including  
 * dumping tracing info, updating the control flow graph, and unlocking mutexs.
 */
void strata_leave_builder(strata_fragment* frag, strata_fragment* from_frag) {
	/* emit information about ibtc traces, if requested */
	if(from_frag && form_ibtc_traces_fd)
	{
		fwrite((const void *)(&(from_frag->ty)),        
		       sizeof(int),      1, form_ibtc_traces_fd);
		fwrite((const void *)(&(from_frag->indPC)),  
		       sizeof(unsigned), 1, form_ibtc_traces_fd);
		fwrite((const void *)(&(from_frag->indfPC)),    
		       sizeof(unsigned), 1, form_ibtc_traces_fd);
		fwrite((const void *)(&(frag->PC)),             
		       sizeof(unsigned), 1, form_ibtc_traces_fd);
	}

	/* handle control flow edges */
	strata_handle_control_flow_graph(from_frag, frag);

	STRATA_TRACE("Leaving builder to execute 0x%08x:0x%08x\n", frag->fPC, frag->PC);

	(*TI.mutex_unlock)();
}


/*
 * strata_build_main - 
 * Build a fragment and returns the starting fragment address.
 * 
 * Inputs: 
 *    to_PC     - Beginning of new fragment.
 *    from_frag - Pointer to the fragment calling strata_build_main 
 *
 * Output:
 *    The (fragment) address to start executing.
 */
fcache_iaddr_t strata_build_main (app_iaddr_t to_PC, strata_fragment *from_frag) 
{
	strata_fragment *frag;
	insn_t insn;
	fcache_iaddr_t to_fPC, previous_last_fPC;
	app_iaddr_t next_PC, previous_next_PC;
	int insn_class, first_frag;
	int sieve_needs_fill=0;


	strata_enter_builder(to_PC, from_frag);

	/* Mark our place in case we need to restart the builder. 
	   If the fragment cache fills, we need to create a new fragment
	   and then, restart the builder.
	   (consider moving past the point where we know we're building
	   a fragment)
	*/
	if(!targ_opt_fast_return)
		setjmp(strata_build_env);	/* this is for flushing the f$, we're only doing that w/o fast returns */



	#ifdef STATS	
	/* "strata iso" functionality*/
	strata_entrance_count++;
	if ( strata_entrance_count == strata_stop_after ) {
		return to_PC;
	}

	stat_builder_enters++;
	#endif


	STRATA_TRACE("Builder entered from fragment %08x:%08x [%s] to execute %08x (%d entrances)\n",
		     from_frag,
		     from_frag?from_frag->PC:0,
		     from_frag?frag_ty_map[from_frag->ty]:"NONE",
		     to_PC,
		     strata_entrance_count
		     );

	/* !!! TEMP SOLUTNION check for fast return setjmp error */
	if ( strata_fragment_address(to_PC) ) {
		STRATA_LOG("fast_returns", "returning to to_PC!");
		(*TI.mutex_unlock)();
		return to_PC;
	}

	/* lookup the fragment in the F$ */
	frag = strata_lookup_built_fragment(to_PC) ;

	/* if it's not there, build it */
	if (!frag)
	{
		/* We're adding at least one new fragment to the fragment cache. */ 
		/* (consider moving setjump here) */
		STRATA_TRACE("Target not in F$!\n");
	
		/* Add it to the work list, and build the group. */
		strata_enqueue_address(to_PC);
		frag = strata_install_fragment_group();
	
	}

	/* Execute the fragment. */
	STRATA_TRACE("Executing %08x mapped to %08x type=%s\n",
		     to_PC,
		     frag->fPC,
		     frag_ty_map[frag->ty]
		);

	strata_sieve_update(frag);

	/* leave builder and return the fragment address */
	strata_leave_builder(frag, from_frag);
	return frag->fPC;

}

/*
 *  strata_handle_control_flow_graph - update the (non-working) CFG for strata
 */
void strata_handle_control_flow_graph(strata_fragment *from_frag, strata_fragment *frag)
{
	app_iaddr_t to_PC;
	assert(frag);
	to_PC=frag->PC;
	

	/* Target is already in the fragment cache. */
	STRATA_TRACE("Target in F$!\n");
	/* Count the execution of the fragment we're going to. */
	/* consider making into macro */
	strata_profiler_count_insn(frag->prof,1);	

	if (from_frag != NULL) { 

		/* Update control flow information. */
		if (!(from_frag->ty == STRATA_FRAG_CBRANCH || 
		      from_frag->ty == STRATA_FRAG_CALL)) {
			strata_frag_control_edge(from_frag,frag);
		}

		switch(from_frag->ty) {
		case STRATA_FRAG_RET:
			#ifdef STATS
			stat_num_rets++;
			#endif
			strata_indirect_branch_miss(from_frag,frag);
			break;
		case STRATA_FRAG_ICALL:
		case STRATA_FRAG_IBRANCH:
			#ifdef STATS
			stat_num_ibranches++;
			#endif
			strata_indirect_branch_miss(from_frag,frag);
			break;
		case STRATA_FRAG_CBRANCH:
			#ifdef STATS
			stat_num_branches++;
			#endif
			break;
		case STRATA_FRAG_SWITCH:
			break;
		case STRATA_FRAG_CALL:
			break;
		case STRATA_FRAG_SPECIAL:
			break;
		default:
			strata_fatal("Unknown branch type for fragment"); 
		}
	} else {
		/* All fragments must set from_frag! */
		/*strata_fatal("Re-entering fragment did not set from_frag");*/
		/* I'm not sure above statement is true, warn about it for now */
		/* thread -- reason for not using strata fatal */
		STRATA_LOG("warn", "From Frag not set!");
	}
}



/* 
 * strata_install_fragment_group - 
 * This function builds and installs an group of
 * dependent fragments into the F$. These should be
 * fragments that aren't ready to be used until all of them are
 * built. (ie, a fragment with a call + its return fragment if 
 * fast returns are on.) 
 */
strata_fragment* strata_install_fragment_group() 
{
	strata_fragment* frag, *first_frag;
	app_iaddr_t next_PC;
	fragment_queue* cur;
	
	/* initializations */
       	first_frag = NULL;
	cur = HEAD;
	
	/* While we have fragments on the work list */
	while ( cur != NULL ) {
		next_PC = cur->PC;
		frag = strata_build_single_fragment(next_PC);
		
		if ( !(frag->flags & STRATA_FRAG_DONT_LINK) ) {
			/* Do chaining. */
			strata_apply_patches(frag);
		}
		cur = cur->next;
	}

	/* don't set the flags to "ready" unil all of the fragments 
	   are built */
	while( next_PC = strata_dequeue_address() ) {
		frag = strata_lookup_fragment(next_PC);
		assert(frag!=NULL);
		if ( first_frag == NULL ) {
			first_frag = frag;
		}
		frag->flags |= STRATA_FRAG_READY;
	}
	
	return first_frag;

}

/*
 * strata_build_single_fragment -
 * builds a single fragment from the give application address, and
 * returns a pointer to the strata_fragment struct. Note, this function
 * does not set the STRATA_FRAG_READY flag, which is handled in the common
 * case by strata_install_fragment_group
 */
strata_fragment* strata_build_single_fragment(app_iaddr_t next_PC) 
{
	strata_fragment *frag=NULL;
	insn_t insn;
	int insn_class=0;
	int instrs_in_this_frag = 0;
	fcache_iaddr_t to_fPC=0, previous_last_fPC=0;
	app_iaddr_t previous_next_PC=0;
	
	/* initalize the new fragment */
	STRATA_TRACE("Building new fragment for :>0x%08x\n",next_PC);
	frag = strata_create_fragment(next_PC);
	strata_begin_fragment(frag);

	/* set linking flag if necessary */
	if ( builder_opt_no_frag_linking ) {
		frag->flags |= STRATA_FRAG_DONT_LINK;
	}

	STRATA_TRACE("New fragment at: 0x%08x\n", frag->fPC);

	/* Remember the frag. cache address of the first fragment. */
	if (to_fPC == 0)
		to_fPC = frag->fPC;

	/* Fetch/decode/translate loop for fragment formation. */
	do {
		/* reset vars keeping last PC */
		previous_next_PC=next_PC;
		previous_last_fPC=frag->last_fPC;
		
		/* fetch and classify */
		insn = (*TI.fetch)(next_PC);
		insn_class = (*TI.classify)(insn); 

		if(next_PC==strata_stop_address)
		{
			targ_emit_shutdown_code(frag,previous_next_PC, insn);
			frag->ty=STRATA_FRAG_SPECIAL;
			next_PC=0;
			break;
		}

		/* consider making into a indirect function call off the enumeration */
		switch(insn_class) {
		case STRATA_CALL:
			next_PC = (*TI.xlate_call)(frag,next_PC,insn);
			strata_add_pc_mapping(next_PC, frag->last_fPC);
			STRATA_TRACE("call translation returned: 0x%08x\n", next_PC);
			break;
		case STRATA_PC_RELATIVE_BRANCH:
			next_PC = (*TI.xlate_pcrel_branch)(frag,next_PC,insn);
			strata_add_pc_mapping(next_PC, frag->last_fPC);
			break;
		case STRATA_INDIRECT_BRANCH: 
			next_PC = (*TI.xlate_ind_branch)(frag,next_PC,insn);
			break;
		case STRATA_RETURN:
			next_PC = (*TI.xlate_return)(frag,next_PC,insn);
			break;
		case STRATA_SPECIAL:
			next_PC = (*TI.xlate_special)(frag,next_PC,insn);
			strata_add_pc_mapping(next_PC, frag->last_fPC);
			break;
		case STRATA_NORMAL:
			next_PC = (*TI.xlate_normal)(frag,next_PC,insn);
			break;
		default:
			assert(0);
		}

		instrs_in_this_frag++;
                if(instrs_in_this_frag >= strata_max_insts_per_frag && next_PC)
                {
                        (*TI.end_fragment_early)(frag,next_PC);
                        break;
                }


		
		frag->indPC  = previous_next_PC;
		frag->indfPC = previous_last_fPC;

	} while(next_PC);

	/* Create all the trampolines that need to be added */
	strata_create_fragment_trampolines(frag);

	/* Mark end of fragment. */
	strata_end_fragment(frag);
	
	/* assert that the fragment type was set to non-zero */
	assert(frag->ty!=STRATA_FRAG_INVALID);

	return frag;
}


/* The next two functions manage the builder's work list of fragments.  Items
 * added to the work list will get added to the fragment cache in FIFO order.
 * We use a linked list to represent the queue.  The static globals head &
 * tail point to the head and tail of the queue respectively.  We enqueue at 
 * the tail and dequeue at the head.  The queue is empty when head points to 
 * NULL.
 */
 
/* 
 * strata_enqueue_address - Place a fragment's starting address onto the builder's work list. 
 */
void strata_enqueue_address (app_iaddr_t PC) 
{
	fragment_queue *p;

	STRATA_TRACE("Enqueue'ing 0x%08x to process later\n",PC);

	/* Allocate a new queue element and initialize its fields. */
	NEW(p,BUILDER);
	p->PC = PC;
	p->next = NULL;

	/* Link p into the queue at the tail. */
	if (TAIL != NULL) { 
		TAIL->next = p;
	}
	TAIL = p;

	/* Check for previously empty queue. */
	if (HEAD == NULL)
		HEAD = TAIL;
}

/* 
 * strata_dequeue_address - Get the next fragment starting address off of the builder's work list. 
 */
app_iaddr_t strata_dequeue_address (void) 
{
	fragment_queue *p;

	p = HEAD;
	if (p != NULL) {
		HEAD = HEAD->next;
		return p->PC;
	} else {
		TAIL = NULL;
		return 0;
	}
}

/* 
 * strata_reset_builder - Reset the builder. 
 */
void strata_reset_builder (void) 
{
	int i;

	for(i=0;i<PATCHTABSIZE;i++) {
		patch_tab[i] = NULL;
	}

	HEAD = TAIL = NULL;

	strata_deallocate(BUILDER);
}

/* Initialize the builder. */
void strata_init_builder (void) 
{

	strata_entrance_count = 0;

	/* Initialize target specific builder stuff. */
	(*TI.init)();

	/* Reset builder data structures. */
	strata_reset_builder();
}

/* Restart the builder. */
void strata_restart_builder (void) {
	extern int targ_opt_fast_return;
	assert(targ_opt_fast_return==FALSE);

	strata_reset_builder();
	longjmp(strata_build_env,0);
}

/* Link all trampolines with target PC that were installed before the 
 * fragment from PC had been copied to fragment cache location fPC.
 * 
 * NOTE: Patches aren't removed after they have been applied.  This
 * simplifies the code, but could hamper performance.  This merits 
 * looking at before release. 
 */ 
void strata_apply_patches (strata_fragment *frag) {
	app_iaddr_t h;
	strata_patch *cur;

	STRATA_TRACE("Applying patches for 0x%08x => 0x%08x\n",frag->PC,frag->fPC);

	h = frag->PC % PATCHTABSIZE;
	cur = patch_tab[h];
	while(cur != NULL) {
		if (!cur->patched && cur->PC == frag->PC) {
			strata_frag_control_edge(cur->frag,frag);
			strata_remove_create_tramp_entry(cur);
			(*TI.patch)(cur,frag->fPC);
			cur->patched = 1;
		}
		cur = cur->next;
	}
}


/*
 * This is a list of patches that needs to be applied for the current fragment.
 */
strata_patch* tramplist=NULL;

/* 
 * strata_create_trampoline_later - Record that the branch in patch->u.loc needs to temporarily go
 * to a trampoline.  However, we can't emit that trampoline now
 * because we're not anywhere near done with emitting this fragment.
 * Consequently, we'll fix up this branch later (in end_fragment)
 * and emit a trampoline.
 */ 
void strata_create_trampoline_later(strata_patch *patch, app_iaddr_t to_PC)
{
	app_iaddr_t h;

	assert(patch);


	/* tracing help */
	if (patch->ty == PATCH_SWITCH) 
	{
		assert(0);
	} 
	else 
	{
		STRATA_TRACE("Location %08x will have a tramp added after this fragment build\n",
			     patch->u.loc,to_PC);
	}

	patch->PC=to_PC;


	/* Install the patch into add trampoline list */
	patch->next=tramplist;
	tramplist=patch;
}

/*
 * Create all the trampolines that this fragments needs
 */
void strata_create_fragment_trampolines(strata_fragment *frag)
{
	/* loop over the tramplist, creating trampolines as we go */
	while(tramplist)
	{
		/* create this trampoline, we'll need the target's help */
		targ_create_trampoline(frag,tramplist);
	
		/* next trampoline */
		tramplist=tramplist->next;
	}
	return;
}

/*
 * strata_remove_create_tramp_entry - Remove an entry from the create
 * trampoline list.  This is sometimes necessary when we patch before
 * we finish the fragment (sometimes this happens when we create PC mappings).
 */
void strata_remove_create_tramp_entry(strata_patch* cur)
{
	strata_patch* ttramp=tramplist;
	strata_patch* prev=NULL;

	/* examine each entry on the tramp lines */
	while(ttramp)
	{
		/* match:  remove entry */
		if(ttramp->PC==cur->PC)
		{
			/* note:  freeing of list entries isn't necessary, as they're arena allocated.
			 * We could put them into a list of free entries, if we had a mechanism for it 
			 */
			if(!prev)
			{
				/* head of list, easy removal */
				tramplist=tramplist->next;
			}
			else
			{
				/* make prev entry's next ptr point to cur entry next */
				prev->next=ttramp->next;
			}						
		}

		/* keep track of the previous one for removal purposes, and move to the next one */
		prev=ttramp;
		ttramp=ttramp->next;
	}
	return;
}


/*
 * strata_patch_later - Add patch as a list of fragment addresses that need to be fixed 
 * when targPC is translated.
 */
void strata_patch_later (strata_patch *patch, app_iaddr_t targPC) 
{
	app_iaddr_t h;

	assert(patch);

	if (patch->ty == PATCH_SWITCH) {
		STRATA_TRACE("Table %08x, element %08x will be patched when %08x arrives\n",
			     patch->u.sw.table_base,patch->u.sw.table_entry,targPC);
	} else {
		STRATA_TRACE("Location %08x will be patched when %08x arrives\n",
			     patch->u.loc,targPC);
	}


	/* Initialize the patch. */
	patch->PC = targPC;
	patch->patched = 0;

	/* Install the patch into the patch table. */
	h = patch->PC % PATCHTABSIZE;
	patch->next = patch_tab[h];
	patch_tab[h] = patch;
}

/*
 *  strata_create_patch_with_type - Create a simple patch with a f$ address and a type, which may be
 *  a target defined type.
 */
strata_patch *strata_create_patch_with_type(strata_fragment *frag, fcache_iaddr_t loc, 
	strata_patch_type_t ty)
{
	strata_patch *patch;
	NEW(patch,FCACHE);
	patch->ty = ty;
	patch->frag = frag;
	patch->u.loc = loc;

	return patch;
	
}

/* Allocate a trampoline patch. */
strata_patch *strata_patch_tramp (strata_fragment *frag, fcache_iaddr_t loc) {
	return strata_create_patch_with_type(frag,loc,PATCH_TRAMP);
}
/* Allocate for a return address. */
strata_patch *strata_patch_alt_retaddr (strata_fragment *frag, fcache_iaddr_t loc) {
	return strata_create_patch_with_type(frag,loc,PATCH_ALT_RETADDR);
}
/* Allocate for a callsite address; used when partial inlining is off */
strata_patch *strata_patch_callsite(strata_fragment *frag, app_iaddr_t loc) {
	return strata_create_patch_with_type(frag,loc,PATCH_CALLSITE);
}

/* Allocate for a return address. */
strata_patch *strata_patch_retaddr (strata_fragment *frag, fcache_iaddr_t loc) {
	return strata_create_patch_with_type(frag,loc,PATCH_RETADDR);
}

/* Allocate a patch for a switch trampoline entry. */
strata_patch *strata_patch_switch (strata_fragment *frag, unsigned table_base, unsigned table_entry) {
        strata_patch *patch;

        NEW(patch,FCACHE);
        patch->ty = PATCH_SWITCH;
        patch->frag = frag;
        patch->u.sw.table_base = table_base;
        patch->u.sw.table_entry = table_entry;

        return patch;
}

/*
 * strata_add_pc_mapping - create a fake fragment which is a mapping of an frag_PC to an app_PC.
 */
void strata_add_pc_mapping(app_iaddr_t PC, fcache_iaddr_t fPC)
{
	strata_fragment *frag=NULL;
#define strata_opt_add_pc_mappings 1

	if(!strata_opt_add_pc_mappings)
		return;
	if((void*)PC==(void*)NULL)
	{
		return;
	}

	frag = strata_create_fragment(PC);
	frag->fPC=fPC;
	frag->last_fPC=fPC;
	frag->ty=STRATA_FRAG_PC_MAPPING;

	strata_apply_patches(frag);
}