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