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 "util/glheader.h"
30 #include "main/shader_types.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
166 struct gl_program *
_mesa_search_program_cache(struct gl_program_cache * cache,const void * key,GLuint keysize)167 _mesa_search_program_cache(struct gl_program_cache *cache,
168 const void *key, GLuint keysize)
169 {
170 if (cache->last &&
171 cache->last->keysize == keysize &&
172 memcmp(cache->last->key, key, keysize) == 0) {
173 return cache->last->program;
174 }
175 else {
176 const GLuint hash = hash_key(key, keysize);
177 struct cache_item *c;
178
179 for (c = cache->items[hash % cache->size]; c; c = c->next) {
180 if (c->hash == hash &&
181 c->keysize == keysize &&
182 memcmp(c->key, key, keysize) == 0) {
183
184 cache->last = c;
185 return c->program;
186 }
187 }
188
189 return NULL;
190 }
191 }
192
193
194 void
_mesa_program_cache_insert(struct gl_context * ctx,struct gl_program_cache * cache,const void * key,GLuint keysize,struct gl_program * program)195 _mesa_program_cache_insert(struct gl_context *ctx,
196 struct gl_program_cache *cache,
197 const void *key, GLuint keysize,
198 struct gl_program *program)
199 {
200 const GLuint hash = hash_key(key, keysize);
201 struct cache_item *c = CALLOC_STRUCT(cache_item);
202
203 c->hash = hash;
204
205 c->key = malloc(keysize);
206 memcpy(c->key, key, keysize);
207 c->keysize = keysize;
208
209 c->program = program; /* no refcount change */
210
211 if (cache->n_items > cache->size * 1.5) {
212 if (cache->size < 1000)
213 rehash(cache);
214 else
215 clear_cache(ctx, cache, GL_FALSE);
216 }
217
218 cache->n_items++;
219 c->next = cache->items[hash % cache->size];
220 cache->items[hash % cache->size] = c;
221 }
222