LCOV - code coverage report
Current view: top level - contrib/bloom - blutils.c (source / functions) Hit Total Coverage
Test: PostgreSQL 14devel Lines: 164 179 91.6 %
Date: 2020-12-05 16:06:12 Functions: 14 15 93.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * blutils.c
       4             :  *      Bloom index utilities.
       5             :  *
       6             :  * Portions Copyright (c) 2016-2020, PostgreSQL Global Development Group
       7             :  * Portions Copyright (c) 1990-1993, Regents of the University of California
       8             :  *
       9             :  * IDENTIFICATION
      10             :  *    contrib/bloom/blutils.c
      11             :  *
      12             :  *-------------------------------------------------------------------------
      13             :  */
      14             : #include "postgres.h"
      15             : 
      16             : #include "access/amapi.h"
      17             : #include "access/generic_xlog.h"
      18             : #include "access/reloptions.h"
      19             : #include "bloom.h"
      20             : #include "catalog/index.h"
      21             : #include "commands/vacuum.h"
      22             : #include "miscadmin.h"
      23             : #include "storage/bufmgr.h"
      24             : #include "storage/freespace.h"
      25             : #include "storage/indexfsm.h"
      26             : #include "storage/lmgr.h"
      27             : #include "utils/memutils.h"
      28             : 
      29             : /* Signature dealing macros - note i is assumed to be of type int */
      30             : #define GETWORD(x,i) ( *( (BloomSignatureWord *)(x) + ( (i) / SIGNWORDBITS ) ) )
      31             : #define CLRBIT(x,i)   GETWORD(x,i) &= ~( 0x01 << ( (i) % SIGNWORDBITS ) )
      32             : #define SETBIT(x,i)   GETWORD(x,i) |=  ( 0x01 << ( (i) % SIGNWORDBITS ) )
      33             : #define GETBIT(x,i) ( (GETWORD(x,i) >> ( (i) % SIGNWORDBITS )) & 0x01 )
      34             : 
      35           4 : PG_FUNCTION_INFO_V1(blhandler);
      36             : 
      37             : /* Kind of relation options for bloom index */
      38             : static relopt_kind bl_relopt_kind;
      39             : 
      40             : /* parse table for fillRelOptions */
      41             : static relopt_parse_elt bl_relopt_tab[INDEX_MAX_KEYS + 1];
      42             : 
      43             : static int32 myRand(void);
      44             : static void mySrand(uint32 seed);
      45             : 
      46             : /*
      47             :  * Module initialize function: initialize info about Bloom relation options.
      48             :  *
      49             :  * Note: keep this in sync with makeDefaultBloomOptions().
      50             :  */
      51             : void
      52           2 : _PG_init(void)
      53             : {
      54             :     int         i;
      55             :     char        buf[16];
      56             : 
      57           2 :     bl_relopt_kind = add_reloption_kind();
      58             : 
      59             :     /* Option for length of signature */
      60           2 :     add_int_reloption(bl_relopt_kind, "length",
      61             :                       "Length of signature in bits",
      62             :                       DEFAULT_BLOOM_LENGTH, 1, MAX_BLOOM_LENGTH,
      63             :                       AccessExclusiveLock);
      64           2 :     bl_relopt_tab[0].optname = "length";
      65           2 :     bl_relopt_tab[0].opttype = RELOPT_TYPE_INT;
      66           2 :     bl_relopt_tab[0].offset = offsetof(BloomOptions, bloomLength);
      67             : 
      68             :     /* Number of bits for each possible index column: col1, col2, ... */
      69          66 :     for (i = 0; i < INDEX_MAX_KEYS; i++)
      70             :     {
      71          64 :         snprintf(buf, sizeof(buf), "col%d", i + 1);
      72          64 :         add_int_reloption(bl_relopt_kind, buf,
      73             :                           "Number of bits generated for each index column",
      74             :                           DEFAULT_BLOOM_BITS, 1, MAX_BLOOM_BITS,
      75             :                           AccessExclusiveLock);
      76          64 :         bl_relopt_tab[i + 1].optname = MemoryContextStrdup(TopMemoryContext,
      77             :                                                            buf);
      78          64 :         bl_relopt_tab[i + 1].opttype = RELOPT_TYPE_INT;
      79          64 :         bl_relopt_tab[i + 1].offset = offsetof(BloomOptions, bitSize[0]) + sizeof(int) * i;
      80             :     }
      81           2 : }
      82             : 
      83             : /*
      84             :  * Construct a default set of Bloom options.
      85             :  */
      86             : static BloomOptions *
      87           0 : makeDefaultBloomOptions(void)
      88             : {
      89             :     BloomOptions *opts;
      90             :     int         i;
      91             : 
      92           0 :     opts = (BloomOptions *) palloc0(sizeof(BloomOptions));
      93             :     /* Convert DEFAULT_BLOOM_LENGTH from # of bits to # of words */
      94           0 :     opts->bloomLength = (DEFAULT_BLOOM_LENGTH + SIGNWORDBITS - 1) / SIGNWORDBITS;
      95           0 :     for (i = 0; i < INDEX_MAX_KEYS; i++)
      96           0 :         opts->bitSize[i] = DEFAULT_BLOOM_BITS;
      97           0 :     SET_VARSIZE(opts, sizeof(BloomOptions));
      98           0 :     return opts;
      99             : }
     100             : 
     101             : /*
     102             :  * Bloom handler function: return IndexAmRoutine with access method parameters
     103             :  * and callbacks.
     104             :  */
     105             : Datum
     106          42 : blhandler(PG_FUNCTION_ARGS)
     107             : {
     108          42 :     IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);
     109             : 
     110          42 :     amroutine->amstrategies = BLOOM_NSTRATEGIES;
     111          42 :     amroutine->amsupport = BLOOM_NPROC;
     112          42 :     amroutine->amoptsprocnum = BLOOM_OPTIONS_PROC;
     113          42 :     amroutine->amcanorder = false;
     114          42 :     amroutine->amcanorderbyop = false;
     115          42 :     amroutine->amcanbackward = false;
     116          42 :     amroutine->amcanunique = false;
     117          42 :     amroutine->amcanmulticol = true;
     118          42 :     amroutine->amoptionalkey = true;
     119          42 :     amroutine->amsearcharray = false;
     120          42 :     amroutine->amsearchnulls = false;
     121          42 :     amroutine->amstorage = false;
     122          42 :     amroutine->amclusterable = false;
     123          42 :     amroutine->ampredlocks = false;
     124          42 :     amroutine->amcanparallel = false;
     125          42 :     amroutine->amcaninclude = false;
     126          42 :     amroutine->amusemaintenanceworkmem = false;
     127          42 :     amroutine->amparallelvacuumoptions =
     128             :         VACUUM_OPTION_PARALLEL_BULKDEL | VACUUM_OPTION_PARALLEL_CLEANUP;
     129          42 :     amroutine->amkeytype = InvalidOid;
     130             : 
     131          42 :     amroutine->ambuild = blbuild;
     132          42 :     amroutine->ambuildempty = blbuildempty;
     133          42 :     amroutine->aminsert = blinsert;
     134          42 :     amroutine->ambulkdelete = blbulkdelete;
     135          42 :     amroutine->amvacuumcleanup = blvacuumcleanup;
     136          42 :     amroutine->amcanreturn = NULL;
     137          42 :     amroutine->amcostestimate = blcostestimate;
     138          42 :     amroutine->amoptions = bloptions;
     139          42 :     amroutine->amproperty = NULL;
     140          42 :     amroutine->ambuildphasename = NULL;
     141          42 :     amroutine->amvalidate = blvalidate;
     142          42 :     amroutine->amadjustmembers = NULL;
     143          42 :     amroutine->ambeginscan = blbeginscan;
     144          42 :     amroutine->amrescan = blrescan;
     145          42 :     amroutine->amgettuple = NULL;
     146          42 :     amroutine->amgetbitmap = blgetbitmap;
     147          42 :     amroutine->amendscan = blendscan;
     148          42 :     amroutine->ammarkpos = NULL;
     149          42 :     amroutine->amrestrpos = NULL;
     150          42 :     amroutine->amestimateparallelscan = NULL;
     151          42 :     amroutine->aminitparallelscan = NULL;
     152          42 :     amroutine->amparallelrescan = NULL;
     153             : 
     154          42 :     PG_RETURN_POINTER(amroutine);
     155             : }
     156             : 
     157             : /*
     158             :  * Fill BloomState structure for particular index.
     159             :  */
     160             : void
     161        8042 : initBloomState(BloomState *state, Relation index)
     162             : {
     163             :     int         i;
     164             : 
     165        8042 :     state->nColumns = index->rd_att->natts;
     166             : 
     167             :     /* Initialize hash function for each attribute */
     168       24126 :     for (i = 0; i < index->rd_att->natts; i++)
     169             :     {
     170       16084 :         fmgr_info_copy(&(state->hashFn[i]),
     171       16084 :                        index_getprocinfo(index, i + 1, BLOOM_HASH_PROC),
     172             :                        CurrentMemoryContext);
     173       16084 :         state->collations[i] = index->rd_indcollation[i];
     174             :     }
     175             : 
     176             :     /* Initialize amcache if needed with options from metapage */
     177        8042 :     if (!index->rd_amcache)
     178             :     {
     179             :         Buffer      buffer;
     180             :         Page        page;
     181             :         BloomMetaPageData *meta;
     182             :         BloomOptions *opts;
     183             : 
     184          18 :         opts = MemoryContextAlloc(index->rd_indexcxt, sizeof(BloomOptions));
     185             : 
     186          18 :         buffer = ReadBuffer(index, BLOOM_METAPAGE_BLKNO);
     187          18 :         LockBuffer(buffer, BUFFER_LOCK_SHARE);
     188             : 
     189          18 :         page = BufferGetPage(buffer);
     190             : 
     191          18 :         if (!BloomPageIsMeta(page))
     192           0 :             elog(ERROR, "Relation is not a bloom index");
     193          18 :         meta = BloomPageGetMeta(BufferGetPage(buffer));
     194             : 
     195          18 :         if (meta->magickNumber != BLOOM_MAGICK_NUMBER)
     196           0 :             elog(ERROR, "Relation is not a bloom index");
     197             : 
     198          18 :         *opts = meta->opts;
     199             : 
     200          18 :         UnlockReleaseBuffer(buffer);
     201             : 
     202          18 :         index->rd_amcache = (void *) opts;
     203             :     }
     204             : 
     205        8042 :     memcpy(&state->opts, index->rd_amcache, sizeof(state->opts));
     206        8042 :     state->sizeOfBloomTuple = BLOOMTUPLEHDRSZ +
     207        8042 :         sizeof(BloomSignatureWord) * state->opts.bloomLength;
     208        8042 : }
     209             : 
     210             : /*
     211             :  * Random generator copied from FreeBSD.  Using own random generator here for
     212             :  * two reasons:
     213             :  *
     214             :  * 1) In this case random numbers are used for on-disk storage.  Usage of
     215             :  *    PostgreSQL number generator would obstruct it from all possible changes.
     216             :  * 2) Changing seed of PostgreSQL random generator would be undesirable side
     217             :  *    effect.
     218             :  */
     219             : static int32 next;
     220             : 
     221             : static int32
     222      187514 : myRand(void)
     223             : {
     224             :     /*----------
     225             :      * Compute x = (7^5 * x) mod (2^31 - 1)
     226             :      * without overflowing 31 bits:
     227             :      *      (2^31 - 1) = 127773 * (7^5) + 2836
     228             :      * From "Random number generators: good ones are hard to find",
     229             :      * Park and Miller, Communications of the ACM, vol. 31, no. 10,
     230             :      * October 1988, p. 1195.
     231             :      *----------
     232             :      */
     233             :     int32       hi,
     234             :                 lo,
     235             :                 x;
     236             : 
     237             :     /* Must be in [1, 0x7ffffffe] range at this point. */
     238      187514 :     hi = next / 127773;
     239      187514 :     lo = next % 127773;
     240      187514 :     x = 16807 * lo - 2836 * hi;
     241      187514 :     if (x < 0)
     242       36204 :         x += 0x7fffffff;
     243      187514 :     next = x;
     244             :     /* Transform to [0, 0x7ffffffd] range. */
     245      187514 :     return (x - 1);
     246             : }
     247             : 
     248             : static void
     249      102144 : mySrand(uint32 seed)
     250             : {
     251      102144 :     next = seed;
     252             :     /* Transform to [1, 0x7ffffffe] range. */
     253      102144 :     next = (next % 0x7ffffffe) + 1;
     254      102144 : }
     255             : 
     256             : /*
     257             :  * Add bits of given value to the signature.
     258             :  */
     259             : void
     260       51072 : signValue(BloomState *state, BloomSignatureWord *sign, Datum value, int attno)
     261             : {
     262             :     uint32      hashVal;
     263             :     int         nBit,
     264             :                 j;
     265             : 
     266             :     /*
     267             :      * init generator with "column's" number to get "hashed" seed for new
     268             :      * value. We don't want to map the same numbers from different columns
     269             :      * into the same bits!
     270             :      */
     271       51072 :     mySrand(attno);
     272             : 
     273             :     /*
     274             :      * Init hash sequence to map our value into bits. the same values in
     275             :      * different columns will be mapped into different bits because of step
     276             :      * above
     277             :      */
     278       51072 :     hashVal = DatumGetInt32(FunctionCall1Coll(&state->hashFn[attno], state->collations[attno], value));
     279       51072 :     mySrand(hashVal ^ myRand());
     280             : 
     281      187514 :     for (j = 0; j < state->opts.bitSize[attno]; j++)
     282             :     {
     283             :         /* prevent multiple evaluation in SETBIT macro */
     284      136442 :         nBit = myRand() % (state->opts.bloomLength * SIGNWORDBITS);
     285      136442 :         SETBIT(sign, nBit);
     286             :     }
     287       51072 : }
     288             : 
     289             : /*
     290             :  * Make bloom tuple from values.
     291             :  */
     292             : BloomTuple *
     293       25516 : BloomFormTuple(BloomState *state, ItemPointer iptr, Datum *values, bool *isnull)
     294             : {
     295             :     int         i;
     296       25516 :     BloomTuple *res = (BloomTuple *) palloc0(state->sizeOfBloomTuple);
     297             : 
     298       25516 :     res->heapPtr = *iptr;
     299             : 
     300             :     /* Blooming each column */
     301       76548 :     for (i = 0; i < state->nColumns; i++)
     302             :     {
     303             :         /* skip nulls */
     304       51032 :         if (isnull[i])
     305           0 :             continue;
     306             : 
     307       51032 :         signValue(state, res->sign, values[i], i);
     308             :     }
     309             : 
     310       25516 :     return res;
     311             : }
     312             : 
     313             : /*
     314             :  * Add new bloom tuple to the page.  Returns true if new tuple was successfully
     315             :  * added to the page.  Returns false if it doesn't fit on the page.
     316             :  */
     317             : bool
     318       25554 : BloomPageAddItem(BloomState *state, Page page, BloomTuple *tuple)
     319             : {
     320             :     BloomTuple *itup;
     321             :     BloomPageOpaque opaque;
     322             :     Pointer     ptr;
     323             : 
     324             :     /* We shouldn't be pointed to an invalid page */
     325             :     Assert(!PageIsNew(page) && !BloomPageIsDeleted(page));
     326             : 
     327             :     /* Does new tuple fit on the page? */
     328       25554 :     if (BloomPageGetFreeSpace(state, page) < state->sizeOfBloomTuple)
     329          38 :         return false;
     330             : 
     331             :     /* Copy new tuple to the end of page */
     332       25516 :     opaque = BloomPageGetOpaque(page);
     333       25516 :     itup = BloomPageGetTuple(state, page, opaque->maxoff + 1);
     334       25516 :     memcpy((Pointer) itup, (Pointer) tuple, state->sizeOfBloomTuple);
     335             : 
     336             :     /* Adjust maxoff and pd_lower */
     337       25516 :     opaque->maxoff++;
     338       25516 :     ptr = (Pointer) BloomPageGetTuple(state, page, opaque->maxoff + 1);
     339       25516 :     ((PageHeader) page)->pd_lower = ptr - page;
     340             : 
     341             :     /* Assert we didn't overrun available space */
     342             :     Assert(((PageHeader) page)->pd_lower <= ((PageHeader) page)->pd_upper);
     343             : 
     344       25516 :     return true;
     345             : }
     346             : 
     347             : /*
     348             :  * Allocate a new page (either by recycling, or by extending the index file)
     349             :  * The returned buffer is already pinned and exclusive-locked
     350             :  * Caller is responsible for initializing the page by calling BloomInitPage
     351             :  */
     352             : Buffer
     353          50 : BloomNewBuffer(Relation index)
     354             : {
     355             :     Buffer      buffer;
     356             :     bool        needLock;
     357             : 
     358             :     /* First, try to get a page from FSM */
     359             :     for (;;)
     360           0 :     {
     361          50 :         BlockNumber blkno = GetFreeIndexPage(index);
     362             : 
     363          50 :         if (blkno == InvalidBlockNumber)
     364          48 :             break;
     365             : 
     366           2 :         buffer = ReadBuffer(index, blkno);
     367             : 
     368             :         /*
     369             :          * We have to guard against the possibility that someone else already
     370             :          * recycled this page; the buffer may be locked if so.
     371             :          */
     372           2 :         if (ConditionalLockBuffer(buffer))
     373             :         {
     374           2 :             Page        page = BufferGetPage(buffer);
     375             : 
     376           2 :             if (PageIsNew(page))
     377           0 :                 return buffer;  /* OK to use, if never initialized */
     378             : 
     379           2 :             if (BloomPageIsDeleted(page))
     380           2 :                 return buffer;  /* OK to use */
     381             : 
     382           0 :             LockBuffer(buffer, BUFFER_LOCK_UNLOCK);
     383             :         }
     384             : 
     385             :         /* Can't use it, so release buffer and try again */
     386           0 :         ReleaseBuffer(buffer);
     387             :     }
     388             : 
     389             :     /* Must extend the file */
     390          48 :     needLock = !RELATION_IS_LOCAL(index);
     391          48 :     if (needLock)
     392          20 :         LockRelationForExtension(index, ExclusiveLock);
     393             : 
     394          48 :     buffer = ReadBuffer(index, P_NEW);
     395          48 :     LockBuffer(buffer, BUFFER_LOCK_EXCLUSIVE);
     396             : 
     397          48 :     if (needLock)
     398          20 :         UnlockRelationForExtension(index, ExclusiveLock);
     399             : 
     400          48 :     return buffer;
     401             : }
     402             : 
     403             : /*
     404             :  * Initialize any page of a bloom index.
     405             :  */
     406             : void
     407          52 : BloomInitPage(Page page, uint16 flags)
     408             : {
     409             :     BloomPageOpaque opaque;
     410             : 
     411          52 :     PageInit(page, BLCKSZ, sizeof(BloomPageOpaqueData));
     412             : 
     413          52 :     opaque = BloomPageGetOpaque(page);
     414          52 :     memset(opaque, 0, sizeof(BloomPageOpaqueData));
     415          52 :     opaque->flags = flags;
     416          52 :     opaque->bloom_page_id = BLOOM_PAGE_ID;
     417          52 : }
     418             : 
     419             : /*
     420             :  * Fill in metapage for bloom index.
     421             :  */
     422             : void
     423          10 : BloomFillMetapage(Relation index, Page metaPage)
     424             : {
     425             :     BloomOptions *opts;
     426             :     BloomMetaPageData *metadata;
     427             : 
     428             :     /*
     429             :      * Choose the index's options.  If reloptions have been assigned, use
     430             :      * those, otherwise create default options.
     431             :      */
     432          10 :     opts = (BloomOptions *) index->rd_options;
     433          10 :     if (!opts)
     434           0 :         opts = makeDefaultBloomOptions();
     435             : 
     436             :     /*
     437             :      * Initialize contents of meta page, including a copy of the options,
     438             :      * which are now frozen for the life of the index.
     439             :      */
     440          10 :     BloomInitPage(metaPage, BLOOM_META);
     441          10 :     metadata = BloomPageGetMeta(metaPage);
     442          10 :     memset(metadata, 0, sizeof(BloomMetaPageData));
     443          10 :     metadata->magickNumber = BLOOM_MAGICK_NUMBER;
     444          10 :     metadata->opts = *opts;
     445          10 :     ((PageHeader) metaPage)->pd_lower += sizeof(BloomMetaPageData);
     446             : 
     447             :     /* If this fails, probably FreeBlockNumberArray size calc is wrong: */
     448             :     Assert(((PageHeader) metaPage)->pd_lower <= ((PageHeader) metaPage)->pd_upper);
     449          10 : }
     450             : 
     451             : /*
     452             :  * Initialize metapage for bloom index.
     453             :  */
     454             : void
     455           8 : BloomInitMetapage(Relation index)
     456             : {
     457             :     Buffer      metaBuffer;
     458             :     Page        metaPage;
     459             :     GenericXLogState *state;
     460             : 
     461             :     /*
     462             :      * Make a new page; since it is first page it should be associated with
     463             :      * block number 0 (BLOOM_METAPAGE_BLKNO).
     464             :      */
     465           8 :     metaBuffer = BloomNewBuffer(index);
     466             :     Assert(BufferGetBlockNumber(metaBuffer) == BLOOM_METAPAGE_BLKNO);
     467             : 
     468             :     /* Initialize contents of meta page */
     469           8 :     state = GenericXLogStart(index);
     470           8 :     metaPage = GenericXLogRegisterBuffer(state, metaBuffer,
     471             :                                          GENERIC_XLOG_FULL_IMAGE);
     472           8 :     BloomFillMetapage(index, metaPage);
     473           8 :     GenericXLogFinish(state);
     474             : 
     475           8 :     UnlockReleaseBuffer(metaBuffer);
     476           8 : }
     477             : 
     478             : /*
     479             :  * Parse reloptions for bloom index, producing a BloomOptions struct.
     480             :  */
     481             : bytea *
     482          42 : bloptions(Datum reloptions, bool validate)
     483             : {
     484             :     BloomOptions *rdopts;
     485             : 
     486             :     /* Parse the user-given reloptions */
     487          42 :     rdopts = (BloomOptions *) build_reloptions(reloptions, validate,
     488             :                                                bl_relopt_kind,
     489             :                                                sizeof(BloomOptions),
     490             :                                                bl_relopt_tab,
     491             :                                                lengthof(bl_relopt_tab));
     492             : 
     493             :     /* Convert signature length from # of bits to # to words, rounding up */
     494          38 :     if (rdopts)
     495          38 :         rdopts->bloomLength = (rdopts->bloomLength + SIGNWORDBITS - 1) / SIGNWORDBITS;
     496             : 
     497          38 :     return (bytea *) rdopts;
     498             : }

Generated by: LCOV version 1.13