1 /* $NetBSD: nouveau_core_mm.c,v 1.1.1.1 2014/08/06 12:36:23 riastradh Exp $ */
2
3 /*
4 * Copyright 2012 Red Hat Inc.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, including without limitation
9 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 * and/or sell copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE COPYRIGHT HOLDER(S) OR AUTHOR(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR
20 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
21 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
22 * OTHER DEALINGS IN THE SOFTWARE.
23 *
24 * Authors: Ben Skeggs
25 */
26
27 #include <sys/cdefs.h>
28 __KERNEL_RCSID(0, "$NetBSD: nouveau_core_mm.c,v 1.1.1.1 2014/08/06 12:36:23 riastradh Exp $");
29
30 #include "core/os.h"
31 #include "core/mm.h"
32
33 #define node(root, dir) ((root)->nl_entry.dir == &mm->nodes) ? NULL : \
34 list_entry((root)->nl_entry.dir, struct nouveau_mm_node, nl_entry)
35
36 void
nouveau_mm_free(struct nouveau_mm * mm,struct nouveau_mm_node ** pthis)37 nouveau_mm_free(struct nouveau_mm *mm, struct nouveau_mm_node **pthis)
38 {
39 struct nouveau_mm_node *this = *pthis;
40
41 if (this) {
42 struct nouveau_mm_node *prev = node(this, prev);
43 struct nouveau_mm_node *next = node(this, next);
44
45 if (prev && prev->type == 0) {
46 prev->length += this->length;
47 list_del(&this->nl_entry);
48 kfree(this); this = prev;
49 }
50
51 if (next && next->type == 0) {
52 next->offset = this->offset;
53 next->length += this->length;
54 if (this->type == 0)
55 list_del(&this->fl_entry);
56 list_del(&this->nl_entry);
57 kfree(this); this = NULL;
58 }
59
60 if (this && this->type != 0) {
61 list_for_each_entry(prev, &mm->free, fl_entry) {
62 if (this->offset < prev->offset)
63 break;
64 }
65
66 list_add_tail(&this->fl_entry, &prev->fl_entry);
67 this->type = 0;
68 }
69 }
70
71 *pthis = NULL;
72 }
73
74 static struct nouveau_mm_node *
region_head(struct nouveau_mm * mm,struct nouveau_mm_node * a,u32 size)75 region_head(struct nouveau_mm *mm, struct nouveau_mm_node *a, u32 size)
76 {
77 struct nouveau_mm_node *b;
78
79 if (a->length == size)
80 return a;
81
82 b = kmalloc(sizeof(*b), GFP_KERNEL);
83 if (unlikely(b == NULL))
84 return NULL;
85
86 b->offset = a->offset;
87 b->length = size;
88 b->type = a->type;
89 a->offset += size;
90 a->length -= size;
91 list_add_tail(&b->nl_entry, &a->nl_entry);
92 if (b->type == 0)
93 list_add_tail(&b->fl_entry, &a->fl_entry);
94 return b;
95 }
96
97 int
nouveau_mm_head(struct nouveau_mm * mm,u8 type,u32 size_max,u32 size_min,u32 align,struct nouveau_mm_node ** pnode)98 nouveau_mm_head(struct nouveau_mm *mm, u8 type, u32 size_max, u32 size_min,
99 u32 align, struct nouveau_mm_node **pnode)
100 {
101 struct nouveau_mm_node *prev, *this, *next;
102 u32 mask = align - 1;
103 u32 splitoff;
104 u32 s, e;
105
106 BUG_ON(!type);
107
108 list_for_each_entry(this, &mm->free, fl_entry) {
109 e = this->offset + this->length;
110 s = this->offset;
111
112 prev = node(this, prev);
113 if (prev && prev->type != type)
114 s = roundup(s, mm->block_size);
115
116 next = node(this, next);
117 if (next && next->type != type)
118 e = rounddown(e, mm->block_size);
119
120 s = (s + mask) & ~mask;
121 e &= ~mask;
122 if (s > e || e - s < size_min)
123 continue;
124
125 splitoff = s - this->offset;
126 if (splitoff && !region_head(mm, this, splitoff))
127 return -ENOMEM;
128
129 this = region_head(mm, this, min(size_max, e - s));
130 if (!this)
131 return -ENOMEM;
132
133 this->type = type;
134 list_del(&this->fl_entry);
135 *pnode = this;
136 return 0;
137 }
138
139 return -ENOSPC;
140 }
141
142 static struct nouveau_mm_node *
region_tail(struct nouveau_mm * mm,struct nouveau_mm_node * a,u32 size)143 region_tail(struct nouveau_mm *mm, struct nouveau_mm_node *a, u32 size)
144 {
145 struct nouveau_mm_node *b;
146
147 if (a->length == size)
148 return a;
149
150 b = kmalloc(sizeof(*b), GFP_KERNEL);
151 if (unlikely(b == NULL))
152 return NULL;
153
154 a->length -= size;
155 b->offset = a->offset + a->length;
156 b->length = size;
157 b->type = a->type;
158
159 list_add(&b->nl_entry, &a->nl_entry);
160 if (b->type == 0)
161 list_add(&b->fl_entry, &a->fl_entry);
162 return b;
163 }
164
165 int
nouveau_mm_tail(struct nouveau_mm * mm,u8 type,u32 size_max,u32 size_min,u32 align,struct nouveau_mm_node ** pnode)166 nouveau_mm_tail(struct nouveau_mm *mm, u8 type, u32 size_max, u32 size_min,
167 u32 align, struct nouveau_mm_node **pnode)
168 {
169 struct nouveau_mm_node *prev, *this, *next;
170 u32 mask = align - 1;
171
172 BUG_ON(!type);
173
174 list_for_each_entry_reverse(this, &mm->free, fl_entry) {
175 u32 e = this->offset + this->length;
176 u32 s = this->offset;
177 u32 c = 0, a;
178
179 prev = node(this, prev);
180 if (prev && prev->type != type)
181 s = roundup(s, mm->block_size);
182
183 next = node(this, next);
184 if (next && next->type != type) {
185 e = rounddown(e, mm->block_size);
186 c = next->offset - e;
187 }
188
189 s = (s + mask) & ~mask;
190 a = e - s;
191 if (s > e || a < size_min)
192 continue;
193
194 a = min(a, size_max);
195 s = (e - a) & ~mask;
196 c += (e - s) - a;
197
198 if (c && !region_tail(mm, this, c))
199 return -ENOMEM;
200
201 this = region_tail(mm, this, a);
202 if (!this)
203 return -ENOMEM;
204
205 this->type = type;
206 list_del(&this->fl_entry);
207 *pnode = this;
208 return 0;
209 }
210
211 return -ENOSPC;
212 }
213
214 int
nouveau_mm_init(struct nouveau_mm * mm,u32 offset,u32 length,u32 block)215 nouveau_mm_init(struct nouveau_mm *mm, u32 offset, u32 length, u32 block)
216 {
217 struct nouveau_mm_node *node;
218
219 if (block) {
220 INIT_LIST_HEAD(&mm->nodes);
221 INIT_LIST_HEAD(&mm->free);
222 mm->block_size = block;
223 mm->heap_nodes = 0;
224 }
225
226 node = kzalloc(sizeof(*node), GFP_KERNEL);
227 if (!node)
228 return -ENOMEM;
229
230 if (length) {
231 node->offset = roundup(offset, mm->block_size);
232 node->length = rounddown(offset + length, mm->block_size);
233 node->length -= node->offset;
234 }
235
236 list_add_tail(&node->nl_entry, &mm->nodes);
237 list_add_tail(&node->fl_entry, &mm->free);
238 mm->heap_nodes++;
239 return 0;
240 }
241
242 int
nouveau_mm_fini(struct nouveau_mm * mm)243 nouveau_mm_fini(struct nouveau_mm *mm)
244 {
245 if (nouveau_mm_initialised(mm)) {
246 struct nouveau_mm_node *node, *heap =
247 list_first_entry(&mm->nodes, typeof(*heap), nl_entry);
248 int nodes = 0;
249
250 list_for_each_entry(node, &mm->nodes, nl_entry) {
251 if (WARN_ON(nodes++ == mm->heap_nodes))
252 return -EBUSY;
253 }
254
255 kfree(heap);
256 }
257
258 return 0;
259 }
260