util: Support MustBeFresh processing in InMemoryStorage
Change-Id: I8e8e647d7673e4e0fe8dd1c5025fbc8e5e524c70
Refs: #3274
diff --git a/src/util/in-memory-storage-entry.cpp b/src/util/in-memory-storage-entry.cpp
index ae34ba2..c0f5e59 100644
--- a/src/util/in-memory-storage-entry.cpp
+++ b/src/util/in-memory-storage-entry.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -24,16 +24,35 @@
namespace ndn {
namespace util {
+InMemoryStorageEntry::InMemoryStorageEntry()
+ : m_isFresh(true)
+{
+}
+
void
InMemoryStorageEntry::release()
{
m_dataPacket.reset();
+ m_markStaleEventId.reset();
}
void
InMemoryStorageEntry::setData(const Data& data)
{
m_dataPacket = data.shared_from_this();
+ m_isFresh = true;
+}
+
+void
+InMemoryStorageEntry::setMarkStaleEventId(unique_ptr<scheduler::ScopedEventId>&& markStaleEventId)
+{
+ m_markStaleEventId = std::move(markStaleEventId);
+}
+
+void
+InMemoryStorageEntry::markStale()
+{
+ m_isFresh = false;
}
} // namespace util
diff --git a/src/util/in-memory-storage-entry.hpp b/src/util/in-memory-storage-entry.hpp
index 8950b01..6e77b3d 100644
--- a/src/util/in-memory-storage-entry.hpp
+++ b/src/util/in-memory-storage-entry.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -25,6 +25,7 @@
#include "../common.hpp"
#include "../interest.hpp"
#include "../data.hpp"
+#include "scheduler-scoped-event-id.hpp"
namespace ndn {
namespace util {
@@ -34,6 +35,11 @@
class InMemoryStorageEntry : noncopyable
{
public:
+
+ /** @brief Create an entry
+ */
+ InMemoryStorageEntry();
+
/** @brief Releases reference counts on shared objects
*/
void
@@ -67,12 +73,35 @@
/** @brief Changes the content of in-memory storage entry
+ *
+ * This method also allows data to satisfy Interest with MustBeFresh
*/
void
setData(const Data& data);
+ /** @brief Set eventId for the markStale event.
+ */
+ void
+ setMarkStaleEventId(unique_ptr<scheduler::ScopedEventId>&& eventId);
+
+ /** @brief Disable the data from satisfying interest with MustBeFresh
+ */
+ void
+ markStale();
+
+ /** @brief Check if the data can satisfy an interest with MustBeFresh
+ */
+ bool
+ isFresh()
+ {
+ return m_isFresh;
+ }
+
private:
shared_ptr<const Data> m_dataPacket;
+
+ bool m_isFresh;
+ unique_ptr<scheduler::ScopedEventId> m_markStaleEventId;
};
} // namespace util
diff --git a/src/util/in-memory-storage-fifo.cpp b/src/util/in-memory-storage-fifo.cpp
index 91cc7b4..5906d97 100644
--- a/src/util/in-memory-storage-fifo.cpp
+++ b/src/util/in-memory-storage-fifo.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -29,6 +29,11 @@
{
}
+InMemoryStorageFifo::InMemoryStorageFifo(boost::asio::io_service& ioService, size_t limit)
+ : InMemoryStorage(ioService, limit)
+{
+}
+
InMemoryStorageFifo::~InMemoryStorageFifo()
{
}
diff --git a/src/util/in-memory-storage-fifo.hpp b/src/util/in-memory-storage-fifo.hpp
index fc83fe5..4d522a4 100644
--- a/src/util/in-memory-storage-fifo.hpp
+++ b/src/util/in-memory-storage-fifo.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -40,6 +40,9 @@
explicit
InMemoryStorageFifo(size_t limit = 10);
+ explicit
+ InMemoryStorageFifo(boost::asio::io_service& ioService, size_t limit = 10);
+
virtual
~InMemoryStorageFifo();
diff --git a/src/util/in-memory-storage-lfu.cpp b/src/util/in-memory-storage-lfu.cpp
index 0596145..0450c6c 100644
--- a/src/util/in-memory-storage-lfu.cpp
+++ b/src/util/in-memory-storage-lfu.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -29,6 +29,11 @@
{
}
+InMemoryStorageLfu::InMemoryStorageLfu(boost::asio::io_service& ioService, size_t limit)
+ : InMemoryStorage(ioService, limit)
+{
+}
+
InMemoryStorageLfu::~InMemoryStorageLfu()
{
}
diff --git a/src/util/in-memory-storage-lfu.hpp b/src/util/in-memory-storage-lfu.hpp
index ac8a02d..f02079e 100644
--- a/src/util/in-memory-storage-lfu.hpp
+++ b/src/util/in-memory-storage-lfu.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -43,6 +43,9 @@
explicit
InMemoryStorageLfu(size_t limit = 10);
+ explicit
+ InMemoryStorageLfu(boost::asio::io_service& ioService, size_t limit = 10);
+
virtual
~InMemoryStorageLfu();
diff --git a/src/util/in-memory-storage-lru.cpp b/src/util/in-memory-storage-lru.cpp
index b823b2b..2a50644 100644
--- a/src/util/in-memory-storage-lru.cpp
+++ b/src/util/in-memory-storage-lru.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -29,6 +29,12 @@
{
}
+InMemoryStorageLru::InMemoryStorageLru(boost::asio::io_service& ioService,
+ size_t limit)
+ : InMemoryStorage(ioService, limit)
+{
+}
+
InMemoryStorageLru::~InMemoryStorageLru()
{
}
diff --git a/src/util/in-memory-storage-lru.hpp b/src/util/in-memory-storage-lru.hpp
index bde0de4..8d7f852 100644
--- a/src/util/in-memory-storage-lru.hpp
+++ b/src/util/in-memory-storage-lru.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -42,6 +42,8 @@
explicit
InMemoryStorageLru(size_t limit = 10);
+ InMemoryStorageLru(boost::asio::io_service& ioService, size_t limit = 10);
+
virtual
~InMemoryStorageLru();
diff --git a/src/util/in-memory-storage-persistent.cpp b/src/util/in-memory-storage-persistent.cpp
index 687a91f..613aa7b 100644
--- a/src/util/in-memory-storage-persistent.cpp
+++ b/src/util/in-memory-storage-persistent.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -29,6 +29,11 @@
{
}
+InMemoryStoragePersistent::InMemoryStoragePersistent(boost::asio::io_service& ioService)
+ : InMemoryStorage(ioService)
+{
+}
+
InMemoryStoragePersistent::~InMemoryStoragePersistent()
{
}
diff --git a/src/util/in-memory-storage-persistent.hpp b/src/util/in-memory-storage-persistent.hpp
index cd9faa3..3cd12ef 100644
--- a/src/util/in-memory-storage-persistent.hpp
+++ b/src/util/in-memory-storage-persistent.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -33,9 +33,11 @@
class InMemoryStoragePersistent : public InMemoryStorage
{
public:
- explicit
InMemoryStoragePersistent();
+ explicit
+ InMemoryStoragePersistent(boost::asio::io_service& ioService);
+
virtual
~InMemoryStoragePersistent();
diff --git a/src/util/in-memory-storage.cpp b/src/util/in-memory-storage.cpp
index 4a19660..7d3584c 100644
--- a/src/util/in-memory-storage.cpp
+++ b/src/util/in-memory-storage.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2015 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -21,6 +21,7 @@
#include "in-memory-storage.hpp"
#include "in-memory-storage-entry.hpp"
+#include "util/backports.hpp"
#include "crypto.hpp"
@@ -29,6 +30,9 @@
namespace ndn {
namespace util {
+const time::milliseconds InMemoryStorage::INFINITE_WINDOW(-1);
+const time::milliseconds InMemoryStorage::ZERO_WINDOW(0);
+
InMemoryStorage::const_iterator::const_iterator(const Data* ptr, const Cache* cache,
Cache::index<byFullName>::type::iterator it)
: m_ptr(ptr)
@@ -87,10 +91,24 @@
: m_limit(limit)
, m_nPackets(0)
{
+ init();
+}
+
+InMemoryStorage::InMemoryStorage(boost::asio::io_service& ioService, size_t limit)
+ : m_limit(limit)
+ , m_nPackets(0)
+{
+ m_scheduler = make_unique<Scheduler>(ioService);
+ init();
+}
+
+void
+InMemoryStorage::init()
+{
// TODO consider a more suitable initial value
m_capacity = 10;
- if (limit != std::numeric_limits<size_t>::max() && m_capacity > m_limit) {
+ if (m_limit != std::numeric_limits<size_t>::max() && m_capacity > m_limit) {
m_capacity = m_limit;
}
@@ -146,7 +164,7 @@
}
void
-InMemoryStorage::insert(const Data& data)
+InMemoryStorage::insert(const Data& data, const time::milliseconds& mustBeFreshProcessingWindow)
{
//check if identical Data/Name already exists
Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().find(data.getFullName());
@@ -173,6 +191,12 @@
m_freeEntries.pop();
m_nPackets++;
entry->setData(data);
+ if (m_scheduler != nullptr && mustBeFreshProcessingWindow > ZERO_WINDOW) {
+ auto eventId = make_unique<scheduler::ScopedEventId>(*m_scheduler);
+ *eventId = m_scheduler->scheduleEvent(mustBeFreshProcessingWindow,
+ bind(&InMemoryStorageEntry::markStale, entry));
+ entry->setMarkStaleEventId(std::move(eventId));
+ }
m_cache.insert(entry);
//let derived class do something with the entry
@@ -218,7 +242,6 @@
return shared_ptr<const Data>();
}
-
//to locate the element that has a just smaller name than the interest's
if (it != m_cache.get<byFullName>().begin())
it--;
@@ -234,6 +257,17 @@
}
}
+InMemoryStorage::Cache::index<InMemoryStorage::byFullName>::type::iterator
+InMemoryStorage::findNextFresh(Cache::index<byFullName>::type::iterator it) const
+{
+ for (; it != m_cache.get<byFullName>().end(); it++) {
+ if ((*it)->isFresh())
+ return it;
+ }
+
+ return it;
+}
+
InMemoryStorageEntry*
InMemoryStorage::selectChild(const Interest& interest,
Cache::index<byFullName>::type::iterator startingPoint) const
@@ -248,6 +282,14 @@
bool hasLeftmostSelector = (interest.getChildSelector() <= 0);
bool hasRightmostSelector = !hasLeftmostSelector;
+ // filter out "stale" data
+ if (interest.getMustBeFresh())
+ startingPoint = findNextFresh(startingPoint);
+
+ if (startingPoint == m_cache.get<byFullName>().end()) {
+ return nullptr;
+ }
+
if (hasLeftmostSelector)
{
if (interest.matchesData((*startingPoint)->getData()))
@@ -266,6 +308,9 @@
while (true)
{
++rightmostCandidate;
+ // filter out "stale" data
+ if (interest.getMustBeFresh())
+ rightmostCandidate = findNextFresh(rightmostCandidate);
bool isInBoundaries = (rightmostCandidate != m_cache.get<byFullName>().end());
bool isInPrefix = false;
diff --git a/src/util/in-memory-storage.hpp b/src/util/in-memory-storage.hpp
index 5e800c2..bdc3962 100644
--- a/src/util/in-memory-storage.hpp
+++ b/src/util/in-memory-storage.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -25,7 +25,7 @@
#include "../common.hpp"
#include "../interest.hpp"
#include "../data.hpp"
-
+#include "scheduler.hpp"
#include "in-memory-storage-entry.hpp"
#include <boost/multi_index/member.hpp>
@@ -109,9 +109,19 @@
}
};
+ /** @brief Create a InMemoryStorage with up to @p limit entries
+ * The InMemoryStorage created through this method will ignore MustBeFresh in interest processing
+ */
explicit
InMemoryStorage(size_t limit = std::numeric_limits<size_t>::max());
+ /** @brief Create a InMemoryStorage with up to @p limit entries
+ * The InMemoryStorage created through this method will handle MustBeFresh in interest processing
+ */
+ explicit
+ InMemoryStorage(boost::asio::io_service& ioService,
+ size_t limit = std::numeric_limits<size_t>::max());
+
/** @note Please make sure to implement it to free m_freeEntries and evict
* all items in the derived class for anybody who wishes to inherit this class
*/
@@ -120,6 +130,10 @@
/** @brief Inserts a Data packet
*
+ * @param data the packet to insert
+ * @param mustBeFreshProcessingWindow Beyond this time period after the data is inserted, the
+ * data can only be used to answer interest without MustBeFresh selector.
+ *
* @note Packets are considered duplicate if the name with implicit digest matches.
* The new Data packet with the identical name, but a different payload
* will be placed in the in-memory storage.
@@ -127,7 +141,7 @@
* @note It will invoke afterInsert(shared_ptr<InMemoryStorageEntry>).
*/
void
- insert(const Data& data);
+ insert(const Data& data, const time::milliseconds& mustBeFreshProcessingWindow = INFINITE_WINDOW);
/** @brief Finds the best match Data for an Interest
*
@@ -294,6 +308,24 @@
selectChild(const Interest& interest,
Cache::index<byFullName>::type::iterator startingPoint) const;
+ /** @brief Get the next iterator (include startingPoint) that satisfies MustBeFresh requirement
+ *
+ * @param startingPoint The iterator to start with.
+ * @return The next qualified iterator
+ */
+ Cache::index<byFullName>::type::iterator
+ findNextFresh(Cache::index<byFullName>::type::iterator startingPoint) const;
+
+private:
+ void
+ init();
+
+public:
+ static const time::milliseconds INFINITE_WINDOW;
+
+private:
+ static const time::milliseconds ZERO_WINDOW;
+
private:
Cache m_cache;
/// user defined maximum capacity of the in-memory storage in packets
@@ -304,6 +336,8 @@
size_t m_nPackets;
/// memory pool
std::stack<InMemoryStorageEntry*> m_freeEntries;
+ /// scheduler
+ unique_ptr<Scheduler> m_scheduler;
};
} // namespace util
diff --git a/tests/unit-tests/util/test-in-memory-storage-common.cpp b/tests/unit-tests/util/test-in-memory-storage-common.cpp
index f2c1b9f..ea78f29 100644
--- a/tests/unit-tests/util/test-in-memory-storage-common.cpp
+++ b/tests/unit-tests/util/test-in-memory-storage-common.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2015 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -27,6 +27,7 @@
#include "boost-test.hpp"
#include "../make-interest-data.hpp"
+#include "../unit-test-time-fixture.hpp"
#include <boost/mpl/list.hpp>
@@ -631,7 +632,7 @@
typedef boost::mpl::list<InMemoryStorageFifo, InMemoryStorageLfu, InMemoryStorageLru>
InMemoryStoragesLimited;
-BOOST_AUTO_TEST_CASE_TEMPLATE(setCapacity, T, InMemoryStoragesLimited)
+BOOST_AUTO_TEST_CASE_TEMPLATE(SetCapacity, T, InMemoryStoragesLimited)
{
T ims;
@@ -700,18 +701,24 @@
///as Find function is implemented at the base case, therefore testing for one derived class is
///sufficient for all
-class FindFixture
+class FindFixture : public ndn::tests::UnitTestTimeFixture
{
protected:
+ FindFixture()
+ : m_ims(io)
+ {
+ }
+
Name
- insert(uint32_t id, const Name& name)
+ insert(uint32_t id, const Name& name,
+ const time::milliseconds& freshWindow = InMemoryStorage::INFINITE_WINDOW)
{
shared_ptr<Data> data = makeData(name);
data->setFreshnessPeriod(time::milliseconds(99999));
data->setContent(reinterpret_cast<const uint8_t*>(&id), sizeof(id));
signData(data);
- m_ims.insert(*data);
+ m_ims.insert(*data, freshWindow);
return data->getFullName();
}
@@ -975,6 +982,78 @@
BOOST_CHECK_EQUAL(find(), 1);
}
+BOOST_AUTO_TEST_CASE(MustBeFresh)
+{
+ Name data1Name = insert(1, "ndn:/A/1", time::milliseconds(500));
+ insert(2, "ndn:/A/2", time::milliseconds(2500));
+ insert(3, "ndn:/A/3", time::milliseconds(3500));
+ insert(4, "ndn:/A/4", time::milliseconds(1500));
+
+ // @0s, all Data are fresh
+ startInterest("ndn:/A/1")
+ .setMustBeFresh(true);
+ BOOST_CHECK_EQUAL(find(), 1);
+
+ startInterest("ndn:/A/1")
+ .setMustBeFresh(false);
+ BOOST_CHECK_EQUAL(find(), 1);
+
+ startInterest("ndn:/A")
+ .setMustBeFresh(true)
+ .setChildSelector(0);
+ BOOST_CHECK_EQUAL(find(), 1);
+
+ startInterest("ndn:/A")
+ .setMustBeFresh(true)
+ .setChildSelector(1);
+ BOOST_CHECK_EQUAL(find(), 4);
+
+ advanceClocks(time::milliseconds(1000));
+ // @1s, /A/1 is stale
+ startInterest("ndn:/A/1")
+ .setMustBeFresh(true);
+ BOOST_CHECK_EQUAL(find(), 0);
+ startInterest("ndn:/A/1")
+ .setMustBeFresh(false);
+ BOOST_CHECK_EQUAL(find(), 1);
+
+ // MustBeFresh is ignored when full Name is specified
+ startInterest(data1Name)
+ .setMustBeFresh(true);
+ BOOST_CHECK_EQUAL(find(), 1);
+
+ startInterest("ndn:/A")
+ .setMustBeFresh(true)
+ .setChildSelector(0);
+ BOOST_CHECK_EQUAL(find(), 2);
+ startInterest("ndn:/A")
+ .setMustBeFresh(false)
+ .setChildSelector(0);
+ BOOST_CHECK_EQUAL(find(), 1);
+
+ advanceClocks(time::milliseconds(1000));
+ // @2s, /A/1 and /A/4 are stale
+ startInterest("ndn:/A")
+ .setMustBeFresh(true)
+ .setChildSelector(1);
+ BOOST_CHECK_EQUAL(find(), 3);
+ startInterest("ndn:/A")
+ .setMustBeFresh(false)
+ .setChildSelector(1);
+ BOOST_CHECK_EQUAL(find(), 4);
+
+ advanceClocks(time::milliseconds(2000));
+ // @4s, all Data are stale
+ startInterest("ndn:/A")
+ .setMustBeFresh(true)
+ .setChildSelector(0);
+ BOOST_CHECK_EQUAL(find(), 0);
+ startInterest("ndn:/A")
+ .setMustBeFresh(true)
+ .setChildSelector(1);
+ BOOST_CHECK_EQUAL(find(), 0);
+}
+
BOOST_AUTO_TEST_SUITE_END() // Find
BOOST_AUTO_TEST_SUITE_END() // Common
BOOST_AUTO_TEST_SUITE_END() // UtilInMemoryStorage