From mboxrd@z Thu Jan 1 00:00:00 1970 From: Praveen Kumar Subject: [PATCH v5 16/17] rbtree: low level optimizations in rb_erase() Date: Fri, 14 Jul 2017 13:56:35 +0530 Message-ID: <20170714082636.29511-17-kpraveen.lkml@gmail.com> References: <20170714082636.29511-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: <20170714082636.29511-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 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 bi9yYnRyZWUuYyB8IDEwMCArKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKystLS0tLS0t LS0tLS0tLS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgNjQgaW5zZXJ0aW9ucygrKSwgMzYgZGVsZXRp b25zKC0pCgpkaWZmIC0tZ2l0IGEveGVuL2NvbW1vbi9yYnRyZWUuYyBiL3hlbi9jb21tb24vcmJ0 cmVlLmMKaW5kZXggNDMzMTliOGYzYi4uOGUxZGQyYzU2ZSAxMDA2NDQKLS0tIGEveGVuL2NvbW1v bi9yYnRyZWUuYworKysgYi94ZW4vY29tbW9uL3JidHJlZS5jCkBAIC00Nyw5ICs0NywxNCBAQAog I2RlZmluZQkJUkJfUkVECQkwCiAjZGVmaW5lCQlSQl9CTEFDSwkxCiAKLSNkZWZpbmUgcmJfY29s b3IocikgICAoKHIpLT5fX3JiX3BhcmVudF9jb2xvciAmIDEpCi0jZGVmaW5lIHJiX2lzX3JlZChy KSAgICghcmJfY29sb3IocikpCi0jZGVmaW5lIHJiX2lzX2JsYWNrKHIpIHJiX2NvbG9yKHIpCisj ZGVmaW5lIF9fcmJfcGFyZW50KHBjKSAgICAoKHN0cnVjdCByYl9ub2RlICopKHBjICYgfjMpKQor CisjZGVmaW5lIF9fcmJfY29sb3IocGMpICAgICAoKHBjKSAmIDEpCisjZGVmaW5lIF9fcmJfaXNf YmxhY2socGMpICBfX3JiX2NvbG9yKHBjKQorI2RlZmluZSBfX3JiX2lzX3JlZChwYykgICAgKCFf X3JiX2NvbG9yKHBjKSkKKyNkZWZpbmUgcmJfY29sb3IocmIpICAgICAgIF9fcmJfY29sb3IoKHJi KS0+X19yYl9wYXJlbnRfY29sb3IpCisjZGVmaW5lIHJiX2lzX3JlZChyYikgICAgICBfX3JiX2lz X3JlZCgocmIpLT5fX3JiX3BhcmVudF9jb2xvcikKKyNkZWZpbmUgcmJfaXNfYmxhY2socmIpICAg IF9fcmJfaXNfYmxhY2soKHJiKS0+X19yYl9wYXJlbnRfY29sb3IpCiAKIHN0YXRpYyBpbmxpbmUg dm9pZCByYl9zZXRfYmxhY2soc3RydWN0IHJiX25vZGUgKnJiKQogewpAQCAtMzc4LDYgKzM4Myw3 IEBAIHZvaWQgcmJfZXJhc2Uoc3RydWN0IHJiX25vZGUgKm5vZGUsIHN0cnVjdCByYl9yb290ICpy b290KQogewogCXN0cnVjdCByYl9ub2RlICpjaGlsZCA9IG5vZGUtPnJiX3JpZ2h0LCAqdG1wID0g bm9kZS0+cmJfbGVmdDsKIAlzdHJ1Y3QgcmJfbm9kZSAqcGFyZW50LCAqcmViYWxhbmNlOworCXVu c2lnbmVkIGxvbmcgcGM7CiAKIAlpZiAoIXRtcCkgewogCQkvKgpAQCAtMzg3LDUzICszOTMsNzUg QEAgdm9pZCByYl9lcmFzZShzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX3Jvb3QgKnJv b3QpCiAJCSAqIGFuZCBub2RlIG11c3QgYmUgYmxhY2sgZHVlIHRvIDQpLiBXZSBhZGp1c3QgY29s b3JzIGxvY2FsbHkKIAkJICogc28gYXMgdG8gYnlwYXNzIF9fcmJfZXJhc2VfY29sb3IoKSBsYXRl ciBvbi4KIAkJICovCi0KLQkJcGFyZW50ID0gcmJfcGFyZW50KG5vZGUpOwotCisJCXBjID0gbm9k ZS0+X19yYl9wYXJlbnRfY29sb3I7CisJCXBhcmVudCA9IF9fcmJfcGFyZW50KHBjKTsKIAkJX19y Yl9jaGFuZ2VfY2hpbGQobm9kZSwgY2hpbGQsIHBhcmVudCwgcm9vdCk7CiAJCWlmIChjaGlsZCkg ewotCQkJcmJfc2V0X3BhcmVudF9jb2xvcihjaGlsZCwgcGFyZW50LCBSQl9CTEFDSyk7CisJCQlj aGlsZC0+X19yYl9wYXJlbnRfY29sb3IgPSBwYzsKIAkJCXJlYmFsYW5jZSA9IE5VTEw7Ci0JCX0g ZWxzZSB7Ci0JCQlyZWJhbGFuY2UgPSByYl9pc19ibGFjayhub2RlKSA/IHBhcmVudCA6IE5VTEw7 Ci0JCX0KKwkJfSBlbHNlCisJCQlyZWJhbGFuY2UgPSBfX3JiX2lzX2JsYWNrKHBjKSA/IHBhcmVu dCA6IE5VTEw7CiAJfSBlbHNlIGlmICghY2hpbGQpIHsKIAkJLyogU3RpbGwgY2FzZSAxLCBidXQg dGhpcyB0aW1lIHRoZSBjaGlsZCBpcyBub2RlLT5yYl9sZWZ0ICovCi0JCXBhcmVudCA9IHJiX3Bh cmVudChub2RlKTsKKwkJdG1wLT5fX3JiX3BhcmVudF9jb2xvciA9IHBjID0gbm9kZS0+X19yYl9w YXJlbnRfY29sb3I7CisJCXBhcmVudCA9IF9fcmJfcGFyZW50KHBjKTsKIAkJX19yYl9jaGFuZ2Vf Y2hpbGQobm9kZSwgdG1wLCBwYXJlbnQsIHJvb3QpOwotCQlyYl9zZXRfcGFyZW50X2NvbG9yKHRt cCwgcGFyZW50LCBSQl9CTEFDSyk7CiAJCXJlYmFsYW5jZSA9IE5VTEw7CiAJfSBlbHNlIHsKLQkJ c3RydWN0IHJiX25vZGUgKm9sZCA9IG5vZGUsICpsZWZ0OwotCi0JCW5vZGUgPSBjaGlsZDsKLQkJ d2hpbGUgKChsZWZ0ID0gbm9kZS0+cmJfbGVmdCkgIT0gTlVMTCkKLQkJCW5vZGUgPSBsZWZ0Owot Ci0JCV9fcmJfY2hhbmdlX2NoaWxkKG9sZCwgbm9kZSwgcmJfcGFyZW50KG9sZCksIHJvb3QpOwot Ci0JCWNoaWxkID0gbm9kZS0+cmJfcmlnaHQ7Ci0JCXBhcmVudCA9IHJiX3BhcmVudChub2RlKTsK LQotCQlpZiAocGFyZW50ID09IG9sZCkgewotCQkJcGFyZW50ID0gbm9kZTsKKwkJc3RydWN0IHJi X25vZGUgKnN1Y2Nlc3NvciA9IGNoaWxkLCAqY2hpbGQyOworCQl0bXAgPSBjaGlsZC0+cmJfbGVm dDsKKwkJaWYgKCF0bXApIHsKKwkJCS8qCisJCQkgKiBDYXNlIDI6IG5vZGUncyBzdWNjZXNzb3Ig aXMgaXRzIHJpZ2h0IGNoaWxkCisJCQkgKgorCQkJICogICAgKG4pICAgICAgICAgIChzKQorCQkJ ICogICAgLyBcICAgICAgICAgIC8gXAorCQkJICogICh4KSAocykgIC0+ICAoeCkgKGMpCisJCQkg KiAgICAgICAgXAorCQkJICogICAgICAgIChjKQorCQkJICovCisJCQlwYXJlbnQgPSBjaGlsZDsK KwkJCWNoaWxkMiA9IGNoaWxkLT5yYl9yaWdodDsKIAkJfSBlbHNlIHsKLQkJCXBhcmVudC0+cmJf bGVmdCA9IGNoaWxkOwotCi0JCQlub2RlLT5yYl9yaWdodCA9IG9sZC0+cmJfcmlnaHQ7Ci0JCQly Yl9zZXRfcGFyZW50KG9sZC0+cmJfcmlnaHQsIG5vZGUpOworCQkJLyoKKwkJCSAqIENhc2UgMzog bm9kZSdzIHN1Y2Nlc3NvciBpcyBsZWZ0bW9zdCB1bmRlcgorCQkJICogbm9kZSdzIHJpZ2h0IGNo aWxkIHN1YnRyZWUKKwkJCSAqCisJCQkgKiAgICAobikgICAgICAgICAgKHMpCisJCQkgKiAgICAv IFwgICAgICAgICAgLyBcCisJCQkgKiAgKHgpICh5KSAgLT4gICh4KSAoeSkKKwkJCSAqICAgICAg LyAgICAgICAgICAgIC8KKwkJCSAqICAgIChwKSAgICAgICAgICAocCkKKwkJCSAqICAgIC8gICAg ICAgICAgICAvCisJCQkgKiAgKHMpICAgICAgICAgIChjKQorCQkJICogICAgXAorCQkJICogICAg KGMpCisJCQkgKi8KKwkJCWRvIHsKKwkJCQlwYXJlbnQgPSBzdWNjZXNzb3I7CisJCQkJc3VjY2Vz c29yID0gdG1wOworCQkJCXRtcCA9IHRtcC0+cmJfbGVmdDsKKwkJCX0gd2hpbGUgKHRtcCk7CisJ CQlwYXJlbnQtPnJiX2xlZnQgPSBjaGlsZDIgPSBzdWNjZXNzb3ItPnJiX3JpZ2h0OworCQkJc3Vj Y2Vzc29yLT5yYl9yaWdodCA9IGNoaWxkOworCQkJcmJfc2V0X3BhcmVudChjaGlsZCwgc3VjY2Vz c29yKTsKIAkJfQogCi0JCWlmIChjaGlsZCkgewotCQkJcmJfc2V0X3BhcmVudF9jb2xvcihjaGls ZCwgcGFyZW50LCBSQl9CTEFDSyk7CisJCXN1Y2Nlc3Nvci0+cmJfbGVmdCA9IHRtcCA9IG5vZGUt PnJiX2xlZnQ7CisJCXJiX3NldF9wYXJlbnQodG1wLCBzdWNjZXNzb3IpOworCisJCXBjID0gbm9k ZS0+X19yYl9wYXJlbnRfY29sb3I7CisJCXRtcCA9IF9fcmJfcGFyZW50KHBjKTsKKwkJX19yYl9j aGFuZ2VfY2hpbGQobm9kZSwgc3VjY2Vzc29yLCB0bXAsIHJvb3QpOworCQlpZiAoY2hpbGQyKSB7 CisJCQlzdWNjZXNzb3ItPl9fcmJfcGFyZW50X2NvbG9yID0gcGM7CisJCQlyYl9zZXRfcGFyZW50 X2NvbG9yKGNoaWxkMiwgcGFyZW50LCBSQl9CTEFDSyk7CiAJCQlyZWJhbGFuY2UgPSBOVUxMOwog CQl9IGVsc2UgewotCQkJcmViYWxhbmNlID0gcmJfaXNfYmxhY2sobm9kZSkgPyBwYXJlbnQgOiBO VUxMOworCQkJdW5zaWduZWQgbG9uZyBwYzIgPSBzdWNjZXNzb3ItPl9fcmJfcGFyZW50X2NvbG9y OworCQkJc3VjY2Vzc29yLT5fX3JiX3BhcmVudF9jb2xvciA9IHBjOworCQkJcmViYWxhbmNlID0g X19yYl9pc19ibGFjayhwYzIpID8gcGFyZW50IDogTlVMTDsKIAkJfQotCQlub2RlLT5fX3JiX3Bh cmVudF9jb2xvciA9IG9sZC0+X19yYl9wYXJlbnRfY29sb3I7Ci0JCW5vZGUtPnJiX2xlZnQgPSBv bGQtPnJiX2xlZnQ7Ci0KLQkJcmJfc2V0X3BhcmVudChvbGQtPnJiX2xlZnQsIG5vZGUpOwogCX0K IAogCWlmIChyZWJhbGFuY2UpCi0tIAoyLjEyLjAKCgpfX19fX19fX19fX19fX19fX19fX19fX19f X19fX19fX19fX19fX19fX19fX19fXwpYZW4tZGV2ZWwgbWFpbGluZyBsaXN0Clhlbi1kZXZlbEBs aXN0cy54ZW4ub3JnCmh0dHBzOi8vbGlzdHMueGVuLm9yZy94ZW4tZGV2ZWwK