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