531a1b95a1ecd097fa3fcea64320a820ea7c634c
[people/andreif/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
34 /** Default timeout value */
35 #define MIN_TIMEOUT ( TICKS_PER_SEC / 4 )
36
37 /** Limit after which the timeout will be deemed permanent */
38 #define MAX_TIMEOUT ( 10 * TICKS_PER_SEC )
39
40 /* The theoretical minimum that the algorithm in stop_timer() can
41  * adjust the timeout back down to is seven ticks, so set the minimum
42  * timeout to at least that value for the sake of consistency.
43  */
44 #if MIN_TIMEOUT < 7
45 #undef MIN_TIMEOUT
46 #define MIN_TIMEOUT 7
47 #endif
48
49 /** List of running timers */
50 static LIST_HEAD ( timers );
51
52 /**
53  * Start timer
54  *
55  * @v timer             Retry timer
56  *
57  * This starts the timer running with the current timeout value.  If
58  * stop_timer() is not called before the timer expires, the timer will
59  * be stopped and the timer's callback function will be called.
60  */
61 void start_timer ( struct retry_timer *timer ) {
62         list_add ( &timer->list, &timers );
63         timer->start = currticks();
64         if ( timer->timeout < MIN_TIMEOUT )
65                 timer->timeout = MIN_TIMEOUT;
66 }
67
68 /**
69  * Stop timer
70  *
71  * @v timer             Retry timer
72  *
73  * This stops the timer and updates the timer's timeout value.
74  */
75 void stop_timer ( struct retry_timer *timer ) {
76         unsigned long old_timeout = timer->timeout;
77         unsigned long runtime;
78
79         list_del ( &timer->list );
80         runtime = currticks() - timer->start;
81
82         /* Update timer.  Variables are:
83          *
84          *   r = round-trip time estimate (i.e. runtime)
85          *   t = timeout value (i.e. timer->timeout)
86          *   s = smoothed round-trip time
87          *
88          * By choice, we set t = 4s, i.e. allow for four times the
89          * normal round-trip time to pass before retransmitting.
90          *
91          * We want to smooth according to s := ( 7 s + r ) / 8
92          *
93          * Since we don't actually store s, this reduces to
94          * t := ( 7 t / 8 ) + ( r / 2 )
95          *
96          */
97         timer->timeout -= ( timer->timeout >> 3 );
98         timer->timeout += ( runtime >> 1 );
99         if ( timer->timeout != old_timeout ) {
100                 DBG ( "Timer updated to %dms\n",
101                       ( ( 1000 * timer->timeout ) / TICKS_PER_SEC ) );
102         }
103 }
104
105 /**
106  * Single-step the retry timer list
107  *
108  * @v process           Retry timer process
109  */
110 static void retry_step ( struct process *process ) {
111         struct retry_timer *timer;
112         struct retry_timer *tmp;
113         unsigned long now = currticks();
114         unsigned long used;
115         int fail;
116
117         list_for_each_entry_safe ( timer, tmp, &timers, list ) {
118                 used = ( now - timer->start );
119                 if ( used >= timer->timeout ) {
120                         /* Stop timer without performing RTT calculations */
121                         list_del ( &timer->list );
122                         /* Back off the timeout value */
123                         timer->timeout <<= 1;
124                         if ( ( fail = ( timer->timeout > MAX_TIMEOUT ) ) )
125                                 timer->timeout = MAX_TIMEOUT;
126                         DBG ( "Timer backed off to %dms\n",
127                               ( ( 1000 * timer->timeout ) / TICKS_PER_SEC ) );
128                         /* Call expiry callback */
129                         timer->expired ( timer, fail );
130                 }
131         }
132
133         schedule ( process );
134 }
135
136 /** Retry timer process */
137 static struct process retry_process = {
138         .step = retry_step,
139 };
140
141 /** Initialise the retry timer module */
142 static void init_retry ( void ) {
143         schedule ( &retry_process );
144 }
145
146 INIT_FN ( INIT_PROCESS, init_retry, NULL, NULL );