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
|
/**
* @file llkeythrottle.h
* @brief LLKeyThrottle class definition
*
* Copyright (c) 2005-$CurrentYear$, Linden Research, Inc.
* $License$
*/
#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>
// Implementation utility class - use LLKeyThrottle, not this
template <class T>
class LLKeyThrottleImpl
{
public:
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 interval_usec;
// each map covers this time period
U64 start_usec;
// currMap started counting at this time
// prevMap covers the previous interval
LLKeyThrottleImpl() : prevMap(0), currMap(0) { }
static U64 getTime()
{
return LLFrameTimer::getTotalTime();
}
};
template< class T >
class LLKeyThrottle
{
public:
LLKeyThrottle(U32 limit, F32 interval)
: m(* new LLKeyThrottleImpl<T>)
{
// limit is the maximum number of keys
// allowed per interval (in seconds)
m.countLimit = limit;
m.interval_usec = (U64)(interval * USEC_PER_SEC);
m.start_usec = LLKeyThrottleImpl<T>::getTime();
m.prevMap = new typename LLKeyThrottleImpl<T>::EntryMap;
m.currMap = new typename LLKeyThrottleImpl<T>::EntryMap;
}
~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
};
// call each time the key wants use
State noteAction(const T& id, S32 weight = 1)
{
U64 now = LLKeyThrottleImpl<T>::getTime();
if (now >= (m.start_usec + m.interval_usec))
{
if (now < (m.start_usec + 2 * m.interval_usec))
{
// prune old data
delete m.prevMap;
m.prevMap = m.currMap;
m.currMap = new typename LLKeyThrottleImpl<T>::EntryMap;
m.start_usec += m.interval_usec;
}
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.start_usec = 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.start_usec) / m.interval_usec);
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];
if (curr.count < m.countLimit)
{
curr.count = m.countLimit;
}
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;
}
protected:
LLKeyThrottleImpl<T>& m;
};
#endif
|
