/src/php-src/ext/opcache/zend_accelerator_hash.c

Source
/*
   +----------------------------------------------------------------------+
   | Zend OPcache                                                         |
   +----------------------------------------------------------------------+
   | Copyright (c) The PHP Group                                          |
   +----------------------------------------------------------------------+
   | This source file is subject to version 3.01 of the PHP license,      |
   | that is bundled with this package in the file LICENSE, and is        |
   | available through the world-wide-web at the following url:           |
   | https://www.php.net/license/3_01.txt                                 |
   | If you did not receive a copy of the PHP license and are unable to   |
   | obtain it through the world-wide-web, please send a note to          |
   | license@php.net so we can mail you a copy immediately.               |
   +----------------------------------------------------------------------+
   | Authors: Andi Gutmans <andi@php.net>                                 |
   |          Zeev Suraski <zeev@php.net>                                 |
   |          Stanislav Malyshev <stas@zend.com>                          |
   |          Dmitry Stogov <dmitry@php.net>                              |
   +----------------------------------------------------------------------+
*/

#include "ZendAccelerator.h"
#include "zend_accelerator_hash.h"
#include "zend_hash.h"
#include "zend_shared_alloc.h"

/* Generated on an Octa-ALPHA 300MHz CPU & 2.5GB RAM monster */
static const uint32_t prime_numbers[] =
  {5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963, 16229, 32531, 65407, 130987, 262237, 524521, 1048793 };
static const uint32_t num_prime_numbers = sizeof(prime_numbers) / sizeof(uint32_t);

void zend_accel_hash_clean(zend_accel_hash *accel_hash)
{
  accel_hash->num_entries = 0;
  accel_hash->num_direct_entries = 0;
  memset(accel_hash->hash_table, 0, sizeof(zend_accel_hash_entry *)*accel_hash->max_num_entries);
}

void zend_accel_hash_init(zend_accel_hash *accel_hash, uint32_t hash_size)
{
  uint32_t i;

  for (i=0; i<num_prime_numbers; i++) {
    if (hash_size <= prime_numbers[i]) {
      hash_size = prime_numbers[i];
      break;
    }
  }

  accel_hash->num_entries = 0;
  accel_hash->num_direct_entries = 0;
  accel_hash->max_num_entries = hash_size;

  /* set up hash pointers table */
  accel_hash->hash_table = zend_shared_alloc(sizeof(zend_accel_hash_entry *)*accel_hash->max_num_entries);
  if (!accel_hash->hash_table) {
    zend_accel_error_noreturn(ACCEL_LOG_FATAL, "Insufficient shared memory!");
    return;
  }

  /* set up hash values table */
  accel_hash->hash_entries = zend_shared_alloc(sizeof(zend_accel_hash_entry)*accel_hash->max_num_entries);
  if (!accel_hash->hash_entries) {
    zend_accel_error_noreturn(ACCEL_LOG_FATAL, "Insufficient shared memory!");
    return;
  }
  memset(accel_hash->hash_table, 0, sizeof(zend_accel_hash_entry *)*accel_hash->max_num_entries);
}

/* Returns NULL if hash is full
 * Returns pointer the actual hash entry on success
 * key needs to be already allocated as it is not copied
 */
zend_accel_hash_entry* zend_accel_hash_update(zend_accel_hash *accel_hash, zend_string *key, bool indirect, void *data)
{
  zend_ulong hash_value;
  zend_ulong index;
  zend_accel_hash_entry *entry;
  zend_accel_hash_entry *indirect_bucket = NULL;

  if (indirect) {
    indirect_bucket = (zend_accel_hash_entry*)data;
    while (indirect_bucket->indirect) {
      indirect_bucket = (zend_accel_hash_entry*)indirect_bucket->data;
    }
  }

  hash_value = zend_string_hash_val(key);
#ifndef ZEND_WIN32
  hash_value ^= ZCG(root_hash);
#endif
  index = hash_value % accel_hash->max_num_entries;

  /* try to see if the element already exists in the hash */
  entry = accel_hash->hash_table[index];
  while (entry) {
    if (entry->hash_value == hash_value
     && zend_string_equals(entry->key, key)) {

      if (entry->indirect) {
        if (indirect_bucket) {
          entry->data = indirect_bucket;
        } else {
          ((zend_accel_hash_entry*)entry->data)->data = data;
        }
      } else {
        if (indirect_bucket) {
          accel_hash->num_direct_entries--;
          entry->data = indirect_bucket;
          entry->indirect = 1;
        } else {
          entry->data = data;
        }
      }
      return entry;
    }
    entry = entry->next;
  }

  /* Does not exist, add a new entry */
  if (accel_hash->num_entries == accel_hash->max_num_entries) {
    return NULL;
  }

  entry = &accel_hash->hash_entries[accel_hash->num_entries++];
  if (indirect) {
    entry->data = indirect_bucket;
    entry->indirect = 1;
  } else {
    accel_hash->num_direct_entries++;
    entry->data = data;
    entry->indirect = 0;
  }
  entry->hash_value = hash_value;
  entry->key = key;
  entry->next = accel_hash->hash_table[index];
  accel_hash->hash_table[index] = entry;
  return entry;
}

static zend_always_inline void* zend_accel_hash_find_ex(zend_accel_hash *accel_hash, zend_string *key, int data)
{
  zend_ulong index;
  zend_accel_hash_entry *entry;
  zend_ulong hash_value;

  hash_value = zend_string_hash_val(key);
#ifndef ZEND_WIN32
  hash_value ^= ZCG(root_hash);
#endif
  index = hash_value % accel_hash->max_num_entries;

  entry = accel_hash->hash_table[index];
  while (entry) {
    if (entry->hash_value == hash_value
     && zend_string_equals(entry->key, key)) {
      if (entry->indirect) {
        if (data) {
          return ((zend_accel_hash_entry*)entry->data)->data;
        } else {
          return entry->data;
        }
      } else {
        if (data) {
          return entry->data;
        } else {
          return entry;
        }
      }
    }
    entry = entry->next;
  }
  return NULL;
}

/* Returns the data associated with key on success
 * Returns NULL if data doesn't exist
 */
void* zend_accel_hash_find(zend_accel_hash *accel_hash, zend_string *key)
{
  return zend_accel_hash_find_ex(accel_hash, key, 1);
}

/* Returns the hash entry associated with key on success
 * Returns NULL if it doesn't exist
 */
zend_accel_hash_entry* zend_accel_hash_find_entry(zend_accel_hash *accel_hash, zend_string *key)
{
  return (zend_accel_hash_entry *)zend_accel_hash_find_ex(accel_hash, key, 0);
}

int zend_accel_hash_unlink(zend_accel_hash *accel_hash, zend_string *key)
{
  zend_ulong hash_value;
  zend_ulong index;
  zend_accel_hash_entry *entry, *last_entry=NULL;

  hash_value = zend_string_hash_val(key);
#ifndef ZEND_WIN32
  hash_value ^= ZCG(root_hash);
#endif
  index = hash_value % accel_hash->max_num_entries;

  entry = accel_hash->hash_table[index];
  while (entry) {
    if (entry->hash_value == hash_value
     && zend_string_equals(entry->key, key)) {
      if (!entry->indirect) {
        accel_hash->num_direct_entries--;
      }
      if (last_entry) {
        last_entry->next = entry->next;
      } else {
        accel_hash->hash_table[index] = entry->next;
      }
      return SUCCESS;
    }
    last_entry = entry;
    entry = entry->next;
  }
  return FAILURE;
}

Coverage Report

Created: 2025-09-27 06:26

Line	Count	Source
1		/*
2		+----------------------------------------------------------------------+
3		\| Zend OPcache \|
4		+----------------------------------------------------------------------+
5		\| Copyright (c) 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		\| https://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@php.net> \|
16		\| Zeev Suraski <zeev@php.net> \|
17		\| Stanislav Malyshev <stas@zend.com> \|
18		\| Dmitry Stogov <dmitry@php.net> \|
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 const uint32_t prime_numbers[] =
29		{5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963, 16229, 32531, 65407, 130987, 262237, 524521, 1048793 };
30		static const uint32_t num_prime_numbers = sizeof(prime_numbers) / sizeof(uint32_t);
31
32		void zend_accel_hash_clean(zend_accel_hash *accel_hash)
33	0	{
34	0	accel_hash->num_entries = 0;
35	0	accel_hash->num_direct_entries = 0;
36	0	memset(accel_hash->hash_table, 0, sizeof(zend_accel_hash_entry )accel_hash->max_num_entries);
37	0	}
38
39		void zend_accel_hash_init(zend_accel_hash *accel_hash, uint32_t hash_size)
40	16	{
41	16	uint32_t i;
42
43	192	for (i=0; i<num_prime_numbers; i++) {
44	192	if (hash_size <= prime_numbers[i]) {
45	16	hash_size = prime_numbers[i];
46	16	break;
47	16	}
48	192	}
49
50	16	accel_hash->num_entries = 0;
51	16	accel_hash->num_direct_entries = 0;
52	16	accel_hash->max_num_entries = hash_size;
53
54		/* set up hash pointers table */
55	16	accel_hash->hash_table = zend_shared_alloc(sizeof(zend_accel_hash_entry )accel_hash->max_num_entries);
56	16	if (!accel_hash->hash_table) {
57	0	zend_accel_error_noreturn(ACCEL_LOG_FATAL, "Insufficient shared memory!");
58	0	return;
59	0	}
60
61		/* set up hash values table */
62	16	accel_hash->hash_entries = zend_shared_alloc(sizeof(zend_accel_hash_entry)*accel_hash->max_num_entries);
63	16	if (!accel_hash->hash_entries) {
64	0	zend_accel_error_noreturn(ACCEL_LOG_FATAL, "Insufficient shared memory!");
65	0	return;
66	0	}
67	16	memset(accel_hash->hash_table, 0, sizeof(zend_accel_hash_entry )accel_hash->max_num_entries);
68	16	}
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		*/
74		zend_accel_hash_entry* zend_accel_hash_update(zend_accel_hash accel_hash, zend_string key, bool indirect, void *data)
75	60.4k	{
76	60.4k	zend_ulong hash_value;
77	60.4k	zend_ulong index;
78	60.4k	zend_accel_hash_entry *entry;
79	60.4k	zend_accel_hash_entry *indirect_bucket = NULL;
80
81	60.4k	if (indirect) {
82	0	indirect_bucket = (zend_accel_hash_entry*)data;
83	0	while (indirect_bucket->indirect) {
84	0	indirect_bucket = (zend_accel_hash_entry*)indirect_bucket->data;
85	0	}
86	0	}
87
88	60.4k	hash_value = zend_string_hash_val(key);
89	60.4k	#ifndef ZEND_WIN32
90	60.4k	hash_value ^= ZCG(root_hash);
91	60.4k	#endif
92	60.4k	index = hash_value % accel_hash->max_num_entries;
93
94		/* try to see if the element already exists in the hash */
95	60.4k	entry = accel_hash->hash_table[index];
96	60.4k	while (entry) {
97	60.4k	if (entry->hash_value == hash_value
98	60.4k	&& zend_string_equals(entry->key, key)) {
99
100	60.4k	if (entry->indirect) {
101	0	if (indirect_bucket) {
102	0	entry->data = indirect_bucket;
103	0	} else {
104	0	((zend_accel_hash_entry*)entry->data)->data = data;
105	0	}
106	60.4k	} else {
107	60.4k	if (indirect_bucket) {
108	0	accel_hash->num_direct_entries--;
109	0	entry->data = indirect_bucket;
110	0	entry->indirect = 1;
111	60.4k	} else {
112	60.4k	entry->data = data;
113	60.4k	}
114	60.4k	}
115	60.4k	return entry;
116	60.4k	}
117	0	entry = entry->next;
118	0	}
119
120		/* Does not exist, add a new entry */
121	3	if (accel_hash->num_entries == accel_hash->max_num_entries) {
122	0	return NULL;
123	0	}
124
125	3	entry = &accel_hash->hash_entries[accel_hash->num_entries++];
126	3	if (indirect) {
127	0	entry->data = indirect_bucket;
128	0	entry->indirect = 1;
129	3	} else {
130	3	accel_hash->num_direct_entries++;
131	3	entry->data = data;
132	3	entry->indirect = 0;
133	3	}
134	3	entry->hash_value = hash_value;
135	3	entry->key = key;
136	3	entry->next = accel_hash->hash_table[index];
137	3	accel_hash->hash_table[index] = entry;
138	3	return entry;
139	3	}
140
141		static zend_always_inline void* zend_accel_hash_find_ex(zend_accel_hash accel_hash, zend_string key, int data)
142	378k	{
143	378k	zend_ulong index;
144	378k	zend_accel_hash_entry *entry;
145	378k	zend_ulong hash_value;
146
147	378k	hash_value = zend_string_hash_val(key);
148	378k	#ifndef ZEND_WIN32
149	378k	hash_value ^= ZCG(root_hash);
150	378k	#endif
151	378k	index = hash_value % accel_hash->max_num_entries;
152
153	378k	entry = accel_hash->hash_table[index];
154	378k	while (entry) {
155	316k	if (entry->hash_value == hash_value
156	316k	&& zend_string_equals(entry->key, key)) {
157	316k	if (entry->indirect) {
158	0	if (data) {
159	0	return ((zend_accel_hash_entry*)entry->data)->data;
160	0	} else {
161	0	return entry->data;
162	0	}
163	316k	} else {
164	316k	if (data) {
165	255k	return entry->data;
166	255k	} else {
167	60.4k	return entry;
168	60.4k	}
169	316k	}
170	316k	}
171	0	entry = entry->next;
172	0	}
173	61.8k	return NULL;
174	378k	}
175
176		/* Returns the data associated with key on success
177		* Returns NULL if data doesn't exist
178		*/
179		void* zend_accel_hash_find(zend_accel_hash accel_hash, zend_string key)
180	315k	{
181	315k	return zend_accel_hash_find_ex(accel_hash, key, 1);
182	315k	}
183
184		/* Returns the hash entry associated with key on success
185		* Returns NULL if it doesn't exist
186		*/
187		zend_accel_hash_entry* zend_accel_hash_find_entry(zend_accel_hash accel_hash, zend_string key)
188	62.7k	{
189	62.7k	return (zend_accel_hash_entry *)zend_accel_hash_find_ex(accel_hash, key, 0);
190	62.7k	}
191
192		int zend_accel_hash_unlink(zend_accel_hash accel_hash, zend_string key)
193	0	{
194	0	zend_ulong hash_value;
195	0	zend_ulong index;
196	0	zend_accel_hash_entry entry, last_entry=NULL;
197
198	0	hash_value = zend_string_hash_val(key);
199	0	#ifndef ZEND_WIN32
200	0	hash_value ^= ZCG(root_hash);
201	0	#endif
202	0	index = hash_value % accel_hash->max_num_entries;
203
204	0	entry = accel_hash->hash_table[index];
205	0	while (entry) {
206	0	if (entry->hash_value == hash_value
207	0	&& zend_string_equals(entry->key, key)) {
208	0	if (!entry->indirect) {
209	0	accel_hash->num_direct_entries--;
210	0	}
211	0	if (last_entry) {
212	0	last_entry->next = entry->next;
213	0	} else {
214	0	accel_hash->hash_table[index] = entry->next;
215	0	}
216	0	return SUCCESS;
217	0	}
218	0	last_entry = entry;
219	0	entry = entry->next;
220	0	}
221	0	return FAILURE;
222	0	}