dovecot-2.2: Added asserts to binary searches to make sure we do...

[dovecot at dovecot.org]

details:   http://hg.dovecot.org/dovecot-2.2/rev/38ca85ccd5af
changeset: 16361:38ca85ccd5af
user:      Timo Sirainen <tss at iki.fi>
date:      Wed May 15 15:06:24 2013 +0300
description:
Added asserts to binary searches to make sure we don't go to infinite loop.
Using idx=left+(right-left)/2 would have worked also to allow 4GB sizes,
but since none of the places in the code are likely to reach 2GB we might as
well just add an assert. (Also if they do reach 2GB, it could be possible
that they could reach also above 4GB and cause problems. Better to see an
early error.)

diffstat:

 src/lib-index/mail-index-map.c                |  1 +
 src/lib-index/mail-index-transaction-update.c |  1 +
 src/lib-storage/index/index-sort-string.c     |  1 +
 src/lib/bsearch-insert-pos.c                  |  2 ++
 src/lib/bsearch-insert-pos.h                  |  1 +
 src/lib/seq-range-array.c                     |  2 ++
 6 files changed, 8 insertions(+), 0 deletions(-)

diffs (75 lines):

diff -r 03aac782261e -r 38ca85ccd5af src/lib-index/mail-index-map.c
--- a/src/lib-index/mail-index-map.c	Wed May 15 14:28:04 2013 +0300
+++ b/src/lib-index/mail-index-map.c	Wed May 15 15:06:24 2013 +0300
@@ -514,6 +514,7 @@
 	idx = left_idx;
 	right_idx = I_MIN(map->hdr.messages_count, uid);
 
+	i_assert(right_idx < INT_MAX);
 	while (left_idx < right_idx) {
 		idx = (left_idx + right_idx) / 2;
 
diff -r 03aac782261e -r 38ca85ccd5af src/lib-index/mail-index-transaction-update.c
--- a/src/lib-index/mail-index-transaction-update.c	Wed May 15 14:28:04 2013 +0300
+++ b/src/lib-index/mail-index-transaction-update.c	Wed May 15 15:06:24 2013 +0300
@@ -402,6 +402,7 @@
 
 	updates = array_get(&t->updates, &count);
 	i_assert(left_idx <= right_idx && right_idx <= count);
+	i_assert(count < INT_MAX);
 
 	/* find the first update with either overlapping range,
 	   or the update which will come after our insert */
diff -r 03aac782261e -r 38ca85ccd5af src/lib-storage/index/index-sort-string.c
--- a/src/lib-storage/index/index-sort-string.c	Wed May 15 14:28:04 2013 +0300
+++ b/src/lib-storage/index/index-sort-string.c	Wed May 15 15:06:24 2013 +0300
@@ -382,6 +382,7 @@
 	int ret;
 
 	nodes = array_get_modifiable(&ctx->nonzero_nodes, &right_idx);
+	i_assert(right_idx < INT_MAX);
 	idx = left_idx = start_idx;
 	while (left_idx < right_idx) {
 		idx = (left_idx + right_idx) / 2;
diff -r 03aac782261e -r 38ca85ccd5af src/lib/bsearch-insert-pos.c
--- a/src/lib/bsearch-insert-pos.c	Wed May 15 14:28:04 2013 +0300
+++ b/src/lib/bsearch-insert-pos.c	Wed May 15 15:06:24 2013 +0300
@@ -13,6 +13,8 @@
 	unsigned int idx, left_idx, right_idx;
 	int ret;
 
+	i_assert(nmemb < INT_MAX);
+
 	idx = 0; left_idx = 0; right_idx = nmemb;
 	while (left_idx < right_idx) {
 		idx = (left_idx + right_idx) / 2;
diff -r 03aac782261e -r 38ca85ccd5af src/lib/bsearch-insert-pos.h
--- a/src/lib/bsearch-insert-pos.h	Wed May 15 14:28:04 2013 +0300
+++ b/src/lib/bsearch-insert-pos.h	Wed May 15 15:06:24 2013 +0300
@@ -5,6 +5,7 @@
 #define BINARY_NUMBER_SEARCH(data, count, value, idx_r) \
 	unsigned int idx, left_idx, right_idx;        \
 						      \
+	i_assert((count) < INT_MAX);                  \
 	idx = 0; left_idx = 0; right_idx = (count);   \
 	while (left_idx < right_idx) {                \
 		idx = (left_idx + right_idx) / 2;     \
diff -r 03aac782261e -r 38ca85ccd5af src/lib/seq-range-array.c
--- a/src/lib/seq-range-array.c	Wed May 15 14:28:04 2013 +0300
+++ b/src/lib/seq-range-array.c	Wed May 15 15:06:24 2013 +0300
@@ -12,6 +12,7 @@
 	unsigned int idx, left_idx, right_idx, count;
 
 	data = array_get(array, &count);
+	i_assert(count < INT_MAX);
 
 	idx = 0; left_idx = 0; right_idx = count;
 	while (left_idx < right_idx) {
@@ -198,6 +199,7 @@
 
 	/* somewhere in the middle, array is sorted so find it with
 	   binary search */
+	i_assert(count < INT_MAX);
 	left_idx = 0; right_idx = count;
 	while (left_idx < right_idx) {
 		idx = (left_idx + right_idx) / 2;