Commit | Line | Data |
---|---|---|
573a2a37 | 1 | /* |
496734bf | 2 | * Copyright 2012 Red Hat Inc. |
573a2a37 BS |
3 | * |
4 | * Permission is hereby granted, free of charge, to any person obtaining a | |
5 | * copy of this software and associated documentation files (the "Software"), | |
6 | * to deal in the Software without restriction, including without limitation | |
7 | * the rights to use, copy, modify, merge, publish, distribute, sublicense, | |
8 | * and/or sell copies of the Software, and to permit persons to whom the | |
9 | * Software is furnished to do so, subject to the following conditions: | |
10 | * | |
11 | * The above copyright notice and this permission notice shall be included in | |
12 | * all copies or substantial portions of the Software. | |
13 | * | |
14 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
15 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
16 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL | |
17 | * THE COPYRIGHT HOLDER(S) OR AUTHOR(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR | |
18 | * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, | |
19 | * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR | |
20 | * OTHER DEALINGS IN THE SOFTWARE. | |
21 | * | |
22 | * Authors: Ben Skeggs | |
23 | */ | |
5025407b | 24 | #include <core/mm.h> |
573a2a37 | 25 | |
5025407b BS |
26 | #define node(root, dir) ((root)->nl_entry.dir == &mm->nodes) ? NULL : \ |
27 | list_entry((root)->nl_entry.dir, struct nvkm_mm_node, nl_entry) | |
496734bf | 28 | |
d36a99d2 | 29 | void |
5025407b | 30 | nvkm_mm_dump(struct nvkm_mm *mm, const char *header) |
d7bda18c | 31 | { |
5025407b | 32 | struct nvkm_mm_node *node; |
d7bda18c | 33 | |
5025407b BS |
34 | printk(KERN_ERR "nvkm: %s\n", header); |
35 | printk(KERN_ERR "nvkm: node list:\n"); | |
d7bda18c | 36 | list_for_each_entry(node, &mm->nodes, nl_entry) { |
5025407b | 37 | printk(KERN_ERR "nvkm: \t%08x %08x %d\n", |
d7bda18c BS |
38 | node->offset, node->length, node->type); |
39 | } | |
5025407b | 40 | printk(KERN_ERR "nvkm: free list:\n"); |
d7bda18c | 41 | list_for_each_entry(node, &mm->free, fl_entry) { |
5025407b | 42 | printk(KERN_ERR "nvkm: \t%08x %08x %d\n", |
d7bda18c BS |
43 | node->offset, node->length, node->type); |
44 | } | |
45 | } | |
46 | ||
496734bf | 47 | void |
5025407b | 48 | nvkm_mm_free(struct nvkm_mm *mm, struct nvkm_mm_node **pthis) |
573a2a37 | 49 | { |
5025407b | 50 | struct nvkm_mm_node *this = *pthis; |
496734bf BS |
51 | |
52 | if (this) { | |
5025407b BS |
53 | struct nvkm_mm_node *prev = node(this, prev); |
54 | struct nvkm_mm_node *next = node(this, next); | |
496734bf | 55 | |
79456e1a | 56 | if (prev && prev->type == NVKM_MM_TYPE_NONE) { |
496734bf BS |
57 | prev->length += this->length; |
58 | list_del(&this->nl_entry); | |
59 | kfree(this); this = prev; | |
60 | } | |
61 | ||
79456e1a | 62 | if (next && next->type == NVKM_MM_TYPE_NONE) { |
496734bf BS |
63 | next->offset = this->offset; |
64 | next->length += this->length; | |
79456e1a | 65 | if (this->type == NVKM_MM_TYPE_NONE) |
496734bf BS |
66 | list_del(&this->fl_entry); |
67 | list_del(&this->nl_entry); | |
68 | kfree(this); this = NULL; | |
69 | } | |
70 | ||
79456e1a | 71 | if (this && this->type != NVKM_MM_TYPE_NONE) { |
496734bf BS |
72 | list_for_each_entry(prev, &mm->free, fl_entry) { |
73 | if (this->offset < prev->offset) | |
74 | break; | |
75 | } | |
76 | ||
77 | list_add_tail(&this->fl_entry, &prev->fl_entry); | |
79456e1a | 78 | this->type = NVKM_MM_TYPE_NONE; |
496734bf BS |
79 | } |
80 | } | |
81 | ||
82 | *pthis = NULL; | |
573a2a37 BS |
83 | } |
84 | ||
5025407b BS |
85 | static struct nvkm_mm_node * |
86 | region_head(struct nvkm_mm *mm, struct nvkm_mm_node *a, u32 size) | |
573a2a37 | 87 | { |
5025407b | 88 | struct nvkm_mm_node *b; |
573a2a37 BS |
89 | |
90 | if (a->length == size) | |
91 | return a; | |
92 | ||
93 | b = kmalloc(sizeof(*b), GFP_KERNEL); | |
94 | if (unlikely(b == NULL)) | |
95 | return NULL; | |
96 | ||
97 | b->offset = a->offset; | |
98 | b->length = size; | |
65270a65 | 99 | b->heap = a->heap; |
573a2a37 BS |
100 | b->type = a->type; |
101 | a->offset += size; | |
102 | a->length -= size; | |
103 | list_add_tail(&b->nl_entry, &a->nl_entry); | |
79456e1a | 104 | if (b->type == NVKM_MM_TYPE_NONE) |
573a2a37 | 105 | list_add_tail(&b->fl_entry, &a->fl_entry); |
5025407b | 106 | |
573a2a37 BS |
107 | return b; |
108 | } | |
109 | ||
573a2a37 | 110 | int |
5025407b BS |
111 | nvkm_mm_head(struct nvkm_mm *mm, u8 heap, u8 type, u32 size_max, u32 size_min, |
112 | u32 align, struct nvkm_mm_node **pnode) | |
573a2a37 | 113 | { |
5025407b | 114 | struct nvkm_mm_node *prev, *this, *next; |
496734bf | 115 | u32 mask = align - 1; |
8b464bfe BS |
116 | u32 splitoff; |
117 | u32 s, e; | |
118 | ||
13dfe128 | 119 | BUG_ON(type == NVKM_MM_TYPE_NONE || type == NVKM_MM_TYPE_HOLE); |
18902bbf | 120 | |
987eec10 | 121 | list_for_each_entry(this, &mm->free, fl_entry) { |
65270a65 BS |
122 | if (unlikely(heap != NVKM_MM_HEAP_ANY)) { |
123 | if (this->heap != heap) | |
124 | continue; | |
125 | } | |
8b464bfe BS |
126 | e = this->offset + this->length; |
127 | s = this->offset; | |
128 | ||
129 | prev = node(this, prev); | |
130 | if (prev && prev->type != type) | |
987eec10 | 131 | s = roundup(s, mm->block_size); |
8b464bfe BS |
132 | |
133 | next = node(this, next); | |
134 | if (next && next->type != type) | |
987eec10 | 135 | e = rounddown(e, mm->block_size); |
8b464bfe | 136 | |
496734bf BS |
137 | s = (s + mask) & ~mask; |
138 | e &= ~mask; | |
139 | if (s > e || e - s < size_min) | |
573a2a37 BS |
140 | continue; |
141 | ||
8b464bfe | 142 | splitoff = s - this->offset; |
496734bf BS |
143 | if (splitoff && !region_head(mm, this, splitoff)) |
144 | return -ENOMEM; | |
145 | ||
146 | this = region_head(mm, this, min(size_max, e - s)); | |
147 | if (!this) | |
148 | return -ENOMEM; | |
149 | ||
150 | this->type = type; | |
151 | list_del(&this->fl_entry); | |
152 | *pnode = this; | |
153 | return 0; | |
154 | } | |
155 | ||
156 | return -ENOSPC; | |
157 | } | |
158 | ||
5025407b BS |
159 | static struct nvkm_mm_node * |
160 | region_tail(struct nvkm_mm *mm, struct nvkm_mm_node *a, u32 size) | |
496734bf | 161 | { |
5025407b | 162 | struct nvkm_mm_node *b; |
496734bf BS |
163 | |
164 | if (a->length == size) | |
165 | return a; | |
166 | ||
167 | b = kmalloc(sizeof(*b), GFP_KERNEL); | |
168 | if (unlikely(b == NULL)) | |
169 | return NULL; | |
170 | ||
171 | a->length -= size; | |
172 | b->offset = a->offset + a->length; | |
173 | b->length = size; | |
65270a65 | 174 | b->heap = a->heap; |
496734bf BS |
175 | b->type = a->type; |
176 | ||
177 | list_add(&b->nl_entry, &a->nl_entry); | |
79456e1a | 178 | if (b->type == NVKM_MM_TYPE_NONE) |
496734bf | 179 | list_add(&b->fl_entry, &a->fl_entry); |
5025407b | 180 | |
496734bf BS |
181 | return b; |
182 | } | |
183 | ||
184 | int | |
5025407b BS |
185 | nvkm_mm_tail(struct nvkm_mm *mm, u8 heap, u8 type, u32 size_max, u32 size_min, |
186 | u32 align, struct nvkm_mm_node **pnode) | |
496734bf | 187 | { |
5025407b | 188 | struct nvkm_mm_node *prev, *this, *next; |
496734bf BS |
189 | u32 mask = align - 1; |
190 | ||
13dfe128 | 191 | BUG_ON(type == NVKM_MM_TYPE_NONE || type == NVKM_MM_TYPE_HOLE); |
18902bbf | 192 | |
496734bf BS |
193 | list_for_each_entry_reverse(this, &mm->free, fl_entry) { |
194 | u32 e = this->offset + this->length; | |
195 | u32 s = this->offset; | |
196 | u32 c = 0, a; | |
65270a65 BS |
197 | if (unlikely(heap != NVKM_MM_HEAP_ANY)) { |
198 | if (this->heap != heap) | |
199 | continue; | |
200 | } | |
496734bf BS |
201 | |
202 | prev = node(this, prev); | |
203 | if (prev && prev->type != type) | |
204 | s = roundup(s, mm->block_size); | |
205 | ||
206 | next = node(this, next); | |
207 | if (next && next->type != type) { | |
208 | e = rounddown(e, mm->block_size); | |
209 | c = next->offset - e; | |
210 | } | |
211 | ||
212 | s = (s + mask) & ~mask; | |
213 | a = e - s; | |
214 | if (s > e || a < size_min) | |
215 | continue; | |
216 | ||
217 | a = min(a, size_max); | |
218 | s = (e - a) & ~mask; | |
219 | c += (e - s) - a; | |
220 | ||
221 | if (c && !region_tail(mm, this, c)) | |
8b464bfe | 222 | return -ENOMEM; |
573a2a37 | 223 | |
496734bf | 224 | this = region_tail(mm, this, a); |
8b464bfe | 225 | if (!this) |
573a2a37 BS |
226 | return -ENOMEM; |
227 | ||
8b464bfe | 228 | this->type = type; |
573a2a37 BS |
229 | list_del(&this->fl_entry); |
230 | *pnode = this; | |
231 | return 0; | |
232 | } | |
233 | ||
ef1b2871 | 234 | return -ENOSPC; |
573a2a37 BS |
235 | } |
236 | ||
237 | int | |
5025407b | 238 | nvkm_mm_init(struct nvkm_mm *mm, u32 offset, u32 length, u32 block) |
573a2a37 | 239 | { |
5025407b | 240 | struct nvkm_mm_node *node, *prev; |
13dfe128 | 241 | u32 next; |
a12036ba | 242 | |
5025407b | 243 | if (nvkm_mm_initialised(mm)) { |
13dfe128 BS |
244 | prev = list_last_entry(&mm->nodes, typeof(*node), nl_entry); |
245 | next = prev->offset + prev->length; | |
246 | if (next != offset) { | |
247 | BUG_ON(next > offset); | |
248 | if (!(node = kzalloc(sizeof(*node), GFP_KERNEL))) | |
249 | return -ENOMEM; | |
250 | node->type = NVKM_MM_TYPE_HOLE; | |
251 | node->offset = next; | |
252 | node->length = offset - next; | |
253 | list_add_tail(&node->nl_entry, &mm->nodes); | |
254 | } | |
d979ab97 BS |
255 | BUG_ON(block != mm->block_size); |
256 | } else { | |
a12036ba BS |
257 | INIT_LIST_HEAD(&mm->nodes); |
258 | INIT_LIST_HEAD(&mm->free); | |
259 | mm->block_size = block; | |
260 | mm->heap_nodes = 0; | |
261 | } | |
573a2a37 | 262 | |
a12036ba BS |
263 | node = kzalloc(sizeof(*node), GFP_KERNEL); |
264 | if (!node) | |
573a2a37 | 265 | return -ENOMEM; |
a7dbf004 BS |
266 | |
267 | if (length) { | |
268 | node->offset = roundup(offset, mm->block_size); | |
269 | node->length = rounddown(offset + length, mm->block_size); | |
270 | node->length -= node->offset; | |
271 | } | |
987eec10 | 272 | |
a12036ba BS |
273 | list_add_tail(&node->nl_entry, &mm->nodes); |
274 | list_add_tail(&node->fl_entry, &mm->free); | |
65270a65 | 275 | node->heap = ++mm->heap_nodes; |
573a2a37 BS |
276 | return 0; |
277 | } | |
278 | ||
279 | int | |
5025407b | 280 | nvkm_mm_fini(struct nvkm_mm *mm) |
573a2a37 | 281 | { |
5025407b | 282 | struct nvkm_mm_node *node, *temp; |
d7bda18c | 283 | int nodes = 0; |
7e0f992b | 284 | |
5025407b | 285 | if (!nvkm_mm_initialised(mm)) |
d7bda18c | 286 | return 0; |
a12036ba | 287 | |
d7bda18c | 288 | list_for_each_entry(node, &mm->nodes, nl_entry) { |
13dfe128 BS |
289 | if (node->type != NVKM_MM_TYPE_HOLE) { |
290 | if (++nodes > mm->heap_nodes) { | |
5025407b | 291 | nvkm_mm_dump(mm, "mm not clean!"); |
13dfe128 BS |
292 | return -EBUSY; |
293 | } | |
d7bda18c | 294 | } |
ad9ac437 | 295 | } |
573a2a37 | 296 | |
d7bda18c BS |
297 | list_for_each_entry_safe(node, temp, &mm->nodes, nl_entry) { |
298 | list_del(&node->nl_entry); | |
299 | kfree(node); | |
300 | } | |
5025407b | 301 | |
d7bda18c | 302 | mm->heap_nodes = 0; |
573a2a37 BS |
303 | return 0; |
304 | } |