From mboxrd@z Thu Jan 1 00:00:00 1970 From: Praveen Kumar Subject: [PATCH v6 15/16 RESEND] rbtree: low level optimizations in rb_erase() Date: Tue, 21 Nov 2017 20:50:08 +0530 Message-ID: <20171121152009.15591-16-kpraveen.lkml@gmail.com> References: <20171121152009.15591-1-kpraveen.lkml@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: base64 Return-path: In-Reply-To: <20171121152009.15591-1-kpraveen.lkml@gmail.com> List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xen.org Sender: "Xen-devel" To: xen-devel@lists.xen.org Cc: sstabellini@kernel.org, wei.liu2@citrix.com, konrad.wilk@oracle.com, George.Dunlap@eu.citrix.com, andrew.cooper3@citrix.com, dario.faggioli@citrix.com, ian.jackson@eu.citrix.com, tim@xen.org, kpraveen.lkml@gmail.com, jbeulich@suse.com List-Id: xen-devel@lists.xenproject.org RnJvbTogTWljaGVsIExlc3BpbmFzc2UgPHdhbGtlbkBnb29nbGUuY29tPgoKVmFyaW91cyBtaW5v ciBvcHRpbWl6YXRpb25zIGluIHJiX2VyYXNlKCk6Ci0gQXZvaWQgbXVsdGlwbGUgbG9hZGluZyBv ZiBub2RlLT5fX3JiX3BhcmVudF9jb2xvciB3aGVuIGNvbXB1dGluZyBwYXJlbnQKICBhbmQgY29s b3IgaW5mb3JtYXRpb24gKHBvc3NpYmx5IG5vdCBpbiBjbG9zZSBzZXF1ZW5jZSwgYXMgdGhlcmUg bWlnaHQKICBiZSBmdXJ0aGVyIGJyYW5jaGVzIGluIHRoZSBhbGdvcml0aG0pCi0gSW4gdGhlIDEt Y2hpbGQgc3ViY2FzZSBvZiBjYXNlIDEsIGNvcHkgdGhlIF9fcmJfcGFyZW50X2NvbG9yIGZpZWxk IGZyb20KICB0aGUgZXJhc2VkIG5vZGUgdG8gdGhlIGNoaWxkIGluc3RlYWQgb2YgcmVjb21wdXRp bmcgaXQgZnJvbSB0aGUgZGVzaXJlZAogIHBhcmVudCBhbmQgY29sb3IKLSBXaGVuIHNlYXJjaGlu ZyBmb3IgdGhlIGVyYXNlZCBub2RlJ3Mgc3VjY2Vzc29yLCBkaWZmZXJlbnRpYXRlIGJldHdlZW4K ICBjYXNlcyAyIGFuZCAzIGJhc2VkIG9uIHdoZXRoZXIgYW55IGxlZnQgbGlua3Mgd2VyZSBmb2xs b3dlZC4gVGhpcyBhdm9pZHMKICBhIGNvbmRpdGlvbiBsYXRlciBkb3duLgotIEluIGNhc2UgMywg a2VlcCBhIHBvaW50ZXIgdG8gdGhlIGVyYXNlZCBub2RlJ3MgcmlnaHQgY2hpbGQgc28gd2UgZG9u J3QKICBoYXZlIHRvIHJlZmV0Y2ggaXQgbGF0ZXIgdG8gYWRqdXN0IGl0cyBwYXJlbnQuCi0gSW4g dGhlIG5vLWNoaWxkcyBzdWJjYXNlIG9mIGNhc2VzIDIgYW5kIDMsIHBsYWNlIHRoZSByZWJhbGFu Y2UgYXNzaWdtZW50CiAgbGFzdCBzbyB0aGF0IHRoZSBjb21waWxlciBjYW4gcmVtb3ZlIHRoZSBm b2xsb3dpbmcgaWYocmViYWxhbmNlKSB0ZXN0LgoKQWxzbywgYWRkZWQgc29tZSBjb21tZW50cyB0 byBpbGx1c3RyYXRlIGNhc2VzIDIgYW5kIDMuCgpTaWduZWQtb2ZmLWJ5OiBNaWNoZWwgTGVzcGlu YXNzZSA8d2Fsa2VuQGdvb2dsZS5jb20+CkFja2VkLWJ5OiBSaWsgdmFuIFJpZWwgPHJpZWxAcmVk aGF0LmNvbT4KQ2M6IFBldGVyIFppamxzdHJhIDxhLnAuemlqbHN0cmFAY2hlbGxvLm5sPgpDYzog QW5kcmVhIEFyY2FuZ2VsaSA8YWFyY2FuZ2VAcmVkaGF0LmNvbT4KQ2M6IERhdmlkIFdvb2Rob3Vz ZSA8ZHdtdzJAaW5mcmFkZWFkLm9yZz4KU2lnbmVkLW9mZi1ieTogQW5kcmV3IE1vcnRvbiA8YWtw bUBsaW51eC1mb3VuZGF0aW9uLm9yZz4KU2lnbmVkLW9mZi1ieTogTGludXMgVG9ydmFsZHMgPHRv cnZhbGRzQGxpbnV4LWZvdW5kYXRpb24ub3JnPgpbTGludXggY29tbWl0IDRmMDM1YWQ2N2Y0NjMz YzIzM2NiMzY0MjcxMWQ0OWI0ZWZjOWM4MmRdCgpQb3J0ZWQgdG8gWGVuLgoKU2lnbmVkLW9mZi1i eTogUHJhdmVlbiBLdW1hciA8a3ByYXZlZW4ubGttbEBnbWFpbC5jb20+Ci0tLQogeGVuL2NvbW1v bi9yYnRyZWUuYyB8IDk4ICsrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKystLS0tLS0t LS0tLS0tLS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgNjQgaW5zZXJ0aW9ucygrKSwgMzQgZGVsZXRp b25zKC0pCgpkaWZmIC0tZ2l0IGEveGVuL2NvbW1vbi9yYnRyZWUuYyBiL3hlbi9jb21tb24vcmJ0 cmVlLmMKaW5kZXggZTdkZjI3MzgwMC4uNWM0ZTIzOWMyNCAxMDA2NDQKLS0tIGEveGVuL2NvbW1v bi9yYnRyZWUuYworKysgYi94ZW4vY29tbW9uL3JidHJlZS5jCkBAIC00Nyw5ICs0NywxNCBAQAog I2RlZmluZQkJUkJfUkVECQkwCiAjZGVmaW5lCQlSQl9CTEFDSwkxCiAKLSNkZWZpbmUgcmJfY29s b3IocikgICAoKHIpLT5fX3JiX3BhcmVudF9jb2xvciAmIDEpCi0jZGVmaW5lIHJiX2lzX3JlZChy KSAgICghcmJfY29sb3IocikpCi0jZGVmaW5lIHJiX2lzX2JsYWNrKHIpIHJiX2NvbG9yKHIpCisj ZGVmaW5lIF9fcmJfcGFyZW50KHBjKSAgICAoKHN0cnVjdCByYl9ub2RlICopKHBjICYgfjMpKQor CisjZGVmaW5lIF9fcmJfY29sb3IocGMpICAgICAoKHBjKSAmIDEpCisjZGVmaW5lIF9fcmJfaXNf YmxhY2socGMpICBfX3JiX2NvbG9yKHBjKQorI2RlZmluZSBfX3JiX2lzX3JlZChwYykgICAgKCFf X3JiX2NvbG9yKHBjKSkKKyNkZWZpbmUgcmJfY29sb3IocmIpICAgICAgIF9fcmJfY29sb3IoKHJi KS0+X19yYl9wYXJlbnRfY29sb3IpCisjZGVmaW5lIHJiX2lzX3JlZChyYikgICAgICBfX3JiX2lz X3JlZCgocmIpLT5fX3JiX3BhcmVudF9jb2xvcikKKyNkZWZpbmUgcmJfaXNfYmxhY2socmIpICAg IF9fcmJfaXNfYmxhY2soKHJiKS0+X19yYl9wYXJlbnRfY29sb3IpCiAKIHN0YXRpYyBpbmxpbmUg dm9pZCByYl9zZXRfYmxhY2soc3RydWN0IHJiX25vZGUgKnJiKQogewpAQCAtMzc4LDYgKzM4Myw3 IEBAIHZvaWQgcmJfZXJhc2Uoc3RydWN0IHJiX25vZGUgKm5vZGUsIHN0cnVjdCByYl9yb290ICpy b290KQogewogCXN0cnVjdCByYl9ub2RlICpjaGlsZCA9IG5vZGUtPnJiX3JpZ2h0LCAqdG1wID0g bm9kZS0+cmJfbGVmdDsKIAlzdHJ1Y3QgcmJfbm9kZSAqcGFyZW50LCAqcmViYWxhbmNlOworCXVu c2lnbmVkIGxvbmcgcGM7CiAKIAlpZiAoIXRtcCkgewogCQkvKgpAQCAtMzg3LDUxICszOTMsNzUg QEAgdm9pZCByYl9lcmFzZShzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX3Jvb3QgKnJv b3QpCiAJCSAqIGFuZCBub2RlIG11c3QgYmUgYmxhY2sgZHVlIHRvIDQpLiBXZSBhZGp1c3QgY29s b3JzIGxvY2FsbHkKIAkJICogc28gYXMgdG8gYnlwYXNzIF9fcmJfZXJhc2VfY29sb3IoKSBsYXRl ciBvbi4KIAkJICovCi0KLQkJcGFyZW50ID0gcmJfcGFyZW50KG5vZGUpOworCQlwYyA9IG5vZGUt Pl9fcmJfcGFyZW50X2NvbG9yOworCQlwYXJlbnQgPSBfX3JiX3BhcmVudChwYyk7CiAJCV9fcmJf Y2hhbmdlX2NoaWxkKG5vZGUsIGNoaWxkLCBwYXJlbnQsIHJvb3QpOwogCQlpZiAoY2hpbGQpIHsK LQkJCXJiX3NldF9wYXJlbnRfY29sb3IoY2hpbGQsIHBhcmVudCwgUkJfQkxBQ0spOworCQkJY2hp bGQtPl9fcmJfcGFyZW50X2NvbG9yID0gcGM7CiAJCQlyZWJhbGFuY2UgPSBOVUxMOwotCQl9IGVs c2UgewotCQkJcmViYWxhbmNlID0gcmJfaXNfYmxhY2sobm9kZSkgPyBwYXJlbnQgOiBOVUxMOwot CQl9CisJCX0gZWxzZQorCQkJcmViYWxhbmNlID0gX19yYl9pc19ibGFjayhwYykgPyBwYXJlbnQg OiBOVUxMOwogCX0gZWxzZSBpZiAoIWNoaWxkKSB7CiAJCS8qIFN0aWxsIGNhc2UgMSwgYnV0IHRo aXMgdGltZSB0aGUgY2hpbGQgaXMgbm9kZS0+cmJfbGVmdCAqLwotCQlwYXJlbnQgPSByYl9wYXJl bnQobm9kZSk7CisJCXRtcC0+X19yYl9wYXJlbnRfY29sb3IgPSBwYyA9IG5vZGUtPl9fcmJfcGFy ZW50X2NvbG9yOworCQlwYXJlbnQgPSBfX3JiX3BhcmVudChwYyk7CiAJCV9fcmJfY2hhbmdlX2No aWxkKG5vZGUsIHRtcCwgcGFyZW50LCByb290KTsKLQkJcmJfc2V0X3BhcmVudF9jb2xvcih0bXAs IHBhcmVudCwgUkJfQkxBQ0spOwogCQlyZWJhbGFuY2UgPSBOVUxMOwogCX0gZWxzZSB7Ci0JCXN0 cnVjdCByYl9ub2RlICpvbGQgPSBub2RlLCAqbGVmdDsKLQotCQlub2RlID0gY2hpbGQ7Ci0JCXdo aWxlICgobGVmdCA9IG5vZGUtPnJiX2xlZnQpICE9IE5VTEwpCi0JCQlub2RlID0gbGVmdDsKLQot CQlfX3JiX2NoYW5nZV9jaGlsZChvbGQsIG5vZGUsIHJiX3BhcmVudChvbGQpLCByb290KTsKLQot CQljaGlsZCA9IG5vZGUtPnJiX3JpZ2h0OwotCQlwYXJlbnQgPSByYl9wYXJlbnQobm9kZSk7Ci0K LQkJaWYgKHBhcmVudCA9PSBvbGQpIHsKLQkJCXBhcmVudCA9IG5vZGU7CisJCXN0cnVjdCByYl9u b2RlICpzdWNjZXNzb3IgPSBjaGlsZCwgKmNoaWxkMjsKKwkJdG1wID0gY2hpbGQtPnJiX2xlZnQ7 CisJCWlmICghdG1wKSB7CisJCQkvKgorCQkJICogQ2FzZSAyOiBub2RlJ3Mgc3VjY2Vzc29yIGlz IGl0cyByaWdodCBjaGlsZAorCQkJICoKKwkJCSAqICAgIChuKSAgICAgICAgICAocykKKwkJCSAq ICAgIC8gXCAgICAgICAgICAvIFwKKwkJCSAqICAoeCkgKHMpICAtPiAgKHgpIChjKQorCQkJICog ICAgICAgIFwKKwkJCSAqICAgICAgICAoYykKKwkJCSAqLworCQkJcGFyZW50ID0gY2hpbGQ7CisJ CQljaGlsZDIgPSBjaGlsZC0+cmJfcmlnaHQ7CiAJCX0gZWxzZSB7Ci0JCQlwYXJlbnQtPnJiX2xl ZnQgPSBjaGlsZDsKLQotCQkJbm9kZS0+cmJfcmlnaHQgPSBvbGQtPnJiX3JpZ2h0OwotCQkJcmJf c2V0X3BhcmVudChvbGQtPnJiX3JpZ2h0LCBub2RlKTsKKwkJCS8qCisJCQkgKiBDYXNlIDM6IG5v ZGUncyBzdWNjZXNzb3IgaXMgbGVmdG1vc3QgdW5kZXIKKwkJCSAqIG5vZGUncyByaWdodCBjaGls ZCBzdWJ0cmVlCisJCQkgKgorCQkJICogICAgKG4pICAgICAgICAgIChzKQorCQkJICogICAgLyBc ICAgICAgICAgIC8gXAorCQkJICogICh4KSAoeSkgIC0+ICAoeCkgKHkpCisJCQkgKiAgICAgIC8g ICAgICAgICAgICAvCisJCQkgKiAgICAocCkgICAgICAgICAgKHApCisJCQkgKiAgICAvICAgICAg ICAgICAgLworCQkJICogIChzKSAgICAgICAgICAoYykKKwkJCSAqICAgIFwKKwkJCSAqICAgIChj KQorCQkJICovCisJCQlkbyB7CisJCQkJcGFyZW50ID0gc3VjY2Vzc29yOworCQkJCXN1Y2Nlc3Nv ciA9IHRtcDsKKwkJCQl0bXAgPSB0bXAtPnJiX2xlZnQ7CisJCQl9IHdoaWxlICh0bXApOworCQkJ cGFyZW50LT5yYl9sZWZ0ID0gY2hpbGQyID0gc3VjY2Vzc29yLT5yYl9yaWdodDsKKwkJCXN1Y2Nl c3Nvci0+cmJfcmlnaHQgPSBjaGlsZDsKKwkJCXJiX3NldF9wYXJlbnQoY2hpbGQsIHN1Y2Nlc3Nv cik7CiAJCX0KIAotCQlpZiAoY2hpbGQpIHsKLQkJCXJiX3NldF9wYXJlbnRfY29sb3IoY2hpbGQs IHBhcmVudCwgUkJfQkxBQ0spOworCQlzdWNjZXNzb3ItPnJiX2xlZnQgPSB0bXAgPSBub2RlLT5y Yl9sZWZ0OworCQlyYl9zZXRfcGFyZW50KHRtcCwgc3VjY2Vzc29yKTsKKworCQlwYyA9IG5vZGUt Pl9fcmJfcGFyZW50X2NvbG9yOworCQl0bXAgPSBfX3JiX3BhcmVudChwYyk7CisJCV9fcmJfY2hh bmdlX2NoaWxkKG5vZGUsIHN1Y2Nlc3NvciwgdG1wLCByb290KTsKKwkJaWYgKGNoaWxkMikgewor CQkJc3VjY2Vzc29yLT5fX3JiX3BhcmVudF9jb2xvciA9IHBjOworCQkJcmJfc2V0X3BhcmVudF9j b2xvcihjaGlsZDIsIHBhcmVudCwgUkJfQkxBQ0spOwogCQkJcmViYWxhbmNlID0gTlVMTDsKIAkJ fSBlbHNlIHsKLQkJCXJlYmFsYW5jZSA9IHJiX2lzX2JsYWNrKG5vZGUpID8gcGFyZW50IDogTlVM TDsKKwkJCXVuc2lnbmVkIGxvbmcgcGMyID0gc3VjY2Vzc29yLT5fX3JiX3BhcmVudF9jb2xvcjsK KwkJCXN1Y2Nlc3Nvci0+X19yYl9wYXJlbnRfY29sb3IgPSBwYzsKKwkJCXJlYmFsYW5jZSA9IF9f cmJfaXNfYmxhY2socGMyKSA/IHBhcmVudCA6IE5VTEw7CiAJCX0KLQkJbm9kZS0+X19yYl9wYXJl bnRfY29sb3IgPSBvbGQtPl9fcmJfcGFyZW50X2NvbG9yOwotCQlub2RlLT5yYl9sZWZ0ID0gb2xk LT5yYl9sZWZ0OwotCQlyYl9zZXRfcGFyZW50KG9sZC0+cmJfbGVmdCwgbm9kZSk7CiAJfQogCiAJ aWYgKHJlYmFsYW5jZSkKLS0gCjIuMTMuMQoKCl9fX19fX19fX19fX19fX19fX19fX19fX19fX19f X19fX19fX19fX19fX19fX19fClhlbi1kZXZlbCBtYWlsaW5nIGxpc3QKWGVuLWRldmVsQGxpc3Rz Lnhlbi5vcmcKaHR0cHM6Ly9saXN0cy54ZW4ub3JnL3hlbi1kZXZlbAo=