diff options
author | Jose Antonio Ortega Ruiz <jao@gnu.org> | 2019-04-09 02:59:08 +0100 |
---|---|---|
committer | Jose Antonio Ortega Ruiz <jao@gnu.org> | 2019-04-09 02:59:08 +0100 |
commit | 5c331f54c23dd5db6ee4cd92bf67460935aaec5f (patch) | |
tree | 71a0f73e77b7b2afadaf066162225c634abae585 | |
parent | 5e854d5060e4874d27049cda500535bb7eabe6d9 (diff) | |
download | mdk-5c331f54c23dd5db6ee4cd92bf67460935aaec5f.tar.gz mdk-5c331f54c23dd5db6ee4cd92bf67460935aaec5f.tar.bz2 |
Change vm->address_list from GSList to GQueue
The current emulator uses an unbounded linked list for tracking the
memory locations our program has traveled through. On a 64 bit system,
this requires 16 bytes of data for every instruction a MIX program
performs. For small programs that are light on computation cycles,
this does not cause a noticeable issue.
For programs that execute hundreds of millions of instructions, this
causes the memory footprint of the virtual machine to explode. I have
attached an example MIXAL program that will cause the VM to grow to
over 3 GB of memory usage when run.
To run the sample, compile coin-opt.mixal (attached), run it in mixvm,
and enter 499 at the prompt. Or use the following steps.
This patch changes all the appropriate references to GQueue references
and also caps the backtrace at 1000, which can be changed in the
mixlib/mix_vm.h header. I feel like 1000 is a reasonable limit for the
vast majority of debugging needs. Most people are looking back at the
most recent 100 instructions or so.
You can get the original behavior (unlimited tracing) back by setting
the MIX_MAXTRACE to -1, albeit with a slightly higher memory cost (24
bytes per instruction). Or you can turn it off entirely by setting it
to 0.
Using a queue doesn't change the logic of the program in any
significant way, and it allows programs to run for an extended period
of time without consuming all the memory on the machine and slowing
down to a crawl.
-Kevin Brunelle
-rw-r--r-- | doc/mdk_mixvm.texi | 9 | ||||
-rw-r--r-- | mixlib/mix_vm.c | 50 | ||||
-rw-r--r-- | mixlib/mix_vm.h | 12 | ||||
-rw-r--r-- | mixlib/xmix_vm.h | 3 | ||||
-rw-r--r-- | mixlib/xmix_vm_handlers.c | 45 | ||||
-rw-r--r-- | mixlib/xmix_vm_handlers.h | 1 | ||||
-rw-r--r-- | samples/coin-opt.mixal | 114 |
7 files changed, 214 insertions, 20 deletions
diff --git a/doc/mdk_mixvm.texi b/doc/mdk_mixvm.texi index 580f641..f0da1cf 100644 --- a/doc/mdk_mixvm.texi +++ b/doc/mdk_mixvm.texi @@ -417,6 +417,15 @@ MIX > @end example @end deffn +@deffn {debug command} sbt [NUMBER] +This command changes the limit for the backtrace of executed instructions. +If the number is omitted, the command prints the current limit. If you +use a 0, backtraces are turned off. This can improve performance. If you +wish for all the instructions to be logged, a -1 will enable that. The +amount of memory required for unlimited backtraces can be substantial +for long-running programs. +@end deffn + @deffn {debug command} pbt [INS_NUMBER] This command prints a backtrace of executed instructions. Its optional argument @var{ins_number} is the number of instructions to print. If it diff --git a/mixlib/mix_vm.c b/mixlib/mix_vm.c index d714bba..94eae1e 100644 --- a/mixlib/mix_vm.c +++ b/mixlib/mix_vm.c @@ -81,8 +81,8 @@ vm_reset_reload_ (mix_vm_t *vm, gboolean is_reload) if (vm->address_list) { - g_slist_free (vm->address_list); - vm->address_list = NULL; + g_queue_free (vm->address_list); + vm->address_list = g_queue_new (); } } @@ -99,7 +99,8 @@ mix_vm_new (void) vm->symbol_table = NULL; vm->src_file = NULL; vm->pred_list = mix_predicate_list_new (vm); - vm->address_list = NULL; + vm->max_backtrace_amount = MIX_MAX_TRACE_AMOUNT; + vm->address_list = g_queue_new (); vm->last_error = MIX_VM_ERROR_NONE; for (i = 0; i < BD_NO_; ++i) @@ -126,7 +127,7 @@ mix_vm_delete (mix_vm_t * vm) if (vm->symbol_table != NULL) mix_symbol_table_delete (vm->symbol_table); if (vm->src_file != NULL) mix_src_file_delete (vm->src_file); if (vm->pred_list != NULL) mix_predicate_list_delete (vm->pred_list); - if (vm->address_list != NULL) g_slist_free (vm->address_list); + if (vm->address_list != NULL) g_queue_free (vm->address_list); for (i = 0; i < BD_NO_; ++i) mix_device_delete (vm->devices[i]); mix_vm_clock_delete (vm->clock); @@ -452,9 +453,14 @@ mix_vm_run (mix_vm_t *vm) while ( !is_halted_ (vm) ) { mix_word_to_ins_uncheck (get_cell_ (vm, get_loc_ (vm)), ins); - vm->address_list = - g_slist_prepend (vm->address_list, - GINT_TO_POINTER ((gint)get_loc_ (vm))); + if ( vm->max_backtrace_amount != 0 ) { + g_queue_push_head (vm->address_list, + GINT_TO_POINTER ((gint)get_loc_ (vm))); + if ( vm->max_backtrace_amount > 0 && + g_queue_get_length (vm->address_list) > vm->max_backtrace_amount ) { + g_queue_pop_tail (vm->address_list); + } + } if ( !(*ins_handlers_[ins.opcode]) (vm,&ins) ) return set_status_ (vm, MIX_VM_ERROR); else @@ -476,9 +482,14 @@ mix_vm_exec_next (mix_vm_t *vm) g_return_val_if_fail (vm != NULL, MIX_VM_ERROR); if (get_loc_ (vm) >= MIX_VM_CELL_NO) halt_ (vm, TRUE); if (is_halted_ (vm)) return set_status_ (vm, MIX_VM_HALT); - vm->address_list = - g_slist_prepend (vm->address_list, - GINT_TO_POINTER ((gint)get_loc_ (vm))); + if ( vm->max_backtrace_amount != 0 ) { + g_queue_push_head (vm->address_list, + GINT_TO_POINTER ((gint)get_loc_ (vm))); + if ( vm->max_backtrace_amount > 0 && + g_queue_get_length (vm->address_list) > vm->max_backtrace_amount ) { + g_queue_pop_tail (vm->address_list); + } + } mix_word_to_ins_uncheck (get_cell_ (vm, get_loc_ (vm)), ins); if (!(*ins_handlers_[ins.opcode]) (vm, &ins)) return set_status_ (vm, MIX_VM_ERROR); @@ -698,9 +709,24 @@ mix_vm_get_uptime (const mix_vm_t *vm) } /* Get the list of addresses for executed instructions */ -const GSList * +GQueue * mix_vm_get_backtrace (const mix_vm_t *vm) { g_return_val_if_fail (vm != NULL, NULL); - return get_address_list_ (vm); + return vm->address_list; +} + +gint +mix_vm_get_max_trace (const mix_vm_t *vm) +{ + g_return_val_if_fail (vm != NULL, -2); + return vm->max_backtrace_amount; +} + +void +mix_vm_set_max_trace (mix_vm_t *vm, gint val) +{ + g_return_if_fail (vm != NULL); + g_return_if_fail (val >= -1); + vm->max_backtrace_amount = val; } diff --git a/mixlib/mix_vm.h b/mixlib/mix_vm.h index 0f4e690..4b07164 100644 --- a/mixlib/mix_vm.h +++ b/mixlib/mix_vm.h @@ -34,6 +34,9 @@ /* Comparison flag */ typedef enum { mix_LESS, mix_EQ, mix_GREAT } mix_cmpflag_t; +/* Maximum number of addresses for backtraces: -1 = unlimited, 0 = off */ +enum { MIX_MAX_TRACE_AMOUNT = 500 }; + /* Number of memory cells in the virtual machine */ enum { MIX_VM_CELL_NO = 4000 }; @@ -247,9 +250,16 @@ extern mix_time_t mix_vm_get_uptime (const mix_vm_t *vm); /* Get the list of addresses for executed instructions */ -extern const GSList * +extern GQueue * mix_vm_get_backtrace (const mix_vm_t *vm); +/* Get the maximum number of instructions we will trace */ +gint +mix_vm_get_max_trace (const mix_vm_t *vm); + +/* Set the maximum number of instructions we will trace */ +void +mix_vm_set_max_trace (mix_vm_t *vm, gint val); #endif /* MIX_VM_H */ diff --git a/mixlib/xmix_vm.h b/mixlib/xmix_vm.h index 0d6605f..34dedd7 100644 --- a/mixlib/xmix_vm.h +++ b/mixlib/xmix_vm.h @@ -50,6 +50,7 @@ struct mix_vm_t mix_vm_status_t status; mix_vm_error_t last_error; mix_device_t * devices[BD_NO_]; + gint max_backtrace_amount; /* the limit of backtraces */ mix_address_t start_addr; /* start address of loaded file */ GTree *line_table; /* source line no -> address */ GTree *address_table; /* adress -> source line no */ @@ -59,7 +60,7 @@ struct mix_vm_t mix_src_file_t *src_file; /* source of last loaded code file */ mix_device_factory_t factory; /* the factory for new devices */ mix_predicate_list_t *pred_list; /* predicates for conditional bps */ - GSList *address_list; /* list of executed addresses */ + GQueue *address_list; /* list of executed addresses */ }; /* Macros for accessing/modifying the above structure. diff --git a/mixlib/xmix_vm_handlers.c b/mixlib/xmix_vm_handlers.c index c964116..f356607 100644 --- a/mixlib/xmix_vm_handlers.c +++ b/mixlib/xmix_vm_handlers.c @@ -86,6 +86,8 @@ mix_vm_command_info_t commands_[] = { "strace on|off"}, { "pbt", cmd_pbt_, N_("Print backtrace of executed instructions"), "pbt [INS_NO] (e.g pbt 5)"}, + { "sbt", cmd_sbt_, N_("Set limit on backtrace of executed instructions"), + "sbt [LIMIT] (e.g sbt 100)"}, { "stime", cmd_stime_, N_("Turn on/off timing statistics"), "stime on|off"}, { "ptime", cmd_ptime_, N_("Print current time statistics"), "ptime"}, @@ -1306,6 +1308,7 @@ gboolean cmd_pbt_ (mix_vm_cmd_dispatcher_t *dis, const gchar *arg) { enum {SIZE = 256}; + static const gchar *NULLSTR = "(null)"; static gchar BUFFER[SIZE]; gint no = atoi (arg); gint k = 0, address; @@ -1314,29 +1317,59 @@ cmd_pbt_ (mix_vm_cmd_dispatcher_t *dis, const gchar *arg) char *name = file ? g_path_get_basename (mix_src_file_get_path (file)) : NULL; - const GSList *add = mix_vm_get_backtrace (dis->vm); - while (add && (no == 0 || k < no)) + GQueue *add = mix_vm_get_backtrace (dis->vm); + while (g_queue_get_length (add) > k && (no == 0 || k < no)) { BUFFER[0] = '\0'; - address = GPOINTER_TO_INT (add->data); + address = GPOINTER_TO_INT (g_queue_peek_nth (add, k)); line = mix_vm_get_address_lineno (dis->vm, address); if (line && file) { int j = 0; g_snprintf (BUFFER, SIZE, "%s", mix_src_file_get_line (file, line)); - while (!isspace (BUFFER[j])) j++; + while ( (j < SIZE - 1) && (BUFFER[j] != '\n') && (BUFFER[j] != '\r') + && (BUFFER[j] != '\f') && (BUFFER[j] != '\0') ) j++; BUFFER[j] = '\0'; } - if (strlen (BUFFER) == 0) g_snprintf (BUFFER, SIZE, "%d", address); + if ( (strlen (BUFFER) == 0) || !(strcmp(NULLSTR,BUFFER)) ) + g_snprintf (BUFFER, SIZE, "%d", address); fprintf (dis->out, "#%d\t%s\tin %s%s:%d\n", k, BUFFER, name, MIX_SRC_DEFEXT, line); ++k; - add = add->next; } return TRUE; } gboolean +cmd_sbt_ (mix_vm_cmd_dispatcher_t *dis, const gchar *arg) +{ + gint no = atoi (arg); + GQueue *add = mix_vm_get_backtrace (dis->vm); + + if ( strlen(arg) == 0 ) { + log_message_ (dis, "Backtrace limit is %d instructions", + mix_vm_get_max_trace(dis->vm)); + } else { + if ( no >= -1 ) { + log_message_ (dis, "Backtrace limit changed from %d to %d instructions", + mix_vm_get_max_trace(dis->vm), no); + mix_vm_set_max_trace (dis->vm, no); + + /* We might have shrunk the queue and need to resize it */ + if ( no >= 0 ) { + while ( g_queue_get_length (add) > no ) { + g_queue_pop_tail(add); + } + } + + } else { + log_error_ (dis, "Error: %d is not a valid number of instructions.", no); + } + } + return TRUE; +} + +gboolean cmd_slog_ (mix_vm_cmd_dispatcher_t *dis, const gchar *arg) { static const gchar *ON = "on"; diff --git a/mixlib/xmix_vm_handlers.h b/mixlib/xmix_vm_handlers.h index decdd24..be276d4 100644 --- a/mixlib/xmix_vm_handlers.h +++ b/mixlib/xmix_vm_handlers.h @@ -71,6 +71,7 @@ DEC_FUN (cbpm_); DEC_FUN (cbpc_); DEC_FUN (cbpo_); DEC_FUN (pbt_); +DEC_FUN (sbt_); DEC_FUN (slog_); DEC_FUN (pprog_); DEC_FUN (psrc_); diff --git a/samples/coin-opt.mixal b/samples/coin-opt.mixal new file mode 100644 index 0000000..6d86d45 --- /dev/null +++ b/samples/coin-opt.mixal @@ -0,0 +1,114 @@ +* Count the number of coin combinations + +TERM EQU 19 Terminal uses 14 words or 70 char +VAL EQU 4:5 The value of a coin +AMT EQU 1:3 The current amount of those coins + +* Start of the program. + ORIG 1000 +PROG OUT PRMPT(TERM) +* Get the value we want combos for + IN INPT1(TERM) + LDA INPT1 THE NUMBER IS PROBABLY IN THIS WORD + LDX INPT2 WE LOAD 10 CHARS OF INPUT + JAP 1F MAKE SURE THEY ENTERED SOMETHING + JXZ PROG MAYBE THEY HAD SPACES FIRST? +1H CMPX PRMPT(5:5) IS THE LAST CHAR A SPACE + JNE 3F IF NOT THEN WE CAN MOVE ON + SRAX 1 IF IT IS, SHIFT RIGHT 1 SPOT AND + JMP 1B LOOP BACK TO MAKE SURE +3H NUM + CMPA MAX + JG PROG + STZ MAX + STA WANTED + +* Get a current value of the coins we have +CURRVAL LD6 TYPES How many kinds of coins + LDA COINS,6(AMT) Load current amount of first coin +2H DEC6 1 Move to next coin + ADD COINS,6(AMT) Add the amount of the next coin + J6NZ 2B Keep going for all combos + +* If less than goal, add a coin + CMPA WANTED Compare the current value to wanted value + JGE 1F If it's < wanted + LDA COINS(AMT) { + ADD COINS(VAL) add another of the first coin + STA COINS(AMT) and go back to CURRVAL + JMP CURRVAL } +1H JG 3F If it's = wanted + +* It was equal, print, and the fall through + LDX MAX + INCX 1 We use this for counting the hits + LD6 TYPES We iterate through the types + ENT5 0 This points to the word in PBUFF + STX MAX + LDA MAX + CHAR + STX PBUF,5 Print the current number of hits +1H INC5 2 Move to the next column + ENTA 0 + LDX COINS,6(AMT) Get the number of coins by dividing the amount + DIV COINS,6(VAL) by the value of 1 coin +6H CHAR + STX PBUF,5(3:5) Print the current amount + DEC6 1 Go to the next coin type + J6NN 1B If we go negative, we're done with coins + OUT PBUF(TERM) Output the line to the console + +* Equal or Greater, find first non-zero spot, add one to the next +* spot up, and then zero it out. +3H ENT5 0 +5H LDA COINS,5(AMT) Load current coin value + INC5 1 Go to next type of coin + CMP5 TYPES Compare to number of coin types + JG DONE If greater, we're out of coins + JAZ 5B If current coin value is 0, go to next coin + LDA COINS,5(AMT) Load next coin up + ADD COINS,5(VAL) Add it's value to the amount + STA COINS,5(AMT) Save it + DEC5 1 Go back to previous type + STZ COINS,5(AMT) Zero it out + JMP CURRVAL Go back to the main loop +DONE HLT +* Tables to keep the values and counts +* The below can be used to test for 1000 (1:2), 100 (3:4), and 10 (5:5) +MAX CON 499 MAX AMOUNT OF CENTS BEFORE COUNTER RESETS IS 221 +WANTED CON 62 THE COMBINATION WE WANT +TYPES CON 5 NUMBER OF TYPES - 1 +COINS CON 1 PENNIES + CON 5 NICKLES + CON 10 DIMES + CON 25 QUARTERS + CON 50 HALF-DOLLARS + CON 100 DOLLARS +PRMPT ALF "WHAT " + ALF "AMOUN" + ALF "T <IN" + ALF " CENT" + ALF "S> DO" + ALF " YOU " + ALF "WANT " + ALF "MAX 2" + ALF "20: " + ORIG PRMPT+14 +INPT1 CON 0 +INPT2 CON 0 +* This will be our printline + ORIG PRMPT+28 +PBUF CON 0 COUNT + ALF " DLR" + ALF ": " + ALF " HLF" + ALF ": " + ALF " QTR" + ALF ": " + ALF " DMS" + ALF ": " + ALF " NCKL" + ALF ": " + ALF " PNY" + ALF ": " + END PROG |