From 0f1d226c5fc94d4d28665b9c1f3ffc2bac11cdfc Mon Sep 17 00:00:00 2001 From: imarom Date: Wed, 14 Sep 2016 13:31:39 +0300 Subject: draft: new split algorithm --- src/stateless/cp/trex_stream_vm.h | 238 ++++++++++++++++++---------------- src/stateless/cp/trex_vm_splitter.cpp | 127 +++++------------- src/stateless/cp/trex_vm_splitter.h | 4 +- 3 files changed, 163 insertions(+), 206 deletions(-) (limited to 'src/stateless') diff --git a/src/stateless/cp/trex_stream_vm.h b/src/stateless/cp/trex_stream_vm.h index 5e3665c6..ab2a4fa8 100644 --- a/src/stateless/cp/trex_stream_vm.h +++ b/src/stateless/cp/trex_stream_vm.h @@ -30,7 +30,27 @@ limitations under the License. #include "pal_utl.h" #include "mbuf.h" +static inline +uint64_t inc_mod(uint64_t a, uint64_t b, uint64_t c, uint64_t step) { + /* check if we have enough left for simple inc */ + uint64_t left = b - c; + if (step <= left) { + return (c + step); + } else { + return (a + (step - left - 1)); // restart consumes also 1 + } +} +static inline +uint64_t dec_mod(uint64_t a, uint64_t b, uint64_t c, uint64_t step) { + /* check if we have enough left for simple dec */ + uint64_t left = c - a; + if (step <= left) { + return (c - step); + } else { + return (b - (step - left - 1)); // restart consumes also 1 + } +} //https://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/ @@ -211,20 +231,12 @@ public: inline void run_inc(uint8_t * flow_var) { uint8_t *p = (flow_var + m_flow_offset); - if (*p == m_max_val) { - *p = m_min_val; - } else { - *p = *p + 1; - } + *p = inc_mod(m_min_val, m_max_val, *p, 1); } inline void run_dec(uint8_t * flow_var) { uint8_t *p = (flow_var + m_flow_offset); - if (*p == m_min_val) { - *p = m_max_val; - } else { - *p = *p - 1; - } + *p = dec_mod(m_min_val, m_max_val, *p, 1); } inline void run_rand(uint8_t * flow_var,uint32_t *per_thread_random) { @@ -245,20 +257,12 @@ public: inline void run_inc(uint8_t * flow_var) { uint16_t *p = (uint16_t *)(flow_var + m_flow_offset); - if (*p == m_max_val) { - *p = m_min_val; - } else { - *p = *p + 1; - } + *p = inc_mod(m_min_val, m_max_val, *p, 1); } inline void run_dec(uint8_t * flow_var) { uint16_t *p = (uint16_t *)(flow_var + m_flow_offset); - if (*p == m_min_val) { - *p = m_max_val; - } else { - *p = *p - 1; - } + *p = dec_mod(m_min_val, m_max_val, *p, 1); } inline void run_rand(uint8_t * flow_var,uint32_t *per_thread_random) { @@ -280,20 +284,12 @@ public: inline void run_inc(uint8_t * flow_var) { uint32_t *p = (uint32_t *)(flow_var + m_flow_offset); - if (*p == m_max_val) { - *p = m_min_val; - } else { - *p = *p + 1; - } + *p = inc_mod(m_min_val, m_max_val, *p, 1); } inline void run_dec(uint8_t * flow_var) { uint32_t *p = (uint32_t *)(flow_var + m_flow_offset); - if (*p == m_min_val) { - *p = m_max_val; - } else { - *p = *p - 1; - } + *p = dec_mod(m_min_val, m_max_val, *p, 1); } inline void run_rand(uint8_t * flow_var,uint32_t *per_thread_random) { @@ -313,20 +309,12 @@ public: inline void run_inc(uint8_t * flow_var) { uint64_t *p = (uint64_t *)(flow_var + m_flow_offset); - if (*p == m_max_val) { - *p = m_min_val; - } else { - *p = *p + 1; - } + *p = inc_mod(m_min_val, m_max_val, *p, 1); } inline void run_dec(uint8_t * flow_var) { uint64_t *p = (uint64_t *)(flow_var + m_flow_offset); - if (*p == m_min_val) { - *p = m_max_val; - } else { - *p = *p - 1; - } + *p = dec_mod(m_min_val, m_max_val, *p, 1); } inline void run_rand(uint8_t * flow_var,uint32_t *per_thread_random) { @@ -355,20 +343,12 @@ public: inline void run_inc(uint8_t * flow_var) { uint8_t *p = (flow_var + m_flow_offset); - if (*p > (m_max_val-m_step)) { - *p = m_min_val; - } else { - *p = *p + m_step; - } + *p = inc_mod(m_min_val, m_max_val, *p, m_step); } inline void run_dec(uint8_t * flow_var) { uint8_t *p = (flow_var + m_flow_offset); - if (*p < (m_min_val+m_step)) { - *p = m_max_val; - } else { - *p = *p - m_step; - } + *p = dec_mod(m_min_val, m_max_val, *p, m_step); } } __attribute__((packed)) ; @@ -385,20 +365,12 @@ public: inline void run_inc(uint8_t * flow_var) { uint16_t *p = (uint16_t *)(flow_var + m_flow_offset); - if (*p > (m_max_val-m_step)) { - *p = m_min_val; - } else { - *p = *p + m_step; - } + *p = inc_mod(m_min_val, m_max_val, *p, m_step); } inline void run_dec(uint8_t * flow_var) { uint16_t *p = (uint16_t *)(flow_var + m_flow_offset); - if (*p < (m_min_val+m_step)) { - *p = m_max_val; - } else { - *p = *p - m_step; - } + *p = dec_mod(m_min_val, m_max_val, *p, m_step); } } __attribute__((packed)) ; @@ -414,20 +386,12 @@ public: inline void run_inc(uint8_t * flow_var) { uint32_t *p = (uint32_t *)(flow_var + m_flow_offset); - if (*p > (m_max_val-m_step)) { - *p = m_min_val; - } else { - *p = *p + m_step; - } + *p = inc_mod(m_min_val, m_max_val, *p, m_step); } inline void run_dec(uint8_t * flow_var) { uint32_t *p = (uint32_t *)(flow_var + m_flow_offset); - if (*p < (m_min_val+m_step)) { - *p = m_max_val; - } else { - *p = *p - m_step; - } + *p = dec_mod(m_min_val, m_max_val, *p, m_step); } } __attribute__((packed)) ; @@ -443,20 +407,12 @@ public: inline void run_inc(uint8_t * flow_var) { uint64_t *p = (uint64_t *)(flow_var + m_flow_offset); - if (*p > (m_max_val-m_step) ) { - *p = m_min_val; - } else { - *p = *p + m_step; - } + *p = inc_mod(m_min_val, m_max_val, *p, m_step); } inline void run_dec(uint8_t * flow_var) { uint64_t *p = (uint64_t *)(flow_var + m_flow_offset); - if (*p < m_min_val+m_step) { - *p = m_max_val; - } else { - *p = *p - m_step; - } + *p = dec_mod(m_min_val, m_max_val, *p, m_step); } @@ -981,10 +937,11 @@ public: virtual StreamVmInstruction * clone() = 0; - /* by default an instruction is not splitable */ - virtual bool is_splitable() const { - return false; + bool is_var_instruction() const { + instruction_type_t type = get_instruction_type(); + return ( (type == itFLOW_MAN) || (type == itFLOW_CLIENT) ); } + /* nothing to init */ virtual uint8_t bss_init_value(uint8_t *p){ return (0); @@ -1007,19 +964,41 @@ public: } - const std::string & get_var_name() { + const std::string & get_var_name() const { return m_var_name; } - virtual bool is_splitable() const { - return true; - } + virtual bool need_split() const = 0; /** * what is the split range for this var * */ - virtual uint64_t get_splitable_range() const = 0; + virtual uint64_t get_range() const = 0; + + /** + * allows a var instruction to be updated + * for multicore (split) + * + */ + virtual void update(uint64_t phase, uint64_t step_multiplier) = 0; + + uint64_t peek_next(uint64_t skip = 1) const { + return peek(skip, true); + } + + uint64_t peek_prev(uint64_t skip = 1) const { + return peek(skip, false); + } + + +protected: + /** + * a var instruction should be able to peek back/forward with + * any number of steps in the series + * + */ + virtual uint64_t peek(int skip = 1, bool forward = true) const = 0; public: @@ -1064,12 +1043,12 @@ public: return ( StreamVmInstruction::itFLOW_MAN); } - virtual bool is_valid_for_split() const { - return (m_step==1?true:false); + virtual bool need_split() const { + /* random does not need split */ + return (m_op != FLOW_VAR_OP_RANDOM); } - - virtual uint64_t get_splitable_range() const { + virtual uint64_t get_range() const { return (m_max_value - m_min_value + 1); } @@ -1094,19 +1073,7 @@ public: * */ uint64_t get_bss_init_value() const { - uint64_t init = m_init_value; - - switch (m_op) { - case FLOW_VAR_OP_INC: - return (init == m_min_value ? m_max_value : (init - 1)); - - case FLOW_VAR_OP_DEC: - return (init == m_max_value ? m_min_value : (init + 1)); - - default: - return init; - } - + return peek_prev(); } StreamVmInstructionFlowMan(const std::string &var_name, @@ -1117,15 +1084,27 @@ public: uint64_t max_value, uint64_t step=1) : StreamVmInstructionVar(var_name) { - m_op = op; - m_size_bytes = size; - m_init_value = init_value; - m_min_value = min_value; - m_max_value = max_value; - m_step = step; + m_op = op; + m_size_bytes = size; + m_init_value = init_value; + m_min_value = min_value; + m_max_value = max_value; + m_step = step % get_range(); // support step overflow by modulu + + assert(m_init_value >= m_min_value); + assert(m_init_value <= m_max_value); + } + virtual void update(uint64_t phase, uint64_t step_multiplier) { + /* update the init value to be with a phase */ + m_init_value = peek_next(phase); + m_step = (m_step * step_multiplier) % get_range(); + + assert(m_init_value >= m_min_value); + assert(m_init_value <= m_max_value); } + virtual void Dump(FILE *fd); void sanity_check(uint32_t ins_id,StreamVm *lp); @@ -1140,6 +1119,29 @@ public: m_step); } + +protected: + + /* fetch the next value in the variable (used for core phase and etc.) */ + virtual uint64_t peek(int skip = 1, bool forward = true) const { + + if (m_op == FLOW_VAR_OP_RANDOM) { + return m_init_value; + } + + assert( (m_op == FLOW_VAR_OP_INC) || (m_op == FLOW_VAR_OP_DEC) ); + bool add = ( (m_op == FLOW_VAR_OP_INC) ? forward : !forward ); + + uint64_t next_step = (m_step * skip) % get_range(); + + if (add) { + return inc_mod(m_min_value, m_max_value, m_init_value, next_step); + } else { + return dec_mod(m_min_value, m_max_value, m_init_value, next_step); + } + } + + private: void sanity_check_valid_size(uint32_t ins_id,StreamVm *lp); void sanity_check_valid_opt(uint32_t ins_id,StreamVm *lp); @@ -1313,6 +1315,9 @@ public: return ( StreamVmInstruction::itFLOW_CLIENT); } + virtual bool need_split() const { + return true; + } StreamVmInstructionFlowClient(const std::string &var_name, uint32_t client_min_value, @@ -1347,7 +1352,7 @@ public: return (m_port_max - m_port_min + 1); } - virtual uint64_t get_splitable_range() const { + virtual uint64_t get_range() const { return get_ip_range(); } @@ -1370,6 +1375,15 @@ public: m_flags); } + virtual void update(uint64_t phase, uint64_t step_multiplier) { + } + + +protected: + virtual uint64_t peek(int skip = 1, bool forward = true) const { + return (0); + } + public: uint32_t m_client_min; // min ip diff --git a/src/stateless/cp/trex_vm_splitter.cpp b/src/stateless/cp/trex_vm_splitter.cpp index 5069c535..1ff43829 100644 --- a/src/stateless/cp/trex_vm_splitter.cpp +++ b/src/stateless/cp/trex_vm_splitter.cpp @@ -89,27 +89,28 @@ TrexVmSplitter::split(TrexStream *stream, std::vector core_streams bool TrexVmSplitter::split_internal() { - const StreamVmInstructionVar *split_instr = m_stream->m_vm.get_split_instruction(); + duplicate_vm(); + + /* search for splitable instructions */ + for (StreamVmInstruction *instr : m_stream->m_vm.get_instruction_list()) { + if (!instr->is_var_instruction()) { + continue; + } + + split_flow_var( (const StreamVmInstructionVar *)instr ); - /* if no split instruction was specified - fall back*/ - if (split_instr == NULL) { - return false; } - if (split_instr->get_instruction_type() == StreamVmInstruction::itFLOW_MAN) { - return split_by_flow_var( (const StreamVmInstructionFlowMan *)split_instr ); - } else if (split_instr->get_instruction_type() == StreamVmInstruction::itFLOW_CLIENT) { - return split_by_flow_client_var( (const StreamVmInstructionFlowClient *)split_instr ); + /* done - now compile for all cores */ + compile_vm(); - } else { - throw TrexException("VM splitter : cannot split by instruction which is not flow var or flow client var"); - } + return true; } /** - * split VM by flow var + * split a flow var instruction * * @author imarom (20-Dec-15) * @@ -117,98 +118,29 @@ TrexVmSplitter::split_internal() { * * @return bool */ -bool -TrexVmSplitter::split_by_flow_var(const StreamVmInstructionFlowMan *instr) { - /* no point in splitting random */ - if (instr->m_op == StreamVmInstructionFlowMan::FLOW_VAR_OP_RANDOM) { - return false; - } - - /* if the range is too small - it is unsplitable */ - if (instr->get_splitable_range() < m_dp_core_count) { - return false; - } - - /* split only step of 1 */ - if (!instr->is_valid_for_split() ){ - return false; +void +TrexVmSplitter::split_flow_var(const StreamVmInstructionVar *src) { + /* a var might not need split (random) */ + if (!src->need_split()) { + return; } - /* we need to split - duplicate VM now */ - duplicate_vm(); - - /* calculate range splitting */ - uint64_t range = instr->get_splitable_range(); - - uint64_t range_part = range / m_dp_core_count; - uint64_t leftover = range % m_dp_core_count; - - /* first core handles a bit more */ - uint64_t start = instr->m_min_value; - uint64_t end = start + range_part + leftover - 1; - - /* do work */ + int core_id = 0; for (TrexStream *core_stream : *m_core_streams) { - /* get the per-core instruction to split */ - StreamVmInstructionFlowMan *per_core_instr = (StreamVmInstructionFlowMan *)core_stream->m_vm.get_split_instruction(); - - per_core_instr->m_min_value = start; - per_core_instr->m_max_value = end; + StreamVmInstructionVar *dst = core_stream->m_vm.lookup_var_by_name(src->get_var_name()); + assert(dst); - /* after split this has no meaning - choose it as we see fit */ - per_core_instr->m_init_value = (per_core_instr->m_op == StreamVmInstructionFlowMan::FLOW_VAR_OP_DEC ? end : start); + /* for each core we need to give a phase and multiply the step frequency */ + dst->update(core_id, m_dp_core_count); - core_stream->vm_compile(); - - start = end + 1; - end = start + range_part - 1; + core_id++; } - return true; } -bool -TrexVmSplitter::split_by_flow_client_var(const StreamVmInstructionFlowClient *instr) { - - /* if the range is too small - it is unsplitable */ - if (instr->get_ip_range() < m_dp_core_count) { - return false; - } - - /* we need to split - duplicate VM now */ - duplicate_vm(); - - /* calculate range splitting */ - uint64_t range = instr->get_ip_range(); - - uint64_t range_part = range / m_dp_core_count; - uint64_t leftover = range % m_dp_core_count; - - /* first core handles a bit more */ - uint64_t start = instr->m_client_min; - uint64_t end = start + range_part + leftover - 1; - - - /* do work */ - for (TrexStream *core_stream : *m_core_streams) { - - /* get the per-core instruction to split */ - StreamVmInstructionFlowClient *per_core_instr = (StreamVmInstructionFlowClient *)core_stream->m_vm.get_split_instruction(); - - per_core_instr->m_client_min = start; - per_core_instr->m_client_max = end; - - core_stream->vm_compile(); - - start = end + 1; - end = start + range_part - 1; - } - - return true; -} /** * duplicate the VM instructions @@ -222,3 +154,14 @@ TrexVmSplitter::duplicate_vm() { } } +/** + * now compile the updated VM + */ +void +TrexVmSplitter::compile_vm() { + /* for each core - duplicate the instructions */ + for (TrexStream *core_stream : *m_core_streams) { + core_stream->vm_compile(); + } +} + diff --git a/src/stateless/cp/trex_vm_splitter.h b/src/stateless/cp/trex_vm_splitter.h index dac71c21..d24cd2cc 100644 --- a/src/stateless/cp/trex_vm_splitter.h +++ b/src/stateless/cp/trex_vm_splitter.h @@ -46,10 +46,10 @@ public: private: bool split_internal(); - bool split_by_flow_var(const StreamVmInstructionFlowMan *instr); - bool split_by_flow_client_var(const StreamVmInstructionFlowClient *instr); + void split_flow_var(const StreamVmInstructionVar *instr); void duplicate_vm(); + void compile_vm(); TrexStream *m_stream; std::vector *m_core_streams; -- cgit 1.2.3-korg