Opened 9 years ago

Closed 9 years ago

#10435 closed defect (fixed)

Invalid write in bitsets

Reported by: rlm Owned by: jason
Priority: major Milestone: sage-4.6.2
Component: misc Keywords:
Cc: mvngu Merged in: sage-4.6.2.alpha3
Authors: Robert Miller Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description


Attachments (1)

trac_10435.patch (4.3 KB) - added by rlm 9 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 9 years ago by rlm

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by jason

  • Cc mvngu added

Also CCing Minh, who has done some bitset work.

comment:3 Changed 9 years ago by ncohen

  • Status changed from needs_review to needs_work

The -testall fails on the file to which the doctest is added... Here is what I got :

Expected:
    a 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    list a []
    a.size 128
    len(a) 0
    a.limbs 4
    b 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a.in(n)   False
    a.not_in(n)   True
    a.add(n)     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.discard(n)   00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.set_to(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.flip(n)    00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.set_first_n(n)    11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
    a.first_in_complement()    -1
    a.isempty()  True
    a.eq(b)      False
    a.cmp(b)     -1
    a.issubset(b) True
    a.issuperset(b) False
    a.copy()     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    r.clear()     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    complement a        11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
    a intersect b      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a union b       01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a minus b      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a symmetric_difference b      01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a.rshift(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.lshift(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.first()           -1
    a.next(n)           -1
    a.first_diff(b)     1
    a.next_diff(b, n)   -1
    a.hamming_weight()  0
    a.hamming_weight_sparse()  0
    rshifts add  True
    lshifts add  True
    intersection commutes True
    union commutes  True
    not not = id True
    flipped bit  -1
    add bit      -1
    discard bit    -1
    lshift add unset ok True
    rshift set unset ok True
    reallocating a      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to size 128          00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to size 256          0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to original size    00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Got:
    a 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    list a []
    a.size 128
    len(a) 0
    a.limbs 2
    b 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a.in(n)   False
    a.not_in(n)   True
    a.add(n)     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.discard(n)   00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.set_to(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.flip(n)    00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.set_first_n(n)    11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
    a.first_in_complement()    -1
    a.isempty()  True
    a.eq(b)      False
    a.cmp(b)     -1
    a.issubset(b) True
    a.issuperset(b) False
    a.copy()     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    r.clear()     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    complement a        11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
    a intersect b      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a union b       01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a minus b      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a symmetric_difference b      01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a.rshift(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.lshift(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.first()           -1
    a.next(n)           -1
    a.first_diff(b)     1
    a.next_diff(b, n)   -1
    a.hamming_weight()  0
    a.hamming_weight_sparse()  0
    rshifts add  True
    lshifts add  True
    intersection commutes True
    union commutes  True
    not not = id True
    flipped bit  -1
    add bit      -1
    discard bit    -1
    lshift add unset ok True
    rshift set unset ok True
    reallocating a      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to size 128          00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to size 256          0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to original size    00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

The only difference I was able to notice is at the 5th line

Nathann

comment:4 Changed 9 years ago by rlm

  • Status changed from needs_work to needs_review

Oops.

comment:5 Changed 9 years ago by ncohen

It now passes all tests.. But what about this "limbs" parameter ? Is it platform-dependent ?

Nathann

comment:6 Changed 9 years ago by ncohen

    bits.limbs = (size - 1)/(8*sizeof(unsigned long)) + 1

Looks like it is.... Thank you very much for your help ! :-)

Nathann

comment:7 Changed 9 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:8 Changed 9 years ago by ncohen

  • Reviewers set to Nathann Cohen

comment:9 follow-up: Changed 9 years ago by jdemeyer

  • Status changed from positive_review to needs_work

This seems to cause problems on some Skynet machines, for example on hawk (OpenSolaris? 06.2009-32):

sage -t -long  -force_lib devel/sage/sage/misc/misc_c.pyx
**********************************************************************
File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-4.6.2.alpha0/devel/sage-main/sage/misc/misc_c.pyx", line 598:
    sage: test_bitset('00'*64, '01'*64, 128)
Expected:
    a 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    list a []
    a.size 128
    len(a) 0
    a.limbs ...
    b 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a.in(n)   False
    a.not_in(n)   True
    a.add(n)     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.discard(n)   00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.set_to(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.flip(n)    00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.set_first_n(n)    11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
    a.first_in_complement()    -1
    a.isempty()  True
    a.eq(b)      False
    a.cmp(b)     -1
    a.issubset(b) True
    a.issuperset(b) False
    a.copy()     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    r.clear()     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    complement a        11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
    a intersect b      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a union b       01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a minus b      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a symmetric_difference b      01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a.rshift(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.lshift(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.first()           -1
    a.next(n)           -1
    a.first_diff(b)     1
    a.next_diff(b, n)   -1
    a.hamming_weight()  0
    a.hamming_weight_sparse()  0
    rshifts add  True
    lshifts add  True
    intersection commutes True
    union commutes  True
    not not = id True
    flipped bit  -1
    add bit      -1
    discard bit    -1
    lshift add unset ok True
    rshift set unset ok True
    reallocating a      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to size 128          00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to size 256          0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to original size    00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Got:
    a 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    list a []
    a.size 128
    len(a) 0
    a.limbs 4
    b 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a.in(n)   True
    a.not_in(n)   False
    a.add(n)     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.discard(n)   00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.set_to(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.flip(n)    00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.set_first_n(n)    11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
    a.first_in_complement()    -1
    a.isempty()  True
    a.eq(b)      False
    a.cmp(b)     -1
    a.issubset(b) True
    a.issuperset(b) False
    a.copy()     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    r.clear()     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    complement a        11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
    a intersect b      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a union b       01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a minus b      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a symmetric_difference b      01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a.rshift(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.lshift(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.first()           -1
    a.next(n)           -1
    a.first_diff(b)     1
    a.next_diff(b, n)   -1
    a.hamming_weight()  0
    a.hamming_weight_sparse()  0
    rshifts add  True
    lshifts add  True
    intersection commutes True
    union commutes  True
    not not = id True
    flipped bit  -1
    add bit      -1
    discard bit    -1
    lshift add unset ok True
    rshift set unset ok True
    reallocating a      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to size 128          00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to size 256          0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to original size    00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
**********************************************************************

comment:10 Changed 9 years ago by jdemeyer

On bsd.math (OS X 10.6 32-bit), doctesting misc_c.pyx gives a segmentation fault.

comment:11 in reply to: ↑ 9 Changed 9 years ago by rlm

Replying to jdemeyer:

This seems to cause problems on some Skynet machines, for example on hawk (OpenSolaris? 06.2009-32):

The diff of these two is:

5c5
<     a.limbs ...
---
>     a.limbs 4
7,8c7,8
<     a.in(n)   False
<     a.not_in(n)   True
---
>     a.in(n)   True
>     a.not_in(n)   False

Changed 9 years ago by rlm

comment:12 Changed 9 years ago by rlm

  • Status changed from needs_work to needs_review

comment:13 follow-up: Changed 9 years ago by jdemeyer

Can you justify why you removed the test from the patch?

comment:14 in reply to: ↑ 13 Changed 9 years ago by rlm

Replying to jdemeyer:

Can you justify why you removed the test from the patch?

Yes. It was an invalid test. The number provided was equal to the size of the bitset, which is valid when setting the first n bits to 1, but not valid when adding that bit to the set, i.e. 0..127 would be valid but 128 is not. That is why I added the new testing function.

comment:15 Changed 9 years ago by jdemeyer

I realize that the reviewer of this ticket might not have access to a Solaris machine to test this new patch on. That's fine, I would be happy with a positive_review based on simply reading the patch and not testing it. If this gets a positive_review, I will test it properly.

comment:16 Changed 9 years ago by ncohen

  • Status changed from needs_review to positive_review

Then I give it a positive review ! It fixes a real problem, and passes all tests on the last alpha0 release. Thank you for testing it on OpenSolaris? ! :-)

Nathann

comment:17 Changed 9 years ago by jdemeyer

  • Merged in set to sage-4.6.2.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.