summaryrefslogtreecommitdiff
path: root/indra/llcommon/llkeythrottle.h
blob: 8ee0e08c69fe75ccf5d4eb27fad5be88d6993168 (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
/**
 * @file llkeythrottle.h
 *
 * $LicenseInfo:firstyear=2005&license=viewerlgpl$
 * Second Life Viewer Source Code
 * Copyright (C) 2010, Linden Research, Inc.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation;
 * version 2.1 of the License only.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 *
 * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
 * $/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