is malloc thread-safe??

[Nehil]

Hi all,

i'm the same Nehil who was developing a conservative garbage collector
for C and was using Mark and Sweep algorithm.

I'm now aiming to extend it for multithreaded environment. Plz note
that i'm not making the garbage collector multithreaded but enhancing
the features so that it can also work for multithreaded programs.

can u please tell me some points which i should consider while
enhancing the garbage collector.

one more query i want to ask is " IS MALLOC THREAD_SAFE or NOT ? "
let say in a user program there are two threads A and B. now A calls
malloc and inside malloc it came to know about a free block which can
fulfill the requested bytes of memory. just then B calls malloc and
came to know the same block.
how malloc handels this situation cause either A or B will have the
false information about the free block. does malloc handel such
situations?
can u please tell some other situations.

Thanks.

 

[jacob navia]

Hi all,

i'm the same Nehil who was developing a conservative garbage collector
for C and was using Mark and Sweep algorithm.

I'm now aiming to extend it for multithreaded environment. Plz note
that i'm not making the garbage collector multithreaded but enhancing
the features so that it can also work for multithreaded programs.

can u please tell me some points which i should consider while
enhancing the garbage collector.

one more query i want to ask is " IS MALLOC THREAD_SAFE or NOT ? "
let say in a user program there are two threads A and B. now A calls
malloc and inside malloc it came to know about a free block which can
fulfill the requested bytes of memory. just then B calls malloc and
came to know the same block.
how malloc handels this situation cause either A or B will have the
false information about the free block. does malloc handel such
situations?
can u please tell some other situations.

Thanks.

Some implementations are thread safe, others not.
The best way would be to build your own semaphore
handling stuff, and make it thread safe yourself.

In some operating systems like windows, you can call APIs that are
documented as thread safe.

 

[Ian Collins]

one more query i want to ask is " IS MALLOC THREAD_SAFE or NOT ? "

The answer lies in your system's documentation.

 

[Chris Dollin]

Hi all,

i'm the same Nehil who was developing a conservative garbage collector
for C and was using Mark and Sweep algorithm.

I'm now aiming to extend it for multithreaded environment. Plz note
that i'm not making the garbage collector multithreaded but enhancing
the features so that it can also work for multithreaded programs.

can u please tell me some points which i should consider while
enhancing the garbage collector.

one more query i want to ask is " IS MALLOC THREAD_SAFE or NOT ? "

C doesn't have threads, so malloc is automatically thread-safe.

If your /implementation/ has threads, then I earnestly hope it documents
whether it's malloc (and umpty-seven other library functions) are
thread-safe or not. But, apart from my empty answer above, you'll
have to appeal to each implementation.

Maybe you can stick with whatever POSIX says.

 

[pete]

Chris Dollin wrote:

C doesn't have threads, so malloc is automatically thread-safe.

C has this to say about reentrancy,
"The functions in the standard library are not
guaranteed to be reentrant and may modify objects with
static storage duration."

A quick look at:

http://www.google.com/search?hl=en&ie=ISO-8859-1&safe=off&q=reentrancy+thread+safety

suggests that there is a connection between reentrancy
and thread safety, So I would say that malloc is not thread safe.

 

[Nehil]

C has this to say about reentrancy,
"The functions in the standard library are not
guaranteed to be reentrant and may modify objects with
static storage duration."

A quick look at:

http://www.google.com/search?hl=en&ie=ISO-8859-1&safe=off&q=reentranc...

suggests that there is a connection between reentrancy
and thread safety, So I would say that malloc is not thread safe.

Thanks all, for your answers.

So malloc is NOT thread safe. But can i know some conditions which i
should consider to make my own function thread safe.
i've developd my own memory allocator and now want to make it safe for
multithreaded programs.
can i get the key points to be considered.
Thanks.

 

[pete]

Thanks all, for your answers.

So malloc is NOT thread safe. But can i know some conditions which i
should consider to make my own function thread safe.
i've developd my own memory allocator and now want to make it safe for
multithreaded programs.
can i get the key points to be considered.
Thanks.

Now you're really going to have to find a newsgroup
that deals with threads.
This one doesn't.
Threads may or may not be part of POSIX, but they're not part of C.

 

[Ian Collins]

Thanks all, for your answers.

So malloc is NOT thread safe. But can i know some conditions which i
should consider to make my own function thread safe.

Just because the C standard makes no mention of threads, that doesn't
stop implementations from using them. As I said before, read your
system's documentation, this is more of a platform specific question,
than a C one.

 

[Chris Thomasson]

Hi all,

[...]

You can't count on malloc being thread-safe unless the documentation for the
platform explicitly states otherwise. There are ways to create scaleable
memory allocators that can handle any number of threads, but that's another
issue:

http://softwarecommunity.intel.com/isn/Community/en-US/forums/thread/30235584.aspx

 

[Richard Tobin]

So malloc is NOT thread safe.

Any implementation that provides threads is likely to to provide a
thread-safe malloc(), since it would be unusable otherwise.

But can i know some conditions which i
should consider to make my own function thread safe.
i've developd my own memory allocator and now want to make it safe for
multithreaded programs.

This is difficult: you will need to write appropriate code for each
implementation.

-- Richard

 

[tedu]

C has this to say about reentrancy,
"The functions in the standard library are not
guaranteed to be reentrant and may modify objects with
static storage duration."

A quick look at:

http://www.google.com/search?hl=en&ie=ISO-8859-1&safe=off&q=reentranc...

suggests that there is a connection between reentrancy
and thread safety, So I would say that malloc is not thread safe.

this is misleading. many malloc implementations are thread safe, but
not reentrant. reentrant is not a synonym for multi-threaded.

 

[¬a\\/b]

Any implementation that provides threads is likely to to provide a
thread-safe malloc(), since it would be unusable otherwise.


This is difficult: you will need to write appropriate code for each
implementation.

-- Richard

char* mymalloc(int a)
{static unsigned here=0;
char *v;
if(a<0) return 0;
la:;
if(here==1)
{sleep(1); goto la;}
else
{++here;
if(here>=2)
{here=0; goto la;}
v=malloc(a);
here=0; return v;
}
}

this is thread safe?
there is a way to do a thread safe malloc in few lines?

 

[Richard Tobin]

char* mymalloc(int a)
{static unsigned here=0;
char *v;
if(a<0) return 0;
la:;
if(here==1)
{sleep(1); goto la;}
else
{++here;
if(here>=2)
{here=0; goto la;}
v=malloc(a);
here=0; return v;
}
}

this is thread safe?

I haven't looked closely enough to see whather there are race conditions,
but in any case

(a) you would need to declare "here" to be volatile
(b) you would need to ensure that it was an atomic type (sig_atomic_t
should work)
(c) calling sleep(1) in an allocator is likely to result in disappointing
performance, even if it allows other threads to run.

It will usually make more sense to use an implementation-dependent
locking mechanism.

-- Richard

 

[Chris Torek]

¬a\\/b <[email protected]> wrote:

[this guy is in my kill-file but Richard Tobin, below, is not, and
I need to quote at least a little code]

No.

I haven't looked closely enough to see whather there are race conditions,

There are. In particular:

but in any case

(a) you would need to declare "here" to be volatile
(b) you would need to ensure that it was an atomic type (sig_atomic_t
should work)

Using "volatile sig_atomic_t" is only guaranteed against signals,
and only for simple assignments.

In practice, the code really fails on many real implementations --
those that use a load/store model in hardware, and do arithmetic
only in registers -- even when using "volatile sig_atomic_t",
because the C-level code:

++here;

translates into the machine-code sequence:

load <memaddr>, reg # where <memaddr> is the static variable "here"
add reg, 1, reg
store reg, <memaddr>

since there is no way to add a value directly to a memory location.
If two separate threads that share the variable both execute the
"load" instruction simultaneously (presumably on two separate CPUs),
then both execute the "add", then both execute the "store", the
variable will increment by 1, even though two threads have modified
it. (Even if there is only one CPU, if one thread executes the
"load" and maybe "add", but is then interrupted by the second before
it can do the "store", the second thread can load, add, and store,
and then the first thread will, upon being resumed, execute its
store.)

This race-window is quite small, which makes debugging extraordinarily
difficult. (Those who have built SMP systems are familiar with
the problem. )

(c) calling sleep(1) in an allocator is likely to result in disappointing
performance, even if it allows other threads to run.

It will usually make more sense to use an implementation-dependent
locking mechanism.

Indeed. In fact, given Standard C (and even non-Standard Extended
C on some systems), an implementation-dependent locking mechanism
is in fact required on many machines. (Some C compilers have no
way to generate the machine's special atomic instruction(s), such
as the V7 SPARC "ldstub" instruction. In these cases the special
mechanisms are usually coded in C-callable assembly.)

 

[¬a\\/b]

¬a\\/b <[email protected]> wrote:

[this guy is in my kill-file but Richard Tobin, below, is not, and
I need to quote at least a little code]

the guy above is in the kill-file in my mind too, i read only some
line if not too long

No.



There are. In particular:


Using "volatile sig_atomic_t" is only guaranteed against signals,
and only for simple assignments.

In practice, the code really fails on many real implementations --
those that use a load/store model in hardware, and do arithmetic
only in registers -- even when using "volatile sig_atomic_t",
because the C-level code:

++here;

translates into the machine-code sequence:

load <memaddr>, reg # where <memaddr> is the static variable "here"
add reg, 1, reg
store reg, <memaddr>

since there is no way to add a value directly to a memory location.
If two separate threads that share the variable both execute the
"load" instruction simultaneously (presumably on two separate CPUs),
then both execute the "add", then both execute the "store", the
variable will increment by 1, even though two threads have modified
it.

wrong:
so where is the problem "here>=2" so the second "if(here>=2)"
goes to loop that wait.

there is a problem when n>=2 threads in n-cpu are in sincronize and
call for ++here all thoghter, and so for always

1-cpu{++here, ++here, etc etc}
time | |
-------------------------------------------------->
| |
2-cpu{++here, ++here, etc, etc}

but if there is "a time" where only one thread execute "++here" that
thread has malloc.
so there is only one thread that can use that resource
if you are not agree; this is the right time to speak something
wrong anhother time...

anhother problem is when the resurce is call more time that cpu can
displace because there is not a queue of calls
and can be one tread not have the resource for too many time

i have not read the rest

 

[Ben Bacarisse]

¬a\\/b <[email protected]> wrote:

[this guy is in my kill-file but Richard Tobin, below, is not, and
I need to quote at least a little code]

the guy above is in the kill-file in my mind too, i read only some
line if not too long

Even if it only a mental kill-file, remove him if you want to fix this
program.

wrong:
so where is the problem "here>=2" so the second "if(here>=2)"
goes to loop that wait.

No. I can't see any way to explain it better than Chris Torek already
has, so I can only suggest to re-read his message.

 

[¬a\\/b]

¬a\\/b <[email protected]> wrote:

[this guy is in my kill-file but Richard Tobin, below, is not, and
I need to quote at least a little code]

the guy above is in the kill-file in my mind too, i read only some
line if not too long

No.



There are. In particular:


Using "volatile sig_atomic_t" is only guaranteed against signals,
and only for simple assignments.

In practice, the code really fails on many real implementations --
those that use a load/store model in hardware, and do arithmetic
only in registers -- even when using "volatile sig_atomic_t",
because the C-level code:

++here;

translates into the machine-code sequence:

load <memaddr>, reg # where <memaddr> is the static variable "here"
add reg, 1, reg
store reg, <memaddr>

since there is no way to add a value directly to a memory location.
If two separate threads that share the variable both execute the
"load" instruction simultaneously (presumably on two separate CPUs),
then both execute the "add", then both execute the "store", the
variable will increment by 1, even though two threads have modified
it.

wrong:
so where is the problem "here>=2" so the second "if(here>=2)"
goes to loop that wait.

it seems i did some errors but what is the problem with
"my_threadsafe_f" function?

there was someone that said this is not ok in a multi processor pc
but in my dual core windows xp pc all seems ok

#include <stdio.h>
#include <windows.h>
#include <time.h>

#define F for
#define uns unsigned

int __stdcall LockDword(uns* mem, uns NThread);
void __stdcall UnlockDword(uns* mem);

uns resource=0;
uns fine=0;

time_t ti, tf;

void my_threadsafe_f(int siz, void* a)
{unsigned int aa;
static uns here=0;

aa= *(uns*)a; (void) siz;
la:;
Sleep(0);
if( LockDword(&here, aa)==0 || here!=aa)
goto la;
else
{++resource;
UnlockDword(&here);
}
}

DWORD WINAPI xx(void* a)
{uns x;
char szMsg[80];

// 100000 * 88 = 8800000
F(x=0; x<100000; ++x)
my_threadsafe_f(0, a);
++fine;
return 0;
}


void error_exit(char* a)
{if(a) MessageBox( NULL, a, "Exit", MB_OK ); exit(0);}


VOID main( VOID )
{
SECURITY_ATTRIBUTES scat;
uns i;
DWORD dwThreadId[900];
HANDLE hThread[900], even;
uns dwThrdParam[900];
char msg[512];
char sg[512];

MessageBox( NULL, "I'm in ", " MAIN ", MB_OK );

ti=time(0);
F(i=0; i<88; ++i)
{dwThrdParam=i;
hThread = CreateThread(
NULL, // no security attributes
0, // use default stack size
xx, // thread function
&dwThrdParam, // argument to thread function
0, // use default creation flags
&dwThreadId
);
if(hThread==0)
{wsprintf( msg, "ThreadFunct %d Error\n", i);
if(i!=0)
{F(--i;i!=0;--i)
CloseHandle( hThread );
CloseHandle( hThread[0] );
}
error_exit(msg);
}
}

F(i=87; i!=-1; --i)
WaitForSingleObject(
hThread, // handle of object to wait for
INFINITE // time-out interval in milliseconds
);
tf=time(0);

F(i=0;i<88; ++i); CloseHandle( hThread );

sprintf( sg, "resource=%u ;;; fine=%u time=%g",
resource, fine, difftime(tf, ti) );
MessageBox( NULL, sg, "Threads ", MB_OK );
// Sleep(900);

ti=time(0);
F(i=0; i<88000000; ++i)
resource+=i%30;
tf=time(0);

sprintf( sg, " 2 time=%g %u ", difftime(tf, ti), resource/2 );
MessageBox( NULL, sg, "Threads ", MB_OK );

}
-------------------------------------------

; nasmw -fobj thisfile.asm

section _DATA public use32 class=DATA
global LockDword, UnlockDword

section _TEXT public use32 class=CODE


; int LockDword(uns* mem, uns NThread)
; Se effettua il lock ritorna 1(CF==0)
; Se non effettua il lock ritorna 0(CF==1)
; 0c, 4r, 8ra, 12P_mem, 16P_NThread
LockDword:
push ecx
push edx
%define @mem [esp+12]
%define @NThread [esp+16]
mov edx, @mem
xor eax, eax
cmp dword[edx], 0
jne .1
mov ecx, @NThread
lock cmpxchg dword[edx] , ecx
jnz .1
mov eax, 1
clc
jmp short .2
..1: ; 0 CF==1 Error
xor eax, eax
stc
..2: ; 1 CF==0 0k
%undef @mem
%undef @NThread
pop edx
pop ecx
ret 8

; void UnlockDword(uns* mem)
; 0r, 4a, 8ra, 12P_mem
UnlockDword:
push eax
push edx
mov eax, [esp+12]
xor edx, edx
lock xchg [eax] , edx
pop edx
pop eax
ret 4

 

[Chris Thomasson]

What they heck are you trying to do? You don't need any mutual exclusion
technique to implement a scaleable multi-threaded memory allocator!!!!!!!

Man!

 

[¬a\\/b]

it seems i did some errors in numbering the threads too

but what is the problem with
"my_threadsafe_f" function?

there was someone that said this is not ok in a multi processor pc
but in my dual core windows xp pc all seems ok

#include <stdio.h>
#include <windows.h>
#include <time.h>

#define F for
#define uns unsigned

int __stdcall LockDword(uns* mem, uns NThread);
void __stdcall UnlockDword(uns* mem);

uns resource=0;
uns fine=0;

time_t ti, tf;

void my_threadsafe_f(int siz, void* a)
{unsigned int aa;
static uns here=0;

aa= *(uns*)a; (void) siz;
la:;
Sleep(0);
if( LockDword(&here, aa)==0 || here!=aa)
goto la;
else
{++resource;
UnlockDword(&here);
}
}

DWORD WINAPI xx(void* a)
{uns x;
char szMsg[80];

// 100000 * 88 = 8800000
F(x=0; x<100000; ++x)
my_threadsafe_f(0, a);
++fine;
return 0;
}


void error_exit(char* a)
{if(a) MessageBox( NULL, a, "Exit", MB_OK ); exit(0);}


VOID main( VOID )
{
SECURITY_ATTRIBUTES scat;
uns i;
DWORD dwThreadId[900];
HANDLE hThread[900], even;
uns dwThrdParam[900];
char msg[512];
char sg[512];

MessageBox( NULL, "I'm in ", " MAIN ", MB_OK );

ti=time(0);
F(i=0; i<88; ++i)
{dwThrdParam=i+1;
hThread = CreateThread(
NULL, // no security attributes
0, // use default stack size
xx, // thread function
&dwThrdParam, // argument to thread function
0, // use default creation flags
&dwThreadId
);
if(hThread==0)
{wsprintf( msg, "ThreadFunct %d Error\n", i);
if(i!=0)
{F(--i;i!=0;--i)
CloseHandle( hThread );
CloseHandle( hThread[0] );
}
error_exit(msg);
}
}

F(i=87; i!=-1; --i)
WaitForSingleObject(
hThread, // handle of object to wait for
INFINITE // time-out interval in milliseconds
);
tf=time(0);

F(i=0;i<88; ++i); CloseHandle( hThread );

sprintf( sg, "resource=%u ;;; fine=%u time=%g",
resource, fine, difftime(tf, ti) );
MessageBox( NULL, sg, "Threads ", MB_OK );
// Sleep(900);

ti=time(0);
F(i=0; i<88000000; ++i)
resource+=i%30;
tf=time(0);

sprintf( sg, " 2 time=%g %u ", difftime(tf, ti), resource/2 );
MessageBox( NULL, sg, "Threads ", MB_OK );

}
-------------------------------------------

; nasmw -fobj thisfile.asm

section _DATA public use32 class=DATA
global LockDword, UnlockDword

section _TEXT public use32 class=CODE


; int LockDword(uns* mem, uns NThread)
; Se effettua il lock ritorna 1(CF==0)
; Se non effettua il lock ritorna 0(CF==1)
; NB
; il numero di tread è un valore che varia
; da 1 a UNS_MAX
; il valore 0 significa: "mem" non usata dai thread
; 0c, 4r, 8ra, 12P_mem, 16P_NThread
LockDword:
push ecx
push edx
%define @mem [esp+12]
%define @NThread [esp+16]
mov edx, @mem
xor eax, eax
cmp dword[edx], 0
jne .1
mov ecx, @NThread
lock cmpxchg dword[edx] , ecx
jnz .1
mov eax, 1
clc
jmp short .2
..1: ; 0 CF==1 Error
xor eax, eax
stc
..2: ; 1 CF==0 0k
%undef @mem
%undef @NThread
pop edx
pop ecx
ret 8

; void UnlockDword(uns* mem)
; 0r, 4a, 8ra, 12P_mem
UnlockDword:
push eax
push edx
mov eax, [esp+12]
xor edx, edx
lock xchg [eax] , edx
pop edx
pop eax
ret 4

 

[¬a\\/b]

it seems i did some errors in numbering the threads too

but what is the problem with
"my_threadsafe_f" function?

i all ears for to hear who can modify "DWORD WINAPI xx(void* a)"
function in the way 88 threads and the 88 loops create some "dead
lock" or something that slow down my dual core cpu more than necessary

this is the right time to speak: in a example
show if you are so good in programming here if you can