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 1qWa7N-003i5A-7X for pgsql-hackers@arkaria.postgresql.org; Thu, 17 Aug 2023 10:20:41 +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 1qWa7K-00GAnC-Te for pgsql-hackers@arkaria.postgresql.org; Thu, 17 Aug 2023 10:20:39 +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 1qWa7K-00GAn4-GQ for pgsql-hackers@lists.postgresql.org; Thu, 17 Aug 2023 10:20:38 +0000 Received: from mail.postgrespro.ru ([93.174.131.139]) by magus.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1qWa7H-000eDQ-70 for pgsql-hackers@postgresql.org; Thu, 17 Aug 2023 10:20:38 +0000 Received: from [10.4.15.186] (unknown [93.174.131.141]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) (Authenticated sender: a.rybakina@postgrespro.ru) by mail.postgrespro.ru (Postfix/587) with ESMTPSA id 0C059E203BC; Thu, 17 Aug 2023 13:20:34 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mx2023; t=1692267634; bh=7yyMnsecSPZh8dcaj9YKz+r/09o4ikVzQKyIff+pc+k=; h=Message-ID:Date:User-Agent:Subject:From:To:Cc:References: In-Reply-To:From; b=2IbUnTzHNBjfaNOY6Q07vD+GmACNJK0bVo6F1amJubyjfNw6TfLXVfWSsg0b6YncY mULzB6DNUE/No5+rLD8+w33VMB77kb3qza5ky3pN1Sf6gCI1lHufx/UN26tJLV/uP9 7cdUrxFqWRBNnEUeUH14Nz5ShMypbMoBGLvb2zkWKzzKAJHbH97Cl1F6z547ikjDCn YvFUPbjM7droDhpHXyLIDJRdMXnedh5eQm/smjfTth2p1rlZw8dr6AY3ueY1v1crpC el3aOaObzf5xF1z2k7E/KBy4sr4fl4avtnghcvPm9KNnVTDX+6alO8BgaIw7/HHtXW /C2p/8UITt/nQ== Content-Type: multipart/mixed; boundary="------------iGczFavueqs6sJxDcwVu5RH3" Message-ID: <11403645-b342-c400-859e-47d0f41ec22a@postgrespro.ru> Date: Thu, 17 Aug 2023 13:20:33 +0300 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.13.0 Subject: Re: POC, WIP: OR-clause support for indexes Content-Language: en-US From: "a.rybakina" To: Peter Geoghegan Cc: "Finnerty, Jim" , Marcos Pegoraro , Andrey Lepikhov , pgsql-hackers@postgresql.org, teodor@sigaev.ru, Ranier Vilela , Tomas Vondra References: <567ED6CA.2040504@sigaev.ru> <7829312a-eb6b-b9ba-9719-71c9bc410884@yandex.ru> <9ea35f18-419d-efb7-b7c8-2e641a61f020@yandex.ru> <08f5ff34-1497-2123-8701-461a299035c9@yandex.ru> <8d714510-af73-a908-99c8-fc14536f2669@yandex.ru> <4bac271d-1700-db24-74ac-8414f2baf9fd@postgrespro.ru> In-Reply-To: <4bac271d-1700-db24-74ac-8414f2baf9fd@postgrespro.ru> List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk This is a multi-part message in MIME format. --------------iGczFavueqs6sJxDcwVu5RH3 Content-Type: multipart/alternative; boundary="------------cKR2r60tX1yEH81m6y0VM03n" --------------cKR2r60tX1yEH81m6y0VM03n Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Sorry, I didn't write correctly enough, about the second second place in the code where the conversion works well enough is the removal of duplicate OR expressions. I attached patch to learn it in more detail. On 17.08.2023 13:08, a.rybakina wrote: > Hi, all! >>> The optimizer will itself do a limited form of "normalizing to CNF". >>> Are you familiar with extract_restriction_or_clauses(), from >>> orclauses.c? Comments above the function have an example of how this >>> can work: >>> >>>   * Although a join clause must reference multiple relations overall, >>>   * an OR of ANDs clause might contain sub-clauses that reference >>> just one >>>   * relation and can be used to build a restriction clause for that >>> rel. >>>   * For example consider >>>   *      WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45)); >>>   * We can transform this into >>>   *      WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45)) >>>   *          AND (a.x = 42 OR a.x = 44) >>>   *          AND (b.y = 43 OR b.z = 45); >>>   * which allows the latter clauses to be applied during the scans >>> of a and b, >>>   * perhaps as index qualifications, and in any case reducing the >>> number of >>>   * rows arriving at the join.  In essence this is a partial >>> transformation to >>>   * CNF (AND of ORs format).  It is not complete, however, because >>> we do not >>>   * unravel the original OR --- doing so would usually bloat the >>> qualification >>>   * expression to little gain. >> This is an interesting feature. I didn't notice this function before, >> I studied many times consider_new_or_cause, which were called there. >> As far as I know, there is a selectivity calculation going on there, >> but as far as I remember, I called it earlier after my conversion, >> and unfortunately it didn't solve my problem with calculating >> selectivity. I'll reconsider it again, maybe I can find something I >> missed. >>> Of course this immediately makes me wonder: shouldn't your patch be >>> able to perform an additional transformation here? You know, by >>> transforming "a.x = 42 OR a.x = 44" into "a IN (42, 44)"? Although I >>> haven't checked for myself, I assume that this doesn't happen right >>> now, since your patch currently performs all of its transformations >>> during parsing. >>> >>> I also noticed that the same comment block goes on to say something >>> about "clauselist_selectivity's inability to recognize redundant >>> conditions". Perhaps that is relevant to the problems you were having >>> with selectivity estimation, back when the code was in >>> preprocess_qual_conditions() instead? I have no reason to believe that >>> there should be any redundancy left behind by your transformation, so >>> this is just one possibility to consider. >>> Separately, the commit message of commit 25a9e54d2d says something >>> about how the planner builds RestrictInfos, which seems >>> possibly-relevant. That commit enhanced extended statistics for OR >>> clauses, so the relevant paragraph describes a limitation of extended >>> statistics with OR clauses specifically. I'm just guessing, but it >>> still seems like it might be relevant to the problem you ran into with >>> selectivity estimation. Another possibility to consider. >> >> I understood what is said about AND clauses in this comment. It seems >> to me that AND clauses saved like (BoolExpr *) >> expr->args->(RestrictInfo *) clauseA->(RestrictInfo *)clauseB lists >> and OR clauses saved like (BoolExpr *) expr -> >> orclause->(RestrictInfo *)clause A->(RestrictInfo *)clause B. >> >> As I understand it, selectivity is calculated for each expression. >> But I'll exploring it deeper, because I think this place may contain >> the answer to the question, what's wrong with selectivity calculation >> in my patch. > > I could move transformation in there (extract_restriction_or_clauses) > and didn't have any problem with selectivity calculation, besides it > also works on the redundant or duplicates stage. So, it looks like: > > CREATE TABLE tenk1 (unique1 int, unique2 int, ten int, hundred int); > insert into tenk1 SELECT x,x,x,x FROM generate_series(1,50000) as x; > CREATE INDEX a_idx1 ON tenk1(unique1); CREATE INDEX a_idx2 ON > tenk1(unique2); CREATE INDEX a_hundred ON tenk1(hundred); > > explain analyze select * from tenk1 a join tenk1 b on ((a.unique2 = 3 > or a.unique2 = 7)); > > PLAN > ------------------------------------------------------------------------------------------------------------------------------ > Nested Loop (cost=0.29..2033.62 rows=100000 width=32) (actual > time=0.090..60.258 rows=100000 loops=1) -> Seq Scan on tenk1 b > (cost=0.00..771.00 rows=50000 width=16) (actual time=0.016..9.747 > rows=50000 loops=1) -> Materialize (cost=0.29..12.62 rows=2 width=16) > (actual time=0.000..0.000 rows=2 loops=50000) -> Index Scan using > a_idx2 on tenk1 a (cost=0.29..12.62 rows=2 width=16) (actual > time=0.063..0.068 rows=2 loops=1) Index Cond: (unique2 = ANY (ARRAY[3, > 7])) Planning Time: 8.257 ms Execution Time: 64.453 ms (7 rows) > > Overall, this was due to incorrectly defined types of elements in the > array, and if we had applied the transformation with the definition of > the tup operator, we could have avoided such problems (I used > make_scalar_array_op and have not yet found an alternative to this). > > When I moved the transformation on the index creation stage, it > couldn't work properly and as a result I faced the same problem of > selectivity calculation. I supposed that the selectivity values are > also used there, and not recalculated all over again. perhaps we can > solve this by forcibly recalculating the selectivity values, but I > foresee other problems there. > > explain analyze select * from tenk1 a join tenk1 b on ((a.unique2 = 3 > or a.unique2 = 7)); > > QUERY PLAN > ----------------------------------------------------------------------------------------------------------------------------------- > Nested Loop (cost=12.58..312942.91 rows=24950000 width=32) (actual > time=0.040..47.582 rows=100000 loops=1) -> Seq Scan on tenk1 b > (cost=0.00..771.00 rows=50000 width=16) (actual time=0.009..7.039 > rows=50000 loops=1) -> Materialize (cost=12.58..298.16 rows=499 > width=16) (actual time=0.000..0.000 rows=2 loops=50000) -> Bitmap Heap > Scan on tenk1 a (cost=12.58..295.66 rows=499 width=16) (actual > time=0.025..0.028 rows=2 loops=1) Recheck Cond: ((unique2 = 3) OR > (unique2 = 7)) Heap Blocks: exact=1 -> BitmapOr (cost=12.58..12.58 > rows=500 width=0) (actual time=0.023..0.024 rows=0 loops=1) -> Bitmap > Index Scan on a_idx2 (cost=0.00..6.17 rows=250 width=0) (actual > time=0.019..0.019 rows=1 loops=1) Index Cond: (unique2 = 3) -> Bitmap > Index Scan on a_idx2 (cost=0.00..6.17 rows=250 width=0) (actual > time=0.003..0.003 rows=1 loops=1) Index Cond: (unique2 = 7) Planning > Time: 0.401 ms Execution Time: 51.350 ms (13 rows) > > I have attached a diff file so far, but it is very raw and did not > pass all regression tests (I attached regression.diff) and even had > bad conversion cases (some of the cases did not work at all, in other > cases there were no non-converted nodes). But now I see an interesting > transformation, which was the most interesting for me. > > EXPLAIN (COSTS OFF) SELECT * FROM tenk1 WHERE thousand = 42 AND > (tenthous = 1 OR tenthous = 3 OR tenthous = 42); - QUERY PLAN > ------------------------------------------------------------------------------------------------------------------------------------------ > - Bitmap Heap Scan on tenk1 - Recheck Cond: (((thousand = 42) AND > (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3)) OR ((thousand > = 42) AND (tenthous = 42))) - -> BitmapOr - -> Bitmap Index Scan on > tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous = > 1)) - -> Bitmap Index Scan on tenk1_thous_tenthous - Index Cond: > ((thousand = 42) AND (tenthous = 3)) - -> Bitmap Index Scan on > tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous = > 42)) -(9 rows) + QUERY PLAN > +------------------------------------------------------------------------ > + Index Scan using tenk1_thous_tenthous on tenk1 + Index Cond: > ((thousand = 42) AND (tenthous = ANY (ARRAY[1, 3, 42]))) +(2 rows) > --------------cKR2r60tX1yEH81m6y0VM03n Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

Sorry, I didn't write correctly enough, about the second second place in the code where the conversion works well enough is the removal of duplicate OR expressions.

I attached patch to learn it in more detail.

On 17.08.2023 13:08, a.rybakina wrote:
Hi, all!
The optimizer will itself do a limited form of "normalizing to CNF".
Are you familiar with extract_restriction_or_clauses(), from
orclauses.c? Comments above the function have an example of how this
can work:

  * Although a join clause must reference multiple relations overall,
  * an OR of ANDs clause might contain sub-clauses that reference just one
  * relation and can be used to build a restriction clause for that rel.
  * For example consider
  *      WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45));
  * We can transform this into
  *      WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45))
  *          AND (a.x = 42 OR a.x = 44)
  *          AND (b.y = 43 OR b.z = 45);
  * which allows the latter clauses to be applied during the scans of a and b,
  * perhaps as index qualifications, and in any case reducing the number of
  * rows arriving at the join.  In essence this is a partial transformation to
  * CNF (AND of ORs format).  It is not complete, however, because we do not
  * unravel the original OR --- doing so would usually bloat the qualification
  * expression to little gain.
This is an interesting feature. I didn't notice this function before, I studied many times consider_new_or_cause, which were called there. As far as I know, there is a selectivity calculation going on there, but as far as I remember, I called it earlier after my conversion, and unfortunately it didn't solve my problem with calculating selectivity. I'll reconsider it again, maybe I can find something I missed.
Of course this immediately makes me wonder: shouldn't your patch be
able to perform an additional transformation here? You know, by
transforming "a.x = 42 OR a.x = 44" into "a IN (42, 44)"? Although I
haven't checked for myself, I assume that this doesn't happen right
now, since your patch currently performs all of its transformations
during parsing.

I also noticed that the same comment block goes on to say something
about "clauselist_selectivity's inability to recognize redundant
conditions". Perhaps that is relevant to the problems you were having
with selectivity estimation, back when the code was in
preprocess_qual_conditions() instead? I have no reason to believe that
there should be any redundancy left behind by your transformation, so
this is just one possibility to consider.
Separately, the commit message of commit 25a9e54d2d says something
about how the planner builds RestrictInfos, which seems
possibly-relevant. That commit enhanced extended statistics for OR
clauses, so the relevant paragraph describes a limitation of extended
statistics with OR clauses specifically. I'm just guessing, but it
still seems like it might be relevant to the problem you ran into with
selectivity estimation. Another possibility to consider.

I understood what is said about AND clauses in this comment. It seems to me that AND clauses saved like (BoolExpr *) expr->args->(RestrictInfo *) clauseA->(RestrictInfo *)clauseB lists and OR clauses saved like (BoolExpr *) expr -> orclause->(RestrictInfo *)clause A->(RestrictInfo *)clause B.

As I understand it, selectivity is calculated for each expression. But I'll exploring it deeper, because I think this place may contain the answer to the question, what's wrong with selectivity calculation in my patch.

I could move transformation in there (extract_restriction_or_clauses) and didn't have any problem with selectivity calculation, besides it also works on the redundant or duplicates stage. So, it looks like:

CREATE TABLE tenk1 (unique1 int, unique2 int, ten int, hundred int); insert into tenk1 SELECT x,x,x,x FROM generate_series(1,50000) as x; CREATE INDEX a_idx1 ON tenk1(unique1); CREATE INDEX a_idx2 ON tenk1(unique2); CREATE INDEX a_hundred ON tenk1(hundred);

explain analyze select * from tenk1 a join tenk1 b on ((a.unique2 = 3 or a.unique2 = 7));

PLAN ------------------------------------------------------------------------------------------------------------------------------ Nested Loop (cost=0.29..2033.62 rows=100000 width=32) (actual time=0.090..60.258 rows=100000 loops=1) -> Seq Scan on tenk1 b (cost=0.00..771.00 rows=50000 width=16) (actual time=0.016..9.747 rows=50000 loops=1) -> Materialize (cost=0.29..12.62 rows=2 width=16) (actual time=0.000..0.000 rows=2 loops=50000) -> Index Scan using a_idx2 on tenk1 a (cost=0.29..12.62 rows=2 width=16) (actual time=0.063..0.068 rows=2 loops=1) Index Cond: (unique2 = ANY (ARRAY[3, 7])) Planning Time: 8.257 ms Execution Time: 64.453 ms (7 rows)

Overall, this was due to incorrectly defined types of elements in the array, and if we had applied the transformation with the definition of the tup operator, we could have avoided such problems (I used make_scalar_array_op and have not yet found an alternative to this).

When I moved the transformation on the index creation stage, it couldn't work properly and as a result I faced the same problem of selectivity calculation. I supposed that the selectivity values are also used there, and not recalculated all over again. perhaps we can solve this by forcibly recalculating the selectivity values, but I foresee other problems there.

explain analyze select * from tenk1 a join tenk1 b on ((a.unique2 = 3 or a.unique2 = 7));

QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------- Nested Loop (cost=12.58..312942.91 rows=24950000 width=32) (actual time=0.040..47.582 rows=100000 loops=1) -> Seq Scan on tenk1 b (cost=0.00..771.00 rows=50000 width=16) (actual time=0.009..7.039 rows=50000 loops=1) -> Materialize (cost=12.58..298.16 rows=499 width=16) (actual time=0.000..0.000 rows=2 loops=50000) -> Bitmap Heap Scan on tenk1 a (cost=12.58..295.66 rows=499 width=16) (actual time=0.025..0.028 rows=2 loops=1) Recheck Cond: ((unique2 = 3) OR (unique2 = 7)) Heap Blocks: exact=1 -> BitmapOr (cost=12.58..12.58 rows=500 width=0) (actual time=0.023..0.024 rows=0 loops=1) -> Bitmap Index Scan on a_idx2 (cost=0.00..6.17 rows=250 width=0) (actual time=0.019..0.019 rows=1 loops=1) Index Cond: (unique2 = 3) -> Bitmap Index Scan on a_idx2 (cost=0.00..6.17 rows=250 width=0) (actual time=0.003..0.003 rows=1 loops=1) Index Cond: (unique2 = 7) Planning Time: 0.401 ms Execution Time: 51.350 ms (13 rows)

I have attached a diff file so far, but it is very raw and did not pass all regression tests (I attached regression.diff) and even had bad conversion cases (some of the cases did not work at all, in other cases there were no non-converted nodes). But now I see an interesting transformation, which was the most interesting for me.

EXPLAIN (COSTS OFF) SELECT * FROM tenk1 WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); - QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------ - Bitmap Heap Scan on tenk1 - Recheck Cond: (((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3)) OR ((thousand = 42) AND (tenthous = 42))) - -> BitmapOr - -> Bitmap Index Scan on tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous = 1)) - -> Bitmap Index Scan on tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous = 3)) - -> Bitmap Index Scan on tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous = 42)) -(9 rows) + QUERY PLAN +------------------------------------------------------------------------ + Index Scan using tenk1_thous_tenthous on tenk1 + Index Cond: ((thousand = 42) AND (tenthous = ANY (ARRAY[1, 3, 42]))) +(2 rows)

--------------cKR2r60tX1yEH81m6y0VM03n-- --------------iGczFavueqs6sJxDcwVu5RH3 Content-Type: text/x-patch; charset=UTF-8; name="diff_fix_sel1.diff" Content-Disposition: attachment; filename="diff_fix_sel1.diff" Content-Transfer-Encoding: base64 ZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wbGFuL3BsYW5uZXIuYyBiL3Ny Yy9iYWNrZW5kL29wdGltaXplci9wbGFuL3BsYW5uZXIuYwppbmRleCA0NGVmYjFmNGViYy4u ODA5MzVjZWM3YWEgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wbGFuL3Bs YW5uZXIuYworKysgYi9zcmMvYmFja2VuZC9vcHRpbWl6ZXIvcGxhbi9wbGFubmVyLmMKQEAg LTY3LDYgKzY3LDcgQEAKICNpbmNsdWRlICJ1dGlscy9yZWwuaCIKICNpbmNsdWRlICJ1dGls cy9zZWxmdW5jcy5oIgogI2luY2x1ZGUgInV0aWxzL3N5c2NhY2hlLmgiCisjaW5jbHVkZSAi b3B0aW1pemVyL29yY2xhdXNlcy5oIgogCiAvKiBHVUMgcGFyYW1ldGVycyAqLwogZG91Ymxl CQljdXJzb3JfdHVwbGVfZnJhY3Rpb24gPSBERUZBVUxUX0NVUlNPUl9UVVBMRV9GUkFDVElP TjsKQEAgLTExNjksNyArMTE3MCw3IEBAIHByZXByb2Nlc3NfZXhwcmVzc2lvbihQbGFubmVy SW5mbyAqcm9vdCwgTm9kZSAqZXhwciwgaW50IGtpbmQpCiAJaWYgKGtpbmQgPT0gRVhQUktJ TkRfUVVBTCkKIAl7CiAJCWV4cHIgPSAoTm9kZSAqKSBjYW5vbmljYWxpemVfcXVhbCgoRXhw ciAqKSBleHByLCBmYWxzZSk7Ci0KK2V4cHIgPSB0cmFuc2Zvcm1fb3JzKHJvb3QsIChFeHBy ICopIGV4cHIpOwogI2lmZGVmIE9QVElNSVpFUl9ERUJVRwogCQlwcmludGYoIkFmdGVyIGNh bm9uaWNhbGl6ZV9xdWFsKClcbiIpOwogCQlwcHJpbnQoZXhwcik7CmRpZmYgLS1naXQgYS9z cmMvYmFja2VuZC9vcHRpbWl6ZXIvdXRpbC9vcmNsYXVzZXMuYyBiL3NyYy9iYWNrZW5kL29w dGltaXplci91dGlsL29yY2xhdXNlcy5jCmluZGV4IDZlZjlkMTRiOTAyLi4yZTMwZjJiZjg4 YSAxMDA2NDQKLS0tIGEvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3V0aWwvb3JjbGF1c2VzLmMK KysrIGIvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3V0aWwvb3JjbGF1c2VzLmMKQEAgLTIyLDYg KzIyLDEwIEBACiAjaW5jbHVkZSAib3B0aW1pemVyL29wdGltaXplci5oIgogI2luY2x1ZGUg Im9wdGltaXplci9vcmNsYXVzZXMuaCIKICNpbmNsdWRlICJvcHRpbWl6ZXIvcmVzdHJpY3Rp bmZvLmgiCisjaW5jbHVkZSAidXRpbHMvbHN5c2NhY2hlLmgiCisjaW5jbHVkZSAicGFyc2Vy L3BhcnNlX2V4cHIuaCIKKyNpbmNsdWRlICJwYXJzZXIvcGFyc2VfY29lcmNlLmgiCisjaW5j bHVkZSAicGFyc2VyL3BhcnNlX29wZXIuaCIKIAogCiBzdGF0aWMgYm9vbCBpc19zYWZlX3Jl c3RyaWN0aW9uX2NsYXVzZV9mb3IoUmVzdHJpY3RJbmZvICpyaW5mbywgUmVsT3B0SW5mbyAq cmVsKTsKQEAgLTI5LDcgKzMzLDI1NSBAQCBzdGF0aWMgRXhwciAqZXh0cmFjdF9vcl9jbGF1 c2UoUmVzdHJpY3RJbmZvICpvcl9yaW5mbywgUmVsT3B0SW5mbyAqcmVsKTsKIHN0YXRpYyB2 b2lkIGNvbnNpZGVyX25ld19vcl9jbGF1c2UoUGxhbm5lckluZm8gKnJvb3QsIFJlbE9wdElu Zm8gKnJlbCwKIAkJCQkJCQkJICAgRXhwciAqb3JjbGF1c2UsIFJlc3RyaWN0SW5mbyAqam9p bl9vcl9yaW5mbyk7CiAKK3R5cGVkZWYgc3RydWN0IE9yQ2xhdXNlR3JvdXBFbnRyeQorewor CU5vZGUJCSAgICpub2RlOworCUxpc3QJCSAgICpjb25zdHM7CisJT2lkCQkJCWNvbGxhdGlv bjsKKwlPaWQJCQkJb3BubzsKKwlSZXN0cmljdEluZm8gICAqcmluZm87CisJRXhwciAqZXhw cjsKK30gT3JDbGF1c2VHcm91cEVudHJ5OworCisvKgorICogUGFzcyB0aHJvdWdoIGJhc2Vy ZXN0cmljdGluZm8gY2xhdXNlcyBhbmQgdHJ5IHRvIGNvbnZlcnQgT1IgY2xhdXNlcyBpbnRv IElOCisgKiBSZXR1cm4gYSBtb2RpZmllZCBjbGF1c2UgbGlzdCBvciBqdXN0IHRoZSBzYW1l IGJhc2VyZXN0cmljdGluZm8sIGlmIG5vCisgKiBjaGFuZ2VzIGhhdmUgbWFkZS4KKyAqIFhY WDogZG8gbm90IGNoYW5nZSBzb3VyY2UgbGlzdCBvZiBjbGF1c2VzIGF0IGFsbC4KKyAqLwor c3RhdGljIEV4cHIgKgordHJhbnNmb3JtX29yc19mb3JfcmVsKEV4cHIgKnF1YWwpCit7CisJ TGlzdAkgICAgICAgKm1vZGlmaWVkX2NsYXVzZSA9IE5JTDsKKwlib29sCQkgICAgc29tZXRo aW5nX2NoYW5nZWQgPSBmYWxzZTsKKwlMaXN0CQkgICAqb3JfbGlzdCA9IE5JTDsKKwlMaXN0 Q2VsbAkgICAqbGNfZWFyZ3MsCisJCQkJICAgKmxjX2FyZ3M7CisJTGlzdAkJICAgKmdyb3Vw c19saXN0ID0gTklMOworCWJvb2wJCQljaGFuZ2VfYXBwbHkgPSBmYWxzZTsKKworCWlmICgh KGlzX29yY2xhdXNlKHF1YWwpKSkKKwl7CisJCS8qIEFkZCBhIGNsYXVzZSB3aXRob3V0IGNo YW5nZXMgKi8KKwkJcmV0dXJuIHF1YWw7CisJfQorCisJLyoKKwkJKiBOT1RFOgorCQkqIEl0 IGlzIGFuIE9SLWNsYXVzZS4gU28sIHJpbmZvLT5vcmNsYXVzZSBpcyBhIEJvb2xFeHByIG5v ZGUsIGNvbnRhaW5zCisJCSogYSBsaXN0IG9mIHN1Yi1yZXN0cmljdGluZm8gYXJncywgYW5k IHJpbmZvLT5jbGF1c2UgLSB3aGljaCBpcyB0aGUKKwkJKiBzYW1lIGV4cHJlc3Npb24sIG1h ZGUgZnJvbSBiYXJlIGNsYXVzZXMuIFRvIG5vdCBicmVhayBzZWxlY3Rpdml0eQorCQkqIGNh Y2hlcyBhbmQgb3RoZXIgb3B0aW1pemF0aW9ucywgdXNlIGJvdGg6CisJCSogLSB1c2Ugcmlu Zm9zIGZyb20gb3JjbGF1c2UgaWYgbm8gdHJhbnNmb3JtYXRpb24gbmVlZGVkCisJCSogLSB1 c2UgIGJhcmUgcXVhbHMgZnJvbSByaW5mby0+Y2xhdXNlIGluIHRoZSBjYXNlIG9mIHRyYW5z Zm9ybWF0aW9uLAorCQkqIHRvIGNyZWF0ZSBuZXcgUmVzdHJpY3RJbmZvOiBpbiB0aGlzIGNh c2Ugd2UgaGF2ZSBubyBvcHRpb25zIHRvIGF2b2lkCisJCSogc2VsZWN0aXZpdHkgZXN0aW1h dGlvbiBwcm9jZWR1cmUuCisJCSovCisJZm9yZWFjaChsY19lYXJncywgKChCb29sRXhwciAq KSBxdWFsKS0+YXJncykKKwl7CisJCUV4cHIJCQkgICAqYmFyZV9vcmFyZyA9IChFeHByICop IGxmaXJzdChsY19lYXJncyk7CisJCU5vZGUJCQkgICAqY29uc3RfZXhwcjsKKwkJTm9kZQkJ CSAgICpub25fY29uc3RfZXhwcjsKKwkJTGlzdENlbGwJCSAgICpsY19ncm91cHM7CisJCU9y Q2xhdXNlR3JvdXBFbnRyeSAqZ2VudHJ5OworCQlPaWQJCQkJCW9wbm87CisKKwkJLyogQ2hl Y2s6IGl0IGlzIGFuIGV4cHIgb2YgdGhlIGZvcm0gJ0YoeCkgb3BlciBDb25zdEV4cHInICov CisJCWlmICghYmFyZV9vcmFyZyAgfHwKKwkJCWNvbnRhaW5fdm9sYXRpbGVfZnVuY3Rpb25z KChOb2RlICopIGJhcmVfb3JhcmcpKQorCQl7CisJCQkvKiBBZ2FpbiwgaXQncyBub3QgdGhl IGV4cHIgd2UgY2FuIHRyYW5zZm9ybSAqLworCQkJb3JfbGlzdCA9IGxhcHBlbmQob3JfbGlz dCwgKHZvaWQgKikgYmFyZV9vcmFyZyk7CisJCQljb250aW51ZTsKKwkJfQorCisJCS8qIEdl dCBwb2ludGVycyB0byBjb25zdGFudCBhbmQgZXhwcmVzc2lvbiBzaWRlcyBvZiB0aGUgY2xh dXNlICovCisJCWNvbnN0X2V4cHIgPSBnZXRfcmlnaHRvcChiYXJlX29yYXJnKTsKKwkJbm9u X2NvbnN0X2V4cHIgPSBnZXRfbGVmdG9wKGJhcmVfb3JhcmcpOworCisJCW9wbm8gPSAoKE9w RXhwciAqKWJhcmVfb3JhcmcpLT5vcG5vOworCQkvL2lmICghb3BfbWVyZ2Vqb2luYWJsZShv cG5vLCBleHByVHlwZShub25fY29uc3RfZXhwcikpKQorCQkvL3sKKwkJCS8qIEFuZCBhZ2Fp biwgZmlsdGVyIG91dCBub24tZXF1YWxpdHkgb3BlcmF0b3JzICovCisJCS8vCW9yX2xpc3Qg PSBsYXBwZW5kKG9yX2xpc3QsICh2b2lkICopIGJhcmVfb3JhcmcpOworCQkvLwljb250aW51 ZTsKKwkJLy99CisKKwkJLyoKKwkJCSogQXQgdGhpcyBwb2ludCB3ZSBkZWZpbml0ZWx5IGhh dmUgYSB0cmFuc2Zvcm1hYmxlIGNsYXVzZS4KKwkJCSogQ2xhc3NpZnkgaXQgYW5kIGFkZCBp bnRvIHNwZWNpZmljIGdyb3VwIG9mIGNsYXVzZXMsIG9yIGNyZWF0ZSBuZXcKKwkJCSogZ3Jv dXAuCisJCQkqIFRPRE86IHRvIG1hbmFnZSBjb21wbGV4aXR5IGluIHRoZSBjYXNlIG9mIG1h bnkgZGlmZmVyZW50IGNsYXVzZXMKKwkJCSogKFgxPUMxKSBPUiAoWDI9QzIgT1IpIC4uLiAo WE4gPSBDTikgd2UgY291bGQgaW52ZW50IHNvbWV0aGluZworCQkJKiBsaWtlIGEgaGFzaCB0 YWJsZSAoaHRhYiBrZXkgPz8/KS4KKwkJCSovCisJCWZvcmVhY2gobGNfZ3JvdXBzLCBncm91 cHNfbGlzdCkKKwkJeworCQkJT3JDbGF1c2VHcm91cEVudHJ5ICp2ID0gKE9yQ2xhdXNlR3Jv dXBFbnRyeSAqKSBsZmlyc3QobGNfZ3JvdXBzKTsKKworCQkJQXNzZXJ0KHYtPm5vZGUgIT0g TlVMTCk7CisKKwkJCWlmIChlcXVhbCh2LT5ub2RlLCBub25fY29uc3RfZXhwcikpCisJCQl7 CisJCQkJdi0+Y29uc3RzID0gbGFwcGVuZCh2LT5jb25zdHMsIGNvbnN0X2V4cHIpOworCQkJ CW5vbl9jb25zdF9leHByID0gTlVMTDsKKwkJCQlicmVhazsKKwkJCX0KKwkJfQorCisJCWlm IChub25fY29uc3RfZXhwciA9PSBOVUxMKQorCQkJLyoKKwkJCQkqIFRoZSBjbGF1c2UgY2xh c3NpZmllZCBzdWNjZXNzZnVsbHkgYW5kIGFkZGVkIGludG8gZXhpc3RlZAorCQkJCSogY2xh dXNlIGdyb3VwLgorCQkJCSovCisJCQljb250aW51ZTsKKworCQkvKiBOZXcgY2xhdXNlIGdy b3VwIG5lZWRlZCAqLworCQlnZW50cnkgPSBwYWxsb2Moc2l6ZW9mKE9yQ2xhdXNlR3JvdXBF bnRyeSkpOworCQlnZW50cnktPm5vZGUgPSBub25fY29uc3RfZXhwcjsKKwkJZ2VudHJ5LT5j b25zdHMgPSBsaXN0X21ha2UxKGNvbnN0X2V4cHIpOworCQlnZW50cnktPmNvbGxhdGlvbiA9 IGV4cHJJbnB1dENvbGxhdGlvbigoTm9kZSAqKSBiYXJlX29yYXJnKTsKKwkJZ2VudHJ5LT5v cG5vID0gb3BubzsKKwkJZ2VudHJ5LT5leHByID0gYmFyZV9vcmFyZzsKKwkJZ3JvdXBzX2xp c3QgPSBsYXBwZW5kKGdyb3Vwc19saXN0LCAgKHZvaWQgKikgZ2VudHJ5KTsKKwl9CisKKwlp ZiAoZ3JvdXBzX2xpc3QgPT0gTklMKQorCXsKKwkJLyoKKwkJCSogTm8gYW55IHRyYW5zZm9y bWF0aW9ucyBwb3NzaWJsZSB3aXRoIHRoaXMgcmluZm8sIGp1c3QgYWRkIGl0c2VsZgorCQkJ KiB0byB0aGUgbGlzdCBhbmQgZ28gZnVydGhlci4KKwkJCSovCisJCW1vZGlmaWVkX2NsYXVz ZSA9IGxhcHBlbmQobW9kaWZpZWRfY2xhdXNlLCBxdWFsKTsKKwl9CisJZWxzZQorCXsKKwkJ LyogTGV0J3MgY29udmVydCBlYWNoIGdyb3VwIG9mIGNsYXVzZXMgdG8gYW4gSU4gb3BlcmF0 aW9uLiAqLworCisJCS8qCisJCQkqIEdvIHRocm91Z2ggdGhlIGxpc3Qgb2YgZ3JvdXBzIGFu ZCBjb252ZXJ0IGVhY2gsIHdoZXJlIG51bWJlciBvZgorCQkJKiBjb25zdHMgbW9yZSB0aGFu IDEuIHRyaXZpYWwgZ3JvdXBzIG1vdmUgdG8gT1ItbGlzdCBhZ2FpbgorCQkJKi8KKworCQlm b3JlYWNoKGxjX2FyZ3MsIGdyb3Vwc19saXN0KQorCQl7CisJCQlPckNsYXVzZUdyb3VwRW50 cnkgKmdlbnRyeSA9IChPckNsYXVzZUdyb3VwRW50cnkgKikgbGZpcnN0KGxjX2FyZ3MpOwor CQkJTGlzdAkJCSAgICphbGxleHByczsKKwkJCU9pZAkJCQkgICAgc2NhbGFyX3R5cGU7CisJ CQlPaWQJCQkJCWFycmF5X3R5cGU7CisKKwkJCUFzc2VydChsaXN0X2xlbmd0aChnZW50cnkt PmNvbnN0cykgPiAwKTsKKworCQkJaWYgKGxpc3RfbGVuZ3RoKGdlbnRyeS0+Y29uc3RzKSA9 PSAxKQorCQkJeworCQkJCS8qCisJCQkJICogT25seSBvbmUgZWxlbWVudCBpbiB0aGUgY2xh c3MuIFJldHVybiByaW5mbyBpbnRvIHRoZSBCb29sRXhwcgorCQkJCSAqIGFyZ3MgbGlzdCB1 bmNoYW5nZWQuCisJCQkJICovCisJCQkJbGlzdF9mcmVlKGdlbnRyeS0+Y29uc3RzKTsKKwkJ CQlvcl9saXN0ID0gbGFwcGVuZChvcl9saXN0LCBnZW50cnktPmV4cHIpOworCQkJCWNvbnRp bnVlOworCQkJfQorCisJCQkvKgorCQkJICogRG8gdGhlIHRyYW5zZm9ybWF0aW9uLgorCQkJ ICoKKwkJCSAqIEZpcnN0IG9mIGFsbCwgdHJ5IHRvIHNlbGVjdCBhIGNvbW1vbiB0eXBlIGZv ciB0aGUgYXJyYXkgZWxlbWVudHMuCisJCQkgKiBOb3RlIHRoYXQgc2luY2UgdGhlIExIUycg dHlwZSBpcyBmaXJzdCBpbiB0aGUgbGlzdCwgaXQgd2lsbCBiZQorCQkJICogcHJlZmVycmVk IHdoZW4gdGhlcmUgaXMgZG91YnQgKGVnLCB3aGVuIGFsbCB0aGUgUkhTIGl0ZW1zIGFyZQor CQkJICogdW5rbm93biBsaXRlcmFscykuCisJCQkgKgorCQkJICogTm90ZTogdXNlIGxpc3Rf Y29uY2F0IGhlcmUgbm90IGxjb25zLCB0byBhdm9pZCBkYW1hZ2luZyBybm9udmFycy4KKwkJ CSAqCisJCQkgKiBBcyBhIHNvdXJjZSBvZiBpbnNpZGVzLCB1c2UgbWFrZV9zY2FsYXJfYXJy YXlfb3AoKQorCQkJICovCisJCQlhbGxleHBycyA9IGxpc3RfY29uY2F0KGxpc3RfbWFrZTEo Z2VudHJ5LT5ub2RlKSwgZ2VudHJ5LT5jb25zdHMpOworCQkJc2NhbGFyX3R5cGUgPSBzZWxl Y3RfY29tbW9uX3R5cGUoTlVMTCwgYWxsZXhwcnMsIE5VTEwsIE5VTEwpOworCisJCQlpZiAo c2NhbGFyX3R5cGUgIT0gUkVDT1JET0lEICYmIE9pZElzVmFsaWQoc2NhbGFyX3R5cGUpKQor CQkJCWFycmF5X3R5cGUgPSBnZXRfYXJyYXlfdHlwZShzY2FsYXJfdHlwZSk7CisJCQllbHNl CisJCQkJYXJyYXlfdHlwZSA9IEludmFsaWRPaWQ7CisKKwkJCWlmIChhcnJheV90eXBlICE9 IEludmFsaWRPaWQpCisJCQl7CisJCQkJLyoKKwkJCQkgKiBPSzogY29lcmNlIGFsbCB0aGUg cmlnaHQtaGFuZCBub24tVmFyIGlucHV0cyB0byB0aGUgY29tbW9uCisJCQkJICogdHlwZSBh bmQgYnVpbGQgYW4gQXJyYXlFeHByIGZvciB0aGVtLgorCQkJCSAqLworCQkJCUxpc3QJICAg KmFleHByczsKKwkJCQlBcnJheUV4cHIgICpuZXdhOworCQkJCVNjYWxhckFycmF5T3BFeHBy ICpzYW9wZXhwcjsKKwkJCQlMaXN0Q2VsbCAqbDsKKworCQkJCWFleHBycyA9IE5JTDsKKwor CQkJCWZvcmVhY2gobCwgZ2VudHJ5LT5jb25zdHMpCisJCQkJeworCQkJCQlOb2RlCSAgICpy ZXhwciA9IChOb2RlICopIGxmaXJzdChsKTsKKworCQkJCQlyZXhwciA9IGNvZXJjZV90b19j b21tb25fdHlwZShOVUxMLCByZXhwciwKKwkJCQkJCQkJCQkJCXNjYWxhcl90eXBlLAorCQkJ CQkJCQkJCQkJIklOIik7CisJCQkJCWFleHBycyA9IGxhcHBlbmQoYWV4cHJzLCByZXhwcik7 CisJCQkJfQorCisJCQkJbmV3YSA9IG1ha2VOb2RlKEFycmF5RXhwcik7CisJCQkJLyogYXJy YXlfY29sbGlkIHdpbGwgYmUgc2V0IGJ5IHBhcnNlX2NvbGxhdGUuYyAqLworCQkJCW5ld2Et PmVsZW1lbnRfdHlwZWlkID0gc2NhbGFyX3R5cGU7CisJCQkJbmV3YS0+YXJyYXlfdHlwZWlk ID0gYXJyYXlfdHlwZTsKKwkJCQluZXdhLT5tdWx0aWRpbXMgPSBmYWxzZTsKKwkJCQluZXdh LT5lbGVtZW50cyA9IGFleHByczsKKwkJCQluZXdhLT5sb2NhdGlvbiA9IC0xOworCisJCQkJ c2FvcGV4cHIgPQorCQkJCQkoU2NhbGFyQXJyYXlPcEV4cHIgKikKKwkJCQkJCW1ha2Vfc2Nh bGFyX2FycmF5X29wKE5VTEwsCisJCQkJCQkJCQkJCSBsaXN0X21ha2UxKG1ha2VTdHJpbmco KGNoYXIgKikgIj0iKSksCisJCQkJCQkJCQkJCSB0cnVlLAorCQkJCQkJCQkJCQkgZ2VudHJ5 LT5ub2RlLAorCQkJCQkJCQkJCQkgKE5vZGUgKikgbmV3YSwKKwkJCQkJCQkJCQkJIC0xKTsK KworCQkJCW9yX2xpc3QgPSBsYXBwZW5kKG9yX2xpc3QsICh2b2lkICopIHNhb3BleHByKTsK KwkJCX0KKwkJCWVsc2UKKwkJCXsKKwkJCQlsaXN0X2ZyZWUoZ2VudHJ5LT5jb25zdHMpOwor CQkJCW9yX2xpc3QgPSBsYXBwZW5kKG9yX2xpc3QsIGdlbnRyeS0+ZXhwcik7CisJCQkJY29u dGludWU7CisJCQl9CisJCX0KKwl9CisKKwkJLyoKKwkJKiBNYWtlIGEgbmV3IHZlcnNpb24g b2YgdGhlIHJlc3RyaWN0aW9uLiBSZW1lbWJlciBzb3VyY2UgcmVzdHJpY3Rpb24KKwkJKiBj YW4gYmUgdXNlZCBpbiBhbm90aGVyIHBhdGggKFNlcVNjYW4sIGZvciBleGFtcGxlKS4KKwkJ Ki8KKwkvKiBPbmUgbW9yZSB0cmljazogYXNzZW1ibGUgY29ycmVjdCBjbGF1c2UgKi8KKwlx dWFsID0gbGlzdF9sZW5ndGgob3JfbGlzdCkgPiAxID8gbWFrZV9vcmNsYXVzZShvcl9saXN0 KSA6IGxpbml0aWFsKG9yX2xpc3QpOwogCisJLy9tb2RpZmllZF9jbGF1c2UgPSBsYXBwZW5k KG1vZGlmaWVkX2NsYXVzZSwgcXVhbCk7CisJbGlzdF9mcmVlX2RlZXAoZ3JvdXBzX2xpc3Qp OworCXNvbWV0aGluZ19jaGFuZ2VkID0gdHJ1ZTsKKworCS8qCisJICogQ2hlY2sgaWYgdHJh bnNmb3JtYXRpb24gaGFzIG1hZGUuIElmIG5vdGhpbmcgY2hhbmdlZCAtIHJldHVybgorCSAq IGJhc2VyZXN0cmljdGluZm8gYXMgaXMuCisJICovCisJLyogaWYgKHNvbWV0aGluZ19jaGFu Z2VkKQorCXsKKwkJcmV0dXJuIG1vZGlmaWVkX2NsYXVzZTsKKwl9ICovCisKKwlsaXN0X2Zy ZWUobW9kaWZpZWRfY2xhdXNlKTsKKwlyZXR1cm4gcXVhbDsKK30KK05vZGUgKgordHJhbnNm b3JtX29ycyhQbGFubmVySW5mbyAqcm9vdCwgRXhwciAqanRub2RlKQoreworCXJldHVybiAo Tm9kZSAqKSB0cmFuc2Zvcm1fb3JzX2Zvcl9yZWwoanRub2RlKTsKK30KIC8qCiAgKiBleHRy YWN0X3Jlc3RyaWN0aW9uX29yX2NsYXVzZXMKICAqCSAgRXhhbWluZSBqb2luIE9SLW9mLUFO RCBjbGF1c2VzIHRvIHNlZSBpZiBhbnkgdXNlZnVsIHJlc3RyaWN0aW9uIE9SCmRpZmYgLS1n aXQgYS9zcmMvaW5jbHVkZS9vcHRpbWl6ZXIvb3JjbGF1c2VzLmggYi9zcmMvaW5jbHVkZS9v cHRpbWl6ZXIvb3JjbGF1c2VzLmgKaW5kZXggZjlkYmU2YTI5NzIuLjZhMjMyYWViM2VkIDEw MDY0NAotLS0gYS9zcmMvaW5jbHVkZS9vcHRpbWl6ZXIvb3JjbGF1c2VzLmgKKysrIGIvc3Jj L2luY2x1ZGUvb3B0aW1pemVyL29yY2xhdXNlcy5oCkBAIC0xNyw1ICsxNyw1IEBACiAjaW5j bHVkZSAibm9kZXMvcGF0aG5vZGVzLmgiCiAKIGV4dGVybiB2b2lkIGV4dHJhY3RfcmVzdHJp Y3Rpb25fb3JfY2xhdXNlcyhQbGFubmVySW5mbyAqcm9vdCk7Ci0KK2V4dGVybiBOb2RlICog dHJhbnNmb3JtX29ycyhQbGFubmVySW5mbyAqcm9vdCwgRXhwciAqanRub2RlKTsKICNlbmRp ZgkJCQkJCQkvKiBPUkNMQVVTRVNfSCAqLwo= --------------iGczFavueqs6sJxDcwVu5RH3--