1 /*
2  * Copyright (c) 2011 Intel Corporation. All Rights Reserved.
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a
5  * copy of this software and associated documentation files (the
6  * "Software"), to deal in the Software without restriction, including
7  * without limitation the rights to use, copy, modify, merge, publish,
8  * distribute, sub license, and/or sell copies of the Software, and to
9  * permit persons to whom the Software is furnished to do so, subject to
10  * the following conditions:
11  *
12  * The above copyright notice and this permission notice (including the
13  * next paragraph) shall be included in all copies or substantial portions
14  * of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
17  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
19  * IN NO EVENT SHALL PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR
20  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
21  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
22  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23  *
24  * Authors:
25  *    Waldo Bastian <waldo.bastian@intel.com>
26  *
27  */
28 
29 #include "object_heap.h"
30 
31 #include <stdlib.h>
32 #include <string.h>
33 
34 #include "psb_def.h"
35 #include "psb_drv_debug.h"
36 
37 #define LAST_FREE    -1
38 #define ALLOCATED    -2
39 #define SUSPENDED    -3
40 
41 /*
42  * Expands the heap
43  * Return 0 on success, -1 on error
44  */
object_heap_expand(object_heap_p heap)45 static int object_heap_expand(object_heap_p heap)
46 {
47     int i;
48     int malloc_error = FALSE;
49     object_base_p *new_heap_index;
50     int next_free;
51     int new_heap_size = heap->heap_size + heap->heap_increment;
52 
53     new_heap_index = (object_base_p *) realloc(heap->heap_index, new_heap_size * sizeof(object_base_p));
54     if (NULL == new_heap_index) {
55         return -1; /* Out of memory */
56     }
57     heap->heap_index = new_heap_index;
58     next_free = heap->next_free;
59     for (i = new_heap_size; i-- > heap->heap_size;) {
60         object_base_p obj = (object_base_p) calloc(1, heap->object_size);
61         heap->heap_index[i] = obj;
62         if (NULL == obj) {
63             malloc_error = TRUE;
64             continue; /* Clean up after the loop is completely done */
65         }
66         obj->id = i + heap->id_offset;
67         obj->next_free = next_free;
68         next_free = i;
69     }
70 
71     if (malloc_error) {
72         /* Clean up the mess */
73         for (i = new_heap_size; i-- > heap->heap_size;) {
74             if (heap->heap_index[i]) {
75                 free(heap->heap_index[i]);
76             }
77         }
78         /* heap->heap_index is left as is */
79         return -1; /* Out of memory */
80     }
81     heap->next_free = next_free;
82     heap->heap_size = new_heap_size;
83     return 0; /* Success */
84 }
85 
86 /*
87  * Return 0 on success, -1 on error
88  */
object_heap_init(object_heap_p heap,int object_size,int id_offset)89 int object_heap_init(object_heap_p heap, int object_size, int id_offset)
90 {
91     heap->object_size = object_size;
92     heap->id_offset = id_offset & OBJECT_HEAP_OFFSET_MASK;
93     heap->heap_size = 0;
94     heap->heap_increment = 16;
95     heap->heap_index = NULL;
96     heap->next_free = LAST_FREE;
97     return object_heap_expand(heap);
98 }
99 
100 /*
101  * Allocates an object
102  * Returns the object ID on success, returns -1 on error
103  */
object_heap_allocate(object_heap_p heap)104 int object_heap_allocate(object_heap_p heap)
105 {
106     object_base_p obj;
107     if (LAST_FREE == heap->next_free) {
108         if (-1 == object_heap_expand(heap)) {
109             return -1; /* Out of memory */
110         }
111     }
112     ASSERT(heap->next_free >= 0);
113 
114     obj = heap->heap_index[heap->next_free];
115     heap->next_free = obj->next_free;
116     obj->next_free = ALLOCATED;
117     return obj->id;
118 }
119 
120 /*
121  * Lookup an object by object ID
122  * Returns a pointer to the object on success, returns NULL on error
123  */
object_heap_lookup(object_heap_p heap,int id)124 object_base_p object_heap_lookup(object_heap_p heap, int id)
125 {
126     object_base_p obj;
127     if ((id < heap->id_offset) || (id > (heap->heap_size + heap->id_offset))) {
128         return NULL;
129     }
130     id &= OBJECT_HEAP_ID_MASK;
131     obj = heap->heap_index[id];
132 
133     /* Check if the object has in fact been allocated */
134 #if 0
135     if (obj->next_free != ALLOCATED) {
136         return NULL;
137     }
138 #endif
139     return obj;
140 }
141 
142 /*
143  * Iterate over all objects in the heap.
144  * Returns a pointer to the first object on the heap, returns NULL if heap is empty.
145  */
object_heap_first(object_heap_p heap,object_heap_iterator * iter)146 object_base_p object_heap_first(object_heap_p heap, object_heap_iterator *iter)
147 {
148     *iter = -1;
149     return object_heap_next(heap, iter);
150 }
151 
152 /*
153  * Iterate over all objects in the heap.
154  * Returns a pointer to the next object on the heap, returns NULL if heap is empty.
155  */
object_heap_next(object_heap_p heap,object_heap_iterator * iter)156 object_base_p object_heap_next(object_heap_p heap, object_heap_iterator *iter)
157 {
158     object_base_p obj;
159     int i = *iter + 1;
160     while (i < heap->heap_size) {
161         obj = heap->heap_index[i];
162         if ((obj->next_free == ALLOCATED) || (obj->next_free == SUSPENDED)) {
163             *iter = i;
164             return obj;
165         }
166         i++;
167     }
168     *iter = i;
169     return NULL;
170 }
171 
172 
173 
174 /*
175  * Frees an object
176  */
object_heap_free(object_heap_p heap,object_base_p obj)177 void object_heap_free(object_heap_p heap, object_base_p obj)
178 {
179     /* Don't complain about NULL pointers */
180     if (NULL != obj) {
181         /* Check if the object has in fact been allocated */
182         ASSERT((obj->next_free == ALLOCATED) || (obj->next_free == SUSPENDED));
183 
184         obj->next_free = heap->next_free;
185         heap->next_free = obj->id & OBJECT_HEAP_ID_MASK;
186     }
187 }
188 
189 /*
190  * Destroys a heap, the heap must be empty.
191  */
object_heap_destroy(object_heap_p heap)192 void object_heap_destroy(object_heap_p heap)
193 {
194     object_base_p obj;
195     int i;
196     for (i = 0; i < heap->heap_size; i++) {
197         /* Check if object is not still allocated */
198         obj = heap->heap_index[i];
199         ASSERT(obj->next_free != ALLOCATED);
200         ASSERT(obj->next_free != SUSPENDED);
201         /* Free object itself */
202         free(obj);
203     }
204     free(heap->heap_index);
205     heap->heap_size = 0;
206     heap->heap_index = NULL;
207     heap->next_free = LAST_FREE;
208 }
209 
210 /*
211  * Suspend an object
212  * Suspended objects can not be looked up
213  */
object_heap_suspend_object(object_base_p obj,int suspend)214 void object_heap_suspend_object(object_base_p obj, int suspend)
215 {
216     if (suspend) {
217         ASSERT(obj->next_free == ALLOCATED);
218         obj->next_free = SUSPENDED;
219     } else {
220         ASSERT(obj->next_free == SUSPENDED);
221         obj->next_free = ALLOCATED;
222     }
223 }
224