Move shared files in net/quic/ into net/quic/core/

net/quic/crypto/strike_register.h

-// 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.
-
-#ifndef NET_QUIC_CRYPTO_STRIKE_REGISTER_H_
-#define NET_QUIC_CRYPTO_STRIKE_REGISTER_H_
-
-#include <stdint.h>
-
-#include <memory>
-#include <set>
-#include <utility>
-#include <vector>
-
-#include "base/macros.h"
-#include "net/base/net_export.h"
-
-namespace net {
-
-// InsertStatus enum values cannot be changed, they need to be stable.
-enum InsertStatus {
-  NONCE_OK = 0,
-  // The default error value for nonce verification failures from strike
-  // register (covers old strike registers and unknown failures).
-  NONCE_UNKNOWN_FAILURE = 1,
-  // Decrypted nonce had incorrect length.
-  NONCE_INVALID_FAILURE = 2,
-  // Nonce is not unique.
-  NONCE_NOT_UNIQUE_FAILURE = 3,
-  // Nonce's orbit is invalid or incorrect.
-  NONCE_INVALID_ORBIT_FAILURE = 4,
-  // Nonce's timestamp is not in the strike register's valid time range.
-  NONCE_INVALID_TIME_FAILURE = 5,
-  // Strike register's RPC call timed out, nonce couldn't be verified.
-  STRIKE_REGISTER_TIMEOUT = 6,
-  // Strike register is down, nonce couldn't be verified.
-  STRIKE_REGISTER_FAILURE = 7,
-};
-
-// A StrikeRegister is critbit tree which stores a set of observed nonces.
-// We use a critbit tree because:
-//   1) It's immune to algorithmic complexity attacks. If we had used a hash
-//      tree, an attacker could send us a series of values which stretch out one
-//      of the hash chains, causing us to do much more work than normal.
-//   2) We can write it to use a fixed block of memory: avoiding fragmentation
-//      issues and so forth. (We might be able to do that with the STL
-//      algorithms and a custom allocator, but I don't want to go there.)
-//   3) It's simple (compared to balanced binary trees) and doesn't involve
-//      bouncing nearly as many cache lines around.
-//   4) It allows us to query for the oldest element in log(n) time.
-//
-// This code is based on djb's public domain critbit tree from qhasm.
-//
-// A critbit tree has external and internal nodes. External nodes are just the
-// nonce values (which are stored with internal times, see below, and without
-// the orbit values included). Internal nodes contain the bit number at which
-// the tree is branching and exactly two children. The critical bit is stored
-// as a byte number and a byte (|otherbits|) which has all the bits set
-// /except/ the one in question.
-//
-// Internal nodes have exactly two children: an internal node with only a
-// single child would be useless.
-//
-// The branching bit number (considering the MSB to be the 1st bit) is
-// monotonically increasing as you go down the tree.
-//
-// There are two distinct time representations used. External times are those
-// which are exposed to the users of this class. They are expected to be a
-// count of the number of seconds since the UNIX epoch. Internal times are a
-// count of the number of seconds since a point in time a couple of years
-// before the creation time given to the constructor. (See
-// |ExternalTimeToInternal|) This avoids having to worry about overflow since
-// we assume that no process will run for 130 years.
-class NET_EXPORT_PRIVATE StrikeRegister {
- public:
-  enum StartupType {
-    // DENY_REQUESTS_AT_STARTUP is the typical mode for a strike register.
-    // Because servers can crash and the strike-register memory-based, the
-    // state of the strike-register may be lost at any time. Thus the previous
-    // instance of the server may have accepted an nonce with time
-    // now+window_secs, which was forgotten in the crash. Therefore
-    // DENY_REQUESTS_AT_STARTUP causes the strike-register to reject all
-    // requests timestampped before window_secs + the creation time (the
-    // quiescent period).
-    DENY_REQUESTS_AT_STARTUP,
-    // NO_STARTUP_PERIOD_NEEDED indicates that no quiescent period is required.
-    // This may be because the strike-register is using an orbit randomly
-    // generated at startup and therefore nonces accepted by the previous
-    // instance of the strike-register are invalid for that reason.
-    NO_STARTUP_PERIOD_NEEDED,
-  };
-
-  // An external node takes 24 bytes as we don't record the orbit.
-  static const uint32_t kExternalNodeSize;
-
-  // We address the nodes by their index in the array. This means that 0 is a
-  // valid index. Therefore this is our invalid index. It also has a one bit
-  // in the LSB position because we tend to store indexes shifted up 8 bits
-  // and this distinguishes kNil from (kExternalFlag | 0) << 8.
-  static const uint32_t kNil;
-
-  // Our pointers from internal nodes can either point to an internal or
-  // external node. We flag the 24th bit to mark a pointer as external.
-  static const uint32_t kExternalFlag;
-
-  // Allows early validation before a strike register is created.
-  static void ValidateStrikeRegisterConfig(unsigned max_entries);
-
-  // Construct a new set which can hold, at most, |max_entries| (which must be
-  // less than 2**23). See the comments around StartupType about initial
-  // behaviour. Otherwise, all nonces that are outside +/- |window_secs| from
-  // the current time will be rejected. Additionally, all nonces that have an
-  // orbit value other than |orbit| will be rejected.
-  //
-  // (Note that this code is independent of the actual units of time used, but
-  // you should use seconds.)
-  StrikeRegister(unsigned max_entries,
-                 uint32_t current_time_external,
-                 uint32_t window_secs,
-                 const uint8_t orbit[8],
-                 StartupType startup);
-
-  ~StrikeRegister();
-
-  void Reset();
-
-  // |Insert| queries to see if |nonce| is
-  //   a) for the wrong orbit
-  //   b) before the current horizon
-  //   c) outside of the valid time window
-  //   d) already in the set of observed nonces
-  // and returns the failure reason if any of these are true. It is also free to
-  // return failure reason for other reasons as it's always safe to reject an
-  // nonce.
-  //
-  // nonces are:
-  //   4 bytes of timestamp (UNIX epoch seconds)
-  //   8 bytes of orbit value (a cluster id)
-  //   20 bytes of random data
-  //
-  // Otherwise, it inserts |nonce| into the observed set and returns NONCE_OK.
-  InsertStatus Insert(const uint8_t nonce[32], uint32_t current_time);
-
-  // orbit returns a pointer to the 8-byte orbit value for this
-  // strike-register.
-  const uint8_t* orbit() const;
-
-  // Time window for which the strike register has complete information.
-  uint32_t GetCurrentValidWindowSecs(uint32_t current_time_external) const;
-
-  // This is a debugging aid which checks the tree for sanity.
-  void Validate();
-
- private:
-  class InternalNode;
-
-  // TimeFromBytes returns a big-endian uint32_t from |d|.
-  static uint32_t TimeFromBytes(const uint8_t d[4]);
-
-  // Range of internal times for which the strike register has
-  // complete information.  A nonce is within the valid range of the
-  // strike register if:
-  //   valid_range.first <= nonce_time_internal <= valid_range.second
-  std::pair<uint32_t, uint32_t> GetValidRange(
-      uint32_t current_time_internal) const;
-
-  // ExternalTimeToInternal converts an external time value into an internal
-  // time value using |internal_epoch_|.
-  uint32_t ExternalTimeToInternal(uint32_t external_time) const;
-
-  // BestMatch returns either kNil, or an external node index which could
-  // possibly match |v|.
-  uint32_t BestMatch(const uint8_t v[24]) const;
-
-  // external_node_next_ptr returns the 'next' pointer embedded in external
-  // node |i|. This is used to thread a free list through the external nodes.
-  uint32_t& external_node_next_ptr(unsigned i);
-
-  uint8_t* external_node(unsigned i);
-
-  uint32_t GetFreeExternalNode();
-
-  uint32_t GetFreeInternalNode();
-
-  // DropOldestNode removes the oldest node in the tree and updates |horizon_|
-  // accordingly.
-  void DropOldestNode();
-
-  void FreeExternalNode(uint32_t index);
-
-  void FreeInternalNode(uint32_t index);
-
-  void ValidateTree(uint32_t internal_node,
-                    int last_bit,
-                    const std::vector<std::pair<unsigned, bool>>& bits,
-                    const std::set<uint32_t>& free_internal_nodes,
-                    const std::set<uint32_t>& free_external_nodes,
-                    std::set<uint32_t>* used_internal_nodes,
-                    std::set<uint32_t>* used_external_nodes);
-
-  const uint32_t max_entries_;
-  const uint32_t window_secs_;
-  // internal_epoch_ contains the external time value of the start of internal
-  // time.
-  const uint32_t internal_epoch_;
-  uint8_t orbit_[8];
-  // The strike register will reject nonces with internal times < |horizon_| .
-  uint32_t horizon_;
-
-  uint32_t internal_node_free_head_;
-  uint32_t external_node_free_head_;
-  uint32_t internal_node_head_;
-  // internal_nodes_ can't be a scoped_ptr because the type isn't defined in
-  // this header.
-  InternalNode* internal_nodes_;
-  std::unique_ptr<uint8_t[]> external_nodes_;
-
-  DISALLOW_COPY_AND_ASSIGN(StrikeRegister);
-};
-
-}  // namespace net
-
-#endif  // NET_QUIC_CRYPTO_STRIKE_REGISTER_H_