| 1 |
/***************************************************************************** |
| 2 |
Copyright (c) 2001 - 2011, The Board of Trustees of the University of Illinois. |
| 3 |
All rights reserved. |
| 4 |
|
| 5 |
Redistribution and use in source and binary forms, with or without |
| 6 |
modification, are permitted provided that the following conditions are |
| 7 |
met: |
| 8 |
|
| 9 |
* Redistributions of source code must retain the above |
| 10 |
copyright notice, this list of conditions and the |
| 11 |
following disclaimer. |
| 12 |
|
| 13 |
* Redistributions in binary form must reproduce the |
| 14 |
above copyright notice, this list of conditions |
| 15 |
and the following disclaimer in the documentation |
| 16 |
and/or other materials provided with the distribution. |
| 17 |
|
| 18 |
* Neither the name of the University of Illinois |
| 19 |
nor the names of its contributors may be used to |
| 20 |
endorse or promote products derived from this |
| 21 |
software without specific prior written permission. |
| 22 |
|
| 23 |
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS |
| 24 |
IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, |
| 25 |
THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| 26 |
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR |
| 27 |
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| 28 |
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| 29 |
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 30 |
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| 31 |
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| 32 |
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 33 |
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 34 |
*****************************************************************************/ |
| 35 |
|
| 36 |
/***************************************************************************** |
| 37 |
written by |
| 38 |
Yunhong Gu, last updated 01/27/2011 |
| 39 |
*****************************************************************************/ |
| 40 |
|
| 41 |
#ifndef INC_SRT_CACHE_H |
| 42 |
#define INC_SRT_CACHE_H |
| 43 |
|
| 44 |
#include <list> |
| 45 |
#include <vector> |
| 46 |
|
| 47 |
#include "sync.h" |
| 48 |
#include "netinet_any.h" |
| 49 |
#include "udt.h" |
| 50 |
|
| 51 |
namespace srt |
| 52 |
{ |
| 53 |
|
| 54 |
class CCacheItem |
| 55 |
{ |
| 56 |
public: |
| 57 |
virtual ~CCacheItem() {} |
| 58 |
|
| 59 |
public: |
| 60 |
virtual CCacheItem& operator=(const CCacheItem&) = 0; |
| 61 |
|
| 62 |
// The "==" operator SHOULD only compare key values. |
| 63 |
virtual bool operator==(const CCacheItem&) = 0; |
| 64 |
|
| 65 |
/// get a deep copy clone of the current item |
| 66 |
/// @return Pointer to the new item, or NULL if failed. |
| 67 |
|
| 68 |
virtual CCacheItem* clone() = 0; |
| 69 |
|
| 70 |
/// get a random key value between 0 and MAX_INT to be used for the hash in cache |
| 71 |
/// @return A random hash key. |
| 72 |
|
| 73 |
virtual int getKey() = 0; |
| 74 |
|
| 75 |
// If there is any shared resources between the cache item and its clone, |
| 76 |
// the shared resource should be released by this function. |
| 77 |
virtual void release() {} |
| 78 |
}; |
| 79 |
|
| 80 |
template <typename T> |
| 81 |
class CCache |
| 82 |
{ |
| 83 |
public: |
| 84 |
CCache(int size = 1024) |
| 85 |
: m_iMaxSize(size) |
| 86 |
, m_iHashSize(size * 3) |
| 87 |
, m_iCurrSize(0) |
| 88 |
{ |
| 89 |
m_vHashPtr.resize(m_iHashSize); |
| 90 |
// Exception: -> CUDTUnited ctor |
| 91 |
srt::sync::setupMutex(m_Lock, "Cache"); |
| 92 |
} |
| 93 |
|
| 94 |
~CCache() { clear(); } |
| 95 |
|
| 96 |
public: |
| 97 |
/// find the matching item in the cache. |
| 98 |
/// @param [in,out] data storage for the retrieved item; initially it must carry the key information |
| 99 |
/// @return 0 if found a match, otherwise -1. |
| 100 |
|
| 101 |
int lookup(T* data) |
| 102 |
{ |
| 103 |
srt::sync::ScopedLock cacheguard(m_Lock); |
| 104 |
|
| 105 |
int key = data->getKey(); |
| 106 |
if (key < 0) |
| 107 |
return -1; |
| 108 |
if (key >= m_iMaxSize) |
| 109 |
key %= m_iHashSize; |
| 110 |
|
| 111 |
const ItemPtrList& item_list = m_vHashPtr[key]; |
| 112 |
for (typename ItemPtrList::const_iterator i = item_list.begin(); i != item_list.end(); ++i) |
| 113 |
{ |
| 114 |
if (*data == ***i) |
| 115 |
{ |
| 116 |
// copy the cached info |
| 117 |
*data = ***i; |
| 118 |
return 0; |
| 119 |
} |
| 120 |
} |
| 121 |
|
| 122 |
return -1; |
| 123 |
} |
| 124 |
|
| 125 |
/// update an item in the cache, or insert one if it doesn't exist; oldest item may be removed |
| 126 |
/// @param [in] data the new item to updated/inserted to the cache |
| 127 |
/// @return 0 if success, otherwise -1. |
| 128 |
|
| 129 |
int update(T* data) |
| 130 |
{ |
| 131 |
srt::sync::ScopedLock cacheguard(m_Lock); |
| 132 |
|
| 133 |
int key = data->getKey(); |
| 134 |
if (key < 0) |
| 135 |
return -1; |
| 136 |
if (key >= m_iMaxSize) |
| 137 |
key %= m_iHashSize; |
| 138 |
|
| 139 |
T* curr = NULL; |
| 140 |
|
| 141 |
ItemPtrList& item_list = m_vHashPtr[key]; |
| 142 |
for (typename ItemPtrList::iterator i = item_list.begin(); i != item_list.end(); ++i) |
| 143 |
{ |
| 144 |
if (*data == ***i) |
| 145 |
{ |
| 146 |
// update the existing entry with the new value |
| 147 |
***i = *data; |
| 148 |
curr = **i; |
| 149 |
|
| 150 |
// remove the current entry |
| 151 |
m_StorageList.erase(*i); |
| 152 |
item_list.erase(i); |
| 153 |
|
| 154 |
// re-insert to the front |
| 155 |
m_StorageList.push_front(curr); |
| 156 |
item_list.push_front(m_StorageList.begin()); |
| 157 |
|
| 158 |
return 0; |
| 159 |
} |
| 160 |
} |
| 161 |
|
| 162 |
// create new entry and insert to front |
| 163 |
curr = data->clone(); |
| 164 |
m_StorageList.push_front(curr); |
| 165 |
item_list.push_front(m_StorageList.begin()); |
| 166 |
|
| 167 |
++m_iCurrSize; |
| 168 |
if (m_iCurrSize >= m_iMaxSize) |
| 169 |
{ |
| 170 |
// Cache overflow, remove oldest entry. |
| 171 |
T* last_data = m_StorageList.back(); |
| 172 |
int last_key = last_data->getKey() % m_iHashSize; |
| 173 |
|
| 174 |
ItemPtrList& last_item_list = m_vHashPtr[last_key]; |
| 175 |
for (typename ItemPtrList::iterator i = last_item_list.begin(); i != last_item_list.end(); ++i) |
| 176 |
{ |
| 177 |
if (*last_data == ***i) |
| 178 |
{ |
| 179 |
last_item_list.erase(i); |
| 180 |
break; |
| 181 |
} |
| 182 |
} |
| 183 |
|
| 184 |
last_data->release(); |
| 185 |
delete last_data; |
| 186 |
m_StorageList.pop_back(); |
| 187 |
--m_iCurrSize; |
| 188 |
} |
| 189 |
|
| 190 |
return 0; |
| 191 |
} |
| 192 |
|
| 193 |
private: |
| 194 |
/// Specify the cache size (i.e., max number of items). |
| 195 |
/// Private or else must be protected by a lock. |
| 196 |
/// @param [in] size max cache size. |
| 197 |
void setSizeLimit(int size) |
| 198 |
{ |
| 199 |
m_iMaxSize = size; |
| 200 |
m_iHashSize = size * 3; |
| 201 |
m_vHashPtr.resize(m_iHashSize); |
| 202 |
} |
| 203 |
|
| 204 |
/// Clear all entries in the cache, restore to initialization state. |
| 205 |
/// Private or else must be protected by a lock. |
| 206 |
void clear() |
| 207 |
{ |
| 208 |
for (typename std::list<T*>::iterator i = m_StorageList.begin(); i != m_StorageList.end(); ++i) |
| 209 |
{ |
| 210 |
(*i)->release(); |
| 211 |
delete *i; |
| 212 |
} |
| 213 |
m_StorageList.clear(); |
| 214 |
for (typename std::vector<ItemPtrList>::iterator i = m_vHashPtr.begin(); i != m_vHashPtr.end(); ++i) |
| 215 |
i->clear(); |
| 216 |
m_iCurrSize = 0; |
| 217 |
} |
| 218 |
|
| 219 |
private: |
| 220 |
std::list<T*> m_StorageList; |
| 221 |
typedef typename std::list<T*>::iterator ItemPtr; |
| 222 |
typedef std::list<ItemPtr> ItemPtrList; |
| 223 |
std::vector<ItemPtrList> m_vHashPtr; |
| 224 |
|
| 225 |
int m_iMaxSize; |
| 226 |
int m_iHashSize; |
| 227 |
int m_iCurrSize; |
| 228 |
|
| 229 |
srt::sync::Mutex m_Lock; |
| 230 |
|
| 231 |
private: |
| 232 |
CCache(const CCache&); |
| 233 |
CCache& operator=(const CCache&); |
| 234 |
}; |
| 235 |
|
| 236 |
class CInfoBlock |
| 237 |
{ |
| 238 |
public: |
| 239 |
uint32_t m_piIP[4]; // IP address, machine read only, not human readable format. |
| 240 |
int m_iIPversion; // Address family: AF_INET or AF_INET6. |
| 241 |
uint64_t m_ullTimeStamp; // Last update time. |
| 242 |
int m_iSRTT; // Smoothed RTT. |
| 243 |
int m_iBandwidth; // Estimated link bandwidth. |
| 244 |
int m_iLossRate; // Average loss rate. |
| 245 |
int m_iReorderDistance; // Packet reordering distance. |
| 246 |
double m_dInterval; // Inter-packet time (Congestion Control). |
| 247 |
double m_dCWnd; // Congestion window size (Congestion Control). |
| 248 |
|
| 249 |
public: |
| 250 |
CInfoBlock() {} // NOTE: leaves uninitialized |
| 251 |
CInfoBlock& copyFrom(const CInfoBlock& obj); |
| 252 |
CInfoBlock(const CInfoBlock& src) { copyFrom(src); } |
| 253 |
CInfoBlock& operator=(const CInfoBlock& src) { return copyFrom(src); } |
| 254 |
bool operator==(const CInfoBlock& obj) const; |
| 255 |
CInfoBlock* clone(); |
| 256 |
int getKey(); |
| 257 |
void release() {} |
| 258 |
|
| 259 |
public: |
| 260 |
/// convert sockaddr structure to an integer array |
| 261 |
/// @param [in] addr network address |
| 262 |
/// @param [in] ver IP version |
| 263 |
/// @param [out] ip the result machine readable IP address in integer array |
| 264 |
|
| 265 |
static void convert(const sockaddr_any& addr, uint32_t ip[4]); |
| 266 |
}; |
| 267 |
|
| 268 |
} // namespace srt |
| 269 |
|
| 270 |
#endif |