546 |
546 |
547 #define MILLISECOND ((unsigned long long)1000000) |
547 #define MILLISECOND ((unsigned long long)1000000) |
548 #define SECOND 1000 * MILLISECOND |
548 #define SECOND 1000 * MILLISECOND |
549 |
549 |
550 #define ULL_MAX std::numeric_limits<unsigned long long>::max() |
550 #define ULL_MAX std::numeric_limits<unsigned long long>::max() |
|
551 #define UL_MAX std::numeric_limits<uint32_t>::max() |
551 |
552 |
552 /* unsigned long long -> multiply and add : time_var += interval * multiplier */ |
553 /* unsigned long long -> multiply and add : time_var += interval * multiplier */ |
553 /* note: multiplier must be <> 0 due to overflow test */ |
554 /* note: multiplier must be <> 0 due to overflow test */ |
554 #define ULL_MUL_ADD(time_var, interval, multiplier, overflow_flag) { \ |
555 #define ULL_MUL_ADD(time_var, interval, multiplier, overflow_flag) { \ |
555 /* Test overflow on MUL by pre-condition: If (ULL_MAX / a) < b => overflow! */ \ |
556 /* Test overflow on MUL by pre-condition: If (ULL_MAX / a) < b => overflow! */ \ |
645 /***********************************************************************/ |
646 /***********************************************************************/ |
646 |
647 |
647 class calculate_common_ticktime_c: public iterator_visitor_c { |
648 class calculate_common_ticktime_c: public iterator_visitor_c { |
648 private: |
649 private: |
649 unsigned long long common_ticktime; |
650 unsigned long long common_ticktime; |
650 unsigned long long least_common_ticktime; |
651 |
651 |
652 /* Tick overflow can't happen at 2^32 because it |
|
653 * must align with task periods. |
|
654 * |
|
655 * Instead of overflowing naturaly at 2^32 |
|
656 * the overall periodicity of tasks scheduling |
|
657 * is used to find the closest overflow lesser than 2^32 |
|
658 * |
|
659 */ |
|
660 |
|
661 /* after common_period ticks, all task period align again */ |
|
662 unsigned long common_period; |
|
663 |
652 public: |
664 public: |
653 calculate_common_ticktime_c(void){ |
665 calculate_common_ticktime_c(void){ |
654 common_ticktime = 0; |
666 common_ticktime = 0; |
655 least_common_ticktime = 0; |
667 common_period = 1; /* first tick time equals single/first task period */ |
656 } |
668 } |
657 |
669 |
658 unsigned long long euclide(unsigned long long a, unsigned long long b) { |
670 unsigned long long GCM(unsigned long long a, unsigned long long b) { |
659 unsigned long long c = a % b; |
671 if(a >= b){ |
660 if (c == 0) |
672 unsigned long long c = a % b; |
661 return b; |
673 if (c == 0) |
662 else |
674 return b; |
663 return euclide(b, c); |
675 else |
|
676 return GCM(b, c); |
|
677 } else { |
|
678 return GCM(b, a); |
|
679 } |
664 } |
680 } |
665 |
681 |
666 bool update_ticktime(unsigned long long time) { |
682 bool update_ticktime(unsigned long long time) { |
667 bool overflow = false; |
|
668 |
|
669 if (common_ticktime == 0) |
683 if (common_ticktime == 0) |
670 common_ticktime = time; |
684 common_ticktime = time; |
671 else if (time > common_ticktime) |
685 else |
672 common_ticktime = euclide(time, common_ticktime); |
686 common_ticktime = GCM(time, common_ticktime); |
673 else |
687 |
674 common_ticktime = euclide(common_ticktime, time); |
688 unsigned long task_period = (time / common_ticktime); /* in tick count */ |
675 if (least_common_ticktime == 0) |
689 |
676 least_common_ticktime = time; |
690 /* New Common Period is |
677 else { |
691 * Least Common Multiple of |
678 /* Test overflow on MUL by pre-condition: If (ULL_MAX / a) < b => overflow! */ |
692 * Previous Common Period and |
679 overflow = ((ULL_MAX / least_common_ticktime) < (time / common_ticktime)); |
693 * New task period |
680 least_common_ticktime = least_common_ticktime * (time / common_ticktime); |
694 * |
681 } |
695 * LCM(a,b) = a*b/GCD(a,b) |
682 return !overflow; |
696 */ |
|
697 unsigned long long new_common_period = |
|
698 common_period * task_period / GCM(common_period, task_period); |
|
699 |
|
700 if(new_common_period >= UL_MAX){ |
|
701 return false; |
|
702 } else { |
|
703 common_period = new_common_period; |
|
704 } |
|
705 /* else if task period already divides common period, |
|
706 * keep the same common period */ |
|
707 |
|
708 return true; |
683 } |
709 } |
684 |
710 |
685 unsigned long long get_common_ticktime(void) { |
711 unsigned long long get_common_ticktime(void) { |
686 return common_ticktime; |
712 return common_ticktime; |
687 } |
713 } |
688 |
714 |
689 unsigned long get_greatest_tick_count(void) { |
715 uint32_t get_greatest_tick_count(void) { |
690 unsigned long long least_common_tick = least_common_ticktime / common_ticktime; |
716 if (common_period == 1) { |
691 if (least_common_tick >> 32) |
717 return 0; |
692 ERROR; |
718 } else { |
693 return (unsigned long)(~(((unsigned long)-1) % (unsigned long)least_common_tick) + 1); |
719 return UL_MAX - (UL_MAX % common_period); |
|
720 } |
694 } |
721 } |
695 |
722 |
696 /* TASK task_name task_initialization */ |
723 /* TASK task_name task_initialization */ |
697 //SYM_REF2(task_configuration_c, task_name, task_initialization) |
724 //SYM_REF2(task_configuration_c, task_name, task_initialization) |
698 void *visit(task_initialization_c *symbol) { |
725 void *visit(task_initialization_c *symbol) { |
699 if (symbol->interval_data_source != NULL) { |
726 if (symbol->interval_data_source != NULL) { |
700 unsigned long long time = calculate_time(symbol->interval_data_source); |
727 unsigned long long time = calculate_time(symbol->interval_data_source); |
701 if (!update_ticktime(time)) |
728 if(!update_ticktime(time)) { |
702 /* time is being stored in ns resolution (MILLISECOND #define is set to 1000000) */ |
729 /* time is being stored in ns resolution (MILLISECOND #define is set to 1000000) */ |
703 /* time is being stored in unsigned long long (ISO C99 guarantees at least 64 bits) */ |
730 /* time is being stored in unsigned long long (ISO C99 guarantees at least 64 bits) */ |
704 /* 2⁶64ns works out to around 584.5 years, assuming 365.25 days per year */ |
731 /* 2⁶64ns works out to around 584.5 years, assuming 365.25 days per year */ |
705 STAGE4_ERROR(symbol, symbol, "Internal overflow calculating least common multiple of task intervals (must be < 584 years)."); |
732 STAGE4_ERROR(symbol, symbol, "Internal overflow calculating least common multiple of task intervals (must be < 584 years)."); |
|
733 } |
706 } |
734 } |
707 return NULL; |
735 return NULL; |
708 } |
736 } |
709 }; |
737 }; |
710 |
738 |