/* Major data structures in the FT-Linda TS managers. Some of the minor data * structures and unimportant fields in the following data structures have been * ommitted for brevity and clarity. They have also been reordered for clarity. */ /* request_kind_t tracks the kind of request request_t deals with. */ typedef enum { REQ_AGS, /* a normal < ... => ... > command */ REQ_NEW_LPID, /* a request for a logical PID */ REQ_TS_CREATE, /* create a replicated TS */ REQ_TS_DESTROY, /* destroy a replicated TS */ REQ_FAIL_NOTIFY, /* notify TS replicas of a host failure */ REQ_NEW_FAILURE_ID /* allocate a new failure ID */ } request_kind_t; @\newpage /* request_t is what is passed from the FT-Linda application to the FT-Linda RTS. */ typedef struct request_t { request_kind_t r_kind; /* what kind of request */ guard_kind_t r_guards_kind; /* absent, blocking, boolean */ resilience_t r_guards_resilience; /* resilience of guards */ scope_t r_guards_scope; /* scope of guards */ char r_filename[MAX_FILENAME+1]; /* filename of request*/ int r_starting_line; /* line <...> started on */ int r_num_branches; /* number of branches */ branch_t r_branch[MAX_BRANCHES]; /* each guard => body */ int r_branch_chosen; /* which branch did we do? */ TS_HANDLE_T r_ts_handle; /* which TS to destroy */ UCHAR r_guard_return_val; /* return val for => */ /* r_id is used by non-AGS requests depending on what its r_kind is: * * REQ_TS_ID: TS id allocated * REQ_LPID: LPID allocated * REQ_CREATE: TS index of created TS * REQ_DESTROY: TS index of destroyed TS * REQ_FAIL_NOTIFY: host that failed * REQ_NEW_FAILURE_ID: failure ID allocated * */ int r_id; int r_lpid; /* LPID of request originator */ int r_rep_seqn; /* sequence number for id */ int r_next_offset; /* next offset into r_actual[]*/ /* unresolved opcode args, i.e. one where at least one argument is * P_FORMAL_VAL so the GC couldn't evaluate. */ opcode_args_t r_opcode_args [MAX_OPCODES][MAX_OPCODE_ARGS]; int r_cookie; /* magic cookie to try to detect * corruption of request * structure. */ int r_times_called; /* times the AGS has been * executed */ int r_host; /* host the request sent from*/ double r_pad1; /* ensure following aligned*/ UCHAR r_formal[FORMALSIZE]; /* area to store all the * formals for the * chosen branch. */ double r_pad2; /* ensure following aligned*/ UCHAR r_actual[MAX_ACTUALS_SIZE]; } request_t; @\newpage /* * a branch is one guard => body */ typedef struct branch_t { UCHAR b_guard_present; /* is there a guard? */ UCHAR b_guard_negated; /* is guard negated with ``not'' ??*/ op_t b_guard; /* guard of the branch */ op_t b_body[MAX_BODY]; /* body of the branch */ int b_body_size; /* no of ops in body */ int b_body_next_idx[MAX_BODY];/* ordering of body ops; 0, then * next_idx[0], ... Need cause a * move must generate outs before * next op */ int b_formal_offset[MAX_FORMALS]; /* offset for each formal * into r_formal[]. */ stub_t *b_stubptr; /* RTS ptr to branch stub */ } branch_t; /* param_t tracks what type of parameters each TS op have. The values of some parameters * (P_FORMAL_VAL below) will not have their values known until the request has been received * at each replica, since they are a reference to the value of a variable that was a formal * in an earlier op in the same <...>. These can occur either as * parameters or as arguments to an opcode parameter. For example, in * * < in(FOO, ?x) => out(FEE, x, MAX(X,1) ) > * * x is P_FORMAL in the in(FOO...) but in out(FEE... is P_FORMAL_VAL * both as a parameter by itsself and as an argument to opcode MAX. * The order of the literals used here is important. Opcodes must come last, * and the first opcode must be P_OP_MIN. This is so the RTS can quickly test * whether or not a param is an opcode. */ typedef enum { P_TYPENAME, /* Linda type, actual or formal */ P_FORMAL_VAR, /* ?var */ P_VAL, /* constant (later expr?) */ P_FORMAL_VAL, /* val of var that was a formal * earlier in the same branch */ P_OP_MIN, P_OP_MAX, P_OP_MINUS, P_OP_PLUS, /* P_OP_xxx is opcode xxx */ P_OP_LOOKUP1, P_OP_LOOKUP2, P_OP_LOOKUP3 } param_t; @\newpage /* optype_t denotes Linda primitives; op_t stores needed info for them. */ typedef enum { OP_IN, OP_INP, OP_RD, OP_RDP, OP_MOVE, OP_COPY, OP_OUT} optype_t; /* guard_kind_t tells what kind the guards are (they all must be the same) */ typedef enum {g_absent, g_blocking, g_boolean} guard_kind_t; /* we track the arguments for opcode calls. If none of the agruments * are P_FORMAL_VAL then they are all known while the request is being * filled in by the GC. In this case the opcode will be evaluated * and the param listed as P_VAL. Thus, P_OP... params only occur * when arg(s) are P_FORMAL_VAL. (MAY CHANGE FOR SIMJPLICITY) */ typedef struct { int oa_formal_index; /* index into request.bindings if param is FORMAL_VAL * or -1 if arg val is in op_arg_value.*/ int oa_op_arg_value; /* LIMITATION: only ints for opcode args * for now. Could later make this a union. */ } opcode_args_t; /* A stub_t variable represents one branch of a request in the RTS. It is * enqueued on a queue based on the hash value of the branch's guard. */ typedef struct stub_t { struct request_t *st_request; /* request for the given stub */ int st_branch_index; /* branch # of corresponding branch for this stub */ BOOL is_blocked; /* is this blocked? else on candidateQ*/ } stub_t; /* ts_t is a tuple space. */ typedef struct ts { Q_t ts_blocked[MAX_HASH]; /* stubs for blocked guards */ Q_t ts_tuples[MAX_HASH]; /* tuples in the TS */ } ts_t; @\newpage /* op_t is the data structure for both ops in an AGS and also tuples in TS. If the op is * in an AGS then the actuals' data will be stored in the request's r_actual[] area, otherwise * the tuple's actuals will be stored in op.o_actual[]. When the TS managers create a tuple from * an out op they allocate an op with enough room at the end for o_acutal[] to fit all the actual data. */ typedef struct op_t { Q_t o_links; /* RTS links + key; MUST BE FIRST */ TIME_T o_time; /* RTS time stamp; MUST FOLLOW LINKS */ TS_HANDLE_T o_ts[2]; /* TS or TSs involved in this op */ optype_t o_optype; /* operator */ param_t o_param[NARITY]; /* kind of parameter. ?? */ /* o_idx[i] is used in different ways, as an index into another array. * The way is it used is a function of o_param[i] : * case P_FORMAL_VAR: * case P_FORMAL_VAL: * Here o_idx[i] tells which formal # that parameter i is * for the branch. This can be used as follows to find * where to store the formal (P_FORMAL_VAR) or where to * retrieve its value from (P_FORMAL_VAL): * formal_idx = tuple.o_idx[i] * offset = b_formal_offset[formal_idx] * formal_address = &(r_formal[offset]) * case P_OP_xxx: * Here o_idx[i] tells which unresolved opcode # that parameter * i is for this request. (Unresolved opcodes are where at * least one of the arguments is P_FORMAL_VAL and thus the * GC can't evaluate it and convert it to P_VAL.) The info * for this opcode is stored in r_opcode_args[o_idx[i]]. */ UCHAR o_idx[NARITY]; /* Let start = o_data_start[i] and stop = o_data_stop[i]. Then parameter i's data is in * locations [start..stop) of either tuple.o_actual[] or request.r_actual[], depending * on which case the parameter is. */ UWORD o_data_start[NARITY]; UWORD o_data_stop[NARITY]; UWORD o_arity; /* number of params MAY GO AWAY */ long o_polarity; /* actual/formal; assumes NARITY <= 32 */ int o_linenum; /* starting line of op */ int o_type; /* tuple type, aka the tuple's index. */ int o_hash; /* hash value;f(type,param1) */ double o_pad1; /* ensure o_actual[] aligned */ UCHAR o_actual[1]; /* area for actual (P_VAL) data if this op is a tuple. */ } op_t;