blob: a8f1a5fc2c13a90351d819f7cb97ecebfb61bc8d [file] [log] [blame]
// Copyright 2017 The Chromium OS 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 <stdint.h>
#include <functional>
#include <map>
#include <unordered_set>
#include <gtest/gtest.h>
#include "patchpanel/mac_address_generator.h"
namespace patchpanel {
namespace {
// The standard library sadly does not provide a hash function for std::array.
// So implement one here for MacAddress based off boost::hash_combine.
struct MacAddressHasher {
size_t operator()(const MacAddress& addr) const noexcept {
std::hash<uint8_t> hasher;
size_t hash = 0;
for (uint8_t octet : addr) {
hash ^= hasher(octet) + 0x9e3779b9 + (hash << 6) + (hash >> 2);
return hash;
} // namespace
// Tests that the mac addresses created by the generator have the proper flags.
TEST(MacAddressGenerator, Flags) {
MacAddressGenerator generator;
MacAddress addr = generator.Generate();
EXPECT_EQ(static_cast<uint8_t>(0x02), addr[0] & static_cast<uint8_t>(0x02));
EXPECT_EQ(static_cast<uint8_t>(0), addr[0] & static_cast<uint8_t>(0x01));
// Tests that the generator does not create duplicate addresses. Obviously due
// the vast range of possible addresses it's expensive to do an exhaustive
// search in this test. However, we can take advantage of the birthday paradox
// to reduce the number of addresses we need to generate. We know that the 2
// least significant bits of the first octet in the address are fixed. This
// leaves 2^46 possible addresses. Generating 2^25 addresses gives us a 99.96%
// chance of triggering a collision in this range. So if the generator returns
// 2^25 unique addresses then we can be fairly certain that it won't give out
// duplicate addresses.
// This test is currently disabled because it takes a long time to run
// (~minutes). We ran it on the CQ for several months without issue so we can
// be pretty confident that the current implementation does not produce
// duplicates. If you make any changes to the mac address generation code,
// please re-enable this test.
TEST(MacAddressGenerator, DISABLED_Duplicates) {
constexpr uint32_t kNumAddresses = (1 << 25);
MacAddressGenerator generator;
std::unordered_set<MacAddress, MacAddressHasher> addrs;
for (uint32_t i = 0; i < kNumAddresses; ++i) {
MacAddress addr = generator.Generate();
EXPECT_EQ(addrs.end(), addrs.find(addr));
TEST(MacAddressGenerator, Stable) {
MacAddressGenerator generator1, generator2;
std::map<uint8_t, MacAddress> addrs;
for (uint8_t i = 0;; ++i) {
addrs[i] = generator1.GetStable(i);
addrs[i][0] & static_cast<uint8_t>(0x02));
addrs[i][0] & static_cast<uint8_t>(0x01));
if (i == 255)
EXPECT_EQ(addrs.size(), 256);
for (const auto addr : addrs) {
EXPECT_EQ(addr.second, generator2.GetStable(addr.first));
} // namespace patchpanel