From mboxrd@z Thu Jan 1 00:00:00 1970 From: Praveen Kumar Subject: [PATCH v2 19/20] rbtree: low level optimizations in rb_erase() Date: Sat, 17 Jun 2017 15:02:52 +0530 Message-ID: <20170617093253.3990-20-kpraveen.lkml@gmail.com> References: <20170617093253.3990-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: <20170617093253.3990-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, 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 VmFyaW91cyBtaW5vciBvcHRpbWl6YXRpb25zIGluIHJiX2VyYXNlKCk6Ci0gQXZvaWQgbXVsdGlw bGUgbG9hZGluZyBvZiBub2RlLT5fX3JiX3BhcmVudF9jb2xvciB3aGVuIGNvbXB1dGluZyBwYXJl bnQKICBhbmQgY29sb3IgaW5mb3JtYXRpb24gKHBvc3NpYmx5IG5vdCBpbiBjbG9zZSBzZXF1ZW5j ZSwgYXMgdGhlcmUgbWlnaHQKICBiZSBmdXJ0aGVyIGJyYW5jaGVzIGluIHRoZSBhbGdvcml0aG0p Ci0gSW4gdGhlIDEtY2hpbGQgc3ViY2FzZSBvZiBjYXNlIDEsIGNvcHkgdGhlIF9fcmJfcGFyZW50 X2NvbG9yIGZpZWxkIGZyb20KICB0aGUgZXJhc2VkIG5vZGUgdG8gdGhlIGNoaWxkIGluc3RlYWQg b2YgcmVjb21wdXRpbmcgaXQgZnJvbSB0aGUgZGVzaXJlZAogIHBhcmVudCBhbmQgY29sb3IKLSBX aGVuIHNlYXJjaGluZyBmb3IgdGhlIGVyYXNlZCBub2RlJ3Mgc3VjY2Vzc29yLCBkaWZmZXJlbnRp YXRlIGJldHdlZW4KICBjYXNlcyAyIGFuZCAzIGJhc2VkIG9uIHdoZXRoZXIgYW55IGxlZnQgbGlu a3Mgd2VyZSBmb2xsb3dlZC4gVGhpcyBhdm9pZHMKICBhIGNvbmRpdGlvbiBsYXRlciBkb3duLgot IEluIGNhc2UgMywga2VlcCBhIHBvaW50ZXIgdG8gdGhlIGVyYXNlZCBub2RlJ3MgcmlnaHQgY2hp bGQgc28gd2UgZG9uJ3QKICBoYXZlIHRvIHJlZmV0Y2ggaXQgbGF0ZXIgdG8gYWRqdXN0IGl0cyBw YXJlbnQuCi0gSW4gdGhlIG5vLWNoaWxkcyBzdWJjYXNlIG9mIGNhc2VzIDIgYW5kIDMsIHBsYWNl IHRoZSByZWJhbGFuY2UgYXNzaWdtZW50CiAgbGFzdCBzbyB0aGF0IHRoZSBjb21waWxlciBjYW4g cmVtb3ZlIHRoZSBmb2xsb3dpbmcgaWYocmViYWxhbmNlKSB0ZXN0LgoKQWxzbywgYWRkZWQgc29t ZSBjb21tZW50cyB0byBpbGx1c3RyYXRlIGNhc2VzIDIgYW5kIDMuCgpTaWduZWQtb2ZmLWJ5OiBN aWNoZWwgTGVzcGluYXNzZSA8d2Fsa2VuQGdvb2dsZS5jb20+CkFja2VkLWJ5OiBSaWsgdmFuIFJp ZWwgPHJpZWxAcmVkaGF0LmNvbT4KQ2M6IFBldGVyIFppamxzdHJhIDxhLnAuemlqbHN0cmFAY2hl bGxvLm5sPgpDYzogQW5kcmVhIEFyY2FuZ2VsaSA8YWFyY2FuZ2VAcmVkaGF0LmNvbT4KQ2M6IERh dmlkIFdvb2Rob3VzZSA8ZHdtdzJAaW5mcmFkZWFkLm9yZz4KU2lnbmVkLW9mZi1ieTogQW5kcmV3 IE1vcnRvbiA8YWtwbUBsaW51eC1mb3VuZGF0aW9uLm9yZz4KU2lnbmVkLW9mZi1ieTogTGludXMg VG9ydmFsZHMgPHRvcnZhbGRzQGxpbnV4LWZvdW5kYXRpb24ub3JnPgpbTGludXggY29tbWl0IDRm MDM1YWQ2N2Y0NjMzYzIzM2NiMzY0MjcxMWQ0OWI0ZWZjOWM4MmRdCgpQb3J0ZWQgdG8gWGVuLgoK U2lnbmVkLW9mZi1ieTogUHJhdmVlbiBLdW1hciA8a3ByYXZlZW4ubGttbEBnbWFpbC5jb20+Ci0t LQogeGVuL2NvbW1vbi9yYnRyZWUuYyB8IDEwMCArKysrKysrKysrKysrKysrKysrKysrKysrKysr KysrKysrKy0tLS0tLS0tLS0tLS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgNjcgaW5zZXJ0aW9ucygr KSwgMzMgZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEveGVuL2NvbW1vbi9yYnRyZWUuYyBiL3hl bi9jb21tb24vcmJ0cmVlLmMKaW5kZXggZGZlNTY2YTVhZi4uNjhlNTA1YmVkZSAxMDA2NDQKLS0t IGEveGVuL2NvbW1vbi9yYnRyZWUuYworKysgYi94ZW4vY29tbW9uL3JidHJlZS5jCkBAIC00Niw5 ICs0NiwxNCBAQAogI2RlZmluZSAgICBSQl9SRUQgICAgMAogI2RlZmluZSAgICBSQl9CTEFDSyAg MQogCi0jZGVmaW5lIHJiX2NvbG9yKHIpICAgICAoKHIpLT5fX3JiX3BhcmVudF9jb2xvciAmIDEp Ci0jZGVmaW5lIHJiX2lzX3JlZChyKSAgICAoIXJiX2NvbG9yKHIpKQotI2RlZmluZSByYl9pc19i bGFjayhyKSAgcmJfY29sb3IocikKKyNkZWZpbmUgX19yYl9wYXJlbnQocGMpICAgICgoc3RydWN0 IHJiX25vZGUgKikocGMgJiB+MykpCisKKyNkZWZpbmUgX19yYl9jb2xvcihwYykgICAgICgocGMp ICYgMSkKKyNkZWZpbmUgX19yYl9pc19ibGFjayhwYykgIF9fcmJfY29sb3IocGMpCisjZGVmaW5l IF9fcmJfaXNfcmVkKHBjKSAgICAoIV9fcmJfY29sb3IocGMpKQorI2RlZmluZSByYl9jb2xvcihy YikgICAgICAgX19yYl9jb2xvcigocmIpLT5fX3JiX3BhcmVudF9jb2xvcikKKyNkZWZpbmUgcmJf aXNfcmVkKHJiKSAgICAgIF9fcmJfaXNfcmVkKChyYiktPl9fcmJfcGFyZW50X2NvbG9yKQorI2Rl ZmluZSByYl9pc19ibGFjayhyYikgICAgX19yYl9pc19ibGFjaygocmIpLT5fX3JiX3BhcmVudF9j b2xvcikKIAogc3RhdGljIGlubGluZSB2b2lkIHJiX3NldF9ibGFjayhzdHJ1Y3QgcmJfbm9kZSAq cmIpCiB7CkBAIC0zODEsNiArMzg2LDcgQEAgdm9pZCByYl9lcmFzZShzdHJ1Y3QgcmJfbm9kZSAq bm9kZSwgc3RydWN0IHJiX3Jvb3QgKnJvb3QpCiB7CiAgICAgc3RydWN0IHJiX25vZGUgKmNoaWxk ID0gbm9kZS0+cmJfcmlnaHQsICp0bXAgPSBub2RlLT5yYl9sZWZ0OwogICAgIHN0cnVjdCByYl9u b2RlICpwYXJlbnQsICpyZWJhbGFuY2U7CisgICAgdW5zaWduZWQgbG9uZyBwYzsKICAKIAlpZiAo IXRtcCkgewogICAgICAgICAvKgpAQCAtMzkxLDUxICszOTcsNzkgQEAgdm9pZCByYl9lcmFzZShz dHJ1Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX3Jvb3QgKnJvb3QpCiAgICAgICAgICAqIHNv IGFzIHRvIGJ5cGFzcyBfX3JiX2VyYXNlX2NvbG9yKCkgbGF0ZXIgb24uCiAgICAgICAgICAqLwog Ci0gICAgICAgIHBhcmVudCA9IHJiX3BhcmVudChub2RlKTsKKyAgICAgICAgcGMgPSBub2RlLT5f X3JiX3BhcmVudF9jb2xvcjsKKyAgICAgICAgcGFyZW50ID0gX19yYl9wYXJlbnQocGMpOwogICAg ICAgICBfX3JiX2NoYW5nZV9jaGlsZChub2RlLCBjaGlsZCwgcGFyZW50LCByb290KTsKICAgICAg ICAgaWYgKGNoaWxkKQogICAgICAgICB7Ci0gICAgICAgICAgICByYl9zZXRfcGFyZW50X2NvbG9y KGNoaWxkLCBwYXJlbnQsIFJCX0JMQUNLKTsKKyAgICAgICAgICAgIGNoaWxkLT5fX3JiX3BhcmVu dF9jb2xvciA9IHBjOwogICAgICAgICAgICAgcmViYWxhbmNlID0gTlVMTDsKLSAgICAgICAgfSBl bHNlIHsKLSAgICAgICAgICAgIHJlYmFsYW5jZSA9IHJiX2lzX2JsYWNrKG5vZGUpID8gcGFyZW50 IDogTlVMTDsKLSAgICAgICAgfQorICAgICAgICB9IGVsc2UKKyAgICAgICAgICAgIHJlYmFsYW5j ZSA9IF9fcmJfaXNfYmxhY2socGMpID8gcGFyZW50IDogTlVMTDsKICAgICB9IGVsc2UgaWYgKCFj aGlsZCkgewogICAgICAgICAvKiBTdGlsbCBjYXNlIDEsIGJ1dCB0aGlzIHRpbWUgdGhlIGNoaWxk IGlzIG5vZGUtPnJiX2xlZnQgKi8KLSAgICAgICAgcGFyZW50ID0gcmJfcGFyZW50KG5vZGUpOwor ICAgICAgICB0bXAtPl9fcmJfcGFyZW50X2NvbG9yID0gcGMgPSBub2RlLT5fX3JiX3BhcmVudF9j b2xvcjsKKyAgICAgICAgcGFyZW50ID0gX19yYl9wYXJlbnQocGMpOwogICAgICAgICBfX3JiX2No YW5nZV9jaGlsZChub2RlLCB0bXAsIHBhcmVudCwgcm9vdCk7Ci0gICAgICAgIHJiX3NldF9wYXJl bnRfY29sb3IodG1wLCBwYXJlbnQsIFJCX0JMQUNLKTsKICAgICAgICAgcmViYWxhbmNlID0gTlVM TDsKICAgICB9IGVsc2UgewotICAgICAgICBzdHJ1Y3QgcmJfbm9kZSAqb2xkID0gbm9kZSwgKmxl ZnQ7Ci0KLSAgICAgICAgbm9kZSA9IGNoaWxkOwotICAgICAgICB3aGlsZSAoKGxlZnQgPSBub2Rl LT5yYl9sZWZ0KSAhPSBOVUxMKQotICAgICAgICAgICAgbm9kZSA9IGxlZnQ7Ci0gICAgICAgIF9f cmJfY2hhbmdlX2NoaWxkKG9sZCwgbm9kZSwgcmJfcGFyZW50KG9sZCksIHJvb3QpOwotICAgICAg ICBjaGlsZCA9IG5vZGUtPnJiX3JpZ2h0OwotICAgICAgICBwYXJlbnQgPSByYl9wYXJlbnQobm9k ZSk7Ci0KLSAgICAgICAgaWYgKHBhcmVudCA9PSBvbGQpIHsKLSAgICAgICAgICAgIHBhcmVudCA9 IG5vZGU7CisgICAgICAgIHN0cnVjdCByYl9ub2RlICpzdWNjZXNzb3IgPSBjaGlsZCwgKmNoaWxk MjsKKyAgICAgICAgdG1wID0gY2hpbGQtPnJiX2xlZnQ7CisgICAgICAgIGlmICghdG1wKQorICAg ICAgICB7CisgICAgICAgICAgICAvKgorICAgICAgICAgICAgICogQ2FzZSAyOiBub2RlJ3Mgc3Vj Y2Vzc29yIGlzIGl0cyByaWdodCBjaGlsZAorICAgICAgICAgICAgICoKKyAgICAgICAgICAgICAq ICAgIChuKSAgICAgICAgICAocykKKyAgICAgICAgICAgICAqICAgIC8gXCAgICAgICAgICAvIFwK KyAgICAgICAgICAgICAqICAoeCkgKHMpICAtPiAgKHgpIChjKQorICAgICAgICAgICAgICogICAg ICAgIFwKKyAgICAgICAgICAgICAqICAgICAgICAoYykKKyAgICAgICAgICAgICAqLworICAgICAg ICAgICAgcGFyZW50ID0gY2hpbGQ7CisgICAgICAgICAgICBjaGlsZDIgPSBjaGlsZC0+cmJfcmln aHQ7CiAgICAgICAgIH0gZWxzZSB7Ci0gICAgICAgICAgICBwYXJlbnQtPnJiX2xlZnQgPSBjaGls ZDsKLQotICAgICAgICAgICAgbm9kZS0+cmJfcmlnaHQgPSBvbGQtPnJiX3JpZ2h0OwotICAgICAg ICAgICAgcmJfc2V0X3BhcmVudChvbGQtPnJiX3JpZ2h0LCBub2RlKTsKKyAgICAgICAgICAgIC8q CisgICAgICAgICAgICAgKiBDYXNlIDM6IG5vZGUncyBzdWNjZXNzb3IgaXMgbGVmdG1vc3QgdW5k ZXIKKyAgICAgICAgICAgICAqIG5vZGUncyByaWdodCBjaGlsZCBzdWJ0cmVlCisgICAgICAgICAg ICAgKgorICAgICAgICAgICAgICogICAgKG4pICAgICAgICAgIChzKQorICAgICAgICAgICAgICog ICAgLyBcICAgICAgICAgIC8gXAorICAgICAgICAgICAgICogICh4KSAoeSkgIC0+ICAoeCkgKHkp CisgICAgICAgICAgICAgKiAgICAgIC8gICAgICAgICAgICAvCisgICAgICAgICAgICAgKiAgICAo cCkgICAgICAgICAgKHApCisgICAgICAgICAgICAgKiAgICAvICAgICAgICAgICAgLworICAgICAg ICAgICAgICogIChzKSAgICAgICAgICAoYykKKyAgICAgICAgICAgICAqICAgIFwKKyAgICAgICAg ICAgICAqICAgIChjKQorICAgICAgICAgICAgICovCisgICAgICAgICAgICBkbworICAgICAgICAg ICAgeworICAgICAgICAgICAgICAgIHBhcmVudCA9IHN1Y2Nlc3NvcjsKKyAgICAgICAgICAgICAg ICBzdWNjZXNzb3IgPSB0bXA7CisgICAgICAgICAgICAgICAgdG1wID0gdG1wLT5yYl9sZWZ0Owor ICAgICAgICAgICAgfSB3aGlsZSAodG1wKTsKKyAgICAgICAgICAgIHBhcmVudC0+cmJfbGVmdCA9 IGNoaWxkMiA9IHN1Y2Nlc3Nvci0+cmJfcmlnaHQ7CisgICAgICAgICAgICBzdWNjZXNzb3ItPnJi X3JpZ2h0ID0gY2hpbGQ7CisgICAgICAgICAgICByYl9zZXRfcGFyZW50KGNoaWxkLCBzdWNjZXNz b3IpOwogICAgICAgICB9CiAKLSAgICAgICAgaWYgKGNoaWxkKSB7Ci0gICAgICAgICAgICByYl9z ZXRfcGFyZW50X2NvbG9yKGNoaWxkLCBwYXJlbnQsIFJCX0JMQUNLKTsKKyAgICAgICAgc3VjY2Vz c29yLT5yYl9sZWZ0ID0gdG1wID0gbm9kZS0+cmJfbGVmdDsKKyAgICAgICAgcmJfc2V0X3BhcmVu dCh0bXAsIHN1Y2Nlc3Nvcik7CisKKyAgICAgICAgcGMgPSBub2RlLT5fX3JiX3BhcmVudF9jb2xv cjsKKyAgICAgICAgdG1wID0gX19yYl9wYXJlbnQocGMpOworICAgICAgICBfX3JiX2NoYW5nZV9j aGlsZChub2RlLCBzdWNjZXNzb3IsIHRtcCwgcm9vdCk7CisgICAgICAgIGlmIChjaGlsZDIpCisg ICAgICAgIHsKKyAgICAgICAgICAgIHN1Y2Nlc3Nvci0+X19yYl9wYXJlbnRfY29sb3IgPSBwYzsK KyAgICAgICAgICAgIHJiX3NldF9wYXJlbnRfY29sb3IoY2hpbGQyLCBwYXJlbnQsIFJCX0JMQUNL KTsKICAgICAgICAgICAgIHJlYmFsYW5jZSA9IE5VTEw7CiAgICAgICAgIH0gZWxzZSB7Ci0gICAg ICAgICAgICByZWJhbGFuY2UgPSByYl9pc19ibGFjayhub2RlKSA/IHBhcmVudCA6IE5VTEw7Cisg ICAgICAgICAgICB1bnNpZ25lZCBsb25nIHBjMiA9IHN1Y2Nlc3Nvci0+X19yYl9wYXJlbnRfY29s b3I7CisgICAgICAgICAgICBzdWNjZXNzb3ItPl9fcmJfcGFyZW50X2NvbG9yID0gcGM7CisgICAg ICAgICAgICByZWJhbGFuY2UgPSBfX3JiX2lzX2JsYWNrKHBjMikgPyBwYXJlbnQgOiBOVUxMOwog ICAgICAgICB9Ci0KLSAgICAgICAgbm9kZS0+X19yYl9wYXJlbnRfY29sb3IgPSBvbGQtPl9fcmJf cGFyZW50X2NvbG9yOwotICAgICAgICBub2RlLT5yYl9sZWZ0ID0gb2xkLT5yYl9sZWZ0OwotCi0g ICAgICAgIHJiX3NldF9wYXJlbnQob2xkLT5yYl9sZWZ0LCBub2RlKTsKICAgICB9CiAKICAgICBp ZiAocmViYWxhbmNlKQotLSAKMi4xMi4wCgoKX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f X19fX19fX19fX19fX19fX18KWGVuLWRldmVsIG1haWxpbmcgbGlzdApYZW4tZGV2ZWxAbGlzdHMu eGVuLm9yZwpodHRwczovL2xpc3RzLnhlbi5vcmcveGVuLWRldmVsCg==