1 /*
2 * object_heap.c - Management of VA-API resources
3 *
4 * libva-vdpau-driver (C) 2009-2011 Splitted-Desktop Systems
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
19 */
20
21 #include "sysdeps.h"
22 #include <pthread.h>
23 #include "object_heap.h"
24
25 /* This code is:
26 * Copyright (c) 2007 Intel Corporation. All Rights Reserved.
27 *
28 * Permission is hereby granted, free of charge, to any person obtaining a
29 * copy of this software and associated documentation files (the
30 * "Software"), to deal in the Software without restriction, including
31 * without limitation the rights to use, copy, modify, merge, publish,
32 * distribute, sub license, and/or sell copies of the Software, and to
33 * permit persons to whom the Software is furnished to do so, subject to
34 * the following conditions:
35 *
36 * The above copyright notice and this permission notice (including the
37 * next paragraph) shall be included in all copies or substantial portions
38 * of the Software.
39 *
40 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
41 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
42 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
43 * IN NO EVENT SHALL PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR
44 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
45 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
46 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
47 */
48
49 #define LAST_FREE -1
50 #define ALLOCATED -2
51
52 /*
53 * Expands the heap
54 * Return 0 on success, -1 on error
55 */
56 static int
object_heap_expand(object_heap_p heap)57 object_heap_expand(object_heap_p heap)
58 {
59 int i;
60 void *new_heap_index;
61 int next_free;
62 int new_heap_size = heap->heap_size + heap->heap_increment;
63 int bucket_index = new_heap_size / heap->heap_increment - 1;
64
65 if (bucket_index >= heap->num_buckets) {
66 int new_num_buckets = heap->num_buckets + 8;
67 void **new_bucket;
68
69 new_bucket = realloc(heap->bucket, new_num_buckets * sizeof(void *));
70 if (NULL == new_bucket) {
71 return -1;
72 }
73
74 heap->num_buckets = new_num_buckets;
75 heap->bucket = new_bucket;
76 }
77
78 new_heap_index = (void *) malloc(heap->heap_increment * heap->object_size);
79 if (NULL == new_heap_index) {
80 return -1; /* Out of memory */
81 }
82
83 heap->bucket[bucket_index] = new_heap_index;
84 next_free = heap->next_free;
85 for (i = new_heap_size; i-- > heap->heap_size;) {
86 object_base_p obj = (object_base_p)(new_heap_index + (i - heap->heap_size) * heap->object_size);
87 obj->id = i + heap->id_offset;
88 obj->next_free = next_free;
89 next_free = i;
90 }
91 heap->next_free = next_free;
92 heap->heap_size = new_heap_size;
93 return 0; /* Success */
94 }
95
96 /*
97 * Return 0 on success, -1 on error
98 */
99 int
object_heap_init(object_heap_p heap,int object_size,int id_offset)100 object_heap_init(object_heap_p heap, int object_size, int id_offset)
101 {
102 pthread_mutex_init(&heap->mutex, NULL);
103 heap->object_size = object_size;
104 heap->id_offset = id_offset & OBJECT_HEAP_OFFSET_MASK;
105 heap->heap_size = 0;
106 heap->heap_increment = 16;
107 heap->next_free = LAST_FREE;
108 heap->num_buckets = 0;
109 heap->bucket = NULL;
110 return object_heap_expand(heap);
111 }
112
113 /*
114 * Allocates an object
115 * Returns the object ID on success, returns -1 on error
116 */
117 static int
object_heap_allocate_unlocked(object_heap_p heap)118 object_heap_allocate_unlocked(object_heap_p heap)
119 {
120 object_base_p obj;
121 int bucket_index, obj_index;
122
123 if (LAST_FREE == heap->next_free) {
124 if (-1 == object_heap_expand(heap)) {
125 return -1; /* Out of memory */
126 }
127 }
128 ASSERT(heap->next_free >= 0);
129
130 bucket_index = heap->next_free / heap->heap_increment;
131 obj_index = heap->next_free % heap->heap_increment;
132
133 obj = (object_base_p)(heap->bucket[bucket_index] + obj_index * heap->object_size);
134 heap->next_free = obj->next_free;
135 obj->next_free = ALLOCATED;
136 return obj->id;
137 }
138
139 int
object_heap_allocate(object_heap_p heap)140 object_heap_allocate(object_heap_p heap)
141 {
142 int ret;
143
144 pthread_mutex_lock(&heap->mutex);
145 ret = object_heap_allocate_unlocked(heap);
146 pthread_mutex_unlock(&heap->mutex);
147 return ret;
148 }
149
150 /*
151 * Lookup an object by object ID
152 * Returns a pointer to the object on success, returns NULL on error
153 */
154 static object_base_p
object_heap_lookup_unlocked(object_heap_p heap,int id)155 object_heap_lookup_unlocked(object_heap_p heap, int id)
156 {
157 object_base_p obj;
158 int bucket_index, obj_index;
159
160 if ((id < heap->id_offset) || (id > (heap->heap_size + heap->id_offset))) {
161 return NULL;
162 }
163 id &= OBJECT_HEAP_ID_MASK;
164 bucket_index = id / heap->heap_increment;
165 obj_index = id % heap->heap_increment;
166 obj = (object_base_p)(heap->bucket[bucket_index] + obj_index * heap->object_size);
167
168 /* Check if the object has in fact been allocated */
169 if (obj->next_free != ALLOCATED) {
170 return NULL;
171 }
172 return obj;
173 }
174
175 object_base_p
object_heap_lookup(object_heap_p heap,int id)176 object_heap_lookup(object_heap_p heap, int id)
177 {
178 object_base_p obj;
179
180 pthread_mutex_lock(&heap->mutex);
181 obj = object_heap_lookup_unlocked(heap, id);
182 pthread_mutex_unlock(&heap->mutex);
183 return obj;
184 }
185
186 /*
187 * Iterate over all objects in the heap.
188 * Returns a pointer to the first object on the heap, returns NULL if heap is empty.
189 */
190 object_base_p
object_heap_first(object_heap_p heap,object_heap_iterator * iter)191 object_heap_first(object_heap_p heap, object_heap_iterator *iter)
192 {
193 *iter = -1;
194 return object_heap_next(heap, iter);
195 }
196
197 /*
198 * Iterate over all objects in the heap.
199 * Returns a pointer to the next object on the heap, returns NULL if heap is empty.
200 */
201 static object_base_p
object_heap_next_unlocked(object_heap_p heap,object_heap_iterator * iter)202 object_heap_next_unlocked(object_heap_p heap, object_heap_iterator *iter)
203 {
204 object_base_p obj;
205 int bucket_index, obj_index;
206 int i = *iter + 1;
207
208 while (i < heap->heap_size) {
209 bucket_index = i / heap->heap_increment;
210 obj_index = i % heap->heap_increment;
211
212 obj = (object_base_p)(heap->bucket[bucket_index] + obj_index * heap->object_size);
213 if (obj->next_free == ALLOCATED) {
214 *iter = i;
215 return obj;
216 }
217 i++;
218 }
219 *iter = i;
220 return NULL;
221 }
222
223 object_base_p
object_heap_next(object_heap_p heap,object_heap_iterator * iter)224 object_heap_next(object_heap_p heap, object_heap_iterator *iter)
225 {
226 object_base_p obj;
227
228 pthread_mutex_lock(&heap->mutex);
229 obj = object_heap_next_unlocked(heap, iter);
230 pthread_mutex_unlock(&heap->mutex);
231 return obj;
232 }
233
234 /*
235 * Frees an object
236 */
237 static void
object_heap_free_unlocked(object_heap_p heap,object_base_p obj)238 object_heap_free_unlocked(object_heap_p heap, object_base_p obj)
239 {
240 /* Check if the object has in fact been allocated */
241 ASSERT(obj->next_free == ALLOCATED);
242
243 obj->next_free = heap->next_free;
244 heap->next_free = obj->id & OBJECT_HEAP_ID_MASK;
245 }
246
247 void
object_heap_free(object_heap_p heap,object_base_p obj)248 object_heap_free(object_heap_p heap, object_base_p obj)
249 {
250 if (!obj)
251 return;
252 pthread_mutex_lock(&heap->mutex);
253 object_heap_free_unlocked(heap, obj);
254 pthread_mutex_unlock(&heap->mutex);
255 }
256
257 /*
258 * Destroys a heap, the heap must be empty.
259 */
260 void
object_heap_destroy(object_heap_p heap)261 object_heap_destroy(object_heap_p heap)
262 {
263 object_base_p obj;
264 int bucket_index, obj_index, i;
265
266 /* Check if heap is empty */
267 for (i = 0; i < heap->heap_size; i++) {
268 /* Check if object is not still allocated */
269 bucket_index = i / heap->heap_increment;
270 obj_index = i % heap->heap_increment;
271 obj = (object_base_p)(heap->bucket[bucket_index] + obj_index * heap->object_size);
272 ASSERT(obj->next_free != ALLOCATED);
273 }
274
275 for (i = 0; i < heap->heap_size / heap->heap_increment; i++) {
276 free(heap->bucket[i]);
277 }
278
279 pthread_mutex_destroy(&heap->mutex);
280
281 free(heap->bucket);
282 heap->bucket = NULL;
283 heap->heap_size = 0;
284 heap->next_free = LAST_FREE;
285 }
286