1 /* 2 * Copyright (C) 2006 Michael Brown <mbrown (at) fensystems.co.uk>. 3 * 4 * This program is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU General Public License as 6 * published by the Free Software Foundation; either version 2 of the 7 * License, or any later version. 8 * 9 * This program is distributed in the hope that it will be useful, but 10 * WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 * General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write to the Free Software 16 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 17 */ 18 19 FILE_LICENCE ( GPL2_OR_LATER ); 20 21 #include <stddef.h> 22 #include <gpxe/timer.h> 23 #include <gpxe/list.h> 24 #include <gpxe/process.h> 25 #include <gpxe/init.h> 26 #include <gpxe/retry.h> 27 28 /** @file 29 * 30 * Retry timers 31 * 32 * A retry timer is a binary exponential backoff timer. It can be 33 * used to build automatic retransmission into network protocols. 34 * 35 * This implementation of the timer is designed to satisfy RFC 2988 36 * and therefore be usable as a TCP retransmission timer. 37 * 38 * 39 */ 40 41 /* The theoretical minimum that the algorithm in stop_timer() can 42 * adjust the timeout back down to is seven ticks, so set the minimum 43 * timeout to at least that value for the sake of consistency. 44 */ 45 #define MIN_TIMEOUT 7 46 47 /** List of running timers */ 48 static LIST_HEAD ( timers ); 49 50 /** 51 * Start timer 52 * 53 * @v timer Retry timer 54 * 55 * This starts the timer running with the current timeout value. If 56 * stop_timer() is not called before the timer expires, the timer will 57 * be stopped and the timer's callback function will be called. 58 */ 59 void start_timer ( struct retry_timer *timer ) { 60 if ( ! timer->running ) 61 list_add ( &timer->list, &timers ); 62 timer->start = currticks(); 63 timer->running = 1; 64 65 /* 0 means "use default timeout" */ 66 if ( timer->min_timeout == 0 ) 67 timer->min_timeout = DEFAULT_MIN_TIMEOUT; 68 /* We must never be less than MIN_TIMEOUT under any circumstances */ 69 if ( timer->min_timeout < MIN_TIMEOUT ) 70 timer->min_timeout = MIN_TIMEOUT; 71 /* Honor user-specified minimum timeout */ 72 if ( timer->timeout < timer->min_timeout ) 73 timer->timeout = timer->min_timeout; 74 75 DBG2 ( "Timer %p started at time %ld (expires at %ld)\n", 76 timer, timer->start, ( timer->start + timer->timeout ) ); 77 } 78 79 /** 80 * Start timer with a specified fixed timeout 81 * 82 * @v timer Retry timer 83 * @v timeout Timeout, in ticks 84 */ 85 void start_timer_fixed ( struct retry_timer *timer, unsigned long timeout ) { 86 start_timer ( timer ); 87 timer->timeout = timeout; 88 DBG2 ( "Timer %p expiry time changed to %ld\n", 89 timer, ( timer->start + timer->timeout ) ); 90 } 91 92 /** 93 * Stop timer 94 * 95 * @v timer Retry timer 96 * 97 * This stops the timer and updates the timer's timeout value. 98 */ 99 void stop_timer ( struct retry_timer *timer ) { 100 unsigned long old_timeout = timer->timeout; 101 unsigned long now = currticks(); 102 unsigned long runtime; 103 104 /* If timer was already stopped, do nothing */ 105 if ( ! timer->running ) 106 return; 107 108 list_del ( &timer->list ); 109 runtime = ( now - timer->start ); 110 timer->running = 0; 111 DBG2 ( "Timer %p stopped at time %ld (ran for %ld)\n", 112 timer, now, runtime ); 113 114 /* Update timer. Variables are: 115 * 116 * r = round-trip time estimate (i.e. runtime) 117 * t = timeout value (i.e. timer->timeout) 118 * s = smoothed round-trip time 119 * 120 * By choice, we set t = 4s, i.e. allow for four times the 121 * normal round-trip time to pass before retransmitting. 122 * 123 * We want to smooth according to s := ( 7 s + r ) / 8 124 * 125 * Since we don't actually store s, this reduces to 126 * t := ( 7 t / 8 ) + ( r / 2 ) 127 * 128 */ 129 if ( timer->count ) { 130 timer->count--; 131 } else { 132 timer->timeout -= ( timer->timeout >> 3 ); 133 timer->timeout += ( runtime >> 1 ); 134 if ( timer->timeout != old_timeout ) { 135 DBG ( "Timer %p timeout updated to %ld\n", 136 timer, timer->timeout ); 137 } 138 } 139 } 140 141 /** 142 * Handle expired timer 143 * 144 * @v timer Retry timer 145 */ 146 static void timer_expired ( struct retry_timer *timer ) { 147 int fail; 148 149 /* Stop timer without performing RTT calculations */ 150 DBG2 ( "Timer %p stopped at time %ld on expiry\n", 151 timer, currticks() ); 152 assert ( timer->running ); 153 list_del ( &timer->list ); 154 timer->running = 0; 155 timer->count++; 156 157 /* Back off the timeout value */ 158 timer->timeout <<= 1; 159 if ( timer->max_timeout == 0 ) /* 0 means "use default timeout" */ 160 timer->max_timeout = DEFAULT_MAX_TIMEOUT; 161 if ( ( fail = ( timer->timeout > timer->max_timeout ) ) ) 162 timer->timeout = timer->max_timeout; 163 DBG ( "Timer %p timeout backed off to %ld\n", 164 timer, timer->timeout ); 165 166 /* Call expiry callback */ 167 timer->expired ( timer, fail ); 168 } 169 170 /** 171 * Single-step the retry timer list 172 * 173 * @v process Retry timer process 174 */ 175 static void retry_step ( struct process *process __unused ) { 176 struct retry_timer *timer; 177 struct retry_timer *tmp; 178 unsigned long now = currticks(); 179 unsigned long used; 180 181 list_for_each_entry_safe ( timer, tmp, &timers, list ) { 182 used = ( now - timer->start ); 183 if ( used >= timer->timeout ) 184 timer_expired ( timer ); 185 } 186 } 187 188 /** Retry timer process */ 189 struct process retry_process __permanent_process = { 190 .list = LIST_HEAD_INIT ( retry_process.list ), 191 .step = retry_step, 192 }; 193
