memory_datasrc.cc 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473
  1. // Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC")
  2. //
  3. // Permission to use, copy, modify, and/or distribute this software for any
  4. // purpose with or without fee is hereby granted, provided that the above
  5. // copyright notice and this permission notice appear in all copies.
  6. //
  7. // THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  8. // REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  9. // AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  10. // INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  11. // LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  12. // OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  13. // PERFORMANCE OF THIS SOFTWARE.
  14. #include <map>
  15. #include <cassert>
  16. #include <boost/shared_ptr.hpp>
  17. #include <boost/bind.hpp>
  18. #include <dns/name.h>
  19. #include <dns/rrclass.h>
  20. #include <dns/rrsetlist.h>
  21. #include <dns/masterload.h>
  22. #include <datasrc/memory_datasrc.h>
  23. #include <datasrc/rbtree.h>
  24. using namespace std;
  25. using namespace isc::dns;
  26. namespace isc {
  27. namespace datasrc {
  28. // Private data and hidden methods of MemoryZone
  29. struct MemoryZone::MemoryZoneImpl {
  30. // Constructor
  31. MemoryZoneImpl(const RRClass& zone_class, const Name& origin) :
  32. zone_class_(zone_class), origin_(origin), origin_data_(NULL)
  33. {
  34. // We create the node for origin (it needs to exist anyway in future)
  35. domains_.insert(origin, &origin_data_);
  36. DomainPtr origin_domain(new Domain);
  37. origin_data_->setData(origin_domain);
  38. }
  39. // Some type aliases
  40. /*
  41. * Each domain consists of some RRsets. They will be looked up by the
  42. * RRType.
  43. *
  44. * The use of map is questionable with regard to performance - there'll
  45. * be usually only few RRsets in the domain, so the log n benefit isn't
  46. * much and a vector/array might be faster due to its simplicity and
  47. * continuous memory location. But this is unlikely to be a performance
  48. * critical place and map has better interface for the lookups, so we use
  49. * that.
  50. */
  51. typedef map<RRType, ConstRRsetPtr> Domain;
  52. typedef Domain::value_type DomainPair;
  53. typedef boost::shared_ptr<Domain> DomainPtr;
  54. // The tree stores domains
  55. typedef RBTree<Domain> DomainTree;
  56. typedef RBNode<Domain> DomainNode;
  57. // Information about the zone
  58. RRClass zone_class_;
  59. Name origin_;
  60. DomainNode* origin_data_;
  61. string file_name_;
  62. // The actual zone data
  63. DomainTree domains_;
  64. /*
  65. * Does some checks in context of the data that are already in the zone.
  66. * Currently checks for forbidden combinations of RRsets in the same
  67. * domain (CNAME+anything, DNAME+NS).
  68. *
  69. * If such condition is found, it throws AddError.
  70. */
  71. void contextCheck(const ConstRRsetPtr& rrset,
  72. const DomainPtr& domain) const {
  73. // Ensure CNAME and other type of RR don't coexist for the same
  74. // owner name.
  75. if (rrset->getType() == RRType::CNAME()) {
  76. // XXX: this check will become incorrect when we support DNSSEC
  77. // (depending on how we support DNSSEC). We should revisit it
  78. // at that point.
  79. if (!domain->empty()) {
  80. isc_throw(AddError, "CNAME can't be added with other data for "
  81. << rrset->getName());
  82. }
  83. } else if (domain->find(RRType::CNAME()) != domain->end()) {
  84. isc_throw(AddError, "CNAME and " << rrset->getType() <<
  85. " can't coexist for " << rrset->getName());
  86. }
  87. /*
  88. * Similar with DNAME, but it must not coexist only with NS and only in
  89. * non-apex domains.
  90. * RFC 2672 section 3 mentions that it is implied from it and RFC 2181
  91. */
  92. if (rrset->getName() != origin_ &&
  93. // Adding DNAME, NS already there
  94. ((rrset->getType() == RRType::DNAME() &&
  95. domain->find(RRType::NS()) != domain->end()) ||
  96. // Adding NS, DNAME already there
  97. (rrset->getType() == RRType::NS() &&
  98. domain->find(RRType::DNAME()) != domain->end())))
  99. {
  100. isc_throw(AddError, "DNAME can't coexist with NS in non-apex "
  101. "domain " << rrset->getName());
  102. }
  103. }
  104. /*
  105. * Implementation of longer methods. We put them here, because the
  106. * access is without the impl_-> and it will get inlined anyway.
  107. */
  108. // Implementation of MemoryZone::add
  109. result::Result add(const ConstRRsetPtr& rrset, DomainTree* domains) {
  110. // Sanitize input
  111. if (!rrset) {
  112. isc_throw(NullRRset, "The rrset provided is NULL");
  113. }
  114. // Check for singleton RRs. It should probably handled at a different
  115. // in future.
  116. if ((rrset->getType() == RRType::CNAME() ||
  117. rrset->getType() == RRType::DNAME()) &&
  118. rrset->getRdataCount() > 1)
  119. {
  120. // XXX: this is not only for CNAME or DNAME. We should generalize
  121. // this code for all other "singleton RR types" (such as SOA) in a
  122. // separate task.
  123. isc_throw(AddError, "multiple RRs of singleton type for "
  124. << rrset->getName());
  125. }
  126. Name name(rrset->getName());
  127. NameComparisonResult compare(origin_.compare(name));
  128. if (compare.getRelation() != NameComparisonResult::SUPERDOMAIN &&
  129. compare.getRelation() != NameComparisonResult::EQUAL)
  130. {
  131. isc_throw(OutOfZone, "The name " << name <<
  132. " is not contained in zone " << origin_);
  133. }
  134. // Get the node
  135. DomainNode* node;
  136. switch (domains->insert(name, &node)) {
  137. // Just check it returns reasonable results
  138. case DomainTree::SUCCESS:
  139. case DomainTree::ALREADYEXISTS:
  140. break;
  141. // Something odd got out
  142. default:
  143. assert(0);
  144. }
  145. assert(node != NULL);
  146. // Now get the domain
  147. DomainPtr domain;
  148. // It didn't exist yet, create it
  149. if (node->isEmpty()) {
  150. domain.reset(new Domain);
  151. node->setData(domain);
  152. } else { // Get existing one
  153. domain = node->getData();
  154. }
  155. // Checks related to the surrounding data.
  156. // Note: when the check fails and the exception is thrown, it may
  157. // break strong exception guarantee. At the moment we prefer
  158. // code simplicity and don't bother to introduce complicated
  159. // recovery code.
  160. contextCheck(rrset, domain);
  161. // Try inserting the rrset there
  162. if (domain->insert(DomainPair(rrset->getType(), rrset)).second) {
  163. // Ok, we just put it in
  164. // If this RRset creates a zone cut at this node, mark the node
  165. // indicating the need for callback in find().
  166. if (rrset->getType() == RRType::NS() &&
  167. rrset->getName() != origin_) {
  168. node->enableCallback();
  169. // If it is DNAME, we have a callback as well here
  170. } else if (rrset->getType() == RRType::DNAME()) {
  171. node->enableCallback();
  172. }
  173. return (result::SUCCESS);
  174. } else {
  175. // The RRSet of given type was already there
  176. return (result::EXIST);
  177. }
  178. }
  179. /*
  180. * Same as above, but it checks the return value and if it already exists,
  181. * it throws.
  182. */
  183. void addFromLoad(const ConstRRsetPtr& set, DomainTree* domains) {
  184. switch (add(set, domains)) {
  185. case result::EXIST:
  186. isc_throw(dns::MasterLoadError, "Duplicate rrset: " <<
  187. set->toText());
  188. case result::SUCCESS:
  189. return;
  190. default:
  191. assert(0);
  192. }
  193. }
  194. // Maintain intermediate data specific to the search context used in
  195. /// \c find().
  196. ///
  197. /// It will be passed to \c zonecutCallback() and record a possible
  198. /// zone cut node and related RRset (normally NS or DNAME).
  199. struct FindState {
  200. FindState(FindOptions options) :
  201. zonecut_node_(NULL),
  202. dname_node_(NULL),
  203. options_(options)
  204. {}
  205. const DomainNode* zonecut_node_;
  206. const DomainNode* dname_node_;
  207. ConstRRsetPtr rrset_;
  208. const FindOptions options_;
  209. };
  210. // A callback called from possible zone cut nodes and nodes with DNAME.
  211. // This will be passed from the \c find() method to \c RBTree::find().
  212. static bool cutCallback(const DomainNode& node, FindState* state) {
  213. // We need to look for DNAME first, there's allowed case where
  214. // DNAME and NS coexist in the apex. DNAME is the one to notice,
  215. // the NS is authoritative, not delegation (corner case explicitly
  216. // allowed by section 3 of 2672)
  217. const Domain::const_iterator foundDNAME(node.getData()->find(
  218. RRType::DNAME()));
  219. if (foundDNAME != node.getData()->end()) {
  220. state->dname_node_ = &node;
  221. state->rrset_ = foundDNAME->second;
  222. // No more processing below the DNAME (RFC 2672, section 3
  223. // forbids anything to exist below it, so there's no need
  224. // to actually search for it). This is strictly speaking
  225. // a different way than described in 4.1 of that RFC,
  226. // but because of the assumption in section 3, it has the
  227. // same behaviour.
  228. return (true);
  229. }
  230. // Look for NS
  231. const Domain::const_iterator foundNS(node.getData()->find(
  232. RRType::NS()));
  233. if (foundNS != node.getData()->end()) {
  234. // We perform callback check only for the highest zone cut in the
  235. // rare case of nested zone cuts.
  236. if (state->zonecut_node_ != NULL) {
  237. return (false);
  238. }
  239. // BIND 9 checks if this node is not the origin. That's probably
  240. // because it can support multiple versions for dynamic updates
  241. // and IXFR, and it's possible that the callback is called at
  242. // the apex and the DNAME doesn't exist for a particular version.
  243. // It cannot happen for us (at least for now), so we don't do
  244. // that check.
  245. state->zonecut_node_ = &node;
  246. state->rrset_ = foundNS->second;
  247. // Unless glue is allowed the search stops here, so we return
  248. // false; otherwise return true to continue the search.
  249. return ((state->options_ & FIND_GLUE_OK) == 0);
  250. }
  251. // This case should not happen because we enable callback only
  252. // when we add an RR searched for above.
  253. assert(0);
  254. // This is here to avoid warning (therefore compilation error)
  255. // in case assert is turned off. Otherwise we could get "Control
  256. // reached end of non-void function".
  257. return (false);
  258. }
  259. // Implementation of MemoryZone::find
  260. FindResult find(const Name& name, RRType type,
  261. RRsetList* target, const FindOptions options) const
  262. {
  263. // Get the node
  264. DomainNode* node(NULL);
  265. FindState state(options);
  266. switch (domains_.find(name, &node, cutCallback, &state)) {
  267. case DomainTree::PARTIALMATCH:
  268. /*
  269. * In fact, we could use a single variable instead of
  270. * dname_node_ and zonecut_node_. But then we would need
  271. * to distinquish these two cases by something else and
  272. * it seemed little more confusing to me when I wrote it.
  273. *
  274. * Usually at most one of them will be something else than
  275. * NULL (it might happen both are NULL, in which case we
  276. * consider it NOT FOUND). There's one corner case when
  277. * both might be something else than NULL and it is in case
  278. * there's a DNAME under a zone cut and we search in
  279. * glue OK mode ‒ in that case we don't stop on the domain
  280. * with NS and ignore it for the answer, but it gets set
  281. * anyway. Then we find the DNAME and we need to act by it,
  282. * therefore we first check for DNAME and then for NS. In
  283. * all other cases it doesn't matter, as at least one of them
  284. * is NULL.
  285. */
  286. if (state.dname_node_ != NULL) {
  287. // We were traversing a DNAME node (and wanted to go
  288. // lower below it), so return the DNAME
  289. return (FindResult(DNAME, state.rrset_));
  290. }
  291. if (state.zonecut_node_ != NULL) {
  292. return (FindResult(DELEGATION, state.rrset_));
  293. }
  294. // TODO: we should also cover empty non-terminal cases, which
  295. // will require non trivial code and is deferred for later
  296. // development. For now, we regard any partial match that
  297. // didn't hit a zone cut as "not found".
  298. case DomainTree::NOTFOUND:
  299. return (FindResult(NXDOMAIN, ConstRRsetPtr()));
  300. case DomainTree::EXACTMATCH: // This one is OK, handle it
  301. break;
  302. default:
  303. assert(0);
  304. }
  305. assert(node);
  306. assert(!node->isEmpty());
  307. Domain::const_iterator found;
  308. // If the node callback is enabled, this may be a zone cut. If it
  309. // has a NS RR, we should return a delegation, but not in the apex.
  310. if (node->isCallbackEnabled() && node != origin_data_) {
  311. found = node->getData()->find(RRType::NS());
  312. if (found != node->getData()->end()) {
  313. return (FindResult(DELEGATION, found->second));
  314. }
  315. }
  316. // handle type any query
  317. if (target && !node->getData()->empty()) {
  318. // Empty domain will be handled as NXRRSET by normal processing
  319. for (found = node->getData()->begin();
  320. found != node->getData()->end(); found++)
  321. {
  322. target->addRRset(
  323. boost::const_pointer_cast<RRset>(found->second));
  324. }
  325. return (FindResult(SUCCESS, ConstRRsetPtr()));
  326. }
  327. found = node->getData()->find(type);
  328. if (found != node->getData()->end()) {
  329. // Good, it is here
  330. return (FindResult(SUCCESS, found->second));
  331. } else {
  332. // Next, try CNAME.
  333. found = node->getData()->find(RRType::CNAME());
  334. if (found != node->getData()->end()) {
  335. return (FindResult(CNAME, found->second));
  336. }
  337. }
  338. // No exact match or CNAME. Return NXRRSET.
  339. return (FindResult(NXRRSET, ConstRRsetPtr()));
  340. }
  341. };
  342. MemoryZone::MemoryZone(const RRClass& zone_class, const Name& origin) :
  343. impl_(new MemoryZoneImpl(zone_class, origin))
  344. {
  345. }
  346. MemoryZone::~MemoryZone() {
  347. delete impl_;
  348. }
  349. const Name&
  350. MemoryZone::getOrigin() const {
  351. return (impl_->origin_);
  352. }
  353. const RRClass&
  354. MemoryZone::getClass() const {
  355. return (impl_->zone_class_);
  356. }
  357. Zone::FindResult
  358. MemoryZone::find(const Name& name, const RRType& type,
  359. RRsetList* target, const FindOptions options) const
  360. {
  361. return (impl_->find(name, type, target, options));
  362. }
  363. result::Result
  364. MemoryZone::add(const ConstRRsetPtr& rrset) {
  365. return (impl_->add(rrset, &impl_->domains_));
  366. }
  367. void
  368. MemoryZone::load(const string& filename) {
  369. // Load it into a temporary tree
  370. MemoryZoneImpl::DomainTree tmp;
  371. masterLoad(filename.c_str(), getOrigin(), getClass(),
  372. boost::bind(&MemoryZoneImpl::addFromLoad, impl_, _1, &tmp));
  373. // If it went well, put it inside
  374. impl_->file_name_ = filename;
  375. tmp.swap(impl_->domains_);
  376. // And let the old data die with tmp
  377. }
  378. void
  379. MemoryZone::swap(MemoryZone& zone) {
  380. std::swap(impl_, zone.impl_);
  381. }
  382. const string
  383. MemoryZone::getFileName() const {
  384. return (impl_->file_name_);
  385. }
  386. /// Implementation details for \c MemoryDataSrc hidden from the public
  387. /// interface.
  388. ///
  389. /// For now, \c MemoryDataSrc only contains a \c ZoneTable object, which
  390. /// consists of (pointers to) \c MemoryZone objects, we may add more
  391. /// member variables later for new features.
  392. class MemoryDataSrc::MemoryDataSrcImpl {
  393. public:
  394. MemoryDataSrcImpl() : zone_count(0) {}
  395. unsigned int zone_count;
  396. ZoneTable zone_table;
  397. };
  398. MemoryDataSrc::MemoryDataSrc() : impl_(new MemoryDataSrcImpl)
  399. {}
  400. MemoryDataSrc::~MemoryDataSrc() {
  401. delete impl_;
  402. }
  403. unsigned int
  404. MemoryDataSrc::getZoneCount() const {
  405. return (impl_->zone_count);
  406. }
  407. result::Result
  408. MemoryDataSrc::addZone(ZonePtr zone) {
  409. if (!zone) {
  410. isc_throw(InvalidParameter,
  411. "Null pointer is passed to MemoryDataSrc::addZone()");
  412. }
  413. const result::Result result = impl_->zone_table.addZone(zone);
  414. if (result == result::SUCCESS) {
  415. ++impl_->zone_count;
  416. }
  417. return (result);
  418. }
  419. MemoryDataSrc::FindResult
  420. MemoryDataSrc::findZone(const isc::dns::Name& name) const {
  421. return (FindResult(impl_->zone_table.findZone(name).code,
  422. impl_->zone_table.findZone(name).zone));
  423. }
  424. } // end of namespace datasrc
  425. } // end of namespace dns