merge revision(s) 56558,59116,59136: [Backport #12670]

	* gc.c (heap_page_resurrect): do not return tomb_pages when
	  page->freelist == NULL.
	  [Bug #12670]

	test for [Bug #12670]

	heap corruption by deferred free.
	gc.c: expand sorted pages

	* gc.c (heap_page_allocate): expand sorted pages before inserting
	  allocated new page.  [Bug #12670]

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/branches/ruby_2_3@59234 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

5 files changed, 86 insertions, 24 deletions

diff --git a/ChangeLog b/ChangeLog
index 237567d8b9..17deaf86c9 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,14 @@
+Fri Jun 30 21:35:16 2017  Nobuyoshi Nakada  <nobu@ruby-lang.org>
+
+	* gc.c (heap_page_allocate): expand sorted pages before inserting
+	  allocated new page. [Bug #12670]
+
+Fri Jun 30 21:33:39 2017  Koichi Sasada  <ko1@atdot.net>
+
+	* gc.c (heap_page_resurrect): do not return tomb_pages when
+	  page->freelist == NULL.
+	  [Bug #12670]
+
 Fri Jun 30 21:23:20 2017  Nobuyoshi Nakada  <nobu@ruby-lang.org>
 
 	* vsnprintf.c (BSD_vfprintf): sign and hex-prefix should not be counted
diff --git a/ext/-test-/typeddata/typeddata.c b/ext/-test-/typeddata/typeddata.c
index 1c5d677713..ae060960cd 100644
--- a/ext/-test-/typeddata/typeddata.c
+++ b/ext/-test-/typeddata/typeddata.c
@@ -2,19 +2,43 @@
 
 static const rb_data_type_t test_data = {
     "typed_data",
+    {NULL, ruby_xfree, NULL},
+    NULL, NULL,
+    0/* deferred free */,
 };
 
 static VALUE
+test_alloc(VALUE klass)
+{
+    char *p;
+    return TypedData_Make_Struct(klass, char, &test_data, p);
+}
+
+static VALUE
 test_check(VALUE self, VALUE obj)
 {
     rb_check_typeddata(obj, &test_data);
     return obj;
 }
 
+static VALUE
+test_make(VALUE klass, VALUE num)
+{
+    unsigned long i, n = NUM2UINT(num);
+
+    for (i = 0; i < n; i++) {
+	test_alloc(klass);
+    }
+
+    return Qnil;
+}
+
 void
 Init_typeddata(void)
 {
     VALUE mBug = rb_define_module("Bug");
     VALUE klass = rb_define_class_under(mBug, "TypedData", rb_cData);
+    rb_define_alloc_func(klass, test_alloc);
     rb_define_singleton_method(klass, "check", test_check, 1);
+    rb_define_singleton_method(klass, "make", test_make, 1);
 }
diff --git a/gc.c b/gc.c
index 8a345db0cc..5d73a7e157 100644
--- a/gc.c
+++ b/gc.c
@@ -1314,6 +1314,29 @@ rb_objspace_free(rb_objspace_t *objspace)
 }
 
 static void
+heap_pages_expand_sorted_to(rb_objspace_t *objspace, size_t next_length)
+{
+    struct heap_page **sorted;
+    size_t size = next_length * sizeof(struct heap_page *);
+
+    gc_report(3, objspace, "heap_pages_expand_sorted: next_length: %d, size: %d\n", (int)next_length, (int)size);
+
+    if (heap_pages_sorted_length > 0) {
+	sorted = (struct heap_page **)realloc(heap_pages_sorted, size);
+	if (sorted) heap_pages_sorted = sorted;
+    }
+    else {
+	sorted = heap_pages_sorted = (struct heap_page **)malloc(size);
+    }
+
+    if (sorted == 0) {
+	rb_memerror();
+    }
+
+    heap_pages_sorted_length = next_length;
+}
+
+static void
 heap_pages_expand_sorted(rb_objspace_t *objspace)
 {
     size_t next_length = heap_allocatable_pages;
@@ -1321,24 +1344,7 @@ heap_pages_expand_sorted(rb_objspace_t *objspace)
     next_length += heap_tomb->page_length;
 
     if (next_length > heap_pages_sorted_length) {
-	struct heap_page **sorted;
-	size_t size = next_length * sizeof(struct heap_page *);
-
-	gc_report(3, objspace, "heap_pages_expand_sorted: next_length: %d, size: %d\n", (int)next_length, (int)size);
-
-	if (heap_pages_sorted_length > 0) {
-	    sorted = (struct heap_page **)realloc(heap_pages_sorted, size);
-	    if (sorted) heap_pages_sorted = sorted;
-	}
-	else {
-	    sorted = heap_pages_sorted = (struct heap_page **)malloc(size);
-	}
-
-	if (sorted == 0) {
-	    rb_memerror();
-	}
-
-	heap_pages_sorted_length = next_length;
+	heap_pages_expand_sorted_to(objspace, next_length);
     }
 }
 
@@ -1477,6 +1483,9 @@ heap_page_allocate(rb_objspace_t *objspace)
 	    rb_bug("same heap page is allocated: %p at %"PRIuVALUE, (void *)page_body, (VALUE)mid);
 	}
     }
+    if (heap_allocated_pages >= heap_pages_sorted_length) {
+	heap_pages_expand_sorted_to(objspace, heap_allocated_pages + 1);
+    }
     if (hi < heap_allocated_pages) {
 	MEMMOVE(&heap_pages_sorted[hi+1], &heap_pages_sorted[hi], struct heap_page_header*, heap_allocated_pages - hi);
     }
@@ -1486,7 +1495,10 @@ heap_page_allocate(rb_objspace_t *objspace)
     heap_allocated_pages++;
     objspace->profile.total_allocated_pages++;
 
-    if (RGENGC_CHECK_MODE) assert(heap_allocated_pages <= heap_pages_sorted_length);
+    if (heap_allocated_pages > heap_pages_sorted_length) {
+	rb_bug("heap_page_allocate: allocated(%"PRIdSIZE") > sorted(%"PRIdSIZE")",
+	       heap_allocated_pages, heap_pages_sorted_length);
+    }
 
     /* adjust obj_limit (object number available in this page) */
     start = (RVALUE*)((VALUE)page_body + sizeof(struct heap_page_header));
@@ -1516,12 +1528,16 @@ heap_page_allocate(rb_objspace_t *objspace)
 static struct heap_page *
 heap_page_resurrect(rb_objspace_t *objspace)
 {
-    struct heap_page *page;
+    struct heap_page *page = heap_tomb->pages;
 
-    if ((page = heap_tomb->pages) != NULL) {
-	heap_unlink_page(objspace, heap_tomb, page);
-	return page;
+    while (page) {
+	if (page->freelist != NULL) {
+	    heap_unlink_page(objspace, heap_tomb, page);
+	    return page;
+	}
+	page = page->next;
     }
+
     return NULL;
 }
 
diff --git a/test/-ext-/typeddata/test_typeddata.rb b/test/-ext-/typeddata/test_typeddata.rb
index 058b7b70c5..c768b5e752 100644
--- a/test/-ext-/typeddata/test_typeddata.rb
+++ b/test/-ext-/typeddata/test_typeddata.rb
@@ -17,4 +17,15 @@ class Test_TypedData < Test::Unit::TestCase
     obj = eval("class C\u{1f5ff}; self; end").new
     assert_raise_with_message(TypeError, /C\u{1f5ff}/) {Bug::TypedData.check(obj)}
   end
+
+  def test_deferred_free
+    assert_ruby_status([], "#{<<-"begin;"}\n#{<<-"end;"}")
+    require "-test-/typeddata"
+    begin;
+      n = 1 << 20
+      Bug::TypedData.make(n)
+    end;
+  rescue MiniTest::Assertion => e
+    skip e.message
+  end
 end
diff --git a/version.h b/version.h
index 0005fdf3bc..beca3fa556 100644
--- a/version.h
+++ b/version.h
@@ -1,6 +1,6 @@
 #define RUBY_VERSION "2.3.5"
 #define RUBY_RELEASE_DATE "2017-06-30"
-#define RUBY_PATCHLEVEL 330
+#define RUBY_PATCHLEVEL 331
 
 #define RUBY_RELEASE_YEAR 2017
 #define RUBY_RELEASE_MONTH 6