[Bug libstdc++/24469] New: Possible race condition in mt_allocator causing SIGSEGV

[Bug libstdc++/24469] New: Possible race condition in mt_allocator causing SIGSEGV

[l_heldt at poczta dot onet dot pl]

In function deallocate(pointer _p, size_type __n) there is no synchronization
on __bin._M_used[__block->_M_thread_id] variable. During block deallocation
current thread decrements other threads _M_used variable without a lock.

This can result in undefined value of _M_used variable which than is used to
calculate __remove size. SIGSEGV shows up in following code:

while (__remove-- > 0)
        __tmp = __tmp->_M_next;

Since __remove variable might have undefined value code may surpass the end of
the list.

Increment and decrement operations are not atomic and should be placed in
critical section to avoid such situation.

Bug is very hard to reproduce. There must be many threads allocating memory and
deallocating other threads memory.

I have found this bug by code inspection - not gdb.


-- 
           Summary: Possible race condition in mt_allocator causing SIGSEGV
           Product: gcc
           Version: 3.4.2
            Status: UNCONFIRMED
          Severity: critical
          Priority: P1
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: l_heldt at poczta dot onet dot pl
  GCC host triplet: Linux 2.6.12 #4 SMP


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24469

[Bug libstdc++/24469] Possible race condition in mt_allocator causing SIGSEGV

[pcarlini at suse dot de]

------- Comment #1 from pcarlini at suse dot de  2005-10-21 09:02 -------
Yes, I think this is a real issue. We already discussed it briefly with Stefan
(the initial contributor of the mt_allocator code):

  http://gcc.gnu.org/ml/libstdc++/2004-07/msg00095.html

Thanks for reminding us the open problem!


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24469

[Bug libstdc++/24469] Possible race condition in mt_allocator causing SIGSEGV

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|critical                    |normal


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24469

[Bug libstdc++/24469] Possible race condition in mt_allocator causing SIGSEGV

[pcarlini at suse dot de]

------- Comment #2 from pcarlini at suse dot de  2005-10-27 10:16 -------
I can see a few possible strategies:
1- Arches supporting the new __sync_fetch_and_add (at least, i686, x86_64,
powerpc
   ia64, s390), could simply use it on the existing __bin._M_used.
2- Otherwise, a lock in _M_reclaim_block only when __block->_M_thread_id !=
   __thread_id. At the same time has to be changed _M_reserve_block too,
however,
   and it's tricky to do that without locking at every single allocation:
maybe,
   changing slightly the algorithm, an entire pool of blocks can be marked as
   used when obtained from operator new or the global list (at the beginning of
   _M_reserve_block).


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24469

[Bug libstdc++/24469] Possible race condition in mt_allocator causing SIGSEGV

[pcarlini at suse dot de]

------- Comment #3 from pcarlini at suse dot de  2005-11-15 12:02 -------
> 2- Otherwise, a lock in _M_reclaim_block only when __block->_M_thread_id !=
>    __thread_id. At the same time has to be changed _M_reserve_block too,
>    however, and it's tricky to do that without locking at every single  
>    allocation: maybe, changing slightly the algorithm, an entire pool of 
>    blocks can be marked as used when obtained from operator new or the
>    global list (at the beginning of _M_reserve_block).

Hi again. I mean to draft a version of this fix. Can you test it together
with the application which leads to SIGSEGVs? I don't think I have ready at
hand a testcase really stressing the allocator for this issue...


-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24469

[Bug libstdc++/24469] Possible race condition in mt_allocator causing SIGSEGV

[l_heldt at poczta dot onet dot pl]

------- Comment #4 from l_heldt at poczta dot onet dot pl  2005-11-15 12:26 -------
Unfortunately I cannot perform such test because it would require changing
stdlibc++ on many machines. 
My solution to this problem is setting GLIBCXX_FORCE_NEW variable before
starting application.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24469

[Bug libstdc++/24469] Possible race condition in mt_allocator causing SIGSEGV

[pcarlini at suse dot de]

------- Comment #5 from pcarlini at suse dot de  2005-11-15 12:31 -------
(In reply to comment #4)
> Unfortunately I cannot perform such test because it would require changing
> stdlibc++ on many machines.

Out of curiosity: why many and not just one (and optionally, of course, along
the existing compiler/library). If you want I can give details about how to
do that in a safe way.

> My solution to this problem is setting GLIBCXX_FORCE_NEW variable before
> starting application.

Too bad that the distro that you are using configures mt_allocator by
default.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24469

[Bug libstdc++/24469] Possible race condition in mt_allocator causing SIGSEGV

[bkoz at gcc dot gnu dot org]

------- Comment #6 from bkoz at gcc dot gnu dot org  2006-03-03 17:52 -------
Created an attachment (id=10963)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=10963&action=view)
make _M_used, _M_free atomic


Hey. This is a patch to make these operations atomic. It's based on top of
another set of patches that improve scalability, and some cleanups. 

I'm awaiting the assignments for some of this, and when I do I'll stagger that
part in first. 

The use of atomic updates kills performance on x86. Perhaps there is a better
way to do this.

-benjamin


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24469

[Bug libstdc++/24469] Possible race condition in mt_allocator causing SIGSEGV

[bkoz at gcc dot gnu dot org]

------- Comment #7 from bkoz at gcc dot gnu dot org  2006-03-03 17:53 -------
Created an attachment (id=10964)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=10964&action=view)
sources, as patched with p.20060303

Tarball of the patched sources.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24469

[Bug libstdc++/24469] Possible race condition in mt_allocator causing SIGSEGV

[pcarlini at suse dot de]

------- Comment #8 from pcarlini at suse dot de  2006-08-31 18:08 -------
Now I know how to fix it...


-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pcarlini at suse dot de
                   |dot org                     |
             Status|WAITING                     |UNCONFIRMED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24469

[Bug libstdc++/24469] Possible race condition in mt_allocator causing SIGSEGV

[paolo at gcc dot gnu dot org]

------- Comment #9 from paolo at gcc dot gnu dot org  2006-09-02 08:31 -------
Subject: Bug 24469

Author: paolo
Date: Sat Sep  2 08:31:45 2006
New Revision: 116660

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=116660
Log:
2006-09-02  Paolo Carlini  <pcarlini@suse.de>
            Richard Guenther  <rguenther@suse.de>

        PR libstdc++/24469
        * src/mt_allocator.cc (__pool<true>::_M_reserve_block,
        __pool<true>::_M_reclaim_block): Fix the logic to avoid
        races, exploit atomic counters stored in second part of
        the memory pointed by _M_used.
        (__pool<true>::_M_initialize): Adjust _M_used allocation.
        * include/ext/mt_allocator.h (__pool<true>::_Bin_record):
        Update comment.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/ext/mt_allocator.h
    trunk/libstdc++-v3/src/mt_allocator.cc


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24469

[Bug libstdc++/24469] Possible race condition in mt_allocator causing SIGSEGV

[pcarlini at suse dot de]

------- Comment #10 from pcarlini at suse dot de  2006-09-02 08:34 -------
Fixed for 4.2.0.


-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.2.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24469