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
|
/*
* 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.
*/
FILE_LICENCE ( GPL2_OR_LATER );
#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
*
* @v timer Retry timer
*
* This starts the timer running with the current 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 ) {
if ( ! timer->running ) {
list_add ( &timer->list, &timers );
ref_get ( timer->refcnt );
}
timer->start = currticks();
timer->running = 1;
/* 0 means "use default timeout" */
if ( timer->min_timeout == 0 )
timer->min_timeout = DEFAULT_MIN_TIMEOUT;
/* We must never be less than MIN_TIMEOUT under any circumstances */
if ( timer->min_timeout < MIN_TIMEOUT )
timer->min_timeout = MIN_TIMEOUT;
/* Honor user-specified minimum timeout */
if ( timer->timeout < timer->min_timeout )
timer->timeout = timer->min_timeout;
DBG2 ( "Timer %p started at time %ld (expires at %ld)\n",
timer, timer->start, ( timer->start + timer->timeout ) );
}
/**
* Start timer with a specified fixed timeout
*
* @v timer Retry timer
* @v timeout Timeout, in ticks
*/
void start_timer_fixed ( struct retry_timer *timer, unsigned long timeout ) {
start_timer ( timer );
timer->timeout = timeout;
DBG2 ( "Timer %p expiry time changed to %ld\n",
timer, ( timer->start + 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;
DBG2 ( "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 ) {
DBG ( "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;
int fail;
/* Stop timer without performing RTT calculations */
DBG2 ( "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 ( timer->max_timeout == 0 ) /* 0 means "use default timeout" */
timer->max_timeout = DEFAULT_MAX_TIMEOUT;
if ( ( fail = ( timer->timeout > timer->max_timeout ) ) )
timer->timeout = timer->max_timeout;
DBG ( "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 );
|
