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 1qP1XJ-009ks8-Sv for pgsql-hackers@arkaria.postgresql.org; Thu, 27 Jul 2023 14:00:14 +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 1qP1XI-00AI40-AI for pgsql-hackers@arkaria.postgresql.org; Thu, 27 Jul 2023 14:00:12 +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 1qP1XH-00AI3s-UQ for pgsql-hackers@lists.postgresql.org; Thu, 27 Jul 2023 14:00:12 +0000 Received: from mail-pg1-x530.google.com ([2607:f8b0:4864:20::530]) by magus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1qP1XD-000heX-Eq for pgsql-hackers@lists.postgresql.org; Thu, 27 Jul 2023 14:00:11 +0000 Received: by mail-pg1-x530.google.com with SMTP id 41be03b00d2f7-563e21a6011so673559a12.0 for ; Thu, 27 Jul 2023 07:00:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1690466405; x=1691071205; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=2CPKCDOi6mJwjL6XSC+rDJJpHneYnFLHKwvtm+s6raU=; b=odJ+GedOCrZffvfpUtfa7Ugl1IyJSgEH8UkGsZG4bURz6+a5rdU52eA2LbypbMMBOD 2w4vVVcl1cTAzkLVEy3YA5tRdb3Xq1KH+jnqezWlyL8CVKIyxPzrlKC/gNQY+EHIL7JY /hGFUrDv3M/N2FMu4K7aGkbP1Kl+I0NEbvWFmgcH2J4j5vVfcZ7LFbn2sYsRtlLjUA1o ONoSqoz0Bgd2FaO7AeFJXzv/DMTdnzxxKC17iHAFLAHktyl3fVPGf34WjYyL/NSknqwj +aGghrWs4JFm3vX4OfJhc9Az4EnJEkQvuKmEzU2Lq4FUHZTBWdNgGYmmcgtMe2TUDGMV gK0A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690466405; x=1691071205; 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=2CPKCDOi6mJwjL6XSC+rDJJpHneYnFLHKwvtm+s6raU=; b=Qhzudp3Fs6sDMYn1h2TyUguiFBayxtS2v/+2wRe+gy9l/yUThoG1R2cMByvpZJQlrR 1y0vjkiMNpQ47mxkn1dwR4wVNig7NCGRx0sJlWkIc5xArZr8jmoiTNauZ/GFW8U+2dMo oHF0jHCUfsFso8S3QaeiqmHfsDuISzZEmlccG9qDSAWTGX1cPH3WOJDvBESxSd0cPNFH azSyyIdpnX5aZpNzVe5JneeN4qoJh/DfHjF85dIblhZ4MYdeH7QKu3pI0DRr5Fp+puaZ ZNyi5jR+y1HOKgMjAr8QwN6DS9hOJCB2AYEBDloeN3T8Kibkhx9tZDEsB//s0+QJ6QXB nQvA== X-Gm-Message-State: ABy/qLZWBgzPdBbIULE+L6PGJijHXKy2K6rWQvhLDAqihxiBjuPCqLLU i03DYMzI/cgJzzPScz5fPK99B/kvPr9JK7BnD9Y= X-Google-Smtp-Source: APBJJlH+4/A4iyPHtOrk4UWk6GRI6atrkJuBjTrgHPL7oZlpyRNTLXZYbMHgmCfoV9ZRDDygq9cpogPV/gLvEgHMBlk= X-Received: by 2002:a17:90a:d193:b0:268:2606:76e0 with SMTP id fu19-20020a17090ad19300b00268260676e0mr4854836pjb.4.1690466403497; Thu, 27 Jul 2023 07:00:03 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Matthias van de Meent Date: Thu, 27 Jul 2023 15:59:51 +0200 Message-ID: Subject: Re: Optimizing nbtree ScalarArrayOp execution, allowing multi-column ordered scans, skip scan To: Peter Geoghegan Cc: PostgreSQL Hackers , Tom Lane , Tomas Vondra , Jeff Davis , benoit Content-Type: multipart/mixed; boundary="0000000000007cbdb1060178613b" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --0000000000007cbdb1060178613b Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Thu, 27 Jul 2023 at 06:14, Peter Geoghegan wrote: > > On Wed, Jul 26, 2023 at 12:07=E2=80=AFPM Matthias van de Meent > wrote: > > We could cache the last accessed leaf page across amrescan operations > > to reduce the number of index traversals needed when the join key of > > the left side is highly (but not necessarily strictly) correllated. > > That sounds like block nested loop join. It's possible that that could > reuse some infrastructure from this patch, but I'm not sure. My idea is not quite block nested loop join. It's more 'restart the index scan at the location the previous index scan ended, if heuristics say there's a good chance that might save us time'. I'd say it is comparable to the fast tree descent optimization that we have for endpoint queries, and comparable to this patch's scankey optimization, but across AM-level rescans instead of internal rescans. See also the attached prototype and loosely coded patch. It passes tests, but it might not be without bugs. The basic design of that patch is this: We keep track of how many times we've rescanned, and the end location of the index scan. If a new index scan hits the same page after _bt_search as the previous scan ended, we register that. Those two values - num_rescans and num_samepage - are used as heuristics for the following: If 50% or more of rescans hit the same page as the end location of the previous scan, we start saving the scan's end location's buffer into the BTScanOpaque, so that the next _bt_first can check whether that page might be the right leaf page, and if so, immediately go to that buffer instead of descending the tree - saving one tree descent in the process. Further optimizations of this mechanism could easily be implemented by e.g. only copying the min/max index tuples instead of the full index page, reducing the overhead at scan end. Kind regards, Matthias van de Meent Neon (https://neon.tech) --0000000000007cbdb1060178613b Content-Type: application/octet-stream; name="v1-0001-Cache-btree-scan-end-page-across-rescans-in-the-s.patch.cfbot-ignore" Content-Disposition: attachment; filename="v1-0001-Cache-btree-scan-end-page-across-rescans-in-the-s.patch.cfbot-ignore" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_lkl7xo6o0 RnJvbSBlNTIzMmI4YThlOTBmNjBmNDVhYWRjODEzYzVmMDI0YzllY2Q4ZGFiIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBNYXR0aGlhcyB2YW4gZGUgTWVlbnQgPGJvZWtld3VybStwb3N0 Z3Jlc0BnbWFpbC5jb20+CkRhdGU6IFRodSwgMjcgSnVsIDIwMjMgMTU6MzY6MDEgKzAyMDAKU3Vi amVjdDogW1BBVENIIHYxXSBDYWNoZSBidHJlZSBzY2FuIGVuZCBwYWdlIGFjcm9zcyByZXNjYW5z IGluIHRoZSBzYW1lIG5vZGUKCklmIHRoZSBpbmRleCBpcyByZXBlYXRlZGx5IHNjYW5uZWQgZm9y IHZhbHVlcyAoZS5nLiBpbiBhIG5lc3RlZCBsb29wKSBhbmQgaWYKdGhlIHZhbHVlcyB0aGF0IGFy ZSBiZWluZyBsb29rZWQgdXAgYXJlIGhpZ2hseSBjb3JyZWxhdGVkLCB0aGVuIHdlIGNhbiBsaWtl bHkKcmV1c2UgdGhlIHByZXZpb3VzIGluZGV4IHNjYW4ncyBsYXN0IHBhZ2UgYXMgYSBzdGFydHBv aW50IGZvciB0aGUgbmV3IHNjYW4sCmluc3RlYWQgb2YgZ29pbmcgdGhyb3VnaCBhIHJlbGF0aXZl bHkgZXhwZW5zaXZlIGluZGV4IGRlc2NlbnQuCi0tLQogc3JjL2JhY2tlbmQvYWNjZXNzL25idHJl ZS9uYnRwYWdlLmMgICB8ICAxOCArKysrKwogc3JjL2JhY2tlbmQvYWNjZXNzL25idHJlZS9uYnRy ZWUuYyAgICB8ICAgOCArKysKIHNyYy9iYWNrZW5kL2FjY2Vzcy9uYnRyZWUvbmJ0c2VhcmNoLmMg fCAxMDAgKysrKysrKysrKysrKysrKysrKysrKysrLS0KIHNyYy9pbmNsdWRlL2FjY2Vzcy9uYnRy ZWUuaCAgICAgICAgICAgfCAgMjEgKysrKysrCiA0IGZpbGVzIGNoYW5nZWQsIDE0MSBpbnNlcnRp b25zKCspLCA2IGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL2FjY2Vzcy9u YnRyZWUvbmJ0cGFnZS5jIGIvc3JjL2JhY2tlbmQvYWNjZXNzL25idHJlZS9uYnRwYWdlLmMKaW5k ZXggZDc4OTcxYmZlOC4uODk3YjY3NzJmYyAxMDA2NDQKLS0tIGEvc3JjL2JhY2tlbmQvYWNjZXNz L25idHJlZS9uYnRwYWdlLmMKKysrIGIvc3JjL2JhY2tlbmQvYWNjZXNzL25idHJlZS9uYnRwYWdl LmMKQEAgLTg1Niw2ICs4NTYsMjQgQEAgX2J0X2dldGJ1ZihSZWxhdGlvbiByZWwsIEJsb2NrTnVt YmVyIGJsa25vLCBpbnQgYWNjZXNzKQogCXJldHVybiBidWY7CiB9CiAKK0J1ZmZlcgorX2J0X2dl dHJlY2VudGJ1ZihSZWxhdGlvbiByZWwsIEJsb2NrTnVtYmVyIGJsa25vLCBCdWZmZXIgYnVmLCBp bnQgYWNjZXNzKQoreworCUFzc2VydChCbG9ja051bWJlcklzVmFsaWQoYmxrbm8pKTsKKwlBc3Nl cnQoQnVmZmVySXNWYWxpZChidWYpKTsKKworCWlmICghUmVhZFJlY2VudEJ1ZmZlcihyZWwtPnJk X2xvY2F0b3IsIE1BSU5fRk9SS05VTSwgYmxrbm8sIGJ1ZikpCisJeworCQkvKiBSZWFkIGFuIGV4 aXN0aW5nIGJsb2NrIG9mIHRoZSByZWxhdGlvbiAqLworCQlidWYgPSBSZWFkQnVmZmVyKHJlbCwg Ymxrbm8pOworCX0KKworCV9idF9sb2NrYnVmKHJlbCwgYnVmLCBhY2Nlc3MpOworCV9idF9jaGVj a3BhZ2UocmVsLCBidWYpOworCisJcmV0dXJuIGJ1ZjsKK30KKwogLyoKICAqCV9idF9hbGxvY2J1 ZigpIC0tIEFsbG9jYXRlIGEgbmV3IGJsb2NrL3BhZ2UuCiAgKgpkaWZmIC0tZ2l0IGEvc3JjL2Jh Y2tlbmQvYWNjZXNzL25idHJlZS9uYnRyZWUuYyBiL3NyYy9iYWNrZW5kL2FjY2Vzcy9uYnRyZWUv bmJ0cmVlLmMKaW5kZXggNDU1M2FhZWU1My4uZTRjYTJmOGVjYiAxMDA2NDQKLS0tIGEvc3JjL2Jh Y2tlbmQvYWNjZXNzL25idHJlZS9uYnRyZWUuYworKysgYi9zcmMvYmFja2VuZC9hY2Nlc3MvbmJ0 cmVlL25idHJlZS5jCkBAIC0zNzYsNiArMzc2LDExIEBAIGJ0YmVnaW5zY2FuKFJlbGF0aW9uIHJl bCwgaW50IG5rZXlzLCBpbnQgbm9yZGVyYnlzKQogCSAqLwogCXNvLT5jdXJyVHVwbGVzID0gc28t Pm1hcmtUdXBsZXMgPSBOVUxMOwogCisJc28tPnJlc2NhbnMgPSBzby0+cmVzY2FuU2FtZVBhZ2Ug PSAwOworCXNvLT5yZWNlbnRFbmRQYWdlID0gSW52YWxpZEJsb2NrTnVtYmVyOworCXNvLT5wYWdl Q2FjaGVWYWxpZCA9IGZhbHNlOworCXNvLT5wYWdlQ2FjaGUgPSAoY2hhciAqKSBwYWxsb2MoQkxD S1NaKTsKKwogCXNjYW4tPnhzX2l0dXBkZXNjID0gUmVsYXRpb25HZXREZXNjcihyZWwpOwogCiAJ c2Nhbi0+b3BhcXVlID0gc287CkBAIC00MDIsNiArNDA3LDcgQEAgYnRyZXNjYW4oSW5kZXhTY2Fu RGVzYyBzY2FuLCBTY2FuS2V5IHNjYW5rZXksIGludCBuc2NhbmtleXMsCiAJCUJUU2NhblBvc0lu dmFsaWRhdGUoc28tPmN1cnJQb3MpOwogCX0KIAorCXNvLT5yZXNjYW5zKys7CiAJc28tPm1hcmtJ dGVtSW5kZXggPSAtMTsKIAlzby0+YXJyYXlLZXlDb3VudCA9IDA7CiAJQlRTY2FuUG9zVW5waW5J ZlBpbm5lZChzby0+bWFya1Bvcyk7CkBAIC00NjcsNiArNDczLDggQEAgYnRlbmRzY2FuKEluZGV4 U2NhbkRlc2Mgc2NhbikKIAkvKiBSZWxlYXNlIHN0b3JhZ2UgKi8KIAlpZiAoc28tPmtleURhdGEg IT0gTlVMTCkKIAkJcGZyZWUoc28tPmtleURhdGEpOworCWlmIChzby0+cGFnZUNhY2hlICE9IE5V TEwpCisJCXBmcmVlKHNvLT5wYWdlQ2FjaGUpOwogCS8qIHNvLT5hcnJheUtleURhdGEgYW5kIHNv LT5hcnJheUtleXMgYXJlIGluIGFycmF5Q29udGV4dCAqLwogCWlmIChzby0+YXJyYXlDb250ZXh0 ICE9IE5VTEwpCiAJCU1lbW9yeUNvbnRleHREZWxldGUoc28tPmFycmF5Q29udGV4dCk7CmRpZmYg LS1naXQgYS9zcmMvYmFja2VuZC9hY2Nlc3MvbmJ0cmVlL25idHNlYXJjaC5jIGIvc3JjL2JhY2tl bmQvYWNjZXNzL25idHJlZS9uYnRzZWFyY2guYwppbmRleCAzMjMwYjNiODk0Li42N2U1OTdiNTZj IDEwMDY0NAotLS0gYS9zcmMvYmFja2VuZC9hY2Nlc3MvbmJ0cmVlL25idHNlYXJjaC5jCisrKyBi L3NyYy9iYWNrZW5kL2FjY2Vzcy9uYnRyZWUvbmJ0c2VhcmNoLmMKQEAgLTQ3LDYgKzQ3LDQ1IEBA IHN0YXRpYyBCdWZmZXIgX2J0X3dhbGtfbGVmdChSZWxhdGlvbiByZWwsIEJ1ZmZlciBidWYsIFNu YXBzaG90IHNuYXBzaG90KTsKIHN0YXRpYyBib29sIF9idF9lbmRwb2ludChJbmRleFNjYW5EZXNj IHNjYW4sIFNjYW5EaXJlY3Rpb24gZGlyKTsKIHN0YXRpYyBpbmxpbmUgdm9pZCBfYnRfaW5pdGlh bGl6ZV9tb3JlX2RhdGEoQlRTY2FuT3BhcXVlIHNvLCBTY2FuRGlyZWN0aW9uIGRpcik7CiAKK3N0 YXRpYyB2b2lkIF9idF9lbmRzY2Fub25wYWdlKEJUU2Nhbk9wYXF1ZSBidHNvLCBCdWZmZXIgYnVm LAorCQkJCQkJCSAgQmxvY2tOdW1iZXIgZW5kUGFnZSwgUGFnZSBwYWdlKTsKKworI2RlZmluZSBS ZXNjYW5NYXlIaXRTYW1lUGFnZShzbykgKCgoZmxvYXQpICgoc28pLT5yZXNjYW5TYW1lUGFnZSkg LyAoZmxvYXQpICgoc28pLT5yZXNjYW5zKSkgPj0gMC41KQorCitzdGF0aWMgdm9pZAorX2J0X2Vu ZHNjYW5vbnBhZ2UoQlRTY2FuT3BhcXVlIGJ0c28sIEJ1ZmZlciBidWYsIEJsb2NrTnVtYmVyIGVu ZFBhZ2UsIFBhZ2UgcGFnZSkKK3sKKwlCbG9ja051bWJlciBwcmV2RW5kUGFnZSA9IGJ0c28tPnJl Y2VudEVuZFBhZ2U7CisKKwkvKgorCSAqIFdlIGhhdmUgb2Z0ZW4gKD41MCUpIGhpdCB0aGUgcGFn ZSB0aGUgcHJldmlvdXMgc2NhbiBlbmRlZCBvbiwgc28KKwkgKiBjYWNoZSB0aGUgY3VycmVudCAo bGFzdCkgcGFnZSBvZiB0aGUgc2NhbiBmb3IgZnV0dXJlIHVzZS4KKwkgKi8KKwlpZiAoUmVzY2Fu TWF5SGl0U2FtZVBhZ2UoYnRzbykpCisJeworCQkvKgorCQkgKiBJZiB3ZSBoYXZlIGEgdmFsaWQg Y2FjaGUsIGFuZCB0aGUgY2FjaGUgY29udGFpbnMgdGhpcyBwYWdlLCB0aGVuCisJCSAqIHdlIGRv bid0IGhhdmUgYW55dGhpbmcgdG8gZG8uCisJCSAqLworCQlpZiAocHJldkVuZFBhZ2UgPT0gZW5k UGFnZSAmJiBidHNvLT5wYWdlQ2FjaGVWYWxpZCkKKwkJeworCQkJLyogZG8gbm90aGluZyAqLwor CQl9CisJCWVsc2UKKwkJeworCQkJbWVtY3B5KGJ0c28tPnBhZ2VDYWNoZSwgcGFnZSwgQkxDS1Na KTsKKwkJCWJ0c28tPnBhZ2VDYWNoZVZhbGlkID0gdHJ1ZTsKKwkJCWJ0c28tPnJlY2VudEJ1ZmZl ciA9IGJ1ZjsKKwkJCWJ0c28tPnJlY2VudEVuZFBhZ2UgPSBlbmRQYWdlOworCQl9CisJfQorCWVs c2UgaWYgKHByZXZFbmRQYWdlICE9IGVuZFBhZ2UpCisJeworCQlidHNvLT5yZWNlbnRFbmRQYWdl ID0gZW5kUGFnZTsKKwkJYnRzby0+cGFnZUNhY2hlVmFsaWQgPSBmYWxzZTsKKwl9Cit9CisKIAog LyoKICAqCV9idF9kcm9wX2xvY2tfYW5kX21heWJlX3BpbigpCkBAIC04NzIsNyArOTExLDcgQEAg X2J0X2ZpcnN0KEluZGV4U2NhbkRlc2Mgc2NhbiwgU2NhbkRpcmVjdGlvbiBkaXIpCiB7CiAJUmVs YXRpb24JcmVsID0gc2Nhbi0+aW5kZXhSZWxhdGlvbjsKIAlCVFNjYW5PcGFxdWUgc28gPSAoQlRT Y2FuT3BhcXVlKSBzY2FuLT5vcGFxdWU7Ci0JQnVmZmVyCQlidWY7CisJQnVmZmVyCQlidWYgPSBJ bnZhbGlkQnVmZmVyOwogCUJUU3RhY2sJCXN0YWNrOwogCU9mZnNldE51bWJlciBvZmZudW07CiAJ U3RyYXRlZ3lOdW1iZXIgc3RyYXQ7CkBAIC0xMzcxLDEzICsxNDEwLDU5IEBAIF9idF9maXJzdChJ bmRleFNjYW5EZXNjIHNjYW4sIFNjYW5EaXJlY3Rpb24gZGlyKQogCWluc2tleS5rZXlzeiA9IGtl eXNDb3VudDsKIAogCS8qCi0JICogVXNlIHRoZSBtYW51ZmFjdHVyZWQgaW5zZXJ0aW9uIHNjYW4g a2V5IHRvIGRlc2NlbmQgdGhlIHRyZWUgYW5kCi0JICogcG9zaXRpb24gb3Vyc2VsdmVzIG9uIHRo ZSB0YXJnZXQgbGVhZiBwYWdlLgorCSAqIElmIHdlJ3ZlIHJlc3RhcnRlZCB0aGUgc2NhbiB0aHJv dWdoIGFtcmVzY2FuLCBpdCBpcyBxdWl0ZSBwb3NzaWJsZQorCSAqIHRoYXQgYSBwcmV2aW91cyBz Y2FuIGVuZGVkIG9uIHRoZSBzYW1lIHBhZ2Ugd2UncmUgdHJ5aW5nIHRvIGZpbmQuCisJICogSWYg dGhpcyBoYXBwZW5lZCByZXBlYXRlZGx5LCB3ZSBjYWNoZSB0aGUgbGFzdCBwYWdlIG9mIHRoZSBz Y2FuLAorCSAqIHNvIHRoYXQgd2UgbWF5IGJlIGFibGUgdG8gaWdub3JlIHRoZSBwZW5hbHR5IG9m IHRyYXZlcnNpbmcgdGhlIHRyZWUKKwkgKiBmcm9tIHRoZSB0b3AuCisJICogCisJICogWFhYOiBN YXliZSB0aGlzIG1pZ2h0IG5vdCBiZSBjb25jdXJyZW5jeS1zYWZlPyBIYXZlbid0IHRob3VnaHQg YWJvdXQgaXQKKwkgKiBxdWl0ZSB5ZXQuCiAJICovCi0Jc3RhY2sgPSBfYnRfc2VhcmNoKHJlbCwg TlVMTCwgJmluc2tleSwgJmJ1ZiwgQlRfUkVBRCwgc2Nhbi0+eHNfc25hcHNob3QpOworCWlmIChS ZXNjYW5NYXlIaXRTYW1lUGFnZShzbykgJiYgc28tPnBhZ2VDYWNoZVZhbGlkKQorCXsKKwkJUGFn ZQlwYWdlID0gc28tPnBhZ2VDYWNoZTsKKwkJQlRQYWdlT3BhcXVlIG9wYXF1ZSA9IEJUUGFnZUdl dE9wYXF1ZShwYWdlKTsKKworCQkvKiBjYWNoZWQgcGFnZSBpcyBhIGxlYWYgcGFnZSwgYW5kIGlz IG5vdCBlbXB0eSAqLworCQlBc3NlcnQoUF9JU0xFQUYob3BhcXVlKSAmJiBQYWdlR2V0TWF4T2Zm c2V0TnVtYmVyKHBhZ2UpICE9IDApOworCisJCS8qCisJCSAqIElmIHRoZSBzZWFyY2gga2V5IGRv ZXNuJ3QgZml0IHdpdGhpbiB0aGUgbWluL21heCBvZiB0aGlzIHBhZ2UsCisJCSAqIHdlIGNvbnRp bnVlIHdpdGggbm9ybWFsIGluZGV4IGRlc2NlbnQuCisJCSAqLworCQlpZiAoX2J0X2NvbXBhcmUo cmVsLCAmaW5za2V5LCBwYWdlLCBQX0hJS0VZKSA+PSAwKQorCQkJZ290byBub2NhY2hlOworCQlp ZiAoX2J0X2NvbXBhcmUocmVsLCAmaW5za2V5LCBwYWdlLCBQYWdlR2V0TWF4T2Zmc2V0TnVtYmVy KHBhZ2UpKSA8PSAwKQorCQkJZ290byBub2NhY2hlOworCisJCWJ1ZiA9IF9idF9nZXRyZWNlbnRi dWYocmVsLCBzby0+cmVjZW50RW5kUGFnZSwgc28tPnJlY2VudEJ1ZmZlciwKKwkJCQkJCQkgICBC VF9SRUFEKTsKIAotCS8qIGRvbid0IG5lZWQgdG8ga2VlcCB0aGUgc3RhY2sgYXJvdW5kLi4uICov Ci0JX2J0X2ZyZWVzdGFjayhzdGFjayk7CisJCS8qCisJCSAqIEl0IGlzIHBvc3NpYmxlIHRoZSBw YWdlIGhhcyBzcGxpdCBpbiB0aGUgbWVhbnRpbWUsIHNvIHdlIG1heSBoYXZlCisJCSAqIHRvIG1v dmUgcmlnaHQKKwkJICovCisJCWJ1ZiA9IF9idF9tb3ZlcmlnaHQocmVsLCBOVUxMLCAmaW5za2V5 LCBidWYsIGZhbHNlLCBOVUxMLCBCVF9SRUFELAorCQkJCQkJCXNjYW4tPnhzX3NuYXBzaG90KTsK KwkJc28tPnJlc2NhblNhbWVQYWdlICs9IDE7CisJfQorCitub2NhY2hlOgorCWlmICghQnVmZmVy SXNWYWxpZChidWYpKQorCXsKKwkJLyoKKwkJICogVXNlIHRoZSBtYW51ZmFjdHVyZWQgaW5zZXJ0 aW9uIHNjYW4ga2V5IHRvIGRlc2NlbmQgdGhlIHRyZWUgYW5kCisJCSAqIHBvc2l0aW9uIG91cnNl bHZlcyBvbiB0aGUgdGFyZ2V0IGxlYWYgcGFnZS4KKwkJICovCisJCXN0YWNrID0gX2J0X3NlYXJj aChyZWwsIE5VTEwsICZpbnNrZXksICZidWYsIEJUX1JFQUQsIHNjYW4tPnhzX3NuYXBzaG90KTsK KworCQkvKiBkb24ndCBuZWVkIHRvIGtlZXAgdGhlIHN0YWNrIGFyb3VuZC4uLiAqLworCQlfYnRf ZnJlZXN0YWNrKHN0YWNrKTsKKworCQlpZiAoYnVmID09IHNvLT5yZWNlbnRCdWZmZXIpCisJCQlz by0+cmVzY2FuU2FtZVBhZ2UgKz0gMTsKKwl9CiAKIAlpZiAoIUJ1ZmZlcklzVmFsaWQoYnVmKSkK IAl7CkBAIC0xNzkyLDYgKzE4NzcsOSBAQCBfYnRfcmVhZHBhZ2UoSW5kZXhTY2FuRGVzYyBzY2Fu LCBTY2FuRGlyZWN0aW9uIGRpciwgT2Zmc2V0TnVtYmVyIG9mZm51bSkKIAkJc28tPmN1cnJQb3Mu aXRlbUluZGV4ID0gTWF4VElEc1BlckJUcmVlUGFnZSAtIDE7CiAJfQogCisJaWYgKCFjb250aW51 ZXNjYW4pCisJCV9idF9lbmRzY2Fub25wYWdlKHNvLCBzby0+Y3VyclBvcy5idWYsIHNvLT5jdXJy UG9zLmN1cnJQYWdlLCBwYWdlKTsKKwogCXJldHVybiAoc28tPmN1cnJQb3MuZmlyc3RJdGVtIDw9 IHNvLT5jdXJyUG9zLmxhc3RJdGVtKTsKIH0KIApkaWZmIC0tZ2l0IGEvc3JjL2luY2x1ZGUvYWNj ZXNzL25idHJlZS5oIGIvc3JjL2luY2x1ZGUvYWNjZXNzL25idHJlZS5oCmluZGV4IDg4OTFmYTc5 NzMuLmI3NmQ0MzM3MjUgMTAwNjQ0Ci0tLSBhL3NyYy9pbmNsdWRlL2FjY2Vzcy9uYnRyZWUuaAor KysgYi9zcmMvaW5jbHVkZS9hY2Nlc3MvbmJ0cmVlLmgKQEAgLTEwNjIsNiArMTA2MiwyNiBAQCB0 eXBlZGVmIHN0cnVjdCBCVFNjYW5PcGFxdWVEYXRhCiAJY2hhcgkgICAqY3VyclR1cGxlczsJCS8q IHR1cGxlIHN0b3JhZ2UgZm9yIGN1cnJQb3MgKi8KIAljaGFyCSAgICptYXJrVHVwbGVzOwkJLyog dHVwbGUgc3RvcmFnZSBmb3IgbWFya1BvcyAqLwogCisJLyoKKwkgKiBJZiB3ZSdyZSBvbiB0aGUg b3V0ZXIgc2lkZSBvZiBhIGxvb3Agam9pbiwgcGFyYW1ldGVyaXplZCBqb2lucyBtYXkKKwkgKiBo YXZlIHNvbWUgY29ycmVsYXRpb24sIGkuZS4gcmVwZWF0ZWQgY2xvc2UgdmFsdWVzIHdoaWNoIGZp dCBvbgorCSAqIG5lYXJieSBwYWdlcy4gQnkgdHJhY2tpbmcgYXQgd2hpY2ggbGVhZiBwYWdlIHdl IHN0YXJ0IGFuZCBlbmQgb3VyCisJICogc2NhbnMsIHdlIGNhbiBkZXRlY3QgdGhpcyBjYXNlIGFu ZCAoaW4gc29tZSBjYXNlcykgcmVkdWNlIGJ1ZmZlcgorCSAqIGFjY2Vzc2VzIGJ5IGEgaHVnZSBt YXJnaW4uCisJICogCisJICogVE9ETzogQ2FjaGluZyB0aGlzIHBhZ2UgbG9jYWxseSBpcyBPSywg YmVjYXVzZSB0aGlzIGlzIGluc2lkZSBhIHF1ZXJ5CisJICogY29udGV4dCBhbmQgdGh1cyBib3Vu ZCB0byB0aGUgbGlmZXRpbWUgYW5kIHNuYXBzaG90IG9mIHRoZSBxdWVyeS4KKwkgKiBBY2Nlc3Np bmcgYW4gdXBkYXRlZCB2ZXJzaW9uIG9mIHRoZSBwYWdlIG1pZ2h0IG5vdCBiZSwgc28gdGhhdCBu ZWVkcworCSAqIGNoZWNraW5nLgorCSAqLworCWludAkJCXJlc2NhbnM7CQkvKiBudW1iZXIgb2Yg cmVzY2FucyAqLworCWludAkJCXJlc2NhblNhbWVQYWdlOwkvKiBudW1iZXIgb2YgcmVzY2FucyB0 aGF0IHN0YXJ0ZWQgb24gdGhlIHByZXZpb3VzIHNjYW4ncyBlbmQgbG9jYXRpb24gKi8KKworCUJs b2NrTnVtYmVyCXJlY2VudEVuZFBhZ2U7CS8qIHNjYW4gZW5kIHBhZ2Ugb2YgcHJldmlvdXMgc2Nh biAqLworCUJ1ZmZlcgkJcmVjZW50QnVmZmVyOwkvKiBidWZmZXIgb2YgcmVjZW50RW5kUGFnZS4g TWF5IG5vdCBtYXRjaC4gKi8KKwlib29sCQlwYWdlQ2FjaGVWYWxpZDsJLyogaXMgdGhlIGNhY2hl ZCBwYWdlIHZhbGlkPyAqLworCWNoYXIJICAgKnBhZ2VDYWNoZTsJCS8qIGNvcHkgb2YgdGhlIHBy ZXZpb3VzIHNjYW4ncyBsYXN0IHBhZ2UsIGlmIHZhbGlkICovCisKIAkvKgogCSAqIElmIHRoZSBt YXJrZWQgcG9zaXRpb24gaXMgb24gdGhlIHNhbWUgcGFnZSBhcyBjdXJyZW50IHBvc2l0aW9uLCB3 ZQogCSAqIGRvbid0IHVzZSBtYXJrUG9zLCBidXQganVzdCBrZWVwIHRoZSBtYXJrZWQgaXRlbUlu ZGV4IGluIG1hcmtJdGVtSW5kZXgKQEAgLTEyMDcsNiArMTIyNyw3IEBAIGV4dGVybiB2b2lkIF9i dF9tZXRhdmVyc2lvbihSZWxhdGlvbiByZWwsIGJvb2wgKmhlYXBrZXlzcGFjZSwKIAkJCQkJCQli b29sICphbGxlcXVhbGltYWdlKTsKIGV4dGVybiB2b2lkIF9idF9jaGVja3BhZ2UoUmVsYXRpb24g cmVsLCBCdWZmZXIgYnVmKTsKIGV4dGVybiBCdWZmZXIgX2J0X2dldGJ1ZihSZWxhdGlvbiByZWws IEJsb2NrTnVtYmVyIGJsa25vLCBpbnQgYWNjZXNzKTsKK2V4dGVybiBCdWZmZXIgX2J0X2dldHJl Y2VudGJ1ZihSZWxhdGlvbiByZWwsIEJsb2NrTnVtYmVyIGJsa25vLCBCdWZmZXIgYnVmZmVyLCBp bnQgYWNjZXNzKTsKIGV4dGVybiBCdWZmZXIgX2J0X2FsbG9jYnVmKFJlbGF0aW9uIHJlbCwgUmVs YXRpb24gaGVhcHJlbCk7CiBleHRlcm4gQnVmZmVyIF9idF9yZWxhbmRnZXRidWYoUmVsYXRpb24g cmVsLCBCdWZmZXIgb2J1ZiwKIAkJCQkJCQkgICBCbG9ja051bWJlciBibGtubywgaW50IGFjY2Vz cyk7Ci0tIAoyLjQwLjEKCg== --0000000000007cbdb1060178613b--