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 1vDzfk-002Yw3-Hy for pgsql-hackers@arkaria.postgresql.org; Wed, 29 Oct 2025 06:28:40 +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 1vDzfj-00Gdvf-Fn for pgsql-hackers@arkaria.postgresql.org; Wed, 29 Oct 2025 06:28:38 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1vDzfi-00GdvX-Ru for pgsql-hackers@lists.postgresql.org; Wed, 29 Oct 2025 06:28:38 +0000 Received: from mail-qt1-x842.google.com ([2607:f8b0:4864:20::842]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.96) (envelope-from ) id 1vDzfg-004Kon-0C for pgsql-hackers@lists.postgresql.org; Wed, 29 Oct 2025 06:28:37 +0000 Received: by mail-qt1-x842.google.com with SMTP id d75a77b69052e-4ed0f3d4611so14903761cf.3 for ; Tue, 28 Oct 2025 23:28:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1761719315; x=1762324115; darn=lists.postgresql.org; h=cc:to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=/0N9NNOBS0lnd88KU8QgcxSzchRn3GG5urzZrpXC6hQ=; b=CPfV/R9mp9JsiPbHVzdKaLDFlNv85CWX/xjl93RY5s7aKyjVzHEu3Vvf9KodG35drR JTBDWZocISp12AksizmvrEOmTKC/8CisY3r2L9Pt6Q6RSavVjlD353xiQMkXyMDOpAci hIaqklwFCzKD5AUJgvajvcclBP+EM85WED86iazWYHMZ6knOD6Dmu8/Oz4NTLjrvk4hX wK3ScobzeX4NAwURSEKS8TvwYDqF8oQUTY6MvmC2ubH4xG+GElRlmYm0ZpLq2DANKfup sFTvWdMlh0q5S7SfgPACJG+49hDUExwxiYYpqQ5q0INNg4ENdKvUFOwCN4T0z29GkZal 4gMw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761719315; x=1762324115; h=cc:to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=/0N9NNOBS0lnd88KU8QgcxSzchRn3GG5urzZrpXC6hQ=; b=tLYmmgVFotjNPPiB60LqegLbcpapE5ddHWWeXlWZXBGeTAUFKhR5H5ZpOFha2aolT8 KkAerVqs/V9ENBaC5atLONAXYRRok6+JAhKRHKXUfKjtPYnbI6AP+z5CYW7dXZJvT06y 1ObVMA2yBWJ2+Zzd4LRv4wcUK6e3O5zrU9xylw17RQablAg+TaUHmeK6O4wat4u8ouuf PBT4tU9eJL5HdaaQGBpaMQ1J2Zyl5zdlyRqP8ZGKtyYTcGQYvBxj6D9b3DxTpyG1SMx9 wDAe5nu0urYl9o0iNO0BXRCVwAAlvcJWr+l6XtaQUunF0ARRY6QBz4SeErjeYaOwm9Ha joQw== X-Gm-Message-State: AOJu0YwZOBaGoXJg9oTdFQyYIF9HroSy8z7gvaLrHjDfOj7DuIE/C961 hQ1woQjRt33BozoN12pPENlERO6dmE/HvkMz7b+jTMiXdRwBj9mOx7dqettwElUfmc34k0UPwnE Bru9QA6jAJvzuZBcOoHyyXkBJ8mUKiABSN4iPIMU= X-Gm-Gg: ASbGncuFVaKyZ8LTp0VqMAwY4LvlkGCFctu2BbZCvU52N+/7eUnNV+MY8zTIA0kpWuH IMiE698+5NPuFz65HS3uzao6gSI6gnJaUQWDnjD2MTxUN+V2tlDFtSb7p3EIN/bye9exWQPwToq 8V22GpxywwKRK0/roB6uf9M5lFmsWHho1VFN1pNu1t6V1+35EqXazRBjeNkaD8n6XEbe+s6gUsp gt4jnTCaVaCPR5k0L/FO1/VfOngya1p7qaSbeQqqIxuofcVMK7/vtdP8dNaOM7SlVquThhcwHm2 k4elrX23ESEo/eDJoTTkvPVnsxjQlY/8iWvKawsGvQDBL7/nLwrsxmYjNIy+amlY/OfSvD7HVAz Pbn+8EA015Wn6kTo= X-Google-Smtp-Source: AGHT+IEI7EvcqzOp0wVFwQqCOoMHr3fjhujkALBQ+pY3GjRKx105BDDHhgcwjjX38o7BrFfmwRjCYPxNGeOevVgYVRo= X-Received: by 2002:a05:622a:90b:b0:4e8:b739:6b5d with SMTP id d75a77b69052e-4ed15c020bdmr27045911cf.46.1761719314713; Tue, 28 Oct 2025 23:28:34 -0700 (PDT) MIME-Version: 1.0 From: John Naylor Date: Wed, 29 Oct 2025 13:28:21 +0700 X-Gm-Features: AWmQ_bkPO0FwovFq7LsKWpaBjn_f159sowsnLrV_j1rSZIZ9snaF0Dj5fR_swS4 Message-ID: Subject: tuple radix sort To: PostgreSQL Hackers Cc: Peter Geoghegan Content-Type: multipart/mixed; boundary="000000000000f2a8300642463df4" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --000000000000f2a8300642463df4 Content-Type: text/plain; charset="UTF-8" First, a quick demonstration of what this PoC can do on 1 million random not-NULL bigints: set wip_radix_sort = 'off'; select * from test order by a offset 1_000_000_000; 240ms set wip_radix_sort = 'on'; select * from test order by a offset 1_000_000_000; 140ms Background: Peter Geoghegan recently mentioned to me off-list an interesting set of techniques for sorting in the context of databases. I'm not yet sure how to approach certain aspects of that architecture, so I won't go into the full picture at this point. However, there is one piece that already fits well within our existing architecture, and that is using radix sort on datum1. The basic sequence is: 1. Partition tuples on first key NULL and not-NULL, according to NULLS FIRST or NULLS LAST. 2. Do normal qsort on the NULL partition using the tiebreak comparator. 3. Create a "conditioned" or "normalized" datum that encodes datum1 such that unsigned comparison is order-preserving, accounting for ASC / DESC as well. I've reused space now unused during in-memory not-NULL sorts: typedef struct { void *tuple; /* the tuple itself */ Datum datum1; /* value of first key column */ union { struct { bool isnull1; /* is first key column NULL? */ int srctape; /* source tape number */ }; Datum cond_datum1; /* sort key for radix sort */ }; } SortTuple; 4. Radix sort on cond_datum1. For the PoC I've based it on the implementation in "ska sort" [1] (C++, Boost license). For medium-sized sorts it uses "American flag sort" (there is a paper [3] co-authored by M. D. McIlroy, same as in the paper we reference for quicksort). For larger sorts it's similar, but performs multiple passes, which takes better advantage of modern CPUs. Upon recursion, sorts on small partitions divert to quicksort. Any necessary tiebreaks are handled by quicksort, either after the end of radix sort, or when diverting to small quicksort. 5. Reset isnull1 to "false" before returning to the caller. This also must be done when diverting to quicksort. Next steps: Try to find regressions (help welcome here). The v1 patch has some optimizations, but in other ways things are simple and/or wasteful. Exactly how things fit together will be informed by what, if anything, has to be done to avoid regressions. I suspect the challenge will be multikey sorts when the first key has low cardinality. This is because tiebreaks are necessarily postponed rather than taken care of up front. I'm optimistic, since low cardinality cases can be even faster than our B&M qsort, so we have some headroom: drop table if exists test; create unlogged table test (a bigint); insert into test select (1_000_000_000 * random())::bigint % 8 -- mod -- (1_000_000_000 * random())::bigint -- random, for the case at the top from generate_series(1,1_000_000,1) i; vacuum freeze test; select pg_prewarm('test'); set work_mem = '64MB'; set wip_radix_sort = 'off'; select * from test order by a offset 1_000_000_000; 95ms set wip_radix_sort = 'on'; select * from test order by a offset 1_000_000_000; 84ms [1] https://github.com/skarupke/ska_sort/tree/master [2] https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/ [3] http://static.usenix.org/publications/compsystems/1993/win_mcilroy.pdf -- John Naylor Amazon Web Services --000000000000f2a8300642463df4 Content-Type: application/x-patch; name="v1-0001-Use-radix-sort-when-datum1-is-an-integer-type.patch" Content-Disposition: attachment; filename="v1-0001-Use-radix-sort-when-datum1-is-an-integer-type.patch" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_mh7i3iyj0 RnJvbSA4MTg1ZjViODgzNGQ1OGJkZGMxYzM3OTY4ZDMzNGJkMmM5N2JjYzE1IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBKb2huIE5heWxvciA8am9obi5uYXlsb3JAcG9zdGdyZXNxbC5v cmc+CkRhdGU6IEZyaSwgMTcgT2N0IDIwMjUgMDk6NTc6NDMgKzA3MDAKU3ViamVjdDogW1BBVENI IHYxXSBVc2UgcmFkaXggc29ydCB3aGVuIGRhdHVtMSBpcyBhbiBpbnRlZ2VyIHR5cGUKClhYWCBy ZWdyZXNzaW9uIHRlc3RzIGRvbid0IHBhc3MgZm9yIHVuZGVyc3BlY2lmaWVkIHF1ZXJpZXM7IHRo aXMKaXMgZXhwZWN0ZWQKLS0tCiBzcmMvYmFja2VuZC91dGlscy9taXNjL2d1Y19wYXJhbWV0ZXJz LmRhdCB8ICAgNyArCiBzcmMvYmFja2VuZC91dGlscy9zb3J0L3R1cGxlc29ydC5jICAgICAgICB8 IDY0MSArKysrKysrKysrKysrKysrKysrKystCiBzcmMvaW5jbHVkZS91dGlscy9ndWMuaCAgICAg ICAgICAgICAgICAgICB8ICAgMSArCiBzcmMvaW5jbHVkZS91dGlscy90dXBsZXNvcnQuaCAgICAg ICAgICAgICB8ICAxMiArLQogNCBmaWxlcyBjaGFuZ2VkLCA2NDEgaW5zZXJ0aW9ucygrKSwgMjAg ZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2JhY2tlbmQvdXRpbHMvbWlzYy9ndWNfcGFy YW1ldGVycy5kYXQgYi9zcmMvYmFja2VuZC91dGlscy9taXNjL2d1Y19wYXJhbWV0ZXJzLmRhdApp bmRleCBkNmZjODMzMzg1MC4uZjhmYzZjODgwODIgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL3V0 aWxzL21pc2MvZ3VjX3BhcmFtZXRlcnMuZGF0CisrKyBiL3NyYy9iYWNrZW5kL3V0aWxzL21pc2Mv Z3VjX3BhcmFtZXRlcnMuZGF0CkBAIC02ODEsNiArNjgxLDEzIEBACiAgIGJvb3RfdmFsID0+ICdm YWxzZScsCiB9LAogCit7IG5hbWUgPT4gJ3dpcF9yYWRpeF9zb3J0JywgdHlwZSA9PiAnYm9vbCcs IGNvbnRleHQgPT4gJ1BHQ19VU0VSU0VUJywgZ3JvdXAgPT4gJ0RFVkVMT1BFUl9PUFRJT05TJywK KyAgc2hvcnRfZGVzYyA9PiAnVGVzdCByYWRpeCBzb3J0IGZvciBkZWJ1Z2dpbmcuJywKKyAgZmxh Z3MgPT4gJ0dVQ19OT1RfSU5fU0FNUExFJywKKyAgdmFyaWFibGUgPT4gJ3dpcF9yYWRpeF9zb3J0 JywKKyAgYm9vdF92YWwgPT4gJ3RydWUnLAorfSwKKwogIyB0aGlzIGlzIHVuZG9jdW1lbnRlZCBi ZWNhdXNlIG5vdCBleHBvc2VkIGluIGEgc3RhbmRhcmQgYnVpbGQKIHsgbmFtZSA9PiAndHJhY2Vf c3luY3NjYW4nLCB0eXBlID0+ICdib29sJywgY29udGV4dCA9PiAnUEdDX1VTRVJTRVQnLCBncm91 cCA9PiAnREVWRUxPUEVSX09QVElPTlMnLAogICBzaG9ydF9kZXNjID0+ICdHZW5lcmF0ZSBkZWJ1 Z2dpbmcgb3V0cHV0IGZvciBzeW5jaHJvbml6ZWQgc2Nhbm5pbmcuJywKZGlmZiAtLWdpdCBhL3Ny Yy9iYWNrZW5kL3V0aWxzL3NvcnQvdHVwbGVzb3J0LmMgYi9zcmMvYmFja2VuZC91dGlscy9zb3J0 L3R1cGxlc29ydC5jCmluZGV4IDVkNDQxMWRjMzNmLi4zYjgyMGQyNDVlOSAxMDA2NDQKLS0tIGEv c3JjL2JhY2tlbmQvdXRpbHMvc29ydC90dXBsZXNvcnQuYworKysgYi9zcmMvYmFja2VuZC91dGls cy9zb3J0L3R1cGxlc29ydC5jCkBAIC0xMDQsNiArMTA0LDcgQEAKICNpbmNsdWRlICJjb21tYW5k cy90YWJsZXNwYWNlLmgiCiAjaW5jbHVkZSAibWlzY2FkbWluLmgiCiAjaW5jbHVkZSAicGdfdHJh Y2UuaCIKKyNpbmNsdWRlICJwb3J0L3BnX2JpdHV0aWxzLmgiCiAjaW5jbHVkZSAic3RvcmFnZS9z aG1lbS5oIgogI2luY2x1ZGUgInV0aWxzL2d1Yy5oIgogI2luY2x1ZGUgInV0aWxzL21lbXV0aWxz LmgiCkBAIC0xMjIsNiArMTIzLDcgQEAKIAogLyogR1VDIHZhcmlhYmxlcyAqLwogYm9vbAkJdHJh Y2Vfc29ydCA9IGZhbHNlOworYm9vbAkJd2lwX3JhZGl4X3NvcnQgPSB0cnVlOwogCiAjaWZkZWYg REVCVUdfQk9VTkRFRF9TT1JUCiBib29sCQlvcHRpbWl6ZV9ib3VuZGVkX3NvcnQgPSB0cnVlOwpA QCAtNjE1LDYgKzYxNyw0MDggQEAgcXNvcnRfdHVwbGVfaW50MzJfY29tcGFyZShTb3J0VHVwbGUg KmEsIFNvcnRUdXBsZSAqYiwgVHVwbGVzb3J0c3RhdGUgKnN0YXRlKQogI2RlZmluZSBTVF9ERUZJ TkUKICNpbmNsdWRlICJsaWIvc29ydF90ZW1wbGF0ZS5oIgogCisKKy8qCisgKiBXSVA6IEZvciBu b3cgcHJlZmVyIHRlc3QgY292ZXJhZ2Ugb2YgcmFkaXggc29ydCBpbiBBc3NlcnQgYnVpbGRzLgor ICogVGhlIHRocmVzaG9sZHMgYXJlIGp1c3QgZ3Vlc3NlcworICovCisjaWZkZWYgVVNFX0FTU0VS VF9DSEVDS0lORworI2RlZmluZSBRU09SVF9USFJFU0hPTEQgMAorI2RlZmluZSBBTUVSSUNBTl9G TEFHX1RIUkVTSE9MRCAwCisjZWxzZQorI2RlZmluZSBRU09SVF9USFJFU0hPTEQgNjQKKyNkZWZp bmUgQU1FUklDQU5fRkxBR19USFJFU0hPTEQgMTUwMAorI2VuZGlmCisKK3R5cGVkZWYgc3RydWN0 IFBhcnRpdGlvbkluZm8KK3sKKwl1bmlvbgorCXsKKwkJc2l6ZV90CQljb3VudDsKKwkJc2l6ZV90 CQlvZmZzZXQ7CisJfTsKKwlzaXplX3QJCW5leHRfb2Zmc2V0OworfQkJCVBhcnRpdGlvbkluZm87 CisKK3N0YXRpYyBpbmxpbmUgdWludDhfdAorZXh0cmFjdF9rZXkoRGF0dW0ga2V5LCBpbnQgbGV2 ZWwpCit7CisJcmV0dXJuIChrZXkgPj4gKCgoU0laRU9GX0RBVFVNIC0gMSkgLSBsZXZlbCkgKiA4 KSkgJiAweEZGOworfQorCitzdGF0aWMgaW5saW5lIHZvaWQKK3N3YXAoU29ydFR1cGxlICphLCBT b3J0VHVwbGUgKmIpCit7CisJU29ydFR1cGxlCXRtcCA9ICphOworCisJKmEgPSAqYjsKKwkqYiA9 IHRtcDsKK30KKworLyoKKyAqIENvbmRpdGlvbiBkYXR1bSB0byB3b3JrIHdpdGggcHVyZSB1bnNp Z25lZCBjb21wYXJpc29uLAorICogdGFraW5nIEFTQy9ERVNDIGludG8gYWNjb3VudCBhcyB3ZWxs LgorICovCitzdGF0aWMgaW5saW5lIERhdHVtCitjb25kaXRpb25fZGF0dW0oRGF0dW0gb3JpZywg U29ydFN1cHBvcnQgc3N1cCkKK3sKKwlEYXR1bQkJY29uZF9kYXR1bTE7CisKKwlpZiAoc3N1cC0+ Y29tcGFyYXRvciA9PSBzc3VwX2RhdHVtX3NpZ25lZF9jbXApCisJeworCQkvKiBpdCB3YXMgYWxy ZWFkeSBjYXN0IHRvIHVuc2lnbmVkIHdoZW4gc3RvcmVkICovCisJCWNvbmRfZGF0dW0xID0gb3Jp ZyBeIChVSU5UNjRDT05TVCgxKSA8PCA2Myk7CisJfQorCWVsc2UgaWYgKHNzdXAtPmNvbXBhcmF0 b3IgPT0gc3N1cF9kYXR1bV9pbnQzMl9jbXApCisJeworCQkvKgorCQkgKiBGaXJzdCBub3JtYWxp emUgdG8gdWludDMyLiBUZWNobmljYWxseSwgd2UgZG9uJ3QgbmVlZCB0byBkbyB0aGlzLAorCQkg KiBidXQgaXQgZm9yY2VzIHRoZSB1cHBlciBieXRlcyB0byByZW1haW4gdGhlIHNhbWUgcmVnYXJk bGVzcyBvZgorCQkgKiBzaWduLgorCQkgKi8KKwkJdWludDMyCQl1MzIgPSBEYXR1bUdldFVJbnQz MihvcmlnKSBeICgodWludDMyKSAxIDw8IDMxKTsKKworCQljb25kX2RhdHVtMSA9IFVJbnQzMkdl dERhdHVtKHUzMik7CisJfQorCWVsc2UKKwl7CisJCUFzc2VydChzc3VwLT5jb21wYXJhdG9yID09 IHNzdXBfZGF0dW1fdW5zaWduZWRfY21wKTsKKwkJY29uZF9kYXR1bTEgPSBvcmlnOworCX0KKwor CWlmIChzc3VwLT5zc3VwX3JldmVyc2UpCisJCWNvbmRfZGF0dW0xID0gfmNvbmRfZGF0dW0xOwor CisJcmV0dXJuIGNvbmRfZGF0dW0xOworfQorCisvKgorICogQmFzZWQgb24gaW1wbGVtZW50YXRp b24gaW4gaHR0cHM6Ly9naXRodWIuY29tL3NrYXJ1cGtlL3NrYV9zb3J0IChCb29zdCBsaWNlbnNl KQorICogVE9ETzogbWF0Y2ggcXNvcnQgQVBJIHdpdGggbnVtYmVyIG9mIGVsZW1lbnRzIHJhdGhl ciB0aGFuIGVuZCBwb2ludGVyCisgKi8KK3N0YXRpYyB2b2lkCithbWVyaWNhbl9mbGFnX3NvcnQo U29ydFR1cGxlICpiZWdpbiwKKwkJCQkgICBTb3J0VHVwbGUgKmVuZCwgaW50IGxldmVsLCBUdXBs ZXNvcnRzdGF0ZSAqc3RhdGUpCit7CisJUGFydGl0aW9uSW5mbyBwYXJ0aXRpb25zWzI1Nl0gPSB7 MH07CisJdWludDhfdAkJcmVtYWluaW5nX3BhcnRpdGlvbnNbMjU2XSA9IHswfTsKKwlzaXplX3QJ CXRvdGFsID0gMDsKKwlpbnQJCQludW1fcGFydGl0aW9ucyA9IDA7CisKKwkvKiBjb3VudCBrZXkg Y2h1bmtzICovCisJZm9yIChTb3J0VHVwbGUgKnR1cCA9IGJlZ2luOyB0dXAgPCBlbmQ7IHR1cCsr KQorCXsKKwkJdWludDgJCWtleV9jaHVuazsKKworCQlrZXlfY2h1bmsgPSBleHRyYWN0X2tleSh0 dXAtPmNvbmRfZGF0dW0xLCBsZXZlbCk7CisJCXBhcnRpdGlvbnNba2V5X2NodW5rXS5jb3VudCsr OworCX0KKworCS8qIGNvbXB1dGUgcGFydGl0aW9uIG9mZnNldHMgKi8KKwlmb3IgKGludCBpID0g MDsgaSA8IDI1NjsgKytpKQorCXsKKwkJc2l6ZV90CQljb3VudCA9IHBhcnRpdGlvbnNbaV0uY291 bnQ7CisKKwkJaWYgKCFjb3VudCkKKwkJCWNvbnRpbnVlOworCQlwYXJ0aXRpb25zW2ldLm9mZnNl dCA9IHRvdGFsOworCQl0b3RhbCArPSBjb3VudDsKKwkJcGFydGl0aW9uc1tpXS5uZXh0X29mZnNl dCA9IHRvdGFsOworCQlyZW1haW5pbmdfcGFydGl0aW9uc1tudW1fcGFydGl0aW9uc10gPSBpOwor CQkrK251bV9wYXJ0aXRpb25zOworCX0KKworCS8qIHBlcm11dGUgdHVwbGVzIHRvIGNvcnJlY3Qg cGFydGl0aW9uICovCisJaWYgKG51bV9wYXJ0aXRpb25zID4gMSkKKwl7CisJCXVpbnQ4X3QgICAg KmN1cnJlbnRfYmxvY2tfcHRyID0gcmVtYWluaW5nX3BhcnRpdGlvbnM7CisJCVBhcnRpdGlvbklu Zm8gKmN1cnJlbnRfYmxvY2sgPSBwYXJ0aXRpb25zICsgKmN1cnJlbnRfYmxvY2tfcHRyOworCQl1 aW50OF90ICAgICpsYXN0X2Jsb2NrID0gcmVtYWluaW5nX3BhcnRpdGlvbnMgKyBudW1fcGFydGl0 aW9ucyAtIDE7CisJCVNvcnRUdXBsZSAgKml0ID0gYmVnaW47CisJCVNvcnRUdXBsZSAgKmJsb2Nr X2VuZCA9IGJlZ2luICsgY3VycmVudF9ibG9jay0+bmV4dF9vZmZzZXQ7CisJCVNvcnRUdXBsZSAg Kmxhc3RfZWxlbWVudCA9IGVuZCAtIDE7CisKKwkJZm9yICg7OykKKwkJeworCQkJUGFydGl0aW9u SW5mbyAqYmxvY2sgPSBwYXJ0aXRpb25zICsgZXh0cmFjdF9rZXkoaXQtPmNvbmRfZGF0dW0xLCBs ZXZlbCk7CisKKwkJCWlmIChibG9jayA9PSBjdXJyZW50X2Jsb2NrKQorCQkJeworCQkJCSsraXQ7 CisJCQkJaWYgKGl0ID09IGxhc3RfZWxlbWVudCkKKwkJCQkJYnJlYWs7CisJCQkJZWxzZSBpZiAo aXQgPT0gYmxvY2tfZW5kKQorCQkJCXsKKwkJCQkJZm9yICg7OykKKwkJCQkJeworCQkJCQkJKytj dXJyZW50X2Jsb2NrX3B0cjsKKwkJCQkJCWlmIChjdXJyZW50X2Jsb2NrX3B0ciA9PSBsYXN0X2Js b2NrKQorCQkJCQkJCWdvdG8gcmVjdXJzZTsKKwkJCQkJCWN1cnJlbnRfYmxvY2sgPSBwYXJ0aXRp b25zICsgKmN1cnJlbnRfYmxvY2tfcHRyOworCQkJCQkJaWYgKGN1cnJlbnRfYmxvY2stPm9mZnNl dCAhPSBjdXJyZW50X2Jsb2NrLT5uZXh0X29mZnNldCkKKwkJCQkJCQlicmVhazsKKwkJCQkJfQor CisJCQkJCWl0ID0gYmVnaW4gKyBjdXJyZW50X2Jsb2NrLT5vZmZzZXQ7CisJCQkJCWJsb2NrX2Vu ZCA9IGJlZ2luICsgY3VycmVudF9ibG9jay0+bmV4dF9vZmZzZXQ7CisJCQkJfQorCQkJfQorCQkJ ZWxzZQorCQkJeworCQkJCXNpemVfdAkJb2Zmc2V0ID0gYmxvY2stPm9mZnNldCsrOworCisJCQkJ c3dhcChpdCwgYmVnaW4gKyBvZmZzZXQpOworCQkJfQorCQl9CisJfQorCityZWN1cnNlOgorCXNp emVfdAkJc3RhcnRfb2Zmc2V0ID0gMDsKKwlTb3J0VHVwbGUgICpwYXJ0aXRpb25fYmVnaW4gPSBi ZWdpbjsKKworCWZvciAodWludDhfdCAqaXQgPSByZW1haW5pbmdfcGFydGl0aW9ucywgKmVuZCA9 IHJlbWFpbmluZ19wYXJ0aXRpb25zICsgbnVtX3BhcnRpdGlvbnM7CisJCSBpdCAhPSBlbmQ7CisJ CSArK2l0KQorCXsKKwkJc2l6ZV90CQllbmRfb2Zmc2V0ID0gcGFydGl0aW9uc1sqaXRdLm5leHRf b2Zmc2V0OworCQlTb3J0VHVwbGUgICpwYXJ0aXRpb25fZW5kID0gYmVnaW4gKyBlbmRfb2Zmc2V0 OworCQlwdHJkaWZmX3QJbnVtX2VsZW1lbnRzID0gZW5kX29mZnNldCAtIHN0YXJ0X29mZnNldDsK KworCQlpZiAobnVtX2VsZW1lbnRzID4gMSkKKwkJeworCQkJaWYgKGxldmVsIDwgU0laRU9GX0RB VFVNIC0gMSkKKwkJCXsKKwkJCQlpZiAobnVtX2VsZW1lbnRzIDwgUVNPUlRfVEhSRVNIT0xEKQor CQkJCXsKKwkJCQkJLyogcmVzdG9yZSBOT1QgTlVMTCBmb3IgZmFsbGJhY2sgcXNvcnQgKi8KKwkJ CQkJLyoKKwkJCQkJICogV0lQOiBNYXliZSB3ZSBjYW4gaGF2ZSBhIHFzb3J0IHRoYXQgc2tpcHMg dGhlIE5VTEwKKwkJCQkJICogY29tcGFyaXNvbnMsIGNvbXBhcmVzIGRpcmVjdGx5IG9uIGNvbmRf ZGF0dW0xLCBhbmQgb25seQorCQkJCQkgKiByZXN0b3JlcyBpc251bGwxIGlmIHdlIGFjdHVhbGx5 IGNhbGwgdGhlIHRpZWJyZWFrLgorCQkJCQkgKi8KKwkJCQkJZm9yIChTb3J0VHVwbGUgKnR1cCA9 IHBhcnRpdGlvbl9iZWdpbjsKKwkJCQkJCSB0dXAgPCBwYXJ0aXRpb25fYmVnaW4gKyBudW1fZWxl bWVudHM7CisJCQkJCQkgdHVwKyspCisJCQkJCQl0dXAtPmlzbnVsbDEgPSBmYWxzZTsKKworCQkJ CQlxc29ydF90dXBsZShwYXJ0aXRpb25fYmVnaW4sCisJCQkJCQkJCW51bV9lbGVtZW50cywKKwkJ CQkJCQkJc3RhdGUtPmJhc2UuY29tcGFyZXR1cCwKKwkJCQkJCQkJc3RhdGUpOworCQkJCX0KKwkJ CQllbHNlCisJCQkJeworCQkJCQlhbWVyaWNhbl9mbGFnX3NvcnQocGFydGl0aW9uX2JlZ2luLAor CQkJCQkJCQkJICAgcGFydGl0aW9uX2VuZCwKKwkJCQkJCQkJCSAgIGxldmVsICsgMSwKKwkJCQkJ CQkJCSAgIHN0YXRlKTsKKwkJCQl9CisJCQl9CisJCQllbHNlIGlmIChzdGF0ZS0+YmFzZS5vbmx5 S2V5ID09IE5VTEwpCisJCQl7CisJCQkJLyoKKwkJCQkgKiBGaW5pc2hlZCByYWRpeCBzb3J0IG9u IGFsbCBieXRlcyBvZiBjb25kX2RhdHVtMSAocG9zc2liaWx5CisJCQkJICogYWJicmV2aWF0ZWQp LCBub3cgcXNvcnQgd2l0aCB0aWVicmVhayBjb21wYXJhdG9yLgorCQkJCSAqLworCisJCQkJLyog Zmlyc3QgcmVzdG9yZSBOT1QgTlVMTCBmb3IgbGF0ZXIgY29tcGFyYXRvcnMgKi8KKwkJCQlmb3Ig KFNvcnRUdXBsZSAqdHVwID0gcGFydGl0aW9uX2JlZ2luOworCQkJCQkgdHVwIDwgcGFydGl0aW9u X2JlZ2luICsgbnVtX2VsZW1lbnRzOworCQkJCQkgdHVwKyspCisJCQkJCXR1cC0+aXNudWxsMSA9 IGZhbHNlOworCisJCQkJcXNvcnRfdHVwbGUocGFydGl0aW9uX2JlZ2luLAorCQkJCQkJCW51bV9l bGVtZW50cywKKwkJCQkJCQlzdGF0ZS0+YmFzZS5jb21wYXJldHVwX3RpZWJyZWFrLAorCQkJCQkJ CXN0YXRlKTsKKwkJCX0KKwkJfQorCQlzdGFydF9vZmZzZXQgPSBlbmRfb2Zmc2V0OworCQlwYXJ0 aXRpb25fYmVnaW4gPSBwYXJ0aXRpb25fZW5kOworCX0KK30KKworLyoKKyAqIEJhc2VkIG9uIGlt cGxlbWVudGF0aW9uIGluIGh0dHBzOi8vZ2l0aHViLmNvbS9za2FydXBrZS9za2Ffc29ydCAoQm9v c3QgbGljZW5zZSksCisgKiB3aXRoIHRoZSBmb2xsb3dpbmcgY2hhbmdlczoKKyAqICAtIHVucm9s bCBsb29wIGluIGNvdW50aW5nIHN0ZXAKKyAqICAtIGNvdW50IHNvcnRlZCBwYXJ0aXRpb25zIGlu IGV2ZXJ5IHBhc3MsIHJhdGhlciB0aGFuIG1haW50YWluaW5nIGxpc3Qgb2YgdW5zb3J0ZWQgcGFy dGl0aW9ucworICogVE9ETzogbWF0Y2ggcXNvcnQgQVBJIHdpdGggbnVtYmVyIG9mIGVsZW1lbnRz IHJhdGhlciB0aGFuIGVuZCBwb2ludGVyCisgKi8KK3N0YXRpYyB2b2lkCitza2FfYnl0ZV9zb3J0 KFNvcnRUdXBsZSAqYmVnaW4sCisJCQkgIFNvcnRUdXBsZSAqZW5kLCBpbnQgbGV2ZWwsIFR1cGxl c29ydHN0YXRlICpzdGF0ZSkKK3sKKwkvKiBzaXplX3QJCWNvdW50czBbMjU2XSA9IHswfTsgKi8K KwlzaXplX3QJCWNvdW50czFbMjU2XSA9IHswfTsKKwlzaXplX3QJCWNvdW50czJbMjU2XSA9IHsw fTsKKwlzaXplX3QJCWNvdW50czNbMjU2XSA9IHswfTsKKwlQYXJ0aXRpb25JbmZvIHBhcnRpdGlv bnNbMjU2XSA9IHswfTsKKwl1aW50OF90CQlyZW1haW5pbmdfcGFydGl0aW9uc1syNTZdID0gezB9 OworCXNpemVfdAkJdG90YWwgPSAwOworCWludAkJCW51bV9wYXJ0aXRpb25zID0gMDsKKwlpbnQJ CQludW1fcmVtYWluaW5nOworCVNvcnRUdXBsZSAgKmN0dXA7CisKKwkvKiBjb3VudCBrZXkgY2h1 bmtzLCB1bnJvbGxlZCBmb3Igc3BlZWQgKi8KKworCWZvciAoY3R1cCA9IGJlZ2luOyBjdHVwICsg NCA8IGVuZDsgY3R1cCArPSA0KQorCXsKKwkJdWludDgJCWtleV9jaHVuazAgPSBleHRyYWN0X2tl eSgoY3R1cCArIDApLT5jb25kX2RhdHVtMSwgbGV2ZWwpOworCQl1aW50OAkJa2V5X2NodW5rMSA9 IGV4dHJhY3Rfa2V5KChjdHVwICsgMSktPmNvbmRfZGF0dW0xLCBsZXZlbCk7CisJCXVpbnQ4CQlr ZXlfY2h1bmsyID0gZXh0cmFjdF9rZXkoKGN0dXAgKyAyKS0+Y29uZF9kYXR1bTEsIGxldmVsKTsK KwkJdWludDgJCWtleV9jaHVuazMgPSBleHRyYWN0X2tleSgoY3R1cCArIDMpLT5jb25kX2RhdHVt MSwgbGV2ZWwpOworCisJCXBhcnRpdGlvbnNba2V5X2NodW5rMF0uY291bnQrKzsKKwkJY291bnRz MVtrZXlfY2h1bmsxXSsrOworCQljb3VudHMyW2tleV9jaHVuazJdKys7CisJCWNvdW50czNba2V5 X2NodW5rM10rKzsKKworCX0KKworCWZvciAoc2l6ZV90IGkgPSAwOyBpIDwgMjU2OyBpKyspCisJ CXBhcnRpdGlvbnNbaV0uY291bnQgKz0gY291bnRzMVtpXSArIGNvdW50czJbaV0gKyBjb3VudHMz W2ldOworCisJZm9yICg7IGN0dXAgPCBlbmQ7IGN0dXArKykKKwl7CisJCXVpbnQ4CQlrZXlfY2h1 bms7CisKKwkJa2V5X2NodW5rID0gZXh0cmFjdF9rZXkoY3R1cC0+Y29uZF9kYXR1bTEsIGxldmVs KTsKKwkJcGFydGl0aW9uc1trZXlfY2h1bmtdLmNvdW50Kys7CisJfQorCisJLyogY29tcHV0ZSBw YXJ0aXRpb24gb2Zmc2V0cyAqLworCWZvciAoaW50IGkgPSAwOyBpIDwgMjU2OyArK2kpCisJewor CQlzaXplX3QJCWNvdW50ID0gcGFydGl0aW9uc1tpXS5jb3VudDsKKworCQlpZiAoY291bnQpCisJ CXsKKwkJCXBhcnRpdGlvbnNbaV0ub2Zmc2V0ID0gdG90YWw7CisJCQl0b3RhbCArPSBjb3VudDsK KwkJCXJlbWFpbmluZ19wYXJ0aXRpb25zW251bV9wYXJ0aXRpb25zXSA9IGk7CisJCQkrK251bV9w YXJ0aXRpb25zOworCQl9CisJCXBhcnRpdGlvbnNbaV0ubmV4dF9vZmZzZXQgPSB0b3RhbDsKKwl9 CisKKwludW1fcmVtYWluaW5nID0gbnVtX3BhcnRpdGlvbnM7CisKKwkvKgorCSAqIFBlcm11dGUg dHVwbGVzIHRvIGNvcnJlY3QgcGFydGl0aW9uLiBJZiB3ZSBzdGFydGVkIHdpdGggb25lIHBhcnRp dGlvbiwKKwkgKiB0aGVyZSBpcyBub3RoaW5nIHRvIGRvLiBJZiBhIHBlcm11dGF0aW9uIGZyb20g YSBwcmV2aW91cyBpdGVyYXRpb24KKwkgKiByZXN1bHRzIGluIGEgc2luZ2xlIHBhcnRpdGlvbiB0 aGF0IGhhc24ndCBiZWVuIG1hcmtlZCBhcyBzb3J0ZWQsIHdlCisJICoga25vdyBpdCdzIGFjdHVh bGx5IHNvcnRlZC4KKwkgKi8KKwl3aGlsZSAobnVtX3JlbWFpbmluZyA+IDEpCisJeworCQkvKgor CQkgKiBXZSBjYW4gb25seSBleGl0IHRoZSBsb29wIHdoZW4gYWxsIHBhcnRpdGlvbnMgYXJlIHNv cnRlZCwgc28gbXVzdAorCQkgKiByZXNldCBldmVyeSBpdGVyYXRpb24KKwkJICovCisJCW51bV9y ZW1haW5pbmcgPSBudW1fcGFydGl0aW9uczsKKworCQlmb3IgKGludCBpID0gMDsgaSA8IG51bV9w YXJ0aXRpb25zOyBpKyspCisJCXsKKwkJCXVpbnQ4CQlpZHggPSByZW1haW5pbmdfcGFydGl0aW9u c1tpXTsKKworCQkJUGFydGl0aW9uSW5mbyBwYXJ0ID0gcGFydGl0aW9uc1tpZHhdOworCisJCQlm b3IgKFNvcnRUdXBsZSAqc3QgPSBiZWdpbiArIHBhcnQub2Zmc2V0OworCQkJCSBzdCA8IGJlZ2lu ICsgcGFydC5uZXh0X29mZnNldDsKKwkJCQkgc3QrKykKKwkJCXsKKwkJCQl1aW50OAkJdGhpc19w YXJ0aXRpb24gPSBleHRyYWN0X2tleShzdC0+Y29uZF9kYXR1bTEsIGxldmVsKTsKKwkJCQlzaXpl X3QJCW9mZnNldCA9IHBhcnRpdGlvbnNbdGhpc19wYXJ0aXRpb25dLm9mZnNldCsrOworCisJCQkJ QXNzZXJ0KGJlZ2luICsgb2Zmc2V0IDwgZW5kKTsKKwkJCQlzd2FwKHN0LCBiZWdpbiArIG9mZnNl dCk7CisJCQl9OworCisJCQlpZiAocGFydC5vZmZzZXQgPT0gcGFydC5uZXh0X29mZnNldCkKKwkJ CXsKKwkJCQkvKiBwYXJ0aXRpb24gaXMgc29ydGVkOyBza2lwICovCisJCQkJbnVtX3JlbWFpbmlu Zy0tOworCQkJfQorCQl9CisJfQorCisJeworCQlzaXplX3QJCXN0YXJ0X29mZnNldCA9IDA7CisJ CVNvcnRUdXBsZSAgKnBhcnRpdGlvbl9iZWdpbiA9IGJlZ2luOworCisJCWZvciAodWludDhfdCAq aXQgPSByZW1haW5pbmdfcGFydGl0aW9ucywgKmVuZCA9IHJlbWFpbmluZ19wYXJ0aXRpb25zICsg bnVtX3BhcnRpdGlvbnM7CisJCQkgaXQgIT0gZW5kOworCQkJICsraXQpCisJCXsKKwkJCXNpemVf dAkJZW5kX29mZnNldCA9IHBhcnRpdGlvbnNbKml0XS5uZXh0X29mZnNldDsKKwkJCVNvcnRUdXBs ZSAgKnBhcnRpdGlvbl9lbmQgPSBiZWdpbiArIGVuZF9vZmZzZXQ7CisJCQlwdHJkaWZmX3QJbnVt X2VsZW1lbnRzID0gZW5kX29mZnNldCAtIHN0YXJ0X29mZnNldDsKKworCQkJaWYgKG51bV9lbGVt ZW50cyA+IDEpCisJCQl7CisJCQkJaWYgKGxldmVsIDwgU0laRU9GX0RBVFVNIC0gMSkKKwkJCQl7 CisJCQkJCWlmIChudW1fZWxlbWVudHMgPCBRU09SVF9USFJFU0hPTEQpCisJCQkJCXsKKwkJCQkJ CS8qIHJlc3RvcmUgTk9UIE5VTEwgZm9yIGZhbGxiYWNrIHFzb3J0ICovCisJCQkJCQkvKgorCQkJ CQkJICogV0lQOiBNYXliZSB3ZSBjYW4gaGF2ZSBhIHFzb3J0IHRoYXQgc2tpcHMgdGhlIE5VTEwK KwkJCQkJCSAqIGNvbXBhcmlzb25zLCBjb21wYXJlcyBkaXJlY3RseSBvbiBjb25kX2RhdHVtMSwg YW5kCisJCQkJCQkgKiBvbmx5IHJlc3RvcmVzIGlzbnVsbDEgaWYgd2UgYWN0dWFsbHkgY2FsbCB0 aGUKKwkJCQkJCSAqIHRpZWJyZWFrLgorCQkJCQkJICovCisJCQkJCQlmb3IgKFNvcnRUdXBsZSAq dHVwID0gcGFydGl0aW9uX2JlZ2luOworCQkJCQkJCSB0dXAgPCBwYXJ0aXRpb25fYmVnaW4gKyBu dW1fZWxlbWVudHM7CisJCQkJCQkJIHR1cCsrKQorCQkJCQkJCXR1cC0+aXNudWxsMSA9IGZhbHNl OworCisJCQkJCQlxc29ydF90dXBsZShwYXJ0aXRpb25fYmVnaW4sCisJCQkJCQkJCQludW1fZWxl bWVudHMsCisJCQkJCQkJCQlzdGF0ZS0+YmFzZS5jb21wYXJldHVwLAorCQkJCQkJCQkJc3RhdGUp OworCQkJCQl9CisJCQkJCWVsc2UgaWYgKG51bV9lbGVtZW50cyA8IEFNRVJJQ0FOX0ZMQUdfVEhS RVNIT0xEKQorCQkJCQl7CisJCQkJCQlhbWVyaWNhbl9mbGFnX3NvcnQocGFydGl0aW9uX2JlZ2lu LAorCQkJCQkJCQkJCSAgIHBhcnRpdGlvbl9lbmQsCisJCQkJCQkJCQkJICAgbGV2ZWwgKyAxLAor CQkJCQkJCQkJCSAgIHN0YXRlKTsKKwkJCQkJfQorCQkJCQllbHNlCisJCQkJCXsKKwkJCQkJCXNr YV9ieXRlX3NvcnQocGFydGl0aW9uX2JlZ2luLAorCQkJCQkJCQkJICBwYXJ0aXRpb25fZW5kLAor CQkJCQkJCQkJICBsZXZlbCArIDEsCisJCQkJCQkJCQkgIHN0YXRlKTsKKwkJCQkJfQorCQkJCX0K KwkJCQllbHNlIGlmIChzdGF0ZS0+YmFzZS5vbmx5S2V5ID09IE5VTEwpCisJCQkJeworCQkJCQkv KgorCQkJCQkgKiBGaW5pc2hlZCByYWRpeCBzb3J0IG9uIGFsbCBieXRlcyBvZiBjb25kX2RhdHVt MQorCQkJCQkgKiAocG9zc2liaWx5IGFiYnJldmlhdGVkKSwgbm93IHFzb3J0IHdpdGggdGllYnJl YWsKKwkJCQkJICogY29tcGFyYXRvci4KKwkJCQkJICovCisKKwkJCQkJLyogZmlyc3QgcmVzdG9y ZSBOT1QgTlVMTCBmb3IgbGF0ZXIgY29tcGFyYXRvcnMgKi8KKwkJCQkJZm9yIChTb3J0VHVwbGUg KnR1cCA9IHBhcnRpdGlvbl9iZWdpbjsKKwkJCQkJCSB0dXAgPCBwYXJ0aXRpb25fYmVnaW4gKyBu dW1fZWxlbWVudHM7CisJCQkJCQkgdHVwKyspCisJCQkJCQl0dXAtPmlzbnVsbDEgPSBmYWxzZTsK KworCQkJCQlxc29ydF90dXBsZShwYXJ0aXRpb25fYmVnaW4sCisJCQkJCQkJCW51bV9lbGVtZW50 cywKKwkJCQkJCQkJc3RhdGUtPmJhc2UuY29tcGFyZXR1cF90aWVicmVhaywKKwkJCQkJCQkJc3Rh dGUpOworCQkJCX0KKwkJCX0KKwkJCXN0YXJ0X29mZnNldCA9IGVuZF9vZmZzZXQ7CisJCQlwYXJ0 aXRpb25fYmVnaW4gPSBwYXJ0aXRpb25fZW5kOworCQl9CisJfQorfQorCiAvKgogICoJCXR1cGxl c29ydF9iZWdpbl94eHgKICAqCkBAIC0yNjYzLDggKzMwNjcsMTkyIEBAIHNvcnRfYm91bmRlZF9o ZWFwKFR1cGxlc29ydHN0YXRlICpzdGF0ZSkKIAlzdGF0ZS0+Ym91bmRVc2VkID0gdHJ1ZTsKIH0K IAorLyogV0lQOiBhbGxvdyB0dXJuaW5nIGNvbW1vbiBwcmVmaXggc2tpcHBpbmcgb2ZmIGZvciB0 ZXN0aW5nICovCisjZGVmaW5lIENPTU1PTl9QUkVGSVgKKworLyoKKyAqIFByZXBhcmUgU29ydFR1 cGxlcyBmb3IgcmFkaXggc29ydCBiZWZvcmUgZGlzcGF0Y2ggdG8gdGhlIGFjdHVhbCBzb3J0Lgor ICovCitzdGF0aWMgdm9pZAorcmFkaXhzb3J0X3R1cGxlKFR1cGxlc29ydHN0YXRlICpzdGF0ZSkK K3sKKwlTb3J0U3VwcG9ydERhdGEgc3N1cCA9IHN0YXRlLT5iYXNlLnNvcnRLZXlzWzBdOworCisJ Ym9vbAkJbnVsbHNfZmlyc3QgPSBzc3VwLnNzdXBfbnVsbHNfZmlyc3Q7CisJU29ydFR1cGxlICAq Zmlyc3QgPSBzdGF0ZS0+bWVtdHVwbGVzOworCVNvcnRUdXBsZSAgKmxhc3QgPSBzdGF0ZS0+bWVt dHVwbGVzICsgc3RhdGUtPm1lbXR1cGNvdW50OworCVNvcnRUdXBsZSAgKm5vdF9udWxsX3N0YXJ0 OworCXNpemVfdAkJZDEsCisJCQkJZDIsCisJCQkJbm90X251bGxfY291bnQ7CisjaWZkZWYgQ09N TU9OX1BSRUZJWAorCURhdHVtCQlmaXJzdF9kYXR1bSA9IDA7CisJRGF0dW0JCWNvbW1vbl91cHBl cl9iaXRzID0gMDsKKyNlbmRpZgorCWludAkJCWNvbW1vbl9wcmVmaXg7CisKKwkvKgorCSAqIFBh cnRpdGlvbiBieSBpc251bGwxLCBzaW5jZSB3ZSBjYW4gb25seSByYWRpeCBzb3J0IG9uIG5vbi1O VUxMCisJICogZWxlbWVudHMuCisJICovCisKKwkvKgorCSAqIEZpbmQgdGhlIGxlZnRtb3N0IE5P VCBOVUxMIHR1cGxlIGlmIE5VTExTIEZJUlNULCBvciBsZWZ0bW9zdCBOVUxMCisJICogZWxlbWVu dCBpZiBOVUxMUyBMQVNULgorCSAqLworCXdoaWxlIChmaXJzdCA8IGxhc3QgJiYgZmlyc3QtPmlz bnVsbDEgPT0gbnVsbHNfZmlyc3QpCisJCWZpcnN0Kys7CisKKwkvKgorCSAqIFhYWCBXZSBtdXN0 IHN0YXJ0ICJsYXN0IiBhZnRlciB0aGUgZmluYWwgdHVwbGUgdG8gbWFpbnRhaW4gdGhlCisJICog aW52YXJpYW50IHRoYXQgaXQgZW5kcyB1cCBvbmUgYWZ0ZXIgdGhlIGZpcnN0IHBhcnRpdGlvbiwg YW5kIHRoZSBmaXJzdAorCSAqIHBhcnRpdGlvbiBtYXkgY29ycmVzcG9uZCB0byB0aGUgZW50aXJl IGFycmF5LiBJZiAiZmlyc3QiIGlzbid0IGdvdHRlbgorCSAqIHRoaXMgZmFyLCB3ZSBuZWVkIHRv IHByZS1kZWNyZW1lbnQgImxhc3QiIGJlZm9yZSBiZWdpbm5pbmcgaXRzIGxvb3AuCisJICovCisJ aWYgKGZpcnN0IDwgbGFzdCkKKwkJbGFzdC0tOworCisJLyoKKwkgKiBGaW5kIHRoZSByaWdodG1v c3QgTlVMTCB0dXBsZSBpZiBOVUxMUyBGSVJTVCwgb3IgcmlnaHRtb3N0IE5PVCBOVUxMCisJICog dHVwbGUgaWYgTlVMTFMgTEFTVC4KKwkgKi8KKwl3aGlsZSAoZmlyc3QgPCBsYXN0ICYmIGxhc3Qt PmlzbnVsbDEgIT0gbnVsbHNfZmlyc3QpCisJCWxhc3QtLTsKKworCS8qIHN3YXAgcGFpcnMgb2Yg dHVwbGVzIHRoYXQgYXJlIGluIHRoZSB3cm9uZyBvcmRlciAqLworCXdoaWxlIChmaXJzdCA8IGxh c3QpCisJeworCQlzd2FwKGZpcnN0LCBsYXN0KTsKKwkJd2hpbGUgKGZpcnN0IDwgbGFzdCAmJiBm aXJzdC0+aXNudWxsMSA9PSBudWxsc19maXJzdCkKKwkJCWZpcnN0Kys7CisJCXdoaWxlIChmaXJz dCA8IGxhc3QgJiYgbGFzdC0+aXNudWxsMSAhPSBudWxsc19maXJzdCkKKwkJCWxhc3QtLTsKKwl9 CisKKwlkMSA9IGxhc3QgLSBzdGF0ZS0+bWVtdHVwbGVzOworCWQyID0gc3RhdGUtPm1lbXR1cGNv dW50IC0gZDE7CisKKwlBc3NlcnQobGFzdCA9IGZpcnN0KTsKKwlBc3NlcnQobGFzdCArIGQyID09 IHN0YXRlLT5tZW10dXBsZXMgKyBzdGF0ZS0+bWVtdHVwY291bnQpOworCWZvciAoU29ydFR1cGxl ICpwbSA9IHN0YXRlLT5tZW10dXBsZXM7CisJCSBwbSA8IHN0YXRlLT5tZW10dXBsZXMgKyBkMTsK KwkJIHBtKyspCisJCUFzc2VydChwbS0+aXNudWxsMSA9PSBudWxsc19maXJzdCk7CisJZm9yIChT b3J0VHVwbGUgKnBtID0gbGFzdDsKKwkJIHBtIDwgbGFzdCArIGQyOworCQkgcG0rKykKKwkJQXNz ZXJ0KHBtLT5pc251bGwxICE9IG51bGxzX2ZpcnN0KTsKKworCS8qCisJICogU29ydCBudWxsIHBh cnRpdGlvbiB1c2luZyB0aWVicmVhayBjb21wYXJhdG9yLiBYWFggdGhpcyB3aWxsIHJlcGVhdCB0 aGUKKwkgKiBOVUxMIGNoZWNrIGZvciBhYmJyZXZpYXRlZCBrZXlzLgorCSAqLworCWlmIChudWxs c19maXJzdCkKKwl7CisJCXFzb3J0X3R1cGxlKHN0YXRlLT5tZW10dXBsZXMsCisJCQkJCWQxLAor CQkJCQlzdGF0ZS0+YmFzZS5jb21wYXJldHVwX3RpZWJyZWFrLAorCQkJCQlzdGF0ZSk7CisJCW5v dF9udWxsX3N0YXJ0ID0gbGFzdDsKKwkJbm90X251bGxfY291bnQgPSBkMjsKKwl9CisJZWxzZQor CXsKKwkJcXNvcnRfdHVwbGUobGFzdCwKKwkJCQkJZDIsCisJCQkJCXN0YXRlLT5iYXNlLmNvbXBh cmV0dXBfdGllYnJlYWssCisJCQkJCXN0YXRlKTsKKwkJbm90X251bGxfc3RhcnQgPSBzdGF0ZS0+ bWVtdHVwbGVzOworCQlub3RfbnVsbF9jb3VudCA9IGQxOworCX0KKworCS8qCisJICogQ29uZGl0 aW9uIGRhdHVtIHNvIHRoYXQgdW5zaWduZWQgY29tcGFyaXNpb24gaXMgb3JkZXItcHJlc2Vydmlu ZywgYW5kCisJICogY29tcHV0ZSB0aGUgY29tbW9uIHByZWZpeCB0byBza2lwIHVucHJvZHVjdGl2 ZSByZWN1cnNpb24gc3RlcHMuCisJICovCisJZm9yIChTb3J0VHVwbGUgKnR1cCA9IG5vdF9udWxs X3N0YXJ0OworCQkgdHVwIDwgbm90X251bGxfc3RhcnQgKyBub3RfbnVsbF9jb3VudDsKKwkJIHR1 cCsrKQorCXsKKwkJRGF0dW0JCWNvbmRfZGF0dW0xID0gY29uZGl0aW9uX2RhdHVtKHR1cC0+ZGF0 dW0xLCAmc3N1cCk7CisjaWZkZWYgQ09NTU9OX1BSRUZJWAorCQlpZiAodHVwID09IG5vdF9udWxs X3N0YXJ0KQorCQl7CisJCQkvKiBOZWVkIHRvIHN0YXJ0IHdpdGggc29tZSB2YWx1ZSwgbWF5IGFz IHdlbGwgYmUgdGhlIGZpcnN0IG9uZS4gKi8KKwkJCWZpcnN0X2RhdHVtID0gY29uZF9kYXR1bTE7 CisJCX0KKwkJZWxzZQorCQl7CisJCQlEYXR1bQkJdGhpc19jb21tb25fYml0czsKKworCQkJLyog VGhlIGJpdHMgaW4gY29tbW9uIHdpbGwgYmUgemVybyAqLworCQkJdGhpc19jb21tb25fYml0cyA9 IGZpcnN0X2RhdHVtIF4gY29uZF9kYXR1bTE7CisKKwkJCS8qCisJCQkgKiBXZSdyZSByZWFsbHkg b25seSBpbnRlcmVzdGVkIGluIHRoZSBjYXNlIHdoZXJlIHRoZSByaWdodG1vc3QKKwkJCSAqIG9u ZSBiaXQgaXMgZnVydGhlciByaWdodCwgYnV0IHRoaXMgYnJhbmNoIHNob3VsZCBiZSByYXJlIGVu b3VnaAorCQkJICogbm90IHRvIHdhc3RlIGN5Y2xlcyB0cnlpbmcgaGFyZGVyLgorCQkJICovCisJ CQlpZiAodGhpc19jb21tb25fYml0cyA+IGNvbW1vbl91cHBlcl9iaXRzKQorCQkJCWNvbW1vbl91 cHBlcl9iaXRzID0gdGhpc19jb21tb25fYml0czsKKwkJfQorI2VuZGlmCisJCXR1cC0+Y29uZF9k YXR1bTEgPSBjb25kX2RhdHVtMTsKKwl9CisKKwkvKgorCSAqIFRoZSB1cHBlciBiaXRzIGFyZSB6 ZXJvIHdoZXJlIGFsbCB2YWx1ZXMgYXJlIHRoZSBzYW1lLCBpZiBhbnkuIFR1cm4gdGhlCisJICog Ynl0ZSBwb3NpdGlvbiBvZiB0aGUgcmlnaHRtb3N0IG9uZSBiaXQgaW50byB0aGUgYnl0ZSB3aGVy ZSByYWRpeCBzb3J0CisJICogc2hvdWxkIHN0YXJ0IGJ1Y2tldGluZy4gT1ItaW5nIGluIHRoZSBs b3dlc3QgYml0IGd1YXJkcyBhZ2FpbnN0CisJICogdW5kZWZpbmVkIGJlaGF2aW9yIHdpdGhvdXQg Y2hhbmdpbmcgdGhlIHJlc3VsdC4KKwkgKi8KKyNpZmRlZiBDT01NT05fUFJFRklYCisJY29tbW9u X3ByZWZpeCA9IHNpemVvZihEYXR1bSkgLSAxIC0KKwkJKHBnX2xlZnRtb3N0X29uZV9wb3M2NChj b21tb25fdXBwZXJfYml0cyB8IDEpIC8gQklUU19QRVJfQllURSk7CisjZWxzZQorCWNvbW1vbl9w cmVmaXggPSAwOworI2VuZGlmCisJLyogcGVyZm9ybSB0aGUgcmFkaXggc29ydCBvbiB0aGUgbm90 LU5VTEwgcGFydGl0aW9uICovCisJc2thX2J5dGVfc29ydChub3RfbnVsbF9zdGFydCwKKwkJCQkg IG5vdF9udWxsX3N0YXJ0ICsgbm90X251bGxfY291bnQsCisJCQkJICBjb21tb25fcHJlZml4LAor CQkJCSAgc3RhdGUpOworCisJLyoKKwkgKiBSZXN0b3JlIGZpZWxkcyB0aGF0IHdlcmUgb3Zlcndy aXR0ZW4gd2l0aCB0ZW1wb3JhcnkgY29uZGl0aW9uZWQgZGF0dW0xCisJICovCisJZm9yIChTb3J0 VHVwbGUgKnR1cCA9IG5vdF9udWxsX3N0YXJ0OworCQkgdHVwIDwgbm90X251bGxfc3RhcnQgKyBu b3RfbnVsbF9jb3VudDsKKwkJIHR1cCsrKQorCXsKKwkJLyogbmVlZCB0byByZXN0b3JlIE5PVCBO VUxMICovCisJCXR1cC0+aXNudWxsMSA9IGZhbHNlOworCQkvKiBiZSB0aWR5ICovCisJCXR1cC0+ c3JjdGFwZSA9IDA7CisJfQorfQorCisvKiBWZXJpZnkgc29ydCB1c2luZyBzdGFuZGFyZCBjb21w YXJhdG9yLiAqLworc3RhdGljIHZvaWQKK2NoZWNrX3NvcnRlZChUdXBsZXNvcnRzdGF0ZSAqc3Rh dGUpCit7CisjaWZkZWYgVVNFX0FTU0VSVF9DSEVDS0lORworCWZvciAoU29ydFR1cGxlICpwbSA9 IHN0YXRlLT5tZW10dXBsZXMgKyAxOworCQkgcG0gPCBzdGF0ZS0+bWVtdHVwbGVzICsgc3RhdGUt Pm1lbXR1cGNvdW50OworCQkgcG0rKykKKwl7CisjaWYgMAorCQlBc3NlcnQoQ09NUEFSRVRVUChz dGF0ZSwgcG0gLSAxLCBwbSkgPD0gMCk7CisjZWxzZQorCQlpZiAoQ09NUEFSRVRVUChzdGF0ZSwg cG0gLSAxLCBwbSkgPiAwKQorCQkJZWxvZyhFUlJPUiwgIlNPUlQgRkFJTEVEIik7CisjZW5kaWYK Kwl9CisjZW5kaWYKK30KKwogLyoKLSAqIFNvcnQgYWxsIG1lbXR1cGxlcyB1c2luZyBzcGVjaWFs aXplZCBxc29ydCgpIHJvdXRpbmVzLgorICogU29ydCBhbGwgbWVtdHVwbGVzIHVzaW5nIHNwZWNp YWxpemVkIHJvdXRpbmVzLgogICoKICAqIFF1aWNrc29ydCBpcyB1c2VkIGZvciBzbWFsbCBpbi1t ZW1vcnkgc29ydHMsIGFuZCBleHRlcm5hbCBzb3J0IHJ1bnMuCiAgKi8KQEAgLTI2ODEsMjYgKzMy NjksNDMgQEAgdHVwbGVzb3J0X3NvcnRfbWVtdHVwbGVzKFR1cGxlc29ydHN0YXRlICpzdGF0ZSkK IAkJICovCiAJCWlmIChzdGF0ZS0+YmFzZS5oYXZlRGF0dW0xICYmIHN0YXRlLT5iYXNlLnNvcnRL ZXlzKQogCQl7Ci0JCQlpZiAoc3RhdGUtPmJhc2Uuc29ydEtleXNbMF0uY29tcGFyYXRvciA9PSBz c3VwX2RhdHVtX3Vuc2lnbmVkX2NtcCkKLQkJCXsKLQkJCQlxc29ydF90dXBsZV91bnNpZ25lZChz dGF0ZS0+bWVtdHVwbGVzLAotCQkJCQkJCQkJIHN0YXRlLT5tZW10dXBjb3VudCwKLQkJCQkJCQkJ CSBzdGF0ZSk7Ci0JCQkJcmV0dXJuOwotCQkJfQotCQkJZWxzZSBpZiAoc3RhdGUtPmJhc2Uuc29y dEtleXNbMF0uY29tcGFyYXRvciA9PSBzc3VwX2RhdHVtX3NpZ25lZF9jbXApCisJCQlTb3J0U3Vw cG9ydERhdGEgc3N1cCA9IHN0YXRlLT5iYXNlLnNvcnRLZXlzWzBdOworCisJCQlpZiAod2lwX3Jh ZGl4X3NvcnQpCiAJCQl7Ci0JCQkJcXNvcnRfdHVwbGVfc2lnbmVkKHN0YXRlLT5tZW10dXBsZXMs Ci0JCQkJCQkJCSAgIHN0YXRlLT5tZW10dXBjb3VudCwKLQkJCQkJCQkJICAgc3RhdGUpOwotCQkJ CXJldHVybjsKKwkJCQlpZiAoc3RhdGUtPm1lbXR1cGNvdW50ID4gUVNPUlRfVEhSRVNIT0xEICYm CisJCQkJCShzc3VwLmNvbXBhcmF0b3IgPT0gc3N1cF9kYXR1bV91bnNpZ25lZF9jbXAgfHwKKwkJ CQkJIHNzdXAuY29tcGFyYXRvciA9PSBzc3VwX2RhdHVtX3NpZ25lZF9jbXAgfHwKKwkJCQkJIHNz dXAuY29tcGFyYXRvciA9PSBzc3VwX2RhdHVtX2ludDMyX2NtcCkpCisJCQkJeworCQkJCQlyYWRp eHNvcnRfdHVwbGUoc3RhdGUpOworCQkJCQljaGVja19zb3J0ZWQoc3RhdGUpOworCQkJCQlyZXR1 cm47CisJCQkJfQogCQkJfQotCQkJZWxzZSBpZiAoc3RhdGUtPmJhc2Uuc29ydEtleXNbMF0uY29t cGFyYXRvciA9PSBzc3VwX2RhdHVtX2ludDMyX2NtcCkKKwkJCWVsc2UKIAkJCXsKLQkJCQlxc29y dF90dXBsZV9pbnQzMihzdGF0ZS0+bWVtdHVwbGVzLAotCQkJCQkJCQkgIHN0YXRlLT5tZW10dXBj b3VudCwKLQkJCQkJCQkJICBzdGF0ZSk7Ci0JCQkJcmV0dXJuOworCQkJCWlmIChzdGF0ZS0+YmFz ZS5zb3J0S2V5c1swXS5jb21wYXJhdG9yID09IHNzdXBfZGF0dW1fdW5zaWduZWRfY21wKQorCQkJ CXsKKwkJCQkJcXNvcnRfdHVwbGVfdW5zaWduZWQoc3RhdGUtPm1lbXR1cGxlcywKKwkJCQkJCQkJ CQkgc3RhdGUtPm1lbXR1cGNvdW50LAorCQkJCQkJCQkJCSBzdGF0ZSk7CisJCQkJCXJldHVybjsK KwkJCQl9CisJCQkJZWxzZSBpZiAoc3RhdGUtPmJhc2Uuc29ydEtleXNbMF0uY29tcGFyYXRvciA9 PSBzc3VwX2RhdHVtX3NpZ25lZF9jbXApCisJCQkJeworCQkJCQlxc29ydF90dXBsZV9zaWduZWQo c3RhdGUtPm1lbXR1cGxlcywKKwkJCQkJCQkJCSAgIHN0YXRlLT5tZW10dXBjb3VudCwKKwkJCQkJ CQkJCSAgIHN0YXRlKTsKKwkJCQkJcmV0dXJuOworCQkJCX0KKwkJCQllbHNlIGlmIChzdGF0ZS0+ YmFzZS5zb3J0S2V5c1swXS5jb21wYXJhdG9yID09IHNzdXBfZGF0dW1faW50MzJfY21wKQorCQkJ CXsKKwkJCQkJcXNvcnRfdHVwbGVfaW50MzIoc3RhdGUtPm1lbXR1cGxlcywKKwkJCQkJCQkJCSAg c3RhdGUtPm1lbXR1cGNvdW50LAorCQkJCQkJCQkJICBzdGF0ZSk7CisJCQkJCXJldHVybjsKKwkJ CQl9CiAJCQl9CiAJCX0KIApkaWZmIC0tZ2l0IGEvc3JjL2luY2x1ZGUvdXRpbHMvZ3VjLmggYi9z cmMvaW5jbHVkZS91dGlscy9ndWMuaAppbmRleCBmMjFlYzM3ZGE4OS4uYmM2ZjdmYTYwZjMgMTAw NjQ0Ci0tLSBhL3NyYy9pbmNsdWRlL3V0aWxzL2d1Yy5oCisrKyBiL3NyYy9pbmNsdWRlL3V0aWxz L2d1Yy5oCkBAIC0zMjQsNiArMzI0LDcgQEAgZXh0ZXJuIFBHRExMSU1QT1JUIGludCB0Y3BfdXNl cl90aW1lb3V0OwogZXh0ZXJuIFBHRExMSU1QT1JUIGNoYXIgKnJvbGVfc3RyaW5nOwogZXh0ZXJu IFBHRExMSU1QT1JUIGJvb2wgaW5faG90X3N0YW5kYnlfZ3VjOwogZXh0ZXJuIFBHRExMSU1QT1JU IGJvb2wgdHJhY2Vfc29ydDsKK2V4dGVybiBQR0RMTElNUE9SVCBib29sIHdpcF9yYWRpeF9zb3J0 OwogCiAjaWZkZWYgREVCVUdfQk9VTkRFRF9TT1JUCiBleHRlcm4gUEdETExJTVBPUlQgYm9vbCBv cHRpbWl6ZV9ib3VuZGVkX3NvcnQ7CmRpZmYgLS1naXQgYS9zcmMvaW5jbHVkZS91dGlscy90dXBs ZXNvcnQuaCBiL3NyYy9pbmNsdWRlL3V0aWxzL3R1cGxlc29ydC5oCmluZGV4IGVmNzlmMjU5Zjkz Li5iMmVjYmJjOWU1MSAxMDA2NDQKLS0tIGEvc3JjL2luY2x1ZGUvdXRpbHMvdHVwbGVzb3J0LmgK KysrIGIvc3JjL2luY2x1ZGUvdXRpbHMvdHVwbGVzb3J0LmgKQEAgLTE0OSw4ICsxNDksMTYgQEAg dHlwZWRlZiBzdHJ1Y3QKIHsKIAl2b2lkCSAgICp0dXBsZTsJCQkvKiB0aGUgdHVwbGUgaXRzZWxm ICovCiAJRGF0dW0JCWRhdHVtMTsJCQkvKiB2YWx1ZSBvZiBmaXJzdCBrZXkgY29sdW1uICovCi0J Ym9vbAkJaXNudWxsMTsJCS8qIGlzIGZpcnN0IGtleSBjb2x1bW4gTlVMTD8gKi8KLQlpbnQJCQlz cmN0YXBlOwkJLyogc291cmNlIHRhcGUgbnVtYmVyICovCisKKwl1bmlvbgorCXsKKwkJc3RydWN0 CisJCXsKKwkJCWJvb2wJCWlzbnVsbDE7CQkvKiBpcyBmaXJzdCBrZXkgY29sdW1uIE5VTEw/ICov CisJCQlpbnQJCQlzcmN0YXBlOwkJLyogc291cmNlIHRhcGUgbnVtYmVyICovCisJCX07CisJCURh dHVtCQljb25kX2RhdHVtMTsJCS8qIHNvcnQga2V5IGZvciByYWRpeCBzb3J0ICovCisJfTsKIH0g U29ydFR1cGxlOwogCiB0eXBlZGVmIGludCAoKlNvcnRUdXBsZUNvbXBhcmF0b3IpIChjb25zdCBT b3J0VHVwbGUgKmEsIGNvbnN0IFNvcnRUdXBsZSAqYiwKLS0gCjIuNTEuMAoK --000000000000f2a8300642463df4--