sync0sync.c 43.9 KB
Newer Older
1 2
/*****************************************************************************

3
Copyright (c) 1995, 2011, Innobase Oy. All Rights Reserved.
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Copyright (c) 2008, Google Inc.

Portions of this file contain modifications contributed and copyrighted by
Google, Inc. Those modifications are gratefully acknowledged and are described
briefly in the InnoDB documentation. The contributions by Google are
incorporated with their permission, and subject to the conditions contained in
the file COPYING.Google.

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free Software
Foundation; version 2 of the License.

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 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., 59 Temple
Place, Suite 330, Boston, MA 02111-1307 USA

*****************************************************************************/

26 27
/**************************************************//**
@file sync/sync0sync.c
osku's avatar
osku committed
28 29 30 31 32 33 34 35 36 37 38 39 40 41
Mutex, the basic synchronization primitive

Created 9/5/1995 Heikki Tuuri
*******************************************************/

#include "sync0sync.h"
#ifdef UNIV_NONINL
#include "sync0sync.ic"
#endif

#include "sync0rw.h"
#include "buf0buf.h"
#include "srv0srv.h"
#include "buf0types.h"
42
#include "os0sync.h" /* for HAVE_ATOMIC_BUILTINS */
43 44 45
#ifdef UNIV_SYNC_DEBUG
# include "srv0start.h" /* srv_is_being_started */
#endif /* UNIV_SYNC_DEBUG */
osku's avatar
osku committed
46 47 48 49 50 51 52 53 54 55 56 57

/*
	REASONS FOR IMPLEMENTING THE SPIN LOCK MUTEX
	============================================

Semaphore operations in operating systems are slow: Solaris on a 1993 Sparc
takes 3 microseconds (us) for a lock-unlock pair and Windows NT on a 1995
Pentium takes 20 microseconds for a lock-unlock pair. Therefore, we have to
implement our own efficient spin lock mutex. Future operating systems may
provide efficient spin locks, but we cannot count on that.

Another reason for implementing a spin lock is that on multiprocessor systems
58
it can be more efficient for a processor to run a loop waiting for the
osku's avatar
osku committed
59 60 61 62 63 64 65
semaphore to be released than to switch to a different thread. A thread switch
takes 25 us on both platforms mentioned above. See Gray and Reuter's book
Transaction processing for background.

How long should the spin loop last before suspending the thread? On a
uniprocessor, spinning does not help at all, because if the thread owning the
mutex is not executing, it cannot be released. Spinning actually wastes
66
resources.
osku's avatar
osku committed
67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

On a multiprocessor, we do not know if the thread owning the mutex is
executing or not. Thus it would make sense to spin as long as the operation
guarded by the mutex would typically last assuming that the thread is
executing. If the mutex is not released by that time, we may assume that the
thread owning the mutex is not executing and suspend the waiting thread.

A typical operation (where no i/o involved) guarded by a mutex or a read-write
lock may last 1 - 20 us on the current Pentium platform. The longest
operations are the binary searches on an index node.

We conclude that the best choice is to set the spin time at 20 us. Then the
system should work well on a multiprocessor. On a uniprocessor we have to
make sure that thread swithches due to mutex collisions are not frequent,
i.e., they do not happen every 100 us or so, because that wastes too much
resources. If the thread switches are not frequent, the 20 us wasted in spin
83
loop is not too much.
osku's avatar
osku committed
84 85 86 87

Empirical studies on the effect of spin time should be done for different
platforms.

88

osku's avatar
osku committed
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
	IMPLEMENTATION OF THE MUTEX
	===========================

For background, see Curt Schimmel's book on Unix implementation on modern
architectures. The key points in the implementation are atomicity and
serialization of memory accesses. The test-and-set instruction (XCHG in
Pentium) must be atomic. As new processors may have weak memory models, also
serialization of memory references may be necessary. The successor of Pentium,
P6, has at least one mode where the memory model is weak. As far as we know,
in Pentium all memory accesses are serialized in the program order and we do
not have to worry about the memory model. On other processors there are
special machine instructions called a fence, memory barrier, or storage
barrier (STBAR in Sparc), which can be used to serialize the memory accesses
to happen in program order relative to the fence instruction.

Leslie Lamport has devised a "bakery algorithm" to implement a mutex without
the atomic test-and-set, but his algorithm should be modified for weak memory
models. We do not use Lamport's algorithm, because we guess it is slower than
the atomic test-and-set.

Our mutex implementation works as follows: After that we perform the atomic
test-and-set instruction on the memory word. If the test returns zero, we
know we got the lock first. If the test returns not zero, some other thread
was quicker and got the lock: then we spin in a loop reading the memory word,
waiting it to become zero. It is wise to just read the word in the loop, not
perform numerous test-and-set instructions, because they generate memory
traffic between the cache and the main memory. The read loop can just access
the cache, saving bus bandwidth.

If we cannot acquire the mutex lock in the specified time, we reserve a cell
in the wait array, set the waiters byte in the mutex to 1. To avoid a race
condition, after setting the waiters byte and before suspending the waiting
thread, we still have to check that the mutex is reserved, because it may
have happened that the thread which was holding the mutex has just released
it and did not see the waiters byte set to 1, a case which would lead the
other thread to an infinite wait.

126 127 128 129
LEMMA 1: After a thread resets the event of a mutex (or rw_lock), some
=======
thread will eventually call os_event_set() on that particular event.
Thus no infinite wait is possible in this case.
osku's avatar
osku committed
130 131 132 133 134 135

Proof:	After making the reservation the thread sets the waiters field in the
mutex to 1. Then it checks that the mutex is still reserved by some thread,
or it reserves the mutex for itself. In any case, some thread (which may be
also some earlier thread, not necessarily the one currently holding the mutex)
will set the waiters field to 0 in mutex_exit, and then call
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
os_event_set() with the mutex as an argument.
Q.E.D.

LEMMA 2: If an os_event_set() call is made after some thread has called
=======
the os_event_reset() and before it starts wait on that event, the call
will not be lost to the second thread. This is true even if there is an
intervening call to os_event_reset() by another thread.
Thus no infinite wait is possible in this case.

Proof (non-windows platforms): os_event_reset() returns a monotonically
increasing value of signal_count. This value is increased at every
call of os_event_set() If thread A has called os_event_reset() followed
by thread B calling os_event_set() and then some other thread C calling
os_event_reset(), the is_set flag of the event will be set to FALSE;
but now if thread A calls os_event_wait_low() with the signal_count
value returned from the earlier call of os_event_reset(), it will
return immediately without waiting.
Q.E.D.

Proof (windows): If there is a writer thread which is forced to wait for
the lock, it may be able to set the state of rw_lock to RW_LOCK_WAIT_EX
The design of rw_lock ensures that there is one and only one thread
that is able to change the state to RW_LOCK_WAIT_EX and this thread is
guaranteed to acquire the lock after it is released by the current
holders and before any other waiter gets the lock.
On windows this thread waits on a separate event i.e.: wait_ex_event.
Since only one thread can wait on this event there is no chance
of this event getting reset before the writer starts wait on it.
Therefore, this thread is guaranteed to catch the os_set_event()
signalled unconditionally at the release of the lock.
osku's avatar
osku committed
167 168 169 170
Q.E.D. */

/* Number of spin waits on mutexes: for performance monitoring */

171 172 173 174 175 176 177 178 179 180 181
/** The number of iterations in the mutex_spin_wait() spin loop.
Intended for performance monitoring. */
static ib_int64_t	mutex_spin_round_count		= 0;
/** The number of mutex_spin_wait() calls.  Intended for
performance monitoring. */
static ib_int64_t	mutex_spin_wait_count		= 0;
/** The number of OS waits in mutex_spin_wait().  Intended for
performance monitoring. */
static ib_int64_t	mutex_os_wait_count		= 0;
/** The number of mutex_exit() calls. Intended for performance
monitoring. */
182
UNIV_INTERN ib_int64_t	mutex_exit_count		= 0;
osku's avatar
osku committed
183

184
/** The global array of wait cells for implementation of the database's own
osku's avatar
osku committed
185
mutexes and read-write locks */
186
UNIV_INTERN sync_array_t*	sync_primary_wait_array;
osku's avatar
osku committed
187

188
/** This variable is set to TRUE when sync_init is called */
189
UNIV_INTERN ibool	sync_initialized	= FALSE;
osku's avatar
osku committed
190

191
/** An acquired mutex or rw-lock and its level in the latching order */
osku's avatar
osku committed
192
typedef struct sync_level_struct	sync_level_t;
193
/** Mutexes or rw-locks held by a thread */
osku's avatar
osku committed
194 195
typedef struct sync_thread_struct	sync_thread_t;

196
#ifdef UNIV_SYNC_DEBUG
197
/** The latch levels currently owned by threads are stored in this data
osku's avatar
osku committed
198 199
structure; the size of this array is OS_THREAD_MAX_N */

200
UNIV_INTERN sync_thread_t*	sync_thread_level_arrays;
osku's avatar
osku committed
201

202
/** Mutex protecting sync_thread_level_arrays */
203
UNIV_INTERN mutex_t		sync_thread_mutex;
204 205 206 207

# ifdef UNIV_PFS_MUTEX
UNIV_INTERN mysql_pfs_key_t	sync_thread_mutex_key;
# endif /* UNIV_PFS_MUTEX */
208
#endif /* UNIV_SYNC_DEBUG */
osku's avatar
osku committed
209

210
/** Global list of database mutexes (not OS mutexes) created. */
211
UNIV_INTERN ut_list_base_node_t  mutex_list;
osku's avatar
osku committed
212

213
/** Mutex protecting the mutex_list variable */
214
UNIV_INTERN mutex_t mutex_list_mutex;
osku's avatar
osku committed
215

216 217 218 219
#ifdef UNIV_PFS_MUTEX
UNIV_INTERN mysql_pfs_key_t	mutex_list_mutex_key;
#endif /* UNIV_PFS_MUTEX */

220
#ifdef UNIV_SYNC_DEBUG
221
/** Latching order checks start when this is set TRUE */
222
UNIV_INTERN ibool	sync_order_checks_on	= FALSE;
223
#endif /* UNIV_SYNC_DEBUG */
osku's avatar
osku committed
224

225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
/** Number of slots reserved for each OS thread in the sync level array */
static const ulint SYNC_THREAD_N_LEVELS = 10000;

typedef struct sync_arr_struct sync_arr_t;

/** Array for tracking sync levels per thread. */
struct sync_arr_struct {
	ulint		in_use;		/*!< Number of active cells */
	ulint		n_elems;	/*!< Number of elements in the array */
	ulint		max_elems;	/*!< Maximum elements */
	ulint		next_free;	/*!< ULINT_UNDEFINED or index of next
					free slot */
	sync_level_t*	elems;		/*!< Array elements */
};

240
/** Mutexes or rw-locks held by a thread */
osku's avatar
osku committed
241
struct sync_thread_struct{
242 243 244
	os_thread_id_t	id;		/*!< OS thread id */
	sync_arr_t*	levels;		/*!< level array for this thread; if
					this is NULL this slot is unused */
osku's avatar
osku committed
245 246
};

247
/** An acquired mutex or rw-lock and its level in the latching order */
osku's avatar
osku committed
248
struct sync_level_struct{
249 250 251 252 253 254 255 256 257 258
	void*		latch;		/*!< pointer to a mutex or an
					rw-lock; NULL means that
					the slot is empty */
	ulint		level;		/*!< level of the latch in the
					latching order. This field is
					overloaded to serve as a node in a
					linked list of free nodes too. When
					latch == NULL then this will contain
					the ordinal value of the next free
					element */
osku's avatar
osku committed
259 260
};

261
/******************************************************************//**
osku's avatar
osku committed
262 263 264 265
Creates, or rather, initializes a mutex object in a specified memory
location (which must be appropriately aligned). The mutex is initialized
in the reset state. Explicit freeing of the mutex with mutex_free is
necessary only if the memory block containing it is freed. */
266
UNIV_INTERN
osku's avatar
osku committed
267 268 269
void
mutex_create_func(
/*==============*/
270
	mutex_t*	mutex,		/*!< in: pointer to memory */
271
#ifdef UNIV_DEBUG
272
	const char*	cmutex_name,	/*!< in: mutex name */
273
# ifdef UNIV_SYNC_DEBUG
274
	ulint		level,		/*!< in: level */
275 276
# endif /* UNIV_SYNC_DEBUG */
#endif /* UNIV_DEBUG */
277 278
	const char*	cfile_name,	/*!< in: file name where created */
	ulint		cline)		/*!< in: file line where created */
osku's avatar
osku committed
279
{
280
#if defined(HAVE_ATOMIC_BUILTINS)
281
	mutex_reset_lock_word(mutex);
282
#else
osku's avatar
osku committed
283 284 285
	os_fast_mutex_init(&(mutex->os_fast_mutex));
	mutex->lock_word = 0;
#endif
286
	mutex->event = os_event_create(NULL);
osku's avatar
osku committed
287
	mutex_set_waiters(mutex, 0);
288
#ifdef UNIV_DEBUG
osku's avatar
osku committed
289
	mutex->magic_n = MUTEX_MAGIC_N;
290
#endif /* UNIV_DEBUG */
osku's avatar
osku committed
291 292 293
#ifdef UNIV_SYNC_DEBUG
	mutex->line = 0;
	mutex->file_name = "not yet reserved";
294
	mutex->level = level;
295
#endif /* UNIV_SYNC_DEBUG */
osku's avatar
osku committed
296 297
	mutex->cfile_name = cfile_name;
	mutex->cline = cline;
298
	mutex->count_os_wait = 0;
299
#ifdef UNIV_DEBUG
300 301 302 303 304 305 306 307
	mutex->cmutex_name=	  cmutex_name;
	mutex->count_using=	  0;
	mutex->mutex_type=	  0;
	mutex->lspent_time=	  0;
	mutex->lmax_spent_time=     0;
	mutex->count_spin_loop= 0;
	mutex->count_spin_rounds=   0;
	mutex->count_os_yield=  0;
308
#endif /* UNIV_DEBUG */
309

osku's avatar
osku committed
310 311 312 313 314
	/* Check that lock_word is aligned; this is important on Intel */
	ut_ad(((ulint)(&(mutex->lock_word))) % 4 == 0);

	/* NOTE! The very first mutexes are not put to the mutex list */

315 316 317 318 319
	if ((mutex == &mutex_list_mutex)
#ifdef UNIV_SYNC_DEBUG
	    || (mutex == &sync_thread_mutex)
#endif /* UNIV_SYNC_DEBUG */
	    ) {
osku's avatar
osku committed
320

321
		return;
osku's avatar
osku committed
322
	}
323

osku's avatar
osku committed
324 325
	mutex_enter(&mutex_list_mutex);

326 327
	ut_ad(UT_LIST_GET_LEN(mutex_list) == 0
	      || UT_LIST_GET_FIRST(mutex_list)->magic_n == MUTEX_MAGIC_N);
osku's avatar
osku committed
328 329 330 331 332 333

	UT_LIST_ADD_FIRST(list, mutex_list, mutex);

	mutex_exit(&mutex_list_mutex);
}

334
/******************************************************************//**
335
NOTE! Use the corresponding macro mutex_free(), not directly this function!
osku's avatar
osku committed
336 337 338
Calling this function is obligatory only if the memory buffer containing
the mutex is freed. Removes a mutex object from the mutex list. The mutex
is checked to be in the reset state. */
339
UNIV_INTERN
osku's avatar
osku committed
340
void
341 342
mutex_free_func(
/*============*/
343
	mutex_t*	mutex)	/*!< in: mutex */
osku's avatar
osku committed
344
{
345
	ut_ad(mutex_validate(mutex));
osku's avatar
osku committed
346 347
	ut_a(mutex_get_lock_word(mutex) == 0);
	ut_a(mutex_get_waiters(mutex) == 0);
348

349 350 351 352 353 354 355 356 357
#ifdef UNIV_MEM_DEBUG
	if (mutex == &mem_hash_mutex) {
		ut_ad(UT_LIST_GET_LEN(mutex_list) == 1);
		ut_ad(UT_LIST_GET_FIRST(mutex_list) == &mem_hash_mutex);
		UT_LIST_REMOVE(list, mutex_list, mutex);
		goto func_exit;
	}
#endif /* UNIV_MEM_DEBUG */

358 359 360 361 362
	if (mutex != &mutex_list_mutex
#ifdef UNIV_SYNC_DEBUG
	    && mutex != &sync_thread_mutex
#endif /* UNIV_SYNC_DEBUG */
	    ) {
osku's avatar
osku committed
363

364
		mutex_enter(&mutex_list_mutex);
osku's avatar
osku committed
365

366 367 368 369 370 371
		ut_ad(!UT_LIST_GET_PREV(list, mutex)
		      || UT_LIST_GET_PREV(list, mutex)->magic_n
		      == MUTEX_MAGIC_N);
		ut_ad(!UT_LIST_GET_NEXT(list, mutex)
		      || UT_LIST_GET_NEXT(list, mutex)->magic_n
		      == MUTEX_MAGIC_N);
372 373

		UT_LIST_REMOVE(list, mutex_list, mutex);
osku's avatar
osku committed
374 375 376 377

		mutex_exit(&mutex_list_mutex);
	}

378
	os_event_free(mutex->event);
379 380 381
#ifdef UNIV_MEM_DEBUG
func_exit:
#endif /* UNIV_MEM_DEBUG */
382
#if !defined(HAVE_ATOMIC_BUILTINS)
osku's avatar
osku committed
383 384 385 386 387
	os_fast_mutex_free(&(mutex->os_fast_mutex));
#endif
	/* If we free the mutex protecting the mutex list (freeing is
	not necessary), we have to reset the magic number AFTER removing
	it from the list. */
388
#ifdef UNIV_DEBUG
osku's avatar
osku committed
389
	mutex->magic_n = 0;
390
#endif /* UNIV_DEBUG */
osku's avatar
osku committed
391 392
}

393
/********************************************************************//**
394 395
NOTE! Use the corresponding macro in the header file, not this function
directly. Tries to lock the mutex for the current thread. If the lock is not
396 397
acquired immediately, returns with return value 1.
@return	0 if succeed, 1 if not */
398
UNIV_INTERN
osku's avatar
osku committed
399
ulint
400 401
mutex_enter_nowait_func(
/*====================*/
402
	mutex_t*	mutex,		/*!< in: pointer to mutex */
osku's avatar
osku committed
403
	const char*	file_name __attribute__((unused)),
404
					/*!< in: file name where mutex
osku's avatar
osku committed
405 406
					requested */
	ulint		line __attribute__((unused)))
407
					/*!< in: line where requested */
osku's avatar
osku committed
408 409 410 411 412
{
	ut_ad(mutex_validate(mutex));

	if (!mutex_test_and_set(mutex)) {

413
		ut_d(mutex->thread_id = os_thread_get_curr_id());
osku's avatar
osku committed
414 415 416 417 418 419 420 421 422 423
#ifdef UNIV_SYNC_DEBUG
		mutex_set_debug_info(mutex, file_name, line);
#endif

		return(0);	/* Succeeded! */
	}

	return(1);
}

424
#ifdef UNIV_DEBUG
425
/******************************************************************//**
426 427
Checks that the mutex has been initialized.
@return	TRUE */
428
UNIV_INTERN
osku's avatar
osku committed
429 430 431
ibool
mutex_validate(
/*===========*/
432
	const mutex_t*	mutex)	/*!< in: mutex */
osku's avatar
osku committed
433 434 435 436 437 438
{
	ut_a(mutex);
	ut_a(mutex->magic_n == MUTEX_MAGIC_N);

	return(TRUE);
}
439

440
/******************************************************************//**
441
Checks that the current thread owns the mutex. Works only in the debug
442 443
version.
@return	TRUE if owns */
444
UNIV_INTERN
445 446 447
ibool
mutex_own(
/*======*/
448
	const mutex_t*	mutex)	/*!< in: mutex */
449 450 451 452 453 454
{
	ut_ad(mutex_validate(mutex));

	return(mutex_get_lock_word(mutex) == 1
	       && os_thread_eq(mutex->thread_id, os_thread_get_curr_id()));
}
455
#endif /* UNIV_DEBUG */
osku's avatar
osku committed
456

457
/******************************************************************//**
osku's avatar
osku committed
458
Sets the waiters field in a mutex. */
459
UNIV_INTERN
osku's avatar
osku committed
460 461 462
void
mutex_set_waiters(
/*==============*/
463 464
	mutex_t*	mutex,	/*!< in: mutex */
	ulint		n)	/*!< in: value to set */
osku's avatar
osku committed
465
{
466 467
	volatile ulint*	ptr;		/* declared volatile to ensure that
					the value is stored to memory */
osku's avatar
osku committed
468 469 470 471 472 473 474 475
	ut_ad(mutex);

	ptr = &(mutex->waiters);

	*ptr = n;		/* Here we assume that the write of a single
				word in memory is atomic */
}

476
/******************************************************************//**
osku's avatar
osku committed
477 478 479
Reserves a mutex for the current thread. If the mutex is reserved, the
function spins a preset time (controlled by SYNC_SPIN_ROUNDS), waiting
for the mutex before suspending the thread. */
480
UNIV_INTERN
osku's avatar
osku committed
481 482 483
void
mutex_spin_wait(
/*============*/
484 485
	mutex_t*	mutex,		/*!< in: pointer to mutex */
	const char*	file_name,	/*!< in: file name where mutex
486
					requested */
487
	ulint		line)		/*!< in: line where requested */
osku's avatar
osku committed
488
{
489 490
	ulint	   index; /* index of the reserved wait cell */
	ulint	   i;	  /* spin round count */
491
#ifdef UNIV_DEBUG
492
	ib_int64_t lstart_time = 0, lfinish_time; /* for timing os_wait */
493 494 495 496
	ulint ltime_diff;
	ulint sec;
	ulint ms;
	uint timer_started = 0;
497
#endif /* UNIV_DEBUG */
498
	ut_ad(mutex);
osku's avatar
osku committed
499

500 501 502 503 504 505
	/* This update is not thread safe, but we don't mind if the count
	isn't exact. Moved out of ifdef that follows because we are willing
	to sacrifice the cost of counting this as the data is valuable.
	Count the number of calls to mutex_spin_wait. */
	mutex_spin_wait_count++;

osku's avatar
osku committed
506 507
mutex_loop:

508
	i = 0;
osku's avatar
osku committed
509

510 511 512 513 514
	/* Spin waiting for the lock word to become zero. Note that we do
	not have to assume that the read access to the lock word is atomic,
	as the actual locking is always committed with atomic test-and-set.
	In reality, however, all processors probably have an atomic read of
	a memory word. */
osku's avatar
osku committed
515 516

spin_loop:
517
	ut_d(mutex->count_spin_loop++);
osku's avatar
osku committed
518

519 520 521 522
	while (mutex_get_lock_word(mutex) != 0 && i < SYNC_SPIN_ROUNDS) {
		if (srv_spin_wait_delay) {
			ut_delay(ut_rnd_interval(0, srv_spin_wait_delay));
		}
osku's avatar
osku committed
523

524 525
		i++;
	}
osku's avatar
osku committed
526

527
	if (i == SYNC_SPIN_ROUNDS) {
528
#ifdef UNIV_DEBUG
529
		mutex->count_os_yield++;
530 531
#ifndef UNIV_HOTBACKUP
		if (timed_mutexes && timer_started == 0) {
532
			ut_usectime(&sec, &ms);
533
			lstart_time= (ib_int64_t)sec * 1000000 + ms;
534 535
			timer_started = 1;
		}
536
#endif /* UNIV_HOTBACKUP */
537
#endif /* UNIV_DEBUG */
538 539
		os_thread_yield();
	}
osku's avatar
osku committed
540 541

#ifdef UNIV_SRV_PRINT_LATCH_WAITS
542
	fprintf(stderr,
543 544
		"Thread %lu spin wait mutex at %p"
		" cfile %s cline %lu rnds %lu\n",
545
		(ulong) os_thread_pf(os_thread_get_curr_id()), (void*) mutex,
546
		mutex->cfile_name, (ulong) mutex->cline, (ulong) i);
osku's avatar
osku committed
547 548
#endif

549
	mutex_spin_round_count += i;
osku's avatar
osku committed
550

551
	ut_d(mutex->count_spin_rounds += i);
osku's avatar
osku committed
552

553 554
	if (mutex_test_and_set(mutex) == 0) {
		/* Succeeded! */
osku's avatar
osku committed
555

556
		ut_d(mutex->thread_id = os_thread_get_curr_id());
osku's avatar
osku committed
557
#ifdef UNIV_SYNC_DEBUG
558
		mutex_set_debug_info(mutex, file_name, line);
osku's avatar
osku committed
559 560
#endif

561 562
		goto finish_timing;
	}
osku's avatar
osku committed
563

564 565 566 567 568 569
	/* We may end up with a situation where lock_word is 0 but the OS
	fast mutex is still reserved. On FreeBSD the OS does not seem to
	schedule a thread which is constantly calling pthread_mutex_trylock
	(in mutex_test_and_set implementation). Then we could end up
	spinning here indefinitely. The following 'i++' stops this infinite
	spin. */
osku's avatar
osku committed
570

571
	i++;
osku's avatar
osku committed
572

573 574 575
	if (i < SYNC_SPIN_ROUNDS) {
		goto spin_loop;
	}
osku's avatar
osku committed
576

577
	sync_array_reserve_cell(sync_primary_wait_array, mutex,
578
				SYNC_MUTEX, file_name, line, &index);
osku's avatar
osku committed
579

580 581 582 583 584
	/* The memory order of the array reservation and the change in the
	waiters field is important: when we suspend a thread, we first
	reserve the cell and then set waiters field to 1. When threads are
	released in mutex_exit, the waiters field is first set to zero and
	then the event is set to the signaled state. */
osku's avatar
osku committed
585

586
	mutex_set_waiters(mutex, 1);
osku's avatar
osku committed
587

588 589 590 591
	/* Try to reserve still a few times */
	for (i = 0; i < 4; i++) {
		if (mutex_test_and_set(mutex) == 0) {
			/* Succeeded! Free the reserved wait cell */
osku's avatar
osku committed
592

593
			sync_array_free_cell(sync_primary_wait_array, index);
osku's avatar
osku committed
594

595
			ut_d(mutex->thread_id = os_thread_get_curr_id());
osku's avatar
osku committed
596
#ifdef UNIV_SYNC_DEBUG
597
			mutex_set_debug_info(mutex, file_name, line);
osku's avatar
osku committed
598 599 600
#endif

#ifdef UNIV_SRV_PRINT_LATCH_WAITS
601 602 603
			fprintf(stderr, "Thread %lu spin wait succeeds at 2:"
				" mutex at %p\n",
				(ulong) os_thread_pf(os_thread_get_curr_id()),
604
				(void*) mutex);
osku's avatar
osku committed
605 606
#endif

607
			goto finish_timing;
osku's avatar
osku committed
608

609 610 611 612 613
			/* Note that in this case we leave the waiters field
			set to 1. We cannot reset it to zero, as we do not
			know if there are other waiters. */
		}
	}
osku's avatar
osku committed
614

615 616 617
	/* Now we know that there has been some thread holding the mutex
	after the change in the wait array and the waiters field was made.
	Now there is no risk of infinite wait on the event. */
osku's avatar
osku committed
618 619

#ifdef UNIV_SRV_PRINT_LATCH_WAITS
620 621
	fprintf(stderr,
		"Thread %lu OS wait mutex at %p cfile %s cline %lu rnds %lu\n",
622
		(ulong) os_thread_pf(os_thread_get_curr_id()), (void*) mutex,
623
		mutex->cfile_name, (ulong) mutex->cline, (ulong) i);
osku's avatar
osku committed
624 625
#endif

626
	mutex_os_wait_count++;
osku's avatar
osku committed
627

628
	mutex->count_os_wait++;
629
#ifdef UNIV_DEBUG
630
	/* !!!!! Sometimes os_wait can be called without os_thread_yield */
631 632
#ifndef UNIV_HOTBACKUP
	if (timed_mutexes == 1 && timer_started == 0) {
633
		ut_usectime(&sec, &ms);
634
		lstart_time= (ib_int64_t)sec * 1000000 + ms;
635 636
		timer_started = 1;
	}
637
#endif /* UNIV_HOTBACKUP */
638
#endif /* UNIV_DEBUG */
osku's avatar
osku committed
639

640 641
	sync_array_wait_event(sync_primary_wait_array, index);
	goto mutex_loop;
osku's avatar
osku committed
642 643

finish_timing:
644
#ifdef UNIV_DEBUG
645 646
	if (timed_mutexes == 1 && timer_started==1) {
		ut_usectime(&sec, &ms);
647
		lfinish_time= (ib_int64_t)sec * 1000000 + ms;
648 649 650 651 652 653 654 655

		ltime_diff= (ulint) (lfinish_time - lstart_time);
		mutex->lspent_time += ltime_diff;

		if (mutex->lmax_spent_time < ltime_diff) {
			mutex->lmax_spent_time= ltime_diff;
		}
	}
656
#endif /* UNIV_DEBUG */
657
	return;
osku's avatar
osku committed
658 659
}

660
/******************************************************************//**
osku's avatar
osku committed
661
Releases the threads waiting in the primary wait array for this mutex. */
662
UNIV_INTERN
osku's avatar
osku committed
663 664 665
void
mutex_signal_object(
/*================*/
666
	mutex_t*	mutex)	/*!< in: mutex */
osku's avatar
osku committed
667 668 669 670 671
{
	mutex_set_waiters(mutex, 0);

	/* The memory order of resetting the waiters field and
	signaling the object is important. See LEMMA 1 above. */
672 673
	os_event_set(mutex->event);
	sync_array_object_signalled(sync_primary_wait_array);
osku's avatar
osku committed
674 675 676
}

#ifdef UNIV_SYNC_DEBUG
677
/******************************************************************//**
osku's avatar
osku committed
678
Sets the debug information for a reserved mutex. */
679
UNIV_INTERN
osku's avatar
osku committed
680 681 682
void
mutex_set_debug_info(
/*=================*/
683 684 685
	mutex_t*	mutex,		/*!< in: mutex */
	const char*	file_name,	/*!< in: file where requested */
	ulint		line)		/*!< in: line where requested */
osku's avatar
osku committed
686 687 688 689 690 691 692
{
	ut_ad(mutex);
	ut_ad(file_name);

	sync_thread_add_level(mutex, mutex->level);

	mutex->file_name = file_name;
693 694
	mutex->line	 = line;
}
osku's avatar
osku committed
695

696
/******************************************************************//**
osku's avatar
osku committed
697
Gets the debug information for a reserved mutex. */
698
UNIV_INTERN
osku's avatar
osku committed
699 700 701
void
mutex_get_debug_info(
/*=================*/
702 703 704 705
	mutex_t*	mutex,		/*!< in: mutex */
	const char**	file_name,	/*!< out: file where requested */
	ulint*		line,		/*!< out: line where requested */
	os_thread_id_t* thread_id)	/*!< out: id of the thread which owns
osku's avatar
osku committed
706 707 708 709 710 711 712 713 714
					the mutex */
{
	ut_ad(mutex);

	*file_name = mutex->file_name;
	*line	   = mutex->line;
	*thread_id = mutex->thread_id;
}

715
/******************************************************************//**
osku's avatar
osku committed
716
Prints debug info of currently reserved mutexes. */
717
static
osku's avatar
osku committed
718
void
719 720
mutex_list_print_info(
/*==================*/
721
	FILE*	file)		/*!< in: file where to print */
osku's avatar
osku committed
722 723 724 725 726 727 728 729
{
	mutex_t*	mutex;
	const char*	file_name;
	ulint		line;
	os_thread_id_t	thread_id;
	ulint		count		= 0;

	fputs("----------\n"
730
	      "MUTEX INFO\n"
731
	      "----------\n", file);
osku's avatar
osku committed
732 733 734 735 736 737 738 739 740

	mutex_enter(&mutex_list_mutex);

	mutex = UT_LIST_GET_FIRST(mutex_list);

	while (mutex != NULL) {
		count++;

		if (mutex_get_lock_word(mutex) != 0) {
741
			mutex_get_debug_info(mutex, &file_name, &line,
742
					     &thread_id);
743
			fprintf(file,
744 745
				"Locked mutex: addr %p thread %ld"
				" file %s line %ld\n",
746
				(void*) mutex, os_thread_pf(thread_id),
osku's avatar
osku committed
747 748 749 750 751 752
				file_name, line);
		}

		mutex = UT_LIST_GET_NEXT(list, mutex);
	}

753
	fprintf(file, "Total number of mutexes %ld\n", count);
754

osku's avatar
osku committed
755 756 757
	mutex_exit(&mutex_list_mutex);
}

758
/******************************************************************//**
759 760
Counts currently reserved mutexes. Works only in the debug version.
@return	number of reserved mutexes */
761
UNIV_INTERN
osku's avatar
osku committed
762 763 764 765 766
ulint
mutex_n_reserved(void)
/*==================*/
{
	mutex_t*	mutex;
767
	ulint		count	= 0;
osku's avatar
osku committed
768 769 770

	mutex_enter(&mutex_list_mutex);

771 772 773
	for (mutex = UT_LIST_GET_FIRST(mutex_list);
	     mutex != NULL;
	     mutex = UT_LIST_GET_NEXT(list, mutex)) {
osku's avatar
osku committed
774 775 776 777 778 779 780 781 782 783 784

		if (mutex_get_lock_word(mutex) != 0) {

			count++;
		}
	}

	mutex_exit(&mutex_list_mutex);

	ut_a(count >= 1);

785 786 787 788
	/* Subtract one, because this function itself was holding
	one mutex (mutex_list_mutex) */

	return(count - 1);
osku's avatar
osku committed
789 790
}

791
/******************************************************************//**
osku's avatar
osku committed
792
Returns TRUE if no mutex or rw-lock is currently locked. Works only in
793 794
the debug version.
@return	TRUE if no mutexes and rw-locks reserved */
795
UNIV_INTERN
osku's avatar
osku committed
796 797 798 799 800 801 802
ibool
sync_all_freed(void)
/*================*/
{
	return(mutex_n_reserved() + rw_lock_n_locked() == 0);
}

803
/******************************************************************//**
804 805
Looks for the thread slot for the calling thread.
@return	pointer to thread slot, NULL if not found */
osku's avatar
osku committed
806 807 808 809
static
sync_thread_t*
sync_thread_level_arrays_find_slot(void)
/*====================================*/
810

osku's avatar
osku committed
811 812
{
	ulint		i;
813
	os_thread_id_t	id;
osku's avatar
osku committed
814 815 816 817

	id = os_thread_get_curr_id();

	for (i = 0; i < OS_THREAD_MAX_N; i++) {
818
		sync_thread_t*	slot;
osku's avatar
osku committed
819

820
		slot = &sync_thread_level_arrays[i];
osku's avatar
osku committed
821 822 823 824 825 826 827 828 829 830

		if (slot->levels && os_thread_eq(slot->id, id)) {

			return(slot);
		}
	}

	return(NULL);
}

831
/******************************************************************//**
832 833
Looks for an unused thread slot.
@return	pointer to thread slot */
osku's avatar
osku committed
834 835 836 837
static
sync_thread_t*
sync_thread_level_arrays_find_free(void)
/*====================================*/
838

osku's avatar
osku committed
839 840 841 842
{
	ulint		i;

	for (i = 0; i < OS_THREAD_MAX_N; i++) {
843
		sync_thread_t*	slot;
osku's avatar
osku committed
844

845
		slot = &sync_thread_level_arrays[i];
osku's avatar
osku committed
846 847 848 849 850 851 852 853 854 855

		if (slot->levels == NULL) {

			return(slot);
		}
	}

	return(NULL);
}

856
/******************************************************************//**
857
Print warning. */
osku's avatar
osku committed
858
static
859 860 861 862 863
void
sync_print_warning(
/*===============*/
	const sync_level_t*	slot)	/*!< in: slot for which to
					print warning */
osku's avatar
osku committed
864
{
865
	mutex_t*	mutex;
osku's avatar
osku committed
866

867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894
	mutex = slot->latch;

	if (mutex->magic_n == MUTEX_MAGIC_N) {
		fprintf(stderr,
			"Mutex created at %s %lu\n",
			mutex->cfile_name, (ulong) mutex->cline);

		if (mutex_get_lock_word(mutex) != 0) {
			ulint		line;
			const char*	file_name;
			os_thread_id_t	thread_id;

			mutex_get_debug_info(
				mutex, &file_name, &line, &thread_id);

			fprintf(stderr,
				"InnoDB: Locked mutex:"
				" addr %p thread %ld file %s line %ld\n",
				(void*) mutex, os_thread_pf(thread_id),
				file_name, (ulong) line);
		} else {
			fputs("Not locked\n", stderr);
		}
	} else {
		rw_lock_t*	lock = slot->latch;

		rw_lock_print(lock);
	}
osku's avatar
osku committed
895 896
}

897
/******************************************************************//**
osku's avatar
osku committed
898
Checks if all the level values stored in the level array are greater than
899 900
the given limit.
@return	TRUE if all greater */
osku's avatar
osku committed
901 902 903 904
static
ibool
sync_thread_levels_g(
/*=================*/
905
	sync_arr_t*	arr,	/*!< in: pointer to level array for an OS
osku's avatar
osku committed
906
				thread */
907 908
	ulint		limit,	/*!< in: level limit */
	ulint		warn)	/*!< in: TRUE=display a diagnostic message */
osku's avatar
osku committed
909 910 911
{
	ulint		i;

912 913
	for (i = 0; i < arr->n_elems; i++) {
		const sync_level_t*	slot;
914

915
		slot = &arr->elems[i];
osku's avatar
osku committed
916

917 918
		if (slot->latch != NULL && slot->level <= limit) {
			if (warn) {
osku's avatar
osku committed
919
				fprintf(stderr,
920
					"InnoDB: sync levels should be"
921 922
					" > %lu but a level is %lu\n",
					(ulong) limit, (ulong) slot->level);
osku's avatar
osku committed
923

924
				sync_print_warning(slot);
osku's avatar
osku committed
925
			}
926 927

			return(FALSE);
osku's avatar
osku committed
928 929 930 931 932 933
		}
	}

	return(TRUE);
}

934
/******************************************************************//**
935
Checks if the level value is stored in the level array.
936
@return	slot if found or NULL */
osku's avatar
osku committed
937
static
938
const sync_level_t*
osku's avatar
osku committed
939 940
sync_thread_levels_contain(
/*=======================*/
941
	sync_arr_t*	arr,	/*!< in: pointer to level array for an OS
osku's avatar
osku committed
942
				thread */
943
	ulint		level)	/*!< in: level */
osku's avatar
osku committed
944 945 946
{
	ulint		i;

947 948
	for (i = 0; i < arr->n_elems; i++) {
		const sync_level_t*	slot;
osku's avatar
osku committed
949

950
		slot = &arr->elems[i];
osku's avatar
osku committed
951

952
		if (slot->latch != NULL && slot->level == level) {
osku's avatar
osku committed
953

954
			return(slot);
osku's avatar
osku committed
955 956 957
		}
	}

958
	return(NULL);
osku's avatar
osku committed
959 960
}

961 962 963 964 965 966 967 968 969 970 971 972
/******************************************************************//**
Checks if the level array for the current thread contains a
mutex or rw-latch at the specified level.
@return	a matching latch, or NULL if not found */
UNIV_INTERN
void*
sync_thread_levels_contains(
/*========================*/
	ulint	level)			/*!< in: latching order level
					(SYNC_DICT, ...)*/
{
	ulint		i;
973 974
	sync_arr_t*	arr;
	sync_thread_t*	thread_slot;
975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993

	if (!sync_order_checks_on) {

		return(NULL);
	}

	mutex_enter(&sync_thread_mutex);

	thread_slot = sync_thread_level_arrays_find_slot();

	if (thread_slot == NULL) {

		mutex_exit(&sync_thread_mutex);

		return(NULL);
	}

	arr = thread_slot->levels;

994 995
	for (i = 0; i < arr->n_elems; i++) {
		sync_level_t*	slot;
996

997
		slot = &arr->elems[i];
998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010

		if (slot->latch != NULL && slot->level == level) {

			mutex_exit(&sync_thread_mutex);
			return(slot->latch);
		}
	}

	mutex_exit(&sync_thread_mutex);

	return(NULL);
}

1011
/******************************************************************//**
1012
Checks that the level array for the current thread is empty.
1013
@return	a latch, or NULL if empty except the exceptions specified below */
1014
UNIV_INTERN
1015 1016 1017
void*
sync_thread_levels_nonempty_gen(
/*============================*/
1018
	ibool	dict_mutex_allowed)	/*!< in: TRUE if dictionary mutex is
osku's avatar
osku committed
1019 1020 1021 1022 1023
					allowed to be owned by the thread,
					also purge_is_running mutex is
					allowed */
{
	ulint		i;
1024 1025
	sync_arr_t*	arr;
	sync_thread_t*	thread_slot;
osku's avatar
osku committed
1026 1027 1028

	if (!sync_order_checks_on) {

1029
		return(NULL);
osku's avatar
osku committed
1030 1031 1032 1033 1034 1035 1036 1037 1038 1039
	}

	mutex_enter(&sync_thread_mutex);

	thread_slot = sync_thread_level_arrays_find_slot();

	if (thread_slot == NULL) {

		mutex_exit(&sync_thread_mutex);

1040
		return(NULL);
osku's avatar
osku committed
1041 1042 1043 1044
	}

	arr = thread_slot->levels;

1045 1046
	for (i = 0; i < arr->n_elems; ++i) {
		const sync_level_t*	slot;
osku's avatar
osku committed
1047

1048
		slot = &arr->elems[i];
osku's avatar
osku committed
1049

1050 1051 1052 1053
		if (slot->latch != NULL
		    && (!dict_mutex_allowed
			|| (slot->level != SYNC_DICT
			    && slot->level != SYNC_DICT_OPERATION))) {
osku's avatar
osku committed
1054 1055 1056 1057

			mutex_exit(&sync_thread_mutex);
			ut_error;

1058
			return(slot->latch);
osku's avatar
osku committed
1059 1060 1061 1062 1063
		}
	}

	mutex_exit(&sync_thread_mutex);

1064
	return(NULL);
osku's avatar
osku committed
1065 1066
}

1067
/******************************************************************//**
1068 1069
Checks that the level array for the current thread is empty.
@return	TRUE if empty */
1070
UNIV_INTERN
osku's avatar
osku committed
1071 1072 1073 1074 1075 1076 1077
ibool
sync_thread_levels_empty(void)
/*==========================*/
{
	return(sync_thread_levels_empty_gen(FALSE));
}

1078
/******************************************************************//**
osku's avatar
osku committed
1079 1080 1081
Adds a latch and its level in the thread level array. Allocates the memory
for the array if called first time for this OS thread. Makes the checks
against other latch levels stored in the array for this thread. */
1082
UNIV_INTERN
osku's avatar
osku committed
1083 1084 1085
void
sync_thread_add_level(
/*==================*/
1086 1087
	void*	latch,	/*!< in: pointer to a mutex or an rw-lock */
	ulint	level)	/*!< in: level in the latching order; if
1088
			SYNC_LEVEL_VARYING, nothing is done */
osku's avatar
osku committed
1089
{
1090
	ulint		i;
osku's avatar
osku committed
1091
	sync_level_t*	slot;
1092
	sync_arr_t*	array;
osku's avatar
osku committed
1093
	sync_thread_t*	thread_slot;
1094

osku's avatar
osku committed
1095 1096 1097 1098 1099 1100
	if (!sync_order_checks_on) {

		return;
	}

	if ((latch == (void*)&sync_thread_mutex)
1101 1102 1103
	    || (latch == (void*)&mutex_list_mutex)
	    || (latch == (void*)&rw_lock_debug_mutex)
	    || (latch == (void*)&rw_lock_list_mutex)) {
osku's avatar
osku committed
1104 1105 1106 1107

		return;
	}

1108
	if (level == SYNC_LEVEL_VARYING) {
osku's avatar
osku committed
1109 1110 1111 1112 1113 1114 1115 1116 1117

		return;
	}

	mutex_enter(&sync_thread_mutex);

	thread_slot = sync_thread_level_arrays_find_slot();

	if (thread_slot == NULL) {
1118
		ulint	sz;
1119

1120 1121
		sz = sizeof(*array)
		   + (sizeof(*array->elems) * SYNC_THREAD_N_LEVELS);
1122

1123 1124 1125
		/* We have to allocate the level array for a new thread */
		array = calloc(sz, sizeof(char));
		ut_a(array != NULL);
1126

1127 1128 1129
		array->next_free = ULINT_UNDEFINED;
		array->max_elems = SYNC_THREAD_N_LEVELS;
		array->elems = (sync_level_t*) &array[1];
osku's avatar
osku committed
1130

1131
		thread_slot = sync_thread_level_arrays_find_free();
osku's avatar
osku committed
1132

1133 1134
		thread_slot->levels = array;
		thread_slot->id = os_thread_get_curr_id();
osku's avatar
osku committed
1135 1136 1137
	}

	array = thread_slot->levels;
1138

osku's avatar
osku committed
1139 1140 1141 1142 1143
	/* NOTE that there is a problem with _NODE and _LEAF levels: if the
	B-tree height changes, then a leaf can change to an internal node
	or the other way around. We do not know at present if this can cause
	unnecessary assertion failures below. */

1144 1145 1146 1147
	switch (level) {
	case SYNC_NO_ORDER_CHECK:
	case SYNC_EXTERN_STORAGE:
	case SYNC_TREE_NODE_FROM_HASH:
osku's avatar
osku committed
1148
		/* Do no order checking */
1149
		break;
1150 1151 1152 1153 1154 1155 1156
	case SYNC_TRX_SYS_HEADER:
		if (srv_is_being_started) {
			/* This is violated during trx_sys_create_rsegs()
			when creating additional rollback segments when
			upgrading in innobase_start_or_create_for_mysql(). */
			break;
		}
1157 1158 1159
	case SYNC_MEM_POOL:
	case SYNC_MEM_HASH:
	case SYNC_RECV:
1160
	case SYNC_WORK_QUEUE:
1161
	case SYNC_LOG:
irana's avatar
irana committed
1162
	case SYNC_LOG_FLUSH_ORDER:
1163 1164
	case SYNC_THR_LOCAL:
	case SYNC_ANY_LATCH:
1165
	case SYNC_FILE_FORMAT_TAG:
1166
	case SYNC_DOUBLEWRITE:
1167
	case SYNC_SEARCH_SYS:
1168
	case SYNC_SEARCH_SYS_CONF:
1169 1170 1171 1172 1173 1174
	case SYNC_TRX_LOCK_HEAP:
	case SYNC_KERNEL:
	case SYNC_IBUF_BITMAP_MUTEX:
	case SYNC_RSEG:
	case SYNC_TRX_UNDO:
	case SYNC_PURGE_LATCH:
1175
	case SYNC_PURGE_QUEUE:
1176 1177 1178
	case SYNC_DICT_AUTOINC_MUTEX:
	case SYNC_DICT_OPERATION:
	case SYNC_DICT_HEADER:
vasil's avatar
vasil committed
1179 1180
	case SYNC_TRX_I_S_RWLOCK:
	case SYNC_TRX_I_S_LAST_READ:
1181
		if (!sync_thread_levels_g(array, level, TRUE)) {
1182 1183
			fprintf(stderr,
				"InnoDB: sync_thread_levels_g(array, %lu)"
vasil's avatar
vasil committed
1184
				" does not hold!\n", level);
1185 1186
			ut_error;
		}
1187
		break;
irana's avatar
irana committed
1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199
	case SYNC_BUF_FLUSH_LIST:
	case SYNC_BUF_POOL:
		/* We can have multiple mutexes of this type therefore we
		can only check whether the greater than condition holds. */
		if (!sync_thread_levels_g(array, level-1, TRUE)) {
			fprintf(stderr,
				"InnoDB: sync_thread_levels_g(array, %lu)"
				" does not hold!\n", level-1);
			ut_error;
		}
		break;

1200
	case SYNC_BUF_BLOCK:
1201
		/* Either the thread must own the buffer pool mutex
1202 1203
		(buf_pool->mutex), or it is allowed to latch only ONE
		buffer block (block->mutex or buf_pool->zip_mutex). */
1204 1205
		if (!sync_thread_levels_g(array, level, FALSE)) {
			ut_a(sync_thread_levels_g(array, level - 1, TRUE));
1206 1207
			ut_a(sync_thread_levels_contain(array, SYNC_BUF_POOL));
		}
1208 1209
		break;
	case SYNC_REC_LOCK:
1210 1211 1212 1213 1214 1215
		if (sync_thread_levels_contain(array, SYNC_KERNEL)) {
			ut_a(sync_thread_levels_g(array, SYNC_REC_LOCK - 1,
						  TRUE));
		} else {
			ut_a(sync_thread_levels_g(array, SYNC_REC_LOCK, TRUE));
		}
1216 1217
		break;
	case SYNC_IBUF_BITMAP:
1218 1219 1220
		/* Either the thread must own the master mutex to all
		the bitmap pages, or it is allowed to latch only ONE
		bitmap page. */
1221 1222 1223 1224 1225
		if (sync_thread_levels_contain(array,
					       SYNC_IBUF_BITMAP_MUTEX)) {
			ut_a(sync_thread_levels_g(array, SYNC_IBUF_BITMAP - 1,
						  TRUE));
		} else {
1226 1227 1228 1229 1230 1231
			/* This is violated during trx_sys_create_rsegs()
			when creating additional rollback segments when
			upgrading in innobase_start_or_create_for_mysql(). */
			ut_a(srv_is_being_started
			     || sync_thread_levels_g(array, SYNC_IBUF_BITMAP,
						     TRUE));
1232
		}
1233 1234
		break;
	case SYNC_FSP_PAGE:
osku's avatar
osku committed
1235
		ut_a(sync_thread_levels_contain(array, SYNC_FSP));
1236 1237
		break;
	case SYNC_FSP:
osku's avatar
osku committed
1238
		ut_a(sync_thread_levels_contain(array, SYNC_FSP)
1239
		     || sync_thread_levels_g(array, SYNC_FSP, TRUE));
1240 1241
		break;
	case SYNC_TRX_UNDO_PAGE:
1242 1243 1244 1245 1246 1247 1248
		/* Purge is allowed to read in as many UNDO pages as it likes,
		there was a bogus rule here earlier that forced the caller to
		acquire the purge_sys_t::mutex. The purge mutex did not really
		protect anything because it was only ever acquired by the
		single purge thread. The purge thread can read the UNDO pages
		without any covering mutex. */

osku's avatar
osku committed
1249
		ut_a(sync_thread_levels_contain(array, SYNC_TRX_UNDO)
1250
		     || sync_thread_levels_contain(array, SYNC_RSEG)
1251
		     || sync_thread_levels_g(array, level - 1, TRUE));
1252 1253
		break;
	case SYNC_RSEG_HEADER:
osku's avatar
osku committed
1254
		ut_a(sync_thread_levels_contain(array, SYNC_RSEG));
1255 1256
		break;
	case SYNC_RSEG_HEADER_NEW:
osku's avatar
osku committed
1257
		ut_a(sync_thread_levels_contain(array, SYNC_KERNEL)
1258
		     && sync_thread_levels_contain(array, SYNC_FSP_PAGE));
1259 1260
		break;
	case SYNC_TREE_NODE:
osku's avatar
osku committed
1261
		ut_a(sync_thread_levels_contain(array, SYNC_INDEX_TREE)
1262
		     || sync_thread_levels_contain(array, SYNC_DICT_OPERATION)
1263
		     || sync_thread_levels_g(array, SYNC_TREE_NODE - 1, TRUE));
1264 1265
		break;
	case SYNC_TREE_NODE_NEW:
osku's avatar
osku committed
1266
		ut_a(sync_thread_levels_contain(array, SYNC_FSP_PAGE)
1267
		     || sync_thread_levels_contain(array, SYNC_IBUF_MUTEX));
1268 1269
		break;
	case SYNC_INDEX_TREE:
1270 1271 1272 1273 1274 1275 1276 1277
		if (sync_thread_levels_contain(array, SYNC_IBUF_MUTEX)
		    && sync_thread_levels_contain(array, SYNC_FSP)) {
			ut_a(sync_thread_levels_g(array, SYNC_FSP_PAGE - 1,
						  TRUE));
		} else {
			ut_a(sync_thread_levels_g(array, SYNC_TREE_NODE - 1,
						  TRUE));
		}
1278 1279
		break;
	case SYNC_IBUF_MUTEX:
1280
		ut_a(sync_thread_levels_g(array, SYNC_FSP_PAGE - 1, TRUE));
1281 1282
		break;
	case SYNC_IBUF_PESS_INSERT_MUTEX:
1283 1284
		ut_a(sync_thread_levels_g(array, SYNC_FSP - 1, TRUE));
		ut_a(!sync_thread_levels_contain(array, SYNC_IBUF_MUTEX));
1285 1286
		break;
	case SYNC_IBUF_HEADER:
1287 1288 1289 1290
		ut_a(sync_thread_levels_g(array, SYNC_FSP - 1, TRUE));
		ut_a(!sync_thread_levels_contain(array, SYNC_IBUF_MUTEX));
		ut_a(!sync_thread_levels_contain(array,
						 SYNC_IBUF_PESS_INSERT_MUTEX));
1291 1292
		break;
	case SYNC_DICT:
osku's avatar
osku committed
1293 1294
#ifdef UNIV_DEBUG
		ut_a(buf_debug_prints
1295
		     || sync_thread_levels_g(array, SYNC_DICT, TRUE));
osku's avatar
osku committed
1296
#else /* UNIV_DEBUG */
1297
		ut_a(sync_thread_levels_g(array, SYNC_DICT, TRUE));
osku's avatar
osku committed
1298
#endif /* UNIV_DEBUG */
1299 1300
		break;
	default:
osku's avatar
osku committed
1301 1302 1303
		ut_error;
	}

1304 1305
	if (array->next_free == ULINT_UNDEFINED) {
		ut_a(array->n_elems < array->max_elems);
osku's avatar
osku committed
1306

1307 1308 1309 1310 1311
		i = array->n_elems++;
	} else {
		i = array->next_free;
		array->next_free = array->elems[i].level;
	}
osku's avatar
osku committed
1312

1313 1314
	ut_a(i < array->n_elems);
	ut_a(i != ULINT_UNDEFINED);
osku's avatar
osku committed
1315

1316 1317 1318 1319 1320
	++array->in_use;

	slot = &array->elems[i];

	ut_a(slot->latch == NULL);
osku's avatar
osku committed
1321

1322 1323
	slot->latch = latch;
	slot->level = level;
osku's avatar
osku committed
1324 1325 1326

	mutex_exit(&sync_thread_mutex);
}
1327

1328
/******************************************************************//**
1329
Removes a latch from the thread level array if it is found there.
1330 1331 1332
@return TRUE if found in the array; it is no error if the latch is
not found, as we presently are not able to determine the level for
every latch reservation the program does */
1333
UNIV_INTERN
osku's avatar
osku committed
1334 1335 1336
ibool
sync_thread_reset_level(
/*====================*/
1337
	void*	latch)	/*!< in: pointer to a mutex or an rw-lock */
osku's avatar
osku committed
1338
{
1339
	sync_arr_t*	array;
osku's avatar
osku committed
1340 1341
	sync_thread_t*	thread_slot;
	ulint		i;
1342

osku's avatar
osku committed
1343 1344 1345 1346 1347 1348
	if (!sync_order_checks_on) {

		return(FALSE);
	}

	if ((latch == (void*)&sync_thread_mutex)
1349 1350 1351
	    || (latch == (void*)&mutex_list_mutex)
	    || (latch == (void*)&rw_lock_debug_mutex)
	    || (latch == (void*)&rw_lock_list_mutex)) {
osku's avatar
osku committed
1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368

		return(FALSE);
	}

	mutex_enter(&sync_thread_mutex);

	thread_slot = sync_thread_level_arrays_find_slot();

	if (thread_slot == NULL) {

		ut_error;

		mutex_exit(&sync_thread_mutex);
		return(FALSE);
	}

	array = thread_slot->levels;
1369

1370 1371 1372 1373 1374 1375 1376 1377
	for (i = 0; i < array->n_elems; i++) {
		sync_level_t*	slot;

		slot = &array->elems[i];

		if (slot->latch != latch) {
			continue;
		}
osku's avatar
osku committed
1378

1379
		slot->latch = NULL;
osku's avatar
osku committed
1380

1381 1382 1383 1384
		/* Update the free slot list. See comment in sync_level_t
		for the level field. */
		slot->level = array->next_free;
		array->next_free = i;
osku's avatar
osku committed
1385

1386 1387
		ut_a(array->in_use >= 1);
		--array->in_use;
osku's avatar
osku committed
1388

1389 1390 1391 1392 1393 1394 1395
		/* If all cells are idle then reset the free
		list. The assumption is that this will save
		time when we need to scan up to n_elems. */

		if (array->in_use == 0) {
			array->n_elems = 0;
			array->next_free = ULINT_UNDEFINED;
osku's avatar
osku committed
1396
		}
1397 1398 1399 1400

		mutex_exit(&sync_thread_mutex);

		return(TRUE);
osku's avatar
osku committed
1401 1402
	}

1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414
	if (((mutex_t*) latch)->magic_n != MUTEX_MAGIC_N) {
		rw_lock_t*	rw_lock;

		rw_lock = (rw_lock_t*) latch;

		if (rw_lock->level == SYNC_LEVEL_VARYING) {
			mutex_exit(&sync_thread_mutex);

			return(TRUE);
		}
	}

osku's avatar
osku committed
1415 1416 1417 1418 1419 1420
	ut_error;

	mutex_exit(&sync_thread_mutex);

	return(FALSE);
}
1421
#endif /* UNIV_SYNC_DEBUG */
1422

1423
/******************************************************************//**
osku's avatar
osku committed
1424
Initializes the synchronization data structures. */
1425
UNIV_INTERN
osku's avatar
osku committed
1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437
void
sync_init(void)
/*===========*/
{
	ut_a(sync_initialized == FALSE);

	sync_initialized = TRUE;

	/* Create the primary system wait array which is protected by an OS
	mutex */

	sync_primary_wait_array = sync_array_create(OS_THREAD_MAX_N,
1438
						    SYNC_ARRAY_OS_MUTEX);
1439
#ifdef UNIV_SYNC_DEBUG
osku's avatar
osku committed
1440 1441 1442
	/* Create the thread latch level array where the latch levels
	are stored for each OS thread */

1443 1444 1445
	sync_thread_level_arrays = calloc(
		sizeof(sync_thread_t), OS_THREAD_MAX_N);
	ut_a(sync_thread_level_arrays != NULL);
osku's avatar
osku committed
1446

1447
#endif /* UNIV_SYNC_DEBUG */
1448
	/* Init the mutex list and create the mutex to protect it. */
osku's avatar
osku committed
1449 1450

	UT_LIST_INIT(mutex_list);
1451 1452
	mutex_create(mutex_list_mutex_key, &mutex_list_mutex,
		     SYNC_NO_ORDER_CHECK);
1453
#ifdef UNIV_SYNC_DEBUG
1454 1455
	mutex_create(sync_thread_mutex_key, &sync_thread_mutex,
		     SYNC_NO_ORDER_CHECK);
1456
#endif /* UNIV_SYNC_DEBUG */
osku's avatar
osku committed
1457 1458 1459 1460

	/* Init the rw-lock list and create the mutex to protect it. */

	UT_LIST_INIT(rw_lock_list);
1461 1462
	mutex_create(rw_lock_list_mutex_key, &rw_lock_list_mutex,
		     SYNC_NO_ORDER_CHECK);
osku's avatar
osku committed
1463 1464

#ifdef UNIV_SYNC_DEBUG
1465 1466
	mutex_create(rw_lock_debug_mutex_key, &rw_lock_debug_mutex,
		     SYNC_NO_ORDER_CHECK);
osku's avatar
osku committed
1467 1468 1469 1470 1471 1472

	rw_lock_debug_event = os_event_create(NULL);
	rw_lock_debug_waiters = FALSE;
#endif /* UNIV_SYNC_DEBUG */
}

1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500
#ifdef UNIV_SYNC_DEBUG
/******************************************************************//**
Frees all debug memory. */
static
void
sync_thread_level_arrays_free(void)
/*===============================*/

{
	ulint	i;

	for (i = 0; i < OS_THREAD_MAX_N; i++) {
		sync_thread_t*	slot;

		slot = &sync_thread_level_arrays[i];

		/* If this slot was allocated then free the slot memory too. */
		if (slot->levels != NULL) {
			free(slot->levels);
			slot->levels = NULL;
		}
	}

	free(sync_thread_level_arrays);
	sync_thread_level_arrays = NULL;
}
#endif /* UNIV_SYNC_DEBUG */

1501
/******************************************************************//**
osku's avatar
osku committed
1502 1503
Frees the resources in InnoDB's own synchronization data structures. Use
os_sync_free() after calling this. */
1504
UNIV_INTERN
osku's avatar
osku committed
1505 1506 1507 1508 1509 1510 1511 1512
void
sync_close(void)
/*===========*/
{
	mutex_t*	mutex;

	sync_array_free(sync_primary_wait_array);

1513 1514
	for (mutex = UT_LIST_GET_FIRST(mutex_list);
	     mutex != NULL;
1515
	     /* No op */) {
osku's avatar
osku committed
1516

1517 1518 1519 1520 1521 1522
#ifdef UNIV_MEM_DEBUG
		if (mutex == &mem_hash_mutex) {
			mutex = UT_LIST_GET_NEXT(list, mutex);
			continue;
		}
#endif /* UNIV_MEM_DEBUG */
1523

1524
		mutex_free(mutex);
1525 1526

	        mutex = UT_LIST_GET_FIRST(mutex_list);
osku's avatar
osku committed
1527 1528 1529
	}

	mutex_free(&mutex_list_mutex);
1530
#ifdef UNIV_SYNC_DEBUG
1531
	mutex_free(&sync_thread_mutex);
1532 1533 1534

	/* Switch latching order checks on in sync0sync.c */
	sync_order_checks_on = FALSE;
1535 1536

	sync_thread_level_arrays_free();
1537
#endif /* UNIV_SYNC_DEBUG */
1538 1539

	sync_initialized = FALSE;	
osku's avatar
osku committed
1540 1541
}

1542
/*******************************************************************//**
osku's avatar
osku committed
1543
Prints wait info of the sync system. */
1544
UNIV_INTERN
osku's avatar
osku committed
1545 1546 1547
void
sync_print_wait_info(
/*=================*/
1548
	FILE*	file)		/*!< in: file where to print */
osku's avatar
osku committed
1549 1550
{
#ifdef UNIV_SYNC_DEBUG
1551
	fprintf(file, "Mutex exits %llu, rws exits %llu, rwx exits %llu\n",
osku's avatar
osku committed
1552 1553 1554 1555
		mutex_exit_count, rw_s_exit_count, rw_x_exit_count);
#endif

	fprintf(file,
1556
		"Mutex spin waits %llu, rounds %llu, OS waits %llu\n"
1557 1558
		"RW-shared spins %llu, rounds %llu, OS waits %llu\n"
		"RW-excl spins %llu, rounds %llu, OS waits %llu\n",
1559 1560 1561 1562
		mutex_spin_wait_count,
		mutex_spin_round_count,
		mutex_os_wait_count,
		rw_s_spin_wait_count,
1563
		rw_s_spin_round_count,
1564 1565
		rw_s_os_wait_count,
		rw_x_spin_wait_count,
1566
		rw_x_spin_round_count,
1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577
		rw_x_os_wait_count);

	fprintf(file,
		"Spin rounds per wait: %.2f mutex, %.2f RW-shared, "
		"%.2f RW-excl\n",
		(double) mutex_spin_round_count /
		(mutex_spin_wait_count ? mutex_spin_wait_count : 1),
		(double) rw_s_spin_round_count /
		(rw_s_spin_wait_count ? rw_s_spin_wait_count : 1),
		(double) rw_x_spin_round_count /
		(rw_x_spin_wait_count ? rw_x_spin_wait_count : 1));
osku's avatar
osku committed
1578 1579
}

1580
/*******************************************************************//**
osku's avatar
osku committed
1581
Prints info of the sync system. */
1582
UNIV_INTERN
osku's avatar
osku committed
1583 1584 1585
void
sync_print(
/*=======*/
1586
	FILE*	file)		/*!< in: file where to print */
osku's avatar
osku committed
1587 1588
{
#ifdef UNIV_SYNC_DEBUG
1589
	mutex_list_print_info(file);
osku's avatar
osku committed
1590

1591
	rw_lock_list_print_info(file);
osku's avatar
osku committed
1592 1593 1594 1595 1596 1597
#endif /* UNIV_SYNC_DEBUG */

	sync_array_print_info(file, sync_primary_wait_array);

	sync_print_wait_info(file);
}