Skip to contentSkip to conversation

Native POSIX Thread Library 0.1

ANNOUNCE Ulrich Drepper 23 participants 62 messages Sep 20, 2002 – Sep 26, 2002

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

We are pleased to announce the first publically available source release of a new POSIX thread library for Linux. As part of the continuous effort to improve Linux's capabilities as a client, server, and computing platform Red Hat sponsored the development of this completely new implementation of a POSIX thread library, called Native POSIX Thread Library, NPTL.

Unless major flaws in the design are found this code is intended to become the standard POSIX thread library on Linux system and it will be included in the GNU C library distribution.

The work visible here is the result of close collaboration of kernel and runtime developers. The collaboration proceeded by developing the kernel changes while writing the appropriate parts of the thread library. Whenever something couldn't be implemented optimally some interface was changed to eliminate the issue. The result is this thread library which is, unlike previous attempts, a very thin layer on top of the kernel. This helps to achieve a maximum of performance for a minimal price.

A white paper (still in its draft stage, though) describing the design is available at

http://people.redhat.com/drepper/nptl-design.pdf

It provides a larger number of details on the design and insight into the design process. At this point we want to repeat only a few important points:

- - the new library is based on an 1-on-1 model. Earlier design documents stated that an M-on-N implementation was necessary to support a scalable thread library. This was especially true for the IA-32 and x86-64 platforms since the ABI with respect to threads forces the use of segment registers and the only way to use those registers was with the Local Descriptor Table (LDT) data structure of the processor.

The kernel limitations the earlier designs were based on have been eliminated as part of this project, opening the road to a 1-on-1 implementation which has many advantages such as

+ less complex implementation;
+ avoidance of two-level scheduling, enabling the kernel to make all

    scheduling decisions;
  + direct interaction between kernel and user-level code (e.g., when
    delivering signals);

+ and more and more.

It is not generally accepted that a 1-on-1 model is superior but our tests showed the viability of this approach and by comparing it with the overhead added by existing M-on-N implementations we became convinced that 1-on-1 is the right approach.

Initial confirmations were test runs with huge numbers of threads. Even on IA-32 with its limited address space and memory handling running 100,000 concurrent threads was no problem at all, creating and destroying the threads did not take more than two seconds. This all was made possible by the kernel work performed as part of this project.

The only limiting factors on the number of threads today are resource availability (RAM and processor resources) and architecture limitations. Since every thread needs at least a stack and data structures describing the thread the number is capped. On 64-bit machines the architecture does not add any limitations anymore (at least for the moment) and with enough resources the number of threads can be grown arbitrarily.

This does not mean that using hundreds of thousands of threads is a desirable design for the majority of applications. At least not unless the number of processors matches the number of threads. But it is important to note that the design on the library does not have a fixed limit.

The kernel work to optimize for a high thread count is still ongoing. Some places in which the kernel iterates over process and threads remain and other places need to be cleaned up. But it has already been shown that given sufficient resources and a reasonable architecture an order of magnitude more threads can be created than in our tests on IA-32.

- - The futex system call is used extensively in all synchronization primitives and other places which need some kind of synchronization. The futex mechanism is generic enough to support the standard POSIX synchronization mechanisms with very little effort.

The fact that this is possible is also essential for the selection of the 1-on-1 model since only with the kernel seeing all the waiters and knowing that they are blocked for synchronization purposes will allow the scheduler to make decisions as good as a thread library would be able to in an M-on-N model implementation.

Futexes also allow the implementation of inter-process synchronization primitives, a sorely missed feature in the old LinuxThreads implementation (Hi jbj!).

- - Substantial effort went into making the thread creation and destruction as fast as possible. Extensions to the clone(2) system call were introduced to eliminate the need for a helper thread in either creation or destruction. The exit process in the kernel was optimized (previously not a high priority). The library itself optimizes the memory allocation so that in many cases the creation of a new thread can be achieved with one single system call.

On an old IA-32 dual 450MHz PII Xeon system 100,000 threads can be created and destroyed in 2.3 secs (with up to 50 threads running at any one time).

- - Programs indirectly linked against the thread library had problems with the old implementation because of the way symbols are looked up. This should not be a problem anymore.

The thread library is designed to be binary compatible with the old LinuxThreads implementation. This compatibility obviously has some limitations. In places where the LinuxThreads implementation diverged from the POSIX standard incompatibilities exist. Users of the old library have been warned from day one that this day will come and code which added work-arounds for the POSIX non-compliance better be prepared to remove that code. The visible changes of the library include:

- - The signal handling changes from per-thread signal handling to the POSIX process signal handling. This change will require changes in programs which exploit the non-conformance of the old implementation.

One consequence of this is that SIGSTOP works on the process. Job
control
in the shell and stopping the whole process in a debugger work now.

- - getpid() now returns the same value in all threads

- - the exec functions are implemented correctly: the exec'ed process gets the PID of the process. The parent of the multi-threaded application is only notified when the exec'ed process terminates.

- - thread handlers registered with pthread_atfork are not anymore run if vfork is used. This isn't required by the standard (which does not define vfork) and all which is allowed in the child is calling exit() or an exec function. A user of vfork better knows what s/he does.

- - libpthread should now be much more resistant to linking problems: even if the application doesn't list libpthread as a direct dependency functions which are extended by libpthread should work correctly.

- - no manager thread

- - inter-process mutex, read-write lock, conditional variable, and barrier implementations are available

- - the pthread_kill_other_threads_np function is not available. It was needed to work around the broken signal handling. If somebody shows some existing code which makes legitimate use of this function we might add it back.

- - requires a kernel with the threading capabilities of Linux 2.5.36.

The sources for the new library are for the time being available at

ftp://people.redhat.com/drepper/nptl/

The current sources contain support only for IA-32 but this will change very quickly. The thread library is built as part of glibc so the complete set of glibc sources is available as well. The current snapshot for glibc 2.3 (or glibc 2.3 when released) is necessary. You can find it at

ftp://sources.redhat.com/pub/glibc/snapshots

Final releases will be available on ftp.gnu.org and its mirrors.

Building glibc with the new thread library is demanding on the compilation environment.

- - The 2.5.36 kernel or above must be installed and used. To compile glibc it is necessary to create the symbolic link

     /lib/modules/$(uname -r)/build

to point to the build directory.

- - The general compiler requirement for glibc is at least gcc 3.2. For the new thread code it is even necessary to have working support for the __thread keyword.

Similarly, binutils with functioning TLS support are needed.

The (Null) beta release of the upcoming Red Hat Linux product is known to have the necessary tools available after updating from the latest binaries on the FTP site. This is no ploy to force everybody to use Red Hat Linux, it's just the only environment known to date which works. If alternatives are known they can be announced on the mailing list.

- - To configure glibc it is necessary to run in the build directory (which always should be separate from the source directory):

   /path/to/glibc/configure --prefix=/usr --enable-add-ons=linuxthreads2 \
      --enable-kernel=current --with-tls

The --enable-kernel parameter requires that the 2.5.36+ kernel is running. It is not strictly necessary but helps to avoid mistakes. It might also be a good idea to add --disable-profile, just to speed up the compilation.

When configured as above the library must not be installed since it would overwrite the system's library. If you want to install the resulting library choose a different --prefix parameter value. Otherwise the new code can be used without installation. Running existing binaries is possible with

elf/ld.so --library-path .:linuxthreads2:dlfcn:math <binary> <args>...

Alternatively the binary could be build to find the dynamic linker and DSO by itself. This is a much easier way to debug the code since gdb can start the binary. Compiling is a bit more complicated in this case:

   gcc -nostdlib -nostartfiles -o <OUTPUT> csu/crt1.o csu/crti.o \
     $(gcc --print-file-name=crtbegin.o) <INPUTS> \
     -Wl,-rpath,$PWD,-dynamic-linker,$PWD/ld-linux.so.2 \
     linuxthreads2/libpthread.so.0 ./libc.so.6 ./libc_nonshared.a \
     elf/ld-linux.so.2 $(gcc --print-file-name=crtend.o) csu/crtn.o

This command assumes that it is run in the build directory. Correct the paths if necessary. The compilation will use the system's headers which is a good test but might lead to strange effects if there are compatibility bugs left.

Once all these prerequisites are met compiling glibc should be easy. But there are some tests which will flunk. For good reasons we aren't officially releasing the code yet. The bugs are either in the TLS code which is not enabled in the standard glibc build, or obviously in the thread library itself. To run the tests for the thread library run

make subdirs=linuxthreads2 check

One word on the name 'linuxthreads2' of the directory. This is only a convenience thing so that the glibc configure scripts don't complain about missing thread support. It will we changed to reflect the real name of the library ASAP.

What can you expect?

This is a very early version of the code so the obvious answer is:
some problems. The test suite for the new thread code should pass but beside that and some performance measurement tool we haven't run much code. Ideally we would get people to write many more of these small test programs which are included in the sources. Compiling big programs would mean not being able to locate problems easy. But I certainly won't object to people running and debugging bigger applications. Please report successes and failures to the mailing list.

People who are interested in contributing must be aware that for any non-trivial change we need an assignment of the code to the FSF. The process is unfortunately necessary in today's world.

People who are contaminated by having worked on proprietary thread library implementation should not participate in discussions on the mailing list unless they willfully disclose the information. Every bit of information is publically available from the mailing list archive.

Which brings us to the final point: the mailing list for *all* discussions related to this thread library implementation is

[email protected]

Go to

https://listman.redhat.com/mailman/listinfo/phil-list

to subscribe, unsubscribe, or review the archive.

- -- - ---------------. ,-. 1325 Chesapeake Terrace
Ulrich Drepper \ ,-------------------' \ Sunnyvale, CA 94089 USA
Red Hat --' drepper at redhat.com ------------------------
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.7 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQE9im7E2ijCOnn/RHQRApe9AKCN20A8A5ITi3DUq+3IRZ0gsSVHTQCeKqEu fA5OFtNuzYqltxSMoL8Ambw=
=4pb4
-----END PGP SIGNATURE-----

#1 lore raw
Quoted 6 lines · Ulrich Drepper

Initial confirmations were test runs with huge numbers of threads. Even on IA-32 with its limited address space and memory handling running 100,000 concurrent threads was no problem at all, creating and destroying the threads did not take more than two seconds. This all was made possible by the kernel work performed as part of this project.

What stress tests and/or benchmarks are you using?

Thanks,
Bill

#2 lore raw

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoted 1 line · William Lee Irwin III

What stress tests and/or benchmarks are you using?

We have developed a little benchmark in parallel to the library. Nothing special, but you've seen Ingo using it in his argumentations (usually called p3).

This does not in any way removes the need for more benchmarks.

- -- - ---------------. ,-. 1325 Chesapeake Terrace
Ulrich Drepper \ ,-------------------' \ Sunnyvale, CA 94089 USA
Red Hat --' drepper at redhat.com ------------------------
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.7 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQE9inta2ijCOnn/RHQRAp+mAJ9KQJgH1wy1hifkON6/v9EgkptjbgCdHQhF vcrLVpU85pCuq6fZDo8uFn0=
=Ep3W
-----END PGP SIGNATURE-----

#3 lore raw
Quoted 2 lines
Quoted 1 line · William Lee Irwin III

What stress tests and/or benchmarks are you using?

Quoted 4 lines · Ulrich Drepper

We have developed a little benchmark in parallel to the library. Nothing special, but you've seen Ingo using it in his argumentations (usually called p3).
This does not in any way removes the need for more benchmarks.

If you could pass that along for me (or others) to add to the list of things to bench I'd be much obliged.

Thanks,
Bill

#4 lore raw
In reply to Ulrich Drepper
Quoted 12 lines

- - the new library is based on an 1-on-1 model. Earlier design documents stated that an M-on-N implementation was necessary to support a scalable thread library. This was especially true for the IA-32 and x86-64 platforms since the ABI with respect to threads forces the use of segment registers and the only way to use those registers was with the Local Descriptor Table (LDT) data structure of the processor.

The kernel limitations the earlier designs were based on have been eliminated as part of this project, opening the road to a 1-on-1 implementation which has many advantages such as

Quoted 6 lines

+ less complex implementation;
+ avoidance of two-level scheduling, enabling the kernel to make all

     scheduling decisions;
   + direct interaction between kernel and user-level code (e.g., when
     delivering signals);

+ and more and more.

I'm just starting to look at this... Without digging into it, my impression is that this is 100% the right way to go. Rob Pike (Mr Plan 9, which while it hasn't had the impact of Linux is actually a fantastic chunk of work) once said "If you think you need threads, your processes are too fat". I believe that's another way of stating that a 1-on-1 model is the right approach. He's saying "don't make threads to make things lighter, that's bullshit, use processes as threads, that will force the processes to be light and that's a good thing for processes *and* threads".

My only issue with that approach (I'm a big time advocate of that approach) is TLB & page table sharing. My understanding (weak as it is) of Linux is that it does the right thing here so there isn't much of an issue. In Linux the address space is a first class object so the id in the TLB is an address space ID, not a process id, which means a pile of unrelated processes could, in theory, share the same chunk of address space. That's cool. A lot of processor folks have danced around that issue for years, I fought with Mash at MIPS about it, he knew it was something that was needed. But Linux, as far as I can tell, got it right in a different way that made the issue go away. Which means 1-on-1 threads are the right approach for reasons which have nothing to do with threads, as well as reasons which have to do with threads.

Kudos to Ulrich & team for getting it right. I'll go dig into it and see if I've missed the point or not, but this sounds really good.

Signature · 2 lines
---
Larry McVoy            	 lm at bitmover.com           http://www.bitmover.com/lm 
#5 lore raw
In reply to Ulrich Drepper
Quoted 3 lines · Ulrich Drepper

Initial confirmations were test runs with huge numbers of threads. Even on IA-32 with its limited address space and memory handling running 100,000 concurrent threads was no problem at all,

So, where did you put those 800 MB of kernel stacks needed for 100,000 threads ?

If you used the standard 3:1 user/kernel split you'd be using all of ZONE_NORMAL for kernel stacks, but if you use a 2:2 split you'll end up with a lot less user space (bad if you want to have many threads in the same address space).

Do you have some special solutions up your sleeve or is this in the category of as-of-yet unsolved problems ?

regards,

Rik

Signature · 5 lines
Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/		http://distro.conectiva.com/

Spamtraps of the month:  [email protected] [email protected]
#6 lore raw
Quoted 2 lines · Rik van Riel

So, where did you put those 800 MB of kernel stacks needed for 100,000 threads ?

That's what the 4KB stack patch is for. ;-)

-ben

#7 lore raw
Quoted 6 lines · Benjamin LaHaise
Quoted 2 lines · Rik van Riel

So, where did you put those 800 MB of kernel stacks needed for 100,000 threads ?

That's what the 4KB stack patch is for. ;-)

It's shameless plug time...

Just in case anybody is interested, I updated Ben's patch for 2.5.34.
I just resynced against current -bk, which is attached. Works For
Me (tm)

Signature · 2 lines
Dave Hansen
[email protected]

# This is a BitKeeper generated patch for the following project:
# Project Name: Linux kernel tree
# This patch format is intended for GNU patch command version 2.5 or higher. # This patch includes the following deltas:
# ChangeSet 1.552 -> 1.553
# arch/i386/kernel/process.c 1.40 -> 1.41
# arch/i386/kernel/irq.c 1.18 -> 1.19
# arch/i386/kernel/head.S 1.15 -> 1.16
# include/asm-i386/thread_info.h 1.7 -> 1.8
# include/asm-i386/page.h 1.16.1.1 -> 1.18
# arch/i386/kernel/entry.S 1.41.1.3 -> 1.44
# arch/i386/config.in 1.47.1.2 -> 1.49
# arch/i386/Makefile 1.17.1.3 -> 1.19
# arch/i386/kernel/i386_ksyms.c 1.30 -> 1.31
# arch/i386/kernel/smpboot.c 1.33.1.2 -> 1.35
# arch/i386/boot/compressed/misc.c 1.7 -> 1.8
# arch/i386/kernel/init_task.c 1.6 -> 1.7
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 02/09/19 haveblue@elm3b96.(none) 1.553
# Merge elm3b96.(none):/work/dave/bk/linux-2.5

# into elm3b96.(none):/work/dave/bk/linux-2.5-irqstack
# --------------------------------------------
#
diff -Nru a/arch/i386/Makefile b/arch/i386/Makefile
--- a/arch/i386/Makefile	Thu Sep 19 19:38:27 2002
+++ b/arch/i386/Makefile	Thu Sep 19 19:38:27 2002
@@ -85,6 +85,10 @@
 CFLAGS += -march=i586
 endif

+ifdef CONFIG_X86_STACK_CHECK
+CFLAGS += -p
+endif
+
HEAD := arch/i386/kernel/head.o arch/i386/kernel/init_task.o

libs-y += arch/i386/lib/

arch/i386/boot/compressed/misc.c +4 -0
diff -Nru a/arch/i386/boot/compressed/misc.c b/arch/i386/boot/compressed/misc.c
@@ -377,3 +377,7 @@
 	if (high_loaded) close_output_buffer_if_we_run_high(mv);
 	return high_loaded;
 }
+
+/* We don't actually check for stack overflows this early. */
+__asm__(".globl mcount ; mcount: ret\n");
+
arch/i386/config.in +7 -0
diff -Nru a/arch/i386/config.in b/arch/i386/config.in
@@ -35,6 +35,7 @@
 #
 # Define implied options from the CPU selection here
 #
+define_bool CONFIG_X86_HAVE_CMOV n
 
 if [ "$CONFIG_M386" = "y" ]; then
    define_bool CONFIG_X86_CMPXCHG n
@@ -91,18 +92,21 @@
    define_bool CONFIG_X86_GOOD_APIC y
    define_bool CONFIG_X86_USE_PPRO_CHECKSUM y
    define_bool CONFIG_X86_PPRO_FENCE y
+   define_bool CONFIG_X86_HAVE_CMOV y
 fi
 if [ "$CONFIG_MPENTIUMIII" = "y" ]; then
    define_int  CONFIG_X86_L1_CACHE_SHIFT 5
    define_bool CONFIG_X86_TSC y
    define_bool CONFIG_X86_GOOD_APIC y
    define_bool CONFIG_X86_USE_PPRO_CHECKSUM y
+   define_bool CONFIG_X86_HAVE_CMOV y
 fi
 if [ "$CONFIG_MPENTIUM4" = "y" ]; then
    define_int  CONFIG_X86_L1_CACHE_SHIFT 7
    define_bool CONFIG_X86_TSC y
    define_bool CONFIG_X86_GOOD_APIC y
    define_bool CONFIG_X86_USE_PPRO_CHECKSUM y
+   define_bool CONFIG_X86_HAVE_CMOV y
 fi
 if [ "$CONFIG_MK6" = "y" ]; then
    define_int  CONFIG_X86_L1_CACHE_SHIFT 5
@@ -116,6 +120,7 @@
    define_bool CONFIG_X86_GOOD_APIC y
    define_bool CONFIG_X86_USE_3DNOW y
    define_bool CONFIG_X86_USE_PPRO_CHECKSUM y
+   define_bool CONFIG_X86_HAVE_CMOV y
 fi
 if [ "$CONFIG_MELAN" = "y" ]; then
    define_int  CONFIG_X86_L1_CACHE_SHIFT 4
@@ -132,6 +137,7 @@
 if [ "$CONFIG_MCRUSOE" = "y" ]; then
    define_int  CONFIG_X86_L1_CACHE_SHIFT 5
    define_bool CONFIG_X86_TSC y
+   define_bool CONFIG_X86_HAVE_CMOV y
 fi
 if [ "$CONFIG_MWINCHIPC6" = "y" ]; then
    define_int  CONFIG_X86_L1_CACHE_SHIFT 5
@@ -435,6 +441,7 @@
    if [ "$CONFIG_HIGHMEM" = "y" ]; then
       bool '  Highmem debugging' CONFIG_DEBUG_HIGHMEM
    fi
+   bool '  Check for stack overflows' CONFIG_X86_STACK_CHECK
 fi
 
 endmenu
arch/i386/kernel/entry.S +89 -2

116 lines not on this page · raw message

arch/i386/kernel/head.S +2 -1
diff -Nru a/arch/i386/kernel/head.S b/arch/i386/kernel/head.S
@@ -15,6 +15,7 @@
 #include <asm/page.h>
 #include <asm/pgtable.h>
 #include <asm/desc.h>
+#include <asm/thread_info.h>
 
 #define OLD_CL_MAGIC_ADDR	0x90020
 #define OLD_CL_MAGIC		0xA33F
@@ -305,7 +306,7 @@
 	ret
 
 ENTRY(stack_start)
-	.long init_thread_union+8192
+	.long init_thread_union+THREAD_SIZE
 	.long __KERNEL_DS
 
 /* This is the default interrupt "handler" :-) */
arch/i386/kernel/i386_ksyms.c +5 -0
diff -Nru a/arch/i386/kernel/i386_ksyms.c b/arch/i386/kernel/i386_ksyms.c
@@ -172,3 +172,8 @@
 EXPORT_SYMBOL(is_sony_vaio_laptop);
 
 EXPORT_SYMBOL(__PAGE_KERNEL);
+
+#ifdef CONFIG_X86_STACK_CHECK
+extern void mcount(void);
+EXPORT_SYMBOL(mcount);
+#endif
arch/i386/kernel/init_task.c +17 -1
diff -Nru a/arch/i386/kernel/init_task.c b/arch/i386/kernel/init_task.c
@@ -13,6 +13,14 @@
 static struct signal_struct init_signals = INIT_SIGNALS(init_signals);
 struct mm_struct init_mm = INIT_MM(init_mm);
 
+union thread_union init_irq_union
+	__attribute__((__section__(".data.init_task")));
+
+#ifdef CONFIG_X86_STACK_CHECK
+union thread_union stack_overflow_stack
+	__attribute__((__section__(".data.init_task")));
+#endif
+
 /*
  * Initial thread structure.
  *
@@ -22,7 +30,15 @@
  */
 union thread_union init_thread_union 
 	__attribute__((__section__(".data.init_task"))) =
-		{ INIT_THREAD_INFO(init_task) };
+		{ { 
+			task:		&init_task,
+			exec_domain:	&default_exec_domain,
+			flags:		0,
+			cpu:		0,
+			addr_limit:	KERNEL_DS,
+			irq_stack:	&init_irq_union,
+		} };
+
 
 /*
  * Initial task structure.
arch/i386/kernel/irq.c +5 -4
diff -Nru a/arch/i386/kernel/irq.c b/arch/i386/kernel/irq.c
@@ -311,7 +311,8 @@
  * SMP cross-CPU interrupts have their own specific
  * handlers).
  */
-asmlinkage unsigned int do_IRQ(struct pt_regs regs)
+struct pt_regs *do_IRQ(struct pt_regs *regs) __attribute__((regparm(1)));
+struct pt_regs *do_IRQ(struct pt_regs *regs)
 {	
 	/* 
 	 * We ack quickly, we don't want the irq controller
@@ -323,7 +324,7 @@
 	 * 0 return value means that this irq is already being
 	 * handled by some other CPU. (or is disabled)
 	 */
-	int irq = regs.orig_eax & 0xff; /* high bits used in ret_from_ code  */
+	int irq = regs->orig_eax & 0xff; /* high bits used in ret_from_ code  */
 	int cpu = smp_processor_id();
 	irq_desc_t *desc = irq_desc + irq;
 	struct irqaction * action;
@@ -373,7 +374,7 @@
 	 */
 	for (;;) {
 		spin_unlock(&desc->lock);
-		handle_IRQ_event(irq, &regs, action);
+		handle_IRQ_event(irq, regs, action);
 		spin_lock(&desc->lock);
 		
 		if (likely(!(desc->status & IRQ_PENDING)))
@@ -392,7 +393,7 @@
 
 	irq_exit();
 
-	return 1;
+	return regs;
 }
 
 /**
arch/i386/kernel/process.c +11 -0
diff -Nru a/arch/i386/kernel/process.c b/arch/i386/kernel/process.c
@@ -438,6 +438,16 @@
 
 extern void show_trace(unsigned long* esp);
 
+#ifdef CONFIG_X86_STACK_CHECK
+void stack_overflow_panic(void *esp, void *eip)
+{
+	printk("stack overflow from %p.  esp: %p\n", eip, esp);
+	show_trace(esp);
+	panic("stack overflow\n");
+}
+
+#endif
+
 void show_regs(struct pt_regs * regs)
 {
 	unsigned long cr0 = 0L, cr2 = 0L, cr3 = 0L, cr4 = 0L;
@@ -693,6 +703,7 @@
 
 	/* never put a printk in __switch_to... printk() calls wake_up*() indirectly */
 
+	next_p->thread_info->irq_stack = prev_p->thread_info->irq_stack;
 	unlazy_fpu(prev_p);
 
 	/*
arch/i386/kernel/smpboot.c +34 -1
diff -Nru a/arch/i386/kernel/smpboot.c b/arch/i386/kernel/smpboot.c
@@ -66,6 +66,10 @@
 /* Per CPU bogomips and other parameters */
 struct cpuinfo_x86 cpu_data[NR_CPUS] __cacheline_aligned;
 
+extern union thread_union init_irq_union;
+union thread_union *irq_stacks[NR_CPUS] __cacheline_aligned =
+	{ &init_irq_union, };
+
 /* Set when the idlers are all forked */
 int smp_threads_ready;
 
@@ -760,6 +764,27 @@
 	return (send_status | accept_status);
 }
 
+static void __init setup_irq_stack(struct task_struct *p, int cpu)
+{
+	unsigned long stk;
+
+	stk = __get_free_pages(GFP_KERNEL, THREAD_ORDER);
+	if (!stk)
+		panic("I can't seem to allocate my irq stack.  Oh well, giving up.");
+
+	irq_stacks[cpu] = (void *)stk;
+	memset(irq_stacks[cpu], 0, THREAD_SIZE);
+	irq_stacks[cpu]->thread_info.cpu = cpu;
+	irq_stacks[cpu]->thread_info.preempt_count = 1;
+					/* interrupts are not preemptable */
+	p->thread_info->irq_stack = irq_stacks[cpu];
+
+	/* If we want to make the irq stack more than one unit
+	 * deep, we can chain then off of the irq_stack pointer
+	 * here.
+	 */
+}
+
 extern unsigned long cpu_initialized;
 
 static void __init do_boot_cpu (int apicid) 
@@ -783,6 +808,8 @@
 	if (IS_ERR(idle))
 		panic("failed fork for CPU %d", cpu);
 
+	setup_irq_stack(idle, cpu);
+
 	/*
 	 * We remove it from the pidhash and the runqueue
 	 * once we got the process:
@@ -800,7 +827,13 @@
 
 	/* So we see what's up   */
 	printk("Booting processor %d/%d eip %lx\n", cpu, apicid, start_eip);
-	stack_start.esp = (void *) (1024 + PAGE_SIZE + (char *)idle->thread_info);
+
+	/* The -4 is to correct for the fact that the stack pointer
+	 * is used to find the location of the thread_info structure
+	 * by masking off several of the LSBs.  Without the -4, esp
+	 * is pointing to the page after the one the stack is on.
+	 */
+	stack_start.esp = (void *)(THREAD_SIZE - 4 + (char *)idle->thread_info);
 
 	/*
 	 * This grunge runs the startup process for
include/asm-i386/page.h +4 -0
diff -Nru a/include/asm-i386/page.h b/include/asm-i386/page.h
@@ -3,7 +3,11 @@
 
 /* PAGE_SHIFT determines the page size */
 #define PAGE_SHIFT	12
+#ifndef __ASSEMBLY__
 #define PAGE_SIZE	(1UL << PAGE_SHIFT)
+#else
+#define PAGE_SIZE	(1 << PAGE_SHIFT)
+#endif
 #define PAGE_MASK	(~(PAGE_SIZE-1))
 
 #define LARGE_PAGE_MASK (~(LARGE_PAGE_SIZE-1))
include/asm-i386/thread_info.h +23 -19

86 lines not on this page · raw message

#8 lore raw
In reply to Benjamin LaHaise
Quoted 2 lines · Rik van Riel
Quoted 2 lines

So, where did you put those 800 MB of kernel stacks needed for 100,000 threads ?

Quoted 2 lines · Benjamin LaHaise

That's what the 4KB stack patch is for. ;-)
-ben

The task_struct isn't particularly slim either. I heard rumblings that way back when it was shared with the stack the NR_CPUS arrays filled (and overflowed) the entire stack... It's also enough to put a wee bit of pressure on ZONE_NORMAL even on smaller task count workloads.

Perhaps something like this is in order? vs. 2.5.33:

 fs/proc/array.c       |   22 ----------------------
 fs/proc/base.c        |   11 +----------
 include/linux/sched.h |    1 -
 kernel/fork.c         |   11 +----------
 kernel/timer.c        |    3 ---
 5 files changed, 2 insertions(+), 46 deletions(-)

Cheers,
Bill

===== fs/proc/array.c 1.24 vs edited =====

fs/proc/array.c +0 -22
@@ -592,25 +592,3 @@
 out:
 	return retval;
 }
-
-#ifdef CONFIG_SMP
-int proc_pid_cpu(struct task_struct *task, char * buffer)
-{
-	int i, len;
-
-	len = sprintf(buffer,
-		"cpu  %lu %lu\n",
-		jiffies_to_clock_t(task->utime),
-		jiffies_to_clock_t(task->stime));
-		
-	for (i = 0 ; i < NR_CPUS; i++) {
-		if (cpu_online(i))
-		len += sprintf(buffer + len, "cpu%d %lu %lu\n",
-			i,
-			jiffies_to_clock_t(task->per_cpu_utime[i]),
-			jiffies_to_clock_t(task->per_cpu_stime[i]));
-
-	}
-	return len;
-}
-#endif

===== fs/proc/base.c 1.26 vs edited =====

fs/proc/base.c +1 -10
@@ -52,7 +52,6 @@
 	PROC_PID_STAT,
 	PROC_PID_STATM,
 	PROC_PID_MAPS,
-	PROC_PID_CPU,
 	PROC_PID_MOUNTS,
 	PROC_PID_FD_DIR = 0x8000,	/* 0x8000-0xffff */
 };
@@ -72,9 +71,6 @@
   E(PROC_PID_CMDLINE,	"cmdline",	S_IFREG|S_IRUGO),
   E(PROC_PID_STAT,	"stat",		S_IFREG|S_IRUGO),
   E(PROC_PID_STATM,	"statm",	S_IFREG|S_IRUGO),
-#ifdef CONFIG_SMP
-  E(PROC_PID_CPU,	"cpu",		S_IFREG|S_IRUGO),
-#endif
   E(PROC_PID_MAPS,	"maps",		S_IFREG|S_IRUGO),
   E(PROC_PID_MEM,	"mem",		S_IFREG|S_IRUSR|S_IWUSR),
   E(PROC_PID_CWD,	"cwd",		S_IFLNK|S_IRWXUGO),
@@ -1003,12 +999,7 @@
 		case PROC_PID_MAPS:
 			inode->i_fop = &proc_maps_operations;
 			break;
-#ifdef CONFIG_SMP
-		case PROC_PID_CPU:
-			inode->i_fop = &proc_info_file_operations;
-			ei->op.proc_read = proc_pid_cpu;
-			break;
-#endif
+
 		case PROC_PID_MEM:
 			inode->i_op = &proc_mem_inode_operations;
 			inode->i_fop = &proc_mem_operations;

===== include/linux/sched.h 1.70 vs edited =====

include/linux/sched.h +0 -1
@@ -325,7 +325,6 @@
 	struct timer_list real_timer;
 	unsigned long utime, stime, cutime, cstime;
 	unsigned long start_time;
-	long per_cpu_utime[NR_CPUS], per_cpu_stime[NR_CPUS];
 /* mm fault and swap info: this can arguably be seen as either mm-specific or thread-specific */
 	unsigned long min_flt, maj_flt, nswap, cmin_flt, cmaj_flt, cnswap;
 	int swappable:1;

===== kernel/fork.c 1.49 vs edited =====

kernel/fork.c +1 -10
@@ -725,16 +725,7 @@
 	p->tty_old_pgrp = 0;
 	p->utime = p->stime = 0;
 	p->cutime = p->cstime = 0;
-#ifdef CONFIG_SMP
-	{
-		int i;
-
-		/* ?? should we just memset this ?? */
-		for(i = 0; i < NR_CPUS; i++)
-			p->per_cpu_utime[i] = p->per_cpu_stime[i] = 0;
-		spin_lock_init(&p->sigmask_lock);
-	}
-#endif
+	spin_lock_init(&p->sigmask_lock);
 	p->array = NULL;
 	p->lock_depth = -1;		/* -1 = no lock */
 	p->start_time = jiffies;

===== kernel/timer.c 1.17 vs edited =====

kernel/timer.c +0 -2
@@ -569,8 +569,6 @@
 void update_one_process(struct task_struct *p, unsigned long user,
 			unsigned long system, int cpu)
 {
-	p->per_cpu_utime[cpu] += user;
-	p->per_cpu_stime[cpu] += system;
 	do_process_times(p, user, system);
 	do_it_virt(p, user);
 	do_it_prof(p);
#9 lore raw
In reply to Rik van Riel
Quoted 8 lines · Rik van Riel
Quoted 3 lines · Ulrich Drepper

Initial confirmations were test runs with huge numbers of threads. Even on IA-32 with its limited address space and memory handling running 100,000 concurrent threads was no problem at all,

So, where did you put those 800 MB of kernel stacks needed for 100,000 threads ?

Come on, you and I normally agree, but 100,000 threads? Where is the need for that? More importantly, is there any realistic application that can use 100,000 threads where the kernel stack is 0 but the user level stack doesn't have exactly the same problem? The kernel can be perfect, i.e., cost zero, and you still have a problem.

Signature · 2 lines
---
Larry McVoy            	 lm at bitmover.com           http://www.bitmover.com/lm 
#10 lore raw
Quoted 7 lines · Larry McVoy
Quoted 2 lines · Rik van Riel

So, where did you put those 800 MB of kernel stacks needed for 100,000 threads ?

Come on, you and I normally agree, but 100,000 threads? Where is the need for that?

I agree, it's pretty silly. But still, I was curious how they managed to achieve it ;)

OTOH, some applications are known for sillyness ...

cheers,

Rik

Signature · 5 lines
Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/		http://distro.conectiva.com/

Spamtraps of the month:  [email protected] [email protected]
#11 lore raw

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoted 2 lines · Rik van Riel

I agree, it's pretty silly. But still, I was curious how they managed to achieve it ;)

Ingo will be able to tell you when he gets up. This is not my area of expertise. AFAIK there were no special changes involved; Ben's irq stack patch would add to this number (I think Ingo said something about 188,000 threads or so).

- -- - ---------------. ,-. 1325 Chesapeake Terrace
Ulrich Drepper \ ,-------------------' \ Sunnyvale, CA 94089 USA
Red Hat --' drepper at redhat.com ------------------------
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.7 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQE9ioi02ijCOnn/RHQRAnw+AJ9fFu36D8ZIk2Y3NC8Rpekb5EXwPwCePCBL Z/u1XIdgB2F/UuixLkIpNvI=
=Ldzx
-----END PGP SIGNATURE-----

#12 lore raw
In reply to Rik van Riel

In article <[email protected]>,

Quoted 11 lines · Rik van Riel
Quoted 7 lines · Larry McVoy
Quoted 2 lines · Rik van Riel

So, where did you put those 800 MB of kernel stacks needed for 100,000 threads ?

Come on, you and I normally agree, but 100,000 threads? Where is the need for that?

I agree, it's pretty silly. But still, I was curious how they managed to achieve it ;)

You didn't read the post carefully.

They started and waited for 100,000 threads.

They did not have them all running at the same time. I think the original post said something like "up to 50 at a time".

Basically, the benchmark was how _fast_ thread creation is, not now many you can run at the same time. 100k threads at once is crazy, but you can do it now on 64-bit architectures if you really want to.

Linus

#13 lore raw
Quoted 2 lines · Linus Torvalds

They did not have them all running at the same time. I think the original post said something like "up to 50 at a time".

actually, that was Ulrich's other test, which tests the serial starting of 100,000 threads.

the test i did started up 100,000 concurrent threads which shot up the load-average to a couple of thousands. [the default timeslice the parent has is enough to start more than 50,000 parallel threads a pop or so.]

Quoted 3 lines

Basically, the benchmark was how _fast_ thread creation is, not now many you can run at the same time. 100k threads at once is crazy, but you can do it now on 64-bit architectures if you really want to.

we did both, and on the dual-P4 testbox i have started and stopped 100,000 *parallel* threads in less than 2 seconds. Ie. starting up 100,000 threads without any throttling, waiting for all of them to start up, then killing them all. It needs roughly 1 GB of RAM to do this test on the default x86 kernel, it need roughly 500 MB of RAM to do this test with the IRQ-stacks patch applied.

with 2.5.31 this test would have taken roughly 15 minutes, on the same box, provided the NMI watchdog is turned off.

with 100,000 threads started up and idling silently the system is completely usable - all the critical for_each_task loops have been fixed. Obviously with 100,000 threads running at once there's some shortage in CPU power :-) [ I will perhaps try that once, at SCHED_BATCH priority, just for kicks. Not that it makes much sense - they will get a 3 seconds worth of timeslice every 3 days. ]

Ingo

#14 lore raw
In reply to Rik van Riel
Quoted 3 lines

So, where did you put those 800 MB of kernel stacks needed for 100,000 threads ?

I hope no one is going to run x86 boxes with 100,000 threads, but its nice to know we can do it. (just to have an upper limit)

If they want 100k threads they should start thinking about a 64bit box. Ive already tested 1 million kernel threads with 24GB and we make machines with more than 10 times that memory... (and no I cant think of any possible reason someone would want that many threads :)

Anton

#15 lore raw

Re: 100,000 threads? [was: [ANNOUNCE] Native POSIX Thread Library 0.1]

In reply to Rik van Riel
Quoted 2 lines · Rik van Riel

So, where did you put those 800 MB of kernel stacks needed for 100,000 threads ?

With the default split and kernel stack we can start up 94,000 threads on x86. With Ben's/Dave's patch we can have up to 188,000 threads. With a 2:2 GB VM split configured we can start 376,000 threads. If someone's that desperate then with a 1:3 split we can start up 564,000 threads.

Anton tested 1 million concurrent threads on one of his bigger PowerPC boxes, which started up in around 30 seconds. I think he saw a load average of around 200 thousand. [ie. the runqueue was probably a few hundred thousand entries long at times.]

Quoted 4 lines

If you used the standard 3:1 user/kernel split you'd be using all of ZONE_NORMAL for kernel stacks, but if you use a 2:2 split you'll end up with a lot less user space (bad if you want to have many threads in the same address space).

the extreme high-end of threading typically uses very controlled applications and very small user level stacks.

as to the question of why so many threads, the answer is because we can :) This, besides demonstrating some of the recent scalability advances, gives us the warm fuzzy feeling that things are right in this area. I mean, there are architectures where Linux could map a petabyte of RAM just fine, even though that might not be something we desperately need today.

Ingo

#16 lore raw

Re: 100,000 threads? [was: [ANNOUNCE] Native POSIX Thread Library 0.1]

Quoted 8 lines · Ingo Molnar

the extreme high-end of threading typically uses very controlled applications and very small user level stacks.

as to the question of why so many threads, the answer is because we can :) This, besides demonstrating some of the recent scalability advances, gives us the warm fuzzy feeling that things are right in this area. I mean, there are architectures where Linux could map a petabyte of RAM just fine, even though that might not be something we desperately need today.

I think testing at these high numbers is a good proof of scalability, although response and stability are also important. Before I went to NGPT I had a fair bit of problem with learning experiences after threads got beyond 200 or so.

Signature · 3 lines
bill davidsen <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.
#17 lore raw
In reply to Ulrich Drepper
Quoted 2 lines · Ulrich Drepper

We are pleased to announce the first publically available source release of a new POSIX thread library for Linux

[snip]

Quoted 1 line

called Native POSIX Thread Library, NPTL.

Great! Where does this leave NGPT though? I had assumed that this was going to be the next pthread implementation in glibc.

also:

-------- Original Message --------
Subject: glibc threading performance
Date: Mon, 16 Sep 2002 10:42:42 +0100
From: Padraig Brady <[email protected]>
To: Ingo Molnar <[email protected]>, Ulrich Drepper <[email protected]>

Hey guys,

I noticed you're looking at threading stuff lately, and was wondering about this thread:
http://sources.redhat.com/ml/bug-glibc/2001-12/msg00048.html

In summary wouldn't it be better to have a per process flag that was only set when pthread_create() is called. If the flag is not set, then you don't need to do locking. This locking seems to have huge overhead. For e.g. I patched uniq in textutils to use getc_unlocked() rather than getc() and got a 300% performance increase!

cheers,
Pádraig.

#18 lore raw
Quoted 2 lines · Padraig Brady

Great! Where does this leave NGPT though? I had assumed that this was going to be the next pthread implementation in glibc.

This was never the intention of the glibc people.

Robert Love

#19 lore raw
Quoted 6 lines · Robert Love
Quoted 2 lines · Padraig Brady

Great! Where does this leave NGPT though? I had assumed that this was going to be the next pthread implementation in glibc.

This was never the intention of the glibc people.

Was there some shortcoming in NGPT? Clearly someone provided a good bit of funding for this, so there must have been motivation beyond NIH or funding someone's honors thesis.

I also expected NGPT to be the next step, not a library which requires a kernel which is unlikely to be stable for 18 months.

Signature · 3 lines
bill davidsen <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.
#20 lore raw
In reply to Ulrich Drepper
Quoted 7 lines · Ulrich Drepper

...
Unless major flaws in the design are found this code is intended to become the standard POSIX thread library on Linux system and it will be included in the GNU C library distribution.
...
- - requires a kernel with the threading capabilities of Linux 2.5.36.
...

My personal estimation is that Debian will support kernel 2.4 in it's stable distribution until 2006 or 2007 (this is based on the experience that Debian usually supports two stable kernel series and the time between stable releases of Debian is > 1 year). What is the proposed way for distributions to deal with this?

cu
Adrian

Signature · 3 lines
You only think this is a free country. Like the US the UK spends a lot of
time explaining its a free country because its a police state.
								Alan Cox
#21 lore raw
Quoted 7 lines · Adrian Bunk
Quoted 6 lines

Unless major flaws in the design are found this code is intended to become the standard POSIX thread library on Linux system and it will be included in the GNU C library distribution.
...
- - requires a kernel with the threading capabilities of Linux 2.5.36.
...

Quoted 5 lines

My personal estimation is that Debian will support kernel 2.4 in it's stable distribution until 2006 or 2007 (this is based on the experience that Debian usually supports two stable kernel series and the time between stable releases of Debian is > 1 year). What is the proposed way for distributions to deal with this?

Ulrich will give a fuller reply i guess, but the new threading code in 2.5 does not disable (or in any way obsolete) the old glibc threading library. So by doing boot-time kernel version checks glibc can decide whether it wants to provide the new library or the old library.

Ingo

#22 lore raw
In reply to Adrian Bunk

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoted 5 lines · Adrian Bunk

My personal estimation is that Debian will support kernel 2.4 in it's stable distribution until 2006 or 2007 (this is based on the experience that Debian usually supports two stable kernel series and the time between stable releases of Debian is > 1 year). What is the proposed way for distributions to deal with this?

Two ways:

- - continue to use the old code

- - backport the required functionality

Note that not all the changes Ingo made have to be ported back to 2.4. Only those required for correct execution, not the optimizations.

Whether Marcello is interested in this I cannot say, I doubt it though.
But this does not mean you cannot have such a kernel in Debian.

- -- - ---------------. ,-. 1325 Chesapeake Terrace
Ulrich Drepper \ ,-------------------' \ Sunnyvale, CA 94089 USA
Red Hat --' drepper at redhat.com ------------------------
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.7 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQE9i3Fb2ijCOnn/RHQRAlC+AJ9kXWMdkfuORtodijTXQ+Hnah0ZYQCfZkOT Axzw/z1VEFVXIQdZ4d8PLe4=
=ptvg
-----END PGP SIGNATURE-----

#23 lore raw
Quoted 11 lines · On 2002.09.20 Ulrich Drepper wrote:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoted 5 lines · Adrian Bunk

My personal estimation is that Debian will support kernel 2.4 in it's stable distribution until 2006 or 2007 (this is based on the experience that Debian usually supports two stable kernel series and the time between stable releases of Debian is > 1 year). What is the proposed way for distributions to deal with this?

Quoted 6 lines

Two ways:

- - continue to use the old code

- - backport the required functionality

Could you post a list of requirements ? For example:
- kernel: futexes, per_cpu_areas
- toolchain: binutils version + RH-patches, gcc version
- glibc: 2.2.xxxx
etc...

Perhaps it is not so difficult, for example futexes are in -aa for 2.4, Mandrake has gcc-3.2, etc...

Are you pushing hard for the infrastructure you need to get in standard source trees (ie, changes to gcc, binutils...) ??

Thanks.

Signature · 4 lines
J.A. Magallon <[email protected]>      \                 Software is like sex:
werewolf.able.es                         \           It's better when it's free
Mandrake Linux release 9.0 (Cooker) for i586
Linux 2.4.20-pre7-jam0 (gcc 3.2 (Mandrake Linux 9.0 3.2-1mdk))
#24 lore raw

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoted 2 lines · J.A. Magallon

Could you post a list of requirements ? For example:
- kernel: futexes, per_cpu_areas

There's a lot more. The signal handling, the exec handling, the exit handling, the clone extensions.

Quoted 1 line

- toolchain: binutils version + RH-patches, gcc version

No RH patches. Don't spread misinformation.

All the changes needed for kernel, glibc, and the tools are in the official sources trees. It's just that nobody else ships those versions or versions with the necessary features backported.

Quoted 1 line

- glibc: 2.2.xxxx

The announcement said it clearly: you need at least the 2.3 prerelease of as yesterday. Again, all in the public archive.

- -- - ---------------. ,-. 1325 Chesapeake Terrace
Ulrich Drepper \ ,-------------------' \ Sunnyvale, CA 94089 USA
Red Hat --' drepper at redhat.com ------------------------
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.7 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQE9i7BI2ijCOnn/RHQRAn0nAKCF4cZO9K2/vhNbCuawvk0ecM2SCQCeOKE9 Qg19wkleGKXFmr3plY1dbho=
=oWVM
-----END PGP SIGNATURE-----

#25 lore raw
Quoted 5 lines · On 2002.09.21 Ulrich Drepper wrote:

-----BEGIN PGP SIGNED MESSAGE-----

Quoted 1 line

- toolchain: binutils version + RH-patches, gcc version

No RH patches. Don't spread misinformation.

Oh, sorry, no misinformation intended. As I read previous posts I understood that there were things developed still not in standard trees. Sometimes I see in Mandrake changelogs 'patch-X, from RH', and then 'patch-X removed, merged upstream'

/by

Signature · 4 lines
J.A. Magallon <[email protected]>      \                 Software is like sex:
werewolf.able.es                         \           It's better when it's free
Mandrake Linux release 9.0 (Cooker) for i586
Linux 2.4.20-pre7-jam0 (gcc 3.2 (Mandrake Linux 9.0 3.2-1mdk))
#26 lore raw
In reply to Ulrich Drepper
Quoted 4 lines · Ulrich Drepper

It is not generally accepted that a 1-on-1 model is superior but our tests showed the viability of this approach and by comparing it with the overhead added by existing M-on-N implementations we became convinced that 1-on-1 is the right approach.

Maybe not but...

You might like to try a context switching/thread wakeup performance measurement against FreeBSD's libc_r. I'd imagine that it's difficult to beat a system like that since they keep all of that stuff in userspace since it's just 2 context switches and a call to their thread-kernel.

I'm curious as to the rough numbers you got doing the 1:1 and M:N comparison.

bill

#27 lore raw
Quoted 4 lines · Bill Huey

You might like to try a context switching/thread wakeup performance measurement against FreeBSD's libc_r. I'd imagine that it's difficult to beat a system like that since they keep all of that stuff in userspace since it's just 2 context switches and a call to their thread-kernel.

our kernel thread context switch latency is below 1 usec on a typical P4 box, so our NPT library should compare pretty favorably even in such benchmarks. We get from the pthread_create() call to the first user instruction of the specified thread-function code in less than 2 usecs, and we get from pthread_exit() to the thread that does the pthread_join() in less than 2 usecs as well - all of these operations are done via a single system-call and a single context switch.

also consider the fact that the true cost of M:N threading does not show up with just one or two threads running. The true cost comes when thousands of threads are running, each of them doing nontrivial work that matters, ie. IO. The true cost of M:N shows up when threading is actually used for what it's intended to be used :-) And basically nothing offloads work to threads for them to just do userspace synchronization - real, useful work always involves some sort of IO and kernel calls. At which point M:N loses out badly.

M:N's big mistake is that it concentrates on what matters the least:
user<->user context switches. Nothing really wants to do that. And if it does, it's contended on some userspace locking object, at which point it doesnt really matter whether the cost of switching is 1 usec or 0.5 usecs, the main application cost is the lost paralellism and increased cache trashing due to the serialization - independently of what kind of threading abstraction is used.

and since our NPT library uses futexes for *all* userspace synchronization primitives (including internal glibc locks), all uncontended synchronization is done purely in user-space. [and for the contended case we *want* to switch into the kernel.]

Ingo

#28 lore raw
Quoted 7 lines · Ingo Molnar

our kernel thread context switch latency is below 1 usec on a typical P4 box, so our NPT library should compare pretty favorably even in such benchmarks. We get from the pthread_create() call to the first user instruction of the specified thread-function code in less than 2 usecs, and we get from pthread_exit() to the thread that does the pthread_join() in less than 2 usecs as well - all of these operations are done via a single system-call and a single context switch.

That's outstanding...

Quoted 8 lines

also consider the fact that the true cost of M:N threading does not show up with just one or two threads running. The true cost comes when thousands of threads are running, each of them doing nontrivial work that matters, ie. IO. The true cost of M:N shows up when threading is actually used for what it's intended to be used :-) And basically nothing offloads work to threads for them to just do userspace synchronization - real, useful work always involves some sort of IO and kernel calls. At which point M:N loses out badly.

It can. Certainly, if IO upcall overhead is greater than just running the thread that's blocked inside the kernel, then yes. Not sure how this is all going to play out...

Quoted 7 lines

M:N's big mistake is that it concentrates on what matters the least:
user<->user context switches. Nothing really wants to do that. And if it does, it's contended on some userspace locking object, at which point it doesnt really matter whether the cost of switching is 1 usec or 0.5 usecs, the main application cost is the lost paralellism and increased cache trashing due to the serialization - independently of what kind of threading abstraction is used.

Yeah, that's not a new argument and is a solid criticism...

Hmmm, random thoughts... This is probably outside the scope of lkml, but...

I'm trying to think up a possible problem with how the JVM does threading that might be able to exploit this kind of situation...Hmm, there's locks on the method dictionary, but that's not something that's generally changing a lot of the time... I'll give it some thought.

The JVM needs a couple of pretty critical things that are a bit off from the normal Posix threading standard. One of them is very fast thread suspension for both individual threads and the all threads accept the currently running one...

In the Solaris threads implementation of JVM/HotSpot it has two methods of getting a ucontext for doing GC and wierd exception/signal handling via safepoints (a JIT compiler goody) and it would be nice to have...

1) Slow Version. Throw a SIGUSR1 at a thread and read/write the ucontext on the signal frame itself.

2) Fast Version. The thread state and ucontext is examined directly to determine the validity of the stored thread context, whether it's blocked on a syscall (ignore it) or was doing a CPU intensive operation (use it).

That ucontext is used for various things:

a) Proper GC so that registers that might contain valid references are taken into account properly to maintain the correctness of the mark/sweep algorithms.

b) The thread's program counter value is altered to deal with safepoints.

(2) above being the most desireable since it's a kind of fast path for

	(a) and (b).

So userspace exposure to the thread's ucontext would be a good thing. I'm not sure how this is dealt within the current implementation of what you folks are doing at this moment.

Quoted 3 lines

primitives (including internal glibc locks), all uncontended synchronization is done purely in user-space. [and for the contended case we *want* to switch into the kernel.]

If there's any thing on this planet that's going to stress a threading system, it's going to be the JVM. I'll give what you've said a some thought. My bias has been to FreeBSD's KSE project for the most part over this last threading/development run.

/me thinks...

bill

#29 lore raw
Quoted 4 lines · Bill Huey

The JVM needs a couple of pretty critical things that are a bit off from the normal Posix threading standard. One of them is very fast thread suspension for both individual threads and the all threads accept the currently running one...

the user contexts for active but preempted threads are stored in the kernel stack. To support GC safepoints we need fast access to the current state of every not voluntarily preempted thread. This is admittedly easier if threads are abstraced in user-space [in which case the context is stored in user-space], but the question is, what is more important, an occasional pass of garbage collection, or the cost of doing IO?

until then it can be done via sending SIGSTOP/SIGCONT to the process PID from the garbage collection thread, which should stop all threads pretty efficiently in 2.5.35+ kernels. Then all threads that are not voluntarily sleeping can be fixed up via ptrace calls.

and it can be further improved by tracking preempted user contexts in the scheduler and giving fast access to them via a syscall. (all voluntarily sleeping contexts can properly prepare their suspension state in userspace.) So it's possible to do it efficiently.

how frequently does the GC thread run?

Ingo

#30 lore raw
Quoted 6 lines · Ingo Molnar

the user contexts for active but preempted threads are stored in the kernel stack. To support GC safepoints we need fast access to the current state of every not voluntarily preempted thread. This is admittedly easier if threads are abstraced in user-space [in which case the context is stored in user-space], but the question is, what is more important, an occasional pass of garbage collection, or the cost of doing IO?

The GC is generational and incremental, so it must deal with a lot of short term objects that need to be collected. GC performance is a sore point in the JVM (language runtimes in general) and having slow access to this is potentially crippling for high load machines. The HotSpot/JVM is a bit overzealous with safepoints which opens this area to optimization, but the problem exists now.

Quoted 4 lines

until then it can be done via sending SIGSTOP/SIGCONT to the process PID from the garbage collection thread, which should stop all threads pretty efficiently in 2.5.35+ kernels. Then all threads that are not voluntarily sleeping can be fixed up via ptrace calls.

It's better to have an explict pthread_suspend_[thread,all]() function since this kind of thing is becoming more and more common in thread heavy language runtimes. The Posix thread spec was build without regard to this and it's definitely become an important issues these days.

Quoted 6 lines

and it can be further improved by tracking preempted user contexts in the scheduler and giving fast access to them via a syscall. (all voluntarily sleeping contexts can properly prepare their suspension state in userspace.) So it's possible to do it efficiently.

how frequently does the GC thread run?

Don't remember off hand, but it's like to be several times a second which is often enough to be a problem especially on large systems with high load.

The JVM with incremental GC is being targetted for media oriented tasks using the new NIO, 3d library, etc... slowness in safepoints would cripple it for these tasks. It's a critical item and not easily address by the current 1:1 model.

bill

#31 lore raw
Quoted 1 line · Bill Huey

It's better to have an explict pthread_suspend_[thread,all]() function

could this be implemented by having a gc thread in a unique process group and then suspending the jvm process group?

-dean

#32 lore raw
Quoted 4 lines · dean gaudet
Quoted 1 line

It's better to have an explict pthread_suspend_[thread,all]() function

could this be implemented by having a gc thread in a unique process group and then suspending the jvm process group?

Suspending how ? via signal ?

Possibly, but having an explicit syscall() call is important since interrupts are also suspended under that condition, pthread_cond_timedwait(), etc... It really needs to be suspended in a way that's different than the SIGSOMETHING mechanism. I was fixing bugs in libc_r, so I know the issues to a certain degree and bad logic those particular corner cases was screwing me up.

bill

#33 lore raw
Quoted 7 lines · Bill Huey
Quoted 4 lines · dean gaudet
Quoted 1 line

It's better to have an explict pthread_suspend_[thread,all]() function

could this be implemented by having a gc thread in a unique process group and then suspending the jvm process group?

Suspending how ? via signal ?

yeah SIGSTOP to the jvm process group.

Quoted 5 lines

Possibly, but having an explicit syscall() call is important since interrupts are also suspended under that condition, pthread_cond_timedwait(), etc... It really needs to be suspended in a way that's different than the SIGSOMETHING mechanism. I was fixing bugs in libc_r, so I know the issues to a certain degree and bad logic those particular corner cases was screwing me up.

SIGSTOP is different from other signals because it will stop the whole process group from continuing. i am completely aware of how much of a pain it is to actually trap signals and do something (for apache 2.0's design i outlawed the use of signals because of the pains of getting things working in 1.3.x :).

doesn't the hotspot GC work something like this:

- stop all threads
- go read each thread's $pc, and find its nearest "safety point"
- go overwrite that safety point (YUCK SELF MODIFYING CODE!! :) with something which will stop the thread
- start the threads and wait for them all to get to their safety points
- perform gc
- undo the above mess

the only part of that which looks challenging with kernel threads is the $pc reading part... ptrace will certainly get it for you, but that's a lot of syscall overhead.

or am i missing something?

-dean

#34 lore raw
Quoted 5 lines · dean gaudet

SIGSTOP is different from other signals because it will stop the whole process group from continuing. i am completely aware of how much of a pain it is to actually trap signals and do something (for apache 2.0's design i outlawed the use of signals because of the pains of getting things working in 1.3.x :).

There's definitely a need for a pthread_suspend_something() call...

Quoted 9 lines

doesn't the hotspot GC work something like this:

- stop all threads
- go read each thread's $pc, and find its nearest "safety point"
- go overwrite that safety point (YUCK SELF MODIFYING CODE!! :) with something which will stop the thread
- start the threads and wait for them all to get to their safety points
- perform gc
- undo the above mess

+ read the entire ucontext for EAX, etc... so that it can be used for GC roots. It could be allocating something in an executing method block that hasn't hit stack or any kind of variable storage known to the GC.

Quoted 3 lines

the only part of that which looks challenging with kernel threads is the $pc reading part... ptrace will certainly get it for you, but that's a lot of syscall overhead.

And the entire ucontext.

Quoted 1 line

or am i missing something?

The ucontext. ;)

bill

#35 lore raw
Quoted 10 lines · Bill Huey
Quoted 9 lines

doesn't the hotspot GC work something like this:

- stop all threads
- go read each thread's $pc, and find its nearest "safety point"
- go overwrite that safety point (YUCK SELF MODIFYING CODE!! :) with something which will stop the thread
- start the threads and wait for them all to get to their safety points
- perform gc
- undo the above mess

Quoted 3 lines

+ read the entire ucontext for EAX, etc... so that it can be used for GC roots. It could be allocating something in an executing method block that hasn't hit stack or any kind of variable storage known to the GC.

PTRACE_GETREGS. Yeah, it's overhead, see my previous mails about various levels of kernel features of how to do it potentially cheaper. Not like the above process is particularly fast.

One more method to speed it up: to amortize the kernel entry overhead we could introduce a new PTRACE_GETREGS_GROUP to get a full array of user contexts from all group member threads, via a single system-call.

Quoted 5 lines
Quoted 3 lines

the only part of that which looks challenging with kernel threads is the $pc reading part... ptrace will certainly get it for you, but that's a lot of syscall overhead.

And the entire ucontext.

PTRACE_GETREGS gets you the instruction pointer and all general purpose registers, eax and the rest.

Ingo

#36 lore raw
In reply to Bill Huey (Hui)
Quoted 9 lines · Bill Huey
Quoted 1 line

how frequently does the GC thread run?

Don't remember off hand, but it's like to be several times a second which is often enough to be a problem especially on large systems with high load.

The JVM with incremental GC is being targetted for media oriented tasks using the new NIO, 3d library, etc... slowness in safepoints would cripple it for these tasks. It's a critical item and not easily address by the current 1:1 model.

Also throwing a signal to get the ucontext is pretty a expensive way of getting it. But you folks know this already. Solaris threading has this via a some special libraries. For large number of actively running threads, say, executing in a middle of a method block it is potentially a huge problem for scalability.

Again, it's a critical issue from what I see of this.

bill

#37 lore raw
Quoted 2 lines · Bill Huey

Also throwing a signal to get the ucontext is pretty a expensive way of getting it. But you folks know this already. [...]

as i've mentioned in the previous mail, 2.5.35+ kernels have a very fast SIGSTOP/SIGCONT implementation, which change was done as part of this project - a few orders faster than throwing/catching SIGUSR1 to every single thread for example.

so right now we first need to get some results back about how big the GC problem is with the new SIGSTOP/SIGCONT implementation. If it's still not fast enough then we still have a number of options.

Ingo

#38 lore raw
Quoted 4 lines · Ingo Molnar

as i've mentioned in the previous mail, 2.5.35+ kernels have a very fast SIGSTOP/SIGCONT implementation, which change was done as part of this project - a few orders faster than throwing/catching SIGUSR1 to every single thread for example.

That's good, but having an explict API for suspending threads is very useful, since it can greatly simplify the already complicated signal handling in highly threaded systems. It's something that your group should seriously consider, since I expect some explicit thread suspension call to be implemented in Posix threading standard, via their committee. Mainly, because of the advent of heavily threaded language runtimes as standard programming staple.

It's a good thing to have regardless.

Quoted 3 lines

so right now we first need to get some results back about how big the GC problem is with the new SIGSTOP/SIGCONT implementation. If it's still not fast enough then we still have a number of options.

I'm running out of things to say. ;)

bill

#39 lore raw
In reply to Bill Huey (Hui)
Quoted 4 lines · Bill Huey

The JVM with incremental GC is being targetted for media oriented tasks using the new NIO, 3d library, etc... slowness in safepoints would cripple it for these tasks. It's a critical item and not easily address by the current 1:1 model.

actually, in the previous mail i've outlined a sensible way to help safepoints in the kernel, for the case of the 1:1 model. I'd not call that 'not easily addressed' :-)

there's an even more advanced way to expose preempted user contexts in the 1:1 model: by putting most of the the register info (which is now dumped into the kernel stack) into a page that is also mapped into user-space. This too introduces (constant) syscall entry/exit overhead, but can be done if justified.

Ingo

#40 lore raw
Quoted 9 lines · Ingo Molnar

actually, in the previous mail i've outlined a sensible way to help safepoints in the kernel, for the case of the 1:1 model. I'd not call that 'not easily addressed' :-)

there's an even more advanced way to expose preempted user contexts in the 1:1 model: by putting most of the the register info (which is now dumped into the kernel stack) into a page that is also mapped into user-space. This too introduces (constant) syscall entry/exit overhead, but can be done if justified.

Maybe mmapping a special device into memory ? /proc/satanic_procID_666* ???

A method needs to be considered, definitely. Getting some Sun/Blackdown folks on this thread wouldn't be bad either.

I'm not exactly sure what Solaris does in this case, so it might be worth investigating it so that this is conceptually regular across various Unix variants to a certain degree.

It's also essential to have the run states along with the ucontext to determine the validity of ucontext backing the thread. Obviously, being blocked in the kernel on a IO request isn't going to result in any thing useable GC. And that's because libc library calls are external symbols and don't preserve registers across calls.

Also, permission to the PTRACE* interface shouldn't conflict with debuggers... Complete multithreaded debugging is important of course. I would expect GDB to be modified so that it can get and examine those register values and thread run states too.

Uh, the JVM also has a habit of also checksumming the register contents over a window of time to see if a thread is actively running through its internal debugging facilities... It shouldn't have to lock or suspend thread execution to examine it. Now that I think of it, syscall overlay technique isn't going work, since nothing of interest to the GC is going to be present in the ucontext, so the above suggest of exporting the ucontext at syscall points isn't going to work.

More to come...

bill

#41 lore raw
In reply to Bill Huey (Hui)
Quoted 7 lines · Bill Huey

Don't remember off hand, but it's like to be several times a second which is often enough to be a problem especially on large systems with high load.

The JVM with incremental GC is being targetted for media oriented tasks using the new NIO, 3d library, etc... slowness in safepoints would cripple it for these tasks. It's a critical item and not easily address by the current 1:1 model.

Could you comment on how whell this works (or not) with linuxthreads, Solaris, and NGPT? I realize you probably haven't had time to look at NPTL yet. If an N:M model is really better for your application you might be able to just run NGPT.

Since preempt threads seem a problem, cound a dedicated machine run w/o preempt? I assume when you say "high load" that you would be talking a server, where performance is critical.

Signature · 3 lines
bill davidsen <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.
#42 lore raw
Quoted 16 lines · Bill Davidsen
Quoted 7 lines · Bill Huey

Don't remember off hand, but it's like to be several times a second which is often enough to be a problem especially on large systems with high load.

The JVM with incremental GC is being targetted for media oriented tasks using the new NIO, 3d library, etc... slowness in safepoints would cripple it for these tasks. It's a critical item and not easily address by the current 1:1 model.

Could you comment on how whell this works (or not) with linuxthreads, Solaris, and NGPT? I realize you probably haven't had time to look at NPTL yet. If an N:M model is really better for your application you might be able to just run NGPT.

Quoted 5 lines

Since preempt threads seem a problem, cound a dedicated machine run w/o preempt? I assume when you say "high load" that you would be talking a server, where performance is critical.

From 10,000 feet out I have one comment. If the VM has safe points. It sounds

like the problem is more that the safepoints don't provide the register dumps more than anything else.

They are talking about an incremental GC routine so it does not need to stop all threads simultaneously. Threads only need to be stopped when the GC is gather a root set. This is what the safe points are for right? And it does not need to be 100% accurate in finding all of the garbage. The collector just needs to not make mistakes in the other direction.

I fail to see why:

/* This is a safe point ... */
if (needs to be suspended) {
save_all_registers_on_the_stack()
flag_gc_thread()
wait_until_gc_thread_has_what_it_needs()
}

Needs kernel support.

Eric

#43 lore raw
Quoted 10 lines · Eric W. Biederman

I fail to see why:

/* This is a safe point ... */
if (needs to be suspended) {
save_all_registers_on_the_stack()
flag_gc_thread()
wait_until_gc_thread_has_what_it_needs()
}

Needs kernel support.

given that the existing code uses self-modifying-code for the safe-points i'm guessing there are so many safe-points that the above if statement would be excessive overhead (and the save/flag/wait stuff would probably cause a huge amount of code bloat -- but could probably be a subroutine).

there was some really interesting GC work i heard about years ago where the compiler generated GC code along-side the normal executable code. the GC code understood the structure of the function and could make much better choices of GC targets than a generic routine could. when GC needs to occur, a walk up the stack in each thread executing the routine-specific GC stubs would be performed. (given just the stack frames you can index into a lookup table for the GC stubs... so there's no overhead when GC isn't occuring.) i don't have a reference handy though.

anyhow, this is probably getting off-topic :)

-dean

#44 lore raw
Quoted 4 lines · dean gaudet

given that the existing code uses self-modifying-code for the safe-points i'm guessing there are so many safe-points that the above if statement would be excessive overhead (and the save/flag/wait stuff would probably cause a huge amount of code bloat -- but could probably be a subroutine).

It might be worth reminding people here that you cannot implement self modifying code safely on x86 SMP systems without a lot of care. Several common chips take a long walk off a short bus when the code they are currently executing is modified as they execute it. Not just because of write atomicity (which could be fixed) but because of hardware errata.

So if you are patching something that another cpu could be executing at the same time - you already lost.

#45 lore raw
In reply to Eric W. Biederman
Quoted 5 lines · Eric W. Biederman

They are talking about an incremental GC routine so it does not need to stop all threads simultaneously. Threads only need to be stopped when the GC is gather a root set. This is what the safe points are for right? And it does not need to be 100% accurate in finding all of the garbage. The collector just needs to not make mistakes in the other direction.

There's a mixture of GC algorithms in HotSpot including generational and I believe a traditional mark/sweep. GC isn't my expertise per se.

Think, you have a compiled code block and you suspend/interrupt threads when you either start hitting the stack yellow guard or by a periodic GC thread...

That can happen anytime, so you can't just expect things to drop onto a regular boundary in the compiled code block. It's for that reason that you have to some kind of OS level threading support to get the ucontext.

bill

#46 lore raw
Quoted 11 lines · Bill Huey (Hui)
Quoted 2 lines · Eric W. Biederman

They are talking about an incremental GC routine so it does not need to stop all threads simultaneously. Threads only need to be stopped when the GC is

gather

Quoted 3 lines

a root set. This is what the safe points are for right? And it does not need to be 100% accurate in finding all of the garbage. The collector just needs to not make mistakes in the other direction.

There's a mixture of GC algorithms in HotSpot including generational and I believe a traditional mark/sweep. GC isn't my expertise per se.

If they have any sense they also have an incremental GC algorithm. That the GC thread can sit around all day and executing. If they are actually using a stop and collect algorithm there are real issues. Though I would love to see the Java guys justify a copy collector...

Quoted 5 lines

Think, you have a compiled code block and you suspend/interrupt threads when you either start hitting the stack yellow guard or by a periodic GC thread...

That can happen anytime, so you can't just expect things to drop onto a regular boundary in the compiled code block.

Agreed, but what was this talk earlier about safe points?

Quoted 2 lines

It's for that reason that
you have to some kind of OS level threading support to get the ucontext.

I don't quite follow the need and I'm not certain you do either. A full GC pass is very expensive. So saving a threads context in user space should not be a big deal. It is very minor compared to the rest of the work going on. Especially in a language like java where practically everything lives on the heap.

The thing that sounds sensible to me is that before a threads makes a blocking call it can be certain to save relevant bits of information to the stack. But x86 is easy what to do with the pointer heavy architectures where pushing all of the registers onto the stack starts getting expensive is an entirely different question.

But beyond that. The most sensible algorithm I can see is a generational incremental collector where each thread has it's own local heap, and does it's own local garbage collection. And only the boundary where the local heap meets the global heap needs to collected by the collector for all threads. This preserves a lot of cache locality as well as circumventing the whole ucontext issue.

If getting the registers is really a bottle neck in the garbage collector I suspect it can probably share some generic primitives with user mode linux.

If support really needs to happen I suspect this case is close enough to what that user mode linux is doing that someone should look at how the same mechanism to get the register state can be shared.

Eric

#47 lore raw
Quoted 4 lines · Eric W. Biederman

If they have any sense they also have an incremental GC algorithm. That the GC thread can sit around all day and executing. If they are actually using a stop and collect algorithm there are real issues. Though I would love to see the Java guys justify a copy collector...

They have that and other crazy things. Thread local storage facilities, etc...

Quoted 2 lines
Quoted 1 line

regular boundary in the compiled code block.

Agreed, but what was this talk earlier about safe points?

It's needed to deal with exceptions and GC.

Quoted 5 lines
Quoted 2 lines

It's for that reason that
you have to some kind of OS level threading support to get the ucontext.

I don't quite follow the need and I'm not certain you do either. A full GC pass is very expensive. So saving a threads context in user space

But you haven't read the code and the supporting white papers for this JIT compiler otherwise you wouldn't be whining about this. HotSpot is no whimp when it comes to these issues. Compilers execute code, code is stored some where and does memory allocation. Geez.

Quoted 3 lines

should not be a big deal. It is very minor compared to the rest of the work going on. Especially in a language like java where practically everything lives on the heap.

Then you need to look at the compilation architecture of HotSpot. It's pretty different than your picture of it and is gross oversimplification. Hell, I don't know what much of it does since it's so freaking large.

Quoted 5 lines

The thing that sounds sensible to me is that before a threads makes a blocking call it can be certain to save relevant bits of information to the stack. But x86 is easy what to do with the pointer heavy architectures where pushing all of the registers onto the stack starts getting expensive is an entirely different question.

Dude, you have not been reading this thread... Nothing valuable is at syscall time per thread, those are external symbol calls that contain nothing of value to the GC. It's allowed to execute at that point so any allocated chunk of memory is going to be properly shoved some where known to the GC.

The stuff that's of value to maintain the correctness of this is within executing code blocks in the method dictionary... move the program counter to a specific place, funny execution stuff that I haven't looked at yet since I was pretty happy about getting the threading glue to the OS working, etc...

Quoted 6 lines

But beyond that. The most sensible algorithm I can see is a generational incremental collector where each thread has it's own local heap, and does it's own local garbage collection. And only the boundary where the local heap meets the global heap needs to collected by the collector for all threads. This preserves a lot of cache locality as well as circumventing the whole ucontext issue.

Which HotSpot has...Read the papers... Thread local storage exists.

This isn't a just a GC library isolated from a compiler. This a very sophisticated compiler with a heavy threading infrastructure and you have to take into account various kinds of interaction with the GC. It is non-trivial stuff.

Quoted 3 lines

If getting the registers is really a bottle neck in the garbage collector I suspect it can probably share some generic primitives with user mode linux.

It can be if you have to send a single to each thread to get the ucontext.

Quoted 4 lines

If support really needs to happen I suspect this case is close enough to what that user mode linux is doing that someone should look at how the same mechanism to get the register state can be shared.

With a non-PTRACE interface to those ucontexts...

bill

#48 lore raw
Quoted 1 line · Bill Huey (Hui)

Which HotSpot has...Read the papers... Thread local storage exists.

I'd love to. Do you have a URL. I didn't see in my quick look.

Eric

#49 lore raw
In reply to Bill Davidsen
Quoted 4 lines · Bill Davidsen

Could you comment on how whell this works (or not) with linuxthreads, Solaris, and NGPT? I realize you probably haven't had time to look at NPTL yet. If an N:M model is really better for your application you might be able to just run NGPT.

I can't. I'm in a different OS community, FreeBSD, and I deal with issues related to threading systems there. There's many variables that could be at play for various performance categories.

Quoted 3 lines

Since preempt threads seem a problem, cound a dedicated machine run w/o preempt? I assume when you say "high load" that you would be talking a server, where performance is critical.

The JVM itself can has a habit of really stretching the amount of resources available in many areas and fringe logic in commonly used systems. I can't really say what the problems are until the Blackdown folks start integrating the new threading model and then start testing it.

However, there is a mutex fast path in the code itself that can be optionally used in place of the the OS back version. They felt it was significant to do the work for that for some reason, so I'm just going to assume that this is important until otherwise noted.

bill

#50 lore raw
In reply to Ulrich Drepper

Great, but how about using code similar to the following rather than hand-coded asm operations?

extern struct pthread __pt_current_struct asm("%gs:0"); #define __pt_current (&__pt_current_struct)

#define THREAD_GETMEM(descr, member) (__pt_current->member) #define THREAD_SETMEM(descr, member, value) ((__pt_current->member) = value)
#define THREAD_MASKMEM(descr, member, mask) ((__pt_current->member) &= mask)
...

Of course, it doesn't work if you try to take the address of a member.

#51 lore raw
Quoted 6 lines · Luca Barbieri

Great, but how about using code similar to the following rather than hand-coded asm operations?

extern struct pthread __pt_current_struct asm("%gs:0"); #define __pt_current (&__pt_current_struct)

Quoted 6 lines

#define THREAD_GETMEM(descr, member) (__pt_current->member) #define THREAD_SETMEM(descr, member, value) ((__pt_current->member) = value)
#define THREAD_MASKMEM(descr, member, mask) ((__pt_current->member) &= mask)
...

it's a good idea i think. Ulrich has an obsession with writing code in assembly though :-)

Ingo

#52 lore raw
Quoted 7 lines · Luca Barbieri
Quoted 6 lines

Great, but how about using code similar to the following rather than hand-coded asm operations?

extern struct pthread __pt_current_struct asm("%gs:0"); #define __pt_current (&__pt_current_struct)

Try that under -fpic and you will see the problem.

#53 lore raw
Quoted 1 line

Try that under -fpic and you will see the problem.

Unfortunately it tries to get it using the GOT and I can't find any practical workaround, so ignore my broken suggestion.

#54 lore raw
In reply to Ulrich Drepper
Quoted 6 lines · Ulrich Drepper

We are pleased to announce the first publically available source release of a new POSIX thread library for Linux. As part of the continuous effort to improve Linux's capabilities as a client, server, and computing platform Red Hat sponsored the development of this completely new implementation of a POSIX thread library, called Native POSIX Thread Library, NPTL.

Is this related to the thread library work that IBM was doing or was this independently developed?

Thanks,

Jim

#55 lore raw
Quoted 9 lines · On Fri, 20 Sep 2002 [email protected] wrote:
Quoted 6 lines

We are pleased to announce the first publically available source release of a new POSIX thread library for Linux. As part of the continuous effort to improve Linux's capabilities as a client, server, and computing platform Red Hat sponsored the development of this completely new implementation of a POSIX thread library, called Native POSIX Thread Library, NPTL.

Is this related to the thread library work that IBM was doing or was this independently developed?

independently developed.

Ingo

#56 lore raw
Quoted 6 lines · On Fri, 20 Sep 2002 18:42:48 +0200 (CEST) Ingo Molnar <[email protected]> wrote:
Quoted 2 lines · On Fri, 20 Sep 2002 [email protected] wrote:

Is this related to the thread library work that IBM was doing or was this independently developed?

independently developed.

And, ironically, using the futex implementation developed on IBM time 8).

Of course, the time I spent on futexes would have been completely wasted without the 95% done by Ingo and Uli to reach normal user programs and address the other scalability problems.

Thanks guys! IOU each a beer or local equiv...
Rusty.

Signature · 2 lines
   there are those who do and those who hang on and you don't see too
   many doers quoting their contemporaries.  -- Larry McVoy
#57 lore raw
Quoted 6 lines · Rusty Russell
Quoted 4 lines
Quoted 2 lines

Is this related to the thread library work that IBM was doing or was this independently developed?

independently developed.

And, ironically, using the futex implementation developed on IBM time 8).

you are right, futexes are really important for all the userspace locking primitives and thread-joining. And like basically all core kernel code, futexes were a collaborative effort as well:

 *  Thanks to Ben LaHaise for yelling "hashed waitqueues" loudly
 *  enough at me, Linus for the original (flawed) idea, Matthew
 *  Kirkwood for proof-of-concept implementation.

there are so many prerequisites to this that it's impossible to list them all. What i meant above were the specific patches developed for recent 2.5 kernels, and the library itself.

Ingo

#58 lore raw

In message <[email protected]> you write:

Quoted 9 lines
Quoted 1 line

And, ironically, using the futex implementation developed on IBM time 8).

you are right, futexes are really important for all the userspace locking primitives and thread-joining. And like basically all core kernel code, futexes were a collaborative effort as well:

 *  Thanks to Ben LaHaise for yelling "hashed waitqueues" loudly
 *  enough at me, Linus for the original (flawed) idea, Matthew
 *  Kirkwood for proof-of-concept implementation.

And yourself, Robert Love, Paul Mackerras and Hubertus Franke all contributed to futexes directly, too. I wasn't complaining about credit, I just found the IBM involvement worth noting (in case someone thought we were onesided).

Quoted 2 lines

there are so many prerequisites to this that it's impossible to list them all.

True here, but in general: almost all the order-of-magnitude scalability jumps in 2.5 can be traced back to you or Andrew Morton. I wouldn't want a casual reader to miss that fact 8)

Cheers,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

#59 lore raw
In reply to Ulrich Drepper
Quoted 10 lines · Ulrich Drepper

We are pleased to announce the first publically available source release of a new POSIX thread library for Linux. As part of the continuous effort to improve Linux's capabilities as a client, server, and computing platform Red Hat sponsored the development of this completely new implementation of a POSIX thread library, called Native POSIX Thread Library, NPTL.

Unless major flaws in the design are found this code is intended to become the standard POSIX thread library on Linux system and it will be included in the GNU C library distribution.

If the comment that this doesn't work with the stable kernel is correct, I consider that a pretty major flaw. Unlike the kernel and NGPT which are developed using an open source model with lots of eyes on the WIP, this was done and then released whole with the decision to include it in the standard library already made. Having any part of glibc not work with the current stable kernel doesn't seem like such a hot idea, honestly.

Quoted 9 lines

The work visible here is the result of close collaboration of kernel and runtime developers. The collaboration proceeded by developing the kernel changes while writing the appropriate parts of the thread library. Whenever something couldn't be implemented optimally some interface was changed to eliminate the issue. The result is this thread library which is, unlike previous attempts, a very thin layer on top of the kernel. This helps to achieve a maximum of performance for a minimal price.

Quoted 6 lines

Initial confirmations were test runs with huge numbers of threads. Even on IA-32 with its limited address space and memory handling running 100,000 concurrent threads was no problem at all, creating and destroying the threads did not take more than two seconds. This all was made possible by the kernel work performed as part of this project.

Is there a performance comparison with current pthreads and NGPT and more typical levels of 5-10k threads as seen on news/mail/dns/web servers? Eliminating overhead is good, but in most cases there just isn't all that much overhead in NGPT. I haven't measured Linux threads, but there are a lot of bad urban legends about them ;-)

Quoted 14 lines

Building glibc with the new thread library is demanding on the compilation environment.

- - The 2.5.36 kernel or above must be installed and used. To compile glibc it is necessary to create the symbolic link

      /lib/modules/$(uname -r)/build

to point to the build directory.

- - The general compiler requirement for glibc is at least gcc 3.2. For the new thread code it is even necessary to have working support for the __thread keyword.

Quoted 7 lines

Similarly, binutils with functioning TLS support are needed.

The (Null) beta release of the upcoming Red Hat Linux product is known to have the necessary tools available after updating from the latest binaries on the FTP site. This is no ploy to force everybody to use Red Hat Linux, it's just the only environment known to date which works.

Of course not, it's coincidence that only Redhat has these things readily available, perhaps because this was developed where no other vendor knew it existed and could have support ready for it.

Modulo my comments on not putting things in libraries which don't widely work, this souncds as if it is less complex and hopefully more stable (not that NGPT isn't) and lower maintenence. I'd love to see comparisons of the three libraries under some typical load, how about a Redhat DNS server running threaded bind? Run a day with each library and look at response time, load average, and of course stability.

Signature · 3 lines
bill davidsen <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.
#60 lore raw
Quoted 10 lines · Bill Davidsen
Quoted 3 lines

Unless major flaws in the design are found this code is intended to become the standard POSIX thread library on Linux system and it will be included in the GNU C library distribution.

If the comment that this doesn't work with the stable kernel is correct, I consider that a pretty major flaw. Unlike the kernel and NGPT which are developed using an open source model with lots of eyes on the WIP, this was done and then released whole with the decision to include it in the standard library already made. Having any part of glibc not work with the current stable kernel doesn't seem like such a hot idea, honestly.

glibc supports .note.ABI-tag notes for libraries, so there is no problem with having NPTL libpthread.so.0 --enable-kernel=2.5.36 in say /lib/i686/libpthread.so.0 and linuxthreads --enable-kernel=2.2.1 in /lib/libpthread.so.0. The dynamic linker will then choose based on currently running kernel.
(well, ATM because of libc tsd DL_ERROR --without-tls ld.so cannot be used with --with-tls libs and vice versa, but that is beeing worked on).

That's similar to non-FLOATING_STACK and FLOATING_STACK linuxthreads, the latter can be used with 2.4.8+ or something kernels on IA-32.

Quoted 12 lines
Quoted 11 lines

- - The general compiler requirement for glibc is at least gcc 3.2. For the new thread code it is even necessary to have working support for the __thread keyword.

Similarly, binutils with functioning TLS support are needed.

The (Null) beta release of the upcoming Red Hat Linux product is known to have the necessary tools available after updating from the latest binaries on the FTP site. This is no ploy to force everybody to use Red Hat Linux, it's just the only environment known to date which works.

Quoted 3 lines

Of course not, it's coincidence that only Redhat has these things readily available, perhaps because this was developed where no other vendor knew it existed and could have support ready for it.

Because all of glibc/gcc/binutils TLS support was developed together (and still is)? All the changes are publicly available, mostly in the corresponding CVS archives.

Jakub

#61 lore raw
Quoted 20 lines · Jakub Jelinek
Quoted 10 lines · Bill Davidsen
Quoted 3 lines

Unless major flaws in the design are found this code is intended to become the standard POSIX thread library on Linux system and it will be included in the GNU C library distribution.

If the comment that this doesn't work with the stable kernel is correct, I consider that a pretty major flaw. Unlike the kernel and NGPT which are developed using an open source model with lots of eyes on the WIP, this was done and then released whole with the decision to include it in the standard library already made. Having any part of glibc not work with the current stable kernel doesn't seem like such a hot idea, honestly.

glibc supports .note.ABI-tag notes for libraries, so there is no problem with having NPTL libpthread.so.0 --enable-kernel=2.5.36 in say /lib/i686/libpthread.so.0 and linuxthreads --enable-kernel=2.2.1 in /lib/libpthread.so.0. The dynamic linker will then choose based on currently running kernel.
(well, ATM because of libc tsd DL_ERROR --without-tls ld.so cannot be used with --with-tls libs and vice versa, but that is beeing worked on).

Quoted 2 lines

That's similar to non-FLOATING_STACK and FLOATING_STACK linuxthreads, the latter can be used with 2.4.8+ or something kernels on IA-32.

Good point, I had forgotten that! It will be somewhat large having both, but presumably someone who really worried about it would build a subset.

Signature · 3 lines
bill davidsen <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.