Opened 12 years ago

Closed 12 years ago

#10435 closed defect (fixed)

Invalid write in bitsets

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

Status badges

Description


Attachments (1)

trac_10435.patch (4.3 KB) - added by Robert Miller 12 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 12 years ago by Robert Miller

Status: newneeds_review

comment:2 Changed 12 years ago by Jason Grout

Cc: Minh Van Nguyen added

Also CCing Minh, who has done some bitset work.

comment:3 Changed 12 years ago by Nathann Cohen

Status: needs_reviewneeds_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 12 years ago by Robert Miller

Status: needs_workneeds_review

Oops.

comment:5 Changed 12 years ago by Nathann Cohen

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

Nathann

comment:6 Changed 12 years ago by Nathann Cohen

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

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

Nathann

comment:7 Changed 12 years ago by Nathann Cohen

Status: needs_reviewpositive_review

comment:8 Changed 12 years ago by Nathann Cohen

Reviewers: Nathann Cohen

comment:9 Changed 12 years ago by Jeroen Demeyer

Status: positive_reviewneeds_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 12 years ago by Jeroen Demeyer

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

comment:11 in reply to:  9 Changed 12 years ago by Robert Miller

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 12 years ago by Robert Miller

Attachment: trac_10435.patch added

comment:12 Changed 12 years ago by Robert Miller

Status: needs_workneeds_review

comment:13 Changed 12 years ago by Jeroen Demeyer

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

comment:14 in reply to:  13 Changed 12 years ago by Robert Miller

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 12 years ago by Jeroen Demeyer

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 12 years ago by Nathann Cohen

Status: needs_reviewpositive_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 12 years ago by Jeroen Demeyer

Merged in: sage-4.6.2.alpha3
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.