From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Dmitry Antipov Newsgroups: gmane.emacs.devel Subject: Re: Proposal: block-based vector allocator Date: Sun, 11 Dec 2011 17:18:09 +0400 Message-ID: <4EE4AD91.7070006@yandex.ru> References: <4EDDA68B.5050601@yandex.ru> <4EDE315E.3030804@yandex.ru> <4EDEF421.6090800@yandex.ru> <4EDF8F8E.8050401@yandex.ru> <87hb1b25i7.fsf@uwakimon.sk.tsukuba.ac.jp> <4EE03FFD.1090400@yandex.ru> <4EE0EA5C.1090505@yandex.ru> <4EE1CF09.70700@yandex.ru> <4EE23422.3050008@yandex.ru> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------080704070003030301020203" X-Trace: dough.gmane.org 1323609500 32176 80.91.229.12 (11 Dec 2011 13:18:20 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 11 Dec 2011 13:18:20 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Dec 11 14:18:15 2011 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([140.186.70.17]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1RZjID-0006yn-TS for ged-emacs-devel@m.gmane.org; Sun, 11 Dec 2011 14:18:14 +0100 Original-Received: from localhost ([::1]:41553 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RZjID-0001Na-07 for ged-emacs-devel@m.gmane.org; Sun, 11 Dec 2011 08:18:13 -0500 Original-Received: from eggs.gnu.org ([140.186.70.92]:51664) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RZjI9-0001NV-UG for emacs-devel@gnu.org; Sun, 11 Dec 2011 08:18:11 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1RZjI7-0004PC-2a for emacs-devel@gnu.org; Sun, 11 Dec 2011 08:18:09 -0500 Original-Received: from mail.dev.rtsoft.ru ([213.79.90.226]:56624) by eggs.gnu.org with smtp (Exim 4.71) (envelope-from ) id 1RZjI6-0004Or-7X for emacs-devel@gnu.org; Sun, 11 Dec 2011 08:18:07 -0500 Original-Received: (qmail 3020 invoked from network); 11 Dec 2011 13:18:02 -0000 Original-Received: from unknown (HELO ?192.168.5.146?) (192.168.1.70) by 0 with SMTP; 11 Dec 2011 13:18:02 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:8.0) Gecko/20111115 Thunderbird/8.0 In-Reply-To: X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6, seldom 2.4 (older, 4) X-Received-From: 213.79.90.226 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:146646 Archived-At: This is a multi-part message in MIME format. --------------080704070003030301020203 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit On 12/10/2011 01:04 AM, Stefan Monnier wrote: > BTW, your code seems to compute the free list index by dividing by > word_size (= 4 on 32bit systems) rather than by 8, so half of the slots > will always be unused, IIUC. You're correct, and this is fixed. > Let us how it turns out. It needs to be run again since I introduced some fixes, including those that suggested by you. > If it's an arbitrary choice, it should not be called "page_size" but > "vector_block_size" or some such. Otherwise, we should fetch its value > from the OS. Better name is OK (old one was a trace of mmap()-related experiments :-). > Where do you make use of this alignment? Not needed any more. > This test looks dangerous (we if we allocate a large vector of this > size?). It's impossible because VECTOR_BLOCK_BYTES is 'exact-fit' for the largest possible block-allocated vector. That's why I'm using xmalloc/mem_insert and not lisp_malloc: VECTOR_BLOCK_SIZE bytes are allocated for the block, but only block->data..block->data + VECTOR_BLOCK_BYTES range is marked as vector memory within mem_node tree. So, any MEM_TYPE_VECTORLIKE mem_node with VECTOR_BLOCK_BYTES size memory range is guaranteed to match the vector block, and this vector block may contain the only vector of VECTOR_BLOCK_BYTES bytes size. > Hmm... I didn't think of it, but this is a disadvantage of > non-segregated blocks: during conservative scanning, you need to scan > the vector block to determine if we really have a live_vector_p whereas > segregated blocks would just divide the offset by the block's > vector size. Yes, but this linear scan may be optimized: 1) scan is required only if examined pointer is less than block bump allocation pointer; 2) scan should not look at addresses beyond examined pointer. > For small enough vector blocks, it's probably not a big deal, but for > 10-slot vectors on 32bit systems with 4KB blocks, that's about > 100 iterations. This is a worst-case scenario when it's needed to scan up to the end of vector block, and the block is full of small vectors. Although the most vectors are small, small vectors usually allocated and died (becomes unreachable) in groups, and such a group of adjacent died vectors is a subject for coalescing, which reduces the number of vectors in the block. For the byte-compile benchmark, this loop does ~12 iterations on the average (for 64-bit code; expect larger value for 32-bit since average vector size is ~2x smaller). BTW, what do you think about hooking buffer allocation into common vector allocation code? I found it controversial (buffers are mid-sized vector-like objects, so it might be reasonable to generalize buffer allocation with other vectors; on the other side, buffers needs special treatment for liveness detection and special processing during sweep), but want to try anyway. Dmitry --------------080704070003030301020203 Content-Type: text/plain; name="vector_alloc.patch" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="vector_alloc.patch" PT09IG1vZGlmaWVkIGZpbGUgJ3NyYy9hbGxvYy5jJwotLS0gc3JjL2FsbG9jLmMJMjAxMS0x MS0yMCAwMzowNzowMiArMDAwMAorKysgc3JjL2FsbG9jLmMJMjAxMS0xMi0xMSAxMDoxNTox MSArMDAwMApAQCAtMjEsNyArMjEsNyBAQAogI2luY2x1ZGUgPHN0ZGlvLmg+CiAjaW5jbHVk ZSA8bGltaXRzLmg+CQkvKiBGb3IgQ0hBUl9CSVQuICAqLwogI2luY2x1ZGUgPHNldGptcC5o PgotCisjaW5jbHVkZSA8c3lzL3BhcmFtLmg+CQkvKiBGb3Igcm91bmR1cC4gICovCiAjaW5j bHVkZSA8c2lnbmFsLmg+CiAKICNpZmRlZiBIQVZFX1BUSFJFQUQKQEAgLTI4OTYsMTcgKzI4 OTYsMzA5IEBACiAJCQkgICBWZWN0b3IgQWxsb2NhdGlvbgogICoqKioqKioqKioqKioqKioq KioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioq LwogCi0vKiBTaW5nbHktbGlua2VkIGxpc3Qgb2YgYWxsIHZlY3RvcnMuICAqLwotCi1zdGF0 aWMgc3RydWN0IExpc3BfVmVjdG9yICphbGxfdmVjdG9yczsKKyNkZWZpbmUgVkVDVE9SX0JM T0NLX1NJWkUgKDQwOTYpCiAKIC8qIEhhbmR5IGNvbnN0YW50cyBmb3IgdmVjdG9ybGlrZSBv YmplY3RzLiAgKi8KIGVudW0KICAgewogICAgIGhlYWRlcl9zaXplID0gb2Zmc2V0b2YgKHN0 cnVjdCBMaXNwX1ZlY3RvciwgY29udGVudHMpLAotICAgIHdvcmRfc2l6ZSA9IHNpemVvZiAo TGlzcF9PYmplY3QpCisgICAgd29yZF9zaXplID0gc2l6ZW9mIChMaXNwX09iamVjdCksCisg ICAgcm91bmR1cF9zaXplID0gOAogICB9OwogCisvKiBPbmUgcG9pbnRlciBpcyBtYWxsb2Mg b3ZlcmhlYWQsIG90aGVycyBhcmUgQlVNUCBhbmQgTkVYVCBmaWVsZHMgb2Ygc3RydWN0Cisg ICB2ZWN0b3JfYmxvY2suICBSb3VuZGluZyBoZWxwcyB0byBtYWludGFpbiBhbGlnbm1lbnQg Y29uc3RyYWludHMuICAqLworCisjZGVmaW5lIFZFQ1RPUl9CTE9DS19CWVRFUyBcCisgIChW RUNUT1JfQkxPQ0tfU0laRSAtIHJvdW5kdXAgKDMgKiBzaXplb2YgKHZvaWQgKiksIHJvdW5k dXBfc2l6ZSkpCisKKy8qIE1heGltdW0gYW1vdW50IG9mIHZlY3RvcnMgYWxsb2NhdGVkIGZy b20gdGhlIHZlY3RvciBibG9jay4gICovCisKKyNkZWZpbmUgVkVDVE9SU19QRVJfQkxPQ0tf TUFYIFwKKyAgKFZFQ1RPUl9CTE9DS19CWVRFUyAvIHNpemVvZiAoc3RydWN0IHZlY3Rvcmxp a2VfaGVhZGVyKSkKKworLyogRnJlZSBsaXN0cyBmb3IgYWxsIHBvc3NpYmxlIGJsb2NrLWFs bG9jYXRlZCB2ZWN0b3JzLiAgKi8KKworI2RlZmluZSBWRUNUT1JfRlJFRV9MSVNUUyAoKFZF Q1RPUl9CTE9DS19CWVRFUyAvIHJvdW5kdXBfc2l6ZSkgKyAxKQorCisvKiBXaGVuIHRoZSB2 ZWN0b3IgaXMgb24gYSBmcmVlIGxpc3QsIHZlY3Rvcmxpa2VfaGVhZGVyLlNJWkUgaXMgc2V0 IHRvCisgICB0aGlzIHNwZWNpYWwgdmFsdWUgT1JlZCB3aXRoIHZlY3RvcidzIG1lbW9yeSBm b290cHJpbnQgc2l6ZS4gICovCisKKyNkZWZpbmUgVkVDVE9SX0ZSRUVfTElTVF9TSVpFIFwK KyAgKCgoRU1BQ1NfSU5UKSB+MCkgJiB+KEFSUkFZX01BUktfRkxBRyB8IFBTRVVET1ZFQ1RP Ul9GTEFHIHwgXAorCQkJKFZFQ1RPUl9CTE9DS19TSVpFIC0gMSkpKQorCisvKiBDb21tb24g c2hvcnRjdXQgdG8gYWR2YW5jZSB2ZWN0b3IgcG9pbnRlciBvdmVyIGEgYmxvY2sgZGF0YS4g ICovCisKKyNkZWZpbmUgQURWQU5DRSh2LG5ieXRlcykgXAorICAoc3RydWN0IExpc3BfVmVj dG9yICopICgodW5zaWduZWQgY2hhciAqKSAodikgKyAobmJ5dGVzKSkKKworLyogQ29tbW9u IHNob3J0Y3V0IHRvIHNldHVwIHZlY3RvciBvbiBhIGZyZWUgbGlzdC4gICovCisKKyNkZWZp bmUgU0VUVVBfT05fRlJFRV9MSVNUKHYsbmJ5dGVzLGluZGV4KSBkbyB7IFwKKyAgKHYpLT5o ZWFkZXIuc2l6ZSA9IFZFQ1RPUl9GUkVFX0xJU1RfU0laRSB8IChuYnl0ZXMpOyBcCisgIGVh c3NlcnQgKChuYnl0ZXMpICUgcm91bmR1cF9zaXplID09IDApOyBcCisgIChpbmRleCkgPSAo bmJ5dGVzKSAvIHJvdW5kdXBfc2l6ZTsgXAorICBlYXNzZXJ0ICgoaW5kZXgpIDwgVkVDVE9S X0ZSRUVfTElTVFMpOyBcCisgICh2KS0+aGVhZGVyLm5leHQudmVjdG9yID0gdmVjdG9yX2Zy ZWVfbGlzdHNbKGluZGV4KV07IFwKKyAgdmVjdG9yX2ZyZWVfbGlzdHNbKGluZGV4KV0gPSAo dik7IH0gd2hpbGUgKDApCisKK3N0cnVjdCB2ZWN0b3JfYmxvY2sKK3sKKyAgdW5zaWduZWQg Y2hhciBkYXRhW1ZFQ1RPUl9CTE9DS19CWVRFU107CisgIHVuc2lnbmVkIGNoYXIgKmJ1bXA7 CisgIHN0cnVjdCB2ZWN0b3JfYmxvY2sgKm5leHQ7Cit9OworCisvKiBDdXJyZW50IHZlY3Rv ciBibG9jay4gICovCisKK3N0YXRpYyBzdHJ1Y3QgdmVjdG9yX2Jsb2NrICp2ZWN0b3JfYmxv Y2s7CisKKy8qIFZlY3RvciBmcmVlIGxpc3RzLCB3aGVyZSBOVEggaXRlbSBwb2ludHMgdG8g YSBjaGFpbgorICAgb2YgZnJlZSB2ZWN0b3JzIG9mIE5USCAqIFJPVU5EVVBfU0laRSBieXRl cy4gICovCisKK3N0YXRpYyBzdHJ1Y3QgTGlzcF9WZWN0b3IgKnZlY3Rvcl9mcmVlX2xpc3Rz W1ZFQ1RPUl9GUkVFX0xJU1RTXTsKKworLyogU2luZ2x5LWxpbmtlZCBsaXN0IG9mIGxhcmdl IHZlY3RvcnMuICAqLworCitzdGF0aWMgc3RydWN0IExpc3BfVmVjdG9yICpsYXJnZV92ZWN0 b3JzOworCisvKiBHZXQgYSBuZXcgdmVjdG9yIGJsb2NrLiAgKi8KKworc3RhdGljIHN0cnVj dCB2ZWN0b3JfYmxvY2sgKgorYWxsb2NhdGVfdmVjdG9yX2Jsb2NrICh2b2lkKQoreworICBz dHJ1Y3QgdmVjdG9yX2Jsb2NrICpibG9jazsKKworI2lmZGVmIERPVUdfTEVBX01BTExPQwor ICBtYWxsb3B0IChNX01NQVBfTUFYLCAwKTsKKyNlbmRpZgorCisgIGJsb2NrID0geG1hbGxv YyAoVkVDVE9SX0JMT0NLX1NJWkUpOworICBpZiAoIWJsb2NrKQorICAgIG1lbW9yeV9mdWxs IChWRUNUT1JfQkxPQ0tfU0laRSk7CisKKyNpZmRlZiBET1VHX0xFQV9NQUxMT0MKKyAgbWFs bG9wdCAoTV9NTUFQX01BWCwgTU1BUF9NQVhfQVJFQVMpOworI2VuZGlmCisKKyNpZiBHQ19N QVJLX1NUQUNLICYmICFkZWZpbmVkIEdDX01BTExPQ19DSEVDSworICBtZW1faW5zZXJ0IChi bG9jay0+ZGF0YSwgYmxvY2stPmRhdGEgKyBWRUNUT1JfQkxPQ0tfQllURVMsCisJICAgICAg TUVNX1RZUEVfVkVDVE9STElLRSk7CisjZW5kaWYKKworICBibG9jay0+YnVtcCA9IGJsb2Nr LT5kYXRhOworICBibG9jay0+bmV4dCA9IHZlY3Rvcl9ibG9jazsKKyAgdmVjdG9yX2Jsb2Nr ID0gYmxvY2s7CisgIHJldHVybiBibG9jazsKK30KKworLyogQ2FsbGVkIG9uY2UgdG8gaW5p dGlhbGl6ZSB2ZWN0b3IgYWxsb2NhdGlvbi4gICovCisKK3N0YXRpYyB2b2lkCitpbml0X3Zl Y3RvcnMgKHZvaWQpCit7CisgIGludCBpOworCisgIGxhcmdlX3ZlY3RvcnMgPSBOVUxMOwor ICB2ZWN0b3JfYmxvY2sgPSBhbGxvY2F0ZV92ZWN0b3JfYmxvY2sgKCk7CisKKyAgZm9yIChp ID0gMDsgaSA8IFZFQ1RPUl9GUkVFX0xJU1RTOyBpKyspCisgICAgdmVjdG9yX2ZyZWVfbGlz dHNbaV0gPSBOVUxMOworfQorCisvKiBBbGxvY2F0ZSB2ZWN0b3IgZnJvbSB0aGUgdmVjdG9y IGJsb2NrLiAgKi8KKworc3RhdGljIHN0cnVjdCBMaXNwX1ZlY3RvciAqCithbGxvY2F0ZV92 ZWN0b3JfZnJvbV9ibG9jayAoc2l6ZV90IG5ieXRlcykKK3sKKyAgc3RydWN0IExpc3BfVmVj dG9yICp2ZWN0b3I7CisgIHN0cnVjdCB2ZWN0b3JfYmxvY2sgKmJsb2NrOworICBzaXplX3Qg aW5kZXgsIHJlc3RieXRlczsKKworICAvKiBWZWN0b3Igd2l0aCAwIHNsb3RzIGZvciBMaXNw X09iamVjdHMgaXMgYWxsb3dlZC4gICovCisgIGVhc3NlcnQgKG5ieXRlcyA+PSBzaXplb2Yg KHN0cnVjdCB2ZWN0b3JsaWtlX2hlYWRlcikgJiYKKwkgICBuYnl0ZXMgPD0gVkVDVE9SX0JM T0NLX0JZVEVTKTsKKyAgZWFzc2VydCAobmJ5dGVzICUgcm91bmR1cF9zaXplID09IDApOwor ICBlYXNzZXJ0ICh2ZWN0b3JfYmxvY2sgIT0gTlVMTCk7CisKKyAgLyogRmlyc3QsIHRyeSB0 byBhbGxvY2F0ZSBmcm9tIGEgZnJlZSBsaXN0CisgICAgIGNvbnRhaW5zIHZlY3RvcnMgb2Yg dGhlIHJlcXVlc3RlZCBzaXplLiAgKi8KKyAgaW5kZXggPSBuYnl0ZXMgLyByb3VuZHVwX3Np emU7CisgIGlmICh2ZWN0b3JfZnJlZV9saXN0c1tpbmRleF0pCisgICAgeworICAgICAgdmVj dG9yID0gdmVjdG9yX2ZyZWVfbGlzdHNbaW5kZXhdOworICAgICAgdmVjdG9yX2ZyZWVfbGlz dHNbaW5kZXhdID0gdmVjdG9yLT5oZWFkZXIubmV4dC52ZWN0b3I7CisgICAgICB2ZWN0b3It PmhlYWRlci5uZXh0Lm5ieXRlcyA9IG5ieXRlczsKKyAgICAgIHJldHVybiB2ZWN0b3I7Cisg ICAgfQorCisgIC8qIE5leHQsIGNoZWNrIGZyZWUgbGlzdHMgY29udGFpbnMgbGFyZ2VyIHZl Y3RvcnMuICAqLworICBmb3IgKGluZGV4ID0gKG5ieXRlcyArIHNpemVvZiAoc3RydWN0IExp c3BfVmVjdG9yKSkgLyByb3VuZHVwX3NpemU7CisgICAgICAgaW5kZXggPCBWRUNUT1JfRlJF RV9MSVNUUzsgaW5kZXgrKykKKyAgICBpZiAodmVjdG9yX2ZyZWVfbGlzdHNbaW5kZXhdKQor ICAgICAgeworCXN0cnVjdCBMaXNwX1ZlY3RvciAqcmVzdDsKKworCS8qIFRoaXMgdmVjdG9y IGlzIGxhcmdlciB0aGFuIGl0IHdhcyByZXF1ZXN0ZWQuICAqLworCXZlY3RvciA9IHZlY3Rv cl9mcmVlX2xpc3RzW2luZGV4XTsKKwl2ZWN0b3JfZnJlZV9saXN0c1tpbmRleF0gPSB2ZWN0 b3ItPmhlYWRlci5uZXh0LnZlY3RvcjsKKwl2ZWN0b3ItPmhlYWRlci5uZXh0Lm5ieXRlcyA9 IG5ieXRlczsKKworCS8qIEV4Y2Vzc2l2ZSBieXRlcyBhcmUgdXNlZCBmb3IgdGhlIHNtYWxs ZXIgdmVjdG9yLAorCSAgIHdoaWNoIHNob3VsZCBiZSBzZXQgb24gYW4gYXBwcm9wcmlhdGUg ZnJlZSBsaXN0LiAgKi8KKwlyZXN0Ynl0ZXMgPSBpbmRleCAqIHJvdW5kdXBfc2l6ZSAtIG5i eXRlczsKKwllYXNzZXJ0IChyZXN0Ynl0ZXMgJSByb3VuZHVwX3NpemUgPT0gMCk7CisJcmVz dCA9IEFEVkFOQ0UgKHZlY3RvciwgbmJ5dGVzKTsKKwlTRVRVUF9PTl9GUkVFX0xJU1QgKHJl c3QsIHJlc3RieXRlcywgaW5kZXgpOworCXJldHVybiB2ZWN0b3I7CisgICAgICB9CisKKyAg LyogTmV4dCwgdHJ5IHRvIGFsbG9jYXRlIGZyb20gY3VycmVudCB2ZWN0b3IgYmxvY2suICAq LworICByZXN0Ynl0ZXMgPSB2ZWN0b3JfYmxvY2stPmRhdGEgKyBWRUNUT1JfQkxPQ0tfQllU RVMgLSB2ZWN0b3JfYmxvY2stPmJ1bXA7CisgIGlmIChuYnl0ZXMgPiByZXN0Ynl0ZXMpCisg ICAgeworICAgICAgLyogQ3VycmVudCBibG9jaydzIGZyZWUgc3BhY2UgaXNuJ3QgZW5vdWdo Li4uICAqLworICAgICAgaWYgKHJlc3RieXRlcyA+PSBzaXplb2YgKHN0cnVjdCBMaXNwX1Zl Y3RvcikpCisJeworCSAgLyogLi4uYnV0IGl0J3MgZW5vdWdoIHRvIGFsbG9jYXRlIHNtYWxs ZXIgdmVjdG9yLAorCSAgICAgd2hpY2ggc2hvdWxkIGJlIHNldCBvbiBhbiBhcHByb3ByaWF0 ZSBmcmVlIGxpc3QuICAqLworCSAgZWFzc2VydCAocmVzdGJ5dGVzICUgcm91bmR1cF9zaXpl ID09IDApOworCSAgdmVjdG9yID0gKHN0cnVjdCBMaXNwX1ZlY3RvciAqKSB2ZWN0b3JfYmxv Y2stPmJ1bXA7CisJICB2ZWN0b3JfYmxvY2stPmJ1bXAgKz0gcmVzdGJ5dGVzOworCSAgU0VU VVBfT05fRlJFRV9MSVNUICh2ZWN0b3IsIHJlc3RieXRlcywgaW5kZXgpOworCX0KKyAgICAg IC8qIEFueXdheSwgbmVlZCBhIG5ldyB2ZWN0b3IgYmxvY2suICAqLworICAgICAgYmxvY2sg PSBhbGxvY2F0ZV92ZWN0b3JfYmxvY2sgKCk7CisgICAgfQorICBlbHNlCisgICAgLyogQWxs b2NhdGUgZnJvbSBjdXJyZW50IHZlY3RvciBibG9jay4gICovCisgICAgYmxvY2sgPSB2ZWN0 b3JfYmxvY2s7CisKKyAgLyogQnVtcCBwb2ludGVyIGFsbG9jYXRpb24gZnJvbSBjdXJyZW50 IHZlY3RvciBibG9jay4gICovCisgIHZlY3RvciA9IChzdHJ1Y3QgTGlzcF9WZWN0b3IgKikg YmxvY2stPmJ1bXA7CisgIGJsb2NrLT5idW1wICs9IG5ieXRlczsKKyAgdmVjdG9yLT5oZWFk ZXIubmV4dC5uYnl0ZXMgPSBuYnl0ZXM7CisgIHJldHVybiB2ZWN0b3I7Cit9CisKKy8qIFJl dHVybiBhbW91bnQgb2YgTGlzcF9PYmplY3RzIGNhbiBiZSBzdG9yZWQgaW4gdGhhdCB2ZWN0 b3IuICAqLworCisjZGVmaW5lIFZFQ1RPUl9TSVpFKHYpICgodiktPmhlYWRlci5zaXplICYg UFNFVURPVkVDVE9SX0ZMQUcgPyBcCisgIChQU0VVRE9WRUNUT1JfU0laRV9NQVNLICYgKHYp LT5oZWFkZXIuc2l6ZSkgOiAodiktPmhlYWRlci5zaXplKQorCisvKiBSZWNsYWltIHNwYWNl IHVzZWQgYnkgdW5tYXJrZWQgdmVjdG9ycy4gICovCisKK3N0YXRpYyB2b2lkCitzd2VlcF92 ZWN0b3JzICh2b2lkKQoreworICBzdHJ1Y3QgdmVjdG9yX2Jsb2NrICpibG9jayA9IHZlY3Rv cl9ibG9jaywgKmJwcmV2ID0gTlVMTCwgKmJuZXh0OworICBzdHJ1Y3QgTGlzcF9WZWN0b3Ig KnZlY3RvciwgKnByZXYsICpuZXh0OworICBpbnQgaTsKKworICB0b3RhbF92ZWN0b3Jfc2l6 ZSA9IDA7CisgIGZvciAoaSA9IDA7IGkgPCBWRUNUT1JfRlJFRV9MSVNUUzsgaSsrKQorICAg IHZlY3Rvcl9mcmVlX2xpc3RzW2ldID0gTlVMTDsKKworICAvKiBMb29raW5nIHRocm91Z2gg dmVjdG9yIGJsb2Nrcy4gICovCisKKyAgd2hpbGUgKGJsb2NrKQorICAgIHsKKyAgICAgIHN0 cnVjdCBMaXNwX1ZlY3RvciAqZnJlZV92ZWN0b3JzW1ZFQ1RPUlNfUEVSX0JMT0NLX01BWF07 CisgICAgICBpbnQgaW5kZXgsIHVzZWQ7CisKKyAgICAgIGZvciAoaW5kZXggPSAwLCB1c2Vk ID0gMCwgdmVjdG9yID0gKHN0cnVjdCBMaXNwX1ZlY3RvciAqKSBibG9jay0+ZGF0YTsKKwkg ICAodW5zaWduZWQgY2hhciAqKSB2ZWN0b3IgPCBibG9jay0+YnVtcDsgdmVjdG9yID0gbmV4 dCkKKwl7CisJICBpZiAoVkVDVE9SX01BUktFRF9QICh2ZWN0b3IpKQorCSAgICB7CisJICAg ICAgVkVDVE9SX1VOTUFSSyAodmVjdG9yKSwgdXNlZCA9IDE7CisJICAgICAgdG90YWxfdmVj dG9yX3NpemUgKz0gVkVDVE9SX1NJWkUgKHZlY3Rvcik7CisJICAgICAgbmV4dCA9IEFEVkFO Q0UgKHZlY3RvciwgdmVjdG9yLT5oZWFkZXIubmV4dC5uYnl0ZXMpOworCSAgICB9CisJICBl bHNlCisJICAgIHsKKwkgICAgICBFTUFDU19JTlQgbmJ5dGVzOworCisJICAgICAgaWYgKCh2 ZWN0b3ItPmhlYWRlci5zaXplICYgVkVDVE9SX0ZSRUVfTElTVF9TSVpFKSA9PSAKKwkJICBW RUNUT1JfRlJFRV9MSVNUX1NJWkUpCisJCXZlY3Rvci0+aGVhZGVyLm5leHQubmJ5dGVzID0K KwkJICB2ZWN0b3ItPmhlYWRlci5zaXplICYgKFZFQ1RPUl9CTE9DS19TSVpFIC0gMSk7CisJ ICAgICAgCisJICAgICAgbmV4dCA9IEFEVkFOQ0UgKHZlY3RvciwgdmVjdG9yLT5oZWFkZXIu bmV4dC5uYnl0ZXMpOworCisJICAgICAgLyogV2hpbGUgTkVYVCBpcyBub3QgbWFya2VkLCB0 cnkgdG8gY29hbGVzY2Ugd2l0aCBWRUNUT1IsCisJCSB0aHVzIG1ha2luZyBWRUNUT1Igb2Yg dGhlIGxhcmdlc3QgcG9zc2libGUgc2l6ZS4gICovCisKKwkgICAgICB3aGlsZSAoKHVuc2ln bmVkIGNoYXIgKikgbmV4dCA8IGJsb2NrLT5idW1wKQorCQl7CisJCSAgaWYgKFZFQ1RPUl9N QVJLRURfUCAobmV4dCkpCisJCSAgICBicmVhazsKKwkJICBpZiAoKG5leHQtPmhlYWRlci5z aXplICYgVkVDVE9SX0ZSRUVfTElTVF9TSVpFKSA9PSAKKwkJICAgICAgVkVDVE9SX0ZSRUVf TElTVF9TSVpFKQorCQkgICAgbmJ5dGVzID0gbmV4dC0+aGVhZGVyLnNpemUgJiAoVkVDVE9S X0JMT0NLX1NJWkUgLSAxKTsKKwkJICBlbHNlCisJCSAgICBuYnl0ZXMgPSBuZXh0LT5oZWFk ZXIubmV4dC5uYnl0ZXM7CisJCSAgdmVjdG9yLT5oZWFkZXIubmV4dC5uYnl0ZXMgKz0gbmJ5 dGVzOworCQkgIG5leHQgPSBBRFZBTkNFIChuZXh0LCBuYnl0ZXMpOworCQl9CisJICAgICAg CisJICAgICAgLyogQ29sbGVjdCBhIHBvaW50ZXIgdG8gcmVzdWx0aW5nIHZlY3Rvci4gICov CisJICAgICAgZWFzc2VydCAoaW5kZXggPCBWRUNUT1JTX1BFUl9CTE9DS19NQVgpOworCSAg ICAgIGZyZWVfdmVjdG9yc1tpbmRleCsrXSA9IHZlY3RvcjsKKwkgICAgfQorCX0KKworICAg ICAgaWYgKHVzZWQpCisJeworCSAgLyogU2V0dXAgY29sbGVjdGVkIHZlY3RvcnMgb24gYSBm cmVlIGxpc3RzLiAgKi8KKwkgIHdoaWxlICgtLWluZGV4ID49IDApCisJICAgIHsKKwkgICAg ICB2ZWN0b3IgPSBmcmVlX3ZlY3RvcnNbaW5kZXhdOworCSAgICAgIGVhc3NlcnQgKHZlY3Rv ci0+aGVhZGVyLm5leHQubmJ5dGVzICUgcm91bmR1cF9zaXplID09IDApOworCSAgICAgIFNF VFVQX09OX0ZSRUVfTElTVCAodmVjdG9yLCB2ZWN0b3ItPmhlYWRlci5uZXh0Lm5ieXRlcywg aSk7CisJICAgIH0KKwkgIGJwcmV2ID0gYmxvY2ssIGJsb2NrID0gYmxvY2stPm5leHQ7CisJ fQorICAgICAgZWxzZQorCXsKKwkgIC8qIE5vdGhpbmcgdXNlZCBpbiB0aGlzIGJsb2NrLiAg Ki8KKwkgIGlmIChicHJldikKKwkgICAgYnByZXYtPm5leHQgPSBibG9jay0+bmV4dDsKKwkg IGVsc2UKKwkgICAgdmVjdG9yX2Jsb2NrID0gYmxvY2stPm5leHQ7CisJICBibmV4dCA9IGJs b2NrLT5uZXh0OworI2lmIEdDX01BUktfU1RBQ0sgJiYgIWRlZmluZWQgR0NfTUFMTE9DX0NI RUNLCisJICBtZW1fZGVsZXRlIChtZW1fZmluZCAoYmxvY2stPmRhdGEpKTsKKyNlbmRpZgor CSAgeGZyZWUgKGJsb2NrKTsKKwkgIGJsb2NrID0gYm5leHQ7CisJfQorICAgIH0KKworICAv KiBTd2VlcCBsYXJnZSB2ZWN0b3JzLiAgKi8KKworICB2ZWN0b3IgPSBsYXJnZV92ZWN0b3Jz LCBwcmV2ID0gTlVMTDsKKworICB3aGlsZSAodmVjdG9yKQorICAgIGlmIChWRUNUT1JfTUFS S0VEX1AgKHZlY3RvcikpCisgICAgICB7CisJVkVDVE9SX1VOTUFSSyAodmVjdG9yKTsKKwl0 b3RhbF92ZWN0b3Jfc2l6ZSArPSBWRUNUT1JfU0laRSAodmVjdG9yKTsKKwlwcmV2ID0gdmVj dG9yLCB2ZWN0b3IgPSB2ZWN0b3ItPmhlYWRlci5uZXh0LnZlY3RvcjsKKyAgICAgIH0KKyAg ICBlbHNlCisgICAgICB7CisJaWYgKHByZXYpCisJICBwcmV2LT5oZWFkZXIubmV4dCA9IHZl Y3Rvci0+aGVhZGVyLm5leHQ7CisJZWxzZQorCSAgbGFyZ2VfdmVjdG9ycyA9IHZlY3Rvci0+ aGVhZGVyLm5leHQudmVjdG9yOworCW5leHQgPSB2ZWN0b3ItPmhlYWRlci5uZXh0LnZlY3Rv cjsKKwlsaXNwX2ZyZWUgKHZlY3Rvcik7CisJdmVjdG9yID0gbmV4dDsKKyAgICAgIH0KK30K KwogLyogVmFsdWUgaXMgYSBwb2ludGVyIHRvIGEgbmV3bHkgYWxsb2NhdGVkIExpc3BfVmVj dG9yIHN0cnVjdHVyZQogICAgd2l0aCByb29tIGZvciBMRU4gTGlzcF9PYmplY3RzLiAgKi8K IApAQCAtMjkyOSw3ICszMjIxLDE1IEBACiAgIC8qIGVhc3NlcnQgKCFoYW5kbGluZ19zaWdu YWwpOyAqLwogCiAgIG5ieXRlcyA9IGhlYWRlcl9zaXplICsgbGVuICogd29yZF9zaXplOwot ICBwID0gKHN0cnVjdCBMaXNwX1ZlY3RvciAqKSBsaXNwX21hbGxvYyAobmJ5dGVzLCBNRU1f VFlQRV9WRUNUT1JMSUtFKTsKKyAgaWYgKG5ieXRlcyA+IFZFQ1RPUl9CTE9DS19CWVRFUykK KyAgICB7CisgICAgICBwID0gKHN0cnVjdCBMaXNwX1ZlY3RvciAqKSBsaXNwX21hbGxvYyAo bmJ5dGVzLCBNRU1fVFlQRV9WRUNUT1JMSUtFKTsKKyAgICAgIHAtPmhlYWRlci5uZXh0LnZl Y3RvciA9IGxhcmdlX3ZlY3RvcnM7CisgICAgICBsYXJnZV92ZWN0b3JzID0gcDsKKyAgICB9 CisgIGVsc2UKKyAgICAvKiBSb3VuZGluZyBpcyBmb3IgMzItYml0IGNvZGUgdG8gcHJlc2Vy dmUgYWxpZ25tZW50LiAgKi8KKyAgICBwID0gYWxsb2NhdGVfdmVjdG9yX2Zyb21fYmxvY2sg KHJvdW5kdXAgKG5ieXRlcywgcm91bmR1cF9zaXplKSk7CiAKICNpZmRlZiBET1VHX0xFQV9N QUxMT0MKICAgLyogQmFjayB0byBhIHJlYXNvbmFibGUgbWF4aW11bSBvZiBtbWFwJ2VkIGFy ZWFzLiAgKi8KQEAgLTI5MzksOSArMzIzOSw2IEBACiAgIGNvbnNpbmdfc2luY2VfZ2MgKz0g bmJ5dGVzOwogICB2ZWN0b3JfY2VsbHNfY29uc2VkICs9IGxlbjsKIAotICBwLT5oZWFkZXIu bmV4dC52ZWN0b3IgPSBhbGxfdmVjdG9yczsKLSAgYWxsX3ZlY3RvcnMgPSBwOwotCiAgIE1B TExPQ19VTkJMT0NLX0lOUFVUOwogCiAgIHJldHVybiBwOwpAQCAtNDAxNiw3ICs0MzEzLDQx IEBACiBzdGF0aWMgaW5saW5lIGludAogbGl2ZV92ZWN0b3JfcCAoc3RydWN0IG1lbV9ub2Rl ICptLCB2b2lkICpwKQogewotICByZXR1cm4gKHAgPT0gbS0+c3RhcnQgJiYgbS0+dHlwZSA9 PSBNRU1fVFlQRV9WRUNUT1JMSUtFKTsKKyAgaWYgKG0tPnR5cGUgPT0gTUVNX1RZUEVfVkVD VE9STElLRSkKKyAgICB7CisgICAgICBpZiAobS0+ZW5kIC0gbS0+c3RhcnQgPT0gVkVDVE9S X0JMT0NLX0JZVEVTKQorCXsKKwkgIC8qIFRoaXMgbWVtb3J5IG5vZGUgY29ycmVzcG9uZHMg dG8gYSB2ZWN0b3IgYmxvY2suICAqLworCSAgc3RydWN0IHZlY3Rvcl9ibG9jayAqYmxvY2sg PSAoc3RydWN0IHZlY3Rvcl9ibG9jayAqKSBtLT5zdGFydDsKKworCSAgaWYgKHAgPCAodm9p ZCAqKSBibG9jay0+YnVtcCkKKwkgICAgeworCSAgICAgIHN0cnVjdCBMaXNwX1ZlY3RvciAq dmVjdG9yID0gKHN0cnVjdCBMaXNwX1ZlY3RvciAqKSBibG9jay0+ZGF0YTsKKworCSAgICAg IC8qIFAgaXMgaW4gdGhlIGJsb2NrJ3MgYWxsb2NhdGlvbiByYW5nZS4gU2NhbiB0aGUgYmxv Y2sKKwkJIHVwIHRvIFAgYW5kIHNlZSB3aGV0aGVyIFAgcG9pbnRzIHRvIHRoZSBzdGFydCBv ZiBzb21lCisJCSB2ZWN0b3Igd2hpY2ggaXMgbm90IG9uIGEgZnJlZSBsaXN0LiAgKi8KKwkg ICAgICB3aGlsZSAodmVjdG9yIDw9IChzdHJ1Y3QgTGlzcF9WZWN0b3IgKikgcCkKKwkJewor CQkgIGlmICgodmVjdG9yLT5oZWFkZXIuc2l6ZSAmIFZFQ1RPUl9GUkVFX0xJU1RfU0laRSkK KwkJICAgICAgPT0gVkVDVE9SX0ZSRUVfTElTVF9TSVpFKQorCQkgICAgdmVjdG9yID0gQURW QU5DRSAodmVjdG9yLCAodmVjdG9yLT5oZWFkZXIuc2l6ZSAmIAorCQkJCQkgICAgICAgKFZF Q1RPUl9CTE9DS19TSVpFIC0gMSkpKTsKKwkJICBlbHNlIGlmICh2ZWN0b3IgPT0gcCkKKwkJ ICAgIHJldHVybiAxOworCQkgIGVsc2UKKwkJICAgIHZlY3RvciA9IEFEVkFOQ0UgKHZlY3Rv ciwgdmVjdG9yLT5oZWFkZXIubmV4dC5uYnl0ZXMpOworCQl9CisJICAgIH0KKwl9CisgICAg ICBlbHNlCisJeworCSAgaWYgKHAgPT0gbS0+c3RhcnQpCisJICAgIC8qIFRoaXMgbWVtb3J5 IG5vZGUgY29ycmVzcG9uZHMgdG8gYSBsYXJnZSB2ZWN0b3IuICAqLworCSAgICByZXR1cm4g MTsKKwl9CisgICAgfQorICByZXR1cm4gMDsKIH0KIAogCkBAIC02MTY5LDMzICs2NTAwLDcg QEAKIAl9CiAgIH0KIAotICAvKiBGcmVlIGFsbCB1bm1hcmtlZCB2ZWN0b3JzICovCi0gIHsK LSAgICByZWdpc3RlciBzdHJ1Y3QgTGlzcF9WZWN0b3IgKnZlY3RvciA9IGFsbF92ZWN0b3Jz LCAqcHJldiA9IDAsICpuZXh0OwotICAgIHRvdGFsX3ZlY3Rvcl9zaXplID0gMDsKLQotICAg IHdoaWxlICh2ZWN0b3IpCi0gICAgICBpZiAoIVZFQ1RPUl9NQVJLRURfUCAodmVjdG9yKSkK LQl7Ci0JICBpZiAocHJldikKLQkgICAgcHJldi0+aGVhZGVyLm5leHQgPSB2ZWN0b3ItPmhl YWRlci5uZXh0OwotCSAgZWxzZQotCSAgICBhbGxfdmVjdG9ycyA9IHZlY3Rvci0+aGVhZGVy Lm5leHQudmVjdG9yOwotCSAgbmV4dCA9IHZlY3Rvci0+aGVhZGVyLm5leHQudmVjdG9yOwot CSAgbGlzcF9mcmVlICh2ZWN0b3IpOwotCSAgdmVjdG9yID0gbmV4dDsKLQotCX0KLSAgICAg IGVsc2UKLQl7Ci0JICBWRUNUT1JfVU5NQVJLICh2ZWN0b3IpOwotCSAgaWYgKHZlY3Rvci0+ aGVhZGVyLnNpemUgJiBQU0VVRE9WRUNUT1JfRkxBRykKLQkgICAgdG90YWxfdmVjdG9yX3Np emUgKz0gUFNFVURPVkVDVE9SX1NJWkVfTUFTSyAmIHZlY3Rvci0+aGVhZGVyLnNpemU7Ci0J ICBlbHNlCi0JICAgIHRvdGFsX3ZlY3Rvcl9zaXplICs9IHZlY3Rvci0+aGVhZGVyLnNpemU7 Ci0JICBwcmV2ID0gdmVjdG9yLCB2ZWN0b3IgPSB2ZWN0b3ItPmhlYWRlci5uZXh0LnZlY3Rv cjsKLQl9Ci0gIH0KKyAgc3dlZXBfdmVjdG9ycyAoKTsKIAogI2lmZGVmIEdDX0NIRUNLX1NU UklOR19CWVRFUwogICBpZiAoIW5vbmludGVyYWN0aXZlKQpAQCAtNjMzMSw3ICs2NjM2LDYg QEAKICAgVmRlYWQgPSBtYWtlX3B1cmVfc3RyaW5nICgiREVBRCIsIDQsIDQsIDApOwogI2Vu ZGlmCiAKLSAgYWxsX3ZlY3RvcnMgPSAwOwogICBpZ25vcmVfd2FybmluZ3MgPSAxOwogI2lm ZGVmIERPVUdfTEVBX01BTExPQwogICBtYWxsb3B0IChNX1RSSU1fVEhSRVNIT0xELCAxMjgq MTAyNCk7IC8qIHRyaW0gdGhyZXNob2xkICovCkBAIC02MzQ0LDYgKzY2NDgsNyBAQAogICBp bml0X21hcmtlciAoKTsKICAgaW5pdF9mbG9hdCAoKTsKICAgaW5pdF9pbnRlcnZhbHMgKCk7 CisgIGluaXRfdmVjdG9ycyAoKTsKICAgaW5pdF93ZWFrX2hhc2hfdGFibGVzICgpOwogCiAj aWZkZWYgUkVMX0FMTE9DCgo9PT0gbW9kaWZpZWQgZmlsZSAnc3JjL2xpc3AuaCcKLS0tIHNy Yy9saXNwLmgJMjAxMS0xMi0wNSAwMDoxNToxNSArMDAwMAorKysgc3JjL2xpc3AuaAkyMDEx LTEyLTA5IDExOjQ2OjE1ICswMDAwCkBAIC04NjgsMTIgKzg2OCwxNSBAQAogc3RydWN0IHZl Y3Rvcmxpa2VfaGVhZGVyCiAgIHsKICAgICBFTUFDU19JTlQgc2l6ZTsKLQotICAgIC8qIFBv aW50ZXIgdG8gdGhlIG5leHQgdmVjdG9yLWxpa2Ugb2JqZWN0LiAgSXQgaXMgZ2VuZXJhbGx5 IGEgYnVmZmVyIG9yIGEKKyAgICAvKiBXaGVuIHRoZSB2ZWN0b3IgaXMgYWxsb2NhdGVkIGZy b20gYSB2ZWN0b3IgYmxvY2ssIE5CWVRFUyBpcyB1c2VkCisgICAgICAgaWYgdGhlIHZlY3Rv ciBpcyBub3Qgb24gYSBmcmVlIGxpc3QsIGFuZCBWRUNUT1IgaXMgdXNlZCBvdGhlcndpc2Uu CisgICAgICAgRm9yIGxhcmdlIHZlY3Rvci1saWtlIG9iamVjdHMsIEJVRkZFUiBvciBWRUNU T1IgaXMgdXNlZCBhcyBhIHBvaW50ZXIKKyAgICAgICB0byB0aGUgbmV4dCB2ZWN0b3ItbGlr ZSBvYmplY3QuICBJdCBpcyBnZW5lcmFsbHkgYSBidWZmZXIgb3IgYSAKICAgICAgICBMaXNw X1ZlY3RvciBhbGlhcywgc28gZm9yIGNvbnZlbmllbmNlIGl0IGlzIGEgdW5pb24gaW5zdGVh ZCBvZiBhCiAgICAgICAgcG9pbnRlcjogdGhpcyB3YXksIG9uZSBjYW4gd3JpdGUgUC0+bmV4 dC52ZWN0b3IgaW5zdGVhZCBvZiAoKHN0cnVjdAogICAgICAgIExpc3BfVmVjdG9yICopIFAt Pm5leHQpLiAgKi8KICAgICB1bmlvbiB7CisgICAgICBFTUFDU19JTlQgbmJ5dGVzOwogICAg ICAgc3RydWN0IGJ1ZmZlciAqYnVmZmVyOwogICAgICAgc3RydWN0IExpc3BfVmVjdG9yICp2 ZWN0b3I7CiAgICAgfSBuZXh0OwoK --------------080704070003030301020203--