From mboxrd@z Thu Jan 1 00:00:00 1970 From: Praveen Kumar Subject: [PATCH v5 09/17] rbtree: optimize case selection logic in __rb_erase_color() Date: Fri, 14 Jul 2017 13:56:28 +0530 Message-ID: <20170714082636.29511-10-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 RnJvbTogTWljaGVsIExlc3BpbmFzc2UgPHdhbGtlbkBnb29nbGUuY29tPgoKSW4gX19yYl9lcmFz ZV9jb2xvcigpLCB3ZSBoYXZlIHRvIHNlbGVjdCBvbmUgb2YgMyBjYXNlcyBkZXBlbmRpbmcgb24g dGhlCmNvbG9yIG9uIHRoZSAnb3RoZXInIG5vZGUgY2hpbGRyZW4uICBJZiBib3RoIGNoaWxkcmVu IGFyZSBibGFjaywgd2UgZmxpcCBhCmZldyBub2RlIGNvbG9ycyBhbmQgaXRlcmF0ZS4gIE90aGVy d2lzZSwgd2UgZG8gZWl0aGVyIG9uZSBvciB0d28gdHJlZQpyb3RhdGlvbnMsIGRlcGVuZGluZyBv biB0aGUgY29sb3Igb2YgdGhlICdvdGhlcicgY2hpbGQgb3Bwb3NpdGUgdG8gJ25vZGUnLAphbmQg dGhlbiB3ZSBhcmUgZG9uZS4KClRoZSBjb3JyZXNwb25kaW5nIGxvZ2ljIGhhZCBkdXBsaWNhdGUg Y2hlY2tzIGZvciB0aGUgY29sb3Igb2YgdGhlICdvdGhlcicKY2hpbGQgb3Bwb3NpdGUgdG8gJ25v ZGUnLiAgSXQgd2FzIGNoZWNraW5nIGl0IGZpcnN0IHRvIGRldGVybWluZSBpZiBib3RoCmNoaWxk cmVuIGFyZSBibGFjaywgYW5kIHRoZW4gdG8gZGV0ZXJtaW5lIGhvdyBtYW55IHRyZWUgcm90YXRp b25zIGFyZQpyZXF1aXJlZC4gIFJlYXJyYW5nZSB0aGUgbG9naWMgdG8gYXZvaWQgdGhhdCBleHRy YSBjaGVjay4KClNpZ25lZC1vZmYtYnk6IE1pY2hlbCBMZXNwaW5hc3NlIDx3YWxrZW5AZ29vZ2xl LmNvbT4KQ2M6IEFuZHJlYSBBcmNhbmdlbGkgPGFhcmNhbmdlQHJlZGhhdC5jb20+CkFja2VkLWJ5 OiBEYXZpZCBXb29kaG91c2UgPERhdmlkLldvb2Rob3VzZUBpbnRlbC5jb20+CkNjOiBSaWsgdmFu IFJpZWwgPHJpZWxAcmVkaGF0LmNvbT4KQ2M6IFBldGVyIFppamxzdHJhIDxhLnAuemlqbHN0cmFA Y2hlbGxvLm5sPgpDYzogRGFuaWVsIFNhbnRvcyA8ZGFuaWVsLnNhbnRvc0Bwb2JveC5jb20+CkNj OiBKZW5zIEF4Ym9lIDxheGJvZUBrZXJuZWwuZGs+CkNjOiAiRXJpYyBXLiBCaWVkZXJtYW4iIDxl YmllZGVybUB4bWlzc2lvbi5jb20+ClNpZ25lZC1vZmYtYnk6IEFuZHJldyBNb3J0b24gPGFrcG1A bGludXgtZm91bmRhdGlvbi5vcmc+ClNpZ25lZC1vZmYtYnk6IExpbnVzIFRvcnZhbGRzIDx0b3J2 YWxkc0BsaW51eC1mb3VuZGF0aW9uLm9yZz4KW0xpbnV4IGNvbW1pdCBlMTI1ZDE0NzFhNGY4ZjFi ZjdlYTlhODNkZWI4ZDIzY2I0MGJkNzEyXQoKUG9ydGVkIHRvIFhlbi4KClNpZ25lZC1vZmYtYnk6 IFByYXZlZW4gS3VtYXIgPGtwcmF2ZWVuLmxrbWxAZ21haWwuY29tPgotLS0KIHhlbi9jb21tb24v cmJ0cmVlLmMgfCA2OCArKysrKysrKysrKysrKysrKysrKysrKy0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLQogMSBmaWxlIGNoYW5nZWQsIDMwIGluc2VydGlvbnMoKyksIDM4IGRlbGV0aW9u cygtKQoKZGlmZiAtLWdpdCBhL3hlbi9jb21tb24vcmJ0cmVlLmMgYi94ZW4vY29tbW9uL3JidHJl ZS5jCmluZGV4IDI0OTAzNWM5MjMuLmE2NDkxZTU2MTAgMTAwNjQ0Ci0tLSBhL3hlbi9jb21tb24v cmJ0cmVlLmMKKysrIGIveGVuL2NvbW1vbi9yYnRyZWUuYwpAQCAtMjgzLDI4ICsyODMsMjQgQEAg c3RhdGljIHZvaWQgX19yYl9lcmFzZV9jb2xvcihzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0 IHJiX25vZGUgKnBhcmVudCwKIAkJCQlfX3JiX3JvdGF0ZV9sZWZ0KHBhcmVudCwgcm9vdCk7CiAJ CQkJb3RoZXIgPSBwYXJlbnQtPnJiX3JpZ2h0OwogCQkJfQotCQkJaWYgKCghb3RoZXItPnJiX2xl ZnQgfHwgcmJfaXNfYmxhY2sob3RoZXItPnJiX2xlZnQpKSAmJgotCQkJICAgICghb3RoZXItPnJi X3JpZ2h0IHx8IHJiX2lzX2JsYWNrKG90aGVyLT5yYl9yaWdodCkpKQotCQkJewotCQkJCXJiX3Nl dF9yZWQob3RoZXIpOwotCQkJCW5vZGUgPSBwYXJlbnQ7Ci0JCQkJcGFyZW50ID0gcmJfcGFyZW50 KG5vZGUpOwotCQkJfQotCQkJZWxzZQotCQkJewotCQkJCWlmICghb3RoZXItPnJiX3JpZ2h0IHx8 IHJiX2lzX2JsYWNrKG90aGVyLT5yYl9yaWdodCkpCi0JCQkJewotCQkJCQlyYl9zZXRfYmxhY2so b3RoZXItPnJiX2xlZnQpOworCQkJaWYgKCFvdGhlci0+cmJfcmlnaHQgfHwgcmJfaXNfYmxhY2so b3RoZXItPnJiX3JpZ2h0KSkgeworCQkJCWlmICghb3RoZXItPnJiX2xlZnQgfHwKKwkJCQkgICAg cmJfaXNfYmxhY2sob3RoZXItPnJiX2xlZnQpKSB7CiAJCQkJCXJiX3NldF9yZWQob3RoZXIpOwot CQkJCQlfX3JiX3JvdGF0ZV9yaWdodChvdGhlciwgcm9vdCk7Ci0JCQkJCW90aGVyID0gcGFyZW50 LT5yYl9yaWdodDsKKwkJCQkJbm9kZSA9IHBhcmVudDsKKwkJCQkJcGFyZW50ID0gcmJfcGFyZW50 KG5vZGUpOworCQkJCQljb250aW51ZTsKIAkJCQl9Ci0JCQkJcmJfc2V0X2NvbG9yKG90aGVyLCBy Yl9jb2xvcihwYXJlbnQpKTsKLQkJCQlyYl9zZXRfYmxhY2socGFyZW50KTsKLQkJCQlyYl9zZXRf YmxhY2sob3RoZXItPnJiX3JpZ2h0KTsKLQkJCQlfX3JiX3JvdGF0ZV9sZWZ0KHBhcmVudCwgcm9v dCk7Ci0JCQkJYnJlYWs7CisJCQkJcmJfc2V0X2JsYWNrKG90aGVyLT5yYl9sZWZ0KTsKKwkJCQly Yl9zZXRfcmVkKG90aGVyKTsKKwkJCQlfX3JiX3JvdGF0ZV9yaWdodChvdGhlciwgcm9vdCk7CisJ CQkJb3RoZXIgPSBwYXJlbnQtPnJiX3JpZ2h0OwogCQkJfQorCQkJcmJfc2V0X2NvbG9yKG90aGVy LCByYl9jb2xvcihwYXJlbnQpKTsKKwkJCXJiX3NldF9ibGFjayhwYXJlbnQpOworCQkJcmJfc2V0 X2JsYWNrKG90aGVyLT5yYl9yaWdodCk7CisJCQlfX3JiX3JvdGF0ZV9sZWZ0KHBhcmVudCwgcm9v dCk7CisJCQlicmVhazsKIAkJfSBlbHNlIHsKIAkJCW90aGVyID0gcGFyZW50LT5yYl9sZWZ0Owog CQkJaWYgKHJiX2lzX3JlZChvdGhlcikpCkBAIC0zMTQsMjggKzMxMCwyNCBAQCBzdGF0aWMgdm9p ZCBfX3JiX2VyYXNlX2NvbG9yKHN0cnVjdCByYl9ub2RlICpub2RlLCBzdHJ1Y3QgcmJfbm9kZSAq cGFyZW50LAogCQkJCV9fcmJfcm90YXRlX3JpZ2h0KHBhcmVudCwgcm9vdCk7CiAJCQkJb3RoZXIg PSBwYXJlbnQtPnJiX2xlZnQ7CiAJCQl9Ci0JCQlpZiAoKCFvdGhlci0+cmJfbGVmdCB8fCByYl9p c19ibGFjayhvdGhlci0+cmJfbGVmdCkpICYmCi0JCQkgICAgKCFvdGhlci0+cmJfcmlnaHQgfHwg cmJfaXNfYmxhY2sob3RoZXItPnJiX3JpZ2h0KSkpCi0JCQl7Ci0JCQkJcmJfc2V0X3JlZChvdGhl cik7Ci0JCQkJbm9kZSA9IHBhcmVudDsKLQkJCQlwYXJlbnQgPSByYl9wYXJlbnQobm9kZSk7Ci0J CQl9Ci0JCQllbHNlCi0JCQl7Ci0JCQkJaWYgKCFvdGhlci0+cmJfbGVmdCB8fCByYl9pc19ibGFj ayhvdGhlci0+cmJfbGVmdCkpCi0JCQkJewotCQkJCQlyYl9zZXRfYmxhY2sob3RoZXItPnJiX3Jp Z2h0KTsKKwkJCWlmICghb3RoZXItPnJiX2xlZnQgfHwgcmJfaXNfYmxhY2sob3RoZXItPnJiX2xl ZnQpKSB7CisJCQkJaWYgKCFvdGhlci0+cmJfcmlnaHQgfHwKKwkJCQkgICAgcmJfaXNfYmxhY2so b3RoZXItPnJiX3JpZ2h0KSkgewogCQkJCQlyYl9zZXRfcmVkKG90aGVyKTsKLQkJCQkJX19yYl9y b3RhdGVfbGVmdChvdGhlciwgcm9vdCk7Ci0JCQkJCW90aGVyID0gcGFyZW50LT5yYl9sZWZ0Owor CQkJCQlub2RlID0gcGFyZW50OworCQkJCQlwYXJlbnQgPSByYl9wYXJlbnQobm9kZSk7CisJCQkJ CWNvbnRpbnVlOwogCQkJCX0KLQkJCQlyYl9zZXRfY29sb3Iob3RoZXIsIHJiX2NvbG9yKHBhcmVu dCkpOwotCQkJCXJiX3NldF9ibGFjayhwYXJlbnQpOwotCQkJCXJiX3NldF9ibGFjayhvdGhlci0+ cmJfbGVmdCk7Ci0JCQkJX19yYl9yb3RhdGVfcmlnaHQocGFyZW50LCByb290KTsKLQkJCQlicmVh azsKKwkJCQlyYl9zZXRfYmxhY2sob3RoZXItPnJiX3JpZ2h0KTsKKwkJCQlyYl9zZXRfcmVkKG90 aGVyKTsKKwkJCQlfX3JiX3JvdGF0ZV9sZWZ0KG90aGVyLCByb290KTsKKwkJCQlvdGhlciA9IHBh cmVudC0+cmJfbGVmdDsKIAkJCX0KKwkJCXJiX3NldF9jb2xvcihvdGhlciwgcmJfY29sb3IocGFy ZW50KSk7CisJCQlyYl9zZXRfYmxhY2socGFyZW50KTsKKwkJCXJiX3NldF9ibGFjayhvdGhlci0+ cmJfbGVmdCk7CisJCQlfX3JiX3JvdGF0ZV9yaWdodChwYXJlbnQsIHJvb3QpOworCQkJYnJlYWs7 CiAJCX0KIAl9CiB9Ci0tIAoyLjEyLjAKCgpfX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f X19fX19fX19fX19fX19fXwpYZW4tZGV2ZWwgbWFpbGluZyBsaXN0Clhlbi1kZXZlbEBsaXN0cy54 ZW4ub3JnCmh0dHBzOi8vbGlzdHMueGVuLm9yZy94ZW4tZGV2ZWwK