From 03b900d3ed120ea919ea3eded7edbece3488cff3 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Thu, 18 Feb 2016 08:36:26 +0100 Subject: score: Replace watchdog handler implementation Use a red-black tree instead of delta chains. Close #2344. Update #2554. Update #2555. Close #2606. --- cpukit/score/src/watchdoginsert.c | 132 +++++++++++--------------------------- 1 file changed, 36 insertions(+), 96 deletions(-) (limited to 'cpukit/score/src/watchdoginsert.c') diff --git a/cpukit/score/src/watchdoginsert.c b/cpukit/score/src/watchdoginsert.c index db15f55b0d..22fc7a5f76 100644 --- a/cpukit/score/src/watchdoginsert.c +++ b/cpukit/score/src/watchdoginsert.c @@ -1,17 +1,22 @@ /** - * @file + * @file * * @brief Watchdog Insert * @ingroup ScoreWatchdog */ - + /* - * COPYRIGHT (c) 1989-1999. - * On-Line Applications Research Corporation (OAR). + * Copyright (c) 2016 embedded brains GmbH. All rights reserved. + * + * embedded brains GmbH + * Dornierstr. 4 + * 82178 Puchheim + * Germany + * * - * The license and distribution terms for this file may be - * found in the file LICENSE in this distribution or at - * http://www.rtems.org/license/LICENSE. + * The license and distribution terms for this file may be + * found in the file LICENSE in this distribution or at + * http://www.rtems.org/license/LICENSE. */ #if HAVE_CONFIG_H @@ -20,106 +25,41 @@ #include -static void _Watchdog_Insert_fixup( - Watchdog_Header *header, - Watchdog_Control *the_watchdog, - Watchdog_Interval delta, - Watchdog_Control *next_watchdog, - Watchdog_Interval delta_next -) -{ - const Chain_Node *iterator_tail; - Chain_Node *iterator_node; - - next_watchdog->delta_interval = delta_next - delta; - - iterator_node = _Chain_First( &header->Iterators ); - iterator_tail = _Chain_Immutable_tail( &header->Iterators ); - - while ( iterator_node != iterator_tail ) { - Watchdog_Iterator *iterator; - - iterator = (Watchdog_Iterator *) iterator_node; - - if ( iterator->current == &next_watchdog->Node ) { - iterator->current = &the_watchdog->Node; - } - - iterator_node = _Chain_Next( iterator_node ); - } -} - -void _Watchdog_Insert_locked( +void _Watchdog_Insert( Watchdog_Header *header, Watchdog_Control *the_watchdog, - ISR_lock_Context *lock_context + uint64_t expire ) { - if ( the_watchdog->state == WATCHDOG_INACTIVE ) { - Watchdog_Iterator iterator; - Chain_Node *current; - Chain_Node *next; - Watchdog_Interval delta; - - the_watchdog->state = WATCHDOG_BEING_INSERTED; - - _Chain_Append_unprotected( &header->Iterators, &iterator.Node ); - - delta = the_watchdog->initial; - current = _Chain_Head( &header->Watchdogs ); + RBTree_Node **link; + RBTree_Node *parent; + RBTree_Node *old_first; + RBTree_Node *new_first; - while ( - ( next = _Chain_Next( current ) ) != _Chain_Tail( &header->Watchdogs ) - ) { - Watchdog_Control *next_watchdog; - Watchdog_Interval delta_next; + _Assert( _Watchdog_Get_state( the_watchdog ) == WATCHDOG_INACTIVE ); - next_watchdog = (Watchdog_Control *) next; - delta_next = next_watchdog->delta_interval; + link = _RBTree_Root_reference( &header->Watchdogs ); + parent = NULL; + old_first = header->first; + new_first = &the_watchdog->Node.RBTree; - if ( delta < delta_next ) { - _Watchdog_Insert_fixup( - header, - the_watchdog, - delta, - next_watchdog, - delta_next - ); - break; - } + the_watchdog->expire = expire; - iterator.delta_interval = delta - delta_next; - iterator.current = next; + while ( *link != NULL ) { + Watchdog_Control *parent_watchdog; - _Watchdog_Flash( header, lock_context ); + parent = *link; + parent_watchdog = (Watchdog_Control *) parent; - if ( the_watchdog->state != WATCHDOG_BEING_INSERTED ) { - goto abort_insert; - } - - delta = iterator.delta_interval; - current = iterator.current; + if ( expire < parent_watchdog->expire ) { + link = _RBTree_Left_reference( parent ); + } else { + link = _RBTree_Right_reference( parent ); + new_first = old_first; } - - the_watchdog->delta_interval = delta; - the_watchdog->start_time = _Watchdog_Ticks_since_boot; - _Watchdog_Activate( the_watchdog ); - _Chain_Insert_unprotected( current, &the_watchdog->Node ); - -abort_insert: - - _Chain_Extract_unprotected( &iterator.Node ); } -} - -void _Watchdog_Insert( - Watchdog_Header *header, - Watchdog_Control *the_watchdog -) -{ - ISR_lock_Context lock_context; - _Watchdog_Acquire( header, &lock_context ); - _Watchdog_Insert_locked( header, the_watchdog, &lock_context ); - _Watchdog_Release( header, &lock_context ); + header->first = new_first; + _RBTree_Add_child( &the_watchdog->Node.RBTree, parent, link ); + _RBTree_Insert_color( &header->Watchdogs, &the_watchdog->Node.RBTree ); } -- cgit v1.2.3