1 /*
2 * ngtcp2
3 *
4 * Copyright (c) 2017 ngtcp2 contributors
5 * Copyright (c) 2012 nghttp2 contributors
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining
8 * a copy of this software and associated documentation files (the
9 * "Software"), to deal in the Software without restriction, including
10 * without limitation the rights to use, copy, modify, merge, publish,
11 * distribute, sublicense, and/or sell copies of the Software, and to
12 * permit persons to whom the Software is furnished to do so, subject to
13 * the following conditions:
14 *
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
22 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
23 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
24 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25 */
26 #include "util.h"
27
28 #ifdef HAVE_ARPA_INET_H
29 # include <arpa/inet.h>
30 #endif // HAVE_ARPA_INET_H
31 #ifdef HAVE_NETINET_IN_H
32 # include <netinet/in.h>
33 #endif
34 #include <sys/types.h>
35 #include <unistd.h>
36 #include <fcntl.h>
37 #include <netdb.h>
38
39 #include <cassert>
40 #include <cstring>
41 #include <chrono>
42 #include <array>
43 #include <iostream>
44 #include <fstream>
45 #include <algorithm>
46 #include <limits>
47
48 #include "template.h"
49
50 namespace ngtcp2 {
51
52 namespace util {
53
54 namespace {
55 constexpr char LOWER_XDIGITS[] = "0123456789abcdef";
56 } // namespace
57
format_hex(uint8_t c)58 std::string format_hex(uint8_t c) {
59 std::string s;
60 s.resize(2);
61
62 s[0] = LOWER_XDIGITS[c >> 4];
63 s[1] = LOWER_XDIGITS[c & 0xf];
64
65 return s;
66 }
67
format_hex(const uint8_t * s,size_t len)68 std::string format_hex(const uint8_t *s, size_t len) {
69 std::string res;
70 res.resize(len * 2);
71
72 for (size_t i = 0; i < len; ++i) {
73 auto c = s[i];
74
75 res[i * 2] = LOWER_XDIGITS[c >> 4];
76 res[i * 2 + 1] = LOWER_XDIGITS[c & 0x0f];
77 }
78 return res;
79 }
80
format_hex(const std::string & s)81 std::string format_hex(const std::string &s) {
82 return format_hex(reinterpret_cast<const uint8_t *>(s.data()), s.size());
83 }
84
decode_hex(const std::string & s)85 std::string decode_hex(const std::string &s) {
86 assert(s.size() % 2 == 0);
87 std::string res(s.size() / 2, '0');
88 auto p = std::begin(res);
89 for (auto it = std::begin(s); it != std::end(s); it += 2) {
90 *p++ = (hex_to_uint(*it) << 4) | hex_to_uint(*(it + 1));
91 }
92 return res;
93 }
94
95 namespace {
96 // format_fraction2 formats |n| as fraction part of integer. |n| is
97 // considered as fraction, and its precision is 3 digits. The last
98 // digit is ignored. The precision of the resulting fraction is 2
99 // digits.
format_fraction2(uint32_t n)100 std::string format_fraction2(uint32_t n) {
101 n /= 10;
102
103 if (n < 10) {
104 return {'.', '0', static_cast<char>('0' + n)};
105 }
106 return {'.', static_cast<char>('0' + n / 10),
107 static_cast<char>('0' + (n % 10))};
108 }
109 } // namespace
110
111 namespace {
112 // round2even rounds the last digit of |n| so that the n / 10 becomes
113 // even.
round2even(uint64_t n)114 uint64_t round2even(uint64_t n) {
115 if (n % 10 == 5) {
116 if ((n / 10) & 1) {
117 n += 10;
118 }
119 } else {
120 n += 5;
121 }
122 return n;
123 }
124 } // namespace
125
format_durationf(uint64_t ns)126 std::string format_durationf(uint64_t ns) {
127 static constexpr const char *units[] = {"us", "ms", "s"};
128 if (ns < 1000) {
129 return std::to_string(ns) + "ns";
130 }
131 auto unit = 0;
132 if (ns < 1000000) {
133 // do nothing
134 } else if (ns < 1000000000) {
135 ns /= 1000;
136 unit = 1;
137 } else {
138 ns /= 1000000;
139 unit = 2;
140 }
141
142 ns = round2even(ns);
143
144 if (ns / 1000 >= 1000 && unit < 2) {
145 ns /= 1000;
146 ++unit;
147 }
148
149 return std::to_string(ns / 1000) + format_fraction2(ns % 1000) + units[unit];
150 }
151
make_mt19937()152 std::mt19937 make_mt19937() {
153 std::random_device rd;
154 return std::mt19937(rd());
155 }
156
timestamp(struct ev_loop * loop)157 ngtcp2_tstamp timestamp(struct ev_loop *loop) {
158 return std::chrono::duration_cast<std::chrono::nanoseconds>(
159 std::chrono::steady_clock::now().time_since_epoch())
160 .count();
161 }
162
numeric_host(const char * hostname)163 bool numeric_host(const char *hostname) {
164 return numeric_host(hostname, AF_INET) || numeric_host(hostname, AF_INET6);
165 }
166
numeric_host(const char * hostname,int family)167 bool numeric_host(const char *hostname, int family) {
168 int rv;
169 std::array<uint8_t, sizeof(struct in6_addr)> dst;
170
171 rv = inet_pton(family, hostname, dst.data());
172
173 return rv == 1;
174 }
175
176 namespace {
hexdump8(FILE * out,const uint8_t * first,const uint8_t * last)177 void hexdump8(FILE *out, const uint8_t *first, const uint8_t *last) {
178 auto stop = std::min(first + 8, last);
179 for (auto k = first; k != stop; ++k) {
180 fprintf(out, "%02x ", *k);
181 }
182 // each byte needs 3 spaces (2 hex value and space)
183 for (; stop != first + 8; ++stop) {
184 fputs(" ", out);
185 }
186 // we have extra space after 8 bytes
187 fputc(' ', out);
188 }
189 } // namespace
190
hexdump(FILE * out,const uint8_t * src,size_t len)191 void hexdump(FILE *out, const uint8_t *src, size_t len) {
192 if (len == 0) {
193 return;
194 }
195 size_t buflen = 0;
196 auto repeated = false;
197 std::array<uint8_t, 16> buf{};
198 auto end = src + len;
199 auto i = src;
200 for (;;) {
201 auto nextlen =
202 std::min(static_cast<size_t>(16), static_cast<size_t>(end - i));
203 if (nextlen == buflen &&
204 std::equal(std::begin(buf), std::begin(buf) + buflen, i)) {
205 // as long as adjacent 16 bytes block are the same, we just
206 // print single '*'.
207 if (!repeated) {
208 repeated = true;
209 fputs("*\n", out);
210 }
211 i += nextlen;
212 continue;
213 }
214 repeated = false;
215 fprintf(out, "%08lx", static_cast<unsigned long>(i - src));
216 if (i == end) {
217 fputc('\n', out);
218 break;
219 }
220 fputs(" ", out);
221 hexdump8(out, i, end);
222 hexdump8(out, i + 8, std::max(i + 8, end));
223 fputc('|', out);
224 auto stop = std::min(i + 16, end);
225 buflen = stop - i;
226 auto p = buf.data();
227 for (; i != stop; ++i) {
228 *p++ = *i;
229 if (0x20 <= *i && *i <= 0x7e) {
230 fputc(*i, out);
231 } else {
232 fputc('.', out);
233 }
234 }
235 fputs("|\n", out);
236 }
237 }
238
make_cid_key(const ngtcp2_cid * cid)239 std::string make_cid_key(const ngtcp2_cid *cid) {
240 return std::string(cid->data, cid->data + cid->datalen);
241 }
242
make_cid_key(const uint8_t * cid,size_t cidlen)243 std::string make_cid_key(const uint8_t *cid, size_t cidlen) {
244 return std::string(cid, cid + cidlen);
245 }
246
straddr(const sockaddr * sa,socklen_t salen)247 std::string straddr(const sockaddr *sa, socklen_t salen) {
248 std::array<char, NI_MAXHOST> host;
249 std::array<char, NI_MAXSERV> port;
250
251 auto rv = getnameinfo(sa, salen, host.data(), host.size(), port.data(),
252 port.size(), NI_NUMERICHOST | NI_NUMERICSERV);
253 if (rv != 0) {
254 std::cerr << "getnameinfo: " << gai_strerror(rv) << std::endl;
255 return "";
256 }
257 std::string res = "[";
258 res.append(host.data(), strlen(host.data()));
259 res += "]:";
260 res.append(port.data(), strlen(port.data()));
261 return res;
262 }
263
strccalgo(ngtcp2_cc_algo cc_algo)264 std::string_view strccalgo(ngtcp2_cc_algo cc_algo) {
265 switch (cc_algo) {
266 case NGTCP2_CC_ALGO_RENO:
267 return "reno";
268 case NGTCP2_CC_ALGO_CUBIC:
269 return "cubic";
270 case NGTCP2_CC_ALGO_BBR:
271 return "bbr";
272 default:
273 assert(0);
274 abort();
275 }
276 }
277
278 namespace {
rws(char c)279 constexpr bool rws(char c) { return c == '\t' || c == ' '; }
280 } // namespace
281
282 std::optional<std::unordered_map<std::string, std::string>>
read_mime_types(const std::string_view & filename)283 read_mime_types(const std::string_view &filename) {
284 std::ifstream f(filename.data());
285 if (!f) {
286 return {};
287 }
288
289 std::unordered_map<std::string, std::string> dest;
290
291 std::string line;
292 while (std::getline(f, line)) {
293 if (line.empty() || line[0] == '#') {
294 continue;
295 }
296
297 auto p = std::find_if(std::begin(line), std::end(line), rws);
298 if (p == std::begin(line) || p == std::end(line)) {
299 continue;
300 }
301
302 auto media_type = std::string{std::begin(line), p};
303 for (;;) {
304 auto ext = std::find_if_not(p, std::end(line), rws);
305 if (ext == std::end(line)) {
306 break;
307 }
308
309 p = std::find_if(ext, std::end(line), rws);
310 dest.emplace(std::string{ext, p}, media_type);
311 }
312 }
313
314 return dest;
315 }
316
format_duration(ngtcp2_duration n)317 std::string format_duration(ngtcp2_duration n) {
318 if (n >= 3600 * NGTCP2_SECONDS && (n % (3600 * NGTCP2_SECONDS)) == 0) {
319 return format_uint(n / (3600 * NGTCP2_SECONDS)) + 'h';
320 }
321 if (n >= 60 * NGTCP2_SECONDS && (n % (60 * NGTCP2_SECONDS)) == 0) {
322 return format_uint(n / (60 * NGTCP2_SECONDS)) + 'm';
323 }
324 if (n >= NGTCP2_SECONDS && (n % NGTCP2_SECONDS) == 0) {
325 return format_uint(n / NGTCP2_SECONDS) + 's';
326 }
327 if (n >= NGTCP2_MILLISECONDS && (n % NGTCP2_MILLISECONDS) == 0) {
328 return format_uint(n / NGTCP2_MILLISECONDS) + "ms";
329 }
330 if (n >= NGTCP2_MICROSECONDS && (n % NGTCP2_MICROSECONDS) == 0) {
331 return format_uint(n / NGTCP2_MICROSECONDS) + "us";
332 }
333 return format_uint(n) + "ns";
334 }
335
336 namespace {
337 std::optional<std::pair<uint64_t, size_t>>
parse_uint_internal(const std::string_view & s)338 parse_uint_internal(const std::string_view &s) {
339 uint64_t res = 0;
340
341 if (s.empty()) {
342 return {};
343 }
344
345 for (size_t i = 0; i < s.size(); ++i) {
346 auto c = s[i];
347 if (c < '0' || '9' < c) {
348 return {{res, i}};
349 }
350
351 auto d = c - '0';
352 if (res > (std::numeric_limits<uint64_t>::max() - d) / 10) {
353 return {};
354 }
355
356 res *= 10;
357 res += d;
358 }
359
360 return {{res, s.size()}};
361 }
362 } // namespace
363
parse_uint(const std::string_view & s)364 std::optional<uint64_t> parse_uint(const std::string_view &s) {
365 auto o = parse_uint_internal(s);
366 if (!o) {
367 return {};
368 }
369 auto [res, idx] = *o;
370 if (idx != s.size()) {
371 return {};
372 }
373 return res;
374 }
375
parse_uint_iec(const std::string_view & s)376 std::optional<uint64_t> parse_uint_iec(const std::string_view &s) {
377 auto o = parse_uint_internal(s);
378 if (!o) {
379 return {};
380 }
381 auto [res, idx] = *o;
382 if (idx == s.size()) {
383 return res;
384 }
385 if (idx + 1 != s.size()) {
386 return {};
387 }
388
389 uint64_t m;
390 switch (s[idx]) {
391 case 'G':
392 case 'g':
393 m = 1 << 30;
394 break;
395 case 'M':
396 case 'm':
397 m = 1 << 20;
398 break;
399 case 'K':
400 case 'k':
401 m = 1 << 10;
402 break;
403 default:
404 return {};
405 }
406
407 if (res > std::numeric_limits<uint64_t>::max() / m) {
408 return {};
409 }
410
411 return res * m;
412 }
413
parse_duration(const std::string_view & s)414 std::optional<uint64_t> parse_duration(const std::string_view &s) {
415 auto o = parse_uint_internal(s);
416 if (!o) {
417 return {};
418 }
419 auto [res, idx] = *o;
420 if (idx == s.size()) {
421 return res * NGTCP2_SECONDS;
422 }
423
424 uint64_t m;
425 if (idx + 1 == s.size()) {
426 switch (s[idx]) {
427 case 'H':
428 case 'h':
429 m = 3600 * NGTCP2_SECONDS;
430 break;
431 case 'M':
432 case 'm':
433 m = 60 * NGTCP2_SECONDS;
434 break;
435 case 'S':
436 case 's':
437 m = NGTCP2_SECONDS;
438 break;
439 default:
440 return {};
441 }
442 } else if (idx + 2 == s.size() && (s[idx + 1] == 's' || s[idx + 1] == 'S')) {
443 switch (s[idx]) {
444 case 'M':
445 case 'm':
446 m = NGTCP2_MILLISECONDS;
447 break;
448 case 'U':
449 case 'u':
450 m = NGTCP2_MICROSECONDS;
451 break;
452 case 'N':
453 case 'n':
454 return res;
455 default:
456 return {};
457 }
458 } else {
459 return {};
460 }
461
462 if (res > std::numeric_limits<uint64_t>::max() / m) {
463 return {};
464 }
465
466 return res * m;
467 }
468
469 namespace {
eat_file(InputIt first,InputIt last)470 template <typename InputIt> InputIt eat_file(InputIt first, InputIt last) {
471 if (first == last) {
472 *first++ = '/';
473 return first;
474 }
475
476 if (*(last - 1) == '/') {
477 return last;
478 }
479
480 auto p = last;
481 for (; p != first && *(p - 1) != '/'; --p)
482 ;
483 if (p == first) {
484 // this should not happened in normal case, where we expect path
485 // starts with '/'
486 *first++ = '/';
487 return first;
488 }
489
490 return p;
491 }
492 } // namespace
493
494 namespace {
eat_dir(InputIt first,InputIt last)495 template <typename InputIt> InputIt eat_dir(InputIt first, InputIt last) {
496 auto p = eat_file(first, last);
497
498 --p;
499
500 assert(*p == '/');
501
502 return eat_file(first, p);
503 }
504 } // namespace
505
normalize_path(const std::string & path)506 std::string normalize_path(const std::string &path) {
507 assert(path.size() <= 1024);
508 assert(path.size() > 0);
509 assert(path[0] == '/');
510
511 std::array<char, 1024> res;
512 auto p = res.data();
513
514 auto first = std::begin(path);
515 auto last = std::end(path);
516
517 *p++ = '/';
518 ++first;
519 for (; first != last && *first == '/'; ++first)
520 ;
521
522 for (; first != last;) {
523 if (*first == '.') {
524 if (first + 1 == last) {
525 break;
526 }
527 if (*(first + 1) == '/') {
528 first += 2;
529 continue;
530 }
531 if (*(first + 1) == '.') {
532 if (first + 2 == last) {
533 p = eat_dir(res.data(), p);
534 break;
535 }
536 if (*(first + 2) == '/') {
537 p = eat_dir(res.data(), p);
538 first += 3;
539 continue;
540 }
541 }
542 }
543 if (*(p - 1) != '/') {
544 p = eat_file(res.data(), p);
545 }
546 auto slash = std::find(first, last, '/');
547 if (slash == last) {
548 p = std::copy(first, last, p);
549 break;
550 }
551 p = std::copy(first, slash + 1, p);
552 first = slash + 1;
553 for (; first != last && *first == '/'; ++first)
554 ;
555 }
556 return std::string{res.data(), p};
557 }
558
make_socket_nonblocking(int fd)559 int make_socket_nonblocking(int fd) {
560 int rv;
561 int flags;
562
563 while ((flags = fcntl(fd, F_GETFL, 0)) == -1 && errno == EINTR)
564 ;
565 if (flags == -1) {
566 return -1;
567 }
568
569 while ((rv = fcntl(fd, F_SETFL, flags | O_NONBLOCK)) == -1 && errno == EINTR)
570 ;
571
572 return rv;
573 }
574
create_nonblock_socket(int domain,int type,int protocol)575 int create_nonblock_socket(int domain, int type, int protocol) {
576 #ifdef SOCK_NONBLOCK
577 auto fd = socket(domain, type | SOCK_NONBLOCK, protocol);
578 if (fd == -1) {
579 return -1;
580 }
581 #else // !SOCK_NONBLOCK
582 auto fd = socket(domain, type, protocol);
583 if (fd == -1) {
584 return -1;
585 }
586
587 make_socket_nonblocking(fd);
588 #endif // !SOCK_NONBLOCK
589
590 return fd;
591 }
592
593 } // namespace util
594
operator <<(std::ostream & os,const ngtcp2_cid & cid)595 std::ostream &operator<<(std::ostream &os, const ngtcp2_cid &cid) {
596 return os << "0x" << util::format_hex(cid.data, cid.datalen);
597 }
598
599 } // namespace ngtcp2
600