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