Re: top vs. array sorted_state's out of bounds indexing (and related issues)

From: Mark Millard <marklmi_at_yahoo.com>
Date: Sun, 02 Jul 2023 22:45:10 UTC
Clifton Royston <cliftonr_at_volcano.org> wrote on
Date: Sun, 02 Jul 2023 21:44:10 UTC :

> On 7/2/2023 9:52 AM, Clifton Royston wrote:
> > On 6/19/2023 6:05 AM, Konstantin Belousov wrote:
> >> On Sun, Jun 18, 2023 at 09:23:06PM -0700, Mark Millard wrote:
> >>> usr.bin/top/machine.c (from main) has:
> [...]
> >>>
> >>> static int sorted_state[] = {
> >>> 0, /* not used */
> >>> 3, /* sleep */
> >>> 1, /* ABANDONED (WAIT) */
> >>> 6, /* run */
> >>> 5, /* start */
> >>> 2, /* zombie */
> >>> 4 /* stop */
> >>> };
> >>>
> >>> Note the elements are 0..6, so 7 elements.
> >>>
> >>> It is accessed via code like:
> >>>
> >>> sorted_state[(unsigned char)(b)->ki_stat]
> > [...]
> >>> /*
> >>> * These were process status values (p_stat), now they are only 
> used in
> >>> * legacy conversion code.
> >>> */
> >>> #define SIDL 1 /* Process being created by fork. */
> >>> #define SRUN 2 /* Currently runnable. */
> >>> #define SSLEEP 3 /* Sleeping on an address. */
> >>> #define SSTOP 4 /* Process debugging or suspension. */
> >>> #define SZOMB 5 /* Awaiting collection by parent. */
> >>> #define SWAIT 6 /* Waiting for interrupt. */
> >>> #define SLOCK 7 /* Blocked on a lock. */
> >>>
> > [...]
> >>> } else if (TD_ON_LOCK(td)) {
> >>> kp->ki_stat = SLOCK;
> > [...]
> >> https://reviews.freebsd.org/D40607
> >
> > I rarely comment here and hesitate to now, but out of curiosity I
> > looked at the original report and at the chain of commits.
> >
> > It appears to me that in making the code more readable the final
> > result may have accidentally inverted the sort order from the intended
> > values (mostly.) A casual test wouldn't show this, as unless the sort
> > order in top were changed, normally it would only come into play for
> > two processes with equal CPU % and ticks which seems unlikely.
> [...]
> 
> And, following up to myself, I now realized that both the committed
> patch *and* my reply completely missed addressing the original issue
> Mark reported:
> 
> No value for the index SLOCK is included in the array initializer,

Not true now. See below.

> so
> SLOCK is still not translated to a meaningful index, and AFAICT it is
> not included in the dimensions!

SLOCK has a element in the array now. See below.

> I expect it would still result in the
> same out-of-bounds indexing problem Mark reported for that case.

Nope. See below.

> A further corrected comment and array initializer:
> 
> /*
> * proc_compare - comparison function for "qsort"
> * Compares the resource consumption of two processes using five
> * distinct keys. The keys (in descending order of importance) are:
> * percent cpu, cpu ticks, state, resident set size, total virtual
> * memory usage. The process states are ordered as follows (from most
> * to least important): run, zombie, idle (being created), interrupt
> * wait, blocked on lock, stop, sleep.
> * The array declaration below maps a process state index into a
> * number that reflects this ordering.
> */
> 
> static const int sorted_state[] = {
> [SRUN] = 7, /* Currently runnable. */
> [SZOMB] = 6, /* Awaiting collection by parent. */
> [SIDL] = 5, /* Process being created by fork. */
> [SWAIT] = 4, /* Waiting for interrupt. */
> [SLOCK] = 3, /* Blocked on a lock. */
> [SSTOP] = 2, /* Process debugging or suspension. */
> [SSLEEP] = 1, /* Sleeping on an address. */
> }


[I ignore here specific choices/views of what sort order
should result.]

Looking at modern /usr/main-src/usr.bin/top/machine.c in
main's source I see:

static const int sorted_state[] = {
        [SIDL] =        3,      /* being created        */
        [SRUN] =        1,      /* running/runnable     */
        [SSLEEP] =      6,      /* sleeping             */
        [SSTOP] =       5,      /* stopped/suspended    */
        [SZOMB] =       2,      /* zombie               */
        [SWAIT] =       4,      /* intr                 */
        [SLOCK] =       7,      /* blocked on lock      */
};

In other words, after substitutions for the macros:

static const int sorted_state[] = {
        [1] =        3,      /* being created        */
        [2] =        1,      /* running/runnable     */
        [3] =      6,      /* sleeping             */
        [4] =       5,      /* stopped/suspended    */
        [5] =       2,      /* zombie               */
        [6] =       4,      /* intr                 */
        [7] =       7,      /* blocked on lock      */
};

That notation means (being explicit about the size
and the implicit [0] case):

static const int sorted_state[8] = {
        [0] =        0,      /* implicit case        */
        [1] =        3,      /* being created        */
        [2] =        1,      /* running/runnable     */
        [3] =      6,      /* sleeping             */
        [4] =       5,      /* stopped/suspended    */
        [5] =       2,      /* zombie               */
        [6] =       4,      /* intr                 */
        [7] =       7,      /* blocked on lock      */
};

It spans all the indexes for use of:

#define SIDL 1 /* Process being created by fork. */
#define SRUN 2 /* Currently runnable. */
#define SSLEEP 3 /* Sleeping on an address. */
#define SSTOP 4 /* Process debugging or suspension. */
#define SZOMB 5 /* Awaiting collection by parent. */
#define SWAIT 6 /* Waiting for interrupt. */
#define SLOCK 7 /* Blocked on a lock. */

So there is no out of bounds access for any of those
named values.


===
Mark Millard
marklmi at yahoo.com