// 当ack时一个可疑的ack，如sack，或者路由发送的显示拥塞控制，或者当前拥塞状态不是正常状态时。
if (tcp_ack_is_dubious(sk, flag)) {
	/* Advance CWND, if state allows this. */
	if ((flag & FLAG_DATA_ACKED) && !frto_cwnd &&
	    tcp_may_raise_cwnd(sk, flag))
	    // 当窗口仍然满足可以增长的条件时，进入拥塞控制，
	    // 这是一个钩子函数，具体实现由具体拥塞控制算法来实现，
	    // 对于reno而言可能是慢启动，可能是拥塞避免。
		tcp_cong_avoid(sk, ack, prior_in_flight);
	// 处理拥塞状态机，暂时不展开
	tcp_fastretrans_alert(sk, prior_packets - tp->packets_out,
			      flag);
} else {
    // 当这个ack是一个正常的数据确认包，进入拥塞控制
	if ((flag & FLAG_DATA_ACKED) && !frto_cwnd)
		tcp_cong_avoid(sk, ack, prior_in_flight);
}

/*
 * TCP Reno congestion control
 * This is special case used for fallback as well.
 */
/* This is Jacobson's slow start and congestion avoidance.
 * SIGCOMM '88, p. 328.
 */
void tcp_reno_cong_avoid(struct sock *sk, u32 ack, u32 in_flight)
{
	struct tcp_sock *tp = tcp_sk(sk);
	if (!tcp_is_cwnd_limited(sk, in_flight))
		return;
	/* In "safe" area, increase. */
	// 小于阈值会进入慢启动环节，不重置窗口的慢启动。
	if (tp->snd_cwnd <= tp->snd_ssthresh)
		tcp_slow_start(tp);
	/* In dangerous area, increase slowly. */
	else if (sysctl_tcp_abc) {
		/* RFC3465: Appropriate Byte Count
		 * increase once for each full cwnd acked
		 */
		// RFC3465的拥塞避免算法，使用bytes_acked来作为修改拥塞窗口的判断条件
		if (tp->bytes_acked >= tp->snd_cwnd*tp->mss_cache) {
			tp->bytes_acked -= tp->snd_cwnd*tp->mss_cache;
			if (tp->snd_cwnd < tp->snd_cwnd_clamp)
				tp->snd_cwnd++;
		}
	} else {
	    // 拥塞避免
		tcp_cong_avoid_ai(tp, tp->snd_cwnd);
	}
}

/*
 * Slow start is used when congestion window is less than slow start
 * threshold. This version implements the basic RFC2581 version
 * and optionally supports:
 * 	RFC3742 Limited Slow Start  	  - growth limited to max_ssthresh
 *	RFC3465 Appropriate Byte Counting - growth limited by bytes acknowledged
 */
void tcp_slow_start(struct tcp_sock *tp)
{
	int cnt; /* increase in packets */
	/* RFC3465: ABC Slow start
	 * Increase only after a full MSS of bytes is acked
	 *
	 * TCP sender SHOULD increase cwnd by the number of
	 * previously unacknowledged bytes ACKed by each incoming
	 * acknowledgment, provided the increase is not more than L
	 */
    // 不满足tcp abc的窗口增加条件，此时确认的字节数小于mss_cache。
	if (sysctl_tcp_abc && tp->bytes_acked < tp->mss_cache)
		return;
    // RFC 3742，限制慢启动在一个RTT内的burst。
	if (sysctl_tcp_max_ssthresh > 0 && tp->snd_cwnd > sysctl_tcp_max_ssthresh)
		cnt = sysctl_tcp_max_ssthresh >> 1;	/* limited slow start */
	else
	// 加上一个窗口大小，在没有abc的情况，保证在最底下的循环中拥塞窗口大小至少增加1.
		cnt = tp->snd_cwnd;			/* exponential increase */
	/* RFC3465: ABC
	 * We MAY increase by 2 if discovered delayed ack
	 */
	// tcp-abc，慢启动阶段更激进的burst。
	if (sysctl_tcp_abc > 1 && tp->bytes_acked >= 2*tp->mss_cache)
		cnt <<= 1;
	tp->bytes_acked = 0;
    // 更新snd_cwnd_cnt(窗口线性增长器)
    tp->snd_cwnd_cnt += cnt;
    // 线性增长器是窗口的多少倍，窗口就增加多少。
    // 注意：这里的标准场景下的线性增长，每次也只增长1个窗口大小，
    // 但是其仍然是指数增长，因此每个窗口发出去的数据对应一个ack，
    // 而每一个ack都会对应触发一次增长。
    // 以下为一个简单的例子，sender为发送端，receiver为接收端
    // px为包号为x的包，ack x为对第x个包的确认
    // snd_cwnd为拥塞窗口
    // sender                                           receiver
    //  p1 (snd_cwnd 1)  --------------------------->
    //    
    //                   <---------------------------     ack 1
    //  snd_cwnd++ (2)
    //
    //  p2 (snd_cwnd 2)  --------------------------->
    //  p3 (snd_cwnd 2)  ---------------------------> 
    //
    //                   <---------------------------     ack 2
    //  snd_cwnd++ (3)
    //                   <---------------------------     ack 3
    //  snd_cwnd++ (4)
    //
    //  p4 (snd_cwnd 4)  --------------------------->
    //  p5 (snd_cwnd 4)  --------------------------->
    //  p6 (snd_cwnd 4)  --------------------------->
    //  p7 (snd_cwnd 4)  --------------------------->
    //
    //                   <---------------------------     ack 4
    //  snd_cwnd++ (5)
    //                   <---------------------------     ack 5
    //  snd_cwnd++ (6)
    //                   <---------------------------     ack 6
    //  snd_cwnd++ (7)
    //                   <---------------------------     ack 7
    //  snd_cwnd++ (8)
    //  send with snd_cwnd = 8 (p8 - p15)
    // 每一个ack对应增加一个窗口大小，不丢包的场景下相当于窗口以指数上升
    // 1 --> 2 --> 4 --> 8
	while (tp->snd_cwnd_cnt >= tp->snd_cwnd) {
		tp->snd_cwnd_cnt -= tp->snd_cwnd;
		if (tp->snd_cwnd < tp->snd_cwnd_clamp)
			tp->snd_cwnd++;
	}
}

/* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd (or alternative w) */
void tcp_cong_avoid_ai(struct tcp_sock *tp, u32 w)
{
    // 每次cnt++，直到w次后snd_cwnd++，即单位 1 / w
	if (tp->snd_cwnd_cnt >= w) {
		if (tp->snd_cwnd < tp->snd_cwnd_clamp)
			tp->snd_cwnd++;
		tp->snd_cwnd_cnt = 0;
	} else {
		tp->snd_cwnd_cnt++;
	}
}

/* Slow start is used when congestion window is no greater than the slow start
 * threshold. We base on RFC2581 and also handle stretch ACKs properly.
 * We do not implement RFC3465 Appropriate Byte Counting (ABC) per se but
 * something better;) a packet is only considered (s)acked in its entirety to
 * defend the ACK attacks described in the RFC. Slow start processes a stretch
 * ACK of degree N as if N acks of degree 1 are received back to back except
 * ABC caps N to 2. Slow start exits when cwnd grows over ssthresh and
 * returns the leftover acks to adjust cwnd in congestion avoidance mode.
 */
u32 tcp_slow_start(struct tcp_sock *tp, u32 acked)
{
    // 使用确认的包数(其中可能包括sack的确认，或者重传数据的确认都加上)
    // 来更新窗口值，而不是之前的byte。
    // 在函数tcp_clean_rtx_queue中有更新对应的delivered。
    // 其更新的值貌似和MSS有关系。
	u32 cwnd = min(tp->snd_cwnd + acked, tp->snd_ssthresh);
    // 当acked仍然有值，说明超过阈值，处理完slow start后还会进行congestion avoid的处理。
	acked -= cwnd - tp->snd_cwnd;
	tp->snd_cwnd = min(cwnd, tp->snd_cwnd_clamp);
	return acked;
}

/* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd (or alternative w),
 * for every packet that was ACKed.
 */
void tcp_cong_avoid_ai(struct tcp_sock *tp, u32 w, u32 acked)
{
	/* If credits accumulated at a higher w, apply them gently now. */
	// 第一次线性增长计算。
	if (tp->snd_cwnd_cnt >= w) {
		tp->snd_cwnd_cnt = 0;
		tp->snd_cwnd++;
	}
    // 以 acked / snd_cwnd为单位增长。将循环改为除法。
	tp->snd_cwnd_cnt += acked;
	if (tp->snd_cwnd_cnt >= w) {
		u32 delta = tp->snd_cwnd_cnt / w;
		tp->snd_cwnd_cnt -= delta * w;
		tp->snd_cwnd += delta;
	}
	tp->snd_cwnd = min(tp->snd_cwnd, tp->snd_cwnd_clamp);
}

#include <iostream>
#include <vector>
using namespace std;
class tree {
  public:
    void build_tree (int dragon, int damage) {
      vector<int> in; 
      in.push_back (30);
      for (int i = 1; i < dragon + 1; i++) {
        in.push_back (2);
      }   
      build_tree_1 (in, damage, 1.0);
    }   
    bool result_match (vector<int> &in) {
      int cnt = 0;
      for (int i = 1; i < in.size (); i++)
        if (in[i] != 0)
          cnt++;
      return cnt == alive;
    }   
    void build_tree_1 (vector<int> &in, int damage, float p) {
      int count = 0;
      float new_p = 0.0;
#ifdef DEBUG
      for (int i = 0; i < in.size (); i++)
        cout << in[i] << ",";
      cout << "Prob " << p << " else damage " << damage << endl;
#endif
      if (damage == 0) {
        if (result_match (in))
          result += p;
        return;
      }   
      for (int i = 0; i < in.size (); i++) {
        if (in[i] != 0)
          count++;
      }
      if (count == 0)
        return;
      new_p = p / count;
      count = 0;
      for (int i = 0; i < in.size (); i++) {
        /* A dead dragon.  */
        if (in[i] == 0)
          continue;
        in[i]--;
        build_tree_1 (in, damage - 1, new_p);
        in[i]++;
      }
    }
    tree (int dragon, int damage, int _alive) : alive (_alive) {
      result = 0.0;
      build_tree (dragon, damage);
    }
    float get_result () {
      return result;
    }
    ~tree () {
    }
  private:
    int alive;
    float result;
};
int main ()
{
  tree t (3, 8, 1);
  cout << t.get_result () << endl;
  return 0;
}