From mboxrd@z Thu Jan  1 00:00:00 1970
From: Lucas Stach <l.stach@pengutronix.de>
Subject: Re: [PATCH v4 1/2] drm: Improve drm_mm search (and fix topdown
 allocation) with rbtrees
Date: Thu, 02 Feb 2017 14:33:54 +0100
Message-ID: <1486042434.23471.45.camel@pengutronix.de>
References: <20170202114434.3060-1-chris@chris-wilson.co.uk>
Mime-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
Return-path: <dri-devel-bounces@lists.freedesktop.org>
In-Reply-To: <20170202114434.3060-1-chris@chris-wilson.co.uk>
List-Unsubscribe: <https://lists.freedesktop.org/mailman/options/dri-devel>,
 <mailto:dri-devel-request@lists.freedesktop.org?subject=unsubscribe>
List-Archive: <https://lists.freedesktop.org/archives/dri-devel>
List-Post: <mailto:dri-devel@lists.freedesktop.org>
List-Help: <mailto:dri-devel-request@lists.freedesktop.org?subject=help>
List-Subscribe: <https://lists.freedesktop.org/mailman/listinfo/dri-devel>,
 <mailto:dri-devel-request@lists.freedesktop.org?subject=subscribe>
Errors-To: dri-devel-bounces@lists.freedesktop.org
Sender: "dri-devel" <dri-devel-bounces@lists.freedesktop.org>
To: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Thomas Hellstrom <thellstrom@vmware.com>, Stephen Warren <swarren@wwwdotorg.org>, intel-gfx@lists.freedesktop.org, dri-devel@lists.freedesktop.org, Russell King <rmk+kernel@armlinux.org.uk>, Alexandre Courbot <gnurou@gmail.com>, Alex Deucher <alexander.deucher@amd.com>, Daniel Vetter <daniel.vetter@intel.com>, Christian =?ISO-8859-1?Q?K=F6nig?= <christian.koenig@amd.com>
List-Id: intel-gfx@lists.freedesktop.org

QW0gRG9ubmVyc3RhZywgZGVuIDAyLjAyLjIwMTcsIDExOjQ0ICswMDAwIHNjaHJpZWIgQ2hyaXMg
V2lsc29uOgo+IFRoZSBkcm1fbW0gcmFuZ2UgbWFuYWdlciBjbGFpbWVkIHRvIHN1cHBvcnQgdG9w
LWRvd24gaW5zZXJ0aW9uLCBidXQgaXQKPiB3YXMgbmVpdGhlciBzZWFyY2hpbmcgZm9yIHRoZSB0
b3AtbW9zdCBob2xlIHRoYXQgY291bGQgZml0IHRoZQo+IGFsbG9jYXRpb24gcmVxdWVzdCBub3Ig
Zml0dGluZyB0aGUgcmVxdWVzdCB0byB0aGUgaG9sZSBjb3JyZWN0bHkuCj4gCj4gSW4gb3JkZXIg
dG8gc2VhcmNoIHRoZSByYW5nZSBlZmZpY2llbnRseSwgd2UgY3JlYXRlIGEgc2Vjb25kYXJ5IGlu
ZGV4Cj4gZm9yIHRoZSBob2xlcyB1c2luZyBlaXRoZXIgdGhlaXIgc2l6ZSBvciB0aGVpciBhZGRy
ZXNzLiBUaGlzIGluZGV4Cj4gYWxsb3dzIHVzIHRvIGZpbmQgdGhlIHNtYWxsZXN0IGhvbGUgb3Ig
dGhlIGhvbGUgYXQgdGhlIGJvdHRvbSBvciB0b3Agb2YKPiB0aGUgcmFuZ2UgZWZmaWNpZW50bHks
IHdoaWxzdCBrZWVwaW5nIHRoZSBob2xlIHN0YWNrIHRvIHJhcGlkbHkgc2VydmljZQo+IGV2aWN0
aW9ucy4KPiAKPiB2MjogU2VhcmNoIGZvciBob2xlcyBib3RoIGhpZ2ggYW5kIGxvdy4gUmVuYW1l
IGZsYWdzIHRvIG1vZGUuCj4gdjM6IERpc2NvdmVyIHJiX2VudHJ5X3NhZmUoKSBhbmQgdXNlIGl0
IQo+IHY0OiBLZXJuZWxkb2MgZm9yIGVudW0gZHJtX21tX2luc2VydF9tb2RlLgo+IAo+IFNpZ25l
ZC1vZmYtYnk6IENocmlzIFdpbHNvbiA8Y2hyaXNAY2hyaXMtd2lsc29uLmNvLnVrPgo+IFJldmll
d2VkLWJ5OiBKb29uYXMgTGFodGluZW4gPGpvb25hcy5sYWh0aW5lbkBsaW51eC5pbnRlbC5jb20+
Cj4gQ2M6IEFsZXggRGV1Y2hlciA8YWxleGFuZGVyLmRldWNoZXJAYW1kLmNvbT4KPiBDYzogIkNo
cmlzdGlhbiBLw7ZuaWciIDxjaHJpc3RpYW4ua29lbmlnQGFtZC5jb20+Cj4gQ2M6IERhdmlkIEFp
cmxpZSA8YWlybGllZEBsaW51eC5pZT4KPiBDYzogUnVzc2VsbCBLaW5nIDxybWsra2VybmVsQGFy
bWxpbnV4Lm9yZy51az4KPiBDYzogRGFuaWVsIFZldHRlciA8ZGFuaWVsLnZldHRlckBpbnRlbC5j
b20+Cj4gQ2M6IEphbmkgTmlrdWxhIDxqYW5pLm5pa3VsYUBsaW51eC5pbnRlbC5jb20+Cj4gQ2M6
IFNlYW4gUGF1bCA8c2VhbnBhdWxAY2hyb21pdW0ub3JnPgo+IENjOiBMdWNhcyBTdGFjaCA8bC5z
dGFjaEBwZW5ndXRyb25peC5kZT4KPiBDYzogQ2hyaXN0aWFuIEdtZWluZXIgPGNocmlzdGlhbi5n
bWVpbmVyQGdtYWlsLmNvbT4KPiBDYzogUm9iIENsYXJrIDxyb2JkY2xhcmtAZ21haWwuY29tPgo+
IENjOiBUaGllcnJ5IFJlZGluZyA8dGhpZXJyeS5yZWRpbmdAZ21haWwuY29tPgo+IENjOiBTdGVw
aGVuIFdhcnJlbiA8c3dhcnJlbkB3d3dkb3Rvcmcub3JnPgo+IENjOiBBbGV4YW5kcmUgQ291cmJv
dCA8Z251cm91QGdtYWlsLmNvbT4KPiBDYzogRXJpYyBBbmhvbHQgPGVyaWNAYW5ob2x0Lm5ldD4K
PiBDYzogU2luY2xhaXIgWWVoIDxzeWVoQHZtd2FyZS5jb20+Cj4gQ2M6IFRob21hcyBIZWxsc3Ry
b20gPHRoZWxsc3Ryb21Adm13YXJlLmNvbT4KPiAtLS0KPiAgZHJpdmVycy9ncHUvZHJtL2FtZC9h
bWRncHUvYW1kZ3B1X2d0dF9tZ3IuYyAgfCAgMTYgKy0KPiAgZHJpdmVycy9ncHUvZHJtL2FtZC9h
bWRncHUvYW1kZ3B1X3ZyYW1fbWdyLmMgfCAgMjAgKy0KPiAgZHJpdmVycy9ncHUvZHJtL2FybWFk
YS9hcm1hZGFfZ2VtLmMgICAgICAgICAgfCAgIDQgKy0KPiAgZHJpdmVycy9ncHUvZHJtL2RybV9t
bS5jICAgICAgICAgICAgICAgICAgICAgfCA0ODggKysrKysrKysrKysrKysrLS0tLS0tLS0tLS0t
Cj4gIGRyaXZlcnMvZ3B1L2RybS9kcm1fdm1hX21hbmFnZXIuYyAgICAgICAgICAgIHwgICAzICst
Cj4gIGRyaXZlcnMvZ3B1L2RybS9ldG5hdml2L2V0bmF2aXZfbW11LmMgICAgICAgIHwgIDE2ICst
Cj4gIGRyaXZlcnMvZ3B1L2RybS9pOTE1L2k5MTVfZ2VtLmMgICAgICAgICAgICAgIHwgIDEwICst
Cj4gIGRyaXZlcnMvZ3B1L2RybS9pOTE1L2k5MTVfZ2VtX2V2aWN0LmMgICAgICAgIHwgICA5ICst
Cj4gIGRyaXZlcnMvZ3B1L2RybS9pOTE1L2k5MTVfZ2VtX2V4ZWNidWZmZXIuYyAgIHwgICA1ICst
Cj4gIGRyaXZlcnMvZ3B1L2RybS9pOTE1L2k5MTVfZ2VtX2d0dC5jICAgICAgICAgIHwgIDM5ICst
LQo+ICBkcml2ZXJzL2dwdS9kcm0vaTkxNS9pOTE1X2dlbV9zdG9sZW4uYyAgICAgICB8ICAgNiAr
LQo+ICBkcml2ZXJzL2dwdS9kcm0vbXNtL21zbV9nZW0uYyAgICAgICAgICAgICAgICB8ICAgMyAr
LQo+ICBkcml2ZXJzL2dwdS9kcm0vbXNtL21zbV9nZW1fdm1hLmMgICAgICAgICAgICB8ICAgMyAr
LQo+ICBkcml2ZXJzL2dwdS9kcm0vc2VsZnRlc3RzL3Rlc3QtZHJtX21tLmMgICAgICB8ICA1OCAr
Ky0tCj4gIGRyaXZlcnMvZ3B1L2RybS9zaXMvc2lzX21tLmMgICAgICAgICAgICAgICAgIHwgICA2
ICstCj4gIGRyaXZlcnMvZ3B1L2RybS90ZWdyYS9nZW0uYyAgICAgICAgICAgICAgICAgIHwgICA0
ICstCj4gIGRyaXZlcnMvZ3B1L2RybS90dG0vdHRtX2JvX21hbmFnZXIuYyAgICAgICAgIHwgIDE4
ICstCj4gIGRyaXZlcnMvZ3B1L2RybS92YzQvdmM0X2NydGMuYyAgICAgICAgICAgICAgIHwgICAy
ICstCj4gIGRyaXZlcnMvZ3B1L2RybS92YzQvdmM0X2h2cy5jICAgICAgICAgICAgICAgIHwgICAz
ICstCj4gIGRyaXZlcnMvZ3B1L2RybS92YzQvdmM0X3BsYW5lLmMgICAgICAgICAgICAgIHwgICA2
ICstCj4gIGRyaXZlcnMvZ3B1L2RybS92aWEvdmlhX21tLmMgICAgICAgICAgICAgICAgIHwgICA0
ICstCj4gIGRyaXZlcnMvZ3B1L2RybS92bXdnZngvdm13Z2Z4X2NtZGJ1Zi5jICAgICAgIHwgIDEw
ICstCj4gIGluY2x1ZGUvZHJtL2RybV9tbS5oICAgICAgICAgICAgICAgICAgICAgICAgIHwgMTg0
ICsrKysrLS0tLS0KPiAgMjMgZmlsZXMgY2hhbmdlZCwgNDcwIGluc2VydGlvbnMoKyksIDQ0NyBk
ZWxldGlvbnMoLSkKWy4uLl0KPiAgCj4gZGlmZiAtLWdpdCBhL2RyaXZlcnMvZ3B1L2RybS9ldG5h
dml2L2V0bmF2aXZfbW11LmMgYi9kcml2ZXJzL2dwdS9kcm0vZXRuYXZpdi9ldG5hdml2X21tdS5j
Cj4gaW5kZXggZjUwM2FmNDYyZGFkLi4wMDQ0NTY1MzRlNDggMTAwNjQ0Cj4gLS0tIGEvZHJpdmVy
cy9ncHUvZHJtL2V0bmF2aXYvZXRuYXZpdl9tbXUuYwo+ICsrKyBiL2RyaXZlcnMvZ3B1L2RybS9l
dG5hdml2L2V0bmF2aXZfbW11LmMKPiBAQCAtMTA3LDYgKzEwNyw3IEBAIHN0YXRpYyBpbnQgZXRu
YXZpdl9pb21tdV9maW5kX2lvdmEoc3RydWN0IGV0bmF2aXZfaW9tbXUgKm1tdSwKPiAgCQkJCSAg
IHN0cnVjdCBkcm1fbW1fbm9kZSAqbm9kZSwgc2l6ZV90IHNpemUpCj4gIHsKPiAgCXN0cnVjdCBl
dG5hdml2X3ZyYW1fbWFwcGluZyAqZnJlZSA9IE5VTEw7Cj4gKwllbnVtIGRybV9tbV9pbnNlcnRf
bW9kZSBtb2RlID0gRFJNX01NX0lOU0VSVF9MT1c7Cj4gIAlpbnQgcmV0Owo+ICAKPiAgCWxvY2tk
ZXBfYXNzZXJ0X2hlbGQoJm1tdS0+bG9jayk7Cj4gQEAgLTExNywxNSArMTE4LDEwIEBAIHN0YXRp
YyBpbnQgZXRuYXZpdl9pb21tdV9maW5kX2lvdmEoc3RydWN0IGV0bmF2aXZfaW9tbXUgKm1tdSwK
PiAgCQlzdHJ1Y3QgbGlzdF9oZWFkIGxpc3Q7Cj4gIAkJYm9vbCBmb3VuZDsKPiAgCj4gLQkJLyoK
PiAtCQkgKiBYWFg6IFRoZSBEUk1fTU1fU0VBUkNIX0JFTE9XIGlzIHJlYWxseSBhIGhhY2sgdG8g
dHJpY2sKPiAtCQkgKiBkcm1fbW0gaW50byBnaXZpbmcgb3V0IGEgbG93IElPVkEgYWZ0ZXIgYWRk
cmVzcyBzcGFjZQo+IC0JCSAqIHJvbGxvdmVyLiBUaGlzIG5lZWRzIGEgcHJvcGVyIGZpeC4KPiAt
CQkgKi8KPiAgCQlyZXQgPSBkcm1fbW1faW5zZXJ0X25vZGVfaW5fcmFuZ2UoJm1tdS0+bW0sIG5v
ZGUsCj4gLQkJCXNpemUsIDAsIG1tdS0+bGFzdF9pb3ZhLCB+MFVMLAo+IC0JCQltbXUtPmxhc3Rf
aW92YSA/IERSTV9NTV9TRUFSQ0hfREVGQVVMVCA6IERSTV9NTV9TRUFSQ0hfQkVMT1cpOwo+IC0K
PiArCQkJCQkJICBzaXplLCAwLCAwLAo+ICsJCQkJCQkgIG1tdS0+bGFzdF9pb3ZhLCBVNjRfTUFY
LAo+ICsJCQkJCQkgIG1vZGUpOwo+ICAJCWlmIChyZXQgIT0gLUVOT1NQQykKPiAgCQkJYnJlYWs7
Cj4gIAo+IEBAIC0xNDAsNyArMTM2LDcgQEAgc3RhdGljIGludCBldG5hdml2X2lvbW11X2ZpbmRf
aW92YShzdHJ1Y3QgZXRuYXZpdl9pb21tdSAqbW11LAo+ICAJCX0KPiAgCj4gIAkJLyogVHJ5IHRv
IHJldGlyZSBzb21lIGVudHJpZXMgKi8KPiAtCQlkcm1fbW1fc2Nhbl9pbml0KCZzY2FuLCAmbW11
LT5tbSwgc2l6ZSwgMCwgMCwgMCk7Cj4gKwkJZHJtX21tX3NjYW5faW5pdCgmc2NhbiwgJm1tdS0+
bW0sIHNpemUsIDAsIDAsIG1vZGUpOwo+ICAKPiAgCQlmb3VuZCA9IDA7Cj4gIAkJSU5JVF9MSVNU
X0hFQUQoJmxpc3QpOwo+IEBAIC0xOTIsNiArMTg4LDggQEAgc3RhdGljIGludCBldG5hdml2X2lv
bW11X2ZpbmRfaW92YShzdHJ1Y3QgZXRuYXZpdl9pb21tdSAqbW11LAo+ICAJCQlsaXN0X2RlbF9p
bml0KCZtLT5zY2FuX25vZGUpOwo+ICAJCX0KPiAgCj4gKwkJbW9kZSA9IERSTV9NTV9JTlNFUlRf
RVZJQ1Q7Cj4gKwo+ICAJCS8qCj4gIAkJICogV2UgcmVtb3ZlZCBlbm91Z2ggbWFwcGluZ3Mgc28g
dGhhdCB0aGUgbmV3IGFsbG9jYXRpb24gd2lsbAo+ICAJCSAqIHN1Y2NlZWQuICBFbnN1cmUgdGhh
dCB0aGUgTU1VIHdpbGwgYmUgZmx1c2hlZCBiZWZvcmUgdGhlCgpUaGlzIG5lZWRzIGEgcmViYXNl
IG9uIHRoZSBldG5hdml2IGZvciA0LjExIHB1bGwsIHRoYXQgcmVtb3ZlcyB0aGUgaGFjawptZW50
aW9uZWQgaW4gdGhlIGNvbW1lbnQgYWJvdmUuIE90aGVyd2lzZSB0aGUgY29kZSBjaGFuZ2UgbG9v
a3MgZmluZS4KClJlZ2FyZHMsCkx1Y2FzCgpfX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f
X19fX19fX19fX19fX19fXwpkcmktZGV2ZWwgbWFpbGluZyBsaXN0CmRyaS1kZXZlbEBsaXN0cy5m
cmVlZGVza3RvcC5vcmcKaHR0cHM6Ly9saXN0cy5mcmVlZGVza3RvcC5vcmcvbWFpbG1hbi9saXN0
aW5mby9kcmktZGV2ZWwK