MySQL  8.0.27
Source Code Documentation
lf.h
Go to the documentation of this file.
1 /* Copyright (c) 2007, 2021, 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 
52 struct LF_DYNARRAY {
53  std::atomic<void *> level[LF_DYNARRAY_LEVELS];
55 };
56 
57 typedef int (*lf_dynarray_func)(void *, void *);
58 
59 void lf_dynarray_init(LF_DYNARRAY *array, uint element_size);
60 void lf_dynarray_destroy(LF_DYNARRAY *array);
61 void *lf_dynarray_value(LF_DYNARRAY *array, uint idx);
62 void *lf_dynarray_lvalue(LF_DYNARRAY *array, uint idx);
63 int 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 
72 typedef void lf_pinbox_free_func(void *, void *, void *);
73 
74 struct 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 
83 struct 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 
108 static 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 
115 static 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 
122 void lf_pinbox_init(LF_PINBOX *pinbox, uint free_ptr_offset,
123  lf_pinbox_free_func *free_func, void *free_func_arg);
124 void lf_pinbox_destroy(LF_PINBOX *pinbox);
126 void lf_pinbox_put_pins(LF_PINS *pins);
127 void lf_pinbox_free(LF_PINS *pins, void *addr);
128 
129 /*
130  memory allocator, lf_alloc-pin.c
131 */
132 typedef void lf_allocator_func(uchar *);
133 
134 struct LF_ALLOCATOR {
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)
144 void lf_alloc_init2(LF_ALLOCATOR *allocator, uint size, uint free_ptr_offset,
145  lf_allocator_func *ctor, lf_allocator_func *dtor);
146 void lf_alloc_destroy(LF_ALLOCATOR *allocator);
148 
149 static 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 
156 void *lf_alloc_new(LF_PINS *pins);
157 
158 struct LF_HASH;
159 
160 typedef uint lf_hash_func(const LF_HASH *, const uchar *, size_t);
161 typedef void lf_hash_init_func(uchar *dst, const uchar *src);
162 
163 #define LF_HASH_UNIQUE 1
164 #define MY_LF_ERRPTR ((void *)(intptr)1)
165 
166 /* lf_hash overhead per element (that is, sizeof(LF_SLIST) */
167 extern MYSQL_PLUGIN_IMPORT const int LF_HASH_OVERHEAD;
168 
169 /**
170  Callback for extracting key and key length from user data in a LF_HASH.
171  @param arg Pointer to user data.
172  @param[out] length Store key length here.
173  @return Pointer to key to be hashed.
174 
175  @note Was my_hash_get_key, with lots of C-style casting when calling
176  my_hash_init. Renamed to force build error (since signature changed)
177  in case someone keeps following that coding style.
178  */
179 typedef const uchar *(*hash_get_key_function)(const uchar *arg, size_t *length);
180 
181 struct LF_HASH {
182  LF_DYNARRAY array; /* hash itself */
183  LF_ALLOCATOR alloc; /* allocator for elements */
185  CHARSET_INFO *charset; /* see HASH */
186  lf_hash_func *hash_function; /* see HASH */
187  uint key_offset, key_length; /* see HASH */
188  uint element_size; /* size of memcpy'ed area on insert */
189  uint flags; /* LF_HASH_UNIQUE, etc */
190  std::atomic<int32> size; /* size of array */
191  std::atomic<int32> count; /* number of elements in the hash */
192  /**
193  "Initialize" hook - called to finish initialization of object provided by
194  LF_ALLOCATOR (which is pointed by "dst" parameter) and set element key
195  from object passed as parameter to lf_hash_insert (pointed by "src"
196  parameter). Allows to use LF_HASH with objects which are not "trivially
197  copyable".
198  NULL value means that element initialization is carried out by copying
199  first element_size bytes from object which provided as parameter to
200  lf_hash_insert.
201  */
203 };
204 
205 #define lf_hash_init(A, B, C, D, E, F, G) \
206  lf_hash_init2(A, B, C, D, E, F, G, NULL, NULL, NULL, NULL)
207 void lf_hash_init2(LF_HASH *hash, uint element_size, uint flags,
208  uint key_offset, uint key_length,
210  lf_hash_func *hash_function, lf_allocator_func *ctor,
212 void lf_hash_destroy(LF_HASH *hash);
213 int lf_hash_insert(LF_HASH *hash, LF_PINS *pins, const void *data);
214 void *lf_hash_search(LF_HASH *hash, LF_PINS *pins, const void *key,
215  uint keylen);
216 int lf_hash_delete(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen);
217 
218 static inline LF_PINS *lf_hash_get_pins(LF_HASH *hash) {
219  return lf_pinbox_get_pins(&hash->alloc.pinbox);
220 }
221 
222 static inline void lf_hash_put_pins(LF_PINS *pins) { lf_pinbox_put_pins(pins); }
223 
224 static inline void lf_hash_search_unpin(LF_PINS *pins) { lf_unpin(pins, 2); }
225 
226 typedef int lf_hash_match_func(const uchar *el);
227 void *lf_hash_random_match(LF_HASH *hash, LF_PINS *pins,
228  lf_hash_match_func *match, uint rand_val);
229 
230 #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
void lf_hash_init_func(uchar *dst, const uchar *src)
Definition: lf.h:161
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
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:179
void lf_pinbox_destroy(LF_PINBOX *pinbox)
Definition: lf_alloc-pin.cc:151
int lf_hash_delete(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen)
Definition: lf_hash.cc:548
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:224
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:459
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:651
int lf_hash_insert(LF_HASH *hash, LF_PINS *pins, const void *data)
Definition: lf_hash.cc:494
static LF_PINS * lf_hash_get_pins(LF_HASH *hash)
Definition: lf.h:218
void lf_dynarray_destroy(LF_DYNARRAY *array)
Definition: lf_dynarray.cc:85
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:438
#define LF_DYNARRAY_LEVELS
Definition: lf.h:50
LF_PINS * lf_pinbox_get_pins(LF_PINBOX *pinbox)
Definition: lf_alloc-pin.cc:165
static void lf_hash_put_pins(LF_PINS *pins)
Definition: lf.h:222
int(* lf_dynarray_func)(void *, void *)
Definition: lf.h:57
void * lf_dynarray_lvalue(LF_DYNARRAY *array, uint idx)
Definition: lf_dynarray.cc:114
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_dynarray_value(LF_DYNARRAY *array, uint idx)
Definition: lf_dynarray.cc:174
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:226
void * lf_alloc_new(LF_PINS *pins)
Definition: lf_alloc-pin.cc:439
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:601
static uint key_length
Definition: mi_test1.cc:42
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:354
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:181
CHARSET_INFO * charset
Definition: lf.h:185
uint element_size
Definition: lf.h:188
std::atomic< int32 > size
Definition: lf.h:190
hash_get_key_function get_key
Definition: lf.h:184
lf_hash_init_func * initialize
"Initialize" hook - called to finish initialization of object provided by LF_ALLOCATOR (which is poin...
Definition: lf.h:202
lf_hash_func * hash_function
Definition: lf.h:186
uint key_length
Definition: lf.h:187
LF_DYNARRAY array
Definition: lf.h:182
uint key_offset
Definition: lf.h:187
uint flags
Definition: lf.h:189
std::atomic< int32 > count
Definition: lf.h:191
LF_ALLOCATOR alloc
Definition: lf.h:183
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