hadoop-common-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Hudson (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (HADOOP-11327) BloomFilter#not() omits the last bit, resulting in an incorrect filter
Date Thu, 22 Jan 2015 15:24:40 GMT

    [ https://issues.apache.org/jira/browse/HADOOP-11327?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14287594#comment-14287594
] 

Hudson commented on HADOOP-11327:
---------------------------------

FAILURE: Integrated in Hadoop-Mapreduce-trunk #2032 (See [https://builds.apache.org/job/Hadoop-Mapreduce-trunk/2032/])
HADOOP-11327. BloomFilter#not() omits the last bit, resulting in an incorrect filter. Contributed
by Eric Payne (jlowe: rev 07b08060369caf34f248745a10bda61fb0a3ef23)
* hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/util/bloom/TestBloomFilters.java
* hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/util/bloom/BloomFilter.java
* hadoop-common-project/hadoop-common/CHANGES.txt


> BloomFilter#not() omits the last bit, resulting in an incorrect filter
> ----------------------------------------------------------------------
>
>                 Key: HADOOP-11327
>                 URL: https://issues.apache.org/jira/browse/HADOOP-11327
>             Project: Hadoop Common
>          Issue Type: Bug
>          Components: util
>    Affects Versions: 2.5.1
>            Reporter: Tim Luo
>            Assignee: Eric Payne
>            Priority: Minor
>             Fix For: 2.7.0
>
>         Attachments: HADOOP-11327.v1.txt, HADOOP-11327.v2.txt
>
>
> There's an off-by-one error in {{BloomFilter#not()}}:
> {{BloomFilter#not}} calls {{BitSet#flip(0, vectorSize - 1)}}, but according to the javadoc
for that method, {{toIndex}} is end-_exclusive_:
> {noformat}
> * @param  toIndex index after the last bit to flip
> {noformat}
> This means that the last bit in the bit array is not flipped.
> Specifically, this was discovered in the following scenario:
> 1. A new/empty {{BloomFilter}} was created with vectorSize=7.
> 2. Invoke {{bloomFilter.not()}}; now expecting a bloom filter with all 7 bits (0 through
6) flipped to 1 and membershipTest(...) to always return true.
> 3. However, membershipTest(...) was found to often not return true, and upon inspection,
the BitSet only had bits 0 through 5 flipped.
> The fix should be simple: remove the "- 1" from the call to {{BitSet#flip}}.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message