Cache for mDNS records

net/dns/mdns_cache.cc

Index: net/dns/mdns_cache.cc
diff --git a/net/dns/mdns_cache.cc b/net/dns/mdns_cache.cc
new file mode 100644
index 0000000000000000000000000000000000000000..36efbb71e27c3a8e5398e143b703338390e659a2
--- /dev/null
+++ b/net/dns/mdns_cache.cc
@@ -0,0 +1,169 @@
+// Copyright (c) 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/dns/mdns_cache.h"
+
+#include "base/stl_util.h"
+#include "base/strings/string_number_conversions.h"
+#include "net/dns/dns_protocol.h"
+#include "net/dns/record_parsed.h"
+#include "net/dns/record_rdata.h"
+
+// TODO(noamsml): Recursive CNAME closure (backwards and forwards).
+
+namespace net {
+
+// The effective TTL given to records with a nominal zero TTL.
+// Allows time for hosts to send updated records.

[szym, 2013/05/17 05:04:34]

I suggest referring to RFC 6762 Section 10.1 here.

[Noam Samuel, 2013/05/17 22:26:05]

Done.

+static const unsigned kZeroTTLSeconds = 1;
+
+MDnsCache::DnsRecordCacheKey::DnsRecordCacheKey(unsigned type,
+                                                const std::string& name,
+                                                const std::string& optional)
+    : type_(type), name_(name), optional_(optional) {
+}
+
+MDnsCache::DnsRecordCacheKey::~DnsRecordCacheKey() {
+}
+
+bool MDnsCache::DnsRecordCacheKey::operator<(
+    const MDnsCache::DnsRecordCacheKey& key) const {
+  if (type_ != key.type_)
+    return type_ < key.type_;
+
+  if (name_ != key.name_)
+    return name_ < key.name_;
+
+  if (optional_ != key.optional_)
+    return optional_ < key.optional_;
+  return false;  // keys are equal
+}
+
+bool MDnsCache::DnsRecordCacheKey::operator==(
+    const MDnsCache::DnsRecordCacheKey& key) const {
+  return type_ == key.type_ && name_ == key.name_ && optional_ == key.optional_;
+}
+
+MDnsCache::MDnsCache(
+    const MDnsCache::RecordRemovedCallback& record_removed_callback)
+    : record_removed_callback_(record_removed_callback) {
+}
+
+MDnsCache::~MDnsCache() {
+  Clear();
+}
+
+void MDnsCache::Clear() {
+  next_expiration_ = base::Time();
+  STLDeleteValues(&mdns_cache_);
+}
+
+MDnsCache::UpdateType MDnsCache::UpdateDnsRecord(
+    scoped_ptr<const RecordParsed> record) {
+  UpdateType type = NoChange;
+
+  MDnsCache::DnsRecordCacheKey cache_key = MDnsCache::DnsRecordCacheKey(
+      record->type(),
+      record->name(),
+      GetOptionalFieldForRecord(record.get()));
+
+  base::Time expiration = GetEffectiveExpiration(record.get());
+  if (next_expiration_ == base::Time() || expiration < next_expiration_) {
+    next_expiration_ = expiration;
+  }
+
+  MDnsCacheMap::iterator i = mdns_cache_.find(cache_key);

[szym, 2013/05/17 05:04:34]

I'd suggest:

const RecordParsed*& found = mdns_cache_[cache_key];
if (found) {
  if (...)
    type = RecordChanged;
  delete found;
} else {
  type = RecordAdded;
}
found = record.release();

This way you are doing at most one lookup.

Alternatively, if the reference is confusing, you can use iterators:

std::pair<MDnsCacheMap::iterator, bool> found = 
    mdns_cache_.insert(make_pair(cache_key, record.get()));
if (found.second) {
  type = RecordAdded;
  ...
} else {
  ...
  delete found.first->second;
  found.first->second = record.release();
}

[Noam Samuel, 2013/05/17 22:26:05]

Done.

+  if (i != mdns_cache_.end()) {
+    if (!record->IsEqual(i->second, true)) {
+      type = RecordChanged;

[szym, 2013/05/17 05:04:34]

IMPORTANT: There is no RecordParsed::IsEqual.

[Noam Samuel, 2013/05/17 22:26:05]

Oh whoops. Uploaded the patch wrong. This upload is diffed against master and
should contain all files.

On 2013/05/17 05:04:34, szym wrote:

+    }
+    delete i->second;
+    i->second = record.release();
+  } else {
+    mdns_cache_[cache_key] = record.release();
+    type = RecordAdded;
+  }
+
+  return type;
+}
+
+void MDnsCache::CleanupRecords(

[szym, 2013/05/17 05:04:34]

nit: fits on a single line.

[Noam Samuel, 2013/05/17 22:26:05]

Done.

+    base::Time now) {
+  base::Time next_expiration;
+
+  // We are guaranteed that next_expiration_ will be at or before the next

[szym, 2013/05/17 05:04:34]

nit: || around variable names.

[Noam Samuel, 2013/05/17 22:26:05]

Done.

+  // expiration. This allows clients to eagrely call CleanupRecords with
+  // impunity.
+  if (now < next_expiration_) return;
+
+  std::vector<MDnsCacheMap::iterator> to_delete;

[szym, 2013/05/17 05:04:34]

Instead of keeping a handle on the iterators, remove them from the map as you go
through it the first time.

for (map::iterator i = cache_.begin(); i != ..end(); ) {
  if (now >= expiration) {
    // TODO: take a hold of i->second or delete it.
    cache_.erase(i++);
  } else {
    ++i;
  }
}

If you don't want to run record_removed_callback_ until they are all removed
from the cache, you could keep a std::vector<const RecordParsed*> until later.
But if that does not matter, just run it now and delete the record.

[Noam Samuel, 2013/05/17 22:26:05]

Done.

+  for (MDnsCacheMap::iterator i = mdns_cache_.begin();
+       i != mdns_cache_.end(); i++) {
+    base::Time expiration = GetEffectiveExpiration(i->second);
+    if (now >= expiration) {
+      to_delete.push_back(i);
+    } else {
+      if (next_expiration == base::Time() ||  expiration < next_expiration) {
+        next_expiration = expiration;
+      }
+    }
+  }
+
+  for (std::vector<MDnsCacheMap::iterator>::iterator i = to_delete.begin();
+       i != to_delete.end(); ++i) {
+    record_removed_callback_.Run((*i)->second);
+    delete (*i)->second;
+    mdns_cache_.erase(*i);
+  }
+
+  next_expiration_ = next_expiration;
+}
+
+void MDnsCache::FindDnsRecords(unsigned type,
+                               const std::string& name,
+                               std::vector<const RecordParsed*>* results,
+                               base::Time now) {
+  results->clear();

[szym, 2013/05/17 05:04:34]

DCHECK(results)

[Noam Samuel, 2013/05/17 22:26:05]

Done.

+
+  MDnsCacheMap::iterator i =
+      mdns_cache_.lower_bound(DnsRecordCacheKey(type, name, ""));
+  for (; i != mdns_cache_.end(); ++i) {
+    if (i->first.type() != type ||
+        (!name.empty() && i->first.name() != name)) {
+      break;
+    }
+
+    const RecordParsed* record = i->second;
+
+    // Records are deleted only upon request to make this op idempotent
+    if (now >= GetEffectiveExpiration(record)) continue;
+
+    results->push_back(record);
+  }
+}
+
+std::string MDnsCache::GetOptionalFieldForRecord(const RecordParsed* record) {
+  switch (record->type()) {
+    case PtrRecordRdata::kType: {
+      const PtrRecordRdata* rdata = record->rdata<PtrRecordRdata>();
+      return rdata->ptrdomain();
+    }
+    default:  // Most records are considered unique for our purposes
+      return "";
+  }
+}
+
+base::Time MDnsCache::GetEffectiveExpiration(const RecordParsed* record) {
+  base::TimeDelta ttl;
+
+  if (record->ttl()) {
+    ttl = base::TimeDelta::FromSeconds(record->ttl());
+  } else {
+    ttl = base::TimeDelta::FromSeconds(kZeroTTLSeconds);
+  }
+
+  return record->time_created() + ttl;
+}
+
+}  // namespace net