From mboxrd@z Thu Jan 1 00:00:00 1970 From: Praveen Kumar Subject: [Resend][PATCH 10/17] rbtree: optimize case selection logic in __rb_erase_color() Date: Thu, 1 Jun 2017 02:50:49 +0530 Message-ID: <20170531212056.10583-11-kpraveen.lkml@gmail.com> References: <20170531212056.10583-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: <20170531212056.10583-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, Praveen Kumar , jbeulich@suse.com List-Id: xen-devel@lists.xenproject.org SW4gX19yYl9lcmFzZV9jb2xvcigpLCB3ZSBoYXZlIHRvIHNlbGVjdCBvbmUgb2YgMyBjYXNlcyBk ZXBlbmRpbmcgb24gdGhlCmNvbG9yIG9uIHRoZSAnb3RoZXInIG5vZGUgY2hpbGRyZW4uICBJZiBi b3RoIGNoaWxkcmVuIGFyZSBibGFjaywgd2UgZmxpcCBhCmZldyBub2RlIGNvbG9ycyBhbmQgaXRl cmF0ZS4gIE90aGVyd2lzZSwgd2UgZG8gZWl0aGVyIG9uZSBvciB0d28gdHJlZQpyb3RhdGlvbnMs IGRlcGVuZGluZyBvbiB0aGUgY29sb3Igb2YgdGhlICdvdGhlcicgY2hpbGQgb3Bwb3NpdGUgdG8g J25vZGUnLAphbmQgdGhlbiB3ZSBhcmUgZG9uZS4KClRoZSBjb3JyZXNwb25kaW5nIGxvZ2ljIGhh ZCBkdXBsaWNhdGUgY2hlY2tzIGZvciB0aGUgY29sb3Igb2YgdGhlICdvdGhlcicKY2hpbGQgb3Bw b3NpdGUgdG8gJ25vZGUnLiAgSXQgd2FzIGNoZWNraW5nIGl0IGZpcnN0IHRvIGRldGVybWluZSBp ZiBib3RoCmNoaWxkcmVuIGFyZSBibGFjaywgYW5kIHRoZW4gdG8gZGV0ZXJtaW5lIGhvdyBtYW55 IHRyZWUgcm90YXRpb25zIGFyZQpyZXF1aXJlZC4gIFJlYXJyYW5nZSB0aGUgbG9naWMgdG8gYXZv aWQgdGhhdCBleHRyYSBjaGVjay4KCmNvbW1pdCBlMTI1ZDE0NzFhNGY4ZjFiZjdlYTlhODNkZWI4 ZDIzY2I0MGJkNzEyIGZyb20gbGludXggdHJlZQoKU2lnbmVkLW9mZi1ieTogUHJhdmVlbiBLdW1h ciA8a3ByYXZlZW4ubGttbEBnbWFpbC5jb20+Ci0tLQogeGVuL2NvbW1vbi9yYnRyZWUuYyB8IDY5 ICsrKysrKysrKysrKysrKysrKysrKystLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCiAx IGZpbGUgY2hhbmdlZCwgMjkgaW5zZXJ0aW9ucygrKSwgNDAgZGVsZXRpb25zKC0pCgpkaWZmIC0t Z2l0IGEveGVuL2NvbW1vbi9yYnRyZWUuYyBiL3hlbi9jb21tb24vcmJ0cmVlLmMKaW5kZXggNzM2 ZTJhNTVhYS4uMWU0Y2IxZWQyYyAxMDA2NDQKLS0tIGEveGVuL2NvbW1vbi9yYnRyZWUuYworKysg Yi94ZW4vY29tbW9uL3JidHJlZS5jCkBAIC0yODgsMzEgKzI4OCwyNiBAQCBzdGF0aWMgdm9pZCBf X3JiX2VyYXNlX2NvbG9yKHN0cnVjdCByYl9ub2RlICpub2RlLCBzdHJ1Y3QgcmJfbm9kZSAqcGFy ZW50LAogICAgICAgICAgICAgICAgIF9fcmJfcm90YXRlX2xlZnQocGFyZW50LCByb290KTsKICAg ICAgICAgICAgICAgICBvdGhlciA9IHBhcmVudC0+cmJfcmlnaHQ7CiAgICAgICAgICAgICB9Ci0g ICAgICAgICAgICBpZiAoKCFvdGhlci0+cmJfbGVmdCB8fCByYl9pc19ibGFjayhvdGhlci0+cmJf bGVmdCkpICYmCi0gICAgICAgICAgICAgICAgKCFvdGhlci0+cmJfcmlnaHQgfHwgcmJfaXNfYmxh Y2sob3RoZXItPnJiX3JpZ2h0KSkpCisgICAgICAgICAgICBpZiAoIW90aGVyLT5yYl9yaWdodCB8 fCByYl9pc19ibGFjayhvdGhlci0+cmJfcmlnaHQpKQogICAgICAgICAgICAgewotICAgICAgICAg ICAgICAgIHJiX3NldF9yZWQob3RoZXIpOwotICAgICAgICAgICAgICAgIG5vZGUgPSBwYXJlbnQ7 Ci0gICAgICAgICAgICAgICAgcGFyZW50ID0gcmJfcGFyZW50KG5vZGUpOwotICAgICAgICAgICAg fQotICAgICAgICAgICAgZWxzZQotICAgICAgICAgICAgewotICAgICAgICAgICAgICAgIGlmICgh b3RoZXItPnJiX3JpZ2h0IHx8IHJiX2lzX2JsYWNrKG90aGVyLT5yYl9yaWdodCkpCisgICAgICAg ICAgICAgICAgaWYgKCFvdGhlci0+cmJfbGVmdCB8fCByYl9pc19ibGFjayhvdGhlci0+cmJfbGVm dCkpCiAgICAgICAgICAgICAgICAgewotICAgICAgICAgICAgICAgICAgICBzdHJ1Y3QgcmJfbm9k ZSAqb19sZWZ0OwotICAgICAgICAgICAgICAgICAgICBpZiAoKG9fbGVmdCA9IG90aGVyLT5yYl9s ZWZ0KSkKLSAgICAgICAgICAgICAgICAgICAgICAgIHJiX3NldF9ibGFjayhvX2xlZnQpOwogICAg ICAgICAgICAgICAgICAgICByYl9zZXRfcmVkKG90aGVyKTsKLSAgICAgICAgICAgICAgICAgICAg X19yYl9yb3RhdGVfcmlnaHQob3RoZXIsIHJvb3QpOwotICAgICAgICAgICAgICAgICAgICBvdGhl ciA9IHBhcmVudC0+cmJfcmlnaHQ7CisgICAgICAgICAgICAgICAgICAgIG5vZGUgPSBwYXJlbnQ7 CisgICAgICAgICAgICAgICAgICAgIHBhcmVudCA9IHJiX3BhcmVudChub2RlKTsKKyAgICAgICAg ICAgICAgICAgICAgY29udGludWU7CisKICAgICAgICAgICAgICAgICB9Ci0gICAgICAgICAgICAg ICAgcmJfc2V0X2NvbG9yKG90aGVyLCByYl9jb2xvcihwYXJlbnQpKTsKLSAgICAgICAgICAgICAg ICByYl9zZXRfYmxhY2socGFyZW50KTsKLSAgICAgICAgICAgICAgICBpZiAob3RoZXItPnJiX3Jp Z2h0KQotICAgICAgICAgICAgICAgICAgICByYl9zZXRfYmxhY2sob3RoZXItPnJiX3JpZ2h0KTsK LSAgICAgICAgICAgICAgICBfX3JiX3JvdGF0ZV9sZWZ0KHBhcmVudCwgcm9vdCk7Ci0gICAgICAg ICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAgcmJfc2V0X2JsYWNrKG90aGVyLT5yYl9s ZWZ0KTsKKyAgICAgICAgICAgICAgICByYl9zZXRfcmVkKG90aGVyKTsKKyAgICAgICAgICAgICAg ICBfX3JiX3JvdGF0ZV9yaWdodChvdGhlciwgcm9vdCk7CisgICAgICAgICAgICAgICAgb3RoZXIg PSBwYXJlbnQtPnJiX3JpZ2h0OwogICAgICAgICAgICAgfQorICAgICAgICAgICAgcmJfc2V0X2Nv bG9yKG90aGVyLCByYl9jb2xvcihwYXJlbnQpKTsKKyAgICAgICAgICAgIHJiX3NldF9ibGFjayhw YXJlbnQpOworICAgICAgICAgICAgcmJfc2V0X2JsYWNrKG90aGVyLT5yYl9yaWdodCk7CisgICAg ICAgICAgICBfX3JiX3JvdGF0ZV9sZWZ0KHBhcmVudCwgcm9vdCk7CisgICAgICAgICAgICBicmVh azsKICAgICAgICAgfQogICAgICAgICBlbHNlCiAgICAgICAgIHsKQEAgLTMyNCwzMSArMzE5LDI1 IEBAIHN0YXRpYyB2b2lkIF9fcmJfZXJhc2VfY29sb3Ioc3RydWN0IHJiX25vZGUgKm5vZGUsIHN0 cnVjdCByYl9ub2RlICpwYXJlbnQsCiAgICAgICAgICAgICAgICAgX19yYl9yb3RhdGVfcmlnaHQo cGFyZW50LCByb290KTsKICAgICAgICAgICAgICAgICBvdGhlciA9IHBhcmVudC0+cmJfbGVmdDsK ICAgICAgICAgICAgIH0KLSAgICAgICAgICAgIGlmICgoIW90aGVyLT5yYl9sZWZ0IHx8IHJiX2lz X2JsYWNrKG90aGVyLT5yYl9sZWZ0KSkgJiYKLSAgICAgICAgICAgICAgICAoIW90aGVyLT5yYl9y aWdodCB8fCByYl9pc19ibGFjayhvdGhlci0+cmJfcmlnaHQpKSkKKyAgICAgICAgICAgIGlmICgh b3RoZXItPnJiX2xlZnQgfHwgcmJfaXNfYmxhY2sob3RoZXItPnJiX2xlZnQpKQogICAgICAgICAg ICAgewotICAgICAgICAgICAgICAgIHJiX3NldF9yZWQob3RoZXIpOwotICAgICAgICAgICAgICAg IG5vZGUgPSBwYXJlbnQ7Ci0gICAgICAgICAgICAgICAgcGFyZW50ID0gcmJfcGFyZW50KG5vZGUp OwotICAgICAgICAgICAgfQotICAgICAgICAgICAgZWxzZQotICAgICAgICAgICAgewotICAgICAg ICAgICAgICAgIGlmICghb3RoZXItPnJiX2xlZnQgfHwgcmJfaXNfYmxhY2sob3RoZXItPnJiX2xl ZnQpKQorICAgICAgICAgICAgICAgIGlmICghb3RoZXItPnJiX3JpZ2h0IHx8IHJiX2lzX2JsYWNr KG90aGVyLT5yYl9yaWdodCkpCiAgICAgICAgICAgICAgICAgewotICAgICAgICAgICAgICAgICAg ICByZWdpc3RlciBzdHJ1Y3QgcmJfbm9kZSAqb19yaWdodDsKLSAgICAgICAgICAgICAgICAgICAg aWYgKChvX3JpZ2h0ID0gb3RoZXItPnJiX3JpZ2h0KSkKLSAgICAgICAgICAgICAgICAgICAgICAg IHJiX3NldF9ibGFjayhvX3JpZ2h0KTsKICAgICAgICAgICAgICAgICAgICAgcmJfc2V0X3JlZChv dGhlcik7Ci0gICAgICAgICAgICAgICAgICAgIF9fcmJfcm90YXRlX2xlZnQob3RoZXIsIHJvb3Qp OwotICAgICAgICAgICAgICAgICAgICBvdGhlciA9IHBhcmVudC0+cmJfbGVmdDsKKyAgICAgICAg ICAgICAgICAgICAgbm9kZSA9IHBhcmVudDsKKyAgICAgICAgICAgICAgICAgICAgcGFyZW50ID0g cmJfcGFyZW50KG5vZGUpOworICAgICAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAg ICAgICAgICB9Ci0gICAgICAgICAgICAgICAgcmJfc2V0X2NvbG9yKG90aGVyLCByYl9jb2xvcihw YXJlbnQpKTsKLSAgICAgICAgICAgICAgICByYl9zZXRfYmxhY2socGFyZW50KTsKLSAgICAgICAg ICAgICAgICBpZiAob3RoZXItPnJiX2xlZnQpCi0gICAgICAgICAgICAgICAgICAgIHJiX3NldF9i bGFjayhvdGhlci0+cmJfbGVmdCk7Ci0gICAgICAgICAgICAgICAgX19yYl9yb3RhdGVfcmlnaHQo cGFyZW50LCByb290KTsKLSAgICAgICAgICAgICAgICBicmVhazsKKyAgICAgICAgICAgICAgICBy Yl9zZXRfYmxhY2sob3RoZXItPnJiX3JpZ2h0KTsKKyAgICAgICAgICAgICAgICByYl9zZXRfcmVk KG90aGVyKTsKKyAgICAgICAgICAgICAgICBfX3JiX3JvdGF0ZV9sZWZ0KG90aGVyLCByb290KTsK KyAgICAgICAgICAgICAgICBvdGhlciA9IHBhcmVudC0+cmJfbGVmdDsKICAgICAgICAgICAgIH0K KyAgICAgICAgICAgIHJiX3NldF9jb2xvcihvdGhlciwgcmJfY29sb3IocGFyZW50KSk7CisgICAg ICAgICAgICByYl9zZXRfYmxhY2socGFyZW50KTsKKyAgICAgICAgICAgIHJiX3NldF9ibGFjayhv dGhlci0+cmJfbGVmdCk7CisgICAgICAgICAgICBfX3JiX3JvdGF0ZV9yaWdodChwYXJlbnQsIHJv b3QpOworICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgIH0KICAgICB9CiB9Ci0tIAoyLjEyLjAK CgpfX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fXwpYZW4tZGV2 ZWwgbWFpbGluZyBsaXN0Clhlbi1kZXZlbEBsaXN0cy54ZW4ub3JnCmh0dHBzOi8vbGlzdHMueGVu Lm9yZy94ZW4tZGV2ZWwK