From patchwork Sun Sep 13 17:28:04 2009 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Gerrit Renker X-Patchwork-Id: 33553 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming@bilbo.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from ozlabs.org (ozlabs.org [203.10.76.45]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "mx.ozlabs.org", Issuer "CA Cert Signing Authority" (verified OK)) by bilbo.ozlabs.org (Postfix) with ESMTPS id 1CBC9B6F2B for ; Mon, 14 Sep 2009 03:29:48 +1000 (EST) Received: by ozlabs.org (Postfix) id BA3C9DDD0C; Mon, 14 Sep 2009 03:29:47 +1000 (EST) Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.176.167]) by ozlabs.org (Postfix) with ESMTP id 596DCDDD0B for ; Mon, 14 Sep 2009 03:29:47 +1000 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754448AbZIMR2N (ORCPT ); Sun, 13 Sep 2009 13:28:13 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1754441AbZIMR2M (ORCPT ); Sun, 13 Sep 2009 13:28:12 -0400 Received: from dee.erg.abdn.ac.uk ([139.133.204.82]:52439 "EHLO erg.abdn.ac.uk" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1751524AbZIMR2L (ORCPT ); Sun, 13 Sep 2009 13:28:11 -0400 Received: from laptev.erg.abdn.ac.uk (Debian-exim@ra-gerrit.erg.abdn.ac.uk [139.133.204.38]) by erg.abdn.ac.uk (8.13.4/8.13.4) with ESMTP id n8DHS4pk025783 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NOT); Sun, 13 Sep 2009 18:28:06 +0100 (BST) Received: from gerrit by laptev.erg.abdn.ac.uk with local (Exim 4.69) (envelope-from ) id 1Mmsrs-0001ay-Ia; Sun, 13 Sep 2009 19:28:04 +0200 Date: Sun, 13 Sep 2009 19:28:04 +0200 From: Gerrit Renker To: Ivo Calado Cc: dccp@vger.kernel.org, netdev@vger.kernel.org Subject: Re: [PATCH 3/5] Implement TFRC-SP calc of mean length of loss intervals, accordingly to section 3 of RFC 4828 Message-ID: <20090913172804.GA6109@gerrit.erg.abdn.ac.uk> Mail-Followup-To: Gerrit Renker , Ivo Calado , dccp@vger.kernel.org, netdev@vger.kernel.org References: <4AA6A263.8000106@embedded.ufcg.edu.br> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <4AA6A263.8000106@embedded.ufcg.edu.br> User-Agent: Mutt/1.5.18 (2008-05-17) X-ERG-MailScanner: Found to be clean X-ERG-MailScanner-From: gerrit@erg.abdn.ac.uk X-Spam-Status: No Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org | Implement TFRC-SP calc of mean length of loss intervals accordingly to | section 3 of RFC 4828 Sorry this also has problems. the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html --- dccp_tree_work5.orig/net/dccp/ccids/lib/loss_interval_sp.c +++ dccp_tree_work5/net/dccp/ccids/lib/loss_interval_sp.c @@ -67,10 +67,11 @@ } } -static void tfrc_sp_lh_calc_i_mean(struct tfrc_loss_hist *lh) +static void tfrc_sp_lh_calc_i_mean(struct tfrc_loss_hist *lh, __u8 curr_ccval) { u32 i_i, i_tot0 = 0, i_tot1 = 0, w_tot = 0; int i, k = tfrc_lh_length(lh) - 1; /* k is as in rfc3448bis, 5.4 */ + u32 losses; if (k <= 0) return; @@ -78,6 +79,15 @@ for (i = 0; i <= k; i++) { i_i = tfrc_lh_get_interval(lh, i); + if (SUB16(curr_ccval, + tfrc_lh_get_loss_interval(lh, i)->li_ccval) <= 8) { + + losses = tfrc_lh_get_loss_interval(lh, i)->li_losses; + + if (losses > 0) + i_i = div64_u64(i_i, losses); + } + (Both 'i_i' and 'losses' are u32, so could write "i_i /= losses" instead.) However, this computation is done in the wrong place: here it is already too late. The N/K in RFC 4828 refers to entering each individual interval I_0, so the division (and the check whether this is a "short" interval) needs to be done when adding the interval, in tfrc_sp_lh_interval_add(). (There also exists a special rule for the open interval I_0, see RFC 5348, 5.3.) A second problem is a divide-by-zero condition encoded in the above: if i_i < losses, the result is 0, if all intervals are 0 then I_mean = 0, and thus p = 1/I_mean triggers a panic. In all other cases, the integer arithmetic has the effect of floor(N/K), i.e. it decreases the interval length. A way out (which does not fix the truncation problem) is to round up: if (losses > 0) i_i = DIV_ROUND_UP(i_i, losses); In fact, we have to do this, to avoid the divide-by-zero condition. The third problem is that the CCVal can be wrong, i.e. "less than 8" can also mean that it just wrapped around one or more times. But this is noted already in RFC 5622, it is a problem of the specification. @@ -87,6 +97,11 @@ } lh->i_mean = max(i_tot0, i_tot1) / w_tot; + BUG_ON(w_tot == 0); + if (SUB16(curr_ccval, tfrc_lh_get_loss_interval(lh, 0)->li_ccval) > 8) + lh->i_mean = max(i_tot0, i_tot1) / w_tot; + else + lh->i_mean = i_tot1 / w_tot; } The line above the BUG_ON is probably a leftover. For the BUG_ON, this would be too late (division by zero). In fact, the BUG_ON is not needed, due to testing for k <= 0, see http://mirror.celinuxforum.org/gitstat//commit-detail.php?commit=eff253c4272cd2aac95ccff46d3d2e1a495f22b1 @@ -127,7 +142,7 @@ return; cur->li_length = len; - tfrc_sp_lh_calc_i_mean(lh); + tfrc_sp_lh_calc_i_mean(lh, dccp_hdr(skb)->dccph_ccval); } Should be division as per above. --- dccp_tree_work5.orig/net/dccp/ccids/lib/loss_interval_sp.h +++ dccp_tree_work5/net/dccp/ccids/lib/loss_interval_sp.h @@ -73,7 +73,8 @@ extern bool tfrc_sp_lh_interval_add(struct tfrc_loss_hist *, struct tfrc_rx_hist *, u32 (*first_li)(struct sock *), - struct sock *); + struct sock *, + __u8 ccval); This function already has the ccval available, so could use it instead of just passing it through. -- To unsubscribe from this list: send the line "unsubscribe netdev" in