From eb677c4548005b4e6423749aed8ee86386e9ba57 Mon Sep 17 00:00:00 2001 From: Samuel Hunt Date: Mon, 12 Jan 2026 16:49:02 +0000 Subject: Fixed 0/0, empty FIC and improved priority scheduling --- src/fig/FIGCarouselPriority.cpp | 538 ++++++++++++++++++++++++++-------------- src/fig/FIGCarouselPriority.h | 220 +++++++++++----- 2 files changed, 522 insertions(+), 236 deletions(-) (limited to 'src') diff --git a/src/fig/FIGCarouselPriority.cpp b/src/fig/FIGCarouselPriority.cpp index fc15c80..6bca635 100644 --- a/src/fig/FIGCarouselPriority.cpp +++ b/src/fig/FIGCarouselPriority.cpp @@ -1,6 +1,6 @@ /* - Copyright (C) 2026 - Samuel Hunt, Maxxwave Ltd. sam@maxxwave.co.uk + Copyright (C) 2024 + Matthias P. Braendli, matthias.braendli@mpb.li Implementation of a priority-based FIG carousel scheduler. */ @@ -27,6 +27,7 @@ #include #include +#include #include #include @@ -46,10 +47,10 @@ FIGEntryPriority* PriorityLevel::find_must_send() FIGEntryPriority* PriorityLevel::find_can_send() { - for (auto* entry : carousel) { - // A FIG can send if it has data (even if must_send is false) - // We always have something to send - the FIG will return 0 bytes if nothing - return entry; + // Return front of carousel if non-empty + // Any FIG can potentially send - it will return 0 bytes if nothing to send + if (!carousel.empty()) { + return carousel.front(); } return nullptr; } @@ -142,63 +143,76 @@ FIGCarouselPriority::FIGCarouselPriority( void FIGCarouselPriority::assign_figs_to_priorities() { /* - * Priority assignments: + * Priority assignments based on WorldDAB "Guidance on FIC generation + * for high service count ensembles": + * + * Priority 0 (every frame): 0/0, 0/7 - Fixed insertion (first FIB of every frame) + * Priority 1 (reset 1): 0/1, 0/2 - Core MCI (fixed share, ~50% of FIC) + * Priority 2 (reset 2): 1/1, 1/0 - Service labels + ensemble label (fixed share) + * Critical for scan completion - receivers timeout! + * Priority 3 (reset 4): 0/9 - ECC (timing critical, once/sec) + * Priority 4 (reset 8): 0/3, 0/8, 0/13 - Packet mode, component details + * Priority 5 (reset 16): 0/5, 0/10, 0/17, 0/18, 0/20 - Scaled insertion + * 1/4, 1/5, 2/0, 2/1, 2/4, 2/5 - Other labels (match label cycle) + * PTY (0/17) is NOT essential for scan, just nice-to-have + * Priority 6 (reset 32): 0/14, 0/19 - Announcements, FEC + * Priority 7 (reset 64): 0/6 - Service linking (short form) + * Priority 8 (reset 128): 0/21, 0/24 - Frequency info, OE (best effort, 2 mins) + * Priority 9 (reserved): (future/dynamic use) * - * Priority 0 (every frame): 0/0, 0/7 - Critical MCI - * Priority 1 (reset 2): 0/1, 0/2 - Core MCI (subchannel/service organisation) - * Priority 2 (reset 4): 0/3 - Service component in packet mode - * Priority 3 (reset 8): 1/1 - Programme service labels - * Priority 4 (reset 16): 0/8, 0/13 - Service component global definition, user apps - * Priority 5 (reset 32): 0/5, 0/9, 0/10, 0/17, 0/18 - Metadata - * Priority 6 (reset 64): 1/0, 1/4, 1/5, 2/0, 2/1, 2/4, 2/5 - Labels - * Priority 7 (reset 128): 0/6, 0/14, 0/19 - Service linking, FEC, announcements - * Priority 8 (reset 256): 0/21, 0/24 - Frequency info, OE services - * Priority 9 (reset 512): (reserved for future/dynamic use) + * Key insight from WorldDAB: For >20 services, service labels (1/1) are + * critical for scan completion. Receivers abort scan if labels timeout. + * PTY and other metadata should be "scaled insertion" - match label cycle, + * not compete with it. */ - // Priority 0: Critical (every frame) + // Priority 0: Fixed insertion (every frame at framephase 0) add_fig_to_priority(m_fig0_0, 0); add_fig_to_priority(m_fig0_7, 0); - // Priority 1: Core MCI + // Priority 1: Core MCI (fixed share - ~50% of FIC capacity) add_fig_to_priority(m_fig0_1, 1); add_fig_to_priority(m_fig0_2, 1); - // Priority 2: Packet mode - add_fig_to_priority(m_fig0_3, 2); + // Priority 2: Service labels (fixed share - critical for scan completion!) + // WorldDAB: "labels should get 2 FIGs per 96ms frame" + // Ensemble label should match service label rate + add_fig_to_priority(m_fig1_1, 2); // Programme service labels - PROMOTED + add_fig_to_priority(m_fig1_0, 2); // Ensemble label - PROMOTED - // Priority 3: Service labels - add_fig_to_priority(m_fig1_1, 3); + // Priority 3: ECC (timing critical - once per second) + add_fig_to_priority(m_fig0_9, 3); // Priority 4: Component details - add_fig_to_priority(m_fig0_8, 4); - add_fig_to_priority(m_fig0_13, 4); - - // Priority 5: Metadata - add_fig_to_priority(m_fig0_5, 5); - add_fig_to_priority(m_fig0_9, 5); - add_fig_to_priority(m_fig0_10, 5); - add_fig_to_priority(m_fig0_17, 5); - add_fig_to_priority(m_fig0_18, 5); + add_fig_to_priority(m_fig0_3, 4); // Packet mode + add_fig_to_priority(m_fig0_8, 4); // Service component global def + add_fig_to_priority(m_fig0_13, 4); // User applications + + // Priority 5: Scaled insertion (should match label cycle time) + // These are important but NOT critical for scan completion + add_fig_to_priority(m_fig0_5, 5); // Language + add_fig_to_priority(m_fig0_10, 5); // Date and time + add_fig_to_priority(m_fig0_17, 5); // PTY - DEMOTED (not essential for scan) + add_fig_to_priority(m_fig0_18, 5); // Announcement support add_fig_to_priority(m_fig0_20, 5); // SCI - Service Component Information + // Other labels (component, data service) - less critical than service labels + add_fig_to_priority(m_fig1_4, 5); // Component labels + add_fig_to_priority(m_fig1_5, 5); // Data service labels + add_fig_to_priority(m_fig2_0, 5); // Extended ensemble label + add_fig_to_priority(m_fig2_1, 5); // Extended service labels + add_fig_to_priority(m_fig2_4, 5); // Extended component labels + add_fig_to_priority(m_fig2_5, 5); // Extended data service labels - // Priority 6: Labels (ensemble, component, data, extended) - add_fig_to_priority(m_fig1_0, 6); - add_fig_to_priority(m_fig1_4, 6); - add_fig_to_priority(m_fig1_5, 6); - add_fig_to_priority(m_fig2_0, 6); - add_fig_to_priority(m_fig2_1, 6); - add_fig_to_priority(m_fig2_4, 6); - add_fig_to_priority(m_fig2_5, 6); + // Priority 6: Announcements and FEC + add_fig_to_priority(m_fig0_14, 6); // FEC subchannel organisation + add_fig_to_priority(m_fig0_19, 6); // Announcement switching - // Priority 7: Linking and announcements - add_fig_to_priority(m_fig0_6, 7); - add_fig_to_priority(m_fig0_14, 7); - add_fig_to_priority(m_fig0_19, 7); + // Priority 7: Service linking + add_fig_to_priority(m_fig0_6, 7); // Service linking (short form) - // Priority 8: Frequency/OE - add_fig_to_priority(m_fig0_21, 8); - add_fig_to_priority(m_fig0_24, 8); + // Priority 8: Frequency/OE (best effort - within 2 minutes) + add_fig_to_priority(m_fig0_21, 8); // Frequency information + add_fig_to_priority(m_fig0_24, 8); // OE services // Priority 9: Reserved for dynamic adjustment } @@ -220,63 +234,135 @@ void FIGCarouselPriority::add_fig_to_priority(IFIG& fig, int priority) void FIGCarouselPriority::tick_all_deadlines(int elapsed_ms) { for (auto& entry : m_all_entries) { - entry->tick_deadline(elapsed_ms); + bool start_new = entry->tick_deadline(elapsed_ms); // Check if a new cycle should start - if (!entry->must_send && entry->deadline_ms <= 0) { + if (start_new) { entry->start_new_cycle(); - entry->deadline_ms = entry->rate_ms; // Reset for next cycle } } } void FIGCarouselPriority::check_and_log_deadlines(uint64_t current_frame) { + // Log every ~6 seconds (250 frames at 24ms) if ((current_frame % 250) != 0) { return; } - std::stringstream ss; - bool any_violated = false; + std::stringstream ss_slow; // 1x-2x nominal (acceptable per WorldDAB) + std::stringstream ss_warning; // 2x-3x nominal (approaching limit) + std::stringstream ss_critical; // >3x nominal (unacceptable) + bool any_slow = false; + bool any_warning = false; + bool any_critical = false; for (auto& entry : m_all_entries) { - if (entry->deadline_violated) { - ss << " " << entry->name(); + if (entry->deadline_violated && entry->cycle_count > 0) { + // Check how severe the violation is based on average cycle time + uint64_t avg = entry->avg_cycle_time_ms(); + uint64_t required = entry->rate_ms; + + if (avg > required * 3) { + ss_critical << " " << entry->name(); + any_critical = true; + } else if (avg > required * 2) { + ss_warning << " " << entry->name(); + any_warning = true; + } else if (avg > required) { + ss_slow << " " << entry->name(); + any_slow = true; + } entry->deadline_violated = false; - any_violated = true; } } - if (any_violated) { - etiLog.level(info) << "FIGCarouselPriority: Could not respect repetition rates for FIGs:" << ss.str(); + // Log critical issues first (these violate WorldDAB guidance) + if (any_critical) { + etiLog.level(warn) << "FIGCarouselPriority: UNACCEPTABLE repetition rates (>3x nominal) for FIGs:" << ss_critical.str(); + } + + // Log warnings (approaching limit) + if (any_warning) { + etiLog.level(info) << "FIGCarouselPriority: Slow repetition rates (2x-3x nominal) for FIGs:" << ss_warning.str(); + } + + // Log slow but acceptable (only if no worse issues, to avoid log spam) + if (any_slow && !any_warning && !any_critical) { + etiLog.level(info) << "FIGCarouselPriority: Repetition rates slightly exceeded for FIGs:" << ss_slow.str(); } } -size_t FIGCarouselPriority::write_fibs(uint8_t* buf, uint64_t current_frame, bool fib3_present) +void FIGCarouselPriority::log_rate_statistics(uint64_t current_frame) { - m_rti.currentFrame = current_frame; +#if PRIORITY_RATE_STATS_DEBUG + // Log every ~10 seconds (approx 417 frames) + m_stats_log_counter++; + if (m_stats_log_counter < 417) { + return; + } + m_stats_log_counter = 0; - const int fibCount = fib3_present ? 4 : 3; - const int framephase = current_frame % 4; + etiLog.level(info) << "=== FIG Repetition Rate Statistics ==="; + etiLog.level(info) << "FIG Required Avg Min Max Cycles"; + etiLog.level(info) << "------------ -------- -------- -------- -------- --------"; -#if PRIORITY_CAROUSEL_DEBUG - if ((current_frame % 50) == 0) { // Log every 50 frames (~1.2 sec) - std::stringstream ss; - ss << "Frame " << current_frame << " (phase " << framephase << ") FIG deadlines: "; - for (auto& entry : m_all_entries) { - if (entry->must_send || entry->deadline_ms < 50) { - ss << entry->name() << "(" << entry->deadline_ms << "ms" - << (entry->must_send ? ",MUST" : "") - << (entry->deadline_violated ? ",VIOL" : "") << ") "; + for (auto& entry : m_all_entries) { + if (entry->cycle_count > 0) { + std::stringstream ss; + ss << std::left << std::setw(12) << entry->name() + << " " << std::right << std::setw(7) << entry->rate_ms << "ms" + << " " << std::setw(7) << entry->avg_cycle_time_ms() << "ms" + << " " << std::setw(7) << entry->min_cycle_time_ms << "ms" + << " " << std::setw(7) << entry->max_cycle_time_ms << "ms" + << " " << std::setw(8) << entry->cycle_count; + + // WorldDAB guidance: worst case is 3x nominal rate + // - Within spec: no marker + // - SLOW (1x-2x): exceeds nominal but well within WorldDAB limits + // - [!] (2x-3x): approaching WorldDAB worst-case limit + // - UNACCEPTABLE (>3x): violates WorldDAB guidance + uint64_t avg = entry->avg_cycle_time_ms(); + uint64_t required = entry->rate_ms; + if (avg > required * 3) { + ss << " UNACCEPTABLE"; // >3x nominal - violates WorldDAB + } else if (avg > required * 2) { + ss << " [!]"; // 2x-3x nominal - approaching limit + } else if (avg > required) { + ss << " [SLOW]"; // 1x-2x nominal - exceeds but acceptable } + + etiLog.level(info) << ss.str(); } - etiLog.level(debug) << ss.str(); + + // Reset stats for next interval + entry->reset_stats(); } + etiLog.level(info) << "======================================"; +#else + (void)current_frame; #endif +} + +size_t FIGCarouselPriority::write_fibs(uint8_t* buf, uint64_t current_frame, bool fib3_present) +{ + m_rti.currentFrame = current_frame; + + // Tick all deadline monitors (24ms per frame) + tick_all_deadlines(24); + + // Periodically log missed deadlines + check_and_log_deadlines(current_frame); + + // Periodically log rate statistics (if enabled) + log_rate_statistics(current_frame); + + const int fibCount = fib3_present ? 4 : 3; + const int framephase = current_frame % 4; for (int fib = 0; fib < fibCount; fib++) { memset(buf, 0x00, 30); - size_t figSize = fill_fib(buf, 30, framephase); + size_t figSize = fill_fib(buf, 30, fib, framephase); if (figSize < 30) { buf[figSize] = 0xff; // End marker @@ -297,145 +383,208 @@ size_t FIGCarouselPriority::write_fibs(uint8_t* buf, uint64_t current_frame, boo *(buf++) = crc & 0xFF; } - // Tick all deadline monitors AFTER sending (24ms per frame) - tick_all_deadlines(24); - - // Periodically log missed deadlines - check_and_log_deadlines(current_frame); - return 32 * fibCount; } -size_t FIGCarouselPriority::fill_fib(uint8_t* buf, size_t max_size, int framephase) +size_t FIGCarouselPriority::fill_fib(uint8_t* buf, size_t max_size, int fib_index, int framephase) { size_t written = 0; #if PRIORITY_CAROUSEL_DEBUG std::stringstream fib_log; - fib_log << "FIB fill (phase " << framephase << "): "; + fib_log << "FIB" << fib_index << " fp" << framephase << ": "; #endif - // Step 1: Priority 0 always first (FIG 0/0, 0/7) - size_t p0_written = send_priority_zero(buf, max_size, framephase); - written += p0_written; - -#if PRIORITY_CAROUSEL_DEBUG - if (p0_written > 0) { - fib_log << "P0:" << p0_written << "B "; - } -#endif + // Step 1: Priority 0 - FIG 0/0 and 0/7 (only in FIB 0 at framephase 0) + written += send_priority_zero(buf, max_size, fib_index, framephase); size_t remaining = max_size - written; uint8_t* pbuf = buf + written; - // Step 2: Must-send pass - send FIGs that are due - int attempts = 0; - const int max_attempts = NUM_PRIORITIES * 2; // Prevent infinite loop + // Track which FIGs we've tried this pass to avoid infinite loops + std::unordered_set tried_this_fib; - while (remaining > 2 && attempts < max_attempts) { - attempts++; - - // Find any priority with must_send FIGs - FIGEntryPriority* entry = nullptr; - int send_prio = -1; + // Step 2: Must-send pass - clear all urgent FIGs using cascading priority + // We iterate through priorities and try each must_send FIG. + // A FIG might return 0 bytes if it doesn't fit, so we try all of them. + + bool made_progress = true; + while (remaining > 2 && made_progress) { + made_progress = false; - // First try the selected priority - int prio = select_priority(); - if (prio >= 0) { - entry = m_priorities[prio].find_must_send(); - if (entry) { - send_prio = prio; - } + // Try each priority, starting from the selected one + int start_prio = select_priority(); + if (start_prio < 0) { + start_prio = 1; } - // If selected priority has nothing, search all priorities - if (!entry) { - for (int p = 1; p < NUM_PRIORITIES; p++) { - entry = m_priorities[p].find_must_send(); - if (entry) { - send_prio = p; - break; + // Look for must_send FIGs in priority order + for (int prio_offset = 0; prio_offset < NUM_PRIORITIES - 1 && remaining > 2; prio_offset++) { + int prio = start_prio + prio_offset; + if (prio >= NUM_PRIORITIES) { + prio = 1 + (prio - NUM_PRIORITIES); // Wrap around, skip 0 + } + + if (!m_priorities[prio].has_must_send()) { + continue; + } + + // Try all must_send FIGs in this priority + size_t carousel_size = m_priorities[prio].carousel.size(); + for (size_t fig_attempt = 0; fig_attempt < carousel_size && remaining > 2; fig_attempt++) { + FIGEntryPriority* entry = m_priorities[prio].find_must_send(); + if (!entry) { + break; // No more must_send in this priority + } + + // Skip if we've already tried this FIG this FIB + if (tried_this_fib.count(entry)) { + m_priorities[prio].move_to_back(entry); + continue; + } + tried_this_fib.insert(entry); + + size_t bytes = try_send_fig(entry, pbuf, remaining); + if (bytes > 0) { +#if PRIORITY_CAROUSEL_DEBUG + fib_log << entry->name() << ":" << bytes << "B "; +#endif + written += bytes; + remaining -= bytes; + pbuf += bytes; + m_priorities[prio].move_to_back(entry); + on_fig_sent(prio); + made_progress = true; + } else { + // FIG couldn't write (doesn't fit), move to back and try next + m_priorities[prio].move_to_back(entry); } } } + } + + // Step 3: Can-send pass - fill remaining space opportunistically + // By now, there should be no must_send FIGs (cleared in step 2) + // Any FIG can send to fill the FIB and improve repetition rates + // + // TWO-PASS APPROACH to avoid over-serving FIGs that are ahead of schedule: + // Pass 1: Only try FIGs that are past 50% of their deadline (actually need bandwidth) + // Pass 2: If still space, try any FIG that can_send (avoid wasting FIB space) + // + // This ensures bandwidth goes to FIGs that need it (like 1/1 at ~1200ms vs 960ms target) + // rather than FIGs already well ahead of schedule (like 0/9 at ~500ms vs 960ms target) + // + // NOTE: We do NOT update the priority counters here. The counter system + // is for bandwidth allocation in must_send. In can_send, we just fill space. + + tried_this_fib.clear(); + + // Pass 1: FIGs that are past 50% of their deadline (need bandwidth more urgently) + for (int prio = 1; prio < NUM_PRIORITIES && remaining > 2; prio++) { + if (m_priorities[prio].carousel.empty()) { + continue; + } - if (!entry) break; // No more must_send anywhere - - size_t bytes = try_send_fig(entry, pbuf, remaining); - if (bytes > 0) { + size_t carousel_size = m_priorities[prio].carousel.size(); + for (size_t fig_attempt = 0; fig_attempt < carousel_size && remaining > 2; fig_attempt++) { + FIGEntryPriority* entry = m_priorities[prio].find_can_send(); + if (!entry) { + break; + } + + // Skip if we've already tried this FIG this FIB + if (tried_this_fib.count(entry)) { + m_priorities[prio].move_to_back(entry); + continue; + } + + // Pass 1: Only try FIGs past 50% of their deadline + if (!entry->past_deadline_percent(50)) { + tried_this_fib.insert(entry); + m_priorities[prio].move_to_back(entry); + continue; + } + + tried_this_fib.insert(entry); + + size_t bytes = try_send_fig(entry, pbuf, remaining); + if (bytes > 0) { #if PRIORITY_CAROUSEL_DEBUG - fib_log << entry->name() << ":" << bytes << "B "; + fib_log << entry->name() << ":" << bytes << "B(urg) "; #endif - written += bytes; - remaining -= bytes; - pbuf += bytes; - m_priorities[send_prio].move_to_back(entry); - on_fig_sent(send_prio); - } else { - // FIG couldn't write (no space or no data), move to back to try others - m_priorities[send_prio].move_to_back(entry); + written += bytes; + remaining -= bytes; + pbuf += bytes; + } + m_priorities[prio].move_to_back(entry); } } - // Step 3: Can-send pass (fill remaining space opportunistically) - attempts = 0; - while (remaining > 2 && attempts < max_attempts) { - attempts++; - - int prio = select_priority(); - if (prio < 0) break; - - FIGEntryPriority* entry = m_priorities[prio].find_can_send(); + // Pass 2: Any remaining FIGs that can send (to fill unused space) + // Reset tried set - we want to try everything again, but only those we skipped + std::set tried_pass1 = tried_this_fib; + + for (int prio = 1; prio < NUM_PRIORITIES && remaining > 2; prio++) { + if (m_priorities[prio].carousel.empty()) { + continue; + } - if (!entry) { - // Try other priorities - for (int p = 1; p < NUM_PRIORITIES; p++) { - if (!m_priorities[p].carousel.empty()) { - entry = m_priorities[p].carousel.front(); - prio = p; - break; + size_t carousel_size = m_priorities[prio].carousel.size(); + for (size_t fig_attempt = 0; fig_attempt < carousel_size && remaining > 2; fig_attempt++) { + FIGEntryPriority* entry = m_priorities[prio].find_can_send(); + if (!entry) { + break; + } + + // Skip if already sent in pass 1 + if (tried_pass1.count(entry) && tried_this_fib.count(entry)) { + // Check if it was actually sent (not just tried and skipped) + // If it was skipped due to not being urgent, we can try it now + if (entry->past_deadline_percent(50)) { + // Was tried and is urgent - was actually attempted, skip + m_priorities[prio].move_to_back(entry); + continue; } } - } - - if (!entry) break; - - size_t bytes = try_send_fig(entry, pbuf, remaining); - if (bytes > 0) { + + tried_this_fib.insert(entry); + + size_t bytes = try_send_fig(entry, pbuf, remaining); + if (bytes > 0) { #if PRIORITY_CAROUSEL_DEBUG - fib_log << entry->name() << ":" << bytes << "B(opt) "; + fib_log << entry->name() << ":" << bytes << "B(fill) "; #endif - written += bytes; - remaining -= bytes; - pbuf += bytes; - m_priorities[prio].move_to_back(entry); - on_fig_sent(prio); - } else { - // FIG wrote nothing, move on + written += bytes; + remaining -= bytes; + pbuf += bytes; + } m_priorities[prio].move_to_back(entry); - break; // No more space or nothing to send } } #if PRIORITY_CAROUSEL_DEBUG fib_log << "= " << written << "/" << max_size; - etiLog.level(debug) << fib_log.str(); + etiLog.level(info) << fib_log.str(); #endif return written; } -size_t FIGCarouselPriority::send_priority_zero(uint8_t* buf, size_t max_size, int framephase) +size_t FIGCarouselPriority::send_priority_zero(uint8_t* buf, size_t max_size, int fib_index, int framephase) { size_t written = 0; - // FIG 0/0 and 0/7 only in framephase 0 (every 96ms in mode I) - if (framephase != 0) { + // EN 300 401 Clause 6.4.1: FIG 0/0 shall only be transmitted in the first + // FIB of the first CIF of each FIC (once per 96ms in Mode I) + // It must be the first FIG in that FIB + + // Only send in FIB 0 at framephase 0 + if (fib_index != 0 || framephase != 0) { return 0; } #if PRIORITY_CAROUSEL_DEBUG - etiLog.level(debug) << "send_priority_zero: framephase=0, sending 0/0 and 0/7"; + etiLog.level(info) << "send_priority_zero: FIB0, framephase=0, sending 0/0 and 0/7"; #endif // Find and send FIG 0/0 @@ -443,17 +592,18 @@ size_t FIGCarouselPriority::send_priority_zero(uint8_t* buf, size_t max_size, in if (entry->fig->figtype() == 0 && entry->fig->figextension() == 0) { FillStatus status = entry->fig->fill(buf + written, max_size - written); #if PRIORITY_CAROUSEL_DEBUG - etiLog.level(debug) << " FIG 0/0: wrote " << status.num_bytes_written + etiLog.level(info) << " FIG 0/0: wrote " << status.num_bytes_written << " bytes, complete=" << status.complete_fig_transmitted << ", deadline was " << entry->deadline_ms << "ms"; #endif if (status.num_bytes_written > 0) { written += status.num_bytes_written; - if (status.complete_fig_transmitted) { - entry->on_cycle_complete(); - } } - else { + // Mark cycle complete if the FIG says so + if (status.complete_fig_transmitted) { + entry->on_cycle_complete(status.num_bytes_written > 0); + } + if (status.num_bytes_written == 0) { throw std::logic_error("Failed to write FIG 0/0"); } break; @@ -464,23 +614,23 @@ size_t FIGCarouselPriority::send_priority_zero(uint8_t* buf, size_t max_size, in for (auto* entry : m_priorities[0].carousel) { if (entry->fig->figtype() == 0 && entry->fig->figextension() == 7) { #if PRIORITY_CAROUSEL_DEBUG - etiLog.level(debug) << " FIG 0/7: deadline=" << entry->deadline_ms + etiLog.level(info) << " FIG 0/7: deadline=" << entry->deadline_ms << "ms, must_send=" << entry->must_send << ", violated=" << entry->deadline_violated; #endif FillStatus status = entry->fig->fill(buf + written, max_size - written); #if PRIORITY_CAROUSEL_DEBUG - etiLog.level(debug) << " FIG 0/7: wrote " << status.num_bytes_written + etiLog.level(info) << " FIG 0/7: wrote " << status.num_bytes_written << " bytes, complete=" << status.complete_fig_transmitted; #endif if (status.num_bytes_written > 0) { written += status.num_bytes_written; } - // If complete (even with 0 bytes - means nothing to send), reset the cycle + // If complete, reset the cycle - pass whether data was sent if (status.complete_fig_transmitted) { - entry->on_cycle_complete(); + entry->on_cycle_complete(status.num_bytes_written > 0); #if PRIORITY_CAROUSEL_DEBUG - etiLog.level(debug) << " FIG 0/7: cycle complete, new deadline=" << entry->deadline_ms; + etiLog.level(info) << " FIG 0/7: cycle complete, new deadline=" << entry->deadline_ms; #endif } break; @@ -523,6 +673,40 @@ int FIGCarouselPriority::select_priority() return best_prio; } +int FIGCarouselPriority::cascade_find_priority(int start, bool must_send_only) +{ + // Cascade from start priority down to 8, then wrap to 1 and continue + // until we reach start again (full circle) + + // First pass: start -> NUM_PRIORITIES-1 + for (int p = start; p < NUM_PRIORITIES; p++) { + if (must_send_only) { + if (m_priorities[p].has_must_send()) { + return p; + } + } else { + if (m_priorities[p].has_can_send()) { + return p; + } + } + } + + // Second pass: 1 -> start-1 (wrap around, skip priority 0) + for (int p = 1; p < start; p++) { + if (must_send_only) { + if (m_priorities[p].has_must_send()) { + return p; + } + } else { + if (m_priorities[p].has_can_send()) { + return p; + } + } + } + + return -1; // Nothing found in any priority +} + void FIGCarouselPriority::on_fig_sent(int priority) { // Decrement all counters @@ -567,16 +751,10 @@ size_t FIGCarouselPriority::try_send_fig(FIGEntryPriority* entry, uint8_t* buf, throw std::logic_error(ss.str()); } -#if PRIORITY_CAROUSEL_DEBUG - if (written > 0) { - etiLog.level(debug) << "FIGCarouselPriority: " << entry->name() - << " wrote " << written << " bytes" - << (status.complete_fig_transmitted ? " (complete)" : " (partial)"); - } -#endif - + // Handle cycle completion + // Pass whether data was actually sent - only record stats if we transmitted something if (status.complete_fig_transmitted) { - entry->on_cycle_complete(); + entry->on_cycle_complete(written > 0); } return written; diff --git a/src/fig/FIGCarouselPriority.h b/src/fig/FIGCarouselPriority.h index 47beb35..ee4bdc3 100644 --- a/src/fig/FIGCarouselPriority.h +++ b/src/fig/FIGCarouselPriority.h @@ -1,6 +1,6 @@ /* - Copyright (C) 2026 - Samuel Hunt, Maxxwave Ltd. sam@maxxwave.co.uk + Copyright (C) 2024 + Matthias P. Braendli, matthias.braendli@mpb.li Implementation of a priority-based FIG carousel scheduler. This scheduler uses weighted priority classes with round-robin @@ -45,29 +45,6 @@ namespace FIC { -inline int rate_increment_ms(FIG_rate rate) -{ - switch (rate) { - /* All these values are multiples of 24, so that it is easier to reason - * about the behaviour when considering ETI frames of 24ms duration - * - * In large ensembles it's not always possible to respect the reptition rates, so - * the values are a bit larger than what the spec says. - * However, we observed that some receivers wouldn't always show labels (rate B), - * and that's why we reduced B rate to slightly below 1s. - * */ - case FIG_rate::FIG0_0: return 96; // Is a special case - case FIG_rate::A: return 240; - case FIG_rate::A_B: return 480; - case FIG_rate::B: return 960; - case FIG_rate::C: return 24000; - case FIG_rate::D: return 30000; - case FIG_rate::E: return 120000; - } - throw std::logic_error("Invalid FIG_rate"); -} - - // Number of priority levels (0-9) constexpr int NUM_PRIORITIES = 10; @@ -75,31 +52,70 @@ constexpr int NUM_PRIORITIES = 10; constexpr int PRIORITY_CRITICAL = 0; // Debug flag for carousel tracing - set to 1 to enable verbose logging +// Note: Uses 'info' level so output is visible without -v flag #define PRIORITY_CAROUSEL_DEBUG 0 +// Debug flag for repetition rate statistics - logs actual vs required rates +#define PRIORITY_RATE_STATS_DEBUG 0 + /* * FIGEntryPriority - Holds a FIG and its scheduling state * - * Each FIG has: - * - must_send: Set when a new cycle is due, cleared when cycle completes - * - deadline_ms: Independent countdown for monitoring repetition rate compliance + * Deadline/Cycle Model: + * --------------------- + * - deadline_ms: Countdown timer, reset ONLY when cycle completes + * - must_send: Flag indicating a cycle is in progress and not yet complete * - rate_ms: The required repetition rate from the FIG's specification + * + * Lifecycle: + * 1. Counter starts at rate_ms, must_send = true (cycle in progress) + * 2. Counter ticks down every 24ms + * 3. When FIG completes its cycle (complete_fig_transmitted = true): + * - must_send = false + * - deadline_ms = rate_ms (reset for next cycle) + * 4. When deadline_ms reaches 0: + * - If must_send == true: VIOLATION (cycle didn't complete in time) + * - If must_send == false: Start new cycle (must_send = true) + * Note: DON'T reset deadline_ms here - it continues counting to track lateness + * + * In a lightly loaded mux: + * - can_send completes cycles well before deadline + * - deadline_ms gets reset early, must_send is briefly true then false + * - When deadline_ms hits 0, must_send is false, so we just start new cycle + * + * In a heavily loaded mux: + * - must_send stays true longer as cycle takes time to complete + * - If deadline_ms hits 0 while must_send is true, violation is logged + * + * Repetition rate tracking (for debug/verification): + * - last_cycle_complete_ms: Timestamp when last cycle completed + * - cycle_count: Number of completed cycles + * - total_cycle_time_ms: Sum of all cycle times (for averaging) + * - min_cycle_time_ms / max_cycle_time_ms: Range tracking */ struct FIGEntryPriority { IFIG* fig = nullptr; // Scheduling state - bool must_send = false; // Cycle is due, not yet complete + bool must_send = false; // Cycle is in progress, not yet complete - // Deadline monitoring (independent of scheduling) - int deadline_ms = 0; // Countdown timer - int rate_ms = 0; // Reset value (from FIG_rate) + // Deadline monitoring + int deadline_ms = 0; // Countdown timer - ONLY reset on cycle complete + int rate_ms = 0; // Required repetition rate (from FIG_rate) bool deadline_violated = false; // Set if deadline expires before cycle completes // For future dynamic priority adjustment int assigned_priority = 0; // Current priority assignment int base_priority = 0; // Original priority assignment + // Repetition rate statistics (for verification) + uint64_t last_cycle_complete_ms = 0; // Timestamp of last completion + uint64_t cycle_count = 0; // Number of completed cycles + uint64_t total_cycle_time_ms = 0; // For calculating average + uint64_t min_cycle_time_ms = UINT64_MAX; + uint64_t max_cycle_time_ms = 0; + uint64_t current_time_ms = 0; // Updated each frame + std::string name() const { if (fig) { return fig->name(); @@ -107,6 +123,16 @@ struct FIGEntryPriority { return "unknown"; } + // Returns true if this FIG has used more than the given percentage of its deadline + // Used to prioritize FIGs that actually need bandwidth over those running ahead + bool past_deadline_percent(int percent) const { + // deadline_ms counts down from rate_ms + // If deadline_ms < rate_ms * (100 - percent) / 100, we're past that percent + // e.g., for 50%: if deadline_ms < rate_ms/2, we're past 50% + int threshold = rate_ms * (100 - percent) / 100; + return deadline_ms < threshold; + } + void init_deadline() { rate_ms = rate_increment_ms(fig->repetition_rate()); // FIG 0/7 has special timing - only sent at framephase 0 @@ -119,15 +145,54 @@ struct FIGEntryPriority { must_send = true; // Start with cycle due } - void tick_deadline(int elapsed_ms) { + // Called every frame (24ms). Returns true if a new cycle should start. + bool tick_deadline(int elapsed_ms) { + current_time_ms += elapsed_ms; deadline_ms -= elapsed_ms; - if (deadline_ms <= 0 && must_send && !deadline_violated) { - // Deadline expired but cycle not complete (only flag once) - deadline_violated = true; + + if (deadline_ms <= 0) { + if (must_send) { + // Deadline expired but cycle not complete - VIOLATION + if (!deadline_violated) { + deadline_violated = true; + } + // Don't start new cycle - current one isn't done yet + // Let deadline go negative to track how late we are + return false; + } else { + // Deadline expired and cycle is complete - start new cycle + // Note: We do NOT reset deadline_ms here. It was already reset + // when the cycle completed. If we're here, it means the cycle + // completed exactly on time or the counter wrapped. + // Actually, if must_send is false and deadline <= 0, the cycle + // completed and deadline was reset, then counted down again. + // So we should start a new cycle. + return true; + } } + return false; } - void on_cycle_complete() { + void on_cycle_complete(bool data_was_sent = true) { + // Track repetition rate statistics only if data was actually sent + // FIGs that return 0 bytes (nothing to send) shouldn't count as "cycles" + // as they don't consume bandwidth and skew the statistics + if (data_was_sent && last_cycle_complete_ms > 0) { + uint64_t cycle_time = current_time_ms - last_cycle_complete_ms; + // Only count if meaningful time has passed (avoid artifacts from + // multiple completions in same frame due to timing granularity) + if (cycle_time > 0) { + cycle_count++; + total_cycle_time_ms += cycle_time; + if (cycle_time < min_cycle_time_ms) min_cycle_time_ms = cycle_time; + if (cycle_time > max_cycle_time_ms) max_cycle_time_ms = cycle_time; + } + } + if (data_was_sent) { + last_cycle_complete_ms = current_time_ms; + } + + // Reset deadline for next cycle // FIG 0/7 needs extra margin for framephase timing if (fig->figtype() == 0 && fig->figextension() == 7) { deadline_ms = rate_ms + 24; @@ -141,6 +206,23 @@ struct FIGEntryPriority { void start_new_cycle() { must_send = true; + // Note: Do NOT reset deadline_ms here! + // The deadline was reset when the previous cycle completed. + // If we reset here, we lose track of timing. + } + + // Get average cycle time in ms (0 if no data) + uint64_t avg_cycle_time_ms() const { + return (cycle_count > 0) ? (total_cycle_time_ms / cycle_count) : 0; + } + + // Reset statistics (call periodically to get recent averages) + void reset_stats() { + cycle_count = 0; + total_cycle_time_ms = 0; + min_cycle_time_ms = UINT64_MAX; + max_cycle_time_ms = 0; + // Don't reset last_cycle_complete_ms - need it for next cycle measurement } }; @@ -158,19 +240,19 @@ struct PriorityLevel { int poll_reset_value = 1; std::list carousel; - // Find first FIG with must_send set that fits in available space + // Find first FIG with must_send set FIGEntryPriority* find_must_send(); - // Find first FIG that can send (has data) + // Find first FIG in carousel (for can_send - any FIG can potentially send) FIGEntryPriority* find_can_send(); - // Move entry to back of carousel (after sending) + // Move entry to back of carousel (only call after successful send!) void move_to_back(FIGEntryPriority* entry); // Check if any FIG in this priority has must_send bool has_must_send() const; - // Check if any FIG in this priority can send + // Check if carousel is non-empty bool has_can_send() const; }; @@ -178,20 +260,32 @@ struct PriorityLevel { * FIGCarouselPriority - Priority-based FIG scheduler * * Scheduling algorithm: - * 1. Priority 0 (0/0, 0/7) always sends first every frame - * 2. Other priorities are polled based on weighted counters - * 3. Within each priority, FIGs rotate via round-robin carousel - * 4. must_send FIGs are prioritised over can_send (opportunistic) - * 5. Lower priorities can get early turns if higher has nothing due + * + * 1. Priority 0 (FIG 0/0, 0/7) handled specially: + * - Only sent in FIB 0 at framephase 0 (once per 96ms) + * - FIG 0/0 must be first FIG in FIB per EN 300 401 clause 6.4.1 + * + * 2. Must-send pass (clear urgent FIGs): + * - Select priority via weighted counter system + * - If selected priority has must_send FIG, try to send it + * - If not, CASCADE: try lower priorities, then wrap to 1 and continue + * - Only move FIG to back of carousel if it actually wrote bytes + * - Continue until no must_send FIGs remain or FIB full + * + * 3. Can-send pass (fill remaining space opportunistically): + * - Same cascading logic as must-send + * - Any FIG can send even if not "due" - improves receiver acquisition + * - Continue until FIB full or all FIGs tried * * Counter mechanism: - * - All counters decrement when ANY FIG is sent + * - All counters decrement when ANY FIG successfully sends * - When a priority sends, its counter resets to poll_reset_value * - Priority with counter=0 (or lowest weighted score) is selected * - * Priority stack: - * - Tracks which priority sent most recently - * - Used for tie-breaking when multiple priorities are due + * Carousel ordering: + * - Front of carousel = least recently sent + * - FIGs only move to back when they actually write bytes + * - FIGs that write 0 bytes stay at front (get another chance) */ class FIGCarouselPriority { public: @@ -204,18 +298,25 @@ public: private: // Fill a single FIB with FIG data - size_t fill_fib(uint8_t* buf, size_t max_size, int framephase); + // fib_index: 0-3, which FIB we're filling (needed for FIG 0/0 placement) + size_t fill_fib(uint8_t* buf, size_t max_size, int fib_index, int framephase); - // Send priority 0 FIGs (0/0, 0/7) - size_t send_priority_zero(uint8_t* buf, size_t max_size, int framephase); + // Send priority 0 FIGs (0/0, 0/7) - only in FIB 0 at framephase 0 + size_t send_priority_zero(uint8_t* buf, size_t max_size, int fib_index, int framephase); - // Select which priority to poll next + // Select which priority to poll next based on weighted counters int select_priority(); - // Called after a FIG is sent from a priority + // Cascade through priorities starting from 'start', wrapping around + // Returns priority that has a FIG matching the predicate, or -1 if none + // For must_send: predicate checks must_send flag + // For can_send: predicate checks carousel non-empty + int cascade_find_priority(int start, bool must_send_only); + + // Called after a FIG successfully sends from a priority void on_fig_sent(int priority); - // Decrement all poll counters (called on each FIG send) + // Decrement all poll counters (called on each successful FIG send) void decrement_all_counters(); // Tick all deadline monitors (called each frame) @@ -224,7 +325,11 @@ private: // Check and log any deadline violations void check_and_log_deadlines(uint64_t current_frame); + // Log repetition rate statistics (when PRIORITY_RATE_STATS_DEBUG enabled) + void log_rate_statistics(uint64_t current_frame); + // Try to send a FIG, returns bytes written + // Does NOT move FIG in carousel - caller must do that only if bytes > 0 size_t try_send_fig(FIGEntryPriority* entry, uint8_t* buf, size_t max_size); // Assign FIGs to priority levels (hardcoded assignments) @@ -248,6 +353,9 @@ private: // Track missed deadlines for periodic logging std::unordered_set m_missed_deadlines; + // Frame counter for rate statistics logging interval + uint64_t m_stats_log_counter = 0; + // FIG instances FIG0_0 m_fig0_0; FIG0_1 m_fig0_1; -- cgit v1.2.3