Make start_timer() and stop_timer() robust against incorrect usage.
[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 <latch.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 /** Default timeout value */
40 #define MIN_TIMEOUT ( TICKS_PER_SEC / 4 )
41
42 /** Limit after which the timeout will be deemed permanent */
43 #define MAX_TIMEOUT ( 10 * TICKS_PER_SEC )
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 #if MIN_TIMEOUT < 7
50 #undef MIN_TIMEOUT
51 #define MIN_TIMEOUT 7
52 #endif
53
54 /** List of running timers */
55 static LIST_HEAD ( timers );
56
57 /**
58  * Start timer
59  *
60  * @v timer             Retry timer
61  *
62  * This starts the timer running with the current timeout value.  If
63  * stop_timer() is not called before the timer expires, the timer will
64  * be stopped and the timer's callback function will be called.
65  */
66 void start_timer ( struct retry_timer *timer ) {
67         if ( ! timer->start )
68                 list_add ( &timer->list, &timers );
69         timer->start = currticks();
70         if ( timer->timeout < MIN_TIMEOUT )
71                 timer->timeout = MIN_TIMEOUT;
72         DBG2 ( "Timer %p started\n", timer );
73 }
74
75 /**
76  * Stop timer
77  *
78  * @v timer             Retry timer
79  *
80  * This stops the timer and updates the timer's timeout value.
81  */
82 void stop_timer ( struct retry_timer *timer ) {
83         unsigned long old_timeout = timer->timeout;
84         unsigned long runtime;
85
86         /* If timer was already stopped, do nothing */
87         if ( ! timer->start )
88                 return;
89
90         DBG2 ( "Timer %p stopped\n", timer );
91         list_del ( &timer->list );
92         runtime = currticks() - timer->start;
93         timer->start = 0;
94
95         /* Update timer.  Variables are:
96          *
97          *   r = round-trip time estimate (i.e. runtime)
98          *   t = timeout value (i.e. timer->timeout)
99          *   s = smoothed round-trip time
100          *
101          * By choice, we set t = 4s, i.e. allow for four times the
102          * normal round-trip time to pass before retransmitting.
103          *
104          * We want to smooth according to s := ( 7 s + r ) / 8
105          *
106          * Since we don't actually store s, this reduces to
107          * t := ( 7 t / 8 ) + ( r / 2 )
108          *
109          */
110         if ( timer->count ) {
111                 timer->count--;
112         } else {
113                 timer->timeout -= ( timer->timeout >> 3 );
114                 timer->timeout += ( runtime >> 1 );
115                 if ( timer->timeout != old_timeout ) {
116                         DBG ( "Timer %p updated to %ldms\n", timer,
117                               ( ( 1000 * timer->timeout ) / TICKS_PER_SEC ) );
118                 }
119         }
120 }
121
122 /**
123  * Handle expired timer
124  *
125  * @v timer             Retry timer
126  */
127 static void timer_expired ( struct retry_timer *timer ) {
128         int fail;
129
130         /* Stop timer without performing RTT calculations */
131         DBG2 ( "Timer %p stopped on expiry\n", timer );
132         list_del ( &timer->list );
133         timer->start = 0;
134         timer->count++;
135
136         /* Back off the timeout value */
137         timer->timeout <<= 1;
138         if ( ( fail = ( timer->timeout > MAX_TIMEOUT ) ) )
139                 timer->timeout = MAX_TIMEOUT;
140         DBG ( "Timer %p backed off to %ldms\n", timer,
141               ( ( 1000 * timer->timeout ) / TICKS_PER_SEC ) );
142
143         /* Call expiry callback */
144         timer->expired ( timer, fail ); 
145 }
146
147 /**
148  * Single-step the retry timer list
149  *
150  * @v process           Retry timer process
151  */
152 static void retry_step ( struct process *process ) {
153         struct retry_timer *timer;
154         struct retry_timer *tmp;
155         unsigned long now = currticks();
156         unsigned long used;
157
158         list_for_each_entry_safe ( timer, tmp, &timers, list ) {
159                 used = ( now - timer->start );
160                 if ( used >= timer->timeout )
161                         timer_expired ( timer );
162         }
163
164         schedule ( process );
165 }
166
167 /** Retry timer process */
168 static struct process retry_process = {
169         .step = retry_step,
170 };
171
172 /** Initialise the retry timer module */
173 static void init_retry ( void ) {
174         schedule ( &retry_process );
175 }
176
177 INIT_FN ( INIT_PROCESS, init_retry, NULL, NULL );