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