## pick-nextcode-fns-for-heaplimit-checks.pkg
#
# This file implements one of the nextcode compiler passes.
# For context, see the comments in
#
# src/lib/compiler/back/top/highcode/highcode-form.api#
# Checking for heap overflow on every heap allocation would be
# unacceptably slow so instead we keep a generous amount of
# free space on the heap, and only check now and then. This
# allows of small heapchunks like refcells and cons cells
# to be very fast -- basically just *edi++ = tag; *edi++ = val.
# (We do an explicit heap-limit check each time we allot
# a large or variable-length heap object.)
#
# Our task in this file is to select functions in the code at
# which to perform heap-limit checks, in such a way as to
# ensure that the checks happen often enough to guarantee that
# we never overrun the end of the heap. Specifically, we guarantee
# that no more than 1024 words of heap memory are allocated between
# calls to the heaplimit check function.
#
# We mark selected functions by changing their type from PRIVATE
# to PRIVATE_AND_NEEDS_HEAPLIMIT_CHECK. Actual generation
# of code to call the heaplimit check code is done by
#
# src/lib/compiler/back/low/main/nextcode/emit-treecode-heapcleaner-calls-g.pkg# Compiled by:
# src/lib/compiler/core.sublib### "To define is to limit."
### -- Oscar Wilde
stipulate
package ncf = nextcode_form; # nextcode_form is from src/lib/compiler/back/top/nextcode/nextcode-form.pkgherein
api Pick_Nextcode_Fns_For_Heaplimit_Checks {
#
pick_nextcode_fns_for_heaplimit_checks
:
List( ncf::Function )
->
( List( ncf::Function ),
#
ncf::Codetemp # Given a fun_id,
-> # return
{ max_possible_heapwords_allocated_before_next_heaplimit_check: Int, # max heap words allocated on any path from function to next heaplimit check, and
max_possible_nextcode_ops_run_before_next_heaplimit_check: Int # max nextcode instructions run on any path from function to next heaplimit check.
}
);
};
end;
stipulate
package coc = global_controls::compiler; # global_controls is from src/lib/compiler/toplevel/main/global-controls.pkg package ctl = global_controls; # global_controls is from src/lib/compiler/toplevel/main/global-controls.pkg package err = error_message; # error_message is from src/lib/compiler/front/basics/errormsg/error-message.pkg package ncf = nextcode_form; # nextcode_form is from src/lib/compiler/back/top/nextcode/nextcode-form.pkg package tmp = highcode_codetemp; # highcode_codetemp is from src/lib/compiler/back/top/highcode/highcode-codetemp.pkg package iht = int_hashtable; # int_hashtable is from src/lib/src/int-hashtable.pkg package mfv = compute_minimum_feedback_vertex_set_of_digraph; # compute_minimum_feedback_vertex_set_of_digraph is from src/lib/compiler/src/stuff/compute-minimum-feedback-vertex-set-of-digraph.pkgherein
# This package is referenced (only) in:
#
# src/lib/compiler/back/top/main/backend-tophalf-g.pkg #
package pick_nextcode_fns_for_heaplimit_checks
: (weak) Pick_Nextcode_Fns_For_Heaplimit_Checks
{
say = ctl::print::say;
error = err::impossible;
max_heapwords_to_allocate_between_heaplimit_checks = 1023; # Maximum number of words to allot per check. XXX SUCKO FIXME: Should be declared in some central configuration file.
# This has(?) to match skid_pad_size_in_bytes in src/lib/compiler/back/low/main/nextcode/emit-treecode-heapcleaner-calls-g.pkg # This has(?) to match 4 * ONE_K_BINARY in src/c/main/run-mythryl-code-and-runtime-eventloop.c
fun tabulate_per_function_callers_info function_list
=
# Run through the list of functions,
# building of a hashtable which maps
# fun_id (an Int) to callers_info.
#
# We return a function mapping name to kind, and also
# a function to change kind from PRIVATE to
# PRIVATE_AND_NEEDS_HEAPLIMIT_CHECK
#
{ exception LIMIT;
my hashtable: iht::Hashtable( ncf::Callers_Info )
= iht::make_hashtable { size_hint => 32, not_found_exception => LIMIT };
apply
(\\ (callers_info, fun_id, _, _, _) = iht::set hashtable (fun_id, callers_info)) # 'fun_id' here is a Variable (== Int) not a String -- a unique ID not a human-readable identifier.
function_list;
get_fun_callers_info = iht::get hashtable;
{ get_fun_callers_info,
#
change__all_calls_known__fun_to__all_calls_known_and_needs_heaplimit_check
=>
\\ fun_id
=
case (get_fun_callers_info fun_id)
#
ncf::PRIVATE_FN => iht::set hashtable (fun_id, ncf::PRIVATE_FN_WHICH_NEEDS_HEAPLIMIT_CHECK);
_ => ();
esac
};
};
fun insert_additional_heaplimit_checks_as_necessary get_fun_callers_info function_list
=
# Caller has already changed enough functions from PRIVATE
# to PRIVATE_AND_NEEDS_HEAPLIMIT_CHECK to guarantee that
# every loop through the code will include at least one heaplimit check,
# but we need a stronger guarantee: We need a heaplimit check at least
# once every 1024 words of heap allocation.
#
# Thus, our task here is to search for code execution paths potentially
# allocating more than 1024 words of heap memory and subdivide them by
# changing additional functions from PRIVATE to
# PRIVATE_AND_NEEDS_HEAPLIMIT_CHECK.
#
# As a bonus, we also return a function which gives, for each function:
#
# o max_possible_heapwords_allocated_before_next_heaplimit_check:
# The maximum number of words of heap memory which
# might be allocated without hitting a heaplimit check.
#
# o max_possible_nextcode_ops_run_before_next_heaplimit_check:
# The maximum number of nextcode instructions which
# might be executed without hitting a heaplimit check.
#
# The latter is of interest because we also (ab)use the heapcleaner's
# heaplimit-check mechanism to generate periodic events in software,
# which is to say without using (for example) the expensive kernel-based
# SIGALRM facility. For more about that see
#
# src/lib/std/src/unsafe/software-generated-periodic-events.api #
# The max_possible_heapwords_allocated_before_next_heaplimit_check values we compute are used (only) in
#
# src/lib/compiler/back/low/main/main/translate-nextcode-to-treecode-g.pkg #
# as an argument to the functions
#
# optimized_known_function_check_limit
# known_function_check_limit
# standard_function_check_limit
# from
#
# src/lib/compiler/back/low/main/nextcode/emit-treecode-heapcleaner-calls-g.pkg #
# As of 2011-07-28 the max_possible_nextcode_ops_run_before_next_heaplimit_check value we compute is used nowhere.
#
{ exception LIMIT';
stipulate
my fun_id__to__fun_body__hashtable
: iht::Hashtable( ncf::Instruction )
= iht::make_hashtable { size_hint => 32, not_found_exception => LIMIT' };
my _ =
apply (iht::set fun_id__to__fun_body__hashtable o (\\ (_, fun_id, _, _, fun_body) = (fun_id, fun_body)))
function_list;
herein
get_fun_body = iht::get fun_id__to__fun_body__hashtable;
end;
my fun_id__to__fun_info__hashtable
: iht::Hashtable { callers_info: ncf::Callers_Info,
max_possible_heapwords_allocated_before_next_heaplimit_check: Int,
max_possible_nextcode_ops_run_before_next_heaplimit_check: Int
}
= iht::make_hashtable { size_hint => 32, not_found_exception => LIMIT' };
get_fun_info = iht::get fun_id__to__fun_info__hashtable;
storelist_entry_size = 2; # Size of store-list entry. This is a two-word CONS cell logging a change to heap memory, such as a refcell write.
# Most of these heap-allocation-size numbers/formulae should be in some centralized spot, not buried here! XXX SUCKO FIXME.
# This fun computes max possible heapwords allocated
# on any path through the function body. Slight over-estimates
# are ok, but any under-estimate could result in heap corruption,
# so we err on the over-estimate side here:
#
fun max_words (result, ncf::TAIL_CALL { fn => ncf::LABEL fun_id, ... })
=>
# This is the critical case, where we
# may actually add a heaplimit check:
#
case (maxpath fun_id)
#
{ callers_info => ncf::PRIVATE_FN,
max_possible_heapwords_allocated_before_next_heaplimit_check,
max_possible_nextcode_ops_run_before_next_heaplimit_check
}
=>
if (result + max_possible_heapwords_allocated_before_next_heaplimit_check <= max_heapwords_to_allocate_between_heaplimit_checks)
result + max_possible_heapwords_allocated_before_next_heaplimit_check;
else
iht::set fun_id__to__fun_info__hashtable
( fun_id,
{ callers_info => ncf::PRIVATE_FN_WHICH_NEEDS_HEAPLIMIT_CHECK,
max_possible_heapwords_allocated_before_next_heaplimit_check,
max_possible_nextcode_ops_run_before_next_heaplimit_check
}
);
result;
fi;
_ => result;
esac;
max_words (result, ncf::TAIL_CALL _) => result;
# The remaining cases are all just about counting
# words of heap memory allocated:
#
max_words (result, ncf::DEFINE_RECORD { kind => ncf::rk::FLOAT64_BLOCK, fields, next, ... }) => max_words (result + (length(fields) * 2) + 2, next); # 64-bit issue: '*2' is floats-to-words
max_words (result, ncf::DEFINE_RECORD { kind => ncf::rk::FLOAT64_FATE_FN, fields, next, ... }) => max_words (result + (length(fields) * 2) + 2, next); # 64-bit issue: '*2' is floats-to-words
max_words (result, ncf::DEFINE_RECORD { kind => ncf::rk::VECTOR, fields, next, ... }) => max_words (result + length(fields) + 4, next);
max_words (result, ncf::DEFINE_RECORD { kind => _, fields, next, ... }) => max_words (result + length(fields) + 1, next);
#
max_words (result, ncf::GET_FIELD_I { next, ... }) => max_words (result, next);
max_words (result, ncf::GET_ADDRESS_OF_FIELD_I { next, ... }) => max_words (result, next);
#
max_words (result, ncf::JUMPTABLE { nexts, ... }) => fold_backward int::max 0 (map (\\ next = max_words (result, next)) nexts);
#
max_words (result, ncf::STORE_TO_RAM { op => ncf::p::SET_REFCELL, next, ... }) => max_words (result+storelist_entry_size, next);
max_words (result, ncf::STORE_TO_RAM { op => ncf::p::RW_VECTOR_SET, next, ... }) => max_words (result+storelist_entry_size, next);
max_words (result, ncf::STORE_TO_RAM { op => ncf::p::SET_VECSLOT_TO_BOXED_VALUE, next, ... }) => max_words (result+storelist_entry_size, next);
#
max_words (result, ncf::ARITH { op => ncf::p::ARITH { kind_and_size => ncf::p::FLOAT 64, ... }, next, ... }) => max_words (result+3, next); # Should be +0 when unboxedfloat is turned on.
max_words (result, ncf::ARITH { op => ncf::p::ARITH { kind_and_size => ncf::p::INT _, ... }, next, ... }) => max_words (result+1, next);
#
max_words (result, ncf::ARITH { op => ncf::p::SHRINK_UNT _, next, ... }) => max_words (result+1, next);
max_words (result, ncf::ARITH { op => ncf::p::SHRINK_INT _, next, ... }) => max_words (result+1, next);
max_words (result, ncf::ARITH { op => ncf::p::SHRINK_INTEGER _, next, ... }) => error "9827489 test_inf in limit";
max_words (result, ncf::ARITH r) => max_words (result, r.next);
max_words (result, ncf::PURE { op => ncf::p::PURE_ARITH { kind_and_size => ncf::p::FLOAT 64, ... }, next, ... }) => max_words (result+3, next);
max_words (result, ncf::PURE { op => ncf::p::CONVERT_FLOAT { to => ncf::p::FLOAT 64, ... }, next, ... }) => max_words (result+3, next);
#
max_words (result, ncf::PURE { op => ncf::p::WRAP_FLOAT64, args => _, next, ... }) => max_words (result+4, next);
max_words (result, ncf::PURE { op => ncf::p::IWRAP, args => _, next, ... }) => max_words (result+2, next);
max_words (result, ncf::PURE { op => ncf::p::WRAP_INT1, args => _, next, ... }) => max_words (result+2, next);
max_words (result, ncf::PURE { op => ncf::p::MAKE_ZERO_LENGTH_VECTOR, args => _, next, ... }) => max_words (result+5, next);
max_words (result, ncf::PURE { op => ncf::p::MAKE_REFCELL, args => _, next, ... }) => max_words (result+2, next);
max_words (result, ncf::PURE { op => ncf::p::MAKE_WEAK_POINTER_OR_SUSPENSION, args => _, next, ... }) => max_words (result+2, next);
max_words (result, ncf::PURE { op => ncf::p::ALLOT_RAW_RECORD tag, args =>[ncf::INT n], next, ... })
=>
max_words (result+n+(case tag THE _ => 1; NULL => 0; esac), next);
max_words (result, ncf::PURE { op => ( ncf::p::CHOP_INTEGER _
| ncf::p::STRETCH_TO_INTEGER _
| ncf::p::COPY_TO_INTEGER _
),
...
}
)
=>
error "23487978 *_inf in limit";
max_words (result, ncf::FETCH_FROM_RAM { op => ncf::p::GET_VECSLOT_NUMERIC_CONTENTS { kind_and_size=>ncf::p::FLOAT 64 }, next, ... })
=>
max_words (result+3, next);
#
max_words (result, ncf::FETCH_FROM_RAM r) => max_words (result, r.next);
max_words (result, ncf::STORE_TO_RAM r) => max_words (result, r.next);
max_words (result, ncf::PURE r) => max_words (result, r.next);
max_words (result, ncf::RAW_C_CALL r) => max_words (result, r.next);
#
max_words (result, ncf::IF_THEN_ELSE { then_next, else_next, ... })
=>
int::max ( max_words (result, then_next),
max_words (result, else_next)
);
max_words (result, ncf::DEFINE_FUNS _) => error "8932 in limit";
end
# This fun computes maximum number of nextcode instructions
# executed for any possible path through function body:
#
also
fun max_ops (result, ncf::DEFINE_RECORD r) => max_ops (result+1, r.next);
max_ops (result, ncf::GET_FIELD_I r) => max_ops (result+1, r.next);
max_ops (result, ncf::GET_ADDRESS_OF_FIELD_I r) => max_ops (result+1, r.next);
max_ops (result, ncf::STORE_TO_RAM r) => max_ops (result+1, r.next);
max_ops (result, ncf::FETCH_FROM_RAM r) => max_ops (result+1, r.next);
max_ops (result, ncf::ARITH r) => max_ops (result+1, r.next);
max_ops (result, ncf::PURE r) => max_ops (result+1, r.next);
max_ops (result, ncf::RAW_C_CALL r) => max_ops (result+1, r.next);
#
max_ops (result, ncf::JUMPTABLE { nexts, ... })
=>
fold_backward int::max 1 (map (\\ e = max_ops (result, e)) nexts); # SML/NJ had 'max_words' instead of 'max_ops' here -- a bug.
max_ops (result, ncf::IF_THEN_ELSE { then_next, else_next, ... })
=>
int::max (max_ops(result, then_next), max_ops (result, else_next)) + 1;
max_ops (result, ncf::TAIL_CALL { fn => ncf::LABEL fun_id, ... })
=>
case (maxpath fun_id)
#
{ callers_info => ncf::PRIVATE_FN,
max_possible_heapwords_allocated_before_next_heaplimit_check,
max_possible_nextcode_ops_run_before_next_heaplimit_check
}
=>
result + max_possible_nextcode_ops_run_before_next_heaplimit_check;
_ => result;
esac;
max_ops (result, ncf::TAIL_CALL _) => result;
max_ops (result, ncf::DEFINE_FUNS _) => error "8932.1 in limit";
end
also
fun maxpath fun_id
=
get_fun_info fun_id
except
LIMIT'
=
case (get_fun_callers_info fun_id)
#
ncf::PRIVATE_FN
=>
{ fun_body = get_fun_body fun_id;
max_possible_heapwords_allocated_before_next_heaplimit_check = max_words (1, fun_body); # '1' because the heap may need to be aligned.
max_possible_nextcode_ops_run_before_next_heaplimit_check = max_ops (0, fun_body);
fun_info
=
if (max_possible_heapwords_allocated_before_next_heaplimit_check
> max_heapwords_to_allocate_between_heaplimit_checks)
#
{ callers_info => ncf::PRIVATE_FN_WHICH_NEEDS_HEAPLIMIT_CHECK,
max_possible_heapwords_allocated_before_next_heaplimit_check,
max_possible_nextcode_ops_run_before_next_heaplimit_check
};
else
{ callers_info => ncf::PRIVATE_FN,
max_possible_heapwords_allocated_before_next_heaplimit_check,
max_possible_nextcode_ops_run_before_next_heaplimit_check
};
fi;
iht::set fun_id__to__fun_info__hashtable (fun_id, fun_info);
fun_info;
};
callers_info
=>
{ fun_body = get_fun_body fun_id;
fun_info
= { iht::set fun_id__to__fun_info__hashtable
( fun_id,
{ callers_info,
max_possible_heapwords_allocated_before_next_heaplimit_check => 0,
max_possible_nextcode_ops_run_before_next_heaplimit_check => 0
}
);
{ callers_info,
max_possible_heapwords_allocated_before_next_heaplimit_check => max_words (1, fun_body), # '1' because the heap may need to be aligned.
max_possible_nextcode_ops_run_before_next_heaplimit_check => max_ops (0, fun_body)
};
};
iht::set fun_id__to__fun_info__hashtable (fun_id, fun_info);
fun_info;
};
esac;
# Decide where to insert additional heaplimit checks,
# while also computing for each function
# max_possible_heapwords_allocated_before_next_heaplimit_check and max_possible_nextcode_ops_run_before_next_heaplimit_check.
#
apply
(\\ (_, fun_id, _, _, _) = { maxpath fun_id; (); })
function_list;
# Generate a new function_list with the callers_info slots
# changed from ncf::PRIVATE_FN to
# ncf::PRIVATE_FN_WHICH_NEEDS_HEAPLIMIT_CHECK
# as appropriate per our analysis:
#
function_list
=
map (\\ (_, fun_id, fun_args, fun_arg_types, fun_body)
= ((get_fun_info fun_id).callers_info, fun_id, fun_args, fun_arg_types, fun_body)
)
function_list;
( function_list,
#
\\ fun_id
=
{ max_possible_heapwords_allocated_before_next_heaplimit_check => fun_info.max_possible_heapwords_allocated_before_next_heaplimit_check,
max_possible_nextcode_ops_run_before_next_heaplimit_check => fun_info.max_possible_nextcode_ops_run_before_next_heaplimit_check
}
where
fun_info = get_fun_info fun_id;
end
);
}; # fun insert_additional_heaplimit_checks_as_necessary
fun pick_nextcode_fns_for_heaplimit_checks function_list
=
insert_additional_heaplimit_checks_as_necessary get_fun_callers_info function_list
where
# Build a hashtable mapping fun_id -> callers_info:
#
(tabulate_per_function_callers_info function_list)
->
{ get_fun_callers_info,
change__all_calls_known__fun_to__all_calls_known_and_needs_heaplimit_check
};
if *coc::printit say "Starting feedback..."; ctl::print::flush (); fi;
# Here we do three things:
# o Construct a callgraph giving, for each ncf::Function, all functions it is known to call.
# o Extract from the callgraph a minimal set of functions such that every possible codeloop includes one of our functions.
# o Mark each function in that miminal set as ncf::ALL_CALLS_KNOWN_AND_NEEDS_HEAPLIMIT_CHECK.
#
apply
change__all_calls_known__fun_to__all_calls_known_and_needs_heaplimit_check
(mfv::compute_minimum_feedback_vertex_set_of_digraph (map make_callgraph_node function_list))
where
# We're constructing the callgraph by finding
# for each function all the other functions it might
# call. Here we're given one function and we return its
# name plus a list of the names of the functions it calls:
#
fun make_callgraph_node (_, fun_id, _, _, fun_body) # 'fun_id' is a Variable (== Int) not a String -- which is to say, a unique identifier rather than a human-readable name.
=
(fun_id, edges fun_body)
where
fun edges (ncf::TAIL_CALL { fn => ncf::LABEL w, ... }) # This is the case that matters.
=>
case (get_fun_callers_info w)
#
ncf::PRIVATE_FN => [w];
_ => NIL;
esac;
edges (ncf::TAIL_CALL _) => NIL;
# The remaining cases are just routine
# dagwalk propagation of above results:
#
edges (ncf::DEFINE_RECORD { next, ... }) => edges next;
edges (ncf::GET_FIELD_I { next, ... }) => edges next;
edges (ncf::GET_ADDRESS_OF_FIELD_I { next, ... }) => edges next;
#
edges (ncf::JUMPTABLE { nexts, ... }) => list::cat (map edges nexts);
#
edges (ncf::STORE_TO_RAM r) => edges r.next;
edges (ncf::FETCH_FROM_RAM r) => edges r.next;
#
edges (ncf::ARITH r) => edges r.next;
edges (ncf::PURE r) => edges r.next;
edges (ncf::RAW_C_CALL r) => edges r.next;
edges (ncf::IF_THEN_ELSE { then_next, else_next, ... })
=>
edges then_next @ edges else_next;
#
#
edges (ncf::DEFINE_FUNS _) => error "8933 in limit";
end;
end;
end;
if *coc::printit say "Finished\n"; ctl::print::flush (); fi;
end;
# We are called (only) from:
#
# src/lib/compiler/back/top/main/backend-tophalf-g.pkg #
pick_nextcode_fns_for_heaplimit_checks # Wrapper for above which adds additional optional narration.
=
\\ function_list
=
if (not *coc::printit)
#
pick_nextcode_fns_for_heaplimit_checks function_list;
else
(pick_nextcode_fns_for_heaplimit_checks function_list)
->
info as (function_list, limits);
apply showinfo function_list
where
fun showinfo (callers_info, fun_id, _, _, _) # 'fun_id' is ncf::Codetemp naming the function.
=
{ (limits fun_id) -> { max_possible_heapwords_allocated_before_next_heaplimit_check, max_possible_nextcode_ops_run_before_next_heaplimit_check };
say (tmp::name_of_highcode_codetemp fun_id);
say "\t";
case callers_info
#
ncf::PRIVATE_FN => say "K ";
ncf::PRIVATE_FN_WHICH_NEEDS_HEAPLIMIT_CHECK => say "H ";
ncf::PUBLIC_FN => say "E ";
ncf::FATE_FN => say "C ";
#
_ => error "nolimit 323 in pick-nextcode-fns-for-heaplimit-checks.pkg";
esac;
say (int::to_string max_possible_heapwords_allocated_before_next_heaplimit_check);
say "\t";
say (int::to_string max_possible_nextcode_ops_run_before_next_heaplimit_check);
say "\n";
};
end;
info;
fi;
}; # package pick_nextcode_fns_for_heaplimit_checks
end; # stipulate