blob: 5e3b79d14d5d2d366473e2678befaddb2e35c60c [file] [log] [blame]
Junxiao Shi0fcb41e2014-01-24 10:29:43 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
Alexander Afanasyev9bcbc7c2014-04-06 19:37:37 -07003 * Copyright (c) 2014 Regents of the University of California,
4 * Arizona Board of Regents,
5 * Colorado State University,
6 * University Pierre & Marie Curie, Sorbonne University,
7 * Washington University in St. Louis,
8 * Beijing Institute of Technology
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -08009 *
Alexander Afanasyev9bcbc7c2014-04-06 19:37:37 -070010 * This file is part of NFD (Named Data Networking Forwarding Daemon).
11 * See AUTHORS.md for complete list of NFD authors and contributors.
12 *
13 * NFD is free software: you can redistribute it and/or modify it under the terms
14 * of the GNU General Public License as published by the Free Software Foundation,
15 * either version 3 of the License, or (at your option) any later version.
16 *
17 * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
18 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
19 * PURPOSE. See the GNU General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License along with
22 * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
23 *
24 * \author Ilya Moiseenko <iliamo@ucla.edu>
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070025 */
26
Alexander Afanasyev613e2a92014-04-15 13:36:58 -070027#ifndef NFD_DAEMON_TABLE_CS_HPP
28#define NFD_DAEMON_TABLE_CS_HPP
Alexander Afanasyevb927a3a2014-01-24 10:41:47 -080029
30#include "common.hpp"
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070031#include "cs-entry.hpp"
Alexander Afanasyevb927a3a2014-01-24 10:41:47 -080032
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040033#include <boost/multi_index/member.hpp>
34#include <boost/multi_index_container.hpp>
35#include <boost/multi_index/ordered_index.hpp>
36#include <boost/multi_index/sequenced_index.hpp>
37#include <boost/multi_index/identity.hpp>
38
Davide Pesavento52a18f92014-04-10 00:55:01 +020039#include <queue>
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040040
Alexander Afanasyev18bbf812014-01-29 01:40:23 -080041namespace nfd {
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070042
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040043typedef std::list<cs::Entry*> SkipListLayer;
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080044typedef std::list<SkipListLayer*> SkipList;
45
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040046class StalenessComparator
47{
48public:
49 bool
50 operator()(const cs::Entry* entry1, const cs::Entry* entry2) const
51 {
52 return entry1->getStaleTime() < entry2->getStaleTime();
53 }
54};
55
56class UnsolicitedComparator
57{
58public:
59 bool
60 operator()(const cs::Entry* entry1, const cs::Entry* entry2) const
61 {
62 return entry1->isUnsolicited();
63 }
64};
65
66// tags
67class unsolicited;
68class byStaleness;
69class byArrival;
70
Davide Pesavento52a18f92014-04-10 00:55:01 +020071typedef boost::multi_index_container<
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040072 cs::Entry*,
Davide Pesavento52a18f92014-04-10 00:55:01 +020073 boost::multi_index::indexed_by<
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040074
75 // by arrival (FIFO)
Davide Pesavento52a18f92014-04-10 00:55:01 +020076 boost::multi_index::sequenced<
77 boost::multi_index::tag<byArrival>
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040078 >,
79
80 // index by staleness time
Davide Pesavento52a18f92014-04-10 00:55:01 +020081 boost::multi_index::ordered_non_unique<
82 boost::multi_index::tag<byStaleness>,
83 boost::multi_index::identity<cs::Entry*>,
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040084 StalenessComparator
85 >,
86
87 // unsolicited Data is in the front
Davide Pesavento52a18f92014-04-10 00:55:01 +020088 boost::multi_index::ordered_non_unique<
89 boost::multi_index::tag<unsolicited>,
90 boost::multi_index::identity<cs::Entry*>,
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040091 UnsolicitedComparator
92 >
93
94 >
95> CleanupIndex;
96
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080097/** \brief represents Content Store
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070098 */
Alexander Afanasyevb927a3a2014-01-24 10:41:47 -080099class Cs : noncopyable
Junxiao Shi0fcb41e2014-01-24 10:29:43 -0700100{
101public:
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800102 explicit
103 Cs(int nMaxPackets = 65536); // ~500MB with average packet size = 8KB
104
Junxiao Shi0fcb41e2014-01-24 10:29:43 -0700105 ~Cs();
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800106
Junxiao Shi0fcb41e2014-01-24 10:29:43 -0700107 /** \brief inserts a Data packet
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800108 * This method does not consider the payload of the Data packet.
109 *
110 * Packets are considered duplicate if the name matches.
111 * The new Data packet with the identical name, but a different payload
112 * is not placed in the Content Store
Junxiao Shi0fcb41e2014-01-24 10:29:43 -0700113 * \return{ whether the Data is added }
114 */
115 bool
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800116 insert(const Data& data, bool isUnsolicited = false);
117
Junxiao Shi0fcb41e2014-01-24 10:29:43 -0700118 /** \brief finds the best match Data for an Interest
Alexander Afanasyevc9765df2014-01-25 19:24:27 -0800119 * \return{ the best match, if any; otherwise 0 }
Junxiao Shi0fcb41e2014-01-24 10:29:43 -0700120 */
Alexander Afanasyevc9765df2014-01-25 19:24:27 -0800121 const Data*
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800122 find(const Interest& interest) const;
123
124 /** \brief deletes CS entry by the exact name
125 */
126 void
127 erase(const Name& exactName);
128
129 /** \brief sets maximum allowed size of Content Store (in packets)
130 */
131 void
132 setLimit(size_t nMaxPackets);
133
134 /** \brief returns maximum allowed size of Content Store (in packets)
135 * \return{ number of packets that can be stored in Content Store }
136 */
137 size_t
138 getLimit() const;
139
140 /** \brief returns current size of Content Store measured in packets
141 * \return{ number of packets located in Content Store }
142 */
143 size_t
144 size() const;
145
146protected:
147 /** \brief removes one Data packet from Content Store based on replacement policy
148 * \return{ whether the Data was removed }
149 */
150 bool
151 evictItem();
152
153private:
154 /** \brief returns True if the Content Store is at its maximum capacity
155 * \return{ True if Content Store is full; otherwise False}
156 */
157 bool
158 isFull() const;
159
160 /** \brief Computes the layer where new Content Store Entry is placed
161 *
162 * Reference: "Skip Lists: A Probabilistic Alternative to Balanced Trees" by W.Pugh
163 * \return{ returns random layer (number) in a skip list}
164 */
Alexander Afanasyevefea8fe2014-03-23 00:00:35 -0700165 size_t
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800166 pickRandomLayer() const;
167
168 /** \brief Inserts a new Content Store Entry in a skip list
169 * \return{ returns a pair containing a pointer to the CS Entry,
170 * and a flag indicating if the entry was newly created (True) or refreshed (False) }
171 */
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400172 std::pair<cs::Entry*, bool>
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800173 insertToSkipList(const Data& data, bool isUnsolicited = false);
174
175 /** \brief Removes a specific CS Entry from all layers of a skip list
176 * \return{ returns True if CS Entry was succesfully removed and False if CS Entry was not found}
177 */
178 bool
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400179 eraseFromSkipList(cs::Entry* entry);
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800180
181 /** \brief Prints contents of the skip list, starting from the top layer
182 */
183 void
184 printSkipList() const;
185
186 /** \brief Implements child selector (leftmost, rightmost, undeclared).
187 * Operates on the first layer of a skip list.
188 *
189 * startingPoint must be less than Interest Name.
190 * startingPoint can be equal to Interest Name only when the item is in the begin() position.
191 *
192 * Iterates toward greater Names, terminates when CS entry falls out of Interest prefix.
193 * When childSelector = leftmost, returns first CS entry that satisfies other selectors.
194 * When childSelector = rightmost, it goes till the end, and returns CS entry that satisfies
195 * other selectors. Returned CS entry is the leftmost child of the rightmost child.
196 * \return{ the best match, if any; otherwise 0 }
197 */
198 const Data*
199 selectChild(const Interest& interest, SkipListLayer::iterator startingPoint) const;
200
201 /** \brief checks if Content Store entry satisfies Interest selectors (MinSuffixComponents,
202 * MaxSuffixComponents, Implicit Digest, MustBeFresh)
203 * \return{ true if satisfies all selectors; false otherwise }
204 */
205 bool
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400206 doesComplyWithSelectors(const Interest& interest,
207 cs::Entry* entry,
208 bool doesInterestContainDigest) const;
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800209
210 /** \brief interprets minSuffixComponent and name lengths to understand if Interest contains
211 * implicit digest of the data
212 * \return{ True if Interest name contains digest; False otherwise }
213 */
214 bool
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400215 recognizeInterestWithDigest(const Interest& interest, cs::Entry* entry) const;
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800216
217private:
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800218 SkipList m_skipList;
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400219 CleanupIndex m_cleanupIndex;
220 size_t m_nMaxPackets; // user defined maximum size of the Content Store in packets
221 size_t m_nPackets; // current number of packets in Content Store
222 std::queue<cs::Entry*> m_freeCsEntries; // memory pool
Junxiao Shi0fcb41e2014-01-24 10:29:43 -0700223};
224
Alexander Afanasyev18bbf812014-01-29 01:40:23 -0800225} // namespace nfd
Alexander Afanasyevb927a3a2014-01-24 10:41:47 -0800226
Alexander Afanasyev613e2a92014-04-15 13:36:58 -0700227#endif // NFD_DAEMON_TABLE_CS_HPP