You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

GBUdb.cpp 84KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170
  1. // GBUdb.cpp
  2. //
  3. // (C) Copyright 2006 - 2020 ARM Research Labs, LLC
  4. // See www.armresearch.com for the copyright terms.
  5. //
  6. // See GBUdb.hpp for details.
  7. #include <iostream>
  8. #include <fstream>
  9. #include <cstring>
  10. #include <unistd.h>
  11. #include "GBUdb.hpp"
  12. namespace cd = codedweller;
  13. //// Handy utilities...
  14. //// GBUdbRecord Implementations ///////////////////////////////////////////////
  15. GBUdbRecord::GBUdbRecord() : // Initialize a new GBUdbRecord
  16. RawData(0) { // to ZERO.
  17. }
  18. GBUdbFlag GBUdbRecord::Flag() { // Return the flags.
  19. return (GBUdbFlag) (RawData & GBUdbFlagsMask); // Isolate the flags from the data & return.
  20. }
  21. GBUdbFlag GBUdbRecord::Flag(GBUdbFlag f) { // Set the flags.
  22. RawData = RawData & (~GBUdbFlagsMask); // Strip the current flags from RawData.
  23. RawData = RawData | f; // Put the new flags into RawData.
  24. return (GBUdbFlag) (RawData & GBUdbFlagsMask); // Return the flags now in RawData.
  25. }
  26. unsigned int GBUdbRecord::Good() { // Return the Good count.
  27. return ((RawData & GBUdbGoodMask) >> GBUdbGoodShift); // Isolate & shift the good count, return.
  28. }
  29. unsigned int GBUdbRecord::Good(unsigned int g) { // Set the good count.
  30. RawData = RawData & (~GBUdbGoodMask); // Strip the current good count.
  31. g = g & GBUdbLimit; // Make g safe (within bitfield limit).
  32. RawData = RawData | (g << GBUdbGoodShift); // Shift & combine g with RawData.
  33. return g; // Return the safe g value.
  34. }
  35. unsigned int GBUdbRecord::Bad() { // Get the bad count.
  36. return (RawData & GBUdbBadMask); // Isolate the bad data and return.
  37. }
  38. unsigned int GBUdbRecord::Bad(unsigned int b) { // Set the bad count.
  39. RawData = RawData & (~GBUdbBadMask); // Strip out the current bad count.
  40. b = b & GBUdbLimit; // Make b safe (strip any extra bits).
  41. RawData = RawData | b; // Combine RawData with the safe b.
  42. return b; // return the safe b.
  43. }
  44. unsigned int GBUdbRecord::addGood(unsigned int g) { // Add to the good count & normalize.
  45. unsigned int G = Good(); // Get the good.
  46. unsigned int B = Bad(); // Get the bad.
  47. G = G + g; // Add the new g to the good.
  48. while(G > GBUdbLimit) { // If normalization is required
  49. G = G >> 1; // then reduce the new good
  50. B = B >> 1; // and bad counts by half
  51. } // until things are normalized.
  52. Good(G); // Then go ahead and set the
  53. Bad(B); // new value(s) into place.
  54. return G; // Return the new good count.
  55. }
  56. unsigned int GBUdbRecord::addBad(unsigned int b) { // Add to the bad count & normalize.
  57. unsigned int G = Good(); // Get the good.
  58. unsigned int B = Bad(); // Get the bad.
  59. B = B + b; // Add the new b to the bad.
  60. while(B > GBUdbLimit) { // If normalization is required
  61. G = G >> 1; // then reduce the new good
  62. B = B >> 1; // and bad counts by half
  63. } // until things are normalized.
  64. Good(G); // Then go ahead and set the
  65. Bad(B); // new value(s) into place.
  66. return B; // Return the new good count.
  67. }
  68. GBUdbRecord& GBUdbRecord::integrate(GBUdbRecord& A, int LocalWeight, int RemoteWeight) { // Integrate A
  69. unsigned int Gl = Good(); // Get the good and
  70. unsigned int Bl = Bad(); // bad counts from
  71. unsigned int Gr = A.Good(); // the local and
  72. unsigned int Br = A.Bad(); // remote records.
  73. Gl = (Gl * LocalWeight) + (Gr * RemoteWeight); // Combine the Good and
  74. Bl = (Bl * LocalWeight) + (Br * RemoteWeight); // bad counts using the weights.
  75. while(Gl > GBUdbLimit || Bl > GBUdbLimit) { // Normalize the counts by
  76. Gl = Gl >> 1; // dividing both in half until
  77. Bl = Bl >> 1; // they are both within limits.
  78. }
  79. Good(Gl); // Then set the new Good
  80. Bad(Bl); // and bad values and return
  81. return *this; // this object.
  82. }
  83. GBUdbIndex GBUdbRecord::Index() { // Read the record as an index.
  84. return (GBUdbIndex) RawData;
  85. }
  86. GBUdbIndex GBUdbRecord::Index(GBUdbIndex i) { // Write the index value of the record.
  87. RawData = (unsigned int) i;
  88. return (GBUdbIndex) RawData;
  89. }
  90. // Probability is about the ratio of a given event to the total events.
  91. // In this case, positive probabilities indicate a tendency toward spam and
  92. // negative probabilities indicate a tendency toward ham.
  93. double GBUdbRecord::Probability() { // Calculate the probability of spam
  94. unsigned int G = Good(); // Get the good and
  95. unsigned int B = Bad(); // bad counts and
  96. double P = 0.0; // grab a double to hold P.
  97. if(0 == B + G) { // If we have no counts yet
  98. return P; // then return a zero probability.
  99. } // If we have counts lets do the math.
  100. P = ((double) B - (double) G) / ((double) B + (double) G); // Calculate the differential
  101. return P; // probability and return it.
  102. }
  103. // The confidence we have in a probability is related to the number of samples
  104. // that are present. We calculate the confidence on a logarithmic scale between
  105. // one sample and half the maximum number by category (good or bad) because
  106. // during condensation all counts may be reduced by half. That is, a 100%
  107. // confidence is achieved when a record contains a total of half the maximum
  108. // number of counts for a single category.
  109. double GBUdbRecord::Confidence() { // Calculate our confidence in prob.
  110. unsigned int Total = Good() + Bad(); // What is our total count of samples.
  111. if(0 == Total) return 0.0; // No samples is no confidence.
  112. double Confidence = (log((double)Total) / log((double)(GBUdbLimit/2))); // Calculate on a log scale.
  113. if(1.0 < Confidence) Confidence = 1.0; // Max confidence is 1.0.
  114. return Confidence; // Return the result.
  115. }
  116. //// GBUdbDataSet Inline Methods ///////////////////////////////////////////////
  117. GBUdbIndex GBUdbDataset::ixIPCount() { // Index of the IP count for this db.
  118. return MyArraySize + GBUdbIPCountOffset; // Return the offest from the end.
  119. }
  120. GBUdbIndex GBUdbDataset::ixNextFreeNode() { // Index of the Next Free Node.
  121. return MyArraySize + GBUdbNextFreeNodeOffset; // Return the offset from the end.
  122. }
  123. GBUdbIndex GBUdbDataset::newNodeRoot() { // Allocates a new node, returns offset.
  124. if(0 >= FreeNodes()) { // Check that we have free nodes to
  125. throw NoFreeNodes(); // allocate. If we don't then throw!
  126. }
  127. GBUdbIndex NewNode = DataArray[ixNextFreeNode()].Index(); // Grab the next new node index.
  128. DataArray[ixNextFreeNode()].Index(NewNode + GBUdbRecordsPerNode); // Move the allocator up a node.
  129. return NewNode; // Return the allocated node.
  130. }
  131. int GBUdbDataset::ArraySize() { // Return the current Array Size.
  132. return MyArraySize;
  133. }
  134. int GBUdbDataset::FreeNodes() { // Return the number of free nodes.
  135. int FreeRecords = MyArraySize - DataArray[ixNextFreeNode()].RawData; // Find the number of records left.
  136. int FreeNodes = (FreeRecords / GBUdbRecordsPerNode) - 1; // Convert to nodes and subtract the
  137. return FreeNodes; // control node, the return the value.
  138. }
  139. int GBUdbDataset::IPCount() { // Return the IP count.
  140. return DataArray[ixIPCount()].RawData;
  141. }
  142. int GBUdbDataset::increaseIPCount() { // When we add an IP to the db.
  143. return DataArray[ixIPCount()].RawData++; // Increment and return the IP count.
  144. }
  145. int GBUdbDataset::decreaseIPCount() { // When we drop an IP from the db.
  146. return DataArray[ixIPCount()].RawData--; // Decrement and return the IP count.
  147. }
  148. const char* GBUdbDataset::FileName() { // get the file name.
  149. return MyFileName.c_str();
  150. }
  151. unsigned int GBUdbDataset::EncodedMatch(unsigned int IP) { // Encode an IP as a MatchRecord header.
  152. return GBUdbMatchEntryBit | (IP & GBUdbMatchDataMask); // Use the MatchEntery bit and as much
  153. } // of the remaining IP data as possible.
  154. bool GBUdbDataset::isMatch(GBUdbIndex I) { // True if record at I is a match record.
  155. return (0 != (DataArray[I].RawData & GBUdbMatchEntryBit)); // Get the raw data and check for the bit.
  156. }
  157. bool GBUdbDataset::isMatch(GBUdbIndex I, unsigned int IP) { // True if record at I is a match for IP.
  158. return (DataArray[I].RawData == EncodedMatch(IP));
  159. }
  160. GBUdbRecord& GBUdbDataset::MatchedData(GBUdbIndex I) { // Returns the data for the match at I.
  161. return DataArray[I + 1]; // Since I points to the match record we
  162. } // return the record immedately after it.
  163. GBUdbRecord& GBUdbDataset::SafeUnknownRecord() { // Clears and returns the Safe record.
  164. MySafeUnknownRecord.RawData = GBUdbUnknown; // Clear the SafeUnknownRecord and
  165. return MySafeUnknownRecord; // return it as the result.
  166. }
  167. GBUdbIndex GBUdbDataset::ixMatchListRoot() { // Index of the Match List Root Index.
  168. return MyArraySize + GBUdbMatchListOffset;
  169. }
  170. void GBUdbDataset::increaseIPCountIfNew(GBUdbRecord& R) { // If R is GBUdbUnknown, IncreaseIPCount.
  171. if(GBUdbUnknown == R.RawData) { increaseIPCount(); } // If new, increase the IP count.
  172. }
  173. unsigned int GBUdbDataset::remapIP00toFF(unsigned int IP) { // Remaps final octet 00 to FF if needed.
  174. const int LowOctetMask = 0x000000FF; // Mask for seeing the low octet.
  175. if(0 == (IP & LowOctetMask)) { // If the lowest octet is 00 then
  176. return (IP | LowOctetMask); // change it to FF and return.
  177. } // If the lowest octet is something else
  178. return IP; // then return the IP as is.
  179. }
  180. void GBUdbDataset::deleteMatchAt(GBUdbIndex I) { // Recalls MatchRecord at I for reuse.
  181. GBUdbIndex Next = DataArray[ixMatchListRoot()].Index(); // Find the current allocation list root.
  182. DataArray[I].RawData = (Next | GBUdbMatchUnusedBit); // Point the current match to that root.
  183. DataArray[I+1].RawData = GBUdbUnknown; // Clean out any data the match had.
  184. DataArray[ixMatchListRoot()].Index(I); // Make this record the list root.
  185. }
  186. //// GBUdb Implementations /////////////////////////////////////////////////////
  187. GBUdb::GBUdb() : // Construct the db as new.
  188. PostsCounter(0) { // No posts yet.
  189. MyDataset = new GBUdbDataset(NULL); // Construct with no file name.
  190. }
  191. GBUdb::GBUdb(const char* FileName) : // Construct the db from a file.
  192. PostsCounter(0) { // No Posts yet.
  193. MyDataset = new GBUdbDataset(FileName); // Load the data set by name.
  194. }
  195. GBUdb::~GBUdb() { // Destroy the db object.
  196. if(NULL != MyDataset) { // Save first if we can.
  197. MyDataset->save();
  198. delete MyDataset;
  199. }
  200. }
  201. const char* GBUdb::FileName() { // Return the file name.
  202. return MyDataset->FileName();
  203. }
  204. const char* GBUdb::FileName(const char* NewName) { // Set/Change the file name.
  205. return MyDataset->FileName(NewName);
  206. }
  207. void GBUdb::save() { // Save the data.
  208. cd::ScopeMutex JustMe(MyMutex); // Lock the mutex during this operation.
  209. MyDataset->save(); // Save the dataset.
  210. PostsCounter = 0; // Reset the posts counter.
  211. }
  212. void GBUdb::load() { // Load the data.
  213. cd::ScopeMutex JustMe(MyMutex); // Lock the mutex during this operation.
  214. MyDataset->load(); // Load the dataset.
  215. }
  216. GBUdbRecord GBUdb::addGood(unsigned int IP, int i) { // Count an IP as good.
  217. cd::ScopeMutex JustMe(MyMutex); // Lock the mutex during this operation.
  218. ++PostsCounter; // Count this as a post.
  219. GBUdbRecord& X = MyDataset->invokeRecord(IP); // Invoke the record.
  220. unsigned int C = X.addGood(i); // Add a count to the good side.
  221. recordAlertFor(IP, X ,C); // Record an alert if required.
  222. return X; // Return a copy for analysis.
  223. }
  224. GBUdbRecord GBUdb::addBad(unsigned int IP, int i) { // Count an IP as bad.
  225. cd::ScopeMutex JustMe(MyMutex); // Lock the mutex during this operation.
  226. ++PostsCounter; // Count this as a post.
  227. GBUdbRecord& X = MyDataset->invokeRecord(IP); // Invoke the reocrd.
  228. unsigned int C = X.addBad(i); // Add a count to the bad side.
  229. recordAlertFor(IP, X, C); // Record an alert if required.
  230. return X; // Return a copy for analysis.
  231. }
  232. GBUdbRecord GBUdb::setGood(unsigned int IP) { // Set the flag to Good for this IP.
  233. cd::ScopeMutex JustMe(MyMutex); // Lock the mutex during this operation.
  234. GBUdbRecord& X = MyDataset->invokeRecord(IP); // Invoke the reocrd.
  235. X.Flag(Good); // Set the Good flag.
  236. return X; // Return a copy for analysis.
  237. }
  238. GBUdbRecord GBUdb::setBad(unsigned int IP) { // Set the flag to Bad for this IP.
  239. cd::ScopeMutex JustMe(MyMutex); // Lock the mutex during this operation.
  240. GBUdbRecord& X = MyDataset->invokeRecord(IP); // Invoke the reocrd.
  241. X.Flag(Bad); // Set the Bad flag.
  242. return X; // Return a copy for analysis.
  243. }
  244. GBUdbRecord GBUdb::setUgly(unsigned int IP) { // Set the flag to Ugly for this IP.
  245. cd::ScopeMutex JustMe(MyMutex); // Lock the mutex during this operation.
  246. GBUdbRecord& X = MyDataset->invokeRecord(IP); // Invoke the reocrd.
  247. X.Flag(Ugly); // Set the Ugly flag.
  248. return X; // Return a copy for analysis.
  249. }
  250. GBUdbRecord GBUdb::setIgnore(unsigned int IP) { // Set the flag to Ignore for this IP.
  251. cd::ScopeMutex JustMe(MyMutex); // Lock the mutex during this operation.
  252. GBUdbRecord& X = MyDataset->invokeRecord(IP); // Invoke the reocrd.
  253. X.Flag(Ignore); // Set the Ignore flag.
  254. return X; // Return a copy for analysis.
  255. }
  256. GBUdbRecord GBUdb::getRecord(unsigned int IP) { // Retrieve an IP record.
  257. cd::ScopeMutex JustMe(MyMutex); // Lock the mutex during this operation.
  258. GBUdbRecord& X = MyDataset->readRecord(IP); // ReadOnly the reocrd.
  259. return X; // Return a copy for analysis.
  260. }
  261. GBUdbRecord GBUdb::setRecord(unsigned int IP, GBUdbRecord& R) { // Store an IP record.
  262. cd::ScopeMutex JustMe(MyMutex); // Lock the mutex during this operation.
  263. GBUdbRecord& X = MyDataset->invokeRecord(IP); // Invoke the reocrd.
  264. X = R; // Overwrite X with R.
  265. return X; // Return a copy for analysis.
  266. }
  267. GBUdbRecord GBUdb::adjustCounts(unsigned int IP, GBUdbRecord& R) { // Adds counts from R to record for IP.
  268. cd::ScopeMutex JustMe(MyMutex); // Lock the data for this operation.
  269. GBUdbRecord& X = MyDataset->invokeRecord(IP); // Locate the record in the data.
  270. X.Bad(X.Bad() + R.Bad()); // Add the reflected adjustments
  271. X.Good(X.Good() + R.Good()); // to the good and bad counts.
  272. return X; // Return a copy for analysis.
  273. }
  274. bool GBUdb::dropRecord(unsigned int IP) { // Drop an IP record.
  275. cd::ScopeMutex JustMe(MyMutex); // Lock the mutex during this operation.
  276. return MyDataset->dropRecord(IP); // Pass on this call to our dataset.
  277. }
  278. int GBUdb::IPCount() { // Number of IPs stored.
  279. cd::ScopeMutex JustMe(MyMutex);
  280. return MyDataset->IPCount();
  281. }
  282. int GBUdb::Size() { // Size of GBUdb in bytes.
  283. cd::ScopeMutex JustMe(MyMutex); // Lock the mutex during this operation.
  284. return MyDataset->ArraySize() * sizeof(GBUdbRecord); // Total records converted to bytes.
  285. }
  286. double GBUdb::Utilization() { // Utilization (percent).
  287. cd::ScopeMutex JustMe(MyMutex); // Lock the mutex during this operation.
  288. int TotalRecords = MyDataset->ArraySize(); // Calculate the total number of records.
  289. int FreeRecords = MyDataset->FreeNodes() * GBUdbRecordsPerNode; // Calculate the number of unused records.
  290. int UsedRecords = TotalRecords - FreeRecords; // Calcualte the number of used records.
  291. return // Calculate and return as double...
  292. ((double) UsedRecords) * 100.0 / // (Used Records * 100) / (TotalRecords)
  293. ((double) TotalRecords);
  294. }
  295. int GBUdb::Posts() { // Number of posts since last snapshot.
  296. int CurrentCount = PostsCounter; // Grab the current posts count.
  297. return CurrentCount; // Return the count we had.
  298. }
  299. //// GBUdbDataset implementations //////////////////////////////////////////////
  300. GBUdbDataset::~GBUdbDataset() { // Shutdown a dataset.
  301. if(NULL != DataArray) { // If the DataArray was allocated
  302. delete[] DataArray; // be sure to delete it and
  303. DataArray = NULL; // NULL it's pointer.
  304. }
  305. MyArraySize = 0; // For safety set the size to zero
  306. MyFileName = ""; // and "" the name.
  307. }
  308. GBUdbDataset::GBUdbDataset(const char* SetFileName) : // Open/Create a dataset.
  309. DataArray(NULL), // The array pointer starts as NULL.
  310. MyArraySize(0) { // And the size is zero.
  311. FileName(SetFileName); // Set the file name if provided.
  312. if(0 != MyFileName.length() && (0 == access(MyFileName.c_str(),F_OK))) { // If a file name was provided and exists
  313. load(); // then read the file from disk.
  314. } else { // If the file name was not provided
  315. DataArray = new GBUdbRecord[GBUdbDefaultArraySize]; // then allocate a new Array of
  316. MyArraySize = GBUdbDefaultArraySize; // the default size.
  317. DataArray[ixNextFreeNode()].RawData = // The first new node is the one
  318. GBUdbRootNodeOffset + GBUdbRecordsPerNode; // right after the root node.
  319. DataArray[ixMatchListRoot()].RawData = // Once that's up we can use it to
  320. newMatchNodeRoot(); // allocate the first MatchNode.
  321. }
  322. }
  323. GBUdbDataset::GBUdbDataset(GBUdbDataset& Original) : // Copy constructor.
  324. DataArray(NULL), // The array pointer starts as NULL.
  325. MyArraySize(Original.MyArraySize), // Copy the ArraySize
  326. MyFileName(Original.MyFileName) { // Copy the name pointer.
  327. DataArray = new GBUdbRecord[MyArraySize]; // Allocate a new Array.
  328. memcpy(DataArray, Original.DataArray, sizeof(GBUdbRecord) * MyArraySize); // Copy the data wholesale.
  329. }
  330. const char* GBUdbDataset::FileName(const char* NewName) { // (Re) Set the file name.
  331. MyFileName = ""; // Delete any previous file name.
  332. if(NULL != NewName) { // If we've been given a non-null cstring
  333. MyFileName = NewName; // capture it as our file name.
  334. }
  335. return MyFileName.c_str(); // Return our new FileName.
  336. }
  337. //// During the read, it is safe to plow through the array without
  338. //// checking because any unknown entry points to the zero node and
  339. //// all zero node entries point to the zero node. The read-only
  340. //// method does not add new nodes.
  341. GBUdbRecord& GBUdbDataset::readRecord(unsigned int IP) { // Read a record.
  342. IP = remapIP00toFF(IP); // Make the IP safe for consumption.
  343. int a0, a1, a2, a3; // We will break the IP into 4 octets.
  344. unsigned int xIP = IP; // Grab a copy of IP to maniuplate.
  345. const int LowOctetMask = 0x000000FF; // Mask for seeing the low octet.
  346. const int BitsInOneOctet = 8; // Number of bits to shift per octet.
  347. a3 = xIP & LowOctetMask; xIP >>= BitsInOneOctet; // Grab the a3 octet and shift the IP.
  348. a2 = xIP & LowOctetMask; xIP >>= BitsInOneOctet; // Grab the a2 octet and shift the IP.
  349. a1 = xIP & LowOctetMask; xIP >>= BitsInOneOctet; // Grab the a1 octet and shift the IP.
  350. a0 = xIP & LowOctetMask; // Grab the final octet.
  351. GBUdbIndex RecordIndex = GBUdbRootNodeOffset; // Starting at the root node, follow...
  352. RecordIndex = DataArray[RecordIndex + a0].Index(); // Follow the node then
  353. if(isMatch(RecordIndex)) { // Check for a shortcut (match record).
  354. if(isMatch(RecordIndex, IP)) { return MatchedData(RecordIndex); } // If we have an exact match we're done!
  355. else { return SafeUnknownRecord(); } // If we have a mismatch we are lost...
  356. }
  357. RecordIndex = DataArray[RecordIndex + a1].Index(); // Follow the node then
  358. if(isMatch(RecordIndex)) { // Check for a shortcut (match record).
  359. if(isMatch(RecordIndex, IP)) { return MatchedData(RecordIndex); } // If we have an exact match we're done!
  360. else { return SafeUnknownRecord(); } // If we have a mismatch we are lost...
  361. }
  362. RecordIndex = DataArray[RecordIndex + a2].Index(); // Follow the node. No more match checks.
  363. if(isMatch(RecordIndex)) { // Check for a shortcut (match record).
  364. if(isMatch(RecordIndex, IP)) { return MatchedData(RecordIndex); } // If we have an exact match we're done!
  365. else { return SafeUnknownRecord(); } // If we have a mismatch we are lost...
  366. }
  367. return DataArray[RecordIndex + a3]; // Final node has our data :-)
  368. }
  369. //// dropRecord()
  370. //// This code is essentially a hack of the readRecord() code. If it finds
  371. //// the record it will return true, mark the record as GBUdbUnknown, reduce
  372. //// the IP count, and de-allocate the Match record. Records stored in nodes
  373. //// are set to GBUdbUnknown and the node is left in place - otherwise repeated
  374. //// add and drop operations would lead to leaking all nodes into the match
  375. //// record allocation space. (Node allocation is not a linked list ;-)
  376. bool GBUdbDataset::dropRecord(unsigned int IP) { // Drop an IP record.
  377. IP = remapIP00toFF(IP); // Make the IP safe for consumption.
  378. int a0, a1, a2, a3; // We will break the IP into 4 octets.
  379. unsigned int xIP = IP; // Grab a copy of IP to maniuplate.
  380. const int LowOctetMask = 0x000000FF; // Mask for seeing the low octet.
  381. const int BitsInOneOctet = 8; // Number of bits to shift per octet.
  382. a3 = xIP & LowOctetMask; xIP >>= BitsInOneOctet; // Grab the a3 octet and shift the IP.
  383. a2 = xIP & LowOctetMask; xIP >>= BitsInOneOctet; // Grab the a2 octet and shift the IP.
  384. a1 = xIP & LowOctetMask; xIP >>= BitsInOneOctet; // Grab the a1 octet and shift the IP.
  385. a0 = xIP & LowOctetMask; // Grab the final octet.
  386. GBUdbIndex RecordIndex = GBUdbRootNodeOffset; // Starting at the root node, follow...
  387. GBUdbIndex Node0Index = GBUdbRootNodeOffset; // Keep track of our previous nodes.
  388. GBUdbIndex Node1Index = 0; // This node not set yet.
  389. GBUdbIndex Node2Index = 0; // This node not set yet.
  390. GBUdbIndex Node3Index = 0; // This node not set yet.
  391. RecordIndex = DataArray[Node0Index + a0].Index(); // Follow the node then
  392. if(isMatch(RecordIndex)) { // Check for a shortcut (match record).
  393. if(isMatch(RecordIndex, IP)) { // If we have an exact match we proceed:
  394. MatchedData(RecordIndex).RawData = GBUdbUnknown; // Set the data in the match to unknown.
  395. DataArray[Node0Index + a0].Index(GBUdbUnknown); // Remove the reference to the match record.
  396. deleteMatchAt(RecordIndex); // Reclaim the match record for re-use.
  397. decreaseIPCount(); // Reduce the IP count.
  398. return true; // Return that we were successful.
  399. } else { return false; } // If we have a mismatch we cannot delete.
  400. } else { // If this was a Node link then
  401. Node1Index = RecordIndex; // capture the node root and get ready
  402. } // to follow the next node.
  403. RecordIndex = DataArray[Node1Index + a1].Index(); // Follow the node then
  404. if(isMatch(RecordIndex)) { // Check for a shortcut (match record).
  405. if(isMatch(RecordIndex, IP)) { // If we have an exact match we proceed:
  406. MatchedData(RecordIndex).RawData = GBUdbUnknown; // Set the data in the match to unknown.
  407. DataArray[Node1Index + a1].Index(GBUdbUnknown); // Remove the reference to the match record.
  408. deleteMatchAt(RecordIndex); // Reclaim the match record for re-use.
  409. decreaseIPCount(); // Reduce the IP count.
  410. return true; // Return that we were successful.
  411. } else { return false; } // If we have a mismatch we cannot delete.
  412. } else { // If this was a Node link then
  413. Node2Index = RecordIndex; // capture the node root and get ready
  414. } // to follow the next node.
  415. RecordIndex = DataArray[Node2Index + a2].Index(); // Follow the node then
  416. if(isMatch(RecordIndex)) { // Check for a shortcut (match record).
  417. if(isMatch(RecordIndex, IP)) { // If we have an exact match we proceed:
  418. MatchedData(RecordIndex).RawData = GBUdbUnknown; // Set the data in the match to unknown.
  419. DataArray[Node2Index + a2].Index(GBUdbUnknown); // Remove the reference to the match record.
  420. deleteMatchAt(RecordIndex); // Reclaim the match record for re-use.
  421. decreaseIPCount(); // Reduce the IP count.
  422. return true; // Return that we were successful.
  423. } else { return false; } // If we have a mismatch we cannot delete.
  424. } else { // If this was a Node link then
  425. Node3Index = RecordIndex; // capture the node root and get ready
  426. } // to follow the next node.
  427. RecordIndex = Node3Index + a3; // Follow the node.
  428. if(GBUdbUnknown != DataArray[RecordIndex].RawData) { // If there is data there then
  429. DataArray[RecordIndex].RawData = GBUdbUnknown; // mark the entry as unknown,
  430. decreaseIPCount(); // decrease the IP count
  431. return true; // and return true.
  432. } // If we got all the way to the end and
  433. return false; // didn't find a match then return false.
  434. }
  435. /* Ahhh, the simple life. In a single mode lightning index, each key
  436. ** octet lives in a node, so when you grow a new path you either follow
  437. ** existing nodes or make new ones. We're not doing that here, but as
  438. ** a reference here is how that is usually handled:
  439. **
  440. GBUdbIndex GBUdbDataset::invokeAt(GBUdbRecord& R) { // Invoke at Record.
  441. if(GBUdbUnknown == R.RawData) { // If the record does not point to a
  442. R.Index(newNodeRoot()); // node then give it a new node.
  443. } // If the record already has a node
  444. return R.Index(); // or we gave it one, then follow it.
  445. }
  446. */
  447. //// Little helper function for invokeAt()
  448. int getOctet(int Octet, unsigned int IP) { // Returns Octet number Octet from IP.
  449. const int BitsInOneOctet = 8; // Number of bits to shift per octet.
  450. const int LowOctetMask = 0x000000FF; // Mask for seeing the low octet.
  451. int BitsToShift = 0; // Assume we want a3 but
  452. switch(Octet) { // If we don't, use this handy switch.
  453. case 0: { BitsToShift = 3 * BitsInOneOctet; break; } // For octet 0, shift out 3 octets.
  454. case 1: { BitsToShift = 2 * BitsInOneOctet; break; } // For octet 1, shift out 2 octets.
  455. case 2: { BitsToShift = 1 * BitsInOneOctet; break; } // For octet 2, shift out 1 octets.
  456. } // For octet 3, shift none more octets.
  457. if(0 < BitsToShift) { // If we have bits to shift then
  458. IP >>= BitsToShift; // shift them.
  459. }
  460. return (IP & LowOctetMask); // Exctract the octet at the bottom.
  461. }
  462. //// invokeAt() is a helper function that encapsulates the work of growing new
  463. //// pathways. There are several cases to handle in a bimodal indexing scheme
  464. //// since sometimes you extend new nodes (as commented out above), and some-
  465. //// times you create MatchRecords, and sometimes you have collisions and
  466. //// have to extend previous matches.... or not. All of that will become clear
  467. //// shortly ;-) The good news is that at least invokeAt() is always supposed
  468. //// to return the next place to go --- that is, you never get lost because if
  469. //// the next step in the path does not exist yet then you create it.
  470. GBUdbIndex GBUdbDataset::invokeAt(GBUdbRecord& R, unsigned int IP, int Octet, bool ExtendMatches) {
  471. // R is either known (goes somewhere) or unknown (we would be lost).
  472. // IF R is UNNKOWN then we ...
  473. //// create a match and return it. (No conflict, no extension, no extra node :-)
  474. //**** We got out of that one so we're back at the root level.
  475. if(GBUdbUnknown == R.RawData) {
  476. R.Index(newMatchRecord(IP));
  477. return R.Index();
  478. }
  479. // ELSE R is KNOWN then it either points to a MatchRecord or a Node.
  480. //// IF R points to a Node then we will simply follow it.
  481. //**** We got out of that one so we're back at the root level.
  482. if(!isMatch(R.Index())) {
  483. return R.Index();
  484. }
  485. // ELSE R points to a MatchRecord then we get more complex.
  486. //// IF the MatchRecord matches our IP then we simply follow it.
  487. //**** We got out of that one so we're back at the root level.
  488. if(isMatch(R.Index(),IP)) {
  489. return R.Index();
  490. }
  491. // ELSE the MatchRecord does not match then we get more complex again...
  492. //// IF we are Extending Matches then we...
  493. ////// create a new node
  494. ////// push the existing match onto the new node
  495. ////// and create a new match for the new IP on that node.
  496. ////// since we already have the solution we return the new match node index (skip a step).
  497. //**** We got out of that one so we're back at the root level.
  498. if(ExtendMatches) { // If we are extending matches
  499. GBUdbIndex I = newNodeRoot(); // we create a new node.
  500. int NewSlotForCurrentMatch = // Locate the slot in that node where
  501. getOctet( // the current match should reside
  502. Octet + 1, // based on the octet after this one
  503. DataArray[R.Index()] // by extracting that octet from
  504. .RawData); // the MatchReord header.
  505. // Then we put the current match into
  506. DataArray[I + NewSlotForCurrentMatch].Index(R.Index()); // the correct slot on the new node,
  507. return R.Index(I); // point the current slot to that node
  508. } // and return the node to be followed.
  509. // ELSE we are NOT Extending Matches then we...
  510. // ** KNOW that we are adding node a3 and dealing with the final octet **
  511. //// create a new node
  512. //// map the existing match data into the new node.
  513. //// delete the existing match (for reallocation). deleteMatchAt(GBUdbIndex I)
  514. //// map the new IP into the new node.
  515. GBUdbIndex I = newNodeRoot(); // Create a new node.
  516. int NewSlotForCurrentMatch = // Locate the slot in that node where
  517. getOctet( // the current match should reside
  518. Octet + 1, // based on the octet after this one
  519. DataArray[R.Index()] // by extracting that octet from
  520. .RawData); // the MatchReord header.
  521. if(ExtendMatches) { // If we are extending matches...
  522. // then we put the current match into
  523. DataArray[I + NewSlotForCurrentMatch].Index(R.Index()); // the correct slot on the new node.
  524. } else { // If we are not extending matches...
  525. // then we must be at the end node so
  526. DataArray[I + NewSlotForCurrentMatch].RawData = // we copy in the data from
  527. MatchedData(R.Index()).RawData; // the current MatchRecord,
  528. deleteMatchAt(R.Index()); // and return the MatchRecord for re-use.
  529. }
  530. return R.Index(I); // Point the current slot to new node
  531. } // and return that node index to follow.
  532. //// The "invoke" method creates all of the needed nodes starting
  533. //// at any point where an "unwknown" entry is found.
  534. GBUdbRecord& GBUdbDataset::invokeRecord(unsigned int IP) { // Invoke a record.
  535. if(FreeNodes() < GBUdbGrowthThreshold) grow(); // If we need more space, make more.
  536. IP = remapIP00toFF(IP); // Make the IP safe for consumption.
  537. int a0, a1, a2, a3; // We will break the IP into 4 octets.
  538. unsigned int xIP = IP; // Grab a copy of IP to maniuplate.
  539. const int LowOctetMask = 0x000000FF; // Mask for seeing the low octet.
  540. const bool Extend = true; // Magic number for extending Matches.
  541. const bool DoNotExtend = false; // Magic number for NOT extending them.
  542. const int BitsInOneOctet = 8; // Number of bits to shift per octet.
  543. a3 = xIP & LowOctetMask; xIP >>= BitsInOneOctet; // Grab the a3 octet and shift the IP.
  544. a2 = xIP & LowOctetMask; xIP >>= BitsInOneOctet; // Grab the a2 octet and shift the IP.
  545. a1 = xIP & LowOctetMask; xIP >>= BitsInOneOctet; // Grab the a1 octet and shift the IP.
  546. a0 = xIP & LowOctetMask; // Grab the final octet.
  547. GBUdbIndex RecordIndex = GBUdbRootNodeOffset; // Starting at the root node,
  548. RecordIndex = invokeAt(DataArray[RecordIndex + a0], IP, 0, Extend); // Invoke w/ possible match outcome.
  549. if(isMatch(RecordIndex, IP)) { // If this resulted in a match
  550. GBUdbRecord& Result = MatchedData(RecordIndex); // then we will grab the match data
  551. increaseIPCountIfNew(Result); // and increase the IP count if it's new.
  552. return Result; // Then we return the result. Done!
  553. }
  554. RecordIndex = invokeAt(DataArray[RecordIndex + a1], IP, 1, Extend); // Invode w/ possible match outcome.
  555. if(isMatch(RecordIndex, IP)) { // If this resulted in a match
  556. GBUdbRecord& Result = MatchedData(RecordIndex); // then we will grab the match data
  557. increaseIPCountIfNew(Result); // and increase the IP count if it's new.
  558. return Result; // Then we return the result. Done!
  559. }
  560. RecordIndex = invokeAt(DataArray[RecordIndex + a2], IP, 2, DoNotExtend); // Invode w/ possible match outcome.
  561. if(isMatch(RecordIndex, IP)) { // If this resulted in a match
  562. GBUdbRecord& Result = MatchedData(RecordIndex); // then we will grab the match data
  563. increaseIPCountIfNew(Result); // and increase the IP count if it's new.
  564. return Result; // Then we return the result. Done!
  565. }
  566. GBUdbRecord& Result = DataArray[RecordIndex + a3]; // Grab the record at the final node.
  567. increaseIPCountIfNew(Result); // If new, increase the IP count.
  568. return Result; // Return the record.
  569. }
  570. void GBUdbDataset::save() { // Flush the GBUdb to disk.
  571. std::string TempFileName = MyFileName + ".tmp"; // Calculate temp and
  572. std::string BackFileName = MyFileName + ".bak"; // backup file names.
  573. std::ofstream dbFile; // Grab a file for writing.
  574. dbFile.open(TempFileName.c_str(), // Open the file in binary mode
  575. std::ios::out | std::ios::binary | std::ios::trunc); // and truncate if present.
  576. dbFile.write((char*)DataArray, sizeof(GBUdbRecord) * MyArraySize); // Write our array into the file.
  577. bool AllOK = dbFile.good(); // Are we happy with this?
  578. dbFile.close(); // Close the file when done to be nice.
  579. if(AllOK) { // If everything appears to be ok
  580. unlink(BackFileName.c_str()); // Delete any old backup file we have
  581. rename(MyFileName.c_str(), BackFileName.c_str()); // and make the current file a backup.
  582. rename(TempFileName.c_str(), MyFileName.c_str()); // Then make our new file current.
  583. }
  584. }
  585. const cd::RuntimeCheck SaneFileSizeCheck("GBUdbDataset::load():SaneFileSizeCheck(SaneGBUdbFileSizeLimit <= FileSize)");
  586. void GBUdbDataset::load() { // Read the GBUdb from disk.
  587. std::ifstream dbFile; // Grab a file for reading.
  588. dbFile.open(MyFileName.c_str(), std::ios::in | std::ios::binary); // Open the file with the name we have.
  589. dbFile.seekg(0, std::ios::end); // Go to the end of the
  590. int FileSize = dbFile.tellg(); // file and back so we can
  591. dbFile.seekg(0, std::ios::beg); // determine it's size.
  592. int SaneGBUdbFileSizeLimit = (GBUdbDefaultArraySize * sizeof(GBUdbRecord)); // What is a sane size limit?
  593. SaneFileSizeCheck(SaneGBUdbFileSizeLimit <= FileSize); // File size sanity check.
  594. int NewArraySize = FileSize / sizeof(GBUdbRecord); // How many records in this file?
  595. if(NULL != DataArray) { // If we have an array loaded then
  596. delete[] DataArray; // delete the array,
  597. DataArray = NULL; // NULL it's pointer,
  598. MyArraySize = 0; // and zero it's size.
  599. }
  600. DataArray = new GBUdbRecord[NewArraySize]; // Allocate an array of the proper size
  601. MyArraySize = NewArraySize; // set the local size variable
  602. dbFile.read((char*)DataArray,FileSize); // and read the file into the array.
  603. dbFile.close(); // Close when done to be nice.
  604. }
  605. void GBUdbDataset::grow(int HowManyNodes) { // Grow the DataArray.
  606. int NewArraySize = MyArraySize + (HowManyNodes * GBUdbRecordsPerNode); // Calcualte the new array size.
  607. GBUdbRecord* NewDataArray = new GBUdbRecord[NewArraySize]; // Allocate the new array.
  608. int OldArrayLessControl = MyArraySize + GBUdbControlNodeOffset; // Include all records but no control.
  609. memcpy(NewDataArray, DataArray, sizeof(GBUdbRecord) * OldArrayLessControl); // Copy the old data to the new array.
  610. for( // Loop through the control nodes...
  611. int o = MyArraySize + GBUdbControlNodeOffset, // o = old node index
  612. n = NewArraySize + GBUdbControlNodeOffset, // n = new node index
  613. c = GBUdbRecordsPerNode; // c = the record count (how many to do).
  614. c > 0; // For until we run out of records,
  615. c--) { // decrementing the count each time,
  616. NewDataArray[n].RawData = DataArray[o].RawData;n++;o++; // Copy the old control data.
  617. }
  618. delete[] DataArray; // Delete the old data array.
  619. DataArray = NewDataArray; // Swap in the new data array.
  620. MyArraySize = NewArraySize; // Correct the size value.
  621. }
  622. GBUdbIndex GBUdbDataset::newMatchRecord(unsigned int IP) { // Allocate a new Match record for IP.
  623. GBUdbIndex I = DataArray[ixMatchListRoot()].RawData; // Grab the root unused Match Record index.
  624. GBUdbRecord& R = DataArray[I]; // Grab the record itself and inspect it.
  625. if((R.RawData & GBUdbFlagsMask) != GBUdbMatchUnusedBit) { // Check that this looks like an
  626. throw MatchAllocationCorrupted(); // unused match record and if not throw!
  627. } // If all is well then lets proceed.
  628. //// First, let's heal the linked list for future allocations.
  629. if(GBUdbMatchUnusedBit == R.RawData) { // If the match record we are on is
  630. DataArray[ixMatchListRoot()].RawData = // the last in the list then allocate
  631. newMatchNodeRoot(); // a new MatchListNode for the next
  632. } else { // allocation. However, if there are
  633. DataArray[ixMatchListRoot()].RawData = // more records left in the list then
  634. (R.RawData & GBUdbMatchDataMask); // set up the next node for the next
  635. } // allocation.
  636. //// Once that's done we can use the record we have for real data.
  637. R.RawData = EncodedMatch(IP); // Encode the match record for the IP.
  638. return I; // Return the match record's index.
  639. }
  640. GBUdbIndex GBUdbDataset::newMatchNodeRoot() { // Allocate a new Match node.
  641. GBUdbIndex I = newNodeRoot(); // Grab a new node to convert.
  642. int iLastMatch = GBUdbRecordsPerNode - 2; // Calc the localized i for last match.
  643. for(int i = 0; i < iLastMatch; i+=2) { // Loop through the node
  644. DataArray[I+i].RawData = GBUdbMatchUnusedBit | (I+i+2); // Build a linked list of Unused Match
  645. DataArray[I+i+1].RawData = GBUdbUnknown; // records with empty data.
  646. }
  647. DataArray[I+iLastMatch].RawData = GBUdbMatchUnusedBit; // The last record gets a NULL index
  648. DataArray[I+iLastMatch+1].RawData = GBUdbUnknown; // and null data to terminate the list.
  649. return I; // Return the root index.
  650. }
  651. // doForAllRecords()
  652. // This method uses a recursive call to doAllAtNode()
  653. // doAllAtNode sweeps through each record in a node and processes any
  654. // node entries through the next level (calling itself) or directly if
  655. // the node is node3, or if it's pointing to a match record.
  656. void GBUdbDataset::updateWorkingIP(unsigned int& WIP, int OctetValue, int Level) { // Update the Working IP (WIP) at octet Level
  657. switch(Level) {
  658. case 0: { // For the node zero address,
  659. WIP = WIP & 0x00FFFFFF; // Mask out the node zero bits.
  660. OctetValue = OctetValue << 24; // Shift the octet value into position.
  661. WIP = WIP | OctetValue; // Or the octet value bits into place.
  662. break;
  663. }
  664. case 1: {
  665. WIP = WIP & 0xFF00FFFF; // Mask out the node zero bits.
  666. OctetValue = OctetValue << 16; // Shift the octet value into position.
  667. WIP = WIP | OctetValue; // Or the octet value bits into place.
  668. break;
  669. }
  670. case 2: {
  671. WIP = WIP & 0xFFFF00FF; // Mask out the node zero bits.
  672. OctetValue = OctetValue << 8; // Shift the octet value into position.
  673. WIP = WIP | OctetValue; // Or the octet value bits into place.
  674. break;
  675. }
  676. case 3: {
  677. WIP = WIP & 0xFFFFFF00; // Mask out the node zero bits.
  678. WIP = WIP | OctetValue; // Or the octet value bits into place.
  679. break;
  680. }
  681. }
  682. }
  683. //// Note about doAllAtNode(). The x.x.x.0 address is skipped on purpose. This
  684. //// is because all x.x.x.0 addresses are mapped to x.x.x.255. By skipping this
  685. //// address and starting at x.x.x.1 in any search, we do not need to check for
  686. //// x.x.x.0 ips that were remapped. They will simply appear at x.x.x.255.
  687. void GBUdbDataset::doAllAtNode( // Recursively call O with all valid records.
  688. GBUdbIndex I, // Input the node index.
  689. GBUdbOperator& O, // Input the Operator to call.
  690. int NodeLevel, // Input the NodeLevel.
  691. unsigned int WIP // Input the working IP.
  692. ) {
  693. int FirstI = (3 > NodeLevel) ? 0 : 1; // Skip any x.x.x.0 addresses.
  694. for(int i = FirstI; i < GBUdbRecordsPerNode; i++) { // Loop through the slots in this node.
  695. GBUdbIndex RecordIndex = DataArray[I + i].Index(); // Get the record index for this slot.
  696. if(GBUdbUnknown != RecordIndex) { // Check that this slot is not empty.
  697. updateWorkingIP(WIP, i, NodeLevel); // If we've got something then update the WIP.
  698. if(3 > NodeLevel) { // If we are working in rootward nodes:
  699. if(isMatch(RecordIndex)) { // Check for a match record. If we have one then
  700. unsigned int MatchIP = WIP & 0xFF000000; // build the IP for the match from the root
  701. MatchIP |= (DataArray[RecordIndex].RawData & 0x00FFFFFF); // of the WIP and the match IP data.
  702. O(MatchIP, MatchedData(RecordIndex)); // Then call the operator with the matched data.
  703. // If this slot is not a match record
  704. } else { // then it is a node address so we will
  705. doAllAtNode(RecordIndex, O, NodeLevel+1, WIP); // recurse to that node at a deeper level.
  706. }
  707. } else { // If we are working in the last node then
  708. O(WIP, DataArray[I + i]); // call the Operator with this IP & Record.
  709. } // All known data values in the last node are
  710. } // actual data records after all.
  711. }
  712. }
  713. void GBUdbDataset::doForAllRecords(GBUdbOperator& O) { // Call O for every valid record.
  714. unsigned int WorkingIP = 0; // A working IP for all levels to use.
  715. int NodeLevel = 0; // The Node level where we start.
  716. doAllAtNode(GBUdbRootNodeOffset, O, NodeLevel, WorkingIP); // Start at the root node, level 0.
  717. }
  718. //// GBUdb Implementations /////////////////////////////////////////////////////
  719. bool AlertFor(int count) { // True if an alert is needed.
  720. return ( // We want an alert whenever a count
  721. 0x00000001 == count || // hits any of these thresholds. Each
  722. 0x00000002 == count || // threshold is a new bit position
  723. 0x00000004 == count || // indicating that the count has
  724. 0x00000008 == count || // achieved a new power of 2. This
  725. 0x00000010 == count || // mechanism insures that newer IPs
  726. 0x00000020 == count || // get lots of attention while long
  727. 0x00000040 == count || // standing IPs still get visited
  728. 0x00000080 == count || // from time to time as their activity
  729. 0x00000100 == count || // continues.
  730. 0x00000200 == count ||
  731. 0x00000400 == count ||
  732. 0x00000800 == count ||
  733. 0x00001000 == count ||
  734. 0x00002000 == count ||
  735. 0x00004000 == count
  736. );
  737. }
  738. cd::RuntimeCheck GoodTimestampLength("GBUdb.cpp:getTimestamp snprintf(...) == CorrectTimestampLength");
  739. char* getTimestamp(char* TimestampBfr) { // Creates an ISO GMT timestamp.
  740. time_t rawtime; // Get a timer and
  741. tm * gmt; // a time structure.
  742. time(&rawtime); // Grab the current time and
  743. gmt=gmtime(&rawtime); // convert it to GMT.
  744. size_t l = snprintf(TimestampBfr,UTCBufferSize, "%04d%02d%02d%02d%02d%02d", // Format yyyymmddhhmmss
  745. gmt->tm_year+1900,
  746. gmt->tm_mon+1,
  747. gmt->tm_mday,
  748. gmt->tm_hour,
  749. gmt->tm_min,
  750. gmt->tm_sec
  751. );
  752. const size_t CorrectTimestampLength = 4+2+2+2+2+2;
  753. GoodTimestampLength(l == CorrectTimestampLength);
  754. return TimestampBfr;
  755. }
  756. char* getIPString(unsigned int IP, char* bfr) { // Converts an IP to a string.
  757. int a0, a1, a2, a3; // We will break the IP into 4 octets.
  758. const int LowOctetMask = 0x000000FF; // Mask for seeing the low octet.
  759. const int BitsInOneOctet = 8; // Number of bits to shift per octet.
  760. a3 = IP & LowOctetMask; IP >>= BitsInOneOctet; // Grab the a3 octet and shift the IP.
  761. a2 = IP & LowOctetMask; IP >>= BitsInOneOctet; // Grab the a2 octet and shift the IP.
  762. a1 = IP & LowOctetMask; IP >>= BitsInOneOctet; // Grab the a1 octet and shift the IP.
  763. a0 = IP & LowOctetMask; // Grab the final octet.
  764. sprintf(bfr,"%d.%d.%d.%d",a0,a1,a2,a3);
  765. return bfr;
  766. }
  767. void GBUdb::recordAlertFor(unsigned int IP, GBUdbRecord& R, unsigned int C) { // Record an alert event for R if needed.
  768. if(AlertFor(C)) { // If an alert is needed at this level...
  769. GBUdbAlert NewAlert; // Create a new alert record.
  770. NewAlert.IP = IP; // Assign the IP.
  771. NewAlert.R = R; // Assign the Record.
  772. cd::ScopeMutex JustMe(AlertsMutex); // Lock the alerts list mutex.
  773. MyAlerts.push_back(NewAlert); // Add our new alert to the list.
  774. }
  775. }
  776. GBUdbAlert::GBUdbAlert() : // Default constructor gets timestamp.
  777. IP(0) { // IP to zero, R will init to zero
  778. getTimestamp(UTC); // on it's own... Get timestamp.
  779. }
  780. std::string GBUdbAlert::toXML() { // Convert this alert to XML text
  781. std::stringstream Alert; // We'll use a stringstream.
  782. const char* FlagName = "ERROR"; // We will want the Flag as text.
  783. switch(R.Flag()) { // Switch on the Flag() value.
  784. case Good: { FlagName = "Good"; break; } // Convert each value to it's name.
  785. case Bad: { FlagName = "Bad"; break; }
  786. case Ugly: { FlagName = "Ugly"; break; }
  787. case Ignore: { FlagName = "Ignore"; break; }
  788. }
  789. char IPStringBfr[20]; // We need a buffer for our IP.
  790. Alert
  791. << "<gbu time=\'" << UTC // GBU alert + timestamp followed
  792. << "\' ip=\'" << getIPString(IP,IPStringBfr) // with the IP,
  793. << "\' t=\'" << FlagName // the type flag,
  794. << "\' b=\'" << R.Bad() // the bad count,
  795. << "\' g=\'" << R.Good() // and the good count.
  796. << "\'/>"; // That's the end.
  797. return Alert.str(); // Return the string.
  798. }
  799. //// Alert import and export - for sharing data between nodes.
  800. void GBUdb::GetAlerts(std::list<GBUdbAlert>& ListToFill) { // Get all current alerts & clear;
  801. ListToFill.clear(); // Clear out the list to fill.
  802. cd::ScopeMutex JustMe(AlertsMutex); // Lock for a moment.
  803. ListToFill = MyAlerts; // Copy our alerts to the new list.
  804. MyAlerts.clear(); // Clear our alerts.
  805. }
  806. // In order to allow gbudb nodes to interact without swamping their individuality,
  807. // the default mode for integrating thier data is to represent the remote peer's
  808. // influence on a logarithmic scale.
  809. unsigned int rescaleGBUdbCount(unsigned int C) { // Rescale count C for integration.
  810. if(C < 0x00000001) { return 0; } else // Log2, really, .. the short way.
  811. if(C < 0x00000002) { return 1; } else // How many significant bits are in
  812. if(C < 0x00000004) { return 2; } else // the number. Put another way, what
  813. if(C < 0x00000008) { return 3; } else // power of 2 is required to for
  814. if(C < 0x00000010) { return 4; } else // this number.
  815. if(C < 0x00000020) { return 5; } else
  816. if(C < 0x00000040) { return 6; } else
  817. if(C < 0x00000080) { return 7; } else
  818. if(C < 0x00000100) { return 8; } else
  819. if(C < 0x00000200) { return 9; } else
  820. if(C < 0x00000400) { return 10; } else
  821. if(C < 0x00000800) { return 11; } else
  822. if(C < 0x00001000) { return 12; } else
  823. if(C < 0x00002000) { return 13; } else
  824. if(C < 0x00004000) { return 14; } else
  825. return 15;
  826. }
  827. void GBUdb::ImportAlerts(std::list<GBUdbAlert>& PeerAlerts) { // Integrate peer alerts using log2.
  828. std::list<GBUdbAlert>::iterator iA;
  829. for(iA = PeerAlerts.begin(); iA != PeerAlerts.end(); iA++) { // Go through the list of PeerAlerts.
  830. GBUdbRecord R = (*iA).R; // Grab the Record in this alert.
  831. R.Bad(rescaleGBUdbCount(R.Bad())); // Adjust the bad and good counts
  832. R.Good(rescaleGBUdbCount(R.Good())); // for integration.
  833. adjustCounts((*iA).IP, R); // Adjust the local counts w/ R.
  834. }
  835. }
  836. //// doForAllRecords
  837. //// This method handles GBUdbOperators and their locking semantics.
  838. //// For full dataset locking the mutex is acquired before calling the
  839. //// dataset's doForAllRecords(). For record locking, the O passed to
  840. //// this method is wrapped in a record locking shim (below) and that is
  841. //// passed to the dataset. If None is selected then the Operator is
  842. //// passed to the dataset as is -- assuming that the Operator will handle
  843. //// it's own locking as needed.
  844. class GBUdbRecordLockingShim : public GBUdbOperator { // Record locking shim for doForAllRecords.
  845. private:
  846. GBUdbOperator& MyOperator; // Reference the Operator we will be servicing.
  847. cd::Mutex& MyMutex; // Reference the Mutex for the GBUdb we are in.
  848. public:
  849. GBUdbRecordLockingShim(GBUdbOperator& O, cd::Mutex& M) : // On construction we grab our critical pieces.
  850. MyOperator(O),
  851. MyMutex(M) {
  852. }
  853. GBUdbRecord& operator()(unsigned int IP, GBUdbRecord& R) { // When our operator() is called
  854. cd::ScopeMutex JustMe(MyMutex); // we lock the mutex in scope and
  855. return MyOperator(IP, R); // call the Operator we're servicing.
  856. } // When we leave scope we unlock (see above).
  857. };
  858. void GBUdb::doForAllRecords(GBUdbOperator& O, GBUdbLocking L) { // Calls O(IP, Record) w/Every record.
  859. if(Dataset == L) { // If we are locking for the Dataset, then
  860. cd::ScopeMutex JustMe(MyMutex); // we will lock the mutex during this
  861. MyDataset->doForAllRecords(O); // entire operation.
  862. } else
  863. if(Record == L) { // If we are locking per record then
  864. GBUdbRecordLockingShim X(O, MyMutex); // we create a record locking shim instance
  865. MyDataset->doForAllRecords(X); // and call O() through that.
  866. } else { // If locking is NOT enabled, then
  867. MyDataset->doForAllRecords(O); // we will call O() without any locking.
  868. }
  869. }
  870. //// The saveSnapshot() method allows us to save a snapshot of our dataset
  871. //// while keeping the mutex locked for as short a time as possible: Just long
  872. //// enough to make a copy of the dataset in RAM.
  873. void GBUdb::saveSnapshot() { // Saves a snapshot of the current db.
  874. GBUdbDataset* Snapshot = NULL; // We need a pointer for our snapshot.
  875. if(NULL == MyDataset) { // If we do not have a dataset to copy
  876. return; // then we simply return.
  877. } else { // If we do have a Dataset to copy...
  878. cd::ScopeMutex JustMe(MyMutex); // Lock the mutex and
  879. Snapshot = new GBUdbDataset(*MyDataset); // make a copy in memory.
  880. } // Then we can unlock the mutex.
  881. Snapshot->save(); // Then outside the mutex we can save.
  882. delete Snapshot; // Once saved we can delete the snapshot.
  883. PostsCounter = 0; // Reset the posts counter.
  884. }
  885. //// reduce()
  886. //// Using the doForAllRecords() functionality, this method reduces all counts
  887. //// by 2 thus renormalizing all records at lower count values. Unknown flagged
  888. //// records who's counts drop to zero will achieve the state GBUdbUnknown. As
  889. //// such, those values would not be carried over in a compress() operation.
  890. class ReduceAll : public GBUdbOperator { // To reduce the good and bad counts.
  891. public:
  892. GBUdbRecord& operator()(unsigned int IP, GBUdbRecord& R) { // Given each record,
  893. R.Good(R.Good() >> 1); // Reduce the Good count by half.
  894. R.Bad(R.Bad() >> 1); // Reduce the Bad count by half.
  895. return R; // Return the record.
  896. }
  897. } ReduceAllOperator;
  898. void GBUdb::reduce() { // Reduce all counts by half.
  899. doForAllRecords(ReduceAllOperator); // Call do for all records with the
  900. } // ReduceAllOperator.
  901. //// compress()
  902. //// Using the doForAllRecords() functionality, this method creates a temporary
  903. //// dataset, copies the existing data into that dataset except where the data
  904. //// is GBUdbUnknown, and then swaps the new dataset in place of the old.
  905. class CompressAll : public GBUdbOperator {
  906. private:
  907. GBUdbDataset* MyOldDataset; // Where do we find the old dataset.
  908. GBUdbDataset* MyNewDataset; // Where do we store our new dataset.
  909. int CountConverted;
  910. int CountDropped;
  911. public:
  912. // Note - There is no destructor. It is expected that the calling function
  913. // will extract the NewDataset and replace the OldDataset when the operation
  914. // has been successful.
  915. CompressAll(GBUdbDataset* OldDataset) : // Startup by
  916. MyOldDataset(OldDataset), // Grabbing the old dataset,
  917. MyNewDataset(NULL), // The new one isn't there yet.
  918. CountConverted(0), // Converted and Dropped
  919. CountDropped(0) { // Counts are zero.
  920. MyNewDataset = new GBUdbDataset(NULL); // Allocate a new Dataset.
  921. MyNewDataset->FileName(OldDataset->FileName()); // Set it's name the same as the old.
  922. } // We don't want to Load() it that way ;-)
  923. GBUdbRecord& operator()(unsigned int IP, GBUdbRecord& R) { // The ForAll Operator goes like this...
  924. if(GBUdbUnknown != R.RawData) { // If the record is not GBUdbUnknown then
  925. MyNewDataset->invokeRecord(IP).RawData = R.RawData; // invoke it and copy it's data.
  926. ++CountConverted; // Increment the converted count.
  927. } else { // If the record is GBUdbUnknown then
  928. ++CountDropped; // count it as dropped and forget it.
  929. }
  930. return R; // Return the record reference.
  931. }
  932. GBUdbDataset* Old() {return MyOldDataset;} // Here we can get our OldDataset pointer.
  933. GBUdbDataset* New() {return MyNewDataset;} // Here we can get our NewDataset pointer.
  934. int Converted() {return CountConverted;} // Here we can get the converted count.
  935. int Dropped() {return CountDropped;} // Here we can get the dropped count.
  936. };
  937. void GBUdb::compress() { // Remove any unknown records (reduced to zero).
  938. CompressAll BuildCompressedDataset(MyDataset); // Create a CompressAll operator for this dataset.
  939. cd::ScopeMutex Freeze(MyMutex); // Lock the mutex for the rest of this operation.
  940. MyDataset->doForAllRecords(BuildCompressedDataset); // Copy all of the active data records.
  941. MyDataset = BuildCompressedDataset.New(); // Put the new dataset in place.
  942. delete BuildCompressedDataset.Old(); // Delete the old dataset.
  943. } // All done, so we're unlocked.
  944. int GBUdb::readIgnoreList(const char* FileName) { // setIgnore for a list of IPs
  945. int IPCount = 0; // Keep track of the IPs we read.
  946. try { // Capture any exceptions.
  947. char IPLineBuffer[256]; // Create a line buffer.
  948. const int SafeBufferSize = sizeof(IPLineBuffer) - 1; // Safe size always leaves a NULL on the end.
  949. std::ifstream ListFile(FileName, std::ios::in); // Open up the list file.
  950. while(ListFile.good()) { // While we've got a good file (not eof)
  951. memset(IPLineBuffer, 0, sizeof(IPLineBuffer)); // Clear the buffer.
  952. ListFile.getline(IPLineBuffer, SafeBufferSize); // Read the line. (safely NULL terminated)
  953. // Now we have an IP on a line (in theory). We will parse
  954. // the ip and process any that parse correctly.
  955. // First eat anything that's not a digit.
  956. unsigned long IP = 0L; // We need an IP buffer.
  957. char* cursor = IPLineBuffer; // Start on the first byte.
  958. if('#' == *cursor) continue; // Lines that start with # are comments.
  959. while(0 < *cursor && isspace(*cursor)) ++cursor; // Eat any leading spaces.
  960. // First octet.
  961. if(!isdigit(*cursor)) continue; // If it's not a digit skip this line.
  962. if(255 < atoi(cursor)) continue; // If the octet is out of range skip!
  963. IP += atoi(cursor); IP <<= 8; // Grab the first int and shift it.
  964. while(isdigit(*cursor)) ++cursor; // Eat those digits.
  965. if('.'!=(*cursor)) continue; // If we don't find a dot skip this line.
  966. ++cursor; // If we do, skip the dot.
  967. // Second octet.
  968. if(!isdigit(*cursor)) continue; // If we're not at digit skip this line.
  969. if(255 < atoi(cursor)) continue; // If the octet is out of range skip!
  970. IP += atoi(cursor); IP <<= 8; // Grab the octet and shift things left.
  971. while(isdigit(*cursor)) ++cursor; // Eat those digits.
  972. if('.'!=(*cursor)) continue; // If we don't find a dot skip this line.
  973. ++cursor; // If we do, skip the dot.
  974. // Third octet.
  975. if(!isdigit(*cursor)) continue; // If we're not at digit skip this line.
  976. if(255 < atoi(cursor)) continue; // If the octet is out of range skip!
  977. IP += atoi(cursor); IP <<= 8; // Grab the octet and shift things left.
  978. while(isdigit(*cursor)) ++cursor; // Eat those digits.
  979. if('.'!=(*cursor)) continue; // If we don't find a dot skip this line.
  980. ++cursor; // If we do, skip the dot.
  981. // Last octet.
  982. if(!isdigit(*cursor)) continue; // If we're not at a digit skip this line.
  983. if(255 < atoi(cursor)) continue; // If the octet is out of range skip!
  984. IP += atoi(cursor); // Grab the octet. IP finished!
  985. setIgnore(IP); // Set the IP to Ignore.
  986. ++IPCount; // Bump the IP count.
  987. }
  988. ListFile.close();
  989. }
  990. catch(...) { } // If we have an exception we stop.
  991. return IPCount; // Always return the number of lines read.
  992. }