1 /*
2 * Copyright (C) 2006 Michael Brown <mbrown@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 */
start_timer(struct retry_timer * timer)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 */
start_timer_fixed(struct retry_timer * timer,unsigned long timeout)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 */
stop_timer(struct retry_timer * timer)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 */
timer_expired(struct retry_timer * timer)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 */
retry_step(struct process * process __unused)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