llkeythrottle.h

Go to the documentation of this file.
00001 
00022 #ifndef LL_LLKEY_THROTTLE_H
00023 #define LL_LLKEY_THROTTLE_H
00024 
00025 // LLKeyThrottle keeps track of the number of action occurences with a key value
00026 // for a type over a given time period.  If the rate set in the constructor is
00027 // exceeed, the key is considered blocked.  The transition from unblocked to
00028 // blocked is noted so the responsible agent can be informed.  This transition
00029 // takes twice the look back window to clear.
00030 
00031 #include "linden_common.h"
00032 
00033 #include "llframetimer.h"
00034 #include <map>
00035 
00036 
00037 // Implementation utility class - use LLKeyThrottle, not this
00038 template <class T>
00039 class LLKeyThrottleImpl
00040 {
00041 public:
00042         struct Entry {
00043                 U32             count;
00044                 BOOL    blocked;
00045 
00046                 Entry() : count(0), blocked(FALSE) { }
00047         };
00048 
00049         typedef std::map<T, Entry> EntryMap;
00050 
00051         EntryMap * prevMap;
00052         EntryMap * currMap;
00053         
00054         U32 countLimit;
00055                 // maximum number of keys allowed per interval
00056                 
00057         U64 interval_usec;
00058                 // each map covers this time period
00059         U64 start_usec;
00060                 // currMap started counting at this time
00061                 // prevMap covers the previous interval
00062         
00063         LLKeyThrottleImpl() : prevMap(0), currMap(0) { }
00064 
00065         static U64 getTime()
00066         {
00067                 return LLFrameTimer::getTotalTime();
00068         }
00069 };
00070 
00071 
00072 template< class T >
00073 class LLKeyThrottle
00074 {
00075 public:
00076         LLKeyThrottle(U32 limit, F32 interval)
00077                 : m(* new LLKeyThrottleImpl<T>)
00078         {
00079                 // limit is the maximum number of keys
00080                 // allowed per interval (in seconds)
00081                 m.countLimit = limit;
00082                 m.interval_usec = (U64)(interval * USEC_PER_SEC);
00083                 m.start_usec = LLKeyThrottleImpl<T>::getTime();
00084 
00085                 m.prevMap = new typename LLKeyThrottleImpl<T>::EntryMap;
00086                 m.currMap = new typename LLKeyThrottleImpl<T>::EntryMap;
00087         }
00088                 
00089         ~LLKeyThrottle()
00090         {
00091                 delete m.prevMap;
00092                 delete m.currMap;
00093                 delete &m;
00094         }
00095 
00096         enum State {
00097                 THROTTLE_OK,                    // rate not exceeded, let pass
00098                 THROTTLE_NEWLY_BLOCKED, // rate exceed for the first time
00099                 THROTTLE_BLOCKED,               // rate exceed, block key
00100         };
00101 
00102         // call each time the key wants use
00103         State noteAction(const T& id, S32 weight = 1)
00104         {
00105                 U64 now = LLKeyThrottleImpl<T>::getTime();
00106 
00107                 if (now >= (m.start_usec + m.interval_usec))
00108                 {
00109                         if (now < (m.start_usec + 2 * m.interval_usec))
00110                         {
00111                                 // prune old data
00112                                 delete m.prevMap;
00113                                 m.prevMap = m.currMap;
00114                                 m.currMap = new typename LLKeyThrottleImpl<T>::EntryMap;
00115 
00116                                 m.start_usec += m.interval_usec;
00117                         }
00118                         else
00119                         {
00120                                 // lots of time has passed, all data is stale
00121                                 delete m.prevMap;
00122                                 delete m.currMap;
00123                                 m.prevMap = new typename LLKeyThrottleImpl<T>::EntryMap;
00124                                 m.currMap = new typename LLKeyThrottleImpl<T>::EntryMap;
00125 
00126                                 m.start_usec = now;
00127                         }
00128                 }
00129 
00130                 U32 prevCount = 0;
00131                 BOOL prevBlocked = FALSE;
00132 
00133                 typename LLKeyThrottleImpl<T>::EntryMap::const_iterator prev = m.prevMap->find(id);
00134                 if (prev != m.prevMap->end())
00135                 {
00136                         prevCount = prev->second.count;
00137                         prevBlocked = prev->second.blocked;
00138                 }
00139 
00140                 typename LLKeyThrottleImpl<T>::Entry& curr = (*m.currMap)[id];
00141 
00142                 bool wereBlocked = curr.blocked || prevBlocked;
00143 
00144                 curr.count += weight;
00145 
00146                 // curr.count is the number of keys in
00147                 // this current 'time slice' from the beginning of it until now
00148                 // prevCount is the number of keys in the previous
00149                 // time slice scaled to be one full time slice back from the current 
00150                 // (now) time.
00151 
00152                 // compute current, windowed rate
00153                 F64 timeInCurrent = ((F64)(now - m.start_usec) / m.interval_usec);
00154                 F64 averageCount = curr.count + prevCount * (1.0 - timeInCurrent);
00155                 
00156                 curr.blocked |= averageCount > m.countLimit;
00157 
00158                 bool nowBlocked = curr.blocked || prevBlocked;
00159 
00160                 if (!nowBlocked)
00161                 {
00162                         return THROTTLE_OK;
00163                 }
00164                 else if (!wereBlocked)
00165                 {
00166                         return THROTTLE_NEWLY_BLOCKED;
00167                 }
00168                 else
00169                 {
00170                         return THROTTLE_BLOCKED;
00171                 }
00172         }
00173 
00174         // call to force throttle conditions for id
00175         void throttleAction(const T& id)
00176         {
00177                 noteAction(id);
00178                 typename LLKeyThrottleImpl<T>::Entry& curr = (*m.currMap)[id];
00179                 if (curr.count < m.countLimit)
00180                 {
00181                         curr.count = m.countLimit;
00182                 }
00183                 curr.blocked = TRUE;
00184         }
00185 
00186         // returns TRUE if key is blocked
00187         BOOL isThrottled(const T& id) const
00188         {
00189                 if (m.currMap->empty()
00190                         && m.prevMap->empty())
00191                 {
00192                         // most of the time we'll fall in here
00193                         return FALSE;
00194                 }
00195 
00196                 // NOTE, we ignore the case where id is in the map but the map is stale.  
00197                 // You might think that we'd stop throttling things in such a case, 
00198                 // however it may be that a god has disabled scripts in the region or 
00199                 // estate --> we probably want to report the state of the id when the 
00200                 // scripting engine was paused.
00201                 typename LLKeyThrottleImpl<T>::EntryMap::const_iterator entry = m.currMap->find(id);
00202                 if (entry != m.currMap->end())
00203                 {
00204                         return entry->second.blocked;
00205                 }
00206                 entry = m.prevMap->find(id);
00207                 if (entry != m.prevMap->end())
00208                 {
00209                         return entry->second.blocked;
00210                 }
00211                 return FALSE;
00212         }
00213 
00214 protected:
00215         LLKeyThrottleImpl<T>& m;
00216 };
00217 
00218 #endif

Generated on Thu Jul 1 06:08:48 2010 for Second Life Viewer by  doxygen 1.4.7