1 /*
2 +----------------------------------------------------------------------+
3 | Zend OPcache |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 1998-2016 The PHP Group |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 3.01 of the PHP license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | http://www.php.net/license/3_01.txt |
11 | If you did not receive a copy of the PHP license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@php.net so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
15 | Authors: Andi Gutmans <andi@zend.com> |
16 | Zeev Suraski <zeev@zend.com> |
17 | Stanislav Malyshev <stas@zend.com> |
18 | Dmitry Stogov <dmitry@zend.com> |
19 +----------------------------------------------------------------------+
20 */
21
22 #include "ZendAccelerator.h"
23 #include "zend_accelerator_hash.h"
24 #include "zend_hash.h"
25 #include "zend_shared_alloc.h"
26
27 /* Generated on an Octa-ALPHA 300MHz CPU & 2.5GB RAM monster */
28 static uint prime_numbers[] =
29 {5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963, 16229, 32531, 65407, 130987, 262237, 524521, 1048793 };
30 static uint num_prime_numbers = sizeof(prime_numbers) / sizeof(uint);
31
zend_accel_hash_clean(zend_accel_hash * accel_hash)32 void zend_accel_hash_clean(zend_accel_hash *accel_hash)
33 {
34 accel_hash->num_entries = 0;
35 accel_hash->num_direct_entries = 0;
36 memset(accel_hash->hash_table, 0, sizeof(zend_accel_hash_entry *)*accel_hash->max_num_entries);
37 }
38
zend_accel_hash_init(zend_accel_hash * accel_hash,zend_uint hash_size)39 void zend_accel_hash_init(zend_accel_hash *accel_hash, zend_uint hash_size)
40 {
41 uint i;
42
43 for (i=0; i<num_prime_numbers; i++) {
44 if (hash_size <= prime_numbers[i]) {
45 hash_size = prime_numbers[i];
46 break;
47 }
48 }
49
50 accel_hash->num_entries = 0;
51 accel_hash->num_direct_entries = 0;
52 accel_hash->max_num_entries = hash_size;
53
54 /* set up hash pointers table */
55 accel_hash->hash_table = zend_shared_alloc(sizeof(zend_accel_hash_entry *)*accel_hash->max_num_entries);
56 if (!accel_hash->hash_table) {
57 zend_accel_error(ACCEL_LOG_FATAL, "Insufficient shared memory!");
58 return;
59 }
60
61 /* set up hash values table */
62 accel_hash->hash_entries = zend_shared_alloc(sizeof(zend_accel_hash_entry)*accel_hash->max_num_entries);
63 if (!accel_hash->hash_entries) {
64 zend_accel_error(ACCEL_LOG_FATAL, "Insufficient shared memory!");
65 return;
66 }
67 memset(accel_hash->hash_table, 0, sizeof(zend_accel_hash_entry *)*accel_hash->max_num_entries);
68 }
69
70 /* Returns NULL if hash is full
71 * Returns pointer the actual hash entry on success
72 * key needs to be already allocated as it is not copied
73 */
zend_accel_hash_update(zend_accel_hash * accel_hash,char * key,zend_uint key_length,zend_bool indirect,void * data)74 zend_accel_hash_entry* zend_accel_hash_update(zend_accel_hash *accel_hash, char *key, zend_uint key_length, zend_bool indirect, void *data)
75 {
76 zend_ulong hash_value;
77 zend_ulong index;
78 zend_accel_hash_entry *entry;
79 zend_accel_hash_entry *indirect_bucket = NULL;
80 #ifndef ZEND_WIN32
81 TSRMLS_FETCH();
82 #endif
83
84 if (indirect) {
85 indirect_bucket = (zend_accel_hash_entry*)data;
86 while (indirect_bucket->indirect) {
87 indirect_bucket = (zend_accel_hash_entry*)indirect_bucket->data;
88 }
89 }
90
91 hash_value = zend_inline_hash_func(key, key_length);
92 #ifndef ZEND_WIN32
93 hash_value ^= ZCG(root_hash);
94 #endif
95 index = hash_value % accel_hash->max_num_entries;
96
97 /* try to see if the element already exists in the hash */
98 entry = accel_hash->hash_table[index];
99 while (entry) {
100 if (entry->hash_value == hash_value
101 && entry->key_length == key_length
102 && !memcmp(entry->key, key, key_length)) {
103
104 if (entry->indirect) {
105 if (indirect_bucket) {
106 entry->data = indirect_bucket;
107 } else {
108 ((zend_accel_hash_entry*)entry->data)->data = data;
109 }
110 } else {
111 if (indirect_bucket) {
112 accel_hash->num_direct_entries--;
113 entry->data = indirect_bucket;
114 entry->indirect = 1;
115 } else {
116 entry->data = data;
117 }
118 }
119 return entry;
120 }
121 entry = entry->next;
122 }
123
124 /* Does not exist, add a new entry */
125 if (accel_hash->num_entries == accel_hash->max_num_entries) {
126 return NULL;
127 }
128
129 entry = &accel_hash->hash_entries[accel_hash->num_entries++];
130 if (indirect) {
131 entry->data = indirect_bucket;
132 entry->indirect = 1;
133 } else {
134 accel_hash->num_direct_entries++;
135 entry->data = data;
136 entry->indirect = 0;
137 }
138 entry->hash_value = hash_value;
139 entry->key = key;
140 entry->key_length = key_length;
141 entry->next = accel_hash->hash_table[index];
142 accel_hash->hash_table[index] = entry;
143 return entry;
144 }
145
146 /* Returns the data associated with key on success
147 * Returns NULL if data doesn't exist
148 */
zend_accel_hash_find(zend_accel_hash * accel_hash,char * key,zend_uint key_length)149 void* zend_accel_hash_find(zend_accel_hash *accel_hash, char *key, zend_uint key_length)
150 {
151 zend_ulong hash_value;
152 zend_ulong index;
153 zend_accel_hash_entry *entry;
154 #ifndef ZEND_WIN32
155 TSRMLS_FETCH();
156 #endif
157
158 hash_value = zend_inline_hash_func(key, key_length);
159 #ifndef ZEND_WIN32
160 hash_value ^= ZCG(root_hash);
161 #endif
162 index = hash_value % accel_hash->max_num_entries;
163
164 entry = accel_hash->hash_table[index];
165 while (entry) {
166 if (entry->hash_value == hash_value
167 && entry->key_length == key_length
168 && !memcmp(entry->key, key, key_length)) {
169 if (entry->indirect) {
170 return ((zend_accel_hash_entry *) entry->data)->data;
171 } else {
172 return entry->data;
173 }
174 }
175 entry = entry->next;
176 }
177 return NULL;
178 }
179
180 /* Returns the hash entry associated with key on success
181 * Returns NULL if it doesn't exist
182 */
zend_accel_hash_find_entry(zend_accel_hash * accel_hash,char * key,zend_uint key_length)183 zend_accel_hash_entry* zend_accel_hash_find_entry(zend_accel_hash *accel_hash, char *key, zend_uint key_length)
184 {
185 zend_ulong hash_value;
186 zend_ulong index;
187 zend_accel_hash_entry *entry;
188 #ifndef ZEND_WIN32
189 TSRMLS_FETCH();
190 #endif
191
192 hash_value = zend_inline_hash_func(key, key_length);
193 #ifndef ZEND_WIN32
194 hash_value ^= ZCG(root_hash);
195 #endif
196 index = hash_value % accel_hash->max_num_entries;
197
198 entry = accel_hash->hash_table[index];
199 while (entry) {
200 if (entry->hash_value == hash_value
201 && entry->key_length == key_length
202 && !memcmp(entry->key, key, key_length)) {
203 if (entry->indirect) {
204 return (zend_accel_hash_entry *) entry->data;
205 } else {
206 return entry;
207 }
208 }
209 entry = entry->next;
210 }
211 return NULL;
212 }
213
zend_accel_hash_unlink(zend_accel_hash * accel_hash,char * key,zend_uint key_length)214 int zend_accel_hash_unlink(zend_accel_hash *accel_hash, char *key, zend_uint key_length)
215 {
216 zend_ulong hash_value;
217 zend_ulong index;
218 zend_accel_hash_entry *entry, *last_entry=NULL;
219 #ifndef ZEND_WIN32
220 TSRMLS_FETCH();
221 #endif
222
223 hash_value = zend_inline_hash_func(key, key_length);
224 #ifndef ZEND_WIN32
225 hash_value ^= ZCG(root_hash);
226 #endif
227 index = hash_value % accel_hash->max_num_entries;
228
229 entry = accel_hash->hash_table[index];
230 while (entry) {
231 if (entry->hash_value == hash_value
232 && entry->key_length == key_length
233 && !memcmp(entry->key, key, key_length)) {
234 if (!entry->indirect) {
235 accel_hash->num_direct_entries--;
236 }
237 if (last_entry) {
238 last_entry->next = entry->next;
239 } else {
240 accel_hash->hash_table[index] = entry->next;
241 }
242 return SUCCESS;
243 }
244 last_entry = entry;
245 entry = entry->next;
246 }
247 return FAILURE;
248 }
249
