ccid3.c (878ac60023c4ba11a7fbf0b1dfe07b8472c0d6ce) ccid3.c (cc0a910b942d11069d35f52b2c0ed0e229e2fb46)
1/*
2 * net/dccp/ccids/ccid3.c
3 *
4 * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand.
5 * Copyright (c) 2005-7 Ian McDonald <ian.mcdonald@jandi.co.nz>
6 *
7 * An implementation of the DCCP protocol
8 *

--- 805 unchanged lines hidden (view full) ---

814 &pinv, sizeof(pinv)) ||
815 dccp_insert_option(sk, skb, TFRC_OPT_RECEIVE_RATE,
816 &x_recv, sizeof(x_recv)))
817 return -1;
818
819 return 0;
820}
821
1/*
2 * net/dccp/ccids/ccid3.c
3 *
4 * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand.
5 * Copyright (c) 2005-7 Ian McDonald <ian.mcdonald@jandi.co.nz>
6 *
7 * An implementation of the DCCP protocol
8 *

--- 805 unchanged lines hidden (view full) ---

814 &pinv, sizeof(pinv)) ||
815 dccp_insert_option(sk, skb, TFRC_OPT_RECEIVE_RATE,
816 &x_recv, sizeof(x_recv)))
817 return -1;
818
819 return 0;
820}
821
822/* calculate first loss interval
823 *
824 * returns estimated loss interval in usecs */
825
826static u32 ccid3_hc_rx_calc_first_li(struct sock *sk,
827 struct list_head *hist_list,
828 struct timeval *last_feedback,
829 u16 s, u32 bytes_recv,
830 u32 previous_x_recv)
831{
832 struct dccp_rx_hist_entry *entry, *next, *tail = NULL;
833 u32 x_recv, p;
834 suseconds_t rtt, delta;
835 struct timeval tstamp = { 0, 0 };
836 int interval = 0;
837 int win_count = 0;
838 int step = 0;
839 u64 fval;
840
841 list_for_each_entry_safe(entry, next, hist_list, dccphrx_node) {
842 if (dccp_rx_hist_entry_data_packet(entry)) {
843 tail = entry;
844
845 switch (step) {
846 case 0:
847 tstamp = entry->dccphrx_tstamp;
848 win_count = entry->dccphrx_ccval;
849 step = 1;
850 break;
851 case 1:
852 interval = win_count - entry->dccphrx_ccval;
853 if (interval < 0)
854 interval += TFRC_WIN_COUNT_LIMIT;
855 if (interval > 4)
856 goto found;
857 break;
858 }
859 }
860 }
861
862 if (unlikely(step == 0)) {
863 DCCP_WARN("%s(%p), packet history has no data packets!\n",
864 dccp_role(sk), sk);
865 return ~0;
866 }
867
868 if (unlikely(interval == 0)) {
869 DCCP_WARN("%s(%p), Could not find a win_count interval > 0."
870 "Defaulting to 1\n", dccp_role(sk), sk);
871 interval = 1;
872 }
873found:
874 if (!tail) {
875 DCCP_CRIT("tail is null\n");
876 return ~0;
877 }
878
879 delta = timeval_delta(&tstamp, &tail->dccphrx_tstamp);
880 DCCP_BUG_ON(delta < 0);
881
882 rtt = delta * 4 / interval;
883 ccid3_pr_debug("%s(%p), approximated RTT to %dus\n",
884 dccp_role(sk), sk, (int)rtt);
885
886 /*
887 * Determine the length of the first loss interval via inverse lookup.
888 * Assume that X_recv can be computed by the throughput equation
889 * s
890 * X_recv = --------
891 * R * fval
892 * Find some p such that f(p) = fval; return 1/p [RFC 3448, 6.3.1].
893 */
894 if (rtt == 0) { /* would result in divide-by-zero */
895 DCCP_WARN("RTT==0\n");
896 return ~0;
897 }
898
899 dccp_timestamp(sk, &tstamp);
900 delta = timeval_delta(&tstamp, last_feedback);
901 DCCP_BUG_ON(delta <= 0);
902
903 x_recv = scaled_div32(bytes_recv, delta);
904 if (x_recv == 0) { /* would also trigger divide-by-zero */
905 DCCP_WARN("X_recv==0\n");
906 if (previous_x_recv == 0) {
907 DCCP_BUG("stored value of X_recv is zero");
908 return ~0;
909 }
910 x_recv = previous_x_recv;
911 }
912
913 fval = scaled_div(s, rtt);
914 fval = scaled_div32(fval, x_recv);
915 p = tfrc_calc_x_reverse_lookup(fval);
916
917 ccid3_pr_debug("%s(%p), receive rate=%u bytes/s, implied "
918 "loss rate=%u\n", dccp_role(sk), sk, x_recv, p);
919
920 if (p == 0)
921 return ~0;
922 else
923 return 1000000 / p;
924}
925
926static void ccid3_hc_rx_update_li(struct sock *sk,
927 struct dccp_li_hist *li_hist,
928 struct list_head *li_hist_list,
929 struct list_head *hist_list,
930 struct timeval *last_feedback,
931 u16 s, u32 bytes_recv,
932 u32 previous_x_recv,
933 u64 seq_loss, u8 win_loss)
934{
935 struct dccp_li_hist_entry *head;
936 u64 seq_temp;
937
938 if (list_empty(li_hist_list)) {
939 if (!dccp_li_hist_interval_new(li_hist, li_hist_list,
940 seq_loss, win_loss))
941 return;
942
943 head = list_entry(li_hist_list->next, struct dccp_li_hist_entry,
944 dccplih_node);
945 head->dccplih_interval =
946 ccid3_hc_rx_calc_first_li(sk, hist_list,
947 last_feedback, s,
948 bytes_recv,
949 previous_x_recv);
950 } else {
951 struct dccp_li_hist_entry *entry;
952 struct list_head *tail;
953
954 head = list_entry(li_hist_list->next, struct dccp_li_hist_entry,
955 dccplih_node);
956 /* FIXME win count check removed as was wrong */
957 /* should make this check with receive history */
958 /* and compare there as per section 10.2 of RFC4342 */
959
960 /* new loss event detected */
961 /* calculate last interval length */
962 seq_temp = dccp_delta_seqno(head->dccplih_seqno, seq_loss);
963 entry = dccp_li_hist_entry_new(li_hist, GFP_ATOMIC);
964
965 if (entry == NULL) {
966 DCCP_BUG("out of memory - can not allocate entry");
967 return;
968 }
969
970 list_add(&entry->dccplih_node, li_hist_list);
971
972 tail = li_hist_list->prev;
973 list_del(tail);
974 kmem_cache_free(li_hist->dccplih_slab, tail);
975
976 /* Create the newest interval */
977 entry->dccplih_seqno = seq_loss;
978 entry->dccplih_interval = seq_temp;
979 entry->dccplih_win_count = win_loss;
980 }
981}
982
983static int ccid3_hc_rx_detect_loss(struct sock *sk,
984 struct dccp_rx_hist_entry *packet)
985{
986 struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
987 struct dccp_rx_hist_entry *rx_hist =
988 dccp_rx_hist_head(&hcrx->ccid3hcrx_hist);
989 u64 seqno = packet->dccphrx_seqno;
990 u64 tmp_seqno;

--- 9 unchanged lines hidden (view full) ---

1000 hcrx->ccid3hcrx_ccval_nonloss = packet->dccphrx_ccval;
1001 goto detect_out;
1002 }
1003
1004
1005 while (dccp_delta_seqno(hcrx->ccid3hcrx_seqno_nonloss, seqno)
1006 > TFRC_RECV_NUM_LATE_LOSS) {
1007 loss = 1;
822static int ccid3_hc_rx_detect_loss(struct sock *sk,
823 struct dccp_rx_hist_entry *packet)
824{
825 struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
826 struct dccp_rx_hist_entry *rx_hist =
827 dccp_rx_hist_head(&hcrx->ccid3hcrx_hist);
828 u64 seqno = packet->dccphrx_seqno;
829 u64 tmp_seqno;

--- 9 unchanged lines hidden (view full) ---

839 hcrx->ccid3hcrx_ccval_nonloss = packet->dccphrx_ccval;
840 goto detect_out;
841 }
842
843
844 while (dccp_delta_seqno(hcrx->ccid3hcrx_seqno_nonloss, seqno)
845 > TFRC_RECV_NUM_LATE_LOSS) {
846 loss = 1;
1008 ccid3_hc_rx_update_li(sk, ccid3_li_hist,
1009 &hcrx->ccid3hcrx_li_hist,
1010 &hcrx->ccid3hcrx_hist,
1011 &hcrx->ccid3hcrx_tstamp_last_feedback,
1012 hcrx->ccid3hcrx_s,
1013 hcrx->ccid3hcrx_bytes_recv,
1014 hcrx->ccid3hcrx_x_recv,
1015 hcrx->ccid3hcrx_seqno_nonloss,
1016 hcrx->ccid3hcrx_ccval_nonloss);
847 dccp_li_update_li(sk, ccid3_li_hist,
848 &hcrx->ccid3hcrx_li_hist,
849 &hcrx->ccid3hcrx_hist,
850 &hcrx->ccid3hcrx_tstamp_last_feedback,
851 hcrx->ccid3hcrx_s,
852 hcrx->ccid3hcrx_bytes_recv,
853 hcrx->ccid3hcrx_x_recv,
854 hcrx->ccid3hcrx_seqno_nonloss,
855 hcrx->ccid3hcrx_ccval_nonloss);
1017 tmp_seqno = hcrx->ccid3hcrx_seqno_nonloss;
1018 dccp_inc_seqno(&tmp_seqno);
1019 hcrx->ccid3hcrx_seqno_nonloss = tmp_seqno;
1020 dccp_inc_seqno(&tmp_seqno);
1021 while (dccp_rx_hist_find_entry(&hcrx->ccid3hcrx_hist,
1022 tmp_seqno, &ccval)) {
1023 hcrx->ccid3hcrx_seqno_nonloss = tmp_seqno;
1024 hcrx->ccid3hcrx_ccval_nonloss = ccval;

--- 281 unchanged lines hidden --- 		856 tmp_seqno = hcrx->ccid3hcrx_seqno_nonloss;
857 dccp_inc_seqno(&tmp_seqno);
858 hcrx->ccid3hcrx_seqno_nonloss = tmp_seqno;
859 dccp_inc_seqno(&tmp_seqno);
860 while (dccp_rx_hist_find_entry(&hcrx->ccid3hcrx_hist,
861 tmp_seqno, &ccval)) {
862 hcrx->ccid3hcrx_seqno_nonloss = tmp_seqno;
863 hcrx->ccid3hcrx_ccval_nonloss = ccval;

--- 281 unchanged lines hidden ---