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