You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hbase.apache.org by ap...@apache.org on 2019/01/12 00:54:45 UTC
[hbase] 03/04: HBASE-20928 Rewrite calculation of midpoint in
binarySearch functions to prevent overflow
This is an automated email from the ASF dual-hosted git repository.
apurtell pushed a commit to branch branch-1
in repository https://gitbox.apache.org/repos/asf/hbase.git
commit 231e6d56b569ca17fe620b1d29749dd211e1de02
Author: Saurabh Singh <sa...@csm-hadoop-spark-box.example.com>
AuthorDate: Fri Jan 11 12:14:18 2019 -0800
HBASE-20928 Rewrite calculation of midpoint in binarySearch functions to prevent overflow
HBASE-20928 Rewrite calculation of midpoint - addendum (Xu Cang)
Signed-off-by: tedyu <yu...@gmail.com>
Conflicts:
hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/RowIndexSeekerV1.java
hbase-common/src/main/java/org/apache/hadoop/hbase/util/Bytes.java
Amending-Author: Andrew Purtell <ap...@apache.org>
---
.../apache/hadoop/hbase/io/encoding/RowIndexSeekerV1.java | 14 +++++++++-----
.../src/main/java/org/apache/hadoop/hbase/util/Bytes.java | 6 +++---
.../org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java | 2 +-
.../hadoop/hbase/util/BoundedPriorityBlockingQueue.java | 2 +-
4 files changed, 14 insertions(+), 10 deletions(-)
diff --git a/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/RowIndexSeekerV1.java b/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/RowIndexSeekerV1.java
index e72c685..f210fc5 100644
--- a/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/RowIndexSeekerV1.java
+++ b/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/RowIndexSeekerV1.java
@@ -154,15 +154,13 @@ public class RowIndexSeekerV1 extends AbstractEncodedSeeker {
private int binarySearch(Cell seekCell, boolean seekBefore) {
int low = 0;
int high = rowNumber - 1;
- int mid = (low + high) >>> 1;
+ int mid = low + ((high - low) >> 1);
int comp = 0;
SimpleMutableByteRange row = new SimpleMutableByteRange();
while (low <= high) {
- mid = (low + high) >>> 1;
+ mid = low + ((high - low) >> 1);
getRow(mid, row);
- comp = comparator.compareRows(row.getBytes(), row.getOffset(),
- row.getLength(), seekCell.getRowArray(), seekCell.getRowOffset(),
- seekCell.getRowLength());
+ comp = compareRows(row, seekCell);
if (comp < 0) {
low = mid + 1;
} else if (comp > 0) {
@@ -184,6 +182,12 @@ public class RowIndexSeekerV1 extends AbstractEncodedSeeker {
}
}
+ private int compareRows(SimpleMutableByteRange row, Cell seekCell) {
+ return comparator.compareRows(row.getBytes(), row.getOffset(),
+ row.getLength(), seekCell.getRowArray(), seekCell.getRowOffset(),
+ seekCell.getRowLength());
+ }
+
private void getRow(int index, SimpleMutableByteRange row) {
int offset = Bytes.toIntUnsafe(rowOffsets.array(), rowOffsets.arrayOffset()
+ (index << 2)); // index * Bytes.SIZEOF_INT
diff --git a/hbase-common/src/main/java/org/apache/hadoop/hbase/util/Bytes.java b/hbase-common/src/main/java/org/apache/hadoop/hbase/util/Bytes.java
index 765f51b..22ade4b 100644
--- a/hbase-common/src/main/java/org/apache/hadoop/hbase/util/Bytes.java
+++ b/hbase-common/src/main/java/org/apache/hadoop/hbase/util/Bytes.java
@@ -2145,7 +2145,7 @@ public class Bytes implements Comparable<Bytes> {
int high = arr.length - 1;
while (low <= high) {
- int mid = (low+high) >>> 1;
+ int mid = low + ((high - low) >> 1);
// we have to compare in this order, because the comparator order
// has special logic when the 'left side' is a special key.
int cmp = comparator.compare(key, offset, length,
@@ -2182,7 +2182,7 @@ public class Bytes implements Comparable<Bytes> {
int high = arr.length - 1;
KeyValue.KeyOnlyKeyValue r = new KeyValue.KeyOnlyKeyValue();
while (low <= high) {
- int mid = (low+high) >>> 1;
+ int mid = low + ((high - low) >> 1);
// we have to compare in this order, because the comparator order
// has special logic when the 'left side' is a special key.
r.setKey(arr[mid], 0, arr[mid].length);
@@ -2357,7 +2357,7 @@ public class Bytes implements Comparable<Bytes> {
int high = toIndex - 1;
while (low <= high) {
- int mid = (low + high) >>> 1;
+ int mid = low + ((high - low) >> 1);
int midVal = a[mid] & 0xff;
if (midVal < unsignedKey) {
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java
index da6f3b6..9148815 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java
@@ -533,7 +533,7 @@ public class HFileBlockIndex {
// keys[low - 1] < key < keys[high + 1] while narrowing down the range.
KeyValue.KeyOnlyKeyValue nonRootIndexKV = new KeyValue.KeyOnlyKeyValue();
while (low <= high) {
- mid = (low + high) >>> 1;
+ mid = low + ((high - low) >> 1);
// Midkey's offset relative to the end of secondary index
int midKeyRelOffset = nonRootIndex.getInt(
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BoundedPriorityBlockingQueue.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BoundedPriorityBlockingQueue.java
index 4a93151..2d09e13 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BoundedPriorityBlockingQueue.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BoundedPriorityBlockingQueue.java
@@ -119,7 +119,7 @@ public class BoundedPriorityBlockingQueue<E> extends AbstractQueue<E> implements
private int upperBound(int start, int end, E key) {
while (start < end) {
- int mid = (start + end) >>> 1;
+ int mid = start + ((end - start) >> 1);
E mitem = objects[mid];
int cmp = comparator.compare(mitem, key);
if (cmp > 0) {