vm*: doubly-linked list from ccan to manage vm->living_threads

A doubly-linked list for tracking living threads guarantees
constant-time insert/delete performance with no corner cases of a
hash table.  I chose this ccan implementation of doubly-linked
lists over the BSD sys/queue.h implementation since:

1) insertion and removal are both branchless
2) locality is improved if a struct may be a member of multiple lists
   (0002 patch in Feature 9632 will introduce a secondary list
   for waiting FDs)

This also increases cache locality during iteration: improving
performance in a new IO#close benchmark with many sleeping threads
while still scanning the same number of threads.

	vm_thread_close 1.762

* vm_core.h (rb_vm_t): list_head and counter for living_threads
  (rb_thread_t): vmlt_node for living_threads linkage
  (rb_vm_living_threads_init): new function wrapper
  (rb_vm_living_threads_insert): ditto
  (rb_vm_living_threads_remove): ditto
* vm.c (rb_vm_living_threads_foreach): new function wrapper
* thread.c (terminate_i, thread_start_func_2, thread_create_core,
  thread_fd_close_i, thread_fd_close): update to use new APIs
* vm.c (vm_mark_each_thread_func, rb_vm_mark, ruby_vm_destruct,
  vm_memsize, vm_init2, Init_VM): ditto
* vm_trace.c (clear_trace_func_i, rb_clear_trace_func): ditto
* benchmark/bm_vm_thread_close.rb: added to show improvement
* ccan/build_assert/build_assert.h: added as a dependency of list.h
* ccan/check_type/check_type.h: ditto
* ccan/container_of/container_of.h: ditto
* ccan/licenses/BSD-MIT: ditto
* ccan/licenses/CC0: ditto
* ccan/str/str.h: ditto (stripped of unused macros)
* ccan/list/list.h: ditto
* common.mk: add CCAN_LIST_INCLUDES
  [ruby-core:61871][Feature 9632 (part 1)]

Apologies for the size of this commit, but I think a good
doubly-linked list will be useful for future features, too.
This may be used to add ordering to a container_of-based hash
table to preserve compatibility if required (e.g. feature 9614).

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

1 files changed, 29 insertions, 15 deletions

diff --git a/vm.c b/vm.c
index 5e387feb1f..cba2a7f896 100644
--- a/vm.c
+++ b/vm.c
@@ -1687,10 +1687,9 @@ rb_vm_call_cfunc(VALUE recv, VALUE (*func)(VALUE), VALUE arg,
 /* vm */
 
 static int
-vm_mark_each_thread_func(st_data_t key, st_data_t value, st_data_t dummy)
+vm_mark_each_thread_func(rb_thread_t *th, void *dummy)
 {
-    VALUE thval = (VALUE)key;
-    rb_gc_mark(thval);
+    rb_gc_mark(th->self);
     return ST_CONTINUE;
 }
 
@@ -1705,9 +1704,7 @@ rb_vm_mark(void *ptr)
     RUBY_GC_INFO("-------------------------------------------------\n");
     if (ptr) {
 	rb_vm_t *vm = ptr;
-	if (vm->living_threads) {
-	    st_foreach(vm->living_threads, vm_mark_each_thread_func, 0);
-	}
+	rb_vm_living_threads_foreach(vm, vm_mark_each_thread_func, 0);
 	RUBY_MARK_UNLESS_NULL(vm->thgroup_default);
 	RUBY_MARK_UNLESS_NULL(vm->mark_object_ary);
 	RUBY_MARK_UNLESS_NULL(vm->load_path);
@@ -1767,10 +1764,7 @@ ruby_vm_destruct(rb_vm_t *vm)
 	    rb_fiber_reset_root_local_storage(th->self);
 	    thread_free(th);
 	}
-	if (vm->living_threads) {
-	    st_free_table(vm->living_threads);
-	    vm->living_threads = 0;
-	}
+	rb_vm_living_threads_init(vm);
 	ruby_vm_run_at_exit_hooks(vm);
 	rb_vm_gvl_destroy(vm);
 #if defined(ENABLE_VM_OBJSPACE) && ENABLE_VM_OBJSPACE
@@ -1792,9 +1786,9 @@ vm_memsize(const void *ptr)
     if (ptr) {
 	const rb_vm_t *vmobj = ptr;
 	size_t size = sizeof(rb_vm_t);
-	if (vmobj->living_threads) {
-	    size += st_memsize(vmobj->living_threads);
-	}
+
+	size += vmobj->living_thread_num * sizeof(rb_thread_t);
+
 	if (vmobj->defined_strings) {
 	    size += DEFINED_EXPR * sizeof(VALUE);
 	}
@@ -1894,6 +1888,7 @@ static void
 vm_init2(rb_vm_t *vm)
 {
     MEMZERO(vm, rb_vm_t, 1);
+    rb_vm_living_threads_init(vm);
     vm->src_encoding_index = -1;
     vm->at_exit.basic.flags = (T_ARRAY | RARRAY_EMBED_FLAG) & ~RARRAY_EMBED_LEN_MASK; /* len set 0 */
     rb_obj_hide((VALUE)&vm->at_exit);
@@ -2665,8 +2660,7 @@ Init_VM(void)
 	th->top_self = rb_vm_top_self();
 	rb_thread_set_current(th);
 
-	vm->living_threads = st_init_numtable();
-	st_insert(vm->living_threads, th_self, (st_data_t) th->thread_id);
+	rb_vm_living_threads_insert(vm, th);
 
 	rb_gc_register_mark_object(iseqval);
 	GetISeqPtr(iseqval, iseq);
@@ -3001,3 +2995,23 @@ vm_collect_usage_register(int reg, int isset)
 }
 #endif
 
+void
+rb_vm_living_threads_foreach(rb_vm_t *vm,
+			    int (*fn)(rb_thread_t *, void*), void *arg)
+{
+    rb_thread_t *cur, *next;
+    list_for_each_safe(&vm->living_threads, cur, next, vmlt_node) {
+	int rc = fn(cur, arg);
+	switch (rc) {
+	  case ST_CHECK:
+	  case ST_CONTINUE: break;
+	  case ST_STOP: return;
+	  case ST_DELETE: /* untested */
+	    rb_vm_living_threads_remove(vm, cur);
+	    xfree(cur);
+	    break;
+	  default:
+	    rb_bug("rb_vm_living_threads_foreach: unexpected: %d", rc);
+	}
+    }
+}