From mboxrd@z Thu Jan 1 00:00:00 1970 From: Praveen Kumar Subject: [Resend][PATCH 16/17] rbtree: low level optimizations in rb_erase() Date: Thu, 1 Jun 2017 02:50:55 +0530 Message-ID: <20170531212056.10583-17-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 VmFyaW91cyBtaW5vciBvcHRpbWl6YXRpb25zIGluIHJiX2VyYXNlKCk6Ci0gQXZvaWQgbXVsdGlw bGUgbG9hZGluZyBvZiBub2RlLT5fX3JiX3BhcmVudF9jb2xvciB3aGVuIGNvbXB1dGluZyBwYXJl bnQKICBhbmQgY29sb3IgaW5mb3JtYXRpb24gKHBvc3NpYmx5IG5vdCBpbiBjbG9zZSBzZXF1ZW5j ZSwgYXMgdGhlcmUgbWlnaHQKICBiZSBmdXJ0aGVyIGJyYW5jaGVzIGluIHRoZSBhbGdvcml0aG0p Ci0gSW4gdGhlIDEtY2hpbGQgc3ViY2FzZSBvZiBjYXNlIDEsIGNvcHkgdGhlIF9fcmJfcGFyZW50 X2NvbG9yIGZpZWxkIGZyb20KICB0aGUgZXJhc2VkIG5vZGUgdG8gdGhlIGNoaWxkIGluc3RlYWQg b2YgcmVjb21wdXRpbmcgaXQgZnJvbSB0aGUgZGVzaXJlZAogIHBhcmVudCBhbmQgY29sb3IKLSBX aGVuIHNlYXJjaGluZyBmb3IgdGhlIGVyYXNlZCBub2RlJ3Mgc3VjY2Vzc29yLCBkaWZmZXJlbnRp YXRlIGJldHdlZW4KICBjYXNlcyAyIGFuZCAzIGJhc2VkIG9uIHdoZXRoZXIgYW55IGxlZnQgbGlu a3Mgd2VyZSBmb2xsb3dlZC4gVGhpcyBhdm9pZHMKICBhIGNvbmRpdGlvbiBsYXRlciBkb3duLgot IEluIGNhc2UgMywga2VlcCBhIHBvaW50ZXIgdG8gdGhlIGVyYXNlZCBub2RlJ3MgcmlnaHQgY2hp bGQgc28gd2UgZG9uJ3QKICBoYXZlIHRvIHJlZmV0Y2ggaXQgbGF0ZXIgdG8gYWRqdXN0IGl0cyBw YXJlbnQuCi0gSW4gdGhlIG5vLWNoaWxkcyBzdWJjYXNlIG9mIGNhc2VzIDIgYW5kIDMsIHBsYWNl IHRoZSByZWJhbGFuY2UgYXNzaWdtZW50CiAgbGFzdCBzbyB0aGF0IHRoZSBjb21waWxlciBjYW4g cmVtb3ZlIHRoZSBmb2xsb3dpbmcgaWYocmViYWxhbmNlKSB0ZXN0LgoKQWxzbywgYWRkZWQgc29t ZSBjb21tZW50cyB0byBpbGx1c3RyYXRlIGNhc2VzIDIgYW5kIDMuCgpjb21taXQgNGYwMzVhZDY3 ZjQ2MzNjMjMzY2IzNjQyNzExZDQ5YjRlZmM5YzgyZCBmcm9tIExpbnV4IHRyZWUKClNpZ25lZC1v ZmYtYnk6IFByYXZlZW4gS3VtYXIgPGtwcmF2ZWVuLmxrbWxAZ21haWwuY29tPgotLS0KIHhlbi9j b21tb24vcmJ0cmVlLmMgfCAxMDIgKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKy0t LS0tLS0tLS0tLS0tLS0tLQogMSBmaWxlIGNoYW5nZWQsIDY3IGluc2VydGlvbnMoKyksIDM1IGRl bGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3hlbi9jb21tb24vcmJ0cmVlLmMgYi94ZW4vY29tbW9u L3JidHJlZS5jCmluZGV4IDZlMzdlOTYwYWIuLjgzYjQ4OTJmNTQgMTAwNjQ0Ci0tLSBhL3hlbi9j b21tb24vcmJ0cmVlLmMKKysrIGIveGVuL2NvbW1vbi9yYnRyZWUuYwpAQCAtNDYsOSArNDYsMTQg QEAKICNkZWZpbmUgICAgUkJfUkVEICAgIDAKICNkZWZpbmUgICAgUkJfQkxBQ0sgIDEKIAotI2Rl ZmluZSByYl9jb2xvcihyKSAgICAgKChyKS0+X19yYl9wYXJlbnRfY29sb3IgJiAxKQotI2RlZmlu ZSByYl9pc19yZWQocikgICAgKCFyYl9jb2xvcihyKSkKLSNkZWZpbmUgcmJfaXNfYmxhY2socikg IHJiX2NvbG9yKHIpCisjZGVmaW5lIF9fcmJfcGFyZW50KHBjKSAgICAoKHN0cnVjdCByYl9ub2Rl ICopKHBjICYgfjMpKQorCisjZGVmaW5lIF9fcmJfY29sb3IocGMpICAgICAoKHBjKSAmIDEpCisj ZGVmaW5lIF9fcmJfaXNfYmxhY2socGMpICBfX3JiX2NvbG9yKHBjKQorI2RlZmluZSBfX3JiX2lz X3JlZChwYykgICAgKCFfX3JiX2NvbG9yKHBjKSkKKyNkZWZpbmUgcmJfY29sb3IocmIpICAgICAg IF9fcmJfY29sb3IoKHJiKS0+X19yYl9wYXJlbnRfY29sb3IpCisjZGVmaW5lIHJiX2lzX3JlZChy YikgICAgICBfX3JiX2lzX3JlZCgocmIpLT5fX3JiX3BhcmVudF9jb2xvcikKKyNkZWZpbmUgcmJf aXNfYmxhY2socmIpICAgIF9fcmJfaXNfYmxhY2soKHJiKS0+X19yYl9wYXJlbnRfY29sb3IpCiAK IHN0YXRpYyBpbmxpbmUgdm9pZCByYl9zZXRfYmxhY2soc3RydWN0IHJiX25vZGUgKnJiKQogewpA QCAtMzg3LDYgKzM5Miw3IEBAIHZvaWQgcmJfZXJhc2Uoc3RydWN0IHJiX25vZGUgKm5vZGUsIHN0 cnVjdCByYl9yb290ICpyb290KQogewogICAgIHN0cnVjdCByYl9ub2RlICpjaGlsZCA9IG5vZGUt PnJiX3JpZ2h0LCAqdG1wID0gbm9kZS0+cmJfbGVmdDsKICAgICBzdHJ1Y3QgcmJfbm9kZSAqcGFy ZW50LCAqcmViYWxhbmNlOworICAgIHVuc2lnbmVkIGxvbmcgcGM7CiAKICAgICBpZiAoIXRtcCkK ICAgICB7CkBAIC0zOTgsNTMgKzQwNCw3OSBAQCB2b2lkIHJiX2VyYXNlKHN0cnVjdCByYl9ub2Rl ICpub2RlLCBzdHJ1Y3QgcmJfcm9vdCAqcm9vdCkKICAgICAgICAgICogc28gYXMgdG8gYnlwYXNz IF9fcmJfZXJhc2VfY29sb3IoKSBsYXRlciBvbi4KICAgICAgICAgICovCiAKLSAgICAgICAgcGFy ZW50ID0gcmJfcGFyZW50KG5vZGUpOworICAgICAgICBwYyA9IG5vZGUtPl9fcmJfcGFyZW50X2Nv bG9yOworICAgICAgICBwYXJlbnQgPSBfX3JiX3BhcmVudChwYyk7CiAgICAgICAgIF9fcmJfY2hh bmdlX2NoaWxkKG5vZGUsIGNoaWxkLCBwYXJlbnQsIHJvb3QpOwogICAgICAgICBpZiAoY2hpbGQp CiAgICAgICAgIHsKLSAgICAgICAgICAgIHJiX3NldF9wYXJlbnRfY29sb3IoY2hpbGQsIHBhcmVu dCwgUkJfQkxBQ0spOworICAgICAgICAgICAgY2hpbGQtPl9fcmJfcGFyZW50X2NvbG9yID0gcGM7 CiAgICAgICAgICAgICByZWJhbGFuY2UgPSBOVUxMOwotICAgICAgICB9IGVsc2UgewotICAgICAg ICAgICAgcmViYWxhbmNlID0gcmJfaXNfYmxhY2sobm9kZSkgPyBwYXJlbnQgOiBOVUxMOwotICAg ICAgICB9CisgICAgICAgIH0gZWxzZQorICAgICAgICAgICAgcmViYWxhbmNlID0gX19yYl9pc19i bGFjayhwYykgPyBwYXJlbnQgOiBOVUxMOwogICAgIH0gZWxzZSBpZiAoIWNoaWxkKSB7CiAgICAg ICAgIC8qIFN0aWxsIGNhc2UgMSwgYnV0IHRoaXMgdGltZSB0aGUgY2hpbGQgaXMgbm9kZS0+cmJf bGVmdCAqLwotICAgICAgICBwYXJlbnQgPSByYl9wYXJlbnQobm9kZSk7CisgICAgICAgIHRtcC0+ X19yYl9wYXJlbnRfY29sb3IgPSBwYyA9IG5vZGUtPl9fcmJfcGFyZW50X2NvbG9yOworICAgICAg ICBwYXJlbnQgPSBfX3JiX3BhcmVudChwYyk7CiAgICAgICAgIF9fcmJfY2hhbmdlX2NoaWxkKG5v ZGUsIHRtcCwgcGFyZW50LCByb290KTsKLSAgICAgICAgcmJfc2V0X3BhcmVudF9jb2xvcih0bXAs IHBhcmVudCwgUkJfQkxBQ0spOwogICAgICAgICByZWJhbGFuY2UgPSBOVUxMOwogICAgIH0gZWxz ZSB7Ci0gICAgICAgIHN0cnVjdCByYl9ub2RlICpvbGQgPSBub2RlLCAqbGVmdDsKLQotICAgICAg ICBub2RlID0gY2hpbGQ7Ci0gICAgICAgIHdoaWxlICgobGVmdCA9IG5vZGUtPnJiX2xlZnQpICE9 IE5VTEwpCi0gICAgICAgICAgICBub2RlID0gbGVmdDsKLQotICAgICAgICBfX3JiX2NoYW5nZV9j aGlsZChvbGQsIG5vZGUsIHJiX3BhcmVudChvbGQpLCByb290KTsKLQotICAgICAgICBjaGlsZCA9 IG5vZGUtPnJiX3JpZ2h0OwotICAgICAgICBwYXJlbnQgPSByYl9wYXJlbnQobm9kZSk7Ci0KLSAg ICAgICAgaWYgKHBhcmVudCA9PSBvbGQpIHsKLSAgICAgICAgICAgIHBhcmVudCA9IG5vZGU7Cisg ICAgICAgIHN0cnVjdCByYl9ub2RlICpzdWNjZXNzb3IgPSBjaGlsZCwgKmNoaWxkMjsKKyAgICAg ICAgdG1wID0gY2hpbGQtPnJiX2xlZnQ7CisgICAgICAgIGlmICghdG1wKQorICAgICAgICB7Cisg ICAgICAgICAgICAvKgorICAgICAgICAgICAgICogQ2FzZSAyOiBub2RlJ3Mgc3VjY2Vzc29yIGlz IGl0cyByaWdodCBjaGlsZAorICAgICAgICAgICAgICoKKyAgICAgICAgICAgICAqICAgIChuKSAg ICAgICAgICAocykKKyAgICAgICAgICAgICAqICAgIC8gXCAgICAgICAgICAvIFwKKyAgICAgICAg ICAgICAqICAoeCkgKHMpICAtPiAgKHgpIChjKQorICAgICAgICAgICAgICogICAgICAgIFwKKyAg ICAgICAgICAgICAqICAgICAgICAoYykKKyAgICAgICAgICAgICAqLworICAgICAgICAgICAgcGFy ZW50ID0gY2hpbGQ7CisgICAgICAgICAgICBjaGlsZDIgPSBjaGlsZC0+cmJfcmlnaHQ7CiAgICAg ICAgIH0gZWxzZSB7Ci0gICAgICAgICAgICBwYXJlbnQtPnJiX2xlZnQgPSBjaGlsZDsKLQotICAg ICAgICAgICAgbm9kZS0+cmJfcmlnaHQgPSBvbGQtPnJiX3JpZ2h0OwotICAgICAgICAgICAgcmJf c2V0X3BhcmVudChvbGQtPnJiX3JpZ2h0LCBub2RlKTsKKyAgICAgICAgICAgIC8qCisgICAgICAg ICAgICAgKiBDYXNlIDM6IG5vZGUncyBzdWNjZXNzb3IgaXMgbGVmdG1vc3QgdW5kZXIKKyAgICAg ICAgICAgICAqIG5vZGUncyByaWdodCBjaGlsZCBzdWJ0cmVlCisgICAgICAgICAgICAgKgorICAg ICAgICAgICAgICogICAgKG4pICAgICAgICAgIChzKQorICAgICAgICAgICAgICogICAgLyBcICAg ICAgICAgIC8gXAorICAgICAgICAgICAgICogICh4KSAoeSkgIC0+ICAoeCkgKHkpCisgICAgICAg ICAgICAgKiAgICAgIC8gICAgICAgICAgICAvCisgICAgICAgICAgICAgKiAgICAocCkgICAgICAg ICAgKHApCisgICAgICAgICAgICAgKiAgICAvICAgICAgICAgICAgLworICAgICAgICAgICAgICog IChzKSAgICAgICAgICAoYykKKyAgICAgICAgICAgICAqICAgIFwKKyAgICAgICAgICAgICAqICAg IChjKQorICAgICAgICAgICAgICovCisgICAgICAgICAgICBkbworICAgICAgICAgICAgeworICAg ICAgICAgICAgICAgIHBhcmVudCA9IHN1Y2Nlc3NvcjsKKyAgICAgICAgICAgICAgICBzdWNjZXNz b3IgPSB0bXA7CisgICAgICAgICAgICAgICAgdG1wID0gdG1wLT5yYl9sZWZ0OworICAgICAgICAg ICAgfSB3aGlsZSAodG1wKTsKKyAgICAgICAgICAgIHBhcmVudC0+cmJfbGVmdCA9IGNoaWxkMiA9 IHN1Y2Nlc3Nvci0+cmJfcmlnaHQ7CisgICAgICAgICAgICBzdWNjZXNzb3ItPnJiX3JpZ2h0ID0g Y2hpbGQ7CisgICAgICAgICAgICByYl9zZXRfcGFyZW50KGNoaWxkLCBzdWNjZXNzb3IpOwogICAg ICAgICB9CiAKLSAgICAgICAgaWYgKGNoaWxkKSB7Ci0gICAgICAgICAgICByYl9zZXRfcGFyZW50 X2NvbG9yKGNoaWxkLCBwYXJlbnQsIFJCX0JMQUNLKTsKKyAgICAgICAgc3VjY2Vzc29yLT5yYl9s ZWZ0ID0gdG1wID0gbm9kZS0+cmJfbGVmdDsKKyAgICAgICAgcmJfc2V0X3BhcmVudCh0bXAsIHN1 Y2Nlc3Nvcik7CisKKyAgICAgICAgcGMgPSBub2RlLT5fX3JiX3BhcmVudF9jb2xvcjsKKyAgICAg ICAgdG1wID0gX19yYl9wYXJlbnQocGMpOworICAgICAgICBfX3JiX2NoYW5nZV9jaGlsZChub2Rl LCBzdWNjZXNzb3IsIHRtcCwgcm9vdCk7CisgICAgICAgIGlmIChjaGlsZDIpCisgICAgICAgIHsK KyAgICAgICAgICAgIHN1Y2Nlc3Nvci0+X19yYl9wYXJlbnRfY29sb3IgPSBwYzsKKyAgICAgICAg ICAgIHJiX3NldF9wYXJlbnRfY29sb3IoY2hpbGQyLCBwYXJlbnQsIFJCX0JMQUNLKTsKICAgICAg ICAgICAgIHJlYmFsYW5jZSA9IE5VTEw7CiAgICAgICAgIH0gZWxzZSB7Ci0gICAgICAgICAgICBy ZWJhbGFuY2UgPSByYl9pc19ibGFjayhub2RlKSA/IHBhcmVudCA6IE5VTEw7CisgICAgICAgICAg ICB1bnNpZ25lZCBsb25nIHBjMiA9IHN1Y2Nlc3Nvci0+X19yYl9wYXJlbnRfY29sb3I7CisgICAg ICAgICAgICBzdWNjZXNzb3ItPl9fcmJfcGFyZW50X2NvbG9yID0gcGM7CisgICAgICAgICAgICBy ZWJhbGFuY2UgPSBfX3JiX2lzX2JsYWNrKHBjMikgPyBwYXJlbnQgOiBOVUxMOwogICAgICAgICB9 Ci0KLSAgICAgICAgbm9kZS0+X19yYl9wYXJlbnRfY29sb3IgPSBvbGQtPl9fcmJfcGFyZW50X2Nv bG9yOwotICAgICAgICBub2RlLT5yYl9sZWZ0ID0gb2xkLT5yYl9sZWZ0OwotCi0gICAgICAgIHJi X3NldF9wYXJlbnQob2xkLT5yYl9sZWZ0LCBub2RlKTsKICAgICB9CiAKICAgICBpZiAocmViYWxh bmNlKQotLSAKMi4xMi4wCgoKX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f X19fX19fX18KWGVuLWRldmVsIG1haWxpbmcgbGlzdApYZW4tZGV2ZWxAbGlzdHMueGVuLm9yZwpo dHRwczovL2xpc3RzLnhlbi5vcmcveGVuLWRldmVsCg==