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 #include "my_global.h"
27 #include "my_atomic.h"
28 #include "my_sys.h"
29 #include "hash.h"
30
31 C_MODE_START
32
33 /*
34 wait-free dynamic array, see lf_dynarray.c
35
36 4 levels of 256 elements each mean 4311810304 elements in an array - it
37 should be enough for a while
38 */
39 #define LF_DYNARRAY_LEVEL_LENGTH 256
40 #define LF_DYNARRAY_LEVELS 4
41
42 typedef struct {
43 void * volatile level[LF_DYNARRAY_LEVELS];
44 uint size_of_element;
45 } LF_DYNARRAY;
46
47 typedef int (*lf_dynarray_func)(void *, void *);
48
49 void lf_dynarray_init(LF_DYNARRAY *array, uint element_size);
50 void lf_dynarray_destroy(LF_DYNARRAY *array);
51 void *lf_dynarray_value(LF_DYNARRAY *array, uint idx);
52 void *lf_dynarray_lvalue(LF_DYNARRAY *array, uint idx);
53 int lf_dynarray_iterate(LF_DYNARRAY *array, lf_dynarray_func func, void *arg);
54
55 /*
56 pin manager for memory allocator, lf_alloc-pin.c
57 */
58
59 #define LF_PINBOX_PINS 4
60 #define LF_PURGATORY_SIZE 10
61
62 typedef void lf_pinbox_free_func(void *, void *, void*);
63
64 typedef struct {
65 LF_DYNARRAY pinarray;
66 lf_pinbox_free_func *free_func;
67 void *free_func_arg;
68 uint free_ptr_offset;
69 uint32 volatile pinstack_top_ver; /* this is a versioned pointer */
70 uint32 volatile pins_in_array; /* number of elements in array */
71 } LF_PINBOX;
72
73 typedef struct st_lf_pins {
74 void * volatile pin[LF_PINBOX_PINS];
75 LF_PINBOX *pinbox;
76 void *purgatory;
77 uint32 purgatory_count;
78 uint32 volatile link;
79 /* we want sizeof(LF_PINS) to be 64 to avoid false sharing */
80 #if SIZEOF_INT*2+SIZEOF_CHARP*(LF_PINBOX_PINS+2) != 64
81 char pad[64-sizeof(uint32)*2-sizeof(void*)*(LF_PINBOX_PINS+2)];
82 #endif
83 } LF_PINS;
84
85 /*
86 compile-time assert, to require "no less than N" pins
87 it's enough if it'll fail on at least one compiler, so
88 we'll enable it on GCC only, which supports zero-length arrays.
89 */
90 #if defined(__GNUC__) && defined(MY_LF_EXTRA_DEBUG)
91 #define LF_REQUIRE_PINS(N) \
92 static const char require_pins[LF_PINBOX_PINS-N] \
93 MY_ATTRIBUTE ((unused)); \
94 static const int LF_NUM_PINS_IN_THIS_FILE= N;
95 #else
96 #define LF_REQUIRE_PINS(N)
97 #endif
98
lf_pin(LF_PINS * pins,int pin,void * addr)99 static inline void lf_pin(LF_PINS *pins, int pin, void *addr)
100 {
101 #if defined(__GNUC__) && defined(MY_LF_EXTRA_DEBUG)
102 assert(pin < LF_NUM_PINS_IN_THIS_FILE);
103 #endif
104 my_atomic_storeptr(&pins->pin[pin], addr);
105 }
106
lf_unpin(LF_PINS * pins,int pin)107 static inline void lf_unpin(LF_PINS *pins, int pin)
108 {
109 #if defined(__GNUC__) && defined(MY_LF_EXTRA_DEBUG)
110 assert(pin < LF_NUM_PINS_IN_THIS_FILE);
111 #endif
112 my_atomic_storeptr(&pins->pin[pin], NULL);
113 }
114
115 void lf_pinbox_init(LF_PINBOX *pinbox, uint free_ptr_offset,
116 lf_pinbox_free_func *free_func, void * free_func_arg);
117 void lf_pinbox_destroy(LF_PINBOX *pinbox);
118 LF_PINS *lf_pinbox_get_pins(LF_PINBOX *pinbox);
119 void lf_pinbox_put_pins(LF_PINS *pins);
120 void lf_pinbox_free(LF_PINS *pins, void *addr);
121
122
123 /*
124 memory allocator, lf_alloc-pin.c
125 */
126 typedef void lf_allocator_func(uchar *);
127
128 typedef struct st_lf_allocator {
129 LF_PINBOX pinbox;
130 uchar * volatile top;
131 uint element_size;
132 uint32 volatile mallocs;
133 lf_allocator_func *constructor; /* called, when an object is malloc()'ed */
134 lf_allocator_func *destructor; /* called, when an object is free()'d */
135 } LF_ALLOCATOR;
136
137 #define lf_alloc_init(A, B, C) lf_alloc_init2(A, B, C, NULL, NULL)
138 void lf_alloc_init2(LF_ALLOCATOR *allocator, uint size, uint free_ptr_offset,
139 lf_allocator_func *ctor, lf_allocator_func *dtor);
140 void lf_alloc_destroy(LF_ALLOCATOR *allocator);
141 uint lf_alloc_pool_count(LF_ALLOCATOR *allocator);
142
lf_alloc_direct_free(LF_ALLOCATOR * allocator,void * addr)143 static inline void lf_alloc_direct_free(LF_ALLOCATOR *allocator, void *addr)
144 {
145 if (allocator->destructor)
146 allocator->destructor((uchar *)addr);
147 my_free(addr);
148 }
149
150 void *lf_alloc_new(LF_PINS *pins);
151
152 struct st_lf_hash;
153 typedef uint lf_hash_func(const struct st_lf_hash *, const uchar *, size_t);
154 typedef void lf_hash_init_func(uchar *dst, const uchar* src);
155
156 #define LF_HASH_UNIQUE 1
157
158 /* lf_hash overhead per element (that is, sizeof(LF_SLIST) */
159 extern MYSQL_PLUGIN_IMPORT const int LF_HASH_OVERHEAD;
160
161 typedef struct st_lf_hash {
162 LF_DYNARRAY array; /* hash itself */
163 LF_ALLOCATOR alloc; /* allocator for elements */
164 my_hash_get_key get_key; /* see HASH */
165 CHARSET_INFO *charset; /* see HASH */
166 lf_hash_func *hash_function; /* see HASH */
167 uint key_offset, key_length; /* see HASH */
168 uint element_size; /* size of memcpy'ed area on insert */
169 uint flags; /* LF_HASH_UNIQUE, etc */
170 int32 volatile size; /* size of array */
171 int32 volatile count; /* number of elements in the hash */
172 /**
173 "Initialize" hook - called to finish initialization of object provided by
174 LF_ALLOCATOR (which is pointed by "dst" parameter) and set element key
175 from object passed as parameter to lf_hash_insert (pointed by "src"
176 parameter). Allows to use LF_HASH with objects which are not "trivially
177 copyable".
178 NULL value means that element initialization is carried out by copying
179 first element_size bytes from object which provided as parameter to
180 lf_hash_insert.
181 */
182 lf_hash_init_func *initialize;
183 } LF_HASH;
184
185 #define lf_hash_init(A, B, C, D, E, F, G) \
186 lf_hash_init2(A, B, C, D, E, F, G, NULL, NULL, NULL, NULL)
187 void lf_hash_init2(LF_HASH *hash, uint element_size, uint flags,
188 uint key_offset, uint key_length, my_hash_get_key get_key,
189 CHARSET_INFO *charset, lf_hash_func *hash_function,
190 lf_allocator_func *ctor, lf_allocator_func *dtor,
191 lf_hash_init_func *init);
192 void lf_hash_destroy(LF_HASH *hash);
193 int lf_hash_insert(LF_HASH *hash, LF_PINS *pins, const void *data);
194 void *lf_hash_search(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen);
195 int lf_hash_delete(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen);
196
lf_hash_get_pins(LF_HASH * hash)197 static inline LF_PINS *lf_hash_get_pins(LF_HASH *hash)
198 {
199 return lf_pinbox_get_pins(&hash->alloc.pinbox);
200 }
201
lf_hash_put_pins(LF_PINS * pins)202 static inline void lf_hash_put_pins(LF_PINS *pins)
203 {
204 lf_pinbox_put_pins(pins);
205 }
206
lf_hash_search_unpin(LF_PINS * pins)207 static inline void lf_hash_search_unpin(LF_PINS *pins)
208 {
209 lf_unpin(pins, 2);
210 }
211
212 typedef int lf_hash_match_func(const uchar *el);
213 void *lf_hash_random_match(LF_HASH *hash, LF_PINS *pins,
214 lf_hash_match_func *match, uint rand_val);
215
216 C_MODE_END
217
218 #endif
219
220