1 /*
2    +----------------------------------------------------------------------+
3    | Zend OPcache                                                         |
4    +----------------------------------------------------------------------+
5    | Copyright (c) 1998-2018 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,uint32_t hash_size)39 void zend_accel_hash_init(zend_accel_hash *accel_hash, uint32_t 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,uint32_t key_length,zend_bool indirect,void * data)74 zend_accel_hash_entry* zend_accel_hash_update(zend_accel_hash *accel_hash, char *key, uint32_t 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 
81 	if (indirect) {
82 		indirect_bucket = (zend_accel_hash_entry*)data;
83 		while (indirect_bucket->indirect) {
84 			indirect_bucket = (zend_accel_hash_entry*)indirect_bucket->data;
85 		}
86 	}
87 
88 	hash_value = zend_inline_hash_func(key, key_length);
89 #ifndef ZEND_WIN32
90 	hash_value ^= ZCG(root_hash);
91 #endif
92 	index = hash_value % accel_hash->max_num_entries;
93 
94 	/* try to see if the element already exists in the hash */
95 	entry = accel_hash->hash_table[index];
96 	while (entry) {
97 		if (entry->hash_value == hash_value
98 			&& entry->key_length == key_length
99 			&& !memcmp(entry->key, key, key_length)) {
100 
101 			if (entry->indirect) {
102 				if (indirect_bucket) {
103 					entry->data = indirect_bucket;
104 				} else {
105 					((zend_accel_hash_entry*)entry->data)->data = data;
106 				}
107 			} else {
108 				if (indirect_bucket) {
109 					accel_hash->num_direct_entries--;
110 					entry->data = indirect_bucket;
111 					entry->indirect = 1;
112 				} else {
113 					entry->data = data;
114 				}
115 			}
116 			return entry;
117 		}
118 		entry = entry->next;
119 	}
120 
121 	/* Does not exist, add a new entry */
122 	if (accel_hash->num_entries == accel_hash->max_num_entries) {
123 		return NULL;
124 	}
125 
126 	entry = &accel_hash->hash_entries[accel_hash->num_entries++];
127 	if (indirect) {
128 		entry->data = indirect_bucket;
129 		entry->indirect = 1;
130 	} else {
131 		accel_hash->num_direct_entries++;
132 		entry->data = data;
133 		entry->indirect = 0;
134 	}
135 	entry->hash_value = hash_value;
136 	entry->key = key;
137 	entry->key_length = key_length;
138 	entry->next = accel_hash->hash_table[index];
139 	accel_hash->hash_table[index] = entry;
140 	return entry;
141 }
142 
zend_accel_hash_find_ex(zend_accel_hash * accel_hash,char * key,uint32_t key_length,zend_ulong hash_value,int data)143 static zend_always_inline void* zend_accel_hash_find_ex(zend_accel_hash *accel_hash, char *key, uint32_t key_length, zend_ulong hash_value, int data)
144 {
145 	zend_ulong index;
146 	zend_accel_hash_entry *entry;
147 
148 #ifndef ZEND_WIN32
149 	hash_value ^= ZCG(root_hash);
150 #endif
151 	index = hash_value % accel_hash->max_num_entries;
152 
153 	entry = accel_hash->hash_table[index];
154 	while (entry) {
155 		if (entry->hash_value == hash_value
156 			&& entry->key_length == key_length
157 			&& !memcmp(entry->key, key, key_length)) {
158 			if (entry->indirect) {
159 				if (data) {
160 					return ((zend_accel_hash_entry*)entry->data)->data;
161 				} else {
162 					return entry->data;
163 				}
164 			} else {
165 				if (data) {
166 					return entry->data;
167 				} else {
168 					return entry;
169 				}
170 			}
171 		}
172 		entry = entry->next;
173 	}
174 	return NULL;
175 }
176 
177 /* Returns the data associated with key on success
178  * Returns NULL if data doesn't exist
179  */
zend_accel_hash_find(zend_accel_hash * accel_hash,zend_string * key)180 void* zend_accel_hash_find(zend_accel_hash *accel_hash, zend_string *key)
181 {
182 	return zend_accel_hash_find_ex(
183 		accel_hash,
184 		ZSTR_VAL(key),
185 		ZSTR_LEN(key),
186 		zend_string_hash_val(key),
187 		1);
188 }
189 
190 /* Returns the hash entry associated with key on success
191  * Returns NULL if it doesn't exist
192  */
zend_accel_hash_find_entry(zend_accel_hash * accel_hash,zend_string * key)193 zend_accel_hash_entry* zend_accel_hash_find_entry(zend_accel_hash *accel_hash, zend_string *key)
194 {
195 	return (zend_accel_hash_entry *)zend_accel_hash_find_ex(
196 		accel_hash,
197 		ZSTR_VAL(key),
198 		ZSTR_LEN(key),
199 		zend_string_hash_val(key),
200 		0);
201 }
202 
203 /* Returns the data associated with key on success
204  * Returns NULL if data doesn't exist
205  */
zend_accel_hash_str_find(zend_accel_hash * accel_hash,char * key,uint32_t key_length)206 void* zend_accel_hash_str_find(zend_accel_hash *accel_hash, char *key, uint32_t key_length)
207 {
208 	return zend_accel_hash_find_ex(
209 		accel_hash,
210 		key,
211 		key_length,
212 		zend_inline_hash_func(key, key_length),
213 		1);
214 }
215 
216 /* Returns the hash entry associated with key on success
217  * Returns NULL if it doesn't exist
218  */
zend_accel_hash_str_find_entry(zend_accel_hash * accel_hash,char * key,uint32_t key_length)219 zend_accel_hash_entry* zend_accel_hash_str_find_entry(zend_accel_hash *accel_hash, char *key, uint32_t key_length)
220 {
221 	return (zend_accel_hash_entry *)zend_accel_hash_find_ex(
222 		accel_hash,
223 		key,
224 		key_length,
225 		zend_inline_hash_func(key, key_length),
226 		0);
227 }
228 
zend_accel_hash_unlink(zend_accel_hash * accel_hash,char * key,uint32_t key_length)229 int zend_accel_hash_unlink(zend_accel_hash *accel_hash, char *key, uint32_t key_length)
230 {
231     zend_ulong hash_value;
232     zend_ulong index;
233     zend_accel_hash_entry *entry, *last_entry=NULL;
234 
235 	hash_value = zend_inline_hash_func(key, key_length);
236 #ifndef ZEND_WIN32
237 	hash_value ^= ZCG(root_hash);
238 #endif
239 	index = hash_value % accel_hash->max_num_entries;
240 
241 	entry = accel_hash->hash_table[index];
242 	while (entry) {
243 		if (entry->hash_value == hash_value
244 			&& entry->key_length == key_length
245 			&& !memcmp(entry->key, key, key_length)) {
246 			if (!entry->indirect) {
247 				accel_hash->num_direct_entries--;
248 			}
249 			if (last_entry) {
250 				last_entry->next = entry->next;
251 			} else {
252 				accel_hash->hash_table[index] = entry->next;
253 			}
254 			return SUCCESS;
255 		}
256 		last_entry = entry;
257 		entry = entry->next;
258 	}
259 	return FAILURE;
260 }
261