[prev in list] [next in list] [prev in thread] [next in thread]
List: tcpdump-workers
Subject: [tcpdump-workers] =?utf-8?q?_Optimizer_uses_stale_control_flow_gr?= =?utf-8?q?aph_data_structures?=
From: "Archit P. Shah via tcpdump-workers" <tcpdump-workers () lists ! tcpdump ! org>
Date: 2020-11-04 6:22:06
Message-ID: mailman.9.1604470960.2098.tcpdump-workers () lists ! tcpdump ! org
[Download RAW message or body]
Return-Path: <archit.shah@alum.mit.edu>
Received: from localhost (localhost [127.0.0.1])
by tuna.sandelman.ca (Postfix) with ESMTP id 92CC838984
for <tcpdump-workers@lists.tcpdump.org>; Wed, 4 Nov 2020 01:22:39 -0500 (EST)
Received: from tuna.sandelman.ca ([127.0.0.1])
by localhost (localhost [127.0.0.1]) (amavisd-new, port 10024)
with LMTP id XD-7Owwlt-x6 for <tcpdump-workers@lists.tcpdump.org>;
Wed, 4 Nov 2020 01:22:37 -0500 (EST)
Received: from NAM02-SN1-obe.outbound.protection.outlook.com \
(mail-sn1nam02on0602.outbound.protection.outlook.com [IPv6:2a01:111:f400:fe44::602]) \
(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client \
certificate requested) by tuna.sandelman.ca (Postfix) with ESMTPS id B280838988
for <tcpdump-workers@lists.tcpdump.org>; Wed, 4 Nov 2020 01:22:36 -0500 (EST)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none;
b=j5MnFQPgNVrpS5wVA+ksMaiiLlE7JnkxL4VGj3df3oS0Iuq+vmvbLlA99QHAzLZsjXmrUuwmoXBlsm0g1FF \
gdwfwJ2YCDGfWmgaO1/3FG4edhWOLvnYoYfn9SQBJesQ8skD/m7qCbm3c3PR7/FsoGP8aOrwmzX7TybuoueTIC \
tKlFgHauy+Gtx1taYUVmj1haO9xR+2YNmeZZ1ffpcD62WWWPXxbWMjL43Qzis108OygYaqPBdNEYTVSMKFQ1Ns \
XEq4VfJnA0N9JQhQaxtMJm7Ewag3oeBe7VGVMqW1klOE3UjBa3Ptr+DBayQ1wBu3YT1BWLPmsejpLbl51YclOXQ==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com;
s=arcselector9901;
h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck;
bh=cYw3VwQdQL6UadnS9MxYG3gepNhWGR7BRiKdJbsH5cE=;
b=kgDjARNC0DvbyDwj4UsReamqAgT0r48tc0qI5OS5mO5jyzsQ9aSAPUM0wDAgQQsUEYQhp99VVmL3dvOXV+7 \
GDPMFXLVNJTaDLhkfQCuHpVVp3vZ8KBnGSEIzVJx8w1RmkM5oTiCr6Hm3zKK3weYLPNAIrrjyvxUIVZ4p2S1Zt \
Cm3knApikM1vw3dxcK/lx7L31jN5ZFMJsJlzXqzQhiBxfwiJYWy0O00202dE0cdufbgw5R/DrFzrv/2FAtCvyf \
rBVX9gSH4Ek/+Fh1+l/R4Yge15hstK6JhyUoOUs9XPTjxgMS2ql627MiJsqA/2xd1NvbBhS7oqgWWDmi73ibDxg==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=temperror (sender ip
is 18.7.68.33) smtp.rcpttodomain=lists.tcpdump.org
smtp.mailfrom=alum.mit.edu; dmarc=none action=none header.from=alum.mit.edu;
dkim=none (message not signed); arc=none
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=alum.mit.edu;
s=selector2;
h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck;
bh=cYw3VwQdQL6UadnS9MxYG3gepNhWGR7BRiKdJbsH5cE=;
b=atI2VDpHh8+Ry88l7a0q3IhGvuJNbEfHwBsi/2lo+33Xs0YecWm9he4DOBsunn4pwj3IITh0BsGSPfOV1Pc \
K5Q88w6LlyE7Q0lyqT/9QYH5L9PPXaexsWqrJdjkq4dR97PONmAHZ6Z3DiOzQZ+H/c/IG+U5tnpJAOhVSFWXu6kk=
Received: from SN2PR01CA0059.prod.exchangelabs.com (2603:10b6:800::27) by
DM6PR12MB4283.namprd12.prod.outlook.com (2603:10b6:5:211::21) with Microsoft
SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id
15.20.3499.27; Wed, 4 Nov 2020 06:22:32 +0000
Received: from SN1NAM02FT034.eop-nam02.prod.protection.outlook.com
(2603:10b6:800:0:cafe::44) by SN2PR01CA0059.outlook.office365.com
(2603:10b6:800::27) with Microsoft SMTP Server (version=TLS1_2,
cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3499.19 via Frontend
Transport; Wed, 4 Nov 2020 06:22:32 +0000
X-MS-Exchange-Authentication-Results: spf=temperror (sender IP is 18.7.68.33)
smtp.mailfrom=alum.mit.edu; lists.tcpdump.org; dkim=none (message not signed)
header.d=none;lists.tcpdump.org; dmarc=none action=none
header.from=alum.mit.edu;
Received-SPF: TempError (protection.outlook.com: error in processing during
lookup of alum.mit.edu: DNS Timeout)
Received: from outgoing-alum.mit.edu (18.7.68.33) by
SN1NAM02FT034.mail.protection.outlook.com (10.152.72.141) with Microsoft SMTP
Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id
15.20.3520.15 via Frontend Transport; Wed, 4 Nov 2020 06:22:30 +0000
Received: from auth2-smtp.messagingengine.com (auth2-smtp.messagingengine.com \
[66.111.4.228]) (authenticated bits=0)
(User authenticated as archit.shah@ALUM.MIT.EDU)
by outgoing-alum.mit.edu (8.14.7/8.12.4) with ESMTP id 0A46MRWG028977
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT)
for <tcpdump-workers@lists.tcpdump.org>; Wed, 4 Nov 2020 01:22:29 -0500
Received: from compute4.internal (compute4.nyi.internal [10.202.2.44])
by mailauth.nyi.internal (Postfix) with ESMTP id D895C27C0054
for <tcpdump-workers@lists.tcpdump.org>; Wed, 4 Nov 2020 01:22:26 -0500 (EST)
Received: from imap9 ([10.202.2.59])
by compute4.internal (MEProxy); Wed, 04 Nov 2020 01:22:26 -0500
X-ME-Sender: <xms:okiiX69Wp-Hj2I3qZ-_lZXP6-LcsoaCNKc9FrUAwS_ReQQvsBUdgig>
<xme:okiiX6s-a1_ujIUGkk3AV9h7naN8_u8Puupk_ixypBhrDLWebxXxjrS5uKRyC8i_O
0BMT7nKCewHcfO6>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedruddtgedgledvucetufdoteggodetrfdotf
fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen
uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfffhffvufgtsehttdertd
erreejnecuhfhrohhmpedftehrtghhihhtucfrrdcuufhhrghhfdcuoegrrhgthhhithdr
shhhrghhsegrlhhumhdrmhhithdrvgguuheqnecuggftrfgrthhtvghrnhepkeefffduje
egleeuteeuffehvddtleehteeuhffgheeludegkedvgeegudfgheelnecuffhomhgrihhn
pehgihhthhhusgdrtghomhdpfhhrvggvsghsugdrohhrghenucevlhhushhtvghrufhiii
gvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpegrrhgthhhithdomhgvshhmthhprghu
thhhphgvrhhsohhnrghlihhthidquddttdejtdduvdegtddquddvuddvtddtieehqdgrrh
gthhhithdrshhhrghhpeeprghluhhmrdhmihhtrdgvughusehfrghsthhmrghilhdrfhhm
X-ME-Proxy: <xmx:okiiXwCp-wHkwmDrtJSu_u_kNfsjhKvTeMwinYDDGhERwlHggsw9uQ>
<xmx:okiiXydh4AJ3eQI5CStkhdmBStchyD0OQbQi-LxvMeTzluy65rhXQA>
<xmx:okiiX_MrCm_WzsjGOgDGfrppyn1r5pAla5DW3QV_xV-Zg_pujtwa_Q>
<xmx:okiiX1ZIBMpzlOvkmdB7IPhxJ5VOKaQ5NpCnKUrVPTacvnRaI_EovQ>
Received: by mailuser.nyi.internal (Postfix, from userid 501)
id A32BF1C01E8; Wed, 4 Nov 2020 01:22:26 -0500 (EST)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.3.0-530-g8da6958-fm-20201021.003-g69105b13-v35
Mime-Version: 1.0
Message-Id: <250b9c4f-238d-4dc4-a8a7-9afed35d53fd@www.fastmail.com>
Date: Tue, 03 Nov 2020 22:22:06 -0800
From: "Archit P. Shah" <archit.shah@alum.mit.edu>
To: tcpdump-workers@lists.tcpdump.org
Subject: =?UTF-8?Q?[tcpdump-workers]_Optimizer_uses_stale_control_flow_graph_data?=
=?UTF-8?Q?_structures?=
Content-Type: text/plain
X-EOPAttributedMessage: 0
X-MS-PublicTrafficType: Email
X-MS-Office365-Filtering-Correlation-Id: ef334d40-56a7-4929-e0f1-08d8808a0286
X-MS-TrafficTypeDiagnostic: DM6PR12MB4283:
X-Microsoft-Antispam-PRVS: \
<DM6PR12MB42839368110C92BEE8C98A92D2EF0@DM6PR12MB4283.namprd12.prod.outlook.com>
X-MS-Oob-TLC-OOBClassifiers: OLM:9508;
X-MS-Exchange-SenderADCheck: 1
X-Microsoft-Antispam: BCL:0;
X-Microsoft-Antispam-Message-Info: \
6f1judPtJHdz6YnDvAG/T3KycbaPQFlOrqebJ2eaZvGat0bBJzLwXzWDl+uFf4jFOxp6OLL/YQmz5f4B2/bePm \
1aXmnEyB/6h95XUgLDPftobtDY5j4VnQ8oAfX+S9quweKaiSAEVDq8oO+v44SNSqfRHnQcAy8V4Oqx/OGy2Iqv \
mwgvnDa1tmLqYBRO/OVo/phWwwsjN5IqZv3n1wW+Lk1pIVjBGvVtFDSrSJdFRU3oIBDfeMQVDqgDkxa3TV/V9C \
8V17StXuxmlG13xdY587xh6bFdeH6NROgeTHWmDLEKF3JekKUzZuJqtx93YU769XRhCFNmJMJgWcV6JbT9EtL9 \
5O/MM20nt/+uQUQFR0IZvuiV0lSvpKeM3QAY+BrMyj00Z3ulVZj5PKDmjMFPNFRftGJeBCGhRNnXltkjm4yfzN \
1MDCod5vdXJ/xxTblyeI33pnJl07CR8sFRPzlFUI42RJmOP00FXMZbSdjWSQc++0adhf+OVDB7NJtVLOopQMKJLRBbLO648IPvga19QXoW+vO8fu2HIbdtvu2zvZg=
X-Forefront-Antispam-Report: \
CIP:18.7.68.33;CTRY:US;LANG:en;SCL:1;SRV:;IPV:CAL;SFV:NSPM;H:outgoing-alum.mit.edu;PTR \
:outgoing-alum.mit.edu;CAT:NONE;SFS:(136003)(39860400002)(376002)(396003)(346002)(4696 \
6005)(70586007)(42186006)(6266002)(70206006)(82310400003)(82740400003)(36906005)(96600 \
5)(316002)(786003)(83380400001)(5660300002)(7596003)(26005)(336012)(478600001)(3169600 \
2)(6666004)(6916009)(8676002)(356005)(75432002)(31686004)(47076004)(86362001)(8936002) \
(63350400001)(186003)(2906002)(9686003)(40310500001)(40720500001);DIR:OUT;SFP:1101;
X-OriginatorOrg: alum.mit.edu
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 04 Nov 2020 06:22:30.7292
(UTC)
X-MS-Exchange-CrossTenant-Network-Message-Id: ef334d40-56a7-4929-e0f1-08d8808a0286
X-MS-Exchange-CrossTenant-Id: 3326b102-c043-408b-a990-b89e477d582f
X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: \
TenantId=3326b102-c043-408b-a990-b89e477d582f;Ip=[18.7.68.33];Helo=[outgoing-alum.mit.edu]
X-MS-Exchange-CrossTenant-AuthSource: \
SN1NAM02FT034.eop-nam02.prod.protection.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Anonymous
X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM6PR12MB4283
I submitted two pull requests fixing bugs in the libpcap optimizer (#972 and #976). \
Both proposed patches are relatively narrow hacks to address specific bugs (links [1] \
and [2] below). I'm writing here because it appears both bugs are specific instances \
of a broader issue that can be resolved with a larger restructuring of the optimzier. \
I have mocked up a patch with such a larger restructuring of the optimizer's looping \
structure. See https://github.com/the-tcpdump-group/libpcap/compare/master...tenarchits:2020-recalculate-cfg
Currently opt_loop builds a series of data structures related to the control flow \
graph (block levels, dominators, use/def information, edge dominators, etc.) and then \
calls opt_blks which walks through the control graph calling opt_blk on each block to \
optimize. The issue is that individual optimizations to one block or statement may \
make alterations that render the computed data structures stale. The next \
optimization may then be relying on stale data. In the bug in link [1] below, \
or_pullup rearranges control flow to invalidate the calculations made by find_dom. \
The next call to or_pullup or and_pullup may rely on stale data. In the bug in link \
[2] below, opt_deadstore deletes instructions impacting the structures computed by \
find_ud, which may impact optimization of the of the next block.
First, my patch uses setjmp/longjmp to jump back to the calculation of the control \
flow graph-related data structures in opt_loop any time an optimization is made that \
invalidates any of the computed structures. Obviously, a more finegrained \
recalculation would be preferable, but I believe this approach prioritizes \
correctness at a reasonable performance penalty.
Second, my patch restructures the control flow in opt_loop. Currently, opt_loop runs \
opt_blks repeatedly until a fixed point is reached. It is first run with \
do_stmts=false to find a fixed point and then with do_stmts=true to find a fixed \
point. With the patch, opt_loop alternates between running opt_blks with \
do_stmts=false and running opt_blks with do_stmts=true until a fixed point is \
reached. Thus first there is a recalculation of the control flow graph data \
structures, then a pass of opt_blks with do_stmts=false and then a pass of opt_blks \
with do_stmts=true.
I hope these observations and this proposal is useful. I welcome any feedback for \
improvements to this patch or suggestions for alternate approaches.
I have also mocked a patch adding tests to the tcpdump project reflecting these two \
bugs. Please let me know if it would helpful for me to create a pull request for \
these tests. See [3].
Links
[1] https://github.com/the-tcpdump-group/libpcap/issues/945
[2] https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=144325
[3] https://github.com/the-tcpdump-group/tcpdump/compare/master...tenarchits:2020-optimizer-tests
Regards,
-- Archit
[Attachment #3 (text/plain)]
_______________________________________________
tcpdump-workers mailing list
tcpdump-workers@lists.tcpdump.org
https://lists.sandelman.ca/mailman/listinfo/tcpdump-workers
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic