Ticket #1399 (closed bug: fixed)

Opened 12 years ago

Last modified 12 years ago

Array unshift/access broken

Reported by: plobsing Owned by:
Priority: normal Milestone:
Component: core Version: trunk
Severity: medium Keywords:
Cc: Language:
Patch status: Platform:

Description

The Array PMC breaks (segfaults) when a large number of PMCs are unshifted onto it and then are accessed. I suspect that this is in the resizing code because no such error occurs when the array is pre-allocated.

Attachments

array_unshift_test.pir Download (0.5 KB) - added by plobsing 12 years ago.
simple PIR file demonstrating the issue
debug.patch Download (1.1 KB) - added by kurahaupo 12 years ago.
How the instrumenting was done
debug.txt Download (35.5 KB) - added by kurahaupo 12 years ago.
Annotated output from (instrumented) "parrot -G array_unshift_test.pir"

Change History

Changed 12 years ago by plobsing

simple PIR file demonstrating the issue

  Changed 12 years ago by jkeenan

  • component changed from none to core

  Changed 12 years ago by kurahaupo

Firstly, I notice that the array is always missing 1920 elements, even if I double the size to 200000.

Secondly, when I instrumented Parrot_pmc_array_unshift (by putting a "printf" in the conditional block where "start" is 0) it actually failed during the build, at

./parrot -o runtime/parrot/include/parrotlib.pbc runtime/parrot/library/parrotlib.pir

in much the same manner, after just two "unshift" chunk insertions. However since I still had runtime files from the unadulterated build, I could still run the test file.

It's possible that the instrumentation itself causes the new form of error, but I would like to investigate whether GCC is over-optimizating something.

  Changed 12 years ago by kurahaupo

Sorry, it appears that using "printf" screws up freeze/thaw. I've changed it to fprintf(stderr...) and it now builds cleanly -- albeit noisily.

I'll upload a new debug profile after I've tweaked it a bit more...

Changed 12 years ago by kurahaupo

How the instrumenting was done

Changed 12 years ago by kurahaupo

Annotated output from (instrumented) "parrot -G array_unshift_test.pir"

  Changed 12 years ago by plobsing

Looking around src/list.c I noticed that get_chunk() has two implementations: normal and 'SLOW_AND_BORING'. When I compile with SLOW_AND_BORING defined, the bug goes away.

The quick fix is therefore to make 'SLOW_AND_BORING' the default get_chunk() implementation. We should run benchmarks to determine how much slower (as suggested by the name) this is.

  Changed 12 years ago by kurahaupo

Smallest array size exhibiting problem is 2033 (although the core dump occurs elsewhere due to memory corruption, rather than directly in the array handling code).

The "early" symptom (before the core dump) is that an unshifted sequence does not read back correctly via sequential indexing.

follow-up: ↓ 7   Changed 12 years ago by kurahaupo

I've found the key problem: , which will need a patch of about 20-30 lines. (An entire loop needs to be re-done).

Or I can include the entire work-over and refactoring I've given it while I've been trying to figure out how exactly it works.

That would include:

  • fix the round-up-to-power-of-two logic so it doesn't leave unnecessary empty space
  • unify handling of several different chunk types (therefore fewer tests & code paths)
  • make chunk grouping work with any size chunks, not just power-of-two
  • separate the handling of "sparsity" and "grouping" (there would still be some interaction in the allocation policy)
  • reorder functions to make inlining available

Any preferences for the "short" patch or the "full" patch?

in reply to: ↑ 6   Changed 12 years ago by darbelo

Replying to kurahaupo:

I've found the key problem: , which will need a patch of about 20-30 lines. (An entire loop needs to be re-done).

Any preferences for the "short" patch or the "full" patch?

If the short one is already 20+ lines, let's start with that one. Reviewing a full refactor of Array will take significantly longer and that might delay the bugfix going in.

  Changed 12 years ago by kurahaupo

Okay, I'll concentrate on that first. (Either way is going to need some work: (a) extract minimal bugfix changeset, or (b) complete the refactoring to a suitable coding standard.)

  Changed 12 years ago by kurahaupo

Yesterday I found an even weirder problem: unshift 17 items, shift 1, push 2, and it dies. Actually, I guessed this one based on code inspection.

Today, however, it appears this all goes away: Array PMC has been removed after a deprecation cycle. (Darn, I wish I'd remembered that before burning so much time debugging it.)

Ticket can be closed.

  Changed 12 years ago by kurahaupo

See ArrayTasklist for plans related to arrays of various sorts.

  Changed 12 years ago by bacek

I would like to reject this ticket as original issue isn't applicable anymore due Array removal.

We can create separate ticket for refactoring various *Array PMCs.

-- Bacek

  Changed 12 years ago by whiteknight

  • status changed from new to closed
  • resolution set to fixed

Array PMC is removed in r43695. Closing ticket.

Note: See TracTickets for help on using tickets.