From mboxrd@z Thu Jan 1 00:00:00 1970 From: Praveen Kumar Subject: [PATCH 12/17] rbtree: optimize fetching of sibling node Date: Thu, 1 Jun 2017 02:17:03 +0530 Message-ID: <20170531204708.10470-13-kpraveen.lkml@gmail.com> References: <20170531204708.10470-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: <20170531204708.10470-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: Andrea Arcangeli , Jens Axboe , sstabellini@kernel.org, wei.liu2@citrix.com, David Woodhouse , George.Dunlap@eu.citrix.com, andrew.cooper3@citrix.com, dario.faggioli@citrix.com, ian.jackson@eu.citrix.com, tim@xen.org, Daniel Santos , Praveen Kumar , "Eric W. Biederman" , jbeulich@suse.com, Andrew Morton , Michel Lespinasse , Linus Torvalds , Peter Zijlstra List-Id: xen-devel@lists.xenproject.org V2hlbiBsb29raW5nIHRvIGZldGNoIGEgbm9kZSdzIHNpYmxpbmcsIHdlIHdlbnQgdGhyb3VnaCBh IHNlcXVlbmNlIG9mOgotIGNoZWNrIGlmIG5vZGUgaXMgdGhlIHBhcmVudCdzIGxlZnQgY2hpbGQK LSBpZiBpdCBpcywgdGhlbiBmZXRjaCB0aGUgcGFyZW50J3MgcmlnaHQgY2hpbGQKClRoaXMgY2Fu IGJlIHJlcGxhY2VkIHdpdGg6Ci0gZmV0Y2ggdGhlIHBhcmVudCdzIHJpZ2h0IGNoaWxkIGFzIGFu IGFzc3VtZWQgc2libGluZwotIGNoZWNrIHRoYXQgbm9kZSBpcyBOT1QgdGhlIGZldGNoZWQgY2hp bGQKClRoaXMgYXZvaWRzIGZldGNoaW5nIHRoZSBwYXJlbnQncyBsZWZ0IGNoaWxkIHdoZW4gbm9k ZSBpcyBhY3R1YWxseQp0aGF0IGNoaWxkLiBTYXZlcyBhIGJpdCBvbiBjb2RlIHNpemUsIHRob3Vn aCBpdCBkb2Vzbid0IHNlZW0gdG8gbWFrZQphIGxhcmdlIGRpZmZlcmVuY2UgaW4gc3BlZWQuCgpj b21taXQgNTk2MzNhYmYzNGUyZjQ0YjhlNzcyYTJjMTJhOTIxMzJhYTdjMjIyMCBmcm9tIExpbnV4 IHRyZWUKClNpZ25lZC1vZmYtYnk6IE1pY2hlbCBMZXNwaW5hc3NlIDx3YWxrZW5AZ29vZ2xlLmNv bT4KQ2M6IEFuZHJlYSBBcmNhbmdlbGkgPGFhcmNhbmdlQHJlZGhhdC5jb20+CkNjOiBEYXZpZCBX b29kaG91c2UgPERhdmlkLldvb2Rob3VzZUBpbnRlbC5jb20+CkFja2VkLWJ5OiBSaWsgdmFuIFJp ZWwgPHJpZWxAcmVkaGF0LmNvbT4KQ2M6IFBldGVyIFppamxzdHJhIDxhLnAuemlqbHN0cmFAY2hl bGxvLm5sPgpDYzogRGFuaWVsIFNhbnRvcyA8ZGFuaWVsLnNhbnRvc0Bwb2JveC5jb20+CkNjOiBK ZW5zIEF4Ym9lIDxheGJvZUBrZXJuZWwuZGs+CkNjOiAiRXJpYyBXLiBCaWVkZXJtYW4iIDxlYmll ZGVybUB4bWlzc2lvbi5jb20+ClNpZ25lZC1vZmYtYnk6IEFuZHJldyBNb3J0b24gPGFrcG1AbGlu dXgtZm91bmRhdGlvbi5vcmc+ClNpZ25lZC1vZmYtYnk6IExpbnVzIFRvcnZhbGRzIDx0b3J2YWxk c0BsaW51eC1mb3VuZGF0aW9uLm9yZz4KLS0tCiB4ZW4vY29tbW9uL3JidHJlZS5jIHwgMjEgKysr KysrKysrKysrKy0tLS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgMTMgaW5zZXJ0aW9ucygrKSwgOCBk ZWxldGlvbnMoLSkKCmRpZmYgLS1naXQgYS94ZW4vY29tbW9uL3JidHJlZS5jIGIveGVuL2NvbW1v bi9yYnRyZWUuYwppbmRleCAyNTM4NjFkODg5Li5iNjVmMDBjYTFmIDEwMDY0NAotLS0gYS94ZW4v Y29tbW9uL3JidHJlZS5jCisrKyBiL3hlbi9jb21tb24vcmJ0cmVlLmMKQEAgLTEwOCw5ICsxMDgs OSBAQCB2b2lkIHJiX2luc2VydF9jb2xvcihzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0IHJi X3Jvb3QgKnJvb3QpCiAKICAgICAgICAgZ3BhcmVudCA9IHJiX3JlZF9wYXJlbnQocGFyZW50KTsK IAotICAgICAgICBpZiAocGFyZW50ID09IGdwYXJlbnQtPnJiX2xlZnQpCisgICAgICAgIHRtcCA9 IGdwYXJlbnQtPnJiX3JpZ2h0OworICAgICAgICBpZiAocGFyZW50ICE9IHRtcCkgICAgLyogcGFy ZW50ID09IGdwYXJlbnQtPnJiX2xlZnQgKi8KICAgICAgICAgewotICAgICAgICAgICAgdG1wID0g Z3BhcmVudC0+cmJfcmlnaHQ7CiAgICAgICAgICAgICBpZiAodG1wICYmIHJiX2lzX3JlZCh0bXAp KQogICAgICAgICAgICAgewogICAgICAgICAgICAgICAgIC8qCkBAIC0xMzQsNyArMTM0LDggQEAg dm9pZCByYl9pbnNlcnRfY29sb3Ioc3RydWN0IHJiX25vZGUgKm5vZGUsIHN0cnVjdCByYl9yb290 ICpyb290KQogICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgfQogCi0gICAg ICAgICAgICBpZiAocGFyZW50LT5yYl9yaWdodCA9PSBub2RlKQorICAgICAgICAgICAgdG1wID0g cGFyZW50LT5yYl9yaWdodDsKKyAgICAgICAgICAgIGlmIChub2RlID09IHRtcCkKICAgICAgICAg ICAgIHsKICAgICAgICAgICAgICAgICAvKgogICAgICAgICAgICAgICAgICAqIENhc2UgMiAtIGxl ZnQgcm90YXRlIGF0IHBhcmVudApAQCAtMTY0LDcgKzE2NSw3IEBAIHZvaWQgcmJfaW5zZXJ0X2Nv bG9yKHN0cnVjdCByYl9ub2RlICpub2RlLCBzdHJ1Y3QgcmJfcm9vdCAqcm9vdCkKICAgICAgICAg ICAgICAqICAgICAvICAgICAgICAgICAgICAgICBcCiAgICAgICAgICAgICAgKiAgICBuICAgICAg ICAgICAgICAgICAgIFUKICAgICAgICAgICAgICAqLwotICAgICAgICAgICAgZ3BhcmVudC0+cmJf bGVmdCA9IHRtcCA9IHBhcmVudC0+cmJfcmlnaHQ7CisgICAgICAgICAgICBncGFyZW50LT5yYl9s ZWZ0ID0gdG1wOyAgICAvKiA9PSBwYXJlbnQtPnJiX3JpZ2h0ICovCiAgICAgICAgICAgICBwYXJl bnQtPnJiX3JpZ2h0ID0gZ3BhcmVudDsKICAgICAgICAgICAgIGlmICh0bXApCiAgICAgICAgICAg ICAgICAgcmJfc2V0X3BhcmVudF9jb2xvcih0bXAsIGdwYXJlbnQsIFJCX0JMQUNLKTsKQEAgLTE4 Myw3ICsxODQsOCBAQCB2b2lkIHJiX2luc2VydF9jb2xvcihzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwg c3RydWN0IHJiX3Jvb3QgKnJvb3QpCiAgICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAg ICAgICB9CiAKLSAgICAgICAgICAgIGlmIChwYXJlbnQtPnJiX2xlZnQgPT0gbm9kZSkKKyAgICAg ICAgICAgIHRtcCA9IHBhcmVudC0+cmJfbGVmdDsKKyAgICAgICAgICAgIGlmIChub2RlID09IHRt cCkKICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAvKiBDYXNlIDIgLSByaWdodCByb3Rh dGUgYXQgcGFyZW50ICovCiAgICAgICAgICAgICAgICAgcGFyZW50LT5yYl9sZWZ0ID0gdG1wID0g bm9kZS0+cmJfcmlnaHQ7CkBAIC0xOTIsMTAgKzE5NCwxMSBAQCB2b2lkIHJiX2luc2VydF9jb2xv cihzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX3Jvb3QgKnJvb3QpCiAgICAgICAgICAg ICAgICAgICAgIHJiX3NldF9wYXJlbnRfY29sb3IodG1wLCBwYXJlbnQsIFJCX0JMQUNLKTsKICAg ICAgICAgICAgICAgICByYl9zZXRfcGFyZW50X2NvbG9yKHBhcmVudCwgbm9kZSwgUkJfUkVEKTsK ICAgICAgICAgICAgICAgICBwYXJlbnQgPSBub2RlOworICAgICAgICAgICAgICAgIHRtcCA9IG5v ZGUtPnJiX2xlZnQ7CiAgICAgICAgICAgICB9CiAKICAgICAgICAgICAgIC8qIENhc2UgMyAtIGxl ZnQgcm90YXRlIGF0IGdwYXJlbnQgKi8KLSAgICAgICAgICAgIGdwYXJlbnQtPnJiX3JpZ2h0ID0g dG1wID0gcGFyZW50LT5yYl9sZWZ0OworICAgICAgICAgICAgZ3BhcmVudC0+cmJfcmlnaHQgPSB0 bXA7ICAgIC8qID09IHBhcmVudC0+cmJfbGVmdCAqLwogICAgICAgICAgICAgcGFyZW50LT5yYl9s ZWZ0ID0gZ3BhcmVudDsKICAgICAgICAgICAgIGlmICh0bXApCiAgICAgICAgICAgICAgICAgcmJf c2V0X3BhcmVudF9jb2xvcih0bXAsIGdwYXJlbnQsIFJCX0JMQUNLKTsKQEAgLTIyOCw4ICsyMzEs MTAgQEAgc3RhdGljIHZvaWQgX19yYl9lcmFzZV9jb2xvcihzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwg c3RydWN0IHJiX25vZGUgKnBhcmVudCwKICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICB9IGVs c2UgaWYgKCFwYXJlbnQpIHsKICAgICAgICAgICAgIGJyZWFrOwotICAgICAgICB9IGVsc2UgaWYg KHBhcmVudC0+cmJfbGVmdCA9PSBub2RlKSB7Ci0gICAgICAgICAgICBzaWJsaW5nID0gcGFyZW50 LT5yYl9yaWdodDsKKyAgICAgICAgfQorICAgICAgICBzaWJsaW5nID0gcGFyZW50LT5yYl9yaWdo dDsKKyAgICAgICAgaWYgKCBub2RlICE9IHNpYmxpbmcpICAgIC8qIG5vZGUgPT0gcGFyZW50LT5y Yl9sZWZ0ICovCisgICAgICAgIHsKICAgICAgICAgICAgIGlmIChyYl9pc19yZWQoc2libGluZykp IHsKICAgICAgICAgICAgICAgICAvKgogICAgICAgICAgICAgICAgICAqIENhc2UgMSAtIGxlZnQg cm90YXRlIGF0IHBhcmVudAotLSAKMi4xMi4wCgoKX19fX19fX19fX19fX19fX19fX19fX19fX19f X19fX19fX19fX19fX19fX19fX18KWGVuLWRldmVsIG1haWxpbmcgbGlzdApYZW4tZGV2ZWxAbGlz dHMueGVuLm9yZwpodHRwczovL2xpc3RzLnhlbi5vcmcveGVuLWRldmVsCg==