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