From mboxrd@z Thu Jan 1 00:00:00 1970 From: Praveen Kumar Subject: [PATCH 10/17] rbtree: optimize case selection logic in __rb_erase_color() Date: Thu, 1 Jun 2017 02:17:01 +0530 Message-ID: <20170531204708.10470-11-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 , Rik van Riel , sstabellini@kernel.org, wei.liu2@citrix.com, Peter Zijlstra , 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 List-Id: xen-devel@lists.xenproject.org SW4gX19yYl9lcmFzZV9jb2xvcigpLCB3ZSBoYXZlIHRvIHNlbGVjdCBvbmUgb2YgMyBjYXNlcyBk ZXBlbmRpbmcgb24gdGhlCmNvbG9yIG9uIHRoZSAnb3RoZXInIG5vZGUgY2hpbGRyZW4uICBJZiBi b3RoIGNoaWxkcmVuIGFyZSBibGFjaywgd2UgZmxpcCBhCmZldyBub2RlIGNvbG9ycyBhbmQgaXRl cmF0ZS4gIE90aGVyd2lzZSwgd2UgZG8gZWl0aGVyIG9uZSBvciB0d28gdHJlZQpyb3RhdGlvbnMs IGRlcGVuZGluZyBvbiB0aGUgY29sb3Igb2YgdGhlICdvdGhlcicgY2hpbGQgb3Bwb3NpdGUgdG8g J25vZGUnLAphbmQgdGhlbiB3ZSBhcmUgZG9uZS4KClRoZSBjb3JyZXNwb25kaW5nIGxvZ2ljIGhh ZCBkdXBsaWNhdGUgY2hlY2tzIGZvciB0aGUgY29sb3Igb2YgdGhlICdvdGhlcicKY2hpbGQgb3Bw b3NpdGUgdG8gJ25vZGUnLiAgSXQgd2FzIGNoZWNraW5nIGl0IGZpcnN0IHRvIGRldGVybWluZSBp ZiBib3RoCmNoaWxkcmVuIGFyZSBibGFjaywgYW5kIHRoZW4gdG8gZGV0ZXJtaW5lIGhvdyBtYW55 IHRyZWUgcm90YXRpb25zIGFyZQpyZXF1aXJlZC4gIFJlYXJyYW5nZSB0aGUgbG9naWMgdG8gYXZv aWQgdGhhdCBleHRyYSBjaGVjay4KCmNvbW1pdCBlMTI1ZDE0NzFhNGY4ZjFiZjdlYTlhODNkZWI4 ZDIzY2I0MGJkNzEyIGZyb20gbGludXggdHJlZQoKU2lnbmVkLW9mZi1ieTogTWljaGVsIExlc3Bp bmFzc2UgPHdhbGtlbkBnb29nbGUuY29tPgpDYzogQW5kcmVhIEFyY2FuZ2VsaSA8YWFyY2FuZ2VA cmVkaGF0LmNvbT4KQWNrZWQtYnk6IERhdmlkIFdvb2Rob3VzZSA8RGF2aWQuV29vZGhvdXNlQGlu dGVsLmNvbT4KQ2M6IFJpayB2YW4gUmllbCA8cmllbEByZWRoYXQuY29tPgpDYzogUGV0ZXIgWmlq bHN0cmEgPGEucC56aWpsc3RyYUBjaGVsbG8ubmw+CkNjOiBEYW5pZWwgU2FudG9zIDxkYW5pZWwu c2FudG9zQHBvYm94LmNvbT4KQ2M6IEplbnMgQXhib2UgPGF4Ym9lQGtlcm5lbC5kaz4KQ2M6ICJF cmljIFcuIEJpZWRlcm1hbiIgPGViaWVkZXJtQHhtaXNzaW9uLmNvbT4KU2lnbmVkLW9mZi1ieTog QW5kcmV3IE1vcnRvbiA8YWtwbUBsaW51eC1mb3VuZGF0aW9uLm9yZz4KU2lnbmVkLW9mZi1ieTog TGludXMgVG9ydmFsZHMgPHRvcnZhbGRzQGxpbnV4LWZvdW5kYXRpb24ub3JnPgotLS0KIHhlbi9j b21tb24vcmJ0cmVlLmMgfCA2OSArKysrKysrKysrKysrKysrKysrKysrLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLQogMSBmaWxlIGNoYW5nZWQsIDI5IGluc2VydGlvbnMoKyksIDQwIGRl bGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3hlbi9jb21tb24vcmJ0cmVlLmMgYi94ZW4vY29tbW9u L3JidHJlZS5jCmluZGV4IDczNmUyYTU1YWEuLjFlNGNiMWVkMmMgMTAwNjQ0Ci0tLSBhL3hlbi9j b21tb24vcmJ0cmVlLmMKKysrIGIveGVuL2NvbW1vbi9yYnRyZWUuYwpAQCAtMjg4LDMxICsyODgs MjYgQEAgc3RhdGljIHZvaWQgX19yYl9lcmFzZV9jb2xvcihzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwg c3RydWN0IHJiX25vZGUgKnBhcmVudCwKICAgICAgICAgICAgICAgICBfX3JiX3JvdGF0ZV9sZWZ0 KHBhcmVudCwgcm9vdCk7CiAgICAgICAgICAgICAgICAgb3RoZXIgPSBwYXJlbnQtPnJiX3JpZ2h0 OwogICAgICAgICAgICAgfQotICAgICAgICAgICAgaWYgKCghb3RoZXItPnJiX2xlZnQgfHwgcmJf aXNfYmxhY2sob3RoZXItPnJiX2xlZnQpKSAmJgotICAgICAgICAgICAgICAgICghb3RoZXItPnJi X3JpZ2h0IHx8IHJiX2lzX2JsYWNrKG90aGVyLT5yYl9yaWdodCkpKQorICAgICAgICAgICAgaWYg KCFvdGhlci0+cmJfcmlnaHQgfHwgcmJfaXNfYmxhY2sob3RoZXItPnJiX3JpZ2h0KSkKICAgICAg ICAgICAgIHsKLSAgICAgICAgICAgICAgICByYl9zZXRfcmVkKG90aGVyKTsKLSAgICAgICAgICAg ICAgICBub2RlID0gcGFyZW50OwotICAgICAgICAgICAgICAgIHBhcmVudCA9IHJiX3BhcmVudChu b2RlKTsKLSAgICAgICAgICAgIH0KLSAgICAgICAgICAgIGVsc2UKLSAgICAgICAgICAgIHsKLSAg ICAgICAgICAgICAgICBpZiAoIW90aGVyLT5yYl9yaWdodCB8fCByYl9pc19ibGFjayhvdGhlci0+ cmJfcmlnaHQpKQorICAgICAgICAgICAgICAgIGlmICghb3RoZXItPnJiX2xlZnQgfHwgcmJfaXNf YmxhY2sob3RoZXItPnJiX2xlZnQpKQogICAgICAgICAgICAgICAgIHsKLSAgICAgICAgICAgICAg ICAgICAgc3RydWN0IHJiX25vZGUgKm9fbGVmdDsKLSAgICAgICAgICAgICAgICAgICAgaWYgKChv X2xlZnQgPSBvdGhlci0+cmJfbGVmdCkpCi0gICAgICAgICAgICAgICAgICAgICAgICByYl9zZXRf YmxhY2sob19sZWZ0KTsKICAgICAgICAgICAgICAgICAgICAgcmJfc2V0X3JlZChvdGhlcik7Ci0g ICAgICAgICAgICAgICAgICAgIF9fcmJfcm90YXRlX3JpZ2h0KG90aGVyLCByb290KTsKLSAgICAg ICAgICAgICAgICAgICAgb3RoZXIgPSBwYXJlbnQtPnJiX3JpZ2h0OworICAgICAgICAgICAgICAg ICAgICBub2RlID0gcGFyZW50OworICAgICAgICAgICAgICAgICAgICBwYXJlbnQgPSByYl9wYXJl bnQobm9kZSk7CisgICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOworCiAgICAgICAgICAgICAg ICAgfQotICAgICAgICAgICAgICAgIHJiX3NldF9jb2xvcihvdGhlciwgcmJfY29sb3IocGFyZW50 KSk7Ci0gICAgICAgICAgICAgICAgcmJfc2V0X2JsYWNrKHBhcmVudCk7Ci0gICAgICAgICAgICAg ICAgaWYgKG90aGVyLT5yYl9yaWdodCkKLSAgICAgICAgICAgICAgICAgICAgcmJfc2V0X2JsYWNr KG90aGVyLT5yYl9yaWdodCk7Ci0gICAgICAgICAgICAgICAgX19yYl9yb3RhdGVfbGVmdChwYXJl bnQsIHJvb3QpOwotICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAgICAgICAgIHJiX3Nl dF9ibGFjayhvdGhlci0+cmJfbGVmdCk7CisgICAgICAgICAgICAgICAgcmJfc2V0X3JlZChvdGhl cik7CisgICAgICAgICAgICAgICAgX19yYl9yb3RhdGVfcmlnaHQob3RoZXIsIHJvb3QpOworICAg ICAgICAgICAgICAgIG90aGVyID0gcGFyZW50LT5yYl9yaWdodDsKICAgICAgICAgICAgIH0KKyAg ICAgICAgICAgIHJiX3NldF9jb2xvcihvdGhlciwgcmJfY29sb3IocGFyZW50KSk7CisgICAgICAg ICAgICByYl9zZXRfYmxhY2socGFyZW50KTsKKyAgICAgICAgICAgIHJiX3NldF9ibGFjayhvdGhl ci0+cmJfcmlnaHQpOworICAgICAgICAgICAgX19yYl9yb3RhdGVfbGVmdChwYXJlbnQsIHJvb3Qp OworICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgIH0KICAgICAgICAgZWxzZQogICAgICAgICB7 CkBAIC0zMjQsMzEgKzMxOSwyNSBAQCBzdGF0aWMgdm9pZCBfX3JiX2VyYXNlX2NvbG9yKHN0cnVj dCByYl9ub2RlICpub2RlLCBzdHJ1Y3QgcmJfbm9kZSAqcGFyZW50LAogICAgICAgICAgICAgICAg IF9fcmJfcm90YXRlX3JpZ2h0KHBhcmVudCwgcm9vdCk7CiAgICAgICAgICAgICAgICAgb3RoZXIg PSBwYXJlbnQtPnJiX2xlZnQ7CiAgICAgICAgICAgICB9Ci0gICAgICAgICAgICBpZiAoKCFvdGhl ci0+cmJfbGVmdCB8fCByYl9pc19ibGFjayhvdGhlci0+cmJfbGVmdCkpICYmCi0gICAgICAgICAg ICAgICAgKCFvdGhlci0+cmJfcmlnaHQgfHwgcmJfaXNfYmxhY2sob3RoZXItPnJiX3JpZ2h0KSkp CisgICAgICAgICAgICBpZiAoIW90aGVyLT5yYl9sZWZ0IHx8IHJiX2lzX2JsYWNrKG90aGVyLT5y Yl9sZWZ0KSkKICAgICAgICAgICAgIHsKLSAgICAgICAgICAgICAgICByYl9zZXRfcmVkKG90aGVy KTsKLSAgICAgICAgICAgICAgICBub2RlID0gcGFyZW50OwotICAgICAgICAgICAgICAgIHBhcmVu dCA9IHJiX3BhcmVudChub2RlKTsKLSAgICAgICAgICAgIH0KLSAgICAgICAgICAgIGVsc2UKLSAg ICAgICAgICAgIHsKLSAgICAgICAgICAgICAgICBpZiAoIW90aGVyLT5yYl9sZWZ0IHx8IHJiX2lz X2JsYWNrKG90aGVyLT5yYl9sZWZ0KSkKKyAgICAgICAgICAgICAgICBpZiAoIW90aGVyLT5yYl9y aWdodCB8fCByYl9pc19ibGFjayhvdGhlci0+cmJfcmlnaHQpKQogICAgICAgICAgICAgICAgIHsK LSAgICAgICAgICAgICAgICAgICAgcmVnaXN0ZXIgc3RydWN0IHJiX25vZGUgKm9fcmlnaHQ7Ci0g ICAgICAgICAgICAgICAgICAgIGlmICgob19yaWdodCA9IG90aGVyLT5yYl9yaWdodCkpCi0gICAg ICAgICAgICAgICAgICAgICAgICByYl9zZXRfYmxhY2sob19yaWdodCk7CiAgICAgICAgICAgICAg ICAgICAgIHJiX3NldF9yZWQob3RoZXIpOwotICAgICAgICAgICAgICAgICAgICBfX3JiX3JvdGF0 ZV9sZWZ0KG90aGVyLCByb290KTsKLSAgICAgICAgICAgICAgICAgICAgb3RoZXIgPSBwYXJlbnQt PnJiX2xlZnQ7CisgICAgICAgICAgICAgICAgICAgIG5vZGUgPSBwYXJlbnQ7CisgICAgICAgICAg ICAgICAgICAgIHBhcmVudCA9IHJiX3BhcmVudChub2RlKTsKKyAgICAgICAgICAgICAgICAgICAg Y29udGludWU7CiAgICAgICAgICAgICAgICAgfQotICAgICAgICAgICAgICAgIHJiX3NldF9jb2xv cihvdGhlciwgcmJfY29sb3IocGFyZW50KSk7Ci0gICAgICAgICAgICAgICAgcmJfc2V0X2JsYWNr KHBhcmVudCk7Ci0gICAgICAgICAgICAgICAgaWYgKG90aGVyLT5yYl9sZWZ0KQotICAgICAgICAg ICAgICAgICAgICByYl9zZXRfYmxhY2sob3RoZXItPnJiX2xlZnQpOwotICAgICAgICAgICAgICAg IF9fcmJfcm90YXRlX3JpZ2h0KHBhcmVudCwgcm9vdCk7Ci0gICAgICAgICAgICAgICAgYnJlYWs7 CisgICAgICAgICAgICAgICAgcmJfc2V0X2JsYWNrKG90aGVyLT5yYl9yaWdodCk7CisgICAgICAg ICAgICAgICAgcmJfc2V0X3JlZChvdGhlcik7CisgICAgICAgICAgICAgICAgX19yYl9yb3RhdGVf bGVmdChvdGhlciwgcm9vdCk7CisgICAgICAgICAgICAgICAgb3RoZXIgPSBwYXJlbnQtPnJiX2xl ZnQ7CiAgICAgICAgICAgICB9CisgICAgICAgICAgICByYl9zZXRfY29sb3Iob3RoZXIsIHJiX2Nv bG9yKHBhcmVudCkpOworICAgICAgICAgICAgcmJfc2V0X2JsYWNrKHBhcmVudCk7CisgICAgICAg ICAgICByYl9zZXRfYmxhY2sob3RoZXItPnJiX2xlZnQpOworICAgICAgICAgICAgX19yYl9yb3Rh dGVfcmlnaHQocGFyZW50LCByb290KTsKKyAgICAgICAgICAgIGJyZWFrOwogICAgICAgICB9CiAg ICAgfQogfQotLSAKMi4xMi4wCgoKX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f X19fX19fX19fX18KWGVuLWRldmVsIG1haWxpbmcgbGlzdApYZW4tZGV2ZWxAbGlzdHMueGVuLm9y ZwpodHRwczovL2xpc3RzLnhlbi5vcmcveGVuLWRldmVsCg==