From nobody Mon Jul 25 16:20:52 2022 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4Ls4zC0t25z4XrP4; Mon, 25 Jul 2022 16:20:55 +0000 (UTC) (envelope-from jhb@FreeBSD.org) Received: from smtp.freebsd.org (smtp.freebsd.org [IPv6:2610:1c1:1:606c::24b:4]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "smtp.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4Ls4zC0Ny0z3Ttb; Mon, 25 Jul 2022 16:20:55 +0000 (UTC) (envelope-from jhb@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1658766055; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=6ASXtgniAgerEO6u091oW85dbB0QvNqBwnHoiLnZjVQ=; b=EHElFmNfa4H231wxj4HwQ7gjeZcR5IcTiqztHUCLR4vwh1G7GWJ/mw9XQcfmHUBemwoeyc P1ZondGUGqJ71OkunBYygWOYwd4jGxyCr4KF+NKRUxeq6lYvoGnLmc+m8KtTRMLEVDskxG luSDKBFaEQS+YSgo3EeXuxdAPE7+KJCRukeQ0TsvGSuJSVO/ZMvVgLclY0fqy9MxBlRu4P GnZyjbehGdtbqk265J8poYrJ0LVlrVQuDry/NYd0MK3UT0vOXJDPObNh29Ro9bcE1/5x2i I/f8WX4OmSEDcT2K8pNXqa5A8wIg5XjNagwxFT4+EhThcrxAxq0Qar7zGZEh1w== Received: from [10.0.1.4] (ralph.baldwin.cx [66.234.199.215]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits)) (Client did not present a certificate) (Authenticated sender: jhb) by smtp.freebsd.org (Postfix) with ESMTPSA id 4Ls4zB20Z1z1BK9; Mon, 25 Jul 2022 16:20:54 +0000 (UTC) (envelope-from jhb@FreeBSD.org) Message-ID: <1ad901aa-ac87-3725-de1e-3c6a42c50cc2@FreeBSD.org> Date: Mon, 25 Jul 2022 09:20:52 -0700 List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0) Gecko/20100101 Thunderbird/91.11.0 Subject: Re: git: 151abc80cde7 - main - if_vlan: avoid hash table thrashing when adding and removing entries Content-Language: en-US To: Kristof Provost , src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org References: <202207222319.26MNJEVY032683@gitrepo.freebsd.org> From: John Baldwin In-Reply-To: <202207222319.26MNJEVY032683@gitrepo.freebsd.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1658766055; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=6ASXtgniAgerEO6u091oW85dbB0QvNqBwnHoiLnZjVQ=; b=mAFcVK9tLKKAPM3VK1Bdm84rxqn7wY6wRn9c1RFzcBm7oMuHcVw8hg23iBTPntGVvHaqld OMGoNrw/qyVHkLonzabLuTC26AFlG76bJRnH1AToX4LxDIW81ORNuq6F6dPoVJEfuuMuEv Nw4jnK6dQGPdpD18l1W1h5IC+mv4kLdVfOtBBw77vJT3DhaQ8bQE6fF1J05O8hthbkLLAU B2L1w0gFSN6mlxHvWPhsSG+KQFJGGEju9DyPOt4qPaVSHdu3+dJUKpA+mPQSIXoaRsBOBt NT7+mc5dlIHaIkFKJJ3FgvS3XyJUn7jVRTyAsNLyr/+OFw+UK9tprxEIiZw/7g== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1658766055; a=rsa-sha256; cv=none; b=NpPrCRqSvo5mUtyGNeed7xCzHN1b1tPCYJU5dQQHCqqiKf5Qqfx6cs4n9QTCkphzEemkwu thde5YsfNK+MWmRP6nxpyrUNhUEuMJn6D7YYeLeP1/jWtiVQmPGYUiFVotjlU/UudNgd/M +24Tap1SVX8Zb3NMsTVP+hr8XYZCu0nA+UiMjWiEoxzqJiFWHu0pzO81sF/InlHUAWr2i/ Z0aOQ81ZrdhGwkg9uns7UY4Ch0R0PiJ0AkZUsm/59+QS7SPRw0zEKml+IrOn54QTA8wHs9 sCkB1JPW1zfe90rqulT5HzPvkvt6SGWejpe5ywKyq6jaPlrtAHT3ybFipk6K7w== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N On 7/22/22 4:19 PM, Kristof Provost wrote: > The branch main has been updated by kp: > > URL: https://cgit.FreeBSD.org/src/commit/?id=151abc80cde778bc18b91c334d07fbd52bbb38fb > > commit 151abc80cde778bc18b91c334d07fbd52bbb38fb > Author: Kristof Provost > AuthorDate: 2022-07-22 17:17:04 +0000 > Commit: Kristof Provost > CommitDate: 2022-07-22 17:18:41 +0000 > > if_vlan: avoid hash table thrashing when adding and removing entries > > vlan_remhash() uses incorrect value for b. > > When using the default value for VLAN_DEF_HWIDTH (4), the VLAN hash-list table > expands from 16 chains to 32 chains as the 129th entry is added. trunk->hwidth > becomes 5. Say a few more entries are added and there are now 135 entries. > trunk-hwidth will still be 5. If an entry is removed, vlan_remhash() will > calculate a value of 32 for b. refcnt will be decremented to 134. The if > comparison at line 473 will return true and vlan_growhash() will be called. The > VLAN hash-list table will be compressed from 32 chains wide to 16 chains wide. > hwidth will become 4. This is an error, and it can be seen when a new VLAN is > added. The table will again be expanded. If an entry is then removed, again > the table is contracted. > > If the number of VLANS stays in the range of 128-512, each time an insert > follows a remove, the table will expand. Each time a remove follows an > insert, the table will be contracted. > > The fix is simple. The line 473 should test that the number of entries has > decreased such that the table should be contracted using what would be the new > value of hwidth. line 467 should be: > > b = 1 << (trunk->hwidth - 1); > > PR: 265382 > Reviewed by: kp > MFC after: 2 weeks > Sponsored by: NetApp, Inc. This does mean that there are some odd edge cases (e.g. if you remove the 513th entry only to turn around and re-add it) that can still thrash even with this fixed. Not sure if those are worth worrying about though? If they were, perhaps you could imagine some sort of "dampener" where you have to remove some number N of entries to actually rehash to a smaller table. But that is probably rather complex to implement and probably not worth it? -- John Baldwin