アプリケーションによる通信のrate limit機能の調査(抽出編)

# きっかけ
ネットワークで帯域制御と言えば、IPスタック内蔵のQoS機能を思いつく。
が、高機能で複雑だったり、権限や全体への影響で、簡単に使えないこともあるのでは。
一方、世のダウンロードアプリには、通信速度に上限を設ける機能がついている。
あれ、どうやってるの?

# 気になるポイント
- 制御方法
    - 基本は、TCPのフロー制御により、受信側が引き抜く速度を落とすことで、送信側が手加減する仕組み、と想像
- 粒度
    - 送受信の単位
    - タイマーの単位
- 精度
    - バースト性の許容度
        - TCPのバッファが大きいと、バーストしてしまうのでは
        - 最近のlarge initial windowは10 MSSだとか[^rfc6928]
    - 遅延による影響
        - 遅延が大きいと、sender-receiver間の制御に時間がかかって、期待通りに動かないのでは
    - slow startとの関係
    - self clockingとの関係

# 事例の調査
## sftp

執筆時(2019/8/9)の[masterのHEAD](https://github.com/openssh/openssh-portable)より

### オプション
[マニュアル](https://man.openbsd.org/sftp)によると、`-l limit`

### オプション->変数
```c:sftp.c
int
main(int argc, char **argv)
{
 :
		case 'l':
			limit_kbps = strtonum(optarg, 1, 100 * 1024 * 1024,
			    &errstr);
```

`bwlimit_in`と`bwlimit_out`に渡る。

```c:sftp-client.c
do_init(int fd_in, int fd_out, u_int transfer_buflen, u_int num_requests,
    u_int64_t limit_kbps)
{
 :
	ret->limit_kbps = limit_kbps;
	if (ret->limit_kbps > 0) {
		bandwidth_limit_init(&ret->bwlimit_in, ret->limit_kbps,
		    ret->transfer_buflen);
		bandwidth_limit_init(&ret->bwlimit_out, ret->limit_kbps,
		    ret->transfer_buflen);
```

最終的に`rate`になる。

```c:misc.c
void
bandwidth_limit_init(struct bwlimit *bw, u_int64_t kbps, size_t buflen)
{
        bw->buflen = buflen;
        bw->rate = kbps;
        bw->thresh = buflen;
        bw->lamt = 0;
        timerclear(&bw->bwstart);
        timerclear(&bw->bwend);
}
```

### 変数の使用

送信と受信の両方に使われる。

```c:sftp-client.c
static void
send_msg(struct sftp_conn *conn, struct sshbuf *m)
{
 :
	if (atomiciov6(writev, conn->fd_out, iov, 2, sftpio,
	    conn->limit_kbps > 0 ? &conn->bwlimit_out : NULL) !=
	    sshbuf_len(m) + sizeof(mlen))
```

```c:sftp-client.c
static void
get_msg_extended(struct sftp_conn *conn, struct sshbuf *m, int initial)
{
 :
	if (atomicio6(read, conn->fd_in, p, msg_len, sftpio,
	    conn->limit_kbps > 0 ? &conn->bwlimit_in : NULL)
	    != msg_len) {
```

`sftpio`は関数ポインタ。

```c:sftp-client.c
static int
sftpio(void *_bwlimit, size_t amount)
{
        struct bwlimit *bwlimit = (struct bwlimit *)_bwlimit;

        refresh_progress_meter(0);
        if (bwlimit != NULL)
                bandwidth_limit(bwlimit, amount);
        return 0;
}
```

### 計算
ここで`rate`が出てくる。
read/write loopにbandwidth-limiting delayをinsertしているのか。コメント重要。

```c:misc.c
/* Callback from read/write loop to insert bandwidth-limiting delays */
void
bandwidth_limit(struct bwlimit *bw, size_t read_len)
{
	u_int64_t waitlen;
	struct timespec ts, rm;

	bw->lamt += read_len;
	if (!timerisset(&bw->bwstart)) {
		monotime_tv(&bw->bwstart);
		return;
	}
	if (bw->lamt < bw->thresh)
		return;

	monotime_tv(&bw->bwend);
	timersub(&bw->bwend, &bw->bwstart, &bw->bwend);
	if (!timerisset(&bw->bwend))
		return;

	bw->lamt *= 8;
	waitlen = (double)1000000L * bw->lamt / bw->rate;

	bw->bwstart.tv_sec = waitlen / 1000000L;
	bw->bwstart.tv_usec = waitlen % 1000000L;

	if (timercmp(&bw->bwstart, &bw->bwend, >)) {
		timersub(&bw->bwstart, &bw->bwend, &bw->bwend);

		/* Adjust the wait time */
		if (bw->bwend.tv_sec) {
			bw->thresh /= 2;
			if (bw->thresh < bw->buflen / 4)
				bw->thresh = bw->buflen / 4;
		} else if (bw->bwend.tv_usec < 10000) {
			bw->thresh *= 2;
			if (bw->thresh > bw->buflen * 8)
				bw->thresh = bw->buflen * 8;
		}

		TIMEVAL_TO_TIMESPEC(&bw->bwend, &ts);
		while (nanosleep(&ts, &rm) == -1) {
			if (errno != EINTR)
				break;
			ts = rm;
		}
	}

	bw->lamt = 0;
	monotime_tv(&bw->bwstart);
}
```

## wget

[wget-1.20.3.tar.gz](https://ftp.gnu.org/gnu/wget/wget-1.20.3.tar.gz)より

### オプション
[マニュアル](https://www.gnu.org/software/wget/manual/wget.html)によると、`--limit-rate=amount`

### オプション->変数
最終的に`limit_rate`になる。

```c:src/main.c
    { "limit-rate", 0, OPT_VALUE, "limitrate", -1 },
```

```c:src/init.c
  { "limitrate",        &opt.limit_rate,        cmd_bytes },
```

### 変数の使用
ながーい受信関数から使用。

```c:src/retr.c
int
fd_read_body (const char *downloaded_filename, int fd, FILE *out, wgint toread, wgint startpos,

              wgint *qtyread, wgint *qtywritten, double *elapsed, int flags,
              FILE *out2)
{
 :
  /* Use a smaller buffer for low requested bandwidths.  For example,
     with --limit-rate=2k, it doesn't make sense to slurp in 16K of
     data and then sleep for 8s.  With buffer size equal to the limit,
     we never have to sleep for more than one second.  */
  if (opt.limit_rate && opt.limit_rate < dlbufsize)
    dlbufsize = opt.limit_rate;
 :
      if (opt.limit_rate)
        limit_bandwidth (ret, timer);
```

受信バッファにも影響か。

```c:src/connect.c
int
connect_to_ip (const ip_address *ip, int port, const char *print)
{
 :
  /* For very small rate limits, set the buffer size (and hence,
     hopefully, the kernel's TCP window size) to the per-second limit.
     That way we should never have to sleep for more than 1s between
     network reads.  */
  if (opt.limit_rate && opt.limit_rate < 8192)
    {
      int bufsize = opt.limit_rate;
      if (bufsize < 512)
        bufsize = 512;          /* avoid pathologically small values */
#ifdef SO_RCVBUF
      if (setsockopt (sock, SOL_SOCKET, SO_RCVBUF,
                  (void *) &bufsize, (socklen_t) sizeof (bufsize)))
        logprintf (LOG_NOTQUIET, _("setsockopt SO_RCVBUF failed: %s\n"),
                   strerror (errno));
#endif
```

### 計算
downloadをpauseしてlimitしている、と。

```c:src/retr.c
/* Limit the bandwidth by pausing the download for an amount of time.
   BYTES is the number of bytes received from the network, and TIMER
   is the timer that started at the beginning of download.  */

static void
limit_bandwidth (wgint bytes, struct ptimer *timer)
{
  double delta_t = ptimer_read (timer) - limit_data.chunk_start;
  double expected;

  limit_data.chunk_bytes += bytes;

  /* Calculate the amount of time we expect downloading the chunk
     should take.  If in reality it took less time, sleep to
     compensate for the difference.  */
  expected = (double) limit_data.chunk_bytes / opt.limit_rate;

  if (expected > delta_t)
    {
      double slp = expected - delta_t + limit_data.sleep_adjust;
      double t0, t1;
      if (slp < 0.2)
        {
          DEBUGP (("deferring a %.2f ms sleep (%s/%.2f).\n",
                   delta_t));
          return;
        }
      DEBUGP (("\nsleeping %.2f ms for %s bytes, adjust %.2f ms\n",
               slp * 1000, number_to_static_string (limit_data.chunk_bytes),
               limit_data.sleep_adjust));

      t0 = ptimer_read (timer);
      xsleep (slp);
      t1 = ptimer_measure (timer);

      /* Due to scheduling, we probably slept slightly longer (or
         shorter) than desired.  Calculate the difference between the
         desired and the actual sleep, and adjust the next sleep by
         that amount.  */
      limit_data.sleep_adjust = slp - (t1 - t0);
      /* If sleep_adjust is very large, it's likely due to suspension
         and not clock inaccuracy.  Don't enforce those.  */
      if (limit_data.sleep_adjust > 0.5)
        limit_data.sleep_adjust = 0.5;
      else if (limit_data.sleep_adjust < -0.5)
        limit_data.sleep_adjust = -0.5;
    }

  limit_data.chunk_bytes = 0;
  limit_data.chunk_start = ptimer_read (timer);
}
```


## curl
執筆時(2019/8/9)の[masterのHEAD](https://github.com/curl/curl)より

### オプション
[マニュアル](https://curl.haxx.se/docs/manpage.html)によると、`--limit-rate <speed>`

### オプション->変数
```c:src/tool_getparam.c
ParameterError getparameter(const char *flag, /* f or -long-flag */
 :
      case 'i': /* --limit-rate */
      {
        curl_off_t value;
        ParameterError pe = GetSizeParameter(global, nextarg, "rate", &value);

        if(pe != PARAM_OK)
           return pe;
        config->recvpersecond = value;
        config->sendpersecond = value;
      }
```

```c:src/tool_operate.c
/* go through the list of URLs and configs and add transfers */

static CURLcode create_transfers(struct GlobalConfig *global,
 :
        my_setopt(curl, CURLOPT_MAX_SEND_SPEED_LARGE,
                  config->sendpersecond);
        my_setopt(curl, CURLOPT_MAX_RECV_SPEED_LARGE,
                  config->recvpersecond);
```

最終的に`max_send_speed`と`max_recv_speed`に渡される。

```c:lib/setopt.c
CURLcode Curl_vsetopt(struct Curl_easy *data, CURLoption option, va_list param)
{
 :
  case CURLOPT_MAX_SEND_SPEED_LARGE:
    /*
     * When transfer uploads are faster then CURLOPT_MAX_SEND_SPEED_LARGE
     * bytes per second the transfer is throttled..
     */
    bigsize = va_arg(param, curl_off_t);
    if(bigsize < 0)
      return CURLE_BAD_FUNCTION_ARGUMENT;
    data->set.max_send_speed = bigsize;
    break;
  case CURLOPT_MAX_RECV_SPEED_LARGE:
    /*
     * When receiving data faster than CURLOPT_MAX_RECV_SPEED_LARGE bytes per
     * second the transfer is throttled..
     */
    bigsize = va_arg(param, curl_off_t);
    if(bigsize < 0)
      return CURLE_BAD_FUNCTION_ARGUMENT;
    data->set.max_recv_speed = bigsize;
    break;
```

バッファサイズにも影響があるらしい。

```c:src/tool_operate.c
        if(config->recvpersecond &&
           (config->recvpersecond < BUFFER_SIZE))
          /* use a smaller sized buffer for better sleeps */
          my_setopt(curl, CURLOPT_BUFFERSIZE, (long)config->recvpersecond);
```

こちらは最終的に`buffer_size`に渡される。受信バッファだけに影響?

```c:lib/setopt.c
  case CURLOPT_BUFFERSIZE:
    /*
     * The application kindly asks for a differently sized receive buffer.
     * If it seems reasonable, we'll use it.
     */
 :
    data->set.buffer_size = arg;
```

### 変数の使用
```c:lib/multi.c
static CURLMcode multi_runsingle(struct Curl_multi *multi,
                                 struct curltime now,
                                 struct Curl_easy *data)
{
 :
        send_timeout_ms = 0;
        if(data->set.max_send_speed > 0)
          send_timeout_ms =
            Curl_pgrsLimitWaitTime(data->progress.uploaded,
                                   data->progress.ul_limit_size,
                                   data->set.max_send_speed,
                                   data->progress.ul_limit_start,
                                   now);

        recv_timeout_ms = 0;
        if(data->set.max_recv_speed > 0)
          recv_timeout_ms =
            Curl_pgrsLimitWaitTime(data->progress.downloaded,
                                   data->progress.dl_limit_size,
                                   data->set.max_recv_speed,
                                   data->progress.dl_limit_start,
                                   now);
```

バッファの方は、いろいろところで使われているが、一旦省略。

### 計算
長いが、コメントが重要そう。
`timediff_t`を返す。

```c:lib/progress.c
/*
 * This is used to handle speed limits, calculating how many milliseconds to
 * wait until we're back under the speed limit, if needed.
 *
 * The way it works is by having a "starting point" (time & amount of data
 * transferred by then) used in the speed computation, to be used instead of
 * the start of the transfer.  This starting point is regularly moved as
 * transfer goes on, to keep getting accurate values (instead of average over
 * the entire transfer).
 *
 * This function takes the current amount of data transferred, the amount at
 * the starting point, the limit (in bytes/s), the time of the starting point
 * and the current time.
 *
 * Returns 0 if no waiting is needed or when no waiting is needed but the
 * starting point should be reset (to current); or the number of milliseconds
 * to wait to get back under the speed limit.
 */
timediff_t Curl_pgrsLimitWaitTime(curl_off_t cursize,
                                  curl_off_t startsize,
                                  curl_off_t limit,
                                  struct curltime start,
                                  struct curltime now)
{
  curl_off_t size = cursize - startsize;
  timediff_t minimum;
  timediff_t actual;

  if(!limit || !size)
    return 0;

  /*
   * 'minimum' is the number of milliseconds 'size' should take to download to
   * stay below 'limit'.
   */
  if(size < CURL_OFF_T_MAX/1000)
    minimum = (time_t) (CURL_OFF_T_C(1000) * size / limit);
  else {
    minimum = (time_t) (size / limit);
    if(minimum < TIMEDIFF_T_MAX/1000)
      minimum *= 1000;
    else
      minimum = TIMEDIFF_T_MAX;
  }

  /*
   * 'actual' is the time in milliseconds it took to actually download the
   * last 'size' bytes.
   */
  actual = Curl_timediff(now, start);
  if(actual < minimum) {
    /* if it downloaded the data faster than the limit, make it wait the
       difference */
    return (minimum - actual);
  }

  return 0;
}
```

# 今後
- 計算部分の理解(未だ本題に到達してませんの…)
- tcpdumpで通信帯域の確認
    - 伝送路帯域・遅延など、条件も変えて
    - 無線などのLong Fat Pipeでは?
- 他のダウンローダーは?
- QUICの時代にはどうなる?

[^rfc6928]: https://tools.ietf.org/html/rfc6928