home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / access / heap / hrnd.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  6.2 KB  |  291 lines
  1. /*
  2.  * hrnd.c --
  3.  *    POSTGRES heap access method randomization code.
  4.  */
  5.  
  6. #include "tmp/c.h"
  7.  
  8. RcsId("$Header: /private/postgres/src/access/heap/RCS/hrnd.c,v 1.8 1992/03/05 00:36:25 hong Exp $");
  9.  
  10. #include "storage/block.h"
  11. #include "storage/buf.h"
  12. #include "storage/bufmgr.h"
  13. #include "storage/bufpage.h"
  14.  
  15. #include "utils/memutils.h"
  16. #include "utils/rel.h"
  17.  
  18. #ifdef    RANDOMDEBUG
  19. #include "utils/log.h"
  20. #endif    /* defined(RANDOMDEBUG) */
  21.  
  22. #include "access/hrnd.h"
  23.  
  24. static bool        DisableHeapRandomization = false;
  25. static BlockNumber    RandomBlockIndexList[1 + MaxLengthOfBlockIndexList];
  26. static bool        ClusterIsEnabled;
  27. static BlockNumber    ClusterBlockIndex;
  28.  
  29. /*
  30.  * BlockIndexRandomlyFillRandomBlockIndexList --
  31.  *    Fills RandomBlockIndexList with random indexes given number of blocks.
  32.  */
  33. extern
  34. void
  35. BlockIndexRandomlyFillRandomBlockIndexList ARGS((
  36.     BlockNumber    numberOfBlocks
  37. ));
  38.  
  39. /*
  40.  * BlockIndexFillRandomBlockIndexList --
  41.  *    Fills RandomBlockIndexList with indexes given number of blocks and id.
  42.  */
  43. extern
  44. void
  45. BlockIndexFillRandomBlockIndexList ARGS((
  46.     BlockNumber    numberOfBlocks,
  47.     ObjectId    id
  48. ));
  49.  
  50. /*
  51.  * ObjectIdHashBlockIndex --
  52.  *    Returns a block index hashed from an object id.
  53.  */
  54. extern
  55. BlockNumber
  56. ObjectIdHashBlockIndex ARGS((
  57.     ObjectId    id,
  58.     Index        method
  59. ));
  60.  
  61. void
  62. InitRandom()
  63. {
  64.     extern Pointer    getenv();
  65.  
  66.     if (PointerIsValid(getenv("POSTGROWS"))) {
  67.         DisableHeapRandomization = true;
  68.         RandomBlockIndexList[0] = InvalidBlockNumber;
  69.     } else {
  70.         DisableHeapRandomization = false;
  71.         RandomBlockIndexList[MaxLengthOfBlockIndexList] =
  72.             InvalidBlockNumber;
  73.     }
  74.     ClusterBlockIndex = InvalidBlockNumber;
  75. }
  76.  
  77. void
  78. setclusteredappend(on)
  79.     bool    on;
  80. {
  81.     ClusterBlockIndex = InvalidBlockNumber;
  82.     ClusterIsEnabled = on;
  83. }
  84.  
  85. BlockNumber
  86. getclusterblockindex()
  87. {
  88.     if (!ClusterIsEnabled) {
  89.         Assert(!BlockNumberIsValid(ClusterBlockIndex));
  90.     }
  91.     return (ClusterBlockIndex);
  92. }
  93.  
  94. void
  95. setclusterblockindex(blockIndex)
  96.     BlockNumber    blockIndex;
  97. {
  98.     Assert(BlockNumberIsValid(blockIndex));
  99.  
  100.     if (ClusterIsEnabled) {
  101.         ClusterBlockIndex = blockIndex;
  102.  
  103. #ifdef    RANDOMDEBUG
  104.         elog(DEBUG, "setclusterblockindex(%d)", blockIndex);
  105. #endif    /* defined(RANDOMDEBUG) */
  106.     }
  107. }
  108.  
  109. BlockIndexList
  110. RelationGetRandomBlockIndexList(relation, id)
  111.     Relation    relation;
  112.     ObjectId    id;
  113. {
  114.     Assert(RelationIsValid(relation));
  115.  
  116.     if (!DisableHeapRandomization) {
  117.         if (!ObjectIdIsValid(id)) {
  118.             BlockIndexRandomlyFillRandomBlockIndexList(
  119.                 RelationGetNumberOfBlocks(relation));
  120.         } else {
  121.             BlockIndexFillRandomBlockIndexList(
  122.                 RelationGetNumberOfBlocks(relation), id);
  123.         }
  124.     }
  125.  
  126.     return (RandomBlockIndexList);
  127. }
  128.  
  129. /*
  130.  * XXX RelationContainsUsableBlock uses heuristics instead of statistics.
  131.  */
  132. bool
  133. RelationContainsUsableBlock(relation, blockIndex, size, numberOfFailures)
  134.     Relation    relation;
  135.     BlockNumber    blockIndex;
  136.     Size        size;
  137.     Index        numberOfFailures;
  138. {
  139.     BlockNumber    numberOfBlocks;
  140.     BlockSize    fillLimit;
  141.     PageFreeSpace    pageFreeSpace;
  142.     Buffer        buffer;
  143.  
  144.     Assert(RelationIsValid(relation));
  145.     Assert(size < BLCKSZ);
  146.  
  147.     numberOfBlocks = RelationGetNumberOfBlocks(relation);
  148.     Assert(numberOfBlocks > 0);
  149.  
  150. #ifndef    DOCLUSTER
  151.     if (/* type of relation is temporary */ 1) {
  152.         fillLimit = 0;        /* XXX -1 is better? */
  153.     } else
  154. #endif
  155.     if (ClusterIsEnabled &&
  156.             numberOfFailures == ClusteredNumberOfFailures) {
  157.  
  158.         fillLimit = ClusteredBlockFillLimit * (BLCKSZ / FillLimitBase);
  159.     } else {
  160.         switch (numberOfBlocks) {
  161.         case 1:
  162.             fillLimit = OneBlockFillLimit;
  163.             break;
  164.         case 2:
  165.             fillLimit = TwoBlockFillLimit;
  166.             break;
  167.         case 3:
  168.             fillLimit = ThreeBlockFillLimit;
  169.             break;
  170.         default:
  171.             fillLimit = ManyBlockFillLimit;
  172.             break;
  173.         }
  174.         fillLimit += FillLimitAdjustment(numberOfFailures);
  175.         fillLimit *= BLCKSZ / FillLimitBase;
  176.     }
  177.  
  178.     buffer = ReadBuffer(relation, blockIndex);
  179.     pageFreeSpace = PageGetFreeSpace(BufferSimpleGetPage(buffer));
  180.     ReleaseBuffer(buffer);
  181.  
  182.     return ((bool)((int32)pageFreeSpace - (int32)LONGALIGN(size) >
  183.         (int32)fillLimit));
  184. }
  185.  
  186. void
  187. BlockIndexRandomlyFillRandomBlockIndexList(numberOfBlocks)
  188.     BlockNumber    numberOfBlocks;
  189. {
  190.     Index    entry;
  191.  
  192.     if (numberOfBlocks < MaxLengthOfBlockIndexList) {
  193.         RandomBlockIndexList[numberOfBlocks] = InvalidBlockNumber;
  194.     }
  195.     for (entry = 0; entry < Min(numberOfBlocks, MaxLengthOfBlockIndexList);
  196.             entry += 1) {
  197.  
  198.         Index        index;
  199.  
  200.         do {
  201.             BlockNumber    blockIndex;
  202.  
  203.             blockIndex = random() % numberOfBlocks;
  204.             RandomBlockIndexList[entry] = blockIndex;
  205.             for (index = 0; index < entry; index += 1) {
  206.                 if (RandomBlockIndexList[index] == blockIndex) {
  207.                     break;
  208.                 }
  209.             }
  210.         } while (index != entry);
  211.     }
  212. #ifdef    RANDOMDEBUG
  213.     elog(DEBUG, "RandomlyFillRandomBlockIndexList returns [%d,%d,%d,%d]",
  214.         RandomBlockIndexList[0],
  215.         RandomBlockIndexList[1],
  216.         RandomBlockIndexList[2],
  217.         RandomBlockIndexList[3]);
  218. #endif    /* defined(RANDOMDEBUG) */
  219. }
  220.  
  221. void
  222. BlockIndexFillRandomBlockIndexList(numberOfBlocks, id)
  223.     BlockNumber    numberOfBlocks;
  224.     ObjectId    id;
  225. {
  226.     Index    entry;
  227.     Index    method = 0;
  228.  
  229.     if (numberOfBlocks < MaxLengthOfBlockIndexList) {
  230.         RandomBlockIndexList[numberOfBlocks] = InvalidBlockNumber;
  231.     }
  232.     for (entry = 0; entry < Min(numberOfBlocks, MaxLengthOfBlockIndexList);
  233.             entry += 1) {
  234.  
  235.         Index        index;
  236.  
  237.         do {
  238.             BlockNumber    blockIndex;
  239.  
  240.             blockIndex = ObjectIdHashBlockIndex(id, method)
  241.                 % numberOfBlocks;
  242.             method += 1;
  243.             RandomBlockIndexList[entry] = blockIndex;
  244.             for (index = 0; index < entry; index += 1) {
  245.                 if (RandomBlockIndexList[index] == blockIndex) {
  246.                     break;
  247.                 }
  248.             }
  249.         } while (index != entry);
  250.     }
  251. #ifdef    RANDOMDEBUG
  252.     elog(DEBUG, "FillRandomBlockIndexList(%d,%d) returns [%d,%d,%d,%d]",
  253.         numberOfBlocks, id,
  254.         RandomBlockIndexList[0],
  255.         RandomBlockIndexList[1],
  256.         RandomBlockIndexList[2],
  257.         RandomBlockIndexList[3]);
  258. #endif    /* defined(RANDOMDEBUG) */
  259. }
  260.  
  261. /* XXX tune me.  case 0 is not very random -> good? bad? */
  262. BlockNumber
  263. ObjectIdHashBlockIndex(id, method)
  264.     ObjectId    id;
  265.     Index        method;
  266. {
  267.     BlockNumber    index;
  268.  
  269.     switch (method % 5) {
  270.     case 0:
  271.         index = 17 + ((id << 2) ^ (id >> 1)) + id * (1 + (method >> 1));
  272.         break;
  273.     case 1:
  274.         index = 37 + ((id << 3) ^ (id >> 2)) + id * (method >> 2);
  275.         break;
  276.     case 2:
  277.         index = 67 + ((id << 5) ^ (id >> 3)) + id * (method >> 1);
  278.         break;
  279.     case 3:
  280.         index = 107 + ((id << 7) ^ (id >> 5)) + id * (method >> 2);
  281.         break;
  282.     case 4:
  283.         index = 137 + ((id << 11) ^ (id >> 7)) + id * (method >> 1);
  284.         break;
  285.     default:
  286.         Assert(false);
  287.         break;
  288.     }
  289.     return(index + method);
  290. }
  291.