/***************************************************************************** * Author: Lance C. Luvaul * * * * Title: Evol * * * * Date: January 1997 - Present * * * * Invocation: ./evol [<parameters initialization file>] * * * * Description: Evol is a software emulation of a virtual computer designed * * to provide self-replicating programs a mutable environment * * in which to reproduce. Like Avida, Evol was inspired by * * Thomas Ray's Tierra system. * * * * Features: interrupt facility to change various parameters in realtime * * viewport onto the breeding grounds (hex or human readable) * * realtime instruction histogram * * initialization file for storing parameter values * * rudimentary debugger (step/auto mode) * * conditionally compiled sanity checks * * point and line mutations * * * * Notes: Reaper's "queue" (RQ) is now sorted 1st by error, 2nd by * * age, and 3rd by id (to resolve conflicts where two CPUs have * * the same error and age values) to prevent tight bugs (which * * accrue no errors nor reproduce) from tying up system re- * * sources. This could introduce selective pressure against * * large ids. * * * * Add ability to save state of Evol to a file and the ability * * to restore the state from a file. Partly done: g_space is * * saved to a file named "state" via the 'v' function of the * * interrupt facility. * * * * User defined instruction sets? Would be difficult. * * * * Need to complete coding the MEXEC and REPEAT instructions. * * * * Would like to make consistent tests for the various cond- * * itions present. There are several ways to test for BOM in- * * validness, for example. Find the best way and make the code * * consistent with that. * * * * Three locations in the code run thru all the tests required * * for a bug to read a value from memory [i_read(), main(), and * * i_inline()]. Make one routine and call it. * * * * Tree "fullness" stats have shown a need for AVL trees (BSTs * * that retain optimum fullness for optimum search speed) * * * * Use a linked list of RANGE structures for more efficient CIP * * and BIP. Stats output has shown the current method for ob- * * taining IDs is inefficient. Additionally, the old method's * * use of g_l(b|c)r was causing seed 2 to fail to fill g_space * * properly; this may be an issue with the RANGE linked list * * method as well... * * * * Use the regs array for fl and pc (cid, age, err)? * * * * Maybe some more realistic time costs for the instructions? * * Could determine the real average time it takes to execute an * * instruction and use that. Maybe a real-time running/rolling * * average, used to update the time cost field during execution * * (would accurately determine [thru convergence] the true time * * cost regardless of the computer architecture). * * * * Special case 0 in i_revoke. * * * * Add another p_iface option: a realtime view of the ARL cloud * * * * Implement PC tracker and viewport pan ability to pan to * * where the action is concentrated * * * * Thanks: Mark York, for convincing me I could do it. * * Jack Wells, for letting me bounce ideas off of him. * * Helen O'Malley, for her patience. * * Jesse Lynch, for the multiple key BST ideas. * *****************************************************************************/ /***************************************************************************** * Some acronyms/terminology/abbreviations... * * ------------------------------------+------------------------------------ * * BOM - Block Of Memory | CPU - Central Processing Unit * * ARL - Access ReLation | * * CB - Communications Buffer | WB - Work Buffer * * PC - Program Counter | TS - Time Slice * * BST - Binary Search Tree | RL - Range List * * RQ - Reaper's Queue | EQ - Execution Queue * * [S|D]LL - [Sing|Doub]ly Linked List | [S|D]LR - [Sing|Doub]ly Linked Ring * * [S|D]LT - [Sing|Doub]ly Linked Tree | [S|M]KT - [Single|Multiple] Key Tre * * [B|C]S - [Bom|Cpu] Store | * * [B|C]ID - [Bom|Cpu] IDentifier | [B|C]IP - [Bom|Cpu] Identifier Pool * * [B|C]AT - [Bom|Cpu] Access Tree | [B|C]OT - [Bom|Cpu] Ownership Tree * * ACT - Access Control Tree | OCT - Ownership Control Tree * * AKA - Also Known As | ATP - At This Point * * BCZ - BeCaus(Z)e | IFF - IF and only iF * * [M]TU - [Mean] Time Units | DLMKBST - take a guess * *****************************************************************************/ /***************************************************************************** * includes * *****************************************************************************/ #include <stdio.h> /* vprintf, perror */ #include <stdlib.h> /* rand, RAND_MAX, free, malloc, atexit, exit, abort */ #include <stdarg.h> /* va_list, va_start, va_arg, va_end */ #include <signal.h> /* signal, SIGINT, SIG_IGN */ #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> /* open, O_WRONLY */ #include <unistd.h> /* close, write, sleep */ #include <math.h> /* log2, ceil */ /*#include <curses.h>*/ /* WINDOW, mvwprintw, initscr, endwin */ #include <grx20.h> #include <grxkeys.h> /***************************************************************************** * macros (#defines) * *****************************************************************************/ /* COLORS */ #define BLACK g_egacolors[0] #define BLUE g_egacolors[1] #define GREEN g_egacolors[2] #define CYAN g_egacolors[3] #define RED g_egacolors[4] #define MAGENTA g_egacolors[5] #define BROWN g_egacolors[6] #define LIGHTGRAY g_egacolors[7] #define DARKGRAY g_egacolors[8] #define LIGHTBLUE g_egacolors[9] #define LIGHTGREEN g_egacolors[10] #define LIGHTCYAN g_egacolors[11] #define LIGHTRED g_egacolors[12] #define LIGHTMAGENTA g_egacolors[13] #define YELLOW g_egacolors[14] #define WHITE g_egacolors[15] /* INSTRUCTIONS */ #define _UMASK 0x00 #define _COMM 0x01 #define _WORK 0x02 #define _ADD 0x03 #define _SUB 0x04 #define _MEXEC 0x05 /* coding incomplete */ #define _ZERO 0x06 #define _SHL 0x07 #define _SHR 0x08 #define _LSB0 0x09 #define _LSB1 0x0a #define _BAND 0x0b #define _BOR 0x0c #define _BXOR 0x0d #define _BINV 0x0e #define _READ 0x0f #define _WRITE 0x10 #define _THROW 0x11 #define _CATCH 0x12 #define _ALLOC 0x13 #define _FREE 0x14 #define _FORK 0x15 #define _TERM 0x16 #define _CHOWN 0x17 #define _GRANT 0x18 #define _REVOKE 0x19 #define _TEST 0x1a #define _HERE 0x1b #define _FTOW 0x1c #define _ITOW 0x1d #define _RTOW 0x1e #define _JUMP 0x1f #define _WTOR 0x20 #define _NOP 0x21 #define _PASS 0x22 #define _REPEAT 0x23 /* coding incomplete */ #define _SPIN 0x24 #define _DUP 0x25 #define _INLINE 0x26 #define _CLR 0x27 #define _LAST_INS _CLR #define _NINSTRUCTIONS (_LAST_INS+1) /* total instructions */ /* STATUS CODES: return values from the execution of an instruction */ #define _SUCCESS 0 #define _SUCCESS_FORK 1 #define _FAILURE_BNV 2 #define _UNUSED 3 /* unused */ #define _FAILURE_CNV 4 #define _FAILURE_WBE 5 /* frequently indicates insufficient args */ #define _FAILURE_WBF 6 /* frequently indicates no room for results */ #define _FAILURE_CBE 7 #define _FAILURE_CBF 8 #define _FAILURE_NRA 9 #define _FAILURE_NWA 10 #define _FAILURE_INV 11 #define _FAILURE_NER 12 #define _FAILURE_BNO 13 #define _FAILURE_BNE 14 #define _FAILURE_CNE 15 #define _LAST_STATCODE _FAILURE_CNE /* _NSTATCODES is additionally constrained by the number of bits reserved in * the flags register for a status code. If this number is n, say, then * _NSTATCODES can be no larger than 2^n. */ #define _NSTATCODES (_LAST_STATCODE+1) /* total error codes */ /* COMPILATION PARAMETERS: these parameters are used to selectively exclude * various aspects of Evol from compilation (to increase execution speed). if * defined, include for compilataion; if not, exclude */ #define _SANITY_CHECK /* force Evol to thoroughly double-check its logic */ #define _REALTIME_STATS /* compute various stats in realtime */ #undef _CURSES_INTERFACE /* provide curses-based interface */ /* FLAG BITS: CPU allocation defaults are listed */ #define _FLAG_LEAST_SIG_BIT 0 /* 0-3 reserved for errcodes */ #define _FLAG_UMASK_OWNER_READ 4 /* default = hi (on) */ #define _FLAG_UMASK_OWNER_WRITE 5 /* default = hi (on) */ #define _FLAG_UMASK_WORLD_READ 6 /* default = hi (on) */ #define _FLAG_UMASK_WORLD_WRITE 7 /* default = hi (on) */ #define _FLAG_ROLL_OVER 15 #define _FLAG_DISCARD_BIT 16 #define _FLAG_PASS 17 /* default = lo (off) */ #define _FLAG_WB_QUEUE_OR_STACK 27 /* default = hi (stack) */ #define _FLAG_WB_PRESERVE_OR_OVERWRITE 28 /* default = hi (overwrite) */ #define _FLAG_CB_QUEUE_OR_STACK 29 /* default = lo (queue) */ #define _FLAG_CB_PRESERVE_OR_OVERWRITE 30 /* default = lo (preserve) */ #define _FLAG_INCREASE_OR_DECREASE 31 /* default = lo (increase) */ #define _FLAG_MOST_SIG_BIT 31 /* CHARACTER CELL SIZE IN PIXELS */ #define _CHAR_CELL_WIDTH 6 /* Based on GrFont_PC6x8 */ #define _CHAR_CELL_HEIGHT 8 /* Based on GrFont_PC6x8 */ /* ON SCREEN PLACEMENTS IN CHARACTERS */ #define _OSP_CLINE_HEIGHT 2 /* Control Line Height */ #define _OSP_GSTATS_XOS 0 /* Global Stats column X Offset */ #define _OSP_GSTATS_YOS 0 /* Global Stats row Y Offset */ #define _OSP_GSTATS_HEAD_WIDTH 9 /* Global Stats Headings column Width */ #define _OSP_GSTATS_DATA_WIDTH 21 /* Global Stats Data column Width */ #define _OSP_LSTATS_XOS 31 /* Local Stats column X Offset */ #define _OSP_LSTATS_YOS 0 /* Local Stats row Y Offset */ #define _OSP_LSTATS_HEAD_WIDTH 6 /* Local Stats Headings column Width */ #define _OSP_LSTATS_DATA_WIDTH 30 /* Local Stats Data column Width */ #define _OSP_LSTATS2_XOS 68 /* Local Stats 2 column X Offset */ #define _OSP_LSTATS2_YOS 0 /* Local Stats 2 row Y Offset */ #define _OSP_LSTATS3_XOS 77 /* Local Stats 2 column X Offset */ #define _OSP_LSTATS3_YOS 0 /* Local Stats 2 row Y Offset */ #define _OSP_VPORT_YOS 11 /* Viewport Y Offset (Vertical) */ /* BOOLEAN VALUES */ #define _TRUE 1 #define _FALSE 0 /* MASKS TO EXTRACT SCREEN TEXT COMPONENTS */ #define _STEXT_MASK_CHAR 0x00ff #define _STEXT_MASK_ATTR 0xff00 /* Short End_Of_Line notation (for use with initialization file) */ #define _EOL(file) while ('\n' != fgetc(file)) /* _MIN() and _MAX() FUNCTIONS: don't use args with side-effects */ #define _MIN(x,y) ((x)<(y))?(x):(y) #define _MAX(x,y) ((x)>(y))?(x):(y) /* Increased readability notations for various bit tests */ #define _DIRECTION(cpu) btest((cpu)->fl, _FLAG_INCREASE_OR_DECREASE) #define _OWNER_READ(cpu) btest((cpu)->fl, _FLAG_UMASK_OWNER_READ) #define _OWNER_WRITE(cpu) btest((cpu)->fl, _FLAG_UMASK_OWNER_WRITE) #define _WORLD_READ(cpu) btest((cpu)->fl, _FLAG_UMASK_WORLD_READ) #define _WORLD_WRITE(cpu) btest((cpu)->fl, _FLAG_UMASK_WORLD_WRITE) #define _READABLE(arl) btest((arl)->priv, 0) #define _WRITABLE(arl) btest((arl)->priv, 1) /* Increased readability notations for various other conditions */ #define _AINVALID(adr) (p_bom_size > (adr)) || ((adr) >= p_bom_size*p_max_boms) #define _BINVALID(bid) (1 > (bid)) || ((bid) >= p_max_boms) #define _CINVALID(cid) (1 > (cid)) || ((cid) >= p_max_cpus) /* BST say functions (part of the BST print functions) */ #define bp_say(_level,_root) say(p_out_all, "%*c[%u,%u]\n", _level, ' ', \ _root->a, _root->b); #define cs_say(_level,_root) say(p_out_dbg, "%*c%u\n", _level, ' ', \ _root->cid); #define bs_say(_level,_root) say(p_out_dbg, "%*c%u\n", _level, ' ', \ _root->bid); #define rq_say(_level,_root) say(p_out_dbg, "%*cerr=%u, age=%u, cid=%u\n", \ _level, ' ', _root->err, _root->age, _root->cid); /* BST GET FUNCTION: This macro generates code for a function definition. In * particular, it generates the code for a binary search tree Get function * (aka Retrieve or Find). It returns a pointer to the item sought after (if * found within the binary search tree) or NULL (if not found). */ #define DEFINE_BST_GET_FUNCTION(Name,T,Tkey,Tlptr,Trptr) \ T* Name(T *bst_root, U4 bst_target) { \ T *curr; \ \ curr = bst_root; \ while (curr) { \ if (bst_target < curr->Tkey) \ curr = curr->Tlptr; \ else if (bst_target > curr->Tkey) \ curr = curr->Trptr; \ else \ return curr; \ } \ return NULL; \ } #define DEFINE_BST_INSERT_FUNCTION(Name,T,Tcompare,Tlptr,Trptr) \ BOOL Name(T **_root, T *_new) { \ T *curr; \ T *prev; \ int res; \ \ if (!_new) \ return _FALSE; \ \ if (!*_root) { \ *_root = _new; \ return _TRUE; \ } \ \ curr = prev = *_root; \ while (curr) { \ prev = curr; \ res = Tcompare(_new, curr); \ if (res < 0) \ curr = curr->Tlptr; \ else if (res > 0) \ curr = curr->Trptr; \ else \ return _FALSE; \ } \ \ ((Tcompare(_new, prev) < 0) ? prev->Tlptr : prev->Trptr) = _new; \ \ return _TRUE; \ } #define DEFINE_ID_COMPARE_FUNCTION(Name,T,Tchar) \ int Name(T *a, T *b) { \ if (a->Tchar##id < b->Tchar##id) \ return -15; \ else if (a->Tchar##id > b->Tchar##id) \ return 15; \ else \ return 0; \ } /* BST REMOVE FUNCTION: This macro generates code for a function definition. * In particular, it generates the code for a binary search tree Remove * function. It returns a pointer to the item removed. */ #define DEFINE_BST_REMOVE_FUNCTION(Name,T,Tlptr,Trptr) \ T* Name(T **_root, T *_curr1, T *_prev1) { \ T *curr2; \ T *prev2; \ \ if (!_curr1->Tlptr) \ if (_prev1->Tlptr == _curr1) \ _prev1->Tlptr = _curr1->Trptr; \ else if (_prev1->Trptr == _curr1) \ _prev1->Trptr = _curr1->Trptr; \ else \ *_root = _curr1->Trptr; \ \ else if (!_curr1->Trptr) \ if (_prev1->Tlptr == _curr1) \ _prev1->Tlptr = _curr1->Tlptr; \ else if (_prev1->Trptr == _curr1) \ _prev1->Trptr = _curr1->Tlptr; \ else \ *_root = _curr1->Tlptr; \ \ else { \ curr2 = prev2 = _curr1; \ prev2 = curr2; \ curr2 = curr2->Tlptr; \ while (curr2->Trptr) { \ prev2 = curr2; \ curr2 = curr2->Trptr; \ } \ \ if (_prev1->Tlptr == _curr1) \ _prev1->Tlptr = curr2; \ else if (_prev1->Trptr == _curr1) \ _prev1->Trptr = curr2; \ else \ *_root = curr2; \ if (prev2->Tlptr == curr2) \ prev2->Tlptr = _curr1; \ else \ prev2->Trptr = _curr1; \ swap_U4((U4 *)&(_curr1->Tlptr), (U4 *)&(curr2->Tlptr)); \ swap_U4((U4 *)&(_curr1->Trptr), (U4 *)&(curr2->Trptr)); \ \ if (_curr1 == prev2) \ prev2 = curr2; \ ((prev2->Tlptr == _curr1) ? prev2->Tlptr : prev2->Trptr) = \ _curr1->Tlptr; \ } \ \ _curr1->Tlptr = _curr1->Trptr = NULL; \ return _curr1; \ } /* BST FIND AND REMOVE FUNCTION: This macro generates code for a function * definition. In particular, it generates the code for a binary search * tree FindAndRemove function. It returns NULL if the item to be removed * is not found within the binary search tree. Otherwise, it returns a * pointer to the item after removing it. */ #define DEFINE_BST_FIND_REMOVE_FUNCTION(Name,T,Tcompare,Tlptr,Trptr) \ T* Name(T **_root, T *_old) { \ T *curr1; \ T *prev1; \ T *curr2; \ T *prev2; \ int res; \ \ curr1 = prev1 = *_root; \ while (curr1) { \ res = Tcompare(_old, curr1); \ if (res < 0) { \ prev1 = curr1; \ curr1 = curr1->Tlptr; \ } \ else if (res > 0) { \ prev1 = curr1; \ curr1 = curr1->Trptr; \ } \ else { \ if (!curr1->Tlptr) \ if (prev1->Tlptr == curr1) \ prev1->Tlptr = curr1->Trptr; \ else if (prev1->Trptr == curr1) \ prev1->Trptr = curr1->Trptr; \ else \ *_root = curr1->Trptr; \ \ else if (!curr1->Trptr) \ if (prev1->Tlptr == curr1) \ prev1->Tlptr = curr1->Tlptr; \ else if (prev1->Trptr == curr1) \ prev1->Trptr = curr1->Tlptr; \ else \ *_root = curr1->Tlptr; \ \ else { \ curr2 = prev2 = curr1; \ prev2 = curr2; \ curr2 = curr2->Tlptr; \ while (curr2->Trptr) { \ prev2 = curr2; \ curr2 = curr2->Trptr; \ } \ \ if (prev1->Tlptr == curr1) \ prev1->Tlptr = curr2; \ else if (prev1->Trptr == curr1) \ prev1->Trptr = curr2; \ else \ *_root = curr2; \ if (prev2->Tlptr == curr2) \ prev2->Tlptr = curr1; \ else \ prev2->Trptr = curr1; \ swap_U4((U4 *)&(curr1->Tlptr), (U4 *)&(curr2->Tlptr)); \ swap_U4((U4 *)&(curr1->Trptr), (U4 *)&(curr2->Trptr)); \ \ if (curr1 == prev2) \ prev2 = curr2; \ ((prev2->Tlptr == curr1) ? prev2->Tlptr : prev2->Trptr) = \ curr1->Tlptr; \ } \ \ curr1->Tlptr = curr1->Trptr = NULL; \ return curr1; \ } \ } \ return NULL; \ } /* BST DEPTH FUNCTION */ #define DEFINE_BST_DEPTH_FUNCTION(Name,T,Tlptr,Trptr) \ U4 Name(T* _root) { \ U4 lside, rside; \ \ if (!_root) \ return 0; \ \ if (!_root->Tlptr) { \ if (!_root->Trptr) \ return 1; \ else \ return Name(_root->Trptr) + 1; \ } \ else { \ if (!_root->Trptr) \ return Name(_root->Tlptr) + 1; \ else { \ lside = Name(_root->Tlptr); \ rside = Name(_root->Trptr); \ return ((lside >= rside) ? lside : rside) + 1; \ } \ } \ } /* BST PRINT FUNCTION */ #define DEFINE_BST_PRINT_FUNCTION(Name,T,Tsay,Tlptr,Trptr) \ void Name(T *_root, U4 _level) { \ if (_root) { \ Name(_root->Tlptr, _level + 1); \ Tsay(_level, _root); \ Name(_root->Trptr, _level + 1); \ } \ } /* GET XID FUNCTION: returns a number between 1 and p_max_(cpu|bom)s-1 guar- * anteed not to be in the (C|B)S (unless ALL these numbers are in the * (C|B)S, then it returns 0). Removed the g_l(b|c)r facility (for short * term storage and hence quick return of most recently freed (c|b)ids) as * it was causing seed 2 to fail to fill g_space properly (may be an issue * if/when I move to a more efficient (B|C)S mechanism) */ #define DEFINE_ID_GET_FUNCTION(Tchar,T) \ U4 get_##Tchar##id(void) { \ U4 hold; \ int g_n##Tchar##fails = 0; \ \ ++g_##Tchar##hmcnt; \ if (g_n##T##s >= p_max_##T##s-1) \ return 0; \ \ for (;;) { \ \ hold = (U4)nrandom(p_max_##T##s); \ \ if ((0 != hold) && (!Tchar##s_get(g_##Tchar##s_root, hold))) { \ say(p_out_dbg, "<get_"#Tchar"id() fails: %d>", g_n##Tchar##fails); \ g_##Tchar##hmsum += g_n##Tchar##fails; \ return hold; \ } \ \ ++g_n##Tchar##fails; \ } \ } /* NEW RELATION OBJECT FUNCTION */ #define DEFINE_NEW_REL_FUNCTION(t,T) \ T* new_##t(void) { \ T *t; \ \ if (!(t = (T *)malloc(sizeof(T)))) \ return NULL; \ else { \ t->cL = t->cR = NULL; \ t->bL = t->bR = NULL; \ ++g_n##t##s; \ return t; \ } \ } /* OLD RELATION OBJECT FUNCTION */ #define DEFINE_OLD_REL_FUNCTION(t,T) \ void old_##t(T *t) { \ if (t) { \ say(p_out_obj, "<old_"#t": CPU=%u, BOM=%u>", t->cid, t->bid); \ free(t); \ --g_n##t##s; \ } \ } /* BUFFER RESTORE FUNCTION: can be used to restore the buffer to its previous * state if it is determined that execution of an instruction cannot continue * for some reason (most usually not enough args or not enough space in buff- * er for results), the result of which is an instruction that is nondestruc- * tive to a cell's state, regardless of success or failure. if n=positive, * tries to restore the last n elements that previously occupied the buffer. * if n=negative, tries to remove -n elements currently in the buffer. re- * turns the number of elements restored (a positive number) or removed (neg- * ated). */ #define DEFINE_XB_RESTORE_FUNCTION(Tbuff, Tparam, Tflag) \ int Tbuff##_restore(CPU *cpu, int n) { \ int i; \ int count = 0; \ \ if (n>0) \ for (i=0; i<n; ++i) { \ if (++(cpu->Tbuff.size) > Tparam) { \ cpu->Tbuff.size = Tparam; \ return count; \ } \ ++count; \ if (!btest(cpu->fl, Tflag)) \ if (--(cpu->Tbuff.head) < 0) \ cpu->Tbuff.head = Tparam - 1; \ } \ \ else if (n<0) \ for (i=0; i<-n; ++i) { \ if (--(cpu->Tbuff.size) < 0) { \ cpu->Tbuff.size = 0; \ return count; \ } \ --count; \ if (!btest(cpu->fl, Tflag)) \ if (++(cpu->Tbuff.head) >= Tparam) \ cpu->Tbuff.head = 0; \ } \ \ return count; \ } #define DEFINE_SWAP_FUNCTION(T) \ void swap_##T(T *a, T *b) { \ *a = *a ^ *b; \ *b = *a ^ *b; \ *a = *a ^ *b; \ } /* ASSERT FUNCTION: * assert_f(): unlike ANSI C assert(), still evaluates the asserted * expression (typically a function) if _SANITY_CHECK is not defined. * This is so that I can specify * assert_f(wb_get(this_cpu, &arg)); * instead of * ret = wb_get(this_cpu, &arg); assert(ret); * If the expression contains a call to a function such as * 1 == wb_restore(...) * use assert_f() instead. * assert_e(): operates similar to ANSI C assert(). */ #if defined(_SANITY_CHECK) #define assert_e(expr) \ if (!(expr)) { \ if (p_iface) { \ xyprintf(0, 0, BLACK, WHITE, "\n%s%s\n%s%s\n%s%d\n\n", \ "Assertion failed: ", #expr, "in file ", __FILE__, \ "at line ", __LINE__); \ GrKeyRead(); \ } \ else { \ say(_TRUE, "\n%s%s\n%s%s\n%s%d\n\n", "Assertion failed: ", #expr, \ "in file ", __FILE__, "at line ", __LINE__); \ } \ abort(); \ } #define assert_f(func) \ if (!(func)) { \ if (p_iface) { \ xyprintf(0, 0, BLACK, WHITE, "\n%s%s\n%s%s\n%s%d\n\n", \ "Assertion failed: ", #func, "in file ", __FILE__, \ "at line ", __LINE__); \ GrKeyRead(); \ } \ else { \ say(_TRUE, "\n%s%s\n%s%s\n%s%d\n\n", "Assertion failed: ", #func, \ "in file ", __FILE__, "at line ", __LINE__); \ } \ abort(); \ } #else #define assert_e(expr) #define assert_f(func) func #endif /***************************************************************************** * typedefs * *****************************************************************************/ typedef unsigned char U1; typedef signed char S1; typedef unsigned short int U2; typedef signed short int S2; typedef unsigned int U4; typedef signed int S4; typedef int BOOL; typedef unsigned short int STEXT; /* screen text: character + attributes */ /* may in future be used for more efficient BIP and CIP */ typedef struct _range_ { U4 a; U4 b; struct _range_ *p_L; struct _range_ *p_R; } RANGE; typedef struct { unsigned long a; unsigned long b; /*unsigned long c;*/ } UTIMER; typedef struct { U4 src; /* id of the cpu throwing the value */ U4 val; /* the actual value thrown by the cpu */ } PACKET; typedef struct { S4 head; S4 size; void *data; } BUFFER; /* forms the access relation between a single CPU and a single BOM */ typedef struct _arl_ { U4 cid; U4 bid; U4 priv; struct _arl_ *cL; struct _arl_ *cR; struct _arl_ *bL; struct _arl_ *bR; } ARL; /* sizeof(ARL) = 7*4 = 28 */ typedef struct _cpu_ { U4 cid; /* CPU id (unique; used as key) */ U4 age; /* age */ U4 err; /* error count */ S4 ts; /* time slice */ U4 pc; /* program counter (aka instruction pointer) */ U4 *reg; /* register bank */ U4 fl; /* flags */ BUFFER cb; /* comm buffer (initially a preserve-mode queue) */ BUFFER wb; /* work buffer (initially an overwrite-mode stack) */ ARL *bat; /* BOM access tree (the BOMs that cid can access) */ struct _bom_ *bot; /* BOM ownership tree (the BOMs that cid owns) */ struct _cpu_ *eq_N; /* used to implement the EQ */ struct _cpu_ *eq_P; /* used to implement the EQ */ struct _cpu_ *cs_L; /* used to implement the CS */ struct _cpu_ *cs_R; /* used to implement the CS */ struct _cpu_ *rq_L; /* used to implement the RQ */ struct _cpu_ *rq_R; /* used to implement the RQ */ } CPU; /* sizeof(CPU) = 21*4 = 84 */ typedef struct _bom_ { U4 bid; /* BOM id (unique; used as key) */ ARL *cat; /* CPU access tree (the CPUs with access to bid) */ CPU *cot; /* CPU ownership tree (the CPUs owning bid [only 1]) */ struct _bom_ *bs_L; /* used to implement the BS */ struct _bom_ *bs_R; /* used to implement the BS */ struct _bom_ *ot_L; /* used to implement the OT */ struct _bom_ *ot_R; /* used to implement the OT */ } BOM; /* sizeof(BOM) = 7*4 = 28 */ /***************************************************************************** * enums * *****************************************************************************/ enum sio { dummy, mutate, cell_read, cell_write, execute, /* previously "evol_read" */ initialize, /* previously "evol_write" */ touch }; enum iface { textscroll, viewport, histogram }; enum vport_cell { human, hex, pixel }; /***************************************************************************** * function prototypes * *****************************************************************************/ /* AT, OT, BS, CS, EQ, & RQ functions */ void cs_print(CPU *_root, U4 _level); /* macro-generated definition */ void bs_print(BOM *_root, U4 _level); /* macro-generated definition */ void rq_print(CPU *_root, U4 _level); /* macro-generated definition */ void eq_print(CPU *_curr); U4 cs_depth(CPU* _root); /* macro-generated definition */ U4 bs_depth(BOM* _root); /* macro-generated definition */ /*U4 bat_depth(ARL* _root);*/ /* macro-generated definition */ /*U4 cat_depth(ARL* _root);*/ /* macro-generated definition */ /*U4 bot_depth(BOM* _root);*/ /* macro-generated definition */ U4 rq_depth(CPU* _root); /* macro-generated definition */ U4 bp_depth(RANGE* _root); /* macro-generated definition */ CPU* cs_get(CPU *_root, U4 _target); /* macro-generated definition */ BOM* bs_get(BOM *_root, U4 _target); /* macro-generated definition */ ARL* bat_get(ARL *_root, U4 _target); /* macro-generated definition */ /*ARL* cat_get(ARL *_root, U4 _target);*/ /* macro-generated definition */ BOM* bot_get(BOM *_root, U4 _target); /* macro-generated definition */ CPU* rq_grab(void); int cs_compare(CPU *a, CPU *b); /* macro-generated definition */ int bs_compare(BOM *a, BOM *b); /* macro-generated definition */ int bat_compare(ARL *a, ARL *b); /* macro-generated definition */ int cat_compare(ARL *a, ARL *b); /* macro-generated definition */ int rq_compare(CPU *a, CPU *b); BOOL cs_insert(CPU **_root, CPU *_new); /* macro-generated definition */ BOOL bs_insert(BOM **_root, BOM *_new); /* macro-generated definition */ BOOL bat_insert(ARL **_root, ARL *_new); /* macro-generated definition */ BOOL cat_insert(ARL **_root, ARL *_new); /* macro-generated definition */ BOOL bot_insert(BOM **_root, BOM *_new); /* macro-generated definition */ BOOL rq_insert(CPU **_root, CPU *_new); /* macro-generated definition */ BOOL eq_insert(CPU **_curr, CPU *_new); RANGE *bp_remove(RANGE **_root, RANGE *_curr, RANGE *_prev); CPU* cs_remove(CPU **_root, CPU *_old); /* macro-generated definition */ BOM* bs_remove(BOM **_root, BOM *_old); /* macro-generated definition */ ARL* bat_remove(ARL **_root, ARL *_old); /* macro-generated definition */ ARL* cat_remove(ARL **_root, ARL *_old); /* macro-generated definition */ BOM* bot_remove(BOM **_root, BOM *_old); /* macro-generated definition */ CPU* rq_remove(CPU **_root, CPU *_old); /* macro-generated definition */ CPU* eq_remove(CPU **_curr, CPU *_old); U4 get_cid(void); /* macro-generated definition */ U4 get_bid(U4 bid); /* object functions */ CPU* new_cpu(void); BOM* new_bom(U4 bid); ARL* new_arl(void); /* macro-generated definition */ void old_cpu(CPU *cpu); void old_bom(BOM *bom); void old_arl(ARL *arl); /* macro-generated definition */ void free_cpu(CPU *cpu); void free_bom(BOM *bom); void free_arl(BOM *bom, CPU *cpu); /* flag functions */ void setb(U4 *val, int bit); void clrb(U4 *val, int bit); BOOL btest(U4 val, int bit); /* buffer functions */ BOOL wb_put(CPU *cpu, U4 val); BOOL cb_put(CPU *cpu, U4 src, U4 val); BOOL wb_get(CPU *cpu, U4 *val); BOOL cb_get(CPU *cpu, U4 *src, U4 *val); int wb_restore(CPU *cpu, int n); /* macro-generated definition */ int cb_restore(CPU *cpu, int n); /* macro-generated definition */ /* instruction functions */ int i_comm(CPU *this_cpu); int i_work(CPU *this_cpu); int i_here(CPU *this_cpu); int i_jump(CPU *this_cpu); int i_ftow(CPU *this_cpu); int i_add(CPU *this_cpu); int i_sub(CPU *this_cpu); int i_zero(CPU *this_cpu); int i_shl(CPU *this_cpu); int i_shr(CPU *this_cpu); int i_lsb0(CPU *this_cpu); int i_lsb1(CPU *this_cpu); int i_band(CPU *this_cpu); int i_bor(CPU *this_cpu); int i_bxor(CPU *this_cpu); int i_binv(CPU *this_cpu); int i_read(CPU *this_cpu); int i_write(CPU *this_cpu); int i_throw(CPU *this_cpu); int i_catch(CPU *this_cpu); int i_fork(CPU *mother); int i_alloc(CPU *this_cpu); int i_free(CPU *this_cpu); int i_term(CPU *this_cpu); int i_grant(CPU *this_cpu); int i_revoke(CPU *this_cpu); int i_chown(CPU *this_cpu); int i_test(CPU *this_cpu); int i_rtow(CPU *this_cpu); int i_itow(CPU *this_cpu); int i_wtor(CPU *this_cpu); int i_mexec(CPU *this_cpu); int i_repeat(CPU *this_cpu); int i_umask(CPU *this_cpu); int i_nop(CPU *this_cpu); int i_pass(CPU *this_cpu); int i_spin(CPU *this_cpu); int i_dup(CPU *this_cpu); int i_inline(CPU *this_cpu); int i_clr(CPU *this_cpu); /* miscellaneous functions */ void swap_U4(U4 *a, U4 *b); /* macro-generated definition */ void swap_U1(U1 *a, U1 *b); /* macro-generated definition */ void tick(int n); void init_params(char *filename); void save_state(void); int nrandom(int n); void adjust(CPU *cpu, int etime, int status); void set_statcode(CPU *cpu, int err); void nstep(U4 *pc, BOOL dir, int n); U1 spacio(U4 address, int how, U1 write_value); int say(BOOL level, char *format, ...); void compute_health(CPU *_root); void cleanup(void); void print_stats(void); void print_template(int iface); int ssprintf(STEXT *csbuff, STEXT attr, char *format, ...); int xyprintf(int x, int y, GrColor fg, GrColor bg, char *format, ...); void ssmodat(char op, STEXT attr, STEXT *csbuff, int n); float histo(int instruction); void interrupt(int sig); /***************************************************************************** * global variables * *****************************************************************************/ /* globals beginning with p_ are parameters read in from an *.ini file */ BOOL p_step; int p_seed; int p_iface; BOOL p_hist; int p_vport_cell; BOOL p_direction; BOOL p_random_space; BOOL p_out_err; BOOL p_out_ins; BOOL p_out_obj; BOOL p_out_dbg; BOOL p_out_all; BOOL p_out_stat; U4 p_vport_paint; S4 p_vport_offset; U4 p_vport_height; U4 p_vport_width; U4 p_report_freq; U4 p_pmutate_freq; U4 p_lmutate_freq; float p_multiplier; U4 p_ts_size; U4 p_cb_size; U4 p_wb_size; U4 p_nregs; U4 p_bom_size; U4 p_max_boms; U4 p_max_cpus; float p_bron; float p_cron; float p_broff; float p_croff; U4 p_max_age; U4 p_max_err; S4 p_max_ts; S4 p_min_ts; U4 p_default_flags; U1 p_fspace_read; U1 p_fspace_write; /* universal time */ UTIMER g_clock; /* curses window variables */ /*WINDOW g_win = NULL;*/ int g_lines; int g_cols; /* GRX-related globals */ GrColor *g_egacolors; GrColor g_color_pairs[2][7]; GrTextOption g_gtxo = { &GrFont_PC6x8, /* font for screen text */ {0}, /* foreground color (initial trash value) */ {0}, /* background color (initial trash value) */ GR_TEXT_RIGHT, /* text direction */ GR_ALIGN_LEFT, /* horizontal text alignment */ GR_ALIGN_TOP, /* vertical text alignment */ GR_BYTE_TEXT /* text structure */ }; U4 g_nrngs = 0; U4 g_narls = 0; U4 g_nboms = 0; U4 g_ncpus = 0; U4 g_ndead = 0; double g_health; double g_chmsum = 0; /* used to compute get_cid() efficiency */ U4 g_chmcnt = 0; /* used to compute get_cid() efficiency */ double g_bhmsum = 0; /* used to compute get_bid() efficiency */ U4 g_bhmcnt = 0; /* used to compute get_bid() efficiency */ U4 g_nbfails; U4 g_ncfails; U1 *g_space = NULL; /* vars related to the BID_POOL */ RANGE *g_bpool = NULL; /* vars related to the CID_POOL */ RANGE *g_cpool = NULL; /* vars related to the EQ (DLR) */ CPU *g_eq_curr = NULL; /* vars related to the CS (SLT, i.e. no prev ptr) */ CPU *g_cs_root = NULL; /* vars related to the BS (SLT, i.e. no prev ptr) */ BOM *g_bs_root = NULL; /* vars related to the RQ (MKT [currently]; alt. implementation: nested SKT) */ CPU *g_rq_root = NULL; /* Status code table */ struct { S4 cost; /* status penalty value */ char *text; /* string representation of status code */ } g_stab[_NSTATCODES] = { {0, "success"}, /* _SUCCESS */ {2000, "success, fork"}, /* _SUCCESS_FORK */ {6, "failure, bid not valid"}, /* _FAILURE_BNV */ {0, "unused"}, /* _UNUSED */ {6, "failure, cid not valid"}, /* _FAILURE_CNV */ {15, "failure, wb [near] empty"}, /* _FAILURE_WBE */ {15, "failure, wb [near] full"}, /* _FAILURE_WBF */ {0, "failure, cb [near] empty"}, /* _FAILURE_CBE */ {0, "failure, cb [near] full"}, /* _FAILURE_CBF */ {900, "failure, no read access"}, /* _FAILURE_NRA */ {1300, "failure, no write access"}, /* _FAILURE_NWA */ {900, "failure, invalid instruction"}, /* _FAILURE_INV */ {2, "failure, not enough resources"}, /* _FAILURE_NER */ {6, "failure, bid not owned"}, /* _FAILURE_BNO */ {5, "failure, bid nonexistant"}, /* _FAILURE_BNE */ {5, "failure, cid nonexistant"} /* _FAILURE_CNE */ }; /* Instruction table */ struct { int (*addr)(CPU*); /* function pointer to the instruction */ S4 cost; /* time penalty incurred upon execution */ char *text; /* string representation of instruction */ } g_itab[_NINSTRUCTIONS] = { {i_umask, 5, "UMASK"}, {i_comm, 4, "COMM"}, {i_work, 4, "WORK"}, {i_add, 6, "ADD"}, {i_sub, 6, "SUB"}, {i_mexec, 1, "MEXEC"}, {i_zero, 3, "ZERO"}, {i_shl, 6, "SHL"}, {i_shr, 6, "SHR"}, {i_lsb0, 3, "LSB0"}, {i_lsb1, 3, "LSB1"}, {i_band, 5, "BAND"}, {i_bor, 5, "BOR"}, {i_bxor, 5, "BXOR"}, {i_binv, 5, "BINV"}, {i_read, 9, "READ"}, {i_write, 9, "WRITE"}, {i_throw, 8, "THROW"}, {i_catch, 7, "CATCH"}, {i_alloc, 11, "ALLOC"}, {i_free, 10, "FREE"}, {i_fork, 8, "FORK"}, {i_term, 10, "TERM"}, {i_chown, 13, "CHOWN"}, {i_grant, 12, "GRANT"}, {i_revoke, 13, "REVOKE"}, {i_test, 3, "TEST"}, {i_here, 3, "HERE"}, {i_ftow, 3, "FTOW"}, {i_itow, 3, "ITOW"}, {i_rtow, 3, "RTOW"}, {i_jump, 3, "JUMP"}, {i_wtor, 3, "WTOR"}, {i_nop, 1, "NOP"}, {i_pass, 2, "PASS"}, {i_repeat, 1, "REPEAT"}, {i_spin, 2, "SPIN"}, {i_dup, 5, "DUP"}, {i_inline, 5, "INLINE"}, {i_clr, 2, "CLR"} }; /* my first try (too perfect, resulted in little variation, replicates * continuously); code non-functional now due to changes in register bank * implementation... included here now only for historical reasons. */ #if 0 U1 g_seed[45] = { _HERE, /* :from */ _WB2R0, /* R0=:from */ _ALLOC, _WB2R1, /* R1=:to */ _ZERO, _WB2R2, /* R2=<instructions copied> */ _ZERO, /* :copy-5 */ _LSB1, _SHL, _SHL, _LSB1, _HERE, /* :copy */ _SUB, /* S0=:copy-5 */ _R22WB, /* . */ _R02WB, /* | copy [:from+R2] */ _ADD, /* | to :to+R2 */ _READ, /* | */ _R22WB, /* | */ _R12WB, /* | */ _ADD, /* | */ _WRITE, /* v */ _R22WB, /* . */ _ZERO, /* | */ _LSB1, /* | R2++ */ _ADD, /* | */ _WB2R2, /* v */ _R22WB, /* . */ _ZERO, /* | */ _LSB1, /* | compute */ _SHL, /* | instructions */ _LSB1, /* | remaining */ _SHL, /* | to be */ _SHL, /* | copied (48-R2) */ _SHL, /* | */ _SHL, /* | */ _SUB, /* v */ _TEST, /* 48-R2 =? 0 */ _JUMP, /* no, goto :copy-5 */ _WB2R3, /* yes, clear stack */ _R12WB, /* . */ _FORK, /* | spawn child and provide */ _R12WB, /* | ownership of code to it */ _CHOWN, /* v */ _R02WB, /* . goto :from */ _JUMP /* v */ }; #endif /* my second try (sloppy code, runs off into unknown code after replication, * reproduces only once) */ U1 g_seed[82] = { _HERE, /* :start */ _ZERO, /* reg[0]= */ _WTOR, /* src address */ _HERE, /* arg for alloc */ _ALLOC, _DUP, _ZERO, _LSB1, /* reg[1]= */ _WTOR, /* dest address */ _INLINE, 82, _NOP, _NOP, _NOP, _NOP, _NOP, _NOP, _INLINE, 2, _WTOR, /* reg[2]=# instructions left to copy */ _NOP, /* . */ _NOP, /* | landing zone */ _NOP, /* | for branch */ _NOP, /* v */ _INLINE, 8, _NOP, _NOP, _NOP, _HERE, /* :copy */ _SUB, _ZERO, _RTOW, /* . */ _READ, /* | copy over */ _INLINE, 1, _RTOW, /* | one instruction */ _WRITE, /* v */ _ZERO, /* . */ _LSB1, /* | increment */ _ZERO, _RTOW, /* | source */ _ADD, /* | address */ _ZERO, _WTOR, /* v */ _ZERO, /* . */ _LSB1, /* | increment */ _INLINE, 1, _RTOW, /* | destination */ _ADD, /* | address */ _INLINE, 1, _WTOR, /* v */ _ZERO, /* . */ _LSB1, /* | decrement number of instruct- */ _INLINE, 2, _RTOW, /* | ions remaining to copy */ _SUB, /* | */ _INLINE, 2, _WTOR, /* v */ _INLINE, 2, _RTOW, _TEST, /* reg[2]=?0 */ _JUMP, /* if no (more to copy), goto :copy */ _INLINE, 3, _WTOR, /* . */ _INLINE, 3, _WTOR, /* | */ _INLINE, 3, _RTOW, /* | if yes (done copying), */ _FORK, /* | then reproduce */ _INLINE, 3, _RTOW, /* | */ _CHOWN /* v */ }; /***************************************************************************** * id pool functions * *****************************************************************************/ DEFINE_BST_PRINT_FUNCTION(bp_print, RANGE, bp_say, p_L, p_R) DEFINE_ID_GET_FUNCTION(c, cpu) /*DEFINE_ID_GET_FUNCTION(b, bom)*/ DEFINE_BST_REMOVE_FUNCTION(bp_remove, RANGE, p_L, p_R) DEFINE_BST_DEPTH_FUNCTION(bp_depth, RANGE, p_L, p_R) int bp_compare(RANGE *a, RANGE *b) { if (a->b < b->a) return -15; else if (a->a > b->b) return 15; else return 0; } BOOL put_bid(U4 old) { RANGE *curr1 = g_bpool; RANGE *prev1 = g_bpool; RANGE *curr2; RANGE *prev2; RANGE *new; while (curr1) if (old < curr1->a-1) { prev1 = curr1; curr1 = curr1->p_L; } else if (old > curr1->b+1) { prev1 = curr1; curr1 = curr1->p_R; } else if (old < curr1->a) { curr1->a = old; if (curr1->p_L) { curr2 = prev2 = curr1; prev2 = curr2; curr2 = curr2->p_L; while (curr2->p_R) { prev2 = curr2; curr2 = curr2->p_R; } if (curr2->b+1 == curr1->a) { curr1->a = curr2->a; /* may not be correct */ new = bp_remove(&g_bpool, curr2, prev2); assert_e(new == curr2); free(new); --g_nrngs; } } return _TRUE; } else if (old > curr1->b) { curr1->b = old; if (curr1->p_R) { curr2 = prev2 = curr1; prev2 = curr2; curr2 = curr2->p_R; while (curr2->p_L) { prev2 = curr2; curr2 = curr2->p_L; } if (curr1->b+1 == curr2->a) { curr1->b = curr2->b; /* may not be correct */ new = bp_remove(&g_bpool, curr2, prev2); assert_e(new == curr2); free(new); --g_nrngs; } } return _TRUE; } else return _FALSE; /* insert new node under prev1 */ new = (RANGE *)malloc(sizeof(RANGE)); new->p_L = new->p_R = NULL; new->a = new->b = old; ++g_nrngs; if (curr1 == prev1) { assert_e(!g_bpool); g_bpool = new; } else ((bp_compare(new, prev1) < 0) ? prev1->p_L : prev1->p_R) = new; } U4 get_bid(U4 preferred) { RANGE *curr = g_bpool; RANGE *prev = g_bpool; RANGE *new; /*say(p_out_obj, "\n<get_bid: %u>\n", preferred);*/ /*bp_print(g_bpool, 0);*/ if (!g_bpool) return 0; if (preferred) while (curr) { if (preferred < curr->a) { prev = curr; curr = curr->p_L; } else if (preferred > curr->b) { prev = curr; curr = curr->p_R; } else { if (preferred == curr->a) { if (++(curr->a) > curr->b) { new = bp_remove(&g_bpool, curr, prev); assert_e(curr == new); free(new); --g_nrngs; } } else if (preferred == curr->b) { if (--(curr->b) < curr->a) { new = bp_remove(&g_bpool, curr, prev); assert_e(curr == new); free(new); --g_nrngs; } } else { /* preferred is buried, must split */ /* gonna need a new node (RANGE struct) */ new = (RANGE *)malloc(sizeof(RANGE)); new->p_L = new->p_R = NULL; ++g_nrngs; if (!curr->p_L) { new->a = curr->a; new->b = preferred - 1; curr->a = preferred + 1; curr->p_L = new; } else if (!curr->p_R) { new->a = preferred + 1; new->b = curr->b; curr->b = preferred - 1; curr->p_R = new; } else { new->a = curr->a; new->b = preferred - 1; curr->a = preferred + 1; prev = curr; curr = curr->p_L; /* arbitrarily choose to follow left link */ while (curr->p_R) { prev = curr; curr = curr->p_R; } curr->p_R = new; } } return preferred; } } return get_bid((U4)nrandom(p_max_boms)); } /***************************************************************************** * type comparison functions * *****************************************************************************/ DEFINE_ID_COMPARE_FUNCTION(cat_compare, ARL, c) DEFINE_ID_COMPARE_FUNCTION(bat_compare, ARL, b) DEFINE_ID_COMPARE_FUNCTION(cs_compare, CPU, c) DEFINE_ID_COMPARE_FUNCTION(bs_compare, BOM, b) int rq_compare(CPU *a, CPU *b) { /* compare by err */ if (a->err < b->err) return -15; else if (a->err > b->err) return 15; /* same err: compare by age */ else if (a->age < b->age) return -15; else if (a->age > b->age) return 15; /* same age: compare by cid (guaranteed to yield uniqueness but could * introduce selective pressure against large ids) */ else if (a->cid < b->cid) return -15; else if (a->cid > b->cid) return 15; else return 0; } /***************************************************************************** * UTIMER functions * *****************************************************************************/ void tick(int n) { int i; for (i=0; i<n; ++i) /*if (0 == ++g_clock.c)*/ if (0 == ++g_clock.b) ++g_clock.a; } /***************************************************************************** * store (BS & CS) functions * *****************************************************************************/ DEFINE_BST_GET_FUNCTION(cs_get, CPU, cid, cs_L, cs_R) DEFINE_BST_GET_FUNCTION(bs_get, BOM, bid, bs_L, bs_R) DEFINE_BST_INSERT_FUNCTION(cs_insert, CPU, cs_compare, cs_L, cs_R) DEFINE_BST_INSERT_FUNCTION(bs_insert, BOM, bs_compare, bs_L, bs_R) DEFINE_BST_FIND_REMOVE_FUNCTION(cs_remove, CPU, cs_compare, cs_L, cs_R) DEFINE_BST_FIND_REMOVE_FUNCTION(bs_remove, BOM, bs_compare, bs_L, bs_R) DEFINE_BST_DEPTH_FUNCTION(cs_depth, CPU, cs_L, cs_R) DEFINE_BST_DEPTH_FUNCTION(bs_depth, BOM, bs_L, bs_R) DEFINE_BST_PRINT_FUNCTION(cs_print, CPU, cs_say, cs_L, cs_R) DEFINE_BST_PRINT_FUNCTION(bs_print, BOM, bs_say, bs_L, bs_R) /***************************************************************************** * relation tree (AT & OT) functions * *****************************************************************************/ DEFINE_BST_GET_FUNCTION(bat_get, ARL, bid, cL, cR) /*DEFINE_BST_GET_FUNCTION(cat_get, ARL, cid, bL, bR)*/ DEFINE_BST_GET_FUNCTION(bot_get, BOM, bid, ot_L, ot_R) DEFINE_BST_INSERT_FUNCTION(bat_insert, ARL, bat_compare, cL, cR) DEFINE_BST_INSERT_FUNCTION(cat_insert, ARL, cat_compare, bL, bR) DEFINE_BST_INSERT_FUNCTION(bot_insert, BOM, bs_compare, ot_L, ot_R) DEFINE_BST_FIND_REMOVE_FUNCTION(bat_remove, ARL, bat_compare, cL, cR) DEFINE_BST_FIND_REMOVE_FUNCTION(cat_remove, ARL, cat_compare, bL, bR) DEFINE_BST_FIND_REMOVE_FUNCTION(bot_remove, BOM, bs_compare, ot_L, ot_R) /*DEFINE_BST_DEPTH_FUNCTION(bat_depth, ARL, cL, cR)*/ /*DEFINE_BST_DEPTH_FUNCTION(cat_depth, ARL, bL, bR)*/ /*DEFINE_BST_DEPTH_FUNCTION(bot_depth, BOM, ot_L, ot_R)*/ /***************************************************************************** * reaper queue (RQ) functions * *****************************************************************************/ DEFINE_BST_INSERT_FUNCTION(rq_insert, CPU, rq_compare, rq_L, rq_R) DEFINE_BST_FIND_REMOVE_FUNCTION(rq_remove, CPU, rq_compare, rq_L, rq_R) DEFINE_BST_PRINT_FUNCTION(rq_print, CPU, rq_say, rq_L, rq_R) DEFINE_BST_DEPTH_FUNCTION(rq_depth, CPU, rq_L, rq_R) /* -- multiple key BST method -- */ CPU* rq_grab(void) { CPU *curr; curr = g_rq_root; while (curr->rq_R) curr = curr->rq_R; return curr; } /***************************************************************************** * execution queue (EQ) functions * *****************************************************************************/ void eq_print(CPU *_curr) { CPU *cpu = _curr; /* EQ is not empty */ if (cpu) { while (cpu->eq_N != _curr) { say(p_out_dbg, "%u ", cpu->cid); cpu = cpu->eq_N; } say(p_out_dbg, "%u\n", cpu->cid); } } BOOL eq_insert(CPU **_curr, CPU *_new) { if (!_new) return _FALSE; /* cid=0 should never be inserted into the EQ */ assert_e(0 < _new->cid); /* special case: EQ is empty */ if (!*_curr) *_curr = _new; /* EQ is not empty */ else { _new->eq_N = *_curr; _new->eq_P = (*_curr)->eq_P; _new->eq_P->eq_N = _new; _new->eq_N->eq_P = _new; } return _TRUE; } CPU* eq_remove(CPU **_curr, CPU *_old) { CPU *cpu; /* cid=0 should never be removed from the EQ (as it should never be * inserted) */ assert_e(0 < _old->cid); /* no cid=_old->cid -OR- CS=empty */ if (!(cpu = cs_get(g_cs_root, _old->cid))) return NULL; /* special case: EQ contains 1 node */ if ((*_curr)->eq_N == *_curr) *_curr = NULL; /* normal case */ else { if (cpu == *_curr) *_curr = cpu->eq_P; cpu->eq_P->eq_N = cpu->eq_N; cpu->eq_N->eq_P = cpu->eq_P; } /* re-init the object's ptrs before returning it */ cpu->eq_N = cpu->eq_P = cpu; return cpu; } /***************************************************************************** * object functions * *****************************************************************************/ DEFINE_NEW_REL_FUNCTION(arl, ARL) DEFINE_OLD_REL_FUNCTION(arl, ARL) CPU* new_cpu(void) { CPU *cpu; void *A, *B, *C, *D; U4 Z; A = malloc(sizeof(CPU)); B = malloc(p_cb_size * sizeof(PACKET)); C = malloc(p_wb_size * sizeof(U4)); D = malloc(p_nregs * sizeof(U4)); Z = get_cid(); /* not enough resources */ if (!A || !B || !C || !D || !Z) { free(A); free(B); free(C); free(D); return NULL; } /* fill with default values */ else { cpu = (CPU *)A; cpu->cid = Z; cpu->age = 0; cpu->err = 0; cpu->ts = 0; cpu->pc = p_bom_size; /* why? it's the 1st valid PC value */ cpu->reg = (U4 *)D; cpu->fl = p_default_flags; cpu->cb.head = 0; cpu->cb.size = 0; cpu->cb.data = B; /* note no casting */ cpu->wb.head = 0; cpu->wb.size = 0; cpu->wb.data = C; /* note no casting */ cpu->bat = NULL; cpu->bot = NULL; cpu->eq_N = cpu; cpu->eq_P = cpu; cpu->cs_L = NULL; cpu->cs_R = NULL; cpu->rq_L = NULL; cpu->rq_R = NULL; ++g_ncpus; say(p_out_obj, "<new_cpu: CPU=%u>", Z); return cpu; } } BOM* new_bom(U4 bid) { BOM *bom; void *A; U4 Z; A = malloc(sizeof(BOM)); Z = get_bid(bid); /* not enough resources */ if (!A || (0 == Z)) { free(A); return NULL; } /* fill with default values */ else { bom = (BOM *)A; bom->bid = Z; bom->cat = NULL; bom->cot = NULL; bom->bs_L = NULL; bom->bs_R = NULL; bom->ot_L = NULL; bom->ot_R = NULL; ++g_nboms; say(p_out_obj, "<new_bom: BOM=%u>", Z); return bom; } } /* called only by free_cpu() and i_fork() */ void old_cpu(CPU *cpu) { if (cpu) { say(p_out_obj, "<old_cpu: CPU=%u>", cpu->cid); free(cpu->cb.data); free(cpu->wb.data); free(cpu->reg); free(cpu); --g_ncpus; } } /* called only by free_bom() and i_alloc() */ void old_bom(BOM *bom) { int i; if (bom) { /* if requested, erase recent activity history upon freeing (helps * in distinguishing living versus dead blocks) */ if ((p_hist) && (viewport == p_iface)) /* note short-circuited evaluation */ for (i=0; i<p_bom_size; ++i) spacio(bom->bid*p_bom_size+i, touch, 0); say(p_out_obj, "<old_bom: BOM=%u>", bom->bid); assert_f(put_bid(bom->bid)); /* return bid to bpool */ free(bom); --g_nboms; } } void free_cpu(CPU *cpu) { CPU *a; CPU *b; CPU *c; BOM *bom; /* abort on NULL or special case CPU: calling free_cpu() on CPU 0 * would result in a seg fault due to non-standard linking */ assert_e(cpu && cpu->cid); /* short circuited evaluation */ /* unlink from BOM access trees */ while (cpu->bat) { bom = bs_get(g_bs_root, cpu->bat->bid); /* assured by the fact that, for a CPU to have access to a BOM, that BOM * must exist. the only exception to this rule is CPU 0, which is pre- * vented from getting to this point by the first test above */ assert_e(bom); free_arl(bom, cpu); } /* unlink from BOM ownership tree */ while (cpu->bot) free_bom(cpu->bot); /* unlink from CPU store, execution queue, and reaper's queue */ a = eq_remove(&g_eq_curr, cpu); b = rq_remove(&g_rq_root, cpu); c = cs_remove(&g_cs_root, cpu); /* sanity check: pointer mismatch [(c == a) is also true if the assertion * below is true; no need to test] */ assert_e((a == b) && (b == c)); ++g_ndead; old_cpu(a); } void free_bom(BOM *bom) { BOM *ret; /* abort on NULL or special case BOM: calling free_bom() on BOM 0 is not * harmful (unless its NULL cat is being used to ensure no access to BOM 0 * space [which I'm not sure is the case]). this step is really performed * only for consistency with free_cpu(). additionally, the NULL condition * is not actually tested bcz a U4 is passed in rather than a pointer to a * BOM (this may soon change for consistency). */ assert_e(bom && bom->bid); /* unlink from CPU access trees */ while (bom->cat) free_arl(bom, cs_get(g_cs_root, bom->cat->cid)); /* unlink from owning CPU's BOM ownership tree */ ret = bot_remove(&(bom->cot->bot), bom); assert_e(ret == bom); /* sanity check: pointer mismatch */ /* unlink from CPU ownership tree */ bom->cot = NULL; /* unlink from BOM store */ ret = bs_remove(&g_bs_root, bom); assert_e(ret == bom); /* sanity check: pointer mismatch */ old_bom(bom); } void free_arl(BOM *bom, CPU *cpu) { ARL *a; ARL *b; ARL dummy; assert_e(bom && cpu); dummy.cid = cpu->cid; dummy.bid = bom->bid; a = cat_remove(&(bom->cat), &dummy); b = bat_remove(&(cpu->bat), &dummy); /* sanity check: pointer mismatch */ assert_e(a == b); if (0 != cpu->cid) old_arl(a); else if (a) { a->priv = p_fspace_read | p_fspace_write; assert_f(bat_insert(&(cpu->bat), a)); } } /***************************************************************************** * flag functions * *****************************************************************************/ void setb(U4 *val, int bit) { *val |= (0x00000001 << bit); } void clrb(U4 *val, int bit) { *val &= ~(0x00000001 << bit); } BOOL btest(U4 val, int bit) { return val & (0x00000001 << bit); } /***************************************************************************** * buffer (WB & CB) functions * *****************************************************************************/ DEFINE_XB_RESTORE_FUNCTION(wb, p_wb_size, _FLAG_WB_QUEUE_OR_STACK) DEFINE_XB_RESTORE_FUNCTION(cb, p_cb_size, _FLAG_CB_QUEUE_OR_STACK) BOOL wb_put(CPU *cpu, U4 val) { int index; /* work buffer is not full */ if (p_wb_size != cpu->wb.size) { index = (cpu->wb.size >= p_wb_size - cpu->wb.head) ? (cpu->wb.size - (p_wb_size - cpu->wb.head)) : (cpu->wb.head + cpu->wb.size); *((U4 *)(cpu->wb.data) + index) = val; ++(cpu->wb.size); return _TRUE; } /* work buffer is full */ else { /* overwrite mode */ if (btest(cpu->fl, _FLAG_WB_PRESERVE_OR_OVERWRITE)) { *((U4 *)(cpu->wb.data) + cpu->wb.head) = val; if (++(cpu->wb.head) >= p_wb_size) cpu->wb.head = 0; return _TRUE; } /* preserve mode */ else { return _FALSE; } } } BOOL cb_put(CPU *cpu, U4 src, U4 val) { int index; /* comm buffer is not full */ if (p_cb_size != cpu->cb.size) { index = (cpu->cb.size >= p_cb_size - cpu->cb.head) ? (cpu->cb.size - (p_cb_size - cpu->cb.head)) : (cpu->cb.head + cpu->cb.size); ((PACKET)*((PACKET *)(cpu->cb.data) + index)).src = src; ((PACKET)*((PACKET *)(cpu->cb.data) + index)).val = val; ++cpu->cb.size; return _TRUE; } /* comm buffer is full */ else { /* comm buffer is in overwrite mode */ if (btest(cpu->fl, _FLAG_CB_PRESERVE_OR_OVERWRITE)) { ((PACKET)*((PACKET *)(cpu->cb.data) + cpu->cb.head)).src = src; ((PACKET)*((PACKET *)(cpu->cb.data) + cpu->cb.head)).val = val; if (++(cpu->cb.head) >= p_cb_size) cpu->cb.head = 0; return _TRUE; } /* comm buffer is in preserve mode */ else { return _FALSE; } } } BOOL wb_get(CPU *cpu, U4 *val) { int index; /* work buffer contains data */ if (0 != cpu->wb.size) { --(cpu->wb.size); /* work bfr is a stack */ if (btest(cpu->fl, _FLAG_WB_QUEUE_OR_STACK)) { index = (cpu->wb.size >= p_wb_size - cpu->wb.head) ? (cpu->wb.size - (p_wb_size - cpu->wb.head)) : (cpu->wb.head + cpu->wb.size); *val = *((U4 *)(cpu->wb.data) + index); } /* work bfr is a queue */ else { *val = *((U4 *)(cpu->wb.data) + cpu->wb.head); if (++(cpu->wb.head) >= p_wb_size) cpu->wb.head = 0; } return _TRUE; } /* work buffer is empty */ else { return _FALSE; } } BOOL cb_get(CPU *cpu, U4 *src, U4 *val) { int index; /* comm buffer contains data */ if (0 != cpu->cb.size) { --(cpu->cb.size); /* comm buffer to be operated as a stack */ if (btest(cpu->fl, _FLAG_CB_QUEUE_OR_STACK)) { index = (cpu->cb.size >= p_cb_size - cpu->cb.head) ? (cpu->cb.size - (p_cb_size - cpu->cb.head)) : (cpu->cb.head + cpu->cb.size); *src = ((PACKET)*((PACKET *)(cpu->cb.data) + index)).src; *val = ((PACKET)*((PACKET *)(cpu->cb.data) + index)).val; } /* comm buffer to be operated as a queue */ else { *src = ((PACKET)*((PACKET *)(cpu->cb.data) + cpu->cb.head)).src; *val = ((PACKET)*((PACKET *)(cpu->cb.data) + cpu->cb.head)).val; if (++(cpu->cb.head) >= p_cb_size) cpu->cb.head = 0; } return _TRUE; } /* comm buffer is empty */ else { return _FALSE; } } /***************************************************************************** * miscellaneous functions * *****************************************************************************/ DEFINE_SWAP_FUNCTION(U4) DEFINE_SWAP_FUNCTION(U1) /* little range or error checking is done on the read values; rectify */ void init_params(char *filename) { FILE *ini_file; int i; char discard[12]; ini_file = fopen(filename, "r"); assert_e(ini_file); fscanf(ini_file, "P_STEP=%d", &p_step); _EOL(ini_file); fscanf(ini_file, "P_SEED=%d", &p_seed); _EOL(ini_file); fscanf(ini_file, "P_IFACE=%d", &p_iface); _EOL(ini_file); fscanf(ini_file, "P_HIST=%d", &p_hist); _EOL(ini_file); fscanf(ini_file, "P_VPORT_CELL=%d", &p_vport_cell); _EOL(ini_file); fscanf(ini_file, "P_DIRECTION=%d", &p_direction); _EOL(ini_file); fscanf(ini_file, "P_RANDOM_SPACE=%d", &p_random_space); _EOL(ini_file); fscanf(ini_file, "P_OUT_ERR=%d", &p_out_err); _EOL(ini_file); fscanf(ini_file, "P_OUT_INS=%d", &p_out_ins); _EOL(ini_file); fscanf(ini_file, "P_OUT_OBJ=%d", &p_out_obj); _EOL(ini_file); fscanf(ini_file, "P_OUT_DBG=%d", &p_out_dbg); _EOL(ini_file); fscanf(ini_file, "P_OUT_ALL=%d", &p_out_all); _EOL(ini_file); fscanf(ini_file, "P_OUT_STAT=%d", &p_out_stat); _EOL(ini_file); fscanf(ini_file, "P_REPORT_FREQ=%u", &p_report_freq); _EOL(ini_file); fscanf(ini_file, "P_PMUTATE_FREQ=%u", &p_pmutate_freq); _EOL(ini_file); fscanf(ini_file, "P_LMUTATE_FREQ=%u", &p_lmutate_freq); _EOL(ini_file); fscanf(ini_file, "P_MULTIPLIER=%f", &p_multiplier); _EOL(ini_file); fscanf(ini_file, "P_TS_SIZE=%u", &p_ts_size); _EOL(ini_file); fscanf(ini_file, "P_CB_SIZE=%u", &p_cb_size); _EOL(ini_file); fscanf(ini_file, "P_WB_SIZE=%u", &p_wb_size); _EOL(ini_file); fscanf(ini_file, "P_NREGS=%u", &p_nregs); _EOL(ini_file); fscanf(ini_file, "P_BOM_SIZE=%u", &p_bom_size); _EOL(ini_file); fscanf(ini_file, "P_MAX_BOMS=%u", &p_max_boms); _EOL(ini_file); fscanf(ini_file, "P_MAX_CPUS=%u", &p_max_cpus); _EOL(ini_file); fscanf(ini_file, "P_BRON=%f", &p_bron); _EOL(ini_file); fscanf(ini_file, "P_CRON=%f", &p_cron); _EOL(ini_file); fscanf(ini_file, "P_BROFF=%f", &p_broff); _EOL(ini_file); fscanf(ini_file, "P_CROFF=%f", &p_croff); _EOL(ini_file); fscanf(ini_file, "P_MAX_AGE=%u", &p_max_age); _EOL(ini_file); fscanf(ini_file, "P_MAX_ERR=%u", &p_max_err); _EOL(ini_file); fscanf(ini_file, "P_MAX_TS=%d", &p_max_ts); _EOL(ini_file); fscanf(ini_file, "P_MIN_TS=%d", &p_min_ts); _EOL(ini_file); for (i=0; i<32; ++i) { fscanf(ini_file, "%s", discard); if (discard[10] - 48) setb(&p_default_flags, i); else clrb(&p_default_flags, i); _EOL(ini_file); } fscanf(ini_file, "P_VPORT_OFFSET=%s", discard); _EOL(ini_file); if ('s' == discard[0]) p_vport_offset = -1; else sscanf(discard, "%d", &p_vport_offset); fscanf(ini_file, "P_VPORT_HEIGHT=%u", &p_vport_height); _EOL(ini_file); fscanf(ini_file, "P_VPORT_WIDTH=%u", &p_vport_width); _EOL(ini_file); fscanf(ini_file, "P_VPORT_PAINT=%u", &p_vport_paint); _EOL(ini_file); fscanf(ini_file, "P_FSPACE_READ=%c", &p_fspace_read); _EOL(ini_file); fscanf(ini_file, "P_FSPACE_WRITE=%c", &p_fspace_write); _EOL(ini_file); assert_f(!fclose(ini_file)); p_fspace_read -= 48; p_fspace_write -= 48; } /* print screen template */ void print_template(int iface) { int i; /* viewport template */ if (1 == iface) { /* left column: global stats (evol) */ xyprintf(_OSP_GSTATS_XOS, _OSP_GSTATS_YOS+0, WHITE, BLACK, " clock: "); xyprintf(_OSP_GSTATS_XOS, _OSP_GSTATS_YOS+1, WHITE, BLACK, "BIDhits: "); xyprintf(_OSP_GSTATS_XOS, _OSP_GSTATS_YOS+2, WHITE, BLACK, "CIDhits: "); xyprintf(_OSP_GSTATS_XOS, _OSP_GSTATS_YOS+3, WHITE, BLACK, " nboms: "); xyprintf(_OSP_GSTATS_XOS, _OSP_GSTATS_YOS+4, WHITE, BLACK, " ncpus: "); xyprintf(_OSP_GSTATS_XOS, _OSP_GSTATS_YOS+5, WHITE, BLACK, " narls: "); xyprintf(_OSP_GSTATS_XOS, _OSP_GSTATS_YOS+6, WHITE, BLACK, " ndead: "); xyprintf(_OSP_GSTATS_XOS, _OSP_GSTATS_YOS+7, WHITE, BLACK, "BOM/CPU: "); xyprintf(_OSP_GSTATS_XOS, _OSP_GSTATS_YOS+8, WHITE, BLACK, "MTU/err: "); /* right column: local stats (current cell) */ xyprintf(_OSP_LSTATS_XOS, _OSP_LSTATS_YOS+0, WHITE, BLACK, " cid: "); xyprintf(_OSP_LSTATS_XOS, _OSP_LSTATS_YOS+1, WHITE, BLACK, " age: "); xyprintf(_OSP_LSTATS_XOS, _OSP_LSTATS_YOS+2, WHITE, BLACK, " err: "); xyprintf(_OSP_LSTATS_XOS, _OSP_LSTATS_YOS+3, WHITE, BLACK, " ts: "); xyprintf(_OSP_LSTATS_XOS, _OSP_LSTATS_YOS+4, WHITE, BLACK, " pc: "); xyprintf(_OSP_LSTATS_XOS, _OSP_LSTATS_YOS+5, WHITE, BLACK, "[pc]: "); xyprintf(_OSP_LSTATS_XOS, _OSP_LSTATS_YOS+6, WHITE, BLACK, "stat: "); xyprintf(_OSP_LSTATS2_XOS, _OSP_LSTATS2_YOS, WHITE, BLACK, " :regs: "); xyprintf(_OSP_LSTATS3_XOS, _OSP_LSTATS3_YOS, WHITE, BLACK, " :wb: "); } /* histogram template */ else if (2 == iface) { for (i=0; i<_NINSTRUCTIONS; ++i) xyprintf(0, i, WHITE, BLACK, "%6s: ", g_itab[i].text); for (i=_NINSTRUCTIONS; i<100; ++i) xyprintf(0, i, WHITE, BLACK, "%6x: ", i); } /*wrefresh(g_win);*/ } /* dump various stats and metrics */ void print_stats(void) { int i, j, hold; char stats[9][32]; g_health = 0; compute_health(g_cs_root); g_health /= g_ncpus; if (viewport == p_iface) { /* clear left column (global stats [evol/system]) */ sprintf(stats[0], "%*c", 16, ' '); sprintf(stats[1], "%*c", 20, ' '); sprintf(stats[2], "%*c", 20, ' '); sprintf(stats[3], "%*c", 12, ' '); sprintf(stats[4], "%*c", 12, ' '); sprintf(stats[5], "%*c", 21, ' '); sprintf(stats[6], "%*c", 10, ' '); sprintf(stats[7], "%*c", 20, ' '); sprintf(stats[8], "%*c", 20, ' '); for (i=0; i<9; ++i) xyprintf( _OSP_GSTATS_XOS+_OSP_GSTATS_HEAD_WIDTH, _OSP_GSTATS_YOS+i, WHITE, BLACK, stats[i] ); /* fill left column (global stats [evol/system]) */ sprintf(stats[0], "%08lX%08lX", g_clock.a, g_clock.b); sprintf(stats[1], "%f", g_bhmsum / g_bhmcnt); sprintf(stats[2], "%f", g_chmsum / g_chmcnt); sprintf(stats[3], "%u+1", g_nboms-1); sprintf(stats[4], "%u+1", g_ncpus-1); sprintf(stats[5], "%u+%u", g_narls-p_max_boms+1, p_max_boms-1); sprintf(stats[6], "%u", g_ndead); sprintf(stats[7], "%f", (float)g_nboms / g_ncpus); sprintf(stats[8], "%f", g_health); for (i=0; i<9; ++i) xyprintf( _OSP_GSTATS_XOS+_OSP_GSTATS_HEAD_WIDTH, _OSP_GSTATS_YOS+i, WHITE, BLACK, stats[i] ); /* clear right column (local stats [current cell]) */ sprintf(stats[0], "%*c", 10, ' '); sprintf(stats[1], "%*c", 10, ' '); sprintf(stats[2], "%*c", 10, ' '); sprintf(stats[3], "%*c", 11, ' '); sprintf(stats[4], "%*c", 10, ' '); sprintf(stats[5], "%*c", 11, ' '); sprintf(stats[6], "%*c", 30, ' '); for (i=0; i<7; ++i) xyprintf( _OSP_LSTATS_XOS+_OSP_LSTATS_HEAD_WIDTH, _OSP_LSTATS_YOS+i, WHITE, BLACK, stats[i] ); for (i=0; i<p_nregs; ++i) xyprintf( _OSP_LSTATS2_XOS, _OSP_LSTATS2_YOS+i+1, WHITE, BLACK, " " ); for (i=0; i<p_wb_size; ++i) xyprintf( _OSP_LSTATS3_XOS, _OSP_LSTATS3_YOS+i+1, WHITE, BLACK, " " ); /* fill right column (local stats [current cell]) */ if (g_eq_curr) { sprintf(stats[0], "%x", g_eq_curr->cid); sprintf(stats[1], "%u", g_eq_curr->age); sprintf(stats[2], "%u", g_eq_curr->err); sprintf(stats[3], "%d", g_eq_curr->ts); sprintf(stats[4], "%x", g_eq_curr->pc); /* pc is always set after a bom invalidity check */ assert_e(!_AINVALID(g_eq_curr->pc)); if (g_space[g_eq_curr->pc] < _NINSTRUCTIONS) sprintf(stats[5], "%.2x (%s)", g_space[g_eq_curr->pc], g_itab[g_space[g_eq_curr->pc]].text); else sprintf(stats[5], "%.2x (inv)", g_space[g_eq_curr->pc]); sprintf(stats[6], "%s", g_stab[(g_eq_curr->fl)&0x0000000F].text); for (i=0; i<7; ++i) xyprintf( _OSP_LSTATS_XOS+_OSP_LSTATS_HEAD_WIDTH, _OSP_LSTATS_YOS+i, WHITE, BLACK, stats[i] ); for (i=0; i<p_nregs; ++i) xyprintf( _OSP_LSTATS2_XOS, _OSP_LSTATS2_YOS+i+1, WHITE, BLACK, "%.8x", g_eq_curr->reg[i] ); for (i=0; i<g_eq_curr->wb.size; ++i) { hold = (g_eq_curr->wb.head + i) % p_wb_size; xyprintf( _OSP_LSTATS3_XOS, _OSP_LSTATS3_YOS+i+1, WHITE, BLACK, "%.8x", *((U4 *)(g_eq_curr->wb.data)+hold) ); } } /*wrefresh(g_win);*/ } else if (textscroll == p_iface) { /*rq_print(g_rq_root, 0);*/ /* global health */ say(p_out_stat, "[%f MTU/err]", g_health); /* average cell size */ say(p_out_stat, "[%f BOM/CPU]", (float)g_nboms / g_ncpus); /* objects */ say(p_out_stat, "[CPU: %u, BOM: %u, ARL: %u, RANGE: %u]", g_ncpus, g_nboms, g_narls, g_nrngs ); /* total cummulative population */ say(p_out_stat, "[died: %u]", g_ndead); /* average id request misses */ say(p_out_stat, "[get_cid: %f, get_bid: %f]", g_chmsum / g_chmcnt, g_bhmsum / g_bhmcnt); /* deviation from optimal BST depth (actual - theoretical) */ say(p_out_stat, "[CS: %u-%u, BS: %u-%u, RQ: %u-%u, BP: %u-%u]", cs_depth(g_cs_root), g_ncpus>0 ? ((U4)ceil(log(g_ncpus)/log(2))+1) : 0, bs_depth(g_bs_root), g_nboms>0 ? ((U4)ceil(log(g_nboms)/log(2))+1) : 0, rq_depth(g_rq_root), g_ncpus>0 ? ((U4)ceil(log(g_ncpus)/log(2))+1) : 0, bp_depth(g_bpool), g_nboms>0 ? ((U4)ceil(log(g_nboms)/log(2))+1) : 0 ); /* memory usage */ say(p_out_stat, "[mem: space %u + objects %u]\n", p_bom_size * p_max_boms * sizeof(U1), /* mem used by g_space */ g_ncpus * sizeof(CPU) + /* mem used by CPUs */ 2 * g_ncpus * sizeof(BUFFER) + /* mem used by BUFFERs */ g_ncpus * p_cb_size * sizeof(PACKET) + /* mem used by CBs */ g_ncpus * p_wb_size * sizeof(U4) + /* mem used by WBs */ g_nboms * sizeof(BOM) + /* mem used by BOMs */ g_narls * sizeof(ARL) + /* mem used by ARLs */ g_nrngs * sizeof(RANGE) /* mem used by RANGEs */ ); } else { /* print histogram line */ for (i=0; i<100; ++i) { xyprintf(8, i, WHITE, BLACK, "%*c", 50, ' '); for (j=0; j<(int)(50*histo(i)); ++j) xyprintf((j+8), i, WHITE, BLACK, "%c", '*'); } /*wrefresh(g_win);*/ } } float histo(int instruction) { U4 i; int count = 0; for (i=p_bom_size; i<p_bom_size * p_max_boms * sizeof(U1); ++i) if (instruction == g_space[i]) ++count; return (float)count / ((p_bom_size * p_max_boms * sizeof(U1)) - p_bom_size); } /* This must be a GRXism: ATP the screen is in text mode, so no * graphics operations or we'll get a crash */ void cleanup(void) { /* prevent dumping during cleanup */ /*signal(SIGINT, SIG_IGN);*/ /*print_stats(); wrefresh(g_win);*/ /* should always contain at least CPU 0 atp */ assert_e(g_cs_root); /* free all CPUs other than CPU 0: bcz 1) the CS tree is a BST, 2) cid 0 is * always added first, and 3) all other cids (greater than cid 0) are added * later, these 'other' CPUs are always found hanging from the cs_R branch * of g_cs_root, whereas CPU 0 itself is pointed to by g_cs_root. this is * not guaranteed to be true if the CS tree becomes an AVL tree (in the * future). CPU 0 is freed further down. */ while (g_cs_root->cs_R) free_cpu(g_cs_root->cs_R); /* free world access tree (must use old_arl, can't use free_arl) */ while (g_cs_root->bat) old_arl(bat_remove(&(g_cs_root->bat), g_cs_root->bat)); /* free CPU 0 */ old_cpu(rq_remove(&g_rq_root, cs_remove(&g_cs_root, cs_get(g_cs_root, 0)))); /* free BOM 0 */ old_bom(bs_remove(&g_bs_root, bs_get(g_bs_root, 0))); free(g_space); /*print_stats();*/ /*if (p_iface) endwin();*/ } void compute_health(CPU *_root) { if (_root) { compute_health(_root->cs_L); g_health += (double)(_root->age) / (_root->err ? _root->err : 1); compute_health(_root->cs_R); } } /* must not be called when certain data structures are in a transitional * state, such as during a node removal from the RQ. in such cases, the * signal should be ignored as a first step in such routines as rq_remove() * to prevent them from being interrupted. otherwise, the save_state() * routine, which traverses the RQ as it writes its contents to disk, could * be traversing the RQ in an inconsistent and incorrect state. this will * not become an issue until save_state() saves such info; at the moment, * it simply saves g_space contents. */ void save_state(void) { int i; int statefd; say(p_out_all, "<saving virtual machine state...>"); /* open the state file for writing */ if (-1 == (statefd = open("state", O_WRONLY | O_CREAT))) perror("state"); else { if (g_space) { /* dump g_space to the state file */ write(statefd, g_space, p_bom_size * p_max_boms * sizeof(U1)); } /* close the state file */ if (-1 == close(statefd)) perror("state"); } /* indicate completion... */ say(p_out_all, "<done>"); sleep(3); } /* dump the BPOOL tree */ void interrupt(int sig) { /* prevent multiple invocations of the signal handler */ signal(sig, SIG_IGN); bp_print(g_bpool, 0); /* restore the signal handler */ signal(sig, interrupt); } #if 0 /* move the viewport to a more interesting location */ void interrupt(int sig) { int y, count; /* prevent multiple invocations of the signal handler */ signal(sig, SIG_IGN); /* only valid if we're in viewport mode */ if (viewport == p_iface) { if (pixel == p_vport_cell) count = 1; else if (hex == p_vport_cell) count = 2; else if (human == p_vport_cell) count = 7; /* blank the viewport (screen only, g_space is untouched) */ for (y=_OSP_VPORT_YOS; y<g_lines-_OSP_CLINE_HEIGHT; ++y) xyprintf(0, y, WHITE, BLACK, "%*c", p_vport_width*count, ' '); /* 'interesting' might be were the current CPU is */ if (g_eq_curr) p_vport_offset = p_bom_size * (g_eq_curr->pc / p_bom_size) - 10; p_step = _TRUE; } /* restore the signal handler */ signal(sig, interrupt); } /* handle various realtime parameter changes */ void interrupt(int sig) { int ch; char sbuff[11]; /* prevent multiple invocations of the signal handler */ signal(sig, SIG_IGN); ch = GrKeyRead(); assert_e(ERR != ch); switch ((char)ch) { case 'v': save_state(); break; case 's': p_step = p_step ? _FALSE : _TRUE; break; case 'p': mvwgetnstr(g_win, g_lines-1, 1, sbuff, 10); p_pmutate_freq = atoi(sbuff); break; case 'l': mvwgetnstr(g_win, g_lines-1, 1, sbuff, 10); p_lmutate_freq = atoi(sbuff); break; case 'i': if (p_iface) { (viewport == p_iface) ? ++p_iface : --p_iface; wclear(g_win); /*wrefresh(g_win);*/ print_template(p_iface); } break; case 'h': if (p_iface) { p_hex = p_hex ? _FALSE : _TRUE; wclear(g_win); /*wrefresh(g_win);*/ print_template(p_iface); } break; } mvwprintw(g_win, 100, 0, "%20c", ' '); /* restore the signal handler */ signal(sig, interrupt); } #endif int say(BOOL level, char *format, ...) { va_list ap; /* argument pointer */ int ret = 0; /* vprintf's return value */ if (level) { va_start(ap, format); ret = vprintf(format, ap); va_end(ap); } return ret; } /* returns a pseudo-random integer between 0 and n-1, inclusive */ int nrandom(int n) { return (int)(n * 1.0 * rand() / (RAND_MAX + 1.0)); } /* this is the only place in the entire program where a cpu's err, age, or * ts get changed (except for new_cpu() where they are initialized, and * main() where ts is awarded); also the only place where a cpu's status * code is set */ void adjust(CPU *cpu, int etime, int status) { /* inform cell of result of instruction execution */ set_statcode(cpu, status); /* adjust cell's position in RQ; do this only if necessary (one of the * relevant values is nonzero) as relinking the RQ is expensive */ if (g_stab[status].cost || etime) { /* sanity check: pointer mismatch */ assert_f(rq_remove(&g_rq_root, cpu) == cpu); cpu->err += g_stab[status].cost; cpu->age += etime; /* sanity check: linking error */ assert_f(rq_insert(&g_rq_root, cpu)); } /* adjust the cell's TS to reflect the instruction execution time */ cpu->ts -= etime; /* advance the cell to the next instruction */ nstep(&(cpu->pc), _DIRECTION(cpu), 1); } void set_statcode(CPU *cpu, int err) { err &= 0x0000000F; cpu->fl &= 0xFFFFFFF0; cpu->fl += err; } /* nstep() performs stepping in the specified direction and normalization: pc * is always left pointing into a valid block. Block 0 and blocks equal to or * greater than p_max_boms are invalid. If a BOM ever becomes anything other * than an array of U1s (say an array of new_things) in the future, leaving * "p_bom_size*p_max_boms" as it is will cause the pc to step in increments of * sizeof(new_thing); in the case of some complex, multi-byte new_thing (eg, a * struct), this means pc steps over the current new_thing to the beginning of * the next new_thing. Changing to "p_bom_size*p_max_boms*sizeof(new_thing)" * will cause the pc to step (as it does now) in increments of 1 byte; with * the complex, multi-byte new_thing, this means pc steps within new_thing. * Depending on the purpose of the change to the composition of a BOM, these * considerations need to be taken into account. */ void nstep(U4 *pc, BOOL dir, int n) { /* reverse */ if (dir) for (; n>0; --n) { --*pc; if (_AINVALID(*pc)) /* note macro: can't do _AINVALID(--*pc) */ *pc = p_bom_size*p_max_boms-1; } /* forward */ else for (; n>0; --n) { ++*pc; if (_AINVALID(*pc)) /* note macro: can't do _AINVALID(++*pc) */ *pc = p_bom_size; } } /* spacio is short for "SPACe Input/Output"; all accesses to g_space are * handled here [except for some in print_stats(), histo()... which is only * called by print_stats(), and in the line mutation code in main()] */ U1 spacio(U4 address, int how, U1 write_value) { int x = -1; int y = -1; U4 hold; if (viewport == p_iface) if ((address >= p_vport_offset) && (address < p_vport_offset + p_vport_width * p_vport_height)) { if (p_direction) { /* horizontal */ y = (address - p_vport_offset) / p_vport_width; x = (address - p_vport_offset) % p_vport_width; } else { /* vertical */ x = (address - p_vport_offset) / p_vport_height; y = (address - p_vport_offset) % p_vport_height; } } /* specified access falls within viewport */ if (-1 < x) { /* odd accesses are active (writes): mutate, cell_write, initialize * even accesses are passive (reads): cell_read, execute, touch */ hold = (how % 2) ? write_value : g_space[address]; /* first print stats (if time) then access cell; reversing this order * will not leave the cursor at the modified/accessed cell (which is esp. * useful for manual stepping mode) */ /* print stats */ if (p_step && (how!=initialize)) print_stats(); /* update cell */ if (hex == p_vport_cell) /* hexadecimal output */ xyprintf(x*2, y+_OSP_VPORT_YOS, g_color_pairs[0][how], g_color_pairs[1][how], "%.2x", hold); else if (human == p_vport_cell) /* human-readable output */ /* instruction; print human-readable name */ if (hold<_NINSTRUCTIONS) xyprintf(x*7, y+_OSP_VPORT_YOS, g_color_pairs[0][how], g_color_pairs[1][how], "%6s", g_itab[hold].text); /* data; print padded hex */ else xyprintf(x*7, y+_OSP_VPORT_YOS, g_color_pairs[0][how], g_color_pairs[1][how], " <%.2x>", hold); else /* pixel output */ GrPlot(x, y+_OSP_VPORT_YOS*_CHAR_CELL_HEIGHT, g_color_pairs[0][how]); /* refresh during manual stepping mode */ if (p_step && (how!=initialize)) GrKeyRead(); } /* odd accesses are active (writes): mutate, cell_write, initialize * even accesses are passive (reads): cell_read, execute, touch */ if (how % 2) g_space[address] = write_value; else return g_space[address]; } /* second attempt */ #if 0 U1 spacio(U4 address, int how, U1 write_value) { int x = -1; int y = -1; /*char sbuff[7];*/ STEXT csbuff[7]; STEXT ch; U4 hold; /*static U4 vport_update = 0;*/ if (viewport == p_iface) if ((address >= p_vport_offset) && (address < p_vport_offset + p_vport_width * p_vport_height)) { y = (address - p_vport_offset) / p_vport_width; x = (address - p_vport_offset) % p_vport_width; } /* specified access falls within viewport */ if (-1 < x) { hold = (how % 2) ? write_value : g_space[address]; /* this... */ if (p_step && (how!=initialize)) print_stats(); /* should come before this in order to place cursor next to the memory * cell being changed (esp. useful for manual stepping mode) */ if (p_hex) { /* hexadecimal output */ /*if (how==execute) ch = (mvwinch(g_win, y+_OSP_VPORT_YOS, x*2)&A_ATTRIBUTES)|A_REVERSE; else ch = COLOR_PAIR(how); ssprintf(csbuff, ch, "%.2x", hold); mvwaddchstr(g_win, y+_OSP_VPORT_YOS, x*2, csbuff);*/ xyprintf( x*2, y+_OSP_VPORT_YOS, g_color_pairs[0][how], g_color_pairs[1][how], "%.2x", hold ); } else { /* human-readable output */ if (hold<_NINSTRUCTIONS) { /*if (how==execute) ch = (mvwinch(g_win, y+_OSP_VPORT_YOS, x*7)&A_ATTRIBUTES)|A_REVERSE; else ch = COLOR_PAIR(how); ssprintf(csbuff, ch, "%6s", g_itab[hold].text);*/ xyprintf( x*7, y+_OSP_VPORT_YOS, g_color_pairs[0][how], g_color_pairs[1][how], "%6s", g_itab[hold].text ); } else { /*if (how==execute) ch = (mvwinch(g_win, y+_OSP_VPORT_YOS, x*7)&A_ATTRIBUTES)|A_REVERSE; else ch = COLOR_PAIR(how); sprintf(sbuff, "<%.2x>", hold); ssprintf(csbuff, ch, "%6s", sbuff);*/ xyprintf( x*7, y+_OSP_VPORT_YOS, g_color_pairs[0][how], g_color_pairs[1][how], " <%.2x>", hold ); } /*mvwaddchstr(g_win, y+_OSP_VPORT_YOS, x*7, csbuff);*/ } /* refresh during manual stepping mode */ if (p_step && (how!=initialize)) { /*wrefresh(g_win);*/ GrKeyRead(); } /*usleep(350000);*/ /* refresh after n changes where n=p_vport_paint */ /* if (++vport_update >= p_vport_paint) { vport_update = 0; wrefresh(g_win); } */ } if (how % 2) /* odd accesses are active (writes): mutate, cell_write, initialize */ g_space[address] = write_value; else /* even accesses are passive (reads): cell_read, execute */ return g_space[address]; } #endif /* first attempt */ #if 0 U1 spacio(U4 address, int how, U1 write_value) { int x = -1; int y = -1; STEXT csbuff[7]; if (viewport == p_iface) if ((address >= p_vport_offset) && (address < p_vport_offset + p_vport_width * p_vport_height)) { y = (address - p_vport_offset) / p_vport_width; x = (address - p_vport_offset) % p_vport_width; } switch (how) { case mutate: if (-1 < x) { if (p_step) print_stats(); if (p_hex) { ssprintf(csbuff, COLOR_PAIR(1), "%.2x", write_value); mvwaddchstr(g_win, y+_OSP_VPORT_YOS, x*2, csbuff); } else { ssprintf( csbuff, COLOR_PAIR(1), "%6s", (write_value<_NINSTRUCTIONS) ? g_itab[write_value].text : "<inv>" ); mvwaddchstr(g_win, y+_OSP_VPORT_YOS, x*7, csbuff); } /*wrefresh(g_win);*/ if (p_step) wgetch(g_win); /*usleep(350000); */ } g_space[address] = write_value; break; case cell_read: if (-1 < x) { if (p_step) print_stats(); if (p_hex) { ssprintf(csbuff, COLOR_PAIR(2), "%.2x", g_space[address]); mvwaddchstr(g_win, y+_OSP_VPORT_YOS, x*2, csbuff); } else { /* ssmodat( '=', COLOR_PAIR(2), csbuff, mvwinchnstr(g_win, y+_OSP_VPORT_YOS, x*7, csbuff, 6) ); */ ssprintf( csbuff, COLOR_PAIR(2), "%6s", (g_space[address]<_NINSTRUCTIONS) ? g_itab[g_space[address]].text : "<inv>" ); mvwaddchstr(g_win, y+_OSP_VPORT_YOS, x*7, csbuff); } /*wrefresh(g_win);*/ if (p_step) wgetch(g_win); /*usleep(350000); */ } return g_space[address]; break; case cell_write: if (-1 < x) { if (p_step) print_stats(); if (p_hex) { ssprintf(csbuff, COLOR_PAIR(3), "%.2x", write_value); mvwaddchstr(g_win, y+_OSP_VPORT_YOS, x*2, csbuff); } else { ssprintf( csbuff, COLOR_PAIR(3), "%6s", (write_value<_NINSTRUCTIONS) ? g_itab[write_value].text : "<inv>" ); mvwaddchstr(g_win, y+_OSP_VPORT_YOS, x*7, csbuff); } /*wrefresh(g_win);*/ if (p_step) wgetch(g_win); /*usleep(350000); */ } g_space[address] = write_value; break; case execute: if (-1 < x) { if (p_step) print_stats(); if (p_hex) { ssmodat( '+', A_REVERSE, csbuff, mvwinchnstr(g_win, y+_OSP_VPORT_YOS, x*2, csbuff, 2) ); /*ssprintf(csbuff, COLOR_PAIR(4), "%.2x", g_space[address]); */ mvwaddchstr(g_win, y+_OSP_VPORT_YOS, x*2, csbuff); } else { ssmodat( '+', A_REVERSE, csbuff, mvwinchnstr(g_win, y+_OSP_VPORT_YOS, x*7, csbuff, 6) ); /* ssprintf( csbuff, COLOR_PAIR(4), "%6s", (g_space[address]<_NINSTRUCTIONS) ? g_itab[g_space[address]].text : "<inv>" ); */ mvwaddchstr(g_win, y+_OSP_VPORT_YOS, x*7, csbuff); } /*wrefresh(g_win);*/ if (p_step) wgetch(g_win); /*usleep(350000); */ } return g_space[address]; break; case initialize: if (-1 < x) { if (p_hex) { ssprintf(csbuff, COLOR_PAIR(5), "%.2x", write_value); mvwaddchstr(g_win, y+_OSP_VPORT_YOS, x*2, csbuff); } else { ssprintf( csbuff, COLOR_PAIR(5), "%6s", (write_value<_NINSTRUCTIONS) ? g_itab[write_value].text : "<inv>" ); mvwaddchstr(g_win, y+_OSP_VPORT_YOS, x*7, csbuff); } /*wrefresh(g_win);*/ } g_space[address] = write_value; break; } } #endif /* ssmodat is short for "STEXT String MODify ATtributes"; for op equal '+', * attr will be added to the first n characters of stbuf. for op equal '=', * attr will replace the existing attributes of those same characters. */ void ssmodat(char op, STEXT attr, STEXT *stbuf, int n) { int i; for (i=0; i<n; ++i) if ('+' == op) /* add attributes */ stbuf[i] |= attr; else if ('=' == op) /* replace attributes */ stbuf[i] = (stbuf[i] & _STEXT_MASK_CHAR) | attr; } /* Formatted STEXT String Print: if resulting string longer than 6 chars, * stack overflow may result */ int ssprintf(STEXT *stbuf, STEXT attr, char *format, ...) { char sbuf[7]; va_list ap; /* variable argument list pointer */ int i, ret; va_start(ap, format); ret = vsprintf(sbuf, format, ap); va_end(ap); for (i=0; i<ret; ++i) stbuf[i] = sbuf[i] | attr; stbuf[i] = 0; return ret; } int xyprintf(int x, int y, GrColor fg, GrColor bg, char *format, ...) { char sbuf[g_cols]; va_list ap; /* variable argument list pointer */ int i, ret; /* perform clipping: x or y off screen */ if ((g_cols < x) || (g_lines < y)) return 0; va_start(ap, format); /* may cause stack overflow; use vsnprintf() */ ret = vsprintf(sbuf, format, ap); /* vsnprintf() not available in DJGPP yet */ #if 0 ret = vsnprintf(sbuf, g_cols, format, ap); #endif va_end(ap); /* won't need until vsnprintf() available */ #if 0 if (ret >= g_cols) /* string was truncated */ ret = g_cols-1; #endif /*GrTextXY(x, y, sbuf, fg, bg);*/ g_gtxo.txo_fgcolor.v = fg; g_gtxo.txo_bgcolor.v = bg; GrDrawString( sbuf, _MIN(ret,g_cols-x), x*_CHAR_CELL_WIDTH, y*_CHAR_CELL_HEIGHT, &g_gtxo ); return ret; } /***************************************************************************** * instructions * *****************************************************************************/ int i_dup(CPU *this_cpu) { int nargs = 1; U4 arg; /* no room for results */ if (p_cb_size <= this_cpu->wb.size) return _FAILURE_WBF; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg)); assert_f(wb_put(this_cpu, arg)); assert_f(wb_put(this_cpu, arg)); return _SUCCESS; } int i_spin(CPU *this_cpu) { if (_DIRECTION(this_cpu)) clrb(&(this_cpu->fl), _FLAG_INCREASE_OR_DECREASE); else setb(&(this_cpu->fl), _FLAG_INCREASE_OR_DECREASE); return _SUCCESS; } int i_comm(CPU *this_cpu) { int nargs = 1; U4 arg; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg)); if (btest(arg, 1)) setb(&(this_cpu->fl), _FLAG_CB_QUEUE_OR_STACK); else clrb(&(this_cpu->fl), _FLAG_CB_QUEUE_OR_STACK); if (btest(arg, 0)) setb(&(this_cpu->fl), _FLAG_CB_PRESERVE_OR_OVERWRITE); else clrb(&(this_cpu->fl), _FLAG_CB_PRESERVE_OR_OVERWRITE); return _SUCCESS; } int i_work(CPU *this_cpu) { int nargs = 1; U4 arg; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg)); if (btest(arg, 1)) setb(&(this_cpu->fl), _FLAG_WB_QUEUE_OR_STACK); else clrb(&(this_cpu->fl), _FLAG_WB_QUEUE_OR_STACK); if (btest(arg, 0)) setb(&(this_cpu->fl), _FLAG_WB_PRESERVE_OR_OVERWRITE); else clrb(&(this_cpu->fl), _FLAG_WB_PRESERVE_OR_OVERWRITE); return _SUCCESS; } int i_here(CPU *this_cpu) { /* no room for results */ if (!wb_put(this_cpu, this_cpu->pc)) return _FAILURE_WBF; return _SUCCESS; } int i_jump(CPU *this_cpu) { int nargs = 1; U4 arg_addr; /* new address to jump to */ /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg_addr)); /* address (and hence bid) not valid */ if (_AINVALID(arg_addr)) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_BNV; } this_cpu->pc = arg_addr; /* Note the inversion of _DIRECTION(): this counteracts the nstep() that is * done in main() after execution of every instruction. this is only re- * quired within i_jump() in order to place the pc where this_cpu expects * it. */ nstep(&(this_cpu->pc), !_DIRECTION(this_cpu), 1); return _SUCCESS; } int i_ftow(CPU *this_cpu) { /* no room for results */ if (!wb_put(this_cpu, this_cpu->fl)) return _FAILURE_WBF; return _SUCCESS; } int i_add(CPU *this_cpu) { int nargs = 2; U4 arg1, arg2, result; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg1)); assert_f(wb_get(this_cpu, &arg2)); result = arg1 + arg2; assert_f(wb_put(this_cpu, result)); if ((result < arg1) || (result < arg2)) setb(&(this_cpu->fl), _FLAG_ROLL_OVER); else clrb(&(this_cpu->fl), _FLAG_ROLL_OVER); return _SUCCESS; } int i_sub(CPU *this_cpu) { int nargs = 2; U4 arg1, arg2, result; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg1)); assert_f(wb_get(this_cpu, &arg2)); result = arg1 - arg2; assert_f(wb_put(this_cpu, result)); if (result > arg1) setb(&(this_cpu->fl), _FLAG_ROLL_OVER); else clrb(&(this_cpu->fl), _FLAG_ROLL_OVER); return _SUCCESS; } int i_zero(CPU *this_cpu) { /* no room for results */ if (!wb_put(this_cpu, 0)) return _FAILURE_WBF; return _SUCCESS; } int i_shl(CPU *this_cpu) { int nargs = 1; U4 arg; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg)); if (btest(arg, _FLAG_MOST_SIG_BIT)) setb(&(this_cpu->fl), _FLAG_DISCARD_BIT); else clrb(&(this_cpu->fl), _FLAG_DISCARD_BIT); arg <<= 1; assert_f(wb_put(this_cpu, arg)); return _SUCCESS; } int i_shr(CPU *this_cpu) { int nargs = 1; U4 arg; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg)); if (btest(arg, _FLAG_LEAST_SIG_BIT)) setb(&(this_cpu->fl), _FLAG_DISCARD_BIT); else clrb(&(this_cpu->fl), _FLAG_DISCARD_BIT); arg >>= 1; assert_f(wb_put(this_cpu, arg)); return _SUCCESS; } int i_lsb0(CPU *this_cpu) { int nargs = 1; U4 arg; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg)); clrb(&arg, _FLAG_LEAST_SIG_BIT); assert_f(wb_put(this_cpu, arg)); return _SUCCESS; } int i_lsb1(CPU *this_cpu) { int nargs = 1; U4 arg; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg)); setb(&arg, _FLAG_LEAST_SIG_BIT); assert_f(wb_put(this_cpu, arg)); return _SUCCESS; } int i_band(CPU *this_cpu) { int nargs = 2; U4 arg1, arg2; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg1)); assert_f(wb_get(this_cpu, &arg2)); assert_f(wb_put(this_cpu, arg1 & arg2)); return _SUCCESS; } int i_bor(CPU *this_cpu) { int nargs = 2; U4 arg1, arg2; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg1)); assert_f(wb_get(this_cpu, &arg2)); assert_f(wb_put(this_cpu, arg1 | arg2)); return _SUCCESS; } int i_bxor(CPU *this_cpu) { int nargs = 2; U4 arg1, arg2; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg1)); assert_f(wb_get(this_cpu, &arg2)); assert_f(wb_put(this_cpu, arg1 ^ arg2)); return _SUCCESS; } int i_binv(CPU *this_cpu) { int nargs = 1; U4 arg; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg)); assert_f(wb_put(this_cpu, ~arg)); return _SUCCESS; } int i_read(CPU *this_cpu) { int nargs = 1; ARL *arl; U4 arg_addr, /* address to read from */ bid; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg_addr)); /* address (and hence bid) not valid */ if (_AINVALID(arg_addr)) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_BNV; } bid = arg_addr / p_bom_size; /* * if we let bid be 0, what (other than the unallowable obvious) could * i_read() be used for? */ /* no explicit access */ if (!(arl = bat_get(this_cpu->bat, bid))) /* use implicit */ assert_f(arl = bat_get(cs_get(g_cs_root, 0)->bat, bid)); /* no read access */ if (!_READABLE(arl)) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_NRA; } assert_f(wb_put(this_cpu, (U4)spacio(arg_addr, cell_read, 0))); return _SUCCESS; } int i_write(CPU *this_cpu) { int nargs = 2; ARL *arl; U4 arg_addr, /* address to write to */ arg_wval, /* value to write */ bid; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg_addr)); assert_f(wb_get(this_cpu, &arg_wval)); /* address (and hence bid) not valid */ if (_AINVALID(arg_addr)) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_BNV; } bid = arg_addr / p_bom_size; /* * if we let bid be 0, what (other than the unallowable obvious) could * i_write() be used for? */ /* no explicit access */ if (!(arl = bat_get(this_cpu->bat, bid))) /* use implicit */ assert_f(arl = bat_get(cs_get(g_cs_root, 0)->bat, bid)); /* no write access */ if (!_WRITABLE(arl)) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_NWA; } spacio(arg_addr, cell_write, (U1)arg_wval); return _SUCCESS; } int i_throw(CPU *this_cpu) { int nargs = 2; U4 arg_cid, /* cid of target CPU */ arg_val; /* value to be thrown */ CPU *dest_cpu; /* ptr to the target CPU */ /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg_cid)); assert_f(wb_get(this_cpu, &arg_val)); /* * what could a throw to cid 0 potentially be used for? */ /* invalid cid */ if (_CINVALID(arg_cid)) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_CNV; } dest_cpu = cs_get(g_cs_root, arg_cid); /* target cpu does not exist */ if (!dest_cpu) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_CNE; } /* cb of target cpu is full and in preserve mode */ if (!cb_put(dest_cpu, this_cpu->cid, arg_val)) { assert_f(nargs == wb_restore(this_cpu, nargs)); /* the below line will not incur a penalty on this_cpu as _FAILURE_CBF's * cost value is 0: someone else's full mailbox shouldn't be grounds for * penalization (unless perhaps spamming is a problem) */ return _FAILURE_CBF; } return _SUCCESS; } int i_catch(CPU *this_cpu) { U4 hold1, hold2; int nputs; /* no data to get in cb */ if (!cb_get(this_cpu, &hold1, &hold2)) /* the below line will not incur a penalty on this_cpu as _FAILURE_CBE's * cost value is 0: checking an empty mailbox shouldn't be grounds for * penalization */ return _FAILURE_CBE; nputs = wb_put(this_cpu, hold1) + wb_put(this_cpu, hold2); /* no room for results */ if (2 != nputs) { assert_f(-nputs == wb_restore(this_cpu, -nputs)); assert_f(1 == cb_restore(this_cpu, 1)); return _FAILURE_WBF; } return _SUCCESS; } int i_fork(CPU *mother) { int nargs = 1; U4 arg_addr; /* address to become the child's PC value */ CPU *child = new_cpu(); /* not enough resources */ if (!child) return _FAILURE_NER; /* not enough args */ if (nargs > mother->wb.size) { old_cpu(child); return _FAILURE_WBE; } assert_f(wb_get(mother, &arg_addr)); /* address (and hence bid) not valid */ if (_AINVALID(arg_addr)) { old_cpu(child); assert_f(nargs == wb_restore(mother, nargs)); return _FAILURE_BNV; } /* link child into structures and sanity check for linking errors */ assert_f(rq_insert(&g_rq_root, child)); assert_f(eq_insert(&g_eq_curr, child)); assert_f(cs_insert(&g_cs_root, child)); assert_f(wb_put(mother, child->cid)); /* give child's id to mother */ assert_f(wb_put(child, mother->cid)); /* give mother's id to child */ child->pc = arg_addr; return _SUCCESS_FORK; } int i_alloc(CPU *this_cpu) { int nargs = 1; U4 arg_addr; /* bid to grab */ BOM *bom; ARL *arl_owner; ARL *arl_world; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg_addr)); /* address (and hence bid) not valid */ if (_AINVALID(arg_addr)) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_BNV; } arg_addr /= p_bom_size; bom = new_bom(arg_addr); arl_owner = new_arl(); /* not enough resources */ if (!bom || !arl_owner) { old_bom(bom); old_arl(arl_owner); assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_NER; } /* no room for results */ if (!wb_put(this_cpu, bom->bid*p_bom_size)) { old_bom(bom); old_arl(arl_owner); assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_WBF; } /* form ownership relation */ bom->cot = this_cpu; assert_f(bot_insert(&(this_cpu->bot), bom)); /* form access relation for owner */ arl_owner->cid = this_cpu->cid; arl_owner->bid = bom->bid; if (_OWNER_READ(this_cpu)) setb(&(arl_owner->priv), 0); else clrb(&(arl_owner->priv), 0); if (_OWNER_WRITE(this_cpu)) setb(&(arl_owner->priv), 1); else clrb(&(arl_owner->priv), 1); say(p_out_obj, "<new_arl: CPU=%u, BOM=%u>", arl_owner->cid, arl_owner->bid); assert_f(bat_insert(&(this_cpu->bat), arl_owner)); assert_f(cat_insert(&(bom->cat), arl_owner)); /* form access relation for world */ arl_world = bat_get(cs_get(g_cs_root, 0)->bat, bom->bid); assert_e(arl_world); if (_WORLD_READ(this_cpu)) setb(&(arl_world->priv), 0); else clrb(&(arl_world->priv), 0); if (_WORLD_WRITE(this_cpu)) setb(&(arl_world->priv), 1); else clrb(&(arl_world->priv), 1); assert_f(cat_insert(&(bom->cat), arl_world)); assert_f(bs_insert(&g_bs_root, bom)); return _SUCCESS; } int i_free(CPU *this_cpu) { int nargs = 1; U4 arg_addr; /* address within bom to be freed */ BOM *bom; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg_addr)); /* address (and hence bid) not valid */ if (_AINVALID(arg_addr)) return _FAILURE_BNV; /* * allowing bid to be 0 as a special case could be used by a cell to free * all boms it owns in one shot */ /* bid is not allocated */ if (!(bom = bs_get(g_bs_root, arg_addr/p_bom_size))) return _FAILURE_BNE; /* bid is not owned */ /*if (bom->cot->cid != this_cpu->cid)*/ if (bom->cot != this_cpu) /* should work as well as the above */ return _FAILURE_BNO; free_bom(bom); return _SUCCESS; } int i_term(CPU *this_cpu) { free_cpu(this_cpu); return _SUCCESS; } int i_grant(CPU *this_cpu) { int nargs = 3; U4 arg_bid, /* bid */ arg_cid, /* cid */ arg_prv; /* new privs */ CPU *cpu; ARL *arl; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg_bid)); assert_f(wb_get(this_cpu, &arg_cid)); assert_f(wb_get(this_cpu, &arg_prv)); arg_bid /= p_bom_size; /* bid not valid: everywhere else in the program (except here in i_grant and * again in i_revoke) for a BID to be valid, it must fall between 1 and * p_max_boms-1, inclusive. Here, a BID is allowed to be 0 (in order to * indicate granting or revoking permissions to everybody). Is this * correct??? */ if (arg_bid >= p_max_boms) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_BNV; } /* cid not valid */ if (arg_cid >= p_max_cpus) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_CNV; } /* bid not owned */ if (!bot_get(this_cpu->bot, arg_bid)) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_BNO; } /* cid not alive */ if (!(cpu = cs_get(g_cs_root, arg_cid))) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_CNE; } /* no prev access relation for cid and bid */ if (!(arl = bat_get(cpu->bat, arg_bid))) { /* not enough resources */ if (!(arl = new_arl())) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_NER; } arl->bid = arg_bid; arl->cid = arg_cid; say(p_out_obj, "<new_arl: CPU=%u, BOM=%u>", arl->cid, arl->bid); assert_f(bat_insert(&(cpu->bat), arl)); assert_f(cat_insert(&(bs_get(g_bs_root, arg_bid)->cat), arl)); } if (btest(arg_prv, 0)) setb(&(arl->priv), 0); else clrb(&(arl->priv), 0); if (btest(arg_prv, 1)) setb(&(arl->priv), 1); else clrb(&(arl->priv), 1); return _SUCCESS; } int i_revoke(CPU *this_cpu) { int nargs = 2; U4 arg_bid, arg_cid; CPU *cpu; BOM *bom; ARL *arl_sav; ARL adummy; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg_bid)); assert_f(wb_get(this_cpu, &arg_cid)); arg_bid /= p_bom_size; /* bid not valid: except within i_revoke and i_grant, a bid must fall * between 1 and p_max_boms-1, inclusive, to be valid. Here, a bid is * allowed to be 0 to effect special case 2. */ if (arg_bid >= p_max_boms) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_BNV; } /* cid not valid: except within i_revoke and i_grant, a cid must fall * between 1 and p_max_cpus-1, inclusive, to be valid. Here, a cid is * allowed to be 0 to effect special case 1. */ if (arg_cid >= p_max_cpus) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_CNV; } /* (special) case 0 (cid == 0, bid == 0): this_cpu wishes to revoke rights * from every CPU on every block it owns. Hasn't been coded... but should? * Or is it already handled in one of the special cases below? At the mo- * ment, this would be handled by special case 1; does this special case * handle this scenario correctly? */ /* (special) case 1 (cid == 0): no particular CPU singled out for permis- * sions revocation; special CPU ID 0 means everybody (right?), so ALL * have their rights to this block revoked. (Yes... this_cpu wishes to * revoke rights from every CPU on the block specified.) */ if (0 == arg_cid) { /* bid not owned */ if (!bot_get(this_cpu->bot, arg_bid)) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_BNO; } bom = bs_get(g_bs_root, arg_bid); adummy.cid = 0; arl_sav = cat_remove(&(bom->cat), &adummy); while (bom->cat) free_arl(bom, cs_get(g_cs_root, bom->cat->cid)); assert_f(cat_insert(&(bom->cat), arl_sav)); } /* (special) case 2 (cid != 0, bid == 0): no particular block specified for * revocation of rights. What does this mean? Does it mean the CPU singl- * ed out has its rights to ALL blocks owned by this_cpu revoked? (Yes... * this_cpu wishes to revoke rights from some CPU on every block this_cpu * owns.) */ else if (0 == arg_bid) { /* cid not alive */ if (!(cpu = cs_get(g_cs_root, arg_cid))) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_CNE; } /* for each bom, b, in this_cpu->bot */ /* free_arl(b, cpu), if any */ /*while (this_cpu->bot) { bom = bs_get(g_bs_root, this_cpu->bot->bid); orl = bot_remove(&(this_cpu->bot), bom); assert_f(bot_insert(&(orl_sav), orl)); free_arl(bom, cpu); } while (orl_sav) { orl = bot_remove(&(orl_sav), orl_sav); assert_f(bot_insert(&(this_cpu->bot), orl)); }*/ } /* (normal) case 3 (cid != 0, bid != 0): this is the "normal" case (for * which this instruction was first envisioned and written), which is not * to say that this case will be the most common use of i_revoke. */ else { /* bid not owned */ if (!bot_get(this_cpu->bot, arg_bid)) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_BNO; } /* cid not alive */ if (!(cpu = cs_get(g_cs_root, arg_cid))) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_CNE; } free_arl(bs_get(g_bs_root, arg_bid), cpu); } return _SUCCESS; } int i_chown(CPU *this_cpu) { int nargs = 2; U4 arg_addr, arg_cid; U4 bid; CPU *cpu; BOM *bom; ARL *arl_owner, *arl_world; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg_addr)); assert_f(wb_get(this_cpu, &arg_cid)); /* address (and hence bid) not valid */ if (_AINVALID(arg_addr)) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_BNV; } bid = arg_addr / p_bom_size; /* * future enhancement: if bid is allowed to be 0, i_chown() could be used * to transfer ownership to another cpu of ALL blocks owned by this_cpu */ /* cid not valid */ if (_CINVALID(arg_cid)) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_CNV; } /* bid not owned */ if (!bot_get(this_cpu->bot, bid)) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_BNO; } /* cid not alive */ if (!(cpu = cs_get(g_cs_root, arg_cid))) { assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_CNE; } arl_owner = new_arl(); /* not enough resources */ if (!arl_owner) { old_arl(arl_owner); assert_f(nargs == wb_restore(this_cpu, nargs)); return _FAILURE_NER; } bom = bs_get(g_bs_root, bid); /* dissolve prev ownership relation */ bom->cot = NULL; assert_f(bom == bot_remove(&(this_cpu->bot), bom)); /* dissolve prev access relations */ while (bom->cat) free_arl(bom, cs_get(g_cs_root, bom->cat->cid)); /* form new ownership relation */ bom->cot = cpu; assert_f(bot_insert(&(cpu->bot), bom)); /* form new access relation for owner */ arl_owner->cid = cpu->cid; arl_owner->bid = bom->bid; if (_OWNER_READ(cpu)) setb(&(arl_owner->priv), 0); else clrb(&(arl_owner->priv), 0); if (_OWNER_WRITE(cpu)) setb(&(arl_owner->priv), 1); else clrb(&(arl_owner->priv), 1); say(p_out_obj, "<new_arl: CPU=%u, BOM=%u>", arl_owner->cid, arl_owner->bid); assert_f(bat_insert(&(cpu->bat), arl_owner)); assert_f(cat_insert(&(bom->cat), arl_owner)); /* form new access relation for world */ assert_f(arl_world = bat_get(cs_get(g_cs_root, 0)->bat, bom->bid)); if (_WORLD_READ(cpu)) setb(&(arl_world->priv), 0); else clrb(&(arl_world->priv), 0); if (_WORLD_WRITE(cpu)) setb(&(arl_world->priv), 1); else clrb(&(arl_world->priv), 1); assert_f(cat_insert(&(bom->cat), arl_world)); return _SUCCESS; } int i_test(CPU *this_cpu) { int nargs = 1; U4 arg; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg)); if (0 == arg) nstep(&(this_cpu->pc), _DIRECTION(this_cpu), 1); return _SUCCESS; } int i_wtor(CPU *this_cpu) { int nargs = 2; U4 arg_ndx; U4 arg_val; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg_ndx)); assert_f(wb_get(this_cpu, &arg_val)); this_cpu->reg[arg_ndx % p_nregs] = arg_val; return _SUCCESS; } int i_itow(CPU *this_cpu) { if (!wb_put(this_cpu, this_cpu->cid)) return _FAILURE_WBF; return _SUCCESS; } int i_rtow(CPU *this_cpu) { int nargs = 1; U4 arg_ndx; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg_ndx)); assert_f(wb_put(this_cpu, this_cpu->reg[arg_ndx % p_nregs])); return _SUCCESS; } int i_mexec(CPU *this_cpu) { return _SUCCESS; } /* this is going to require a lot of the same code that is in main(), like * checking if previous instruction executed was TERM; same for MEXEC. Need * to abstract that instruction execution code into a modular function that * can be called from main(), i_repeat(), and i_mexec() */ /* execute the instruction (I) following REPEAT n times; reduce * this_cpu->ts by the time cost of I for each successful invocation of I; * stop when n is exhausted or I fails; this_cpu->ts may become negative; * the time cost of the REPEAT instruction itself will be applied in main() */ int i_repeat(CPU *this_cpu) { int nargs = 1; U4 arg_n; U4 i; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; /* get n */ assert_f(wb_get(this_cpu, &arg_n)); /* get I */ /*for (i=0; i<arg_n; ++i) {*/ /* run I; save statcode */ /* apply time cost of I to TS (regardless of success or failure) */ /* apply statcode penalty to ERR (regardless of success or failure) */ /* if I failed, break */ /*}*/ /* if I executed successfully n times, return _SUCCESS */ /* if not, return _FAILURE (whatever the last I failed with) */ return _SUCCESS; } int i_umask(CPU *this_cpu) { int nargs = 1; U4 arg; /* not enough args */ if (nargs > this_cpu->wb.size) return _FAILURE_WBE; assert_f(wb_get(this_cpu, &arg)); if (btest(arg, 0)) setb(&(this_cpu->fl), _FLAG_UMASK_OWNER_READ); else clrb(&(this_cpu->fl), _FLAG_UMASK_OWNER_READ); if (btest(arg, 1)) setb(&(this_cpu->fl), _FLAG_UMASK_OWNER_WRITE); else clrb(&(this_cpu->fl), _FLAG_UMASK_OWNER_WRITE); if (btest(arg, 2)) setb(&(this_cpu->fl), _FLAG_UMASK_WORLD_READ); else clrb(&(this_cpu->fl), _FLAG_UMASK_WORLD_READ); if (btest(arg, 3)) setb(&(this_cpu->fl), _FLAG_UMASK_WORLD_WRITE); else clrb(&(this_cpu->fl), _FLAG_UMASK_WORLD_WRITE); return _SUCCESS; } int i_nop(CPU *this_cpu) { return _SUCCESS; } int i_pass(CPU *this_cpu) { setb(&(this_cpu->fl), _FLAG_PASS); return _SUCCESS; } /* reads the value after the INLINE instruction (from memory) into the WB * (where "after" depends on _FLAG_INCREASE_OR_DECREASE). allows "inlining" * of numeric constants into a bug's body code, thus the name. saves a bug * from having to construct from scratch any numeric constants needed. */ int i_inline(CPU *this_cpu) { U4 bid; ARL *arl; nstep(&(this_cpu->pc), _DIRECTION(this_cpu), 1); /* assured by above call to nstep(), but sanity check anyway */ assert_e(!_AINVALID(this_cpu->pc)); bid = this_cpu->pc / p_bom_size; /* no explicit access */ if (!(arl = bat_get(this_cpu->bat, bid))) /* use implicit */ assert_f(arl = bat_get(cs_get(g_cs_root, 0)->bat, bid)); /* read access not granted */ if (!_READABLE(arl)) return _FAILURE_NRA; /* no room for result */ if (!wb_put(this_cpu, (U4)spacio(this_cpu->pc, cell_read, 0))) return _FAILURE_WBF; return _SUCCESS; } int i_clr(CPU *this_cpu) { this_cpu->wb.size = 0; return _SUCCESS; } /***************************************************************************** * main * *****************************************************************************/ int main(int argc, char *argv[]) { CPU *cpu; BOM *bom; ARL *arl; int i; int ret; int status; int etime; int next_pmutation = 0; int next_lmutation = 0; U4 P; int lmut_length; U4 A, B, n; U1 save; BOOL dirA, dirB, spanA, spanB, overlap; BOOL maxed_ts = _FALSE; U4 bid; U1 ins; int report = 0; const GrVideoMode *gvm; assert_e((4 == sizeof(U4)) && (2 == sizeof(U2)) && (1 == sizeof(U1))); assert_e(2 == argc); say(_TRUE, "initializing...\n"); assert_f(!atexit(cleanup)); /* map SIGINT (usually CTRL-C) to interrupt() [can still use CTRL-\ * (SIGQUIT) to abort termination] */ assert_f(SIG_ERR != signal(SIGINT, interrupt)); /* read in parameters from *.ini file */ init_params(argv[1]); if (p_iface) { /* GRX: put screen in graphics mode */ GrSetMode(GR_default_graphics); /* terminal window size in characters */ gvm = GrCurrentVideoMode(); g_lines = gvm->height/_CHAR_CELL_HEIGHT; g_cols = gvm->width/_CHAR_CELL_WIDTH; /* for pixel view, override viewport dimensions */ if (pixel == p_vport_cell) { p_vport_width = gvm->width; p_vport_height = gvm->height-(_OSP_VPORT_YOS+_OSP_CLINE_HEIGHT)* _CHAR_CELL_HEIGHT; } /* clip viewport dimensions based on terminal window size */ else { if (p_vport_width > g_cols/(p_vport_cell?2:7)) p_vport_width = g_cols/(p_vport_cell?2:7); if (p_vport_height > g_lines-_OSP_VPORT_YOS-_OSP_CLINE_HEIGHT) p_vport_height = g_lines-_OSP_VPORT_YOS-_OSP_CLINE_HEIGHT; } /* initialize color pairs for viewport mode */ g_egacolors = GrAllocEgaColors(); g_color_pairs[0][mutate] = MAGENTA/*RED*//*YELLOW*/; g_color_pairs[1][mutate] = BLACK; g_color_pairs[0][cell_read] = GREEN; g_color_pairs[1][cell_read] = BLACK; g_color_pairs[0][cell_write] = YELLOW/*RED*/; g_color_pairs[1][cell_write] = BLACK; g_color_pairs[0][execute] = CYAN; g_color_pairs[1][execute] = BLACK; g_color_pairs[0][initialize] = BLUE/*MAGENTA*/; g_color_pairs[1][initialize] = BLACK; g_color_pairs[0][touch] = BLUE; g_color_pairs[1][touch] = BLACK; print_template(p_iface); } /* allocate space for g_space */ assert_f(g_space = (U1 *)malloc(p_bom_size * p_max_boms * sizeof(U1))); /* allocate the BID and CID pools */ assert_f(g_bpool = (RANGE *)malloc(sizeof(RANGE))); assert_f(g_cpool = (RANGE *)malloc(sizeof(RANGE))); g_bpool->a = 1; g_bpool->b = p_max_boms-1; g_bpool->p_L = NULL; g_bpool->p_R = NULL; g_cpool->a = 1; g_cpool->b = p_max_cpus-1; g_cpool->p_L = NULL; g_cpool->p_R = NULL; /* Create special meaning CPU, CID=0 */ assert_f(cpu = new_cpu()); cpu->cid = 0; assert_f(cs_insert(&g_cs_root, cpu)); /* CPU 0 should always be the very last CPU reaped by virtue of the fact * that its err=age=cid=0 (the first two of which never change bcz CPU 0 * isn't in the EQ). May not want to do this if RQ becomes an AVL tree or * if cid is no longer used as a key. */ assert_f(rq_insert(&g_rq_root, cpu)); /* form world access privs... */ for (i=1; i<p_max_boms; ++i) { assert_f(arl = new_arl()); assert_f(bom = new_bom(0)); /* assured by get_bid() (called by new_bom()) and the fact that the BS * will not be exhausted due to the specific upper limit placed on this * for loop. */ assert_e(bom->bid); arl->bid = bom->bid; arl->cid = 0; arl->priv = p_fspace_read | p_fspace_write; say(p_out_obj, "<new_arl: CPU=%u, BOM=%u>", arl->cid, arl->bid); assert_f(bat_insert(&(cpu->bat), arl)); assert_f(bs_insert(&g_bs_root, bom)); /* the following linkings are only to prevent free_bom() below from * crashing... they are not necessary for correct operation. in any * case, free_bom() will undo these linkings */ assert_f(bot_insert(&(cpu->bot), bom)); bom->cot = cpu; } while (g_bs_root) free_bom(g_bs_root); /* Create special meaning BOM, BID=0 */ assert_f(bom = new_bom(0)); bom->bid = 0; assert_f(bs_insert(&g_bs_root, bom)); /* Create ancestor CPU (seed cell) */ assert_f(cpu = new_cpu()); /* places the newly allocated address of the BOM in the WB */ assert_f(wb_put(cpu, (U4)nrandom(p_max_boms)*p_bom_size)); assert_f(_SUCCESS == i_alloc(cpu)); /* points the PC to the first instruction in the BOM */ assert_f(_SUCCESS == i_jump(cpu)); nstep(&(cpu->pc), _DIRECTION(cpu), 1); assert_f(rq_insert(&g_rq_root, cpu)); assert_f(eq_insert(&g_eq_curr, cpu)); assert_f(cs_insert(&g_cs_root, cpu)); /* a negative p_vport_offset indicates seed cell should be in view; * setting of p_vport_offset must be before first call to spacio(), * otherwise what's shown onscreen doesn't match g_space contents */ if (0 > p_vport_offset) p_vport_offset = cpu->pc-10; /* randomize contents of g_space */ if (p_random_space) for (i=p_bom_size; i<p_bom_size * p_max_boms * sizeof(U1); ++i) spacio(i, initialize, (U1)nrandom(256)); /* seed g_space with ancestor cell genome... */ /* reverse order cpu->pc += sizeof(g_seed)+1; for (i=0; i<sizeof(g_seed); ++i) spacio(cpu->pc-i, initialize, g_seed[i]); i_spin(cpu); */ /* forward order */ for (i=0; i<sizeof(g_seed); ++i) spacio(cpu->pc+i, initialize, g_seed[i]); say(p_out_all, "executing...\n"); /* for each cpu in the execution queue */ while (g_eq_curr) { /* print all sorts of statistics... */ if ((0 < p_report_freq) && (++report >= p_report_freq)) { report = 0; print_stats(); /*wrefresh(g_win);*/ } /* EXTRACT out to a separate function */ /* if BOM threshold has been exceeded... */ if (g_nboms >= p_max_boms*p_bron) { say(p_out_all, "BOM threshold exceeded\n" "\treaper activated\n"); /* reap some cpus */ while (g_nboms >= p_max_boms*p_broff) { cpu = rq_grab(); say(p_out_all, "\tCPU %010u (age %010u, err %010u) culled\n", cpu->cid, cpu->age, cpu->err); free_cpu(cpu); } say(p_out_all, "\treaper deactivated\n"); if (!g_eq_curr) break; } /* EXTRACT out to a separate function */ /* if CPU threshold has been exceeded... */ if (g_ncpus >= p_max_cpus*p_cron) { say(p_out_all, "CPU threshold exceeded\n" "\treaper activated\n"); /* reap some cpus */ while (g_ncpus >= p_max_cpus*p_croff) { cpu = rq_grab(); say(p_out_all, "\tCPU %010u (age %010u, err %010u) culled\n", cpu->cid, cpu->age, cpu->err); free_cpu(cpu); } say(p_out_all, "\treaper deactivated\n"); if (!g_eq_curr) break; } g_eq_curr = g_eq_curr->eq_N; g_eq_curr->ts += p_ts_size; say(p_out_dbg, "CPU %010u: awarded TS\n", g_eq_curr->cid); /* begin working off timeslice: decreases the current cell's TS; increases * the current cell's age and (potentially) err, as well as increasing * next_pmutation. This is why code blocks executing conditional upon * these values are enclosed within this loop. */ while (g_eq_curr) { /* EXTRACT out to a separate function */ /* point mutation: to introduce new material (previously unused * instructions and numeric constants) */ while ((0 < p_pmutate_freq) && (next_pmutation >= p_pmutate_freq)) { /* as BOM 0 is not used to hold cell-code, mutating it is pointless; * if BOM 0 is ever used in the future to hold Evol internal data, * mutating it would be disasterous! */ do P = (nrandom(p_max_boms)*p_bom_size)+nrandom(p_bom_size); while (p_bom_size > P); spacio(P, mutate, (U1)nrandom(256)); say(p_out_dbg, "point mutation at %010u\n", P); next_pmutation -= p_pmutate_freq; } /* EXTRACT out to a separate function */ /* line mutation: to (hopefully) simulate the effects of genetic * crossover */ while ((0 < p_lmutate_freq) && (next_lmutation >= p_lmutate_freq)) { do lmut_length = nrandom(p_bom_size*p_multiplier); while (0 >= lmut_length); do A = (nrandom(p_max_boms)*p_bom_size)+nrandom(p_bom_size); while (p_bom_size > A); n = p_max_boms*p_bom_size; do { do B = (nrandom(p_max_boms)*p_bom_size)+nrandom(p_bom_size); while ((p_bom_size > B) && (B != A)); overlap = _FALSE; /* * * I'm thinkin' that nstep(), particularly the 'n' of nstep(), * can make the following code much more readable... * */ /* only 1st range spans boundary */ if ((A+lmut_length > n) && (B+lmut_length <= n)) { spanA = _TRUE; spanB = _FALSE; if ((A+lmut_length-n+p_bom_size > B) || (B+lmut_length > A)) overlap = _TRUE; /* if (((A+lmut_length-1)%n+p_bom_size > B) || (B+lmut_length > A)) overlap = _TRUE; */ } /* only 2nd range spans boundary */ else if ((B+lmut_length > n) && (A+lmut_length <= n)) { spanA = _FALSE; spanB = _TRUE; if ((B+lmut_length-n+p_bom_size > A) || (A+lmut_length > B)) overlap = _TRUE; /* if (((B+lmut_length-1)%n+p_bom_size > A) || (A+lmut_length > B)) overlap = _TRUE; */ } /* both ranges span boundary */ else if ((A+lmut_length > n) && (B+lmut_length > n)) { spanA = _TRUE; spanB = _TRUE; overlap = _TRUE; } /* neither range spans boundary */ else { spanA = _FALSE; spanB = _FALSE; if ((A < B) && (A+lmut_length > B)) overlap = _TRUE; else if ((B < A) && (B+lmut_length > A)) overlap = _TRUE; } } while (overlap); dirA = nrandom(2); dirB = nrandom(2); A = dirA?(spanA?(A+lmut_length-1)%n+p_bom_size:A+lmut_length-1):A; B = dirB?(spanB?(B+lmut_length-1)%n+p_bom_size:B+lmut_length-1):B; for (i=0; i<lmut_length; ++i) { save = g_space[A]; spacio(A, mutate, g_space[B]); spacio(B, mutate, save); nstep(&A, dirA, 1); nstep(&B, dirB, 1); } say( p_out_dbg, "line mutation of size %d from %010u to %010u\n", lmut_length, A, B ); next_lmutation -= p_lmutate_freq; } /* instant death due to excessive error */ if (g_eq_curr->err >= p_max_err) { say(p_out_dbg, "CPU %010u: instant death (excessive error)\n", g_eq_curr->cid); free_cpu(g_eq_curr); break; } /* instant death due to excessive age */ if (g_eq_curr->age >= p_max_age) { say(p_out_dbg, "CPU %010u: instant death (excessive age)\n", g_eq_curr->cid); free_cpu(g_eq_curr); break; } if (g_eq_curr->ts < p_min_ts) { /* timeslice expired */ say(p_out_dbg, "CPU %010u: TS expired\n", g_eq_curr->cid); maxed_ts = _FALSE; break; } else if (g_eq_curr->ts >= p_max_ts) { say(p_out_dbg, "CPU %010u: maxed TS\n", g_eq_curr->cid); maxed_ts = _TRUE; } if (btest(g_eq_curr->fl, _FLAG_PASS)) { say(p_out_dbg, "CPU %010u: attempting to pass: ", g_eq_curr->cid); clrb(&(g_eq_curr->fl), _FLAG_PASS); if (!maxed_ts) { say(p_out_dbg, "allowed\n"); break; } say(p_out_dbg, "not allowed (maxed TS)\n"); } /* * everything from here up TS is not applied... */ /* * everything from here down TS is applied... */ /* i_term() causes the invoking cpu to be removed from the EQ, changing * the g_eq_curr pointer; since we do not know in advance which * instruction will be executed, save g_eq_curr prior to invoking *any* * instruction so this condition can be checked below */ cpu = g_eq_curr; /* reset elapsed time counter */ etime = 0; say(p_out_dbg, "CPU %010u: PC %010u: ", g_eq_curr->cid, g_eq_curr->pc); /* assured by the fact that only i_jump() and i_fork() can set a cell's * pc and they both perform a bom validity check first; thus no bom * validity check in main() required... */ assert_e(!_AINVALID(g_eq_curr->pc)); /* calculate the actual block id */ bid = g_eq_curr->pc / p_bom_size; /* no explicit access */ if (!(arl = bat_get(g_eq_curr->bat, bid))) /* use implicit */ assert_f(arl = bat_get(cs_get(g_cs_root, 0)->bat, bid)); /* read access not granted */ if (!_READABLE(arl)) { status = _FAILURE_NRA; say(p_out_dbg, "%s\n", g_stab[status].text); etime += 1; /* one time unit spent on this */ } /* read access granted */ else { /* instruction not valid */ if (_NINSTRUCTIONS <= (ins = spacio(g_eq_curr->pc, execute, 0))) { status = _FAILURE_INV; say(p_out_dbg, "%s (%.2x)\n", g_stab[status].text, ins); etime += 1; /* one time unit spent on this */ } /* instruction valid */ else { say(p_out_ins, "executing %6s (%.2x): ", g_itab[ins].text, ins); status = (*(g_itab[ins].addr))(g_eq_curr); say(p_out_ins, "%s\n", g_stab[status].text); etime += g_itab[ins].cost + 1; /* time spent on this */ } } /* if we are still who we think we are and haven't committed suicide */ if (cpu == g_eq_curr) adjust(g_eq_curr, etime, status); tick(etime); next_pmutation += etime; next_lmutation += etime; } } say(p_out_all, "systemic extinction\n"); exit(0); } /* * EOF vim: ts=2 noet ic */