Implement VATS both in InnoDB and XtraDB. Add configuration options for it in both of them.

1 files changed, 141 insertions, 14 deletions

diff --git a/storage/xtradb/lock/lock0lock.cc b/storage/xtradb/lock/lock0lock.cc
index 8650cdd106a..eb47ef6e685 100644
--- a/storage/xtradb/lock/lock0lock.cc
+++ b/storage/xtradb/lock/lock0lock.cc
@@ -76,6 +76,9 @@ bitmap */
 
 #define LOCK_PAGE_BITMAP_MARGIN		64
 
+/** Lock scheduling algorithm */
+ulong innodb_lock_schedule_algorithm = INNODB_LOCK_SCHEDULE_ALGORITHM_FCFS;
+
 /* An explicit record lock affects both the record and the gap before it.
 An implicit x-lock does not affect the gap, it only locks the index
 record from read or update.
@@ -2006,6 +2009,72 @@ wsrep_print_wait_locks(
 #endif /* WITH_WSREP */
 
 /*********************************************************************//**
+Check if lock1 has higher priority than lock2.
+NULL has lowest priority.
+If neither of them is wait lock, the first one has higher priority.
+If only one of them is a wait lock, it has lower priority.
+Otherwise, the one with an older transaction has higher priority.
+@returns true if lock1 has higher priority, false otherwise. */
+bool
+has_higher_priority(
+	lock_t *lock1,
+	lock_t *lock2)
+{
+	if (lock1 == NULL) {
+		return false;
+	} else if (lock2 == NULL) {
+		return true;
+	}
+	if (!lock_get_wait(lock1)) {
+		return true;
+	} else if (!lock_get_wait(lock2)) {
+		return false;
+	}
+	return lock1->trx->start_time < lock2->trx->start_time;
+}
+
+/*********************************************************************//**
+Insert a lock to the hash list according to the mode (whether it is a wait lock)
+and the age of the transaction the it is associated with.
+If the lock is not a wait lock, insert it to the head of the hash list.
+Otherwise, insert it to the middle of the wait locks according to the age of the
+transaciton.
+*/
+static
+void
+lock_rec_insert_by_trx_age(
+	lock_t *in_lock, /*!< in: lock to be insert */
+	bool wait)		 	/*!< in: whether it's a wait lock */
+{
+	ulint					space;
+	ulint					page_no;
+	ulint 				rec_fold;
+	hash_cell_t		cell;
+	lock_t*				node;
+	lock_t*				next;
+
+	space = in_lock->un_member.rec_lock.space;
+	page_no = in_lock->un_member.rec_lock.page_no;
+	rec_fold = lock_rec_fold(space, page_no);
+	cell = hash_get_nth_cell(lock_sys->rec_hash,
+					hash_calc_hash(rec_fold, lock_sys->rec_hash));
+
+	node = (lock_t *) cell->node;
+	// If in_lock is not a wait lock, we insert it to the head of the list.
+	if (node == NULL || !wait || has_higher_priority(in_lock, node)) {
+		cell->node = in_lock;
+		in_lock->hash = node;
+		return;
+	}
+	while (node != NULL && has_higher_priority((lock_t *) node->hash, in_lock)) {
+		node = (lock_t *) node->hash;
+	}
+	next = (lock_t *) node->hash;
+	node->hash = in_lock;
+	in_lock->hash = next;
+}
+
+/*********************************************************************//**
 Creates a new record lock and inserts it to the lock queue. Does NOT check
 for deadlocks or lock compatibility!
 @return	created lock */
@@ -2167,13 +2236,19 @@ lock_rec_create(
 			return(lock);
 		}
 		trx_mutex_exit(c_lock->trx);
+	} else if (innodb_lock_schedule_algorithm == INNODB_LOCK_SCHEDULE_ALGORITHM_VATS) {
+		lock_rec_insert_by_trx_age(lock, type_mode & LOCK_WAIT);
 	} else {
 		HASH_INSERT(lock_t, hash, lock_sys->rec_hash,
-			    lock_rec_fold(space, page_no), lock);
+					lock_rec_fold(space, page_no), lock);
 	}
 #else
-	HASH_INSERT(lock_t, hash, lock_sys->rec_hash,
-		    lock_rec_fold(space, page_no), lock);
+	if (innodb_lock_schedule_algorithm == INNODB_LOCK_SCHEDULE_ALGORITHM_VATS) {
+		lock_rec_insert_by_trx_age(lock, type_mode & LOCK_WAIT);
+	} else {
+		HASH_INSERT(lock_t, hash, lock_sys->rec_hash,
+					lock_rec_fold(space, page_no), lock);
+	}
 #endif /* WITH_WSREP */
 
 	lock_sys->rec_num++;
@@ -2859,6 +2934,27 @@ lock_rec_cancel(
 }
 
 /*************************************************************//**
+Move the lock to the head of the hash list. */
+static
+void
+lock_rec_move_to_front(
+	lock_t *lock_to_move,	/*!< in: lock to be moved */
+	ulint rec_fold)			 /*!< in: rec fold of the lock */
+{
+	if (lock_to_move != NULL)
+	{
+		// Move the target lock to the head of the list
+		hash_cell_t* cell = hash_get_nth_cell(lock_sys->rec_hash,
+        	                  hash_calc_hash(rec_fold, lock_sys->rec_hash));
+		if (lock_to_move != cell->node) {
+			lock_t *next = (lock_t *) cell->node;
+			cell->node = lock_to_move;
+			lock_to_move->hash = next;
+		}
+	}
+}
+
+/*************************************************************//**
 Removes a record lock request, waiting or granted, from the queue and
 grants locks to other transactions in the queue if they now are entitled
 to a lock. NOTE: all record locks contained in in_lock are removed. */
@@ -2898,20 +2994,51 @@ lock_rec_dequeue_from_page(
 	MONITOR_INC(MONITOR_RECLOCK_REMOVED);
 	MONITOR_DEC(MONITOR_NUM_RECLOCK);
 
-	/* Check if waiting locks in the queue can now be granted: grant
-	locks if there are no conflicting locks ahead. Stop at the first
-	X lock that is waiting or has been granted. */
+	if (innodb_lock_schedule_algorithm == INNODB_LOCK_SCHEDULE_ALGORITHM_FCFS) {
+		/* Check if waiting locks in the queue can now be granted: grant
+		locks if there are no conflicting locks ahead. Stop at the first
+		X lock that is waiting or has been granted. */
 
-	for (lock = lock_rec_get_first_on_page_addr(space, page_no);
-	     lock != NULL;
-	     lock = lock_rec_get_next_on_page(lock)) {
+		for (lock = lock_rec_get_first_on_page_addr(space, page_no);
+		     lock != NULL;
+		     lock = lock_rec_get_next_on_page(lock)) {
 
-		if (lock_get_wait(lock)
-		    && !lock_rec_has_to_wait_in_queue(lock)) {
+			if (lock_get_wait(lock)
+			    && !lock_rec_has_to_wait_in_queue(lock)) {
 
-			/* Grant the lock */
-			ut_ad(lock->trx != in_lock->trx);
-			lock_grant(lock);
+				/* Grant the lock */
+				ut_ad(lock->trx != in_lock->trx);
+				lock_grant(lock);
+			}
+		}
+	} else {
+		/* Grant locks if there are no conflicting locks ahead.
+		   Move granted locks to the head of the list. */
+		for (lock = lock_rec_get_first_on_page_addr(space, page_no);
+			 lock != NULL;) {
+
+			/* If the lock is a wait lock on this page, and it does not need to wait. */
+			if ((lock->un_member.rec_lock.space == space)
+				&& (lock->un_member.rec_lock.page_no == page_no)
+				&& lock_get_wait(lock)
+				&& !lock_rec_has_to_wait_in_queue(lock)) {
+
+				lock_grant(lock);
+
+				if (previous != NULL) {
+					/* Move the lock to the head of the list. */
+					HASH_GET_NEXT(hash, previous) = HASH_GET_NEXT(hash, lock);
+					lock_rec_move_to_front(lock, rec_fold);
+				} else {
+					/* Already at the head of the list. */
+					previous = lock;
+				}
+				/* Move on to the next lock. */
+				lock = static_cast<lock_t *>(HASH_GET_NEXT(hash, previous));
+			} else {
+				previous = lock;
+				lock = static_cast<lock_t *>(HASH_GET_NEXT(hash, lock));
+			}
 		}
 	}
 }