1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
/*****************************************************************************
Copyright (c) 2021, 2025, Oracle and/or its affiliates.
This program is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License, version 2.0, as published by the
Free Software Foundation.
This program is designed to work with certain software (including
but not limited to OpenSSL) that is licensed under separate terms,
as designated in a particular file or component or in included license
documentation. The authors of MySQL hereby grant you an additional
permission to link the program and your derivative works with the
separately licensed software that they have either included with
the program or referenced in the documentation.
This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
for more details.
You should have received a copy of the GNU General Public License along with
this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*****************************************************************************/
/** @file include/sync0arr_impl.h
The wait array used in synchronization primitives, implementation details.
*******************************************************/
#include "sync0arr.h"
#include "sync0rw.h"
/*
WAIT ARRAY
==========
The wait array consists of cells each of which has an an event object created
for it. The threads waiting for a mutex, for example, can reserve a cell
in the array and suspend themselves to wait for the event to become signaled.
When using the wait array, remember to make sure that some thread holding
the synchronization object will eventually know that there is a waiter in
the array and signal the object, to prevent infinite wait. Why we chose
to implement a wait array? First, to make mutexes fast, we had to code
our own implementation of them, which only in usually uncommon cases
resorts to using slow operating system primitives. Then we had the choice of
assigning a unique OS event for each mutex, which would be simpler, or
using a global wait array. In some operating systems, the global wait
array solution is more efficient and flexible, because we can do with
a very small number of OS events, say 200. In NT 3.51, allocating events
seems to be a quadratic algorithm, because 10 000 events are created fast,
but 100 000 events takes a couple of minutes to create.
As of 5.0.30 the above mentioned design is changed. Since now OS can handle
millions of wait events efficiently, we no longer have this concept of each
cell of wait array having one event. Instead, now the event that a thread
wants to wait on is embedded in the wait object (mutex or rw_lock). We still
keep the global wait array for the sake of diagnostics and also to avoid
infinite wait The error_monitor thread scans the global wait array to signal
any waiting threads who have missed the signal. */
typedef SyncArrayMutex::MutexType WaitMutex;
typedef BlockSyncArrayMutex::MutexType BlockWaitMutex;
/** The latch types that use the sync array. */
union sync_object_t {
/** RW lock instance */
rw_lock_t *lock = nullptr;
/** Mutex instance */
WaitMutex *mutex;
/** Block mutex instance */
BlockWaitMutex *bpmutex;
};
/** A cell where an individual thread may wait suspended until a resource
is released. The suspending is implemented using an operating system
event semaphore. */
struct sync_cell_t {
sync_object_t latch; /*!< pointer to the object the
thread is waiting for; if NULL
the cell is free for use */
ulint request_type = 0; /*!< lock type requested on the
object */
const char *file = nullptr; /*!< in debug version file where
requested */
ulint line = 0; /*!< in debug version line where
requested */
std::thread::id thread_id{}; /*!< thread id of this waiting
thread */
bool waiting = false; /*!< true if the thread has already
called sync_array_event_wait
on this cell */
int64_t signal_count = 0; /*!< We capture the signal_count
of the latch when we
reset the event. This value is
then passed on to os_event_wait
and we wait only if the event
has not been signalled in the
period between the reset and
wait call. */
/** Time when the thread reserved the wait cell. */
std::chrono::steady_clock::time_point reservation_time{};
/** Odd value means it is currently on-stack in a DFS search for cycles.
Even value means it was completely processed.
It is set to (odd) arr->last_scan when first visited, and then incremented
again when all of its children are processed (and thus it is processed, too).
@see arr->last_scan */
uint64_t last_scan{0};
};
/* NOTE: It is allowed for a thread to wait for an event allocated for
the array without owning the protecting mutex (depending on the case:
OS or database mutex), but all changes (set or reset) to the state of
the event must be made while owning the mutex. */
/** Synchronization array */
struct sync_array_t {
/** Constructor
Creates a synchronization wait array. It is protected by a mutex
which is automatically reserved when the functions operating on it
are called.
@param[in] num_cells Number of cells to create */
sync_array_t(ulint num_cells) UNIV_NOTHROW;
/** Destructor */
~sync_array_t() UNIV_NOTHROW;
ulint n_reserved; /*!< number of currently reserved
cells in the wait array */
ulint n_cells; /*!< number of cells in the
wait array */
sync_cell_t *cells; /*!< pointer to wait array */
SysMutex mutex; /*!< System mutex protecting the
data structure. As this data
structure is used in constructing
the database mutex, to prevent
infinite recursion in implementation,
we fall back to an OS mutex. */
ulint res_count; /*!< count of cell reservations
since creation of the array */
ulint next_free_slot; /*!< the next free cell in the array */
ulint first_free_slot; /*!< the last slot that was freed */
/** It is incremented by one at the beginning of search for deadlock cycles,
and then again after the scan has finished.
If during a scan we visit a cell with cell->last_scan == arr->last_scan it
means it is already on the stack, and thus a cycle was found.
If we visit a cell with cell->last_scan == arr->last_scan+1 it means it was
already fully processed and no deadlock was found "below" it.
If it has some other value, the cell wasn't visited by this scan before.*/
uint64_t last_scan{0};
};
/** Locally stored copy of srv_sync_array_size */
extern ulint sync_array_size;
/** The global array of wait cells for implementation of the database's own
mutexes and read-write locks */
extern sync_array_t **sync_wait_array;
static inline void sync_array_exit(sync_array_t *a) { mutex_exit(&a->mutex); }
static inline void sync_array_enter(sync_array_t *a) { mutex_enter(&a->mutex); }
/** Gets the nth cell in array.
@param[in] arr Sync array to get cell from.
@param[in] n Index of cell to retrieve.
@return cell */
sync_cell_t *sync_array_get_nth_cell(sync_array_t *arr, ulint n);
/** Reports info of a wait array cell into a file.
@param[in] file File where to print.
@param[in] cell Sync array cell to report.
*/
void sync_array_cell_print(FILE *file, const sync_cell_t *cell);
|
