Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1r1Eum-00AA07-CF for pgsql-hackers@arkaria.postgresql.org; Thu, 09 Nov 2023 23:58:24 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1r1Euk-000D51-Tz for pgsql-hackers@arkaria.postgresql.org; Thu, 09 Nov 2023 23:58:22 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1r1Euk-000D4V-D4 for pgsql-hackers@lists.postgresql.org; Thu, 09 Nov 2023 23:58:22 +0000 Received: from mail-vs1-xe2a.google.com ([2607:f8b0:4864:20::e2a]) by magus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1r1Euh-005dtP-SX for pgsql-hackers@lists.postgresql.org; Thu, 09 Nov 2023 23:58:21 +0000 Received: by mail-vs1-xe2a.google.com with SMTP id ada2fe7eead31-45f19811ae5so979523137.0 for ; Thu, 09 Nov 2023 15:58:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bowt-ie.20230601.gappssmtp.com; s=20230601; t=1699574297; x=1700179097; darn=lists.postgresql.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=+NarV0+7AqkdMY2WFulcPx+k+eo9McxTPEevbQm6hyA=; b=oZ3H8w3deOCl70QVbgYIHSt86CJpLbJQNZfh1bdjPZkrQ2o6MD7hyHqJx2PKlAoG16 RXmy8XdrsxeAdubRFkE6miSaMz4wrJ3NHbJ/RYyJNRD7bMkZjsSW/ZkidajinfJqHUYZ 3Si7Z6y6MvliEpls7RC7HQYdAOO+D9KzR+a2KJZBCQGD00FZ4X0xCuEYR2CUyNDz3+iq 1L1gqO3h2ogasvtQ9OwpJ0WvSDblVa+dzfp+A6wgy0c6pUyB6+wS3+Wk1KULNKf4IWLo fHLn2/mt6Bx2opU8pqTMlnHR3xB9MFUukZuZehYu7NCFHDaMVoY9O01w11pjRmmDDWVH Hkbw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1699574297; x=1700179097; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=+NarV0+7AqkdMY2WFulcPx+k+eo9McxTPEevbQm6hyA=; b=l++OQC+xLdQQon/dOZ/euDe30/hCU/i+al7OeXrRi7ShEB7ZPUpX5EDB53rrtqWlb/ i1E153Wk++034gsYRa75v4ymrEHwvubgkzjbHfxIExkbvUdv0A85dblUOQO5QXt+Zm2t Jqma3UUsEXMqfxy0PlRngIlQ7wn899wVc3sAPhwoeRyQYn9JdiDTi9DP9yYC2LbUMezL j9nz69oLZTg2GkVD1LDtChjxRDYw3MBShT5ypmc2kZ6Tbpd1iy3T0AatffLsQirsmSW1 5KtvRQmTxWzEtuEy2hu12ES9gsY3cRhFfU+1YIaHfYEk3+oLci5lS6Pis/vNhHqlP9y7 YvDg== X-Gm-Message-State: AOJu0Yw/Q8UcuhefjF5IzAxR+he9WOL9skxEbBLMp/Q36bWvI71ovj4k 8ysb7Bk1F7S6+Gz7ZuCMeVVPSQ098Ht/ZZMmq8C+ZDmhMbk1hNFMecPsNA== X-Google-Smtp-Source: AGHT+IFk89cU4MMIM15NAZFutVIlCgDtxKAPspGA25DXchKNSIgGfthN8/a0uephgwNClSNZw++6qFC/fPs3oLNcpLI= X-Received: by 2002:a67:f4c9:0:b0:457:ca73:83d6 with SMTP id s9-20020a67f4c9000000b00457ca7383d6mr455118vsn.5.1699574297600; Thu, 09 Nov 2023 15:58:17 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Peter Geoghegan Date: Thu, 9 Nov 2023 15:57:51 -0800 Message-ID: Subject: Re: Optimizing nbtree ScalarArrayOp execution, allowing multi-column ordered scans, skip scan To: Matthias van de Meent Cc: PostgreSQL Hackers , Tom Lane , Tomas Vondra , Jeff Davis , benoit , Alexander Korotkov Content-Type: multipart/mixed; boundary="00000000000047511e0609c0fa37" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --00000000000047511e0609c0fa37 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Tue, Nov 7, 2023 at 5:53=E2=80=AFPM Peter Geoghegan wrote: > If you end up finding a bug in this v6, it'll most likely be a case > where nbtree fails to live up to that. This project is as much about > robust/predictable performance as anything else -- nbtree needs to be > able to cope with practically anything. I suggest that your review > start by trying to break the patch along these lines. I spent some time on this myself today (which I'd already planned on). Attached is an adversarial stress-test, which shows something that must be approaching the worst case for the patch in terms of time spent with a buffer lock held, due to spending so much time evaluating unusually expensive SAOP index quals. The array binary searches that take place with a buffer lock held aren't quite like anything else that nbtree can do right now, so it's worthy of special attention. I thought of several factors that maximize both the number of binary searches within any given _bt_readpage, as well as the cost of each binary search -- the SQL file has full details. My test query is *extremely* unrealistic, since it combines multiple independent unrealistic factors, all of which aim to make life hard for the implementation in one way or another. I hesitate to say that it couldn't be much worse (I only spent a few hours on this), but I'm prepared to say that it seems very unlikely that any real world query could make the patch spend as many cycles in _bt_readpage/_bt_checkkeys as this one does. Perhaps you can think of some other factor that would make this test case even less sympathetic towards the patch, Matthias? The only thing I thought of that I've left out was the use of a custom btree opclass, "unrealistically_slow_ops". Something that calls pg_usleep in its order proc. (I left it out because it wouldn't prove anything.) On my machine, custom instrumentation shows that each call to _bt_readpage made while this query executes (on a patched server) takes just under 1.4 milliseconds. While that is far longer than it usually takes, it's basically acceptable IMV. It's not significantly longer than I'd expect heap_index_delete_tuples() to take on an average day with EBS (or other network-attached storage). But that's a process that happens all the time, with an exclusive buffer lock held on the leaf page throughout -- whereas this is only a shared buffer lock, and involves a query that's just absurd . Another factor that makes this seem acceptable is just how sensitive the test case is to everything going exactly and perfectly wrong, all at the same time, again and again. The test case uses a 32 column index (the INDEX_MAX_KEYS maximum), with a query that has 32 SAOP clauses (one per index column). If I reduce the number of SAOP clauses in the query to (say) 8, I still have a test case that's almost as silly as my original -- but now we only spend ~225 microseconds in each _bt_readpage call (i.e. we spend over 6x less time in each _bt_readpage call). (Admittedly if I also make the CREATE INDEX use only 8 columns, we can fit more index tuples on one page, leaving us at ~800 microseconds). I'm a little surprised that it isn't a lot worse than this, given how far I went. I was a little concerned that it would prove necessary to lock this kind of thing down at some higher level (e.g., in the planner), but that now looks unnecessary. There are much better ways to DOS the server than this. For example, you could run this same query while forcing a sequential scan! That appears to be quite a lot less responsive to interrupts (in addition to being hopelessly slow), probably because it uses parallel workers, each of which will use wildly expensive filter quals that just do a linear scan of the SAOP. --=20 Peter Geoghegan --00000000000047511e0609c0fa37 Content-Type: application/octet-stream; name="nemesis.sql" Content-Disposition: attachment; filename="nemesis.sql" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_lortfacn0 LS0KLS0gQWR2ZXJzYXJpYWwgdGVzdCBjYXNlIGZvciBTQU9QIHBhdGNoCi0tCi0tIFRoZSB0ZXN0 IGNhc2UgKHdoaWNoIGlzIGhpZ2hseSB1bnJlYWxpc3RpYykgc3RyZXNzZXMgdGhlIFNBT1AgcGF0 Y2guICBJbgotLSBwYXJ0aWN1bGFyIGl0IG1heGltaXplcyB0aW1lIHNwZW50IHdpdGggYSBidWZm ZXIgbG9jayBoZWxkIChoZWxkIHdoZW4KLS0gc2Nhbm5pbmcgZWFjaCBsZWFmIHBhZ2UgdXNpbmcg X2J0X3JlYWRwYWdlKS4gIFRoaXMgaXMgbm90IGludGVuZGVkIHRvIGJlCi0tIGFueSBraW5kIG9m IGdlbmVyYWwtcHVycG9zZSBiZW5jaG1hcmsgLS0gaXQncyBqdXN0IGEgbmFycm93bHkgZm9jdXNz ZWQKLS0gc3RyZXNzLXRlc3QuCi0tCi0tIEFsbCBuYnRyZWUgU0FPUCBxdWFscyB1c2UgYmluYXJ5 IHNlYXJjaGVzIGludGVybmFsbHkgKHdpdGggdGhlIHBhdGNoKS4KLS0gVGhlc2UgYXJlIHVudXN1 YWxseSBleHBlbnNpdmUsIGFzIEItVHJlZSBpbmRleCBxdWFscyBnby4gIFdlIHRyeSB0bwotLSBt YXhpbWl6ZS9leGFnZ2VyYXRlIHRoZWlyIGNvc3QuICBPdXIgYXBwcm9hY2ggaXMgdG8gbWF4aW1p emUgdGhlIG51bWJlciBvZgotLSBiaW5hcnkgc2VhcmNoZXMgcGVyIHBhZ2UsIGFuZCB0byBtYWtl IGVhY2ggb2YgdGhvc2UgYmluYXJ5IHNlYXJjaGVzIGFzCi0tIGV4cGVuc2l2ZSBhcyBwb3NzaWJs ZS4gIEFueSB0cmljayBJIGNvdWxkIHRoaW5rIG9mIChzaG9ydCBvZiBjcmVhdGluZyBteQotLSBv d24gY3VzdG9tIGRhdGF0eXBlIHdpdGggZXhjZXB0aW9uYWxseSBleHBlbnNpdmUgY29tcGFyaXNv bnMpIHdhcyB0aHJvd24KLS0gaW50byB0aGUgbWl4LgotLQotLSBOT1RFOiB0aGlzIHF1ZXJ5IGlz bid0IGV4cGVjdGVkIHRvIGV2ZXIgZmluaXNoIG9uIHRoZSBtYXN0ZXIgYnJhbmNoIChJIGxvc3QK LS0gcGF0aWVuY2UgYWZ0ZXIgNiBvciA3IG1pbnV0ZXMpLgotLQotLSBOT1RFOiB0aGUgcXVlcnkg YWxzbyBkb2Vzbid0IGNvbXBsZXRlIGluIGFueXRoaW5nIGxpa2UgYSByZWFzb25hYmxlIHRpbWUK LS0gZnJhbWUgd2hlbiBhbGxvd2VkIHRvIHVzZSBhIChwYXJhbGxlbCkgc2VxdWVudGlhbCBzY2Fu LiAgKFRvIGJlIGZhaXIsIHRoZQotLSBoYXNoIHRhYmxlIG9wdGltaXphdGlvbiBhZGRlZCBieSBj b21taXQgNTBlMTdhZDI4MSBjYW4ndCBiZSB1c2VkIGhlcmUKLS0gYmVjYXVzZSB3ZSBkb24ndCB1 c2UgQ29uc3RzIGluIHRoZSBTQU9QIGNsYXVzZXMuKQoKXHNldCBWRVJCT1NJVFkgdmVyYm9zZQpc cHNldCBwYWdlciBvZmYKXHggb24KCi0tIFNldCBhcnJheSBzaXplcyBmb3IgbGF0ZXI6ClxzZXQg YXJyYXlfc2l6ZSA1MDBfMDAwCgotLSBVc2UgbnVtZXJpYyBmb3IgZXZlcnl0aGluZywgc28gdGhh dCB0aGUgYWRkaXRpb25hbCBtZW1vcnkgaW5kaXJlY3Rpb24KLS0gKG51bWVyaWMgaXMgYSBwYXNz LWJ5LXZhbHVlIHR5cGUpIG1ha2VzIG91ciBiaW5hcnkgc2VhcmNoZXMgbW9yZSBleHBlbnNpdmUK ZHJvcCB0YWJsZSBpZiBleGlzdHMgbmVtZXNpczsKY3JlYXRlIHVubG9nZ2VkIHRhYmxlIG5lbWVz aXMoCiAgcGsgbnVtZXJpYywKICBoYXNoMSBudW1lcmljLAogIGhhc2gyIG51bWVyaWMsCiAgaGFz aDMgbnVtZXJpYywKICBoYXNoNCBudW1lcmljLAogIGhhc2g1IG51bWVyaWMsCiAgaGFzaDYgbnVt ZXJpYywKICBoYXNoNyBudW1lcmljLAogIGhhc2g4IG51bWVyaWMsCiAgaGFzaDkgbnVtZXJpYywK ICBoYXNoMTAgbnVtZXJpYywKICBoYXNoMTEgbnVtZXJpYywKICBoYXNoMTIgbnVtZXJpYywKICBo YXNoMTMgbnVtZXJpYywKICBoYXNoMTQgbnVtZXJpYywKICBoYXNoMTUgbnVtZXJpYywKICBoYXNo MTYgbnVtZXJpYywKICBoYXNoMTcgbnVtZXJpYywKICBoYXNoMTggbnVtZXJpYywKICBoYXNoMTkg bnVtZXJpYywKICBoYXNoMjAgbnVtZXJpYywKICBoYXNoMjEgbnVtZXJpYywKICBoYXNoMjIgbnVt ZXJpYywKICBoYXNoMjMgbnVtZXJpYywKICBoYXNoMjQgbnVtZXJpYywKICBoYXNoMjUgbnVtZXJp YywKICBoYXNoMjYgbnVtZXJpYywKICBoYXNoMjcgbnVtZXJpYywKICBoYXNoMjggbnVtZXJpYywK ICBoYXNoMjkgbnVtZXJpYywKICBoYXNoMzAgbnVtZXJpYywKICBoYXNoMzEgbnVtZXJpYywKICBo YXNoMzIgbnVtZXJpYwopOwoKLS0gQnVsayBsb2FkIHdpdGggcmFuZG9tIGRhdGEKaW5zZXJ0IGlu dG8gbmVtZXNpcwpzZWxlY3QKICBpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCgxKTo6aW50OCks CiAgaGFzaGludDgoaSArIGhhc2hpbnQ0KDIpOjppbnQ4KSwKICBoYXNoaW50OChpICsgaGFzaGlu dDQoMyk6OmludDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCg0KTo6aW50OCksCiAgaGFzaGlu dDgoaSArIGhhc2hpbnQ0KDUpOjppbnQ4KSwKICBoYXNoaW50OChpICsgaGFzaGludDQoNik6Omlu dDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCg3KTo6aW50OCksCiAgaGFzaGludDgoaSArIGhh c2hpbnQ0KDgpOjppbnQ4KSwKICBoYXNoaW50OChpICsgaGFzaGludDQoOSkpOjppbnQ4LAogIGhh c2hpbnQ4KGkgKyBoYXNoaW50NCgxMCk6OmludDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCgx MSk6OmludDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCgxMik6OmludDgpLAogIGhhc2hpbnQ4 KGkgKyBoYXNoaW50NCgxMyk6OmludDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCgxNCk6Omlu dDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCgxNSk6OmludDgpLAogIGhhc2hpbnQ4KGkgKyBo YXNoaW50NCgxNik6OmludDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCgxNyk6OmludDgpLAog IGhhc2hpbnQ4KGkgKyBoYXNoaW50NCgxOCk6OmludDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50 NCgxOSk6OmludDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCgyMCk6OmludDgpLAogIGhhc2hp bnQ4KGkgKyBoYXNoaW50NCgyMSk6OmludDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCgyMik6 OmludDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCgyMyk6OmludDgpLAogIGhhc2hpbnQ4KGkg KyBoYXNoaW50NCgyNCk6OmludDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCgyNSk6OmludDgp LAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCgyNik6OmludDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNo aW50NCgyNyk6OmludDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCgyOCk6OmludDgpLAogIGhh c2hpbnQ4KGkgKyBoYXNoaW50NCgyOSk6OmludDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCgz MCk6OmludDgpLAogIGhhc2hpbnQ4KGkgKyBoYXNoaW50NCgzMSk6OmludDgpLAogIGhhc2hpbnQ4 KGkgKyBoYXNoaW50NCgzMik6OmludDgpCmZyb20KICBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5 X3NpemUpIGk7CgotLSBDcmVhdGUgaW5kZXggYWZ0ZXIgYnVsayBsb2FkLCB3aXRoIGZpbGxmYWN0 b3I9MTAwLCBzbyB0aGF0IGVhY2ggbGVhZiBwYWdlCi0tIGlzIHBhY2tlZCB0byB0aGUgYnJpbS4g IFRoYXQgd2F5IHRoZXJlJ2xsIGJlIG1vcmUgYmluYXJ5IHNlYXJjaGVzIHBlcgotLSBfYnRfcmVh ZHBhZ2UgY2FsbDogZWFjaCBjYWxsIGhhcyBtb3JlIHR1cGxlcyB0byBwcm9jZXNzIGF0IGEgdGlt ZS4KLS0KLS0gVGhpcyBpbmRleCBoYXMgdGhlIG1heGltdW0gMzIgKGFrYSBJTkRFWF9NQVhfS0VZ UykgaW5kZXggY29sdW1ucy4KLS0gSGVyZSBhcmUgd2hhdCB0d28gYWRqYWNlbnQgaW5kZXggdHVw bGVzIGZyb20gb3VyIGluZGV4IGxvb2sgbGlrZToKLS0KLS0gKGhhc2gxLCBoYXNoMiwgaGFzaDMs IC4uLiwgaGFzaDMyKT0oLTIxNDY2MTgwMDcsICAgODY3MTU4NzEzLCAtOTgwNTE3Nzk2LCAgLi4u LCAgLTQ3MzgxOTk4NSkKLS0gKGhhc2gxLCBoYXNoMiwgaGFzaDMsIC4uLiwgaGFzaDMyKT0oLTIx NDY2MTczNzYsIC0xOTkwNDM0NTUzLCAgMjgzMTA4NTAzLCAgLi4uLCAgLTY1MjUwNTA4MikKLS0K LS0gVGhlcmUgaXMgbm8gbG9jYWxpdHksIGV4Y2VwdCB3aXRoIHRoZSBmaXJzdCBjb2x1bW4sICJo YXNoMSIuICBUaGUgb3RoZXIgMzEKLS0gY29sdW1ucyBjb250YWluIGRhdGEgdGhhdCBpcyBjb21w bGV0ZWx5IHJhbmRvbTogaXQgaGFzIG5vIHJlbGF0aW9uc2hpcCB3aXRoCi0tIG90aGVyIGRhdHVt cyBmcm9tIHRoZSBzYW1lIHR1cGxlLCBub3IgaXMgaXQgY29ycmVsYXRlZCBpbiBhbnkgd2F5IHdp dGgKLS0gZGF0dW1zIGZyb20gYWRqYWNlbnQgdHVwbGVzLiAgV2UgYWltIHRvIG1pbmltaXplIGxv Y2FsaXR5IG9mIGFjY2VzcyAoZXZlcnkKLS0gZm9ybSB5b3UgY2FuIHRoaW5rIG9mKSBkdXJpbmcg b3VyIGluZGV4IHNjYW4uCi0tCi0tIFhYWCBXZSBjYW4gb25seSBmaXQgMjYgb2YgdGhlc2UgdHVw bGVzIG9uIGFuIDhLaUIgbGVhZiBwYWdlIChwbHVzIGEgbXVjaAotLSBzbWFsbGVyIHRydW5jYXRl ZCBoaWdoIGtleSksIGV2ZW4gd2l0aCBmaWxsZmFjdG9yPTEwMCAoYW5kIG5vIHVzZSBvZgotLSBk ZWR1cGxpY2F0aW9uKS4gIFRoaXMgdHVwbGUgc2hhcGUgc2VlbXMgbGlrZWx5IHRvIGJlIGp1c3Qg YWJvdXQgdGhlIGJlc3QKLS0gd2F5IG9mIG1heGltaXppbmcgdGhlIG51bWJlciBvZiBiaW5hcnkg c2VhcmNoZXMgcmVxdWlyZWQgcGVyIF9idF9yZWFkcGFnZQotLSBjYWxsLCBkZXNwaXRlIHRoZSBh dHRlbmRhbnQgImRvd25zaWRlIiBvZiBoYXZpbmcgbGFyZ2VyIHR1cGxlcyB0aGF0IGZvcmNlCi0t IHVzIHRvIHBsYWNlIGZld2VyIGluZGl2aWR1YWwgdHVwbGVzIG9uIGVhY2ggcGFnZS4KY3JlYXRl IGluZGV4IG5lbWVzaXNfaWR4IG9uIG5lbWVzaXMgKAogIGhhc2gxLAogIGhhc2gyLAogIGhhc2gz LAogIGhhc2g0LAogIGhhc2g1LAogIGhhc2g2LAogIGhhc2g3LAogIGhhc2g4LAogIGhhc2g5LAog IGhhc2gxMCwKICBoYXNoMTEsCiAgaGFzaDEyLAogIGhhc2gxMywKICBoYXNoMTQsCiAgaGFzaDE1 LAogIGhhc2gxNiwKICBoYXNoMTcsCiAgaGFzaDE4LAogIGhhc2gxOSwKICBoYXNoMjAsCiAgaGFz aDIxLAogIGhhc2gyMiwKICBoYXNoMjMsCiAgaGFzaDI0LAogIGhhc2gyNSwKICBoYXNoMjYsCiAg aGFzaDI3LAogIGhhc2gyOCwKICBoYXNoMjksCiAgaGFzaDMwLAogIGhhc2gzMSwKICBoYXNoMzIK KQp3aXRoIChmaWxsZmFjdG9yPTEwMCk7CgotLSBCZSB0aWR5OiBtYWtlIHN1cmUgdGhhdCB3ZSBj YW4gZG8gYW4gaW5kZXgtb25seSBzY2FuICh0aGUgZmFjdCB0aGF0IHRoaXMgaXMKLS0gYW4gdW5s b2dnZWQgdGFibGUgYWxzbyBoZWxwcyBtYWtlIHRoYXQgaGFwcGVuIHJlbGlhYmx5KQpWQUNVVU0g bmVtZXNpczsKCi0tIFRoZSBxdWVyeS90ZXN0IGl0c2VsZiBwZXJmb3JtcyAyNiozMj04MzIgYmlu YXJ5IHNlYXJjaGVzIHBlciBfYnRfcmVhZHBhZ2UgY2FsbC4KLS0KLS0gSGVyZSBpdCdzIGltcG9y dGFudCB0aGF0IGV2ZXJ5IHR1cGxlIGFjdHVhbGx5IHNhdGlzZnkgb3VyIGV4cGVuc2l2ZSBxdWFs cwotLSBmb3IgYWxsIDMyIGluZGV4IGF0dHJpYnV0ZXMuICBJZiB0aGF0IGRpZG4ndCBoYXBwZW4g KGlmIGFuIGVhcmxpZXIgYmluYXJ5Ci0tIHNlYXJjaCBkaWRuJ3QgZmluZCBhIHByZWNpc2UgbWF0 Y2gpIHRoZW4gd2Ugd291bGRuJ3QgaGF2ZSB0byBkbyByZWFsIGJpbmFyeQotLSBzZWFyY2hlcyBm b3IgbGF0ZXIgYXR0cmlidXRlcyBmcm9tIHRoYXQgc2FtZSB0dXBsZS4KLS0KLS0gUmV1c2luZyB0 aGUgYm91bmRzIGZyb20gZWFybGllciBsb3dlci1vcmRlciBhdHRyaWJ1dGVzIHdpbGwgYWx3YXlz IGJlCi0tIGltcG9zc2libGUsIGJlY2F1c2UgKGJhcnJpbmcgdGhlIG9kZCBoYXNoIGNvbGxpc2lv bikgbm8gaGFzaDEvbW9zdAotLSBzaWduaWZpY2FudCBjb2x1bW4gdmFsdWUgd2lsbCBiZSByZXBl YXRlZC4KLS0KLS0gWFhYIEFzIHdpdGggbWFueSBvZiBteSBzdHJlc3MgdGVzdHMgdGFyZ2V0aW5n IHRoaXMgc2FtZSBwYXRjaCwgdGhpcwotLSBzdHJlc3MtdGVzdCBxdWVyeSBlZmZlY3RpdmVseSBk ZWdlbmVyYXRlcyBpbnRvIGEgZnVsbCBpbmRleCBzY2FuIChpdCBzY2FucwotLSBldmVyeSBsZWFm IHBhZ2UgZXhhY3RseSBvbmNlKSB3aXRoIHRoZSBwYXRjaCBhcHBsaWVkLiAgVGhpcyBudW1iZXIg b2YKLS0gbGVhZiBwYWdlcyBpbiB0aGUgaW5kZXggYmVjb21lcyB0aGUgImxvZ2ljYWwgSS9PIHdv cnN0IGNhc2UiIGZvciBfZXZlcnlfCi0tIGluZGV4IHNjYW4gd2l0aCB0aGUgcGF0Y2guICBTbyBs b2dpY2FsIEkvTyAoYnVmZmVycyBoaXQvcmVhZC93aGF0ZXZlcikgaXNuJ3QKLS0gYSBjb3N0IHdl IG5lZWQgdG8gd29ycnkgYWJvdXQgaGVyZS4KCnByZXBhcmUgbmVtZXNpc19xdWVyeSBhcwpzZWxl Y3QgY291bnQoKikgICAgICAgICAtLSBjb3VudCgqKSBtYXRjaGVzIG91ciA6YXJyYXlfc2l6ZSAo aW5kZXggcXVhbHMgc2F0aXNmaWVkIGJ5IGV2ZXJ5IGluZGV4IHR1cGxlKQpmcm9tIG5lbWVzaXMK d2hlcmUKICBoYXNoMSA9IGFueSAoYXJyYXlbKCBzZWxlY3QgYXJyYXlfYWdnKGhhc2hpbnQ4KGkg KyBoYXNoaW50NCgxKTo6aW50OCkpIGZyb20gZ2VuZXJhdGVfc2VyaWVzKDEsIDphcnJheV9zaXpl KSBpKV0pCiAgYW5kCiAgaGFzaDIgPSBhbnkgKGFycmF5Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNo aW50OChpICsgaGFzaGludDQoMik6OmludDgpKSBmcm9tIGdlbmVyYXRlX3NlcmllcygxLCA6YXJy YXlfc2l6ZSkgaSldKQogIGFuZAogIGhhc2gzID0gYW55IChhcnJheVsoIHNlbGVjdCBhcnJheV9h Z2coaGFzaGludDgoaSArIGhhc2hpbnQ0KDMpOjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMo MSwgOmFycmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNoNCA9IGFueSAoYXJyYXlbKCBzZWxlY3Qg YXJyYXlfYWdnKGhhc2hpbnQ4KGkgKyBoYXNoaW50NCg0KTo6aW50OCkpIGZyb20gZ2VuZXJhdGVf c2VyaWVzKDEsIDphcnJheV9zaXplKSBpKV0pCiAgYW5kCiAgaGFzaDUgPSBhbnkgKGFycmF5Wygg c2VsZWN0IGFycmF5X2FnZyhoYXNoaW50OChpICsgaGFzaGludDQoNSk6OmludDgpKSBmcm9tIGdl bmVyYXRlX3NlcmllcygxLCA6YXJyYXlfc2l6ZSkgaSldKQogIGFuZAogIGhhc2g2ID0gYW55IChh cnJheVsoIHNlbGVjdCBhcnJheV9hZ2coaGFzaGludDgoaSArIGhhc2hpbnQ0KDYpOjppbnQ4KSkg ZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNoNyA9 IGFueSAoYXJyYXlbKCBzZWxlY3QgYXJyYXlfYWdnKGhhc2hpbnQ4KGkgKyBoYXNoaW50NCg3KTo6 aW50OCkpIGZyb20gZ2VuZXJhdGVfc2VyaWVzKDEsIDphcnJheV9zaXplKSBpKV0pCiAgYW5kCiAg aGFzaDggPSBhbnkgKGFycmF5Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNoaW50OChpICsgaGFzaGlu dDQoOCk6OmludDgpKSBmcm9tIGdlbmVyYXRlX3NlcmllcygxLCA6YXJyYXlfc2l6ZSkgaSldKQog IGFuZAogIGhhc2g5ID0gYW55IChhcnJheVsoIHNlbGVjdCBhcnJheV9hZ2coaGFzaGludDgoaSAr IGhhc2hpbnQ0KDkpOjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUp IGkpXSkKICBhbmQKICBoYXNoMTAgPSBhbnkgKGFycmF5Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNo aW50OChpICsgaGFzaGludDQoMTApOjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFy cmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNoMTEgPSBhbnkgKGFycmF5Wyggc2VsZWN0IGFycmF5 X2FnZyhoYXNoaW50OChpICsgaGFzaGludDQoMTEpOjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJp ZXMoMSwgOmFycmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNoMTIgPSBhbnkgKGFycmF5Wyggc2Vs ZWN0IGFycmF5X2FnZyhoYXNoaW50OChpICsgaGFzaGludDQoMTIpOjppbnQ4KSkgZnJvbSBnZW5l cmF0ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNoMTMgPSBhbnkgKGFy cmF5Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNoaW50OChpICsgaGFzaGludDQoMTMpOjppbnQ4KSkg ZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNoMTQg PSBhbnkgKGFycmF5Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNoaW50OChpICsgaGFzaGludDQoMTQp OjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUpIGkpXSkKICBhbmQK ICBoYXNoMTUgPSBhbnkgKGFycmF5Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNoaW50OChpICsgaGFz aGludDQoMTUpOjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUpIGkp XSkKICBhbmQKICBoYXNoMTYgPSBhbnkgKGFycmF5Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNoaW50 OChpICsgaGFzaGludDQoMTYpOjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5 X3NpemUpIGkpXSkKICBhbmQKICBoYXNoMTcgPSBhbnkgKGFycmF5Wyggc2VsZWN0IGFycmF5X2Fn ZyhoYXNoaW50OChpICsgaGFzaGludDQoMTcpOjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMo MSwgOmFycmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNoMTggPSBhbnkgKGFycmF5Wyggc2VsZWN0 IGFycmF5X2FnZyhoYXNoaW50OChpICsgaGFzaGludDQoMTgpOjppbnQ4KSkgZnJvbSBnZW5lcmF0 ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNoMTkgPSBhbnkgKGFycmF5 Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNoaW50OChpICsgaGFzaGludDQoMTkpOjppbnQ4KSkgZnJv bSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNoMjAgPSBh bnkgKGFycmF5Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNoaW50OChpICsgaGFzaGludDQoMjApOjpp bnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUpIGkpXSkKICBhbmQKICBo YXNoMjEgPSBhbnkgKGFycmF5Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNoaW50OChpICsgaGFzaGlu dDQoMjEpOjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUpIGkpXSkK ICBhbmQKICBoYXNoMjIgPSBhbnkgKGFycmF5Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNoaW50OChp ICsgaGFzaGludDQoMjIpOjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5X3Np emUpIGkpXSkKICBhbmQKICBoYXNoMjMgPSBhbnkgKGFycmF5Wyggc2VsZWN0IGFycmF5X2FnZyho YXNoaW50OChpICsgaGFzaGludDQoMjMpOjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwg OmFycmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNoMjQgPSBhbnkgKGFycmF5Wyggc2VsZWN0IGFy cmF5X2FnZyhoYXNoaW50OChpICsgaGFzaGludDQoMjQpOjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9z ZXJpZXMoMSwgOmFycmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNoMjUgPSBhbnkgKGFycmF5Wygg c2VsZWN0IGFycmF5X2FnZyhoYXNoaW50OChpICsgaGFzaGludDQoMjUpOjppbnQ4KSkgZnJvbSBn ZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNoMjYgPSBhbnkg KGFycmF5Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNoaW50OChpICsgaGFzaGludDQoMjYpOjppbnQ4 KSkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNo MjcgPSBhbnkgKGFycmF5Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNoaW50OChpICsgaGFzaGludDQo MjcpOjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUpIGkpXSkKICBh bmQKICBoYXNoMjggPSBhbnkgKGFycmF5Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNoaW50OChpICsg aGFzaGludDQoMjgpOjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUp IGkpXSkKICBhbmQKICBoYXNoMjkgPSBhbnkgKGFycmF5Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNo aW50OChpICsgaGFzaGludDQoMjkpOjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFy cmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNoMzAgPSBhbnkgKGFycmF5Wyggc2VsZWN0IGFycmF5 X2FnZyhoYXNoaW50OChpICsgaGFzaGludDQoMzApOjppbnQ4KSkgZnJvbSBnZW5lcmF0ZV9zZXJp ZXMoMSwgOmFycmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNoMzEgPSBhbnkgKGFycmF5Wyggc2Vs ZWN0IGFycmF5X2FnZyhoYXNoaW50OChpICsgaGFzaGludDQoMzEpOjppbnQ4KSkgZnJvbSBnZW5l cmF0ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUpIGkpXSkKICBhbmQKICBoYXNoMzIgPSBhbnkgKGFy cmF5Wyggc2VsZWN0IGFycmF5X2FnZyhoYXNoaW50OChpICsgaGFzaGludDQoMzIpOjppbnQ4KSkg ZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwgOmFycmF5X3NpemUpIGkpXSkKICA7CgotLSBOb3cgcnVu IHRoZSBxdWVyeToKZXhlY3V0ZSBuZW1lc2lzX3F1ZXJ5OwoKLS0gVXNpbmcgY3VzdG9tIGluc3Ry dW1lbnRhdGlvbiB0byBtZWFzdXJlIGhvdyBtdWNoIHRpbWUgaXMgc3BlbnQgaW4KLS0gX2J0X3Jl YWRwYWdlIChhbmQgZGV0ZXJtaW5pbmcgb3VyIGV4cG9zdXJlIHRvIGJ1ZmZlci1sb2NrLWhlbGQt dG9vLWxvbmcKLS0gcHJvYmxlbXMpIGlzIGxlZnQgYXMgYW4gZXhlcmNpc2UgZm9yIHRoZSByZWFk ZXIK --00000000000047511e0609c0fa37--