1573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs/* 2496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs * Copyright 2012 Red Hat Inc. 3573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * 4573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * Permission is hereby granted, free of charge, to any person obtaining a 5573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * copy of this software and associated documentation files (the "Software"), 6573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * to deal in the Software without restriction, including without limitation 7573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * and/or sell copies of the Software, and to permit persons to whom the 9573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * Software is furnished to do so, subject to the following conditions: 10573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * 11573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * The above copyright notice and this permission notice shall be included in 12573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * all copies or substantial portions of the Software. 13573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * 14573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 17573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * THE COPYRIGHT HOLDER(S) OR AUTHOR(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR 18573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 19573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 20573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * OTHER DEALINGS IN THE SOFTWARE. 21573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * 22573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs * Authors: Ben Skeggs 23573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs */ 24573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs 25496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs#include "core/os.h" 26496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs#include "core/mm.h" 27573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs 28496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs#define node(root, dir) ((root)->nl_entry.dir == &mm->nodes) ? NULL : \ 29496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs list_entry((root)->nl_entry.dir, struct nouveau_mm_node, nl_entry) 30496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 31d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggsstatic void 32d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggsnouveau_mm_dump(struct nouveau_mm *mm, const char *header) 33d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs{ 34d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs struct nouveau_mm_node *node; 35d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs 36d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs printk(KERN_ERR "nouveau: %s\n", header); 37d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs printk(KERN_ERR "nouveau: node list:\n"); 38d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs list_for_each_entry(node, &mm->nodes, nl_entry) { 39d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs printk(KERN_ERR "nouveau: \t%08x %08x %d\n", 40d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs node->offset, node->length, node->type); 41d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs } 42d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs printk(KERN_ERR "nouveau: free list:\n"); 43d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs list_for_each_entry(node, &mm->free, fl_entry) { 44d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs printk(KERN_ERR "nouveau: \t%08x %08x %d\n", 45d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs node->offset, node->length, node->type); 46d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs } 47d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs} 48d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs 49496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggsvoid 50496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggsnouveau_mm_free(struct nouveau_mm *mm, struct nouveau_mm_node **pthis) 51573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs{ 52496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs struct nouveau_mm_node *this = *pthis; 53496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 54496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs if (this) { 55496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs struct nouveau_mm_node *prev = node(this, prev); 56496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs struct nouveau_mm_node *next = node(this, next); 57496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 5879456e1a10d5f4e708822287ed0e97af469bf49bBen Skeggs if (prev && prev->type == NVKM_MM_TYPE_NONE) { 59496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs prev->length += this->length; 60496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs list_del(&this->nl_entry); 61496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs kfree(this); this = prev; 62496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs } 63496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 6479456e1a10d5f4e708822287ed0e97af469bf49bBen Skeggs if (next && next->type == NVKM_MM_TYPE_NONE) { 65496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs next->offset = this->offset; 66496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs next->length += this->length; 6779456e1a10d5f4e708822287ed0e97af469bf49bBen Skeggs if (this->type == NVKM_MM_TYPE_NONE) 68496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs list_del(&this->fl_entry); 69496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs list_del(&this->nl_entry); 70496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs kfree(this); this = NULL; 71496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs } 72496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 7379456e1a10d5f4e708822287ed0e97af469bf49bBen Skeggs if (this && this->type != NVKM_MM_TYPE_NONE) { 74496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs list_for_each_entry(prev, &mm->free, fl_entry) { 75496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs if (this->offset < prev->offset) 76496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs break; 77496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs } 78496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 79496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs list_add_tail(&this->fl_entry, &prev->fl_entry); 8079456e1a10d5f4e708822287ed0e97af469bf49bBen Skeggs this->type = NVKM_MM_TYPE_NONE; 81496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs } 82496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs } 83496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 84496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs *pthis = NULL; 85573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs} 86573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs 87573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggsstatic struct nouveau_mm_node * 88496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggsregion_head(struct nouveau_mm *mm, struct nouveau_mm_node *a, u32 size) 89573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs{ 90573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs struct nouveau_mm_node *b; 91573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs 92573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs if (a->length == size) 93573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs return a; 94573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs 95573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs b = kmalloc(sizeof(*b), GFP_KERNEL); 96573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs if (unlikely(b == NULL)) 97573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs return NULL; 98573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs 99573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs b->offset = a->offset; 100573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs b->length = size; 10165270a6569710b42f5ab2073c1cc91fb90189eaaBen Skeggs b->heap = a->heap; 102573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs b->type = a->type; 103573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs a->offset += size; 104573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs a->length -= size; 105573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs list_add_tail(&b->nl_entry, &a->nl_entry); 10679456e1a10d5f4e708822287ed0e97af469bf49bBen Skeggs if (b->type == NVKM_MM_TYPE_NONE) 107573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs list_add_tail(&b->fl_entry, &a->fl_entry); 108573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs return b; 109573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs} 110573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs 111573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggsint 11265270a6569710b42f5ab2073c1cc91fb90189eaaBen Skeggsnouveau_mm_head(struct nouveau_mm *mm, u8 heap, u8 type, u32 size_max, 11365270a6569710b42f5ab2073c1cc91fb90189eaaBen Skeggs u32 size_min, u32 align, struct nouveau_mm_node **pnode) 114573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs{ 1158b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs struct nouveau_mm_node *prev, *this, *next; 116496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs u32 mask = align - 1; 1178b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs u32 splitoff; 1188b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs u32 s, e; 1198b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs 12013dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs BUG_ON(type == NVKM_MM_TYPE_NONE || type == NVKM_MM_TYPE_HOLE); 12118902bbf06a93ea497be2f177a6323ed9e5f30beMaarten Lankhorst 122987eec10dd76624d0edacdc7ecc7e1a6fc877373Ben Skeggs list_for_each_entry(this, &mm->free, fl_entry) { 12365270a6569710b42f5ab2073c1cc91fb90189eaaBen Skeggs if (unlikely(heap != NVKM_MM_HEAP_ANY)) { 12465270a6569710b42f5ab2073c1cc91fb90189eaaBen Skeggs if (this->heap != heap) 12565270a6569710b42f5ab2073c1cc91fb90189eaaBen Skeggs continue; 12665270a6569710b42f5ab2073c1cc91fb90189eaaBen Skeggs } 1278b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs e = this->offset + this->length; 1288b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs s = this->offset; 1298b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs 1308b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs prev = node(this, prev); 1318b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs if (prev && prev->type != type) 132987eec10dd76624d0edacdc7ecc7e1a6fc877373Ben Skeggs s = roundup(s, mm->block_size); 1338b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs 1348b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs next = node(this, next); 1358b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs if (next && next->type != type) 136987eec10dd76624d0edacdc7ecc7e1a6fc877373Ben Skeggs e = rounddown(e, mm->block_size); 1378b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs 138496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs s = (s + mask) & ~mask; 139496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs e &= ~mask; 140496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs if (s > e || e - s < size_min) 141573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs continue; 142573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs 1438b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs splitoff = s - this->offset; 144496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs if (splitoff && !region_head(mm, this, splitoff)) 145496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs return -ENOMEM; 146496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 147496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs this = region_head(mm, this, min(size_max, e - s)); 148496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs if (!this) 149496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs return -ENOMEM; 150496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 151496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs this->type = type; 152496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs list_del(&this->fl_entry); 153496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs *pnode = this; 154496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs return 0; 155496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs } 156496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 157496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs return -ENOSPC; 158496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs} 159496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 160496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggsstatic struct nouveau_mm_node * 161496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggsregion_tail(struct nouveau_mm *mm, struct nouveau_mm_node *a, u32 size) 162496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs{ 163496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs struct nouveau_mm_node *b; 164496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 165496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs if (a->length == size) 166496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs return a; 167496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 168496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs b = kmalloc(sizeof(*b), GFP_KERNEL); 169496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs if (unlikely(b == NULL)) 170496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs return NULL; 171496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 172496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs a->length -= size; 173496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs b->offset = a->offset + a->length; 174496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs b->length = size; 17565270a6569710b42f5ab2073c1cc91fb90189eaaBen Skeggs b->heap = a->heap; 176496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs b->type = a->type; 177496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 178496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs list_add(&b->nl_entry, &a->nl_entry); 17979456e1a10d5f4e708822287ed0e97af469bf49bBen Skeggs if (b->type == NVKM_MM_TYPE_NONE) 180496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs list_add(&b->fl_entry, &a->fl_entry); 181496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs return b; 182496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs} 183496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 184496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggsint 18565270a6569710b42f5ab2073c1cc91fb90189eaaBen Skeggsnouveau_mm_tail(struct nouveau_mm *mm, u8 heap, u8 type, u32 size_max, 18665270a6569710b42f5ab2073c1cc91fb90189eaaBen Skeggs u32 size_min, u32 align, struct nouveau_mm_node **pnode) 187496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs{ 188496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs struct nouveau_mm_node *prev, *this, *next; 189496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs u32 mask = align - 1; 190496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 19113dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs BUG_ON(type == NVKM_MM_TYPE_NONE || type == NVKM_MM_TYPE_HOLE); 19218902bbf06a93ea497be2f177a6323ed9e5f30beMaarten Lankhorst 193496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs list_for_each_entry_reverse(this, &mm->free, fl_entry) { 194496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs u32 e = this->offset + this->length; 195496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs u32 s = this->offset; 196496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs u32 c = 0, a; 19765270a6569710b42f5ab2073c1cc91fb90189eaaBen Skeggs if (unlikely(heap != NVKM_MM_HEAP_ANY)) { 19865270a6569710b42f5ab2073c1cc91fb90189eaaBen Skeggs if (this->heap != heap) 19965270a6569710b42f5ab2073c1cc91fb90189eaaBen Skeggs continue; 20065270a6569710b42f5ab2073c1cc91fb90189eaaBen Skeggs } 201496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 202496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs prev = node(this, prev); 203496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs if (prev && prev->type != type) 204496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs s = roundup(s, mm->block_size); 205496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 206496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs next = node(this, next); 207496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs if (next && next->type != type) { 208496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs e = rounddown(e, mm->block_size); 209496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs c = next->offset - e; 210496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs } 211496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 212496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs s = (s + mask) & ~mask; 213496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs a = e - s; 214496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs if (s > e || a < size_min) 215496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs continue; 216496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 217496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs a = min(a, size_max); 218496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs s = (e - a) & ~mask; 219496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs c += (e - s) - a; 220496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs 221496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs if (c && !region_tail(mm, this, c)) 2228b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs return -ENOMEM; 223573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs 224496734bf0391f38c196e16dbbfaaeda8e6ec5845Ben Skeggs this = region_tail(mm, this, a); 2258b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs if (!this) 226573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs return -ENOMEM; 227573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs 2288b464bfed674fc25d39d8a686010ebe509c8f62aBen Skeggs this->type = type; 229573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs list_del(&this->fl_entry); 230573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs *pnode = this; 231573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs return 0; 232573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs } 233573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs 234ef1b287169cd3d1e428c8ed8222e0bbf733d5dbbBen Skeggs return -ENOSPC; 235573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs} 236573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs 237573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggsint 238987eec10dd76624d0edacdc7ecc7e1a6fc877373Ben Skeggsnouveau_mm_init(struct nouveau_mm *mm, u32 offset, u32 length, u32 block) 239573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs{ 24013dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs struct nouveau_mm_node *node, *prev; 24113dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs u32 next; 242a12036ba2c0a190c93e5238c5f32fdb8c023c068Ben Skeggs 243d979ab975ecdb336ed4da77a808be813a293b59eBen Skeggs if (nouveau_mm_initialised(mm)) { 24413dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs prev = list_last_entry(&mm->nodes, typeof(*node), nl_entry); 24513dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs next = prev->offset + prev->length; 24613dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs if (next != offset) { 24713dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs BUG_ON(next > offset); 24813dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs if (!(node = kzalloc(sizeof(*node), GFP_KERNEL))) 24913dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs return -ENOMEM; 25013dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs node->type = NVKM_MM_TYPE_HOLE; 25113dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs node->offset = next; 25213dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs node->length = offset - next; 25313dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs list_add_tail(&node->nl_entry, &mm->nodes); 25413dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs } 255d979ab975ecdb336ed4da77a808be813a293b59eBen Skeggs BUG_ON(block != mm->block_size); 256d979ab975ecdb336ed4da77a808be813a293b59eBen Skeggs } else { 257a12036ba2c0a190c93e5238c5f32fdb8c023c068Ben Skeggs INIT_LIST_HEAD(&mm->nodes); 258a12036ba2c0a190c93e5238c5f32fdb8c023c068Ben Skeggs INIT_LIST_HEAD(&mm->free); 259a12036ba2c0a190c93e5238c5f32fdb8c023c068Ben Skeggs mm->block_size = block; 260a12036ba2c0a190c93e5238c5f32fdb8c023c068Ben Skeggs mm->heap_nodes = 0; 261a12036ba2c0a190c93e5238c5f32fdb8c023c068Ben Skeggs } 262573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs 263a12036ba2c0a190c93e5238c5f32fdb8c023c068Ben Skeggs node = kzalloc(sizeof(*node), GFP_KERNEL); 264a12036ba2c0a190c93e5238c5f32fdb8c023c068Ben Skeggs if (!node) 265573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs return -ENOMEM; 266a7dbf00433fa9dc6f4a3828a17d56a9df2bd06b1Ben Skeggs 267a7dbf00433fa9dc6f4a3828a17d56a9df2bd06b1Ben Skeggs if (length) { 268a7dbf00433fa9dc6f4a3828a17d56a9df2bd06b1Ben Skeggs node->offset = roundup(offset, mm->block_size); 269a7dbf00433fa9dc6f4a3828a17d56a9df2bd06b1Ben Skeggs node->length = rounddown(offset + length, mm->block_size); 270a7dbf00433fa9dc6f4a3828a17d56a9df2bd06b1Ben Skeggs node->length -= node->offset; 271a7dbf00433fa9dc6f4a3828a17d56a9df2bd06b1Ben Skeggs } 272987eec10dd76624d0edacdc7ecc7e1a6fc877373Ben Skeggs 273a12036ba2c0a190c93e5238c5f32fdb8c023c068Ben Skeggs list_add_tail(&node->nl_entry, &mm->nodes); 274a12036ba2c0a190c93e5238c5f32fdb8c023c068Ben Skeggs list_add_tail(&node->fl_entry, &mm->free); 27565270a6569710b42f5ab2073c1cc91fb90189eaaBen Skeggs node->heap = ++mm->heap_nodes; 276573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs return 0; 277573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs} 278573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs 279573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggsint 280987eec10dd76624d0edacdc7ecc7e1a6fc877373Ben Skeggsnouveau_mm_fini(struct nouveau_mm *mm) 281573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs{ 282d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs struct nouveau_mm_node *node, *temp; 283d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs int nodes = 0; 2847e0f992b796e102d32b75392fba38be7cab1c5a9Ben Skeggs 285d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs if (!nouveau_mm_initialised(mm)) 286d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs return 0; 287a12036ba2c0a190c93e5238c5f32fdb8c023c068Ben Skeggs 288d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs list_for_each_entry(node, &mm->nodes, nl_entry) { 28913dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs if (node->type != NVKM_MM_TYPE_HOLE) { 29013dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs if (++nodes > mm->heap_nodes) { 29113dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs nouveau_mm_dump(mm, "mm not clean!"); 29213dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs return -EBUSY; 29313dfe1286d1ea1af4c9330b039c2316d0d92c484Ben Skeggs } 294d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs } 295ad9ac437a500f8c0822bd5fe139af8ee2c132e15Ben Skeggs } 296573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs 297d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs list_for_each_entry_safe(node, temp, &mm->nodes, nl_entry) { 298d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs list_del(&node->nl_entry); 299d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs kfree(node); 300d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs } 301d7bda18c9102b65078c132fd7d7ffd835058f021Ben Skeggs mm->heap_nodes = 0; 302573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs return 0; 303573a2a37e8648a3249426c816f51e7ef50f6f73eBen Skeggs} 304