home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 4 / AACD04.ISO / AACD / Programming / Wipeout / source / allocator.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-16  |  13.9 KB  |  642 lines
  1. /*
  2.  * $Id: allocator.c 1.14 1998/04/16 11:03:41 olsen Exp olsen $
  3.  *
  4.  * :ts=4
  5.  *
  6.  * Wipeout -- Traces and munges memory and detects memory trashing
  7.  *
  8.  * Written by Olaf `Olsen' Barthel <olsen@sourcery.han.de>
  9.  * Public Domain
  10.  */
  11.  
  12. #ifndef _GLOBAL_H
  13. #include "global.h"
  14. #endif    /* _GLOBAL_H */
  15.  
  16. /******************************************************************************/
  17.  
  18. #include "installpatches.h"
  19.  
  20. /******************************************************************************/
  21.  
  22. STATIC struct MinList AllocationList;
  23.  
  24. /******************************************************************************/
  25.  
  26. STATIC VOID
  27. AddAllocation(struct TrackHeader * th)
  28. {
  29.     /* Register the new regular memory allocation. */
  30.     AddTail((struct List *)&AllocationList,(struct Node *)th);
  31. }
  32.  
  33. STATIC VOID
  34. RemoveAllocation(struct TrackHeader * th)
  35. {
  36.     /* Unregister the regular memory allocation. */
  37.     Remove((struct Node *)th);
  38.     th->th_Magic = 0;
  39. }
  40.  
  41. /******************************************************************************/
  42.  
  43. ULONG
  44. CalculateChecksum(const ULONG * mem,ULONG memSize)
  45. {
  46.     ULONG tmp,sum;
  47.     int i;
  48.  
  49.     /* memSize must be a multiple of 4. */
  50.     ASSERT((memSize % 4) == 0);
  51.  
  52.     /* Calculate the "additive carry wraparound" checksum
  53.      * for the given memory area. The Kickstart and the boot block
  54.      * checksums are calculated using the same technique.
  55.      */
  56.     sum = 0;
  57.     for(i = 0 ; i < memSize / 4 ; i++)
  58.     {
  59.         tmp = sum + mem[i];
  60.         if(tmp < sum)
  61.             tmp++;
  62.  
  63.         sum = tmp;
  64.     }
  65.  
  66.     return(sum);
  67. }
  68.  
  69. /******************************************************************************/
  70.  
  71. VOID
  72. FixTrackHeaderChecksum(struct TrackHeader * th)
  73. {
  74.     ASSERT(th != NULL);
  75.  
  76.     /* Protect everything but the MinNode at the beginning
  77.      * with a checksum.
  78.      */
  79.     th->th_Checksum = 0;
  80.     th->th_Checksum = ~CalculateChecksum((ULONG *)&th->th_PoolHeader,
  81.                                          sizeof(*th) - offsetof(struct TrackHeader,th_PoolHeader));
  82. }
  83.  
  84. /******************************************************************************/
  85.  
  86. VOID
  87. PerformDeallocation(struct TrackHeader * th)
  88. {
  89.     BOOL mungMem = FALSE;
  90.     LONG allocationSize;
  91.     APTR poolHeader;
  92.  
  93.     allocationSize = th->th_NameTagLen + sizeof(*th) + PreWallSize + th->th_Size + th->th_PostSize;
  94.  
  95.     /* It is quasi-legal to release and reuse memory whilst under
  96.      * Forbid(). If this is the case, we will not stomp on the allocation
  97.      * body and leave the contents of the buffer unmodified. Note that
  98.      * while in Disable() state, multitasking will be halted, just as whilst
  99.      * in Forbid() state. But as there is no safe way to track whether the
  100.      * system actually has the interrupts disabled and because the memory
  101.      * allocator is documented to operate under Forbid() conditions only,
  102.      * we just consider the Forbid() state.
  103.      */
  104.     if(NoReuse || SysBase->TDNestCnt == 0) /* not -1 because we always run under Forbid() */
  105.     {
  106.         mungMem = TRUE;
  107.     }
  108.  
  109.     switch(th->th_Type)
  110.     {
  111.         case ALLOCATIONTYPE_AllocMem:
  112.         case ALLOCATIONTYPE_AllocVec:
  113.  
  114.             RemoveAllocation(th);
  115.  
  116.             /* skip the name tag header, if there is one */
  117.             if(th->th_NameTagLen > 0)
  118.             {
  119.                 th = (struct TrackHeader *)(((ULONG)th) - th->th_NameTagLen);
  120.             }
  121.  
  122.             /* munge the entire allocation, not just the allocation body. */
  123.             if(mungMem)
  124.             {
  125.                 MungMem((ULONG *)th,allocationSize,DEADBEEF);
  126.             }
  127.  
  128.             (*OldFreeMem)(th,allocationSize,SysBase);
  129.             break;
  130.  
  131.         case ALLOCATIONTYPE_AllocPooled:
  132.  
  133.             RemovePuddle(th);
  134.  
  135.             /* remember this, as it may be gone in a minute */
  136.             poolHeader = th->th_PoolHeader->ph_PoolHeader;
  137.  
  138.             /* skip the name tag header, if there is one */
  139.             if(th->th_NameTagLen > 0)
  140.             {
  141.                 th = (struct TrackHeader *)(((ULONG)th) - th->th_NameTagLen);
  142.             }
  143.  
  144.             /* munge the entire allocation, not just the allocation body. */
  145.             if(mungMem)
  146.             {
  147.                 MungMem((ULONG *)th,allocationSize,DEADBEEF);
  148.             }
  149.  
  150.             (*OldFreePooled)(poolHeader,th,allocationSize,SysBase);
  151.             break;
  152.     }
  153. }
  154.  
  155. /******************************************************************************/
  156.  
  157. BOOL
  158. PerformAllocation(
  159.     ULONG                    pc,
  160.     struct PoolHeader *        poolHeader,
  161.     ULONG                    memSize,
  162.     ULONG                    attributes,
  163.     UBYTE                    type,
  164.     APTR *                    resultPtr)
  165. {
  166.     struct TrackHeader * th;
  167.     ULONG preSize;
  168.     ULONG allocationRemainder;
  169.     ULONG postSize;
  170.     LONG nameTagLen;
  171.     APTR result = NULL;
  172.     BOOL success = FALSE;
  173.  
  174.     nameTagLen = 0;
  175.  
  176.     /* Get the name of the current task, if this is necessary. */
  177.     if(NameTag)
  178.     {
  179.         nameTagLen = GetNameTagLen(pc);
  180.     }
  181.  
  182.     /* If the allocation is not a multiple of the memory granularity
  183.      * block size, increase the post memory wall by the remaining
  184.      * few bytes of padding.
  185.      */
  186.     allocationRemainder = (memSize % MEM_BLOCKSIZE);
  187.     if(allocationRemainder > 0)
  188.     {
  189.         allocationRemainder = MEM_BLOCKSIZE - allocationRemainder;
  190.     }
  191.  
  192.     preSize = PreWallSize;
  193.     postSize = allocationRemainder + PostWallSize;
  194.  
  195.     switch(type)
  196.     {
  197.         case ALLOCATIONTYPE_AllocMem:
  198.  
  199.             th = (*OldAllocMem)(nameTagLen + sizeof(*th) + preSize + memSize + postSize,attributes & (~MEMF_CLEAR),SysBase);
  200.             if(th != NULL)
  201.             {
  202.                 /* Store the name tag data in front of the header, then
  203.                  * adjust the header address.
  204.                  */
  205.                 if(nameTagLen > 0)
  206.                 {
  207.                     FillNameTag(th,nameTagLen);
  208.                     th = (struct TrackHeader *)(((ULONG)th) + nameTagLen);
  209.                 }
  210.  
  211.                 AddAllocation(th);
  212.             }
  213.  
  214.             break;
  215.  
  216.         case ALLOCATIONTYPE_AllocVec:
  217.  
  218.             /* This will later contain the length long word. */
  219.             memSize += sizeof(ULONG);
  220.  
  221.             th = (*OldAllocMem)(nameTagLen + sizeof(*th) + preSize + memSize + postSize,attributes & (~MEMF_CLEAR),SysBase);
  222.             if(th != NULL)
  223.             {
  224.                 /* Store the name tag data in front of the header, then
  225.                  * adjust the header address.
  226.                  */
  227.                 if(nameTagLen > 0)
  228.                 {
  229.                     FillNameTag(th,nameTagLen);
  230.                     th = (struct TrackHeader *)(((ULONG)th) + nameTagLen);
  231.                 }
  232.  
  233.                 AddAllocation(th);
  234.             }
  235.  
  236.             break;
  237.  
  238.         case ALLOCATIONTYPE_AllocPooled:
  239.  
  240.             th = (*OldAllocPooled)(poolHeader->ph_PoolHeader,nameTagLen + sizeof(*th) + preSize + memSize + postSize,SysBase);
  241.             if(th != NULL)
  242.             {
  243.                 /* Store the name tag data in front of the header, then
  244.                  * adjust the header address.
  245.                  */
  246.                 if(nameTagLen > 0)
  247.                 {
  248.                     FillNameTag(th,nameTagLen);
  249.                     th = (struct TrackHeader *)(((ULONG)th) + nameTagLen);
  250.                 }
  251.  
  252.                 AddPuddle(poolHeader,th);
  253.             }
  254.  
  255.             break;
  256.  
  257.         default:
  258.  
  259.             th = NULL;
  260.             break;
  261.     }
  262.  
  263.     if(th != NULL)
  264.     {
  265.         STATIC ULONG Sequence;
  266.  
  267.         UBYTE * mem;
  268.  
  269.         /* Fill in the regular header data. */
  270.         th->th_Magic        = BASEBALL;
  271.         th->th_PointBack    = th;
  272.         th->th_PC            = pc;
  273.         th->th_Owner        = FindTask(NULL);
  274.         th->th_OwnerType    = GetTaskType(NULL);
  275.         th->th_NameTagLen    = nameTagLen;
  276.  
  277.         GetSysTime(&th->th_Time);
  278.         th->th_Sequence = Sequence++;
  279.  
  280.         th->th_Size            = memSize;
  281.         th->th_PoolHeader    = poolHeader;
  282.         th->th_Type            = type;
  283.         th->th_FillChar        = NewFillChar();
  284.         th->th_PostSize        = postSize;
  285.         th->th_Marked        = FALSE;
  286.  
  287.         /* Calculate the checksum. */
  288.         FixTrackHeaderChecksum(th);
  289.  
  290.         /* Fill in the preceding memory wall. */
  291.         mem = (UBYTE *)(th + 1);
  292.  
  293.         memset(mem,th->th_FillChar,preSize);
  294.         mem += preSize;
  295.  
  296.         /* Fill the memory allocation body either with
  297.          * junk or with zeroes.
  298.          */
  299.         if(FLAG_IS_CLEAR(attributes,MEMF_CLEAR))
  300.         {
  301.             MungMem((ULONG *)mem,memSize,DEADFOOD);
  302.         }
  303.         else
  304.         {
  305.             memset(mem,0,memSize);
  306.         }
  307.  
  308.         mem += memSize;
  309.  
  310.         /* Fill in the following memory wall. */
  311.         memset(mem,th->th_FillChar,postSize);
  312.  
  313.         mem = (UBYTE *)(th + 1);
  314.         mem += preSize;
  315.  
  316.         /* AllocVec()'ed allocations are special in that
  317.          * the size of the allocation precedes the header.
  318.          */
  319.         if(type == ALLOCATIONTYPE_AllocVec)
  320.         {
  321.             /* Size of the allocation must include the
  322.              * size long word.
  323.              */
  324.             (*(ULONG *)mem) = memSize + sizeof(ULONG);
  325.  
  326.             result = (APTR)(mem + sizeof(ULONG));
  327.         }
  328.         else
  329.         {
  330.             result = (APTR)mem;
  331.         }
  332.  
  333.         success = TRUE;
  334.     }
  335.  
  336.     (*resultPtr) = result;
  337.  
  338.     return(success);
  339. }
  340.  
  341. /******************************************************************************/
  342.  
  343. BOOL
  344. IsValidTrackHeader(struct TrackHeader * th)
  345. {
  346.     BOOL valid = FALSE;
  347.  
  348.     /* Check whether the calculated address looks good enough. */
  349.     if(NOT IsInvalidAddress((ULONG)th) && NOT IsOddAddress((ULONG)th))
  350.     {
  351.         /* Check for the unique identifiers. */
  352.         if(th->th_Magic == BASEBALL && th->th_PointBack == th)
  353.         {
  354.             valid = TRUE;
  355.         }
  356.     }
  357.  
  358.     return(valid);
  359. }
  360.  
  361. /******************************************************************************/
  362.  
  363. BOOL
  364. IsTrackHeaderChecksumCorrect(struct TrackHeader * th)
  365. {
  366.     BOOL isCorrect = FALSE;
  367.  
  368.     /* For extra safety, also take a look at the checksum. */
  369.     if(CalculateChecksum((ULONG *)&th->th_PoolHeader,
  370.                          sizeof(*th) - offsetof(struct TrackHeader,th_PoolHeader)) == (ULONG)-1)
  371.     {
  372.         isCorrect = TRUE;
  373.     }
  374.  
  375.     return(isCorrect);
  376. }
  377.  
  378. /******************************************************************************/
  379.  
  380. BOOL
  381. IsTrackedAllocation(
  382.     ULONG                    address,
  383.     struct TrackHeader **    resultPtr)
  384. {
  385.     struct TrackHeader * result = NULL;
  386.     struct TrackHeader * th;
  387.     BOOL valid = FALSE;
  388.  
  389.     /* Move back to the memory tracking header. */
  390.     th = (struct TrackHeader *)(address - PreWallSize - sizeof(*th));
  391.  
  392.     /* Check if the track header is valid. */
  393.     if(IsValidTrackHeader(th) && IsTrackHeaderChecksumCorrect(th))
  394.     {
  395.         result = th;
  396.         valid = TRUE;
  397.     }
  398.  
  399.     (*resultPtr) = result;
  400.  
  401.     return(valid);
  402. }
  403.  
  404. /******************************************************************************/
  405.  
  406. VOID
  407. SetupAllocationList(VOID)
  408. {
  409.     /* Initialize the list of regular memory allocations.
  410.      * Pooled allocations will be stored elsewhere.
  411.      */
  412.     NewList((struct List *)&AllocationList);
  413. }
  414.  
  415. /******************************************************************************/
  416.  
  417. VOID
  418. CheckAllocatedMemory(VOID)
  419. {
  420.     ULONG totalBytes;
  421.     ULONG totalAllocations;
  422.  
  423.     /* Check and count all regular memory allocations. We look for
  424.      * trashed memory walls and orphaned memory.
  425.      */
  426.  
  427.     totalBytes = 0;
  428.     totalAllocations = 0;
  429.  
  430.     Forbid();
  431.  
  432.     if(IsAllocationListConsistent())
  433.     {
  434.         struct TrackHeader * th;
  435.  
  436.         for(th = (struct TrackHeader *)AllocationList.mlh_Head ;
  437.             th->th_MinNode.mln_Succ != NULL ;
  438.             th = (struct TrackHeader *)th->th_MinNode.mln_Succ)
  439.         {
  440.             /* A magic value of 0 indicates a "dead" allocation
  441.              * that we left to its own devices. We don't want it
  442.              * to show up in our list.
  443.              */
  444.             if(th->th_Magic != 0)
  445.             {
  446.                 /* Check for trashed memory walls. */
  447.                 CheckStomping(NULL,th);
  448.         
  449.                 /* Check if its creator is still with us. */
  450.                 if(NOT IsTaskStillAround(th->th_Owner))
  451.                 {
  452.                     VoiceComplaint(NULL,th,"Orphaned allocation?\n");
  453.                 }
  454.         
  455.                 totalBytes += th->th_Size;
  456.                 totalAllocations++;
  457.             }
  458.         }
  459.     }
  460.  
  461.     Permit();
  462.  
  463.     DPrintf("%ld byte(s) in %ld single allocation(s).\n",totalBytes,totalAllocations);
  464. }
  465.  
  466. /******************************************************************************/
  467.  
  468. VOID
  469. ShowUnmarkedMemory(VOID)
  470. {
  471.     ULONG totalBytes;
  472.     ULONG totalAllocations;
  473.  
  474.     /* Show and count all unmarked regular memory allocations. */
  475.  
  476.     totalBytes = 0;
  477.     totalAllocations = 0;
  478.  
  479.     Forbid();
  480.  
  481.     if(IsAllocationListConsistent())
  482.     {
  483.         struct TrackHeader * th;
  484.  
  485.         for(th = (struct TrackHeader *)AllocationList.mlh_Head ;
  486.             th->th_MinNode.mln_Succ != NULL ;
  487.             th = (struct TrackHeader *)th->th_MinNode.mln_Succ)
  488.         {
  489.             /* A magic value of 0 indicates a "dead" allocation
  490.              * that we left to its own devices. We don't want it
  491.              * to show up in our list.
  492.              */
  493.             if(th->th_Magic != 0)
  494.             {
  495.                 if(NOT th->th_Marked)
  496.                 {
  497.                     VoiceComplaint(NULL,th,NULL);
  498.                 }
  499.     
  500.                 totalBytes += th->th_Size;
  501.                 totalAllocations++;
  502.             }
  503.         }
  504.     }
  505.  
  506.     Permit();
  507.  
  508.     DPrintf("%ld byte(s) in %ld single allocation(s).\n",totalBytes,totalAllocations);
  509. }
  510.  
  511. /******************************************************************************/
  512.  
  513. VOID
  514. ChangeMemoryMarks(BOOL markSet)
  515. {
  516.     /* Mark or unmark all memory puddles. */
  517.  
  518.     Forbid();
  519.  
  520.     if(IsAllocationListConsistent())
  521.     {
  522.         struct TrackHeader * th;
  523.     
  524.         for(th = (struct TrackHeader *)AllocationList.mlh_Head ;
  525.             th->th_MinNode.mln_Succ != NULL ;
  526.             th = (struct TrackHeader *)th->th_MinNode.mln_Succ)
  527.         {
  528.             /* A magic value of 0 indicates a "dead" allocation
  529.              * that we left to its own devices.
  530.              */
  531.             if(th->th_Magic != 0)
  532.             {
  533.                 th->th_Marked = markSet;
  534.     
  535.                 /* Repair the checksum value. */
  536.                 FixTrackHeaderChecksum(th);
  537.             }
  538.         }
  539.     }
  540.  
  541.     Permit();
  542. }
  543.  
  544. /******************************************************************************/
  545.  
  546. BOOL
  547. IsAllocationListConsistent(VOID)
  548. {
  549.     BOOL isConsistent = TRUE;
  550.  
  551.     Forbid();
  552.  
  553.     if(NOT IsMemoryListConsistent(&AllocationList))
  554.     {
  555.         isConsistent = FALSE;
  556.  
  557.         DPrintf("\a** TRACKED MEMORY LIST INCONSISTENT!!! **\n");
  558.  
  559.         NewList((struct List *)&AllocationList);
  560.     }
  561.  
  562.     Permit();
  563.  
  564.     return(isConsistent);
  565. }
  566.  
  567. /******************************************************************************/
  568.  
  569. BOOL
  570. IsMemoryListConsistent(struct MinList * mlh)
  571. {
  572.     BOOL isConsistent = TRUE;
  573.  
  574.     if(CheckConsistency)
  575.     {
  576.         struct TrackHeader * th;
  577.         struct timeval lastTime = {0,0};
  578.         ULONG lastSequence = 0;
  579.         BOOL haveData = FALSE;
  580.     
  581.         for(th = (struct TrackHeader *)mlh->mlh_Head ;
  582.             th->th_MinNode.mln_Succ != NULL ;
  583.             th = (struct TrackHeader *)th->th_MinNode.mln_Succ)
  584.         {
  585.             /* check whether the header data is consistent */
  586.             if(NOT IsInvalidAddress((ULONG)th) &&
  587.                NOT IsOddAddress((ULONG)th) &&
  588.                IsTrackHeaderChecksumCorrect(th))
  589.             {
  590.                 /* do not test dead allocations */
  591.                 if(th->th_Magic != 0)
  592.                 {
  593.                     /* check for the unique identifiers */
  594.                     if(th->th_Magic == BASEBALL && th->th_PointBack == th)
  595.                     {
  596.                         /* the following is to check whether there are
  597.                          * cycles in the allocation list which may have
  598.                          * resulted through strange and unlikely memory
  599.                          * trashing
  600.                          */
  601.                         if(haveData)
  602.                         {
  603.                             LONG result = (-CmpTime(&th->th_Time,&lastTime));
  604.         
  605.                             if(result == 0) /* both allocation times are the same? */
  606.                             {
  607.                                 /* allocation sequence is smaller than previous? */
  608.                                 if(th->th_Sequence <= lastSequence)
  609.                                 {
  610.                                     isConsistent = FALSE;
  611.                                     break;
  612.                                 }
  613.                             }
  614.                             else if (result < 0) /* allocation is older than previous? */
  615.                             {
  616.                                 isConsistent = FALSE;
  617.                             }
  618.                         }
  619.         
  620.                         lastTime        = th->th_Time;
  621.                         lastSequence    = th->th_Sequence;
  622.         
  623.                         haveData = TRUE;
  624.                     }
  625.                     else
  626.                     {
  627.                         isConsistent = FALSE;
  628.                         break;
  629.                     }
  630.                 }
  631.             }
  632.             else
  633.             {
  634.                 isConsistent = FALSE;
  635.                 break;
  636.             }
  637.         }
  638.     }
  639.  
  640.     return(isConsistent);
  641. }
  642.