1 /**************************************************************************
2 *
3 * Copyright 2003 VMware, Inc.
4 * All Rights Reserved.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sub license, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial portions
16 * of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
21 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25 *
26 **************************************************************************/
27
28
29 #include "main/glheader.h"
30 #include "main/mtypes.h"
31
32 #include "main/shaderobj.h"
33 #include "program/prog_cache.h"
34 #include "program/program.h"
35 #include "util/u_memory.h"
36
37
38 struct cache_item
39 {
40 GLuint hash;
41 unsigned keysize;
42 void *key;
43 struct gl_program *program;
44 struct cache_item *next;
45 };
46
47 struct gl_program_cache
48 {
49 struct cache_item **items;
50 struct cache_item *last;
51 GLuint size, n_items;
52 };
53
54
55
56 /**
57 * Compute hash index from state key.
58 */
59 static GLuint
hash_key(const void * key,GLuint key_size)60 hash_key(const void *key, GLuint key_size)
61 {
62 const GLuint *ikey = (const GLuint *) key;
63 GLuint hash = 0, i;
64
65 assert(key_size >= 4);
66
67 /* Make a slightly better attempt at a hash function:
68 */
69 for (i = 0; i < key_size / sizeof(*ikey); i++)
70 {
71 hash += ikey[i];
72 hash += (hash << 10);
73 hash ^= (hash >> 6);
74 }
75
76 return hash;
77 }
78
79
80 /**
81 * Rebuild/expand the hash table to accommodate more entries
82 */
83 static void
rehash(struct gl_program_cache * cache)84 rehash(struct gl_program_cache *cache)
85 {
86 struct cache_item **items;
87 struct cache_item *c, *next;
88 GLuint size, i;
89
90 cache->last = NULL;
91
92 size = cache->size * 3;
93 items = malloc(size * sizeof(*items));
94 memset(items, 0, size * sizeof(*items));
95
96 for (i = 0; i < cache->size; i++)
97 for (c = cache->items[i]; c; c = next) {
98 next = c->next;
99 c->next = items[c->hash % size];
100 items[c->hash % size] = c;
101 }
102
103 free(cache->items);
104 cache->items = items;
105 cache->size = size;
106 }
107
108
109 static void
clear_cache(struct gl_context * ctx,struct gl_program_cache * cache,GLboolean shader)110 clear_cache(struct gl_context *ctx, struct gl_program_cache *cache,
111 GLboolean shader)
112 {
113 struct cache_item *c, *next;
114 GLuint i;
115
116 cache->last = NULL;
117
118 for (i = 0; i < cache->size; i++) {
119 for (c = cache->items[i]; c; c = next) {
120 next = c->next;
121 free(c->key);
122 if (shader) {
123 _mesa_reference_shader_program(ctx,
124 (struct gl_shader_program **)&c->program,
125 NULL);
126 } else {
127 _mesa_reference_program(ctx, &c->program, NULL);
128 }
129 free(c);
130 }
131 cache->items[i] = NULL;
132 }
133
134
135 cache->n_items = 0;
136 }
137
138
139
140 struct gl_program_cache *
_mesa_new_program_cache(void)141 _mesa_new_program_cache(void)
142 {
143 struct gl_program_cache *cache = CALLOC_STRUCT(gl_program_cache);
144 if (cache) {
145 cache->size = 17;
146 cache->items =
147 calloc(cache->size, sizeof(struct cache_item *));
148 if (!cache->items) {
149 free(cache);
150 return NULL;
151 }
152 }
153 return cache;
154 }
155
156
157 void
_mesa_delete_program_cache(struct gl_context * ctx,struct gl_program_cache * cache)158 _mesa_delete_program_cache(struct gl_context *ctx, struct gl_program_cache *cache)
159 {
160 clear_cache(ctx, cache, GL_FALSE);
161 free(cache->items);
162 free(cache);
163 }
164
165 void
_mesa_delete_shader_cache(struct gl_context * ctx,struct gl_program_cache * cache)166 _mesa_delete_shader_cache(struct gl_context *ctx,
167 struct gl_program_cache *cache)
168 {
169 clear_cache(ctx, cache, GL_TRUE);
170 free(cache->items);
171 free(cache);
172 }
173
174
175 struct gl_program *
_mesa_search_program_cache(struct gl_program_cache * cache,const void * key,GLuint keysize)176 _mesa_search_program_cache(struct gl_program_cache *cache,
177 const void *key, GLuint keysize)
178 {
179 if (cache->last &&
180 cache->last->keysize == keysize &&
181 memcmp(cache->last->key, key, keysize) == 0) {
182 return cache->last->program;
183 }
184 else {
185 const GLuint hash = hash_key(key, keysize);
186 struct cache_item *c;
187
188 for (c = cache->items[hash % cache->size]; c; c = c->next) {
189 if (c->hash == hash &&
190 c->keysize == keysize &&
191 memcmp(c->key, key, keysize) == 0) {
192
193 cache->last = c;
194 return c->program;
195 }
196 }
197
198 return NULL;
199 }
200 }
201
202
203 void
_mesa_program_cache_insert(struct gl_context * ctx,struct gl_program_cache * cache,const void * key,GLuint keysize,struct gl_program * program)204 _mesa_program_cache_insert(struct gl_context *ctx,
205 struct gl_program_cache *cache,
206 const void *key, GLuint keysize,
207 struct gl_program *program)
208 {
209 const GLuint hash = hash_key(key, keysize);
210 struct cache_item *c = CALLOC_STRUCT(cache_item);
211
212 c->hash = hash;
213
214 c->key = malloc(keysize);
215 memcpy(c->key, key, keysize);
216 c->keysize = keysize;
217
218 c->program = program; /* no refcount change */
219
220 if (cache->n_items > cache->size * 1.5) {
221 if (cache->size < 1000)
222 rehash(cache);
223 else
224 clear_cache(ctx, cache, GL_FALSE);
225 }
226
227 cache->n_items++;
228 c->next = cache->items[hash % cache->size];
229 cache->items[hash % cache->size] = c;
230 }
231
232 void
_mesa_shader_cache_insert(struct gl_context * ctx,struct gl_program_cache * cache,const void * key,GLuint keysize,struct gl_shader_program * program)233 _mesa_shader_cache_insert(struct gl_context *ctx,
234 struct gl_program_cache *cache,
235 const void *key, GLuint keysize,
236 struct gl_shader_program *program)
237 {
238 const GLuint hash = hash_key(key, keysize);
239 struct cache_item *c = CALLOC_STRUCT(cache_item);
240
241 c->hash = hash;
242
243 c->key = malloc(keysize);
244 memcpy(c->key, key, keysize);
245 c->keysize = keysize;
246
247 c->program = (struct gl_program *)program; /* no refcount change */
248
249 if (cache->n_items > cache->size * 1.5) {
250 if (cache->size < 1000)
251 rehash(cache);
252 else
253 clear_cache(ctx, cache, GL_TRUE);
254 }
255
256 cache->n_items++;
257 c->next = cache->items[hash % cache->size];
258 cache->items[hash % cache->size] = c;
259 }
260