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