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
19FILE_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 */
48static 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 */
59void 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 */
85void 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 */
99void 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 */
146static 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 */
175static 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 */
189struct process retry_process __permanent_process = {
190	.list = LIST_HEAD_INIT ( retry_process.list ),
191	.step = retry_step,
192};
193