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