MDEV-19526 heap number overflow on innodb_page_size=64k

InnoDB only reserves 13 bits for the heap number in the record header,
limiting the heap number to be at most 8191. But, when using
innodb_page_size=64k and secondary index records of 7 bytes each,
it is possible to exceed the maximum heap number.

btr_cur_optimistic_insert(): Let the operation fail if the
maximum number of records would be exceeded.

page_mem_alloc_heap(): Move to the same compilation unit with the
only caller, and let the operation fail if the maximum heap number
has been allocated already.

10 files changed, 139 insertions, 122 deletions

diff --git a/mysql-test/suite/innodb/r/innodb-64k.result b/mysql-test/suite/innodb/r/innodb-64k.result
index dc938f236cd..0ecc1b7096b 100644
--- a/mysql-test/suite/innodb/r/innodb-64k.result
+++ b/mysql-test/suite/innodb/r/innodb-64k.result
@@ -1084,3 +1084,10 @@ update t2 set col145=@b;
 COMMIT;
 drop table t2;
 DROP TABLE t1;
+#
+# MDEV-19526 heap number overflow
+#
+CREATE TABLE t1(a SMALLINT NOT NULL UNIQUE AUTO_INCREMENT, KEY(a))
+ENGINE=InnoDB;
+INSERT INTO t1 (a) SELECT seq FROM seq_1_to_8191;
+DROP TABLE t1;
diff --git a/mysql-test/suite/innodb/t/innodb-64k.test b/mysql-test/suite/innodb/t/innodb-64k.test
index 0498544279b..50dc1535aa6 100644
--- a/mysql-test/suite/innodb/t/innodb-64k.test
+++ b/mysql-test/suite/innodb/t/innodb-64k.test
@@ -2,6 +2,7 @@
 # Tests for setting innodb-page-size=64k; 
 --source include/have_innodb.inc
 --source include/have_innodb_64k.inc
+--source include/have_sequence.inc
 
 call mtr.add_suppression("InnoDB: Warning: innodb_page_size has been changed from default value *");
 call mtr.add_suppression("InnoDB: Resizing redo log from *");
@@ -650,6 +651,15 @@ COMMIT;
 
 drop table t2;
 DROP TABLE t1;
+
+--echo #
+--echo # MDEV-19526 heap number overflow
+--echo #
+CREATE TABLE t1(a SMALLINT NOT NULL UNIQUE AUTO_INCREMENT, KEY(a))
+ENGINE=InnoDB;
+INSERT INTO t1 (a) SELECT seq FROM seq_1_to_8191;
+DROP TABLE t1;
+
 #
 # restore environment to the state it was before this test execution
 #
diff --git a/storage/innobase/btr/btr0cur.cc b/storage/innobase/btr/btr0cur.cc
index 7b2fbfa0f0e..8e1a7200ab3 100644
--- a/storage/innobase/btr/btr0cur.cc
+++ b/storage/innobase/btr/btr0cur.cc
@@ -3,7 +3,7 @@
 Copyright (c) 1994, 2016, Oracle and/or its affiliates. All Rights Reserved.
 Copyright (c) 2008, Google Inc.
 Copyright (c) 2012, Facebook Inc.
-Copyright (c) 2015, 2017, MariaDB Corporation.
+Copyright (c) 2015, 2020, MariaDB Corporation.
 
 Portions of this file contain modifications contributed and copyrighted by
 Google, Inc. Those modifications are gratefully acknowledged and are described
@@ -1433,17 +1433,23 @@ fail_err:
 	}
 
 	ulint	max_size = page_get_max_insert_size_after_reorganize(page, 1);
+	if (max_size < rec_size) {
+		goto fail;
+	}
+
+	const ulint n_recs = page_get_n_recs(page);
+	if (UNIV_UNLIKELY(n_recs >= 8189)) {
+		ut_ad(srv_page_size == 65536);
+		goto fail;
+	}
 
 	if (page_has_garbage(page)) {
-		if ((max_size < rec_size
-		     || max_size < BTR_CUR_PAGE_REORGANIZE_LIMIT)
-		    && page_get_n_recs(page) > 1
+		if (max_size < BTR_CUR_PAGE_REORGANIZE_LIMIT
+		    && n_recs > 1
 		    && page_get_max_insert_size(page, 1) < rec_size) {
 
 			goto fail;
 		}
-	} else if (max_size < rec_size) {
-		goto fail;
 	}
 
 	/* If there have been many consecutive inserts to the
diff --git a/storage/innobase/include/page0page.h b/storage/innobase/include/page0page.h
index 64ae31905b4..5e9081476ce 100644
--- a/storage/innobase/include/page0page.h
+++ b/storage/innobase/include/page0page.h
@@ -1,7 +1,7 @@
 /*****************************************************************************
 
 Copyright (c) 1994, 2016, Oracle and/or its affiliates. All Rights Reserved.
-Copyright (c) 2013, 2018, MariaDB Corporation.
+Copyright (c) 2013, 2020, MariaDB Corporation.
 
 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
@@ -759,21 +759,6 @@ page_mem_alloc_free(
 				free record list */
 	ulint		need);	/*!< in: number of bytes allocated */
 /************************************************************//**
-Allocates a block of memory from the heap of an index page.
-@return	pointer to start of allocated buffer, or NULL if allocation fails */
-UNIV_INTERN
-byte*
-page_mem_alloc_heap(
-/*================*/
-	page_t*		page,	/*!< in/out: index page */
-	page_zip_des_t*	page_zip,/*!< in/out: compressed page with enough
-				space available for inserting the record,
-				or NULL */
-	ulint		need,	/*!< in: total number of bytes needed */
-	ulint*		heap_no);/*!< out: this contains the heap number
-				of the allocated record
-				if allocation succeeds */
-/************************************************************//**
 Puts a record to free list. */
 UNIV_INLINE
 void
diff --git a/storage/innobase/page/page0cur.cc b/storage/innobase/page/page0cur.cc
index e9ac4b4bb04..94e861ab554 100644
--- a/storage/innobase/page/page0cur.cc
+++ b/storage/innobase/page/page0cur.cc
@@ -2,6 +2,7 @@
 
 Copyright (c) 1994, 2013, Oracle and/or its affiliates. All Rights Reserved.
 Copyright (c) 2012, Facebook Inc.
+Copyright (c) 2020, MariaDB Corporation.
 
 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
@@ -941,6 +942,52 @@ page_cur_parse_insert_rec(
 	return(ptr + end_seg_len);
 }
 
+/************************************************************//**
+Allocates a block of memory from the heap of an index page.
+@return	pointer to start of allocated buffer, or NULL if allocation fails */
+static
+byte*
+page_mem_alloc_heap(
+/*================*/
+	page_t*		page,	/*!< in/out: index page */
+	page_zip_des_t*	page_zip,/*!< in/out: compressed page with enough
+				space available for inserting the record,
+				or NULL */
+	ulint		need,	/*!< in: total number of bytes needed */
+	ulint*		heap_no)/*!< out: this contains the heap number
+				of the allocated record
+				if allocation succeeds */
+{
+	byte*	block;
+	ulint	avl_space;
+
+	ut_ad(page && heap_no);
+
+	avl_space = page_get_max_insert_size(page, 1);
+
+	if (avl_space >= need) {
+		const ulint h = page_dir_get_n_heap(page);
+		if (UNIV_UNLIKELY(h >= 8191)) {
+			/* At the minimum record size of 5+2 bytes,
+			we can only reach this condition when using
+			innodb_page_size=64k. */
+			ut_ad(srv_page_size == 65536);
+			return(NULL);
+		}
+		*heap_no = h;
+
+		block = page_header_get_ptr(page, PAGE_HEAP_TOP);
+
+		page_header_set_ptr(page, page_zip, PAGE_HEAP_TOP,
+				    block + need);
+		page_dir_set_n_heap(page, page_zip, 1 + *heap_no);
+
+		return(block);
+	}
+
+	return(NULL);
+}
+
 /***********************************************************//**
 Inserts a record next to page cursor on an uncompressed page.
 Returns pointer to inserted record if succeed, i.e., enough
diff --git a/storage/innobase/page/page0page.cc b/storage/innobase/page/page0page.cc
index ac16d71322a..1d9e4a97782 100644
--- a/storage/innobase/page/page0page.cc
+++ b/storage/innobase/page/page0page.cc
@@ -2,7 +2,7 @@
 
 Copyright (c) 1994, 2016, Oracle and/or its affiliates. All Rights Reserved.
 Copyright (c) 2012, Facebook Inc.
-Copyright (c) 2018, MariaDB Corporation.
+Copyright (c) 2018, 2020, MariaDB Corporation.
 
 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
@@ -235,44 +235,6 @@ page_set_max_trx_id(
 	}
 }
 
-/************************************************************//**
-Allocates a block of memory from the heap of an index page.
-@return	pointer to start of allocated buffer, or NULL if allocation fails */
-UNIV_INTERN
-byte*
-page_mem_alloc_heap(
-/*================*/
-	page_t*		page,	/*!< in/out: index page */
-	page_zip_des_t*	page_zip,/*!< in/out: compressed page with enough
-				space available for inserting the record,
-				or NULL */
-	ulint		need,	/*!< in: total number of bytes needed */
-	ulint*		heap_no)/*!< out: this contains the heap number
-				of the allocated record
-				if allocation succeeds */
-{
-	byte*	block;
-	ulint	avl_space;
-
-	ut_ad(page && heap_no);
-
-	avl_space = page_get_max_insert_size(page, 1);
-
-	if (avl_space >= need) {
-		block = page_header_get_ptr(page, PAGE_HEAP_TOP);
-
-		page_header_set_ptr(page, page_zip, PAGE_HEAP_TOP,
-				    block + need);
-		*heap_no = page_dir_get_n_heap(page);
-
-		page_dir_set_n_heap(page, page_zip, 1 + *heap_no);
-
-		return(block);
-	}
-
-	return(NULL);
-}
-
 #ifndef UNIV_HOTBACKUP
 /**********************************************************//**
 Writes a log record of page creation. */
diff --git a/storage/xtradb/btr/btr0cur.cc b/storage/xtradb/btr/btr0cur.cc
index 5235fe434a9..7d97881f552 100644
--- a/storage/xtradb/btr/btr0cur.cc
+++ b/storage/xtradb/btr/btr0cur.cc
@@ -3,7 +3,7 @@
 Copyright (c) 1994, 2016, Oracle and/or its affiliates. All Rights Reserved.
 Copyright (c) 2008, Google Inc.
 Copyright (c) 2012, Facebook Inc.
-Copyright (c) 2015, 2017, MariaDB Corporation.
+Copyright (c) 2015, 2020, MariaDB Corporation.
 
 Portions of this file contain modifications contributed and copyrighted by
 Google, Inc. Those modifications are gratefully acknowledged and are described
@@ -1542,17 +1542,23 @@ fail_err:
 	}
 
 	ulint	max_size = page_get_max_insert_size_after_reorganize(page, 1);
+	if (max_size < rec_size) {
+		goto fail;
+	}
+
+	const ulint n_recs = page_get_n_recs(page);
+	if (UNIV_UNLIKELY(n_recs >= 8189)) {
+		ut_ad(srv_page_size == 65536);
+		goto fail;
+	}
 
 	if (page_has_garbage(page)) {
-		if ((max_size < rec_size
-		     || max_size < BTR_CUR_PAGE_REORGANIZE_LIMIT)
-		    && page_get_n_recs(page) > 1
+		if (max_size < BTR_CUR_PAGE_REORGANIZE_LIMIT
+		    && n_recs > 1
 		    && page_get_max_insert_size(page, 1) < rec_size) {
 
 			goto fail;
 		}
-	} else if (max_size < rec_size) {
-		goto fail;
 	}
 
 	/* If there have been many consecutive inserts to the
diff --git a/storage/xtradb/include/page0page.h b/storage/xtradb/include/page0page.h
index 2efc2d302a1..b377aa68ac7 100644
--- a/storage/xtradb/include/page0page.h
+++ b/storage/xtradb/include/page0page.h
@@ -1,7 +1,7 @@
 /*****************************************************************************
 
 Copyright (c) 1994, 2016, Oracle and/or its affiliates. All Rights Reserved.
-Copyright (c) 2013, 2018, MariaDB Corporation.
+Copyright (c) 2013, 2020, MariaDB Corporation.
 
 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
@@ -749,21 +749,6 @@ page_mem_alloc_free(
 				free record list */
 	ulint		need);	/*!< in: number of bytes allocated */
 /************************************************************//**
-Allocates a block of memory from the heap of an index page.
-@return	pointer to start of allocated buffer, or NULL if allocation fails */
-UNIV_INTERN
-byte*
-page_mem_alloc_heap(
-/*================*/
-	page_t*		page,	/*!< in/out: index page */
-	page_zip_des_t*	page_zip,/*!< in/out: compressed page with enough
-				space available for inserting the record,
-				or NULL */
-	ulint		need,	/*!< in: total number of bytes needed */
-	ulint*		heap_no);/*!< out: this contains the heap number
-				of the allocated record
-				if allocation succeeds */
-/************************************************************//**
 Puts a record to free list. */
 UNIV_INLINE
 void
diff --git a/storage/xtradb/page/page0cur.cc b/storage/xtradb/page/page0cur.cc
index e9ac4b4bb04..94e861ab554 100644
--- a/storage/xtradb/page/page0cur.cc
+++ b/storage/xtradb/page/page0cur.cc
@@ -2,6 +2,7 @@
 
 Copyright (c) 1994, 2013, Oracle and/or its affiliates. All Rights Reserved.
 Copyright (c) 2012, Facebook Inc.
+Copyright (c) 2020, MariaDB Corporation.
 
 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
@@ -941,6 +942,52 @@ page_cur_parse_insert_rec(
 	return(ptr + end_seg_len);
 }
 
+/************************************************************//**
+Allocates a block of memory from the heap of an index page.
+@return	pointer to start of allocated buffer, or NULL if allocation fails */
+static
+byte*
+page_mem_alloc_heap(
+/*================*/
+	page_t*		page,	/*!< in/out: index page */
+	page_zip_des_t*	page_zip,/*!< in/out: compressed page with enough
+				space available for inserting the record,
+				or NULL */
+	ulint		need,	/*!< in: total number of bytes needed */
+	ulint*		heap_no)/*!< out: this contains the heap number
+				of the allocated record
+				if allocation succeeds */
+{
+	byte*	block;
+	ulint	avl_space;
+
+	ut_ad(page && heap_no);
+
+	avl_space = page_get_max_insert_size(page, 1);
+
+	if (avl_space >= need) {
+		const ulint h = page_dir_get_n_heap(page);
+		if (UNIV_UNLIKELY(h >= 8191)) {
+			/* At the minimum record size of 5+2 bytes,
+			we can only reach this condition when using
+			innodb_page_size=64k. */
+			ut_ad(srv_page_size == 65536);
+			return(NULL);
+		}
+		*heap_no = h;
+
+		block = page_header_get_ptr(page, PAGE_HEAP_TOP);
+
+		page_header_set_ptr(page, page_zip, PAGE_HEAP_TOP,
+				    block + need);
+		page_dir_set_n_heap(page, page_zip, 1 + *heap_no);
+
+		return(block);
+	}
+
+	return(NULL);
+}
+
 /***********************************************************//**
 Inserts a record next to page cursor on an uncompressed page.
 Returns pointer to inserted record if succeed, i.e., enough
diff --git a/storage/xtradb/page/page0page.cc b/storage/xtradb/page/page0page.cc
index 16587f872ef..ee31c9dbd87 100644
--- a/storage/xtradb/page/page0page.cc
+++ b/storage/xtradb/page/page0page.cc
@@ -2,7 +2,7 @@
 
 Copyright (c) 1994, 2016, Oracle and/or its affiliates. All Rights Reserved.
 Copyright (c) 2012, Facebook Inc.
-Copyright (c) 2018, MariaDB Corporation.
+Copyright (c) 2018, 2020, MariaDB Corporation.
 
 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
@@ -240,44 +240,6 @@ page_set_max_trx_id(
 	}
 }
 
-/************************************************************//**
-Allocates a block of memory from the heap of an index page.
-@return	pointer to start of allocated buffer, or NULL if allocation fails */
-UNIV_INTERN
-byte*
-page_mem_alloc_heap(
-/*================*/
-	page_t*		page,	/*!< in/out: index page */
-	page_zip_des_t*	page_zip,/*!< in/out: compressed page with enough
-				space available for inserting the record,
-				or NULL */
-	ulint		need,	/*!< in: total number of bytes needed */
-	ulint*		heap_no)/*!< out: this contains the heap number
-				of the allocated record
-				if allocation succeeds */
-{
-	byte*	block;
-	ulint	avl_space;
-
-	ut_ad(page && heap_no);
-
-	avl_space = page_get_max_insert_size(page, 1);
-
-	if (avl_space >= need) {
-		block = page_header_get_ptr(page, PAGE_HEAP_TOP);
-
-		page_header_set_ptr(page, page_zip, PAGE_HEAP_TOP,
-				    block + need);
-		*heap_no = page_dir_get_n_heap(page);
-
-		page_dir_set_n_heap(page, page_zip, 1 + *heap_no);
-
-		return(block);
-	}
-
-	return(NULL);
-}
-
 #ifndef UNIV_HOTBACKUP
 /**********************************************************//**
 Writes a log record of page creation. */