From kde-commits  Thu Oct 28 08:09:05 2004
From: Tom Hughes <thh () cyberscience ! com>
Date: Thu, 28 Oct 2004 08:09:05 +0000
To: kde-commits
Subject: valgrind/coregrind
Message-Id: <20041028080905.8F7C616CC0 () office ! kde ! org>
X-MARC-Message: https://marc.info/?l=kde-commits&m=109895102415224

CVS commit by thughes: 

Fixed get_height to ensure that SK_MAXHEIGHT-1 is the maximum level we
will allocate for a skip list entry as many routines use arrays of
size SK_MAXHEIGHT to hold a set of level pointers which means that a
level of SK_MAXHEIGHT is not valid due to C arrays being zero based.

This led to a number of subtle and hard to locate problems caused by
stack based arrays being overflowed by one entry when a node was
allocated with the maximum level. As each node only has a one in two
million or so chance of getting a level of SK_MAXHEIGHT this didn't
actually happen all that often.

BUG: 91028


  M +1 -1      vg_skiplist.c   1.7


--- valgrind/coregrind/vg_skiplist.c  #1.6:1.7
@@ -113,5 +113,5 @@ static inline Int get_height(void)
    UInt ret = 0;
 
-   while((ret < SK_MAXHEIGHT) && (random() & 1))
+   while((ret < SK_MAXHEIGHT - 1) && (random() & 1))
       ret++;