1 /*
2    +----------------------------------------------------------------------+
3    | Zend OPcache                                                         |
4    +----------------------------------------------------------------------+
5    | Copyright (c) 1998-2015 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 
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 	index = hash_value % accel_hash->max_num_entries;
90 
91 	/* try to see if the element already exists in the hash */
92 	entry = accel_hash->hash_table[index];
93 	while (entry) {
94 		if (entry->hash_value == hash_value
95 			&& entry->key_length == key_length
96 			&& !memcmp(entry->key, key, key_length)) {
97 
98 			if (entry->indirect) {
99 				if (indirect_bucket) {
100 					entry->data = indirect_bucket;
101 				} else {
102 					((zend_accel_hash_entry*)entry->data)->data = data;
103 				}
104 			} else {
105 				if (indirect_bucket) {
106 					accel_hash->num_direct_entries--;
107 					entry->data = indirect_bucket;
108 					entry->indirect = 1;
109 				} else {
110 					entry->data = data;
111 				}
112 			}
113 			return entry;
114 		}
115 		entry = entry->next;
116 	}
117 
118 	/* Does not exist, add a new entry */
119 	if (accel_hash->num_entries == accel_hash->max_num_entries) {
120 		return NULL;
121 	}
122 
123 	entry = &accel_hash->hash_entries[accel_hash->num_entries++];
124 	if (indirect) {
125 		entry->data = indirect_bucket;
126 		entry->indirect = 1;
127 	} else {
128 		accel_hash->num_direct_entries++;
129 		entry->data = data;
130 		entry->indirect = 0;
131 	}
132 	entry->hash_value = hash_value;
133 	entry->key = key;
134 	entry->key_length = key_length;
135 	entry->next = accel_hash->hash_table[index];
136 	accel_hash->hash_table[index] = entry;
137 	return entry;
138 }
139 
140 /* Returns the data associated with key on success
141  * Returns NULL if data doesn't exist
142  */
zend_accel_hash_find(zend_accel_hash * accel_hash,char * key,zend_uint key_length)143 void* zend_accel_hash_find(zend_accel_hash *accel_hash, char *key, zend_uint key_length)
144 {
145 	zend_ulong hash_value;
146 	zend_ulong index;
147 	zend_accel_hash_entry *entry;
148 
149 	hash_value = zend_inline_hash_func(key, key_length);
150 	index = hash_value % accel_hash->max_num_entries;
151 
152 	entry = accel_hash->hash_table[index];
153 	while (entry) {
154 		if (entry->hash_value == hash_value
155 			&& entry->key_length == key_length
156 			&& !memcmp(entry->key, key, key_length)) {
157 			if (entry->indirect) {
158 				return ((zend_accel_hash_entry *) entry->data)->data;
159 			} else {
160 				return entry->data;
161 			}
162 		}
163 		entry = entry->next;
164 	}
165 	return NULL;
166 }
167 
168 /* Returns the hash entry associated with key on success
169  * Returns NULL if it doesn't exist
170  */
zend_accel_hash_find_entry(zend_accel_hash * accel_hash,char * key,zend_uint key_length)171 zend_accel_hash_entry* zend_accel_hash_find_entry(zend_accel_hash *accel_hash, char *key, zend_uint key_length)
172 {
173 	zend_ulong hash_value;
174 	zend_ulong index;
175 	zend_accel_hash_entry *entry;
176 
177 	hash_value = zend_inline_hash_func(key, key_length);
178 	index = hash_value % accel_hash->max_num_entries;
179 
180 	entry = accel_hash->hash_table[index];
181 	while (entry) {
182 		if (entry->hash_value == hash_value
183 			&& entry->key_length == key_length
184 			&& !memcmp(entry->key, key, key_length)) {
185 			if (entry->indirect) {
186 				return (zend_accel_hash_entry *) entry->data;
187 			} else {
188 				return entry;
189 			}
190 		}
191 		entry = entry->next;
192 	}
193 	return NULL;
194 }
195 
zend_accel_hash_unlink(zend_accel_hash * accel_hash,char * key,zend_uint key_length)196 int zend_accel_hash_unlink(zend_accel_hash *accel_hash, char *key, zend_uint key_length)
197 {
198 	zend_ulong hash_value;
199     zend_ulong index;
200     zend_accel_hash_entry *entry, *last_entry=NULL;
201 
202 	hash_value = zend_inline_hash_func(key, key_length);
203 	index = hash_value % accel_hash->max_num_entries;
204 
205 	entry = accel_hash->hash_table[index];
206 	while (entry) {
207 		if (entry->hash_value == hash_value
208 			&& entry->key_length == key_length
209 			&& !memcmp(entry->key, key, key_length)) {
210 			if (!entry->indirect) {
211 				accel_hash->num_direct_entries--;
212 			}
213 			if (last_entry) {
214 				last_entry->next = entry->next;
215 			} else {
216 				accel_hash->hash_table[index] = entry->next;
217 			}
218 			return SUCCESS;
219 		}
220 		last_entry = entry;
221 		entry = entry->next;
222 	}
223 	return FAILURE;
224 }
225