Opened 18 years ago

Closed 18 years ago

Last modified 17 months ago

#8 closed bug (Fixed)

Regex failure

Reported by: xoltar Owned by: simonmar
Priority: normal Milestone:
Component: hslibs/text Version: 5.02
Keywords: Cc:
Operating System: Architecture:
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

Working through samples from the Great Computer
Language Shootout, I wrote a Haskell program which is
supposed to be basically equivalent to the perl program at:

http://www.bagley.org/~doug/shootout/bench/regexmatch/regexmatch.perl

And in fact I copied the regular expression directly
from the perl example and used search and replace to
change single backslashes to double backslashes to deal
with Haskell vs. Perl strings.

But the regex fails to match where it should. Since I
copied the regex directly from the working perl script,
I'm pretty sure it's correct. Since the RegexString
modules says the regex syntax is that of Perl, I'm
reporting it as a bug.

The haskell file is attached. It is intended to be run
with an integer command line argument (2 is fine), and
input piped from the file at:

http://www.bagley.org/data/shootout/regexmatch/Input

I'm on Windows NT 4.0 sp4 and GHC 5.02.

Attachments (1)

regexmatch.8.hs (1.6 KB) - added by xoltar 18 years ago.

Download all attachments as: .zip

Change History (5)

Changed 18 years ago by xoltar

Attachment: regexmatch.8.hs added

comment:1 Changed 18 years ago by simonmar

Status: assignedclosed
Logged In: YES 
user_id=48280

The documentation is incorrect to say that the syntax is 
that of Perl, although it may have been right at the time 
of writing.  The regex library doesn't implement Perl's 
special regex extensions (i.e. the (?...) syntax).  I'll 
update the docs to say this.

comment:2 Changed 8 years ago by karel.gardas@…

commit 5cf87b43993f5fd2884755cd16268c2f40572026

Author: Karel Gardas <karel.gardas@centrum.cz>
Date:   Thu Jul 14 22:21:09 2011 +0200

    disable for now ARM specific target data layout and triple
    
    This patch disables ARM specific target data layout and triple.
    The reason for this is that LLVM asserts on some files if this
    is in use. The assert looks:
    Formal argument #8 has unhandled type i32UNREACHABLE executed at
    /llvm-ghc-arm/lib/CodeGen/CallingConvLower.cpp:81!

 compiler/llvmGen/LlvmCodeGen/Ppr.hs |   10 +++++-----
 1 files changed, 5 insertions(+), 5 deletions(-)

comment:3 Changed 4 years ago by Sergei Trofimovich <siarheit@…>

In 74897dec/ghc:

Make rts/ThreadLabels.c threadsafe for debug runtime.

rts/ThreadLabels.c has a global hashtable for each
running haskell thread. It's not synchronized across
OS threads.

Was discovered when ran -debug build of ghc itself as:

    $ ghc-stage2 -j8 +RTS -A256M -l

and glibc detected double-free corruption:

    #2  in __libc_message (do_abort=do_abort@entry=2,
        fmt=fmt@entry=0x7fe0bcebf368 "*** Error in `%s': %s: 0x%s ***\n")
    #3  in malloc_printerr (action=3, str=0x7fe0bcebf4c0 "double free or corruption (fasttop)",
        ptr=<optimized out>)
    #4  in _int_free (av=<optimized out>, p=<optimized out>, have_lock=0)
    #5  in stgFree (p=0x7fe060001820) at rts/RtsUtils.c:108
    #6  in freeHashTable (table=0x5929320, freeDataFun=0x36374df <stgFree>) at rts/Hash.c:360
    #7  in freeThreadLabelTable () at rts/ThreadLabels.c:37
    #8  in hs_exit_ (wait_foreign=rtsFalse) at rts/RtsStartup.c:403
    #9  in shutdownHaskellAndExit (n=0, fastExit=0) at rts/RtsStartup.c:481
    #10 in hs_main (...) at rts/RtsMain.c:91
    #11 in main (...) at ghc/hschooks.c:63

Exposed itself after commit:

> commit f6866824ce5cdf5359f0cad78c49d65f6d43af12
> Author: Sergei Trofimovich <slyfox@gentoo.org>
> Date:   Mon Aug 4 08:10:33 2014 -0500
>
>     ghc --make: add nicer names to RTS threads (threaded IO manager, make workers)

Signed-off-by: Sergei Trofimovich <siarheit@google.com>

Reviewers: austin, simonmar, ezyang, bgamari

Reviewed By: ezyang, bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1146

comment:4 Changed 17 months ago by Ömer Sinan Ağacan <omeragacan@…>

Type of failure: None/Unknown

In c6fbac6/ghc:

Fix a race between GC threads in concurrent scavenging

While debugging #15285 I realized that free block lists (free_list in
BlockAlloc.c) get corrupted when multiple scavenge threads allocate and
release blocks concurrently. Here's a picture of one such race:

    Thread 2 (Thread 32573.32601):
    #0  check_tail
        (bd=0x940d40 <stg_TSO_info>) at rts/sm/BlockAlloc.c:860
    #1  0x0000000000928ef7 in checkFreeListSanity
        () at rts/sm/BlockAlloc.c:896
    #2  0x0000000000928979 in freeGroup
        (p=0x7e998ce02880) at rts/sm/BlockAlloc.c:721
    #3  0x0000000000928a17 in freeChain
        (bd=0x7e998ce02880) at rts/sm/BlockAlloc.c:738
    #4  0x0000000000926911 in freeChain_sync
        (bd=0x7e998ce02880) at rts/sm/GCUtils.c:80
    #5  0x0000000000934720 in scavenge_capability_mut_lists
        (cap=0x1acae80) at rts/sm/Scav.c:1665
    #6  0x000000000092b411 in gcWorkerThread
        (cap=0x1acae80) at rts/sm/GC.c:1157
    #7  0x000000000090be9a in yieldCapability
        (pCap=0x7f9994e69e20, task=0x7e9984000b70, gcAllowed=true) at rts/Capability.c:861
    #8  0x0000000000906120 in scheduleYield
        (pcap=0x7f9994e69e50, task=0x7e9984000b70) at rts/Schedule.c:673
    #9  0x0000000000905500 in schedule
        (initialCapability=0x1acae80, task=0x7e9984000b70) at rts/Schedule.c:293
    #10 0x0000000000908d4f in scheduleWorker
        (cap=0x1acae80, task=0x7e9984000b70) at rts/Schedule.c:2554
    #11 0x000000000091a30a in workerStart
        (task=0x7e9984000b70) at rts/Task.c:444
    #12 0x00007f99937fa6db in start_thread
        (arg=0x7f9994e6a700) at pthread_create.c:463
    #13 0x000061654d59f88f in clone
        () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:95

    Thread 1 (Thread 32573.32573):
    #0  checkFreeListSanity
        () at rts/sm/BlockAlloc.c:887
    #1  0x0000000000928979 in freeGroup
        (p=0x7e998d303540) at rts/sm/BlockAlloc.c:721
    #2  0x0000000000926f23 in todo_block_full
        (size=513, ws=0x1aa8ce0) at rts/sm/GCUtils.c:264
    #3  0x00000000009583b9 in alloc_for_copy
        (size=513, gen_no=0) at rts/sm/Evac.c:80
    #4  0x000000000095850d in copy_tag_nolock
        (p=0x7e998c675f28, info=0x421d98 <Main_Large_con_info>, src=0x7e998d075d80, size=513,
        gen_no=0, tag=1) at rts/sm/Evac.c:153
    #5  0x0000000000959177 in evacuate
        (p=0x7e998c675f28) at rts/sm/Evac.c:715
    #6  0x0000000000932388 in scavenge_small_bitmap
        (p=0x7e998c675f28, size=1, bitmap=0) at rts/sm/Scav.c:271
    #7  0x0000000000934aaf in scavenge_stack
        (p=0x7e998c675f28, stack_end=0x7e998c676000) at rts/sm/Scav.c:1908
    #8  0x0000000000934295 in scavenge_one
        (p=0x7e998c66e000) at rts/sm/Scav.c:1466
    #9  0x0000000000934662 in scavenge_mutable_list
        (bd=0x7e998d300440, gen=0x1b1d880) at rts/sm/Scav.c:1643
    #10 0x0000000000934700 in scavenge_capability_mut_lists
        (cap=0x1aaa340) at rts/sm/Scav.c:1664
    #11 0x00000000009299b6 in GarbageCollect
        (collect_gen=0, do_heap_census=false, gc_type=2, cap=0x1aaa340, idle_cap=0x1b38aa0)
        at rts/sm/GC.c:378
    #12 0x0000000000907a4a in scheduleDoGC
        (pcap=0x7ffdec5b5310, task=0x1b36650, force_major=false) at rts/Schedule.c:1798
    #13 0x0000000000905de7 in schedule
        (initialCapability=0x1aaa340, task=0x1b36650) at rts/Schedule.c:546
    #14 0x0000000000908bc4 in scheduleWaitThread
        (tso=0x7e998c0067c8, ret=0x0, pcap=0x7ffdec5b5430) at rts/Schedule.c:2537
    #15 0x000000000091b5a0 in rts_evalLazyIO
        (cap=0x7ffdec5b5430, p=0x9c11f0, ret=0x0) at rts/RtsAPI.c:530
    #16 0x000000000091ca56 in hs_main
        (argc=1, argv=0x7ffdec5b5628, main_closure=0x9c11f0, rts_config=...) at rts/RtsMain.c:72
    #17 0x0000000000421ea0 in main
        ()

In particular, dbl_link_onto() which is used to add a freed block to a
doubly-linked free list is not thread safe and corrupts the list when
called concurrently.

Note that thread 1 is to blame here as thread 2 is properly taking the
spinlock. With this patch we now take the spinlock when freeing a todo
block in GC, avoiding this race.

Test Plan:
- Tried slow validate locally: this patch does not introduce new failures.
- circleci: https://circleci.com/gh/ghc/ghc-diffs/283 The test got killed
  because it took 5 hours but T7919 (which was previously failing on circleci)
  passed.

Reviewers: simonmar, bgamari, erikd

Reviewed By: simonmar

Subscribers: rwbarton, carter

GHC Trac Issues: #15285

Differential Revision: https://phabricator.haskell.org/D5115
Note: See TracTickets for help on using tickets.