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 #include "main/imports.h" 32 #include "main/shaderobj.h" 33 #include "program/prog_cache.h" 34 #include "program/program.h" 35 36 37 struct cache_item 38 { 39 GLuint hash; 40 unsigned keysize; 41 void *key; 42 struct gl_program *program; 43 struct cache_item *next; 44 }; 45 46 struct gl_program_cache 47 { 48 struct cache_item **items; 49 struct cache_item *last; 50 GLuint size, n_items; 51 }; 52 53 54 55 /** 56 * Compute hash index from state key. 57 */ 58 static GLuint 59 hash_key(const void *key, GLuint key_size) 60 { 61 const GLuint *ikey = (const GLuint *) key; 62 GLuint hash = 0, i; 63 64 assert(key_size >= 4); 65 66 /* Make a slightly better attempt at a hash function: 67 */ 68 for (i = 0; i < key_size / sizeof(*ikey); i++) 69 { 70 hash += ikey[i]; 71 hash += (hash << 10); 72 hash ^= (hash >> 6); 73 } 74 75 return hash; 76 } 77 78 79 /** 80 * Rebuild/expand the hash table to accommodate more entries 81 */ 82 static void 83 rehash(struct gl_program_cache *cache) 84 { 85 struct cache_item **items; 86 struct cache_item *c, *next; 87 GLuint size, i; 88 89 cache->last = NULL; 90 91 size = cache->size * 3; 92 items = malloc(size * sizeof(*items)); 93 memset(items, 0, size * sizeof(*items)); 94 95 for (i = 0; i < cache->size; i++) 96 for (c = cache->items[i]; c; c = next) { 97 next = c->next; 98 c->next = items[c->hash % size]; 99 items[c->hash % size] = c; 100 } 101 102 free(cache->items); 103 cache->items = items; 104 cache->size = size; 105 } 106 107 108 static void 109 clear_cache(struct gl_context *ctx, struct gl_program_cache *cache, 110 GLboolean shader) 111 { 112 struct cache_item *c, *next; 113 GLuint i; 114 115 cache->last = NULL; 116 117 for (i = 0; i < cache->size; i++) { 118 for (c = cache->items[i]; c; c = next) { 119 next = c->next; 120 free(c->key); 121 if (shader) { 122 _mesa_reference_shader_program(ctx, 123 (struct gl_shader_program **)&c->program, 124 NULL); 125 } else { 126 _mesa_reference_program(ctx, &c->program, NULL); 127 } 128 free(c); 129 } 130 cache->items[i] = NULL; 131 } 132 133 134 cache->n_items = 0; 135 } 136 137 138 139 struct gl_program_cache * 140 _mesa_new_program_cache(void) 141 { 142 struct gl_program_cache *cache = CALLOC_STRUCT(gl_program_cache); 143 if (cache) { 144 cache->size = 17; 145 cache->items = 146 calloc(cache->size, sizeof(struct cache_item *)); 147 if (!cache->items) { 148 free(cache); 149 return NULL; 150 } 151 } 152 return cache; 153 } 154 155 156 void 157 _mesa_delete_program_cache(struct gl_context *ctx, struct gl_program_cache *cache) 158 { 159 clear_cache(ctx, cache, GL_FALSE); 160 free(cache->items); 161 free(cache); 162 } 163 164 void 165 _mesa_delete_shader_cache(struct gl_context *ctx, 166 struct gl_program_cache *cache) 167 { 168 clear_cache(ctx, cache, GL_TRUE); 169 free(cache->items); 170 free(cache); 171 } 172 173 174 struct gl_program * 175 _mesa_search_program_cache(struct gl_program_cache *cache, 176 const void *key, GLuint keysize) 177 { 178 if (cache->last && 179 cache->last->keysize == keysize && 180 memcmp(cache->last->key, key, keysize) == 0) { 181 return cache->last->program; 182 } 183 else { 184 const GLuint hash = hash_key(key, keysize); 185 struct cache_item *c; 186 187 for (c = cache->items[hash % cache->size]; c; c = c->next) { 188 if (c->hash == hash && 189 c->keysize == keysize && 190 memcmp(c->key, key, keysize) == 0) { 191 192 cache->last = c; 193 return c->program; 194 } 195 } 196 197 return NULL; 198 } 199 } 200 201 202 void 203 _mesa_program_cache_insert(struct gl_context *ctx, 204 struct gl_program_cache *cache, 205 const void *key, GLuint keysize, 206 struct gl_program *program) 207 { 208 const GLuint hash = hash_key(key, keysize); 209 struct cache_item *c = CALLOC_STRUCT(cache_item); 210 211 c->hash = hash; 212 213 c->key = malloc(keysize); 214 memcpy(c->key, key, keysize); 215 c->keysize = keysize; 216 217 c->program = program; /* no refcount change */ 218 219 if (cache->n_items > cache->size * 1.5) { 220 if (cache->size < 1000) 221 rehash(cache); 222 else 223 clear_cache(ctx, cache, GL_FALSE); 224 } 225 226 cache->n_items++; 227 c->next = cache->items[hash % cache->size]; 228 cache->items[hash % cache->size] = c; 229 } 230 231 void 232 _mesa_shader_cache_insert(struct gl_context *ctx, 233 struct gl_program_cache *cache, 234 const void *key, GLuint keysize, 235 struct gl_shader_program *program) 236 { 237 const GLuint hash = hash_key(key, keysize); 238 struct cache_item *c = CALLOC_STRUCT(cache_item); 239 240 c->hash = hash; 241 242 c->key = malloc(keysize); 243 memcpy(c->key, key, keysize); 244 c->keysize = keysize; 245 246 c->program = (struct gl_program *)program; /* no refcount change */ 247 248 if (cache->n_items > cache->size * 1.5) { 249 if (cache->size < 1000) 250 rehash(cache); 251 else 252 clear_cache(ctx, cache, GL_TRUE); 253 } 254 255 cache->n_items++; 256 c->next = cache->items[hash % cache->size]; 257 cache->items[hash % cache->size] = c; 258 } 259