From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id 656753B29D for ; Wed, 4 Sep 2024 06:05:32 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1725444332; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=7SgMWqwfRAemJXpyVUWXtmjgoS7M6mnA9OsZpEX3Nsc=; b=ZHDl4nNJCBrxSB22NUsiTqSyWZqxx7zwW/jY/pIjOu5AsGUoAqVY6AK6wUzi9OTkeTaDdu AyRIsWiF95+S5odvtQO7TrjoMi32emFlRR8eI7Q28YROpoVuq5d7CvcBrPNstmmjJcyzKt eZkz/CfBquKDitzMdFJoYDKkI7esDjs= Received: from mail-wr1-f69.google.com (mail-wr1-f69.google.com [209.85.221.69]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-177-4PDKSFIHM8e7ANUncqLgmw-1; Wed, 04 Sep 2024 06:05:31 -0400 X-MC-Unique: 4PDKSFIHM8e7ANUncqLgmw-1 Received: by mail-wr1-f69.google.com with SMTP id ffacd0b85a97d-3771b6da3ceso622673f8f.3 for ; Wed, 04 Sep 2024 03:05:30 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1725444329; x=1726049129; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=7SgMWqwfRAemJXpyVUWXtmjgoS7M6mnA9OsZpEX3Nsc=; b=roQzT1ErgRL3k3zB5um7nkRhHkSp6m30xFXMta62E2IhUHZd2C0CjamBBYN3AZRM++ im4OedJ8dmjs4sPcCftyoJ6SD2UJYnO68+amlQ0Pft1b5yRvzjh970CJ2BRLqvd1AFpb gM6Q/9733EmOAWBz9zM4UGWBl2Ba7rZ7VjHP64+Vqc3nEM9Gpy7owEpGgtqdrIWjUGlI l9ZZOE81IgJIl7VkCOz59oe1Ps+YBGwIc3nw3+7WsTclMDbjDJbrI9aFLVHa2Ks4c43t uOPHd7nbTn+XtNTQV+gu8Q2fsjQSpTPo4FPwUL60C1zJQJGXLHKNparJuNa+AOWc/eNM aq3A== X-Forwarded-Encrypted: i=1; AJvYcCXHPWBnAlTspxwVgRDe4NFnuhRGreycWInmfqIZzFA3YgUF/GAB0Z/tkACPEUEcb5qRm2Ec@lists.bufferbloat.net X-Gm-Message-State: AOJu0YyHdl0/XLYQ5zhstnUyIiYyunguy17vtznCGt9YO2xo5B7CS8zv l8UwP9w7qjmwEV956q/y7AxYYN6im0PqTHdpeaBqsNHv+kGTNwgV9Ei5ENdIosG5OCeR916SHk4 lnFOZChoYLK8QbxX3NHfKfW7sGgC8fUSKoJijoSJQ20YGJPdIdkTtGFZVpBg= X-Received: by 2002:adf:e5ce:0:b0:374:c712:507a with SMTP id ffacd0b85a97d-374c71250b6mr6136143f8f.32.1725444329461; Wed, 04 Sep 2024 03:05:29 -0700 (PDT) X-Google-Smtp-Source: AGHT+IFeRTWuKvLCbwapCMh7yQPpztr87Al5rISbB93gh6CJwlRrsshXjrGddYXAlYkLaqWSK1GQPQ== X-Received: by 2002:adf:e5ce:0:b0:374:c712:507a with SMTP id ffacd0b85a97d-374c71250b6mr6136133f8f.32.1725444328978; Wed, 04 Sep 2024 03:05:28 -0700 (PDT) Received: from alrua-x1.borgediget.toke.dk ([45.145.92.2]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-374c0f6f4c4sm11128642f8f.44.2024.09.04.03.05.28 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 04 Sep 2024 03:05:28 -0700 (PDT) Received: by alrua-x1.borgediget.toke.dk (Postfix, from userid 1000) id 5A22F14AE6D7; Wed, 04 Sep 2024 12:05:27 +0200 (CEST) From: =?UTF-8?q?Toke=20H=C3=B8iland-J=C3=B8rgensen?= To: =?UTF-8?q?Toke=20H=C3=B8iland-J=C3=B8rgensen?= , Jamal Hadi Salim , Cong Wang , Jiri Pirko Cc: Dave Taht , =?UTF-8?q?Toke=20H=C3=B8iland-J=C3=B8rgensen?= , "David S. Miller" , Eric Dumazet , Jakub Kicinski , Paolo Abeni , cake@lists.bufferbloat.net, netdev@vger.kernel.org Date: Wed, 4 Sep 2024 12:05:16 +0200 Message-ID: <20240904100516.16926-1-toke@redhat.com> X-Mailer: git-send-email 2.46.0 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Subject: [Cake] [PATCH net-next] sch_cake: constify inverse square root cache X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: Cake - FQ_codel the next generation List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 04 Sep 2024 10:05:32 -0000 From: Dave Taht sch_cake uses a cache of the first 16 values of the inverse square root calculation for the Cobalt AQM to save some cycles on the fast path. This cache is populated when the qdisc is first loaded, but there's really no reason why it can't just be pre-populated. So change it to be pre-populated with constants, which also makes it possible to constify it. This gives a modest space saving for the module (not counting debug data): .text: -224 bytes .rodata: +80 bytes .bss: -64 bytes Total: -192 bytes Signed-off-by: Dave Taht [ fixed up comment, rewrote commit message ] Signed-off-by: Toke Høiland-Jørgensen --- net/sched/sch_cake.c | 53 +++++++++++++++----------------------------- 1 file changed, 18 insertions(+), 35 deletions(-) diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c index 9602dafe32e6..a51c43bde0de 100644 --- a/net/sched/sch_cake.c +++ b/net/sched/sch_cake.c @@ -361,8 +361,24 @@ static const u8 besteffort[] = { static const u8 normal_order[] = {0, 1, 2, 3, 4, 5, 6, 7}; static const u8 bulk_order[] = {1, 0, 2, 3}; +/* There is a big difference in timing between the accurate values placed in the + * cache and the approximations given by a single Newton step for small count + * values, particularly when stepping from count 1 to 2 or vice versa. Hence, + * these values are calculated using eight Newton steps, using the implementation + * below. Above 16, a single Newton step gives sufficient accuracy in either + * direction, given the precision stored. + * + * The magnitude of the error when stepping up to count 2 is such as to give + * the value that *should* have been produced at count 4. + */ + #define REC_INV_SQRT_CACHE (16) -static u32 cobalt_rec_inv_sqrt_cache[REC_INV_SQRT_CACHE] = {0}; +static const u32 inv_sqrt_cache[REC_INV_SQRT_CACHE] = { + ~0, ~0, 3037000500, 2479700525, + 2147483647, 1920767767, 1753413056, 1623345051, + 1518500250, 1431655765, 1358187914, 1294981364, + 1239850263, 1191209601, 1147878294, 1108955788 +}; /* http://en.wikipedia.org/wiki/Methods_of_computing_square_roots * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2) @@ -388,47 +404,14 @@ static void cobalt_newton_step(struct cobalt_vars *vars) static void cobalt_invsqrt(struct cobalt_vars *vars) { if (vars->count < REC_INV_SQRT_CACHE) - vars->rec_inv_sqrt = cobalt_rec_inv_sqrt_cache[vars->count]; + vars->rec_inv_sqrt = inv_sqrt_cache[vars->count]; else cobalt_newton_step(vars); } -/* There is a big difference in timing between the accurate values placed in - * the cache and the approximations given by a single Newton step for small - * count values, particularly when stepping from count 1 to 2 or vice versa. - * Above 16, a single Newton step gives sufficient accuracy in either - * direction, given the precision stored. - * - * The magnitude of the error when stepping up to count 2 is such as to give - * the value that *should* have been produced at count 4. - */ - -static void cobalt_cache_init(void) -{ - struct cobalt_vars v; - - memset(&v, 0, sizeof(v)); - v.rec_inv_sqrt = ~0U; - cobalt_rec_inv_sqrt_cache[0] = v.rec_inv_sqrt; - - for (v.count = 1; v.count < REC_INV_SQRT_CACHE; v.count++) { - cobalt_newton_step(&v); - cobalt_newton_step(&v); - cobalt_newton_step(&v); - cobalt_newton_step(&v); - - cobalt_rec_inv_sqrt_cache[v.count] = v.rec_inv_sqrt; - } -} - static void cobalt_vars_init(struct cobalt_vars *vars) { memset(vars, 0, sizeof(*vars)); - - if (!cobalt_rec_inv_sqrt_cache[0]) { - cobalt_cache_init(); - cobalt_rec_inv_sqrt_cache[0] = ~0; - } } /* CoDel control_law is t + interval/sqrt(count) -- 2.46.0