MIME-Version: 1.0
References: <CA+hUKGJ_7NKd46nx1wbyXWriuZSNzsTfm+rhEuvU6nxZi3-KVw@mail.gmail.com>
 <d8c3bbe9-690d-4d51-9d80-51f9856ee086@postgresql.org>
In-Reply-To: <d8c3bbe9-690d-4d51-9d80-51f9856ee086@postgresql.org>
From: Thomas Munro <thomas.munro@gmail.com>
Date: Fri, 6 Sep 2024 16:28:52 +1200
Message-ID: <CA+hUKG+x2BcqWzBC77cN0ewhzMF0kYhC6c4G_T2gJLPbqYQ6Ow@mail.gmail.com>
Subject: Re: Trying out read streams in pgvector (an extension)
To: "Jonathan S. Katz" <jkatz@postgresql.org>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Content-Type: multipart/mixed; boundary="0000000000006cb83906216bdad2"
Archived-At: <https://www.postgresql.org/message-id/CA%2BhUKG%2Bx2BcqWzBC77cN0ewhzMF0kYhC6c4G_T2gJLPbqYQ6Ow%40mail.gmail.com>
Precedence: bulk

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

On Wed, Jun 12, 2024 at 3:37=E2=80=AFAM Jonathan S. Katz <jkatz@postgresql.=
org> wrote:
> If you're curious, I can fire up some of my more serious benchmarks on
> this to do a before/after to see if there's anything interesting. I have
> a few large datasets (10s of millions) of larger vectors (1536dim =3D> 6K=
B
> payloads) that could see the net effect here.
>
> > (Make sure you remember to set effective_io_concurrency to an
> > interesting number if you want to generate a lot of overlapping
> > fadvise calls.)
>
> What would you recommend as an "interesting number?" - particularly
> using the data parameters above.

Hi Jonathan,

Sorry for not replying sooner (ETOOMANYPROJECTS).  For HNSW, I think
the maximum useful effective_io_concurrency is bound by the number of
connections per HNSW layer ("m").  Here are some times I measured
using m=3D16 on two laptops:

              |     linux (xfs)           |  macos (apfs)
 branch | eic |  avg   | speedup | stdev  |  avg   | speedup | stdev
--------+-----+--------+---------+--------+--------+---------+--------
 master |     | 73.959 |     1.0 | 24.168 | 72.290 |     1.0 | 11.851
 stream |   0 | 70.117 |     1.1 | 36.699 | 76.289 |     1.0 | 12.742
 stream |   1 | 57.983 |     1.3 |  5.845 | 79.969 |     1.2 |  8.308
 stream |   2 | 35.629 |     2.1 |  4.088 | 49.198 |     2.0 |  7.686
 stream |   3 | 28.477 |     2.6 |  2.607 | 37.540 |     2.5 |  5.272
 stream |   4 | 26.493 |     2.8 |  3.691 | 33.014 |     2.7 |  4.444
 stream |   5 | 23.711 |     3.1 |  2.435 | 32.622 |     3.0 |  2.270
 stream |   6 | 22.885 |     3.2 |  1.908 | 31.254 |     3.2 |  4.170
 stream |   7 | 21.910 |     3.4 |  2.153 | 33.669 |     3.3 |  4.616
 stream |   8 | 20.741 |     3.6 |  1.594 | 34.182 |     3.5 |  3.819
 stream |   9 | 22.471 |     3.3 |  3.094 | 30.690 |     3.2 |  2.677
 stream |  10 | 19.895 |     3.7 |  1.695 | 32.631 |     3.6 |  4.976
 stream |  11 | 19.447 |     3.8 |  1.647 | 31.163 |     3.7 |  3.351
 stream |  12 | 18.658 |     4.0 |  1.503 | 30.817 |     3.9 |  3.538
 stream |  13 | 18.886 |     3.9 |  0.874 | 29.184 |     3.8 |  4.832
 stream |  14 | 18.667 |     4.0 |  1.692 | 28.783 |     3.9 |  3.459
 stream |  15 | 19.080 |     3.9 |  1.429 | 28.928 |     3.8 |  3.396
 stream |  16 | 18.929 |     3.9 |  3.469 | 29.282 |     3.8 |  2.868

Those are millisecond times to run the test() function shown earlier,
with empty kernel cache and PostgreSQL cache (see below) for maximum
physical I/O.  I ran the master test 30 times, and each
effective_io_concurrency level 10 times, to show that the variance
decreases even at the default effective_io_concurency =3D 1, so we're
not only talking about the avg speed improving.

The all-cached performance also seems to improve, ~8.9ms -> ~6.9ms on
Linux, but I can't fully explain why that is, maybe just some random
stuff about memory layout run-to-run in my quick and dirty test or
something like that, so I'm not claiming that is significant.  It
certainly didn't get slower, anyway.

I think you would get very different numbers on a high latency storage
system (say, non-local cloud storage) and potentially much more
speedup with your large test indexes.  Also my 6d random number test
may not be very representative and you may be able to come up with
much better tests.

Here's a new version with a TODO tidied up.  I also understood that we
need to tweak the read_stream_reset() function, so that it doesn't
forget its current readhead distance when it hops between HNSW nodes
(which is something that comes up in several other potential uses
cases including another one I am working in in core).  Without this
patch for PostgreSQL, it reads 1, 2, 4, 7 blocks (=3D 16 in total)
before it has to take a break to hop to a new page, and then it start
again at 1.  Oops.  With this patch, it is less forgetful, and reaches
the full possible I/O concurrency of 16 (or whatever the minimum of
HNSW's m parameter and effective_io_concurrency is for you).

PSA two patches, one for PostgreSQL and one for pgvector.

I am not actively working on this right now.  If someone wants to try
to develop it further, please feel free!  I haven't looked at IVFFlat
at all.

--- function to let you do SELECT uncache('t_embedding_idx'),
--- which is the opposite of SELECT pg_prewarm('t_embedding_idx')
--- see also "echo 1 | sudo tee /proc/sys/vm/drop_caches" (Linux)
--- "sudo purge" (macOS)
create extension pg_buffercache;
create or replace function uncache(name text) returns bool
begin atomic;
  select bool_and(pg_buffercache_evict(bufferid))
    from pg_buffercache where relfilenode =3D name::regclass;
end;

--0000000000006cb83906216bdad2
Content-Type: text/x-patch; charset="US-ASCII"; 
	name="0001-Remember-ReadStream-look-ahead-distance-on-reset.patch"
Content-Disposition: attachment; 
	filename="0001-Remember-ReadStream-look-ahead-distance-on-reset.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_m0q7ol7t1>
X-Attachment-Id: f_m0q7ol7t1

RnJvbSA3NGI0NWU2YTYzODdmMGI3YTBmMTIwNjBhMGQ4Y2I0MDFhODU1NTJlIE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiBUaG9tYXMgTXVucm8gPHRob21hcy5tdW5yb0BnbWFpbC5jb20+
CkRhdGU6IFNhdCwgMTUgSnVuIDIwMjQgMTQ6Mzc6MjYgKzEyMDAKU3ViamVjdDogW1BBVENIXSBS
ZW1lbWJlciBSZWFkU3RyZWFtIGxvb2stYWhlYWQgZGlzdGFuY2Ugb24gcmVzZXQuCgpTb21lIFJl
YWRTdHJlYW0gY2xpZW50cyBuZWVkIHRvIGRvIG1vcmUgd29yayB0byBtYWtlIGEgbmV3IHN0cmVh
bSBvZgpibG9jayBudW1iZXJzIGF2YWlsYWJsZS4gIFRoZSBjYWxsYmFjayBpbmRpY2F0ZXMgdGhh
dCBibG9jayBudW1iZXJzIGhhdmUKcnVuIG91dCBieSByZXR1cm5pbmcgSW52YWxpZEJsb2NrTnVt
YmVyLCBidXQgc29tZSB0aW1lIGxhdGVyIHRoZSBjbGllbnQKY29kZSByZXNldHMgdGhlIFJlYWRT
dHJlYW0gdG8gdGVsbCBpdCB0aGF0IHRoZSBjYWxsYmFjayBub3cgaGFzIG1vcmUKYmxvY2sgbnVt
YmVyLCBzbyB0aGF0IGl0IGNhbiBiZWdpbiBjb25zdW1pbmcgYnVmZmVycyBhZ2Fpbi4gIEZvcgpl
eGFtcGxlLCBwZ3ZlY3RvcidzIEhOU1cgaW5kZXggc2NhbiByZWFjaCBhIG5ldyBwYWdlLCBhbmQg
ZmluZCBhIG5ldyBzZXQKb2YgY29ubmVjdGlvbnMgdG8gbWFueSBvdGhlciBwYWdlcyB0aGF0IHdp
bGwgc29vbiBiZSBhY2Nlc2VkLgoKV2hlbiB0aGUgc3RyZWFtIGlzIHJlc2V0LCBpdCB3b3VsZCBw
cmV2aW91c2x5IHJlc2V0IGl0cyBsb29rLWFoZWFkCmRpc3RhbmNlIHRvIDEsIGFuZCBoYXZlIHRv
IGJ1aWxkIGl0IGJhY2sgdXAgYWdhaW4gaWYgSS9PIGlzIG5lY2Vzc2FyeS4KV2l0aCB0aGlzIHBh
dGNoLCBpdCB3aWxsIHJlbWVtYmVyIHdoYXQgaXQgaGFkIGJlZm9yZSwgd2hpY2ggc2VlbXMgbGlr
ZSBhCmJldHRlciBiZXQuICBJZiB0aGF0J3Mgd3JvbmcsIGl0IHdpbGwgc29vbiByYW1wIGRvd24g
dmlhIHRoZSB1c3VhbAphbGdvcml0aG0uCgpEaXNjdXNzaW9uOiBodHRwczovL3Bvc3Rnci5lcy9t
L0NBJTJCaFVLR0pfN05LZDQ2bngxd2J5WFdyaXVaU056c1RmbSUyQnJoRXV2VTZueFppMy1LVncl
NDBtYWlsLmdtYWlsLmNvbQotLS0KIHNyYy9iYWNrZW5kL3N0b3JhZ2UvYWlvL3JlYWRfc3RyZWFt
LmMgfCAxMCArKysrKysrKy0tCiAxIGZpbGUgY2hhbmdlZCwgOCBpbnNlcnRpb25zKCspLCAyIGRl
bGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL3N0b3JhZ2UvYWlvL3JlYWRfc3Ry
ZWFtLmMgYi9zcmMvYmFja2VuZC9zdG9yYWdlL2Fpby9yZWFkX3N0cmVhbS5jCmluZGV4IDdmMGUw
N2Q5NTg2Li41ZDNlMDcwYWZhZSAxMDA2NDQKLS0tIGEvc3JjL2JhY2tlbmQvc3RvcmFnZS9haW8v
cmVhZF9zdHJlYW0uYworKysgYi9zcmMvYmFja2VuZC9zdG9yYWdlL2Fpby9yZWFkX3N0cmVhbS5j
CkBAIC0xMTUsNiArMTE1LDcgQEAgc3RydWN0IFJlYWRTdHJlYW0KIAlpbnQxNgkJbWF4X3Bpbm5l
ZF9idWZmZXJzOwogCWludDE2CQlwaW5uZWRfYnVmZmVyczsKIAlpbnQxNgkJZGlzdGFuY2U7CisJ
aW50MTYJCXJlc2V0X2Rpc3RhbmNlOwogCWJvb2wJCWFkdmljZV9lbmFibGVkOwogCiAJLyoKQEAg
LTMzNSw2ICszMzYsNyBAQCByZWFkX3N0cmVhbV9sb29rX2FoZWFkKFJlYWRTdHJlYW0gKnN0cmVh
bSwgYm9vbCBzdXBwcmVzc19hZHZpY2UpCiAJCWlmIChibG9ja251bSA9PSBJbnZhbGlkQmxvY2tO
dW1iZXIpCiAJCXsKIAkJCS8qIEVuZCBvZiBzdHJlYW0uICovCisJCQlzdHJlYW0tPnJlc2V0X2Rp
c3RhbmNlID0gc3RyZWFtLT5kaXN0YW5jZTsKIAkJCXN0cmVhbS0+ZGlzdGFuY2UgPSAwOwogCQkJ
YnJlYWs7CiAJCX0KQEAgLTUyNiw2ICs1MjgsNyBAQCByZWFkX3N0cmVhbV9iZWdpbl9pbXBsKGlu
dCBmbGFncywKIAkJc3RyZWFtLT5kaXN0YW5jZSA9IE1pbihtYXhfcGlubmVkX2J1ZmZlcnMsIGlv
X2NvbWJpbmVfbGltaXQpOwogCWVsc2UKIAkJc3RyZWFtLT5kaXN0YW5jZSA9IDE7CisJc3RyZWFt
LT5yZXNldF9kaXN0YW5jZSA9IHN0cmVhbS0+ZGlzdGFuY2U7CiAKIAkvKgogCSAqIFNpbmNlIHdl
IGFsd2F5cyBhY2Nlc3MgdGhlIHNhbWUgcmVsYXRpb24sIHdlIGNhbiBpbml0aWFsaXplIHBhcnRz
IG9mCkBAIC04MjIsOCArODI1LDExIEBAIHJlYWRfc3RyZWFtX3Jlc2V0KFJlYWRTdHJlYW0gKnN0
cmVhbSkKIAlBc3NlcnQoc3RyZWFtLT5waW5uZWRfYnVmZmVycyA9PSAwKTsKIAlBc3NlcnQoc3Ry
ZWFtLT5pb3NfaW5fcHJvZ3Jlc3MgPT0gMCk7CiAKLQkvKiBTdGFydCBvZmYgYXNzdW1pbmcgZGF0
YSBpcyBjYWNoZWQuICovCi0Jc3RyZWFtLT5kaXN0YW5jZSA9IDE7CisJLyoKKwkgKiBJZiB0aGUg
Y2FsbGJhY2sgcmFuIG91dCBvZiBibG9ja3MgdGVtcG9yYXJpbHksIHJlc3RvcmUgdGhlIGRpc3Rh
bmNlIGZyb20KKwkgKiBiZWZvcmUuCisJICovCisJc3RyZWFtLT5kaXN0YW5jZSA9IE1heChzdHJl
YW0tPnJlc2V0X2Rpc3RhbmNlLCAxKTsKIH0KIAogLyoKLS0gCjIuNDYuMAoK
--0000000000006cb83906216bdad2
Content-Type: text/x-patch; charset="US-ASCII"; 
	name="v2-0001-Use-streaming-I-O-for-HNSW-blocks.patch"
Content-Disposition: attachment; 
	filename="v2-0001-Use-streaming-I-O-for-HNSW-blocks.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_m0q7t9w01>
X-Attachment-Id: f_m0q7t9w01

RnJvbSAyMWI0MDRkOGE2ZjQwMGJiNmRhMWJiZmNhNzUwOWE0MWYyYjlmMDAyIE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiBUaG9tYXMgTXVucm8gPHRob21hcy5tdW5yb0BnbWFpbC5jb20+
CkRhdGU6IFR1ZSwgMTEgSnVuIDIwMjQgMTQ6MzI6NDcgKzEyMDAKU3ViamVjdDogW1BBVENIIHYy
XSBVc2Ugc3RyZWFtaW5nIEkvTyBmb3IgSE5TVyBibG9ja3MuCgpJZiBkYXRhIGlzIG5vdCBhbHJl
YWR5IGluIFBvc3RncmVTUUwncyBjYWNoZSwgaXQgd2lsbCBiZSBhY2Nlc3NlZCB1c2luZwp0aGUg
bmV3IFJlYWRTdHJlYW0gQVBJIGluIFBvc3RncmVTUUwgMTcuICBXZSBrbm93IHRoZSBuZXh0ICdt
JyBITlNXCmJsb2NrcyB3ZSB3aWxsIGFjY2Vzcywgc28gdGhlIFJlYWRTdHJlYW0gY2FuIHJlYWQg
dGhlbSBpbnRvIHRoZQprZXJuZWwncyBwYWdlIGNhY2hlIGFzeW5jaHJvbm91c2x5LCB1cCB0byB0
aGUgbGltaXQgb2YgdGhlCmVmZmVjdGl2ZV9pb19jb25jdXJyZW5jeSBzZXR0aW5nLiAgIFdoaWxl
IHRoYXQgY3VycmVudGx5IGRlZmF1bHRzIHRvCm9ubHkgMSwgZXZlbiAxIHByb3ZpZGVzIHNvbWUg
c3BlZWR1cCBmb3IgY29sZCBjYWNoZXMsIGFuZCBoaWdoZXIgbnVtYmVyCmhlbHAgbW9yZS4KClhY
WCBUaGlzIGlzIGEgcHJvb2Ytb2YtY29uY2VwdAoKQXV0aG9yOiBUaG9tYXMgTXVucm8gPHRob21h
cy5tdW5yb0BnbWFpbC5jb20+CkRpc2N1c3Npb246IGh0dHBzOi8vd3d3LnBvc3RncmVzcWwub3Jn
L21lc3NhZ2UtaWQvZmxhdC9DQSUyQmhVS0dKXzdOS2Q0Nm54MXdieVhXcml1WlNOenNUZm0lMkJy
aEV1dlU2bnhaaTMtS1Z3JTQwbWFpbC5nbWFpbC5jb20KLS0tCiBzcmMvaG5zdy5oICAgICAgfCAg
IDEgKwogc3JjL2huc3d1dGlscy5jIHwgMTEzICsrKysrKysrKysrKysrKysrKysrKysrKysrKysr
KysrKysrKysrKysrKysrKysrKwogMiBmaWxlcyBjaGFuZ2VkLCAxMTQgaW5zZXJ0aW9ucygrKQoK
ZGlmZiAtLWdpdCBhL3NyYy9obnN3LmggYi9zcmMvaG5zdy5oCmluZGV4IDQ4MGFkOWYuLmU3Mzgy
NDEgMTAwNjQ0Ci0tLSBhL3NyYy9obnN3LmgKKysrIGIvc3JjL2huc3cuaApAQCAtMTM2LDYgKzEz
Niw3IEBAIHN0cnVjdCBIbnN3RWxlbWVudERhdGEKIAl1aW50OAkJZGVsZXRlZDsKIAl1aW50MzIJ
CWhhc2g7CiAJSG5zd05laWdoYm9yc1B0ciBuZWlnaGJvcnM7CisJQnVmZmVyCQlidWZmZXI7CiAJ
QmxvY2tOdW1iZXIgYmxrbm87CiAJT2Zmc2V0TnVtYmVyIG9mZm5vOwogCU9mZnNldE51bWJlciBu
ZWlnaGJvck9mZm5vOwpkaWZmIC0tZ2l0IGEvc3JjL2huc3d1dGlscy5jIGIvc3JjL2huc3d1dGls
cy5jCmluZGV4IDk2YzUwMjYuLjQ2ZTc2YmUgMTAwNjQ0Ci0tLSBhL3NyYy9obnN3dXRpbHMuYwor
KysgYi9zcmMvaG5zd3V0aWxzLmMKQEAgLTE0LDYgKzE0LDEwIEBACiAjaW5jbHVkZSAidXRpbHMv
bWVtZGVidWcuaCIKICNpbmNsdWRlICJ1dGlscy9yZWwuaCIKIAorI2lmIFBHX1ZFUlNJT05fTlVN
ID49IDE3MDAwMAorI2luY2x1ZGUgInN0b3JhZ2UvcmVhZF9zdHJlYW0uaCIKKyNlbmRpZgorCiAj
aWYgUEdfVkVSU0lPTl9OVU0gPj0gMTMwMDAwCiAjaW5jbHVkZSAiY29tbW9uL2hhc2hmbi5oIgog
I2Vsc2UKQEAgLTI3OCw2ICsyODIsOSBAQCBIbnN3SW5pdEVsZW1lbnRGcm9tQmxvY2soQmxvY2tO
dW1iZXIgYmxrbm8sIE9mZnNldE51bWJlciBvZmZubykKIAlIbnN3RWxlbWVudCBlbGVtZW50ID0g
cGFsbG9jKHNpemVvZihIbnN3RWxlbWVudERhdGEpKTsKIAljaGFyCSAgICpiYXNlID0gTlVMTDsK
IAorI2lmIFBHX1ZFUlNJT05fTlVNID49IDE3MDAwMAorCWVsZW1lbnQtPmJ1ZmZlciA9IEludmFs
aWRCdWZmZXI7CisjZW5kaWYKIAllbGVtZW50LT5ibGtubyA9IGJsa25vOwogCWVsZW1lbnQtPm9m
Zm5vID0gb2Zmbm87CiAJSG5zd1B0clN0b3JlKGJhc2UsIGVsZW1lbnQtPm5laWdoYm9ycywgKEhu
c3dOZWlnaGJvckFycmF5UHRyICopIE5VTEwpOwpAQCAtNTU1LDcgKzU2MiwyMCBAQCBIbnN3TG9h
ZEVsZW1lbnQoSG5zd0VsZW1lbnQgZWxlbWVudCwgZmxvYXQgKmRpc3RhbmNlLCBEYXR1bSAqcSwg
UmVsYXRpb24gaW5kZXgsCiAJSG5zd0VsZW1lbnRUdXBsZSBldHVwOwogCiAJLyogUmVhZCB2ZWN0
b3IgKi8KKyNpZiBQR19WRVJTSU9OX05VTSA+PSAxNzAwMDAKKwlpZiAoZWxlbWVudC0+YnVmZmVy
ICE9IEludmFsaWRCdWZmZXIpCisJeworCQkvKiBCdWZmZXIgcGlubmVkIGFscmVhZHkuICovCisJ
CWJ1ZiA9IGVsZW1lbnQtPmJ1ZmZlcjsKKwkJQXNzZXJ0KEJ1ZmZlckdldEJsb2NrTnVtYmVyKGJ1
ZikgPT0gZWxlbWVudC0+Ymxrbm8pOworCX0KKwllbHNlCisJeworCQlidWYgPSBSZWFkQnVmZmVy
KGluZGV4LCBlbGVtZW50LT5ibGtubyk7CisJfQorI2Vsc2UKIAlidWYgPSBSZWFkQnVmZmVyKGlu
ZGV4LCBlbGVtZW50LT5ibGtubyk7CisjZW5kaWYKIAlMb2NrQnVmZmVyKGJ1ZiwgQlVGRkVSX0xP
Q0tfU0hBUkUpOwogCXBhZ2UgPSBCdWZmZXJHZXRQYWdlKGJ1Zik7CiAKQEAgLTcxNyw2ICs3Mzcs
MzQgQEAgQ291bnRFbGVtZW50KGNoYXIgKmJhc2UsIEhuc3dFbGVtZW50IHNraXBFbGVtZW50LCBI
bnN3Q2FuZGlkYXRlICogaGMpCiAJcmV0dXJuIGUtPmhlYXB0aWRzTGVuZ3RoICE9IDA7CiB9CiAK
KyNpZiBQR19WRVJTSU9OX05VTSA+PSAxNzAwMDAKK3R5cGVkZWYgc3RydWN0IEhuc3dTZWFyY2hM
YXllck5leHRCbG9ja0RhdGEgeworCWNoYXIJICAgKmJhc2U7CisJSG5zd0NhbmRpZGF0ZSAqKml0
ZW1zOworCWludAkJCW5pdGVtczsKKwlpbnQJCQlpOworfSBIbnN3U2VhcmNoTGF5ZXJOZXh0Qmxv
Y2tEYXRhOworCisvKgorICogQ2FsbGJhY2sgdXNlZCB0byBmZWVkIGJsb2NrIG51bWJlcnMgdG8g
dGhlIFJlYWRTdHJlYW0uCisgKi8KK3N0YXRpYyBCbG9ja051bWJlcgorSG5zd1NlYXJjaExheWVy
TmV4dEJsb2NrKFJlYWRTdHJlYW0gKnN0cmVhbSwKKwkJCQkJCSB2b2lkICpjYWxsYmFja19kYXRh
LAorCQkJCQkJIHZvaWQgKnBlcl9idWZmZXJfZGF0YSkKK3sKKwlIbnN3U2VhcmNoTGF5ZXJOZXh0
QmxvY2tEYXRhICpkYXRhID0gY2FsbGJhY2tfZGF0YTsKKwlIbnN3RWxlbWVudCBoY2U7CisKKwlp
ZiAoZGF0YS0+aSA9PSBkYXRhLT5uaXRlbXMpCisJCXJldHVybiBJbnZhbGlkQmxvY2tOdW1iZXI7
CisKKwloY2UgPSBIbnN3UHRyQWNjZXNzKGRhdGEtPmJhc2UsIGRhdGEtPml0ZW1zW2RhdGEtPmkr
K10tPmVsZW1lbnQpOworCisJcmV0dXJuIGhjZS0+Ymxrbm87Cit9CisjZW5kaWYKKwogLyoKICAq
IEFsZ29yaXRobSAyIGZyb20gcGFwZXIKICAqLwpAQCAtNzMyLDYgKzc4MCwyNyBAQCBIbnN3U2Vh
cmNoTGF5ZXIoY2hhciAqYmFzZSwgRGF0dW0gcSwgTGlzdCAqZXAsIGludCBlZiwgaW50IGxjLCBS
ZWxhdGlvbiBpbmRleCwgRgogCUhuc3dOZWlnaGJvckFycmF5ICpuZWlnaGJvcmhvb2REYXRhID0g
TlVMTDsKIAlTaXplCQluZWlnaGJvcmhvb2RTaXplID0gMDsKIAorI2lmIFBHX1ZFUlNJT05fTlVN
ID49IDE3MDAwMAorCUhuc3dTZWFyY2hMYXllck5leHRCbG9ja0RhdGEgc3RyZWFtX2NhbGxiYWNr
X2RhdGEgPSB7MH07CisJUmVhZFN0cmVhbSAqc3RyZWFtOworCisJLyoKKwkgKiBJZiB3ZSdyZSBz
ZWFyY2hpbmcgYW4gaW5kZXgsIGNyZWF0ZSBhIHN0cmVhbSBzbyB0aGF0IHdlIGNhbiBnZW5lcmF0
ZQorCSAqIHNvbWUgSS9PIGFzeW5jaHJvbmljaXR5IHdoZW4gdGhlIGluZGV4IGlzIGNvbGQsIGlm
CisJICogZWZmZWN0aXZlX2lvX2NvbmN1cnJlbmN5IGlzIGNvbmZpZ3VyZWQuCisJICovCisJaWYg
KGluZGV4KQorCQlzdHJlYW0gPSByZWFkX3N0cmVhbV9iZWdpbl9yZWxhdGlvbihSRUFEX1NUUkVB
TV9GVUxMLAorCQkJCQkJCQkJCQlOVUxMLAorCQkJCQkJCQkJCQlpbmRleCwKKwkJCQkJCQkJCQkJ
TUFJTl9GT1JLTlVNLAorCQkJCQkJCQkJCQlIbnN3U2VhcmNoTGF5ZXJOZXh0QmxvY2ssCisJCQkJ
CQkJCQkJCSZzdHJlYW1fY2FsbGJhY2tfZGF0YSwKKwkJCQkJCQkJCQkJMCk7CisJZWxzZQorCQlz
dHJlYW0gPSBOVUxMOworI2VuZGlmCisKIAlJbml0VmlzaXRlZChiYXNlLCAmdiwgaW5kZXgsIGVm
LCBtKTsKIAogCS8qIENyZWF0ZSBsb2NhbCBtZW1vcnkgZm9yIG5laWdoYm9yaG9vZCBpZiBuZWVk
ZWQgKi8KQEAgLTc2Nyw2ICs4MzYsOCBAQCBIbnN3U2VhcmNoTGF5ZXIoY2hhciAqYmFzZSwgRGF0
dW0gcSwgTGlzdCAqZXAsIGludCBlZiwgaW50IGxjLCBSZWxhdGlvbiBpbmRleCwgRgogCQlIbnN3
Q2FuZGlkYXRlICpjID0gKChIbnN3UGFpcmluZ0hlYXBOb2RlICopIHBhaXJpbmdoZWFwX3JlbW92
ZV9maXJzdChDKSktPmlubmVyOwogCQlIbnN3Q2FuZGlkYXRlICpmID0gKChIbnN3UGFpcmluZ0hl
YXBOb2RlICopIHBhaXJpbmdoZWFwX2ZpcnN0KFcpKS0+aW5uZXI7CiAJCUhuc3dFbGVtZW50IGNF
bGVtZW50OworCQlIbnN3Q2FuZGlkYXRlICppdGVtc1tITlNXX01BWF9TSVpFXTsKKwkJaW50IG5p
dGVtczsKIAogCQlpZiAoYy0+ZGlzdGFuY2UgPiBmLT5kaXN0YW5jZSkKIAkJCWJyZWFrOwpAQCAt
Nzg4LDYgKzg1OSw4IEBAIEhuc3dTZWFyY2hMYXllcihjaGFyICpiYXNlLCBEYXR1bSBxLCBMaXN0
ICplcCwgaW50IGVmLCBpbnQgbGMsIFJlbGF0aW9uIGluZGV4LCBGCiAJCQluZWlnaGJvcmhvb2Qg
PSBuZWlnaGJvcmhvb2REYXRhOwogCQl9CiAKKwkJLyogQnVpbGQgYSBsaXN0IG9mIGluZGV4ZXMg
b2YgbmVpZ2hib3JzIHRvIHZpc2l0LiAqLworCQluaXRlbXMgPSAwOwogCQlmb3IgKGludCBpID0g
MDsgaSA8IG5laWdoYm9yaG9vZC0+bGVuZ3RoOyBpKyspCiAJCXsKIAkJCUhuc3dDYW5kaWRhdGUg
KmUgPSAmbmVpZ2hib3Job29kLT5pdGVtc1tpXTsKQEAgLTc5Niw2ICs4NjksMzUgQEAgSG5zd1Nl
YXJjaExheWVyKGNoYXIgKmJhc2UsIERhdHVtIHEsIExpc3QgKmVwLCBpbnQgZWYsIGludCBsYywg
UmVsYXRpb24gaW5kZXgsIEYKIAkJCUFkZFRvVmlzaXRlZChiYXNlLCAmdiwgZSwgaW5kZXgsICZ2
aXNpdGVkKTsKIAogCQkJaWYgKCF2aXNpdGVkKQorCQkJCWl0ZW1zW25pdGVtcysrXSA9IGU7CisJ
CX0KKworI2lmIFBHX1ZFUlNJT05fTlVNID49IDE3MDAwMAorCQlpZiAoc3RyZWFtKQorCQl7CisJ
CQkvKgorCQkJICogR2l2ZSB0aGUgY2FsbGJhY2sgdGhlIGluZm9ybWF0aW9uIGl0IG5lZWRzIHRv
IGZpbmQgZnV0dXJlIGJsb2NrCisJCQkgKiBudW1iZXJzLgorCQkJICovCisJCQlzdHJlYW1fY2Fs
bGJhY2tfZGF0YS5iYXNlID0gYmFzZTsKKwkJCXN0cmVhbV9jYWxsYmFja19kYXRhLml0ZW1zID0g
aXRlbXM7CisJCQlzdHJlYW1fY2FsbGJhY2tfZGF0YS5uaXRlbXMgPSBuaXRlbXM7CisJCQlzdHJl
YW1fY2FsbGJhY2tfZGF0YS5pID0gMDsKKworCQkJLyoKKwkJCSAqIFJlc2V0IHRoZSBzdHJlYW0u
ICBUaGlzIGlzIG5lY2Vzc2FyeSBiZWNhdXNlIGVhY2ggdGltZSB0aGUKKwkJCSAqIGNhbGxiYWNr
IHJ1bnMgb3V0IG9mIGRhdGEsIHRoZSBzdHJlYW0gbmVlZHMgdG8gYmUgcmVzZXRhcnRlZAorCQkJ
ICogYmVmb3JlIGl0IHRyaWVzIHRvIGxvb2sgYWhlYWQgYWdhaW4uCisJCQkgKi8KKwkJCXJlYWRf
c3RyZWFtX3Jlc2V0KHN0cmVhbSk7CisJCX0KKyNlbmRpZgorCisJCS8qIFZpc2l0IHRoZW0uICov
CisJCWZvciAoaW50IGkgPSAwOyBpIDwgbml0ZW1zOyBpKyspCisJCXsKKwkJCUhuc3dDYW5kaWRh
dGUgKmUgPSBpdGVtc1tpXTsKKwogCQkJewogCQkJCWZsb2F0CQllRGlzdGFuY2U7CiAJCQkJSG5z
d0VsZW1lbnQgZUVsZW1lbnQgPSBIbnN3UHRyQWNjZXNzKGJhc2UsIGUtPmVsZW1lbnQpOwpAQCAt
ODA2LDcgKzkwOCwxMyBAQCBIbnN3U2VhcmNoTGF5ZXIoY2hhciAqYmFzZSwgRGF0dW0gcSwgTGlz
dCAqZXAsIGludCBlZiwgaW50IGxjLCBSZWxhdGlvbiBpbmRleCwgRgogCQkJCWlmIChpbmRleCA9
PSBOVUxMKQogCQkJCQllRGlzdGFuY2UgPSBHZXRDYW5kaWRhdGVEaXN0YW5jZShiYXNlLCBlLCBx
LCBwcm9jaW5mbywgY29sbGF0aW9uKTsKIAkJCQllbHNlCisJCQkJeworI2lmIFBHX1ZFUlNJT05f
TlVNID49IDE3MDAwMAorCQkJCQlpZiAoc3RyZWFtKQorCQkJCQkJZUVsZW1lbnQtPmJ1ZmZlciA9
IHJlYWRfc3RyZWFtX25leHRfYnVmZmVyKHN0cmVhbSwgTlVMTCk7CisjZW5kaWYKIAkJCQkJSG5z
d0xvYWRFbGVtZW50KGVFbGVtZW50LCAmZURpc3RhbmNlLCAmcSwgaW5kZXgsIHByb2NpbmZvLCBj
b2xsYXRpb24sIGluc2VydGluZywgYWx3YXlzQWRkID8gTlVMTCA6ICZmLT5kaXN0YW5jZSk7CisJ
CQkJfQogCiAJCQkJaWYgKGVEaXN0YW5jZSA8IGYtPmRpc3RhbmNlIHx8IGFsd2F5c0FkZCkKIAkJ
CQl7CkBAIC04NDQsNiArOTUyLDExIEBAIEhuc3dTZWFyY2hMYXllcihjaGFyICpiYXNlLCBEYXR1
bSBxLCBMaXN0ICplcCwgaW50IGVmLCBpbnQgbGMsIFJlbGF0aW9uIGluZGV4LCBGCiAJCX0KIAl9
CiAKKyNpZiBQR19WRVJTSU9OX05VTSA+PSAxNzAwMDAKKwlpZiAoc3RyZWFtKQorCQlyZWFkX3N0
cmVhbV9lbmQoc3RyZWFtKTsKKyNlbmRpZgorCiAJLyogQWRkIGVhY2ggZWxlbWVudCBvZiBXIHRv
IHcgKi8KIAl3aGlsZSAoIXBhaXJpbmdoZWFwX2lzX2VtcHR5KFcpKQogCXsKLS0gCjIuNDYuMAoK
--0000000000006cb83906216bdad2--