LCOV - code coverage report
Current view: top level - contrib/bloom - blutils.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13beta1 Lines: 163 178 91.6 %
Date: 2020-06-01 07:06:57 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->ambeginscan = blbeginscan;
     143          42 :     amroutine->amrescan = blrescan;
     144          42 :     amroutine->amgettuple = NULL;
     145          42 :     amroutine->amgetbitmap = blgetbitmap;
     146          42 :     amroutine->amendscan = blendscan;
     147          42 :     amroutine->ammarkpos = NULL;
     148          42 :     amroutine->amrestrpos = NULL;
     149          42 :     amroutine->amestimateparallelscan = NULL;
     150          42 :     amroutine->aminitparallelscan = NULL;
     151          42 :     amroutine->amparallelrescan = NULL;
     152             : 
     153          42 :     PG_RETURN_POINTER(amroutine);
     154             : }
     155             : 
     156             : /*
     157             :  * Fill BloomState structure for particular index.
     158             :  */
     159             : void
     160        8042 : initBloomState(BloomState *state, Relation index)
     161             : {
     162             :     int         i;
     163             : 
     164        8042 :     state->nColumns = index->rd_att->natts;
     165             : 
     166             :     /* Initialize hash function for each attribute */
     167       24126 :     for (i = 0; i < index->rd_att->natts; i++)
     168             :     {
     169       16084 :         fmgr_info_copy(&(state->hashFn[i]),
     170       16084 :                        index_getprocinfo(index, i + 1, BLOOM_HASH_PROC),
     171             :                        CurrentMemoryContext);
     172       16084 :         state->collations[i] = index->rd_indcollation[i];
     173             :     }
     174             : 
     175             :     /* Initialize amcache if needed with options from metapage */
     176        8042 :     if (!index->rd_amcache)
     177             :     {
     178             :         Buffer      buffer;
     179             :         Page        page;
     180             :         BloomMetaPageData *meta;
     181             :         BloomOptions *opts;
     182             : 
     183          18 :         opts = MemoryContextAlloc(index->rd_indexcxt, sizeof(BloomOptions));
     184             : 
     185          18 :         buffer = ReadBuffer(index, BLOOM_METAPAGE_BLKNO);
     186          18 :         LockBuffer(buffer, BUFFER_LOCK_SHARE);
     187             : 
     188          18 :         page = BufferGetPage(buffer);
     189             : 
     190          18 :         if (!BloomPageIsMeta(page))
     191           0 :             elog(ERROR, "Relation is not a bloom index");
     192          18 :         meta = BloomPageGetMeta(BufferGetPage(buffer));
     193             : 
     194          18 :         if (meta->magickNumber != BLOOM_MAGICK_NUMBER)
     195           0 :             elog(ERROR, "Relation is not a bloom index");
     196             : 
     197          18 :         *opts = meta->opts;
     198             : 
     199          18 :         UnlockReleaseBuffer(buffer);
     200             : 
     201          18 :         index->rd_amcache = (void *) opts;
     202             :     }
     203             : 
     204        8042 :     memcpy(&state->opts, index->rd_amcache, sizeof(state->opts));
     205        8042 :     state->sizeOfBloomTuple = BLOOMTUPLEHDRSZ +
     206        8042 :         sizeof(BloomSignatureWord) * state->opts.bloomLength;
     207        8042 : }
     208             : 
     209             : /*
     210             :  * Random generator copied from FreeBSD.  Using own random generator here for
     211             :  * two reasons:
     212             :  *
     213             :  * 1) In this case random numbers are used for on-disk storage.  Usage of
     214             :  *    PostgreSQL number generator would obstruct it from all possible changes.
     215             :  * 2) Changing seed of PostgreSQL random generator would be undesirable side
     216             :  *    effect.
     217             :  */
     218             : static int32 next;
     219             : 
     220             : static int32
     221      187514 : myRand(void)
     222             : {
     223             :     /*----------
     224             :      * Compute x = (7^5 * x) mod (2^31 - 1)
     225             :      * without overflowing 31 bits:
     226             :      *      (2^31 - 1) = 127773 * (7^5) + 2836
     227             :      * From "Random number generators: good ones are hard to find",
     228             :      * Park and Miller, Communications of the ACM, vol. 31, no. 10,
     229             :      * October 1988, p. 1195.
     230             :      *----------
     231             :      */
     232             :     int32       hi,
     233             :                 lo,
     234             :                 x;
     235             : 
     236             :     /* Must be in [1, 0x7ffffffe] range at this point. */
     237      187514 :     hi = next / 127773;
     238      187514 :     lo = next % 127773;
     239      187514 :     x = 16807 * lo - 2836 * hi;
     240      187514 :     if (x < 0)
     241       36204 :         x += 0x7fffffff;
     242      187514 :     next = x;
     243             :     /* Transform to [0, 0x7ffffffd] range. */
     244      187514 :     return (x - 1);
     245             : }
     246             : 
     247             : static void
     248      102144 : mySrand(uint32 seed)
     249             : {
     250      102144 :     next = seed;
     251             :     /* Transform to [1, 0x7ffffffe] range. */
     252      102144 :     next = (next % 0x7ffffffe) + 1;
     253      102144 : }
     254             : 
     255             : /*
     256             :  * Add bits of given value to the signature.
     257             :  */
     258             : void
     259       51072 : signValue(BloomState *state, BloomSignatureWord *sign, Datum value, int attno)
     260             : {
     261             :     uint32      hashVal;
     262             :     int         nBit,
     263             :                 j;
     264             : 
     265             :     /*
     266             :      * init generator with "column's" number to get "hashed" seed for new
     267             :      * value. We don't want to map the same numbers from different columns
     268             :      * into the same bits!
     269             :      */
     270       51072 :     mySrand(attno);
     271             : 
     272             :     /*
     273             :      * Init hash sequence to map our value into bits. the same values in
     274             :      * different columns will be mapped into different bits because of step
     275             :      * above
     276             :      */
     277       51072 :     hashVal = DatumGetInt32(FunctionCall1Coll(&state->hashFn[attno], state->collations[attno], value));
     278       51072 :     mySrand(hashVal ^ myRand());
     279             : 
     280      187514 :     for (j = 0; j < state->opts.bitSize[attno]; j++)
     281             :     {
     282             :         /* prevent multiple evaluation in SETBIT macro */
     283      136442 :         nBit = myRand() % (state->opts.bloomLength * SIGNWORDBITS);
     284      136442 :         SETBIT(sign, nBit);
     285             :     }
     286       51072 : }
     287             : 
     288             : /*
     289             :  * Make bloom tuple from values.
     290             :  */
     291             : BloomTuple *
     292       25516 : BloomFormTuple(BloomState *state, ItemPointer iptr, Datum *values, bool *isnull)
     293             : {
     294             :     int         i;
     295       25516 :     BloomTuple *res = (BloomTuple *) palloc0(state->sizeOfBloomTuple);
     296             : 
     297       25516 :     res->heapPtr = *iptr;
     298             : 
     299             :     /* Blooming each column */
     300       76548 :     for (i = 0; i < state->nColumns; i++)
     301             :     {
     302             :         /* skip nulls */
     303       51032 :         if (isnull[i])
     304           0 :             continue;
     305             : 
     306       51032 :         signValue(state, res->sign, values[i], i);
     307             :     }
     308             : 
     309       25516 :     return res;
     310             : }
     311             : 
     312             : /*
     313             :  * Add new bloom tuple to the page.  Returns true if new tuple was successfully
     314             :  * added to the page.  Returns false if it doesn't fit on the page.
     315             :  */
     316             : bool
     317       25554 : BloomPageAddItem(BloomState *state, Page page, BloomTuple *tuple)
     318             : {
     319             :     BloomTuple *itup;
     320             :     BloomPageOpaque opaque;
     321             :     Pointer     ptr;
     322             : 
     323             :     /* We shouldn't be pointed to an invalid page */
     324             :     Assert(!PageIsNew(page) && !BloomPageIsDeleted(page));
     325             : 
     326             :     /* Does new tuple fit on the page? */
     327       25554 :     if (BloomPageGetFreeSpace(state, page) < state->sizeOfBloomTuple)
     328          38 :         return false;
     329             : 
     330             :     /* Copy new tuple to the end of page */
     331       25516 :     opaque = BloomPageGetOpaque(page);
     332       25516 :     itup = BloomPageGetTuple(state, page, opaque->maxoff + 1);
     333       25516 :     memcpy((Pointer) itup, (Pointer) tuple, state->sizeOfBloomTuple);
     334             : 
     335             :     /* Adjust maxoff and pd_lower */
     336       25516 :     opaque->maxoff++;
     337       25516 :     ptr = (Pointer) BloomPageGetTuple(state, page, opaque->maxoff + 1);
     338       25516 :     ((PageHeader) page)->pd_lower = ptr - page;
     339             : 
     340             :     /* Assert we didn't overrun available space */
     341             :     Assert(((PageHeader) page)->pd_lower <= ((PageHeader) page)->pd_upper);
     342             : 
     343       25516 :     return true;
     344             : }
     345             : 
     346             : /*
     347             :  * Allocate a new page (either by recycling, or by extending the index file)
     348             :  * The returned buffer is already pinned and exclusive-locked
     349             :  * Caller is responsible for initializing the page by calling BloomInitPage
     350             :  */
     351             : Buffer
     352          50 : BloomNewBuffer(Relation index)
     353             : {
     354             :     Buffer      buffer;
     355             :     bool        needLock;
     356             : 
     357             :     /* First, try to get a page from FSM */
     358             :     for (;;)
     359           0 :     {
     360          50 :         BlockNumber blkno = GetFreeIndexPage(index);
     361             : 
     362          50 :         if (blkno == InvalidBlockNumber)
     363          48 :             break;
     364             : 
     365           2 :         buffer = ReadBuffer(index, blkno);
     366             : 
     367             :         /*
     368             :          * We have to guard against the possibility that someone else already
     369             :          * recycled this page; the buffer may be locked if so.
     370             :          */
     371           2 :         if (ConditionalLockBuffer(buffer))
     372             :         {
     373           2 :             Page        page = BufferGetPage(buffer);
     374             : 
     375           2 :             if (PageIsNew(page))
     376           0 :                 return buffer;  /* OK to use, if never initialized */
     377             : 
     378           2 :             if (BloomPageIsDeleted(page))
     379           2 :                 return buffer;  /* OK to use */
     380             : 
     381           0 :             LockBuffer(buffer, BUFFER_LOCK_UNLOCK);
     382             :         }
     383             : 
     384             :         /* Can't use it, so release buffer and try again */
     385           0 :         ReleaseBuffer(buffer);
     386             :     }
     387             : 
     388             :     /* Must extend the file */
     389          48 :     needLock = !RELATION_IS_LOCAL(index);
     390          48 :     if (needLock)
     391          20 :         LockRelationForExtension(index, ExclusiveLock);
     392             : 
     393          48 :     buffer = ReadBuffer(index, P_NEW);
     394          48 :     LockBuffer(buffer, BUFFER_LOCK_EXCLUSIVE);
     395             : 
     396          48 :     if (needLock)
     397          20 :         UnlockRelationForExtension(index, ExclusiveLock);
     398             : 
     399          48 :     return buffer;
     400             : }
     401             : 
     402             : /*
     403             :  * Initialize any page of a bloom index.
     404             :  */
     405             : void
     406          52 : BloomInitPage(Page page, uint16 flags)
     407             : {
     408             :     BloomPageOpaque opaque;
     409             : 
     410          52 :     PageInit(page, BLCKSZ, sizeof(BloomPageOpaqueData));
     411             : 
     412          52 :     opaque = BloomPageGetOpaque(page);
     413          52 :     memset(opaque, 0, sizeof(BloomPageOpaqueData));
     414          52 :     opaque->flags = flags;
     415          52 :     opaque->bloom_page_id = BLOOM_PAGE_ID;
     416          52 : }
     417             : 
     418             : /*
     419             :  * Fill in metapage for bloom index.
     420             :  */
     421             : void
     422          10 : BloomFillMetapage(Relation index, Page metaPage)
     423             : {
     424             :     BloomOptions *opts;
     425             :     BloomMetaPageData *metadata;
     426             : 
     427             :     /*
     428             :      * Choose the index's options.  If reloptions have been assigned, use
     429             :      * those, otherwise create default options.
     430             :      */
     431          10 :     opts = (BloomOptions *) index->rd_options;
     432          10 :     if (!opts)
     433           0 :         opts = makeDefaultBloomOptions();
     434             : 
     435             :     /*
     436             :      * Initialize contents of meta page, including a copy of the options,
     437             :      * which are now frozen for the life of the index.
     438             :      */
     439          10 :     BloomInitPage(metaPage, BLOOM_META);
     440          10 :     metadata = BloomPageGetMeta(metaPage);
     441          10 :     memset(metadata, 0, sizeof(BloomMetaPageData));
     442          10 :     metadata->magickNumber = BLOOM_MAGICK_NUMBER;
     443          10 :     metadata->opts = *opts;
     444          10 :     ((PageHeader) metaPage)->pd_lower += sizeof(BloomMetaPageData);
     445             : 
     446             :     /* If this fails, probably FreeBlockNumberArray size calc is wrong: */
     447             :     Assert(((PageHeader) metaPage)->pd_lower <= ((PageHeader) metaPage)->pd_upper);
     448          10 : }
     449             : 
     450             : /*
     451             :  * Initialize metapage for bloom index.
     452             :  */
     453             : void
     454           8 : BloomInitMetapage(Relation index)
     455             : {
     456             :     Buffer      metaBuffer;
     457             :     Page        metaPage;
     458             :     GenericXLogState *state;
     459             : 
     460             :     /*
     461             :      * Make a new page; since it is first page it should be associated with
     462             :      * block number 0 (BLOOM_METAPAGE_BLKNO).
     463             :      */
     464           8 :     metaBuffer = BloomNewBuffer(index);
     465             :     Assert(BufferGetBlockNumber(metaBuffer) == BLOOM_METAPAGE_BLKNO);
     466             : 
     467             :     /* Initialize contents of meta page */
     468           8 :     state = GenericXLogStart(index);
     469           8 :     metaPage = GenericXLogRegisterBuffer(state, metaBuffer,
     470             :                                          GENERIC_XLOG_FULL_IMAGE);
     471           8 :     BloomFillMetapage(index, metaPage);
     472           8 :     GenericXLogFinish(state);
     473             : 
     474           8 :     UnlockReleaseBuffer(metaBuffer);
     475           8 : }
     476             : 
     477             : /*
     478             :  * Parse reloptions for bloom index, producing a BloomOptions struct.
     479             :  */
     480             : bytea *
     481          42 : bloptions(Datum reloptions, bool validate)
     482             : {
     483             :     BloomOptions *rdopts;
     484             : 
     485             :     /* Parse the user-given reloptions */
     486          42 :     rdopts = (BloomOptions *) build_reloptions(reloptions, validate,
     487             :                                                bl_relopt_kind,
     488             :                                                sizeof(BloomOptions),
     489             :                                                bl_relopt_tab,
     490             :                                                lengthof(bl_relopt_tab));
     491             : 
     492             :     /* Convert signature length from # of bits to # to words, rounding up */
     493          38 :     if (rdopts)
     494          38 :         rdopts->bloomLength = (rdopts->bloomLength + SIGNWORDBITS - 1) / SIGNWORDBITS;
     495             : 
     496          38 :     return (bytea *) rdopts;
     497             : }

Generated by: LCOV version 1.13