merge with master
[platform/upstream/libwsbm.git] / src / wsbm_mm.c
1 /**************************************************************************
2  *
3  * Copyright 2006-2008 Tungsten Graphics, Inc., Cedar Park, TX., USA.
4  * All Rights Reserved.
5  * Copyright 2009 VMware, Inc., Palo Alto, CA., USA.
6  * All Rights Reserved.
7  *
8  * Permission is hereby granted, free of charge, to any person obtaining a
9  * copy of this software and associated documentation files (the
10  * "Software"), to deal in the Software without restriction, including
11  * without limitation the rights to use, copy, modify, merge, publish,
12  * distribute, sub license, and/or sell copies of the Software, and to
13  * permit persons to whom the Software is furnished to do so, subject to
14  * the following conditions:
15  *
16  * The above copyright notice and this permission notice (including the
17  * next paragraph) shall be included in all copies or substantial portions
18  * of the Software.
19  *
20  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
21  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22  * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
23  * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
24  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
25  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
26  * USE OR OTHER DEALINGS IN THE SOFTWARE.
27  *
28  **************************************************************************/
29
30 /*
31  * Generic simple memory manager implementation. Intended to be used as a base
32  * class implementation for more advanced memory managers.
33  *
34  * Note that the algorithm used is quite simple and there might be substantial
35  * performance gains if a smarter free list is implemented. Currently it is just an
36  * unordered stack of free regions. This could easily be improved if an RB-tree
37  * is used instead. At least if we expect heavy fragmentation.
38  * Note that this implementation is more or less identical to the drm core manager
39  * in the linux kernel.
40  *
41  * Authors:
42  * Thomas Hellström <thomas-at-tungstengraphics-dot-com>
43  */
44
45 #ifdef HAVE_CONFIG_H
46 #include "config.h"
47 #endif
48
49 #include "wsbm_mm.h"
50 #include <errno.h>
51 #include <stdlib.h>
52
53 unsigned long
54 wsbmMMTailSpace(struct _WsbmMM *mm)
55 {
56     struct _WsbmListHead *tail_node;
57     struct _WsbmMMNode *entry;
58
59     tail_node = mm->ml_entry.prev;
60     entry = WSBMLISTENTRY(tail_node, struct _WsbmMMNode, ml_entry);
61
62     if (!entry->free)
63         return 0;
64
65     return entry->size;
66 }
67
68 int
69 wsbmMMRemoveSpaceFromTail(struct _WsbmMM *mm, unsigned long size)
70 {
71     struct _WsbmListHead *tail_node;
72     struct _WsbmMMNode *entry;
73
74     tail_node = mm->ml_entry.prev;
75     entry = WSBMLISTENTRY(tail_node, struct _WsbmMMNode, ml_entry);
76
77     if (!entry->free)
78         return -ENOMEM;
79
80     if (entry->size <= size)
81         return -ENOMEM;
82
83     entry->size -= size;
84     return 0;
85 }
86
87 static int
88 wsbmMMCreateTailNode(struct _WsbmMM *mm,
89                      unsigned long start, unsigned long size)
90 {
91     struct _WsbmMMNode *child;
92
93     child = (struct _WsbmMMNode *)malloc(sizeof(*child));
94     if (!child)
95         return -ENOMEM;
96
97     child->free = 1;
98     child->size = size;
99     child->start = start;
100     child->mm = mm;
101
102     WSBMLISTADDTAIL(&child->ml_entry, &mm->ml_entry);
103     WSBMLISTADDTAIL(&child->fl_entry, &mm->fl_entry);
104
105     return 0;
106 }
107
108 static struct _WsbmMMNode *
109 wsbmMMSplitAtStart(struct _WsbmMMNode *parent, unsigned long size)
110 {
111     struct _WsbmMMNode *child;
112
113     child = (struct _WsbmMMNode *)malloc(sizeof(*child));
114     if (!child)
115         return NULL;
116
117     WSBMINITLISTHEAD(&child->fl_entry);
118
119     child->free = 0;
120     child->size = size;
121     child->start = parent->start;
122     child->mm = parent->mm;
123
124     WSBMLISTADDTAIL(&child->ml_entry, &parent->ml_entry);
125     WSBMINITLISTHEAD(&child->fl_entry);
126
127     parent->size -= size;
128     parent->start += size;
129     return child;
130 }
131
132 struct _WsbmMMNode *
133 wsbmMMGetBlock(struct _WsbmMMNode *parent,
134                unsigned long size, unsigned alignment)
135 {
136
137     struct _WsbmMMNode *align_splitoff = NULL;
138     struct _WsbmMMNode *child;
139     unsigned tmp = 0;
140
141     if (alignment)
142         tmp = parent->start % alignment;
143
144     if (tmp) {
145         align_splitoff = wsbmMMSplitAtStart(parent, alignment - tmp);
146         if (!align_splitoff)
147             return NULL;
148     }
149
150     if (parent->size == size) {
151         WSBMLISTDELINIT(&parent->fl_entry);
152         parent->free = 0;
153         return parent;
154     } else {
155         child = wsbmMMSplitAtStart(parent, size);
156     }
157
158     if (align_splitoff)
159         wsbmMMPutBlock(align_splitoff);
160
161     return child;
162 }
163
164 /*
165  * Put a block. Merge with the previous and / or next block if they are free.
166  * Otherwise add to the free stack.
167  */
168
169 void
170 wsbmMMPutBlock(struct _WsbmMMNode *cur)
171 {
172
173     struct _WsbmMM *mm = cur->mm;
174     struct _WsbmListHead *cur_head = &cur->ml_entry;
175     struct _WsbmListHead *root_head = &mm->ml_entry;
176     struct _WsbmMMNode *prev_node = NULL;
177     struct _WsbmMMNode *next_node;
178
179     int merged = 0;
180
181     if (cur_head->prev != root_head) {
182         prev_node =
183             WSBMLISTENTRY(cur_head->prev, struct _WsbmMMNode, ml_entry);
184         if (prev_node->free) {
185             prev_node->size += cur->size;
186             merged = 1;
187         }
188     }
189     if (cur_head->next != root_head) {
190         next_node =
191             WSBMLISTENTRY(cur_head->next, struct _WsbmMMNode, ml_entry);
192         if (next_node->free) {
193             if (merged) {
194                 prev_node->size += next_node->size;
195                 WSBMLISTDEL(&next_node->ml_entry);
196                 WSBMLISTDEL(&next_node->fl_entry);
197                 free(next_node);
198             } else {
199                 next_node->size += cur->size;
200                 next_node->start = cur->start;
201                 merged = 1;
202             }
203         }
204     }
205     if (!merged) {
206         cur->free = 1;
207         WSBMLISTADD(&cur->fl_entry, &mm->fl_entry);
208     } else {
209         WSBMLISTDEL(&cur->ml_entry);
210         free(cur);
211     }
212 }
213
214 struct _WsbmMMNode *
215 wsbmMMSearchFree(const struct _WsbmMM *mm,
216                  unsigned long size, unsigned alignment, int best_match)
217 {
218     struct _WsbmListHead *list;
219     const struct _WsbmListHead *free_stack = &mm->fl_entry;
220     struct _WsbmMMNode *entry;
221     struct _WsbmMMNode *best;
222     unsigned long best_size;
223     unsigned wasted;
224
225     best = NULL;
226     best_size = ~0UL;
227
228     WSBMLISTFOREACH(list, free_stack) {
229         entry = WSBMLISTENTRY(list, struct _WsbmMMNode, fl_entry);
230
231         wasted = 0;
232
233         if (entry->size < size)
234             continue;
235
236         if (alignment) {
237             register unsigned tmp = entry->start % alignment;
238
239             if (tmp)
240                 wasted += alignment - tmp;
241         }
242
243         if (entry->size >= size + wasted) {
244             if (!best_match)
245                 return entry;
246             if (size < best_size) {
247                 best = entry;
248                 best_size = entry->size;
249             }
250         }
251     }
252
253     return best;
254 }
255
256 int
257 wsbmMMclean(struct _WsbmMM *mm)
258 {
259     struct _WsbmListHead *head = &mm->ml_entry;
260
261     return (head->next->next == head);
262 }
263
264 int
265 wsbmMMinit(struct _WsbmMM *mm, unsigned long start, unsigned long size)
266 {
267     WSBMINITLISTHEAD(&mm->ml_entry);
268     WSBMINITLISTHEAD(&mm->fl_entry);
269
270     return wsbmMMCreateTailNode(mm, start, size);
271 }
272
273 void
274 wsbmMMtakedown(struct _WsbmMM *mm)
275 {
276     struct _WsbmListHead *bnode = mm->fl_entry.next;
277     struct _WsbmMMNode *entry;
278
279     entry = WSBMLISTENTRY(bnode, struct _WsbmMMNode, fl_entry);
280
281     if (entry->ml_entry.next != &mm->ml_entry ||
282         entry->fl_entry.next != &mm->fl_entry) {
283         return;
284     }
285
286     WSBMLISTDEL(&entry->fl_entry);
287     WSBMLISTDEL(&entry->ml_entry);
288     free(entry);
289 }