summaryrefslogtreecommitdiff
path: root/indra/llcommon/llkeythrottle.h
blob: 7544ab1d11ffb2a3f853d1709457186689fbf828 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
/** 
 * @file llkeythrottle.h
 *
 * $LicenseInfo:firstyear=2005&license=viewergpl$
 * 
 * Copyright (c) 2005-2009, Linden Research, Inc.
 * 
 * Second Life Viewer Source Code
 * The source code in this file ("Source Code") is provided by Linden Lab
 * to you under the terms of the GNU General Public License, version 2.0
 * ("GPL"), unless you have obtained a separate licensing agreement
 * ("Other License"), formally executed by you and Linden Lab.  Terms of
 * the GPL can be found in doc/GPL-license.txt in this distribution, or
 * online at http://secondlifegrid.net/programs/open_source/licensing/gplv2
 * 
 * There are special exceptions to the terms and conditions of the GPL as
 * it is applied to this Source Code. View the full text of the exception
 * in the file doc/FLOSS-exception.txt in this software distribution, or
 * online at
 * http://secondlifegrid.net/programs/open_source/licensing/flossexception
 * 
 * By copying, modifying or distributing this software, you acknowledge
 * that you have read and understood your obligations described above,
 * and agree to abide by those obligations.
 * 
 * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
 * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
 * COMPLETENESS OR PERFORMANCE.
 * $/LicenseInfo$
 */

#ifndef LL_LLKEY_THROTTLE_H
#define LL_LLKEY_THROTTLE_H

// LLKeyThrottle keeps track of the number of action occurences with a key value
// for a type over a given time period.  If the rate set in the constructor is
// exceeed, the key is considered blocked.  The transition from unblocked to
// blocked is noted so the responsible agent can be informed.  This transition
// takes twice the look back window to clear.

#include "linden_common.h"

#include "llframetimer.h"
#include <map>


// forward declaration so LLKeyThrottleImpl can befriend it
template <class T> class LLKeyThrottle;


// Implementation utility class - use LLKeyThrottle, not this
template <class T>
class LLKeyThrottleImpl
{
	friend class LLKeyThrottle<T>;
protected:
	struct Entry {
		U32		count;
		bool	blocked;

		Entry() : count(0), blocked(false) { }
	};

	typedef std::map<T, Entry> EntryMap;

	EntryMap* prevMap;
	EntryMap* currMap;
	
	U32 countLimit;
		// maximum number of keys allowed per interval
		
	U64 intervalLength;		// each map covers this time period (usec or frame number)
	U64 startTime;			// start of the time period (usec or frame number)
		// currMap started counting at this time
		// prevMap covers the previous interval
	
	LLKeyThrottleImpl() :
		prevMap(NULL),
		currMap(NULL),
		countLimit(0),
		intervalLength(1),
		startTime(0)
	{}

	static U64 getTime()
	{
		return LLFrameTimer::getTotalTime();
	}
	static U64 getFrame()		// Return the current frame number
	{
		return (U64) LLFrameTimer::getFrameCount();
	}
};


template< class T >
class LLKeyThrottle
{
public:
	// @param realtime = FALSE for frame-based throttle, TRUE for usec
	// real-time throttle
	LLKeyThrottle(U32 limit, F32 interval, BOOL realtime = TRUE)	
		: m(* new LLKeyThrottleImpl<T>)
	{
		setParameters( limit, interval, realtime );
	}
		
	~LLKeyThrottle()
	{
		delete m.prevMap;
		delete m.currMap;
		delete &m;
	}

	enum State {
		THROTTLE_OK,			// rate not exceeded, let pass
		THROTTLE_NEWLY_BLOCKED,	// rate exceed for the first time
		THROTTLE_BLOCKED,		// rate exceed, block key
	};

	F64 getActionCount(const T& id)
	{
		U64 now = 0;
		if ( mIsRealtime )
		{
			now = LLKeyThrottleImpl<T>::getTime();
		}
		else
		{
			now = LLKeyThrottleImpl<T>::getFrame();
		}

		if (now >= (m.startTime + m.intervalLength))
		{
			if (now < (m.startTime + 2 * m.intervalLength))
			{
				// prune old data
				delete m.prevMap;
				m.prevMap = m.currMap;
				m.currMap = new typename LLKeyThrottleImpl<T>::EntryMap;

				m.startTime += m.intervalLength;
			}
			else
			{
				// lots of time has passed, all data is stale
				delete m.prevMap;
				delete m.currMap;
				m.prevMap = new typename LLKeyThrottleImpl<T>::EntryMap;
				m.currMap = new typename LLKeyThrottleImpl<T>::EntryMap;

				m.startTime = now;
			}
		}

		U32 prevCount = 0;

		typename LLKeyThrottleImpl<T>::EntryMap::const_iterator prev = m.prevMap->find(id);
		if (prev != m.prevMap->end())
		{
			prevCount = prev->second.count;
		}

		typename LLKeyThrottleImpl<T>::Entry& curr = (*m.currMap)[id];

		// curr.count is the number of keys in
		// this current 'time slice' from the beginning of it until now
		// prevCount is the number of keys in the previous
		// time slice scaled to be one full time slice back from the current 
		// (now) time.

		// compute current, windowed rate
		F64 timeInCurrent = ((F64)(now - m.startTime) / m.intervalLength);
		F64 averageCount = curr.count + prevCount * (1.0 - timeInCurrent);
		return averageCount;
	}

	// call each time the key wants use
	State noteAction(const T& id, S32 weight = 1)
	{
		U64 now = 0;
		if ( mIsRealtime )
		{
			now = LLKeyThrottleImpl<T>::getTime();
		}
		else
		{
			now = LLKeyThrottleImpl<T>::getFrame();
		}

		if (now >= (m.startTime + m.intervalLength))
		{
			if (now < (m.startTime + 2 * m.intervalLength))
			{
				// prune old data
				delete m.prevMap;
				m.prevMap = m.currMap;
				m.currMap = new typename LLKeyThrottleImpl<T>::EntryMap;

				m.startTime += m.intervalLength;
			}
			else
			{
				// lots of time has passed, all data is stale
				delete m.prevMap;
				delete m.currMap;
				m.prevMap = new typename LLKeyThrottleImpl<T>::EntryMap;
				m.currMap = new typename LLKeyThrottleImpl<T>::EntryMap;

				m.startTime = now;
			}
		}

		U32 prevCount = 0;
		bool prevBlocked = false;

		typename LLKeyThrottleImpl<T>::EntryMap::const_iterator prev = m.prevMap->find(id);
		if (prev != m.prevMap->end())
		{
			prevCount = prev->second.count;
			prevBlocked = prev->second.blocked;
		}

		typename LLKeyThrottleImpl<T>::Entry& curr = (*m.currMap)[id];

		bool wereBlocked = curr.blocked || prevBlocked;

		curr.count += weight;

		// curr.count is the number of keys in
		// this current 'time slice' from the beginning of it until now
		// prevCount is the number of keys in the previous
		// time slice scaled to be one full time slice back from the current 
		// (now) time.

		// compute current, windowed rate
		F64 timeInCurrent = ((F64)(now - m.startTime) / m.intervalLength);
		F64 averageCount = curr.count + prevCount * (1.0 - timeInCurrent);
		
		curr.blocked |= averageCount > m.countLimit;

		bool nowBlocked = curr.blocked || prevBlocked;

		if (!nowBlocked)
		{
			return THROTTLE_OK;
		}
		else if (!wereBlocked)
		{
			return THROTTLE_NEWLY_BLOCKED;
		}
		else
		{
			return THROTTLE_BLOCKED;
		}
	}

	// call to force throttle conditions for id
	void throttleAction(const T& id)
	{
		noteAction(id);
		typename LLKeyThrottleImpl<T>::Entry& curr = (*m.currMap)[id];
		curr.count = llmax(m.countLimit, curr.count);
		curr.blocked = true;
	}

	// returns true if key is blocked
	bool isThrottled(const T& id) const
	{
		if (m.currMap->empty()
			&& m.prevMap->empty())
		{
			// most of the time we'll fall in here
			return false;
		}

		// NOTE, we ignore the case where id is in the map but the map is stale.  
		// You might think that we'd stop throttling things in such a case, 
		// however it may be that a god has disabled scripts in the region or 
		// estate --> we probably want to report the state of the id when the 
		// scripting engine was paused.
		typename LLKeyThrottleImpl<T>::EntryMap::const_iterator entry = m.currMap->find(id);
		if (entry != m.currMap->end())
		{
			return entry->second.blocked;
		}
		entry = m.prevMap->find(id);
		if (entry != m.prevMap->end())
		{
			return entry->second.blocked;
		}
		return false;
	}

	// Get the throttling parameters
	void getParameters( U32 & out_limit, F32 & out_interval, BOOL & out_realtime )
	{
		out_limit = m.countLimit;
		out_interval = m.intervalLength;
		out_realtime = mIsRealtime;
	}

	// Set the throttling behavior
	void setParameters( U32 limit, F32 interval, BOOL realtime = TRUE )
	{
		// limit is the maximum number of keys
		// allowed per interval (in seconds or frames)
		mIsRealtime = realtime;
		m.countLimit = limit;
		if ( mIsRealtime )
		{
			m.intervalLength = (U64)(interval * USEC_PER_SEC);
			m.startTime = LLKeyThrottleImpl<T>::getTime();
		}
		else
		{
			m.intervalLength = (U64)interval;
			m.startTime = LLKeyThrottleImpl<T>::getFrame();
		}

		if ( m.intervalLength == 0 )
		{	// Don't allow zero intervals
			m.intervalLength = 1;
		}

		delete m.prevMap;
		m.prevMap = new typename LLKeyThrottleImpl<T>::EntryMap;
		delete m.currMap;
		m.currMap = new typename LLKeyThrottleImpl<T>::EntryMap;
	}

protected:
	LLKeyThrottleImpl<T>& m;
	BOOL	mIsRealtime;	// TRUE to be time based (default), FALSE for frame based
};

#endif