MySQL 9.1.0
Source Code Documentation
lf.h
Go to the documentation of this file.
1/* Copyright (c) 2007, 2024, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is designed to work with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have either included with
13 the program or referenced in the documentation.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
23
24#ifndef _lf_h
25#define _lf_h
26
27/**
28 @file include/lf.h
29*/
30
31#include "my_config.h"
32
33#include <stddef.h>
34#include <sys/types.h>
35
36#include <atomic>
37
38#include "my_inttypes.h"
39#include "my_macros.h"
42#include "sql_string.h"
43
44struct CHARSET_INFO;
45
46/*
47 wait-free dynamic array, see lf_dynarray.c
48
49 4 levels of 256 elements each mean 4311810304 elements in an array - it
50 should be enough for a while
51*/
52#define LF_DYNARRAY_LEVEL_LENGTH 256
53#define LF_DYNARRAY_LEVELS 4
54
56 std::atomic<void *> level[LF_DYNARRAY_LEVELS];
58};
59
60typedef int (*lf_dynarray_func)(void *, void *);
61
62void lf_dynarray_init(LF_DYNARRAY *array, uint element_size);
64void *lf_dynarray_value(LF_DYNARRAY *array, uint idx);
65void *lf_dynarray_lvalue(LF_DYNARRAY *array, uint idx);
66int lf_dynarray_iterate(LF_DYNARRAY *array, lf_dynarray_func func, void *arg);
67
68/*
69 pin manager for memory allocator, lf_alloc-pin.c
70*/
71
72#define LF_PINBOX_PINS 4
73#define LF_PURGATORY_SIZE 10
74
75typedef void lf_pinbox_free_func(void *, void *, void *);
76
77struct LF_PINBOX {
82 std::atomic<uint32> pinstack_top_ver; /* this is a versioned pointer */
83 std::atomic<uint32> pins_in_array; /* number of elements in array */
84};
85
86struct LF_PINS {
87 std::atomic<void *> pin[LF_PINBOX_PINS];
89 void *purgatory;
91 std::atomic<uint32> link;
92 /* we want sizeof(LF_PINS) to be 64 to avoid false sharing */
93#if SIZEOF_INT * 2 + SIZEOF_CHARP * (LF_PINBOX_PINS + 2) != 64
94 char pad[64 - sizeof(uint32) * 2 - sizeof(void *) * (LF_PINBOX_PINS + 2)];
95#endif
96};
97
98/*
99 compile-time assert, to require "no less than N" pins
100 it's enough if it'll fail on at least one compiler, so
101 we'll enable it on GCC only, which supports zero-length arrays.
102*/
103#if defined(__GNUC__) && defined(MY_LF_EXTRA_DEBUG)
104#define LF_REQUIRE_PINS(N) \
105 static const char require_pins[LF_PINBOX_PINS - N] [[maybe_unused]]; \
106 static const int LF_NUM_PINS_IN_THIS_FILE = N;
107#else
108#define LF_REQUIRE_PINS(N)
109#endif
110
111static inline void lf_pin(LF_PINS *pins, int pin, void *addr) {
112#if defined(__GNUC__) && defined(MY_LF_EXTRA_DEBUG)
113 assert(pin < LF_NUM_PINS_IN_THIS_FILE);
114#endif
115 pins->pin[pin].store(addr);
116}
117
118static inline void lf_unpin(LF_PINS *pins, int pin) {
119#if defined(__GNUC__) && defined(MY_LF_EXTRA_DEBUG)
120 assert(pin < LF_NUM_PINS_IN_THIS_FILE);
121#endif
122 pins->pin[pin].store(nullptr);
123}
124
125void lf_pinbox_init(LF_PINBOX *pinbox, uint free_ptr_offset,
126 lf_pinbox_free_func *free_func, void *free_func_arg);
127void lf_pinbox_destroy(LF_PINBOX *pinbox);
129void lf_pinbox_put_pins(LF_PINS *pins);
130void lf_pinbox_free(LF_PINS *pins, void *addr);
131
132/*
133 memory allocator, lf_alloc-pin.c
134*/
135typedef void lf_allocator_func(uchar *);
136
139 std::atomic<uchar *> top;
141 std::atomic<uint32> mallocs;
142 lf_allocator_func *constructor; /* called, when an object is malloc()'ed */
143 lf_allocator_func *destructor; /* called, when an object is free()'d */
144};
145
146#define lf_alloc_init(A, B, C) lf_alloc_init2(A, B, C, NULL, NULL)
147void lf_alloc_init2(LF_ALLOCATOR *allocator, uint size, uint free_ptr_offset,
149void lf_alloc_destroy(LF_ALLOCATOR *allocator);
150uint lf_alloc_pool_count(LF_ALLOCATOR *allocator);
151
152static inline void lf_alloc_direct_free(LF_ALLOCATOR *allocator, void *addr) {
153 if (allocator->destructor) {
154 allocator->destructor((uchar *)addr);
155 }
156 my_free(addr);
157}
158
159void *lf_alloc_new(LF_PINS *pins);
160
161struct LF_HASH;
162
163typedef uint lf_hash_func(const LF_HASH *, const uchar *, size_t);
164typedef int lf_cmp_func(const uchar *key1, size_t key1_length,
165 const uchar *key2, size_t key2_length);
166typedef void lf_hash_init_func(uchar *dst, const uchar *src);
167
168#define LF_HASH_UNIQUE 1
169#define MY_LF_ERRPTR ((void *)(intptr)1)
170
171/* lf_hash overhead per element (that is, sizeof(LF_SLIST) */
173
174/**
175 Callback for extracting key and key length from user data in a LF_HASH.
176
177 @param arg Pointer to user data.
178 @param[out] length Store key length here.
179 @return Pointer to key to be hashed.
180
181 @note Was my_hash_get_key, with lots of C-style casting when calling
182 my_hash_init. Renamed to force build error (since signature changed)
183 in case someone keeps following that coding style.
184 */
185typedef const uchar *(*hash_get_key_function)(const uchar *arg, size_t *length);
186
187struct LF_HASH {
188 LF_DYNARRAY array; /* hash itself */
189 LF_ALLOCATOR alloc; /* allocator for elements */
191 CHARSET_INFO *charset; /* see HASH */
193 lf_cmp_func *cmp_function; /* Compare two keys. */
194 uint key_offset, key_length; /* see HASH */
195 uint element_size; /* size of memcpy'ed area on insert */
196 uint flags; /* LF_HASH_UNIQUE, etc */
197 std::atomic<int32> size; /* size of array */
198 std::atomic<int32> count; /* number of elements in the hash */
199 /**
200 "Initialize" hook - called to finish initialization of object provided by
201 LF_ALLOCATOR (which is pointed by "dst" parameter) and set element key
202 from object passed as parameter to lf_hash_insert (pointed by "src"
203 parameter). Allows to use LF_HASH with objects which are not "trivially
204 copyable".
205 NULL value means that element initialization is carried out by copying
206 first element_size bytes from object which provided as parameter to
207 lf_hash_insert.
208 */
210};
211
212#define lf_hash_init(A, B, C, D, E, F, G) \
213 lf_hash_init2(A, B, C, D, E, F, G, NULL, NULL, NULL, NULL)
214
215void lf_hash_init2(LF_HASH *hash, uint element_size, uint flags,
216 uint key_offset, uint key_length,
218 lf_hash_func *hash_function, lf_allocator_func *ctor,
220
221void lf_hash_init3(LF_HASH *hash, uint element_size, uint flags,
222 hash_get_key_function get_key, lf_hash_func *hash_function,
223 lf_cmp_func *cmp_function, lf_allocator_func *ctor,
225
226void lf_hash_destroy(LF_HASH *hash);
227int lf_hash_insert(LF_HASH *hash, LF_PINS *pins, const void *data);
228void *lf_hash_search(LF_HASH *hash, LF_PINS *pins, const void *key,
229 uint keylen);
230int lf_hash_delete(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen);
231
232static inline LF_PINS *lf_hash_get_pins(LF_HASH *hash) {
233 return lf_pinbox_get_pins(&hash->alloc.pinbox);
234}
235
236static inline void lf_hash_put_pins(LF_PINS *pins) { lf_pinbox_put_pins(pins); }
237
238static inline void lf_hash_search_unpin(LF_PINS *pins) { lf_unpin(pins, 2); }
239
240typedef int lf_hash_match_func(const uchar *el, void *arg);
241void *lf_hash_random_match(LF_HASH *hash, LF_PINS *pins,
242 lf_hash_match_func *match, uint rand_val,
243 void *match_arg);
244
245#endif
static mysql_service_status_t init()
Component initialization.
Definition: audit_api_message_emit.cc:571
static int flags[50]
Definition: hp_test1.cc:40
static uint16 key1[1001]
Definition: hp_test2.cc:50
void lf_hash_init_func(uchar *dst, const uchar *src)
Definition: lf.h:166
void lf_allocator_func(uchar *)
Definition: lf.h:135
uint lf_hash_func(const LF_HASH *, const uchar *, size_t)
Definition: lf.h:163
static void lf_unpin(LF_PINS *pins, int pin)
Definition: lf.h:118
static void lf_alloc_direct_free(LF_ALLOCATOR *allocator, void *addr)
Definition: lf.h:152
static void lf_pin(LF_PINS *pins, int pin, void *addr)
Definition: lf.h:111
void lf_alloc_destroy(LF_ALLOCATOR *allocator)
Definition: lf_alloc-pin.cc:419
int lf_dynarray_iterate(LF_DYNARRAY *array, lf_dynarray_func func, void *arg)
Definition: lf_dynarray.cc:227
#define LF_PINBOX_PINS
Definition: lf.h:72
void lf_pinbox_put_pins(LF_PINS *pins)
Definition: lf_alloc-pin.cc:219
void lf_pinbox_free_func(void *, void *, void *)
Definition: lf.h:75
void lf_pinbox_destroy(LF_PINBOX *pinbox)
Definition: lf_alloc-pin.cc:152
LF_PINS * lf_pinbox_get_pins(LF_PINBOX *pinbox)
Definition: lf_alloc-pin.cc:166
void * lf_hash_search(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen)
Find hash element corresponding to the key.
Definition: lf_hash.cc:723
const uchar *(* hash_get_key_function)(const uchar *arg, size_t *length)
Callback for extracting key and key length from user data in a LF_HASH.
Definition: lf.h:185
int lf_hash_delete(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen)
Definition: lf_hash.cc:670
void lf_pinbox_free(LF_PINS *pins, void *addr)
Definition: lf_alloc-pin.cc:273
static void lf_hash_search_unpin(LF_PINS *pins)
Definition: lf.h:238
void lf_hash_init3(LF_HASH *hash, uint element_size, uint flags, hash_get_key_function get_key, lf_hash_func *hash_function, lf_cmp_func *cmp_function, lf_allocator_func *ctor, lf_allocator_func *dtor, lf_hash_init_func *init)
Definition: lf_hash.cc:573
void lf_alloc_init2(LF_ALLOCATOR *allocator, uint size, uint free_ptr_offset, lf_allocator_func *ctor, lf_allocator_func *dtor)
Initialize lock-free allocator.
Definition: lf_alloc-pin.cc:397
void lf_hash_destroy(LF_HASH *hash)
Definition: lf_hash.cc:581
int lf_hash_insert(LF_HASH *hash, LF_PINS *pins, const void *data)
Definition: lf_hash.cc:616
static LF_PINS * lf_hash_get_pins(LF_HASH *hash)
Definition: lf.h:232
void lf_dynarray_destroy(LF_DYNARRAY *array)
Definition: lf_dynarray.cc:86
int lf_cmp_func(const uchar *key1, size_t key1_length, const uchar *key2, size_t key2_length)
Definition: lf.h:164
void lf_hash_init2(LF_HASH *hash, uint element_size, uint flags, uint key_offset, uint key_length, hash_get_key_function get_key, CHARSET_INFO *charset, lf_hash_func *hash_function, lf_allocator_func *ctor, lf_allocator_func *dtor, lf_hash_init_func *init)
Definition: lf_hash.cc:564
void * lf_dynarray_value(LF_DYNARRAY *array, uint idx)
Definition: lf_dynarray.cc:175
#define LF_DYNARRAY_LEVELS
Definition: lf.h:53
static void lf_hash_put_pins(LF_PINS *pins)
Definition: lf.h:236
int(* lf_dynarray_func)(void *, void *)
Definition: lf.h:60
void * lf_alloc_new(LF_PINS *pins)
Definition: lf_alloc-pin.cc:440
uint lf_alloc_pool_count(LF_ALLOCATOR *allocator)
Definition: lf_alloc-pin.cc:476
void lf_dynarray_init(LF_DYNARRAY *array, uint element_size)
Definition: lf_dynarray.cc:65
void lf_pinbox_init(LF_PINBOX *pinbox, uint free_ptr_offset, lf_pinbox_free_func *free_func, void *free_func_arg)
Definition: lf_alloc-pin.cc:140
MYSQL_PLUGIN_IMPORT const int LF_HASH_OVERHEAD
Definition: lf_hash.cc:72
void * lf_dynarray_lvalue(LF_DYNARRAY *array, uint idx)
Definition: lf_dynarray.cc:115
void * lf_hash_random_match(LF_HASH *hash, LF_PINS *pins, lf_hash_match_func *match, uint rand_val, void *match_arg)
Find random hash element which satisfies condition specified by match function.
Definition: lf_hash.cc:775
int lf_hash_match_func(const uchar *el, void *arg)
Definition: lf.h:240
Some integer typedefs for easier portability.
unsigned char uchar
Definition: my_inttypes.h:52
uint32_t uint32
Definition: my_inttypes.h:67
Some common macros.
void my_free(void *ptr)
Frees the memory pointed by the ptr.
Definition: my_memory.cc:81
#define MYSQL_PLUGIN_IMPORT
Definition: my_sharedlib.h:71
Instrumentation helpers for statements.
const std::string charset("charset")
bool length(const dd::Spatial_reference_system *srs, const Geometry *g1, double *length, bool *null) noexcept
Computes the length of linestrings and multilinestrings.
Definition: length.cc:76
size_t size(const char *const c)
Definition: base64.h:46
required string key
Definition: replication_asynchronous_connection_failover.proto:60
Our own string classes, used pervasively throughout the executor.
Definition: m_ctype.h:421
Definition: lf.h:137
lf_allocator_func * destructor
Definition: lf.h:143
uint element_size
Definition: lf.h:140
std::atomic< uint32 > mallocs
Definition: lf.h:141
lf_allocator_func * constructor
Definition: lf.h:142
LF_PINBOX pinbox
Definition: lf.h:138
std::atomic< uchar * > top
Definition: lf.h:139
Definition: lf.h:55
uint size_of_element
Definition: lf.h:57
std::atomic< void * > level[LF_DYNARRAY_LEVELS]
Definition: lf.h:56
Definition: lf.h:187
CHARSET_INFO * charset
Definition: lf.h:191
uint element_size
Definition: lf.h:195
std::atomic< int32 > size
Definition: lf.h:197
hash_get_key_function get_key
Definition: lf.h:190
lf_hash_init_func * initialize
"Initialize" hook - called to finish initialization of object provided by LF_ALLOCATOR (which is poin...
Definition: lf.h:209
lf_hash_func * hash_function
Definition: lf.h:192
uint key_length
Definition: lf.h:194
LF_DYNARRAY array
Definition: lf.h:188
uint key_offset
Definition: lf.h:194
uint flags
Definition: lf.h:196
std::atomic< int32 > count
Definition: lf.h:198
LF_ALLOCATOR alloc
Definition: lf.h:189
lf_cmp_func * cmp_function
Definition: lf.h:193
Definition: lf.h:77
lf_pinbox_free_func * free_func
Definition: lf.h:79
LF_DYNARRAY pinarray
Definition: lf.h:78
void * free_func_arg
Definition: lf.h:80
uint free_ptr_offset
Definition: lf.h:81
std::atomic< uint32 > pins_in_array
Definition: lf.h:83
std::atomic< uint32 > pinstack_top_ver
Definition: lf.h:82
Definition: lf.h:86
char pad[64 - sizeof(uint32) *2 - sizeof(void *) *(LF_PINBOX_PINS+2)]
Definition: lf.h:94
uint32 purgatory_count
Definition: lf.h:90
LF_PINBOX * pinbox
Definition: lf.h:88
std::atomic< void * > pin[LF_PINBOX_PINS]
Definition: lf.h:87
void * purgatory
Definition: lf.h:89
std::atomic< uint32 > link
Definition: lf.h:91