Conference turris::decc

2074.0. "v5.3 vs. 5.5 - $literal psect?" by CSC32::J_HENSON (Don't get even, get ahead!) Tue Jan 28 1997 10:15

This is sort of a strange request, and by no means critical.  I have a 
customer who is of the opinion that there was a bug in dec c for ovms
alpha v5.3-006 in which the compiler is generating the $LITERAL$
psect incorrectly, and which results in the beginning of the
$READONLY$ psect to be initialized incorrectly.  He also is of the
opinion that V5.5 does not generate the bad code, so it must have
been fixed.  He has provided the code sample below to illustrate
the problem.

FWIW, the only reason that the $READONLY$ psect is being corrupted is
that the linker just happens to place it immediately after the
$LITERAL$ psect.  Or at least this is the current working theory.

When I run then command procedure below, and both analyze the object
and examine the linker map, I do see some differences in the $LITERAL$
psect that is generated by the 2 versions.  However, I do not know
enough about the compiler and object langauge to determine whether
or not it's a problem.

Under both versions of the compiler, the $LITERAL$ psect has a length of
4265 bytes.  However, when analyzing the object, the contributions to
this psect are different.  On 5.5-002, they appear to be less.  To
see this, direct the output of the ana/obj command to a file and
edit or otherwise examine the file.  You will see that with both compilers
a $LITERAL$ psect is created with an allocation of 4265 bytes.  The
$LITERAL$ psect is denoted as psect #2.

If you start looking for the string "psect: 2", you will begin to see
differences in the sizes of the various contributions.  My customer
feels that is the crux of the matter.

Anyway, if you are aware of any changes or fixes between 5.3 and 5.5 that 
addresses this, I (and my customer) would like to know.  He is currently
exploring the option of recompiling everything (he has a lot of code)
with 5.5, but it is a bit uneasy with this approach until he further
understands what is happening.  Mostly, though, he just wants to better
understand the issue.

Thanks,

Jerry

==========================================================================

From:	US3RMC::"[email protected]" "Ed Miller x3411" 27-JAN-1997 15:33:43.38
To:	CSC32::J_HENSON
CC:	[email protected]
Subj:	C970116-3377 (cc compile test procedure)

Hi Jerry,

The appended command file is what we use to produce the object file
which was causing us the problem with $LITERAL$ data overwriting
overwriting (by the LINKer) data in the following psect ($READONLY$).
That is, the data at the tail end of the $LITERAL$ psect from this
object file was overwriting the beginning of the $READONLY$ psect.

I will send you in a separate letter to follow the output of ANAL/OBJECT
for this .OBJ file (eliminating most of the output except for the
contributions to 'psect: 2', the $LITERAL$ psect.)  There is certainly not
a zero contribution to this psect.  You may disagree with our assessment that
the compiler is misleading the linker about the description of this psect
data, but at least we should be sure that we are both looking at the same
evidence.

This compile command is not significantly different from what I indicated
before.  If you can't reproduce this, then perhaps our INCLUDE files are not the
same?  (We only have 3 include files, and they all are satisfied from
sys$library:decc$rtldef.tlb.)

 Thanks,
   Ed Miller

------------------------------------------------------------------------------
$!
$!!! define decc$compiler sys$system:DECC$COMPILER_V53.EXE
$!
$ CC/DECC/STANDARD=VAXC/NOMEMBER_ALIGN/EXTERN=COMMON/FLOAT=D_FLOAT-
/SHARE_GLOBALS/list=qiksortc.lis -
/object=qiksortc.obj/DEBUG/PSECT=MULTILANG/SHOW=(SOURCE)/WARN-
/CHEC=(UNINIT,POIN=ALL)/NOOPTI sys$input:
/*    **MEMBER**=SLCLIBS:SYSUTILLIB
 
================================================================================
 
  Abs:  Sort an array using C.A.R.Hoare's "quicksort" algorithm.
 
  Name: QIKSORTC (module)
        qiksortc                   Sort an array in which sort keys are treated
                                   as ascii strings.
 
  Rem:  See below.  See also qiksortu and qiksortf.
 
  Side: None.
 
  Proto: slctxt:sysutil_proto.h
 
  Auth: 25-Feb-1983, Tony Gromme (TEG)
  Revw:
 
--------------------------------------------------------------------------------
 
  Mod:  21-Jul-1996, Tony Gromme (TEG):
            Translated to C from Vax Macro.
 
==============================================================================*/
 
#include <stddef.h>                  /* NULL.                                 */
#include <stdlib.h>                  /* malloc, free.                         */
#include <string.h>                  /* memcmp, memcpy.                       */
 
 
#define QIKS_STK_MAX 500         /* Max depth of sort stack.                  */
#define QIKS_ITMBC_MAX 256       /* Limit on item size above which we have to */
                                 /*  allocate heap storage.                   */
 
 
 
 
        /**************************************************************/
        /*                                                            */
        /* Abs:  Sort an array using C.A.R.Hoare's "quicksort"        */
        /*       algorithm.                                           */
        /* Name: qiksortc.                                            */
        /* Scop: Public.                                              */
        /* Rem:  Considering the given input as an array of           */
        /*       structures to be sorted, and assuming the sort key   */
        /*       in each structure is a string of contiguous bytes,   */
        /*       we compare sort keys as ascii strings, i.e., using   */
        /*       memcmp.                                              */
        /* Args: items_n_p            Pointer to longword containing  */
        /*                            number of items to be sorted.   */
        /*       array_p              Pointer to array of items to    */
        /*                            be sorted.                      */
        /*       item_bc_p            Pointer to word containing      */
        /*                            length in bytes of each item    */
        /*                            in given array.                 */
        /*       key_off_p            Pointer to word containing      */
        /*                            offset in bytes of sort key     */
        /*                            relative to beginning of any    */
        /*                            item in given array.            */
        /*       key_bc_p             Pointer to word containing      */
        /*                            length in bytes of sort key in  */
        /*                            each item.                      */
        /* Ret:  None.                                                */
        /* Note: Performance of this algorithm depends on the         */
        /*       randomness of the input;  the algorithm performs     */
        /*       poorly when the input is already more or less        */
        /*       ordered.                                             */
        /*                                                            */
        /**************************************************************/
 
 /**procedure**/
 void qiksortc(const unsigned long *items_n_p, void *array_p, const unsigned short *item_bc_p,
               const unsigned short *key_off_p, const unsigned short *key_bc_p)
 {   unsigned char  *sort_stack[QIKS_STK_MAX][2],
                    *low_p,
                    *hi_p,
                    *tmphi_p,
                    *item_swap_p,
                    *item_alloc_p,
                    *limit_p,
                     swap_tmp[QIKS_ITMBC_MAX];
     unsigned        stkx,
                     flip;
 
               /*----------------------------------------------*/
 
     if (*items_n_p > 1)
     {
          /* For swapping items, we need space to hold one item. */
          /* We allocated QIKS_ITMBC_MAX bytes for that in our   */
          /* stackframe;  if the given item size is larger, we   */
          /* must allocate (and subsequently free) some heap     */
          /* storage.                                            */
 
         if (*item_bc_p <= QIKS_ITMBC_MAX)
         {
             item_alloc_p = NULL;
             item_swap_p = swap_tmp;
         }
         else
         {
             item_swap_p = item_alloc_p = malloc(*item_bc_p);
         }
 
          /* Each element of sort_stack is a pair of pointers, pointing to */
          /* the first and last elements in a subarray of at least two     */
          /* contiguous items in the array given to be sorted.  For each   */
          /* such pair of pointers, we make a pass (as described below)    */
          /* through the subarray they define.  At the end of such a pass, */
          /* we have the pair of pointers defining the subarray, and a     */
          /* third pointer pointing to some middle item in that subarray   */
          /* such that all items located in the subarray above that middle */
          /* item compare higher or equal to it and all items located in   */
          /* the subarray below that middle item compare lower or equal to */
          /* it.  This middle item may be located anywhere in the current  */
          /* subarray.  We replace the subarray definer on sort_stack with */
          /* zero or one or two definers of smaller subarrays, namely:     */
          /* those items if any in the subarray below the middle item, and */
          /* those items if any in the subarray above the middle item.     */
          /* Neither of these smaller subarrays includes the middle item   */
          /* itself.  We start the sort by pushing onto sort_stack a       */
          /* definer for the whole given array.  We are done when          */
          /* sort_stack is empty.                                          */
 
         sort_stack[0][0] = array_p;
         sort_stack[0][1] = &((unsigned char *) array_p)[(*items_n_p-1)*(*item_bc_p)];
         stkx = 1;
         while (stkx > 0)
         {
              /* Copy the pointers defining the subarray at the top of  */
              /* sort_stack.  We compare the items these pointers point */
              /* to, and swap them if the lower-addressed item's key    */
              /* compares high to the higher-addressed item's key.  We  */
              /* choose one of the two items when we start this pass.   */
              /* After each comparison and possible swap, we move the   */
              /* pointer pointing to the non-chosen item by one item    */
              /* closer to the other pointer.  This pass is done when   */
              /* the two pointers coincide;  they will then point to    */
              /* the item chosen at the beginning of this pass (now     */
              /* probably in a different location).                     */
 
             low_p = sort_stack[stkx-1][0];
             hi_p = sort_stack[stkx-1][1];
             while (low_p < hi_p)
             {
                  /* Compare the keys of the items pointed to by the */
                  /* two pointers, and swap if needed.               */
 
                 if (memcmp(&low_p[*key_off_p], &hi_p[*key_off_p], *key_bc_p) > 0)
                 {
                     memcpy(item_swap_p, low_p, *item_bc_p);
                     memcpy(low_p, hi_p, *item_bc_p);
                     memcpy(hi_p, item_swap_p, *item_bc_p);
                     flip ^= 1;
                 }
                  /* Adjust one or the other pointer, depending on flip. */
                  /* Flip is toggled whenever we swap two items.  Thus,  */
                  /* flip tells which pointer is pointing to the chosen  */
                  /* item.  Note that we never initialized flip.  That's */
                  /* because flip's initial state doesnt matter, since   */
                  /* we make no assumptions about how the given input is */
                  /* ordered to start with.                              */
 
                 if (flip & 1)
                     low_p += *item_bc_p;
                 else
                     hi_p -= *item_bc_p;
             }
 
              /* The two pointers now coincide.  If there are at least two */
              /* items strictly below the chosen item, they constitute a   */
              /* new subarray to be pushed onto sort_stack.  If there are  */
              /* at least two items strictly above the chosen item, they   */
              /* constitute a new subarray to be pushed onto sort_stack.   */
              /* Thus, sort_stack now either shrinks by one element, or    */
              /* stays the same size, or grows by one element.             */
 
             tmphi_p = sort_stack[stkx-1][1];
             low_p -= *item_bc_p;
             if (low_p > sort_stack[stkx-1][0])
                 sort_stack[stkx-1][1] = low_p;
             else
                 stkx--;
 
             hi_p += *item_bc_p;
             if (hi_p < tmphi_p)
             {
                 if (stkx >= QIKS_STK_MAX)
                     break;                /* Oops;  sort_stack overflowed; */
                                           /* let's try some other method.  */
                 stkx++;
                 sort_stack[stkx-1][0] = hi_p;
                 sort_stack[stkx-1][1] = tmphi_p;
             }
         }
 
         if (stkx > 0)
         {
              /* Sort_stack overflowed;  we settle on a crummy n-squared sort. */
 
             limit_p = &((unsigned char *) array_p)[(*items_n_p)*(*item_bc_p)];
             for (hi_p = &((unsigned char *) array_p)[*item_bc_p];
                  hi_p < limit_p;  hi_p = &hi_p[*item_bc_p])
             {
                 for (low_p = array_p;  low_p < hi_p;  low_p = &low_p[*item_bc_p])
                 {
                     if (memcmp(&low_p[*key_off_p], &hi_p[*key_off_p], *key_bc_p) > 0)
                     {
                         memcpy(item_swap_p, low_p, *item_bc_p);
                         memcpy(low_p, hi_p, *item_bc_p);
                         memcpy(hi_p, item_swap_p, *item_bc_p);
                     }
                 }
             }
         }
 
         free(item_alloc_p);
     }
 }                                                           /* End qiksortc. */

    
    Jerry,
    
    The folks who work on the compiler back-end have informed us
    that they did make a number of bug fixes in this area. 
    
    So it appears that your customer is quite correct. 
    
    					Ed
    
    

>>                       <<< Note 2074.2 by DECC::VOGEL >>>
>>                             -< There were fixes >-