Jeff Roberson recently announced a new 1:1 threading implementation that has been merged into FreeBSD -current. The effort builds upon the work done so far on KSE [story], offering SMP scalability and working proof of KSE's design. Jeff explains, "This code works in parallel with KSE and does not break it in any way. It actually helps bring M:N threading closer by testing out shared bits."

In his announcement, Jeff notes that he has succesfully run Mozilla and Open Office with this new threading library. With the March 31'st merge annoucement, Jeff noted that the code is beta quailty, and he included a small list of known errata .

Following the announcement of this new threading library, it was asked how it fits together with the overall SMPng effort. Terry Lambert provided an interesting summary of each of these projects, including pthreads, libc_r, KSE, libthr, and SMPng. He provides a few related links, however explaining, "most of the documentation lives in mailing list archives, and is not terribly formal (Software Engineers, not English Majors, and all that...)" Read on for the full details.

From: Jeff Roberson
To: arch
Subject: 1:1 Threading implementation.
Date: 25, Mar 2003 19:00:14 (PST)

I realize that many people have strong feelings on this topic.  I'm asking
everyone up front to try not to devolve this thread into a bikeshed.

Thanks to the foundation provided by Julian, David Xu, Mini, Dan Eischen,
and everyone else who has participated with KSE and libpthread development
Mini and I have developed a 1:1 threading implementation.  This code works
in parallel with KSE and does not break it in any way.  It actually helps
bring M:N threading closer by testing out shared bits.

I have successfully run mozilla 1.2.1 using this threading package.  It
still has some bugs and some incomplete corners but we're very close to
being able to commit this.  I'm going to post a link to the kernel portion
of this code at the end of this mail.  The library will come later.

What this means is that for every pthread in an application there is one
KSE and thread.  There is also only one ksegroup per proc in this model.
Since the kernel knows about all threads it handles all scheduling
decisions and all signal delivery.  I have followed the POSIX spec while
implementing the signal code.  I would really appreciate review from
anyone who is intimately familiar with signals and threads.  Included in
this is an implementation of sigwait(), sigtimedwait(), and sigwaitinfo().

The user land mutexes are supported by kernel code.  Uncontested acquires
and releases are done entirely in application space using atomic
instructions.  Once there is contention the library falls back to system
calls to handle the locks.  There are no per lock kernel resources
allocated.  There is a user space safe atomic cmpset function that has
been defined for x86 only at the moment.  New architectures require only
this function and the *context apis to run this threading package.  There
is no arch specific code in user space.

The condition variables and other blocking situations are handled with
sig*wait*() and a new signal, SIGTHR.  There are many reasons that we went
with a signal here.  If anyone cares to know them, you may ask.

There are only 4 system calls for threading. thr_create, thr_self,
thr_exit, and thr_kill.  The rest of the functionality is implemented in a
library that has been heavily hacked up from the original libc_r.

The reason we're doing this in parallel with the M:N effort is so that we
can have reasonable threading sooner.  As I stated before, this project is
complimentary to KSE and does not prohibit it from working.  I also think
that the performance will be better or comparable in the majority of real
applications.

The kernel bits are available at
http://www.chesapeake.net/~jroberson/thr.diff

I'd like to get the signal code commited asap.  It's the majority of the
patch and I often have to resolve conflicts.  There have been no
regressions in KSE or non threaded applications with this signal code.

Cheers,
Jeff

From: Jeff Roberson
To: current
Subject: New threading code.
Date: Mon, 31 Mar 2003 20:28:26 -0500 (EST)

The kernel components for the 1:1 threading implementation are in the
tree.  This includes the thr system calls, the umtx implementation, and
all of the signal changes.

I will commit the library shortly.  This is all 'beta' quality.  It runs
mozilla and openoffice without issue.  There are known bugs which I will
point out when libthr is in the tree.

More to come.

Cheers,
Jeff

From: Jeff Roberson
To: current
Subject: libthr and 1:1 threading.
Date: Mon, 31 Mar 2003 22:54:45 -0500 (EST)

I have commited libthr.  To try this out you'll need to do the following

1.  cvsup
2.  rebuild world and kernel
3.  install world and kernel
4.  build libthr from src/lib/libthr
5.  Either replace /usr/lib/libc_r.so.5 with /usr/lib/libthr.so.1 or
relink your applications against libthr.so.1

This works with mozilla and open office.

Known errata:
1.  Mutex priority inheritance is not implemented.
2.  If you mess with the mutex or condvar queues from a signal handler you
will break.
3.  If you reset the sigaction for SIGTHR you will break things.
4.  The scheduling parameters lie.
5.  The garbage collector deadlocks.  We never free threads.  You will
eventually leak memory or run out of LDT entries.
6.  This is x86 only for a short while.
7.  Some of the code is ugly.

I will be addressing all of this shortly.  Feel free to try it out and
report bugs that are not mentioned above.

Cheers,
Jeff



From: Stijn Hoop
Subject: Re: libthr and 1:1 threading.
Date: Wed, 2 Apr 2003 10:30:26 +0200

On Mon, Mar 31, 2003 at 10:54:45PM -0500, Jeff Roberson wrote:
> I have commited libthr.  To try this out you'll need to do the following

I know very very little about threads, but I'm interested as to what the
purpose is of this library. Is there a document available somewhere that
describes the relationships between this, KSE, libc_r, pthreads, the
Giant-unwinding-make-SMP-work-better project and some of the other
threads and SMP related libraries and terminology?

--Stijn

-- 
"...I like logs. They give me a warm fuzzy feeling. I've been known to keep
logs for 30 months at a time (generally when I thought I was rotating them
daily, but was actually rotating them once a month)."
	-- Michael Lucas, in Big Scary Daemons article 'Controlling Bandwidth'



From: Terry Lambert
Subject: Re: libthr and 1:1 threading.
Date: Wed, 02 Apr 2003 01:17:21 -0800

Stijn Hoop wrote:
> On Mon, Mar 31, 2003 at 10:54:45PM -0500, Jeff Roberson wrote:
> > I have commited libthr.  To try this out you'll need to do the following
> 
> I know very very little about threads, but I'm interested as to what the
> purpose is of this library. Is there a document available somewhere that
> describes the relationships between this, KSE, libc_r, pthreads, the
> Giant-unwinding-make-SMP-work-better project and some of the other
> threads and SMP related libraries and terminology?

No, not really: the new libthr was pretty much a "Skunk Works"
project, and was not managed through the KSE project; it's really
orthogonal, but builds on some of the KSE work already done in the
kernel so far... most of KSE lives there.

Here's a thumbnail sketch, though (forgive me, KSE folks, if I mung
it too badly):

pthreads:	POSIX Threads is a threads API, which is
		specified by the standard ISO/IEC 9945-1:1996
		(``POSIX.1'').

libc_r:		A user space implementation of the pthreads API;
		this implementation uses a "call conversion"
		scheduler, in user space, to convert blocking
		calls into non-blocking calls, plus a threads
		context switch via the user space scheduler.
		Like all interactive timesharing schedulers, it
		gives the illusion of concurrency.  However, the
		kernel is not thread-reentrant in this model, so
		it does not scale to more than one CPU on an SMP
		system, since there is only a single scheduler
		context.

KSE:		"Kernel Schedulable Entitites" is the name of
		the modified scheduler activations framework, as
		well as the user space components, and kernel
		modifications, for an N:M model threading system.
		It has the advantage over the "libc_r" in that it
		causes the kernel to be thread reentrant, and so
		it provides SMP scalability.  Because it's N:M,
		it also has the advantage over the 1:1 approach
		of causing full quantum utilization, and providing
		for CPU affinity for individual threads, and CPU
		negaffinity for threads within the same process,
		thereby providing for theoretically optimal CPU
		and other resource utilization.  It also includes
		a user-space library component, which is incomplete
		at present.

libthr:		This is the recently committed 1:1 model threading
		library.  It provides a simpler user space library
		component, which provides the same SMP scalability,
		as far as kernel thread reentrancy is concerned,
		but fails to provide for full quantum utilization,
		and, at present, does not directly address the CPU
		affinity issues itself (no sophisticated use of
		KSEGRP).  It builds on the kernel modifications for
		KSE, and adds a couple of system call API's in order
		to manage creation, etc., of threads.  The major
		intent is to provide for SMP scalability; as a side
		effect, it provides a proof-of-concept for the KSE
		code already in the kernel, and as such, has been
		very welcome.

SMPng:		"The Giant-unwinding-make-SMP-work-better project",
		to quote you.  8-).  SMPng has it's own project
		page and documentation.  To give another thumbnail
		drawing, it's about improving the granularity of
		locking and the logical seperation between kernel
		subsystems, so that stall barriers are eliminated.
		By doing this, inter-CPU contention is reduced,
		and you get better SMP scaling.  Traditionally,
		when you added another CPU, you maybe got a 20%
		performance improvement for a 100% increase in
		cost.  The idea is to get that 20% up to as close
		to 100% as possible (impossible, but you can
		approach that).  SVR4, for example, scales well
		up to 4 processors on Intel.  It scales higher than
		that, but the incremental improvement is about 80%,
		and so at about 4 processors, you hit a point where
		the cost of additional processors is higher than
		the value of the additional compute cycles.

You may also find these resources useful:

	http://people.freebsd.org/~julian/threads/
	http://www.freebsd.org/smp/index.html
	http://www.freebsd.org/projects/busdma/index.html
	http://www.freebsd.org/projects/projects.html

Most of the documentation lives in mailing list archives, and is
not terribly formal (Software Engineers, not English Majors, and
all that...).

-- Terry

• BSDForums Announcement