folly/detail/IPAddress.h

   1 /*
   2  * Copyright 2015 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #pragma once
  18
  19 #include <boost/noncopyable.hpp>
  20 #include <glog/logging.h>
  21
  22 #include <algorithm>
  23 #include <array>
  24 #include <cstring>
  25 #include <string>
  26 #include <sstream>
  27 #include <type_traits>
  28 #include <vector>
  29
  30 extern "C" {
  31 #ifndef _MSC_VER
  32 #include <arpa/inet.h>
  33 #include <netinet/in.h>
  34 #include <sys/socket.h>
  35 #else
  36 #include <winsock2.h>
  37 #include <ws2tcpip.h>
  38 // missing in socket headers
  39 #define sa_family_t ADDRESS_FAMILY
  40 #endif
  41
  42 #include <sys/types.h>
  43 #include <netdb.h>
  44 }
  45
  46 #include <folly/Conv.h>
  47 #include <folly/Format.h>
  48
  49 #if defined(__APPLE__) && !defined(s6_addr16)
  50 # define s6_addr16 __u6_addr.__u6_addr16
  51 #endif
  52
  53 namespace folly { namespace detail {
  54
  55 inline std::string familyNameStr(sa_family_t family) {
  56   switch (family) {
  57     case AF_INET:
  58       return "AF_INET";
  59     case AF_INET6:
  60       return "AF_INET6";
  61     case AF_UNSPEC:
  62       return "AF_UNSPEC";
  63     case AF_UNIX:
  64       return "AF_UNIX";
  65     default:
  66       return folly::format("sa_family_t({})",
  67           folly::to<std::string>(family)).str();
  68   }
  69 }
  70
  71 template<typename IPAddrType>
  72 inline bool getNthMSBitImpl(const IPAddrType& ip, uint8_t bitIndex,
  73     sa_family_t family) {
  74   if (bitIndex >= ip.bitCount()) {
  75     throw std::invalid_argument(folly::to<std::string>("Bit index must be < ",
  76           ip.bitCount(), " for addresses of type :", familyNameStr(family)));
  77   }
  78   //Underlying bytes are in n/w byte order
  79   return (ip.getNthMSByte(bitIndex / 8) & (0x80 >> (bitIndex % 8))) != 0;
  80 }
  81
  82 /**
  83  * Helper for working with unsigned char* or uint8_t* ByteArray values
  84  */
  85 struct Bytes : private boost::noncopyable {
  86   // return true if all values of src are zero
  87   static bool isZero(const uint8_t* src, std::size_t len) {
  88     for (std::size_t i = 0; i < len; i++) {
  89       if (src[i] != 0x00) {
  90         return false;
  91       }
  92     }
  93     return true;
  94   }
  95
  96   // mask the values from two byte arrays, returning a new byte array
  97   template<std::size_t N>
  98   static std::array<uint8_t, N> mask(const std::array<uint8_t, N>& a,
  99                                      const std::array<uint8_t, N>& b) {
 100     static_assert(N > 0, "Can't mask an empty ByteArray");
 101     std::size_t asize = a.size();
 102     std::array<uint8_t, N> ba{{0}};
 103     for (std::size_t i = 0; i < asize; i++) {
 104       ba[i] = a[i] & b[i];
 105     }
 106     return ba;
 107   }
 108
 109   template<std::size_t N>
 110   static std::pair<std::array<uint8_t, N>, uint8_t>
 111   longestCommonPrefix(
 112     const std::array<uint8_t, N>& one, uint8_t oneMask,
 113     const std::array<uint8_t, N>& two, uint8_t twoMask) {
 114     static constexpr auto kBitCount = N * 8;
 115     static constexpr std::array<uint8_t, 8> kMasks {{
 116       0x80, // /1
 117       0xc0, // /2
 118       0xe0, // /3
 119       0xf0, // /4
 120       0xf8, // /5
 121       0xfc, // /6
 122       0xfe, // /7
 123       0xff  // /8
 124     }};
 125     if (oneMask > kBitCount || twoMask > kBitCount) {
 126       throw std::invalid_argument(folly::to<std::string>("Invalid mask "
 127             "length: ", oneMask > twoMask ? oneMask : twoMask,
 128             ". Mask length must be <= ", kBitCount));
 129     }
 130
 131     auto mask = std::min(oneMask, twoMask);
 132     uint8_t byteIndex = 0;
 133     std::array<uint8_t, N> ba{{0}};
 134     // Compare a byte at a time. Note - I measured compared this with
 135     // going multiple bytes at a time (8, 4, 2 and 1). It turns out
 136     // to be 20 - 25% slower for 4 and 16 byte arrays.
 137     while (byteIndex * 8 < mask && one[byteIndex] == two[byteIndex]) {
 138       ba[byteIndex] = one[byteIndex];
 139       ++byteIndex;
 140     }
 141     auto bitIndex = std::min(mask, (uint8_t)(byteIndex * 8));
 142     // Compute the bit up to which the two byte arrays match in the
 143     // unmatched byte.
 144     // Here the check is bitIndex < mask since the 0th mask entry in
 145     // kMasks array holds the mask for masking the MSb in this byte.
 146     // We could instead make it hold so that no 0th entry masks no
 147     // bits but thats a useless iteration.
 148     while (bitIndex < mask && ((one[bitIndex / 8] & kMasks[bitIndex % 8]) ==
 149         (two[bitIndex / 8] & kMasks[bitIndex % 8]))) {
 150       ba[bitIndex / 8] = one[bitIndex / 8] & kMasks[bitIndex % 8];
 151       ++bitIndex;
 152     }
 153     return {ba, bitIndex};
 154   }
 155
 156   // create an in_addr from an uint8_t*
 157   static inline in_addr mkAddress4(const uint8_t* src) {
 158     union {
 159       in_addr addr;
 160       uint8_t bytes[4];
 161     } addr;
 162     std::memset(&addr, 0, 4);
 163     std::memcpy(addr.bytes, src, 4);
 164     return addr.addr;
 165   }
 166
 167   // create an in6_addr from an uint8_t*
 168   static inline in6_addr mkAddress6(const uint8_t* src) {
 169     in6_addr addr;
 170     std::memset(&addr, 0, 16);
 171     std::memcpy(addr.s6_addr, src, 16);
 172     return addr;
 173   }
 174
 175   // convert an uint8_t* to its hex value
 176   static std::string toHex(const uint8_t* src, std::size_t len) {
 177     static const char* const lut = "0123456789abcdef";
 178     std::stringstream ss;
 179     for (std::size_t i = 0; i < len; i++) {
 180       const unsigned char c = src[i];
 181       ss << lut[c >> 4] << lut[c & 15];
 182     }
 183     return ss.str();
 184   }
 185
 186  private:
 187   Bytes() = delete;
 188   ~Bytes() = delete;
 189 };
 190
 191 //
 192 // Write a maximum amount of base-converted character digits, of a
 193 // given base, from an unsigned integral type into a byte buffer of
 194 // sufficient size.
 195 //
 196 // This function does not append null terminators.
 197 //
 198 // Output buffer size must be guaranteed by caller (indirectly
 199 // controlled by DigitCount template parameter).
 200 //
 201 // Having these parameters at compile time allows compiler to
 202 // precompute several of the values, use smaller instructions, and
 203 // better optimize surrounding code.
 204 //
 205 // IntegralType:
 206 //   - Something like uint8_t, uint16_t, etc
 207 //
 208 // DigitCount is the maximum number of digits to be printed
 209 //   - This is tied to IntegralType and Base. For example:
 210 //     - uint8_t in base 10 will print at most 3 digits ("255")
 211 //     - uint16_t in base 16 will print at most 4 hex digits ("FFFF")
 212 //
 213 // Base is the desired output base of the string
 214 //   - Base 10 will print [0-9], base 16 will print [0-9a-f]
 215 //
 216 // PrintAllDigits:
 217 //   - Whether or not leading zeros should be printed
 218 //
 219 template<class IntegralType,
 220          IntegralType DigitCount,
 221          IntegralType Base = 10,
 222          bool PrintAllDigits = false,
 223          class = typename std::enable_if<
 224            std::is_integral<IntegralType>::value &&
 225            std::is_unsigned<IntegralType>::value,
 226            bool>::type>
 227   inline void writeIntegerString(
 228     IntegralType val,
 229     char** buffer) {
 230   char* buf = *buffer;
 231
 232   if (!PrintAllDigits && val == 0) {
 233     *(buf++) = '0';
 234     *buffer = buf;
 235     return;
 236   }
 237
 238   IntegralType powerToPrint = 1;
 239   for (int i = 1; i < DigitCount; ++i) {
 240     powerToPrint *= Base;
 241   }
 242
 243   bool found = PrintAllDigits;
 244   while (powerToPrint) {
 245
 246     if (found || powerToPrint <= val) {
 247       IntegralType value = val/powerToPrint;
 248       if (Base == 10 || value < 10) {
 249         value += '0';
 250       } else {
 251         value += ('a'-10);
 252       }
 253       *(buf++) = value;
 254       val %= powerToPrint;
 255       found = true;
 256     }
 257
 258     powerToPrint /= Base;
 259   }
 260
 261   *buffer = buf;
 262 }
 263
 264 inline std::string fastIpv4ToString(
 265   const in_addr& inAddr) {
 266   const uint8_t* octets = reinterpret_cast<const uint8_t*>(&inAddr.s_addr);
 267   char str[sizeof("255.255.255.255")];
 268   char* buf = str;
 269
 270   writeIntegerString<uint8_t, 3>(octets[0], &buf);
 271   *(buf++) = '.';
 272   writeIntegerString<uint8_t, 3>(octets[1], &buf);
 273   *(buf++) = '.';
 274   writeIntegerString<uint8_t, 3>(octets[2], &buf);
 275   *(buf++) = '.';
 276   writeIntegerString<uint8_t, 3>(octets[3], &buf);
 277
 278   return std::string(str, buf-str);
 279 }
 280
 281 inline std::string fastIpv6ToString(const in6_addr& in6Addr) {
 282   const uint16_t* bytes = reinterpret_cast<const uint16_t*>(&in6Addr.s6_addr16);
 283   char str[sizeof("2001:0db8:0000:0000:0000:ff00:0042:8329")];
 284   char* buf = str;
 285
 286   for (int i = 0; i < 8; ++i) {
 287     writeIntegerString<uint16_t,
 288                        4,  // at most 4 hex digits per ushort
 289                        16, // base 16 (hex)
 290                        true>(htons(bytes[i]), &buf);
 291
 292     if(i != 7) {
 293       *(buf++) = ':';
 294     }
 295   }
 296
 297   return std::string(str, buf-str);
 298 }
 299
 300 }}  // folly::detail