Source: util/memory-content-cache.js

  1. /**
  2. * Copyright (C) 2014-2016 Regents of the University of California.
  3. * @author: Jeff Thompson <jefft0@remap.ucla.edu>
  4. *
  5. * This program is free software: you can redistribute it and/or modify
  6. * it under the terms of the GNU Lesser General Public License as published by
  7. * the Free Software Foundation, either version 3 of the License, or
  8. * (at your option) any later version.
  9. *
  10. * This program is distributed in the hope that it will be useful,
  11. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13. * GNU Lesser General Public License for more details.
  14. *
  15. * You should have received a copy of the GNU Lesser General Public License
  16. * along with this program. If not, see <http://www.gnu.org/licenses/>.
  17. * A copy of the GNU Lesser General Public License is in the file COPYING.
  18. */
  19. /** @ignore */
  20. var Name = require('../name.js').Name; /** @ignore */
  21. var InterestFilter = require('../interest-filter.js').InterestFilter; /** @ignore */
  22. var ForwardingFlags = require('../forwarding-flags.js').ForwardingFlags; /** @ignore */
  23. var WireFormat = require('../encoding/wire-format.js').WireFormat; /** @ignore */
  24. var LOG = require('../log.js').Log.LOG;
  25. /**
  26. * A MemoryContentCache holds a set of Data packets and answers an Interest to
  27. * return the correct Data packet. The cache is periodically cleaned up to
  28. * remove each stale Data packet based on its FreshnessPeriod (if it has one).
  29. * @note This class is an experimental feature. See the API docs for more detail at
  30. * http://named-data.net/doc/ndn-ccl-api/memory-content-cache.html .
  31. *
  32. * Create a new MemoryContentCache to use the given Face.
  33. *
  34. * @param {Face} face The Face to use to call registerPrefix and
  35. * setInterestFilter, and which will call this object's OnInterest callback.
  36. * @param {number} cleanupIntervalMilliseconds (optional) The interval
  37. * in milliseconds between each check to clean up stale content in the cache. If
  38. * omitted, use a default of 1000 milliseconds. If this is a large number, then
  39. * effectively the stale content will not be removed from the cache.
  40. * @constructor
  41. */
  42. var MemoryContentCache = function MemoryContentCache
  43. (face, cleanupIntervalMilliseconds)
  44. {
  45. cleanupIntervalMilliseconds = (cleanupIntervalMilliseconds || 1000.0);
  46. this.face = face;
  47. this.cleanupIntervalMilliseconds = cleanupIntervalMilliseconds;
  48. this.nextCleanupTime = new Date().getTime() + cleanupIntervalMilliseconds;
  49. this.onDataNotFoundForPrefix = {}; /**< The map key is the prefix.toUri().
  50. The value is an OnInterest function. */
  51. this.interestFilterIdList = []; /**< elements are number */
  52. this.registeredPrefixIdList = []; /**< elements are number */
  53. this.noStaleTimeCache = []; /**< elements are MemoryContentCache.Content */
  54. this.staleTimeCache = []; /**< elements are MemoryContentCache.StaleTimeContent */
  55. //StaleTimeContent::Compare contentCompare_;
  56. this.emptyComponent = new Name.Component();
  57. this.pendingInterestTable = [];
  58. var thisMemoryContentCache = this;
  59. this.storePendingInterestCallback = function
  60. (localPrefix, localInterest, localFace, localInterestFilterId, localFilter) {
  61. thisMemoryContentCache.storePendingInterest(localInterest, localFace);
  62. };
  63. };
  64. exports.MemoryContentCache = MemoryContentCache;
  65. /**
  66. * Call registerPrefix on the Face given to the constructor so that this
  67. * MemoryContentCache will answer interests whose name has the prefix.
  68. * Alternatively, if the Face's registerPrefix has already been called,
  69. * then you can call this object's setInterestFilter.
  70. * @param {Name} prefix The Name for the prefix to register. This copies the Name.
  71. * @param {function} onRegisterFailed If this fails to register the prefix for
  72. * any reason, this calls onRegisterFailed(prefix) where prefix is the prefix
  73. * given to registerPrefix.
  74. * NOTE: The library will log any exceptions thrown by this callback, but for
  75. * better error handling the callback should catch and properly handle any
  76. * exceptions.
  77. * @param {function} onRegisterSuccess (optional) When this receives a success
  78. * message, this calls onRegisterSuccess[0](prefix, registeredPrefixId). If
  79. * onRegisterSuccess is [null] or omitted, this does not use it. (As a special
  80. * case, this optional parameter is supplied as an array of one function,
  81. * instead of just a function, in order to detect when it is used instead of the
  82. * following optional onDataNotFound function.)
  83. * NOTE: The library will log any exceptions thrown by this callback, but for
  84. * better error handling the callback should catch and properly handle any
  85. * exceptions.
  86. * @param {function} onDataNotFound (optional) If a data packet for an interest
  87. * is not found in the cache, this forwards the interest by calling
  88. * onDataNotFound(prefix, interest, face, interestFilterId, filter). Your
  89. * callback can find the Data packet for the interest and call
  90. * face.putData(data). If your callback cannot find the Data packet, it can
  91. * optionally call storePendingInterest(interest, face) to store the pending
  92. * interest in this object to be satisfied by a later call to add(data). If you
  93. * want to automatically store all pending interests, you can simply use
  94. * getStorePendingInterest() for onDataNotFound. If onDataNotFound is omitted or
  95. * null, this does not use it.
  96. * NOTE: The library will log any exceptions thrown by this callback, but for
  97. * better error handling the callback should catch and properly handle any
  98. * exceptions.
  99. * @param {ForwardingFlags} flags (optional) See Face.registerPrefix.
  100. * @param {WireFormat} wireFormat (optional) See Face.registerPrefix.
  101. */
  102. MemoryContentCache.prototype.registerPrefix = function
  103. (prefix, onRegisterFailed, onRegisterSuccess, onDataNotFound, flags, wireFormat)
  104. {
  105. var arg3 = onRegisterSuccess;
  106. var arg4 = onDataNotFound;
  107. var arg5 = flags;
  108. var arg6 = wireFormat;
  109. // arg3, arg4, arg5, arg6 may be:
  110. // [OnRegisterSuccess], OnDataNotFound, ForwardingFlags, WireFormat
  111. // [OnRegisterSuccess], OnDataNotFound, ForwardingFlags, null
  112. // [OnRegisterSuccess], OnDataNotFound, WireFormat, null
  113. // [OnRegisterSuccess], OnDataNotFound, null, null
  114. // [OnRegisterSuccess], ForwardingFlags, WireFormat, null
  115. // [OnRegisterSuccess], ForwardingFlags, null, null
  116. // [OnRegisterSuccess], WireFormat, null, null
  117. // [OnRegisterSuccess], null, null, null
  118. // OnDataNotFound, ForwardingFlags, WireFormat, null
  119. // OnDataNotFound, ForwardingFlags, null, null
  120. // OnDataNotFound, WireFormat, null, null
  121. // OnDataNotFound, null, null, null
  122. // ForwardingFlags, WireFormat, null, null
  123. // ForwardingFlags, null, null, null
  124. // WireFormat, null, null, null
  125. // null, null, null, null
  126. if (typeof arg3 === "object" && arg3.length === 1 &&
  127. typeof arg3[0] === "function")
  128. onRegisterSuccess = arg3[0];
  129. else
  130. onRegisterSuccess = null;
  131. if (typeof arg3 === "function")
  132. onDataNotFound = arg3;
  133. else if (typeof arg4 === "function")
  134. onDataNotFound = arg4;
  135. else
  136. onDataNotFound = null;
  137. if (arg3 instanceof ForwardingFlags)
  138. flags = arg3;
  139. else if (arg4 instanceof ForwardingFlags)
  140. flags = arg4;
  141. else if (arg5 instanceof ForwardingFlags)
  142. flags = arg5;
  143. else
  144. flags = new ForwardingFlags();
  145. if (arg3 instanceof WireFormat)
  146. wireFormat = arg3;
  147. else if (arg4 instanceof WireFormat)
  148. wireFormat = arg4;
  149. else if (arg5 instanceof WireFormat)
  150. wireFormat = arg5;
  151. else if (arg6 instanceof WireFormat)
  152. wireFormat = arg6;
  153. else
  154. wireFormat = WireFormat.getDefaultWireFormat();
  155. if (onDataNotFound)
  156. this.onDataNotFoundForPrefix[prefix.toUri()] = onDataNotFound;
  157. var registeredPrefixId = this.face.registerPrefix
  158. (prefix, this.onInterest.bind(this), onRegisterFailed, onRegisterSuccess,
  159. flags, wireFormat);
  160. this.registeredPrefixIdList.push(registeredPrefixId);
  161. };
  162. /**
  163. * Call setInterestFilter on the Face given to the constructor so that this
  164. * MemoryContentCache will answer interests whose name matches the filter.
  165. * There are two forms of setInterestFilter.
  166. * The first form uses the exact given InterestFilter:
  167. * setInterestFilter(filter, [onDataNotFound]).
  168. * The second form creates an InterestFilter from the given prefix Name:
  169. * setInterestFilter(prefix, [onDataNotFound]).
  170. * @param {InterestFilter} filter The InterestFilter with a prefix and optional
  171. * regex filter used to match the name of an incoming Interest. This makes a
  172. * copy of filter.
  173. * @param {Name} prefix The Name prefix used to match the name of an incoming
  174. * Interest.
  175. * @param {function} onDataNotFound (optional) If a data packet for an interest
  176. * is not found in the cache, this forwards the interest by calling
  177. * onDataNotFound(prefix, interest, face, interestFilterId, filter). Your
  178. * callback can find the Data packet for the interest and call
  179. * face.putData(data). If your callback cannot find the Data packet, it can
  180. * optionally call storePendingInterest(interest, face) to store the pending
  181. * interest in this object to be satisfied by a later call to add(data). If you
  182. * want to automatically store all pending interests, you can simply use
  183. * getStorePendingInterest() for onDataNotFound. If onDataNotFound is omitted or
  184. * null, this does not use it.
  185. * NOTE: The library will log any exceptions thrown by this callback, but for
  186. * better error handling the callback should catch and properly handle any
  187. * exceptions.
  188. */
  189. MemoryContentCache.prototype.setInterestFilter = function
  190. (filterOrPrefix, onDataNotFound)
  191. {
  192. if (onDataNotFound) {
  193. var prefix;
  194. if (typeof filterOrPrefix === 'object' && filterOrPrefix instanceof InterestFilter)
  195. prefix = filterOrPrefix.getPrefix();
  196. else
  197. prefix = filterOrPrefix;
  198. this.onDataNotFoundForPrefix[prefix.toUri()] = onDataNotFound;
  199. }
  200. var interestFilterId = this.face.setInterestFilter
  201. (filterOrPrefix, this.onInterest.bind(this));
  202. this.interestFilterIdList.push(interestFilterId);
  203. };
  204. /**
  205. * Call Face.unsetInterestFilter and Face.removeRegisteredPrefix for all the
  206. * prefixes given to the setInterestFilter and registerPrefix method on this
  207. * MemoryContentCache object so that it will not receive interests any more. You
  208. * can call this if you want to "shut down" this MemoryContentCache while your
  209. * application is still running.
  210. */
  211. MemoryContentCache.prototype.unregisterAll = function()
  212. {
  213. for (var i = 0; i < this.interestFilterIdList.length; ++i)
  214. this.face.unsetInterestFilter(this.interestFilterIdList[i]);
  215. this.interestFilterIdList = [];
  216. for (var i = 0; i < this.registeredPrefixIdList.length; ++i)
  217. this.face.removeRegisteredPrefix(this.registeredPrefixIdList[i]);
  218. this.registeredPrefixIdList = [];
  219. // Also clear each onDataNotFoundForPrefix given to registerPrefix.
  220. this.onDataNotFoundForPrefix = {};
  221. };
  222. /**
  223. * Add the Data packet to the cache so that it is available to use to answer
  224. * interests. If data.getMetaInfo().getFreshnessPeriod() is not null, set the
  225. * staleness time to now plus data.getMetaInfo().getFreshnessPeriod(), which is
  226. * checked during cleanup to remove stale content. This also checks if
  227. * cleanupIntervalMilliseconds milliseconds have passed and removes stale
  228. * content from the cache. After removing stale content, remove timed-out
  229. * pending interests from storePendingInterest(), then if the added Data packet
  230. * satisfies any interest, send it through the face and remove the interest
  231. * from the pending interest table.
  232. * @param {Data} data The Data packet object to put in the cache. This copies
  233. * the fields from the object.
  234. */
  235. MemoryContentCache.prototype.add = function(data)
  236. {
  237. this.doCleanup();
  238. if (data.getMetaInfo().getFreshnessPeriod() != null &&
  239. data.getMetaInfo().getFreshnessPeriod() >= 0.0) {
  240. // The content will go stale, so use staleTimeCache.
  241. var content = new MemoryContentCache.StaleTimeContent(data);
  242. // Insert into staleTimeCache, sorted on content.staleTimeMilliseconds.
  243. // Search from the back since we expect it to go there.
  244. var i = this.staleTimeCache.length - 1;
  245. while (i >= 0) {
  246. if (this.staleTimeCache[i].staleTimeMilliseconds <= content.staleTimeMilliseconds)
  247. break;
  248. --i;
  249. }
  250. // Element i is the greatest less than or equal to
  251. // content.staleTimeMilliseconds, so insert after it.
  252. this.staleTimeCache.splice(i + 1, 0, content);
  253. }
  254. else
  255. // The data does not go stale, so use noStaleTimeCache.
  256. this.noStaleTimeCache.push(new MemoryContentCache.Content(data));
  257. // Remove timed-out interests and check if the data packet matches any pending
  258. // interest.
  259. // Go backwards through the list so we can erase entries.
  260. var nowMilliseconds = new Date().getTime();
  261. for (var i = this.pendingInterestTable.length - 1; i >= 0; --i) {
  262. if (this.pendingInterestTable[i].isTimedOut(nowMilliseconds)) {
  263. this.pendingInterestTable.splice(i, 1);
  264. continue;
  265. }
  266. if (this.pendingInterestTable[i].getInterest().matchesName(data.getName())) {
  267. try {
  268. // Send to the same face from the original call to onInterest.
  269. // wireEncode returns the cached encoding if available.
  270. this.pendingInterestTable[i].getFace().send(data.wireEncode().buf());
  271. }
  272. catch (ex) {
  273. if (LOG > 0)
  274. console.log("" + ex);
  275. return;
  276. }
  277. // The pending interest is satisfied, so remove it.
  278. this.pendingInterestTable.splice(i, 1);
  279. }
  280. }
  281. };
  282. /**
  283. * Store an interest from an OnInterest callback in the internal pending
  284. * interest table (normally because there is no Data packet available yet to
  285. * satisfy the interest). add(data) will check if the added Data packet
  286. * satisfies any pending interest and send it through the face.
  287. * @param {Interest} interest The Interest for which we don't have a Data packet
  288. * yet. You should not modify the interest after calling this.
  289. * @param {Face} face The Face with the connection which received
  290. * the interest. This comes from the OnInterest callback.
  291. */
  292. MemoryContentCache.prototype.storePendingInterest = function(interest, face)
  293. {
  294. this.pendingInterestTable.push
  295. (new MemoryContentCache.PendingInterest(interest, face));
  296. };
  297. /**
  298. * Return a callback to use for onDataNotFound in registerPrefix which simply
  299. * calls storePendingInterest() to store the interest that doesn't match a
  300. * Data packet. add(data) will check if the added Data packet satisfies any
  301. * pending interest and send it.
  302. * @returns {function} A callback to use for onDataNotFound in registerPrefix().
  303. */
  304. MemoryContentCache.prototype.getStorePendingInterest = function()
  305. {
  306. return this.storePendingInterestCallback;
  307. };
  308. /**
  309. * This is the OnInterest callback which is called when the library receives
  310. * an interest whose name has the prefix given to registerPrefix. First check
  311. * if cleanupIntervalMilliseconds milliseconds have passed and remove stale
  312. * content from the cache. Then search the cache for the Data packet, matching
  313. * any interest selectors including ChildSelector, and send the Data packet
  314. * to the face. If no matching Data packet is in the cache, call
  315. * the callback in onDataNotFoundForPrefix (if defined).
  316. */
  317. MemoryContentCache.prototype.onInterest = function
  318. (prefix, interest, face, interestFilterId, filter)
  319. {
  320. this.doCleanup();
  321. var selectedComponent = 0;
  322. var selectedEncoding = null;
  323. // We need to iterate over both arrays.
  324. var totalSize = this.staleTimeCache.length + this.noStaleTimeCache.length;
  325. for (var i = 0; i < totalSize; ++i) {
  326. var content;
  327. if (i < this.staleTimeCache.length)
  328. content = this.staleTimeCache[i];
  329. else
  330. // We have iterated over the first array. Get from the second.
  331. content = this.noStaleTimeCache[i - this.staleTimeCache.length];
  332. if (interest.matchesName(content.getName())) {
  333. if (interest.getChildSelector() < 0) {
  334. // No child selector, so send the first match that we have found.
  335. face.send(content.getDataEncoding());
  336. return;
  337. }
  338. else {
  339. // Update selectedEncoding based on the child selector.
  340. var component;
  341. if (content.getName().size() > interest.getName().size())
  342. component = content.getName().get(interest.getName().size());
  343. else
  344. component = this.emptyComponent;
  345. var gotBetterMatch = false;
  346. if (selectedEncoding === null)
  347. // Save the first match.
  348. gotBetterMatch = true;
  349. else {
  350. if (interest.getChildSelector() == 0) {
  351. // Leftmost child.
  352. if (component.compare(selectedComponent) < 0)
  353. gotBetterMatch = true;
  354. }
  355. else {
  356. // Rightmost child.
  357. if (component.compare(selectedComponent) > 0)
  358. gotBetterMatch = true;
  359. }
  360. }
  361. if (gotBetterMatch) {
  362. selectedComponent = component;
  363. selectedEncoding = content.getDataEncoding();
  364. }
  365. }
  366. }
  367. }
  368. if (selectedEncoding !== null)
  369. // We found the leftmost or rightmost child.
  370. face.send(selectedEncoding);
  371. else {
  372. // Call the onDataNotFound callback (if defined).
  373. var onDataNotFound = this.onDataNotFoundForPrefix[prefix.toUri()];
  374. if (onDataNotFound)
  375. onDataNotFound(prefix, interest, face, interestFilterId, filter);
  376. }
  377. };
  378. /**
  379. * Check if now is greater than nextCleanupTime and, if so, remove stale
  380. * content from staleTimeCache and reset nextCleanupTime based on
  381. * cleanupIntervalMilliseconds. Since add(Data) does a sorted insert into
  382. * staleTimeCache, the check for stale data is quick and does not require
  383. * searching the entire staleTimeCache.
  384. */
  385. MemoryContentCache.prototype.doCleanup = function()
  386. {
  387. var now = new Date().getTime();
  388. if (now >= this.nextCleanupTime) {
  389. // staleTimeCache is sorted on staleTimeMilliseconds, so we only need to
  390. // erase the stale entries at the front, then quit.
  391. while (this.staleTimeCache.length > 0 && this.staleTimeCache[0].isStale(now))
  392. this.staleTimeCache.shift();
  393. this.nextCleanupTime = now + this.cleanupIntervalMilliseconds;
  394. }
  395. };
  396. /**
  397. * Content is a private class to hold the name and encoding for each entry
  398. * in the cache. This base class is for a Data packet without a FreshnessPeriod.
  399. *
  400. * Create a new Content entry to hold data's name and wire encoding.
  401. * @param {Data} data The Data packet whose name and wire encoding are copied.
  402. */
  403. MemoryContentCache.Content = function MemoryContentCacheContent(data)
  404. {
  405. // Allow an undefined data so that StaleTimeContent can set the prototype.
  406. if (data) {
  407. // Copy the name.
  408. this.name = new Name(data.getName());
  409. // wireEncode returns the cached encoding if available.
  410. this.dataEncoding = data.wireEncode().buf();
  411. }
  412. };
  413. MemoryContentCache.Content.prototype.getName = function() { return this.name; };
  414. MemoryContentCache.Content.prototype.getDataEncoding = function() { return this.dataEncoding; };
  415. /**
  416. * StaleTimeContent extends Content to include the staleTimeMilliseconds for
  417. * when this entry should be cleaned up from the cache.
  418. *
  419. * Create a new StaleTimeContent to hold data's name and wire encoding as well
  420. * as the staleTimeMilliseconds which is now plus
  421. * data.getMetaInfo().getFreshnessPeriod().
  422. * @param {Data} data The Data packet whose name and wire encoding are copied.
  423. */
  424. MemoryContentCache.StaleTimeContent = function MemoryContentCacheStaleTimeContent
  425. (data)
  426. {
  427. // Call the base constructor.
  428. MemoryContentCache.Content.call(this, data);
  429. // Set up staleTimeMilliseconds which is The time when the content becomse
  430. // stale in milliseconds according to new Date().getTime().
  431. this.staleTimeMilliseconds = new Date().getTime() +
  432. data.getMetaInfo().getFreshnessPeriod();
  433. };
  434. MemoryContentCache.StaleTimeContent.prototype = new MemoryContentCache.Content();
  435. MemoryContentCache.StaleTimeContent.prototype.name = "StaleTimeContent";
  436. /**
  437. * Check if this content is stale.
  438. * @param {number} nowMilliseconds The current time in milliseconds from
  439. * new Date().getTime().
  440. * @returns {boolean} True if this content is stale, otherwise false.
  441. */
  442. MemoryContentCache.StaleTimeContent.prototype.isStale = function(nowMilliseconds)
  443. {
  444. return this.staleTimeMilliseconds <= nowMilliseconds;
  445. };
  446. /**
  447. * A PendingInterest holds an interest which onInterest received but could
  448. * not satisfy. When we add a new data packet to the cache, we will also check
  449. * if it satisfies a pending interest.
  450. */
  451. MemoryContentCache.PendingInterest = function MemoryContentCachePendingInterest
  452. (interest, face)
  453. {
  454. this.interest = interest;
  455. this.face = face;
  456. if (this.interest.getInterestLifetimeMilliseconds() >= 0.0)
  457. this.timeoutMilliseconds = (new Date()).getTime() +
  458. this.interest.getInterestLifetimeMilliseconds();
  459. else
  460. this.timeoutMilliseconds = -1.0;
  461. };
  462. /**
  463. * Return the interest given to the constructor.
  464. */
  465. MemoryContentCache.PendingInterest.prototype.getInterest = function()
  466. {
  467. return this.interest;
  468. };
  469. /**
  470. * Return the face given to the constructor.
  471. */
  472. MemoryContentCache.PendingInterest.prototype.getFace = function()
  473. {
  474. return this.face;
  475. };
  476. /**
  477. * Check if this interest is timed out.
  478. * @param {number} nowMilliseconds The current time in milliseconds from
  479. * new Date().getTime().
  480. * @returns {boolean} True if this interest timed out, otherwise false.
  481. */
  482. MemoryContentCache.PendingInterest.prototype.isTimedOut = function(nowMilliseconds)
  483. {
  484. return this.timeoutTimeMilliseconds >= 0.0 &&
  485. nowMilliseconds >= this.timeoutTimeMilliseconds;
  486. };