Date: Tue, 26 Jul 2022 11:03:47 +0200 From: Kristof Provost <kp@FreeBSD.org> To: John Baldwin <jhb@FreeBSD.org> Cc: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org Subject: Re: git: 151abc80cde7 - main - if_vlan: avoid hash table thrashing when adding and removing entries Message-ID: <057F4F07-EFE1-4F67-B15D-857F42C5588D@FreeBSD.org> In-Reply-To: <1ad901aa-ac87-3725-de1e-3c6a42c50cc2@FreeBSD.org> References: <202207222319.26MNJEVY032683@gitrepo.freebsd.org> <1ad901aa-ac87-3725-de1e-3c6a42c50cc2@FreeBSD.org>
index | next in thread | previous in thread | raw e-mail
[-- Attachment #1 --] On 25 Jul 2022, at 18:20, John Baldwin wrote: > 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 <kp@FreeBSD.org> >> AuthorDate: 2022-07-22 17:17:04 +0000 >> Commit: Kristof Provost <kp@FreeBSD.org> >> 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? > Good point, although I think I agree it’s probably not worth worrying too much about this. There’s a tangentially related issue I also want to look at one of these days, namely that the current `trunk->refcnt > (b * b) / 2` check results in far too many entries in each hash row. For example, until 128 vlan interfaces we stick with width = 4, so end up with an average of 8 entries in each row. That means that for every inbound packet we scan through a linked list of 8 entries to find the correct vlan interface. We should tweak the check to reduce this, as all it’ll cost is a tiny bit of memory. (Or we should just default VLAN_ARRAY on, paying a bit more memory for no linked-list scanning). Kristof [-- Attachment #2 --] <!DOCTYPE html> <html> <head> <meta http-equiv="Content-Type" content="text/xhtml; charset=utf-8"> </head> <body><div style="font-family: sans-serif;"><div class="markdown" style="white-space: normal;"> <p dir="auto">On 25 Jul 2022, at 18:20, John Baldwin wrote:</p> </div><div class="plaintext" style="white-space: normal;"><blockquote style="margin: 0 0 5px; padding-left: 5px; border-left: 2px solid #136BCE; color: #136BCE;"><p dir="auto">On 7/22/22 4:19 PM, Kristof Provost wrote:</p> <blockquote style="margin: 0 0 5px; padding-left: 5px; border-left: 2px solid #136BCE; border-left-color: #4B89CF; color: #4B89CF;"><p dir="auto">The branch main has been updated by kp:</p> <p dir="auto">URL: <a href="https://cgit.FreeBSD.org/src/commit/?id=151abc80cde778bc18b91c334d07fbd52bbb38fb">https://cgit.FreeBSD.org/src/commit/?id=151abc80cde778bc18b91c334d07fbd52bbb38fb</a></p>; <p dir="auto">commit 151abc80cde778bc18b91c334d07fbd52bbb38fb <br> Author: Kristof Provost <kp@FreeBSD.org> <br> AuthorDate: 2022-07-22 17:17:04 +0000 <br> Commit: Kristof Provost <kp@FreeBSD.org> <br> CommitDate: 2022-07-22 17:18:41 +0000</p> <p dir="auto"> if_vlan: avoid hash table thrashing when adding and removing entries <br> vlan_remhash() uses incorrect value for b. <br> When using the default value for VLAN_DEF_HWIDTH (4), the VLAN hash-list table <br> expands from 16 chains to 32 chains as the 129th entry is added. trunk->hwidth <br> becomes 5. Say a few more entries are added and there are now 135 entries. <br> trunk-hwidth will still be 5. If an entry is removed, vlan_remhash() will <br> calculate a value of 32 for b. refcnt will be decremented to 134. The if <br> comparison at line 473 will return true and vlan_growhash() will be called. The <br> VLAN hash-list table will be compressed from 32 chains wide to 16 chains wide. <br> hwidth will become 4. This is an error, and it can be seen when a new VLAN is <br> added. The table will again be expanded. If an entry is then removed, again <br> the table is contracted. <br> If the number of VLANS stays in the range of 128-512, each time an insert <br> follows a remove, the table will expand. Each time a remove follows an <br> insert, the table will be contracted. <br> The fix is simple. The line 473 should test that the number of entries has <br> decreased such that the table should be contracted using what would be the new <br> value of hwidth. line 467 should be: <br> b = 1 << (trunk->hwidth - 1); <br> PR: 265382 <br> Reviewed by: kp <br> MFC after: 2 weeks <br> Sponsored by: NetApp, Inc.</p> </blockquote><p dir="auto">This does mean that there are some odd edge cases (e.g. if you remove the 513th entry <br> only to turn around and re-add it) that can still thrash even with this fixed. Not <br> sure if those are worth worrying about though? If they were, perhaps you could <br> imagine some sort of "dampener" where you have to remove some number N of entries <br> to actually rehash to a smaller table. But that is probably rather complex to <br> implement and probably not worth it?</p> <br></blockquote></div> <div class="markdown" style="white-space: normal;"> <p dir="auto">Good point, although I think I agree it’s probably not worth worrying too much about this.</p> <p dir="auto">There’s a tangentially related issue I also want to look at one of these days, namely that the current <code>trunk->refcnt > (b * b) / 2</code> check results in far too many entries in each hash row. For example, until 128 vlan interfaces we stick with width = 4, so end up with an average of 8 entries in each row.<br> That means that for every inbound packet we scan through a linked list of 8 entries to find the correct vlan interface. We should tweak the check to reduce this, as all it’ll cost is a tiny bit of memory. (Or we should just default VLAN_ARRAY on, paying a bit more memory for no linked-list scanning).</p> <p dir="auto">Kristof</p> </div></div></body> </html>help
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?057F4F07-EFE1-4F67-B15D-857F42C5588D>