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

Generated by: LCOV version 1.13