iPXE
retry.c
Go to the documentation of this file.
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  */
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  */
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 */
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  */
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  */
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  */
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  */
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 );
A process.
Definition: process.h:17
#define max(x, y)
Definition: ath.h:39
#define list_add(new, head)
Add a new entry to the head of a list.
Definition: list.h:69
static void retry_step(struct process *process __unused)
Single-step the retry timer list.
Definition: retry.c:221
struct list_head list
List of active timers.
Definition: retry.h:23
Retry timers.
#define DBGC(...)
Definition: compiler.h:505
#define min(x, y)
Definition: ath.h:34
A retry timer.
Definition: retry.h:21
iPXE timers
A reference counter.
Definition: refcnt.h:26
A timer.
Definition: timer.h:28
#define list_del(list)
Delete an entry from a list.
Definition: list.h:119
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
#define list_for_each_entry(pos, head, member)
Iterate over entries in a list.
Definition: list.h:420
#define DEFAULT_MAX_TIMEOUT
Default maximum timeout value (in ticks)
Definition: retry.h:18
Linked lists.
#define ref_get(refcnt)
Get additional reference to object.
Definition: refcnt.h:92
#define DEFAULT_MIN_TIMEOUT
Default minimum timeout value (in ticks)
Definition: retry.h:15
Processes.
static LIST_HEAD(timers)
List of running timers.
void retry_poll(void)
Poll the retry timer list.
Definition: retry.c:197
void start_timer(struct retry_timer *timer)
Start timer.
Definition: retry.c:93
void start_timer_fixed(struct retry_timer *timer, unsigned long timeout)
Start timer with a specified timeout.
Definition: retry.c:64
#define __unused
Declare a variable or data structure as unused.
Definition: compiler.h:573
void stop_timer(struct retry_timer *timer)
Stop timer.
Definition: retry.c:117
#define DBGC2(...)
Definition: compiler.h:522
static struct timer * timer
Current timer.
Definition: timer.c:35
#define MIN_TIMEOUT
Definition: retry.c:49
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
void timeout(int)
unsigned long currticks(void)
Get current system time in ticks.
Definition: timer.c:42
static void timer_expired(struct retry_timer *timer)
Handle expired timer.
Definition: retry.c:166
PERMANENT_PROCESS(retry_process, retry_step)
Retry timer process.
#define ref_put(refcnt)
Drop reference to object.
Definition: refcnt.h:106