MIME-Version: 1.0
References: 
 <CABPTF7XiwbA38OZBj5Y2F-q+fZ=03YFN9iFnb_406F4SfE-f4w@mail.gmail.com>
In-Reply-To: 
 <CABPTF7XiwbA38OZBj5Y2F-q+fZ=03YFN9iFnb_406F4SfE-f4w@mail.gmail.com>
From: Xuneng Zhou <xunengzhou@gmail.com>
Date: Tue, 16 Dec 2025 18:20:24 +0800
Message-ID: 
 <CABPTF7WcZ4_xvPeBh9Ws3_AJ3u67gHdHSAmE5Pp+0pDppY=ZvA@mail.gmail.com>
Subject: Re: Optimize SnapBuild by maintaining committed.xip in sorted order
To: pgsql-hackers <pgsql-hackers@lists.postgresql.org>
Cc: Masahiko Sawada <sawada.mshk@gmail.com>
Content-Type: multipart/mixed; boundary="00000000000028c1c506460f145d"
Archived-At: 
 <https://www.postgresql.org/message-id/CABPTF7WcZ4_xvPeBh9Ws3_AJ3u67gHdHSAmE5Pp%2B0pDppY%3DZvA%40mail.gmail.com>
Precedence: bulk

--00000000000028c1c506460f145d
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi,

On Fri, Nov 7, 2025 at 12:55=E2=80=AFPM Xuneng Zhou <xunengzhou@gmail.com> =
wrote:
>
> Hi hackers,
>
> I'd like to propose an optimization for logical decoding's snapshot build=
ing
> mechanism that eliminates repeated sorting overhead once a replication sl=
ot
> reaches the CONSISTENT state.
>
> 1) Problem
>
> Currently, SnapBuildBuildSnapshot() sorts the entire committed.xip array =
on
> every call using qsort(). Once a logical decoding slot reaches CONSISTENT
> state, snapshots are built frequently=E2=80=94after every catalog-modifyi=
ng transaction
> commit. This repeated O(n log n) sorting becomes a performance bottleneck=
 as
> the committed transaction array grows.
>
> The existing code even has a TODO comment acknowledging this inefficiency=
:
> "TODO: It's unclear whether that reasoning has much merit. Every time we =
add
> something here after becoming consistent will also require distributing a
> snapshot."
>
> 2) Proposed Solution
>
> Maintain sorted order via batch merge on each commit:
>
> 1. Collect all relevant XIDs (including subtransactions) into a batch arr=
ay
> 2. Sort the batch: O(m log m) where m is typically small (1 + nsubxacts)
> 3. Merge into the global array: O(n + m) via reverse in-place merge
>
> While per-commit cost increases from O(m) to O(m log m + n), this is offs=
et by
> eliminating O(n log n) sorts at each snapshot build. Since CONSISTENT sta=
te
> builds snapshots after each catalog-modifying commit, the amortized cost =
is
> significantly lower.
>
> 3) Performance Impact
>
> Expected improvements in CONSISTENT state:
> - Eliminates O(n log n) qsort on every snapshot build
> - Replaces with O(m log m + n) merge per commit
> - For typical cases where m << n and snapshots are frequent, this is a wi=
n
>
>
> The benchmark results for this patch are shown below.
>
> 4) Configuration
>
> shared_buffers =3D '4GB'
> wal_level =3D logical
> max_replication_slots =3D 10
> max_wal_senders =3D 10
> log_min_messages =3D warning
> max_connections =3D 600
> autovacuum =3D off
> checkpoint_timeout =3D 15min
> max_wal_size =3D 4GB
>
>
> 5) Workloads
>
> # Workload 1: DDL - High frequency, small commits
> create_ddl_workload() {
>   local ROOT=3D"$1"
>   cat >"$ROOT/ddl.sql" <<'SQL'
> -- High-frequency small catalog commits
> -- Each commit triggers SnapBuildBuildSnapshot
> DO $$
> DECLARE
>   tbl text :=3D format('temp_%s_%s',
>                      current_setting('application_name', true),
>                      floor(random()*1e9)::int);
> BEGIN
>   EXECUTE format('CREATE TEMP TABLE %I (id int, data text) ON COMMIT
> DROP', tbl);
>   EXECUTE format('INSERT INTO %I VALUES (1, ''x'')', tbl);
>   EXECUTE format('SELECT * FROM %I', tbl);
> END$$;
> SQL
> }
>
> # Workload 2: MIXED - mix of DDL and DML, 50%-50%
> create_mixed_workload() {
>   local ROOT=3D"$1"
>   cat >"$ROOT/mixed_ddl.sql" <<'SQL'
> -- DDL workload (catalog changes)
> DO $$
> DECLARE
>   tbl text :=3D format('t_%s_%s',
>                      current_setting('application_name', true),
>                      floor(random()*1e9)::int);
> BEGIN
>   EXECUTE format('CREATE TABLE %I (id int, data text) ON COMMIT DROP', tb=
l);
>   EXECUTE format('INSERT INTO %I VALUES (1, ''x'')', tbl);
> END$$;
>
> SQL
>   cat >"$ROOT/mixed_dml.sql" <<'SQL'
> -- DML workload (no catalog changes)
> INSERT INTO app_data (id, data)
> VALUES (floor(random()*1e6)::int, repeat('x', 100))
> ON CONFLICT (id) DO UPDATE SET data =3D repeat('y', 100);
> SQL
> }
>
> # Workload 3: CONTROL - Pure DML, no catalog changes
> create_control_workload() {
>   local ROOT=3D"$1"
>   cat >"$ROOT/control.sql" <<'SQL'
>
> -- Pure DML, no catalog changes
> -- Should show no difference between baseline and patched
> INSERT INTO control_data (id, data)
> VALUES (floor(random()*1e6)::int, repeat('x', 100))
> ON CONFLICT (id) DO UPDATE SET data =3D repeat('y', 100);
> SQL
> }
>
>
> 6) Test strategy
>
> Clients: 100 concurrent connections per workload
> Duration: 40 seconds per run
> Repetitions: 1 run per workload type
> Replication:  Logical replication slot using `test_decoding` plugin
> with `EXPORT_SNAPSHOT=3Dtrue`
>
> Workload Types:
> 1. DDL - Pure catalog churn (temp table create/drop)
> 2. Mixed- 50% DDL + 50% DML (workload)
> 3. Control - Pure DML (no catalog changes)
>
> Measurement:
> - Metrics captured from pg_stat_replication_slots before/after each run
> - Primary metrics: total_txns (transactions decoded) and total_bytes
> (data volume)
> - Compared baseline (vanilla PostgreSQL) vs patched (sorted
> committed.xip optimization)
>
>
> 7) Performance results
>
> DDL Workload: +235% Decoder Improvement
> Decoder throughput:  713.76 =E2=86=92 2396.52 txns/sec  (+235%)
> Throughput (MB/s):   672.67 =E2=86=92 1747.22 MB/s     (+159%)
> Decode efficiency:   9.46% =E2=86=92 33.29%             (+23.83 points)
>
> Mixed Workload: No Change
> Decoder throughput:  2751.10 =E2=86=92 2730.00 txns/sec  (0%)
> Decode efficiency:   40.47% =E2=86=92 40.47%             (unchanged)
>
> We can see that the qsort overhead in SnapBuild has been eliminated in
> the flamegraphs in the mixed workload. However, the performance
> improvement was not observed as in the DDL workload. My guess is that,
> for DML workloads, ReorderBufferApplyChange has become the new
> hotspot.
>
> DML Workload: No Change
> Decoder throughput:  3062.57 =E2=86=92 3066.37 txns/sec  (0%)
> Decode efficiency:   49.97% =E2=86=92 49.97%             (unchanged)
>
> =3D=3D=3D Workload: ddl =3D=3D=3D
> Client commits/sec:
>   Baseline:  7545.76 commits/sec
>   Patched:   7198.21 commits/sec
>
> Decoder throughput (from pg_stat_replication_slots):
>   Baseline:  713.76 txns/sec  (672.67 MB/s)
>   Patched:   2396.52 txns/sec  (1747.22 MB/s)
>
> Transaction efficiency (decoded vs committed):
>   Baseline:  309376 committed  =E2=86=92  29264 decoded  (9.46%)
>   Patched:   302325 committed  =E2=86=92  100654 decoded  (33.29%)
>
> Total decoded (all reps):
>   Baseline:  29264 txns  (27579.53 MB)
>   Patched:   100654 txns  (73383.10 MB)
>
>   Decoder improvement: +235.00% (txns/sec)
>   Decoder improvement: +159.00% (MB/s)
>   Efficiency improvement: +23.83% points (more transactions decoded
> per committed)
>
> =3D=3D=3D Workload: mixed =3D=3D=3D
> Client commits/sec:
>   Baseline:  6797.50 commits/sec
>   Patched:   6745.26 commits/sec
>
> Decoder throughput (from pg_stat_replication_slots):
>   Baseline:  2751.10 txns/sec  (210.35 MB/s)
>   Patched:   2730.00 txns/sec  (205.64 MB/s)
>
> Transaction efficiency (decoded vs committed):
>   Baseline:  285495 committed  =E2=86=92  115546 decoded  (40.47%)
>   Patched:   283301 committed  =E2=86=92  114660 decoded  (40.47%)
>
> Total decoded (all reps):
>   Baseline:  115546 txns  (8834.71 MB)
>   Patched:   114660 txns  (8636.96 MB)
>
>   =E2=89=88  Decoder unchanged: 0.00% (txns/sec)
>
> =3D=3D=3D Workload: DML =3D=3D=3D
> Client commits/sec:
>   Baseline:  6129.24 commits/sec
>   Patched:   6136.93 commits/sec
>
> Decoder throughput (from pg_stat_replication_slots):
>   Baseline:  3062.57 txns/sec  (0.26 MB/s)
>   Patched:   3066.37 txns/sec  (0.26 MB/s)
>
> Transaction efficiency (decoded vs committed):
>   Baseline:  257428 committed  =E2=86=92  128628 decoded  (49.97%)
>   Patched:   251614 committed  =E2=86=92  125721 decoded  (49.97%)
>
> Total decoded (all reps):
>   Baseline:  128628 txns  (10.98 MB)
>   Patched:   125721 txns  (10.69 MB)
>
>   =E2=89=88  Decoder unchanged: 0.00% (txns/sec)
>
> 8) Potential regression
>
> The potential regression point could be before the slot reaches the
> CONSISTENT state, particularly when building_full_snapshot is set to
> true. In this phase, all transactions including those that don=E2=80=99t
> modify the catalog =E2=80=94 must be added to the committed.xip array. Th=
ese
> XIDs don=E2=80=99t require later snapshot builds or sorting, so the
> batch-insert logic increases the per-insert cost from O(1) to O(m + n)
> without providing a direct benefit.
>
> However, the impact of this regression could be limited. The system
> remains in the pre-CONSISTENT phase only briefly during initial
> snapshot building, and the building_full_snapshot =3D true case is rare,
> mainly used when creating replication slots with the EXPORT_SNAPSHOT
> option.
>
> Once the slot becomes CONSISTENT, only catalog-modifying transactions
> are tracked in committed.xip, and the patch reduces overall
> snapshot-building overhead by eliminating repeated full-array sorts.
>
> We could also adopt a two-phase approach =E2=80=94 keeping the current
> behavior before reaching the CONSISTENT state and maintaining a sorted
> array only after that point. This would preserve the performance
> benefits while avoiding potential regressions. However, it would
> introduce additional complexity and potential risks in handling the
> state transitions.
>
> if (builder->state < SNAPBUILD_CONSISTENT)
> {
> /* ensure that only commits after this are getting replayed */
> if (builder->start_decoding_at <=3D lsn)
> builder->start_decoding_at =3D lsn + 1;
>
> /*
> * If building an exportable snapshot, force xid to be tracked, even
> * if the transaction didn't modify the catalog.
> */
> if (builder->building_full_snapshot)
> {
> needs_timetravel =3D true;
> }
> }

After some consideration, a two-phase sorting strategy seems feasible
to implement in a relatively straightforward manner. So it's done in
v2. I also plan to run benchmarks to evaluate potential regressions of
the original =E2=80=9Csort-at-all-stages=E2=80=9D approach of v1.

> 9) Additional benefit
> With this patch applied, we can optimize the SnapBuildPurgeOlderTxn to us=
e
> two binary searchs rather than interating and copying to find the interva=
l
> to keep in the sorted commited.xip array. [1]
>
> Feedbacks welcomed.
>
> [1] https://www.postgresql.org/message-id/flat/CABPTF7V9gcpTLrOY0fG4Yonto=
HjVg8YrbmiH4XB_5PT6K56xhg%40mail.gmail.com

V2 fixes several issues in v1, including a potential memory leak, type
inconsistencies, and applies pgindent to the files.

--
Best,
Xuneng

--00000000000028c1c506460f145d
Content-Type: application/octet-stream;
	name="v2-0001-Optimize-SnapBuild-by-maintaining-committed.xip-i.patch"
Content-Disposition: attachment;
	filename="v2-0001-Optimize-SnapBuild-by-maintaining-committed.xip-i.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_mj8fiiwc0>
X-Attachment-Id: f_mj8fiiwc0

RnJvbSAxYTU0M2ZjMTFlOTgxNzEyMDQ0ZDU3NzQ1OGNhOGI1MzMwMGU1MjBkIE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiBhbHRlcmVnbzY1NSA8ODI0NjYyNTI2QHFxLmNvbT4KRGF0ZTog
VHVlLCAxNiBEZWMgMjAyNSAxNToxNToxNCArMDgwMApTdWJqZWN0OiBbUEFUQ0ggdjIgMS8yXSBP
cHRpbWl6ZSBTbmFwQnVpbGQgYnkgbWFpbnRhaW5pbmcgY29tbWl0dGVkLnhpcCBpbgogc29ydGVk
IG9yZGVyCgpNYWludGFpbiBjb21taXR0ZWQueGlwIGluIHhpZENvbXBhcmF0b3Igb3JkZXIgdXNp
bmcgYSB0d28tcGhhc2UgYXBwcm9hY2gKdGhhdCBiYWxhbmNlcyBwZXJmb3JtYW5jZSBkdXJpbmcg
c2xvdCBpbml0aWFsaXphdGlvbiB3aXRoIGVmZmljaWVuY3kgZHVyaW5nCnN0ZWFkeS1zdGF0ZSBk
ZWNvZGluZzoKClByZS1DT05TSVNURU5UIHBoYXNlOgotIFVzZSBmYXN0IE8oMSkgYXBwZW5kIGZv
ciB1bnNvcnRlZCBYSURzCi0gU29ydCBvbmNlIGF0IHRyYW5zaXRpb24gdG8gQ09OU0lTVEVOVCBz
dGF0ZQotIEF2b2lkcyBtZXJnZSBvdmVyaGVhZCBkdXJpbmcgaW5pdGlhbCBzbmFwc2hvdCBidWls
ZGluZwoKUG9zdC1DT05TSVNURU5UIHBoYXNlOgotIFVzZSBwZXItY29tbWl0IGJhdGNoIGluc2Vy
dGlvbiB3aXRoIHNvcnRlZCBtZXJnZQotIENvbGxlY3QgYWxsIHJlbGV2YW50IFhJRHMgZm9yIGVh
Y2ggY29tbWl0Ci0gU29ydCB0aGUgYmF0Y2ggb25jZTogTyhtIGxvZyBtKQotIFJldmVyc2UtbWVy
Z2UgaW50byB0aGUgZ2xvYmFsIGFycmF5OiBPKE4gKyBtKQoKV2l0aCB0aGlzIGNoYW5nZSwgc25h
cHNob3QgYnVpbGRzIGNhbiBza2lwIHRoZSBxc29ydCgpIHN0ZXAgYW5kIHNpbXBseQptZW1jcHkg
dGhlIHNvcnRlZCBhcnJheS4gV2hpbGUgcGVyLWNvbW1pdCB3b3JrIGluY3JlYXNlcyBmcm9tIE8o
bSkgKHBsYWluCmFwcGVuZCkgdG8gTyhtIGxvZyBtICsgTikgKHNvcnQtYW5kLW1lcmdlKSBhZnRl
ciBDT05TSVNURU5ULCBlbGltaW5hdGluZwpyZXBlYXRlZCBPKE4gbG9nIE4pIHNvcnRzIGF0IGVh
Y2ggc25hcHNob3QgYnVpbGQgc2lnbmlmaWNhbnRseSByZWR1Y2VzCm92ZXJhbGwgc3RlYWR5LXN0
YXRlIGNvc3Qgb25jZSBDT05TSVNURU5UIGlzIHJlYWNoZWQgYW5kIHNuYXBzaG90cyBhcmUKYnVp
bHQgZnJlcXVlbnRseS4KLS0tCiBzcmMvYmFja2VuZC9yZXBsaWNhdGlvbi9sb2dpY2FsL3NuYXBi
dWlsZC5jICB8IDE1MCArKysrKysrKysrKysrKysrKy0tCiBzcmMvaW5jbHVkZS9yZXBsaWNhdGlv
bi9zbmFwYnVpbGRfaW50ZXJuYWwuaCB8ICAxMiArLQogMiBmaWxlcyBjaGFuZ2VkLCAxMzcgaW5z
ZXJ0aW9ucygrKSwgMjUgZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2JhY2tlbmQvcmVw
bGljYXRpb24vbG9naWNhbC9zbmFwYnVpbGQuYyBiL3NyYy9iYWNrZW5kL3JlcGxpY2F0aW9uL2xv
Z2ljYWwvc25hcGJ1aWxkLmMKaW5kZXggZDZhYjFlMDE3ZWIuLjIwMzFlZjkxMWJmIDEwMDY0NAot
LS0gYS9zcmMvYmFja2VuZC9yZXBsaWNhdGlvbi9sb2dpY2FsL3NuYXBidWlsZC5jCisrKyBiL3Ny
Yy9iYWNrZW5kL3JlcGxpY2F0aW9uL2xvZ2ljYWwvc25hcGJ1aWxkLmMKQEAgLTQwNyw4ICs0MDcs
MTEgQEAgU25hcEJ1aWxkQnVpbGRTbmFwc2hvdChTbmFwQnVpbGQgKmJ1aWxkZXIpCiAJCSAgIGJ1
aWxkZXItPmNvbW1pdHRlZC54aXAsCiAJCSAgIGJ1aWxkZXItPmNvbW1pdHRlZC54Y250ICogc2l6
ZW9mKFRyYW5zYWN0aW9uSWQpKTsKIAotCS8qIHNvcnQgc28gd2UgY2FuIGJzZWFyY2goKSAqLwot
CXFzb3J0KHNuYXBzaG90LT54aXAsIHNuYXBzaG90LT54Y250LCBzaXplb2YoVHJhbnNhY3Rpb25J
ZCksIHhpZENvbXBhcmF0b3IpOworI2lmZGVmIFVTRV9BU1NFUlRfQ0hFQ0tJTkcKKwkvKiBWZXJp
ZnkgYXJyYXkgaXMgc3RyaWN0bHkgc29ydGVkICovCisJZm9yIChpbnQgaSA9IDE7IGkgPCBzbmFw
c2hvdC0+eGNudDsgaSsrKQorCQlBc3NlcnQoc25hcHNob3QtPnhpcFtpIC0gMV0gPCBzbmFwc2hv
dC0+eGlwW2ldKTsKKyNlbmRpZgogCiAJLyoKIAkgKiBJbml0aWFsbHksIHN1YnhpcCBpcyBlbXB0
eSwgaS5lLiBpdCdzIGEgc25hcHNob3QgdG8gYmUgdXNlZCBieQpAQCAtODIyLDE3ICs4MjUsMzMg
QEAgU25hcEJ1aWxkRGlzdHJpYnV0ZVNuYXBzaG90QW5kSW52YWwoU25hcEJ1aWxkICpidWlsZGVy
LCBYTG9nUmVjUHRyIGxzbiwgVHJhbnNhY3QKIH0KIAogLyoKLSAqIEtlZXAgdHJhY2sgb2YgYSBu
ZXcgY2F0YWxvZyBjaGFuZ2luZyB0cmFuc2FjdGlvbiB0aGF0IGhhcyBjb21taXR0ZWQuCisgKiBL
ZWVwIHRyYWNrIG9mIG5ldyBjYXRhbG9nIGNoYW5naW5nIHRyYW5zYWN0aW9ucyB0aGF0IGhhdmUg
Y29tbWl0dGVkLgorICoKKyAqIEJlZm9yZSByZWFjaGluZyBDT05TSVNURU5UIHN0YXRlLCB3ZSB1
c2UgZmFzdCBPKDEpIGFwcGVuZCBzaW5jZSB0aGUgYXJyYXkKKyAqIGRvZXNuJ3QgbmVlZCB0byBi
ZSBzb3J0ZWQgeWV0LiAgQWZ0ZXIgQ09OU0lTVEVOVCwgd2UgbWFpbnRhaW4gc29ydGVkIG9yZGVy
CisgKiB1c2luZyBhIG1lcmdlIGFwcHJvYWNoIHRvIGF2b2lkIHJlcGVhdGVkIGZ1bGwtYXJyYXkg
c29ydHMgYXQgc25hcHNob3QgYnVpbGQuCiAgKi8KIHN0YXRpYyB2b2lkCi1TbmFwQnVpbGRBZGRD
b21taXR0ZWRUeG4oU25hcEJ1aWxkICpidWlsZGVyLCBUcmFuc2FjdGlvbklkIHhpZCkKK1NuYXBC
dWlsZEFkZENvbW1pdHRlZFR4bnMoU25hcEJ1aWxkICpidWlsZGVyLAorCQkJCQkJICBjb25zdCBU
cmFuc2FjdGlvbklkICpiYXRjaF94aWRzLAorCQkJCQkJICBpbnQgYmF0Y2hfY250KQogewotCUFz
c2VydChUcmFuc2FjdGlvbklkSXNWYWxpZCh4aWQpKTsKKwlUcmFuc2FjdGlvbklkICpjb21taXR0
ZWRfeGlkczsKKwlzaXplX3QJCW9sZF94Y250OworCisJb2xkX3hjbnQgPSBidWlsZGVyLT5jb21t
aXR0ZWQueGNudDsKIAotCWlmIChidWlsZGVyLT5jb21taXR0ZWQueGNudCA9PSBidWlsZGVyLT5j
b21taXR0ZWQueGNudF9zcGFjZSkKKwkvKiBFbnN1cmUgd2UgaGF2ZSBzcGFjZSBmb3IgYWxsIGVs
ZW1lbnRzICovCisJaWYgKG9sZF94Y250ICsgYmF0Y2hfY250ID4gYnVpbGRlci0+Y29tbWl0dGVk
LnhjbnRfc3BhY2UpCiAJewogCQlidWlsZGVyLT5jb21taXR0ZWQueGNudF9zcGFjZSA9IGJ1aWxk
ZXItPmNvbW1pdHRlZC54Y250X3NwYWNlICogMiArIDE7CiAKKwkJLyoKKwkJICogUmVwZWF0IGlm
IHdlIG5lZWQgbW9yZSB0aGFuIDJ4IGN1cnJlbnQgc3BhY2UuCisJCSAqLworCQl3aGlsZSAob2xk
X3hjbnQgKyBiYXRjaF9jbnQgPiBidWlsZGVyLT5jb21taXR0ZWQueGNudF9zcGFjZSkKKwkJCWJ1
aWxkZXItPmNvbW1pdHRlZC54Y250X3NwYWNlID0gYnVpbGRlci0+Y29tbWl0dGVkLnhjbnRfc3Bh
Y2UgKiAyICsgMTsKKwogCQllbG9nKERFQlVHMSwgImluY3JlYXNpbmcgc3BhY2UgZm9yIGNvbW1p
dHRlZCB0cmFuc2FjdGlvbnMgdG8gJXUiLAogCQkJICh1aW50MzIpIGJ1aWxkZXItPmNvbW1pdHRl
ZC54Y250X3NwYWNlKTsKIApAQCAtODQwLDEyICs4NTksNTcgQEAgU25hcEJ1aWxkQWRkQ29tbWl0
dGVkVHhuKFNuYXBCdWlsZCAqYnVpbGRlciwgVHJhbnNhY3Rpb25JZCB4aWQpCiAJCQkJCQkJCQkJ
ICBidWlsZGVyLT5jb21taXR0ZWQueGNudF9zcGFjZSAqIHNpemVvZihUcmFuc2FjdGlvbklkKSk7
CiAJfQogCisJY29tbWl0dGVkX3hpZHMgPSBidWlsZGVyLT5jb21taXR0ZWQueGlwOworCiAJLyoK
LQkgKiBUT0RPOiBJdCBtaWdodCBtYWtlIHNlbnNlIHRvIGtlZXAgdGhlIGFycmF5IHNvcnRlZCBo
ZXJlIGluc3RlYWQgb2YKLQkgKiBkb2luZyBpdCBldmVyeSB0aW1lIHdlIGJ1aWxkIGEgbmV3IHNu
YXBzaG90LiBPbiB0aGUgb3RoZXIgaGFuZCB0aGlzCi0JICogZ2V0cyBjYWxsZWQgcmVwZWF0ZWRs
eSB3aGVuIGEgdHJhbnNhY3Rpb24gd2l0aCBzdWJ0cmFuc2FjdGlvbnMgY29tbWl0cy4KKwkgKiBC
ZWZvcmUgQ09OU0lTVEVOVCBzdGF0ZSwganVzdCBhcHBlbmQgdW5zb3J0ZWQgZm9yIE8oMSkgcGVy
Zm9ybWFuY2UuIFRoZQorCSAqIGFycmF5IHdpbGwgYmUgc29ydGVkIG9uY2Ugd2hlbiB0cmFuc2l0
aW9uaW5nIHRvIENPTlNJU1RFTlQuCiAJICovCi0JYnVpbGRlci0+Y29tbWl0dGVkLnhpcFtidWls
ZGVyLT5jb21taXR0ZWQueGNudCsrXSA9IHhpZDsKKwlpZiAoYnVpbGRlci0+c3RhdGUgPCBTTkFQ
QlVJTERfQ09OU0lTVEVOVCkKKwl7CisJCWZvciAoaW50IGkgPSAwOyBpIDwgYmF0Y2hfY250OyBp
KyspCisJCXsKKwkJCUFzc2VydChUcmFuc2FjdGlvbklkSXNWYWxpZChiYXRjaF94aWRzW2ldKSk7
CisJCQljb21taXR0ZWRfeGlkc1tvbGRfeGNudCsrXSA9IGJhdGNoX3hpZHNbaV07CisJCX0KKwkJ
YnVpbGRlci0+Y29tbWl0dGVkLnhjbnQgPSBvbGRfeGNudDsKKwl9CisJZWxzZQorCXsKKwkJLyoK
KwkJICogQWZ0ZXIgQ09OU0lTVEVOVCwgbWFpbnRhaW4gc29ydGVkIG9yZGVyIHZpYSBtZXJnZS4g
IE1lcmdlIGZyb20gdGhlCisJCSAqIGVuZCB0byBhdm9pZCBvdmVyd3JpdGluZyB1bnJlYWQgZGF0
YS4KKwkJICovCisJCWludAkJCW9sZF9pZHggPSBvbGRfeGNudCAtIDE7CisJCWludAkJCWJhdGNo
X2lkeCA9IGJhdGNoX2NudCAtIDE7CisJCWludAkJCXdyaXRlX2lkeCA9IG9sZF94Y250ICsgYmF0
Y2hfY250IC0gMTsKKworCQl3aGlsZSAob2xkX2lkeCA+PSAwICYmIGJhdGNoX2lkeCA+PSAwKQor
CQl7CisJCQlBc3NlcnQoVHJhbnNhY3Rpb25JZElzVmFsaWQoYmF0Y2hfeGlkc1tiYXRjaF9pZHhd
KSk7CisKKwkJCWlmIChjb21taXR0ZWRfeGlkc1tvbGRfaWR4XSA+IGJhdGNoX3hpZHNbYmF0Y2hf
aWR4XSkKKwkJCXsKKwkJCQljb21taXR0ZWRfeGlkc1t3cml0ZV9pZHgtLV0gPSBjb21taXR0ZWRf
eGlkc1tvbGRfaWR4LS1dOworCQkJfQorCQkJZWxzZQorCQkJeworCQkJCS8qIER1cGxpY2F0ZXMg
c2hvdWxkIG5ldmVyIG9jY3VyICovCisJCQkJQXNzZXJ0KGNvbW1pdHRlZF94aWRzW29sZF9pZHhd
ICE9IGJhdGNoX3hpZHNbYmF0Y2hfaWR4XSk7CisJCQkJY29tbWl0dGVkX3hpZHNbd3JpdGVfaWR4
LS1dID0gYmF0Y2hfeGlkc1tiYXRjaF9pZHgtLV07CisJCQl9CisJCX0KKworCQkvKiBDb3B5IGFu
eSByZW1haW5pbmcgYmF0Y2ggZWxlbWVudHMgKi8KKwkJd2hpbGUgKGJhdGNoX2lkeCA+PSAwKQor
CQl7CisJCQlBc3NlcnQoVHJhbnNhY3Rpb25JZElzVmFsaWQoYmF0Y2hfeGlkc1tiYXRjaF9pZHhd
KSk7CisJCQljb21taXR0ZWRfeGlkc1t3cml0ZV9pZHgtLV0gPSBiYXRjaF94aWRzW2JhdGNoX2lk
eC0tXTsKKwkJfQorCisJCS8qIE9sZCBlbGVtZW50cyB0aGF0IHdlcmVuJ3QgbW92ZWQgYXJlIGFs
cmVhZHkgaW4gY29ycmVjdCBwb3NpdGlvbiAqLworCQlidWlsZGVyLT5jb21taXR0ZWQueGNudCA9
IG9sZF94Y250ICsgYmF0Y2hfY250OworCX0KIH0KIAogLyoKQEAgLTk0Nyw2ICsxMDExLDEzIEBA
IFNuYXBCdWlsZENvbW1pdFR4bihTbmFwQnVpbGQgKmJ1aWxkZXIsIFhMb2dSZWNQdHIgbHNuLCBU
cmFuc2FjdGlvbklkIHhpZCwKIAogCVRyYW5zYWN0aW9uSWQgeG1heCA9IHhpZDsKIAorCS8qCisJ
ICogQ29sbGVjdCBYSURzIHRoYXQgbmVlZCB0cmFja2luZyBpbnRvIGEgYmF0Y2guICBXZSdsbCBz
b3J0IGFuZCBtZXJnZQorCSAqIHRoZW0gaW50byBjb21taXR0ZWQueGlwIGluIG9uZSBwYXNzIGF0
IHRoZSBlbmQuCisJICovCisJVHJhbnNhY3Rpb25JZCAqYmF0Y2hfeGlkcyA9IE5VTEw7CisJaW50
CQkJYmF0Y2hfY250ID0gMDsKKwogCS8qCiAJICogVHJhbnNhY3Rpb25zIHByZWNlZGluZyBCVUlM
RElOR19TTkFQU0hPVCB3aWxsIG5laXRoZXIgYmUgZGVjb2RlZCwgbm9yCiAJICogd2lsbCB0aGV5
IGJlIHBhcnQgb2YgYSBzbmFwc2hvdC4gIFNvIHdlIGRvbid0IG5lZWQgdG8gcmVjb3JkIGFueXRo
aW5nLgpAQCAtOTc3LDYgKzEwNDgsMTIgQEAgU25hcEJ1aWxkQ29tbWl0VHhuKFNuYXBCdWlsZCAq
YnVpbGRlciwgWExvZ1JlY1B0ciBsc24sIFRyYW5zYWN0aW9uSWQgeGlkLAogCQl9CiAJfQogCisJ
aWYgKG5zdWJ4YWN0cyA+IDAgfHwgYnVpbGRlci0+YnVpbGRpbmdfZnVsbF9zbmFwc2hvdCB8fAor
CQlTbmFwQnVpbGRYaWRIYXNDYXRhbG9nQ2hhbmdlcyhidWlsZGVyLCB4aWQsIHhpbmZvKSkKKwl7
CisJCWJhdGNoX3hpZHMgPSBwYWxsb2MoKG5zdWJ4YWN0cyArIDEpICogc2l6ZW9mKFRyYW5zYWN0
aW9uSWQpKTsKKwl9CisKIAlmb3IgKG54YWN0ID0gMDsgbnhhY3QgPCBuc3VieGFjdHM7IG54YWN0
KyspCiAJewogCQlUcmFuc2FjdGlvbklkIHN1YnhpZCA9IHN1YnhhY3RzW254YWN0XTsKQEAgLTk5
Myw3ICsxMDcwLDcgQEAgU25hcEJ1aWxkQ29tbWl0VHhuKFNuYXBCdWlsZCAqYnVpbGRlciwgWExv
Z1JlY1B0ciBsc24sIFRyYW5zYWN0aW9uSWQgeGlkLAogCQkJZWxvZyhERUJVRzEsICJmb3VuZCBz
dWJ0cmFuc2FjdGlvbiAldToldSB3aXRoIGNhdGFsb2cgY2hhbmdlcyIsCiAJCQkJIHhpZCwgc3Vi
eGlkKTsKIAotCQkJU25hcEJ1aWxkQWRkQ29tbWl0dGVkVHhuKGJ1aWxkZXIsIHN1YnhpZCk7CisJ
CQliYXRjaF94aWRzW2JhdGNoX2NudCsrXSA9IHN1YnhpZDsKIAogCQkJaWYgKE5vcm1hbFRyYW5z
YWN0aW9uSWRGb2xsb3dzKHN1YnhpZCwgeG1heCkpCiAJCQkJeG1heCA9IHN1YnhpZDsKQEAgLTEw
MDcsNyArMTA4NCw3IEBAIFNuYXBCdWlsZENvbW1pdFR4bihTbmFwQnVpbGQgKmJ1aWxkZXIsIFhM
b2dSZWNQdHIgbHNuLCBUcmFuc2FjdGlvbklkIHhpZCwKIAkJICovCiAJCWVsc2UgaWYgKG5lZWRz
X3RpbWV0cmF2ZWwpCiAJCXsKLQkJCVNuYXBCdWlsZEFkZENvbW1pdHRlZFR4bihidWlsZGVyLCBz
dWJ4aWQpOworCQkJYmF0Y2hfeGlkc1tiYXRjaF9jbnQrK10gPSBzdWJ4aWQ7CiAJCQlpZiAoTm9y
bWFsVHJhbnNhY3Rpb25JZEZvbGxvd3Moc3VieGlkLCB4bWF4KSkKIAkJCQl4bWF4ID0gc3VieGlk
OwogCQl9CkBAIC0xMDIwLDcgKzEwOTcsNyBAQCBTbmFwQnVpbGRDb21taXRUeG4oU25hcEJ1aWxk
ICpidWlsZGVyLCBYTG9nUmVjUHRyIGxzbiwgVHJhbnNhY3Rpb25JZCB4aWQsCiAJCQkgeGlkKTsK
IAkJbmVlZHNfc25hcHNob3QgPSB0cnVlOwogCQluZWVkc190aW1ldHJhdmVsID0gdHJ1ZTsKLQkJ
U25hcEJ1aWxkQWRkQ29tbWl0dGVkVHhuKGJ1aWxkZXIsIHhpZCk7CisJCWJhdGNoX3hpZHNbYmF0
Y2hfY250KytdID0geGlkOwogCX0KIAllbHNlIGlmIChzdWJfbmVlZHNfdGltZXRyYXZlbCkKIAl7
CkBAIC0xMDI4LDE1ICsxMTA1LDMzIEBAIFNuYXBCdWlsZENvbW1pdFR4bihTbmFwQnVpbGQgKmJ1
aWxkZXIsIFhMb2dSZWNQdHIgbHNuLCBUcmFuc2FjdGlvbklkIHhpZCwKIAkJZWxvZyhERUJVRzIs
ICJmb3JjZWQgdHJhbnNhY3Rpb24gJXUgdG8gZG8gdGltZXRyYXZlbCBkdWUgdG8gb25lIG9mIGl0
cyBzdWJ0cmFuc2FjdGlvbnMiLAogCQkJIHhpZCk7CiAJCW5lZWRzX3RpbWV0cmF2ZWwgPSB0cnVl
OwotCQlTbmFwQnVpbGRBZGRDb21taXR0ZWRUeG4oYnVpbGRlciwgeGlkKTsKKwkJYmF0Y2hfeGlk
c1tiYXRjaF9jbnQrK10gPSB4aWQ7CiAJfQogCWVsc2UgaWYgKG5lZWRzX3RpbWV0cmF2ZWwpCiAJ
ewogCQllbG9nKERFQlVHMiwgImZvcmNlZCB0cmFuc2FjdGlvbiAldSB0byBkbyB0aW1ldHJhdmVs
IiwgeGlkKTsKIAotCQlTbmFwQnVpbGRBZGRDb21taXR0ZWRUeG4oYnVpbGRlciwgeGlkKTsKKwkJ
YmF0Y2hfeGlkc1tiYXRjaF9jbnQrK10gPSB4aWQ7CiAJfQogCisJLyoKKwkgKiBTb3J0IGFuZCBt
ZXJnZSB0aGUgYmF0Y2ggaW50byBjb21taXR0ZWQueGlwLiAgVGhpcyBtYWludGFpbnMgdGhlCisJ
ICogaW52YXJpYW50IHRoYXQgY29tbWl0dGVkLnhpcCBpcyBnbG9iYWxseSBzb3J0ZWQgYnkgcmF3
IHVpbnQzMiBvcmRlcgorCSAqICh4aWRDb21wYXJhdG9yKS4KKwkgKi8KKwlpZiAoYmF0Y2hfY250
ID4gMCkKKwl7CisJCS8qIFNvcnQgYnkgcmF3IHVpbnQzMiBvcmRlciAqLworCQlxc29ydChiYXRj
aF94aWRzLCBiYXRjaF9jbnQsIHNpemVvZihUcmFuc2FjdGlvbklkKSwgeGlkQ29tcGFyYXRvcik7
CisKKwkJLyogTWVyZ2UgaW50byBnbG9iYWwgYXJyYXkgKi8KKwkJU25hcEJ1aWxkQWRkQ29tbWl0
dGVkVHhucyhidWlsZGVyLCBiYXRjaF94aWRzLCBiYXRjaF9jbnQpOworCX0KKworCS8qIEZyZWUg
YmF0Y2ggYXJyYXkgaWYgYWxsb2NhdGVkIChldmVuIGlmIG5vdGhpbmcgd2FzIGFkZGVkIHRvIGl0
KSAqLworCWlmIChiYXRjaF94aWRzICE9IE5VTEwpCisJCXBmcmVlKGJhdGNoX3hpZHMpOworCiAJ
aWYgKCFuZWVkc190aW1ldHJhdmVsKQogCXsKIAkJLyogcmVjb3JkIHRoYXQgd2UgY2Fubm90IGV4
cG9ydCBhIGdlbmVyYWwgc25hcHNob3QgYW55bW9yZSAqLwpAQCAtMTMwNSw2ICsxNDAwLDE1IEBA
IFNuYXBCdWlsZEZpbmRTbmFwc2hvdChTbmFwQnVpbGQgKmJ1aWxkZXIsIFhMb2dSZWNQdHIgbHNu
LCB4bF9ydW5uaW5nX3hhY3RzICpydW5uCiAJCUFzc2VydChUcmFuc2FjdGlvbklkSXNOb3JtYWwo
YnVpbGRlci0+eG1pbikpOwogCQlBc3NlcnQoVHJhbnNhY3Rpb25JZElzTm9ybWFsKGJ1aWxkZXIt
PnhtYXgpKTsKIAorCQkvKgorCQkgKiBTb3J0IGNvbW1pdHRlZC54aXAgYmVmb3JlIHRyYW5zaXRp
b25pbmcgdG8gQ09OU0lTVEVOVC4gIER1cmluZyB0aGUKKwkJICogcHJlLUNPTlNJU1RFTlQgcGhh
c2UsIFhJRHMgd2VyZSBhcHBlbmRlZCB1bnNvcnRlZCBmb3IgcGVyZm9ybWFuY2UuCisJCSAqIE5v
dyB3ZSBuZWVkIHNvcnRlZCBvcmRlciBmb3IgZWZmaWNpZW50IHNuYXBzaG90IGJ1aWxkaW5nLgor
CQkgKi8KKwkJaWYgKGJ1aWxkZXItPmNvbW1pdHRlZC54Y250ID4gMSkKKwkJCXFzb3J0KGJ1aWxk
ZXItPmNvbW1pdHRlZC54aXAsIGJ1aWxkZXItPmNvbW1pdHRlZC54Y250LAorCQkJCSAgc2l6ZW9m
KFRyYW5zYWN0aW9uSWQpLCB4aWRDb21wYXJhdG9yKTsKKwogCQlidWlsZGVyLT5zdGF0ZSA9IFNO
QVBCVUlMRF9DT05TSVNURU5UOwogCQlidWlsZGVyLT5uZXh0X3BoYXNlX2F0ID0gSW52YWxpZFRy
YW5zYWN0aW9uSWQ7CiAKQEAgLTE0MDIsNiArMTUwNiwxNSBAQCBTbmFwQnVpbGRGaW5kU25hcHNo
b3QoU25hcEJ1aWxkICpidWlsZGVyLCBYTG9nUmVjUHRyIGxzbiwgeGxfcnVubmluZ194YWN0cyAq
cnVubgogCQkJIFRyYW5zYWN0aW9uSWRQcmVjZWRlc09yRXF1YWxzKGJ1aWxkZXItPm5leHRfcGhh
c2VfYXQsCiAJCQkJCQkJCQkJICAgcnVubmluZy0+b2xkZXN0UnVubmluZ1hpZCkpCiAJeworCQkv
KgorCQkgKiBTb3J0IGNvbW1pdHRlZC54aXAgYmVmb3JlIHRyYW5zaXRpb25pbmcgdG8gQ09OU0lT
VEVOVC4gIER1cmluZyB0aGUKKwkJICogcHJlLUNPTlNJU1RFTlQgcGhhc2UsIFhJRHMgd2VyZSBh
cHBlbmRlZCB1bnNvcnRlZCBmb3IgcGVyZm9ybWFuY2UuCisJCSAqIE5vdyB3ZSBuZWVkIHNvcnRl
ZCBvcmRlciBmb3IgZWZmaWNpZW50IHNuYXBzaG90IGJ1aWxkaW5nLgorCQkgKi8KKwkJaWYgKGJ1
aWxkZXItPmNvbW1pdHRlZC54Y250ID4gMSkKKwkJCXFzb3J0KGJ1aWxkZXItPmNvbW1pdHRlZC54
aXAsIGJ1aWxkZXItPmNvbW1pdHRlZC54Y250LAorCQkJCSAgc2l6ZW9mKFRyYW5zYWN0aW9uSWQp
LCB4aWRDb21wYXJhdG9yKTsKKwogCQlidWlsZGVyLT5zdGF0ZSA9IFNOQVBCVUlMRF9DT05TSVNU
RU5UOwogCQlidWlsZGVyLT5uZXh0X3BoYXNlX2F0ID0gSW52YWxpZFRyYW5zYWN0aW9uSWQ7CiAK
QEAgLTE4ODksNiArMjAwMiwxMyBAQCBTbmFwQnVpbGRSZXN0b3JlKFNuYXBCdWlsZCAqYnVpbGRl
ciwgWExvZ1JlY1B0ciBsc24pCiAJCXBmcmVlKGJ1aWxkZXItPmNvbW1pdHRlZC54aXApOwogCQli
dWlsZGVyLT5jb21taXR0ZWQueGNudF9zcGFjZSA9IG9uZGlzay5idWlsZGVyLmNvbW1pdHRlZC54
Y250OwogCQlidWlsZGVyLT5jb21taXR0ZWQueGlwID0gb25kaXNrLmJ1aWxkZXIuY29tbWl0dGVk
LnhpcDsKKworCQkvKgorCQkgKiBTb3J0IHRoZSByZXN0b3JlZCBhcnJheSB0byBlbnN1cmUgaXQn
cyBpbiB4aWRDb21wYXJhdG9yIG9yZGVyLiBPbGQKKwkJICogc25hcHNob3QgZmlsZXMgbWF5IGhh
dmUgYmVlbiB3cml0dGVuIHdpdGggdW5zb3J0ZWQgYXJyYXlzLgorCQkgKi8KKwkJcXNvcnQoYnVp
bGRlci0+Y29tbWl0dGVkLnhpcCwgYnVpbGRlci0+Y29tbWl0dGVkLnhjbnQsCisJCQkgIHNpemVv
ZihUcmFuc2FjdGlvbklkKSwgeGlkQ29tcGFyYXRvcik7CiAJfQogCW9uZGlzay5idWlsZGVyLmNv
bW1pdHRlZC54aXAgPSBOVUxMOwogCmRpZmYgLS1naXQgYS9zcmMvaW5jbHVkZS9yZXBsaWNhdGlv
bi9zbmFwYnVpbGRfaW50ZXJuYWwuaCBiL3NyYy9pbmNsdWRlL3JlcGxpY2F0aW9uL3NuYXBidWls
ZF9pbnRlcm5hbC5oCmluZGV4IDNiOTE1ZGM4NzkzLi4xNjQxNjBlNWU1ZSAxMDA2NDQKLS0tIGEv
c3JjL2luY2x1ZGUvcmVwbGljYXRpb24vc25hcGJ1aWxkX2ludGVybmFsLmgKKysrIGIvc3JjL2lu
Y2x1ZGUvcmVwbGljYXRpb24vc25hcGJ1aWxkX2ludGVybmFsLmgKQEAgLTExNSwxNiArMTE1LDgg
QEAgc3RydWN0IFNuYXBCdWlsZAogCQkvKgogCQkgKiBBcnJheSBvZiBjb21taXR0ZWQgdHJhbnNh
Y3Rpb25zIHRoYXQgaGF2ZSBtb2RpZmllZCB0aGUgY2F0YWxvZy4KIAkJICoKLQkJICogQXMgdGhp
cyBhcnJheSBpcyBmcmVxdWVudGx5IG1vZGlmaWVkIHdlIGRvICpub3QqIGtlZXAgaXQgaW4KLQkJ
ICogeGlkQ29tcGFyYXRvciBvcmRlci4gSW5zdGVhZCB3ZSBzb3J0IHRoZSBhcnJheSB3aGVuIGJ1
aWxkaW5nICYKLQkJICogZGlzdHJpYnV0aW5nIGEgc25hcHNob3QuCi0JCSAqCi0JCSAqIFRPRE86
IEl0J3MgdW5jbGVhciB3aGV0aGVyIHRoYXQgcmVhc29uaW5nIGhhcyBtdWNoIG1lcml0LiBFdmVy
eQotCQkgKiB0aW1lIHdlIGFkZCBzb21ldGhpbmcgaGVyZSBhZnRlciBiZWNvbWluZyBjb25zaXN0
ZW50IHdpbGwgYWxzbwotCQkgKiByZXF1aXJlIGRpc3RyaWJ1dGluZyBhIHNuYXBzaG90LiBTdG9y
aW5nIHRoZW0gc29ydGVkIHdvdWxkCi0JCSAqIHBvdGVudGlhbGx5IGFsc28gbWFrZSBpdCBlYXNp
ZXIgdG8gcHVyZ2UgKGJ1dCBtb3JlIGNvbXBsaWNhdGVkIHdydAotCQkgKiB3cmFwYXJvdW5kPyku
IFNob3VsZCBiZSBpbXByb3ZlZCBpZiBzb3J0aW5nIHdoaWxlIGJ1aWxkaW5nIHRoZQotCQkgKiBz
bmFwc2hvdCBzaG93cyB1cCBpbiBwcm9maWxlcy4KKwkJICogTWFpbnRhaW5lZCBpbiBzb3J0ZWQg
b3JkZXIgKGJ5IHJhdyB1aW50MzIgdmFsdWUpIHRvIGFsbG93IGVmZmljaWVudAorCQkgKiBzbmFw
c2hvdCBidWlsZGluZyB3aXRob3V0IHJlcGVhdGVkIHNvcnRpbmcgb3ZlcmhlYWQuCiAJCSAqLwog
CQlUcmFuc2FjdGlvbklkICp4aXA7CiAJfQkJCWNvbW1pdHRlZDsKLS0gCjIuNTEuMAoK
--00000000000028c1c506460f145d--