[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-commits
Subject:    valgrind/coregrind
From:       Tom Hughes <thh () cyberscience ! com>
Date:       2004-10-28 8:09:05
Message-ID: 20041028080905.8F7C616CC0 () office ! kde ! org
[Download RAW message or body]

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++;
 


[prev in list] [next in list] [prev in thread] [next in thread]