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., 51 Franklin Street, Fifth Floor, Boston, MA
17 * 02110-1301, USA.
18 *
19 * You can also choose to distribute this program under the terms of
20 * the Unmodified Binary Distribution Licence (as given in the file
21 * COPYING.UBDL), provided that you have satisfied its requirements.
22 */
23
24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
25
26 #include <stddef.h>
27 #include <ipxe/timer.h>
28 #include <ipxe/list.h>
29 #include <ipxe/process.h>
30 #include <ipxe/init.h>
31 #include <ipxe/retry.h>
32
33 /** @file
34 *
35 * Retry timers
36 *
37 * A retry timer is a binary exponential backoff timer. It can be
38 * used to build automatic retransmission into network protocols.
39 *
40 * This implementation of the timer is designed to satisfy RFC 2988
41 * and therefore be usable as a TCP retransmission timer.
42 *
43 */
44
45 /* The theoretical minimum that the algorithm in stop_timer() can
46 * adjust the timeout back down to is seven ticks, so set the minimum
47 * timeout to at least that value for the sake of consistency.
48 */
49 #define MIN_TIMEOUT 7
50
51 /** List of running timers */
52 static LIST_HEAD ( timers );
53
54 /**
55 * Start timer with a specified timeout
56 *
57 * @v timer Retry timer
58 * @v timeout Timeout, in ticks
59 *
60 * This starts the timer running with the specified timeout value. If
61 * stop_timer() is not called before the timer expires, the timer will
62 * be stopped and the timer's callback function will be called.
63 */
start_timer_fixed(struct retry_timer * timer,unsigned long timeout)64 void start_timer_fixed ( struct retry_timer *timer, unsigned long timeout ) {
65
66 /* Add to list of running timers (if applicable) */
67 if ( ! timer->running ) {
68 list_add ( &timer->list, &timers );
69 ref_get ( timer->refcnt );
70 timer->running = 1;
71 }
72
73 /* Record start time */
74 timer->start = currticks();
75
76 /* Record timeout */
77 timer->timeout = timeout;
78
79 DBGC2 ( timer, "Timer %p started at time %ld (expires at %ld)\n",
80 timer, timer->start, ( timer->start + timer->timeout ) );
81 }
82
83 /**
84 * Start timer
85 *
86 * @v timer Retry timer
87 *
88 * This starts the timer running with the current timeout value
89 * (rounded up to the minimum timeout value). If stop_timer() is not
90 * called before the timer expires, the timer will be stopped and the
91 * timer's callback function will be called.
92 */
start_timer(struct retry_timer * timer)93 void start_timer ( struct retry_timer *timer ) {
94 unsigned long timeout = timer->timeout;
95 unsigned long min;
96
97 /* Calculate minimum timeout */
98 min = ( timer->min ? timer->min : DEFAULT_MIN_TIMEOUT );
99 if ( min < MIN_TIMEOUT )
100 min = MIN_TIMEOUT;
101
102 /* Ensure timeout is at least the minimum */
103 if ( timeout < min )
104 timeout = min;
105
106 /* Start timer with this timeout */
107 start_timer_fixed ( timer, timeout );
108 }
109
110 /**
111 * Stop timer
112 *
113 * @v timer Retry timer
114 *
115 * This stops the timer and updates the timer's timeout value.
116 */
stop_timer(struct retry_timer * timer)117 void stop_timer ( struct retry_timer *timer ) {
118 unsigned long old_timeout = timer->timeout;
119 unsigned long now = currticks();
120 unsigned long runtime;
121
122 /* If timer was already stopped, do nothing */
123 if ( ! timer->running )
124 return;
125
126 list_del ( &timer->list );
127 runtime = ( now - timer->start );
128 timer->running = 0;
129 DBGC2 ( timer, "Timer %p stopped at time %ld (ran for %ld)\n",
130 timer, now, runtime );
131
132 /* Update timer. Variables are:
133 *
134 * r = round-trip time estimate (i.e. runtime)
135 * t = timeout value (i.e. timer->timeout)
136 * s = smoothed round-trip time
137 *
138 * By choice, we set t = 4s, i.e. allow for four times the
139 * normal round-trip time to pass before retransmitting.
140 *
141 * We want to smooth according to s := ( 7 s + r ) / 8
142 *
143 * Since we don't actually store s, this reduces to
144 * t := ( 7 t / 8 ) + ( r / 2 )
145 *
146 */
147 if ( timer->count ) {
148 timer->count--;
149 } else {
150 timer->timeout -= ( timer->timeout >> 3 );
151 timer->timeout += ( runtime >> 1 );
152 if ( timer->timeout != old_timeout ) {
153 DBGC ( timer, "Timer %p timeout updated to %ld\n",
154 timer, timer->timeout );
155 }
156 }
157
158 ref_put ( timer->refcnt );
159 }
160
161 /**
162 * Handle expired timer
163 *
164 * @v timer Retry timer
165 */
timer_expired(struct retry_timer * timer)166 static void timer_expired ( struct retry_timer *timer ) {
167 struct refcnt *refcnt = timer->refcnt;
168 unsigned long max = ( timer->max ? timer->max : DEFAULT_MAX_TIMEOUT );
169 int fail;
170
171 /* Stop timer without performing RTT calculations */
172 DBGC2 ( timer, "Timer %p stopped at time %ld on expiry\n",
173 timer, currticks() );
174 assert ( timer->running );
175 list_del ( &timer->list );
176 timer->running = 0;
177 timer->count++;
178
179 /* Back off the timeout value */
180 timer->timeout <<= 1;
181 if ( ( fail = ( timer->timeout > max ) ) )
182 timer->timeout = max;
183 DBGC ( timer, "Timer %p timeout backed off to %ld\n",
184 timer, timer->timeout );
185
186 /* Call expiry callback */
187 timer->expired ( timer, fail );
188 /* If refcnt is NULL, then timer may already have been freed */
189
190 ref_put ( refcnt );
191 }
192
193 /**
194 * Poll the retry timer list
195 *
196 */
retry_poll(void)197 void retry_poll ( void ) {
198 struct retry_timer *timer;
199 unsigned long now = currticks();
200 unsigned long used;
201
202 /* Process at most one timer expiry. We cannot process
203 * multiple expiries in one pass, because one timer expiring
204 * may end up triggering another timer's deletion from the
205 * list.
206 */
207 list_for_each_entry ( timer, &timers, list ) {
208 used = ( now - timer->start );
209 if ( used >= timer->timeout ) {
210 timer_expired ( timer );
211 break;
212 }
213 }
214 }
215
216 /**
217 * Single-step the retry timer list
218 *
219 * @v process Retry timer process
220 */
retry_step(struct process * process __unused)221 static void retry_step ( struct process *process __unused ) {
222 retry_poll();
223 }
224
225 /** Retry timer process */
226 PERMANENT_PROCESS ( retry_process, retry_step );
227