Hi,

I found another problem with Semaphores between FreeBSD and Linux.

Attached is my test project. Again, it is similar code used in tiOPF.

For some reason under FreeBSD, it *always* zeros the variable that holds the Max Pool Size value passed in to sem_init()'s third parameter. This means that if I try and us that variable anywhere after the sem_init() call, like when I want to destroy the semaphore, I can't because the variable now holds the value 0.

Here is an example of the test program's output. Not the value of FMaxPoolSize before and after sem_init() call. Also note the value of i
- no destruction code (sem_post) is executed.

---------[ output under Linux ]---------------
$ ./project1
FMaxPoolSize before = 2
FMaxPoolSize after = 0
c = 2
Now create a lock
c = 1
Now create a lock
c = 0
i = 0
-----------------------------------------------

And here is that exact same test project under Linux. Note the FMaxPoolSize variable still has the original value after the sem_init() call - as expected. Also the i variable increments as we unlock the semaphore.

---------[ output under Linux ]---------------
$ ./project1
FMaxPoolSize before = 2
FMaxPoolSize after = 2
c = 2
Now create a lock
c = 1
Now create a lock
c = 0
i = 0
unlock a semaphore
i = 1
unlock a semaphore
i = 2
-----------------------------------------------

Any idea why FreeBSD does this? A bug in FPC+FreeBSD?

Regards,
- Graeme -

[snip]

Any idea why FreeBSD does this? A bug in FPC+FreeBSD?

I have an idea. But for this I'd need some confirmation: Can you please put in your example program the FSemaphore into a record and add also a field of type "array[0..1] of LongInt" to that record and try that again? (of course you'll need to adjust the call to sem_init to use the field in the record). Additionally it would be nice if you write some "well defined garbage" into the added array (e.g. $12345678 and $87654321) and then output the content of the two values after the sem_init call? [and yes, I'm thinking in the context of memory corruption here]

Regards,
Sven

FPC's definition of the semaphore struct is probably wrong for FreeBSD. Currently, it's:

sem_t = cint;

Whereas a quick google search got me here:

http://svnweb.freebsd.org/base/head/include/semaphore.h?revision=201546&view=markup

Which says sem_t should be:

struct _sem {
	__uint32_t _magic;
	struct _usem _kern;
};

This would explain your variable getting overwritten, I think.

Henry

Sven Barth wrote

I have an idea. But for this I'd need some confirmation: Can you please put in your example program the FSemaphore into a record and add also a ...

OK, attached is the new test project. Below is the output.

Now the FMaxPoolSize variable still has the correct value before and after sem_init(), and I could successfully unlock the semaphores. But as you can see, the array values have changed.

--------[ freebsd output ]--------------
$ ./project1
FMaxPoolSize before = 2
FValues[0] = $123456
FValues[1] = $654321
FMaxPoolSize after = 2
FValues[0] = $000002
FValues[1] = $000000
c = 2
Now create a lock
c = 1
Now create a lock
c = 0
i = 0
unlock a semaphore
i = 1
unlock a semaphore
i = 2

----------------------------------------

Regards,
- Graeme -

Exactly as I thought. The reason is - as Henry already wrote - the incorrect declaration of sem_t. I had already started a discussion about this on core after I had investigated your original problem, because I thought that this could lead to problems. The way sem_t is currently declared is the way it was declared in the C headers of FreeBSD 7.

So currently you can only be safe by putting an "array[0..3] of LongInt" (4 * 4 Byte to be on the safe side) after the declaration of FSemaphore in your class. Even if a fix is made in trunk it won't be likely to make it into 2.6.2 though as that is currently already prepared for release... :(

Could you please report this together with the adjusted test program as a bug, so it's definitely not forgotten? (and you can mark this at least as "major")

Regards,
Sven

You are in so far right that the declaration is incorrect, but in trunk it looks like this:

=== code begin ===

sem_t_rec = record end;
sem_t = ^sem_t_rec;

=== code end ===

So that it resembles the declaration of sem_t in the headers of FreeBSD 7:

=== code begin ===

typedef struct sem * sem_t;

=== code end ===

Nevertheless this needs to be changed...

Regards,
Sven

Indeed, but trunk pthread.inc looks different from this:

sem_t = record
	magic   : cuint32;
	lock    : pthread_mutex_t;
	gtzero  : pthread_cond_t;
	count   : cuint32;
	nwaiters: cuint32;
	semid   : semid_t;
	sysse   : cint;
	entry   : psem_t;
	backpointer : ppsem_t;
	spare : array[0..SEM_SAFE] of char;
end;

Since the definition of TSemaphore is in this file, this definition will be used?

Henry

In our previous episode, Henry Vermaak said:

For the threadmanager it will be yes. Since the $i pthreads.inc is after the unixtype include in cthreads.

The rtl/freebsd/pthread.inc is only used in the implementation section of rtl/unix/cthreads.pp. And if we fix the sem_t type then this declaration can be removed again (it will then use UnixType.sem_t which is located in rtl/inc/ptypes.inc).

Regards,
Sven

Hi,

OK, now that we established that semaphores are broken in FreeBSD using FPC 2.6.0 and the upcoming FPC 2.6.2. I'm looking for an alternative.

An alternative for two reasons.
- I hate IFDEF code, and the semaphore code between Linux, FreeBSD and Windows are different.
- Semaphore sem_t structure is incorrectly defined for FreeBSD, so I'll have to implement a special case for that platform.

Semaphore functionality seems pretty simple though, so I am thinking of creating my own Object Pascal based cross-platform semaphore - no low level code or OS specific library API's.

It case I'm overlooking something critical, has anybody else done something like this. If so, anybody willing to share that code - saving me some time in developing, unit testing and debugging my own Object Pascal based semaphore.

Regards,
- Graeme -

In our previous episode, Graeme Geldenhuys said:

Why do you not use the standard syncobjs implementations? In 2.6.2 they should be ok. (only the types exported by unixtype/unix/baseunix are wrong)

wrong)

We don't have semaphores yet in SyncObjs.

Regards,
Sven

If you just define your own semaphore class that contains the platform specific types and lock and unlock methods then you only need to add an additional "array[0..4] of Longint" after the "sem_t" field for FreeBSD. Then you should be okay.

Semaphore functionality seems pretty simple though, so I am thinking of creating my own Object Pascal based cross-platform semaphore - no low level code or OS specific library API's.

You need to use at least synchronisation primitives like mutexes otherwise it won't be threadsafe.

If you really want to do this the hard way you should read corresponding articles.

Regards,
Sven

Hello,

You can use some structure to lock an integer. `Some structure` can for example be a mutex, a critical section, some busy waiting loop based on CMPXCH, etc... Say that you lock the integer by calling `Lock;` and you unlock it by calling `UnLock;`. Then you can define a class TSemaphore like this:

===> Code Begin <===

Type
    TSemaphore = Class
    Private
        DaValue: Integer;
        Lock: TLockType;
    Public
        Constructor Create;        // sem_init
        Function GetValue: Integer;    // sem_getvalue
        Procedure Post;       // sem_post
        Function TryWait: Boolean; //sem_trywait
    End;
Constructor TSemaphore.Create;
Begin
    inherited Create;
    DaValue:= 0;
    //Initialize lock here to unlocked state.
End;
Function TSemaphore.GetValue;
Begin
    Lock;
    Result:= DaValue;
    UnLock;
End;
Procedure TSemaphore.Post;
Begin
    Lock;
    DaValue+= 1;
    UnLock;
End;
// True if the semaphore is hereby decremented; false otherwise
Function TSemaphore.TryWait: Boolean;
Begin
    Lock;
    If DaValue > 0 Then
    Begin
        DaValue-= 1;
        Result:= True;
    End Else
        Result:= False;
    UnLock;
End;
//True if this function returned immediately, false otherwise.
Function TSemaphore.Wait: Boolean;
Begin
    Result:= True;
    While True Do
    Begin
        Lock;
        If DaValue > 0 Then
        Begin
            DaValue-= 1;
            Break;
        End;
        Result:= False;
        UnLock;
    End;
End;

===> Code End <===

The only function missing is sem_timedwait, but this could easily be implemented by combining `nanosleep`, `trywait` and `timeofday`.

NOTE: The above code is not tested, it more of a thing which I just wrote, so you will probably find some syntax errors and possible race conditions; altough I doubt the latter.

Concerning the locking mechanism, you can uses mutex(en/es/ii) or you can do this by a busy waiting loop with an integer (of course there are other possibilities). To elaborate on the latter a bit more:

*  TLockType = Integer;
*  Initialization: `Lock:= 0;`
*  Lock & unlock:

===> Code Begin <===

Procedure WaitLockVar(var aLock: Integer);
Begin
    Repeat
    Until InterLockedCompareExchange(aLock, 1, 0) = 0;
End;
Procedure UnlockVar(var aLock: Integer);
Begin
    InterlockedExchange(aLock, 0);
End;

===> Code End <===

This last code is tested and works.

Hope it is of any use.

Once upon a time, on 02/06/2013 08:24 PM to be precise, Graeme Geldenhuys said:

MSEgui has a semaphore implementation. On Linux it uses the libc interface, on Windows an own implementation with a windows event object, lib/kernel/windows/msesysintf1.pas. Works so far, but with sync mechanics one never knows...

Martin

Sven Barth wrote

We don't have semaphores yet in SyncObjs.

Correct. FPC's SyncObjs unit has quite a few missing features compared to Delphi.

http://docwiki.embarcadero.com/Libraries/XE2/en/System.SyncObjs

Regards,
- Graeme -

Yes that will work, but it simply moves the problems or IFDEF's to a different location.

You need to use at least synchronisation primitives like mutexes otherwise it won't be threadsafe.

Yes, that is what I am planning. The class I am working with is a Thread Pool, so thread safety is a given. ;-)
At least I don't need cross-process semaphore support, only multiple threads in the same process. So this makes things a lot easier.

Regards,
- Graeme -

Thanks Ewald. What you described is exactly what I started, and had in mind. Thanks for your feedback.

Regards,
- Graeme -

Yes, I noticed that as well when I checked whether we have a platform independant semaphore implementation...
I've basically already put the extension of SyncObjs on my longterm ToDo list (so if someone wants to "beat" me, please feel free to do so).

Regards,
Sven

But the ifdefs will only be in one location. If I've understood you correctly, than your currently problem also is that you have the "{$ifdef windows}...{$elseif linux}...{$endif}" code in multiple places. This way you'd reduce that to one and rely on OS functionality nevertheless (which is known to work - if used correctly :P ).

Regards,
Sven

Sven Barth wrote

But the ifdefs will only be in one location.

I understand that, but there will be IFDEF's none the less. As I said, I hate IFDEF's in application/library code. They have their place in FPC source code, but I don't like them anywhere else. That's just me.

This way you'd reduce that to one and rely on OS functionality nevertheless (which is known to work - if used correctly :P ).

Having a clean Object Pascal based Semaphore implementation will be useful, and clean code. My unit testing and usage of it in tiOPF on Windows, Linux and FreeBSD will hopefully prove that it works too.

Once done, I'll post a link to the code. You are welcome to see if it will fit in the SyncObjs unit.

Regards,
- Graeme -

It might at least be useful for those systems that don't provide a native semaphore implementation (e.g. OS/2).

Regards,
Sven

It only works on some platforms (and even there it may change depending on which exact processor you are using). InterlockedExchange does not guarantee any kind of memory barrier, and hence you will get occasional data races on platforms with weakly consistent memory models. You have to add memory barriers.

Jonas

Hi Jonas,

Interesting, there is no mention of those limitations in the FPC 2.6.0 documentation. I looked in the RTL docs. It this is a concern, it is something that should be mentioned in the docs.

Do you know more specifically what platforms or CPU's are affected, so Michael could update the docs accordingly.

Does this limitation apply to all InterlockedXXX() functions?

Regards,
- Graeme -

Graeme Geldenhuys wrote

Interesting, there is no mention of those limitations in the FPC 2.6.0 documentation. I looked in the RTL docs. It this is a concern, it is something that should be mentioned in the docs.

That has nothing to do with the programming language. This is about low level computer architecture. We don't claim that our documentation is a processor architecture manual. The interlocked* routines are documented as offering atomic accesses to memory locations, which is correct. The text doesn't suggest in any way that they also provide memory barriers, nor that they are sufficient to guard critical sections. That's what Enter/LeaveCriticalSection are for.

Do you know more specifically what platforms or CPU's are affected, so Michael could update the docs accordingly.

It doesn't belong in our manuals. Anyone who wants to manually create low level thread synchronisation primitives will have to know a lot more about cpu architecture and memory consistency models then we could ever describe in our documentation.

Does this limitation apply to all InterlockedXXX() functions?

Yes.

Jonas

Jonas Maebe wrote

It doesn't belong in our manuals. Anyone who wants to manually create low level thread synchronisation primitives will have to know a lot more about cpu architecture and memory consistency models then we could ever describe in our documentation.

In case anyone is interested, some good documents on this topic are:
* http://www.rdrop.com/users/paulmck/scalability/paper/ordering.2007.09.19a.pdf
* http://www.kernel.org/doc/Documentation/memory-barriers.txt

Jonas

Once upon a time, on 02/07/2013 11:57 AM to be precise, Jonas Maebe said:

Well, I always thought that the InterLoackedCompareExchange boiles down to [**]
.Lock CMPXCHG

Or something quite like that. The `.Lock` there is the important part since this does insure a memory barier. Then the only problem would be the absence of the keyword `volatile` to ensure the integer is always in the same location but I've read somewhere, long ago, that fpc doesn't perform such optimizations.

So I don't see the issue really.

[**] I make this assumption because the documentation says it is done in a thread safe way (reference:
http://www.freepascal.org/docs-html/rtl/system/interlockedcompareexchange.html), and I don't see what other things can be made thread safe about this function except for a memory barrier.

It's only a memory barrier if you don't use SSE (or write-combined memory, but that's generally only the case for memory mapped video memory or so, and more of an issue for kernel mode code than for user space). Furthermore, FPC supports many more architectures than just x86, and on (virtually?) all other platforms the instructions for atomic accesses do not automatically imply any kind of memory barrier.

Jonas

Once upon a time, on 02/07/2013 01:46 PM to be precise, Jonas Maebe said:

Alright, this is getting interesting ;-) Yet I wonder: InterlockedCompareExchange is atomic, then you need to find a way to make sure that only one processor core (one thread in general) is accessing the memory that contains the integer/pointer. So, since InterlockedCompareExchange does not necessarily makes use of a memory barrier, how could it be done?

Also, in case I misunderstood you and you are trying to say that if I write using some instruction to a part of memory that contains or is contained the integer/pointer (so there is some memory overlap) then yes, I agree and it isn't a memory barrier anymore. But then again, who writes data to a locking variable other then the code that does the locking? (same goes for a simple `lock:= 5;` for example)

Furthermore, FPC supports many more architectures than just x86, and on (virtually?) all other platforms the instructions for atomic accesses do not automatically imply any kind of memory barrier.

Of course, I only used this piece of pseudo-assembly since it conveys the message enough to understand each other.

Paul McKenney has written quite a lot about this, I find his "Memory Barriers: a Hardware View for Software Hackers" very useful.

Henry

The interlocked* routines only guarantee that that particular value is updated in atomic way across multiple cores. It does not guarantee anything about memory access performed before or after that interlocked* call. The memory barriers are to ensure that all memory accesses before the lock-primitive (such as Enter/ LeaveCriticalSection) are also synchronized across all cores.

Please read the documents linked in one of my previous mails, they explain it in extensive detail.

Jonas

It may be a good idea for the documentation to explicitly say which functions do/do not imply memory barriers, since the linux kernel atomic_cmpxchg() and the Windows API guarantees full memory barriers, so people may expect that.

Henry

Most of the gcc __sync_* builtins guarantee a full barrier, too.

Henry

Once upon a time, on 02/07/2013 03:11 PM to be precise, Jonas Maebe said:

Right, I see your point, should be documented if you ask me (like `This call doesn't guarantee any kind of memory barrier.`). Altough I still don't see how you can make these calls atomic then (without the barrier)? I guess I'll have to take a peek at the source code for these calls on different platforms/architectures...

Graeme Geldenhuys wrote

Semaphore functionality seems pretty simple though, so I am thinking of creating my own Object Pascal based cross-platform semaphore - no low level code or OS specific library API's.

Progress... It was rather simple so far. I created a semaphore class, used TCriticalSection to wrap the access to the semaphore's internal count field. I API is similar, but not identical to TSynchroObject, so I opted to descend from TObject instead. If Timeout (in milliseconds) is specified, then Acquire will loop (ie: a blocking call). If the timeout lapses, False is returned. If Timeout = INFINITE, it will block until a successful acquire.

The units tests for this unit, and the tiPool unit tests in tiOPF (which includes threaded access) now passes for FreeBSD and Linux under 64-bit platforms. Next up I'll test under 32-bit systems and under Windows. If all passes, the code will be published in the tiOPF2 code repository.

I have a few more methods I want to add to this class, but below is what I needed for now to get tiOPF2 to work under FreeBSD.

---------------------------
unit tiSemaphore;
{$IFDEF fpc}
  {$mode objfpc}{$H+}
{$ENDIF}
interface
uses
  Classes, SysUtils, SyncObjs;
type
  TtiSemaphore = class(TObject)
  private
    FCount: LongWord;
    FMaximumCount: LongWord;
    FTimeout: LongWord;
    FCriticalSection: TCriticalSection;
    procedure   SetTimeout(AValue: LongWord);
  public
    constructor Create(const AMaximumCount: LongWord);
    destructor  Destroy; override;
    function    Acquire: Boolean;
    procedure   Release;
    property    Timeout: LongWord read FTimeout write SetTimeout;
    property    MaximumCount: LongWord read FMaximumCount;
    property    Count: LongWord read FCount;
  end;

...
---------------------------

Regards,
- Graeme -

Graeme Geldenhuys wrote

On 2013-02-06 19:24, Graeme Geldenhuys wrote: > Semaphore functionality seems pretty simple though, (...)

Not if you want high performance and multi-processor support.

Flávio Etrusco wrote

Not if you want high performance and multi-processor support.

I'll prefer _working_ code to start. Currently semaphores are broken in FPC+FreeBSD. My implementation at least works everywhere I have tested - without hacks or jumping through loops.

Regards,
- Graeme -

In our previous episode, Graeme Geldenhuys said:

I think I'll apply a patch before building the releases, and point the freebsd maintainer to the patch. (upload it to the dist/2.6.2 dir)

Don't forget to apply the patch to trunk as well :P

Regards,
Sven

Ewald wrote

Altough I still don't see how you can make these calls atomic then (without the barrier)?

On x86, it is impossible to perform an atomic access without a (partial) memory barrier that affects all memory (due to the behaviour of the "lock" prefix). On other architectures, the instructions for atomic accesses may only lock the cacheline or memory page containing the value to be atomically modified. I.e., they are only a barrier for that cacheline/page, not for the entire memory.

Or not even that: older SPARC architectures only had a test-and-set instruction, which only supported switching between 0 and 1. So basically you had to use a single global lock variable, which you locked using this instruction, then you modified the "atomic value" using regular instructions, and then unlocked the global lock again. So any atomic update conflicted with any other atomic update, regardless of where the values were located, and there was no memory barrier whatsoever (except for this one lock variable). And it only worked if all code in the entire program made use of the same global lock variable. It's similar for older ARM CPUs.

Jonas

Once upon a time, on 02/08/2013 04:02 PM to be precise, Jonas Maebe said:

Now I see, thanks for the explanation!

This might change with Haswell though (when the new instructions are used).

It is already not a memory barrier for certain SSE instructions, that's why I wrote "(partial)".

Jonas