loss_interval.c 5.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186
  1. /*
  2. * Copyright (c) 2007 The University of Aberdeen, Scotland, UK
  3. * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand.
  4. * Copyright (c) 2005-7 Ian McDonald <ian.mcdonald@jandi.co.nz>
  5. * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
  6. *
  7. * This program is free software; you can redistribute it and/or modify
  8. * it under the terms of the GNU General Public License as published by
  9. * the Free Software Foundation; either version 2 of the License, or
  10. * (at your option) any later version.
  11. */
  12. #include <net/sock.h>
  13. #include "tfrc.h"
  14. static struct kmem_cache *tfrc_lh_slab __read_mostly;
  15. /* Loss Interval weights from [RFC 3448, 5.4], scaled by 10 */
  16. static const int tfrc_lh_weights[NINTERVAL] = { 10, 10, 10, 10, 8, 6, 4, 2 };
  17. /* implements LIFO semantics on the array */
  18. static inline u8 LIH_INDEX(const u8 ctr)
  19. {
  20. return LIH_SIZE - 1 - (ctr % LIH_SIZE);
  21. }
  22. /* the `counter' index always points at the next entry to be populated */
  23. static inline struct tfrc_loss_interval *tfrc_lh_peek(struct tfrc_loss_hist *lh)
  24. {
  25. return lh->counter ? lh->ring[LIH_INDEX(lh->counter - 1)] : NULL;
  26. }
  27. /* given i with 0 <= i <= k, return I_i as per the rfc3448bis notation */
  28. static inline u32 tfrc_lh_get_interval(struct tfrc_loss_hist *lh, const u8 i)
  29. {
  30. BUG_ON(i >= lh->counter);
  31. return lh->ring[LIH_INDEX(lh->counter - i - 1)]->li_length;
  32. }
  33. /*
  34. * On-demand allocation and de-allocation of entries
  35. */
  36. static struct tfrc_loss_interval *tfrc_lh_demand_next(struct tfrc_loss_hist *lh)
  37. {
  38. if (lh->ring[LIH_INDEX(lh->counter)] == NULL)
  39. lh->ring[LIH_INDEX(lh->counter)] = kmem_cache_alloc(tfrc_lh_slab,
  40. GFP_ATOMIC);
  41. return lh->ring[LIH_INDEX(lh->counter)];
  42. }
  43. void tfrc_lh_cleanup(struct tfrc_loss_hist *lh)
  44. {
  45. if (!tfrc_lh_is_initialised(lh))
  46. return;
  47. for (lh->counter = 0; lh->counter < LIH_SIZE; lh->counter++)
  48. if (lh->ring[LIH_INDEX(lh->counter)] != NULL) {
  49. kmem_cache_free(tfrc_lh_slab,
  50. lh->ring[LIH_INDEX(lh->counter)]);
  51. lh->ring[LIH_INDEX(lh->counter)] = NULL;
  52. }
  53. }
  54. static void tfrc_lh_calc_i_mean(struct tfrc_loss_hist *lh)
  55. {
  56. u32 i_i, i_tot0 = 0, i_tot1 = 0, w_tot = 0;
  57. int i, k = tfrc_lh_length(lh) - 1; /* k is as in rfc3448bis, 5.4 */
  58. if (k <= 0)
  59. return;
  60. for (i = 0; i <= k; i++) {
  61. i_i = tfrc_lh_get_interval(lh, i);
  62. if (i < k) {
  63. i_tot0 += i_i * tfrc_lh_weights[i];
  64. w_tot += tfrc_lh_weights[i];
  65. }
  66. if (i > 0)
  67. i_tot1 += i_i * tfrc_lh_weights[i-1];
  68. }
  69. lh->i_mean = max(i_tot0, i_tot1) / w_tot;
  70. }
  71. /**
  72. * tfrc_lh_update_i_mean - Update the `open' loss interval I_0
  73. * For recomputing p: returns `true' if p > p_prev <=> 1/p < 1/p_prev
  74. */
  75. u8 tfrc_lh_update_i_mean(struct tfrc_loss_hist *lh, struct sk_buff *skb)
  76. {
  77. struct tfrc_loss_interval *cur = tfrc_lh_peek(lh);
  78. u32 old_i_mean = lh->i_mean;
  79. s64 len;
  80. if (cur == NULL) /* not initialised */
  81. return 0;
  82. len = dccp_delta_seqno(cur->li_seqno, DCCP_SKB_CB(skb)->dccpd_seq) + 1;
  83. if (len - (s64)cur->li_length <= 0) /* duplicate or reordered */
  84. return 0;
  85. if (SUB16(dccp_hdr(skb)->dccph_ccval, cur->li_ccval) > 4)
  86. /*
  87. * Implements RFC 4342, 10.2:
  88. * If a packet S (skb) exists whose seqno comes `after' the one
  89. * starting the current loss interval (cur) and if the modulo-16
  90. * distance from C(cur) to C(S) is greater than 4, consider all
  91. * subsequent packets as belonging to a new loss interval. This
  92. * test is necessary since CCVal may wrap between intervals.
  93. */
  94. cur->li_is_closed = 1;
  95. if (tfrc_lh_length(lh) == 1) /* due to RFC 3448, 6.3.1 */
  96. return 0;
  97. cur->li_length = len;
  98. tfrc_lh_calc_i_mean(lh);
  99. return lh->i_mean < old_i_mean;
  100. }
  101. /* Determine if `new_loss' does begin a new loss interval [RFC 4342, 10.2] */
  102. static inline u8 tfrc_lh_is_new_loss(struct tfrc_loss_interval *cur,
  103. struct tfrc_rx_hist_entry *new_loss)
  104. {
  105. return dccp_delta_seqno(cur->li_seqno, new_loss->tfrchrx_seqno) > 0 &&
  106. (cur->li_is_closed || SUB16(new_loss->tfrchrx_ccval, cur->li_ccval) > 4);
  107. }
  108. /**
  109. * tfrc_lh_interval_add - Insert new record into the Loss Interval database
  110. * @lh: Loss Interval database
  111. * @rh: Receive history containing a fresh loss event
  112. * @calc_first_li: Caller-dependent routine to compute length of first interval
  113. * @sk: Used by @calc_first_li in caller-specific way (subtyping)
  114. *
  115. * Updates I_mean and returns 1 if a new interval has in fact been added to @lh.
  116. */
  117. int tfrc_lh_interval_add(struct tfrc_loss_hist *lh, struct tfrc_rx_hist *rh,
  118. u32 (*calc_first_li)(struct sock *), struct sock *sk)
  119. {
  120. struct tfrc_loss_interval *cur = tfrc_lh_peek(lh), *new;
  121. if (cur != NULL && !tfrc_lh_is_new_loss(cur, tfrc_rx_hist_loss_prev(rh)))
  122. return 0;
  123. new = tfrc_lh_demand_next(lh);
  124. if (unlikely(new == NULL)) {
  125. DCCP_CRIT("Cannot allocate/add loss record.");
  126. return 0;
  127. }
  128. new->li_seqno = tfrc_rx_hist_loss_prev(rh)->tfrchrx_seqno;
  129. new->li_ccval = tfrc_rx_hist_loss_prev(rh)->tfrchrx_ccval;
  130. new->li_is_closed = 0;
  131. if (++lh->counter == 1)
  132. lh->i_mean = new->li_length = (*calc_first_li)(sk);
  133. else {
  134. cur->li_length = dccp_delta_seqno(cur->li_seqno, new->li_seqno);
  135. new->li_length = dccp_delta_seqno(new->li_seqno,
  136. tfrc_rx_hist_last_rcv(rh)->tfrchrx_seqno) + 1;
  137. if (lh->counter > (2*LIH_SIZE))
  138. lh->counter -= LIH_SIZE;
  139. tfrc_lh_calc_i_mean(lh);
  140. }
  141. return 1;
  142. }
  143. int __init tfrc_li_init(void)
  144. {
  145. tfrc_lh_slab = kmem_cache_create("tfrc_li_hist",
  146. sizeof(struct tfrc_loss_interval), 0,
  147. SLAB_HWCACHE_ALIGN, NULL);
  148. return tfrc_lh_slab == NULL ? -ENOBUFS : 0;
  149. }
  150. void tfrc_li_exit(void)
  151. {
  152. if (tfrc_lh_slab != NULL) {
  153. kmem_cache_destroy(tfrc_lh_slab);
  154. tfrc_lh_slab = NULL;
  155. }
  156. }