Op 2010-06-22 12:01, Michael Van Canneyt het geskryf:

One of the drawbacks is that it will pull in thread support, and hence the C library. But if you care to donate the code, I will be happy to include it in FPC.

If these questions are answered somewhere on the wiki, then just pointing me in that direction please.

I know that to threading support is optional in Linux/Unix apps, and is always available under Windows (not sure about Macs).

* What is the downside again of pulling in thread support by default?

* Michael mentioned the C library gets pulled in. Is that bad? Is it possible to have threading support without the C library.

* Why is Windows different is this case and doesn't require a special unit to enable threading support.

Regards,
- Graeme -

OK, the subject sounded vaguely familiar, so when I Googled it, I found my own posting back in 2009 asking the same questions. :-) I'll extend the wiki multi-threading page with the answers that was given last time.

Just another question. Windows gets its threading support from the Win API. Similar for OS/2. Doesn't the Linux kernel have a similar threading API, or do they just rely on the C library?

If not, then I gather the C library (libc, glibc or whatever is used these days) implemented threading in C code using the POSIX spec as the guide. So couldn't one implement the POSIX spec (thinking of threading support only) in pure Object Pascal?

Does the Qt framework also rely on the GNU C library, or do they have there own threading implementation?

Regards,
- Graeme -

In our previous episode, Graeme Geldenhuys said:

See 4.3 in http://www.stack.nl/~marcov/unixrtl.pdf

Note that nowadays afaik it is a bit less problematic as it used to be.

Yes, but that would probably be a very daunting task.

Does the Qt framework also rely on the GNU C library, or do they have there own threading implementation?

Qt is a c++ framework, so they rely on libc anyway. I can't see a reason why they would implement their own threading.

Henry

Graeme Geldenhuys wrote

Just another question. Windows gets its threading support from the Win API. Similar for OS/2. Doesn't the Linux kernel have a similar threading API, or do they just rely on the C library?

The "Linux Way" is more like doing separate executable than doing threads, as Linux always provided high-performance inter process communication (e.g. pipes, usable with "select()" etc.) and process starting ( "fork()" ).

Thus older Linux Kernels did not have special threading support. Threading could be done using "clone()" (instead of "fork()" ) to create processes that share some resources (e.g. memory). The kernel did not really know about the processes forming a multi-threaded application so, to provide some managing capabilities the thread library created an additional "manager thread" to do housekeeping (e.g. kill the other threads if the main thread dies). This is called "Linux Threads".

Modern Kernels Kernels do provide "Native Posix Threads (NPTL) ", managing the specifics of multi-threaded processes in the Kernel itself (providing better Posix compatibility). Moreover the "FUTEX" API is provided to allow for thread synchronization to be even faster than process synchronization.

The "PThread library" user-API did not change. Just using the appropriate version of glibc lets you use "Linux Threads" or "Native Posix Threads" as appropriate, and FUTEX is automatically used for Posix semaphores, if available in the arch used.

Of course you can avoid using the library, do the stuff in Pascal and directly access the Kernel API, but this might be dangerous in case the API might be modified some time in the future or if it's different with different archs (e.g. some archs don't provide FUTEX).

-Michael

In our previous episode, Henry Vermaak said:

> If not, then I gather the C library (libc, glibc or whatever is used these > days) implemented threading in C code using the POSIX spec as the guide. So > couldn't one implement the POSIX spec (thinking of threading support only) > in pure Object Pascal?

No, not straight away. That is technically impossible without integrating a full C compiler, since POSIX requires to be able to read and interpret system headers (e.g. /usr/include/linux and asm on Linux systems, and worse, afaik they have non standard constructs even)

But this is not the biggest problem.

Yes, but that would probably be a very daunting task.

The problem is not the programming (since a dedicated person could probably start with a translated glibc in a good month), but the continuous maintenance (for every distribution separately, since they could use different kernels, options etc) , and interoperability with C code would be killing.

This is all more trouble than interface glibc, even longterm. FPC already supports this (FPC_USE_LIBC) but it is not maintained/used much for Linux/FreeBSD. Because Darwin and Solaris use it, it is not totally outdated though.

Unix is simply not very non C (non gcc) friendly, and worse, the distributions (and FreeBSD too) hardly do anything to mitigate this fundamental design problem.

What maintenance are you referring to? The syscall interface is very stable, so you wouldn't have to touch anything there. I haven't looked at the nptl source, yet, what do they use that changes between distros?

Henry

Michael Schnell wrote

Thus older Linux Kernels did not have special threading support. Threading could be done using "clone()" (instead of "fork()" ) to create processes that share some resources (e.g. memory). The kernel did not

Threading is still done with clone.

Henry

Op 2010-06-22 14:24, Marco van de Voort het geskryf:

No, not straight away. That is technically impossible without integrating a full C compiler, since POSIX requires to be able to read and interpret

And what if one implements a non-posix based implementation (of Free Pascal's own design) support for kernel threading? eg: Start with Linux, then implement others like OSX or *BSD if they support kernel threading. I did a quick Google search, and there are a lot of multi-threading libraries which implement kernel or user-space multi-threading which are not based on POSIX standard.

Here is one such list - there are many more. Not all listed in this link are POSIX based.

http://linas.org/linux/threads-faq.html

The WINE project faced a similar problem. How to implement multi-threading support from Win32 on a Linux kernel that didn't have all the same features or API. Read the page linked for more information - it makes for interesting reading.

http://www.winehq.org/docs/winedev-guide/threading

Anyway, my first thoughts is the same as Henry's - what would change between distros?

Regards,
- Graeme -

For the kernel interface: Not so much. (on some archs, FUTEX is missing).

The problem starts if you start linking to C libraries. In that case you're pretty much forced to use pthreads; each distribution can make different choices when compiling libc.

It would be nice to have a kernel interface, though. That way you could have threading support without pulling in libc.

Michael.

Op 2010-06-22 14:13, Michael Schnell het geskryf:

The "Linux Way" is more like doing separate executable than doing threads, as Linux always provided high-performance inter process communication (e.g. pipes, usable with "select()" etc.) and process starting ( "fork()" ).

Form the previous links I posted, Linux had kernel level threading support since 1.3.56 - that is ages ago. This is very different to the old "creating new processes" idea.

"As of 1.3.56, Linux has supported kernel-level multithreading." -- http://linas.org/linux/threads-faq.html

Of course you can avoid using the library, do the stuff in Pascal and directly access the Kernel API, but this might be dangerous in case the API might be modified some time in the future

Wouldn't the same apply to the pthreads library? From what I understand the currently implementation of NTPL is very good, so I doubt it will change any time soon.

or if it's different with different archs (e.g. some archs don't provide FUTEX).

Start with one platform and implement others as you go on, if they support kernel level threading API. Otherwise fall back to glibc as is currently done. This should minimize dependencies on platforms that support it.

Regards,
- Graeme -

Op 2010-06-22 14:55, Michael Van Canneyt het geskryf:

It would be nice to have a kernel interface, though. That way you could have threading support without pulling in libc.

Exactly. The less we rely on other libraries the better. :)

Regards,
- Graeme -

Michael Van Canneyt wrote

The problem starts if you start linking to C libraries. In that case you're pretty much forced to use pthreads;

Why is that? I thought you could use anything, as long as it's posix compliant?

Henry

No, the syscall api is very stable, so minimum maintenance is required. Which architectures don't provide futex? I'm not aware of any.

Henry

Because the library will make certain assumptions on how a thread is started. If the thread is started from FPC code, then most likely some pthread structures will not have been created for that thread, causing errors.

Likewise, the current FPC threading code assumes that all threads are created through the FPC code. If this is not the case, and some external C code creates a thread, you'll get errors in the FPC code.

Michael.

Well, this is a good reason for getting fpc threading posix compliant, then, no?

Delphi and FPC both implement memory managers with the same API. That does not mean that as a result you can allocate a memory block in FPC code, pass it to a Delphi-compiled DLL and free it there.

A libQt compiled against libpthread.so will continue using libpthread.so, even if your FPC program includes its own POSIX- interface-compliant thread manager. Even if you add "packages" support to FPC so that you can turn both the FPC RTL and this FPC thread library into independent shared libraries, you're not yet home free since both this FPC threadlib and libpthread will export symbols with the same name. Depending on how the symbols are resolved, a) the C code may keep using the libpthread functions and your Pascal code the FPC threadlib functions, in which case there is just as much interoperability as with the memory manager case above (that's what would happen on Mac OS X unless you force the dynamic linker to use a flat namespace, but not all programs work when run that way) b) the C code and Pascal code may both use a mix of symbols from both libraries, which is even worse than case a) (I think that this can happen on Linux under certain circumstances)
c) the C and Pascal code may both use all *common* symbols from either lipthread of the FPC threadlib, but then there's still the case of symbols that are not common. Even if you implement every single function from POSIX, all platforms I know of also have extra pthread*_np functions (such as pthread_kill_other_threads_np() on Linux -- the np stands for "not portable") that only exist on some platforms. So you'd also have to implement all of these extra functions per platform (and such functions get added/removed from time to time).

I propose that if someone wants to write this: try and see how it works out. We can include such a thread manager in the FPC packages if it works and if someone guarantees that they will support and maintain it for the foreseeable future.

Jonas

In our previous episode, Henry Vermaak said:

The syscall interface now only uses a subset of relatively the oldest functions. It doesn't use whatever libpthreads uses to interface with the kernel. (and which got reworked afaik with every major kernel version, and sometimes inbeween)

In our previous episode, Graeme Geldenhuys said:

Same problem. You still have to interface with the kernel, and it would be incompatible with C libraries that use threads.

In our previous episode, Henry Vermaak said:
[ Charset ISO-8859-1 unsupported, converting... ]

Good luck getting all the C libs to use your POSIX compatible threading model.

(I was talking about the kernel syscall interface).

So maybe the fpc syscall interface needs to be updated. Can you give any examples of what got reworked? The kernel seems very serious about keeping the syscall interface stable.

Henry

The reason for creating a native threading implementations is that you _don't_ have to use libc. Why would you use a native one if you're linking to libc anyway?

In our previous episode, Henry Vermaak said:

I only know the subsystem used, and I know that the thread library changed several times, and those thread libraries were major kernel specific.

I thus concluded the kernel interface changed.

In our previous episode, Henry Vermaak said:

Why would you need a native one in the first place?

I was under the impression that fpc uses libc to implement threads on unix. Is this not the case?

Henry

In our previous episode, Henry Vermaak said:

Yes. And 99% of the thread using programs also use other C libs that use libc anyway (*)

As Jonas explained, two thread systems in one binary is almost certain not workable.

(*) the only exception that I'm aware of is the CHM compressor, and because of that fpdoc (but also e.g. chmcmd). It could use thread support to increase compression speed, but is purely Pascal. So currently it doesn't use threads to make distribution easier.

But does it really warrant making a complex lib for that? And for which archs and OSes do you want to do this?

So, to answer your question above about why we need a native one: so we can do away with the libc dependency.

As Jonas explained, two thread systems in one binary is almost certain not workable.

Yes, but you wouldn't use the native one when you are linking to libc, you'll just use pthreads like you do now.

But does it really warrant making a complex lib for that? And for which

I just link to libc myself, since I've never seen a system without one, but this whole thread was in response to Michael who complained that thread support pulls in libc. So this explored an alternative solution.

Henry

In our previous episode, Henry Vermaak said:

In 0.1% of the programs. The rest doesn't need libc, or needs libc because of compatibility with other systems.

I know, but the point is that is the most common case. The case that you actually use a native one would be extremely rare.

The cure is ten times more difficult than the problem. (namely that the stock FPC distribution must be cross-distro compatible to allow for bootstrapping and basic usage).

Libc breaks often, but I'm sure that a native lib will break much more often. And linux distros merge in emergency libc fixes, but they are often not so fast in propagating patches and new versions of FPC.

Marco van de Voort wrote

The cure is ten times more difficult than the problem. (namely that the

That seems quite clear.

Libc breaks often, but I'm sure that a native lib will break much more

I certainly haven't experienced this libc that breaks often. Does that mean that our linux threading will also break often because we rely on libc for that? Again, I haven't seen this, either.

Henry

In our previous episode, Henry Vermaak said:

Keep in mind that that is defined in the context of cross-distro compatibility of the binary interface.

This because we only have one source, and don't automatically adapt to differences.

So if only one distro e.g. starts increasing time_t to 64-bit, it is considered broken (we can't have a binary distro that works everywhere) till all distros have adopted time_t to 64-bit. Gentoo is usually the distro that is first with such changes btw.

Only one such change in 2 years, but that takes its time to ripple through to all distros can already cause effective "breakage" half of the time.

Besides that there is the reference distribution problem. This goes even a step further, and not only requires that something from FPC source, linked on target is working on all distros, but requires that the reference FPC release (the .tgz on linux, nearly all, binaries are libc free atm) works on all distros, and can be used as a base for bootstrapping. This breaks as soon as a binary linked on one distro doesn't work on the other.

Even renaming a library breaks this, since it will not exist on the other platform.

Does that mean that our linux threading will also break often because we rely on libc for that? Again, I haven't seen this, either.

Its not the threading, but the fact that if _something_ that you use from libc, or the link process _TO_ libc leads to an incompatible binary.

As far as threading goes, post NTPL (which hurt pretty bad btw), I can vaguely remember some problems related to sem_timedwait.

At least according to Linus, the kernel api/syscall interface will never break.

In our previous episode, Florian Klaempfl said:

They will just not implement new calls on new archs ? :-)

In our previous episode, Marco van de Voort said:

Euh, old calls obviously.

Thanks for the explanation, it all makes a bit more sense, now!

Henry

Never say never, things will be added, but not taken away. There are some very old programs that still run fine on new kernels. I've read that someone has programs compiled for a 0.9 kernel that runs fine on 2.6.

fpc also proves this point by running on a wide range of kernels.

In our previous episode, Henry Vermaak said:

Huh? Do stock Linux kernels still support a.out? Since afaik ELF was only added in 1.1.52 ?

Well, adding a new arch is not breaking old stuff, right :)?

In our previous episode, Florian Kl?mpfl said:

It was just a remark that "Not breaking" and being backwards compat are two different things.

IOW there are cases where non breaking policy changes can be frustrating (e.g. where general Unix code becomes OS and arch dependant)

Marco van de Voort wrote

Huh? Do stock Linux kernels still support a.out? Since afaik ELF was only added in 1.1.52 ?

It's a kernel option to support it. Most distro's choose "module" here I think? (Autodetect when used)

Micha

Yes, it's BINFMT_AOUT, debian has this compiled as a module.

Henry

Op 2010-06-22 15:31, Marco van de Voort het geskryf:

Same problem. You still have to interface with the kernel, and it would be incompatible with C libraries that use threads.

Well, if I don't use C libraries (only Object Pascal code), then it should still be beneficial. I can then write pure Object Pascal code/applications and still have multi-threading support.

Regards,
- Graeme -

Op Wed, 23 Jun 2010, schreef Graeme Geldenhuys:

It's not just about eliminating libc dependencies. I believe it would be beneficial in most cases, even when using C libraries, since the Linux kernels does not expose a Posix threads like API, Posix threads are emulated. The FPC model is again unlike the Posix model, so you have again glue code. Directly calling the kernel would remove this overhead and allow for more efficient threading.

The fact that the C libraries you call are written for libpthread does not need to be a problem:
- You would not be able to share a variable between Pascal and C and have threads in both worlds wait on each other and two threads may not be able to call C code at the same time, you would need to protect that.
- However, C libraries could safely launch pthread based threads without getting in the wheels of Pascal based threads.

Daniël

The Kylix-like addition of an C compiler would help to solve such issues, that arise from the use of *any* C code with FPC.

An integration of such an compiler (or front-end) into FPC could be based on my ToPas project, that already parses all C syntax and allows to translate it into OPL, as far as that language allows for. It should not be so hard to add the few missing syntax constructs (anonymous unions, bitfields...) to the FPC compiler.

This is all more trouble than interface glibc, even longterm. FPC already supports this (FPC_USE_LIBC) but it is not maintained/used much for Linux/FreeBSD. Because Darwin and Solaris use it, it is not totally outdated though.

It may be a bit harder to unify the libc procedures, so that their use does not duplicate already existing FPC library code, resulting in confusion like with the errno/cerrno variables. This could be done by a set of recognized platform-(in)dependent procedures, so that the basic platform-specific procedures are translated from the (libc...) source code, while the platform-independent procedures are replaced by the according FPC implementation.

A solution may be platform-specific header files, that #define macros for the compatible procedures, redirecting all calls to the existing FPC library procedures. The then obsolete implementations in the C sources can be ignored by the compiler, or can be removed by the linker.

DoDi

Florian Klaempfl wrote

At least according to Linus, the kernel api/syscall interface will never break.

Regarding Threads, as far as I understand, the thread aware APIs (e.g. NPTL and FUTEX) have been added, while the other APIs were not affected. (No wonder, as I understand that the "Linux Threads" were constructed on top of the non-thread "process" APIs (e.g. fork and Inter-Process Semaphores) by the pthread library.

When NPTL, FUTEX, etc appears in one arch, the pthread library is modified to use it, without changing the the user "pthread....." interface of libc.

Very nice for applications that use libc dynamically. So Kylix applications automatically take advantage of NPTL and FUTEX, behaving better and running faster.

But of course using libc does provide problems in certain issues....

-Michael

Henry Vermaak wrote

So maybe the fpc syscall interface needs to be updated. Can you give any examples of what got reworked?

I don't suppose we already have NPTL and FUTEX, as same are used by libc, anyway. If we want perfect performance and good (Posix-like) behavior of the threaded applications, but no libc binding, NPTL and FUTEX API calls need to be done instead of old-style clone() and interprocess semaphores. Especially FUTEX is tricky. (read "Futexes are tricky" by U. Drepper: http://people.redhat.com/drepper/futex.pdf)

-Michael

Graeme Geldenhuys wrote

http://linas.org/linux/threads-faq.html

This is _very_ old (1996).

they say:
"Kernel-Threads
Kernel-level threads often are implemented in the kernel using several tables"

This might be true, but we now have a ubiquitous and stable NPTL implementation in the Kernel.

-Michael

Michael Van Canneyt wrote

For the kernel interface: Not so much. (on some archs, FUTEX is missing).

Yep.

If not using libc, _we_ must do the decision (e.g. whether to use FUTEX or not.

i.e..:
Archs that don't provide FUTEX, do not have atomic user space instructions, which are necessary to make use of the FUTEX Kernel API. But some archs (some ARM types) do provide a "atomic region" interface to simulate atomic user space instruction,. so Futex is possible without hardware support of "atomic".

It would be nice to have a kernel interface, though. That way you could have threading support without pulling in libc.

Right but not easy to do and creates very arch- and sub-arch depending code.

-Michael

I suppose that the Kernel Thread API (NPTL, FUTEX) in fact is here to stay, but especially _using_ the FUTEX API in a user land application is tricky, so relying on libc (on that behalf) seems like a good idea, as it's "pthread...()" api is easy to use.

-Michael

These "APIs" you're talking about, are just system calls. There are no magic NPTL APIs: both NPTL and LinuxThreads use the "clone" system call. In order to implement Posix threads, some things needed to be improved in the kernel, though, and there were also some new system calls (tls for x86/64, exit_group). futex was added before NPTL, so NPTL uses them.

Read this article if you'd like to find out how this was implemented:

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

Henry

I still can't find which arches miss futex, and I can't find this information in the manpages, either. Can you point me to where you've found this information?

I've had a look at the kernel source, go to the arch directory and execute:

grep -Rl NR_futex *

All the architectures show up.

Henry

In our previous episode, Hans-Peter Diettrich said:

Well, since this is about a maintenance problem, it would only solve it if the maintenance of the C compiler would be lower than the maintenance of fixing the headers/RTL..... Which I doubt strongly, even if we forget about the gigantic initial costs (making a production C compiler)

If a real systematic problem here would ever appear, I would go more in the direction of a configure like hack. Characterising the system by compiling small C programs.

I think I don't entirely understand what problem this paragraph is about. Yes, we have two errnos now, but not doing that means that you essentially have to create a configure like layer. (since this is not even automagical for C programs)

In the light of that, I have no problem with the current solution.

The FUTEX Kernel API only makes sense, if the arch provides the appropriate atomic operations to perform the FUTEX semaphore handling in user space.

Some archs (like X86 and the new ARMs' "load locked / store conditional" instructions) provide assembler instructions for this.

Some archs (e.g. older ARMs and BlackFin) provide the "atomic area" function calls (procedures located at at fixed locations) for this (only doable with non-SMP implementations).

Some archs don't provide atomic instructions at all (e.g. the current NIOS arch, "atomic region" is planned to be implemented".) Here enabling the FUTEX API in the Kernel does not make sense.

-Michael

Henry Vermaak wrote

There are no magic NPTL APIs: both NPTL and LinuxThreads use the "clone" system call.

Yep. Additional "clone flags" have been added with newer Kernels (see "man clone").

Moreover for NPTL there are thread IDs additional to process IDs Same can be obtained from the Kernel by some kind of NPTL specific API.

-Michael

Henry Vermaak wrote

I still can't find which arches miss futex, and I can't find this information in the manpages, either. Can you point me to where you've found this information?

At least in the Linux Kernel Mailing list there are several discussions on Futex (e.g. non-existing Futex). Astonishingly, even for x86 archs there have been several patches to cure problems.

If they show up that does not mean there really is a valid implementation. I don't know which archs are provided with the "Linus Tree", but at least with some "embedded" Kernels trees there only is some dummy code, just providing an error.

-Michael

I think you'll first have to worry porting fpc to those architectures.

Henry Vermaak wrote

I think you'll first have to worry porting fpc to those architectures.

Right you are :)

But anyway, if not using libc, you need to do the FUTEX user space part in Pascal/Assembler

- With X86 using the appropriate assembler instructions (such as "lock cmpxchg")
- with ARM11 using "load locked / store conditional"
- with ARM9 using an appropriate call to a fixed Kernel defined address to have the atomic instruction executed.

tricky but doable.

-Michael

Why would you want to do that? Just use the futex syscall.

Op Wed, 23 Jun 2010, schreef Henry Vermaak:

Because the Futex syscall won't give you threads, it requires userspace assistance.

Daniël

A futex syscall doesn't know anything about threads, it's for locking. Perhaps I'm misunderstanding you?

Henry Vermaak wrote

Why would you want to do that? Just use the futex syscall.

Here you are definitely wrong.

Futex is all about _not_ doing a syscall (i.e. change from user space to Kernel space and back) but doing the Mutex operation in user space, if possible (i.e. if not putting a thread to sleep due to Mutex already taken or to wake a thread if the Mutex is freed and at least one thread is waiting. As in most cases a Futex (TCtriticalSection) is only locked for a short time, performance is increased if no syscall needs to be done if no other thread tries to lock it while it's already taken.

So userspace needs to do some non-trivial stuff without doing the FUTEX syscall and only do the system call if necessary (see "Futexes are tricky" I mentioned above).

This includes doing some critical operations in an atomic way (Thread safe and SMP safe if appropriate).

-Michael

Op Wed, 23 Jun 2010, schreef Henry Vermaak:

A futex syscall doesn't know anything about threads, it's for locking. Perhaps I'm misunderstanding you?

I have should have written "futex" instead of "threads". With a Futex, you only call the Futex syscall, if the Futex is locked. You still have to test wether the Futex is locked in userspace, and you that with the interlocked assembler instructions. This assembler implementation must be implemented for each architecture (though abstractions can probably be used, we already have many interlockedxxxxx procedures).

Daniël

Henry Vermaak wrote

A futex syscall doesn't know anything about threads, it's for locking. Perhaps I'm misunderstanding you?

The Futex syscall does not lock a 's a helper for the user space locking action and performs the putting a thread to sleep (called by userspace, if userspace detects that the Mutex to be locked is already taken) and waking up a thread (called by userspace if userspace detects that a thread is waiting on the Mutex it is about to unlock) and moreover the Futex syscall takes care that the system can do some housekeeping in case a thread dies that still has a lock.

The user space stuff is usually done in a library (such as pthread lib in libc. But of course it can be done natively the FPC RTL, as well.

-Michael

Ah, I see. I've seen the interlocked procedures in the rtl, we seem to have them for quite a couple arches (at least all the ones that support linux).

Henry

Ops, except m68k.

And that one is currently not supported by FPC (at least from 2.x on, because no one updated the cpu units for this architecture).

Please correct me if I'm wrong.

Regards,
Sven

The C compiler IMO won't cost much, since it can use the OPL code generation. ToPas can produce an FPC compatible AST for that purpose. It also is already configurable, to emulate almost any existing C compiler. I've tested with CBuilder, MSVC and gcc, and their header files, so that such existing header files can be used instead of e.g. the MinGW or Cygwin rewrites.

I'm just about to make the FPC compiler usable as a mere syntax parser, with all semantic actions, like code generation, moved into (exchangable) units. The C front-end could create the tree(s) for immediate use by these semantic procedures. Since the separation of the semantic code is already sponsored by Adem, I will do it anyways without burdening the FPC team. The result only depends on the goodwill of the FPC developers, to accept that separation and put it into the FPC trunk, so that the future development can be done without syncing different codebases. I'll start an according thread as soon as I have some more concrete ideas and results.

If a real systematic problem here would ever appear, I would go more in the direction of a configure like hack. Characterising the system by compiling small C programs.

I don't like that hack, and have ideas also for this problem. IMO a header file with the description of the capabilities of a concrete platform will be sufficient, with low maintenance requirements. Something like the autobloat tools try to achieve, but with a better implementation. Here the outstanding FPC handling of platform specific differences will be very helpful.

<rant>
The major problem of the open source (GNU/Linux...) world is the lack of cooperation between the maintainers of the various platforms - they always ask for perfect implementations which they can use off-the-shelf, but are not willing to spend a few hours even in the specification, adaptation or configuration of a new model. Since we already have a team of platform maintainers in the FPC project, it should be much easier to specify and implement a model for handling the platform differences. In the best case we could end up in an simplified and improved autobloat replacement, which all the C experts could not provide in past decades.

Perhaps in a few years nobody will remember gcc and autobloat any more, because then everybody uses our superior fcc ;-)
</rant>

I think I don't entirely understand what problem this paragraph is about. Yes, we have two errnos now, but not doing that means that you essentially have to create a configure like layer. (since this is not even automagical for C programs)

My idea is an abstraction at the header-file level, eliminating the need for an adaptation layer in code. It's not a very concrete project right now, since I could not yet identify all the possible problems.

In the light of that, I have no problem with the current solution.

I have no problem with the existing solution, too, but together we possibly could find easier and more consistent solutions for all these problems.

Okay, it's time to wake up and stop dreaming, there remains enough higher priority work for everybody right now...

DoDi

We've got this already, then:

http://www.freepascal.org/docs-html/rtl/system/interlockedcompareexchange.html

nice !

X86, X68-64: good.

"ARMV6" uses ldrex (seemingly = "load locked"): good

Other ARMs (including thumb2) uses a loop with result compare. AFAIK this does not work reliably. I am not sure it it's really true that ARM implements the "atomic region" but if FUTEX is available in the Kernel a set of reliable atomic user space instructions is provided as well. So we would need to use this.

PPC, PPC64, Sparc: loop: not reliable

In theory a decent Futex implementation could be done on top of this (see "futexes are tricky") for X86, X86-64 and ARMV6. For ARMV5 we should take a look at the implementation of the atomic functions for Futex ("pthread_mutex...()") done in libc.

-Michael

Michael Schnell wrote

PPC, PPC64, Sparc: loop: not reliable

interlocked* is implemented correctly in the RTL and functions 100% reliably on the above architectures. Please don't make such categorical statements if you are unfamiliar with the architectures (and I guess that the version for ARMv5 and below is probably also completely correct).

Jonas

PPC, PPC64, Sparc: loop: not reliable

I can only speak for sparc (because I implemented them initially): they are implemented according to official sparc docs. Do you know more then them?

Michael Schnell wrote

Other ARMs (including thumb2) uses a loop with result compare. AFAIK this does not work reliably. I am not sure it it's really true that ARM

No, SWP is atomic, so the implementation looks good (at a glance).

Henry

Sorry if I have been sounding rude :(.

I learned that If there is no hardware support, it's not possible to create thread-safe or smp safe atomic operations. Maybe the sequence in fact performs a "load locked, save conditional" paradigm, which I did not see.

-Michael

even if that is true there is a problem:

// lock
ldr r12, .Lfpc_system_lock
mov r3, #1
.Lloop:
swp r3, r3, [r12]
cmp r3, #0
bne .Lloop
// do the job

- thread 1 comes in and sets fpc_system_lock to 1
- now thread 2 is scheduled and comes in
- fpc_system_lock is set so it enters a busy spinning

unfortunately we are in a "realtime" system and the priority of thread 2 is set higher than that of thread 1 and thus thread 1 never gets a CPU cycle as thread 2 is busy and thus we have a dead-lock.

-Michael

Michael Schnell wrote

unfortunately we are in a "realtime" system and the priority of thread 2 is set higher than that of thread 1 and thus thread 1 never gets a CPU

Priority inversion? Isn't this a problem with any InterlockedC/E?

Micha

What system has such an unfair scheduler?

Mattias

Henry Vermaak wrote

No, SWP is atomic, so the implementation looks good (at a glance).

Seemingly not on all ARM sub-archs:

From some ARM manual:

The ARM7500FE does not use the lock feature available in the ARM701 macrocell
You must take care to ensure that control of the memory is not removed from the ARM
processor while it is performing this instruction.

-Michael

Micha Nelissen wrote

Priority inversion? Isn't this a problem with any InterlockedC/E?

Priority inversion here leads to an unavoidable deadlock. "Normal" priority inversion only reduces the priority of a high priority thread to that of a lower priority thread that holds the lock.

-Michael

Mattias Gaertner wrote

What system has such an unfair scheduler?

A "fair" Scheduler only can be fair if time slices are to be managed. If you set a thread to a "realtime priority" (OK, you need to be root to be allowed to do that :) ) it's priority is above all the normal processes. That is quite normal if you do embedded Linux systems.

-Michael

Sorry if I have been sounding rude:(.

-Michael

Op Wed, 23 Jun 2010, schreef Michael Schnell:

It's a non-issue. If you set a thread realtime you know what you are doing and can take care you give up the CPU when feasible, or you simply don't enter mutuxes shared with non-realtime threads.

Of course if there is a simple fix...

Daniël

the ARM7500FE is ARMv3. I think fpc supports ARMv4 and higher.

Regards, Bernd.

That only means that it doesn't send the lock signal to the external memory manager, so you can't have a multi processor implementation using this processor. It doesn't affect the working of the swp instruction.

Henry

I'am sure if it's a problem for somebody, he will find a solution and send a patch.

This seems to apply only to systems with multiple processors, and perhaps with DMA controllers. Who else could obtain control of the memory? And who would build a multi-processor system with that inappropriate processor?

But sh*t happens, of course ;-)

DoDi

Daniël Mantione wrote

It's a non-issue. If you set a thread realtime you know what you are doing and can take care you give up the CPU when feasible, or you simply don't enter mutuxes shared with non-realtime threads.

I don't agree.

If the RTL provides a method, it should be working and not unavoidably create a dead lock, even if a thread is set to a realtime priority. Moreover Thread Synchronization using FUTEX (via TCriticalSection) (implementing this directly in the RTL instead of using libc is what is being discussed right now here) is especially useful in a "realtime" system, as it improves the performance of the threaded application.

Moreover the current implementation is not optimal at all even in a system with time-slices. If there is no other way with this arch but an active spinning lock, the blocked thread should at least give up it's current time slice before retrying to get the lock, so that the blocking thread can work and release the lock. otherwise (in a single CPU system) the resting part of the time slice is deterministically wasted.

AFAIK calling "sleep(0)" would give up the time slice.

-Michael

I understand the "external memory manager" is the memory interface of the ARM IP core and thus is involved with any read and write access. As the ARM company only provides the CPU IP core, the chip manufacturer is responsible of the memory interface and if the locking is not decently handled, even a single CPU system might fail. This of course is true if the lock signal is provided by a more advanced ARM core but the Chip hardware does not use it

But maybe I am just too cautious ....

-Michael

Florian Klämpfl wrote

I'am sure if it's a problem for somebody, he will find a solution and send a patch.

As the swap instruction seems to be the only atomic memory operation ARM lower than v6 can do, there is no possible workaround in user space software.

For a single CPU system the Kernel might provide a "atomic area" functionality to help with this.

-Michael

Tell this the writers of the cpu architecture manuals.

Well, yes, you shouldn't simply use locked operations in a single cpu environment, your application should provide different algorithms for single and multi cpu/threaded environments if the application really contains speed critical code requiring locking. This is why FPC uses inclocked/declocked for fast reference counting.

On 24 Jun 2010, at 09:27, Michael Schnell wrote:

[ARMv5 and lower atomic exchange]

If there is no other way with this arch but an active spinning lock,

There is indeed none.

And on a multiple cpu system you can introduce extra latency if you give up your time slice early. The compromise is obviously to try for a few times and if it doesn't work after that, give up the time slice. However, at this time the interlocked* routines are completely OS- agnostic and that would require moving these routines to OS-specific include files (or add the ability for OS-specific include files of the system unit to override the implementation of these routines).

AFAIK calling "sleep(0)" would give up the time slice.

It doesn't on all systems.

Jonas

Op Thu, 24 Jun 2010, schreef Michael Schnell:

If you are special things, it is reaosnable to ask special attention by the one who does those things. If there is an easy fix, feel free to propose it.

Yes, but in a multi-cpu system giving up the timeslice is a very bad idea, because the lock might be released a few clock cycles later by the other cpu; you would waste the rest of time slice while you could be crunching.

Daniël

Florian Klaempfl wrote

Well, yes, you shouldn't simply use locked operations in a single cpu environment, your application should provide different algorithms for single and multi cpu/threaded environments if the application really contains speed critical code requiring locking.

Do you suggest the application programmer should take care about if the application runs on a multi.CPU system or a single CPU system ?

This is why FPC uses inclocked/declocked for fast reference counting.

I don't understand.

with ARM inclocked() calls InterlocktIncrement, that triggers exactly this problem.

-Michael

Of course you are right. But this code is only used for ARM lower than v6 (ARMV6 provides ldrx which is fine, anyway). Are there really multi-CPU ARMv5 or even ARMv4 systems ? They would work decently with the sleep; I don't think it's relevant to optimize the RTL code for those.

-Michael

Yes. If it's real time or performance critical then he should really know when locking is needed etc.

... because nobody provided a better implementation yet, e.g. i386 does. Nobody provided either code yet which makes dynamic use of strex/ldex as newer arms provide as I did e.g. for move using pld if available because I needed it.

Not without kernel support, see here:

http://www.eglibc.org/cgi-bin/viewcvs.cgi/trunk/ports/sysdeps/arm/bits/atomic.h?rev=77&view=markup

Note the comment:

/* Atomic compare and exchange. These sequences are not actually atomic; there is a race if *MEM != OLDVAL and we are preempted between the two swaps. However, they are very close to atomic, and are the best that a pre-ARMv6 implementation can do without operating system support. LinuxThreads has been using these sequences for many years. */

The linux specific code is here:

http://www.eglibc.org/cgi-bin/viewcvs.cgi/trunk/ports/sysdeps/unix/sysv/linux/arm/nptl/bits/atomic.h?rev=3063&view=markup

It relies completely on the kernel.

Henry

Florian Klaempfl wrote

Nobody provided either code yet which makes dynamic use of strex/ldex as newer arms provide as I did e.g. for move using pld if available because I needed it.

The code using strex/ldex is in place for ARMv6 and ARMv7. I don't doubt that same is as goos as possible.

Only lower ARM suffer from the problem in question. Same does not support strx/ldx. Thus the workaround with swp is provided.for those archs

-Michael

SMP is not supported by the kernel for arch < armv6.

But it is not used dynamically: if you compile for arm linux, you get the ARMv5 code path even if the code runs on ARMv6+

:) :) :) "Very close to atomic" is funny, regarding that the (obviously rare) case of non-atomic behavior will cause a system crash.

The linux specific code is here..

I suppose this uses the said "atomic region" method:

- Userspace (without doing a change to system mode) calls a function provided by the system in a dedicated place (in user-space, write protected and common for all processes)
- if no interrupt happens everything is fine
- the interrupt code in the Kernel detects if the interrupted user space function was preempted in the middle of such a function (i.e. PC in the atomic area)
- if such a condition is detected the kernel correctly completes the function for the user space process and adjusts the user space PC before returning to user space into this or another procedure / thread.

With such systems the C library (i.e. macros in .h files) for "atomic_..."-functions is provided as a call to the appropriate "atomic region" function.

Of course this can be done directly in the RTL, as the addresses of the "atomic_..."-functions is supposed to be stable.

-Michael

Florian Klaempfl wrote

But it is not used dynamically: if you compile for arm linux, you get the ARMv5 code path even if the code runs on ARMv6+

I see.
I suppose somewhere you can define that you want RMv6+ code. I would do this whenever possible.

Maybe providing an optional dynamic ARM-arch detection would be nice to have.

-Michael

Henry Vermaak wrote

SMP is not supported by the kernel for arch < armv6.

Great !
So nothing serious needs to be done about that. Maybe automatically detecting the arch and using the best possible code for atomicness would be a good way to go.

-Michael

Which exposes the user helpers here:

http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=arch/arm/kernel/entry-armv.S;h=7ee48e7f8f318a7b453e12849b60a6832bb85770;hb=HEAD#l767

Henry

Yep.

"These are segment of kernel provided user code reachable from user space at a fixed address in kernel memory. "

So these functions can be called directly from the RTL. I suppose, the fixed addresses can be taken from some library ".h" file.

-Michael

Michael Schnell wrote

Maybe automatically detecting the arch and using the best possible code for atomicness would be a good way to go.

Even better: as you found the "fixed addresses" implementations same should be used having the Kernel automatically provide the optimum implementatikon for the sub-arch it runs on.

-Michael

Yes, but in a multi-cpu system giving up the timeslice is a very bad idea, because the lock might be released a few clock cycles later by the other cpu; you would waste the rest of time slice while you could be crunching.

IMO the default implementation should work on every architecture. When somebody has really time critical tasks, he has to choose a decent architecture (machine and OS), and optimize his code for that platform.

For everydays computing background-threads are perfectly sufficient, and these can even be "inlined" when a platform does not provide thread expects that his number-crunching software will
run on an ZX-81 as well as on a Cray, and the same IMO applies to other perfomance-critical requirements.

Threads IMO are the best platform-independent solution, when it comes to the use of the actually available resources on nowadays processors, with possibly more than one core. Then the OS can distribute the load on the available cores - and for that purpose it *must* provide the required synchronization features. If not, then the user did something wrong in the configuration of his machine, and he cannot expect that FPC gets out of it more than he has put in.

DoDi